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

本套试题共50题。

1. 班级：

格式如“19计应31”

2. 学号：

10位数完整格式

3. 姓名：

4. 在深度为7的满二叉树中，度为2的结点个数为______。

5. [（3）简单选择排序法：对于长度为n的序列，选择排序需要扫描n-1遍，每一遍扫描均从剩下的子表中选出最小的元素，然后将该最小的元素与子表中的第一个元素进行交换。简单选择排序法在最坏情况下需要比较n(n-1)/2次。]

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

7. 设二叉树中共有31个结点，其中的结点值互不相同。如果该二叉树的后序序列与中序序列相同，则该二叉树的深度为______。

8. 设某二叉树的后序序列与中序序列均为ABCDEFGH，则该二叉树的前序序列为______。

9. 某二叉树的前序序列为ABCDEFG，中序序列为DCBAEFG，则该二叉树的深度（根结点在第1层）为______。

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

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

12. 下列数据结构中为非线性结构的是______。

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

14. 某循环队列的存储空间为Q(1:m)，初始状态为front=rear=m。现经过一系列的入队操作和退队操作后，front=m-1，rear=m，则该循环队列中的元素个数为______。

15. [（2）简单插入排序法：在简单插入排序法中，每一次比较后最多移掉一个逆序，因此，这种排序方法的效率与冒泡排序法相同。在最坏情况下，简单插入排序需要n(n-1)/2次比较。]

16. 对长度为n的线性表作快速排序，在最坏情况下，比较次数为______。

17. 下列各序列中不是堆的是______。

18. 某二叉树共有845个结点，其中叶子结点有45个，则度为1的结点数为______。

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

20. [假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-1)/2。快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。冒泡排序法与快速排序法本质上都是通过数据元素的交换来逐步消除线性表中的逆序。]

21. 若某二叉树中的所有结点值均大于其左子树上的所有结点值，且小于右子树上的所有结点值，则该二叉树遍历序列中有序的是______。

22. 某二叉树的中序序列为DCBAEFG，后序序列为DCBGFEA，则该二叉树的深度（根结点在第1层）为______。

23. 某循环队列的存储空间为Q(1:m)，初始状态为front=rear=m。现经过一系列的入队操作和退队操作后，front=m，rear=m-1，则该循环队列中的元素个数为______。

24. [(3)希尔排序：将整个无序序列分割成若干小的子序列分别进行插入排序。在最坏情况下，希尔排序所需的比较次数为O(n1.5)。]

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

26. 下列关于算法复杂度叙述正确的是______。

27. 某二叉树共有13个结点，其中有4个度为1的结点，则叶子结点数为______。

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

29. 设数据集合为D={1,2,3,4,5,6}，下列数据结构B=(D,R)中为线性结构的是______。

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

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

32. 在具有2n个结点的完全二叉树中，叶子结点个数为______。

33. 某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后，front=rear=10。该队列中的元素个数为______。

34. 设表的长度为15。则在最坏情况下，快速排序所需要的比较次数为______。

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

36. 下列结构中属于线性结构链式存储的是______。

37. 设一棵树的度为3，共有27个结点，其中度为3，2，0的结点数分别为4，1，10。该树中度为1的结点数为______。

38. 设二叉树共有500个结点，其中叶子结点有250个。则度为2的结点个数是______。

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

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

41. 循环队列的存储空间为Q(0:59)，初始状态为空。经过一系列正常的入队与退队操作后，front=25，rear=24。循环队列中的元素个数为______。

42. 设某树的度为3，且度为3的结点数为5，度为2的结点数为4，没有度为1的结点。则该树中的叶子结点数为______。

43. 设栈与队列初始状态为空。首先A,B,C,D,E依次入栈，再F,G,H,I,J依次入队；然后依次出栈至栈空，再依次出队至队空。则输出序列为______。

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

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

46. 下列各组算法中，最坏情况下其时间复杂度不同的是______。

47. 设某树的度为3，且度为3的结点数为4，度为1的结点数为9，没有度为2的结点。则该树中的叶子结点数为______。

48. 设二叉树的前序序列为ABCDEF，中序序列为ABCDEF，则该二叉树的深度为（根结点为第1层）______。

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

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

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

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

53. 对下列二叉树进行中序遍历的结果是______。

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

消息

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