A． p!=UNLL B． p->lchild!=NULL C. p->ltag==0 D. p->ltag==1
二、填空题
1. 具有n个结点的完全二叉树的深度为 。 2. 二叉树第i层上最多有 个结点。 3. 深度为k的二叉树最多有 个结点。
4．具有n个结点的二叉树的最小深度为 ，最大深度为 ；具有具有n个结点的度为2的树的最小深度为 ，最大深度为 。 5．具有m个叶结点的huffman树共有 个结点。
6．完全二叉树T按顺序存放，编号依次为1,2,...,n,则编号为i的结点左孩子如果存在的话，其编号为 。
7．在一棵二叉树中，度为０的结点个数为n0，度为２的个数为n2，则n0= 。 8．三个结点a,b,C．组成二叉树，共有 种不同的结构。
9. 一颗树T中，包括1个度为1的结点，2个度为2的结点，3个度为3的结点，则T的叶子结点数为 。
10．已知某完全二叉树采用顺序存储结构，结点的存放顺序为（A,B,C,D,E,F,G,H,I,J），该完全二叉树的后根遍历序列为 。 11．前序遍历序列是abc且后序遍历序列为cba的二叉树共有 棵。
12. F是由T1, T2, T3三棵树组成的森林，T1, T2, T3 的结点数分别为n1,n2,n3,则F对应的二叉树B(F)的根的左子树中结点数为 ，根的右子树中的结点数为 。
三、基础知识题
1．已知一棵树遍的集合为{
(7) 哪些是结点e的兄弟？哪些是结点f的兄弟？ (8) 结点b和n的层次号分别是什么？
30
(9) 树的深度是多少？
(10) 以结点c为根的子树的深度是多少？ (11) 树的度数是多少？
2．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，?，nk个度为k
的结点，问该树中有多少个叶子结点？
4．对题2所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。 5．现有按先序遍历二叉树的结点序列为abc，试写出能得到这一遍历结果的各种二
叉树。
6．一棵非空的二叉树其先序序列和后序序列正好相反，说明这棵二叉树的形状。 7．分别画出和下列树对应的二叉树。
A B
8．画出和下列二叉树相应的森林。
A B
9．以数据集{4，5，6，7，10，12，18}为结点权值构造的Huffman树，并求其带权
路径长度。
10．假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK，请画出
31
该树并给出其后序序列。
12. 已知某二叉树按后序遍历序列为CEDBHJIGFA，按中序遍历序列为CBEDAHGIJF,
试画出该二叉树形状（要求写出中间过程）， 并写出它的先序遍历序列。 13. 设a,b,c,d,e,f六个字母出现的次数分别为7,19,2,6,32,3,试为这六个字母设
计huffman编码并画出对应huffman树。
14. 对给出的数据序列4,5,6,7,10,12,15,18,23，构造一棵huffman树，并求其带
权路径长度。
15．设a,b,c,d,e,f,g,h,i九个字母出现的次数分别为4,5,6,7,10,12,15, 18,23，
构造一棵huffman树，并给出每个字符的huffman编码。
16. 设一棵二叉树的先序、中序遍历序列分别为EBADCFHGIKJ和ABCDEFGHIJK，要求：
(1) 画出该二叉树(要求写出中间步骤); (2)将这棵二叉树转换成对应的树(或森林)。
17.设一份电文中a,b,c,d,e,f,g,h八个字母出现的次数分别为7,19,2,6,32,3,21,
10, 要求： (1) 为每个字母设计huffman编码, (2) 给出八个字母二进制表示的等长编码并比较两方案的优缺点。
18．证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树。
19. 证明一棵二叉树无论进行先序、中序或后序遍历，其叶结点的相对次序不发生改
变。
四、算法设计题
1．试给出二叉树先序遍历的非递归形式的算法。 2．试写出按层次遍历二叉树的算法。
3．以二叉链表作存储结构，试编写求二叉树深度的算法。
4．设一棵二叉树以二叉链表存储，试设计算法求此二叉树上叶子结点个数。 5．设一棵二叉树以二叉链表存储，试设计算法求此二叉树上度为2的结点个数。 6．试编写算法，对一棵以孩子-兄弟链表表示的树统计叶子结点个数。 7．设计一个算法，统计二叉树中 等于给定值x的结点个数。 8．设计一个算法，从一棵二叉树中查找出所有结点的最大值。 9．编写递归算法，将二叉树中所有结点的左、右子树相互交换。
10．编写求任意二叉树中一条最长的路径的算法，要求输出此路径上各结点的值及路径的长度。
11．设一棵树以孩子-兄弟表示法存储，试编写计算树的深度的算法。
32
第七章 图
一、选择题
1．具有4个顶点的无向完全图有（ ）条边。 A． 6 B．12 C. 16 D． 20
2．对于具有n个顶点的连通无向图，其边的个数至少为（ ）。 A． n-1 B．n C． n+1 D． nlogn
3．G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。 A． 6 B．7 C． 8 D． 9
4．对于具有n个顶点的强连通图，其弧条数的最小值为（ ）。 A． n+1 B．n C． n-1 D． n-2
5. 在一个图中，所有顶点的度数之和等于所有边数的（ ）倍；在一个有向图中，
所有顶点的入度之和等于所有顶点出度之和的（ ）倍。 A． 1/2 B． 2 C． 1 D． 4
6．图的深度、广度优先遍历算法分别类似于二叉树的（ ）。
A． 先序遍历和中序遍历 C． 后序遍历和中序遍历
B． 先序遍历和层序遍历
D． 层序遍历和先序遍历
7. 有n个顶点e条边的无向图G,它的邻接表中的表结点总数是( ) A． 2n B．n C． 2e D． e
8. 连通图G中有n个顶点,G的生成树是( )连通子图.
A． 包含G的所有顶点 B． 不必包含G的所有顶点 C． 包含G的所有边 D． 包含G的所有顶点和所有边 9. 下面关于图的存储的叙述中正确的是（ ）
A．用相邻矩阵法存储图，占用的存储空间大小只与图中结点个数有关，而与边
数无关
B．用相邻矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个
数无关
C．用邻接表法存储图，占用的存储空间大小只与图中结点个数有关，而与边数
无关
D．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数
无关
10．对一个具有n个顶点和e条边的无向图，若采用邻接表存储，则表结点数是( ⒀ )。 A． n+e B． 2e C． e D． n
11．设图G用邻接表存储，则拓扑排序的时间复杂度为（ ）。
33