发布时间 : 星期六 文章校本教材各章习题及答案更新完毕开始阅读6ee99662580102020740be1e650e52ea5518ce3a
concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2))) 其结果为（）【北方交通大学 1999 一、5】
A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345 E．ABC###G1234 F．ABCD###1234 G．ABC###01234
3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（） A．求子串 B．联接 C．匹配 D．求串长 【北京邮电大学 2000 二、4】【西安电子科技大学 1996 一、1】
4．已知串S=‘aaab’,其Next数组值为（）。【西安电子科技大学 1996 一、7】 A．0123 B．1123 C．1231 D．1211 5．串‘ababaaababaa’的next数组为（）。【中山大学 1999 一、7】
A．012345678999 B．012121111212 C．011234223456 D．0123012322345 6．字符串‘ababaabab’的nextval 为（）【北京邮电大学 1999 一、1】 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数组的值为（）。【北京邮电大学 1998 二、3】
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
8．若串S=’software’,其子串的数目是（）。【西安电子科技大学 2001 一、2】 A．8 B．37 C．36 D．9
9．设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（）。【中科院计算所 1997 】
A．2n-1
B．n2
C．(n2/2)+(n/2)
D．(n2/2)+(n/2)-1 E. (n2/2)-(n/2)-1 F.其他情况 10．串的长度是指（）【北京工商大学 2001 一、6】 A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数 二、判断题
1．KMP算法的特点是在模式匹配时指示主串的指针不会变小。（ ）【北京邮电大学 2002 一、4 （1分）】
2．设模式串的长度为m,目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（ ）【长沙铁道学院 1998 一、1 (1分)】
3．串是一种数据对象和操作都特殊的线性表。（ ）【大连海事大学 2001 1、L (1分)】 三、填空题
1．空格串是指__(1)__，其长度等于___(2)__。 【西安电子科技大学 2001软件 一、4】 2．组成串的数据元素只能是________。 【中山大学 1998 一、5】
3．一个字符串中________称为该串的子串 。 【华中理工大学 2000 一、3】 4．INDEX（‘DATASTRUCTURE’， ‘STR’）=________。【福州大学 1998 二、4】
5．设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为________。
【重庆大学 2000 一、4】
6．模式串P=‘abaabcac’的next函数值序列为____________________________________。【西安电子科技大学 2001 一、6】 7．字符串‘ababaaab’的nextval函数值为________________________________________。 【北京邮电大学 2001 二、4】 8．设T和P是两个给定的串，在T中寻找等于P的子串的过程称为____，又称P为___。【西安电子科技大学 1998 二、5】
9．两个字符串相等的充分必要条件是_______。 【西安电子科技大学 1999软件 一、1】 10．知U=‘xyxyxyxxyxy’；t=‘xxy’；
ASSIGN（S，U）；
ASSIGN（V，SUBSTR（S，INDEX（s，t），LEN（t）+1））； ASSIGN（m，‘ww’）
求REPLACE（S，V，m）= ________。 【东北大学 1997 一、1】 11．实现字符串拷贝的函数 strcpy为：【浙江大学1999一、5】
void strcpy(char *s , char *t) /*copy t to s*/ { while (________) }
12．下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如 f(\返回1，f(\返回0； 【浙江大学1999一、6】
int f(________)
{int i=0,j=0; while (s[j])(2)________;
for(j--; i 实验题目 编制一个统计特定单词在文本串中出现的次数和位置的程序。 练习题目答案 一、选择题 1.B 二、判断题 1.√ 2.√ 3.√ 三．填空题 1．(1) 由空格字符（ASCII值32）所组成的字符串 (2)空格个数 2．字符 2.E 3.C 4.A 5.C 6.A 7.1D 7.2F 8.B 9.D 10.B 3．任意个连续的字符组成的子序列 4．5 5.O(m+n) 6．01122312 7．01010421 8．(1)模式匹配 (2)模式串 9．两串的长度相等且两串中对应位置的字符也相等。 10．’xyxyxywwy’ 11．*s++=*t++ 或（*s++=*t++）!=‘\\0’ 12．（1）char s[ ] (2) j++ (3) i >= j 第五章 数组和广义表 5.3 总结与提高 5.3.1 主要知识点 1、数组以行为主的存储结构； 2、对称矩阵和三角矩阵压缩存储时的下标变换； 3、三元组表示稀疏矩阵时进行矩阵运算的方法； 4、广义表的特点及存储方法。 5.3.2 典型例题 1、数组元素之间的关系，（） A）是线性的 B）是树形的 C）既是线性的，又是树形的 D）既不是线性的，也不是树形的 由数组的特点可知，答案为D。 2、二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存储时元素（）的起始地址相同。 A）M[2][4] B）M[3][4] C ）M[3][5] D）M[4][4] M为5行6列，在按行存储时，元素M[3][5]的起始地址为((3-0)*6+(5-0))*4=92；在按列存储时，元素M[2][4]的起始地址为((4-0)*5+(2-0))*4=88，元素M[3][4]的起始地址为((4-0)*5+(3-0))*4=92，元素M[3][5]的起始地址为((5-0)*5+(3-0))*4=112，元素M[4][4]的起始地址为((4-0)*5+(4-0))*4=96，答案为B。 3、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是（） A）80 B）100 C）240 D）270 数组A有8行10列，共需单元数=8*10*3=240，答案为C。 4、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a1,1为第一个 元素，其存储地址为1，每个元素占1个地址空间，则a8,5的地址为（） A）13 B）33 C）18 D）40 这里数组下标从1开始，只存储其下三角元素，在a8,5的前面有7行，第1行有1个元素，第2行有2个元素，?，第7行有7个元素，这7行共有(1+7)*7/2=28个元素，在第8行中，a8,5的前面有4个元素，所以，a8,5前有28+4=32个元素，其地址为33，答案为B。 5、广义表（（a，b），c，d）的表头是（），表尾是（） A）a B）b C）（a，b） D）（c，d） 由广义表表头和表尾定义可知，表头为C，表尾为D。 6、广义表（a，（b，c），（（e）））的长度为（） A）1 B）2 C）3 D）4 由广义表定义知，其长度为3，答案为C。 练习题目 1、一个n*n的对称矩阵，如果以行或列为主序放入内存，则容量为（ C ） A）n*n B）n*n/2 C）n*(n+1)/2 D）(n+1)*(n+1)/2 2、对矩阵压缩存储是为了（ D ）。 A）方便运算 B）方便存储 C）提高运算速度 D）减少存储空间 3、二维数组M的元素是5个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到5，列下标j的范围从0到4，M按行存储时元素M[3][2]的起始地址与M按列存储时元素（A） A）M[5][2] B）M[4][4]C）M[5][4] D）M[3][0] 4、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[5][8]的起始地址为（ B ） A）SA+141 B）SA+180 C）SA+222 D）SA+225 5、广义表((a),a)的表尾是（ B ） A）a B）(a) C）( ) D）((a)) 6、广义表（（a，b），（c，d），e）的长度为（ C ） A）1 B）2 C）3 D）4 实验题目 假设稀疏矩阵A采用三元组表表示，编写程序实现该矩阵的快速转置。要求：输入一个稀疏矩阵A，由程序将其转换成三元组表存储；转置后的三元组表，由程序将其转换成矩阵形式后输出。 #include #define MAXSIZE 100 typedef struct { int i,j; int e; }Triple; typedef struct{ Triple data[MAXSIZE+1];