1、習題四 參考答案一、選擇題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(nm

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

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

4、稱為 空串 ，只包含空格的串稱為 空格串 。3. 若兩個串的長度相等且對應位置上的字符也相等，則稱兩個串 相等 。4. 尋找子串在主串中的位置，稱為 模式匹配 。其中，子串又稱為 模式串 。5. 模式串t=ababaab的next數組值為 -1001231 ，nextval數組值為 -10-10-130 。6. 設數組A1.5,1.6的基地址為1000，每個元素占5個存儲單元，若以行序為主序順序存儲，則元素A5,5的存儲地址為 1140 。7在稀疏矩陣的三元組順序表存儲結構中，除表示非零元的三元組表以外，還需要表示矩陣的行數、列數和 非零元個數 。8一個nn的對稱矩陣，如果以相同的元素只存儲一

5、次的原則進行壓縮存儲，則其元素壓縮后所需的存儲容量為 n(n+1)/2 。9對矩陣壓縮的目的是為了 節省存儲空間 。10.稀疏矩陣一般采用的壓縮存儲方法有兩種，即 三元組 和 十字鏈表 。三、算法設計題1 編寫基于SeqString類的成員函數count(),統計當前字符串中的單詞個數。參考答案:public int count() int wordcount = 0; /單詞個數 char currChar, preChar; for (int i = 1; i this.length(); i+) currChar = this.charAt(i); /當前字符 preChar = thi

6、s.charAt(i - 1); /前一個字符 if (int) (currChar) 122 /當前字符不是字母 | (int) (preChar) 90 & (int) (preChar) = 65 & (int) (preChar) = 97 & (int) (preChar) = 122) wordcount+; return wordcount;2 編寫基于SeqString類的成員函數replace(begin,s1,s2)。要求在當前對象串中，從下標begin開始，將所有的s1子串替換為s2串。參考答案: /begin int 開始位置;s1 String 原始字符串; s2 S

7、tring 目標字符串; public SeqString replace(int begin, SeqString s1, SeqString s2) if (s1 = null | s2 = null) return null; SeqString ss = new SeqString(); /產生空串 SeqString source = this; int index = -1; while (index = source.indexOf(s1, begin) != -1) ss.concat(source.substring(0, index); /串連接 ss.concat(s2)

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

9、, temp); return this; 4 編寫基于SeqString類的成員函數deleteallchar(ch)。要求從當前對象串中刪除其值等于ch的所有字符。參考答案:public SeqString deleteAllChar(char ch) SeqString s1 = new SeqString(String.valueOf(ch); if (s1 = null) return null; SeqString ss = new SeqString(); /產生空串 SeqString source = this; /當前串賦值到sourse int index = -1; w

10、hile (index = source.indexOf(s1, 0) != -1) ss.concat(source.substring(0, index); /串連接 source = (SeqString) source.substring(index + 1); /取子串 ss.concat(source); /串連接 return ss; 5 編寫基于SeqString類的成員函數stringcount(str)。要求統計子串str在當前對象串中出現的次數，若不出現則返回0。參考答案:public int stringCount(SeqString str) SeqString so

11、urce = this.curstr; int count = 0, begin = 0; int index; while (index = source.indexOf(str, begin) != -1) count+; begin = index + str.length(); return count; 6 鞍點是指矩陣中的元素aij是第i行中值最小的元素，同時又是第j列中值最大的元素。試設計一個算法求矩陣A的所有鞍點。參考答案:/存放矩陣中鞍點的類class Result TripleNode data; /三元組表，存放鞍點的行、列、值 int nums; /鞍點個數 publi

12、c Result(int maxSize) /構造方法 data = new TripleNodemaxSize; /為順序表分配maxSize個存儲單元 for (int i = 0; i data.length; i+) datai = new TripleNode(); nums = 0; /返回矩陣中的所有鞍點public Result allSaddlePoint(int ar) int i, j, flag, m, n; Result re = new Result(ar.length); for (i = 0; i ar.length; i+) m = i; n = 0; fla

13、g = 1; /假設當前結點是鞍點 for (j = 0; j ari.length; j+) if (arij armn) n = j; for (j = 0; j armn) flag = 0; /不是鞍點 if (flag = 1) /是鞍點，將其加入 re.datare.nums = new TripleNode(m, n, armn); re.nums+; return re; 7 設計算法，求出二維數組An,n的兩條對角線元素之和參考答案:public static int sumOfDiagonal(int a) int i, n = a0.length, sum1 = 0, s

14、um2 = 0, sum; for (i = 0; i a.length; i+) sum1 += aii; /主對角線之和 sum2 += ain - i - 1; /副對角線之和 sum = sum1 + sum2; if (n % 2 = 1) /若矩陣行數為奇數，則減去兩條對角線相交的元素。 sum -= an / 2n / 2; return sum;四、上機實踐題1. 在順序串類SeqString中增加一個主函數，測試各成員函數的正確性。參考答案: package ch04Exercise;import ch04.SeqString;public class Exercise4_4

15、_1 extends SeqString public static void main(String args) char chararray = W, o, r, l, d; SeqString s1 = new SeqString(); /構造一個空串 SeqString s2 = new SeqString(Hello); /以字符串常量構造串對象 SeqString s3 = new SeqString(chararray); /以字符數組構造串對象 System.out.println(串 s1= + s1 + , s2= + s2 + , s3= + s3); s1.insert

16、(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的運算。參考答案

17、:package ch04Exercise;import ch04.SparseMatrix;public class Exercise4_4_2 public static SparseMatrix addSMatrix(SparseMatrix a, SparseMatrix b) /計算兩個三元組表示的稀疏矩陣之和 if (a.getRows() != b.getRows() | a.getCols() != b.getCols() System.out.println(這兩個矩陣不能相加); return null; SparseMatrix c = new SparseMatrix(

18、a.getNums() + b.getNums(); int i = 0, j = 0, k = 0; int len=0; while (i a.getNums() & j b.getNums() if (a.getData()i.getRow() b.getData()j.getRow() /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.setNu

19、ms(+k); i+; else if (a.getData()i.getRow() = b.getData()j.getRow() / A行號=B行號 if (a.getData()i.getColumn() = b.getData()j.getColumn() /A列=B列 if (a.getData()i.getValue() + b.getData()j.getValue() != 0) c.getData()k.setColumn(a.getData()i.getColumn(); c.getData()k.setRow(a.getData()i.getRow(); c.getDat

20、a()k.setValue(a.getData()i.getValue() + b.getData()j.getValue(); c.setNums(+k); /設置元素個數 i+; j+; else if (a.getData()i.getColumn() b.getData()j.getColumn() /A列 b.getData()j.getColumn() /A列B列 c.getData()k.setColumn(b.getData()j.getColumn(); c.getData()k.setRow(b.getData()j.getRow(); c.getData()k.setVa

21、lue(b.getData()j.getValue(); c.setNums(+k); j+; else if (a.getData()i.getRow() b.getData()j.getRow() /A行B行 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 (i a.getNums() /將A,B中的剩余非零元復制

22、過去 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 col) current.setRight(oldtemp.getRight(); oldtemp.setRight ( current); break; else /當前位置存在元素 if (rtemp.getCol() = col) System.out.

23、println(本位置存在元素); return; else if (rtemp.getRight() = null) rtemp.setRight ( current); break; if (ctemp.getDown() = null) ctemp.setDown(current); this.setTu(this.getTu()+1); else while (ctemp.getDown() != null) oldtemp = ctemp; ctemp = ctemp.getDown(); if (ctemp.getRow() row) current.setDown(oldtemp

24、.getDown(); oldtemp.setDown(current); break; else /當前位置存在元素 if (ctemp.getRow() = row) System.out.println(本位置存在元素); return; else if (ctemp.getDown() = null) ctemp.setDown ( current); this.setTu(this.getTu()+1); return; public static void main(String args) int temp = 0,0,0,0,5,0,0,0,0,0,0,0,2,0,0,0,0,

25、0,8,0; int inelem=1,2,3; /待插入的元素為：第1行第2列元素3 int row =4; int col =5; Exercise4_4_3 cl = new Exercise4_4_3(row, col); /構造十字鏈表 for (int i = 0; i row; i+) for (int j = 0; j col; j+) int v = 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(); 運行結果:4. 編寫程序實現以三元組形式輸出用十字鏈表表示的稀疏矩陣中的非零元素及其下標。參考答案:package ch04Exercise;import ch04.CrossList;import ch04.OLNode;public class Exercise4_4_4 extends CrossList public Exercise4_4_4(in