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

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

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

4、是線性結構（B.二叉樹 C.10.以下那一個術語與數據的存儲結構無關？ 一、 2（2 分）】A.棧B.鏈表哈希表 C.哈希表 D.）？【北方交通大學稀疏矩陣 D.A ）【 北方交通大學線索樹D.棧2001串2001雙向11.在下面的程序段中，對 x 的賦值語句的頻度為（ 學 2001 一、 10（ 3分）】TOTO）【北京工商大FOR i:=1FOR j:=1 x:=x+1;A O（2n）DODO2 O(n)CO(n2) O(log 2n)12程序段 FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF Aj>Aj+1THEN Aj 與 Aj+1 對換； 其中

5、 n 為正整數，則最后一行的語句頻度在最壞情況下是 A. O （ n） B. O（nlogn） C. O（n 工大學 1998 一、 1（2 分） 】 13以下哪個數據結構不是多型數據類型 （ 1 分）】A.棧B14以下數據結構中，A.樹B15. 下列數據中， 1（2 分）】A.棧 B.16.連續存儲設計時， （ 1 分）】A. 定連續 B .一定不連續不連續17.以下屬于邏輯結構的是（ C 1】A.順序表 B. 哈希表3)C 是非線性數據結構C 隊有向圖廣義表（ A ）字符串C ）是非線性數據結構。隊列 C.存儲單元的地址（2D.O(n 2)）【中山大學D ）南京理1999 一、 3D .

6、字符串 【中山大學 1999 一、4】D .棧北京理工大學 2001 六、完全二叉樹 D. 堆A ）。【中山大學 1999不一定連續 D 部分連續，部分西安電子科技大學應用 2001C. 有序表D.單鏈表、判斷題1. 數據元素是數據的最小單位。 （ X ）【北京郵電大學 1998 一、 1（2 分）】【青島大學 2000 一、1 分）】【上海交通大學 1998 一、 1】 【山東師范大學 2001 一、 1 分）】2. 記錄是數據處理的最小單位。 （ X ） 【上海海運學院 1998 一、 5（1 分）】3. 數據的邏輯結構是指數據的各數據項之間的邏輯關系； （ X ） 【北京郵 電大學 20

7、02 一、1（1 分）】 4算法的優劣與算法描述語言無關，但與所用計算機有關。（ X ）【大連海事大學 2001 一、 10（ 1分）】 5健壯的算法不會因非法的輸入數據而出現莫名其妙的狀態。（ O ）大連海事大學 2001 一、 11（ 1分）】6. 算法可以用不同的語言描述，如果用C語言或PASCALS言等高級語言來描述，則算法實際上就是程序了。 （ X ） 【西安交通大學 1996 二、 7 （ 3 分）】7. 程序一定是算法。 （ X ） 【燕山大學 1998 二、 2（2 分）并改錯】&數據的物理結構是指數據在計算機內的實際存儲形式。（0）【山東師范大學 2001 一、2（2

8、 分）】1(1 分)】( 0)X )9. 數據結構的抽象操作的定義與具體實現有關。 （ X ） 【華南理工大學 2002 一10. 在順序存儲結構中，有時也存儲數據結構中元素之間的關系。（ X ）【華南理工大學 2002 一、 2 （1分）】11. 順序存儲方式的優點是存儲密度大，且插入、刪除運算效率高。（ X ）【上海海運學院 1999 一、1（1 分）】12. 數據結構的基本操作的設置的最重要的準則是， 實現應用程序與存儲結構的獨立。【華南理工大學 2002 一、5（1 分）】13. 數據的邏輯結構說明數據元素之間的順序關系 ,它依賴于計算機的儲存結構 . （【上海海運學院 1998 一、

9、1（1 分）】、填空1. 數據的物理結構包括 數據元素 的表示和 數據元素間關系 的表示。【燕山 大學 1998 一、1（2 分）】2. 對于給定的 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分）】& 一個算法具有5個特性：（1）有窮性（2）確定性 （3）可行性，有零個或多個輸入、有一個或多個輸出。【華中理工大學 2000 一、2

11、 （5分）】【燕山大學1998 一、2 （5分）】9. 已知如下程序段FOR i:= n DOWNTO 1 DO語句 1BEGINx:=x+1 ;語句 2FOR j:=nDOWNTO i DO語句 3y:=y+1;語句 4END ;語句1執行的頻度為_n +1_;語句2執行的頻度為n；語句3執行的頻度為n（n+3）/2 ;語句4執行的頻度為n（n +1）/2。【北方交通大學1999 二、4 （5分）】10. 在下面的程序段中， 對x的賦值語句的頻度為1+ （1+2+ （ 1+2+3）3+ + （1+2+n） =n（n +1）（ n+2）/6 O（n ）（表示為n的函數）FOR i ： =1 T

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

13、行次數的數量級是(log 2n2)【合肥工業大學 2001三、1( 2分)】i : =n*n WHILE 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的自然

14、數之和，f(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個選手參加的單循環賽中，總共將進行n(

15、n-1)/2場比賽。【合肥工業大學1999三、8 (2分)】四、應用題1. 數據結構是一門研究什么內容的學科？【燕山大學1999二、1 (4分)】 數據結構是一門研究在非數值計算的程序設計問題中， 計算機的操作 對象及對象間的關系和施加于對象的操作等的學科。2. 數據元素之間的關系在計算機中有幾種表示方法？各有什么特點？ 【燕 山大學 1999 二、2（4 分）】四種表示方法（ 1）順序存儲方式。數據元素順序存放，每個存儲結點只含一個元素。 存儲位置反映數據元素間的邏輯關系。 存儲密度大， 但有些操作 （如插入、 刪除）效率較差。（ 2）鏈式存儲方式。 每個存儲結點除包含數據元素信息外還包含一

16、組 （至 少一個）指針。指針反映數據元素間的邏輯關系。這種方式不要求存儲空 間連續，便于動態操作 （如插入、刪除等），但存儲空間開銷大 （用于指針） ， 另外不能折半查找等。（ 3）索引存儲方式。 除數據元素存儲在一地址連續的內存空間外，尚需建立一個索引表，索引表中索引指示存儲結點的存儲位置（下標）或存儲 區間端點（下標） ，兼有靜態和動態特性。（ 4）散列存儲方式。 通過散列函數和解決沖突的方法， 將關鍵字散列在 連續的有限的地址空間內，并將散列函數的值解釋成關鍵字所在元素的存 儲地址，這種存儲方式稱為散列存儲。其特點是存取速度快，只能按關鍵 字隨機存取，不能順序存取，也不能折半存取。3.

17、數據類型和抽象數據類型是如何定義的。 二者有何相同和不同之處， 抽 象數據類型的主要特點是什么？使用抽象數據類型的主要好處是什么？ 【北京郵電大學 1994 一（ 8 分）】數據類型是程序設計語言中的一個概念，它是一個值的集合和操作的 集合。如 C 語言中的整型、實型、字符型等。整型值的范圍（對具體機器 都應有整數范圍） ，其操作有加、減、乘、除、求余等。實際上數據類型是 廠家提供給用戶的已實現了的數據結構。 “抽象數據類型（ ADT ）”指一個 數學模型及定義在該模型上的一組操作。 “抽象” 的意義在于數據類型的數 學抽象特性。抽象數據類型的定義僅取決于它的邏輯特性，而與其在計算 機內部如何

18、表示和實現無關。無論其內部結構如何變化，只要它的數學特 性不變就不影響它的外部使用。抽象數據類型和數據類型實質上是一個概 念。此外，抽象數據類型的范圍更廣，它已不再局限于機器已定義和實現 的數據類型，還包括用戶在設計軟件系統時自行定義的數據類型。使用抽 象數據類型定義的軟件模塊含定義、表示和實現三部分，封裝在一起，對 用戶透明 （提供接口） ，而不必了解實現細節。 抽象數據類型的出現使程序 設計不再是“藝術” ，而是向“科學”邁進了一步。4. 回答問題（每題 2 分）【山東工業大學 1997 一 （8 分）】（1）在數據結構課程中，數據的邏輯結構，數據的存儲結構及數據的 運算之間存在著怎樣的關

19、系？數據的邏輯結構反映數據元素之間的邏輯關系（即數據元素之間的關 聯方式或“鄰接關系” ），數據的存儲結構是數據結構在計算機中的表示， 包括數據元素的表示及其關系的表示。數據的運算是對數據定義的一組操 作，運算是定義在邏輯結構上的，和存儲結構無關，而運算的實現則是依 賴于存儲結構。（2）若邏輯結構相同但存儲結構不同，則為不同的數據結構。這樣的 說法對嗎？舉例說明之。邏輯結構相同但存儲不同，可以是不同的數據結構。例如，線性表的 邏輯結構屬于線性結構，采用順序存儲結構為順序表，而采用鏈式存儲結 構稱為線性鏈表。（3）在給定的邏輯結構及其存儲表示上可以定義不同的運算集合，從 而得到不同的數據結構。這

20、樣說法對嗎？舉例說明之。棧和隊列的邏輯結構相同，其存儲表示也可相同（順序存儲和鏈式存 儲），但由于其運算集合不同而成為不同的數據結構。（ 4）評價各種不同數據結構的標準是什么？ 數據結構的評價非常復雜，可以考慮兩個方面，一是所選數據結構是否準 確、完整的刻劃了問題的基本特征；二是是否容易實現（如對數據分解是 否恰當； 邏輯結構的選擇是否適合于運算的功能， 是否有利于運算的實現； 基本運算的選擇是否恰當。 ） 5評價一個好的算法，您是從哪幾方面來考慮的？ 評價好的算法有四個方面。一是算法的正確性；二是算法的易讀性；三是 算法的健壯性；四是算法的時空效率（運行） 。【大連海事大學 1996 二、

21、3 （2 分）】【中山大學 1998 三、1 （5 分）】6解釋和比較以下各組概念【華南師范大學 2000 一（ 10 分）】 （ 1）抽象數據類型及數據類型（ 2）數據結構、邏輯結構、存儲結構（3）抽象數據類型【哈爾濱工業大學2000 一、 1（ 3分）】（4）算法的時間復雜性 【河海大學 1998 一、2（3 分）】（5）算法【吉林工業大學 1999 一、1（2 分）】（6）頻度【吉林工業大學 1999 一、2（2 分）】（ 1）見上面題 3 （2）見上面題 4 （3）見上面題 3（ 4）算法的時間復雜性是算法輸入規模的函數。 算法的輸入規模或問題 的規模是作為該算法輸入的數據所含數據元素

22、的數目，或與此數目有關的 其它參數。有時考慮算法在最壞情況下的時間復雜度或平均時間復雜度。（ 5）算法是對特定問題求解步驟的描述， 是指令的有限序列， 其中每一 條指令表示一個或多個操作。算法具有五個重要特性：有窮性、確定性、 可行性、輸入和輸出。（ 6）頻度。在分析算法時間復雜度時， 有時需要估算基本操作的原操作， 它是執行次數最多的一個操作，該操作重復執行的次數稱為頻度。7. 根據數據元素之間的邏輯關系，一般有哪幾類基本的數據結構？ 集合、線性結構、樹形結構、圖形或網狀結構。【北京科技大學 1998 一、 1】【同濟大學 1998 】8對于一個數據結構， 一般包括哪三個方面的討論？ 【北京

23、科技大學 1999 一、 1（2 分）】邏輯結構、存儲結構、操作（運算） 。9. 當你為解決某一問題而選擇數據結構時， 應從哪些方面考慮？ 【西安電 子北京科技大學 2000 】通常考慮算法所需要的存儲空間量和算法所需要的時間量。后者又涉及 到四方面： 程序運行時所需輸入的數據總量， 對源程序進行編譯所需時間， 計算機執行每條指令所需時間和程序中指令重復執行的次數。10. 若將數據結構定義為一個二元組（ D，R）, 說明符號 D，R 應分別表示 什么？【北京科技大學 2001 一、1（2 分）】D是數據元素的有限集合，S是D上數據元素之間關系的有限集合。11數據結構與數據類型有什么區別？ 【哈

24、爾濱工業大學 2001 三、1（ 3 分）】“數據結構”這一術語有兩種含義，一是作為一門課程的名稱；二是作為 一個科學的概念。作為科學概念，目前尚無公認定義，一般認為，討論數 據結構要包括三個方面，一是數據的邏輯結構，二是數據的存儲結構，三 是對數據進行的操作 （運算）。而數據類型是值的集合和操作的集合， 可以 看作是已實現了的數據結構，后者是前者的一種簡化情況。12數據的存儲結構由哪四種基本的存儲方法實現？【山東科技大學 2001一、 1（4 分）】12見上面題 2。13若有 100 個學生，每個學生有學號，姓名，平均成績，采用什么樣的 數據結構最方便，寫出這些結構？【山東師范大學 1996

25、 二、2（2 分）】 將學號、姓名、平均成績看成一個記錄（元素，含三個數據項），將100 個這樣的記錄存于數組中。因一般無增刪操作，故宜采用順序存儲。typedef struct int num;/ 學號char name8;/ 姓名float score;/ 平均成績node ；node student100;14. 運算是數據結構的一個重要方面。試舉一例，說明兩個數據結構的邏 輯結構和存儲方式完全相同，只是對于運算的定義不同。因而兩個結構具 有顯著不同的特性，是兩個不同的結構。【北京大學 1998 一、 1（5 分）】見上面題 4（ 3）。15. 在編制管理通訊錄的程序時 , 什么樣的數據

26、結構合適 ? 為什么 ?【 長 沙鐵道學院 1998 四、3（6 分） 】應從兩方面進行討論： 如通訊錄較少變動 （如城市私人電話號碼） ，主 要用于查詢，以順序存儲較方便，既能順序查找也可隨機查找；若通訊錄 經常有增刪操作，用鏈式存儲結構較為合適，將每個人的情況作為一個元 素（即一個結點存放一個人） ，設姓名作關鍵字， 鏈表安排成有序表， 這樣 可提高查詢速度。16. 試舉一例，說明對相同的邏輯結構 , 同一種運算在不同的存儲方式下實 現，其運算效率不同。【北京理工大學 2000 三、 1（4.5 分）】 線性表中的插入、刪除操作，在順序存儲方式下平均移動近一半的元素，時間復雜度為 0（n）

27、;而在鏈式存儲方式下，插入和刪除時間復雜度 都是 O（ 1）。17. 有實現同一功能的兩個算法A1和A2，其中 A1的時間復雜度為TI=0（2 n），A2的時間復雜度為 T2=O（n2），僅就時間復雜度而言，請具體分 析這兩個算法哪一個好。 【北京航空航天大學 2000 二（10分）】 對算法A1和A2的時間復雜度T1和T2取對數，得nlog2和2log n。顯然， 算法A2好于A1。18設計一數據結構，用來表示某一銀行儲戶的基本信息：賬號、姓名、開戶年月日、儲蓄類型、存入累加數、利息、帳面總數。 【浙江大學 1994 一 、3（5 分）】struct node int year,month,

28、day; ;typedef struct int num;/ 帳號char name8;/ 姓名struct node date;/ 開戶年月日int tag;/ 儲蓄類型，如：0-零存，1- 一年定期float put;/ 存入累加數;float interest;/ 利息float total;/ 帳面總數count ；19. 寫出下面算法中帶標號語句的頻度。TYPE ar=ARRAY1.n OF datatype;PROCEDURE perm ( a: ar; k, n: integer);VAR x: datatype; i:integer;BEGIN(1) IF k=nTHEN BE

29、GIN(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 分)】(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,故第語句執行n次。(2)是FOR循環語句，在滿足(1)的條件下 執行，該語句進入循環體 (3)n

30、次，加上最后一次判斷出界，故執行了 n+1 次。 (4) 也是循環語句,當 k=1 時判斷 n+1 次(進入循環體 (5)n 次), k=2 時判斷n次，最后一次 k=n-1時判斷3次，故執行次數是(n+1) +n+ +3=(n+4)(n-1)/2 次。語句 (5) 是 (4) 的循環體,每次比 (4) 少一次判斷,故 執行次數是 n+(n-1)+ +2=(n+2)(n-1)/2 次。注意分析時, 不要把 (2) 分析 成 n 次,更不是 1 次。20. 分析下面程序段中循環語句的執行次數。i:=0;s:=0;n:=100;REPEATi:=i+1;s:=s+10*i;UNTIL NOT(i&

31、lt;n) AND (s<n);【北京郵電大學 1998 四、1(5 分)】4 (這時 i=4 ， s=100 ) REPEAT 語句先執行循環體，后判斷條件， 直到條件為真時退出循環。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；END Inc ；【東南大

32、學 1998 三 (8 分) 1994 二( 15 分)】 算法在最好情況下，即二進制數的最后一位為零時，只作一次判斷， 未執行循環體， 賦值語句 Ai 執行了一次；最壞情況出現在二進制數各位 均為 1(最高位為零，因題目假設無溢出) ，這時循環體執行了 n-1 次，時 間復雜度是 O(n) ，循環體平均執行 n/2 次，時間復雜度仍是 O(n) 。22. 閱讀下列算法，指出算法 A 的功能和時間復雜性PROCEDURE A (h,g:pointer);(h,g 分別為單循環鏈表( single linked circular list )中 兩個結點指針 )PROCEDURE B(s,q:p

33、ointer) ；VAR p:pointer;BEGINp:=s;WHILE p» next<>q DO p:=pA. next;pin ext:=s;END;(of B)BEGINB(h,g); B(g,h);END;(of A )【東南大學 1999 二( 10分)】該算法功能是將原單循環鏈表分解成兩個單循環鏈表：其一包括結點 h到結點g的前驅結點；另一個包括結點g到結點h的前驅結點。時間復雜度是0(n)。23. 調用下列C函數f(n)或PASACA函數f(n)回答下列問題：(1) 試指出f(n)值的大小，并寫出f(n)值的推導過程；(2) 假定n= 5，試指出f(5

34、)值的大小和執行f(5)時的輸出結果。C 函數：int f(i nt n) 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+;prin tf("sum=%dn",sum)；return (sum);【華中理工大學2000六(10分)】第一層FOR循環判斷n+1次，往下執行n次，第二層FOR執行次數為 (n+(n-1)+(n- 2)+1),第三層循環體受第一層循環和第二層循環的控制， 其執行次數如下表：i=123 nj=nn nn nj=n_1n-1n-1n-1j=333j=222j=11執行次數為(1+2+ +n)+(2+3+ +n)+ +n=n*n(n +1)/2-n(n 2-1)/6。在 n=5時，f(5)=55, 執行過程中，輸出結果為：sum=15,sum=29,sum=41,sum=50,sum=55 (每個 sum