数据结构习题库练习题带答案1-9章全.doc

第一章 绪论
一．填空题
1.数据结构是一门研究非数值计算的程序设计问题中计算机的_____________ 以及它们之间的_________ 和操作等的学科。
2.数据结构包括数据的_____________ 结构、_____________ 结构和运算。
3.数据的物理结构被分为_________、________、__________和___________四种。
4.数据的逻辑结构是指数据元素之间的逻辑关系，根据数据元素之间关系的不同特性，逻辑结构通常有_______________ ，________________ ，________________ 和 __________________四类基本结构。
5.一种抽象数据类型包括 ____________和_____________ 两个部分。
6.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N（M：N）的联系时，称这种结构为____________当结点之间存在1 对N（1：N）的联系时，称这种结构为____________。
7.数据结构被形式地定义为（D, R），其中D是___________ 的有限集合，R是D上的有限集合。
8. 数据的基本单位是________，它在计算机中是作为一个整体来处理的。
9.算法的特性有________，___________ ，____________ ，_______________ 和__________ 等五种特性。
10.通常从四个方面评价算法的质量：_________、_________、_________和_________。
11.算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。
12.算法的效率可分为______________ 效率和__________________ 效率。
13.算法的时间复杂度为(3n3+2000nlog2n+90)/n2，其数量级表示为________。
14.下面程序段的时间复杂度为____________。
for(int i=0; i<m; i++)
for(int j=0; j<n; j++)
a[i][j]=i*j;
15．for(i=1，t=1，s=0；i<=n；i++) {t=t*i；s=s+t；}的时间复杂度为_________。
16．对算法从时间和空间两方面进行度量，分别称为_____和_______ 分析。
二．选择题
1.计算机识别、存储和加工处理的对象被统称为_________。
A、数据 　　　B、数据元素　　　C、数据结构 　　D、数据类型
2.数据结构通常是研究数据的__________及它们之间的联系。
A、存储和逻辑结构 B、存储和抽象 C、理想和抽象 D、理想与逻辑
3.在数据结构中，从逻辑上可以把数据结构分成__________。
A、动态结构和静态结构 B、紧凑结构和非紧凑结构
C、线性结构和非线性结构 D、内部结构和非内部结构
4．不是数据的逻辑结构是__________。
A、散列结构 B、线性结构 C、树结构 D、图结构
5．不是数据的存储结构是__________。
A、散列结构 B、顺序结构 C、链接结构 D、线性结构
6.同一记录结构中的各数据项的类型__________一致。
A、必须 B、不必 C、不能 D、不可能
8.组成数据的基本单位是__________。
A、数据项 B、数据类型 C、数据元素 D、数据变量
9．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r} ，r={<1 ，2> ，<2 ，3>，<3 ，4> ，<4 ，1>}，则数据结构 A是__________。
A、线性结构 B、树型结构 C、图型结构 D、集合
10．设某数据结构的二元组形式表示为 A=(D ，R)，D={01 ，02，03，04，05，06，07，08，
09}，R={r} ，r={<01 ，02>，<01，03>，<01 ，04>，<02 ，05>，<02 ，06>，<03 ，07>，
<03 ，08>，<03，09>}，则数据结构 A是__________。
A、线性结构 B、树型结构 C、物理结构 D、图型结构
11.对一个算法的评价，不包括如下__________方面的内容。
A、健壮性和可读性 B、并行性 C、正确性 D、时空复杂度
12.算法的五个重要特性是________？
A、可执行性、可移植性、可扩充性、输入和输出。
B、可行性、确定性、有穷性、输入和输出。
C、确定性、有穷性、稳定性、输入和输出。
D、可执行性、可移植性、可扩充性、输入和输出。
13．算法分析的两个方面是________。
A、空间复杂性和时间复杂性 B、正确性和简明性
C、可读性和文档性 D、数据复杂性和程序复杂性
14. 算法分析的目的是__________？
A、找出数据结构的合理性 B、研究算法中的输入和输出的关系
C、分析算法的效率以求改进 D、分析算法的易懂性和文档性
15. 以下算法的空间复杂度是__________。
#include
#define n 10
cout(int A[])
{
int B[n],i;
for(i=0;i<N;I++)< p>
B[n-i-1]=A[i];
for(i=0;i<N;I++)< p>
printf("%d",B[i]);
}
A、O(1) B、O(n) C、O(log2n) D、O(n*n)
16．下面程序的时间复杂为__________。
for（i=1，s=0； i<=n ； i++ ）
{
t=1 ；
for(j=1；j<=i；j++)
t=t*j ；
s=s+t；
}
A、O(n) B、O(n2) C、O(n3) D、O(n4)
17.一个算法的时间复杂度为(9n2+2nlog n+2)/(5n)，其数量级表示为________。
A、O(1) B、O(n2) C、O(log2n) D、O(n)
18.阅读以下的程序段,它的时间复杂度为__________。
for(i=1;i<=m;++i)
for(j =1;j<=n;++j)
c[i][j]=0;
A、O(n) B、O(m+2n) C、O(m+n) D、O(m*n)
19．程序段 s=i=0；do {i=i+1 ； s=s+i ；}while(i<=n)；的时间复杂度为（ ）。
A、O(n) B、O(nlog2n) C、O(n2 ) D、O(n/2)
20．下列程序段的时间复杂度为__________。
for(i=0 ； i<m； i++) for(j=0 ； j<t ； j++) c[i][j]=0 ；
for(i=0 ； i<m； i++) for(j=0 ； j<t ； j++) for(k=0 ； k<n ； k++) c[i][j]=c[i][j]+a[i][k]*b[k][j] ；
A、 O(m*n*t) B、O(m+n+t) C、O(m+n*t) D、O(m*t+n)
21. 在数据结构中，与所使用的计算机无关的是数据的__________结构。
A、逻辑 B、存储 C、逻辑和存储 D、物理
22. 数据结构在计算机中的表示是指__________？
A、数据的逻辑结构 B、数据结构 C、数据的存储结构 D、数据元素之间的关系
23. 下面__________的时间复杂性最好，即执行时间最短。
A、O(n) B、O(log2n) C、O(nlog2n) D、O(n2)
三、判断题
1. 程序越短，程序运行的时间就越少。
2. 数据结构包括数据间的逻辑结构、数据的存储方式和数据的运算三个方面。
四、简答题
1．数据的逻辑结构有哪几种？常用的存储有哪几种？
2．举一个数据结构的例子，叙述其逻辑结构、存储结构和运算三方面的内容。
3．什么叫算法？它有哪些特性？
4．有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑结构图，并指出它们分别以属于何种结构。
（1）A=(K,R),其中
K={a,b,c,d,e,f,g,h}
R={r}
r={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>}
(2) B=(K,R),其中
K＝{a,b,c,d,e,f,g,h}
R={r}
r={<d,b>,<d,g>,<d,a>,<b,c>,<g,e>,<g,h>,<e,f>}
(3) B=(K,R),其中
K={1,2,3,4,5,6}
R={r}
r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}
5．简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。
解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
数据对象是性质相同的数据元素的集合，是数据的一个子集。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
存储结构是数据结构在计算机中的表示。
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。
6. 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。
解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。
7. 设有数据结构(D,R)，其中
，，
试按图论中图的画法惯例画出其逻辑结构图。
解：

8.设n为正整数。试确定下列各程序段中前置以记号@的语句的频度：
(1) i=1; k=0;
while(i<=n-1){
@ k += 10*i;
i++;
}
(2) i=1; k=0;
do {
@ k += 10*i;
i++;
} while(i<=n-1);
(3) i=1; k=0;
while (i<=n-1) {
i++;
@ k += 10*i;
}
(4) k=0;
for(i=1; i<=n; i++) {
for(j=i; j<=n; j++)
@ k++;
}
(5) for(i=1; i<=n; i++) {
for(j=1; j<=i; j++) {
for(k=1; k<=j; k++)
@ x += delta;
}
(6) i=1; j=0;
while(i+j<=n) {
@ if(i>j) j++;
else i++;
}
(7) x=n; y=0; // n是不小于1的常数
while(x>=(y+1)*(y+1)) {
@ y++;
}
(8) x=91; y=100;
while(y>0) {
@ if(x>100) { x -= 10; y--; }
else x++;
}
解：(1) n-1
(2) n-1
(3) n-1
(4) n+(n-1)+(n-2)+...+1=
(5) 1+(1+2)+(1+2+3)+...+(1+2+3+...+n)=
=
=
(6) n
(7) 向下取整
(8) 1100
五、程序算法题
1.设n为整数，求下列各程序段的时间复杂度
（1）i=1;k=2;
While(i<n){
k=k+10*I;
i=i+1;
}
(2)i=1;j=0;
While(i+j<=n)
If(i>j)j=j+1;
Else i=i+1;
(3)x=91;y=100
While(y>0)
If(x>100){
x=x-10;
y=y-1;
}else x=x+1;
2. 试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值
解：
int max3(int x,int y,int z)
{
if(x>y)
if(x>z) return x;
else return z;
else
if(y>z) return y;
else return z;
}

第九章 排序
一、选择题
1.下述排序算法中，稳定的是________。
A．直接选择排序 B．直接插入排序 C．快速排序 D．堆排序
2.下列排序算法中，________需要的辅助存储空间最大。
A．快速排序 B．插入排序 C．希尔排序 D．归并排序
3.下列排序算法中，________是稳定的。
A．插入、希尔 B．冒泡、快速 C．选择、堆排序 D．基数、归并
4.下列各种排序算法中平均时间复杂度为O(n2)的是________。
A．快速排序 B．堆排序 C．归并排序 D．冒泡排序
5. 在待排序的元素基本有序的前提下，效率最高的排序方法是________。
A．简单插入排序 B．简单选择排序 C．快速排序 D．归并排序
6. 利用直接插入排序法的思想建立一个有序线性表的时间复杂度为_______。
A．O(n) B．O(nlog2n) C．O(n2) D．O(log2n)
7. 对n个记录进行堆排序，所需要的辅助存储空间为________。
A．O(1og2n) B．O(n) C．O(1) D．O(n2)
8. 快速排序在最坏情况下的时间复杂度为________。
A．O(log2n) B．O(nlog2n) C．O(n) D．O(n2)
9. 设有序列12、42、37、19，当使用直接插入排序从小到大排序时，其比较次数为________。
A．3 B．4 C．5 D．6
10. 对数据元素序列( 49, 72, 68, 13, 38, 50, 97, 27 )排序，前三趟排序结束时的结果依次为：
第一趟：13, 72, 68, 49, 38, 50, 97, 27；
第二趟：13, 27, 68, 49, 38, 50, 97, 72；
第三趟：13, 27, 38, 49, 68, 50, 97, 72；
该排序采用的方法是_________。
A. 直接插入排序 B. 直接选择排序 C. 冒泡排序 D. 堆排序
11. 如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。________就是不稳定的排序方法。
A．起泡排序 B．归并排序 C．直接插入排序 D．简单选择排序
12. 设一组初始记录关键字的长度为8，则最多经过________趟插入排序可以得到有序序列。
A．6 B．7 C．8 D．9
13. 设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是________。
A． F，H，C，D，P，A，M，Q，R，S，Y，X
B． P，A，C，S，Q，D，F，X，R，H，M，Y
C． A，D，C，R，F，Q，M，S，Y，P，H，X
D． H，C，Q，P，A，M，S，R，D，F，X，Y
14. 每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做________ 排序。
A．插入 B．堆 C．快速 D．归并
15.每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做________排序。
A．插入 B．堆 C．快速 D．归并
16.下列________种排序算法的平均时间复杂度为O(nlog2n)。
A．简单选择排序 B．简单插入排序 C．冒泡排序 D．归并排序
17. 下列________种排序算法更适合于外部排序。
A．选择排序 B．插入排序 C．冒泡排序 D．归并排序
18. 设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为________ 。
A．2，3，5，8，6 B．3，2，5，8，6
C．3，2，5，6，8 D．2，3，6，5，8
19. 二路归并排序的时间复杂度为________。
A． O(n) B．O(n2) C．O(nlog2n) D．O(log2n)
20. 时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是________。
A． 堆排序 B．冒泡排序 C．希尔排序 D．快速排序
21.一趟排序结束后不一定能够选出一个元素放在其最终位置上的是________。
A．堆排序 B．冒泡排序 C．快速排序 D．希尔排序
22.设有5000 个待排序的记录关键字，如果需要用最快的方法选出其中最小的10 个记录关键字，则用下列________方法可以达到此目的。
A．快速排序 B．堆排序 C．归并排序 D．插入排序
23. 设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20 为基准记录的一趟快速排序结束后的结果为________。
A．10，15，14，18，20，36，40，21
B．10，15，14，18，20，40，36，21
C．10，15，14，20，18，40，36，2l
D．15，10，14，18，20，36，40，21
24. 设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行________趟的分配和回收才能使得初始关键字序列变成有序序列。
A． 3 B． 4 C．5 D．8
25．设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4 条记录关键字为________。
A．40，50，20，95 B．15，40，60，20
C．15，20，40，45 D．45，40，15，20
26. 设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为________。
A． 15，25，35，50，20，40，80，85，36，70
B． 15，25，35，50，80，20，85，40，70，36
C． 15，25，35，50，80，85，20，36，40，70
D． 15，25，35，50，80，20，36，40，70，85
27.对于关键字值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从关键字值为__________的结点开始。
A． 100 B． 12 C． 60 D．15
28.一组记录的排序码为（46，79，56，38，40，84），则堆排序时建立的初始大顶堆为________。
A．79，46，56，38，40，80 B．38，46, 56，79， 40，84
C．84，79，56，38，40，46 D．84，56，79，40，46，38

二、填空题
1. 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以d=4 为增量的一趟希尔排序结束后的结果为_______。
2. 对一组初始关键字序列（40，50，95，20，15，70，60，45，10）进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为______，在整个排序过程中最多需要进行______趟排序才可以完成。
3. 设有n个无序的记录关键字，则直接插入排序的时间复杂度为________，快速排序的平均时间复杂度为________。
4. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_______，整个堆排序过程的时间复杂度为________。
5. 对n个元素的序列进行起泡排序时，最少的比较次数是_______。
6. 在插入和选择排序中，若初始数据基本正序，则选用_______；若初始数据基本反序，则选用_______。
7. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较_______。
8. 设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟直接插入排序结束后的结果是________。
9. 设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟简单选择排序结束后的结果是_______。
10. 设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟冒泡排序结束后的结果为_______。
11. 设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的一趟快速排序结果为_________。
12. 当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用____ 排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用_______排序。
13. 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有_______。
14. 在快速排序、堆排序、归并排序中，_______排序是稳定的。

三、判断题
1. 直接选择排序是一种稳定的排序方法。 （ ）
2. 冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（ ）
3. 希尔排序算法的时间复杂度为O(n2)。 （ ）
4. 设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（ ）
5. 一组关键码已完全有序时，最快的排序方法是快速排序。 （ ）
6. 快速排序是排序算法中平均性能最好的一种排序。 （ ）
7. 堆是完全二叉树，完全二叉树不一定是堆。 （ ）
8. 层次遍历初始堆可以得到一个有序的序列。 （ ）
9. 从平均性能而言，快速排序最佳，其所需时间最省。 （ ）

四、算法设计题
1.设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前。
2.写一组英文单词按字典序排列的基数排序算法。设单词均由大写字母构成，最长的单词有d个字母。提示：所有长度不足d个字母的单词都在尾处补足空格，排序时设置27个箱子，分别与空格，A，B...Z对应。
3.对给定的j（1<=j<=n），要求在无序的记录区R［1…n］中找到按关键字自小到大排在第j个位置上的记录（即在无序集合中找到第j个最小元），试利用快速排序的划分思想编写算法实现上述的查找操作。
4.改写快速排序算法，要求采用前、中、后三者取中的方式选择划分的基准记录；若当前被排序的区间长度小于等于3时，无须划分而是直接采用直接插入方式对其排序。
第六章 树
一、选择题
1．对于一棵具有n个结点的树，该树中所有结点的度数之和为________。
A． n-1 B. n C. n+1 D. (n+1)/2
2．设结点A 有3个兄弟结点且结点B为结点A的双亲结点，则结点B 的度数为________。
A． 3 B. 4 C.5 D. 1
3．根据二叉树的定义可知二叉树共有________种不同的形态。
A． 4 B. 5 C. 6 D. 7
4．在一棵树中，________没有前驱结点。
A. 分支结点 B. 叶结点 C. 树根结点 D. 空结点
5．设某棵二叉树中只有度数为0和度数为2的结点,且度数为0的结点数为 n，则这棵二叉中共有________个结点。
A． 2n B.n+1 C. 2n-1 D.2n+1
6．设某棵二叉树的高度为10，则该二叉树上叶子结点最多有________。
A． 20 B.256 C. 512 D.1024
7. 一棵具有5层满二叉树中结点总数为________。
A． 31 B. 32 C.33 D.16
8. 如下图所示的4 棵二叉树，_______不是完全二叉树。

9.具有65个结点的完全二叉树的高度为________。 (根的层次号为1)
A.8 B.7 C.6 D.5
10.把一棵深度4的左单支二叉树改造成完全二叉树时，要增添 个空结点。
A．10 B．8 C．6 D．4
11.设按照从上到下、从左到右的顺序从 1 开始对完全二叉树进行顺序编号，则编号为 i结点的左孩子结点的编号为________。
A． 2i+1 B. 2i C. i/2 D. 2i-1
12.首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为________。
A.前序遍历 B.后序遍历 C.中序遍历 D.层次遍历
13.已知一棵二叉树的前序遍历结果为 ABCDEF ，中序遍历结果为 CBAEDF，则后序遍历的结果为________。
A．CBEFDA B. FEDCBA C. CBEDFA D. 不定
14.已知某二叉树的后序遍历序列是 dabec, 中序遍历序列是 debac,它的前序遍历序列是________。
A．acbed B．decab C．deabc D．cedba
15.某二叉树T有n个结点，设按某种遍历顺序对T中的每个结点进行编号，编号值为1,2,…,n且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树 的结点中，其最小编号等于V左子树上结点的最大编号加1。这时按 编号。
A.中序遍历序列 B.前序遍历序列 C.后序遍历序列 D.层次遍历序列
16.某非空二叉树的前序序列和后序序列正好相反，则二叉树一定是________的二叉树。
A.空或只有一个结点 B.高度等于其结点数
C.任一结点无左孩子 D.任一结点无右孩子
17.由前序序列和中序序列________唯一确定一棵二叉树。
A． 能 B. 不能 C. 不一定
18.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。下面结论正确的是________。
A．树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B．树的后根遍历序列与其对应的二叉树的后序遍历序列相同
C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同
D．以上都不对
19.对于一棵具有n个结点的二叉树，对应二叉链表中指针总数为 2n 个，其中________ 个用于指向孩子结点。
A． n-1 B. n C. n+1 D.n-2
20.设F是由T1、T2和T3 三棵树组成的森林，与F对应的二叉树为B，T1、T2 和T3 的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为________。
A． N1-1 B. N2-1 C. N2+N3 D. N1+N3
21. 由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为 __ ___。
A. 23 B. 37 C. 44 D.46
22.n 个权构成一棵Huffman树，其结点总数为__________。
A．2n-1 B.2n C.2n+1 D. 不确定

二、填空题
1. 在一棵二叉树中，度为0的结点的个数为n0 ，度为2的结点的个数为n2 ，则：n0 = 。
2．结点数为7的二叉树的高度最矮是_______ ，最高是_______ 。
3．给定二叉树的结点数，要使树高为最大，那么该树应该是_______形状。
4．给定二叉树的结点数，要使树高为最矮，那么该树应该是_______形状。
5．如果一棵满二叉树的深度为7，那么它共有_______个结点，有 _______个叶结点。
6．深度为5的二叉树，至多有_______个结点。
7．深度为k 的完全二叉树至少有_______个结点，至多有_______个结点。
8．在树形结构中，树根结点没有前驱结点，其余每个结点有且只有_______ 个前驱结点，叶子结点没有后继结点，其余每个结点的后继结点可以有_______个。
9.设二叉树中度数为0 的结点数为50，度数为1 的结点数为30，则该二叉树中总共有_______个结点。
10.设二叉树中结点的两个指针域分别为lchild 和rchild，则判断指针变量p 所指向的结点为叶子结点的条件是___________________________。
11. 在n 个带权叶子结点构造出的所有二叉树中，带权路径长度最小的二叉树称为________。
12.设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1 开始顺序编号，则编号为8 的双亲结点的编号是_____，编号为8 的左孩子结点的编号是_______。
13. 设哈夫曼树中共有n 个结点，则该哈夫曼树中有_____个度数为1 的结点。
14. 以数据集{4，5，6，7，10，12，18}为结点权值所构造的Huffman 树为____，其带权路径长度为_________ 。
15.设一棵Huffman 树有6 个叶结点，权值分别为3、4、7、14、15、20，则根
结点的权值是_______。
16.设用于通信的电文仅由8 个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为_________。

三、综合应用题
1. 已知一棵树的边的集合表示为{（L,N）,（G,K）,（G,L）,（G,M）,（B,E）,（B,F）,（D,G）,（D,H）,（D,I）,（D,J）,（A,B）,（A,C）,（A,D）}。画出这棵树并回答下面问题：
（1） 树的根节点是哪个，哪些是叶子结点，哪些是非终端结点。
（2） 树的深度是多少，各个结点的层数是多少。
（3） 对于G结点，它的双亲结点、祖先结点、孩子结点、子孙结点、兄弟和堂兄弟分别是哪些结点。
2.设二叉树如下图所示，分别写出它的先序遍历、中序遍历、后序遍历序列。
A
B
E
C
F
G
D
H
I
J

3.设一棵二叉树的先序遍历序列为abcde，中序遍历序列为badce，请画出对应的二叉树，并写出对应后序遍历序列。
4.某二叉树结点的中序序列为HBCDEFG，后序序列为BDCHFGE，请据此画出该二叉树，再给该树加上中序线索。
5.请按照孩子-兄弟表示法，将下图所示树转化为二叉树。
A
C
B
D
E
F
G

6.若7个带权结点，其权值分别为3，7，8，2，6，10，14，试以它们为叶结点构造一棵哈夫曼树（请按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造），计算出带权路径长度WPL及该树的结点总数。
7.在一段文字中，共出现a、b、c、d、e、f六种字符，每种字符出现的频率分别为7,9,12,22,23,27。请回答下列问题：
（1）什么是哈夫曼树？
（2）根据题目所给频率值，画出相应的哈夫曼树。
（3）给出各个字符对应的哈夫曼编码。
（4）该段文字经过哈夫曼编码