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

本套试题共50题。

1. 班级：

格式如“19计应31”

2. 学号：

10位数完整格式

3. 姓名：

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

5. 下列关于栈的叙述正确的是______。

6. 设序列长度为n，在最坏情况下比较次数低于O(n2)的排序方法是______。

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

8. 设循环队列为Q(1:m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=20，rear=15。现要在该循环队列中寻找最小值的元素，最坏情况下需要比较的次数为______。

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

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

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

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

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

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

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

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

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

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

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

20. 下列处理中与队列有关的是______。

21. 在深度为5的满二叉树中，叶子结点的个数为______。

22. 下列各组排序法中，最坏情况下比较次数相同的是______。

23. 下列链表中，其逻辑结构属于非线性结构的是______。

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

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

26. 在下列几种排序方法中，要求内存量最大的是______。

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

28. 算法的空间复杂度是指______。

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

30. 某二叉树的后序遍历序列与中序遍历序列相同，均为ABCDEF，则前序遍历序列为______。

31. 设顺序表的长度为n。下列算法中，最坏情况下比较次数等于n(n-1)/2的是______。

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

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

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

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

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

37. 度为3的一棵树共有30个结点，其中度为3、1的结点个数分别为3、4。则该树中的叶子结点数为______。

38. 设顺序表的长度为16，对该表进行简单插入排序。在最坏情况下需要的比较次数为______。

39. 某二叉树的前序序列为ABDFHCEG，中序序列为HFDBACEG。该二叉树的后序序列为______。

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

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

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

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

44. 下列排序方法中，最坏情况下时间复杂度（即比较次数）最低的是______。

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

46. 树的度为3，且有9个度为3的结点，5个度为1的结点，但没有度为2的结点。则该树总的结点数为______。

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

48. 设栈与队列初始状态为空。将元素A,B,C,D,E,F,G,H依次轮流入栈和入队，然后依次轮流退队和出栈，则输出序列为______。

49. 对下列二叉树进行前序遍历的结果为______。

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

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

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

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

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

消息

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