數(shù)據(jù)結(jié)構(gòu)考研真題及其答案.doc

一、選擇題1. 算法的計算量的大小稱為計算的（ B ）?！颈本┼]電大學2000 二、3 （20/8分）】A效率 B. 復(fù)雜性 C. 現(xiàn)實性 D. 難度2. 算法的時間復(fù)雜度取決于（C ）【中科院計算所 1998 二、1 （2分）】A問題的規(guī)模 B. 待處理數(shù)據(jù)的初態(tài) C. A和B3.計算機算法指的是（C），它必須具備（B） 這三個特性。(1) A計算方法 B. 排序方法 C. 解決問題的步驟序列 D. 調(diào)度方法(2) A可執(zhí)行性、可移植性、可擴充性 B. 可執(zhí)行性、確定性、有窮性C. 確定性、有窮性、穩(wěn)定性 D. 易讀性、穩(wěn)定性、安全性 【南京理工大學 1999 一、1（2分） 【武漢交通科技大學 1996 一、1（ 4分）】4一個算法應(yīng)該是（ B ）。【中山大學 1998 二、1（2分）】 A程序 B問題求解步驟的描述 C要滿足五個基本特性 DA和C. 5. 下面關(guān)于算法說法錯誤的是（ D ）【南京理工大學 2000 一、1（1.5分）】A算法最終必須由計算機程序?qū)崿F(xiàn)B.為解決某問題的算法同為該問題編寫的程序含義是相同的C. 算法的可行性是指指令不能有二義性 D. 以上幾個都是錯誤的6. 下面說法錯誤的是（ C ）【南京理工大學 2000 一、2 （1.5分）】 (1）算法原地工作的含義是指不需要任何額外的輔助空間 （2）在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時間上總是優(yōu)于復(fù)雜度O(2n)的算法 （3）所謂時間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界 （4）同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低4 A(1) B.(1),(2) C.(1),(4) D.(3)7從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ C ）兩大類。【武漢交通科技大學 1996 一 、4（2分）】A動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B順序結(jié)構(gòu)、鏈式結(jié)構(gòu) C線性結(jié)構(gòu)、非線性結(jié)構(gòu) D初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)8以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（ D ）?！颈狈浇煌ù髮W 2000 二、1（2分）】A循環(huán)隊列 B. 鏈表 C. 哈希表 D. 棧9以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)（ D ）？【北方交通大學 2001 一、1（2分）】A廣義表 B. 二叉樹 C. 稀疏矩陣 D. 串10以下那一個術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)？（ A ）【北方交通大學 2001 一、2（2分）】A棧 B. 哈希表 C. 線索樹 D. 雙向鏈表11在下面的程序段中，對x的賦值語句的頻度為（C ）【北京工商大學 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ù)，則最后一行的語句頻度在最壞情況下是（ D ）A. O（n） B. O(nlogn) C. O(n3) D. O(n2) 【南京理工大學1998一、1(2分)】13以下哪個數(shù)據(jù)結(jié)構(gòu)不是多型數(shù)據(jù)類型（ D ）【中山大學 1999 一、3（1分）】A棧 B廣義表 C有向圖 D字符串14以下數(shù)據(jù)結(jié)構(gòu)中，（ A ）是非線性數(shù)據(jù)結(jié)構(gòu)【中山大學 1999 一、4】A樹 B字符串 C隊 D棧15. 下列數(shù)據(jù)中，（ C）是非線性數(shù)據(jù)結(jié)構(gòu)?！颈本├砉ご髮W 2001 六、1（2分）】A棧 B. 隊列 C. 完全二叉樹 D. 堆16連續(xù)存儲設(shè)計時，存儲單元的地址（ A ）?！局猩酱髮W 1999 一、1（1分）】A一定連續(xù) B一定不連續(xù) C不一定連續(xù) D部分連續(xù)，部分不連續(xù)17以下屬于邏輯結(jié)構(gòu)的是（ C ）。【西安電子科技大學應(yīng)用 2001一、1】A順序表 B. 哈希表 C.有序表 D. 單鏈表二、判斷題1. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。( X )【北京郵電大學 1998 一、1（2分）】【青島大學 2000 一、1 （1分）】【上海交通大學 1998 一、1】 【山東師范大學 2001 一、1 （2分）】2. 記錄是數(shù)據(jù)處理的最小單位。 ( X ) 【上海海運學院 1998 一、5（1分）】3. 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關(guān)系；( X )【北京郵電大學2002 一、1（1分）】4算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計算機有關(guān)。( X )【大連海事大學 2001 一、10（1分）】5健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。( O )【大連海事大學 2001 一、11（1分）】6算法可以用不同的語言描述，如果用C 語言或PASCAL語言等高級語言來描述，則算法實際上就是程序了。( X )【西安交通大學 1996 二、7（3分）】7程序一定是算法。( X )【燕山大學 1998 二、2（2分）并改錯】8數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。( O )【山東師范大學2001 一、2（2分）】9. 數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實現(xiàn)有關(guān)。( X )【華南理工大學 2002 一、1（1分）】10. 在順序存儲結(jié)構(gòu)中，有時也存儲數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。( X )【華南理工大學 2002 一、2 （1分）】11. 順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。( X )【上海海運學院 1999 一、1（1分）】12. 數(shù)據(jù)結(jié)構(gòu)的基本操作的設(shè)置的最重要的準則是，實現(xiàn)應(yīng)用程序與存儲結(jié)構(gòu)的獨立。( O )【華南理工大學 2002 一、5（1分）】13. 數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的順序關(guān)系,它依賴于計算機的儲存結(jié)構(gòu). ( X )【上海海運學院 1998 一、1（1分）】三、填空1數(shù)據(jù)的物理結(jié)構(gòu)包括數(shù)據(jù)元素的表示和數(shù)據(jù)元素間關(guān)系的表示。【燕山大學 1998 一、1（2分）】2. 對于給定的n個元素,可以構(gòu)造出的邏輯結(jié)構(gòu)有集合 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 圖狀結(jié)構(gòu)(或網(wǎng)狀結(jié)構(gòu))四種?！局锌圃河嬎闼?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)系”?！颈本┼]電大學 2001 二、1（2分）】4一個數(shù)據(jù)結(jié)構(gòu)在計算機中表示（又稱映像）稱為存儲結(jié)構(gòu)。【華中理工大學 2000 一、1（1分）】5抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與在計算機內(nèi)部如何表示和實現(xiàn)無關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學特性不變，都不影響其外部使用?！旧綎|大學 2001 三、3（2分）】6數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標是算法的時間復(fù)雜度和空間復(fù)雜度【北京理工大學 2001 七、1（2分）】7. 數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的_邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，以及它們之間的相互關(guān)系，并對與這種結(jié)構(gòu)定義相應(yīng)的操作（運算），設(shè)計出相應(yīng)的算法?！疚靼搽娮涌萍即髮W 1998 二、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í)行的頻度為 n+1 ；語句2執(zhí)行的頻度為n；語句3執(zhí)行的頻度為n(n+3)/2；語句4執(zhí)行的頻度為n(n+1)/2?！颈狈浇煌ù髮W 1999 二、4（5分）】10在下面的程序段中，對的賦值語句的頻度為1+（1+2+（1+2+3）+（1+2+n）=n(n+1)(n+2)/6 O(n3)（表示為n的函數(shù)） FORi： TO nDOFORj：TO iDOFORk：1TOjDO：delta；【北京工業(yè)大學 1999 一、6（2分）】11.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是：log2n【合肥工業(yè)大學1999三、1（2分）】i：=1； WHILE in DO i：=i*2;12. 下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是( nlog2n )?！竞戏使I(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ù)量級是(log2n2 ) 【合肥工業(yè)大學 2001 三、1（2分）】i：=n*n WHILE i1 DO i:=i div 2;14. 計算機執(zhí)行下面的語句時，語句s的執(zhí)行次數(shù)為 (n+3)(n-2)/2 。【南京理工大學2000二、1（1.5分）】 FOR(i=l；i=i;j-) s; 15. 下面程序段的時間復(fù)雜度為_ O(n)_。(n1) sum=1； for (i=0;sumn;i+) sum+=1; 【南京理工大學 2001 二、1（2分）】16設(shè)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) return 1;if(n=1) return 1;if(mn) 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。 【中科院軟件所 1997 二、1 （9分）】17. 在有n個選手參加的單循環(huán)賽中，總共將進行n(n-1)/2場比賽?！竞戏使I(yè)大學1999三、8（2分）】四、應(yīng)用題1. 數(shù)據(jù)結(jié)構(gòu)是一門研究什么內(nèi)容的學科？【燕山大學 1999 二、1 （4分）】數(shù)據(jù)結(jié)構(gòu)是一門研究在非數(shù)值計算的程序設(shè)計問題中，計算機的操作對象及對象間的關(guān)系和施加于對象的操作等的學科。2. 數(shù)據(jù)元素之間的關(guān)系在計算機中有幾種表示方法？各有什么特點？【燕山大學1999 二、2（4分）】四種表示方法（1）順序存儲方式。數(shù)據(jù)元素順序存放，每個存儲結(jié)點只含一個元素。存儲位置反映數(shù)據(jù)元素間的邏輯關(guān)系。存儲密度大，但有些操作（如插入、刪除）效率較差。（2）鏈式存儲方式。每個存儲結(jié)點除包含數(shù)據(jù)元素信息外還包含一組（至少一個）指針。指針反映數(shù)據(jù)元素間的邏輯關(guān)系。這種方式不要求存儲空間連續(xù)，便于動態(tài)操作（如插入、刪除等），但存儲空間開銷大（用于指針），另外不能折半查找等。（3）索引存儲方式。除數(shù)據(jù)元素存儲在一地址連續(xù)的內(nèi)存空間外，尚需建立一個索引表，索引表中索引指示存儲結(jié)點的存儲位置（下標）或存儲區(qū)間端點（下標），兼有靜態(tài)和動態(tài)特性。（4）散列存儲方式。通過散列函數(shù)和解決沖突的方法，將關(guān)鍵字散列在連續(xù)的有限的地址空間內(nèi)，并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的存儲地址，這種存儲方式稱為散列存儲。其特點是存取速度快，只能按關(guān)鍵字隨機存取，不能順序存取，也不能折半存取。3. 數(shù)據(jù)類型和抽象數(shù)據(jù)類型是如何定義的。二者有何相同和不同之處，抽象數(shù)據(jù)類型的主要特點是什么？使用抽象數(shù)據(jù)類型的主要好處是什么？【北京郵電大學 1994 一（8分）】數(shù)據(jù)類型是程序設(shè)計語言中的一個概念，它是一個值的集合和操作的集合。如C語言中的整型、實型、字符型等。整型值的范圍（對具體機器都應(yīng)有整數(shù)范圍），其操作有加、減、乘、除、求余等。實際上數(shù)據(jù)類型是廠家提供給用戶的已實現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)。“抽象數(shù)據(jù)類型（ADT）”指一個數(shù)學模型及定義在該模型上的一組操作?！俺橄蟆钡囊饬x在于數(shù)據(jù)類型的數(shù)學抽象特性。抽象數(shù)據(jù)類型的定義僅取決于它的邏輯特性，而與其在計算機內(nèi)部如何表示和實現(xiàn)無關(guān)。無論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學特性不變就不影響它的外部使用。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實質(zhì)上是一個概念。此外，抽象數(shù)據(jù)類型的范圍更廣，它已不再局限于機器已定義和實現(xiàn)的數(shù)據(jù)類型，還包括用戶在設(shè)計軟件系統(tǒng)時自行定義的數(shù)據(jù)類型。使用抽象數(shù)據(jù)類型定義的軟件模塊含定義、表示和實現(xiàn)三部分，封裝在一起，對用戶透明（提供接口），而不必了解實現(xiàn)細節(jié)。抽象數(shù)據(jù)類型的出現(xiàn)使程序設(shè)計不再是“藝術(shù)”，而是向“科學”邁進了一步。4. 回答問題（每題2分）【山東工業(yè)大學 1997 一 （8分）】（1）在數(shù)據(jù)結(jié)構(gòu)課程中，數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲結(jié)構(gòu)及數(shù)據(jù)的運算之間存在著怎樣的關(guān)系？數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系（即數(shù)據(jù)元素之間的關(guān)聯(lián)方式或“鄰接關(guān)系”），數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計算機中的表示，包括數(shù)據(jù)元素的表示及其關(guān)系的表示。數(shù)據(jù)的運算是對數(shù)據(jù)定義的一組操作，運算是定義在邏輯結(jié)構(gòu)上的，和存儲結(jié)構(gòu)無關(guān)，而運算的實現(xiàn)則是依賴于存儲結(jié)構(gòu)。（2）若邏輯結(jié)構(gòu)相同但存儲結(jié)構(gòu)不同，則為不同的數(shù)據(jù)結(jié)構(gòu)。這樣的說法對嗎？舉例說明之。邏輯結(jié)構(gòu)相同但存儲不同，可以是不同的數(shù)據(jù)結(jié)構(gòu)。例如，線性表的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，采用順序存儲結(jié)構(gòu)為順序表，而采用鏈式存儲結(jié)構(gòu)稱為線性鏈表。（3）在給定的邏輯結(jié)構(gòu)及其存儲表示上可以定義不同的運算集合，從而得到不同的數(shù)據(jù)結(jié)構(gòu)。這樣說法對嗎？舉例說明之。棧和隊列的邏輯結(jié)構(gòu)相同，其存儲表示也可相同（順序存儲和鏈式存儲），但由于其運算集合不同而成為不同的數(shù)據(jù)結(jié)構(gòu)。（4）評價各種不同數(shù)據(jù)結(jié)構(gòu)的標準是什么？數(shù)據(jù)結(jié)構(gòu)的評價非常復(fù)雜，可以考慮兩個方面，一是所選數(shù)據(jù)結(jié)構(gòu)是否準確、完整的刻劃了問題的基本特征；二是是否容易實現(xiàn)（如對數(shù)據(jù)分解是否恰當；邏輯結(jié)構(gòu)的選擇是否適合于運算的功能，是否有利于運算的實現(xiàn)；基本運算的選擇是否恰當。）5評價一個好的算法，您是從哪幾方面來考慮的？評價好的算法有四個方面。一是算法的正確性；二是算法的易讀性；三是算法的健壯性；四是算法的時空效率（運行）?！敬筮B海事大學 1996 二、3 （2分）】【中山大學 1998 三、1 （5分）】6解釋和比較以下各組概念【華南師范大學 2000 一（10分）】（1）抽象數(shù)據(jù)類型及數(shù)據(jù)類型 （2）數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)（3）抽象數(shù)據(jù)類型【哈爾濱工業(yè)大學 2000 一、1（3分）】（4）算法的時間復(fù)雜性 【河海大學 1998 一、2（3分）】（5）算法【吉林工業(yè)大學1999 一、1（2分）】（6）頻度【吉林工業(yè)大學 1999 一、2（2分）】（1）見上面題3 （2）見上面題4 （3）見上面題3 （4）算法的時間復(fù)雜性是算法輸入規(guī)模的函數(shù)。算法的輸入規(guī)?；騿栴}的規(guī)模是作為該算法輸入的數(shù)據(jù)所含數(shù)據(jù)元素的數(shù)目，或與此數(shù)目有關(guān)的其它參數(shù)。有時考慮算法在最壞情況下的時間復(fù)雜度或平均時間復(fù)雜度。 （5）算法是對特定問題求解步驟的描述，是指令的有限序列，其中每一條指令表示一個或多個操作。算法具有五個重要特性：有窮性、確定性、可行性、輸入和輸出。 （6）頻度。在分析算法時間復(fù)雜度時，有時需要估算基本操作的原操作，它是執(zhí)行次數(shù)最多的一個操作，該操作重復(fù)執(zhí)行的次數(shù)稱為頻度。7. 根據(jù)數(shù)據(jù)元素之間的邏輯關(guān)系，一般有哪幾類基本的數(shù)據(jù)結(jié)構(gòu)？集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形或網(wǎng)狀結(jié)構(gòu)。 【北京科技大學 1998 一、1】【同濟大學 1998】8對于一個數(shù)據(jù)結(jié)構(gòu)，一般包括哪三個方面的討論？【北京科技大學 1999 一、1（2分）】邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、操作（運算）。9. 當你為解決某一問題而選擇數(shù)據(jù)結(jié)構(gòu)時，應(yīng)從哪些方面考慮？【西安電子北京科技大學 2000】通?？紤]算法所需要的存儲空間量和算法所需要的時間量。后者又涉及到四方面：程序運行時所需輸入的數(shù)據(jù)總量，對源程序進行編譯所需時間，計算機執(zhí)行每條指令所需時間和程序中指令重復(fù)執(zhí)行的次數(shù)。10. 若將數(shù)據(jù)結(jié)構(gòu)定義為一個二元組（D，R）,說明符號D，R 應(yīng)分別表示什么？【北京科技大學 2001 一、1（2分）】D是數(shù)據(jù)元素的有限集合，S是D上數(shù)據(jù)元素之間關(guān)系的有限集合。11數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型有什么區(qū)別？【哈爾濱工業(yè)大學 2001 三、1（3分）】“數(shù)據(jù)結(jié)構(gòu)”這一術(shù)語有兩種含義，一是作為一門課程的名稱；二是作為一個科學的概念。作為科學概念，目前尚無公認定義，一般認為，討論數(shù)據(jù)結(jié)構(gòu)要包括三個方面，一是數(shù)據(jù)的邏輯結(jié)構(gòu)，二是數(shù)據(jù)的存儲結(jié)構(gòu)，三是對數(shù)據(jù)進行的操作（運算）。而數(shù)據(jù)類型是值的集合和操作的集合，可以看作是已實現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)，后者是前者的一種簡化情況。12數(shù)據(jù)的存儲結(jié)構(gòu)由哪四種基本的存儲方法實現(xiàn)？【山東科技大學 2001 一、1（4分）】 12見上面題2。13若有100個學生，每個學生有學號，姓名，平均成績，采用什么樣的數(shù)據(jù)結(jié)構(gòu)最方便，寫出這些結(jié)構(gòu)？【山東師范大學 1996 二、2（2分）】將學號、姓名、平均成績看成一個記錄（元素，含三個數(shù)據(jù)項），將100個這樣的記錄存于數(shù)組中。因一般無增刪操作，故宜采用順序存儲。 typedef struct int num;/學號 char name8;/姓名 float score;/平均成績 node； node student100;14. 運算是數(shù)據(jù)結(jié)構(gòu)的一個重要方面。試舉一例，說明兩個數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲方式完全相同，只是對于運算的定義不同。因而兩個結(jié)構(gòu)具有顯著不同的特性，是兩個不同的結(jié)構(gòu)。【北京大學 1998一、1（5分）】見上面題4（3）。15. 在編制管理通訊錄的程序時, 什么樣的數(shù)據(jù)結(jié)構(gòu)合適? 為什么?【 長沙鐵道學院1998四、3(6分)】應(yīng)從兩方面進行討論：如通訊錄較少變動（如城市私人電話號碼），主要用于查詢，以順序存儲較方便，既能順序查找也可隨機查找；若通訊錄經(jīng)常有增刪操作，用鏈式存儲結(jié)構(gòu)較為合適，將每個人的情況作為一個元素（即一個結(jié)點存放一個人），設(shè)姓名作關(guān)鍵字，鏈表安排成有序表，這樣可提高查詢速度。16. 試舉一例，說明對相同的邏輯結(jié)構(gòu),同一種運算在不同的存儲方式下實現(xiàn)，其運算效率不同。【北京理工大學 2000 三、1（4.5分）】線性表中的插入、刪除操作，在順序存儲方式下平均移動近一半的元素，時間復(fù)雜度為O（n）；而在鏈式存儲方式下，插入和刪除時間復(fù)雜度都是O（1）。17. 有實現(xiàn)同一功能的兩個算法A1和A2，其中A1的時間復(fù)雜度為Tl=O(2n)，A2的時間復(fù)雜度為T2=O(n2)，僅就時間復(fù)雜度而言，請具體分析這兩個算法哪一個好?！颈本┖娇蘸教齑髮W 2000 二（10分）】對算法A1和A2的時間復(fù)雜度T1和T2取對數(shù)，得nlog2和2logn。顯然，算法A2好于A1。18設(shè)計一數(shù)據(jù)結(jié)構(gòu)，用來表示某一銀行儲戶的基本信息： 賬號、姓名、開戶年月日、儲蓄類型、存入累加數(shù)、利息、帳面總數(shù)?！菊憬髮W 1994 一 、3（5分）】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. 寫出下面算法中帶標號語句的頻度。 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; END ELSE BEGIN （4） FOR i:=k TO n DO （5）ai:=ai+i*i; （6） perm (a, k+1, n); END; END;設(shè)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 這是一個遞歸調(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=2時判斷n次，最后一次k=n-1時判斷3次，故執(zhí)行次數(shù)是（n+1）+n+3=(n+4)(n-1)/2次。語句(5)是(4)的循環(huán)體，每次比(4)少一次判斷，故執(zhí)行次數(shù)是n+(n-1)+2=(n+2)(n-1)/2次。注意分析時，不要把(2)分析成n次，更不是1次。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分）】4 （這時i=4， s=100） REPEAT語句先執(zhí)行循環(huán)體，后判斷條件，直到條件為真時退出循環(huán)。21下列算法對一n位二進制數(shù)加1，假如無溢出，該算法的最壞時間復(fù)雜性是什么？并分析它的平均時間復(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；END Inc；【東南大學1998 三 (8分) 1994 二（15分）】算法在最好情況下，即二進制數(shù)的最后一位為零時，只作一次判斷，未執(zhí)行循環(huán)體，賦值語句Ai執(zhí)行了一次；最壞情況出現(xiàn)在二進制數(shù)各位均為1（最高位為零，因題目假設(shè)無溢出），這時循環(huán)體執(zhí)行了n-1次，時間復(fù)雜度是O(n)，循環(huán)體平均執(zhí)行n/2次，時間復(fù)雜度仍是O(n)。22. 閱讀下列算法，指出算法A的功能和時間復(fù)雜性 PROCEDURE A (h,g:pointer);(h,g分別為單循環(huán)鏈表（single linked circular list）中兩個結(jié)點指針)PROCEDURE B(s,q:pointer)； VAR p:pointer; BEGIN p:=s; WHILE p.nextq DO p:=p.next; p.next:=s; END;(of B)BEGINB(h,g); B(g,h);END;（of A）【東南大學 1999 二（10分）】該算法功能是將原單循環(huán)鏈表分解成兩個單循環(huán)鏈表：其一包括結(jié)點h到結(jié)點g的前驅(qū)結(jié)點；另一個包括結(jié)點g到結(jié)點h的前驅(qū)結(jié)點。時間復(fù)雜度是O(n)。23. 調(diào)用下列C函數(shù)f(n)或PASACAL函數(shù)f(n) 回答下列問題 :（1） 試指出f(n)值的大小，并寫出f(n) 值的推導過程;（2） 假定n= 5，試指出f(5)值的大小和執(zhí)行f(5)時的輸出結(jié)果 。 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); 【華中理工大學 2000 六（10分）】第一層FOR循環(huán)判斷n+1次，往下執(zhí)行n次，第二層FOR執(zhí)行次數(shù)為(n+(n-1)+(n-2)+1)，第三層循環(huán)體受第一層循環(huán)和第二層循環(huán)的控制，其執(zhí)行次數(shù)如下表： i= 1 2 3 n j=n n n n n j=n-1 n-1 n-1 n-1 j=3 3 3j=2 2 2j=1 1執(zhí)行次數(shù)為(1+2+n)+(2+3+n)+n=n*n(n+1)/2-n(n2-1)/6。在n=5時，f(5)=55，執(zhí)行過程中，輸出結(jié)果為：sum=15,sum=29,sum=41,sum=50,sum=55（每個sum=