1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)單選題：在一個具有n個單元的順序棧中，假定以地址低端作為棧底，以top作為棧頂指針， 則當(dāng)做退棧處理時，top變化為_。A. top不變 B. top-n C. toptop-1 D.top=top+1向順序棧中壓入元素時，是_。A.先移動棧頂指針，后存入元素 B.先存入元素，后移動棧頂指針 在一個順序存儲的循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的_。A.前一個位置 B.后一個位置 C.隊(duì)首元素位置若進(jìn)棧序列為1,2,3,4,進(jìn)棧過程中可以出棧，則_不可能是一個出棧序列。A.

2、3,4,2,1 B.2,4,3,1 C.1,4,3,2 D.3,2,1,4在具有n個單元的順序存儲的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則判斷隊(duì)空的條件是_。A.front= =rear+1 B.front+1= =rear C.front= =rear D.front= =0在具有n個單元的順序存儲的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則判斷隊(duì)滿的條件是_。A.rear % n= =front B.(rear-1) % n= =front C.(rear-1) % n= =rear D.(rear+1) % n= =front向一個棧項(xiàng)指針

3、為hs的鏈棧中插入一個*s結(jié)點(diǎn)時，則執(zhí)行_。A.hs-next=s; B.s-next=hs-next; hs-next=s; C.s-next=hs；hs=s; D.s-next=hs; hs=hs-next;在一個鏈隊(duì)列中，假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則進(jìn)行插入*s結(jié)點(diǎn)的操作時應(yīng)執(zhí)行_。A.front-next=s; front=s; B.rear-next=s; rear=s; C.front=front-next; D.front=rear-next;棧的特點(diǎn)是_隊(duì)的特點(diǎn)是_A.先進(jìn)先出 B.先進(jìn)后出 B|A棧和隊(duì)列的共同點(diǎn)是_。A.都是先進(jìn)后出 B.都是先進(jìn)先出

4、 C.只允許在端點(diǎn)處插入和刪除元素 D.沒有共同點(diǎn)一個棧的進(jìn)棧序列是a,b,c,d,e,則棧的不可能的輸出序列是_。A.edcba B.decba C.dceab D.abcde若己知一個棧的進(jìn)棧序列是1,2,3,n,其輸出序列為p1,p2,p3,pn,若p1=n,則pi(1i=n)為_。A.i B.n=I C.n-i+1 D.不確定若己知一個棧的進(jìn)棧序列是1,2,3,n,其輸出序列為p1,p2,p3,pn,若pn=n,則pi(i=itop!=-1 B.st-top=-1 C.st-top!=MaxSize-1 D.st-top=MaxSize-1判定一個順序棧st(最多元素為MaxSize)

5、為棧滿的條件是_。A.st-top!=-1 B.st-top=-1 C.st-top!=MaxSize-1 D.st-top=MaxSize-1最不適合用作鏈棧的鏈表是_。A.只有表頭指針沒有表尾指針的循環(huán)雙鏈表 B.只有表尾指針沒有表頭指針的循環(huán)雙鏈表 C.只有表尾指針沒有表頭指針的循環(huán)單鏈表 D.只有表頭指針沒有表尾指針的循環(huán)單鏈表向一個棧項(xiàng)指針為hs的鏈棧中插入一個s所指結(jié)點(diǎn)時，則執(zhí)行_。A.hs-next=s; B.s-next=hs-next;hs-next=s; C.s-next=hs;hs=s; D.s-next=hs;hs=hs-next;從一個棧項(xiàng)指針為hs的鏈棧中刪除一個結(jié)

6、點(diǎn)時，用x保存被刪結(jié)點(diǎn)的值，則執(zhí)行_。A.x=hs;hs=hs-next; B.x=hs-data; C.hs=hs-next;x=hs-data; D.x=hs-data;hs=hs-next; 一個隊(duì)列的入隊(duì)序列是1,2,3,4,則隊(duì)列的輸出序列是_。A.4,3,2,1 B.1,2,3,4, C.1,4,3,2 D.3,2,4,1判定一個環(huán)形隊(duì)列qu(最多元素為MaxSize)為空的條件是_。A.qu-rear-qu-front=MaxSize B.qu-rear-qu-front-1=MaxSize C.qu-front=qu-rear D.qu-front=qu-rear+1 判定一個

7、環(huán)形隊(duì)列qi(最多元素為MaxSize)為滿隊(duì)列的條件是_。A.(qu-rear+1)%MaxSize=qu-front B.qu-rear-qu-front-1=MaxSize C.qu-front=qu-rear D.qu-front=qu-rear+1 環(huán)形順序隊(duì)列中是否可以插入下一個元素,_。A.與隊(duì)頭指針的隊(duì)尾指針的值有關(guān) B.只與隊(duì)尾指針的值有關(guān),與隊(duì)頭指針的值無關(guān) C.只與數(shù)組大小有關(guān),與隊(duì)首指針和隊(duì)尾指針的值無關(guān) D.與曾經(jīng)進(jìn)行過多少次插入操作有關(guān)環(huán)形隊(duì)列用數(shù)組A0.MaxSize-1存放其元素值,己知其頭尾指針分別是front和rear,則當(dāng)前隊(duì)列的元素個數(shù)是_。A.(rea

8、r-front+MaxSize)%MaxSize B.rear-front+1 C.(rear-front-1)%MaxSize D.(rear-front)%MaxSize若用一個大小為6的一維數(shù)組來實(shí)現(xiàn)環(huán)形隊(duì)列，且當(dāng)前rear和front的值分別為0和3。當(dāng)從隊(duì)列中刪除一個元素，再加入兩個元素后，rear和front的值分別是_。A.1和5 B.2和4 C.4和2 D.5和1最不適合用作鏈隊(duì)的鏈表是_。A.只帶隊(duì)頭指針的非循環(huán)雙鏈表 B.只帶隊(duì)頭指針的循環(huán)雙鏈表 C.只帶隊(duì)尾指針的循環(huán)雙鏈表D.只帶隊(duì)尾指針的循環(huán)單鏈表在一個鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的運(yùn)算是_

9、。A.f-next=s;f=s; B.r-next=s;r=s; C.s-next=r;r=s; D.s-next=f;f=s; 在一個鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個結(jié)點(diǎn)的運(yùn)算是_。A.r=f-next; B.r=r-next; C.f=f-next; D.f=r-next;用單鏈表表示的鏈隊(duì)的隊(duì)頭在鏈用不著的_位置。A.鏈頭 B.鏈尾 C.鏈中 D.任意 中綴表達(dá)式A*(B+C)/(D-E+F)的后綴表達(dá)式是_。A.A*B+C/D-E+F B.AB*C+D/E-F+ C.ABC+*DE-+/ D.ABCDEF*+/-+ 己知一個棧的進(jìn)棧序列是ABC,出棧序列為CBA,經(jīng)過

10、的棧操作是_。A.push,pop,push,pop,push,pop B.push,push,push,pop,pop,pop C.push,push,pop,pop,push,pop D.push,pop,push,push,pop,pop判定一個順序棧st為(元素個數(shù)最多為MaxSize)空的條件為_。A.st.top=-1 B.st.top!=-1 C.st.top!=MaxSize D.st.top=MaxSize判定一個順序棧st(元素個數(shù)最多為MaxSize)為棧滿的條件是_。A.st.top!=-1 B.st.top=-1 C.st.top!=MaxSize-1 D.st.to

11、p=MaxSize-1表達(dá)式a*(b+c)-d的后綴表達(dá)式是_。A.abcd*+- B.abc+*d- C.abc*+d- D.-+*abcd表達(dá)式(2+2*3)*2+6*3/2的后綴表達(dá)式是_。A.2 2 3 * + 2 * 6 3 * 2 / + B.2 2 * 3 + 2 * 6 3 * 2 / + C.2 2 3 * 2 * 6 3 * + 2 / + D.2 2 3 * + 2 6 3 * 2 / + *鏈棧與順序棧相比有一個明顯的優(yōu)點(diǎn),即_。A.插入操作更方便 B.通常不會出現(xiàn)棧滿的情況 C.不會出現(xiàn)棧空的情況 D.刪除操作更加方便最不適合用作鏈棧的鏈表是_。A.只有表頭指針沒有表

12、尾指針的循環(huán)雙鏈表 B.只有表尾指針沒有表頭指針的循環(huán)雙鏈表C.只有表尾指針沒有表頭指針的循環(huán)單鏈表 D.只有表頭指針沒有表尾指針的循環(huán)單鏈表如果以鏈表作為棧的存儲結(jié)構(gòu),則退鏈棧操作時_。A.必須判別棧是否滿 B.判別鏈棧元素的類型 C.必須差別鏈棧是否空 D.對鏈棧不作任何差別向一個不帶頭結(jié)點(diǎn)的棧指針為1st的鏈棧中插入一個s所指結(jié)點(diǎn)時,則執(zhí)行_。A.1st-next=s; B.s-next=1st-next;1st-next=s; C.s-next=1st;1st=s; D.s-next=1st;1st=1st-next;從一個不帶頭結(jié)點(diǎn)的棧頂指針為1st的鏈棧中刪除一個結(jié)點(diǎn)時,用x保存被

13、刪結(jié)點(diǎn)的值,則執(zhí)行_。A.x=1st;1st=1st-next; B.x=1st-data; C.1st=1st-next;x=1st-data; D.x=1st-data;1st=1st-next;一個棧的進(jìn)棧序列是a,b,c,d,e,則棧的不可能的輸出序列是_.A.edcba B.decba C.dceab D.abcde 在一個長度為n的順序存儲的集合中查找值為x的元素時，在等概率情況下，查找成功時的平均查找長度為_。A.n B.n/2 C.(n+1)/2 D.(n-1)/2在一個長度為n的鏈接存儲的集合中查找值為x的元素時，算法的時間復(fù)雜度為_。A.O(1) B.O(n) C.O(n*

14、n) D.O(lbn)已知一個元素x不屬于一個長度為n的順序或鏈接存儲的集合中的元素，把它插入集合時不進(jìn)行比較過程，則插入過程的時間復(fù)雜度為_。A.O(1) B.O(lbn) C.O(n) D.O(n*n)設(shè)一個具有t個非零元素的m*n大小的稀疏矩陣采用順序存儲，求其轉(zhuǎn)置矩陣的普通轉(zhuǎn)置算法的時間復(fù)雜度為_。A.O(m) B.O(n) C.O(n+t) D.O(n*t)判斷題：棧底元素是不能刪除的元素。 F順序棧中元素值的大小是有序的。 F在n個元素進(jìn)棧后,它們的出棧順序和進(jìn)棧順序一定正好相反。 T棧頂元素和棧底元素有可能是同一個元素。 T若用S1-Sm表示順序棧的存儲空間,則對棧的進(jìn)棧、出棧操

15、作最多只能進(jìn)行m次。 F棧沒有棧頂指針。 F填空題：在具有n個單元、順序存儲的循環(huán)隊(duì)列中，隊(duì)滿時共有_個元素。n-1棧和隊(duì)列的區(qū)別僅在于_。刪除運(yùn)算的不同通常元素進(jìn)棧的操作是_。先移動棧頂指針，后存入元素通常元素退棧的操作是_。先取出元素，后移動棧頂指針一個棧的輸入序列是12345,則棧的輸出序列是_。 不可能的一個棧的輸入序列是12345,則棧的輸出序列12345是_。 可能的設(shè)有一個順序棧S,元素s1,s2,s3,s4,s5,s6依次進(jìn)棧,如果6個元素的出棧順序?yàn)閟2,s3,s4,s6,s5,s1,則順序棧的容量至少應(yīng)為_。 3設(shè)棧采用順序存儲結(jié)構(gòu),若己知i-1個元素進(jìn)棧,則將第i個元素進(jìn)

16、棧時,進(jìn)棧算法的時間復(fù)雜度為_。 O（1）若用不帶頭結(jié)點(diǎn)的單鏈表來表示鏈棧S,則創(chuàng)建一個空棧所要執(zhí)行的操作是_。 S=NULL從環(huán)形隊(duì)列中插入一個元素時,通常的操作是_。 先存放元素,后移動隊(duì)尾指針從環(huán)形隊(duì)列中插入一個元素時,通常的操作是_。從環(huán)形隊(duì)列中插入一個元素時,通常的操作是_。 MaxSize-1在鏈表qu中,判定只有一個結(jié)點(diǎn)的條件是_。 qu-front=qu-rear&qu-front!=NULL設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空,元素a1,a2,a3,a4,a5,a6,a7和a8依次通過棧S,一個元素出棧后立即進(jìn)入隊(duì)列Q,若8個元素出隊(duì)列的順序是a3,a6,a7,a5,a8,a4,a2

17、,a1,則棧S的容量至少應(yīng)該是多少(即至少應(yīng)該容納多少個元素)? 5設(shè)有算術(shù)表達(dá)式x+a*(y-b)-c/d,該表達(dá)式的前綴表達(dá)為_。后綴表示為_。 -+x*a-yb/cd|xayb-*+cd/-棧是一種具有_特性的線性表。 后進(jìn)先出順序棧和鏈棧的區(qū)別僅在于_的不同。 存儲結(jié)構(gòu)如果棧的最大長度難以估計(jì),則最好使用_。 鏈棧一個棧的輸入序列是12345,則棧的輸出序列12345是_。 可能的設(shè)棧采用順序存儲結(jié)構(gòu),若己知i-1個元素進(jìn)棧,則將第i個元素進(jìn)棧時,進(jìn)棧算法的時間復(fù)雜度為_。 O(1)表達(dá)式23+(12*3-2)/4+34*5/7)+108/9的后綴表達(dá)式是_。 23 12 3 * 2

18、- 4 / 34 5 * 7 / + + 108 9 / +若用不帶頭結(jié)點(diǎn)的單鏈表來表示鏈棧1st,則創(chuàng)建一個空棧所要執(zhí)行的操作是_。 1st=NULL對于鏈棧1st,進(jìn)棧操作在_端進(jìn)行,出棧操作在_端進(jìn)行。 鏈棧頭|鏈棧頭將遞歸算法轉(zhuǎn)換為非遞歸算法時,通常使用_這種數(shù)據(jù)結(jié)構(gòu)。棧24.有如下遞歸算法:void print (int w) int i; if (w!=0) print(w-1); for(i=1;i=w;i+) printf(%3d,w); printf(n); 調(diào)用語句printf(4)的結(jié)果是_。 25. 有如下遞歸過程:void reverse(int m) printf(

19、%d,n%10); if (n/10 !=0) reverse(n/10);調(diào)用語句reverse(582)的結(jié)果是_。 28526. 求順序存儲的集合的長度的時間復(fù)雜度為_。 O(1)27. 求鏈接存儲的集合的長度的時間復(fù)雜度為_。 O(n)28. 設(shè)集合S的長度為n，則判斷x是否屬于集合的時間復(fù)雜度為_ O(n)29. 在稀疏矩陣的順序存儲中，利用一個數(shù)組來存儲非零元素，該數(shù)組的長度應(yīng)_對應(yīng)三元組線性表的長度。 大于等于算法分析題：設(shè)計(jì)一個算法,利用棧的基本運(yùn)算將指定棧中的內(nèi)容進(jìn)行逆轉(zhuǎn)。答：、status Nizhuan(sqstacks, int a, int b, int t)If(s

20、.top=s.base)error(no data);for(i=0;ilefttop= -1; s-righttop=MAXNUM; return TRUE;（2）入棧操作【共享?xiàng)５娜霔２僮鳌縤nt pushDupStack(dupsqstack *s,char status,Elemtype x)*把數(shù)據(jù)元素x壓入左棧（status=L）或右棧（status=R）*/ if(s-lefttop+1= =s-righttop) return FALSE; /*棧滿*/ if(status=L) s-stack+s-lefttop=x; /*左棧進(jìn)棧*/ else if(status=R) s

21、-stack-s-lefttop=x; /*右棧進(jìn)棧*/ else return FALSE; /*參數(shù)錯誤*/return TRUE;（3）出棧操作【共享?xiàng)５某鰲２僮鳌縀lemtype popDupStack(dupsqstack *s,char status)/*從左棧（status=L）或右棧（status=R）退出棧頂用不帶頭結(jié)點(diǎn)的單鏈表存儲鏈棧,設(shè)計(jì)初始棧、判斷棧是否為空、進(jìn)棧和出棧等相應(yīng)的算法。答：（1）入棧操作【單個鏈棧的入棧操作】int pushLstack(slStacktype *top,Elemtype x)/將元素x壓入鏈棧top中slStacktype *p;if(p

22、=(slStacktype*)malloc(sizeof(slStacktype)=NULL) return FALSE; /申請一個結(jié)點(diǎn)p-data=x; p-next=top; top=p; return TRUE;（2）出棧操作【單個鏈棧的出棧操作】Elemtype popLstack(slStacktype *top)/從鏈棧top中刪除棧頂元素slStacktype *p;Elemtype x;if (top= =NULL) return NULL; /空棧p=top; top=top-next; x=p-data;free(p);return x;問答題：試述棧的基本性質(zhì)?解答：由

23、棧的定義可知，這種結(jié)構(gòu)的基本性質(zhì)綜述如下： (1)集合性。棧是由若干個元素集合而成，當(dāng)沒有元素的空集合稱為空棧； (2)線性結(jié)構(gòu)。除棧底元素和棧頂元素外，棧中任一元素均有唯一的前驅(qū)元素和后繼元素； (3)受限制的運(yùn)算。只允許在棧頂實(shí)施壓入或彈出操作，且棧頂位置由棧指針?biāo)甘荆?4)數(shù)學(xué)性質(zhì)。當(dāng)多個編號元素依某種順序壓入，且可任意時刻彈出時，所獲得的編號元素排列的數(shù)目，恰好滿足卡塔南數(shù)列的計(jì)算，即： n n 2n /(n1) 其中，n為編號元素的個數(shù)，Cn 是可能的排列數(shù)目。何謂隊(duì)列的上溢現(xiàn)象?解決它有哪些方法，且分別簡述其工作原理。解答：在隊(duì)列的順序存儲結(jié)構(gòu)中，設(shè)隊(duì)頭指針為front,隊(duì)尾指針

24、為rear,隊(duì)的容量（存儲空間的大?。閙。當(dāng)有元素要加入隊(duì)列時，若rearm（初始時reat0），則發(fā)生隊(duì)列的上溢現(xiàn)象，該元素不能加入隊(duì)列。 這里要特別注意的是：隊(duì)列的假溢出現(xiàn)象，隊(duì)列中還有空余的空間，但元素不能進(jìn)隊(duì) 列。造成這種現(xiàn)象的原因是由于隊(duì)列的操作方式所致。 解決隊(duì)列的上溢有以下幾種方法： (1)建立一個足夠大的存儲空間，但這樣做往往會造成空間使用的效率低。 (2)當(dāng)出現(xiàn)假溢出時，可采用以下幾種方法： 采用平移元素的方法。每當(dāng)隊(duì)列中加入一個元素時，隊(duì)列中已有的元素向隊(duì)頭 移動一個位置（當(dāng)然要有空余的空間可移）； 每當(dāng)刪去一個隊(duì)頭元素時，則依次序移隊(duì)中的元素，始終使front指針指向隊(duì)

25、列 中的第一個位置； 采用循環(huán)隊(duì)列方式。把隊(duì)頭隊(duì)尾看成是一個首尾相鄰的循環(huán)隊(duì)列，雖然物理上假定用一個循環(huán)單鏈表表示隊(duì)列（稱此為循環(huán)鏈隊(duì)），該隊(duì)列只設(shè)一個隊(duì)尾指針， 不設(shè)隊(duì)首指針，試編寫下列算法： (1)向循環(huán)鏈隊(duì)插入一個元素為x的結(jié)點(diǎn)。 (2)從循環(huán)鏈隊(duì)中刪除一個結(jié)點(diǎn)（假定不需要保留被刪除結(jié)點(diǎn)的值和不需要回收結(jié)點(diǎn)）。3. 假定用一個循環(huán)單鏈表表示隊(duì)列（稱此為循環(huán)鏈隊(duì)），該隊(duì)列只設(shè)一個隊(duì)尾指針， 不設(shè)隊(duì)首指針，試編寫下列算法： (1)向循環(huán)鏈隊(duì)插入一個元素為x的結(jié)點(diǎn)。 (2)從循環(huán)鏈隊(duì)中刪除一個結(jié)點(diǎn)（假定不需要保留被刪除結(jié)點(diǎn)的值和不需要回收結(jié)點(diǎn)）解答： (1) 解答:status insert(

26、Rear,x) / 假定Rear為循環(huán)鏈隊(duì)的隊(duì)尾指針，x為待插入的元素 (1) malloc(p); p-datax; / 建立值為x的新結(jié)點(diǎn)p (2) if( Rearnil) Rearp; Rear-nextp; else p-nextRear-next; Rear-nextp; Rearp; / 若條件成立則建立循環(huán)鏈隊(duì)的第一個結(jié)點(diǎn)，否則在隊(duì)尾插入p結(jié)點(diǎn) (2) 解答:status delete(Rear) if( Rearnil ) error(underflow); if (Rear-next= =Rear) Rearnil; else Rear-nextRear-next-next

27、; /Rear.next 所指向的結(jié)點(diǎn)為循環(huán)鏈隊(duì)的隊(duì)首結(jié)點(diǎn) 4.為什么說棧是一種后進(jìn)先出表?解答：棧是允許在同一端進(jìn)行插入和刪除操作的特殊線性表。允許進(jìn)行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動；棧中元素個數(shù)為零時稱為空棧。插入一般稱為進(jìn)棧（PUSH），刪除則稱為退棧（POP）。 棧也稱為后進(jìn)先出表（LIFO-Last IN First Out表）。5對于一個棧,給出輸入項(xiàng)A,B,C。如果輸入項(xiàng)序列由A,B,C所組成,試給出全部可能的輸出序列。解答：A，6.有字符串次序?yàn)?*y-a/y2,試?yán)脳＝o出將次序改變?yōu)?y-*ay2/-的操作步驟。(

28、可用X代表掃描該字符串函數(shù)中順序取一字符進(jìn)棧的操作,用S代表從棧中取出一個字符加到新字符串尾的出棧的操作)。例如:ABC變?yōu)锽CA,則操作步驟為XXSXX。解答：X:進(jìn)棧 S:出棧XSXXXSSSXXSXXSXXSSSS7.跟蹤以下代碼,顯示每次調(diào)用后隊(duì)列中的內(nèi)容。InitQueue(qu);EnQueue(qu,A);EnQueue(qu,B);EnQueue(qu,C);EnQueue(qu,x;EnQueue(qu,x;EnQueue(qu,D);EnQueue(qu,E);EnQueue(qu,F);EnQueue(qu,x)EnQueue(qu,G);EnQueue(qu,X)EnQueue(qu,X)EnQueue(qu,X)解答：InitQueue(qu); 隊(duì)列為空EnQueue(qu,A); 隊(duì)列為AEnQueue(qu,B); 隊(duì)列為ABEnQueue(qu,C); 隊(duì)列為ABCEnQueue(qu,x; 隊(duì)列為ABCxEnQueue(qu,x