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

本套试题共50题。

1. 班级:

格式如“19计应31”

2. 学号:

10位数完整格式

3. 姓名:

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

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

6. 在单链表中,增加头结点的目的是______。

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

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

9. 某二叉树的前序序列为ABCDEFG,中序序列为DCBAEFG,则该二叉树的后序序列为______。

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

11. [希尔排序法属于插入类排序,但它对简单插入排序做了较大的改进。基本思想是:将整个无序序列分割成若干小的子序列分别进行插入排序。在希尔排序过程中,虽然对于每一个子表采用的仍是插入排序,但是,在子表中每进行一次比较久有可能移去整个线性表中的多个逆序,从而改善了整个排序过程的性能。最欢情况下,希尔排序所需要的比较次数为O(n1.5)。]

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

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

14. 某二叉树的前序遍历序列为 ABCDE ,中序遍历序列为 CBADE ,则后序遍历序列为______。

15. 算法的时间复杂度是指______。

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

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

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

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

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

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

22. [(2) 快速排序:通常,快速排序被认为是,所有同数量级(O(nlogn))的排序方法中,其平均性能最好。但是,若初始记录序列按关键字有序或基本有序时,快速排序将蜕化为起泡排序,其时间复杂度为O(n2)。]

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

24. 下列算法中,最坏情况下时间复杂度为O(log2n)的是______。

25. 某棵树中共有25个结点,且只有度为3的结点和叶子结点,其中叶子结点有7个,则该树中度为3的结点数为______。

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

27. 下列关于线性链表的叙述中,正确的是______。

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

29. 下列排序方法中,最坏情况下时间复杂度(即比较次数)低于O(n2)的是______。

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

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

32. 某二叉树的中序遍历序列为CBADE,后序遍历序列为CBADE,则前序遍历序列为______。

33. 带链栈空的条件是______。

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

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

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

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

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

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

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

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

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

43. 设元素集合为D={1,2,3,4,5,6}。B=(D,R)为线性结构所对应的R是______。

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

45. 设二叉树的前序序列为ABCDEF,中序序列为ABCDEF,则该二叉树的后序序列为______。

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

47. 设二叉树的前序序列为ABCDEF,中序序列为BDFECA,则该二叉树的后序序列为______。

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

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

50. 设二叉树如下,则前序序列为______。

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

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

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

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

消息

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