二級VF考試大綱

1、二級VF考試大綱基 本 要 求 （1）掌握算法的基本概念。 （2）掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作。 （3）掌握基本排序和查找算法。 （4）掌握逐步求精的結(jié)構(gòu)化程序設(shè)計方法。 （5）掌握軟件工程的基本方法，具有初步應(yīng)用相關(guān)技術(shù)進行軟件開發(fā)的能力。 （6）掌握數(shù)據(jù)庫的基本知識，了解關(guān)系數(shù)據(jù)庫的設(shè)計。 考 試 內(nèi) 容 1. 基本數(shù)據(jù)結(jié)構(gòu)與算法 （1）算法的基本概念：算法復(fù)雜度的概念和意義（時間復(fù)雜度與空間復(fù)雜度）。 （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）棧和隊列的定義：棧和隊列的順序

2、存儲結(jié)構(gòu)及其基本運算。 （5）線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運算。 （6）樹的基本概念：二叉樹的定義及其存儲結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。 （7）順序查找與二分法查找算法：基本排序算法（交換類排序，選擇類排序，插入類排序）。 2. 程序設(shè)計基礎(chǔ) （1）程序設(shè)計方法與風(fēng)格。 （2）結(jié)構(gòu)化程序設(shè)計。 （3）面向?qū)ο蟮某绦蛟O(shè)計方法，對象，方法，屬性及繼承與多態(tài)性。 3. 軟件工程基礎(chǔ) （1）軟件工程基本概念，軟件生命周期概念，軟件工具與軟件開發(fā)環(huán)境。 （2）結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。 （3）結(jié)構(gòu)化設(shè)計方法，總體設(shè)計與詳細(xì)設(shè)計。 （4）軟件測試的方法，

3、白盒測試與黑盒測試，測試用例設(shè)計，軟件測試的實施，單元測試、集成測試和系統(tǒng)測試。 （5）程序的調(diào)試，靜態(tài)調(diào)試與動態(tài)調(diào)試。 4. 數(shù)據(jù)庫設(shè)計基礎(chǔ) （1）數(shù)據(jù)庫的基本概念：數(shù)據(jù)庫，數(shù)據(jù)庫管理系統(tǒng)，數(shù)據(jù)庫系統(tǒng)。 （2）數(shù)據(jù)模型：實體聯(lián)系模型及E-R圖，從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。 （3）關(guān)系代數(shù)運算：包括集合運算及選擇、投影、連接運算，數(shù)據(jù)庫規(guī)范化理論。 （4）數(shù)據(jù)庫設(shè)計方法和步驟：需求分析、概念設(shè)計、邏輯設(shè)計和物理設(shè)計的相關(guān)策略。 考 試 方 式 （1）公共基礎(chǔ)知識的考試方式為筆試，與C語言程序設(shè)計（C+語言程序設(shè)計、Java語言程序設(shè)計、Visual Basic語言程序設(shè)計、Visual Fox

4、Pro數(shù)據(jù)庫程序設(shè)計、Access數(shù)據(jù)庫程序設(shè)計或Delphi語言程序設(shè)計）的筆試部分合為一張試卷。公共基礎(chǔ)知識部分占全卷的30分。 （2）公共基礎(chǔ)知識有10道選擇題和5道填空題。 二級Visual FoxPro數(shù)據(jù)庫程序設(shè)計考試大綱 基 本 要 求 （1）具有數(shù)據(jù)庫系統(tǒng)的基本知識。 （2）基本了解面向?qū)ο蟮母拍睢?（3）掌握關(guān)系數(shù)據(jù)庫的基本原理。 （4）掌握數(shù)據(jù)庫程序設(shè)計方法。 （5）能夠使用Visual FoxPro建立一個小型數(shù)據(jù)庫應(yīng)用系統(tǒng)。 考 試 內(nèi) 容 1 .Visual FoxPro基礎(chǔ)知識 1）基本概念：數(shù)據(jù)庫，數(shù)據(jù)模型，數(shù)據(jù)庫管理系統(tǒng)，類和對象，事件，方法。 2）關(guān)系數(shù)據(jù)庫：

5、 （1）關(guān)系數(shù)據(jù)庫：關(guān)系模型，關(guān)系模式，關(guān)系，元組，屬性，域，主關(guān)鍵字和外部關(guān)鍵字。 （2）關(guān)系運算：選擇，投影，連接。 （3）數(shù)據(jù)的一致性和完整性：實體完整性，域完整性，參照完整性。 3）Visual FoxPro系統(tǒng)特點與工作方式： （1）Windows版本數(shù)據(jù)庫的特點。 （2）數(shù)據(jù)類型和主要文件類型。 （3）各種設(shè)計器和向?qū)А?（4）工作方式：交互方式（命令方式，可視化操作）和程序運行方式。 4）Visual FoxPro的基本數(shù)據(jù)元素： （1）常量，變量，表達(dá)式。 （2）常用函數(shù):字符處理函數(shù)，數(shù)值計算函數(shù)，日期時間函數(shù)，數(shù)據(jù)類型轉(zhuǎn)換函數(shù)，測試函數(shù)。 2. Visual FoxPro數(shù)

6、據(jù)庫的基本操作 1）數(shù)據(jù)庫和表的建立、修改與有效性檢驗： （1）表結(jié)構(gòu)的建立與修改。 （2）表記錄的瀏覽、增加、刪除與修改。 （3）創(chuàng)建數(shù)據(jù)庫，向數(shù)據(jù)庫添加或移出表。 （4）設(shè)定字段級規(guī)則和記錄級規(guī)則。 （5）表的索引：主索引，候選索引，普通索引，惟一索引。 2）多表操作： （1）選擇工作區(qū)。 （2）建立表之間的關(guān)聯(lián)，一對一的關(guān)聯(lián)，一對多的關(guān)聯(lián)。 （3）設(shè)置參照完整性。 （4）建立表間臨時關(guān)聯(lián)。 3）建立視圖與數(shù)據(jù)查詢： （1）查詢文件的建立、執(zhí)行與修改。 （2）視圖文件的建立、查看與修改。 （3）建立多表查詢。 （4）建立多表視圖。 3 .關(guān)系數(shù)據(jù)庫標(biāo)準(zhǔn)語言SQL 1）SQL的數(shù)據(jù)定義功能：

7、 （1）CREATE TABLE-SQL。 （2）ALTER TABLE-SQL。 2）SQL的數(shù)據(jù)修改功能： （1）DELETE-SQL。 （2）INSERT-SQL。 （3）UPDATE-SQL。 3）SQL的數(shù)據(jù)查詢功能： （1）簡單查詢。 （2）嵌套查詢。 （3）連接查詢。 內(nèi)連接 外連接：左連接，右連接，完全連接 4）分組與計算查詢。 5）集合的并運算。 4 .項目管理器、設(shè)計器和向?qū)У氖褂?1）使用項目管理器： （1）使用“數(shù)據(jù)”選項卡。 （2）使用“文檔”選項卡。 2）使用表單設(shè)計器： （1）在表單中加入和修改控件對象。 （2）設(shè)定數(shù)據(jù)環(huán)境。 3）使用菜單設(shè)計器： （1）建立主選

8、項。 （2）設(shè)計子菜單。 （3）設(shè)定菜單選項程序代碼。 4）使用報表設(shè)計器： （1）生成快速報表。 （2）修改報表布局。 （3）設(shè)計分組報表。 （4）設(shè)計多欄報表。 5）使用應(yīng)用程序向?qū)А?6）應(yīng)用程序生成器與連編應(yīng)用程序。 5. Visual FoxPro程序設(shè)計 1）命令文件的建立與運行： （1）程序文件的建立。 （2）簡單的交互式輸入、輸出命令。 （3）應(yīng)用程序的調(diào)試與執(zhí)行。 2）結(jié)構(gòu)化程序設(shè)計： （1）順序結(jié)構(gòu)程序設(shè)計。 （2）選擇結(jié)構(gòu)程序設(shè)計。 （3）循環(huán)結(jié)構(gòu)程序設(shè)計。 3）過程與過程調(diào)用： （1）子程序設(shè)計與調(diào)用。 （2）過程與過程文件。 （3）局部變量和全局變量，過程調(diào)用中的參數(shù)

9、傳遞。 4）用戶定義對話框（MESSAGEBOX）的使用。 考 試 方 式 （1）筆試：90分鐘，滿分100分，其中含公共基礎(chǔ)知識部分的30分。 （2）上機操作：90分鐘，滿分100分。 基本操作。簡單應(yīng)用。綜合應(yīng)用。數(shù)據(jù)庫語言程序設(shè)計(Visual FoxPro)一、數(shù)據(jù)庫基礎(chǔ)知識1基本概念(1) 數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)、數(shù)據(jù)庫系統(tǒng)(2) 三種數(shù)據(jù)庫模型：關(guān)系模型、網(wǎng)(3) VFP的命令格式(4) 兩種工作方式：交互方式（命令操作和可視化操作）、程序運行方式(5) 輔助設(shè)計工具：向?qū)А⒃O(shè)計器、生成器與項目管理器2VFP的數(shù)據(jù)元素 (1) 常量：數(shù)值型、字符型、邏輯型、日期型常量(2) 變量：

10、字段變量、簡單內(nèi)存變量、數(shù)組；內(nèi)存變量的保存與恢復(fù)；數(shù)組的定義(3) 變量類型：數(shù)值型、字符型、邏輯型、日期型、備注型、通用型等(4) 表達(dá)式：表達(dá)式的類型及運算順序(5) 常用函數(shù)： 數(shù)值計算函數(shù)：ABS( )、INT( )、SQRT( )、MAX( )、MIN( )、ROUND( )、MOD( )等。字符處理函數(shù)：&、ALLTRIM( )、TRIM()、LTRM()、SUBSTR( )、LEFT( )、RIGHT( )、LEN( )、AT( )、SPACE( )、UPPER( )、LOWER( )等。數(shù)據(jù)類型轉(zhuǎn)換函數(shù)：CTOD( )、DTOC( ) 、VAL( )、STR( )、C

11、HR( )、ASC( )等。日期處理函數(shù)：DATE( )、TIME( )、DAY( )、DOW( )、MONTH( )、YEAR( )等。測試函數(shù)：BOF( )、EOF( )、RECNO( )、FOUND( )、SELECT( )、DELETE( )、TYPE( )等。其它函數(shù)：ROW( )、COL( )、INKEY( )、READKEY( )等。三、數(shù)據(jù)庫的基本操作1表與數(shù)據(jù)庫的概念2表的建立、顯示、修改與復(fù)制(1) 表結(jié)構(gòu)的建立、顯示、修改與復(fù)制(2) 表的打開與關(guān)閉(3) 表中記錄的輸入、定位、顯示、增加、刪除、修改與復(fù)制(4) 數(shù)據(jù)過濾（記錄過濾與字段過濾）3排序、查詢與統(tǒng)計計算 (1

12、) 索引與排序 (2) 條件查詢與索引查詢 (3) 統(tǒng)計：統(tǒng)計記錄個數(shù)、求和、求均值、分類匯總4工作區(qū)與表之間的關(guān)聯(lián) (1) 工作區(qū)的選擇 (2) 建立多表之間的關(guān)聯(lián)（一對一的關(guān)聯(lián)、一對多的關(guān)聯(lián)）5表中數(shù)據(jù)與數(shù)組之間的傳遞6數(shù)據(jù)庫 (1) 建立、打開、修改、刪除數(shù)據(jù)庫 (2) 數(shù)據(jù)庫中表的添加與移去 (3) 數(shù)據(jù)庫表的特殊操作（設(shè)置字段的有效性規(guī)則、默認(rèn)值、記錄規(guī)則等） (4) 建立表間的永久關(guān)系；設(shè)置參照完整性7使用設(shè)計器建立視圖四、結(jié)構(gòu)化查詢語言SQL1. SQL的數(shù)據(jù)定義功能（CREATE TABLE-SQL、ALTER TABLE-SQL、DROP TABLE-SQL）2. SQL的數(shù)

13、據(jù)更新功能（INSERT-SQL、DELETE-SQL、UPDATE-SQL）3SQL的查詢功能（SELECT-SQL）：簡單查詢、條件查詢、統(tǒng)計查詢、分組查詢、查詢排序、連接查詢、嵌套查詢、查詢結(jié)果的輸出4使用設(shè)計器建立查詢五、結(jié)構(gòu)化程序設(shè)計1程序文件的建立與執(zhí)行。2程序文件中常用的命令：輸入類命令；輸出類命令；注釋命令；中止程序執(zhí)行命令等。3程序的三種基本結(jié)構(gòu) (1)順序結(jié)構(gòu)。 (2)選擇結(jié)構(gòu)：條件選擇語句IF-ELSE-ENDIF及其嵌套形式的使用；多分支選擇語句DOCASE-ENDCASE的使用。 (3)循環(huán)結(jié)構(gòu)：條件循環(huán)語句DO WHILE-ENDDO、計數(shù)循環(huán)語句FOR-ENDFO

14、R、表循環(huán)語句SCAN-ENDSCAN及其嵌套形式的使用。4. 子程序與過程 (1) 子程序的設(shè)計與調(diào)用。 (2) 過程文件的結(jié)構(gòu)與使用。 (3) 自定義函數(shù)的定義與調(diào)用。 (4) 局部變量、全局變量與變量的作用域；過程調(diào)用中的參數(shù)傳遞。六、Visual FoxPro的可視化程序設(shè)計1面向?qū)ο蟮某绦蛟O(shè)計方法：基本概念、對象和類、對象的屬性、事件和方法。2表單設(shè)計 (1) 表單向?qū)c表單設(shè)計器。 (2) 表單控件設(shè)計：標(biāo)簽、圖象、線條、形狀；文本框、編輯框、列表框、組合框、微調(diào)控件；命令按鈕與命令按鈕組、復(fù)選框、選項按鈕組、計時器；表格、頁框、容器等。 (3) 表單的建立、運行及事件驅(qū)動編程。3

15、使用菜單設(shè)計器設(shè)計菜單：下拉式菜單與彈出式菜單。4使用報表設(shè)計器設(shè)計報表。七、上機考試1表設(shè)計器、數(shù)據(jù)庫設(shè)計器、查詢設(shè)計器、視圖設(shè)計器、報表設(shè)計器、菜單設(shè)計器、表單設(shè)計器、項目管理器等的基本操作。2表與數(shù)據(jù)庫的基本操作。3結(jié)構(gòu)化程序設(shè)計（表的查詢、統(tǒng)計、修改、輸出），按要求編寫、修改并運行程序。4表單設(shè)計5菜單設(shè)計6. 創(chuàng)建視圖和查詢（使用設(shè)計器）考試內(nèi)容軟件技術(shù)基礎(chǔ)一、掌握程序設(shè)計常用的數(shù)據(jù)結(jié)構(gòu)與算法1數(shù)據(jù)結(jié)構(gòu)與算法的基本概念2線性表的基本操作及存儲結(jié)構(gòu)3棧、隊列、鏈表的定義、操作及存儲結(jié)構(gòu)4樹、二叉樹和圖的概念5線性表的查找：順序查找、二分法查找、分塊查找6內(nèi)排序：插入排序、選擇排序、變換

16、排序、歸并排序二、了解軟件工程的基本思想及軟件開發(fā)技術(shù)1程序、軟件、軟件工具、軟件工程的概念2軟件的生存期和開發(fā)模型3結(jié)構(gòu)化分析方法（SA方法）、結(jié)構(gòu)化設(shè)計方法（SD方法）、結(jié)構(gòu)化程序設(shè)計（SP）的概念、任務(wù)和實現(xiàn)方法。結(jié)構(gòu)化程序設(shè)計的主要圖示工具（程序流程圖、方框圖、問題分析圖）及偽代碼。4面向?qū)ο笙到y(tǒng)的基本概念：類、對象、方法、消息、繼承、多態(tài)性5面向?qū)ο蟪绦蛟O(shè)計與結(jié)構(gòu)化程序設(shè)計的主要區(qū)別6基于構(gòu)件的軟件開發(fā)方法及軟件復(fù)用的概念7軟件測試的概念及基本方法三、熟悉計算機軟件開發(fā)的支撐環(huán)境操作系統(tǒng)1操作系統(tǒng)的功能和類型2進程及處理機管理：進程、進程的通訊、進程控制、進程調(diào)度及死鎖等基本概念3存

17、儲管理、設(shè)備管理、文件管理的基本任務(wù)和方法 2011年計算機等級考試二級公共基礎(chǔ)考前背誦版 下面分為四個部分進行組織。文中標(biāo)注了三個星號的，表示非常重要，基本每次考試都是必考；標(biāo)注了兩個星號或一個星號的，表示也較重要，很容易考到。出現(xiàn)在【】括號中的內(nèi)容，表示要很精確的背下來的。整個文檔中的五頁，建議考前都要認(rèn)真的記憶。第一部分 算法與數(shù)據(jù)結(jié)構(gòu) (歷年比例41%)1、算法 問題處理方案的正確而完整的描述稱為【算法】。算法分析的目的是，分析算法的效率以求改進。算法的基本特征是【可行性】、【確定性】、【有窮性】和擁有足夠情報。 算法的有窮性是指：算法程序的運行時間是有限的。算法的復(fù)雜度是衡量算法好壞

18、的度量，分為【時間復(fù)雜度】和【空間復(fù)雜度】。 時間復(fù)雜度是指執(zhí)行算法所需要的【計算工作量】；算法的空間復(fù)雜度是指算法執(zhí)行過程中所需的【存儲空間】。 算法時間復(fù)雜度或空間復(fù)雜度中的一項的值，沒有辦法推出另一項的值。2、數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)分為【邏輯結(jié)構(gòu)】和【存儲結(jié)構(gòu)】。線性結(jié)構(gòu)和非線性結(jié)構(gòu)屬于邏輯結(jié)構(gòu)；順序、鏈?zhǔn)?、索引屬于存儲結(jié)構(gòu)(物理結(jié)構(gòu))。循環(huán)隊列屬于【存儲結(jié)構(gòu)】。 數(shù)據(jù)的存儲結(jié)構(gòu)又稱為物理結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式。 一個邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)影響數(shù)據(jù)處理的效率。程序執(zhí)行的效率與數(shù)據(jù)的存儲結(jié)構(gòu)密切相關(guān)。 數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈的隊列

19、屬于【線性結(jié)構(gòu)】。 線性表的存儲結(jié)構(gòu)主要分為順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。順序存儲結(jié)構(gòu)的存儲一定是連續(xù)的，鏈?zhǔn)酱鎯Φ拇鎯臻g不一定是連續(xù)的。 有序線性表既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。 隊列是一種特殊的線性表，循環(huán)隊列按照【先進先出】原則組織數(shù)據(jù)。循環(huán)隊列是隊列的【順序】存儲結(jié)構(gòu)。 數(shù)據(jù)的獨立性分為【物理獨立】性和【邏輯獨立性】。當(dāng)數(shù)據(jù)的存儲結(jié)構(gòu)改變時，其邏輯結(jié)構(gòu)可以不變，因此，基于邏輯結(jié)構(gòu)的應(yīng)用程序可以不用修改，稱為【物理獨立性】。3、棧和隊列 棧是一種特殊的線性表，是只能在一端進行插入和刪除的線性表，特點是FILO(First In Last Out)。 棧是【先進后出】的線

20、性表；棧具有記憶作用；對棧的插入與刪除操作中，不需要改變【棧底指針】。假定讓元素1、2、3、A、B依次入棧，則出棧的順序是：B、A、3、2、1。 棧與隊列都是線性結(jié)構(gòu)，樹是非線性結(jié)構(gòu)。支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是【棧】。 棧與隊列的共同點是，都只允許在【端點處】插入和刪除元素。 棧只能順序存儲的描述是錯誤的。?？梢杂小卷樞蚝玩?zhǔn)健績煞N存儲方式。 隊列是允許在一段插入，在另一端進行刪除的線性表，其特點是【先進先出】。 循環(huán)隊列中元素的個數(shù)是由隊頭指針和隊尾指針共同決定。循環(huán)隊列的頭指針為front，尾指針為rear，容量為maxSize，則循環(huán)隊列中元素的個數(shù)是【 (rear-front+maxS

21、ize) mod maxSize】。4、線性鏈表 線性鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。用鏈表表示線性表的優(yōu)點是【便于插入和刪除操作】。 線性鏈表的存儲空間不一定連續(xù)，且個元素的存儲順序是任意的。5、樹與二叉樹 在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件（繼）的個數(shù)稱為該結(jié)點的度，所有結(jié)點中最大的度稱為樹的度。二叉樹各結(jié)點的度只可能取值0、1、2，不可能是其它值。換言之，知道了度為1結(jié)點數(shù)量的前提下，葉子結(jié)點或度為2的結(jié)點中知道其一，就可以求出總的結(jié)點數(shù)。下面關(guān)于計算結(jié)點數(shù)量的幾個性質(zhì)，非常重要：(1)對任意的二叉樹，葉子結(jié)點的數(shù)量，比度為2的結(jié)點數(shù)量多一個(換言之，已知葉子結(jié)點的數(shù)量，減去1則是度為2的結(jié)點

22、數(shù)量；已知度為2的結(jié)點數(shù)量，加上1就是葉子結(jié)點數(shù)量)(2)完全二叉樹如果有N個結(jié)點，當(dāng)N為奇數(shù)的時候，葉子結(jié)點數(shù)為(N+1)/2，此時二叉樹只有度為0的葉子結(jié)點及度為2的結(jié)點，沒有度為1的結(jié)點；當(dāng)N為偶數(shù)的時候，葉子結(jié)點的數(shù)量為N/2。(注意條件，必須是完全二叉樹，當(dāng)然包括滿二叉樹)(3)滿二叉樹第K層上的結(jié)點數(shù)量為2K-1；深度為K的滿二叉樹，結(jié)點總數(shù)為2K-1。 上述的計算公式，關(guān)鍵要能夠應(yīng)用，例如，深度為7的滿二叉樹，度為2的結(jié)點數(shù)量是多少？既然是滿二叉樹，葉子結(jié)點的數(shù)量就是第7層的結(jié)點數(shù)量，也就是26，可以算出葉子結(jié)點為64，因此度為2的結(jié)點數(shù)是63(葉子結(jié)點數(shù)減去1)。 二叉樹的前序

23、遍歷、中序遍歷、后續(xù)遍歷：前中后三個詞是相對于根來講的，前序是【根->左->右】，中序是【左->根->右】，后續(xù)是【左->右->根】。具體操作為：先序遍歷(D L R): 訪問根結(jié)點，按先序遍歷左子樹，按先序遍歷右子樹。中序遍歷(L D R): 按中序遍歷左子樹，訪問根結(jié)點，按中序遍歷右子樹。后序遍歷(L R D): 按后序遍歷左子樹，按后序遍歷右子樹，訪問根結(jié)點。下面以中序遍歷為例，來講解實際的解題方法：對一棵樹，將根結(jié)點下的左子樹用一個橢圓圈起來，右子樹也用一個橢圓圈起來。之后，在左子樹上標(biāo)記上1，在根結(jié)點標(biāo)記上2，在右子樹上標(biāo)記上3。對在左邊橢圓內(nèi)的左

24、子樹，現(xiàn)在把它單獨拿出來分析。把它的左子樹圈起來標(biāo)上1.1，根結(jié)點標(biāo)記上1.2，右子樹標(biāo)上1.3。按照上述方法依次往下，直到樹不能拆分，然后按照“左->根->右”的順序?qū)懗鼋Y(jié)點的訪問先后即可。6、查找技術(shù) 對于長度為n的線性表，順序查找最壞情況下需要比較n次。(對數(shù)據(jù)是否有序沒有要求)。 順序查找最好情況下查詢次數(shù)是1，最壞情況下是n，平均為(1+n)/2。 對于長度為n的有序線性表，二分法最壞情況下只需要比較log2n次。(數(shù)據(jù)必須有序) 能用二分法進行查找的是【順序存儲的有序線性表】。7、排序技術(shù) 對于長度為n的線性表，【冒泡排序、快速排序、簡單插入排序、簡單選擇排序】這四種排

25、序方式在最壞情況下的比較次數(shù)相同，都是【n(n-1)/2】。堆排序的效率最高，是【nlog2n】。 希爾排序最壞情況下需要次比較【n1.5】。希爾排序?qū)儆凇静迦腩惻判蚍ā俊?已知數(shù)據(jù)表A中每個元素距最終位置不遠(yuǎn)，為節(jié)省時間，應(yīng)該采用的算法是【直接插入排序】。選擇排序、插入排序、快速排序、歸并排序中對內(nèi)存要求最大的是【歸并排序】。第二部分 軟件工程基礎(chǔ) (歷年比例27%)1、軟件工程基本概念 軟件是包括【程序】、【數(shù)據(jù)】及【相關(guān)文檔】的完整集合，軟件是一種邏輯產(chǎn)品。軟件工程三要素包括【方法、工具和過程】，其中【過程】支持軟件開發(fā)的各個環(huán)節(jié)的控制和管理。 軟件工程的核心思想：把軟件產(chǎn)品當(dāng)作是一個工

26、程產(chǎn)品來處理，強調(diào)在軟件開發(fā)過程中應(yīng)用【工程化】原則。 從工程管理角度，軟件設(shè)計一般分為兩步完成，它們是【概要設(shè)計】和【詳細(xì)設(shè)計】。 軟件生命周期可分為多個階段，一般分為【定義】階段、【開發(fā)】階段和【維護】階段，編碼和測試屬于【開發(fā)階段】 需求分析階段產(chǎn)生的主要文檔是【軟件需求規(guī)格說明書】。軟件需求的規(guī)格說明書應(yīng)該有完整性、無歧義性、正確性、可驗證性、可修改性等特征，其中最重要的是【正確性】。2、結(jié)構(gòu)化分析與設(shè)計 需求分析的分發(fā)有：【結(jié)構(gòu)化】需求分析方法，【面向?qū)ο蟆康姆治龇椒?。DFD是【需求分析階段】可以使用的工具之一。 結(jié)構(gòu)化分析的常用工具：數(shù)據(jù)流圖(DFD)；數(shù)據(jù)字典；判定樹；判定表。

27、在結(jié)構(gòu)化分析使用數(shù)據(jù)流圖(DFD)時候，利用【數(shù)據(jù)字典】對其中的圖形元素進行確切的解釋?！緮?shù)據(jù)字典】是結(jié)構(gòu)化分析的核心。 典型的數(shù)據(jù)流類型有兩種，【交換性】和【事務(wù)型】。 常見的過程設(shè)計工具有：圖形工具(程序流程圖、N-S，PAD，HIPO)、表格工具(判定表)、語言工具(PDL偽碼)。 內(nèi)聚性是模塊內(nèi)部的聯(lián)系，耦合性模塊之間的相互聯(lián)系的緊密程度。 追求目標(biāo)是：模塊的內(nèi)聚程度要高，模塊間的耦合程度要盡量弱。即高內(nèi)聚低耦合。 程序流程圖中帶有箭頭的線段表示的是【控制流】?！酒叫兴倪呅巍看磔斎胼敵觯揪匦巍看硖幚?，菱形代表【判斷】(注意，數(shù)據(jù)流圖中的箭頭，代表【數(shù)據(jù)流】)。 符合結(jié)構(gòu)化原則的三

28、種基本控制結(jié)構(gòu)是：【順序結(jié)構(gòu)】，【選擇結(jié)構(gòu)】和【循環(huán)結(jié)構(gòu)】。3、軟件測試與維護 軟件測試的目的是盡可能多的發(fā)現(xiàn)程序中的錯誤，但是不包括改正錯誤。(軟件調(diào)試的目的才是改正錯誤) 軟件測試分為靜態(tài)測試和動態(tài)測試，其中【靜態(tài)測試】是指不執(zhí)行程序，只對程序文本進行檢查。軟件的動態(tài)測試主要包括【黑盒測試】和【白盒測試】。 黑盒測試的方法有等價類劃分法，邊界值分析法，錯誤推測法，因果圖；白盒測試主要方法有邏輯覆蓋、基本路徑測試。(考試時給出一種方法的名字，你要知道屬于白盒還是黑盒)【白盒測試】的原則之一是保證所測模塊的每一個獨立路徑至少要執(zhí)行一次。白盒測試將程序看做是【路徑的集合】。 軟件測試一般按照四個

29、步驟進行：單元測試，集成測試，驗收測試和系統(tǒng)測試。集成測試應(yīng)該在【單元測試】之后進行。 在模塊測試中，需要為每個被測試的模塊設(shè)計【驅(qū)動模塊】和【承接模塊】。其中，驅(qū)動模塊的作用是將測試的數(shù)據(jù)傳給被測試的模塊，并顯示結(jié)果。 【測試用例】是為某個目標(biāo)而編制的一組測試輸入、執(zhí)行條件及預(yù)期結(jié)果。測試用例包括輸入值集和【輸出值集】。 診斷和改正程序中的錯誤稱為【程序調(diào)試】(或軟件調(diào)試)，通常也稱為Debug。軟件調(diào)試可分為【靜態(tài)調(diào)試】和【動態(tài)調(diào)試】。 在軟件已經(jīng)交付使用之后，為了改正錯誤或滿足新的需要而修改軟件的過程稱為【軟件維護】。注意軟件維護不屬于軟件生命周期【開發(fā)階段】的任務(wù)。第三部分 數(shù)據(jù)庫設(shè)計

30、基礎(chǔ) (歷年比例24%)1、數(shù)據(jù)庫系統(tǒng)基本概念 數(shù)據(jù)庫設(shè)計的根本目標(biāo)是要解決【數(shù)據(jù)共享問題】。在數(shù)據(jù)庫管理技術(shù)發(fā)展的三個階段中，數(shù)據(jù)共享最好的是【數(shù)據(jù)庫系統(tǒng)階段】。數(shù)據(jù)獨立性最高的階段是【數(shù)據(jù)庫系統(tǒng)階段】。 數(shù)據(jù)庫系統(tǒng)與文件系統(tǒng)的區(qū)別是前者具有【特定的數(shù)據(jù)模型】。 數(shù)據(jù)庫系統(tǒng)常見的數(shù)據(jù)模型有層次模型，網(wǎng)絡(luò)模型和【關(guān)系模型】。 數(shù)據(jù)庫系統(tǒng)的核心是【數(shù)據(jù)庫管理系統(tǒng)】。 DBS包括DB和DBMS。完整講，數(shù)據(jù)庫系統(tǒng)DBS由數(shù)據(jù)庫DB、數(shù)據(jù)庫管理系統(tǒng)DBMS、數(shù)據(jù)庫管理員DBA、硬件平臺和軟件平臺組成。 數(shù)據(jù)庫應(yīng)用系統(tǒng)的核心是【數(shù)據(jù)庫維護】。 數(shù)據(jù)庫系統(tǒng)的三級模式結(jié)構(gòu)：內(nèi)模式處于最底層，它反映了數(shù)據(jù)在

31、計算機物理結(jié)構(gòu)中的實際存儲形式；概念模式處于中層，它放映了設(shè)計者的數(shù)據(jù)全局邏輯要求，與軟硬件環(huán)境無關(guān)；外模式處于最外層，它反映了用戶對數(shù)據(jù)的要求。 在數(shù)據(jù)庫系統(tǒng)中，用戶所見的數(shù)據(jù)模式為【外模式】。 數(shù)據(jù)庫設(shè)計的四個階段是：需求分析、概念設(shè)計、【邏輯設(shè)計】和【物理設(shè)計】。將E-R圖轉(zhuǎn)換成關(guān)系數(shù)據(jù)模型屬于【邏輯設(shè)計】階段。 數(shù)據(jù)庫管理系統(tǒng)提供的數(shù)據(jù)語言：數(shù)據(jù)定義語言DDL，數(shù)據(jù)操縱語言DML，數(shù)據(jù)控制語言DCL。SQL的全稱是Structured Query Language，中文意思是【結(jié)構(gòu)化查詢語言】。2、數(shù)據(jù)模型 實體之間的聯(lián)系用樹形結(jié)構(gòu)來表示的模型是【層次模型】。采用二維表來表示的是【關(guān)系模型】。在關(guān)系數(shù)據(jù)庫中，把數(shù)據(jù)表示成二維表，每一個二維表稱為【關(guān)系】。 在關(guān)