二級(jí)公共基礎(chǔ)知識(shí)

二級(jí)VB考試實(shí)訓(xùn)主講:張靜辦公地點(diǎn):SA408聯(lián)系方式試大綱基本要求

1.熟悉VisualBasic集成開(kāi)發(fā)環(huán)境。

2.了解VisualBasic中對(duì)象的概念和事件驅(qū)動(dòng)程序的基本特性。

3.了解簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)和算法

4.能夠編寫(xiě)和調(diào)試簡(jiǎn)單的VisualBasic程序?？荚嚧缶V考試內(nèi)容(略)考試方式

1.筆試：90分鐘，滿(mǎn)分100分，其中含公共基礎(chǔ)知識(shí)部分的30分。(選擇題35*2’,填空題15*2’)

2.上機(jī)操作：90分鐘，滿(mǎn)分100分。上機(jī)操作包括：

(1)基本操作。

(2)簡(jiǎn)單應(yīng)用。

(3)綜合應(yīng)用?？荚囐Y源2/→課件下載→張靜→課件→二級(jí)VB/→計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)--內(nèi)容介紹考試大綱掌握算法的基本概念掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作掌握基本排序和查找算法掌握逐步求精的結(jié)構(gòu)化程序設(shè)計(jì)方法掌握軟件工程的基本方法,具有初步應(yīng)用相關(guān)技術(shù)進(jìn)行軟件開(kāi)發(fā)的能力掌握數(shù)據(jù)庫(kù)的基本知識(shí),了解關(guān)系數(shù)據(jù)庫(kù)的設(shè)計(jì)考試內(nèi)容1基本數(shù)據(jù)結(jié)構(gòu)與算法算法的基本概念:算法的復(fù)雜度的概念和意義(時(shí)間復(fù)雜度和空間復(fù)雜度)數(shù)據(jù)結(jié)構(gòu)的定義:數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu);數(shù)據(jù)結(jié)構(gòu)的圖形表示;線(xiàn)性結(jié)構(gòu)與非線(xiàn)性結(jié)構(gòu)的概念線(xiàn)性表的定義:線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除運(yùn)算考試內(nèi)容棧和隊(duì)列的定義:棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算線(xiàn)性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算樹(shù)的基本概念：二叉樹(shù)的定義及其存儲(chǔ)結(jié)構(gòu)；二叉樹(shù)的前序、中序和后序遍歷順序查找與二分法查找算法：基本排序算法（交換類(lèi)排序、選擇類(lèi)排序、插入類(lèi)排序）考試內(nèi)容2程序設(shè)計(jì)基礎(chǔ)程序設(shè)計(jì)方法與風(fēng)格結(jié)構(gòu)化程序設(shè)計(jì)面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對(duì)象，方法，屬性及繼承與多態(tài)性考試內(nèi)容3軟件工程基礎(chǔ)軟件工程基本概念，軟件生命周期概念，軟件工具與軟件開(kāi)發(fā)環(huán)境結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說(shuō)明書(shū)結(jié)構(gòu)化設(shè)計(jì)方法，總體設(shè)計(jì)與詳細(xì)設(shè)計(jì)軟件測(cè)試的方法，白盒測(cè)試與黑盒測(cè)試，測(cè)試用例設(shè)計(jì)，軟件測(cè)試的實(shí)施，單元測(cè)試、集成測(cè)試和系統(tǒng)測(cè)試程序調(diào)試，靜態(tài)調(diào)試與動(dòng)態(tài)調(diào)試考試內(nèi)容4數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)數(shù)據(jù)庫(kù)的基本概念：數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)管理系統(tǒng)，數(shù)據(jù)庫(kù)系統(tǒng)數(shù)據(jù)模型：實(shí)體聯(lián)系模型及E-R圖，從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型關(guān)系代數(shù)運(yùn)算：包括集合運(yùn)算及選擇、投影、連接運(yùn)算，數(shù)據(jù)庫(kù)規(guī)范化理論數(shù)據(jù)庫(kù)設(shè)計(jì)方法和步驟：需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略考試方式筆試30分10道選擇題、5道填空題算法與數(shù)據(jù)結(jié)構(gòu)---二級(jí)公共基礎(chǔ)知識(shí)之一命題情況本章在最近幾次考試中題量都在５題左右算法基本概念、算法復(fù)雜度、數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)、線(xiàn)性結(jié)構(gòu)與非線(xiàn)性結(jié)構(gòu)、棧及其基本運(yùn)算、隊(duì)列、線(xiàn)性鏈表、二叉樹(shù)的基本概念及其特性、順序查找、二分法查找、交換類(lèi)排序法是考核的重點(diǎn)。其中，算法、棧和隊(duì)列、二叉樹(shù)是重中之重。1算法★★★★算法的定義:為解決某個(gè)特定問(wèn)題而采取的確定且有限的步驟的一種描述,簡(jiǎn)單地說(shuō),就是解決問(wèn)題的操作步驟考點(diǎn)1：算法的特點(diǎn)(1)確定性(無(wú)歧義)(2)有窮性(操作步驟是有限的)(3)有效性(可行性,能夠得出滿(mǎn)意的結(jié)果)(4)輸入:有0個(gè)或多個(gè)輸入(擁有足夠的情報(bào))(5)輸出:有一個(gè)或多個(gè)輸出1算法★★★★考點(diǎn)2算法的基本要素兩種基本要素:(1)對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作:算術(shù)運(yùn)算:+、-、×、÷邏輯運(yùn)算：&、||、!關(guān)系運(yùn)算：>、<、=、≠數(shù)據(jù)傳輸：賦值、輸入、輸出(2)算法的控制結(jié)構(gòu),即運(yùn)算或操作間的順序控制結(jié)構(gòu)：順序、分支（選擇）、循環(huán)描述算法的工具有：傳統(tǒng)的流程圖、N-S結(jié)構(gòu)化流程圖、算法描述語(yǔ)言等1算法★★★★算法設(shè)計(jì)的基本方法：列舉法、歸納法、遞推法、遞歸法、減半遞推技術(shù)和回溯法算法設(shè)計(jì)的要求：正確性、健壯性、可讀性、高效性1算法★★★★考點(diǎn)3:算法復(fù)雜度(1)時(shí)間復(fù)雜度:執(zhí)行算法所需要的計(jì)算工作量Ｔ(n)＝O(f(n)),只依賴(lài)于問(wèn)題的規(guī)模，如

for(i=1;i<n;i++)

for(j=0;j<n;j++)

a[i][j]=i+j;此程度段計(jì)算量為(n-1)*n,則它的時(shí)間復(fù)雜度為O(n2)兩種分析的方法:平均時(shí)間復(fù)雜度，最壞時(shí)間復(fù)雜度1算法★★★★(2)算法的空間復(fù)雜度：描述算法的存儲(chǔ)空間要求，記作S(n)=O(g(n))輸入數(shù)據(jù)所占的存儲(chǔ)空間；程序本身所占的存儲(chǔ)空間；算法執(zhí)行過(guò)程中所需要的額外空間（包括算法程序執(zhí)行過(guò)程中的工作單元，以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲(chǔ)空間）為了降低算法的空間復(fù)雜度，主要減少輸入數(shù)據(jù)所占的存儲(chǔ)空間以及額外空間，通常采用壓縮存儲(chǔ)技術(shù)1算法★★★★例1：下列敘述中正確的是：A、算法的效率只與問(wèn)題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)B、算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量C、數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是一一對(duì)應(yīng)的D、算法的時(shí)間復(fù)雜度與空間復(fù)雜度一定相關(guān)B1算法★★★★例2：下列敘述中正確的是：A、一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度也必定大B、一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度必定小C、一個(gè)算法的時(shí)間復(fù)雜度越大，則其空間復(fù)雜度必定小D、以上三種說(shuō)法均不對(duì)D２數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)★★★定義：反映數(shù)據(jù)元素之間關(guān)系的數(shù)據(jù)元素集合的表示。數(shù)據(jù)：需要處理的數(shù)據(jù)元素的集合結(jié)構(gòu)：就是關(guān)系，是集合中各個(gè)數(shù)據(jù)元素之間存在的某種關(guān)系（或聯(lián)系）２數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)★★★考點(diǎn)：數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)：用來(lái)描述數(shù)據(jù)元素之間的邏輯關(guān)系---線(xiàn)性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、網(wǎng)狀結(jié)構(gòu)、集合數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，也稱(chēng)數(shù)據(jù)的物理結(jié)構(gòu)---順序、鏈?zhǔn)?、索引、散列邏輯結(jié)構(gòu)K1K2K3K4K5ABＣＤＥＧＦＨＩJ存儲(chǔ)結(jié)構(gòu)200201202203204K1204K3203K4206K2202K5∧200201202203204205206200Head數(shù)據(jù)指針2數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)例1：下列敘述中正確的是：A、程序執(zhí)行的效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)密切相關(guān)B、程序執(zhí)行的效率只取決于程序的控制結(jié)構(gòu)C、程序執(zhí)行的效率只取決于所處理的數(shù)據(jù)量D、以上三種說(shuō)法都不對(duì)A2數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)例2：下列敘述中正確的是：A、數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)必定是一一對(duì)應(yīng)的B、由于計(jì)算機(jī)在存儲(chǔ)空間是向量式的存儲(chǔ)結(jié)構(gòu)，因此，利用數(shù)組只能處理線(xiàn)性結(jié)構(gòu)C、程序設(shè)計(jì)語(yǔ)言中的數(shù)組一般是順序存儲(chǔ)結(jié)構(gòu)，因此，利用數(shù)組只能處理線(xiàn)性結(jié)構(gòu)D、以上說(shuō)法都不對(duì)D2數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)例3：下列敘述中正確的是：A、一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲(chǔ)結(jié)構(gòu)B、數(shù)據(jù)邏輯結(jié)構(gòu)屬于線(xiàn)性結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)屬于非線(xiàn)性結(jié)構(gòu)C、一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)不影響數(shù)據(jù)處理的效率D、一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理的效率D３線(xiàn)性表—最簡(jiǎn)單最常用的一種數(shù)據(jù)結(jié)構(gòu)★★線(xiàn)性表是具有相同數(shù)據(jù)類(lèi)型的N個(gè)數(shù)據(jù)元素組成的有限序列（a1,a2,…,ai-1,ai,ai+1,…,an）考點(diǎn)１：線(xiàn)性表的兩種存儲(chǔ)結(jié)構(gòu)：順序，鏈?zhǔn)娇键c(diǎn)２：線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)（順序表）特點(diǎn)：線(xiàn)性表中所有元素所占的存儲(chǔ)空間是連續(xù)的線(xiàn)性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的３線(xiàn)性表隨機(jī)存取（通常用數(shù)組來(lái)描述順序表）在順序表中，若第一個(gè)元素存放的位置是LOC(a1),每個(gè)元素占用的空間大小為c，則元素ai的存放位置為：LOC(ai)=LOC(a1)+(i-1)*c插入、刪除：插入：最好情況下的時(shí)間復(fù)雜度Ｏ(1)(在表尾插入)，最環(huán)時(shí)間復(fù)雜度是Ｏ(n)（即在表頭插入），平均時(shí)間復(fù)雜度為Ｏ(n)刪除：同插入a1…ai-1ai…ana1…ai-1eai…an３線(xiàn)性表考點(diǎn)３：線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：?jiǎn)捂湵?、雙向鏈表、循環(huán)鏈表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)采用結(jié)點(diǎn)來(lái)表示數(shù)據(jù)元素。一個(gè)結(jié)點(diǎn)由兩個(gè)部分組成：數(shù)據(jù)域和指針域。單鏈表的插入、刪除和查找３種基本操作同Ｃ語(yǔ)言介紹的鏈表時(shí)間復(fù)雜度均為：O(ListLength(L)),ListLength(L)表示鏈表Ｌ的長(zhǎng)度３線(xiàn)性表例1：在一個(gè)長(zhǎng)度為N的順序表中，向第I個(gè)元素位置插入一個(gè)新元素時(shí)，需要從后向前依次后移

個(gè)元素A、N-IB、IC、N-I-1D、N-I+1例2：在一個(gè)長(zhǎng)度為N的順序表中，刪除第I個(gè)元素，需要向前移動(dòng)

個(gè)元素DN-I４棧和隊(duì)列★★★★★棧和隊(duì)列都是一種特殊的線(xiàn)性表考點(diǎn)１：棧及其基本操作特點(diǎn)：先進(jìn)后出棧的基本操作：入棧、出棧、讀棧頂元素an-1…a2a1棧頂棧底進(jìn)棧出棧４棧和隊(duì)列例：對(duì)于一個(gè)棧，如果輸入項(xiàng)序列由a,b,c所組成，則不可能產(chǎn)生的輸出序列是（）A)cabB)abcC)bacD)cba４棧和隊(duì)列考點(diǎn)２：隊(duì)列及其基本操作特點(diǎn)：先進(jìn)先出a0a1a2…an-1入隊(duì)rear(只能插入元素)出隊(duì)front(只能刪除元素)……frontreara8a7a60MAXSIZE-1順序隊(duì)列循環(huán)隊(duì)列順序隊(duì)列的運(yùn)算a1a1a2a2frontrearfrontrearfrontrearfrontrear空隊(duì)列a1入隊(duì)列rear=rear+1a2入隊(duì)列rear=rear+1a1出隊(duì)列front=front+1循環(huán)隊(duì)列的運(yùn)算入隊(duì)：rear=(rear+1)%MAXSIZE出隊(duì)：front=(front+1)%MAXSIZE隊(duì)列滿(mǎn)/空的判斷（front=rear）通常增加標(biāo)志量Ｓ，Ｓ定義如下S=0，表示循環(huán)隊(duì)列為空S=1，表示循環(huán)隊(duì)列非空那么，當(dāng)s=0且front=rear時(shí),隊(duì)列為空否則，當(dāng)s=1且front=rear時(shí),隊(duì)列為滿(mǎn)5線(xiàn)性鏈表★★定義：線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)－－用一組不連續(xù)的存儲(chǔ)單元存儲(chǔ)線(xiàn)性表中的各個(gè)元素．K1204K3203K4206K2202K5∧200201202203204205206200Head數(shù)據(jù)指針HeadK1K2K3K4K5NULL邏輯上物理上線(xiàn)性鏈表的基本運(yùn)算1、查找2、插入3、刪除★鏈表的插入◆插在鏈表的頭結(jié)點(diǎn)之前

head148325033471NULL0511qq->next=head;head=q;◆插在兩個(gè)結(jié)點(diǎn)之間

head148325033471NULL0511qp=p->next;q->next=p->next;p->next=q;pp先通過(guò)一條或多條p=p->next;這類(lèi)語(yǔ)句，向后逐步尋找插入點(diǎn)，然后實(shí)施有關(guān)的鏈接操作．◆插在尾結(jié)點(diǎn)之后

head148325033471NULL0511qpNULLp=head;while(p->next!=NULL)p=p->next;p->next=q;q->next=NULL;★鏈表的刪除操作◆刪除頭結(jié)點(diǎn)

headp148325033471NULLhead=p->next;free(p);★鏈表的刪除操作◆刪除中間結(jié)點(diǎn)如:刪除結(jié)點(diǎn)q

headp3471NULLp->next=q->next;free(q);q14832503刪除學(xué)號(hào)為2的學(xué)生q=head;while(q->num!=2){p=q;q=q->next;}p->next=q->next;free(q);將指針p,q移到合適的位置鏈表例1:下列敘述中正確的是:A、線(xiàn)性鏈表是線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B、棧與隊(duì)列是非線(xiàn)性結(jié)構(gòu)C、雙向鏈表是非線(xiàn)性結(jié)構(gòu)D、只有根結(jié)點(diǎn)的二叉樹(shù)是線(xiàn)性結(jié)構(gòu)解析：根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后關(guān)系的復(fù)雜程序，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類(lèi)型：線(xiàn)性結(jié)構(gòu)與非線(xiàn)性結(jié)構(gòu)。如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿(mǎn)足下列兩個(gè)條件：1）有且只有一個(gè)頭結(jié)點(diǎn)；2）每個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最有一個(gè)后件。則稱(chēng)該數(shù)據(jù)結(jié)構(gòu)為線(xiàn)性結(jié)構(gòu)，又稱(chēng)線(xiàn)性表。如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線(xiàn)性結(jié)構(gòu)，則稱(chēng)之為非線(xiàn)性結(jié)構(gòu)。線(xiàn)性表、棧與隊(duì)列、線(xiàn)性鏈表都是線(xiàn)性結(jié)構(gòu)，而二叉樹(shù)是非線(xiàn)性結(jié)構(gòu)。A鏈表例2：線(xiàn)性表的存儲(chǔ)結(jié)構(gòu)主要分為順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。隊(duì)列是一種特殊的線(xiàn)性表，循環(huán)隊(duì)列是

存儲(chǔ)結(jié)構(gòu)。例3：數(shù)據(jù)結(jié)構(gòu)分為線(xiàn)性結(jié)構(gòu)與非線(xiàn)性結(jié)構(gòu)，帶鏈的隊(duì)列屬于

結(jié)構(gòu)。

順序線(xiàn)性6樹(shù)★★★★★考點(diǎn)１：樹(shù)的基本概念（樹(shù)是一種簡(jiǎn)單的非線(xiàn)性結(jié)構(gòu)）ABCDEFGIJHKL結(jié)點(diǎn)根葉子雙親，孩子，兄弟結(jié)點(diǎn)的度：結(jié)點(diǎn)的子樹(shù)數(shù)目樹(shù)的度：樹(shù)內(nèi)各結(jié)點(diǎn)的度的最大值樹(shù)的深度（高度）：樹(shù)中結(jié)點(diǎn)最大層次數(shù)6樹(shù)考點(diǎn)２：二叉樹(shù)及其基本性質(zhì)遍歷：先序，中序，后序ABＣＤＥＧＦＨＩJ先序：ＡＢＤＨＩＥＣＦＪＧ中序：ＨＤＩＢＥＡＦＪＣＧ后序：ＨＩＤＥＢＪＦＧＣＡ6樹(shù)滿(mǎn)二叉樹(shù)：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)，每一層上的結(jié)點(diǎn)樹(shù)都達(dá)到最大ＡBＣＤＥＧＦＨＩＪＫＬＭＮＯ6樹(shù)完全二叉樹(shù)：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)ＡBＣＤＥＧＦＨＩＪ6樹(shù)二叉樹(shù)的性質(zhì)性質(zhì)１：在二叉樹(shù)的第k層上，最多有2k-1(k≥1)個(gè)結(jié)點(diǎn)（滿(mǎn)二叉樹(shù)為最多的情況）性質(zhì)２：深度為m的二叉樹(shù)最多有2m-1個(gè)結(jié)點(diǎn)（滿(mǎn)二叉樹(shù)為最多的情況）性質(zhì)３：在任意一棵二叉樹(shù)中，度數(shù)為０的結(jié)點(diǎn)（葉子）總比度為２的結(jié)點(diǎn)多一個(gè)，即n0=n2+1,n0表示度為０的結(jié)點(diǎn)數(shù)，n2為度為２的結(jié)點(diǎn)數(shù)6樹(shù)性質(zhì)４：具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)的深度至少為[log2n]+1,[

]表示取整性質(zhì)５：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為[log2n]+16樹(shù)例1：一棵二叉樹(shù)中共有70個(gè)葉子結(jié)點(diǎn)與80個(gè)度為1的結(jié)點(diǎn)，則該二叉樹(shù)的總結(jié)點(diǎn)數(shù)為：A、219B、221C、229D、231解析：根據(jù)二叉樹(shù)的性質(zhì)，度為0的結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個(gè)。因此度為2的結(jié)點(diǎn)數(shù)為69，所以一共是219個(gè)結(jié)點(diǎn)。A6樹(shù)例2：對(duì)下列二叉樹(shù)進(jìn)行前序遍歷的結(jié)果為

。例3：在深度為7的滿(mǎn)二叉樹(shù)中，葉子結(jié)點(diǎn)個(gè)數(shù)為：度為2的結(jié)點(diǎn)個(gè)數(shù)為：ＡBＣＤＥXＦZYABDYECFXZ27-1=64636樹(shù)例4：若某二叉樹(shù)的前序遍歷是ABDGCEFH，中序遍歷是DGBAECHF，則后序遍歷是：例5：若某二叉樹(shù)的中序遍歷是DEBGFAC，后序遍歷是EDGFBCA，則前序遍歷是：GDBEHFCAABDEFGC7排序排序時(shí)間復(fù)雜度最壞情況比較次數(shù)冒泡排序O(n2)n(n-1)/2快速排序O(nlog2n)n(n-1)/2O(n2)簡(jiǎn)單選擇排序O(n2)n(n-1)/2直接插入排序O(n2)n(n-1)/2若n較小，可采用直接插入排序或直接選擇排序．若文件的初始狀態(tài)已是基本有序，則選用直接插入排序或冒泡排序．若n較大，則應(yīng)采用快速排序或堆排序．8查找考點(diǎn)１：順序查找O(n)考點(diǎn)２：二分查找O(log2n)程序設(shè)計(jì)基礎(chǔ)---二級(jí)公共基礎(chǔ)知識(shí)之二命題情況本章在最近幾次考試中題量很少，一般只有一道選擇題面向?qū)ο蟪绦蛟O(shè)計(jì)特點(diǎn)和方法、結(jié)構(gòu)化程序設(shè)計(jì)方法是本章考核重點(diǎn)1結(jié)構(gòu)化程序設(shè)計(jì)★★考點(diǎn)1：原則自頂向下、逐步求精、模塊化、限制使用goto語(yǔ)句考點(diǎn)2：基本結(jié)構(gòu)：順序、選擇（分支）、循環(huán)（重復(fù)）2面向?qū)ο蟪绦蛟O(shè)計(jì)★★★OOP(Object-OrientedProgramming)：系統(tǒng)中的對(duì)象及對(duì)象之間的關(guān)系能夠如實(shí)反映問(wèn)題域中固有事物及其關(guān)系．考點(diǎn)１：OOP的主要優(yōu)點(diǎn)1)與人類(lèi)習(xí)慣的思維方法一致.2)穩(wěn)定性好.3)可重用性好.4)易于開(kāi)發(fā)大型軟件產(chǎn)品.5)可維護(hù)性好.2面向?qū)ο蟪绦蛟O(shè)計(jì)考點(diǎn)2:基本概念對(duì)象:現(xiàn)實(shí)世界中的每個(gè)實(shí)體,如:人,汽車(chē),電視等屬性:對(duì)象所包含的信息,如書(shū)是一個(gè)對(duì)象,它的屬性可以是書(shū)名,作者,出版社,出版年份,定價(jià)等事件:由對(duì)象識(shí)別的一個(gè)動(dòng)作,如單擊鼠標(biāo)方法:規(guī)定了對(duì)象的行為,表示對(duì)象所能提供的服務(wù)類(lèi)和實(shí)例:類(lèi)是一組具有相同屬性和相同操作的對(duì)象的集合.一個(gè)類(lèi)中的每個(gè)對(duì)象都是這個(gè)類(lèi)的一個(gè)實(shí)例;如”轎車(chē)”是一個(gè)類(lèi),”張三的轎車(chē)”就是它的一個(gè)實(shí)例2面向?qū)ο蟪绦蛟O(shè)計(jì)繼承(派生):使用已有的類(lèi)定義作為基礎(chǔ),建立新類(lèi)的定義技術(shù).繼承具有傳遞性,如果類(lèi)C繼承類(lèi)B,類(lèi)B繼承類(lèi)A,則類(lèi)C繼承類(lèi)A多態(tài)性:指同一個(gè)操作作用于不同的對(duì)象上可以有不同的解釋,并產(chǎn)生不同的執(zhí)行結(jié)果.如”畫(huà)”操作,作用在”矩形”對(duì)象和”圓”對(duì)象上,產(chǎn)生的結(jié)果就不同.例1：在面向?qū)ο蠓椒ㄖ?，?shí)現(xiàn)信息隱蔽是依靠

。A、對(duì)象的繼承B、對(duì)象的多態(tài)C、對(duì)象的封裝D、對(duì)象的分類(lèi)例2：下列選項(xiàng)中不屬于面向?qū)ο蟪绦蛟O(shè)計(jì)特征的是

。A、繼承性B、多態(tài)性C、類(lèi)比性D、封裝性CC例3：在面向?qū)ο蠓椒ㄖ校?/p>

描述的是具有相似屬性與操作的一組對(duì)象。例4：在面向?qū)ο蠓椒ㄖ校?lèi)的實(shí)例稱(chēng)為

。類(lèi)對(duì)象軟件工程基礎(chǔ)---二級(jí)公共基礎(chǔ)知識(shí)之三大綱要求1.軟件工程基本概念，軟件生命周期概念，軟件工具與軟件開(kāi)發(fā)環(huán)境。

2.結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說(shuō)明書(shū)。

3.結(jié)構(gòu)化設(shè)計(jì)方法，總體設(shè)計(jì)與詳細(xì)設(shè)計(jì)。

4.軟件測(cè)試的方法，白盒測(cè)試與黑盒測(cè)試，測(cè)試用例設(shè)計(jì)，軟件測(cè)試的實(shí)施，單元測(cè)試、集成測(cè)試和系統(tǒng)測(cè)試。

5.程序的調(diào)試，靜態(tài)調(diào)試與動(dòng)態(tài)調(diào)試。命題情況本章在最近幾次考試中選擇題一般2題，填空題2-3題，約占試卷總分值的確30%軟件生命周期、軟件的測(cè)試、軟件調(diào)試是本章考核重點(diǎn)考點(diǎn)分析1軟件工程基本概念考點(diǎn)1:軟件危機(jī)與軟件工程（了解）1、軟件危機(jī)是泛指在計(jì)算機(jī)軟件的開(kāi)發(fā)和維護(hù)過(guò)程中所遇到的一系列嚴(yán)重問(wèn)題2、軟件工程是指應(yīng)用于計(jì)算機(jī)軟件的定義、開(kāi)發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工序。它包括3個(gè)要素：方法、工具和過(guò)程。1軟件工程基本概念考點(diǎn)2：軟件生命周期（掌握）3個(gè)階段軟件定義階段：包括可行性研究與計(jì)劃制定、需求分析軟件開(kāi)發(fā)階段：包括軟件設(shè)計(jì)、軟件實(shí)現(xiàn)、軟件測(cè)試軟件運(yùn)行維護(hù)階段1軟件工程基本概念考點(diǎn)3：軟件工程的目標(biāo)與原則（了解）1、軟件工程研究的內(nèi)容包括：軟件開(kāi)發(fā)技術(shù)和軟件工程管理2、軟件工程的原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性、可驗(yàn)證性。1軟件工程基本概念考點(diǎn)4軟件開(kāi)發(fā)工具與軟件開(kāi)發(fā)環(huán)境（了解）1、工具：需求分析工具、設(shè)計(jì)工具、編碼工具、排錯(cuò)工具和測(cè)試工具等2、軟件開(kāi)發(fā)環(huán)境（軟件工程環(huán)境）：計(jì)算機(jī)輔助軟件工程（CASE：ComputerAidedSoftwareEngineering)舉例例1:軟件是指:A、程序B、程序和文檔C、算法加數(shù)據(jù)結(jié)構(gòu)D、程序、數(shù)據(jù)與相關(guān)文檔例2：下列選項(xiàng)中不屬于軟件生命周期開(kāi)發(fā)階段任務(wù)的是：A、軟件測(cè)試B、概要設(shè)計(jì)C、軟件維護(hù)D、詳細(xì)設(shè)計(jì)DC舉例例3：軟件生命周期分為多個(gè)階段，一般分為定義階段、開(kāi)發(fā)階段和維護(hù)階段。編碼和測(cè)試屬于

階段。例4：軟件工程的結(jié)構(gòu)化生命周期方法中，一般將軟件設(shè)計(jì)階段劃分為

和詳細(xì)設(shè)計(jì)兩個(gè)階段。開(kāi)發(fā)概要設(shè)計(jì)2結(jié)構(gòu)化分析方法考點(diǎn)1：需求分析階段需求分析階段的任務(wù)是確定：軟件系統(tǒng)功能軟件需求分析階段的工作分為：需求獲取、需求分析、編寫(xiě)需求規(guī)格說(shuō)明書(shū)及需求評(píng)審2結(jié)構(gòu)化分析方法考點(diǎn)2：結(jié)構(gòu)化分析方法（掌握）常用工具：數(shù)據(jù)流圖（DFD）、數(shù)據(jù)字典、判定樹(shù)、判定表數(shù)據(jù)流圖以圖形的方式描繪數(shù)據(jù)在系統(tǒng)中流動(dòng)和處理的過(guò)程。人事部門(mén)后勤部門(mén)工資計(jì)算出勤表業(yè)績(jī)表水電扣款表職工工資源點(diǎn)終點(diǎn)加工數(shù)據(jù)流2結(jié)構(gòu)化分析方法數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心，數(shù)據(jù)字典是對(duì)所有與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個(gè)有組織的列表，以及精確的、嚴(yán)格的定義，使得用戶(hù)和系統(tǒng)分析員對(duì)于輸入、輸出、存儲(chǔ)成分和中間結(jié)果有共同的理解，它所定義的對(duì)象都包含在數(shù)據(jù)流圖中。2結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析方法是面向數(shù)據(jù)流進(jìn)行需求分析的方法，采用自頂向下、逐層分解、建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型。舉例例1：軟件需求規(guī)格說(shuō)明書(shū)應(yīng)具有完整性、無(wú)歧義性、正確性、可驗(yàn)證性、可修改性等特性，其中最重要的是

。解析：軟件需求規(guī)格說(shuō)明書(shū)是確保軟件質(zhì)量的有力措施，衡量軟件需求規(guī)格說(shuō)明書(shū)質(zhì)量好壞的標(biāo)準(zhǔn)，其中最重要的就是正確性。例2：在結(jié)構(gòu)化分析使用的數(shù)據(jù)流圖（DFD）中，利用

對(duì)其中的圖形元素進(jìn)行確切解釋。正確性數(shù)據(jù)字典3結(jié)構(gòu)化設(shè)計(jì)方法考點(diǎn)1：軟件設(shè)計(jì)的基本原理基本原理：抽象、模塊化、信息隱蔽、模塊獨(dú)立性衡量模塊獨(dú)立性的兩個(gè)標(biāo)準(zhǔn)：（1）內(nèi)聚性：是度量模塊功能強(qiáng)度的指標(biāo)，包括（由弱到強(qiáng)）：偶然內(nèi)聚、邏輯內(nèi)聚、時(shí)間內(nèi)聚、過(guò)程內(nèi)聚、通信內(nèi)聚、順序內(nèi)聚、功能內(nèi)聚（2）耦合性：是度量模塊之間的相互聯(lián)系程度。分為（耦合度由高到低）：內(nèi)容耦合、公共耦合、外部耦合、控制耦合、標(biāo)記耦合、數(shù)據(jù)耦合、非直接耦合3結(jié)構(gòu)化設(shè)計(jì)方法考點(diǎn)2：概要設(shè)計(jì)1、概要設(shè)計(jì)基本任務(wù)：設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)設(shè)計(jì)、編寫(xiě)概要設(shè)計(jì)文檔、概要設(shè)計(jì)文檔評(píng)審2、常用的軟件結(jié)構(gòu)設(shè)計(jì)工具是結(jié)構(gòu)圖；在程序結(jié)構(gòu)圖中，模塊用一個(gè)矩形表示，矩形內(nèi)注明模塊功能和名字；箭頭表示模塊間的調(diào)用關(guān)系。用帶實(shí)心圓的箭頭表示傳遞的是控制信息，用帶空心圓的箭頭表示傳遞的是數(shù)據(jù)。3結(jié)構(gòu)化設(shè)計(jì)方法3、面向數(shù)據(jù)流的設(shè)計(jì)方法---數(shù)據(jù)流的類(lèi)型：變換型、事務(wù)型信息流輸入流輸出流變換流內(nèi)部表示外部表示信息時(shí)間變換型數(shù)據(jù)流圖將變換型映射成結(jié)構(gòu)圖，稱(chēng)為變換分析3結(jié)構(gòu)化設(shè)計(jì)方法通路事務(wù)事務(wù)中心事務(wù)型數(shù)據(jù)流圖將事務(wù)型映射成結(jié)構(gòu)圖，稱(chēng)為事務(wù)分析3結(jié)構(gòu)化設(shè)計(jì)方法考點(diǎn)3：詳細(xì)設(shè)計(jì)常用工具：程序流程圖N-S圖PAD圖（問(wèn)題分析圖：ProblemAnalysisDiagram)過(guò)程設(shè)計(jì)語(yǔ)言PDL舉例例1：模塊獨(dú)立性是軟件模塊化所提出的要求，衡量模塊獨(dú)立性的度量標(biāo)準(zhǔn)是A、抽象和信息隱蔽B、局部化和封裝化C、內(nèi)聚性和耦合性D、激活機(jī)制和控制方法例2：在概要設(shè)計(jì)階段，設(shè)計(jì)軟件結(jié)構(gòu)一般不確定A、模塊的功能B、模塊間的調(diào)用關(guān)系C、模塊之間的接口D、模塊內(nèi)的局部數(shù)據(jù)CD4軟件測(cè)試考點(diǎn)1：軟件測(cè)試的目的軟件測(cè)試的指用人工或自動(dòng)手段來(lái)運(yùn)行或測(cè)定某個(gè)系統(tǒng)的過(guò)程，其目的在于檢驗(yàn)它是否滿(mǎn)足規(guī)定的需求或是弄清預(yù)期結(jié)果與實(shí)際結(jié)果之間的差別。簡(jiǎn)單地說(shuō)，軟件測(cè)試的目的是盡可能多地發(fā)現(xiàn)程序中的錯(cuò)誤。4軟件測(cè)試考點(diǎn)2：軟件測(cè)試技術(shù)與方法1、靜態(tài)測(cè)試與動(dòng)態(tài)測(cè)試靜態(tài)測(cè)試：一般是指人工評(píng)審軟件文檔或程序，以發(fā)現(xiàn)其中的錯(cuò)誤。有代碼檢查、靜態(tài)結(jié)構(gòu)分析和代碼質(zhì)量度量等動(dòng)態(tài)測(cè)試：上機(jī)測(cè)試；分為白盒測(cè)試和黑盒測(cè)試4軟件測(cè)試2、白盒測(cè)試（結(jié)構(gòu)測(cè)試或邏輯驅(qū)動(dòng)測(cè)試）---根據(jù)軟件產(chǎn)品的內(nèi)部過(guò)程，檢查內(nèi)部成分，以確定每種內(nèi)部操作是否符合設(shè)計(jì)規(guī)格要求白盒測(cè)試的方法主要有：邏輯覆蓋、基本路徑測(cè)試等。主要用于軟件的單元測(cè)試。白盒測(cè)試的原則之一是保證所測(cè)模塊中每一個(gè)獨(dú)立路徑至少要執(zhí)行一次．4軟件測(cè)試3、黑盒測(cè)試（功能測(cè)試或數(shù)據(jù)驅(qū)動(dòng)測(cè)試）---對(duì)軟件已經(jīng)實(shí)現(xiàn)的功能是否滿(mǎn)足需求進(jìn)行測(cè)試和驗(yàn)證。黑盒測(cè)試不關(guān)心程序內(nèi)部的邏輯，只是根據(jù)程序的功能說(shuō)明來(lái)設(shè)計(jì)測(cè)試用例。黑盒測(cè)試的主要方法有：等價(jià)類(lèi)劃分法、邊界值分析法、錯(cuò)誤推測(cè)法和因果圖。主要用于軟件的確認(rèn)測(cè)試。4軟件測(cè)試軟件測(cè)試過(guò)程分為4個(gè)步驟：?jiǎn)卧獪y(cè)試、集成測(cè)試、驗(yàn)收測(cè)試（或確認(rèn)測(cè)試）和系統(tǒng)測(cè)試舉例例1：軟件測(cè)試分為白盒測(cè)試和黑盒測(cè)試。等價(jià)類(lèi)劃分屬于

測(cè)試。解析：軟件測(cè)試的方法有3種：動(dòng)態(tài)測(cè)試、靜態(tài)測(cè)試和正確性證明。設(shè)計(jì)測(cè)試實(shí)例的方法一般有兩種：黑盒測(cè)試方法和白盒測(cè)試方法。黑盒測(cè)試方法主要有：等價(jià)類(lèi)劃分法、邊界值分析法、錯(cuò)誤推測(cè)法、因果圖等，主要用于軟件確認(rèn)測(cè)試。黑盒舉例例2：下列敘述中正確的是A、軟件測(cè)試的主要目的是發(fā)現(xiàn)程序中的錯(cuò)誤B、軟件測(cè)試的主要目的是確定程序中錯(cuò)誤的位置C、為了提高軟件測(cè)試的效率，最好由程序編制者自己來(lái)完成軟件測(cè)試的工作D、軟件測(cè)試是證明軟件沒(méi)有錯(cuò)誤A舉例例3：在兩種基本測(cè)試方法中，

測(cè)試的原則之一是保證所測(cè)模塊中每一個(gè)獨(dú)立路徑至少要執(zhí)行一次。白盒5程序的調(diào)試考點(diǎn)1：基本概念程序調(diào)試的基本步驟：錯(cuò)誤定位---修改設(shè)計(jì)和代碼---進(jìn)行回歸測(cè)試，防止引進(jìn)新的錯(cuò)誤。5程序的調(diào)試考點(diǎn)2：軟件調(diào)試方法1、強(qiáng)行排錯(cuò)法：設(shè)置斷點(diǎn)、程序暫停、觀(guān)察程序狀態(tài)、繼續(xù)運(yùn)行程序2、回溯法：適合于小規(guī)模程序的排錯(cuò)3、原因排除法：通過(guò)演繹和歸納及二分法實(shí)現(xiàn)舉例例1：軟件調(diào)試的目的是A、發(fā)現(xiàn)錯(cuò)誤B、更正錯(cuò)誤C、改善軟件性能D、驗(yàn)證軟件的正確性例2：

的任務(wù)是診斷和改正程序中的錯(cuò)誤。程序調(diào)試B數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)---二級(jí)考試公共基礎(chǔ)知識(shí)之四1數(shù)據(jù)庫(kù)系統(tǒng)的基本概念考點(diǎn)1：數(shù)據(jù)、數(shù)據(jù)庫(kù)和數(shù)據(jù)庫(kù)管理系統(tǒng)1、數(shù)據(jù)有型與值之分：數(shù)據(jù)的型給出了數(shù)據(jù)的類(lèi)型，如整型、實(shí)型、字符型等。2、數(shù)據(jù)庫(kù)(DB，Database):數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式，并存入于統(tǒng)一的存儲(chǔ)介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個(gè)應(yīng)用程序所共享。3、數(shù)據(jù)庫(kù)管理系統(tǒng)(DBMS,DatabaseManagementSystem)：是一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫(kù)中數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護(hù)、控制、保護(hù)和數(shù)據(jù)服務(wù)等。1數(shù)據(jù)庫(kù)系統(tǒng)的基本概念DBMS的功能：DBMS是數(shù)據(jù)庫(kù)系統(tǒng)的核心，有以下幾個(gè)方面的功能：數(shù)據(jù)模式定義、數(shù)據(jù)存取的物理構(gòu)建、數(shù)據(jù)操縱、數(shù)據(jù)的完整性、安全性定義與檢查、數(shù)據(jù)庫(kù)的并發(fā)控制與故障恢復(fù)、數(shù)據(jù)的服務(wù)。數(shù)據(jù)語(yǔ)言：數(shù)據(jù)定義語(yǔ)言（DDL）、數(shù)據(jù)操縱語(yǔ)言（DML）、數(shù)據(jù)控制語(yǔ)言（DCL）4、數(shù)據(jù)庫(kù)系統(tǒng)（DBS，DatabaseSystem）包括：數(shù)據(jù)庫(kù)（數(shù)據(jù)）、數(shù)據(jù)庫(kù)管理系統(tǒng)、數(shù)據(jù)庫(kù)管理員、系統(tǒng)平臺(tái)之一---硬件平臺(tái)、系統(tǒng)平臺(tái)之一---軟件平臺(tái)。1數(shù)據(jù)庫(kù)系統(tǒng)的基本概念考點(diǎn)2：數(shù)據(jù)庫(kù)系統(tǒng)的發(fā)展數(shù)據(jù)管理發(fā)展至今已經(jīng)歷了人工管理階段、文件系統(tǒng)階段、數(shù)據(jù)庫(kù)系統(tǒng)階段（分布式數(shù)據(jù)庫(kù)系統(tǒng)階段）3個(gè)階段考點(diǎn)3：數(shù)據(jù)庫(kù)系統(tǒng)的基本特點(diǎn)數(shù)據(jù)的集成性、數(shù)據(jù)的高共享性與低冗余性、數(shù)據(jù)獨(dú)立性（物理獨(dú)立性與邏輯獨(dú)立性）、數(shù)據(jù)統(tǒng)一管理與控制（數(shù)據(jù)的完整性檢查、數(shù)據(jù)的安全性保護(hù)、并發(fā)控制）考點(diǎn)4：數(shù)據(jù)獨(dú)立性（物理/邏輯獨(dú)立性）指程序與數(shù)據(jù)互不依賴(lài)，即數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)與存取方式的改變不會(huì)影響應(yīng)用程序。1數(shù)據(jù)庫(kù)系統(tǒng)的基本概念考點(diǎn)5：數(shù)據(jù)庫(kù)系統(tǒng)的內(nèi)部結(jié)構(gòu)體系數(shù)據(jù)庫(kù)的三級(jí)模式：概念模式、外模式、內(nèi)模式概念模式---數(shù)據(jù)庫(kù)系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，是一種抽象的描述，與具體的硬件環(huán)境與平臺(tái)、具體的軟件環(huán)境無(wú)關(guān)。外模式---用戶(hù)模式，是用戶(hù)所看到和理解的數(shù)據(jù)庫(kù)內(nèi)模式---物理模式/存儲(chǔ)模式，給出了數(shù)據(jù)庫(kù)物理存儲(chǔ)結(jié)構(gòu)與物理存取方法舉例例1：下列敘述中正確的是A、數(shù)據(jù)庫(kù)系統(tǒng)是一個(gè)獨(dú)立的系統(tǒng)，不需要操作系統(tǒng)的支持B、數(shù)據(jù)庫(kù)技術(shù)的根本目標(biāo)是解決數(shù)據(jù)的共享問(wèn)題C、數(shù)據(jù)庫(kù)管理系統(tǒng)就是數(shù)據(jù)庫(kù)系統(tǒng)D、以上3種說(shuō)法都不對(duì)B舉例例2：在數(shù)據(jù)庫(kù)系統(tǒng)中，用戶(hù)所見(jiàn)的數(shù)據(jù)模式為

。例3：數(shù)據(jù)獨(dú)立性分為邏輯獨(dú)立性和物理獨(dú)立性。當(dāng)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)改變時(shí)，其邏輯結(jié)構(gòu)可以不