16．如果树中各结点的各子树从左至右是有序排列，不可互换的，则称该树为______。 17．如果树中各结点的各子树无排列顺序，即可以互换位置，则称为该树为_________。 18．n(n≥0)棵互不相交的树的集合称为______________________。 19．二又树（Binary Tree）是结点的有限集合，这个集合或者是空，或者是由一个根结点和__________的称为______________和____________的二叉树构成。
20．二叉树第i层上最多有____________个结点。
21．深度为k的二又树最多有____________个结点(k≥l)。
22．在任意二叉树中，叶子结点的数目(即度为0的结点数)等于度为2的结点数____________。
23．一棵深度为k且具有2k-1个结点的二叉树称为__________。这类二叉树的特点是，二叉树中每一层结点的个数都是______________的个数。
24．_________是那种在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者所缺少的结点都在右边。
25．具有n个结点的完全二叉树的深度是_______________。
26．对于一棵有n个结点的完全二叉树的结点进行编号（自上而下，自左至右），则对任一结点 i（l≤i≤n），如果结点i=l，则结点i是二叉树的____________，无双亲；如果结点i>l，则其双亲Parent(i)的序号是结点_______________；如果2i≤n，则结点i的左孩子Lchild(BT,，i）是_________，否则结点i无左孩子(结点i必为叶子结点)；如果2i＋l≤n，则结点i的右孩子 RChild（BT，i）的序号是____________；否则该结点无右孩子。
27．二叉树的顺序存储结构是用_________________存储二叉树的数据元素。
28．____________是指按照某条搜索路径访问树中的某个结点，使得树中每个结点均被访问一次，而且仅被访问一次。
29．先序遍历二叉树的操作定义为：若二叉树为空，则为空操作；否则进行如下操作：访问二叉树____________；先序遍历二叉树____________；先序遍历二叉树_________。
30．中序遍历二叉树的操作定义为：若二叉树为空，则为空操作；否则进行如下操作：中序遍历二叉树__________；访问二又树__________；中序遍历二又树____________。
31．后序遍历二叉树的操作定义为：若二叉树为空，则为空操作；否则进行如下操作：后序遍历二叉树___________；后序遍历二叉树_________；访问二叉树_____________。
32．线索二叉树（Threaded Binary Tree）是充分利用二义链表的 n+1个空的指针域作为线索来标志每一个结点的________和__________信息。当某个结点有左孩子的时候，使其___________指向其左孩子，无左孩子的时候，使其左指针域指向该结点的___________；当某个结点有有孩子的时候，使其右指针域指向该结点的__________，无右孩子的时候，使其有指针域指向该结点的_____________。
33．线索二叉树的线索链表中，指向结点前驱和后继的指针称为___________；加上线索的二叉树称为_____________；对二叉树以某种次序进行遍历使其成为线索二叉树的过程称为_______________________。
34．树的存储结构常见的有____________、____________和________________。
35．树的先序遍历过程如下：若树为空，则进行空操作；若树非空，则：访问树的__________；依次先序遍历树的__________。
36．树的后序遍历过程为：若树为空，则进行空操作；若树非空，则：依次后序遍历__________；访问_________________。
37．森林的先序遍历过程为：若森林非空，则： （1）访问森林中第一棵树的___________。 （2）先序遍历第一棵树中_____________。
（3）先序遍历_______________________。
38．森林的后序遍历过程为：若森林非空，则：
（l）后序遍历森林中第一棵树的_______________。 （2）访问第一棵树的_________________________。 （3）后序遍历_______________________________。
39．从树中一个结点到另一个结点之间的_________称为这两个结点的路径。 40．路径上的分支数目称为______________。
41．树的路径长度是指从树根到每一结点的__________________。
42．将树中的结点赋上一个有着某种意义的实数，称此实数为该结点的____________。 43．树的带权路径长度为树中所有叶子结点的____________。
44．哈夫曼树（Huffman Tree）又称___________。它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL__________________。
45，所谓前缀编码是指在所有对字符的编码中，任何一个字符都不是____________。 46．已知完全二叉树的第八层有8个结点，则其叶子结点数是__________________。 47．在有n个叶子结点的哈夫曼树中，总结点数是___________。
48．已知完全二又树的第7层有10个叶子结点，则整个二又树的结点数最多是__________。 49．已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为__________。 50．一棵树T采用二叉链表BT存储，如果树T中某结点为叶子结点，则在二叉链表BT中所对应的结点一定满足___________________。
51．在二叉链表中，判断某指针P所指结点为叶子结点的条件是__________。 52．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是___________。 53．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是______________。 54．3个结点可构成___________________棵不同形态的树。
55．已知完全二叉树的第七层有8个结点，则其叶子结点数是______________.
56．将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结 点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为____________。
57．若要对某二叉排序树进行遍历，保证输出的所有结点序列按键值递增次序排列， 应对该二叉树采用_______________遍历法。
1. 有限
2. 根、根、根、子树 3. 结点、记录 4. 子树数目 5. 最大值
6. 分支结点、非终端结点 7. 度为零的结点
8. 后继结点、子树的根 9. 双亲结点 10. 子孙结点 11. 祖先结点 12. 同一双亲
13. 第一、第二、第k+1 14. 堂兄弟 15. 最大层次 16. 有序树
17. 无序树 18. 森林
19. 两棵互不相交、左子树、右子树 20. 2i-1 21. 2k-1 22. 加1
23. 满二叉树、最大结点 24. 完全二叉树 25. ?log2n??1
26. 根、?i/2?、2i、2i+1
27. 一组连续的存储单元 28. 遍历二叉树
29. 根结点、左子树、右子树 30. 左子树、根结点、右子树 31. 左子树、右子树、根结点
32. 前驱、后继、左指针域、直接前驱结点、右孩子、直接后继结点 33. 线索、线索二叉树、线索化
34. 双亲表示法、孩子表示法、孩子兄弟表示法 35. 根结点、各子树
36. 根的各子树、根结点
37. 根结点、根结点的子树、除第一棵树之外剩余的树构成的森林 38. 根结点的子树、根结点、除第一棵树之外剩余的树构成的森林 39. 分支
40. 路径长度
41. 路径长度之和 42. 权
43. 带权路径长度之和
44. 最优二叉树、最小的二叉树 45. 另一个字符的前缀 46. 68 47. 2n-1 48. 74 49. 129
50. 左子树为空
51. (p->lchild==nil)&&(p->rchild==nil) 52. 69 53. 99 54. 2 55. 36 56. 98 57. 中序
三、判断题
1．完全二叉树的某个结点若无左孩子，则它必然是叶结点。（ ） 2．存在这样一种二叉树，对它采用任何次序的遍历结果相同。（ ） 3．度为二的树称为二叉树。（× ） 4．二叉树中不存在度大于2的结点。（ ）
5．当二叉树中某个结点只有一棵子树的时候，无左右子树之分。（× ） 6．任何一棵二叉树都可以不用栈实现前序线索树的前序遍历。（ ） 7．哈夫曼编码是一种前缀编码，不允许出现两个字符编码相同的情况。（ ） 8．完全二叉树某结点有右子树，则必然有左子树。（ ） 9．前序遍历一棵二叉树的结点就可以得到排好序的结点序列。（× ） 10．将一棵拥有子树的树转换为二叉树后，根结点可能没有左子树。（× ） 11．根据二叉树的前序遍历和中序遍历可以得到二又树的后序遍历。（ ） 12．哈夫曼树是带权路径长度最短的二叉树。（ ） 13．哈夫曼树上权值较大的结点离根较远。（× ）
14．中序遍历森林与后序遍历与森林相对应的二叉树结果相同。（× ）
15．在二叉树中，具有一个孩子的结点，在中序遍历序列中，没有后继子女结点。 （× ）
16．先序遍历森林与先序遍历相对应的二叉树结果不同。（× ）
17．若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。（× ） 18．二叉树只能采用二叉链表来存储。（× ） 19．给定结点数的平衡二叉树的高度是惟一的。（× ）
1. 正确：根据完全二叉树定义可以知道，若完全二叉树无左孩子，则它必然无右孩子。 2. 正确：二叉树只有一个结点的时候。 3. 错误：二叉树子树还有左右次序之分。 4. 正确。 5. 错误。 6. 正确。 7. 正确。
8. 正确：根据完全二叉树定义可以知道，
9. 错误：中序遍历一棵二叉树的结点就可以得到排好序的结点序列。 10. 错误：将一棵拥有子树的树转换为二叉树后，根结点必然有左子树。 11. 正确。 12. 正确。
13. 错误：哈夫曼树的路径上权值较大的结点离根较近。
14. 错误：后序遍历森林与中序遍历与森林相对应的二叉树结果相同。
15. 错误：在二叉树中，具有一个左孩子的结点，在中序遍历序列中，没有后继子女结点。 16. 错误：前序遍历森林与前序遍历与森林相对应的二叉树结果相同。
17. 错误：任一非叶子结点的度为2也不能保证满足满足满二叉树的定义。 18. 错误：也可以采用顺序存储和三叉链表等形式进行表示。 19. 错误：给定结点数的平衡二叉树的高度不一定是惟一的。
四、综合题
1．一棵树表达成如下形式：
D＝{A，B，C，D，E，F，G， H，I，J，K，L，M，N，O}
R=＜A，B＞，＜A，C＞，＜A，D＞，＜B，E＞，＜B，F＞，＜C，G＞，＜D，H＞，＜D，I＞，＜D，J＞，＜K，F＞，＜K，L＞，＜F，M＞，＜I，N＞，＜I，O＞｝
其中D为结点集合，R为边的集合。请根据以上内容回答以下问题： (1) 画出这棵树。
(2) 该树的根结点是哪一个？ (3) 哪些是叶子结点？ (4) F结点的双亲是谁？ (5) F结点的祖先是哪些？ (6) F结点的孩子是哪些？ (7) F结点的兄弟是哪些？ (8) F结点的堂兄弟是哪些？ (9) F结点的度是多少？ (10)F结点的层次是多少？ (11)D结点的子孙有哪些？
(12) 以结点D为根的子树度是多少？ (13) 以结点D为根的子树层是多少？ (14) 该树的层是多少？ (15) 该树的度是多少？
2．画出图6-1中树的二叉树表示形式。
（a） （b） （c） 图6-l
3．已知某二叉树的先序遍历的结果是：A，B，D，QC，E，H，L，I，K，M，F和J，它的中序遍历的结果是：QD，B，A，L，H，E，K，LM，C，F和J，请画出这棵二叉树，并且写出该二叉树后序通历的结果。
4．写一个将一棵二叉树复制给另一棵二又树的算法。
5．已知—个二叉树用二叉链表表示，其根指针为t，请写一个算法，从根结点开始按层次通历该二叉树，同层的结点接从左到右的次序进行访问。
6．已知一棵二叉树的先序遍历序列和中序遍历序列，请写出根据二又树先序遍历序列和中序遍历序列构造一棵二叉树的算法。
7．假设一棵哈夫曼树共有n0个叶子结点，试证明树中共有2no-l个结点。
8．假设通信用的报文由9个字母A、B、C、D、E、F、G、H和I构成，它们出现的频率分别是：10、20、5、15、8、2、3、7和30。请用这9个字母出现得频率作为权值求：
（l）设计一棵哈夫曼树。
（2）计算其带权路径长度WPL值。 （3）写出每个字符的哈夫曼编码。 1.
（1）该树的图形如图B-1所示。
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构习题集包含答案(5)在线全文阅读。
相关推荐：