第4章-串-数组与广义表-自测题

栈、队列、串、数组和广义表习题一、选择题1 一个栈的输入序列为1234 5，则下列序列中不可能是栈的输出序列的是（）。

A. 2 3 4 1 5B. 5 4 1 3 2C. 2 3 1 4 5D. 1 5 4 3 22 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，p N,若p N是n，则p i是( )。

A. iB. n-iC. n-i+1D. 不确定3 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )A. 1和 5B. 2和4C. 4和2D. 5和14 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。

A． 6 B. 4 C. 3 D. 25 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串 B．联接 C．匹配 D．求串长6 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A. 13B. 33C. 18D. 407 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( )。

A. head(tail(LS))B. tail(head(LS))C. head(tail(head(tail(LS)))D. head(tail(tail(head(LS))))8 模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（ D ），nextval数组的值为（ F ）。

A．0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B．0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2 C．0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D．0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2 E．0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F．0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1二、填空题1 在作进栈运算时应先判别栈是否_(1)_;在作退栈运算时应先判别栈是否_(2)_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3)_。

考研真题精选一、选择题1．下面关于串的的叙述中，哪一个是不正确的？（）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)))其结果为（）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．求串长4．已知串S=‘aaab’,其next数组值为（）。

A．0123 B．1123 C．1231 D．12115．串‘ababaaababaa’的next数组为（）。

A．012345678999 B．012121111212 C．011234223456 D．0123012322345 6．字符串‘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 )7．模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（），nextval数组的值为（）。

A．0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B．0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2C．0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D．0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2E．0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F．0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 18．若串S=’software’,其子串的数目是（）。

第4章数组和广义表【例4-1】二维数组A的每一个元素是由6个字符组成的串，其行下标i=0，1，…，8，列下标j=1，2，…，10。

若A以行为主序存储元素，A[8][5]的物理地址与当A按列为主序存储时的元素（）的物理地址相同。

设每个字符占一个字节。

A．A[8][5] B．A[3][10] C．A[5][8] D．A[0][9]解：二维数A是一个9行10列的矩阵，即A[9][10]。

按行存储时，A[8][5]是第85个元素存储的元素。

而按列存储时，第85个存储的元素是A[3][10]。

即正确答案为B。

【例4-2】若对n阶对称矩阵A以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组B[n（n+1）/2]中，则在B中确定的位置k的关系为（）。

A．jii+-2)1(*B．ijj+-2)1(*C．jii++2)1(*D．ijj++2)1(*解：如果a ij按行存储，那么它的前面有i-1行，其有元素个数为：1+2+3+…+（i-1）=i（i-1）/2。

同时它又是所在行的第j列，因此它排列的顺序还得加上j，一维数组B[n(n+1)/2]中的位置k与其下标的关系是：jii+-2)1(*。

因此答案为A。

【例4-3】已知n阶下三角矩阵A，按照压缩存储的思想，可以将其主对角线以下所有元素（包括主对角线上元素）依次存放于一维数组B中。

请写出从第一列开始以列序为主序分配方式时在B中确定元素a ij的存放位置的公式。

解：如果a ij按列存储，那么它的前面有j-1列，共有元素：n+(n-1)+(n-2)+ …+[n-(j-2)]=(j-1)*n-2)1)(2(--jj而它又是所在列的第i行，因此在它前的元素个数还得加上i。

因此它在一维数组B中的存储顺序为：(j-1)*n-2)1)(2(--jj+i【例4-4】已知广义表L=((x,y,z),a,(u,t,w))，从L表中取出的原子项ASCII码最大的运算是（）。

习题四参考答案一、选择题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 )域的结点表示。

一、填空题1．通常采用___________存储结构来存放数组。

对二维数组可有两种存储方法：一种是以___________为主序的存储方式，另一种是以___________为主序的存储方式。

2. 用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j] (1≤i≤n,i-2≤j≤i+2),B 中的第8个元素是A 中的第_ _行，第_ _列的元素。

3．设n行n列的下三角矩阵A已压缩到一维数组B[1..n*（n+1）/2]中，若按行为主序存储，则A[i,j]对应的B中存储位置为_______。

4. 所谓稀疏矩阵指的是_ 。

5. 广义表简称表，是由零个或多个原子或子表组成的有限序列，原子与表的差别仅在于____ 。

为了区分原子和表，一般用 ____表示表，用 _____表示原子。

一个表的长度是指 __，而表的深度是指__ __6、设数组a[1..50，1..80]的基地址为2000，每个元素占2个存储单元，若一行序为主序顺序存储，则元素a[45，68]的存储地址为；若以列序为主序存储，则元素a[45，68]的存储地址为。

7、有一个8ⅹ8的下三角矩阵A，若采用行序为主序顺序存储于一维数组a[1..n]，则n的值为。

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

9、已知广义表A=（（（a））），则A的表头为：，A的表尾为：。

10、求下列广义表操作的结果：（1）Head ((a,b),(c,d)) == ; //头元素不必加括号（2）Head（Tail((a,b),(c,d))）== ;（3）Head（Tail（Head((a,b),(c,d))））== ;（4）Tail(Head(Tail((a,b),(c,d))))== ;11、设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j从0到3 ，则二维数组W的数据元素共占用＿_____＿个字节。

第4章 数组和广义表 自测卷答案 姓名 班级一、填空题1. 假设有二维数组A 6×8，每个元素用相邻的6个字节存储，存储器按字节编址。

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

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

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

4.求下列广义表操作的结果：（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 ） ;二、单选题（ A ）1.假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为 。

栈、队列、串、数组和广义表习题一、选择题1 一个栈的输入序列为1234 5，则下列序列中不可能是栈的输出序列的是（ B ）。

A. 2 3 4 1 5B. 5 4 1 3 2C. 2 3 1 4 5D. 1 5 4 3 22 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，p N,若p N是n，则p i是( D )。

A. iB. n-iC. n-i+1D. 不确定3 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( B )A. 1和 5B. 2和4C. 4和2D. 5和14 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( C )。

A． 6 B. 4 C. 3 D. 25 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ C ）A．求子串 B．联接 C．匹配 D．求串长6 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ B ）。

A. 13B. 33C. 18D. 407 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( C )。

A. head(tail(LS))B. tail(head(LS))C. head(tail(head(tail(LS)))D. head(tail(tail(head(LS))))8 模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（ D ），nextval数组的值为（ F ）。

A．0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B．0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2 C．0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D．0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2 E．0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F．0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1二、填空题1 在作进栈运算时应先判别栈是否_(1)满_;在作退栈运算时应先判别栈是否_(2)空_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3)n_。

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、5章串、数组和广义表习题1．选择题（1）串是一种特殊的线性表，其特殊性体现在（）。

A．可以顺序存储B．数据元素是一个字符C．可以链式存储D．数据元素可以是多个字符（2）串下面关于串的的叙述中，（）是不正确的？A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储（3）串“ababaabab”的next为（）。

A．010104101 B．011234234 C．011232231 D．010101011 （4）串的长度是指（）。

A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数（5）假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（）。

A．808 B．818 C．1010 D．1020（6）设有数组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（7）A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N(N+1)/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（）。

A．i(i-1)/2+j B．j(j-1)/2+i C．i(j-i)/2+1 D．j(i-1)/2+1（8）广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为（）。

A．(g) B．(d) C．c D．d（9）广义表((a,b,c,d))的表头是（），表尾是（）。

A．a B．( ) C．(a,b,c,d) D．(b,c,d)（10）设广义表L=((a,b,c))，则L的长度和深度分别为（）。

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章（数组和广义表）作业参考答案一、单项选择题1.将一个A[1..100，1..100]的三对角矩阵，按行优先压缩存储到一维数组B[1‥298]中，A 中元素A[66][65]在B数组中的位置K为（C ）。

A. 198B. 197C. 195D. 1962.广义表（a,(b,c),d,e）的表头为（ A ）。

A. aB. a,(b,c)C. (a,(b,c))D. (a)3.在三对角矩阵中，非零元素的行标i和列标j的关系是（ A ）。

A. |i-j|≤1B. i>jC. i==jD. i<j4.广义表L=（a，（b，c）），进行Tail（L）操作后的结果为（ D ）。

A. cB. b，cC.（b，c）D.（（b，c））5.设二维数组A[1..m,1..n]（即m行n列）按行存储在数组B[1..m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为（ D ）。

A. j*m+i-1B. (i-1)*n+j-1C. i*(j-1)D. (i-1)*n+j6.广义表(( ),( ),( ))的深度为（ C ）。

A. 0B. 1C. 2D. 37.假设以行序为主序存储二维数组A[0..99,0..99]，设每个数据元素占2个存储单元，基地址为10，则LOC（A[4][4]）=（ C ）。

A. 1020B. 1010C. 818D. 8088.已知广义表A=((a,b),(c,d))，则head(A)等于（ A ）。

A. (a,b)B. ((a,b))C. a,bD. a9.已知一个稀疏矩阵的三元组表如下：(1，2，3)，(1，6，1)，(3，1，5)，(3，2，-1)，(4，5，4)，(5，1，-3)则其转置矩阵的三元组表中第3个三元组为（ C ）。

A. (2，3，-1)B. (3，1，5)C. (2，1，3)D. (3，2，-1)10.广义表（(b,c),d,e）的表尾为（ C ）。

第四章串和数组一．选择题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中每一个字符出现的次数。

第一章概论一、选择题1、研究数据结构就是研究（D ）。

A. 数据的逻辑结构B. 数据的存储结构C. 数据的逻辑结构和存储结构D. 数据的逻辑结构、存储结构及其基本操作（研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作）2、算法分析的两个主要方面是（ A ）。

A. 空间复杂度和时间复杂度B. 正确性和简单性C. 可读性和文档性D. 数据复杂性和程序复杂性3、具有线性结构的数据结构是（ D ）。

（线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素，有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继）（链表、栈、队列、数组、串）A. 图B. 树C. 广义表（线性表的推广）D. 栈4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B ）等5个特性。

A. 可执行性、可移植性和可扩充性B. 可执行性、有穷性和确定性C. 确定性、有穷性和稳定性D. 易读性、稳定性和确定性5、下面程序段的时间复杂度是（ C ）。

for(i=0;i<m;i++)for(j=0;j<n;j++)a[i][j]=i*j;A. O(m2)B. O(n2)C. O(m*n)D. O(m+n)6、算法是（D ）。

为了解决某一问题而规定的一个有限长的操作序列A. 计算机程序B. 解决问题的计算方法C. 排序算法D. 解决问题的有限运算序列7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（C ）。

A. O(n)B. O(nlog2n)C. O(n2)D. O(log2n)8、下面程序段的时间复杂度为（ C ）。

i=1;while(i<=n)i=i*3;A. O(n)B. O(3n)C. O(log3n)D. O(n3)9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（B ）和运算等的学科。

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

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.设数组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）;二、单选题（每小题1分，共15分）（ 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.假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为 。

第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。

【课后习题】第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.一个串的任意连续字符组成的子序列称为串的子串，该串称为主串。

第4～5章串和数组自测卷答案姓名班级题号一二三四五总分题分20 15 20 15 30 100得分一、填空题（每空1分，共20分）1. 不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串。

2. 设S=“A;/document/”，则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.设数组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) ; 是一种特殊的线性表，其特殊性体现在：Ａ．可以顺序存储Ｂ．数据元素是一个字符Ｃ．可以链式存储Ｄ．数据元素可以是多个字符（ 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.假设有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))的结果是( )。

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

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

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

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

A. 连接B. 模式匹配C. 求子串D. 求串长5．设串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. BCDEFB. BCDEFGC. BCPQRSTD. BCDEFEF6．设串的长度为n，则它的子串个数为 C 。

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’,其长度是_14___。

4.3 判断题1．串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串中符构成的有限序列。

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

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

（对）4．设模式串的长度为m，目标串的长度为n；当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价也可能会更为节省。