数据结构练习题与答案

数据结构练习题与答案

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

10011001、顺序查找法适用于存储结构为（）的线性表A、压缩存储B、顺序存储或链式存储C、散列存储D、索引存储正确答案B

2、在索引查找中，若用于保存数据元素的主表的长度为144,它被均分为12子表，每个子表的长度均为12,则索引查找的平均查找长度为（）A、79B、24C、13D、12正确答案C

3、设哈夫曼树中的叶子结点总数为m,若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域A、2mB、2m-1C、4mD、2m+l正确答案A

4、设无向图G中有n个顶点，则该无向图的最小生成树上有（）条边A、2nB、n-1C、2n-lD n正确答案B

5、在完全二叉树中，若一个结点是叶结点，则它没有（）A、左孩子结点B、右孩子结点C、左孩子结点和右孩子结点D、左孩子结点，右孩子结点和兄弟结点正确答案C

47、若采用邻接矩阵存储一个n个顶点的无向图，则该邻接矩阵是一个oA、对角矩阵B、上三角矩阵C、稀疏矩阵D、对称矩阵正确答案D

48、设一棵完全二叉树中有65个结点，则该完全二叉树的深度为0A、6B、7C、5D、8正确答案B

49、若一个图的边集为集A,B,A,C,B,D,C,F,D,E,D,F},则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为A、A,B,C,D,E,FB、A,B,C,F,D,EC、A,B,D,C,E,FD、A,C,B,F,D,E正确答案D

50、从未排序序列中挑选元素，并将其依次插入已排序序列初始时为空的一端的方法，称为oA、选择排序B、希尔排序C、归并排序D、插入排序正确答案A

51、用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的A、队列B、树C、图D、栈正确答案D

52、无向图G=V,E,其中V={a,b,c,d,e,f},E={a,b,a,e,a,c,b,e,c,f,f,d,e,d},对该图进行深度优先遍历，得到的顶点序列正确的是oA、a,e,d,f,c,bB a,e,b,c,f,dC、a,b,e,c,d,fD a,c,f,e,b,d正确答案A

53、若一个图的边集为集1,2,1,4,2,5,3,1,3,5,4,3},则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为A、1,2,5,4,3B、1,2,3,4,5C、1,2,5,3,4D、1,4,3,2,5正确答案A

54、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中A、第i行非0的元素之和B、第i列非0的元素之和C、第i行非0的元素个数D、第i列非0的元素个数正确答案D

55、在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为oA、01B、0nC、0log2nD、0n2正确答案B

56、在待排关键字序列基本有序的前提下，效率最高的排序方法是A、直接插入排序B、归并排序C、快速排序D、直接选择排序正确答案A

57、对于具有n个顶点的连通无向图，其边的个数至少为（）A、n+1B、nlog2nC、n-1D、n正确答案c

58、在等概率情况下，顺序表的插入操作要移动（）结点A、全部B、一半C、三分之一D、四分之一正确答案B

59、若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是（）oA、栈B、队列C、二叉排序树D、线性表正确答案A

60、下列排序算法中，在最好情况下，时间复杂度为O（n）的算法是（）A、归并排序B、快速排序C、冒泡排序D、选择排序正确答案C

61、已知某二叉树的后序遍历序列是DABEC,中序遍历序列是DEBAC,则其先序遍历的结点访问序列是（）A、ACBEDB、DECABC、DEABCD、CEDBA正确答案D

62、栈和队列（）A、共同之处在于二者都是先进先出的特殊的线性表B、共同之处在于二者都是先进后出的特殊的线性表C、没有共同之处D、共同之处在于二者都只允许在顶端执行删除操作正确答案D

63、算法分析的两个主要方面是A、数据复杂性和程序复杂性B、可读性和文档性C、正确性和简明性D、空间复杂性和时间复杂性正确答案D

64、邻接矩阵为对称矩阵的图是（）A、带权有向图B、有向图C、无向图D、有向图或无向图正确答案D

65、循环队列是空队列的条件是（）A、（Q-rear+l）%maxsize==Q-frontB、Q-front==0C、Q-rear==OD Q-rear-Q-front正确答案D

66、若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（）A、3,2,4,1,6,5B、2,4,3,1,5,6C、2,3,5,1,6,4D、4,3,2,1,5,6正确答案C

67、对n个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多（）A、元素无序B、从大到小排列好的C、元素基本有序D、从小到大排列好的正确答案B

68、高度为h的完全二叉树中，结点数最多为A、27h-lB、2h-lC、2h+lD、2%正确答案B

69、对于一个线性表，若既要求能够进行较快地插入和删除，又要求存储结构能够得出数据元素之间的关系，则应该以A、散列方式存储B、顺序方式存储C、链式存储D、索引方式存储正确答案C

70、在一个具有n个结点的有序单链表插入一个新结点并仍然有序的时间复杂度是oA、0nlog2nB、0nC、0n2D、01正确答案B

71、下面程序段的时间复杂度为int funsignedint n{ifn==0||n==1return1;else returnn*f n-l;A、01B、0nC、0rT2D、0n!正确答案B

72、设某棵二叉树的高度为10,则该二叉树上叶子结点最多有A、1024B、256C、512D、20正确答案C

73、图的深度、广度优先遍历算法分别类似于二叉树的（）A、先序遍历和中序遍历B、先序遍历和层序遍历C、层序遍历和先序遍历D、后序遍历和中序遍历正确答案B

74、逻辑上通常可以将数据结构分为（）A、顺序结构和链式结构B、动态结构和静态结构C、初等结构和组合结构D、线性结构和非线性结构正确答案D

75、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个A、6B、5C、4D、7正确答案A

76、用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为（）A、n+1B、2nC、n-1D n正确答案A

77、设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）oA、0（n2）B、0（nlog2n）C、0

（1）D、0（n）正确答案C

78、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为oA、front+1=rearB rear==frontC、rear+1%n=frontD、rear%n==front正确答案B

79、可以唯一地转化成一棵一般树的二叉树的特点是A、根结点无左孩子B、根结点没有孩子C、根结点有两个孩子D、根结点无右孩子正确答案D

80、当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为A、n-1B、n+1C nDn_2正确答案A

81、设指针变量p指向单链表中结点A,若删除单链表中结点A,则需要修改指针的操作序列为oA、q=p-next；p-data=q-data；p-next=q-next；free q；B、q=p-next；q-data=p-data；p-next=q-next；free q；C q=p-next；p-next=q-next；free q；D、q=p-next；p-data=q-data；free q；正确答案A

82、将5个不同的数据进行排序，至多需要比较次A、10B、9C、8D、25正确答案A

83、对n个元素进行直接插入排序时间复杂度为oA、0log2nB、0n2C、0nD、01正确答案B

84、有个顶点e条边的无向图G,它的邻接表中的表结点总数是A、2nB、nC、2eD e正确答案c

85、根据数据元素的关键字直接计算出该元素存储地址的存储方法是A、顺序存储方法B、链式存储方法C、散列存储方法D、索引存储方法正确答案C

86、设数组dataDn］作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出对操作后其头指针front值为A、front=front-1%mB front=front+1%m-1C front=front+1D、front=front+1%m正确答案D

87、设以数组A［m］存放循环队列的元素，其头尾指针分别为front和rear,则当前队列中的元素个数为A、rear-front+m%mB、rear-front+1C、front-rear+m%mD、rear-front%m正确答案A

88、树的先根序列等同于与该树对应的二叉树的A、后序序列B、先序序列C、中序序列D、层序序列正确答案B

89、除根结点外，树上每个结点（）A、可有任意多个孩子、一个双亲B、可有一个孩子、任意多个双亲C、可有任意多个孩子、任意多个双亲D、只有一个孩子、一个双亲正确答案A

90、数据结构中所定义的数据元素，是用于表示数据的（）A、最小单位B、不可分割的单位C、基本单位D、最大单位正确答案C

91、在一个长度为n的顺序表中，向第i个元素（IWiWn+l）位置插入一个新元素时需要从后向前移动（）个元素A、iB、n-i+1C n-iD、n-i-1正确答案B

92、数据的基本单位是（）A、数据类型B、数据项C、数据元素D、数据变量正确答案C

93、某二叉树的前序遍历序列为ABDGCEFH,中序遍历序列为DGBAECHF,则后序遍历序列为（）A、BDGCEFHAB、GDBECFHAC、BDGAECHFD、GDBEHFCA正确答案D

94、除第一层外，满二叉树中每一层结点个数是上一层结点个数的A、1/2倍B、2倍C、1倍D、3倍正确答案B、如果F是由有序树T转换而来的二叉树，那么T中结点的前序就是F中95结点的oA、前序B、层次序C、后序D、中序正确答案A

96、若已知一个栈的入栈序列是1,2,3,4……n,其输出序列为pl,p2,p3,....pn,若pl=二n,则pi为oA、n-i+1B、不确定C、iD n==i正确答案A

97、在一个单链表中，若p所指结点不是最后结点，则删除p所指结点的后继结点的正确操作是A、p-next=p-next-nextB、p=p-nextC、p-next=pD、p-next=p-next正确答案A

98、求单链表中当前结点的后继和前驱的时间复杂度分别是A、01和01B、0n和0⑴C、0n和0nD、01和0n正确答案D

6、设数据结构A二D,R,其中D={1,2,3,4},R={r},r={L2,2,3,3,4,4,1},则数据结构A是oA、线性结构B、树型结构C、图型结构D、集合正确答案C

7、下列排序算法中，第一趟排序结束后其最大或最小元素一定在其最终位置上的算法是A、冒泡排序B、直接插入排序C、快速排序D、归并排序正确答案A

8、假设以数组A[m]存放循环队列的元素已知队列的长度为length,指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为A、rear-1ength+m+1%mB、rear-1ength+m%mC rear-1ength+m-1%mD、rear-length%m正确答案B

9、在下面的程序段中，对x的赋值语句的频度为fori=1;n=i;i++oforj=l;n=j;j++x=x+l;A、0log2nB、

02、C、0rT2D、0n正确答案C

10、具有4个顶点的无向完全图有条边A、12B、20C、6D、

1699、为使平均查找长度达到最小，当由关键字集合{05,11,21,25,37,40,41,62,84）构建二叉排序树时,第一个插入的关键字应为（）A、41B、37C、62D、5正确答案B

100、若要在单链表中的结点*p之后插入一个结点*s,则应执行的语句是（）typedef struct node{char data

[8];structnode*next;}LinkStrNode;A、s-next=p;p-next=s-next;B s-next=p-next;p-next=s;C、p-next=s-next;s-next=p;D p-next=s;s-next=p-next;正确答案B正确答案C

11、下面关于生成树的描述中，不正确的是（）A、生成树是树的一种表现形式B、生成树一定是连通的C、生成树一定不含有环D、若生成树顶点个数为n,则其边数一定为n-1正确答案A

12、树中所有结点的度之和等于所有结点数加（）A、2B、-1C、0D、1正确答案B

13、高度为5的完全二叉树中含有的结点数至少为（）A、32B、17C、16D、31正确答案C

14、对关键字序列（6,1,4,3,7,2,8,5）进行快速排序时，以第1个A、8,7,6,5,4,3,2,1B、5,1,4,3,2,6,7,8C、5,1,4,3,2,6,8,7D、5,1,4,3,6,2,8,7正确答案C元素为基准的一次划分的结果为（）

15、在下列对顺序表进行的操作中，算法时间复杂度为0

（1）的是（）A、访问第i个元素的前驱（li=n）B、删除第i个元素（1〈=i=n）C、在第i个元素之后插入一个新元素（l〈=i〈=n）D、对顺序表中元素进行排序正确答案A

16、已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为dal,则第I个结点的地址为（）oA、dal-I*mB、dal+I-l*mC dal+I*mD dal+1+1正确答案B

17、图的邻接矩阵表示法适用于表示A、稀疏图B、稠密图C、有向图D、无向图正确答案B

18、下面程序的时间复杂为for i=l,s=0；i=n；i++{t=l；forj=l；j=i；j++t=t*j；s=s+t；}A、0n4B、0nC、0n2D、0n3正确答案C

19、数据结构中，与所使用的计算机无关的是数据的结构；A、物理B、物理和存储C、逻辑D、存储正确答案C

20、已知二叉树的中序序列和后序序列均为ABCDEF,则该二叉树的先序序列为A、FEDCBAB、ABCDEFC、FDECBAD、FBDCEA正确答案A

21、散列查找是由键值确定散列表中的位置，进行存储或查找A、相反数B、散列函数值C、本身D、平方正确答案BA、12,27,45,41]55[34,63,

7222、执行一趟快速排序能够得到的序列是（）oB、[45,34,12,41]55[72,63,27]C、[41,12,34,45,27]55[72,63]D、[63,12,34,45,27]55[41,72]正确答案C

23、设有n个结点的二叉树上只有度为0和度为2的结点，则此二叉树中叶子结点数（）A、（n-l）/2B、（n+1）/2C、不能确定D、n/2正确答案B

24、设用链表作为栈的存储结构则退栈操作（）oA、必须判别栈是否为满B、必须判别栈是否为空C、判别栈元素的类型D、对栈不作任何判别正确答案B

25、散列查找中散列函数的值（）散列地址的范围A、无关B、小于C、大于D、在正确答案D

26、设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是（）s-next=p-next;p-next=s;t=p-data;p-data=s-data;s-data=t;A、在p所指结点的元素之后插入元素B、在p所指结点的元素之前插入元素C、结点*p与结点*s的数据域互换D、在结点*p之前插入结点*s正确答案D

27、for i=0；im；i++for j=0；jn；j++A[i][j]=i*j；上面算法的时间复杂度为A、0m2B、0n2C、OmXnD、0m+n正确答案C

28、数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为oA、顺序存储结构B、逻辑结构C、链式存储结构D、存储结构正确答案C

29、设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为oA、i/2B、2i+lC、2i-lD、2i正确答案D

30、对于哈希函数Hkey=key%13,被称为同义词的关键字是A、35和41B、23和39C、25和51D、15和44正确答案C

31、计算机识别、存储和加工处理的对象被统称为A、数据类型B、数据结构C、数据D、数据元素正确答案C

32、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为oA、rear+1%n==frontB rear%n==frontC、rear%n-1==frontD front+1%n==rear正确答案A

33、若一个图的边集为集1,2,1,4,2,5,3,1,3,5,4,3},则从顶点1开始对该图进行广度优先搜索，得到的顶点序列可能为A、1,4,2,5,3B、1,2,3,4,5C、1,2,4,3,5D、1,2,4,5,3正确答案D

34、在排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列初始时为空的一端的方法，称为A、归并排序B、选择排序C、希尔排序D、插入排序正确答案B

35、设森林F对应的二叉树为B,它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵子树的结点个数是oA、m-nB m-n-1C、n+1D、条件不足，无法确定正确答案A

36、对关键码序列28,16,32,12,60,2,5,72快速排序，从小到大一次划分结果为A、2,5,12,162860,32,72B、5,16,2,122860,32,72C、5,16,2,122832,60,72D、（2,16,12,5）28（60,32,72）正确答案B

37、若线性表最常用的操作是存取第i个元素及其前趋的值，那么最节省操作时间的存储方式是（）A、单循环链表B、顺序表C、双链表D、单链表正确答案B

38、顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为（）oA、s.top=s.top+1；s.elem[top+1]=e；B、s.top=s.top+1；s.elem[top]=e；C、s.elem[top++]=e；s.top;s.top+1；D、s.elem[top]=e；s.top=s.top+1；正确答案B

39、对于二叉树来说，第I层上至多有（）个节点A、24B、2Xi-1）C、2ilD、27i-l）-l正确答案B

40、下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是（）A、二分查找B、顺序查找C、散列查找D、分块查找正确答案C

41、一棵含18个结点的二叉树的高度至少为（）A、6B、3C、5D、4正确答案C

42、在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为A、0nB、0n2C、0n/2D、01正确答案A

43、以下与数据的存储结构无关的术语是oA、链表B、循环队列C、哈希表D、栈正确答案D

44、具有n个结点的二叉树，拥有指向孩子结点的分支数目是A、2nB、n-1C、n+1D、n正确答案B

45、一个栈的输入序列为1,2,3,n,设若输出序列的第1个元素为n,输出第i IWiWn个元素是A、n-iB、n-i+1C、iD、不确定正确答案B

46、排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列初始时为空的一端的方法，称为A、希尔排序B、归并排序C、插入排序D、选择排序正确答案D。