当前位置:首页 >> 理化生 >>

数据结构课堂习题2


第 6 章 树和二叉树 6.1 设树 T 的度为 4,其中度为 1,2,3 和 4 的结点个数分别为 4,2,1,1

则 T 中的叶子

数为( D ) A.5 B.6 C.7 D.8 6.2 在下述结论中,正确的是( D ) ①只有一个结点的二叉树的度为 0; ②二叉树的度为 2; ③二叉树的左右子树可任意 交换; ④深度为 K 的完全

二叉树的结点个数小于或等于深度相同的满二叉树。 A.①②③ B.②③④ C.②④ D.①④ 6.3 设森林 F 对应的二叉树为 B,它有 m 个结点,B 的根为 p,p 的右子树结点个数为 n,森林 F 中第一棵树的结点个数是( A ) A.m-n B.m-n-1 C.n+1 D.条件不足,无法确定 1. 2. 3. 如果结点 A 是结点 B 的双亲,而且结点B有4个兄弟,则结点 A 的度是(D) A)2 B)3 C)4 D)5 设有一棵二叉树,其1度结点有 m 个,2度结点有 n 个,则该二叉树的结点总数为(D) A)m+n B)2*m+n C)m+2*n D)m+2*n+1 设有一棵二叉树,其先序遍历序列是:ABCDEFG,中序遍历序列是:CBDAFEG,则该二叉 树的后序遍历序列是(A) A)CDBFGEA B)CDFGBEA C)CDBAFGE D)CDBFEGA 设有 13 个值,由它们组成一棵哈夫曼树,则该哈夫曼树中结点个数共有(D)。 A)13 B)12 C)26 D)25 设电文中出现的字母为 A、B、C、D 和 E,每个字母在电文中出现的次数分别为:6,23, 3,5 和 12,按哈夫曼编码,则字母 C 的编码应是 (C) A)10 B)110 C)1110 D)111 已知一棵二叉树的先序遍历序列为 EFHIGJK,中序遍历序列为 HFIEJGK,则该二叉树根 的右子树的根是(G) A)E B)F C)G D)J 设结点 A 有左孩子结点 B,右孩子结点 C,则在先序遍历、中序遍历、后序遍历这三种 基本遍历序列中 B 一定是 C 的(A) A)前驱 B)后继 C)相邻结点 D)不相邻结点 填空题 采用二叉链式存储结构,具有 n 个结点的二叉树中,一共有 2n 个指针域,其中 n+1 个指针域为空。 i-1 一棵非空的二叉树,其第 i 层上最多有_2 ____个结点。 k 满二叉树是一棵深度为 k 的且恰好有_2 -1____个结点的二叉树。 将一棵完全二叉树按层次编号,对任一编号为 i 的结点有:如该结点有左孩子,则其编 号为 2i ;如该结点有右孩子,则其编号为 2i+1 。 设一棵二叉树中只有叶子结点和左、右子树都非空的结点,如果叶子结点的个数是 m, 则左、右子树都非空的结点个数是_m-1____ 设有一棵树(如图 6-5 所示) ,请回答下列问题:

4. 5.

6.

7.

四. 1. 2. 3. 4. 5. 6.

根结点是_A_; 叶子结点有_D H I J F K;E的双亲是_B_;F的祖先是 _C A_;G的孩子是_K_;D的孩 子是_无; E的子孙有__H I J__; D的兄弟是 E__;B的兄弟是_C _; 结点H的层数是_4_; 树的深度 是_4_;E为根的子树深度是_2; 这棵树的度是_3_。 7. 现有一表达式 ( a+b )*c-d / e,写出该表达式的波兰式_-*+abc/de___,以及逆 波兰式_ab+c*de/-_____。

6.4 一棵深度为 H 的满 k 叉树有如下性质:第 H 层上的结点都是叶子结点,其余各层上每个结点都有 k 棵 非空子树。如果按层次顺序从 1 开始对全部结点编号,问: (1) 总结点数目是多少? (2) 编号为 p 的结点的父结点(若存在)的编号是多少? (3) 编号为 p 的结点的第 i 个儿子结点(若存在)的编号是多少? 解:(1) (k -1)/(k-1) (2)如果 p 是其双亲的最小的孩子(右孩子) ,则 p 减去根结点的一个结点,应是 k 的整数倍,该整数 即为所在的组数,每一组为一棵满 k 叉树,正好应为双亲结点的编号。如果 p 是其双亲的最大的孩子(左 孩子) ,则 p+k-1 为其最小的弟弟,再减去一个根结点,除以 k,即为其双亲结点的编号。 综合来说,对于 p 是左孩子的情况,i=(p+k-2)/k;对于 p 是右孩子的情况,i=(p-1)/k (3)结点 p 的右孩子的编号为 kp+1,左孩子的编号为 kp+1-(k-1)=k(p-1)+2,第 i 个孩子的编号为 k(p-1)+2+i-1=kp-k+i+1。 6.5 已知一棵度为 k 的树中有 n1 个度为 1 的结点, n2 个度为 2 的结点,…, nk 个度为 k 的结点,问该树 中有多少个叶子结点? 解:根据树的定义,在一颗树中,除树根结点外,每个结点有且仅有一个前驱结点,也就是说,每个 结点与指向它的一个分支一一对应,所以除树根结点之外的结点数等于所有结点的分支数,即度数,从而 可得树中的结点数等于所有结点的度数加 1。总结点数为
H

1 ? n1 ? 2n2 ? 3n3 ? ... ? knk
而度为 0 的结点数就应为总结点数减去度不为 0 的结点数的总和,即

n0 ? 1 ? n1 ? 2n2 ? 3n3 ? ... ? knk ? (n1 ? n2 ? n3 ? ... ? nk ) ? 1 ? ? (i ? 1)ni
i ?1

k

6.8 证明:一棵满 k 叉树上的叶子结点数 n0 和非叶子结点数 n1 之间满足以下关系:

n0 ? ?k ? 1?n1 ? 1

解: 一棵满 k 叉树的最后一层(深度为 h)的结点数(叶子结点数)为 n0

? k h ?1 , 其总结点数为

k h ?1 , k ?1

则非叶子结点数 n1

?

kn ? 1 k h ?1 ? n0 ? 0 ? n0 ,从而得 k ?1 k ?1

n0 ? (k ? 1)n1 ? 1

6.19 分别画出和下列树对应的各个二叉树: 解:

6.24 解:本题应注意下列转换: 树 先根 后根 森林 先序 中序 二叉树 先序 中序

6.42 解: // 求二叉树中叶子结点的数目 Status POLeafNodeNum(int& i,BiTree& T) { if(T){ if(!T->lchild && !T->rchild) i++; POLeafNodeNum(i,T->lchild); POLeafNodeNum(i,T->rchild); } return OK; }


相关文章:
数据结构(C语言版)第2版习题答案—严蔚敏
数据结构(C语言版)第2习题答案—严蔚敏_计算机软件及应用_IT/计算机_专业资料...66 II 第1章 绪论 1 .简述下列概念:数据、数据元素、数据项、数据对象、数据...
数据结构C语言版第2版课后习题答案
数据结构C语言版第2版课后习题答案_计算机软件及应用_IT/计算机_专业资料 暂无评价|0人阅读|0次下载|举报文档数据结构C语言版第2版课后习题答案_计算机软件及应用...
数据结构课后习题答案
数据结构课后习题答案_理学_高等教育_教育专区。高等学校精品资源共享课程 十二五普通...1.2 数据结构涉及哪几个方面? 【答】:数据结构涉及三个方面的内容,即数据的...
数据结构课后习题(第2章)
第 1 页共 5 页 网络工程 2011 级 1 班、计算机科学与技术 2011 级 2 班《算法与数据结构》课后习题(第 2 章) 三、单项选择(请将正确答案的代号填写在...
数据结构课程 课后习题答案
填空题 (1)数据结构包括数据的 ① 、数据的 ② 和数据的 ③ 这三个方面的内容。 答:①逻辑结构 ②存储结构 ③运算 (2)数据结构按逻辑结构可分为两大类,...
数据结构课后习题答案
数据结构课后习题答案_工学_高等教育_教育专区。数据结构 第1 章绪论 1 .简述...( 2 )链式存储结构 顺序存储结构要求所有的元素依次存放在一片连续的存储空间中...
2套通用期末数据结构试题及答案
2套通用期末数据结构试题及答案_其它课程_高中教育_教育专区。数据结构试卷(一) 一、单选题(每题 2 分,共 20 分) 1. 栈和队列的共同特点是( )。 A.只允...
数据结构课习题参考答案
5页 2财富值 南邮数据结构课后习题课 25页 免费 初中物理运动经典习题及详... 5页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请...
数据结构课后习题答案
数据结构课后习题答案_理学_高等教育_教育专区。1 绪论 1.1 回答下列概念:数据...2.存储密度:顺序表的存储密度大,而链表的存储密度小。 3.存储分配方式:顺序表...
数据结构第二章课后答案
数据结构章课后答案_从业资格考试_资格考试/认证_教育专区。2.4 已知顺序表...数据结构章考试题库... 57页 免费 数据结构课后答案 18页 免费 数据结构...
更多相关标签: