（大题）数据结构练习题(1)

输入序列

123PA 输入序列

答：pa321,p3a21,p32a1,p321a,ap321

4、设有序列30,18,3,61,14,49，请按该序列构成一棵二叉排序树，并求其查找成功时的平均查找长度。

30 18 61 3 49 14 查找成功时的平均查找长度:1/6(1+2+2+3+3+4)=2.5

5、有7个带权结点，其权值分别为3，7，8，2，6，10，14，试以它们为叶子结点生成一棵霍夫曼树（要求左子女的权值小于右子女），并求出该树的带权路径长度。（这道题还有问题）

50

29 21

14 15 10 11

7 8 5 6

2 3

该树的带权路径长度为：14*2+7*3+8*3+10*2+2*4+3*4+6*3=131

6、设有一个输入数据的序列为{46，25，78，62，12，37，70，29}，试根据二叉排序树的

17

插入过程画出逐个输入以上数据而生成的二叉排序树。（要求写出插入过程）(这道题不懂) 46 25 78 12 37 62 29 70

7、已知某系统在通讯时，只出现F，T，D，S，H五种字符，它们出现的频率依次为5，10，4，2，1，试设计Huffman编码。（定义左子树为0右子树为1） 22 12 10 5 7 3 4

1 2

Huffman编码为：F: 00,T:1,D:011,S:0101,H:0100

8、用序列（46，88，45，39，70，58，101，10，66，34）建立一棵二叉排序树，画出该树，并求在等概率情况下查找成功的平均搜索长度。

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树；（66为什么不排在101左下侧） 46 45 88 39 70 101 10 58 34 66 平均搜索长度:1/10(1+2+2+3+3+3+4+4+5+5)=3.2

9、在实际应用中经常遇到的稀疏矩阵是三对角矩阵，如下图所示。在该矩阵中除主对角线及在主对角线上下最临近的两条对角线上的元素外，所有其他元素均为0。现在要将三对角矩阵A中三条对角线上的元素按行优先方式存储在一维数组B中，且a11存放于B[0]。试给出计算A在三条对角线上的元素aij（1≤i≤n，i-1≤j≤i+1）在一维数组B中的存放位置的计算公式。（5分）（这道题不懂）

18

?a11?a?21?A=??????a12a22a32?a23a33?a34?an?1n?2an?1n?1ann?1????? ?an?1n??ann?? a11 a12 a21 a22 a23 a32 a33 a34 ?? ann-1 ann 答：k=2*i+j-3

10、分别根据Kruskal、普里姆算法的基本思想，从顶点0开始，给出下图的最小生成树(要 求写出生成过程)。

Kruskal算法的最小生成树如上图红线所示

Prim算法如图所示。

11、若一个具有n个顶点，k条边的无向图是一个森林（n>k），则该森林中必有多少棵树。 答假设该森林中有s棵树：T1,T2,……,TS ，且每个Ti有ni 个结点，ki条边(i=1,2,……，S),由树的等价条件可知： ki＝ni－1，则k＝k1+k2+……+ks=（n1－1）+（n2－1）＋……＋（ns－1）＝n－s,故s=n－k,所以该森林中必有n－k棵树。

0 10 5 25 4 24 28 14 6 1 16 2 18 3 12 22 0 10 5 25 4 24 28 14 6 1 16 2 18 3 12 22 19

12、假设通信电文使用的字符集为{a，b，c，d，e，f，g}，字符的霍夫曼编码依次为：0110，10，110，111，00，0111和010。

（1）请根据编码画出该霍夫曼树，并在叶子结点中标注相应字符；

（2）若这些字符在电文中出现的频度分别为：3，35，13，15，20，5和9，求该霍夫曼树的带权路径长度WPL的值。 100 37 63 17 20 28 35 8 9 13 15 3 5

WPL=3*4+5*4+9*3+20*2+13*3+15*3+35*2=253

13、给定权值集合{15，03，14，02，06，09，16，17}。根据赫夫曼算法的内容来构造相应的赫夫曼树，并计算它的带权路径长度WPL。 82 49 33 20 29 16 17 11 09 14 15 5 6 2 3

WPL=2*5+3*5+6*4+9*3+14*3+15*3+16*2+17*2=229

g a f c d e b

20