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

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

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

3、率就越低B.(1),(2)C.(1),(4)D.(3)7.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為A.動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)C.線性結(jié)構(gòu)、非線性結(jié)構(gòu)8 .以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是A.循環(huán)隊列B.鏈表9 .以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(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):（）。【北方交通大學(xué)2000二、1（2分）】C.哈希表D.棧）?【北方交通大學(xué)2001一、1（2分）】A.廣義表B.二叉樹C.10.以下那一個術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)?A.棧B.哈希表C.稀疏矩陣）線索樹D.串【北方交通大學(xué)2001一、2（2分）】D.雙向鏈表11.在下面的程序

4、段中,分）】對x的賦值語句的頻度為（）【北京工商大學(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對換；其中n為正整數(shù)，則最后一行的語句頻度在最壞情況下是（）A.O（n）B.O（nlogn）C.O（n3）D.O（n2）【南京理工大學(xué)19981（2分）】13.以下哪個數(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.隊D.棧15 .下列數(shù)據(jù)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)?！颈本├砉ご髮W(xué)2001六、1（2分）】A.棧B.隊列C.完全二叉樹D.堆16 .連續(xù)存儲設(shè)計時，存儲單元的地址（）?！局猩酱髮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ù)處理的最小單位。（）【上海海運學(xué)院1998一、5（1分）】3 .數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關(guān)系；（）【北京郵電大學(xué)2002-1（1分）】4 .算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計算機有關(guān)。（）【大連海事大學(xué)2001一、10（1分）】5 .健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。（）【大連海事大學(xué)2001一、11（1分）】6 .算法可以用不同的語言描述，如果用C語言或PASCAL語言等高級語言來描述，則算法實際上就是程序了。（）【西安交通大學(xué)1996二、7（3分）】7 .程序一定是算法。（）【燕山大學(xué)1998二、2（2分）

7、并改錯】8 .數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。（）【山東師范大學(xué)20012（2分）】9 .數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實現(xiàn)有關(guān)。（）【華南理工大學(xué)2002一、1（1分）】10 .在順序存儲結(jié)構(gòu)中，有時也存儲數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。（）【華南理工大學(xué)2002一、2（1分）】11 .順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。（）【上海海運學(xué)院1999一、1（1分）】12 .數(shù)據(jù)結(jié)構(gòu)的基本操作的設(shè)置的最重要的準(zhǔn)則是，實現(xiàn)應(yīng)用程序與存儲結(jié)構(gòu)的獨立。（）【華南理工大學(xué)2002一、5（1分）】13 .數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的順序關(guān)系，它依賴于計算機的儲存結(jié)構(gòu).（）

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

9、工大學(xué)2001七、1（2分）】7 .數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的_（1）_禾口,以及它們之間的相互關(guān)系，并對與這種結(jié)構(gòu)定義相應(yīng)的_（3）_,設(shè)計出相應(yīng)的（4）?！疚靼搽娮涌萍即髮W(xué)1998二、2（3分）】8 .一個算法具有5個特性：（1）、（2）、（3）,有零個或多個輸入、有一個或多個輸出?！救A中理工大學(xué)2000一、2（5分）】【燕山大學(xué)1998一、2（5分）】9 .已知如下程序段FORi:=nDOWNTO1DO語句1x:=x+1;FORj:=nDOWNTODO語句2語句3語句4BEGINy:=y+1;END；語句1執(zhí)行的頻度為（1）;語句2執(zhí)行的頻度為（2）;語句3執(zhí)行的頻度為（3）;語句4執(zhí)行的頻度

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

11、程序段中帶有下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是（）【合肥工業(yè)大學(xué)2001（2分）i：=n*nWHILEi<>1DOi:=idiv2;14 .計算機執(zhí)行下面的語句時，語句s的執(zhí)行次數(shù)為。【南京理工大學(xué)2000二、1（1.5分）FOR（i=l;i<n-l;i+）FOR（j=n;j>=i;j-）s;15.下面程序段的時間復(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ù)的程序段，請將未完成的部分填入，使之完整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）=?！局锌圃很浖?997二、1（9分）】17 .在有n個選手參加的單循環(huán)賽中，總共將進(jìn)行場比賽。【合肥工業(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)系在計算機中有幾種表示方法？各有什么特點？【燕山大學(xué)1999二2（4分）3 .數(shù)據(jù)類型和抽象數(shù)據(jù)類型是如何定義的。二者有何相同和不同之處，抽象數(shù)據(jù)類型的主要特點是什么？使用抽象數(shù)據(jù)類型的主要好處是什么？【北京郵電大學(xué)1994一（8分）】4 .回答問題（每題2分）【山東工業(yè)大學(xué)1997（8分）】（1）在數(shù)據(jù)結(jié)構(gòu)課程中，數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲結(jié)構(gòu)及數(shù)據(jù)的運算之間存在著怎樣的關(guān)系？（2）若邏輯結(jié)構(gòu)相同但存儲結(jié)構(gòu)不同，則為不同的數(shù)據(jù)結(jié)構(gòu)。這樣的說法對嗎？舉例說明之。（3）在給定的邏輯結(jié)構(gòu)及其存儲表示上可以定義不同的運算集合，從而得到不同的數(shù)據(jù)結(jié)構(gòu)。這樣說法對嗎？舉例說明之。（4）

14、評價各種不同數(shù)據(jù)結(jié)構(gòu)的標(biāo)準(zhǔn)是什么？5 .評價一個好的算法，您是從哪幾方面來考慮的？【大連海事大學(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)、存儲結(jié)構(gòu)（3）抽象數(shù)據(jù)類型【哈爾濱工業(yè)大學(xué)2000、1（3分）】（4）算法的時間復(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 .對于一個數(shù)據(jù)結(jié)構(gòu)，一般包括哪三個方面的討論？【北京科技大學(xué)1999一、1(2分)】9 .當(dāng)你為解決某一問題而選擇數(shù)據(jù)結(jié)構(gòu)時，應(yīng)從哪些方面考慮？【西安電子北京科技大學(xué)2000】10 .若將數(shù)據(jù)結(jié)構(gòu)定義為一個二元組(D,R),說明符號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ù)的存儲結(jié)構(gòu)由哪四種基本的存儲方法實現(xiàn)？【山東科技大學(xué)2001、1(4分)】13 .若有100個學(xué)生，每個學(xué)生有學(xué)號，姓名，平均成績，采用什么樣的數(shù)據(jù)結(jié)構(gòu)最方便，寫出這些結(jié)構(gòu)？【山東師范大學(xué)1996二、2(2分)】1

16、4 .運算是數(shù)據(jù)結(jié)構(gòu)的一個重要方面。試舉一例，說明兩個數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲方式完全相同，只是對于運算的定義不同。因而兩個結(jié)構(gòu)具有顯著不同的特性，是兩個不同的結(jié)構(gòu)。【北京大學(xué)1998、1(5分)】15 .在編制管理通訊錄的程序時，什么樣的數(shù)據(jù)結(jié)構(gòu)合適？為什么？【長沙鐵道學(xué)院1998四、3(6分)】16 .試舉一例，說明對相同的邏輯結(jié)構(gòu)，同一種運算在不同的存儲方式下實現(xiàn)，其運算效率不同?！颈本├砉ご髮W(xué)2000三、1(4.5分)】17 .有實現(xiàn)同一功能的兩個算法A1和A2,其中A1的時間復(fù)雜度為Tl=O(2n),A2的時間復(fù)雜度為T2=O(n2),僅就時間復(fù)雜度而言，請具體分析這兩個算法哪一個好

17、。【北京航空航天大學(xué)2000二(10分)】18 .設(shè)計一數(shù)據(jù)結(jié)構(gòu)，用來表示某一銀行儲戶的基本信息：賬號、姓名、開戶年月日、儲蓄類型、存入累加數(shù)、利息、帳面總數(shù)?！菊憬髮W(xué)1994一、3(5分)】19 .寫出下面算法中帶標(biāo)號語句的頻度。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)語句的執(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 .下列算法對一n位二進(jìn)制數(shù)加1,假如無溢出，該算法的最壞時間復(fù)雜性是什么？并分析它的平均時間復(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的功能和時間復(fù)雜性PROCEDUREA(h,g:pointer);(h,g分別為單循環(huán)鏈表(singlelinkedcircularlist)中兩個結(jié)點指針)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)時的輸出結(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ù)，試計算運行下列程序段后m的值并給出該程序段的時間復(fù)雜度。m:=0;FORi:=

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

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