第4章-串与数组-习题参考答案

习题四参考答案一、选择题1．下面关于串的叙述中，哪一个是不正确的？（B）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2．串的长度是指(A)A.串中包含的字符个数B.串中包含的不同字符个数C.串中除空格以外的字符个数D.串中包含的不同字母个数3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（C）A．求子串B．联接C．模式匹配D．求串长4．设主串的长度为n，模式串的长度为m，则串匹配的KMP算法时间复杂度是(C)。A.O(m)B.O(n)C.O(n+m)D.O(n×m)5.串也是一种线性表，只不过(A)。A.数据元素均为字符B.数据元素是子串C.数据元素数据类型不受限制D.表长受到限制6.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主进行存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（B）。A.13B.33C.18D.407.有一个二维数组A[1..6,0..7]，每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组占用的存储空间大小是（D）个字节。A.48B.96C.252D.2888.设有数组A[1..8,1..10]，数组的每个元素占3字节，数组从内存首地址BA开始以列序为主序顺序存放，则数组元素A[5，8]的存储首地址为(B)。A.BA+141B.BA+180C.BA+222D.BA+2259.稀疏矩阵的三元组存储表示方法(B)A.实现转置操作很简单，只需将每个三元组中行下标和列下标交换即可B.矩阵的非零元素个数和位置在操作过程中变化不大时较有效C.是一种链式存储方法D.比十字链表更高效10.用十字链表表示一个稀疏矩阵，每个非零元素一般用一个含有(A)域的结点表示。A.5B.4C.3D.2二、填空题1.一个串的任意连续字符组成的子序列称为串的子串，该串称为主串。2．串长度为0的串称为空串，只包含空格的串称为空格串。3.若两个串的长度相等且对应位置上的字符也相等，则称两个串相等。4.寻找子串在主串中的位置，称为模式匹配。其中，子串又称为模式串。5.模式串t=ababaab的next[]数组值为-1001231，nextval[]数组值为-10-10-130。6.设数组A[1..5,1..6]的基地址为1000，每个元素占5个存储单元，若以行序为主序顺序存储，则元素A[5,5]的存储地址为1140。7．在稀疏矩阵的三元组顺序表存储结构中，除表示非零元的三元组表以外，还需要表示矩阵的行数、列数和非零元个数。8．一个n×n的对称矩阵，如果以相同的元素只存储一次的原则进行压缩存储，则其元素压缩后所需的存储容量为n(n+1)/2。9．对矩阵压缩的目的是为了节省存储空间。10.稀疏矩阵一般采用的压缩存储方法有两种，即三元组和十字链表。三、算法设计题1．编写基于SeqString类的成员函数count(),统计当前字符串中的单词个数。参考答案:publicintcount(){intwordcount=0;//单词个数charcurrChar,preChar;for(inti=1;ithis.length();i++){currChar=this.charAt(i);//当前字符preChar=this.charAt(i-1);//前一个字符if(((int)(currChar)65||(int)(currChar)122//当前字符不是字母||((int)(preChar)90&&(int)(preChar)97))&&(((int)(preChar)=65&&(int)(preChar)=90)//当前字符的前一个字符是字母||((int)(preChar)=97&&(int)(preChar)=122))){wordcount++;}}returnwordcount;}2．编写基于SeqString类的成员函数replace(begin,s1,s2)。要求在当前对象串中，从下标begin开始，将所有的s1子串替换为s2串。参考答案://beginint开始位置;s1String原始字符串;s2String目标字符串;publicSeqStringreplace(intbegin,SeqStrings1,SeqStrings2){if(s1==null||s2==null){returnnull;}SeqStringss=newSeqString();//产生空串SeqStringsource=this;intindex=-1;while((index=source.indexOf(s1,begin))!=-1){ss.concat(source.substring(0,index));//串连接ss.concat(s2);source=(SeqString)source.substring(index+s1.length());//取子串}ss.concat(source);//串连接returnss;}3．编写基于SeqString类的成员函数reverse()。要求将当前对象中的字符反序存放。参考答案:publicSeqStringreverse(){for(inti=0,j=this.length()-1;ij;i++,j--){chartemp=this.charAt(i);setCharAt(i,this.charAt(j));setCharAt(j,temp);}returnthis;}4．编写基于SeqString类的成员函数deleteallchar(ch)。要求从当前对象串中删除其值等于ch的所有字符。参考答案:publicSeqStringdeleteAllChar(charch){SeqStrings1=newSeqString(String.valueOf(ch));if(s1==null){returnnull;}SeqStringss=newSeqString();//产生空串SeqStringsource=this;//当前串赋值到sourseintindex=-1;while((index=source.indexOf(s1,0))!=-1){ss.concat(source.substring(0,index));//串连接source=(SeqString)source.substring(index+1);//取子串}ss.concat(source);//串连接returnss;}5．编写基于SeqString类的成员函数stringcount(str)。要求统计子串str在当前对象串中出现的次数，若不出现则返回0。参考答案:publicintstringCount(SeqStringstr){SeqStringsource=this.curstr;intcount=0,begin=0;intindex;while((index=source.indexOf(str,begin))!=-1){count++;begin=index+str.length();}returncount;}6．鞍点是指矩阵中的元素aij是第i行中值最小的元素，同时又是第j列中值最大的元素。试设计一个算法求矩阵A的所有鞍点。参考答案://存放矩阵中鞍点的类classResult{TripleNodedata[];//三元组表，存放鞍点的行、列、值intnums;//鞍点个数publicResult(intmaxSize){//构造方法data=newTripleNode[maxSize];//为顺序表分配maxSize个存储单元for(inti=0;idata.length;i++){data[i]=newTripleNode();}nums=0;}}//返回矩阵中的所有鞍点publicResultallSaddlePoint(int[][]ar){inti,j,flag,m,n;Resultre=newResult(ar.length);for(i=0;iar.length;i++){m=i;n=0;flag=1;//假设当前结点是鞍点for(j=0;jar[i].length;j++){if(ar[i][j]ar[m][n]){n=j;}}for(j=0;jar.length;j++){if(ar[j][n]ar[m][n]){flag=0;//不是鞍点}}if(flag==1){//是鞍点，将其加入re.data[re.nums]=newTripleNode(m,n,ar[m][n]);re.nums++;}}returnre;}7．设计算法，求出二维数组A[n,n]的两条对角线元素之和参考答案:publicstaticintsumOfDiagonal(int[][]a){inti,n=a[0].length,sum1=0,sum2=0,sum;for(i=0;ia.length;i++){sum1+=a[i][i];//主对角线之和sum2+=a[i][n-i-1];//副对角线之和}sum=sum1+sum2;if(n%2==1){//若矩阵行数为奇数，则减去两条对角线相交的元素。sum-=a[n/2][n/2];}returnsum;}四、上机实践题1.在顺序串类SeqString中增加一个主函数，测试各成员函数的正确性。参考答案:packagech04Exercise;importch04.SeqString;publicclassExercise4_4_1extendsSeqString{publicstaticvoidmain(Stringargs[]){char[]chararray={'W','o','r','l','d'};SeqStrings1=newSeqString();//构造一个空串SeqStrings2=newSeqString(Hello);//以字符串常量构造串对象SeqStrings3=newSeqString(chararray);//以字符数组构造串对象System.out.println(串s1=+s1+,s2=+s2+,s3=+s3);s1.insert(0,s2);System.out.println(串s1在第0个字符前插入串s2后,s1=+s1);s1.insert(1,s3);System.out.println(串s1在第1个字符前插入串s3后,s1=+s1);s1.delete(1,4);System.out.println(串s1删除第1到第3个字符后,s1=+s1);System.out.println(串s1中从第2到第5个字符组成的子串是：+s1.substring(2,6));}}运行结果:2.已知两个稀疏矩阵A和B，试基于三元组顺序表或十字链表的存储结构，编程实现A+B的运算。参考答案:packagech04Exercise;importch04.SparseMatrix;publicclassExercise4_4_2{publicstaticSparseMatrixaddSMatrix(SparseMatrixa,SparseMatrixb){//计算两个三元组表示的稀疏矩阵之和if(a.getRows()!=b.getRows()||a.getCols()!=b.getCols()){System.out.println(这两个矩阵不能相加);returnnull;}SparseMatrixc=newSparseMatrix(a.getNums()+b.getNums());inti=0,j=0,k=0;intlen=0;while(ia.getNums()&&jb.getNums()){if(a.getData()[i].getRow()b.getData()[j].getRow()){//A行B行c.getData()[