第4～5章串和陣列自測卷答案
一、填空題（每空1分，共20分）
1. 不包含任何字元（長度為0）的串稱為空串； 由乙個或多個空格（僅由空格符）組成的串稱為空白串。
（對應嚴題集4.1①，簡答題：簡述空串和空格串的區別）
2. 設s=「a;/document/mary.doc」，則strlen(s)= 20的字元定位的位置為 3 。
4. 子串的定位運算稱為串的模式匹配； 被匹配的主串稱為目標串， 子串稱為模式。
5. 設目標t=」abccdcdccbaa」，模式p=「cdcc」，則第 6 次匹配成功。
6. 若n為主串長，m為子串長，則串的古典（樸素）匹配演算法最壞的情況下需要比較字元的總次數為 (n-m+1)*m 。
7. 假設有二維陣列a6×8，每個元素用相鄰的6個位元組儲存，儲存器按位元組編址。已知a的起始儲存位置（基位址）為1000，則陣列a的體積（儲存量）為 288 b ；末尾元素a57的第乙個位元組位址為 1282 ；若按行儲存時，元素a14的第乙個位元組位址為 (8+4)×6+1000=1072 ；若按列儲存時，元素a47的第乙個位元組位址為 (6×7＋4)×6＋1000）＝1276 。
(注：陣列是從0行0列還是從1行1列計算起呢？由末單元為a57可知，是從0行0列開始！)
8. 〖00年計算機系考研題〗設陣列a[1…60, 1…70]的基位址為2048，每個元素佔2個儲存單元，若以列序為主序順序儲存，則元素a[32,58]的儲存位址為 8950
。答：不考慮0行0列，利用列優先公式： loc(aij)=loc(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*l
得：loc(a32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2＝8950
9. 三元素組表中的每個結點對應於稀疏矩陣的乙個非零元素，它包含有三個資料項，分別表示該元素
的行下標 、 列下標和元素值 。
10.求下列廣義表操作的結果：
（1） gethead【((a,b),(c,da, b頭元素不必加括號
（2） gethead【gettail【((a,b),(c,dc,d) ;
（3） gethead【gettail【gethead【((a,b),(c,db ;
（4） gettail【gethead【gettail【((a,b),(c,dd） ;
二、單選題（每小題1分，共15分）
（ b ）1. 〖李〗串是一種特殊的線性表，其特殊性體現在：
ａ．可以順序儲存 ｂ．資料元素是乙個字元
ｃ．可以鏈式儲存資料元素可以是多個字元
（ b ）2. 〖李〗設有兩個串p和q，求q在p中首次出現的位置的運算稱作：
ａ．連線 ｂ．模式匹配 ｃ．求子串 ｄ．求串長
（ d ）3. 〖李〗設串s1=』abcdefg』，s2=』pqrst』，函式con(x,y)返回x和y串的連線串，subs(s, i, j)返回串s的從序號i開始的j個字元組成的子串，len(s)返回串s的長度，則con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的結果串是：
ａ．bcdef ｂ．bcdefg ｃ．bcpqrstbcdefef
解：con(x,y)返回x和y串的連線串，即 con(x,y)＝『abcdefgpqrst』；
subs(s, i, j)返回串s的從序號i開始的j個字元組成的子串，則
subs(s1, 2, len(s2))＝subs(s1, 2, 5)=』 bcdef』; subs(s1, len(s2), 2)＝subs(s1, 5, 2)=』 ef』;
所以con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))＝con(』 bcdef』, 』 ef』)之連線，即bcdefef
（ a ）4. 〖01年計算機系考研題〗假設有60行70列的二維陣列a[1…60, 1…70]以列序為主序順序儲存，其基位址為10000，每個元素佔2個儲存單元，那麼第32行第58列的元素a[32,58]的儲存位址為 。（無第0行第0列元素）
ａ．16902 ｂ．16904 ｃ．14454 ｄ．答案a, b, c均不對
答：此題與填空題第8小題相似。（57列×60行＋31行）×2位元組＋10000=16902
( b )5. 設矩陣a是乙個對稱矩陣，為了節省儲存，將其下三角部分（如下圖所示）按行序存放在一維陣列b[ 1, n(n-1)/2 ]中，對下三角部分中任一元素ai,j(i≤j), 在一維陣列b中下標k的值是：
ａ．i(i-1)/2+j-1 ｂ．i(i-1)/2+j ｃ．i(i+1)/2+j-1i(i+1)/2+j
6. 【91初程p78】 從供選擇的答案中，選出應填入下面敘述 ？ 內的最確切的解答，把相應編號寫在答卷的對應欄內。
有乙個二維陣列a，行下標的範圍是0到8，列下標的範圍是1到5，每個陣列元素用相鄰的4個位元組儲存。儲存器按位元組編址。假設儲存陣列元素a[0,1]的第乙個位元組的位址是0。
儲存陣列a的最後乙個元素的第乙個位元組的位址是 a 。若按行儲存，則a[3,5]和a[5,3]的第乙個位元組的位址分別是 b 和 c 。若按列儲存，則a[7,1]和a[2,4]的第乙個位元組的位址分別是 d 和 e 。
供選擇的答案：
a～e：①28 ② 44 ③ 76 ④ 92 ⑤ 108
⑥ 116 ⑦ 132 ⑧ 176 ⑨ 184 ⑩ 188
答案：abcde=8, 3, 5, 1, 6
7.【94程p12】 有乙個二維陣列a，行下標的範圍是1到6，列下標的範圍是0到7，每個陣列元素用相鄰的6個位元組儲存，儲存器按位元組編址。那麼，這個陣列的體積是 a 個位元組。
假設儲存陣列元素a[1,0]的第乙個位元組的位址是0，則儲存陣列a的最後乙個元素的第乙個位元組的位址是 b 。若按行儲存，則a[2,4]的第乙個位元組的位址是 c 。若按列儲存，則a[5,7]的第乙個位元組的位址是 d 。
供選擇的答案
a～d：①12 ② 66 ③ 72 ④ 96 ⑤ 114 ⑥ 120
⑦ 156 ⑧ 234 ⑨ 276 ⑩ 282 （11）283 （12）288
答案：abcd=12, 10, 3, 9
三、簡答題（每小題5分，共15分）
1. 【其他教材】已知二維陣列am,m採用按行優先順序存放，每個元素佔k個儲存單元，並且第乙個元素的儲存位址為loc(a11)，請寫出求loc(aij)的計算公式。如果採用列優先順序存放呢？
解：公式教材已給出，此處雖是方陣，但行列公式仍不相同；
按行儲存的元素位址公式是： loc(aij)= loc(a11) +[ (i-1)*m+(j-1) ] * k
按列儲存的元素位址公式是： loc(aij)= loc(a11) +[ (j-1)*m+(i-1) ] * k
2.【全國專公升本資格考試】遞迴演算法比非遞迴演算法花費更多的時間，對嗎？為什麼？
答：不一定。時間複雜度與樣本個數n有關，是指最深層的執行語句耗費時間，而遞迴演算法與非遞迴演算法在最深層的語句執行上是沒有區別的，迴圈的次數也沒有太大差異。
僅僅是確定迴圈是否繼續的方式不同，遞迴用棧隱含迴圈次數，非遞迴用迴圈變數來顯示迴圈次數而已。
四、計算題（每題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』,q)＝』i am a worker』
② 因為 substring(s,6,2)＝『a 』；substring(s,7,8)＝『 student』
concat(t,substring(s,7,8))＝』good student』
所以concat(substring(s,6,2), concat(t,substring(s,7,8)))＝『a good student』
2. （p60 4-18）用三元組表表示下列稀疏矩陣：
解：參見填空題4. 三元素組表中的每個結點對應於稀疏矩陣的乙個非零元素，它包含有三個資料項，分別表示該元素的行下標 、 列下標和元素值 。
所以（1）可列表為2）可列表為：
3. （p60 4-19）下列各三元組表分別表示乙個稀疏矩陣，試寫出它們的稀疏矩陣。
解：（1）為6×4矩陣，非零元素有6個。 （2）為4×5矩陣，非零元素有5個
五、演算法設計題（每題10分，共30分）
1. 【嚴題集4.12③】 編寫乙個實現串的置換操作replace(&s, t, v)的演算法。
資料結構C語言版第3章習題答案
第3章棧和佇列自測卷答案 一 填空題 每空1分，共15分 1.向量 棧和佇列都是線性結構，可以在向量的任何位置插入和刪除元素 對於棧只能在棧頂插入和刪除元素 對於佇列只能在隊尾插入和隊首刪除元素。2.棧是一種特殊的線性表，允許插入和刪除運算的一端稱為棧頂 不允許插入和刪除運算的一端稱為棧底 3.佇列...
資料結構C語言版第2章練習題
第2章線性表練習題 一 填空 1.在順序表中插入或刪除乙個元素，需要平均移動元素，具體移動的元素個數 與有關。2.線性表中結點的集合是的，結點間的關係是的。3.向乙個長度為n的向量的第i個元素 1 i n 1 之前插入乙個元素時，需向後移動個元素。4.向乙個長度為n的向量中刪除第i個元素 1 i n...
資料結構 C語言版
考試大綱將陸續公布 計算機應用基礎考試大綱 主要考查計算機應用基礎知識，參考參考用書課後練習內容。其它同型別的計算機應用基礎教材均可作為複習用書 高等數學考試大綱 一 函式 二 極限 1 數列極限的概念 2 數列極限的性質 3 函式極限的概念 4 函式極限的定理 5 無窮小量和無窮大量 6 兩個重要...