公共基礎ACCESS培訓講解

公共基礎ACCESS培訓講解對培訓學員要求

1、明確自己，明確目標！

2、注重方法，100％投入！

3、團隊合作，共解難題！

4、注重資料，按章按知識點逐一把握

5、不拋棄不放棄，堅持就是勝利！自信——堅持——成功2考試方式筆試（選擇題35個+填空題15空）公共基礎知識（30分；識記為主，理解及推導為輔）數(shù)據(jù)庫程序設計（70分；假期把握練習冊）機試（三大題）以真題為準，強化練習！基本操作30分簡單應用40分綜合應用30分3公共基礎知識

（四個部分——筆試-30分）

★記憶為主，理解推導為輔

（暑假必須完成該部分，假后考核?。?/p>

一、基本數(shù)據(jù)結構與算法

4本部分主要內(nèi)容算法數(shù)據(jù)結構數(shù)據(jù)結構研究的主要內(nèi)容基本概念和術語數(shù)據(jù)結構類型線性結構和非線性結構順序存儲與鏈式存儲線性表棧和隊列線性鏈表樹與二叉樹查找和排序圖基本數(shù)據(jù)結構與算法5基本數(shù)據(jù)結構與算法1.1算法算法的基本概念（重點）算法：解題方案的準確而完整的描述。算法的基本特征：是一組嚴謹?shù)囟x運算順序的規(guī)則，每一個規(guī)則都是有效的，是明確的，此順序將在有限的次數(shù)下終止。算法不等于程序，程序不可能優(yōu)于算法?；咎匦钥尚行裕焊鶕?jù)實際問題設計的算法，執(zhí)行得到滿意結果確定性：每一步驟必須有明確定義，不允許有多義性。有窮性：算法必須能在有限的時間內(nèi)做完。擁有足夠的情報:輸入和輸出必須擁有足夠的情報：，方可執(zhí)行。6基本數(shù)據(jù)結構與算法1.1算法算法的基本要素（了解）1.對數(shù)據(jù)對象的運算和操作算術運算：＋、－、×、÷等邏輯運算：>、<、＝、>=、<=、等關系運算：、、等數(shù)據(jù)傳輸：輸入、輸出、賦值等2.算法的控制結構算法中各操作之間的執(zhí)行順序描述算法的工具通常有傳統(tǒng)流程圖、結構化流程圖、算法描述語言等算法可以用順序、選擇、循環(huán)三種基本機構組合而成。7基本數(shù)據(jù)結構與算法1.1算法算法設計基本方法（了解）（1）列舉法：根據(jù)問題，列舉所有可能的情況，并用問題中給定的條件檢驗哪些是需要的，哪些是不需要的。（2）歸納法：通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關系。（3）遞推：是指從已知的初始條件出發(fā)，逐次推出所要求的各中間結果和最后結果。（4）遞歸：將問題逐層分解的過程。（5）減半遞推技術：“減半”，是指將問題規(guī)模減半，而問題性質不變；“遞推”，是指重復“減半”過程。（6）回溯法：分析問題，找出一個解決總線索，然后沿著這個線索逐步試探。8基本數(shù)據(jù)結構與算法1.1算法算法的復雜度：時間復雜度、空間復雜度（重點）算法的時間復雜度算法時間復雜度是指執(zhí)行算法所需要的計算工作量。工作量用算法所執(zhí)行的基本運算次數(shù)來度量，而算法所執(zhí)行的基本運算次數(shù)是問題規(guī)模的函數(shù)，即算法的工作量(n)算法空間復雜度算法空間復雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。存儲空間包括：①算法程序所占的空間、②輸入數(shù)據(jù)所占的空間、③算法執(zhí)行過程中所需要的額外空間。。9基本數(shù)據(jù)結構與算法通關練習1.下列敘述中正確的是（）。

A.算法的效率只與問題規(guī)模有關，與存儲結構無關。

B.算法的時間復雜度是指執(zhí)行算法所需的計算工作量。

C.數(shù)據(jù)的邏輯結構與存儲結構是一一對應的。

D.算法的時間復雜度與空間復雜度一定相關。2.算法的時間復雜度取決于（）。

A.問題的規(guī)模B.問題的困難度

C.待處理的數(shù)據(jù)的初始狀態(tài)和C3.描述算法的常用方法有（）。4.一個算法的時間復雜度是（）的函數(shù)。5.算法復雜度主要包括時間復雜度和（）復雜度。BD傳統(tǒng)流程圖、圖、偽代碼問題規(guī)?？臻g10基本數(shù)據(jù)結構與算法練習參考答案1、B2、D3、傳統(tǒng)流程圖、結構化流程圖和偽碼描述語言

4、問題規(guī)模5、空間11基本數(shù)據(jù)結構與算法1.2數(shù)據(jù)結構研究的主要內(nèi)容當今計算機應用的特點（了解）所處理的數(shù)據(jù)量大且具有一定的關系；對其操作不再是單純的數(shù)值計算，而更多地是需要對其進行組織、管理和檢索。應用舉例1——學籍檔案管理（了解）假設一個學籍檔案管理系統(tǒng)應包含如下表所示的學生信息。12基本數(shù)據(jù)結構與算法特點（了解）每個學生的信息占據(jù)一行，所有學生的信息按學號順序依次排列構成一張表格；表中每個學生的信息依據(jù)學號的大小存在著一種前后關系.對它的操作通常是插入某個學生的信息，刪除某個學生的信息，更新某個學生的信息，按條件檢索某個學生的信息等等。1.2數(shù)據(jù)結構研究的主要內(nèi)容13基本數(shù)據(jù)結構與算法應用舉例2—制定教學計劃（了解）在制定教學計劃時，需要考慮各門課程的開設順序。有些課程需要先導課程，有些則不需要;而有些課程又是其他課程的先導課程。比如，計算機專業(yè)課程的開設情況如下表所示：1.2數(shù)據(jù)結構研究的主要內(nèi)容14基本數(shù)據(jù)結構與算法課程先后關系的圖形描形式c1

c9

c4

c2

c12

c10

c11

c5

c3

c6

c7

c8

1.2數(shù)據(jù)結構研究的主要內(nèi)容特點（了解）課程的先后關系用圖結構描述；通過實施創(chuàng)建圖結構，按要求將圖結構中的頂點進行線性排序。15基本數(shù)據(jù)結構與算法

數(shù)據(jù)結構主要研究以下三個方面的問題：重點掌握數(shù)據(jù)的邏輯結構：數(shù)據(jù)集合中各元素的信息，及元素之間所固有的邏輯關系（前后件關系）數(shù)據(jù)的存儲結構：各數(shù)據(jù)元素在計算機中的存儲關系對各種數(shù)據(jù)結構進行的運算主要目的是為了提高數(shù)據(jù)處理的效率。所謂提高數(shù)據(jù)處理的效率，主要包括兩個方面：一是提高數(shù)據(jù)處理的速度，二是盡量節(jié)省在數(shù)據(jù)處理過程中所占用的計算機存儲空間。1.2數(shù)據(jù)結構研究的主要內(nèi)容16基本數(shù)據(jù)結構與算法

數(shù)據(jù)結構是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學科。一句話，數(shù)據(jù)結構是相互有關聯(lián)的數(shù)據(jù)元素的集合。（重點）1.2.1基本概念和術語17基本數(shù)據(jù)結構與算法能輸入到計算機中并能被計算機程序處理的符號的集合。整數(shù)(1,2)、實數(shù)(1.1,1.2)字符串()、圖形、聲音。

數(shù)據(jù)結構是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學科。1.2.1基本概念和術語（了解）18基本數(shù)據(jù)結構與算法計算機管理圖書問題圖書館里有各種卡片：有按書名編排的、有按作者編排的、有按分類編排。如何將查詢圖書的這些信息存入計算機中既要考慮查詢時間短，又要考慮節(jié)省空間

數(shù)據(jù)結構是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學科。1.2.1基本概念和術語（了解）19基本數(shù)據(jù)結構與算法最簡單的辦法之一是建立一張表，每一本書的信息在表中占一行，如

數(shù)據(jù)結構是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學科。1.2.1基本概念和術語（了解）20基本數(shù)據(jù)結構與算法

如何將0,1,2,3,4,5,6,7,8,9這10個數(shù)存放在計算機中能最快地達到你所需要的目的？目的不同，最佳的存儲方方法就不同。從大到小排列：9,8,7,6,5,4,3,2,1,0輸出偶數(shù)：0,2,4,6,8,1,3,5,7,9數(shù)據(jù)元素在計算機中的表示

數(shù)據(jù)結構是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學科。1.2.1基本概念和術語（了解）21基本數(shù)據(jù)結構與算法對數(shù)據(jù)結構中的節(jié)點進行操作處理(插入、刪除、修改、查找、排序)

數(shù)據(jù)結構是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學科。1.2.1基本概念和術語（了解）22基本數(shù)據(jù)結構與算法數(shù)據(jù)元素()

數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個體。有時一個數(shù)據(jù)元素可由若干數(shù)據(jù)項()組成。數(shù)據(jù)項是數(shù)據(jù)的最小單位。數(shù)據(jù)元素亦稱節(jié)點或記錄。1.2.1基本概念和術語（重點）23基本數(shù)據(jù)結構與算法數(shù)據(jù)邏輯結構描述（D，R）有限個數(shù)據(jù)元素的集合有限個節(jié)點間關系的集合1.2.1基本概念和術語如：（D，R）

{,…}{(),(),…()}如：（D，R）

{父親,兒子,女兒}{(父親,兒子),(父親,女兒)}（了解）24基本數(shù)據(jù)結構與算法1．數(shù)據(jù)的邏輯結構2、數(shù)據(jù)的存儲結構3、數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等。A．線性結構B．非線性結構A順序存儲B鏈式存儲線性表棧隊列樹形結構圖形結構數(shù)據(jù)結構的三個方面1.3數(shù)據(jù)結構類型（重點）C索引存儲25基本數(shù)據(jù)結構與算法1.3.1線性結構和非線性結構

線性結構條件（1）有且只有一個根結點；（2）每一個結點最多有一個前件，也最多有一個后件。（3）首節(jié)點無前件，尾節(jié)點無后件。非線性結構：不滿足線性結構條件的數(shù)據(jù)結構注意：在一個線性結構中插入或刪除任何一個節(jié)點后還應是線性結構；否則，不能稱為線性結構。只有一個結點的數(shù)據(jù)結構是非線性結構。（重點）26基本數(shù)據(jù)結構與算法1.3.1線性結構和非線性結構全校學生檔案管理的樹形結構的組織方式非線性結構

樹形結構（了解）27基本數(shù)據(jù)結構與算法ABCDEFGH樹形結構—結點間具有分層次的連接關系HBCDEFGA1.3.1線性結構和非線性結構

樹形結構（了解）28基本數(shù)據(jù)結構與算法1.3.1線性結構和非線性結構

圖形結構（網(wǎng)狀結構）：節(jié)點間的連接任意1423D={1,2,3,4}R={(1,2),(1,3),(1,4),(2,3)(3,4),(2,4)}無向圖213D={1,2,3}R={(1,2),(2,3),(1,3)}有向圖（了解）29基本數(shù)據(jù)結構與算法Lo+（n-1)*m元素n……..元素i……..元素2元素1Lo

Lo+mLo+(i-1)*m存儲地址存儲內(nèi)容Loc(i)=Lo+（i-1)*m每個元素所占用的存儲單元大小(Byte)1.3.2順序存儲與鏈式存儲

順序存儲常用于線性數(shù)據(jù)結構，將邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里。三個弱點插入或刪除操作時，需移動大量元素。長度變化較大時，需按最大空間分配。表的容量難以擴充（重點）30基本數(shù)據(jù)結構與算法每個節(jié)點都由兩部分組成：數(shù)據(jù)域和指針域。數(shù)據(jù)域：存放元素本身的數(shù)據(jù)，指針域：存放指針，體現(xiàn)數(shù)據(jù)元素之間的邏輯聯(lián)系1.3.2順序存儲與鏈式存儲1536元素21400元素11346元素3∧元素4head1345

鏈接存儲結構特點邏輯上相鄰的節(jié)點物理上不必相鄰。最大優(yōu)點：插入、刪除靈活(不必移動節(jié)點，僅改變節(jié)點中的指針)。鏈接存儲結構（重點）31基本數(shù)據(jù)結構與算法1346

元素31536…….……..…….1536

元素21400…….……..…….∧

元素413461400

元素11345

指針

存儲內(nèi)容存儲地址1.3.2順序存儲與鏈式存儲鏈式存儲的地址映射表指向首元素位置1536元素21400元素11346元素3∧元素4head1345

（重點）每個鏈式結構都是以頭結點（）開始，以尾結點指針域存放0或表示鏈表的結束。32基本數(shù)據(jù)結構與算法1、鏈表不具有的特點是（）

A)不必事先估計存儲空間B)插入刪除不需要移動元素

C)可隨機訪問任一元素D)所需空間與線性表長度成正比2、數(shù)據(jù)結構中，與所使用的計算機無關的是數(shù)據(jù)的（）

A)存儲結構 B)物理結構

C)邏輯結構 D)物理和存儲結構3、根據(jù)數(shù)據(jù)結構中各數(shù)據(jù)元素之間前后件關系的復雜程度，一般將數(shù)據(jù)結構分成（）

A)動態(tài)結構和靜態(tài)結構 B)緊湊結構和非緊湊結構

C)線性結構和非線性結構D)內(nèi)部結構和外部結構4、數(shù)據(jù)處理的最小單位是（）

A)數(shù)據(jù)B)數(shù)據(jù)元素C)數(shù)據(jù)項D)數(shù)據(jù)結構通關練習CCCC33基本數(shù)據(jù)結構與算法5、下列敘述中，錯誤的是（）

A)數(shù)據(jù)的存儲結構與數(shù)據(jù)處理的效率密切相關

B)數(shù)據(jù)的存儲結構與數(shù)據(jù)處理的效率無關

C)數(shù)據(jù)的存儲結構在計算機中所占空間不一定是連續(xù)的

D)一種數(shù)據(jù)的邏輯結構可以有多種存儲結構6、線性表的順序存儲結構和線性表的鏈式存儲結構分別是（)A)順序存取的存儲結構、順序存取的存儲結構

B)隨機存取的存儲結構、順序存取的存儲結構

C)隨機存取的存儲結構、隨機存取的存儲結構

D)任意存取的存儲結構、任意存取的存儲結構7、數(shù)據(jù)結構作為計算機的一門學科，主要研究數(shù)據(jù)的邏輯結構、對各種數(shù)據(jù)結構進行的運算，以及（）

A)數(shù)據(jù)的存儲結構 B)計算方法

C)數(shù)據(jù)映象D)邏輯存儲通關練習BBA34基本數(shù)據(jù)結構與算法8、下列敘述中正確的是（）A）程序執(zhí)行的效率與數(shù)據(jù)的存儲結構密切相關B）程序執(zhí)行的效率只取決于程序的控制結構C）程序執(zhí)行的效率只取決于所處理的數(shù)據(jù)量D）以上都不對9、數(shù)據(jù)的存儲結構是指（）A）數(shù)據(jù)所占的存儲空間B）數(shù)據(jù)的邏輯結構在計算機中的表示C）數(shù)據(jù)在計算機中的順序存儲方式D）存儲在外存中的數(shù)據(jù)10、數(shù)據(jù)（）包括集合、線性結構、樹形結構和圖4種類型。A)算法描述B)基本運算C)邏輯結構D)存儲結構通關練習ABC35基本數(shù)據(jù)結構與算法11、數(shù)據(jù)在計算機內(nèi)存中的表示是指（）A）數(shù)據(jù)的存儲結構B）數(shù)據(jù)結構C）數(shù)據(jù)的邏輯機構D）數(shù)據(jù)元素間的關系12、數(shù)據(jù)結構研究的主要內(nèi)容包括（）、（）和數(shù)據(jù)元素之間的三方面聯(lián)系。13、順序存儲方法是把邏輯上相鄰的結點存儲在物理位置（）的存儲單元中。14、數(shù)據(jù)的基本單位是（）。15、數(shù)據(jù)結構分為邏輯結構與存儲結構，線性鏈表屬于（）16、數(shù)據(jù)的邏輯結構有線性結構和（）兩大類。通關練習A36基本數(shù)據(jù)結構與算法練習參考答案1～5、6～11、

12、數(shù)據(jù)存儲結構、數(shù)據(jù)邏輯結構

13、相鄰

14、數(shù)據(jù)元素

15、存儲結構

16、非線性結構37基本數(shù)據(jù)結構與算法1.3.3線性表線性表的基本概念（了解）線性表由一組數(shù)據(jù)元素構成，數(shù)據(jù)元素的位置只取決于自己的序號，元素之間的相對位置是線性的。非空線性表的結構特征(重點)有且只有一個根結點a1，它無前件；有且只有一個終端結點，它無后件；除根結點與終端結點外，其他所有結點有且只有一個前件，也有且只有一個后件。結點個數(shù)n稱為線性表的長度，當0時，稱為空表。Lo+（n-1)*m元素n……..元素i……..元素2元素1Lo

Lo+mLo+(i-1)*m存儲地址存儲內(nèi)容Loc(i)=Lo+（i-1)*m38基本數(shù)據(jù)結構與算法線性表的插入/刪除操作在長度為n的線性表中第i個數(shù)據(jù)元素之前插入數(shù)據(jù)元素e

則移動元素個數(shù)：1線性表插入/刪除運算，平均移動元素的個數(shù)為：2，最壞情況下是n.1.3.3線性表(重點)39基本數(shù)據(jù)結構與算法線性表的插入操作（時間復雜度O(n)）插入前插入xlastMaxsize-1aia1a0ai-1ai+1an-1a0a1ai-1aian-1lastMaxsize-1后移后ai＋1a0a1ai-1ai+1ai+1anxlastMaxsize-1插入后ai+21.3.3線性表（了解）40基本數(shù)據(jù)結構與算法線性表的刪除操作（時間復雜度O(n)）1.3.3線性表a0a1ai-1aiai+1an-1刪除lastmaxsize刪除前a0a1ai-1ai+2an-1lastmaxsize刪除后ai+1（了解）41基本數(shù)據(jù)結構與算法1、線性表(a123,…，…)，下列說法正確的是（）

A)每個元素都有一個直接前件和直接后件

B)線性表中至少要有一個元素

C)表中諸元素的排列順序必須是由小到大或由大到小

D)除第一個元素和最后一個元素外，其余每個元素都有一個且只有一個直接前件和直接后件2、線性表采用鏈式存儲結構時，則內(nèi)存中可用存儲單元地址

A)必須是連續(xù)的 B)部分地址必須是連續(xù)的

C)一定是不連續(xù)的D)連續(xù)不連續(xù)都可以過關練習DD42基本數(shù)據(jù)結構與算法練習參考答案3、在一個長度為n的順序表中，向第i個元素位置插入一個新元素時，需要向后移動（）個元素

A)B)iC)1D)14、長度為n的順序存儲線性表，當在任何位置上插入一個元素概率都相等時，插入一個元素所需移動元素的平均個數(shù)為（）。

D243基本數(shù)據(jù)結構與算法1.3.4棧和隊列

棧和隊列是兩種運算時要受到某些特殊限制的線性表，故也稱為限定性的數(shù)據(jù)結構。棧：限定只能在表的一端進行插入和刪除的特殊的線性表,此種結構稱為后進先出（）。設棧（a1，a2，…，…，）其中a1是棧底元素，是棧頂元素。棧頂（)：允許插入和刪除的一端；約定始終指向新數(shù)據(jù)元素將存放的位置。棧底（):不允許插入和刪除的一端。棧是先進后出,后進先出結構

a1a2….an

進棧出棧棧頂棧底(重點)44基本數(shù)據(jù)結構與算法隊列的主要運算設置一個空隊列；令0插入一個新的隊尾（）元素，稱為進隊；刪除隊頭（）元素，稱為出隊；讀取隊頭元素；a1,a2,a3,a4,…………1,隊頭隊尾1.3.4棧和隊列隊列：限定只能在表的一端進行插入，在表的另一端進行刪除的線性表。此種結構稱為先進先出（）表。(重點)45基本數(shù)據(jù)結構與算法

3210(a)rear=front=0(隊空）

e3

e4

(c)e1,e2出隊，e4入隊rear=4fronte1e2e3

(b)rearfront(b)e1,e2,e3入隊1.3.4棧和隊列隊列的主要運算隊空時，令0;元素個數(shù)＝當有新元素入隊時，尾指針加1，當有元素出隊時，頭指針加1。故在非空隊列中，頭指針始終指向隊頭元素前一個位置，而尾指針始終指向隊尾元素的位置(重點)46基本數(shù)據(jù)結構與算法循環(huán)隊列元素個數(shù)=()na1,a2,a3,a4,…………1,隊頭隊尾1.3.4棧和隊列循環(huán)隊列：首尾相接的隊列，邏輯上形成一個環(huán)狀。(了解)47基本數(shù)據(jù)結構與算法1、棧和隊列的共同特點是（）

A)都是先進先出B)都是先進后出

C)只允許在端點處插入和刪除元素D)沒有共同點2、如果進棧序列為e1234，則可能的出棧序列是（）

A)e3142 B)e2431C)e3412 D)任意順序3、在順序棧中進行退棧操作時，（）。Ａ）誰先誰后都可以B）先移動棧頂指針，后取出元素C）不分先后，同時進行D）先取出元素，后移動棧頂指針過關練習CBD48基本數(shù)據(jù)結構與算法4、下列關于隊列的敘述中正確的是（）Ａ）在隊列中只能插入數(shù)據(jù)B）在隊列中只能刪除數(shù)據(jù)C）隊列是先進先出的線性表D）隊列是后進先出的線性表5、下列數(shù)據(jù)結構中，按先進后出原則組織數(shù)據(jù)的是（）

A)線性鏈表B)棧C)循環(huán)鏈表D)順序表6、下列關于棧的敘述中正確的是（）Ａ）在棧中只能插入數(shù)據(jù)B）在棧中只能刪除數(shù)據(jù)C）棧是先進先出的線性表D）棧是后進先出的線性表過關練習CBD49基本數(shù)據(jù)結構與算法8、線性表的存儲結構主要分為順序存儲結構和鏈式存儲結構。隊列是一種特殊的線性表，循環(huán)隊列是隊列的（）存儲結構。9、數(shù)據(jù)結構分為線性結構和非線性結構，帶鏈的隊列屬于（）。10、通常元素進棧的順序是（）。11、從一個循環(huán)隊列中刪除一個元素，通常的操作是（）。過關練習注意：一般元素進棧或入隊的順序（即插入一個元素）：先移動棧頂指針或隊尾指針，然后插入元素。元素出?；虺鲫牭捻樞颍磩h除一個元素）：先讀出元素，然后移動棧頂指針或對頭指針。順序線性結構先移動棧頂指針，后存入元素先取出元素，后移動對頭指針50基本數(shù)據(jù)結構與算法練習參考答案1～5、6～7、

8、順序9、線性結構

10、先移動棧頂指針，后存入元素

11、先取出元素，后移動對頭指針51基本數(shù)據(jù)結構與算法1.3.5線性鏈表線性表順序存儲結構的特點簡單、方便，要求數(shù)據(jù)元素依次存放在連續(xù)的存儲單元中，從而利用數(shù)據(jù)元素的存儲順序表示相應的邏輯順序，這種存儲方式屬于靜態(tài)存儲形式。暴露的問題在做插入或刪除元素的操作時，會產(chǎn)生大量的數(shù)據(jù)元素移動；對于長度變化較大的線性表，要一次性地分配足夠的存儲空間，但這些空間常常又得不到充分的利用；線性表的容量難以擴充。52基本數(shù)據(jù)結構與算法

將線性表的元素放到一個具有頭指針的鏈表中，鏈表中每個結點包含數(shù)據(jù)域和指針域。

數(shù)據(jù)域存放數(shù)據(jù)，指針域存放后繼結點的地址，最后一個結點的指針域為空(即為0或)。邏輯上相鄰的數(shù)據(jù)元素在內(nèi)存中的物理存儲空間不一定相鄰。線性鏈表分為：單鏈表、雙鏈表、循環(huán)鏈表1.3.5線性鏈表

a1

a2∧an

a3

L…..帶頭結點的單鏈表(重點)53基本數(shù)據(jù)結構與算法單鏈表：每個結點只有一個指針域，由該指針只能找到其后件結點。1.3.5線性鏈表54基本數(shù)據(jù)結構與算法1.3.5線性鏈表線性鏈表的特點插入、刪除節(jié)點方便(不必移動節(jié)點，僅改變節(jié)點中的指針)只能順序存?。ú檎抑荒軓念^指針開始），不能隨機存取。適應于數(shù)據(jù)的動態(tài)變化(重點)55基本數(shù)據(jù)結構與算法1、鏈表不具有的特點是（）

A)不必事先估計存儲空間B)可隨機訪問任一元素

C)插入刪除不需要移動元素D)所需空間與線性表長度成正比2、用鏈表表示線性表的優(yōu)點是（）

A)便于隨機存取B)花費的存儲空間較順序存儲少

C)便于插入和刪除操作

D)數(shù)據(jù)元素的物理順序與邏輯順序相同3、線性表(a123,…，…)，下列說法正確的是（）

A)每個元素都有一個直接前件和直接后件

B)線性表中至少要有一個元素

C)表中諸元素的排列順序必須是由小到大或由大到小

D)除第一個元素和最后一個元素外，其余每個元素都有一個且只有一個直接前件和直接后件過關練習BCD56基本數(shù)據(jù)結構與算法4、下列敘述中正確的是（）。

A)線性鏈表是線性表的鏈式存儲結構

B)棧與隊列是非線性結構

C)雙向鏈表是非線性結構

D)只有根結點的二叉樹是線性結構5、循環(huán)鏈表的主要優(yōu)點是（）

A)不再需要頭指針了

B)從表中任一結點出發(fā)都能訪問到整個鏈表

C)在進行插入、刪除運算時，能更好的保證鏈表不斷開

D)已知某個結點的位置后，能夠容易的找到它的直接前件

過關練習AB57基本數(shù)據(jù)結構與算法6、線性表的順序存儲結構和線性表的鏈式存儲結構分別是

A)順序存取的存儲結構、順序存取的存儲結構

B)隨機存取的存儲結構、順序存取的存儲結構

C)隨機存取的存儲結構、隨機存取的存儲結構

D)任意存取的存儲結構、任意存取的存儲結構7、用鏈表表示線性表的突出優(yōu)點是（）。8、長度為n的順序存儲線性表中，當在任何位置上插入一個元素概率都相等時，插入一個元素所需移動元素的平均個數(shù)為（）。過關練習B插入刪除節(jié)點方便258基本數(shù)據(jù)結構與算法練習參考答案1～6、

7、插入、刪除結點方便

8、259基本數(shù)據(jù)結構與算法樹的定義：由一個或多個結點組成的有限集合。僅有一個根結點，結點間有明顯的層次結構關系。ACGT2

DHIT3

J

MBELKT1

F

現(xiàn)實世界中，能用樹的結構表示：學校的行政關系、書的層次結構、人類的家族血緣關系等。1.3.6樹與二叉樹60基本數(shù)據(jù)結構與算法樹的基本概念：結點（）：樹中的元素結點的度（）：結點擁有的子樹數(shù)（后件數(shù)）。樹的度：所有結點中最大的度結點的層次：從根結點開始算起，根為第一層。葉子（）：度為零的結點，也稱端結點。深度/高度（)：樹中結點的最大層次數(shù)。ACGT2

DHIT3

J

MBELKT1

F1.3.6樹與二叉樹(重點)61基本數(shù)據(jù)結構與算法二叉樹（）的定義二叉樹的五種基本形態(tài)

空二叉樹

僅有根結點

右子樹為空

左子樹為空左右子樹均非空1.3.6樹與二叉樹二叉樹是一種很有用的非線性結構，它具有以下兩個特點：1）非空二叉樹只有一個根結點；2）每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。次序不能顛倒。(重點)62基本數(shù)據(jù)結構與算法滿二叉樹423167891011121314155

特點：所有分支結點都存在左右子樹，且所有葉子結點都在同一層上。即每一層上都含有最大結點數(shù)。1.3.6樹與二叉樹(重點)63基本數(shù)據(jù)結構與算法423167891011125

非完全二叉樹

完全二叉樹423167891011125

完全二叉樹

特點：除最后一層外，每一層都取最大結點數(shù)，最后一層結點都集中在該層最左邊的若干位置。1.3.6樹與二叉樹(重點)注意：滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。64性質1：在任意一棵二叉樹中，度為0的結點（即葉子結點）總是比度為2的結點多一個。例子1：某二叉樹中度為2的結點有18個，則該二叉樹中有個葉子結點。二叉樹的性質：6519算法與數(shù)據(jù)結構65性質2：二叉樹的第i層上至多有21（i1）個結點二叉樹的性質：423167891011121314155第三層上(3)，有23-1=4個節(jié)點。第四層上(4)，有24-1=8個節(jié)點。66性質3：深度為h的二叉樹中至多含有21個結點423167891011121314155此樹的深度4，共有24-1=15個節(jié)點。二叉樹的性質：67基本數(shù)據(jù)結構與算法A、二叉樹的第i層上最多有21（i1）個結點。B、深度為h的二叉樹中最多含有21個結點。C、若在任意一棵二叉樹中，有n0個葉子結點（度為0），有n2個度為2的結點，則：n02+1D、具有n個結點的二叉樹的深度至少為[2n]+1，其中[2n]表示2n的整數(shù)部分。二叉樹的基本性質總結4231678910111213141551.3.6樹與二叉樹第三層(3)，有23-1=4個節(jié)點深度4，共有24-1=15個節(jié)點n0=82=702+115個節(jié)點，深度=[215]+1=4(重點)68基本數(shù)據(jù)結構與算法E、具有n個結點的完全二叉樹的深度為[2n]+1，其中[2n]表示2n的整數(shù)部分。F、任意完全二叉樹：度為1的結點數(shù)只能為0或1二叉樹的基本性質總結1.3.6樹與二叉樹一般情況下(規(guī)律)：1、任意二叉樹總結點數(shù)：0122、任意二叉樹中總有：n02+13、任意完全二叉樹中總有：n1=0或n1=1(重點)69

對于完全二叉樹而言，通用規(guī)律：若它的結點個數(shù)為偶數(shù)，則該二叉樹中： 葉子結點的個數(shù)=非葉子結點的個數(shù)若它的結點個數(shù)為奇數(shù)，則該二叉樹中： 葉子結點的個數(shù)=非葉子結點的個數(shù)+1

（即葉子結點數(shù)比非葉子結點數(shù)多一個）(重點)1.3.6樹與二叉樹70

實題講解1、設一棵完全二叉樹共有700個結點，則在該二叉樹中有個葉子結點。2、在深度為5的滿二叉樹中，葉子結點的個數(shù)為（）

A)32B)31C)16D)15算法與數(shù)據(jù)結構√350C71基本數(shù)據(jù)結構與算法E、設完全二叉樹共有n個結點，如從根結點開始，按層序（每一層從左到右）用自然數(shù)1,2,…給結點進行編號，則對于編號為k（1,2,…）的結點有以下結論：①若1，則該結點為根結點，它沒有父結點；若k>1，則該結點的父結點的編號為(2)。②若2k≤n，則結點k的左子結點編號為2k；否則該結點無左子結點（顯然也沒有右子結點）。③若21≤n，則結點k的右子結點編號為21；否則該結點無右子結點。二叉樹的基本性質（該性質注意以特殊推導一般）4231678910111213141551.3.6樹與二叉樹例如結點6，其父結點為3，左子結點為12，左子結點為13(了解)72基本數(shù)據(jù)結構與算法1.3.6樹與二叉樹二叉樹的存儲結構順序存儲結構鏈式存儲結構(了解)73基本數(shù)據(jù)結構與算法二叉樹的遍歷遍歷是指按某條搜索路線尋訪樹中每個結點，且每個結點只被訪問一次。按先左后右的原則，一般使用三種遍歷：先序遍歷(DLR):

訪問根結點，按先序遍歷左子樹，按先序遍歷右子樹。中序遍歷(LDR):

按中序遍歷左子樹，訪問根結點，按中序遍歷右子樹。后序遍歷(LRD):

按后序遍歷左子樹，按后序遍歷右子樹，訪問根結點。二叉樹為空時，執(zhí)行空操作，即空二叉樹已遍歷完。1.3.6樹與二叉樹(重點)74基本數(shù)據(jù)結構與算法遍歷算法先序遍歷：DLR中序遍歷：LDR后序遍歷：LRDADBCT1T2T3DLRADLRDLR>B>>D>>CDLR以先序遍歷DLR為例演示遍歷過程

1.3.6樹與二叉樹(重點)7576基本數(shù)據(jù)結構與算法1、已知一棵二叉樹前序遍歷和中序遍歷分別為和，則該二叉樹的后序遍歷為（）

A) B)C) D)2、樹是結點的集合，它的根結點數(shù)目是（）

A)有且只有1B)1或多于1C)0或1 D)至少23、在深度為5的滿二叉樹中，葉子結點的個數(shù)為（）

A)32 B)31C)16 D)154、下列敘述中正確的是（）

A)線性表是線性結構 B)棧與隊列是非線性結構

C)線性鏈表是非線性結構 D)二叉樹是線性結構

過關練習BCCA77基本數(shù)據(jù)結構與算法5、具有3個結點的二叉樹有（）

A)2種形態(tài)B)4種形態(tài)C)7種形態(tài)D)5種形態(tài)6、設有下列二叉樹,其前序遍歷的結果為（）

A)B)C)D)7、一棵二叉樹中，共有70個葉子結點與80個度為1的結點，則其總結點為（）。

A)219 B)221C)229D)231過關練習DBA78基本數(shù)據(jù)結構與算法8、設一棵二叉樹中有3個葉子結點，有8個度為1的結點，則該二叉樹中總的結點數(shù)為（）

A)12 B)13C)14D)159、設有下列二叉樹，中序遍歷的結果為（）

A)B)C)D)過關練習BB79基本數(shù)據(jù)結構與算法10、在樹結構中，樹根結點沒有（）11、在深度為7的滿二叉樹中，度為2的結點個數(shù)為（）。12、一棵二叉樹第6層（根結點為第1層）的結點數(shù)最多為（）個。13、深度為K的完全二叉樹，至少有（）個結點，至多有（）個結點，若按至上而下，從左到右的次序編號（從1開始），則編號最小的葉子結點的編號是（）。過關練習前件633221212180基本數(shù)據(jù)結構與算法練習參考答案1～5、6～9、

10、前件

11、6312、3213、21,21,2181基本數(shù)據(jù)結構與算法查找：在一個給定的數(shù)據(jù)結構中，根據(jù)給定的條件找到滿足條件的結點。不同的數(shù)據(jù)結構采用不同的查找方法。查找的效率直接影響數(shù)據(jù)處理的效率。平均查找長度：查找過程中比較的次數(shù)查找的結果查找成功：找到滿足條件的結點查找失?。赫也坏綕M足條件的結點。1.3.7查找和排序82基本數(shù)據(jù)結構與算法順序查找（線性查找）對給定的一關鍵字K，從線性表的一端開始，逐個進行記錄的關鍵字和K的比較，直到找到關鍵字等于K的記錄或到達表的另一端?？梢圆捎脧那跋蚝蟛?，也可采用從后向前查的方法。在平均情況下，大約要與表中一半以上元素進行比較，效率較低。最壞情況下需要比較n次。時間復雜度＝O(n)或n在下面兩種情況下只能采取順序查找：線性表為無序表（元素排列是無序的）；即使是有序線性表，但采用的是鏈式存儲結構。1.3.7查找和排序(重點)83基本數(shù)據(jù)結構與算法折半查找（二分法查找）思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認找不到該記錄為止。前提：必須在具有順序存儲結構的有序表中進行。分三種情況：中間項()/2不進位取整若中間項的值等于x,則說明已查到。若x小于中間項的值，則在線性表的前半部分查找；若x大于中間項的值，則在線性表的后半部分查找。特點：比順序查找方法效率高。最壞的情況下，需要比較2n次。1.3.7查找和排序(重點)84折半查找（二分法查找）算法

假設查找表存放在數(shù)組a的a[1]～a[n]中，且升序，查找關鍵字值為k。折半查找的主要步驟為：（1）置初始查找范圍：1，;（2）求查找范圍中間項：()/2（3）將指定的關鍵字值k與中間項a[]比較。若相等，查找成功，找到的數(shù)據(jù)元素為此時指向的位置；若小于，查找范圍的低端數(shù)據(jù)元素指針不變，高端數(shù)據(jù)元素指針更新為1;

若大于，查找范圍的高端數(shù)據(jù)元素指針不變，低端數(shù)據(jù)元素指針更新為1;（4）重復步驟（2）、（3）直到查找成功或查找范圍空（>），即查找失敗為止。（5）如果查找成功，返回找到元素的存放位置，即當前的中間項位置指針；否則返回查找失敗標志。85查找23的過程如下圖：9元素()/2不進位取整(08,14,23,37,46,55,68,79,91)(08,14,23,37,46,55,68,79,91)lowhighmid(08,14,23,37,46,55,68,79,91)lowhigh=mid-1mid(08,14,23,37,46,55,68,79,91)low=mid+1highmid折半查找（二分法查找）算法(重點)86基本數(shù)據(jù)結構與算法

排序的功能：將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排成一個按關鍵字有序的序列。排序過程的組成步驟

1、首先比較兩個關鍵字的大??；

2、然后將記錄從一個位置移動到另一個位置。1.3.7查找和排序堆排序起泡排序排序方法插入排序選擇排序交換排序歸并排序直接、折半插入排序希爾排序簡單選擇排序快速排序(重點)87基本數(shù)據(jù)結構與算法

交換排序的特點在于交換，有冒泡和快速排序兩種。冒泡排序（起泡排序）思想：小的浮起，大的沉底。從左端開始比較。第一趟：第1個與第2個比較，大則交換；第2個與第3個比較，大則交換，…關鍵字最大的記錄交換到最后一個位置上；則第一趟需比較交換的元素對有1組第二趟：對前1個記錄進行同樣的操作，關鍵字次大的記錄交換到第1個位置上；依次類推，則完成排序。1.3.7交換排序(重點)88基本數(shù)據(jù)結構與算法各種排序法比較(重點)89基本數(shù)據(jù)結構與算法1、假設線性表的長度為n，則在最壞情況下，冒泡排序需要的比較次數(shù)為（）

A)2n B)n2C)O(n1..5) D)n(1)/22、最簡單的交換排序方法是（）

A)快速排序B)選擇排序C)堆排序D)冒泡排序3、對長度為n的線性表進行順序查找，在最壞的情況下所需要的比較次數(shù)為（）Ａ)1B)nC)(1)/2D)2

過關練習DDB90基本數(shù)據(jù)結構與算法4、下列數(shù)據(jù)結構中，能用二分法進行查找的是（）

A)順序存儲的有序線性表B)線性鏈表

C)二叉鏈表 D)有序線性鏈表5、在對n個元素進行冒泡排序的過程中，第一趟至多需要進行（）對相鄰元素之間的比較。

A)2 B)1C)n D)1過關練習AB91基本數(shù)據(jù)結構與算法6、排序是計算機程序設計中的一種重要操作，常見的排序方法有插入排序、（）和選擇排序等。7、在長度為n的有序線性表中進行二分查找。最壞的情況下，需要的比較次數(shù)為（）。8、二分查找法的存儲結構僅限于（），且是有序的。9、在插入排序和選擇排序中，若原始記錄基本正序，則選擇（），若原始記錄基本反序，則選擇（）。過關練習交換排序2n順序存儲結構插入排序選擇排序92基本數(shù)據(jù)結構與算法練習參考答案1～5、

6、交換排序

7、2n8、順序存儲結構

9、插入排序、選擇排序93基本數(shù)據(jù)結構與算法1.3.8圖圖的基本概念圖：節(jié)點(圖中稱頂點)間的連接是任意的。圖的分類：有向圖、無向圖n個頂點的連通圖中邊的條數(shù)至少為n條．(重點)94基本數(shù)據(jù)結構與算法算法的四個基本特征（可行性、確定性、有窮性、有足夠情報）算法的復雜度（時間復雜度、空間復雜度），衡量的標準是什么？數(shù)據(jù)結構研究的三個方面（數(shù)據(jù)邏輯結構、存儲結構、基本運算）數(shù)據(jù)結構邏輯分類（線性、非線性）、存儲結構分類（順序存儲、鏈式存儲）線性結構：棧、隊列、循環(huán)隊列的基本結構，操作方式，特點鏈式存儲：單鏈、雙向鏈、循環(huán)鏈表的結構，基本操作二叉樹：定義，滿二叉樹與完全二叉樹的定義與對比二叉樹的三種遍歷算法：先序、中序、后序查找技術：二分查找法的基本運算過程，時間復雜度多少？排序技術：交換、插入排序的基本算法，時間復雜度多少？本章重難點分析95基本數(shù)據(jù)結構與算法謝謝大家96軟件設計及軟件工程基礎本部分主要內(nèi)容程序設計方法和風格結構化程序設計面向對象程序設計軟件工程基本概念結構化分析方法軟件測試程序的調試過關練習97軟件設計及軟件工程基礎什么是程序指令的集合。（解釋指令）通過硬件控制系統(tǒng)自動完成某一功能。通過一系列代碼實現(xiàn)。程序設計的風格總體而言，應該強調簡單和清晰，程序必須是可以理解的。著名的“清晰第一，效率第二”的論點成為當今主導的程序設計風格2.1程序設計方法和風格98軟件設計及軟件工程基礎程序設計風格編寫程序時所表現(xiàn)出來的特點、習慣和邏輯思路。一般從以下四部分加以規(guī)范：源程序文檔化：選擇有含義的符號名字、注釋（序言性和功能性注釋）、程序的視覺組織。數(shù)據(jù)說明：顯式地說明一切變量、數(shù)據(jù)說明的次序應該規(guī)范化、便于查找變量（按順序排列）、對復雜數(shù)據(jù)結構應注釋說明語句的結構：每條語句簡單明了、盡量不用或少用語句、盡量只采用3種基本控制結構編程輸入和輸出：對所有輸入數(shù)據(jù)進行校驗和合理性檢查、輸入輸出格式保持一致、設計良好的輸出報表2.1程序設計方法和風格位于源程序模塊內(nèi)部一般位于模塊的首部，用于說明模塊的相關信息99軟件設計及軟件工程基礎基本思想結構化程序設計的主要思想是功能分解并逐步求精。當一些任務十分復雜不易描述時，可以將它拆分為一系列較小的功能部件，直到這些子任務小到易于理解和實現(xiàn)的程度。結構化程序的特點：程序結構僅由順序、選擇和循環(huán)3種結構復合而成。設計原則自頂向下逐步求精模塊化限制使用語句2.2結構化程序設計100軟件設計及軟件工程基礎基本結構：順序、選擇、循環(huán)

2.2結構化程序設計101軟件設計及軟件工程基礎2.3面向對象程序設計基本思想客觀世界中任何一個事物都可以被看成是一個對象，面向對象方法的本質就是主張從客觀世界固有的事物出發(fā)來構造系統(tǒng)，系統(tǒng)中的對象及對象之間的關系能夠如實地反映問題域中固有的事物及其關系。面向對象的程序設計（，是一種把面向對象的思想應用于軟件開發(fā)過程中，指導開發(fā)活動的系統(tǒng)方法，簡稱方法，它是建立在對象概念（對象、類和繼承）基礎上的方法。102軟件設計及軟件工程基礎主要優(yōu)點與人類習慣的思維方法一致穩(wěn)定性好可重用性好易于開發(fā)大型軟件產(chǎn)品可維護性好2.3面向對象程序設計面向對象程序設計主要考慮的是提高軟件的可重用性！103軟件設計及軟件工程基礎2.3面向對象程序設計幾個術語：對象：在現(xiàn)實世界中，每個實體都是對象，例如，大學生、汽車、電視機、空調等都是現(xiàn)實世界中的對象屬性：通常是一些數(shù)據(jù)，有時它也可以是另一個對象事件：是由對象識別的一個動作，用戶可以編寫相應代碼對此動作進行響應方法：對象中的屬性只能通過該對象所提供的操作來存取或修改104軟件設計及軟件工程基礎2.3面向對象程序設計類：類是一組具有相同屬性和相同操作的對象的集合。基類：用來生成新類的類。派生類：由已存在的類派生出來的新類，也叫子類。繼承是指能夠直接獲得已有的性質和特征，而不必重復定義他們。繼承分單繼承和多重繼承。單繼承指一個類只允許有一個父類，多重繼承指一個類允許有多個父類多態(tài)性是指同樣的消息被不同的對象接受時可導致完全不同的行動的現(xiàn)象。105軟件設計及軟件工程基礎封裝()將數(shù)據(jù)和操作數(shù)據(jù)的函數(shù)銜接在一起，構成一個具有類類型的對象的描述。對象的內(nèi)部實現(xiàn)受保護，外界不能訪問封裝簡化了程序員對對象的使用2.3面向對象程序設計（應該注意的概念）類()一個類定義了一組大體上相似的對象。一個類所包含的方法和數(shù)據(jù)描述一組對象的共同行為和屬性。類是在對象之上的抽象，對象是類的具體化，是類的實例106軟件設計及軟件工程基礎消息()對象之間進行通信的一種數(shù)據(jù)構造。消息是一個實例與另一個實例之間傳遞的信息2.3面向對象程序設計（應該注意的概念）對象()對象是基本的運行時的實體，它既包括數(shù)據(jù)（屬性），也包括作用于數(shù)據(jù)的操作（行為）。一個對象把屬性和行為封裝為一個整體一個對象通?？捎蓪ο竺?、屬性和操作3部分組成107繼承()繼承是父類和子類之間共享數(shù)據(jù)的方法的機制一個子類可以繼承它的父類（或祖先類）中的屬性和操作子類中可以定義自己的屬性和操作單重繼承、多重繼承；且繼承具有傳遞性

水上交通工具陸上交通工具水陸兩用交通工具

多重繼承圖2.3面向對象程序設計（應該注意的概念）108

結構化程序設計的3種結構是（D）

A)順序結構、選擇結構、轉移結構

B)分支結構、等價結構、循環(huán)結構

C)多分支結構、賦值結構、等價結構

D)順序結構、選擇結構、循環(huán)結構在設計程序時，應采納的原則之一是（D）

A)不限制語句的使用B)減少或取消注解行

C)程序越短越好 D)程序結構應有助于讀者理解√√過關練習—選擇題109

結構化程序設計主要強調的是（D）

A)程序的規(guī)模 B)程序的效率

C)程序設計語言的先進性 D)程序易讀性以下不屬于對象的基本特點的是（C）

A)分類性B)多態(tài)性C)繼承性 D)封裝性√√過關練習—選擇題110

對建立良好的程序設計風格，下面描述正確的是（A）

A)程序應簡單、清晰、可讀性好

B)符號名的命名只要符合語法

C)充分考慮程序的執(zhí)行效率

D)程序的注釋可有可無在結構化程序設計思想提出之前，在程序設計中曾強調程序的效率，現(xiàn)在，與程序的效率相比，人們更重視程序的（C）

A)安全性 B)一致性

C)可理解性 D)合理性√√過關練習—選擇題111

下列敘述中，不屬于結構化程序設計方法的主要原則的是（B）

A)自頂向下B)由底向上

C)模塊化 D)限制使用語句對象實現(xiàn)了數(shù)據(jù)和操作的結合，是指對數(shù)據(jù)和數(shù)據(jù)的操作進行（C）

A)結合B)隱藏C)封裝D)抽象在面向對象方法中，一個對象請求另一個對象為其服務的方式是通過發(fā)送（D）A）調用語句B）命令C）口令D）消息√√√過關練習—選擇題112

信息屏蔽的概念與下述哪一種概念直接相關（B）A）軟件結構定義B）模塊獨立性C）模塊類型劃分D）模塊偶合度下列對對象概念描述錯誤的是（A）A）任何對象都必須有繼承性B）對象是屬性和方法的封裝體C）對象間的通訊靠消息傳遞D）操作是對象的動態(tài)屬性√√過關練習—選擇題113面向對象的設計方法與傳統(tǒng)的面向過程的方法有本質的不同,它的基本原理是（C）

A)模擬現(xiàn)實世界中不同事物之間的聯(lián)系

B)強調模擬現(xiàn)實世界中的算法而不強調概念

C)使用現(xiàn)實世界的概念抽象地思考問題從而自然地解決問題

D)鼓勵開發(fā)者在軟件開發(fā)的絕大部分中都用實際領域的概念去思考在面向對象的程序設計中，類描述的是具有相似性質的一組【1】?！敬鸢浮繉ο笤诿嫦驅ο蠓椒ㄖ?，類之間共享屬性和操作的機制稱為【2】?！敬鸢浮坷^承一個類可以從直接或間接的祖先中繼承所有屬性和方法。采用這個方法提高了軟件的【3】。【答案】可重用性√114面向對象的模型中，最基本的概念是對象和【4】。

【答案】：類在面向對象的設計中，用來請求對象執(zhí)行某一處理或回答某些信息的要求稱為【5】?！敬鸢浮浚合⒃诔绦蛟O計階段應該采取【6】和逐步求精的方法，把一個模塊的功能逐步分解，細化為一系列具體的步驟，進而用某種程序設計語言寫成程序。

【答案】：自頂向下過關練習—選擇題115【7】是一種信息隱蔽技術，目的在于將對象的使用者和對象的設計者分開?！敬鸢浮浚悍庋b子程序通常分為兩類：【9】和函數(shù)，前者是命令的抽象，后者是為了求值?！敬鸢浮浚哼^程源程序文檔化要求程序應加注釋。注釋一般分為序言性注釋和【10】。【答案】：功能性注釋在面向對象方法種，信息屏蔽是通過對象的【11】性來實現(xiàn)的?！敬鸢浮浚悍庋b類是一個支持集成的抽象數(shù)據(jù)類型，而對象是類的【12】。

【答案】：實例在面向對象方法種，類之間共享屬性和操作的機制稱為【13】。【答案】：繼承116軟件的定義軟件()是計算機系統(tǒng)中與硬件()相互依存的另一部分。軟件包括三個部分：程序()、相關數(shù)據(jù)()、說明文檔()。軟件的特點軟件是一種邏輯實體，不是物理實體，具有抽象性。軟件沒有明顯的制造過程。軟件在使用過程中，沒有磨損、老化問題軟件依賴與硬件和環(huán)境，導致了移植問題軟件是復雜的，而且以后會更復雜軟件的成本相當昂貴軟件工作牽涉到很多社會因素2.4軟件工程基本概念117軟件危機早期的軟件主要指程序，采用個體工作方式，缺少相關文檔，質量低，維護困難，這些問題稱為“軟件危機”，軟件工程概念的出現(xiàn)源自于軟件危機。軟件工程軟件工程是指應用計算機科學、數(shù)學及管理科學等原理，以工程化的原則和方法來解決軟件問題的工程。其目的是提高軟件生產(chǎn)率、提高軟件質量、降低軟件成本。2.4軟件工程基本概念118軟件工程基本目標在給定成本、進度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護性、可重用性、可適應性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。軟件工程三要素方法：完成軟件工程項目的技術手段工具：支持軟件的開發(fā)、管理、文檔生成過程：支持軟件開發(fā)的各個環(huán)節(jié)的控制、管理2.4軟件工程基本概念119軟件生命周期軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的過程稱為軟件生命周期。維護是持續(xù)時間最長，花費代價最大的一個時期，軟件工程學的一個目的就是提高軟件的可維護性，降低維護代價。分為軟件定義、軟件開發(fā)及軟件運行維護3個階段。1）軟件定義階段：包括制定計劃和需求分析。制定計劃：確定總目標；可行性研究；探討解決方案；制定開發(fā)計劃。需求分析：對待開發(fā)軟件提出的需求進行分析并給出詳細的定義。2.4軟件工程基本概念1202）軟件開發(fā)階段：軟件設計：分為概要設計和詳細設計兩個部分。軟件實現(xiàn)：把軟件設計轉換成計算機可以接受的程序代碼。軟件測試：在設計測試用例的基礎上檢驗軟件的各個組成部分。3）軟件運行維護階段（生命周期中花費最多的階段）：軟件投入運行，并在使用中不斷地維護，進行必要的擴充和刪改。2.4軟件工程基本概念121軟件生命周期6個主要活動階段：見教材P63圖3.1可行性研究與計劃制定、需求分析屬于軟件定義階段。軟件設計、軟件實現(xiàn)、軟件測試屬于軟件開發(fā)階段。其中軟件設計分為概要設計和詳細設計兩個部分。運行與維護（包括軟件的使用、維護、退役）屬于軟件運行維護階段。2.4軟件工程基本概念122需求分析用戶對目標軟件系統(tǒng)在功能、行為、性能、設計約束等方面的期望。需求分析的任務是發(fā)現(xiàn)需求、求精、建模和定義需求的過程。需求分析將創(chuàng)建所需的數(shù)據(jù)模型、功能模型和控制模型。需求分析的四步驟需求獲取、需求分析、編寫需求規(guī)格說明書和需求評審需求分析的方法結構化分析方法、面向對象分析方法2.5結構化分析方法123軟件設計及軟件工程基礎結構化分析方法結構化程序設計理論在軟件需求分析階段的運用，其目的是幫助弄清用戶對軟件的需求。常用工具數(shù)據(jù)流圖()、數(shù)據(jù)字典()、判定樹、判定表開發(fā)策略自頂向下，逐層分解2.5結構化分析方法124數(shù)據(jù)流圖()：以圖形的方式描繪數(shù)據(jù)在系統(tǒng)中流動和處理的過程，它反映了系統(tǒng)必須完成的邏輯功能，是結構化分析方法中用于表示系統(tǒng)邏輯模型的一種工具。2.5結構化分析方法加工

存儲文件

源、潭數(shù)據(jù)流

加工（轉換）：輸入數(shù)據(jù)經(jīng)加工變換產(chǎn)生輸出。數(shù)據(jù)流：沿箭頭方向傳送數(shù)據(jù)的通道，旁邊標注數(shù)據(jù)流名。存儲文件（數(shù)據(jù)源）：表示處理過程中存放各種數(shù)據(jù)的文件。源、潭：表示系統(tǒng)和環(huán)境的接口，屬系統(tǒng)之外的實體。125軟件設計及軟件工程基礎畫數(shù)據(jù)流圖的基本步驟（了解）自外向內(nèi)，自頂向下，逐層細化，完善求精2.5結構化分析方法數(shù)據(jù)流圖的示例

126軟件設計及軟件工程基礎數(shù)據(jù)字典()：對所有與系統(tǒng)相關的數(shù)據(jù)元素的一個有組織的列表，其作用是對數(shù)據(jù)流圖中出現(xiàn)的被命名的圖形元素的確切解釋。數(shù)據(jù)字典是結構化分析方法的核心概括地說，的作用是對中出現(xiàn)的被命名的圖形元素的確切解釋。2.5結構化分析方法軟件需求規(guī)格說明書（）：需求分析階段的最后成果，是軟件開發(fā)中的重要文檔之一。通過建立完整的信息描述、詳細的功能和行為描述、性能需求和設計約束的說明、合適的驗收標準，給出對目標軟件的各種需求。127軟件設計及軟件工程基礎需求分析主要解決“做什么”的問題，而軟件設計主要解決“怎么做”的問題。從技術觀點來看，軟件設計包括軟件結構設計、數(shù)據(jù)設計、接口設計、過程設計。結構設計：定義軟件系統(tǒng)各主要部件之間的關系。數(shù)據(jù)設計：將分析時創(chuàng)建的模型轉化為數(shù)據(jù)結構的定義。接口設計：描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信。過程設計：把系統(tǒng)結構部件轉換成軟件的過程性描述2.6結構化設計方法—軟件設計的基礎128軟件設計及軟件工程基礎軟件設計基本原理：抽象、模塊化、信息隱蔽和模塊獨立性。抽象：抽象是一種思維工具，就是把事物本質的共同特性提取出來而不考慮其他細節(jié)。模塊化：解決一個復雜問題時自頂向下逐步把軟件系統(tǒng)劃分成較小的、相對獨立但又不相互關聯(lián)的模塊的過程。信息隱蔽：模塊的實施細節(jié)對于其他模塊來說是隱蔽的。模塊獨立性：軟件系統(tǒng)中每個模塊只涉及軟件要求的具體的子功能，和軟件系統(tǒng)中其他模塊的接口是簡單的。2.6結構化設計方法—軟件設計的基礎1292.6結構化設計方法—總體設計模塊獨立性評價模塊獨立性程度是評價設計好壞的重要度量標準模塊獨立性指標：耦合性和內(nèi)聚性內(nèi)聚性：是一個模塊內(nèi)容各元素之間彼此結合緊密程度的度量內(nèi)聚種類中功能內(nèi)聚最強，偶然內(nèi)聚最弱耦合性：是模塊間相互連接的緊密程度的度量優(yōu)秀的軟件設計原則，或稱模塊劃分原則是要求：高內(nèi)聚，低耦合1302.6結構化設計方法—總體設計

典型的數(shù)據(jù)流類型分為：變換型和事務型變換型：變換型數(shù)據(jù)處理問題的工作過程大致分為三步，即取得數(shù)據(jù)、變換數(shù)據(jù)和輸出數(shù)據(jù)。變換型系統(tǒng)結構圖由輸入、中心變換、輸出三部分組成。事務型：事務型數(shù)據(jù)處理問題的工作機理是接受一項事務，根據(jù)事務處理的特點和性質，選擇分派一個適當?shù)奶幚韱卧缓蠼o出結果。1312.7軟件測試目的、含義通過合理的設計測試用例以最少的人力和時間發(fā)現(xiàn)潛在的各種錯誤和缺陷；為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程。測試基本方法靜態(tài)測試（人工測試）：評審軟件文檔或程序，包括代碼檢查、靜態(tài)結構分析、代碼質量度量。不實際運行軟件，主要通過人工進行。動態(tài)測試（機器測試）：通過運行軟件，來檢驗結果的正確性。主要包括白盒測試方法和黑盒測試方法。提問：測試能否發(fā)現(xiàn)程序中的所有錯誤？答案：不能。1322.7軟件測試—白盒測試白盒測試（結構測試、邏輯驅動測試）將軟件看成透明的白盒，根據(jù)程序的內(nèi)部結構和邏輯結構來設計測試例子，對程序的路徑和過程進行測試，檢查是否滿足設計的要求白盒測試基本原則(選擇題)保證所測模塊中每一獨立路徑至少執(zhí)行一次；保證所測模塊所有判斷的每一分支至少執(zhí)行一次；保證所測模塊每一循環(huán)都在邊界條件和一般條件下至少各執(zhí)行一次；驗證所有內(nèi)部數(shù)據(jù)結構的有效性。1332.7軟件測試—白盒測試測試用例根據(jù)程序內(nèi)部邏輯設計，主要用于軟件的單元測試。用例主要設計方法有邏輯覆蓋：指一系列以程序內(nèi)部的邏輯結構為基礎的測試用例設計技術?；韭窂綔y試：根據(jù)軟件過程性描述中的控制流程確定程序的環(huán)路復雜性度量，用此度量定義基本路徑集合，并由此導出一組測試用例，對每一條獨立執(zhí)行路徑進行測試。134軟件設計及軟件工程基礎2.7軟件測試—白盒測試邏輯覆蓋設計的基本內(nèi)容（利用測試用例）語句覆蓋：使得程序每一個語句至少都能被執(zhí)行一次。路徑覆蓋：使程序中所有的可能的路徑都至少經(jīng)歷一次。判定覆蓋：保證程序中每個判斷的每個取值分支（T或F）至少經(jīng)歷一次。條件覆蓋：保證程序中每個判斷的每個條件的可能取值至少執(zhí)行一次。判斷-條件覆蓋：使判斷中每個條件的所有可能取值至少執(zhí)行一次，同時每個判斷的所有可能取值分支至少執(zhí)行一次。邏輯覆蓋強度依次是：語句覆蓋<路