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

1、1 / 7 第三課 棧、隊列和數(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 的后綴表達式是（） 。a abcd*+- babc+*d- cabc*+d- d -+*abcd 10表達式 3*2(4+2*2-6*3)-5求值過程中當(dāng)掃描到6 時，對象棧和算符棧為（） ，其中為乘冪。a3,2,4,1,1；(*(+*- b3,2,8；(*- c3,2,4,2,2

2、；(*(- d3,2,8；(*(- 2 / 7 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 分別表示隊頭和隊尾，則當(dāng)前隊列中的元素數(shù)是（） 。a (rear-front+m)%m brear-front+1 crear-front-1 d rear-front 14循環(huán)隊列存儲在

3、數(shù)組a0.m 中，則入隊時的操作為（） 。a rear=rear+1 brear=(rear+1) mod (m-1) c rear=(rear+1) mod m d rear=(rear+1) mod (m+1) 15若用一個大小為6 的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前rear 和 front 的值分別為0 和 3，當(dāng)從隊列中刪除一個元素，再加入兩個元素后，rear 和 front 的值分別為多少？（）a1 和 5 b 2和 4 c4 和 2 d5 和 1 16最大容量為n 的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是（） 。a (rear+1) mod n=front bre

4、ar=front crear+1=front d(rear-l) mod n=front 17設(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 d2 18數(shù)組 a0.4,-1.-3,5.7 中含有元素的個數(shù)（） 。a55 b45 c36 d 16 19設(shè)二維數(shù)組a1.m ，1.n（即 m 行 n 列）按行存儲在數(shù)組b1.m*n 中，則二維數(shù)組元素 ai ，j在一維數(shù)組b 中的下標(biāo)為（） 。a (i-1)*n+j

5、 b(i-1)*n+j-1 ci*(j-1) dj*m+i-1 20設(shè)有一個10 階的對稱矩陣a，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為（） 。a13 b 33 c18 d40 21設(shè)有數(shù)組ai,j ，數(shù)組的每個元素長度為3 字節(jié)， i 的值為 1 到 8 ，j 的值為 1 到 10，數(shù)組從內(nèi)存首地址ba 開始順序存放，當(dāng)用以列為主存放時，元素a5 ，8的存儲首地址為（） 。aba+141 bba+180 cba+222 dba+225 3 / 7 22數(shù)組 a0.5,0.6 的每個元素占五個字節(jié)，將其按列優(yōu)先次序存儲在起始

6、地址為1000 的內(nèi)存單元中，則元素a5 ，5的地址是（） 。a1175 b1180 c 1205 d1210 23將一個a1.100 ，1.100的三對角矩陣，按行優(yōu)先存入一維數(shù)組b1 298中， a 中元素 a66,65（即該元素下標(biāo)i=66，j=65） ，在 b 數(shù)組中的位置k 為（） 。a198 b195 c197 d196 24對稀疏矩陣進行壓縮存儲目的是（） 。a便于進行矩陣運算b便于輸入和輸出c節(jié)省存儲空間d降低運算的時間復(fù)雜度25有一個 100*90 的稀疏矩陣，非0 元素有 10 個，設(shè)每個整型數(shù)占2 字節(jié)，則用三元組表示該矩陣時，所需的字節(jié)數(shù)是（） 。a60 b 66 c1

7、8000 d33 二、應(yīng)用題1有 5 個元素，其入棧次序為a、b、c、d、e，在各種可能的出棧次序中，以元素c，d最先出棧（即c 第一個且d 第二個出棧）的次序有哪幾個？2如果輸入序列為1 2 3 4 5 6，試問能否通過棧結(jié)構(gòu)得到以下兩個序列: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才

8、能出棧。 這就說明， 對于 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)*(5-6/2 ）的后綴表達式是：8 3 5 + 5 6 2 / - * - 表達式生成過程為：中綴表達式exp1 轉(zhuǎn)為后綴表達式exp2 的規(guī)則如下：設(shè)操作符棧s，初始為空棧后，壓入優(yōu)先級最低的操作符# 。對中綴表達式從左向右（2）8 3 5 + 5 6 2#*#（ 3）8 3 5 + 5 6 2 / -（ 4）8 3 5 + 5

9、 6 2 / - * -#*（/）-）（1）8 3 5#（+-4 / 7 掃描，遇操作數(shù)， 直接寫入exp2；若是操作符 （記為 w） ，分如下情況處理， 直至表達式exp1掃描完畢。（1）w 為一般操作符（+， - ，*，/ 等） ，要與棧頂操作符比較優(yōu)先級，若w 優(yōu)先級高于棧頂操作符，則入棧；否則，棧頂運算符退棧到exp2，w 再與新棧頂操作符作上述比較處理，直至w 入棧。（2）w 為左括號（ （ ） ，w 入棧。（3）w 為右括號（ ） ） ，操作符棧退棧并進入exp2，直到碰到左括號為止，左括號退棧（不能進入exp2） ，右括號也丟掉，達到exp2 中消除括號的目的。（4）w 為 #

10、，表示中綴表達式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 + 5 6 2 / - * - ?？捎妙愃品椒▽⒅芯Y表達式轉(zhuǎn)為前綴表達式。5設(shè)輸

11、入元素為1、2、3、p 和 a，輸入次序為123pa。元素經(jīng)過棧后達輸出序列，當(dā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); /ex1 7寫出如下程序段輸出結(jié)果。void ex3() char x=e,y=c; initqueue(q); enqueue(q,h); enqueue(q,r); e

12、nqueue(q,y); dequeue(q,x); enqueue(q,x); 5 / 7 dequeue(q,x); enqueue(q,a); while(!queueempty(q) dequeue(q,y); printf(y); /while printf(x); /ex3 8將如下遞歸過程改寫為非遞歸過程。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 (!m) return n+1; else

13、 if(!n) return ack(m-1,1); else return ack(m-1,ack(m,n-1); /ack 9三維數(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 中的下標(biāo)位置k 是什么？ a 中任一個下三角元素aij(ij),在數(shù)組

14、 b 中的下標(biāo)位置k 是什么？11設(shè)有三對角矩陣(ai,j)mn,將其三條對角線上的元素逐行的存于數(shù)組b(1:3n-2) 中，使得bk=ai,j，求：用i,j 表示 k 的下標(biāo)變換公式；若n=103，每個元素占用l 個單元，則用bk 方式比常規(guī)存儲節(jié)省多少單元。6 / 7 12設(shè)有矩陣且a=121133312，執(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è)有兩個

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

16、 ioiioioo b iooioiio c iiioioio diiiooioo 。通過對的分析，寫出一個算法， 判定所給的操作序列是否合法。若合法，返回 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 和隊尾指針

17、 rear，約定 front 指向隊頭元素的前一位置，rear 指向隊尾元素。 定義 front=rear 時為隊空，(rear+1)%m=front 為隊滿。 約定隊頭端入隊向下標(biāo)小的方向發(fā)展，隊尾端入隊向下標(biāo)大的方向發(fā)展。6已知 ackermann 函數(shù)定義如下，寫出ack(2,1) 的計算過程；寫出計算ack(m,n) 的非遞歸算法。7利用兩個棧s1 和 s2模擬一個隊列，寫出入隊和出隊的算法（可用棧的基本操作）。8假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾元素結(jié)點（注意不設(shè)頭指針），試編寫相應(yīng)的隊列初始化、入隊和出隊的算法。7 / 7 9設(shè)有大小不等的n 個數(shù)據(jù)組（ n 個數(shù)據(jù)組中數(shù)據(jù)的總數(shù)為m） ，順序存放在空間區(qū)d 內(nèi),每個數(shù)據(jù)占一個存儲單元，數(shù)據(jù)組的首地址由數(shù)組s 給出， （如下圖所示） ，試編寫將新數(shù)據(jù)x 插