数据结构复习之运算操作题（答案）

[习题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

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种字符,即a.b.c.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),试依次插入结点分别生成一棵二叉搜索树，并求查找每个元素的平均查找长度. 1.

广义表：46( 52 (12 , 37 ( 29 )) , 78 ( 62 ( ,70 ))) 3. 38 38 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 d e 0001 1 4 1 a b c 0000 01 001 4 2 3 字符 编码 7. 9. 6. 5. 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 广义表：( ( ( ( 2 , 3 ) , 6 ) , 10 ) , ( ( 7 , 8 ) , 14 ) ) WPL = ( 10 + 14 )×2 + ( 6 + 7 + 8 )×3 + ( 2 + 3 )×4 2. 删除72 删除12 删除49 删除28 码长 ASL =( 1 + 2×2 + 2×3 + 3×4 + 2×5 ) / 10 电文总长 = 4×4 + 7×2 + 5×3 + 2×4 + 9×1 [习题7-1]运算题

1、 如图7-13（a）和图7-13（b）所示，求： （1） （2） （3） （4） （5）

每一个图的二元组表示。

图7-13（a）中每个顶点的度，以及每个顶点的所有邻接点和所有边。 图7-13（b）中每个顶点的入度、出度和度，以及每顶点的所有入边的出边。 图7-13（a）中从v0到v4的所有简单路径及相应路径长度。 图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） （3） 答案 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

画出对应的图形。

假定从顶点0出发，给出邻接矩阵表示图的深度优先和广度优先搜索遍历的顶点序列。

假定从顶点0出发，给出邻接表表示的图的深度优先和广度优先搜索遍历的顶点序列，假定每个顶点邻接表中的结点都是按顶点序号从大到小的次序链接的。

[习题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 有向带权图 3、已知一个图的二元组表示为：V={ 0，1，2，3，4，5，6，7 }

E={（0，1）8，（0，3）2，（0，5）10，（1，2）6，（1，4）20，（1，6）12，（2，4）10，（2，7）15，（3，5）5，（3，6）7，（4，7）4，（5，6）6，（6，7）8 } （1）按照克鲁斯卡尔算法求出最小生成树，写出依次得到的各条边。 （2）按照狄克斯特算法求从顶点0到其余各顶点的最短路径。 ( 1 ) ( 0 ,3 )， ( 4 ,7 )，( 3 ,5 ) ，( 5 ,6 )， ( 1 ,2 ) ，( 0 ,1 ) ，( 6 ,7 ) ( 2 ) 0→3：( 0 ,3 )

0→5：( 0 ,3 )，( 3 ,5 ) 0→1：( 0 ,1 )

0→6：( 0 ,3 )，( 3 ,6 ) 0→2：( 0 ,1 )，( 1 ,2 ) 0→7：( 0 ,3 )，( 3 ,6 )，( 6 ,7 ) 0→4：( 0 ,3 )，( 3 ,6 )，( 6 ,7 )，( 7 ,4 )

4、如图形8-20所示，利用弗洛伊德算法求每对顶点之间的最短路径，即仿照如图形8-8的运算过程，给出从邻接矩阵出发每加入一个中间每加入一个中间点后矩阵状态。 图 8—20 有向带权图 5如图形8-21所示，试给出一种拓扑序列，若在它的邻接表存储结构中，每个顶点邻接表中的边结点都是按照终点序号从大到小链接的，则按此给出唯一一种拓扑序列。 6一个AOV网的二元组表示为：V={0，1，2，3，4，5，6，7，8，9，10} E={<0,2>,<0,4>,<1,2>,<1,5>,<2,4>,<3,5>,<4,6>,<4,7>,<5,7>,<6,8>,<7,6>,<7,8>,<7,9>,<8,10>,<9,10>}

在此AOV网的邻接表存储中,若各顶点邻接表中的边结点是按照邻接顶点序号从大到小链接的,请写出按此邻接表和介绍表和介绍的拓扑排序算法得到得到的拓扑排序算法得到的拓扑序列。

提示：先画出图形再运算。

图8—21 AOV网 答案:

1 4 0 2 3 5 7 6 8 9 答案:1 0 2 4 3 5 7 6 8 9 10

7、如图形8-22所示的AOV网，求：

（1）每个事件的最早发生时间和最迟发生时间。 （2）完成整个工程至少需要多长时间。

（3）每项活动的最早开始时间和最迟开始时间以及开始时间余量。 （4）画出由所有关键活动所构成的图。 （5）哪些活动加速可使整个工程提前完成？

图8—22 AOE网 答案:

( 1 )设ve( i )和vl( i )分别表示事件i的最早发生时间和最迟发生时间。 ve( 0 ) = 0

ve( 1 ) = ve( 0 ) + a1 = 5 ve( 2 ) = ve( 0 ) + a2 = 6

ve( 3 ) = Max{ ve( 1 ) + a3 , ve( 2 ) + a4 } = Max{ 8 , 12 } = 12 ve( 4 ) = Max{ ve( 2 ) + a5 , ve( 3 ) + a6 } = Max{ 9 , 15 } = 15 ve( 5 ) = ve( 3 ) + a7 = 16

ve( 6 ) = Max{ ve( 3 ) + a8 , ve( 4 ) + a9 } = Max{ 16 , 16 } = 16 ve( 7 ) = ve( 4 ) + a10 = 17

ve( 8 ) = Max{ ve( 6 ) + a12 , ve( 7 ) + a13 } = Max{ 21 , 19 } = 21 ve( 9 ) = Max{ ve( 5 ) + a11 , ve( 8 ) + a14 } = Max{ 20 , 23 } = 23

vl( 9 ) = 23

vl( 8 ) = vl( 9 ) – a14 = 21 vl( 7 ) = vl( 8 ) – a13 = 19 vl( 6 ) = vl( 8 ) – a12 = 16 vl( 5 ) = vl( 9 ) – a11 = 19

vl( 4 ) = Min{ vl( 6 ) – a9 , vl( 7 ) - a10 } = Min{ 15 , 17 } = 15

vl( 3 ) = Min{ vl( 5 ) – a7 , vl( 6 ) – a8, vl( 4 ) – a3 } = Min{ 15 , 12, 12 } = 12 vl( 2 ) = Min{ vl( 3 ) – a4 , vl( 4 ) – a5 } = Min{ 6 , 12 } = 6 vl( 1 ) = vl( 3 ) – a3 = 9 vl( 0 ) = 0

( 2 ) 因为ve( 9 ) = 23，所以完成整个工程至少的时间为23。

( 3 ) 设e( i )和l( i )分别为活动i的最早开始时间和最迟开始时间，则l( i )－e( i )为每个活动的开始时间余量。活动i由弧< j,k >表示。根据( 1 )题所得的结果和关系e( i ) = ve( j )、l( i ) = vl( k )－w，得出下表： 活动 < 0,1 > < 0,2> < 1,3> < 2,3> < 2,4> < 3,4> < 3,5> < 3,6> < 4,6> < 4,7> < 5,9> < 6,8> < 7,8> < 8,9> e ve( 0 ) = 0 ve( 0 ) = 0 ve( 1 ) = 5 ve( 2 ) = 6 ve( 2 ) = 6 ve( 3 ) = 12 ve( 3 ) = 12 ve( 3 ) = 12 ve( 4 ) = 15 ve( 4 ) = 15 ve( 5 ) = 16 ve( 6 ) = 16 ve( 7 ) = 17 ve( 7 ) = 21 l vl( 1 )－a1=4 vl( 2 )－a2=0 vl( 3 )－a3=9 vl( 3 )－a4=6 vl( 4 )－a5=12 vl( 4 )－a6=12 vl( 5 )－a7=15 vl( 6 )－a8=12 vl( 6 )－a9=15 vl( 7 )－a10=17 vl( 9 )－a11=19 vl( 8 )－a12=16 vl( 8 )－a13=19 vl( 9 )－a14=21 l-e 4 0 4 0 6 0 3 0 0 2 3 0 2 0 ( 4 ) e( i )等于l( i )的活动( 即开始时间剩余量为0的活动 )为关键活动，所以图中的关键活动为：< 0,2>，< 2,3>， < 3,4>，< 3,6>，< 4,6>，< 6,8>，< 8,9>。 所以图中的关键路径有两条：

① < 0,2>，< 2,3>，< 3,4>，< 4,6>，< 6,8>，< 8,9> ② < 0,2>，< 2,3>，< 3,6>，< 6,8>，< 8,9> 它们的路径长度都为23。 所有关键活动所构成的图为：

( 5 )关键活动决定整个工程的持续时间。所以加速关键活动< 0,2>，< 2,3>， < 3,4>，< 3,6>，< 4,6>，< 6,8>，< 8,9>可以整个工程提前完成。

本文来源：https://www.bwwdw.com/article/ozw8.html