第一章緒論一、選擇題1.算法的計算量的大小稱為計算的（）。A．效率B.復雜性C.現(xiàn)實性D.難度2.算法的時間復雜度取決于（）A．問題的規(guī)模B.待處理數(shù)據(jù)的初態(tài)C.A和B3.計算機算法指的是（1），它必須具備（2）這三個特性。(1)A．計算方法B.排序方法C.解決問題的步驟序列D.調度方法(2)A．可執(zhí)行性、可移植性、可擴充性B.可執(zhí)行性、確定性、有窮性C.確定性、有窮性、穩(wěn)定性D.易讀性、穩(wěn)定性、安全性4．一個算法應該是（）。A．程序B．問題求解步驟的描述C．要滿足五個基本特性D．A和C.5.下面關于算法說法錯誤的是（）A．算法最終必須由計算機程序實現(xiàn)B.為解決某問題的算法同為該問題編寫的程序含義是相同的C.算法的可行性是指指令不能有二義性D.以上幾個都是錯誤的6.下面說法錯誤的是（）(1)算法原地工作的含義是指不需要任何額外的輔助空間（2）在相同的規(guī)模n下，復雜度O(n)的算法在時間上總是優(yōu)于復雜度O(2n)的算法（3）所謂時間復雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界（4）同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低A．(1)B.(1),(2)C.(1),(4)D.(3)7．從邏輯上可以把數(shù)據(jù)結構分為（）兩大類。A．動態(tài)結構、靜態(tài)結構B．順序結構、鏈式結構C．線性結構、非線性結構D．初等結構、構造型結構8．以下與數(shù)據(jù)的存儲結構無關的術語是（）。A．循環(huán)隊列B.鏈表C.哈希表D.棧9．以下數(shù)據(jù)結構中，哪一個是線性結構（）？A．廣義表B.二叉樹C.稀疏矩陣D.串10．以下那一個術語與數(shù)據(jù)的存儲結構無關？（）A．棧B.哈希表C.線索樹D.雙向鏈表11．線性表若采用鏈式存儲結構時，要求內(nèi)存中可用存儲單元的地址（①）。A．必須是連續(xù)的B．部分地址必須是連續(xù)的C．一定是不連續(xù)的D．連續(xù)或不連續(xù)都可以12．在以下的敘述中，正確的是（①）。A．線性表的線性存儲結構優(yōu)于鏈表存儲結構B．二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C．棧的操作方式是先進先出D．隊列的操作方式是先進后出13．以下哪個數(shù)據(jù)結構不是多型數(shù)據(jù)類型（）A．棧B．廣義表C．有向圖D．字符串14．以下數(shù)據(jù)結構中，（）是非線性數(shù)據(jù)結構A．樹B．字符串C．隊D．棧15.下列數(shù)據(jù)中，（）是非線性數(shù)據(jù)結構。A．棧B.隊列C.完全二叉樹D.堆16．連續(xù)存儲設計時，存儲單元的地址（）。A．一定連續(xù)B．一定不連續(xù)C．不一定連續(xù)D．部分連續(xù)，部分不連續(xù)17．以下屬于邏輯結構的是（）。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.關鍵字C.數(shù)據(jù)元素D.數(shù)據(jù)類型20.數(shù)據(jù)結構在計算機中的表示稱為數(shù)據(jù)()。A.對象B.的存儲結構C.類型D.元素21.下列程序段的時間復雜度為()。{for(i=0；i<5；i++)for(j=0；j<n；j++)x=x+1；}A.O(5)B.O(5+n)C.O(n5)D.O(n)22．數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中計算機的（①）以及它們之間的（②）和運算等的學科。

①A．操作對象B．計算方法C．邏輯存儲D．數(shù)據(jù)映象

②A．結構B．關系C．運算D．算法23．數(shù)據(jù)結構被形式地定義為（K，R），其中K是（①）的有限集合，R是K上的（②）的有限集合。

①A．算法B．數(shù)據(jù)元素C．數(shù)據(jù)操作D．邏輯結構

②A．操作B．映象C．存儲D．關系24．在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分成（①）。

A．動態(tài)結構和靜態(tài)結構B．緊湊結構和非緊湊結構

C．線性結構和非線性結構D．內(nèi)部結構和外部結構

25．線性表的順序存儲結構是一種（①）的存儲結構，線性表的鏈式存儲結構是一種（②）的存儲結構。

A．隨機存取B．順序存取C．索引存取D．散列存取

26．算法分析的目的是（①），算法分析的兩個主要方面是（②）。

①A．找出數(shù)據(jù)結構的合理性

B．研究算法中的輸入和輸出的關系

C．分析算法的效率以求改進

D．分析算法的易懂性和文檔性

②A．空間復雜性和時間復雜性

B．正確性和簡明性

C．可讀性和文檔性

D．數(shù)據(jù)復雜性和程序復雜性

27．計算機算法指的是（①），它必具備輸入、輸出和（②）等五個特性。①A．計算方法B．排序方法C．解決問題的有限運算序列D．調度方法②A．可行性、可移植性和可擴充性B．可行性、確定性和有窮性C．確定性、有窮性和穩(wěn)定性D．易讀性、穩(wěn)定性和安全性28．線性表的邏輯順序與存儲順序總是一致的，這種說法（①）。A．正確B．不正確二、填空題1．數(shù)據(jù)的物理結構包括的表示和的表示。2.對于給定的n個元素,可以構造出的邏輯結構有（1），（2），（3），__（4）四種。3．數(shù)據(jù)的邏輯結構是指。4．一個數(shù)據(jù)結構在計算機中稱為存儲結構。5．抽象數(shù)據(jù)類型的定義僅取決于它的一組__（1）_，而與_（2）_無關，即不論其內(nèi)部結構如何變化，只要它的_（3）_不變，都不影響其外部使用。6．數(shù)據(jù)結構中評價算法的兩個重要指標是7.數(shù)據(jù)結構是研討數(shù)據(jù)的_（1）_和_（2）_，以及它們之間的相互關系，并對與這種結構定義相應的_（3）_，設計出相應的（4）_。8．一個算法具有5個特性:（1）、（2）、（3），有零個或多個輸入、有一個或多個輸出。9．下面程序段的時間復雜度為________。(n>1)sum=1；for(i=0;sum<n;i++)sum+=1;10．計算機執(zhí)行下面的語句時，語句s的執(zhí)行次數(shù)為_______。FOR(i=l；i<n-l；i++)FOR(j=n;j>=i;j--)s;11.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是：i：=1；WHILEi<nDOi：=i*2;三、基礎知識題1．數(shù)據(jù)結構是一門研究什么內(nèi)容的學科？2．數(shù)據(jù)元素之間的關系在計算機中有幾種表示方法？各有什么特點？3．數(shù)據(jù)類型和抽象數(shù)據(jù)類型是如何定義的。二者有何相同和不同之處，抽象數(shù)據(jù)類型的主要特點是什么？使用抽象數(shù)據(jù)類型的主要好處是什么？4．回答問題（每題2分）（1）在數(shù)據(jù)結構課程中，數(shù)據(jù)的邏輯結構，數(shù)據(jù)的存儲結構及數(shù)據(jù)的運算之間存在著怎樣的關系？（2）若邏輯結構相同但存儲結構不同，則為不同的數(shù)據(jù)結構。這樣的說法對嗎？舉例說明之。（3）在給定的邏輯結構及其存儲表示上可以定義不同的運算集合，從而得到不同的數(shù)據(jù)結構。這樣說法對嗎？舉例說明之。（4）評價各種不同數(shù)據(jù)結構的標準是什么？5．評價一個好的算法，您是從哪幾方面來考慮的？6．解釋和比較以下各組概念抽象數(shù)據(jù)類型及數(shù)據(jù)類型數(shù)據(jù)結構、邏輯結構、存儲結構抽象數(shù)據(jù)類型算法的時間復雜性（5）算法（6）頻度7.根據(jù)數(shù)據(jù)元素之間的邏輯關系，一般有哪幾類基本的數(shù)據(jù)結構？8．對于一個數(shù)據(jù)結構，一般包括哪三個方面的討論？9.當你為解決某一問題而選擇數(shù)據(jù)結構時，應從哪些方面考慮？10.若將數(shù)據(jù)結構定義為一個二元組（D，R）,說明符號D，R應分別表示什么？11．數(shù)據(jù)結構與數(shù)據(jù)類型有什么區(qū)別？12．數(shù)據(jù)的存儲結構由哪四種基本的存儲方法實現(xiàn)？13．若有100個學生，每個學生有學號，姓名，平均成績，采用什么樣的數(shù)據(jù)結構最方便，寫出這些結構？14.運算是數(shù)據(jù)結構的一個重要方面。試舉一例，說明兩個數(shù)據(jù)結構的邏輯結構和存儲方式完全相同，只是對于運算的定義不同。因而兩個結構具有顯著不同的特性，是兩個不同的結構。15.在編制管理通訊錄的程序時,什么樣的數(shù)據(jù)結構合適?為什么?16.試舉一例，說明對相同的邏輯結構,同一種運算在不同的存儲方式下實現(xiàn)，其運算效率不同。17.有實現(xiàn)同一功能的兩個算法A1和A2，其中A1的時間復雜度為Tl=O(2n)，A2的時間復雜度為T2=O(n2)，僅就時間復雜度而言，請具體分析這兩個算法哪一個好。18．設計一數(shù)據(jù)結構，用來表示某一銀行儲戶的基本信息：賬號、姓名、開戶年月日、儲蓄類型、存入累加數(shù)、利息、帳面總數(shù)。第二章線性表一、選擇題1．下述哪一條是順序存儲結構的優(yōu)點？（）存儲密度大B．插入運算方便C．刪除運算方便D．可方便地用于各種邏輯結構的存儲表示2．下面關于線性表的敘述中，錯誤的是哪一個？（）A．線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B．線性表采用順序存儲，便于進行插入和刪除操作。C．線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D．線性表采用鏈接存儲，便于插入和刪除操作。3．線性表是具有n個（）的有限序列（n>0）。A．表元素B．字符C．數(shù)據(jù)元素D．數(shù)據(jù)項E．信息項4．若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（）存儲方式最節(jié)省時間。A．順序表B．雙鏈表C．帶頭結點的雙循環(huán)鏈表D．單循環(huán)鏈表5．某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（）存儲方式最節(jié)省運算時間。A．單鏈表B．僅有頭指針的單循環(huán)鏈表C．雙鏈表D．僅有尾指針的單循環(huán)鏈表6．設一個鏈表最常用的操作是在末尾插入結點和刪除尾結點，則選用()最節(jié)省時間。A.單鏈表B.單循環(huán)鏈表C.帶尾指針的單循環(huán)鏈表D.帶頭結點的雙循環(huán)鏈表7．若某表最常用的操作是在最后一個結點之后插入一個結點或刪除最后一個結點。則采用（）存儲方式最節(jié)省運算時間。A．單鏈表B．雙鏈表C．單循環(huán)鏈表D．帶頭結點的雙循環(huán)鏈表8.靜態(tài)鏈表中指針表示的是（）.A．內(nèi)存地址B．數(shù)組下標C．下一元素地址D．左、右孩子地址9.鏈表不具有的特點是（）A．插入、刪除不需要移動元素B．可隨機訪問任一元素C．不必事先估計存儲空間D．所需空間與線性長度成正比10.下面的敘述不正確的是（）A．線性表在鏈式存儲時，查找第i個元素的時間同i的值成正比B.線性表在鏈式存儲時，查找第i個元素的時間同i的值無關C.線性表在順序存儲時，查找第i個元素的時間同i的值成正比D.線性表在順序存儲時，查找第i個元素的時間同i的值無關11．雙向鏈表中有兩個指針域，llink和rlink分別指向前趨及后繼，設p指向鏈表中的一個結點，現(xiàn)要求刪去p所指結點，則正確的刪除是（）（鏈中結點數(shù)大于2，p不是第一個結點）A．p^.llink^.rlink:=p^.llink;p^.llink^.rlink:=p^.rlink;dispose(p);B．dispose(p);p^.llink^.rlink:=p^.llink;p^.llink^,rlink:=p^.rlink;C．p^.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無關。(2)靜態(tài)鏈表中能容納的元素個數(shù)的最大數(shù)在表定義時就確定了，以后不能增加。(3)靜態(tài)鏈表與動態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動。以上錯誤的是（）A．（1），（2）B．（1）C．（1），（2）,(3)D.（2）13.若長度為n的線性表采用順序存儲結構，在其第i個位置插入一個新元素的算法的時間復雜度為（）(1<=i<=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)14.對于順序存儲的線性表，訪問結點和增加、刪除結點的時間復雜度為（）。A．O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)15．線性表（a1,a2,…,an）以鏈接方式存儲時，訪問第i位置元素的時間復雜性為（）A．O（i）B．O（1）C．O（n）D．O（i-1）16．非空的循環(huán)單鏈表head的尾結點p↑滿足（）。A．p↑.link=headB．p↑.link=NILC．p=NILD．p=head17．循環(huán)鏈表H的尾結點P的特點是（）。A．P^.NEXT:=HB．P^.NEXT:=H^.NEXTC．P:=HD．P:=H^.NEXT18．在一個以h為頭的單循環(huán)鏈中，p指針指向鏈尾的條件是（）A.p＾.next=hB.p＾.next=NILC.p＾.next.＾next=hD.p＾.data=-119．完成在雙循環(huán)鏈表結點p之后插入s的操作是（）；A．p^.next:=s;s^.priou:=p;p^.next^.priou:=s;s^.next:=p^.next;B．p^.next^.priou:=s;p^.next:=s;s^.priou:=p;s^.next:=p^.next;C．s^.priou:=p;s^.next:=p^.next;p^.next:=s;p^.next^.priou:=s;D．s^.priou:=p;s^.next:=p^.next;p^.next^.priou:=s;p^.next:=s;20．在雙向循環(huán)鏈表中,在p指針所指向的結點前插入一個指針q所指向的新結點,其修改指針的操作是()。注:雙向鏈表的結點結構為(llink,data,rlink)。供選擇的答案：A．p↑.llink：=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:=p；p↑.llink：=q；p↑.llink：=q；21．在非空雙向循環(huán)鏈表中q所指的結點前插入一個由p所指的鏈結點的過程依次為:rlink(p)←q;llink(p)←llink(q);llink(q)←p;（）A．rlink(q)←pB．rlink(llink(q))←pC．rlink(llink(p))←pD．rlink(rlink(p))←p22．雙向鏈表中有兩個指針域，llink和rlink，分別指回前驅及后繼，設p指向鏈表中的一個結點，q指向一待插入結點，現(xiàn)要求在p前插入q，則正確的插入為（）A.p＾.llink:=q;q＾.rlink:=p;p＾.llink＾.rlink:=q;q^.llink:=p^.llink;B.q＾.llink:=p^.llink;p＾.llink^.rlink:=q;q＾.rlink:=p;p^.llink:=q^.rlink;C.q^.rlink:=p;p^.rlink:=q;p^.llink^.rlink:=q;q^.rlink:=p;D.p^.llink^.rlink:=q;q^.rlink:=p;q^.llink:=p^.llink;p^.llink:=q;23．在雙向鏈表指針p的結點前插入一個指針q的結點操作是（）。A.p->Llink=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的結點之后插入指針為s的結點，正確的操作是：（）。A．p->next=s;s->next=p->next;B．s->next=p->next;p->next=s;C．p->next=s;p->next=s->next;D．p->next=s->next;p->next=s;25．對于一個頭指針為head的帶頭結點的單鏈表，判定該表為空表的條件是（）A．head==NULLB．head→next==NULLC．head→next==headD．head!=NULL26.在雙向鏈表存儲結構中，刪除p所指的結點時須修改指針（）。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:=pp^.rlink:=(p^.rlink)^.rlinkD．p^.rlink:=(p^.llink)^.llinkp^.llink:=(p^.rlink)^.rlink;二、填空題1．當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應采用_______存儲結構。2．線性表L=（a1,a2,…,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是________。3．設單鏈表的結點結構為(data,next)，next為指針域，已知指針px指向單鏈表中data為x的結點，指針py指向data為y的新結點,若將結點y插入結點x之后，則需要執(zhí)行以下語句:_______；______;4．在一個長度為n的順序表中第i個元素（1<=i<=n）之前插入一個元素時，需向后移動________個元素。5．在單鏈表中設置頭結點的作用是________。6．對于一個具有n個結點的單鏈表，在已知的結點*p后插入一個新結點的時間復雜度為________,在給定值為x的結點后插入一個新結點的時間復雜度為________。7．根據(jù)線性表的鏈式存儲結構中每一個結點包含的指針個數(shù)，將線性鏈表分成________和_______；而又根據(jù)指針的連接方式，鏈表又可分成________和________。8．在雙向循環(huán)鏈表中,向p所指的結點之后插入指針f所指的結點，其操作是_______、_______、_______、________。9．在雙向鏈表結構中，若要求在p指針所指的結點之前插入指針為s所指的結點，則需執(zhí)行下列語句：s^.next:=p；s^.prior:=________；p^.prior:=s；________:=s；10.鏈接存儲的特點是利用________來表示數(shù)據(jù)元素之間的邏輯關系。11.順序存儲結構是通過________表示元素之間的關系的;鏈式存儲結構是通過________表示元素之間的關系的。12.對于雙向鏈表,在兩個結點之間插入一個新結點需修改的指針共______個，單鏈表為_______個。13.循環(huán)單鏈表的最大優(yōu)點是：________。14.已知指針p指向單鏈表L中的某結點，則刪除其后繼結點的語句是：________15.帶頭結點的雙循環(huán)鏈表L中只有一個元素結點的條件是：________16.在單鏈表L中，指針p所指結點有后繼結點的條件是：__17.帶頭結點的雙循環(huán)鏈表L為空表的條件是：________。18.在單鏈表p結點之后插入s結點的操作是：_______。三、解答題1．線性表有兩種存儲結構：一是順序表，二是鏈表。試問：（1）如果有n個線性表同時并存，并且在處理過程中各表的長度會動態(tài)變化，線性表的總數(shù)也會自動地改變。在此情況下，應選用哪種存儲結構？為什么？（2）若線性表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應采用哪種存儲結構？為什么？2．線性表的順序存儲結構具有三個弱點：其一，在作插入或刪除操作時，需移動大量元素；其二，由于難以估計，必須預先分配較大的空間，往往使存儲空間不能得到充分利用；其三，表的容量難以擴充。線性表的鏈式存儲結構是否一定都能夠克服上述三個弱點，試討論之。3．若較頻繁地對一個線性表進行插入和刪除操作，該線性表宜采用何種存儲結構？為什么？4．線性結構包括______、______、_______和_______。線性表的存儲結構分成______和______。請用類PASCＡL語言描述這兩種結構。5．線性表（a1，a2，…，an）用順序映射表示時，ai和ai+1（1<=i<n）的物理位置相鄰嗎？鏈接表示時呢？6.說明在線性表的鏈式存儲結構中，頭指針與頭結點之間的根本區(qū)別；頭結點與首元結點的關系。7.試述頭結點,首元結點,頭指針這三個概念的區(qū)別.8．有線性表(a1,a2,…,an),采用單鏈表存儲，頭指針為H，每個結點中存放線性表中一個元素，現(xiàn)查找某個元素值等于X的結點。分別寫出下面三種情況的查找語句。要求時間盡量少。（1）線性表中元素無序。（2）線性表中元素按遞增有序。（3）線性表中元素按遞減有序。9.在單鏈表和雙向鏈表中，能否從當前結點出發(fā)訪問到任何一個結點?10.如何通過改鏈的方法，把一個單向鏈表變成一個與原來鏈接方向相反的單向鏈表？11.設單鏈表結點指針域為next，試寫出刪除鏈表中指針p所指結點的直接后繼的C語言語句。12.設單鏈表中某指針p所指結點（即p結點）的數(shù)據(jù)域為data，鏈指針域為next，請寫出在p結點之前插入s結點的操作（PASCAL語句）。四、算法設計題1．假設有兩個按元素值遞增次序排列的線性表，均以單鏈表形式存儲。請編寫算法將這兩個單鏈表歸并為一個按元素值遞減次序排列的單鏈表，并要求利用原來兩個單鏈表的結點存放歸并后的單鏈表。2.知L1、L2分別為兩循環(huán)單鏈表的頭結點指針，m,n分別為L1、L2表中數(shù)據(jù)結點個數(shù)。要求設計一算法，用最快速度將兩表合并成一個帶頭結點的循環(huán)單鏈表。3．在帶頭結點的單鏈表上，給出求表長Length(L)的算法，并加入簡要的注釋或說明。4．設單鏈表具有頭結點，且表中元素各不相同，試給出在單鏈表中查找值為"x"的結點的算法，并加入簡要的注釋或說明。5．設單鏈表具有頭結點，且表中元素各不相同，試給出在單鏈表中刪除值為"x"的結點的算法。第三章棧和隊列一、選擇題1.對于棧操作數(shù)據(jù)的原則是（）。A.先進先出B.后進先出C.后進后出D.不分順序2.在作進棧運算時,應先判別棧是否(①),在作退棧運算時應先判別棧是否(②)。當棧中元素為n個,作進棧運算時發(fā)生上溢,則說明該棧的最大容量為(③)。為了增加內(nèi)存空間的利用率和減少溢出的可能性,由兩個棧共享一片連續(xù)的內(nèi)存空間時,應將兩棧的(④)分別設在這片內(nèi)存空間的兩端,這樣,當(⑤)時，才產(chǎn)生上溢。①,②:A.空B.滿C.上溢D.下溢③:A.n-1B.nC.n+1D.n/2④:A.長度B.深度C.棧頂D.棧底⑤:A.兩個棧的棧頂同時到達棧空間的中心點.B.其中一個棧的棧頂?shù)竭_?？臻g的中心點.C.兩個棧的棧頂在棧空間的某一位置相遇.D.兩個棧均不空,且一個棧的棧頂?shù)竭_另一個棧的棧底.3.一個棧的輸入序列為123…n，若輸出序列的第一個元素是n，輸出第i（1<=i<=n）個元素是（）。A.不確定B.n-i+1C.iD.n-i4.若一個棧的輸入序列為1,2,3,…,n，輸出序列的第一個元素是i，則第j個輸出元素是（）。A.i-j-1B.i-jC.j-i+1D.不確定的5.若已知一個棧的入棧序列是1,2,3,…,n，其輸出序列為p1,p2,p3，…，pN,若pN是n，則pi是()。A.iB.n-iC.n-i+1D.不確定6.有六個元素6，5，4，3，2，1的順序進棧，問下列哪一個不是合法的出棧序列？（）A.543612B.453126C.346521D.2341567.設棧的輸入序列是1，2，3，4,則（）不可能是其出棧序列。A.1，2，4，3，B.2，1，3，4，C.1，4，3，2，D.4，3，1，2，E.3，2，1，4，8.一個棧的輸入序列為12345，則下列序列中不可能是棧的輸出序列的是（）。A.23415B.54132C.23145D.154329.設一個棧的輸入序列是1，2，3，4，5,則下列序列中，是棧的合法輸出序列的是（）。A.51234B.45132C.43125D.3215410.某堆棧的輸入序列為a,b，c，d,下面的四個序列中，不可能是它的輸出序列的是（）。A.a，c，b，dB.b,c，d，aC.c,d，b,aD.d,c，a，b11.設abcdef以所給的次序進棧，若在進棧操作時，允許退棧操作,則下面得不到的序列為（）。A．fedcbaB.bcafedC.dcefbaD.cabdef12.設有三個元素X，Y，Z順序進棧（進的過程中允許出棧），下列得不到的出棧排列是()。A．XYZB.YZXC.ZXYD.ZYX13.輸入序列為ABC，可以變?yōu)镃BA時，經(jīng)過的棧操作為（）A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop14.若一個棧以向量V[1..n]存儲，初始棧頂指針top為n+1，則下面x進棧的正確操作是()。A．top:=top+1;V[top]:=xB.V[top]:=x;top:=top+1C.top:=top-1;V[top]:=xD.V[top]:=x;top:=top-115.若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V[1..m]，top[i]代表第i個棧(i=1,2)棧頂，棧1的底在v[1]，棧2的底在V[m]，則棧滿的條件是（）。A.|top[2]-top[1]|=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]16.棧在（）中應用。A.遞歸調用B.子程序調用C.表達式求值D.A，Ｂ，Ｃ17.一個遞歸算法必須包括（）。A.遞歸部分B.終止條件和遞歸部分C.迭代部分D.終止條件和迭代部分18.執(zhí)行完下列語句段后，i值為：（）intf(intx){return((x>0)?x*f(x-1):2);}inti;i=f(f(1));A．2B.4C.8D.無限遞歸19.表達式a*(b+c)-d的后綴表達式是()。A．a(chǎn)bcd*+-B.abc+*d-C.abc*+d-D.-+*abcd20.表達式3*2^(4+2*2-6*3)-5求值過程中當掃描到6時，對象棧和算符棧為（），其中^為乘冪。A.3,2,4,1,1；(*^(+*-B.3,2,8；(*^-C.3,2,4,2,2；(*^(-D.3,2,8；(*^(-21.設計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用（）數(shù)據(jù)結構最佳。A．線性表的順序存儲結構B.隊列C.線性表的鏈式存儲結構D.棧22.用鏈接方式存儲的隊列，在進行刪除運算時（）。A.僅修改頭指針B.僅修改尾指針C.頭、尾指針都要修改D.頭、尾指針可能都要修改23.用不帶頭結點的單鏈表存儲隊列時,其隊頭指針指向隊頭結點,其隊尾指針指向隊尾結點，則在進行刪除操作時()。A．僅修改隊頭指針B.僅修改隊尾指針C.隊頭、隊尾指針都要修改D.隊頭,隊尾指針都可能要修改24.遞歸過程或函數(shù)調用時，處理參數(shù)及返回地址，要用一種稱為（）的數(shù)據(jù)結構。A．隊列B．多維數(shù)組C．棧D.線性表25.假設以數(shù)組A[m]存放循環(huán)隊列的元素,其頭尾指針分別為front和rear，則當前隊列中的元素個數(shù)為（）。A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m26.循環(huán)隊列A[0..m-1]存放其元素值，用front和rear分別表示隊頭和隊尾，則當前隊列中的元素數(shù)是()。A.(rear-front+m)%mB.rear-front+1C.rear-front-1D.rear-front27.循環(huán)隊列存儲在數(shù)組A[0..m]中，則入隊時的操作為（）。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)28.若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為多少？()A.1和5B.2和4C.4和2D.5和129.已知輸入序列為abcd經(jīng)過輸出受限的雙向隊列后能得到的輸出序列有（）。A.dacbB.cadbC.dbcaD.bdacE.以上答案都不對30.若以1234作為雙端隊列的輸入序列，則既不能由輸入受限的雙端隊列得到，也不能由輸出受限的雙端隊列得到的輸出序列是()。A.1234B.4132C.4231D.421331.最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是（）。A.(rear+1)MODn=frontB.rear=frontC．rear+1=frontD.(rear-l)MODn=front32.棧和隊列的共同點是（）。A.都是先進先出B.都是先進后出C.只允許在端點處插入和刪除元素D.沒有共同點33.棧的特點是（①）,隊列的特點是（②）,棧和隊列都是（③）。若進棧序列為1,2,3,4則（④）不可能是一個出棧序列（不一定全部進棧后再出棧）；若進隊列的序列為1,2,3,4則（⑤）是一個出隊列序列。①,②:A.先進先出B.后進先出C.進優(yōu)于出D.出優(yōu)于進③:A.順序存儲的線性結構B.鏈式存儲的線性結構C.限制存取點的線性結構D.限制存取點的非線性結構④,⑤:A.3,2,1,4B.3,2,4,1C.4,2,3,1D.4,3,2,1F.1,2,3,4G.1,3,2,434.棧和隊都是（）A．順序存儲的線性結構B.鏈式存儲的非線性結構C.限制存取點的線性結構D.限制存取點的非線性結構35.設棧S和隊列Q的初始狀態(tài)為空，元素e1，e2，e3，e4,e5和e6依次通過棧S，一個元素出棧后即進隊列Q，若6個元素出隊的序列是e2，e4，e3,e6,e5,e1則棧S的容量至少應該是()。A．6B.4C.3D.236.用單鏈表表示的鏈式隊列的隊頭在鏈表的（）位置。A．鏈頭B．鏈尾C．鏈中37.依次讀入數(shù)據(jù)元素序列{a，b，c，d，e，f，g}進棧,每進一個元素，機器可要求下一個元素進棧或彈棧，如此進行，則?？諘r彈出的元素構成的序列是以下哪些序列？A．{d，e，c，f，b，g，a}B.{f，e，g，d，a，c，b}C.{e，f，d，g，b，c，a}D.{c，d，b，e，f，a，g}

二、填空題1．棧是_______的線性表，其運算遵循_______的原則。2．_______是限定僅在表尾進行插入或刪除操作的線性表。3.一個棧的輸入序列是：1，2，3則不可能的棧輸出序列是_______。4.設有一個空棧，棧頂指針為1000H(十六進制)，現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，輸出序列是_______，而棧頂指針值是_______H。設棧為順序棧，每個元素占4個字節(jié)。5.當兩個棧共享一存儲區(qū)時，棧利用一維數(shù)組stack(1,n)表示，兩棧頂指針為top[1]與top[2]，則當棧1空時，top[1]為_______，棧2空時，top[2]為_______，棧滿時為_______。6．兩個棧共享空間時棧滿的條件_______。7．在作進棧運算時應先判別棧是否_(1)_;在作退棧運算時應先判別棧是否_(2)_；當棧中元素為n個，作進棧運算時發(fā)生上溢，則說明該棧的最大容量為_(3)_。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個棧共享一片連續(xù)的空間時，應將兩棧的_(4)_分別設在內(nèi)存空間的兩端，這樣只有當_(5)_時才產(chǎn)生溢出。8.多個棧共存時，最好用_______作為存儲結構。9．用S表示入棧操作，X表示出棧操作，若元素入棧的順序為1234，為了得到1342出棧順序，相應的S和X的操作串為_______。10.順序棧用data[1..n]存儲數(shù)據(jù)，棧頂指針是top,則值為x的元素入棧的操作是_______。11．表達式23+((12*3-2)/4+34*5/7)+108/9的后綴表達式是_______。12.循環(huán)隊列的引入，目的是為了克服_______。13．用下標0開始的N元數(shù)組實現(xiàn)循環(huán)隊列時，為實現(xiàn)下標變量M加1后在數(shù)組有效下標范圍內(nèi)循環(huán)，M=_______。14．________又稱作先進先出表。15.隊列的特點是_______。16．隊列是限制插入只能在表的一端，而刪除在表的另一端進行的線性表，其特點是_______。17.已知鏈隊列的頭尾指針分別是f和r，則將值x入隊的操作序列是_______。18．區(qū)分循環(huán)隊列的滿與空，只有兩種方法，它們是______和______。19．設循環(huán)隊列用數(shù)組A[1..M]表示，隊首、隊尾指針分別是FRONT和TAIL，判定隊滿的條件為_______。20.設循環(huán)隊列存放在向量sq.data[0:M]中，則隊頭指針sq.front在循環(huán)意義下的出隊操作可表示為_______，若用犧牲一個單元的辦法來區(qū)分隊滿和隊空（設隊尾指針sq.rear）,則隊滿的條件為_______。三、基礎知識題1．名詞解釋：棧。2．名詞解釋：隊列3．什么是循環(huán)隊列？4．假設以S和X分別表示入棧和出棧操作，則對初態(tài)和終態(tài)均為空的棧操作可由S和X組成的序列表示（如SXSX）。（1）試指出判別給定序列是否合法的一般規(guī)則。（2）兩個不同合法序列（對同一輸入序列）能否得到相同的輸出元素序列？如能得到，請舉列說明。5.有5個元素，其入棧次序為：A，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出棧（即C第一個且D第二個出棧）的次序有哪幾個？6.如果輸入序列為123456,試問能否通過棧結構得到以下兩個序列:435612和135426;請說明為什么不能或如何才能得到。7.若元素的進棧序列為：A、B、C、D、E，運用棧操作，能否得到出棧序列B、C、A、E、D和D、B、A、C、E？為什么？8.設輸入序列為a,b,c,d,試寫出借助一個棧可得到的兩個輸出序列和兩個不能得到的輸出序列。9.設輸入序列為2，3，4，5，6，利用一個棧能得到序列2，5，3，4，6嗎？棧可以用單鏈表實現(xiàn)嗎？10.試證明：若借助棧由輸入序列1,2,…,n得到輸出序列為P1,P2,…,Pn（它是輸入序列的一個排列），則在輸出序列中不可能出現(xiàn)這樣的情形：存在著i<j<k,使Pj<Pk<Pi。11.設一數(shù)列的輸入順序為123456，若采用堆棧結構，并以A和D分別表示入棧和出棧操作，試問通過入出棧操作的合法序列。能否得到輸出順序為325641的序列。能否得到輸出順序為154623的序列。12.（1）什么是遞歸程序？（2）遞歸程序的優(yōu)、缺點是什么？（3）遞歸程序在執(zhí)行時，應借助于什么來完成？（4）遞歸程序的入口語句、出口語句一般用什么語句實現(xiàn)？13.在一個算法中需要建立多個堆棧時可以選用下列三種方案之一，試問：這三種方案之間相比較各有什么優(yōu)缺點？（1）分別用多個順序存儲空間建立多個獨立的堆棧；（2）多個堆棧共享一個順序存儲空間；（3）分別建立多個獨立的鏈接堆棧。14．在某程序中，有兩個棧共享一個一維數(shù)組空間SPACE[N]、SPACE[0]、SPACE[N-1]分別是兩個棧的棧底。（1）對棧1、棧2，試分別寫出（元素x）入棧的主要語句和出棧的主要語句。（2）對棧1、棧2，試分別寫出棧滿、?？盏臈l件。15.簡述順序存儲隊列的假溢出的避免方法及隊列滿和空的條件。16.舉例說明順序隊的“假溢出”現(xiàn)象，并給出解決方案。17.怎樣判定循環(huán)隊列的空和滿？18.簡要敘述循環(huán)隊列的數(shù)據(jù)結構，并寫出其初始狀態(tài)、隊列空、隊列滿時的隊首指針與隊尾指針的值。四、算法設計1．假設以帶頭結點的循環(huán)鏈表表示隊列，并且只設一個指針指向隊尾元素結點（注意不設頭指針），試編寫相應的初始化隊列、入隊列和出隊列算法。2．借助棧(可用棧的基本運算)來實現(xiàn)單鏈表的逆置運算。3．假設一個算術表達式中可以包含三中括號：圓括號“（”和“）”，方括號“[”和“]”以及花括號與“{”和“}”，且這三種括號可按任意的次序嵌套試用，如（...[...{...}...[...]...]...(...[...]...)。試利用棧的運算編寫判斷給定表達式中所含括號是否正確配對出現(xiàn)的算法（可設表達式已存入字符型數(shù)組中）。第四章串一、選擇題1．下面關于串的的敘述中，哪一個是不正確的？（）串是字符的有限序列B．空串是由空格構成的串模式匹配是串的一種重要運算D．串既可以采用順序存儲，也可以采用鏈式存儲2.若串S1=‘ABCDEFG’,S2=‘9898’,S3=‘###’,S4=‘012345’concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’其結果為（）A．ABC###G0123B．ABCD###2345C．ABC###G2345D．ABC###2345E．ABC###G1234F．ABCD###1234G．ABC###012343．設有兩個串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（）A．求子串B．聯(lián)接C．匹配D．求串長4．已知串S=‘a(chǎn)aab’,其Next數(shù)組值為（）。A．0123B．1123C．1231D．12115．串‘a(chǎn)babaaababaa’的next數(shù)組為（）。A．．．．6．字符串‘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=‘a(chǎn)bcaabbcabcaabdab’，該模式串的next數(shù)組的值為（），nextval數(shù)組的值為（）。A．01112211123456712B．01112121123456112C．01110013101100701D．01112231123456712E．01100111011001701F．011021310110217018．若串S=’software’,其子串的數(shù)目是（）。A．8B．37C．36D．99．設S為一個長度為n的字符串，其中的字符各不相同，則S中的互異的非平凡子串（非空且不同于S本身）的個數(shù)為（）。A．2n-1B．n2C．(n2/2)+(n/2)D．(n2/2)+(n/2)-1E.(n2/2)-(n/2)-1F.其他情況10．串的長度是指（）A．串中所含不同字母的個數(shù)B．串中所含字符的個數(shù)C．串中所含不同字符的個數(shù)D．串中所含非空格字符的個數(shù)二、填空題1.空格串是指__(1)__，其長度等于___(2)__。2.組成串的數(shù)據(jù)元素只能是________。3.一個字符串中________稱為該串的子串。4.INDEX（‘DATASTRUCTURE’，‘STR’）=________。5．設正文串長度為n，模式串長度為m，則串匹配的KMP算法的時間復雜度為________。6．模式串P=‘a(chǎn)baabcac’的next函數(shù)值序列為________。7．字符串’ababaaab’的nextval函數(shù)值為________。8．設T和P是兩個給定的串，在T中尋找等于P的子串的過程稱為__(1)__，又稱P為__(2)__。9．串是一種特殊的線性表，其特殊性表現(xiàn)在__(1)__；串的兩種最基本的存儲方式是__(2)__、__(3)__；兩個串相等的充分必要條件是__(4)__。10．兩個字符串相等的充分必要條件是_______。11．知U=‘xyxyxyxxyxy’；t=‘xxy’；ASSIGN（S，U）；ASSIGN（V，SUBSTR（S，INDEX（s，t），LEN（t）+1））；ASSIGN（m，‘ww’）求REPLACE（S，V，m）=________。12．實現(xiàn)字符串拷貝的函數(shù)strcpy為：voidstrcpy(char*s,char*t)/*copyttos*/{while(________)}13．下列程序判斷字符串s是否對稱，對稱則返回1，否則返回0；如f("abba")返回1，f("abab")返回0；intf((1)________){inti=0,j=0;while(s[j])(2)________;for(j--;i<j&&s[i]==s[j];i++,j--);return((3)_______)}三、基礎知識題1．名詞解釋：串2．描述以下概念的區(qū)別：空格串與空串。3．兩個字符串S1和S2的長度分別為m和n。求這兩個字符串最大共同子串算法的時間復雜度為T(m,n)。估算最優(yōu)的T(m,n)，并簡要說明理由。4．設主串S=‘xxyxxxyxxxxyxyx’，模式串T=‘xxyxy’。請問：如何用最少的比較次數(shù)找到T在S中出現(xiàn)的位置？相應的比較次數(shù)是多少？5．KMP算法(字符串匹配算法)較Brute(樸素的字符串匹配)算法有哪些改進?6．已知模式串t=‘a(chǎn)bcaabbabcab’寫出用KMP法求得的每個字符對應的next和nextval函數(shù)值。7．給出字符串‘a(chǎn)bacabaaad’在KMP算法中的next和nextval數(shù)組。8．令t=‘a(chǎn)bcabaa’,求其next函數(shù)值和nextval函數(shù)值。9．已知字符串‘cddcdececdea’，計算每個字符的next和nextval函數(shù)的值。四、算法設計1．設s、t為兩個字符串，分別放在兩個一維數(shù)組中，m、n分別為其長度，判斷t是否為s的子串。如果是，輸出子串所在位置（第一個字符），否則輸出0。（注：用程序實現(xiàn)）2．輸入一個字符串，內(nèi)有數(shù)字和非數(shù)字字符，如：ak123x45617960?302gef4563，將其中連續(xù)的數(shù)字作為一個整體，依次存放到一數(shù)組ａ中，例如123放入ａ［０］,456放入ａ［１］，……。編程統(tǒng)計其共有多少個整數(shù)，并輸出這些數(shù)。3．以順序存儲結構表示串，設計算法。求串S中出現(xiàn)的第一個最長重復子串及其位置并分析算法的時間復雜度。4．編寫程序，統(tǒng)計在輸入字符串中各個不同字符出現(xiàn)的頻度并將結果存入文件（字符串中的合法字符為A-Z這26個字母和0-9這10個數(shù)字）。5．寫一個遞歸算法來實現(xiàn)字符串逆序存儲，要求不另設串存儲空間。第五章數(shù)組和廣義表一、選擇題1.設有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為（）。A.13B.33C.18D.402.有一個二維數(shù)組A[1:6，0:7]每個數(shù)組元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址，那么這個數(shù)組的體積是（①）個字節(jié)。假設存儲數(shù)組元素A[1，0]的第一個字節(jié)的地址是0，則存儲數(shù)組A的最后一個元素的第一個字節(jié)的地址是（②）。若按行存儲，則A[2，4]的第一個字節(jié)的地址是（③）。若按列存儲，則A[5，7]的第一個字節(jié)的地址是（④）。就一般情況而言，當（⑤）時，按行存儲的A[I，J]地址與按列存儲的A[J，I]地址相等。供選擇的答案：①-④：A．12B.66C.72D.96E.114F.120G.156H.234I.276J.282K.283L.288⑤：A．行與列的上界相同B.行與列的下界相同C.行與列的上、下界都相同D.行的元素個數(shù)與列的元素個數(shù)相同3.設有數(shù)組A[i,j]，數(shù)組的每個元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當用以列為主存放時，元素A[5，8]的存儲首地址為()。A.BA+141B.BA+180C.BA+222D.BA+2254.假設以行序為主序存儲二維數(shù)組A=array[1..100，1..100]，設每個數(shù)據(jù)元素占2個存儲單元，基地址為10，則LOC[5，5]=（）。A.808B.818C.1010D.10205.數(shù)組A[0..5,0..6]的每個元素占五個字節(jié)，將其按列優(yōu)先次序存儲在起始地址為1000的內(nèi)存單元中，則元素A[5，5]的地址是()。A.1175B.1180C.1205D.12106.有一個二維數(shù)組A[0:8,1:5],每個數(shù)組元素用相鄰的4個字節(jié)存儲，存儲器按字節(jié)編址，假設存儲數(shù)組元素A[0,1]的第一個字節(jié)的地址是0，存儲數(shù)組A的最后一個元素的第一個字節(jié)的地址是（①）。若按行存儲，則A[3,5]和A[5,3]的第一個字節(jié)的地址是（②）和（③）。若按列存儲，則A[7,1]和A[2,4]的第一個字節(jié)的地址是（④）和（⑤）。①-⑤:A.28B.44C.76D.92E.108F.116G.132H.176I.184J.1887.將一個A[1..100，1..100]的三對角矩陣，按行優(yōu)先存入一維數(shù)組B[1‥298]中，A中元素A6665（即該元素下標i=66，j=65），在B數(shù)組中的位置K為（）。供選擇的答案：A.198B.195C.1978.二維數(shù)組A的元素都是6個字符組成的串，行下標i的范圍從0到8，列下標j的范圈從1到10。從供選擇的答案中選出應填入下列關于數(shù)組存儲敘述中（）內(nèi)的正確答案。（1）存放A至少需要（）個字節(jié)；（2）A的第8列和第5行共占（）個字節(jié)；（3）若A按行存放，元素A[8，5]的起始地址與A按列存放時的元素（）的起始地址一致。供選擇的答案：（1）A.90B.180C.240D.270E.540（2）A.108B.114C.54D.60E.150（3）A.A[8,5]B.A[3,10]C.A[5,8]D.A[0,9]9.二維數(shù)組A的每個元素是由6個字符組成的串，其行下標i=0,1,…,8,列下標j=1,2,…,10。若A按行先存儲，元素A[8,5]的起始地址與當A按列先存儲時的元素（）的起始地址相同。設每個字符占一個字節(jié)。A.A[8,5]B.A[3,10]C.A[5,8]D.A[0,9]10.若對n階對稱矩陣A以行序為主序方式將其下三角形的元素(包括主對角線上所有元素)依次存放于一維數(shù)組B［1..(n(n+1))/2］中，則在B中確定aij（i<j）的位置k的關系為()。A.i*(i-1)/2+jB.j*(j-1)/2+iC.i*(i+1)/2+jD.j*(j+1)/2+i11.設A是n*n的對稱矩陣，將A的對角線及對角線上方的元素以列為主的次序存放在一維數(shù)組B[1..n(n+1)/2]中，對上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置為()。A.i(i-l)/2+jB.j(j-l)/2+iC.j(j-l)/2+i-1D.i(i-l)/2+j-112.A[N，N]是對稱矩陣，將下面三角（包括對角線）以行序存儲到一維數(shù)組T[N（N+1）/2]中，則對任一上三角元素a[i][j]對應T[k]的下標k是（）。A.i（i-1）/2+jB.j（j-1）/2+iC.i（j-i）/2+1D.j（i-1）/2+113.設二維數(shù)組A[1..m，1..n]（即m行n列）按行存儲在數(shù)組B[1..m*n]中，則二維數(shù)組元素A[i，j]在一維數(shù)組B中的下標為()。A.（i-1）*n+jB.（i-1）*n+j-1C.i*（j-1）D.j*m+i-114.有一個100*90的稀疏矩陣，非0元素有10個，設每個整型數(shù)占2字節(jié)，則用三元組表示該矩陣時，所需的字節(jié)數(shù)是（）。A.60B.66C.18000D.3315.數(shù)組A[0..4,-1..-3,5..7]中含有元素的個數(shù)（）?！局猩酱髮W1998二、5（2分）】A.55B.45C.36D.1616.用數(shù)組r存儲靜態(tài)鏈表，結點的next域指向后繼，工作指針j指向鏈中結點，使j沿鏈移動的操作為()。A.j=r[j].nextB.j=j+1C.j=j->nextD.j=r[j]->next17.對稀疏矩陣進行壓縮存儲目的是（）。A.便于進行矩陣運算B．便于輸入和輸出C．節(jié)省存儲空間D．降低運算的時間復雜度18.已知廣義表L=（（x,y,z），a，（u，t，w）），從L表中取出原子項t的運算是（）。A.head（tail（tail（L）））B.tail（head（head（tail（L））））C.head（tail（head（tail（L））））D.head（tail(head（tail（tail（L）））)）19.已知廣義表LS＝((a,b,c),(d,e,f)),運用head和tail函數(shù)取出LS中原子e的運算是()。A.head(tail(LS))B.tail(head(LS))C.head(tail(head(tail(LS)))D.head(tail(tail(head(LS))))20.廣義表A=(a,b,(c,d),(e,(f,g))),則下面式子的值為（）。Head(Tail(Head(Tail(TailA))))A.(g)B.DC.cD.d21.已知廣義表:A=(a,b),B=(A,A),C=(a,(b,A),B),求下列運算的結果:tail(head(tailC))=()。A.（a）B.AC.aD.BE.bF.A22.廣義表運算式Tail(((a,b),(c,d)))的操作結果是（）。A.(c,d)B.c,dC.((c,d))D.d23.廣義表L=（a，（b，c）），進行Tail（L）操作后的結果為（）。A.cB.b，cC.（b，c）D.（（b，c））24.廣義表（（a,b,c,d））的表頭是（），表尾是（）。A.aB.（）C.（a,b,c,d）D.（b,c,d）25.廣義表（a,(b,c),d,e）的表頭為（）。A.aB.a,(b,c)C.(a,(b,c))D.A26.設廣義表L=（（a,b,c）），則L的長度和深度分別為（）。A.1和1B.1和3C.1和2D.2和327.下面說法不正確的是()。A.廣義表的表頭總是一個廣義表B.廣義表的表尾總是一個廣義表C.廣義表難以用順序存儲結構D.廣義表可以是一個多層次的結構二、填空題1.數(shù)組的存儲結構采用_______存儲方式。2.設二維數(shù)組A[-20..30,-30..20],每個元素占有4個存儲單元,存儲起始地址為200.如按行優(yōu)先順序存儲,則元素A[25,18]的存儲地址為__（1）_；如按列優(yōu)先順序存儲,則元素A[-18,-25]的存儲地址為__（2）_。3.設數(shù)組a[1..50,1..80]的基地址為2000，每個元素占2個存儲單元，若以行序為主序順序存儲，則元素a[45,68]的存儲地址為_（1）_;若以列序為主序順序存儲，則元素a[45,68]的存儲地址為_（2）_。4.將整型數(shù)組A[1..8，1..8]按行優(yōu)先次序存儲在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A[7，3]的地址是：_______。5.二維數(shù)組a[4][5][6]（下標從0開始計，a有4*5*6個元素），每個元素的長度是2，則a[2][3][4]的地址是____。(設a[0][0][0]的地址是1000,數(shù)據(jù)以行為主方式存儲)6.設有二維數(shù)組A[0..9,0..19],其每個元素占兩個字節(jié)，第一個元素的存儲地址為100，若按列優(yōu)先順序存儲，則元素A[6,6]存儲地址為_______。7.已知數(shù)組A[0..9,0..9]的每個元素占5個存儲單元，將其按行優(yōu)先次序存儲在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A[6，8]的地址為_______。8.已知二維數(shù)組A[1..10，0..9]中每個元素占4個單元，在按行優(yōu)先方式將其存儲到起始地址為1000的連續(xù)存儲區(qū)域時，A[5，9]的地址是：_______。9.用一維數(shù)組B與列優(yōu)先存放帶狀矩陣A中的非零元素A[i,j](1≤i≤n,i-2≤j≤i+2),B中的第8個元素是A中的第_（1）_行，第_（2）_列的元素。10.設數(shù)組A[0..8,1..10],數(shù)組中任一元素A[i,j]均占內(nèi)存48個二進制位，從首地址2000開始連續(xù)存放在主內(nèi)存里，主內(nèi)存字長為16位，那么（l）存放該數(shù)組至少需要的單元數(shù)是_______;（2）存放數(shù)組的第8列的所有元素至少需要的單元數(shù)是_______;（3）數(shù)組按列存儲時，元素A[5,8]的起始地址是_______。11.當廣義表中的每個元素都是原子時，廣義表便成了_______。12.廣義表的表尾是指除第一個元素之外，_______。13.廣義表簡稱表，是由零個或多個原子或子表組成的有限序列，原子與表的差別僅在于(1)____。為了區(qū)分原子和表，一般用(2)____表示表，用(3)_____表示原子。一個表的長度是指(4)__，而表的深度是指__(5)__14.廣義表的_______定義為廣義表中括弧的重數(shù)。15．設廣義表L=((),()),則head(L)是(1)___；tail(L)是(2)____；L的長度是(3)___；深度是(4)__。16.已知廣義表A=(9,7,(8,10,(99)),12)，試用求表頭和表尾的操作Head()和Tail()將原子元素99從A中取出來。17.廣義表的深度是_______。三、基礎知識題1.數(shù)組A[1..8，-2..6，0..6]以行為主序存儲，設第一個元素的首地址是78，每個元素的長度為4，試求元素A[4,2,3]的存儲首地址。2.已知b對角矩陣（aij）n*n，以行主序將b條對角線上的非零元存儲在一維數(shù)組中，每個數(shù)據(jù)元素占Ｌ個存儲單元，存儲基地址為Ｓ，請用i，j表示出aij的存儲位置。3.數(shù)組A中，每個元素A[i,j]的長度均為32個二進位,行下標從-1到9，列下標從1到11，從首地址S開始連續(xù)存放主存儲器中，主存儲器字長為16位。求：（1）存放該數(shù)組所需多少單元？（2）存放數(shù)組第4列所有元素至少需多少單元？（3）數(shù)組按行存放時，元素A[7,4]的起始地址是多少？（4）數(shù)組按列存放時，元素A[4,7]的起始地址是多少？4．假設按低下標優(yōu)先存儲整型數(shù)組A（-3:8,3:5,-4:0,0:7）時，第一個元素的字節(jié)存儲地址是100，每個整數(shù)占4個字節(jié)，問A（0，4，-2，5）的存儲地址是什么？5．設有三維數(shù)組A[-2:4,0:3,-5:1]按列序存放，數(shù)組的起始地址為1210，試求A(1,3,-2)所在的地址。6.三維數(shù)組A[1..10,-2..6,2..8]的每個元素的長度為4個字節(jié)，試問該數(shù)組要占多少個字節(jié)的存儲空間？如果數(shù)組元素以行優(yōu)先的順序存貯，設第一個元素的首地址是100，試求元素A[5,0,7]的存貯首地址。四、算法設計題1.設有大小不等的n

個數(shù)據(jù)組（n個數(shù)據(jù)組中數(shù)據(jù)的總數(shù)為m），順序存放在空間區(qū)D內(nèi),每個數(shù)據(jù)占一個存儲單元，數(shù)據(jù)組的首地址由數(shù)組S給出，（如下圖所示），試編寫將新數(shù)據(jù)x插入到第i個數(shù)據(jù)組的末尾且屬于第i個數(shù)據(jù)組的算法，插入后，空間區(qū)D和數(shù)組S的相互關系仍保持正確。2.數(shù)組H[1：1000]中存放著1000個大小不同的正整數(shù);（1）選擇一分類算法使能最快地得到其中10個最大的數(shù)，簡要說明理由；（2）編寫一程序seek()，執(zhí)行該程序時，在命令行中提供二個參數(shù)；seekan<enter>表示需打印H[]中n個最大數(shù)。seekIn<enter>表示需打印H[]中n個最小數(shù)。第六章樹和二叉樹一、選擇題1．樹最適合用來表示（）。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間具有分支層次關系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)2．深度為5的二叉樹至多有（）個結點。A．16B．32C．31D．103．有32個結點的完全二叉樹的深度為（）（根的層次為1）。A．8B．7C．6D．54．若二叉樹中度為2的結點有15個，度為1的結點有10個，則有（）個葉結點。A．25B．15C．16D．415．在有n個結點的二叉鏈表