数组广义表答案 及 二叉树习题及答案.doc

数组广义表答案 及 二叉树习题及答案.doc 习题4参考答案 一、单项选择题 1. A 2. A 3. A 4. B 5. BA 6. C 7. A 8. A 9. C 10. C 11. C 12. C 13. B 14. D 15.A 16.B 二、填空题 1. 线性结构，顺序结构，以行为主序，以列为主序 2. i×n+j个元素位置 3. 5，3 4.((0，2，2)，(1，0，3)，(2，2，-1)，(2，3，5)) 5. n×(n+1)/2 6. e 7. 41 8. head(head(tail(Ls))) 9.(d-c+1)×(d-c+1)×(d-c+1) 223311 10. 913 三、判断题 1.× 2.? 3.? 4.? 5.× 6.× 7.? 8.× 9.× 10.? 11.? 12.? 13.× 14.? 15.? 第5章 树 习题5 一、单项选择题 1. 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为( )个。 A. 4 B. 5 C. 6 D. 7 2. 假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( )个。 A. 15 B. 16 C. 17 D. 47 3. 假定一棵三叉树的结点数为50，则它的最小高度为( )。 A. 3 B. 4 C. 5 D. 6 4. 在一棵二叉树上第4层的结点数最多为( )。 A. 2 B. 4 C. 6 D. 8 5. 用顺序存储的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点R[i]若有左孩子，其左孩子的编号为结点( )。 A. R[2i+1] B. R[2i] C. R[i/2] D. R[2i-1] 6. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A. 24 B. 48 C. 72 D. 53 7. 线索二叉树是一种( )结构。 A. 逻辑 B. 逻辑和存储 C. 物理 D. 线性 8. 线索二叉树中，结点p没有左子树的充要条件是( )。 A. p->lc=NULL B. p->ltag=1 C. p->ltag=1 且p->lc=NULL D. 以上都不对 9. 设n , m 为一棵二叉树上的两个结点，在中序遍历序列中n在m前的条件是( )。 A. n在m右方 B. n在m 左方 C. n是m的祖先 D. n是m的子孙 10. 如果F是由有序树T转换而来的二叉树，那么T中结点的前序就是F中结点的( )。 A. 中序 B. 前序 C. 后序 D. 层次序 11. 欲实现任意二叉树的后序遍历的非递归算法而不必使用栈，最佳 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 是二叉树采用( )存储结构。 A. 三叉链表 B. 广义表 C. 二叉链表 D. 顺序 -2- 12. 下面叙述正确的是( )。 A. 二叉树是特殊的树 B. 二叉树等价于度为2的树 C. 完全二叉树必为满二叉树 D. 二叉树的左右子树有次序之分 13. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序( )。 A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对 14. 已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为( )。 A. 1 B. 2 C. 3 D. 4 15. 根据先序序列ABDC和中序序列DBAC确定对应的二叉树，该二叉树( )。 A. 是完全二叉树 B. 不是完全二叉树 C. 是满二叉树 D. 不是满二叉树 二、判断题 1. 二叉树中每个结点的度不能超过2，所以二叉树是一种特殊的树。 ( ) 2. 二叉树的前序遍历中，任意结点均处在其子女结点之前。 ( ) 3. 线索二叉树是一种逻辑结构。 ( ) 4. 哈夫曼树的 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 点个数(多于1时)不能为偶数。 ( ) 5. 由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。 ( ) 6. 树的后序遍历与其对应的二叉树的后序遍历序列相同。 ( ) 7. 根据任意一种遍历序列即可唯一确定对应的二叉树。 ( ) 8. 满二叉树也是完全二叉树。 ( ) 9. 哈夫曼树一定是完全二叉树。 ( ) 10. 树的子树是无序的。 ( ) 三、填空题 1. 假定一棵树的广义表表示为A(B(E)，C(F(H，I，J)，G)，D)，则该树的度为_____，树的深度为_____，终端结点的个数为______，单分支结点的个数为______，双分支结点的个数为______，三分支结点的个数为_______，C结点的双亲结点为_______，其孩子结点为_______和_______结点。 2. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有_______个。 3. 对于一个有n个结点的二叉树，当它为一棵________二叉树时具有最小高度，即为_______，当它为一棵单支树具有_______高度，即为_______。 4. 由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为___。 5. 在一棵二叉排序树上按_______遍历得到的结点序列是一个有序序列。 6. 对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为_______个，其中_______个用于链接孩子结点，_______个空闲着。 -3- 7. 在一棵二叉树中，度为0的结点个数为n，度为2的结点个数为n，则n=______。 200 8. 一棵深度为k的满二叉树的结点总数为_______，一棵深度为k的完全二叉树的结点总数的最小值为_____，最大值为______。 9. 由三个结点构成的二叉树，共有____种不同的形态。 10. 设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为____。 11. 一棵含有n个结点的k叉树，______形态达到最大深度，____形态达到最小深度。 12. 对于一棵具有n个结点的二叉树，若一个结点的编号为i(1?i?n)，则它的左孩子结点的编号为________，右孩子结点的编号为________，双亲结点的编号为________。 13. 对于一棵具有n个结点的二叉树，采用二叉链表存储时，链表中指针域的总数为_________个，其中___________个用于链接孩子结点，_____________个空闲着。 14. 哈夫曼树是指________________________________________________的二叉树。 15. 空树是指________________________，最小的树是指_______________________。 16. 二叉树的链式存储结构有______________和_______________两种。 17. 三叉链表比二叉链表多一个指向______________的指针域。 18. 线索是指___________________________________________。 19. 线索链表中的rtag域值为_____时，表示该结点无右孩子，此时______域为指向该结点后继线索的指针。 20. 本节中我们学习的树的存储结构有_____________、___________和___________。 四、应用题 1. 已知一棵树边的集合为{，，，，，，，，，，，，}，请画出这棵树，并回答下列问题: (1)哪个是根结点, (2)哪些是叶子结点, (3)哪个是结点g的双亲, (4)哪些是结点g的祖先, (5)哪些是结点g的孩子, (6)哪些是结点e的孩子, (7)哪些是结点e的兄弟,哪些是结点f的兄弟, (8)结点b和n的层次号分别是什么, (9)树的深度是多少, (10)以结点c为根的子树深度是多少, 2. 一棵度为2的树与一棵二叉树有何区别。 3. 试分别画出具有3个结点的树和二叉树的所有不同形态, 4. 已知用一维数组存放的一棵完全二叉树:ABCDEFGHIJKL，写出该二叉树的先序、中序和后序遍历序列。 5. 一棵深度为H的满k叉树有如下性质:第H层上的结点都是叶子结点，其余各层 -4- 上每个结点都有k棵非空子树，如果按层次自上至下，从左到右顺序从1开始对全部结点编号，回答下列问题: (1)各层的结点数目是多少, (2)编号为n的结点的父结点如果存在，编号是多少, (3)编号为n的结点的第i个孩子结点如果存在，编号是多少, (4)编号为n的结点有右兄弟的条件是什么,其右兄弟的编号是多少, 6. 找出所有满足下列条件的二叉树: (1)它们在先序遍历和中序遍历时，得到的遍历序列相同; (2)它们在后序遍历和中序遍历时，得到的遍历序列相同; (3)它们在先序遍历和后序遍历时，得到的遍历序列相同; 7. 假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请写出该二叉树的后序遍历序列。 8. 假设一棵二叉树的后序序列为DCEGBFHKJIA，中序序列为DCBGEAHFIJK，请写出该二叉树的后序遍历序列。 9. 给出如图5-14所示的森林的先根、后根遍历结点序列，然后画出该森林对应的二叉树。 10(给定一组权值(5，9，11，2，7，16)，试设计相应的哈夫曼树。 A G K L C I B H M D E F J O N 图5-14 五、算法设计题 1. 一棵具有n个结点的完全二叉树以一维数组作为存储结构，试设计一个对该完全二叉树进行先序遍历的算法。 2. 给定一棵用二叉链表表示的二叉树，其中的指针t指向根结点，试写出从根开始，按层次遍历二叉树的算法，同层的结点按从左至右的次序访问。 3. 写出在中序线索二叉树中结点P的右子树中插入一个结点s的算法。 4. 给定一棵二叉树，用二叉链表表示，其根指针为t，试写出求该二叉树中结点n的双亲结点的算法。若没有结点n或者该结点没有双亲结点，分别输出相应的信息;若结点n有双亲，输出其双亲的值。 -5- 习题5参考答案 一、单项选择题 1. C 2. B 3. C 4. D 5. B 6. D 7. C 8. B 9. B 10. B 11. A 12. D 13. A 14. B 15. A 二、判断题 1.× 2.? 3.× 4.? 5.× 6.? 7.? 8.? 9.× 10.× 三、填空题 1. 3，4，6，1，1，2，A，F，G 2. n+1 log(1)n，3. 完全，，最大，n ，，2,, 4. 55 5. 中序 6. 2n，n-1，n+1 7. n+1 2kk-1k8. 2-1，2，2-1 9. 5 h10. 2-1 11. 单支树，完全二叉树 12. 2i，2i+1，i/2(或，i/2，) 13. 2n，n-1，n+1 14. 带权路径长度最小 15. 结点数为0，只有一个根结点的树 16. 二叉链表，三叉链表 17. 双亲结点 18. 指向结点前驱和后继信息的指针 19. 1，RChild 20. 孩子表示法，双亲表示法，长子兄弟表示法 四、应用题 1. 解答: 根据给定的边确定的树如图5-15所示。 a 其中根结点为a; c b 叶子结点有:d、m、n、j、k、f、l; c是结点g的双亲; g e f h d i i j k m n -6- 图5-15 a、c是结点g的祖先; j、k是结点g的孩子; m、n是结点e的子孙; e是结点d的兄弟; g、h是结点f的兄弟; 结点b和n的层次号分别是2和5; 树的深度为5。 2. 解答: 度为2的树有两个分支，但分支没有左右之分;一棵二叉树也有两个分支，但有左右 之分，左右子树不能交换。 3. 解答: 略 4. 解答: 先序序列:ABDHIEJKCFLG 中序序列:HDIBJEKALFCG 后序序列:HIDJKEBLFGCA 5. 解答: i-1(1)第i层上的结点数目是m。 (2)编号为n的结点的父结点如果存在，编号是((n-2)/m)+1。 (3)编号为n的结点的第i个孩子结点如果存在，编号是(n-1)*m+i+1。 (4)编号为n的结点有右兄弟的条件是(n-1)%m?0。其右兄弟的编号是n+1。 6. 解答: (1)先序序列和中序序列相同的二叉树为:空树或者任一结点均无左孩子的非空二叉树; (2)中序序列和后序序列相同的二叉树为:空树或者任一结点均无右孩子的非空二叉树; (3)先序序列和后序序列相同的二叉树为:空树或仅有一个结点的二叉树。 7. 解答:后序序列:ACDBGJKIHFE 8. 解答:先序序列:ABCDGEIHFJK 9. 解答: 先根遍历:ABCDEFGHIJKLMNO 后根遍历:BDEFCAHJIGKNOML 森林转换成二叉树如图5-16所示。 10. 解答:构造而成的哈夫曼树如图5-17所示。 A 50 B G 30 20 C H K D I L 9 11 14 16 E J M 7 7 F N 5 2 O 图5-16 图5-17 -7- 五、算法设计题 1. 解答:这个问题可以用递归算法，也可用非递归算法，下面给出的为非递归算法。假设该完全二叉树的结点以层次为序，按照从上到下，同层从左到右顺序编号，存放在一个一维数组R[1..n]中，且用一个有足够大容量为maxlen的顺序栈作辅助存储，算法描述如下: preorder (R) //先序遍历二叉树R int R[n]; { int root; SqStack *s; //s为一个指针栈，类型为seqstack，其中包含top域和数组data s->top= -1; //s栈置空 root=1; while ((root<=n) && (s->top>-1)) { while (root<=n) { printf(R[root]); s->top++; s->data[s->top]=root; root=2*root; } if (s->top>-1) //栈非空访问，遍历右子树 { root=s->data[s->top]*2+1; s->top--; } } } 2. 解答:考虑用一个顺序队que来保存遍历过程中的各个结点，由于二叉树以二叉链表存储，所以可设que为一个指向数据类型为bitree的指针数组，最大容量为maxnum，下标从1开始，同层结点从左到右存放。算法中的front为队头指针，rear为队尾指针。 levelorder (BiTree *t) //按层次遍历二叉树t { BiTree *que[maxnum]; int rear,front; if (t!=NULL) { front=0; //置空队列 rear=1; que[1]=t; do -8- { front=front%maxsize+1; //出队 t=que[front]; printf(t->data); if (t->lchild!=NULL) //左子树的根结点入队 { rear=rear%maxsize+1; que[rear]=t->lchild; } if (t->rchild!=NULL) //右子树的根结点入队 { rear=rear%maxsize+1; que[rear]=t->rchild; } }while (rear= =front); //队列为空时结束 } } 3. 解答:设该线索二叉树类型为bithptr，包含5个域:lchild，ltag，data，rchild，rtag。 insert(p, s) //将s结点作为p的右子树插入 BiThrNode *p,*s; { BiThrNode *q; if (p->rtag= =1) //无右子树，则有右线索 { s->rchild=p->rchild; s->rtag=1; p->rchild=s; p->rtag=0; } else { q=p->rchild; while(q->ltag= =0) //查找p所指结点中序后继，即为其右子树中最左下的结点 q=q->lchild; q->lchild=p->rchild; s->rtag=0; p->rchild=s; } s->lchild=p; //将s结点的左线索指向p结点 s->ltag=1; } 4. 解答:利用一个队列来完成，设该队列类型为指针类型，最大容量为maxnum。算法中 的front为队头指针，rear为队尾指针，若当前队头结点的左、右子树的根结点不是所求结 点，则将两子树的根结点入队，否则，队头指针所指结点即为结点的双亲。 -9- parentjudge(t,n) BiTree *t; int n; { BiTree *que[maxnum]; int front,rear; BiTree *parent; parent=NULL; if (t) if (t->data= =n) o parent!”); //n是根结点，无双亲 printf(“n else { front=0; //初始化队列 rear=1; que[1]=t; //根结点进队 do { front=front%maxsize+1; t=que[front]; if((t->lchild->data= =n)|| (t->rchild->data= =n)) //结点n有双亲 { parent=t; front=rear; printf(“parent”,t->data); } else { if (t->lchild!=NULL) //左子树的根结点入队 { rear=rear%maxsize+1; que[rear]=t->lchild; } if (t->rchild!=NULL) //右子树的根结点入队 { rear=rear%maxsize+1; que[rear]=t->rchild; } } }while(rear= =front); //队空时结束 if (parent = =NULL) printf(“结点不存在”); } } -10-