数据结构 第4章 串练习题

数据结构第四五六七章作业答案数据结构第四、五、六、七章作业答案第四章和第五章一、填空题1.不包含任何字符（长度为0）的字符串称为空字符串；由一个或多个空格（仅空格字符）组成的字符串称为空白字符串。

2.设s=“a;/document/mary.doc”，则strlen(s)=20,“/”的位置为3。

3.子串的定位操作称为串模式匹配；匹配的主字符串称为目标字符串，子字符串称为模式。

4、串的存储方式有顺序存储、堆分配存储和块链存储5.有一个二维数组a[0:8,1:5]，每个数组元素用四个相邻字节存储，内存用字节寻址。

假设存储阵列元素a[0,1]的地址为100，如果以主行顺序存储，则a[3,5]的地址为176，[5,3]的地址为208。

如果按列存储，[7,1]的地址为128，[2,4]的地址为216。

6、设数组a[1…60,1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为8950。

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

8、二维数组a[10][20]采用列序为主方式存储，每个元素占10个存储单元，且a[0][0]的存储地址是2000，则a[6][12]的地址是32609.已知二维数组a[20][10]按行顺序存储，每个元素占2个存储单元，a[10][5]的存储地址为1000，则a[18][9]的存储地址为116810。

已知二维数组a[10][20]按行顺序存储，每个元素占2个存储单元，a[0][0]的存储地址为1024，则a[6][18]的地址为130011，两个字符串相等。

充要条件是长度相等，相应位置的字符相同。

12、二维数组a[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且a[0][0]的存储地址是200，则a[6][12]的地址是200+（12*10+6）=326。

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

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

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

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

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

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

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

动态分配的顺序串是在编译时不分配串值空间，在运行过程中用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. 不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串。

2. 设S=“A;/document/Mary.doc”，则strlen(s)= 20 , “/”的字符定位的位置为3。

3. 子串的定位运算称为串的模式匹配；被匹配的主串称为目标串，子串称为模式。

4. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 6 次匹配成功。

5. 若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m。

6. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。

已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为288 B ；末尾元素A57的第一个字节地址为1282 ；若按行存储时，元素A14的第一个字节地址为(8+4)×6+1000=1072 ；若按列存储时，元素A47的第一个字节地址为(6×7＋4)×6＋1000）＝1276 。

(注：数组是从0行0列还是从1行1列计算起呢？由末单元为A57可知，是从0行0列开始！)7. 〖00年计算机系考研题〗设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为8950 。

答：不考虑0行0列，利用列优先公式：LOC(a ij)=LOC(a c1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L 得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2＝89508. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的行下标、列下标和元素值。

9.求下列广义表操作的结果：（1）GetHead【((a,b),(c,d))】=== (a, b) ; //头元素不必加括号（2）GetHead【GetTail【((a,b),(c,d))】】=== (c,d) ;（3）GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== b ;（4）GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== （d）;10．C语言规定，字符串常量按_字符数组_____处理，它的值在程序的执行过程中是不能改变的。

习题4 串4.1 单项选择题1．以下叙述中正确的是。

A.串是一种特殊的线性表B.串的长度必须大于零C.串中无素只能是字母D.空串就是空白串2．空串与空格串是相同的，这种说法____。

A. 正确B. 不正确3．串是一种特殊的线性表，其特殊性体现在____。

A. 可以顺序存储B. 数据元素是一个字符C. 可以链接存储D. 数据元素可以是多个字符4．设有两个串p和q，求q在p中首次出现的位置的运算称作____。

A. 连接B. 模式匹配C. 求子串D. 求串长5．设串s1='ABCDEFG'，s2='PQRST'，函数con (x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i（从1开始编号）的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con (subs (s1,2,len (s2)), subs (s1,len (s2),2))的结果串是____。

A. BCDEFB. BCDEFGC. BCPQRSTD. BCDEFEF6．设串的长度为n，则它的子串个数为。

A.nB.n(n+1)C.n(n+1)/2D.n(n+1)/2+14.2 填空题（将正确的答案填在相应的空中）1．串的两种最基本的存储方式是________。

2．两个串相等的充分必要条件是________。

3．空串是________，其长度等于________。

4．空格串是________，其长度等于________。

5．设串s='I︺AM︺A︺TEACHER', ︺表示空格，则s的长度是________。

4.3 判断题1．子串定位函数的时间复杂度在最坏情况下为O（n*m），因此子串定位函数没有实际使用的价值。

（）2．KMP算法的最大特点是指主串的指针不需要回溯。

（）3．如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。

（）4.4 算法设计题1．编写算法，从串s 中删除所有和串 t相同的子串。

吉林省专升本考试数据结构分章习题及参考答案———选择题（第四章）1、多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为( )。

A、数组的元素处在行和列两个关系中B、数组的元素必须从左到右顺序排列C、数组的元素之间存在次序关系D、数组是多维结构，内存是一维结构2、串的长度是（）A、串中不同字母的个数B、串中不同字符的个数C、串中所含字符的个数D、串中所含字符的个数，且大于03、串与普通的线性表相比较，它的特殊性体现在（）。

A、顺序的存储结构B、链式存储结构C、数据元素是一个字符D、数据元素任意4、若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1……n(n+1)/2]中，则在B中确定aij(i<j)的位置k的关系为( )。

A、i*(i-1)/2+jB、j*(j-1)/2+iC、i*(i+1)/2+jD、j*(i+1)/2+i5、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。

A、60B、66C、18000D、336、若6行8列的数组以列序为主序顺序存储,基地址为1000,每个元素占2个存储单元,则第5行第3列的元素(假定无第0行第0列)的地址是()。

A、 1086B、 1032C、 1068D、答案A,B,C都不对7、下面的说法中,不正确的是(）A、数组是一种线性结构B、数组是一种定长的线性结构C、除了插入与删除操作外，数组的基本操作还有存取修改、检索和排序等D、数组的基本操作有存取、修改、检索和排序等，没有插入与删除操作8、设有一个n*n的对称矩A,将其下三角部分按行存放在一维数组B中，而A[0][0]存放于B[0]中，那么第i行对角线元素A[i][i]存放于B中( ) 处。

A、(i+3)i/2B、(i+1)i/2C、(2n-i+1)i/2D、(2n-i-1)i/29、设模式T=“abcabc”，则该模式的next值为（）A、{-1,0,0,1,2,3}B、{-1,0,0,0,1,2}C、{-1,0,0,1,1,2}D、{-1,0,0,0,2,3}10、下面()不属于特殊矩阵。

B(2.0) D(2.0) D(2.0) D(2.0) D(2.0) A(2.0) B(2.0) B(2.0) D(2.0) C(2.0) D(2.0) D(2.0)2-1广义表是一种（B）数据结构。

(2分)1.非递归的2.递归的3.树型4.图状作者: 严冰单位: 浙江大学城市学院2-2一个广义表为( a, (b, c), d, (), ((f, g), h) )，则该广义表的长度与深度分别为（D）。

(2分)1.4和62.6和33.3和54.5和3作者: 严冰单位: 浙江大学城市学院2-3稀疏矩阵的快速转置算法的时间复杂度是（D）。

(2分)1.三次方时间2.二次方时间3.对数时间4.线性时间作者: 严冰单位: 浙江大学城市学院2-4在定义稀疏矩阵的十字链接存储结构时，每个结点结构需包含（D）个域。

(2分)1. 42. 33. 64. 5作者: 严冰单位: 浙江大学城市学院2-5广义表与稀疏矩阵都是线性表的扩展，它们的共同点为（D）。

(2分)1.都可以用链接结构与顺序结构存储2.无共同点3.都是递归结构4.数据元素本身是一个数据结构作者: 严冰单位: 浙江大学城市学院2-6(neuDS_C++)以下叙述中正确的是(A )。

(2分)1.串是一种特殊的线性表2.串的长度必须大于零3.串中元素只能是字母4.空串就是空白串作者: 姚志军单位: 广东东软学院2-7(neuDS_C++)串是一种特殊的线性表，其特殊性体现在(B )。

(2分)1.可以顺序存储2.数据元素是一个字符3.可以链接存储4.数据元素可以是多个字符作者: 姚志军单位: 浙江大学2-8(neuDS_C++)设有两个串p和q，求q在p中首次出现的位置的运算称作( B)。

(2分)1.连接2.模式匹配3.求子串4.求串长作者: 姚志军单位: 广东东软学院2-9(neuDS_C++)设串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 )。

数据结构(第二版)习题答案第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 100typedef struct{char str[MAXSIZE];int length;}seqstring;/* 函数 strcompare()的功能是：当 s1>s2时返回 1，当 s1==s2时返回 0，当 s1<s2时返回-1*/int strcompare(seqstring s1,seqstring s2){ int i,m=0,len;len=s1.length<s2.length ?s1.length:s2.length;for(i=0;i<=len;i++)if(s1.str[i]>s2.str[i]){m=1;break;}else if(s1.str[i]<s2.str[i]){m=-1;break;}return m;}int main(){ seqstring s1,s2;int i,m;printf("input char to s1:\n");gets(s1.str);s1.length=strlen(s1.str);printf("input char to s2:\n");gets(s2.str);s2.length=strlen(s2.str);m=strcompare(s1,s2);if(m==1) printf("s1>s2\n");else if(m==-1) printf("s2>s1\n");else if(m==0) printf("s1=s2\n");}4.9试编写一个函数，实现在顺序存储方式下字符串的replace（S，T1，T2）运算。

第四章串一．单项选择题1．串的连接运算不满足。

A. 分配律B. 交换律C. 结合律D. 都不满足2．串是一种特殊的线性表，其特殊性体现在。

A. 可以顺序存储B. 数据元素是一个字符C. 可以链接存储D. 数据元素可以是多个字符3．设有两个串p和q，求q在p中首次出现的位置的运算称作。

A. 连接B. 模式匹配C. 求子串D. 求串长4．串是一个的序列。

A. 不少于一个字母B. 有限个字符C. 不少于一个字符D. 空格或字母5．已知串s=’ABCDEFGH’，则s的所有不同子串的个数为。

A. 8B. 9C. 36D. 376. 设串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))的结果串是。

A. BCDEFB. BCDEFGC. BCPQRSTD. BCDEFEF二．填空题1．两个串相等的充分必要条件是。

2．空格串是①,其长度等于②。

3．模式串‘abaabade’的next函数值为。

4．在串S=’tuition’中，以t为首字符且值不相同的子串有个。

5. 使用“求子串”substring(S,pos,len)和“联接”concat(S1,S2)的串操作，可从串s=’conduction’中的字符得到串t=’cont’，则求t的串表达式为。

6. 已知字符串p=’abcabcabbac’，则next(3)和next(6)分别为①、②。

7. 设对主串’bcdbcddabcdbcdbac’和模式串’bcdbcdb’进行KMP模式匹配。

第1趟匹配失败后，若使用非改进的Next函数，则下一趟匹配将由主串的第①个字符与模式串的第__②___字符开始比较。

若采用改进的Next函数，则下一趟匹配将由主串的第③个字符与模式串的第___④__字符开始比较。

《数据结构（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。

（7）设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（）。

A．BA+141 B．BA+180 C．BA+222 D．BA+225答案：B解释：以列序为主，则LOC[5,8]=[（8-1）*8+（5-1）]*3+BA=BA+180。

第4章串、数组和广义表一、填空题1、零个或多个字符组成的有限序列称为串。

二、判断题1、稀疏矩阵压缩存储后，必会失去随机存取功能。

（√）2、数组是线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。

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

（╳）4、若一个广义表的表头为空表，则此广义表亦为空表。

（╳）5、所谓取广义表的表尾就是返回广义表中最后一个元素。

（╳）三、单项选择题1、串是一种特殊的线性表，其特殊性体现在（B）。

A．可以顺序存储B．数据元素是一个字符C．可以链式存储D．数据元素可以是多个字符若2、串下面关于串的的叙述中，（B）是不正确的？A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储解释：空格常常是串的字符集合中的一个元素，有一个或多个空格组成的串成为空格串，零个字符的串成为空串，其长度为零。

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

A．012345678999 B．012121111212 C．011234223456 D．01230123223454、串“ababaabab”的nextval为（A）。

A．010104101B．010102101 C．010100011 D．0101010115、串的长度是指（B）。

A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数解释：串中字符的数目称为串的长度。

6、假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（B）。

A．808 B．818 C．1010 D．1020解释：以行序为主，则LOC[5,5]=[（5-1）*100+（5-1）]*2+10=818。

数据结构(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.7习题一、选择（1）串是（）。

A 不少于一个字母和序列B 任意个字母的序列C 不少于一个字符的序列D 有限个字符的序列（2）串的长度是（）。

A 串中不同字母的个数B 串中不同字符的个数C 串中所含字符的个数，且大于0D 串中所含字符的个数（3）设串s1＝‘abcdefg’，s2＝‘pqrst’，函数CON（X，Y）返回X和串的连接串，SUB （S，I，J）返回串S的从序号I的字符开始的J个字符组成的子串，LEN（S）返回串S的长度，则CON（SUB（s1,2，LEN（s2））,SUB(s1,LEN(s2),2)）的结果串是（）。

A bcdefB bcdefgC bcpqrstD bcdefef注释：CON（SUB（s1,2，LEN（s2））, SUB(s1,LEN(s2),2)）= CON（SUB（s1,2，5）, SUB(s1,5,2)）= CON（bcdef, ef）=bcdefef（4）数组A[1：5][1：6]的每个元素占5个单元，将其按行优先次序存储在起始起址为1000的连续的内存单元中，则元素A[5,5]的地址为（A）。

A 1140B 1145C 1120D 1125注释：该数组为5行6列，按照公式：Loc[i, j]=Loc[1,1] + (n×(i-1)+j-1)×size,其中m=5,n=6, size=5 ,那么Loc[5, 5]=Loc[1,1] + (6×(5-1)+5-1)×5=1140（5）对矩阵压缩存储是为了（）。

A 方便运算B 节省空间C 方便存储D 提高运算速度（6）数组通常具有的两种基本操作是（）。

A 插入与删除B 索引和修改C 查找和修改D 查找与删除注释：数组，连续存储，不适合经常插入和删除；适合经常查找和修改（定位后修改某单元内的值，单元个数和单元之间的逻辑顺序不做修改。

）（7）二维数组M[i,j]的行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3,5]的起始地址与M按列存储时元素（）的起始地址相同。

第4～5章串和数组自测卷答案一、填空题（每空1分，共20分）1. 不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串。

（对应严题集4.1①，简答题：简述空串和空格串的区别）2. 设S=“A;/document/Mary.doc”，则strlen(s)= 20 , “/”的字符定位的位置为3。

4. 子串的定位运算称为串的模式匹配；被匹配的主串称为目标串，子串称为模式。

5. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 6 次匹配成功。

6. 若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m。

7. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。

已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为288 B ；末尾元素A57的第一个字节地址为1282 ；若按行存储时，元素A14的第一个字节地址为(8+4)×6+1000=1072 ；若按列存储时，元素A47的第一个字节地址为(6×7＋4)×6＋1000）＝1276 。

(注：数组是从0行0列还是从1行1列计算起呢？由末单元为A57可知，是从0行0列开始！)8. 〖00年计算机系考研题〗设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为8950 。

答：不考虑0行0列，利用列优先公式：LOC(a ij)=LOC(a c1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2＝89509. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的行下标、列下标和元素值。