(3) 按行存储时，元素a14的第一个字节的地址；=1000+(8x1+4)x6=1072 (4) 按列存储时，元素a47的第一个字节的地址；=1000+(7x6+4)x6=1276
【11， 6，1】（选自《数据结构题集》6.1，必做题）
已知一棵树边的集合为{
（3）哪个是结点G的双亲？ （4）哪些是结点G的祖先？ （5）哪些是结点G的孩子？ （6）哪些是结点E的子孙？
（7）哪些是结点E的兄弟？哪些是结点F的兄弟？ （8）结点B和N的层次号分别是什么？ （9）树的深度是多少？
（10）以结点C为根的子树的深度是多少？ 解：这棵树为:
所以，根结点为A；
叶子结点是D，M，N，F，J，K，L； 结点G双亲为C；
结点G的祖先为A，C； 结点E的子孙为I，M.，N；
结点E的兄弟有D，结点F的兄弟有G，H； 结点B和N的层次号分别是2，5； 树的深度是5；
以结点C为根的子树的深度为3。
【12， 6，1】（选自《数据结构题集》6.4，选做题）
一棵深度为H的满k叉树有如下性质第H层上的结点都是叶子节点，其余各层上每个结点都有k棵非空子树。如果按层次顺序从1开始对全部结点编号，问： （1）各层的结点数目是多少？
（2）编号为p的父结点（若存在）的编号是多少？
（3）编号为p的结点的第i个儿子结点（若存在）的编号是多少？
（4）编号为p的结点有右兄弟的条件是什么？其右兄弟的编号是多少？ 解：（1）各层的结点数为
（n＝1，2，…，H）；
时，通过归纳可得，编号为a的结到
，则编号为p的结点的父
（2）首先，p＝1时，没有父结点，点，它的所有子结点的编号为从
结点为「；
（3）由上可得，第i个儿子结点的编号为；
（4）p有右兄弟，即p不为最右的结点，条件为编号为p＋1。
，右兄弟的
【13， 6，2】（选自《数据结构题集》6.5，选做题）
已知一棵度为k的树中有个度为1 的结点，个度为2 的结点，…，个度为k的结点，问该树中有多少个叶子结点？ 解：设结点总数为n，则有n= n0+n1+n2+…+nk，
因为除了根结点外，所有结点都有边进入，所以有n=B+1,而 B = 1*n1+2*n2+…+k*nk = ∑i*ni ,所以有 n0+n1+n2+…+nk = ∑i*ni + 1 n0 = ∑（i-1）*ni + 1
【14， 6，3】（选自《数据结构题集》6.13，必做题）
假设n和m为二叉树中的两结点，用“1”、“0”、“Φ”（分别表示肯定、恰恰相反或者不一定）填写下表： 已知 \\ 问 前序遍历时 中序遍历时 后序遍历时 答: n在m前？ n在m前？ n在m前？ 1 1 1 n在m左方 0 0 0 n在m右方 1 0 Φ n是m祖先 0 1 Φ n是m子孙 注：如果（1）离a和b最近的共同祖先p存在，且（2）a在p的左子树中，b在p的右子树中，则称a在b的左方（即b在a的右方）
【15， 6，3】（选自《数据结构题集》6.14，选做题）
找出所有满足下列条件的二叉树：
（a）它们在先序遍历和中序遍历时，得到的结点访问序列相同； （b）它们在后序遍历和中序遍历时，得到的结点访问序列相同； （c）它们在先序遍历和后序遍历时，得到的结点访问序列相同； 答：（a）除叶子结点外所有结点都只有右孩子的树或只有根结点的树； （b）只有根结点以及除叶子结点外所有结点都只有左孩子的树； （c）只有根结点的树。
【16， 6，4】（选自《数据结构题集》6.19，必做题）
分别画出和下列树对应的各二叉树：
答：用孩子兄弟表示法将树表示成二叉树，二叉树的左右结点分别为第一个孩子结点和下一个兄弟结点，表示如下：
【17， 6，3】（选自《数据结构题集》6.23，选做题）
画出和下列已知序列对应的树T
树的先根次序访问序列为GFKDAIEBCHJ； 树的后根次序访问序列为DIAEKFCJHBG。 解：对应的树如下：
【18， 6，5】（选自《数据结构题集》6.26，必做题）
假设用于通信的电文仅有8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10.试为这8个字母设计哈夫曼编码。使用0－7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。
解：哈夫曼编码树如下：
所以编码如下： 0.07 0.19 0.02 0.06 0.32 0.03 0.21 0.10 字母 1010 00 10000 1001 11 10001 01 1011 编码 带权路径长度WPL＝0.19×2＋0.21×2＋0.02×5＋0.03×5＋0.06×4＋0.07×4＋0.10×4＋0.32×2＝2.61，而采用等长编码时，每个字母至少3位，故带权路径长度WPL＝3.采用哈夫曼编码可以大大提高通信信道的利用率。
【19， 6，2】（选自《数据结构题集》6.29，必做题）
假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出该树。
解：该二叉树如下：
【20， 7，2】（选自《数据结构题集》7.1，必做题）
已知如右图所示的有向图，请给出该图的
（1） 每个顶点的入/出度； （2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表； （5） 强连通分量。
答：（1）各顶点的入/出度如下：
顶点1：3/0；顶点2：2/2；顶点3：1/2；顶点4： 1/2； 顶点5：2/1；顶点6：2/3。 （2）邻接矩阵如下： 1 2 3 4 1 0 0 0 0 2 1 0 0 1 3 0 1 0 0 4 0 0 1 0 5 1 0 0 0 6 1 1 0 0 （3）邻接表如下： 5 0 0 0 1 0 1 6 0 0 1 1 0 0
（4） 逆邻接表如下：