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

1、格式一、選擇題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分）【武漢

2、交通科技大學(xué) 1996 一、 1（4 分）】4一個(gè)算法應(yīng)該是（ B）。【中山大學(xué)1998 二、 1（ 2分）】A程序 B問題求解步驟的描述 C要滿足五個(gè)基本特性 D A 和 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） 的算

3、法在時(shí)間上總是優(yōu)于復(fù)雜度O（2n） 的算法（ 3 ）所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界（ 4 ）同一個(gè)算法，實(shí)現(xiàn)語(yǔ)言的級(jí)別越高，執(zhí)行效率就越低4A （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ù)語(yǔ)是（ D）【。北方交通大學(xué)2000 二、 1（2 分）】A循環(huán)隊(duì)列 B. 鏈表 C.哈希表 D.棧 9以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線性結(jié)構(gòu)（D）？【北方交通大學(xué)

4、 2001一、1（2 分）】A廣義表 B. 二叉樹 C.稀疏矩陣 D.串 10以下那一個(gè)術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)？（ A）【北方交通大學(xué) 2001 一、2（2 分）】A棧 B. 哈希表 C. 線索樹 D.雙向 鏈表11在下面的程序段中，對(duì) x 的賦值語(yǔ)句的頻度為（ C）【北京工商大 學(xué) 2001 一、 10 （ 3 分）】FORi:=1TOnDOFORj:=1TOnDO x:=x+1;AO（2n）B O（n）CO（n2）D O（logn）2）D O（log212程序段 FORi:=n-1DOWNTO1DOFORj:=1TOiDOIFAj>Aj+1THENAj 與 Aj+1 對(duì)換；其中 n

5、 為正整數(shù)，則最后一行的語(yǔ)句頻度在最壞情況下是（D）A.O（ n） B.O（nlogn）C.O（n）D.O（n ） 【南京理工大學(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棧4. 下列數(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一定連

6、續(xù) B一定不連續(xù) C不一定連續(xù) D部分連續(xù)，部分 不連續(xù)17以下屬于邏輯結(jié)構(gòu)的是（ C）?！疚靼搽娮涌萍即髮W(xué)應(yīng)用 2001 一、 1】A順序表 B. 哈希表 C.有序表 D.單鏈表二、判斷題5. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。 （X） 【北京郵電大學(xué) 1998一、 1（ 2分）】【青島大學(xué) 2000一、 1（ 1 分）】【上海交通大學(xué) 1998 一、 1】【山東師范大學(xué) 2001 一、 1（ 2分）】6. 記錄是數(shù)據(jù)處理的最小單位。 （X） 【上海海運(yùn)學(xué)院 1998 一、5（1 分）】7. 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系； （X） 【北京郵 電大學(xué) 2002 一、1（1 分）】 4

7、算法的優(yōu)劣與算法描述語(yǔ)言無關(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算法可以用不同的語(yǔ)言描述，如果用C 語(yǔ)言或 PASCAL語(yǔ)言等高級(jí)語(yǔ)言來描述，則算法實(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 分）】1（1 分）】7. 數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體

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

9、?！狙嗌酱髮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)系的總體參考專業(yè)資料整理格式專業(yè)資料整理學(xué)而 2001 二、1（2 分）】 4邏一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中表示（又稱映像）稱為存儲(chǔ)結(jié)構(gòu)?！救A中理工 大關(guān)輯學(xué) 2000 一、1（1 分）】5系不影響其外部使用。【山東大學(xué) 2001 三、3（2 分）】【元素關(guān)據(jù)北京理工大學(xué)素結(jié)不型間互據(jù)即，之類數(shù)7據(jù).數(shù)據(jù)電子結(jié)科技大學(xué)一構(gòu)是個(gè)算法具有零個(gè)研或多個(gè)輸入、有

10、一個(gè)或多個(gè)輸出。 討【）系”?！繑?shù)據(jù)9它兩，的結(jié)只已要的知它如下程序2001 七、 11998 二、 25 個(gè)特性 :運(yùn)算2 分）】3 分）】1）有窮性（ 2）確定性（ 3）可行性，華中理工大學(xué) 2000 一、 2（ 5分）】【燕山大學(xué) 1998 一、2（5 北京郵電大 的數(shù)學(xué)特性不變， 如，下而程與序在段計(jì)算機(jī)內(nèi) Ri:=nDOWNTO1D輯BEGIN結(jié) 理結(jié)構(gòu)x，:=以x+及1它；們 語(yǔ)之句間的2相FORj:=nDOWNTOiDO語(yǔ) 句 3 y:=y+1; 語(yǔ)句 4 【E西ND；部句如1）的，時(shí)時(shí)設(shè)間算復(fù)法。雜 語(yǔ)句 1 執(zhí)行的頻度 為 n+1；語(yǔ)句 2 執(zhí)行的頻度 為 n ；語(yǔ)句 3 執(zhí)

11、行的頻 間度復(fù)雜度 4為（ 5 分）】（n 1 n+?+（01+2+?+n）=n（n+1）（n+2）/6O（n +（表示在為 n 的函數(shù)） ）3 FOR下i： TOnDOF的ORj： TOiDOFO程Rk： 1TOjDO 序語(yǔ) ： delta ； 句段4句 【中北京工業(yè)大學(xué) 1999 一、6（2 分）】 1執(zhí)2.下，度分面）為】對(duì)n（n+1）/2 【。北方交通大學(xué) 1999 二、 序程 的 i ： =1； WHILEi<nDOi： =i*2;序段 賦 段中 值 中帶參考語(yǔ)帶 度為 1+（ 1+2+（ 1+2+3）格式8. 下面程序段中帶下劃線的語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)是(nlog2n) 。

12、【合肥工業(yè)大學(xué) 2000 三、1(2 分)】i:=1;WHILEi<nBEGINFORj:=1TOnDOx:=x+1;i:=i*2END ；2)13. 下面程序段中帶有下劃線的語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)是 (log2n 【合肥工業(yè)大學(xué) 2001 三、1(2 分)】i： =n*nWHILEi<>1DOi:=idiv2;13. 計(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;14. 下面程序段的時(shí)間復(fù)雜度為 _O(n)

13、。 (n>1)sum=1；for(i=0;sum<n;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)將未完成的部分填入，使之完整intf(m,n)intm,n;if(m=1)return1;if(n=1)return1;if(m<n)returnf(m,m);if(m=n)return1+f(m,n-1

14、);returnf(m.n-1)+f(m-n,n);執(zhí)行程序， f(6,4)=9 。【中科院軟件所 1997 二、1(9 分)】3.在有 n 個(gè)選手參加的單循環(huán)賽中，總共將進(jìn)行n(n-1)/2場(chǎng)比賽。【合肥工業(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é)科。9. 數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有幾種表示方法？各有什么特點(diǎn)？【燕 山大學(xué) 1999 二、2（4 分）】四種表示方法（ 1 ）順序存儲(chǔ)方式。數(shù)據(jù)元素順序存放，

15、每個(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ù)的有限的地址空

16、間內(nèi)，并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的存 儲(chǔ)地址，這種存儲(chǔ)方式稱為散列存儲(chǔ)。其特點(diǎn)是存取速度快，只能按關(guān)鍵 字隨機(jī)存取，不能順序存取，也不能折半存取。10. 數(shù)據(jù)類型和抽象數(shù)據(jù)類型是如何定義的。二者有何相同和不同之處，抽 象數(shù)據(jù)類型的主要特點(diǎn)是什么？使用抽象數(shù)據(jù)類型的主要好處是什么？ 【北京郵電大學(xué) 1994 一（8 分）】數(shù)據(jù)類型是程序設(shè)計(jì)語(yǔ)言中的一個(gè)概念，它是一個(gè)值的集合和操作的 集合。如 C 語(yǔ)言中的整型、實(shí)型、字符型等。整型值的范圍（對(duì)具體機(jī)器 都應(yīng)有整數(shù)范圍），其操作有加、減、乘、除、求余等。實(shí)際上數(shù)據(jù)類型是 廠家提供給用戶的已實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)?！俺橄髷?shù)據(jù)類型（ADT）”指一個(gè)

17、數(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)了一步。11. 回答問題（每題

18、 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)，采用順序存

19、儲(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à)

20、好的算法有四個(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

21、）見上面題 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ù)稱為頻度。12. 根據(jù)數(shù)據(jù)元素之間的邏輯關(guān)系，一般有哪幾類基本的數(shù)據(jù)結(jié)構(gòu)？ 集合、線性結(jié)構(gòu)

22、、樹形結(jié)構(gòu)、圖形或網(wǎng)狀結(jié)構(gòu)?！颈本┛萍即髮W(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)算）。15. 當(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ù)。16. 若將數(shù)據(jù)結(jié)構(gòu)定義為一個(gè)二元組（ D，R）, 說明符號(hào) D， R應(yīng)分別表示 什么？【北京科技大學(xué)

23、 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ù)語(yǔ)有兩種含義，一是作為一門課程的名稱；二是作為 一個(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。1

24、3若有 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ǔ)。 typedefstructintnum;/ 學(xué)號(hào)charname8;/ 姓名參考專業(yè)資料整理格式專業(yè)資料整理floatscore;/ 平均成績(jī)node ；nodestudent100;13.運(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)具 有顯著

25、不同的特性，是兩個(gè)不同的結(jié)構(gòu)?！颈本┐髮W(xué) 1998 一、 1（ 5 分）】 見上面題4（ 3）。14.在 編沙 鐵制 應(yīng) 1管要998 從四、 3（6 分） 】 理經(jīng)用 兩 通常于素 方 訊可查通（有提高面查詢速度。1刪增詢即一，序5時(shí). 試,如通什么樣的數(shù)據(jù)結(jié)構(gòu)合適 ?為什么 ?【長(zhǎng) 舉，一現(xiàn)刪操以個(gè)，其訊運(yùn)算效率不同。一順作結(jié)例序，點(diǎn)用，存儲(chǔ)素放鏈說，時(shí)市性間復(fù)雜度為 O（ n）；而在鏈?zhǔn)酱鎯?chǔ)方式下，插入和刪除時(shí)間復(fù)雜度 是中私表人O（ 1）。6.有實(shí)的電現(xiàn)同一功能的兩個(gè)算法結(jié)1序一刪，5式較一【如（北京理工大學(xué) 2000 三、1（ 4.5 分）】 線城，主A1和 A2，其中 A1 的時(shí)間

26、復(fù)雜度為,，n同主一種運(yùn)算在不同的存儲(chǔ)方式下實(shí) 為姓能較設(shè)析順這兩、刪個(gè)）算法哪一個(gè)好。【北京航空航天大學(xué) 名序合對(duì) 除 算適查作 操 算找，法鏈表作A安2好排于成有A序1。表，這樣在3順序一（個(gè)5元分）】 存structnode 儲(chǔ) 方 intyear,month,day; 式下 typedefstruct 平 intnum;/ 帳號(hào)charname8;/ 姓名 structnodedate;/ 開戶年月日 inttag;/ 儲(chǔ)蓄類型，如：0- 零存， floatput;/ 存入累加數(shù)；個(gè)通一戶訊、錄 一設(shè)年況戶作、為 月計(jì) 日一 、數(shù) 儲(chǔ)據(jù) 蓄 蓄結(jié) 類構(gòu)均 的元、用 存來 入表 累示 加

27、某 數(shù)一參考 、銀參考 利行 息儲(chǔ) 、賬號(hào)、姓名、 數(shù)。【浙江大學(xué) 19942000 二（ 10 分）】2 和 2log n 。1- 一年定期 ?顯然，格式floatinterest;/ 利息 floattotal;/ 帳面總數(shù) count ；17.寫 出 下 面 算 法 中 帶 標(biāo) 號(hào) 語(yǔ)TYPEar=ARRAY1.nOFdatatype;PROCEDUREperm(a:ar;k,n:integer);VARx:datatype;i:integer;BEGIN( 1) IFk=nTHENBEGIN(2) FORi:=1TOnDO(3) write(ai);writeln;ENDELSEBEG

28、IN( 4) FORi:=kTOnDO(5) ai:=ai+i*i;( 6 ) perm(a,k+1,n);END;END;設(shè)k 的初值等于1句環(huán)次專業(yè)資料整理增1執(zhí)次，行【北京郵電大學(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這是。，時(shí)故判斷遞n次，最后一次 k=n-1 時(shí)判斷 3 次， (+第該k)(413執(zhí)句語(yǔ)行次1的數(shù)是 n+(n-1)+ ?+2=(n+2)(n-1)/2 句()=進(jìn)成也 n 次，更不是 1 次。 (由 n語(yǔ)是入由+循句語(yǔ)14+執(zhí)環(huán)8.分析句下面程序段中循環(huán)語(yǔ)句的執(zhí)行次數(shù)。)4語(yǔ)行體()

29、kn=1 時(shí)6判斷(3n次)-)n。知故執(zhí)行次數(shù)是( n+1) +n+?注意分析時(shí)，不要把 (2) 分析n+1次iR:=E(0P;進(jìn)sE:=A入0T循; n:環(huán)=1體00; (5)n 次)，k=2i:=i+1;每 參考k格式s:=s+10*i;UNTILNOT(i<n)AND(s<n);【北京郵電大學(xué) 1998 四、1(5 分)】4(這時(shí) i=4 ， s=100) REPEAT語(yǔ)句先執(zhí)行循環(huán)體，后判斷條件， 直到條件為真時(shí)退出循環(huán)。21 下列算法對(duì)一 n 位二進(jìn)制數(shù)加 1，假如無溢出，該算法的最壞時(shí)間復(fù) 雜性是什么？并分析它的平均時(shí)間復(fù)雜性。TYPEnum=ARRAY1.nof0.

30、1 ；PROCEDUREIn(c VARa： num)；VARi： integer ；BEGINi： =n；WHILEAi=1DOBEGINAi ： =0；i ：=i-1 ； END；END；Ai ： =1；ENDInc；【東南大學(xué) 1998 三(8 分)1994 二(15 分)】 算法在最好情況下，即二進(jìn)制數(shù)的最后一位為零時(shí)，只作一次判斷， 未執(zhí)行循環(huán)體，賦值語(yǔ)句 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) 。 19.閱讀下列算法，指出算法

31、A 的功能和時(shí)間復(fù)雜性PROCEDUREA(h,g:pointer);(h,g 分別為單循環(huán)鏈表( singlelinkedcircularlist )中 兩個(gè)結(jié)點(diǎn)指針 )PROCEDUREB(s,q:pointer) ；VARp:pointer;BEGINp:=s;WHILEp.next<>qDOp:=p.next;p.next:=s;END;(ofB)BEGINB(h,g);B(g,h);END;( ofA )【東南大學(xué) 1999 二(10 分)】參考h 到雜度是算該O(n) 。 2結(jié)0.調(diào)法 用( 功結(jié)出數(shù)點(diǎn)f點(diǎn)n另結(jié)或值點(diǎn)P或的 A大 S小 A，C并A寫2)能假定 n=5，

32、試指出 f(5) 值的大小和執(zhí)行 f(5) 時(shí)的輸出結(jié)果。 是將 C 函數(shù)： intf(intn) 原單循環(huán)鏈表分inti,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+) 解g 到結(jié)點(diǎn) h 的前驅(qū)結(jié)點(diǎn)。時(shí)su間m復(fù)+; 成 兩 個(gè) 單 循 環(huán)第表printf("sum=%dn",sum) ；return(sum);【華中理2000 六( 10 分)】執(zhí)行層其次數(shù)如下表：F結(jié)i=點(diǎn)123 ?nORj=nnnn ?n循j=n-1n-1n-1n-1n+1次，往下執(zhí)行 n 次，第

33、二層 FOR執(zhí)行次數(shù)為 ?j=333 j=222 j=11答(+題:n2-1)/6 。在 n=5)2執(zhí)行次數(shù)為 (1+2+ ?+n)+(2+3+ ?+n)+ ?+n=n*n(n+1)/2-n(n+時(shí)s?，um=15,sum=29,sum=41,sum=50,sum=55 (每個(gè) sum=占一行 , 為節(jié)省篇幅， f(1+這里省去換行)。)5)2=第，4設(shè)n是偶數(shù)，試計(jì)算運(yùn)行下列程序段 后 m的值并給出該程序段的時(shí)間 5復(fù)三雜度。5層m:=0;程環(huán)中，輸出結(jié)FO果R為i:=：1TOnDO 體 FORj:=2*iTOnDO第 m:=m+1;專業(yè)資料整理考參 層循環(huán)和第二層【南京郵電大學(xué)2000 一、 1】O(n2),m 的值等于賦值 語(yǔ)句 m:=m+1的運(yùn)行次數(shù)，其計(jì)算式為n2/1i( n2i1)25