【正文】 14的第一個(gè)字節(jié)地址為 (8+4)6+1000=1072 ；若按列存儲(chǔ)時(shí)，元素A47的第一個(gè)字節(jié)地址為 (67＋4)6＋1000）＝1276 。6. 若n為主串長(zhǎng)，m為子串長(zhǎng)，則串的古典（樸素）匹配算法最壞的情況下需要比較字符的總次數(shù)為 (nm+1)*m 。4. 子串的定位運(yùn)算稱為串的模式匹配； 被匹配的主串 稱為目標(biāo)串， 子串 稱為模式。（①，簡(jiǎn)答題：簡(jiǎn)述空串和空格串的區(qū)別）2. 設(shè)S=“A。 }}答：該算法的功能是：利用堆棧做輔助，將隊(duì)列中的數(shù)據(jù)元素進(jìn)行逆置。while(!StackEmpty(S)){ Pop(S,d)。 Push(S,d)。InitStack(S)。Q){Stack S。3. 【②】簡(jiǎn)述以下算法的功能（棧和隊(duì)列的元素類型均為int）。Printf(x)。printf(y)。 EnQueue (Q,’a’)。 EnQueue (Q,x)。 EnQueue (Q, y)。EnQueue (Q,’h’)。Char x=’e’。void main( ){Queue Q。}答：輸出為“stack”。 }。while(!StackEmpty(S)){ Pop(S,y)。Pop(S,x)。 Push(S,’t’)。 Push(S,y)。Push(S,x)。X=’c’。Char x,y。 ② front=19，rear=11；問(wèn)在這兩種情況下，循環(huán)隊(duì)列中各有元素多少個(gè)？答：用隊(duì)列長(zhǎng)度計(jì)算公式： (N＋r－f)% N① L=（40＋19－11）% 40=8 ② L=（40＋11－19）% 40=321. 【②】寫(xiě)出下列程序段的輸出結(jié)果（棧的元素類型SElem Type為char）。我們常采用法②，即隊(duì)頭指針、隊(duì)尾指針中有一個(gè)指向?qū)嵲?，而另一個(gè)指向空閑元素。另外，解決隊(duì)滿隊(duì)空的辦法有三：① 設(shè)置一個(gè)布爾變量以區(qū)別隊(duì)滿還是隊(duì)空；② 浪費(fèi)一個(gè)元素的空間，用于區(qū)別隊(duì)滿還是隊(duì)空。4. 【統(tǒng)考書(shū)P60 413】順序隊(duì)的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊(duì)列是空還是滿？答：一般的一維數(shù)組隊(duì)列的尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊(duì)操作，但其實(shí)數(shù)組中還有空位置，這就叫“假溢出”。若正文在機(jī)內(nèi)已是順序存儲(chǔ)，則直接用線性表從后往前讀取即可，或?qū)⒍褩ｍ旈_(kāi)到數(shù)組末尾，然后直接用POP動(dòng)作實(shí)現(xiàn)。假設(shè)一字符序列已存入計(jì)算機(jī)，請(qǐng)分析用線性表、堆棧和隊(duì)列等方式正確輸出其回文的可能性？答：線性表是隨機(jī)存儲(chǔ)，可以實(shí)現(xiàn)，靠循環(huán)變量（j）從表尾開(kāi)始打印輸出；堆棧是后進(jìn)先出，也可以實(shí)現(xiàn)，靠正序入棧、逆序出棧即可；隊(duì)列是先進(jìn)先出，不易實(shí)現(xiàn)。劉答：至少有14種。② 用途不同，堆棧用于子程調(diào)用和保護(hù)現(xiàn)場(chǎng)，隊(duì)列用于多道作業(yè)處理、指令寄存及其他運(yùn)算等等。都可以用順序存儲(chǔ)或鏈表存儲(chǔ)；棧和隊(duì)列是兩種特殊的線性表，即受限的線性表，只是對(duì)插入、刪除運(yùn)算加以限制。供選擇的答案：A，B：①空 ② 滿 ③ 上溢 ④ 下溢C： ①n1 ② n ③ n+1 ④ n/2D： ① 長(zhǎng)度 ②深度 ③ 棧頂 ④ 棧底E：①兩個(gè)棧的棧頂同時(shí)到達(dá)?？臻g的中心點(diǎn) ②其中一個(gè)棧的棧頂?shù)竭_(dá)棧空間的中心點(diǎn) ③兩個(gè)棧的棧頂在達(dá)?？臻g的某一位置相遇 ④兩個(gè)棧均不空，且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底答案：ABCDE＝2, 1, 2, 4, 3四、簡(jiǎn)答題（每小題4分，共20分）1. 【①①】說(shuō)明線性表、棧與隊(duì)的異同點(diǎn)。當(dāng)棧中元素為n個(gè)，做進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說(shuō)明該棧的最大容量為 C 。8. 【91初程P77】 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。設(shè)?？諘r(shí)，有輸入序列a，b，c，經(jīng)過(guò)PUSH，POP，PUSH，PUSH，POP操作后，從棧中彈出的元素的序列是 D ，變量T的值是 E 。設(shè)用一維數(shù)組A[1,…,n]來(lái)表示一個(gè)棧，A[n]為棧底，用整型變量T指示當(dāng)前棧頂位置，A[T]為棧頂元素。供選擇的答案：A～D：①a1 ②a2 ③ a3 ④a4E： ①1 ②2 ③ 3 ④ 0答：ABCDE＝2, 4, 1, 2, 27. 【94初程P75】 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)?，F(xiàn)要進(jìn)行的棧操作是進(jìn)棧兩次，出棧一次，再進(jìn)棧兩次，出棧一次；這時(shí)，第一次出棧得到的元素是 A ，第二次出棧得到的元素是 B 是；類似地，考慮對(duì)這四個(gè)數(shù)據(jù)元素進(jìn)行的隊(duì)操作是進(jìn)隊(duì)兩次，出隊(duì)一次，再進(jìn)隊(duì)兩次，出隊(duì)一次；這時(shí)，第一次出隊(duì)得到的元素是 C ，第二次出隊(duì)得到的元素是 D 。在進(jìn)?；蜻M(jìn)隊(duì)操作時(shí)，按aaaa4次序每次進(jìn)入一個(gè)元素。 （Ｄ）（n＋r－f）% n6. 【98初程P71】 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。 （Ｂ）（n＋f－r）% n。由于約定滿隊(duì)時(shí)隊(duì)首指針與隊(duì)尾指針相差1，所以不必再減1了，應(yīng)當(dāng)選A。三、單項(xiàng)選擇題（每小題1分，共20分）（ B ）1. 〖00年元月統(tǒng)考題〗棧中元素的進(jìn)出原則是 Ａ．先進(jìn)先出 Ｂ．后進(jìn)先出 Ｃ．?？談t進(jìn) Ｄ．棧滿則出（ C ）2. 〖李春葆〗若已知一個(gè)棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為 Ａ．i Ｂ．n=i Ｃ．ni+1 Ｄ．不確定解釋：當(dāng)p1=n，即n是最先出棧的，根據(jù)棧的原理，n必定是最后入棧的（事實(shí)上題目已經(jīng)表明了），那么輸入順序必定是1，2，3，…，n，則出棧的序列是n，…，3，2，1。（ ）10. 一個(gè)棧的輸入序列是12345，則棧的輸出序列不可能是12345。 （ ）9. 隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。（ √ ）7. 棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。（ ）6. 棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。（ ）5. 棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。（ √ ）4. 對(duì)于不同的使用者，一個(gè)表結(jié)構(gòu)既可以是棧，也可以是隊(duì)列，也可以是線性表。 錯(cuò)，不一定吧？調(diào)用子程序或函數(shù)常用，CPU中也用隊(duì)列。 錯(cuò)，線性表是邏輯結(jié)構(gòu)概念，可以順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)，與元素?cái)?shù)據(jù)類型無(wú)關(guān)。L=head頭結(jié)點(diǎn)R=headhead解：二、判斷正誤（判斷下列概念的正確性，并作出簡(jiǎn)要的說(shuō)明。7. 從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是 先 移動(dòng)隊(duì)首指針 ，后 取出元素 。5. 在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有 n1 個(gè)元素。3. 隊(duì)列 是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。2. 棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為 棧頂 。datalink 頭指針 首元結(jié)點(diǎn)簡(jiǎn)而言之，頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針；頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長(zhǎng)等信息（內(nèi)放頭指針？那還得另配一個(gè)頭指針?。。。┦自亟Y(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。是否設(shè)置頭結(jié)點(diǎn)，是不同的存儲(chǔ)結(jié)構(gòu)表示同一邏輯結(jié)構(gòu)的問(wèn)題。否則表示空表的鏈表的頭指針為空。頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針。在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是什么？答：首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。若線性表的長(zhǎng)度變化不大，且其主要操作是查找，則采用順序表；若線性表的長(zhǎng)度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。缺點(diǎn)：存儲(chǔ)密度?。?），存儲(chǔ)空間利用率低。缺點(diǎn)：插入或刪除元素時(shí)不方便。在什么情況下用順序表比鏈表好？答：① 順序存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲(chǔ)單元的地址必須是連續(xù)的。a24224。（Ａ）需經(jīng)常修改Ｌ中的結(jié)點(diǎn)值 （Ｂ）需不斷對(duì)Ｌ進(jìn)行刪除插入 （Ｃ）Ｌ中含有大量的結(jié)點(diǎn) （Ｄ）Ｌ中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜（ C ）9． 單鏈表的存儲(chǔ)密度（Ａ）大于1； （Ｂ）等于1； （Ｃ）小于1； （Ｄ）不能確定（ B ）10． 設(shè)aaa3為3個(gè)結(jié)點(diǎn)，整數(shù)P0，3，4代表地址，則如下的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為P034P0224。鏈?zhǔn)酱鎯?chǔ)就無(wú)需一致。（后一節(jié)介紹）（ ）10. 線性表的邏輯順序與存儲(chǔ)順序總是一致的。錯(cuò)誤。線性表有兩種存儲(chǔ)方式，在順序存儲(chǔ)時(shí)，邏輯上相鄰的元素在存儲(chǔ)的物理位置次序上也相鄰。（ ）8. 線性表在順序存儲(chǔ)時(shí)，邏輯上相鄰的元素未必在存儲(chǔ)的物理位置次序上相鄰。錯(cuò)，線性表有兩種存儲(chǔ)方式，順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。順序存儲(chǔ)方式插入、刪除運(yùn)算效率較低，在表長(zhǎng)為n的順序表中，插入和刪除一個(gè)數(shù)據(jù)元素，平均需移動(dòng)表長(zhǎng)一半個(gè)數(shù)的數(shù)據(jù)元素。順序表才適合隨機(jī)存取，鏈表恰恰適于“順藤摸瓜”（ ）6. 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。（ ）5. 順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。（ ）4. 線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。（ ）3. 鏈表的刪除算法很簡(jiǎn)單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會(huì)自動(dòng)地將后續(xù)的各個(gè)單元向前移動(dòng)。（ ）2. 鏈表的物理存儲(chǔ)結(jié)構(gòu)具有同鏈表一樣的順序。鏈表中的結(jié)點(diǎn)可含多個(gè)指針域，分別存放多個(gè)指針。二、判斷正誤（在正