數(shù)據(jù)結(jié)構(gòu)習(xí)題集.doc

《數(shù)據(jù)結(jié)構(gòu)習(xí)題集.doc》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)習(xí)題集.doc（42頁珍藏版）》請在裝配圖網(wǎng)上搜索。

第一章 緒論一、選擇題1. 算法的計算量的大小稱為計算的（ ）。A效率 B. 復(fù)雜性 C. 現(xiàn)實性 D. 難度2. 算法的時間復(fù)雜度取決于（ ）A問題的規(guī)模 B. 待處理數(shù)據(jù)的初態(tài) C. A和B3.計算機算法指的是（1），它必須具備（2） 這三個特性。(1) A計算方法 B. 排序方法 C. 解決問題的步驟序列 D. 調(diào)度方法(2) A可執(zhí)行性、可移植性、可擴充性 B. 可執(zhí)行性、確定性、有窮性C. 確定性、有窮性、穩(wěn)定性 D. 易讀性、穩(wěn)定性、安全性 4一個算法應(yīng)該是（ ）。 A程序 B問題求解步驟的描述 C要滿足五個基本特性 DA和C. 5. 下面關(guān)于算法說法錯誤的是（ ）A算法最終必須由計算機程序?qū)崿F(xiàn)B.為解決某問題的算法同為該問題編寫的程序含義是相同的C. 算法的可行性是指指令不能有二義性 D. 以上幾個都是錯誤的6. 下面說法錯誤的是（ ） (1)算法原地工作的含義是指不需要任何額外的輔助空間 （2）在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時間上總是優(yōu)于復(fù)雜度O(2n)的算法 （3）所謂時間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界 （4）同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低 A(1) B.(1),(2) C.(1),(4) D.(3)7從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）兩大類。A動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu) C線性結(jié)構(gòu)、非線性結(jié)構(gòu) D初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)8以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（ ）。A循環(huán)隊列 B. 鏈表 C. 哈希表 D. 棧9以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)（ ）？ A廣義表 B. 二叉樹 C. 稀疏矩陣 D. 串10以下那一個術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)？（ ）A棧 B. 哈希表 C. 線索樹 D. 雙向鏈表 11線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（）。 A必須是連續(xù)的 B部分地址必須是連續(xù)的 C一定是不連續(xù)的 D連續(xù)或不連續(xù)都可以12在以下的敘述中，正確的是（）。 A線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu) B二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表 C棧的操作方式是先進先出 D隊列的操作方式是先進后出 13以下哪個數(shù)據(jù)結(jié)構(gòu)不是多型數(shù)據(jù)類型（ ）A棧 B廣義表 C有向圖 D字符串14以下數(shù)據(jù)結(jié)構(gòu)中，（ ）是非線性數(shù)據(jù)結(jié)構(gòu)A樹 B字符串 C隊 D棧15. 下列數(shù)據(jù)中，（ ）是非線性數(shù)據(jù)結(jié)構(gòu)。A棧 B. 隊列 C. 完全二叉樹 D. 堆16連續(xù)存儲設(shè)計時，存儲單元的地址（ ）。A一定連續(xù) B一定不連續(xù) C不一定連續(xù) D部分連續(xù)，部分不連續(xù)17以下屬于邏輯結(jié)構(gòu)的是（ ）。A順序表 B. 哈希表 C.有序表 D. 單鏈表18.一個數(shù)據(jù)對象是（ ）的集合。 A.相同類型的數(shù)據(jù)項 B.相同類型的數(shù)據(jù)元素C.不同類型的數(shù)據(jù)項 D.不同類型的數(shù)據(jù)元素19. ( )是數(shù)據(jù)的基本單位。A.數(shù)據(jù)項 B.關(guān)鍵字 C.數(shù)據(jù)元素 D.數(shù)據(jù)類型 20.數(shù)據(jù)結(jié)構(gòu)在計算機中的表示稱為數(shù)據(jù)( )。 A.對象 B.的存儲結(jié)構(gòu) C.類型 D.元素21.下列程序段的時間復(fù)雜度為( )。 for(i=0；i5；i+) for(j=0；j1) sum=1； for (i=0;sumn;i+) sum+=1; 10計算機執(zhí)行下面的語句時，語句s的執(zhí)行次數(shù)為 _ 。 FOR(i=l；i=i;j-) s; 11.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是： i：=1； WHILE i0）。 A表元素 B字符 C數(shù)據(jù)元素 D數(shù)據(jù)項 E信息項4若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（ ）存儲方式最節(jié)省時間。A順序表 B雙鏈表 C帶頭結(jié)點的雙循環(huán)鏈表 D單循環(huán)鏈表5某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（ ）存儲方式最節(jié)省運算時間。A單鏈表 B僅有頭指針的單循環(huán)鏈表 C雙鏈表 D僅有尾指針的單循環(huán)鏈表6設(shè)一個鏈表最常用的操作是在末尾插入結(jié)點和刪除尾結(jié)點，則選用( )最節(jié)省時間。A. 單鏈表 B.單循環(huán)鏈表 C. 帶尾指針的單循環(huán)鏈表 D.帶頭結(jié)點的雙循環(huán)鏈表7若某表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點或刪除最后一個結(jié)點。則采用（ ）存儲方式最節(jié)省運算時間。A單鏈表 B雙鏈表 C單循環(huán)鏈表 D帶頭結(jié)點的雙循環(huán)鏈表8. 靜態(tài)鏈表中指針表示的是（ ）. A 內(nèi)存地址 B數(shù)組下標(biāo) C下一元素地址 D左、右孩子地址9. 鏈表不具有的特點是（ ） A插入、刪除不需要移動元素 B可隨機訪問任一元素 C不必事先估計存儲空間 D所需空間與線性長度成正比10. 下面的敘述不正確的是（ ）A線性表在鏈?zhǔn)酱鎯r，查找第i個元素的時間同i的值成正比 B. 線性表在鏈?zhǔn)酱鎯r，查找第i個元素的時間同i的值無關(guān)C. 線性表在順序存儲時，查找第i個元素的時間同i 的值成正比D. 線性表在順序存儲時，查找第i個元素的時間同i的值無關(guān)11 雙向鏈表中有兩個指針域，llink和rlink分別指向前趨及后繼，設(shè)p指向鏈表中的一個結(jié)點，現(xiàn)要求刪去p所指結(jié)點，則正確的刪除是（ ）（鏈中結(jié)點數(shù)大于2，p不是第一個結(jié)點）Ap.llink.rlink:=p.llink; p.llink.rlink:=p.rlink; dispose(p);Bdispose(p); p.llink.rlink:=p.llink; p.llink,rlink:=p.rlink;Cp.llink.rlink:=p.llink; dispose(p); p.llink.rlink:=p.rlink;D以上A，B，C都不對。12.(1) 靜態(tài)鏈表既有順序存儲的優(yōu)點，又有動態(tài)鏈表的優(yōu)點。所以，它存取表中第i個元素的時間與i無關(guān)。 (2) 靜態(tài)鏈表中能容納的元素個數(shù)的最大數(shù)在表定義時就確定了，以后不能增加。 (3) 靜態(tài)鏈表與動態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動。以上錯誤的是（ ） A（1），（2） B（1） C（1），（2）,(3) D.（2）13. 若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復(fù)雜度為（ ）(1=iLlink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q；B. p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;C. q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q;D. q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q;24在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點，正確的操作是：（ ）。Ap-next=s;s-next=p-next; B s-next=p-next;p-next=s;Cp-next=s;p-next=s-next; D p-next=s-next;p-next=s;25對于一個頭指針為head的帶頭結(jié)點的單鏈表，判定該表為空表的條件是（ ）Ahead=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL26. 在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點時須修改指針（ ）。A (p.llink).rlink:=p.rlink (p.rlink).llink:=p.llink;B p.llink:=(p.llink).llink (p.llink).rlink:=p;C (p.rlink).llink:=p p.rlink:=(p.rlink).rlinkD p.rlink:=(p.llink).llink p.llink:=(p.rlink).rlink; 二、填空題1當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應(yīng)采用_存儲結(jié)構(gòu)。2線性表L=（a1,a2,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是_。3設(shè)單鏈表的結(jié)點結(jié)構(gòu)為(data,next)，next為指針域，已知指針px指向單鏈表中data為x的結(jié)點，指針py指向data為y的新結(jié)點 , 若將結(jié)點y插入結(jié)點x之后，則需要執(zhí)行以下語句:_； _;4在一個長度為n的順序表中第i個元素（1=i=n）之前插入一個元素時，需向后移動_個元素。5在單鏈表中設(shè)置頭結(jié)點的作用是_。6對于一個具有n個結(jié)點的單鏈表，在已知的結(jié)點*p后插入一個新結(jié)點的時間復(fù)雜度為_,在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為_。7根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每一個結(jié)點包含的指針個數(shù)，將線性鏈表分成_和_；而又根據(jù)指針的連接方式，鏈表又可分成_和_。8在雙向循環(huán)鏈表中,向p所指的結(jié)點之后插入指針f所指的結(jié)點，其操作是_、_、_、_。9在雙向鏈表結(jié)構(gòu)中，若要求在p 指針?biāo)傅慕Y(jié)點之前插入指針為s 所指的結(jié)點，則需執(zhí)行下列語句：s .next:=p； s .prior:= _；p .prior:=s；_:=s；10.鏈接存儲的特點是利用_來表示數(shù)據(jù)元素之間的邏輯關(guān)系。11.順序存儲結(jié)構(gòu)是通過_表示元素之間的關(guān)系的;鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過_表示元素之間的關(guān)系的。12. 對于雙向鏈表,在兩個結(jié)點之間插入一個新結(jié)點需修改的指針共 _個，單鏈 表為_個。13. 循環(huán)單鏈表的最大優(yōu)點是：_。14. 已知指針p指向單鏈表L中的某結(jié)點，則刪除其后繼結(jié)點的語句是：_15. 帶頭結(jié)點的雙循環(huán)鏈表L中只有一個元素結(jié)點的條件是：_16. 在單鏈表L中，指針p所指結(jié)點有后繼結(jié)點的條件是：_ 17.帶頭結(jié)點的雙循環(huán)鏈表L為空表的條件是：_。18. 在單鏈表p結(jié)點之后插入s結(jié)點的操作是：_。 三、解答題1線性表有兩種存儲結(jié)構(gòu)：一是順序表，二是鏈表。試問：（1）如果有 n個線性表同時并存，并且在處理過程中各表的長度會動態(tài)變化，線性表的總數(shù)也會自動地改變。在此情況下，應(yīng)選用哪種存儲結(jié)構(gòu)？ 為什么？（2）若線性表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應(yīng)采用哪種存儲結(jié)構(gòu)？為什么？ 2線性表的順序存儲結(jié)構(gòu)具有三個弱點：其一，在作插入或刪除操作時，需移動大量元素；其二，由于難以估計，必須預(yù)先分配較大的空間，往往使存儲空間不能得到充分利用；其三，表的容量難以擴充。線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是否一定都能夠克服上述三個弱點，試討論之。3若較頻繁地對一個線性表進行插入和刪除操作，該線性表宜采用何種存儲結(jié)構(gòu)？為什么？4線性結(jié)構(gòu)包括_、_、_和_。線性表的存儲結(jié)構(gòu)分成_和_。請用類PASCL語言描述這兩種結(jié)構(gòu)。5線性表（a1，a2，an）用順序映射表示時，ai和ai+1（1=in）的物理位置相鄰嗎？鏈接表示時呢？ 6. 說明在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，頭指針與頭結(jié)點之間的根本區(qū)別；頭結(jié)點與首元結(jié)點的關(guān)系。7. 試述頭結(jié)點,首元結(jié)點,頭指針這三個概念的區(qū)別. 8有線性表(a1,a2,an),采用單鏈表存儲，頭指針為H，每個結(jié)點中存放線性表中一個元素，現(xiàn)查找某個元素值等于X的結(jié)點。分別寫出下面三種情況的查找語句。要求時間盡量少。（1）線性表中元素?zé)o序。（2）線性表中元素按遞增有序。 （3）線性表中元素按遞減有序。9. 在單鏈表和雙向鏈表中，能否從當(dāng)前結(jié)點出發(fā)訪問到任何一個結(jié)點?10. 如何通過改鏈的方法，把一個單向鏈表變成一個與原來鏈接方向相反的單向鏈表？11. 設(shè)單鏈表結(jié)點指針域為next，試寫出刪除鏈表中指針p所指結(jié)點的直接后繼的C語言語句。12. 設(shè)單鏈表中某指針p所指結(jié)點（即p結(jié)點）的數(shù)據(jù)域為data，鏈指針域為next，請寫出在p結(jié)點之前插入s結(jié)點的操作（PASCAL語句）。 四、算法設(shè)計題1 假設(shè)有兩個按元素值遞增次序排列的線性表，均以單鏈表形式存儲。請編寫算法將這兩個單鏈表歸并為一個按元素值遞減次序排列的單鏈表，并要求利用原來兩個單鏈表的結(jié)點存放歸并后的單鏈表。2. 知L1、L2分別為兩循環(huán)單鏈表的頭結(jié)點指針，m,n分別為L1、L2表中數(shù)據(jù)結(jié)點個數(shù)。要求設(shè)計一算法，用最快速度將兩表合并成一個帶頭結(jié)點的循環(huán)單鏈表。3在帶頭結(jié)點的單鏈表上，給出求表長Length(L)的算法，并加入簡要的注釋或說明。4設(shè)單鏈表具有頭結(jié)點，且表中元素各不相同，試給出在單鏈表中查找值為x的結(jié)點的算法，并加入簡要的注釋或說明。5設(shè)單鏈表具有頭結(jié)點，且表中元素各不相同，試給出在單鏈表中刪除值為x的結(jié)點的算法。第三章 棧和隊列一、 選擇題1. 對于棧操作數(shù)據(jù)的原則是（ ）。A. 先進先出 B. 后進先出 C. 后進后出 D. 不分順序2. 在作進棧運算時,應(yīng)先判別棧是否( ),在作退棧運算時應(yīng)先判別棧是否( )。當(dāng)棧中元素為n個,作進棧運算時發(fā)生上溢,則說明該棧的最大容量為( )。為了增加內(nèi)存空間的利用率和減少溢出的可能性,由兩個棧共享一片連續(xù)的內(nèi)存空間時,應(yīng)將兩棧的 ( )分別設(shè)在這片內(nèi)存空間的兩端,這樣,當(dāng)( )時，才產(chǎn)生上溢。 , : A. 空 B. 滿 C. 上溢 D. 下溢 : A. n-1 B. n C. n+1 D. n/2 : A. 長度 B. 深度 C. 棧頂 D. 棧底 : A. 兩個棧的棧頂同時到達?？臻g的中心點.B. 其中一個棧的棧頂?shù)竭_棧空間的中心點. C. 兩個棧的棧頂在?？臻g的某一位置相遇. D. 兩個棧均不空,且一個棧的棧頂?shù)竭_另一個棧的棧底.3. 一個棧的輸入序列為123n，若輸出序列的第一個元素是n，輸出第i（1=i0) ? x* f(x-1):2); int i ; i =f(f(1);A2 B. 4 C. 8 D. 無限遞歸19. 表達式a*(b+c)-d的后綴表達式是( )。Aabcd*+- B. abc+*d- C. abc*+d- D. -+*abcd20. 表達式3* 2(4+2*2-6*3)-5求值過程中當(dāng)掃描到6時，對象棧和算符棧為（ ），其中為乘冪 。A. 3,2,4,1,1；(*(+*- B. 3,2,8；(*- C. 3,2,4,2,2；(*(- D. 3,2,8；(*(-21. 設(shè)計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用（ ）數(shù)據(jù)結(jié)構(gòu)最佳。A線性表的順序存儲結(jié)構(gòu) B. 隊列 C. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) D. 棧22. 用鏈接方式存儲的隊列，在進行刪除運算時（ ）。A. 僅修改頭指針 B. 僅修改尾指針 C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改23. 用不帶頭結(jié)點的單鏈表存儲隊列時,其隊頭指針指向隊頭結(jié)點,其隊尾指針指向隊尾結(jié)點，則在進行刪除操作時( )。A僅修改隊頭指針 B. 僅修改隊尾指針 C. 隊頭、隊尾指針都要修改 D. 隊頭,隊尾指針都可能要修改24. 遞歸過程或函數(shù)調(diào)用時，處理參數(shù)及返回地址，要用一種稱為（ ）的數(shù)據(jù)結(jié)構(gòu)。A隊列 B多維數(shù)組 C棧 D. 線性表25. 假設(shè)以數(shù)組Am存放循環(huán)隊列的元素,其頭尾指針分別為front和rear，則當(dāng)前隊列中的元素個數(shù)為（ ）。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m26. 循環(huán)隊列A0.m-1存放其元素值，用front和rear分別表示隊頭和隊尾，則當(dāng)前隊列中的元素數(shù)是( )。A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front27. 循環(huán)隊列存儲在數(shù)組A0.m中，則入隊時的操作為（ ）。A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 28. 若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 29. 已知輸入序列為abcd 經(jīng)過輸出受限的雙向隊列后能得到的輸出序列有（ ）。 A. dacb B. cadb C. dbca D. bdac E. 以上答案都不對 30. 若以1234作為雙端隊列的輸入序列，則既不能由輸入受限的雙端隊列得到，也不能由輸出受限的雙端隊列得到的輸出序列是( )。A. 1234 B. 4132 C. 4231 D. 4213 31. 最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是 （ ）。 A. (rear+1) MOD n=front B. rear=front Crear+1=front D. (rear-l) MOD n=front32. 棧和隊列的共同點是（ ）。A. 都是先進先出 B. 都是先進后出 C. 只允許在端點處插入和刪除元素 D. 沒有共同點33. 棧的特點是（ ）,隊列的特點是（ ）,棧和隊列都是（ ）。若進棧序列為1,2,3,4 則（ ）不可能是一個出棧序列（不一定全部進棧后再出棧）；若進隊列的序列為1,2,3,4 則（ ）是一個出隊列序列。, : A. 先進先出 B. 后進先出 C. 進優(yōu)于出 D. 出優(yōu)于進: A.順序存儲的線性結(jié)構(gòu) B.鏈?zhǔn)酱鎯Φ木€性結(jié)構(gòu) C.限制存取點的線性結(jié)構(gòu) D.限制存取點的非線性結(jié)構(gòu), : A. 3,2,1,4 B. 3,2,4,1 C. 4,2,3,1 D. 4,3,2,1 F. 1,2,3,4 G. 1,3,2,434. 棧和隊都是（ ）A順序存儲的線性結(jié)構(gòu) B. 鏈?zhǔn)酱鎯Φ姆蔷€性結(jié)構(gòu)C. 限制存取點的線性結(jié)構(gòu) D. 限制存取點的非線性結(jié)構(gòu)35. 設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1，e2，e3，e4,e5和e6依次通過棧S，一個元素出棧后即進隊列Q，若6個元素出隊的序列是e2，e4，e3,e6,e5,e1則棧S的容量至少應(yīng)該是( )。A 6 B. 4 C. 3 D. 236. 用單鏈表表示的鏈?zhǔn)疥犃械年狀^在鏈表的（ ）位置。A鏈頭 B鏈尾 C鏈中37. 依次讀入數(shù)據(jù)元素序列a，b，c，d，e，f，g進棧,每進一個元素，機器可要求下一個元素進?；驈棗＃绱诉M行，則棧空時彈出的元素構(gòu)成的序列是以下哪些序列？ Ad ，e，c，f，b，g，a B. f，e，g，d，a，c，bC. e，f，d，g，b，c，a D. c，d，b，e，f，a，g二、填空題 1棧是_的線性表，其運算遵循_的原則。2_是限定僅在表尾進行插入或刪除操作的線性表。3. 一個棧的輸入序列是：1，2，3則不可能的棧輸出序列是_。4. 設(shè)有一個空棧，棧頂指針為1000H(十六進制)，現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，輸出序列是_，而棧頂指針值是_H。設(shè)棧為順序棧，每個元素占4個字節(jié)。5. 當(dāng)兩個棧共享一存儲區(qū)時，棧利用一維數(shù)組stack(1,n)表示，兩棧頂指針為top1與top2，則當(dāng)棧1空時，top1為_，棧2空時 ，top2為_，棧滿時為_。6兩個棧共享空間時棧滿的條件_。7在作進棧運算時應(yīng)先判別棧是否_(1)_;在作退棧運算時應(yīng)先判別棧是否_(2)_；當(dāng)棧中元素為n個，作進棧運算時發(fā)生上溢，則說明該棧的最大容量為_(3)_。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個棧共享一片連續(xù)的空間時，應(yīng)將兩棧的_(4)_分別設(shè)在內(nèi)存空間的兩端，這樣只有當(dāng)_(5)_時才產(chǎn)生溢出。8. 多個棧共存時，最好用_作為存儲結(jié)構(gòu)。9用S表示入棧操作，X表示出棧操作，若元素入棧的順序為1234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為_。10. 順序棧用data1.n存儲數(shù)據(jù)，棧頂指針是top,則值為x的元素入棧的操作是_。11表達式23+(12*3-2)/4+34*5/7)+108/9的后綴表達式是_。12. 循環(huán)隊列的引入，目的是為了克服_。 13用下標(biāo)0開始的N元數(shù)組實現(xiàn)循環(huán)隊列時，為實現(xiàn)下標(biāo)變量M加1后在數(shù)組有效下標(biāo)范圍內(nèi)循環(huán)， M= _。14_又稱作先進先出表。15. 隊列的特點是_。16隊列是限制插入只能在表的一端，而刪除在表的另一端進行的線性表，其特點是_。17. 已知鏈隊列的頭尾指針分別是f和r，則將值x入隊的操作序列是_。18區(qū)分循環(huán)隊列的滿與空，只有兩種方法，它們是_和_。19設(shè)循環(huán)隊列用數(shù)組A1.M表示，隊首、隊尾指針分別是FRONT和TAIL，判定隊滿的條件為_。20. 設(shè)循環(huán)隊列存放在向量sq.data0:M中，則隊頭指針sq.front在循環(huán)意義下的出隊操作可表示為_，若用犧牲一個單元的辦法來區(qū)分隊滿和隊空（設(shè)隊尾指針sq.rear）,則隊滿的條件為_。三、基礎(chǔ)知識題1名詞解釋：棧。2名詞解釋：隊列3什么是循環(huán)隊列？4假設(shè)以S和X分別表示入棧和出棧操作，則對初態(tài)和終態(tài)均為空的棧操作可由S和X組成的序列表示（如SXSX）。（1）試指出判別給定序列是否合法的一般規(guī)則。（2）兩個不同合法序列（對同一輸入序列）能否得到相同的輸出元素序列？如能得到，請舉列說明。5. 有5 個元素，其入棧次序為：A，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出棧（即C第一個且D第二個出棧）的次序有哪幾個？ 6.如果輸入序列為1 2 3 4 5 6,試問能否通過棧結(jié)構(gòu)得到以下兩個序列:4 3 5 6 1 2和1 3 5 4 2 6;請說明為什么不能或如何才能得到。7. 若元素的進棧序列為：A、B、C、D、E，運用棧操作，能否得到出棧序列B、C、A、E、D 和D、B、A、C、E？為什么？8. 設(shè)輸入序列為a,b,c,d,試寫出借助一個棧可得到的兩個輸出序列和兩個不能得到的輸出序列。9. 設(shè)輸入序列為2，3，4，5，6，利用一個棧能得到序列2，5，3，4，6嗎？?？梢杂脝捂湵韺崿F(xiàn)嗎？10. 試證明：若借助棧由輸入序列1,2,n得到輸出序列為P1,P2,Pn（它是輸入序列的一個排列），則在輸出序列中不可能出現(xiàn)這樣的情形：存在著ijk,使PjPkPi。11. 設(shè)一數(shù)列的輸入順序為123456，若采用堆棧結(jié)構(gòu)，并以A和D分別表示入棧和出棧操作，試問通過入出棧操作的合法序列。能否得到輸出順序為325641的序列。能否得到輸出順序為154623的序列。12.（1） 什么是遞歸程序？ （2） 遞歸程序的優(yōu)、缺點是什么？ （3） 遞歸程序在執(zhí)行時，應(yīng)借助于什么來完成？（4） 遞歸程序的入口語句、出口語句一般用什么語句實現(xiàn)？ 13. 在一個算法中需要建立多個堆棧時可以選用下列三種方案之一，試問：這三種方案之間相比較各有什么優(yōu)缺點？（1）分別用多個順序存儲空間建立多個獨立的堆棧；（2）多個堆棧共享一個順序存儲空間；（3）分別建立多個獨立的鏈接堆棧。14在某程序中，有兩個棧共享一個一維數(shù)組空間SPACEN、SPACE0、SPACEN-1 分別是兩個棧的棧底。（1）對棧1、棧2，試分別寫出（元素x）入棧的主要語句和出棧的主要語句。（2）對棧1、棧2，試分別寫出棧滿、棧空的條件。15. 簡述順序存儲隊列的假溢出的避免方法及隊列滿和空的條件。16. 舉例說明順序隊的“假溢出”現(xiàn)象，并給出解決方案。17. 怎樣判定循環(huán)隊列的空和滿？18. 簡要敘述循環(huán)隊列的數(shù)據(jù)結(jié)構(gòu)，并寫出其初始狀態(tài)、隊列空、隊列滿時的隊首指針與隊尾指針的值。 四、算法設(shè)計1假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾元素結(jié)點（注意不設(shè)頭指針），試編寫相應(yīng)的初始化隊列、入隊列和出隊列算法。2借助棧(可用棧的基本運算)來實現(xiàn)單鏈表的逆置運算。3假設(shè)一個算術(shù)表達式中可以包含三中括號：圓括號“（”和“）”，方括號“”和“”以及花括號與“”和“”，且這三種括號可按任意的次序嵌套試用，如（. . . . . . . .( . . . .)。試?yán)脳５倪\算編寫判斷給定表達式中所含括號是否正確 配對出現(xiàn)的算法（可設(shè)表達式已存入字符型數(shù)組中）。第四章 串一、選擇題1下面關(guān)于串的的敘述中，哪一個是不正確的？（ ）A 串是字符的有限序列 B空串是由空格構(gòu)成的串C 模式匹配是串的一種重要運算 D串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯? .若串S1=ABCDEFG, S2=9898 ,S3=#,S4=012345,執(zhí)行concat(replace(S1,substr(S1,length(S2),length(S3),S3),substr(S4,index(S2,8),length(S2)其結(jié)果為（ ）AABC#G0123 BABCD#2345 CABC#G2345 DABC#2345EABC#G1234 FABCD#1234 GABC#012343設(shè)有兩個串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（ ）A求子串 B聯(lián)接 C匹配 D求串長4已知串S=aaab,其Next數(shù)組值為（ ）。A0123 B1123 C1231 D12115串 ababaaababaa 的next數(shù)組為（ ）。A012345678999 B012121111212 C011234223456 D01230123223456字符串a(chǎn)babaabab 的nextval 為（ ）A(0,1,0,1,04,1,0,1) B(0,1,0,1,0,2,1,0,1)C(0,1,0,1,0,0,0,1,1) D(0,1,0,1,0,1,0,1,1 )7模式串t=abcaabbcabcaabdab，該模式串的next數(shù)組的值為（ ），nextval數(shù)組的值為 （ ）。