数据结构与算法练习题（含答案）

数据结构与算法练习题（含答案）

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

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

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

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

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

2.下列代码ifA+二B;}eIse fori=0;i N*2;i++forji；J—AB{fori=0;iN;i++forj=N*N;j=N*2；ji;j—A+二B；A、0NB、0N2C、0N3D、0N4正确答案c

3.设森林F中有三棵树，第

一、第

二、第三棵树的结点个数分别为的完全二叉树的结点个数小于或等于深度相同的满二叉树A、

①②③B、

②③④C、

①④D、

②④正确答案C

26.设数组S[]={93,946,372,9,146,151,301,485,236,327,43,892,采用最低位优先LSD基数排序将S排列成升序序列第1越分配、收集后，元素372之前、之后紧邻的元素分别是A、43,892B、236,301C、301,892D、485,301正确答案C

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

28.若栈S1中保存整数，栈S2中保存运算符，函数F依次执行下述各步操作1从S1中依次弹出两个操作数a和b;2从S2中弹出一个运算符op;3执行相应的运算b opa;4将运算结果压入S1中假定S1中的操作数依次是｛5,8,3,22在栈顶，S2中的运算符依次是｛*,-,+｝+在栈顶调用3次F0后，S1栈顶保存的值是A、-20B、15C、-15D、20正确答案B

29.若AVL树的深度是6空树的深度定义为-1,则该树的最少结点数是A、13B、17C、20D、33正确答案D

30.设一段文本中包含4个对象{a,b,c,d},其出现次数相应为（4,2,5,1）,则该段文本的哈夫曼编码比采用等长方式的编码节省了多少位数？、A4B、2C、5D、0正确答案B

31.一棵满二叉树中127个节点，其中叶子节点的个数是（）A、64B、不确定C、65D、63正确答案A

32.在下述结论中，正确的是

①只有2个结点的树的度为1;

②二叉树的度为2;

③二叉树的左右子树可任意交换；

④在最大堆（大顶堆）中，从根到任意其它结点的路径上的键值一定是按非递增有序排列的A、

②④B、

②③④C、

①④D、

①②③正确答案C

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

34.将元素序列｛18,23,11,20,2,7,27,33,42,15｝按顺序插入一个初始为空的、大小为11的散列表中散列函数为HKey=Key%11,采用线性探测法处理冲突问当第一次发现有冲突时，散列表的装填因子大约是多少？A、

0.27B、

0.73C、

0.64D、

0.45正确答案D

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

36.给定NXNXN的三维数组A,则在不改变数组的前提下，查找最小元素的时间复杂度是A、0N2B、ONlogNC、0N21ogND、0N3正确答案D

37.在下列查找的方法中，平均查找长度与结点个数无关的查找方法是A、利用哈希散列表B、二分法C、利用二叉搜索树D、顺序查找正确答案A

38.对于一个具有N个结点的单链表，在给定值为x的结点后插入一个新结点的时间复杂度为、0N/2AB、01C、0N2D、0N正确答案D

39.有组记录的排序码为｛46,79,56,38,40,84,采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为、｛40,38,46,56,79,84｝AB、｛38,79,56,46,40,84｝C、｛38,46,79,56,40,84｝D、｛38,46,56,79,40,84正确答案A

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

41.栈和队列的共同点是0A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点正确答案C

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

43.设数字｛4371,1323,6173,4199,4344,9679,1989在大小为10的散列表中根据散歹函数hX=X%10得到的下标对应为｛1,3,4,9,5,0,2｝o那么继续用散列函数“hX=X%表长”实施再散列并用线性探测法解决冲突后，它们的下标变为A、1,3,0,24,9,5,B、11,3,13,19,4,0,9C、1,12,9,13,20,19,11D、1,12,17,0,13,8,14正确答案C

44.若二叉搜索树是有N个结点的完全二叉树，则不正确的说法是、所有结点的平均查找效率是OlogNAB、最小值一定在叶结点上C、最大值一定在叶结点上D、中位值结点在根结点或根的左子树上正确答案C

45.下列程序段的时间复杂度为x=n；/*n1*/y=0;wh iI ex=y+1*y+1y=y+1;A、01B、0nC、0n%D、0n2正确答案C

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

47.下列复杂度表示法中，表示算法复杂度渐近的紧的界，即一种算法的复杂度与某个函数的阶相等A、大0表示法B、大®表示法、大标识符C QD、以上都不对正确答案B

48.关于存储结构的特点是借助指示元素存储地址的指针来表示数据元素之间的逻辑关系A、链式存储结构B、顺序存储结构C、索引存储结构D、散列存储结构正确答案A

49.设散列表的地址区间为[0,16],散列函数为HKey=Key%17采用线o性探测法处理冲突，并将关键字序列｛26,25,72,38,8,18,59｝依次存储到散列表中元素59存放在散列表中的地址是:A、9B、10C、11D、8正确答案C

50.利用大小为n的数组（下标从0到n-1）存储一个栈时，假定栈从数组另一头开始且top二二n表示栈空，则向这个栈插入一个元素时,修改top指针应当执行A、top不变B、top一C、top=0D、top++正确答案B

51.为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据该缓冲区的逻辑结构应该是？、图AB、树C、队列D、堆栈M1,M2和M3则与森林F对应的二叉树根结点的右子树上的结点个数是A、M3B、M2+M3C、M1+M2D、Ml正确答案B

4.已知有向图G=V,E,其中V={v1,v2,v3,v4,v5,v6},E二{v1,v2,v1,v4,v2,v6,v3,v1,v3,v4,v4,v5,v5,v2,A、vl,v3,v4,v5,v2,v6B、v3,vl,v4,v5,v2,v6C、vl,v3,v4,v5,v2,v6D、v3,v4,vl,v5,v2,v6v5,v6}o G的拓扑序列是:正确答案B

5.被计算机加工的数据元素不是孤立的，它们彼此之间一般存在某种关系，通常把数据元素之间的这种关系称为、集合AB、结构C、运算正确答案c

52.稀疏矩阵采用三元组存储的时候，一般需要一个行逻辑链接的顺序表，用以指出每一行的第一个非零元素在三元组中的位置用这个顺序表的主要目的是为了OA、加快算法运行效率B、更清晰表示每行元素所在位置C、节省存储空间D、更清晰表示每列元素所在位置正确答案A

53.若将n个顶点e条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是A、0nB、0n+eC、0n2D、0nX e正确答案B

54.若二叉搜索树是有N个结点的完全二叉树，则不正确的说法是A、平均查找效率是OlogNB、最大值一定在最后一层C、最小值一定在叶结点上D、中位值结点在根结点或根的左子树上正确答案B

55.对最小堆小顶堆{1,3,2,6,7,5,4,15,14,12,9,10,11,13,8进行三次删除最小元的操作后，结果序列为A、4,6,5,13,7,10,8,15,14,12,9,11B、4,5,6,7,8,9,10,11,12,13,14,15C、4,6,5,12,7,10,8,15,14,9,13,11D、4,5,6,12,7,10,8,15,14,13,9,11正确答案A

57.下面代码段的时间复杂度是i=1;while i=ni=i*3;A、0n2B、01D、0n正确答案C

58.对n个互不相同的符号进行哈夫曼编码若生成的哈夫曼树共有115个结点，则n的值是A、58B、56C、57D、60正确答案A

59.对N个记录进行快速排序，在最坏的情况下，其时间复杂度是、ONlogNAB、0N2C、0ND、0N21ogN正确答案B

60.对于一个有N个结点、K条边的森林，共有几棵树？A、不能确定B、N水C、N4TD、N/+1正确答案B

61.有两个垃圾邮件检测系统，分别用带有10000封正常邮件和2000封垃圾邮件的数据集进行测试系统A检测出了300封正常邮件和1600封垃圾邮件，系统B检测出了315封正常邮件和1800封垃圾邮件如果我们重点关注的是保证重要邮件的安全，下A、我们应重点关注准确率,系统A更好一些B、我们应重点关注召回率,系统B更好一些C、我们应重点关注准确率,系统B更好一些D、我们应重点关注召回率,系统A更好一些列哪句陈述是正确的？正确答案C

62.元素A,B,C,D依次入栈，出栈无限制，则以下（）是可能的出栈序列A、C,A,B,DB、B,A,D,CC、B,D,A,CD、A,D,B,C正确答案B

63.若一个栈的入栈序列为

1、

2、

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

64.在单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行A、s-next=p-next;p-next=s;B、s-next=p;p-next=s;C、p-next=s;s-next=p;D、s-next=p-next;p=s;正确答案A

65.招M个元素存入用长度为S的数组表示的散列表，则该表的装填因子为A、M/SB、S+MC、M-SD、MXS正确答案A

66.设主串T二abaabaabcabaabc,模式串S=abaabc,采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是、10AB、9C、12D、15正确答案A

67.桶排序算法的时间复杂度TM,N是多少？void BucketSort EIementTypeA[],i ntN{count□初始化；wh iI e读入1个学生成绩grade将该生插入count[grade]链表；for i=0;iM;i++{if count[i]输出整个count[i]链表;}}、0MAB、0NC、0MND、0M+N正确答案D

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

69.给定初始待排序列{15,9,7,8,20,-1,4}如果希尔排序第一0趟结束后得到序列为{15,-1,4,8,20,9,7},则该趟增量为A、4B、1C、3D、2正确答案A

70.在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左右指针都会停止移动，那么当所有元素都相等时，算法的时间复杂度是多少？A、0NB、OlogNC、ONlogND、0N2正确答案C

71.采用线性探测法解决冲突时所产生的一系列后继散列地址A、必须小于等于原散列地址B、可以大于或小于但不等于原散列地址C、对地址在何处没有限制D、必须大于等于原散列地址正确答案B

72.已知字符集{a,b,c,d,e,f）,若各字符出现的次数分别为{6,3,8,2,10,4）,则对应字符集中各字符的哈夫曼编码可能是A、0011,10,11,0010,01,000B、10,1011,11,0011,00,010C、00,100,110,000,0010,01D、00,1011,01,1010,11,100正确答案D

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

74.一棵高度为8的完全二叉树至少有（）叶子节点A、63B、128C、64D、127正确答案C

75.二叉树的形态由3个结点可以构造出种不同形态的二叉树、5AB、2C、4D、3正确答案A

76.堆的形状是一棵A、二叉搜索树B、非二叉树C、满二叉树D、完全二叉树正确答案D

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

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

79.对一棵二叉树的结点从1开始顺序编号要求每个结点的编号都大于其子树所有结点的编号，且左子树所有结点的编号都小于右子树所有结点的编号可采用实现编号A、先序遍历B、中序遍历C、层次遍历D、后序遍历正确答案DD、规则正确答案B

6.令P代表入栈，0代表出栈若利用堆栈将中缀表达式3*2+8/4转为后缀表达式，则相应的堆栈操作序列是A、POPOPOB、PPPOOOC、POPPOOD、PPOOPO正确答案C

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

8.设h为不带头结点的单向链表在h的头上插入一个新结点t的语句是A、h=t;t-next=h;B、t-next=h;h=t;

80.将元素序列｛18,23,4,26,31,33,17,39｝按顺序插入一个初始为空的、大小为13的散列表中散列函数为:H Key=Key%13,采用线性探测法处理冲突问当第一次发现有冲突时，散列表的装填因子大约是多少？、

0.31AB、

0.63C、

0.62D、

0.54正确答案A

81.若一棵AVL树有28个结点，则该树的最大深度为空树的深度定义为0oA、4B、5C、6D、7正确答案C

82.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是A、堆排序》快速排序〉归并排序B、堆排序〈快速排序归并排序C、堆排序〉归并排序〉快速排序D、堆排序归并排序〈快速排序正确答案B

83.下列各种数据结构中属于线性结构的有（）A、集合B、图C、树D、队列正确答案D

84.数组A[

0..6,

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

85.若一个栈的入栈序列为

1、

2、

3、…、N,其输出序列为p

1、p

2、p

3、…、pNo若p1二N,则pi为A、不确定B、n-iC、n-i+1D、i正确答案C

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

二、多选题共3题，每题1分，共3分

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

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

3.下列排序算法的常规实现中，除去对原始数据的保存以外，哪些算法的额外空间复杂度是

01、冒泡AB、选择C、归并D、堆排序E、归并正确答案ABD

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

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

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

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

4.算法分析的两个主要方面是时间复杂度和空间复杂度的分析A、正确B、错误正确答案A

5.将一棵完全二叉树存于数组中（根结点的下标为1）则下标为23和24的两个结点是兄弟A、正确B、错误正确答案B

6.若图G为连通图且不存在拓扑排序序列，则图G必有环A、正确B、错误正确答案A

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

8.二叉搜索树的查找和折半查找的时间复杂度相同、正确AB、错误正确答案B

9.对N个记录进行堆排序，需要的额外空间为0NA、正确B、错误正确答案B

10.对于一个有N个结点、K条边的森林，不能确定它共有几棵树A、正确B、错误正确答案B

11.任何最小堆的前序遍历结果是有序的从小到大A、正确B、错误正确答案B

12.在实现二项式队列时，每棵二项式树是用左孩子右兄弟的结构表示的B、错误正确答案A

13.链表-存储结构链表中逻辑上相邻的元素，其物理位置也一定相邻A、正确B、错误正确答案B

14.无向连通图边数一定大于顶点个数减1A、正确B、错误正确答案B

15.对N个记录进行归并排序，归并趟数的数量级是ONlogNA、正确B、错误正确答案B

16.通过对堆栈S操作PushS,1,Push⑸2,Pop S,PushS,3,Pop S,Pop So输出的序列为123oA、正确B、错误正确答案B

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

18.仅基于比较的算法能得到的最好的“最坏时间复杂度”是0NlogNo、正确AB、错误正确答案A

19.在具有N个结点的单链表中，访问结点和增加结点的时间复杂度分别对应为0⑴和0NA、正确B、错误正确答案B

20.KMP算法的最大特点是指示主串的指针不需要回溯、正确AB、错误正确答案A

21.斐波那契数列FN的定义为:FOR,F1=1,FN=FN-1+FN-2,N=2,3,…用递归函数计算FN的空间复杂度是0NB、错误正确答案A

22.若用链表来表示一个线性表，则表中元素的地址一定是连续的A、正确B、错误正确答案B

23.采用递归方式对顺序表进行快速排序，每次划分后，先处理较短的分区可以减少递归次数A、正确B、错误正确答案B

24.若一个栈的输入序列为1,2,3,…，N,输出序列的第一个元素是i,则第j个输出元素是j-i-1A、正确B、错误正确答案B

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

26.KMP算法的特点是在模式匹配时指示主串的指针不会变小回溯A、正确B、错误正确答案AC h=t;t-next=h-next;D t-next=h-next;h=t;正确答案B

9.有六个元素以

6、

5、

4、

3、

2、1的顺序进栈，问哪个不是合法的出栈序列、AB、C、D、正确答案:

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

11.AVL树是一种平衡的二叉搜索树，树中任一结点具有下列哪一特性A、左、右子树的高度均相同B、左、右子树高度差的绝对值不超过1C、左子树的高度均大于右子树的高度D、左子树的高度均小于右子树的高度正确答案B

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

13.在用邻接表表示有N个结点E条边的图时，深度优先遍历算法的时间复杂度为A、0N2B、0N2X EC、0ND、0N+E正确答案D

14.在作进栈运算时，应先判别栈是否

①；在作退栈运算时应先判别栈是否

②当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为

③①A.空B.满C.上溢D.下溢

②A.空B.满C.上溢D.下溢

③A.n-1B.n C.n+1D.n/2A、

①C

②D

③BB、

①B

②A

③BC、

①B

②B

③AD、正确答案B

15.循环队列的队满条件为A、sq.rear+1%maxsize==sq.frontB sq.front+1%maxsize==sq.rearC、sq.rear==sq.frontD、sq.rear+1%maxsize==sq.front+1%maxsize正确答案A

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

17.在N个结点的顺序表中，算法的时间复杂度为0

（1）的操作是、删除第i个结点（1W）AB、将N个结点从小到大排序C、访问第i个结点（IWiWN）和求第i个结点的直接前驱（2WiWN）D、在第i个结点后插入一个新结点（IWiWN）正确答案C

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

19.将两个结点数都为N且都从小到大有序的单向链表合并成一个从小到大有序的单向链表，那么可能的最少比较次数是A、NlogNB、1C、ND、2N正确答案C

20.散列冲突可以被描述为A、两个元素除了有不同键值，其它都相同B、两个有不同数据的元素具有相同的键值C、两个有不同键值的元素具有相同的散列地址D、两个有相同键值的元素具有不同的散列地址正确答案C

21.若结点p与q在二叉树T的中序遍历序列中相邻，且p在q之前，则下列p与q的关系中，不可能的是I.q是p的双亲I I.q是p的右孩子III.q是p的右兄弟IV.q是p的双亲的双亲A、仅IIIB、仅H、IVC、仅ID、仅n、in正确答案A

22.斐波那契数歹ij FN的定义为F0=0,F1=1,FN=FN-1+FN-2,N=2,3,…用递归函数计算FN的时间复杂度是A、OlogNB、NlogN2和NlogNC、0ND、0N!正确答案B

23.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序、发生改变AB、不发生改变C、不能确定D、以上都不对正确答案B

24.双链表-删除结点在双链表中，删除p所指结点的后继结点，其语句应该为OA s=p-next;s-next-prev=p;p-next=s-next;B、s=p-next;s-next-prev=p;p-next=s-〉next-next;C、s=p;s-next-prev=p;p-next=s-next;D s=p;s-next-prev=p-prev;p-next=s-next;正确答案A

25.在下述结论中，正确的是

①只有一个结点的二叉树的度为0；

②二叉树的度为2;

③二叉树的左右子树可任意交换；

④深度为K。