1、第 1 章 緒論一、選擇題1.算法的計算量的大小稱為計算的（）。【北京郵電大學2000 二、 3(20/8分）】A 效 率B. 復雜性C.現實性D. 難度2.算法的時間復雜度取決于（ ）【中科院計算所1998 二、 1（ 2 分）】A問題的規模B.待處理數據的初態C. A 和 B3. 計算機算法指的是（ 1），它必須具備（ 2） 這三個特性。（1）A 計算方法 B. 排序方法 C. 解決問題的步驟序 列 D. 調度方法（2）A 可執行性、可移植性、可擴充性 B. 可執行性、確定性、有窮性 C. 確定性、有窮性、穩定性 D. 易讀性、穩定性、安全 性4【南京理工大學 一個算法應該是（ A程序性5

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

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

4、通科技大學 1996B順序結構、鏈式結構D.10以下那一個術語與數據的存儲結構無關？（ 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 為正整數，則最后一行的語

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

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

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

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

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

10、只要它的_數學特性 _不變，都不影響其外部使用。【山東大學 2001 三、 3（2分）】6數據結構中 評價算法 的兩個重要指標是 算法的時間復雜度和空間復雜 度 【北京理工大學 2001 七、 1（ 2 分）】7. 數據結構是研討數據的 _邏輯結構 _和_物理結構 _，以及它們之間的相互關系， 并對與這 種結構定義相應的 _操作（運算） _，設計出相應的 _算法。【西安電子科技大學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 執行的頻度為 n+1 ；語句 2 執行的頻度為 n ；語句 3 執行的頻度 為 n(n+3)/2 ；語句 4 執行的頻度為 n(n+1)/2 。【北方交通大學 1999 二、 4( 5 分)】10在下面的程序段中，對的賦值語句的頻度為_1+(1+2+(1+2+3)+( 1+2+ +n)=n(n+1)(n+2)/6_(表示為 n 的函數)FOR i ： TO n DOFOR j ： TO i D

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

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

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

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

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

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

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

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

21、析下面程序段中循環語句的執行次數。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 位二進制數加 1，假如無溢出，該算法的最壞時間復雜性是什么？并分 析它的平均時間復雜性。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 的功能和時間復雜性PROCEDURE A (h,g:pointer);(h,g 分別為單循環鏈表( single linkedcircular list )中兩個結點指針 )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. 調用下列 C 函數 f(n) 或 PASACAL函數 f(n) 回答下列問題 :( 1) 試指出 f(n) 值的大小，并寫出 f(n) 值的推導過程 ;(2) 假定 n= 5，試指出 f(5) 值的大小和執行 f(5) 時的輸出結果 。C 函數： 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設 n

24、 是偶數，試計算運行下列程序段后m的值并給出該程序段的時間復雜度。m:=0;FORi:=1TO n DOFORj:=2*i TO nDOm:=m+1;【南京郵電大學 2000 一、 1】 25有下列運行時間函數：2 3 2（1）T1 （n）=1000;（2）T2（n）=n 2+1000n;（ 3）T3（n）=3n 3+100n2+n+1;分別寫出相應的大 O表示的運算時間。【吉林工業大學 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. 斐波那契數列 Fn 定義如下 F0=0，Fl =1， Fn=Fn-1 +Fn-2 ,n=2,3.請就此斐波那契數列，回答下列問題。（1）（7 分） 在遞歸計算 Fn的時候，需要對較小的 Fn-1 ，Fn-2 ， , Fl, F0精確計算多少次 ?（2）（5 分） 如果用大 O表示法，試給出遞歸計算Fn時遞歸函數的時間復雜度錄多少 ?【清華大學 2000 二（12 分）】 28將下列函數，按它們在 n時的無窮大階數，從小到大排序。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數據元素數據元素間關系2集合線性結構 樹形結構 圖狀結構或網狀結構。3數據的組織形式，即數據元素之間邏輯關系的總體。而邏輯關系是指數據元素之間 的關聯方式或稱“鄰接

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

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

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

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

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

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

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

35、tudent100;14. 見上面題 4（ 3）。15應從兩方面進行討論：如通訊錄較少變動（如城市私人電話號碼），主要用于查 詢，以順序存儲較方便， 既能順序查找也可隨機查找；若通訊錄經常有增刪操作， 用鏈式存 儲結構較為合適，將每個人的情況作為一個元素（即一個結點存放一個人） ，設姓名作關鍵 字，鏈表安排成有序表，這樣可提高查詢速度。16線性表中的插入、刪除操作，在順序存儲方式下平均移動近一半的元素，時間復 雜度為 O（n）；而在鏈式存儲方式下，插入和刪除時間復雜度都是O（ 1）。17對算法 A1和 A2的時間復雜度 T1和T2取對數，得 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;/ 存入累加數；float interest;/ 利息float total;/ 帳面總數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) 語 句執行 n 次。( 2)是 FOR循環語句，在滿足 (1) 的條件下執行，該語句進入循環體 (3)n 次， 加上最后一次判斷出界，故執行了 n+1 次。 (4) 也是循環語句，當 k=1 時判斷 n+1 次(進入 循環體 (5)n 次)，k=2 時判斷 n 次，最后一