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

[习题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出发，要据普里姆算法求出最小生成树的过程中，把依次得到的各条边 …… 此处隐藏：4625字，全部文档内容请下载后查看。喜欢就下载吧 ……