1、第 1 章 緒論一、選擇題1.算法的計算量的大小稱為計算的（）。【北京郵電大學2000 二、 3(20/8分）】A 效 率B. 復(fù)雜性C.現(xiàn)實性D. 難度2.算法的時間復(fù)雜度取決于（ ）【中科院計算所1998 二、 1（ 2 分）】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程序性5

2、.1999 一、 1（ 2 分） 【武漢交通科技大學 ）。【中山大學 1998 二、 B問題求解步驟的描述 DA 和 C.1996 一、1（ 4 分）】1（2 分）】C要滿足五個基本特下面關(guān)于算法說法錯誤的是（ A算法最終必須由計算機程序?qū)崿F(xiàn) B. 為解決某問題的算法同為該問題編寫的程序含義是相同的 C. 算法的可行性是指指令不能有二義性）【南京理工大學2000 一、 1（ 1.5 分）】D. 以上幾個都是錯誤的6. 下面說法錯誤的是（ ）【南京理工大學 2000 一、 2 （ 1.5 分）】（1 ）算法原地工作的含義是指不需要任何額外的輔助空間（2）在相同的規(guī)模 n 下，復(fù)雜度 O（n）的算

3、法在時間上總是優(yōu)于復(fù)雜度 O（2n）的算法（3）所謂時間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界（4）同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低）。【北方交通大學2000二、1（2B. 鏈 表C.哈 希）？【北方交通大學2001一、1（2B. 二 叉 樹C.稀疏矩D初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)A （1）B.（1）,（2）7從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ 4（ 2 分）】A動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)C線性結(jié)構(gòu)、非線性結(jié)構(gòu) 8以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（ 分）】A 循 環(huán) 隊 列 表 D. 棧 9以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)（ 分）】A廣義表C.（1）,（4） D.（3） ）兩大類。 【武漢交

4、通科技大學 1996B順序結(jié)構(gòu)、鏈式結(jié)構(gòu)D.10以下那一個術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)？（ 2 分）】A 棧）【北方交通大學 2001 一、 2B. 哈 希 表C. 線 索樹 D. 雙向鏈表 11在下面的程序段中， 對 x 的賦值語句的頻度為 （ 10（3 分）】）【北京工商大學 2001FOR i:=1 TO nDOFOR j:=1 TOn DOx:=x+1;A O(2n)2B O(n)C O(n2)(logn2)12程序段 FOR i:=n-1DOWNTO 1 DOFOR j:=1 TO i DODOIF Aj>Aj+1THEN Aj 與 Aj+1 對換；其中n 為正整數(shù)，則最后一行的語

5、句頻度在最壞情況下是（）A. O( n)B. O(nlogn)3C. O(n 3)2D. O(n 2)理工大學1998 一、 1(2 分) 】13以下哪個數(shù)據(jù)結(jié)構(gòu)不是多型數(shù)據(jù)類型（）【中山大學A棧B廣義表C有向圖南京1999 一、3（1 分）】D字符串14以下數(shù)據(jù)結(jié)構(gòu)中，（A樹）是非線性數(shù)據(jù)結(jié)構(gòu)【中山大學B字符串C隊1999 一、 4】D棧15. 下列數(shù)據(jù)中， （A 棧樹 D. 堆）是非線性數(shù)據(jù)結(jié)構(gòu)。 【北京理工大學B. 隊 列16連續(xù)存儲設(shè)計時，存儲單元的地址（A一定連續(xù)B一定不連續(xù)17以下屬于邏輯結(jié)構(gòu)的是（A 順 序 表 表 D. 單鏈表1.、判斷題數(shù)據(jù)元素是數(shù)據(jù)的最小單位。【北京郵電大學

6、 1998【上海交通大學 1998記錄是數(shù)據(jù)處理的最小單位。2001 六、1（ 2 分）】C. 完 全 二 叉）。【中山大學 1999 一、1（1 分）】 C不一定連續(xù)D部分連續(xù)，部分不連續(xù)。【西安電子科技大學應(yīng)用2001 一、 1】B. 哈 希 表 C. 有 序（、1（2 分）】【青島大學 2000 山東師范大學 2001 ） 【上海海運學院 （、1】（2.3.20024算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計算機有關(guān)。數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關(guān)系；、1（1 分）】（ 1 分）】2 分）】1998 一、5（1 分）】） 【北京郵電大學一、1、1【大連海事大學 2001 一、

7、 10（ 1 分）】 5健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。大連海事大學 2001 一、 11（ 1 分）】6算法可以用不同的語言描述，如果用C 語言或 PASCAL語言等高級語言來描述，則算法實際上就是程序了。 （ ） 【西安交通大學 1996 二、 7（3分）】 7程序一定是算法。 （） 【燕山大學 1998 二、2（2 分）并改錯】8 數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。 （ ） 【山東師范大學2001 一、2（2 分）】1 分）】9. 數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實現(xiàn)有關(guān)。 （ ） 【華南理工大學 2002 一、 1（10. 在順序存儲結(jié)構(gòu)中，有時也存儲數(shù)

8、據(jù)結(jié)構(gòu)中元素之間的關(guān)系。 （ ） 【華南理工大學 2002 一、 2 （1 分）】11. 順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。 （ ） 【上海海運學院 1999 一、 1（1 分）】12. 數(shù)據(jù)結(jié)構(gòu)的基本操作的設(shè)置的最重要的準則是，實現(xiàn)應(yīng)用程序與存儲結(jié)構(gòu)的獨立。 （ 【華南理工大學 2002 一、 5（1 分）】13. 數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的順序關(guān)系 , 它依賴于計算機的儲存結(jié)構(gòu) . （）【上海海運學院 1998 一、 1（1 分）】 三、填空1數(shù)據(jù)的物理結(jié)構(gòu)包括數(shù)據(jù)元素 的表示和 數(shù)據(jù)元素關(guān)系 的表示。【燕山大學 1998 一、1（2 分）】2. 對 于 給 定

9、 的 n 個 元 素 , 可 以 構(gòu) 造 出 的 邏 輯 結(jié) 構(gòu) 有集 合， 線 性 結(jié)構(gòu) ， 樹形結(jié)構(gòu)， _圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) _四種。【中科院計算所 1999 二、 1（4 分）】3數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的組織形式，即數(shù)據(jù)元素之間邏輯關(guān)系的總體。而邏輯關(guān)系是指數(shù)據(jù)元素之間的關(guān)聯(lián)方式或稱“鄰接關(guān)系” 。【北京郵電大 學 2001 二、 1（ 2 分）】4一個數(shù)據(jù)結(jié)構(gòu)在計算機中的表示（或稱映像） 稱為存儲結(jié)構(gòu)（又數(shù)據(jù)的物理結(jié)構(gòu)）。【華中理工大學 2000 一、1（1 分）】 5抽象數(shù)據(jù)類型的定義僅取決于它的一組_邏輯特性 _，而與 _在計算機內(nèi)部如何表示和實現(xiàn)_無關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，

10、只要它的_數(shù)學特性 _不變，都不影響其外部使用。【山東大學 2001 三、 3（2分）】6數(shù)據(jù)結(jié)構(gòu)中 評價算法 的兩個重要指標是 算法的時間復(fù)雜度和空間復(fù)雜 度 【北京理工大學 2001 七、 1（ 2 分）】7. 數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的 _邏輯結(jié)構(gòu) _和_物理結(jié)構(gòu) _，以及它們之間的相互關(guān)系， 并對與這 種結(jié)構(gòu)定義相應(yīng)的 _操作（運算） _，設(shè)計出相應(yīng)的 _算法。【西安電子科技大學1998 二、2（3 分）】8 一個算法具有 5 個特性 : 有窮性 、 確定性 、 可行性 ，有零個或多個輸入、 有一個或多個輸出 。燕山大學 1998 一、 2（ 5分）】 語句 1 語句 2 語句 3 語句 4

11、【華中理工大學 2000 一、 2（5 分）】 9已知如下程序段FOR i:= nDOWNTO 1 DOBEGINx:=x+1 ；FOR j:=n DOWNTO i DO y:=y+1;END；語句 1 執(zhí)行的頻度為 n+1 ；語句 2 執(zhí)行的頻度為 n ；語句 3 執(zhí)行的頻度 為 n(n+3)/2 ；語句 4 執(zhí)行的頻度為 n(n+1)/2 。【北方交通大學 1999 二、 4( 5 分)】10在下面的程序段中，對的賦值語句的頻度為_1+(1+2+(1+2+3)+( 1+2+ +n)=n(n+1)(n+2)/6_(表示為 n 的函數(shù))FOR i ： TO n DOFOR j ： TO i D

12、OFOR k： 1 TO j DO： delta ； 【北京工業(yè)大學 1999一、6(2 分)】1(2 分)11. 下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是：log 2n【合肥工業(yè)大學 1999三i ： =1； WHILE i<n DO i ： =i*2;12. 下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是 (nlog 2n) 。【合肥工業(yè)大學 2000 三、 1( 2 分)】i:=1;WHILE i<n BEGINFOR j:=1 TO n DO x:=x+1;i:=i*2END；13. 下面程序段中帶有下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是 (log 2n2) 【合肥工業(yè)大學

13、 2001 三、 1(2 分)】i ：=n*nWHILE i<>1 DO i:=i div 2;14. 計算機執(zhí)行下面的語句時，語句 s 的執(zhí)行次數(shù)為 _(n+3)(n-2)/2 。【南京 理工大學 2000 二、 1( 1.5 分)】FOR(i=l ； i<n-l ； i+)FOR(j=n;j>=i;j-) s;15. 下面程序段的時間復(fù)雜度為 _O( n) 。 (n>1)sum=1；for (i=0;sum<n;i+) sum+=1;【南京理工大學 2001 二、 1( 2分)】16設(shè) m.n 均為自然數(shù)， m可表示為一些不超過 n 的自然數(shù)之和， f(

14、m,n) 為這種表示方式的 數(shù)目。例 f(5,3)=5 ，有 5 種表示方式： 3+2， 3+1+1， 2+2+1，2+1+1+1，1+1+1+1+1。 以下是該函數(shù)的程序段，請將未完成的部分填入，使之完整int f(m,n)int m,n; if(m=1) return1;if(n=1)return1;if(m<n)return f(m,m);if (m=n)return 1+ f(m,n-1) ;return f(m.n-1)+f(m-n,n );執(zhí)行程序， f（6,4）= 9 。 【中科院軟件所 1997 二、1 （9 分）】 17. 在有 n 個選手參加的單循環(huán)賽中，總共將進行_

15、n（n-1）/2 場比賽。【合肥工業(yè)大學 1999 三、 8（ 2 分）】四、應(yīng)用題1. 數(shù)據(jù)結(jié)構(gòu)是一門研究什么內(nèi)容的學科？【燕山大學 1999 二、 1 （4分）】2. 數(shù)據(jù)元素之間的關(guān)系在計算機中有幾種表示方法？各有什么特點？【燕山大學 1999 二、2（4 分）】3. 數(shù)據(jù)類型和抽象數(shù)據(jù)類型是如何定義的。 二者有何相同和不同之處， 抽象數(shù)據(jù)類型的主 要特點是什么？使用抽象數(shù)據(jù)類型的主要好處是什么？【北京郵電大學 1994 一（8 分）】 4. 回答問題（每題 2 分）【山東工業(yè)大學 1997 一 （ 8分）】（ 1）在數(shù)據(jù)結(jié)構(gòu)課程中，數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲結(jié)構(gòu)及數(shù)據(jù)的運算之間存在著

16、怎樣的關(guān)系？（ 2）若邏輯結(jié)構(gòu)相同但存儲結(jié)構(gòu)不同，則為不同的數(shù)據(jù)結(jié)構(gòu)。這樣的說法對嗎？舉例 說明之。（ 3）在給定的邏輯結(jié)構(gòu)及其存儲表示上可以定義不同的運算集合，從而得到不同的數(shù) 據(jù)結(jié)構(gòu) 。這樣說法對嗎？舉例說明之。（ 4）評價各種不同數(shù)據(jù)結(jié)構(gòu)的標準是什么？ 5評價一個好的算法，您是從哪幾方面來考慮的？【大連海事大學 1996 二、3 （2 分）】【中山大學 1998 三、1 （5分）】 6解釋和比較以下各組概念【華南師范大學2000 一（ 10 分）】（ 1）抽象數(shù)據(jù)類型及數(shù)據(jù)類型（ 2）數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)（3）抽象數(shù)據(jù)類型 【哈爾濱工業(yè)大學 2000 一、1（3 分）】（4）算法

17、的時間復(fù)雜性【河海大學 1998 一、2（3 分）】（5）算法【吉林工業(yè)大學 1999一、1（2 分）】（6）頻度【吉林工業(yè)大學1999 一、2（2 分）】7. 根據(jù)數(shù)據(jù)元素之間的邏輯關(guān)系，一般有哪幾類基本的數(shù)據(jù)結(jié)構(gòu)？ 【北京科技大學 1998 一、 1】【同濟大學 1998】8對于一個數(shù)據(jù)結(jié)構(gòu)， 一般包括哪三個方面的討論？ 【北京科技大學 1999 一、1（2 分）】9. 當你為解決某一問題而選擇數(shù)據(jù)結(jié)構(gòu)時，應(yīng)從哪些方面考慮？【西安電子北京科技大 學 2000 】10. 若將數(shù)據(jù)結(jié)構(gòu)定義為一個二元組（ D，R）, 說明符號 D，R 應(yīng)分別表示什么？ 【北京科技大學 2001 一、 1（2 分

18、）】11數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型有什么區(qū)別？【哈爾濱工業(yè)大學2001 三、1（3 分）】12數(shù)據(jù)的存儲結(jié)構(gòu)由哪四種基本的存儲方法實現(xiàn)？【山東科技大學 2001 一、1（4 分）】13若有 100 個學生，每個學生有學號，姓名，平均成績，采用什么樣的數(shù)據(jù)結(jié)構(gòu)最方便， 寫出這些結(jié)構(gòu)？【山東師范大學 1996 二、 2（2 分）】14. 運算是數(shù)據(jù)結(jié)構(gòu)的一個重要方面。試舉一例，說明兩個數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲方 式完全相同， 只是對于運算的定義不同。 因而兩個結(jié)構(gòu)具有顯著不同的特性， 是兩個不同的 結(jié)構(gòu)。【北京大學 1998 一、1（5 分）】15. 在編制管理通訊錄的程序時 , 什么樣的數(shù)據(jù)結(jié)構(gòu)合適 ?

19、 為什么 ?【 長沙鐵道學院 1998 四、 3（6 分） 】16. 試舉一例， 說明對相同的邏輯結(jié)構(gòu) , 同一種運算在不同的存儲方式下實現(xiàn)， 其運算效率 不同。【北京理工大學 2000 三、 1（4.5 分）】17. 有實現(xiàn)同一功能的兩個算法 A1和 A2，其中 A1的時間復(fù)雜度為 Tl=O（2 n） ，A2的時間復(fù) 雜度為 T2=O（n2） ，僅就時間復(fù)雜度而言，請具體分析這兩個算法哪一個好。【北京航空航天大學 2000 二（ 10 分）】18設(shè)計一數(shù)據(jù)結(jié)構(gòu)，用來表示某一銀行儲戶的基本信息：賬號、姓名、開戶年月日、儲蓄類型 、存入累加數(shù)、利息、帳面總數(shù)。【浙江大學 1994 一 、3（5

20、分）】19. 寫出下面算法中帶標號語句的頻度。TYPE ar=ARRAY1.n OF datatype;PROCEDURE perm（ a: ar; k, n: integer）;VAR x: datatype; i:integer;BEGIN（1）IF k=nTHEN BEGIN（2）FOR i:=1 TO n DO（ 3）write （ai）;writeln;ENDELSE BEGIN（ 4） FOR i:=k TO n DO（5）ai:=ai+i*i;（ 6） perm （a, k+1, n）;END;END;設(shè) k 的初值等于 1 。【北京郵電大學 1997 二（ 10分）】20. 分

21、析下面程序段中循環(huán)語句的執(zhí)行次數(shù)。i:=0;s:=0;n:=100;REPEATi:=i+1;s:=s+10*i;UNTIL NOT（i<n） AND （s<n）;【北京郵電大學 1998 四、 1（5 分）】21下列算法對一 n 位二進制數(shù)加 1，假如無溢出，該算法的最壞時間復(fù)雜性是什么？并分 析它的平均時間復(fù)雜性。TYPE num=ARRAY 1.n of 0.1；PROCEDURE Inc （VAR a：num）；VAR i ： integer ；BEGIN i ： =n；WHILE Ai=1 DOBEGIN Ai ： =0；i ：=i-1 ；END；END；Ai ：=1；E

22、ND Inc ；【東南大學 1998 三 (8 分)1994 二( 15 分)】22. 閱讀下列算法，指出算法 A 的功能和時間復(fù)雜性PROCEDURE A (h,g:pointer);(h,g 分別為單循環(huán)鏈表( single linkedcircular list )中兩個結(jié)點指針 )PROCEDURE B(s,q:pointer) ；VAR p:pointer;BEGINp:=s;WHILE p.next<>q DO p:=p.next;p.next:=s;END;(of B)BEGINB(h,g); B(g,h);END;( of A)【東南大學 1999 二(10 分)】

23、23. 調(diào)用下列 C 函數(shù) f(n) 或 PASACAL函數(shù) f(n) 回答下列問題 :( 1) 試指出 f(n) 值的大小，并寫出 f(n) 值的推導過程 ;(2) 假定 n= 5，試指出 f(5) 值的大小和執(zhí)行 f(5) 時的輸出結(jié)果 。C 函數(shù)： int f(intn) int i,j， k,sum= 0;for(i=l; i<n+1;i+)for(j=n;j>i-1; j-) for(k=1;k<j+1;k+ ) sum+;printf("sum=%dn",sum) ；return (sum);【華中理工大學2000 六（ 10 分）】24設(shè) n

24、 是偶數(shù)，試計算運行下列程序段后m的值并給出該程序段的時間復(fù)雜度。m:=0;FORi:=1TO n DOFORj:=2*i TO nDOm:=m+1;【南京郵電大學 2000 一、 1】 25有下列運行時間函數(shù)：2 3 2（1）T1 （n）=1000;（2）T2（n）=n 2+1000n;（ 3）T3（n）=3n 3+100n2+n+1;分別寫出相應(yīng)的大 O表示的運算時間。【吉林工業(yè)大學 1999 二（12 分）】26. 試給出下面兩個算法的運算時間。（1）fori 1to n dox x+1 END（ 2）for i 1 to n doforj 1tox x+1doendend 【中科院自動

25、化研究所 1995 二、2 （6 分）】27. 斐波那契數(shù)列 Fn 定義如下 F0=0，F(xiàn)l =1， Fn=Fn-1 +Fn-2 ,n=2,3.請就此斐波那契數(shù)列，回答下列問題。（1）（7 分） 在遞歸計算 Fn的時候，需要對較小的 Fn-1 ，F(xiàn)n-2 ， , Fl, F0精確計算多少次 ?（2）（5 分） 如果用大 O表示法，試給出遞歸計算Fn時遞歸函數(shù)的時間復(fù)雜度錄多少 ?【清華大學 2000 二（12 分）】 28將下列函數(shù)，按它們在 n時的無窮大階數(shù)，從小到大排序。3 5 n/2 3 1/2 n 2n, n-n +7n , nlogn, 2 , n , logn, n+logn, （

26、3/2） , ,n!, n +logn【中科院計算所 1995 】第 1 章 緒論、選擇題1.B2.C3.1C3.2B4.B5.D6.C7.C8.D9.D10.A11.C12.D13.D14.A15.C16.A17.C、判斷題1. ×2. ×3.×4. ×5. 6. ×7. ×8. 9. ×10.×11.×12. 13. ×三填空題1數(shù)據(jù)元素數(shù)據(jù)元素間關(guān)系2集合線性結(jié)構(gòu) 樹形結(jié)構(gòu) 圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。3數(shù)據(jù)的組織形式，即數(shù)據(jù)元素之間邏輯關(guān)系的總體。而邏輯關(guān)系是指數(shù)據(jù)元素之間 的關(guān)聯(lián)方式或稱“鄰接

27、關(guān)系”。4表示（又稱映像）。5（ 1）邏輯特性（2）在計算機內(nèi)部如何表示和實現(xiàn)（ 3）數(shù)學特性。6算法的時間復(fù)雜度和空間復(fù)雜度。 7（ 1）邏輯結(jié)構(gòu)（ 2）物理結(jié)構(gòu)（ 3）操作（運 算）（ 4）算法。8（ 1）有窮性（2）確定性 （3）可行性。9（ 1）n+1（ 2）n（3）n（n+3）/2（4）n（n+1）/2 。3101+（1+2+（1+2+3）+（1+2+n） =n（n+1）（n+2）/6O（n3）211. log 2n12.nlog 2n13.log 2n14.（n+3）（n-2）/2 15. O（n）16. (1)1 (2)117. n(n-1)/2(3)f(m,n-1)(4)n9四

28、應(yīng)用題1數(shù)據(jù)結(jié)構(gòu)是一門研究在非數(shù)值計算的程序設(shè)計問題中，計算機的操作對象及對象間 的關(guān)系和施加于對象的操作等的學科。2四種表示方法（ 1）順序存儲方式。數(shù)據(jù)元素順序存放，每個存儲結(jié)點只含一個元素。存儲位置反映數(shù) 據(jù)元素間的邏輯關(guān)系。存儲密度大，但有些操作（如插入、刪除）效率較差。（ 2）鏈式存儲方式。 每個存儲結(jié)點除包含數(shù)據(jù)元素信息外還包含一組（至少一個） 指針。指針反映數(shù)據(jù)元素間的邏輯關(guān)系。這種方式不要求存儲空間連續(xù)，便于動態(tài)操作（如插入、 刪除等），但存儲空間開銷大（用于指針），另外不能折半查找等。（ 3）索引存儲方式。 除數(shù)據(jù)元素存儲在一地址連續(xù)的內(nèi)存空間外，尚需建立一個索引表，索引表中

29、索引指示存儲結(jié)點的存儲位置（下標）或存儲區(qū)間端點（下標），兼有靜態(tài)和動態(tài) 特性。（ 4）散列存儲方式。通過散列函數(shù)和解決沖突的方法，將關(guān)鍵字散列在連續(xù)的有限的地 址空間內(nèi)， 并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的存儲地址， 這種存儲方式稱為散列存 儲。其特點是存取速度快，只能按關(guān)鍵字隨機存取，不能順序存取，也不能折半存取。3數(shù)據(jù)類型是程序設(shè)計語言中的一個概念，它是一個值的集合和操作的集合。如 C 語 言中的整型、 實型、 字符型等。 整型值的范圍 （對具體機器都應(yīng)有整數(shù)范圍） ，其操作有加、 減、乘、除、求余等。實際上數(shù)據(jù)類型是廠家提供給用戶的已實現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)。 “抽象數(shù) 據(jù)類型（ ADT）

30、”指一個數(shù)學模型及定義在該模型上的一組操作。“抽象”的意義在于數(shù)據(jù) 類型的數(shù)學抽象特性。 抽象數(shù)據(jù)類型的定義僅取決于它的邏輯特性， 而與其在計算機內(nèi)部如 何表示和實現(xiàn)無關(guān)。 無論其內(nèi)部結(jié)構(gòu)如何變化， 只要它的數(shù)學特性不變就不影響它的外部使 用。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實質(zhì)上是一個概念。此外， 抽象數(shù)據(jù)類型的范圍更廣，它已不再局限于機器已定義和實現(xiàn)的數(shù)據(jù)類型，還包括用戶在設(shè)計軟件系統(tǒng)時自行定義的數(shù)據(jù)類 型。使用抽象數(shù)據(jù)類型定義的軟件模塊含定義、表示和實現(xiàn)三部分，封裝在一起， 對用戶透 明（提供接口），而不必了解實現(xiàn)細節(jié)。抽象數(shù)據(jù)類型的出現(xiàn)使程序設(shè)計不再是“藝術(shù)”， 而是向“科學”邁進了一步。4（

31、1）數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系（即數(shù)據(jù)元素之間的關(guān)聯(lián)方式 或“鄰接關(guān)系”），數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計算機中的表示，包括數(shù)據(jù)元素的表示及 其關(guān)系的表示。 數(shù)據(jù)的運算是對數(shù)據(jù)定義的一組操作， 運算是定義在邏輯結(jié)構(gòu)上的， 和存儲 結(jié)構(gòu)無關(guān)，而運算的實現(xiàn)則是依賴于存儲結(jié)構(gòu)。（2）邏輯結(jié)構(gòu)相同但存儲不同，可以是不同的數(shù)據(jù)結(jié)構(gòu)。例如，線性表的邏輯結(jié)構(gòu)屬 于線性結(jié)構(gòu)，采用順序存儲結(jié)構(gòu)為順序表，而采用鏈式存儲結(jié)構(gòu)稱為線性鏈表。（ 3）棧和隊列的邏輯結(jié)構(gòu)相同，其存儲表示也可相同（順序存儲和鏈式存儲），但由 于其運算集合不同而成為不同的數(shù)據(jù)結(jié)構(gòu)。（4）數(shù)據(jù)結(jié)構(gòu)的評價非常復(fù)雜，可以考慮兩個方面，一

32、是所選數(shù)據(jù)結(jié)構(gòu)是否準確、完 整的刻劃了問題的基本特征； 二是是否容易實現(xiàn) （如對數(shù)據(jù)分解是否恰當； 邏輯結(jié)構(gòu)的選擇 是否適合于運算的功能，是否有利于運算的實現(xiàn)；基本運算的選擇是否恰當。）5評價好的算法有四個方面。一是算法的正確性；二是算法的易讀性；三是算法的健 壯性；四是算法的時空效率（運行）。6（ 1）見上面題 3（ 2）見上面題 4（ 3）見上面題 3（4）算法的時間復(fù)雜性是算法輸入規(guī)模的函數(shù)。算法的輸入規(guī)模或問題的規(guī)模是作為 該算法輸入的數(shù)據(jù)所含數(shù)據(jù)元素的數(shù)目， 或與此數(shù)目有關(guān)的其它參數(shù)。 有時考慮算法在最壞 情況下的時間復(fù)雜度或平均時間復(fù)雜度。（5）算法是對特定問題求解步驟的描述，是指

33、令的有限序列，其中每一條指令表示一 個或多個操作。算法具有五個重要特性：有窮性、確定性、可行性、輸入和輸出。（6）頻度。在分析算法時間復(fù)雜度時，有時需要估算基本操作的原操作，它是執(zhí)行次 數(shù)最多的一個操作，該操作重復(fù)執(zhí)行的次數(shù)稱為頻度。7集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形或網(wǎng)狀結(jié)構(gòu)。8邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、操作（運算）。9通常考慮算法所需要的存儲空間量和算法所需要的時間量。后者又涉及到四方面： 程序運行時所需輸入的數(shù)據(jù)總量， 對源程序進行編譯所需時間， 計算機執(zhí)行每條指令所需時 間和程序中指令重復(fù)執(zhí)行的次數(shù)。10D 是數(shù)據(jù)元素的有限集合， S是 D 上數(shù)據(jù)元素之間關(guān)系的有限集合。11“數(shù)據(jù)結(jié)構(gòu)”這一術(shù)

34、語有兩種含義，一是作為一門課程的名稱；二是作為一個科 學的概念。作為科學概念，目前尚無公認定義，一般認為，討論數(shù)據(jù)結(jié)構(gòu)要包括三個方面， 一是數(shù)據(jù)的邏輯結(jié)構(gòu)，二是數(shù)據(jù)的存儲結(jié)構(gòu)，三是對數(shù)據(jù)進行的操作（運算）。而數(shù)據(jù)類型 是值的集合和操作的集合，可以看作是已實現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)，后者是前者的一種簡化情況。12見上面題 2。13將學號、姓名、平均成績看成一個記錄（元素，含三個數(shù)據(jù)項），將100 個這樣的記錄存于數(shù)組中。因一般無增刪操作，故宜采用順序存儲。typedef struct int num;/ 學號 char name8;/ 姓名 float score;/ 平均成績 node ； node s

35、tudent100;14. 見上面題 4（ 3）。15應(yīng)從兩方面進行討論：如通訊錄較少變動（如城市私人電話號碼），主要用于查 詢，以順序存儲較方便， 既能順序查找也可隨機查找；若通訊錄經(jīng)常有增刪操作， 用鏈式存 儲結(jié)構(gòu)較為合適，將每個人的情況作為一個元素（即一個結(jié)點存放一個人） ，設(shè)姓名作關(guān)鍵 字，鏈表安排成有序表，這樣可提高查詢速度。16線性表中的插入、刪除操作，在順序存儲方式下平均移動近一半的元素，時間復(fù) 雜度為 O（n）；而在鏈式存儲方式下，插入和刪除時間復(fù)雜度都是O（ 1）。17對算法 A1和 A2的時間復(fù)雜度 T1和T2取對數(shù)，得 nlog 2和 2log n。顯然，算法 A2 好于

36、 A1。18. struct nodeint year,month,day; ;typedef structint num;/ 帳號char name8;/ 姓名struct node date;/ 開戶年月日int tag;/ 儲蓄類型，如： 0- 零存， 1- 一年定期float put;/ 存入累加數(shù)；float interest;/ 利息float total;/ 帳面總數(shù)count ；19 (1)n(2)n+1 (3)n (4)(n+4)(n-1)/2 (5)(n+2)(n-1)/2 (6)n-1這是一個遞歸調(diào)用，因 k 的初值為 1，由語句( 6)知，每次調(diào)用 k 增 1，故第 (1) 語 句執(zhí)行 n 次。( 2)是 FOR循環(huán)語句，在滿足 (1) 的條件下執(zhí)行，該語句進入循環(huán)體 (3)n 次， 加上最后一次判斷出界，故執(zhí)行了 n+1 次。 (4) 也是循環(huán)語句，當 k=1 時判斷 n+1 次(進入 循環(huán)體 (5)n 次)，k=2 時判斷 n 次，最后一