Pop(T,d); Push(S,d);
}
3. 写出下列程序段的输出结果。 (1)void main(){ Stack S; char x,y; InitStack(S); x=’i’; y=’s’;
Push(S,x); Push(S,’r’); Push(S,y); Pop(S,x); Push(S,’h’); Push(S,x); Pop(S,x); Push(S,’c’);
while (!StackEmpty(S)) {Pop(S,y);printf(y);} printf(x); }
(2)void main(){
Queue Q; InitQueue(Q); char x=’e’, y=’c’;
EnQueue(Q, ‘a’); EnQueue(Q, ‘d’); EnQueue(Q, y); DeQueue(Q, x); EnQueue(Q, x); DeQueue(Q, x); EnQueue(Q, ‘r’);
while (!QueueEmpty(Q)) { DeQueue(Q, y); printf(y); } printf(x); }
4. 已知L是带头结点的单链表。试写一算法求该单链表的长度。 5. 已知L是带头结点的单链表。试写一算法在该链表上查找值为x的元素。
6. 将带头结点的L中的第i个数据元素删除。
7. 在带头结点的L中第i个元素之前插入数据元素e 。 8. 正位序输入n个元素的值，建立带头结点的单链表L。
9. 已知线性表中的元素以值递增有序排列，并以带有头结点的单链表作存储结构。试写一算法删除表中所有值大于mink且小于maxk的元素，同时释放被删除的结点空间。 10. LA和LB是两个数据元素按升序排列的单链表，将LA和LB合并为有序单链表LC。写出这两个有序链表合并的算法。
}
6
第六章习题
一、
单选或填空题
1. 已知完全二叉树的第7层上有10个叶子结点，则整个二叉树的结点数最多是
A) 73 B) 63 C) 235 D) 245
2. 300个结点的完全二叉树的叶结点有 个。 3．一个具有1025个结点的二叉树的高h为____。
A）11 B）10 C）11至1025之间 D）10至1024之间
4. 将一棵有100个节点的完全二叉树从上到下，从左到右依次对节点进行编号，根节点的编号为1，则编号为49的节点的右孩子编号为（ ）。 A．99 B．98 C．50 D．48 5．把如右图所示的树转换成二叉树时，C是（ ） A. A的左子女 B. A的右子女 C. B的左子女 D. B的右子女
6. 设森林F中有3棵树，其结点个数分别是n1、n2和n3，则与森林对应的二叉树根结点的右子树上的结点个数是 。
A) n1-1 B)n1+n2 C) 0 D) n2+n3
7. 在一颗度为3的树T中，若有10个度为3的结点，5个度为2的结点，则树T的叶结点有 个。 A) 15 B) 26 C) 25 D) 40
8. 一棵二叉树中序遍历结果为DCBAEFG，后序遍历结果为DCBGFEA。则此二叉树先序遍历的结果应为
A) ABCDEFG B)ABECFDG C)AEBFCGD D)不能确定
9. 将一棵树t 转换为孩子—兄弟链表表示的二叉树h，则t 的后根遍历是h 的
A）先序遍历 B）中序遍历 C）后序遍历 C）层序遍历
10.现有一段电文共100个字符，其中A出现50次，B出现20次，C出现5次，D出现10次，E出现15次。现对这5个字符进行哈夫曼编码，则其平均码长为 。
11. 现有一段电文共100个字符，其中A出现35次，B出现27次，C出现8次，D出现20次，E出现10。现对这5个字符进行哈夫曼编码（注：建立哈夫曼树时权值小的为左子树，权值大的为右子树），则字符E的编码为 。
7
A) 011 B) 001 C) 1101 D) 1111
解答题
1. 某二叉树的中序遍历结果为DEFABCG；后序遍历结果为FEDCBAG。
（1）画出此二叉树，并给出其先序遍历的结果。 （2）画出与这棵二叉树对应的树（森林）。
2. 已知一个二叉树的先序遍历序列为：ABDGIECFH；中序遍历序列为：DIGBEAFHC。 （1）画出该二叉树
（2）画出下图所示森林对应的二叉树。
K A A BCDLA A A A EFGA A A JIHA A A
3. 某二叉树层序序列为abcdefghij，中序序列为bgdhjaecif。 （1）画出该二叉树；
（2）画出该二叉树的后序后继线索树； （3）画出该二叉树对应的树或森林。
4. 已知某通讯用电文仅有A、B、C、D、E、F六个字符构成，其出现的频率分别为26，8，17，11，28，10，请首先建立哈夫曼树，然后给出六个字符的哈夫曼编码（注：建立哈夫曼树时权值小的为左子树，权值大的为右子树）。
5. 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。
（1） 试为这8个字母设计赫夫曼编码。
（2） 试设计另一种由二进制表示的等长编码方案。 （3） 对于上述实例，比较两种方案的优缺点。 三、算法题
二、
8
1. 以二叉链表作为二叉树的存储结构，编写以下算法： （1）求先序序列为k的结点的值 （2）求二叉树中叶子结点的数目 （3）交换所有结点的左右子树 （4）求二叉树的深度
9
第七章 习题
一． 单选或填空题
1. 若某有向图的邻接矩阵A只有0和1两种元素，其中aij＝1
表示有向图中存在弧
A) 邻接矩阵中第i行元素之和 B) 邻接矩阵中第i列元素之和
C) 邻接矩阵中对角线元素之和 D) 以上均不正确 2. 使用邻接表作为某无向图的存储结构，若无向完全图中有n个顶点，则邻接表中必存在 个表结点。 2
A)n B)2n C)n(n-1) D) 2n-1
3. 一个含有n个顶点和e条边的无向图，在其邻接矩阵存储结构中共有（）零元素。 22
A．e B．2e C．n-e D．n-2e
4．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。
A．1/2 B．1 C．2 D．4
5．下列关于图的叙述中，正确的是（ ） Ⅰ、 回路是简单路径
Ⅱ、存储稀疏图，用邻接矩阵比邻接表更省空间 Ⅲ、若有向图中存在拓扑序列，则该图不存在回路 A．仅Ⅱ B．仅Ⅰ、Ⅱ C．仅Ⅲ D．仅Ⅰ、Ⅲ
6. 若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为__________。
A．A,B,C,D,E,F B．A,B,C,F,D,E C．A,B,D,C,E,F D．A,C,B,F,D,E 7．在有n个结点的无向图中，其边数最多为 。 8. 对于具有n个结点的连通图，它的最小生成树中有 条边。 2
A)n B)n-1 C)n(n-1) D) n(n-1)/2 9. 关键路径是AOE网中
A）从源点到汇点的最长路径 B）从源点到汇点的最短路径
C）最长回路 D）最短回路 10. 以下关于图的描述中，正确的是 A) n个顶点的无向完全图有n(n2?1)条边。
10