數(shù)據(jù)結(jié)構(gòu)考研試題精選及答案第1章緒論

1、緒論一、選擇題1.算法的計(jì)算量的大小稱為計(jì)算的（）?！颈本┼]電大學(xué)2000A.效率B.復(fù)雜性C.現(xiàn)實(shí)性D.二、3（20/8難度分）】2.算法的時(shí)間復(fù)雜度取決于）【中科院計(jì)算所1998二、1（2分）】A.問題的規(guī)模3.計(jì)算機(jī)算法指的是（1） A.計(jì)算方法法（2） A,可執(zhí)行性、B.1),B.待處理數(shù)據(jù)的初態(tài)它必須具備（排序方法可移植性、可擴(kuò)充性C.確定性、有窮性、穩(wěn)定性【南京理工大學(xué)19994.一個(gè)算法應(yīng)該是（A.程序I一、1（2分）。【中山大學(xué)5.6.2)D.B.問題求解步驟的描述卜面關(guān)于算法說法錯(cuò)誤的是（C.A和B這三個(gè)特性。C.B.解決問題的步驟序列可執(zhí)行性、確定性、有窮性易讀性、穩(wěn)定性、

2、安全性D.【武漢交通科技大學(xué)1996一、1（41998二、1（2分）】調(diào)度方C.要滿足五個(gè)基本特性D.A和C.）【南京理工大學(xué)2000、1（1.5分）】A.算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)B.為解決某問題的算法同為該問題編寫的程序含義是相同的C.算法的可行性是指指令不能有二義性卜面說法錯(cuò)誤的是（）【南京理工大學(xué)2000D.以上幾個(gè)都是錯(cuò)誤的、2（1.5分）】(1)(2)(3)(4)A.算法原地工作的含義是指不需要任何額外的輔助空間在相同的規(guī)模n下，復(fù)雜度O（n）的算法在時(shí)間上總是優(yōu)于復(fù)雜度O（2n）的算法所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界同一個(gè)算法，實(shí)現(xiàn)語(yǔ)言的級(jí)別越高，執(zhí)行效

3、率就越低B.(1),(2)C.(1),(4)D.(3)7.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為A.動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)C.線性結(jié)構(gòu)、非線性結(jié)構(gòu)8 .以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)的術(shù)語(yǔ)是A.循環(huán)隊(duì)列B.鏈表9 .以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線性結(jié)構(gòu)）兩大類。【武漢交通科技大學(xué)1996一、4（2分）B.順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu).初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu):（）?！颈狈浇煌ù髮W(xué)2000二、1（2分）】C.哈希表D.棧）?【北方交通大學(xué)2001一、1（2分）】A.廣義表B.二叉樹C.10.以下那一個(gè)術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)?A.棧B.哈希表C.稀疏矩陣）線索樹D.串【北方交通大學(xué)2001一、2（2分）】D.雙向鏈表11.在下面的程序

4、段中,分）】對(duì)x的賦值語(yǔ)句的頻度為（）【北京工商大學(xué)2001一、10（3FORi:=1FORj:=1x:=x+1;A.O(2n)TOTODODO.O(n)_2_C.O(n)D.O(log2n)12.程序段FORi:=n-1DOWNTO1DOFORj:=1TOiDOIFAj>Aj+1THENAj與Aj+1對(duì)換；其中n為正整數(shù)，則最后一行的語(yǔ)句頻度在最壞情況下是（）A.O（n）B.O（nlogn）C.O（n3）D.O（n2）【南京理工大學(xué)19981（2分）】13.以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)不是多型數(shù)據(jù)類型（）【中山大學(xué)1999一、3（1分）】A.棧B.廣義表C.有向圖D.字符串14 .以下數(shù)據(jù)結(jié)構(gòu)中，

5、（）是非線性數(shù)據(jù)結(jié)構(gòu)【中山大學(xué)1999一、4】A.樹B.字符串C.隊(duì)D.棧15 .下列數(shù)據(jù)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)?！颈本├砉ご髮W(xué)2001六、1（2分）】A.棧B.隊(duì)列C.完全二叉樹D.堆16 .連續(xù)存儲(chǔ)設(shè)計(jì)時(shí)，存儲(chǔ)單元的地址（）?！局猩酱髮W(xué)1999一、1（1分）】A.一定連續(xù)B.一定不連續(xù)C.不一定連續(xù)D.部分連續(xù)，部分不連續(xù)17 .以下屬于邏輯結(jié)構(gòu)的是（）。【西安電子科技大學(xué)應(yīng)用2001一、1】A.順序表B.哈希表C.有序表D.單鏈表二、判斷題1 .數(shù)據(jù)元素是數(shù)據(jù)白最小單位。（）【北京郵電大學(xué)1998一、1（2分）】【青島大學(xué)2000、1（1分）】【上海交通大學(xué)1998一、1】【山東師范大

6、學(xué)2001一、1（2分）】2 .記錄是數(shù)據(jù)處理的最小單位。（）【上海海運(yùn)學(xué)院1998一、5（1分）】3 .數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系；（）【北京郵電大學(xué)2002-1（1分）】4 .算法的優(yōu)劣與算法描述語(yǔ)言無(wú)關(guān)，但與所用計(jì)算機(jī)有關(guān)。（）【大連海事大學(xué)2001一、10（1分）】5 .健壯的算法不會(huì)因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。（）【大連海事大學(xué)2001一、11（1分）】6 .算法可以用不同的語(yǔ)言描述，如果用C語(yǔ)言或PASCAL語(yǔ)言等高級(jí)語(yǔ)言來(lái)描述，則算法實(shí)際上就是程序了。（）【西安交通大學(xué)1996二、7（3分）】7 .程序一定是算法。（）【燕山大學(xué)1998二、2（2分）

7、并改錯(cuò)】8 .數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲(chǔ)形式。（）【山東師范大學(xué)20012（2分）】9 .數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實(shí)現(xiàn)有關(guān)。（）【華南理工大學(xué)2002一、1（1分）】10 .在順序存儲(chǔ)結(jié)構(gòu)中，有時(shí)也存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。（）【華南理工大學(xué)2002一、2（1分）】11 .順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。（）【上海海運(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ú)立。（）【華南理工大學(xué)2002一、5（1分）】13 .數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的順序關(guān)系，它依賴于計(jì)算機(jī)的儲(chǔ)存結(jié)構(gòu).（）

8、【上海海運(yùn)學(xué)院1998一、1（1分）】、填空1 .數(shù)據(jù)的物理結(jié)構(gòu)包括的表示和的表示?！狙嗌酱髮W(xué)1998、1（2分）】2 .對(duì)于給定的n個(gè)元素，可以構(gòu)造出的邏輯結(jié)構(gòu)有（1）,（2）,（3）,_（4）四種?！局锌圃河?jì)算所1999二、1（4分）】3 .數(shù)據(jù)的邏輯結(jié)構(gòu)是指?！颈本┼]電大學(xué)2001二、1（2分）】4 .一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中稱為存儲(chǔ)結(jié)構(gòu)。【華中理工大學(xué)2000一、1（1分）】5 .抽象數(shù)據(jù)類型的定義僅取決于它的一組_（1）,而與（2）_無(wú)關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的（3）不變，都不影響其外部使用?！旧綎|大學(xué)2001三、3（2分）】6 .數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是【北京理

9、工大學(xué)2001七、1（2分）】7 .數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的_（1）_禾口,以及它們之間的相互關(guān)系，并對(duì)與這種結(jié)構(gòu)定義相應(yīng)的_（3）_,設(shè)計(jì)出相應(yīng)的（4）?！疚靼搽娮涌萍即髮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 .已知如下程序段FORi:=nDOWNTO1DO語(yǔ)句1x:=x+1;FORj:=nDOWNTODO語(yǔ)句2語(yǔ)句3語(yǔ)句4BEGINy:=y+1;END；語(yǔ)句1執(zhí)行的頻度為（1）;語(yǔ)句2執(zhí)行的頻度為（2）;語(yǔ)句3執(zhí)行的頻度為（3）;語(yǔ)句4執(zhí)行的頻度

10、為（4）?！颈狈浇煌ù髮W(xué)1999二、4（5分）】10 .在下面的程序段中，對(duì)x的賦值語(yǔ)句的頻度為（表示為n的函數(shù)）FORi：=1TOnDOFORj：=1TOiDOFORk:=1TOjDOx：=x+delta；【北京工業(yè)大學(xué)1999一、6（2分）】11 .下面程序段中帶下劃線的語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)是：【合肥工業(yè)大學(xué)1999三、1（2分）】i:=1;WHILEi<nDOi:=i*2;12 .下面程序段中帶下劃線的語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)是（）?！竞戏使I(yè)大學(xué)2000三、1（2分）】i:=1;WHILEi<nBEGINFORj:=1TOnDOx:=x+1;i:=i*2END;13 .下面

11、程序段中帶有下劃線的語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)是（）【合肥工業(yè)大學(xué)2001（2分）i：=n*nWHILEi<>1DOi:=idiv2;14 .計(jì)算機(jī)執(zhí)行下面的語(yǔ)句時(shí)，語(yǔ)句s的執(zhí)行次數(shù)為。【南京理工大學(xué)2000二、1（1.5分）FOR（i=l;i<n-l;i+）FOR（j=n;j>=i;j-）s;15.下面程序段的時(shí)間復(fù)雜度為。(n>1)sum=1;【南京理工大學(xué)2001二、1（2分）】for(i=0;sum<n;i+)sum+=1;16 .設(shè)m.n均為自然數(shù)，m可表示為一些不超過n的自然數(shù)之和，f（m,n）為這種表示方式的數(shù)目。例f（5,3）=5,有5種表示方式

12、：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)return(1);if(n=1)return(2);if(m<n)returnf(m,m);if(m=n)return1+(3);returnf(m.n-1)+f(m-n,(4);執(zhí)行程序，f（6,4）=。【中科院軟件所1997二、1（9分）】17 .在有n個(gè)選手參加的單循環(huán)賽中，總共將進(jìn)行場(chǎng)比賽?！竞戏使I(yè)大學(xué)1999三8（2分）】四、應(yīng)用題1 .數(shù)據(jù)結(jié)構(gòu)是一門研究什么內(nèi)容的學(xué)科？【燕山大學(xué)1999二、1（4分）】2

13、.數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有幾種表示方法？各有什么特點(diǎn)？【燕山大學(xué)1999二2（4分）3 .數(shù)據(jù)類型和抽象數(shù)據(jù)類型是如何定義的。二者有何相同和不同之處，抽象數(shù)據(jù)類型的主要特點(diǎn)是什么？使用抽象數(shù)據(jù)類型的主要好處是什么？【北京郵電大學(xué)1994一（8分）】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)系？（2）若邏輯結(jié)構(gòu)相同但存儲(chǔ)結(jié)構(gòu)不同，則為不同的數(shù)據(jù)結(jié)構(gòu)。這樣的說法對(duì)嗎？舉例說明之。（3）在給定的邏輯結(jié)構(gòu)及其存儲(chǔ)表示上可以定義不同的運(yùn)算集合，從而得到不同的數(shù)據(jù)結(jié)構(gòu)。這樣說法對(duì)嗎？舉例說明之。（4）

14、評(píng)價(jià)各種不同數(shù)據(jù)結(jié)構(gòu)的標(biāo)準(zhǔn)是什么？5 .評(píng)價(jià)一個(gè)好的算法，您是從哪幾方面來(lái)考慮的？【大連海事大學(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分)】7 .根據(jù)數(shù)據(jù)元素之間的邏輯關(guān)系，一般有哪幾類基本的數(shù)據(jù)結(jié)構(gòu)？【北京科技大學(xué)1998一、1】【同濟(jì)大學(xué)1998】

15、8 .對(duì)于一個(gè)數(shù)據(jù)結(jié)構(gòu)，一般包括哪三個(gè)方面的討論？【北京科技大學(xué)1999一、1(2分)】9 .當(dāng)你為解決某一問題而選擇數(shù)據(jù)結(jié)構(gòu)時(shí)，應(yīng)從哪些方面考慮？【西安電子北京科技大學(xué)2000】10 .若將數(shù)據(jù)結(jié)構(gòu)定義為一個(gè)二元組(D,R),說明符號(hào)D,R應(yīng)分別表示什么？【北京科技大學(xué)2001一、1(2分)】11 .數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型有什么區(qū)別？【哈爾濱工業(yè)大學(xué)2001三、1(3分)】12 .數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)由哪四種基本的存儲(chǔ)方法實(shí)現(xiàn)？【山東科技大學(xué)2001、1(4分)】13 .若有100個(gè)學(xué)生，每個(gè)學(xué)生有學(xué)號(hào)，姓名，平均成績(jī)，采用什么樣的數(shù)據(jù)結(jié)構(gòu)最方便，寫出這些結(jié)構(gòu)？【山東師范大學(xué)1996二、2(2分)】1

16、4 .運(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)?！颈本┐髮W(xué)1998、1(5分)】15 .在編制管理通訊錄的程序時(shí)，什么樣的數(shù)據(jù)結(jié)構(gòu)合適？為什么？【長(zhǎng)沙鐵道學(xué)院1998四、3(6分)】16 .試舉一例，說明對(duì)相同的邏輯結(jié)構(gòu)，同一種運(yùn)算在不同的存儲(chǔ)方式下實(shí)現(xiàn)，其運(yùn)算效率不同?！颈本├砉ご髮W(xué)2000三、1(4.5分)】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è)好

17、?！颈本┖娇蘸教齑髮W(xué)2000二(10分)】18 .設(shè)計(jì)一數(shù)據(jù)結(jié)構(gòu)，用來(lái)表示某一銀行儲(chǔ)戶的基本信息：賬號(hào)、姓名、開戶年月日、儲(chǔ)蓄類型、存入累加數(shù)、利息、帳面總數(shù)?！菊憬髮W(xué)1994一、3(5分)】19 .寫出下面算法中帶標(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;ENDELSEBEGIN(4) FORi:=kTOnDO(5) ai:=ai+i

18、*i;(6) perm(a,k+1,n);END;設(shè)k的初值等于1。【北京郵電大學(xué)1997二(10分)】20 .分析下面程序段中循環(huán)語(yǔ)句的執(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分)】21 .下列算法對(duì)一n位二進(jìn)制數(shù)加1,假如無(wú)溢出，該算法的最壞時(shí)間復(fù)雜性是什么？并分析它的平均時(shí)間復(fù)雜性。TYPEnum=ARRAY1.nof0.1;PROCEDUREInc(VARa：numD;VARi：integer;BEGINi:=n；WHILEAi=1DOBEGINAi

19、:=0;i:=i-1;ENDENDAi:=1;ENDInc；【東南大學(xué)1998三(8分)1994二(15分)】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;WHILEpA.next<>qDOp:=pA.next;pA.next:=s;END;(ofB)BEGINB(h,g);B(g,h);END;(ofA)【東南大學(xué)1999二(10分)】23 .調(diào)

20、用下列C函數(shù)f(n)或PASACALE數(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=%dn",sum);)return(sum);【華中理工大學(xué)2000六(10分)】24 .設(shè)n是偶數(shù)，試計(jì)算運(yùn)行下列程序段后m的值并給出該程序段的時(shí)間復(fù)雜度。m:=0;FORi:=

21、1TOnDOFORj:=2*iTOnDOm:=m+1;【南京郵電大學(xué)2000一、1】25 .有下列運(yùn)行時(shí)間函數(shù)：(1) Ti(n)=1000;(2)T2(n)=n2+1000n;(3)Ts(n)=3n3+100n2+n+1;分別寫出相應(yīng)的大。表示的運(yùn)算時(shí)間?！炯止I(yè)大學(xué)1999二(12分)】26 .試給出下面兩個(gè)算法的運(yùn)算時(shí)間。(1) fori-1tondox-x+1END(2) fori-1tondoforj1tondox-x+1endend【中科院自動(dòng)化研究所1995二、2(6分)】27 .斐波那契數(shù)列Fn定義如下F0=0,Fl=1,Fn=Fn-1+Fn-2,n=2,3請(qǐng)就此斐波那契數(shù)列

22、，回答下列問題。(1) (7分)在遞歸計(jì)算Fn的時(shí)候，需要對(duì)較小的Fn-1,Fn-2,，F(xiàn)l,F0精確計(jì)算多少次？(2) (5分)如果用大O表示法，試給出遞歸計(jì)算Fn時(shí)遞歸函數(shù)的時(shí)間復(fù)雜度錄多少？【清華大學(xué)2000二(12分)】28 .將下列函數(shù)，按它們?cè)趎-8時(shí)的無(wú)窮大階數(shù)，從小到大排序。2n'n,n-n3+7n5,nlogn,2n/2,n3,logn,n1/2+logn,(3/2)n,、n，n!,n2+logn【中科院計(jì)算所1995】Whenyouareoldandgreyandfullofsleep,Andnoddingbythefire,takedownthisbook,Andslowlyread,anddreamofthesoftlookYoureyeshadonce,andoftheirshadowsdeep;Howmanylovedyourmomentsofgladgrace,Andlovedyourbea