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

本套试题共50题。

1. 班级：

格式如“19计应31”

2. 学号：

10位数完整格式

3. 姓名：

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

5. 设栈的顺序存储空间为S(0:49)，栈底指针bottom=49，栈顶指针top=30（指向栈顶元素）。则栈中的元素个数为______。

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

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

8. [(1)冒泡排序法：是一种最简单的交换类排序法，它是通过相邻数据元素的交换逐步将线性表变成有序。假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要比较的次数为n(n-1)/2次。因此冒泡排序总的时间复杂度为O(n2)。]

9. 设有栈S和队列Q，初始状态均为空。首先依次将A,B,C,D,E,F入栈，然后从栈中退出三个元素依次入队，再将X,Y,Z入栈后，将栈中所有元素退出并依次入队，最后将队列中所有元素退出，则退队元素的顺序为______。

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

11. 对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是______。

12. 循环队列的存储空间为Q(1:50)。经过一系列正常的入队与退队操作后，front=rear=25。后又成功地将一个元素退队，此时队列中的元素个数为______。

13. 下列序列中不满足堆条件的是______。

14. [假设线性表的长度为16，那么冒泡排序、直接插入排序、简单选择排序都需要比较120次，而堆排序需要比较64次。]

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

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

17. 对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为______。

18. 算法分析的目的是______。

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

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

21. 某二叉树的前序序列为ABCD，中序序列为DCBA，则后序序列为______。

22. 一棵完全二叉树共有360个结点，则在该二叉树中度为1的结点个数为______。

23. 设二叉树的中序序列为BCDA，前序序列为ABCD，则后序序列为______。

24. [(1)冒泡排序法：是一种最简单的交换类排序法，它是通过相邻数据元素的交换逐步将线性表变成有序。假设线性表的长度为n，若初始序列为"正序"序列，则只需进行一趟排序，在排序过程中进行n-1次关键字间的比较，且不移动记录；反之，若初始序列为"逆序"序列，则需进行n-1趟排序，需进行n(n-1)/2次比较，并作等数量级的记录移动。因此冒泡排序总的时间复杂度为O(n2)。]

25. 支持子程序调用的数据结构是______。

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

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

28. 下列关于算法的描述中错误的是______。

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

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

31. 设一棵树的度为3，其中度为3，2，1的结点个数分别为4，1，3。则该棵树中的叶子结点数为______。

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

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

34. 设循环队列的存储空间为Q(1:100)，初始状态为空。现经过一系列正常操作后，front=49，则循环队列中的元素个数为______。

35. 带链队列空的条件是______。

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

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

38. 在希尔排序法中，每经过一次数据交换后______。

39. 设一棵度为3的树，其中度为2，1，0的结点数分别为3，4，15。则该树中总结点数为______。

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

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

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

43. 设二叉树的前序序列为ABDEGHCFIJ，中序序列为DBGEHACIFJ。则按层次输出（从上到下，同一层从左到右）的序列为______。

44. 设二叉树的后序序列为DGHEBIJFCA，中序序列为DBGEHACIFJ。则前序序列为______。

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

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

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

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

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

50. 对如下二叉树进行后序遍历的结果为______。

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

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

53. 某系统结构图如下图所示（n≥5），该系统结构图的最大扇出数是______。

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

消息

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