數(shù)據(jù)結構考試題庫(含參考答案)

1、.第1章緒論一、選擇題1.算法的計算量的大小稱為計算的（）?！颈本┼]電大學2000二、 3（20/8分）】A效率B.復雜性C.現(xiàn)實性D.難度2.算法的時間復雜度取決于（）【中科院計算所1998二、 1（ 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)定性、安全性【南京理工大學1999一、 1（ 2 分） 【武漢交通科技大學1996一、1（4 分）】4

2、一個算法應該是（）?！局猩酱髮W1998二、 1（ 2 分）】A程序B問題求解步驟的描述C要滿足五個基本特性DA 和 C.5.下面關于算法說法錯誤的是（）【南京理工大學2000一、 1（ 1.5 分）】A算法最終必須由計算機程序實現(xiàn)B. 為解決某問題的算法同為該問題編寫的程序含義是相同的C. 算法的可行性是指指令不能有二義性D. 以上幾個都是錯誤的6. 下面說法錯誤的是（）【南京理工大學2000一、 2（ 1.5分）】(1 ）算法原地工作的含義是指不需要任何額外的輔助空間（ 2）在相同的規(guī)模n 下，復雜度 O(n) 的算法在時間上總是優(yōu)于復雜度nO(2 ) 的算法（ 3）所謂時間復雜度是指最壞情

3、況下，估算算法執(zhí)行時間的一個上界（ 4）同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低A (1)B.(1),(2)C.(1),(4)D.(3)7從邏輯上可以把數(shù)據(jù)結構分為（）兩大類。 【武漢交通科技大學1996 一 、4（ 2 分）】A動態(tài)結構、靜態(tài)結構B順序結構、鏈式結構C線性結構、非線性結構D初等結構、構造型結構8以下與數(shù)據(jù)的存儲結構無關的術語是（）?！颈狈浇煌ù髮W2000二、 1（2分）】A循環(huán)隊列B.鏈 表C.哈 希表D.棧9以下數(shù)據(jù)結構中，哪一個是線性結構（）？【北方交通大學2001一、 1（2分）】A廣義表B.二 叉 樹C.稀 疏 矩陣D.串;.10以下那一個術語與數(shù)據(jù)的存儲結構無

4、關？（）【北方交通大學2001一、 2（2 分）】A 棧B.哈希表C.線索樹D.雙向鏈表11在下面的程序段中， 對 x 的賦值語句的頻度為 （）【北京工商大學2001一、10（ 3 分）】FOR i:=1TOnDOFOR j:=1TOnDOx:=x+1;A O(2n)B O(n)C O(n2)D O(logn2 )12程序段FORi:=n-1DOWNTO1DOFOR j:=1 TO i DOIF Aj>Aj+1THENAj與 Aj+1對換；其中 n 為正整數(shù)，則最后一行的語句頻度在最壞情況下是（）A. O （ n）B. O(nlogn)C. O(n 3)D. O(n 2)【南京理工大學

5、1998 一、 1(2 分 ) 】13以下哪個數(shù)據(jù)結構不是多型數(shù)據(jù)類型（）【中山大學1999一、 3（ 1 分）】A棧B廣義表C有向圖D字符串14以下數(shù)據(jù)結構中，（）是非線性數(shù)據(jù)結構【中山大學1999一、 4】A樹B字符串C隊D棧15.下列數(shù)據(jù)中， （）是非線性數(shù)據(jù)結構。 【北京理工大學2001六、1（ 2 分）】A 棧B.隊 列C.完全二叉樹D.堆16連續(xù)存儲設計時，存儲單元的地址（）。【中山大學1999一、 1（ 1 分）】A一定連續(xù)B一定不連續(xù)C不一定連續(xù)D部分連續(xù)，部分不連續(xù)17以下屬于邏輯結構的是（）?！疚靼搽娮涌萍即髮W應用2001 一、 1】A順序表B.哈 希 表C.有序表D.單鏈

6、表二、判斷題1. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。 ()【北京郵電大學1998一、 1（ 2 分）】【青島大學2000一、 1（1 分）】【上海交通大學1998一、 1】【山東師范大學2001一、 1（2 分）】2.記錄是數(shù)據(jù)處理的最小單位。()【上海海運學院1998一、 5（ 1 分）】3.數(shù)據(jù)的邏輯結構是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關系；() 【北京郵電大學2002一、 1（ 1 分）】4算法的優(yōu)劣與算法描述語言無關，但與所用計算機有關。()【大連海事大學2001一、 10（ 1 分）】5健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。()【大連海事大學2001一、 11（ 1 分）】;.6算

7、法可以用不同的語言描述，如果用C語言或PASCAL語言等高級語言來描述，則算法實際上就是程序了。() 【西安交通大學1996 二、 7（ 3 分）】7程序一定是算法。() 【燕山大學1998二、 2（ 2 分）并改錯】8 數(shù)據(jù)的物理結構是指數(shù)據(jù)在計算機內的實際存儲形式。() 【山東師范大學2001一、 2（ 2 分）】9.數(shù)據(jù)結構的抽象操作的定義與具體實現(xiàn)有關。() 【華南理工大學2002一、 1（1分）】10.在順序存儲結構中，有時也存儲數(shù)據(jù)結構中元素之間的關系。()【華南理工大學2002 一、 2（1分）】11.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。()【上海海運學院19

8、99 一、 1（1 分）】12.數(shù)據(jù)結構的基本操作的設置的最重要的準則是，實現(xiàn)應用程序與存儲結構的獨立。()【華南理工大學2002 一、 5（1 分）】13.數(shù)據(jù)的邏輯結構說明數(shù)據(jù)元素之間的順序關系, 它依賴于計算機的儲存結構. ()【上海海運學院1998 一、 1（1 分）】三、填空1數(shù)據(jù)的物理結構包括數(shù)據(jù)元素的表示和數(shù)據(jù)元素關系的表示?！狙嗌酱髮W1998一、 1（ 2 分）】2.對 于 給 定 的 n 個 元 素 , 可 以 構 造 出 的 邏 輯 結 構 有集 合，線 性 結構，樹形結構， _圖狀結構或網(wǎng)狀結構_四種?！局锌圃河嬎闼?999 二、 1（4 分）】3數(shù)據(jù)的邏輯結構是指數(shù)據(jù)的

9、組織形式，即數(shù)據(jù)元素之間邏輯關系的總體。而邏輯關系是指數(shù)據(jù)元素之間的關聯(lián)方式或稱“鄰接關系”?！颈本┼]電大學 2001 二、 1（2 分）】4一個數(shù)據(jù)結構在計算機中的表示（或稱映像）稱為存儲結構（又數(shù)據(jù)的物理結構）?！救A中理工大學2000一、 1（ 1 分）】5抽象數(shù)據(jù)類型的定義僅取決于它的一組_邏輯特性 _，而與 _在計算機內部如何表示和實現(xiàn)_無關，即不論其內部結構如何變化，只要它的_數(shù)學特性 _不變，都不影響其外部使用。【山東大學2001三、 3（2 分）】6數(shù)據(jù)結構中評價算法的兩個重要指標是算法的時間復雜度和空間復雜度【北京理工大學2001七、 1（2 分）】7. 數(shù)據(jù)結構是研討數(shù)據(jù)的

10、_邏輯結構 _和_物理結構 _，以及它們之間的相互關系， 并對與這種結構定義相應的 _操作（運算） _，設計出相應的 _算法?！疚靼搽娮涌萍即髮W1998 二、2（3 分）】8 一個算法具有5 個特性 :有窮性、確定性、可行性，有零個或多個輸入、有一個或多個輸出。【華中理工大學2000一、 2（5 分）】【燕山大學1998一、 2（ 5 分）】9已知如下程序段FOR i:= nDOWNTO1DO 語句 1BEGINx:=x+1 ； 語句 2FOR j:=nDOWNTOiDO 語句 3y:=y+1;語句 4END；;.語句 1執(zhí)行的頻度為n+1；語句2執(zhí)行的頻度為n；語句3執(zhí)行的頻度為n(n+3)

11、/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ù)）FORi ：TOnDOFORj ：TOi DOFOR k： 1TOjDO： delta；【北京工業(yè)大學1999一、 6（ 2 分）】11. 下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是：log 2 n【合肥工業(yè)大學1999 三、1（ 2 分）i ： =1； WHILE i<n DOi ： =i*2;12.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級

12、是(nlog 2n) 。【合肥工業(yè)大學2000三、 1（ 2 分）】i:=1;WHILE i<n BEGINFOR j:=1 TO n DOx:=x+1;i:=i*2END；13.下面程序段中帶有下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是(log 2n2)【合肥工業(yè)大學2001三、 1（ 2 分）】i ： =n*nWHILE i<>1DOi:=i div 2;14.計算機執(zhí)行下面的語句時，語句s 的執(zhí)行次數(shù)為_(n+3)(n-2)/2 _?！灸暇├砉ご髮W2000 二、 1（ 1.5分）】FOR(i=l ； i<n-l； i+)FOR(j=n;j>=i;j-)s;15. 下面

13、程序段的時間復雜度為 _O（ n） _。 (n>1) sum=1；for (i=0;sum<n;i+) sum+=1;【南京理工大學2001二、 1（ 2分）】16設 m.n 均為自然數(shù)， m可表示為一些不超過 n 的自然數(shù)之和， f(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);

14、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)賽中，總共將進行_n(n-1)/2_場比賽?！竞戏使I(yè)大學 1999 三、 8（ 2 分）】四、應用題1.數(shù)據(jù)結構是一門研究什么內容的學科？【燕山大學1999二、 1（ 4 分）】2. 數(shù)據(jù)元素之間的關系在計算機中有幾種表示方法？各有什么特點？【燕山大學1999二、 2（ 4 分）】3.數(shù)據(jù)類型和抽象數(shù)據(jù)類型是如何定義的。二者有何相同和不同之處，抽象數(shù)據(jù)類型的主要特點是什么？使用抽象數(shù)據(jù)

15、類型的主要好處是什么？【北京郵電大學1994 一（ 8 分）】4.回答問題（每題 2 分）【山東工業(yè)大學1997 一 （ 8 分）】（ 1）在數(shù)據(jù)結構課程中，數(shù)據(jù)的邏輯結構，數(shù)據(jù)的存儲結構及數(shù)據(jù)的運算之間存在著怎樣的關系？（ 2）若邏輯結構相同但存儲結構不同，則為不同的數(shù)據(jù)結構。這樣的說法對嗎？舉例說明之。（ 3）在給定的邏輯結構及其存儲表示上可以定義不同的運算集合，從而得到不同的數(shù)據(jù)結構 。這樣說法對嗎？舉例說明之。（ 4）評價各種不同數(shù)據(jù)結構的標準是什么？5評價一個好的算法，您是從哪幾方面來考慮的？【大連海事大學1996二、 3（ 2 分）】【中山大學1998三、 1（5 分）】6解釋和比

16、較以下各組概念【華南師范大學2000一（ 10 分）】（ 1）抽象數(shù)據(jù)類型及數(shù)據(jù)類型（ 2）數(shù)據(jù)結構、邏輯結構、存儲結構（ 3）抽象數(shù)據(jù)類型【哈爾濱工業(yè)大學2000一、 1（3 分）】（ 4）算法的時間復雜性【河海大學1998一、 2（ 3 分）】（ 5）算法【吉林工業(yè)大學1999一、 1（2 分）】（ 6）頻度【吉林工業(yè)大學1999一、 2（2 分）】7. 根據(jù)數(shù)據(jù)元素之間的邏輯關系，一般有哪幾類基本的數(shù)據(jù)結構？【北京科技大學1998一、 1】【同濟大學1998】8對于一個數(shù)據(jù)結構，一般包括哪三個方面的討論？【北京科技大學1999一、1（ 2 分）】9. 當你為解決某一問題而選擇數(shù)據(jù)結構時，

17、應從哪些方面考慮？【西安電子北京科技大學 2000】10. 若將數(shù)據(jù)結構定義為一個二元組（D， R）, 說明符號 D， R 應分別表示什么？【北京科技大學2001 一、 1（2 分）】11數(shù)據(jù)結構與數(shù)據(jù)類型有什么區(qū)別？【哈爾濱工業(yè)大學2001三、 1（3 分）】12數(shù)據(jù)的存儲結構由哪四種基本的存儲方法實現(xiàn)？【山東科技大學2001一、1（4 分）】13若有 100 個學生，每個學生有學號，姓名，平均成績，采用什么樣的數(shù)據(jù)結構最方便，寫出這些結構？【山東師范大學1996二、 2（2 分）】14. 運算是數(shù)據(jù)結構的一個重要方面。試舉一例，說明兩個數(shù)據(jù)結構的邏輯結構和存儲方式完全相同， 只是對于運算的

18、定義不同。 因而兩個結構具有顯著不同的特性，是兩個不同的結構?！颈本┐髮W1998 一、 1（ 5 分）】15. 在編制管理通訊錄的程序時, 什么樣的數(shù)據(jù)結構合適 ? 為什么 ?【 長沙鐵道學院1998 四、 3(6 分 ) 】;.16. 試舉一例， 說明對相同的邏輯結構 , 同一種運算在不同的存儲方式下實現(xiàn)， 其運算效率不同?！颈本├砉ご髮W2000三、 1（4.5 分）】17.有實現(xiàn)同一功能的兩個算法A1 和 A2，其中 A1 的時間復雜度為Tl=O(2 n) ，A2 的時間復雜度為 T2=O(n2) ，僅就時間復雜度而言，請具體分析這兩個算法哪一個好?！颈本┖娇蘸教齑髮W2000二（ 10 分

19、）】18設計一數(shù)據(jù)結構，用來表示某一銀行儲戶的基本信息：賬號、姓名、開戶年月日、儲蓄類型、存入累加數(shù)、利息、帳面總數(shù)?！菊憬髮W1994一 、 3（ 5 分）】19. 寫出下面算法中帶標號語句的頻度。TYPEar=ARRAY1.n OF datatype;PROCEDUREperm( a: ar; k, n: integer);VARx: datatype;i:integer;BEGIN（ 1） IF k=nTHEN BEGIN（ 2）FORi:=1TOn DO（ 3）write (ai);writeln;ENDELSE BEGIN（ 4）FORi:=kTOnDO（ 5）ai:=ai+i*i;

20、（ 6） perm (a, k+1, n); END;END;設 k 的初值等于1。【北京郵電大學1997 二（ 10 分）】20. 分析下面程序段中循環(huán)語句的執(zhí)行次數(shù)。i:=0;s:=0;n:=100;REPEAT i:=i+1; s:=s+10*i;UNTILNOT(i<n) AND (s<n);【北京郵電大學1998四、 1（5 分）】21下列算法對一 n 位二進制數(shù)加 1，假如無溢出，該算法的最壞時間復雜性是什么？并分析它的平均時間復雜性。TYPEnum=ARRAY 1.n of 0.1；PROCEDUREInc（ VAR a： num）；VARi ： integer；BE

21、GINi ： =n；WHILEAi=1DOBEGINAi： =0；i ： =i-1 ； END；END；Ai：=1；;.END Inc ；【東南大學1998三(8 分 )1994二（ 15 分）】22. 閱讀下列算法，指出算法 A 的功能和時間復雜性PROCEDUREA (h,g:pointer);(h,g分別為單循環(huán)鏈表（single linkedcircular list）中兩個結點指針)PROCEDUREB(s,q:pointer)；VAR p:pointer;BEGINp:=s;WHILE p.next<>q DO p:=p.next;p.next:=s;END;(of B

22、)BEGINB(h,g);B(g,h);END;（ of A ）【東南大學1999二（ 10 分）】23.調用下列C 函數(shù) f(n)或 PASACAL函數(shù) f(n)回答下列問題:（ 1） 試指出 f(n) 值的大小，并寫出f(n)值的推導過程;（ 2） 假定 n= 5 ，試指出f(5)值的大小和執(zhí)行f(5) 時的輸出結果。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)；ret

23、urn (sum);【華中理工大學2000 六（ 10 分）】24設 n 是偶數(shù)，試計算運行下列程序段后m的值并給出該程序段的時間復雜度。m:=0;FORi:=1TOnDOFORj:=2*iTOnDOm:=m+1;【南京郵電大學2000 一、 1】25有下列運行時間函數(shù)：122332（ 1）T (n)=1000;（ 2）T (n)=n+1000n;（ 3）T (n)=3n+100n +n+1;分別寫出相應的大O表示的運算時間。【吉林工業(yè)大學1999二（ 12 分）】26. 試給出下面兩個算法的運算時間。（1）fori 1tondoxx+1END（2）for i1tondo;.forj 1ton

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

25、3/2)n ,n!, n2+logn【中科院計算所1995】第 1 章緒論一、選擇題1.B2.C3.1C3.2B4.B5.D6.C7.C8.D9.D10.A11.C12.D 13.D 14.A 15.C 16.A17.C二、判斷題1.2.3. ×4. ×5.6.7.8.9. ×10. ×11. ×12.××××13.×三填空題1數(shù)據(jù)元素數(shù)據(jù)元素間關系2集合線性結構樹形結構圖狀結構或網(wǎng)狀結構。3數(shù)據(jù)的組織形式，即數(shù)據(jù)元素之間邏輯關系的總體。而邏輯關系是指數(shù)據(jù)元素之間的關聯(lián)方式或稱“鄰接關系”。4表

26、示（又稱映像）。5（ 1）邏輯特性（ 2）在計算機內部如何表示和實現(xiàn)（ 3）數(shù)學特性。6算法的時間復雜度和空間復雜度。7（ 1）邏輯結構（ 2）物理結構（ 3）操作（運算）（ 4）算法。8（ 1）有窮性（2）確定性（ 3）可行性。9（ 1） n+1（ 2）n（ 3） n(n+3)/2（ 4） n(n+1)/2 。101+（ 1+2+（ 1+2+3） +（1+2+n） =n(n+1)(n+2)/6O(n3)11.log 2n12.nlog 2n13.log 2n214.(n+3)(n-2)/215. O(n);.16.(1)1(2)1(3)f(m,n-1)(4)n917. n(n-1)/2四應用

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

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

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

30、據(jù)元素之間的關聯(lián)方式或“鄰接關系”），數(shù)據(jù)的存儲結構是數(shù)據(jù)結構在計算機中的表示，包括數(shù)據(jù)元素的表示及其關系的表示。 數(shù)據(jù)的運算是對數(shù)據(jù)定義的一組操作，運算是定義在邏輯結構上的，和存儲結構無關，而運算的實現(xiàn)則是依賴于存儲結構。（ 2）邏輯結構相同但存儲不同，可以是不同的數(shù)據(jù)結構。例如，線性表的邏輯結構屬于線性結構，采用順序存儲結構為順序表，而采用鏈式存儲結構稱為線性鏈表。（ 3）棧和隊列的邏輯結構相同，其存儲表示也可相同（順序存儲和鏈式存儲），但由于其運算集合不同而成為不同的數(shù)據(jù)結構。（ 4）數(shù)據(jù)結構的評價非常復雜，可以考慮兩個方面，一是所選數(shù)據(jù)結構是否準確、完整的刻劃了問題的基本特征； 二是是

31、否容易實現(xiàn) （如對數(shù)據(jù)分解是否恰當； 邏輯結構的選擇是否適合于運算的功能，是否有利于運算的實現(xiàn)；基本運算的選擇是否恰當。）5評價好的算法有四個方面。一是算法的正確性；二是算法的易讀性；三是算法的健壯性；四是算法的時空效率（運行）。6（ 1）見上面題3（ 2）見上面題4（ 3）見上面題3;.（ 4）算法的時間復雜性是算法輸入規(guī)模的函數(shù)。算法的輸入規(guī)?；騿栴}的規(guī)模是作為該算法輸入的數(shù)據(jù)所含數(shù)據(jù)元素的數(shù)目， 或與此數(shù)目有關的其它參數(shù)。 有時考慮算法在最壞情況下的時間復雜度或平均時間復雜度。（ 5）算法是對特定問題求解步驟的描述，是指令的有限序列，其中每一條指令表示一個或多個操作。算法具有五個重要特性

32、：有窮性、確定性、可行性、輸入和輸出。（ 6）頻度。在分析算法時間復雜度時，有時需要估算基本操作的原操作，它是執(zhí)行次數(shù)最多的一個操作，該操作重復執(zhí)行的次數(shù)稱為頻度。7集合、線性結構、樹形結構、圖形或網(wǎng)狀結構。8邏輯結構、存儲結構、操作（運算）。9通?？紤]算法所需要的存儲空間量和算法所需要的時間量。后者又涉及到四方面：程序運行時所需輸入的數(shù)據(jù)總量， 對源程序進行編譯所需時間， 計算機執(zhí)行每條指令所需時間和程序中指令重復執(zhí)行的次數(shù)。10D 是數(shù)據(jù)元素的有限集合，S 是 D 上數(shù)據(jù)元素之間關系的有限集合。11“數(shù)據(jù)結構”這一術語有兩種含義，一是作為一門課程的名稱；二是作為一個科學的概念。作為科學概念

33、，目前尚無公認定義，一般認為，討論數(shù)據(jù)結構要包括三個方面，一是數(shù)據(jù)的邏輯結構，二是數(shù)據(jù)的存儲結構，三是對數(shù)據(jù)進行的操作（運算）。而數(shù)據(jù)類型是值的集合和操作的集合，可以看作是已實現(xiàn)了的數(shù)據(jù)結構，后者是前者的一種簡化情況。12見上面題 2。13將學號、姓名、平均成績看成一個記錄（元素，含三個數(shù)據(jù)項），將100 個這樣的記錄存于數(shù)組中。因一般無增刪操作，故宜采用順序存儲。typedefstruct intnum;/ 學號charname8;/姓名floatscore;/平均成績node ；node student100;14. 見上面題 4（ 3）。15應從兩方面進行討論：如通訊錄較少變動（如城市私

34、人電話號碼），主要用于查詢，以順序存儲較方便，既能順序查找也可隨機查找；若通訊錄經(jīng)常有增刪操作，用鏈式存儲結構較為合適，將每個人的情況作為一個元素（即一個結點存放一個人），設姓名作關鍵字，鏈表安排成有序表，這樣可提高查詢速度。16線性表中的插入、刪除操作，在順序存儲方式下平均移動近一半的元素，時間復雜度為 O（n）；而在鏈式存儲方式下，插入和刪除時間復雜度都是O（ 1）。17對算法 A1 和 A2 的時間復雜度 T1 和 T2 取對數(shù)，得 nlog 2 和 2log n。顯然，算法 A2 好于 A1。18.structnode intyear,month,day; ;typedef struc

35、t intnum;/ 帳號charname8;/姓名structnode date;/開戶年月日inttag;/儲蓄類型，如：0-零存， 1-一年定期 floatput;/存入累加數(shù)；floatinterest;/利息;.floattotal;/帳面總數(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這是一個遞歸調用，因k 的初值為1，由語句（ 6）知，每次調用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 次，最后一次k=n-1 時判斷