综合应用练习
- 格式:docx
- 大小:513.07 KB
- 文档页数:9
综合应用练习题1、树的后根遍历方法是:若树非空则(1)依次序后根遍历根的各个子树T1,T2,……Tm ; (2)访问根结点。
对图1所示的树,用后根遍历方法进行遍历,请写出遍历所得到的结点访问序列。
2、将图2的森林转换为二叉树图23、图3表示一个地区的交通网,顶点表示城市,边表示连结城市间的公路,边上的权表示修建公路花费的代价。
怎样选择能够沟通每个城市且总造价最省的n-1条公路,画出所有可能的方案。
图34、已知一个无向图的邻接表如图4所示。
v 2v 4v 1v 5 v 3v 616 21113611651 2 3 4 5(1)画出这个图。
(2) 以v1为出发点,对图进行广度优先搜索,写出所有可能的访问序列。
5、有一组键值25,84,21,47,15,27,68,35,24,采用快速排序方法由小到大进行排序,请写出每趟的结果,并标明在第一趟排序过程中键值的移动情况。
6、试分析分别满足下列条件的二叉树有何特点:(1)先序序列和中序序列相同;(2)中序序列和后序序列相同;(3)先序序列和后序序列相同。
7、给出下面无向图(图5)的邻接矩阵和邻接表。
8、如图6所示为一无向连通网络,试构造出它的最小生成树。
图5图69、简述广义表与线性表的区别与联系。
10、写出稀疏矩阵M对应的三元组线性表,并画出稀疏矩阵的顺序存储结构图。
11、已知表{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)转化成相应森林。
图714、已知序列[10,18,4,3,6,12,l,9,15,8],请给出采用希尔排序法(d1=5)对该序列做升序排序时的每一趟的结果。
15、设数据序列为D={13,28,72,5,16,8,7,9,34},请为D组织散列表。
散列函数为H(K)=K%7,散列表的长度为10个单元,起站地址为0,要求用拉链法解决冲突,并计算查找成功的平均查找长度。
16、判断下列两序列是否为堆?若是堆,请说明理由;若不是,将其调整为堆,并画出调整后的堆。
(6分)(1)(3,10,12,22,36,18,28,40)(2)(5,8,11,15,23,20,32,7)17、设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,(1)构造Huffman树;(2)为四个字符设计Huffman编码。
18、对m个顶点的无向图G,采用邻接矩阵,如何根据邻接矩阵判别下列有关问题:(1)图中有多少条边?(2)任意两个顶点i和j是否有边相连?(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,试写出快速排序每一趟的排序结果,并标出第一趟中各元素的移动方向。
参考答案:1、EBFGCKHIJDA2、3、分析:本题实际上是求最小生成树问题。
由于边中有两条权值为6的边,故可以得到两种方案。
如下图所示。
4、(1)(2)v 1 v 2 v 4 v 531 4 23 v 5。
5、25 84 21 47 15 27 68 35 24第一趟 [24 15 21] 25 [47 27 68 35 84] 第二趟 [21 15] 24 25 [35 27] 47 [68 84] 第三趟 [15] 21 24 25 [27] 35 47 68 [84] 得到 15 21 24 25 27 35 47 68 84 第一趟排序过程中键值的移动情况如下:第一趟: [25 84 21 47 15 27 68 35 24 ] 一次交换之后二次交换之后 [24 25 21 47 15 27 68 35 84] [24 25 21 47 15 27 68 35 84] [24 25 21 47 15 27 68 35 84] 三次交换之后四次交换之后以上“-”表示当前经比较不交换位置的元素。
“”表示当前经比较交换位置的元素。
6、解:(1)二叉树中任意一个结点都无左孩子; (2)二叉树中任意一个结点都无右孩子; (3)至多只有一个结点的二叉树。
7、解:(1)邻接矩阵:(2)邻接表: 8、解:、线性表是具有相同类型的几个数据元素-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)) 顺序存储结构如下:0 1 1 0 0 01 1 0 111、解:(1)二叉排序树为:(1.5分)ASL suss =(1*1+2*2+3*3+4*3+5*2+6*1)/12=42/12 (1.5分) (2)含有12个元素的有序表进行折半查找的判定树如下:(1.5分)ASL suss =(1*1+2*2+4*3+5*4)/12=37/1212、解: (1)希尔排序第1趟:23,9,39,5,33,12,62,48,68 第2趟:23,5,33,9,39,12,62,48,68JanFebAugDec Mar June JulyMaySep OctNov631 42 97 511 1210第3趟:5,9,12,23,33,39,48,62,68(2)快速排序第1趟:[12,9,5] 23 [68,39,62,48,33]13、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,18 15、16、解:如何判断一个序列是否为堆?先构造完全二叉树;再判断所有分支结点的值是否均不大于(或不小于)其左、右孩子结点的值,若是,则为堆;否则不是堆。
(1)(3,10,12,22,36,18,28,40)对应的完全二叉树为:根据堆的定义,序列(1)是堆,且为小顶堆。
:根据堆的定义,序列(2)不是堆,将其调整为堆,调整后的堆如下所示:17、解: (1)Huffman 树注:Huffman 树的形态不唯一。
3101218 2822 364058 1120 32152357 11203282315(2)由于Huffman树形态不唯一,故Huffman编码也不唯一。
根据这棵Huffman树,得到的Huffman编码为:A——1 B——000C——01 D——00118、解:(1)邻接矩阵非零元素个数的总和除以2。
(2)当A[ i,j ] <> 0或A[ i,j ] <> 0时,表示两顶点i,j之间有边相连。
(2分)(3)计算邻接矩阵上第i行非零元素的个数。
19、解:解题具体过程散列表:0 1 2 3 4 5 6 7 8 9 10 11ASL=(1+2+1+1+1+1+3+5+1+1)/10=17/1020、解:第一趟:[10 18 15 45] 46 [90 58 62]第二趟:10 [18 15 45] 46 [62 58] 90第三趟:10 [15] 18 [45] 46 [58] 62 [90]结果:10 1518 45 46 58 62 90第一趟:[46, 58, 15, 45, 90, 18, 10, 62][46, 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, 62][10, 18, 15, 45, 90, 46, 58, 62][10, 18, 15, 45, 90, 46, 58, 62]四次交换之后[10, 18, 15, 45, 46, 90, 58, 62]以上“-”表示当前经比较不交换位置的元素。
“”表示当前经比较交换位置的元素。