【文章內(nèi)容簡介】 別棧是否 B 。當棧中元素為n個，做進棧運算時發(fā)生上溢，則說明該棧的最大容量為 C 。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個棧共享一片連續(xù)的內(nèi)存空間時，應將兩棧的 D 分別設(shè)在這片內(nèi)存空間的兩端，這樣，只有當 E 時，才產(chǎn)生上溢。供選擇的答案：A，B：①空 ② 滿 ③ 上溢 ④ 下溢C： ①n1 ② n ③ n+1 ④ n/2D： ① 長度 ②深度 ③ 棧頂 ④ 棧底E：①兩個棧的棧頂同時到達?？臻g的中心點 ②其中一個棧的棧頂?shù)竭_?？臻g的中心點 ③兩個棧的棧頂在達棧空間的某一位置相遇 ④兩個棧均不空，且一個棧的棧頂?shù)竭_另一個棧的棧底答案：ABCDE＝2, 1, 2, 4, 3四、簡答題（每小題4分，共20分）1. 【①①】說明線性表、棧與隊的異同點。劉答：相同點：都是線性結(jié)構(gòu)，都是邏輯結(jié)構(gòu)的概念。都可以用順序存儲或鏈表存儲；棧和隊列是兩種特殊的線性表，即受限的線性表，只是對插入、刪除運算加以限制。不同點：①運算規(guī)則不同，線性表為隨機存取，而棧是只允許在一端進行插入、刪除運算，因而是后進先出表LIFO；隊列是只允許在一端進行插入、另一端進行刪除運算，因而是先進先出表FIFO。② 用途不同，堆棧用于子程調(diào)用和保護現(xiàn)場，隊列用于多道作業(yè)處理、指令寄存及其他運算等等。2. 【統(tǒng)考書P60 411，①】設(shè)有編號為1，2，3，4的四輛列車，順序進入一個棧式結(jié)構(gòu)的車站，具體寫出這四輛列車開出車站的所有可能的順序。劉答：至少有14種。① 全進之后再出情況，只有1種：4，3，2，1② 進3個之后再出的情況，有3種，3,4,2,1 3,2,4,1 3,2,1,4③ 進2個之后再出的情況，有5種，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,3,1,4④ 進1個之后再出的情況，有5種，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,33. 【劉自編】假設(shè)正讀和反讀都相同的字符序列為“回文”，例如，‘a(chǎn)bba’和‘a(chǎn)bcba’是回文，‘a(chǎn)bcde’ 和‘a(chǎn)babab’則不是回文。假設(shè)一字符序列已存入計算機，請分析用線性表、堆棧和隊列等方式正確輸出其回文的可能性？答：線性表是隨機存儲，可以實現(xiàn)，靠循環(huán)變量（j）從表尾開始打印輸出；堆棧是后進先出，也可以實現(xiàn)，靠正序入棧、逆序出棧即可；隊列是先進先出，不易實現(xiàn)。哪種方式最好，要具體情況具體分析。若正文在機內(nèi)已是順序存儲，則直接用線性表從后往前讀取即可，或?qū)⒍褩ｍ旈_到數(shù)組末尾，然后直接用POP動作實現(xiàn)。（但堆棧是先減后壓還是……）若正文是單鏈表形式存儲，則等同于隊列，需開輔助空間，可以從鏈首開始入棧，全部壓入后再依次輸出。4. 【統(tǒng)考書P60 413】順序隊的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊列是空還是滿？答：一般的一維數(shù)組隊列的尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊操作，但其實數(shù)組中還有空位置，這就叫“假溢出”。采用循環(huán)隊列是解決假溢出的途徑。另外，解決隊滿隊空的辦法有三：① 設(shè)置一個布爾變量以區(qū)別隊滿還是隊空；② 浪費一個元素的空間，用于區(qū)別隊滿還是隊空。③ 使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度）。我們常采用法②，即隊頭指針、隊尾指針中有一個指向?qū)嵲?，而另一個指向空閑元素。判斷循環(huán)隊列隊空標志是： f=rear 隊滿標志是：f=(r+1)%N5. 【統(tǒng)考書P60 414】設(shè)循環(huán)隊列的容量為40（序號從0到39），現(xiàn)經(jīng)過一系列的入隊和出隊運算后，有① front=11，rear=19。 ② front=19，rear=11；問在這兩種情況下，循環(huán)隊列中各有元素多少個？答：用隊列長度計算公式： (N＋r－f)% N① L=（40＋19－11）% 40=8 ② L=（40＋11－19）% 40=321. 【②】寫出下列程序段的輸出結(jié)果（棧的元素類型SElem Type為char）。void main( ){Stack S。Char x,y。InitStack(S)。X=’c’。y=’k’。Push(S,x)。 Push(S,’a’)。 Push(S,y)。Pop(S,x)。 Push(S,’t’)。 Push(S,x)。Pop(S,x)。 Push(S,’s’)。while(!StackEmpty(S)){ Pop(S,y)。printf(y)。 }。Printf(x)。}答：輸出為“stack”。2. 【②】寫出下列程序段的輸出結(jié)果（隊列中的元素類型QElem Type為char）。void main( ){Queue Q。 Init Queue (Q)。Char x=’e’。 y=’c’。EnQueue (Q,’h’)。 EnQueue (Q,’r’)。 EnQueue (Q, y)。DeQueue (Q,x)。 EnQueue (Q,x)。 DeQueue (Q,x)。 EnQueue (Q,’a’)。 while(!QueueEmpty(Q)){ DeQueue (Q,y)。printf(y)。 }。Printf(x)。}答：輸出為“char”。3. 【②】簡述以下算法的功能（棧和隊列的元素類型均為int）。void algo3(Queue amp。Q){Stack S。 int d。InitStack(S)。while(!QueueEmpty(Q)){ DeQueue (Q,d)。 Push(S,d)。}。while(!StackEmpty(S)){ Pop(S,d)。 EnQueue (Q,d)。 }}答：該算法的功能是：利用堆棧做輔助，將隊列中的數(shù)據(jù)元素進行逆置。第4～5章 串和數(shù)組 一、填空題（每空1分，共20分）1. 不包含任何字符（長度為0）的串 稱為空串； 由一個或多個空格（僅由空格符）組成的串 稱為空白串。（①，簡答題：簡述空串和空格串的區(qū)別）2. 設(shè)S=“A。/document/”，則strlen(s)= 20 , “/”的字符定位的位置為 3 。4. 子串的定位運算稱為串的模式匹配； 被匹配的主串 稱為目標串， 子串 稱為模式。5. 設(shè)目標T=”abccdcdccbaa”，模式P=“cdcc”，則第 6 次匹配成功。6. 若n為主串長，m為子串長，則串的古典（樸素）匹配算法最壞的情況下需要比較字符的總次數(shù)為 (nm+1)*m 。7. 假設(shè)有二維數(shù)組A68，每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。已知A的起始存儲位置（基地址）為1000，則數(shù)組A的體積（存儲量）為 288 B ；末尾元素A57的第一個字節(jié)地址為 1282 ；若按行存儲時，元素A14的第一個字節(jié)地址為 (8+4)6+1000=1072 ；若按列存儲時，元素A47的第一個字節(jié)地址為 (67＋4)6＋1000）＝1276 。(注：數(shù)組是從0行0列還是從1行1列計算起呢？由末單元為A57可知，是從0行0列開始！)8. 〖00年計算機系考研題〗設(shè)數(shù)組a[1…60, 1…70]的基地址為2048，每個元素占2個存儲單元，若以列序為主序順序存儲，則元素a[32,58]的存儲地址為 8950 。答：不考慮0行0列，利用列優(yōu)先公式： LOC(aij)=LOC(ac1，c2)+[(jc2)*(d1c1+1)+ic1)]*L得：LOC(a32,58)=2048+[(581)*(601+1)+321]]*2＝89509. 三元素組表中的每個結(jié)點對應于稀疏矩陣的一個非零元素，它包含有三個數(shù)據(jù)項，分別表示該元素的 行下標 、 列下標 和 元素值 。：（1） GetHead【((a,b),(c,d))】=== (a, b) 。 //頭元素不必加括號（2） GetHead【GetTail【((a,b),(c,d))】】=== (c,d) 。（3） GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== b 。（4） GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== （d） 。二、單選題（每小題1分，共15分）（ B ）1. 〖李〗串是一種特殊的線性表，其特殊性體現(xiàn)在： Ａ．可以順序存儲 Ｂ．數(shù)據(jù)元素是一個字符 Ｃ．可以鏈式存儲 Ｄ．數(shù)據(jù)元素可以是多個字符（ B ）2. 〖李〗設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作： Ａ．連接 Ｂ．模式匹配 Ｃ．求子串 Ｄ．求串長（ D ）3. 〖李〗設(shè)串s1=’ABCDEFG’，s2=’PQRST’，函數(shù)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))的結(jié)果串是： Ａ．BCDEF Ｂ．BCDEFG Ｃ．BCPQRST Ｄ．BCDEFEF解：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