数据结构习题（附参考答案）

数据结构习题（附参考答案）

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

10011001、在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的（）A、度数B、出边数C、度数减1D、入边数正确答案B

2、在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素个数为（）A、neB、2eC、nD e正确答案D

3、数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）A、不好说B、相同C、高D、低正确答案C

4、元素大小为1个单元，容量为n个单元的非空顺序栈中，以地址高端为栈底，以top作为栈顶指针，则出栈处理后，top的值应修改为（）A、top=topB、top=top-1C、top=top+lD top=n-l正确答案c

5、在顺序表中，只要知道（）,就可在相同时间内求出任一结点的存储地址A、向量大小B、基地址和结点大小

47、用链表表示线性表的优点是（）oA、便于随机存取B、花费的存储空间比顺序表少C、数据元素的物理顺序与逻辑顺序相同D、便于插入与删除正确答案D

48、深度为6（根的层次为1）的二叉树至多有（）结点A、32B、63C、31D、64正确答案B

49、设有6个结点的无向图，该图至少应有（）条边才能确保是一个连通图A、5B、6C、7D、8正确答案A

50、若对n个元素进行直接插入排序，则进行任一趟排序的过程中，为寻找插入位置而需要的时间复杂度为（）oA、0

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

51、如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（）A、队列B、树C、栈D、图正确答案B

52、已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（）A、48B、0C、49D、1正确答案C

53、下列四种排序中（）的空间复杂度最大、希尔排序AB、冒泡排序C、快速排序D、堆正确答案C

54、在（）运算中，使用顺序表比链表好A、删除B、根据序号查找C、插入D、根据元素值查找正确答案B

55、在长度为32的有序表中进行二分查找时，所需进行的关键字比较次数最多为（）A、5B、6C、4D、7正确答案B

56、下列排序算法中，不稳定的是（）A、直接插入排序B、归并排序C、简单选择排序D、冒泡排序正确答案C

57、在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，指针域指向该结点的（）A、终端结点B、直接前趋C、开始结点D、直接后继正确答案D

58、设某哈夫曼树中有199个结点，则该哈夫曼树中有个叶子结点A、100B、99C、102D、101正确答案A

59、如下陈述中正确的是A、串是一种特殊的线性表B、串的长度必须大于0C、空串就是空白串D、串中元素只能是字母正确答案A

60、在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是A、01B、0nC、0nlognD、0n2正确答案B

61、在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为A、front=front-〉nextB、rear=front-nextC、front=rear-nextD、rear=rear-next正确答案A

62、在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为A、0n3B、0n+eC、0nD、0n2正确答案B

63、数组的逻辑结构不同于下列的逻辑结构A、队列B、线性表C、栈D、树正确答案D

64、下列程序段的渐进时间复杂度为for inti=l;i=n;i++for intj=l;j=m;j++A[i][j]=i*j;A、0m2B、0n2C0m*nD m+n正确答案C

65、设输入序列是

1、

2、

3、……、n,经过栈的作用后输出序列的第一个元素是n,则输出序列中第i个输出元素是oA、n-IB、不能确定C、n+l-ID、n-l-I正确答案C

66、下面选项中，不是图的存储方法A、邻接链表B、孩子兄弟链表C、逆邻接链表D、邻接矩阵正确答案B

67、两个字符串相等的条件是oA、两串的长度相等，并且两串包含的字符相同B、两串的长度相等C、两串的长度相等，并且对应位置上的字符相同D、两串包含的字符相同正确答案C

68、对于一个无向图，下面（）种说法是正确的A、每个顶点的入度等于出度B、每个顶点的度等于其入度与出度之和C、每个顶点的入度为0D、每个顶点的出度为0正确答案A

69、栈和队列都是（）oA、顺序存储的线性结构B、链式存储的线性结构C、限制存取位置的线性结构D、限制存取位置的非线性结构正确答案C

70、设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X,则入队列的操作序列为（）oA、rear-next=s；rear=s；B front-next=s；front=s；C、s-next=front；front=s；D s-next=rear；rear=s；正确答案A

71、已知指针p和q分别指向某单链表中第一个结点和最后一个结点假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（）A、p-next=s-next；s-next=q;B s-next=q；p-next=s-next；C、s-next=p；q-next=s-next；D、q-next=s-next；s-next=p；正确答案D

72、n个顶点的连通图至少中含有（）边A、nB、n-1C^n+1D、0正确答案B

73、用散列函数求元素在散列表中的存储位置时，可能会出现不同的关键字得到相同散列函数值的冲突现象可用于解决上述问题的是（）A、线性探测法B、平方取中法C、折叠法D、除留余数法正确答案A

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

75、对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为（）oA、n+1B、nC、n（n-l）/2D、n-1正确答案C

76、下列四种基本的逻辑结构中，结构结点间不存在任何逻辑联系的是（）A、树形结构B、图形结构C、集合D、线性结构正确答案C

77、在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）A、-1B、0C、2D、1正确答案C

78、若用一个有6个单元的数组来实现循环队列，rear和front的初值分别为0和3o则从队列中删除一个元素，再添加两个元素后，rear和front的值分别为（）A、5和1B、1和5C、4和2D、2和4正确答案D

79、假定一个顺序存储的循环队列的队头和队尾指针分别为f和r，则判断队空的条件为（）.A、f==0B、f==rC r+1-fD f+1-r正确答案B

80、链表不具有的特点是（）A、可随机访问任一元素B、所需空间与线性长度成正比C、不必事先估计存储空间D、插入、删除不需要移动元素正确答案A

81、3个结点可构成（）棵不同形态的二叉树A、5B、3C、2D、4正确答案A

82、栈是一种操作受限的线性结构，其操作的主要特征是（）A、先进先出B、后进先出C、出优于进D、进优于出正确答案B

83、在线性表的下列运算中，不改变数据元素之间结构关系的运算是（）A、删除B、排序C、定位D、插入正确答案C

84、设单链表中结点结构为（data,link）.已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*P之间插入结点*s,则应执行下列哪一个操作（）A、p-link=s-link;s-link=p;B、q-link=s;s-link=pC p-link=s;s-link=q;D、s-1ink=p-link;p-1ink=s;正确答案B

85、下列排序方法中，属于不稳定的排序方法是（）A、归并排序法B、希尔排序C、冒泡排序法D、直接插入排序法正确答案B

86、设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为CABD,则后序遍历该二叉树得到序列为（）oA、BADCB、BCDAC、CDABD、CBDA正确答案A

87、在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中这种方式主要适合于（）A、静态查找表或动态查找表B、静态查找表与动态查找表C、动态查找表D、静态查找表正确答案C

88、在长度为n的线性表中删除一个指针p所指结点的时间复杂度是A、01B、0n2C、0nD0log2n正确答案c

89、对于任何一棵二叉树T,如果其终端结点数为n0,度为2的结点为n

2.，则A、nO=n2+lB、n2=nO+1C、nO=2n2+lD、n2=2n0+l正确答案A

90、一棵完全二叉树上有1001个结点，其中叶子结点的个数是A、500B、505C、501D、254正确答案C

91、将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为oA、0m+nB、0mC、0nD、01正确答案B

92、深度为k的二叉树至多有A、2Xk-l个结点B、2Xk-1-1个结点C、2一个结点D、2--1个结点正确答案D

93、顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为oA、0nl/2B、0nC、0n2D0log2n正确答案B

94、从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需要比较个结点A、n+l/2B、n-l/2C、nD、n/2正确答案A

95、采用顺序搜索方法查找长度为n的顺序表示，搜索成功的平均搜索长度为oA、nB、n+l/2C、n/2D、n-l/2正确答案B

96、在对n个元素进行直接插入排序的过程中，共需要进行趟A、n-lB、2nC nDn+1正确答案A

97、排序算法中，不稳定的排序是A、冒泡排序B、直接插入排序C、堆排序D、选择排序正确答案C

98、在对n个元素进行冒泡排序的过程中，至少需要趟完成A、1B、n-1C、基地址D、结点大小正确答案B

6、一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程（）oA、较快B、相同C、较慢D、不定正确答案C

7、在计算机内实现递归算法时所需的辅助数据结构是（）A、树B、队列C、图D、栈正确答案D

8、关于二叉树性质的描述，正确的是（）A、二叉树至少含有一个根结点B、二叉树结点的个数可以为0C、二叉树若存在两个结点，则必有一个为根，另一个为左孩子D、二叉树若存在三个结点，则必有一个为根，另两个分别为左、右孩子正确答案B

9、树形结构是数据元素之间存在一种（）oA、多对一关系B、多对多关系C、一对多关系D、一对一关系正确答案C

10、采用顺序存储结构存储的线性表，其首地址为100,每个元素的长度为2,则第5个元素的地址为（）A、108B、110C、120D、100C、n/2D、n正确答案A

99、从一个长度为n的顺序表中删除第i个元素（IWiWn）时，需向前移动的元素的个数是（）oA、iB、n-i-1C、n-i+1D、n-i正确答案D

100、设循环队列的元素存放在一维数组Q[0--30]中，队列非空时，front指示队头元素的前一个位置，rear指示队尾元素如果队列中元素的个数为H,front的值为25,则rear应指向的元素是（）A、Q

[5]B、Q

[4]C、Q

[14]D、Q

[15]正确答案A正确答案A

11、权值为｛1,2,6,8｝的四个结点构成的哈夫曼树的带权路径长度是（）A、18B、28C、19D、29正确答案D

12、设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找,则在查找概率相等的情况下，分块查找成功时的平均查找长度为（）A、21B、23C、62D、41正确答案B

13、设链式栈中结点的结构为（data,link），且top是指向栈顶的指针若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行下列（）操作A、x=top;top=top-1ink;B、x=top-data;top=top-link;C、x=top-data;D top=top-link;x=top-data;正确答案B

14、线性表的顺序存储结构是一种（）的存储结构A、散列存取B、顺序存取C、随机存取D、索引存取正确答案C

15、已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为（）A、9B、8C、7D、10正确答案B

16、将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数为（）A、nB、n2C、2nD、2n-l正确答案A

17、关于存储相同数据元素的说法中正确的是（）A、顺序存储比链式存储多占空间B、顺序存储比链式存储少占空间C、顺序存储和链式存储都要求占用整块存储空间D、链式存储比顺序存储难于扩充空间正确答案B

18、在一个非空二叉树的中序遍历序列中，根结点的右边（）oA、只有右子树上的所有结点B、只有右子树上的部分结点C、只有左子树的上的部分结点D、只有左子树上的所有结点正确答案A

19、若最常用的操作是读取线性表中元素的值，则采用（）存储方式最节省时间A、带尾指针的单链表B、单链表C、带尾指针的单循环链表D、顺序表正确答案D

20、深度为5的二叉树至多有（）个结点A、31B、16C、10D、32正确答案A

21、G是一个非连通无向图，共有28条边，则该图至少有个顶点A、9B、8C、7D、6正确答案A

22、关于栈和队列的说法中正确的是A、栈和队列都不是线性结构B、栈是线性结构，队列不是线性结构C、栈和队列都是线性结构D、栈不是线性结构，队列是线性结构正确答案C

23、在一棵二叉树上第4层的结点数最多为oA、2B、4C、6D、8正确答案D

24、设有一个栈，元素的进栈次序为A,B,C,D,E,下列是不可能的出栈序列oA、A,B,C,D,EB、B,C,D,E,AC、E,A,B,C,DD、E,D,C,B,A正确答案C

25、在对n个元素进行直接插入排序的过程中，算法的空间复杂度为oA、01B、0n2C、0log2nD、0nlog2n正确答案A

26、设有序表中有1000个元素，则用二分查找查找元素X最多需要比较次A、25B、7C、1D、10正确答案D

27、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树A、空或只有一个结点B、高度等于其节点数C、任一结点无左孩子D、任一结点无右孩子正确答案B

28、从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（）A、线性结构和树型结构B、线性结构C、线性结构和图状结构D、树形结构正确答案A

29、具有n个顶点的无向图，若要连通全部顶点，至少需要（）、n（n-1）/2条边AB、n条边C、n（nT）条边D、（n-1）条边正确答案D

30、设一个顺序有序表中有14个元素，则采用二分法查找元素A

[4]的过程中比较元素的顺序为（）A、A[l],A

[2],A

[3],A

[4]B、A[l],A

[14],A

[7],A

[4]C、A

[7],A

[3],A

[5],A

[4]D、A

[7],A

[5],A

[3],A

[4]正确答案C

31、对一个满二叉树，m个树叶，k个分枝结点，n个结点，则（）A、n=m+lB m+l=2nC、m=k-lD、n=2k+l正确答案D

32、在下列排序方法中，平均时间性能为Onlogn且空间性能最好的是oA、堆排序B、归并排序C、快速排序D、基数排序正确答案A

33、对具有n个元素的有序表采用折半查找，则算法的时间复杂度为A、0n2B、0nC、01E、0log2n正确答案D

34、假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除预某个顶点vi相关的所有弧的时间复杂度是、0eAB、0n*eC、0nD、0n+e正确答案D

35、设某无向图有n个顶点，则该无向图的邻接表中有个表头结点A、nB、2nC、nn-lD、n/2正确答案A

36、有8个结点的无向连通图最少有条边A、5B、8C、6D、7正确答案D

37、设栈S和队列Q的初始状态为空，元素El、E

2、E

3、E

4、E5和E6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出列的顺序为E

2、E

4、E

3、E

6、E5和E1,则栈S的容量至少应该是（）A、4B、2C、3D、6正确答案C

38、长度为12的按关键字有序的查找表，采用顺序组织方式若采用折半查找方法，则在等概率情况下，查找失败时的ASL值是（）A、Dec-37B、37/13C、Dec-49D、49/13正确答案D

39、设单链表中指针p指向结点A,要删除A之后的结点（若存在），则修改指针的操作为（）A、p-next=p-next-nextB、p=p-nextC^p=p-next-nextD、p-next=p正确答案A

40、要解决散列引起的冲突问题，常采用的方法有（）A、二次探测法、平方取中法B、二次探测法、链地址法C、数字分析法、线性探测法D、数字分析法、平方取中法正确答案B

41、对于线性表（7,34,55,25,64,46,20,10）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为1的元素有（）个.A、2B、3C、4D、1正确答案C

42、一个向量第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的存储地址是（）A、108B、110C、100D、120正确答案A

43、一个队列的入队序列是1,2,3,4,则队列的输出序列是（）oA、4,3,2,1B、1,4,3,2C、1,2,3,4D、3,2,4,1正确答案C

44、引起循环队列队头位置发生变化的操作是（）A、入队B、取队头元素C、取队尾元素D、出队正确答案D

45、栈和队列共同具有的特点是（）A、只允许在端点进行操作运算B、都是先进后出C、都是先进先出D、既能先进先出，也能先进后出正确答案A

46、哈夫曼树中度为1的结点个数为（）A、不确定B、2C、0D、1正确答案C。