济南铁道职业技术学院 专升本辅导教材 数据结构
(16)在某二叉树中，若结点A有左孩子Y和右孩子X，则在结点的前序序列、中序序列和后序序列中，结点——一定在结点——的前面。
(17)利用中序线索二叉树进行中序遍历可以不用设置——结构。
(18)对二叉排序树进行——，可以得到由该二叉树中结点组成的按值有序排列的序列。
(19)采用逐点插入法建立序列(54，28，16，34，73，62，95，60，26，43)的二叉排序树后，查找数据元素62共进行——次元素间的比较。
(20)具有N0个叶结点的哈夫曼树共有——个结点。
5.4 若结点A有三个兄弟(包括A本身)，并且B是A的双亲结点。问结点B的度是多少?
5.5 若一棵树有n1个度为1的结点，n2个度为2的结点??nm个度为m的结点，试问：该树一共有多少个叶结点(即度为0的结点个数no)?请写出推导过程。
5. 6 一棵深度为h的满m叉树具有如下性质：第h层上的结点都是叶结点，其余各层上每个结点 都有m棵非空子树。问：
(1)第k层有多少个结点?(1≤k≤h) (2)整棵树有多少个结点?
(3)若按层次从上到下，每层从左到右的顺序从1开始对全部结点编号，编号为i的结点的双亲结点的编号是什么?编号为i的结点的第j个孩子结点(若存在的话)的编号是什么?
5.7 一棵度为2的树与一棵二叉树有什么区别?
5.8 请分别画出具有3个结点的树和具有3个结点的 二叉树的所有形态。
5.9 请分别列出如图所示的二叉树的所有叶结点与分支结点，并分别指出各结点的度数以及所 在的层次数。
5.10 若一棵具有n个结点的二叉树采用二叉链表存储结构。试问：该二叉链表中共有多少个空指针域?写出推导过程。
5.11 已知某算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，请写出其前缀形式(利用二叉树的遍历序列)。
5.12 已知某二叉树的前序序列为ABDEGCFHIJ，中序序列为DBGEAHFIJC，请写出后序序列。 5.13 已知某-'X树的中序遍历序列为CBGEAFHD，后序遍历序列为CGEBHFDA，请画出该二叉树的前序线索二叉树的二叉链表结构的表示。
5.14 已知按前序遍历二叉树的结果为ABC。试问，有几种不同的二叉树可以得到这一遍历结果? 5.15 请按照算法,SORTTREE画出对应于序列{15，20，15，7，9，18，61的二叉排序树。
5.16 给定一组权值W={14，15，7，3，20，4}，请构造出相应的哈夫曼树，并计算其带权的路径长度WPL。
5.17 试证明具有n2个叶结点的哈夫曼树的分支总数为2(N0-1)。
5.18 二叉树的深度采用自然语言形式可以描述为：若二叉树为空，则其深度为0，否则其深度等于左子树与右子树的最大深度加1。若二叉树采用二叉链表存储结构，请写出求该二叉树的深度的递归算法。
5.19 已知二叉树采用二叉链表存储结构，根结点的地址为T。请写出二叉树前序遍历的非递归算法。
第 36 页 共 63 页
济南铁道职业技术学院 专升本辅导教材 数据结构
5.20 已知两棵二叉树都采用二叉链表存储结构，根结点的地址分别为T1和T2。请写一算法，判断两棵二叉树是否相似(即具有相同的形态)，并给出相应信息。
5.21 已知两棵二叉树都采用二叉链表存储结构，根结点的地址分别为T1和T2。请写一算法，判断两棵二叉树是否是相同的二叉树，并给出相应信息。
5.22 已知二叉树采用二叉链表存储结构，根结点的地址为T。请写一算法，释放该二叉树中所有结点占用的空间。
5.23 已知二叉树采用二叉链表存储结构，根结点的地址为T。请写一非递归算法统计出该二叉树共有多少个度为1的结点?要求：算法中用到的堆栈采用链式存储结构。
5.24 已知非空二叉树采用二叉链表存储结构，根结点地址为T。请写出非递归算法，该算法打印数据信息为item的结点的所有祖先结点。假设数据信息为item的结点不多于一个。
5.25 已知二叉树采用二叉链表存储结构，根结点的地址为T。请写一算法，将该二叉链表结构转换为顺序存储结构。
5.26 已知某具有n个结点的二叉树的前序序列与中序序列分别存放于数组PREOD[n)与INOD [n]中，并且各结点的数据值均不相同。试写一非递归算法生成该二叉树的二叉链表结构。
5.27 已知二叉树采用二叉链表存储结构，根结点地址为了。试写一算法，判断该二叉树是否为完全二叉树，并给出相应信息。
5.28 已知二叉树采用二叉链表存储结构，根结点地址为丁。试写一算法，删去并释放数据值为key的叶结点。
5.29 已知二叉排序树采用二叉链表存储结构，根结点的地址为T。试写一算法，删去数据值小于或等于key的结点。
5.30 已知二叉树采用二叉链表存储结构，根结点的地址为T。试写一算法，算法功能是按层次从上到下，每层从右到左的顺序依次列出二叉树所有结点的数据信息。
5.31 已知二叉树采用二叉链表存储结构，根结点的地址为T。试写一算法，打印该二叉树所有左子树的根结点的数据信息。
5.32 已知二叉树采用二叉链表存储结构，根结点的地址为T。试写一算法，交换二叉树所有左、右子树的位置，即将结点的左子树变成结点的右子树，右子树变成左子树。
5.33 已知二叉树采用二叉链表存储结构，根结点的地址为丁。请写一算法，输出从根结点到某个指定结点的路径上各结点的值。
5.34 已知二叉树采用二叉链表存储结构，根结点的地址为T，请写一算法，判断该二叉树是否是二叉排序树。
5.35 将图7．43所示的树林转换为一棵二叉树。
5.36 分别写出如图7．44所示的树的前序遍历序列与后序遍历序列。
5.37 已知某树林转化为二叉树后所对应的顺序存储结构为请画出该树林。
第 37 页 共 63 页
济南铁道职业技术学院 专升本辅导教材 数据结构
历年考题
1．在具有n个叶子结点的严格二叉树中，结点总数为（ ）
A．2n+1 B．2n C．2n-1
D．2n-2
2．除根结点外，树上每个结点（ ）
A．可有任意多个孩子、任意多个双亲 B．可有任意多个孩子、一个双亲 C．可有一个孩子、任意多个双亲 D．只有一个孩子、一个双亲
3．具有100个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其余（ ）个指针域为空。 A．50
B．99 C．100
D．101
4．若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过（ ）
A．n/2 B．n C．(n+1)/2 D．n+1
6．一棵有16结点的完全二叉树，对它按层编号，则对编号为7的结点X，它的双亲结点及右孩子结点的编号分别为（ ）
A．2，14 B．2，15 C．3，14 D．3，15 7.下列陈述中正确的是( )
A.二叉树是度为2的有序树
B.二叉树中结点只有一个孩子时无左右之分 C.二叉树中必有度为2的结点
D.二叉树中最多只有两棵子树，并且有左右之分
9、前序遍历序列与中序遍历序列相同的二叉树为 (1) ，前序遍历序列与后序遍历序列相同的二叉树为 (2) 。
(1) A、根结点无左子树的二叉树
B、根结点无右子树的二叉树
C、只有根结点的二叉树或非叶子结点只有左子树的二叉树 D、只有根结点的二叉树或非叶子结点只有右子树的二叉树 (2) A、非叶子结点只有左子树的二叉树
B、只有根结点的二叉树
C、根结点无右子树的二叉树
D、非叶子结点只有右子树的二叉树
10、 假设一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，则其前序遍历序列为 (10) 。
(10) A、ABCDEFGHIJ B、ABDEGHJCFI C、ABDEGHJFIC D、ABDEGJHCFI
11、 设某种二叉树有如下特点；结点的子树数目不是2个，则是0个。这样的一棵二叉树中有m(m>O)个子树为0的结点时，该二叉树上的结点总数为 (34) 。
(34) A．2m+l B．2m-1 C．2(m—1) D．2(m+1)
14、二叉树＿A＿。在完全的二叉树中，若一个结点没有＿B＿，则它必定是叶结点。每棵树都能唯一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子女是N在原树里对应结点的＿C＿，而N的右子女是它在原树里对应结点的＿D＿。二叉排序树的平均检索长度为＿E＿。
供选择的答案：
A：①是特殊的树 ②不是树的特殊形式
第 38 页 共 63 页
济南铁道职业技术学院 专升本辅导教材 数据结构
③是两棵树的总称 ④是只有二个根结点的树形结构
B：①左子结点 ②右子结点
③左子结点或者没有右子结点 ④兄弟
C～D： ①最左子结点 ②最右子结点 ③最邻近的右兄弟 ④最邻近的左兄弟 ⑤最左的兄弟 ⑥最右的兄弟
E：①O(n) ②o(n) ③O(log2n) ④o(log2n)
15、每一棵树都能唯一地转换为它所对应的二叉树，树的这种二叉树表示对树的运算带来很大的好处。遍历（周游）是树形结构的一种重要运算，二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按___A___次序），后序法（即按___B___次序）和中序法（也称对称序法，即按___C___次序）。这三种方法相互这间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是___D___,而且可得该二叉树所表示的树的先根次序序列是___B___。
供选择的答案
A～C：① R L N ② R N L ③ L R N
④ L N R ⑤ N L R ⑥ N R L
D、E：① E F G H B C D ② F E G H D C B
③ B C D E F G H ④ E F B G C H D ⑤ B E F C G D H ⑥ F E G B H D C 17．若一棵满三叉树中含有121个结点，则该树的深度为________________。
18．设有k个结点，在用哈夫曼算法构造哈夫曼树的过程中，若第i次合并时已找到权最小的结点x和权次小的结点y，用T［x］.wt表示结点x的权值，已知T［x］.wt=m, T［y］.wt=n，则合并成新的二叉树后给新根结点的权值赋值的语句为_____________。 19．在下列树中，结点H的祖先为_____________。
20．设一棵二叉树中度为2的结点数为10，则该树的叶子数为________________。 21．如图所示的二叉树，若按后根遍历，则其输出序列为________________。
22.在n个结点的线索二叉链表中，有________个线索指针。
23、一棵具有n个结点的理想平衡二叉树（即除离根最远的最底层外其他各层都是满的，最底层有若干结点）有多少层？若设根结点在第0层，则树的高度h如何用n来表示（注意n可能为0）？ 24．画出下列二叉树的二叉链表表示图。（6分）
第 39 页 共 63 页
济南铁道职业技术学院 专升本辅导教材 数据结构
25.已知树T的先序遍历序列为ABCDEFGHJKL，后序遍历序列为CBEFDJIKLHGA。请画出树T。
27．已知树如右图所示， （1）写出该树的后序序列； （2）画出由该树转换得到的二叉树。
28．分别写出下列二叉树的先根、中根、后根遍历序列。（6分）
第六章 图
迪杰斯特拉算法如下：
SHORTEST—PATH(intcost[][n]，intv，intn，intdist[]，intpath[)) {
ihti，N，u，count，pos[n]； for(i=0;i s[i]=0； ／x标记数组置0 x／ dist[i]=cost[V][i]； ／。将邻接矩阵第v行元素依次送dist数组x path[i][0]=v； ／x源点v到各顶点的路径置初值。／ pos[i]=0； ／。第i条路径的位置计数器置初值x／ } ／x对辅助数组进行初始化。／ s[v]=l； count=1; ／x计数器赋初值1 x／