数据结构课后题答案(第4章).

第1章绪论

课后习题讲解

1.填空

⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行

考虑和处理。

【解答】数据元素

⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。

【解答】数据项，数据元素

【分析】数据结构指的是数据元素以及数据元素之间的关系。

）、（）、（）和（）。

⑶ 从逻辑关系上讲，数据结构主要分为

（【解答】集合，线性结构，树结构，图结

构

⑷ 数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的

关系

⑸ 算法具有五个特性，分别是（）、（）、（）、（）、（）。

【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，

可行性

⑹ 算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。

【解答】自然语言，程序设计语言，流程图，伪代码，伪代码

⑺ 在一般情况下，一个算法的时间复杂度是（）的函数。

【解答】问题规模

⑻设待处理问题的规模为 n，若一个算法的时间复杂度为一个常数，则

表示成数量级的形式为（），若

为n*log25n ，则表示成数量级的形式为（）。

【解答】Ο(1) ，Ο(nlog2n)

【分析】用大 O记号表示算法的时间复杂度，需要将低次幂去掉，将

最高次幂的系数去掉。

2.选择题

⑴ 顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关

系是由（）表示的。

A 线性结构

B 非线性结构

C 存储位置

D 指针

【解答】 C，D

【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，

第四章

一、简述下列每对术语的区别：

空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。

答：

●空串是指不包含任何字符的串，它的长度为零。

空白串是指包含一个或多个空格的串，空格也是字符。

●串常量是指在程序中只可引用但不可改变其值的串。

串变量是可以在运行中改变其值的。

●主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。

●静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。

动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。

●目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相对的。

●有效位移和无效位移：在串定位运算中，模式串从目标的首位开始向右位移，每一次合法位移后如果模式串与目标中相应的字符相同，则这次位移就是有效位移(也就是从此位置开始的匹配成功)，反之，若有不相同的字符存在，则此次位移就是无效位移(也就是从此位置开始的匹配失败)。

二、假设有如下的串说明：

char s1[30]="Stocktom,CA", s2[30]="March 5 1999", s3[30], *p;

(1)在执行如下的每个语句后p的值是什么?

p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6');

第3章栈和队列

习题

1．选择题

（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。

A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1

（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。

A．i B．n-i C．n-i+1 D．不确定（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。

A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n （4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。

A．x=top->data;top=top->link； B．top=top->link;x=top->link；

C．x=top;top=top->link； D．x=top->link；

（5）设有一个递归算法如下

int fact(int n) { 线性表的链式存储结构 D. 栈（11）用链接方式存储的队列，在进行删除运算时（）。

A. 仅修改头指针

B. 仅修改尾指针

C. 头、尾指针都要修改

D. 头、尾指针可能都要修改

（12）循环队列存储在数组A[0..m]中，则入队时的操作为（）。

A. rear=rear+1

B. rear=(rear+1)%(m-1)

C. rear=(rear+1)%m

习题四串

一、单项选择题‎

1．下面关于串‎的的叙述中‎，哪一个是不‎正确的？（）

A．串是字符的‎有限序列 B．空串是由空‎格构成的串‎

C．模式匹配是‎串的一种重‎要运算 D．串既可以采‎用顺序存储‎，也可以采用‎链式存储2．串是一种特‎殊的线性表‎，其特殊性体‎现在（）。

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

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

3．串的长度是‎指（）

A．串中所含不‎同字母的个‎数 B．串中所含字‎符的个数

C．串中所含不‎同字符的个‎数 D．串中所含非‎空格字符的‎个数

4．设有两个串‎p和q，其中q是p‎的子串，求q在p中‎首次出现的‎位置的算法‎称为（）A．求子串 B．联接 C．匹配 D．求串长

5．若串S=“softw‎a re”,其子串的个‎数是（）。

A．8 B．37 C．36 D．9

二、填空题

1．含零个字符‎的串称为_‎_____‎串。任何串中所‎含____‎__的个数‎称为该串的‎长度。

2．空格串是指‎__ __，其长度等于‎__ __。

3．当且仅当两‎个串的__‎____相‎等并且各个‎对应位置上‎的字符都_‎_____‎时，这两个串相‎等。一个串中任‎意个连续字‎符组成的序‎列称为该串‎的____‎__串，该串称为它‎所有子串的‎_____‎_串。

4．INDEX‎（‘DATAS‎T RUCT‎U RE’，‘STR’）=_____‎___。

5．模式串P=‘abaab‎c ac’的next‎函数值序列‎为____‎____。

6．下列程序判‎断字符串s‎是否对称，对称则返回‎1，否则返回0‎；如 f("abba")返回1，f("abab")返回0；

第四章串

4.10

void String_Reverse(Stringtype s,Stringtype &r)//求s的逆串r

{

StrAssign(r,''); //初始化r为空串

for(i=Strlen(s);i;i--)

{

StrAssign(c,SubString(s,i,1));

StrAssign(r,Concat(r,c)); //把s的字符从后往前添加到r中

}

}//String_Reverse

4.11

void String_Subtract(Stringtype s,Stringtype t,Stringtype &r)//求所有包含在串s中而t中没有的字符构成的新串r

{

StrAssign(r,'');

for(i=1;i<=Strlen(s);i++)

{

StrAssign(c,SubString(s,i,1));

for(j=1;j<i&&StrCompare(c,SubString(s,j,1));j++); //判断s的当前字符c是否第一次出现if(i==j)

{

for(k=1;k<=Strlen(t)&&StrCompare(c,SubString(t,k,1));k++); //判断当前字符是否包含在t中

if(k>Strlen(t)) StrAssign(r,Concat(r,c));

}

}//for

}//String_Subtract

4.12

int Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T替换为V,并返回置换次数

数据结构(第二版)习题答案第4章

第

4章字符串、数组和特殊矩阵

4.1稀疏矩阵常用的压缩存储方法有（三元组顺序存储）和（十字链表）两种。

4.2设有一个10 × 10的对称矩阵 A采用压缩方式进行存储，存储时以按行优先的顺序存

储其下三角阵，假设其起始元素 a00的地址为 1，每个数据元素占 2个字节，则 a65的地址为

（ 53 ）。

4.3若串S =“software”，其子串的数目为（ 36 ）。

4.4常对数组进行的两种基本操作为（访问数据元素）和（修改数组元素）。

4.5 要计算一个数组所占空间的大小，必须已知（数组各维数）和（每个元素占用的空

间）。

4.6对于半带宽为 b的带状矩阵，它的特点是：对于矩阵元素 aij，若它满足（|i-j|>b），

则 aij = 0。

4.7字符串是一种特殊的线性表，其特殊性体现在（该线性表的元素类型为字符）。

4.8试编写一个函数，实现在顺序存储方式下字符串的 strcompare （S1，S2）运算。

【答】：

#include <stdio.h>

#include <string.h>

#define MAXSIZE 100

typedef struct{

char str[MAXSIZE];

int length;

}seqstring;

/* 函数 strcompare()的功能是：当 s1>s2时返回 1，当 s1==s2时返回 0，当 s1<s2时返回-1*/

int strcompare(seqstring s1,seqstring s2)

数据结构（C语言版）（第2版）

课后习题答案

李冬梅

2015.3

目录

第1章绪论 (1)

第2章线性表 (5)

第3章栈和队列 (13)

第4章串、数组和广义表 (26)

第5章树和二叉树 (33)

第6章图 (43)

第7章查找 (54)

第8章排序 (65)

第1章绪论

1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：

数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

《数据结构（C语言版第2版）》（严蔚敏著）

第四章练习题答案

第4章串、数组和广义表

1．选择题

（1）串是一种特殊的线性表，其特殊性体现在（）。

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

C．可以链式存储D．数据元素可以是多个字符若

答案：B

（2）串下面关于串的的叙述中，（）是不正确的？

A．串是字符的有限序列B．空串是由空格构成的串

C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储

答案：B

解释：空格常常是串的字符集合中的一个元素，有一个或多个空格组成的串成为空格串，

零个字符的串成为空串，其长度为零。

（3）串“ababaaababaa”的next数组为（）。

A．012345678999 B．012121111212 C．011234223456 D．0123012322345

答案：C

（4）串“ababaabab”的nextval为（）。

A．010104101B．010102101 C．010100011 D．010101011

答案：A

（5）串的长度是指（）。

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

C．串中所含不同字符的个数D．串中所含非空格字符的个数

答案：B

解释：串中字符的数目称为串的长度。

（6）假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单

元，基地址为10，则LOC[5,5]=（）。

A．808 B．818 C．1010 D．1020

答案：B

解释：以行序为主，则LOC[5,5]=[（5-1）*100+（5-1）]*2+10=818。

《数据结构》第四章习题

一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）

1、KMP算法的特点是在模式匹配时指示主串的指针不会变小。( √)

2、串是一种数据对象和操作都特殊的线性表。( √)

3、只包含空白字符的串称为空串（空白串）。( ×)

4、稀疏矩阵压缩存储后，必会（不会）失去随机存取功能。( ×)

5、使用三元组表示稀疏矩阵的非零元素能节省存储空间。( √)

6、插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数组中也经常使用。（×）

7、若采用三元组表存储稀疏矩阵，只要把每个元素的行下标和列下标互换（错的），就完成了对该矩阵的转置运算。（×）

二、单项选择题

1．下面关于串的的叙述中，哪一个是不正确的？（ B ）

A．串是字符的有限序列B．空串是由空格构成的串（空串是长度为零的串）C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2．有串S1=’ABCDEFG’，S2 = ’PQRST’，假设函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回中s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是（ D ）。

A．BCDEF B．BCDEFG C．BCPQRST D．CDEFGFG

3、串的长度是指（ B ）

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

C．串中所含不同字符的个数D．串中所含非空格字符的个数

数据结构部分课后习题答案第四章4.1

广度优先生成树(黑体加粗边:

深度拓扑排序序列:v0-v2-v3-v1-v4 4.2

广度

深度

(1

(2

加边顺序

a-b b-e e-d d-f f-c

4.3、如图所示为一个有6个顶点{u1,u2,u3,u4,u5,u6}的带权有向图的邻接矩阵。根据此邻接矩阵画出相应的带权有向图,利用dijkstra 算法求第一个顶点u1到其余各顶点的最短路径,并给出计算过程。

带权有向图:

4.4证明在图中边权为负时Dijkstra算法不能正确运行

若允许边上带有负权值,有可能出现当与S(已求得最短路径的顶点集,归入S内的结点的最短路径不再变更内某点(记为a以负边相连的点(记为b确定其最短路径时,它的最短路径长度加上这条负边的权值结果小于a原先确定的最短路径长度,而此时a在Dijkstra算法下是无法更新的。

4.5

P.198 图中的权值有负值不会影响prim和kruskal的正确性如图:

KRUSKAL求解过程:

4.6 Dijkstra算法如何应用到无向图?

答:Dijkstra算法通常是运用在带非负权值的有向图中,但是无向图其实就是两点之间两条有向边权值相同的特殊的有向图,这样就能将Dijkstra算法运用到无向图中。

4.7

用FLOYD算法求出任意两顶点的最短路径(如图A(6所示。

A(0= A(1= A(2=

A(3= A(4=

A(5= A(6= V1 到 V2、V3、V4、V5、V6 往返路径长度分别为 5，9，5，9，9，最长为 9，总的往返路程为 37 同理 V2 到 V1、V3、V4、V5、V6 分别为 5，8，4，4，13，最长为 13，总和 34 V3 对应分别为 9，8，12，8，9，最长为 12，

【课后习题】第4章 串 第5章 数组和广义表

网络工程2010级（ ）班 学号： 姓名：

题 号 一 二 三 四 总分 得 分

一、填空题（每空1分，共30分）

1. 串有三种机内表示方法： 、 和 ，其中前两种属于顺序存储结构，第三种属于 。

2. 若n 为主串长度，m 为子串长度，则串的BF （朴素）匹配算法最坏的情况下需要比较字符的总次数

为 ,T(n)= 。

3. 是任意串的子串；任意串S 都是S 本身的子串，除S 本身外，S 的其他子串称为S 的 。

4. 设数组a[1…50, 1…60]的基地址为1000，每个元素占2个存储单元，若以行序为主序顺序存储，则

元素a[32,58]的存储地址为 。

5. 对于数组，比较适于采用 结构够进行存储。

6. 广义表的深度是指_______。

7. 将一个100100 A 的三对角矩阵，按行优先存入一维数组B[297]中，A 中元素66,66A 在B 数组中的位置

k 为 。

8. 注意：a i,j 的k 为 2(i-1)+j-1,(i=1时j=1,2;1

10. 求串T 在主串S 中首次出现的位置的操作是 ，其中 称为目标串， 称为

模式。

11. 对称矩阵的下三角元素a[i,j]，存放在一维数组V 的元素V[k]中（下标都是从0开始）， 12. k 与i ，j 的关系是：k= 。

13. 在n 维数组中每个元素都受到 个条件的约束。 14. 同一数组中的各元素的长度 。

15. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元

素的 、 和 。

数据结构(C语言版)习题及答案第四章习题

4.1选择题

1、空串与空格串是（B）。

A、相同

B、不相同Ｃ、不能确定

2、串是一种特殊的线性表，其特殊性体现在（B）。

A、可以顺序存储

B、数据元素是一个字符

C、可以链式存储

D、数据元素可以是多个字符

3、设有两个串p和q，求q在p中首次出现的位置的操作是（B）。

A、连接

B、模式匹配

C、求子串

D、求串长

4、设串1=“ABCDEFG”，2=“PQRST”函数trconcat（，t）返回和t串的连接串，trub（，i，j）返回串中从第i个字符开始的、由连续j 个字符组成的子串。trlength()返回串的长度。则trconcat（trub（1，2，trlength（2）），trub（1，trlength（2），

2））的结果串是（D）。

A、BCDEF

B、BCDEFG

C、BCPQRST

D、BCDEFEF

5、若串=“oftware”，其子串个数是（B）。

A、8

B、37

C、36

D、9

4.2简答题

1、简述空串与空格串、主串与子串、串名与串值每对术语的区别？

答：空串是指长度为0的串，即没有任何字符的串。

空格串是指由一个或多个空格组成的串，长度不为0。

子串是指由串中任意个连续字符组成的子序列，包含子串的串称为主串。串名是串的一个名称，不指组成串的字符序列。

串值是指组成串的若干个字符序列，即双引号中的内容。

2、两个字符串相等的充要条件是什么？

答：条件一是两个串的长度必须相等

条件二是串中各个对应位置上的字符都相等。

3、串有哪几种存储结构？

答：有三种存储结构，分别为：顺序存储、链式存储和索引存储。

1 填空题

（1）数据元素（2）数据项数据元素（3）集合线性结构树结构图结构（4）顺序存储链接存储数据元素数据元素之间的关系

（5）零或多个输入一个或多个输出有穷性确定性可行性

（6）自然语言程序设计语言流程图伪代码，伪代码

（7）问题规模（8）O(1) O(nlog2n)

2 选择题

（1）C D (2)B (3) B (4) A (5) D (6)A (7) C (8) C E

3 判断题

×××√×

第二章

1 填空题

（1）表长一半表长位置

（2）108

（3）p->next=(p->next)->next;

（4）运算方便

（5）p->next=head;

（6）s->next=rear->next rear->next=s; rear=s;

q=rear->next->next; rear->next->next=q->next; delete q;

（7）O(1) O(n)

（8）循环单链表循环双链表双链表

2 选择题

（1） A B （2） D （3） B （4） A （5） A （6） D

（7） B

（8） B

（9） C

（10）B

（11）B

（12）D

（13）A

（14）A

3 判断题×××××

1 填空题

（1）1003H

（2）顺序栈和链栈top=-1或top==NULL top==数组长度或内存无可用空间（3）栈

（4）abc+*d-

（5）后进先出先进先出操作位置受限

（6）假溢出

（7）（rear-front+n）% n

（8）O(1) O(n)

2 选择题

第1章 绪论

5．选择题：CCBDCA

6．试分析下面各程序段的时间复杂度。．试分析下面各程序段的时间复杂度。 （1）O （1） （2）O （m*n ） （3）O （n 2） （4）O （log 3n ）

（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O （n 2） （6）O(n )

第2章 线性表

1．选择题．选择题

babadbcabdcddac 2．算法设计题．算法设计题

（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。 ElemType Max (LinkList L ){

if(L->next==NULL) return NULL; pmax=L->next; //假定第一个结点中数据具有最大值假定第一个结点中数据具有最大值 p=L->next->next;

while(p != NULL ){//如果下一个结点存在

if(p->data > pmax->data) pmax=p; p=p->next; }

return pmax->data;

（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。的存储空间。

void inverse(LinkList &L) { // 逆置带头结点的单链表 L

p=L->next; L->next=NULL; while ( p) {

q=p->next; // q 指向*p 的后继 p->next=L->next;