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

1、選擇題1. 算法的計(jì)算量的大小稱(chēng)為計(jì)算的 （ B ）?！颈本┼]電大學(xué) 2000 二、3（ 20/8 分）】A. 效率B.復(fù)雜性 C. 現(xiàn)實(shí)性 D.難度2. 算法的時(shí)間復(fù)雜度取決于（ C ）【中科院計(jì)算所 1998 二、 1 （2 分）】A.問(wèn)題的規(guī)模B.待處理數(shù)據(jù)的初態(tài)C.A 和 B3. 計(jì)算機(jī)算法指的是（C），它必須具備（ B）這三個(gè)特性。（1） A .計(jì)算方法B.排序方法C.解決問(wèn)題的步驟序列D.調(diào)度方法（2） A .可執(zhí)行性、可移植性、可擴(kuò)充性B .可執(zhí)行性、確定性、有窮性C. 確定性、有窮性、穩(wěn)定性D.易讀性、穩(wěn)定性、安全性【南京理工大學(xué)1999一、 1（ 2 分） 【武漢交通科技大學(xué)

2、 1996 一、 1（4 分）】4.一個(gè)算法應(yīng)該是（B）?！局猩酱髮W(xué)1998二、 1（ 2 分）】A .程序 B. 問(wèn)題求解步驟的描述C.要滿足五個(gè)基本特性D.A 和 C.5. 下面關(guān)于算法說(shuō)法錯(cuò)誤的是（ D ）【南京理工大學(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ò)誤的是（ C ）【南京理工大學(xué) 2000 一、 2 （1.5 分）】 （1 ）算法原地工作的含義是指不需要任何額外的輔助空間（2）在相同的規(guī)模n下，復(fù)雜度0（n）的算法在時(shí)

3、間上總是優(yōu)于復(fù)雜度 0（2） 的算法3）所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界4） 同一個(gè)算法，實(shí)現(xiàn)語(yǔ)言的級(jí)別越高，執(zhí)行效率就越低4A . （1）B.（1）,（2） C.7. 從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為 （ 一 、 4（ 2 分）】A.動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)BC. 線性結(jié)構(gòu)、非線性結(jié)構(gòu) D（1）,（4）D.（3）C ）兩大類(lèi)。 【武漢交通科技大學(xué) 1996.順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu) .初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)8 以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)的術(shù)語(yǔ)是 （D ）?！颈狈浇煌ù髮W(xué)2000 二、1（2 分）】A.循環(huán)隊(duì)列B.鏈表C.哈希表D.棧9以下數(shù)據(jù)結(jié)構(gòu)中， 哪一個(gè)是線性結(jié)構(gòu) （D）？【北方交通大

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

5、最后一行的語(yǔ)句頻度在最壞情況下是（ 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ù)類(lèi)型（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.樹(shù)B字符串C隊(duì)D 棧15. 下列數(shù)據(jù)中，（ C ）是非線性數(shù)據(jù)結(jié)構(gòu)?！颈本├砉ご髮W(xué) 2001 六、 1 （ 2 分）】A.棧 B.隊(duì)列 C.完全二叉樹(shù) D. 堆16連續(xù)存儲(chǔ)設(shè)計(jì)時(shí)，存儲(chǔ)單元的地址（ 1 分）】A. 定連續(xù) B 一定不

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

7、法描述語(yǔ)言無(wú)關(guān)，但與所用計(jì)算機(jī)有關(guān)?！敬筮B海事大學(xué) 2001 一、 10 （ 1 分）】5 健壯的算法不會(huì)因非法的輸入數(shù)據(jù)而岀現(xiàn)莫名其妙的狀態(tài)?！敬筮B海事大學(xué) 2001 一、 11 （ 1 分）】6 算法可以用不同的語(yǔ)言描述，如果用 C語(yǔ)言或PASCAL語(yǔ)言等高級(jí)語(yǔ)言來(lái)描述， 則算法實(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ǔ)形式。（0）【山東師范大學(xué) 2001 一、 2（ 2 分）】9. 數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實(shí)現(xiàn)有關(guān)。 （ X ） 【華

8、南理工大學(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ú)立。（0）【華南理工大學(xué) 2002 一、 5（ 1 分）】13. 數(shù)據(jù)的邏輯結(jié)構(gòu)說(shuō)明數(shù)據(jù)元素之間的順序關(guān)系 ,它依賴(lài)于計(jì)算機(jī)的儲(chǔ)存結(jié)構(gòu) . （ X ）【上海海運(yùn)學(xué)院 1998 一、 1 （ 1 分）】三、填空1 數(shù)據(jù)的物理結(jié)構(gòu)包括 數(shù)據(jù)元

9、素 的表示和 數(shù)據(jù)元素間關(guān)系 的表示。【燕山大 學(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)狀結(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)方式或稱(chēng)“鄰接關(guān)系”?！颈本┼]電大學(xué)2001 二、1（ 2 分）】4 一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中 表示（又稱(chēng)映像）稱(chēng)為存儲(chǔ)結(jié)構(gòu)。【華中理工大 學(xué) 2000 一、1 （1 分）】5 抽象數(shù)據(jù)類(lèi)型的定義僅取決于它的一組邏輯特性，而與在計(jì)算機(jī)內(nèi)部如何表示和

10、實(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)算），設(shè)計(jì)岀相應(yīng)的算法。【西安電子科技大學(xué)1998二、2 （3分）】8 一個(gè)算法具有5個(gè)特性：（1）有窮性（2）確定性（3）可行性，有零個(gè)或多個(gè)輸入、有一個(gè)或多個(gè)輸出。【華中理工大學(xué) 2000 一、2 （5分）】【燕山大學(xué)1998 一、2 （ 5分）】9已知如下程序段F

11、OR i:= n DOWNTO 1DO語(yǔ)句1BEGINx:=x+1 ；語(yǔ)句2FOR j:=n DOWNTOi DO語(yǔ)句3y:=y+1;語(yǔ)句4END ;語(yǔ)句1執(zhí)行的頻度為_(kāi)n+1_；語(yǔ)句2執(zhí)行的頻度為n；語(yǔ)句3執(zhí)行的頻度為n（n+3）/2 ;語(yǔ)句4執(zhí)行的頻度為 n（n+1）/2?！颈狈浇煌ù髮W(xué)1999 二、4 （5分）】10 在下面的程序段中， 對(duì)x的賦值語(yǔ)句的頻度為1+ （1+2+ （1+2+3） +3+ （1+2+n） =n（n+1）（ n+2）/6 0（n）（表示為n的函數(shù)）FOR i : =1 TO n DOFOR j :=1 TO i DOFOR k: = 1 TO j DOx：=x

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

13、WHILE i<>1 DO i:=i div 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ù)雜度為O(n) 。(n>1)sum=1 ；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,

14、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)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);執(zhí)行程序，f(6,4)= _9o【中科院軟件所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)研究什么

15、內(nèi)容的學(xué)科？【燕山大學(xué)1999二、1(4分)】 數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究在非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中，計(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è)）指針。指針?lè)从硵?shù)據(jù)元素間的邏輯關(guān)系。 這種方式不要求存儲(chǔ)空間連 續(xù)，便于動(dòng)態(tài)操作

16、（如插入、刪除等），但存儲(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ēng)為散列存儲(chǔ)。其特點(diǎn)是存取速度快，只能按關(guān)鍵字隨機(jī)存 取，不能順序存取，也不能折半存取。3. 數(shù)據(jù)類(lèi)型和抽象數(shù)據(jù)類(lèi)型是如何定義的。二者有何相同和不同之處，抽象 數(shù)據(jù)類(lèi)型的主要特點(diǎn)是什么？使用抽象數(shù)據(jù)類(lèi)

17、型的主要好處是什么？ 【北京郵 電大學(xué) 1994 一（8 分）】數(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é)模型 及定義在該模型上的一組操作。 “抽象” 的意義在于數(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)型

18、實(shí)質(zhì)上是一個(gè)概念。此外， 抽象數(shù)據(jù)類(lèi)型的 范圍更廣， 它已不再局限于機(jī)器已定義和實(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. 回答問(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)系？數(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ù)

19、結(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)則是依賴(lài)于存儲(chǔ)結(jié)構(gòu)。（2）若邏輯結(jié)構(gòu)相同但存儲(chǔ)結(jié)構(gòu)不同，則為不同的數(shù)據(jù)結(jié)構(gòu)。這樣的說(shuō) 法對(duì)嗎？舉例說(shuō)明之。邏輯結(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)稱(chēng)為線 性鏈表。（3）在給定的邏輯結(jié)構(gòu)及其存儲(chǔ)表示上可以定義不同的運(yùn)算集合，從而 得到不同的數(shù)據(jù)結(jié)構(gòu)。這樣說(shuō)法對(duì)嗎？舉例說(shuō)明之。棧和隊(duì)列的邏輯結(jié)構(gòu)相同， 其存儲(chǔ)表示也可相同 （順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)） ， 但由于其

20、運(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)確、 完整的刻劃了問(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è)好的算法，您是從哪幾方面來(lái)考慮的？ 評(píng)價(jià)好的算法有四個(gè)方面。一是算法的正確性； 二是算法的易讀性； 三是算法 的健壯性；四是算法的時(shí)空效率（運(yùn)行）。【大連海事大學(xué) 1996 二、3 （2分）】【中山大學(xué) 1998 三、1 （5 分）】 6 解釋和比較以下各組概念【華南師范大學(xué) 200

21、0 一（ 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 分）】（ 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ì)特定

22、問(wèn)題求解步驟的描述，是指令的有限序列，其中每一條 指令表示一個(gè)或多個(gè)操作。 算法具有五個(gè)重要特性： 有窮性、確定性、 可行性、 輸入和輸出。（6）頻度。在分析算法時(shí)間復(fù)雜度時(shí)，有時(shí)需要估算基本操作的原操作， 它是執(zhí)行次數(shù)最多的一個(gè)操作，該操作重復(fù)執(zhí)行的次數(shù)稱(chēng)為頻度。7. 根據(jù)數(shù)據(jù)元素之間的邏輯關(guān)系，一般有哪幾類(lèi)基本的數(shù)據(jù)結(jié)構(gòu)？ 集合、線性結(jié)構(gòu)、樹(shù)形結(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)算）。9. 當(dāng)你為解決某一問(wèn)題而選擇數(shù)據(jù)

23、結(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）,說(shuō)明符號(hào)D, R應(yīng)分別表示什么？【北京科技大學(xué) 2001 一、1（2 分）】D是數(shù)據(jù)元素的有限集合，S是D上數(shù)據(jù)元素之間關(guān)系的有限集合。1 1 數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類(lèi)型有什么區(qū)別？【哈爾濱工業(yè)大學(xué) 2001 三、1（3分）】“數(shù)據(jù)結(jié)構(gòu)”這一術(shù)語(yǔ)有兩種含義,一是作為一門(mén)課程的名稱(chēng)；二是作為一個(gè)科學(xué)的概念。

24、作為科學(xué)概念,目前尚無(wú)公認(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ù)類(lèi)型是值的集合和操作的集合,可以看作是已實(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 見(jiàn)上面題 2 。13若有 100 個(gè)學(xué)生,每個(gè)學(xué)生有學(xué)號(hào),姓名,平均成績(jī),采用什么樣的數(shù)據(jù) 結(jié)構(gòu)最方便,寫(xiě)出這些結(jié)構(gòu)？【山東師范大學(xué) 1996 二、 2（ 2 分）】 將學(xué)號(hào)、姓名、平均成績(jī)看成一個(gè)記錄（元素,含三個(gè)數(shù)據(jù)項(xiàng)）,將100個(gè)這樣的記錄存于數(shù)組中。因一般無(wú)

25、增刪操作,故宜采用順序存儲(chǔ)。typedef structint num;/ 學(xué)號(hào)char name8;/ 姓名float score;/ 平均成績(jī)node ；node student100;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)。【北京大學(xué) 1998 一、1（5 分）】見(jiàn)上面題 4（ 3）。15. 在編制管理通訊錄的程序時(shí) , 什么樣的數(shù)據(jù)結(jié)構(gòu)合適 ? 為什么 ?【 長(zhǎng)沙鐵 道學(xué)院 1998 四、3（6 分） 】應(yīng)從兩方面進(jìn)行討論：如通訊錄較少變動(dòng)（如城市

26、私人電話號(hào)碼），主要 用于查詢，以順序存儲(chǔ)較方便，既能順序查找也可隨機(jī)查找； 若通訊錄經(jīng)常有 增刪操作，用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)較為合適，將每個(gè)人的情況作為一個(gè)元素 （即一個(gè) 結(jié)點(diǎn)存放一個(gè)人），設(shè)姓名作關(guān)鍵字，鏈表安排成有序表，這樣可提高查詢速 度。16. 試舉一例， 說(shuō)明對(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ù)雜度都是0（ 1 ）。17. 有實(shí)現(xiàn)同一功能的兩個(gè)算法A1和A2,其中A1的時(shí)間

27、復(fù)雜度為 TI=0（2 n），A2的時(shí)間復(fù)雜度為 T2=0（n2），僅就時(shí)間復(fù)雜度而言，請(qǐng)具體分析這兩個(gè)算法 哪一個(gè)好?！颈本┖娇蘸教齑髮W(xué) 2000 二（ 10 分）】 對(duì)算法A1和A2的時(shí)間復(fù)雜度 T1和T2取對(duì)數(shù)，得nlog 2和2log n。顯然，算法 A2 好于 A1 。18設(shè)計(jì)一數(shù)據(jù)結(jié)構(gòu)，用來(lái)表示某一銀行儲(chǔ)戶的基本信息：賬號(hào)、姓名、開(kāi)戶年月日、儲(chǔ)蓄類(lèi)型、存入累加數(shù)、利息、帳面總數(shù)?！菊憬髮W(xué)1994 一 、3 （ 5 分）】struct node int year,month,day; ;typedef struct int num;/ 帳號(hào)char name8;/ 姓名struct

28、 node date;/ 開(kāi)戶年月日int tag;/儲(chǔ)蓄類(lèi)型，如：0-零存，1- 一年定期float put;/ 存入累加數(shù)；float interest;/ 利息float total;/ 帳面總數(shù)count ；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;BEGIN(1)IF k=nTHEN BEGIN(2)FOR i:=1 TO n DO( 3) write (ai);writeln;ENDELSE BE

29、GIN( 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，由語(yǔ)句( 6 )知，每次調(diào)用 k 增 1， 故第(1)語(yǔ)句執(zhí)行n次。(2)是FOR循環(huán)語(yǔ)句，在滿足(1)的條件下執(zhí)行，該 語(yǔ)句進(jìn)入循環(huán)體 (3)n 次，加上最后一次判斷出界，故執(zhí)行了 n+1 次。 (4) 也是 循環(huán)語(yǔ)句，當(dāng) k=1 時(shí)判斷

30、n+1 次(進(jìn)入循環(huán)體 (5)n 次)， k=2 時(shí)判斷 n 次，最 后一次k=n-1時(shí)判斷3次，故執(zhí)行次數(shù)是(n+1) +“+ +3=(n+4)(n-1)/2次。語(yǔ)句(5)是的循環(huán)體，每次比(4)少一次判斷，故執(zhí)行次數(shù)是n+(n-1)+2=(n+2)(n-1)/2 次。注意分析時(shí)，不要把 (2) 分析成 n 次，更不是 1 次。 20. 分析下面程序段中循環(huán)語(yǔ)句的執(zhí)行次數(shù)。i:=0;s:=0;n:=100;REPEATi:=i+1;s:=s+10*i;UNTIL NOT(i<n) AND (s<n);【北京郵電大學(xué) 1998 四、 1 ( 5 分)】4 (這時(shí)i=4 , s=10

31、0 ) REPEAT語(yǔ)句先執(zhí)行循環(huán)體，后判斷條件，直到 條件為真時(shí)退出循環(huán)。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；END Inc ；【東南大學(xué) 1998 三 (8 分 ) 1994 二( 15 分)】算法在最好情況下，即二進(jìn)制數(shù)的最后一位為零時(shí)，只作一次判斷

32、， 未執(zhí) 行循環(huán)體，賦值語(yǔ)句 Ai 執(zhí)行了一次；最壞情況出現(xiàn)在二進(jìn)制數(shù)各位均為 1 (最高位為零，因題目假設(shè)無(wú)溢出)，這時(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;BEGINp:=s;WHILE p next<>q DO p:

33、=pA. next;pn ext:=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)或PASACA函數(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) int i

34、,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+;pr in tf("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 23 nj=nn nn nj=n-1n-1n-1n-1j=333j=222j=11執(zhí)行次數(shù)為(1+2+n)+(2+3+ +n)+ +n=n*n(n+1)/2-n(n 2-1)/6。在 n=5 時(shí),f(5)=55，執(zhí)行過(guò)程中，輸岀結(jié)果為：sum=15,sum