数据结构习题及答案

数据结构习题及答案

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

10011001、具有35个结点的完全二叉树的深度为（）A、6B、7C、8D、5正确答案A

2、在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行（）A、p-link=s-link;s一linkup;B、q-link=s;s—link=p;C、sf link=pf link;pf link=s;D pflinks;sf link=q;正确答案B

3、采用线性链表表示一个向量时，要求占用的存储空间地址（）oA、部分地址必须是连续的B、一定是不连续的C、必须是连续的D、可连续可不连续正确答案D

4、在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（）A、数据元素的值表示B、数据元素在表中的序号表示C、数据元素的相邻地址表示D、指向后继元素的指针表示正确答案D

5、在长度为n的顺序表中删除第i个元素（IWiWn）时，元素移动的次数为（）A、i+1B、n-i+1C、ID、n-i正确答案DC log2（n+1）D log2n正确答案B

47、在对n个元素进行冒泡排序的过程中，第一趟排序至多需要进行（）对相邻元素之间的交换A、nB、n/2C、n-1D n+1正确答案c

48、以下数据结构中，哪一个是线性结构（）oA、线索二叉树B、有向图C、串D、二叉树正确答案C

49、若进栈次序为a,b,c,且进栈和出栈可以穿插进行，则可能出现的含3个元素的出栈序列个数是（）A、3B、7C、5D、6正确答案C

50、设一组记录的关键字key值为｛62,50,14,28,19,35,47,56,83）,散列函数为H（key）=key mod13,则它的开散列表中散列地址为1的链中的结点个数是（）A、4B、1C、2D、3正确答案B

51、下列排序方法中，稳定的排序方法为（）A、堆排序B、直接插入排序C、希尔排序D、快速排序正确答案B

52、下面程序段的时间复杂度为for inti=0;im;i++forintj=0;jn;j++a[i][j]=i*j;A、0n2B、0m*nC、0m+nD、0m2正确答案B

53、为了有效地利用散列查找技术，主要解决的问题是

①找一个好的散列函数

②有效地解决冲突

③用整数表示关键值A、

①和

②B、

①②和

③C、

①和

③D、

②和

③正确答案A

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

55、已知栈的最大容量为4o若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行，则可能出现的出栈序列为A、1,4,6,5,2,3B、5,4,3,2,1,6C、3,2,5,4,1,6D、2,3,5,6,1,4正确答案

56、设n,m为一棵二叉树上的两个结点，在中序遍历序列中nC在m前的条件是oA、n在m右方B n是的祖先HIC、n是m的子孙D、n在m左方正确答案D

57、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行A、p-link=s;s-link=p;B、s-link=p-link;p-link=s;C、s-link=p-link;p=s;D s-1ink=p;p-1ink=s;正确答案B

58、设连通图G中的边集E={a,b,a,e,a,c,b,e,e,d,d,f,f,c},则从顶点a出发不能得到一种深度优先遍历的顶点序列为oA、abedfcB aedfcbC、acfebdD aebdfc正确答案c

59、二叉排序树可以得到一个从小到大的有序序列A、层次遍历B、中序遍历C、先序遍历D、后序遍历正确答案B

60、判定一个栈ST最多元素为m0为空的条件是A、ST-top=0B、ST-topOmOC、ST-top0D ST-top=mO正确答案A

61、在一个长度为n的顺序表中删除第i个元素0=i〈=n时，需向前移动个元素A、n-i+1B、n-i-1C、iD n-i正确答案D

62、二叉树的第k层的结点数最多为.A、27k-lC、2k-lC、2klD、2k+l正确答案A

63、下列排序算法中，在某些特殊情况可能只需一趟排序即可完成A、冒泡排序B、堆排序C、插入排序D、快速排序正确答案A

64、设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为oA、0log2nB、01C、0nD、0rT2正确答案c

65、在含有n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为oA、2eB n2_2eD、n2-eD e正确答案B

66、设有一个递归算法如下则计算fact n需要调用该函数的次数为int factint n{/*大于等于0*/ifn〈=0return1;oelse returnn*fact n-1;}A、n+2B n+1C、n-1D、n正确答案B

67、栈的数组表示中，top为栈顶指针，指向栈顶元素的下一个位置，栈空的条件是（）A、top=maxSizeB、top=-lC、top=0D top=maxSize正确答案c

68、栈可以在（）中应用A、递归调用B、子程序调用C、表达式求值D、A,B,C正确答案D

69、一个数组元素a[i]与（）的表示等价A、a+IB、*（a+i）C a+iD*a+I正确答案B

70、根据先序序列ABDC和中序序列DBAC确定对应的二叉树，该二叉树（）oA、是完全二叉树B、不是完全二叉树C、是满二叉树D、是完全二叉树且是满二叉树正确答案A

71、由m棵结点数为n的树组成的森林，将其转化为一棵二叉树，则该二叉树中根结点的右子树上具有的结点个数是（）A、mnC、mn-1C、mn-lD、nm-1正确答案D

72、设某数据结构的二元组形式表示为A=D,R,D={01,02,03,04,05,06,07,08,09},R={r},r={01,02,01,03,01,04,02,05,02,06,03,07,03,08,03,09},则数据结构A是A、线性结构B、树型结构C、物理结构D、图型结构正确答案B

73、如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为A、冒泡排序B、堆排序C、归并排序D、插入排序正确答案D

74、在索引查找中，若用于保存数据元素的主表的长度为n,它被均分为k个子表，每个子表的长度均为n/k,则索引查找的平均查找长度为A、k+n/k/2+lB、n+kD、k+n/k/2E、k+n/k正确答案A

75、一个栈的输入序列是12345,则下列序列中是栈的输出序列的是oA、1,4,2,5,3B、5,4,1,3,2C、3,1,2,4,5D、2,3,4,1,5正确答案D

76、在一个单链表中，若p所指结点是q所指结点的前驱结点，则删除结点q的正确操作是（）A、p=q-nextB、p-next=qC、p-next=q-next-nextD、p-next=q-next正确答案D

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

78、栈和队列的共同特点是（）A、没有共同点B、都是先进后出C、都是先进先出D、只允许在端点处插入和删除正确答案D

79、计算机算法必须具备输入、输出和（）等5个特性A、可行性、确定性和有穷性B、易读性、稳定性和安全性C、可行性、可移植性和可扩充性D、确定性、有穷性和稳定性正确答案A

80、数据结构只是研究数据的逻辑结构和物理结构，这种观点（）A、正确B、前半句对，后半句错C、前半句错，后半句对D、错误正确答案D

81、在有n个叶子结点的哈夫曼树中，其结点总数为（）oA、2n-lB2nC、2n+lD、不确定正确答案A

82、从逻辑上可以把数据结构分为（）.A、线性结构、非线性结构B、初等结构、构造型结构C、顺序结构、链式结构D、动态结构、静态结构正确答案A83for（i=0；im；i++）for（j=0；jt；j++）c[i][j]=0；fori=0；im；i++for j=0；jt；j++for k=0；kn；k++c=C Li][j]+a[i][k]*b上列程序的时间复杂度为A、0m+n+tB、0mX t+nC0mXnXtD、0m+n Xt正确答案C

84、下面关于线性表的叙述错误的是（）oA、线性表采用顺序存储必须占用一片连续的存储空间B、线性表采用链式存储便于插入和删除操作的实现C、线性表采用链式存储不必占用一片连续的存储空间D、线性表采用顺序存储便于插入和删除操作的实现正确答案D

85、数据的四种基本存储结构是指（）树型存储结构、图型存储结构链式存储结构、散列存储结构直接存储结构、倒排存储结构A、a,b,d,cB a,b,c,dA、顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构C d,c,b,aB、顺序存储结构、链式存储结构、C、顺序存储结构、索引存储结构、D、c,d,a,bD、顺序存储结构、索引存储结构、正确答案D正确答案C

86、设一个栈的输入序列是a,b,程c,d,则所得到的输出序列（输入过）中允许出栈）不可能出现的是（

87、栈的两种常用存储结构分别为（）A、顺序存储结构和散列存储结构B、链式存储结构和散列存储结构C、链式存储结构和索引存储结构D、顺序存储结构和链式存储结构正确答案D

88、栈上溢现象通常出现在（）A、链栈的出栈操作过程中B、链栈的入栈操作过程中C、顺序栈的出栈操作过程中D、顺序栈的入栈操作过程中正确答案D

89、假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[O],若BT[i]中的结点有左孩子，则左孩子存放在（）A、BT[i/2]B、BT[2*i-l]C、BT[2*i]D、BT[2*i+l]正确答案D

90、在平均情况下速度最快的排序方法为（）oA、归并排序B、快速排序C、堆排序D、简单选择排序正确答案B

91、由权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A、71B、53C、48D、24正确答案A

92、一组记录的排序码为（46,79,56,38,40,84）,则利用快速排序的方法,以第一个记录为基准得到的第一次划分结果为（）A、40,38,46,79,56,84B、40,38,46,84,56,79C、40,38,46,56,79,84D、38,40,46,56,79,84正确答案C

93、设单链表中结点结构为（data,link）.若想摘除结点*p的直接后继，则应执行下列哪一个操作（）A、p-link=p-link;B、p=p-link;p-link=p-1ink-link;C p-1ink=p-1ink-link;D p=p-link-link;正确答案c

94、设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）A、e,nB n,2eC、n,eD2n,e正确答案B

95、判定一个队列QU（最多元素为mO）为满队列的条件是（）A、QU-front==QU-rear QU-front==（QU-rear+l）%mOB、QU-front==QU-rear+lC QU-rear—QU-front—1==mOD、QU-rear—QU-front二二mO正确答案D

96、假设有向图含n个顶点及e条弧，则表示该图的邻接表中包含的弧结点个数为（）A、eB、2eC n•eD n正确答案A

6、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8,列下标j从1到10所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（）oA、80B、100C、240D、270正确答案c

7、设森林F中有三棵树，第

一、第二和第三棵树的结点个数分别为ml,m2和m3与森林F对应的二叉树根结点的右子树上的结点个数是（）A、ml+m2B、m2C、m2+m3D、m3正确答案C

8、利用二叉链表存储树，则根结点的右指针是（）A、非空B、空C、指向最右孩子D、指向最左孩子正确答案B

9、广度优先遍历类似于二叉树的（）oA、层次遍历B、先序遍历C、后序遍历D、中序遍历正确答案A

10、设有一个栈，按A、B、C、D的顺序进栈，则可能为出栈序列的是（）A、DCBAB、CDABC、DBACD、DCAB正确答案A

11、用链接方式存储的队列，在进行插入运算时（）

97、下面程序段的时间复杂度为s=0；fori=l；in；i++forj=l；ji；j++s+=i*j；A、01B、0n2C、0lognD、0n正确答案B

98、假定对元素序列7,3,5,9,1,12,8,15进行快速排序，则进行第一次划分后，得到的左区间中元素的个数为oA、3B、5C、2D、4正确答案A

99、若根据查找表23,44,36,48,52,73,64,58建立哈希表,采用h K=K%7计算哈希地址，则哈希地址等于3的元素个数A、1B、3C、2D、4正确答案C

100、对于长度为n的顺序表执行删除操作，则其结点的移动次数A、最少为0,最多为nB、最少为1,最多为n-1C、最少为1,最多为nD、最少为0,最多为nT正确答案DA、仅修改尾指针B、头、尾指针可能都要修改C、仅修改头指针D、头、尾指针都要修改正确答案B

12、在关键字序列12,23,34,45,56,67,78,89,91中二分查找关键字为

45、89和12的结点时，所需进行的比较次数分别为A、4,4,3B、4,3,3C、3,3,4D、3,4,4正确答案B

13、循环队列A[0…mT]存放其元素值，分别用front和rear表示队头和队尾，则当前队列的元素个数是A、rear-front+m%mB、rear-front+1C、rear-front-1D、rear-front正确答案A

14、含有10个结点的二叉树中，度为0的结点数为4,则度为2的结点数为A、6B、5C、4D、3正确答案D

15、对包含n个元素的散列表进行搜索，平均搜索长度为A、不直接依赖于nB、0log2nC、上述都不对D、0n正确答案A

16、对于一组记录的关键字值25,38,63,74,采用折半查找25时，次查找成功A、1B、2C、4D、3正确答案B

17、队和栈的主要区别是（）A、所包含的运算个数不同B、限定插入和删除的位置不同C、存储结构不同D、逻辑结构不同正确答案B

18、导致栈上溢的操作是（）A、栈空时执行的入栈B、栈空时执行的出栈C、栈满时执行的出栈D、栈满时执行的入栈正确答案D

19、数据的四种基本逻辑结构是指（）A、线性结构、链表、树、图形结构B、集合、线性结构、树、图形结构C、数组、链表、树、图形结构D、线性表、链表、栈队列、数组广义表正确答案B

20、队列操作的原则是（）oA、后进先出B、只能进行插入C、只能进行删除D、先进先出正确答案D

21、线性表采用链式存储时，结点的存储地址（）A、必须是不连续的B、连续与否均可C、必须是连续的D、和头结点的存储地址相连续正确答案B

22、在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（）A、top不变oB top=0C、top++D top一一正确答案D

23、设指针变量p指向单链表结点A,则删除结点A的后继结点B需要的操作为（）oA、p-next=p-next-nextB、p=p-nextC、p=p-next-nextD、p-next=p正确答案A

24、在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（）A、栈B、队列C、有序表D、线性表正确答案B

25、假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rearo若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为（）A、（rear-front-1）%nB、（rear-front）%nC、（front-rear+1）%nD、（rear-front+n）%n正确答案D

26、向一个栈顶指针为hs的链栈中插入一个s结点时，应执行（）oA、hs-next=s；B、s-next=hs；hs=s；C、s-next=hs；hs=hs-next；D、s-next=hs-next；hs-next=s；正确答案B

27、连通图G中有n个顶点，G的生成树是（）的连通子图A、包含G的所有顶点B、不必包含G的所有顶点C、包含G的所有边D、包含G的所有顶点和所有边正确答案A

28、对于一个有向图，若一个顶点的度为kl,出度为k2,则对应邻接表中该顶点单链表中的边结点数为（）A、kl+k2B、k2C、kl-k2D、kl正确答案B

29、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）oA、操作B、存储结构C、算法D、逻辑结构正确答案D

30、以下数据结构中哪一个是非线性结构？（）A、线性表B、队列C、栈D、二叉树正确答案D

31、从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（）个元素结点A、（n-1）/2B、（n+1）/2C、n/2D、n正确答案B

32、数据结构的定义为（D,S）,其中D是（）的集合A、算法B、数据元素C、数据操作D、逻辑结构正确答案B

33、设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）oA、第i行非0元素的个数之和B、第i列非0元素的个数之和C、第i行0元素的个数之和D、第i列0元素的个数之和正确答案B

34、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）A、冒泡排序B、插入排序C、希尔排序D、选择排序正确答案B

35、已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于（）A、

3.4B、

2.9C、1D、

5.5正确答案B

36、若根据查找表（23,44,36,48,52,73,64,58）建立哈希表,采用h（K）=K%13计算哈希地址，则元素64的哈希地址为（）A、12B、8C、4D、13正确答案A

37、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列进行同样的排序操作，直到子序列为空或只剩下一个元素为止这样的排序方法是A、直接选择排序B、直接插入排序C、快速排序D、冒泡排序正确答案C

38、对于含n个顶点和e条边的图，采用邻接矩阵表示的空间复杂度为A、0eB、0nC、0n+eD、0n2正确答案D

39、链式栈与顺序栈相比，一个比较明显的优点是oA、删除操作更加方便B、通常不会出现栈满的情况C、插入操作更加方便D、不会出现栈空的情况正确答案B

40、设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为oA、top=top-1;B、top=top-next;C、top-next=top;D、top=top+l;正确答案B

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

42、在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为（）A、eB、neC、2eD n正确答案c

43、设顺序循环队列Q[0MT]的头指针和尾指针分别为F和R,头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置,则该循环队列中的元素个数为（）A、R-FB、（R-F+M）%MC、（F-R+M）%MD、F-R正确答案B

44、假设在一棵二叉树中，双分支结点数为15,单分支结点数为30个，则叶子结点数为（）个A、16B、15C、17D、47正确答案A

45、若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（）A、前序遍历算法B、层次遍历算法C、中序遍历算法D、后序遍历算法正确答案C

46、设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）oA、log2n-lB、log2n+l。