程序設計基本概念

基本要求1.掌握算法的基本概念。2.掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作。3.掌握基本排序和查找算法。4.掌握逐步求精的結(jié)構(gòu)化程序設計方法。5.掌握軟件工程的基本方法，具有初步應用相關技術進行軟件開發(fā)的能力。6.掌握數(shù)據(jù)庫的基本知識，了解關系數(shù)據(jù)庫的設計?？荚噧?nèi)容基本數(shù)據(jù)結(jié)構(gòu)與算法程序設計基礎軟件工程基礎數(shù)據(jù)庫設計基礎內(nèi)容2006/92007/42007/92008/42008/910`10`8`2`12`8`4`6`12`8`4`6`10`2`8`10`10`2`8`10`一、基本數(shù)據(jù)結(jié)構(gòu)與算法

1.算法的基本概念；算法復雜度的概念和意義（時間復雜度與空間復雜度）。2.數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。3.線性表的定義；線性表的順序存儲結(jié)構(gòu)及其插入與刪除運算。4.棧和隊列的定義；棧和隊列的順序存儲結(jié)構(gòu)及其基本運算。5.線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運算。6.樹的基本概念；二叉樹的定義及其存儲結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。7.順序查找與二分法查找算法；基本排序算法（交換類排序，選擇類排序，插入類排序）。

二、程序設計基礎1.程序設計方法與風格。2.結(jié)構(gòu)化程序設計。3.面向?qū)ο蟮某绦蛟O計方法，對象，方法，屬性及繼承與多態(tài)性。三、軟件工程基礎1.軟件工程基本概念，軟件生命周期概念，軟件工具與軟件開發(fā)環(huán)境。2.結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。3.結(jié)構(gòu)化設計方法，總體設計與詳細設計。4.軟件測試的方法，白盒測試與黑盒測試，測試用例設計，軟件測試的實施，單元測試、集成測試和系統(tǒng)測試。5.程序的調(diào)試，靜態(tài)調(diào)試與動態(tài)調(diào)試。四、數(shù)據(jù)庫設計基礎1.數(shù)據(jù)庫的基本概念：數(shù)據(jù)庫，數(shù)據(jù)庫管理系統(tǒng)，數(shù)據(jù)庫系統(tǒng)。2.數(shù)據(jù)模型，實體聯(lián)系模型及E-R圖，從E-R圖導出關系數(shù)據(jù)模型。3.關系代數(shù)運算，包括集合運算及選擇、投影、連接運算，數(shù)據(jù)庫規(guī)范化理論。4.數(shù)據(jù)庫設計方法和步驟：需求分析、概念設計、邏輯設計和物理設計的相關策略?？荚嚪绞?、公共基礎的考試方式為筆試，與C語言（VisualBASIC、VisualFoxPro、Java、Access、VisualC++）的筆試部分合為一張試卷。公共基礎部分占全卷的30分。2、公共基礎知識有10道選擇題和5道填空題。學習方法理解基本概念多做練習適當記憶一些名詞與所學的VFP\c\Access程序設計知識結(jié)合起來，以增加對知識的理解能力1.基本數(shù)據(jù)結(jié)構(gòu)與算法1.1算法1.1.1算法(algorithm)基本概念

對特定問題求解步驟的一種描述，它是一組嚴謹?shù)囟x運算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。算法一級算法:S1:輸入圓的半徑r;S2:求周長2∏r;S3:求面積∏r2;S4:輸出周長和面積;例題:已知圓的半徑,求周長和面積.程序dowhile.t.

input“輸入圓的半徑：”tor

ifr<0?“輸入不能是負數(shù)，重新輸入！”

loop

elseexit

endifenddo

S=pi()*r*rL=2*pi()*r?S,L算法的基本特征:(1)可行性(2)確定性(3)有窮性(4)輸入和輸出（擁有足夠的情報）1.1.2算法的基本要素

1、對數(shù)據(jù)對象的運算和操作算術運算邏輯運算關系運算數(shù)據(jù)傳輸2、算法的控制結(jié)構(gòu)算法中各操作之間的執(zhí)行順序一個算法一般可以用順序、選擇、循環(huán)三種基本結(jié)構(gòu)組合而成。1.2算法復雜度1.2.1時間復雜度是指執(zhí)行算法所需要的計算工作量。★算法在執(zhí)行過程中所需基本運算的執(zhí)行次數(shù)來度量算法的工作量.★算法所執(zhí)行的基本運算次數(shù)與問題的規(guī)模n有關.1.2.2算法的空間復雜度一般是指執(zhí)行這個算法所需要的內(nèi)存空間

算法的時間復雜度是指A)執(zhí)行算法程序所需要的時間B)算法程序的長度C)算法執(zhí)行過程中所需要的基本運算次數(shù)D)算法程序中的指令條數(shù)算法的基本特征是可行性、確定性、

【1】和擁有足夠的情報。算法的空間復雜度是指

A)算法程序的長度 B)算法程序中的指令條數(shù)

C)算法程序所占的存儲空間D)執(zhí)行過程中所需要的存儲空間在計算機中，算法是指

A)加工方法 B)解題方案的準確而完整的描述

C)排序方法 D)查詢方法例題講解有窮性算法分析的目的是

A)找出數(shù)據(jù)結(jié)構(gòu)的合理性B)找出算法中輸入和輸出之間的關系

C)分析算法的易懂性和可靠性 D)分析算法的效率以求改進算法的工作量大小和實現(xiàn)算法所需的存儲單元多少分別稱為算法的【1】。時間復雜度和空間復雜度1.2數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的圖形表示線性結(jié)構(gòu)與非線性結(jié)構(gòu)1.2.1數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容(1)數(shù)據(jù)集中數(shù)據(jù)之間的邏輯關系線性樹圖(2)數(shù)據(jù)的存儲結(jié)構(gòu)(3)各種數(shù)據(jù)結(jié)構(gòu)的運算1.2.2基本概念和術語

數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學科。1．數(shù)據(jù)的邏輯結(jié)構(gòu)2、數(shù)據(jù)的存儲結(jié)構(gòu)3、數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等。A．線性結(jié)構(gòu)B．非線性結(jié)構(gòu)A順序存儲B鏈式存儲線性表棧隊樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個方面數(shù)據(jù)結(jié)構(gòu)可描述為Group=（D，R）（2）邏輯結(jié)構(gòu)有限個數(shù)據(jù)元素的集合有限個數(shù)據(jù)元素間關系的集合線性樹圖常用數(shù)據(jù)結(jié)構(gòu):A.線性結(jié)構(gòu)

(A,B,C,·······，X,Y,Z)例:學生成績表86胡孝臣986110395劉忠賞9861107100張卓9861109成績姓名學號①線性表②棧——后進先出③隊列——先進先出例:英文字母表①樹形結(jié)構(gòu)例:全校學生檔案管理的組織方式例:計算機文件管理系統(tǒng)也是典型的樹形結(jié)構(gòu)B．非線性結(jié)構(gòu)1423

例:數(shù)據(jù)結(jié)構(gòu)B(D,R)D={1,2,3,4}R={(1,2),(1,3),(1,4),(2,3),(3,4),(2,4)}213例:數(shù)據(jù)結(jié)構(gòu)C(D,R)D={1,2,3}R={<1,2>,<2,3>,<3,2>,<1,3>}

②圖形結(jié)構(gòu)元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲內(nèi)容Loc(ai)=Lo+（i-1)*m1、順序存儲每個元素所占用的存儲單元個數(shù)（3）存儲結(jié)構(gòu)例：線性表(zhao,qian,sun,li,zhou,wu,zheng,wang)

順序存儲結(jié)構(gòu)：存儲地址數(shù)據(jù)7891011121314zhaoqiansunlizhouwuzhengwang7基地址順序存儲結(jié)構(gòu)，將邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里,具有以下特點:1.隨機存取。2.作插入或刪除操作時，需移動大量元數(shù)。3.長度變化較大時，需按最大空間分配。4.表的容量難以擴充。2、鏈式存儲每個節(jié)點都由兩部分組成：

數(shù)據(jù)域和指針域。數(shù)據(jù)域存放元素本身的數(shù)據(jù)，指針域存放指針。數(shù)據(jù)元素之間邏輯上的聯(lián)系由指針來體現(xiàn)。例：線性表(zhao,qian,sun,li,zhou,wu,zheng,wang)鏈式存儲結(jié)構(gòu)：存儲地址數(shù)據(jù)17131925313743liqiansunwangwuzhaozhengzhou指針43131null377192531頭指針通常我們把鏈表畫成用箭頭相鏈接的結(jié)點的序列，結(jié)點之間的箭頭表示鏈域中的指針。zhaoqiansunlizhouwuzhengwang/H存儲地址數(shù)據(jù)17131925313743liqiansunwangwuzhaozhengzhou指針43131null377192531頭指針1.比順序存儲結(jié)構(gòu)多用空間(存儲密度小)(每個節(jié)點都由數(shù)據(jù)域和指針域組成)。2.邏輯上相鄰的節(jié)點物理上不必相鄰。3.插入、刪除靈活

(不必移動節(jié)點，只要改變節(jié)點中的指針)。4.非隨機存取。鏈接存儲結(jié)構(gòu)特點：1．數(shù)據(jù)的邏輯結(jié)構(gòu)2、數(shù)據(jù)的存儲結(jié)構(gòu)3、數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等。A．線性結(jié)構(gòu)B．非線性結(jié)構(gòu)A順序存儲B鏈式存儲線性表棧隊樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個方面(亦稱物理結(jié)構(gòu))……鏈表不具有的特點是A)不必事先估計存儲空間B)可隨機訪問任一元素C)插入刪除不需要移動元素 D)所需空間與線性表長度成正比數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)，線性鏈表屬于【1】。數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關的是數(shù)據(jù)的

A)存儲結(jié)構(gòu) B)物理結(jié)構(gòu)

C)邏輯結(jié)構(gòu) D)物理和存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和【1】兩大類。數(shù)據(jù)的存儲結(jié)構(gòu)是指A）數(shù)據(jù)所占的存儲空間B）數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示C）數(shù)據(jù)在計算機中的順序存儲方式D）存儲在外存中的數(shù)據(jù)例題講解存儲結(jié)構(gòu)非線性結(jié)構(gòu)順序存儲方法是把邏輯上相鄰的結(jié)點存儲在物理位置

【2】的存儲單元中。

數(shù)據(jù)處理的最小單位是

A)數(shù)據(jù) B)數(shù)據(jù)元素C)數(shù)據(jù)項 D)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)作為計算機的一門學科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、對各種數(shù)據(jù)結(jié)構(gòu)進行的運算，以及

A)數(shù)據(jù)的存儲結(jié)構(gòu) B)計算方法C)數(shù)據(jù)映象D)邏輯存儲//線性表的順序存儲結(jié)構(gòu)和線性表的鏈式存儲結(jié)構(gòu)分別是

A)順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu)

B)隨機存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu)

C)隨機存取的存儲結(jié)構(gòu)、隨機存取的存儲結(jié)構(gòu)

D)任意存取的存儲結(jié)構(gòu)、任意存取的存儲結(jié)構(gòu)

相鄰根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關系的復雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分成

A)動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B)緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

C)線性結(jié)構(gòu)和非線性結(jié)構(gòu)D)內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的

【2】以及對數(shù)據(jù)的操作運算。數(shù)據(jù)的基本單位是

【5】。下列敘述中，錯誤的是

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

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

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

D)一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)存儲結(jié)構(gòu)數(shù)據(jù)元素1.3線性表1.3.1線性表的概念線性表的定義：

線性表是n個元素的有限序列，它們之間的關系可以排成一個線性序列：

(a1，a2，……

，ai，……

，an)

其中n稱作表的長度，當n=0時，稱作空表。線性表的特點：1.線性表中所有元素的性質(zhì)相同。2.除第一個和最后一個數(shù)據(jù)元素之外，其它數(shù)據(jù)元素有且僅有一個前驅(qū)和一個后繼.第一個數(shù)據(jù)元素無前驅(qū),最后一個數(shù)據(jù)元素無后繼。3.數(shù)據(jù)元素在表中的位置只取決于它自身的序號?？偨Y(jié):

順序存儲結(jié)構(gòu)表示的線性表，在做插入或刪除操作時，平均需要移動大約一半的數(shù)據(jù)元素。當線性表的數(shù)據(jù)元素量較大，并且經(jīng)常要對其做插入或刪除操作時，這一點需要值得考慮。長度為n的順序存儲線性表中，當在任何位置上插入一個元素概率都相等時，插入一個元素所需移動元素的平均個數(shù)為【1】。線性表若采用順序存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址

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

C)一定是不連續(xù)的D)連續(xù)不連續(xù)都可以//例題講解線性表L=(a1,a2,a3,…ai，…an)，下列說法正確的是

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

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

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

D)除第一個元素和最后一個元素外，其余每個元素都有一個且只有一個直接前件和直接后件

根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關系的復雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分成

A)動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B)緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

C)線性結(jié)構(gòu)和非線性結(jié)構(gòu)D)內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)當線性表采用順序存儲結(jié)構(gòu)實現(xiàn)存儲時，其主要特點是【1】。隨機存取//1.5線性表的鏈式存儲結(jié)構(gòu)及其插入與刪除操作zhaoqiansunlizhouwuzhengwang/H存儲地址數(shù)據(jù)17131925313743liqiansunwangwuzhaozhengzhou指針43131null377192531頭指針單鏈表鏈表不具有的特點是A)不必事先估計存儲空間B)可隨機訪問任一元素C)插入刪除不需要移動元素D)所需空間與線性表長度成正比用鏈表表示線性表的優(yōu)點是A)便于隨機存取B)花費的存儲空間較順序存儲少C)便于插入和刪除操作D)數(shù)據(jù)元素的物理順序與邏輯順序相同長度為n的順序存儲線性表中,當在任何位置上插入一個元素概率都相等時,插入一個元素所需移動元素的平均個數(shù)為【1】。在單鏈表中，增加頭結(jié)點的目的是

A)方便運算的實現(xiàn)B)使單鏈表至少有一個結(jié)點

C)標識表結(jié)點中首結(jié)點的位置

D)說明單鏈表是線性表的鏈式存儲實現(xiàn)例題講解非空的循環(huán)單鏈表head的尾結(jié)點(由p所指向)，滿足

A)p->next==NULL B)p==NULLC)p->next=head D)p=head循環(huán)鏈表的主要優(yōu)點是

A)不再需要頭指針了

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

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

D)已知某個結(jié)點的位置后，能夠容易的找到它的直接前件1.7棧和隊列1.7.1棧和隊列的定義棧和隊列是兩種特殊的線性表，它們是運算時要受到某些限制的線性表，故也稱為限定性的數(shù)據(jù)結(jié)構(gòu)。1.棧?！窍薅▋H在表尾進行插入或刪除操作的線性表。棧頂——表尾。棧底——表頭?？諚！缓氐目毡怼！璦1a2an棧底棧頂進棧出棧棧s=(a1,a2,…,an)后進先出（LIFO）2.棧的順序存儲結(jié)構(gòu)及其基本運算a2a1a1a2top

用順序存儲結(jié)構(gòu)表示的棧:

順序棧用一組連續(xù)的存儲單元存放自棧底到棧頂?shù)臄?shù)據(jù)元素，一般用一維數(shù)組表示，設置一個簡單變量top指示棧頂位置，稱為棧頂指針，它始終指向待插入元素的位置?；具\算：壓（進）棧：PUSH出棧：POP讀棧頂元素：gettop例子：topbaseEDCBAtopbaseCBAbasetopAbasetop空桟：top＝base非空桟：top始終在桟頂元素的后一個位置桟的元素個數(shù)：top-base上溢下溢3.隊列定義：一種特殊的線性結(jié)構(gòu)，限定只能在表的一端進行插入，在表的另一端進行刪除的線性表。此種結(jié)構(gòu)稱為先進先出（FIFO）表。

a1,

a2,

a3,

a4,…………

an-1,

an

隊列示意圖隊頭隊尾棧和隊列的共同特點是

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

C)只允許在端點處插入和刪除元素D)沒有共同點如果進棧序列為e1,e2,e3,e4，則可能的出棧序列是

A)e3,e1,e4,e2 B)e2,e4,e3,e1C)e3,e4,e1,e2 D)任意順序一些重要的程序語言(如C語言和Pascal語言)允許過程的遞歸調(diào)用。而實現(xiàn)遞歸調(diào)用中的存儲分配通常用

A)棧 B)堆C)數(shù)組 D)鏈表例題講解棧底至棧頂依次存放元素A、B、C、D，在第五個元素E入棧前，棧中元素可以出棧，則出棧序列可能是

A)ABCED B)DCBEAC)DBCEA D)CDABE棧通常采用的兩種存儲結(jié)構(gòu)是

A)線性存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu) B)散列方式和索引方式

C)鏈表存儲結(jié)構(gòu)和數(shù)組D)線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)棧和隊列通常采用的存儲結(jié)構(gòu)是【1】。下列數(shù)據(jù)結(jié)構(gòu)中，按先進后出原則組織數(shù)據(jù)的是

A)線性鏈表B)棧C)循環(huán)鏈表 D)順序表▽當循環(huán)隊列非空且隊尾指針等于隊頭指針時，說明循環(huán)隊列已滿，不能進行入隊運算。這種情況稱為

【2】。鏈表存儲結(jié)構(gòu)和數(shù)組上溢由兩個棧共享一個存儲空間的好處是A)減少存取時間，降低下溢發(fā)生的機率B)節(jié)省存儲空間，降低上溢發(fā)生的機率C)減少存取時間，降低上溢發(fā)生的機率D)節(jié)省存儲空間，降低下溢發(fā)生的機率下列關于棧的敘述中正確的是Ａ）在棧中只能插入數(shù)據(jù)B）在棧中只能刪除數(shù)據(jù)C）棧是先進先出的線性表D）棧是后進先出的線性表下列關于隊列的敘述中正確的是Ａ）在隊列中只能插入數(shù)據(jù)B）在隊列中只能刪除數(shù)據(jù)C）隊列是先進先出的線性表D）隊列是后進先出的線性表1.6.1樹的定義由一個或多個結(jié)點組成的有限集合。僅有一個根結(jié)點，結(jié)點間有明顯的層次結(jié)構(gòu)關系。

A

C

GT2D

HIT3J

M

BEL

KT1F現(xiàn)實世界中，能用樹的結(jié)構(gòu)表示的例子：學校的行政關系、書的層次結(jié)構(gòu)、人類的家族血緣關系等。1.6樹介紹幾個概念：結(jié)點（Node）：樹中的元素，包含數(shù)據(jù)項及若干指向其子樹的分支。結(jié)點的度（Degree）：結(jié)點擁有的子樹數(shù)。結(jié)點的層次：從根結(jié)點開始算起，根為第一層。葉子（Leaf）：度為零的結(jié)點，也稱端結(jié)點。孩子（Child）：結(jié)點子樹的根稱為該結(jié)點的孩子結(jié)點。兄弟（Sibling）：同一雙親的孩子。雙親（Parent）：孩子結(jié)點的上層結(jié)點，稱為這些結(jié)點的雙親。樹的深度（Depth)：樹中結(jié)點的最大層次數(shù)。樹的度：結(jié)點所具有的最大的度.森林（Forest）：M棵互不相交的樹的集合。

A

C

GD

HI

J

M

BEL

KT1F1.6.2二叉樹（BinaryTree）1、二叉樹的定義及其性質(zhì)

(1)二叉樹的定義二叉樹的五種基本形態(tài)

二叉樹一種特殊的樹形結(jié)構(gòu)，特點是樹中每個結(jié)點最多只能有兩棵子樹(即二叉樹中不存在度大于2的結(jié)點)，且子樹有左右之分，次序不能顛倒。

空二叉樹

僅有根結(jié)點

右子樹為空

左子樹為空左右子樹均非空二叉樹是n(n

0)個結(jié)點的有限集合。它或為空數(shù)(n=0),或由一個根結(jié)點和兩棵分別稱為根的左子樹和右子樹的互不相交的二叉樹組成。特別要注意：二叉樹不是一般樹的特殊情況,而是另一種樹形結(jié)構(gòu).aabb兩棵不同的二叉樹ab一棵樹性質(zhì)1:二叉樹的第i層上至多有2i-1（i

1）個結(jié)點。(2)二叉樹的基本性質(zhì)423167891011121314155第三層上(i=3)，有23-1=4個節(jié)點。第四層上(i=4)，有24-1=8個節(jié)點。性質(zhì)2:深度為k的二叉樹中至多含有2k-1個結(jié)點。性質(zhì)３：對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0,度為2的結(jié)點數(shù)為n2,則n0=n2+1。性質(zhì)４：具有n個結(jié)點的完全二叉樹的深度為★滿二叉樹423167891011121314155特點：每一層上都含有最大結(jié)點數(shù)?！锿耆鏄?23167891011125特點：(1)除最后一層外，每一層都取最大結(jié)點數(shù)，(2)最后一層結(jié)點都集中在該層最左邊的若干位置?！飿渑c二叉樹的區(qū)別A．樹和二叉樹的結(jié)點個數(shù)最少都可為0。B．樹中結(jié)點的最大度數(shù)沒有限制，二叉樹結(jié)點最大度數(shù)為2。C．樹的結(jié)點無左、右之分，二叉樹的結(jié)點子樹有明確的左、右之分。3個結(jié)點的樹3個結(jié)點的二叉樹1.6.3二叉樹的遍歷查找某個結(jié)點，或?qū)Χ鏄渲腥拷Y(jié)點進行某種處理，就需要遍歷。（1）遍歷定義及遍歷算法遍歷是指按某條搜索路線尋訪樹中每個結(jié)點，且每個結(jié)點只被訪問一次。按先左后右的原則，一般使用三種遍歷：先序遍歷(DLR):

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

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

按后序遍歷左子樹，按后序遍歷右子樹，訪問根結(jié)點。二叉樹為空時，執(zhí)行空操作，即空二叉樹已遍歷完。

（2）遍歷算法先序遍歷：DLR中序遍歷：LDR后序遍歷：LRDADBCDLRADLRDLR>B>>D>>CDLR以先序遍歷DLR為例演示遍歷過程ABDCBDACDBCAe-+a*b-cd/fLDRLDRa+LDRb*LDRc-d-LDRe/f中序遍歷示圖設有下列二叉樹：

對此二叉樹前序遍歷的結(jié)果為A)ZBTTCPXAB)ATBZXCTPC)ZBTACTXPD)ATBZXCPT設有下列二叉樹：對此二叉樹的中序遍歷的結(jié)果為A)ABCDEFB)DBEAFCC)ABDECFD)DEBFCA已知二叉樹后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是

A)acbedB)decabC)deabc D)cedba

已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹的后序遍歷為

A)GEDHFBCA B)DGEBHFCAC)ABCDEFGH D)ACBFEDHG樹是結(jié)點的集合，它的根結(jié)點數(shù)目是

A)有且只有1 B)1或多于1C)0或1 D)至少2下列敘述中正確的是

A)線性表是線性結(jié)構(gòu) B)棧與隊列是非線性結(jié)構(gòu)

C)線性鏈表是非線性結(jié)構(gòu) D)二叉樹是線性結(jié)構(gòu)例題講解在深度為5的滿二叉樹中，葉子結(jié)點的個數(shù)為

A)32 B)31C)16 D)15若某二叉樹的前序遍歷訪問順序是abdgcefh，中序遍歷訪問順序是dgbaechf，則其后序遍歷的結(jié)點訪問順序是

A)bdgcefhaB)gdbecfhaC)bdgaechfD)gdbehfca在樹結(jié)構(gòu)中，樹根結(jié)點沒有【1】。具有3個結(jié)點的二叉樹有

A)2種形態(tài)B)4種形態(tài)C)7種形態(tài)D)5種形態(tài)

雙親結(jié)點1.7查找和排序順序查找與二分查找算法基本排序算法（交換類排序、選擇類排序、插入類排序）1.7.1查找查找是在一個給定的數(shù)據(jù)結(jié)構(gòu)中，根據(jù)給定的條件查找滿足條件的結(jié)點。不同的數(shù)據(jù)結(jié)構(gòu)采用不同的查找方法。查找的效率直接影響數(shù)據(jù)處理的效率。查找的結(jié)果：查找成功：找到滿足條件的結(jié)點查找失?。赫也坏綕M足條件的結(jié)點。1.7.1.1順序查找（線性查找）◆查找過程：

對給定的一關鍵字K，從線性表的一端開始，逐個進行記錄的關鍵字和K的比較，直到找到關鍵字等于K的記錄或到達表的另一端?！艨梢圆捎脧那跋蚝蟛?，也可采用從后向前查的方法。◆在平均情況下，大約要與表中一半以上元素進行比較，效率較低。平均查找長度較大。最好情況：1最壞情況：n1.7.1.2折半查找（二分法查找）思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認找不到該記錄為止。前提：必須在具有順序存儲結(jié)構(gòu)的有序表中進行。分三種情況：

1）若中間項的值等于x,則說明已查到。

2）若x小于中間項的值,則在線性表的前半部分查找；

3）若x大于中間項的值，則在線性表的后半部分查找。特點：比順序查找方法效率高。最壞的情況下，需要比較log2n次。1.7.2排序1.7.2.1概述

1、排序的功能：

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

2、排序過程的組成步驟：首先比較兩個關鍵字的大??；然后將記錄從一個位置移動到另一個位置。排序方法插入排序選擇排序交換排序歸并排序簡單插入排序希爾排序簡單選擇排序堆排序起泡排序快速排序考點速記冒泡排序法，最壞情況需要比較n(n-1)/2次。快速排序法，

n(n-1)/2簡單插入排序法：n(n-1)/2希爾排序法：n1.5簡單選擇排序法：n(n-1)/2堆排序法：nlog2n1.7.2.2插入排序

簡單插入、希爾排序1、簡單插入排序:

基本思想：從數(shù)組的第2號元素開始，順序從數(shù)組中取出元素，并將該元素插入到其左端已排好序的數(shù)組的適當位置上。該算法適合于n較小的情況，時間復雜度為O(n2).待排元素序列：[53]2736156942第一次排序：[2753]36156942第二次排序：[273653]156942第三次排序：[15273653]6942第四次排序：[1527365369]42第五次排序：[152736425369]

直接插入排序示例對于有n個數(shù)據(jù)元素的待排序列，插入操作要進行n-1趟最壞情況下：需要n(n-1)/2次比較最好：

n-1次比較1、簡單選擇排序思想：首先從1~n個元素中選出關鍵字最小的記錄交換到第一個位置上。然后再從第2個到第n個元素中選出次小的記錄交換到第二個位置上，依次類推。1.7.2.3選擇排序

簡單選擇排序、堆排序1.7.2.4交換排序交換排序的特點在于交換。有冒泡和快速排序兩種。1、冒泡排序（起泡排序）思想：小的浮起，大的沉底。從左端開始比較。第一趟：第1個與第2個比較，大則交換；第2個與第3個比較，大則交換，……關鍵字最大的記錄交換到最后一個位置上；第二趟：對前n-1個記錄進行同樣的操作，關鍵字次大的記錄交換到第n-1個位置上；依次類推，則完成排序。第六趟排序后第五趟排序后第四趟排序后第三趟排序后第二趟排序后第一趟排序后初始關鍵字思想：小的浮起，大的沉底。4936416511783665364156364165413641561178363641491156492525251149495611111125252525排序n個記錄最多需要n-1趟冒泡排序正序：比較次數(shù)為O(n-1)

逆序：比較次數(shù)為O(n(n-1)/2)

適合于數(shù)據(jù)較少的情況。

方法歸并排序簡單插入希爾排序簡單選擇堆排序起泡排序快速排序插入選擇交換比較次數(shù)使用建議查找:方法順序折半比較次數(shù)log2n最好:1最壞:n平均:(n+1)/2使用條件順序存儲結(jié)構(gòu)的有序表任何表排序:n-1n(n-1)/2n1.5n(n-1)/2nlog2nn-1n(n-1)/2log2nn(n-1)/2正序的表、n小的表與表的初始數(shù)據(jù)無關、n小的表正序的表、n小的表n大的表,但逆序的表會蛻變?yōu)槠鹋菖判蚪柚o助空間最多的方法n大的表在長度為n的有序線性表中進行二分查找。最壞的情況下，需要的比較次數(shù)為

【2】。長度為n的順序存儲線性表中，當在任何位置上插入一個元素概率都相等時，插入一個元素所需移動元素的平均個數(shù)為【1】。假設線性表的長度為n，則在最壞情況下，冒泡排序需要的比較次數(shù)為

A)log2n B)n2C)O(n1..5) D)n(n-1)/2已知數(shù)據(jù)表A中每個元素距其最終位置不遠，為節(jié)省時間，應采用的算法是

A)堆排序B)直接插入排序C)快速排序D)直接選擇排序例題講解log2nn/2

冒泡排序算法在最好的情況下的元素交換次數(shù)為【1】。在最壞情況下，堆排序需要比較的次數(shù)為

【2】。最簡單的交換排序方法是

A)快速排序 B)選擇排序C)堆排序 D)冒泡排序排序是計算機程序設計中的一種重要操作，常見的排序方法有插入排序、【1】和選擇排序等。0nlog2n交換排序在下列幾種排序方法中，要求內(nèi)存量最大的是

A)插入排序B)選擇排序C)快速排序 D)歸并排序在待排序的元素序列基本有序的前提下，效率最高的排序方法是

A)冒泡排序B)選擇排序C)快速排序D)歸并排序

希爾排序?qū)儆?/p>

A)交換排序B)歸并排序C)選擇排序 D)插入排序?qū)﹂L度為n的線性表進行順序查找，在最壞的情況下所需要的比較次數(shù)為Ａ)n+1B)nC)(n+1)/2D)n/22.程序設計基礎2.1程序設計方法與風格2.1.1程序設計方法結(jié)構(gòu)化設計方法面向?qū)ο蟪绦蛟O計方法2.2結(jié)構(gòu)化程序設計2.2.1基本概念★基本思想

對大型的程序設計，使用一些基本的結(jié)構(gòu)來設計程序，無論多復雜的程序，都可以使用這些基本結(jié)構(gòu)按一定的順序組合起來。這些基本結(jié)構(gòu)的特點都是只有一個入口、一個出口。由這些基本結(jié)構(gòu)組成的程序就避免了任意轉(zhuǎn)移、閱讀起來需要來回尋找的問題。三種基本結(jié)構(gòu)順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)2.2.2設計原則自頂向下（先總體，后細節(jié)）逐步求精（設計子目標過渡）模塊化（分解總目標）限制使用goto語句★結(jié)構(gòu)化程序設計方法特點要求把程序的結(jié)構(gòu)規(guī)定為順序、選擇和循環(huán)三種基本機構(gòu)，并提出了自頂向下、逐步求精、模塊化程序設計等原則。結(jié)構(gòu)化程序設計是把模塊分割方法作為對大型系統(tǒng)進行分析的手段，使其最終轉(zhuǎn)化為三種基本結(jié)構(gòu)，其目的是為了解決由許多人共同開發(fā)大型軟件時，如何高效率地完成可靠系統(tǒng)的問題。缺點：程序和數(shù)據(jù)結(jié)構(gòu)松散地耦合在一起。解決此問題的方法就是采用面向?qū)ο蟮某绦蛟O計方法(OOP)。2.3面向?qū)ο蟮某绦蛟O計方法2.3.1關于面向?qū)ο蠓椒▽ο到y(tǒng)的復雜性進行概括、抽象和分類，使軟件的設計與現(xiàn)實形成一個由抽象到具體、由簡單到復雜這樣一個循序漸進的過程，從而解決大型軟件研制中存在的效率低、質(zhì)量難以保證、調(diào)試復雜、維護困難等問題。主要優(yōu)點與人類習慣的思維方法一致穩(wěn)定性好可重用性好可維護性好易于開發(fā)大型軟件產(chǎn)品2.3.2基本概念對象(Object)對象是基本的運行時認得實體，它既包括數(shù)據(jù)（屬性），也包括作用于數(shù)據(jù)的操作（行為）。一個對象把屬性和行為封裝為一個整體一個對象通?？捎蓪ο竺?、屬性和操作3部分組成對象的基本特性：（1）標識唯一性（對象可區(qū)分）（2）分類性（對象抽象成類）（3）多態(tài)性（同一操作可以是不同對象的行為）（4）封裝性（只能看到對象的外部特性）（5）模塊獨立性好（對象內(nèi)部各元素結(jié)合緊密、內(nèi)聚性強）類(Class)和實例一個類所包含的方法和數(shù)據(jù)描述一組對象的共同行為和屬性。類是在對象之上的抽象，對象是類的具體化，是類的實例封裝(Encapsulation)將數(shù)據(jù)和操作數(shù)據(jù)的函數(shù)銜接在一起，構(gòu)成一個具有類類型的對象的描述。對象的內(nèi)部實現(xiàn)受保護，外界不能訪問封裝簡化了程序員對對象的使用繼承(Inheritance)繼承是父類和子類之間共享數(shù)據(jù)的方法的機制一個子類可以繼承它的父類（或祖先類）中的屬性和操作子類中可以定義自己的屬性和操作多態(tài)性(Polymorphism)不同的對象收到同一消息可以產(chǎn)生完全不同的結(jié)構(gòu)，這一現(xiàn)象叫做多態(tài)性多態(tài)的實現(xiàn)受到繼承的支持消息(Message)

對象之間進行通信的一種構(gòu)造結(jié)構(gòu)化程序設計的3種結(jié)構(gòu)是

A)順序結(jié)構(gòu)、選擇結(jié)構(gòu)、轉(zhuǎn)移結(jié)構(gòu)B)分支結(jié)構(gòu)、等價結(jié)構(gòu)、循環(huán)結(jié)構(gòu)

C)多分支結(jié)構(gòu)、賦值結(jié)構(gòu)、等價結(jié)構(gòu)D)順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)在設計程序時，應采納的原則之一是

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

C)程序越短越好D)程序結(jié)構(gòu)應有助于讀者理解程序設計語言的基本成分是數(shù)據(jù)成分、運算成分、控制成分和

A)對象成分 B)變量成分

C)語句成分 D)傳輸成分例題講解結(jié)構(gòu)化程序設計主要強調(diào)的是

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

C)程序設計語言的先進性 D)程序易讀性對建立良好的程序設計風格，下面描述正確的是

A)程序應簡單、清晰、可讀性好 B)符號名的命名只要符合語法

C)充分考慮程序的執(zhí)行效率 D)程序的注釋可有可無在結(jié)構(gòu)化程序設計思想提出之前，在程序設計中曾強調(diào)程序的效率，現(xiàn)在，與程序的效率相比，人們更重視程序的

A)安全性 B)一致性C)可理解性 D)合理性程序的3種基本控制結(jié)構(gòu)是

A)過程、子過程和分程序 B)順序、選擇和重復

C)遞歸、堆棧和隊列 D)調(diào)用、返回和轉(zhuǎn)移下列敘述中，不屬于結(jié)構(gòu)化程序設計方法的主要原則的是

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

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

A)結(jié)合 B)隱藏C)封裝 D)抽象☆類是一個支持集成的抽象數(shù)據(jù)類型，而對象是類的_______。實例在面向?qū)ο蠓椒ㄖ?，一個對象請求另一個對象為其服務的方式是通過發(fā)送A）調(diào)用語句B）命令C）口令D）消息信息屏蔽的概念與下述哪一種概念直接相關A）軟件結(jié)構(gòu)定義B）模塊獨立性C）模塊類型劃分D）模塊偶合度下列對象概念描述錯誤的是A）任何對象都必須有繼承性B）對象是屬性和方法的封裝體C）對象間的通訊靠消息傳遞D）操作是對象的動態(tài)屬性下列敘述中，不屬于結(jié)構(gòu)化分析方法的是

A)面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法

B)面向數(shù)據(jù)結(jié)構(gòu)的Jackson方法

C)面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開發(fā)方法

D)面向?qū)ο蟮姆治龇椒?/p>

在面向?qū)ο蟮某绦蛟O計中，類描述的是具有相似性質(zhì)的一組

【3】

在面向?qū)ο蠓椒ㄖ?，類之間共享屬性和操作的機制稱為

【2】。一個類可以從直接或間接的祖先中繼承所有屬性和方法。采用這個方法提高了軟件的

【3】。對象的共同行為和屬性繼承可重用性3.軟件工程基礎3.1基本概念軟件程序數(shù)據(jù)相關文檔機器可執(zhí)行的程序和數(shù)據(jù)機器不能執(zhí)行的，與軟件開發(fā)、運行、維護、使用等有關的文檔1.軟件危機早期的軟件主要指程序，采用個體工作方式，缺少相關文檔，質(zhì)量低，維護困難，這些問題稱為“軟件危機”，軟件工程概念的出現(xiàn)源自于軟件危機。2.軟件工程軟件工程是應用于計算機軟件的定義、開發(fā)和維護的一整套方法、工具、文檔、實踐標準和工序。

3.軟件工程三要素方法：完成軟件工程項目的技術手段工具：支持軟件的開發(fā)、管理、文檔生成過程：支持軟件開發(fā)的各個環(huán)節(jié)的控制、管理;

將方法和工具綜合起來,以達到合理、及時地進行計算機軟件開發(fā)的目的。5.軟件生命周期將軟件產(chǎn)品從提出、實現(xiàn)、使用、維護到停止使用退役的過程稱為軟件生命周期分為軟件定義、軟件開發(fā)及軟件運行維護3個階段。維護是持續(xù)時間最長，花費代價最大的一個階段6個活動階段可行性研究與計劃制定：確定系統(tǒng)的總體目標。需求分析：確定系統(tǒng)的邏輯模型。參加人員有用戶、項目負責人和系統(tǒng)分析員。軟件設計：包括軟件結(jié)構(gòu)設計、數(shù)據(jù)設計、接口設計和過程設計。

結(jié)構(gòu)設計是定義軟件系統(tǒng)各部件之間的關系；

數(shù)據(jù)設計是將分析時創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義；

接口設計是描述軟件內(nèi)部、軟件和操作系統(tǒng)之間及軟件與人之間如何通信；

過程設計是把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程性描述。軟件實現(xiàn)：編程。高級程序員和程序員產(chǎn)生源程序清單軟件測試：在設計測試用例的基礎上，檢驗軟件的各個組成部分。產(chǎn)生軟件測試計劃和軟件測試報告運行與維護可行性研究與計劃制定需求分析軟件設計實現(xiàn)測試運行和維護確定系統(tǒng)的總體目標需求規(guī)格說明書概要設計說明書詳細設計說明書測試計劃初稿完成程序代碼用戶手冊單元測試計劃檢驗軟件測試分析報告可行性研究與計劃制定需求分析概要設計實現(xiàn)測試退役詳細設計使用維護定義階段開發(fā)階段維護階段3.2需求分析與結(jié)構(gòu)化分析方法需求分析的方法結(jié)構(gòu)化分析方法面向?qū)ο蟮姆治龇椒嫦驍?shù)據(jù)流的結(jié)構(gòu)化方法(SA)面向數(shù)據(jù)結(jié)構(gòu)Jackson方法(JSD)面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開發(fā)方法(DSSD)結(jié)構(gòu)化分析常用工具:(1)數(shù)據(jù)流圖(2)數(shù)據(jù)字典(3)判定樹(4)判定表結(jié)構(gòu)化分析方法的實質(zhì)：

著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具,建立系統(tǒng)的邏輯模型。3.3結(jié)構(gòu)化設計方法、概要設計和詳細設計軟件設計

○軟件設計的基本目標是用比較抽象概括的方式確定目標系統(tǒng)如何完成預定的任務，軟件設計是確定系統(tǒng)的物理模型。從技術觀點來看，軟件設計包括軟件結(jié)構(gòu)設計、數(shù)據(jù)設計、接口設計、過程設計。從工程管理角度來看：概要設計和詳細設計。軟件設計的基本原理：（1）抽象（2）模塊化（3）信息隱蔽（4）模塊獨立化內(nèi)聚性：耦合性：在程序結(jié)構(gòu)中各模塊的內(nèi)聚性越強，則耦合性越弱。優(yōu)秀軟件應高內(nèi)聚，低耦合。3.3.2概要設計設計的基本任務軟件的系統(tǒng)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫設計編寫概要設計文檔概要設計文檔評審3.3.3詳細設計根本目標確定應用怎樣具體的實現(xiàn)所要求的系統(tǒng)，不是具體的編寫程序，而是要設計程序的“藍圖”是為軟件結(jié)構(gòu)圖中的每一個模塊確定實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用某種選定的表達工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細節(jié)。此階段的結(jié)果基本上決定了最終的程序代碼的質(zhì)量包括內(nèi)容：代碼設計輸入設計輸出設計處理過程設計用戶界面設計安全控制設計3.4軟件測試

軟件測試定義：使用人工或自動手段來運行或測定某個系統(tǒng)的過程4.4.1意義目的為了發(fā)現(xiàn)錯誤希望能以最少的人力和時間發(fā)現(xiàn)潛在的各種錯誤和缺陷保證系統(tǒng)質(zhì)量和可靠性的關鍵步驟

4.4.2測試方法靜態(tài)測試：包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量。不實際運行軟件，主要通過人工進行。動態(tài)測試：是基于計算機的測試。主要包括白盒測試方法和黑盒測試方法。測試用例：[（輸入值集），（輸出值集）]3.4.3白盒測試結(jié)構(gòu)測試將軟件看成透明的白盒，根據(jù)程序的內(nèi)部結(jié)構(gòu)和邏輯結(jié)構(gòu)來設計測試例子，對程序的路徑和過程進行測試，檢查是否滿足設計的要求主要方法：邏輯覆蓋、基本路徑測試3.4.4黑盒測試功能測試將軟件看成黑盒子，在完全不考慮軟件內(nèi)部結(jié)構(gòu)和特性的情況下，測試軟件的外部特性主要方法：等價類劃分法、邊界值分析法、錯誤推測法3.4.5軟件測試的實施單元測試（模塊測試）集成測試確認測試系統(tǒng)測試單元測試：是對模塊進行正確性檢驗的測試。是軟件測試的最小單位，主要采用靜態(tài)和動態(tài)測試法，動態(tài)測試以白盒測試法為主，輔助于黑盒測試集成測試是測試和組裝軟件的過程，主要目的是發(fā)現(xiàn)與接口有關的錯誤。確認測試驗證軟件的功能和性能及其他特性是否滿足了需求規(guī)格說明中確定的各種要求。系統(tǒng)測試將通過確認測試的軟件，與計算機硬件、外設等其他元素組合在一起，在實際環(huán)境下對計算機系統(tǒng)進行一系列的集成測試和確認測試。3.5程序調(diào)試1．任務根據(jù)測試時發(fā)現(xiàn)的錯誤，（１）找出原因和具體的位置．（２）進行改正，排除錯誤由程序開發(fā)人員來進行，誰開發(fā)的程序就由誰來進行調(diào)試2.程序調(diào)試的基本步驟：（1）錯誤定位；（2）修改設計和代碼，以排除錯誤；（3）進行回歸測試，防止引進新的錯誤。3.調(diào)試方法：（靜態(tài)、動態(tài)調(diào)試法）強行排錯法回溯法原因排除法（演繹、歸納、二分法)為了提高測試的效率，應該

A)隨機選取測試數(shù)據(jù)B)取一切可能的輸入數(shù)據(jù)作為測試數(shù)據(jù)

C)在完成編碼以后制定軟件的測試計劃D)集中對付那些錯誤群集的程序軟件生命周期中所花費用最多的階段是

A)詳細設計 B)軟件編碼C)軟件測試D)軟件維護下列敘述中，不屬于軟件需求規(guī)格說明書的作用的是

A)便于用戶、開發(fā)人員進行理解和交流

B)反映出用戶問題的結(jié)構(gòu)，可以作為軟件開發(fā)工作的基礎和依據(jù)

C)作為確認測試和驗收的依據(jù)

D)便于開發(fā)人員進行需求分析下列不屬于軟件工程的3個要素的是Ａ)工具 Ｂ)過程Ｃ)方法 Ｄ)環(huán)境例題講解開發(fā)軟件所需高成本和產(chǎn)品的低質(zhì)量之間有著尖銳的矛盾，這種現(xiàn)象稱作

A)軟件投機 B)軟件危機C)軟件工程D)軟件產(chǎn)生下面不屬于軟件設計原則的是Ａ)抽象 Ｂ)模塊化Ｃ)自底向上Ｄ)信息隱蔽開發(fā)大型軟件時，產(chǎn)生困難的根本原因是

A)大系統(tǒng)的復雜性 B)人員知識不足

C)客觀世界千變?nèi)f化 D)時間緊、任務重軟件工程的出現(xiàn)是由于

A)程序設計方法學的影響 B)軟件產(chǎn)業(yè)化的需要

C)軟件危機的出現(xiàn) D)計算機的發(fā)展軟件開發(fā)離不開系統(tǒng)環(huán)境資源的支持，其中必要的測試數(shù)據(jù)屬于

A)硬件資源B)通信資源C)支持軟件D)輔助資源在數(shù)據(jù)流圖(DFD)中，帶有名字的箭頭表示

A)模塊之間的調(diào)用關系 B)程序的組成成分

C)控制程序的執(zhí)行順序 D)數(shù)據(jù)的流向在軟件生產(chǎn)過程中，需求信息的給出者是

A)程序員B)項目管理者

C)軟件分析設計人員 D)軟件用戶模塊獨立性是軟件模塊化所提出的要求，衡量模塊獨立性的度量標準則是模塊的

A)抽象和信息隱蔽 B)局部化和封裝化

C)內(nèi)聚性和耦合性 D)激活機制和控制方法軟件開發(fā)的結(jié)構(gòu)化生命周期方法將軟件生命周期劃分成

A)定義、開發(fā)、運行維護B)設計階段、編程階段、測試階段

C)總體設計、詳細設計、編程調(diào)試D)需求分析、功能定義、系統(tǒng)設計在軟件工程中，白箱測試法可用于測試程序的內(nèi)部結(jié)構(gòu)。此方法將程序看做是

A)

路徑的集合B)循環(huán)的集合C)目標的集合D)地址的集合完全不考慮程序的內(nèi)部結(jié)構(gòu)和內(nèi)部特征，而只是根據(jù)程序功能導出測試用例的測試方法是

A)黑箱測試法B)白箱測試法C)錯誤推測法D)安裝測試法為了避免流程圖在描述程序邏輯時的靈活性，提出了用方框圖來代替?zhèn)鹘y(tǒng)的程序流程圖，通常也把這種圖稱為

A)PAD圖 B)N-S圖C)結(jié)構(gòu)圖 D)數(shù)據(jù)流圖下列敘述中，正確的是

A)軟件就是程序清單B)軟件就是存放在計算機中的文件

C)軟件應包括程序清單及運行結(jié)果D)軟件包括程序和文檔軟件設計中，有利于提高模塊獨立性的一個準則是

A)低內(nèi)聚低耦合 B)低內(nèi)聚高耦合

C)高內(nèi)聚低耦合 D)高內(nèi)聚高耦合軟件生命周期中花費時間最多的階段是

A)詳細設計 B)軟件編碼C)軟件測試D)軟件維護下列敘述中，不屬于結(jié)構(gòu)化分析方法的是

A)面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法

B)面向數(shù)據(jù)結(jié)構(gòu)的Jackson方法

C)面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開發(fā)方法

D)面向?qū)ο蟮姆治龇椒ㄔ敿氃O計的結(jié)果基本決定了最終程序的

A)代碼的規(guī)模 B)運行速度

C)質(zhì)量 D)可維護性下列不屬于靜態(tài)測試方法的是

A)代碼檢查 B)白盒法

C)靜態(tài)結(jié)構(gòu)分析 D)代碼質(zhì)量度量軟件調(diào)試的目的是A）發(fā)現(xiàn)錯誤B）改正錯誤C）改善軟件的性能D）挖掘軟件的潛能軟件需求分析階段的工作，可以分為四個方面：需求獲取，需求分析，編寫需求規(guī)格說明書，以及A）階段性報告B）需求評審C）總結(jié)D）都不正確軟件是程序、數(shù)據(jù)和____的集合。Jackson方法是一種面向____的結(jié)構(gòu)化方法。軟件工程研究的內(nèi)容主要包括：____技術和軟件工程管理。文檔數(shù)據(jù)結(jié)構(gòu)軟件開發(fā)

通常，將軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的過程稱為

。耦合和內(nèi)聚是評價模塊獨立性的兩個主要標準，其中

反映了模塊內(nèi)各成分之間的聯(lián)系。測試的目的是暴露錯誤，評價程序的可靠性；而

的目的是發(fā)現(xiàn)錯誤的位置并改正錯誤。單元測試又稱模塊測試，一般采用

測試。軟件的

設計又稱為總體結(jié)構(gòu)設計，其主要任務是建立軟件系統(tǒng)的總體結(jié)構(gòu)。軟件生命周期耦合程序調(diào)試白盒概要4.數(shù)據(jù)庫設計基礎4.1基本概念1.數(shù)據(jù)(Data)實際上就是描述事物的符號記錄2.數(shù)據(jù)庫(DB)長期存儲在計算機內(nèi)的，有組織的，可共享的數(shù)據(jù)集合。數(shù)據(jù)庫中的數(shù)據(jù)按一定的數(shù)學模型組織、描述和存儲，具有較小的冗余度，較高的數(shù)據(jù)獨立性和易擴展性，并可為各種用戶共享。3.數(shù)據(jù)庫管理系統(tǒng)(DBMS)數(shù)據(jù)庫系統(tǒng)的核心軟件解決如何科學地組織和存儲數(shù)據(jù)，如何高效的獲取和維護數(shù)據(jù)的系統(tǒng)軟件4.數(shù)據(jù)庫管理員5.數(shù)據(jù)庫系統(tǒng)（DBS）由數(shù)據(jù)庫（數(shù)據(jù)）、數(shù)據(jù)庫管理系統(tǒng)（軟件）、數(shù)據(jù)庫管理員（人員）、系統(tǒng)平臺之硬件平臺（硬件）和軟件平臺（軟件）構(gòu)成。數(shù)據(jù)庫管理技術的發(fā)展人工管理階段文件系統(tǒng)階段數(shù)據(jù)庫系統(tǒng)階段（層次、網(wǎng)狀、關系）8.數(shù)據(jù)庫系統(tǒng)的基本特點數(shù)據(jù)的集成性采用統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)方式數(shù)據(jù)的高共享性與低冗余性數(shù)據(jù)獨立性物理獨立性和邏輯獨立性數(shù)據(jù)統(tǒng)一管理與控制數(shù)據(jù)的完整性檢查數(shù)據(jù)的安全性檢查并發(fā)控制9.數(shù)據(jù)庫系統(tǒng)的內(nèi)部結(jié)構(gòu)體系數(shù)據(jù)庫系統(tǒng)的三級模式（1）概念模式（2）外模式（3）內(nèi)模式內(nèi)模式處于最底層，它反映了數(shù)據(jù)在計算機物理結(jié)構(gòu)中的實際存儲形式概念模式處于中層，它放映了設計者的數(shù)據(jù)全局邏輯要求外模式處于最外層，它反映了用戶對數(shù)據(jù)的要求4.2數(shù)據(jù)模型數(shù)據(jù)模型：是現(xiàn)實世界數(shù)據(jù)特征的抽象。在數(shù)據(jù)庫中用數(shù)據(jù)模型這個工具來抽象、表示和處理現(xiàn)實世界中的數(shù)據(jù)和信息。通俗地講數(shù)據(jù)模型就是現(xiàn)實世界的模擬。模型的分類：（1）概念模型（信息模型）：它是按用戶的觀點來對數(shù)據(jù)和信息建模，主要用于數(shù)據(jù)庫設計。（2）數(shù)據(jù)模型：主要包括網(wǎng)狀模型、層次模型、關系模型，它是按計算機系統(tǒng)對數(shù)據(jù)建模，主要用于DBMS的實現(xiàn)。對客觀對象的抽象過程：客觀對象信息世界（概念模型）機器世界（數(shù)據(jù)模型）(物理模型)人的認識抽象轉(zhuǎn)換4.2.2E-R模型（實體聯(lián)系模型）基本概念（1）實體（2）屬性（3）聯(lián)系一對一（1：1）一對多（1：M或M：1）多對多（M：N）班級擁有班長11班級擁有學生1n課程選修學生mn4.2.5關系模型采用二維表來表示，簡稱表。二維表的性質(zhì)：（1）元素個數(shù)有限性（2）元組的惟一性（3）元組的次序無關性（4）元組分量的原子性（5）屬性名惟一性（6）屬性的次序無關性（7）分量值域的同一性關系中的數(shù)據(jù)約束

:（1）實體完整性約束（2）參照完整性約束（3）用戶定義的完整性約束運算符集合運算:專門的關系運算:比較運算:>>=<=<=<>邏輯運算:4.3關系代數(shù)設關系R和關系S具有相同的目n,且相應的屬性取自同一個域,則可有如下定義:1.并2.差3.交傳統(tǒng)的集合運算例子:ABCRa1a1a2b1b2b2c1c2c1ABCSa1a1a2b2b3b2c2c2c1ABCRSa1a1a2a1b1b2b2b3c1c2c1c2ABCRa1a1a2b1b2b2c1c2c1ABCSa1a1a2b2b3b2c2c2c1ABCRSa1a2b2b2c2c1ABCR-Sa1b1c1RSa1a1a1a1a1a1a2a2a2ABCABCb1b1b1b2b2b2b2b2b2c1c1c1c2c2c2c1c1c1a1a1a2a1a1a2a1a1a2b2b3b2b2b3b2b2b3b2c2c2c1c2c2c1c2c2c1ABCRa1a1a2b1b2b2c1c2c1ABCSa1a1a2b2b3b2c2c2c14.笛卡兒×專門的關系運算：1.選擇例子1:查詢信息系(IS系)的全體學生.

Sno

Sname

SsexSageSdept劉晨張立9500295004ISIS女男1919

Sno

Sname

SsexSageSdept李勇劉晨王敏張立95001950029500395004CSISMAIS男女女男201918192.投影例子4:查詢學生的姓名和所在系.

Sno

Sname

SsexSageSdept李勇劉晨王敏張立95001950029500395004CSISMAIS男女女男20191819Sname

Sdept李勇劉晨王敏張立CSISMAIS3.連接等值連接:當連接條件為“=”時的連接運算.AR.BCS.BEABCRa1a1a2a2b1b2b3b456812BESb1b2b3b3b5371022a2b38b310a2b38b32AR.BCEa1a1a2a2b1b2b3b3568837102自然連接:是一種特殊的等值連接,它要求兩個關系中進行比較的分量是相同的屬性組,并且在結(jié)果中把重復的屬性列去掉.ABCRa1a1a2a2b1b2b3b456812BESb1b2b3b3b5371022數(shù)據(jù)庫管理系統(tǒng)DBMS中用來定義模式、內(nèi)模式和外模式的語言為

A)C B)BasicC)DDL D)DML下列有關數(shù)據(jù)庫的描述，正確的是

A)數(shù)據(jù)庫是一個DBF文件 B)數(shù)據(jù)庫是一個關系

C)數(shù)據(jù)庫是一個結(jié)構(gòu)化的數(shù)據(jù)集合 D)數(shù)據(jù)庫是一組文件下列有關數(shù)據(jù)庫的描述，正確的是

A)數(shù)據(jù)處理是將信息轉(zhuǎn)化為數(shù)據(jù)的過程

B)數(shù)據(jù)的物理獨立性是指當數(shù)據(jù)的邏輯結(jié)構(gòu)改變時，數(shù)據(jù)的存儲結(jié)構(gòu)不變

C)關系中的每一列稱為元組，一個元組就是一個字段

D)如果一個關系中的屬性或?qū)傩越M并非該關系的關鍵字，但它是另一個關系的關鍵字，則稱其為本關系的外關鍵字例題講解應用數(shù)據(jù)庫的主要目的是

A)解決數(shù)據(jù)保密問題 B)解決數(shù)據(jù)完整性問題

C)解決數(shù)據(jù)共享問題 D)解決數(shù)據(jù)量大的問題在數(shù)據(jù)庫設計中，將E-R圖轉(zhuǎn)換成關系數(shù)據(jù)模型的過程屬于

A)需求分析階段 B)邏輯設計階段

C)概念設計階段 D)物理設計階段在數(shù)據(jù)管理技術的發(fā)展過程中，經(jīng)歷了人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫系統(tǒng)階段。其中數(shù)據(jù)獨立性最高的階段是Ａ)數(shù)據(jù)庫系統(tǒng) Ｂ)文件系統(tǒng)Ｃ)人工管理 Ｄ)數(shù)據(jù)項管理下述關于數(shù)據(jù)庫系統(tǒng)的敘述中正確的是Ａ)數(shù)據(jù)庫系統(tǒng)減少了數(shù)據(jù)冗余Ｂ)數(shù)據(jù)庫系統(tǒng)避免了一切冗余Ｃ)數(shù)據(jù)庫系統(tǒng)中數(shù)據(jù)的一致性是指數(shù)據(jù)類型一致Ｄ)數(shù)據(jù)庫系統(tǒng)比文件系統(tǒng)能管理更多的數(shù)據(jù)索引屬于

A)模式 B)內(nèi)模式C)外模式 D)概念模式數(shù)據(jù)庫系統(tǒng)的核心是

A)數(shù)據(jù)庫 B)數(shù)據(jù)庫管理系統(tǒng)

C)模擬模型 D)軟件工程分布式數(shù)據(jù)庫系統(tǒng)不具有的特點是

A)數(shù)據(jù)分布性和邏輯整體性B)位置透明性和復制透明性

C)分布性 D)數(shù)據(jù)冗余關系表中的每一橫行稱為一個Ａ)元組 Ｂ)字段Ｃ)屬性 Ｄ)碼下列數(shù)據(jù)模型中，具有堅實理論基礎的是

A)層次模型 B)網(wǎng)狀模型

C)關系模型 D)以上3個都是下列SQL語句中，用于修改表結(jié)構(gòu)的是

A)ALTER B)CREATEC)UPDATED)INSERT數(shù)據(jù)庫、數(shù)據(jù)庫系統(tǒng)和數(shù)據(jù)庫管理系統(tǒng)之間的關系是

A)數(shù)據(jù)庫包括數(shù)據(jù)庫系統(tǒng)和數(shù)據(jù)庫管理系統(tǒng)

B)數(shù)據(jù)庫系統(tǒng)包括數(shù)據(jù)庫和數(shù)據(jù)庫管理系統(tǒng)

C)數(shù)據(jù)庫管理系統(tǒng)包括數(shù)據(jù)庫和數(shù)據(jù)庫系統(tǒng)