4. 下列排序方法中,最坏情况下时间复杂度(即比较次数)低于O(n2)的是______。
5. 设栈与队列初始状态为空。将元素A,B,C,D,E,F,G,H依次轮流入栈和入队,然后依次轮流退队和出栈,则输出序列为______。
7. 设某棵树的度为3,其中度为3,1,0的结点个数分别为3,4,15。则该树中总结点数为______。
10. 循环队列的存储空间为Q(1:60),初始状态为空。经过一系列正常的入队与退队操作后,front=24,rear=25。循环队列中的元素个数为______。
11. 循环队列的存储空间为Q(1:40),初始状态为front=rear=40。经过一系列正常的入队与退队操作后,front=rear=15,此后又退出一个元素,则循环队列中的元素个数为______。
12. 设某棵树的度为3,其中度为3,2,1的结点个数分别为3,0,4。则该树中的叶子结点数为______。
14. 某二叉树的中序遍历序列为CBADE,后序遍历序列为CBADE,则前序遍历序列为______。
15. 树的度为3,且有9个度为3的结点,20个叶子结点,但没有度为1的结点。则该树中度为2的结点数为______。
16. 设线性表的长度为12。最坏情况下冒泡排序需要的比较次数为______。
19. 设某树的度为3,且度为3的结点数为5,度为2的结点数为4,没有度为1的结点。则该树中的叶子结点数为______。
22. 某二叉树中共有350个结点,其中200个为叶子结点,则该二叉树中度为2的结点数为______。
23. 在长度为n的顺序表中查找一个元素,假设需要查找的元素有一半的机会在表中,并且如果元素在表中,则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为______。
24. 要在具有n个元素的有序顺序表中插入一个元素,插入后仍是有序顺序表,则在最坏情况下需要移动的元素个数为______。
25. 设二叉树共有500个结点,其中叶子结点有250个。则度为2的结点个数是______。
26. 假设栈和队列初始状态为空。首先,A,B,C,D依次入栈,X,Y,Z依次入队;然后先将队中元素依次退队,再将栈中元素依次退栈。则退出的所有元素依次为______。
27. 树的度为3,共有31个结点,但没有度为1和2的结点。则该树中度为3的结点数为______。
30. 在长度为97的顺序有序表中作二分查找,最多需要的比较次数为______。
32. 树的度为3,且有9个度为3的结点,5个度为1的结点,但没有度为2的结点。则该树中的叶子结点数为______。
33. 设某树的度为3,且度为3的结点数为4,度为1的结点数为9,没有度为2的结点。则该树中的叶子结点数为______。
34. 下列排序法中,最坏情况下排序速度最快的是______。
35. 在希尔排序法中,每经过一次数据交换后______。
37. 设一棵树的度为3,共有27个结点,其中度为3,2,0的结点数分别为4,1,10。该树中度为1的结点数为______。
39. 设二叉树的前序序列为ABCDEF,中序序列为ABCDEF,则该二叉树的后序序列为______。
40. 设栈与队列初始状态为空。首先A,B,C,D,E依次入栈,再F,G,H,I,J依次入队;然后依次出栈至栈空,再依次出队至队空。则输出序列为______。
42. 要在具有n个元素的有序顺序表中删除一个元素,删除后仍是有序顺序表,则在最坏情况下需要移动的元素个数为______。
43. 设顺序表的长度为16,对该表进行简单插入排序。在最坏情况下需要的比较次数为______。
44. 树的度为3,且有9个度为3的结点,20个叶子结点,但没有度为1的结点。则该树总的结点数为______。
46. 设某树的度为3,且度为3的结点数为4,度为1的结点数为9,没有度为2的结点。则该树中总的结点数为______。
47. 设元素集合为D={1,2,3,4,5,6}。B=(D,R)为线性结构所对应的R是______。
49. 设二叉树的前序序列为ABCDEF,中序序列为BDFECA,则该二叉树的深度为(根结点为第1层)______。
51. 设二叉树的中序序列为BCDA,后序序列为DCBA,则前序序列为______。
54. 在长度为n的顺序表中查找一个元素,假设需要查找的元素一定在表中,并且元素出现在表中每个位置上的可能性是相同的,则在平均情况下需要比较的次数为______。
55. 在带链队列中,经过一系列正常的操作后,如果front=rear,则队列中的元素个数为______。
56. 设表的长度为15。则在最坏情况下,快速排序所需要的比较次数为______。
58. 某二叉树的后序遍历序列与中序遍历序列相同,均为ABCDEF,则前序遍历序列为______。
59. 设非空二叉树的所有子树中,其左子树上的结点值均小于根结点值,而右子树上的结点值均不小于根结点值,则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是______。
60. 设栈与队列初始状态为空。将元素A,B,C,D,E,F,G,H依次轮流入栈和入队,然后依次轮流退队和出栈,则输出序列为______。
61. 某二叉树共有400个结点,其中有100个度为1的结点,则该二叉树中的叶子结点数为______。
62. 设二叉树的前序序列为ABCDEF,中序序列为ABCDEF,则该二叉树的深度为(根结点为第1层)______。
65. 下列各组算法中,最坏情况下其时间复杂度相同的是______。
66. 设循环队列的存储空间为Q(1:100),初始状态为空。现经过一系列正常操作后,front=49,则循环队列中的元素个数为______。
67. 设栈与队列初始状态为空。首先A,B,C,D,E依次入栈,再F,G,H,I,J依次入队;然后依次出队至队空,再依次出栈至栈空。则输出序列为______。
68. 设栈与队列初始状态为空。将元素A,B,C,D,E,F,G,H依次轮流入栈和入队,然后依次轮流出栈和退队,则输出序列为______。
69. 在长度为n的顺序表中寻找最大项,需要比较的次数至少是______。
71. 循环队列的存储空间为Q(1:50)。经过一系列正常的入队与退队操作后,front=rear=25。后又成功地将一个元素入队,此时队列中的元素个数为______。
72. 某完全二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH。该完全二叉树的前序序列为______。
73. 循环队列的存储空间为Q(1:50),初始状态为空。经过一系列正常的入队与退队操作后,front=1,rear=25。此时该循环队列中的元素个数为______。
74. 假设栈和队列初始状态为空。首先,A,B,C,D依次入栈,X,Y,Z依次入队;然后先将栈中元素依次退栈,再将队中元素依次退队。则退出的所有元素依次为______。
76. 设顺序表的长度为n。下列排序方法中,最坏情况下比较次数小于n(n-1)/2的是______。
77. 某二叉树有49个度为2的结点,4个度为1的结点,则______。
78. 设顺序表的长度为n。下列算法中,最坏情况下比较次数小于n的是______。
79. 设二叉树的后序序列为DGHEBIJFCA,中序序列为DBGEHACIFJ。则前序序列为______。
81. 在快速排序法中,每经过一次数据交换(或移动)后______。
82. 在具有2n个结点的完全二叉树中,叶子结点个数为______。
83. 某带链栈的初始状态为top=bottom=NULL,经过一系列正常的入栈与退栈操作后,top=bottom=20。该栈中的元素个数为______。
84. 设顺序表的长度为40,对该表进行冒泡排序。在最坏情况下需要的比较次数为______。
85. 设循环队列的存储空间为Q(1: m),初始状态为 front=rear=m。经过一系列正常的操作后,front=1,rear=m。为了在该队列中寻找值最大的元素,在最坏情况下需要的比较次数为______。
86. 某二叉树的前序遍历序列与中序遍历序列相同,均为ABCDEF,则按层次输出(同一层从左到右)的序列为______。
87. 下列各组算法中,最坏情况下其时间复杂度不同的是______。
88. 某二叉树的前序序列为ABDECFG,中序序列为DBEAFCG,则后序序列为______。
90. 某完全二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH。该完全二叉树的中序序列为______。
91. 度为3的一棵树共有30个结点,其中度为3、1的结点个数分别为3、4。则该树中的叶子结点数为______。
93. 从表中任何一个结点位置出发就可以不重复地访问到表中其他所有结点的链表是______。
94. 设数据结构B=(D, R),其中D={ a, b, c, d, e, f } ,R={ (f, a),(d, b), (e, d), (c, e), (a, c) } ,该数据结构为______。
95. 设栈与队列初始状态为空。将元素A,B,C,D,E,F,G,H依次轮流入队和入栈,然后依次轮流退队和出栈,则输出序列为______。
96. 循环队列的存储空间为Q(1:50),初始状态为空。经过一系列正常的入队与退队操作后,front=24,rear=25。此时该循环队列中的元素个数为______。
97. 设一棵树的度为3,其中度为3,2,1的结点个数分别为4,1,3。则该棵树中的叶子结点数为______。
98. 设二叉树共有375个结点,其中度为2的结点有187个。则度为1的结点个数是______。
101. 某二叉树的前序遍历序列与中序遍历序列相同,均为ABCDEF,则后序遍历序列为______。
102. 循环队列的存储空间为Q(1:50),初始状态为front=rear=50。经过一系列正常的入队与退队操作后,front=rear=25,此后又插入一个元素,则循环队列中的元素个数为______。
103. 某带链栈的初始状态为 top=bottom=NULL,经过一系列正常的入栈与退栈操作后,top=10,bottom=20。该栈中的元素个数为______。
105. 设二叉树的前序序列为ABCDEF,中序序列为BDFECA,则该二叉树的后序序列为______。
106. 设顺序表的长度为n。下列算法中,最坏情况下比较次数等于n(n-1)/2的是______。
107. 设栈的顺序存储空间为S(1:m),初始状态为top=-1,则栈中的数据元素个数为______。
109. 某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后,front=10, rear=5。该队列中的元素个数为______。
110. 某二叉树的中序遍历序列为 CBADE ,后序遍历序列为 CBEDA ,则前序遍历序列为______。
113. 某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后,front=rear=10。该队列中的元素个数为______。
114. 对长度为8的数组进行快速排序,最多需要的比较次数为______。
116. 下列结构中为非线性结构的是______。
117. 线性表的长度为n。在最坏情况下,比较次数为n-1的算法是______。
118. 树的度为3,且有9个度为3的结点,5个度为1的结点,但没有度为2的结点。则该树总的结点数为______。
119. 一个栈的初始状态为空。现将元素1,2,3,A,B,C依次入栈,然后再依次出栈,则元素出栈的顺序是______。
120. 设栈的顺序存储空间为S(1:m),初始状态为top=m+1。现经过一系列正常的入栈与退栈运算后,top=20,则栈中的元素个数为______。
122. 设数据结构B=(D, R),其中:D={ a, b, c, d, e, f };R={ (a, b), (b, c), (c, d), (d, e), (e, f), (f, a) },该数据结构为______。
124. 设栈的存储空间为S(1:60),初始状态为top=61。现经过一系列正常的入栈与退栈操作后,top=25,则栈中的元素个数为______。
125. 循环队列的存储空间为Q(0:59),初始状态为空。经过一系列正常的入队与退队操作后,front=25,rear=24。循环队列中的元素个数为______。
126. 设一棵度为3的树,其中度为2,1,0的结点数分别为3,4,15。则该树中总结点数为______。
127. 设二叉树的前序序列为ABDEGHCFIJ,中序序列为DBGEHACIFJ。则按层次输出(从上到下,同一层从左到右)的序列为______。
128. 循环队列的存储空间为Q(1:50),初始状态为空。经过一系列正常的入队与退队操作后,front=25,rear=25。此时该循环队列中的元素个数为______。
129. 某二叉树有49个度为2的结点,4个度为1的结点,30个叶子结点,则______。
131. 设栈的顺序存储空间为 S(1:m),初始状态为top=0,则栈中的数据元素个数为______。
133. 设表的长度为n。在下列算法中,最坏情况下时间复杂度最高的是______。
135. 设有一个栈与一个队列的初始状态均为空。现有一个序列A,B,C,D,E,F,G,H。先分别将序列中的前4个元素依次入栈,后4个元素依次入队;然后分别将栈中的元素依次退栈,再将队列中的元素依次退队。最后得到的序列为______。
138. 某二叉树的前序序列为ABDFHCEG,中序序列为HFDBACEG。该二叉树按层次输出(同一层从左到右)的序列为______。
139. 循环队列的存储空间为Q(1:100),初始状态为front=rear=100。经过一系列正常的入队与退队操作后,front=rear=99,则循环队列中的元素个数为______。
142. 设数据集合为D={1,2,3,4,5},下列数据结构B=(D,R)中为非线性结构的是______。
143. 某二叉树的前序序列为ABDFHCEG,中序序列为HFDBACEG。该二叉树的后序序列为______。
144. 设栈的存储空间为S(1:60),初始状态为top=61。现经过一系列正常的入栈与退栈操作后,top=1,则栈中的元素个数为______。
145. 设栈的顺序存储空间为 S(1:m),初始状态为top=m+1,则栈中的数据元素个数为______。
146. 设表的长度为20。则在最坏情况下,冒泡排序的比较次数为______。
148. 下列算法中,最坏情况下时间复杂度最低的是______。
149. 下列结构中属于线性结构链式存储的是______。
150. 设栈的存储空间为S(1:50),初始状态为top=0。现经过一系列正常的入栈与退栈操作后,top=51,则栈中的元素个数为______。
151. 某二叉树共有400个结点,其中有99个度为1的结点,则该二叉树中的叶子结点数为______。
153. 设某树的度为3,且度为3的结点数为5,度为1的结点数为6,没有度为2的结点。则该树中的叶子结点数为______。
154. 下列排序法中,每经过一次元素的交换会产生新的逆序的是______。
155. 设表的长度为n。在下列结构所对应的算法中,最坏情况下时间复杂度最低的是______。
156. 树的度为3,共有29个结点,但没有度为1和2的结点。则该树中叶子结点数为______。
157. 设循环队列的存储空间为Q(1:50),初始状态为front=rear=50。经过一系列正常的操作后,front-1=rear。为了在该队列中寻找值最大的元素,在最坏情况下需要的比较次数为______。
158. 设二叉树中有20个叶子结点,5个度为1的结点,则该二叉树中总的结点数为______。
159. 下列数据结构中,不能采用顺序存储结构的是______。
160. 一棵二叉树中共有80个叶子结点与70个度为1的结点,则该二叉树中的总结点数为______。
162. 设某树的度为3,且度为3的结点数为5,度为2的结点数为4,没有度为1的结点。则该树中总的结点数为______。
164. 设表的长度为n。下列查找算法中,在最坏情况下,比较次数最少的是______。
165. 设一棵树的度为3,其中没有度为2的结点,且叶子结点数为6。该树中度为3的结点数为______。
166. 某二叉树共有399个结点,其中有199个度为2的结点,则该二叉树中的叶子结点数为______。
169. 在带链栈中,经过一系列正常的操作后,如果top=bottom,则栈中的元素个数为______。
171. 某二叉树的后序序列为DEBFGCA,中序序列为DBEAFCG,则前序序列为______。
172. 设二叉树的前序序列为ABDEGHCFIJ,中序序列为DBGEHACIFJ。则后序序列为______。
173. 下列排序方法中,最坏情况下时间复杂度(即比较次数)最低的是______。
175. 设数据集合为D={1,2,3,4,5,6},下列数据结构B=(D,R)中为线性结构的是______。
176. 下列算法中均以比较作为基本运算,则平均情况与最坏情况下的时间复杂度相同的是______。
177. 在具有n个结点的二叉树中,如果各结点值互不相同,但前序遍历序列与中序遍历序列相同,则该二叉树的深度为(根结点在第1层)______。
178. 某二叉树的后序遍历序列与中序遍历序列相同,均为ABCDEF,则按层次输出(同一层从左到右)的序列为______。