综合应用练习

《综合应用练习》由会员分享，可在线阅读，更多相关《综合应用练习（12页珍藏版）》请在装配图网上搜索。

1、综合应用练习题1、树的后根遍历方法是：若树非空则Tm；(1) 依次序后根遍历根的各个子树Ti?T2，(2) 访问根结点。12对图1所示的树，用后根遍历方法进行遍历，请写出遍历所得到的结点访问 序列。2、将图2的森林转换为二叉树图23、图3表示一个地区的交通网，顶点表示城市，边表示连结城市间的公路， 边上的权表示修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省 的n-1条公路，画出所有可能的方案。图34、已知一个无向图的邻接表如图4所示。12345（1）画出这个图。（2）以V为出发点，对图进行广度优先搜索，写出所有可能的访问序列。5、有一组键值25，84，21，47，15，27，68，3

2、5，24，采用快速排序方法由 小到大进行排序，请写出每趟的结果，并标明在第一趟排序过程中键值的移动情 况。6、试分析分别满足下列条件的二叉树有何特点：（1）先序序列和中序序列相同；（2）中序序列和后序序列相同；（3）先序 序列和后序序列相同。7、给出下面无向图（图5）的邻接矩阵和邻接表。8、如图6所示为一无向连通网络，试构造出它的最小生成树。V2V4V5V3图5图69、简述广义表与线性表的区别与联系。10、写出稀疏矩阵M对应的三元组线性表，并画出稀疏矩阵的顺序存储结构图。稀疏矩阵卜0。5 0 0 0 -2 （I 0 0财=I 0 4 0 fi 0。0 0 0 0 00 0-1 0 0 011、

3、已知表Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec。（1）试按表中元素的次序依次插入一棵初始为空的二叉排序树，请画出插 入之后的二叉排序树，并求在等概率情况下查找成功的平均查找长度。（2）若对表中元素先进行排序构成有序表，求在等概率情况下对此表进行 折半查找成功的平均查找长度。12、设记录的关键字集合 K=23，9，39，5，68，12，62，48，33，（1）给 定的增量序列D=4, 2, 1，请写出希尔排序各趟排序的结果；（2）若以表的第 一个元素为基准（或枢轴），写出快速排序第一趟排序的结果。13、将一棵二叉树（如图7）转化成相应森林

4、。图7一14、已知序列10, 18, 4, 3, 6, 12, 1, 9, 15, 8,请给出采用希尔排序法(dl =5)对该序列做升序排序时的每一趟的结果。15、设数据序列为D=(13, 28, 72, 5, 16, 8, 7, 9,34,请为D组织散 列表。散列函数为H (K)=K%7，散列表的长度为10个单元，起站地址为0,要 求用拉链法解决冲突，并计算查找成功的平均查找长度。16、设散列表为 HT17,关键字序列为Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec ，散列函数为H (key) = Li/2,其中，i是

5、关键字第一个字 母在字母表中的序号。现采用线性探查法解决冲突。字母ABCDEFGHIJKLM序号12345678910111213字母NOPQRSTUVWXYZ序号14151617181920212223242526(1) 试画出相应的散列表(要求给出具体解题过程)；(2) 计算等概率下搜索成功的平均搜索长度。17、设有正文 AADBAACACCDACACAAD，字符集为 A, B, C, D, (1) 构造Huffman树；(2)为四个字符设计Huffman编码。18、对m个顶点的无向图G,采用邻接矩阵，如何根据邻接矩阵判别下列 有关问题：(1) 图中有多少条边？(2) 任意两个顶点i和j是

6、否有边相连？(3) 第i个顶点的度是多少？19、已知散列表的长度为12,散列函数为H(K)=K%12，关键字序列为25,37, 52, 43, 84, 99, 15, 26, 11, 70,采用线性探测法处理冲突，试构造散列 表，并计算等概率情况下查找成功时的平均查找长度（ASL）。20、对于下列一组关键字46, 58，15，45，90, 18，10, 62,试写出快速排序每一趟的排序结果，并标出第一趟中各元素的移动方向。21、判断下列两序列是否为堆？若是堆，请说明理由；若不是，将其调整为 堆，并画出调整后的堆。（6分）（1）（3, 10, 12, 22, 36, 18, 28, 40）（2）

7、（5, 8, 11, 15, 23, 20, 32, 7）参考答案:1、 EBFGCKHIJDA2、3、分析：本题实际上是求最小生成树问题。由于边中有两条权值为6的边， 故可以得到两种方案。如下图所示。4、（1）82（2）V v5、1 2V4 V5 V3 和V V4 V2V3 V5O258421471527683524第一趟241521254727683584第二趟211524253527476884第二趟152124252735476884得到 15212425第一趟排序过程中键值的移动情况如下：2735476884V1V2v3V4_V5LJ_i20314A12A2A第一趟：25842147

8、1527683524 一次交换之后回84214715276835困二次交换之后24国214715276835昶24252147152768J584242521471527683584242521471527683584三次交换之后24扃2147|2127683584241521472527683584四次交换之后241521254727683584以上“-”表示当前经比较不交换位置的元素。“”表示当前经比较交换位置的元素。6、解:（1）二叉树中任意一个结点都无左孩子;（2）二叉树中任意一个结点都无右孩子;（3）全多只有一个结点的二叉树。7、解:（1）邻接矩阵：（2）邻接表:8、解:9、线性表是

9、具有相同类型的几个数据元素K0,k1,kn-1的有限序列，记为 （K0,K1,Kn-1）;广义表是n个元素An的有限序列，其中Ai可以是数据元素 或表结构，记为A=（A1，A2，An）。Ki必须有相同类型，而Ai则可以是数 据元素，也可以是表；当广义表每个Ai均是是数据元素且有相同类型时，则它 就是一个线性表，因此，可以说广义表是线性表的一种推广。10、三元线性表：(1,1,3),(1,4,5),(2,3,-2),(3,1,1),(3,3,4),(3,5,6)(5,3,-1)顺序存储结构如下：56711314523-23133435653-111、解：（1）二叉排序树为：（1.5分）JanNo

10、vASL =（1*1+2*2+3*3+4*3+5*2+6*1）/12=42/12（1.5 分）（2）含有12个元素的有序表进行折半查找的判定树如下：（1.5分）1、 / 258 1012ASL = (1*1+2*2+4*3+5*4) /12=37/12 12、解：(1)希尔排序第 1 趟：23, 9, 39, 5, 33, 12, 62, 48, 68第 2 趟：23, 5, 33, 9, 39, 12, 62, 48, 68第 3 趟：5, 9, 12, 23, 33, 39, 48, 62, 68（2）快速排序第 1 趟：12, 9, 5 23 68, 39, 62, 48, 3313、

11、14、第一趟（d = 5）： 10, l, 43, 6, 12, 18, 9, 15, 8第二趟（d = 2）： 4, 1, 6,3,10, 8, 15,9,18,12第三趟（d = 2）： l, 3, 4,6,8, 9, 10,12,15,1815、查找成功的平均查找长度为：(1*5+2*3+3*1)/9=14/916、解:H(Jan) = L10/2J = 5,成功.H(Feb) = |_6/2=3,成功.H(Mar) = L13/2=6,成功.H(Apr) = L1/2=0,成功.H(May) = L13/2=6, = 7,成功，H(June) = L10/2=5, = 6, = 7,

12、=8，成功.H(July) = L10/2=5, = 6, = 7, = 8, = 9 成功.H(Aug) = L1/2=0, = 1,成功.H(Sep) = L19/2=9, = 10，成功.H(Oct) = L15/2=7, = 8, = 9, = 10, = 11 ,成功.H(Nov) = L14/2=7, = 8, = 9, = 10, = 11, = 12,成功.H(Dec) = L4/2=2,成功.(1)构造的散列表如下(5分)：012345678910111213AprAugDecFebJanMarMayJuneJulySepOctNov(2)(1)(1)(1)(1)(2)(4)

13、(5)(2)(5)(6)（2）搜索成功的平均搜索长度为1/12 * （1 + 2 + 1 + 1 + 1 + 1 + 2 + 4 + 5 + 2 + 5 + 6） = 31 / 12（2 分）17、解：（1）Huffman 树注：Huffman树的形态不唯一。（2）由于Huffman树形态不唯一，故Huffman编码也不唯一。根据这棵 Huffman树，得到的Huffman编码为：A1B000C01D00118、解：（1）邻接矩阵非零元素个数的总和除以2。（2）当A i,j 0或A i,j 0时，表示两顶点i,j之间有边相 连。（2分）（3）计算邻接矩阵上第i行非零元素的个数。19、解：解题具

14、体过程散列表：8425379952152643701101234567891011ASL=(1+2+1+1+1+1+3+5+1+1)/10=17/1020、解：第一趟：1018154546905862第二趟：1018154546625890第三趟：1015184546586290结果：1015184546586290第一趟：46, 58, 15, 45, 90, 18, 10, 6221、如何判断一个序列是否为堆？先构造完全二叉树；再判断所有分支结点的值是否均不大于（或不小于）其 左、右孩子结点的值，若是，则为堆；否则不是堆。40根据堆的定义，序列（1）是堆，且为小顶堆。823203246,58,15,45,90,18,10,62.一次交换之后10,58,15,45,90,18,46,62二次交换之后10,46,15,45,90,18,58,62三次交换之后10,18,15,45,90,46,58,6210,18,45,90,46,58,6210,18,15,45,90,46,58,62四次交换之后10,18,15,45,46,90,58,62以上“一”表示当前经比较不交换位置的元素。“ ”表示当前经比较交换位置 的元素。根据堆的定义，序列（2）不是堆，将其调整为堆，调整后的堆如下所示:8