数据结构C语言总复习.ppt

5. 已知某系统在通讯联络中出现的abcdefg六种字符，其频率为（3，12，7，4，2，8，11），试构造最优二叉树，求带权路径长度，并写出每种字符的huffman编码。 12 15 7 8 20 9 11 4 5 2 3 27 47 字符a的编码为：0011 字符b的编码为：10 字符c的编码为：110 字符d的编码为：000 字符e的编码为：0010 字符f的编码为：111 WPL＝3*4+12*2+7*3+8*3+4*3+2*4+11*2 ＝123 6. 写出如图所示的网的（1）从顶点A出发的深度和广度优先遍历的顶点序列；（2）克鲁斯卡尔算法求最小生成树的过程示意图。 从顶点A出发的深度优先遍历的顶点序列：ABCEFD （答案不唯一） 从顶点A出发的广度优先遍历的顶点序列：ABCDEF （答案不唯一） 6 A B C E F D 10 7 8 11 5 7 9 6 克鲁斯卡尔算法求最小生成树 (1) A B C E F D 5 (2) (3) (4) 7 7 A B C E F D 5 6 A B C E F D 5 6 7 A B C E F D 5 6 克鲁斯卡尔算法求最小生成树 (5) 7 7 A B C E F D 5 6 9 7. 对下图所示的无向网采用prim算法从顶点A开始构造最小生成树。画出最小生成树生成过程。 最小生成树生成过程： 6 A B C D 7 9 5 6 8 10 E 4 7 A B C D E B 5 7 A B C D E B D 6 7 A B C D E B D 4 E 6 7 A B C D E B D 4 E C 8.画出对长度为10的有序表进行折半查找的判定树，并求出查找关键字等概率时查找成功的平均查找长度和查找不成功时的平均查找长度。 答：查找成功的平均查找长度: (1*1+2*2+4*3+3*4)/10=2.9 5 判定树为: 2 8 1 3 6 9 4 7 10 答：查找不成功的平均查找长度: (5*3+6*4)/11=3.54 9.依据下列关键字序列{20，15，19， 23， 30，40，34，25}构成一棵二叉排序树。 （1）请画出些二叉排序树。 （2）若在二叉排序树中查找，则查找成功与查找不成功的平均查找长度分别是多少？ 答：查找成功的平均查找长度: (1*1+2*2+2*3+2*4+1*5)/8=3 20 二叉排序树为: 15 19 23 30 40 34 25 答：查找不成功的平均查找长度: (2*2+2*3+3*4+2*5)/9 =3.56 10.设有一组关键字{1，13，12，34，38，33，27，22}，采用哈希函数H(key)=key%11，请采用开放定址法的线性探测再散列法解决冲突，试在0~10的散列空间中对该关键字序列构造哈希表，并分别求出查找成功的平均查找长度。 线性探测再散列解决冲突构造的哈希表 0 1 2 3 4 5 6 7 8 9 10 1 13 12 34 1 1 比较次数 3 4 38 1 1 33 27 2 8 22 平均查找长度: ASL=21/8 11.已知序列{50 ， 17，12，90，89，27，70，65，42}，请给出采用希尔排序法（d1=4,d2=2,d3=1）对该序列作升序排列时的每一趟的结果。采用快速排序法以第一个元素为枢轴，对该序列作降序排列时每一趟的结果。 初始态 : 50 , 17, 12, 90, 89, 27, 70, 65, 42 初始态 : 50 , 17, 12, 90, 89, 27, 70, 65, 42 d1=4 d2=2 d3=1 89 , 27, 70, 90, 50, 17, 12, 65, 42 89 , 27, 70, 90, 50, 17, 12, 65, 42 89 , 90, 70, 65, 50, 27 ,12, 17, 42 90 , 89, 70, 65, 50, 42, 27, 17, 12 快速排序对该序列作降序排列每一趟结果: 50, 17, 12, 90, 89, 27, 70, 65, 42 初始态 : 第一趟 : 65, 70, 89, 90, 50 , 27, 12, 17, 42 第二趟 : 第三趟 : 第四趟 : 65, 70, 89, 90, 50 ,