数据结构课后习题(第4-5章).doc

【课后习题】第章 ?网络工程2010级（ ）班 学号： 姓名： 题 号 一 二 三 四 总分 得 分 一、填空题 串有三种机内表示方法： 、 和 ，其中前两种属于顺序存储结构，第三种属于 。 若n为主串长度，m为子串长度，则串的BF（朴素）匹配算法最坏的情况下需要比较字符的总次数为 ,T(n)= 。 是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串称为S的 。 设数组a[1…50, 1…60]的基地址为1000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[32,58]的存储地址为 。 对于数组，比较适于采用 结构够进行存储。 广义表的深度是指_______。 将一个的三对角矩阵，按行优先存入一维数组B[297]中，A中元素在B数组中的位置k为 。注意：ai,j的k为 2(i-1)+j-1,(i=1时j=1,2;1i=n时,j=i-1,i,i+1) 。 ????? ???????????称为空串；??? 称为空白串。 求串T在主串S中首次出现的位置的操作是?? ??? 称为目标串，??? 称为模式。对称矩阵的下三角元素a[i,j]，存放在一维数组V的元素V[k]中，k与i，j的关系是：k= ???????? 。 在n维数组中每个元素都受到?????????个条件的约束。 同一数组中的各元素的长度????????? 。稀疏矩阵中有n个非零元素，则其三元组有????????? 行。 求下列广义表操作的结果：GetHead【((a,b),(c,d))】=== ; （2） GetHead【GetTail【((a,b),(c,d))】】=== ;（3） GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== ;（4） GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== ; 广义表(”，否则打“(”。每题1分，共10分) 题号 1 2 3 4 5 6 7 8 9 10 答案 　 　 　 　 　 　 　 　 　 串是字符的有限序列?。????? 串与线性表的运算有所不同，是以“串的整体”作为操作对象。 空串是由空格构成的串。 如果一个串中的所有字符均在另一个串中出现，则说明前者是后者的子串 ?串既可以采用顺序存储，也可以采链式存储。 数组的顺序存储结构，有行（低地址）优先和列（高地址）优先两种不同的顺序。 具备压缩条件的矩阵有：对称矩阵，对角矩阵，稀疏矩阵等。 任何一个非空的广义表，表头可能是原子，也可能是列表；但表尾一定是列表； 三元组顺序表又称有序的双下标法，它可以随机存取某一行中的非零元素。 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算 三、单项选择 1 2 3 4 5 6 7 8 9 10 11 12 答案 题号 13 14 15 16 17 18 19 20 21 22 23 24 答案 　 　 　 　 　 　 　 　 　 串是一种特殊的线性表，其特殊性体现在：（???? ）Ａ．可以顺序存储?????? Ｂ．数据元素是一个字符????? Ｃ．可以链式存储??????? Ｄ．数据元素可以是多个字符 设串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??????? Ｄ．BCDEFEFA)连接 B)模式匹配 C) 求子串 D)求串长 如下是一个稀疏矩阵的三元组法存储表示和基于此表示所得出的相关叙述A)仅I B)I和II C)仅III D)全部 广义表((a),a)的表头和表尾分别是（ )。 A) a ，((a)) B) (a) ，(a) C) b，(a)