數(shù)據(jù)結(jié)構(gòu)期末習(xí)題答案

1、第一章 緒 論一，選擇題1組成數(shù)據(jù)的基本單位是（）A數(shù)據(jù)項B數(shù)據(jù)類型C數(shù)據(jù)元素D數(shù)據(jù)變量2數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的（）以及它們之間的相互關(guān)系。A理想結(jié)構(gòu)，物理結(jié)構(gòu) B理想結(jié)構(gòu)，抽象結(jié)構(gòu)C物理結(jié)構(gòu)，邏輯結(jié)構(gòu) D抽象結(jié)構(gòu)，邏輯結(jié)構(gòu)3算法分析的兩個主要方面是（ ）A正確性和簡單性 B可讀性和文檔性C數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 D時間復(fù)雜度和空間復(fù)雜度4算法分析的目的是（）。A 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B研究算法中的輸入和輸出的關(guān)系C分析算法的效率以求改進D分析算法的易懂性和文檔性5. 算法的時間復(fù)雜度取決于（ ）A問題的規(guī)模 B. 待處理數(shù)據(jù)的初態(tài) C. A和B 以上都不是6一個算法應(yīng)該是（ ）。 A程序 B

2、問題求解步驟的描述 C要滿足五個基本特性 DA和C. 7. 下面關(guān)于算法說法錯誤的是（ ）A算法最終必須由計算機程序?qū)崿F(xiàn)B.為解決某問題的算法同為該問題編寫的程序含義是相同的C. 算法的可行性是指指令不能有二義性 D. 以上幾個都是錯誤的8從邏輯上可以把數(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)9程序段 for ( i=n-1;i>=1;i-) for (j=1j<=i;j+) if( Aj>Aj+1) Aj與Aj+1對換；其中 n為正整數(shù)，則最后一行的語句頻度在最壞情況下是（ ）A O（n） B O(

3、nlogn) C.O(n3) DO(n2) 10連續(xù)存儲設(shè)計時，存儲單元的地址（ ）。A一定連續(xù) B一定不連續(xù) C不一定連續(xù) D部分連續(xù)，部分不連續(xù)二，判斷題1數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實現(xiàn)有關(guān)。( ) 2數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)對象與對象中數(shù)據(jù)元素之間關(guān)系的集合。3在順序存儲結(jié)構(gòu)中，有時也存儲數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。( )4數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用的需要建立的。5算法和程序原則上沒有區(qū)別，在討論數(shù)據(jù)結(jié)構(gòu)是兩者是通用的。6同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性是指數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)都相等。7數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。8算法的優(yōu)

4、劣與算法描述語言無關(guān)，但與所用計算機有關(guān)。( )9健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。( )10算法可以用不同的語言描述，如果用C 語言或PASCAL語言等高級語言來描述，則算法實際上就是程序了。( ) 一，選擇題1C2C3D4C5C6B7D8C9D10A二，判斷題1. ×2. 3. ×4. 5.×6. ×7. 8.×9. 10.×三，填空1數(shù)據(jù)的物理結(jié)構(gòu)包括 的表示和 的表示。2. 對于給定的n個元素,可以構(gòu)造出的邏輯結(jié)構(gòu)有 ， ， ，_ _四種。3一個數(shù)據(jù)結(jié)構(gòu)在計算機中 稱為存儲結(jié)構(gòu)。4抽象數(shù)據(jù)類型的定義僅取決于它

5、的一組_ _，而與_ _無關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的_ _不變，都不影響其外部使用。5線性結(jié)構(gòu)中元素之間存在 關(guān)系,樹形結(jié)構(gòu)中元素之間存在 關(guān)系,圖形結(jié)構(gòu)中元素之間存在 關(guān)系。6一個算法有5個特性: 、 、 ，有零個或多個輸入、有一個或多個輸出。7已知如下程序段for （i= n；i<=1;i+） 語句1x:=x+1； 語句2for( j=n;j<=i ;j+) 語句3 y:=y+1; 語句4語句1執(zhí)行的頻度為 ；語句2執(zhí)行的頻度為 ；語句3執(zhí)行的頻度為 ；語句4執(zhí)行的頻度為 。8在下面的程序段中，對的賦值語句的頻度為_（表示為n的函數(shù)） for(i1;i<=n;

6、i+)for(j;j<=i;j+)for(k1;k<=j;j+)delta；9. 計算機執(zhí)行下面的語句時，語句s的執(zhí)行次數(shù)為 _ 。 for(i=l；i<n-l；i+) for(j=n;j>=i;j-) s; 10. 下面程序段的時間復(fù)雜度為_。(n>1) sum=1； for (i=0;sum<n;i+) sum+=1; 三，填空題1數(shù)據(jù)元素 數(shù)據(jù)元素間關(guān)系 2集合 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)3表示（又稱映像）。 4邏輯特性 在計算機內(nèi)部如何表示和實現(xiàn) 數(shù)學(xué)特性5 一對一一對多多對多6 有窮性 確定性 可行性7 n+1 n n(n+3)/2 n

7、(n+1)/281+（1+2+（1+2+3）+（1+2+n）=n(n+1)(n+2)/6 O(n3)9. (n+3)(n-2)/2 10. O(n)四，應(yīng)用題1什么是數(shù)據(jù)? 它與信息是什么關(guān)系?2什么是數(shù)據(jù)結(jié)構(gòu)? 數(shù)據(jù)結(jié)構(gòu)是研究什么內(nèi)容的學(xué)科？有關(guān)數(shù)據(jù)結(jié)構(gòu)的討論涉及哪三方面?3評價一個好的算法，從哪幾方面考慮？4. 若將數(shù)據(jù)結(jié)構(gòu)定義為一個二元組（D，R）,說明符號D，R 應(yīng)分別表示什么？5解釋算法與程序的區(qū)別？6有下列幾種用二元組表示的數(shù)據(jù)結(jié)構(gòu)，畫出它們分別對應(yīng)的邏輯圖形表示，并指出它們分別屬于何種結(jié)構(gòu)。（1）A=（K，R），其中：K=a，b，c，d，e，f，gR=rr=a，b，b，c，c，d

8、，d，e，e，f，f，g（2）B=（K，R），其中：K=a，b，c，d，e，f，g，hR=rr=d，b，d，g，d，a，b，c，g，e，g，h，a，f（3）C=（K，R），其中：K=1，2，3，4，5，6R=rr=(1, 2)，(2, 3)，（2，4），（3，4），（3，5），（3，6），（4，5），（4,6）這里的圓括號對表示兩結(jié)點是雙向的。7分析以下程序段的時間復(fù)雜度。（1）a=0；b=1；for（i=2；i=n；i+）s=a+b；b=a；a=S；（2）inti，j，k；for（i=0；in；i+for（j=0；jn；j+cij=0；for（k=0；kn；k+cij=cij+aik+bkj

9、；8求下列算法段的語句頻度及時間復(fù)雜度（1）for(i=1; i<=n; i+)for(j =1; j <=i ; j+)x=x+1;（2）for （i=1;i<=n;i+）for (j=1;j<=i;j+)for ( k=1;k<=j;k+)x=i+j-k;四，應(yīng)用題1什么是信息？廣義地講，信息就是消息。宇宙三要素（物質(zhì)、能量、信息）之一。它是現(xiàn)實世界各種事物在人們頭腦中的反映。此外，人們通過科學(xué)儀器能夠認(rèn)識到的也是信息。信息的特征為：可識別、可存儲、可變換、可處理、可傳遞、可再生、可壓縮、可利用、可共享。什么是數(shù)據(jù)？因為信息的表現(xiàn)形式十分廣泛，許多信息在計算機

10、中不方便存儲和處理，例如，一個大樓中4部電梯在軟件控制下調(diào)度和運行的狀態(tài)、一個商店中商品的在庫明細表等，必須將它們轉(zhuǎn)換成數(shù)據(jù)才能很方便地在計算機中存儲、處理、變換。因此，數(shù)據(jù)(data)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計算機中并被計算機程序識別和處理的符號的集合。在計算機中，信息必須以數(shù)據(jù)的形式出現(xiàn)。2數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)以及相互之間的關(guān)系。記為：數(shù)據(jù)結(jié)構(gòu) = D, R 。其中，D是某一數(shù)據(jù)對象，R是該對象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。數(shù)據(jù)結(jié)構(gòu)是一門研究在非數(shù)值計算的程序設(shè)計問題中，計算機的操作對象及對象間的關(guān)系和施加于對象的操作等的學(xué)科。有關(guān)數(shù)據(jù)結(jié)構(gòu)的討論一般涉及以

11、下三方面的內(nèi)容：（1）數(shù)據(jù)成員以及它們相互之間的邏輯關(guān)系，也稱為數(shù)據(jù)的邏輯結(jié)構(gòu)，簡稱為數(shù)據(jù)結(jié)構(gòu)；（2）數(shù)據(jù)成員及其關(guān)系在計算機存儲器內(nèi)的存儲表示，也稱為數(shù)據(jù)的物理結(jié)構(gòu)，簡稱為存儲結(jié)構(gòu)；（3）施加于該數(shù)據(jù)結(jié)構(gòu)上的操作。數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲不是一碼事，是與計算機存儲無關(guān)的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題中抽象出來的數(shù)據(jù)模型，是數(shù)據(jù)的應(yīng)用視圖。數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯數(shù)據(jù)結(jié)構(gòu)在計算機存儲器中的實現(xiàn)（亦稱為映像），它是依賴于計算機的，是數(shù)據(jù)的物理視圖。數(shù)據(jù)的操作是定義于數(shù)據(jù)邏輯結(jié)構(gòu)上的一組運算，每種數(shù)據(jù)結(jié)構(gòu)都有一個運算的集合。例如搜索、插入、刪除、更新、排序等。3

12、評價好的算法有四個方面。一是算法的正確性；二是算法的易讀性；三是算法的健壯性；四是算法的時空效率（運行）。4D是數(shù)據(jù)元素的有限集合，S是D上數(shù)據(jù)元素之間關(guān)系的有限集合。5 算法是為了解決某類問題而規(guī)定的一個有限長的操作序列。一個算法必須滿足以下五個重要特性： 有窮性 確定性 可行性 有輸入 有輸出 算法與程序的聯(lián)系和區(qū)別：（1）算法代表了對問題的解，而程序則是算法在計算機上的特定的實現(xiàn)。一個程序不一定滿足有窮性。例如，操作系統(tǒng)，只要整個系統(tǒng)不遭破壞，它將永遠不會停止。因此，操作系統(tǒng)不是一個算法。（2）程序中的指令必須是機器可執(zhí)行的，而算法中的指令則無此限制。（3）算法是面向功能的，通常用面向過

13、程的方式描述；程序可以用面向?qū)ο蠓绞酱罱ㄋ目蚣?。?）算法與數(shù)據(jù)結(jié)構(gòu)是相輔相承的：解決某一特定類型問題的算法可以選定不同的數(shù)據(jù)結(jié)構(gòu)，而且選擇恰當(dāng)與否直接影響算法的效率。反之，一種數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣由各種算法的執(zhí)行來體現(xiàn)。6 （1）A對應(yīng)邏輯圖形如下，它是一種線性結(jié)構(gòu)。（2）B對應(yīng)邏輯圖形如下，它是一種樹形結(jié)構(gòu)。（3）C對應(yīng)邏輯圖形如下，它是一種圖形結(jié)構(gòu)。7 （1）解：語句的頻度是2；語句的頻度是n；語句的頻度是n-1；語句的頻度是n-1；語句的頻度是n-1；故，該程序段的時間復(fù)雜度T（n）=2+n+3*（n-1）=4n-1=O（n）。（2）解：語句的循環(huán)控制變量i要增加到n，測試到i=n成立才會

14、終止，故它的頻度為n+1；語句作為語句循環(huán)體內(nèi)的語句應(yīng)該執(zhí)行n次，但語句本身要執(zhí)行n+1次，故語句的頻度是n（n+1）；同理可得語句、和的頻度分別是n2，n2（n+1）和n3。該程序段所有語句的頻度之和為：T（n）=2n3+3n2+2n+1其復(fù)雜度為O（n3）。8（1）分析：該算法為一個二重循環(huán)，執(zhí)行次數(shù)為內(nèi)、外循環(huán)次數(shù)相乘，但內(nèi)循環(huán)次數(shù)不固定，與外循環(huán)有關(guān)，因此，時間頻度T(n)=1+2+3+n=n*(n+1)/2。有 1/4T(n)/n21，故它的時間復(fù)雜度為(n2), 即(n)與n2 數(shù)量級相同。 （2）分析算法規(guī)律可知時間頻度T(n)=1+(1+2)+(1+2+3)+.+(1+2+3+

15、n)。由于有1/6 T（n)/ n3 1，故時間復(fù)雜度為(n3) 第二章 線性表一，選擇1在一個以 h 為頭的單循環(huán)鏈中，p 指針指向鏈尾的條件是（ ） A. p->next=h B. p->next=NIL C. p->next->next=h D. p->data=-12下面關(guān)于線性表的敘述中，錯誤的是哪一個？（ ）A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B線性表采用順序存儲，便于進行插入和刪除操作。C線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D線性表采用鏈接存儲，便于插入和刪除操作。3線性表是具有n個（ ）的有限序列（n>0）。 A表元

16、素 B字符 C數(shù)據(jù)元素 D數(shù)據(jù)項 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é)點時不可能修改（ ）。A 頭

17、指針 B頭結(jié)點指針域 C 開始結(jié)點指針域 D其它結(jié)點指針域8 雙向鏈表中有兩個指針域，llink和rlink，分別指向前驅(qū)及后繼，設(shè)p指向鏈表中的一個結(jié)點，q指向一待插入結(jié)點，現(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=

18、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;9對于一個頭指針為head的帶頭結(jié)點的單鏈表，判定該表為空表的條件是（ ）。Ahead=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL10在順序表中查找第i個元素的時間效率最高的算法時間復(fù)雜度是（ ）。AO(1) BO() CO(log2n) DO(n) 11最好的情況下，在

19、順序表中按值查找一個元素的算法時間復(fù)雜度是（ ）。AO(n) BO() CO(log2n) DO(1) 12. 若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復(fù)雜度為（ ）(1<=i<=n+1)。A. O(0) B. O(1) C. O(n) D. O(n2) 13. 對于順序存儲的線性表，訪問結(jié)點和增加、刪除結(jié)點的時間復(fù)雜度為（ ）。AO(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)14線性表（ a1,a2,an）以鏈接方式存儲時，訪問第i位置元素的時間復(fù)雜性為（ ）。AO（i） BO（1） CO（n）

20、 DO（i-1）15非空的循環(huán)單鏈表head的尾結(jié)點p滿足（ ）。Ap->link=head Bp->link=NIL Cp=NIL Dp= head一，選擇1.A2.B3.C4.A5.D6.D7.A8.D9.B10.A11D12.C13.C14.C15.A二，判斷1. 鏈表中的頭結(jié)點僅起到標(biāo)識的作用。( ) 2線性表采用鏈表存儲時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。( )3順序存儲方式插入和刪除時效率太低，因此它不如鏈?zhǔn)酱鎯Ψ绞胶谩? )4順序存儲方式只能用于存儲線性結(jié)構(gòu)。( )5線性表的鏈接存儲，表中元素的邏輯順序與物理順序一定相同。6. 線性表的特點是每個元素都有一個前

21、驅(qū)和一個后繼。( )7. 取線性表的第i個元素的時間同i的大小有關(guān)。 ( )8. 循環(huán)鏈表不是線性表。 ( ) 9. 線性表就是順序存儲的表。( )10. 順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。( )二，判斷1. ×2. 3.×4. ×5. ×6.×7.×8.×9. ×10.×三，填空1當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應(yīng)采用_存儲結(jié)構(gòu)。2線性表L=（a1,a2,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平

22、均需要移動元素的個數(shù)是_。3在一個長度為n的順序表中第i個元素（1<=i<=n）之前插入一個元素時，需向后移動_個元素。4對于一個具有n個結(jié)點的單鏈表，在已知的結(jié)點*p后插入一個新結(jié)點的時間復(fù)雜度為_,在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為_。5 在雙向循環(huán)鏈表中,向p所指的結(jié)點之后插入指針f所指的結(jié)點，其操作是_、_、_、_。6. 在雙向鏈表結(jié)構(gòu)中，若要求在p 指針?biāo)傅慕Y(jié)點之前插入指針為s 所指的結(jié)點，則需執(zhí)行下列語句：s->next=p； s->prior= _；p->prior=s；_=s；7.順序存儲結(jié)構(gòu)通過_表示元素之間的關(guān)系;鏈?zhǔn)酱鎯Y(jié)構(gòu)通

23、過_表示元素之間的關(guān)系。8. 對于雙向鏈表,在兩個結(jié)點之間插入一個新結(jié)點需修改的指針共 _個，單鏈表為_個。9. 已知指針p指向單鏈表L中的某結(jié)點，則刪除其后繼結(jié)點的語句是：_,時間復(fù)雜度是 。10. 帶頭結(jié)點的雙循環(huán)鏈表L中只有一個元素結(jié)點的條件是： 。三，填空1順序 2（n-1）/2 3 n-i+14O(1)，O(n) 5f->next=p->next; f->prior=p; p->next->prior=f; p->next=f;6p->prior s->prior->next7物理上相鄰 指針 84 29u=p->next;

24、 p->next=u->next; free(u); O(1) ; 10L->next->next=L 四，算法設(shè)計1試寫一算法在帶頭結(jié)點的單鏈表結(jié)構(gòu)上實現(xiàn)線性表操作LOCATE（L，X）。2試寫一算法在帶頭結(jié)點的單鏈表結(jié)構(gòu)上實現(xiàn)線性表操作LENGTH（L）。3試寫一算法實現(xiàn)順序表的就地逆置，即利用原表的存儲空間將線性表（a1, a2, ,an）逆置為（an, an-1, ,a1）。4 試寫一算法，對單鏈表實現(xiàn)就地逆置。5 設(shè)線性表A =（a1， a2， ,an），B=（b1, b2, ,bn），試寫一個按下列規(guī)則合并A，B為線性表C的算法，即使得C=（a1, b1,

25、, am ,bm ,bm+1, ,bn） 當(dāng)m<=n時；或者 C=（a1, b1, , an ,bn ,an+1, ,an） 當(dāng)m.>n時；線性表A，B和C均以單鏈表作存儲結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點空間構(gòu)成。注意：單鏈表的長度值m和n均未顯式存儲。1LNode* Locate(LinkList L,int x)/鏈表上的元素查找,返回指針for(p=l->next;p&&p->data!=x;p=p->next);return p;/Locate 2int Length(LinkList L)/求鏈表的長度for(k=0,p=L;p->

26、;next;p=p->next,k+);return k;/Length3void reverse(SqList &A)/順序表的就地逆置for(i=0,j=A.length-1;i<j;i+,j-)A.elemi<->A.elemj;/reverse 4void LinkList_reverse(Linklist &L)/鏈表的就地逆置;為簡化算法,假設(shè)表長大于2p=L->next;q=p->next;s=q->next;p->next=NULL;while(s->next)q->next=p;p=q;q=s;s=s

27、->next; /把L的元素逐個插入新表表頭q->next=p;s->next=q;L->next=s;/LinkList_reverse分析:本算法的思想是,逐個地把L的當(dāng)前元素q插入新的鏈表頭部,p為新表表頭.5void merge1(LinkList &A,LinkList &B,LinkList &C)/把鏈表A和B合并為C,A和B的元素間隔排列,且使用原存儲空間p=A->next;q=B->next;C=A;while(p&&q)s=p->next;p->next=q; /將B的元素插入if(s)

28、t=q->next;q->next=s; /如A非空,將A的元素插入p=s;q=t;/while/merge1第三章 棧和隊列一，選擇1. 對于棧操作數(shù)據(jù)的原則是（ ）。A. 先進先出 B. 后進先出 C. 后進后出 D. 不分順序3. 最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是 （ ）。 A. (rear+1) MOD n=front B. rear=front Crear+1=front D. (rear-l) MOD n=front4當(dāng)利用大小為n的數(shù)組順序存儲一個棧時，假定用top= =n表示?？?，則向這個棧插入一個元素時首先應(yīng)執(zhí)行 語句修

29、改top指針。Atop+ Btop- Ctop=0 Dtop5. 若已知一個棧的入棧序列是1,2,3,n，其輸出序列為p1,p2,p3，pN,若pN是n，則pi是( )。 A. i B. n-i C. n-i+1 D. 不確定6. 一個遞歸算法必須包括（ ）。A. 遞歸部分 B. 終止條件和遞歸部分 C. 迭代部分 D.終止條件和迭代部分7. 執(zhí)行完下列語句段后，i值為：（ ） int f(int x) return (x>0) ? x* f(x-1):2); int i ; i =f(f(1);A2 B. 4 C. 8 D. 無限遞歸8. 設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1，e2，

30、e3，e4,e5和e6依次通過棧S，一個元素出棧后即進隊列Q，若6個元素出隊的序列是e2，e4，e3,e6,e5,e1則棧S的容量至少應(yīng)該是( )。A 6 B. 4 C. 3 D. 29. 棧和隊列的共同點是（ ）。A. 都是先進先出 B. 都是先進后出 C. 只允許在端點處插入和刪除元素 D. 沒有共同點10. 設(shè)計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用（ ）數(shù)據(jù)結(jié)構(gòu)最佳。A線性表的順序存儲結(jié)構(gòu) B. 隊列 C. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) D. 棧11. 用不帶頭結(jié)點的單鏈表存儲隊列時,其隊頭指針指向隊頭結(jié)點,其隊尾指針指向隊尾結(jié)點，則在進行刪除操作時( )。A僅修改隊頭指針 B.

31、僅修改隊尾指針 C. 隊頭、隊尾指針都要修改 D. 隊頭,隊尾指針都可能要修改12. 遞歸過程或函數(shù)調(diào)用時，處理參數(shù)及返回地址，要用一種稱為（ ）的數(shù)據(jù)結(jié)構(gòu)。A隊列 B多維數(shù)組 C棧 D. 線性表13. 假設(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)%m14. 循環(huán)隊列存儲在數(shù)組A0.m中，則入隊時的操作為（ ）。A. rear=rear+1 B. rear=(rear+1) mod (m-1)C. rear=(

32、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的值分別為多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 一，選擇1.B3.B4 B5.D6.B7.B8.C9.C10.D11.D12.C13.A14.D15.B二，填空1_是限定僅在表尾進行插入或刪除操作的線性表。3中綴表達式3*（x+2）-5所對應(yīng)的后綴表達式為 ；后綴表達式“45*32+-”的值為 。4. 順序棧用data1.n存儲數(shù)據(jù)，

33、棧頂指針是top,則值為x的元素入棧的操作是_。5向一個循環(huán)隊列中插入一元素時，需首先移動 ，然后再向所指位置 新插入的元素。 6用下標(biāo)0開始的N元數(shù)組實現(xiàn)循環(huán)隊列時，為實現(xiàn)下標(biāo)變量M加1后在數(shù)組有效下標(biāo)范圍內(nèi)循環(huán)，可采用的表達式是： M= _7用長度為n的數(shù)組順序存儲一個棧時，若用top= =n表示?？?，則表示棧滿的條件為 。二，填空1棧 33 x 2 + * 5 - 154data+top=x； 5 隊尾指針 寫入6(M+1) MOD N (M+1)% N； 7top=0三，應(yīng)用題1指出下列程序段的功能(1) void Demo1(SeqStack *S)int i; arr64 ; n=

34、0 ;while ( StackEmpty(S) arrn+=Pop(S);for (i=0, i< n; i+) Push(S, arri); /Demo1(2) SeqStack S1, S2, tmp;DataType x;./假設(shè)棧tmp和S2已做過初始化while ( ! StackEmpty (&S1)x=Pop(&S1) ;Push(&tmp,x);while ( ! StackEmpty (&tmp) )x=Pop( &tmp); Push( &S1,x);Push( &S2, x);(1)程序段的功能是將

35、一棧中的元素按反序重新排列，也就是原來在棧頂?shù)脑胤诺綏５?，棧底的元素放到棧頂。此棧中元素個數(shù)限制在64個以內(nèi)。(2)程序段的功能是利用tmp棧將一個非空棧s1的所有元素按原樣復(fù)制到一個棧s2當(dāng)中去。四，算法設(shè)計題1 回文是指正讀反讀均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。試寫一個算法判定給定的字符向量是否為回文。(提示：將一半字符入棧) 1 根據(jù)提示，算法可設(shè)計為：/以下為順序棧的存儲結(jié)構(gòu)定義#define StackSize 100 /假定預(yù)分配的棧空間最多為100個元素type

36、def char DataType;/假定棧元素的數(shù)據(jù)類型為字符typedef structDataType dataStackSize;int top;SeqStack;int IsHuiwen( char *t)/判斷t字符向量是否為回文，若是，返回1，否則返回0SeqStack s;int i , len;char temp;InitStack( &s);len=strlen(t); /求向量長度for ( i=0; i<len/2; i+)/將一半字符入棧Push( &s, ti);while( !EmptyStack( &s)/ 每彈出一個字符與相應(yīng)字符

37、比較temp=Pop (&s);if( temp!=Si)  return 0 ;/ 不等則返回0else i+;return 1 ; / 比較完畢均相等則返回 1第四章 串一，選擇1下面關(guān)于串的的敘述中，哪一個是不正確的？（ ）A串是字符的有限序列 B空串是由空格構(gòu)成的串C模式匹配是串的一種重要運算 D串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?設(shè)有兩個串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（ ）A求子串 B聯(lián)接 C匹配 D求串長3串的長度是指（ ）A串中所含不同字母的個數(shù) B串中所含字符的個數(shù)C串中所含不同字符的個數(shù) D串中所含非空格字符的個數(shù)4若串

38、S=software,其子串的數(shù)目是（ ）。A8 B37 C36 D9一，選擇 1.B2.C3B4.B二，填空1空格串是指_，其長度等于_。 2組成串的數(shù)據(jù)元素只能是_。 3一個字符串中_稱為該串的子串 。 4INDEX（DATASTRUCTURE， STR）=_。7設(shè)T和P是兩個給定的串，在T中尋找等于P的子串的過程稱為_，又稱P為_。二，填空1由空格字符（ASCII值32）所組成的字符串 空格個數(shù) 2字符3任意個連續(xù)的字符組成的子序列 45 7模式匹配 模式串 第五章 數(shù)組和廣義表一，選擇1. 已知廣義表L=（x,y,z），a，（u，t，w），從L表中取出原子項t的運算是（ ）。A. he

39、ad（tail（tail（L） B. tail（head（head（tail（L） C. head（tail（head（tail（L） D. head（tail(head（tail（tail（L）)）2. 廣義表A=(a,b,(c,d),(e,(f,g),則下面式子的值為（ ）。Head(Tail(Head(Tail(Tail(A)A. (g) B. (d) C. c D. d3.稀疏矩陣一般的壓縮存儲方法有兩種,即（）A 二維數(shù)組和三維數(shù)組 B三元組和散列C三元組和十字鏈表 D散列和十字鏈表4. 二維數(shù)組A的每個元素是由6個字符組成的串，其行下標(biāo)i=0,1,8,列下標(biāo)j=1,2,10。若A按

40、行先存儲，元素A8,5的起始地址與當(dāng)A按列先存儲時的元素（ ）的起始地址相同。設(shè)每個字符占一個字節(jié)。A. A8,5 B. A3,10 C. A5,8 D. A0,95. 對稀疏矩陣進行壓縮存儲目的是（ ）。A便于進行矩陣運算 B便于輸入和輸出 C節(jié)省存儲空間 D降低運算的時間復(fù)雜度6. 設(shè)A是n*n的對稱矩陣，將A的對角線及對角線上方的元素以列為主的次序存放在一維數(shù)組B1.n(n+1)/2中，對上述任一元素aij(1i，jn，且ij)在B中的位置為( )。A. i(i-l)/2+j B. j(j-l)/2+i C. j(j-l)/2+i-1 D. i(i-l)/2+j-17. AN，N是對稱矩

41、陣，將下面三角（包括對角線）以行序存儲到一維數(shù)組TN（N+1）/2中，則對任一上三角元素aij對應(yīng)Tk的下標(biāo)k是（ ）。A i（i-1）/2+j B j（j-1）/2+i C i（j-i）/2+1 D j（i-1）/2+18. 設(shè)廣義表L=（a,b,c），則L的長度和深度分別為（ ）。 A. 1和1 B. 1和3 C. 1和2 D. 2和3 9. 數(shù)組A0.4,-1.-3,5.7中含有元素的個數(shù)（ ）。A 55 B45 C 36 D1610. 下面說法不正確的是( )。 A. 廣義表的表頭總是一個廣義表 B. 廣義表的表尾總是一個廣義表C. 廣義表難以用順序存儲結(jié)構(gòu) D. 廣義表可以是一個多層

42、次的結(jié)構(gòu)一，選擇 1.D2.D3.C4.B5.C6.B7.B8.C9.B10.A二，判斷1 一個稀疏矩陣Am*n采用三元組形式表示， 若把三元組中有關(guān)行下標(biāo)與列下標(biāo)的值互換，并把m和n的值互換，則就完成了Am*n的轉(zhuǎn)置運算。（ ）2. 從邏輯結(jié)構(gòu)上看，n維數(shù)組的每個元素均屬于n個向量。（ ）3. 稀疏矩陣壓縮存儲后，必會失去隨機存取功能。（ ）4. 對長度為無窮大的廣義表，由于存儲空間的限制，不能在計算機中實現(xiàn)。（ ）5. 數(shù)組可看成線性結(jié)構(gòu)的一種推廣，因此與線性表一樣可對它進行插入，刪除操作。（ ） 6. 所謂取廣義表的表尾就是返回廣義表中最后一個元素。（ ）7. 二維以上的數(shù)組其實是一種特

43、殊的廣義表。（ ） 8. 廣義表的取表尾運算，其結(jié)果通常是個表，但有時也可是個單元素值。（ ）9. 若一個廣義表的表頭為空表，則此廣義表亦為空表。（ ）10. 廣義表中的元素或者是一個不可分割的原子，或者是一個非空的廣義表。（ ）二，判斷1.×2.3.4. 5.×6. ×7.8.×9.×10.×四應(yīng)用題1. 畫出下列廣義表的兩種存儲結(jié)構(gòu)圖(),A,(B,(C,D),(E,F)。2. 設(shè)某表H如下：ABCXa1a2 b1 c1c2其中A,B,C為子表名，a1,a2,b1,c1,c2,x為其元素。試用廣義表形式表示H,并寫出運算HEAD(

44、H)和TAIL(H) 函數(shù)從H中取出單元素a2的運算；（1）H(A(a1,a2）,B(b1）,C(c1，c2）,x）HEAD(TAIL(HEAD(H)=a2五，算法設(shè)計1 設(shè)任意n個整數(shù)存放于數(shù)組A(1:n)中，試編寫程序，將所有正數(shù)排在所有負數(shù)前面 2. 設(shè)二維數(shù)組a1.m, 1.n 含有m*n 個整數(shù)。判斷a中所有元素是否互不相同?輸出相關(guān)信息(yes/no)。1.本題屬于排序問題，只是排出正負，不排出大小?？稍跀?shù)組首尾設(shè)兩個指針i和j，i自小至大搜索到負數(shù)停止，j自大至小搜索到正數(shù)停止。然后i和j所指數(shù)據(jù)交換，繼續(xù)以上過程，直到 i=j為止。void Arrange(int A,int

45、n) /n個整數(shù)存于數(shù)組A中，本算法將數(shù)組中所有正數(shù)排在所有負數(shù)的前面 int i=0,j=n-1,x; /用類C編寫，數(shù)組下標(biāo)從0開始 while(i<j)while(i<j && Ai>0) i+;while(i<j && Aj<0) j-; if(i<j) x=Ai; Ai+=Aj; Aj-=x; /交換Ai 與Aj /算法Arrange結(jié)束.算法討論對數(shù)組中元素各比較一次，比較次數(shù)為n。最佳情況(已排好,正數(shù)在前,負數(shù)在后)不發(fā)生交換，最差情況(負數(shù)均在正數(shù)前面)發(fā)生n/2次交換。用類c編寫，數(shù)組界偶是0.n-1。空間

46、復(fù)雜度為O(1).2.判斷二維數(shù)組中元素是否互不相同，只有逐個比較,找到一對相等的元素，就可結(jié)論為不是互不相同。如何達到每個元素同其它元素比較一次且只一次？在當(dāng)前行，每個元素要同本行后面的元素比較一次（下面第一個循環(huán)控制變量p的for循環(huán)），然后同第i+1行及以后各行元素比較一次，這就是循環(huán)控制變量k和p的二層for循環(huán)。int JudgEqual(ing amn,int m,n) /判斷二維數(shù)組中所有元素是否互不相同，如是，返回1；否則，返回0。for(i=0;i<m;i+) for(j=0;j<n-1;j+) for(p=j+1;p<n;p+) /和同行其它元素比較 if

47、(aij=aip) printf(“no”); return(0); /只要有一個相同的，就結(jié)論不是互不相同 for(k=i+1;k<m;k+) /和第i+1行及以后元素比較 for(p=0;p<n;p+) if(aij=akp) printf(“no”); return(0); / for(j=0;j<n-1;j+)printf(yes”); return(1); /元素互不相同/算法JudgEqual結(jié)束第6章 樹和二叉樹一選擇1算術(shù)表達式a+b*（c+d/e）轉(zhuǎn)為后綴表達式后為（ ）Aab+cde/* Babcde/+*+ Cabcde/*+ Dabcde*/+2. 在下述結(jié)論中，正確的是（ ）只有一個結(jié)點的二叉樹的度為0; 二叉樹的度為2； 二叉樹的左右子樹可任意交換;深度為K的完全二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。