數(shù)據(jù)結(jié)構(gòu)考試題庫(kù)(含參考答案)

1、第1章     緒論        一、選擇題1. 算法的計(jì)算量的大小稱為計(jì)算的（    ）?！颈本┼]電大學(xué)2000 二、3 （20/8分）】A效率          B. 復(fù)雜性       C. 現(xiàn)實(shí)性&#

2、160;          D. 難度2. 算法的時(shí)間復(fù)雜度取決于（ ）【中科院計(jì)算所 1998 二、1 （2分）】A問(wèn)題的規(guī)模      B. 待處理數(shù)據(jù)的初態(tài)      C. A和B3.計(jì)算機(jī)算法指的是（1），它必須具備（2） 這三個(gè)特性。(1) A計(jì)算方法     

3、;B. 排序方法        C. 解決問(wèn)題的步驟序列      D. 調(diào)度方法(2) A可執(zhí)行性、可移植性、可擴(kuò)充性    B. 可執(zhí)行性、確定性、有窮性C. 確定性、有窮性、穩(wěn)定性          D. 易讀性、穩(wěn)定性、安全性  &

4、#160;   【南京理工大學(xué) 1999 一、1（2分） 【武漢交通科技大學(xué) 1996 一、1（ 4分）】4一個(gè)算法應(yīng)該是（     ）。【中山大學(xué) 1998 二、1（2分）】     A程序     B問(wèn)題求解步驟的描述     C要滿足五個(gè)基本特性    

5、    DA和C.5. 下面關(guān)于算法說(shuō)法錯(cuò)誤的是（    ）【南京理工大學(xué) 2000 一、1（1.5分）】A算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)B. 為解決某問(wèn)題的算法同為該問(wèn)題編寫(xiě)的程序含義是相同的C. 算法的可行性是指指令不能有二義性          D. 以上幾個(gè)都是錯(cuò)誤的6. 下面說(shuō)法錯(cuò)誤的是（    ）【

6、南京理工大學(xué) 2000 一、2 （1.5分）】    (1）算法原地工作的含義是指不需要任何額外的輔助空間   （2）在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時(shí)間上總是優(yōu)于復(fù)雜度O(2n)的算法   （3）所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界   （4）同一個(gè)算法，實(shí)現(xiàn)語(yǔ)言的級(jí)別越高，執(zhí)行效率就越低 A(1)      B.(1),(2) 

7、;   C.(1),(4)     D.(3)7從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（    ）兩大類(lèi)。 【武漢交通科技大學(xué) 1996 一 、4（2分）】A動(dòng)態(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)8以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)的術(shù)語(yǔ)是（   &#

8、160;）?！颈狈浇煌ù髮W(xué) 2000 二、1（2分）】A循環(huán)隊(duì)列       B. 鏈表        C. 哈希表          D.  棧9以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線性結(jié)構(gòu)（    ）？【北方交通大學(xué) 2001 一、1（2

9、分）】A廣義表         B. 二叉樹(shù)      C. 稀疏矩陣         D.  串10以下那一個(gè)術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)？（    ）【北方交通大學(xué) 2001 一、2（2分）】A棧     &#

10、160;       B. 哈希表      C. 線索樹(shù)           D.  雙向鏈表11在下面的程序段中，對(duì)x的賦值語(yǔ)句的頻度為（    ）【北京工商大學(xué) 2001 一、10（3分）】FOR i:=1  TO 

11、0;n  DO    FOR j:=1  TO  n  DO        x:=x+1;A O(2n)       BO(n)       CO(n2)        

12、 DO(log2n)  12程序段 FOR  i:=n-1  DOWNTO  1  DO            FOR j:=1 TO i DO               IF Aj>Aj+1 

13、;                 THEN  Aj與Aj+1對(duì)換；其中 n為正整數(shù)，則最后一行的語(yǔ)句頻度在最壞情況下是（   ）A. O（n）    B. O(nlogn)     C. O(n3)     D. O(n2)&#

14、160;  【南京理工大學(xué)1998一、1(2分)】13以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)不是多型數(shù)據(jù)類(lèi)型（    ）【中山大學(xué) 1999 一、3（1分）】A棧        B廣義表       C有向圖       D字符串14以下數(shù)據(jù)結(jié)構(gòu)中，（    ）是非線性數(shù)據(jù)結(jié)構(gòu)【中

15、山大學(xué) 1999 一、4】A樹(shù)        B字符串       C隊(duì)           D棧15. 下列數(shù)據(jù)中，（    ）是非線性數(shù)據(jù)結(jié)構(gòu)。【北京理工大學(xué) 2001 六、1（2分）】A棧    

16、0;  B.  隊(duì)列         C.  完全二叉樹(shù)    D. 堆16連續(xù)存儲(chǔ)設(shè)計(jì)時(shí)，存儲(chǔ)單元的地址（    ）?！局猩酱髮W(xué) 1999 一、1（1分）】A一定連續(xù)  B一定不連續(xù)  C不一定連續(xù)  D部分連續(xù)，部分不連續(xù)17以下屬于邏輯結(jié)構(gòu)的是（  &#

17、160; ）?！疚靼搽娮涌萍即髮W(xué)應(yīng)用 2001一、1】A順序表       B. 哈希表        C.有序表          D.  單鏈表 二、判斷題1. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。(    )【北京郵電大學(xué) 1998&

18、#160;一、1（2分）】【青島大學(xué) 2000  一、1 （1分）】【上海交通大學(xué) 1998 一、1】  【山東師范大學(xué) 2001 一、1 （2分）】2. 記錄是數(shù)據(jù)處理的最小單位。 (    ) 【上海海運(yùn)學(xué)院 1998 一、5（1分）】3. 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系；(   )【北京郵電大學(xué)2002 一、1（1分）】4算法

19、的優(yōu)劣與算法描述語(yǔ)言無(wú)關(guān)，但與所用計(jì)算機(jī)有關(guān)。(    )【大連海事大學(xué) 2001 一、10（1分）】5健壯的算法不會(huì)因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。(    )【大連海事大學(xué) 2001 一、11（1分）】6算法可以用不同的語(yǔ)言描述，如果用C 語(yǔ)言或PASCAL語(yǔ)言等高級(jí)語(yǔ)言來(lái)描述，則算法實(shí)際上就是程序了。(    )【西安交通大學(xué) 1996 二、7（3分）】7程序一定是算法。(  

20、;  )【燕山大學(xué) 1998 二、2（2分）并改錯(cuò)】8數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲(chǔ)形式。(   )【山東師范大學(xué)2001 一、2（2分）】9. 數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實(shí)現(xiàn)有關(guān)。(    )【華南理工大學(xué) 2002 一、1（1分）】10. 在順序存儲(chǔ)結(jié)構(gòu)中，有時(shí)也存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。(    )【華南理工大學(xué) 2002 一、2 （1分）】

21、11. 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。(    )【上海海運(yùn)學(xué)院 1999 一、1（1分）】12. 數(shù)據(jù)結(jié)構(gòu)的基本操作的設(shè)置的最重要的準(zhǔn)則是，實(shí)現(xiàn)應(yīng)用程序與存儲(chǔ)結(jié)構(gòu)的獨(dú)立。(    )【華南理工大學(xué) 2002 一、5（1分）】13. 數(shù)據(jù)的邏輯結(jié)構(gòu)說(shuō)明數(shù)據(jù)元素之間的順序關(guān)系,它依賴于計(jì)算機(jī)的儲(chǔ)存結(jié)構(gòu). (    )【上海海運(yùn)學(xué)院 1998 一、1（1分）】

22、60;三、填空1數(shù)據(jù)的物理結(jié)構(gòu)包括   數(shù)據(jù)元素      的表示和    數(shù)據(jù)元素關(guān)系      的表示?！狙嗌酱髮W(xué) 1998 一、1（2分）】2. 對(duì)于給定的n個(gè)元素,可以構(gòu)造出的邏輯結(jié)構(gòu)有  集合  ，  線性結(jié)構(gòu)  ，  樹(shù)形結(jié)構(gòu)  ，_圖狀結(jié)構(gòu)或網(wǎng)狀

23、結(jié)構(gòu)_四種。【中科院計(jì)算所 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)系”     ?！颈本┼]電大學(xué) 2001 二、1（2分）】4一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的    表示（或稱映像）     稱為存儲(chǔ)結(jié)構(gòu)（又?jǐn)?shù)據(jù)的物理結(jié)構(gòu)）?！救A中理工大學(xué) 2000 一、1

24、（1分）】5抽象數(shù)據(jù)類(lèi)型的定義僅取決于它的一組_邏輯特性_，而與_在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)_無(wú)關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的_數(shù)學(xué)特性_不變，都不影響其外部使用?！旧綎|大學(xué) 2001 三、3（2分）】6數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是    算法的時(shí)間復(fù)雜度和空間復(fù)雜度      【北京理工大學(xué) 2001 七、1（2分）】7. 數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的_邏輯結(jié)構(gòu)_和_物理結(jié)構(gòu)_，以及它們之間的相互關(guān)系，并對(duì)與這種結(jié)構(gòu)定義相應(yīng)的_操作（運(yùn)算

25、）_，設(shè)計(jì)出相應(yīng)的_算法?！疚靼搽娮涌萍即髮W(xué) 1998 二、2（3分）】8 一個(gè)算法具有5個(gè)特性: 有窮性 、 確定性 、 可行性 ，有零個(gè)或多個(gè)輸入、有一個(gè)或多個(gè)輸出 ?！救A中理工大學(xué) 2000 一、2（5分）】 【燕山大學(xué) 1998 一、2（5分）】9已知如下程序段FOR i:= n  DOWNTO  1  DO        

26、60;語(yǔ)句1BEGINx:=x+1；                      語(yǔ)句2FOR j:=n  DOWNTO  i  DO   語(yǔ)句3 y:=y+1;          

27、           語(yǔ)句4END；語(yǔ)句1執(zhí)行的頻度為 n+1 ；語(yǔ)句2執(zhí)行的頻度為 n ；語(yǔ)句3執(zhí)行的頻度為 n(n+3)/2 ；語(yǔ)句4執(zhí)行的頻度為 n(n+1)/2 。【北方交通大學(xué) 1999 二、4（5分）】10在下面的程序段中，對(duì)的賦值語(yǔ)句的頻度為_(kāi)1+（1+2+（1+2+3）+（1+2+n）=n(n+1)(n+2)/6 _（表示為n的函數(shù)）  &#

28、160;FORi： TO  nDOFORj：TO  iDOFORk：1TOjDO：delta；【北京工業(yè)大學(xué) 1999  一、6（2分）】11.下面程序段中帶下劃線的語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)是：  log2n    【合肥工業(yè)大學(xué)1999三、1（2分）】i：=1； WHILE i<n DO i：=i*2;12. 下面程序段中帶下劃線的語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)是(  nlog2n  &#

29、160;)?！竞戏使I(yè)大學(xué) 2000 三、1（2分）】i:=1;WHILE i<n BEGIN  FOR j:=1 TO n DO x:=x+1;i:=i*2  END；13. 下面程序段中帶有下劃線的語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)是(  log2n2  ) 【合肥工業(yè)大學(xué) 2001 三、1（2分）】i：=n*n    WHILE i<>1  DO i:=i div

30、2;14. 計(jì)算機(jī)執(zhí)行下面的語(yǔ)句時(shí)，語(yǔ)句s的執(zhí)行次數(shù)為 _(n+3)(n-2)/2 _ ?！灸暇├砉ご髮W(xué)2000二、1（1.5分）】  FOR(i=l；i<n-l；i+)   FOR(j=n;j>=i;j-)   s;15. 下面程序段的時(shí)間復(fù)雜度為_(kāi)O（n）_。(n>1)        sum=1；      

31、0; for (i=0;sum<n;i+) sum+=1;   【南京理工大學(xué) 2001 二、1（2分）】16設(shè)m.n均為自然數(shù)，m可表示為一些不超過(guò)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ù)的程序段，請(qǐng)將未完成的部分填入，使之完整int f(m,n)   int m,n; if(m=1)       

32、60;return  1   if(n=1)        return  1   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 

33、60;  。 【中科院軟件所 1997 二、1 （9分）】17. 在有n個(gè)選手參加的單循環(huán)賽中，總共將進(jìn)行_n(n-1)/2_場(chǎng)比賽?！竞戏使I(yè)大學(xué)1999三、8（2分）】 四、應(yīng)用題1. 數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究什么內(nèi)容的學(xué)科？【燕山大學(xué) 1999 二、1 （4分）】2. 數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有幾種表示方法？各有什么特點(diǎn)？【燕山大學(xué)1999 二、2（4分）】3. 數(shù)據(jù)類(lèi)型和抽象數(shù)據(jù)類(lèi)型是如何定義的。二者有何相同和不同之處，抽象數(shù)據(jù)類(lèi)型的主要特點(diǎn)是什么？

34、使用抽象數(shù)據(jù)類(lèi)型的主要好處是什么？【北京郵電大學(xué)1994 一（8分）】4. 回答問(wèn)題（每題2分）【山東工業(yè)大學(xué) 1997 一 （8分）】（1）在數(shù)據(jù)結(jié)構(gòu)課程中，數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)及數(shù)據(jù)的運(yùn)算之間存在著怎樣的關(guān)系？（2）若邏輯結(jié)構(gòu)相同但存儲(chǔ)結(jié)構(gòu)不同，則為不同的數(shù)據(jù)結(jié)構(gòu)。這樣的說(shuō)法對(duì)嗎？舉例說(shuō)明之。（3）在給定的邏輯結(jié)構(gòu)及其存儲(chǔ)表示上可以定義不同的運(yùn)算集合，從而得到不同的數(shù)據(jù)結(jié)構(gòu) 。這樣說(shuō)法對(duì)嗎？舉例說(shuō)明之。（4）評(píng)價(jià)各種不同數(shù)據(jù)結(jié)構(gòu)的標(biāo)準(zhǔn)是什么？5評(píng)價(jià)一個(gè)好的算法，您是從哪幾方面來(lái)考慮的？【大連海事大學(xué) 1996  

35、;二、3 （2分）】【中山大學(xué) 1998 三、1 （5分）】6解釋和比較以下各組概念【華南師范大學(xué) 2000 一（10分）】（1）抽象數(shù)據(jù)類(lèi)型及數(shù)據(jù)類(lèi)型  （2）數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)（3）抽象數(shù)據(jù)類(lèi)型 【哈爾濱工業(yè)大學(xué) 2000 一、1（3分）】（4）算法的時(shí)間復(fù)雜性 【河海大學(xué) 1998 一、2（3分）】（5）算法【吉林工業(yè)大學(xué)1999  一、1（2分）】（6）頻度【吉林工業(yè)大學(xué) 1999 一、2（2分）】7.

36、60;根據(jù)數(shù)據(jù)元素之間的邏輯關(guān)系，一般有哪幾類(lèi)基本的數(shù)據(jù)結(jié)構(gòu)？【北京科技大學(xué) 1998 一、1】【同濟(jì)大學(xué) 1998】8對(duì)于一個(gè)數(shù)據(jù)結(jié)構(gòu)，一般包括哪三個(gè)方面的討論？【北京科技大學(xué) 1999 一、1（2分）】9. 當(dāng)你為解決某一問(wèn)題而選擇數(shù)據(jù)結(jié)構(gòu)時(shí)，應(yīng)從哪些方面考慮？【西安電子北京科技大學(xué) 2000】10. 若將數(shù)據(jù)結(jié)構(gòu)定義為一個(gè)二元組（D，R）,說(shuō)明符號(hào)D，R 應(yīng)分別表示什么？【北京科技大學(xué) 2001 一、1（2分）】11數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類(lèi)型有什么區(qū)別？【哈爾濱工業(yè)大學(xué) 

37、60;2001 三、1（3分）】12數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)由哪四種基本的存儲(chǔ)方法實(shí)現(xiàn)？【山東科技大學(xué) 2001 一、1（4分）】13若有100個(gè)學(xué)生，每個(gè)學(xué)生有學(xué)號(hào)，姓名，平均成績(jī)，采用什么樣的數(shù)據(jù)結(jié)構(gòu)最方便，寫(xiě)出這些結(jié)構(gòu)？【山東師范大學(xué) 1996 二、2（2分）】14. 運(yùn)算是數(shù)據(jù)結(jié)構(gòu)的一個(gè)重要方面。試舉一例，說(shuō)明兩個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲(chǔ)方式完全相同，只是對(duì)于運(yùn)算的定義不同。因而兩個(gè)結(jié)構(gòu)具有顯著不同的特性，是兩個(gè)不同的結(jié)構(gòu)?！颈本┐髮W(xué) 1998一、1（5分）】15. 在編制管理通訊錄的程序時(shí), 什么樣的數(shù)據(jù)

38、結(jié)構(gòu)合適? 為什么?【 長(zhǎng)沙鐵道學(xué)院1998四、3(6分)】16. 試舉一例，說(shuō)明對(duì)相同的邏輯結(jié)構(gòu),同一種運(yùn)算在不同的存儲(chǔ)方式下實(shí)現(xiàn)，其運(yùn)算效率不同?！颈本├砉ご髮W(xué) 2000 三、1（4.5分）】17. 有實(shí)現(xiàn)同一功能的兩個(gè)算法A1和A2，其中A1的時(shí)間復(fù)雜度為T(mén)l=O(2n)，A2的時(shí)間復(fù)雜度為T(mén)2=O(n2)，僅就時(shí)間復(fù)雜度而言，請(qǐng)具體分析這兩個(gè)算法哪一個(gè)好。【北京航空航天大學(xué) 2000 二（10分）】18設(shè)計(jì)一數(shù)據(jù)結(jié)構(gòu)，用來(lái)表示某一銀行儲(chǔ)戶的基本信息： 賬號(hào)、姓名、開(kāi)戶年月日、儲(chǔ)蓄類(lèi)型 、存入累加數(shù)、利息、帳面總數(shù)?！?/p>

39、浙江大學(xué) 1994 一 、3（5分）】19. 寫(xiě)出下面算法中帶標(biāo)號(hào)語(yǔ)句的頻度。   TYPE  ar=ARRAY1.n OF datatype;   PROCEDURE    perm  ( a: ar; k, n: integer);     VAR   x: datatype;     i:integer;

40、0;    BEGIN       （1）IF k=n            THEN BEGIN                （2）FOR  i:=1  TO

41、0; n DO                （3）write (ai);                     writeln;       &#

42、160;         END             ELSE BEGIN                （4） FOR   i:=k  TO &

43、#160;n  DO                （5）ai:=ai+i*i;                （6） perm (a, k+1, n);        

44、          END;         END;設(shè)k的初值等于1?！颈本┼]電大學(xué) 1997二（10分）】20. 分析下面程序段中循環(huán)語(yǔ)句的執(zhí)行次數(shù)。i:=0;s:=0;n:=100;REPEAT   i:=i+1;   s:=s+10*i;UNTIL  NOT(i<n) AND (s<n);

45、【北京郵電大學(xué) 1998 四、1（5分）】21下列算法對(duì)一n位二進(jìn)制數(shù)加1，假如無(wú)溢出，該算法的最壞時(shí)間復(fù)雜性是什么？并分析它的平均時(shí)間復(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

46、ND Inc；【東南大學(xué)1998 三 (8分)  1994 二（15分）】22. 閱讀下列算法，指出算法A的功能和時(shí)間復(fù)雜性       PROCEDURE  A (h,g:pointer);(h,g分別為單循環(huán)鏈表（single linked  circular list）中兩個(gè)結(jié)點(diǎn)指針)PROCEDURE  B(s,q:pointer)；    VAR p:poi

47、nter;    BEGIN        p:=s;        WHILE p.next<>q DO p:=p.next;        p.next:=s;    END;(of B)BEGINB(h,g);  B(g,h);END;（of

48、 A）【東南大學(xué) 1999 二（10分）】23. 調(diào)用下列C函數(shù)f(n)或PASACAL函數(shù)f(n)   回答下列問(wèn)題 :（1） 試指出f(n)值的大小，并寫(xiě)出f(n) 值的推導(dǎo)過(guò)程;（2） 假定n= 5，試指出f(5)值的大小和執(zhí)行f(5)時(shí)的輸出結(jié)果 。      C函數(shù)： int f(int  n)          &#

49、160;   int i,j，k,sum= 0;              for(i=l; i<n+1;i+)               for(j=n;j>i-1; j-)        &#

50、160;        for(k=1;k<j+1;k+ ) sum+;                 printf("sum=%dn",sum)；             

51、0;return (sum);  【華中理工大學(xué) 2000 六（10分）】24設(shè)n是偶數(shù)，試計(jì)算運(yùn)行下列程序段后m的值并給出該程序段的時(shí)間復(fù)雜度。m:=0;FOR  i:=1  TO  n  DO  FOR  j:=2*i  TO  n  DO      m:=m+1;【南京郵電大學(xué) 2000 一、

52、1】25有下列運(yùn)行時(shí)間函數(shù)：（1）T1 (n)=1000;    （2）T2(n)=n2+1000n;     （3）T3(n)=3n3+100n2+n+1;分別寫(xiě)出相應(yīng)的大O表示的運(yùn)算時(shí)間?！炯止I(yè)大學(xué) 1999  二（12分）】26. 試給出下面兩個(gè)算法的運(yùn)算時(shí)間。（1）  for  i1   to   n   do

53、60;      x  x+1      END（2）  for i 1   to  n  do        for  j1  to  n  do    &#

54、160;       x x+1          end     end【中科院自動(dòng)化研究所 1995 二、2 （6分）】27. 斐波那契數(shù)列Fn定義如下     F0=0，  Fl=1， Fn=Fn-1+Fn-2,  

55、0;n=2,3.   請(qǐng)就此斐波那契數(shù)列，回答下列問(wèn)題。   (1)  (7分) 在遞歸計(jì)算Fn的時(shí)候，需要對(duì)較小的Fn-1，F(xiàn)n-2，, Fl, F0精確計(jì)算多少次?   (2)  (5分) 如果用大O表示法，試給出遞歸計(jì)算Fn時(shí)遞歸函數(shù)的時(shí)間復(fù)雜度錄多少?【清華大學(xué) 2000 二（12分）】28將下列函數(shù)，按它們?cè)趎時(shí)的無(wú)窮大階數(shù)，從小到大排序。    n, n-n3+7n5, nl

56、ogn, 2n/2, n3, logn, n1/2+logn, (3/2)n, ,n!, n2+logn【中科院計(jì)算所 1995 】 第1章           緒論一、選擇題 1.B2.C3.1C3.2B4.B5.D6.C7.C8.D9.D10.A11.C12.D13.D14.A15.C16.A17.C      二、判斷題1. ×2. ×3.×

57、4.×5. 6. ×7. ×8. 9.×10.×11.×12. 13. ×            三填空題1數(shù)據(jù)元素   數(shù)據(jù)元素間關(guān)系       2集合  線性結(jié)構(gòu)   樹(shù)形結(jié)構(gòu)   圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。3數(shù)據(jù)的組織形式，即數(shù)

58、據(jù)元素之間邏輯關(guān)系的總體。而邏輯關(guān)系是指數(shù)據(jù)元素之間的關(guān)聯(lián)方式或稱“鄰接關(guān)系”。4表示（又稱映像）。    5（1）邏輯特性  （2）在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)  （3）數(shù)學(xué)特性。6算法的時(shí)間復(fù)雜度和空間復(fù)雜度。7（1）邏輯結(jié)構(gòu)（2）物理結(jié)構(gòu)（3）操作（運(yùn)算）（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

59、）+（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.  

60、 (1)1  (2)1  (3)f(m,n-1)  (4)n     9         17. n(n-1)/2 四應(yīng)用題1數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究在非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中，計(jì)算機(jī)的操作對(duì)象及對(duì)象間的關(guān)系和施加于對(duì)象的操作等的學(xué)科。2四種表示方法（1）順序存儲(chǔ)方式。數(shù)據(jù)元素順序存放，每個(gè)存儲(chǔ)結(jié)點(diǎn)只含一個(gè)元素。存儲(chǔ)位置反映數(shù)據(jù)元素間的邏輯關(guān)系。存儲(chǔ)密度大，但有些操作（如插入、刪除

61、）效率較差。（2）鏈?zhǔn)酱鎯?chǔ)方式。每個(gè)存儲(chǔ)結(jié)點(diǎn)除包含數(shù)據(jù)元素信息外還包含一組（至少一個(gè)）指針。指針?lè)从硵?shù)據(jù)元素間的邏輯關(guān)系。這種方式不要求存儲(chǔ)空間連續(xù)，便于動(dòng)態(tài)操作（如插入、刪除等），但存儲(chǔ)空間開(kāi)銷(xiāo)大（用于指針），另外不能折半查找等。（3）索引存儲(chǔ)方式。除數(shù)據(jù)元素存儲(chǔ)在一地址連續(xù)的內(nèi)存空間外，尚需建立一個(gè)索引表，索引表中索引指示存儲(chǔ)結(jié)點(diǎn)的存儲(chǔ)位置（下標(biāo)）或存儲(chǔ)區(qū)間端點(diǎn)（下標(biāo)），兼有靜態(tài)和動(dòng)態(tài)特性。（4）散列存儲(chǔ)方式。通過(guò)散列函數(shù)和解決沖突的方法，將關(guān)鍵字散列在連續(xù)的有限的地址空間內(nèi)，并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的存儲(chǔ)地址，這種存儲(chǔ)方式稱為散列存儲(chǔ)。其特點(diǎn)是存取速度快，只能按關(guān)鍵字隨機(jī)存取

62、，不能順序存取，也不能折半存取。3數(shù)據(jù)類(lèi)型是程序設(shè)計(jì)語(yǔ)言中的一個(gè)概念，它是一個(gè)值的集合和操作的集合。如C語(yǔ)言中的整型、實(shí)型、字符型等。整型值的范圍（對(duì)具體機(jī)器都應(yīng)有整數(shù)范圍），其操作有加、減、乘、除、求余等。實(shí)際上數(shù)據(jù)類(lèi)型是廠家提供給用戶的已實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)?！俺橄髷?shù)據(jù)類(lèi)型（ADT）”指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作?！俺橄蟆钡囊饬x在于數(shù)據(jù)類(lèi)型的數(shù)學(xué)抽象特性。抽象數(shù)據(jù)類(lèi)型的定義僅取決于它的邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無(wú)關(guān)。無(wú)論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變就不影響它的外部使用。抽象數(shù)據(jù)類(lèi)型和數(shù)據(jù)類(lèi)型實(shí)質(zhì)上是一個(gè)概念。此外，抽象數(shù)據(jù)類(lèi)型的范圍更廣，它已不再局限于機(jī)

63、器已定義和實(shí)現(xiàn)的數(shù)據(jù)類(lèi)型，還包括用戶在設(shè)計(jì)軟件系統(tǒng)時(shí)自行定義的數(shù)據(jù)類(lèi)型。使用抽象數(shù)據(jù)類(lèi)型定義的軟件模塊含定義、表示和實(shí)現(xiàn)三部分，封裝在一起，對(duì)用戶透明（提供接口），而不必了解實(shí)現(xiàn)細(xì)節(jié)。抽象數(shù)據(jù)類(lèi)型的出現(xiàn)使程序設(shè)計(jì)不再是“藝術(shù)”，而是向“科學(xué)”邁進(jìn)了一步。4（1）數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系（即數(shù)據(jù)元素之間的關(guān)聯(lián)方式或“鄰接關(guān)系”），數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示，包括數(shù)據(jù)元素的表示及其關(guān)系的表示。數(shù)據(jù)的運(yùn)算是對(duì)數(shù)據(jù)定義的一組操作，運(yùn)算是定義在邏輯結(jié)構(gòu)上的，和存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)，而運(yùn)算的實(shí)現(xiàn)則是依賴于存儲(chǔ)結(jié)構(gòu)。  （2）邏輯結(jié)構(gòu)相同但存儲(chǔ)不同，可以是不同的數(shù)據(jù)

64、結(jié)構(gòu)。例如，線性表的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，采用順序存儲(chǔ)結(jié)構(gòu)為順序表，而采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。  （3）棧和隊(duì)列的邏輯結(jié)構(gòu)相同，其存儲(chǔ)表示也可相同（順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)），但由于其運(yùn)算集合不同而成為不同的數(shù)據(jù)結(jié)構(gòu)。  （4）數(shù)據(jù)結(jié)構(gòu)的評(píng)價(jià)非常復(fù)雜，可以考慮兩個(gè)方面，一是所選數(shù)據(jù)結(jié)構(gòu)是否準(zhǔn)確、完整的刻劃了問(wèn)題的基本特征；二是是否容易實(shí)現(xiàn)（如對(duì)數(shù)據(jù)分解是否恰當(dāng)；邏輯結(jié)構(gòu)的選擇是否適合于運(yùn)算的功能，是否有利于運(yùn)算的實(shí)現(xiàn)；基本運(yùn)算的選擇是否恰當(dāng)。）5評(píng)價(jià)好的算法有四個(gè)方面。一是算法的正確性；二是算法的易讀性；三是算法的健壯性；四是算法的時(shí)空效率（運(yùn)行）。6（

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

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

67、三是對(duì)數(shù)據(jù)進(jìn)行的操作（運(yùn)算）。而數(shù)據(jù)類(lèi)型是值的集合和操作的集合，可以看作是已實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)，后者是前者的一種簡(jiǎn)化情況。12見(jiàn)上面題2。13將學(xué)號(hào)、姓名、平均成績(jī)看成一個(gè)記錄（元素，含三個(gè)數(shù)據(jù)項(xiàng)），將100個(gè)這樣的記錄存于數(shù)組中。因一般無(wú)增刪操作，故宜采用順序存儲(chǔ)。              typedef  struct         

68、0;      int num;/學(xué)號(hào)                 char name8;/姓名                 float score;/平均成績(jī)&

69、#160;               node；               node student100;14. 見(jiàn)上面題4（3）。15應(yīng)從兩方面進(jìn)行討論：如通訊錄較少變動(dòng)（如城市私人電話號(hào)碼），主要用于查詢，以順序存儲(chǔ)較方便，既能順序查找也可隨機(jī)查找；若通訊錄經(jīng)常有增刪操作，用鏈?zhǔn)?/p>

70、存儲(chǔ)結(jié)構(gòu)較為合適，將每個(gè)人的情況作為一個(gè)元素（即一個(gè)結(jié)點(diǎn)存放一個(gè)人），設(shè)姓名作關(guān)鍵字，鏈表安排成有序表，這樣可提高查詢速度。16線性表中的插入、刪除操作，在順序存儲(chǔ)方式下平均移動(dòng)近一半的元素，時(shí)間復(fù)雜度為O（n）；而在鏈?zhǔn)酱鎯?chǔ)方式下，插入和刪除時(shí)間復(fù)雜度都是O（1）。17對(duì)算法A1和A2的時(shí)間復(fù)雜度T1和T2取對(duì)數(shù)，得nlog2和2logn。顯然，算法A2好于A1。18. struct node    int year,month,day; ;    typedef struct

71、60;   int num;/帳號(hào)     char name8;/姓名     struct node date;/開(kāi)戶年月日     int tag;/儲(chǔ)蓄類(lèi)型，如：0- 零存，1- 一年定期     float put;/存入累加數(shù)；     float interest;/利息     float total;/帳面總數(shù)    count；19(1)n