数据结构(C语言版)第五章回答. doc
第五章1、二维数组A【8】【10】是按照行优先顺序存储在存储器中的数组，已知A【0】【0】的起始存储位置为1000，每个数组元素占用4个存储单元，(1) A【4】【5】的起始A【4】【5】的开头存储位置是1000(10*45 ) *41180； )2)起始存储器位置为1184的数组元素的下标。 存储位置为1184的数组元素的下标为4 (行下标)，6 )列下标)。 2、描述以下广义表Dc )、e、a、b、c、d )的图形表示和它们的存储器表示。 省略，参考第52节应用题第5题的分析和解答。 3、知道a是稀疏矩阵，尝试从时间和空间的角度采用两种不同的存储结构(二维排列和三元组表)实现ai，J运算的优缺点求解。 在疏散行列a中采用2维排列存储器时，需要n*n个存储单元，一旦求出1合1，由于是a【i】【I】随机存取，所以速度很快。 但是，在使用三元组表情况下，如果设非零要素的个数为t，则在需要3t3个存储单元(t个成分存储各非零要素的行值、列值、要素值)的同时，需要3个存储稀疏矩阵a的行数、列数、非零要素的个数的存储单元，根据二维排列进行记录然而，在求(1in )时，必须扫描整个三元组表，找出矩阵值相等的非零元素的总和，其时间性能比采用二维阵列有时差。 4、利用三元组存储任意稀疏序列时，什么条件下可以节约存储空间？ 设m行n列稀疏矩阵中非零元素的个数为t，满足关系3*tm*n时，利用三元组记忆稀疏序列时，可以节约记忆空间。 5、求以下各广义表的操作结果。 )1) GetHeada，b，c，d GetHeada，b，c，da )2) GetTaila，b，c，db，c，c，d )3) GetHeada e、b、d、a、b、g、j、g、k、c、f， 回答下一个问题(1)根节点是哪个)叶节点是哪个)3) g的父母是哪个)4) g的祖先是哪个)5) g的孩子是哪个)6) e的子孙是哪个) e的兄弟是哪个) f的兄弟是哪个)节点b和省略证明。 3、知道度m的树中有度1的节点，度2的节点度m的节点。 询问那棵树里有多少片叶子见第62节应用题的第一题。 4、已知某完全二叉树有100个节点，试着求这个二叉树的叶树。 这个二叉树的树叶树有50度。 5、已知完全二叉树的第6段有5个叶。 尝试描绘所有满足该条件的完全二叉树，并指出节点最多的树叶的数量。 根据完全二叉树的定义，(1) 6层为最上层，有5片叶的) 7层为最上层，6层有5片叶。 6、深l的k叉树具有以下性质：第l层的节点都是叶的节点，其馀各层分别有k棵非空子树。 在按层次顺序从1开始对所有节点编号情况下，(1)第I个节点的数量是几个)2)有编号n的节点的父母的节点)的编号是几个)编号n的节点的第I个孩子的节点)的情况下的编号是几个)4)编号n )3)先后顺序列与先后顺序列相同。 有点。 8、证明一棵k叉树的叶节点数与非叶节点数m之间满足以下关系(k-1 ) m1 .证明总点数nm，且满足n-1km，故(k-1 ) m1 . 9、一棵二叉树的中序列和后序列已知分别为BDCEAFHG和DECBHGFA，绘制该二叉树。 导出其第一个导线测量序列。 顺序扫描序列是ABCDEFGH。 L10，将图622所示的森林变换为二叉树。
GANMOBHCPRQKJIFED图622将森林转换为二叉树二叉树见第62节应用问题中的第7题。 11、写出图622所示森林的前序序列和后序序列。 见第62节应用问题的第七题。 12、一系列的数列(15、8、10、21、6、19、3 )分别表示字符a、b、c、d、e、f、g的出现频度，试着生成哈夫曼树，给出各字符的编码值。 见第62节应用问题第10题。