数据结构:Python语言描述期末试卷及答案5套|江阴雨辰互联

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

数据结构试卷（一）

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

1. 栈和队列的共同特点是（ A ）。

A. 只允许在端点处插入和删除元素

B. 都是先进后出

C. 都是先进先出

D. 没有共同点

2. 用链接方式存储的队列在进行插入运算时（D）。

A. 仅修改头指针

B. 头、尾指针都要修改

C. 仅修改尾指针

D. 头、尾指针可能都要修改

3. 以下数据结构中（D）是非线性结构。

A. 队列

B. 栈

C. 线性表

D. 二叉树

4. 设有一个二维数组A[m][n]，假设A[0][0]的存放位置在644(10)，A[2][2]的存放位置在676(10)，每个元素占一个空间，那么A[3][3](10)存放在（C）位置。脚注(10)表示用十进制表示。

A. 688

B. 678

C. 692

D. 696

5. 树最适合用来表示（C）。

A. 有序数据元素

B. 无序数据元素

C. 元素之间具有分支层次关系的数据

D. 元素之间无联系的数据

6. 二叉树的第k层的结点数最多为（D）。

A. 2k-1

B. 2K+1

C. 2K-1

D. 2k-1

7. 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放在A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为（C）。

A. 1，2，3

B. 9，5，2，3

C. 9，5，3

D. 9，4，2，3

8. 对n个记录的文件进行快速排序所需要的辅助存储空间大致为（D）。

A. O(1)

B. O(n)

C. O(1og2n)

D. O(n2)

9. 对线性表(7，34，55，25，64，46，20，10)进行散列存储时，若选用H(K)=K%9作为散列函数，则散列地址为1的元素有(C)个。

A. 1

B. 2

C. 3

D. 4

10. 设有6个结点的无向图，该图至少应有（B）条边才能确保是一个连通图。

A. 5

B. 6

C. 7

D. 8

二、填空题（每空1分，共26分）

1. 通常从4个方面评价算法的质量，即正确性、易读性、强壮性和高效性。

2. 一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示_o（n）_。

3. 假定一棵树的广义表表示为A(C，D(E，F，G)，H(I，J))，则树中所含的结点数为9个，树的深度为3，树的度为3。

4. 后缀算式9 2 3 +- 10 2 / -的值为-1_。中缀算式(3+4X)-2Y/3对应的后缀算式为3 4 X * +2 Y 3

/ * -。

5. 若用链表存储一棵二叉树，每个结点除数据域外还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有2n个指针域，其中有n-1指针域存放了地址，有n+1个指针是空指针。

6. 对于一个有n个顶点和e条边的有向图和无向图，在其对应的邻接表中所含的边结点分别为e个和2e个。

7. AOV网是一种没有回路的图。

8. 在一个有n个顶点的无向完全图中包含有_n(n-1)/2_条边，在一个有n个顶点的有向完全图中包含有_n(n-1)_条边。

9. 假定一个线性表为(12,23,74,55,63,40)，若按key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的4个子表分别为_{12，40}_、_φ_、{74}_和_{23,55,63}_。

10. 在向一棵B-树插入元素的过程中若最终引起树根结点的分裂，则新树比原树的高度_多1_。

11. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_o(log2n)__，整个堆排序过程的时间复杂度为_o(nlog2n)_。

12. 在快速排序、堆排序、归并排序中归并排序是稳定的。

三、计算题（每题6分，共24分）

1. 在如图A.1所示的数组A中链接存储了一个线性表，表头指针为A[0].next，试写出该线性表。

图A.1数组A

线性表为：

A[3]->A[2]->A[7]->A[1]->A[5]->A[4]->A[0]->A[3]

2. 请画出图A.2所示的邻接矩阵和邻接表。

图A.2无向图

邻接矩阵：

1111

1011101111邻接表：

3. 已知一个图的顶点集V和边集E如下：

V={1,2,3,4,5,6,7};

E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,

(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};

用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。

（0,3）2——（4,6）4——（0,2）5——（1,5）6——（0,1）8——（3,6）10——（5,7）20

4. 画出向小根堆中加入数据4、2、5、8、3时每加入一个数据后堆的变化。

四、阅读算法（每题7分，共14分）

1 def mynote(L):

2 # L是不带头结点的单链表的头指针

3 if L is not None and is not None:

4 q = L

5 l =

6 p = L

7 while :

8 p = # S1

9 = q

10 = None

11 return L

请回答下列问题：

(1) 说明语句S1的功能；

(2) 说明语句组S2的功能；

(3) 设链表表示的线性表为(a1,a2, …,an),写出算法执行后的返回值所表示的线性表。

答：

(1) 找到链表的最后一个节点。

(2) 将链表的最后一个节点指向L，并将L的下一节点清空。

(3) a2,...,an,a1。

1 def ABC(BT):

2 # BT是二叉树的结点

3 if BT is not None:

4 ABC()

5 ABC()

6 print(,end=' ')

该算法的功能是_打印二叉树各节点的值_。

五、算法填空（共8分）

二叉搜索树的查找—递归算法:

1 def Find(BST,item):

2 # BST是搜索二叉树的结点，item是查找的元素

3 if BST is None:

4 return false # 查找失败

5 if item == :

6 item = # 查找成功

7 return true

8 elif item<:

9 return Find(BST->left,item)

10 else:

11 return Find(BST->right,item)

六、编写算法（共8分）

统计出单链表HL中结点的值等于给定值X的结点数。

定义函数如下：

def is_count(self, X):

cur = self.__head

count = 0

while cur is not None:

if == X:

count+=1

cur =

return count

数据结构试卷（二）

一、选择题（每题3分，共24分）

1. 下面关于线性表的叙述错误的是（D）。

A. 线性表采用顺序存储必须占用一片连续的存储空间

B. 线性表采用链式存储不必占用一片连续的存储空间

C. 线性表采用链式存储便于插入和删除操作的实现

D. 线性表采用顺序存储便于插入和删除操作的实现

2. 设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（B）个空指针域。

A. 2m-1

B. 2m

C. 2m+1

D. 4m

3. 设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（C）。

A. R-F

B. F-R

C. (R-F+M)％M

D. (F-R+M)％M

4. 设某棵二叉树的中序遍历序列为ABCD、前序遍历序列为CABD，则后序遍历该二叉树得到的序列为（A）。

A. BADC

B. BCDA

C. CDAB

D. CBDA

5. 设某完全无向图中有n个顶点，则该完全无向图中有( A )条边。

A. n(n-1)/2

B. n(n-1)

C. n2D. n-1

6. 设某棵二叉树中有2000个结点，则该二叉树的最小高度为( C )。

A. 9

B. 10

C. 11

D. 12

7. 设某有向图中有n个顶点，则该有向图对应的邻接表中有（ B ）个表头结点。

A. n-1

B. n

C. n+1

D. 2n-1

8. 设有一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（C）。

A. 2，3，5，8，6

B. 3，2，5，8，6

C. 3，2，5，6，8

D. 2，3，6，5，8

二、填空题(每空2分，共24分)

1. 为了能有效地应用Hash查找技术，必须解决的两个问题是___如何构造哈希函数和如何解决冲突。

2. 下面程序段的功能实现数据x进栈，要求在下画线处填上正确的语句。

1 class SqStack:

2 def __init__(self):

3 = [None] * 100

4 = 0

5 # ... ...

7 # ... ...

9 def push(self,x):

10 if == 100:

11 raise('overflow')

12 else:

13 __[top]=x____

14 ___top=top+1___

3. 中序遍历二叉排序树所得到的序列是____有序____序列(填有序或无序)。

24. 快速排序的最坏时间复杂度为___O(n)_____，平均时间复杂度为___O(nlogn)_____。

5. 设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为2的结点数为____N0-1___；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有____N1+2N0____个空指针域。

6. 设某无向图中的顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=____d/2____。

7. 设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建立的初始堆为____ 大根堆：（80，75，55，56，63，44，31，38）

小根堆：（31，38，44，56，75，80，55，63）____。

8. 已知一个有向图的邻接表存储结构如图A.3所示，从顶点1出发，DFS遍历的输出序列是_____ 1，3，4，5，2___，BFS遍历的输出序列是____ 1，3，2，4，5____。

图A.3图的邻接表存储结构

三、应用题(每题6分，共36分)

1. 设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。

答：简单选择排序：22，40，45，48，80，78

直接插入排序：40，45，48，80，22，78

2. 设指针变量p指向双向链表中的结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列(设双向链表中结点的两个指针域分别为llink和rlink)。

答：q->llink=p;

q->rlink=p->rlink;

p->rlink->llink=q;

p->rlink=q;

3. 设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。

答：比较次数2，平均查找长度25/9

图A.4无向图G

4. 设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法(二叉链表)表示出该树的存储结构并将该树转化成对应的二叉树。

答：

5. 设有如图A.4所示的无向图G，要求给出用普里姆算法构造最小生成树所走过的边的集合。

答：{(1 ， 3) ， (1 ， 2) ， (3 ， 5) ， (5 ， 6) ， (6 ， 4)}

6. 设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。

答：构造过程如下：

插入过程：若二叉排序树为空，则待插入结点*S作为根结点插入到空树中；

当非空时，将待插结点关键字S->key和树根关键字t->key进行比较，

若s->key = t->key,则无须插入，若s->key< t->key,则插入到根的左子树中，

若s->key> t->key,则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同，

如此进行下去，直到把结点*s作为一个新的树叶插入到二叉排序树中，或者直到发现树已有相同关键字的结点为止。

构造结果：

四、算法设计题(每题8分，共16分)

1. 设有一组初始记录关键字序列(K1，K2，…，Kn)，要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。

1 def quicksort(list,i,n):

2 left = i

3 right = n

4 temp = list[i]

5 while left < right:

6 while lefttemp :

7 right = right - 1

8 if left < right :

9 list[left] = list[right]

10 left = left + 1

11 while left

12 left = left + 1

13 if left < right :

14 list[right] = list[left]

15 right = right - 1

16 list[left] = temp

2. 设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构表示。

1 class Node():

2 i=0

3 def _init_(self,data):

4 =data

5 =None

6 Node.i+=1

8 def andOperation(a,b,c):

9 p=a

10 c=None

11 while p!=None:

12 q=b

13 while q!=None:

14 if ==:

break

q =

if q!=None:

t=Node()

c=t

p =

数据结构试卷（三）

一、选择题(每题2分，共20分)

1. 设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是( B )。

A. 线性结构

B. 树形结构

C. 物理结构

D. 图形结构

2. 下面程序的时间复杂度为( B )。

1 i = 1

2 s = 0

3 while i<=n:

4 i += 1

5 t = 1

6 for j in range(1,i):

7 t = t * j

8 s = s + t

A. O(n)

2B. O(n)

3C. O(n)

4D. O(n)

3. 设指针变量p指向单链表中的结点A，若删除单链表中的结点A，则需要修改指针的操作序列为( A )。

A. q=； =； =；

B. q=； =； =；

C. q=； =；

D. q=； =；

4. 设有n个待排序的记录关键字，在堆排序中需要( A )个辅助记录单元。

A. 1

B. n

C. nlog2n

D. n

5. 设一组记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为( A )。

A. 10，15，14，18，20，36，40，21

B. 10，15，14，18，20，40，36，21

C. 10，15，14，20，18，40，36，21

D. 15，10，14，18，20，36，40，21

6. 设二叉排序树中有n个结点，则二叉排序树的平均查找长度为( B )。

A. O(1)

B. O(log2n)

C. O（n）

2D. O(n)

7. 设无向图G中有n个顶点、e条边，则其对应的邻接表中的表头结点和表结点的个数分别为( D )。

A. n、e

B. e、n

C. 2n、e

D. n、2e

8. 设某强连通图中有n个顶点，则该强连通图中至少有( C )条边。

A. n(n-1)

B. n+1

C. n

D. n(n+1)

9. 设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列( B )方法可以达到此目的。

A. 快速排序

B. 堆排序

C. 归并排序

D. 插入排序

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

A. 插入排序

B. 冒泡排序

C. 堆排序

D. 归并排序

二、填空题(每空1分，共20分)

1. 数据的物理结构主要包括顺序存储结构和链式存储结构两种情况。

2. 设一棵完全二叉树中有500个结点，则该二叉树的深度为____9_____；若用二叉链表作为该完全二叉树的存储结构，则共有_____501____个空指针域。

3. 设输入序列为（1，2，3），则经过栈的作用后可以得到___5______种不同的输出序列。

4. 设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上的所有元素之和等于顶点i的_____出度____，第i列上的所有元素之和等于顶点i的___入度______。

5. 设哈夫曼树中共有n个结点，则该哈夫曼树中有____0_____个度数为1的结点。

6. 设有向图G中有n个顶点、e条有向边，所有的顶点入度数之和为d，则e和d的关系为____e=d_____。

7. ____中序_____遍历二叉排序树中的结点可以得到一个递增的关键字序列(填先序、中序或后序)。

8. 设查找表中有100个元素，如果用二分查找方法查找数据元素X，则最多需要比较_____7____次就可以断定数据元素X是否在查找表中。

9. 不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为___O(1)______。

10. 设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点的编号为___i/2(向下取整)______，右孩子结点的编号为___2*i+1______。

11. 设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的一趟快速排序的结果为___5 16 71 23 72 94 73______。

12. 设有向图G中的有向边的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图的一种拓扑序列为___1 4 2 3______。

13. 下列算法实现在顺序散列表中查找值为x的关键字的功能，请在下画线处填上正确的语句。

1 class record(object):

2 def __init__(self,key,others):

3 = key

4 = others

6 def hashSqSearch(hashTable,k):

7 i = j = k % P

8 while hashTable[j].key!=k and hashTable[j].flag!=0:

9 j = ___j+1___ % m

10 if i==j:

11 return -1

12 if _hashtable[j].key==__k___:

13 return j

14 else return -1

14. 下列算法实现在二叉排序树上查找关键值k的功能，请在下画线处填上正确的语句。

1 def Find(BST,k):

2 # BST是搜索二叉树的结点，k是查找的元素

3 if BST is None:

4 return false # 查找失败

5 if k == :

6 k = # 查找成功

7 return _true_____

8 elif item<:

9 return Find(______,k)

10 else:

11 return Find(______,k)

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

1. 已知二叉树的前序遍历序列是AEFBGCDHIKJ、中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。

2. 已知待散列的线性表为(36，15，40，63，22)，散列用的一维地址空间为[0..6]，假定选用的散列函数是H(K)= K mod 7，若发生冲突采用线性探查法处理，试计算以下问题：

(1) 计算出每一个元素的散列地址并在图A.5中填写出散列表。

图A.5填写散列表

0 1 2 3 4 5 6

63 36 15 22 40

(2) 求出在查找每一个元素概率相等情况下的平均查找长度。

(1+2+1+1+3)/5 = 1.6。

3. 已知序列(10，18，4，3，6，12，1，9，18，8)，请用快速排序写出每一趟排序的结果。

第一趟排序结果：9 4 3 6 1 10 12 18 18

第二趟排序结果：1 4 3 6 9 10 12 18 18

第三趟排序结果：1 4 3 6 9 10 12 18 18

第四趟排序结果：1 3 4 6 9 10 12 18 18

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

1. 设计在单链表中删除值相同的多余结点的算法。

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

class Node:

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

= data

= nxt

def delete_same_node(node):

p = node

if p is None:

return

elif is None:

return

else:

q =

while q!=None:

if ==:

p = q

q =

else:

p =

q =

return

2. 设计一个求结点x在二叉树中的双亲结点的算法。

class TreeNode:

def __init__(self, data=None, lchild=None, rchild=None):

= data

= lchild

= rchild

def find_parent(root, target):

10.

11.

12.

13.

14.

15.

if root is None:

return None

elif is target or is target:

return root

elif is None and is None:

return None

else:

return find_parent(, target) or find_parent(, target)

数据结构试卷(四)

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

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

A. O(n)

B. O(nlog2n)

C. O(1)

2D. O(n)

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

A. 2k-1

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

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

5. class Node:

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

7. = data

8. = nxt

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

4. class Node:

5. id_counter = 0

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

4. class Node:

5. def __init__(self, key):

6. = key

7. = = None

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()}')

数据结构试卷（五）

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

1. 数据的最小单位是( A )。

A. 数据项

B. 数据类型

C. 数据元素

D. 数据变量

2. 设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为( B )。

A. 40，50，20，95

B. 15，40，60，20

C. 15，20，40，45

D. 45，40，15，20

3. 设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为( A )。

A. 15，25，35，50，20，40，80，85，36，70

B. 15，25，35，50，80，20，85，40，70，36

C. 15，25，35，50，80，85，20，36，40，70

D. 15，25，35，50，80，20，36，40，70，85

4. 函数substr("DATASTRUCTURE"，5，9)的返回值为( A)。

A. "STRUCTURE"

B. "DATA"

C. "ASTRUCTUR"

D. "DATASTRUCTURE"

5. 设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为( D )。

A. O(log2n)

B. O(1)

2C. O(n)

D. O(n)

6. 设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为N1，…，度数为m的结点数为Nm，则N0=(B)。

A. N1+N2+…+Nm

B. 1+N2+2N3+3N4+…+(m-1)Nm

C. N2+2N3+3N4+…+(m-1)Nm

D. 2N1+3N2+…+(m+1)Nm

7. 设有序表中有1000个元素，则用二分查找法查找元素X最多需要比较(B)次。

A. 25

B. 10

C. 7

D. 1

8. 设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为(B)。

A. abedfc

B. acfebd

C. aebdfc

D. aedfcb

9. 设输入序列是（1，2，3，…，n），经过栈的作用后输出序列的第一个元素是n，则输出序列中的第i个输出元素是(C)。

A. n-I

B. n-1-I

C. n+1-I

D. 不能确定

10. 设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准得到的一趟快速排序的结果是(C)。

A. 40，42，45，55，80，83

B. 42，40，45，80，85，88

C. 42，40，45，55，80，85

D. 42，40，45，85，55，80

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

1. 设有一个顺序共享栈S[0： n-1]，其中第一个栈顶指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是__top1+1 = top2__。

2. 在图的邻接表中用顺序存储结构存储表头结点的优点是_可以随机访问到任一个顶点的简单链表_。

3. 设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素(包括对角线上的元素)存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_i*（i+1)/2

+j-1__个数据元素。

4. 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为FILO表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_FIFO表。

5. 设一棵完全二叉树的顺序存储结构中的存储数据元素为ABCDEF，则该二叉树的前序遍历序列为_ABDECF_、中序遍历序列为_DBEAFC_、后序遍历序列为_DEBFCA_。

6. 设一棵完全二叉树有128个结点，则该完全二叉树的深度为_8_，有_64_个叶子结点。

7. 设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中的所有非零元素个数之和等于顶点i的_出度_，第i列中的所有非零元素个数之和等于顶点i的_入度_。

8. 设一组初始记录关键字序列(k1，k2，…，kn)是堆，则对i=1、2、…、n/2而言满足的条件为_ki<=k2i and k<=k2i+1_。

9. 下面程序段的功能是实现冒泡排序算法，请在下画线处填上正确的语句。

1 def bubbleSort(sqlist):

2 flag = True

3 i = 1

4 while i< and flag:

5 flag = False

6 for j in range(_n-i_):

7 if [j+1].key < [j].key:

8 p = [j]

9 r[j+1]=r[j]

10 [j+1] = p

11 flag = True

12 i += 1

10. 下面程序段的功能是实现二分查找算法，请在下画线处填上正确的语句。

1 class record(object):

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

3 = key

4 = other

6 def bisearch(r,k):

7 low = 0

8 high = len(r)-1

9 while low<=high:

10 _mid=(low+high)/2_

11 if r[mid].key == k:

12 return mid+1

13 elif r[mid].key>k:

14 high = mid-1

15 else:

16 low = mid+1

17 return -1

三、应用题（每题8分，共32分）

1. 设某棵二叉树的中序遍历序列为DBEAC、前序遍历序列为ABDEC，要求给出该二叉树的后序遍历序列。

答：DEBCA

2. 设有无向图G(如图A.7所示)，给出该图的最小生成树上边的集合，并计算最小生成树各边上的权值之和。

图A.7无向图G

答：E={(1,5),(5,2),(5,3),(3,4)},W=10

3. 设一组初始记录关键字序列为(15，17，18，22，35，51，60)，要求计算出成功查找时的平均查找长度。

答：ASL=(1*1+2*2+3*4)/7=17/7;

4. 设散列表的长度为8，散列函数H(k)=k mod 7，初始记录关键字序列为(25，31，8，27，13，68)，要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。

答：ASL1=7/6,ASL2=4/3

四、算法设计题（每题14分，共28分）

1. 设计判断两个二叉树是否相同的算法。

1 Def judge(node nod1,node nod2):

2 If nod1 == NULL and nod2 == NULL:

3 return True;

4 Elif nod1 == NULL or nod2 == NULL or !=:

5 return False;

4 Else:

5 If judge(,) and judge(,):

6 Return True;

7 Else:

8 Return False

2. 设计两个有序单链表的合并排序算法。

1 Def merge(lklist l1,lklist l2):

2 lklist out = lklist()

3 While !y() and !y():

4 If () < ():

5 (())

4 _front()

5 Else:

6 (())

7 _front()

8 If !y():

9 For item in l1:

10 (item)

11 If !y():

12 For item in l2:

13 (item)

14 Return out

数据结构试卷（一）

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

1. 栈和队列的共同特点是（ A ）。

A. 只允许在端点处插入和删除元素

B. 都是先进后出

C. 都是先进先出

D. 没有共同点

2. 用链接方式存储的队列在进行插入运算时（D）。

A. 仅修改头指针

B. 头、尾指针都要修改

C. 仅修改尾指针

D. 头、尾指针可能都要修改

3. 以下数据结构中（D）是非线性结构。

A. 队列

B. 栈

C. 线性表

D. 二叉树

A. 688

B. 678

C. 692

D. 696

5. 树最适合用来表示（C）。

A. 有序数据元素

B. 无序数据元素

C. 元素之间具有分支层次关系的数据

D. 元素之间无联系的数据

6. 二叉树的第k层的结点数最多为（D）。

A. 2k-1

B. 2K+1

C. 2K-1

D. 2k-1

7. 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放在A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为（C）。

A. 1，2，3

B. 9，5，2，3

C. 9，5，3

D. 9，4，2，3

8. 对n个记录的文件进行快速排序所需要的辅助存储空间大致为（D）。

A. O(1)

B. O(n)

C. O(1og2n)

D. O(n2)

9. 对线性表(7，34，55，25，64，46，20，10)进行散列存储时，若选用H(K)=K%9作为散列函数，则散列地址为1的元素有(C)个。

A. 1

B. 2

C. 3

D. 4

10. 设有6个结点的无向图，该图至少应有（B）条边才能确保是一个连通图。

A. 5

B. 6

C. 7

D. 8

二、填空题（每空1分，共26分）

1. 通常从4个方面评价算法的质量，即正确性、易读性、强壮性和高效性。

2. 一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示_o（n）_。

3. 假定一棵树的广义表表示为A(C，D(E，F，G)，H(I，J))，则树中所含的结点数为9个，树的深度为3，树的度为3。

4. 后缀算式9 2 3 +- 10 2 / -的值为-1_。中缀算式(3+4X)-2Y/3对应的后缀算式为3 4 X * +2 Y 3

/ * -。

6. 对于一个有n个顶点和e条边的有向图和无向图，在其对应的邻接表中所含的边结点分别为e个和2e个。

7. AOV网是一种没有回路的图。

8. 在一个有n个顶点的无向完全图中包含有_n(n-1)/2_条边，在一个有n个顶点的有向完全图中包含有_n(n-1)_条边。

10. 在向一棵B-树插入元素的过程中若最终引起树根结点的分裂，则新树比原树的高度_多1_。

11. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_o(log2n)__，整个堆排序过程的时间复杂度为_o(nlog2n)_。

12. 在快速排序、堆排序、归并排序中归并排序是稳定的。

三、计算题（每题6分，共24分）

1. 在如图A.1所示的数组A中链接存储了一个线性表，表头指针为A[0].next，试写出该线性表。

图A.1数组A

线性表为：

A[3]->A[2]->A[7]->A[1]->A[5]->A[4]->A[0]->A[3]

2. 请画出图A.2所示的邻接矩阵和邻接表。

图A.2无向图

邻接矩阵：

1111

1011101111邻接表：

3. 已知一个图的顶点集V和边集E如下：

V={1,2,3,4,5,6,7};

E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,

(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};

用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。

（0,3）2——（4,6）4——（0,2）5——（1,5）6——（0,1）8——（3,6）10——（5,7）20

5. 画出向小根堆中加入数据4、2、5、8、3时每加入一个数据后堆的变化。

四、阅读算法（每题7分，共14分）

1 def mynote(L):

2 # L是不带头结点的单链表的头指针

3 if L is not None and is not None:

4 q = L

5 l =

6 p = L

7 while :

8 p = # S1

9 = q

10 = None

11 return L

请回答下列问题：

(1) 说明语句S1的功能；

(2) 说明语句组S2的功能；

(3) 设链表表示的线性表为(a1,a2, …,an),写出算法执行后的返回值所表示的线性表。

答：

(1) 找到链表的最后一个节点。

(2) 将链表的最后一个节点指向L，并将L的下一节点清空。

(3) a2,...,an,a1。

1 def ABC(BT):

2 # BT是二叉树的结点

3 if BT is not None:

4 ABC()

5 ABC()

6 print(,end=' ')

该算法的功能是_打印二叉树各节点的值_。

五、算法填空（共8分）

二叉搜索树的查找—递归算法:

1 def Find(BST,item):

2 # BST是搜索二叉树的结点，item是查找的元素

3 if BST is None:

4 return false # 查找失败

5 if item == :

6 item = # 查找成功

7 return true

8 elif item<:

9 return Find(BST->left,item)

10 else:

11 return Find(BST->right,item)

六、编写算法（共8分）

统计出单链表HL中结点的值等于给定值X的结点数。

定义函数如下：

def is_count(self, X):

cur = self.__head

count = 0

while cur is not None:

if == X:

count+=1

cur =

return count

数据结构试卷（二）

一、选择题（每题3分，共24分）

1. 下面关于线性表的叙述错误的是（D）。

A. 线性表采用顺序存储必须占用一片连续的存储空间

B. 线性表采用链式存储不必占用一片连续的存储空间

C. 线性表采用链式存储便于插入和删除操作的实现

D. 线性表采用顺序存储便于插入和删除操作的实现

2. 设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（B）个空指针域。

A. 2m-1

B. 2m

C. 2m+1

D. 4m

A. R-F

B. F-R

C. (R-F+M)％M

D. (F-R+M)％M

4. 设某棵二叉树的中序遍历序列为ABCD、前序遍历序列为CABD，则后序遍历该二叉树得到的序列为（A）。

A. BADC

B. BCDA

C. CDAB

D. CBDA

5. 设某完全无向图中有n个顶点，则该完全无向图中有( A )条边。

A. n(n-1)/2

B. n(n-1)

C. n2D. n-1

6. 设某棵二叉树中有2000个结点，则该二叉树的最小高度为( C )。

A. 9

B. 10

C. 11

D. 12

7. 设某有向图中有n个顶点，则该有向图对应的邻接表中有（ B ）个表头结点。

A. n-1

B. n

C. n+1

D. 2n-1

8. 设有一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（C）。

A. 2，3，5，8，6

B. 3，2，5，8，6

C. 3，2，5，6，8

D. 2，3，6，5，8

二、填空题(每空2分，共24分)

1. 为了能有效地应用Hash查找技术，必须解决的两个问题是___如何构造哈希函数和如何解决冲突。

2. 下面程序段的功能实现数据x进栈，要求在下画线处填上正确的语句。

1 class SqStack:

2 def __init__(self):

3 = [None] * 100

4 = 0

5 # ... ...

7 # ... ...

9 def push(self,x):

10 if == 100:

11 raise('overflow')

12 else:

13 __[top]=x____

14 ___top=top+1___

3. 中序遍历二叉排序树所得到的序列是____有序____序列(填有序或无序)。

24. 快速排序的最坏时间复杂度为___O(n)_____，平均时间复杂度为___O(nlogn)_____。

6. 设某无向图中的顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=____d/2____。

7. 设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建立的初始堆为____ 大根堆：（80，75，55，56，63，44，31，38）

小根堆：（31，38，44，56，75，80，55，63）____。

8. 已知一个有向图的邻接表存储结构如图A.3所示，从顶点1出发，DFS遍历的输出序列是_____ 1，3，4，5，2___，BFS遍历的输出序列是____ 1，3，2，4，5____。

图A.3图的邻接表存储结构

三、应用题(每题6分，共36分)

1. 设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。

答：简单选择排序：22，40，45，48，80，78

直接插入排序：40，45，48，80，22，78

答：q->llink=p;

q->rlink=p->rlink;

p->rlink->llink=q;

p->rlink=q;

答：比较次数2，平均查找长度25/9

图A.4无向图G

答：

5. 设有如图A.4所示的无向图G，要求给出用普里姆算法构造最小生成树所走过的边的集合。

答：{(1 ， 3) ， (1 ， 2) ， (3 ， 5) ， (5 ， 6) ， (6 ， 4)}

6. 设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。

答：构造过程如下：

插入过程：若二叉排序树为空，则待插入结点*S作为根结点插入到空树中；

当非空时，将待插结点关键字S->key和树根关键字t->key进行比较，

若s->key = t->key,则无须插入，若s->key< t->key,则插入到根的左子树中，

若s->key> t->key,则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同，

如此进行下去，直到把结点*s作为一个新的树叶插入到二叉排序树中，或者直到发现树已有相同关键字的结点为止。

构造结果：

四、算法设计题(每题8分，共16分)

1 def quicksort(list,i,n):

2 left = i

3 right = n

4 temp = list[i]

5 while left < right:

6 while lefttemp :

7 right = right - 1

8 if left < right :

9 list[left] = list[right]

10 left = left + 1

11 while left

12 left = left + 1

13 if left < right :

14 list[right] = list[left]

15 right = right - 1

16 list[left] = temp

2. 设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构表示。

1 class Node():

2 i=0

3 def _init_(self,data):

4 =data

5 =None

6 Node.i+=1

8 def andOperation(a,b,c):

9 p=a

10 c=None

11 while p!=None:

12 q=b

13 while q!=None:

14 if ==:

break

q =

if q!=None:

t=Node()

c=t

p =

数据结构试卷（三）

一、选择题(每题2分，共20分)

A. 线性结构

B. 树形结构

C. 物理结构

D. 图形结构

2. 下面程序的时间复杂度为( B )。

1 i = 1

2 s = 0

3 while i<=n:

4 i += 1

5 t = 1

6 for j in range(1,i):

7 t = t * j

8 s = s + t

A. O(n)

2B. O(n)

3C. O(n)

4D. O(n)

3. 设指针变量p指向单链表中的结点A，若删除单链表中的结点A，则需要修改指针的操作序列为( A )。

A. q=； =； =；

B. q=； =； =；

C. q=； =；

D. q=； =；

4. 设有n个待排序的记录关键字，在堆排序中需要( A )个辅助记录单元。

A. 1

B. n

C. nlog2n

D. n

5. 设一组记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为( A )。

A. 10，15，14，18，20，36，40，21

B. 10，15，14，18，20，40，36，21

C. 10，15，14，20，18，40，36，21

D. 15，10，14，18，20，36，40，21

6. 设二叉排序树中有n个结点，则二叉排序树的平均查找长度为( B )。

A. O(1)

B. O(log2n)

C. O（n）

2D. O(n)

7. 设无向图G中有n个顶点、e条边，则其对应的邻接表中的表头结点和表结点的个数分别为( D )。

A. n、e

B. e、n

C. 2n、e

D. n、2e

8. 设某强连通图中有n个顶点，则该强连通图中至少有( C )条边。

A. n(n-1)

B. n+1

C. n

D. n(n+1)

9. 设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列( B )方法可以达到此目的。

A. 快速排序

B. 堆排序

C. 归并排序

D. 插入排序

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

A. 插入排序

B. 冒泡排序

C. 堆排序

D. 归并排序

二、填空题(每空1分，共20分)

1. 数据的物理结构主要包括顺序存储结构和链式存储结构两种情况。

2. 设一棵完全二叉树中有500个结点，则该二叉树的深度为____9_____；若用二叉链表作为该完全二叉树的存储结构，则共有_____501____个空指针域。

3. 设输入序列为（1，2，3），则经过栈的作用后可以得到___5______种不同的输出序列。

5. 设哈夫曼树中共有n个结点，则该哈夫曼树中有____0_____个度数为1的结点。

6. 设有向图G中有n个顶点、e条有向边，所有的顶点入度数之和为d，则e和d的关系为____e=d_____。

7. ____中序_____遍历二叉排序树中的结点可以得到一个递增的关键字序列(填先序、中序或后序)。

8. 设查找表中有100个元素，如果用二分查找方法查找数据元素X，则最多需要比较_____7____次就可以断定数据元素X是否在查找表中。

9. 不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为___O(1)______。

11. 设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的一趟快速排序的结果为___5 16 71 23 72 94 73______。

12. 设有向图G中的有向边的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图的一种拓扑序列为___1 4 2 3______。

13. 下列算法实现在顺序散列表中查找值为x的关键字的功能，请在下画线处填上正确的语句。

1 class record(object):

2 def __init__(self,key,others):

3 = key

4 = others

6 def hashSqSearch(hashTable,k):

7 i = j = k % P

8 while hashTable[j].key!=k and hashTable[j].flag!=0:

9 j = ___j+1___ % m

10 if i==j:

11 return -1

12 if _hashtable[j].key==__k___:

13 return j

14 else return -1

14. 下列算法实现在二叉排序树上查找关键值k的功能，请在下画线处填上正确的语句。

1 def Find(BST,k):

2 # BST是搜索二叉树的结点，k是查找的元素

3 if BST is None:

4 return false # 查找失败

5 if k == :

6 k = # 查找成功

7 return _true_____

8 elif item<:

9 return Find(______,k)

10 else:

11 return Find(______,k)

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

1. 已知二叉树的前序遍历序列是AEFBGCDHIKJ、中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。

(1) 计算出每一个元素的散列地址并在图A.5中填写出散列表。

图A.5填写散列表

0 1 2 3 4 5 6

63 36 15 22 40

(2) 求出在查找每一个元素概率相等情况下的平均查找长度。

(1+2+1+1+3)/5 = 1.6。

3. 已知序列(10，18，4，3，6，12，1，9，18，8)，请用快速排序写出每一趟排序的结果。

第一趟排序结果：9 4 3 6 1 10 12 18 18

第二趟排序结果：1 4 3 6 9 10 12 18 18

第三趟排序结果：1 4 3 6 9 10 12 18 18

第四趟排序结果：1 3 4 6 9 10 12 18 18

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

1. 设计在单链表中删除值相同的多余结点的算法。

23.

24.

25.

26.

27.

28.

29.

30.

31.

32.

33.

34.

35.

36.

37.

38.

39.

40.

41.

42.

43.

44.

class Node:

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

= data

= nxt

def delete_same_node(node):

p = node

if p is None:

return

elif is None:

return

else:

q =

while q!=None:

if ==:

p = q

q =

else:

p =

q =

return

2. 设计一个求结点x在二叉树中的双亲结点的算法。

16.

17.

18.

19.

20.

21.

22.

class TreeNode:

def __init__(self, data=None, lchild=None, rchild=None):

= data

= lchild

= rchild

def find_parent(root, target):

23.

24.

25.

26.

27.

28.

29.

30.

if root is None:

return None

elif is target or is target:

return root

elif is None and is None:

return None

else:

return find_parent(, target) or find_parent(, target)

数据结构试卷(四)

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

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

A. O(n)

B. O(nlog2n)

C. O(1)

2D. O(n)

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

A. 2k-1

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 个空指针域。

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) 。

发布者：admin，转转请注明出处：http://www.yc00.com/web/1704382775a1347218.html

数据结构:Python语言描述期末试卷及答案5套

发表回复

评论列表（0条）

数据结构:Python语言描述期末试卷及答案5套

相关推荐

发表回复

评论列表（0条）