第4章串與數(shù)組習題參考答案

1、WOR外式可編輯習題四參考答案一、選擇題1.下面關于串的敘述中，哪一個是不正確的？ （B）A.串是字符的有限序列B.空串是由空格構成的串C.模式匹配是串的一種重要運算D.串既可以采用順序存儲，也可以采用鏈式存儲2 .串的長度是指（A）A.串中包含的字符個數(shù) B.串中包含的不同字符個數(shù)C.串中除空格以外的字符個數(shù)D.串中包含的不同字母個數(shù)3 .設有兩個串p和q,其中q是p的子串，求q在p中首次由現(xiàn)的位置的算法稱為（C）A.求子串B.聯(lián)接C.模式匹配D.求串長4 .設主串的長度為n,模式串的長度為 m,則串匹配的KM嶗法時間復雜度是（C）。AQ（m）BQ（n）C.O（n+m）D.O（n x m）5

2、 .串也是一種線性表，只不過 （A） oA.數(shù)據(jù)元素均為字符 B.數(shù)據(jù)元素是子串C.數(shù)據(jù)元素數(shù)據(jù)類型不受限制D.表長受到限制6 .設有一個10階的對稱矩陣 A采用壓縮存儲方式，以彳t序為主進行存儲，all為第一元素，其存儲地址為1,每個元素占一個地址空間，則 a85的地址為（B） oA.13B.33C.18D.407 .有一個二維數(shù)組 A1.6,0.7,每個數(shù)組元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址， 那么這個數(shù)組占用的存儲空間大小是（D）個字節(jié)。A.48B.96C.252D.2888 .設有數(shù)組A1.8,1.10,數(shù)組的每個元素占3字節(jié)，數(shù)組從內存首地址BA開始以列序為主序順序存放，則數(shù)

3、組元素A5, 8的存儲首地址為（B） oA.BA+141B.BA+180C.BA+222D.BA+2259 .稀疏矩陣的三元組存儲表示方法（B）A.實現(xiàn)轉置操作很簡單，只需將每個三元組中行下標和列下標交換即可B.矩陣的非零元素個數(shù)和位置在操作過程中變化不大時較有效C.是一種鏈式存儲方法D.比十字鏈表更高效10 .用十字鏈表表示一個稀疏矩陣，每個非零元素一般用一個含有（A）域的結點表示。A.5B.4C.3D.2二、填空題1 .一個串的任意連續(xù)字符組成的子序列稱為串的子串，該串稱為主任 2 .串長度為。的串稱為空串，只包含空格的串稱為空格串。 3 .若兩個串的長度相等且對應位置上的字符也相等，則稱

4、兩個串相等。 4 .尋找子串在主串中的位置，稱為模式匹配° H中,子串又稱為模式串。 5 .模式串 t="ababaab”的 next數(shù)組值為-1001231，nextval口 數(shù)組值為-10-10-130 -6 .設數(shù)組A1.5,1.6的基地址為1000,每個元素占5個存儲單元，若以行序為主序順序存儲，則元素 A5,5的存儲地址為11407 .在稀疏矩陣的三元組順序表存儲結構中，除表示非零元的三元組表以外，還需要表示矩 陣的行數(shù)、列數(shù)和非零元個數(shù)。8 . 一個nxn的對稱矩陣，如果以相同的元素只存儲一次的原則進行壓縮存儲，則其元素壓縮后所需的存儲容量為n(n+1)/2 o

5、9 .對矩陣壓縮的目的是為了節(jié)省存儲空間。11.稀疏矩陣一般采用的壓縮存儲方法有兩種，即三元組和十字鏈表。 三、算法設計題1 .編寫基于SeqString類的成員函數(shù)count(),統(tǒng)計當前字符串中的單詞個數(shù)。參考答案：publicintcount()intwordcount=0;/單詞個數(shù)charcurrChar,preChar;for(inti=1;i<this.length();i+)currChar=this.charAt(i);當前字符preChar=this.charAt(i-1);前一個字符if(int)(currChar)<65|(int)(currChar)>

6、;122/當前字符不是字母|(int)(preChar)>90&&(int)(preChar)<97)&&(int)(preChar)>=65&&(int)(preChar)<=90)/當前字符的前一個字符是字母|(int)(preChar)>=97&&(int)(preChar)<=122)wordcount+;returnwordcount;2 .編寫基于SeqString類的成員函數(shù)replace(begin,s1,s2) 。要求在當前對象串中，從下 標begin開始，將所有的s1子串替換

7、為s2串。參考答案：/beginint開始位置；s1String原始字符串；s2String 目標字符串；publicSeqStringreplace(intbegin,SeqStrings1,SeqStrings2)if(s1=nu1111s2=null)returnnull;SeqStringss=newSeqString("");/產(chǎn)生空串SeqStringsource=this;intindex=-1;while(index=source.indexOf(s1,begin)!=-1)ss.concat(source.substring(0,index);/串連接ss

8、.concat(s2);source=(SeqString)source.substring(index+s1.length();/取子串 ss.concat(source);/ 串連接 returnss;3 .編寫基于SeqString類的成員函數(shù)reverse。要求將當前對象中的字符反序存放。 參考答案：publicSeqStringreverse()for(inti=0,j=this.length()-1;i<j;i+,j-)chartemp=this.charAt(i);setCharAt(i,this.charAt(j); setCharAt(j,temp); returnth

9、is; 4 .編寫基于SeqString類的成員函數(shù)deleteallchar(ch) 。要求從當前對象串中刪除其值 等于ch的所有字符。參考答案：publicSeqStringdeleteAllChar(charch)SeqStrings1=newSeqString(String.valueOf(ch);if(s1=null) returnnull;SeqStringss=newSeqString("");/ 產(chǎn)生空串 SeqStringsource=this;/當前串賦值到I sourseintindex=-1; while(index=source.indexOf(s

10、1,0)!=-1)ss.concat(source.substring(0,index);/串連接source=(SeqString)source.substring(index+1);/取子串 ss.concat(source);/ 串連接 returnss; 5 .編寫基于 SeqString類的成員函數(shù)stringcount(str) 。要求統(tǒng)計子串str在當前對象串 中由現(xiàn)的次數(shù)，若不由現(xiàn)則返回0。參考答案：publicintstringCount(SeqStringstr) SeqStringsource=this.curstr; intcount=0,begin=0;intinde

11、x;while(index=source.indexOf(str,begin)!=-1)count+;begin=index+str.length(); returncount;6 .鞍點是指矩陣中的元素aj是第i行中值最小的元素，同時又是第 j列中值最大的元素試設計一個算法求矩陣A的所有鞍點。參考答案：/存放矩陣中鞍點的類classResultTripleNodedata口;三元組表，存放鞍點的行、歹人值intnums;/ 鞍點個數(shù)publicResult(intmaxSize)構造方法data=newTripleNodemaxSize;/為順序表分配 maxSize 個存儲單元for(in

12、ti=0;i<data.length;i+)datai=newTripleNode(); nums=0; /返回矩陣中的所有鞍點publicResultallSaddlePoint(intar)inti,j,flag,m,n;Resultre=newResult(ar.length);for(i=0;i<ar.length;i+) m=i;n=0;flag=1;/ 假設當前結點是鞍點for(j=0;j<ari.length;j+)if(ar皿<armn) n=j;for(j=0;j<ar.length;j+)if(arjn>armn)flag=0;/不是鞍點

13、if(flag=1)/ 是鞍點，將其加入re.datare.nums=newTripleNode(m,n,armn);re.nums+;returnre;7 .設計算法，求由二維數(shù)組An,n的兩條對角線元素之和參考答案：publicstaticintsumOfDiagonal(int口a)inti,n=a0.length,sum1=0,sum2=0,sum;for(i=0;i<a.length;i+)sum1+=aii;主對角線之和sum2+=a皿n-i-1;副對角線之和sum=sum1+sum2;if(n%2=1) 若矩陣行數(shù)為奇數(shù)，則減去兩條對角線相交的元素 sum-=an/2n/2

14、;returnsum;四、上機實踐題12 .在順序串類SeqString中增加一個主函數(shù)，測試各成員函數(shù)的正確性。參考答案：packagech04Exercise;importch04.SeqString;publicclassExercise4_4_1extendsSeqString publicstaticvoidmain(Stringargs口)char口chararray='W,'o','r',T,'d'SeqStrings1=newSeqString();/ 構造一個空串SeqStrings2=newSeqString(&quo

15、t;Hello");/以字符串常量構造串對象System.out.println( s1.insert(0,s2);System.out.println( s1.insert(1,s3);System.out.println( s1.delete(1,4);System.out.println( System.out.println( s1.substring(2,6);SeqStrings3=newSeqString(chararray);/ 以字符數(shù)組構造串對象串 s1="+s1+”,s2="+s2+”,s3="+s3);串s1在第0個字符前插入串s

16、2后，s1="+s1);串s1在第1個字符前插入串s3后，s1="+s1);串s1刪除第1到第3個字符后,s1="+s1);串s1中從第2到第5個字符組成的子串是：運行結果：13 .已知兩個稀疏矩陣 A和B,試基于三元組順序表或十字鏈表的存儲結構，編程實現(xiàn) A+B 的運算。 參考答案：packagech04Exercise; importch04.SparseMatrix; publicclassExercise4_4_2 publicstaticSparseMatrixaddSMatrix(SparseMatrixa,SparseMatrixb) /計算兩個三元

17、組表示的稀疏矩陣之和 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(i<a.getNums()&&j<b.getNums() if(a.getData()i.getRow()<b.getData()j.getRow()/A行 <

18、B 行c.getData()k.setColumn(a.getData()i.getColumn(); c.getData()k.setRow(a.getData()i.getRow(); c.getData()k.setValue(a.getData()i.getValue(); c.setNums(+k); i+; elseif(a.getData()i.getRow()=b.getData()j.getRow()/A 行號=B行號 if(a.getData()i.getColumn()=b.getData()j.getColumn() /A 歹"=8歹" if(a.g

19、etData()i.getValue()+b.getData()j.getValue()!=0) c.getData()k.setColumn(a.getData()i.getColumn(); c.getData()k.setRow(a.getData()i.getRow();c.getData()k.setValue(a.getData()i.getValue()+ b.getData()j.getValue();c.setNums(+k);/設置元素個數(shù)i+；j+；elseif(a.getData()i.getColumn()<b.getData()j.getColumn()/A

20、歹U<B 歹Uc.getData()k.setColumn(a.getData()i.getColumn();c.getData()k.setRow(a.getData()i.getRow();c.getData()k.setValue(a.getData()i.getValue();c.setNums(+k);i+；elseif(a.getData()i.getColumn()>b.getData()j.getColumn()/A列外列c.getData()k.setColumn(b.getData()j.getColumn();c.getData()k.setRow(b.get

21、Data()j.getRow();c.getData()k.setValue(b.getData()j.getValue();c.setNums(+k);j+；elseif(a.getData()i.getRow()>b.getData()j.getRow()/A行>8行c.getData()k.setColumn(b.getData()j.getColumn();c.getData()k.setRow(b.getData()j.getRow();c.getData()k.setValue(b.getData()j.getValue();c.setNums(+k);j+；while

22、(i<a.getNums()將A,B中的剩余非零元復制過去c.getData()k.setColumn(a.getData()i.getColumn();c.getData()k.setRow(a.getData()i.getRow();c.getData()k.setValue(a.getData()i.getValue();c.setNums(+k);i+；while(j<b.getNums()c.getData()k.setColumn(b.getData()j.getColumn();c.getData()k.setRow(b.getData()j.getRow();c.g

23、etData()k.setValue(b.getData()j.getValue(); c.setNums(+k);j+；returnc;publicstaticvoidmain(Stringargs)intmatrixA嚇3,0,0,7,0。-1,0,2。0,0,0。0,0,0,0,0,-8；intmatrixB尸-3,0,0,0,1,0。0,3,0。0,0,2,0,0,0,0,0,0；SparseMatrixtsm1=newSparseMatrix(matrixA);SparseMatrixtsm2=newSparseMatrix(matrixB);System.out.println(&

24、quot;矩陣 A:");tsm1.printMatrix();System.out.println("矩陣 B:");tsm2.printMatrix();SparseMatrixmatrixSum=addSMatrix(tsm1,tsm2);System.out.println(" 矩陣 A+P乍 B:");matrixSum.printMatrix();System.out.println("");運行結果：3.基于十字鏈表類CrossList ,設計插入非零元素結點的成員函數(shù)insert(row,col,val)并編

25、程測試。參考答案：packagech04Exercise;importch04.CrossList;importch04.OLNode;publicclassExercise4_4_3extendsCrossListpublicExercise4_4_3(introw,intcol) super(row,col);OverridepublicvoidInsert(introw,intcol,inte)插入元素OLNodertemp=getRhead()row-1;OLNodectemp=getChead()col-1;專業(yè)知識整理分享WOR外式可編輯OLNodeoldtemp=null;OLN

26、odecurrent=newOLNode(row,col,e);if(rtemp.getRight()=null)rtemp.setRight(current);elsewhile(rtemp.getRight()!=null)oldtemp=rtemp;rtemp=rtemp.getRight();if(rtemp.getCol()>col)current.setRight(oldtemp.getRight();oldtemp.setRight(current);break;else 當前位置存在元素if(rtemp.getCol()=col) System.out.println(&

27、quot;本位置存在元素”);return;elseif(rtemp.getRight()=null) rtemp.setRight(current);break;if(ctemp.getDown()=null)ctemp.setDown(current);this.setTu(this.getTu()+1);elsewhile(ctemp.getDown()!=null)oldtemp=ctemp;ctemp=ctemp.getDown();if(ctemp.getRow()>row)current.setDown(oldtemp.getDown();oldtemp.setDown(c

28、urrent);break;else 當前位置存在元素if(ctemp.getRow()=row) System.out.println("本位置存在元素”);return;elseif(ctemp.getDown()=null) ctemp.setDown(current);this.setTu(this.getTu()+1);return; publicstaticvoidmain(Stringargs)inttemp=0Q0Q5,0,0,0Q0,0Q2Q0,0,0,0,8,0;intinelem=1,2,3;/待插入的元素為：第 1行第2列元素3introw=4; intcol

29、=5;Exercise4_4_3cl=newExercise4_4_3(row,col);/構造十字鏈表for(inti=0;i<row;i+)for(intj=0;j<col;j+) intv=tempij; if(v!=0) cl.Insert(i+1,j+1,v);/插入 System.out.println("原稀疏矩陣");cl.print(); cl.Insert(inelem0,inelem1,inelem2);System.out.println(" 在"+inelem0+" 行"+inelem1+”列插入元素"+inelem2+"后的稀疏矩陣")；cl.print(); 運行結果：N C:WINDOWSsystem32cmd.exe專業(yè)知識整理分享OGO 0 0 0 6 6 2 0 0 0 在1仃26 3 00 06 0 20 0 04.編寫程序實現(xiàn)以三元組形式輸由用