數(shù)據(jù)結構第1章

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. 調(diào)度方法(2) A可執(zhí)行性、可移植性、可擴充性 B. 可執(zhí)行性、確定性、有窮性C. 確定性、有窮性、穩(wěn)定性 D. 易讀性、穩(wěn)定性、安全性 (南京理工大學 1999 一、1（2分） (武漢交

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

3、2n)的算法 （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ù)的存儲結構無關的術語是（ ）。(北方交通大學 2000 二、1（2分）)A循環(huán)隊列 B. 鏈表 C. 哈希表 D. 棧9以下數(shù)據(jù)結構中，哪一個是線性結構（ ）？(北方交通大學 2001 一、1（2分）)A廣義表 B

4、. 二叉樹 C. 稀疏矩陣 D. 串10以下那一個術語與數(shù)據(jù)的存儲結構無關？（ ）(北方交通大學 2001 一、2（2分）)A棧 B. 哈希表 C. 線索樹 D. 雙向鏈表11在下面的程序段中，對x的賦值語句的頻度為（ ）(北京工商大學 2001 一、10（3分）)FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1;A O(2n) BO(n) CO(n2) DO(log2n) 12程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF AjAj+1 THEN Aj與Aj+1對換；其中 n為正整數(shù)，則最后一行的語句頻度在最壞情況

5、下是（ ）A. O（n） B. O(nlogn) C. O(n3) D. O(n2) (南京理工大學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ù)，部分

6、不連續(xù)17以下屬于邏輯結構的是（ ）。(西安電子科技大學應用 2001一、1)A順序表 B. 哈希表 C.有序表 D. 單鏈表二、判斷題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)劣與算法描述語言無關，但與所用計算機有關。( )(大連海事大學 200

7、1 一、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ù)的物理結構是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。( )(山東師范大學2001 一、2（2分）)9. 數(shù)據(jù)結構的抽象操作的定義與具體實現(xiàn)有關。( )(華南理工大學 2002 一、1（1分）)10. 在順序存儲結構中，有時也存儲數(shù)據(jù)結構中元素之間的關系。(

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

9、中科院計算所 1999 二、1（4分）)3數(shù)據(jù)的邏輯結構是指 。(北京郵電大學 2001 二、1（2分）)4一個數(shù)據(jù)結構在計算機中 稱為存儲結構。(華中理工大學 2000 一、1（1分）)5抽象數(shù)據(jù)類型的定義僅取決于它的一組_（1）_，而與_（2）_無關，即不論其內(nèi)部結構如何變化，只要它的_（3）_不變，都不影響其外部使用。(山東大學 2001 三、3（2分）)6數(shù)據(jù)結構中評價算法的兩個重要指標是 (北京理工大學 2001 七、1（2分）)7. 數(shù)據(jù)結構是研討數(shù)據(jù)的_（1）_和_（2）_，以及它們之間的相互關系，并對與這種結構定義相應的_（3）_，設計出相應的（4）_。(西安電子科技大學 19

10、98 二、2（3分）)8 一個算法具有5個特性: （1） 、 （2） 、 （3） ，有零個或多個輸入、有一個或多個輸出 。(華中理工大學 2000 一、2（5分）) (燕山大學 1998 一、2（5分）)9已知如下程序段FOR i:= n DOWNTO 1 DO 語句1BEGIN x:=x+1； 語句2FOR j:=n DOWNTO i DO 語句3 y:=y+1; 語句4END；語句1執(zhí)行的頻度為 （1） ；語句2執(zhí)行的頻度為 （2） ；語句3執(zhí)行的頻度為 （3） ；語句4執(zhí)行的頻度為 （4） 。(北方交通大學 1999 二、4（5分）)10在下面的程序段中，對的賦值語句的頻度為_（表示為n

11、的函數(shù)） FORi： TO nDOFORj：TO iDOFORk：1TOjDO：delta；(北京工業(yè)大學 1999 一、6（2分）)11.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是： (合肥工業(yè)大學1999三、1（2分）)i：=1； WHILE in DO i：=i*2;12. 下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是( )。(合肥工業(yè)大學 2000 三、1（2分）)i:=1;WHILE in BEGIN FOR j:=1 TO n DO x:=x+1;i:=i*2 END；13. 下面程序段中帶有下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是( ) (合肥工業(yè)大學 2001 三、1（2分）)i

12、：=n*n WHILE i1 DO i:=i div 2;14. 計算機執(zhí)行下面的語句時，語句s的執(zhí)行次數(shù)為 _ 。(南京理工大學2000二、1（1.5分）) FOR(i=l；i=i;j-) s; 15. 下面程序段的時間復雜度為_。(n1) sum=1； for (i=0;sumn;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ù)的程序段，請將未完成的部分填入，使之完

13、整int f(m,n) int m,n; if(m=1) return (1) ;if(n=1) return (2) ;if(mn) return f(m,m);if (m=n) return 1+ (3) ;return f(m.n-1)+f(m-n, (4) );執(zhí)行程序，f(6,4)= 。 (中科院軟件所 1997 二、1 （9分）)17. 在有n個選手參加的單循環(huán)賽中，總共將進行_場比賽。(合肥工業(yè)大學1999三、8（2分）)四、應用題1. 數(shù)據(jù)結構是一門研究什么內(nèi)容的學科？(燕山大學 1999 二、1 （4分）)2. 數(shù)據(jù)元素之間的關系在計算機中有幾種表示方法？各有什么特點？(燕山

14、大學1999 二、2（4分）)3. 數(shù)據(jù)類型和抽象數(shù)據(jù)類型是如何定義的。二者有何相同和不同之處，抽象數(shù)據(jù)類型的主要特點是什么？使用抽象數(shù)據(jù)類型的主要好處是什么？(北京郵電大學 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評價一個好

15、的算法，您是從哪幾方面來考慮的？(大連海事大學 1996 二、3 （2分）)(中山大學 1998 三、1 （5分）)6解釋和比較以下各組概念(華南師范大學 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對于一個

16、數(shù)據(jù)結構，一般包括哪三個方面的討論？(北京科技大學 1999 一、1（2分）)9. 當你為解決某一問題而選擇數(shù)據(jù)結構時，應從哪些方面考慮？(西安電子北京科技大學 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分）)1

17、4. 運算是數(shù)據(jù)結構的一個重要方面。試舉一例，說明兩個數(shù)據(jù)結構的邏輯結構和存儲方式完全相同，只是對于運算的定義不同。因而兩個結構具有顯著不同的特性，是兩個不同的結構。(北京大學 1998一、1（5分）)15. 在編制管理通訊錄的程序時, 什么樣的數(shù)據(jù)結構合適? 為什么?( 長沙鐵道學院1998四、3(6分)16. 試舉一例，說明對相同的邏輯結構,同一種運算在不同的存儲方式下實現(xiàn)，其運算效率不同。(北京理工大學 2000 三、1（4.5分）)17. 有實現(xiàn)同一功能的兩個算法A1和A2，其中A1的時間復雜度為Tl=O(2n)，A2的時間復雜度為T2=O(n2)，僅就時間復雜度而言，請具體分析這兩個

18、算法哪一個好。(北京航空航天大學 2000 二（10分）)18設計一數(shù)據(jù)結構，用來表示某一銀行儲戶的基本信息： 賬號、姓名、開戶年月日、儲蓄類型 、存入累加數(shù)、利息、帳面總數(shù)。(浙江大學 1994 一 、3（5分）)19. 寫出下面算法中帶標號語句的頻度。 TYPE ar=ARRAY1.n OF datatype; PROCEDURE perm ( a: ar; k, n: integer); VAR x: datatype; i:integer; BEGIN （1）IF k=n THEN BEGIN （2）FOR i:=1 TO n DO （3）write (ai); writeln; EN

19、D ELSE 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. 分析下面程序段中循環(huán)語句的執(zhí)行次數(shù)。i:=0;s:=0;n:=100;REPEAT i:=i+1; s:=s+10*i;UNTIL NOT(in) AND (sn);(北京郵電大學 1998 四、1（5分）)21下列算法對一n位二進制數(shù)加1，假如無溢出，該算法的最壞時間復雜性是什么？并分析它的平均時間復雜性。TYPE num=ARRAY 1.n of 0.1；PROCEDU

20、RE Inc （VAR a：num）；VAR i：integer；BEGIN i：=n；WHILE Ai=1 DOBEGIN Ai：=0； i：=i-1；END；END；Ai：=1；END Inc；(東南大學1998 三 (8分) 1994 二（15分）)22. 閱讀下列算法，指出算法A的功能和時間復雜性 PROCEDURE A (h,g:pointer);(h,g分別為單循環(huán)鏈表（single linked circular list）中兩個結點指針)PROCEDURE B(s,q:pointer)； VAR p:pointer; BEGIN p:=s; WHILE p.nextq DO p

21、:=p.next; p.next:=s; END;(of B)BEGINB(h,g); B(g,h);END;（of A）(東南大學 1999 二（10分）)23. 調(diào)用下列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(int n) int i,j，k,sum= 0; for(i=l; ii-1; j-) for(k=1;kj+1;k+ ) sum+; printf(sum=%dn,sum)； return (sum);

22、(華中理工大學 2000 六（10分）)24設n是偶數(shù)，試計算運行下列程序段后m的值并給出該程序段的時間復雜度。m:=0;FOR i:=1 TO n DO FOR j:=2*i TO n DO m:=m+1;(南京郵電大學 2000 一、1)25有下列運行時間函數(shù)： （1）T1 (n)=1000; （2）T2(n)=n2+1000n; （3）T3(n)=3n3+100n2+n+1;分別寫出相應的大O表示的運算時間。(吉林工業(yè)大學 1999 二（12分）)26. 試給出下面兩個算法的運算時間。 （1） for i1 to n do x x+1 END（2） for i 1 to n do for

23、 j1 to n do x x+1 end end(中科院自動化研究所 1995 二、2 （6分）)27. 斐波那契數(shù)列Fn定義如下 F0=0， Fl=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ù)的時間復雜度錄多少?(清華大學 2000 二（12分）)28將下列函數(shù)，按它們在n時的無窮大階數(shù)，從小到大排序。 n, n-n3+7n5, nlogn, 2n/2, n3, logn, n1/2

24、+logn, (3/2)n, ,n!, n2+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ù)元素間關系 2集合 線性結構 樹形結構 圖狀結構或網(wǎng)狀結構。3數(shù)據(jù)的組織形式，即數(shù)據(jù)元素之間邏輯關系的總體。而邏輯關系是指數(shù)據(jù)元素之間的關聯(lián)方式或稱“鄰接關系”。4表示（又稱映像）。 5（1）邏輯特性 （2）在計算機內(nèi)部如何表示和實現(xiàn) （3）數(shù)學特性。6算

25、法的時間復雜度和空間復雜度。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)/6 O(n3)11. log2n 12. nlog2n 13. log2n2 14. (n+3)(n-2)/2 15. O(n)16. (1)1 (2)1 (3)f(m,n-1) (4)n 9 17. n(n-1)/2四應用題1數(shù)據(jù)結構是一門研究在非數(shù)值計算的程序設計問題中，計算機的操作對象及對象間的關系和施加于對象的

26、操作等的學科。2四種表示方法（1）順序存儲方式。數(shù)據(jù)元素順序存放，每個存儲結點只含一個元素。存儲位置反映數(shù)據(jù)元素間的邏輯關系。存儲密度大，但有些操作（如插入、刪除）效率較差。（2）鏈式存儲方式。每個存儲結點除包含數(shù)據(jù)元素信息外還包含一組（至少一個）指針。指針反映數(shù)據(jù)元素間的邏輯關系。這種方式不要求存儲空間連續(xù)，便于動態(tài)操作（如插入、刪除等），但存儲空間開銷大（用于指針），另外不能折半查找等。（3）索引存儲方式。除數(shù)據(jù)元素存儲在一地址連續(xù)的內(nèi)存空間外，尚需建立一個索引表，索引表中索引指示存儲結點的存儲位置（下標）或存儲區(qū)間端點（下標），兼有靜態(tài)和動態(tài)特性。（4）散列存儲方式。通過散列函數(shù)和解決沖

27、突的方法，將關鍵字散列在連續(xù)的有限的地址空間內(nèi)，并將散列函數(shù)的值解釋成關鍵字所在元素的存儲地址，這種存儲方式稱為散列存儲。其特點是存取速度快，只能按關鍵字隨機存取，不能順序存取，也不能折半存取。3數(shù)據(jù)類型是程序設計語言中的一個概念，它是一個值的集合和操作的集合。如C語言中的整型、實型、字符型等。整型值的范圍（對具體機器都應有整數(shù)范圍），其操作有加、減、乘、除、求余等。實際上數(shù)據(jù)類型是廠家提供給用戶的已實現(xiàn)了的數(shù)據(jù)結構?！俺橄髷?shù)據(jù)類型（ADT）”指一個數(shù)學模型及定義在該模型上的一組操作?！俺橄蟆钡囊饬x在于數(shù)據(jù)類型的數(shù)學抽象特性。抽象數(shù)據(jù)類型的定義僅取決于它的邏輯特性，而與其在計算機內(nèi)部如何表示和

28、實現(xiàn)無關。無論其內(nèi)部結構如何變化，只要它的數(shù)學特性不變就不影響它的外部使用。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實質(zhì)上是一個概念。此外，抽象數(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ù)據(jù)元素之間的關聯(lián)方式或“鄰接關系”），數(shù)據(jù)的存儲結構是數(shù)據(jù)結構在計算機中的表示，包括數(shù)據(jù)元素的表示及其關系的表示。數(shù)據(jù)的運算是對數(shù)

29、據(jù)定義的一組操作，運算是定義在邏輯結構上的，和存儲結構無關，而運算的實現(xiàn)則是依賴于存儲結構。 （2）邏輯結構相同但存儲不同，可以是不同的數(shù)據(jù)結構。例如，線性表的邏輯結構屬于線性結構，采用順序存儲結構為順序表，而采用鏈式存儲結構稱為線性鏈表。 （3）棧和隊列的邏輯結構相同，其存儲表示也可相同（順序存儲和鏈式存儲），但由于其運算集合不同而成為不同的數(shù)據(jù)結構。 （4）數(shù)據(jù)結構的評價非常復雜，可以考慮兩個方面，一是所選數(shù)據(jù)結構是否準確、完整的刻劃了問題的基本特征；二是是否容易實現(xiàn)（如對數(shù)據(jù)分解是否恰當；邏輯結構的選擇是否適合于運算的功能，是否有利于運算的實現(xiàn)；基本運算的選擇是否恰當。）5評價好的算法有

30、四個方面。一是算法的正確性；二是算法的易讀性；三是算法的健壯性；四是算法的時空效率（運行）。6（1）見上面題3 （2）見上面題4 （3）見上面題3 （4）算法的時間復雜性是算法輸入規(guī)模的函數(shù)。算法的輸入規(guī)?；騿栴}的規(guī)模是作為該算法輸入的數(shù)據(jù)所含數(shù)據(jù)元素的數(shù)目，或與此數(shù)目有關的其它參數(shù)。有時考慮算法在最壞情況下的時間復雜度或平均時間復雜度。 （5）算法是對特定問題求解步驟的描述，是指令的有限序列，其中每一條指令表示一個或多個操作。算法具有五個重要特性：有窮性、確定性、可行性、輸入和輸出。 （6）頻度。在分析算法時間復雜度時，有時需要估算基本操作的原操作，它是執(zhí)行次數(shù)最多的一個操作，該操作重復執(zhí)行

31、的次數(shù)稱為頻度。7集合、線性結構、樹形結構、圖形或網(wǎng)狀結構。 8邏輯結構、存儲結構、操作（運算）。9通?？紤]算法所需要的存儲空間量和算法所需要的時間量。后者又涉及到四方面：程序運行時所需輸入的數(shù)據(jù)總量，對源程序進行編譯所需時間，計算機執(zhí)行每條指令所需時間和程序中指令重復執(zhí)行的次數(shù)。10D是數(shù)據(jù)元素的有限集合，S是D上數(shù)據(jù)元素之間關系的有限集合。11“數(shù)據(jù)結構”這一術語有兩種含義，一是作為一門課程的名稱；二是作為一個科學的概念。作為科學概念，目前尚無公認定義，一般認為，討論數(shù)據(jù)結構要包括三個方面，一是數(shù)據(jù)的邏輯結構，二是數(shù)據(jù)的存儲結構，三是對數(shù)據(jù)進行的操作（運算）。而數(shù)據(jù)類型是值的集合和操作的集

32、合，可以看作是已實現(xiàn)了的數(shù)據(jù)結構，后者是前者的一種簡化情況。12見上面題2。13將學號、姓名、平均成績看成一個記錄（元素，含三個數(shù)據(jù)項），將100個這樣的記錄存于數(shù)組中。因一般無增刪操作，故宜采用順序存儲。 typedef struct int num;/學號 char name8;/姓名 float score;/平均成績 node； node student100;14. 見上面題4（3）。15應從兩方面進行討論：如通訊錄較少變動（如城市私人電話號碼），主要用于查詢，以順序存儲較方便，既能順序查找也可隨機查找；若通訊錄經(jīng)常有增刪操作，用鏈式存儲結構較為合適，將每個人的情況作為一個元素（即一

33、個結點存放一個人），設姓名作關鍵字，鏈表安排成有序表，這樣可提高查詢速度。16線性表中的插入、刪除操作，在順序存儲方式下平均移動近一半的元素，時間復雜度為O（n）；而在鏈式存儲方式下，插入和刪除時間復雜度都是O（1）。17對算法A1和A2的時間復雜度T1和T2取對數(shù)，得nlog2和2logn。顯然，算法A2好于A1。18. struct node int year,month,day; ; typedef struct int 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