ds第一章緒論ppt課件-資料下載頁(yè)
2025-05-05 12:10本頁(yè)面
【正文】 121 2)3)(2(3. . . . . .)2()1()1(1niinjninnnnnin算法和算法分析典型題解析 應(yīng)用題 10： 在有 n個(gè)選手參加的單循環(huán)賽中 ， 總共進(jìn)行（ ） 場(chǎng)比賽 ？ ? 解答：因?yàn)槊總€(gè)人都要和其他 n1個(gè)人進(jìn)行一次比賽，所以是 n*(n1)，但甲和乙比賽和乙和甲比賽是相同的，所以要去掉，所以總共進(jìn)行 n*(n1)/2場(chǎng)比賽。 算法和算法分析典型題解析 應(yīng)用題 11： 有實(shí)現(xiàn)同一功能的兩個(gè)算法 A1和 A2， 其中 A1的時(shí)間復(fù)雜度為 T1=O(2n)， A2的時(shí)間復(fù)雜度為 T2=O(n2)，僅就時(shí)間復(fù)雜度而言 ， 請(qǐng)具體分析哪一個(gè)算法好 。 解答：比較兩個(gè)復(fù)雜度函數(shù) 2n和 n2， 顯然有： 當(dāng) n=1時(shí) ， 2112,則算法 A2好于算法 A1； 當(dāng) n=2時(shí) ， 22=22,當(dāng) n=4時(shí) ， 24=42 ， 則兩個(gè)算法的時(shí)間復(fù)雜度相同； 當(dāng) n=3時(shí) ， 2332,則算法 A1好于算法 A2； 當(dāng) n4時(shí) ， 2nn2,則算法 A2好于算法 A1. 算法和算法分析典型題解析 應(yīng)用題 12： 度量一個(gè)算法的執(zhí)行時(shí)間通常有幾種方法 ？ 各有何優(yōu)缺點(diǎn) ？ 解答：通常有兩種方法：事后統(tǒng)計(jì)和事前分析 。 事后統(tǒng)計(jì)方法的優(yōu)點(diǎn)是比較精確 ， 缺點(diǎn)是必須根據(jù)算法編寫(xiě)相應(yīng)的程序 ， 而且所得的時(shí)間依賴于計(jì)算機(jī)的軟硬件環(huán)境 ， 有時(shí)候容易掩蓋算法本身的優(yōu)劣 。 事前分析方法的優(yōu)點(diǎn)是不必運(yùn)行程序就可以從復(fù)雜度角度比較算法的優(yōu)劣 ， 缺點(diǎn)是不夠精確 ， 當(dāng)一個(gè)算法比另一個(gè)算法稍好一些時(shí)不易判斷 。 挑戰(zhàn)題解析 ? 綜合應(yīng)用題：主要考查難度較大的算法時(shí)間性能分析、有關(guān)深層次理解 DS的綜合問(wèn)題。 Hanoi塔算法 void Hanoi( int n, char x, char y, char z ) { if( n == 1 ) move( x, 1, z )。 // 把 1號(hào)盤，從 x移到 z else {Hanoi( n – 1, x, z, y )。// 把 n1個(gè)盤，從 x移到 y， z為輔助塔 move( x, n, z )。 // 把 n號(hào)盤，從 x移到 z Hanoi( n – 1, y, x, z )。//把 n1個(gè)盤，從 y移到 z， x為輔助塔 } } ? 綜合應(yīng)用題 1：分析 Hanoi問(wèn)題的算法時(shí)間復(fù)雜度。 挑戰(zhàn)題解析 ? 綜合應(yīng)用題 1：分析 Hanoi問(wèn)題的算法時(shí)間復(fù)雜度。 關(guān)系為：算法時(shí)間復(fù)雜度的遞歸塔問(wèn)題的算法可以得到由 H a n o iT(n)= 1 n=1 2T(n1)+1 n1 )2(12212*21122. . . . . .22)1(2. . . . . .122)3(212)1)3(2(212)2(21)1)2(2(21)1(2)(123212322nnnnnnOTnTnTnTnTnTnT???????????????????????????????????????T(n)= 1 n=1 2T(n1)+1 n1 所以，時(shí)間復(fù)雜度為 O(2n) 挑戰(zhàn)題解析 ? 綜合應(yīng)用題 2：設(shè) n是偶數(shù)，且有程序段： for(i=1。i=n。i++) if(2*i=n) for(j=2*i。j=n。j++) y=y+i*j。 則語(yǔ)句 y=y+i*j。的執(zhí)行次數(shù)是多少 ？ 要求列出計(jì)算公式 解答： 語(yǔ)句 y=y+i*j。在 i=1時(shí)，執(zhí)行 n1次，在 i=2時(shí)，執(zhí)行 n3次， …… ，當(dāng) i=n/2時(shí)執(zhí)行 1次，當(dāng) in/2時(shí)不再執(zhí)行。故總的執(zhí)行次數(shù)是： (n1)+(n3)+(n5)+…… +3+1=n2/4 挑戰(zhàn)題解析 ? 綜合應(yīng)用題 3：運(yùn)算是 DS的一個(gè)重要方面。舉例說(shuō)明兩個(gè) DS的邏輯結(jié)構(gòu)和存儲(chǔ)方式完全相同，只是對(duì)于運(yùn)算的定義不同，因而具有不同的特性，則這兩個(gè) DS是不同的。 解答： 例如堆棧和隊(duì)列都是線性結(jié)構(gòu)，都可以采用順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，由于對(duì)插入和刪除操作的定義不同，棧規(guī)定在表的一端進(jìn)行插入和刪除操作，隊(duì)列規(guī)定在表的一端進(jìn)行插入在另一端進(jìn)行刪除操作，導(dǎo)致了棧的后進(jìn)先出，隊(duì)列的先進(jìn)先出特性，因而棧和隊(duì)列是兩種不同的 DS。 再如二叉樹(shù)和二叉排序樹(shù)在邏輯結(jié)構(gòu)上都是二叉樹(shù)，都采用二叉鏈表形式存儲(chǔ)，但是對(duì)于某些運(yùn)算的定義不同，例如插入操作，二叉樹(shù)需指明作為哪個(gè)結(jié)點(diǎn)的左孩子還是右孩子插入，而二叉排序樹(shù)無(wú)需指明，由二叉排序樹(shù)的形狀決定插入位置。 )(4222*)12(1)(,n2i,n~i*2,22212121 2nOnninninnTiimninininij???????????????? ???? ?為：，所以，該語(yǔ)句的頻度的最大值滿足：即由于內(nèi)循環(huán)從為解答：算法的基本操作)(4222*)12(1)(2,n2i,n~i*2,22212121 2nOnninninnTniimninininij???????????????? ???? ?為：，所以，該語(yǔ)句的頻度的最大值滿足：即由于內(nèi)循環(huán)從為解答：算法的基本操作典型題解析 ? 5. 可以用（ ）、數(shù)據(jù)關(guān)系和基本操作定義一個(gè)完整的抽象數(shù)據(jù)類型。 A. 數(shù)據(jù)元素 B. 數(shù)據(jù)對(duì)象 C. 原子類型 D. 存儲(chǔ)結(jié)構(gòu) 解答： A 分析： 數(shù)據(jù)對(duì)象指的是具有相同類型的數(shù)據(jù)，而數(shù)據(jù)的概念隱含著數(shù)據(jù)元素和元素之間的關(guān)系；定義抽象數(shù)據(jù)類型無(wú)需指明存儲(chǔ)結(jié)構(gòu)，定義抽象數(shù)據(jù)類型需要定義兩方面的內(nèi)容：數(shù)據(jù)和操作，其中數(shù)據(jù)需要指明數(shù)據(jù)元素以及數(shù)據(jù)元素之間的關(guān)系，操作需要指明基本操作及其操作接口。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1