数据结构课后习题及解析第四章

第四章一、简述下列每对术语的区别：空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。

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

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

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

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

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

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

动态分配的顺序串是在编译时不分配串值空间，在运行过程中用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');(2)在执行下列语句后，s3的值是什么?strcpy(s3,s1); strcat(s3,","); strcat(s3,s2);(3)调用函数strcmp(s1,s2)的返回值是什么?(4)调用函数strcmp(&s1[5],"ton")的返回值是什么?(5)调用函数stlen(strcat(s1,s2))的返回值是什么?解：(1) stchr(*s,c)函数的功能是查找字符c在串s中的位置，若找到，则返回该位置，否则返回NULL。

一. 名词解释（1）栈——只允许在一端进行插入或删除操作的线性表称为栈。

其最大的特点是“后进先出”。

（2）顺序栈——采用顺序存储结构的栈称为顺序栈。

（3）链栈——采用链式存储结构的栈称为链栈。

（5）队列——只允许在一端进行插入，另一端进行删除操作的线性表称为队列。

其最大的特点是“先进先出”。

（6）顺序队列——采用顺序存储结构的队列称为顺序队列。

（7）链队列——采用链式存储结构的称队列为链队列。

（8）循环队列——为了解决顺序队列中“假溢出”现象，将队列的存储空间想象为一个首尾相链的环（即把队头元素与对尾元素链结起来），存储在其中的队列称为循环队列。

二．判断题（下列各题，正确的请在前面的括号内打√；错误的打ㄨ）（1）√（2）√（3）ㄨ（4）ㄨ（5）ㄨ（6）ㄨ（7）√（8）√（9）ㄨ（10）√（11）ㄨ（12）ㄨ三. 填空题（1）后进先出（2）栈顶栈底（3）栈空栈满（4）O（1）O（1）（5）必须一致（6）栈（7）栈空（8）p->next=top top=p（9）- - + +（10）LS->next 首（11）先进先出（12）队尾队头（13）队列是否为空队列是否为满（14）可变的（15）-1 NULL（16）O(n) O(1) O(1) O(1)（17）front==rear front==(rear+1)% MAXLEN MAXLEN-front （18）空只含有一个结点（19）front==rear && front <>NULL（20）队尾指针写入四. 选择题（1）C （2）A （3）D （4）B （5）C（6）D （7）B （8）A （9）A （10）D（11）A （12）A （13）C （14）A （15）B (16) A五、简答题答：n个（同类）数据元素的有限序列称为线性表。

线性表的特点是数据元素之间存在“一对一”的关系。

栈和队列都是操作受限制的线性表，它们和线性表一样，数据元素之间都存在“一对一”的关系。

第四章串习题4一、选择题1.串是一种分外的线性表，其分外性体现在（）。

A.可以顺序存储B.数据元素是一个字符C.可以连接存储D.数据元素可以是多个字符2.有两个串P和Q，求P在Q中首次出现的位置的运算称为（）。

A.模式匹配B.联接C.求子串D.求串长3.设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非通俗子串（非空且例外于S本身）的个数为（）。

A.n²B.（n²/2）+（n/2）C.（n²/2）+（n/2）-1D.（n²/2）-（n/2）-14.设串s1=“ABCDEFG”,s2=“PQRST”，函数concat（x，y）返回x和y串的连接串，subString（s，i，j）返回串s的从序号i的字符开始的j个字符组成的子串，Strlength（s）返回串s的长度，则concat（subString（s1，2，Strlength（s2）），subString(s1，Strlength（s2），2)））的结果串是（）。

A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF5.顺序串中，根据空间分配方式的例外，可分为（）。

A.直接分配和间接分配B.静态分配和动态分配C.顺序分配和链式分配D.随机分配和不变分配6.设串S=“abcdefgh”，则S的所有非通俗子串（除空串和S自身的串）的个数是（）。

A.8B.37C.36D.357.设主串的长度为n，模式串的长度为m，则串匹配的KMP算法时间复杂度是（）。

A.O(m)B.O（n）C.O（m+n）D.O（n*m）8.已知串S=“aaab”，其next数组值为（）。

A.0123B.1123C.1231D.1211二丶填空题1.在空串和空格串中，长度不为0的是（）。

2.空格串是指（），其长度等于（）。

3.按存储结构的例外，串可分为（）、（）和（）。

4.C语言中，以字符（）表示串值的终结。

5.在块链串中，为了提高存储密度，应该增大（）。

第一章绪论一、选择题1.组成数据的基本单位是（）（A）数据项（B）数据类型（C）数据元素（D）数据变量2.数据结构是研究数据的（）以及它们之间的相互关系。

（A）理想结构，物理结构（B）理想结构，抽象结构（C）物理结构，逻辑结构（D）抽象结构，逻辑结构3.在数据结构中，从逻辑上可以把数据结构分成（）（A）动态结构和静态结构（B）紧凑结构和非紧凑结构（C）线性结构和非线性结构（D）内部结构和外部结构4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。

①（A）数据元素（B）计算方法（C）逻辑存储（D）数据映像②（A）结构（B）关系（C）运算（D）算法5.算法分析的目的是（）。

（A）找出数据结构的合理性（B）研究算法中的输入和输出的关系（C）分析算法的效率以求改进（D）分析算法的易懂性和文档性6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5个特性。

①（A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法②（A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性（C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性二、判断题1.数据的机内表示称为数据的存储结构。

（）2.算法就是程序。

（）3.数据元素是数据的最小单位。

（）4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。

（）5.算法的时间复杂度取决于问题的规模和待处理数据的初态。

（）三、填空题1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。

2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。

3.在树形结构中,树根结点没有_______结点,其余每个结点有且只有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________。

第四章习题解答一、基础知识题4.1 简述下列每对术语的区别：略4.2 假设有如下的串说明：char s1[30]="stocktom,CA",s2[30]="March 5,1999",s3[30],*p;(1)在执行如下的每个语句后p的值是什么？略p=strchr(s1,'t')p=strchr(s2,'9')p=strchr(s2,'6')(2)在执行下列语句后，s3的值是什么？strcpy(s3,s1)：s3的值为"stocktom CA"strcat(s3,",")：s3的值为"stocktom CA,"strcat(s3,s2)：s3的值为"stocktom CA,March 5,1999"(3)调用函数strcmp(s1,s2)的返回值是什么？因为s1>s2，所以返回一个正值。

(4)调用函数strcmp(&s1[5],"ton")的返回值是什么？&s1[5]指向“tom,CA”，因为"tom,CA"<"ton"，所以返回一个负值。

(5)调用函数strlen(strcat(s1,s2))的返回值是什么？返回值是23。

二、算法设计题：4.3 利用C的库函数strlen，strcpy和strcat写一个算法void StrInsert(char *S,char *T,int i)，将串T插入到串S的第i个位置上。

若i大于S的长度，则插入不执行。

void StrInsert(char *S,char *T,int i){char temp[256];if(i>strlen(S))return;strcpy(temp,&S[i]);S[i]='\0';strcat(T,temp);strcat(S,T);}4.4 利用C的库函数strlen和strcpy写一算法void StrDelete(char *S,int i,int m)，删去串S中从位置i连续m个字符。

第四章习题1. 设s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’。

给出下列操作的结果：StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1);StrIndex(s,’A’,4); StrReplace(s,’STUDENT’,q);StrCat(StrCat(sub1,t), StrCat(sub2,q));2. 编写算法，实现串的基本操作StrReplace(S,T,V)。

3. 假设以块链结构表示串，块的大小为1，且附设头结点。

试编写算法，实现串的下列基本操作：StrAsign(S,chars)；StrCopy(S,T)；StrCompare(S,T)；StrLength(S)；StrCat(S,T)；SubString(Sub,S,pos,len)。

4．叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。

5．已知：S=”(xyz)*”,T=”(x+z)*y”。

试利用联接、求子串和置换等操作，将S转换为T. 6．S和T是用结点大小为1的单链表存储的两个串，设计一个算法将串S中首次与T匹配的子串逆置。

7．S是用结点大小为4的单链表存储的串,分别编写算法在第k个字符后插入串T，及从第k个字符删除len个字符。

以下算法用定长顺序串：8．编写下列算法：（1）将顺序串r中所有值为ch1的字符换成ch2的字符。

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

（3）从顺序串r中删除其值等于ch的所有字符。

（4）从顺序串r1中第index 个字符起求出首次与串r2相同的子串的起始位置。

（5）从顺序串r中删除所有与串r1相同的子串。

9．写一个函数将顺序串s1中的第i个字符到第j个字符之间的字符用s2串替换。

10．写算法，实现顺序串的基本操作StrCompare(s,t)。

【课后习题】第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<i<=n 时,j=i-1,i,i+1) 。

9. 称为空串； 称为空白串。

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

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

13. 在n 维数组中每个元素都受到 个条件的约束。

14. 同一数组中的各元素的长度 。

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

16.稀疏矩阵中有n个非零元素，则其三元组有行。

17.求下列广义表操作的结果：18.（1）GetHead【((a,b),(c,d))】=== ;19.（2）GetHead【GetTail【((a,b),(c,d))】】=== ;20.（3）GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== ;21.（4）GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== ;22.广义表E=(a,(b,E)),则E的长度= ，深度= ；二、判断题（如果正确，在下表对应位置打“√”，否则打“⨯”。

第一章绪论一、选择题1.组成数据的基本单位是（）（A）数据项（B）数据类型（C）数据元素（D）数据变量2.数据结构是研究数据的（）以及它们之间的相互关系。

（A）理想结构，物理结构（B）理想结构，抽象结构（C）物理结构，逻辑结构（D）抽象结构，逻辑结构3.在数据结构中，从逻辑上可以把数据结构分成（）（A）动态结构和静态结构（B）紧凑结构和非紧凑结构（C）线性结构和非线性结构（D）内部结构和外部结构4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。

①（A）数据元素（B）计算方法（C）逻辑存储（D）数据映像②（A）结构（B）关系（C）运算（D）算法5.算法分析的目的是（）。

（A）找出数据结构的合理性（B）研究算法中的输入和输出的关系（C）分析算法的效率以求改进（D）分析算法的易懂性和文档性6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5个特性。

①（A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法②（A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性（C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性二、判断题1.数据的机内表示称为数据的存储结构。

（）2.算法就是程序。

（）3.数据元素是数据的最小单位。

（）4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。

（）5.算法的时间复杂度取决于问题的规模和待处理数据的初态。

（）三、填空题1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。

2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。

3.在树形结构中,树根结点没有_______结点,其余每个结点有且只有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________。

《数据结构》第四章习题一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）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．CDEFGFG3、串的长度是指（ B ）A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数三、填空题1、串是一种特殊的线性表，其特殊性表现在_数据元素为字符，操作集也不同__；串的两种最基本的存储方式是_顺序存储_、__ 链式存储_；两个串相等的充分必要条件是__两串的长度相等且两串中对应位置的字符也相等__。

2、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为_O(m+n)__。

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

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

3．简述逻辑结构的四种基本关系并画出它们的关系图。

4．存储结构由哪两种基本的存储方法实现？5．选择题（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．栈6．试分析下面各程序段的时间复杂度。

（1）x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;（2）for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;（3）s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;（6）x=n; //n>1y=0;while(x≥(y+1)* (y+1))y++;（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2）（6）O(n)第2章线性表1．选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。

数据结构部分课后习题答案第四章4.1广度优先生成树(黑体加粗边:深度拓扑排序序列:v0-v2-v3-v1-v4 4.2广度深度(1(2加边顺序a-b b-e e-d d-f f-c4.3、如图所示为一个有6个顶点{u1,u2,u3,u4,u5,u6}的带权有向图的邻接矩阵。

根据此邻接矩阵画出相应的带权有向图,利用dijkstra 算法求第一个顶点u1到其余各顶点的最短路径,并给出计算过程。

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

4.5P.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，总和为 46 V4 对应分别为 5，4，12，4，9，最长为 12，总和为 34 V5 对应分别为9，4，8，4，9，最长为 9，总和为 34 V6 对应分别为 9，13，9，9，9，最长为13，总和为 49 题目要求娱乐中心“距其它各结点的最长往返路程最短” ，结点V1， V5 最长往返路径最短都是 9。

数据结构(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、BCDEFB、BCDEFGC、BCPQRSTD、BCDEFEF5、若串=“oftware”，其子串个数是（B）。

A、8B、37C、36D、94.2简答题1、简述空串与空格串、主串与子串、串名与串值每对术语的区别？答：空串是指长度为0的串，即没有任何字符的串。

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

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

串名是串的一个名称，不指组成串的字符序列。

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

2、两个字符串相等的充要条件是什么？答：条件一是两个串的长度必须相等条件二是串中各个对应位置上的字符都相等。

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

4、已知两个串：1=”fgcdbcabcadr”,2=”abc”,试求两个串的长度，判断串2是否是串1的子串，并指出串2在串1中的位置。

答：（1）串1的长度为14，串2的长度为3。

（2）串2是串1的子串，在串2中的位置为9。

5、已知：1=〃I’matudent〃，2=〃tudent〃，3=〃teacher〃，试求下列各操作的结果：trlength(1)；答：13trconcat(2,3)；答：”tudentteachar”trdelub(1,4,10)；答：I’m6、设1=”AB”，2=”ABCD”，3=”EFGHIJK，试画出它们在各种存储结构下的结构图。

【课后习题】第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<i<=n 时,j=i-1,i,i+1) 。

9. 称为空串； 称为空白串。

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

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

13. 在n 维数组中每个元素都受到 个条件的约束。

14. 同一数组中的各元素的长度 。

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

16.稀疏矩阵中有n个非零元素，则其三元组有行。

17.求下列广义表操作的结果：18.（1）GetHead【((a,b),(c,d))】=== ;19.（2）GetHead【GetTail【((a,b),(c,d))】】=== ;20.（3）GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== ;21.（4）GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== ;22.广义表E=(a,(b,E)),则E的长度= ，深度= ；二、判断题（如果正确，在下表对应位置打“√”，否则打“⨯”。

第四章串一、单项选择题1．B2. B3．B4．C5. C二、填空题1．空、字符2．由空格字符（ASCII值32）所组成的字符串空格个数3．长度、相等、子、主4．55．011223126．（1）char s[ ] (2) j++ (3) i >= j7．[题目分析]本题算法采用顺序存储结构求串s和串t的最大公共子串。

串s用i指针（1<=i<=s.len）。

t串用j指针（1<=j<=t.len）。

算法思想是对每个i（1<=i<=s.len，即程序中第一个WHILE循环），来求从i开始的连续字符串与从j（1<=j<=t.len，即程序中第二个ＷHILE循环）开始的连续字符串的最大匹配。

程序中第三个（即最内层）的WHILE循环，是当s中某字符（s［i］）与t中某字符（t［j］）相等时，求出局部公共子串。

若该子串长度大于已求出的最长公共子串（初始为０），则最长公共子串的长度要修改。

(1) i+k<=s.len && j+k<=t.len && s[i+k]==t[j+k] //所有注释同上（a）(2) con=0 (3) j+=k (4) j++ (5) i++三、应用题1．空格是一个字符，其ASCII码值是32。

空格串是由空格组成的串，其长度等于空格的个数。

空串是不含任何字符的串，即空串的长度是零。

2．(a)A+B “ mule”(b)B+A “mule ”(c)D+C+B “myoldmule”(d)SUBSTR(B,3,2) “le”(e)SUBSTR(C,1,0) “”(f)LENGTH(A) 2(g)LENGTH(D) 2(h)INDEX(B,D) 0(i)INDEX(C,”d”) 3(j)INSERT(D,2,C) “myold”(k)INSERT(B,1,A) “m ule”(l)DELETE(B,2,2) “me”(m)DELETE(B,2,0) “mule”3．朴素的模式匹配（Brute－Force）时间复杂度是Ｏ（m＊n），KMP算法有一定改进，时间复杂度达到Ｏ（m＋n）。

python数据结构第四章课后习题1. 写一个Python程序，从键盘输入一个整数n，然后生成一个由n 个随机整数组成的列表，并输出该列表。

```pythonimport randomn = int(input("请输入整数n："))random_list = [random.randint(1, 100) for _ in range(n)]print(random_list)```2. 写一个Python函数，输入一个列表，返回该列表中的最大值和最小值。

```pythondef find_max_min(lst):max_val = max(lst)min_val = min(lst)return max_val, min_valmy_list = [1, 5, 2, 9, 3, 7]max_val, min_val = find_max_min(my_list)print("最大值：", max_val)print("最小值：", min_val)```3. 写一个Python程序，将两个有序列表合并为一个有序列表，不使用内置函数或排序算法。

```pythondef merge_sorted_lists(list1, list2):merged_list = []i = 0 # list1的索引j = 0 # list2的索引while i < len(list1) and j < len(list2):if list1[i] < list2[j]:merged_list.append(list1[i])i += 1else:merged_list.append(list2[j])j += 1# 处理剩余元素while i < len(list1):merged_list.append(list1[i])i += 1while j < len(list2):merged_list.append(list2[j])j += 1return merged_listlist1 = [1, 3, 5, 7, 9]list2 = [2, 4, 6, 8, 10]merged_list = merge_sorted_lists(list1, list2)print("合并后的有序列表：", merged_list)```4. 写一个Python函数，接受一个字符串作为参数，返回该字符串中第一个不重复的字符。