考点2：二级公共基础知识新-数据结构与算法
以下为《考点2：二级公共基础知识新-数据结构与算法》的无排版文字预览，完整内容请下载
1. 下列各排序法中，最坏情况下的时间复杂度最低的是
答案：A
A）堆排序
B）快速排序
C）冒泡排序
D）希尔排序
2. 设栈的存储空间为 S(1:50)，初始状态为 top=51。现经过一系列正常的入栈与退栈操作后，top=50，则栈中的元素个数为
答案：C
A）0
B）49
C）1
D）50
3. 某二叉树共有399个结点，其中有199个度为2的结点，则该二叉树中的叶子结点数为
答案：D
A）不存在这样的二叉树
B）198
C）199
D）200
4. 在长度为n的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为
答案：A
A）(n+1)/2
B）n
C）n/4
D）3n/4
5. 设非空二叉树的所有子树中，其左子树上的结点值均小于根结点值，而右子树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是
答案：D
A）前序序列
B）前序序列或后序序列
C）后序序列
D）中序序列
6. 循环队列的存储空间为 Q(1:50)，初始状态为 front=rear=50。经过一系列正常的入队与退队操作后，front=rear=25，此后又插入一个元素，则循环队列中的元素个数为
答案：A
A）1，或50且产生上溢错误
B）51
C）2
D）26
7. 在具有2n个结点的完全二叉树中，叶子结点个数为
答案：B
A）n+1
B）n
C）n/2
D）n-1
8. 下列叙述中正确的是
答案：B
A）在线性链表中，头指针和链尾指针的动态变化决定链表的长度
B）在栈中，栈顶指针的动态变化决定栈中元素的个数
C）在循环队列中，队尾指针的动态变化决定队列的长度
D）在循环链表中，头指针和链尾指针的动态变化决定链表的长度
9. 循环队列的存储空间为 Q(1:40)，初始状态为 front=rear=40。经过一系列正常的入队与退队操作后，front=rear=15，此后又退出一个元素，则循环队列中的元素个数为
答案：A
A）39，或0且产生下溢错误
B）14
C）15
D）40
10. 下列叙述中正确的是
答案：A
A）在循环队列中，队头指针和队尾指针的动态变化决定队列的长度
B）在带链的栈中，栈顶指针的动态变化决定栈中元素的个数
C）在带链的队列中，队头指针与队尾指针的动态变化决定队列的长度
D）在循环队列中，队尾指针的动态变化决定队列的长度
11. 设栈的存储空间为 S(1:60)，初始状态为 top=61。现经过一系列正常的入栈与退栈操作后，top=1，则栈中的元素个数为
答案：B
A）1
B）60
C）0
D）59
12. 设顺序表的长度为n。下列排序方法中，最坏情况下比较次数小于n(n-1)/2的是
答案：B
A）冒泡排序
B）堆排序
C）快速排序
D）简单插入排序
13. 设一棵树的度为3，其中度为3，2，1的结点个数分别为4，1，3。则该棵树中的叶子结点数为
答案：A
A）10
B）不可能有这样的树
C）11
D）12
14. 设栈的存储空间为 S(1:50)，初始状态为 top=0。现经过一系列正常的入栈与退栈操作后，top=51，则栈中的元素个数为
答案：D
A）1
B）50
C）0
D）不可能
15. 设顺序表的长度为n。下列算法中，最坏情况下比较次数等于n(n-1)/2的是
答案：A
A）快速排序
B）顺序查找
C）寻找最大项
D）堆排序
16. 下列叙述中错误的是
答案：D
A）二叉链表是二叉树的存储结构
B）循环队列是队列的存储结构
C）栈是线性结构
D）循环链表是循环队列的存储结构
17. 设一棵树的度为4，其中度为4，3，2，1的结点个数分别为2，3，3，0。则该棵树中的叶子结点数为
答案：C
A）15
B）不可能有这样的树
C）16
D）17
18. 循环队列的存储空间为 Q(1:100)，初始状态为 front=rear=100。经过一系列正常的入队与退队操作后，front=rear=99，则循环队列中的元素个数为
答案：A
A）0或100
B）2
C）99
D）1
19. 设栈的顺序存储空间为 S(1:m)，初始状态为top=m+1。现经过一系列正常的入栈与退栈操作后，top=0，则栈中的元素个数为
答案：A
A）不可能
B）m+1
C）m
D）1
20. 某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同一层从左到右）的序列为
答案：B
A）CBAFED
B）FEDCBA
C）ABCDEF
D）DEFCBA
21. 循环队列的存储空间为 Q(1:200)，初始状态为 front=rear=200。经过一系列正常的入队与退队操作后，front=rear=1，则循环队列中的元素个数为
答案：A
A）0或200
B）2
C）199
D）1
22. 下列排序法中，最坏情况下时间复杂度最小的是
答案：C
A）快速排序
B）冒泡排序
C）堆排序
D）希尔排序
23. 某二叉树的前序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同一层从左到右）的序列为
答案：C
A）FEDCBA
B）DEFABC
C）ABCDEF
D）BCDEFA
24. 下列叙述中正确的是
答案：C
A）算法的复杂度与问题的规模无关
B）数值型算法只需考虑计算结果的可靠性
C）对数据进行压缩存储会降低算法的空间复杂度
D）算法的优化主要通过程序的编制技巧来实现
25. 下列排序法中，每经过一次元素的交换会产生新的逆序的是
答案：D
A）简单插入排序
B）简单选择排序
C）冒泡排序
D）快速排序
26. 某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队操作后，front=rear=10。该队列中的元素个数为
答案：D
A）不确定
B）0
C）1或0
D）1
27. 某完全二叉树按层次输出（同一层从左到右）的序列为ABCDEFGH。该完全二叉树的前序序列为
答案：D
A）HDEBFGCA
B）HDBEAFCG
C）ABCDEFGH
D）ABDHECFG
28. 下列各排序法中，最坏情况下时间复杂度最小的是
答案：D
A）希尔排序
B）冒泡排序
C）快速排序
D）堆排序
29. 某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队操作后，front=10, rear=5。该队列中的元素个数为
答案：D
A）4
B）6
C）5
D）不确定
30. 某二叉树的前序序列为ABDFHCEG，中序序列为HFDBACEG。该二叉树按层次输出（同一层从左到右）的序列为
答案：D
A）HGFEDCBA
B）ACEGBDFH
C）HFDBGECA
D）ABCDEFGH
31. 设表的长度为15。则在最坏情况下，快速排序所需要的比较次数为
答案：C
A）55
B）75
C）105
D）15
32. 设循环队列的存储空间为Q(1:100)，初始状态为空。现经过一系列正常操作后，front=49，则循环队列中的元素个数为
答案：A
A）不确定
B）51
C）50
D）49
33. 某完全二叉树按层次输出（同一层从左到右）的序列为ABCDEFGH。该完全二叉树的中序序列为
答案：B
A）HDEBFGCA
B）HDBEAFCG
C）ABCDEFGH
D）ABDHECFG
34. 设表的长度为n。下列查找算法中，在最坏情况下，比较次数最少的是
答案：D
A）寻找最小项
B）寻找最大项
C）顺序查找
D）有序表的二分查找
35. 某带链栈的初始状态为 top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=bottom=20。该栈中的元素个数为
答案：B
A）0
B）1
C）不确定
D）20
36. 某二叉树的前序序列为ABDFHCEG，中序序列为HFDBACEG。该二叉树的后序序列为
答案：D
A）ABCDEFGH
B）ACEGBDFH
C）HGFEDCBA
D）HFDBGECA
37. 设表的长度为20。则在最坏情况下，冒泡排序的比较次数为
答案：A
A）190
B）90
C）19
D）20
38. 在带链栈中，经过一系列正常的操作后，如果top=bottom，则栈中的元素个数为
答案：B
A）栈满
B）0 或 1
C）1
D）0
39. 设一棵树的度为3，共有27个结点，其中度为3，2，0的结点数分别为4，1，10。该树中度为1的结点数为
答案：B
A）不可能有这样的树
B）12
C）11
D）13
40. 下列叙述中错误的是
答案：D
A）若带链队列中只有一个元素，则队头指针与队尾指针必定相同
B）若二叉树没有叶子结点，则为空二叉树
C）带链栈的栈底指针是随栈的操作而动态变化的
D）循环队列空的条件是队头指针与队尾指针相同
41. 带链栈空的条件是
答案：D
A）top=bottom=-1
B）top=NULL 且 bottom=-1
C）top=-1 且 bottom=NULL
D）top=bottom=NULL
42. 设一棵度为3的树，其中度为2，1，0的结点数分别为3，1，6。该树中度为3的结点数为
答案：D
A）不可能有这样的树
B）3
C）2
D）1
43. 设二叉树共有375个结点，其中度为2的结点有187个。则度为1的结点个数是
答案：D
A）1
B）不可能有这样的二叉树
C）188
D）0
44. 在带链队列中，经过一系列正常的操作后，如果front=rear，则队列中的元素个数为
答案：C
A）1
B）队列满
C）0 或 1
D）0
45. 设一棵树的度为3，其中没有度为2的结点，且叶子结点数为5。该树中度为3的结点数为
答案：C
A）不可能有这样的树
B）1
C）2
D）3
46. 下列叙述中正确的是
答案：D
A）若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素
B）带链栈的栈底指针是固定的
C）若带链队列的队头指针与队尾指针相同，则队列为空
D）带链栈的栈底指针是随栈的操作而动态变化的
47. 带链队列空的条件是
答案：B
A）front=-1 且 rear=NULL
B）front=rear=NULL
C）front=rear=-1
D）front=NULL 且 rear=-1
48. 设一棵树的度为3，其中没有度为2的结点，且叶子结点数为6。该树中度为3的结点数为
答案：C
A）3
B）2
C）不可能有这样的树
D）1
49. 设某棵树的度为3，其中度为3,2,1的结点个数分别为3,0,4。
则该树中的叶子结点数为
答案：A
A）7
B）不可能有这样的树
C）8
D）6
50. 设有一个栈与一个队列的初始状态均为空。现有一个序列A,B,C,D,E,F,G,H。
先分别将序列中的前4个元素依次入栈，后4个元素依次入队；然后分别将栈中的元素
依次退栈，再将队列中的元素依次退队。最后得到的序列为
答案：A
A）D,C,B,A,E,F,G,H
B）A,B,C,D,E,F,G,H
C）A,B,C,D,H,G,F,E
D）D,C,B,A,H,G,F,E
51. 下列叙述中错误的是
答案：C
A）具有一个根结点且只有一个叶子结点的数据结构也可能是非线性结构
B）具有两个以上叶子结点的数据结构一定属于非线性结构
C）具有两个以上指针域的链式结构一定属于非线性结构
D）具有两个根结点的数据结构一定属于非线性结构
52. 下列叙述中错误的是
答案：D
A）循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点
B）循环链表中有一个表头结点
C）循环链表实现了空表与非空表运算的统一
D）循环链表的存储空间是连续的
53.度为3的一棵树共有30个结点，其中度为3,1的结点个数分别为3,4。
则该树中的叶子结点数为
答案：D
A）14
B）不可能有这样的树
C）16
D）15
54. 在长度为97的顺序有序表中作二分查找，最多需要的比较次数为
答案：A
A）7
B）6
C）48
D）96
55. 从表中任何一个结点位置出发就可以不重复地访问到表中其他所有结点的链表是
答案：A
A）循环链表
B）二叉链表
C）单向链表
D）双向链表
56. 设二叉树的前序序列与中序序列均为ABCDEFGH，则该二叉树的后序序列为
答案：E
A）EFGHABCD
B）ABCDEFGH
C）DCBAHGFE
D）ABCDHGFE
E）HGFEDCBA
57. 设某棵树的度为3，其中度为3,1,0的结点个数分别为3,4,15。
则该树中总结点数为
答案：D
A）不可能有这样的树
B）22
C）35
D）30
58. 在快速排序法中，每经过一次数据交换（或移动）后
答案：B
A）不会产生新的逆序
B）能消除多个逆序
C）消除的逆序个数一定比新产生的逆序个数多
D）只能消除一个逆序
59. 线性表的长度为n。在最坏情况下，比较次数为n-1的算法是
答案：C
A）有序表的插入
B）同时寻找最大项与最小项
C）寻找最大项
D）顺序查找
60. 设某棵树的度为3，其中度为2,1,0的结点个数分别为3,4,15。
则该树中总结点数为
答案：B
A）22
B）不可能有这样的树
C）35
D）30
61. 在希尔排序法中，每经过一次数据交换后
答案：C
A）消除的逆序个数一定比新产生的逆序个数多
B）不会产生新的逆序
C）能消除多个逆序
D）只能消除一个逆序
62. 设二叉树的后序序列与中序序列均为ABCDEFGH，则该二叉树的前序序列为
答案：A
A）HGFEDCBA
B）DCBAHGFE
C）ABCDEFGH
D）ABCDHGFE
63. 下列叙述中正确的是
答案：B
A）具有两个以上指针的链表必定是非线性结构
B）所有的线性结构都可以采用顺序存储结构
C）循环队列是队列的链式存储结构
D）能采用顺序存储的必定是线性结构
64. 设二叉树的前序序列为ABDEGHCFIJ，中序序列为DBGEHACIFJ。
则按层次输出（从上到下，同一层从左到右）的序列为
答案：A
A）ABCDEFGHIJ
B）GHIJDEFBCA
C）DGHEBIJFCA
D）JIHGFEDCBA
65. 设循环队列的存储空间为Q(1: 50)，初始状态为 front=rear=50。经过一系列正常的操作后，front-1=rear。
为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为
答案：C
A）0
B）1
C）48
D）49
66. 设顺序表的长度为40，对该表进行冒泡排序。在最坏情况下需要的比较次数为
答案：D
A）41
B）40
C）820
D）780
67. 设循环队列的存储空间为Q(1: 50)，初始状态为 front=rear=50。经过一系列正常的操作后，front=rear-1。
为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为
答案：D
A）49
B）1
C）50
D）0
68. 设二叉树的前序序列为ABDEGHCFIJ，中序序列为DBGEHACIFJ。则后序序列为
答案：A
A）DGHEBIJFCA
B）JIHGFEDCBA
C）ABCDEFGHIJ
D）GHIJDEFBCA
69. 设顺序表的长度为16，对该表进行简单插入排序。在最坏情况下需要的比较次数为
答案：C
A）30
B）15
C）120
D）60
70. 设表的长度为n。在下列结构所对应的算法中，最坏情况下时间复杂度最低的是
答案：D
A）堆排序
B）希尔排序
C）有序链表查找
D）循环链表中寻找最大项
71. 设循环队列的存储空间为Q(1: m)，初始状态为 front=rear=m。经过一系列正常的操作后，front=1，rear=m。
为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为
答案：C
A）m
B）1
C）m-2
D）m-1
72. 设二叉树的后序序列为DGHEBIJFCA，中序序列为DBGEHACIFJ。则前序序列为
答案：A
A）ABDEGHCFIJ
B）JIHGFEDCBA
C）ABCDEFGHIJ
D）GHIJDEFBCA
73. 下列叙述中正确的是
答案：B
A）循环队列是队列的一种链式存储结构
B）循环队列是队列的一种顺序存储结构
C）循环队列中的队尾指针一定小于队头指针
D）循环队列中的队尾指针一定大于队头指针
74. 某完全二叉树有256个结点，则该二叉树的深度为
答案：B
A）8
B）9
C）10
D）7
75. 下列叙述中错误的是
答案：A
A）非线性结构一定不能采用顺序存储结构
B）线性结构一定能采用顺序存储结构
C）线性结构也能采用链式存储结构
D）有的非线性结构也能采用顺序存储结构
76. 循环队列的存储空间为Q(1:50)。经过一系列正常的入队与退队操作后，front=rear=25。
后又成功地将一个元素退队，此时队列中的元素个数为
答案：D
A）24
B）0
C）26
D）49
77. 设二叉树中有20个叶子结点，5个度为1的结点，则该二叉树中总的结点数为
答案：D
A）46
B）45
C）不可能有这样的二叉树
D）44
78. 设栈与队列初始状态为空。首先A,B,C,D,E依次入栈，再F,G,H,I,J依次入队；然后依次出队至队空，再依次出栈至栈空。则输出序列为
答案：D
A）E,D,C,B,A,J,I,H,G,F
B）F,G,H,I,J,A,B,C,D,E,
C）E,D,C,B,A,F,G,H,I,J
D）F,G,H,I,J,E,D,C,B,A
79. 循环队列的存储空间为Q(1:50)。经过一系列正常的入队与退队操作后，front=rear=25。
后又成功地将一个元素入队，此时队列中的元素个数为
答案：C
A）2
B）50
C）1
D）26
80. 树的度为3，且有9个度为3的结点，5个度为1的结点，但没有度为2的结点。则该树总的结点数为
答案：D
A）14
B）32
C）19
D）33
81. 设栈与队列初始状态为空。首先A,B,C,D,E依次入栈，再F,G,H,I,J依次入队；然后依次出栈至栈空，再依次出队至队空。则输出序列为
答案：A
A）E,D,C,B,A,F,G,H,I,J
B）F,G,H,I,J,A,B,C,D,E,
C）E,D,C,B,A,J,I,H,G,F
D）F,G,H,I,J,E,D,C,B,A
82. 设二叉树的中序序列为BCDA，前序序列为ABCD，则后序序列为
答案：D
A）BCDA
B）ACDB
C）CBDA
D）DCBA
83. 树的度为3，且有9个度为3的结点，5个度为1的结点，但没有度为2的结点。则该树中的叶子结点数为
答案：B
A）32
B）19
C）33
D）18
84. 下列叙述中错误的是
答案：D
A）二叉链表是二叉树的存储结构
B）向量属于线性结构
C）栈和队列是线性表
D）循环链表是循环队列的链式存储结构
85. 下列算法中，最坏情况下时间复杂度最低的是
答案：C
A）堆排序
B）顺序查找
C）有序表的对分查找
D）寻找最大项
86. 树的度为3，且有9个度为3的结点，20个叶子结点，但没有度为1的结点。则该树总的结点数为
答案：D
A）47
B）不可能有这样的树
C）29
D）30
87. 设二叉树的中序序列为BCDA，后序序列为DCB 内容过长，仅展示头部和尾部部分文字预览，全文请查看图片预览。 的是
答案：A
A）向量是顺序存储的线性结构
B）只有一个根结点和一个叶子结点的结构必定是线性结构
C）所有非线性结构都能采用顺序存储结构
D）非线性结构只能采用链式存储结构
119. 下列叙述中错误的是
答案：D
A）具有两个指针域的链表不一定是线性结构
B）具有两个指针域的链表不一定是非线性结构
C）循环队列是队列的存储结构
D）循环链表是循环队列的链式存储结构
120. 设二叉树的前序序列为ABCDEF，中序序列为BDFECA，则该二叉树的后序序列为
答案：D
A）BDFECA
B）CBAFED
C）ABCDEF
D）FEDCBA
001-010 ACDAD ABBA
011-020 BBADA DCAA
021-030 ACCCD DDDD
031-040 CABDB DABB
041-050 DDDCC DBCA
051-060 CDDAA EDBC
061-070 CABAC DDAC
071-080 CABBA DDDC
081-090 ADBDC DADA
091-100 DDBAA CBBD
101-110 BCCBD DBBC
111-120 BCCBB DAAD
[文章尾部最后500字内容到此结束,中间部分内容请查看底下的图片预览]请点击下方选择您需要的文档下载。
- 智慧树知到形势与政策2020网课答案
- 吉大算法题汇总（C语言版）
- 复习提纲_6月＿测绘工程
- （数据结构）实验报告单
- --2数据结构复习大纲
- 公共基础知识点精简版
- 计算机等级考试公共基础知识超强总结，栈、队列、树
- 数据结构导论自考题模拟1
以上为《考点2：二级公共基础知识新-数据结构与算法》的无排版文字预览，完整内容请下载
考点2：二级公共基础知识新-数据结构与算法由用户“暴躁伙伴”分享发布，转载请注明出处