数据结构试卷(四)
一、 选择题（每题2分，共20分）
1. 设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为( C )。
A. O(n) 
B. O(nlog2n) 
C. O(1) 
D. O(n2)
2. 设一棵二叉树的深度为k，则该二叉树中最多有( D )个结点。
A. 2k-1 
B. 2k 
C. 2k-1 
D. 2k-1
3. 设某无向图中有n个顶点、e条边，则该无向图中所有顶点的入度之和为( D )。
A. n 
B. e 
C. 2n 
D. 2e
4. 在二叉排序树中插入一个结点的时间复杂度为( C )。
A. O(1) 
B. O(n) 
C. O(log2n) 
D. O(n2)
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分）
1. 设有n个无序的记录关键字，则直接插入排序的时间复杂度为 O(n2) ，快速排序的平均时间复杂度为 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 。
4. 深度为k的完全二叉树中最少有 2k-1 个结点。
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 
        self.key = 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 
        s.key = a[i]
 12 
        k = a[i] % P
 13 
        s.next = 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.        self.data = data 
8.         = nxt 
9. 
10. 
11.def print_list(head): 
12.    list_data = [] 
13.    while head is not None: 
14.        list_data.append(head.data) 
15.        head =& 
16.    print(list_data) 
17. 
18. 
19.head_all = None 
20.tail_all = None 
21.for _ in range(20): 
22.    node = Node(random.choice([ 
23.        random.choice(string.ascii_uppercase), 
24.        random.choice(string.digits), 
25.        random.choice(list(set(string.printable) - set(string.ascii_uppercase) - set(string.digits))), 
26.    ])) 
27.    if tail_all is None: 
28.        head_all = tail_all = node 
29.    else: 
30.         = 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 node.data.isupper():  快速排序python实现
46.        if tail_upper is None: 
47.            head_upper = tail_upper = node 
48.        else: 
49.             = node 
50.            tail_upper = node 
51.    elif node.data.isdigit(): 
52.        if tail_digit is None: 
53.            head_digit = tail_digit = node 
54.        else: 
55.             = node 
56.            tail_digit = node 
57.    else: 
58.        if tail_other is None: 
59.            head_other = tail_other = node 
60.        else: 
61.             = node 
62.            tail_other = node 

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。