數(shù)據(jù)結(jié)構(gòu)練習(xí)4

1、棧和隊(duì)列棧和隊(duì)列習(xí)題41判斷題(在你認(rèn)為正確的題后的括號(hào)中打√，否則打X)。(1)堆棧和隊(duì)列都是特殊的線性表。(√)(2)堆棧和隊(duì)列都將插入和刪除操作限制在表的端點(diǎn)處進(jìn)行。(√)(3)只允許在表的一端進(jìn)行插入和刪除操作的線性表稱為堆棧。(√)(4)沒有元素的堆棧稱為空棧，空棧用不著棧頂指針。(X)(5)只要堆棧不空，就能任意刪除堆棧的元素。(X)(6)堆棧允許刪除的一端稱為棧頂，而棧底元素是不能刪除的。(X)(7)n個(gè)元素進(jìn)棧的順序一定

2、與它們出棧的順序相反。(X)(8)對(duì)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的堆棧進(jìn)行操作不必判斷溢出。(X)(9)給出順序堆棧的棧頂元素位置的指針是一個(gè)指針類型的變量。(X)(10)判斷順序堆棧是否為空的標(biāo)志是top是否等于0(top為棧頂指針)。(√)(11)插入和刪除操作比較簡(jiǎn)單是鏈接堆棧和鏈接隊(duì)列的優(yōu)點(diǎn)之一。(√)(12)n個(gè)元素進(jìn)隊(duì)的順序與它們出隊(duì)的順序一定是相同的。(√)(13)沒有任何元素的隊(duì)列稱為空隊(duì)?？贞?duì)用不著隊(duì)頭指針與隊(duì)尾指針。(X)(14

3、)元素進(jìn)出隊(duì)列一定滿足“先進(jìn)先出”的規(guī)律。(√)(15)鏈接隊(duì)列不存在溢出問題。(X)(16)在鏈接隊(duì)列中刪除一個(gè)元素是在鏈表的最前端進(jìn)行的。(√)(17)采用循環(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)的隊(duì)列稱為循環(huán)隊(duì)列。(√)(18)堆棧和隊(duì)列都可以用來解決遞歸問題。(X)(19)堆棧和隊(duì)列都不適合采用散列存儲(chǔ)方法。(√)(20)無論是順序隊(duì)列還是鏈接隊(duì)列，插入、刪除操作的時(shí)間復(fù)雜度都是O(1)。(√)42單項(xiàng)選擇題。A(1)堆棧和隊(duì)列的共同之處在于它們具

4、有相同的——。A邏輯特性B物理特性C運(yùn)算方法D元素類型C(2)堆棧和隊(duì)列都是特殊的線性表，其特殊性在于_______。A它們具有一般線性表所沒有的邏輯特性B它們的存儲(chǔ)結(jié)構(gòu)比較特殊C對(duì)它們的使用方法做了限制D它們比一般線性表更簡(jiǎn)單D(3)若5個(gè)元素的出棧序列為1，2，3，4，5，則進(jìn)棧序列可能是——。A2，4，3，1，5B2，3，1，5，4C3，1，4，2，5D3，1，2，5，4A(4)某隊(duì)列初始為空，若它的輸入序列為a，b，c，d，它的

5、輸出序列應(yīng)為——。Aa，b，c，dBd，c，b，aCa，c，b，dDd，a，c，b找公式(5)當(dāng)4個(gè)元素的進(jìn)棧序列給定以后，由這4個(gè)元素組成的可能的出棧序列應(yīng)該有——。A24種B17種C16種D14種(6)設(shè)n個(gè)元素的進(jìn)棧序列為1，2，3，…，n，出棧序列為p1，p2，p3，…，pn，若Pi=n，則B(1≤i2)個(gè)堆棧共享。各棧棧頂指針為top[n]，分別指出各棧棧頂元素的位置；棧底指針為bot[n1]，分別指出各棧棧底元素的位置。初始

6、時(shí)，bop[i]=bot[i]=iROUND(M／n—05)(i=1，2，....，n)其中，ROUND()為四舍五人取整函數(shù)。請(qǐng)寫一算法，該算法向任意指定的第i個(gè)堆棧插入一個(gè)新的元素x。僅當(dāng)M個(gè)空間全部占用時(shí)才產(chǎn)生溢出，并報(bào)告相應(yīng)信息(1≤i≤n)。48設(shè)中綴表達(dá)式E存放于字符數(shù)組中，并以@作為結(jié)束標(biāo)志。請(qǐng)寫出判斷一個(gè)中綴表達(dá)式E中左、右圓括號(hào)是否配對(duì)的算法。49寫出將中綴表達(dá)#(ab)／cd#變換為后綴表達(dá)式的過程中，每讀到一個(gè)單詞