《全國計算機等級考試二級》由會員分享，可在線閱讀，更多相關(guān)《全國計算機等級考試二級（203頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、單擊此處編輯母版標題樣式,,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,,*,全國計算機等級考試二級,,C語言程序設計,,,考試方式,,筆試：90分鐘 100分,,題型：單選題（40題） 70分,,填空題（15題/空） 30分,,其中：基礎30分,,C程序70分,,上機：90分鐘 100分,,題型：填空 修改正確得分,,改錯 結(jié)果運行正確得分,,編程 結(jié)果運行正確得分,,試題結(jié)構(gòu)分析,二級C一直以來是整個二級考試中試題最多、難度最大、報考人數(shù)也最多的考試，但是從2008年4月份開始筆試由原來120分鐘減少到90分

2、鐘，所以二級C語言首次題數(shù)減少、單個題目難度下降(選擇題由原來的50個題目減少到40個，填空由原來的20空減少到15空，滿分100分保持不變)，從而試題整體難度下降。而上機考試時間由原來的60分鐘增加至90分鐘，但上機題目不僅不加難，反而降低難度。所以整個等級考試難度是下降的趨勢，08年4月以后開始，等級考試將沿襲這種題型和題量安排等。,,,,,筆試試題分類統(tǒng)計,二級C各章節(jié)知識點考察到的題目題號和分值分析：,,C語言初步知識 選擇11-13 共3分,,順序結(jié)構(gòu) 選擇14-16 填空7 共5分,,選擇結(jié)構(gòu) 選擇17-20 填空6 共6分,,循環(huán)結(jié)構(gòu) 選擇21、22 填空8 共6分,,函數(shù) 選擇

3、32、34 填空11、13 共8分,,指針/數(shù)組/字符串 選擇23-27、31、33、35、40 填空10-12 共24分,,預編譯與動態(tài)內(nèi)存 選擇28、39 共4分,,結(jié)構(gòu)與共用體 選擇29、36 填空14 共6分,,位運算 選擇38 共2分,,文件 選擇30、37 填空15 共6分,,數(shù)據(jù)結(jié)構(gòu)與算法 選擇5-7 填空2、3 共10分,,程序設計基礎 選擇2 共2分,,軟件工程基礎 選擇1、3、4 填空1 共8分,,數(shù)據(jù)庫設計基礎 選擇8-10 填空4、5 共10分,,其中：選擇1~10每題2分 選擇11～20每題1分 選擇21～40每題2分 填空1-15空每空2分,,試題特點,1、題數(shù)減少

4、,,以前一共50道選擇題、20個空的填空題，今年只有40道選擇題，15個空的填空題。試題數(shù)的減少，使考生有充足的時間分析和檢查題目。,,2、單個題目的難度下級。,,在本次二級C語言筆試試題中，未出現(xiàn)一些特別難的試題，比如沒有出現(xiàn)“指向指針的指 針作函數(shù)參數(shù)”等類型的試題。,,,備考建議,：,,大家可以看出，指針、數(shù)組、字符串無論在筆試還是上機都是重中之重，既是重點又是難點。C語言程序初步、順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)、函數(shù)是基礎。編譯預處理、作用域與存儲類、位運算、文件等是難點但不是重點，每年都會考到，但題量都不大。結(jié)構(gòu)體與共用體可以說比較重點又是難點。公共基礎部分除了程序設計基礎這一部分，其

5、他三部分旗鼓相當，都是重點。,,考試內(nèi)容,,基礎部分30分,,程序設計70分,,上機100分,,基礎部分知識要點（30分）,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,,2. 程序設計基礎,,3. 軟件工程基礎,,4. 數(shù)據(jù)庫設計基礎,,計算機等級考試(二級公共基礎)考試大綱,◆ 基本要求,,1.掌握算法的基本概念。,,2.掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作。,,3.掌握基本排序和查找算法。,,4.掌握逐步求精的結(jié)構(gòu)化程序設計方法。,,5.掌握軟件工程的基本方法，具有初步應用相關(guān)技術(shù)進行軟件開發(fā)的能力。,,6.掌握數(shù)據(jù)庫的基本知識，了解關(guān)系數(shù)據(jù)庫的設計。,,計算機等級考試(二級公共基礎)考試大綱,◆ 考試內(nèi)容,,一、基

6、本數(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.順序查找與二分法查找算法;基本排序算法(交換類排序，選擇類排序，插入類排序)。,,計算機等級考試(二級公共基礎)考試大綱,◆ 考試內(nèi)容,,,二、程

7、序設計基礎,,1.程序設計方法與風格。,,2.結(jié)構(gòu)化程序設計。,,3.面向?qū)ο蟮某绦蛟O計方法，對象，方法，屬性及繼承與多態(tài)性。,,計算機等級考試(二級公共基礎)考試大綱,◆ 考試內(nè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)試。,,計算機等級考試(二級公共基礎)考試大綱,◆ 考試內(nèi)容,,,四、數(shù)據(jù)庫設計

8、基礎,,1.數(shù)據(jù)庫的基本概念：數(shù)據(jù)庫，數(shù)據(jù)庫管理系統(tǒng)，數(shù)據(jù)庫系統(tǒng)。,,2.數(shù)據(jù)模型，實體聯(lián)系模型及E-R圖，從E-R圖導出關(guān)系數(shù)據(jù)模型。,,3.關(guān)系代數(shù)運算，包括集合運算及選擇、投影、連接運算，數(shù)據(jù)庫規(guī)范化理論。,,4.數(shù)據(jù)庫設計方法和步驟：需求分析、概念設計、邏輯設計和物理設計的相關(guān)策略。,,◆ 考試方式,,公共基礎知識有10道選擇題和5道填空題，共三十分。,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,1.1 算法,,,算法：是指解題方案的準確而完整的描述。,,,算法不等于程序，也不等計算機方法，程序的編制不可能優(yōu)于算法的設計。,,,算法的基本特征,：是一組嚴謹?shù)囟x運算順序的規(guī)則，每一個規(guī)則都是有效的，是

9、明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。特征包括：,,（1）可行性；,,（2）確定性，算法中每一步驟都必須有明確定義，不充許有模棱兩可的解釋，不允許有多義性；,,（3）有窮性，算法必須能在有限的時間內(nèi)做完，即能在執(zhí)行有限個步驟后終止，包括合理的執(zhí)行時間的含義；,,（4）擁有足夠的情報。,,算法的基本要素：一是對數(shù)據(jù)對象的運算和操作；二是算法的控制結(jié)構(gòu)。,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,指令系統(tǒng)：一個計算機系統(tǒng)能執(zhí)行的所有指令的集合。,,基本運算和操作包括：算術(shù)運算、邏輯運算、關(guān)系運算、數(shù)據(jù)傳輸。,,,算法的控制結(jié)構(gòu),：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。,,算法基本設計方法：列舉法、歸納法、遞推、遞歸、減斗

10、遞推技術(shù)、回溯法。,,,算法復雜度,：算法時間復雜度和算法空間復雜度。,,算法時間復雜度是指執(zhí)行算法所需要的計算工作量。,,算法空間復雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,算法考試方式及題型分析,,單選題,,算法的時間復雜度是指( ),,A)執(zhí)行算法程序所需要的時間,,B)算法程序的長度,,C)算法執(zhí)行過程中所需要的基本運算次數(shù),,D)算法程序中的指令條數(shù),C,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,下面敘述正確的是 ( ),,A. 算法的執(zhí)行效率與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān),,B. 算法的空間復雜度是指算法程序中指令（或語句）的條數(shù),,C. 算法的有窮性是指

11、算法必須能在執(zhí)行有限個步驟之后終止,,D. 以上三種描述都不對,C,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,算法的空間復雜度是指 ( ),,A. 算法程序的長度,,B. 算法程序中的指令條數(shù),,C. 算法程序所占的存儲空間,,D. 算法執(zhí)行過程中所需要的存儲空間,D,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,結(jié)構(gòu)化程序設計所規(guī)定的三種基本控制結(jié)構(gòu)是( ),,A)輸入、處理、輸出,,B)樹形、網(wǎng)形、環(huán)形,,C)順序、選擇、循環(huán),,D)主程序、子程序、函數(shù),C,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,算法一般都可以用哪幾種控制結(jié)構(gòu)組合而成。( ),,A. 循環(huán)、分支、遞歸,,B. 順序、循環(huán)、嵌套,,C. 循環(huán)

12、、遞歸、選擇,,D. 順序、選擇、循環(huán),D,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,在下列選項中，哪個不是一個算法一般應該具有的基本特征( ),,A. 確定性,,B. 可行性,,C. 無窮性,,D. 擁有足夠的情報,C,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,在計算機中，算法是指( ),,A. 查詢方法,,B. 加工方法,,C. 解題方案的準確而完整的描述,,D. 排序方法,C,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,算法分析的目的是 ( ),,A. 找出數(shù)據(jù)結(jié)構(gòu)的合理性,,B. 找出算法中輸入和輸出之間的關(guān)系,,C. 分析算法的易懂性和可靠性,,D. 分析算法的效率以求改進,D,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,算法考試方式

13、及題型分析,,填空題,,算法的復雜度主要包括______復雜度和空間復雜度。 （時間）,,算法的基本特征是可行性、確定性、______和擁有足夠的情報。 （有窮性）,,實現(xiàn)算法所需的存儲單元多少和算法的工作量大小分別稱為算法的 ______。（空間復雜度和時間復雜度）,,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念,,數(shù)據(jù)結(jié)構(gòu)研究的三個方面：,,（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的,邏輯結(jié)構(gòu),；,,（2）在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即

14、數(shù)據(jù)的,存儲結(jié)構(gòu),；,,（3）對各種數(shù)據(jù)結(jié)構(gòu)進行的,運,算。,,數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。,,數(shù)據(jù)的邏輯結(jié)構(gòu)包含：,,（1）表示數(shù)據(jù)元素的信息；,,（2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。,,,數(shù)據(jù)的存儲結(jié)構(gòu)有順序、鏈接、索引等,。,,,線性結(jié)構(gòu),條件：,,（1）有且只有一個根結(jié)點；,,（2）每一個結(jié)點最多有一個前件，也最多有一個后件。,,,非線性結(jié)構(gòu),：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,1.3 線性表及其順序存儲結(jié)構(gòu),,線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號，元素之間的相對位置是線性的。,,在復雜線性表中，由若干項數(shù)據(jù)元素組成的數(shù)據(jù)元

15、素稱為記錄，而由多個記錄構(gòu)成的線性表又稱為文件。,,非空線性表的結(jié)構(gòu)特征：,,（1）且只有一個根結(jié)點a1，它無前件；,,（2）有且只有一個終端結(jié)點an，它無后件；,,（3）除根結(jié)點與終端結(jié)點外，其他所有結(jié)點有且只有一個前件，也有且只有一個后件。結(jié)點個數(shù)n稱為線性表的長度，當n=0時，稱為空表。,,線性表的順序存儲結(jié)構(gòu)具有以下兩個基本特點：,,（1）線性表中所有元素的所占的存儲空間是連續(xù)的；,,（2）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。,,ai的存儲地址為：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)為第一個元素的地址，k代表每個元素占的字節(jié)數(shù)。,,順序表的運

16、算：插入、刪除。,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,1.4 棧和隊列,,棧是限定在一端進行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。,,棧按照“先進后出”（FILO）或“后進先出”（LIFO）組織數(shù)據(jù)，棧具有記憶作用。用top表示棧頂位置，用bottom表示棧底。,,棧的基本運算：,,（1）插入元素稱為入棧運算；,,（2）刪除元素稱為退棧運算；,,（3）讀棧頂元素是將棧頂元素賦給一個指定的變量，此時指針無變化。,,隊列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。Rear指針指向隊尾，front指針指向隊頭。,,隊列是“先進行出”（FI

17、FO）或“后進后出”（LILO）的線性表。,,隊列運算包括,,（1）入隊運算：從隊尾插入一個元素；,,（2）退隊運算：從隊頭刪除一個元素。,,循環(huán)隊列：s=0表示隊列空，s=1且front=rear表示隊列滿,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,1.5 線性鏈表,,數(shù)據(jù)結(jié)構(gòu)中的每一個結(jié)點對應于一個存儲單元，這種存儲單元稱為存儲結(jié)點，簡稱結(jié)點。,,結(jié)點由兩部分組成：,,（1）用于存儲數(shù)據(jù)元素值，稱為數(shù)據(jù)域；,,（2）用于存放指針，稱為指針域，用于指向前一個或后一個結(jié)點。,,在鏈式存儲結(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系

18、是由指針域來確定的。,,鏈式存儲方式即可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。,,線性鏈表，HEAD稱為頭指針，HEAD=NULL（或0）稱為空表，如果是兩指針：左指針（Llink）指向前件結(jié)點，右指針（Rlink）指向后件結(jié)點。,,線性鏈表的基本運算：查找、插入、刪除。,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,1.6 樹與二叉樹,,樹是一種簡單的非線性結(jié)構(gòu)，所有元素之間具有明顯的層次特性。,,在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為父結(jié)點，沒有前件的結(jié)點只有一個，稱為樹的根結(jié)點，簡稱樹的根。每一個結(jié)點可以有多個后件，稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱為葉子結(jié)點。,,在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件

19、的個數(shù)稱為該結(jié)點的,度,，所有結(jié)點中最大的度稱為樹的,度,。樹的最大層次稱為樹的,深度,。,,,二叉樹的特點,：,,（1）非空二叉樹只有一個根結(jié)點；,,（2）每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,,二叉樹的基本性質(zhì),：,,（1）在二叉樹的第k層上，最多有2,k-1,(k≥1)個結(jié)點；,,（2）深度為m的二叉樹最多有2,m,-1個結(jié)點；,,（3）度為0的結(jié)點（即葉子結(jié)點）總是比度為2的結(jié)點多一個；,,（4）具有n個結(jié)點的二叉樹，其深度至少為[log,2,n]+1,其中[log,2,n]表示取log,2,n的整數(shù)部分；,,（5）具有n個結(jié)點的完全

20、二叉樹的深度為[log,2,n]+1；,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,（6）設完全二叉樹共有n個結(jié)點。如果從根結(jié)點開始，按層序（每一層從左到右）用自然數(shù)1，2，….n給結(jié)點進行編號（k=1,2….n），有以下結(jié)論：,,①若k=1，則該結(jié)點為根結(jié)點，它沒有父結(jié)點；若k>1，則該結(jié)點的父結(jié)點編號為INT(k/2)；,,②若2k≤n，則編號為k的結(jié)點的左子結(jié)點編號為2k；否則該結(jié)點無左子結(jié)點（也無右子結(jié)點）；,,③若2k+1≤n，則編號為k的結(jié)點的右子結(jié)點編號為2k+1；否則該結(jié)點無右子結(jié)點。,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,滿二叉樹,是指除最后一層外，每一層上的所有結(jié)點有兩個子結(jié)點，則k層上有2,k-1

21、,個結(jié)點深度為m的滿二叉樹有2,m,-1個結(jié)點。,,,完全二叉樹,是指除最后一層外，每一層上的結(jié)點數(shù)均達到最大值，在最后一層上只缺少右邊的若干結(jié)點。,,二叉樹存儲結(jié)構(gòu)采用鏈式存儲結(jié)構(gòu)，對于滿二叉樹與完全二叉樹可以按層序進行順序存儲。,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,二叉樹的遍歷,：,,（1）前序遍歷（DLR），首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹；,,（2）中序遍歷（LDR），首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹；,,（3）后序遍歷（LRD）首先遍歷左子樹，然后訪問遍歷右子樹，最后訪問根結(jié)點。,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,數(shù)據(jù)結(jié)構(gòu)考試題型分析,,選擇題,,數(shù)據(jù)的存儲結(jié)構(gòu)是指(

22、),,A. 數(shù)據(jù)所占的存儲空間量,,B. 數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示,,C. 數(shù)據(jù)在計算機中的順序存儲方式,,D. 存儲在外存中的數(shù)據(jù),B,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,下列敘述中，錯誤的是(),A)數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率密切相關(guān),,B)數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率無關(guān),,C)數(shù)據(jù)的存儲結(jié)構(gòu)在計算機中所占的空間不一定是連續(xù)的,,D)一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu),B,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的( ),A)存儲結(jié)構(gòu),,B)物理結(jié)構(gòu),,C)邏輯結(jié)構(gòu),,D)物理和存儲結(jié)構(gòu),C,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件

23、關(guān)系的復雜程度，一般將數(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),C,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,線性表L=(a1,a2,a3,…ai,…an)，下列說法正確的是(),A)每個元素都有一個直接前件和直接后件,,B)線性表中至少要有一個元素,,C)表中諸元素的排列順序必須是由小到大或由大到小,,D)除第一個元素和最后一個元素外，其余每個元素都有一個且只有一個直接前件和直接后件,D,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,線性表的順序存儲結(jié)構(gòu)和線性表的鏈式存儲結(jié)構(gòu)分別是(),A)順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu),,B)

24、順序存取的存儲結(jié)構(gòu)、隨機存取的存儲結(jié)構(gòu),,C)隨機存取的存儲結(jié)構(gòu)、隨機存取的存儲結(jié)構(gòu),,D)隨機存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu),B,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,以下數(shù)據(jù)結(jié)構(gòu)中不屬于線性數(shù)據(jù)結(jié)構(gòu)的是 ( ),A. 隊列,,B. 線性表,,C. 二叉樹,,D. 棧,C,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,下列關(guān)于棧的敘述正確的是( ),,A)棧是非線性結(jié)構(gòu),,B)棧是一種樹狀結(jié)構(gòu),,C)棧具有先進先出的特征,,D)棧具有后進先出的特征,D,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,下列敘述中正確的是( ),,A. 線性表是線性結(jié)構(gòu),,B. 棧與隊列是非線性結(jié)構(gòu),,C. 線性鏈表是非線性結(jié)構(gòu),,D. 二叉樹是線

25、性結(jié)構(gòu),A,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,用鏈表表示線性表的優(yōu)點是（）,,A. 便于插入和刪除操作,,B. 數(shù)據(jù)元素的物理順序與邏輯順序相同,,C. 花費的存儲空間較順序存儲少,,D. 便于隨機存取,A,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,串的長度是(),A)串中不同字符的個數(shù),,B)串中不同字母的個數(shù),,C)串中所含字符的個數(shù)且字符個數(shù)大于零,,D)串中所含字符的個數(shù),D,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,下列關(guān)于棧的敘述中正確的是( ),,A. 在棧中只能插入數(shù)據(jù),,B. 在棧中只能刪除數(shù)據(jù),,C. 棧是先進先出的線性表,,D. 棧是先進后出的線性表,D,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,下列關(guān)于隊列的敘述中正

26、確的是（ ）,,A. 在隊列中只能插入數(shù)據(jù),,B. 在隊列中只能刪除數(shù)據(jù),,C. 隊列是先進先出的線性表,,D. 隊列是先進后出的線性表,C,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,棧和隊列的共同點是（）,,A. 都是先進后出,,B. 都是先進先出,,C. 只允許在端點處插入和刪除元素,,D. 沒有共同點,C,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,棧底至棧頂依次存放元素A、B、C、D，在第五個元素E入棧前，棧中元素可以出棧，則出棧序列可能是（）,,A. ABCED,,B. DBCEA,,C. CDABE,,D. DCBEA,D,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,如果進棧序列為e1，e2，e3，e4，則可能的出棧序列是(

27、),A)e3,，,e1,，,e4,，,e2,,B)e2,，,e4,，,e3,，,e1,,C)e3,，,e4,，,e1,，,e2,,D),任意順序,B,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,在單鏈表中，增加頭結(jié)點的目的是( ),A)方便運算的實現(xiàn),,B)使單鏈表至少有一個結(jié)點,,C)標識表結(jié)點中首結(jié)點的位置,,D)說明單鏈表是線性表的鏈式存儲實現(xiàn),A,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,非空的循環(huán)單鏈表head的尾結(jié)點(由p所指向)，滿足(),A)p->next==NULL,,B)p==NULL,,C)p->next=head,,D)p=head,C,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,設樹T的度為4，其中度為1,2，3

28、,4的結(jié)點個數(shù)分別為4,2，1,1。則T中的葉子結(jié)點數(shù)為(),A)8,,B)7,,C)6,,D)5,A,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,在一棵二叉樹上第5層的結(jié)點數(shù)最多是（ ）,A. 8,,B. 16,,C. 32,,D. 15,B,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,樹是結(jié)點的集合，它的根結(jié)點數(shù)目是(),A),有且只有,1,,B)1,或多于,1,,C)0,或,1,,D)至少2,A,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,設一棵完全二叉樹共有699個結(jié)點，則在該二叉樹中的葉子結(jié)點數(shù)為( ),A. 349,,B. 350,,C. 255,,D. 351,B,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,若某二叉樹的前序遍歷訪問順序是a

29、bdgcefh，中序遍歷訪問順序是dgbaechf，則其后序遍歷的結(jié)點訪問順序是(),A)bdgcefha,,B)gdbecfha,,C)bdgaechf,,D)gdbehfca,D,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,已知二叉樹后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是（）,A. cedba,,B. acbed,,C. decab,,D. deabc,A,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,設有下列二叉樹：,,對此二叉樹前序遍歷的結(jié)果為(),A)ZBTYCPXA,,B)ATBZXCYP,,C)ZBTACYXP,,D)ATBZXCPY,B,T,A,B,Z,X,C,Y,P,,1. 基

30、本數(shù)據(jù)結(jié)構(gòu)與算法,設有下列二叉樹：,,對此二叉樹中序遍歷的結(jié)果為(),A)ABCDEF,,B)DBEAFC,,C)ABDECF,,D)DEBFCA,B,D,A,B,E,C,F,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式稱為數(shù)據(jù)的______。 (物理結(jié)構(gòu)）,,在先左后右的原則下，根據(jù)訪問根結(jié)點的次序，二叉樹的遍歷可以分為三種：前序遍歷、______遍歷和后序遍歷。 （中序）,,設一棵完全二叉樹共有500個結(jié)點，則在該二叉樹中有______個葉子結(jié)點。（250）,,數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的______結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)

31、構(gòu)。 （邏輯）,,棧的基本運算有三種：入棧、退棧和______。,,（讀棧頂元素#讀棧頂?shù)脑?讀出棧頂元素 ）,,,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的 ______以及對數(shù)據(jù)的操作運算。（存儲結(jié)構(gòu)）,,順序存儲方法是把邏輯上相鄰的結(jié)點存儲在物理位置______的存儲單元中。（相鄰）,,若二叉樹度為2的節(jié)點數(shù)有17個，則葉節(jié)點數(shù)為,,,。 （18）,,若串s="Program"，則其子串的數(shù)目是______。,,（29）,,1. 基

32、本數(shù)據(jù)結(jié)構(gòu)與算法,1.7 查找技術(shù),,順序查找的使用情況：,,（1）線性表為無序表；,,（2）表采用鏈式存儲結(jié)構(gòu)。,,二分法查找只適用于順序存儲的有序表，對于長度為n的有序線性表，最壞情況只需比較log,2,n次。,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,1.8 排序技術(shù),,排序是指將一個無序序列整理成按值非遞減順序排列的有序序列。,,交換類排序法：,,（1）冒泡排序法，需要比較的次數(shù)為n(n-1)/2；,,（2）快速排序法。,,插入類排序法：,,（1）簡單插入排序法，最壞情況需要n(n-1)/2次比較；,,（2）希爾排序法，最壞情況需要O(n1.5)次比較。,,選擇類排序法：,,（1）簡單選擇排序法,

33、最壞情況需要n(n-1)/2次比較；,,（2）堆排序法，最壞情況需要O(nlog,2,n)次比較。,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,排序與查找試題分析,,選擇題,,在待排序的元素序列基本有序的前提下，效 率最高的排序方法是(),A)冒泡排序,,B)選擇排序,,C)快速排序,,D)歸并排序,A,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,希爾排序法屬于哪一種類型的排序法 ( ),A. 交換類排序法,,B. 插入類排序法,,C. 選擇類排序法,,D. 建堆排序法,B,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,對長度為N的線性表進行順序查找，在最壞情況下所需要的比較次數(shù)為（ ）,A. N+1,,B. N,,C. (N+1)/2,,D

34、. N/2,B,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,在下列幾種排序方法中，要求內(nèi)存量最大的是（ ）,A. 插入排序,,B. 選擇排序,,C. 快速排序,,D. 歸并排序,D,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,已知數(shù)據(jù)表A中每個元素距其最終位置不遠，為節(jié)省時間，應采用的算法是（ ）,A. 堆排序,,B. 直接插入排序,,C. 快速排序,,D. 直接選擇排序,B,,1. 基本數(shù)據(jù)結(jié)構(gòu)與算法,在最壞情況下，堆排序需要比較的次數(shù)為______。 （O(nlog,2,n) ）,,在最壞情況下，冒泡排序的時間復雜度為______。,,,（,n(n-1)/2#n*(n-1)/2#

35、O(n(n-1)/2)#O(n*(n-1)/2),）,,,其他,,n個頂點的強連通圖的邊數(shù)至少有（）,,A. n-1,,B. n(n-1),,C. n,,D. n+1,C,,2. 程序設計基礎,,2.1 程序設計設計方法和風格,,良好的程序設計風格：,,1、源程序文檔化；,,2、數(shù)據(jù)說明的方法；,,3、語句的結(jié)構(gòu)；,,4、輸入和輸出。,,注釋分序言性注釋和功能性注釋，語句結(jié)構(gòu)清晰第一、效率第二。,,2. 程序設計基礎,,2.2 結(jié)構(gòu)化程序設計,,結(jié)構(gòu)化程序設計方法的四條原則是：1. 自頂向下；2. 逐步求精；3.模塊化；4.限制使用goto語句。,,結(jié)構(gòu)化程序的基本結(jié)構(gòu)和特點：,,（1）順序結(jié)

36、構(gòu)：一種簡單的程序設計，最基本、最常用的結(jié)構(gòu)；,,（2）選擇結(jié)構(gòu)：又稱分支結(jié)構(gòu)，包括簡單選擇和多分支選擇結(jié)構(gòu)，可根據(jù)條件，判斷應該選擇哪一條分支來執(zhí)行相應的語句序列；,,（3）重復結(jié)構(gòu)：又稱循環(huán)結(jié)構(gòu)，可根據(jù)給定條件，判斷是否需要重復執(zhí)行某一相同程序段。,,2. 程序設計基礎,,2.3 面向?qū)ο蟮某绦蛟O計,,面向?qū)ο蟮某绦蛟O計：以60年代末挪威奧斯陸大學和挪威計算機中心研制的SIMULA語言為標志。,,面向?qū)ο蠓椒ǖ膬?yōu)點：,,1、與人類習慣的思維方法一致；,,2、穩(wěn)定性好；,,3、可重用性好；,,4、易于開發(fā)大型軟件產(chǎn)品；,,5、可維護性好。,,對象是面向?qū)ο蠓椒ㄖ凶罨镜母拍?，可以用來表示客觀

37、世界中的任何實體，對象是實體的抽象。,,面向?qū)ο蟮某绦蛟O計方法中的對象是系統(tǒng)中用來描述客觀事物的一個實體，是構(gòu)成系統(tǒng)的一個基本單位，由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。,,,,2. 程序設計基礎,,屬性即對象所包含的信息，操作描述了對象執(zhí)行的功能，操作也稱為方法或服務。,,對象的基本特點：,,1、標識惟一性；,,2、分類性；,,3、多態(tài)性；,,4、封裝性；,,5、模塊獨立性好。,,類是指具有共同屬性、共同方法的對象的集合。所以類是對象的抽象，對象是對應類的一個實例。,,2. 程序設計基礎,,消息是一個實例與另一個實例之間傳遞的信息。,,消息的組成包括：,,1、接收消息的對象的名

38、稱；,,2、消息標識符，也稱消息名；,,3、零個或多個參數(shù)。,,繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復定義他們。,,繼承分單繼承和多重繼承。單繼承指一個類只允許有一個父類，多重繼承指一個類允許有多個父類。,,多態(tài)性是指同樣的消息被不同的對象接受時可導致完全不同的行動的現(xiàn)象。,,2. 程序設計基礎,,程序設計試題及分析,,選擇題,,下面對對象概念描述錯誤的是(),,A)任何對象都必須有繼承性,,B)對象是屬性和方法的封裝體,,C)對象間的通訊靠消息傳遞,,D)操作是對象的動態(tài)屬性,A,,2. 程序設計基礎,,在設計程序時，應采納的原則之一是( ),,A)不限制goto語句的使用,,B)

39、減少或取消注解行,,C)程序越短越好,,D)程序結(jié)構(gòu)應有助于讀者理解,D,,2. 程序設計基礎,,,結(jié)構(gòu)化程序設計的一種基本方法是(),,A)篩選法,,B)遞歸法,,C)歸納法,,D)逐步求精法,,D,,2. 程序設計基礎,,下面描述中，符合結(jié)構(gòu)化程序設計風格的是（）,,A. 使用順序、選擇和重復（循環(huán)）三種基本控制結(jié)構(gòu)表示程序的控制邏輯,,B. 模塊只有一個入口，可以有多個出口,,C. 注重提高程序的執(zhí)行效率,,D. 不使用goto語句,A,,2. 程序設計基礎,,下列敘述中，不屬于結(jié)構(gòu)化分析方法的是(),,A)面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法,,B)面向數(shù)據(jù)結(jié)構(gòu)的Jackson方法,,C)面向數(shù)

40、據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開發(fā)方法,,D)面向?qū)ο蟮姆治龇椒?D,,2. 程序設計基礎,,結(jié)構(gòu)化程序設計主要強調(diào)的是（）,,A. 程序的規(guī)模,,B. 程序的易讀性,,C. 程序的執(zhí)行效率,,D. 程序的可移植性,B,,2. 程序設計基礎,,對建立良好的程序設計風格，下面描述正確的是（）,,A. 程序應簡單、清晰、可讀性好,,B. 符號名的命名要符合語法,,C. 充分考慮程序的執(zhí)行效率,,D. 程序的注釋可有可無,A,,2. 程序設計基礎,,下面對對象概念描述錯誤的是（）,,A. 任何對象都必須有繼承性,,B. 對象是屬性和方法的封裝體,,C. 對象間的通訊靠消息傳遞,,D. 操作是對象的動態(tài)性屬性

41、,A,,2. 程序設計基礎,,對象實現(xiàn)了數(shù)據(jù)和操作的結(jié)合，是指對數(shù)據(jù)和數(shù)據(jù)的操作進行(),,A)結(jié)合,,B)隱藏,,C)封裝,,D)抽象,C,,2. 程序設計基礎,,下面概念中，不屬于面向?qū)ο蠓椒ǖ氖牵ǎ?,A. 對象,,B. 繼承,,C. 類,,D. 過程調(diào)用,D,,2. 程序設計基礎,,在面向?qū)ο蠓椒ㄖ?，一個對象請求另一對象為其服務的方式是通過發(fā)送（）,,A. 調(diào)用語句,,B. 命令,,C. 口令,,D. 消息,D,,2. 程序設計基礎,,面向?qū)ο蟮脑O計方法與傳統(tǒng)的的面向過程的方法有本質(zhì)不同，它的基本原理是（）,,A. 模擬現(xiàn)實世界中不同事物之間的聯(lián)系,,B. 強調(diào)模擬現(xiàn)實世界中的算法而不

42、強調(diào)概念,,C. 使用現(xiàn)實世界的概念抽象地思考問題從而自然地解決問題,,D. 鼓勵開發(fā)者在軟件開發(fā)的絕大部分中都用實際領域的概念去思考,C,,2. 程序設計基礎,,結(jié)構(gòu)化程序設計方法的主要原則可以概括為自頂向下、逐步求精、______和限制使用goto語句。 （模塊化）,,面向?qū)ο蟮某绦蛟O計方法中涉及的對象是系統(tǒng)中用來描述客觀事物的一個____。（實體）,,在面向?qū)ο蠓椒ㄖ校畔㈦[蔽是通過對象的______性來實現(xiàn)的。 （封裝）,,一個類可以從直接或間接的祖先中繼承所有屬性和方法。采用這個方法提高了軟件的______。

43、 （可重用性）,,2. 程序設計基礎,,面向?qū)ο蟮哪Ｐ椭?，最基本的概念是對象?______。 （類）,,Jackson結(jié)構(gòu)化程序設計方法是英國的M.Jackson提出的，它是一種面向______的設計方法。 （數(shù)據(jù)結(jié)構(gòu)）,,與結(jié)構(gòu)化需求分析方法相對應的是______方法。 （結(jié)構(gòu)化設計）,,3. 軟件工程基礎,,3.1 軟件工程基本概念,,計算機軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。,,軟件的特點包括：,,（1）軟件是

44、一種邏輯實體；,,（2）軟件的生產(chǎn)與硬件不同，它沒有明顯的制作過程；,,（3）軟件在運行、使用期間不存在磨損、老化問題；,,（4）軟件的開發(fā)、運行對計算機系統(tǒng)具有依賴性，受計算機系統(tǒng)的限制，這導致了軟件移植的問題；,,（5）軟件復雜性高，成本昂貴；,,（6）軟件開發(fā)涉及諸多的社會因素。,,3. 軟件工程基礎,,軟件按功能分為應用軟件、系統(tǒng)軟件、支撐軟件（或工具軟件）。,,軟件危機主要表現(xiàn)在成本、質(zhì)量、生產(chǎn)率等問題。,,軟件工程是應用于計算機軟件的定義、開發(fā)和維護的一整套方法、工具、文檔、實踐標準和工序。,,軟件工程包括3個要素：方法、工具和過程。,,軟件工程過程是把軟件轉(zhuǎn)化為輸出的一組彼此相關(guān)

45、的資源和活動，包含4種基本活動：,,（1）P——軟件規(guī)格說明；（2）D——軟件開發(fā)；（3）C——軟件確認；（4）A——軟件演進。,,3. 軟件工程基礎,,軟件周期：軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的過程。,,軟件生命周期三個階段:軟件定義、軟件開發(fā)、運行維護，主要活動階段是：,,1、可行性研究與計劃制定；,,2、需求分析；,,3、軟件設計；,,4、軟件實現(xiàn)；,,5、軟件測試；,,6、運行和維護。,,3. 軟件工程基礎,,軟件工程的目標和與原則：,,目標：在給定成本、進度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護性、可重用性、可適應性、可移植性、可追蹤性和可互操作性且滿足用

46、戶需求的產(chǎn)品。,,基本目標：付出較低的開發(fā)成本；達到要求的軟件功能；取得較好的軟件性能；開發(fā)軟件易于移植；需要較低的費用；能按時完成開發(fā)，及時交付使用。,,基本原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗證性。,,3. 軟件工程基礎,,軟件工程的理論和技術(shù)性研究的內(nèi)容主要包括：軟件開發(fā)技術(shù)和軟件工程管理。,,軟件開發(fā)技術(shù)包括：軟件開發(fā)方法學、開發(fā)過程、開發(fā)工具和軟件工程環(huán)境。,,軟件工程管理包括：軟件管理學、軟件工程經(jīng)濟學、軟件心理學等內(nèi)容。,,軟件管理學包括人員組織、進度安排、質(zhì)量保證、配置管理、項目計劃等。,,軟件工程原則包括抽象、信息隱蔽、模塊化、局部化、確定性、一

47、致性、完備性和可驗證性。,,3. 軟件工程基礎,,3.2 結(jié)構(gòu)化分析方法,,結(jié)構(gòu)化方法的核心和基礎是結(jié)構(gòu)化程序設計理論。,,需求分析方法有：,,1、結(jié)構(gòu)化需求分析方法；,,2、面向?qū)ο蟮姆治龅姆椒ā?,從需求分析建立的模型的特性來分：靜態(tài)分析和動態(tài)分析。,,結(jié)構(gòu)化分析方法的實質(zhì)：著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具,建立系統(tǒng)的邏輯模型。,,3. 軟件工程基礎,,結(jié)構(gòu)化分析的常用工具：,,1、數(shù)據(jù)流圖；2、數(shù)據(jù)字典；3、判定樹；4、判定表。,,數(shù)據(jù)流圖：描述數(shù)據(jù)處理過程的工具，是需求理解的邏輯模型的圖形表示，它直接支持系統(tǒng)功能建模。,,數(shù)據(jù)字典：對

48、所有與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個有組織的列表，以及精確的、嚴格的定義，使得用戶和系統(tǒng)分析員對于輸入、輸出、存儲成分和中間計算結(jié)果有共同的理解。,,判定樹：從問題定義的文字描述中分清哪些是判定的條件，哪些是判定的結(jié)論，根據(jù)描述材料中的連接詞找出判定條件之間的從屬關(guān)系、并列關(guān)系、選擇關(guān)系，根據(jù)它們構(gòu)造判定樹。,,判定表：與判定樹相似，當數(shù)據(jù)流圖中的加工要依賴于多個邏輯條件的取值，即完成該加工的一組動作是由于某一組條件取值的組合而引發(fā)的，使用判定表描述比較適宜。,,數(shù)據(jù)字典是結(jié)構(gòu)化分析的核心。,,3. 軟件工程基礎,,軟件需求規(guī)格說明書的特點：,,1、正確性；,,2、無岐義性；,,3、完整性；,,4、

49、可驗證性；,,5、一致性；,,6、可理解性；,,7、可追蹤性。,,3. 軟件工程基礎,,3.3 結(jié)構(gòu)化設計方法,,軟件設計的基本目標是用比較抽象概括的方式確定目標系統(tǒng)如何完成預定的任務，軟件設計是確定系統(tǒng)的物理模型。,,軟件設計是開發(fā)階段最重要的步驟，是將需求準確地轉(zhuǎn)化為完整的軟件產(chǎn)品或系統(tǒng)的唯一途徑。,,3. 軟件工程基礎,,從技術(shù)觀點來看，軟件設計包括軟件結(jié)構(gòu)設計、數(shù)據(jù)設計、接口設計、過程設計。,,（1）結(jié)構(gòu)設計：定義軟件系統(tǒng)各主要部件之間的關(guān)系。,,（2）數(shù)據(jù)設計：將分析時創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義。,,（3）接口設計：描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信。,,（

50、4）過程設計：把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程描述。,,3. 軟件工程基礎,,從工程管理角度來看：概要設計和詳細設計。,,軟件設計的一般過程：軟件設計是一個迭代的過程；先進行高層次的結(jié)構(gòu)設計；后進行低層次的過程設計；穿插進行數(shù)據(jù)設計和接口設計。,,衡量軟件模塊獨立性使用耦合性和內(nèi)聚性兩個定性的度量標準。,,在程序結(jié)構(gòu)中各模塊的內(nèi)聚性越強，則耦合性越弱。,優(yōu)秀軟件應高內(nèi)聚，低耦合。,,,3. 軟件工程基礎,,軟件概要設計的基本任務是：,,1、設計軟件系統(tǒng)結(jié)構(gòu)；,,2、數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫設計；,,3、編寫概要設計文檔；,,4、概要設計文檔評審。,,3. 軟件工程基礎,,模塊用一個矩形表示，箭頭表示模塊

51、間的調(diào)用關(guān)系。,,在結(jié)構(gòu)圖中還可以用帶注釋的箭頭表示模塊調(diào)用過程中來回傳遞的信息。還可用帶實心圓的箭頭表示傳遞的是控制信息，空心圓箭心表示傳遞的是數(shù)據(jù)。,,結(jié)構(gòu)圖的基本形式：基本形式、順序形式、重復形式、選擇形式。,,結(jié)構(gòu)圖有四種模塊類型：傳入模塊、傳出模塊、變換模塊和協(xié)調(diào)模塊。,,3. 軟件工程基礎,,典型的數(shù)據(jù)流類型有兩種：變換型和事務型。,,變換型系統(tǒng)結(jié)構(gòu)圖由輸入、中心變換、輸出三部分組成。,,事務型數(shù)據(jù)流的特點是：接受一項事務，根據(jù)事務處理的特點和性質(zhì)，選擇分派一個適當?shù)奶幚韱卧缓蠼o出結(jié)果。,,詳細設計：是為軟件結(jié)構(gòu)圖中的每一個模塊確定實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用某種選定的表達工具表

52、示算法和數(shù)據(jù)結(jié)構(gòu)的細節(jié)。,,常見的過程設計工具有：圖形工具（程序流程圖）、表格工具（判定表）、語言工具（PDL）。,,3. 軟件工程基礎,,3.4 軟件測試,,軟件測試定義：使用人工或自動手段來運行或測定某個系統(tǒng)的過程，其目的在于檢驗它是否滿足規(guī)定的需求或是弄清預期結(jié)果與實際結(jié)果之間的差別。,,軟件測試的目的：發(fā)現(xiàn)錯誤而執(zhí)行程序的過程。,,軟件測試方法：靜態(tài)測試和動態(tài)測試。,,（1）靜態(tài)測試包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量。不實際運行軟件，主要通過人工進行。,,（2）動態(tài)測試：是基本計算機的測試，主要包括白盒測試方法和黑盒測試方法,,軟件測試過程一般按4個步驟進行：單元測試、集成測試、

53、驗收測試（確認測試）和系統(tǒng)測試。,,3. 軟件工程基礎,,白盒測試方法和黑盒測試,,①白盒測試：在程序內(nèi)部進行，主要用于完成軟件內(nèi)部操作的驗證。主要方法有邏輯覆蓋、基本基路徑測試。,,②黑盒測試：主要診斷功能不對或遺漏、界面錯誤、數(shù)據(jù)結(jié)構(gòu)或外部數(shù)據(jù)庫訪問錯誤、性能錯誤、初始化和終止條件錯，用于軟件確認。主要方法有等價類劃分法、邊界值分析法、錯誤推測法、因果圖等。,,3. 軟件工程基礎,,3.5 程序的調(diào)試,,程序調(diào)試的任務是診斷和改正程序中的錯誤，主要在開發(fā)階段進行。,,程序調(diào)試的基本步驟：,,1、錯誤定位；,,2、修改設計和代碼，以排除錯誤；,,3、進行回歸測試，防止引進新的錯誤。,,軟件調(diào)

54、試可分表靜態(tài)調(diào)試和動態(tài)調(diào)試。靜態(tài)調(diào)試主要是指通過人的思維來分析源程序代碼和排錯，是主要的設計手段，而動態(tài)調(diào)試是輔助靜態(tài)調(diào)試。,主要調(diào)試方法有,：1、強行排錯法；2、回溯法；3、原因排除法。,,3. 軟件工程基礎,,軟件工程試題及分析,,選擇題,,軟件開發(fā)的結(jié)構(gòu)化生命周期方法將軟件生命周期劃分成(),,A)定義、開發(fā)、運行維護,,B)設計階段、編程階段、測試階段,,C)總體設計、詳細設計、編程調(diào)試,,D)需求分析、功能定義、系統(tǒng)設計,A,,3. 軟件工程基礎,,下列工具中為需求分析常用工具的是(),,A)PAD B)PFD,,C)N-S D)DFD,,,開發(fā)

55、大型軟件時，產(chǎn)生困難的根本原因是(),,A)大系統(tǒng)的復雜性,,B)人員知識不足,,C)客觀世界千變?nèi)f化,,D)時間緊、任務重,A,D,,3. 軟件工程基礎,,下面不屬于軟件工程的3個要素的是( ),,A)工具 B)過程 C)方法 D)環(huán)境,,,為了避免流程圖在描述程序邏輯時的靈活性，提出了用方框圖來代替?zhèn)鹘y(tǒng)的程序流程圖，通常也把這種圖稱為( ),,A)PAD圖 B)N-S圖,,C)結(jié)構(gòu)圖 D)數(shù)據(jù)流圖,,,在軟件工程中，白箱測試法可用于測試程序的內(nèi)部結(jié)構(gòu)。此方法將程序看做是( ),,A)路徑的集合

56、 B)循環(huán)的集合,,C)目標的集合 D)地址的集合,D,B,A,,3. 軟件工程基礎,,軟件設計包括軟件的結(jié)構(gòu)、數(shù)據(jù)接口和過程設計，其中軟件的過程設計是指(),,A)模塊間的關(guān)系,,B)系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程描述,,C)軟件層次結(jié)構(gòu),,D)軟件開發(fā)過程,B,,3. 軟件工程基礎,,完全不考慮程序的內(nèi)部結(jié)構(gòu)和內(nèi)部特征，而只是根據(jù)程序功能導出測試用例的測試方法是(),,A)黑箱測試法,,B)白箱測試法,,C)錯誤推測法,,D)安裝測試法,A,,3. 軟件工程基礎,,數(shù)據(jù)流圖用于抽象描述一個軟件的邏輯模型，數(shù)據(jù)流

57、圖由一些特定的圖符構(gòu)成。下列圖符名標識的圖符不屬于數(shù)據(jù)流圖合法圖符的是(),,A)控制流,,B)加工,,C)數(shù)據(jù)存儲,,D)源和終,,分析：數(shù)據(jù)流圖4種基本符號：正方形或立方體代表源點或終點；圓角矩形或圓形代表數(shù)據(jù)處理；開口矩形或兩平行線代表數(shù)據(jù)存儲；箭頭代表數(shù)據(jù)流,A,,3. 軟件工程基礎,,下列不屬于軟件調(diào)試技術(shù)的是(),,A)強行排錯法 B)集成測試法,,C)回溯法 D)原因排除法,,,軟件生命周期中花費時間最多的階段是(),,A)詳細設計 B)軟件編碼,,C)軟件測試 D)軟件維護,,,軟件設計中，有利于提高

58、模塊獨立性的一個準則是(),,A)低內(nèi)聚低耦合 B)低內(nèi)聚高耦合,,C)高內(nèi)聚低耦合 D)高內(nèi)聚高耦合,C,B,D,,3. 軟件工程基礎,,信息隱蔽的概念與下述哪一種概念直接相關(guān),？,(),,A)軟件結(jié)構(gòu)定義 B)模塊獨立性,,C)模塊類型劃分 D)模塊耦合度,,,在軟件生產(chǎn)過程中，需求信息的給出是(),,A)程序員 B)項目管理者,,C)軟件分析設計人員 D)軟件用戶,,,下列敘述中，不屬于測試的特征的是(),,A)測試的挑剔性 B)

59、完全測試的不可能性,,C)測試的可靠性 D)測試的經(jīng)濟性,C,B,D,,3. 軟件工程基礎,,在結(jié)構(gòu)化設計方法中，生成的結(jié)構(gòu)圖(SC)中，帶有箭頭的連線表示(),,A)模塊之間的調(diào)用關(guān)系 B)程序的組成成分,,C)控制程序的執(zhí)行順序 D)數(shù)據(jù)的流向,,,檢查軟件產(chǎn)品是否符合需求定義的過程稱為(),,A)確認測試 B)集成測試,,C)驗證測試 D)驗收測試,,,下面不屬于軟件設計原則的是(),,A)抽象

60、 B)模塊化,,C)自底向上 D)信息隱蔽,C,A,A,,3. 軟件工程基礎,,下面不屬于靜態(tài)測試方法的是(),,A)代碼檢查 B)白盒法,,C)靜態(tài)結(jié)構(gòu)分析 D)代碼質(zhì)量度量,,,在結(jié)構(gòu)化方法中，用數(shù)據(jù)流程圖（DFD）作為描述工具的軟件開發(fā)階段是( ),,A. 可行性分析 B. 需求分析,,C. 詳細設計 D. 程序編碼,,,在軟件開發(fā)中，下面任務不屬于設計階段的是( ),,A. 數(shù)據(jù)結(jié)構(gòu)設計 B. 給出系統(tǒng)模塊結(jié)構(gòu),,C. 定義模塊算法

61、 D. 定義需求并建立系統(tǒng)模型,D,B,B,,3. 軟件工程基礎,,在軟件生命周期中，能準確地確定軟件系統(tǒng)必須做什么和必須具備哪些功能的階段是( ),,A. 概要設計 B. 詳細設計,,C. 可行性分析 D. 需求分析,,,軟件需求分析階段的工作，可以分為四個方面：需求獲取、需求分析、編寫需求規(guī)格說明書以及( ),,A. 階段性報告 B. 需求評審,,C. 總結(jié) D. 都不正確,,,下面不屬于軟件工程的3個要素的是( ),,A. 工具

62、 B. 過程,,C. 方法 D. 環(huán)境,D,D,B,,3. 軟件工程基礎,,程序流程圖（PFD）中的箭頭代表的是( ),,A. 數(shù)據(jù)流 B. 控制流,,C. 調(diào)用關(guān)系 D. 組成關(guān)系,,,檢查軟件產(chǎn)品是否符合需求定義的過程稱為( ),,A. 確認測試 B. 集成測試,,C. 驗證測試 D. 驗收測試,,,下列工具中屬于需求分析常用工具的是( ),,A. PAD

63、 B. PFD,,C. N-S D. DFD,A,D,B,,3. 軟件工程基礎,,下面不屬于軟件設計原則的是( ),,A. 抽象 B. 模塊化,,C. 自底向上 D. 信息隱蔽,,,在結(jié)構(gòu)化方法中，軟件功能分解屬于下列軟件開發(fā)中的階段是( ),,A. 詳細設計 B. 需求分析,,C. 總體設計 D. 編程調(diào)試,,,軟件調(diào)試的目的是( ),,A. 發(fā)現(xiàn)錯誤 B. 改正錯誤,,C. 改善軟件的性能 D. 挖掘

64、軟件的潛能,C,B,C,,3. 軟件工程基礎,,下列不屬于軟件調(diào)試技術(shù)的是( ),,A. 強行排錯法 B. 集成測試法,,C. 回溯法 D. 原因排除法,,,下列敘述中，不屬于軟件需求規(guī)格說明書的作用的是( ),,A. 便于用戶、開發(fā)人員進行理解和交流,,B. 反映出用戶問題的結(jié)構(gòu)，可以作為軟件開發(fā)工作的基礎和依據(jù),,C. 作為確認測試和驗收的依據(jù),,D. 便于開發(fā)人員進行需求分析,,,在數(shù)據(jù)流圖（DFD）中，帶有名字的箭頭表示( ),,A. 控制程序的執(zhí)行順序 B. 模塊之間的調(diào)用關(guān)系,,C. 數(shù)據(jù)的流向

65、 D. 程序的組成成分,D,B,C,,3. 軟件工程基礎,,軟件設計包括軟件的結(jié)構(gòu)、數(shù)據(jù)接口和過程設計，其中軟件的過程設計是指( ),,A. 模塊間的關(guān)系,,B. 系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程描述,,C. 軟件層次結(jié)構(gòu) D. 軟件開發(fā)過程,,,為了避免流程圖在描述程序邏輯時的靈活性，提出了用方框圖來代替?zhèn)鹘y(tǒng)的程序流程圖，通常也把這種圖稱為( ),,A. PAD圖 B. N-S圖,,C. 結(jié)構(gòu)圖 D. 數(shù)據(jù)流圖,,,需求分析階段的任務是確定( )

66、,,A. 軟件開發(fā)方法 B. 軟件開發(fā)工具,,C. 軟件開發(fā)費用 D. 軟件系統(tǒng)功能,B,B,D,,3. 軟件工程基礎,,下列不屬于結(jié)構(gòu)化分析的常用工具的是( ),,A. 數(shù)據(jù)流圖 B. 數(shù)據(jù)字典,,C. 判定樹 D. PAD圖,,,軟件開發(fā)的結(jié)構(gòu)化生命周期方法將軟件生命周期劃分成( ),,A. 定義、開發(fā)、運行維護,,B. 設計階段、編程階段、測試階段,,C. 總體設計、詳細設計、編程調(diào)試,,D. 需求分析、功能定義、系統(tǒng)設計,,,在軟件工程中，白箱測試法可用于測試程序的內(nèi)部結(jié)構(gòu)。此方法將程序看做是( ),,A. 循環(huán)的集合 B. 地址的集合,,C. 路徑的集合 D. 目標的集合,A,D,C,,3. 軟件工程基礎,,若按功能劃分，軟件測試的方法通常分為白盒測試方法和______測試方法。 (黑盒),,軟件的調(diào)試方法主要有：強行