发布时间 : 星期三 文章数据结构更新完毕开始阅读
典型题目解析线索二叉树
48、具有n个结点的线索二叉树共有（ ）个线索。
49、一棵左子树为空的二叉树在前序线索化后，其中空链域的个数是（ ）。 50、一棵左右子树均不为空的二叉树在前序线索化后，其中空链域的个数是（ ）。 51、二叉树在线索化后仍不能有效求解的问题是（ ）
A、前序线索二叉树中求前序后继 B、中序线索二叉树中求中序后继 C、中序线索二叉树中求中序前驱 D、后序线索二叉树中求后序后继 52、关于线索二叉树，下列说法中不正确的是（ ）
A、中序线索二叉树中，若结点有右孩子，则其后继是它的右子树的左分支末端的结点。
B、线索二叉树利用二叉树的n+1个空指针来存放其前驱和后继信息
C、在线索二叉树中，每个结点通过线索都可以直接找打它的前驱和后继 D、中序线索二叉树中，若结点有左孩子，则其前驱是它的左子树的右分支末端结点。
53、线索二叉树是一种（ ）结构
A、逻辑B、逻辑和存储C、物理D、线性 54、（ ）线索二叉树的遍历仍需要栈的支持
典型题目解析树、森林和二叉树
56、讨论树、森林和二叉树的关系，目的是为了（ ） A、借助二叉树上的运算方法去实现对树的一些运算
B、将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题
C、将树、森林转换成二叉树 D、体现一种技巧，实际意义不大 57、深度为h的满二叉树对应的森林由（ ）棵树构成。 A、1 B、log2h C、h/2 D、h
58、设F是一个森林，B是由F转换得到的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。 A、n-1 B、n C、n+1 D、n+2
59、设x是树T中的一个非根结点，B是T所对应的二叉树。在B中，x是其双亲的右孩子，则下列结论正确的是（ ）
A、在树T中，x是其双亲的第一个孩子 B、在树T中，x 一定无右兄弟 C、在树T中，x 一定是叶子结点 D、在树T中，x一定有左兄弟 60、已知一个森林的前序序列为ABCDEFGHIJKL MNO，后序序列为CDEBFHIJGAMLONK，求此森林。
61、如果在表示树的孩子兄弟链表中有6个空的左指针域，7个空的右指针域，5个结点左右指针域都为空，则该二叉树叶子结点个数为多少？
17
典型题目解析哈弗曼树
62、一棵huffman树中共有215个结点，对其进行huffman编码，可以得到多少个不同的编码？
63、下述编码中（ ）不是前缀编码。
A、(00,01,10,11) B、(0,1,00,11) C、(0,10,110,111) D、(1,01,000,001) 64、为5个使用频率不等的字符设计哈弗曼编码，不可能的方案是（ ）。 A、000,001,010,011,1 B、0000,0001,001,01,1 C、000,001,01,10,11 D、00,100,101,110,111
65、设计哈弗曼编码的长度不超过4，若已经对两个字符编码为1和01，则最多还可以为（ ）个字符编码。 A、2 B、3 C、4 D、5
66、假设字符集{a,b,c,d,e}中各字符出现的频率分别为{4,21,7,14,31}，为该字符集构造哈弗曼编码，则字符集编码的总码数为（ ）。 A、12 B、13 C、14 D、15
67、若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点个数为（ ） A、n-1 B、[n/m]-1 C、[(n-1)/(m-1)] D、[(n+1)/(m+1)] -1
68、已知某电文中出现了10种不同的字符，每个字符出现的频率分别为{A:8,B:5,C:3,D:2, E:7,F:23,G:9,H:11,I:2,J:35}，现在对这段电文用三进制进行编码（编码由0、1、2组成），问电文编码的总长度至少有多少位？
典型题目解析历年统考真题2011
4、一棵完全二叉树有768个结点，则该二叉树中叶子结点的个数是（ ） A、257 B、258 C、384 D、385
5、若一棵二叉树的前序遍历序列和后序遍历序列分别是1234和4321，则该二叉树的中序遍历序列是（ ）
A、1234 B、2341 C、3241 D、4321
6、已知一棵树有2011个结点，其中叶结点个数为116，该树对应的二叉树中无右孩子的结点个数为（ ）
A、115 B、116 C、1895 D、1896 典型题目解析历年统考真题2010
3、下列线索二叉树中，符合后序线索二叉树的是（ ）
18
4、在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的的结点，10个度为1的结点，则树T的叶子结点个个数为（ ） A、41 B、82 C、113 D、122
5、对于n个权值均不相同的字符构造huffman树，下列关于该树的描述中，错误的是（ ）
A、该树一定是一棵完全二叉树 B、该树一定没有度为1的结点 C、树中两个权值最小的结点一定是兄弟结点
D、树中任一非叶子结点的权值一定不小于下一层任一结点的权值。 典型题目解析历年统考真题2009
3、给定二叉树如图所示，设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树，若遍历后的结点序列为3175624，则其遍历方式为（ ） A、LRN B、NRL C、RLN D、RNL
4、下列二叉排序树中，满足平衡二叉树的是（ ）
5、一直以棵完全二叉树的第6层有8个叶子结点，则该完全二叉树的结点个数最多是（ ）
A、39 B、52 C、111 D、119
6、森林转换成为的二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是（ ）
1父子关系2兄弟关系3u的父节点和v的父结点是兄弟关系 A、只有2 B、1和2 C、1和3 D、123
典型题目解析 递归 1、递归的本质
递归：调用程序自身的算法，称之为递归。特点是思路明确、代码简洁，在树、图等问题中有广泛的应用。同时，递归算法纷繁复杂，且实现过程对用户透明，使得理解变得较困难。
数据的结构关系虽然有四种，但实质上数据间的关系只有前驱、后继的顺序关系。其常见的物理结构为顺序结构和链式结构，几乎所有的数据结构都可以用链式结
19
构描述。这就使得四种结构关系在逻辑和物理上都可以有统一的表现形式。 对于线性关系，可以理解成由第一个元素和剩余的元素组成，而剩余的元素又是一个相对较小的线性关系。
对于树形结构，是由根和除根之外的若干棵子树组成。
对于图形结构可以理解成某一顶点及所有后继结点为起始点形成的子图所构成。 综上所述，这些数据结构都是由某一个元素和所有后继构成的相同的数据结构所组成。这说明，数据结构的定义基本上是递归的，递归是众多数据结构构造和逻辑意义上的统一体。 2、递归算法的模型
递归算法由两部分组成： ⑴最小问题，称为基本项；
⑵原问题与子问题的关系，称为递归项（递归项包含两部分内容，一是可以继续分解的子问题；二是不能继续划分的子问题，称为有解子问题）。一般形式如下： if（最小问题） 基本项行为； else { 有解子问题的处理；
可继续划分的子问题1，2?n；}
最小子问题决定了递归的出口；不能划分的子问题即有解子问题是按问题要求的处理，如输出等。递归主要研究是有解子问题。
至于可继续划分的子问题，则被写成同样形式的递归调用语句，且，有几个这样的子问题就有几条递归语句。体现了子问题与原问题的处理方式，只是问题规模变小。在数据结构中一般有三种情况的划分：
⑴可划分为一个子问题的：线性表、二叉排序树的查找； ⑵可划分为一个子问题的：广义表、二叉树； ⑶可划分为一个子问题的：图。
根据递归项中有解子问题的处理顺序，递归可以划分为前序递归、中序递归和后序递归。 3、题目分类
例1、有一个不带头结点的单链表，输出以h为头指针的单链表中最大结点值。 例2、假设二叉树采用二叉链表存储结构，编写一个算法，给出二叉树中一个非根节点（由p指针所指），求它的双亲结点。 例3、利用一个二叉树遍历的思想，设计一个算法判断二叉树是否为平衡二叉树。如果是，设计算法求出每个结点的平衡因子。
例4、编写算法根据先序和中序序列来确定一棵二叉树。
20