数据结构第4—5章数组广义表自测卷空题.docx

第4〜5章 串和数组自测卷姓名 班级一、填空题(每空1分，共20分)称为空串；称为空白串。
题号
—
二
三
四
五
总分
题分
20
15
20
15
30
100
得分

1. 设 S= "A;/document/Mary.doc”,则 stden(s)=, aT 的字符定位的位置为。
4. 子串的定位运算称为串的模式匹配；称为目标串，称为模式。
5. 设目标T=" abccdcdccbaa",模式P= "cdcc”，则第次匹配成功。
6. 若n为主串长，m为子串长，则串的古典匹配算法最坏的情况下需要比较字符的总次数为。
7. 假设有二维数组&X8,每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置
(基地址)为1000,则数组A的体积(存储量)为；末尾元素A”的第一个字节地址为；若按行存储时，元素A“的第一个字节地址为;若按列存储时，元素A,的第一个字节地址为o设数组a[l-60,l-70]的基地址为2048,每个元素占2个存储单元，若以列序为主序顺序存储，则元素
a[32,58]的存储地址为o三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的、和。
8. 求下列广义表操作的结果：
(1) GetHead |((a,b),(c,d))] ===；
(2) GetHead [GetTaO [((a,b),(c,d))]] ===;
(3) GetHead [GetTail IGetHead [((a,b),(c,d))]]J ===;
(4) GetTail [GetHead [GetTaU [«a,b),(c,d))]J] ===;二、单选题(每小题1分，共15分)
()1.串是一种特殊的线性表，其特殊性体现在：
A.可以顺序存储B.数据元素是一个字符C.可以链式存储D.数据元素可以是多个字符
()2.设有两个串p和q,求q在p中首次出现的位置的运算称作：
A.连接 B.模式匹配C.求子串 D.求串长
()3.设串 sl = ' ABCDEFG' , s2=，PQRST',函数 con(x,y)返回 x和y 串的连接串，subs(s,i,j)返回串s的从序号i开始的j个字符组成的子串,len(s)返回串s的长度，则con(subs(sl, 2, len(s2)), subs(sl, len(s2), 2))的结果串是：
A. BCDEF B . BCDEFG C. BCPQRST D. BCDEFEF
()4.假设有60行70列的二维数组a［l-60,l-70］以列序为主序顺序存储，其基地址为10000,每 个元素占2个存储单元，那么第32行第58列的元素a［32,58］的存储地址为。(无第。行第0列元素)A 16902 B . 16904 C . 14454 D.答案 A,B,C 均不对()5.设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分(如「％ ,_右图所示)按行序存放在一维数组B［l,n(n-l)/2］中，对下三角部分中任一。。
元素跖Q>,2 …a,,.n_从供选择的答案中，选出应填入下面叙述?内的最确切的解答,把相应编号写在答卷的对应栏
内。
有一个二维数组A,行下标的范围是0到8,列下标的范围是1到5,每个数组元素用相邻的4个字节 存储。存储器按字节编址。假设存储数组元素A［0,l］的第一个字节的地址是0。
存储数组A的最后一个元素的第一个字节的地址是二_。若按行存储，则A［3,5］和A［5J］的第一个字节 的地址分别是B 和C 。若按列存储，则A［7,l］和A「2,4］的第一个字节的地址分别是 D 和 E_o供选择的答案A~E:①28②44③76④92⑤108⑥116⑦132 ⑧176⑨184⑩188答案：A= B= C= D= E=
6. 从供选择的答案中，选出应填入下面叙述二_内的最确切的解答，把相应编号写在答卷的对应栏内。
有一个二维数组A,行下标的范围是1到6,列下标的范围是0到7每个数组元素用相邻的6个字节 存储，存储器按字节编址。那么，这个数组的体积是二_个字节。假设存储数组元素A［l,0］的第一个字 节的地址是0,则存储数组A的最后一个元素的第一个字节的地址是 B 。若按行存储，则A［2,4］的第 一个字节的地址是C 。若按列存储，则A［5,7］的第一个字节的地址是_ D 。
供选择的答案A〜D:① 12(2)66③72④96⑤ 114 ⑥ 120⑦ 156⑧234⑨276⑩282(11)283(12) 288答案：A= B= C= D= E=三、简答题(每小题5分，共15分)
1. KMP算法的设计思想是什么？它有什么优点？
2. 已知二维数组Am>m采用按行优先顺序存放，每个元素占K个存储单元，并且第一个元素的存储地址 为Loc(all),请写出求Loc(aij)的计算公式。如果采用列优先顺序存放呢？
3. 递归算法比非递归算法花费更多的时间，对吗？为什么?
四、计算题(每题5分，共20分)【严题集 4.3①】设 s=' I AM A STUDENT' ,t=' GOOD' ,q=' WORKER', 求 Replace(s/ STUDENT' ,q)和 Concat(SubString(s,6,2), Concat(t^ubString(s,7,8))) oADABBADADA

ADABBADADA
1. 【严题集4.8②】 已知主串s='ADBADABBAABADABBADADA',模式串pat= 写出模式串的nextval函数值，并由此画出KMP算法匹配的全过程。
2. 用三元组表表示下列稀疏矩阵:
0000000000000000
00000000

00000000
00000-2
03000800
03000800

03000800
00000000
00060000
00000000
00009
00()00
(2)
00500
00000
0
0
0
0
00000005
00000005

00000005
00003 0

20000000下列各三元组表分别表示一个稀疏矩阵，试写出它们的稀疏矩阵。
一6 4 6

_4 5 5_
1 2 2

1 1 1
2 1 12

249
3 1 3
(2)
328
44 4

356
5 3 6

_4 3 7_
6 1 16

五、算法设计题(每题10分，共30分)1.【严题集4.12®］编写一个实现串的置换操作Replace(&S,T,V)的算法。
2.【严题集4.10③】写出将字符串反序的递归算法，例字符串为“abcsxw”，反序为“wxscba”【严题集5.18®］试设计一个算法，将数组An中的元素A［0］至A［n-1］循环右移k位，并要求只用一个 元素大小的附加存储，元素移动或交换次数为O(n)附加题：利用 C 的库函数 strlen, strcpy (或 stmcpy)写一个算法 void StrDelete(char *S»int t^nt m),删除串 S中从位置i开始的连续的m个字符。若iXtrien(S),则没有字符被删除；若i+m>strlen(S),则将S中从 位置i开始直至末尾的字符均被删去。
提示：strlen是求串长(length)函数：int strlen(char s); 〃求串的长度
strcpy是串复制(copy)函数：char *strcpy(char to,char from); 〃该函数将串from复制到串to中，并且返 回一个指向串to的开始处的指针。
如有侵权请联系告知删除，感谢你们的配合！