全国二级理论——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} 当前用时
提交成功!

消息

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