数据结构与算法模拟题及参考答案

数据结构与算法模拟题及参考答案

一、单选题（共题，每题分，共分）

861861.适用于压缩存储稀疏矩阵的两种存储结构是A、十字链表和二叉链表B、邻接矩阵和十字链表C、三元组表和十字链表D、三元组表和邻接矩阵正确答案C

2.树最适合于用来表示A、元素之间无联系的数据B、元素之间具有分支层次关系的数据C、无序数据元素D、有序数据元素正确答案B

3.导空栈S进行Push和Pop操作，入栈序列为a,b,c,d,e经过Push,Push,Pop,Push,Pop,Push,Push,Pop操作后,得到的出栈序列是A、b,c,eB、b,a,cC b,c,aD、b,a,e正确答嚏A

4.若AVL.树的深度是6（空树的深度定义为7）,则该树的最少结点数是A、13B、17C、20D、33正确容案.D

5.数据结初研究的内容是（）、数据的逻辑结构AB、数据的存储结构C、建立在相应逻辑结构和存储结构上的算法D、包括以上三个方面正确答案D

6.以下说法正确的是（）oA、一些表面上很不相同的数据可以有相同的逻辑结构B、数据结构是带有结构的各数据项的集合C、数据元素是数据的最小单位D、数据项是数据的基本单位正确答案A

7.对于外排序中的k路归并，k不取很大值的首要原因是、输入、输出的时间会增多AB、归并时的比较次数会增多正确答案B

57.设每年d叉树的结点有d个指针指向子树，有n个结点的d叉树有多少空链域？A、n d-1B、nd-1+1C、nd-1+1D、nd正确答案C

58.对初诺数据序列{8,3,9,11,2,1,4,7,5,10,6}进行希尔排序若第一趟排序结果为1,3,7,5,2,6,4,9,11,10,8,第二趟排序结果为1,2,6,4,3,7,5,8,11,10,9,则两趟排序采用的增量间隔依次是、5,2AB、5,3C、3,1D、3,2正确答案B

59.设有1000个元素的有序序列，如果用二分插入排序再插入一个元素，则最大比较次数是、10AB、1000C、500D、999正确答案A

60.下面的程序段违反了算法的原则void sam{int n=2;whi Ien%2==0n+=2;printf u%dn,n;}、确定性AB、可行性C、健壮性D、有穷性正确答案D61,将10；

12、

1、

14、

6、、

8、

15、

3、

9、7逐个按顺序插入到初始5为空的最小堆小根堆中，然后连续执行两次删除最小元素操作DeleteMin,此后堆顶的元素是什么？、5AB、6C、7D、9正确答案A

62.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点则采用哪种存储方式最节省运算时间？、单链表AB、双链表C、单循环链表D、带头结点的双循环链表正确答案D

63.如果信环队列用大小为m的数组表示，且用队头指针front和队列元素个数size代替一般循环队列中的front和rear指针来表示队列的范围，那么这样的循环队列可以容纳的元素个数最多为、m-1AB、m+1C、mD、不能确定正确答案C

64.已知一个长度为16的顺序表L,其元素按关键字有序排列若采用二分查找法查找一个L中不存在的元素，则关键字的比较次数最多是、4AB、6C、7D、5正确答案D

65.在将薪据序列6,1,5,9,8,4,7建成大根堆时，正确的序列变化过程是A、6,1,7,9,8,4,5T6,9,7,1,8,4,59,6,7,1,8,4,5TT9,8,7,1,6,4,5B、6,9,5,1,8,4,7T9,6,5,1,8,4,7T9,8,9,6,7,1,8,4,5T7,1,6,4,5C、6,1,7,9,8,4,5T7,1,6,9,8,4,5T7,9,6,1,8,4,5T9,7,6,1,8,4,5T9,8,6,1,7,4,5D、6,9,5,1,8,4,7T6,9,7,1,8,4,5T9,6,7,1,8,4,5T9,8,7,1,6,4,5正确答案A

66.斐波加契数列FN的定义为:FOR,F1=1,FN=FN-1+FN-2,N=2,3,…用递归函数计算FN的空间复杂度是A、0IogNB、0N!C、OFND、0N正确答案D

67.某线桂表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用什么存储方式最节省运算时间？A、仅有头指针的单循环链表B、双链表C、仅有尾指针的单循环链表D、单链表正确答案C

68.在有n n1000个元素的升序数组A中查找关键字x查找算法的o伪代码如下所示k=0;whi Iekn且A[k]xk=k+3;ifkn且A[k]=x查找成功；else ifk-1n且A[k-1]==X查找成功；elseifk-2n且A[k-2]=x查找成功;else查找失败;本算法与二分查找折半查找算法相比，有可能具有更少比较次数的情形是A、当x不在数组中B、当x接近数组开头处C、当x接近数组开头处D、当x位于数组中间位置正确答案B

69.在AOE・网中，什么是关键路径？A、最短回路B、最长回路C、从第一个事件到最后一个事件的最短路径D、从第一个事件到最后一个事件的最长路径正确答案D

70.设有二个12X12的对称矩阵M,将其上三角部分的元素mi,j1WiWjW12按行优先存入C语言的一维数组N中，元素m6,6在N中的下标是、50AB、51C、55D、66正确答案A

71.将｛2815,42,18,22,5,40｝依次插入初始为空的二叉搜索树则该树的后序遍历结果是A、5,15,18,22,40,42,28B、5,22,15,40,18,42,28C、5,22,18,15,40,42,28D、28,22,18,42,40,15,5正确答案C

72.数据地构讨论问题的最小单元为A、数据结构B、数据项C、数据对象D、数据元素正确答案.B

73.在快施排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左右指针都不停止移动，那么当所有元素都相等时，算法的时间复杂度是多少？、0IogNAB、0NI ogNC、0N2D、0N正确答案C

74.在一个不带头结点的非空链式队列中，假设f和r分别为队头和队尾指针,则插入s所指的结点运算是A、s-next=s;r=s;B、s-next=f;f=s;C千一〉next=s;f=s;D、r-next=s;r=s;正确答案D

75.一个看N个顶点的强连通图至少有多少条边？A、N（N-1）B、NC、N+1D、N-1正确答案B

76.以二文链表作为二叉树的存储结构，在具有n个结点的二叉链表中（n0）,空链域的个数为—、n+1AB、n-1C、nD、无法确定正确答案A

77.以下数据结构中，（）是非线性数据结构、树AB、栈C、字符串D、队列正确答案A

78.算法的时间复杂度取决于（）oA、问题的规模B、待处理数据的初态C、计算机的配置D、A和B正确答案D

79.下列五组概念中，那一组不完全跟搜索引擎有关？A、词干提取，哈希散列，压缩B、分布式索引，回溯法，查询C、倒排文件索引，停用词，准确率D、倒排表，阈值设置，召回率正确答案.B

80.已知三维数组A按行优先方式存储，每个元素占用1个存储单元若元素A

[0]

[0]的存储地址是100,A

[3]

[3]的存储地址是220,则元素A

[5]

[5]的存储地址是:、295AB、300C、301D、306正确答案B

81.在数据结构中，从逻辑上可以把数据结构分成（）oA、动态结构和静态结构B、内部结构和夕卜部结构C、紧凑结构和非紧凑结构D、线性结构和非线性结构正确答案D

82.在一子有2333个元素的最小堆中，下列哪个下标不可能是最大元的位置？A、2047B、2232C、1167D、1116正确答案D

83.设森及F中有三棵树，第

一、第

二、第三棵树的结点个数分别为M1,M2和M3则与森林F对应的二叉树根结点的右子树上的结点个数是A、M3B、M1C、M1+M2D、M2+M3正确答案D

84.将一素列数字顺序一个个插入一棵初始为空的AVL树下面哪个系列的第一次旋转是“右-左”双旋？、1,2,3,4,5,6AB、6,5,4,3,2,1C、4,2,5,6,3,1D、3,1,4,6,5,2正确答案D

85.数据序列｛3,2,4,9,8,11,6,20｝只能是下列哪种排序算法的两趟排序结果？A、快速排序B、选择排序C、冒泡排序D、插入排序正确答案A

86.采用首项式的非零项链式存储表示法，如果两个多项式的非零项分别为N1和N2个，最高项指数分别为M1和M2,则实现两个多项式相乘的时间复杂度是A、0M1+M2B、0N1+N2C、0N1XN2D、0M1XM2正确答案.C

二、多诬题共题，每题分，共分

3131.链表-时间复杂度在包含n个数据元素的链表中，的时间复杂度为0nA、访问第i个数据元素B、＜n个元素按升序排序C、在第i1WiWn个结点后插入一个新结点D、删除第i1WiWn个结点正确答案ACD2,排序算法的稳定性下列关于顺序表的排序算法中，是稳定的A、快速排序B、冒泡排序C、选择排序D、归并排序正确答案BD

3.关于顺序查找算法顺序查找算法能适用于A、元素无序的顺序表B、元素无序的链表C、元素有序的顺序表D、元素有序的链表正确答案ABCD

三、判断题共题，每题分，共分

261261.对N个不同的数据采用冒泡排序进行从大到小的排序，当元素基本有序时交换元素次数肯定最多A、正确B、错误正确答案B

2.如果无面图G必须进行两次广度优先搜索才能访问其所有顶点，则G中一定有回路、正确AB、错误正确答案B

3.Kruskal算法是通过每步添加一条边及其相连的顶点到一棵树，从而逐步生成最小生成树A、正确B、错误正确答案B

4.在散列表中，所谓同义词就是被不同散列函数映射到同一地址的两个元素A、正确B、错误正确答案B

5.对于二曲式队列，归并操作的平均时间复杂度是常数级A、正确B、错误正确答案B

6.用一维羲组G口存储有4个顶点的无向图如下G[]={0,1,0,1,1,0,0,0,1,0}则顶点2和顶点0之间是有边的A、正确B、错误正确答案A

7.任何二支搜索树中同一层的结点从左到右是有序的（从小到大）、正确AB、错误正确答案A

8.无向连窟图边数一定大于顶点个数减

1、正确AB、错误正确答案B

9.一棵有；24个结点的完全二叉树，其叶结点个数是确定的、正确AB、错误正确答案A

10.对AVL树中的任一结点，其左子树的高度一定比其右子树的高度诙*O、正确AB、错误正确答案B

11.Prim聿法是维护一个森林，每一步把两棵树合并成一棵A、正确B、错误正确答案B

12.无向容通图至少有一个顶点的度为

1、正确AB、错误正确答案B

13.若一段平衡二叉树的所有非叶结点的平衡因子都是0,则其必为完美二叉树A、正确B、错误正确答案A14,存在一棵总共有2016个结点的二叉树，其中有16个结点只有一个孩子、正确AB、错误正确答案B

15.关于哈夫曼树哈夫曼树中一定没有度为1的结点、正确AB、错误正确答案A

16.某二叉树的前序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无左孩子、正确AB、错误正确答案A

17.在散歹中，函数“插入”和“查找”具有同样的时间复杂度A、正确B、错误正确答案A

18.2N和NN具有相同的增长速度、正确AB、错误正确答案B

19.在有N个元素的最大堆中，随机访问任意键值的操作可以在0I ogN时间完成、正确AB、错误正确答案B

20.NI ogN2和NI ogN具有相同的增长速度A、正确B、错误正确答案A

21.若A*B都是一棵二叉树的叶子结点，则存在这样的二叉树，其前序遍历序列为・・.A...B..・，而中序遍历序列为・・.B...A...、正确AB、错误正确答案B

22.无向容通图所有顶点的度之和为偶数A、正确B、错误正确答案A

23.将

1、*

2、

3、

4、

5、6顺序插入初始为空的AVL树中，当完成这6个元素的插入后，该AVL树的先序遍历结果是

4、

2、

1、

3、

5、6OA、正确B、错误正确答案A

24.如果由结点｛1,2,3,4｝组成的AVL树的深度是3根结点的深度是1,则结点2或者结点3一定有两个子结点A、正确B、错误正确答案A

25.如果定向图G必须进行两次广度优先搜索才能访问其所有顶点，则G一定有2个连通分量、正确AB、错误正确答案A

26.在实血二项式队列时，每棵二项式树的子树是按规模递增的顺序链接的、正确AB、错误正确答案BC、k的上界是有序段的个数D、k必须是一个有限的整数正确答案A8,设最小尾小根堆的层序遍历结果为｛1,3,2,5,4,7,6用线性o时间复杂度的算法将该堆调整为最大堆大根堆，则该树的中序遍历结果为A、1,4,3,7,2,6,5B、4,1,3,7,6,52,C、3,5,4,2,6,1,7D、3,5,4,7,2,6,1正确答案D

9.G iven thefol lowingfour aIgor ithms withthe i r runt imesfor prob Iem s i ze100and theirtimecomplexities:AIgorithmRuntimeTimeComp lexityA1000N B500N2C200N3D150N4Which algorithmis thefastest forprobIemsize200A、AB、BC、CD、D正确答案C

10.如果G是一个有28条边的非连通无向图，那么该图顶点个数最少为多少？、8AB、9C、7D、10正确答案B

11.如果AVL树的深度为6空树的深度定义为-1,则此树最少有多少个结点？A、12B、20C、33D、64正确答案C

12.一棵展为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶子结点个数是、41AB、113C、122D、82正确答案D

13.设有二组关键字｛29,01,13,15,56,20,87,27,69,9,10,74,散列函数为Hkey=key%17,采用线性探测方法解决冲突试在0到18的散列地址空间中对该关键字序列构造散列表，则成功查找的平均查找长度为—、

1.33AB、

0.33C、

1.17D、

1.25正确答案A

14.对于谆列{49,38,65,97,76,13,27,50},按由小到大进行排序，下面哪一个是初始步长为4的希尔排序法第一趟的结果？、49,76,65,13,27,50,97,38AB、49,13,27,50,76,38,65,97C、13,27,38,49,50,65,76,97D、97,76,65,50,49,38,27,13正确蓍案:B

15.若top为指向栈顶元素的指针，判定栈S（最多容纳m个元素）为空的条件是A、S-top=m-1B、S-top=0C、S-top——1D、S-top!=m-1正确答案C119,7,911,114,120,122｝采用次位优则

16.对给定序列｛110,两趟收集后的结果为先LSD的基数排序,、7,110,119,114,911,120,122AB、7,110,119,114,911,122,120C、7,110,911,114,119,120,122D、110,120,911,122,114,7,119正确答案C

17.我们由一个有向图来表示航空公司所有航班的航线下列哪种算法最适合解决找给定两城市间最经济的飞行路线问题？A、D ijkstra算法B、Kruska I算法C、深度优先搜索D、拓扑排序算法正确答案A

18.双链装-插入结点在双链表中，将s所指新结点插入到p所指结点之前，其语句应该为A、s-prev=p-prev;s-next=p;p-prev=s;p-prev-next=s;=s;p-prev-next=s;B、p-prevs-prev=p-prev;s-next=p;=p-prev;s-next=p;C、s-prevp-prev-next=s;p-prev=s;D、p-prev-next=s;p-prev=s;s-prev=p-prev;s-next=p;正确答案D

19.数组A[

0..6,

0..5]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5,5]的地址是A、1175B、1180C、1200D、1205正确答案C

20.程序P1和P2时间复杂度的递推公式P1:T1=1,TN=TN/2+1;P2:T1=1,T N=2T N/2+1;则下列关于两程序时间复杂度的结论中最准确的是、均为OlogNAB、P1是OlogN,P2是0NC、均为0ND、P1是OlogN,P2是ONlogN正确答案B

21.由分另1带权为

9、

2、

5、7的四个叶子结点构成一棵哈夫曼树，该树的带权路径长度为、46AB、23C、37D、44正确答案D

22.如果定向图G必须进行两次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是、G肯定不是完全图AB、G有2个连通分量C、G一定不是连通图D、G中一定有回路正确答案D

23.在拓并排序算法中用堆栈和用队列产生的结果会不同吗？、是的肯定不同AB、肯定是相同的C、有可能会不同D、以上全不对正确答案C

24.给定敲列表大小为11,散列函数为HKey=Key%11按照线性探测冲突解决策略连续插入散列值相同的4个元素问此时该散列表的平均不成功查找次数是多少？A、21/11B、1C、4/11D、不确定正确答案A

25.对于先序遍历与中序遍历结果相同的二叉树为（）、一般二叉树AB、任一结点均无右孩子的二叉树C、任一结点均无左子树的二叉树D、以上都不是正确答案C

26.下面算法所执行的加法次数（）输入n,其中『23t为正整数输o出kk^-Owhi Ien=1dofor1to ndok=k+1n^-n/2return kA、lognB、nIognC、n2D、2n-1正确答案D

27.设一例非空完全二叉树T的所有叶节点均位于同一层，且每个非叶结点都有2个子结点若T有k个叶结点，则T的结点总数是A、2k-1B、2k-1C、2kD、k2正确答案B

28.已知前始为空的队列Q的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出队操作若Q的入队序列是

1、

2、

3、

4、5,则A、

5、

3、

1、

2、4B、

4、

1、

3、

2、5C、

4、

2、

1、

3、5D、

5、

4、

3、

1、2正确答案B

29.在有n

（1）个元素的最大堆（大根堆）中，最小元的数组下标可以是不能得到的出队序列是A、|_n/2j+2B、1C、L n/2j-1D、“2」L正确答案A

30.设h区不带头结点的单向链表在h的头上插入一个新结点t的语句是A、t-next=h-next;h=t;B、t-next=h;h=t;C、h=t;t-next=h;D、h=t;t-next=h-next;正确答案B

31.现有瓦列Q与栈S,初始时Q中的元素依次是｛1,2,3,4,5,6）（1在队头），S为空若允许下列3种操作

（1）出队并输出出队元素；

（2）出队并将出队元素入栈；

（3）出栈并输出出栈元素，则不能得到的输出序列是A、6,5,4,3,2,1B、2,3,4,5,6,1C、3,4,5,6,1,2D、1,2,5,6,4,3正确答案C

32.下列库序算法中，哪种算法可能出现在最后一趟开始之前，所有的元素都不在其最终的位置上？（设待排元素个数N2）A、快速排序B、堆排序C、插入排序D、冒泡排序正确答案C

33.二叉树的高度若根节点为高度1,一棵具有1025个结点的二叉树的高度为、10AB、11—1025之间C、10—1024之间D、11正确答案B

34.某队歹允许在其两端进行入队操作，但仅允许在一端进行出队操作若元素a、b、c、d、e依次入此队列后再进行出队操作，则不可能得到的出队序列是A db a c ebacd eC ec ba dD db ca e正确答案D

35.若数届元素序列｛11,12,13,7,8,9,23,4,5｝是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是:、A插入排序B、归并排序C、冒泡排序D、选择排序正确答案A

36.在散歹表中，所谓同义词就是A、两个意义相近的单词B、被不同散列函数映射到同一地址的两个元素C、具有相同散列地址的两个元素D、被映射到不同散列地址的一个元素正确答案C

37.算法分析的目的是（）A、研究算法中的输入和输出的关系B、分析算法的效率以求改进C、找出数据结构的合理性D、分析算法的易读性和文档性正确答案B

38.设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是A、n在m左方B、n是m祖先C、n在m右方D、n是m子孙正确答案A

39.下面说法中哪个是错误的A、任何AVL树的中序遍历结果是有序的从小到大B、任何最小堆的前序遍历结果是有序的从小到大C、任何搜索树中同一层的结点从左到右是有序的从小到大D、任何最小堆中从根结点到任一叶结点路径上的所有结点是有序的从小到大正确答案B

40.下面四种排序算法中，稳定的算法是、堆排序AB、归并排序C、快速排序D、希尔排序正确答案B

41.设一年堆栈的入栈顺序是

1、

2、

3、

4、5o若第一个出栈的元素是4,则最后一个出栈的元素必定是、1或者5AB、1C、5D、3正确答案A

42.下亩代码段的时间复杂度是x=n;//n1y=0;whi Iex2y+1*y+1y++;、0nAB、0n1/2C、01D、0log2n正确答案B

43.给定人口={46,23,8,99,31,12,85},调用非递归的归并排序加表排序执行第1趟后，表元素的结果是A、1,2,3,4,5,6,7B1,0,2,3,5,4,6C、3,6,1,5,2,7,4D、0,2,1,4,3,5,6正确答案B

44.设T是非空二叉树，若T的后序遍历和中序遍历序列相同，则T的形态是—、只有一个根结点AB、没有度为1的结点C、所有结点只有左孩子D、所有结点只有右孩子正确答案c

45.一棵菲空二叉树，若先序遍历与中序遍历的序列相同，则该二叉树oA、所有结点均无左孩子B、所有结点均无右孩子C、只有一个叶子结点D、为任意二叉树正确答案A

46.设栈S和队列Q的初始状态均为空，元素｛1,2,3,4,5,6,7依次进入栈S若每个元素出栈后立即进入队列Q,且7个元素出队的顺序是｛2,5,6,4,7,3,1｝,则栈S的容量至少是:A、1B、3C、2D、4正确答案D

47.若一济栈的入栈序列为

1、

2、

3、…、N,输出序列的第一个元素是i,则第j个输出元素是A、i-j-1B、j-i-1C、不确定D、i-j正确答案C

48.将172,3,6,5,4顺序一个个插入一棵初始为空的AVL树，会经历下列哪些旋转？A、两个“右-右”旋和一个“右-左旋B、一个“右-右”旋、一个“右-左”旋、一个“左-右”旋C、一个“右-右”旋和两个“右-左”旋D、两个“右-右”旋和一个“左-右”旋正确答案C

49.给定元向图G,从V0出发进行深度优先遍历访问的边集合为｛VO,V1,VO,V4,V1,V2,V1,V3,V4,V5,V5,V6｝贝lj下面哪条边不可能出现在G中？、V1,V5AB、VO,V6C、V4,V6D、VO,V2正确答案.A

50.从一年具有N个结点的单链表中查找其值等于X的结点时，在查找成功的情况下，需平均比较多少个结点？、N/2AB、NC、N-1/2D、N+D/2正确答案D

51.若将n个顶点e条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是、OnXeAB、0n2C、0nD、0n+e正确答案D

52.关于血的邻接矩阵，下列哪个结论是正确的？A、有向图的邻接矩阵总是不对称的B、无向图的邻接矩阵总是不对称的C、有向图的邻接矩阵可以是对称的，也可以是不对称的D、无向图的邻接矩阵可以是不对称的，也可以是对称的正确答案C

53.输入105个只有一位数字的整数，可以用0N复杂度将其排序的算法是A、插入排序B、快速排序C、希尔排序D、基数排序正确答案D

54.有六年元素以

6、、

4、

3、2s1的顺序进栈，问哪个不是合法的5出栈序列？A.453126B.346521C.234156D.543612正确答案B

55.一棵三叉树中有7个度为2的结点和5个度为1的结点，其总共有个结点、20AB、30C、18D、16正确答案A

56.链表-存储密度链表的存储密度、不能确定AB、小于1C、等于1D、大于1。