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

1、第一章 緒 論一，選擇題1組成數(shù)據(jù)的基本單位是（）A數(shù)據(jù)項(xiàng)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算法分析的兩個(gè)主要方面是（ ）A正確性和簡單性 B可讀性和文檔性C數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 D時(shí)間復(fù)雜度和空間復(fù)雜度4算法分析的目的是（）。A 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B研究算法中的輸入和輸出的關(guān)系C分析算法的效率以求改進(jìn)D分析算法的易懂性和文檔性5. 算法的時(shí)間復(fù)雜度取決于（ ）A問題的規(guī)模 B. 待處理數(shù)據(jù)的初態(tài) C. A和B 以上都不是6一個(gè)算法應(yīng)該是（ ）。 A程序 B

2、問題求解步驟的描述 C要滿足五個(gè)基本特性 DA和C. 7. 下面關(guān)于算法說法錯誤的是（ ）A算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)B.為解決某問題的算法同為該問題編寫的程序含義是相同的C. 算法的可行性是指指令不能有二義性 D. 以上幾個(gè)都是錯誤的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è)計(jì)時(shí)，存儲單元的地址（ ）。A一定連續(xù) B一定不連續(xù) C不一定連續(xù) D部分連續(xù)，部分不連續(xù)二，判斷題1數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實(shí)現(xiàn)有關(guān)。( ) 2數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)對象與對象中數(shù)據(jù)元素之間關(guān)系的集合。3在順序存儲結(jié)構(gòu)中，有時(shí)也存儲數(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ù)項(xiàng)的個(gè)數(shù)都相等。7數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。8算法的優(yōu)

4、劣與算法描述語言無關(guān)，但與所用計(jì)算機(jī)有關(guān)。( )9健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。( )10算法可以用不同的語言描述，如果用C 語言或PASCAL語言等高級語言來描述，則算法實(shí)際上就是程序了。( ) 一，選擇題1C2C3D4C5C6B7D8C9D10A二，判斷題1. ×2. 3. ×4. 5.×6. ×7. 8.×9. 10.×三，填空1數(shù)據(jù)的物理結(jié)構(gòu)包括 的表示和 的表示。2. 對于給定的n個(gè)元素,可以構(gòu)造出的邏輯結(jié)構(gòu)有 ， ， ，_ _四種。3一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中 稱為存儲結(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一個(gè)算法有5個(gè)特性: 、 、 ，有零個(gè)或多個(gè)輸入、有一個(gè)或多個(gè)輸出。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. 計(jì)算機(jī)執(zhí)行下面的語句時(shí)，語句s的執(zhí)行次數(shù)為 _ 。 for(i=l；i<n-l；i+) for(j=n;j>=i;j-) s; 10. 下面程序段的時(shí)間復(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邏輯特性 在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(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評價(jià)一個(gè)好的算法，從哪幾方面考慮？4. 若將數(shù)據(jù)結(jié)構(gòu)定義為一個(gè)二元組（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é)點(diǎn)是雙向的。7分析以下程序段的時(shí)間復(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求下列算法段的語句頻度及時(shí)間復(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)實(shí)世界各種事物在人們頭腦中的反映。此外，人們通過科學(xué)儀器能夠認(rèn)識到的也是信息。信息的特征為：可識別、可存儲、可變換、可處理、可傳遞、可再生、可壓縮、可利用、可共享。什么是數(shù)據(jù)？因?yàn)樾畔⒌谋憩F(xiàn)形式十分廣泛，許多信息在計(jì)算機(jī)

10、中不方便存儲和處理，例如，一個(gè)大樓中4部電梯在軟件控制下調(diào)度和運(yùn)行的狀態(tài)、一個(gè)商店中商品的在庫明細(xì)表等，必須將它們轉(zhuǎn)換成數(shù)據(jù)才能很方便地在計(jì)算機(jī)中存儲、處理、變換。因此，數(shù)據(jù)(data)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序識別和處理的符號的集合。在計(jì)算機(jī)中，信息必須以數(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ù)值計(jì)算的程序設(shè)計(jì)問題中，計(jì)算機(jī)的操作對象及對象間的關(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)系在計(jì)算機(jī)存儲器內(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ù)的存儲不是一碼事，是與計(jì)算機(jī)存儲無關(guān)的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題中抽象出來的數(shù)據(jù)模型，是數(shù)據(jù)的應(yīng)用視圖。數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存儲器中的實(shí)現(xiàn)（亦稱為映像），它是依賴于計(jì)算機(jī)的，是數(shù)據(jù)的物理視圖。數(shù)據(jù)的操作是定義于數(shù)據(jù)邏輯結(jié)構(gòu)上的一組運(yùn)算，每種數(shù)據(jù)結(jié)構(gòu)都有一個(gè)運(yùn)算的集合。例如搜索、插入、刪除、更新、排序等。3

12、評價(jià)好的算法有四個(gè)方面。一是算法的正確性；二是算法的易讀性；三是算法的健壯性；四是算法的時(shí)空效率（運(yùn)行）。4D是數(shù)據(jù)元素的有限集合，S是D上數(shù)據(jù)元素之間關(guān)系的有限集合。5 算法是為了解決某類問題而規(guī)定的一個(gè)有限長的操作序列。一個(gè)算法必須滿足以下五個(gè)重要特性： 有窮性 確定性 可行性 有輸入 有輸出 算法與程序的聯(lián)系和區(qū)別：（1）算法代表了對問題的解，而程序則是算法在計(jì)算機(jī)上的特定的實(shí)現(xiàn)。一個(gè)程序不一定滿足有窮性。例如，操作系統(tǒng)，只要整個(gè)系統(tǒng)不遭破壞，它將永遠(yuǎn)不會停止。因此，操作系統(tǒng)不是一個(gè)算法。（2）程序中的指令必須是機(jī)器可執(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；故，該程序段的時(shí)間復(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）分析：該算法為一個(gè)二重循環(huán)，執(zhí)行次數(shù)為內(nèi)、外循環(huán)次數(shù)相乘，但內(nèi)循環(huán)次數(shù)不固定，與外循環(huán)有關(guān)，因此，時(shí)間頻度T(n)=1+2+3+n=n*(n+1)/2。有 1/4T(n)/n21，故它的時(shí)間復(fù)雜度為(n2), 即(n)與n2 數(shù)量級相同。 （2）分析算法規(guī)律可知時(shí)間頻度T(n)=1+(1+2)+(1+2+3)+.+(1+2+3+

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

16、素 B字符 C數(shù)據(jù)元素 D數(shù)據(jù)項(xiàng) 4若某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（ ）存儲方式最節(jié)省時(shí)間。A順序表 B雙鏈表 C帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D單循環(huán)鏈表5某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（ ）存儲方式最節(jié)省運(yùn)算時(shí)間。A單鏈表 B僅有頭指針的單循環(huán)鏈表 C雙鏈表 D僅有尾指針的單循環(huán)鏈表6設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用( )最節(jié)省時(shí)間。A. 單鏈表 B.單循環(huán)鏈表 C. 帶尾指針的單循環(huán)鏈表 D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表7在帶有頭結(jié)點(diǎn)的單鏈中插入一個(gè)新結(jié)點(diǎn)時(shí)不可能修改（ ）。A 頭

17、指針 B頭結(jié)點(diǎn)指針域 C 開始結(jié)點(diǎn)指針域 D其它結(jié)點(diǎn)指針域8 雙向鏈表中有兩個(gè)指針域，llink和rlink，分別指向前驅(qū)及后繼，設(shè)p指向鏈表中的一個(gè)結(jié)點(diǎn)，q指向一待插入結(jié)點(diǎn)，現(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對于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是（ ）。Ahead=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL10在順序表中查找第i個(gè)元素的時(shí)間效率最高的算法時(shí)間復(fù)雜度是（ ）。AO(1) BO() CO(log2n) DO(n) 11最好的情況下，在

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

20、 DO（i-1）15非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)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é)點(diǎn)僅起到標(biāo)識的作用。( ) 2線性表采用鏈表存儲時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲空間可以是不連續(xù)的。( )3順序存儲方式插入和刪除時(shí)效率太低，因此它不如鏈?zhǔn)酱鎯Ψ绞胶谩? )4順序存儲方式只能用于存儲線性結(jié)構(gòu)。( )5線性表的鏈接存儲，表中元素的邏輯順序與物理順序一定相同。6. 線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前

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

22、均需要移動元素的個(gè)數(shù)是_。3在一個(gè)長度為n的順序表中第i個(gè)元素（1<=i<=n）之前插入一個(gè)元素時(shí)，需向后移動_個(gè)元素。4對于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)*p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_,在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_。5 在雙向循環(huán)鏈表中,向p所指的結(jié)點(diǎn)之后插入指針f所指的結(jié)點(diǎn)，其操作是_、_、_、_。6. 在雙向鏈表結(jié)構(gòu)中，若要求在p 指針?biāo)傅慕Y(jié)點(diǎn)之前插入指針為s 所指的結(jié)點(diǎn)，則需執(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. 對于雙向鏈表,在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)需修改的指針共 _個(gè)，單鏈表為_個(gè)。9. 已知指針p指向單鏈表L中的某結(jié)點(diǎn)，則刪除其后繼結(jié)點(diǎn)的語句是：_,時(shí)間復(fù)雜度是 。10. 帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L中只有一個(gè)元素結(jié)點(diǎn)的條件是： 。三，填空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è)計(jì)1試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作LOCATE（L，X）。2試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作LENGTH（L）。3試寫一算法實(shí)現(xiàn)順序表的就地逆置，即利用原表的存儲空間將線性表（a1, a2, ,an）逆置為（an, an-1, ,a1）。4 試寫一算法，對單鏈表實(shí)現(xiàn)就地逆置。5 設(shè)線性表A =（a1， a2， ,an），B=（b1, b2, ,bn），試寫一個(gè)按下列規(guī)則合并A，B為線性表C的算法，即使得C=（a1, b1,

25、, am ,bm ,bm+1, ,bn） 當(dāng)m<=n時(shí)；或者 C=（a1, b1, , an ,bn ,an+1, ,an） 當(dāng)m.>n時(shí)；線性表A，B和C均以單鏈表作存儲結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點(diǎn)空間構(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的元素逐個(gè)插入新表表頭q->next=p;s->next=q;L->next=s;/LinkList_reverse分析:本算法的思想是,逐個(gè)地把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第三章 棧和隊(duì)列一，選擇1. 對于棧操作數(shù)據(jù)的原則是（ ）。A. 先進(jìn)先出 B. 后進(jìn)先出 C. 后進(jìn)后出 D. 不分順序3. 最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則隊(duì)空的條件是 （ ）。 A. (rear+1) MOD n=front B. rear=front Crear+1=front D. (rear-l) MOD n=front4當(dāng)利用大小為n的數(shù)組順序存儲一個(gè)棧時(shí)，假定用top= =n表示?？?，則向這個(gè)棧插入一個(gè)元素時(shí)首先應(yīng)執(zhí)行 語句修

29、改top指針。Atop+ Btop- Ctop=0 Dtop5. 若已知一個(gè)棧的入棧序列是1,2,3,n，其輸出序列為p1,p2,p3，pN,若pN是n，則pi是( )。 A. i B. n-i C. n-i+1 D. 不確定6. 一個(gè)遞歸算法必須包括（ ）。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和隊(duì)列Q的初始狀態(tài)為空，元素e1，e2，

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

31、僅修改隊(duì)尾指針 C. 隊(duì)頭、隊(duì)尾指針都要修改 D. 隊(duì)頭,隊(duì)尾指針都可能要修改12. 遞歸過程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為（ ）的數(shù)據(jù)結(jié)構(gòu)。A隊(duì)列 B多維數(shù)組 C棧 D. 線性表13. 假設(shè)以數(shù)組Am存放循環(huán)隊(duì)列的元素,其頭尾指針分別為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（ ）。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m14. 循環(huán)隊(duì)列存儲在數(shù)組A0.m中，則入隊(duì)時(shí)的操作為（ ）。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. 若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，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_是限定僅在表尾進(jìn)行插入或刪除操作的線性表。3中綴表達(dá)式3*（x+2）-5所對應(yīng)的后綴表達(dá)式為 ；后綴表達(dá)式“45*32+-”的值為 。4. 順序棧用data1.n存儲數(shù)據(jù)，

33、棧頂指針是top,則值為x的元素入棧的操作是_。5向一個(gè)循環(huán)隊(duì)列中插入一元素時(shí)，需首先移動 ，然后再向所指位置 新插入的元素。 6用下標(biāo)0開始的N元數(shù)組實(shí)現(xiàn)循環(huán)隊(duì)列時(shí)，為實(shí)現(xiàn)下標(biāo)變量M加1后在數(shù)組有效下標(biāo)范圍內(nèi)循環(huán)，可采用的表達(dá)式是： M= _7用長度為n的數(shù)組順序存儲一個(gè)棧時(shí)，若用top= =n表示棧空，則表示棧滿的條件為 。二，填空1棧 33 x 2 + * 5 - 154data+top=x； 5 隊(duì)尾指針 寫入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ù)脑胤诺綏５?，棧底的元素放到棧頂。此棧中元素個(gè)數(shù)限制在64個(gè)以內(nèi)。(2)程序段的功能是利用tmp棧將一個(gè)非空棧s1的所有元素按原樣復(fù)制到一個(gè)棧s2當(dāng)中去。四，算法設(shè)計(jì)題1 回文是指正讀反讀均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。試寫一個(gè)算法判定給定的字符向量是否為回文。(提示：將一半字符入棧) 1 根據(jù)提示，算法可設(shè)計(jì)為：/以下為順序棧的存儲結(jié)構(gòu)定義#define StackSize 100 /假定預(yù)分配的?？臻g最多為100個(gè)元素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)/ 每彈出一個(gè)字符與相應(yīng)字符

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

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

40、行先存儲，元素A8,5的起始地址與當(dāng)A按列先存儲時(shí)的元素（ ）的起始地址相同。設(shè)每個(gè)字符占一個(gè)字節(jié)。A. A8,5 B. A3,10 C. A5,8 D. A0,95. 對稀疏矩陣進(jìn)行壓縮存儲目的是（ ）。A便于進(jìn)行矩陣運(yùn)算 B便于輸入和輸出 C節(jié)省存儲空間 D降低運(yùn)算的時(shí)間復(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中含有元素的個(gè)數(shù)（ ）。A 55 B45 C 36 D1610. 下面說法不正確的是( )。 A. 廣義表的表頭總是一個(gè)廣義表 B. 廣義表的表尾總是一個(gè)廣義表C. 廣義表難以用順序存儲結(jié)構(gòu) D. 廣義表可以是一個(gè)多層

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

43、殊的廣義表。（ ） 8. 廣義表的取表尾運(yùn)算，其結(jié)果通常是個(gè)表，但有時(shí)也可是個(gè)單元素值。（ ）9. 若一個(gè)廣義表的表頭為空表，則此廣義表亦為空表。（ ）10. 廣義表中的元素或者是一個(gè)不可分割的原子，或者是一個(gè)非空的廣義表。（ ）二，判斷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,并寫出運(yùn)算HEAD(

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

45、n) /n個(gè)整數(shù)存于數(shù)組A中，本算法將數(shù)組中所有正數(shù)排在所有負(fù)數(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ù)在前,負(fù)數(shù)在后)不發(fā)生交換，最差情況(負(fù)數(shù)均在正數(shù)前面)發(fā)生n/2次交換。用類c編寫，數(shù)組界偶是0.n-1?？臻g

46、復(fù)雜度為O(1).2.判斷二維數(shù)組中元素是否互不相同，只有逐個(gè)比較,找到一對相等的元素，就可結(jié)論為不是互不相同。如何達(dá)到每個(gè)元素同其它元素比較一次且只一次？在當(dāng)前行，每個(gè)元素要同本行后面的元素比較一次（下面第一個(gè)循環(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); /只要有一個(gè)相同的，就結(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ù)表達(dá)式a+b*（c+d/e）轉(zhuǎn)為后綴表達(dá)式后為（ ）Aab+cde/* Babcde/+*+ Cabcde/*+ Dabcde*/+2. 在下述結(jié)論中，正確的是（ ）只有一個(gè)結(jié)點(diǎn)的二叉樹的度為0; 二叉樹的度為2； 二叉樹的左右子樹可任意交換;深度為K的完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹。