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

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

2、 .串也是一種線(xiàn)性表，只不過(guò) （A） oA.數(shù)據(jù)元素均為字符 B.數(shù)據(jù)元素是子串C.數(shù)據(jù)元素?cái)?shù)據(jù)類(lèi)型不受限制D.表長(zhǎng)受到限制6 .設(shè)有一個(gè)10階的對(duì)稱(chēng)矩陣 A采用壓縮存儲(chǔ)方式，以彳t序?yàn)橹鬟M(jìn)行存儲(chǔ)，all為第一元素，其存儲(chǔ)地址為1,每個(gè)元素占一個(gè)地址空間，則 a85的地址為（B） oA.13B.33C.18D.407 .有一個(gè)二維數(shù)組 A1.6,0.7,每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址， 那么這個(gè)數(shù)組占用的存儲(chǔ)空間大小是（D）個(gè)字節(jié)。A.48B.96C.252D.2888 .設(shè)有數(shù)組A1.8,1.10,數(shù)組的每個(gè)元素占3字節(jié)，數(shù)組從內(nèi)存首地址BA開(kāi)始以列序?yàn)橹餍蝽樞虼娣?，則數(shù)

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

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

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

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

7、為s2串。參考答案：/beginint開(kāi)始位置；s1String原始字符串；s2String 目標(biāo)字符串；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 .編寫(xiě)基于SeqString類(lèi)的成員函數(shù)reverse。要求將當(dāng)前對(duì)象中的字符反序存放。 參考答案：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 .編寫(xiě)基于SeqString類(lèi)的成員函數(shù)deleteallchar(ch) 。要求從當(dāng)前對(duì)象串中刪除其值 等于ch的所有字符。參考答案：publicSeqStringdeleteAllChar(charch)SeqStrings1=newSeqString(String.valueOf(ch);if(s1=null) returnnull;SeqStringss=newSeqString("");/ 產(chǎn)生空串 SeqStringsource=this;/當(dāng)前串賦值到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 .編寫(xiě)基于 SeqString類(lèi)的成員函數(shù)stringcount(str) 。要求統(tǒng)計(jì)子串str在當(dāng)前對(duì)象串 中由現(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 .鞍點(diǎn)是指矩陣中的元素aj是第i行中值最小的元素，同時(shí)又是第 j列中值最大的元素試設(shè)計(jì)一個(gè)算法求矩陣A的所有鞍點(diǎn)。參考答案：/存放矩陣中鞍點(diǎn)的類(lèi)classResultTripleNodedata口;三元組表，存放鞍點(diǎn)的行、歹人值intnums;/ 鞍點(diǎn)個(gè)數(shù)publicResult(intmaxSize)構(gòu)造方法data=newTripleNodemaxSize;/為順序表分配 maxSize 個(gè)存儲(chǔ)單元for(in

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

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

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

15、t;Hello");/以字符串常量構(gòu)造串對(duì)象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ù)組構(gòu)造串對(duì)象串 s1="+s1+”,s2="+s2+”,s3="+s3);串s1在第0個(gè)字符前插入串s

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

17、組表示的稀疏矩陣之和 if(a.getRows()!=b.getRows()|a.getCols()!=b.getCols() System.out.println("這兩個(gè)矩陣不能相加”)；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 行號(hào)=B行號(hào) 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è)置元素個(gè)數(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中的剩余非零元復(fù)制過(guò)去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("");運(yùn)行結(jié)果：3.基于十字鏈表類(lèi)CrossList ,設(shè)計(jì)插入非零元素結(jié)點(diǎn)的成員函數(shù)insert(row,col,val)并編

25、程測(cè)試。參考答案：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;專(zhuān)業(yè)知識(shí)整理分享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 當(dāng)前位置存在元素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 當(dāng)前位置存在元素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);/構(gòu)造十字鏈表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(); 運(yùn)行結(jié)果：N C:WINDOWSsystem32cmd.exe專(zhuān)業(yè)知識(shí)整理分享OGO 0 0 0 6 6 2 0 0 0 在1仃26 3 00 06 0 20 0 04.編寫(xiě)程序?qū)崿F(xiàn)以三元組形式輸由用