計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)ppt課件

1、計(jì)算機(jī)等級(jí)考試計(jì)算機(jī)等級(jí)考試公共基礎(chǔ)知識(shí)公共基礎(chǔ)知識(shí) 2019版版HNU）第2頁計(jì)算機(jī)二級(jí)考試公共基礎(chǔ)知識(shí)大綱計(jì)算機(jī)二級(jí)考試公共基礎(chǔ)知識(shí)大綱 q 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法q 程序設(shè)計(jì)基礎(chǔ)程序設(shè)計(jì)基礎(chǔ)q 軟件工程基礎(chǔ)軟件工程基礎(chǔ)q 數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)這四個(gè)方面在試卷中出現(xiàn)的情況是：選擇題10個(gè)20分），填空題5個(gè)10分），總分值占到了試卷卷面分的30，是一個(gè)不小的比例。 第3頁計(jì)算機(jī)二級(jí)考試公共基礎(chǔ)知識(shí)試卷分析計(jì)算機(jī)二級(jí)考試公共基礎(chǔ)知識(shí)試卷分析 章節(jié)章節(jié)考試時(shí)間考試時(shí)間數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法與算法程序設(shè)程序設(shè)計(jì)基礎(chǔ)計(jì)基礎(chǔ)軟件工軟件工程基礎(chǔ)程基礎(chǔ)數(shù)據(jù)庫設(shè)數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)計(jì)基礎(chǔ)2019年

2、4月10分2分10分8分2019年9月12分4分8分6分2019年4月10分2分8分10分2019年9月10分2分8分10分2009年3月10分2分8分10分2009年9月10分2分8分10分2019年3月10分0分10分10分第4頁對(duì)于等級(jí)考試，這個(gè)部分的考核重點(diǎn)主要在算法和數(shù)據(jù)結(jié)構(gòu)的基本概對(duì)于等級(jí)考試，這個(gè)部分的考核重點(diǎn)主要在算法和數(shù)據(jù)結(jié)構(gòu)的基本概念、二叉樹念、二叉樹(遍歷、結(jié)點(diǎn)），還有排序和查找考試中也經(jīng)常會(huì)涉及到。遍歷、結(jié)點(diǎn)），還有排序和查找考試中也經(jīng)常會(huì)涉及到。第5頁算法的定義算法的定義對(duì)解題方案準(zhǔn)確而完整的描述稱為算對(duì)解題方案準(zhǔn)確而完整的描述稱為算法。法。算法是程序設(shè)計(jì)的核心算法是

3、程序設(shè)計(jì)的核心 算法是在有限步驟內(nèi)求解某一問題所使用算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。通俗點(diǎn)說，就是計(jì)算的一組定義明確的規(guī)則。通俗點(diǎn)說，就是計(jì)算機(jī)解題的過程機(jī)解題的過程( (計(jì)算的方法計(jì)算的方法) )。在這個(gè)過程中，。在這個(gè)過程中，無論是形成解題思路無論是形成解題思路( (推理實(shí)現(xiàn)的算法推理實(shí)現(xiàn)的算法) )還是編還是編寫程序?qū)懗绦? (操作實(shí)現(xiàn)的算法操作實(shí)現(xiàn)的算法) )，都是在實(shí)施某種算，都是在實(shí)施某種算法。法。例：例： n個(gè)數(shù)從大到小進(jìn)行排序。個(gè)數(shù)從大到小進(jìn)行排序。 有多種排序方法有多種排序方法 ，常用的有冒泡排序、選擇排，常用的有冒泡排序、選擇排序等。序等。第6頁

4、2 . 算法的基本特征算法的基本特征一個(gè)算法應(yīng)該具有以下五個(gè)重要的特征：一個(gè)算法應(yīng)該具有以下五個(gè)重要的特征：n 有窮性有窮性n 確定性確定性n 輸入輸入n 輸出輸出n 可行性可行性一個(gè)算法必須保證執(zhí)行有限步之后結(jié)束；算法的每一步驟必須有確切的定義；一個(gè)算法有0個(gè)或多個(gè)輸入，以刻畫運(yùn)算對(duì)象的初始情況，所謂0個(gè)輸入是指算法本身定除了初始條件；一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的；算法原則上能夠精確地運(yùn)行，而且人們用筆和紙做有限次運(yùn)算后即可完成 第7頁u算法與計(jì)算機(jī)程序算法與計(jì)算機(jī)程序u 算法算法_是一組邏輯步驟是一組邏輯步驟u 程序程序用計(jì)算機(jī)語言描述

5、的算法用計(jì)算機(jī)語言描述的算法INPUT rS=3.14 * r*rPTINT S開場開場輸入輸入R RS=3.14 * R*R輸出輸出S S終了終了問題：輸入園的半徑，計(jì)算園的面積 一個(gè)算法的表示需要使用一些語言形一個(gè)算法的表示需要使用一些語言形式。式。傳統(tǒng)的算法傳統(tǒng)的算法-圖形法，如圖形法，如“流程圖流程圖和和N-S圖圖目前常用的方法目前常用的方法-使用偽碼描述算法。使用偽碼描述算法。第8頁冒泡排序的方法：冒泡排序的方法：1.掃描整個(gè)線性表，逐次對(duì)掃描整個(gè)線性表，逐次對(duì)相鄰的兩個(gè)元素進(jìn)行比較，相鄰的兩個(gè)元素進(jìn)行比較，若為逆序，則交換；第一趟若為逆序，則交換；第一趟掃描的結(jié)果使最大的元素排掃描

6、的結(jié)果使最大的元素排到表的最后到表的最后 ；2.除最后一個(gè)元素，對(duì)剩余除最后一個(gè)元素，對(duì)剩余的元素重復(fù)上述過程，將次的元素重復(fù)上述過程，將次大的數(shù)排到表的倒數(shù)第二個(gè)大的數(shù)排到表的倒數(shù)第二個(gè)位置；位置；3.重復(fù)上述過程；重復(fù)上述過程；對(duì)于長度為對(duì)于長度為n的線性表，冒的線性表，冒泡排序需要對(duì)表掃描泡排序需要對(duì)表掃描n-1遍。遍。 算法舉例：算法舉例：n個(gè)數(shù)排序個(gè)數(shù)排序第9頁4. 算法的兩個(gè)基本要素：算法的兩個(gè)基本要素：u一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作；u二是算法的控制結(jié)構(gòu)。u算法基本設(shè)計(jì)方法：列舉法、歸納法、遞推、遞歸、減斗遞推技術(shù)、回溯法 第10頁存空間存空間算法在執(zhí)行過程中臨時(shí)占用算法在執(zhí)行過程

7、中臨時(shí)占用的存儲(chǔ)空間的存儲(chǔ)空間時(shí)間復(fù)雜度它大致等于計(jì)算機(jī)執(zhí)時(shí)間復(fù)雜度它大致等于計(jì)算機(jī)執(zhí)行一種簡單操作所需的平均時(shí)間與算行一種簡單操作所需的平均時(shí)間與算法中進(jìn)行簡單操作的次數(shù)的乘積。法中進(jìn)行簡單操作的次數(shù)的乘積。一個(gè)算法在計(jì)算機(jī)存儲(chǔ)器上所占用一個(gè)算法在計(jì)算機(jī)存儲(chǔ)器上所占用的存儲(chǔ)空間，包括存儲(chǔ)算法本身所占的存儲(chǔ)空間，包括存儲(chǔ)算法本身所占用的存儲(chǔ)空間、算法中的輸入輸出數(shù)用的存儲(chǔ)空間、算法中的輸入輸出數(shù)據(jù)所占用的存儲(chǔ)空間和算法在運(yùn)行過據(jù)所占用的存儲(chǔ)空間和算法在運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間這三個(gè)部分程中臨時(shí)占用的存儲(chǔ)空間這三個(gè)部分第11頁第12頁(1) 在計(jì)算機(jī)中，算法是指在計(jì)算機(jī)中，算法是指_。 A.

8、 查詢方法查詢方法 B. 加工方法加工方法 C. 解題方案的準(zhǔn)確而完整的描述解題方案的準(zhǔn)確而完整的描述 D. 排序方法排序方法(2)下列敘述中正確的是下列敘述中正確的是 （07年年4月）月）A)算法的效率只與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)算法的效率只與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)B)算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量C)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是一一對(duì)應(yīng)的數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是一一對(duì)應(yīng)的D)算法的時(shí)間復(fù)雜度與空間復(fù)雜度一定相關(guān)算法的時(shí)間復(fù)雜度與空間復(fù)雜度一定相關(guān)(3)算法的有窮性是指算法的有窮性是指 (08年年4月

9、月)A算法程序的運(yùn)行時(shí)間是有限的算法程序的運(yùn)行時(shí)間是有限的 B算法程序所處理的數(shù)據(jù)量是有限的算法程序所處理的數(shù)據(jù)量是有限的 C算法程序的長度是有限的算法程序的長度是有限的 D算法只能被有限的用戶使用算法只能被有限的用戶使用(c)(B)算法習(xí)題:(A)第13頁(4) 算法的時(shí)問復(fù)雜度是指算法的時(shí)問復(fù)雜度是指 (2019年年3月月)A)算法的執(zhí)行時(shí)間算法的執(zhí)行時(shí)間B)算法所處理的數(shù)據(jù)量算法所處理的數(shù)據(jù)量C)算法程序中的語句或指令條數(shù)算法程序中的語句或指令條數(shù)D)算法在執(zhí)行過程中所需要的基本運(yùn)算次數(shù)算法在執(zhí)行過程中所需要的基本運(yùn)算次數(shù)(5) 算法的空間復(fù)雜度是指算法的空間復(fù)雜度是指 (09年年9月月

10、) A算法在執(zhí)行過程中所需要的計(jì)算機(jī)存儲(chǔ)空間算法在執(zhí)行過程中所需要的計(jì)算機(jī)存儲(chǔ)空間B算法所處理的數(shù)據(jù)量算法所處理的數(shù)據(jù)量C算法程序中的語句或指令條數(shù)算法程序中的語句或指令條數(shù)D算法在執(zhí)行過程中所需要的臨時(shí)工作單元數(shù)算法在執(zhí)行過程中所需要的臨時(shí)工作單元數(shù)(6) 下列敘述中正確的是下列敘述中正確的是 (06年年9月月)A一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度也必定大一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度也必定大B一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度必定小一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度必定小C一個(gè)算法的時(shí)間復(fù)雜度大，則其空間復(fù)雜度必定小一個(gè)算法的時(shí)間復(fù)雜度大，則其空間復(fù)雜度必定小 D上述三

11、種說法都不對(duì)上述三種說法都不對(duì)(D)計(jì)算工作計(jì)算工作量量(A)(D)第14頁 計(jì)算機(jī)在進(jìn)行數(shù)據(jù)處理時(shí)，實(shí)際需要處理的數(shù)據(jù)元計(jì)算機(jī)在進(jìn)行數(shù)據(jù)處理時(shí)，實(shí)際需要處理的數(shù)據(jù)元素一般有很多，而這些大量的數(shù)據(jù)元素都需要存放在計(jì)素一般有很多，而這些大量的數(shù)據(jù)元素都需要存放在計(jì)算機(jī)中，因此，大量的數(shù)據(jù)元素在計(jì)算機(jī)中如何組織，算機(jī)中，因此，大量的數(shù)據(jù)元素在計(jì)算機(jī)中如何組織，以便提高數(shù)據(jù)處理的效率，并且節(jié)省計(jì)算機(jī)的存儲(chǔ)空間，以便提高數(shù)據(jù)處理的效率，并且節(jié)省計(jì)算機(jī)的存儲(chǔ)空間，這是進(jìn)行數(shù)據(jù)處理的關(guān)鍵問題。這是進(jìn)行數(shù)據(jù)處理的關(guān)鍵問題。程序程序=算法算法+數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)是

12、指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。 一般來說，人們不會(huì)同時(shí)處理特征完全不同且互一般來說，人們不會(huì)同時(shí)處理特征完全不同且互相之間沒有任何關(guān)系的各類數(shù)據(jù)元素，對(duì)于具有不相之間沒有任何關(guān)系的各類數(shù)據(jù)元素，對(duì)于具有不同特征的數(shù)據(jù)元素總是分別進(jìn)行處理。同特征的數(shù)據(jù)元素總是分別進(jìn)行處理。一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，各個(gè)數(shù)據(jù)元素之間存在有某種關(guān)系即聯(lián)系），這各個(gè)數(shù)據(jù)元素之間存在有某種關(guān)系即聯(lián)系），這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)。構(gòu)。第15頁二二. 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)

13、元素的集合。數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)和數(shù)據(jù)之間關(guān)系的一門學(xué)數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)和數(shù)據(jù)之間關(guān)系的一門學(xué)科，它包括三個(gè)方面?？?，它包括三個(gè)方面。（1數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；（2在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；（3對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。第16頁u 1. 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu) u 數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)數(shù)據(jù)的邏輯結(jié)構(gòu)是指

14、反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。據(jù)結(jié)構(gòu)。u 數(shù)據(jù)的邏輯結(jié)構(gòu)包含：數(shù)據(jù)的邏輯結(jié)構(gòu)包含：u （1表示數(shù)據(jù)元素的信息；表示數(shù)據(jù)元素的信息；u （2表示各數(shù)據(jù)元素之間的前后件關(guān)系。表示各數(shù)據(jù)元素之間的前后件關(guān)系。u 例：例：u 1. 一年四季的數(shù)據(jù)結(jié)構(gòu)一年四季的數(shù)據(jù)結(jié)構(gòu)u B=(D,R)u D=春，夏，秋，冬春，夏，秋，冬u R=(春，夏春，夏) ,(夏，秋夏，秋),(秋，冬秋，冬)u 2. 家庭成員的數(shù)據(jù)結(jié)構(gòu)家庭成員的數(shù)據(jù)結(jié)構(gòu)u B=(D,R)u D=父親，兒子，女兒父親，兒子，女兒u R=(父親，兒子父親，兒子) ,(父親，女兒父親，女兒)春夏秋冬數(shù)據(jù)結(jié)構(gòu)的圖形表示數(shù)據(jù)結(jié)構(gòu)的圖形表示父親兒子女

15、兒第17頁u常見的邏輯結(jié)構(gòu)有：常見的邏輯結(jié)構(gòu)有：u線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。線性結(jié)構(gòu)線性結(jié)構(gòu)樹形結(jié)構(gòu)樹形結(jié)構(gòu)圖形結(jié)構(gòu)圖形結(jié)構(gòu)u 線性結(jié)構(gòu)線性結(jié)構(gòu) u 結(jié)構(gòu)中的每個(gè)元素之間存在一個(gè)對(duì)一個(gè)的關(guān)系；結(jié)構(gòu)中的每個(gè)元素之間存在一個(gè)對(duì)一個(gè)的關(guān)系；u 樹形結(jié)構(gòu)樹形結(jié)構(gòu) u 結(jié)構(gòu)中的每個(gè)元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系；結(jié)構(gòu)中的每個(gè)元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系；u 圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) u 結(jié)構(gòu)中的每個(gè)元素之間存在多個(gè)對(duì)多個(gè)的關(guān)系。結(jié)構(gòu)中的每個(gè)元素之間存在多個(gè)對(duì)多個(gè)的關(guān)系。u 其中，樹形結(jié)構(gòu)和圖形結(jié)構(gòu)統(tǒng)稱為非線形結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)其中，樹形結(jié)構(gòu)和圖形結(jié)構(gòu)統(tǒng)稱為非

16、線形結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)可以用二元關(guān)系表示，也可以直觀地用圖形來表示?？梢杂枚P(guān)系表示，也可以直觀地用圖形來表示。第18頁u 2. 存儲(chǔ)結(jié)構(gòu)物理結(jié)構(gòu)）存儲(chǔ)結(jié)構(gòu)物理結(jié)構(gòu)）u 計(jì)算機(jī)在實(shí)際進(jìn)行數(shù)據(jù)處理時(shí)，被處理的各數(shù)計(jì)算機(jī)在實(shí)際進(jìn)行數(shù)據(jù)處理時(shí)，被處理的各數(shù)據(jù)元素總是被存放在計(jì)算機(jī)的存儲(chǔ)空間中，并且，據(jù)元素總是被存放在計(jì)算機(jī)的存儲(chǔ)空間中，并且，各數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的位置與它們的各數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的位置與它們的邏輯關(guān)系不一定是相同的，而且一般也不可能相邏輯關(guān)系不一定是相同的，而且一般也不可能相同。同。u如：一年四季如：一年四季 u 家庭成員家庭成員 計(jì)算機(jī)存儲(chǔ)空間怎樣存放？計(jì)算機(jī)存

17、儲(chǔ)空間怎樣存放？u 存儲(chǔ)結(jié)構(gòu)指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的具體存儲(chǔ)結(jié)構(gòu)指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的具體實(shí)現(xiàn)。實(shí)現(xiàn)。u常見的存儲(chǔ)結(jié)構(gòu)有：常見的存儲(chǔ)結(jié)構(gòu)有：u 順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)u 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)u索引存儲(chǔ)結(jié)構(gòu)索引存儲(chǔ)結(jié)構(gòu) 只抽象地反映數(shù)據(jù)元素之間的關(guān)只抽象地反映數(shù)據(jù)元素之間的關(guān)系的結(jié)構(gòu)，而不管其存儲(chǔ)方式的系的結(jié)構(gòu)，而不管其存儲(chǔ)方式的數(shù)據(jù)結(jié)構(gòu)稱為邏輯結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)稱為邏輯結(jié)構(gòu)。 一種數(shù)據(jù)結(jié)構(gòu)可以根據(jù)需要表示一種數(shù)據(jù)結(jié)構(gòu)可以根據(jù)需要表示成一種或多種存儲(chǔ)結(jié)構(gòu)。成一種或多種存儲(chǔ)結(jié)構(gòu)。第19頁u3. 數(shù)據(jù)的運(yùn)算u 檢索u 插入u 刪除u 更新u 排序 通常，一個(gè)數(shù)據(jù)結(jié)構(gòu)中的元素結(jié)點(diǎn)可能是

18、動(dòng)態(tài)變通常，一個(gè)數(shù)據(jù)結(jié)構(gòu)中的元素結(jié)點(diǎn)可能是動(dòng)態(tài)變化的。根據(jù)需要或在處理過程中，可以在一個(gè)數(shù)據(jù)化的。根據(jù)需要或在處理過程中，可以在一個(gè)數(shù)據(jù)結(jié)構(gòu)中增加一個(gè)新結(jié)點(diǎn)插入運(yùn)算），也可以刪除結(jié)構(gòu)中增加一個(gè)新結(jié)點(diǎn)插入運(yùn)算），也可以刪除某個(gè)結(jié)點(diǎn)刪除運(yùn)算），除此之外，對(duì)數(shù)據(jù)結(jié)構(gòu)的某個(gè)結(jié)點(diǎn)刪除運(yùn)算），除此之外，對(duì)數(shù)據(jù)結(jié)構(gòu)的運(yùn)算還有查找、分類、合并、分解、復(fù)制和修改。運(yùn)算還有查找、分類、合并、分解、復(fù)制和修改。 在對(duì)數(shù)據(jù)結(jié)構(gòu)的處理過程中，不僅數(shù)據(jù)結(jié)構(gòu)中結(jié)在對(duì)數(shù)據(jù)結(jié)構(gòu)的處理過程中，不僅數(shù)據(jù)結(jié)構(gòu)中結(jié)點(diǎn)的個(gè)數(shù)在動(dòng)態(tài)變化，而且，各數(shù)據(jù)元素之間的關(guān)點(diǎn)的個(gè)數(shù)在動(dòng)態(tài)變化，而且，各數(shù)據(jù)元素之間的關(guān)系也有可能在動(dòng)態(tài)地變化。如：無序表

19、變有序表系也有可能在動(dòng)態(tài)地變化。如：無序表變有序表數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)和數(shù)據(jù)之間數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)和數(shù)據(jù)之間關(guān)系的一門學(xué)科，研究以下三方面關(guān)系的一門學(xué)科，研究以下三方面內(nèi)容：內(nèi)容： 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的運(yùn)算數(shù)據(jù)的運(yùn)算第20頁常見的數(shù)據(jù)結(jié)構(gòu) 1.線性表 2.棧和隊(duì)列 3.樹第21頁 線性表是由線性表是由nn0個(gè)數(shù)據(jù)元素個(gè)數(shù)據(jù)元素 a1，a2，ai，an組成的一個(gè)有限序列。組成的一個(gè)有限序列。春春夏夏秋秋冬冬記錄記錄1 02019001 張三張三 男男記錄記錄2 02019003 李四李四 女女 記錄記錄3記錄記錄4第22頁 順序存儲(chǔ)結(jié)構(gòu)把邏輯上相鄰的數(shù)

20、據(jù)順序存儲(chǔ)結(jié)構(gòu)把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元里元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元里，順序存儲(chǔ)結(jié)構(gòu)只存儲(chǔ)結(jié)點(diǎn)的值，不，順序存儲(chǔ)結(jié)構(gòu)只存儲(chǔ)結(jié)點(diǎn)的值，不存儲(chǔ)結(jié)點(diǎn)間的關(guān)系，結(jié)點(diǎn)間的關(guān)系由存儲(chǔ)結(jié)點(diǎn)間的關(guān)系，結(jié)點(diǎn)間的關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。a1a2aian存儲(chǔ)地址存儲(chǔ)地址200020192000+4*(i-1)2000+4*(n-1)占占4個(gè)字節(jié)個(gè)字節(jié)第i個(gè)數(shù)的地址第一個(gè)數(shù)的地址L為該類型數(shù)所占的字節(jié)線性表的存儲(chǔ)結(jié)構(gòu)有兩種：線性表的存儲(chǔ)結(jié)構(gòu)有兩種： 順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)第23頁u 順序表的插入運(yùn)算順序表的插入運(yùn)算u 順序表的刪除

21、運(yùn)算順序表的刪除運(yùn)算 在線性表順序存儲(chǔ)情況下，要插入或刪除一個(gè)元在線性表順序存儲(chǔ)情況下，要插入或刪除一個(gè)元素，都會(huì)由于數(shù)據(jù)元素的移動(dòng)而消耗大量的處理時(shí)間，素，都會(huì)由于數(shù)據(jù)元素的移動(dòng)而消耗大量的處理時(shí)間，所以這種存儲(chǔ)方式對(duì)于小線性表或其中數(shù)據(jù)元素不經(jīng)所以這種存儲(chǔ)方式對(duì)于小線性表或其中數(shù)據(jù)元素不經(jīng)常變動(dòng)的線性表是合適的。常變動(dòng)的線性表是合適的。線性表的順序存儲(chǔ)結(jié)構(gòu)稱為順序表。線性表的順序存儲(chǔ)結(jié)構(gòu)稱為順序表。第24頁u 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。u 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不要求邏輯上相鄰的數(shù)據(jù)元素物理位鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不要求邏輯上相鄰的數(shù)據(jù)元素物理位置也相鄰，而且各數(shù)據(jù)元

22、素的存儲(chǔ)順序也是任意的置也相鄰，而且各數(shù)據(jù)元素的存儲(chǔ)順序也是任意的。各數(shù)據(jù)元素的先后關(guān)系是由各結(jié)點(diǎn)的指針域指示。各數(shù)據(jù)元素的先后關(guān)系是由各結(jié)點(diǎn)的指針域指示。u 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的每一個(gè)存儲(chǔ)結(jié)點(diǎn)不僅存儲(chǔ)結(jié)點(diǎn)的值鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的每一個(gè)存儲(chǔ)結(jié)點(diǎn)不僅存儲(chǔ)結(jié)點(diǎn)的值，而且存儲(chǔ)結(jié)點(diǎn)之間的關(guān)系：，而且存儲(chǔ)結(jié)點(diǎn)之間的關(guān)系：數(shù)據(jù)域數(shù)據(jù)域指針域指針域第25頁設(shè)線性表為設(shè)線性表為a1，a2，a3，a4，a5）1a2923a1145a4106789a3510a50HEAD3a1a2a5a3a4HEAD319510線性鏈表的邏輯狀態(tài)線性鏈表的邏輯狀態(tài)線性鏈表的物理狀態(tài)線性鏈表的物理狀態(tài)1 a12 a23 a34 a45 a56

23、7留意:1 2 3 此類編號(hào)不代表所在的地址單元的地址編碼第26頁u 單鏈表的插入運(yùn)算單鏈表的插入運(yùn)算u 單鏈表的刪除運(yùn)算單鏈表的刪除運(yùn)算采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，存儲(chǔ)空間開銷較大，但是進(jìn)行插采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，存儲(chǔ)空間開銷較大，但是進(jìn)行插入和刪除運(yùn)算不會(huì)造成大量元素的移動(dòng)。入和刪除運(yùn)算不會(huì)造成大量元素的移動(dòng)。循環(huán)鏈表是加一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它的特點(diǎn)是循環(huán)鏈表是加一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)。表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)。 a1a2a5a3a4HEAD319510第27頁雙向鏈表的存儲(chǔ)結(jié)構(gòu) 提問：單向鏈表的缺點(diǎn)是什么？ 提示：如何尋找結(jié)點(diǎn)的直接前趨。 雙

24、向鏈表可以克服單鏈表的單向性的缺點(diǎn)。 在雙向鏈表的結(jié)點(diǎn)中有兩個(gè)指針域，其一指向直接后繼，另一指向直接前趨。 HEAD31510 a2 a3 a4 a1雙向循環(huán)鏈表雙向循環(huán)鏈表 第28頁u 順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)留意：留意： 數(shù)據(jù)元素在計(jì)算機(jī)數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的位置關(guān)存儲(chǔ)空間中的位置關(guān)系與它們的邏輯關(guān)系系與它們的邏輯關(guān)系不一定是相同的。不一定是相同的。 一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，可以有多種存儲(chǔ)結(jié)構(gòu)，且不同的存儲(chǔ)結(jié)構(gòu)影且不同的存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理的效率響數(shù)據(jù)處理的效率 。1a2923a1145a4106789a3510a50HEAD31 a12 a23 a34

25、a45 a567u鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表線性表 : a1，a2，a3，a4，a5 第29頁棧和隊(duì)列都是特殊的線性表。棧和隊(duì)列都是特殊的線性表。 棧棧Stack及其基本運(yùn)算及其基本運(yùn)算 隊(duì)列隊(duì)列Queue及其基本運(yùn)算及其基本運(yùn)算 循環(huán)隊(duì)列及其基本運(yùn)算循環(huán)隊(duì)列及其基本運(yùn)算第30頁 在順序棧中插入和刪除運(yùn)算不需要在順序棧中插入和刪除運(yùn)算不需要移動(dòng)表中其他數(shù)據(jù)元素。移動(dòng)表中其他數(shù)據(jù)元素。第31頁棧有三種操作：棧有三種操作： 入棧出棧讀棧頂元素入棧出棧讀棧頂元素隊(duì)列有三種操作：入隊(duì)出隊(duì)讀隊(duì)首元素隊(duì)列有三種操作：入隊(duì)出隊(duì)讀隊(duì)首元素例：有入棧元素序列：例：有入棧元素序列：ABCD，求可能的出棧序列，

26、求可能的出棧序列如是隊(duì)列又是什么情況呢？如是隊(duì)列又是什么情況呢？第32頁隊(duì)列中進(jìn)行插入的一端稱做隊(duì)尾隊(duì)列中進(jìn)行插入的一端稱做隊(duì)尾(rear),進(jìn)行刪除的一端進(jìn)行刪除的一端稱做隊(duì)首稱做隊(duì)首(front)。 習(xí)題：數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，循環(huán)隊(duì)習(xí)題：數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，循環(huán)隊(duì)列屬于【列屬于【 】構(gòu)造。（】構(gòu)造。（2019年年9月）月）答案：存儲(chǔ)結(jié)構(gòu)。答案：存儲(chǔ)結(jié)構(gòu)。第33頁常見數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)常見數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)u線性表線性表 線性結(jié)構(gòu)線性結(jié)構(gòu)u棧棧 是特殊的線性表是特殊的線性表 u隊(duì)列隊(duì)列 u 也是一種操作受限的特殊的也是一種操作受限的特殊的線性表線性表u樹樹 （樹型結(jié)構(gòu)

27、）（樹型結(jié)構(gòu)）u 是一種重要的非線形數(shù)據(jù)結(jié)是一種重要的非線形數(shù)據(jù)結(jié)構(gòu)構(gòu)第34頁數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)方面的考題數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)方面的考題 1：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指 （2019年年4月）月）A) 存儲(chǔ)在外存中的數(shù)據(jù)存儲(chǔ)在外存中的數(shù)據(jù) B) 數(shù)據(jù)所占的存儲(chǔ)空間量數(shù)據(jù)所占的存儲(chǔ)空間量C) 數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式 D) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示2. 下列敘述中正確的是下列敘述中正確的是 （2009年年3月）月） A棧是棧是“先進(jìn)先出的線性表先進(jìn)先出的線性表 B隊(duì)列是隊(duì)列是“先進(jìn)后出的線性表先進(jìn)后出的線性表 C循環(huán)隊(duì)列是非線性結(jié)構(gòu)

28、循環(huán)隊(duì)列是非線性結(jié)構(gòu) D有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 3. 數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈的隊(duì)列屬于數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈的隊(duì)列屬于 。4. 下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是A循環(huán)隊(duì)列循環(huán)隊(duì)列 B) 帶鏈隊(duì)列帶鏈隊(duì)列C) 二叉樹二叉樹 D帶鏈棧帶鏈棧答案：答案：D。答案：答案：D。答案：線性結(jié)構(gòu)。答案：線性結(jié)構(gòu)。答案：答案：c第35頁5。下列敘述中正確的是（。下列敘述中正確的是（ ）。）。 （2019年年9月）月） A順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)一定是連續(xù)的，鏈

29、式存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)空間不一順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)一定是連續(xù)的，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間不一定是連續(xù)的定是連續(xù)的 B順序存儲(chǔ)結(jié)構(gòu)只針對(duì)線性結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只針對(duì)非線性結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)只針對(duì)線性結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只針對(duì)非線性結(jié)構(gòu) C順序存儲(chǔ)結(jié)構(gòu)能存儲(chǔ)有序表，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不能存儲(chǔ)有序表順序存儲(chǔ)結(jié)構(gòu)能存儲(chǔ)有序表，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不能存儲(chǔ)有序表 D鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比順序存儲(chǔ)結(jié)構(gòu)節(jié)省存儲(chǔ)空間鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比順序存儲(chǔ)結(jié)構(gòu)節(jié)省存儲(chǔ)空間答案：答案：A。6 6。下列關(guān)于棧的敘述正確的是。下列關(guān)于棧的敘述正確的是 （20192019年年4 4月）月） A A棧按棧按“先進(jìn)先出組織數(shù)據(jù)先進(jìn)先出組織數(shù)據(jù) B) B)棧按棧按“先進(jìn)后出組

30、織數(shù)據(jù)先進(jìn)后出組織數(shù)據(jù) C C只能在棧底插入數(shù)據(jù)只能在棧底插入數(shù)據(jù) D D不能刪除數(shù)據(jù)不能刪除數(shù)據(jù) 答案：答案：B。7. 一個(gè)隊(duì)列的初始狀態(tài)為空?，F(xiàn)將元素一個(gè)隊(duì)列的初始狀態(tài)為空。現(xiàn)將元素A，B，C，D，E，F(xiàn)，5，4，3，2，1依次入隊(duì)，然后再依次退隊(duì)，則元素退隊(duì)的順序?yàn)橐来稳腙?duì)，然后再依次退隊(duì)，則元素退隊(duì)的順序?yàn)?【1】 。（。（2019年年3月）月） 答案：答案：A，B，C，D，E，F(xiàn)，5，4，3，2，1第36頁9. 設(shè)某循環(huán)隊(duì)列的容量為設(shè)某循環(huán)隊(duì)列的容量為50，如果頭指針，如果頭指針front=45(指向指向隊(duì)頭元素的前一位置隊(duì)頭元素的前一位置)，尾指針，尾指針rear=10(指向隊(duì)尾元

31、素指向隊(duì)尾元素)，則該循環(huán)隊(duì)列中共有則該循環(huán)隊(duì)列中共有 【2】 個(gè)元素。個(gè)元素。 （2019年年3月）月） 8。假設(shè)用一個(gè)長度為。假設(shè)用一個(gè)長度為50的數(shù)組數(shù)組元索的下標(biāo)從的數(shù)組數(shù)組元索的下標(biāo)從0到到49作為棧的存儲(chǔ)空間，棧底指針作為棧的存儲(chǔ)空間，棧底指針bottom指間棧底指間棧底元素，棧頂指針元素，棧頂指針top指向棧頂元素，如果指向棧頂元素，如果bottom=49，top=30數(shù)組下標(biāo)），則棧中具有【數(shù)組下標(biāo)），則棧中具有【 】個(gè)元素。】個(gè)元素。 （2009年年3月）月） 答案：答案：19答案：答案：15第37頁一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)若滿足下面的兩個(gè)條件，則這種數(shù)據(jù)結(jié)一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)若滿足

32、下面的兩個(gè)條件，則這種數(shù)據(jù)結(jié)構(gòu)即為線性結(jié)構(gòu)。構(gòu)即為線性結(jié)構(gòu)。 有且僅有一個(gè)根結(jié)點(diǎn)；有且僅有一個(gè)根結(jié)點(diǎn)； 除第一個(gè)結(jié)點(diǎn)外，每一個(gè)結(jié)點(diǎn)最多有一個(gè)直接前驅(qū)結(jié)點(diǎn)；除第一個(gè)結(jié)點(diǎn)外，每一個(gè)結(jié)點(diǎn)最多有一個(gè)直接前驅(qū)結(jié)點(diǎn)； 除最后一個(gè)結(jié)點(diǎn)外，每一個(gè)結(jié)點(diǎn)最多有一個(gè)直接后繼結(jié)點(diǎn)。除最后一個(gè)結(jié)點(diǎn)外，每一個(gè)結(jié)點(diǎn)最多有一個(gè)直接后繼結(jié)點(diǎn)。u 線性結(jié)構(gòu)與非線性結(jié)構(gòu)線性結(jié)構(gòu)與非線性結(jié)構(gòu)u線性表、棧和隊(duì)列都是線性結(jié)構(gòu)線性表、棧和隊(duì)列都是線性結(jié)構(gòu)u 一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱其為非線性結(jié)構(gòu)。一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱其為非線性結(jié)構(gòu)。a1a2a5a3a4HEAD319510線性鏈表的邏輯狀態(tài)線性鏈表的邏輯狀態(tài)第38頁樹型結(jié)構(gòu)

33、是一種重要的非線性結(jié)構(gòu)。樹型結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)。 樹的概念樹的概念 二叉樹的概念二叉樹的概念 二叉樹的存儲(chǔ)二叉樹的存儲(chǔ) 二叉樹的遍歷二叉樹的遍歷第39頁u 樹的定義：n個(gè)結(jié)點(diǎn)的有限集。（n=0） ABDFECGHIJKMn 根：根：only onen 若若n=0，則稱為空樹；，則稱為空樹；n 否則，當(dāng)否則，當(dāng)n1時(shí)，其余結(jié)時(shí)，其余結(jié)點(diǎn)被分成點(diǎn)被分成mm0個(gè)互不個(gè)互不相交的子集相交的子集T1，T2，.，Tm，每個(gè)子集又是一棵樹。，每個(gè)子集又是一棵樹。由此可以看出，樹的定義是由此可以看出，樹的定義是遞歸的。遞歸的。n Question：如何辨別根？：如何辨別根？A只有一個(gè)只有一個(gè)結(jié)點(diǎn)的樹結(jié)

34、點(diǎn)的樹第40頁ABDFECGHIJKMn 結(jié)點(diǎn)的度結(jié)點(diǎn)的度 一個(gè)結(jié)點(diǎn)的子樹的一個(gè)結(jié)點(diǎn)的子樹的個(gè)數(shù)；個(gè)數(shù)； Q：結(jié)點(diǎn)：結(jié)點(diǎn)A、G的度數(shù)？的度數(shù)？n 樹的度樹的度 樹中所有結(jié)點(diǎn)度的最樹中所有結(jié)點(diǎn)度的最大值；大值；Q：右圖中樹的度？：右圖中樹的度？n 終端結(jié)點(diǎn)終端結(jié)點(diǎn) 度為度為0的結(jié)點(diǎn)；的結(jié)點(diǎn)；n Q：圖中葉子結(jié)點(diǎn)有幾個(gè)？：圖中葉子結(jié)點(diǎn)有幾個(gè)？7n 非終端結(jié)點(diǎn)非終端結(jié)點(diǎn) 度不為度不為0的結(jié)點(diǎn)；的結(jié)點(diǎn)；n Q：圖中非終端結(jié)點(diǎn)有幾個(gè)？：圖中非終端結(jié)點(diǎn)有幾個(gè)？ 5第41頁ABDFECGHIJKMn 結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次 樹中根結(jié)點(diǎn)的層次為樹中根結(jié)點(diǎn)的層次為1，根結(jié)點(diǎn)，根結(jié)點(diǎn)子樹的根為第子樹的根為第2層，以

35、此類推；層，以此類推；n Q：圖中結(jié)點(diǎn)：圖中結(jié)點(diǎn)F的層次？的層次？n 樹的深度樹的深度 樹中所有結(jié)點(diǎn)層次的最大值；樹中所有結(jié)點(diǎn)層次的最大值； Q：圖中樹的深度？圖中樹的深度？n 有序樹、無序樹有序樹、無序樹 如果樹中每棵子樹從左向右如果樹中每棵子樹從左向右的排列擁有一定的順序，不得互換，則稱為有的排列擁有一定的順序，不得互換，則稱為有序樹，否則稱為無序樹。序樹，否則稱為無序樹。第42頁 定義：二叉樹是一種有序的樹形結(jié)構(gòu)。它與一般定義：二叉樹是一種有序的樹形結(jié)構(gòu)。它與一般樹形結(jié)構(gòu)的區(qū)別是：樹形結(jié)構(gòu)的區(qū)別是： 每個(gè)結(jié)點(diǎn)最多有兩棵子樹；每個(gè)結(jié)點(diǎn)最多有兩棵子樹； 子樹有左右之分，次序不能任意顛倒。子樹

36、有左右之分，次序不能任意顛倒。 二叉樹的二叉樹的5種基本形態(tài)種基本形態(tài)第43頁【性質(zhì)1】 在二叉樹的第i層上最多有2i-1個(gè)結(jié)點(diǎn)i1）ABCDFEHG第44頁【性質(zhì)2】深度為h的二叉樹最多有2h -1個(gè)結(jié)點(diǎn)h 1）滿二叉樹：如果一個(gè)深度為h的二叉樹擁有2h-1個(gè)結(jié)點(diǎn)，則將它稱為滿二叉樹。完全二叉樹：有一棵深度為h，具有n個(gè)結(jié)點(diǎn)的二叉樹，若將它與一棵同深度的滿二叉樹中的所有結(jié)點(diǎn)按從上到下，從左到右的順序分別進(jìn)行編號(hào)，且該二叉樹中的每個(gè)結(jié)點(diǎn)分別與滿二叉樹中編號(hào)為1n的結(jié)點(diǎn)位置一一對(duì)應(yīng)，則稱這棵二叉樹為完全二叉樹。第45頁1213 141589 10 114567123滿二叉樹滿二叉樹完全二叉樹完全

37、二叉樹121389 10 114567123 完全二叉樹是滿二叉樹 滿二叉樹也是完全二叉樹第46頁121389 10 11456123非完全二叉樹非完全二叉樹深度為深度為4的的完全二叉樹完全二叉樹84567123第47頁【性質(zhì)3】二叉樹上葉子結(jié)點(diǎn)數(shù)比度為2的結(jié)點(diǎn)數(shù)多1ABCDFEHG度為2的結(jié)點(diǎn)葉子結(jié)點(diǎn)第48頁【性質(zhì)4】具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2 (n+1) 其中，log2n 的結(jié)果是不大于log2n的最大整數(shù)1213 141589 10 114567123深度為深度為4的的滿二叉樹滿二叉樹深度為深度為4的的完全二叉樹完全二叉樹84567123深度為深度為3的完全二叉樹具有的完

38、全二叉樹具有47深度為深度為4的完全二叉樹具有的完全二叉樹具有815深度為深度為5的完全二叉樹具有的完全二叉樹具有1531 log2(8+1) = ln9/In2=4 log2 (15+ 1) =In16/In2=4深度為深度為6的完全二叉樹的完全二叉樹 具有具有3263深度為深度為7的完全二叉樹的完全二叉樹 具有具有64127深度為深度為8的完全二叉樹的完全二叉樹 具有具有128255深度為深度為9的完全二叉樹的完全二叉樹 具有具有256511深度為深度為10的完全二叉樹具有的完全二叉樹具有5121023深度為深度為11的完全二叉樹具有的完全二叉樹具有10242047第49頁1 1：在深度為

39、：在深度為7 7的滿二叉樹中的滿二叉樹中, ,葉子結(jié)點(diǎn)的個(gè)數(shù)為葉子結(jié)點(diǎn)的個(gè)數(shù)為20192019年年4 4月）月） A)32 B)31 C)64 D)63 A)32 B)31 C)64 D)632 2：在深度為：在深度為7 7的滿二叉樹中，度為的滿二叉樹中，度為2 2的結(jié)點(diǎn)個(gè)數(shù)為【的結(jié)點(diǎn)個(gè)數(shù)為【 】 。(07(07年年4 4月）月）3 3：一棵二叉樹中共有：一棵二叉樹中共有7070個(gè)葉子結(jié)點(diǎn)與個(gè)葉子結(jié)點(diǎn)與8080個(gè)度為個(gè)度為1 1的結(jié)點(diǎn)，則該二叉樹中的總的結(jié)點(diǎn)，則該二叉樹中的總結(jié)點(diǎn)數(shù)為結(jié)點(diǎn)數(shù)為 （0707年年9 9月）月） A A219 B219 B221 C221 C229 D229 D231

40、2314 4： 某二叉樹中度為某二叉樹中度為2 2的結(jié)點(diǎn)有的結(jié)點(diǎn)有1818個(gè)，則該二叉樹中有個(gè)，則該二叉樹中有 【 】個(gè)葉子結(jié)點(diǎn)。】個(gè)葉子結(jié)點(diǎn)。（20192019年年4 4月）月）5 5：一棵二叉樹第六層根結(jié)點(diǎn)為第一層的結(jié)點(diǎn)數(shù)最多為【：一棵二叉樹第六層根結(jié)點(diǎn)為第一層的結(jié)點(diǎn)數(shù)最多為【 】個(gè)。（】個(gè)。（20192019年年9 9月）月） 樹型結(jié)構(gòu)方面的考題樹型結(jié)構(gòu)方面的考題 1答案：答案：C。3答案：答案：A。5答案：答案：32。2答案：答案：63。4答案：答案：19。第50頁u 在計(jì)算機(jī)中，二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在計(jì)算機(jī)中，二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。LlinkinfoRlink二叉樹的存

41、儲(chǔ)結(jié)點(diǎn)的結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)點(diǎn)的結(jié)構(gòu)ABDCFGE A G E F B C Dt第51頁u 遍歷指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)遍歷指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)。u 二叉樹的遍歷的次序與樹型結(jié)構(gòu)上的大多二叉樹的遍歷的次序與樹型結(jié)構(gòu)上的大多數(shù)運(yùn)算有聯(lián)系。數(shù)運(yùn)算有聯(lián)系。u遍歷的方式有三種遍歷的方式有三種u（1先前序遍歷先前序遍歷DLR）u（2中序遍歷中序遍歷LDR）u（3后序遍歷后序遍歷LRD）ABCDFEHG第52頁u 遍歷指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)。遍歷指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)。u（1先前序遍歷先前序遍歷DLR）u 若二叉樹為空，則結(jié)束遍歷操作；否則若二叉樹為空，則結(jié)束遍歷操作

42、；否則u訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)；u先序遍歷左子樹；先序遍歷左子樹；u先序遍歷右子樹。先序遍歷右子樹。ABCDFEHG先序遍歷的結(jié)果：先序遍歷的結(jié)果： A B E C F G H DA B E C F G H D第53頁（2中序遍歷中序遍歷LDR） 若二叉樹為空，則結(jié)束遍歷操作；否則若二叉樹為空，則結(jié)束遍歷操作；否則中序遍歷左子樹；中序遍歷左子樹；訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)；中序遍歷右子樹。中序遍歷右子樹。中序遍歷的結(jié)果：中序遍歷的結(jié)果： E B A F H G C D（3后序遍歷后序遍歷LRD） 若二叉樹為空，則結(jié)束遍歷操作；否則若二叉樹為空，則結(jié)束遍歷操作；否則后序遍歷左子樹；后序遍歷左子樹；后

43、序遍歷右子樹；后序遍歷右子樹；訪問根結(jié)點(diǎn)。訪問根結(jié)點(diǎn)。后序遍歷的結(jié)果：后序遍歷的結(jié)果： E B H G F D C AABCDFEHG第54頁先序序列：ABDGCEFH中序序列：DGBAECHF后序序列：GDBEHFCAABCFHDEG下圖所示的二叉樹經(jīng)過三種遍歷得到的順序分別為？下圖所示的二叉樹經(jīng)過三種遍歷得到的順序分別為？練習(xí)：練習(xí)：根據(jù)先序遍歷序列，建立二叉樹根據(jù)先序遍歷序列，建立二叉樹第55頁1:設(shè)二叉樹如下：設(shè)二叉樹如下： （2019年年3月）月）對(duì)該二叉樹進(jìn)行后序遍歷的對(duì)該二叉樹進(jìn)行后序遍歷的結(jié)果為結(jié)果為 【3】 樹型結(jié)構(gòu)方面的考題樹型結(jié)構(gòu)方面的考題 22: 對(duì)如下二叉樹對(duì)如下二叉

44、樹2019年年4月）月）進(jìn)行后序遍歷的結(jié)果為進(jìn)行后序遍歷的結(jié)果為A) ABCDEF B) DBEAFC C) ABDECF D) DEBFCA EDBGHFCA DABCFHDGE第56頁 查找是數(shù)據(jù)處理的重要內(nèi)容。查找是數(shù)據(jù)處理的重要內(nèi)容。 查找指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找指定的元素，該查找指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找指定的元素，該元素也稱關(guān)鍵字。元素也稱關(guān)鍵字。 若找到了滿足條件的結(jié)點(diǎn)，稱查找成功；否則稱查找若找到了滿足條件的結(jié)點(diǎn)，稱查找成功；否則稱查找失敗。失敗。 衡量一個(gè)查找算法的主要標(biāo)準(zhǔn)是查找過程中對(duì)關(guān)鍵字衡量一個(gè)查找算法的主要標(biāo)準(zhǔn)是查找過程中對(duì)關(guān)鍵字進(jìn)行的平均比較次數(shù)。進(jìn)行的平均比

45、較次數(shù)。 通常根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，采用不同的查找方法：通常根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，采用不同的查找方法： 順序查找順序查找 二分查找二分查找第57頁u線性表中最簡單的查找方法。線性表中最簡單的查找方法。u 方法：從線性表的第一個(gè)元素開始，依次將線性方法：從線性表的第一個(gè)元素開始，依次將線性表中的元素與關(guān)鍵字進(jìn)行比較，若相等，則查找成表中的元素與關(guān)鍵字進(jìn)行比較，若相等，則查找成功；若將所有元素都與關(guān)鍵字進(jìn)行了比較但不相等，功；若將所有元素都與關(guān)鍵字進(jìn)行了比較但不相等，則查找失敗。則查找失敗。u 順序查找法的適用場合：順序查找法的適用場合：u 對(duì)線性表中元素的排列次序沒有要求；對(duì)線性表中元素的排列次序沒

46、有要求；u 對(duì)線性表的存儲(chǔ)結(jié)構(gòu)沒有要求，鏈?zhǔn)浇Y(jié)構(gòu)和順序?qū)€性表的存儲(chǔ)結(jié)構(gòu)沒有要求，鏈?zhǔn)浇Y(jié)構(gòu)和順序結(jié)構(gòu)均可。結(jié)構(gòu)均可。第58頁u 是一種效率較高的查找方法，但是只適合順序存儲(chǔ)的有序表。u二分查找的方法：首先將關(guān)鍵字與線性表中間位置的結(jié)點(diǎn)比較，相等則查找成功；不相等則根據(jù)比較結(jié)果確定下一步查找應(yīng)在哪個(gè)子表中進(jìn)行；重復(fù)上述過程，直至查找成功或子表長度為0。u 二分查找法的適用場合：u 線性表中的元素按關(guān)鍵字值遞增或遞減的次序排列；u 線性表采用順序存儲(chǔ)結(jié)構(gòu)。第59頁u練習(xí)u假設(shè)待查有序升序順序表中數(shù)據(jù)元素的關(guān)鍵字序列為8,18,27,42,47,50,56, 68,95,120），用折半查找方法查找

47、關(guān)鍵字值為27的數(shù)據(jù)元素.對(duì)于長度為對(duì)于長度為n n的有序線性表，最壞情況只需比較的有序線性表，最壞情況只需比較log2nlog2n次。次。 第60頁u 排序指將一個(gè)無序序列整理成按關(guān)鍵字值遞增或遞減排列的有序序列。u 排序方法中其排序?qū)ο笠话闶琼樞虼鎯?chǔ)的線性表。 u 根據(jù)排序序列的規(guī)模以及數(shù)據(jù)處理的要求，可以采用不同的排序方法：u交換類排序法 u冒泡排序u快速排序u 插入類排序法u簡單插入排序u希爾排序u選擇類排序法u簡單選擇排序u堆排序第61頁u 冒泡排序的方法：冒泡排序的方法：u掃描整個(gè)線性表，逐次對(duì)相鄰的兩個(gè)元素進(jìn)行比較，掃描整個(gè)線性表，逐次對(duì)相鄰的兩個(gè)元素進(jìn)行比較，若為逆序，則交換；

48、第一趟掃描的結(jié)果使最大若為逆序，則交換；第一趟掃描的結(jié)果使最大(或最或最小小)的元素排到表的最后的元素排到表的最后(或最前或最前) ；u除最后除最后(或最前或最前)一個(gè)元素，對(duì)剩余的元素重復(fù)上述一個(gè)元素，對(duì)剩余的元素重復(fù)上述過程，將次大過程，將次大(或次小或次小)的數(shù)排到表的倒數(shù)的數(shù)排到表的倒數(shù)(或正數(shù)或正數(shù))第第二個(gè)位置；二個(gè)位置；u重復(fù)上述過程；重復(fù)上述過程；u對(duì)于長度為對(duì)于長度為n的線性表，冒泡排序需要對(duì)表掃描的線性表，冒泡排序需要對(duì)表掃描n-1遍。遍。 第62頁冒泡排序的方法冒泡排序的方法u 設(shè)待排數(shù)據(jù)元素的關(guān)鍵字為18，20，15，32，4，25），第一趟冒泡排序后的序列狀態(tài)如圖所示

49、：u 18 20 15 32 4 25u 18 20 15 32 4 25u 18 15 20 32 4 25u 18 15 20 32 4 25u 18 15 20 4 32 25u 18 15 20 4 25 32 最大數(shù)u第二趟冒泡排序第二趟冒泡排序下一頁上一頁停止放映第第63|9263|92頁頁Q：第二趟冒泡排序后的結(jié)果是什么樣的？：第二趟冒泡排序后的結(jié)果是什么樣的？達(dá)到了最終的排序目標(biāo)嗎？一共需要多達(dá)到了最終的排序目標(biāo)嗎？一共需要多少次能夠最后成為有序序列？少次能夠最后成為有序序列？Q：你覺得冒泡排序的效率如何？如果是：你覺得冒泡排序的效率如何？如果是你，你會(huì)用什么方法來排序？你，你

50、會(huì)用什么方法來排序？ 冒泡排序比較簡單，當(dāng)初始序列基本有冒泡排序比較簡單，當(dāng)初始序列基本有序時(shí)，冒泡排序有較高的效率，反之效序時(shí)，冒泡排序有較高的效率，反之效率較低。率較低。冒泡排序終止條件冒泡排序終止條件: 本趟排序未發(fā)生交換，終止排序算法本趟排序未發(fā)生交換，終止排序算法 下一頁上一頁停止放映第第64|9264|92頁頁初始初始 第一趟第一趟 第二趟第二趟 第三趟第三趟 第四趟第四趟 第五趟第五趟序列序列 排序后排序后 排序后排序后 排序后排序后 排序后排序后 排序后排序后26 18 18 18 18 918 26 26 26 9 1532 32 32 9 15 1854 47 9 15 2

51、647 9 15 329 15 4715 54設(shè)待排數(shù)據(jù)元素的關(guān)鍵字為設(shè)待排數(shù)據(jù)元素的關(guān)鍵字為26,18,32,54,47,9,15 )冒泡排序法，需要比較的次數(shù)為冒泡排序法，需要比較的次數(shù)為n(n-1)/2n(n-1)/2； 第65頁u 選擇排序的方法：選擇排序的方法：u掃描整個(gè)線性表，從中找出最小的元素，與第一掃描整個(gè)線性表，從中找出最小的元素，與第一個(gè)元素交換；個(gè)元素交換；u除第一個(gè)元素，對(duì)剩下的子表采用相同的方法找除第一個(gè)元素，對(duì)剩下的子表采用相同的方法找出次小的數(shù)，與第二個(gè)數(shù)交換；出次小的數(shù)，與第二個(gè)數(shù)交換；u重復(fù)上述過程；重復(fù)上述過程；u對(duì)于長度為對(duì)于長度為n的線性表，選擇排序需要

52、對(duì)表掃描的線性表，選擇排序需要對(duì)表掃描n-1遍。遍。 簡單選擇排序法簡單選擇排序法, , 最壞情況需要最壞情況需要n(n-1)/2n(n-1)/2次比較；次比較； 下一頁上一頁停止放映第第66|9266|92頁頁u初態(tài)：初態(tài)： 15，14，22，30，37，15，11u第一趟：第一趟： 11 14，22，30，37，15，15u第二趟：第二趟： 11，14 22，30，37，15，15u第三趟：第三趟： 11，14，15 30，37，22，15u第四趟：第四趟： 11，14，15，15 37，22，30u第五趟：第五趟： 11，14，15，15，22 37，30u第六趟：第六趟： 11，14，

53、15，15，22，30 37u 有序序列有序序列例：設(shè)待排數(shù)據(jù)元素的關(guān)鍵字為例：設(shè)待排數(shù)據(jù)元素的關(guān)鍵字為15，14，22，30，37，11），每一趟排序后的序列狀態(tài)如圖所示：），每一趟排序后的序列狀態(tài)如圖所示：第67頁u簡單選擇排序法簡單選擇排序法, 最壞情況需要最壞情況需要n(n-1)/2次比較；次比較；u冒泡排序法冒泡排序法, 最壞情況需要最壞情況需要n(n-1)/2次比較；次比較；u希爾排序法希爾排序法, 最壞情況需要最壞情況需要O(n1.5)次比較；次比較；u堆排序法堆排序法, 最壞情況需要最壞情況需要O(nlog2n)次比較；次比較； 第68頁(1) 對(duì)于長度為對(duì)于長度為n的線性表，

54、在最壞情況下，下列各排序法所對(duì)應(yīng)的比較的線性表，在最壞情況下，下列各排序法所對(duì)應(yīng)的比較次數(shù)中正確的是次數(shù)中正確的是2019年年4月）月）A) 冒泡排序?yàn)槊芭菖判驗(yàn)閚/2 B) 冒泡排序?yàn)槊芭菖判驗(yàn)閚C) 快速排序?yàn)榭焖倥判驗(yàn)閚 D) 快速排序?yàn)榭焖倥判驗(yàn)閚(n-1)/2(2)在長為在長為64的有序線性表中進(jìn)行順序查找，最壞情況下需要比較的次數(shù)的有序線性表中進(jìn)行順序查找，最壞情況下需要比較的次數(shù)為為_。（。（06年年9月）月） A）、）、63 B）、）、64 C）、）、6 D）、）、7(3) 下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進(jìn)行查找的是下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進(jìn)行查找的是2019年年9月）月） A順

55、序存儲(chǔ)的有序線性表順序存儲(chǔ)的有序線性表 B線性鏈表線性鏈表 C二叉鏈表二叉鏈表 D有序線性鏈表有序線性鏈表(4) 下列排序方法中，最壞情況下比較次數(shù)最少的是下列排序方法中，最壞情況下比較次數(shù)最少的是09年年3月）月） A冒泡排序冒泡排序 B簡單選擇排序簡單選擇排序 C直接插入排序直接插入排序 D堆排序堆排序DBAD第69頁第70頁u結(jié)構(gòu)化程序設(shè)計(jì)方法的四條原則是：結(jié)構(gòu)化程序設(shè)計(jì)方法的四條原則是：u1. 自頂向下；自頂向下；u2. 逐步求精；逐步求精；u3. 模塊化；模塊化；u4. 限制使用限制使用goto語句。語句。u 結(jié)構(gòu)化程序的基本結(jié)構(gòu)和特點(diǎn)：結(jié)構(gòu)化程序的基本結(jié)構(gòu)和特點(diǎn)：（1順序結(jié)構(gòu)：順序

56、結(jié)構(gòu)：u 簡單的程序設(shè)計(jì)，最基本、最常用的結(jié)構(gòu)；簡單的程序設(shè)計(jì)，最基本、最常用的結(jié)構(gòu)；（2選擇結(jié)構(gòu)分支結(jié)構(gòu)）：選擇結(jié)構(gòu)分支結(jié)構(gòu)）：u 包括簡單選擇和多分支選擇結(jié)構(gòu)，包括簡單選擇和多分支選擇結(jié)構(gòu)，（3重復(fù)結(jié)構(gòu)循環(huán)結(jié)構(gòu)）：重復(fù)結(jié)構(gòu)循環(huán)結(jié)構(gòu)）：u 可根據(jù)給定條件，判斷是否需要重復(fù)執(zhí)行某一相可根據(jù)給定條件，判斷是否需要重復(fù)執(zhí)行某一相同程序段。同程序段。第71頁對(duì)象是面向?qū)ο蠓椒ㄖ凶罨镜母拍?。?duì)象是面向?qū)ο蠓椒ㄖ凶罨镜母拍睢?對(duì)象是系統(tǒng)中用來描述客觀事物的一個(gè)實(shí)體，是對(duì)象是系統(tǒng)中用來描述客觀事物的一個(gè)實(shí)體，是構(gòu)成系統(tǒng)的一個(gè)基本單位，由一組表示其靜態(tài)構(gòu)成系統(tǒng)的一個(gè)基本單位，由一組表示其靜態(tài)特征的屬性和

57、它可執(zhí)行的一組操作組成。特征的屬性和它可執(zhí)行的一組操作組成。屬性即對(duì)象所包含的信息屬性即對(duì)象所包含的信息操作描述了對(duì)象執(zhí)行的功能，操作也稱為方法或操作描述了對(duì)象執(zhí)行的功能，操作也稱為方法或服務(wù)。服務(wù)。第72頁u類是指具有共同屬性、共同方法的對(duì)象的集合。類是指具有共同屬性、共同方法的對(duì)象的集合。u所以類是對(duì)象的抽象，對(duì)象是對(duì)應(yīng)類的一個(gè)實(shí)例。所以類是對(duì)象的抽象，對(duì)象是對(duì)應(yīng)類的一個(gè)實(shí)例。u消息是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信息。消息是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信息。消息的組成包括消息的組成包括u （1接收消息的對(duì)象的名稱；接收消息的對(duì)象的名稱；u （2消息標(biāo)識(shí)符，也稱消息名；消息標(biāo)識(shí)符，也稱消

58、息名；u （3零個(gè)或多個(gè)參數(shù)。零個(gè)或多個(gè)參數(shù)。u繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們。復(fù)定義他們。u 單繼承指一個(gè)類只允許有一個(gè)父類單繼承指一個(gè)類只允許有一個(gè)父類u 多重繼承指一個(gè)類允許有多個(gè)父類。多重繼承指一個(gè)類允許有多個(gè)父類。u多態(tài)性是指同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完多態(tài)性是指同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同的行動(dòng)的現(xiàn)象。全不同的行動(dòng)的現(xiàn)象。第73頁程序設(shè)計(jì)基礎(chǔ)方面的考題程序設(shè)計(jì)基礎(chǔ)方面的考題1.符合結(jié)構(gòu)化原則的三種基本控制結(jié)構(gòu)是：選擇結(jié)構(gòu)、循環(huán)結(jié)符合結(jié)構(gòu)化原則的三種基本控制結(jié)構(gòu)是：選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)和【構(gòu)和

59、【 】 . (2009年年3月月)2. 下列選項(xiàng)中不屬于結(jié)構(gòu)化程序設(shè)計(jì)原則的是下列選項(xiàng)中不屬于結(jié)構(gòu)化程序設(shè)計(jì)原則的是2009年年9月）月）A) 可封裝可封裝 D) 自頂向下自頂向下 C) 模塊化模塊化 D) 逐步求精逐步求精3. 以下敘述中正確的是。（以下敘述中正確的是。（2019年年3月）月） A程序設(shè)計(jì)的任務(wù)就是編寫程序代碼并上機(jī)調(diào)試程序設(shè)計(jì)的任務(wù)就是編寫程序代碼并上機(jī)調(diào)試 B程序設(shè)計(jì)的任務(wù)就是確定所用數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)的任務(wù)就是確定所用數(shù)據(jù)結(jié)構(gòu) C程序設(shè)計(jì)的任務(wù)就是確定所用算法程序設(shè)計(jì)的任務(wù)就是確定所用算法 D以上三種說法都不完整以上三種說法都不完整4.在面向?qū)ο蠓椒ㄖ校惖膶?shí)例稱為在面向

60、對(duì)象方法中，類的實(shí)例稱為 【_】 。（。（2019年年4月）月）5.在面向?qū)ο蠓椒ㄖ性诿嫦驅(qū)ο蠓椒ㄖ? 【_】 描述的是具有相似屬性與操描述的是具有相似屬性與操作的一組對(duì)象。（作的一組對(duì)象。（2019年年4月）月）（順序結(jié)構(gòu)）（順序結(jié)構(gòu)）A D對(duì)象對(duì)象類類第74頁第三章第三章 軟件工程基礎(chǔ)軟件工程基礎(chǔ)u計(jì)算機(jī)軟件是包括程序、數(shù)據(jù)及相關(guān)文計(jì)算機(jī)軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。檔的完整集合。u軟件按功能分為應(yīng)用軟件、系統(tǒng)軟件、軟件按功能分為應(yīng)用軟件、系統(tǒng)軟件、支撐軟件或工具軟件）。支撐軟件或工具軟件）。第75頁1.軟件工程概念軟件工程概念u軟件工程是應(yīng)用于計(jì)算機(jī)軟件的定義、開發(fā)和維護(hù)的軟