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

本套试题共50题。

1. 班级：

格式如“19计应31”

2. 学号：

10位数完整格式

3. 姓名：

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

5. 数据的存储结构是指______。

6. [(4)堆排序法：堆排序的方法为：①首先将一个无序序列建成堆。②然后将堆顶元素(序列中的最大项)与堆中最后一个元素交换(最大项应该在序列的最后)。堆排序在最坏的情况下，其时间复杂度为O(nlogn)。]

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

8. 下列关于栈的描述正确的是______。

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

10. 堆排序最坏情况下的时间复杂度为______。

11. n个顶点的强连通图的边数至少有______。

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

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

14. 下列数据结构中，属于非线性结构的是______。

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

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

17. 一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为______。

18. 在计算机中，算法是指______。

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

20. 在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数______。

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

22. 按照"后进先出"原则组织数据的数据结构是______。

23. 设循环队列为Q(1:m)，初始状态为front=rear=m。现经一系列入队与退队操作后，front=rear=m-1，则______。

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

25. [(4)堆排序法：堆排序的方法为：①首先将一个无序序列建成堆。②然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。堆排序在最坏的情况下，其时间复杂度为O(nlog2n)。]

26. 下列排序方法中，最坏情况下比较次数最少的是______。

27. 下列关于二叉树的叙述中，正确的是______。

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

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

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

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

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

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

34. 设非空二叉树的所有子树中，其左子树上的结点值均小于根结点值，而右子树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是______。

35. 设一棵树的度为3，其中没有度为2的结点，且叶子结点数为6。该树中度为3的结点数为______。

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

37. 从表中任何一个结点位置出发就可以不重复地访问到表中其他所有结点的链表是______。

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

39. 要在具有n个元素的有序顺序表中删除一个元素，删除后仍是有序顺序表，则在最坏情况下需要移动的元素个数为______。

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

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

42. 某二叉树的后序遍历序列与中序遍历序列相同，均为ABCDEF，则按层次输出（同一层从左到右）的序列为______。

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

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

45. 假设栈和队列初始状态为空。首先，A,B,C,D依次入栈，X,Y,Z依次入队；然后先将队中元素依次退队，再将栈中元素依次退栈。则退出的所有元素依次为______。

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

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

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

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

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

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

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

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

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

消息

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