6假设Q[0,5]是一个循环队列，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入对，请指出其元素，并说明理由。
d, e, b, g, h入队 d, e出队
i , j , k , l , m入队 b出队
n, o, p, q, r入队
⑴假设在树中，结点x是结点y的双亲时，用(x,y)来表示树边。已知一棵树的树边集合为{ (e,i), (b,e), (b,d), (a,b), (g,j), (c,g), (c,f), (h,l), (c,h), (a,c) } ，用树型表示法表示该树，并回答下列问题：
① 哪个是根结点? 哪些是叶子结点? 哪个是g的双亲? 哪些是g的祖先? 哪些是g的孩子? 那些是e的子孙? 哪些是e的兄弟? 哪些是f的兄弟?
② b和n的层次各是多少? 树的深度是多少? 以结点c为根的子树的深度是多少?
①a是根结点；mndfjkl是叶结点；c是g的双亲；c,a是g的祖先；j,k是g的孩子；imn是e的子孙；d是e的兄弟；g,h是f的兄弟；
②b的层次是2；n的层次是5；树的深度是5；以c为根的子树深度是3；
5
⑵一棵深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对全部结点编号，问： ①各层的结点数是多少?
②编号为i的结点的双亲结点(若存在)的编号是多少?
③编号为i的结点的第j个孩子结点(若存在)的编号是多少?
④编号为i的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少?
三、算法理解
1、已知P结点是某双向链表的中间节点，画图并写出下列操作的语句序列。 （1）在P结点后插入S结点。 （2）删除P结点的后继结点Q。 结点结构如下： Prior Data Next （其中Prior、Data、Next分别为前驱节点指针、数据域、后继节点指针。）
6
答：（1）P->Next->Prior=S; S->Next=P->Next; P->Next=S; S->Prior=P; (2) Q=P->Next; P->Next=P->Next->Next; P->Next->Prior=P; free(Q);
4、假设一棵二叉树的前序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK。请画出该树，并写出后序序列。（要求写出分析过程）
E(B(A,D(C,)),F(,H(G,I(,K(J,)))))
答：该树如下
首先，前序序列是以-（根节点）（左子树）（右子树）来排列的，所以在前序树最左边的节点一定是树的根节点，这样我们就可以确定E是根节点。
再来看中序序列，我们知道了E是根节点，便可以从中序序列知道（ABCD）（FGHIJK）分别是E节点的左右子树，再通过前序树得到（BADC）（FHGIKJ）的根节点分别是B与F，以此类推可求得整个树的结构。
后序序列： ACDBGJKIHFE
7、(8分) 假设用于通讯的电文由A、B、C、D、E、F、G、H这8个字母组成，字母在电文中出现的频率为{ 0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.1 }，画出这8个字母哈夫曼树并设计哈夫曼编码。
a：0010 b：10 c：00000 d：0001 e：01 f：00001 g：11 h：0011
7
7、假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率百分比分别为7，19，2，6，32，3，21，10。画出这8个字母哈夫曼树，标出其哈夫曼编码。
答案如上
⑶设有如图6-27所示的二叉树。
①分别用顺序存储方法和链接存储方法画出该二叉树的存储结构。 ②写出该二叉树的先序、中序、后序遍历序列。 答：
①顺序存储结构：
链式存储结构
8
