数据结构串和数组习题

【课后习题】第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 为 。

注意：a i,j 的k 为 2(i-1)+j-1,(i=1时j=1,2;1<i<=n 时,j=i-1,i,i+1) 。

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

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

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

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

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

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

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

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

习题四串一、单项选择题‎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；int f((1)__ _____‎_){int i=0,j=0;while‎(s[j])(2)___ _____‎;for(j--; i<j && s[i]==s[j]; i++,j--);retur‎n((3)___ ____)}7．下列算法实‎现求采用顺‎序结构存储‎的串s和串‎t的一个最‎长公共子串‎。

第四章串和数组一．选择题1．串是一种特殊的线性表，其特殊性体现在（）A．可以顺序存储B．数据元素是一个字符C．可以链式存储D．数据元素可以是多个字符2．串的长度是（）A．串中不同字母的个数B．串中不同字符的个数C．串中所含字符的个数，且大于0 D．串中所含字符个数3．若串S=”software”，其子串数目是（）A．8 B．37 C．36 D．94．数组A[0..5，0..6]的每个元素占5个单元，将其按列优先次序存储在起始地址为1000的连续内存单元中，则元素A[5][5]的地址为（）A．1175 B．1180 C．1205 D．12105．对矩阵压缩存储是为了（）A．方便运算B．节省存储空间C．方便存储D．提高运算速度6．一个n 阶对称矩阵，如果采用压缩存储方式，则容量为（）A．n2B．n2/2 C．n(n+1)/2 D．(n+1)2/27．对稀疏矩阵采用压缩存储，其缺点之一是（）A．无法判断矩阵有多少行多少列B．无法根据行列号查找某个矩阵元素C．无法根据行列号计算矩阵元素的存储地址D．使矩阵元素之间的逻辑关系更加复杂二．填空1．设串s1=”I am a student”，则串长为（）2．设有两个串p和q，其中q是p的子串，求子串q 在p中首次出现位置的算法称为（）3．一维数组的逻辑结构是（），存储结构是（）；对于二维或多维数组，分为按（）和（）两种不同的存储结构。

4．数组A[1..10,-2..6,2..8]以行优先顺序存储，设第一个元素的首地址为100，每个元素占3个单元的存储空间，则元素A[5][0][7]的存储地址为（）5．三维数组R[C1..D1,C2..D2,C3..D3]共含有（）个元素。

三、算法设计1．编写下列算法（假定下面所用的串均采用顺序存储方式，参数c、c1和c2均为字符型）：（1）将串S中所有其值为c1的字符换成c2的字符。

（2）将串S中所有字符逆序（3）从串S中删除其值等于c的所有字符（4）从串S中第index个字符起求出首次与字符串S1相同的子串的起始位置（5）从串S中删除重第i个字符起的j 个字符（6）从串S中删除所有与串S1相同的子串（允许调用第（4）题和第（5）题的算法）2．设计程序，计算串str中每一个字符出现的次数。

《数据结构》第四章串习题《数据结构》第四章串习题基本概念题：4-1 设S1 =“Data Structure Course”，S2 =“Structure”，S3 =“Base”，求：（1）Length(S1)；（2）Compare(S2, S3)；（3）Insert(S1, 5, S3)；（4）Delete(S1, 5, 9)；（5）SubString(S1, 5, 9, T)；（6）Search(S1, 0, S2)；（7）Replace(S1, 0, S2, S3)4-2 什么叫串？串和字符在存储方法上有什么不同？空串和空格串是否相同，为什么？4-3 串是由字符组成的，长度为1的串和字符是否相同。

为什么？4-4 串是不定长的，表示串的长度有几种方法？C语言中的串采用哪种方法？4-5 可以说串是数据类型固定为字符类型的线性表，但是串操作和线性表操作的主要不同之处在哪里？4-6 可以用几种存储方法存储串？4-7 分别写出串的静态数组存储结构和串的动态数组存储结构的结构体定义。

4-8 为什么动态数组结构下串的实现要增加撤消函数？复杂概念题：4-9 令t1=“aaab”, t2=“abcabaa”, t3=“abcaabbabcabaacba”，试分别求出他们的next[j]值。

4-10 简述模式匹配的Brute-Force算法思想。

简述模式匹配的KMP算法思想。

4-11 简述求子串的next[j]值的算法思想。

算法设计题：4-12 设串采用静态数组存储结构，编写函数实现两个串的比较Compare(S, T)。

要求比较结果有等于和不等于两种情况。

4-13 设串采用静态数组存储结构，编写函数实现两个串的比较Compare(S, T)。

要求比较结果有大于、等于和小于三种情况。

4-14 设串采用动态数组存储结构，编写函数实现两个串的比较Compare(S, T)。

要求比较结果有大于、等于和小于三种情况。

数据结构习题精编：串和数组一、选择题1．下面关于串的的叙述中，不正确的是A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2．下面关于串的的叙述中，正确的是A．空串就是空白串B．串相等指的是串的长度相等C．串的长度必须大于零D．串是一种特殊的线性表3．字符串是一种特殊的线性表，它与一般线性表的区别是A．字符串是一种线性结构B．字符串可以进行复制操作C．字符串可以顺序存储也可以链式存储D．字符串由字符构成并且通常作为整体参与操作4．串s="Data Structure"中长度为3的子串的数目是A．9B．11C．12D．145．若串S="software"，则S的子串的数目是A．8 B．35 C．36 D．376．已知串S= "string"，T="this"，执行运算StrLength(StrCopy(S,T))的结果是A．2 B．4 C．6 D．107．若串S="SCIENCESTUDY"，则调用函数StrCopy(P,SubString(S,1,7))后得到A．P="STUDY" B．P="SCIENCE" C．S="STUDY" D．S="SCIENCE" 8．若字符串采用链式存储，每个字符占用一个字节，每个指针在占用四个字节，则该字符串的存储密度为A．20%B．25%C．50%D．75%9．为查找某一特定单词在文本中出现的位置，可应用的串运算是A．串联接B．求子串C．串比较D．子串定位10．当目标串的长度为n，模式串的长度为m时，朴素的模式匹配算法最好情况下字符的比较次数A．m B．n C．n-m D．n+m11．当目标串的长度为n，模式串的长度为m时，朴素的模式匹配算法最坏情况下字符的比较次数A．m B．n C．(n-m+1)*m D．n*m12．已知串S="aaab",其Next数组的元素值依次为A．0、1、2、3 B．1、1、2、3 C．1、2、1、1 D．1、2、3、1 13．串"ababaaababaa" 的next数组为A．011234223456 B．012121111212 C．0123012322345 D．012345678999 14．字符串"ababaabab" 的nextval 为A．(0,1,0,1,0,0,0,1,1) B．(0,1,0,1,0,1,0,1,1)C．(0,1,0,1,0,2,1,0,1) D．(0,1,0,1,0,4,1,0,1)15．二维数组A[10][20]采用按行为主序的存储方式，每个元素占4个存储单元，若A[0][0]的存储地址为300，则A[8][10]的地址为A．660 B．732 C．980 D．113216．二维数组A[5][6]采用按列为主序的存储方式，每个元素占3个存储单元，若A[0][0]的存储地址是100，则A[4][3]的存储地址是A．157 B．166 C．169 D．18117．二维数组A按行优先顺序存储，其中每个元素占1个存储单元。

数据结构习题精编：串和数组一、选择题1．下面关于串的的叙述中，不正确的是A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2．下面关于串的的叙述中，正确的是A．空串就是空白串B．串相等指的是串的长度相等C．串的长度必须大于零D．串是一种特殊的线性表3．字符串是一种特殊的线性表，它与一般线性表的区别是A．字符串是一种线性结构B．字符串可以进行复制操作C．字符串可以顺序存储也可以链式存储D．字符串由字符构成并且通常作为整体参与操作4．串s="Data Structure"中长度为3的子串的数目是A．9B．11C．12D．145．若串S="software"，则S的子串的数目是A．8 B．35 C．36 D．376．已知串S= "string"，T="this"，执行运算StrLength(StrCopy(S,T))的结果是A．2 B．4 C．6 D．107．若串S="SCIENCESTUDY"，则调用函数StrCopy(P,SubString(S,1,7))后得到A．P="STUDY" B．P="SCIENCE" C．S="STUDY" D．S="SCIENCE" 8．若字符串采用链式存储，每个字符占用一个字节，每个指针在占用四个字节，则该字符串的存储密度为A．20%B．25%C．50%D．75%9．为查找某一特定单词在文本中出现的位置，可应用的串运算是A．串联接B．求子串C．串比较D．子串定位10．当目标串的长度为n，模式串的长度为m时，朴素的模式匹配算法最好情况下字符的比较次数A．m B．n C．n-m D．n+m11．当目标串的长度为n，模式串的长度为m时，朴素的模式匹配算法最坏情况下字符的比较次数A．m B．n C．(n-m+1)*m D．n*m12．已知串S="aaab",其Next数组的元素值依次为A．0、1、2、3 B．1、1、2、3 C．1、2、1、1 D．1、2、3、1 13．串"ababaaababaa" 的next数组为A．011234223456 B．012121111212 C．0123012322345 D．012345678999 14．字符串"ababaabab" 的nextval 为A．(0,1,0,1,0,0,0,1,1) B．(0,1,0,1,0,1,0,1,1)C．(0,1,0,1,0,2,1,0,1) D．(0,1,0,1,0,4,1,0,1)15．二维数组A[10][20]采用按行为主序的存储方式，每个元素占4个存储单元，若A[0][0]的存储地址为300，则A[8][10]的地址为A．660 B．732 C．980 D．113216．二维数组A[5][6]采用按列为主序的存储方式，每个元素占3个存储单元，若A[0][0]的存储地址是100，则A[4][3]的存储地址是A．157 B．166 C．169 D．18117．二维数组A按行优先顺序存储，其中每个元素占1个存储单元。

【课后习题】第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．下面关于串的叙述中，哪一个是不正确的？（B）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2．串的长度是指(A)A.串中包含的字符个数B.串中包含的不同字符个数C.串中除空格以外的字符个数D.串中包含的不同字母个数3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（C）A．求子串B．联接C．模式匹配D．求串长4．设主串的长度为n，模式串的长度为m，则串匹配的KMP算法时间复杂度是(C)。

A.O(m)B.O(n)C.O(n+m)D.O(n×m)5.串也是一种线性表，只不过(A)。

A.数据元素均为字符B.数据元素是子串C.数据元素数据类型不受限制D.表长受到限制6.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主进行存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（B）。

A.13B.33C.18D.407.有一个二维数组A[1..6,0..7]，每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组占用的存储空间大小是（D）个字节。

A.48B.96C.252D.2888.设有数组A[1..8,1..10]，数组的每个元素占3字节，数组从内存首地址BA开始以列序为主序顺序存放，则数组元素A[5，8]的存储首地址为(B)。

A.BA+141B.BA+180C.BA+222D.BA+2259.稀疏矩阵的三元组存储表示方法(B)A.实现转置操作很简单，只需将每个三元组中行下标和列下标交换即可B.矩阵的非零元素个数和位置在操作过程中变化不大时较有效C.是一种链式存储方法D.比十字链表更高效10.用十字链表表示一个稀疏矩阵，每个非零元素一般用一个含有(A)域的结点表示。

A.5B.4C.3D.2二、填空题1.一个串的任意连续字符组成的子序列称为串的子串，该串称为主串。

数据结构串和数组试题及答案一、填空题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. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的行下标、列下标和元素值。

10.求下列广义表操作的结果：（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） ;二、单选题（ B ）1. 串是一种特殊的线性表，其特殊性体现在：Ａ．可以顺序存储Ｂ．数据元素是一个字符Ｃ．可以链式存储Ｄ．数据元素可以是多个字符（ B ）2. 设有两个串p和q，求q在p中首次出现的位置的运算称作：Ａ．连接Ｂ．模式匹配Ｃ．求子串Ｄ．求串长（ D ）3.设串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))的结果串是：Ａ．BCDEF Ｂ．BCDEFG Ｃ．BCPQRST Ｄ．BCDEFEF 解：con(x,y)返回x和y串的连接串，即 con(x,y)＝‘ABCDEFGPQRST’；subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，则subs(s1, 2, len(s2))＝subs(s1, 2, 5)=’ BCDEF’; subs(s1,len(s2), 2)＝subs(s1, 5, 2)=’ EF’;所以con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))＝con(’BCDEF’, ’ EF’)之连接，即BCDEFEF（ A ）4. 〖01年计算机系考研题〗假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为。

数据结构第四章（串）考试题目第四章串一单项选择题：1．下列那些为空串（）A）S=“ ” B）S=“”C）S=“φ” D）S=“θ”2．S1=“ABCD”，S2=“CD”则S2在S3中的位置是（）A）1 B）2 C）3D）43.假设S=“abcaabcaaabca”，T=“bca”，Index (S,T,3) 的结果是（）A）2 B）6 C）11 D）04.在串中，对于SubString(&Sub,S,pos,len)基本操作，pos和len的约束条件是（）A）0<pos<strlength(s)+1且1<=len<=strlength(s)-pos+1< p="">B）0<pos<strlength(s)+1且0<=len<=strlength(s)-pos-1< p="">C）1<=pos<=StrLength(S) 且0<=len<=StrLength(S)-pos+1 D）1<=pos<=StrLength(S) 且1<=len<=StrLength(S)-pos-15. 串是一种特殊的线性表，其特殊性体现在( )。

A．可以顺序存储B. 数据元素是一个字符C．可以链接存储D. 数据元素可以是多个字符6. 串是( )。

A．少于一个字母的序列B. 任意个字母的序列C．不少于一个字符的序列D. 有限个字符的序列7. 串的长度是( )。

A．串中不同字母的个数B. 串中不同字符的个数C．串中所含的字符的个数D. 串中所含字符的个数，且大于08. 设有S1=…ABCDEFG?，S2=…PQRST?，函数con(x，y)返回x和y串的连接串，subs(I，j)返回串S的从序号I的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(S1，2，len(S2))，subs(S1，len(S2)，2))的结果是( )。

数据结构习题第四章串第四章串一、选择题1．下面关于串的的叙述中，哪一个是不正确的？（）【北方交通大学 2001 一、5（2分）】A．串是字符的有限序列 B．空串是由空格构成的串C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储2 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr (S4,index(S2,‘8’),length(S2)))其结果为（）【北方交通大学 1999 一、5 （25/7分）】A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345E．ABC###G1234 F．ABCD###1234 G．ABC###012343．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串 B．联接 C．匹配 D．求串长【北京邮电大学2000 二、4（20/8分）】【西安电子科技大学1996 一、1 （2分）】4．已知串S=‘aaab’,其Next数组值为（）。

【西安电子科技大学1996 一、7 （2分）】A．0123 B．1123 C．1231 D．12115．串‘ababaaababaa’的next数组为（）。

【中山大学 1999 一、7】A．012345678999 B．012121111212 C．011234223456 D．01230123223456．字符串‘ababaabab’的nextval 为（）A．(0,1,0,1,04,1,0,1) B．(0,1,0,1,0,2,1,0,1)C．(0,1,0,1,0,0,0,1,1) D．(0,1,0,1,0,1,0,1,1 )【北京邮电大学 1999 一、1（2分）】7．模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（），nextval数组的值为（）。

一.串4.3 4.6 4.7 求next函数值二.数组单项选择题1 设有数组A[i][j],数组的每个元素长度为3字节,i=1,2,…,8,j=1,2,…,10,数组从内存首地址BA开始顺序存放.当数组以列为主序存放元素时,元素A[5][8]的存储首地址为[ ]A.BA+141B.BA+180C.BA+222D.BA+2252 以行为主序存储二维数组A[50][100],设每个数据元素占2个存储单元,基地址为10,则LOC(A[4][4])=[ ]A.418B.818C.1010D.10203 设二维数组A[1..m,1..n](即m行n列)按行存储在数组B[1..m*n]中,则二维数组元素A[i][j]在一维数组B中的下标为[ ]A.(i-1)*n+jB. (i-1)*n+j-1C. i*(j-1)D. j*m+i-14 数组A[0..4,1..3,5..7]中含有元素的个数为[ ]A.55B.45C.36D.165对稀疏矩阵进行压缩存储的目的是[ ]A.便于进行矩阵运算B.便于输入和输出C.节省存储空间D.降低运算的时间复杂度6.设A是n*n的对称矩阵,将A的对角线及对角线上方的元素按以列为主的次序存放在一维数组B[0..n(n+1)/2-1]中.对上述任一元素ai,j(0=<i,j=<n-1,且i=<j)在B中的位置为[ ]A.i(i+1)/2+jB.j(j+1)/2+iC. j(j+1)/2+i-1D. i(i+1)/2+j-1二.判断题1数组可看成是线性结构的一种推广,因此与线性表一样,可以对它进行插入和删除等操作2 稀疏矩阵压缩存储后,必会失去随机存取功能3 二维数组中的每个元素都可以看成是一个一维数组的一维数组.三.填空题1.数组的存储结构采用_______存储方式.2.数组的基本运算有_____和______3.设数组a[50][80]的基地址为2000,每个元素占2个存储单元,若以行为主序顺序存储元素,则元素a[45][68]的存储地址为_____;若以列为主序顺序存储元素,则元素a[45][68]的存储地址为_______.4.用一维数组B按列优先顺序存放带状矩阵A中的非0元素ai,j(0=<i=<n-1,i-2=<j=<i+2),B中下标为8的元素是A中第___行第____列的元素.5.所谓稀疏矩阵,指的是_______6.设n行n列的上三角矩阵A已压缩到一维数组B[0..n*(n+1)/2-1]中,若按行为主序存储,则元素ai,j对应的B中存储位置为____7.n阶对称矩阵a满足a[i][j]=a[j][i],(i,j=1,2,…,n),用一维数组t存储时,t的长度为____,当i=j时,a[i][j]=t[______],当i>j 时,a[i][j]=t[______],当i<j时,a[i][j]=t[_____]参考答案单项选择题1.B2.B3.B4.B5.C6.B判断题1 错误由数组的定义可知,数组可以看作是线性结构的一种推广,但是数组不能进行插入和删除操作,只能对指定元素进行存取和修改操作2 正确稀疏矩阵的压缩存储方法有三元组表表示法和十字链表表示法,这两种方法都不能进行随机存取3 正确由多维数组的定义可知本命题正确填空题1 顺序2 给定一组下标,存取相应的元素;给定一组下标,修改相应的数据元素中某个数据项的值3 9336 88904 1 35 不同元素(或非0元素)的个数远少于元素总数的矩阵6当i=<j时,i(2n-i+1)/2+j-I;当i>j时,存放常数C,n(n+1)/27 n(n+1)/2, i(i+1)/2+j, i(i+1)/2+j, j(j+1)/2+i数组典型例题一、单项选择题[例9-1]下列操作中，( )是数组的基本运算。