2010数据结构第4—5章串与数组广义表自测题

第4-5章字符串和数组自检卷名类文豪一个第二个三个45总分分配问题2015201530100计分第一，填写空白问题(每个空白1分，共20分)1.称为空字符串。称为空字符串。设定S=a。如果/document/Mary.doc ，则strlen (s)=，/的字符位置位置为。子串的定位操作称为字符串模式匹配。称为目标字符串，称为模式。5.如果设置了目标t= abccdccbaa ，模式p= CDCC ，则主要匹配成功。6.如果n是默认字符串长度，m是子字符串长度，则字符串的经典匹配算法是在最坏的情况下必须比较字符的总次数。7.假设有二维阵列A68，每个阵列存储为相邻的6个字节，存储按字节寻址。如果已知a的起始存储位置(主地址)为1000，则阵列a的卷(存储容量)为：最后元素A57的第一个字节地址为：按行保存时，元素A14的第一个字节地址为：按列保存时，元素A47的第一个字节地址为。8.阵列a 1.60，1.如果70的主地址为2048，每个元素占用两个存储单元，并且按列顺序存储，则元素a32，58的存储地址为。9.三元素组表中的每个节点对应于稀疏矩阵中的非零元素，并包含表示该元素的三个数据项、和。10.查找以下广泛表操作的结果：(1) gethead (a，b)，(c，d)=；(2)getheadgettical(a，b)，(c，d)=；(3) gethead gethead (a，b)，(c，d)=；(4) getticl gethead gettical (a，b)，(c，d)=；二、单一主题(每个问题1分，共15分)()1。字串是反映特殊性的特殊线性表格。A.b .可以按顺序存储数据元素的字符为一个字符C.d .数据元素可以是多个字符()2 .有两个字符串p和q，用于查找q在p中首次出现的位置的运算如下：A.连接b .模式匹配c .搜索字符串d .查找字符串长度()3 .字符串s1=ABCDEFG ，s2=PQRST ，函数con(x，y)返回字符串x和y的连接字符串，subs(s，I，j)返回由字符串s的序列号I开始的j字符组成的子字符串A.bcdef b.bcdefg c.bcpqrsd.bcdef ef()4。具有60行70列的二维数组a 1.60，1.假设70的默认地址为10000，每个元素占用两个存储单位，则第32行58列中的元素a32，58的存储地址为。(零行零列元素无)A.16902b.16900c.144454d .答案A、B和C都是错误的()5。为了节省存储，矩阵a将向下三角形部分(右侧图中所示)依次存储在一维数组B 1，n(n-1)/2中，对于向下三角形部分的任意元素ai，j(Ij)，一维数组B中下标k的值为：A.i (I-1)/2j-1b.i (I-1)/2jC.i (I 1)/2 j-1 d.i (I 1)/2 j6.在可选择的回答中，选择是否需要填写下面的叙述？我最准确的答案是在答卷的对应栏中写下相应的号码。有二维数组a，行下标的范围为0到8，列下标的范围为1到5，每个数组元素存储为相邻的4个字节。存储按字节寻址。假定存储阵列元素A0，1的第一个字节地址为0。存储数组a最后一个元素的第一个字节的地址是a。逐行存储时，A3，5和A5，3的第一个字节地址分别为b和c。按列保存时，A7，1和A2，4的第一个字节地址分别为d和e。可以选择的答案a e:2844761081161321761848答案：a=b=c=d=e=7.在可选择的回答中，选择是否需要填写下面的叙述？我最准确的答案是在答卷的对应栏中写下相应的号码。有二维数组a，行下标的范围为1到6，列下标的范围为0到7，每个数组元素存储为相邻的6个字节，存储按字节寻址。那么这个数组的体积是a字节。假设存储阵列元素A1，0的第一个字节地址为0，则存储阵列A中最后一个元素的第一个字节地址为b。逐行存储时，A2，4的第一个字节地址为c。按列保存时，A5，7的第一个字节地址为d。可以选择的答案a d:12667272114120156234282(11)283(12)288答案：a=b=c=d=e=三、简单的回答(每个问题5分，共15分)1.KMP算法的设计理念是什么？有什么优点？2.二维数组Am，m，根据行优先级，写出了查找Loc(aij)的计算公式，因为每个元素占用k存储单位，并且第一个元素的存储地址为Loc(a11)。可以根据列优先级保存吗？3.递归算法比非递归算法需要更多的时间，对吧？怎么了？四、计算问题(每个问题5分，共20分)1.严格的问题集4.3设置s= I am a student ，t= good ，q= worker ，Replace(s， STUDENT ，q)和concat (substring (s，6，2)，concat (t，substring (s，2)2.严格的问题集4.8已知的订单排序s= adbadabbaabadabbada ，模式字符串pat= adabada .写入模式字符串的nextval函数值，绘制匹配KMP算法的整个过程。3.以三元表的形式表示以下稀疏矩阵：4.以下三个组表分别表示稀疏矩阵，并尝试创建相应的稀疏矩阵：第五，算法设计问题(每个问题10分，共30分)1.严格的问题集4.12创建实现一系列更换操作Replace(S，T，V)的算法