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

本套试题共50题。

1. 班级:

格式如“19计应31”

2. 学号:

10位数完整格式

3. 姓名:

4. 在最坏情况下______。

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

6. 深度为5的完全二叉树的结点数不可能是______。

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

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

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

10. [(2)希尔排序:将整个无序序列分割成若干小的子序列分别进行插入排序。在最坏情况下,希尔排序所需的比较次数为O(n1.5)。]

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

12. 下面叙述正确的是______。

13. 某二叉树共有530个结点,其中度为2的结点有250个,则度为1的结点数为______。

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

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

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

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

18. 某二叉树共有845个结点,其中叶子结点有45个,则度为1的结点数为______。

19. 下列各排序法中,最坏情况下的时间复杂度最低的是______。

20. 算法的有穷性是指______。

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

22. [假设线性表的长度为n,则在最坏情况下,冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描,需要的比较次数为n(n-1)/2。快速排序法也是一种互换类的排序方法,但由于它比冒泡排序法的速度快,因此称之为快速排序法。冒泡排序法与快速排序法本质上都是通过数据元素的交换来逐步消除线性表中的逆序。]

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

24. 以下数据结构中不属于线性数据结构的是______。

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

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

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

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

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

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

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

32. 在具有2n个结点的完全二叉树中,叶子结点个数为______。

33. 设栈与队列初始状态为空。首先A,B,C,D,E依次入栈,再F,G,H,I,J依次入队;然后依次出队至队空,再依次出栈至栈空。则输出序列为______。

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

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

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

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

38. 设栈的顺序存储空间为 S(1:m),初始状态为top=m+1,则栈中的数据元素个数为______。

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

40. 某二叉树有49个度为2的结点,4个度为1的结点,30个叶子结点,则______。

41. 设顺序表的长度为n。下列算法中,最坏情况下比较次数小于n的是______。

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

43. 下列排序法中,每经过一次元素的交换会产生新的逆序的是______。

44. 下列算法中,最坏情况下时间复杂度最低的是______。

45. 某二叉树的后序遍历序列与中序遍历序列相同,均为ABCDEF,则按层次输出(同一层从左到右)的序列为______。

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

47. 某带链栈的初始状态为top=bottom=NULL,经过一系列正常的入栈与退栈操作后,top=bottom=20。该栈中的元素个数为______。

48. 设二叉树的前序序列为ABDEGHCFIJ,中序序列为DBGEHACIFJ。则按层次输出(从上到下,同一层从左到右)的序列为______。

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

50. 某系统结构图如下图所示(n≥5),该系统结构图的最大扇出数是______。

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

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

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

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

消息

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