

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、自考數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案自考數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案本章的重點(diǎn)是了解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算三方面的概念及相互關(guān)系,難點(diǎn)是算法復(fù)雜度的分析方法。需要達(dá)到層次的基本概念和術(shù)語(yǔ)有:數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)結(jié)構(gòu)。特別是數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及數(shù)據(jù)運(yùn)算的含義及其相互關(guān)系。數(shù)據(jù)結(jié)構(gòu)的兩大類邏輯結(jié)構(gòu)和四種常用的存儲(chǔ)表示方法。需要達(dá)到層次的內(nèi)容有算法、算法的時(shí)間復(fù)雜度和空間復(fù)雜度、最壞的和平均時(shí)間復(fù)雜度等概念,算法描述和算法分析
2、的方法、對(duì)一般的算法要能分析出時(shí)間復(fù)雜度。對(duì)于基本概念,仔細(xì)看書就能夠理解,這里簡(jiǎn)單提一下:數(shù)據(jù)就是指能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的信息的載體。數(shù)據(jù)元素是數(shù)據(jù)的基本單位,有時(shí)一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。如整數(shù)這個(gè)集合中,10這個(gè)數(shù)就可稱是一個(gè)數(shù)據(jù)元素.又比如在一個(gè)數(shù)據(jù)庫(kù)(關(guān)系式數(shù)據(jù)庫(kù))中,一個(gè)記錄可稱為一個(gè)數(shù)據(jù)元素,而這個(gè)元素中的某一字段就是一個(gè)數(shù)據(jù)項(xiàng)。數(shù)據(jù)結(jié)構(gòu)的定義雖然沒(méi)有標(biāo)準(zhǔn),但是它包
3、括以下三方面內(nèi)容:邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、和對(duì)數(shù)據(jù)的操作。這一段比較重要,我用自己的語(yǔ)言來(lái)說(shuō)明一下,大家看看是不是這樣。比如一個(gè)表(數(shù)據(jù)庫(kù)),我們就稱它為一個(gè)數(shù)據(jù)結(jié)構(gòu),它由很多記錄(數(shù)據(jù)元素)組成,每個(gè)元素又包括很多字段(數(shù)據(jù)項(xiàng))組成。那么這張表的邏輯結(jié)構(gòu)是怎么樣的呢我們分析數(shù)據(jù)結(jié)構(gòu)都是從結(jié)點(diǎn)(其實(shí)也就是元素、記錄、頂點(diǎn),雖然在各種情況下所用名字不同,但說(shuō)的是同一個(gè)東東)之間的關(guān)系來(lái)分析的,對(duì)于這個(gè)表中的任一個(gè)記錄(結(jié)點(diǎn)),它只有一個(gè)直接前
4、趨,只有一個(gè)直接后繼(前趨后繼就是前相鄰后相鄰的意思),整個(gè)表只有一個(gè)開(kāi)始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn),那我們知道了這些關(guān)系就能明白這個(gè)表的邏輯結(jié)構(gòu)了。而存儲(chǔ)結(jié)構(gòu)則是指用計(jì)算機(jī)語(yǔ)言如何表示結(jié)點(diǎn)之間的這種關(guān)系。如上面的表,在計(jì)算機(jī)語(yǔ)言中描述為連續(xù)存放在一片內(nèi)存單元中,還是隨機(jī)的存放在內(nèi)存中再用指針把它們鏈接在一起,這兩種表示法就成為兩種不同的存儲(chǔ)結(jié)構(gòu)。(注意,在本課程里,我們只在高級(jí)語(yǔ)言的層次上討論存儲(chǔ)結(jié)構(gòu)。)第三個(gè)概念就是對(duì)數(shù)據(jù)的運(yùn)算,比如一張表
5、格,我們需要進(jìn)行查找,增加,修改,刪除記錄等工作,而怎么樣才能進(jìn)行這樣的操作呢這也就是數(shù)據(jù)的運(yùn)算,它不僅僅是加減乘除這些算術(shù)運(yùn)算了,在數(shù)據(jù)結(jié)構(gòu)中,這些運(yùn)算常常涉及算法問(wèn)題。弄清了以上三個(gè)問(wèn)題,就可以弄清數(shù)據(jù)結(jié)構(gòu)這個(gè)概念。通常我們就將數(shù)據(jù)的邏輯結(jié)構(gòu)簡(jiǎn)稱為數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)的邏輯結(jié)構(gòu)分兩大類:線性結(jié)構(gòu)和非線性結(jié)構(gòu)(這兩個(gè)很容易理解)數(shù)據(jù)的存儲(chǔ)方法有四種:順序存儲(chǔ)方法、鏈接存儲(chǔ)方法、索引存儲(chǔ)方法和散列存儲(chǔ)方法。下一個(gè)是難點(diǎn)問(wèn)題,就是算法的描述和分
6、析,主要是算法復(fù)雜度的分析方法及其運(yùn)用。首先了解一下幾個(gè)概念。一個(gè)是時(shí)間復(fù)雜度,一個(gè)是漸近時(shí)間復(fù)雜度。前者是某個(gè)算法的時(shí)間耗費(fèi),它是該算法所求解問(wèn)題規(guī)模n的函數(shù),而后者是指當(dāng)問(wèn)題規(guī)模趨向無(wú)窮大時(shí),該算法時(shí)間復(fù)雜度的數(shù)量級(jí)。當(dāng)我們?cè)u(píng)價(jià)一個(gè)算法的時(shí)間性能時(shí),主要標(biāo)準(zhǔn)就是算法的漸近時(shí)間復(fù)雜度,因此,在算法分析時(shí),往往對(duì)兩者不予區(qū)分,經(jīng)常是將漸近時(shí)間復(fù)雜度T(n)=O(f(n)簡(jiǎn)稱為時(shí)間復(fù)雜度,其中的f(n)一般是算法中頻度最大的語(yǔ)句頻度?!羲?/p>
7、引存儲(chǔ)方法:除建立存儲(chǔ)結(jié)點(diǎn)信息外,還建立附加的索引表來(lái)標(biāo)識(shí)結(jié)點(diǎn)的地址?!羯⒘写鎯?chǔ)方法:就是根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。1.4設(shè)三個(gè)函數(shù)fgh分別為f(n)=100n^3n^21000g(n)=25n^35000n^2h(n)=n^1.55000nlgn請(qǐng)判斷下列關(guān)系是否成立:(1)f(n)=O(g(n))(2)g(n)=O(f(n))(3)h(n)=O(n^1.5)(4)h(n)=O(nlgn)◆(1)成立?!筮@里我們復(fù)
8、習(xí)一下漸近時(shí)間復(fù)雜度的表示法T(n)=O(f(n)),這里的“O“是數(shù)學(xué)符號(hào),它的嚴(yán)格定義是“若T(n)和f(n)是定義在正整數(shù)集合上的兩個(gè)函數(shù),則T(n)=O(f(n))表示存在正的常數(shù)C和[size=1]n[size=3]0使得當(dāng)n≥[size=1]n[size=3]0時(shí)都滿足0≤T(n)≤Cf(n)?!坝萌菀桌斫獾脑捳f(shuō)就是這兩個(gè)函數(shù)當(dāng)整型自變量n趨向于無(wú)窮大時(shí),兩者的比值是一個(gè)不等于0的常數(shù)。這么一來(lái),就好計(jì)算了吧。第(1)題中兩
9、個(gè)函數(shù)的最高次項(xiàng)都是n^3因此當(dāng)n→∞時(shí),兩個(gè)函數(shù)的比值是一個(gè)常數(shù),所以這個(gè)關(guān)系式是成立的?!簦?)成立?!簦?)成立?!簦?)不成立。1.5設(shè)有兩個(gè)算法在同一機(jī)器上運(yùn)行,其執(zhí)行時(shí)間分別為100n^2和2^n要使前者快于后者,n至少要多大◆15◇最簡(jiǎn)單最笨的辦法就是拿自然數(shù)去代唄。假定n取為10,則前者的值是10000,后者的值是1024小于前者,那我們就加個(gè)5,用15代入得前者為22500,后者為32768,已經(jīng)比前者大但相差不多,那
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案
- 數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案
- 數(shù)據(jù)結(jié)構(gòu)課程課后習(xí)題答案
- 數(shù)據(jù)結(jié)構(gòu)課程--課后習(xí)題答案
- 數(shù)據(jù)結(jié)構(gòu)課后習(xí)題
- 數(shù)據(jù)結(jié)構(gòu)課后習(xí)題2
- 數(shù)據(jù)結(jié)構(gòu)課后答案
- 數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏版課后習(xí)題答案
- 數(shù)據(jù)結(jié)構(gòu)用c語(yǔ)言描述課后習(xí)題答案
- 嚴(yán)蔚敏版數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案
- 數(shù)據(jù)結(jié)構(gòu)課后習(xí)題集答案解析 _0
- 數(shù)據(jù)結(jié)構(gòu)習(xí)題答案
- 嚴(yán)蔚敏 數(shù)據(jù)結(jié)構(gòu)課后習(xí)題及答案解析
- 數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案第六章
- 嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)課后習(xí)題及答案解析
- 數(shù)據(jù)結(jié)構(gòu)課后習(xí)題(第1章)
- 23490數(shù)據(jù)結(jié)構(gòu)習(xí)題答案
- 數(shù)據(jù)結(jié)構(gòu)習(xí)題(有答案)
- 數(shù)據(jù)結(jié)構(gòu)習(xí)題及答案
- 數(shù)據(jù)結(jié)構(gòu)課本習(xí)題答案
評(píng)論
0/150
提交評(píng)論