数据结构第四、五、六、七章作业答案

第四、五章一、填空题1.不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串。2.设S=“A;/document/Mary.doc”，则strlen(s)=20,“/”的位置为3。3.子串的定位运算称为串的模式匹配；被匹配的主串称为目标串，子串称为模式。4、串的存储方式有顺序存储、堆分配存储和块链存储5、有一个二维数组A[0:8,1:5],每个数组元素用相邻的4个字节存储，存储器按字节编址，假设存储数组元素A[0,1]的地址是100，若按行主顺序存储，则A[3,5]的地址是176和A[5,3]的地址是208。若按列存储，则A[7,1]的地址是128，A[2,4]的地址是216。6、设数组a[1…60,1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为8950。7、三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的行下标、列下标和元素值。8、二维数组A[10][20]采用列序为主方式存储，每个元素占10个存储单元，且A[0][0]的存储地址是2000，则A[6][12]的地址是32609、已知二维数组A[20][10]采用行序为主方式存储,每个元素占2个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的存储地址是116810、已知二维数组A[10][20]采用行序为主方式存储，每个元素占2个存储单元,并且A[0][0]的存储地址是1024,则A[6][18]的地址是130011、两个串相等的充分必要条件是长度相等、对应位置的字符相同。12、二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且A[0][0]的存储地址是200，则A[6][12]的地址是200+（12*10+6）=326。二、单选题1、串是一种特殊的线性表，其特殊性体现在（B）Ａ．可以顺序存储Ｂ．数据元素是一个字符Ｃ．可以链式存储Ｄ．数据元素可以是多个字符2、设有两个串p和q，求q在p中首次出现的位置的运算称作（B）Ａ．连接Ｂ．模式匹配Ｃ．求子串Ｄ．求串长3.设串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))的结果串是（D）Ａ．BCDEFＢ．BCDEFGＣ．BCPQRSTＤ．BCDEFEF4.假设有60行70列的二维数组a[1…60,1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为（A）。（无第0行第0列元素）Ａ．16902Ｂ．16904Ｃ．14454Ｄ．答案A,B,C均不对5、下面关于串的的叙述中，（B）是不正确的。A、串是字符的有限序列B、空串是由空格构成的串C、模式匹配是串的一种重要运算D、串既可以采用顺序存储，也可以采链式存储6.设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B[1,n(n-1)/2]中，对下三角部分中任一元素ai,j(i≤j),在一维数组B中下标k的值是(B)A、i(i-1)/2+j-1B、i(i-1)/2+jC、i(i+1)/2+j-1D、i(i+1)/2+j7.有一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是A个字节。假设存储数组元素A[1,0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是B。若按行存储，则A[2,4]的第一个字节的地址是C。若按列存储，则A[5,7]的第一个字节的地址是D。供选择的答案：A～D：①12②66③72④96⑤114⑥120⑦156⑧234⑨276⑩282（11）283（12）288答案：ABCD=12,10,3,98、以下关于广义表的叙述中,正确的是（A）A)广义表是由0个或多个单元素或子表构成的有限序列B)广义表至少有一个元素是子表C)广义表不能递归定义D)广义表不能为空表nnnnaaaaaaA,2,1,2,21,21,19、设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为(B)。A.i(i-l)/2+jB.j(j-l)/2+iC.j(j-l)/2+i-1D.i(i-l)/2+j-110.设A[n，n]是对称矩阵，将其下三角（包括对角线）以行序存储到一维数组T[n（n+1）/2]中，则:任意一个上三角元素a[i][j]所对应T[k]的下标k是（B）。A.i（i-1）/2+jB.j（j-1）/2+iC.i（j-i）/2+1D.j（i-1）/2+111、常对数组进行的两种基本操作是（C）。A．建立与删除B．索引和修改C．查找和修改D．查找与索引12、就一般情况而言，当（C）时，按行存储的A[I，J]地址与按列存储的A[J，I]地址相等。A．行与列的上界相同B.行与列的下界相同C.行与列的上、下界都相同D.行的元素个数与列的元素个数相同13、二维数组M的成员是6个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要（D①）个字节；M的第8列和第5行共占（②B）个字节。①A．90B．180C．240D．540②A．108B．114C．54D．6014、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是（C）。A．80B．100C．240D．27015、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（C）A．SA+141B．SA+144C．SA+222D．SA+22516、设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（C）A．O(n)B．O(log2n)C．O(1)D．O(n2)17、三、判断题1、（√）子串是主串中任意个连续字符组成的序列。2、（√）广义表(((a),b),c)的表头是((a),b)，表尾是(c)。3、（×）数组元素的下标值越大，存取时间越长4、数组是线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（×）⒋（×）设有两个串p和q，求q在p中首次出现的位置的运算称作求子串。⒌（√）二维数组是其数据元素为线性表的线性表。6、(╳)若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置。7、(╳)若一个广义表的表头为空表，则此广义表亦为空表。8、(╳)用一维数组存储二叉树时，总是以前序遍历存储节点。9、采用堆分配存储串时，串仍以一组地址连续的存储单元存储，但存储空间是在程序执行过程中由动态分配而得到。（√）四、问答题1、已知n阶下三角矩阵A（即当ij时，有aij=0），按照压缩存储的思想，可以将其主对角线以下所有元素(包括主对角线上元素)依次存放于一维数组B中，请写出从第一列开始采用列序为主序分配方式时在B中确定元素aij的存放位置的公式。答：n阶下三角矩阵元素A[i][j]（1=i,j=n,i=j）。第1列有n个元素，第j列有n-j+1个元素，第1列到第j-1列是等腰梯形，元素数为(n+(n-j+2)(j-1)/2，而aij在第j列上的位置是为i-j+1。所以n阶下三角矩阵A按列存储，其元素aij在一维数组B中的存储位置k与i和j的关系为：k=(n+(n-(j-1)+1)(j-1)/2+(i-j+1)=(2n-j)(j-1)/2+i五、算法设计1、输入一个字符串，内有数字和非数字字符，如：ak123x45617960?302gef4563，将其中连续的数字作为一个整体，依次存放到一数组ａ中，例如123放入ａ[0],456放入ａ[1]，……。编程统计其共有多少个整数，并输出这些数。参考答案intCountInt（）//从键盘输入字符串，连续的数字字符算作一个整数，统计其中整数的个数。｛inti=0，a[]；//整数存储到数组a，i记整数个数scanf（“％c”，&ch）；//从左到右读入字符串while（ch!=‘#’）//‘#’是字符串结束标记if（isdigit（ch））//是数字字符｛num=０；//数初始化while（isdigit（ch）&&ch!=‘#’）//拼数｛num=num＊10+‘ch’-‘０’；scanf（“％c”，&ch）；｝a[i]=num；i++；if（ch!=‘#’）scanf（“%c”，&ch）；//若拼数中输入了‘#’，则不再输入｝//结束while（ch！＝‘#’）printf（“共有%d个整数，它们是：”i）；for（j=０；ji；j++）｛printf（“%6d”，a[j]）；if（（j+1）％10==0）printf（“\n”）；}//每10个数输出在一行上｝//算法结束2、S=“S1S2…Sn”是一个长为N的字符串，存放在一个数组中，编程序将S改造之后输出：（1）将S的所有第偶数个字符按照其原来的下标从大到小的次序放在S的后半部分；（2）将S的所有第奇数个字符按照其原来的下标从小到大的次序放在S的前半部分；例如：S=‘ABCDEFGHIJKL’则改造后的S为‘ACEGIKLJHFDB’。voidRearrangeString()//对字符串改造，将第偶数个字符放在串的后半部分，第奇数个字符前半部分。{charch,s[],stk[];//s和stk是字符数组（表示字符串）和字符栈inti=1,j;//i和j字符串和字符栈指针while((ch=getchar())!=’#’)//’#’是字符串结束标志s[i++]=ch;//读入字符串s[i]=’\0’;//字符数组中字符串结束标志i=1;j=1;while(s[i])//改造字符串{if(i%2==0)stk[i/2]=s[i];elses[j++]=s[i];i++;}//whilei--;i=i/2;//i先从’\0’后退，是第偶数字符的个数while(i0)s[j++]=stk[i--]//将第偶数个字符逆序填入原字符数组}3、请编写完整的程序。如果矩阵A中存在这样的一个元素A[i,j]满足条件:A[i,j]是第i行中值最小的元素,且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A的所有马鞍点。intm=10,n=10;voidSaddle(intA[m][n])//A是m*n的矩阵,本算法求矩阵A中的马鞍点.{intmax[n]={0},//max数组存放各列最大值元素的行号,初始化为行号0;min[m]={0},//min数组存放各行最小值元素的列号,初始化为列号0;i,j;for(i=0;im;i++)//选各行最小值元素和各列最大值元素.for(j=0;jn;j++){if(A[max[j]][j]A[i][j])max[j]=i;//修改第j列最大元素的行号if(A[i][min[i]]A[i][j])min[i]=j;//修改第i行最小元素的列号.}for(i=0;im;i++){j=min[i];//第i行最小元素的列号if(i==max[j])printf(“A[%d][%d]是马鞍点，元素值是%d”,i,j,A[i][j]);//是马鞍点}}//Saddle[算法讨论]以上算法假定每行（列）最多只有一个可能的马鞍点，若有多个马鞍点,因为一行(或一列)中可能的马鞍点数值是相同的，则可