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

數(shù)據(jù)結(jié)構(gòu)考研真題和答案數(shù)據(jù)結(jié)構(gòu)考研真題和答案數(shù)據(jù)結(jié)構(gòu)考研真題和答案xxx公司數(shù)據(jù)結(jié)構(gòu)考研真題和答案文件編號(hào)：文件日期：修訂次數(shù)：第1.0次更改批準(zhǔn)審核制定方案設(shè)計(jì)，管理制度一、選擇題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è)基本特性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)的算法在時(shí)間上總是優(yōu)于復(fù)雜度O(2n)的算法（3）所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界（4）同一個(gè)算法，實(shí)現(xiàn)語言的級別越高，執(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ù)語是（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．在下面的程序段中，對x的賦值語句的頻度為（C）【北京工商大學(xué)2001一、10（3分）】FORi:=1TOnDOFORj:=1TOnDOx:=x+1;A．O(2n)B．O(n)C．O(n2)D．O(log2n)12．程序段FORi:=n-1DOWNTO1DOFORj:=1TOiDOIFA[j]>A[j+1]THENA[j]與A[j+1]對換；其中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)。【北京理工大學(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）。【西安電子科技大學(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語言等高級語言來描述，則算法實(shí)際上就是程序了。(X)【西安交通大學(xué)1996二、7（3分）】7．程序一定是算法。(X)【燕山大學(xué)1998二、2（2分）并改錯(cuò)】8．?dāng)?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．?dāng)?shù)據(jù)的物理結(jié)構(gòu)包括數(shù)據(jù)元素的表示和數(shù)據(jù)元素間關(guān)系的表示。【燕山大學(xué)1998一、1（2分）】2.對于給定的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．?dāng)?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)。【華中理工大學(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．?dāng)?shù)據(jù)結(jié)構(gòu)中評價(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)系，并對與這種結(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è)輸出?！救A中理工大學(xué)2000一、2（5分）】【燕山大學(xué)1998一、2（5分）】9．已知如下程序段FORi:=nDOWNTO1DO{語句1}BEGINx:=x+1；{語句2}FORj:=nDOWNTOiDO{語句3}y:=y+1;{語句4}END；語句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．在下面的程序段中，對ｘ的賦值語句的頻度為1+（1+2++（1+2+3）+…+（1+2+…+n）=n(n+1)(n+2)/6O(n3)（表示為n的函數(shù)）FORi：＝１TOnDOFORj：＝１TOiDOFORk：＝1TOjDOｘ：＝ｘ＋delta；【北京工業(yè)大學(xué)1999一、6（2分）】11.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是：log2n【合肥工業(yè)大學(xué)1999三、1（2分）】i：=1；WHILEi<nDOi：=i*2;12.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是(nlog2n)?！竞戏使I(yè)大學(xué)2000三、1（2分）】i:=1;WHILEi<nBEGINFORj:=1TOnDOx:=x+1;i:=i*2END；13.下面程序段中帶有下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是(log2n2)【合肥工業(yè)大學(xué)2001三、1（2分）】i：=n*n WHILEi<>1DOi:=idiv2;14.計(jì)算機(jī)執(zhí)行下面的語句時(shí)，語句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可表示為一些不超過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ù)的程序段，請將未完成的部分填入，使之完整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);}returnf(m.n-1)+f(m-n,n);}②執(zhí)行程序，f(6,4)=9?！局锌圃很浖?997二、1（9分）】

17.在有n個(gè)選手參加的單循環(huán)賽中，總共將進(jìn)行n(n-1)/2場比賽。【合肥工業(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ī)的操作對象及對象間的關(guān)系和施加于對象的操作等的學(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í)型、字符型等。整型值的范圍（對具體機(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)三部分，封裝在一起，對用戶透明（提供接口），而不必了解實(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)算是對數(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)。這樣的說法對嗎？舉例說明之。

邏輯結(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ì)列的邏輯結(jié)構(gòu)相同，其存儲(chǔ)表示也可相同（順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)），但由于其運(yùn)算集合不同而成為不同的數(shù)據(jù)結(jié)構(gòu)。（4）評價(jià)各種不同數(shù)據(jù)結(jié)構(gòu)的標(biāo)準(zhǔn)是什么？

數(shù)據(jù)結(jié)構(gòu)的評價(jià)非常復(fù)雜，可以考慮兩個(gè)方面，一是所選數(shù)據(jù)結(jié)構(gòu)是否準(zhǔn)確、完整的刻劃了問題的基本特征；二是是否容易實(shí)現(xiàn)（如對數(shù)據(jù)分解是否恰當(dāng)；邏輯結(jié)構(gòu)的選擇是否適合于運(yùn)算的功能，是否有利于運(yùn)算的實(shí)現(xiàn)；基本運(yùn)算的選擇是否恰當(dāng)。）5．評價(jià)一個(gè)好的算法，您是從哪幾方面來考慮的？

評價(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）算法是對特定問題求解步驟的描述，是指令的有限序列，其中每一條指令表示一個(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)?！颈本┛萍即髮W(xué)1998一、1】【同濟(jì)大學(xué)1998】8．對于一個(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ù)總量，對源程序進(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．?dāng)?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)，三是對數(shù)據(jù)進(jìn)行的操作（運(yùn)算）。而數(shù)據(jù)類型是值的集合和操作的集合，可以看作是已實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)，后者是前者的一種簡化情況。12．?dāng)?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)，姓名，平均成績，采用什么樣的數(shù)據(jù)結(jié)構(gòu)最方便，寫出這些結(jié)構(gòu)？

【山東師范大學(xué)1996二、2（2分）】將學(xué)號(hào)、姓名、平均成績看成一個(gè)記錄（元素，含三個(gè)數(shù)據(jù)項(xiàng)），將100個(gè)這樣的記錄存于數(shù)組中。因一般無增刪操作，故宜采用順序存儲(chǔ)。typedefstruct{intnum;//學(xué)號(hào)charname[8];//姓名floatscore;/平均成績}node；nodestudent[100];14.運(yùn)算是數(shù)據(jù)結(jié)構(gòu)的一個(gè)重要方面。試舉一例，說明兩個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲(chǔ)方式完全相同，只是對于運(yùn)算的定義不同。因而兩個(gè)結(jié)構(gòu)具有顯著不同的特性，是兩個(gè)不同的結(jié)構(gòu)?！颈本┐髮W(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.試舉一例，說明對相同的邏輯結(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ù)雜度而言，請具體分析這兩個(gè)算法哪一個(gè)好。【北京航空航天大學(xué)2000二（10分）】對算法A1和A2的時(shí)間復(fù)雜度T1和T2取對數(shù)，得nlog2和2logn。顯然，算法A2好于A1。18．設(shè)計(jì)一數(shù)據(jù)結(jié)構(gòu)，用來表示某一銀行儲(chǔ)戶的基本信息：賬號(hào)、姓名、開戶年月日、儲(chǔ)蓄類型、存入累加數(shù)、利息、帳面總數(shù)。【浙江大學(xué)1994一、3（5分）】structnode{intyear,month,day;};typedefstruct{intnum;//帳號(hào)charname[8];//姓名structnodedate;//開戶年月日inttag;//儲(chǔ)蓄類型，如：0-零存，1-一年定期……floatput;//存入累加數(shù)；floatinterest;//利息floattotal;//帳面總數(shù)}count； 19.寫出下面算法中帶標(biāo)號(hào)語句的頻度。TYPEar=ARRAY[1..n]OFdatatype;PROCEDUREperm(a:ar;k,n:integer);VARx:datatype;i:integer;BEGIN（1）IFk=nTHENBEGIN（2）FORi:=1TOnDO（3）write(a[i]);writeln;ENDELSEBEGIN（4）FORi:=kTOnDO（5）a[i]:=a[i]+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;REPEATi:=i+1;s:=s+10*i;UNTILNOT((i<n)AND(s<n));【北京郵電大學(xué)1998四、1（5分）】4（這時(shí)i=4，s=100）REPEAT語句先執(zhí)行循環(huán)體，后判斷條件，直到條件為真時(shí)退出循環(huán)。21．下列算法對一n位二進(jìn)制數(shù)加1，假如無溢出，該算法的最壞時(shí)間復(fù)雜性是什么？并分析它的平均時(shí)間復(fù)雜性。

TYPEnum=ARRAY[1..n]of[0..1]；PROCEDUREInc（VARa：num）；VARi：integer；BEGINi：=n；WHILEA[i]=1DOBEGINA[i]：=0；i：=i-1；END；END；A[i]：=1；ENDInc；【東南大學(xué)1998三(8分)1994二（15分）】算法在最好情況下，即二進(jìn)制數(shù)的最后一位為零時(shí)，只作一次判斷，未執(zhí)行循環(huán)體，賦值語句A[i]執(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ù)雜性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分）】該算法功能是將原單循環(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ù)：intf(intn){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++)sum++;printf("sum=%d\n",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=123…nj=nnnn…nj=n-1n-1n-1n-1……………j=333j=222j=11執(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,