幫你掌握數據結構(第四、五章系列經典試題及答案)

1、第45章 串和數組 一、填空題（每空1分，共20分）1. 不包含任何字符（長度為0）的串 稱為空串； 由一個或多個空格（僅由空格符）組成的串 稱為空白串。（對應嚴題集4.1，簡答題：簡述空串和空格串的區(qū)別）2. 設S=“A;/document/Mary.doc”，則strlen(s= 20 , “/”的字符定位的位置為 3 。4. 子串的定位運算稱為串的模式匹配； 被匹配的主串 稱為目標串， 子串 稱為模式。5. 設目標T=”abccdcdccbaa”，模式P=“cdcc”，則第 6 次匹配成功。6. 若n為主串長，m為子串長，則串的古典（樸素）匹配算法最壞的情況下需要比較字符的總次數為 (n

2、-m+1*m 。7. 假設有二維數組A6×8，每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。已知A的起始存儲位置（基地址）為1000，則數組A的體積（存儲量）為 288 B ；末尾元素A57的第一個字節(jié)地址為 1282 ；若按行存儲時，元素A14的第一個字節(jié)地址為 (8+4×6+1000=1072 ；若按列存儲時，元素A47的第一個字節(jié)地址為 (6×74×61000）1276 。(注：數組是從0行0列還是從1行1列計算起呢？由末單元為A57可知，是從0行0列開始！8. 00年計算機系考研題設數組a160, 170的基地址為2048，每個元素占2個存儲單

3、元，若以列序為主序順序存儲，則元素a32,58的存儲地址為 8950。答：不考慮0行0列，利用列優(yōu)先公式： LOC(aij=LOC(ac1，c2+(j-c2*(d1-c1+1+i-c1*L得：LOC(a32,58=2048+(58-1*(60-1+1+32-1*289509. 三元素組表中的每個結點對應于稀疏矩陣的一個非零元素，它包含有三個數據項，分別表示該元素的 行下標 、 列下標 和 元素值 。10.求下列廣義表操作的結果：（1） GetHead【(a,b,(c,d】= (a, b ; /頭元素不必加括號（2） GetHead【GetTail【(a,b,(c,d】= (c,d ;（3） G

4、etHead【GetTail【GetHead【(a,b,(c,d】= b ;（4） GetTail【GetHead【GetTail【(a,b,(c,d】= （d） ;二、單選題（每小題1分，共15分）（ B ）1. 李串是一種特殊的線性表，其特殊性體現(xiàn)在：可以順序存儲 數據元素是一個字符 可以鏈式存儲 數據元素可以是多個字符（ B ）2. 李設有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作：連接 模式匹配 求子串 求串長（ D ）3. 李設串s1=ABCDEFG，s2=PQRST，函數con(x,y返回x和y串的連接串，subs(s, i, j返回串s的從序號i開始的j個字符組成的子串，l

5、en(s返回串s的長度，則con(subs(s1, 2, len(s2, subs(s1, len(s2, 2的結果串是：BCDEF BCDEFG BCPQRST BCDEFEF解：con(x,y返回x和y串的連接串，即 con(x,yABCDEFGPQRST；subs(s, i, j返回串s的從序號i開始的j個字符組成的子串，則subs(s1, 2, len(s2subs(s1, 2, 5= BCDEF; subs(s1, len(s2, 2subs(s1, 5, 2= EF;所以con(subs(s1, 2, len(s2, subs(s1, len(s2, 2con( BCDEF, EF

6、之連接，即BCDEFEF（ A ）4. 01年計算機系考研題假設有60行70列的二維數組a160, 170以列序為主序順序存儲，其基地址為10000，每個元素占2個存儲單元，那么第32行第58列的元素a32,58的存儲地址為 。（無第0行第0列元素）16902 16904 14454 答案A, B, C均不對答：此題與填空題第8小題相似。（57列×60行31行）×2字節(jié)10000=16902( B 5. 設矩陣A是一個對稱矩陣，為了節(jié)省存儲，將其下三角部分（如下圖所示）按行序存放在一維數組B 1, n(n-1/2 中，對下三角部分中任一元素ai,j(ij, 在一維數組B中下

7、標k的值是：i(i-1/2+j-1 i(i-1/2+j i(i+1/2+j-1 i(i+1/2+j解：注意B的下標要求從1開始。先用第一個元素去套用，可能有B和C；再用第二個元素去套用B和C，B=2而C3（不符）；所以選B6. 【91初程P78】 從供選擇的答案中，選出應填入下面敘述 ？ 內的最確切的解答，把相應編號寫在答卷的對應欄內。有一個二維數組A，行下標的范圍是0到8，列下標的范圍是1到5，每個數組元素用相鄰的4個字節(jié)存儲。存儲器按字節(jié)編址。假設存儲數組元素A0,1的第一個字節(jié)的地址是0。存儲數組A的最后一個元素的第一個字節(jié)的地址是 A 。若按行存儲，則A3,5和A5,3的第一個字節(jié)的地

8、址分別是 B 和 C 。若按列存儲，則A7,1和A2,4的第一個字節(jié)的地址分別是 D 和 E 。供選擇的答案：AE：28 44 76 92 108 116 132 176 184 188答案：ABCDE=8, 3, 5, 1, 67.【94程P12】 有一個二維數組A，行下標的范圍是1到6，列下標的范圍是0到7，每個數組元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。那么，這個數組的體積是 A 個字節(jié)。假設存儲數組元素A1,0的第一個字節(jié)的地址是0，則存儲數組A的最后一個元素的第一個字節(jié)的地址是 B 。若按行存儲，則A2,4的第一個字節(jié)的地址是 C 。若按列存儲，則A5,7的第一個字節(jié)的地址是 D

9、 。供選擇的答案AD：12 66 72 96 114 120 156 234 276 282 （11）283 （12）288答案：ABCD=12, 10, 3, 9三、簡答題（每小題5分，共15分）1. 【其他教材】KMP算法的設計思想是什么？它有什么優(yōu)點？答：其設計思想是，利用已經部分匹配的結果來加快模式串的滑動速度。主要優(yōu)點有二：一是在模式與主串已經部分匹配的情況下，可以大大加快匹配速度；二是主串指針不回溯，可以使外設文件邊讀入邊匹配。2. 【其他教材】已知二維數組Am,m采用按行優(yōu)先順序存放，每個元素占K個存儲單元，并且第一個元素的存儲地址為Loc(a11，請寫出求Loc(aij的計算公

10、式。如果采用列優(yōu)先順序存放呢？解：公式教材已給出，此處雖是方陣，但行列公式仍不相同；按行存儲的元素地址公式是： Loc(aij= Loc(a11 + (i-1*m+(j-1 * K按列存儲的元素地址公式是： Loc(aij= Loc(a11 + (j-1*m+(i-1 * K3.【全國專升本資格考試】遞歸算法比非遞歸算法花費更多的時間，對嗎？為什么？答：不一定。時間復雜度與樣本個數n有關，是指最深層的執(zhí)行語句耗費時間，而遞歸算法與非遞歸算法在最深層的語句執(zhí)行上是沒有區(qū)別的，循環(huán)的次數也沒有太大差異。僅僅是確定循環(huán)是否繼續(xù)的方式不同，遞歸用棧隱含循環(huán)次數，非遞歸用循環(huán)變量來顯示循環(huán)次數而已。四、

11、計算題（每題5分，共20分）1. 設s=I AM A STUDENT, t=GOOD, q=WORKER, 求Replace(s,STUDENT,q 和Concat(SubString(s,6,2, Concat(t,SubString(s,7,8。解： Replace(s,STUDENT,qI AM A WORKER 因為 SubString(s,6,2A ；SubString(s,7,8 STUDENTConcat(t,SubString(s,7,8GOOD STUDENT所以Concat(SubString(s,6,2, Concat(t,SubString(s,7,8A GOOD ST

12、UDENT2. 【嚴題集4.8】 已知主串s=ADBADABBAABADABBADADA,模式串pat=ADABBADADA。寫出模式串的nextval函數值，并由此畫出KMP算法匹配的全過程。解：（由演示程序得知）nextval函數值為0 1 0 2 1 0 1 0 4 0 在第12個字符處發(fā)現(xiàn)匹配！s=ADBADABBAABADABBADADApat=ADABBADADA3. （P60 4-18）用三元組表表示下列稀疏矩陣： 解：參見填空題4. 三元素組表中的每個結點對應于稀疏矩陣的一個非零元素，它包含有三個數據項，分別表示該元素的 行下標 、 列下標 和 元素值 。所以（1）可列表為：

13、（2）可列表為：8866416-225943565353233685467858124. （P60 4-19）下列各三元組表分別表示一個稀疏矩陣，試寫出它們的稀疏矩陣。 解：（1）為6×4矩陣，非零元素有6個。 （2）為4×5矩陣，非零元素有5個0 2 0 0 12 0 0 0 3 0 0 0 0 0 0 4 0 0 6 0 16 0 0 0 1 0 0 0 00 0 0 9 00 8 0 0 60 0 7 0 0五、算法設計題（每題10分，共30分）1. 【嚴題集4.12】 編寫一個實現(xiàn)串的置換操作Replace(&S, T, V的算法。解：int Replace

14、(Stringtype &S,Stringtype T,Stringtype V;/將串S中所有子串T替換為 V,并返回置換次數 for(n=0,i=1;i<=Strlen(S-Strlen(T+1;i+ /注意i的取值范圍 if(!StrCompare(SubString(S,i,Strlen(T,T /找到了與T匹配的子串 /分別把T的前面和后面部分保存為head和tail StrAssign(head,SubString(S,1,i-1; StrAssign(tail,SubString(S,i+Strlen(T,Strlen(S-i-Strlen(T+1; StrAssi

15、gn(S,Concat(head,V; StrAssign(S,Concat(S,tail; /把head,V,tail連接為新串 i+=Strlen(V; /當前指針跳到插入串以后 n+; n+; /if return n; /Replace分析:i+=Strlen(V;這一句是必需的,也是容易忽略的.如省掉這一句,則在某些情況下, 會引起不希望的后果,雖然在大多數情況下沒有影響.請思考:設S='place', T='ace', V='face',則省掉i+=Strlen(V;運行時會出現(xiàn)什么結果?2. 【全國專升本資格考試】寫出將字符串反序的

16、遞歸或遞推算法，例如字符串為“abcsxw”，反序為“wxscba”(注：這也是嚴題集4.10 編寫對串求逆的遞推算法請注意遞歸和遞推的區(qū)別！遞推是由“小”到“大”遞進； 遞歸是由“大”到“小”嵌套。算法思路：1 假定用單鏈表結構存儲字符串；if沒有到尾部字符就不停調用自身函數，直至到達末尾，再從尾部返回并打印字符；遞歸算法的一般形式：（殷人凱題集P102）void p(參數表if （遞歸結束條件）可直接求解步驟； 基本項else p（較小的參數）； 歸納項否則就打印當前字符并返回。 Invert(stringlistnode *pif(!preturn(0;else Invert(p->

17、;next;printf(“%c”, p->data如果當前串長為0,則return(-1否則開始遞歸：if 串沒有到末尾，則P=P->next; 再調用invert(s;else printf(p->data;return嚴題集4.10答案：void String_Reverse(Stringtype s,Stringtype &r/求s的逆串r StrAssign(r,'' /初始化r為空串 for(i=Strlen(s;i;i- StrAssign(c,SubString(s,i,1; StrAssign(r,Concat(r,c; /把s的字符

18、從后往前添加到r中 /這是遞推算法。 /String_Reverse3. 【嚴題集5.18】試設計一個算法，將數組An 中的元素A0至An-1循環(huán)右移k位，并要求只用一個元素大小的附加存儲，元素移動或交換次數為O(n解：分析:要把A的元素循環(huán)右移k位,則A0移至Ak,Ak移至A2k.直到最終回到A 0.然而這并沒有全部解決問題,因為有可能有的元素在此過程中始終沒有被訪問過,而是被跳了過去.分析可知,當n和k的最大公約數為p時,只要分別以A0,A1,.Ap-1為起點執(zhí)行上述算法,就可以保證每一個元素都被且僅被右移一次,從而滿足題目要求.也就是說,A的所有元素分別處在p個"循環(huán)鏈"上面.舉例如下: n=15,k=6,則p=3. 第一條鏈:A0->A6,A6->A12,A12->A3,A3->A9,A9->A0. /已“順便”移動了A6、A12第二條鏈:A1->A7,A7->A13,A13->A4,A4->A10,A10-