全国二级理论——1.2数据结构与算法

本套试题共50题。

1. 班级：

格式如“19计应31”

2. 学号：

10位数完整格式

3. 姓名：

4. 栈和队列的共同点是______。

5. [（4）堆排序法：堆排序的方法为：①首先将一个无序序列建成堆。②然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。在最坏情况下，堆排序需要比较的次数为O(nlog2n)。]

6. 设循环队列的存储空间为Q(1:35)，初始状态为front=rear=35。现经过一系列入队与退队运算后，front=15，rear=15，则循环队列中的元素个数为______。

7. 下列叙述中正确的是______。

8. 对于循环队列，下列叙述中正确的是______。

9. 设数据元素的集合D={1,2,3,4,5}，则满足下列关系R的数据结构中为线性结构的是______。

10. 下列与队列结构有关联的是______。

11. 下列叙述中正确的是______。

12. 设某二叉树的后序序列为CBA，中序序列为ABC，则该二叉树的前序序列为______。

13. [堆排序属于选择类的排序方法。堆排序方法如下：首先将一个无序序列建成堆。然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。不考虑已经换到最后的那个元素，指考虑前n-1个元素构成的子序列，显然，该子序列已不是堆，但左、右子树仍为堆，可以将该子序列调整为堆。在最坏情况下，堆排序需要比较的次数为O(nlog2n)。]

14. 在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是______。

15. 深度为7的二叉树共有127个结点，则下列说法中错误的是______。

16. 下列叙述中错误的是______。

17. 算法时间复杂度的度量方法是______。

18. [所谓简单插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。在简单插入排序中，每一次比较后最多移掉一个逆序，因此，这种排序方法的效率与冒泡排序法相同。在最坏情况下，简单插入排序需要n(n-1)/2次比较。]

19. 某二叉树共有12个结点，其中叶子结点只有1个。则该二叉树的深度为（根结点在第1层）______。

20. 下列叙述中正确的是______。

21. 对长度为n的线性表排序，在最坏情况下，比较次数不是n(n-1)/2的排序方法是______。

22. 设有序线性表的长度为n，则在有序线性表中进行二分查找，最坏情况下的比较次数为______。

23. [希尔排序法属于插入类排序，但它对简单插入排序做了较大的改进。基本思想是：将整个无序序列分割成若干小的子序列分别进行插入排序。在希尔排序过程中，虽然对于每一个子表采用的仍是插入排序，但是，在子表中每进行一次比较久有可能移去整个线性表中的多个逆序，从而改善了整个排序过程的性能。最欢情况下，希尔排序所需要的比较次数为O(n1.5)。]

24. [(3)快速排序：通常，快速排序被认为是，所有同数量级(O(nlogn))的排序方法中，其平均性能最好。但是，若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。]

25. 在下列选项中，哪个不是一个算法一般应该具有的基本特征______。

26. 设循环队列的存储空间为Q(1:m)，初始状态为空。现经过一系列正常的入队与退队操作后，front=m-1，rear=m，此后再向该循环队列中插入一个元素，则队列中的元素个数为______。

27. 在一棵二叉树上第5层的结点数最多是______。

28. 下列关于线性链表的叙述中，正确的是______。

29. 下列叙述中正确的是______。

30. 下列叙述中错误的是______。

31. 某二叉树的中序遍历序列为CBADE，后序遍历序列为CBADE，则前序遍历序列为______。

32. 在长度为n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中,则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为______。

33. 设栈的存储空间为S(1:50)，初始状态为top=0。现经过一系列正常的入栈与退栈操作后，top=51，则栈中的元素个数为______。

34. 设栈的顺序存储空间为S(1:m)，初始状态为top=m+1。现经过一系列正常的入栈与退栈运算后，top=20，则栈中的元素个数为______。

35. 某二叉树的前序序列为ABDFHCEG，中序序列为HFDBACEG。该二叉树按层次输出（同一层从左到右）的序列为______。

36. 某完全二叉树按层次输出（同一层从左到右）的序列为ABCDEFGH。该完全二叉树的中序序列为______。

37. 下列叙述中错误的是______。

38. 在带链队列中，经过一系列正常的操作后，如果front=rear，则队列中的元素个数为______。

39. 下列叙述中正确的是______。

40. 某二叉树共有399个结点，其中有199个度为2的结点，则该二叉树中的叶子结点数为______。

41. 设数据结构B=(D, R)，其中D={ a, b, c, d, e, f } ，R={ (f, a),(d, b), (e, d), (c, e), (a, c) } ，该数据结构为______。

42. 设循环队列的存储空间为Q(1:50)，初始状态为front=rear=50。经过一系列正常的操作后，front-1=rear。为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为______。

43. 在长度为n的顺序表中寻找最大项，需要比较的次数至少是______。

44. 下列算法中，最坏情况下时间复杂度最低的是______。

45. 树的度为3，且有9个度为3的结点，20个叶子结点，但没有度为1的结点。则该树总的结点数为______。

46. 下列叙述中正确的是______。

47. 循环队列的存储空间为Q(1:50)，初始状态为空。经过一系列正常的入队与退队操作后，front=1,rear=25。此时该循环队列中的元素个数为______。

48. 设栈的存储空间为S(1:60)，初始状态为top=61。现经过一系列正常的入栈与退栈操作后，top=1，则栈中的元素个数为______。

49. 设有下列二叉树，此二叉树中序遍历的结果为______。

50. 某系统总体结构如下图所示，该系统结构图的最大扇出数是______。

51. 某系统总体结构图如下图所示，该系统总体结构图的深度是______。

52. 设二叉树如下，则中序序列为______。

53. 某系统结构图如下图所示，该系统结构图的深度是______。

    
/ 完成题数 当前页码
0%
完成进度
{0}:{1} 剩余时间
{0}:{1} 当前用时
提交成功！

消息

正在处理中，请稍候...