C.1≤i≤n D.1≤i≤n+1
9. 字符串采用结点大小为1的链表作为其存储结构，是指（ ）。
A.链表的长度为1
B.链表中只存放1个字符 C.链表的每个链结点的数据域中不仅只存放了一个字符 D.链表的每个链结点的数据域中只存放了一个字符 二、填空题
1. 计算机软件系统中，有两种处理字符串长度的方法：一种是___________，第二种是___________________。
2. 两个字符串相等的充要条件是_____________________和___________________。 3. 设字符串S1= “ABCDEF”，S2= “PQRS”，则运算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值为___________________。
4. 串是指___________________。
5. 空串是指___________________，空格串是指___________________。 三、算法设计题
1. 设有一个长度为s的字符串，其字符顺序存放在一个一维数组的第1至第s个单元中（每个单元存放一个字符）。现要求从此串的第m个字符以后删除长度为t的子串，m 习题3参考答案 一、单项选择题 1．B 2．D 3．C 4．D 5．B 6．C 7．D 8．C 9．D 二、填空题 1. 固定长度，设置长度指针 2. 两个串的长度相等，对应位置的字符相等 3. “BCDEDE” 4. 含n个字符的有限序列 （n≥0） 5. 不含任何字符的串，仅含空格字符的字符串 三、算法设计题 1．算法描述为： int delete(r,s,t,m) //从串的第m个字符以后删除长度为t的子串 char r[ ]; int s,t,m; { int i,j; for(i=1;i<=m;i++) r[s+i]=r[i]; for(j=m+t-i;j<=s;j++) r[s-t+j]=r[j]; return (1); } //delete 2．算法思想为： （1）链表s中取出一个字符；将该字符与单链表t中的字符依次比较； （2）当t中有与从s中取出的这个字符相等的字符，则从t中取下一个字符重复以上比较； （3）当t中没有与从s中取出的这个字符相等的字符，则算法结束。 设单链表类型为LinkList；注意，此时类型 LinkList中的data成分为字符类型。 LinkString find(s,t) LinkString *s, *t; { LinkString *ps, *pt; ps=s; while(ps!=NULL) { pt=t; while((pt!=NULL)&&(ps->data!=pt->data)) pt=pt->next; if(pt= =NULL) ps=NULL; else { ps=ps->next; s=ps; } } return s; } //find 习题4 一、单项选择题 1. 设二维数组A[0…m-1][0…n-1]按行优先顺序存储在内存中，第一个元素的地址为p，每个元素占k个字节，则元素aij的地址为（ ）。 A.p +[i*n+j-1]*k B.p+[(i-1)*n+j-1]*k C.p+[(j-1)*n+i-1]*k D.p+[j*n+i-1]*k 2. 已知二维数组A10×10中，元素a20的地址为560，每个元素占4个字节，则元素a10 的地址为（ ）。 A.520 B.522 C.524 D.518 3. 若数组A[0…m][0…n]按列优先顺序存储，则aij地址为（ ）。 A.LOC(a00)+[j*m+i] B. LOC(a00)+[j*n+i] C.LOC(a00)+[(j-1)*n+i-1] D. LOC(a00)+[(j-1)*m+i-1] 4. 若下三角矩阵An×n，按列顺序压缩存储在数组Sa[0…(n+1)n/2]中，则非零元素aij 的地址为（ ）。（设每个元素占d个字节） (j?2)(j?1)+i-1]*d 2(j?2)(j?1)B. [(j-1)*n-+i]*d 2(j?2)(j?1)C．[(j-1)*n-+i+1]*d 2(j?2)(j?1)D．[(j-1)*n-+i-2]*d 2A. [(j-1)*n-5. 设有广义表D=(a,b,D)，其长度为（ ），深度为（ ）。 A.无穷大 B.3 C.2 D.5 6. 广义表A=（a），则表尾为（ ）。 A.a B.(( )) C.空表 D.(a) 7. 广义表A=((x,(a,B)),(x,(a,B),y))，则运算head(head(tail(A)))的结果为（ ）。 A.x B.(a,B) C.(x,(a,B)) D.A 8. 下列广义表用图来表示时，分支结点最多的是（ ）。 A.L=((x,(a,B)),(x,(a,B),y)) B.A=(s,(a,B)) C.B=((x,(a,B),y)) D.D=((a,B),(c,(a,B),D) 9. 通常对数组进行的两种基本操作是（ ）。 A.建立与删除 B.索引和修改 C.查找和修改 D.查找与索引 10. 假定在数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数为（ ）。 A.80 B.100 C.240 D.270 11. 数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（ ）。 A.SA+141 B.SA+144 C.SA+222 D.SA+225 12. 稀疏矩阵一般的压缩存储方法有两种，即（ ）。 A.二维数组和三维数组 B.三元组和散列 C.三元组和十字链表 D.散列和十字链表 13. 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（ ）。 A.正确 B.不正确 14. 一个广义表的表头总是一个（ ）。 A.广义表 B.元素 C.空表 D.元素或广义表 15. 一个广义表的表尾总是一个（ ）。 A.广义表 B.元素 C.空表 D.元素或广义表 16. 数组就是矩阵，矩阵就是数组，这种说法（ ）。 A.正确 B.错误 C.前句对，后句错 D.后句对 二、填空题 1. 一维数组的逻辑结构是______________，存储结构是______________；对于二维或多维数组，分为______________和______________两种不同的存储方式。 2. 对于一个二维数组A[m][n]，若按行序为主序存储，则任一元素A[i][j]相对于A[0][0]的地址为______________。 3. 一个广义表为(a,(a,b),d,e,((i,j),k))，则该广义表的长度为_____，深度为_____。 4. 一个稀疏矩阵为 ? 2 0 ? ，则对应的三元组线性表为_____________。 0 0 5. 一个n×n的对称矩阵，如果以行为主序或以列为主序存入内存，则其容量为______________。 6. 已知广义表A=((a,b,c),(d,e,f))，则运算head(tail(tail(A)))=____________。 7. 设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a85的地址为______________。 8. 已知广义表Ls=(a,(b,c,d),e)，运用head和tail函数取出Ls中的原子b的运算是______________。 ?3000????00?15???0000??9. 三维数组R[c1…d1,c2…d2,c3…d3]共含有______________个元素。（其中：c1≤d1,c2 ≤d2,c3≤d3） 10. 数组A[1…10，-2…6，2…8]以行优先的顺序存储，设第一个元素的首地址是100，每个元素占3个存储长度的存储空间，则元素A[5，0，7]的存储地址为______________。 三、判断题 1. 数组可看作基本线性表的一种推广，因此与线性表一样，可以对它进行插入、删除等操作。（ ） 2. 多维数组可以看作数据元素也是基本线性表的基本线性表。（ ） 3. 以行为主序或以列为主序对于多维数组的存储没有影响。（ ） 4. 对于不同的特殊矩阵应该采用不同的存储方式。（ ） 5. 采用压缩存储之后，下三角矩阵的存储空间可以节约一半。（ ） 6. 在一般情况下，采用压缩存储之后，对称矩阵是所有特殊矩阵中存储空间节约最多的。（ ） 7. 矩阵不仅是表示多维数组，而且是表示图的重要工具。（ ） 8. 距阵中的数据元素可以是不同的数据类型。（ ） 9. 矩阵中的行列数往往是不相等的。（ ） 10. 广义表的表头可以是广义表，也可以是单个元素。（ ） 11. 广义表的表尾一定是一个广义表。（ ） 12. 广义表的元素可以是子表，也可以是单元素。（ ） 13. 广义表不能递归定义。（ ） 14. 广义表实际上是基本线性表的推广。（ ） 15. 广义表的组成元素可以是不同形式的元素。（ ） 习题4参考答案 一、单项选择题 1. A 2. A 3. A 4. B 5. BA 6. C 7. A 8. A 9. C 10. C 11. C 12. C 13. B 14. D 15.A 16.B 二、填空题 1. 线性结构，顺序结构，以行为主序，以列为主序 2. i×n+j个元素位置 3. 5，3 4.（（0，2，2），（1，0，3），（2，2，-1），（2，3，5）） 5. n×(n+1)/2 6. e 7. 41
相关推荐：
loading