数据结构期末复习章节试题(附答案)

第一章概论自测题答案

一、填空题

1.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系

和运算等的学科。

2.数据结构被形式地定义为（D,R）,其中D是数据元素的有限集合,R是D上的关系有限

集合。

3.数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。

4.数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。

5.线性结构中元素之间存在一对一关系,树形结构中元素之间存在一对多关系,图形结构中元素之间存

在多对多关系。

6.在线性结构中，第一个结点没有前驱结点,其余每个结点有且只有1个前驱结点；最后一个结点

没有后续结点,其余每个结点有且只有1个后续结点。

7.在树形结构中，树根结点没有前驱结点,其余每个结点有且只有1个前驱结点:叶子结点没

有后续结点,其余每个结点的后续结点数可以任意多个。

8.在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。

9.数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。

10.数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。

11.一个算法的效率可分为时间效率和空间效率。

二、单项选择题

（B）1.非线性结构是数据元素之间存在一种:

A）一对多关系B）多对多关系C）多对一关系D）一对一关系

（C）2.数据结构中，与所使用的计算机无关的是数据的结构；

A）存储B）物理C）逻辑D）物理和存储

（C）3.算法分析的目的是：

A）找出数据结构的合理性B）研究算法中的输入和输出的关系

C）分析算法的效率以求改进D）分析算法的易懂性和文档性

（A）4.算法分析的两个主要方面是：

A）空间复杂性和时间复杂性B）正确性和简明性

C）可读性和文档性D）数据复杂性和程序复杂性

（C）5.计算机算法指的是：

A）计算方法B）排序方法C）解决问题的有限运算序列D）调度方法

（B）6.计算机算法必须具备输入、输出和等5个特性。

A)可行性、可移植性和可扩充性B)可行性、确定性和有穷性

C)确定性、有穷性和稳定性D)易读性、稳定性和安全性

三、简答题

1.简述线性结构与非线性结构的不同点。

答：线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多对多的。

2.数据结构的常见的四种存储方式。

答：顺序、链式、索引和散列。

3.数据结构的逻辑结构主要有哪两大类，具体是什么？

答：主要分为线性结构和非线性结构，其中线性结构反映结点间的逻辑关系是一对一的，非线性结构反

映结点间的逻辑关系是多对多的。非线性结构又包含树结构和图结构

四、分析下面各程序段的时间复杂度

1.for(i=0;i<n;i++)

2.s=0;

for(j=0;j<m;j++)

fori=0;i<n;i++)

A[i]|jJ=O；

for(j=0;j<n;j++)

答：0(m*n)

+=B[i]U];

sum=s;

答：0(i?)s

3.x=0;

for(i=l;i<n;i++)

for(j=1;j<=n-i;j++)

x++;

4.i=l;

解：因为x++共执行了n-l+n-2+....+1=

while(i<=n)

n(n-l)/2,

所以执行时间为O(n?)i=i*3;

答：O(log?。)

f=lJ=?+l1=1L

五、设有数据逻辑结构S=(D,R),试按各小题所给条件画出这些逻辑结构的图示，并确定相对于关系R,

哪些结点是开始结点，哪些结点是终端结点？

1.

D={dl,d2,d3,d4}R={(dl,d2),(d2,d3),(d3,d4)}

答:dl-d2fd3fd4dl一无直接前驱，是首结点d4一无直接后继是尾结点

2oD={dl,d2,-,d9}

R={(dl,d2),(dl,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5),(d6,d7),(d8,d9)}

答：此图为树形结构dl一无直接前驱，是根结点d2,d5,d7,d9一无直接后继是叶子结点

3.D={dl,d2,d9}

R={(dl,d3),(dl,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9),(d5,d6),(d8,d9),(d9,d7),(d4,d7),

(d4,d6)}

答：此图为图形结构dl,d2一无直接前驱，是开始结点d6,d7一无直接后继是终端结点

(2)(3)

第3章栈和队列自测卷答案

一、填空题(每空1分，共15分)

1.【李春葆】向量、栈和队列都是线性结构,可以在向量的任何位置插入和删除元素;对

于栈只能在栈顶插入和删除元素;对于队列只能在队尾插入和队首删除元素。

2.栈是一种特殊的线性表，允许插入和删除运算的--端称为栈顶。不允许插入和删除运算的一端

称为栈底。

3.队列是被限定为只能在表的一端进行插入运算，在表的另•端进行删除运算的线性表。

4.在一个循环队列中，队首指针指向队首元素的前一个位置。

5.在具有n个单元的循环队列中，队满时共有n-1个元素。

6.向栈中压入元素的操作是先移动栈顶指针，后存入元素。

7.从循环队列中删除一个元素时，其操作是先移动队首指针，后取出元素。

8.K00年统考题》带表头结点的空循环双向链表的长度等于0。

解：

headIL=head|头结点IR=heaJ-

二、判断正误(判断下列概念的正确性，并作出简要的说明。)(每小题1分，共10分)

(X)1.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。

(X)2.在表结构中最常用的是线性表，栈和队列不太常用。

错，不一定吧？调用子程序或函数常用，CPU中也用队列。

(V)3.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

（J）4.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

（X）5.栈和链表是两种不同的数据结构。

错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。

（X）6.栈和队列是一种非线性数据结构。

错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

（V）7.栈和队列的存储方式既可是顺序方式，也可是链接方式。

（V）8.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底

分别设在这片内存空间的两端。

（X）9.队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。

错，后半句不对。

（X）10.一个栈的输入序列是12345,则栈的输出序列不可能是12345。

错,有可能。

三、单项选择题（每小题1分，共20分）

（B）1.K00年元月统考题11栈中元素的进出原则是

A.先进先出B.后进先出C.栈空则进D.栈满则出

（C）2.R李春葆】若已知一个栈的入栈序列是1,2,3,…，n,其输出序列为pl,p2,p3,…，

pn,若pl=n,则pi为

A.iB.n=iC.n-i+1D.不确定

解释：当pl=n,即n是最先出栈的，根据栈的原理，n必定是最后入栈的（事实上题目已经表明了），那

么输入顺序必定是1,2,3,…，n,则出栈的序列是n,…，3,2,1«

（若不要求顺序出栈，则输出序列不确定）

（B）3.K李春葆】判定一个栈ST（最多元素为m0）为空的条件是

A.ST->topoOB.ST->top=0C.ST->topomOD.ST->top=mO

（A）4.K李春葆1判定一个队列QU（最多元素为mO）为满队列的条件是

A.QU->rear—QU->front==mOB.QU->rear—QU->front_1==mO

C.QU->front==QU->rearD.QU->front==QU->rear+l

解：队满条件是元素个数为mO。山于约定满队时队首指针与队尾指针相差1,所以不必再减1f,应当选

Ao当然，更正确的答案应该取模，即：QU->fronl==（QU->rear+1）%mO

（D）5.数组Q[n]用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾元素的

位置，假定队列中元素的个数小于n,计算队列中元素的公式为

(A)r—f;(B)(n+f—r)%n;(C)n+r—f;(D)(n+r—f)%n

6.198初程P71】从供选择的答案中，选出应填入下面叙述内的最确切的解答，把相应编号写

在答卷的对应栏内。

设有4个数据元素al、a2、a3和a4,对他们分别进行栈操作或队操作。在进栈或进队操作时，按al、

a2、a3、a4次序每次进入•个元素。假设栈或队的初始状态都是空。

现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是—A

,第二次出栈得到的元素是是；类似地，考虑对这四个数据元素进行的队操作是进队两次，出

队一次，再进队两次，出队一次；这时，第一次出队得到的元素是C,第二次出队得到的元素是D

。经操作后，最后在栈中或队中的元素还有一个。

供选择的答案:

A-D：①al②a2③a3④a4

E：①1②2③3④0

答：ABCDE=21AA2

7.194初程P75】从供选择的答案中，选出应填入下面叙述？内的最确切的解答,把相应编号写

在答卷的对应栏内。

栈是一种线性表，它的特点是上。设用一维数组A”,…,n］来表示一个栈，A［n］为栈底，用整型变

量T指示当前栈顶位置，A［T］为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值_；从栈

中弹出（POP）一个元素时，变量T的值C。设栈空时，有输入序列a,b,c,经过PUSH,POP,PUSH,

PUSH,POP操作后，从栈中弹出的元素的序列是_，变量T的值是）

供选择的答案:

A：①先进先出②后进先出③进优于出④出优于进⑤随机进出

B,C：①加1②减1③不变④清0⑤加2⑥减2

D：①a,b②b,c③c,a@b,a⑤c,b@a,c

E：①n+1②n+2③n④n-1⑤n-2

答案：ABCDE=2,2.1,6,4

注意，向地址的高端生长，称为向上生成堆栈；向地址低端生长叫向下生成堆栈，本题中底部为n,向地

址的低端递减生成，称为向F生成堆栈。

8.191初程P77】从供选择的答案中，选出应填入下面叙述内的最确切的解答，把相应编号写

在答卷的对应栏内。

在做进栈运算时，应先判别栈是否A；在做退栈运算时，应先判别栈是否」。当栈中元素为

n个，做进栈运算时发生上溢，则说明该栈的最大容量为C

为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的D

分别设在这片内存空间的两端，这样，只有当E时,才产生上溢。

供选择的答案:

A,B：①空②满③上溢④下溢

C：①n-1②n③n+1④n/2

D：①长度②深度③栈顶④栈底

E：①两个栈的栈顶同时到达栈空间的中心点②其中一个栈的栈顶到达栈空间的中心点

③两个栈的栈顶在达栈空间的某一位置相遇④两个栈均不空，且个栈的栈顶到达另一个栈的栈底

答案：ABCDE^2,1,2,4,3

四、简答题（每小题4分，共20分）

1.【严题集3.2①和3.11①】说明线性表、栈与队的异同点。

刘答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特

殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。

不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先

出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。

②用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。

2.【统考书P604-11,难于严题集3.1①】设有编号为1,2,3,4的四辆列车，顺序进入一个栈式结构的

车站，具体写出这四辆列车开出车站的所有可能的顺序。

刘答：至少有14种。

①全进之后再出情况，只有1种：4,3,2,1

②进3个之后再出的情况，有3种，3,4,213,2,4,13,2,1,4

③进2个之后再出的情况，有5利24,3,12,3,4,12,1,3,42,1,4,32,1,3,4

④进1个之后再出的情况，有5种，1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,3

3.【刘自编】假设正读和反读都相同的字符序列为“回文”，例如，‘abba'和'abcba'是回文，'abcde'

和＜ababab,则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出

其回文的可能性？

答：线性表是随机存储，可以实现，靠循环变量（j-）从表尾开始打印输出；

堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可；

队列是先进先出，不易实现。

哪种方式最好，要具体情况具体分析。若正文在机内已是顺序存储，则直接用线性表从后往前读取即

可，或将堆栈栈顶开到数组末尾，然后直接用POP动作实现。（但堆栈是先减后压还是……）

若正文是单链表形式存储，则等同于队列，需开辅助空间，可以从链首开始入栈，全部压入后再依次

输出。

4.【统考书P604-13］顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满?

答：一般的一维数组队列的尾指针己经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，

这就叫“假溢出

采用循环队列是解决假溢出的途径。

另外，解决队满队空的办法有三：

①设置一个布尔变量以区别队满还是队空；

②浪费一个元素的空间，用于区别队满还是队空。

③使用一个计数器记录队列中元素个数（即队列长度）。

我们常采用法②，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。

判断循环队列队空标志是：f=rear队满标志是：f=（r+l）%N

5.【统考书P604-14］设循环队列的容量为40（序号从0到39）,现经过一系列的入队和出队运算后，有

①front=ll,rear=19;②front=19,rear=ll；问在这两种情况下，循环队列中各有元素多少个？

答：用队列长度计算公式：（N+r—f）%N

①L=（40+19-11）%40=8②L=（40+11-19）%40=32

五、阅读理解（每小题5分，共20分。至少要写出思路）

1.【严题集3.7①】按照四则运算加、减、乘、除和幕运算（t）优先关系的惯例，并仿照教材例3-2的

格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：

A-BXC/D+EtF

当前字符备注

序号OPTR栈OPND栈

A—B«C/D+E■FU（操作）

1U*push(OPND,'A')

2nA•pushCOPTR/-*)

3A•push(OPND,'B')

4#一AB•push(OPTR,***)

5#—•AB•push(OPND.rC)

6#—»ABC*归约.令Ti=B*C

7#一AT.*push(OPTRZ/*)

8#一AT.*push(OPND/iy)

9#-/ATjD*归约.令TLT/D

10#一/AT：*归约.令T严A-T;

11nT,•push(OPTR/+r)

12#+T,•push(OPND/Er)

13廿十T,E*push(OPTR/f#)

14TjE•push(OPND/F)

15#4-tTjEF*归约.令T,=E+F

*

16#+T,T4归约.令Ts=T,+T.

f17#T*return(Ts)

答：-----s

2.1严题集3.3@］写出下列程序段的输出结果(栈的元素类型SElemType为char)。

voidmain(){

StackS;

Charx,y;

InitStack(S);

X='c';y='k';

Push(S,x);Push(S/a,);Push(S,y);

Pop(S,x);Push(S,'l');Push(S,x);

Pop(S,x);Push(S,'s');

while(!StackEmpty(S)){Pop(S,y);printf(y);};

Printf(x);

)

答：输出为“stack”。

2.【严题集3.12②】写出下列程序段的输出结果(队列中的元素类型QElemType为char)。

voidmain(){

QueueQ;InitQueue(Q);

Charx=,e,;y=,c,;

EnQueue(Q,'h')；EnQueue(Q,'r‘)；EnQueue(Q,y);

DeQueue(Q,x);EnQueue(Q,x);

DeQueue(Q,x)；EnQueue(Q,'a')；

while(!QueueEmpty(Q)){DeQueue(Q,y)；printf(y);};

Printf(x);

)

答:输出为“char”。

3.【严题集3.13@]简述以下算法的功能(栈和队列的元素类型均为int)o

voidalgo3(Queue&Q){

StackS;intd;

InitStack(S);

while(IQueueEmpty(Q)){

DeQueue(Q,d);Push(S,d)；

)；

while(!StackEmpty(S)){

Pop(S,d);EnQueue(Q,d);

)

)

答：该算法的功能是：利用堆栈做辅助，将队列中的数据元素进行逆置。

六、算法设计(每小题5分，共15分。至少要写出思路)

1.【李春葆及严题集3.19@]假设一个算术表达式中包含圆括弧、方括弧和花括弧三种类型的括弧，编

写一个判别表达式中括弧是否正确配对的函数correct(exp,tag)；其中：exp为字符串类型的变量(可理

解为每个字符占用一个数组元素)，表示被判别的表达式，tag为布尔型变量。

答：用堆栈st进行判定，将目、或卬入栈，当遇到5、[±\或H时，检查当前栈顶元素是否是对

应的口、匚口或E，若是则退栈，否则返回表示不配对。当整个算术表达式检查完毕时，若栈为空表示括

号正确配对，否则不配对。

编程后的整个函数如下(李书P31—32)

#definemO100/*m0为算术表达式中最多字符个数*/

correct(exp,tag)

charexp[m0];

inttag;

{charst[mO];

inttop=0,i=l;

tag=l;

while(i<=m0&&tag)

{if(exp[i]==<(<llexp[i]==>[1lexp[i]=/*遇到'『或则将其入栈*/

{top++;

st[top]=explij;

)

if(exp[i]==9?)/*遇到)，若栈顶是中,则继续处理,否则以不配对返回*/

if(st[top]=='(')top";

elsetag=0;

if(exp[i]==33/*遇到']'，若栈顶是'['，则继续处理，否则以不配对返回*/

if(st[top]=='[']top—;

elsetag=0;

if(exp[i]==7)信遇到，}',若栈顶是则继续处理,否则以不配对返回*/

if(st[top]==4{4top—;

elsetag=0;

i++；

)

if(top>0)tag=0;/*若栈不空，则不配对*/

)

严题集对应答案：

3.19

StatusAllBrackets_Test(char*str)〃判别表达式中三种括号是否匹配

(

InitStack(s);

for(p=str;*p;p++)

(

if(*p==«(,ll*p==,[,ll*p==,{')push(s,*p);

elseif(*p==》[*p==TII*p=丁)

(

if(StackEmpty(s))returnERROR;

pop(s,c);

if(*p==')'&&c!=,(,)returnERROR;

if(*p==T&&c!='「)returnERROR;

if(*p==T&&c!±{)returnERROR;〃必须与当前栈顶括号匹配

)

)//for

if(!StackEmpty(s))returnERROR;

returnOK;

}//AllBrackets_Test

2001级通信6班张沐同学答案(已上机通过)

#include<stdio.h>

#include<stdlib.h>

voidpush(charx);

voidpop();

voidcorrect(enumBoolean&tag);

〃原来的定义是voidcorrect(structStack*head,enumBoolean&tag);

typedefstructStack

(

chardata;

structStack*next;

)；

structStack*head,*p;

enumBoolean{FALSE,TRUEJtag;

voidmain()

(

head=(structStack*)malloc(sizeof(structStack));

head->data=,S,;

head->next=NULL;

//head'sdatahasnotbeeninitialized!!

correct(tag);

if(tag)

printf(MRight!M);

else

printf("Wrong!u);

voidpush(charx)

p=(structStack*)malloc(sizeof(structStack));

if(!p)

printfC'There'snospace.\nn);

else

(

p->data=x;

p->next=head;

head=p;

)

)

IIifyoudefinethe"Correct"functionlikethat

//DebugwillshowthatthePushactiondoesn'ttakeeffection

voidpop()

(

if(head->next==NULL)

printf(nThestackisempty.\nn);

else

(

p=head;

head=head->next;

free(p);

//voidcorrect(structStack*head,enumBoolean&tag)

voidcorrect(enumBoolean&tag)

(

inti;

chary;

printf("Pleaseenterabds:n);

for(i=0;y!=\n';i++)

scanf("％c”,&y);

if((y==y&&head->data==,(,)ll(y=='],&&head->data==,[,)ll(y==,},&&head->data=='{'))

pop();

elseif((y=='(')ll(y=='[')H(y=='{'))

push(y);

/*调试程序显示，y并没有被推入堆栈中。即head->data的值在Push中显示为y的值，但是出Push函数。

马上变成Null。*/

else

continue;

}

if(head->next==NULL)〃原来的程序是if(head==NULL)tag=TRUE;

tag=TRUE;

else

tag=FALSE;

)

/*总结：由于head为全局变量，所以不应该将其再次作为函数的变量。因为C语言的函数变量是传值机

制，所以在函数中对参数进行了拷贝复本，所以不能改变head的数值。*/

2.【统考书P604-15]假设一个数组squ[m]存放循环队列的元素。若要使这m个分量都得到利用，则需

另一个标志tag,以tag为0或1来区分尾指针和头指针值相同时队列的状态是“空"还是“满二试编写

相应的入队和出队的算法。

解：这就是解决队满队空的三种办法之①设置一个布尔变量以区别队满还是队空(其他两种见筒答题)；

思路：一开始队空，设tag=O,若从rear端加到与front指针相同时，发示入队已满，则令tag=l；

若从front一端加到与rear指针相同时，则令tag=0,表示出队己空。

3.【严题集3.31③】试写一个算法判别读入的一个以'@'为结束符的字符序列是否是“回文

答：编程如下：

intPalindrome_Test()〃判别输入的字符串是否回文序列，是则返回1,否则返回0

(

InitStack(S);InitQueue(Q);

while((c=getchar())!='@')

(

Push(S,c);EnQueue(Q,c)；〃同时使用栈和队列两种结构

)

while(!StackEmpty(S))

Pop(S,a);DeQueue(Q,b));

if(a!=b)returnERROR;

returnOK;

}//Palindrome_Test

第6章树和二叉树自测卷解答

一、下面是有关二叉树的叙述，请判断正误（每小题1分，共10分）

（7）1.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有曰个非空指针域。

（X）2.二叉树中每个结点的两棵子树的高度差等于1。

（V）3.二叉树中每个结点的两棵子树是有序的。

（X）4.二叉树中每个结点有两棵非空子树或有两棵空子树。

（X）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于

其右非空子树（若存在的话）所有结点的关键字值。（应当是二叉排序树的特点）

（X）6.二叉树中所有结点个数是2kL1,其中k是树的深度。（应2」）

（X）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。

（X）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有要一1个结点。（应2"）

（J）9用二叉链表法Qink-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为

空指针。

（正确。用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每

一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指

针。）即有后继链接的指针仅n-1个。

（V）10.K01年计算机系研题》具有12个结点的完全二叉树有5个度为2的结点。

最快方法：用叶子数=fn/2]=6,再求n2=n（＞-l=5

二、填空（每空1分，共15分）

1.由3个结点所构成的二叉树有_匚种形态。

2.【计算机研2000】一棵深度为6的满二叉树有n!+n2=0+n2=111rl=31个分支结点和2.=32个叶

子。

注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。

3.一棵具有257个结点的完全二叉树，它的深度为9。

（注：用Llog2（n）」+l=L8.xx」+1=9

4.【全国专升本统考题】设一棵完全二叉树有700个结点，则共有350个叶子结点。

答：最快方法：用叶子数=皿2]=350

5.设一棵完全二叉树具有1000个结点，则此完全二叉树有500个叶子结点,有499个度为2的结

点，有个结点只有非空左子树，有0个结点只有非空右子树。

答：最快方法：用叶子数=[n⑵=500,n2=n0-l=499o另外，最后一结点为2i属于左叶子，右叶子是空

的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数=0.

6.【严题集6.7③】一棵含有n个结点的k叉树，可能达到的最大深度为口,最小深度为2。

答：当k=l（单叉树）时应该最深，深度=n（层）；当k=n-l（n-1叉树）时应该最浅，深度=2（层），但不

包括n=0或1时的特例情况。教材答案是“完全k叉树"，未定量。）

7.196程试题1】二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍

历次序有六种。最常用的是三种：前序法（即按NLR次序），后序法（即按LRN次序）和中序

法（也称对称序法，即按LNR次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是

BEFCGDH,中序序列是FEBGCHD,则它的后序序列必是FEG

HDCB<,

解：法1：先由已知条件画图，再后序遍历得到结果；

法2：不画图也能快速得出后序序列，只要找到根的位置特征。由前

序先确定root,由中序先确定左子树。例如，前序遍历BEFCGDH中，

根结点在最前面，是B；则后序遍历中B一定在最后面。

法3：递归计算。如B在前序序列中第一，中序中在中间（可知左

右子树上有哪些元素），则在后序中必为最后。如法对B的左右子树同样处理，则问题得解。

8.【全国专升本统考题】中序遍历的递归算法平均空间复杂度为0（n）。

答：即递归最大嵌套层数，即栈的占用单元数。精确值应为树的深度k+1,包括叶子的空域也递归了一次。

9.1计算机研2001）用5个权值｛3,2,4,5,1｝构造的哈夫曼（Huffman）树的带权路径长度是33。

解：先构造哈夫曼树，得到各叶子的路径长度之后便可求出WPL=（4+5+3）X2+（1+2）X3=33

（注：两个合并值先后不同会导致编码不同，即哈夫曼编码不唯一）

（注：合并值应排在叶子值之后）

（注：原题为选择题：A.32B.33C.34D.15）

三、单项选择题（每小题1分，共11分）

（C）1.不含任何结点的空树

（A）是一棵树；（B）是一棵二叉树；

（C）是一棵树也是一棵二叉树；（D）既不是树也不是二叉树

答：以前的标答是B,因为那时树的定义是n2l

（C）2.二叉树是非线性数据结构，所以

(A)它不能用顺序存储结构存储；(B)它不能用链式存储结构存储；

(C)顺序存储结构和链式存储结构都能存储；(D)顺序存储结构和链式存储结构都不能使

用

(C)3.K01年计算机研题X具有n(n>0)个结点的完全二叉树的深度为。

(A)Flog2(n)l(B)Llog2(n)J(C)Llog2(n)J+l(D)riog2(n)+ll

注1：「xl表示不小于x的最小整数：Lx」表示不大于x的最大整数，它们与口含义不同！

注2：选(A)是错误的。例如当n为2的整数基时就会少算一层。似乎11。826)+1」是对的？

(A)4.把一棵树转换为二叉树后，这棵二叉树的形态是。

(A)唯一的(B)有多种

(C)有多种，但根结点都没有左孩子(D)有多种，但根结点都没有右孩子

5.194程PU】从供选择的答案中，选出应填入下面叙述？内的最确切的解答,把相应编号写在

答卷的对应栏内。

树是结点的有限集合，它在根结点，记为T。其余的结点分成为m(m20)个」

的集合Tl,T2,…，Tm,每个集合又都是树，此时结点T称为Ti的父结点，「称为T的子结点(IWiWm)。

一个结点的子结点个数为该结点的」

供选择的答案

A：①有。个或1个②有0个或多个③有且只有1个④有1个或1个以上

B:①互不相交②允许相交③允许叶结点相交④允许树枝结点相交

C：①权②维数③次数(或度)④序

答案：ABC=1,1,3

6.195程P13］从供选择的答案中，选出应填入下面叙述?内的最确切的解答，把相应编号写在

答卷的对应栏内。

二叉树Ao在完全的二叉树中，若一个结点没有B,则它必定是叶结点。每棵树都能惟一地转

换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子女是N在原树里对应结点的_^，

而N的右子女是它在原树里对应结点的o

供选择的答案

A：①是特殊的树②不是树的特殊形式③是两棵树的总称④有是只有二个根结点的树形结构

B:①左子结点②右子结点③左子结点或者没有右子结点④兄弟

C-D：①最左子结点②最右子结点③最邻近的右兄弟④最邻近的左兄弟

⑤最左的兄弟⑥最右的兄弟

答案：A=B=C=D=

答案：ABCDE=2,1,1,3

四、简答题(每小题4分，共20分)

1.【严题集6.2①】一棵度为2的树与一棵二叉树有何区别？

答：度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中

若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是个孩子也有左右之分。

2.R01年计算机研题》设如下图所示的二叉树B的存储结构为二叉

链表，root为根指针，结点结构为：(lchild,data,rchild)。其中Ichild,C的结点类型定义如下：

rchild分别为指向左右孩子的指针，data为字符型，root为根指针，structnode

{chardata;

试回答下列问题：structnode*lchild,rchild;

)；

1.对下列二叉树B,执行下列算法traversal(root),试指出其输出结

果；C算法如下：

voidtraversal(structnode*root)

2.假定二叉树B共有n个结点，试分析算法traversal(root)的时间复{if(root)

{printf("%c”,root->data);

杂度。(共8分)traversal(root->lchild);

printf("%c”,root->data);

Atraversal(root->rchild);

B/\D

C/F/、G

\E

二叉树B

解：这是“先根再左再根再右”，比前序遍历多打印各结点一次，输

出结果为：ABCCEEBADFFDGG

特点：①每个结点肯定都会被打印两次；②但出现的顺序不同，其规律是：凡是有左子树的结点，必间隔

左子树的全部结点后再重复出现；如A,B,D等结点。反之马上就会重复出现。如C,E,F,G等结点。

时间复杂度以访问结点的次数为主，精确值为2*n,时间渐近度为O(n).

3.KOI年计算机研题』【严题集6.27③】给定二叉树的两种遍历序列，分别是：

前序遍历序列：D,A,C,E,B,H,F,G,I；中序遍历序列：D,C,B,E,H,A,G,I,F,

试画出二叉树B,并简述山任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。

解：方法是：由前序先确定root,由中序可确定root的左、右子树。然后由其左子树的元素集合和右子

树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将他们分别作为新的root,不

断递归，则所有元素都将被唯一确定，问题得解。

H

4.1计算机研2000】给定如图所示二叉树T,请画出与其对应的中序线索二叉树。

解：要遵循中序遍历的轨迹来画出每个前驱和后继。

25/73

中序遍历序列：55402560280833544(70szz34

5V

28

25餐33

4411AAA

A40-二62：。83S4i

A-

55

五、阅读分析题（每题5分，共20分）

1.（P604-26）试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。

答:DLR：ABDFJGKCEHILM

LDR:BFJDGKACHELIM

LRD：JFKGDBHLMIECA

2.（P604-27）把如图所示的树转化成二叉树。

答：注意全部兄弟之间都要连线（包括度为2