下载文档原格式
6.3哈夫曼树6.3.1基本术语1.路径和路径长度若在一棵中存在着一个结点序列k1 ,k2,…,kj，使得ki是k1+i 的双亲(1ji<≤)，则称此结点序列是从k1～kj的路径，因树中每个结点只有一个双亲结点，所以它也是这两个结点之间k 1～kj所经过的分支数称为这两点之间的路径长度，它等于路径上的结点数减1(实际就是边数)。
如在图5-19(a)所示的二叉树中，从树根结点L到叶子结点P的路径为结点序列L、M、S、P，路径长度为3。
(a) (b)(c) (d)图5-19 二叉排序树的删除2.结点的权和带权路径长度在许多应用中，常常将树中的结点赋上一个有着某种意义的实数，我们称此实数为该结点的权。
结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点上权的乘积3.树的带权路径长度树的带权路径长度定义为树中所有叶子结点的带权路径长度这和，通常记为：2 WPL = ∑=n i i i lw 1其中n 表示叶子结点的数目，i w 和i l 分别表示叶子结点i k 的权值和根到i k 之间的路径长度 。
4.哈夫曼树哈夫曼(Huffman)树又称最优二叉树。
它是n 个带权叶子结点构成的所有二叉树中，带权路径长度 WPL 最小的二叉树。
因为构造这种树的算法是最早由哈夫曼于1952年提出的，所以被称之为哈夫曼树。
例如，有四个叶子结点a 、b 、c 、d ，分别带权为9、4、5、2，由它们构成的三棵不同的二叉树（当然还有其它许多种）分别如图5-20(a)到图5-20(c)所示。
b ac a b cd d c a b d(a) (b) (c)图5-20 由四个叶子结点构成的三棵不同的带权二叉树 每一棵二叉树的带权路径长度WPL 分别为：(a) WPL = 9×2 + 4×2 + 5×2 + 2×2 = 40(b) WPL = 4×1 + 2×2 + 5×3 + 9×3 = 50(c) WPL = 9×1 + 5×2 + 4×3 + 2×3 = 37其中图5-20(c)树的WPL 最小，稍后便知，此树就是哈夫曼树。
图1. 填空题⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。
【解答】0，n(n-1)/2，0，n(n-1)【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。
⑵ 任何连通图的连通分量只有一个，即是（）。
【解答】其自身⑶ 图的存储结构主要有两种，分别是（）和（）。
【解答】邻接矩阵，邻接表【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。
⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。
【解答】Ｏ(n+e)【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。
⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。
【解答】求第j列的所有元素之和⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。
【解答】出度⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。
【解答】前序，栈，层序，队列⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。
【解答】Ｏ(n2)，Ｏ(elog2e)【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。
⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。
【解答】回路⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。
【解答】vi, vj, vk【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。
数据结构第六章习题
一、选择题
1．求最小生成树的Kruskal算法是一种( )
A.动态规划算法
B.广度优先算法
C.深度优先算法
D.贪心算法
2．在求最短路径的Dijkstra算法中，用来标记顶点是否已经找到最短路径的标记位为( )
A. mark
B. tag
C. flag
D. sign
3．在Dijkstra算法中，初始只将( )加入集合S
A.顶点v
B.顶点v的邻接点
C.顶点v及其邻接点
D.无
4．广义表的抽象数据类型中，判别表示空表的标志位为()
A. head
B. node
C. tail
D. atom
5．静态链表所有分量的数据域统一为()
A. link
B. head
C. data
D. tail
二、填空题
1．在无向图中，任意两点之间只有一条边，则此图称为。
2．求最小生成树的Prim算法的复杂度是。
3．在广义表的抽象数据类型的表示中，一个表示空表的标志位可由一个来表示。
4．串的匹配过程中，用来表示字符串中其中一段字符串的模式串，
用来表示字符串中其它段字符串的模式串。
5．使用栈来求解汉诺塔问题的要点是：先将n-1个盘子从x移到y 上，再将最底下的大盘子从x移到z上，最后将y上n-1个盘子移到z上，如此循环。
三、问答题
1．请介绍二叉树的数据结构及其特点？
二叉树是树结构的一种，其特点是在树中任何一个非叶子节点都有不
超过两个子节点。
一、单项选择题1.已知一个长度为16的顺序L，气元素按关键字有序排列，或采用折半查找法查找一个不在L中存在的元素，则关键字的比较次数最多的是（）。
A．4 B. 5C. 6D. 72.顺序查找适合于存储结构为（）的线性表。
A.顺序存储结构或链式存储结构B.散列存储结构C.索引存储结构D.压缩存储结构3.对长度为n的有序单链表，若查找每个元素的概率相等，则顺序查找表中任意一个元素的查找成功的平均查找长度为（）。
2 B.(n+1)/2C.(n-1)/2 44.对长度为3的顺序表进行查找，若查找的第一个元素概率为1/2，查找第二个元素的概率为1/3，查找第三个元素的概率为1/6，则查找表中任意一个元素的平均查找长度为( )。
33 35.当采用分块查找时，数据的组织方式为（）。
A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D. 数据分成若干块，每块（除最后一块外）中数据个数需相同6.下列关于二分查找的叙述中，正确的是（）。
A．表必须有序，表可以顺序方式存储，也可以链表方式存储B. 表必须有序且表中数据必须是整型，实型或字符型C. 表必须有序，而且只能从小到大排列D．表必须有序，且表只能以顺序方式存储7.使用二分（折半）查找元素的速度比用顺序法（）。
A.必然快B.必然慢C.相等D.不能确定8.已知一个长度为16的顺序表，其元素按关键字有序排列，若采用折半查找查找一个不存在的元素，则比较的次数至少是（），至多是（）。
9.已知一个有序表（13,18,24,35,47,50,62,83,90,115,134），当二分查找值为90的元素师，查找成功的比较次数为（ ）。
10.折半查找过程所对应的判定树是一颗（ ）。
A.最小二叉树B.平衡二叉树C.完全二叉树D.满二叉树11.在有11个元素的 有序表A[1,2,3，…，11]中折半查找(()/2low high +⎢⎥⎣⎦),查找元素为A[11]时，被比较元素的下标依次是（ ）。
，8，10，11 ，9，10，11，7，9，11 ，8，9，1112.具有12个关键字的有序表中，对每个关键字的查找概率相同，遮半查找查找成功的平均查找长度为（ ），折半查找查找失败的平均查找长度为（ ）。
12 1213 1313.对有2500个记录的索引顺序表（分块表）进行查找，最理想的块长为（ ）。
D. 2log 2500⎡⎤⎢⎥14.为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素最多需要执行（ ）次关键字比较。
15.设顺序存储的某线性表共有123个元素，按分块查找的要求等分为3块。
若对索引表采用顺序查找法来确定子块，且确定的字块中也采用顺序查找法，则在等概率情况下，分块查找成功的平均查找长度为（ ）。
16.对长为n 的有序表进行折半查找，其判定树的高度为（ ）。
A. 2log (1)n +⎡⎤⎢⎥B. 2log (1)1n +-⎢⎥⎣⎦C. 2log n ⎡⎤⎢⎥D. 2log 1n -⎢⎥⎣⎦ 17.下列叙述中，不符合m 介B 树定义要求的是（ ）。
A.根节点最多的有m 课子树B.所有叶节点都在同一层上C.各节点内关键字均升序或者降序排列D.叶节点之间通过指针连接18.下列关于m 介B-树的说法错误的是（ ）。
A.根节点至多有m 棵子树B.所有节点都在用一层次上C.非叶节点至少有m/2(m 为偶数)或m/2+1(m 为奇数)棵子树D.根节点中的数据是有序的19.当在一颗m 阶B 树中做插入操作时，若一个结点中的关键字等于（ ），则必须分裂成两个结点，当向一颗树m 阶的B 树做删除操作时，若一个结点中的关键字个数等于（ ），则可能需要同它的做兄弟或有兄弟结点合并成一个结点。
A. ,/22m m -⎡⎤⎢⎥B. 1,/22m m --⎡⎤⎢⎥C. 1,/2m m +⎡⎤⎢⎥D. /2,/21m m +⎡⎤⎢⎥20.下列关于m 阶B 树的说法正确的是（ ）。
I.每个结点至少有两颗非空子树 II.树中每个结点至多有m-1个关键字 III.所有叶结点都在同一层 IV.当插入一个元素引起B 树结点分裂后，树长高一层 、II 、III、IV 、II 、IV 21.下列关于B 树和B+树叙述中，不正确的是（ ）。
A. B 树和B+树都能有效支持顺序查找B. B 树和B+树都能有效支持随机查找C. B 树和B+树都是平衡的多叉树D. B 树和B+树都可以用于文件索引结构22.含有n 个非叶结点的m 阶B-树中至少包含（ ）个关键字。
A. (1)n m +B. nC. ()/21n m -⎡⎤⎢⎥D. ()(1)/211n m --+⎡⎤⎢⎥ 23.已知一课3阶B 树中有2047个关键字，则此B 树的最大高度为（ ），最小高度为（ ）。
24.高度为5的3阶B 树至少有（ ）个结点，至少有（ ）个结点。
25.已知一棵5阶B 树中共有53个关键字，则树的最大高度为（ ），最小高度为（ ）。
.26.具有n 个关键字的m 阶B-树，应有（ ）个叶结点。
+1227.设有一个含有200个表项的散列表，用线性探测法解决冲突，按关键字查询时找到一个表项的平均探测次数不超过，则散列表项应能够容纳（ ）个表项。
（设查找成功的平均查找长度为[]11/(1)/2ASL α=+-，其中α填装因子）A ．400 B. 526C ．624 D. 67628.在开址法中散列到同一个地址而引起的“堆积”问题是由于（ ）引起的。
A.同义词之间发生冲突B. 同义词之间发生冲突之间发生冲突C.同义词或同义词之间发生冲突之间发生冲突D.散列表“溢出”查找一般适用于（ ）情况下的查找。
A.查找表为链表B. 查找表为有序表C.关键字集合比地址集合大得多D. 关键字集合比地址集合存在对应关系30.假定有K 个关键字互为同义词，若用线性探测法把这K 个关键字填入Hash 表中，至少要进行（ ）次探测。
B. K+1 D. K(K+1)/2B A B A二 综合应用题1.若对有N 个元素的有序顺序表和无序顺序表进行顺序查找，试就下列三种情况讨论两者在相等查找概率时的平均查找长度是否相同1).查找失败。
2).查找成功，且表中只有一个关键字等于给定值k 的元素。
3).查找成功，且表中只有若干个关键字等于给定值k 的元素，要求一次能查找所有的元素。
2.设有序顺序表中的元素依次为017、094、154、170、275、503、509、512、553、612、677、765、897、908。
1)试画出对其进行折半查找的判定树。
2)若查找275或684的元素，将依次与表中那些元素比较 3) 计算查找成功的平均查找长度和查找不成功的平均查找长度。
3．已知一个有序顺序表[0...81]A N - 的表厂为8N ，并且表中没有关键字相同的数据元素。
假设按如下所述的方法查找一个关键字值等于给定值X 的数据元素：先在A[7],A[15],A[23],…,A[8K-1],…,A[8N-1]中进行顺序查找，若查找成功，则算法报告成功位置并返回；若不成功，[]81[8(1)1]A K X A K -<<⨯+-时，则可以确定一个缩小的查找范围[]8[8(1)2]A K A K ⨯+-:，然后可以再这个范围内执行折半查找。
特殊情况：若[81]X A N >-的关键字，则查找失败。
1)画出上述查找过程的判定树。
2)计算相等查找概率下查找成功的平均查找长度。
4.类比二分查找法，设计K 分查找法（k 为大于2的整数）如下：首先检查n/k 处（n 为查找表的长度）的元素是否等于要搜索的值，然后检查2n/k 处的元素…这样，或者找到要查找的元素，或者把集合缩小到原来的1/k,如果未找到要查找的元素，则继续在得到的集合上进行K 分查找；如此进行，直到找到要查找的元素或者查找失败。
试求，查找成功和查找失败的时间复杂度。
5.线性表中各结点的检索概率不等，则可用如下策略提高顺序检索的效率：若找到指定的结点，将该结点和其前驱结点交换，使经常被检索的结点尽量位于表的前端。
是设计在顺序结构和链式结构的线性表实现上述策略的顺序检索算法。
6.一个长度为(1)L L ≥的升序序列S ，处在第/2n ⎡⎤⎢⎥个位置的数为S 的中位数。
例如，若序列S1=(11，13，15，17，19)，则S1的中位数是15，两个序列的中位数是含他们所有元素的的升序序列的中位数。
例如，若S2=(2，4，6，8，20),则S1和S2的中位数是11。
现在有两个等长升序序列A 和B ，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A 和B 的中位数。
要求：（1）给出算法的基本思想。
（2）根据设计思想，采用C 或者C++或JAVA 语言描述算法，关键之处给注释。
（3）说明你所涉及的算法的时间复杂度和空间复杂度。
7.写出折半查找的递归算法。
初始调用时，low 为1，high 为8.利用B 树做文件索引时，若假设磁盘的页块的大小是4000字节（实际应该是2的次幂，为了计算方便），指示磁盘地址的指针需要五个字节。
现有个记录构成的文件，每个记录为200字节，其中包括五个关键字节。
试问在次采用B树做索引的文件中，B树的阶数应为多少假定文件数据部分未按关键字有序排列，则索引部分需要占多少磁盘页块9.假定把关键字key散列到有n个表项（从0到n-1编址）的散列表中。
对于下面的每一个散列函数H(key)(key为整数)，这些函数能够当做散列函数吗如果能够，他是好的散列函数吗请说明理由。
设函数random(n)返回一个0到n-1之间的随机整数1）H(key)=key/n。
2）H(key)=1.3）H(key)=(key+random(n))%n。
4）H(key)=key%p(n);其中p(n)是不大于n的最大素数。
10.使用散列函数H(key)=key%11，把一个整数值转换成散列列表的下标，现在要把数据{1,13,34,38,33,27,22}依次插入到散列表中。
1）使用线性探测在散列法来构造散列表。
2）使用链表地址法构造散列表。
答案部分一、选择题1-10 B A B A B D D AB B B11-20 B AD A C B A D C A B21-30 A D AD BD CB A A C D D二、综合题1解答：(1)平均查找长度不同。
因为有序顺序表查找到其关键字值比要查找值大的元素时就停止查找，并报告失败信息，不必查找到表尾；而无需表必须查找到表尾才能确定查找失败。
