全国计算机二级C语言 # 数据结构与算法(1-147)
1. 堆排序最坏情况下的时间复杂度为答案：A
A）
B）
C）
D）
本题答案为:A
题目解析:堆排序法，最坏情况需要O(nlog2n)次比较，堆排序法的时间复杂度最小。所以本题选A。
2. 在线性表的链式存储结构中，其存储空间一般是不连续的，并且答案：C
A）前件结点的存储序号大于后件结点的存储序号
B）前件结点的存储序号小于后件结点的存储序号
C）前件结点的存储序号可以小于也可以大于后件结点的存储序号
D）以上答案均不正确
本题答案为:C
题目解析:链式存储结构使得节点在内存中不受位置的限制，结点存储号可以是任意的，并且能够保证逻辑上的线性关系。所以本题选C。
3. 设数据元素的集合D={ 1,2,3,4,5 }，则满足下列关系R的数据结构中为线性结构的是答案：B
A）R={ (1, 2), (2, 4), (4, 5), (2, 3) }
B）R={ (1, 3), (4, 1), (3, 2), (5, 4) }
C）R={ (1, 2), (3, 2), (5, 1), (4, 5) }
D）R={ (1, 3), (2, 4), (3, 5), (1, 2) }
本题答案为:B
题目解析:A选项2的后面有4、3两个数值， C选项2的前面有1、3两个数值，带有不确定性， D选项1的后面有3、2两个数值。所以本题选B
4. 某二叉树中有15个度为1的结点，16个度为2的结点，则该二叉树中总的结点数为答案：C
A）46
B）49
C）48
D）32
本题答案为:C
题目解析:二叉树有一个性质是：对任何二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1，所以度为0的一共有17个，总的结点数即是17+15+16=48个。所以本题选C
5. 下列叙述中正确的是答案：C
A）所有结点的指针域都为非空的链表一定是非线性结构
B）循环链表是循环队列的链式存储结构
C）线性结构的存储结点也可以有多个指针
D）每一个结点有两个指针域的链表一定是非线性结构
本题答案为:C
题目解析:当结点中两个指针分别指向前驱结点和后继结点是线性结构，当指向两个不同的前驱或后继结点时为非线性结构，指针域为非空的链表也可以是线性结构，链式存储方式既可用于表示线性结构，也可用于表示非线性结构。故A、B、D选项不完全正确。线性结构的存储结点可以由多个指针只有保证有且只有指向一个前驱结点和一个后继结点就是线性结构。所以本题选C。
6. 在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数答案：A
A）相同，元素的存储顺序与逻辑顺序一致
B）不同，但元素的存储顺序与逻辑顺序一致
C）相同，但其元素的存储顺序可以与逻辑顺序不一致
D）不同，且其元素的存储顺序可以与逻辑顺序不一致
本题答案为:A
题目解析:线性表的顺序存储结构的两个特点（1）线性表中所有元素所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。另在线性表中数据元素所占的字节数都是一致的。所以本题选A。
7. 设循环队列为Q(1: m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=30，rear=10。现要在该循环队列中作顺序查找，最坏情况下需要比较的次数为答案：C
A）19
B）20
C）m-20
D）m-19
本题答案为:C
题目解析:二分法查找只适用于顺序存储的有序表，对于长度为n的有序线性表，最坏情况只需比较log2n次，而顺序查找需要比较n次。已知循环队列为Q(1:m)，其初始状态为front=rear=m，而节点个数为m-(front-rear),且顺序查找的比较次数与实际节点个数一致。所以本题选C
8. 某二叉树中共有935个结点，其中叶子结点有435个，则该二叉树中度为2的结点个数为答案：B
A）64
B）434
C）66
D）436
本题答案为:B
题目解析:在二叉树中，度为0的结点个数总比度为2的结点个数多一个。所以本题选B。
9. 非空循环链表所表示的数据结构答案：D
A）没有根结点也没有叶子结点
B）没有根结点但有叶子结点
C）有根结点但没有叶子结点
D）有根结点也有叶子结点
本题答案为:D
题目解析:循环链表的第一个结点就是根结点，最后一个结点就是叶子结点。所以本题选D。
10. 某棵树只有度为3的结点和叶子结点，其中度为3的结点有8个，则该树中的叶子结点数为答案：A
A）17
B）15
C）16
D）不存在这样的树
本题答案为:A
题目解析:度为3的结点都有3个子结点，所以除根结点外，共有子结点3*8=24个，再加上1个根结点，该树共有25个结点，其中度为3的结点有8个，所以度为0的结点有17个。所以本题选A。3✖8-8+1=17
11. 某循环队列的存储空间为Q(1:m)，初始状态为front=rear=m。现经过一系列的入队操作和退队操作后，front=m，rear=m-1，则该循环队列中的元素个数为答案：C
A）1
B）0
C）m-1
D）m
本题答案为:C
题目解析:由于存储空间可以存储m个结点，而头指针指向m，所以第一个结点就在第1个位置上，而最后一个结点在m-1 的位置上，所以该循环队列共有m-1个结点。所以本题选C。
12. 在排序过程中，每一次数据元素的移动会产生新的逆序的排序方法是答案：C
A）简单插入排序
B）冒泡排序
C）快速排序
D）以上答案均不正确
本题答案为:C
题目解析:冒泡排序每次只交换两个相邻的数据；快速排序是选出一个结点，然后将大于该结点的数据移到后面，将小于该结点的数据移到前面，所以会产生一个新的逆序。所以本题选C。
13. 某循环队列的存储空间为Q(1:m)，初始状态为front=rear=m。现经过一系列的入队操作和退队操作后，front=m-1，rear=m，则该循环队列中的元素个数为答案：B
A）m-1
B）1
C）0
D）m
本题答案为:B
题目解析:头指针指向m-1，所以第一个结点m的位置上，而根据题意可知，最后一个结点也在第m个位置上，这说明该循环队列，只有一个结点。所以本题选B。
14. 某棵树中共有25个结点，且只有度为3的结点和叶子结点，其中叶子结点有7个，则该树中度为3的结点数为答案：B
A）6
B）不存在这样的树
C）7
D）8
本题答案为:B
题目解析:如果叶子结点有7个，那么度为3的结点就应该有25-7=18个，但如果度为3的结点有18个，那么整棵树的结点个数应该是18*3+1=55个，与题目相矛盾。所以本题选B。
15. 在最坏情况下，二分查找法的时间复杂度为答案：D
A）
B）
C）
D）log2 N
本题答案为:D
题目解析:最坏情况下，二分法查找的时间复杂度是log2n。所以本题选D。
16. 下列序列中不满足堆条件的是答案：A
A）（98，95，93，96，89，85，76，64，55，49）
B）（98，95，93，94，89，85，76，64，55，49）
C）（98，95，93，94，89，90，76，64，55，49）
D）（98，95，93，94，89，90，76，80，55，49）
本题答案为:A
题目解析:若有n个元素的序列，将元素按顺序组成一棵完全二叉树，当且仅当满足下列条件时称为堆：大根堆，所有结点的值大于或等于其左右子结点的值；小根堆，所有结点的值小于或等于其左右子结点的值。B、C、D选项属于大根堆。A选项由于98>95，判断属于大根堆，但95<96，不满足条件，不是堆。所以本题选A。
17. 下列叙述中正确的是答案：D
A）算法的有穷性是指算法的规模不能太大
B）算法的复杂度用于衡量算法的控制结构
C）算法的效率与数据的存储结构无关
D）程序可以作为算法的一种表达方式
本题答案为:D
题目解析:算法可以用程序来表示；算法的有穷性是指算法必须在有限的时间内结束；算法的复杂度用来衡量算法的好坏；算法的效率与数据的存储结构和逻辑结构都有关。所以本题选D。
18. 某棵树的度为4，且度为4、3、2、1的结点个数分别为1、2、3、4，则该树中的叶子结点数为答案：B
A）10
B）11
C）9
D）8
本题答案为:B
题目解析:根据题意可知，该数中结点个数为4*1+3*2+2*3+1*4+1=21个，所以度为0的结点个数为21-1-2-3-4=11个。所以本题选B。(1+2+3+4+1=11)
19. 设二叉树中共有15个结点，其中的结点值互不相同。如果该二叉树的前序序列与中序序列相同，则该二叉树的深度为答案：B
A）不存在这样的二叉树
B）15
C）4
D）6
本题答案为:B
题目解析:如果该二叉树前序序列与中序序列相同，说明该二叉树没有左子结点，只有右子结点，也就是15个结点结成一串，故该树共分15层，深度为15。所以本题选B。
20. 设循环队列的存储空间为Q(1:50)，初始状态为front=rear=50。现经过一系列入队与退队操作后，front=rear=1，此后又正常地插入了两个元素。最后该队列中的元素个数为答案：D
A）3
B）52
C）1
D）2
本题答案为:D
题目解析:当front=rear=1时，队列为空或满，而题目中说，在此情况下，又正常插入了两个元素，可分析出当前是空的状态，而不是满的状态。在空的状态下，又插入两个元素，所以最后该队列中元素个数为2。所以本题选D。
21. 设数据元素集合为{A，B，C，D，E，F}，下列关系为线性结构的是答案：A
A）R={ (D,E),(E,A),(B,C),(A,B),(C,F) }
B）R={ (A,B),(C,D),(B,A),(E,F),(F,A) }
C）R={ (D,F),(E,C),(B,C),(A,B),(C,F) }
D）R={ (D,E),(E,A),(B,C),(F,B),(C,F) }
本题答案为:A
题目解析:线性结构要求，只有一个根结点和一个叶子结点，除根结点和叶子结点外的其他结点，有且只有一个前件，有且只有一个后件，对各个选项分析可以得出A选项符合要求。所以本题选A。
22. 下列处理中与队列有关的是答案：A
A）操作系统中的作业调度
B）执行程序中的过程调用
C）执行程序中的循环控制
D）以上答案均不正确
本题答案为:A
题目解析:在计算机系统中，如果一次只能执行一个程序，则在多个用户程序需要执行时，这些用户程序必须按照到来的顺序进行排队等待。即操作系统中的作业调度使用的是队列的思想。所以本题选A。
23. 下列数据结构中为非线性结构的是答案：A
A）二叉链表
B）循环链表
C）双向链表
D）循环队列
本题答案为:A
题目解析: 线性结构要求只有一个根结点，只有一个叶子结点，除根结点和叶子结点外，每个结点只有一个前件也只有一个后件，而二叉树是要求某个结点要有两个后件，所以二叉树为非线性结构。所以本题选A。
24. 设二叉树中共有31个结点，其中的结点值互不相同。如果该二叉树的后序序列与中序序列相同，则该二叉树的深度为答案：D
A）5
B）16
C）17
D）31
本题答案为:D
题目解析:根据题意分析，此二叉树没有左子结点，所以除了一个根结点外，都是右子结点，所以该二叉树深度为31。所以本题选D。
25. 下列叙述中错误的是答案：A
A）数据结构中的数据元素不能是另一数据结构
B）空数据结构可以是线性结构也可以是非线性结构
C）数据结构中的数据元素可以是另一数据结构
D）非空数据结构可以没有根结点
本题答案为:A
题目解析:数据结构中的数据元素可以是另外一种数据结构。所以本题选A
26. 为了降低算法的空间复杂度，要求算法尽量采用原地工作(in place)。所谓原地工作是指答案：D
A）执行算法时不使用额外空间
B）执行算法时不使用任何存储空间
C）执行算法时所使用的额外空间随算法所处理的数据空间大小的变化而变化
D）执行算法时所使用的额外空间固定（即不随算法所处理的数据空间大小的变化而变化）
本题答案为:D
题目解析:识记，原地工作原理是执行算法时使用固定的额外空间，降低了算法的空间复杂度。所以本题选D。
27. 设栈的存储空间为S(1:m)，初始状态为top=m+1。经过一系列入栈与退栈操作后，top=1。现又要将一个元素进栈，栈顶指针top值变为答案：B
A）2
B）发生栈满的错误
C）m
D）0
本题答案为:B
题目解析:初始状态为top=m+1，说明栈底是m，栈顶是1，当top=1时，指针已经指向栈顶，栈已经满了，再添加就会溢出，也就是发生栈满错误。所以本题选B。
28. 设某二叉树的后序序列与中序序列均为ABCDEFGH，则该二叉树的前序序列为答案：D
A）EFGHABCD
B）DCBAHGFE
C）ABCDEFGH
D）HGFEDCBA
本题答案为:D
题目解析:后序遍历与中序遍历相同，说明该二叉树各结点都是只有左子结点，并且H是根结点，所以前序遍历的结果与后序遍历的结果正好相反。所以本题选D。
29. 设栈的存储空间为S(1:m)，初始状态为top=m+1。经过一系列入栈与退栈操作后，top=m。现又在栈中退出一个元素后，栈顶指针top值为答案：B
A）m-1
B）m+1
C）0
D）产生栈空错误
本题答案为:B
题目解析:根据题意，我们可以看出，在该栈中，初始状态是空栈，经过若干次操作后，指针指向m，意味着栈中还有一个元素，如果此时退出一个元素，那么再次成为空栈，所以top=m+1。所以本题选B。
30. 下列叙述中正确的是答案：A
A）数据结构中的数据元素可以是另一种数据结构
B）数据结构中的数据元素只能是另一种非线性结构
C）数据结构中的数据元素只能是另一种线性结构
D）以上答案均不正确
本题答案为:A
题目解析:数据结构中的数据元素可以是另外一种数据结构。所以本题选A。
31. 下列叙述中正确的是答案：A
A）二分查找法只适用于顺序存储的有序线性表
B）二分查找法适用于有序双向链表
C）二分查找法适用于任何存储结构的有序线性表
D）二分查找法适用于有序循环链表
本题答案为:A
题目解析:二分法查找也称拆半查找，能使用二分法查找的线性表必须满足两个条件：顺序存储结构以及线性表有序。循环链表和双向链表都不是顺序存储结构。所以本题选A。
32. 设某二叉树的前序序列与中序序列均为ABCDEFGH，则该二叉树的后序序列为答案：C
A）DCBAHGFE
B）EFGHABCD
C）HGFEDCBA
D）ABCDEFGH
本题答案为:C
题目解析:当二叉树的前序遍历和中序遍历结果相同时，说明这是一棵只有右子结点的二叉树，所以其后序结果与前序遍历的结果正好相反。所以本题选C。
33. 设循环队列的存储空间为Q(1:m)，初始状态为空。现经过一系列正常的入队与退队操作后，front=m，rear=m-1，此后从该循环队列中删除一个元素，则队列中的元素个数为答案：B
A）1
B）m-2
C）0
D）m-1
本题答案为:B
题目解析:头指针指向第一个元素的前一个位置。所以头指针指向m，尾指针指向m-1，则队列中有m-1个元素，此后又删除一个元素，所以最后队列中元素个数为m-2。所以本题选B。
34. 某二叉树共有730个结点，其中度为1的结点有30个，则叶子结点个数为答案：C
A）350
B）1
C）不存在这样的二叉树
D）351
本题答案为:C
题目解析:根据题意可知，该二叉树中度为2和度为0的结点共有730-30=700个，而根据二叉树的性质我们知道，二叉树中，度为0的结点个数总比度为2的结点个数多一个，也就是说度为0的结点个数和度为2的结点个数之和应为奇数，不可能是700个，出现了自相矛盾的情况。所以本题选C。
35. 能从任意一个结点开始没有重复地扫描到所有结点的数据结构是答案：B
A）双向链表
B）循环链表
C）二叉链表
D）有序链表
本题答案为:B
题目解析:循环列表可以实现不重复地扫描到所有结点。所以本题选B。
36. 若某二叉树中的所有结点值均大于其左子树上的所有结点值，且小于右子树上的所有结点值，则该二叉树遍历序列中有序的是答案：B
A）前序序列
B）中序序列
C）后序序列
D）以上答案均不正确
本题答案为:B
题目解析:根据题意分析可知，该二叉树中，根结点大于左子结点，而小于右子结点，所以要想有序遍历，只能是从小到大的按照左根右的顺序进行遍历，也就是中序遍历可以实现有序遍历。所以本题选B。
37. 设循环队列的存储空间为Q(1:m)，初始状态为空。现经过一系列正常的入队与退队操作后，front=m-1，rear=m，此后再向该循环队列中插入一个元素，则队列中的元素个数为答案：B
A）m-1
B）2
C）1
D）m
本题答案为:B
题目解析:当头指针指向m-1，尾指针指向m时，循环队列中有1个元素，此后又插入一个元素，则循环队列中共有2个元素。所以本题选B。
38. 某二叉树共有530个结点，其中度为2的结点有250个，则度为1的结点数为答案：C
A）251
B）30
C）29
D）249
本题答案为:C
题目解析:度为2的结点有250个，那么根据二叉树的性质可知，度为0的结点比度为2的结点多一个，也就是有251个，所以度为1的结点个数为530-250-251=29个。所以本题选C。
39. 下列叙述中正确的是答案：A
A）解决同一个问题的不同算法的时间复杂度一般是不同的
B）对同一批数据作不同的处理，如果数据存储结构相同，不同算法的时间复杂度肯定相同
C）解决同一个问题的不同算法的时间复杂度必定是相同的
D）对同一批数据作同一种处理，如果数据存储结构不同，不同算法的时间复杂度肯定相同
本题答案为:A
题目解析:一般来说，不同算法的时间复杂度是不同的，而且时间复杂度也受数据的存储结构影响。所以本题选A。(傻瓜都知道是A)
40. 在最坏情况下，堆排序的时间复杂度是答案：C
A）
B）
C） 0(log2 N)
D）
本题答案为:A
题目解析:一般来说，不同算法的时间复杂度是不同的，而且时间复杂度也受数据的存储结构影响。所以本题选A。
41. 下列叙述中正确的是答案：D
A）算法的空间复杂度是指算法程序中指令的条数
B）算法的空间复杂度是指算法程序控制结构的复杂程度
C）压缩数据存储空间不会降低算法的空间复杂度
D）算法的空间复杂度与算法所处理的数据存储空间有关
本题答案为:D
题目解析:算法的空间复杂度是指算法在执行过程中所需要的存储空间，它与算法所处理的数据存储空间有关。所以本题选D。
42. 设数据集合为D={ 1, 2, 3, 4, 5 }。下列数据结构 B=(D, R)中为非线性结构的是答案：C
A）R={ (5,4), (4,3), (3,2), (2,1) }
B）R={ (2,5), (5,4), (3,2), (4,3) }
C）R={ (1,2), (2,3), (4,3), (3,5) }
D）R={ (1,2), (2,3), (3,4), (4,5) }
本题答案为:C
题目解析:线性结构要求只有一个根结点和一个叶子结点，除根结点和叶子结点外，其它结点只有一个前件也只有一个后件。分析各个选项可知只有C选项是非线性结构。所以本题选C。
43. 某二叉树共有400个结点，其中有100个度为1的结点，则该二叉树中的叶子结点数为答案：D
A）151
B）150
C）149
D）不存在这样的二叉树
本题答案为:D
题目解析:二叉树的性质规定，叶子结点个数总比度为2的结点个数多一个，根据本题题干分析，叶子结点和度为2的结点个数之和为400-100=300，无法满足二叉树的性质，故不存在这样的二叉树。所以本题选D。
44. 设栈的存储空间为 S(1:50)，初始状态为 top=51。现经过一系列正常的入栈与退栈操作后，top=20，则栈中的元素个数为答案：C
A）21
B）20
C）31
D）30
本题答案为:C
题目解析:初始状态为top=51，说明栈底的地址为50，栈顶的位置为1，经过一系列操作后，top=21，则说明21-50位置都有元素，共计31个。所以本题选C。
45. 下列叙述中正确的是答案：D
A）有多个指针域的链表一定是非线性结构
B）有两个指针域的链表一定是二叉树的存储结构
C）只有一个根结点的数据结构一定是线性结构
D）有多个指针域的链表有可能是线性结构
本题答案为:D
题目解析:线性结构要求只要只有一个根结点和一个叶子结点，且每个前中间结点有且只有一个前件，有且只有一个后件，那么该结构就是线性结构，与结点有几个指针域没有必然关系，结点在有多个指针域的情况下，只要满足只有一个指针域有具体的值，其他都为空，那么仍然可以构成线性结构。所以本题选D。
46. 某二叉树共有150个结点，其中有50个度为1的结点，则答案：C
A）该二叉树有50个叶子结点
B）该二叉树有49个叶子结点
C）不存在这样的二叉树
D）该二叉树有51个叶子结点
本题答案为:C
题目解析:二叉树的性质规定，叶子结点个数总比度为2的结点个数多一个，根据本题题干分析，叶子结点和度为2的结点个数之和为150-50=100，无法满足二叉树的性质，故不存在这样的二叉树。所以本题选C。
47. 循环队列的存储空间为 Q(1:50)，初始状态为front=rear=50。经过一系列正常的入队与退队操作后，front=rear=25，此后又正常地插入了一个元素，则循环队列中的元素个数为答案：A
A）1
B）51
C）49
D）50
本题答案为:A
题目解析:在循环队列中，当队头指针和队尾指针指向同一个位置时，可能是队满，也可能是队空，而此题明确提出，又正常地插入了一个元素，也就是告诉考生，此题当front=rear=25时，队空。那么在队空状态下，又插入一个元素，所以队列中只有一个元素。所以本题选A。
48. 某二叉树的前序遍历序列为 ABCDE ，中序遍历序列为 CBADE ，则后序遍历序列为答案：C
A）EDCBA
B）EDABC
C）CBEDA
D）CBADE
本题答案为:C
题目解析:由前序遍历可以A是根结点，结合中序遍历知道CB是左子树，DE是右子树；再回到前序遍历，CB这棵左子树B是根结点，由中序遍历知道C是B的左子结点；同理可得出DE右子树的情况；还原出此二叉树的原形后，再进行后序遍历，可以得出后序遍历的顺序为CBEDA。所以本题选C。
49. 下列叙述中正确的是答案：B
A）所有二叉树均不适合用顺序存储结构
B）循环队列是队列的一种存储结构
C）二分查找适用于任何存储方式的有序表
D）有两个指针域的链表一定是二叉树的存储结构
本题答案为:B
题目解析:队列是一种逻辑架构，而循环队列是队列的一种存储结构，所以B正确。并不是所有二叉树都要采用链式存储，所以A选项错误。二分法查找适用于顺序存储的有序表，所以C选项错误。一个数据结构是不是二叉树，并不是由结点包含几个指针域决定的，而是有几个后件决定的，所以D选项错误。所以本题选B。
50. 下列叙述中正确的是答案：B
A）算法复杂度是用算法中指令的条数来度量的
B）数据的存储结构会影响算法的效率
C）算法设计只需考虑结果的可靠性
D）算法复杂度是指算法控制结构的复杂程度
本题答案为:B
题目解析:算法的逻辑结构和存储结构都会影响算法的效率。所以本题选B。
51. 循环队列的存储空间为 Q(1:40)，初始状态为 front=rear=40。经过一系列正常的入队与退队操作后，front=rear=15，此后又正常地退出了一个元素，则循环队列中的元素个数为答案：C
A）14
B）16
C）39
D）9
本题答案为:C
题目解析:当front=rear=15，队满或队空，题目中说明，此时又正常退出一个元素，说明当时是队满，队满的情况下，此循环队列可以有40个元素，退出1个后，还有39个。所以本题选C。
52. 某二叉树的中序遍历序列为 CBADE ，后序遍历序列为 CBEDA ，则前序遍历序列为答案：C
A）CBEDA
B）CBADE
C）ABCDE
D）EDCBA
本题答案为:C (首为第一个,中为首的第一个字母,尾的第一个字母为首的最后一个目.)
题目解析:由后序遍历知道A是根结点，再由中序遍历知道CB是左子树，DE是右子树；再根据后序遍历知道B和D分别是左右子树中的根结点，由中序遍历可知C是B的左子结点，E是D的右子结点，据此画出二叉树图形后，再进行前序遍历，可得到ABCDE。所以本题选C。
53. 下列叙述中正确的是答案：B
A）只有一个根结点和一个叶子结点的必定是线性结构
B）非线性结构可以为空
C）只有一个根结点的必定是线性结构或二叉树
D）没有根结点的一定是非线性结构
本题答案为:B
题目解析: 一个空的数据结构既可以是线性结构也可以是非线性结构，线性结构要求只有一个根结点和一个叶子结点，并且中间结点有且只有一个前件和一个后件。所以本题选B。
54. 设栈的存储空间为 S(1:60)，初始状态为 top=61。现经过一系列正常的入栈与退栈操作后，top=25，则栈中的元素个数为答案：C
A）25
B）35
C）36
D）26
本题答案为:C
题目解析:初始状态下top=61，说明栈底地址为60，当top=25时，25-60位置都有元素，共计36个。所以本题选C。
55. 下列排序方法中，最坏情况下时间复杂度（即比较次数）最低的是答案：A
A）希尔排序
B）快速排序
C）冒泡排序
D）简单插入排序
本题答案为:A
题目解析:冒泡排序、快速排序、直接插入排序、简单选择排序最坏情况下，需要的比较次数为O(n2)；希尔排序最坏情况下，需要的比较次数为O(n1.5)；堆排序最坏情况下，需要的比较次数为O(nlog2n)；顺序查找最坏情况的需要查找n次；二分法查找最坏情况下，需要查找log2n次。所以本题选A。
56. 下列叙述中错误的是答案：B
A）有一个以上叶子结点的必定是非线性结构
B）非线性结构中至少有一个根结点
C）非线性结构中可以没有根结点与叶子结点
D）有一个以上根结点的必定是非线性结构
57. 某二叉树中共有350个结点，其中200个为叶子结点，则该二叉树中度为2的结点数为答案：C
A）199
B）150
C）不可能有这样的二叉树
D）149
本题答案为:C
题目解析:根据二叉树的性质，叶子结点总比度为2的结点多一个，叶子结点有200个，那么度为0的结点就应该有199个，总数已经超过350个，题目自相矛盾。所以本题选C。
58. 设栈的存储空间为 S(1:50)，初始状态为 top=-1。现经过一系列正常的入栈与退栈操作后，top=30，则栈中的元素个数为答案：B
A）19
B）30
C）31
D）20
本题答案为:B
题目解析:初始状态top=0，说明栈底位置为1；当top=30的时候，1-30位置均有元素，共计30个。所以本题选B。
B）堆排序
C）快速排序
D）冒泡排序
本题答案为:B
题目解析:冒泡排序、快速排序、直接插入排序、简单选择排序最坏情况下，需要的比较次数为O(n2)；希尔排序最坏情况下，需要的比较次数为O(n1.5)；堆排序最坏情况下，需要的比较次数为O(nlog2n)；顺序查找最坏情况的需要查找n次；二分法查找最坏情况下，需要查找log2n次。所以本题选B。
60. 下列算法中，最坏情况下时间复杂度最低的为答案：C
A）快速排序
B）堆排序
C）二分查找法
D）顺序查找法
本题答案为:C
题目解析:冒泡排序、快速排序、直接插入排序、简单选择排序最坏情况下，需要的比较次数为O(n2)；希尔排序最坏情况下，需要的比较次数为O(n1.5)；堆排序最坏情况下，需要的比较次数为O(nlog2n)；顺序查找最坏情况的需要查找n次；二分法查找最坏情况下，需要查找log2n次。所以本题选C。
61. 下列叙述中错误的是答案：A
A）所有二叉树都只能用二叉链表表示
B）二分查找法只适用于顺序存储的线性有序表
C）循环队列是队列的存储结构
D）有多个指针域的链表也有可能是线性结构
本题答案为:A
题目解析:一般来说，二叉树采用链式存储结构，但由于完全二叉树的特点，采用顺序存储也能方便地访问其中的每一个元素。故本题选项A的说法是不正确的。所以本题选A。
62. 某二叉树共有400个结点，其中有99个度为1的结点，则该二叉树中的叶子结点数为答案：D
A）149
B）不可能有这样的二叉树
C）150
D）151
本题答案为:D
题目解析:由题意可知，二叉树中度为0和度为2的结点个数为400-99=301个，由二叉树的性质可知，叶子结点个数总比度为2的结点个数多一个，所以叶子结点个数为151个，度为2的结点个数为150个。所以本题选D。
63. 循环队列的存储空间为 Q(1:50)，初始状态为 front=rear=50。经过一系列正常的入队与退队操作后，front=rear=25，则循环队列中的元素个数为答案：A
A）0或50
B）26
C）25
D）49
本题答案为:A (没有后字)
题目解析:当队头和队尾指针指向同一个位置时，可能队满也可能队空。所以本题选A。
64. 设数据集合为D={ 1, 2, 3, 4, 5, 6 }。下列数据结构 B=(D, R)中为线性结构的是答案：C
A）R={ (1,2), (2,3), (3,4), (4,5), (6,5) }
B）R={ (1,2), (2,3), (4,3), (4,5), (5,6) }
C）R={ (1,2), (2,3), (6,5), (3,6), (5,4) }
D）R={ (5,4), (3,4), (3,2), (4,3), (5,6) }
本题答案为:C (会)
题目解析:对下面四个选项分别画出相应的图形表示，可以直接一目了然的得出C选项是线性结构。所以本题选C。
65. 设栈的顺序存储空间为 S(1:m)，初始状态为top=m+1，则栈中的数据元素个数为答案：D
A）m-top
B）top-m+1
C）top-m
D）m-top+1
本题答案为:D (很定+1)
题目解析:本题中栈的容量为m，当top=m+1时，说明栈空，也就是元素个数为0。所以本题选D。
66. 某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则前序遍历序列为答案：A
A）FEDCBA
B）ABCDEF
C）DEFCBA
D）CBAFED
本题答案为:A
题目解析:后序遍历与中遍历相同，说明该二叉树除了叶子结点外，所有结点都只有左子结点，依据题目中的结点情况，可以得出其前序遍历的结果为FEDCBA。所以本题选A。
67. 在具有n个结点的二叉树中，如果各结点值互不相同，但前序遍历序列与中序遍历序列相同，则该二叉树的深度为（根结点在第1层）答案：B
A）n+1
B）n
C）n-1
D）n/2+1
本题答案为:B
题目解析:前序遍历和中序遍历相同说明该树除了叶子结点外，每个结点只有右子结点，也就是该二叉树是深度为n，结点个数为n的二叉树。所以本题选B。
68. 设栈的顺序存储空间为 S(1:m)，初始状态为top=-1，则栈中的数据元素个数为答案：A
A）top+1
B）m-top
C）top-m
D）m-top+1
本题答案为:A
题目解析:初始状态为top=－1,说明栈空时top=－1；入栈时栈顶指针是加操作，每入栈一个元素，则栈顶指针top的值加1。故栈中元素的个数应为top+1。所以本题选A。
69. 下列叙述中错误的是答案：C
A）顺序栈的栈底指针在操作过程中是固定不变的
B）不管是顺序栈还是带链的栈，在操作过程中其栈顶指针均是动态变化的
C）不管是顺序栈还是带链的栈，在操作过程中其栈底指针均是固定不变的
D）带链栈的栈底指针在操作过程中是有可能改变的
本题答案为:C
题目解析:带链栈其栈底指针是动态变化的。所以本题选C。
70. 某二叉树的前序遍历序列与中序遍历序列相同，均为 ABCDEF ，则后序遍历序列为答案：B
A）DEFABC
B）FEDCBA
C）BCDEFA
D）CDEFAB
本题答案为:B
题目解析:如果二叉树的前序遍历和中序遍历相同，那么说明此二叉树除叶子结点外，所有结点都是只有右子结点。据此还原出二叉树的图形后，可得出其后序遍历序列为FEDCBA。所以本题选B。
71. 下列叙述中正确的是答案：C
A）堆可以用完全二叉树表示，其中序遍历序列是有序序列
B）任何二叉树只能采用链式存储结构
C）排序二叉树的中序遍历序列是有序序列
D）多重链表必定是非线性结构
本题答案为:C
题目解析:排序二叉树中，左子树上的值均小于其根结点，右子树上的值均大于其根结点，所以排序二叉树的中序遍历一定是有序序列。所以本题选C。
72. 下列叙述中正确的是答案：D
A）算法的时间复杂度与算法程序中的语句条数成正比
B）算法的时间复杂度与算法程序编制者的水平有关
C）算法的时间复杂度与计算机的运行速度有关
D）算法的时间复杂度与运行算法时特定的输入有关
本题答案为:D
题目解析:在规模一定的情况下，算法的时间复杂度与特定的输入有关。所以本题选D。
73. 下列各排序法中，最坏情况下的时间复杂度最低的是答案：C
A）快速排序
B）冒泡排序
C）堆排序
D）希尔排序
本题答案为:C
题目解析:冒泡排序、快速排序、直接插入排序、简单选择排序最坏情况下，需要的比较次数为O(n2)；希尔排序最坏情况下，需要的比较次数为O(n1.5)；堆排序最坏情况下，需要的比较次数为O(nlog2n)；顺序查找最坏情况的需要查找n次；二分法查找最坏情况下，需要查找log2n次。所以本题选C。
74. 设栈的存储空间为 S(1:50)，初始状态为 top=51。现经过一系列正常的入栈与退栈操作后，top=50，则栈中的元素个数为答案：B
A）49
B）1
C）0
D）50
本题答案为:B
题目解析:初始状态为top=51,说明栈空时top=51；入栈时栈顶指针是减操作，每入栈一个元素，栈顶指针top的值减1，所以当top=50时，栈中元素的个数应为1。所以本题选B。
75. 某二叉树共有399个结点，其中有199个度为2的结点，则该二叉树中的叶子结点数为答案：D
A）198
B）199
C）不存在这样的二叉树
D）200
本题答案为:D
题目解析:二叉树中，叶子结点的个数总比度为2的结点个数多一个，所以该二叉树共有200个叶子结点。所以本题选D。
76. 下列叙述中错误的是答案：A
A）对于各种特定的输入,算法的时间复杂度是固定不变的
B）算法的时间复杂度与使用的程序设计语言无关
C）算法的时间复杂度与使用的计算机系统无关
D）算法的时间复杂度与实现算法过程中的具体细节无关
本题答案为:A
题目解析:算法的时间复杂度是指执行算法所需要的计算工作量。算法所执行的基本运算次数与问题的规模有关。对于一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关。所以本题选A。
77. 在长度为n的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为答案：C
A）3n/4
B）n/4
C）(n+1)/2
D）n
本题答案为:C
题目解析:在长度为n的顺序表中查找一个元素，最好情况的比较次数是1，最坏情况的比较次数是n，则平均情况的比较次数为(n+1)/2。所以本题选C。
78. 设非空二叉树的所有子树中，其左子树上的结点值均小于根结点值，而右子树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是答案：C
A）前序序列
B）后序序列
C）中序序列
D）前序序列或后序序列
本题答案为:C
题目解析:由题目可知，根结点的值一定大于左子树的结点，并且一定小于右子树的结点，所以要想排序，只能是先左子树，再根结点，再右子树，即采用中序遍历。所以本题选C。
79. 循环队列的存储空间为 Q(1:50)，初始状态为 front=rear=50。经过一系列正常的入队与退队操作后，front=rear=25，此后又插入一个元素，则循环队列中的元素个数为答案：A
A）1，或50且产生上溢错误
B）26
C）2
D）51
本题答案为:A
题目解析:当头指针和尾指针指向同一个元素时，循环队列为空或满。按题目中的说法，再次插入一个元素后，只能是循环队列中有1个元素或队满的情况下，发生溢出错误。所以本题选A。
80. 下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是答案：B
A）在链式存储的有序表中进行查找
B）在顺序存储的线性表中寻找最大项
C）在顺序存储的线性表中进行顺序查找
D）在顺序存储的有序表中进行对分查找
本题答案为:B
题目解析:在顺序表中查找最大值，一定是需要把所有数据元素依次进行比较，所以平均情况和最坏情况的比较次数是n-1。所以本题选B。
81. 在具有2n个结点的完全二叉树中，叶子结点个数为答案：A
A）n
B）n+1
C）n-1
D）n/2
本题答案为:A
题目解析:具有偶数个结点的完全二叉树，其叶子结点数和非叶子结点数各占一半，所以该二叉树中叶子结点个数为n。所以本题选A。
82. 下列叙述中正确的是答案：C
A）在循环链表中，头指针和链尾指针的动态变化决定链表的长度
B）在线性链表中，头指针和链尾指针的动态变化决定链表的长度
C）在栈中，栈顶指针的动态变化决定栈中元素的个数
D）在循环队列中，队尾指针的动态变化决定队列的长度
本题答案为:C (我有多长你能决定的了吗)
题目解析:在栈中，栈底指针不动，栈顶指针随着入栈和出栈操作而变化，所以栈顶指针的动态变化决定了栈中元素的个数。所以本题选C。
83. 循环队列的存储空间为 Q(1:40)，初始状态为 front=rear=40。经过一系列正常的入队与退队操作后，front=rear=15，此后又退出一个元素，则循环队列中的元素个数为答案：B
A）15
B）39，或0且产生下溢错误
C）40
D）14
题目解析:当front=rear=15时，循环队列为空或满，此时执行退出元素操作，只能是两种情况，一是满队列减去一个元素，还剩39个，二是空队列产生下溢错误。所以本题选B。
84. 某二叉树的中序遍历序列为 CBADE ，后序遍历序列为 CBADE ，则前序遍历序列为答案：A
A）EDABC
B）CBADE
C）CBEDA
D）EDCBA
题目解析:本题依据中序遍历和后序遍历还原出二叉树的图形，再查找前序遍历即可。所以本题选A。
85. 下列叙述中正确的是答案：B
A）在带链的队列中，队头指针与队尾指针的动态变化决定队列的长度
B）在循环队列中，队头指针和队尾指针的动态变化决定队列的长度
C）在带链的栈中，栈顶指针的动态变化决定栈中元素的个数
D）在循环队列中，队尾指针的动态变化决定队列的长度
题目解析:循环队列中，队头指针和队尾指针都是动态变化的，所以循环队列中的元素个数由队头指针和队尾指针共同决定。所以本题选B。
86. 设栈的存储空间为 S(1:60)，初始状态为 top=61。现经过一系列正常的入栈与退栈操作后，top=1，则栈中的元素个数为答案：A
A）60
B）1
C）0
D）59
题目解析:初始状态为top=61,说明栈空时top=61；入栈时栈顶指针是减操作，即每入栈一个元素，栈顶指针top的值减1，则入栈元素的个数等于61-top；当top的值为1时，栈中元素的个数为60。所以本题选A。
87. 设顺序表的长度为n。下列排序方法中，最坏情况下比较次数小于n(n-1)/2的是答案：D
A）简单插入排序
B）冒泡排序
C）快速排序
D）堆排序
题目解析:冒泡排序、快速排序、直接插入排序、简单选择排序最坏情况下，需要的比较次数为n(n-1)/2；可以特殊记忆一下，堆排序在最坏情况下的比较次数最小。所以本题选D。
88. 在长度为n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中,则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为答案：A
A）3n/4
B）n/4
C）n/2
D）n
题目解析:因为查找的元素有一半机会在表中，所以二分之一的情况下平均比较次数为 n/2，二分之一情况下平均比较次数为 n。总的平均比较次数为(n/2+n)/2=3n/4。所以本题选A。
89. 设一棵树的度为3，其中度为3，2，1的结点个数分别为4，1，3。则该棵树中的叶子结点数为答案：C
A）不可能有这样的树
B）11
C）10
D）12
题目解析:在任意一棵树中，叶子结点个数n0=1+n2+2n3+3n4+…+(n-1)nn ，所以该树中有n0=1+1+2*4＝10。所以本题选C。
90. 设栈的存储空间为 S(1:50)，初始状态为 top=0。现经过一系列正常的入栈与退栈操作后，top=51，则栈中的元素个数为答案：D
A）0
B）50
C）1
D）不可能
题目解析:一共才50个存储空间，不可能出现top=51的情况。所以本题选D。
91. 设顺序表的长度为n。下列算法中，最坏情况下比较次数等于n(n-1)/2的是答案：D
A）堆排序
B）寻找最大项
C）顺序查找
D）快速排序
题目解析:冒泡排序、快速排序、直接插入排序、简单选择排序最坏情况下，需要的比较次数为n(n-1)/2。所以本题选D。
92. 设表的长度为n。下列算法中，最坏情况下比较次数小于n的是答案：D
A）快速排序
B）堆排序
C）顺序查找法
D）二分查找法
题目解析:二分法查找的比较次数是[log2n]。所以本题选D。
93. 下列叙述中错误的是答案：C
A）二叉链表是二叉树的存储结构
B）循环队列是队列的存储结构
C）循环链表是循环队列的存储结构
D）栈是线性结构
题目解析:循环队列是队列的顺序存储结构，所以C选项说法错误。所以本题选C。
94. 设一棵树的度为4，其中度为4，3，2，1的结点个数分别为2，3，3，0。则该棵树中的叶子结点数为答案：C
A）17
B）不可能有这样的树
C）16
D）15
题目解析:在任意一棵树中，叶子结点个数n0=1+n2+2n3+3n4+…+(n-1)nn ，所以该树中有n0=1+3+2*3+3*2=16。所以本题选C。
95. 循环队列的存储空间为 Q(1:100)，初始状态为 front=rear=100。经过一系列正常的入队与退队操作后，front=rear=99，则循环队列中的元素个数为答案：D
A）2
B）99
C）1
D）0或100
题目解析:队头和队尾指针指向同一个元素时，队列为空或队列为满。所以本题选D。
96. 设顺序表的长度为n。下列算法中，最坏情况下比较次数小于n的是答案：B
A）顺序查找法
B）寻找最大项
C）快速排序
D）堆排序
题目解析:冒泡排序、快速排序、直接插入排序、简单选择排序最坏情况下，需要的比较次数为O(n2)；希尔排序最坏情况下，需要的比较次数为O(n1.5)；堆排序最坏情况下，需要的比较次数为O(nlog2n)；顺序查找最坏情况的需要查找n次；二分法查找最坏情况下，需要查找log2n次。顺序表中，寻找最大项只需要比较n-1次。所以本题选B。
97. 设栈的顺序存储空间为 S(1:m)，初始状态为top=m+1。现经过一系列正常的入栈与退栈操作后，top=0，则栈中的元素个数为答案：D
A）m
B）m+1
C）1
D）不可能
题目解析:本题中栈的容量为m，当top=m时表示栈已满，无法再入栈，本题中top=m+1这种情况是不可能出现的。所以本题选D。
98. 某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同一层从左到右）的序列为答案：C
A）CBAFED
B）ABCDEF
C）FEDCBA
D）DEFCBA
题目解析:首先根据题目还原出二叉树的图形结构，再进行输出。所以本题选C。
99. 循环队列的存储空间为 Q(1:200)，初始状态为 front=rear=200。经过一系列正常的入队与退队操作后，front=rear=1，则循环队列中的元素个数为答案：A
A）0或200
B）1
C）199
D）2
题目解析:队头和队尾指针指向同一个元素时，队列为空或队列为满。所以本题选A。
100. 设栈的顺序存储空间为 S(1:m)，初始状态为top=0。现经过一系列正常的入栈与退栈操作后，top=m+1，则栈中的元素个数为答案：A
A）不可能
B）m
C）m+1
D）0
题目解析:栈是一种特殊的线性表，它所有的插入与删除都限定在表的同一端进行。入栈运算即在栈顶位置插入一个新元素，退栈运算即取出栈顶元素赋予指定变量。栈为空时，栈顶指针top=0，经过入栈和退栈运算，指针始终指向栈顶元素。初始状态为top=0，当栈满时，top=m，无法继续入栈，top 值不可能为 m+1。所以本题选A。
101. 下列排序法中，最坏情况下时间复杂度最小的是答案：D
A）冒泡排序
B）希尔排序
C）快速排序
D）堆排序
题目解析:冒泡排序、快速排序、直接插入排序、简单选择排序最坏情况下，需要的比较次数为O(n2)；希尔排序最坏情况下，需要的比较次数为O(n1.5)；堆排序最坏情况下，需要的比较次数为O(nlog2n)；顺序查找最坏情况的需要查找n次；二分法查找最坏情况下，需要查找log2n次。所以本题选D。
102. 某二叉树的前序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同一层从左到右）的序列为答案：A
A）ABCDEF
B）DEFABC
C）FEDCBA
D）BCDEFA
题目解析:首先根据题目还原出二叉树的图形结构，再进行输出。所以本题选A。
103. 下列叙述中正确的是答案：D
A）算法的复杂度与问题的规模无关
B）算法的优化主要通过程序的编制技巧来实现
C）数值型算法只需考虑计算结果的可靠性
D）对数据进行压缩存储会降低算法的空间复杂度
题目解析:算法的空间复杂度是指算法在执行过程中所需要的存储空间，如果对算法执行中的数据进行压缩存储，会降低算法的空间复杂度。所以本题选D。
104. 设数据结构B=(D, R)，其中
D={ a, b, c, d, e, f }
R={ (a, b), (b, c), (c, d), (d, e), (e, f), (f, a) }
该数据结构为答案：D
A）线性结构
B）循环链表
C）循环队列
D）非线性结构
题目解析:把该数据结构的表示方式还原为图形模式，可清晰得出该数据结构是非线性结构。所以本题选D。
105. 下列排序法中，每经过一次元素的交换会产生新的逆序的是答案：D
A）冒泡排序
B）简单选择排序
C）简单插入排序
D）快速排序
题目解析:在数据元素的序列中，对于某个元素，如果其后存在一个元素小于它，则称之为存在一个逆序。冒泡排序只交换相邻元素，但不是每次移动都产生新的逆序。简单插入排序每一次比较后最多移掉一个逆序。快速排序每一次交换移动都会产生新的逆序，因为当不会有新的逆序产生时，本轮比较结束。简单选择排序的基本思想是先从所有n个待排序的数据元素中选择最小的元素，将该元素与第一个元素交换，再从剩下的n-1个元素中选出最小的元素与第2个元素交换，这样做不会产生逆序。所以本题选D。
106. 某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队操作后，front=rear=10。该队列中的元素个数为答案：C
A）0
B）不确定
C）1
D）1或0
题目解析:往队列的队尾插入一个元素为入队，从队列的排头删除一个元素称为退队。初始时 front=rear=0，front总是指向队头元素的前一位置，入队一次rear+l，退队一次front+l。队列队头队尾指针相同时队列为空。而带链的队列，由于每个元素都包含一个指针域指向下一个元素，当带链队列为空时 front=rear=Null，插入第1个元素时，rear+l指向该元素，front+l 也指向该元素，插入第2个元素时rear+l，front不变，删除1个元素时front+l。即 front=rear不为空时带链的队列中只有一个元素。所以本题选C。
107. 某完全二叉树按层次输出（同一层从左到右）的序列为ABCDEFGH。该完全二叉树的前序序列为答案：C
A）HDEBFGCA
B）ABCDEFGH
C）ABDHECFG
D）HDBEAFCG
题目解析:首先还原出二叉树的图形，再进行前序遍历。所以本题选C。
108. 下列叙述中正确的是答案：B
A）有两个指针域的链表就是二叉链表
B）有的二叉树也能用顺序存储结构表示
C）顺序存储结构一定是线性结构
D）多重链表一定是非线性结构
题目解析:所有结点都只有一个子结点的特殊二叉树可以用顺序结构存储。所以本题选B。
109. 下列各排序法中，最坏情况下时间复杂度最小的是答案：C
A）快速排序
B）冒泡排序
C）堆排序
D）希尔排序
题目解析:冒泡排序、快速排序、直接插入排序、简单选择排序最坏情况下，需要的比较次数为O(n2)；希尔排序最坏情况下，需要的比较次数为O(n1.5)；堆排序最坏情况下，需要的比较次数为O(nlog2n)；顺序查找最坏情况的需要查找n次；二分法查找最坏情况下，需要查找log2n次。所以本题选C。
110. 某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队操作后，front=10, rear=5。该队列中的元素个数为答案：D
A）5
B）6
C）4
D）不确定
题目解析:在链式存储方式中，每个结点有两部分组成，一部分为数据域，一部分为指针域，front=rear时说明只有一个元素，其他情况无法判断。所以本题选D。
111. 某二叉树的前序序列为ABDFHCEG，中序序列为HFDBACEG。该二叉树按层次输出（同一层从左到右）的序列为答案：B
A）HGFEDCBA
B）ABCDEFGH
C）ACEGBDFH
D）HFDBGECA
题目解析:首先根据前序序列和中序序列还原出二叉树的图形，然后进行编号。所以本题选B。
112. 某带链栈的初始状态为 top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=10，bottom=20。该栈中的元素个数为答案：D
A）10
B）0
C）1
D）不确定
题目解析:带链的栈是具有栈属性的链表。线性链表的存储单元是不连续的，为把存储空间中一些离散的空闲存储结点利用起来，把所有空闲的结点组织成一个带链的栈，称为可利用栈。线性链表执行删除操作运算时，被删除的结点可以回收到可利用栈，对应与可利用栈的入栈运算；线性链表执行插入运算时，需要一个新的结点，可以在可利用栈中取栈顶结点，对应于可利用栈的退栈运算。可利用栈的入栈运算和退栈运算只需要改动top指针即可。因为是不连续的存储空间，所以top指针将不会有规律地连续变化，因此无法据此判断栈中的元素个数。所以本题选D。
113. 设表的长度为15。则在最坏情况下，快速排序所需要的比较次数为答案：B
A）75
B）105
C）15
D）55
题目解析:冒泡排序、快速排序、直接插入排序、简单选择排序最坏情况下，需要的比较次数为n(n-1)/2。所以本题选B。
114. 设循环队列的存储空间为Q(1:100)，初始状态为空。现经过一系列正常操作后，front=49，则循环队列中的元素个数为答案：D
A）49
B）51
C）50
D）不确定
题目解析:因为队尾指针所在位置没有给出，所以无法计算出该循环队列中现有多少个元素。所以本题选D。
115. 某完全二叉树按层次输出（同一层从左到右）的序列为ABCDEFGH。该完全二叉树的中序序列为答案：B
A）ABCDEFGH
B）HDBEAFCG
C）HDEBFGCA
D）ABDHECFG
题目解析:首先还原出二叉树的图形，再进行中序遍历。所以本题选B。
116. 下列叙述中正确的是答案：B
A）解决一个问题的算法是唯一的
B）解决一个问题可以有不同的算法，且它们的时间复杂度可以是不同的
C）解决一个问题可以有不同的算法，但它们的时间复杂度必定是相同的
D）算法的时间复杂度与计算机系统有关
题目解析:一个问题可以有不同的算法，不同算法的时间复杂度可以是不同的。所以本题选B。
117. 设表的长度为n。下列查找算法中，在最坏情况下，比较次数最少的是答案：D
A）寻找最小项
B）寻找最大项
C）顺序查找
D）有序表的二分查找
题目解析:有序表的二分法查找，平均情况下，需要比较[log2n]次，顺序查找平均需要n/2次，寻找最大项、最小项都需要比较n-1次。所以本题选D。
118. 某带链栈的初始状态为 top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=bottom=20。该栈中的元素个数为答案：D
A）不确定
B）20
C）0
D）1
题目解析:带链的栈是具有栈属性的链表。线性链表的存储单元是不连续的，为把存储空间中一些离散的空闲存储结点利用起来，把所有空闲的结点组织成一个带链的栈，称为可利用栈。线性链表执行删除操作运算时，被删除的结点可以“回收”到可利用栈，对应于可利用栈的入栈运算，线性链表执行插入运算时，需要一个新的结点，可以在可利用栈中取栈顶结点，对应于可利用栈的退栈运算。可利用栈的入栈运算和退栈运算只需要改动top指针即可。当top=bottom=20时链栈中的元素个数为1。所以本题选D。
119. 某二叉树的前序序列为ABDFHCEG，中序序列为HFDBACEG。该二叉树的后序序列为答案：D
A）ABCDEFGH
B）ACEGBDFH
C）HGFEDCBA
D）HFDBGECA
题目解析:由前序遍历可知，根结点是A，再通过中序遍历可知左子树结点包括HFDB，所以后序遍历中，一定是选访问左子树的HFDB四个结点。所以本题选D。
120. 下列叙述中错误的是答案：B
A）算法的空间复杂度与算法运行输出结果的数据量无关
B）算法的时间复杂度与问题规模无关
C）算法的时间复杂度与计算机系统无关
D）算法的时间复杂度与空间复杂度没有必然的联系
题目解析:算法的时间复杂度与问题的规模有关。所以本题选B。
121. 设表的长度为20。则在最坏情况下，冒泡排序的比较次数为答案：B
A）90
B）190
C）20
D）19
题目解析:冒泡排序最坏情况下的比较次数为n(n-1)/2。所以本题选B。
122. 在带链栈中，经过一系列正常的操作后，如果top=bottom，则栈中的元素个数为答案：B
A）0
B）0 或 1
C）栈满
D）1
题目解析:在链栈中，栈为空时top＝bottom=NULL；入栈第一个元素后，栈顶指针和top和栈底指针都指向该元素，仍然 top=bottom。所以本题选B。
123. 设一棵树的度为3，共有27个结点，其中度为3，2，0的结点数分别为4，1，10。该树中度为1的结点数为答案：D
A）不可能有这样的树
B）13
C）11
D）12
题目解析:所有结点的度的个数之和加根结点的总数就是树的总结点数。所以度为1的结点个数为27－4－1－0*10＝12。所以本题选D。
124. 设数据结构B=(D, R)，其中
D={ a, b, c, d, e, f }
R={ (f, a), (d, b), (e, d), (c, e), (a, c) }
该数据结构为答案：A
A）线性结构
B）非线性结构
C）循环队列
D）循环链表
题目解析:根据数据结构的表示可以得出，该数据结构的元素是一个线性结构，其元素前后顺序依次为facedb。所以本题选A。
125. 下列叙述中错误的是答案：A
A）循环队列空的条件是队头指针与队尾指针相同
B）带链栈的栈底指针是随栈的操作而动态变化的
C）若二叉树没有叶子结点，则为空二叉树
D）若带链队列中只有一个元素，则队头指针与队尾指针必定相同
题目解析:循环队列为空的条件是队头指针和队尾指针相同，并且为空，即rear=front=NULL,选项A的说法是错误的。所以本题选A。
126. 带链栈空的条件是答案：B
A）top=-1 且 bottom=NULL
B）top=bottom=NULL
C）top=NULL 且 bottom=-1
D）top=bottom=-1
题目解析:在链栈中，栈为空时top＝bottom=NULL，栈顶指针top和栈底指针bottom均指向空的存储单元。所以本题选B。
127. 设一棵度为3的树，其中度为2，1，0的结点数分别为3，1，6。该树中度为3的结点数为答案：D
A）3
B）2
C）不可能有这样的树
D）1
题目解析:在任意一棵树中，叶子结点个数n0=1+n2+2n3+3n4+…+(n-1)nn ，所以该树中有5＝1+0*n2+2*n3，所以n3=2。所以本题选D。
128. 下列数据结构中，不能采用顺序存储结构的是答案：B
A）队列
B）非完全二叉树
C）栈
D）堆
题目解析:在计算机中，二叉树通常采用链式存储结构。对于满二叉树与完全二叉树，可以按层次进行顺序存储。所以本题选B。
129. 设二叉树共有375个结点，其中度为2的结点有187个。则度为1的结点个数是答案：C
A）不可能有这样的二叉树
B）1
C）0
D）188
题目解析:度为0的结点比度为2的结点多一个，所以有188个叶子结点。可得度为1的结点个数为375－187－188＝0。所以本题选C。
130. 在带链队列中，经过一系列正常的操作后，如果front=rear，则队列中的元素个数为答案：D
A）1
B）队列满
C）0
D）0 或 1
题目解析:在带链队列中，队列为空时front=rear=NULL，队头指针front和队尾指针bottom均指向空的存储单元；入队一个元素后，队头指针和队尾指针都指向该元素，即front=rear。所以本题选D。
131. 设一棵树的度为3，其中没有度为2的结点，且叶子结点数为5。该树中度为3的结点数为答案：B
A）不可能有这样的树
B）2
C）1
D）3
题目解析:在任意一棵树中，叶子结点个数n0=1+n2+2n3+3n4+…+(n-1)nn ，所以该树中，n0＝1+0+2*3＝7。所以本题选B。
132. 设二叉树共有500个结点，其中叶子结点有250个。则度为2的结点个数是答案：D
A）1
B）0
C）不可能有这样的二叉树
D）249
题目解析:在二叉树中，叶子结点总比度为2的结点多一个，所以度为2的结点个数为249个。所以本题选D。
133. 下列叙述中正确的是答案：D
A）带链栈的栈底指针是固定的
B）若带链队列的队头指针与队尾指针相同，则队列为空
C）若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素
D）带链栈的栈底指针是随栈的操作而动态变化的
题目解析:带链栈的栈底指针是动态变化的。所以本题选D。
134. 带链队列空的条件是答案：C
A）front=-1 且 rear=NULL
B）front=rear=-1
C）front=rear=NULL
D）front=NULL 且 rear=-1
题目解析:在链栈中，栈为空时top＝bottom=NULL，栈顶指针top和栈底指针bottom均指向空的存储单元。所以本题选C。
135. 设一棵树的度为3，其中没有度为2的结点，且叶子结点数为6。该树中度为3的结点数为答案：B
A）3
B）不可能有这样的树
C）1
D）2
题目解析:在任意一棵树中，叶子结点个数n0=1+n2+2n3+3n4+…+(n-1)nn ，所以该树中，6＝1+0+2*n3，所以n3＝2.5，结点数竟然算出了小数，矛盾，所以不存在这样的二叉树。所以本题选B。
136. 下列叙述中正确的是答案：A
A）循环队列是线性结构
B）循环队列是链式存储结构
C）循环队列是非线性存储结构
D）循环队列是线性逻辑结构
题目解析:循环队列是队列的一种，队列都是线性结构。循环队列是队列的顺序存储结构，所以D选项说法不正确。所以本题选A。
137. 设某棵树的度为3，其中度为3,2,1的结点个数分别为3,0,4。则该树中的叶子结点数为答案：C
A）不可能有这样的树
B）6
C）7
D）8
题目解析:在任意一棵树中，叶子结点个数n0=1+n2+2n3+3n4+…+(n-1)nn ，所以该树中，n0＝1+0+2*3＝7。所以本题选C。
138. 设有一个栈与一个队列的初始状态均为空。现有一个序列A,B,C,D,E,F,G,H。先分别将序列中的前4个元素依次入栈，后4个元素依次入队；然后分别将栈中的元素依次退栈，再将队列中的元素依次退队。最后得到的序列为答案：C
A）D,C,B,A,H,G,F,E
B）A,B,C,D,H,G,F,E
C）D,C,B,A,E,F,G,H
D）A,B,C,D,E,F,G,H
题目解析:栈是先进后出，队列是先进先出。所以本题选C。
139. 下列叙述中错误的是答案：D
A）具有两个根结点的数据结构一定属于非线性结构
B）具有两个以上叶子结点的数据结构一定属于非线性结构
C）具有一个根结点且只有一个叶子结点的数据结构也可能是非线性结构
D）具有两个以上指针域的链式结构一定属于非线性结构
题目解析:在线性结构中，每个结点最多只能有一个前件和一个后件，不限制有一个指域或两个指针域。具有两个以上指针域的链式结构，只要不同结点的相同指针域的值均不同，则依然可能是线性结构。所以本题选D。
140. 下列结构中属于线性结构链式存储的是答案：D
A）循环队列
B）二叉链表
C）二维数组
D）双向链表
题目解析:二叉链表不是线性结构。循环队列是队列的顺序存储。本题只有双向链表是线性结构的链式存储。所以本题选D。
141. 下列叙述中错误的是答案：C
A）循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点
B）循环链表实现了空表与非空表运算的统一
C）循环链表的存储空间是连续的
D）循环链表中有一个表头结点
题目解析:链式存储的存储空间都是不连续的。所以本题选C。
142.度为3的一棵树共有30个结点，其中度为3,1的结点个数分别为3,4。则该树中的叶子结点数为答案：A
A）15
B）16
C）14
D）不可能有这样的树
题目解析:在任意一棵树中，总结点数＝总分支数+1，所以该树的总结点数为3*3+2*n2+1*4+0*15+1=30，所以n2＝8。在任意一棵树中，叶子结点个数n0=1+n2+2n3+3n4+…+(n-1)nn ，所以该树中，n0＝1+8+2*3＝15。所以本题选A。
143. 在长度为97的顺序有序表中作二分查找，最多需要的比较次数为答案：C
A）6
B）48
C）7
D）96
题目解析:二分查找的比较次数是最坏情况下是[log2n]。所以本题选C。
144. 下列结构中属于非线性结构的是答案：A
A）二叉链表
B）循环队列
C）双向链表
D）二维数组
题目解析:二叉链表不是线性结构。循环队列是队列的顺序存储。本题只有双向链表是线性结构的链式存储。所以本题选A。
145. 从表中任何一个结点位置出发就可以不重复地访问到表中其他所有结点的链表是答案：C
A）单向链表
B）双向链表
C）循环链表
D）二叉链表
题目解析:只有循环链表才能不重复的访问到表中的所有结点。所以本题选C。
146. 设二叉树的前序序列与中序序列均为ABCDEFGH，则该二叉树的后序序列为答案：C
A）ABCDHGFE
B）DCBAHGFE
C）HGFEDCBA
D）EFGHABCD
题目解析:本题需要首先根据题干还原出二叉树的形状，然后再进行遍历访问。所以本题选C。
147. 设某棵树的度为3，其中度为3,1,0的结点个数分别为3,4,15。则该树中总结点数为答案：A
A）30
B）35
C）22
D）不可能有这样的树
题目解析:任意一棵树中，n0=1+n2+2n3+3n4+…+(n-1)nn 。所以该树中，15＝1+n2+2*3，所以n2=15-1-6=8；在任意一棵树中，总结点数＝总分支数+1，所以该树的总结点数为3*3+2*8+1*4+0*15+1=30。所以本题选A。
