二級C語言公共基礎(chǔ)知識教案

1、二級公共基礎(chǔ)考前輔導(dǎo)常州工學(xué)院常州工學(xué)院相關(guān)知識在二級考試中，占總分的30%n數(shù)據(jù)結(jié)構(gòu)與算法n程序設(shè)計基礎(chǔ)n軟件工程基礎(chǔ)n數(shù)據(jù)庫設(shè)計基礎(chǔ)各部分所占比例圖數(shù)據(jù)結(jié)構(gòu)與算法高頻考點nTop1：算法的基本概念nTop2：算法的復(fù)雜度nTop3：邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)nTop4：線性結(jié)構(gòu)與非線性結(jié)構(gòu)nTop5：棧nTop6：隊列nTop7：鏈表nTop8：二叉樹及其基本性質(zhì)數(shù)據(jù)結(jié)構(gòu)與算法高頻考點nTop9：二叉樹的遍歷nTop10：順序查找nTop11：二分法查找nTop12：排序Top1：算法的基本概念n知識點算法是解決問題準(zhǔn)確而完整的描述。算法是解決問題準(zhǔn)確而完整的描述。它是對特定問題求解步驟的一種描述

2、，是指令的有限序列，其中每條指令表示一個或多個操作。嚴(yán)格來說，一個算法必須滿足下面5個主要特性。Top1：算法的基本概念1.有窮性：有窮性：一個算法必須在執(zhí)行有窮步之后結(jié)束（對任何合法的輸入值），而且每一步都必須在有窮時間內(nèi)完成。2.確定性：確定性：算法中每條指令必須有確定的含義，且在任何條件下，算法只有唯一的一條執(zhí)行路徑。3.可行性：可行性：算法中描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。4.有輸入：有輸入：一個算法可以有0個或多個輸入。5.有輸出：有輸出：一個算法必須有1個或多個輸出。Top1：算法的基本概念n真題分析（2008年4月）算法的有窮性是指A、算法程序的運行時

3、間是有限的 B、算法程序所處理的數(shù)據(jù)量是有限的 C、算法程序的長度是有限的 D、算法只能被有限的用戶使用 ATop1：算法的基本概念n真題分析真題分析（2005年4月）算法具有5 個特性，下列選項中不屬于算法特性的是A、有窮性B、簡潔性C、可行性D、確定性BTop1：算法的基本概念n練習(xí)題1、算法的五個重要特性是有窮性、確定性、有輸入和有輸出。可行性可行性Top2：算法的復(fù)雜度知識點知識點n衡量算法優(yōu)劣的兩個標(biāo)準(zhǔn)一個算法的優(yōu)劣將影響到算法乃至程序的效率。算法分析的目的是在于選擇合適的算法和改進算法。評價一個算法的好壞有兩個標(biāo)準(zhǔn)：時間復(fù)雜度時間復(fù)雜度和空間復(fù)空間復(fù)雜度。雜度。Top2：算法的復(fù)雜

4、度1.算法的時間復(fù)雜度時間復(fù)雜度是指執(zhí)行算法所需要執(zhí)行算法所需要的計算工作量的計算工作量，可以用執(zhí)行算法的過程中所需要的基本運算的執(zhí)行次數(shù)基本運算的執(zhí)行次數(shù)來度量；2.算法的空間復(fù)雜度空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間內(nèi)存空間的大小。Top2：算法的復(fù)雜度n真題分析（2007年4月）下列敘述中正確的是A、算法的效率只與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)。B、算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量。C、數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是一一對應(yīng)的。D、算法的空間復(fù)雜度與時間復(fù)雜度一定相關(guān)。BTop2：算法的復(fù)雜度n答案D：由算法的時間復(fù)雜度空間復(fù)雜度的定義可知，兩者不相關(guān)。n答案A：

5、算法的執(zhí)行效率不僅與問題的規(guī)模有關(guān)，而且還與數(shù)據(jù)的存儲結(jié)構(gòu)有關(guān)。n答案C：數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，它是從邏輯上描述數(shù)據(jù)元素之間的關(guān)系的，是獨立于計算機的，數(shù)據(jù)的存儲結(jié)構(gòu)是研究數(shù)據(jù)元素和數(shù)據(jù)元素之間的關(guān)系如何在計算機中表示，它們并非一一對應(yīng)。Top2：算法的復(fù)雜度n真題分析（2006年9月）下列敘述中正確的是A、一個算法的空間復(fù)雜度大，則其時間復(fù)雜度必定大。B、一個算法的空間復(fù)雜度大，則其時間復(fù)雜度必定小。C、一個算法的時間復(fù)雜度大，則其空間復(fù)雜度必定小。D、上述三種說法都不對。DTop2：算法的復(fù)雜度n真題分析（2005年9月）算法的復(fù)雜度主要包括時間復(fù)雜度和復(fù)雜度?？臻g空間

6、Top2：算法的復(fù)雜度n練習(xí)題1、算法的時間復(fù)雜度是指A、執(zhí)行算法程序所需要的時間B、算法程序的長度C、算法執(zhí)行過程中所需要的基本運算次數(shù)D、算法程序中的指令條數(shù)CTop2：算法的復(fù)雜度n練習(xí)題2、算法的空間復(fù)雜度是指A、算法程序的長度B、算法程序中的指令條數(shù)C、算法程序所占用的存儲空間D、算法執(zhí)行過程中所占用的存儲空間DTop2：算法的復(fù)雜度n解析在算法執(zhí)行時所需要的內(nèi)在空間，其中包括：算法程序所占用的空間算法程序所占用的空間、輸入的初始數(shù)據(jù)所占輸入的初始數(shù)據(jù)所占的存儲空間的存儲空間以及算法執(zhí)行過程中所需要的額外算法執(zhí)行過程中所需要的額外空間空間，其中額外空間還包括算法執(zhí)行過程中的工作單元以

7、及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲空間。Top3：邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)n知識點1.邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)是反映元素之間邏輯關(guān)系的，即前后件關(guān)系，分為線性結(jié)構(gòu)線性結(jié)構(gòu)（常見的有線性表、棧和列隊）和非線性結(jié)構(gòu)非線性結(jié)構(gòu)（常見的有樹和圖）2.存儲結(jié)構(gòu)存儲結(jié)構(gòu)（物理結(jié)構(gòu)）是數(shù)據(jù)的邏輯結(jié)構(gòu)在數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式計算機存儲空間中的存放形式。在數(shù)據(jù)的存儲結(jié)構(gòu)中，不僅要存放各種數(shù)據(jù)元素的信息，還要存放元素之間的前后件關(guān)系的信息。Top3：邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)n知識點3.數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)的存儲結(jié)構(gòu)并不是一數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)的存儲結(jié)構(gòu)并不是一一對應(yīng)的一對應(yīng)的。一般來說，一種數(shù)據(jù)的邏輯結(jié)構(gòu)一種數(shù)據(jù)的邏

8、輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu)。常見的存儲結(jié)構(gòu)有順序、鏈接、索引、散列順序、鏈接、索引、散列等。采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)的處理效率是不同的。Top3：邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)n真題分析（2005年9月）下列敘述中正確的是A、一個邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲結(jié)構(gòu)B、數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲結(jié)構(gòu)屬于非線性結(jié)構(gòu)。C、一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且種存儲結(jié)構(gòu)不影響數(shù)據(jù)處理的效率。D、一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且種存儲結(jié)構(gòu)影響數(shù)據(jù)處理的效率。DTop3：邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)n真題分析（2005年9月）數(shù)據(jù)結(jié)構(gòu)可以分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，循環(huán)隊列屬于結(jié)

9、構(gòu)。循環(huán)隊列是指將隊列存儲空間的最后一個位置繞到第一個位置，形成一個環(huán)狀空間，供隊列循環(huán)使用。所以循環(huán)隊列是屬于存儲結(jié)構(gòu)。存儲存儲Top3：邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)n真題分析（2005年4月）數(shù)據(jù)的存儲結(jié)構(gòu)是指A、存儲在外存中的數(shù)據(jù)B、數(shù)據(jù)所占的存儲空間C、數(shù)據(jù)在計算機中的順序存儲方式D、數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示DTop3：邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)n真題分析（2007年9月）下列敘述中正確的是A、程序執(zhí)行的效率與數(shù)據(jù)的存儲結(jié)構(gòu)密切相關(guān)B、順序存儲結(jié)構(gòu)只針對線性結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)只針對非線性結(jié)構(gòu)C、程序執(zhí)行的效率只取決于所處理的數(shù)據(jù)量D、以上三種說法都不對ATop3：邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)n練習(xí)題1、數(shù)據(jù)

10、結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的A、存儲結(jié)構(gòu)B、物理結(jié)構(gòu)C、邏輯結(jié)構(gòu)D、邏輯結(jié)構(gòu)和物理結(jié)構(gòu)CTop3：邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)n練習(xí)題2、在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(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、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)BTop4：線性結(jié)構(gòu)與非線性結(jié)構(gòu)n知識點1.根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件的復(fù)雜程序，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。2.如果一個非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個條件：有且只有一個根結(jié)點每個結(jié)點最多有一個前件，也最多只有一個后件。則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。線性表是典型的線性結(jié)構(gòu)，如棧、隊列、串。典型的線性結(jié)構(gòu)，如

11、棧、隊列、串。3.如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱為非線性結(jié)非線性結(jié)構(gòu)。如多維數(shù)組、廣義表、樹和圖等。構(gòu)。如多維數(shù)組、廣義表、樹和圖等。Top4：線性結(jié)構(gòu)與非線性結(jié)構(gòu)n真題分析（2006年9月）數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈的隊列屬于隊列是特殊的線性表，可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯ΑＫ詭ф湹年犃袑儆诰€性結(jié)構(gòu)。線性結(jié)構(gòu)線性結(jié)構(gòu)Top4：線性結(jié)構(gòu)與非線性結(jié)構(gòu)n真題分析（2006年4月）下列敘述中正確的是A、線性鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)B、棧與隊列是非線性結(jié)構(gòu)C、雙向鏈表是非線性結(jié)構(gòu)D、只有根結(jié)構(gòu)的二叉樹是線性結(jié)構(gòu)ATop4：線性結(jié)構(gòu)與非線性結(jié)構(gòu)n解析A、線性鏈表就是指線性表的

12、鏈?zhǔn)酱鎯Y(jié)構(gòu)，簡稱鏈表。線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)的基本單位稱為存儲結(jié)點，每個結(jié)點包括數(shù)據(jù)域和指針域兩個部分。B、棧、隊列和雙向鏈表都是線性結(jié)構(gòu)C、二叉樹是非線性結(jié)構(gòu)。D、線性結(jié)構(gòu)和非線性結(jié)構(gòu)是從數(shù)據(jù)的邏輯結(jié)構(gòu)角度來講的，與該數(shù)據(jù)結(jié)構(gòu)中有多少個元素沒有關(guān)系，即使是空的二叉樹也是非線性結(jié)構(gòu)。Top4：線性結(jié)構(gòu)與非線性結(jié)構(gòu)n真題分析（2007年9月）下列敘述中正確的是A、數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)必定是一一對應(yīng)的B、由于計算機存儲空間是向量式的存儲結(jié)構(gòu)，因此，數(shù)據(jù)的存儲結(jié)構(gòu)一定是線性結(jié)構(gòu)C、程序設(shè)計語言中的數(shù)組一般是順序存儲結(jié)構(gòu)，因此，利用數(shù)組只能處理線線結(jié)構(gòu)D、以上三種說法都不對CTop4：線性結(jié)構(gòu)與非線

13、性結(jié)構(gòu)n真題分析（2008年9月）下列敘述中正確的是A、順序存儲結(jié)構(gòu)的存儲一定是連續(xù)的，鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲空間不一定是連續(xù)的B、順序存儲結(jié)構(gòu)只針對線性結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)只針對非線性結(jié)構(gòu)C、順序存儲結(jié)構(gòu)能存儲有序表，鏈?zhǔn)酱鎯Y(jié)構(gòu)不能存儲有序表D、鏈?zhǔn)酱鎯Y(jié)構(gòu)比順序存儲結(jié)構(gòu)節(jié)省存儲空間ATop4：線性結(jié)構(gòu)與非線性結(jié)構(gòu)n練習(xí)題1、下列敘述中正確的是A、線性表是線性結(jié)構(gòu)B、棧與隊列是非線性結(jié)構(gòu)C、線性鏈表是非線性結(jié)構(gòu)D、二叉樹是線性結(jié)構(gòu)ATop4：線性結(jié)構(gòu)與非線性結(jié)構(gòu)n練習(xí)題2、以下數(shù)據(jù)結(jié)構(gòu)中不屬于線性數(shù)據(jù)結(jié)構(gòu)的是A、隊列B、線性表C、二叉樹D、棧CTop4：線性結(jié)構(gòu)與非線性結(jié)構(gòu)n練習(xí)題3、在數(shù)據(jù)結(jié)構(gòu)

14、中，用一組地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的方式是A、動態(tài)結(jié)構(gòu)B、緊湊結(jié)構(gòu)C、線性結(jié)構(gòu)D、非線性結(jié)構(gòu)CTop5：棧n知識點1.棧（堆棧STACK）是一種運算受限制的線性表。限制其只能在表的一端進行插入和刪除操作，此端稱為棧頂，棧頂?shù)牡谝粋€元素稱為棧頂元素，相對地，把另一端稱為棧底。2.向一個棧插入新元素稱為入棧，從棧中刪除一個元素稱為出棧出退棧。3.由于棧的插入和刪除只能在一端進行，后進棧的元素必定先出棧，所以棧又稱為后進先出表LIFO；先進棧的元素必定后出棧，所以棧又稱為先進后出FILO表。Top5：棧棧底dcba棧頂入棧入棧出棧出棧結(jié)論：后進先出，先進后出結(jié)論：后進先出，先進后出棧頂棧頂

15、棧頂Top5：棧n真題分析（2006年9月）按“后進先出”原則組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是棧棧Top5：棧n真題分析（2006年4月）按照“后進先出”原則組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是A、隊列B、棧C、雙向鏈表D、二叉樹BTop5：棧n真題分析（2005年9月）下列關(guān)于棧的描述中正確的是A、在棧中只能插入元素而不能刪除元素B、在棧中只能刪除元素而不能插入元素C、棧是特殊的線性表，只能在一端插入或刪除D、棧是特殊的線性表，只能在一端插入，在另一端刪除。CTop5：棧n真題分析（2005年4月）下列關(guān)于棧的描述錯誤的是A、棧是先進后出的線性表B、棧只能順序存儲C、棧具有記憶作用D、對棧的插入和刪除操作中，不需要改變

16、棧底指針BTop5：棧n真題分析（2008年4月）下列關(guān)于棧的敘述正確的是 A、棧按“先進先出”組織數(shù)據(jù)B、棧按“先進后出”組織數(shù)據(jù) C、只能在棧底插入數(shù)據(jù) D、不能刪除數(shù)據(jù) BTop5：棧n真題分析（2008年9月）一個棧的初始狀態(tài)為空。現(xiàn)將元素1、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，則元素出棧的順序是A、12345ABCDEB、 EDCBA54321C、ABCDE12345D、54321EDCBABTop5：棧n練習(xí)題1、如果進棧序列為e1,e2,e3,e4，則可能的出棧序列是A、e3,e1,e4,e2B、e2,e4,e3,e1C、e3,e4,e1,e2D、任意順序

17、BTop5：棧e4e3e2e1入棧入棧棧底棧頂棧頂棧頂e4e3e2e1棧底出棧出棧出棧出棧入棧入棧Top5：棧n練習(xí)題2、下列關(guān)于棧的敘述中正確的是A、在棧中只能插入元素B、在棧中只能刪除元素C、棧是先進先出的線性表D、棧是先進后出的線性表DTop6：隊列n知識點1.隊列（QUEUE）簡稱隊，和棧一樣，也是一種運算受限制的線性表。其限制體現(xiàn)在僅允許在表的一端進行插入（隊尾），在另一端進行刪除（隊首）。2.向隊列中插入新元素稱為進隊或入隊，新元素進入后就成為新的隊尾元素；從隊列中刪除元素稱為離隊或出隊，元素離隊后，其后繼元素成為隊首元素。3.由于隊列的插入和刪除操作分別是在各自的一端進行的，每個

18、元素必然按照進入的次序離隊，所以隊列稱為先進先出表（FIFO），或后進后出表（LILO）Top6：隊列e4e3e2e1隊首入隊入隊隊尾隊尾隊尾出隊出隊e4e3e2e1結(jié)論：先進先出，后進后出結(jié)論：先進先出，后進后出Top6：隊列n真題分析（2007年4月）下列隊列的敘述中正確的是A、隊列屬于非線性表B、隊列按“先進后出”原則組織數(shù)據(jù)C、隊列在隊尾刪除數(shù)據(jù)D、隊列按“先進先出”原則組織數(shù)據(jù)DTop6：隊列n真題分析（2008年9月）下列敘述中正確的是A、循環(huán)隊列有隊頭和隊尾兩個指針，因此，循環(huán)隊列是非線性結(jié)構(gòu)B、在循環(huán)隊列中，只需要隊頭指針就能反應(yīng)隊列中元素的動態(tài)變化情況C、在循環(huán)隊列中，只需要

19、隊尾指針就能反應(yīng)隊列中元素的動態(tài)變化情況D、循環(huán)隊列中元素的個數(shù)是由隊頭和隊尾指針共同決定DTop6：隊列循環(huán)隊列循環(huán)隊列rearfronte1front隊列為空時，頭指針等于尾指針隊列為空時，頭指針等于尾指針e2front隊列中元素個數(shù)為隊列中元素個數(shù)為rear-frontTop6：隊列e4e3e2e1循環(huán)隊列循環(huán)隊列frontreare7e6e5rearfronte8rear隊頭指針大于隊尾指針時，元素個數(shù)隊頭指針大于隊尾指針時，元素個數(shù)=隊尾隊尾+m-隊頭隊頭e9e10rear隊頭指針等于隊尾指針時，隊列滿隊頭指針等于隊尾指針時，隊列滿Top6：隊列n真題分析（2007年9月）線性表的存

20、儲結(jié)構(gòu)主要分為順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu).隊列是一種特殊的線性表,循環(huán)隊列是隊列的_存儲結(jié)構(gòu).順序順序Top6：隊列n真題分析（2008年4月）設(shè)某循環(huán)隊列的容量為50，頭指針front=5（指向隊頭元素的前一位置），尾指針rear=29（指向隊尾元素），則該循環(huán)隊列中共有個元素。 24Top6：隊列n練習(xí)題1、棧和隊列的共同特點是A、都是先進先出B、都是后進后出C、只允許在端點處插入和刪除元素D、沒有共同點CTop6：隊列n練習(xí)題2、下列關(guān)于隊列的敘述中正確的是A、在隊列中只能插入元素B、在隊列中只能刪除元素C、隊列是先進先出的線性表D、隊列是后進先出的線性表CTop6：隊列n練習(xí)題3、一個

21、隊列的入隊序列是a,b,c,d，則隊列的輸出序列是A、d,c,b,aB、a,b,c,dC、a,d,c,bD、c,b,d,aBTop7：鏈表（單鏈表）n知識點1.數(shù)據(jù)結(jié)構(gòu)中，每個數(shù)據(jù)存儲在一個存儲單元中，這個存儲單元稱為“結(jié)點”。在鏈?zhǔn)剑▎捂湥┐鎯Ψ绞街校竺總€結(jié)點由兩部分組成：存放數(shù)據(jù)元素的數(shù)據(jù)域和存放指針的指針域。其中指針指向該結(jié)點的前一個或后一個結(jié)點。2.在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以存儲空間可以不連續(xù)不連續(xù)，各個數(shù)據(jù)結(jié)點存儲順序與數(shù)據(jù)元素的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針來確定的。3.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。Top7：鏈表（單鏈表）20310

22、051003110011002100310041005100610071008 head1 head23 單鏈表的邏輯結(jié)構(gòu) 單鏈表的存儲結(jié)構(gòu)nullTop7：鏈表（單鏈表）n真題分析（2005年4月）下列對于線性鏈表的描述中正確的是A、存儲空間不一定是連續(xù)，且各元素的存儲順序是任意的。B、存儲空間不一定是連續(xù)，且前件元素一定存儲在后件元素的前面C、存儲空間必定連續(xù)，且各前件元素一定存儲在后件元素的前面D、存儲空間必定連續(xù)，且各元素的存儲順序是任意的ATop7：鏈表（單鏈表）n練習(xí)題1、用鏈表來表示線性表的優(yōu)點是A、便于隨機存取B、花費的存儲空間較順序存儲少C、便于插入和刪除操作D、數(shù)據(jù)元素的物

23、理順序與邏輯順序相同CTop7：鏈表（單鏈表）n練習(xí)題2、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是一種的存儲結(jié)構(gòu)A、隨機存儲B、順序存儲C、索引存儲D、散列存儲B線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中的每一個存儲結(jié)點不僅含有一個數(shù)據(jù)元素，還包括指針，每一個指針指向一個與本結(jié)點有邏輯關(guān)系的結(jié)點，此類存儲屬于順序存儲Top8：二叉樹及其基本性質(zhì)n知識點1. 樹是一種非線性結(jié)構(gòu)，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次性。ABCDEFGHI結(jié)點度葉子寬度深/高度Top8：二叉樹及其基本性質(zhì)n知識點2.二叉樹具有兩個特點：非空二叉樹只有一個根結(jié)點每一個結(jié)點最多有兩棵子樹，且分另稱為左子樹和右子樹ABCDEGFTop8：二叉樹及其基本性質(zhì)n

24、知識點3.二叉樹的性質(zhì)在二叉樹中，第i層上的結(jié)點數(shù)不超過2i-1深度為h(h1)的二叉樹最多有2h-1個結(jié)點，最少有h個結(jié)點對于任意一棵二叉樹，如果其葉子結(jié)點數(shù)（度為0）為x，而度為2的結(jié)點總數(shù)為Y，則X=Y+1具有n個結(jié)點的完全二叉樹的深度為int(log2n)+1Top8：二叉樹及其基本性質(zhì)n知識點4.完全二叉樹：除最后一層外，每一層上的結(jié)點都達到最大值（2），在最后一層上的結(jié)點都集中在該層最左邊的若干位置，也就是說，只能缺少右邊的若干結(jié)點。ABCDEGFABCDEHFGTop8：二叉樹及其基本性質(zhì)ABCDEHFGABCDEHFGI完全二叉樹特點：有完全二叉樹特點：有n個結(jié)點的完全二叉樹，

25、其深度為個結(jié)點的完全二叉樹，其深度為 log2n+1Top8：二叉樹及其基本性質(zhì)n知識點5.滿二叉樹：除最后一層外，其它每一層上的結(jié)點都有兩個子結(jié)點。ABCDEFEABCTop8：二叉樹及其基本性質(zhì)n真題分析（2007年4月）某二叉樹中有n個度為2的結(jié)點，則該二叉樹中，葉子結(jié)點數(shù)為A、n+1B、n-1C、2nD、n/2ATop8：二叉樹及其基本性質(zhì)n真題分析(2007年4月）在深度為7的滿二叉樹中，度為2的結(jié)點個數(shù)為27-1=N0+N2N2=N0-1127=N0+(N0-1)N0=64,N2=6363Top8：二叉樹及其基本性質(zhì)n真題分析（2005年9月）一棵二叉樹第六層（根結(jié)點為第1層）的結(jié)

26、點數(shù)最多為個二叉樹性質(zhì)二叉樹性質(zhì)在二叉樹中，第在二叉樹中，第i層上的結(jié)點數(shù)不超過層上的結(jié)點數(shù)不超過2i-132Top8：二叉樹及其基本性質(zhì)n真題分析（2006年4月）在深度為7的滿二叉樹中，葉子結(jié)點的個數(shù)為A、32B、31C、64D、63C滿二叉樹每一層上的結(jié)點數(shù)都是最大結(jié)點數(shù)滿二叉樹每一層上的結(jié)點數(shù)都是最大結(jié)點數(shù)2i-1Top8：二叉樹及其基本性質(zhì)n真題分析（2005年4月）某二叉樹中，度為2的結(jié)點數(shù)有18個，則該二叉樹中有個葉子結(jié)點。19Top8：二叉樹及其基本性質(zhì)n真題分析（2007年9月）一棵二叉樹中共有70個葉子結(jié)點與80個度為1的結(jié)點，則該二叉樹中的總結(jié)點數(shù)為A、219B、221C

27、、229D、231ATop8：二叉樹及其基本性質(zhì)n真題分析（2008年4月）深度為5的滿二叉樹有個葉子結(jié)點。 16Top8：二叉樹及其基本性質(zhì)n練習(xí)題1、在一棵二叉樹第5層上的結(jié)點數(shù)最多是個A、8B、16C、32D、15BTop8：二叉樹及其基本性質(zhì)n練習(xí)題2、在深度為5的滿二叉樹中，葉子結(jié)點的個數(shù)為A、32B、31C、16D、15CTop8：二叉樹及其基本性質(zhì)n練習(xí)題3、設(shè)一棵完全二叉樹共有699個結(jié)點，則在該二叉樹中的葉子結(jié)點數(shù)為A、349B、350C、255D、351BABCDEFGTop9：二叉樹的遍歷n知識點1.遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規(guī)則和順序走遍

28、二叉樹的所有結(jié)點，所每個結(jié)點都被訪問一次，且僅被訪問一次。2.按訪問根結(jié)點根結(jié)點先后順序，遍歷分為先序遍歷，中序遍歷和后序遍歷。Top9：二叉樹的遍歷ABCDEFG先序遍歷：先訪問根結(jié)點，然后訪問左子樹，最后訪問右子樹。先序遍歷：先訪問根結(jié)點，然后訪問左子樹，最后訪問右子樹。H先序遍歷結(jié)果為：先序遍歷結(jié)果為： A BDHE CFGTop9：二叉樹的遍歷ABCDEFG中序遍歷：先訪問左子樹，然后訪問根結(jié)點，最后訪問右子樹。中序遍歷：先訪問左子樹，然后訪問根結(jié)點，最后訪問右子樹。H中序遍歷結(jié)果為：中序遍歷結(jié)果為： D HBEA FCGTop9：二叉樹的遍歷ABCDEFGH后序遍歷：先訪問左子樹，然

29、后右子樹，最后根結(jié)點。后序遍歷：先訪問左子樹，然后右子樹，最后根結(jié)點。后序遍歷結(jié)果為：后序遍歷結(jié)果為： H DEBF GCATop9：二叉樹的遍歷n真題分析（2007年4月）對下列二叉樹，進行前序遍歷的結(jié)果是A、DYBEAFCZXB、YDEBFZXCAC、ABDYECFXZD、ABCDEFXYZABCDEFXYZCTop9：二叉樹的遍歷n真題分析（2006年9月）對下列二叉樹，進行中序遍歷的結(jié)果是A、ACBDFEGB、ACBDFGEC、ABDCGEFD、FCADBEGFCEADBGATop9：二叉樹的遍歷n真題分析（2007年9月）對下列二叉樹進行中序遍歷的結(jié)果為FCEADBGHPA CBDF

30、EHGPTop9：二叉樹的遍歷n真題分析（2008年9月）對下列二叉樹進行中序遍歷的結(jié)果是 ADXBCEFYZDBXEAYFZCTop9：二叉樹的遍歷n練習(xí)題1、已經(jīng)二叉樹后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷順序是A、acbedB、decabC、deabcD、cedba C d a b eDTop9：二叉樹的遍歷n練習(xí)題2、在先左后右的原則下，根據(jù)訪問根結(jié)點的次序，二叉樹的遍歷可以分為三種：前序遍歷、和后序遍歷。中序遍歷中序遍歷Top10：順序查找n知識點1.順序查找是一種最基本和最簡單的查找方法，它的思路就是拿給定的值與表中的元素逐一比較，直到兩者相同，表示查找成

31、功，否則查找失敗。2.對于大的線性表而言，順序查找的效率很低。但是對于無序線性表，或者線性表雖然有序，但是采用鏈?zhǔn)酱鎯r，都只能使用順序查找。Top10：順序查找63801755最壞情況：比較最壞情況：比較n次次66380175最好情況：比較最好情況：比較1次次Top10：順序查找n真題分析（2006年9月）在長度為64的有序線性表中進行順序查找，最壞情況下，需要比較的次數(shù)為A、63B、64C、6D、7BTop10：順序查找n真題分析（2005年4月）對于長度為n的線性表進行順序查找，在最壞情況下，所需要比較的次數(shù)為A、log2nB、n/2 C、nD、n+1CTop10：順序查找n練習(xí)題1、對

32、長度為n的無序線性表進行查找，應(yīng)該使用查找。順序順序Top11：二分法查找n知識點二分查找是針對順序存儲的有序表順序存儲的有序表進行查找的簡單、有效而又較常用的方法。06356817最壞情況：比較最壞情況：比較log2n次次05356817最好情況：比較最好情況：比較1次次Top11：二分法查找n真題分析（2005年9月）下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法查找的是A、順序存儲的有序線性表B、線性鏈表C、二叉鏈表D、有序線性鏈表ATop11：二分法查找n真題分析（2008年9月）在長度為n的有序線性表中進行二分查找，最壞情況下需要比較的次數(shù)是A、O(N)B、O(n2)C、O(log2n)D、O(n lo

33、g2n)CTop11：二分法查找n練習(xí)題1、有一個有序表為1，3，9，12，32，41，45，62，75，77，82，95，100當(dāng)二分查找為82的結(jié)點時，次比較后查找成功。A、1B、2C、4D、8CTop12：排序n知識點排序是將一個無序序列整理成一個按值非遞減順序排列的序列。03568176380175Top12：排序n知識點常用的排序方法有：1.交換類排序 冒泡排序法，需要比較的次數(shù)為n(n-1)/2 快速排序法,最壞情況需要比較n(n-1)/2次2.插入類排序 簡單插入排序法，最壞情況需要比較n(n-1)/2次 希爾排序法，最壞情況需要比較O（log21.5）次3.選擇類排序 簡單選擇

34、排序法，最壞需要比較n(n-1)/2次 堆排序法，最壞情況需要O(nlog2n)次比較Top12：排序（冒泡）6380175原始序列第一遍3608517第二遍065817第三遍33065第四遍305第五遍30Top12：排序n真題分析（2006年4月）對長度為10的線性表進行冒泡排序，最壞情況下需要比較的次數(shù)是n(n-1)/2=45Top12：排序n真題分析（2005年4月）對于長度為n的線性表，在最壞情況下，下列各排序法所對應(yīng)的比較次數(shù)正確的是A、冒泡排序n/2B、冒泡排序 nC、快速排序nD、快速排序為n(n-1)/2DTop12：排序n真題分析（2007年9月）冒泡排序在最壞情況下的比較

35、次數(shù)是A、 n（n+1）/2 B、 nlog2nC、 n（n-1）/2 D、 n/2CTop12：排序n真題分析（2008年4月）對長度為n的線性表排序，在最壞情況下，比較次數(shù)不是n(n-1)/2的排序方法是A、快速排序B、冒泡排序 C、直接插入排序 D、堆排序 DTop12：排序n練習(xí)題1、已經(jīng)數(shù)據(jù)表A中每個元素距其最終位置不遠，為節(jié)省時間，應(yīng)采用的排序算法是A、堆排序B、插入類排序C、快速排序D、直接選擇排序BTop12：排序n練習(xí)題2、在待排序的元素序列基本有序的前提下，效率最高的排序方法是A、冒泡排序B、選擇排序C、快速排序D、歸并排序A程序設(shè)計基礎(chǔ)高頻考點nTop1：程序設(shè)計方法與風(fēng)

36、格nTop2：結(jié)構(gòu)化程序設(shè)計nTop3：面向?qū)ο蠓椒═op1：程序設(shè)計方法與風(fēng)格n知識點養(yǎng)成良好的程序設(shè)計風(fēng)格（清晰第一，效率第二清晰第一，效率第二），主要考慮下述要素：1.源程序文檔化符號命名要見名知義要有正確的注釋程序?qū)哟吻逦?.數(shù)據(jù)說明的方法數(shù)據(jù)說明的次序規(guī)范說明語句中變量安排有序化使用注釋說明復(fù)雜數(shù)據(jù)結(jié)構(gòu)3.語句的結(jié)構(gòu)：程序應(yīng)簡單易懂，語句構(gòu)造應(yīng)該簡單直接，避免濫用goto語句。4.輸入和輸出：輸入輸出的格式應(yīng)盡可能方便用戶使用。Top1：程序設(shè)計方法與風(fēng)格n真題分析（2006年9月）下列選項中不符合良好的程序設(shè)計風(fēng)格的是A、源程序要文檔化B、數(shù)據(jù)說明的次序要規(guī)范化C、避免濫用goto

37、語句D、模塊設(shè)計要保證高耦合，低內(nèi)聚DTop1：程序設(shè)計方法與風(fēng)格n真題分析（2007年9月）下列敘述中，不符合良好程序設(shè)計風(fēng)格的是A、程序的效率第一，清晰第二 B、程序的可讀性好 C、程序中有必要的注釋 D、輸入數(shù)據(jù)前要有提示信息 ATop1：程序設(shè)計方法與風(fēng)格n練習(xí)題1、對建立良好的程序設(shè)計風(fēng)格，下面描述正確的是A、程序應(yīng)簡單、清晰、可讀性好B、符號名的命名只要符合語法C、充分考慮程序的執(zhí)行效率D、程序的注釋可有可無ATop2：結(jié)構(gòu)化程序設(shè)計n知識點1. 結(jié)構(gòu)化程序設(shè)計主要目的是使程序結(jié)構(gòu)良好、易讀、易理解、易維護。主要原則包括： 自頂向下 逐步求精 模塊化 限制使用goto語句Top2：

38、結(jié)構(gòu)化程序設(shè)計n知識點2. 結(jié)構(gòu)化程序設(shè)計方法可用三種基本結(jié)構(gòu)實現(xiàn)： 順序結(jié)構(gòu) 選擇結(jié)構(gòu)（條件） 循環(huán)結(jié)構(gòu)Top2：結(jié)構(gòu)化程序設(shè)計n知識點3.在結(jié)構(gòu)化程序?qū)嵤┲?，要把握如下要素?使用程序語言中的順序、選擇、循環(huán)等控制結(jié)構(gòu)表示程序的控制邏輯。 選用的控制結(jié)構(gòu)只準(zhǔn)許有一個入口和一個出口。 程序語句組成容易識別的程序?qū)ｍ?，每塊只有一個入口和一個出口。 復(fù)雜結(jié)構(gòu)應(yīng)該用嵌套的基本控制結(jié)構(gòu)進行組合嵌套來實現(xiàn)。Top2：結(jié)構(gòu)化程序設(shè)計n真題分析（2006年4月）下列選項中，不屬于結(jié)構(gòu)化程序設(shè)計方法的是A、自頂向下B、逐步求精C、模塊化D、可復(fù)用D可復(fù)用性是指在軟件不加修改或稍加修改可復(fù)用性是指在軟件不加修

39、改或稍加修改就可在不同軟件開發(fā)過程中重復(fù)使用的性質(zhì)。就可在不同軟件開發(fā)過程中重復(fù)使用的性質(zhì)。軟件可復(fù)用性是軟件工程追求的目標(biāo)之一。軟件可復(fù)用性是軟件工程追求的目標(biāo)之一。面向?qū)ο蠓椒ň哂锌蓮?fù)用性。面向?qū)ο蠓椒ň哂锌蓮?fù)用性。Top2：結(jié)構(gòu)化程序設(shè)計n真題分析（2008年4月）結(jié)構(gòu)化程序設(shè)計的基本原則不包括A、多態(tài)性 B、自頂向下C、模塊化D、逐步求精 ATop2：結(jié)構(gòu)化程序設(shè)計n真題分析（2007年9月）下列敘述中，不符合良好程序設(shè)計風(fēng)格的是A、程序的效率第一，清晰第二 B、程序的可讀性好 C、程序中有必要的注釋 D、輸入數(shù)據(jù)前要有提示信息 ATop2：結(jié)構(gòu)化程序設(shè)計n練習(xí)題1、下列描述中，符合結(jié)

40、構(gòu)化程序設(shè)計風(fēng)格的是A、使用順序、選擇和循環(huán)三種基本控制結(jié)構(gòu)表示程序的控制邏輯B、模塊只有一個入口，可以有多個出口C、注重提高程序的執(zhí)行效率D、不使用goto語句ATop3：面向?qū)ο蠓椒╪知識點1.對象（Object）：對象是用來表示客觀世界中的任何實體。面向?qū)ο蟮某绦蛟O(shè)計方法中涉及的對象是系統(tǒng)中用來描述客觀事物的一個實體，是構(gòu)成系統(tǒng)的一個基本單位，它是由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成一組操作組成。2.類（Class）和實例（Instance）：將屬性、操作類似的對象歸為類，類是具有共同屬性、類是具有共同屬性、共同方法的對象的集合共同方法

41、的對象的集合；一個具體對象稱為一個具體對象稱為類的實例。類的實例。Top3：面向?qū)ο蠓椒╪知識點3.消息（Message）：面向?qū)ο蟮氖澜缡峭ㄟ^對象與對象間彼此的相互合作來推動的，對象間的這種相互合作需要一個機制相互合作需要一個機制協(xié)助進行，這個機制稱為稱為“消息消息”。“消息”是一個實例與另一個實例之間傳遞的信息，它請求對象執(zhí)行某一處理或回答某一要求的信息，它統(tǒng)一了數(shù)據(jù)流和控制流。Top3：面向?qū)ο蠓椒╪知識點4.繼承（Inheritance）：繼承是面向?qū)ο蟮姆椒ǖ囊粋€主要特征。繼承是使用已有的類定義作為基礎(chǔ)（直接獲得已有的性質(zhì)和特征）建立新類的定義技術(shù)。已有的類可以當(dāng)做基類使用，則新類可

42、當(dāng)做派生類使用。5.多態(tài)性（Polymorphism）：對象根據(jù)所接受的消息而做出動作，同樣的消息被不同的對象接受時可導(dǎo)致完全不同的行動，該現(xiàn)象稱為多態(tài)性。6.封裝性：外面只有看到對象的外部特征，對象的內(nèi)部狀態(tài)對外是不可見的。繼承性、多態(tài)性和封裝性是面向?qū)ο蟪绦蛟O(shè)計的繼承性、多態(tài)性和封裝性是面向?qū)ο蟪绦蛟O(shè)計的3 3個主要特征。個主要特征。Top3：面向?qū)ο蠓椒╪真題分析（2007年4月）下面選項中不屬于面向?qū)ο筇卣鞯氖茿、繼承性B、多態(tài)性C、類比性D、封閉性DTop3：面向?qū)ο蠓椒╪真題分析（2006年4月）在面向?qū)ο蠓椒ㄖ?，描?是具有相似屬性與操作的一組對象。類類Top3：面向?qū)ο蠓椒╪真

43、題分析（2005年4月）在面向?qū)ο蠓椒ㄖ?，類的實例稱為對象對象Top3：面向?qū)ο蠓椒╪真題分析（2007年9月）在面向?qū)ο蠓椒ㄖ校瑢崿F(xiàn)信息隱蔽是依靠A、對象的繼承B、對象的多態(tài)C、對象的封裝D、對象的分類CTop3：面向?qū)ο蠓椒╪真題分析（2008年9月）在面向?qū)ο蠓椒ㄖ?，不屬于“對象”基本特點的是A、一致性B、分類性C、多態(tài)性D、標(biāo)識唯一性ATop3：面向?qū)ο蠓椒╪練習(xí)題1、在面向?qū)ο蠓椒ㄖ校愔g共享屬性和操作的機制稱為繼承繼承Top3：面向?qū)ο蠓椒╪練習(xí)題2、在面向?qū)ο蟮脑O(shè)計中，用來請求對象執(zhí)行某一處理或回答某些信息的要求稱為消息消息軟件工程基礎(chǔ)高頻考點nTop1：軟件工程基本概念nTo

44、p2：軟件生命周期nTop3：軟件設(shè)計基本概念nTop4：軟件設(shè)計的基本原理nTop5：結(jié)構(gòu)化分析方法nTop6：軟件測試的目的和測試的準(zhǔn)則nTop7：軟件測試的方法和實施nTop8：程序的調(diào)試Top1：軟件工程基本概念n知識點1.軟件工程概念的出現(xiàn)源自軟件危機軟件危機。2.軟件工程的主要思想：在軟件開發(fā)過程中應(yīng)用工程在軟件開發(fā)過程中應(yīng)用工程化原則?；瓌t。3.軟件工程的主要研究對象：軟件開發(fā)與維護的技術(shù)、技術(shù)、方法、工具和管理方法、工具和管理等方面。4.軟件的定義：程序、數(shù)據(jù)及相關(guān)文檔的集合程序、數(shù)據(jù)及相關(guān)文檔的集合。5.軟件工程三要素：方法、工具和過程。方法、工具和過程。方法：是完成軟件工

45、程項目的技術(shù)手段。方法：是完成軟件工程項目的技術(shù)手段。工具：支持軟件的開發(fā)、管理、文檔生成。工具：支持軟件的開發(fā)、管理、文檔生成。過程：支持軟件開發(fā)的各個環(huán)節(jié)的控制、管理。過程：支持軟件開發(fā)的各個環(huán)節(jié)的控制、管理。Top1：軟件工程基本概念n真題分析（2005年9月）下列描述正確的是A、軟件工程只是解決軟件項目的管理問題B、軟件工程主要解決軟件產(chǎn)品的生產(chǎn)率問題C、軟件工程的主要思想是強調(diào)在軟件開發(fā)中應(yīng)用工程化原則D、軟件工程只是解決軟件開發(fā)中的技術(shù)問題CTop1：軟件工程基本概念n真題分析（2005年4月）下列描述正確的是A、程序就是軟件B、軟件開發(fā)不受計算機系統(tǒng)的限制C、軟件既是邏輯實體、又

46、是物理實體D、軟件是程序、數(shù)據(jù)和相關(guān)文檔的集合DTop1：軟件工程基本概念n真題分析（2007年9月）軟件是指A、程序B、程序和文檔C、算法加數(shù)據(jù)結(jié)構(gòu)D、程序、數(shù)據(jù)和相關(guān)文檔的集合DTop1：軟件工程基本概念n真題分析（2008年9月）軟件工程三要素包括方法、工具和過程，其中支持軟件開發(fā)的各個環(huán)節(jié)的控制和管理。過程過程Top1：軟件工程基本概念n練習(xí)題1、下列不屬于軟件工程三要素的是A、工具B、過程C、方法D、環(huán)境DTop1：軟件工程基本概念n練習(xí)題2、軟件工程的出現(xiàn)是由于A、程序設(shè)計方法學(xué)的影響B(tài)、軟件產(chǎn)業(yè)化的需要C、軟件危機的出現(xiàn)D、計算機的發(fā)展CTop2：軟件生命周期n知識點1.軟件生命

47、周期：產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的過程。2.軟件生命周期的三個階段：軟件定義定義、軟件開發(fā)開發(fā)及軟件運行維護維護。3.軟件生命周期的主要活動：可行性研究與計劃制定需要分析軟件設(shè)計軟件實現(xiàn)軟件測試運行和維護Top2：軟件生命周期可行性研究初步項目計劃需求分析概要設(shè)計詳細設(shè)計實現(xiàn)測試使用維護退役定義階段開發(fā)階段維護階段需求獲取需求分析編寫需要規(guī)格說明書需求評審正確性可行性必要性無岐義性完整性可驗證性Top2：軟件生命周期n真題分析（2007年4月）軟件生命周期可分為多個階段，一般分為定義階段、開發(fā)階段和維護階段。編碼和測試屬于階段。開發(fā)開發(fā)Top2：軟件生命周期n真題分析（2006年

48、9月）下列選項中不屬于軟件生命周期開發(fā)階段任務(wù)的是A、軟件測試B、概要設(shè)計C、軟件維護D、詳細設(shè)計CTop2：軟件生命周期n真題分析（2005年9月）下列敘述中正確的是A、軟件交付使用后還需要進行維護B、軟件一旦交付使用后就不需要再進行維護C、軟件交付使用后其生命周期就結(jié)束D、軟件維護是指修復(fù)程序中被破壞的指令A(yù)Top2：軟件生命周期n真題分析（2007年9月）軟件需求規(guī)格說明書應(yīng)具有完整性、無歧義性、正確性、可驗證性、可修改性等特性，其中最重要的無歧義性無歧義性Top2：軟件生命周期n真題分析（2008年4月）在軟件開發(fā)中，需求分析階段產(chǎn)生的主要文檔是 A、可行性分析報告B、軟件需求規(guī)格說明

49、書 C、概要設(shè)計說明書D、集成測試計劃 BTop2：軟件生命周期n練習(xí)題1、軟件生命周期中所花費用最多的階段是A、詳細設(shè)計B、軟件編碼C、軟件測試D、軟件維護DTop2：軟件生命周期n練習(xí)題2、軟件開發(fā)的結(jié)構(gòu)化生命周期方法將軟件生命周期劃分為A、定義、開發(fā)、運行維護B、設(shè)計階段、編程階段、測試階段C、總體設(shè)計、詳細設(shè)計、編程調(diào)試D、需求分析、功能定義、系統(tǒng)設(shè)計ATop3：軟件設(shè)計基本概念n知識點1.從工程管理角度來看，軟件設(shè)計包括：概要設(shè)計概要設(shè)計和詳細設(shè)計詳細設(shè)計。2.從技術(shù)角度來看，軟件設(shè)計包括：結(jié)構(gòu)設(shè)計：定義軟件系統(tǒng)各主要部件之間的關(guān)系。數(shù)據(jù)設(shè)計：將分析時創(chuàng)建的模型轉(zhuǎn)換為數(shù)據(jù)結(jié)構(gòu)的定義接

50、口設(shè)計：描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信過程設(shè)計：把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的描述過程。Top3：軟件設(shè)計基本概念n真題分析（2006年9月）從工程管理角度看，軟件設(shè)計一般分為兩步完成，它們是A、概要設(shè)計與詳細設(shè)計B、數(shù)據(jù)設(shè)計與接口設(shè)計C、軟件結(jié)構(gòu)設(shè)計與數(shù)據(jù)設(shè)計D、過程設(shè)計與數(shù)據(jù)設(shè)計ATop3：軟件設(shè)計基本概念n練習(xí)題1、軟件設(shè)計包括軟件的結(jié)構(gòu)、數(shù)據(jù)接口和過程設(shè)計，其中軟件的過程設(shè)計是指A、模塊間的關(guān)系B、系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程描述C、軟件層次結(jié)構(gòu)D、軟件開發(fā)過程BTop4：軟件設(shè)計的基本原理n知識點1.軟件設(shè)計中應(yīng)遵循的基本原理與軟件設(shè)計有關(guān)的概念 抽象抽象：把事

51、物的本質(zhì)的共同特性提取出來而不考慮其他細節(jié)。 模塊化模塊化：把一個待開發(fā)的軟件分解成若干個小的簡單的部分。 信息隱蔽信息隱蔽：一個模塊內(nèi)部包含的信息，對于不需要這些信息的其它模塊來說是不能訪問的。 模塊獨立性模塊獨立性：每個模塊只完成系統(tǒng)要求的獨立的子功能，并且與其它模塊的聯(lián)系最少且接口簡單。Top4：軟件設(shè)計的基本原理n知識點2.衡量模塊獨立性的兩個標(biāo)準(zhǔn) 內(nèi)聚性：一個模塊內(nèi)部各元素之間的彼此結(jié)合的緊密程序。 耦合性：模塊間相互連接的緊密程序。軟件設(shè)計應(yīng)盡量做到：高內(nèi)聚，低耦合高內(nèi)聚，低耦合Top4：軟件設(shè)計的基本原理n知識點3.結(jié)構(gòu)圖（SC）是描述軟件結(jié)構(gòu)的圖形工具。模塊用一個矩形表示，箭頭

52、表示模塊間的調(diào)用關(guān)系。在結(jié)構(gòu)圖中，還可以用帶注釋的箭頭表示模塊調(diào)用過程中來回傳遞的信息。Top4：軟件設(shè)計的基本原理n真題分析（2007年4月）在結(jié)構(gòu)化程序設(shè)計中，模塊劃分的原則是A、各模塊應(yīng)包括盡可能多的功能B、各模塊的規(guī)模應(yīng)盡量大C、各模塊之間的聯(lián)系應(yīng)盡量緊密D、模塊內(nèi)部應(yīng)具有高內(nèi)聚度，模塊之間具有低耦合度DTop4：軟件設(shè)計的基本原理n真題分析（2006年9月）下列軟件系統(tǒng)結(jié)構(gòu)圖的寬度為ABDCEF3Top4：軟件設(shè)計的基本原理n真題分析（2006年4月）兩個或兩個以上模塊間關(guān)聯(lián)的緊密程度稱為A、耦合度B、內(nèi)聚度C、復(fù)雜度D、數(shù)據(jù)傳輸性ATop4：軟件設(shè)計的基本原理n真題分析（2005年

53、4月）為了使模塊盡可能獨立，要求A、模塊的內(nèi)聚程度要盡量高，各模塊間的耦合程度要盡量強B、模塊的內(nèi)聚程度要盡量高，各模塊間的耦合程度要盡量弱C、模塊的內(nèi)聚程度要盡量低，各模塊間的耦合程度要盡量弱D、模塊的內(nèi)聚程度要盡量低，各模塊間的耦合程度要盡量強BTop4：軟件設(shè)計的基本原理n真題分析（2008年4月）軟件設(shè)計中模塊劃分應(yīng)遵循的準(zhǔn)則是 A、低內(nèi)聚低耦合 B、高內(nèi)聚低耦合 C、低內(nèi)聚高耦合D、高內(nèi)聚高耦合 BTop4：軟件設(shè)計的基本原理n練習(xí)題1、軟件設(shè)計中，有利于提高模塊獨立性的一個準(zhǔn)則是A、低內(nèi)聚低耦合B、低內(nèi)聚高耦合C、高內(nèi)聚低耦合D、高內(nèi)聚高耦合CTop5：結(jié)構(gòu)化分析方法n知識點1.結(jié)

54、構(gòu)化分析方法的實質(zhì)：著眼于數(shù)據(jù)流著眼于數(shù)據(jù)流，自自頂向下頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖數(shù)據(jù)流圖和數(shù)據(jù)字典數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型。2.結(jié)構(gòu)化分析的常用工具有： 數(shù)據(jù)流圖 數(shù)據(jù)字典 判定樹 判定表結(jié)構(gòu)化分析的核心Top5：結(jié)構(gòu)化分析方法n知識點3. 常用的過程設(shè)計（詳細設(shè)計階段）工具有： 圖形工具：程序流程圖、N-S圖、PAD、HIPO 表格工具：判定表 語言工具：PDL（偽碼）Top5：結(jié)構(gòu)化分析方法數(shù)據(jù)流圖：描述數(shù)據(jù)處理過程的工具，是需求階段需求階段常用的結(jié)構(gòu)化分析工具。數(shù)據(jù)流圖的數(shù)據(jù)流圖的主要圖形元素主要圖形元素加工（轉(zhuǎn)換）加工（轉(zhuǎn)換）數(shù)據(jù)流數(shù)據(jù)流存儲文件（

55、數(shù)據(jù)源）存儲文件（數(shù)據(jù)源）源，潭源，潭Top5：結(jié)構(gòu)化分析方法程序流程圖：是一種傳統(tǒng)的、應(yīng)用廣泛的軟件過程設(shè)計表示工具，通常也稱為程序框圖。程序流程圖的程序流程圖的主要圖形元素主要圖形元素邏輯條件邏輯條件控制流控制流加工步驟加工步驟Top5：結(jié)構(gòu)化分析方法n真題分析（2007年4月）在結(jié)構(gòu)化分析使用的數(shù)據(jù)流圖（DFD）中，利用對其中的圖形元素進行確切解釋。數(shù)據(jù)詞典（數(shù)據(jù)詞典（DD）Top5：結(jié)構(gòu)化分析方法n真題分析（2005年9月）在軟件設(shè)計中，不屬于過程設(shè)計工具的是A、PDL（過程設(shè)計語言）B、PAD圖（問題分析圖）C、N-S圖D、DFD圖（數(shù)據(jù)流程圖）DTop5：結(jié)構(gòu)化分析方法n真題分析（

56、2008年4月）程序流程圖中指有箭頭的線段表示的是A、圖元關(guān)系B、數(shù)據(jù)流C、控制流D、調(diào)用關(guān)系CTop5：結(jié)構(gòu)化分析方法n真題分析（2008年9月）數(shù)據(jù)流圖中帶有箭頭的線段表示的是A、控制流B、事件驅(qū)動C、模塊調(diào)用D、數(shù)據(jù)流DTop5：結(jié)構(gòu)化分析方法n真題分析（2008年9月）在軟件開發(fā)中，需求分析階段可以使用的工具是A、N-S圖B、DFD圖C、PAD圖D、程序流程圖程序流程圖BTop5：結(jié)構(gòu)化分析方法n練習(xí)題1、下列不屬于結(jié)構(gòu)化分析的常用工具的是A、數(shù)據(jù)流圖B、數(shù)據(jù)字典C、判定樹D、PAD圖DTop5：結(jié)構(gòu)化分析方法n練習(xí)題2、下列敘述中，不屬于結(jié)構(gòu)化分析方法的是A、面向數(shù)據(jù)流的結(jié)構(gòu)化分析方

57、法B、面向數(shù)據(jù)結(jié)構(gòu)的Jackson方法C、面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開發(fā)方法D、面向?qū)ο蟮姆治龇椒―Top6：軟件測試的目的和測試的準(zhǔn)則n知識點1.軟件測試定義：使用人工或自動手段來運行或測試某個系統(tǒng)的過程，其目的在于檢測它是否滿足規(guī)定的需求或是弄清預(yù)期結(jié)果與實際結(jié)果之間的差別。2.軟件測試的目的：為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程。Top6：軟件測試的目的和測試的準(zhǔn)則3.軟件測試的準(zhǔn)則： 所有測試都應(yīng)該追溯到需求 嚴(yán)格執(zhí)行測試計劃，排除測試的隨意性 充分注意到測試中的群集現(xiàn)象 程序員應(yīng)盡量避免檢查自己的程序 窮舉測試不可能Top6：軟件測試的目的和測試的準(zhǔn)則n真題分析（2007年4月）下列敘述中

58、正確的是A、軟件測試的主要目的是發(fā)現(xiàn)程序中的錯誤B、軟件測試的主要目的是確定程序中的位置C、為了提高軟件測試的效率，最好由程序員自己來完成測試的工作D、軟件測試是為了證明軟件沒有錯誤ATop6：軟件測試的目的和測試的準(zhǔn)則n真題分析（2006年4月）下列敘述中正確的是A、軟件測試應(yīng)該由程序開發(fā)者來完成B、程序經(jīng)調(diào)試后一般不需要再測試C、軟件維護只包括對程序代碼的維護D、上述三種說法都不正確DTop6：軟件測試的目的和測試的準(zhǔn)則n真題分析（2005年4月）下列對于軟件測試的描述中正確的是A、軟件測試的目的是證明程序是否正確B、軟件測試的目的是使程序運行結(jié)果正確C、軟件測試的目的是盡可能地發(fā)現(xiàn)程序中

59、的錯誤D、軟件測試的目的是使程序符合結(jié)構(gòu)化原則CTop6：軟件測試的目的和測試的準(zhǔn)則n練習(xí)題1、的目的是暴露錯誤，評價程序的可靠性；而調(diào)試的目的是發(fā)現(xiàn)錯誤的位置并改正錯誤。測試測試Top7：軟件測試的方法和實施n知識點1.軟件測試的方法和技術(shù)分類從是否需要執(zhí)行被測試軟件的角度，分為：靜態(tài)測試靜態(tài)測試動態(tài)測試動態(tài)測試按功能劃分，分為：白盒測試白盒測試黑盒測試黑盒測試Top7：軟件測試的方法和實施靜態(tài)測試靜態(tài)測試代碼檢查代碼檢查靜態(tài)結(jié)構(gòu)分析靜態(tài)結(jié)構(gòu)分析代碼質(zhì)量度量代碼質(zhì)量度量動態(tài)測試動態(tài)測試白盒測試白盒測試黑盒測試黑盒測試Top7：軟件測試的方法和實施白盒測試白盒測試邏輯覆蓋邏輯覆蓋基本路徑測試基

60、本路徑測試語句覆蓋語句覆蓋路徑覆蓋路徑覆蓋判定覆蓋判定覆蓋條件覆蓋條件覆蓋判斷判斷-條件覆蓋條件覆蓋又稱為（結(jié)構(gòu)測試又稱為（結(jié)構(gòu)測試/邏輯驅(qū)動測試）邏輯驅(qū)動測試）主要完成軟件內(nèi)部操作的驗證。主要完成軟件內(nèi)部操作的驗證。Top7：軟件測試的方法和實施黑盒測試黑盒測試等價類劃分法等價類劃分法邊界值分析法邊界值分析法有效等價類有效等價類無效等價類無效等價類又稱為（功能測試又稱為（功能測試/數(shù)據(jù)驅(qū)動測試）數(shù)據(jù)驅(qū)動測試）主要測試軟件已經(jīng)實現(xiàn)的功能是否滿足需求，主要測試軟件已經(jīng)實現(xiàn)的功能是否滿足需求，主要用于軟件確認(rèn)測試。主要用于軟件確認(rèn)測試。錯誤推測法錯誤推測法因果圖因果圖Top7：軟件測試的方法和實施