[习题4-1]运算题。
二叉树公式1．有6个元素A、B、C、D、E、F依次进栈，允许任何时候出栈，能否得到下列的每个出栈序列，若能，给出栈操作的过程，若不能，简述其理由。
（1）CDBEFA （2）ABEDFC （3）DCEABF （4）BAEFCD
2．有4个元素a,b,c,d依次进栈，任何时候都可以出栈，请写出所有可能的出栈序列和所有不存在的序列。
3．用一维数组a[7]顺序储一个循环队列，队首和队尾指针分别用front和rear表示，当前队列中已有5个元素：23，45，67，80，34，其中，23为队首元素，front的值为3，请画出对应的存储状态，当连续做4次出队运算后，再让15，36，48元素依次进队，请再次画出对应的存储状态。
4．用于顺序存储一个队列的数组的长度为N,队首和队尾指针分别为front和rear,写出求此队列长度(即所含元素个数)的公式.
参考答案（从简）
1，(1)能: push(S,A), push(S,B), push(S,C), pop(S), push(S,D), pop(S), pop(S), push(S,E), pop(S), push(S,F), pop(S), pop(S).
(2)能:push(S,A), pop(S), push(S,B), pop(S), push(S,C), push(S,D), push(S,E), pop(S), pop(S), push(S,F), pop(S), pop(S).
(3)不能: 当E出栈时，AB必需在栈内，而后继A出栈先于B，不符合后进先出原则。
(4)不能: 当F出栈时，CD必需在栈内，而后继C出栈先于D，不符合后进先出原则。
2，所有可能的出栈序列:
abcd; abdc; acbd; acdb; adcb;
bacd; badc; bcad; bcda; bdca;
cbad; cbda; cdba;
dcba.
所有不存在的序列:
adbc;
bdac;
cabd; cadb; cdab;
dabc; dacb; dbac; dbca; dcab.
3，
0 1 2 3 4 5 6
------------------------------------------------------------------
[80 34 23 45 67]
↑rear ↑front
[ 34 15 36 48 ]
↑front ↑rear
4，队列长度L的计算公式为：
L = ( N+rear-front ) % N
[ 说明：
当rear>front 时，L = rear - front = ( N+rear-front ) % N;
当rear<front 时，队列被分为两个部分，前部分在数组的尾部，其元素个数为 N-1-front , 后部分在数组的首部，其元素个数为 rear+1 , 所以：
L =( rear+1+N-1 - front )%N= ( N+rear-front ) % N; ]
[习题6-1]运算题
1.已知一组元素为(46,25,78,62,12,37,70,29),画出按元素排列顺序输入生成的一棵二叉搜索树,再以广义表的形式给出该二叉搜索树.
2.已知一棵搜索树的广义表表示为28(12(,16),49(34(30),72(63))),若从中依次删除72,12,49,28,等4个结点,试分别画出每删除一个结点后得到的图形表示的二叉搜索树,并写出对应的广义表表示.
3.从空堆中开始依次向小根堆中插入集合{38,64,52,15,73,40,48,55,26,12}中的每个元素,试以顺序表的形式给出每插入一个元素后堆的状态.
4.已知一个堆为{12,15,40,38,26,52,48,64},若从堆中依次删除4个元素,请给出每删除一个元素后的堆的状态.
5.有7个带权结点,其权值分别为3,7,8,2,6,10,14,试以它们为叶子结点构造一棵哈夫曼树,给出其广义表表示.并计算出带权路径长度WPL.
*6.在一份电文中共使用5种字符,即d.e,它们的出现频率依次为4,7,5,2,9,试画出对应的哈夫曼编码和传送电文的总长度.
*7.一棵二叉树的广义表表示为A(B(,D(G,),)C(E(,H),F)),试画出对应的图示二叉树
*9.一组关键字为(36,75,83,54,12,67,60,40,92,72),试依次插入结点分别生成一棵二叉搜索树，并求查每个元素的平均查长度.
2.
删除72 删除12 删除49 删除28
1.
广义表：46( 52 (12 , 37 ( 29 )) , 78 ( 62 ( ,70 )))
5.
广义表：( ( ( ( 2 , 3 ) , 6 ) , 10 ) , ( ( 7 , 8 ) , 14 ) )
WPL = ( 10 + 14 )×2 + ( 6 + 7 + 8 )×3 + ( 2 + 3 )×4
3.4.
删除12
15 26 40 38 64 52 48
删除15
26 38 40 48 64 52
删除26
38 48 40 52 64
删除38
40 48 64 52
3838 64
38 64 52
15 38 52 64
15 38 52 64 73
15 38 40 64 73 52
15 38 40 64 73 52 48
15 38 40 55 73 52 48 64
15 26 40 38 73 52 48 64 55
12 15 40 38 26 52 48 64 55 73
6.
电文总长 = 4×4 + 7×2 + 5×3 + 2×4 + 9×1
7. 9.
ASL =( 1 + 2×2 + 2×3 + 3×4 + 2×5 ) / 10
[习题7-1]运算题
1、 如图7-13（a）和图7-13（b）所示，求：
（1） 每一个图的二元组表示。
（2） 图7-13（a）中每个顶点的度，以及每个顶点的所有邻接点和所有边。
（3） 图7-13（b）中每个顶点的入度、出度和度，以及每顶点的所有入边的出边。
（4） 图7-13（a）中从v0到v4的所有简单路径及相应路径长度。
（5） 图7-13（b）中从v0到v4的所有简单路径及相应带权路径长度。
（a）无向图 （b）有向图
图7—13运算题图1
2、 根据图7-13（a）和图7-13（b），画出：
（1） 每个图的邻接邻接矩阵。
（2） 每个图的邻接表。
（3） 每个图的边集数组。
3、 如图7-14所示，按下列条件分别写出从顶点v0出发按深度优先搜索遍历得到的顶点序列
和按广度优先搜索遍历得到的顶点序列。
（1） 假定它们均采用邻接矩阵表示。
（2） 假定它们均采用邻接表表示，并且每个顶点邻接表中的结点都是按顶点序号从大到小的次序链接的。
（a）无向图 （b）有向图
图7—14运算题图2
4、 已知一个图的二元组表示如下：
V={0，1，2，3，4，5，6，7，8}
E={（0，3），（0，4），（1，2），（1，4），（2，4），（2，5），（3，6），（3，7），（4，7），（5，8），（6，7），（7，8）}
（1） 画出对应的图形。
（2） 假定从顶点0出发，给出邻接矩阵表示图的深度优先和广度优先搜索遍历的顶点序列。
（3） 假定从顶点0出发，给出邻接表表示的图的深度优先和广度优先搜索遍历的顶点序列，假定每个顶点邻接表中的结点都是按顶点序号从大到小的次序链接的。
答案
3.
依照矩阵和邻接表所产生的两种遍历序列各自相等。
a图：深度优先遍历：0 1 2 8 3 4 5 6 7 9
广度优先遍历：0 1 4 2 7 3 8 6 9 5
b图：深度优先遍历：0 1 4 5 8 7 2 3 6
广度优先遍历：0 1 3 4 2 6 7 5 8
4.
深度优先遍历：0 3 6 7 4 1 2 5 8
广度优先遍历：0 3 4 6 7 1 2 8 5
[习题8-1]运算题
1、如图形8-18所示,针对有向图操作如下。
（1）画出最小生成树并求出它的权。
（2）从顶点v0出发，要据普里姆算法求出最小生成树的过程中，把依次得到的各条边按序写出来。
（3）根据克鲁斯卡算法求出最小生成树的过程中，把依次得到的各条边写出来。
图 8—18 无向带权图 (1)
(2)普里姆算法的边的序列：( 0 ,1 )， ( 1 ,6 )，( 6 ,2 ) ，( 2 ,3 )， ( 3 ,4 )，( 4 ,5 )
(3)克鲁斯卡算法的边的序列：( 1 ,6 )， ( 2 ,3 )，( 0 ,1 ) ，( 6 ,2 )， ( 3 ,4 )，( 4 ,5 )
2、如图8-19所示，利用狄克特拉算法求从顶点V0到其余各顶点的最短路径，并画出对应的图形表示。
不画图了，只写出边的序列。以下各点的最短路径是按顺序生成的：
0→3：< 0,3>
0→5：< 0,5>
0→1：< 0,3> , < 3,1>
0→6：< 0,5> , < 5,6>
0→4：< 0,5> , < 5,6> , < 6,4>
0→2：< 0,5> , < 5,6> , < 6,4> , < 4,2>
0→7：< 0,5> , < 5,6> , < 6,4> , < 4,2> , < 2,7>
图 8—19 有向带权图
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论