习题1.设二维数组A[0…m-1][0…n-1]按行优先顺序存储在内存中，第一个元素的地址为p，每个元素占k个字节，则元素aij的地址为（）。A.p+[i*n+j-1]*kB.p+[(i-1)*n+j-1]*kC.p+[(j-1)*n+i-1]*kD.p+[j*n+i-1]*k2.已知二维数组A10×10中，元素a20的地址为560，每个元素占4个字节，则元素a10的地址为（）。A.520B.522C.524D.5183.若数组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.设有广义表D=(a,b,D)，其长度为（），深度为（）。A.无穷大B.3C.2D.55.广义表A=（a），则表尾为（）。A.aB.(())C.空表D.(a)6.广义表A=((x,(a,B)),(x,(a,B),y))，则运算gethead(gethead(gettail(A)))的结果为（）。A.xB.(a,B)C.(x,(a,B))D.A7.一个广义表的表头总是一个（）。A.广义表B.元素C.空表D.元素或广义表8.一个广义表的表尾总是一个（）。A.广义表B.元素C.空表D.元素或广义表9.一维数组的逻辑结构是______________，存储结构是______________；对于二维或多维数组，分为______________和______________两种不同的存储方式。10.对于一个二维数组A[m][n]，若按行序为主序存储，则任一元素A[i][j]相对于A[0][0]的地址为______________。11.一个稀疏矩阵为，则对应的三元组线性表为_____________。判断题1.数组可看作基本线性表的一种推广，因此与线性表一样，可以对它进行插入、删除等操作。（）2.多维数组可以看作数据元素也是基本线性表的基本线性表。（）3.以行为主序或以列为主序对于多维数组的存储没有影响。（）4.对于不同的特殊矩阵应该采用不同的存储方式。（）5.采用压缩存储之后，下三角矩阵的存储空间可以节约一半。（）6.在一般情况下，采用压缩存储之后，对称矩阵是所有特殊矩阵中存储空间节约最多的。（）7.距阵中的数据元素可以是不同的数据类型。（）8.广义表的表头可以是广义表，也可以是单个元素。（）9.广义表的表尾一定是一个广义表。（）10.广义表的元素可以是子表，也可以是单元素。（）11.广义表不能递归定义。（）12.广义表的组成元素可以是不同形式的元素。（）算法设计题假定数组A[n]的n个元素中有多个零元素，编写算法将A中所有的非零元素依次移到A的前端。第四章习题参考答案一、单项选择题1．B2．D3．C4．D5．B6．C7．D8．C9．D二、填空题1.两个串的长度相等，对应位置的字符相等2.“BCDEDE”3.含n个字符的有限序列（n≥0）4.不含任何字符的串，仅含空格字符的字符串三、算法设计题1．算法描述为：intdelete(r,s,t,m)//从串的第m个字符以后删除长度为t的子串charr[];ints,t,m;{inti,j;for(i=1;i<=m;i++)r[s+i]=r[i];for(j=m+t+1;j<=s;j++)r[s-t+j]=r[j];return(1);}//delete2．算法思想为：（1）链表s中取出一个字符；将该字符与单链表t中的字符依次比较；（2）当t中有与从s中取出的这个字符相等的字符，则从t中取下一个字符重复以上比较；（3）当t中没有与从s中取出的这个字符相等的字符，则算法结束。设单链表类型为LinkList；注意，此时类型LinkList中的data成分为字符类型。LinkStringfind(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;}}returns;}//find