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

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