数据结构马世霞习题答案2020版

1.6习题

一、名词解释

1.数据结构：相互之间存在一种或多种特定关系的数据元素的集合。

结构，就是数据之间的关系，即数据与数据之间的排列方式。

2.数据元素：是有一定意义数据的基本单位，可由若干个数据项组成，在计算机中通

常作为整体处理，也可称为结点、记录。

如：在人类社会中，一个“人”是一个数据元素，是有一定意义的作为整体处理的基本

单位，在社会关系里，一般都是拿某个人说事儿，不会拿某个人的胳膊或腿儿说事儿；

但在医学结构上，人又由若干部分组成，比如四肢、心、肝、脾、肺、肾等。

3.数据项：是具有独立含义的最小标识单位。如一个“人”有眼睛、耳朵、手等数据

项，也可有姓名、年龄、性别等这些数据项。一个记录可称为一个数据元素，而这个元素中

的某一字段就是一个数据项。

4.逻辑结构有时也称数据结构，它是数据元素之间关系的描述，可以看作是从具体问

题抽象出来的数学模型，与数据的存储无关，是独立于计算机的。

5.物理结构是数据的逻辑结构在计算机中的表示和实现，也称存储结构。

6.时间复杂度：当问题规模很大时，程序执行时间随问题规模增长程度的一个度

量。

7.空间复杂度：是指程序运行从开始到结束所需的存储量。

二、判断题

（1）数据元素是最小的项。（X）

（2）算法就是程序。（X）

（算法是解决问题的有限指令序列，它可以用某个具体的程序来表示，也可以用自然

语言、流程图、伪代码表示。

即可以用程序来表达算法，但算法不见得就是程序。

目前，用来表达算法用得最多的是伪代码，因为伪代码比具体的程序要求宽松、易理

解，同时又比自然语言更容易转换成可实现的程序。）

（3）数据结构是数据对象与对象中数据元素之间关系的集合。（V）

（4）从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构。（J）

(5)数据的逻辑结构与数据元素本身的内容和形式无关。(。)

三、填空题

(1)算法的一个特性是确定性,即针对一组确定的输入，算法应始终得出一组确定的

结果。

(2)算法的一个特性是有穷性,即算法必须执行有限步就结束。

(3)数据是信息的载体,它能够被计算机程序识别、存储和加工处理。

(4)此题不严谨。

数据结构是带结构的数据元素的集合，因此，可以说数据结构由“数据”和“结

构”两个元素组成;

另外，一般讨论一个具体的数据结构时，我们会讨论它的逻辑数据、物理结构和

数据的运算三个方面。

(就像“土豆炒牛肉”由土豆和牛肉两样主菜组成，当我们讨论这个菜品时，会讨论它

的色、香、味三个方面。)

(5)数据结构的逻辑结构包括线性结构和非线性结构结构两大类。

四、简答题

1.数据结构中数据元素之间的逻辑关系可以由四种基本数据关系组成，简述它们的名

称与含义。

答：

(1)集合结构：在集合结构中，数据元素间的关系是“属于同一个集合”。集合是元素

关系极为松散的一种结构。

(2)线性结构：该结构的数据元素之间存在着“一对一”的关系。

(3)树型结构：该结构的数据元素之间存在着“一对多”的关系。

(4)图形结构：该结构的数据元素之间存在着“多对多”的关系。

2.简述算法的特性。

答：

(1)有穷性。一个算法必须在有穷步之后结束，即必须在人类现有的寿命长度下、有

现实意义的有限时间内完成。如你编写算法，计算机需要30年的时间才能结束，算法的意

义就不大。

(2)确定性。算法的每一步必须有确切的定义，无二义性。相同的输入仅有唯一的输

出结果。(比如:"小明对小强说他的爸爸去出差了”就是一个歧义句。)

(3)可行性。算法中的每一步都可实现，即每一步都在当前环境条件下可以通过有限

次运算实现。

(4)输入。一个算法具有零个或多个输入，可以没有输入。

(5)输出。一个算法具有一个或多个输出，至少有一个输出。(没有输出对我们人类

就没有反馈,那么这个算法就没有意义。)

3.设计一个好的算法通常要考虑哪些要求？

要设计一个好的算法通常要考虑以下的要求。

(1)正确性。算法的执行结果应当满足预先规定的功能和性能要求。

“正确性”的含义是所设计的程序没有语法错误，对于刁难性的数据也能够得到满足

要求的输出结果。

(2)可读性。一个算法应当思路清晰、层次分明、简单明了、易读易懂。

一个好的算法首先应该是便于交流，其次才是机器可执行，可读性好的算法有助于编

程人员对算法的理解，而难懂的算法对于隐藏的错误不易调试和修改。

(3)健壮性(鲁棒性)。当输入不合法数据时，应能作适当处理，不至引起严重后

果，陷入死机。

(4)高效率和低存储量。有效使用存储空间和有较高的时间效率。

4.常用算法大致可以分为几大类？

答：常用的算法大致可以被分为蛮力算法、分治算法、减治算法、变治算法以及动态规

划算法等几大类。

五、观察下列算法回答以下问题。

(1)每一个算法的意图是什么？

(2)每一个算法的关键步骤是什么？

(3)每一个算法的关键步骤执行了多少步？

(4)算法的时间复杂度是什么？

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

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

a++;

答：

算法意图：变量a自增n?次；

算法的关键步骤：a++;

关键步骤执行次数：胡次；

算法的时间复杂度：T(n)=0(n2)

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

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

x++;

答：

算法意图：什么也不做；

算法的关键步骤：X++;

关键步骤执行次数：0次；

算法的时间复杂度：T(n)=0(1)

分析：

虽然看起来是双层循环，但第二次循环for(j=i;j〈i;j++)的循环体因为不满足j〈i

的条件而不执行；所以事实上第一层循环的任何一次执行，都是什么也不做。

无论问题规模n为多少，关键步骤“x++;”的执行次数都为0次。常量阶的时间复杂

度记为T(n)=0(1)»

③i=l;

答：

算法意图：将i的值赋值为1;

算法的关键步骤：i=l；

关键步骤执行次数：1次；

算法的时间复杂度：T(n)=O(1)

第2章

1.名词解释

(1)线性表

具有相同数据类型的n(n>=0)个数据元素的有限序列，排列方式为“一个接一个的排

列”。通常记为：

(ai,32,ai-i,a,,8i+i,"an)

其中，n为表长，n=0时称为空表。

(2)顺序表

用顺序存储方式存放的线性表叫顺序表，顺序存储是指在内存中用地址连续的一块

存储空间顺序存放线性表的各元素。

特点：①用物理上的相邻实现数据元素逻辑关系上的相邻;②可实现随机存取。

(3)线性单链表

用链式存储方式存放的线性表叫链表。

链表是通过一组任意的存储单元来存储线性表中的数据元素，对每个数据元素a”除了

存放数据元素的自身的信息a之外，还需要存放其后继ai+i所在的存贮单元的地址，这两

部分信息组成一个“结点”，存放数据元素信息的称为数据域data,存放其后继地址的称为

指针域nexto因此n个元素的线性表通过每个结点的指针域联成了一个“链子”，称之为

链表。其中：

线性、单向链结构的叫线性单链表；

线性、双向链结构的叫线性双向链表；

环形、单向链结构的叫单循环链表；

环形、双向链结构的叫双循环链表。

(4)单循环链表

在单链表的基础上，链表最后一个结点的指针域不为空，而是指向第一个结点，使得链

表头尾结点相连，整个链表形成一个环。

单循环链表特点：从表中任何一个结点出发均可找到其它结点。

(单链表特点：要找链表中任何一个结点，必须从头结点开始遍历该结点以前的整个链

表。)

2.判断题(在各题后填写“4”或“X”)

(1)线性表若采用链式存储表示时所有存储结点之间的地址可连续可不连续(4)

(2)链式存储在插入和删除时需要保持数据元素原来的物理顺序，不需要保持原来的逻

辑顺序。(X)

(3)链表中每个结点都是两个域。(X)

解析：单链表中每个结点都是两个域，双链表不是两个域。

(4)在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。(X)

(5)顺序表可以按下标随机(或直接)访问，顺序表还可以从某一指定元素开始，向前

或向后逐个元素顺序访问。(4)

3.填空题

(1)线性表的顺序存储结构是一种随机存取的存储结构：线性表的链式存储结

构是一种循序访问的存储结构，即要访问线性表中的任一元素，必须“顺藤摸瓜”先逐个

遍历该元素之前的所有元素。

(“随机存取”，有时亦称直接访问，指的是当存储器中的消息被读取或写入时，所需要

的时间与这段信息所在的位置无关。)

(2)线性表采用顺序存储结构时,其存储地址通常必须是连续的，采用链式存储

结构时，其存储地址连续与否均可以。

(3)已知顺序表长度为n(元素序号为0〜n-l),在i位置(lWi/n+l)插入一个元素

需要移动正1个元素，把i位置(iWiWn)的元素删除需要移动上j个元素。

4.含有n个结点的线性单链表中，在指针p所指结点后插入一个新结点的时间复杂度为

0(1)，在指针p所指结点前插入一个新结点的时间复杂度为0(n)。

(因为在单链表中，任何一个结点含后继指针，但不含前驱指针，所以在p所指结点后

插入一个新结点，需要从第一个结点开始逐一访问。)

5.含有n个结点的线性单链表中，在给定值为d的结点后插入一个新结点的时间复杂度

为QS上，在给定值为d的结点前插入一个新结点的时间复杂度为Qin)o

6.含有n个结点的双向链表中，在指针p所指结点后插入一个新结点的时间复杂度为

0(1),在指针p所指结点前插入一个新结点的时间复杂度为QLL。

7.在具有n个结点的按结点数据有序的线性单链表中插入一个新结点并使链表依然有

序的操作的时间复杂度是皿I。

四、选择题

(1)设单链表中结点的结构为(data,next)。若想摘除结点*p(*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;

(2)在一个长度为n的顺序表中向第i个元素位置插入一个新元素时，

需要从后向前依次后移个元素。

A.n-i

B.n-i+1

C.n-i-1

D.i

(3)设单链表中结点的结构为(data,next)»已知指针q所指结点是指针p所指结点的直

接前驱，若在*q与*p之间插入结点*s,则应执行下列哪一个操作？

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

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

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

D.p->next=s;s->next=q;

(4)在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为。

A.O(n)

B.O(l)

C.O(n2)

DO(log2n)

(5)设双向循环链表中结点的结构为(data,prior,next),且不带表头结点。若想在指针p

所指结点之后插入指针s所指结点，则应执行下列哪一个操作？

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

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

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

D.s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;

五、简答题

简述顺序表与链表的优缺点。

是否是否

存储密度存取效率增删效率

需预先分配需连续存储空间

顺序表高需要需要高低

链表低不需要不需要低高

顺序表的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期

间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均

需要移动一半（或近一半）元素，修改效率不高。

链式存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器

中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来

的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指

针，修改效率较高。但存取表中的数据元素时，只能循序访问，因此存取效率不高。

循序访问，“顺藤摸瓜”逐个按序访问«

六、编程

有顺序表A和B,其元素均按从小到大的升序排列，编写一个算法将它们合并成一个

顺序表C,要求C的元素也是从小到大的升序排列。如：

已知：A={5,8,9,12,16},B={1,3,5,7}求：己{1,3,5,5,7,8,9,12,16}

提示：(1)依次扫描通过A和B的元素，比较当前的元素的值，将较小值的元素赋

给C,如此直到一个线性表扫描完毕；

(2)将未完的那个顺序表中余下部分赋给C即可。C的容量要能够容纳A、B两个线

性表相加的长度。

程序“24.c”如下：

#include<stdio.h>

#defineMaxSize50

typedefintDataType;

typedefstruct

(

DataTypedata[MaxSize];

intlast;/*线性表的最后一个元素last*/

}Lnode,*List;

voidMerge_List(LnodeA,LnodeB,Lnode*C)/*合并C=A+B*/

{

inti,j,k；

i=l;j=l;k=l;

while(i<=A.last&&j<=B.last)

if(A.data[i]<=B.data[j])

(

C->data[k]=A.data[i];

k-H-;

i++；

}

else

C->data[k]=B.datafj];

k++；j++；

while(i<=A.last)

{

C->data[k]=A.data[i];

k++;

i++;

}

while(j<=B.last)

{C->data[k]=B.data[j];

k++；jf}

C->last=k-1;

)

main()

{LnodeA,B,C;

inti,k,m;

printff请输入A顺序表元素，元素为整型量，用空格分开，-1为结束标志：”)；

A.last=0;i=0;scanf(n%dn,&i);

while(i!=-1){/*输入A顺序表元素，建立有序表*/

k=A.last;

while((k>=l)&&(i<A.data[k]))

k・・；

fbr(m=A.last;m>=k+1;m-)

A.data[m+1]=A.data[m];

A.datafk+1]=i;A.last-H-；

scanff%d”,&i);}

printf(〃\n\n请输入B顺序表元素，元素为整型，-1为结束标志：”)；

B.last=0;i=0;scanf(M%dn,&i);

while(i!=-l){/*输入B顺序表元素，建立有序表*/

k=B.last;

while((k>=l)&&(i<B.data[k]))

for(m=B.last;m>=k+1;m-)B.data[m+1]=B.data[m];

B.data[k+1]=i;B.last-H-;

scanf(M%dn,&i);}

printf(〃\nA有序表元素列表：”);

for(i=l;i<=A.last;i++)

prmtf(M%d",A.data[i]);

printf(M\nn);

printf(”\nB有序表元素列表：”)；

for(i=1;i<=B.last;i++)

printff%dn,B.data[i]);

printff\n”)；

MergeList(A,B,&C);

printf(”\n合并后C有序表元素列表:\n“);

for(i=l;i<=C.last;i++)

printff'%dn,C.data[i]);

printff'n”)；

}

算法的时间性能是O(m+n),其中1n是A表长，n是B表长。运行结果如图2-23所

6"D八数据结构源代码\2_4\Debug\2_4-exe”

请输入A顺序表

请输入B顺序表元素，元素为整型，T■为结束标志：1357T

。有序表元素列表：5891216

B有序表元素列表：135?

合并后C有序表元素列表：

图2-23两个有序表合并运行结果

3.5习题

一、名词解释

(1)栈

栈是限制在表的一端进行插入和删除操作的线性表。

允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。

栈的顺序结构：利用顺序存储方式实现的栈称为顺序栈。

栈的链式结构：用链式存储结构实现的栈称为链栈。

(2)队

队是一种“先进先出”(FIFO--FirstInFirstOut)的数据结构，即插入操作在表一端进行,

而删除操作在表的另一端进行，这种数据结构称为队列。

把允许插入的一端称为队尾(rear),把允许删除的一端称为队头(front)。

队的顺序结构：顺序存储的队称为顺序队。

队的链式结构：采用链式存储结构的队称为链队。

二、判断题

(1)栈和队列都是特殊的线性表。(V)

(2)栈和队列都将插入和删除操作限制在表的端点处进行。(V)

(3)只允许在表的一端进行插入和删除操作的线性表称为栈。(V)

(4)没有元素的栈称为空栈，空栈用不着栈顶指针。(x)

(5)只要栈不空，就能任意删除栈的元素。(x)

(6)栈允许删除的一端称为栈顶，而栈底元素是不能删除的。(x)

(7)对采用链式存储结构的栈进行操作不必判断溢出。(V)

(8)元素进出队列一定满足“先进先出”的规律。(V)

(9)链队列不存在溢出问题。(V)

(10)在链队列中删除一个元素是在链表的最前端进行的。(V)

三、单项选择题

(1)栈和队列的共同之处在于它们具有相同的(A)。

A.逻辑特性B.物理特性C.运算方法D.元素类型

(2)栈和队列都是特殊的线性表，其特殊性在于(C)。

A.它们具有一般线性表所没有的逻辑特性

B.它们的存储结构比较特殊

C.对它们的使用方法做了限制

D.它们比一般线性表更简单

(3)若5个元素的出栈序列为1,2,3,4,5,则进栈序列可能是()0

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

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

(4)某队列初始为空，若它的输入序列为a,b,c,d,它的输出序列应为()。

A.a,b,c,dB.d,c,b,a

C.a,c,b,dD.d,a,c,b

(5)当3个元素的进栈序列给定以后，由这3个元素组成的可能的出栈序列应该有

()。

A.5种B.6种C.4种D.3种

(6)若栈采用顺序存储结构，正常情况下，往堆栈中插入一个元素，栈顶指针top的

变化是()o

A.不变B.top=0C.--topD.top++

(7)若栈采用顺序存储结构，正常情况下，删除栈中一个元素，栈顶指针top的变

化是()。

A.不变B.top=0C.top--D.top++

(8)若队列采用顺序存储结构，元素的排列顺序(B)。

A.与元素的值的大小有关

B.由元素进入队列的先后顺序决定

C.与队头指针和队尾指针的取值有关

n与作为顺序存储结构的数组的大小有关

(9)若非空栈采用含头结点的链式存储结构，栈顶指针为top,删除堆栈的一个元素

的过程是依次执行：p=top,(B),free(p)0

A.top=p->nextB.top->next=p->next

C.p=topD.p=p->next

(10)若队列采用链式存储结构,队头元素指针与队尾元素指针分别为front和rear,

向队列中插入一个由P所指的新结点的过程是依次执行：()，rear二p。

A.rear=pB.front二p

C.rear->next=pD.front->next=p

(11)若非空队列采用链式存储结构，队头元素指针与队尾元素指针分别为front和rear,

删除队列的一•1■元素的过程是依次执行：p=front,(),free(p)0

A.rear=pB.rear=p->next

C.rear=p->nextD.front=p->next

(12)在循环队列中，若front与rear分别表示队头元素和队尾元素的位置，则判断循

环队列队空的条件是(C)。

A.front=rear+lB.rear=front+l

C.front==rearD.rear=front-l

四、填空题

(1)栈和队列的逻辑结构都是线性一结构。

(2)栈的插入和删除操作都是在栈顶一进行,而队列的插入操作在.队尾.进行,删除

操作在一队头_进行。

(3)对某栈执行删除操作时，只有在一栈中只有一个元素的一情况下,才会将栈底元素

删除。

(4)在具体的程序设计过程中，栈的顺序存储结构一般是利用一个数组一描述的,同

时还要定义一个整型变量来一给出栈顶元素的位置―。

(5)若栈采用顺序存储结构，在不产生溢出的情况下往栈中插入一个新元素，

首先一将栈顶指针后移一个位置一，然后将被插入元素放在修改后的栈顶指针所指出的位

(6)若队列采用顺序存储结构，未溢出时插入一个元素首先将队尾指针后移一个位

置一然后再一将被插入元素放在修改后的队尾指针所指出的位置―。

(7)当栈的最大长度难以估计时，最好采用一链式一存储结构。

五、综合应用题

(1)已知栈采用链式存储结构，初始时为空，请画出a,b,c,d四个元素依次进栈以

后该栈的状态，然后再画出此时的那个栈顶元素出栈后栈的状态。

(2)若按从左到右的顺序依次读人已知序列{a,b,c,d,e,f,g}中的元素，然后结

合栈操作，能得到下列序列中的哪些序列(每个元素进栈一次，下列序列表示出栈的次序)？

A.{d,e,c,f,b,g,a}B.{f,e,g,d,a,c,b}

C.{e,f,d,g,b,c,a}D.{c,d,b,e,f,a,g)

答：A、D满足出栈序列。满足A出栈次序的具体操作序列为：

a,bed进栈，然后d出栈；

然后e进栈，接着e出栈；

然后c出栈；

然后f进栈，接着f出栈；

然后b出栈；

然后g进栈，接着g出栈

最后a出栈。

出栈序列：d,e,c,f,b,g,a,所以A满足出栈序列。

满足D出栈次序的具体操作序列请同学们自行写出。

4.7习题

一、选择

(1)串是()»

A不少于一个字母和序列B任意个字母的序列

C不少于一个字符的序列D有限个字符的序列

(2)串的长度是()o

A串中不同字母的个数B串中不同字符的个数

C串中所含字符的个数，且大于0D串中所含字符的个数

(3)设串sl='abedefg',s2=*pqrst,函数CON(X,Y)返回X和串的连接串，SUB

(S,I,J)返回串S的从序号I的字符开始的J个字符组成的子串，LEN(S)返回串S的长

度，则CON(SUB(si,2,LEN(s2)),SUB(sl,LEN(s2),2))的结果串是()。

AbcdefBbcdefgCbcpqrstDbcdefef

注释：CON(SUB(si,2,LEN(s2)),SUB(sl,LEN(s2),2))

=CON(SUB(si,2,5),SUB(sl,5,2))

=CON(bcdef,ef)

二bcdefef

(4)数组A[l：5H1：6]的每个元素占5个单元，将其按行优先次序存储在起始起址

为1000的连续的内存单元中，则元素A[5,5]的地址为(A)。

A1140B1145C1120D1125

注释：该数组为5行6列，

按照公式：Loc[i,j]=Loc[l,1]+(nX(i-l)+j-l)Xsize,

其中m=5,n=6,size=5,

那么Loc[5,5>Loc[l,1]+(6X(5-1)+5-1)X5=1140

(5)对矩阵压缩存储是为了()。

A方便运算B节省空间C方便存储D提高运算速度

(6)数组通常具有的两种基本操作是()。

A插入与删除B索引和修改

C查找和修改D查找与删除

注释：数组，连续存储，不适合经常插入和删除；适合经常查找和修改(定位后修

改某单元内的值，单元个数和单元之间的逻辑顺序不做修改。)

(7)二维数组M[i,j]的行下标i的范围从0到4,列下标j的范围从0到5,M按行

存储时元素\1[3,5]的起始地址与M按列存储时元素()的起始地址相同。

Am[2,4]BM[3,4]CM[3,5]DM[4,4]

注释：按行存储时，M[3,5]是第24个元素(前3行是3X6个，第4行是6个)

按列存储时，M[3,4]是第24个元素(前4列是4X5个，第5列是4个)

(8)稀疏矩阵一般的压缩存储方法有两种，即()•

A二维数组和三组数组B三元组表和散列

C三元组表和十字链表D散列和十字链表

(9)设有上三角矩阵a(1:5,1:5),现将其上三角中的元素按列优先顺序存放在一维数

组b(l:15)中。已知b［l］的地址为100,每个元素占用2个存储单元，则a［3,4］的地址为

(A)o

A116B118C120D122

第79页公式，其中i=3,j=4.

上三角矩阵Loc[i,j]=Loc[1,1]+j(j-l)/2+i-l

=Loc[1,1]+8个元素所占的存储单元个数

=100+16

=116

二、判断题

(1)串长度是指串中不同字符的个数。(X)

［注］串长度：串中所包含的字符个数，无论是相同字符还是不同字符。

(2)串是n个字母的有限序列(n>0)。(X)

［注］是字符，不是字母

(3)如果两个串含有相同的字符，则说它们相等。(X)

［注］长度相等且对应位置的字符都相等。

(4)空串与空格串是相同的。(X)

(5)对矩阵压缩存储的方法只能用三元组表存储矩阵元素。(X)

［注］还有行逻辑链接的顺序表和十字链表。

三、填空题

(1)串值的两种最基本的存储方式是顺序存储方式和链接存储方式。

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

(3)空串的长度等于❷。

(4)空格串是空格组成的非空串，其长度等于串中空格字符的个数。

(5)设s='Iamateacher',其长度是14。

(6)设sl=，good,,s2=，',s3-bye!,,则si,s2和s3连接后的结果

是goodbye!

(7)对矩阵采用压缩存储是为了节省存储空间。

(8)设N行N列的下三角矩阵A己压缩到一维数组S(1：N(N+1)/2)中，若按行

序为主存储，则A[LJ1对应的S中的存储位置是一i(i-D/2+jT。

四、程序填空：

(1)采用顺序存储结构编写算法：将串r中所有值为chi的字符换成ch2。

#defineMaxSize100

typedefstruct

{charstr[MaxSize];

intlen;

}strtype;

Strtype*trans(r,chl,ch2)

Strtype*r;

charch1,ch2;

inti;

for(i=0;i<r->len;i++)

if(r->str[i]==chl)

r->str[i]=ch2；

return(r);

(2)执行下列函数会产生什么的结果？

Voiddemonstrate()

{StrAssign(s,"thisisabook");//s=uthisisabook”

StrReplace(s,SubString(s,3,7),44eseare");//s=4tthesearebook''

StrAssign(t,StrCat(s,us"));//t=s=44thesearebooks^^

StrAssign(u,"xyxyxyxyxyxy");//u=xyxyxyxyxyxy

StrAssign(v,SubString(u,6,3))；//v=yxy

StrAssign(w,"W”)；〃w=W

printf("t=”,t,“v=",v,‘'u='',StrReplace(u,v,w));

输出:

t=thesearebooks

v=yxy

u=xWxWxW

五、算法设计：

1采用顺序存储结构编写算法：

(1)将串r中删除其值等于ch的所有字符。

(2)将串r中所有字符按照相反的次序仍存放在r中。

(3)将串rl中第index个字符起求出首次与串r2相同的子串的起始位置。

(4)从串r中删除所有与r3相同的子串。

2编写链式存储结构下删除串S从位置i开始长度为k的子串的算法。

L串的算法设计1

分别在顺序存储和一般链接存储两种方式下用C语言写出实现把串si复制到串S2的串复

制函数strcpy(sl,s2)。

2.串的算法设计2

在一般链接存储(一个结点存放一个字符)方式下，写出采用简单算法实现串的模式匹配的C

语言函数intL_index(t,p)»

串的算法设计1

分别在顺序存储和一般链接存储两种方式下，用C语言写出实现把串si复制到串s2的串复

制函数strcpy(sl,s2)o

顺序存储：

#include"string.h"

#defineMAXN100

chars[MAXN];

intS_strlen(chars[])

(

inti;

for(i=0;s[i]!=W;i++);

return(i);

voidS_strcpy(charsl[],chars2[])//

(

inti;

for(i=0;sl[i]!=W;i4-+)

s2[i]=sl[i];

s2[i]=,\0';

)

一般链接存储：

#include"stdio.h"

typedefstructnode

(

chardata;

structnode*link;

}NODE;

NODE*L_strcpy(NODE*sl)

(

NODE*s2,*tl,*t2,*s;

if(sl==NULL)return(NULL);

else

(

tl=sl;

t2=(NODE*)malloc(sizeof(NODE));

s2=t2;

while(tl!=NULL)

(

s=(NODE*)malloc(sizeof(NODE));

s->data=tI->data;

t2->link=s;

t2=s;

tl=tl->link;

)

t2->link=NULL;

s=s2;

s2=s2->link;

free(s);

return(s2);

串的算法设计2

在一般链接存储(一个结点存放一个字符)方式下，写出采用简单算法实现串的模式匹配的C

语言函数intL_index(t,p)o

#include"stdio.h"

typedefstructnode

(

chardata;

structnode*link;

}NODE;

intL_index(NODE*t,NODE*p)

(

NODE*tl,*pl,*t2;

inti;

tl=t;i=l;

while(tl!=NULL)

(

pl=p;

t2=tl->link;

while(p1->data==t1->data&&p1!=NULL)

pl=pl->link;

tl=tl->link;

}

if(pl==NULL)return(i);

i++；

tl=t2;

)

return(O);

第5章习题答案

一、选择

1.以下说法错误的是（）

A.树形结构的特点是一个结点可以有多个直接前趋

B.线性结构中的一个结点至多只有一个直接后继

C.树形结构可以表达（组织）更复杂的数据

D.树（及一切树形结构）是一种“分支层次”结构

2.以下说法错误的是（BC）

A.二叉树可以是空集

B.二叉树的任一结点都直两棵子树（是“最多有”两棵子树）

C.二叉树与树具有相同的树形结构（二叉树的孩子必有左右之分，只有一个孩子时也要分

出左右，而树即使是有序树，只有一个孩子时部分左右）

D.二叉树中任一结点的两棵子树有次序之分

3、以下说法错误的是（）

A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达

B.在三叉链表上，二叉树的求双亲运算很容易实现

C.在二叉链表上，求根，求左、右孩子等很容易实现

D.在二叉链表上，求双亲运算的时间性能很好

4、以下说法错误的是（）

A.一般在哈夫曼树中，权值越大的叶子离根结点越近

B.哈夫曼树中没有度数为1的分支结点

C.若初始森林中共有n裸二叉树，最终求得的哈夫曼树共有2n-l个结点

D.若初始森林中共有n裸二叉树，进行2n-l次合并后才能剩下一棵最终的哈夫树

5.深度为6的二叉树最多有（）个结点（）

A.64B.63C.32D.31

6.将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从

左到右的顺序对结点编号，那么编号为41的双结点编号为（）

A.42B.40C.21D.20

7.设二叉树有n个结点，则其深度为（）

A.n-1B.nC.5floor（log2n）D.无法确定

注：完全二叉树才能确定其深度。

8.设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总

数最少（）个

A.k+1B.2kC.2k-1D.2k+1

注：单支数含结点个数最少，但题目规定该二叉树中不存在度为1的结点。所以，在

单支树的基础上把结点补齐，使之度数为2或0,结果就是有2k-l个结点。

9.下列说法中正确的是（）

A.任何一棵二叉树中至少有一个结点的度为2

B.任何一棵二叉树中每个结点的度都为2

C.任何一棵二叉树中的度肯定等于2

D.任何一棵二叉树中的度可以小于2

10.对含有（）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列

均相同。

A.0B.lC.2D.不存在这样的二叉树

11.已知某二叉树的后续遍历序列是dabec,中序遍历序列是deabc,它的先序遍历序列是

（）

A.acbedB.deabcC.decabD.cedba

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

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

A.bdgcefhaB.gdbecfhaC.D.bdgechfaD.gdbehfca

分析：先序遍历序列的第一个字符为根结点。时于中序遍历，根结点在中序遍历序列的中间，左边部分

是根结点的左子树的中序遍历序列，右边部分是根结点的右子树的中序遍历序列。

先序：abdgcefh->abdgcefh

中序।dgbaechf->dgbaechf

得出结论：a是树根，a有左子树和右子树，左子树有bdg结点，右子树有cefh结点.

先序：bdg->bdg

中序：dgb->dgb

得出结论：b是左子树的根结点，b无右子树，有左子树.

先序：dg->dg

中序：dg->dg

得出结论：d是b的左子树的根结点，d无左子树，有右子树.

先序：cefh->cefh

中序：echf->echf

得出结论：c是右子树的根结点，c有左子树（只有巳结点），有右子树（有fh结点）.

先序：fh—>fh

中序：hf->hf

得出结论：f是c的左子树的根结点，用左子树（只有h结点），无右子树。

还原二叉树为：

a

bc

def

gh

后序遍历序列：gdbehfca

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

（）

A.正确B.错误

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

（）

A.正确B.错误

15.二叉树是每个结点的度不超过2的有序树的特殊情况，这种说法)

A.正确B.错误

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

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

二、填空

1.树(及一切树形结构)是一种一1次_结构。在树上，结点没有直接前趋。对

树上任一结点X来说，X是它的任一干树的根结点惟一的一双亲.。

2.一棵树上的任何结点(不包括根本身)称为根的子孙。若B是A的子孙，则

称A是B的祖先

3.一般的，二叉树有一空—二叉树、一只有超—的二叉树、只有_左子树的二叉树、

只有一右子树____的二叉树、同时有左子树、右玉树—的二叉树五种基本形态。

4.二叉树第i(i>=l)层上至多有"一个结点。

5.深度为k(k>=l)的二叉树至多有上虫个结点。

6.对任何二叉树，若度为2的节点数为止，则叶子数n产.1+L。

7.满二叉树上各层的结点数已达到了二叉树可以容纳的_极限一。满二叉树也是一完全二

叉树，但反之不然。

8.具有n个结点的完全二叉树的深度为口哂」+

如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(l<=i<=n)的结点X

有：

9,若i=l,则结点X是一根结点；；若i>L则X的双亲结点的编号为一返

10.二叉树通常有酶_存储结构和暹式一存储结构两类存储结构。

11.每个二叉链表的访问只能从_握_结点的指针，该指针具有标识二叉链表的作用。

12.对二叉链表的访问只能从_根_指针开始,若二叉树为空，则一根指针__=NULL.

13.二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是_至—的

指针，或者是.左孩子或右孩子指针一

14.具有n个结点的二叉树中,一共有个指针域，其中只有_m』一个用来指向结点

的左右孩子，其余的.n+1个指针域为NULLo

15.二叉树有不同的链式存储结构，其中最常用的是_二叉链表—与一三叉链表一。

16.在先序一遍历二叉树的序列中,任何结点的子树上的所有结点，都是直接跟在该

结点之后。

17.哈夫曼树是带权路径度一最小一的树,通常权值较大的结点离根一越近一。

18.有m个叶子结点的哈夫曼树，其结点总数为2m-L。

19.任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结

点为n-2m+l个。根据P84性质3:n2=n0-l

20.由任何一棵树转换成二叉树时,其根结点的右子树总是空的。

三、简答题

1.简述二叉链表的类型定义。

2.简述三叉链表的类型定义。

3.分别画出含3个结点的树与二叉树的所有不同形态。

提示：含3个结点的树，共有两种形态；

含3个结点的二叉树，共有五种形态

4.已知一棵二叉树的中序遍历根序列和后序遍历序列分别为BDCEAFHG和EDCBHGEA,

试画出这棵二叉树。

5.将下图所示的森林转换成二叉树。

6.给定权值7,18,3,32,5,26,12,8,构造相应的哈夫曼树。

6、