习 题及答案(2)

图解：

10a110a10b∧10d10e11∧10a10i10j∧10k∧

⑶ 设有二维数组a[6][8]，每个元素占相邻的4个字节，存储器按字节编址，已知a的起始地址是1000，试计算：

① 数组a的最后一个元素a[5][7]起始地址； ② 按行序优先时，元素a[4][6]起始地址； ③ 按行序优先时，元素a[4][6]起始地址。 LOC(a[5][7])=LOC(a[0][0])+47*4=1188

LOC(a[4][6])=LOC(a[0][0])+(4?8+6)?4=1152 LOC(a[4][6])=LOC(a[0][0])+（6*6+4）?4=1160

⑸ 设有稀疏矩阵B如下图所示，请画出该稀疏矩阵的三元组表和十字链表存储结构。

图解：

12331-3384432462521865467573-3

图中未标记空指针，作业中请注意标记

习 题 六

⑴ 假设在树中， 结点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为根的子树的深度是多少? ⑵ 一棵深度为h的满k叉树有如下性质： 第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。 如果按层次顺序(同层自左至右)从1开始对全部结点编号，问：

① 各层的结点数是多少?

② 编号为i的结点的双亲结点(若存在)的编号是多少?

③ 编号为i的结点的第j个孩子结点(若存在)的编号是多少?

④ 编号为i的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少? ⑶ 设有如图6-27所示的二叉树。

① 分别用顺序存储方法和链接存储方法画出该二叉树的存储结构。 ② 写出该二叉树的先序、中序、后序遍历序列。

⑷ 已知一棵二叉树的先序遍历序列和中序遍历序列分别为ABDGHCEFI和GDHBAECIF，请画出这棵二叉树，然后给出该树的后序遍历序列。

⑸ 设一棵二叉树的中序遍历序列和后序遍历序列分别为BDCEAFHG和DECBHGFA ，请画出这棵二叉树，然后给出该树的先序序列。

⑹ 已知一棵二叉树的中序遍历序列和后序遍历序列分别为dgbaekchif和gdbkeihfca，请画出这棵二叉树对应的中序线索树和后序线索树。

⑺ 以二叉链表为存储结构，请分别写出求二叉树的结点总数及叶子结点总数的算法。 ⑻ 设图6-27所示的二叉树是森林F所对应的二叉树，请画出森林F。 ⑼ 设有一棵树，如图6-28所示。

① 请分别用双亲表示法、孩子表示法、孩子兄弟表示法给出该树的存储结构。 ② 请给出该树的先序遍历序列和后序遍历序列。 ③ 请将这棵树转换成二叉树。

⑽ 设给定权值集合w={3,5,7,8,11,12} ，请构造关于w的一棵huffman树，并求其加权路径长度WPL 。

⑾ 假设用于通信的电文是由字符集{a, b, c, d, e, f, g, h}中的字符构成， 这8个字符在电文中出现的概率分别为{0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10} 。

① 请画出对应的huffman树(按左子树根结点的权小于等于右子树根结点的权的次序构造)。 ② 求出每个字符的huffman编码

习 题 七

⑴ 分析并回答下列问题：

① 图中顶点的度之和与边数之和的关系?

② 有向图中顶点的入度之和与出度之和的关系?

③ 具有n个顶点的无向图，至少应有多少条边才能确保是一个连通图? 若采用邻接矩阵表示，则该矩阵的大小是多少?

④ 具有n个顶点的有向图，至少应有多少条弧才能确保是强连通图的? 为什么? ⑵ 设一有向图G=(V,E)，其中V={a,b,c,d,e} ， E={, , , , , ,, , }

① 请画出该有向图，并求各顶点的入度和出度。 ② 分别画出有向图的正邻接链表和逆邻接链表。 ⑶ 对图7-27所示的带权无向图。 ① 写出相应的邻接矩阵表示。 ② 写出相应的边表表示。 ③ 求出各顶点的度。

⑷ 已知有向图的逆邻接链表如图7-28所示。

① 画出该有向图。

② 写出相应的邻接矩阵表示。

③ 写出从顶点a开始的深度优先和广度优先遍历序列。 ④ 画出从顶点a开始的深度优先和广度优先生成树。

⑸ 一个带权连通图的最小生成树是否唯一?在什么情况下可能不唯一? ⑹ 对于图7-27所示的带权无向图。

① 按照Prime算法给出从顶点2开始构造最小生成树的过程。 ② 按照Kruskal算法给出最小生成树的过程。 ⑺ 已知带权有向图如图7-29所示，请利用Dijkstra算法从顶点V4出发到其余顶点的最短路径及长度，给出相应的求解步骤。

⑻ 已知带权有向图如图7-30所示，请利用Floyd算法求出每对顶点之间的最短路径及路径长度。

⑼ 一个AOV网用邻接矩阵表示，如图7-31。用拓扑排序求该AOV网的一个拓扑序列，给出相应的步骤。

⑽ 拓扑排序的结果不是唯一的，请给出如图7-32所示的有向图的所有可能的拓扑序列。 ⑾ 请在深度优先搜索算法的基础上设计一个对有向无环图进行拓扑排序的算法。

⑿ 设计一个算法利用图的遍历方法输出一个无向图G中从顶点Vi到Vj的长度为S的简单路径，设图采用邻接链表作为存储结构。

⒀ 假设一个工程的进度计划用AOE网表示，如图7-33所示。 ① 求出每个事件的最早发生时间和最晚发生时间。 ② 该工程完工至少需要多少时间? ③ 求出所有关键路径和关键活动。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库习 题及答案(2)在线全文阅读。