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

第45章 串和数组自测卷姓名 班级一、填空题(每空1分，共20分)称为空串；称为空白串。题号二三四五总分题分2015201530100得分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设数组al-60,l-70的基地址为2048,每个元素占2个存储单元，若以列序为主序顺序存储，则元素a32,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列的二维数组al-60,l-70以列序为主序顺序存储，其基地址为10000,每 个元素占2个存储单元，那么第32行第58列的元素a32,58的存储地址为。(无第。行第0列元素)A. 16902 B . 16904 C . 14454 D.答案 A,B,C 均不对()5.设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分(如 ,_右图所示)按行序存放在一维数组Bl,n(n-l)/2中，对下三角部分中任一。元素跖Q,2 a,.n_从供选择的答案中，选出应填入下面叙述?内的最确切的解答,把相应编号写在答卷的对应栏内。有一个二维数组A,行下标的范围是0到8,列下标的范围是1到5,每个数组元素用相邻的4个字节 存储。存储器按字节编址。假设存储数组元素A0,l的第一个字节的地址是0。存储数组A的最后一个元素的第一个字节的地址是二_。若按行存储，则A3,5和A5J的第一个字节 的地址分别是B 和C 。若按列存储，则A7,l和A2,4的第一个字节的地址分别是 D 和 E_o供选择的答案AE:28447692108116132 176184188答案：A= B= C= D= E=6. 从供选择的答案中，选出应填入下面叙述二_内的最确切的解答，把相应编号写在答卷的对应栏内。有一个二维数组A,行下标的范围是1到6,列下标的范围是0到7,每个数组元素用相邻的6个字节 存储，存储器按字节编址。那么，这个数组的体积是二_个字节。假设存储数组元素Al,0的第一个字 节的地址是0,则存储数组A的最后一个元素的第一个字节的地址是 B 。若按行存储，则A2,4的第 一个字节的地址是C 。若按列存储，则A5,7的第一个字节的地址是_ D 。供选择的答案AD: 12(2)667296 114 120 156234276282(11)283(12) 288答案：A= B= C= D= E=三、简答题(每小题5分，共15分)1. KMP算法的设计思想是什么？它有什么优点？2. 已知二维数组Amm采用按行优先顺序存放，每个元素占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(tubString(s,7,8) oADABBADADAADABBADADA1. 【严题集4.8】 已知主串s=ADBADABBAABADABBADADA,模式串pat= 写出模式串的nextval函数值，并由此画出KMP算法匹配的全过程。2. 用三元组表表示下列稀疏矩阵:0000000000000000000000000000000000000-20300080003000800030008000000000000060000000000000000900()00(2)0050000000000000000005000000050000000500003 020000000下列各三元组表分别表示一个稀疏矩阵，试写出它们的稀疏矩阵。一6 4 6_4 5 5_1 2 21 1 12 1 122493 1 3(2)32844 43565 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中的元素A0至An-1循环右移k位，并要求只用一个 元素大小的附加存储，元素移动或交换次数为O(n)附加题：利用 C 的库函数 strlen, strcpy (或 stmcpy)写一个算法 void StrDelete(char *Sint tnt m),删除串 S中从位置i开始的连续的m个字符。若iXtrien(S),则没有字符被删除；若i+mstrlen(S),则将S中从 位置i开始直至末尾的字符均被删去。提示：strlen是求串长(length)函数：int strlen(char s); 求串的长度strcpy是串复制(copy)函数：char *strcpy(char to,char from); 该函数将串from复制到串to中，并且返 回一个指向串to的开始处的指针。如有侵权请联系告知删除，感谢你们的配合！