![數(shù)據(jù)結(jié)構(gòu)考試題庫(含參考答案)46402_第1頁](http://file3.renrendoc.com/fileroot_temp3/2022-3/3/661f0376-d46b-4886-b95d-3455e569f8c5/661f0376-d46b-4886-b95d-3455e569f8c51.gif)
![數(shù)據(jù)結(jié)構(gòu)考試題庫(含參考答案)46402_第2頁](http://file3.renrendoc.com/fileroot_temp3/2022-3/3/661f0376-d46b-4886-b95d-3455e569f8c5/661f0376-d46b-4886-b95d-3455e569f8c52.gif)
![數(shù)據(jù)結(jié)構(gòu)考試題庫(含參考答案)46402_第3頁](http://file3.renrendoc.com/fileroot_temp3/2022-3/3/661f0376-d46b-4886-b95d-3455e569f8c5/661f0376-d46b-4886-b95d-3455e569f8c53.gif)
![數(shù)據(jù)結(jié)構(gòu)考試題庫(含參考答案)46402_第4頁](http://file3.renrendoc.com/fileroot_temp3/2022-3/3/661f0376-d46b-4886-b95d-3455e569f8c5/661f0376-d46b-4886-b95d-3455e569f8c54.gif)
![數(shù)據(jù)結(jié)構(gòu)考試題庫(含參考答案)46402_第5頁](http://file3.renrendoc.com/fileroot_temp3/2022-3/3/661f0376-d46b-4886-b95d-3455e569f8c5/661f0376-d46b-4886-b95d-3455e569f8c55.gif)
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)
文檔簡介
1、.第1章緒論一、選擇題1.算法的計算量的大小稱為計算的()?!颈本┼]電大學(xué)2000二、3(20/8分)】A效率B.復(fù)雜性C.現(xiàn)實性D.難度2.算法的時間復(fù)雜度取決于( )【中科院計算所1998二、1(2分)】A問題的規(guī)模B.待處理數(shù)據(jù)的初態(tài)C. A和B3.計算機算法指的是(1),它必須具備(2) 這三個特性。(1) A計算方法B.排序方法C.解決問題的步驟序列D.調(diào)度方法(2) A可執(zhí)行性、可移植性、可擴充性B.可執(zhí)行性、確定性、有窮性C.確定性、有窮性、穩(wěn)定性D.易讀性、穩(wěn)定性、安全性【南京理工大學(xué)1999一、1(2分) 【武漢交通科技大學(xué)1996一、1(4分)】4一個算法應(yīng)該是()?!局猩?/p>
2、大學(xué)1998二、1(2分)】A程序B問題求解步驟的描述C要滿足五個基本特性DA和C.5.下面關(guān)于算法說法錯誤的是()【南京理工大學(xué)2000一、1(1.5分)】A算法最終必須由計算機程序?qū)崿F(xiàn)B.為解決某問題的算法同為該問題編寫的程序含義是相同的C.算法的可行性是指指令不能有二義性D.以上幾個都是錯誤的6.下面說法錯誤的是()【南京理工大學(xué)2000一、2(1.5分)】(1)算法原地工作的含義是指不需要任何額外的輔助空間(2)在相同的規(guī)模n下,復(fù)雜度O(n)的算法在時間上總是優(yōu)于復(fù)雜度O(2n)的算法(3)所謂時間復(fù)雜度是指最壞情況下,估算算法執(zhí)行時間的一個上界(4)同一個算法,實現(xiàn)語言的級別越高,
3、執(zhí)行效率就越低A(1)B.(1),(2)C.(1),(4)D.(3)7從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為()兩大類。 【武漢交通科技大學(xué)1996一 、4(2分)】A動態(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ù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是()?!颈狈浇煌ù髮W(xué)2000二、1(2分)】A循環(huán)隊列B.鏈表C.哈希表D.棧9以下數(shù)據(jù)結(jié)構(gòu)中,哪一個是線性結(jié)構(gòu)()?【北方交通大學(xué)2001一、1(2分)】A廣義表B.二叉樹C.稀疏矩陣D.串10以下那一個術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)?()【北方交通大學(xué)2001一、2(2分)】A棧B.哈希表C.線索樹D.雙向鏈表11在下面的程序段
4、中,對x的賦值語句的頻度為()【北京工商大學(xué)2001一、10(3分)】FOR i:=1TOnDOFOR j:=1TOnDOx:=x+1;AO(2n)BO(n)CO(n2)DO(log2n)12程序段FORi:=n-1DOWNTO1DOFOR j:=1 TO i DOIF AjAj+1THENAj與Aj+1對換;其中n為正整數(shù),則最后一行的語句頻度在最壞情況下是()A. O(n)B. O(nlogn)C. O(n3)D. O(n2)【南京理工大學(xué)1998一、1(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)的是()?!疚靼搽娮涌萍即髮W(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】【山東師范大學(xué)2001一、1(2分)】2.記錄是
6、數(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分)并改錯】8數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)的實際存儲形
7、式。()【山東師范大學(xué)2001一、2(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). ()【上海海運學(xué)院1998一、1(1分)】三、填空1數(shù)據(jù)的物理結(jié)構(gòu)
8、包括數(shù)據(jù)元素的表示和數(shù)據(jù)元素關(guān)系的表示?!狙嗌酱髮W(xué)1998一、1(2分)】2.對于給定的n個元素,可以構(gòu)造出的邏輯結(jié)構(gòu)有集合,線性結(jié)構(gòu),樹形結(jié)構(gòu),_圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)_四種?!局锌圃河嬎闼?999二、1(4分)】3數(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一個數(shù)據(jù)結(jié)構(gòu)在計算機中的表示(或稱映像)稱為存儲結(jié)構(gòu)(又?jǐn)?shù)據(jù)的物理結(jié)構(gòu))?!救A中理工大學(xué)2000一、1(1分)】5抽象數(shù)據(jù)類型的定義僅取決于它的一組_邏輯特性_,而與_在計算機內(nèi)部如何表示和實現(xiàn)_無關(guān),即不論其內(nèi)部結(jié)構(gòu)如何變化,
9、只要它的_數(shù)學(xué)特性_不變,都不影響其外部使用。【山東大學(xué)2001三、3(2分)】6數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標(biāo)是算法的時間復(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)的_操作(運算)_,設(shè)計出相應(yīng)的_算法?!疚靼搽娮涌萍即髮W(xué)1998二、2(3分)】8 一個算法具有5個特性:有窮性、確定性、可行性,有零個或多個輸入、有一個或多個輸出 ?!救A中理工大學(xué)2000一、2(5分)】 【燕山大學(xué)1998一、2(5分)】9已知如下程序段FOR i:= nDOWNTO1DO語句1BEGINx:=x
10、+1;語句2FOR j:=nDOWNTOiDO語句3y:=y+1;語句4END;語句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)/6_(表示為n的函數(shù))FORi:TOnDOFORj:TOiDOFORk:1TOjDO:delta;【北京工業(yè)大學(xué)1999一、6(2分)】11.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是:log2n【合肥工業(yè)大學(xué)1999三、1(2分)】i:=1;
11、WHILE in DOi:=i*2;12.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是(nlog2n)?!竞戏使I(yè)大學(xué)2000三、1(2分)】i:=1;WHILE in BEGINFOR j:=1 TO n DOx:=x+1;i:=i*2END;13.下面程序段中帶有下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是(log2n2)【合肥工業(yè)大學(xué)2001三、1(2分)】i:=n*nWHILE i1DOi:=i div 2;14.計算機執(zhí)行下面的語句時,語句s的執(zhí)行次數(shù)為_(n+3)(n-2)/2 _?!灸暇├砉ご髮W(xué)2000二、1(1.5分)】FOR(i=l;i=i;j-)s;15.下面程序段的時間復(fù)雜度為_O
12、(n)_。(n1)sum=1;for (i=0;sumn;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ù)的程序段,請將未完成的部分填入,使之完整int f(m,n)int m,n; if(m=1)return1;if(n=1)return1;if(mn)return f(m,m);if (m=n)return 1+f(m,n-1);return f(m.n-1)+f(m-n
13、,n);執(zhí)行程序,f(6,4)=9。 【中科院軟件所1997二、1(9分)】17.在有n個選手參加的單循環(huán)賽中,總共將進行_n(n-1)/2_場比賽?!竞戏使I(yè)大學(xué)1999三、8(2分)】四、應(yīng)用題1.數(shù)據(jù)結(jié)構(gòu)是一門研究什么內(nèi)容的學(xué)科?【燕山大學(xué)1999二、1(4分)】2.數(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ù)
14、結(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)評價各種不同數(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
15、(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】【同濟大學(xué)1998】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ū)別?【哈爾
16、濱工業(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分)】14.運算是數(shù)據(jù)結(jié)構(gòu)的一個重要方面。試舉一例,說明兩個數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲方式完全相同,只是對于運算的定義不同。因而兩個結(jié)構(gòu)具有顯著不同的特性,是兩個不同的結(jié)構(gòu)?!颈本┐髮W(xué)1998一、1(5分)】15.在編制管理通訊錄的程序時,什么樣的數(shù)據(jù)結(jié)構(gòu)合適?為什么?【 長沙鐵道學(xué)院1998四、3(6分)】16.試舉一例,說明對相同的邏輯結(jié)構(gòu),同一種運
17、算在不同的存儲方式下實現(xiàn),其運算效率不同。【北京理工大學(xué)2000三、1(4.5分)】17.有實現(xiàn)同一功能的兩個算法A1和A2,其中A1的時間復(fù)雜度為Tl=O(2n),A2的時間復(fù)雜度為T2=O(n2),僅就時間復(fù)雜度而言,請具體分析這兩個算法哪一個好。【北京航空航天大學(xué)2000二(10分)】18設(shè)計一數(shù)據(jù)結(jié)構(gòu),用來表示某一銀行儲戶的基本信息: 賬號、姓名、開戶年月日、儲蓄類型 、存入累加數(shù)、利息、帳面總數(shù)?!菊憬髮W(xué) 1994 一 、3(5分)】19.寫出下面算法中帶標(biāo)號語句的頻度。TYPEar=ARRAY1.n OF datatype;PROCEDUREperm( a: ar; k, n:
18、integer);VARx: datatype;i:integer;BEGIN(1)IF k=nTHEN BEGIN(2)FORi:=1TOn DO(3)write (ai);writeln;ENDELSE BEGIN(4)FORi:=kTOnDO(5)ai:=ai+i*i;(6)perm (a, k+1, n);END;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(in) AND (sn);【北京郵電大學(xué)1998四、1(5分)】21下列算
19、法對一n位二進制數(shù)加1,假如無溢出,該算法的最壞時間復(fù)雜性是什么?并分析它的平均時間復(fù)雜性。TYPEnum=ARRAY 1.n of 0.1;PROCEDUREInc(VAR a:num);VARi:integer;BEGINi:=n;WHILEAi=1DOBEGINAi:=0;i:=i-1;END;END;Ai:=1;END Inc;【東南大學(xué)1998三(8分)1994二(15分)】22.閱讀下列算法,指出算法A的功能和時間復(fù)雜性PROCEDUREA (h,g:pointer);(h,g分別為單循環(huán)鏈表(single linkedcircular list)中兩個結(jié)點指針)PROCEDURE
20、B(s,q:pointer);VAR p:pointer;BEGINp:=s;WHILE p.nextq DO p:=p.next;p.next:=s;END;(of B)BEGINB(h,g);B(g,h);END;(of A)【東南大學(xué)1999二(10分)】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)時的輸出結(jié)果 。C函數(shù):int f(intn) int i,j,k,sum= 0;for(i=l; ii-1; j-)for(k=1;kj+1;k+
21、)sum+;printf(sum=%dn,sum);return (sum);【華中理工大學(xué)2000六(10分)】24設(shè)n是偶數(shù),試計算運行下列程序段后m的值并給出該程序段的時間復(fù)雜度。m:=0;FORi:=1TOnDOFORj:=2*iTOnDOm:=m+1;【南京郵電大學(xué)2000一、1】25有下列運行時間函數(shù):(1)T1(n)=1000;(2)T2(n)=n2+1000n;(3)T3(n)=3n3+100n2+n+1;分別寫出相應(yīng)的大O表示的運算時間?!炯止I(yè)大學(xué)1999二(12分)】26.試給出下面兩個算法的運算時間。(1)fori1tondoxx+1END(2)for i1tondo
22、forj1tondoxx+1endend【中科院自動化研究所1995二、2(6分)】27.斐波那契數(shù)列Fn定義如下F0=0,F(xiàn)l=1,F(xiàn)n=Fn-1+Fn-2,n=2,3.請就此斐波那契數(shù)列,回答下列問題。(1)(7分)在遞歸計算Fn的時候,需要對較小的Fn-1,F(xiàn)n-2,, Fl, F0精確計算多少次?(2)(5分)如果用大O表示法,試給出遞歸計算Fn時遞歸函數(shù)的時間復(fù)雜度錄多少?【清華大學(xué)2000二(12分)】28將下列函數(shù),按它們在n時的無窮大階數(shù),從小到大排序。n, n-n3+7n5, nlogn, 2n/2, n3, logn, n1/2+logn, (3/2)n,n!, n2+lo
23、gn【中科院計算所1995】第1章緒論一、選擇題1.B2.C3.1C3.2B4.B5.D6.C7.C8.D9.D10.A11.C12.D13.D14.A15.C16.A17.C二、判斷題1. 2. 3.4.5. 6. 7. 8. 9.10.11.12. 13. 三填空題1數(shù)據(jù)元素數(shù)據(jù)元素間關(guān)系2集合線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。3數(shù)據(jù)的組織形式,即數(shù)據(jù)元素之間邏輯關(guān)系的總體。而邏輯關(guān)系是指數(shù)據(jù)元素之間的關(guān)聯(lián)方式或稱“鄰接關(guān)系”。4表示(又稱映像)。5(1)邏輯特性(2)在計算機內(nèi)部如何表示和實現(xiàn)(3)數(shù)學(xué)特性。6算法的時間復(fù)雜度和空間復(fù)雜度。7(1)邏輯結(jié)構(gòu)(2)物理結(jié)構(gòu)(3)操作(運算
24、)(4)算法。8(1)有窮性(2)確定性 (3)可行性。9(1)n+1(2)n(3)n(n+3)/2(4)n(n+1)/2。101+(1+2+(1+2+3)+(1+2+n)=n(n+1)(n+2)/6O(n3)11. log2n12. nlog2n13. log2n214. (n+3)(n-2)/215. O(n)16.(1)1(2)1(3)f(m,n-1)(4)n917. n(n-1)/2四應(yīng)用題1數(shù)據(jù)結(jié)構(gòu)是一門研究在非數(shù)值計算的程序設(shè)計問題中,計算機的操作對象及對象間的關(guān)系和施加于對象的操作等的學(xué)科。2四種表示方法(1)順序存儲方式。數(shù)據(jù)元素順序存放,每個存儲結(jié)點只含一個元素。存儲位置反映
25、數(shù)據(jù)元素間的邏輯關(guān)系。存儲密度大,但有些操作(如插入、刪除)效率較差。(2)鏈?zhǔn)酱鎯Ψ绞?。每個存儲結(jié)點除包含數(shù)據(jù)元素信息外還包含一組(至少一個)指針。指針反映數(shù)據(jù)元素間的邏輯關(guān)系。這種方式不要求存儲空間連續(xù),便于動態(tài)操作(如插入、刪除等),但存儲空間開銷大(用于指針),另外不能折半查找等。(3)索引存儲方式。除數(shù)據(jù)元素存儲在一地址連續(xù)的內(nèi)存空間外,尚需建立一個索引表,索引表中索引指示存儲結(jié)點的存儲位置(下標(biāo))或存儲區(qū)間端點(下標(biāo)),兼有靜態(tài)和動態(tài)特性。(4)散列存儲方式。通過散列函數(shù)和解決沖突的方法,將關(guān)鍵字散列在連續(xù)的有限的地址空間內(nèi),并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的存儲地址,這種存儲
26、方式稱為散列存儲。其特點是存取速度快,只能按關(guān)鍵字隨機存取,不能順序存取,也不能折半存取。3數(shù)據(jù)類型是程序設(shè)計語言中的一個概念,它是一個值的集合和操作的集合。如C語言中的整型、實型、字符型等。整型值的范圍(對具體機器都應(yīng)有整數(shù)范圍),其操作有加、減、乘、除、求余等。實際上數(shù)據(jù)類型是廠家提供給用戶的已實現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)。“抽象數(shù)據(jù)類型(ADT)”指一個數(shù)學(xué)模型及定義在該模型上的一組操作?!俺橄蟆钡囊饬x在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。抽象數(shù)據(jù)類型的定義僅取決于它的邏輯特性,而與其在計算機內(nèi)部如何表示和實現(xiàn)無關(guān)。無論其內(nèi)部結(jié)構(gòu)如何變化,只要它的數(shù)學(xué)特性不變就不影響它的外部使用。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實質(zhì)上
27、是一個概念。此外,抽象數(shù)據(jù)類型的范圍更廣,它已不再局限于機器已定義和實現(xiàn)的數(shù)據(jù)類型,還包括用戶在設(shè)計軟件系統(tǒng)時自行定義的數(shù)據(jù)類型。使用抽象數(shù)據(jù)類型定義的軟件模塊含定義、表示和實現(xiàn)三部分,封裝在一起,對用戶透明(提供接口),而不必了解實現(xiàn)細(xì)節(jié)。抽象數(shù)據(jù)類型的出現(xiàn)使程序設(shè)計不再是“藝術(shù)”,而是向“科學(xué)”邁進了一步。4(1)數(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é)
28、構(gòu)相同但存儲不同,可以是不同的數(shù)據(jù)結(jié)構(gòu)。例如,線性表的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu),采用順序存儲結(jié)構(gòu)為順序表,而采用鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。(3)棧和隊列的邏輯結(jié)構(gòu)相同,其存儲表示也可相同(順序存儲和鏈?zhǔn)酱鎯Γ?,但由于其運算集合不同而成為不同的數(shù)據(jù)結(jié)構(gòu)。(4)數(shù)據(jù)結(jié)構(gòu)的評價非常復(fù)雜,可以考慮兩個方面,一是所選數(shù)據(jù)結(jié)構(gòu)是否準(zhǔn)確、完整的刻劃了問題的基本特征;二是是否容易實現(xiàn)(如對數(shù)據(jù)分解是否恰當(dāng);邏輯結(jié)構(gòu)的選擇是否適合于運算的功能,是否有利于運算的實現(xiàn);基本運算的選擇是否恰當(dāng)。)5評價好的算法有四個方面。一是算法的正確性;二是算法的易讀性;三是算法的健壯性;四是算法的時空效率(運行)。6(1)見上面題3
29、(2)見上面題4(3)見上面題3(4)算法的時間復(fù)雜性是算法輸入規(guī)模的函數(shù)。算法的輸入規(guī)?;騿栴}的規(guī)模是作為該算法輸入的數(shù)據(jù)所含數(shù)據(jù)元素的數(shù)目,或與此數(shù)目有關(guān)的其它參數(shù)。有時考慮算法在最壞情況下的時間復(fù)雜度或平均時間復(fù)雜度。(5)算法是對特定問題求解步驟的描述,是指令的有限序列,其中每一條指令表示一個或多個操作。算法具有五個重要特性:有窮性、確定性、可行性、輸入和輸出。(6)頻度。在分析算法時間復(fù)雜度時,有時需要估算基本操作的原操作,它是執(zhí)行次數(shù)最多的一個操作,該操作重復(fù)執(zhí)行的次數(shù)稱為頻度。7集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形或網(wǎng)狀結(jié)構(gòu)。8邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、操作(運算)。9通??紤]算法所需要的存
30、儲空間量和算法所需要的時間量。后者又涉及到四方面:程序運行時所需輸入的數(shù)據(jù)總量,對源程序進行編譯所需時間,計算機執(zhí)行每條指令所需時間和程序中指令重復(fù)執(zhí)行的次數(shù)。10D是數(shù)據(jù)元素的有限集合,S是D上數(shù)據(jù)元素之間關(guān)系的有限集合。11“數(shù)據(jù)結(jié)構(gòu)”這一術(shù)語有兩種含義,一是作為一門課程的名稱;二是作為一個科學(xué)的概念。作為科學(xué)概念,目前尚無公認(rèn)定義,一般認(rèn)為,討論數(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見上面題2。13將學(xué)號、姓名、平均成績看成一個記錄(元素,
31、含三個數(shù)據(jù)項),將100個這樣的記錄存于數(shù)組中。因一般無增刪操作,故宜采用順序存儲。typedefstructintnum;/學(xué)號charname8;/姓名floatscore;/平均成績node;node student100;14.見上面題4(3)。15應(yīng)從兩方面進行討論:如通訊錄較少變動(如城市私人電話號碼),主要用于查詢,以順序存儲較方便,既能順序查找也可隨機查找;若通訊錄經(jīng)常有增刪操作,用鏈?zhǔn)酱鎯Y(jié)構(gòu)較為合適,將每個人的情況作為一個元素(即一個結(jié)點存放一個人),設(shè)姓名作關(guān)鍵字,鏈表安排成有序表,這樣可提高查詢速度。16線性表中的插入、刪除操作,在順序存儲方式下平均移動近一半的元素,時
32、間復(fù)雜度為O(n);而在鏈?zhǔn)酱鎯Ψ绞较拢迦牒蛣h除時間復(fù)雜度都是O(1)。17對算法A1和A2的時間復(fù)雜度T1和T2取對數(shù),得nlog2和2logn。顯然,算法A2好于A1。18.structnodeintyear,month,day; ;typedef structintnum;/帳號charname8;/姓名structnode date;/開戶年月日inttag;/儲蓄類型,如:0-零存,1-一年定期floatput;/存入累加數(shù);floatinterest;/利息floattotal;/帳面總數(shù)count;19(1)n(2)n+1(3)n(4)(n+4)(n-1)/2(5)(n+2)(n-1)/2(6)n-1這是一個遞歸調(diào)用,因k的初值為1,由語句(6)知,每次調(diào)用k增1,故第(1)語句執(zhí)行n次。(2)是FOR循環(huán)語句,在滿足(1)的條件下執(zhí)行,該語句進入循環(huán)體(3)n次,加上最后一次判斷出界,故執(zhí)行了n+1次。(4)也是循環(huán)語句,當(dāng)k=1時判斷n+1次(進入循環(huán)體(5)n次),k=2時判斷
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年中國微電腦計時儀市場調(diào)查研究報告
- 2025-2030年堅果加工廢水處理設(shè)備企業(yè)制定與實施新質(zhì)生產(chǎn)力戰(zhàn)略研究報告
- 2025-2030年戶外防水針織風(fēng)衣企業(yè)制定與實施新質(zhì)生產(chǎn)力戰(zhàn)略研究報告
- 2025年油茶皂角項目可行性研究報告
- 2025年豪華游艇項目可行性研究報告
- 2025年熱風(fēng)槍鐵管芯項目可行性研究報告
- 2025年中國洗衣機進排水管市場調(diào)查研究報告
- 2025年中國單路計量調(diào)速秤市場調(diào)查研究報告
- 2025年光多用表項目可行性研究報告
- 2025至2030年超強渦輪便攜式呼吸機項目投資價值分析報告
- 2025年湖南省長沙市中考數(shù)學(xué)模擬試卷(附答案解析)
- 五級人工智能訓(xùn)練師(初級)職業(yè)技能等級認(rèn)定考試題庫(含答案)
- 2022年內(nèi)蒙古呼和浩特市中考化學(xué)真題(解析版)
- 血栓性微血管病的診治
- 綜合客運樞紐換乘區(qū)域設(shè)施設(shè)備配置要求JTT1066-2016
- 中國急性缺血性卒中診治指南(2023)解讀
- 2024PowerTitan系列運維指導(dǎo)儲能系統(tǒng)運維指導(dǎo)
- 沸石轉(zhuǎn)輪知識講解
- 固定資產(chǎn)盤點報告醫(yī)院版
- 中國內(nèi)部審計準(zhǔn)則及指南
- 2024年ISTQB認(rèn)證筆試歷年真題薈萃含答案
評論
0/150
提交評論