第3課棧隊列和數(shù)組

1、第三課 棧、隊列和數(shù)組一 選擇題1對于棧操作數(shù)據(jù)的原則是（ ）。A先進先出 B后進先出 C后進后出 D不分順序2一個棧的輸入序列為123n，若輸出序列的第一個元素是n，輸出第i（1=i0) ? x* f(x-1):2);int i;i =f(f(1);A2 B4 C8 D無限遞歸9表達式a*(b+c)-d的后綴表達式是（ ）。Aabcd*+- Babc+*d- Cabc*+d- D-+*abcd10表達式3*2(4+2*2-6*3)-5求值過程中當掃描到6時，對象棧和算符棧為（ ），其中為乘冪。A3,2,4,1,1；(*(+*- B3,2,8；(*- C3,2,4,2,2；(*(- D3,2,

2、8；(*(-11用不帶頭結(jié)點的單鏈表存儲隊列時，其隊頭指針指向隊頭結(jié)點，其隊尾指針指向隊尾結(jié)點，則在進行刪除操作時（ ）。A僅修改隊頭指針 B僅修改隊尾指針C隊頭、隊尾指針都要修改 D隊頭、隊尾指針都可能要修改12遞歸過程或函數(shù)調(diào)用時，處理參數(shù)及返回地址，要用一種稱為（ ）的數(shù)據(jù)結(jié)構(gòu)。A隊列 B多維數(shù)組 C棧 D線性表13循環(huán)隊列A0.m-1存放其元素值，用front和rear分別表示隊頭和隊尾，則當前隊列中的元素數(shù)是（ ）。A(rear-front+m)%m Brear-front+1 Crear-front-1 Drear-front14循環(huán)隊列存儲在數(shù)組A0.m中，則入隊時的操作為（ ）

3、。Arear=rear+1 Brear=(rear+1) mod (m-1)Crear=(rear+1) mod m Drear=(rear+1) mod (m+1)15若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為多少？（ ）A1和5 B2和4 C4和2 D5和116最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是（ ）。A(rear+1) MOD n=front Brear=frontCrear+1=front D(rear-l) MOD n=front1

4、7設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1，e2，e3，e4,e5和e6依次通過棧S，一個元素出棧后即進隊列Q，若6個元素出隊的序列是e2，e4，e3，e6，e5，e1則棧S的容量至少應(yīng)該是（ ）。A6 B4 C3 D218數(shù)組A0.4,-1.-3,5.7中含有元素的個數(shù)（ ）。A55 B45 C36 D1619設(shè)二維數(shù)組A1.m，1.n（即m行n列）按行存儲在數(shù)組B1.m*n中，則二維數(shù)組元素Ai，j在一維數(shù)組B中的下標為（ ）。A(i-1)*n+j B(i-1)*n+j-1 Ci*(j-1) Dj*m+i-120設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，

5、其存儲地址為1，每個元素占一個地址空間，則a85的地址為（ ）。A13 B33 C18 D4021設(shè)有數(shù)組Ai,j，數(shù)組的每個元素長度為3字節(jié)，i的值為1 到8 ，j的值為1 到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當用以列為主存放時，元素A5，8的存儲首地址為（ ）。ABA+141 BBA+180 CBA+222 DBA+22522數(shù)組A0.5,0.6的每個元素占五個字節(jié)，將其按列優(yōu)先次序存儲在起始地址為1000的內(nèi)存單元中，則元素A5，5的地址是（ ）。A1175 B1180 C1205 D121023將一個A1.100，1.100的三對角矩陣，按行優(yōu)先存入一維數(shù)組B1298中，A中元素

6、A66,65（即該元素下標i=66，j=65），在B數(shù)組中的位置K為（ ）。A198 B195 C197 D19624對稀疏矩陣進行壓縮存儲目的是（ ）。A便于進行矩陣運算 B便于輸入和輸出 C節(jié)省存儲空間 D降低運算的時間復(fù)雜度25有一個100*90的稀疏矩陣，非0元素有10個，設(shè)每個整型數(shù)占2字節(jié)，則用三元組表示該矩陣時，所需的字節(jié)數(shù)是（ ）。A60 B66 C18000 D33二、應(yīng)用題1有5個元素，其入棧次序為A、B、C、D、E，在各種可能的出棧次序中，以元素C，D最先出棧（即C第一個且D第二個出棧）的次序有哪幾個？2如果輸入序列為1 2 3 4 5 6，試問能否通過棧結(jié)構(gòu)得到以下兩個

7、序列:4 3 5 6 1 2和1 3 5 4 2 6，請說明為什么不能或如何才能得到。3試證明：若借助棧由輸入序列1,2,n得到輸出序列為P1,P2,Pn（它是輸入序列的一個排列），則在輸出序列中不可能出現(xiàn)這樣的情形：存在著ijk,使PjPkPi。參考答案：如果ij，則對于pipj的情況，則說明要將pj壓到pi之上，也就是在pj出棧之后pi才能出棧。這就說明，對于ijk，不可能出現(xiàn)pjpkpi的輸出序列。換句話說，對于輸入序列1，2，3，不可能出現(xiàn)3，1，2的輸出序列。4用棧實現(xiàn)將中綴表達式8-(3+5)*(5-6/2)轉(zhuǎn)換成后綴表達式，畫出棧的變化過程圖。參考答案：中綴表達式8-(3+5)*

8、(5-6/2）的后綴表達式是： 8 3 5 + 5 6 2 / - * -表達式生成過程為：中綴表達式exp1轉(zhuǎn)為后綴表達式exp2的規(guī)則如下：設(shè)操作符棧s，初始為空棧后，壓入優(yōu)先級最低的操作符#。對中綴表達式從左向右掃描，遇操作數(shù)，直接寫入exp2；若是操作符（記為w），分如下情況處理，直至表達式exp1掃描完畢。（1）w為一般操作符（+，-，*，/等），要與棧頂操作符比較優(yōu)先級，若w優(yōu)先級高于棧頂操作符，則入棧；否則，棧頂運算符退棧到exp2，w再與新棧頂操作符作上述比較處理，直至w入棧。（2）w為左括號（），w入棧。（3）w為右括號（），操作符棧退棧并進入exp2，直到碰到左括號為止，左

9、括號退棧（不能進入exp2），右括號也丟掉，達到exp2中消除括號的目的。（4）w為#，表示中綴表達式exp1結(jié)束，操作符棧退棧到exp2，直至碰到#，退棧，整個操作結(jié)束。這里，再介紹一種簡單方法。中綴表達式轉(zhuǎn)為后綴表達式有三步：首先，將中綴表達式中所有的子表達式按計算規(guī)則用嵌套括號括起來；接著，順序?qū)⒚繉ㄌ栔械倪\算符移到相應(yīng)括號的后面；最后，刪除所有括號。例如，將中綴表達式8-(3+5)*(5-6/2）轉(zhuǎn)為后綴表達式。按如上步驟：執(zhí)行完上面第一步后為：(8-(3+5)*(5-(6/2)；執(zhí)行完上面第二步后為：(8(35)+(5(62)/)-)*)- ；執(zhí)行完上面第三步后為：8 3 5 +

10、5 6 2 / - * - 。可用類似方法將中綴表達式轉(zhuǎn)為前綴表達式。5設(shè)輸入元素為1、2、3、P和A，輸入次序為123PA。元素經(jīng)過棧后達輸出序列，當所有元素均到達輸出序列后，有哪些序列可以作為高級語言的變量名。6簡述如下算法功能。Status ex1(Stack S,int e) InitStack(T); while(!StackEmpty(S) Pop(S,d); if(d!=e) Push(T,d); while(!StackEmpty(T) Pop(T,d); Push(S,d); /ex17寫出如下程序段輸出結(jié)果。void ex3() char x=e,y=c; InitQueu

11、e(Q); 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); /while printf(x);/ex38將如下遞歸過程改寫為非遞歸過程。void test(int &sum) int x; scanf(x); if (x=0) sum=0; else test(sum); sum+=x; printf(sum);int ack(int m,int n) if

12、 (!m) return n+1; else if(!n) return ack(m-1,1); else return ack(m-1,ack(m,n-1);/ack9三維數(shù)組A1.10,-2.6,2.8的每個元素的長度為4個字節(jié)，試問該數(shù)組要占多少個字節(jié)的存儲空間？如果數(shù)組元素以行優(yōu)先的順序存貯，設(shè)第一個元素的首地址是100，試求元素A5,0,7 的存貯首地址。10若按照壓縮存儲的思想將nn階的對稱矩陣A的下三角部分（包括主對角線元素）以行序為主序方式存放于一維數(shù)組B1.n(n+1)/2中，那么，A中任一個下三角元素aij(ij),在數(shù)組B中的下標位置k是什么？A中任一個下三角元素aij(

13、ij),在數(shù)組B中的下標位置k是什么？11設(shè)有三對角矩陣(ai,j)mn,將其三條對角線上的元素逐行的存于數(shù)組B(1:3n-2)中，使得Bk=ai,j，求：用i,j表示k的下標變換公式；若n=103，每個元素占用L個單元，則用BK方式比常規(guī)存儲節(jié)省多少單元。12設(shè)有矩陣且a=，執(zhí)行下列語句后，矩陣和的結(jié)果分別是什么？for( i=1 ;i=3 ; i+ )for( j=1 ;j=3 ; j+ ) cij=aaij,aji; for( i=1 ;i=3 ; i+ )for( j=1 ;j=3 ; j+ ) aij=aaij,aji;三、算法設(shè)計題1設(shè)有兩個棧S1,S2都采用順序棧方式，并且共享一

14、個存儲區(qū)0.maxsize-1，為了盡量利用空間，減少溢出的可能，可采用棧頂相向，迎面增長的存儲方式。試設(shè)計S1,S2有關(guān)入棧和出棧的操作算法。2設(shè)從鍵盤輸入一列整數(shù)：a1, a2, a3，an，試編寫算法實現(xiàn)：用棧結(jié)構(gòu)存儲輸入的整數(shù)，當ai-1時，將ai進棧；當ai=-1時，輸出棧頂整數(shù)并出棧。算法應(yīng)對異常情況（入棧滿等）給出相應(yīng)的信息。3假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。下面所示的序列中哪些是合法的？AIOIIOIOO BIOOIOIIO CIIIOIOIO DIIIOO

15、IOO。通過對的分析，寫出一個算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入一維數(shù)組中）。4設(shè)計一個算法，判斷一個算術(shù)表達式中的括號是否配對。算術(shù)表達式保存在帶頭結(jié)點的單循環(huán)鏈表中，每個結(jié)點有兩個域：ch和link，其中ch域為字符類型。5如果允許在循環(huán)隊列的兩端都可以進行插入和刪除操作。要求：寫出循環(huán)隊列的類型定義；寫出“從隊尾刪除”和“從隊頭插入”的算法。用一維數(shù)組v0.M-1實現(xiàn)循環(huán)隊列，其中M是隊列長度。設(shè)隊頭指針 front和隊尾指針rear，約定front指向隊頭元素的前一位置，rear指向隊尾元素。定義front=rear時為隊空，(rear+1)%m=front 為隊滿。約定隊頭端入隊向下標小的方向發(fā)展，隊尾端入隊向下標大的方向發(fā)展。6已知Ackermann函數(shù)定義如下，寫出Ack(2,1)的計算過程；寫出計算Ack(m,n)的非遞歸算法。7利用兩個棧S1和S2模擬一個隊列，寫出入隊和出隊的算法（可用棧的基本操作）。8假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾元素結(jié)點（注意不設(shè)頭指針），試編寫相應(yīng)的隊列初始化、入隊和出隊的算法。9設(shè)有大小不等的n個數(shù)據(jù)組（n個數(shù)據(jù)組中數(shù)據(jù)的總數(shù)為m），順序存放在空間區(qū)D內(nèi),每個數(shù)據(jù)占一個存儲單元，數(shù)據(jù)組的首地址由數(shù)組S給出，（