数据结构期末复习.pdf

《数据结构期末复习.pdf》由会员分享，可在线阅读，更多相关《数据结构期末复习.pdf（140页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、练习一1.第 16题要将现实生活中的数据转化为计算机所能表示的形式，其转化过程依次为()。A.逻辑结构、存储结构、机外表示B.存储结构、逻辑结构、机外表示C.机外表示、逻辑结构、存储结构D.机外表示、存储结构、逻辑结构答案:C2.第 17题关于矩阵的三元组表表示，以下叙述正确的是()。A.转置运算时只需把每个三元组的行、列下标互换即可。B.存储时只需要各非零元素的三元组信息，不需要其它信息。C.适合于对称矩阵的压缩存储。D.访问元素时不能随机存取。答案:D3.第 24题对长度为1 0 的顺序表进行查找，若查找前面5 个元素的概率相同，均 为 1/8,查找后面5个元素的概率相同，均为3/4 0,

2、则查找任一元素的平均查找长度为()。A.5.5B.5C.39/8D.19/4答案:C4.第 25题若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用0 存储方式最节省运算时间。A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表答案:D5.第 27题将数组称为随机存储结构是因为()。A.数组元素是随机的B.随时可以对数组元素进行访问C.对数组的任一元素的存取时间是相等的D.数组的存储结构是不定的答案:C6.第 28题在下列排序方法中，空间复杂性为O(log2n)的方法为0。A.直接选择排序B.归并排序C.堆排序D.快速排序答案:D7.第 30题

3、对 n 个顶点和e 条边的有向图，以邻接矩阵存储，则求图中某顶点入度的时间复杂度为()。A)O(n)B)O(e)C)O(n+e)D)O(n2)A.AB.BC.CD.D答案:A8.第 31题图的广度遍历必须借助()作为辅助空间。A.栈B.队列C.查找表D.数组答案:B9.第 39题基数排序中的“基数”可以是0。A.10B.8C.16D.以上都可以答案:D10.第 40题n 个记录直接插入排序时所需的记录最少比较次数是()。A.n-1B.nC.n(n-l)/2D.n(n+l)/2答案:A11.第 41题下图所示二叉树对应的森林中有0 棵树。A.1B.2C.3D.不确定答案:C12.第 42题对于有

4、向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为()。A.求顶点的邻接点B.求顶点的度C.深度优先遍历D.广度优先遍历答案:B13.第52题二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序()。A.可能改变B.一定会改变C.一定不改变D.可能变也可能不变答案:C14.第53题下列叙述错误的是()。A.多维数组是向量的推广。B.多维数组是非线性结构。C.如果将二维数组看成由若干个行向量组成的一维数组，则为线性结构。D.对矩阵进行压缩存储的目的是为了数据加密。答案:D15.第54题以下关于算法叙述不正确的是0。A.时间和空间性能往往是一对矛盾B.常常可牺牲空间性能换取时间性能C.常常可牺

5、牲时间性能换取空间性能D.时间和空间性能并不会矛盾答案:D16.第55题由同一关键字集合构造的各棵二叉排序树0。A.形态和平均查找长度都不一定相同B.形态不一定相同，但平均查找长度相同C.形态和平均查找长度都相同D.形态相同，但平均查找长度不一定相同答案:A1 7.第56题算法的时间复杂度取决于()。A.问题的规模B.数据的初始状态C.A 和 BD.以上都不是答案:C1 8.第57题对二叉排序树进行()，可以得到各结点键值的递增序列。A.先根遍历B.中根遍历C.层次遍历D.后根遍历答案:B1 9.第58题串是()。A.一些符号构成的序列B.有限个字母构成的序列C.一个以上的字符构成的序列D.有

6、限个字符构成的序列答案:D2 0.第59题以下广义表关系正确的是0。A.线性表 再入表 纯表v 递归表B.线性表 纯表 递归表 再入表C.纯表 线性表 再入表 递归表D.线性表 纯表v 再入表v 递归表答案:D21.第63题以下叙述错误的是()。A.数据的三个层次是数据、数据元素、数据项B.数据类型是指相同性质的计算机数据的集合C.每种逻辑结构都有一个运算的集合D.储存结构中不仅要储存数据的内容，还要把数据间的关系表示出来。答案:B22.第64题若只在线性表的首、尾两端进行插入操作，宜采用的存储结构为()。A.顺序表B.用头指针表示的单循环链表C.用尾指针表示的单循环链表D.单链表答案:C23

7、.第65题栈操作的原则是()。A.先进先出B.后进先出C.栈底删除D.以上都不是答案:B24.第66题若下图表示某广义表，则它是一利吟。A.线性表B.纯表C.再入表D.递归表答案:D25.第67题导致队列下溢的操作是()。A.队满时执行出队B.队满时执行入队C.队空时执行出队D.队空时执行入队答案:C27.第 69题关键字比较次数与数据的初始状态无关的排序算法是0。A.直接选择排序B.冒泡排序C.直接插入排序D.希尔排序答案:A28.第 70题对 n 个元素进行冒泡排序，最好情况下的只需进行()对相邻元素之间的比较。A.nB.n-1C.n+1D.n/2答案:B29.第 71题对 n 个顶点的有

8、向图，若所有顶点的出度之和为s,则所有顶点的入度之和为()。A.sB.s-1C.s+1D.n答案:A30.第 72题与邻接表表示相比，邻接矩阵表示更适合()。A.无向图B.有向图C.稠密图D.稀疏图答案:C31.第 89题多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为()。A.数组的元素处在行和列两个关系中B.数组的元素必须从左到右顺序排列C.数组的元素之间存在次序关系D.数组是多维结构，内存是一维结构答案:A32.第 90题高度为n、结点数也为n 的二叉树，共有。棵。A)nB)2n-lC)n-1D)2n-lA.AB.BC.CD.D答案:D33.第 91题单链表中增加头结点的目的是为

9、了()。A.使单链表至少有一个结点B.标识表结点中首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储答案:C34.第 92题对 n 个结点的二叉树，按()遍历顺序对结点编号(号码为1 n)时，任一结点的编号等于其左子树中结点的最大编号加1,又等于其右子树中结点的最小编号减loA.前根B.中根C.后根D.层次答案:B35.第 93题算法分析是指0。A.分析算法的正确性B.分析算法的可读性C.分析算法的健壮性D.分析算法的时空性能答案:D36.第 94题栈和队列的共同特点是0。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点答案:C37.第 95题下列关于

10、串的叙述中，正确的是0。A.一个串的字符个数即该串的长度B.一个串的长度至少是1C.空串是由空格字符组成的串D.两个串若长度相同，则它们相等答案:A38.第 96题希尔排序的增量序列必须是0。A.递增的B.随机的C.递减的D.任意的答案:C39.第 97题在不完全排序的情况下，就可以找出前几个最大值的方法是()。A.快速排序B.直接插入排序C.堆排序D.归并排序答案:C40.第 98题若 要 在 0(1)的时间内将两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向()。A.各自的头结点B.各自的尾结点C.各自的第一个元素结点D.一个表的头结点，另一个表的尾结点答案:B41.第 9

11、9题在 n 个顶点和e 条边的无向图的邻接表中，边结点的个数为0。A.nB.n*eC.eD.2*e答案:D42.第 100题若一个图中包含有k 个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用()次深度优先搜索遍历的算法。A.1B.kC.k-1D.k+1答案:B43.第 22题连通图的BFS生成树一般比DFS生成树的高度小。答案:正确44.第 23题利用栈可将递归程序转化成非递归程序。答案:正确45.第 29题每一种逻辑结构只能对应一种存储结构。答案:错误46.第 32题用线性探测法解决突出时，同义词在散列表中是相邻的。47.第 33题徒表中逻辑上相邻的元素在物理位置上不一定相邻

12、。答案:正确48.第 34题稀疏矩阵就是矩阵的元素很少。答案:错误49.第 35题堆排序是一种巧妙的树型选择排序。答案:正确50.第 36题图 G 的生成树T 是 G 的子图。答案:正确51.第 37题二叉树中不可能有两个结点在先根、中根和后根序列中的相对次序都不变.答案:错误52.第 43题若二叉树中没有度为1 的结点，则为满二叉树。答案:错误53.第 44题空串并不是由空白字符组成的串。答案:正确54.第 45题在顺序表中按值查找运算的复杂性为0(1)。答案:错误55.第 46题如果根结点的左子树和右子树高度差不超过1,则该二叉树是平衡二叉树。答案:错误56.第 47题排序的目的是为了方便

13、以后的查找。答案:正确57.第 48题基数排序不需进行关键字间的比较，故执行时间比基于比较的排序方法要快。答案:错误58.第 49题如果网络中有多条边的权相同，则其最小生成树就不会是唯一的。答案:错误59.第 50题在栈的应用中，栈顶指针总是指向真正的栈顶。答案:错误60.第 73题线索二叉链表就是用结点的空指针域来存放某种遍历的前趋和后继线索，所以线索二叉链表中就没有空指针了。答案:错误61.第 74题数据的逻辑结构和运算集组成问题的数学模型，与计算机无关。答案:正确62.第 75题单链表中的头结点就是单链表的第一个结点。答案:错误63.第 76题一维数组是一种顺序表。答案:正确64.第 7

14、7题直接插入排序是稳定的，而 Shell排序就是调用若干趟直接插入排序，故也是稳定的。答案:错误65.第 78题二叉排序树上，以根到任一结点的路径为界，则：路径左边结点路径结点路径右边结点。答案:错误66.第 79题不是所有的有向图都可以进行拓扑排序，而能拓扑排序时，结果不一定唯一。答案:正确67.第 80题稀疏矩阵压缩存储后会丧失随机存取特性。答案:正确68.第 101题当问题具有先进先出特点时，就需要用到栈。答案:错误69.第 102题算法的时间复杂性越高，则计算机速度提高后，得到的收益就越大。答案:错误70.第 103题顺序表不需存放指针，链表要存放指针，故链表的存储空间要求总是比顺序表

15、大。答案:错误71.第 104题n 个结点的有向图，若它有n(n1)条边，则它一定是强连通的。答案:正确72.第 105题二路归并排序的核心操作是把两个有序序列合并为一个有序序列。答案:正确73.第 1题树的三种常用存储结构是：孩子链表表示法、和。答案：双亲链表、孩子兄弟链表74.第 2 题线索二叉树中，线索的含义是O答案：某种遍历的前趋或后继信息75.第 3 题运算定义在逻辑结构上，算法定义在结构上；运算指出“做什么”，算法指出。答案：储存；怎么做76.第 4 题下面程序段的时间复杂性为y=i;while(yn)y=y*3;答案：O(log3n)77.第 5 题下面程序段的时间复杂性为。fb

16、r(i=O;in;i+)for(j=0;jnext!=NULL&p-next-next=NULL83.第 11题内排序是指.答案：数据全部在内存中进行排序84.第 12题对 n 个结点的线索二叉树，线索有 个。答案:n+185.第 13题稀疏矩阵的三元组表示中，三元组是指非零元素的、和三项。答案:行号、列号、值86.第 14题四种基本逻辑结构是：一、树、图；可把它们分成两类：和。答案:集合、线性；线性、非线性87.第 15题程序设计的实质是：数据的表示和，或者说，程序=数据结构+。答案:数据的处理：算法88.第 18题设链栈结点结构为(data,next),to p 为栈顶指针，当执行入栈操作

17、时需执行下列语句：p=newnode;p-data=x;p-next=t o p;答案:top=p89.第 19题深度为k 的二叉树，结点数至多为_,结 点 数 至 少 为。答案：2k-l、k90.第 20题某完全二叉树的第5 层只有6 个结点，则其叶子结点数是o答案：1191.第 26题四种基本存储结构是：顺序、索引、；其中最基本的是：和o答案:链式、散列；顺序、链式92.第 60题散列表中同义词是指一o答案:键值不同但散列地址相同93.第 61题设元素al,a2,a3 a4,a5和 a6依次入栈，出栈顺序为a3,a5 a4,a6,a2,a l,则栈的容 量 至 少 为。答案：494.第 6

18、2题串The含 有 的 子 串 个 数 为。答案：795.第 81题“就地排序”是指排序算法辅助空间的复杂度为。答案：0(1)96.第 82题对 n 个顶点和e 条边的图，采用邻接矩阵和邻接表表示时，空间复杂性分别为和。答案:0(n2)、O(n+e)97.第 83题若有向图有2 个有向回路，则其拓扑序列有 个。答案：098.第 84题某树所有结点的度数之和为1 0 0,则 树 中 边 数 为 一。答案：10099.第 85题深度为k 的二叉树，叶子数至多为，叶子数至少为o答案:2k-1、1100.第 86题某哈夫曼树有109个结点，则其叶子数是，度为2 的 结 点 数 是 一 答案:55、54

19、101.第 87题某二叉树有50个结点，根的右子树有45个结点，则对应的森林中第一棵树的结点数为一。答案:55102.第 88题以 行 优 先 存 储 的 一 维 数 组 每 个 元 素 占 4 字节，A5的地址是1020,则数组的首地址是。答案:1004103.第 21题设计递归算法，判断二叉树t 是否满足小根堆的特点。二叉链表的类型定义如下：typedefintdatatype;/结点的数据类型，假设为inttypedefstructNODE*pointer;结点指针类型structNODEdatatypedata;pointerichild,rchild;；typede 巾 ointer

20、bitree;根指针类型答案：intdetect(bitreet)if(t=NULL)returnl;/空树看成真if(t-lchild!=NULL&t-lchild-datat-data)(t-rchild!=NULL&t-rchild-datat-data)return。;/左孩子 根，或右孩子 根，为假elseretumdetect(t-rchild)&detect(t-rchild);题目分数：2.5104.第 38题设计递归算法，求二叉排序树t 的高度。二叉链表的类型定义如下：typedefintdatatype;结点的数据类型，假设 为inttypedefstructNODE*po

21、inter;结点指针类型structNODE(datatypedata;pointerichild,rchild;)；typedemointerbitree;/根指针类型答案：inthigh(bitreet)intL,R;if(t=NULL)retumO;L=high(t-lchild);R=high(t-rchild);retumLR?L+l:R+1;1 0 5.第51题设计算法将顺序表L中所有的数字字符都移动到表的后端，要求元素的移动次数尽量少。顺序表类型定义如下：typedefchardatatype;结点的数据类型，假设为charconstintmaxsize=100;最大表长，假设为

22、 100typedefstructdatatypedatamaxsize;线性表的存储向量，第一个结点是data0intn;/线性表的当前长度sqlist;顺序表类型答案：voidmoves(sqlist*L)inti,j;datatypex;i=l;j=L-n;while(idataidatai,9)&idatai=,0,&L-datai=9,)&idatai;L-datai=L-dataj;L-dataj=x;i+；j-；练习二2.第2题下列编码中属前缀码的是()。A.1,01,000,001B.l,01,011,010C.0,10,110,llD.O,1,OO,11答案:A3.第 3 题

23、线性表采用链式存储时，其地址()。A.必须连续B.部分地址必须连续C.-定不连续D.连续与否均可答案:D4.第 4 题设计一个判断表达式中左右括号是否配对出现的算法，采用()数据结构最好。A.顺序表B.链表C.队列D.栈答案:D5.第 5 题执行下列程序段后，串 X 的值为0。S=abc；T=xyz；X=strcat(S,T);A.abcxyz”B.”xyzabcCJabc”D.xyz”答案:A7.第 7 题某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用()存储方式最节省运算时间。A.单链表B.双链表C.单循环链表D.带头结点的双循环链表答案:D9.第 9 题设

24、有向图n 个顶点和e 条边，进行拓扑排序时，总的计算时间为()。A)O(nlog2n)B)O(en)C)O(elog2n)D)O(n+e)A.AB.BC.CD.D答案:D10.第 22题在 n 个顶点和e 条边的无向图的邻接矩阵中，表示边存在的元素个数为()。A.nB.n*eC.eD.2*e答案:D1 1.第 23题为便于判别有向图中是否存在回路，可借助于()。A.广度优先搜索算法B.最小生成树算法C.最短路径算法D.拓扑排序算法答案:D12.第 29题栈和队列都是0。A.限制存取位置的线性结构B.顺序存储的线性结构C.链式存储的线性结构D.限制存取位置的非线性结构答案:A13.第 30题在

25、C 语言中，串的存储方式是()。A.顺序存储B.散列存储C.索引存储D.链式存储答案:A15.第 32题用链表表示线性表的优点是()。A.便于随机存取B.花费的存储空间较顺序存储少C.便于插入和删除D.数据元素的物理顺序与逻辑顺序相同答案:C16.第 33题对有向图，下面()种说法是正确的。A.每个顶点的入度等于出度B.每个顶点的度等于其入度与出度之和C.每个顶点的入度为0D.每个顶点的出度为0答案:B17.第 34题图的深度遍历必须借助()作为辅助空间。A.栈B.队列C.查找表D.数组答案:A1 8.第 46题已知森林 F=T1,T2,T 3 ,各棵树Ti(i=l,2,3)中所含结点的个数分

26、别为7,3,5,则与F 对应的二叉树的右子树中的结点个数为0。A.10B.12C.8D.15答案:C20.第 56题下列排序方法中，不稳定的是0。A.冒泡排序B.归并排序C.希尔排序D.直接插入排序答案:C21.第 57题以下叙述错误的是()。A.树的先根遍历需要借助栈来实现。B.树的层次遍历需要借助队列来实现。C.树的后根遍历与对应二叉树的后根遍历相同。D.树的先根序列与对应二叉树的先根序列相同。答案:C2 2.第 58题在顺序表中，数据元素之间的逻辑关系用()。A.数据元素的相邻地址表示B.数据元素在表中的序号表示C.指向后继元素的指针表示D.数据元素的值表示答案:A24.第 60题为查找

27、某一特定单词在文本中出现的位置，可应用的串运算是()。A.插入B.删除C.串联接D.子串定位答案:D25.第 61题在待排关键字序列基本有序的前提下，效率最高的排序方法是()。A.直接插入排序B.快速排序C.直接选择排序D.归并排序答案:A26.第 62题循环链表的主要优点是()。A.不在需要头指针了B.已知某个结点的位置后，能够容易找到他的直接前趋C.在进行插入、删除运算时，能更好的保证链表不断开D.从表中的任意结点出发都能扫描到整个链表答案:D27.第 63题从理论上讲，将数据以0 结构存放，查找一个数据的时间不依赖于数据的个数n。A.二叉查找树B.链表C.散列表D.顺序表答案:C28.第

28、 64题下面关于线性表的叙述错误的是()。A.线性表采用顺序存储，必须占用一片地址连续的单元；B.线性表采用顺序存储，便于进行插入和删除操作：C.线性表采用链式存储，不必占用一片地址连续的单元；D.线性表采用链式存储，便于进行插入和删除操作；答案:B3 3.第 83题在 AVL树中，任一结点的()。A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左、右子树的结点数均相同D.左、右子树结点数差的绝对值不超过1答案:B3 4.第 84题设输入序列为A,B,C,D,借助一个队列得到的输出序列可能是()。A.ABCDB.DCBAC.任意顺序D.以上都不是答案:A35.第 91题下列排

29、序算法中，当初始数据有序时，花费时间反而最多的是()。A.起泡排序B.希尔排序C.堆排序D.快速排序答案:D36.第 92题若结点的存储地址可以反映数据间的逻辑关系，则相应的存储结构应为()。A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构答案:A37.第 93题若某线性表中最常用的操作是取第i 个元素和找第i 个元素的前趋元素，则采用()存储方式最节省运算时间()。A.单链表B.顺序表C.双链表D.单循环链表答案:B38.第 94题队列操作的原则是()。A.先进先出B.后进先出C.队尾删除D.队头插入答案:A40.第 96题n 个记录直接选择排序时所需的记录最多交换次数是0。

30、A.n-1B.nC.n(n-l)/2D.n(n+l)/2答案:A41.第 97题某二叉树的先根遍历序列和后根遍历序列相同，则该二叉树的特征是0。A.高度等于其结点数B.任一结点无左孩子C.任一结点无右孩子D.空或只有一个结点答案:D4 2.第 98题如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是0。A.有向完全图B.连通图C.强连通图D.有向无环图答案:D4 4.第 11题计算机的内、外存越大，算法的空间复杂性就越低。答案:错误47.第 14题在拓扑序列中，若两点V i和 V j相邻，则从V i到 V j有路径。答案:错误48.第 15题数组的基本运算有读、写、插入、删除等。答案:

31、错误49.第 21题在二叉排序树中，即使删除一个结点后马上再插入该结点，该二叉排序树的形态也可能不同。答案:正确52.第 26题图的生成树不唯一，但图的最小生成树是唯一的。答案:错误53.第 27题设串的长度为n,则其子串个数为n(n+l)/2。答案:错误54.第 35题消除递归不一定需要使用栈。答案:正确56.第 37题每个节点一个链域的链表是单链表，每个节点两个链域的链表是双链表。答案:错误58.第 39题Shell排序的时间性能与增量序列的选取有关，但关系不大。答案:错误59.第 40题若有向图中含有一个或多个环，则其顶点间不存在拓扑序列。答案:正确60.第 41题线性表、树、图等都可以

32、用广义表表示。答案:正确62.第 68题在线索二叉树上，求结点的（遍历）前趋和后继时可利用线索得到，即不必进行遍历了。答案:错误63.第 69题单链表中取第i 个元素的时间与i 成正比。答案:正确64.第 70题无向图中边数等于邻接矩阵中1 的个数的一半；也等于邻接表中的边表结点数的一半。答案:正确67.第 99题由二叉树的先根和后根序列可以唯一确定该二叉树。答案:错误68.第 100题算法的正确性，一般不进行形式化的证明，而是用测试来验证。答案:正确7 0.第 102题广义表不仅是线性表的推广，也是树的推广。答案:正确72.第 104题缩短关键路径上活动的工期一定能够缩短整个工程的工期。答案

33、:错误73.第 16题散列表既是一种方式又是一种一方法。答案：储存、查找储存、查找74.第 17题某完全二叉树的第5 层只有6 个结点，则其叶子结点数是一。答案：11II75.第 18题在无头结点的双链表中，指针P 所指结点是第一个结点的条件是。答案：p-prior=NULLp-prior=NULL76.第 19题可以将排序算法分为：插入排序、选择排序、分配排序。答案：交换排序、归并排序交换排序、归并排序77.第 20题设 C 数组A2010每个元素占2 个存储单元，且第1个元素的首地址为2000,则元素A89的存储地址为。答案：2178217878.第 42题对 n 个顶点和e 条边的无向图

34、，采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂性分别为和。答案：O(n)O(e/n)O(n)、O(e/n)79.第 43题将长度为2n和 n 的有序表归并成一个有序表，至少进行一次键值比较。答案：nn80.第 44题若有向图有2 个有向回路，则其拓扑序列有 个。答案：0081.第 45题算法满足的五个重要特性是：、输入、输出；其中区别于程序的地方是o答案：有穷性、确定性、可行性；有穷性。有穷性、确定性、可行性；有穷性。82.第 48题查找表的逻辑结构是一。答案：集合集合83.第 49题设链栈结点结构为(data,next),to p 为栈顶指针，当执行入栈操作时需执行下列语句：p=ne

35、wnode;p-data=x;p-next=t o p;答案：top=ptop=p8 5.第 51题从 n 个结点的二叉排序树中查找一个元素，平均时间复杂性大致为。答案：O(log2n)O(log2n)8 6.第 52题深度为k 的二叉树，结 点 数 至 多 为,结 点 数 至 少 为。答案：2k-K k88.第 54题在有向无环图中，若存在一条从顶点i 到顶点j 的弧，则在顶点的拓扑序列中，顶点i 与顶点j 的 先 后 次 序 是。答案：i 在 j 之前i 在j 之前89.第 55题对 n 个结点的线索二叉树，线索有 个。答案：n+1n+190.第 74题在一个双链表中删除指针p 所指结点，

36、可执行以下操作：p-next-prior=_；p-prior-next=_；答案：p、p、deletepp、p deletep91.第 75题所有基于比较的排序方法，平均时间复杂性最好时为。答案：O(nlog2n)O(nlog2n)92.第 76题n 个顶点的连通图至少 条边，最多 条边。答案：n-1、n(n-1 )/2n-1 n(n-1 )/293.第 77题将对称矩阵A 1 .n的下三角(含对角线)按行序存入一维数组B 1 .n(n+l)/2中，设 Aij对应位置B k,则 1 100(或 101)95.第 80题设元素al,a2,a3 a4,a5和 a6依次入栈，出栈顺序为a3,a5,a

37、4,a6 a2,a l,则栈的容 量 至 少 为 答案：497.第 85题在 150个结点的有序表中二分法查找，不论成功与否，键值比较次数最多为一。答案：8898.第 86题对 100个结点的树，所有结点的度数之和为。答案：999999.第 87题用 head。和 tail。函数表示在广义表A=(a,(x,y,z),b)中取出原子x 的运算是：。答案：head(head(tail(A)head(head(tail(A)100.第 88题Prim算法求最小生成树的时间为,对图比较有利。答案：O(n2)、稠密O(n2)、稠密101.第 89题评价排序效率的主要标准是一答案：关键字比较次数、移动次数

38、关键字比较次数、移动次数102.第 90题数组中，每个元素占3 个单元，从首地址SA开始存放，若该数组按列存放，则元素A85的地址是答案：SA+117SA+117103.第 28题设计递归算法，求二叉排序树t 的叶子数。二叉链表的类型定义如下：typedefintdatatype;结点的数据类型，假设为inttypedefstructNODE*pointer;结点指针类型structNODE(datatypedata;pointerichild,rchild;)；typedemointerbitree;/根指针类型答案：intleafi(bitreet)intL,R;if(t=NULL)ret

39、urnO;if(t-chi ld=N U L L&t-rch i ld=N U L L)retum I;L=leaf(t-lchild);R=leaf(t-rchild);retumL+R;intleafi(bitreet)intL,R;if(t=NULL)retumO;if(t-child=NULL&t-rchild=NULL)return 1;L=leaf(t-lchild);R=leaf(t-rchild);return L+R;题目分数：2.51 0 4.第73题设计递归算法，判断二叉树t是否满足小根堆的特点。二叉链表的类型定义如下:typedefintdatatype;结点的数据类型

40、，假设为inttypedefstructNODE*pointer;结点指针类型structNODEdatatypedata;pointerichild,rchild;)；ty pedefpo interb i tree;根指针类型答案：intdetect(bitreet)if(t=NULL)retum 1，空树看成真ifKt-lchild!=NULL&t-lchild-datat-data)(t-rchiId!=NULL&t-rchild-datat-data)return。;/左孩子 根，或右孩子,根，为假elseretumdetect(t-rchild)&detect(t-rchild);

41、)intdetect(bitreet)if(t=NULL)return 1;/空树看成真if(t-lchild!=NULL&t-lchild-datat-data)|(t-rchild!=NULL&t-rchild-datat-data)return。;/左孩子 根，或右孩子,根，为假elseretumdetect(t-rchild)&detect(t-rchild);题目分数：2.51 0 5.第 105 题设计一个递归算法，求二叉树t 中度为1 的结点数。设二叉链表类型定义如下。typedefintdatatype;结点的数据类型，假设为inttypedefstructNODE*point

42、er;结点指针类型structNODEdatatypedata;pointerichild,rchild;)；ty pedefpo interb i tree;根指针类型答案：intsuml(bitreet)intL,R;if(t=NULL)returnO;L=suml(t-lchild);R=suml(t-rchild);if(t-lchild=NULL&t-rchild!=NULL)(t-lchild!=NULL&t-rchild=NULL)return L+R+l;elsereturn L+R;intsuml(bitreet)intL,R;if(t=NULL)retumO;L=suml(

43、t-lchild);R=suml(t-rchild);if(t-lchild=NULL&t-rchild!=NULL)|(t-lchild!=NULL&t-rchild=NULL)retumL+R+l;elsereturn L+R;题目分数：2.5作业总得分：0.0作业总批注：练习三2.第 2 题下列有关线性表的叙述中，正确的是0。A.元素之间是线性关系B.线性表中至少有一个元素C.任一元素有且仅有一个直接前趋D.任一元素有且仅有一个直接后继答案:A4.第 4 题关于十字链表中的叙述，错误的是0。A.便于查找每一行或列的非零元素B.每行、每列的非零元素分别组成行链表、列链表C.C.十字链表是一

44、种多重链表D.行链表、列链表的头结点不能共用答案:D5.第 5 题要解决散列引起的冲突问题，常采用的方法有()。A.数字分析法、平方取中法B.数字分析法、线性探测法C.二次探测法、平方取中法D.二次探测法、链地址法答案:D6.第 6 题静态查找表与动态查找表二者的根本差别在于()。A.它们的逻辑结构不一样B.施加在其上的操作不同C.所包含的数据元素的类型不一样D.存储实现不一样答案:B7.第 7 题在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用()。A.数据元素的相邻地址表示B.数据元素在表中的序号表示C.指向后继元素的指针表示D.数据元素的值表示答案:C8.第 8 题n 个顶点的强

45、连通图若只有n 条边，则该有向图的形状是0。A.无回路B.有回路C.环状D.树状答案:C9.第 9 题在 n 个顶点和e 条边的无向图的邻接表中，存放表头结点的数组的大小为()。A.nB.n+eC.n+2eD.e答案:A10.第 16题已知森林尸=11,T2,T 3 ,各棵树Ti(i=l,2,3)中所含结点的个数分别为7,3,5,则与F 对应的二叉树的右子树中的结点个数为()。A.10B.12C.8D.15答案:C11.第 23题()存储方式适用于折半查找。A.键值有序的单链表B.键值有序的顺序表C.键值有序的双链表D.键值无序的顺序表答案:B1 2.第 24题在有头结点的单链表L 中，向表头

46、插入一个由指针p 指向的结点，则执行0。A.L=p;p-next=L;B.p-next=L;L=p;C.p-next=L;p=L;D.p-next=L-next;L-next=p;答案:D1 4.第 26题有 n 个顶点的图形成一个环，则其生成树的个数为()。A.1B.n-1C.nD.n+1答案:c1 5.第 32题假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入散列表中，至少要进行()次探侧。A.k-1B.kC.k+1D.k(k+l)/2答案:D20.第 52题下列哪种情况需要遇到队列()。A.迷宫求解B.括号匹配C.多级函数调用D.多项打印任务的安排答案:D21.第 53题

47、下图是一棵()。A.4阶 B-树B.4 阶 B+树C.3阶 B-树D.3阶 B+树答案:D22.第 59题时间复杂性为O(nlog2n)且空间复杂性为0(1)的排序方法是()。A.归并排序B.堆排序C.快速排序D.锦标赛排序答案:B23.第 60题以下叙述错误的是()。A.数据可分为数值型和非数值型B.数据类型可分为原子类型和结构类型C.运算可分为加工型和引用型D.数据结构可分为逻辑结构和非逻辑结构答案:D2 5.第 62题求单链表中当前结点的后继和前趋的时间复杂度分别是()。A.O(n)和 0(1)B.0和 0(1)C.O和 0(n)D.O(n)和 0(n)答案:C28.第 65题最好和最坏

48、时间复杂度均为O(nlog2n)且稳定的排序方法是0。A.快速排序B.堆排序C.归并排序D.基数排序答案:C29.第 68题在待排关键字序列基本有序的前提下，效率最高的排序方法是()。A.直接插入排序B.快速排序C.直接选择排序D.归并排序答案:A30.第 69题为便于判别有向图中是否存在回路，可借助于()。A.广度优先搜索算法B.最小生成树算法C.最短路径算法D.拓扑排序算法答案:D31.第 73题下面的二叉树中，()不是完全二叉树。A.AB.BC.CD.D答案:C32.第 74题如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是()。A.有向完全图B.连通图C.强连通图D.有向无环

49、图答案:D33.第 87题下列排序算法中，当初始数据有序时，花费时间反而最多的是()。A.起泡排序B.希尔排序C.堆排序D.快速排序答案:D34.第 88题若结点的存储地址可以反映数据间的逻辑关系，则相应的存储结构应为()。A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构答案:A3 6.第 90题对线性表进行二分查找时，要求线性表必须()。A.以顺序方式存储B.以链接方式存储C.顺序存储，且结点按关键字有序排序D.链式存储，且结点按关键字有序排序答案:C3 9.第 93题在下列排序方法中，空间复杂性为O(n)的方法为0。A.快速排序B.直接插入排序C.堆排序D.归并排序答案:D

50、4 1.第 95题在二叉链表上交换所有分支结点左右子树的位置，则利用()遍历方法最合适。A.前序B.中序C.后序D.按层次答案:C48.第 28题不可能有二叉树的任何遍历次序是相同的。答案:错误49.第 29题在数据结构中，算法的空间耗费包括代码和数据两部分。答案:错误50.第 30题二叉排序树的形态与关键字的输入序列有关，但平衡二叉排序树是相同的。答案:错误51.第 31题广义表不仅是线性表的推广，也是树的推广。答案:正确52.第 33题有向图中顶点i 的出度等于邻接矩阵中第i 行 中 1 的个数；入度等于第i 列 中 1 的个数。答案:错误54.第 35题如果n 个顶点的无向图有n 条边，