【正文】 針是指向鏈表中第一個結(jié)點（或為頭結(jié)點或為首元結(jié)點）的指針。否則表示空表的鏈表的頭指針為空。是否設(shè)置頭結(jié)點，是不同的存儲結(jié)構(gòu)表示同一邏輯結(jié)構(gòu)的問題。第3章 棧和隊列一、填空題（每空1分，共15分）1. 向量、棧和隊列都是 線性 結(jié)構(gòu)，可以在向量的 任何 位置插入和刪除元素；對于棧只能在 棧頂 插入和刪除元素；對于隊列只能在 隊尾 插入和 隊首 刪除元素。不允許插入和刪除運算的一端稱為 棧底 。4. 在一個循環(huán)隊列中，隊首指針指向隊首元素的 前一個 位置。6. 向棧中壓入元素的操作是先 存入元素 ，后 移動棧頂指針 。8. 帶表頭結(jié)點的空循環(huán)雙向鏈表的長度等于 0 。）（每小題1分，共10分）（）1. 線性表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一個復(fù)雜類型。（）2. 在表結(jié)構(gòu)中最常用的是線性表，棧和隊列不太常用。（√）3. 棧是一種對所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。 正確，都是線性邏輯結(jié)構(gòu)，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。 錯，棧是邏輯結(jié)構(gòu)的概念，是特殊殊線性表，而鏈表是存儲結(jié)構(gòu)概念，二者不是同類項。 錯，他們都是線性邏輯結(jié)構(gòu)，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。 （√）8. 兩個棧共享一片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出機(jī)會，應(yīng)把兩個棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。錯，后半句不對。 錯，有可能。（若不要求順序出棧，則輸出序列不確定）（B）3. 判定一個棧ST（最多元素為m0）為空的條件是 Ａ．STtop0 Ｂ．STtop=0 Ｃ．STtopm0 Ｄ．STtop=m0（A）4. 判定一個隊列QU（最多元素為m0）為滿隊列的條件是 Ａ．QUrear － QUfront = = m0 Ｂ．QUrear － QUfront －1= = m0 Ｃ．QUfront = = QUrear Ｄ．QUfront = = QUrear+1解：隊滿條件是元素個數(shù)為m0。當(dāng)然，更正確的答案應(yīng)該取模，即：QUfront = = (QUrear+1)% m0（D）5．?dāng)?shù)組Ｑ［ｎ］用來表示一個循環(huán)隊列，ｆ為當(dāng)前隊列頭元素的前一位置，ｒ為隊尾元素的位置，假定隊列中元素的個數(shù)小于ｎ，計算隊列中元素的公式為（Ａ）r－f。 （Ｃ）n＋r－f。設(shè)有4個數(shù)據(jù)元素aaa3和a4，對他們分別進(jìn)行棧操作或隊操作。假設(shè)?；蜿牭某跏紶顟B(tài)都是空。經(jīng)操作后，最后在棧中或隊中的元素還有 E 個。棧是一種線性表，它的特點是 A 。往棧中推入（PUSH）一個新元素時，變量T的值 B ；從棧中彈出（POP）一個元素時，變量T的值 C 。供選擇的答案：A： ① 先進(jìn)先出 ②后進(jìn)先出 ③進(jìn)優(yōu)于出 ④出優(yōu)于進(jìn) ⑤ 隨機(jī)進(jìn)出B，C： ① 加1 ②減1 ③不變 ④清0 ⑤ 加2 ⑥減2D：① a,b ②b,c ③c,a ④b,a ⑤ c,b ⑥ a,cE：① n+1 ②n+2 ③ n ④ n1 ⑤ n2答案：ABCDE=2, 2, 1, 6, 4注意，向地址的高端生長，稱為向上生成堆棧；向地址低端生長叫向下生成堆棧，本題中底部為n，向地址的低端遞減生成，稱為向下生成堆棧。在做進(jìn)棧運算時，應(yīng)先判別棧是否 A ；在做退棧運算時，應(yīng)先判別棧是否 B 。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個棧共享一片連續(xù)的內(nèi)存空間時，應(yīng)將兩棧的 D 分別設(shè)在這片內(nèi)存空間的兩端，這樣，只有當(dāng) E 時，才產(chǎn)生上溢。答：相同點：都是線性結(jié)構(gòu)，都是邏輯結(jié)構(gòu)的概念。不同點：①運算規(guī)則不同，線性表為隨機(jī)存取，而棧是只允許在一端進(jìn)行插入、刪除運算，因而是后進(jìn)先出表LIFO；隊列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運算，因而是先進(jìn)先出表FIFO。，2，3，4的四輛列車，順序進(jìn)入一個棧式結(jié)構(gòu)的車站，具體寫出這四輛列車開出車站的所有可能的順序。① 全進(jìn)之后再出情況，只有1種：4，3，2，1② 進(jìn)3個之后再出的情況，有3種：3,4,2,1 3,2,4,1 3,2,1,4③ 進(jìn)2個之后再出的情況，有5種：2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4④ 進(jìn)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’則不是回文。哪種方式最好，要具體情況具體分析。（但堆棧是先減后壓還是……）若正文是單鏈表形式存儲，則等同于隊列，需開輔助空間，可以從鏈?zhǔn)组_始入棧，全部壓入后再依次輸出。采用循環(huán)隊列是解決假溢出的途徑。* 使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度）。判斷循環(huán)隊列隊空標(biāo)志是： f=rear 隊滿標(biāo)志是：f=(r+1)%N（序號從0到39），現(xiàn)經(jīng)過一系列的入隊和出隊運算后，有① front=11，rear=19。至少要寫出思路）* 按照四則運算加、減、乘、除和冪運算（↑）優(yōu)先關(guān)系的慣例，并仿照教材例32的格式，畫出對下列算術(shù)表達(dá)式求值時操作數(shù)棧和運算符棧的變化過程：A－BC/D+E↑F答：* 寫出下列程序段的輸出結(jié)果（棧的元素類型SElem Type為char）。Char x,y。X=’c’。Push(S,x)。 Push(S,y)。 Push(S,’t’)。Pop(S,x)。while(!StackEmpty(S)){ Pop(S,y)。 }。}答：輸出為“stack”。void main( ){Queue Q。Char x=’e’。EnQueue (Q,’h’)。 EnQueue (Q, y)。EnQueue (Q,x)。 EnQueue (Q,’a’)。printf(y)。Printf(x)。* 【②】簡述以下算法的功能（棧和隊列的元素類型均為int）。Q){Stack S。InitStack(S)。 Push(S,d)。while(!StackEmpty(S)){ Pop(S,d)。 }}答：該算法的功能是：利用堆棧做輔助，將隊列中的數(shù)據(jù)元素進(jìn)行逆置。至少要寫出思路）[m]存放循環(huán)隊列的元素。試編寫相應(yīng)的入隊和出隊的算法。‘’為結(jié)束符的字符序列是否是“回文”。InitQueue(Q)。39。EnQueue(Q,c)。DeQueue(Q,b))。 }return OK。 串和數(shù)組 自測卷答案 姓名班級 一、填空題（每空1分，共20分）1. 不包含任何字符（長度為0）的串由一個或多個空格（僅由空格符）組成的串（①，簡答題：簡述空串和空格串的區(qū)別）2. 設(shè)S=“A。 20 。 稱為目標(biāo)串，5. 設(shè)目標(biāo)T=”abccdcdccbaa”，模式P=“cdcc”，則第次匹配成功。 (nm+1)*m7. 假設(shè)有二維數(shù)組A68，每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。 288 B ；末尾元素A57的第一個字節(jié)地址為 1282 ；若按行存儲時，元素A14的第一個字節(jié)地址為 ；若按列存儲時，元素A47的第一個字節(jié)地址為A57 第6行第8列(注：數(shù)組是從0行0列還是從1行1列計算起呢？由末單元為A57可知，是從0行0列開始！)8. 〖00年計算機(jī)系考研題〗設(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＝8950 、：（1） GetHead【((a,b),(c,d))】=== (a, b) //頭元素不必加括號（2） GetHead【GetTail【((a,b),(c,d))】】===二、單選題（每小題1分，共15分）（ B Ｃ．可以鏈?zhǔn)酱鎯Γ?. 〖李〗設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作： Ａ．連接 Ｃ．求子串 Ｄ．求串長（ D Ｄ．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’。）4. 〖01年計算機(jī)系考研題〗假設(shè)有60行70列的二維數(shù)組a[1…60, 1…70]以列序為主序順序存儲，其基地址為10000，每個元素占2個存儲單元，那么第32行第58列的元素a[32,58]的存儲地址為（無第0行第0列元素） Ａ．16902 Ｃ．14454Ｄ．答案A, B, C均不對答：此題與填空題第8小題相似。 B )5. 設(shè)矩陣A是一個對稱矩陣，為了節(jié)省存儲，將其下三角部分（如下圖所示）按行序存放在一維數(shù)組B[ 1, n(n1)/2 ]中，對下三角部分中任一元素ai,j(i≤j), 在一維數(shù)組B中下標(biāo)k的值是：Ａ．i(i1)/2+j1 Ｃ．i(i+1)/2+j1先用第一個元素去套用，可能有B和C；再用第二個元素去套用B和C，B=2而C＝3（不符）；所以選B有一個二維數(shù)組A，行下標(biāo)的范圍是0到8，列下標(biāo)的范圍是1到5，每個數(shù)組元素用相鄰的4個字節(jié)存儲。假設(shè)存儲數(shù)組元素A[0,1]的第一個字節(jié)的地址是0。 A 。 B 和 。 D 和供選擇的答案：A～E：①28 ② 44 ③ 76 ④ 92 ⑨ 184 ⑩ 188答案：ABCDE=8, 5, 67.【94程P12】 有一個二維數(shù)組A，行下標(biāo)的范圍是1到6，列下標(biāo)的范圍是0到7，每個數(shù)組元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。假設(shè)存儲數(shù)組元素A[1,0]的第一個字節(jié)的地址是0，則存儲數(shù)組A的最后一個元素的第一個字節(jié)的地址是 B 。 C 。 D 。 ⑤ 114 ⑥ 120 （11）283 （12）288答案：ABCD=12, 3, ,m采用按行優(yōu)Loc(a11)，請寫出求Loc(aij)的計算公式。時間復(fù)雜度與樣本個數(shù)n有關(guān)，是指最深層的執(zhí)在最深層的語句執(zhí)行上是沒有區(qū)別的，循環(huán)的次數(shù)也沒有太大差異。四、計算題（每題5分，共20分）1.解：① Replace(s,’STUDENT’,q)＝’I AM A WORKER’② 因為 、 。53233685467858123. （P60 419）下列各三元組表分別表示一個稀疏矩陣，試寫出它們的稀疏矩陣。 （2）為45矩陣，非零元素有5個0 0 12 0 0 3 0 0 4 0 6 01 00 00 60 0 （ ） 2. 二叉樹中每個結(jié)點的兩棵子樹的高度差等于 1 。 （ ） 4. 二叉樹中每個結(jié)點有兩棵非空子樹或有兩棵空子樹。 （應(yīng)當(dāng)是二叉排序樹的特點） （ ） 6. 二叉樹中所有結(jié)點個數(shù)是 2 k1 1 ，其中 k 是樹的深度。 （ ） 8. 對于一棵非空二叉樹，它的根結(jié)點作為第一層，則它的第 i 層上最多能有 2 i — 1 個結(jié)點。 （正確。由于二叉樹中，除根結(jié)點外，每一個結(jié)點有且僅有一個雙親，所以只有 n1 個結(jié)點的鏈域存放指向非空子女結(jié)點的指針，還有 n+1 個空指針。 （ √ ） 10. 〖 01 年計算機(jī)系研題〗 具有 12 個結(jié)點的完全二叉樹有 5 個度為 2 的結(jié)點。 二、填空（每空 1 分，共 15 分） 1 ． 由３個結(jié)點所構(gòu)成的二叉樹有 5 種形態(tài)。 2. 【計算機(jī)研 2000 】 一棵深度為 6 的滿二叉樹有 n 1 +n 2 =0+ n 2 = n 0 1=31 個分支結(jié)點和 2 61 =32 個葉子。 （ 注：用