数据结构练习题

数据结构练习题

习题1绪论

一、基本内容

数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含

义；算法设计的基本要求以及从时间和空间角度分析算法的方法。

二、要点：

1.熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构

2.理解算法五个要素的确切合义：动态有穷性（能执行结束）；确定性（对于相同的输

入执行相同的路径）；有输入；有输出；可行性（用以描述算法的操作都是可以通过已经

实现的基本的运算执行有限次来实现的）。

3.掌握计算语句频度和估算算法时间复杂度的方法。

1.1选择题

1.数据结构是一门研究非数值计算的程序设计问题中,数据元素的①—、数据信息在

计算机中的②以及一组相关的运算等的课程。

①A.操作对象B.计算方法|C.逻辑结构|D.数据映象

②|A.存储结航HB.关系C.运算D.算法

2.数据结构DS（DataStruct）可以被形式地定义为DS=（D,R）,其中D是①的

有限集合，R是D上的②有限集合。

①A.算法数据元素C.数据操作D.数据对象

②A.操作B.映象C.存储|D.关系

3.在数据结构中，从逻辑上可以把数据结构分成一_________O

A.动态结构和静态结构B.紧凑结构和非紧凑结构

C.线性结构和非线性结构D.内部结构和外部结构

4.算法分析的目的是①，算法分析的两个主要方面是②

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

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

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

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

5.计算机算法指的是①，它必具备输入、输出和②等五个特性。

①A.计算方法B.排序方法

C.解决问题的有限运算序列D.调度方法

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

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

1.2填空题（将正确的答案填在相应的空中）

1.数据结构的三个要点是数据元素的逻辑结构、数据在计算机中的存储结构和数据

的运算。

1.数据逻辑结构包括线性结构、树形结构、图形结构三种类型,树形结构和图形结

构合称为非线性结构。

2.在线性结构中，第一个结点没有前驱结点,其余每个结点有且只有1_个前驱结

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

3.在树形结构中，树根结点没有前驱结点,其余每个结点有且只有个直接前驱

结点，叶子结点没有后续结点，其余每个结点的直接后续结点可以任意多个。

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

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

形结构中元素之间存在多对多关系。

6.算法的五个重要特性是有穷性、确定性、可行性、输入、输出。

7.分析下面算法(程序段)，给出最大语句频度：。，时间复杂度：.0(n2)o

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

for(j=O；j<n;j++)

A[i][j]=0;

8.分析下面算法(程序段)，给出最大语句频度：n(n+析2,时间复杂度：.0肝)

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

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

A[i]U]=0；

9.分析下面算法(程序段)，最大语句频度：rr3,时间复杂度：.0(N)

s=0;

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

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

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

s=s+B[i][j][k];

sum=s;

J1

10.分析下面算法(程序段)给出最大语句频度：金，时间复杂度：.o(/)

i=s=0;

while(s<n){i++;s+=i;}

11.分析下面算法(程序段)给出最大语句频度：loq£n,时间复杂度：.0(l0Q?n)

i=1；

while(i<=n)i=i*2;

1.3简答题

1、试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。

例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行

记成的表。这个表就是一个数据结构。

每个记录(有姓名，学号，成绩等字段)就是一个结点，对于整个表来说，只有一

个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各

有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这儿

个关系就确定了这个表的逻辑结构。

那么我们怎样把这个表中的数据存储到计算机里呢？用高级语言如何表示各结点

之间的关系呢？是用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放

各结点数据再用指针进行链接呢？这就是存储结构的问题，我们都是从高级语言的层

次来讨论这个问题的。

最后，我们有了这个表(数据结构)，肯定要用它，那么就是要对这张表中的记录进

行查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是

数据的运算问题了。

2、常用的存储表示方法有哪儿种？

常用的存储表示方法有两种：顺序存储方法和链接存储方法

3、设n为正整数，利用大"0”记号，将下列程序段的执行时间表示为n的函数。

(1)i=1;k=0

while(i<n){k=k+10*i;i++;}.T(n)=n-1/.T(n)=O(n)O这个函数是按线

性阶递增的

(2)i=0;k=0;

do{k=k+10*i;i++;}while(i<n)；♦T(n)=nT(n)=0(n)◊这也是线性

阶递增的

(3)x=n;//n>1

while(x>=(y+1)*(y+1))

y++;♦T(n)=n1/2Z.T(n)=O(n1/2)O最坏的情况是y=0,那么循

环的次数是n”2次，这是一个按平方根阶递增的函数。

(4)x=91;y=100;

while(y>0)

if(x>1OO){x=x-10;y-;}

elsex++;♦T(n)=O(1)O这个程序总共循环运行了1000次，但是我

们看到n没有？没有。这段程序的运行是和n无关的，只是一个常数阶的函数。

4、算法的时间复杂度仅与问题的规模相关吗？

No,事实上，算法的时间复杂度不仅与问题的规模相关，还与输入实例中的元素

取值等相关，但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。

我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。

习题2线性表

一、基本内容

线性表的逻辑结构定义和各种存储结构的描述方法；在线性表的两类存储结构(顺序

的和链式的)上实现基本操作；一元多项式的表示及相加。

二、学习要点

1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这

种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表

简称为顺序表，用后者表示的线性表简称为链表。

2.熟练掌握这两类存储结构的描述方法，如一维数组中一个区域的上、下界和长度

之间的变换公式，链表中指针P和结点p的对应关系(结点p—>next是结点P的后继

等），链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。链

表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基

本要求。

3.熟练掌握线性表在顺序存储结构上实现基本操作：查找、插入和删除的算法。

4.熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用

适当的链表结构。

5.从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用

场合。

2.1单项选择题

1.一个向量（即一批地址连续的存储单元）第一个元素的存储地址是100,每个元素

的长度为2,则第5个元素的地址是。

A.110|B.108|C.100D.120

2.线性表的顺序存储结构是一种—的存储结构，而链式存储结构是一种的存储

结构。

A.|随机存取|B.索引存取|C.顺序存取刀D.散列存取

3.线性表的逻辑顺序与存储顺序总是一致的，这种说法o

A.正确B.不正确

4.线性表若采用链式存储结构时，要求内存中可用存储单元的地址。

A.必须是连续的B.部分地址必须是连续的

C.一定是不连续的|D.连续或不连续都可以

5.在以下的叙述中，正确的是o

线性表的顺序存储结构优于链表存储结构

线性表的顺序存储结构适用于频繁插入/删除数据元素的情况

线性表的链表存储结构适用于频繁插入/删除数据元素的情况

线性表的链表存储结构优于顺序存储结构

6.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法o

A.正确|B.不正确

7.不带头结点的单链表head为空的判定条件是—o

A.head==NULLB.head->next==NULL

C.head->next==headD.head!=NULL

8.带头结点的单链表head为空的判定条件是—o

A.head==NULLB.head->next==NULL

C.head->next==headD.head!=NULL

9.非空的循环单链表head的尾结点（由p所指向）满足。

A.p->next==NULLB.p==NULL

C.p->next==head|D.p==head

10.在双向循环链表的p所指结点之后插入s所指结点的操作是—o

A.p->right=s;s->Ieft=p;p->right->left=s;s->right=p->right;

B.p->right=s;p->right->left=s;s->left=p;s->right=p->right;

C.s->left=p;s->right=p->right;p->right=s;p->right->left=s;

D.s->left=p;s->right=p->righ>p->right->left=s;p->right=s;

11.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入

s结点，则执行

A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;

B.q->next=s;s->next=p;C.p->next=s;s->next=q;

12.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行

A.s->next=p;p->next=s;B.s->next=p->next;p->next=s;

C.s->next=p->next;p=s;C.p->next=s;s->next=p;

13.在一个单链表中，若删除p所指结点的后续结点，则执行—。

A.p->next=p->next->next；B.p=p->next;p->next=p->next->next；

C.p->next=p->next;D.p=p->next->next；

14.从一个具有n个结点的单链表中查找其值等于x结点时一，在查找成功的情况下，需

平均比较一个结点。

A.nB.n/2C.(n-l)/20(n+l)/2

15.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是

2

A.O⑴O(n)C.O(n)D.O(nlog2n)

16.给定有n个元素的向量，建立一个有序单链表的时间复杂度是。

A.0(1))B.O(n)匕.O(I?)|D.O(n*log2n)

2.2填空题(将正确的答案填在相应的空中)

1.对于顺序表(采用顺序存储结构的线性表)(a.,a2,%),设L表示一个元素

占用的存储单元个数，LOC(aJ表示线性表第i个元素的地址，已知第1个元素的地址

为LOC(a),则LOC⑸)=

2.向一个长度为n的顺序表的第i个元素(IWiWn+l)之前插入一个元素时，需向

后移动n-i+l个元素。

3.向一个长度为n的顺序表中删除第i个元素(IWiWn)时，需向前移动n-i

个元素。

4.单链表可以看做线性表的链式存储表示。

5.在双链表中，每个结点有两个指针域，一个指向前驱结点一，另一个指向一后继结

点___O

6.带头结点的单链表中，除头结点外，任一结点的存储位置是在其前驱结点的指针域中。

7.单链表中引入头结点的作用是在链表的第一个位置上行插入和删除等操作时无须进

行特殊处理

8.一个长为n的线性表，其排序时间性能最优为.O(n*Lo咫n)。

9.在一个单链表中p所指结点之前插入一个s(值为e)所指结点时，可执行如下操作：

q=head;

while(q->next!=p)q=q->next;

s=(structnode*)malloc(sizeof(structnode));s->data=e;

q->next=s;//填空

s->next-p;//填空

10.在一个单链表中删除p所指结点的后继结点时，应执行以下操作：

q=p->next;

p->next=q->next;〃填空

free(q);//填空

11.在一个单链表中p所指结点之后插入一个s所指结点时,应执行s->next=p->next和

p->next=s的操作。

12.对于一个具有n个结点的单链表,在已知p所指结点后插入一个新结点的时间复杂

度是一在给定值为x的结点后插入一个新结点的时间复杂度是O(n)。

13.第二章作业题

习题3栈和队列

一、基本内容

栈和队列的结构特点；在两种存储结构上如何实现栈和队列的基本操作以及栈和

队列在程序设计中的应用。

二、学习要点

1.掌握栈和队列的特点。

2.熟练掌握栈类型的两种实现方法，即两种存储结构表示时的基本操作实现算法，

特别应注意栈满和栈空的条件以及它们的描述方法。

3.熟练掌握循环队列的基本操作实现算法.持别注意队满和队空的描述方法。

4.理解递归算法执行过程中栈的状态变化过程。

3.1单项选择题

1.一个栈的入栈序列a,b,c,d,e,则栈的不可能的输出序列是—o

A.edcbaB.decbaC.dceabD.abcde

2.若已知一个栈的入栈序列是1,2,3,n,其输出序列为pl,p2,p3,…，pn,

若pl=n,则pi为o

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

3.栈结构通常采用的两种存储结构是一。

A.顺序存储结构和链式存储丽B.散列方式和索引方式

C.链表存储结构和数组D.线性存储结构和非线性存储结构

4.判定一个顺序栈ST（最多元素为mO）为空的条件是o

A.top!=0B.top==0C.top!=m0D.top==m0-l

5.判定一个顺序栈ST（最多元素为mO）为栈满的条件是o

A.top!=0B.top==0C.top!=m0D.top==m0

6.栈的特点是_B_,队列的特点是_A_。

A.先进先出B.先进后出

7.向一个栈顶指针为HS的链栈中插入一个s所指结点时-，则执行o（不带空的

头结点）

A.HS—＞next=s;

B.s-＞next=HS一＞next;HS一＞next=s;

C.s-＞next=HS;HS=s;

D.s-＞next=HS;HS=HS一＞next;

8.从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行

。（不带空的头结点）

A.x=HS;HS=HS—＞next;B.x=HS—＞data;

C.HS=HS一＞next;x=HS一＞data;D.x=HS一＞data;HS=HS一＞next;

9.一个队列的数据入列序列是1,2,3,4,则队列的出队时输出序列是—o

A.4,3,2,1|B.1,2,3,4

C.1,4,3,2D.3,2,4,1

10.判定一个循环队列QU（最多元素为m）为空的条件是—o

A.rear-front==mB.rear-front-l==m

C.front==rearD.front==rear+1

11.判定一个循环队列QU（最多元素为m,m==Maxsize-l）为满队列的条件是一。

A.（rear+1）%Maxsize==front

B.rear-front-l==mC.front==rearD.front==rear+1

12.循环队列用数组A[0,mT]存放其元素值，已知其头尾指针分别是front和rear,

则当前队列中的元素个数是—。

A.（rear-front+m）%mB.rear-front+1

C.rear-front-1D.rear-front

13.栈和队列的共同点是—。

A.都是先进后出B.都是先进先出

C.只允许在端点处插入和删除蒜D.没有共同点

3.2填空题（将正确的答案填在相应的空中）

1.向量、栈和队列都是线性结构,可以在向量的任何位置插入和删除元素:

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

删除元素。

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

4.对栈进行退栈时的操作是先移动栈顶指针，后取出元素。

对于顺序栈存放在一维数组s[0...M]o

按课件中的定义：

top=0为栈空,x入栈时,s[top]=x;top++；即先存入元素，后移动栈顶指针

top=MM栈满,出栈时，top—；x=s[top]o即先移动栈顶指针，后取出元素

按有些参考书中定义：

top=T表示栈空，x入栈时，top++,s[top]=x；即先移动栈顶指针,后存入元

素

top=MT表示栈满，出栈时，x=s[top]；top—o即先取出元素，后移动栈顶指

针

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

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

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

8.一个栈的输入序列是12345,则栈的输出序列43512是不可能的。

9.一个栈的输入序列是12345,则栈的输出序列12345是可能的。

10.想象六辆列车位于图中堆栈的输入一边，列车编号为123456,按此顺序开进堆栈，

且可在任意时刻开走，则能否得到325641出站序歹U?能否得到154623出站序歹U?在可能

的情况下，说明如何实现。能得至U325641.实现过程为；Push,push,push,pop,pop.

Push,push,pop,push,pop,pop,pop。不能得至U154623。

11.设循环队列存放在向量sq.data[o..m]中，则队头指针sq.front在循环意义下的加1

操作可用模运算表示为(sq.front+1)MOD(m+1)。若用牺牲一个单元的办法

来区分队满和队空条件，则队满条件可表示为(sq.rear+1)MOD(m+1)=

sq.fronto

12.设顺序栈存放在一维数组s[M],栈底位置是mT,则栈空条件top=0,栈满条

件是top=m。

13.循环队列只有下溢，没有上溢。(错误)

14.队列和栈都是运算受限的线性表，只允许在表的两端进行运算。(正确)

15.栈有哪儿种不同的存储结构?请分别画出在这些存储结构中元素a,b,c,J依次进

栈后堆栈的状态。链栈和顺序栈

17.循环队列入队、出队算法如下:

入队算法：

voiden_cycque(intsq[],intstart,intend^^t嘲始状态

{if(((end+l)%M)==start)printf("overflow");

else{end=(end+l)%M;sq[end]=x;}

出队算法:

intdl_cycque(intsq[],intstart,intend,int*q)

{if(start==end)return(0);

else{start=(start+l)%M;*q=sq[start];return(1);}

队列某个时刻的初始状态如图所示。

1).在初始状态上，画出a7、a8和a9入队后的状态图，

2).在初始状态上，画出a4、a5和a6出队后的状态图。

习题4串

一、基本内容

串的定义；串的三种存储表示：定长顺序存储结构、块链存储结构和堆分配存储

结构；串的各种基本操作的实现。

二、学习要点

1.熟悉串的基本操作的定义

2.掌握在串的定长顺序存储结构上实现串的各种操作的方法。

3.掌握串的堆存储结构以及在其上实现串操作的基本方法。

4.1单项选择题

1.以下叙述中正确的是。

A.串是一种特殊的线性表|B.串的长度必须大于零

C.串中元素只能是字母D.空串就是空白串

2.空串与空格串是相同的，这种说法—。

A.正确|B.不正确

3.串是一中特殊的线性表，其特殊性体现在__。

A.可以顺序存储数据元素是一个字符

C.可以链接存储D.数据元素可以是多个字符

4.设有两个串p和q,求q在p中首次出现的位置的运算称作——o

A.连接R模式匹配

C.求子串D.求串长

5.设串sUABCDEFG，，s2=，PQRS「，函数con(x,y)返回x和y串的连接串，subs(s,i,j)

返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则

con(subs(si,2,len(s2)),subs(si,len(s2),2))的结果串是。

A.BCDEFB.BCDEFG

C.BCPQRST，BCDEFEF

6.设串的长度为n,则它的子串个数为o

A.nB.n(n+l)除n(n+l)/21D.n(n+l)/2+l

4.2填空题(将正确的答案填在相应的空中)

1.串的三种存储表示：定长顺序存储结构、块链存储结构和堆分配存储结构

2.两个串相等的充分必要条件是两个串的长度相等且对应位置的字符相同。

3.空串是零个字符的串，其长度等于零。

4.空格串是由一个或多个空格字符组成的串，其长度等于其包含的空格个数。

5.设s=，I-AM—A^TEACHER，,其长度是14。

6.串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串中字符

构成的有限序列。(X)

7.如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。(X)

4.3算法设计题

写一个递归算法来实现字符串逆序存储，要求不另设存储空间。

voidreverse(chararr[])

{charch;inti=l;

do(ch=getchar();reverse(arr);

arr[i]=ch;i++;}while(ch!=z&&i<n)；

习题5数组和广义表

一、基本内容

数组定义及表示方式；特殊矩阵和稀疏矩阵的压缩存储方法及运算的实现；广义表

的逻辑结构和存储结构。

二、学习要点

1.了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算

方法。

2.掌握对特殊矩阵进行压缩存储时的下标变换公式。

3.了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩

阵时进行矩阵运算采用的处理方法。

4.掌握广义表的结构特点及其存储表示方法，读者可根据自己的习惯掌握任意一种

结构的链表

5.1单项选择题

1.常对数组进行的两种基本操作是—。

A.建立与删除B.索引和修改|C.对数据元素的存取和修阈D.查找与

索引

2.二维数组M的成员是6个字符（每个字符占一个存储单元，即一个字节）组成的串，

行下标i的范围从0到8,列下标j的范围从0到9,则存放M至少需要①一个字节;

M数组的第8列和第5行共占②个字节。

①A.90B.180C.240|D.540

②A.108B.114C.54D.60

3.二维数组A中，每个元素的长度为3个字节，行下标i从。到7,列下标j从。到

9,从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是—o

A.80B.100|C.240|D.270

4.二维数组A中，每个元素A的长度为3个字节，行下标i从。到7,列下标j

从0到9,从首地址SA开始连续存放在存储器内，该数组按行存放时,数组元素A[7][4]

的起始地址为—。

A.SA+141B.SA+144[C.SA+2221D.SA+225

5.二维数组A中，每个元素A的长度为3个字节，行下标i从。到7,列下标j

从0到9,从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]

的起始地址为—o

A.SA+141|B.SA+180]C.SA+222D.SA+225

5.2填空题(将正确的答案填在相应的空中)

1.已知二维数组采用行序为主方式存储，每个元素占k个存储单元，并且第

一个元素的存储地址是L0C(A[0][0]),则A[i][j]的地址是L0C也⑻⑹)+(n*i+O*k

___O

2.二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元并且A[0][0]

的存储地址是200,则A[6][12]的地址是200+(12*10+6)=326。

3.二维数组A[10..20][5..10]采用行序为主方式存储，每个元素占4个存储单元，并

且A[10][5]的存储地址是1000,则A[18][9]的地址是1000+((18-10)*6+(9-5的*4=

1208o

4.设此是矩阵A的第i行第j列非零元素，则b[k]与矩阵a[i,j]的一一对应关系：

k=j*(j-D/2+i且iV=j；k的取值范围为1,2….，n*(n+l)/2

5.求下列广义表操作的结果:

(1)GetTai1[GetHead[((a,b),(c,d))]];(b)

(2)GetTai1[GetHead[GetTai1[((a,b),(c,d))]]]|(d)]

6.利用广义表的GetHead和GetTail操作写出如上题的函数表达式,把原子banana分

别从下列广义表中分离出来.

(1)Li=(((apple)),((pear)),(banana),orange);

GetHead[GetHead[GetTai1[GetTai1[LJ]]];

(2)L2=(apple,(pear,(banana),orange));

GetHead[GetHead[GetTail[GetHead[GetTai1[L2]]]]]

7.对如图所示的稀疏数组，分别画出采用三元组表和带

-01290000-

0000000

行指针向量的单链表表示。

-30000140

M=

00240000

01800000

_1500-700()_6x7

5.3算法设计题：

1.假设稀疏矩阵A和B均以三元组顺序表作为存储结构。试写出矩阵相加的算法，另

设三元组表C存放结果矩阵。

2.假设系数矩阵A和B均以三元组顺序表作为存储结构。试写出满足以下条件的矩阵

相加的算法：假设三元组顺序表A的空间足够大，将矩阵B加到矩阵A上，不增加A,

B之外的附加空间，你的算法能否达到0(m+n)的时间复杂度？其中m和n分别为A,

B矩阵中非零元的数目。

习题6树和二叉树

一、基本内容

二叉树的定义、性质和存储结构；二叉树的遍历以及遍历算法的各种描述形式；

树和森林的定义、存储结构与二叉树的转换。本章是课程的重点内容之一。

二、学习要点

1.熟练掌握二叉树的结构特性，了解相应的证明方法。

2.熟悉二叉树的各种存储结构的特点及适用范围。

3.遍历二叉树是二叉树各种操作的基础。要熟练掌握各种遍历策略的递归算法

4.熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。建立存储

结构是进行其他操作的前提，因此读者应掌握1至2种建立二叉树和树的存储结构的

方法。

5.了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。

6.理解前序序列和中序序列可唯一确定一棵二叉树的道理.掌握由前序序列和中序

序列建立二叉树的存储结构的方法。

6.1单项选择题

1.由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树，这种说法—o

A.正确|B.错误

2.假定在一棵二叉树中，双分支结点数为15,单分支结点数为30个，则叶子结点数

为个。

A.15-IC.17D.47

3.按照二叉树的定义，具有3个结点的不同形状的二叉树有__种。

A.3B.4IC.5ID.6

4.按照二叉树的定义，具有3个不同数据结点的不同的二叉树有一种。

A.5B.6|C.30|D.32

5.深度为5的二叉树至多有__个结点。

A.16B.32|C.31|D.10

6.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点

数至少为。

A.2h|B.2hT|C.2h+lD.h+1

7.对一个满二叉树，m个树叶，n个结点，深度为h,则。

A.n=h+mB.h+m=2nC.m=h-l|D.n=2hR

8.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序。

A.不发生改变］B.发生改变C.不能确定D.以上都不对

9.如果某二叉树的前根次序遍历结果为stuwv,中序遍历为uwtvs,那么该二叉树的

后序为—。

A.uwvtsB.vwutsC.wuvtsD.wutsv

10.二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法

o|A.正确IB.错误

11.某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是

dgbaechf,则其后序遍历的结点访问顺序是。

A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca

12.在一非空二叉树的中序遍历序列中，根结点的右边o

A.只有右子树上的所有结点|B,只有右子树上的部分结点

C.只有左子树上的部分结点D.只有左子树上的所有结点

13.如图6.1所示二叉树的中序遍历序列是。

A.abcdgefC.dbaefcgD.defbagc

图6.1

14.一棵二叉树如图6.2所示，其中序遍历的序列为o

A.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgh

15.设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是。

A.a在b的右方氏a在b的五万

C.a是b的祖先D.a是b的子孙

16.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序

列是

A.acbedB.decabC.deabcD.cedba

图6.3

18.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先

序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应

的二叉树。结论___是正确的。

A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同

B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同

C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同

D.以上都不对

25.树最适合用来表示

A.有序数据元素B.无序数据元素

C.元素之间具有分支层次关系的数据D.元素之间无联系的数据

6.2填空题(将正确的答案填在相应的空中)

1.有一棵树如图6.5所示，回答下面的问题:

⑴这棵树的根结点是kl；

⑵这棵树的叶子结点是点k5k4k7；

⑶结点k3的度是N—；

(4)这棵树的度是3；

⑸这棵树的深度是4—；

(6)结点k3的子女是k5k6；

⑺结点k3的父结点是也____；1516.5一棵树

2.指出树和二叉树的三个主要差别树的结点个数至少为1(不同教材规定不同)，而二

义树的结点个数可以为Q树中结点的最大度数没有限制，而二义树结点的最大度数为

2；树的结点无左、右之分，而二义树的结点有左、右之分。

①一棵度为3的树与一棵二又树有何区别？

①试分别画出具有3个结点约树和3个结点的二叉树的所有不同形态。

3.从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是

树可采用孩子-兄弟链表（二叉链表）做存储结构，目的并利用二叉树的已有算法解

决树的有关问题。

4.一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如图6.6所示，则该

5.深度为k的完全二叉树至少有21"个结点。至多有2卜-1个结点，若按自上而下,

从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是2入+1。（第

kT层的第二个结点为编号最小的叶子结点，深度为k-2的满二叉树的结点数（2卜2-1）

+2=2卜2+1)

6.在一棵二叉树中，度为零的结点的个数为no,度为2的结点的个数为n2,则有

n（）=n2+lo

7.一棵二叉树的第i（i2l）层最多有个结点:一棵有n（n>0）个结点的满二

叉树共有2吃.1T［或（n+1）/2］个叶子和2nty1［或（51）

/2］个非终端结点。层数：k=［log2（n+l）］

8.结点最少的树为只有一个结点的树，结点最少的二叉树为空的二叉树—o

9.现有按中序遍历二叉树的结果为abc,问有5种不同形态的二叉树可以得到这一

遍历结果，这些二叉树分别是。

10.由如图6.9所示的二叉树，回答以下问题：「仁、

⑴其中序遍历序列为_dgbaechif__；

⑵其前序遍历序列为_abdgcefhi__；®

⑶其后序遍历序列为_gdbeihfca—；i

图6.9一棵二叉树

11.设有n个结点的完全二叉树顺序存放在向量a[l..n]中，对任一结点a[i],若a[i]

有父母，则其父母是a[i/2]。若a[i]有左子女,则左子女为a[2i]，若a[i]

有右子女，则右子女a[2i+l]；i值最大的分支结点是a[n/2]。

12.设T是非空的二叉树，若T的先序序列和中序序列相同，则T的形态是所有左子

树为空的二叉树，

,若T的先序序列和后序序列相同，则T的形态是所有右子树为空的二义树；

若T的中序序列和后序序列相同，则T的形态是具有0和1个结点的二叉树。

13.二叉树是度数为2的有序树。（正确）

14.存在这样的二叉树，对它采用任何次序的遍历，其结果相同。（正确。空树或只有

一个根结点的树）

15.完全二叉树中，若一个结点没有左孩子，则它必是树叶。（正确）

16.树形结构中，若结点A有4个兄弟，B是A的双亲，则B的度为5

6.3简答题

1.根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，请将它们分别画出。

图6.11树形5种

2.假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该

树。

3.由如图6.9所示的二叉树，画出该二叉树对应的森林。

4.已知一棵树如图6.14所示，转化为一棵二叉树，表示为

5.以数据集｛4,5,6,7,10,12,18｝为结点权值，画出构造Huffman树的每一步图

示，计算其带权路径长度为。

图6.16Huffman树

6.设T是一棵二叉树，除叶子结点外，其它结点的度数皆为2,若T中有6个叶结点,

试问：

(1)T树的最大可能深度Kmax=?最小可能深度Kmin=?Kmax=6；Kmin=4

(2)T树中共有多少非叶结点?|非叶结点有5不。

(3)若叶结点的权值分别为1,2,3,4,5,6O请构造一棵哈夫曼树，并计算该哈夫

曼树的带权路径长度wPl。wPIf=4X(1+2)+3X3+2X(4+6+5)=51

6.4算法设计题

1.编写按层次顺序(同一层自左至右)遍历二叉树的算法。

2.试编写算法，对一棵二叉树，统计叶子的个数。

3.试编写算法，对一棵二叉树根结点不变，将左、右子树进行交换，树中每个结点的

左、右子树进行交换。

7.假设用于通讯的电文仅有八个字母(③13”,46,£通,11)组成，字母在电文中出现的

频率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。试为这八个字母设

计哈夫曼编码。

使用。-7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺

/占、、、°。

8.试编写算法，对一棵以孩子-兄弟链表表示的树统计叶子的个数。假设一棵二叉树

的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJKo请画出该树。

习题7图

一、基本内容

图的定义和术语；图的存储结构：数组表示法和邻接表；图的两种遍历策略：深

度优先搜索和广度优先搜索；图的连通性：连通分量和最小生成树；拓扑排序和关键

路径；两类求最短路径问题的解法。二、学习要点

1.熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储

结构和算法有密切联系。

2.熟练掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度优先搜索的递归形式

和广度优先搜索的算法。在学习中应注意图的遍历算法与树的遍历算法之间的类似和

差异。树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先搜索策

略。

3.应用图的遍历算法求解各种简单路径问题，理解各种算法。

7.1单项选择题

1.在一个图中，所有顶点的度数之和等于所有边数的一倍。

A.1/2B.1|C.2|D.4

2.任何一个无向连通图的最小生成树o

A.只有一棵R.有一棵或多棚C.一定有多棵D.可能不存在

3.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。

A.1/2|B.1|C.2D.4

4.一个有n个顶点的无向图最多有条边。

A.nB.n(n-l)C.n(n-l)/2D.2n

5.具有4个顶点的无向完全图有一条边。

A.6|B.12C.16D.20

6.具有6个顶点的无向图至少应有一条边才能确保是一个连通图。

A.5|B.6C.7D.8

7.在一个具有n个顶点的无向图中，要连通全部顶点至少需要一条边。

A.nB.n+1C.n-1D.n/2

8.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是—o

A.nB.(n-1)2C.n-1|D.M

9.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小

为一①_;所有邻接表中的接点总数是一②―o

①A.nB.n+1C.n-1D.n+e

②A.e/2B.eC.2eD.n+e

10.已知一个图如图7.1所示，若从顶点a出发按深度搜索法进行遍历，则可能得到

的一种顶点序列为—①按宽度搜索法进行遍历，则可能得到的一种顶点序列为—

②_。

①A.a,b,e,c,d,fB.e,c,f,e,b,dC.a,e,b,c,f,d|D.|

a,e,d,f,c,b

②A.a,b,c,e,d,fB.a,b,c,e,f,dC.a,e,b,c,f,dD.

a,c,f,d,e,b

图7.1一个无向图

11.已知一有向图的邻接表存储结构如图7.2所示。

13---------2|八

2A

34日-5|A-

4A

5-2——-4|A

图7.2一个有向图的邻接表存储结构

⑴根据有向图的深度优先遍历算法，从顶点V1出发，所得到的顶点序列是

A.vl,v2,v3,v5,v4B.vl,v2,v3,v4,v5

C.vl,v3,v4,v5,v2D.vl,v4,v3,v5,v2

⑵根据有向图的宽度优先遍历算法，从顶点vl出发，所得到的顶点序列是

A.vl,v2,v3,v4,v5B.vl,v3,v2,v4,v5

C.vl,v2,v3,v5,v4D.vl,v4,v3,v5,v2

12.采用邻接表存储的图的深度优先遍历算法类似于二叉树的o

A.先序遍历B.中序遍历C.后序遍历D.按层遍历

13.采用邻接表存储的图的宽度优先遍历算法类似于二叉树的

A.先序遍历B,中序遍历C.后序遍历D.按层遍历

14.关键路径是事件结点网络中―

A.从源点到汇点的最长路径B.从源点到汇点的最短路径

C.最长的回路D,最短的回路

15.下面不正确的说法是o

(1)在AOE网中，减小一个关键活动上的权值后，整个工期也就相应减小;

(2)AOE网工程工期为关键活动上的权之和；

(3)在关键路径上的活动都是关键活动，而关键活动也必在关键路径上。

A.⑴|B,(2)C.(3)D.(1)、(2)

16.在图7.3所示的拓朴排列的结果序列为。

A.125634IB.5162341C.123456D.521634

17.一个有n个顶点的无向连通图，它所包含的连通分量个数为—o

A.0B.1C.nD.n+1

18.对于一个有向图，若一个顶点的入度为kl,、出度为k2,则对应邻接表中该顶点

单链表中的结点数为—。

A.klk2|C.kl-k2D.kl+k2

19.对于一个有向图，若一个顶点的入度为kl,、出度为k2,则对应逆邻接表中该顶

点单链表中的结点数为—o

|A.kl|B.k2C.kl-k2D.kl+k2

7.2填空题(将正确的答案填在相应饿空中)

1.n个顶点的连通图至少上L条边。

2.在无权图G的邻接矩阵A中，若(vi,vj)或Vvi,vj＞属于图G的边集合，则对应元

素等于」否则等于0。

3.在无向图G的邻接矩阵A中，若等于L则A[j][i]等于1。

4.已知图G的邻接表如图7.4所示，其从顶点vl出发的深度有限搜索序列为_

vl,v2,v3,v6,v5,v4,其从顶点vl出发的宽度优先搜索序列为vl,v2,v5,v4,v3,

v6

图7.4图G的邻接表

5.已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是求矩阵第i列

非零元素之和。

6.已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是将矩阵第

i行全部置为零。

7.遍历图的过程实质上是对每个顶点查找其邻接点的过程;oBFS遍历图的时间复

杂度为0(e)(e为图中的边数),DFS遍历图的时间复杂度为0(e)；,两者不同之

处在于遍历图的顺序不同，反映在数据结构上的差别是DFS采用栈存储访问过的结

点，BFS采用队列存储访问过的结点。

8.一个图的邻接矩阵表示法是唯一的,而邻接表表示法是不唯一的。

9.有向图中的结点前驱后继关系的特征是一个结点可能有若干个前驱，也可能有若

干个后继。

10.若无向图G