例题选讲.ppt

例3-3 设矩阵A是一个对称矩阵，为了节省存储空间，将其下三角部分按行序存放在一维数组B[1..n(n-1)/2]中，对任一下三角部分元素aij(i=j)，在一维数组B的下标位置k的值是（ ）。 A. i(i-1)/2+j-1 B. i(i-1)/2+j C. i(i+1)/2+j-1 D. i(i+1)/2+j 例3-4 设稀疏矩阵如下图所示： 要求给出该稀疏矩阵下列各表示法的图示。 （1）三元组顺序表； （2）三元组单链表； （3）带行指针数组的三元组链表； （4）三元组十字链表。 树和二叉树 习题选讲 例6-1 树最适合用来表示（ ）。 A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 例6-2 解答：一棵含有n个结点的k叉树，能达到最大深度的是单支树，其深度为n；深度最小的是完全k叉树。 一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各为多少？ 例6-3 解答：设该满二叉树的高度为h，由于满二叉树中叶子结点都集中在最底层，所以该满二叉树的叶子结点的个数为： 则总的结点个数为： 得： 具有n个结点的满二叉树的叶子结点的个数是多少？ 例6-4 解答：由于本题求二叉树的结点数最多是多少，第7层共有27-1=64个结点，已知有10个叶子结点，则其余54个结点均为分支结点。它在第8层上有108个叶子结点。所以该二叉树的结点数最多可达27-1+108=235。 注意：本题未说明完全二叉树的高度，但根据题意，只能有8层。 已知完全二叉树的第7层有10个叶子结点，则整个二叉树的结点数最多是多少？ 例6-5 解答：设二叉树度为0和2的结点数及总的结点数分别为n0， n2， n。则 n= n0 + n2 (1) 再设二叉树的分支数为B，除根结点外，每个结点头上都有一个分支。则 B=n-1 (2) 度为0的是叶子，没有分支，而度为2的结点有两个分支。则 n=2 n2 +1 (3) 由（1）,（3）式得n2= n0-1,并由（1）,（2）式得 B=2（ n0 -1 ） 证明：一棵二叉树中的结点的度或为0或为2，则二叉树的分支数为2(n0-1),其中n0是度为0的结点的个数。 例6-6 下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（ ）。（2010） ? 例6-7 在一棵度为 4 的树 T 中，若有 20 个度为 4 的结点，10 个度为 3 的结点，1 个度为 2 的结点，10 个度为 1 的结点，则树 T 的叶结点个数是（ ）。（2010） A. 41 B. 82 C. 113 D. 122 解答： 四叉树结点的度数均不大于4，结点总数应等于度为i的结点数(记为ni)之和： N=no+n1+n2+n3+n4 (1) 因为度为 i的结点有i个孩子，而根结点不是任何结点的孩子，故结点总数为： N=n1+2n2+3n3+4n4+1 (2) 由上面的(1)、(2)式得到： no=n2+2n3+3n4+1=1+20+60+1=82 例6-8 对 n(n 大于等于 2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（ ）（2010） A.该树一定是一棵完全二叉树 B.树中一定没有度为 1 的结点 C.树中两个权值最小的结点一定是兄弟结点 D.树中任一非叶结点的权值一定不小于下一任 一结点的权值 例6-9 若一棵完全二叉树有768个结点，则该二叉树中叶子结点的个数是（ ）。（2011） A. 257 B. 258 C. 384 D. 385 解答：由性质4可得本完全二叉树的高度为10。第10层上的结点个数为768-(29-1)=257(这些全为叶子结点)；第9层上的非叶子结点为(257-1)/2+1=129;则第9层上的叶子结点个数为： 29-1-129=127;则叶子结点总数为257+127=384。 例6-10 若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1，则该二叉树的中序遍历序列不会是（ ）。（2011） A. 1,2,3,4