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

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

2、與它們出棧的順序相反。(X)(8)對采用鏈式存儲結(jié)構(gòu)的堆棧進行操作不必判斷溢出。(X)(9)給出順序堆棧的棧頂元素位置的指針是一個指針類型的變量。(X)(10)判斷順序堆棧是否為空的標志是top是否等于0(top為棧頂指針)。(√)(11)插入和刪除操作比較簡單是鏈接堆棧和鏈接隊列的優(yōu)點之一。(√)(12)n個元素進隊的順序與它們出隊的順序一定是相同的。(√)(13)沒有任何元素的隊列稱為空隊?？贞犛貌恢狀^指針與隊尾指針。(X)(14

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

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

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

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