全國計算機等級考試二級公共基礎知識

全國計算機等級考試二級公共基礎知識第一頁，共175頁。

一、涉及面廣，但難度小

公共基礎知識考題特點及復習建議計算機等級二級理論考試中有關公共知識部分的題目共有15道，涉及算法及數據結構、程序設計基礎、軟件工程基礎和數據庫設計基礎等四門學科，但是從整體上分析，考試中的考核內容的難度不大，考點也相對集中些。2第二頁，共175頁。二、考核重點為基本概念、基本方法和基本運算

計算機等級二級理論考試中涉及的題目都是基本概念、基本方法和基本運算，考核以概念和認識性內容為主，理解性、應用性內容極少。

3第三頁，共175頁。三、考核重點是數據結構和算法

以下是對以往二級理論考試的大概統(tǒng)計：

算法及數據結構：50%程序設計基礎：12.5%軟件工程基礎：18.75%數據庫設計基礎：18.75%4第四頁，共175頁。1、了解算法的基本概念和一些常用的算法，學會計算算法的時間復雜度；2、掌握數據結構的基本概念，并了解數據的邏輯結構和存儲結構，學會利用圖形的方式表示數據結構；學習目標與要求算法與數據結構：3、了解線性表的基本概念，并掌握線性表的順序存儲結構以及順序存儲的線性表的基本運算；4、了解棧和隊列的基本概念，并掌握它們的基本運算；5、了解線性鏈表的基本概念，并掌握線性鏈表的基本運算，同時，了解循環(huán)鏈表的基本概念和基本操作；

6、理解樹的概念，尤其是二叉樹的基本概念和相關性質，掌握二叉樹的存儲結構和遍歷技術；7、掌握查找技術，學會利用順序查找和二分查找在數列中查找指定的數據；8、學會利用相關的排序技術實現無序數列的排序操作。5第五頁，共175頁。1、了解軟件工程的基本概念；2、了解軟件工程過程與軟件的生命周期，以及軟件工程的目標和原則；學習目標與要求軟件工程：3、了解利用結構化分析法進行軟件工程中的需求分析的方法，并了解需求分析的方法和需要完成的任務；4、了解數據流圖的使用方法；5、了解如何利用結構化設計方法進行軟件設計，并了解軟件設計的一些常用工具；

6、了解軟件測試的目的和方法，以及軟件測試的準則，了解常用的軟件測試方法的區(qū)別和各自的功能與特點；7、了解程序調試的方法和原則。6第六頁，共175頁。1、了解程序設計的方法，以及程序設計風格確立的一些因素，掌握程序設計的基本規(guī)則；2、了解結構化程序設計的基本原則，掌握結構化程序設計的基本結構與特點;學習目標與要求程序設計基礎：3、了解面向對象的程序設計方法，并理解面向對象方法的一些基本概念。

數據庫系統(tǒng)：1、了解數據庫系統(tǒng)的基本概念，以及數據庫系統(tǒng)的發(fā)展；

2、了解數據模型的基本概念，并對E-R模型、層次模型、網狀模型和關系模型進行了解，并掌握關系模型的數據結構、關系的操作和數據約束等知識；

3、了解關系模型的基本操作，掌握關系模型的基本運算及擴充運算；4、了解數據庫的設計與管理，掌握數據庫設計的幾個階段的方法和特點。

7第七頁，共175頁。程序設計基本概念一、計算機工作原理通過工作原理了解，熟悉計算機內部執(zhí)行功能的基本意義。為理解程序打下基礎，特別理解計算機是機器。二、程序的定義指令的集合。（解釋指令）通過硬件控制系統(tǒng)自動完成某一功能。通過一系列代碼實現。8第八頁，共175頁。程序設計基本概念三、程序怎樣執(zhí)行、如何編寫程序計算機本身僅能識別二進制代碼“0”、“1”。編程最直接、最低級的就是機器語言。為解決機器語言難理解、記憶等問題。出現符號語言。為使編程接近自然語言，出現高級語言。如C、PASCAL、FORTRAN等。為配合高級語言編程，出現了開發(fā)工具，提高效率、減輕勞動量。如VB、VC、PB、Delphi、VFP等。因此VFP不是編程語言。9第九頁，共175頁。程序設計基本概念不管什么形式編寫代碼，最終都應將代碼翻譯成機器語言，這就是編譯程序的工作。不同的語言有不同的編譯器。程序控制是一種邏輯控制。因此，嚴謹的邏輯思維是一個程序員必備的基本素質。用程序實現某一功能。有許多方法。具體用哪種完全取決于程序員個人的思維方式。因此，程序是腦力勞動的結晶，從某種意義上，編程又是一門藝術。程序的特殊性決定了程序的復雜性，且與實現功能的復雜性密切相關成正比。因此為使復雜的、智力的編程工作規(guī)范化、科學化，便出現了各種編程設計方法。如結構化編程方法、面向對象的程序設計方法等。10第十頁，共175頁。程序設計基本概念不管用什么方法編程，不管編程者智力程度如何，不管采用什么樣的編程語言和方法，程序最終完成的功能穩(wěn)定、可靠、實用、易維護和安全等是程序的最終目標，也是程序員的追求。程序設計是一個復雜艱巨的過程。編寫代碼僅是程序設計的一部分。必須先有思想，再有方法，然后才是編寫代碼，且要經過許多反復，不可急功近利。11第十一頁，共175頁。程序設計基本概念四、程序設計語言或工具程序設計語言指的是用來編寫程序的語言。人與計算機交流要使用語言，以便讓計算機工作，計算機也通過語言把結果告訴用計算機的人——“人機對話”。人與計算機交流的語言非平常人與人之間交流的語言，是專門的語言——程序設計語言。程序設計語言是計算機系統(tǒng)軟件的重要組成部分。12第十二頁，共175頁。程序設計基本概念執(zhí)行程序設計的語言有很多，可分高級語言和低級語言，區(qū)別在于接近自然語言的程度高級語言一般與具體的計算機硬件無關，比較接近人類自然語言的語法習慣及數學表達形式。用高級語言編寫的源程序不能被機器直接執(zhí)行，需通過編譯成解釋程序的翻譯才可被機器執(zhí)行（機器語言）。

四、程序設計語言或工具（續(xù)）13第十三頁，共175頁。算法與數據結構一、算法（algorithm）1、算法的基本概念

算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。它是一組嚴謹地定義運算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，此順序將在有限的次數下終止。算法具有有窮性、確定性、可行性、輸入和輸出（擁有足夠的情報）等５個重要特性。14第十四頁，共175頁。學習目標與要求2、算法的基本要素對數據對象的運算和操作：算術運算、邏輯運算、關系運算、數據傳輸算法中各操作之間的執(zhí)行順序；描述算法的工具通常有傳統(tǒng)流程圖、N-S結構化流程圖、算法描述語言等；一個算法一般可以用順序、選擇、循環(huán)三種基本結構組合而成。算法的控制結構：15第十五頁，共175頁。算法與數據結構3、算法設計的基本方法列舉法歸納法遞推遞歸（以簡潔的形式設計和描述算法）減半遞推技術回溯法16第十六頁，共175頁。算法與數據結構二、算法的復雜度1、時間復雜度依據算法編制的程序在計算機上運行時所消耗的時間來度量。通常有事后統(tǒng)計法和事前分析估算法。一個算法是由控制結構（順序、分支和循環(huán)）和原操作構成的，算法時間取決于兩者的綜合效果。算法中基本操作重復執(zhí)行次數n和算法執(zhí)行時間同步增長，稱作算法的時間復雜度。17第十七頁，共175頁。算法與數據結構2、空間復雜度一般是指執(zhí)行這個算法所需要的內存空間。一個算法所占用的存儲空間包括算法程序所占的空間、

輸入的初始數據所占的存儲空間以及某種數據結構所需要的附加存儲空間。一個上機執(zhí)行的程序除了需要存儲空間來寄存本身所用指令、常數、變量和輸入數據外，也需要一些對數據進行操作的工作單元和存儲一些為實現計算所需信息的輔助空間。18第十八頁，共175頁。算法與數據結構3、例題講解算法的時間復雜度是指(C)A、執(zhí)行算法程序所需要的時間B、算法程序的長度C、算法執(zhí)行過程中所需要的基本運算次數D、算法程序中的指令條數算法的基本特征是可行性、確定性、【1】和擁有足夠的情報?！敬鸢浮?有窮性算法的空間復雜度是指(D)

A)算法程序的長度 B)算法程序中的指令條數

C)算法程序所占的存儲空間

D)執(zhí)行過程中所需要的存儲空間√

√

19第十九頁，共175頁。算法與數據結構在計算機中，算法是指（B）

A)加工方法 B)解題方案的準確而完整的描述

C)排序方法 D)查詢方法算法分析的目的是(D)

A)找出數據結構的合理性

B)找出算法中輸入和輸出之間的關系

C)分析算法的易懂性和可靠性

D)分析算法的效率以求改進算法的工作量大小和實現算法所需的存儲單元多少分別稱為算法的【1】

?！敬鸢浮?時間復雜度和空間復雜度√

√

20第二十頁，共175頁。算法與數據結構三、數據結構（DataStructure）1、數據結構研究的主要內容當今計算機應用的特點：1、所處理的數據量大且具有一定的關系；2、對其操作不再是單純的數值計算，而更多地是需要對其進行組織、管理和檢索。對數據的討論不單單是數據本身，還要包括數據與數據之間的關系。21第二十一頁，共175頁。特點：每個學生的信息占據一行，所有學生的信息按學號順序依次排列構成一張表格；表中每個學生的信息依據學號的大小存在著一種前后關系，這就是我們所說的線性結構；對它的操作通常是插入某個學生的信息，刪除某個學生的信息，更新某個學生的信息，按條件檢索某個學生的信息等等。應用舉例1——學籍檔案管理假設一個學籍檔案管理系統(tǒng)應包含如下表所示的學生信息。22第二十二頁，共175頁。應用舉例2——家庭血緣關系圖

表示家庭成員的輩分關系，使用下圖1-1所示的形式描述。圖1-1家庭血緣關系圖特點：

在求解過程中，所處理的數據之間具有層次關系，這是我們所說的樹形結構；對它的操作有：建立樹形結構，輸出最結點內容等等。23第二十三頁，共175頁。應用舉例3——制定教學計劃在制定教學計劃時，需要考慮各門課程的開設順序。有些課程需要先導課程，有些課程則不需要，而有些課程又是其他課程的先導課程。比如，計算機專業(yè)課程的開設情況如下表所示：24這種數據可以用下面的圖來表示：第二十四頁，共175頁。課程先后關系的圖形描形式：c1c9c4c2c12c10c11c5c3c6c7c8圖1-2計算機專業(yè)必修課程開設先后關系25第二十五頁，共175頁。1、數據的邏輯結構

2、數據的存儲結構

3、數據的運算：檢索、排序、插入、刪除、修改等。A．線性結構B．非線性結構A．順序存儲

B．鏈式存儲線性表棧隊樹形結構圖形結構數據結構的三個方面(亦稱物理結構)數據結構的主要研究問題：26第二十六頁，共175頁。2、基本概念和術語

數據結構是一門研究數據組織、存儲和運算的一般方法的學科。例：整數(1,2)、實數(1.1,1.2)字符串(Beijing)、圖形、聲音。計算機管理圖書問題：在圖書館里有各種卡片：有按書名編排的、有按作者編排的、有按分類編排。如何將查詢圖書的這些信息存入計算機中既要考慮查詢時間短，又要考慮節(jié)省空間。最簡單的辦法之一是建立一張表，每一本書的信息在表中占一行，如：27第二十七頁，共175頁。數據元素在計算機中的表示

數據結構是一門研究數據組織、存儲和運算的一般方法的學科。如何將0,1,2,3,4,5,6,7,8,9這10個數存放

在計算機中能最快地達到你所需要的目的？目的不同，最佳的存儲方方法就不同。從大到小排列：9,8,7,6,5,4,3,2,1,0輸出偶數：0,2,4,6,8,1,3,5,7,9

對數據結構中的節(jié)點進行操作處理（插入、刪除、修改、查找、排序）28第二十八頁，共175頁。數據元素(DataElement)數據元素是數據的基本單位，即數據集合中的個體。有時一個數據元素可由若干數據項(DataItem)組成。數據項是數據的最小單位。數據元素亦稱節(jié)點或記錄。數據結構可描述為Group=（D，R）有限個數據元素的集合有限個節(jié)點間關系的集合29第二十九頁，共175頁。數據結構可描述為Group=（D，R）例1：一年四季的數據結構可表示成

B=（D，R） D={春，夏，秋，冬} R={（春，夏），（夏，秋），（秋，冬）}

例2：家庭成員數據結構可表示成 B=（D，R） D={父親，兒子，女兒} R={（父親，兒子），（父親，女兒）}冬春夏秋父親兒子女兒30第三十頁，共175頁。數據結構也可用圖形表示一年四季的數據結構可表示成家庭成員數據結構可表示成冬春夏秋父親兒子女兒（概念：結點、前件、后件、根結點、葉子）31第三十一頁，共175頁。樹形結構全校學生檔案管理的組織方式計算機程序管理系統(tǒng)也是典型的樹形結構。32第三十二頁，共175頁。HGFECDBA樹形結構——結點間具有分層次的連接關系HBCDEFGA33第三十三頁，共175頁。1423D={1,2,3,4}R={(1,2),(1,3),(1,4),(2,3),(3,4),(2,4)}

213D={1,2,3}R={(1,2),(2,3),(3,2),(1,3)}

圖形結構——節(jié)點間的連結是任意的34第三十四頁，共175頁。3、例題講解數據處理的最小單位是(C)

A)數據 B)數據元素C)數據項

D)數據結構數據結構作為計算機的一門學科，主要研究數據的邏輯結構、對各種數據結構進行的運算，以及(A)

A)數據的存儲結構

B)計算方法

C)數據映象D)邏輯存儲數據結構包括數據的邏輯結構、數據的

【4】

以及對數據的操作運算?！敬鸢浮课锢斫Y構（或存儲結構）35第三十五頁，共175頁。線性結構與非線性結構：線性結構：有且只有一個根結點；每一個結點最多有一個前件，也最多有一個后件。如：一年四季，26個英文字母非線性結構：線性以外的數據結構。如：反映家庭成員間輩分關系的數據結構

算法與數據結構36第三十六頁，共175頁。4、線性表（LinearList）學生成績表(按成績排列)86胡孝臣986110395劉忠賞9861107100張卓9861109成績姓名學號

線性表——結點間是以線性關系聯結：線性表：具有線性結構的有限序列。數據元素在線性表中的位置只取決于它們自己的序號，即數據元素之間的相對位置是線性的。37第三十七頁，共175頁。線性表的定義:

線性表是n個元素的有限序列，它們之間的關系可以排成一個線性序列：a1，a2，……，ai，……，an其中n稱作表的長度，當n=0時，稱作空表。線性表的特點：1、線性表中所有元素的性質相同。2、除第一個和最后一個數據元素之外，其它數據元素有且僅有一個前驅和一個后繼。第一個數據元素無前驅，最后一個數據元素無后繼。3、數據元素在表中的位置只取決于它自身的序號。在線性表上常用的運算有：初始化、求長度、取元素、修改、前插、刪除、檢索、排序38第三十八頁，共175頁。線性表的順序存儲結構

及其插入

與刪除

操作特點：

1、線性表中數據元素類型一致，只有數據域，存儲空間利用率高。2、所有元素所占的存儲空間是連續(xù)的。3、各數據元素在存儲空間中是按邏輯順序依次存放的（a）做插入、刪除時需移動大量元素。（b）空間估計不明時，按最大空間分配。算法與數據結構39第三十九頁，共175頁。順序存儲存儲地址存儲內容元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)×mLo+（n-1)×mLoc(元素i)=Lo+（i-1)×m每個元素所占用的存儲單元個數

線性表的順序存儲結構：首地址起始地址基地址40第四十頁，共175頁。元素a1元素a2……..元素ai+1……..01i線性表的順序存儲結構——可用C語言中的一維數組來描述.第i個元素的ai存儲地址：Loc(ai)=Loc(a1)+(i-1)*mV[０]V[１]V[i]V[m-1]intV[M];

其中：V是數組的名字，M是數組大小，假設數組中的元素是整型類型算法與數據結構41第四十一頁，共175頁。插入運算…..a2a1an…..ai+1ai01i-1in-1ai-1…..a2a1alength

…ai+1ai

x

ai-1…..

a2

a1

X

aiai+1…..alength插入算法的分析假設線性表中含有n個數據元素，在進行插入操作時，若假定在n+1個位置上插入元素的可能性均等，則平均移動元素的個數為：42第四十二頁，共175頁。在進行刪除操作時，若假定刪除每個元素的可能性均等，則平均移動元素的個數為：分析結論順序存儲結構表示的線性表，在做插入或刪除操作時，平均需要移動大約一半的數據元素。當線性表的數據元素量較大，并且經常要對其做插入或刪除操作時，這一點需要值得考慮。刪除算法的分析43第四十三頁，共175頁。線性表的例題講解順序存儲方法是把邏輯上相鄰的結點存儲在物理位置

【1】

的存儲單元中。【答案】相鄰長度為n的順序存儲線性表中，當在任何位置上插入一個元素概率都相等時，插入一個元素所需移動元素的平均個數為【2】。【答案】

n/2線性表L=(a1,a2,a3,…ai，…an)，下列說法正確的是（D）

A)每個元素都有一個直接前件和直接后件

B)線性表中至少要有一個元素

C)表中諸元素的排列順序必須是由小到大或由大到小

D)除第一個元素和最后一個元素外，其余每個元素都有一個且只有一個直接前件和直接后件√

44第四十四頁，共175頁。數據結構中，與所使用的計算機無關的是數據的(C)

A)存儲結構 B)物理結構

C)邏輯結構

D)物理和存儲結構下列敘述中，錯誤的是（B）

A)數據的存儲結構與數據處理的效率密切相關

B)數據的存儲結構與數據處理的效率無關

C)數據的存儲結構在計算機中所占的空間不一定是連續(xù)的

D)一種數據的邏輯結構可以有多種存儲結構數據的存儲結構是指（B）A）數據所占的存儲空間B）數據的邏輯結構在計算機中的表示C）數據在計算機中的順序存儲方式D）存儲在外存中的數據45第四十五頁，共175頁。根據數據結構中各數據元素之間前后件關系的復雜程度，一般將數據結構分成(C)

A)動態(tài)結構和靜態(tài)結構 B)緊湊結構和非緊湊結構

C)線性結構和非線性結構

D)內部結構和外部結構數據的邏輯結構有線性結構和【2】兩大類。非線性結構當線性表采用順序存儲結構實現存儲時，其主要特點是【1】。【答案】邏輯結構中相鄰的結點在存儲結構中仍相鄰。46第四十六頁，共175頁。5、堆棧和隊列堆棧和隊列的定義棧和隊列是兩種特殊的線性表，它們是運算時要受到某些限制的線性表，故也稱為限定性的數據結構。堆棧的定義堆棧：限定只能在表的一端進行插入和刪除的特殊的線性表,此種結構稱為后進先出。設棧s=（a1，a2，…ai，…，an）,其中a1是棧底元素，an是棧頂元素。棧頂（top)：允許插入和刪除的一端；約定top始終指向新數據元素將存放的位置。棧底（bottom):不允許插入和刪除的一端。

a1

a2….

an進棧出棧棧頂棧底47第四十七頁，共175頁。隊列的定義隊列：一種特殊的線性結構，限定只能在表的一端進行插入，在表的另一端進行刪除的線性表。此種結構稱為先進先出（FIFO）表。

a1,

a2,

a3,

a4,…………

an-1,

an隊列示意圖隊頭隊尾隊列的主要運算（1）設置一個空隊列；（2）插入一個新的隊尾元素，稱為進隊；（3）刪除隊頭元素，稱為出隊；（4）讀取隊頭元素；48第四十八頁，共175頁。堆棧和隊列的例題講解棧和隊列的共同特點是（C）

A)都是先進先出

B)都是先進后出

C)只允許在端點處插入和刪除元素

D)沒有共同點如果進棧序列為e1,e2,e3,e4，則可能的出棧序列是（B）

A)e3,e1,e4,e2B)e4,e3,e2,e1

C)e3,e4,e1,e2 D)任意順序一些重要的程序語言(如C語言和Pascal語言)允許過程的遞歸調用。而實現遞歸調用中的存儲分配通常用（A）

A)棧

B)堆C)數組 D)鏈表√

√

√

49第四十九頁，共175頁。棧底至棧頂依次存放元素A、B、C、D，在第五個元素E入棧前，棧中元素可以出棧，則出棧序列可能是（B）

A)ABCED B)DCBEA

C)DBCEA D)CDABE棧通常采用的兩種存儲結構是（A）

A)順序存儲結構和鏈表存儲結構 B)散列方式和索引方式

C)鏈表存儲結構和數組

D)線性存儲結構和非線性存儲結構棧和隊列通常采用的存儲結構是【1】。【答案】鏈式存儲和順序存儲下列數據結構中，按先進后出原則組織數據的是（B）

A)線性鏈表B)棧

C)循環(huán)鏈表 D)順序表√

√

√

50第五十頁，共175頁。當循環(huán)隊列非空且隊尾指針等于隊頭指針時，說明循環(huán)隊列已滿，不能進行入隊運算。這種情況稱為【2】。答案：上溢由兩個棧共享一個存儲空間的好處是（B）

A)減少存取時間，降低下溢發(fā)生的機率

B)節(jié)省存儲空間，降低上溢發(fā)生的機率

C)減少存取時間，降低上溢發(fā)生的機率

D)節(jié)省存儲空間，降低下溢發(fā)生的機率下列關于棧的敘述中正確的是（

D）Ａ)在棧中只能插入數據B）在棧中只能刪除數據C）棧是先進先出的線性表D）棧是后進先出的線性表下列關于隊列的敘述中正確的是（C）Ａ）在隊列中只能插入數據B）在隊列中只能刪除數據C）隊列是先進先出的線性表

D）隊列是后進先出的線性表√

√

√

51第五十一頁，共175頁。順序存儲結構常用于線性數據結構，將邏輯上相鄰的數據元素存儲在物理上相鄰的存儲單元里。順序存儲結構的三個缺點：1.作插入或刪除操作時，需移動大量元數。2.長度變化較大時，需按最大空間分配。3.表的容量難以擴充。存儲內容元素n……..元素i……..元素2元素152第五十二頁，共175頁。6、線性鏈表線性鏈表的基本概念：

線性表的鏈式存儲結構稱為線性鏈表。為了適應線性表的鏈式存儲結構，計算機存儲空間被劃分為一個一個小塊，每一小塊占若干字節(jié)，通常稱這些小塊為存儲結點。算法與數據結構53第五十三頁，共175頁。將存儲空間中的每一個存儲結點分為兩部：一部分稱為數據域，用于存儲數據元素的值；另一部分稱為指針域，用于存放下一個數據元素的存儲序號（即存儲結點的地址），也就是指向后件結點.線性鏈表中存儲結點的結構如圖2.20所示54第五十四頁，共175頁。1、比順序存儲結構的存儲密度小(每個節(jié)點都由數據域和指針域組成，所以相同空間內假設全存滿的話順序比鏈式存儲更多)。2、邏輯上相鄰的節(jié)點物理上不必相鄰。3、插入、刪除靈活(不必移動節(jié)點，只要改變節(jié)點中的指針)。4、查找結點時鏈式存儲要比順序存儲慢。鏈接存儲結構特點：算法與數據結構55第五十五頁，共175頁。指向線性表中第一個結點的指針HEAD稱為頭指針。當HEAD=NULL（或0）時稱為空表。對于線性鏈表，可以從頭指針開始，沿著各個結點的指針掃描到鏈表中的所有結點。線性鏈表的邏輯結構圖所示56第五十六頁，共175頁。5757第五十七頁，共175頁。58第五十八頁，共175頁。線性鏈表的基本運算：線性鏈表的運算主要有以下幾個：①在線性鏈表中包含指定元素的結點之前

插入一個新元素。②在線性鏈表中刪除包含指定元素的結點。③將兩個線性鏈表按要求合并成一個線性鏈表。59第五十九頁，共175頁。線性鏈表的插入

運算：線性鏈表的插入是指在鏈式存儲結構下的線性表中插入一個新元素。為了要在線性鏈表中插入一個新元素，首先要給該元素分配一個新結點，然后將存放新元素值的結點鏈接到線性鏈表中指定的位置。算法與數據結構60第六十頁，共175頁。6161第六十一頁，共175頁。

線性鏈表的刪除指在鏈式存儲結構下的線性表中刪除包含指定元素的結點。為了在線性鏈表中刪除包含指定元素的結點，首先要在線性鏈表中找到這個結點，然后將要刪除結點放回到可利用棧。線性鏈表的刪除運算：算法與數據結構62第六十二頁，共175頁。6363第六十三頁，共175頁。循環(huán)鏈表的結構與前面所討論的線性鏈表相比，具有以下兩個特點：①循環(huán)鏈表的頭指針指向表頭結點。②在循環(huán)鏈表中，所有結點的指針構成了一個環(huán)狀鏈。

圖2.29是循環(huán)鏈表的示意圖。循環(huán)鏈表：64第六十四頁，共175頁。在實際應用中，循環(huán)鏈表與線性單鏈表相比主要有以下兩個方面的優(yōu)點：①在循環(huán)鏈表中，只要指出表中任何一個結點的位置，就可以從它出發(fā)訪問到表中其他所有的結點。②由于在循環(huán)鏈表中設置了一個表頭結點，因此，在任何情況下，循環(huán)鏈表中至少有一個結點存在，從而使空表與非空表的運算統(tǒng)一。算法與數據結構65第六十五頁，共175頁。鏈表不具有的特點是（B）A)不必事先估計存儲空間B)可隨機訪問任一元素C)插入刪除不需要移動元素

D)所需空間與線性表長度成正比數據結構分為邏輯結構與存儲結構，線性鏈表屬于【1】?！敬鸢浮看鎯Y構線性表的順序存儲結構和線性表的鏈式存儲結構分別是(B)A)順序存取的存儲結構、順序存取的存儲結構B)隨機存取的存儲結構、順序存取的存儲結構C)隨機存取的存儲結構、隨機存取的存儲結構D)任意存取的存儲結構、任意存取的存儲結構線性鏈表的例題講解66第六十六頁，共175頁。7、樹與二叉樹：樹的基本概念：前面我們討論的線性表，棧、隊列和數組等都是線性結構。而樹是一種非線性數據結構，它的每一個結點，都可以有不止一個直接后繼，除根外的所有結點，都有且只有一個直接前趨。這些數據結點按分支關系組織起來，清晰地反映了數據元素之間的層次關系。67第六十七頁，共175頁。算法與數據結構現實世界中，能用樹的結構表示的例子：學校的行政關系、書的層次結構、人類的家族血緣關系等。68第六十八頁，共175頁。6969第六十九頁，共175頁。7070第七十頁，共175頁。

二叉樹(binarytree)是一種很有用的非線性結構。二叉樹具有以下兩個特點：（1）非空二叉樹只有一個根結點；（2）每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。二叉樹（BinaryTree）：因為樹的每個結點的度不同，存儲困難，使對樹的處理算法很復雜。所以引出二叉樹的討論。71第七十一頁，共175頁。7272第七十二頁，共175頁。性質1：在任意一棵二叉樹中，度為0的結點（即葉子結點）總是比度為2的結點多一個。例子1：某二叉樹中度為2的結點有18個，則該二叉樹中有

19個葉子結點。二叉樹的性質：

特別要注意：二叉樹不是樹的特殊情況。aabb兩棵不同的二叉樹73第七十三頁，共175頁。性質2：二叉樹的第i層上至多有2i-1（i1）個結點二叉樹的性質：423167891011121314155第三層上(i=3)，有23-1=4個節(jié)點。第四層上(i=4)，有24-1=8個節(jié)點。74第七十四頁，共175頁。二叉樹的性質：性質3：深度為h的二叉樹中至多含有2h-1個結點423167891011121314155此樹的深度h=4，共有24-1=15個節(jié)點。75第七十五頁，共175頁。滿二叉樹與完全二叉樹滿二叉樹是指除最后一層外，每一層上的所有結點都有兩個子結點。完全二叉樹是指這樣的二叉樹：除最后一層外，每一層上的結點數均達到最大值；在最后一層上只缺少右邊的若干結點。注意：滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。算法與數據結構76第七十六頁，共175頁。滿二叉樹的特點：每一層上都含有最大結點數。7777第七十七頁，共175頁。完全二叉樹的特點：除最后一層外，每一層都取最大結點數，最后一層結點都集中在該層最左邊的若干位置7878第七十八頁，共175頁。對于完全二叉樹而言如果它的結點個數為偶數，則該二叉樹中：

葉子結點的個數=非葉子結點的個數如果它的結點個數為奇數，則該二叉樹中：

葉子結點的個數=非葉子結點的個數+1

（即葉子結點數比非葉子結點數多一個）規(guī)律總結：算法與數據結構79第七十九頁，共175頁。例題講解1、設一棵完全二叉樹共有700個結點，則在該二叉樹中有

350個葉子結點。2、在深度為5的滿二叉樹中，葉子結點的個數為（C

）A)32B)31C)16D)15算法與數據結構√

80第八十頁，共175頁。二叉樹的遍歷

二叉樹的遍歷是指不重復地訪問二叉樹中的所有結點。二叉樹的遍歷可以分為三種：前序遍歷、中序遍歷、后序遍歷。設訪問根結點記作V；遍歷根的左子樹記作L；遍歷根的右子樹記作R；

前序：

VLR（即根左右）

中序：

LVR（即左根右）后序：

LRV（即左右根）81第八十一頁，共175頁。8282第八十二頁，共175頁。1、設一棵二叉樹的中序遍歷結果為DBEAFC,

前序遍歷結果為ABDECF，則后序遍歷結果為：

DEBFCA

例題講解2、已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹的后序遍歷為（B）

A)GEDHFBCA B)DGEBHFCAC)ABCDEFGH D)ACBFEDHG√

83第八十三頁，共175頁。具有3個結點的二叉樹有（D）

A)2種形態(tài)B)4種形態(tài)

C)7種形態(tài)D)5種形態(tài)

設有下列二叉樹：

對此二叉樹前序遍歷的結果為（B）A)ZBTTCPXA B)ATBZXCTP

C)ZBTACTXPD)ATBZXCPT√

√

84第八十四頁，共175頁。8、查找和排序：查找——又稱為檢索

查找算法的評價主要考慮算法的時間復雜性，既可以采用數量級的形式表示，也可以采用平均檢索（查找）長度，即在查找成功情況下的平均比較次數來表示。查找可分為順序查找和二分法查找兩種。算法與數據結構85第八十五頁，共175頁。（a）順序查找：

順序查找又稱線性查找。它是一種最簡單、最基本的查找方法。基本思想是：從表中第一條記錄開始，逐個進行記錄的關鍵字和給定值的比較。若某個記錄的關鍵字和給定值相等，則查找成功；否則，若直至最后一個記錄，其關鍵字和給定值都不相等，則表明表中沒有所查記錄，查找不成功。算法與數據結構86第八十六頁，共175頁。

二分查找又稱折半查找。作為二分查找對象的表必須是順序存儲的有序表，即各記錄的次序是按其關鍵字的大小順序（以下假定按從小到大的順序）排列的表。（b）二分查找：算法與數據結構87第八十七頁，共175頁。

二分查找的具體做法是:先取表中間位置的記錄關鍵字與給定值比較。若相等,則查找成功；否則,若給定值比該記錄的關鍵字小，則給定值必在表的前半部分。在這前半部分中再取中間位置記錄的關鍵字進行比較，就又可以排除這部分的一半。依次反復進行，直到找到給定值或找完全表而找不到為止。對于n較大時，查找長度可以近似地表示為算法與數據結構88第八十八頁，共175頁。

排序是將一組雜亂無章的數據按一定的規(guī)律順次排列起來。通常數據對象有多個屬性域，即由多個數據成員組成,其中有一個屬性域可用來區(qū)分對象,作為排序依據。該域稱為關鍵字（key）。

排序的時間開銷是衡量算法好壞的最重要的標志。對于長度為n的有序線性表，查找時最壞情況只需比較n次。排序（sort）89第八十九頁，共175頁。（a）交換類排序：交換類排序法：冒泡排序法：需要比較的次數為n(n-1)/2快速排序法：是對冒泡排序的改進，是目前內部排序中速度最快的一種。算法與數據結構90第九十頁，共175頁。（b）插入類排序：插入類排序的基本方法是：每步將一個待排序的對象，按其關鍵字大小，插入到前面已經排好序的一組對象的適當位置上，直到對象全部插入為止。簡單插入排序法：最壞情況需要n(n-1)/2次比較；希爾排序法：最壞情況需要O（n）次比較。算法與數據結構91第九十一頁，共175頁。（c）選擇類排序：選擇類排序的思想是：每一趟（例如，第i趟，i=0，1，…，n?2）在后面n?i個待排序對象中選出關鍵字最小（升序，若為降序，選出最大關鍵字）的對象，作為有序對象序列的第i個對象。待到第n?2趟作完，待排序對象只剩下1個，不用再選了，結束排序。簡單選擇排序法，最壞情況需要n(n-1)/2次比較；堆排序法，最壞情況需要O（nlog2n）次比較。92第九十二頁，共175頁。程序設計基礎（一）程序設計方法與風格

如何形成良好的程序設計風格：1、源程序內部文檔化；選擇標識符的名字注釋（序言性和功能性注釋）程序的視覺組織一般位于模塊的首部，用于說明模塊的相關信息位于源程序模塊內部93第九十三頁，共175頁。顯式地說明一切變量數據說明的次序應該規(guī)范化便于查找變量（按順序排列）對復雜數據結構應注釋說明

2、數據說明程序設計基礎3、語句的結構每條語句簡單明了盡量不用或少用GOTO語句盡量只采用3種基本控制結構編程94第九十四頁，共175頁。4、輸入和輸出對所有輸入數據進行校驗和合理性檢查輸入輸出格式保持一致設計良好的輸出報表輸入方式應力求簡單，盡量避免給用戶帶來不必要的麻煩；交互式輸入數據時應有必要的提示信息;程序應對輸入數據的合法性進行檢查;若用戶輸入某些數據后可能產生嚴重后果,應給用戶輸出必要的提示并要求用戶確認；應根據系統(tǒng)的特點和用戶的習慣設計出令用戶滿意的輸入方式。

輸出數據的格式應清晰，美觀；輸出數據時要加上必要的提示信息。95第九十五頁，共175頁。結構化程序設計的主要思想是功能分解并逐步求精。當一些任務十分復雜不易描述時，可以將它拆分為一系列較小的功能部件，直到這些子任務小到易于理解和實現的程度。 結構化程序的特點：程序結構僅由順序、選擇和循環(huán)3種結構復合而成。程序設計基礎（二）結構化程序設計

96第九十六頁，共175頁。（三）面向對象的程序設計方法面向對象的程序設計（Object-OrientedProgramming，OOP）是一種把面向對象的思想應用于軟件開發(fā)過程中，指導開發(fā)活動的系統(tǒng)方法，簡稱OO方法，它是建立在對象概念（對象、類和繼承）基礎上的方法。程序設計基礎97第九十七頁，共175頁。面向對象程序設計方法的優(yōu)點：（1）從認知學的角度來看，面向對象方法符合人們對客觀世界的認識規(guī)律。（2）面向對象方法開發(fā)的軟件系統(tǒng)易于維護，其體系結構易于理解、擴充和修改。（3）面向對象方法中的繼承機制有力地支持軟件的復用。程序設計基礎98第九十八頁，共175頁。幾個術語：對象：在現實世界中，每個實體都是對象，例如，大學生、汽車、電視機、空調等都是現實世界中的對象屬性：通常是一些數據，有時它也可以是另一個對象事件：是由對象識別的一個動作，用戶可以編寫相應代碼對此動作進行響應方法：對象中的屬性只能通過該對象所提供的操作來存取或修改程序設計基礎99第九十九頁，共175頁。類：類是一組具有相同屬性和相同操作的對象的集合。基類：用來生成新類的類。派生類：由已存在的類派生出來的新類，也叫子類。繼承是指能夠直接獲得已有的性質和特征，而不必重復定義他們。繼承分單繼承和多重繼承。單繼承指一個類只允許有一個父類，多重繼承指一個類允許有多個父類多態(tài)性是指同樣的消息被不同的對象接受時可導致完全不同的行動的現象。程序設計基礎100第一百頁，共175頁。

水上交通工具陸上交通工具水陸兩用交通工具

多重繼承圖程序設計基礎101第一百零一頁，共175頁。四、例題講解：程序設計基礎結構化程序設計的3種結構是（D）

A)順序結構、選擇結構、轉移結構

B)分支結構、等價結構、循環(huán)結構

C)多分支結構、賦值結構、等價結構D)順序結構、選擇結構、循環(huán)結構在設計程序時，應采納的原則之一是（D）

A)不限制goto語句的使用B)減少或取消注解行

C)程序越短越好

D)程序結構應有助于讀者理解√

√

102第一百零二頁，共175頁。程序設計語言的基本成分是數據成分、運算成分、控制成分和（D）

A)對象成分 B)變量成分

C)語句成分 D)傳輸成分程序設計基礎結構化程序設計主要強調的是（D）

A)程序的規(guī)模 B)程序的效率

C)程序設計語言的先進性

D)程序易讀性以下不屬于對象的基本特點的是（A）

A)分類性

B)多態(tài)性C)繼承性 D)封裝性√

√

√

103第一百零三頁，共175頁。對建立良好的程序設計風格，下面描述正確的是（A）

A)程序應簡單、清晰、可讀性好

B)符號名的命名只要符合語法

C)充分考慮程序的執(zhí)行效率

D)程序的注釋可有可無在結構化程序設計思想提出之前，在程序設計中曾強調程序的效率，現在，與程序的效率相比，人們更重視程序的（C）

A)安全性 B)一致性

C)可理解性

D)合理性程序設計基礎√

√

104第一百零四頁，共175頁。下列敘述中，不屬于結構化程序設計方法的主要原則的是（B）

A)自頂向下B)由底向上

C)模塊化 D)限制使用goto語句對象實現了數據和操作的結合，是指對數據和數據的操作進行（C）

A)結合B)隱藏C)封裝

D)抽象

在面向對象方法中，一個對象請求另一個對象為其服務的方式是通過發(fā)送（D）A）調用語句B）命令C）口令D）消息程序設計基礎√

√

√

105第一百零五頁，共175頁。信息屏蔽的概念與下述哪一種概念直接相關（B）A）軟件結構定義B）模塊獨立性C）模塊類型劃分D）模塊偶合度下列對對象概念描述錯誤的是（A）A）任何對象都必須有繼承性B）對象是屬性和方法的封裝體C）對象間的通訊靠消息傳遞D）操作是對象的動態(tài)屬性程序設計基礎√

√

106第一百零六頁，共175頁。面向對象的設計方法與傳統(tǒng)的面向過程的方法有本質的不同,它的基本原理是（C）

A)模擬現實世界中不同事物之間的聯系

B)強調模擬現實世界中的算法而不強調概念

C)使用現實世界的概念抽象地思考問題從而自然地解決問題

D)鼓勵開發(fā)者在軟件開發(fā)的絕大部分中都用實際領域的概念去思考

在面向對象的程序設計中，類描述的是具有相似性質的一組

【1】。【答案】對象

在面向對象方法中，類之間共享屬性和操作的機制稱為【2】?！敬鸢浮坷^承一個類可以從直接或間接的祖先中繼承所有屬性和方法。采用這個方法提高了軟件的

【3】?！敬鸢浮靠芍赜眯?/p>

√

第一百零七頁，共175頁。面向對象的模型中，最基本的概念是對象和【4】?！敬鸢浮浚侯?/p>

在面向對象的設計中，用來請求對象執(zhí)行某一處理或回答某些信息的要求稱為【5】。【答案】：消息在程序設計階段應該采取

【6】

和逐步求精的方法，把一個模塊的功能逐步分解，細化為一系列具體的步驟，進而用某種程序設計語言寫成程序?！敬鸢浮浚鹤皂斚蛳鲁绦蛟O計基礎108第一百零八頁，共175頁?！?】

是一種信息隱蔽技術，目的在于將對象的使用者和對象的設計者分開。【答案】：封裝可以把具有相同屬性的一些不同對象歸類，稱為

【8】?！敬鸢浮浚簩ο箢愖映绦蛲ǔ７譃閮深悾?/p>

【9】

和函數，前者是命令的抽象，后者是為了求值?！敬鸢浮浚哼^程源程序文檔化要求程序應加注釋。注釋一般分為序言性注釋和【10】?！敬鸢浮浚汗δ苄宰⑨屧诿嫦驅ο蠓椒ǚN，信息屏蔽是通過對象的【11】性來實現的?！敬鸢浮浚悍庋b類是一個支持集成的抽象數據類型，而對象是類的【12】

。

【答案】：實例在面向對象方法種，類之間共享屬性和操作的機制稱為【13】

?！敬鸢浮浚豪^承第一百零九頁，共175頁。軟件工程基礎（一）基本概念

軟件工程：軟件工程是指應用計算機科學、數學及管理科學等原理，以工程化的原則和方法來解決軟件問題的工程。其目的是提高軟件生產率、提高軟件質量、降低軟件成本。

軟件危機：早期的軟件主要指程序，采用個體工作方式，缺少相關文檔，質量低，維護困難，這些問題稱為“軟件危機”，軟件工程概念的出現源自于軟件危機。110第一百一十頁，共175頁。軟件生命周期將軟件產品從提出、實現、使用維護到停止使用退役的過程稱為軟件生命周期。分為軟件定義、軟件開發(fā)及軟件運行維護3個時期。維護是持續(xù)時間最長，花費代價最大的一個時期，軟件工程學的一個目的就是提高軟件的可維護性，降低維護代價。6個活動階段：可行性研究與計劃制定：確定系統(tǒng)的總體目標。參加人員有用戶、項目負責人和系統(tǒng)分析員，產生文檔有可行性分析報告、項目計劃書等。需求分析：確定系統(tǒng)的邏輯模型。參加人員有用戶、項目負責人和系統(tǒng)分析員。產生文檔為需求規(guī)格說明書，其作用：（1）便于用戶、開發(fā)人員進行理解交流；（2）反映用戶問題的結構，可以作為軟件開發(fā)工作的基礎和依據；（3）作為確認測試和驗收的依據。第一百一十一頁，共175頁。軟件設計：包括軟件結構設計、數據設計、接口設計和過程設計。其中結構設計是定義軟件系統(tǒng)各部件之間的關系；數據設計是將分析時創(chuàng)建的模型轉化為數據結構的定義；接口設計是描述軟件內部、軟件和操作系統(tǒng)之間及軟件與人之間如何通信；過程設計則是把系統(tǒng)結構部件轉換成軟件的過程性描述。軟件設計分概要設計和詳細設計。參加人員有系統(tǒng)分析員和高級程序員。產生的文檔有設計規(guī)格說明書。編碼：編程。高級程序員和程序員產生源程序清單。測試：由另一部門的高級程序員或系統(tǒng)分析員產生軟件測試計劃和軟件測試報告。運行維護第一百一十二頁，共175頁。

軟件工程三要素方法：完成軟件工程項目的技術手段。工具：支持軟件的開發(fā)、管理、文檔生成。過程：支持軟件開發(fā)的各個環(huán)節(jié)的控制、管理。

軟件工程的理論和技術研究的內容軟件開發(fā)技術和軟件工程管理。

軟件工程的目標在給定的成本、進度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護性、可適應性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產品。軟件工程鼓勵研制和采用各種先進的軟件開發(fā)方法、工具和環(huán)境。第一百一十三頁，共175頁。軟件工具和軟件開發(fā)環(huán)境軟件工具(CASE)：用來輔助軟件開發(fā)、運行、維護、管理、支持等過程中的活動的軟件。軟件開發(fā)環(huán)境：支持軟件產品開發(fā)的軟件系統(tǒng)，它由軟件工具集和環(huán)境集成機制構成軟件工程基礎114第一百一十四頁，共175頁。（二）結構化分析方法

軟件工程基礎基本思想將系統(tǒng)分析看成工程項目，有計劃、有步驟地進行工作。開發(fā)策略自頂向下，逐層分解分析結果一套分層的數據流圖(DFD)：用來描述數據流從輸入到輸出的變換流程一個數據字典(DD)：用來描述DFD中的每個數據流、文件以及組成數據流或文件的數據項一組小說明（加工邏輯說明）：用來描述每個基本加工的加工邏輯115第一百一十五頁，共175頁。（三）結構化設計方法、總體設計和詳細設計

軟件工程基礎結構化設計方法

結構圖：

基本成分：模塊、調用、輸入輸出數據模塊用矩形表示，模塊間用線段連接，表示調用關系，輸入輸出數據可寫在調用線段的旁邊

信息流的類型

變換流事務流116第一百一十六頁，共175頁?？傮w設計設計原則分解—協(xié)調原則自頂向下的原則信息屏蔽、抽象的原則一致性原則明確性原則模塊間的耦合度盡可能小，模塊內部組合盡可能緊湊（內聚性高）模塊的扇入和扇出系數合理模塊的規(guī)模適當117第一百一十七頁，共175頁。詳細設計根本目標：

確定應用怎樣具體的實現所要求的系統(tǒng)，不是具體的編寫程序，而是要設計程序的“藍圖”自頂向下的原則。此階段的結果基本上決定了最終的程序代碼的質量。包括內容：代碼設計輸入設計輸出設計處理過程設計用戶界面設計安全控制設計118第一百一十八頁，共175頁。119第一百一十九頁，共175頁。（四）軟件測試

軟件工程基礎

意義目的為了發(fā)現錯誤；希望能以最少的人力和時間發(fā)現潛在的各種錯誤和缺陷；保證系統(tǒng)質量和可靠性的關鍵步驟。

測試方法人工測試；機器測試。提問：測試能否發(fā)現程序中的所有錯誤？答案：不能。120第一百二十頁，共175頁。白盒測試結構測試將軟件看成透明的白盒，根據程序的內部結構和邏輯結構來設計測試例子，對程序的路徑和過程進行測試，檢查是否滿足設計的要求

黑盒測試功能測試將軟件看成黑盒子，在完全不考慮軟件內部結構和特性的情況下，測試軟件的外部特性

軟件測試的實施單元測試（模塊測試）：白盒測試法組裝測試（集成測試）確認測試：檢查軟件產品是否符合需求定義，黑盒測試法系統(tǒng)測試第一百二十一頁，共175頁。適合于黑盒測試的測試方案：等價類劃分、邊界值分析法和錯誤推測法三種。適合于白盒測試的測試方案：主要有邏輯覆蓋法。邏輯覆蓋法包括：語句覆蓋、判定覆蓋（也稱為分支覆蓋）、條件覆蓋、判定/條件覆蓋、條件組合覆蓋。軟件工程基礎122第一百二十二頁，共175頁。（五）程序調試

軟件工程基礎任務根據測試時發(fā)現的錯誤，找出原因和具體的位置，進行改正由程序開發(fā)人員來進行，誰開發(fā)的程序就由誰來進行調試方法：

強行排錯法

回溯法

原因排除法（演繹、歸納、二分法)123第一百二十三頁，共175頁。

靜態(tài)調試通過人的思維來分析源程序代碼和排錯，是主要的調試手段。動態(tài)調試輔助靜態(tài)調試。軟件工程基礎124第一百二十四頁，共175頁。（六）例題講解

為了提高測試的效率，應該（D）

A)隨機選取測試數據

B)取一切可能的輸入數據作為測試數據

C)在完成編碼以后制定軟件的測試計劃

D)選擇發(fā)現錯誤可能性大的數據作為測試數據軟件生命周期中所花費用最多的階段是（D）

A)詳細設計 B)軟件編碼C)軟件測試D)軟件維護軟件工程基礎√

√

125第一百二十五頁，共175頁。下列敘述中，不屬于軟件需求規(guī)格說明書的作用的是(D)

A)便于用戶、開發(fā)人員進行理解和交流

B)反映出用戶問題的結構，可以作為軟件開發(fā)工作的基礎和依據

C)作為確認測試和驗收的依據

D)便于開發(fā)人員進行需求分析下列不屬于軟件工程的3個要素的是（D）Ａ)工具 Ｂ)過程Ｃ)方法Ｄ)環(huán)境軟件設計包括軟件的結構、數據接口和過程設計，其中軟件的過程設計是指（B）

A)模塊間的關系

B)系統(tǒng)結構部件轉換成軟件的過程描述

C)軟件層次結構 D)軟件開發(fā)過程√

√

√

第一百二十六頁，共175頁。檢查軟件產品是否符合需求定義的過程稱為(Ａ)

Ａ)確認測試Ｂ)集成測試Ｃ)驗證測試Ｄ)驗收測試數據流圖用于抽象描述一個軟件的邏輯模型，數據流圖由一些特定的圖符構成。下列圖符名標識的圖符不屬于數據流圖合法圖符的是(Ａ)

Ａ)控制流 Ｂ)加工Ｃ)數據存儲 Ｄ)源和流開發(fā)軟件所需高成本和產品的低質量之間有著尖銳的矛盾，這種現象稱作(B)

A)軟件投機B)軟件危機

C)軟件工程D)軟件產生√

√

√

127第一百二十七頁，共175頁。下面不屬于軟件設計原則的是(Ｃ)Ａ)抽象 Ｂ)模塊化

Ｃ)自底向上Ｄ)信息隱蔽開發(fā)大型軟件時，產生困難的根本原因是(A)

A）大系統(tǒng)的復雜性

B）人員知識不足

C）客觀世界千變萬化 D）時間緊、任務重軟件工程的出現是由于（Ｃ）

A)程序設計方法學的影響 B)軟件產業(yè)化的需要

C)軟件危機的出現 D)計算機的發(fā)展√

√

√

128第一百二十八頁，共175頁。軟件開發(fā)離不開系統(tǒng)環(huán)境資源的支持，其中必要的測試數據屬于（D）

A)硬件資源 B)通信資源

C)支持軟件D)輔助資源在數據流圖(DFD)中，帶有名字的箭頭表示(D)

A)模塊之間的調用關系B)程序的組成成分

C)控制程序的執(zhí)行順序D)數據的流向下列不屬于結構化分析的常用工具的是（D）

A)數據流圖 B)數據字典

C)判定樹 D)PAD圖在軟件生產過程中，需求信息的給出是（D）

A)程序員B)項目管理者

C)軟件分析設計人員 D)軟件用戶√

√

√

√

129第一百二十九頁，共175頁。下列工具不是需求分析常用工具的是（D）Ａ)PAD Ｂ)PFDＣ)N-S Ｄ)DFD模塊獨立性是軟件模塊化所提出的要求，衡量模塊獨立性的度量標準則是模塊的（C）

A)抽象和信息隱蔽B)局部化和封裝化

C)內聚性和耦合性

D)激活機制和控制方法軟件開發(fā)的結構化生命周期方法將軟件生命周期劃分成（A）

A)定義、開發(fā)、運行維護

B)設計階段、編程階段、測試階段

C)總體設計、詳細設計、編程調試

D)需求分析、功能定義、系統(tǒng)設計√

√

√

130第一百三十頁，共175頁。在軟件工程中，白箱測試法可用于測試程序的內部結構。此方法將程序看做是（A）

A)路徑的集合

B)循環(huán)的集合C)目標的集合D)地址的集合完全不考慮程序的內部結構和內部特征，而只是根據程序功能導出測試用例的測試方法是（A）

A)黑箱測試法

B)白箱測試法

C)錯誤推測法D)安裝測試法在結構化設計方法中，生成的結構圖(SC)中，帶有箭頭的連線表示（A）

A)模塊之間的調用關系

B)程序的組成成分

C)控制程序的執(zhí)行順序 D)數據的流向√

√

√

131第一百三十一頁，共175頁。下列選項中，不屬于模塊間耦合的是（C）

A)數據耦合B)同構耦合

C)異構耦合

D)公用耦合下列敘述中，不屬于測試的特征的是（C）

A)測試的挑剔性B)完全測試的不可能性

C)測試的可靠性

D)測試的經濟性需求分析中開發(fā)人員要從用戶那里了解（A）

A)軟件做什么

B)用戶使用界面

C)輸入的信息 D)軟件的規(guī)模下列不屬于軟件調試技術的是（B）

A)強行排錯法 B)集成測試法

C)回溯法 D)原因排除法√

√

√

√

第一百三十二頁，共175頁。為了避免流程圖在描述程序邏輯時的靈活性，提出了用方框圖來代替?zhèn)鹘y(tǒng)的程序流程圖，通常也把這種圖稱為（B）

A)PAD圖B)N-S圖

C)結構圖D)數據流圖軟件復雜性度量的參數包括（B）

A)效率B)規(guī)模

C)完整性D)容錯性下列敘述中，正確的是（D）

A)軟件就是程序清單B)軟件就是存放在計算機中的文件

C)軟件應包括程序清單及運行結果

D)軟件包括程序和文檔軟件設計中，有利于提高模塊獨立性的一個準則是（

C）

A)低內聚低耦合 B)低內聚高耦合

C)高內聚低耦合

D)高內聚高耦合√

√

√

√

第一百三十三頁，共175頁。下列敘述中，不屬于結構化分析方法的是（D）

A)面向數據流的結構化分析方法

B)面向數據結構的Jackson方法

C)面向數據結構的結構化數據系統(tǒng)開發(fā)方法

D)面向對象的分析方法詳細設計的結果基本決定了最終程序的（C）

A)代碼的規(guī)模 B)運行速度

C)質量

D)可維護性下列不屬于靜態(tài)測試方法的是（B）

A)代碼檢查 B)白盒法

C)靜態(tài)結構分析D)代碼質量度量在軟件生命周期中，能準確地確定軟件系統(tǒng)必須做什么和必須具備哪些功能的階段是（D）A）概要設計B）詳細設計C）可行性分析D）需求分析√

√

√

√

第一百三十四頁，共175頁。程序流程圖（PFD）中的箭頭代表的是（B）A）數據流B）控制流

C）調用關系D）組成關系在結構化方法中，軟件功能分解屬于下列軟件開發(fā)中的階段是（C）A）詳細設計B）需求分析C）總體設計

D）編程調試軟件調試的目的是（B）A）發(fā)現錯誤B）改正錯誤C）改善軟件的性能D）挖掘軟件的潛能√

√

√

135第一百三十五頁，共