数据结构应用题

一、应用题

1. 已知关键字序列为：（74,33,52,41,13,88,66,59）哈希表长为9，哈希函数为：H (k)＝k %9，解决冲突用线性补偿探测法 （取Q=5），试构造哈希表，并求出等概率下查找成功的平均查找长度。 【答案】

（1）哈希表:

0 1 2 3 4 5 6 7 8 59 74 88 13 41

2

1

2

1

1

(2) ASL=（5*1+3*2）/8=11/8

33 1

52 1

66 2

（2）简述算法f30的功能。

void f30 (SeqList *L) { int i,j;

for (i=j=0;ilength; i++)

if(L->data[i]>=0){

if(i!=j)L->data[j]=L->data[i]; j++； } L->length=j; }

（1）L=(21,19,0,34,30)

(2) 删除顺序表中小于0的数。

4. 已知关键字序列{34,26,47,12,63,41,22,59},利用堆排序的方法对其排序。

（1）写出在构成初始堆后关键字的排列情况。 （2）写出在堆排序的过程中输出前4个记录时,每次调整后关键字的排列情况。 【答案】

（1）初始堆：{12,26,22,34,63,41,47,59}

（2）输出12后：{22，26，41，34，63，59，47} 输出22后：{26，34，41，47，63，59} 输出26后：{34，47，41，59，63} 输出34后：{41，47，63，59}

5. 请用克鲁斯卡尔算法构造下图所示网络的最小生成树。

18 v1 14 5 3 ∧ 【答案】

2. 已知一个AOV网如图所示。

(1)试画出它的邻接链表。（顶点号递减出现在各邻接表中）

(2)试写出按照拓扑排序算法得到的拓扑序列。

V2 V3 V4 V6 V5 V1 【答案】

(1)

1 v1 0 2v2 2 ∧ 3 V3 2 4 v4 0 5 v5 3 6 v6 1 3 2 ∧ 22 12 v2 10 V6 10 5 ∧ 6 2 ∧ 5 ∧ 16 v4 v3 19 8 v5 20 (2)v4,v6,v1,v3,v5,v2

3. 已知线性表的存储结构为顺序表，阅读下列

算法，并回答问题：

（1）设线性表L=（21，-7，-8，19，0，-11，

34，30，-10），写出执行f30(&L)后的L状态；

【答案】

最小生成树如下图所示：

万维试题库系统 第 1 页

v1 14 18 12 v3 v2 (1) 哈希表:

10 V6 0 1 2 3 4 5 6 7 8 27 93 12 131 42 79 102 8 v5 v4 6. 给出一组关键字K={14,28,17,9,7,21,13,4,11},

写出用下列方法排序时,第一趟结束时关键字的排列

(2) ASL=（5*1+1*2+1*6）/7=13/7

9. 设网络如图所示，试用普里姆算法按照并入最小生成树中边的次序填写下表(从顶点A开始)，并画出对应的最小生成树。

2 B 2 C 3 4 F 1 E 5 4 2 D 状态。

(1)快速排序(2)希尔排序(d1=4) (3)归并排序 【答案】

给出一组关键字K={14,28,17,9,7,21,13,4,11},写出用下列方法排序时,第一趟结束时关键字的排列状态。

(1)快速排序：{11,4,13,9,7}14{21,17,28}

(2)

希

尔

排

序

(d1=4)

：

始 点 终 点 1 3 4 2 A 5

{7,21,13,4,11,28,17,9,14}

(3)归并排序：[11，28 ] [9，17 ] [7，21 ] [4，13 ] [11]

7. 假设一棵二叉树的先根遍历序列为ABCDEFGHI，中根遍历序列为ADCEBFHIG。 (1)画出该二叉树；（2）写出后根遍历序列。 【答案】

（1）二叉树：

A B C D E H I F G 权 值 【答案】 1 3 4

2 始 点 终 点 权 值 A E 2 5 C E 3 E F 1 A R 2 R C 2 B C D 2 2 C 3 1 F 2 D （2）后根遍历序列： DECIHGFBA 8. 已知关键字序列为：（93,42,79,131,12,102,27），哈希表长为9，哈希函数为：H (k)＝k %9，解决冲突用线性探测再

散列法，试构造哈希表，并求出等概率下查找成功的平均查找长度。 【答案】

10. 依次读入给定的整数序列{7，16，4，8，20，9，6，18，5}，完成下列操作：

1)构造一棵二叉排序树,计算在等概率情况下该二叉排序树的平均查找长度ASL;

2)若变更序列中元素的排列,可构造出平均查找长度达到最小的二叉排序树。写出满足上述要求的序列中的第一个元素。 【答案】

万维试题库系统 第 2 页

（1）ASL=(1+2*2+3*3+3*4)/9=26/9 （2）8 11. （1）画出对表长为13的有序顺序表进行二分查找的判定树； （2）已知关键字序列为（12，14，16，21，24，28，35，43，52，67，71，84，99），写出在该序列中二分查找37时所需进行的比较次数。 【答案】 （1）如图所示. 7 中根遍历序列: DBAEGCF 后根遍历序列: DBGEFCA 13. 已知关键字序列为：（70,31,52,41, 88,12,27,66）哈希表长为9，哈希函数为：H (k)＝k %9，解决冲突用线性探测再散列法，试构造哈希表，并求等概率下查找成功的平均查找长度。 【答案】 (1) 哈希表: 0 1 2 3 4 5 6 7 8 88 27 12 31 41 66 70 52 3 1 10 5 8 12 (2) ASL=（4*1+2*2+1*3+1*4）/8 = 15/8 14. 设一段文字中七个常用汉字为{的，地，得，和，个，在，是}，每个字符的使用频率分别为{26，6，4，7，9，8，18}。请画出对应的哈夫曼编码树（按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个字符的哈夫曼编码。 【答案】 13 2 4 6 9 11 哈夫曼树： 78 （2）4次 12. 已知二叉树如右图所示。（1）画出该二叉树的二叉链表；（2）分别写出该二叉树的先根、中根和后根遍历序列。 0 33 1 45 0 15 1 18 19 0 1 26 A C 0 7 1 8 是 0 9 1 10 的 1 6 B 和 在 个 0 4 得 D E F 哈夫曼编码 地 G 【答案】 (1) A B ∧ ∧ D ∧ C ∧ F ∧ 的 11 地 1011 得 1010 和 000 个 100 15. 假设以数组seqn［m］存放循环队列的元素，设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。 (1)写出队满的条件表达式； (2)写出队空的条件表达式； ∧ E ∧ G ∧ （2）先根遍历序列：ABDCEGF (3)设m=40,rear=13,quelen=19,求队头元素的位置； (4)写出一般情况下队头元素位置的表达式。 【答案】 万维试题库系统 第 3 页

(1)quelen==m (2)quelen==0 (3)35 (4)(rear-quelen+1+m)%m 16. 下列是一棵五阶B-树,依次执行以下两步操作,画出每一步执行后所得到的B-树形。 (1)插入n;(2)删除e 。 c f j r H(95)=95 % 13=4 H(187)=187 % 13=5 H(123)=123 % 13=6 H(70)=70 % 13=5 H(63)=63 % 13=11 H(47)=47 % 13=8 a b d e g h i k l m p 【答案】 (1)插入n: j c f m r ∧ 0 1 2 3 s t u x 4 5 6 ∧ 7 8 9 ∧ 10 11 12 27 ∧ 132 ∧ 68 ∧ 95 ∧ 70 123 ∧ 8 87 ∧ 63 25 ∧ 310 ∧ 47 ∧ 187 ∧ ASL=(1*10+2*3)/13=16/13 d e g h i k l n p s t u x 18. 已知一组数据元素为（ 57，24，96，73，18，45，

(2)删除e: 30，40，82），要求： （1）试从空树开始画出按元素排列顺序输入而生成j 的一棵二叉排序树； （2）画出删除结点57后的二叉排序树。 c g m r a b 【答案】 (1) 二叉排序树: 57 a b d f h i k l n p s t u x 24 45 73 96 17. 选取哈希函数为H(K)=K % 13，用链地址法处理冲突。试在0～12的散列地址空间中对关键字序列{87，25，310，08， 27，132，68，95，187，123，70，63，47}构造哈希表，并求出等概率下查找成功的平均查找长度。 【答案】 H(87)=87 % 13=9 H(25)=25 % 13=12 H(310)=310 % 13=11 H(8)= 8 % 13=8 H(27)=27 % 13=1 H(132)=132 % 13=2 H(68)=68 % 13=3 18 30 40 82 （2）删除结点57后的二叉排序树: 24 18 30 73 40 82 45 96 或： 万维试题库系统 第 4 页