2024年1月4日发(作者：)

数据结构试卷(四)

一、 选择题（每题2分，共20分）

1. 设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为( C )。

A. O(n)

B. O(nlog2n)

C. O(1)

2D. O(n)

2. 设一棵二叉树的深度为k，则该二叉树中最多有( D )个结点。

A. 2k-1

k

B. 2k-1

C. 2kD. 2-1

3. 设某无向图中有n个顶点、e条边，则该无向图中所有顶点的入度之和为( D )。

A. n

B. e

C. 2n

D. 2e

4. 在二叉排序树中插入一个结点的时间复杂度为( C )。

A. O(1)

B. O(n)

C. O(log2n)

2D. O(n)

5. 设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有( C )条有向边。

A. n

B. n-1

C. m

D. m-1

6. 设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行( A )趟的分配和回收才能使初始关键字序列变成有序序列。

A. 3

B. 4

C. 5

D. 8

7. 设用链表作为栈的存储结构，则退栈操作( B )。

A. 必须判别栈是否为满

B. 必须判别栈是否为空

C. 判别栈元素的类型

D. 对栈不做任何判别

8. 下列4种排序中( D )的空间复杂度最大。

A. 快速排序

B. 冒泡排序

C. 希尔排序

D. 堆

9. 设某二叉树中度数为0的结点数为N0，度数为1的结点数为N1，度数为2的结点数为N2，则下列等式成立的是( C )。

A. N0=N1+1

B. N0=N1+N2

C. N0=N2+1

D. N0=2N1+1

10. 设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过( A )。

A. log2n+1

B. log2n-1

C. log2n

D. log2(n+1)

二、 填空题（除第2题2分外每空1分，共20分）

21. 设有n个无序的记录关键字，则直接插入排序的时间复杂度为 O(n) ，快速排序的平均时间复杂度为 O(nlog2n) 。

2. 设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为

p->llink->rlink = p->rlink; p->rlink->llink = p->llink; (设结点中的两个指针域分别为llink和rlink)。

3. 根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为 3 。

k-14. 深度为k的完全二叉树中最少有 2 个结点。

5. 设初始记录关键字序列为(K1，K2，…，Kn)，则用筛选法思想建堆必须从 [n/2] 第个元素开始进行筛选。

6. 设哈夫曼树中共有99个结点，则该树中有 50 个叶子结点；若采用二叉链表作为存储结构，则该树中有 100 个空指针域。

7. 设一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储 M-1 个队列元素； 当前实际存储 (R – F + M) % M 个队列元素(设头指针F指向当前队头元素的前一个位置，尾指针R指向当前队尾元素的位置)。

8. 设顺序线性表中有n个数据元素，则在第i个位置上插入一个数据元素需要移动表中的

n- i + 1 个数据元素； 删除第i个位置上的数据元素需要移动表中的 n – i 个元素。

9. 设一组初始记录关键字序列为(20，18，22，16，30，19)，则以20为中轴的一趟快速排序的结果为 (18, 16, 19, 20, 22, 30) 。

10. 设一组初始记录关键字序列为(20，18，22，16，30，19)，则根据这些初始关键字序列建成的初始堆为 (16, 18, 19, 20, 30, 22) 。

11. 设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j互为邻接点的条件是 A[i][j]=A[j][i]=1 。

12. 设无向图对应的邻接矩阵为A，则A中第i行上非0元素的个数 等于 第i列上非0元素的个数(填等于、大于或小于)。

13. 设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该二叉树的序列为 BDCA 。

14. 设散列函数H(k)=k mod p，解决冲突的方法为链地址法。要求在下列算法画线处填上正确的语句完成在散列表hashtalbe中查找关键字值等于k的结点，成功时返回指向关键字的指针，不成功时返回标志0。

1 class Node(object):

2 def __init__(self,key=None,next=None):

3 = key

4 = next

5

6 def createlkHash(hashTable):

7 for i in range(m):

8 hashTable[i] = 0

9 for i in range(n):

10 s = Node()

11 = a[i]

12 k = a[i] % P

13 = hashTable[k]

14 hashTable[k] = s

三、 计算题(每题10分，共30分)

1. 画出广义表LS=(( ),(e),(a,(b,c,d)))的头尾链表存储结构。

2. 设有如图A.6所示的森林：

(1) 求树(a)的先根序列和后根序列；

ABCDEF

BDEFCA

(2) 求森林的先序序列和中序序列；

ABCDEFGHIJK

BDEFCAIJKHG

(3) 将此森林转换为相应的二叉树。

图A.6森林图

3. 设散列表的地址范围是[ 0..9 ]，散列函数为H(key)= (key2+2)mod 9,并采用链表处理冲突，请画出元素7、4、5、3、6、2、8、9依次插入散列表的存储结构。

四、 算法设计题(每题10分，共30分)

1. 设单链表中仅有3类字符的数据元素(大写字母、数字和其他字符)，要求利用原单链表

中的结点空间设计出3个单链表的算法，使每个单链表只包含同类字符。

1. import random

2. import string

3.

4.

5. class Node:

6. def __init__(self, data=None, nxt=None):

7. = data

8. = nxt

9.

10.

11. def print_list(head):

12. list_data = []

13. while head is not None:

14. list_()

15. head =

16. print(list_data)

17.

18.

19. head_all = None

20. tail_all = None

21. for _ in range(20):

22. node = Node(([

23. (_uppercase),

24. (),

25. (list(set(ble) - set(_uppercase) - set())),

26. ]))

27. if tail_all is None:

28. head_all = tail_all = node

29. else:

30. tail_ = node

31. tail_all = node

32. print('all: ', end='')

33. print_list(head_all)

34.

35. head_upper = None

36. tail_upper = None

37. head_digit = None

38. tail_digit = None

39. head_other = None

40. tail_other = None

41. while head_all is not None:

42. node = head_all

43. head_all =

44. = None

45. if r():

46. if tail_upper is None:

47. head_upper = tail_upper = node

48. else:

49. tail_ = node

50. tail_upper = node

51. elif t():

52. if tail_digit is None:

53. head_digit = tail_digit = node

54. else:

55. tail_ = node

56. tail_digit = node

57. else:

58. if tail_other is None:

59. head_other = tail_other = node

60. else:

61. tail_ = node

62. tail_other = node

63. print('upper: ', end='')

64. print_list(head_upper)

65. print('digit: ', end='')

66. print_list(head_digit)

67. print('other: ', end='')

68. print_list(head_other)

2. 设计在链式存储结构上交换二叉树中所有结点左、右子树的算法。

1. import random

2.

3.

4. class Node:

5. id_counter = 0

6.

7. def __init__(self):

8. = _counter

9. _counter += 1

10. = = None

11.

12. def print(self):

13. print(f'id: {}, left: { and }, right: { and }')

14. if is not None:

15. ()

16. if is not None:

17. ()

18.

19. def swap_children(self):

20. if is not None:

21. _children()

22. if is not None:

23. _children()

24. , = ,

25.

26.

27. def build_random_tree(depth=1):

28. node = Node()

29. if depth < 5:

30. if bool(dbits(1)):

31. = build_random_tree(depth + 1)

32. if bool(dbits(1)):

33. = build_random_tree(depth + 1)

34. return node

35.

36.

37. root = build_random_tree()

38. print("original:")

39. ()

40. _children()

41. print("swapped:")

42. ()

3. 在链式存储结构上建立一棵二叉排序树。

1. import random

2.

3.

4. class Node:

5. def __init__(self, key):

6. = key

7. = = None

8.

9. def to_list(self):

10. ret = []

11. if is not None:

12. (_list())

13. ()

14. if is not None:

15. (_list())

16. return ret

17.

18. def insert(self, key):

19. if key < :

20. if is None:

21. = Node(key)

22. else:

23. (key)

24. else:

25. if is None:

26. = Node(key)

27. else:

28. (key)

29.

30.

31. data = [nge(0, 100) for _ in range(10)]

32. print(f'orig: {data}')

33. root = None

34. for x in data:

35. if root is None:

36. root = Node(x)

37. else:

38. (x)

39. print(f'bst: {_list()}')