全國(guó)計(jì)算機(jī)二級(jí)c語言基礎(chǔ)知識(shí)部分

1、 本文由子衿地盤貢獻(xiàn) doc文檔可能在WAP端瀏覽體驗(yàn)不佳。建議您優(yōu)先選擇TXT，或下載源文件到本機(jī)查看。 2011 二級(jí) C 基礎(chǔ)知識(shí)一 Monday, February 28, 2011 全國(guó)計(jì)算機(jī)二級(jí)考試基礎(chǔ)知識(shí)部分 全國(guó)計(jì)算機(jī)二級(jí)考試基礎(chǔ)知識(shí)部分 1 第 1 章 數(shù)據(jù)結(jié)構(gòu)與算法 3 1.1 算法 3 考點(diǎn) 1 算法的基本概念 3 考點(diǎn) 2 算法復(fù)雜度 3 1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念 4 考點(diǎn) 3 數(shù)據(jù)結(jié)構(gòu)的定義 4 考點(diǎn) 4 線性結(jié)構(gòu)與非線性結(jié)構(gòu) 5 1.3 棧及線性鏈表 5 考點(diǎn) 5 棧及其基本運(yùn)算 5 【補(bǔ)】考點(diǎn) 5 隊(duì)列及其基本運(yùn)算 6 考點(diǎn) 6 線性鏈表的基本概念 7 1.4

2、樹與二叉樹 8 考點(diǎn) 7 樹與二叉樹及其基本性質(zhì) 8 【補(bǔ)】考點(diǎn) 二叉樹的存儲(chǔ)結(jié)構(gòu) 10 考點(diǎn) 8 二叉樹的遍歷 10 1.5 查找技術(shù) 11 考點(diǎn) 9 順序查找 11 考點(diǎn) 10 二分法查找 11 1.6 排序技術(shù) 12 考點(diǎn) 11 交換類排序法 12 【補(bǔ)】12 選擇類排序法 13 【補(bǔ)】13 插入類排序法 13 1.7 例題詳解 13 一、選擇題 13 二、填空題 14 第 2 章 程序設(shè)計(jì)基礎(chǔ) 15 2.1 結(jié)構(gòu)化程序設(shè)計(jì) 15 【補(bǔ)】考點(diǎn) 1 程序設(shè)計(jì)的方法和風(fēng)格 15 考點(diǎn) 2 結(jié)構(gòu)化程序設(shè)計(jì)的原則 15 2.2 面向?qū)ο蟮某绦蛟O(shè)計(jì) 15 考點(diǎn) 2 面向?qū)ο蠓椒ǖ幕靖拍?15 2

3、.3 例題詳解 16 一、選擇題 16 二、填空題 17 1/34 2011 二級(jí) C 基礎(chǔ)知識(shí)一 Monday, February 28, 2011 第 3 章 軟件工程基礎(chǔ) 18 3.1 軟件工程基本概念 18 考點(diǎn) 1 軟件定義與軟件特點(diǎn) 18 考點(diǎn) 2 軟件工程過程與軟件生命周期 19 【補(bǔ)】考點(diǎn) 3 軟件工具與軟件開發(fā)環(huán)境 19 【補(bǔ)】考點(diǎn)結(jié)構(gòu)化分析方法 19 3.2 結(jié)構(gòu)化設(shè)計(jì)方法 20 考點(diǎn) 3 軟件設(shè)計(jì)的基本概念 20 考點(diǎn) 4 詳細(xì)設(shè)計(jì) 21 3.3 軟件測(cè)試 22 考點(diǎn) 5 軟件測(cè)試的目的 22 考點(diǎn) 6 軟件測(cè)試的實(shí)施 22 3.4 軟件的調(diào)試 23 考點(diǎn) 7 軟件調(diào)試的

4、基本概念 23 【補(bǔ)】考點(diǎn) 8 軟件測(cè)試技術(shù)和方法綜述 24 3.5 例題詳解 24 一、選擇題 24 二、填空題 26 第 4 章 數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ) 26 4.1 數(shù)據(jù)庫(kù)系統(tǒng)的基本概念 27 考點(diǎn) 1 數(shù)據(jù)、數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)管理系統(tǒng) 27 4.2 數(shù)據(jù)模型 27 考點(diǎn) 5 數(shù)據(jù)模型的基本概念 27 考點(diǎn) 6 E-R 模型 28 考點(diǎn) 7 層次模型 28 考點(diǎn) 8 關(guān)系模型 29 4.3 關(guān)系代數(shù) 30 考點(diǎn) 9 關(guān)系代數(shù) 30 4.4 數(shù)據(jù)庫(kù)設(shè)計(jì)與管理 31 考點(diǎn) 10 數(shù)據(jù)庫(kù)設(shè)計(jì)概述 31 4.4 例題詳解 31 一、選擇題 31 二、填空題 33 2/34 2011 二級(jí) C 基礎(chǔ)知識(shí)一 M

5、onday, February 28, 2011 第 1 章 數(shù)據(jù)結(jié)構(gòu)與算法 經(jīng)過對(duì)部分考生的調(diào)查以及對(duì)近年真題的總結(jié)分析，筆試部分經(jīng)常考查的是算法復(fù)雜 度、數(shù)據(jù)結(jié)構(gòu)的概念、棧、二叉樹的遍歷、二分法查找，讀者應(yīng)對(duì)此部分進(jìn)行重點(diǎn)學(xué)習(xí)。 詳細(xì)重點(diǎn)學(xué)習(xí)知識(shí)點(diǎn)： 1算法的概念、算法時(shí)間復(fù)雜度及空間復(fù)雜度的概念 2數(shù)據(jù)結(jié)構(gòu)的定義、數(shù)據(jù)邏輯結(jié)構(gòu)及物理結(jié)構(gòu)的定義 3棧的定義及其運(yùn)算、線性鏈表的存儲(chǔ)方式 4樹與二叉樹的概念、二叉樹的基本性質(zhì)、完全二叉樹的概念、二叉樹的遍歷 5二分查找法 6冒泡排序法 1.1 算法 考點(diǎn) 1 算法的基本概念 考試鏈接： 考點(diǎn)1在筆試考試中考核的幾率為30%，主要是以填空題的形式

6、出現(xiàn)，分值為2分，此考 點(diǎn)為識(shí)記內(nèi)容，讀者還應(yīng)該了解算法中對(duì)數(shù)據(jù)的基本運(yùn)算。 計(jì)算機(jī)解題的過程實(shí)際上是在實(shí)施某種算法，這種算法稱為計(jì)算機(jī)算法。 【補(bǔ)】 ：算法是指為解決某個(gè)特定的問題而采取的確定且有限的步驟的一種描述，它是 指令的有限序列，使得給定類型的問題通過有限的指令序列，在有限的時(shí)間內(nèi)被求解。 1算法的基本特征：可行性、確定性、有窮性、擁有足夠的情報(bào)。 算法的基本特征： 2算法的基本要素： 算法的基本要素： （1）算法中對(duì)數(shù)據(jù)的運(yùn)算和操作 基本的運(yùn)算和操作有以下4類：算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算和數(shù)據(jù)傳輸。 （2）算法的控制結(jié)構(gòu)：算法中各操作之間的執(zhí)行順序稱為算法的控制結(jié)構(gòu)。 描述算法的

7、工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程圖、算法描述語言等。一個(gè)算法一 般都可以用順序、選擇、循環(huán)3種基本控制結(jié)構(gòu)組合而成。 考點(diǎn) 2 算法復(fù)雜度 考試鏈接： 考點(diǎn)2在筆試考試中，是一個(gè)經(jīng)?？疾榈膬?nèi)容，在筆試考試中出現(xiàn)的幾率為70%，主要是 以選擇的形式出現(xiàn)，分值為2分，此考點(diǎn)為重點(diǎn)識(shí)記內(nèi)容，讀者還應(yīng)該識(shí)記算法時(shí)間復(fù)雜度 及空間復(fù)雜度的概念。 1.算法的時(shí)間復(fù)雜度 算法的時(shí)間復(fù)雜度 算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。 3/34 2011 二級(jí) C 基礎(chǔ)知識(shí)一 Monday, February 28, 2011 同一個(gè)算法用不同的語言實(shí)現(xiàn)， 或者用不同的編譯程序進(jìn)行編譯， 或者在不同

8、的計(jì)算機(jī) 上運(yùn)行，效率均不同。這表明使用絕對(duì)的時(shí)間單位衡量算法的效率是不合適的。撇開這些與 計(jì)算機(jī)硬件、軟件有關(guān)的因素，可以認(rèn)為一個(gè)特定算法"運(yùn)行工作量"的大小，只依賴于問題 的規(guī)模（通常用整數(shù)n表示） ，它是問題規(guī)模的函數(shù)。即算法的工作量=f（n） 【補(bǔ)】 ：通常記作：T（n）=O(f(n),隨著問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和 f(n)的增長(zhǎng)率相同。 2.算法的空間復(fù)雜度 算法的空間復(fù)雜度 算法的空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。 【補(bǔ)】算法執(zhí)行所需要的存儲(chǔ)空間包括固定部分和可變部分。 疑難解答：算法的工作量用什么來計(jì)算？ 算法的工作量用算法所執(zhí)行的基

9、本運(yùn)算次數(shù)來計(jì)算， 而算法所執(zhí)行的基本運(yùn)算次數(shù)是問題規(guī)模的函數(shù)， 即算法的工作量=f（n） ，其中n是問題的規(guī)模。 1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念 考點(diǎn) 3 數(shù)據(jù)結(jié)構(gòu)的定義 考試鏈接： 考點(diǎn)3在筆試考試中，是一個(gè)經(jīng)?？疾榈膬?nèi)容，在筆試考試中出現(xiàn)的幾率為70%，主要是 以選擇的形式出現(xiàn)，分值為2分，此考點(diǎn)為識(shí)記內(nèi)容，讀者還應(yīng)該識(shí)記數(shù)據(jù)的邏輯結(jié)構(gòu)和存 儲(chǔ)結(jié)構(gòu)的概念。 1、數(shù)據(jù)結(jié)構(gòu)的定義： 、數(shù)據(jù)結(jié)構(gòu)的定義： 數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。 2、數(shù)據(jù)的邏輯結(jié)構(gòu)： 、數(shù)據(jù)的邏輯結(jié)構(gòu)： 數(shù)據(jù)結(jié)構(gòu)之間存在著關(guān)系，這種數(shù)據(jù)元素之間的關(guān)系稱為結(jié)構(gòu)，一個(gè)數(shù)據(jù)結(jié)構(gòu)包括： （1） ：表示數(shù)據(jù)

10、元素的信息； （2） ：表示數(shù)據(jù)元素之間的前后關(guān)系。 數(shù)據(jù)的邏輯結(jié)構(gòu)是對(duì)數(shù)據(jù)元素之間的邏輯關(guān)系的描述， 它可以用一個(gè)數(shù)據(jù)元素的集合和 定義在此集合中的若干關(guān)系來表示。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個(gè)要素：一是數(shù)據(jù)元素的集合，通 常記為D；二是D上的關(guān)系，它反映了數(shù)據(jù)元素之間的前后件關(guān)系，通常記為R。一個(gè)數(shù)據(jù) 結(jié)構(gòu)可以表示成 B=（D，R） 其中B表示數(shù)據(jù)結(jié)構(gòu)。為了反映D中各數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元組來表 示。 3、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)： 、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)： 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的標(biāo)識(shí)（又稱映像）成為數(shù)據(jù)的物理結(jié)構(gòu)，或稱為存儲(chǔ)結(jié)構(gòu)。他所 研究的是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)方法， 包括數(shù)據(jù)結(jié)構(gòu)中元素的表示及

11、元素間關(guān)系的表示。 數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方式有：順序存儲(chǔ)方法、鏈?zhǔn)酱鎯?chǔ)方法、索引存儲(chǔ)方法和散列存儲(chǔ)方法。 4/34 2011 二級(jí) C 基礎(chǔ)知識(shí)一 Monday, February 28, 2011 考點(diǎn) 4 線性結(jié)構(gòu)與非線性結(jié)構(gòu) 考試鏈接： 考點(diǎn)4在筆試考試中， 雖然說不是考試經(jīng)?？疾榈膬?nèi)容， 但讀者還是對(duì)此考點(diǎn)有所了解， 在筆試考試中出現(xiàn)的幾率為30%，主要是以填空題出現(xiàn)的形式出現(xiàn)，分值為2分，此考點(diǎn)為 識(shí)記內(nèi)容。 根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度， 一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型： 線性結(jié)構(gòu)與非線性結(jié)構(gòu)。如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個(gè)條件： （1）有且只有一個(gè)根結(jié)點(diǎn)； （2）每

12、一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。 則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。線性結(jié)構(gòu)又稱線性表。在一個(gè)線性結(jié)構(gòu)中插入或刪除任 何一個(gè)結(jié)點(diǎn)后還應(yīng)是線性結(jié)構(gòu)。如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。 疑難解答：空的數(shù)據(jù)結(jié)構(gòu)是線性結(jié)構(gòu)還是非線性結(jié)構(gòu)？ 一個(gè)空的數(shù)據(jù)結(jié)構(gòu)究竟是屬于線性結(jié)構(gòu)還是屬于非線性結(jié)構(gòu)，這要根據(jù)具體情況來確定。如果對(duì)該數(shù) 據(jù)結(jié)構(gòu)的算法是按線性結(jié)構(gòu)的規(guī)則來處理的，則屬于線性結(jié)構(gòu)；否則屬于非線性結(jié)構(gòu)。 1.3 棧及線性鏈表 考點(diǎn) 5 棧及其基本運(yùn)算 考試鏈接： 考點(diǎn)5在筆試考試中，是一個(gè)必考的內(nèi)容，在筆試考試中出現(xiàn)的幾率為100%，主要是以 選擇的形式出現(xiàn)，分值為2分，此考點(diǎn)為重點(diǎn)

13、掌握內(nèi)容，讀者應(yīng)該掌握棧的運(yùn)算 。 1棧的基本概念 棧是限定只在一端進(jìn)行插入與刪除的線性表，通常稱插入、刪除的這一端為棧頂，另一 端為棧底。當(dāng)表中沒有元素時(shí)稱為空棧。棧頂元素總是后被插入的元素，從而也是最先被刪 除的元素；棧底元素總是最先被插入的元素，從而也是最后才能被刪除的元素。棧是按照 "先進(jìn)后出 或"后進(jìn)先出 的原則組織數(shù)據(jù)的。 先進(jìn)后出" 后進(jìn)先出 后進(jìn)先出" 先進(jìn)后出 5/34 2011 二級(jí) C 基礎(chǔ)知識(shí)一 Monday, February 28, 2011 出棧 棧頂 An A2 A1 進(jìn)棧 棧底 2棧的順序存儲(chǔ)及其運(yùn)算 用一維數(shù)組S（1m

14、）作為棧的順序存儲(chǔ)空間，其中m為最大容量。 在棧的順序存儲(chǔ)空間S （1m） 中， （bottom） S 為棧底元素， （top） S 為棧頂元素。 top=0 表示棧空；top=m表示棧滿。 棧的基本運(yùn)算有三種：入棧、退棧與讀棧頂元素。 入棧運(yùn)算： 入棧運(yùn)算是指在棧頂位置插入一個(gè)新元素。首先將棧頂指針加一（即 （1）入棧運(yùn)算： top加1） ，然后將新元素插入到棧頂指針指向的位置。當(dāng)棧頂指針已經(jīng)指向存儲(chǔ)空間的最后 一個(gè)位置時(shí)，說明?？臻g已滿，不可能再進(jìn)行入棧操作。這種情況稱為棧"上溢"錯(cuò)誤。 （2）退棧運(yùn)算： 退棧運(yùn)算： 退棧是指取出棧頂元素并賦給一個(gè)指定的變量。首先將棧頂

15、元素（棧 頂指針指向的元素）賦給一個(gè)指定的變量，然后將棧頂指針減一（即top減1） 。當(dāng)棧頂指針 為0時(shí)，說明?？?，不可進(jìn)行退棧操作。這種情況稱為棧的"下溢"錯(cuò)誤。 （3）讀棧頂元素：讀棧頂元素是指將棧頂元素賦給一個(gè)指定的變量。這個(gè)運(yùn)算不刪 讀棧頂元素： 除棧頂元素，只是將它賦給一個(gè)變量，因此棧頂指針不會(huì)改變。當(dāng)棧頂指針為0時(shí)，說明棧 空，讀不到棧頂元素。 小技巧：棧是按照"先進(jìn)后出"或"后進(jìn)先出"的原則組織數(shù)據(jù)，但是出棧方式有多種選擇，在考 題中經(jīng)?？疾楦鞣N不同的出棧方式。 【補(bǔ)】考點(diǎn) 5 隊(duì)列及其基本運(yùn)算 1 隊(duì)列的基本概念 隊(duì)列

16、是一種只允許在一端進(jìn)行插入， 而在另一端進(jìn)行刪除的線性表， 它是一種操作 受限的線性表，在表中只允許插入的一端稱為隊(duì)尾（Rear） ，只允許進(jìn)行刪除的一端為 隊(duì)頭（Front） ，因此隊(duì)列被稱為“先進(jìn)先出”表。 2、隊(duì)列及其基本運(yùn)算 6/34 2011 二級(jí) C 基礎(chǔ)知識(shí)一 Monday, February 28, 2011 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)一般采用循環(huán)隊(duì)列的形式， 即將隊(duì)列存儲(chǔ)空間最后一個(gè)位置繞 到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。 隊(duì)列的運(yùn)算有以下兩類： （1） ：入隊(duì)運(yùn)算：從隊(duì)尾插入一個(gè)元素； （2） ：出隊(duì)運(yùn)算：從隊(duì)頭刪除一個(gè)元素。 出隊(duì)運(yùn)算 A1 A2 An-1 A

17、n 入隊(duì)運(yùn)算 隊(duì)頭 隊(duì)尾 考點(diǎn) 6 線性鏈表的基本概念 考試鏈接： 考點(diǎn)6在筆試考試中出現(xiàn)的幾率為30%，主要是以選擇的形式出現(xiàn)，分值為2分，此考點(diǎn) 為識(shí)記內(nèi)容。重點(diǎn)識(shí)記結(jié)點(diǎn)的組成。 在鏈?zhǔn)酱鎯?chǔ)方式中，要求每個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱為 數(shù)據(jù)域，另一部分用于存放指針，稱為指針域。其中指針用于指向該結(jié)點(diǎn)的前一個(gè)或后一 個(gè)結(jié)點(diǎn)（即前件或后件） 。 鏈?zhǔn)酱鎯?chǔ)方式既可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。 指針域 數(shù)據(jù)域 指針域 數(shù)據(jù)域 指針域 數(shù)據(jù)域 （1）線性鏈表 ） 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。 在某些應(yīng)用中，對(duì)線性鏈表中的每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針，一個(gè)稱為左指針，用

18、以指向其 前件結(jié)點(diǎn)；另一個(gè)稱為右指針，用以指向其后件結(jié)點(diǎn)。這樣的表稱為雙向鏈表。 7/34 2011 二級(jí) C 基礎(chǔ)知識(shí)一 Monday, February 28, 2011 指針 一 數(shù)據(jù)域 指針 二 （2）帶鏈的棧 ） 棧也是線性表， 也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 帶鏈的?？梢杂脕硎占?jì)算機(jī)存儲(chǔ)空間中所 有空閑的存儲(chǔ)結(jié)點(diǎn)，這種帶鏈的棧稱為可利用棧。 疑難解答：在鏈?zhǔn)浇Y(jié)構(gòu)中，存儲(chǔ)空間位置關(guān)系與邏輯關(guān)系是什么？ 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的 邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。 1.4 樹與二叉樹 考點(diǎn) 7 樹

19、與二叉樹及其基本性質(zhì) 考試鏈接： 考點(diǎn)7在筆試考試中，是一個(gè)必考的內(nèi)容，在筆試考試中出現(xiàn)的幾率為100%，主要是以 選擇的形式出現(xiàn)，有時(shí)也有出現(xiàn)在填空題中，分值為2分，此考點(diǎn)為重點(diǎn)掌握內(nèi)容。重點(diǎn)識(shí) 記樹及二叉樹的性質(zhì)。 誤區(qū)警示： 滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。應(yīng)該注意二者的區(qū)別。 1、樹的基本概念 、 樹(tree）是一種簡(jiǎn)單的非線性結(jié)構(gòu)。在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié) 點(diǎn)，沒有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)。每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，它們稱為該 結(jié)點(diǎn)的子結(jié)點(diǎn)。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。 在樹結(jié)構(gòu)中， 一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為該結(jié)點(diǎn)的度。 葉子

20、結(jié)點(diǎn)的度為0。 在樹中， 所有結(jié)點(diǎn)中的最大的度稱為樹的度。 8/34 2011 二級(jí) C 基礎(chǔ)知識(shí)一 Monday, February 28, 2011 根節(jié)點(diǎn) 前件 如左圖所示，根 子節(jié)點(diǎn) 子節(jié)點(diǎn) 子節(jié)點(diǎn) 后件 節(jié)點(diǎn)的度是 3， 葉子的度是 0， 樹的度為 3. 葉子節(jié)點(diǎn) 葉子節(jié)點(diǎn) 2、二叉樹及其基本性質(zhì) 、 （1）二叉樹的定義 ） 二叉樹是一種很有用的非線性結(jié)構(gòu)，具有以下兩個(gè)特點(diǎn)： 非空二叉樹只有一個(gè)根結(jié)點(diǎn)； 每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹和右子樹。 根節(jié)點(diǎn) 左子樹 右子樹 葉子節(jié)點(diǎn) 葉子節(jié)點(diǎn) 由以上特點(diǎn)可以看出，在二叉樹中，每一個(gè)結(jié)點(diǎn)的度最大為2，即所有子樹（左子樹或

21、 右子樹）也均為二叉樹，而樹結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)的度可以是任意的。另外，二叉樹中的每 個(gè)結(jié)點(diǎn)的子樹被明顯地分為左子樹和右子樹。 在二叉樹中， 一個(gè)結(jié)點(diǎn)可以只有左子樹而沒有 右子樹，也可以只有右子樹而沒有左子樹。當(dāng)一個(gè)結(jié)點(diǎn)既沒有左子樹也沒有右子樹時(shí)，該結(jié) 點(diǎn)即為葉子結(jié)點(diǎn)。 （2）二叉樹的基本性質(zhì) ） 二叉樹具有以下幾個(gè)性質(zhì)： 性質(zhì)1：在二叉樹的第k層上，最多有2 性質(zhì)2：深度為m的二叉樹最多有2 m k-1 （k1）個(gè)結(jié)點(diǎn)； -1個(gè)結(jié)點(diǎn)； 性質(zhì)3： 在任意一棵二叉樹中， 度為0的結(jié)點(diǎn) （即葉子結(jié)點(diǎn)） 總是比度為2的結(jié)點(diǎn)多一個(gè)。 性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為log2n+1，其中l(wèi)og2

22、n表示取log2n 9/34 2011 二級(jí) C 基礎(chǔ)知識(shí)一 Monday, February 28, 2011 的整數(shù)部分。 小技巧：在二叉樹的遍歷中 在二叉樹的遍歷中，無論是前序遍歷，中序遍歷還是后序遍歷，二叉樹的葉子結(jié)點(diǎn)的先 二叉樹的葉子結(jié)點(diǎn)的先 后順序都是不變的。 3、滿二叉樹與完全二叉樹 、 1 滿二叉樹： 在一棵二叉樹 滿二叉樹： 節(jié)點(diǎn)都存在左右樹， 節(jié)點(diǎn)都存在左右樹 并且 一層上，這樣的一棵二 這樣的一棵二 中， ， 如果所有的分支 所有的葉子都在同 叉樹稱作滿二叉樹。 叉樹稱作滿二叉樹 一層外，每一層上的 一層外 結(jié)點(diǎn)。 。 葉子節(jié)點(diǎn)只出現(xiàn) 點(diǎn)集中在樹的左部。 點(diǎn)集中在樹的左部

23、 2 完全二叉樹： 完全二叉樹：除最后 所有結(jié)點(diǎn)都有兩個(gè)子 在最下層和次下層，且最下層的葉子節(jié) 在最下層和次下層 見上圖完全二叉樹 【補(bǔ)】考點(diǎn) 二叉樹的存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 考點(diǎn) 8 二叉樹的遍歷 考試鏈接： 在筆試考試中考核幾率為30%，分值為2分，讀者應(yīng)該熟練掌握各種遍歷的具體算 讀者應(yīng)該熟練掌握各種遍歷的具體算 考點(diǎn)8在筆試考試中考核幾率為 法，能由兩種遍歷的結(jié)果推導(dǎo)另一種遍歷的結(jié)果 能由兩種遍歷的結(jié)果推導(dǎo)另一種遍歷的結(jié)果。 在遍歷二叉樹是指不重復(fù)的訪問二叉樹中所有的結(jié)點(diǎn) 是指不重復(fù)的訪問二叉樹中所有的結(jié)點(diǎn)。 二叉樹的遍歷分為三類：前序遍歷、中序遍歷和后序遍歷。 二叉樹的

24、遍歷分為三類 （1）前序遍歷：先訪問 先訪問根結(jié)點(diǎn)、然后遍歷左子樹，最后遍歷右子樹； ； 注意訪問某一個(gè)子樹時(shí)，將該子樹所有的子樹相全部訪問完畢 將該子樹所有的子樹相全部訪問完畢 （2）中序遍歷：先遍歷 先遍歷左子樹、然后訪問根結(jié)點(diǎn)，最后遍歷右子樹； ； 在遍 歷左、右子樹 時(shí)，仍然先遍 歷左子樹 ，再訪問根結(jié) 點(diǎn)，最后遍歷 右子樹 仍然先遍 （3）后序遍歷：先遍歷 先遍歷左子樹、然后遍歷右子樹，最后訪問根結(jié)點(diǎn)； ； 10/34 2011 二級(jí) C 基礎(chǔ)知識(shí)一 Monday, February 28, 2011 A B D H E F I C G J 前序遍歷： ABD H E CF G I

25、J 中序遍歷： DH BE AFC I GJ 后序遍歷： HDEB F IJG C A 疑難解答：樹與二叉樹的不同之處是什么？ 在二叉樹中，每一個(gè)結(jié)點(diǎn)的度最大為2，即所有子樹（左子樹或右子樹）也均為二叉樹，而樹結(jié)構(gòu)中 的每一個(gè)結(jié)點(diǎn)的度可以是任意的。 1.5 查找技術(shù) 考點(diǎn) 9 順序查找 考試鏈接： 考點(diǎn)9在筆試考試中考核幾率在30%，一般出現(xiàn)選擇題中，分值為2分，讀者應(yīng)該具體掌 握順序查找的算法。 查找是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)指定的元素。從線性表的第一個(gè)元素開始， 依次將線性表中的元素與被查找的元素相比較， 若相等則表示查找成功； 若線性表中所有的 元素都與被查找元素進(jìn)行了比較但都不

26、相等，則表示查找失敗。 在下列兩種情況下也只能采用順序查找： （1）如果線性表為無序表，則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，只能用順序查 找。 （2）即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找。 考點(diǎn) 10 二分法查找 考試鏈接： 考點(diǎn)10在筆試考試中考核幾率為30%，一般出現(xiàn)填空題中，分值為2分，考核比較多查找 的比較次數(shù)，讀者應(yīng)該具體掌握二分查找法的算法。 二分法只適用于順序存儲(chǔ)的，按非遞減排列的有序表，其方法如下： 11/34 2011 二級(jí) C 基礎(chǔ)知識(shí)一 Monday, February 28, 2011 設(shè)有序線性表的長(zhǎng)度為n，被查找的元素為i， （1）將i與線性表

27、的中間項(xiàng)進(jìn)行比較； （2）若i與中間項(xiàng)的值相等，則查找成功； （3）若i小于中間項(xiàng)，則在線性表的前半部分以相同的方法查找； （4）若i大于中間項(xiàng)，則在線性表的后半部分以相同的方法查找。 疑難解答：二分查找法適用于哪種情況？ 二分查找法只適用于順序存儲(chǔ)的有序表。在此所說的有序表是指線性表中的元素按值非遞減排列（即 從小到大，但允許相鄰元素值相等） 。 這個(gè)過程一直進(jìn)行到查找成功或子表長(zhǎng)度為0為止。 對(duì)于長(zhǎng)度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次。 1.6 排序技術(shù) 考點(diǎn) 11 交換類排序法 考試鏈接: 考點(diǎn)11屬于比較難的內(nèi)容，一般以選擇題的形式考查，考核幾率為30%，分

28、值約為2分， 讀者應(yīng)該熟練掌握幾種排序算法的基本過程。 冒泡排序法和快速排序法都屬于交換類排序法。 （1）冒泡排序法 ） 首先，從表頭開始往后掃描線性表，逐次比較相鄰兩個(gè)元素的大小，若前面的元素大于 后面的元素，則將它們互換，不斷地將兩個(gè)相鄰元素中的大者往后移動(dòng)，最后最大者到了 線性表的最后。 然后，從后到前掃描剩下的線性表，逐次比較相鄰兩個(gè)元素的大小，若后面的元素小于 前面的元素，則將它們互換，不斷地將兩個(gè)相鄰元素中的小者往前移動(dòng)，最后最小者到了 線性表的最前面。 對(duì)剩下的線性表重復(fù)上述過程，直到剩下的線性表變空為止，此時(shí)已經(jīng)排好序。 在最壞的情況下，冒泡排序需要比較次數(shù)為n（n1）/2。

29、（2）快速排序法 ） 它的基本思想是：任取待排序序列中的某個(gè)元素作為基準(zhǔn)（一般取第一個(gè)元素） ，通過 一趟排序， 將待排元素分為左右兩個(gè)子序列， 左子序列元素的排序碼均小于或等于基準(zhǔn)元素 的排序碼， 右子序列的排序碼則大于基準(zhǔn)元素的排序碼， 然后分別對(duì)兩個(gè)子序列繼續(xù)進(jìn)行排 序，直至整個(gè)序列有序。 12/34 2011 二級(jí) C 基礎(chǔ)知識(shí)一 疑難解答：冒泡排序和快速排序的平均執(zhí)行時(shí)間分別是多少？ Monday, February 28, 2011 冒泡排序法的平均執(zhí)行時(shí)間是O（n2） ，而快速排序法的平均執(zhí)行時(shí)間是O（nlog2n） 。 【補(bǔ)】12 選擇類排序法 選擇排序的基本思想是：每次從待排

30、序的文件中選出排序碼最小的記錄，將該記錄放入 已排序文件的最后一個(gè)位置，直到已排序文件記錄個(gè)數(shù)等于初始待排序文件的記錄個(gè)數(shù)。 【補(bǔ)】13 插入類排序法 插入排序的基本思想是： 將無序的序列中的各元素依次插入到已經(jīng)有序的線性列表中。 1.7 例題詳解 一、選擇題 【例1】算法的時(shí)間復(fù)雜度取決于。 （考點(diǎn)2） A）問題的規(guī)模 B）待處理的數(shù)據(jù)的初態(tài) C）問題的難度 D）A）和B） 解析：算法的時(shí)間復(fù)雜度不僅與問題的規(guī)模有關(guān)，在同一個(gè)問題規(guī)模下，而且與輸入數(shù) 據(jù)有關(guān)。即與輸入數(shù)據(jù)所有的可能取值范圍、輸入各種數(shù)據(jù)或數(shù)據(jù)集的概率有關(guān)。 答案：D） 【例2】在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成。 （考

31、點(diǎn)3） A）內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) B）線性結(jié)構(gòu)和非線性結(jié)構(gòu) C）緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) D）動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) 解析： 邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系， 線性結(jié)構(gòu)表示數(shù)據(jù)元素之間為一對(duì)一的 關(guān)系，非線性結(jié)構(gòu)表示數(shù)據(jù)元素之間為一對(duì)多或者多對(duì)一的關(guān)系，所以答案為B） 。 答案：B） 【例3】以下不是棧的基本運(yùn)算。 （考點(diǎn)5） A）判斷棧是否為素空 B）將棧置為空棧 C）刪除棧頂元素 D）刪除棧底元素 解析：棧的基本運(yùn)算有：入棧，出棧（刪除棧頂元素） ，初始化、置空、判斷棧是否為 空或滿、提取棧頂元素等，對(duì)棧的操作都是在棧頂進(jìn)行的。 答案：D） 【例4】鏈表不具備的特點(diǎn)是。 （考點(diǎn)6） A）可隨機(jī)訪

32、問任意一個(gè)結(jié)點(diǎn) B）插入和刪除不需要移動(dòng)任何元素 C）不必事先估計(jì)存儲(chǔ)空間 D）所需空間與其長(zhǎng)度成正比 解析：順序表可以隨機(jī)訪問任意一個(gè)結(jié)點(diǎn)，而鏈表必須從第一個(gè)數(shù)據(jù)結(jié)點(diǎn)出發(fā)，逐一查 找每個(gè)結(jié)點(diǎn)。所以答案為A） 。 答案：A） 【例5】已知某二叉樹的后序遍歷序列是DACBE，中序遍歷序列是DEBAC，則它的前 序遍歷序列是。 （考點(diǎn)8） 13/34 2011 二級(jí) C 基礎(chǔ)知識(shí)一 Monday, February 28, 2011 A）ACBED B）DEABC C）DECAB D）EDBAC 解析：后序遍歷的順序是"左子樹右子樹根結(jié)點(diǎn)"；中序遍歷順序是"左子樹根結(jié)

33、 點(diǎn)右子樹"；前序遍歷順序是"根結(jié)點(diǎn)左子樹右子樹"。根據(jù)各種遍歷算法，不難得出 前序遍歷序列是EDBAC。所以答案為D） 。 答案：D） 【例6】設(shè)有一個(gè)已按各元素的值排好序的線性表（長(zhǎng)度大于2） ，對(duì)給定的值k，分別用 順序查找法和二分查找法查找一個(gè)與k相等的元素，比較的次數(shù)分別是s和b，在查找不成功 的情況下，s和b的關(guān)系是。 （考點(diǎn)9） A）s=b B）s>b C）slog2n+1。 答案：B） 【例7】在快速排序過程中，每次劃分，將被劃分的表（或子表）分成左、右兩個(gè)子表， 考慮這兩個(gè)子表，下列結(jié)論一定正確的是。 （考點(diǎn)11） A）左、右兩個(gè)子表都已各

34、自排好序 B）左邊子表中的元素都不大于右邊子表中的元素 C） 左邊子表的長(zhǎng)度小于右邊子表的長(zhǎng)度 D）左、右兩個(gè)子表中元素的平均值相等 解析： 快速排序基本思想是： 任取待排序表中的某個(gè)元素作為基準(zhǔn) （一般取第一個(gè)元素） ， 通過一趟排序， 將待排元素分為左右兩個(gè)子表， 左子表元素的排序碼均小于或等于基準(zhǔn)元素 的排序碼，右子表的排序碼則大于基準(zhǔn)元素的排序碼，然后分別對(duì)兩個(gè)子表繼續(xù)進(jìn)行排序， 直至整個(gè)表有序。 答案：B） 二、填空題 【例1】問題處理方案的正確而完整的描述稱為。 （考點(diǎn)1） 解析：計(jì)算機(jī)解題的過程實(shí)際上是在實(shí)施某種算法，這種算法稱為計(jì)算機(jī)算法。 答案：算法 【例2】一個(gè)空的數(shù)據(jù)結(jié)構(gòu)

35、是按線性結(jié)構(gòu)處理的，則屬于。 （考點(diǎn)4） 解析：一個(gè)空的數(shù)據(jù)結(jié)構(gòu)是線性結(jié)構(gòu)或是非線性結(jié)構(gòu)，要根據(jù)具體情況而定。如果對(duì)數(shù) 據(jù)結(jié)構(gòu)的運(yùn)算是按線性結(jié)構(gòu)來處理的，則屬于線性結(jié)構(gòu)，否則屬于非線性結(jié)構(gòu)。 答案：線性結(jié)構(gòu) 【例3】設(shè)樹的度為，其中度為、和的結(jié)點(diǎn)的個(gè)數(shù)分別為、 ，則中葉子結(jié)點(diǎn)的個(gè)數(shù)為。 （考點(diǎn)7） 解析：根據(jù)樹的性質(zhì)：樹的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度與對(duì)應(yīng)的結(jié)點(diǎn)個(gè)數(shù)乘積之和加。 因此樹的結(jié)點(diǎn)數(shù)為××××16。 葉子結(jié)點(diǎn)數(shù)目等于樹結(jié) 點(diǎn)總數(shù)減去度不為的結(jié)點(diǎn)數(shù)之和，即16（）。 答案：8 【例4】二分法查找的存儲(chǔ)結(jié)構(gòu)僅限于且是有序的。 （考點(diǎn)10） 解析： 二分查

36、找， 也稱折半查找， 它是一種高效率的查找方法。 但二分查找有條件限制： 要求表必須用順序存儲(chǔ)結(jié)構(gòu)，且表中元素必須按關(guān)鍵字有序(升序或降序均可） 。 答案：順序存儲(chǔ)結(jié)構(gòu) 14/34 2011 二級(jí) C 基礎(chǔ)知識(shí)一 Monday, February 28, 2011 第 2 章 程序設(shè)計(jì)基礎(chǔ) 經(jīng)過對(duì)部分考生的調(diào)查以及對(duì)近年真題的總結(jié)分析，筆試部分經(jīng)?？疾榈氖墙Y(jié)構(gòu)化程 序設(shè)計(jì)的原則、面向?qū)ο蠓椒ǖ幕靖拍?，讀者應(yīng)對(duì)此部分進(jìn)行重點(diǎn)學(xué)習(xí)。 詳細(xì)重點(diǎn)學(xué)習(xí)知識(shí)點(diǎn)： 1結(jié)構(gòu)化程序設(shè)計(jì)方法的四個(gè)原則 2對(duì)象、類、消息、繼承的概念、類與實(shí)例的區(qū)別 2.1 結(jié)構(gòu)化程序設(shè)計(jì) 【補(bǔ)】考點(diǎn) 1 程序設(shè)計(jì)的方法和風(fēng)格 程

37、序設(shè)計(jì)方法是研究問題求解和如何進(jìn)行系統(tǒng)構(gòu)造的軟件方法學(xué)。常用的程序設(shè)計(jì)方法 有：結(jié)構(gòu)化程序設(shè)計(jì)方法、軟件工程方法和面向?qū)ο蠓椒ā?程序設(shè)計(jì)風(fēng)格是指編寫程序時(shí)所表現(xiàn)出的特點(diǎn)、習(xí)慣和邏輯思路。良好的程序設(shè)計(jì)風(fēng)格 時(shí)程序質(zhì)量的重要保證， 因?yàn)榱己玫某绦蛟O(shè)計(jì)風(fēng)格可以使程序結(jié)構(gòu)清晰合理， 便于閱讀和維 護(hù)，提高軟件的開發(fā)效率。 考點(diǎn) 2 結(jié)構(gòu)化程序設(shè)計(jì)的原則 考試鏈接： 考點(diǎn)1在筆試考試中出現(xiàn)的幾率為30%，主要是以選擇題的形式出現(xiàn)，分值為2分，此考 點(diǎn)為識(shí)記內(nèi)容，讀者應(yīng)該識(shí)記結(jié)構(gòu)化程序設(shè)計(jì)方法的四個(gè)主要原則。 20世紀(jì)70年代提出了"結(jié)構(gòu)化程序設(shè)計(jì)"的思想和方法。 結(jié)構(gòu)化程序設(shè)計(jì)方

38、法引入了工程 化思想和結(jié)構(gòu)化思想， 使大型軟件的開發(fā)和編程得到了極大的改善。 結(jié)構(gòu)化程序設(shè)計(jì)方法的 主要原則為：自頂向下、逐步求精、模塊化和限制使用goto語句。 疑難解答：如何進(jìn)行自頂向下設(shè)計(jì)方法？ 程序設(shè)計(jì)時(shí)，應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)；不要一開始就過多追 求眾多的細(xì)節(jié)，先從最上層總目標(biāo)開始設(shè)計(jì)，逐步使問題具體化。 2.2 面向?qū)ο蟮某绦蛟O(shè)計(jì) 考點(diǎn) 2 面向?qū)ο蠓椒ǖ幕靖拍?考試鏈接： 考點(diǎn)2在筆試考試中，是一個(gè)經(jīng)?？疾榈膬?nèi)容，在筆試考試中出現(xiàn)的幾率為70%，主要是 以填空題的形式出現(xiàn)，分值為2分，此考點(diǎn)為重點(diǎn)識(shí)記內(nèi)容，讀者應(yīng)該識(shí)記幾個(gè)基本要素的 15/34

39、 2011 二級(jí) C 基礎(chǔ)知識(shí)一 Monday, February 28, 2011 定義、對(duì)象的特征以及消息、繼承、類的定義。 誤區(qū)警示： 當(dāng)使用"對(duì)象"這個(gè)術(shù)語時(shí)，既可以指一個(gè)具體的對(duì)象，也可以泛指一般的對(duì)象，但是當(dāng) 使用"實(shí)例"這個(gè)術(shù)語時(shí)，必須是指一個(gè)具體的對(duì)象。 面向?qū)ο蠓椒êw對(duì)象及對(duì)象屬性與方法、類、繼承、多態(tài)性幾個(gè)基本要素。 （1）對(duì)象 ） 通常把對(duì)對(duì)象的操作也稱為方法或服務(wù)。 屬性即對(duì)象所包含的信息， 它在設(shè)計(jì)對(duì)象時(shí)確定， 一般只能通過執(zhí)行對(duì)象的操作來改變。 屬性值應(yīng)該指的是純粹的數(shù)據(jù)值，而不能指對(duì)象。 操作描述了對(duì)象執(zhí)行的功能，若通過信

40、息的傳遞，還可以為其他對(duì)象使用。 對(duì)象具有如下特征：標(biāo)識(shí)惟一性、分類性、多態(tài)性、封裝性、模塊獨(dú)立性。 （2）類和實(shí)例 ） 類是具有共同屬性、 共同方法的對(duì)象的集合。 它描述了屬于該對(duì)象類型的所有對(duì)象的性 質(zhì)，而一個(gè)對(duì)象則是其對(duì)應(yīng)類的一個(gè)實(shí)例。 類是關(guān)于對(duì)象性質(zhì)的描述， 它同對(duì)象一樣， 包括一組數(shù)據(jù)屬性和在數(shù)據(jù)上的一組合法操 作。 （3）消息 ） 消息是實(shí)例之間傳遞的信息， 它請(qǐng)求對(duì)象執(zhí)行某一處理或回答某一要求的信息， 它統(tǒng)一 了數(shù)據(jù)流和控制流。 一個(gè)消息由三部分組成：接收消息的對(duì)象的名稱、消息標(biāo)識(shí)符（消息名）和零個(gè)或多個(gè) 參數(shù)。 （4）繼承 ） 廣義地說，繼承是指能夠直接獲得已有的性質(zhì)和特征，

41、而不必重復(fù)定義它們。 繼承分為單繼承與多重繼承。單繼承是指，一個(gè)類只允許有一個(gè)父類，即類等級(jí)為樹形 結(jié)構(gòu)。多重繼承是指，一個(gè)類允許有多個(gè)父類。 （5）多態(tài)性 ） 對(duì)象根據(jù)所接收的消息而做出動(dòng)作， 同樣的消息被不同的對(duì)象接收時(shí)可導(dǎo)致完全不同的 行動(dòng)，該現(xiàn)象稱為多態(tài)性。 疑難解答：能舉一下現(xiàn)實(shí)中的對(duì)象及其屬性和操作嗎？ 一輛汽車是一個(gè)對(duì)象，它包含了汽車的屬性（如顏色、型號(hào)等）及其操作（如啟動(dòng)、剎車等） 。一個(gè) 窗口是對(duì)象，它包含了窗口的屬性（如大小、顏色等）及其操作（如打開、關(guān)閉等） 。 2.3 例題詳解 一、選擇題 【例1】結(jié)構(gòu)化程序設(shè)計(jì)方法提出于。 （考點(diǎn)1） 16/34 2011 二級(jí) C

42、基礎(chǔ)知識(shí)一 Monday, February 28, 2011 A）20世紀(jì)50年代 B）20世紀(jì)60年代 C）20世紀(jì)70年代 D）20世紀(jì)80年代 解析： 20世紀(jì)70年代提出了"結(jié)構(gòu)化程序設(shè)計(jì) （structured programming） "的思想和方法。 結(jié)構(gòu)化程序設(shè)計(jì)方法引入了工程化思想和結(jié)構(gòu)化思想， 使大型軟件的開發(fā)和編程得到了極大 的改善。 答案：C） 【例2】結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則有下列4項(xiàng)，不正確的是。 （考點(diǎn)1） A）自下向上 B）逐步求精 C）模塊化 D）限制使用goto語句 解析：結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則為： （1）自頂向下：即先考慮總

43、體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)。 （2）逐步求精：對(duì)復(fù)雜問題，應(yīng)設(shè)計(jì)一些子目標(biāo)作過渡，逐步細(xì)化。 （3）模塊化：把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)， 把每個(gè)小目標(biāo)稱為一個(gè)模塊。 （4）限制使用goto語句。 答案：A） 【例3】面向?qū)ο蟮拈_發(fā)方法中，類與對(duì)象的關(guān)系是。 （考點(diǎn)2） A）抽象與具體 B）具體與抽象 C）部分與整體 D）整體與部分 解析： 現(xiàn)實(shí)世界中的很多事物都具有相似的性質(zhì)， 把具有相似的屬性和操作的對(duì)象歸為 類，也就是說類是具有共同屬性、共同方法的對(duì)象的集合，是對(duì)對(duì)象的抽象。它描述了該對(duì) 象類型的所有對(duì)象的性質(zhì)， 而一個(gè)對(duì)象則是對(duì)應(yīng)類的

44、一個(gè)具體實(shí)例。 所以本題正確答案為A） 項(xiàng)。 答案：A） 二、填空題 【例1】在面向?qū)ο蠓椒ㄖ?，使用已?jīng)存在的類定義作為基礎(chǔ)建立新的類定義，這樣的 技術(shù)叫做。 （考點(diǎn)2） 解析： 繼承是面向?qū)ο蠓椒ǖ囊粋€(gè)主要特征。 繼承是使用已有的類定義作為基礎(chǔ)建立新類 的定義技術(shù)。已有的類可當(dāng)作基類來引用，則新類相應(yīng)地可當(dāng)作派生類來引用。 答案：繼承 【例2】對(duì)象的基本特點(diǎn)包括、分類性、多態(tài)性、封裝性和模塊獨(dú)立性好等5個(gè)特 點(diǎn)。 （考點(diǎn)2） 解析：對(duì)象具有如下的基本特點(diǎn)： （1）標(biāo)識(shí)惟一性。對(duì)象是可區(qū)分的，并且由對(duì)象的內(nèi)在本質(zhì)來區(qū)分； （2）分類性?？梢詫⒕哂邢嗤瑢傩院筒僮鞯膶?duì)象抽象成類； （3）多態(tài)性。同

45、一個(gè)操作可以是不同對(duì)象的行為； （4） 封裝性。 只能看到對(duì)象的外部特征， 無需知道數(shù)據(jù)的具體結(jié)構(gòu)以及實(shí)現(xiàn)操作的算法； （5）模塊獨(dú)立性。面向?qū)ο笫怯蓴?shù)據(jù)及可以對(duì)這些數(shù)據(jù)施加的操作所組成的統(tǒng)一體。 答案：標(biāo)識(shí)惟一性 【例3】對(duì)象根據(jù)所接收的消息而做出動(dòng)作，同樣的消息被不同的對(duì)象所接收時(shí)可能導(dǎo) 致完全不同的行為，這種現(xiàn)象稱為。 （考點(diǎn)2） 解析： 對(duì)象根據(jù)所接收的消息而做出動(dòng)作， 同樣的消息被不同的對(duì)象接收時(shí)可導(dǎo)致完全 17/34 2011 二級(jí) C 基礎(chǔ)知識(shí)一 Monday, February 28, 2011 不同的行為，該現(xiàn)象稱為多態(tài)性。 答案：多態(tài)性 第 3 章 軟件工程基礎(chǔ) 經(jīng)過對(duì)部分

46、考生的調(diào)查以及對(duì)近年真題的總結(jié)分析，筆試部分經(jīng)?？疾榈氖擒浖?周期、軟件設(shè)計(jì)的基本原理，軟件測(cè)試的目的、軟件調(diào)試的基本概念，讀者應(yīng)對(duì)此部分進(jìn)行 重點(diǎn)學(xué)習(xí)。 詳細(xì)重點(diǎn)學(xué)習(xí)知識(shí)點(diǎn)： 1軟件的概念、軟件生命周期的概念及各階段所包含的活動(dòng) 2概要設(shè)計(jì)與詳細(xì)設(shè)計(jì)的概念、模塊獨(dú)立性及其度量的標(biāo)準(zhǔn)、詳細(xì)設(shè)計(jì)常用的工具 3軟件測(cè)試的目的、軟件測(cè)試的4個(gè)步驟、 4軟件調(diào)試的任務(wù) 3.1 軟件工程基本概念 考點(diǎn) 1 軟件定義與軟件特點(diǎn) 考試鏈接： 考點(diǎn)1在筆試考試中，是一個(gè)經(jīng)?？疾榈膬?nèi)容，考核的幾率為70%，主要是以選擇題的形 式出現(xiàn)，分值為2分，此考點(diǎn)為識(shí)記內(nèi)容，讀者應(yīng)該識(shí)記軟件的定義，特點(diǎn)及其分類。 軟件

47、指的是計(jì)算機(jī)系統(tǒng)中與硬件相互依存的另一部分， 包括程序、 數(shù)據(jù)和相關(guān)文檔的完 整集合。程序是軟件開發(fā)人員根據(jù)用戶需求開發(fā)的、用程序設(shè)計(jì)語言描述的、適合計(jì)算機(jī)執(zhí) 行的指令序列。數(shù)據(jù)是使程序能正常操縱信息的數(shù)據(jù)結(jié)構(gòu)。文檔是與程序的開發(fā)、維護(hù)和使 用有關(guān)的圖文資料?？梢?，軟件由兩部分組成： （1）機(jī)器可執(zhí)行的程序和數(shù)據(jù)； （2）機(jī)器不可執(zhí)行的，與軟件開發(fā)、運(yùn)行、維護(hù)、使用等有關(guān)的文檔。 軟件的特點(diǎn)： （1）軟件是邏輯實(shí)體，而不是物理實(shí)體，具有抽象性； （2）沒有明顯的制作過程，可進(jìn)行大量的復(fù)制； （3）使用期間不存在磨損、老化問題； （4）軟件的開發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴性； （5）軟件復(fù)雜性高

48、，成本昂貴； （6）軟件開發(fā)涉及諸多社會(huì)因素。 根據(jù)應(yīng)用目標(biāo)的不同，軟件可分應(yīng)用軟件、系統(tǒng)軟件和支撐軟件（或工具軟件） 。 小提示：應(yīng)用軟件是為解決特定領(lǐng)域的應(yīng)用而開發(fā)的軟件；系統(tǒng)軟件是計(jì)算機(jī)管理自身資源，提 高計(jì)算機(jī)使用效率并為計(jì)算機(jī)用戶提供各種服務(wù)的軟件；支撐軟件是介于兩者之間，協(xié)助用戶開發(fā)軟件的 工具性軟件。 18/34 2011 二級(jí) C 基礎(chǔ)知識(shí)一 Monday, February 28, 2011 考點(diǎn) 2 軟件工程過程與軟件生命周期 考試鏈接： 考點(diǎn)2在筆試考試中，在筆試考試中出現(xiàn)的幾率為30%，主要是以選擇題的形式出現(xiàn)，分 值為2分， 此考點(diǎn)為識(shí)記內(nèi)容， 讀者應(yīng)該識(shí)記軟件生命周

49、期 的定義， 主要活動(dòng)階段及其任務(wù)。 軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過程稱為軟件生命周期。一般包括 可行性分析研究與需求分析、 設(shè)計(jì)、 實(shí)現(xiàn)、 測(cè)試、 交付使用以及維護(hù)等活動(dòng)， 如圖31所示。 圖31軟件生命周期 還可以將軟件生命周期分為如上圖所示的軟件定義、軟件開發(fā)和軟件運(yùn)行維護(hù)3個(gè)階 段。 生命周期的主要活動(dòng)階段是： 可行性研究與計(jì)劃制定、 需求分析、 軟件設(shè)計(jì)、 軟件實(shí)施、 軟件測(cè)試及運(yùn)行與維護(hù)。 【補(bǔ)】考點(diǎn) 3 軟件工具與軟件開發(fā)環(huán)境 軟件工具是從初期的單項(xiàng)工具朝著集成工具發(fā)展的， 與此同時(shí)， 如見開發(fā)的各種方法也 必須得到相應(yīng)的軟件開發(fā)工具的支持，否則方法就很難有效的

50、實(shí)施。 軟件工程環(huán)境或軟件開發(fā)環(huán)境是全面支持軟件開發(fā)過程的軟件工具集合， 這些軟件工具 按照一定的方法或模式組合起來，并能支持軟件生命周期的各個(gè)階段和各項(xiàng)任務(wù)的完成。 【補(bǔ)】考點(diǎn)結(jié)構(gòu)化分析方法 1、結(jié)構(gòu)化分析方法 、 19/34 2011 二級(jí) C 基礎(chǔ)知識(shí)一 Monday, February 28, 2011 1. 關(guān)于結(jié)構(gòu)化分析方法 結(jié)構(gòu)化分析方法是結(jié)構(gòu)化程序設(shè)計(jì)理論在軟件需求分析階段的運(yùn)用， 其目的是幫助弄清用戶對(duì)軟件的需求。 2. 結(jié)構(gòu)化分析的常用工具 數(shù)據(jù)流圖 數(shù)據(jù)字典 判定樹 判定表 2、軟件需求規(guī)格說明書 、 軟件需求規(guī)格說明書是作為需求分析的一部分而制定的可交付文件，是需 求分

51、析階段的最后結(jié)果，其正確性是第一位必須保證的。 3.2 結(jié)構(gòu)化設(shè)計(jì)方法 考點(diǎn) 3 軟件設(shè)計(jì)的基本概念 考試鏈接： 考點(diǎn)3在筆試考試中，是一個(gè)經(jīng)?？疾榈膬?nèi)容，考核中幾率為70%，主要是以選擇題的形 式出現(xiàn)，分值為2分，此考點(diǎn)為重點(diǎn)掌握內(nèi)容，讀者應(yīng)該識(shí)記模塊獨(dú)立性中的耦合性和內(nèi)聚 性。 誤區(qū)警示： 在程序結(jié)構(gòu)中，各模塊的內(nèi)聚性越強(qiáng)，則耦合性越弱。軟件設(shè)計(jì)應(yīng)盡量做到高內(nèi)聚，低 耦合，即減弱模塊之間的耦合性和提高模塊內(nèi)的內(nèi)聚性，有利于提高模塊的獨(dú)立性。 1. 【補(bǔ)】軟件實(shí)際的基本概念 軟件設(shè)計(jì)基礎(chǔ)：軟件設(shè)計(jì)是軟件工程的重要階段，是一個(gè)把軟件需求轉(zhuǎn)化為軟件 表示的過程。 軟件設(shè)計(jì)的基本原理：軟件設(shè)計(jì)遵循

52、軟件工程的基本目標(biāo)和原則，建立了適用于 在軟件設(shè)計(jì)中應(yīng)該遵循的基本原理和與軟件設(shè)計(jì)有關(guān)的概念。 結(jié)果化設(shè)計(jì)方法：與結(jié)構(gòu)化需求分析方法相對(duì)應(yīng)的是結(jié)構(gòu)化設(shè)計(jì)方法。 。 2. 【補(bǔ)】概要設(shè)計(jì) 概要設(shè)計(jì)的任務(wù)： 20/34 2011 二級(jí) C 基礎(chǔ)知識(shí)一 Monday, February 28, 2011 （1） （2） （3） （4） 設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫(kù)設(shè)計(jì) 編寫概要設(shè)計(jì)文檔 概要設(shè)計(jì)文檔審核 面向數(shù)據(jù)流的設(shè)計(jì)方法： 結(jié)果化設(shè)計(jì)方法是一種面向數(shù)據(jù)流的設(shè)計(jì)方法，他可以與 SA 方法銜接， 通常用數(shù)據(jù)流圖（DFD）描述系統(tǒng)中加工和流動(dòng)的情況。 設(shè)計(jì)的準(zhǔn)則： 軟件概要設(shè)計(jì)的主要任務(wù)就是軟件

53、結(jié)構(gòu)的設(shè)計(jì)，為了提高設(shè)計(jì)的質(zhì)量， 必須根據(jù)軟件設(shè)計(jì)的原理改進(jìn)軟件設(shè)計(jì)。 3. 【補(bǔ)】詳細(xì)設(shè)計(jì) 詳細(xì)設(shè)計(jì)階段是軟件設(shè)計(jì)的第二步，在總設(shè)計(jì)階段，已經(jīng)確立了軟件的 總體結(jié)構(gòu)，給出了系統(tǒng)中各個(gè)組成模塊的功能和模塊間的接口。 詳細(xì)設(shè)計(jì)的任務(wù)： 詳細(xì)設(shè)計(jì)的任務(wù)是為每個(gè)模塊設(shè)計(jì)其實(shí)現(xiàn)的細(xì)節(jié)， 確定每個(gè)模塊的算法和 數(shù)據(jù)結(jié)構(gòu)，并用某種特定的表達(dá)工具給出清晰的描述。 詳細(xì)設(shè)計(jì)的工具： 常見的工具有：程序流程圖、N-S 流程圖和問題分析圖。 考點(diǎn) 4 詳細(xì)設(shè)計(jì) 考試鏈接： 考點(diǎn)4在筆試考試中，在筆試考試中出現(xiàn)的幾率為30%，主要是以選擇題的形式出現(xiàn)，分 值為2分，此考點(diǎn)為識(shí)記內(nèi)容，讀者應(yīng)該識(shí)記過程設(shè)計(jì)包括哪些常用

54、工具。 詳細(xì)設(shè)計(jì)的任務(wù)是為軟件結(jié)構(gòu)圖中的每個(gè)模塊確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)， 用某種選 定的表達(dá)表示工具算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。 21/34 2011 二級(jí) C 基礎(chǔ)知識(shí)一 Monday, February 28, 2011 詳細(xì)過程設(shè)計(jì)的常用工具有： （1）圖形工具：程序流程圖，N-S，PAD，HIPO。 （2）表格工具：判定表。 （3）語言工具：PDL（偽碼） 。 程序流程圖的5種控制結(jié)構(gòu)：順序型、選擇型、先判斷重復(fù)型、后判斷重復(fù)型和多分支 選擇型。 方框圖中僅含5種基本的控制結(jié)構(gòu)，即順序型、選擇型、多分支選擇型、WHILE重復(fù)型 和UNTIL重復(fù)型。 PAD圖表示5種基本控制結(jié)構(gòu)，即順序型

55、、選擇型、多分支選擇型、WHILE重復(fù)型和 UNTIL重復(fù)型。 過程設(shè)計(jì)語言（PDL）也稱為結(jié)構(gòu)化的語言和偽碼，它是一種混合語言，采用英語的詞 匯和結(jié)構(gòu)化程序設(shè)計(jì)語言，類似編程語言。 PDL可以由編程語言轉(zhuǎn)換得到，也可以是專門為過程描述而設(shè)計(jì)的。 疑難解答：程序流程圖，N-S圖，PAD圖的控制結(jié)構(gòu)的異同點(diǎn)是什么？ 相同點(diǎn)是三種圖都有順序結(jié)構(gòu)，選擇結(jié)構(gòu)和多分支選擇，并且N-S圖和PAD圖還有相同的WHILE重復(fù) 型、UNTIL重復(fù)型；不同點(diǎn)是程序流程圖沒有WHILE重復(fù)型、UNTIL重復(fù)型而有后判斷重復(fù)型和先判斷重 復(fù)型。 3.3 軟件測(cè)試 軟件測(cè)試 考點(diǎn) 5 軟件測(cè)試的目的 考試鏈接： 考點(diǎn)5在筆試考試中，是一個(gè)經(jīng)?？疾榈膬?nèi)容，在筆試考試中出現(xiàn)的幾率為70%，主要是 以選擇題的形式出現(xiàn)， 分值為2分， 此考點(diǎn)為理解內(nèi)容， 讀者應(yīng)該理解測(cè)試是為了發(fā)現(xiàn)錯(cuò)誤。 軟件測(cè)試是在軟件投入運(yùn)行前對(duì)軟件需求、設(shè)計(jì)、編碼的最后審核。其工作量、成本占 總工作量、總成本的40%以上，而且具有較高的組織管理和技術(shù)難度。 （1）軟件測(cè)試是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過程； （2）一個(gè)好的測(cè)試用例是能夠發(fā)現(xiàn)