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

1、數(shù)據(jù)結(jié)構(gòu)考研真題和答案一、選擇題 算法的計算量的大小稱為計算的（ b ）?！颈本┼]電大學(xué)200 二、 (20/分)】a.效率 b.復(fù)雜性 . 現(xiàn)實性 d.難度.算法的時間復(fù)雜度取決于（c)【中科院計算所1998 二、1 (2分)】a問題的規(guī)模 b. 待處理數(shù)據(jù)的初態(tài) ca和b3.計算機算法指的是（c)，它必須具備（b) 這三個特性。(1) a.計算方法 . 排序方法 c. 解決問題的步驟序列 . 調(diào)度方法（2) a.可執(zhí)行性、可移植性、可擴充性 b 可執(zhí)行性、確定性、有窮性c. 確定性、有窮性、穩(wěn)定性 易讀性、穩(wěn)定性、安全性 【南京理工大學(xué)999一、1（分） 【武漢交通科技大學(xué) 96一、1(4

2、分)】.一個算法應(yīng)該是（ b ）?！局猩酱髮W(xué) 1998 二、1(2分)】 a.程序 問題求解步驟的描述 c.要滿足五個基本特性 d和c . 下面關(guān)于算法說法錯誤的是( d ）【南京理工大學(xué) 20一、1(.5分）】a.算法最終必須由計算機程序?qū)崿F(xiàn)b.為解決某問題的算法同為該問題編寫的程序含義是相同的c. 算法的可行性是指指令不能有二義性 d. 以上幾個都是錯誤的6.下面說法錯誤的是（ c ）【南京理工大學(xué)200 一、 （1.5分)】 (1)算法原地工作的含義是指不需要任何額外的輔助空間 （)在相同的規(guī)模n下,復(fù)雜度o()的算法在時間上總是優(yōu)于復(fù)雜度(2n)的算法 (3)所謂時間復(fù)雜度是指最壞情況

3、下，估算算法執(zhí)行時間的一個上界 (4)同一個算法，實現(xiàn)語言的級別越高,執(zhí)行效率就越低4a(1) b.(),(2） ()，(4) d.(3)7從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）兩大類?！疚錆h交通科技大學(xué) 96 一 、（2分）】動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) 順序結(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(xué) 200 二、1(分)】a.循環(huán)隊列 b. 鏈表 c. 哈希表 d. 棧9以下數(shù)據(jù)結(jié)構(gòu)中,哪一個是線性結(jié)構(gòu)（ d ）?【北方交通大學(xué) 201 一、1（2分)】a.廣義表 b. 二叉樹 c 稀疏矩陣 d. 串10以下那一個術(shù)語與數(shù)

4、據(jù)的存儲結(jié)構(gòu)無關(guān)？（ ）【北方交通大學(xué) 20 一、2（2分)】a.棧 b. 哈希表 c 線索樹 d. 雙向鏈表1.在下面的程序段中，對x的賦值語句的頻度為(c )【北京工商大學(xué) 01 一、10(分）】r :=1 to do frj：= to n o ：=+1;a.o(n） b.o（n） co(n2) d.o（log2n) 12程序段 for :=n- dowto 1 do or：=1 i o f aaj1 te aj與aj+1對換；其中n為正整數(shù)，則最后一行的語句頻度在最壞情況下是（ d ). o(n) b. o(nogn) . o（n3) . o(n2） 【南京理工大學(xué)1998一、（2分)】

5、13以下哪個數(shù)據(jù)結(jié)構(gòu)不是多型數(shù)據(jù)類型( )【中山大學(xué) 99 一、3(1分）】.棧 b.廣義表 有向圖 字符串.以下數(shù)據(jù)結(jié)構(gòu)中，（ a ）是非線性數(shù)據(jù)結(jié)構(gòu)【中山大學(xué) 199 一、4】a.樹 字符串 c隊 d.棧15 下列數(shù)據(jù)中，( c)是非線性數(shù)據(jù)結(jié)構(gòu)?！颈本├砉ご髮W(xué) 2001 六、1(分)】a.棧 b. 隊列 . 完全二叉樹 d. 堆1連續(xù)存儲設(shè)計時,存儲單元的地址（ a)?！局猩酱髮W(xué) 1999 一、（1分)】a一定連續(xù) b一定不連續(xù) c.不一定連續(xù) d.部分連續(xù)，部分不連續(xù)7以下屬于邏輯結(jié)構(gòu)的是( c ）?！疚靼搽娮涌萍即髮W(xué)應(yīng)用 200一、1】a順序表 b.哈希表 c.有序表 d. 單鏈表二

6、、判斷題1. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。( x)【北京郵電大學(xué) 998 一、1（分)】【青島大學(xué) 2000 一、1（1分)】【上海交通大學(xué) 198 一、1】 【山東師范大學(xué) 200一、1 (分）】2 記錄是數(shù)據(jù)處理的最小單位。 ( x ) 【上海海運學(xué)院 199 一、5（分）】3 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關(guān)系；(x )【北京郵電大學(xué)20一、1(分）】4算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計算機有關(guān)。( ）【大連海事大學(xué) 20一、(分)】5健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。( o )【大連海事大學(xué) 2001 一、11（1分)】6算法可以用不同的語言描述，如果

7、用c 語言或paal語言等高級語言來描述，則算法實際上就是程序了。( )【西安交通大學(xué) 196二、7(分）】7程序一定是算法。（ )【燕山大學(xué) 98二、(2分）并改錯】8.數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。（ o )【山東師范大學(xué)200一、2(分)】9. 數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實現(xiàn)有關(guān)。( x )【華南理工大學(xué) 20 一、（分）】10. 在順序存儲結(jié)構(gòu)中,有時也存儲數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。(x )【華南理工大學(xué) 2002 一、2 （1分）】11順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。( ）【上海海運學(xué)院 19 一、1(1分）】12. 數(shù)據(jù)結(jié)構(gòu)的基本操作的

8、設(shè)置的最重要的準則是,實現(xiàn)應(yīng)用程序與存儲結(jié)構(gòu)的獨立。( o )【華南理工大學(xué) 200一、5（1分)】3. 數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的順序關(guān)系,它依賴于計算機的儲存結(jié)構(gòu). ()【上海海運學(xué)院1998一、(分)】三、填空1.數(shù)據(jù)的物理結(jié)構(gòu)包括數(shù)據(jù)元素的表示和數(shù)據(jù)元素間關(guān)系的表示?！狙嗌酱髮W(xué) 998 一、1(2分）】 對于給定的n個元素,可以構(gòu)造出的邏輯結(jié)構(gòu)有集合 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 圖狀結(jié)構(gòu)（或網(wǎng)狀結(jié)構(gòu)）四種?！局锌圃河嬎闼?199 二、1(4分)】.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的組織形式,即數(shù)據(jù)元素之間邏輯關(guān)系的總體。而邏輯關(guān)系是指數(shù)據(jù)元素之間的關(guān)聯(lián)方式或稱“鄰接關(guān)系”?！颈本┼]電大學(xué)20二、1

9、（2分)】4.一個數(shù)據(jù)結(jié)構(gòu)在計算機中表示(又稱映像）稱為存儲結(jié)構(gòu)?！救A中理工大學(xué) 2000 一、1（分）】.抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與在計算機內(nèi)部如何表示和實現(xiàn)無關(guān),即不論其內(nèi)部結(jié)構(gòu)如何變化,只要它的數(shù)學(xué)特性不變，都不影響其外部使用?！旧綎|大學(xué)200 三、(分)】數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標是算法的時間復(fù)雜度和空間復(fù)雜度【北京理工大學(xué) 01 七、1（分）】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(xué)1998 二、2（3分）】8. 一個算法具有5個特性:(1）有窮性 (2）

10、確定性 （）可行性，有零個或多個輸入、有一個或多個輸出?！救A中理工大學(xué) 2000 一、2(5分）】 【燕山大學(xué) 18 一、（5分)】9已知如下程序段fr i:= n downo 1 o 語句bg x:=x+1； 語句2r j: dontoi 語句3 :=y+； 語句4；語句1執(zhí)行的頻度為 n1；語句2執(zhí)行的頻度為n；語句3執(zhí)行的頻度為n(n+3)/2;語句執(zhí)行的頻度為n(n+1)/2?！颈狈浇煌ù髮W(xué)19 二、4(5分）】1在下面的程序段中，對的賦值語句的頻度為1+(1+2+（+3）+(12+n)=n(n1）(n+2)/6 o(n)（表示為n的函數(shù)） fo i：= o ndfr j：=1 to

11、do frk:1 to do x：=xdea；【北京工業(yè)大學(xué) 199 一、6（2分）】11.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是：log2n【合肥工業(yè)大學(xué)99三、(分)】i：=； whiln i:=*2;12. 下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是( nlog2n )?！竞戏使I(yè)大學(xué) 2 三、1（2分）】i:1；while inbgnfor: o n do x:x+;:=i*2 ed;3. 下面程序段中帶有下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是(lo22 ) 【合肥工業(yè)大學(xué) 201三、1（2分）】：n hlei1 do :=i div;4 計算機執(zhí)行下面的語句時,語句s的執(zhí)行次數(shù)

12、為 (n3)(n-2)2 ?！灸暇├砉ご髮W(xué)000二、(.5分)】 for(l;in-l;i+） fo(jn;j=；-) s;5 下面程序段的時間復(fù)雜度為_ o（n)_。(1) u； for(i=0;sum;+） sum+=1； 【南京理工大學(xué) 200 二、1(2分)】1.設(shè)m.n均為自然數(shù)，m可表示為一些不超過的自然數(shù)之和,f(m，n)為這種表示方式的數(shù)目。例(5,)=5，有5種表示方式:+2，3+1+1，2+21，2+1+1，1+1+1+11。以下是該函數(shù)的程序段，請將未完成的部分填入，使之完整int f(m，n) int m,; if（m=1） eur1;i(=1) retun 1;if(

13、mn)turnf(,m）;f (mn） rtn 1f（m,n-1);return f(m.-1)+f(m-n,）;執(zhí)行程序,(6,4)= 9。 【中科院軟件所197 二、(9分)】17.在有n個選手參加的單循環(huán)賽中，總共將進行n(n1)/2場比賽?！竞戏使I(yè)大學(xué)199三、8（分）】四、應(yīng)用題1. 數(shù)據(jù)結(jié)構(gòu)是一門研究什么內(nèi)容的學(xué)科？【燕山大學(xué) 1999 二、1(4分)】數(shù)據(jù)結(jié)構(gòu)是一門研究在非數(shù)值計算的程序設(shè)計問題中,計算機的操作對象及對象間的關(guān)系和施加于對象的操作等的學(xué)科。2. 數(shù)據(jù)元素之間的關(guān)系在計算機中有幾種表示方法？各有什么特點?【燕山大學(xué)99 二、（4分）】四種表示方法（1)順序存儲方式

14、。數(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)

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

16、象”的意義在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。抽象數(shù)據(jù)類型的定義僅取決于它的邏輯特性，而與其在計算機內(nèi)部如何表示和實現(xiàn)無關(guān)。無論其內(nèi)部結(jié)構(gòu)如何變化,只要它的數(shù)學(xué)特性不變就不影響它的外部使用。抽象數(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ù)”，而是向“科學(xué)”邁進了一步。4. 回答問題（每題2分）【山東工業(yè)大學(xué)197一(8分)】(1)在數(shù)據(jù)結(jié)構(gòu)課程

17、中，數(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)及其存儲表示上可以

18、定義不同的運算集合,從而得到不同的數(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);基本運算的選擇是否恰當。)評價一個好的算法，您是從哪幾方面來考慮的?評價好的算法有四個方面。一是算法的正確性；二是算法的易讀性；三是算法的健壯性；四是算法的時空效率(運行）?！敬筮B海事大學(xué)

19、996 二、3 （2分）】【中山大學(xué) 998 三、1 (5分）】.解釋和比較以下各組概念【華南師范大學(xué) 20 一(0分)】(1)抽象數(shù)據(jù)類型及數(shù)據(jù)類型 (2)數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)（）抽象數(shù)據(jù)類型【哈爾濱工業(yè)大學(xué)200 一、1(分）】（）算法的時間復(fù)雜性【河海大學(xué) 1998 一、2(分）】（5）算法【吉林工業(yè)大學(xué)1999 一、1（2分)】()頻度【吉林工業(yè)大學(xué) 9 一、2(分）】(1）見上面題3 (2）見上面題4（3)見上面題3 (4)算法的時間復(fù)雜性是算法輸入規(guī)模的函數(shù)。算法的輸入規(guī)模或問題的規(guī)模是作為該算法輸入的數(shù)據(jù)所含數(shù)據(jù)元素的數(shù)目,或與此數(shù)目有關(guān)的其它參數(shù)。有時考慮算法在最壞情況

20、下的時間復(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)。 【北京科技大學(xué) 18 一、1】【同濟大學(xué)99】8.對于一個數(shù)據(jù)結(jié)構(gòu)，一般包括哪三個方面的討論?【北京科技大學(xué) 999 一、（2分）】邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、操作(運算)。. 當你為解決某一問

21、題而選擇數(shù)據(jù)結(jié)構(gòu)時,應(yīng)從哪些方面考慮?【西安電子北京科技大學(xué)200】通常考慮算法所需要的存儲空間量和算法所需要的時間量。后者又涉及到四方面:程序運行時所需輸入的數(shù)據(jù)總量,對源程序進行編譯所需時間,計算機執(zhí)行每條指令所需時間和程序中指令重復(fù)執(zhí)行的次數(shù)。10.若將數(shù)據(jù)結(jié)構(gòu)定義為一個二元組（d,r），說明符號d, 應(yīng)分別表示什么?【北京科技大學(xué) 2001一、1（2分）】是數(shù)據(jù)元素的有限集合,s是d上數(shù)據(jù)元素之間關(guān)系的有限集合。11數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型有什么區(qū)別?【哈爾濱工業(yè)大學(xué) 200 三、(3分）】“數(shù)據(jù)結(jié)構(gòu)”這一術(shù)語有兩種含義,一是作為一門課程的名稱;二是作為一個科學(xué)的概念。作為科學(xué)概念,目前尚無

22、公認定義,一般認為，討論數(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)？【山東科技大學(xué)201 一、1(分）】12見上面題2。13.若有100個學(xué)生,每個學(xué)生有學(xué)號,姓名,平均成績，采用什么樣的數(shù)據(jù)結(jié)構(gòu)最方便,寫出這些結(jié)構(gòu)?【山東師范大學(xué) 1996 二、2（2分)】將學(xué)號、姓名、平均成績看成一個記錄(元素,含三個數(shù)據(jù)項),將1個這樣的記錄存于數(shù)組中。因一般無增刪操作，故宜采用順序存儲。 yedef struct i

23、nt num;/學(xué)號 car name8;/姓名 lo scoe；/平均成績 ode； nde stdnt100;. 運算是數(shù)據(jù)結(jié)構(gòu)的一個重要方面。試舉一例,說明兩個數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲方式完全相同,只是對于運算的定義不同。因而兩個結(jié)構(gòu)具有顯著不同的特性，是兩個不同的結(jié)構(gòu)?！颈本┐髮W(xué) 198一、1(5分）】見上面題4(）。5. 在編制管理通訊錄的程序時,什么樣的數(shù)據(jù)結(jié)構(gòu)合適? 為什么？【 長沙鐵道學(xué)院998四、3(6分)】應(yīng)從兩方面進行討論：如通訊錄較少變動（如城市私人電話號碼)，主要用于查詢，以順序存儲較方便,既能順序查找也可隨機查找;若通訊錄經(jīng)常有增刪操作，用鏈式存儲結(jié)構(gòu)較為合適，將每

24、個人的情況作為一個元素(即一個結(jié)點存放一個人),設(shè)姓名作關(guān)鍵字,鏈表安排成有序表，這樣可提高查詢速度。6 試舉一例，說明對相同的邏輯結(jié)構(gòu),同一種運算在不同的存儲方式下實現(xiàn)，其運算效率不同。【北京理工大學(xué) 200 三、(4.5分)】線性表中的插入、刪除操作,在順序存儲方式下平均移動近一半的元素,時間復(fù)雜度為（)；而在鏈式存儲方式下,插入和刪除時間復(fù)雜度都是o(1）。. 有實現(xiàn)同一功能的兩個算法a1和a2，其中a1的時間復(fù)雜度為tlo(2n),2的時間復(fù)雜度為t=(n2)，僅就時間復(fù)雜度而言，請具體分析這兩個算法哪一個好?！颈本┖娇蘸教齑髮W(xué) 00 二（10分)】對算法a1和a2的時間復(fù)雜度和t2取

25、對數(shù),得nlg2和2logn。顯然,算法a2好于a1。18設(shè)計一數(shù)據(jù)結(jié)構(gòu)，用來表示某一銀行儲戶的基本信息:賬號、姓名、開戶年月日、儲蓄類型、存入累加數(shù)、利息、帳面總數(shù)?！菊憬髮W(xué) 1994 一 、3（5分)】tru node nt r,monh，dy; ; typdef srct it nu；帳號 charae;/姓名 strt node date;/開戶年月日 tag;/儲蓄類型,如：0-零存，1- 一年定期 floa pt;存入累加數(shù); lot inerest；/利息 fa tot;帳面總數(shù) n；9 寫出下面算法中帶標號語句的頻度。 type ar=rray.ofdataype; proc

26、edure er(: a； , n:integr)； va x: dtayp; i:itegr; bgin (1）ifk=n thn bein (2）for :=1 to n do (3)wte （ai); writn； ed lse beg (4） or i:k to n do （5）a:=ai+i*i; (6） perm (a,k+, n)； ed; en;設(shè)k的初值等于1?！颈本┼]電大學(xué)1997二（0分)】(1)n (2）n+1 (3) (4)(n+4）(n)/2 （5)（n+)(-)2 (6)n1 這是一個遞歸調(diào)用,因k的初值為1，由語句（)知,每次調(diào)用k增1,故第()語句執(zhí)行n次。(

27、2）是or循環(huán)語句，在滿足(1)的條件下執(zhí)行，該語句進入循環(huán)體(3)n次,加上最后一次判斷出界,故執(zhí)行了n次。(4)也是循環(huán)語句,當k=1時判斷1次（進入循環(huán)體(）n次）,=2時判斷次,最后一次n-時判斷3次，故執(zhí)行次數(shù)是（n+1)+(n+4)（n1)/次。語句(5）是（4)的循環(huán)體，每次比(4)少一次判斷，故執(zhí)行次數(shù)是+(n-1)+2（n+2)(n-1)/2次。注意分析時，不要把（2)分析成n次，更不是次。20. 分析下面程序段中循環(huán)語句的執(zhí)行次數(shù)。i：;s:=0；:=1;repeat i:=i+1; s:s+0*i;nil nt(in) ad (sn)；【北京郵電大學(xué) 998 四、（5分）

28、】 （這時=，s100） repea語句先執(zhí)行循環(huán)體,后判斷條件，直到條件為真時退出循環(huán)。1.下列算法對一n位二進制數(shù)加1，假如無溢出，該算法的最壞時間復(fù)雜性是什么?并分析它的平均時間復(fù)雜性。type num=ary .n f 0.1;prceue nc （ar a：nm）;var i：iter;begin i:=n；whilai=1 dogi ai：=0; i：=i-1；end;ed;ai：1;end ic；【東南大學(xué)1998 三 (分) 14 二（15分)】算法在最好情況下，即二進制數(shù)的最后一位為零時,只作一次判斷,未執(zhí)行循環(huán)體,賦值語句ai執(zhí)行了一次；最壞情況出現(xiàn)在二進制數(shù)各位均為1（最

29、高位為零,因題目假設(shè)無溢出)，這時循環(huán)體執(zhí)行了-1次,時間復(fù)雜度是o(）,循環(huán)體平均執(zhí)行n/2次，時間復(fù)雜度仍是o(n)。22. 閱讀下列算法,指出算法a的功能和時間復(fù)雜性 proceur a (h，:ponter)；(，g分別為單循環(huán)鏈表（inge inkd circula lst)中兩個結(jié)點指針)procdre b(s,q:piter)； vr p：poine; gin p：s; whie p.ne do p:=p.ext; .next：=s; ed;（f b）begb(,)； b（g,h);ed;(o a）【東南大學(xué) 19二（0分)】該算法功能是將原單循環(huán)鏈表分解成兩個單循環(huán)鏈表：其一包

30、括結(jié)點h到結(jié)點的前驅(qū)結(jié)點；另一個包括結(jié)點g到結(jié)點h的前驅(qū)結(jié)點。時間復(fù)雜度是(n)。2. 調(diào)用下列c函數(shù)f（n)或pasacl函數(shù)(n) 回答下列問題:(1) 試指出(n)值的大小，并寫出f(n) 值的推導(dǎo)過程;（2）假定n= 5，試指出f（5）值的大小和執(zhí)行f()時的輸出結(jié)果 。 c函數(shù): it (int ) int ，,s= 0; for(=l； ii-1; j-) fo(k=1；kj+1;+) sum+； inf(sum=%dn,s); rtu(su); 【華中理工大學(xué)0 六(10分）】第一層for循環(huán)判斷n+1次,往下執(zhí)行次，第二層fr執(zhí)行次數(shù)為（n+(-）(n-2)+),第三層循環(huán)體受

31、第一層循環(huán)和第二層循環(huán)的控制,其執(zhí)行次數(shù)如下表: 1 2 3 n j=n n =n-n-1 -1 1 j 3 2 2j1 1執(zhí)行次數(shù)為（12+）(2+3+n)+n*n(n1)/2-n(-1)/6。在n5時,f（)=5,執(zhí)行過程中，輸出結(jié)果為:sum1,um=29，sum=1，um50，um=（每個sm= 占一行,為節(jié)省篇幅，這里省去換行）。24設(shè)n是偶數(shù)，試計算運行下列程序段后的值并給出該程序段的時間復(fù)雜度。m:=0；for i:=1 t n do or j:2* ton d m:=m+1；【南京郵電大學(xué) 20一、1】o(n）,的值等于賦值語句m:=m+1的運行次數(shù),其計算式為5.有下列運行時間函數(shù)：（1)1 （n)=1000; (2）t(n)n2100； (）t（n）=3n+100+n+1;分別寫出相應(yīng)的大o表示的運算時間。(1)o(1) (2)o(n2) (3）o(n)【吉林工業(yè)大學(xué) 19