nbhkdz.com冰点文库

数据结构作业9


作业 9 选择题
1.下面关于二叉树的结论正确的是______ _____。 A. 二叉树中,度为 0 的结点个数等于度为 2 的结点个数加 1。 B. 二叉树中结点个数必大于 0。 C. 完全二叉树中,任何一个结点的度,或者为 0,或者为 2。 D. 二叉树的度是 2。 2.设 X 是树 T 中的一个非根结点,B 是 T 所对应得二叉树,在 B 中,X 是其双亲的右孩

子, 下列结论正确的是______ ______。 A.在树 T 中,X是其双亲的第一个孩子。 B.在树 T 中,X一定无右边兄弟。 C.在树 T 中,X一定是叶子结点。 D.在树 T 中,X一定有左边兄弟。 3.一棵三叉树中,已知度为 3 的结点数等于度为 2 的结点数,且树中叶结点的数目为 13, 则度为 2 的结点数目为______ _____。 A.4 B.2 C.3 D. 5 4.设 n、m 为一棵二叉树上的两个结点,在中序遍历时,n 在 m 之前的条件是_____ ______。 A.n 在 m 右方 B.n 是 m 祖先 C.n 在 m 左方 D.n 是 m 子孙 5.对一个满二叉树,m 个树枝,n 个结点,深度为 h,则__________。 h A.n=h+m B.h+m=2n C.m=h-1 D.n=2 -1 6.一棵有 n 个结点的 k 叉树,树中所有结点的度之和为_________。 2 A.n-1 B.kn C.n D.2n 7.以二叉链表作为二叉树的存储结构,在有 n 个结点的二叉链表中(n>0),链表中空链域的 个数为_____ ______。 A.2n-1 B.n-1 C.n+1 D.2n+1 8.设森林中有 3 棵树,其中第 1、第 2 和第 3 棵树的结点个数分别为 n1、n2、n3,则与森林 对应的二叉树中根结点的右子树上的结点个数是_____ ______。 A.n1 B.n1+ n2 C. n3 D.n2+n3 9. 将含有 150 个结点的完全二叉树从根这一层开始, 每一层从左到右依次对结点进行编号, 根结点的编号为 1,则编号为 69 的结点的双亲结点的编号为_____ ______。 A.33 B.34 C.35 D.36 10.在一棵二叉树结点的先序序列、中序序列、后序序列中,所有叶子结点的先后顺序____ _____。 A.都不相同 B.先序和中序相同,而与后序不同 C.完全相同 D.中序和后序相同,而与先序不同 11.如果将给定的一组数据作为叶子数值,所构造出的二叉树的带权路径长度最小,则该树 称为______ ______。 A.哈夫曼树 B.平衡二叉树 C.二叉树 D.完全二叉树 12.树的先根序列和其对应的二叉树的 是一样的,树的后根序列和其对应的二叉树 的 是一样的。 A.先序序列 B.中序序列 C.后序序列 D.按层次遍历序列 13.若一个具有 N 个顶点,K 条边的无向图是一个森林(N>K),则该森林中必有_ ___棵树。 A.K B.N C.N-K D. 1

14. 欲实现任意二叉树的后序遍历的非递归算法而不必使用栈结构, 最佳方案是二叉树采用 _____ ______存储结构。 A.三叉链表 B.广义表 C.二叉链表 D.顺序 15.一棵二叉树满足下列条件:对任一结点,若存在左、右子树,则其值都小于它的左子树 上所有结点的值,而大于右子树上所有结点的值。现采用_____ _____遍历方式就可以得到 这棵二又树上所有结点的递减序列。 A.先序 B.中序 C.后序 D.层次 16.对含有_________个结点的非空二叉树,采用任何一种遍历方式,其结点访问序列均相 同。 A.0 B.1 C.2 D.不存在这样的二叉树 17.对_____ ______进行相应的遍历仍需要栈的支持。 A.先序线索树 B.中序线索树 C.后序线索树 D.A 与 B 18. 已知 n 个结点的二叉树具有最小路径长度时, 其深度为 k, 那么第 k 层上的结点数为____ ____。 k-2 k-1 k k-1 A. n-2 +1 B. n-2 +1 C. n-2 +1 D. n-2

判断题
1.按中序遍历二叉树时,某个结点(有右子树)的直接后继是它的右子树中第一个被访问的 结点。 2.有 1 个以上结点的二叉树,已知先序和后序遍历序列,能唯一确定一棵二叉树。 3.完全二叉树中,若一个结点没有左孩子,则它必然是叶子结点。 4.将一棵树转换成二叉树后,根结点没有左子树。 6.用二叉树的先序遍历和中序遍历可以导出二叉树的后序遍历。 7.若一个叶子结点是某二叉树中序遍历序列的最后一个结点,那么它也是该二叉树的先序 遍历序列的最后一个结点。

填空题
1. 森林 T 转化为二叉树 B,B 中某结点在森林中为叶子结点的条件为_____ _____。 2.N 个结点的二叉树按某种遍历规则对结点从 1 到 N 依次递增编号,如果 (1) 任一结点的编号等于它的左子树中的最小编号减 1,则为______ _____遍历; (2) 某结点右子树中最小编号等于左子树中的最大编号加 1,则为_____ _____遍历。 3.一棵高度为 H 的满 K 叉树,按层次从 1 开始编号,则; (1) 第 i 层结点的数目为:__________; (2) 编号为 n 的结点的父结点的编号为:__________; (3) 编号为 n 的结点的第 i 个孩子的编号为:____ ______; (4) 编号为 n 的结点有右兄弟的条件是:_____ ______,右兄弟的编号为_____ _______。 4.如果某二叉树中有 30 个叶结点,另有 30 个结点仅有一个孩子结点,则该二叉树中共有 ___________个结点。 5.由带权为 3,9,6,2,5 的 5 个叶子结点构成一棵哈夫曼树,则带权路径长度为______。 6.设 F 是一个森林,B 是由 F 转换得到的二叉树,F 中有 n 个非终端结点,则 B 中右指针域 空的结点有____个。 7.设 n 为哈夫曼树的叶子结点数目,则该哈夫曼树共有___________个结点。

8.n 个结点的完全二叉树,编号最大的非叶结点是__________号结点,编号最小的叶结点 是_____ _____号结点。 9.完全二叉树的第 7 层有 8 个结点,则此完全二叉树的叶子结点数为___。768 个结点的完 全二叉树有___个叶子结点?19 个结点的哈夫曼树有______个叶子结点?


数据结构作业9

数据结构作业9_数学_高中教育_教育专区。作业 9 选择题 1.下面关于二叉树的结论正确的是___ ___。 A. 二叉树中,度为 0 的结点个数等于度为 2 的结点个...

3126010018 吴泽世 数据结构作业 9

3126010018 吴泽世 数据结构作业 9_计算机软件及应用_IT/计算机_专业资料。1. 已知顺序表中存储的序列{19, 14, 22, 1, 66, 21, 83, 27, 56, 13 检索...

《数据结构》第九章作业参考答案

数据结构》第一章作业... 《数据结构》第三章作业... 《数据结构》第五章...解:判定树应当描述每次查找的位置: 5 2 1 3 4 6 7 8 9 10 A S L =...

数据结构作业9

同系列文档 数据结构作业61/2 相关文档推荐 数据结构课后作业 9-1 暂无评价 4页 1财富值 2012年9月份考试数据结构第... 4页 5财富值 数据结构作业(二) ...

数据结构作业系统_第九章答案

数据结构作业系统_第九章答案_IT/计算机_专业资料。数据结构anyview作业系统各章所有答案 9.26② 试将折半查找算法改写成递归算法。 实现下列函数: int BinSearch(...

数据结构 课后作业 9

数据结构 课后作业 9_理学_高等教育_教育专区。南昌大学理工班数据结构作业《数据结构》课后作业课后作业 第 九课 算法编程(用 C 编程,要求程序可以成功运行,程序...

数据结构第9章作业

数据结构第9章作业_理学_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档数据结构第9章作业_理学_高等教育_教育专区。9.3 void LinkedList_Select_Sort(...

数据结构第九、十章 作业答案

数据结构第九、十章 作业答案_理学_高等教育_教育专区。第九章 查找 一、填空题 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 表中与 k 相等的...

数据结构9习题及答案

数据结构9习题及答案_计算机软件及应用_IT/计算机_专业资料。第九章 查找 一、...数据结构-第9章习题 8页 1下载券 数据结构第7,9章作业习题... 22页 2下载...

数据结构书面作业练习题6-9

数据结构书面作业练习题6-9_理学_高等教育_教育专区。数据结构作业 习题六 6.1 单项选择题 树和二叉树 1. 如图 8.7 所示的 4 棵二叉树,_C___不是完全...