計算機二級公共基礎知識

一.數據結構與算法

一、基本概念：

?數據(Data)：信息的載體，能夠被計算機識別、存儲和加工處理的物理符號。

包括文本類型的數據(如：字母、數字、漢字)和多媒體類型的數據(如：聲

音、動畫、圖像)。

數據元素(DataElement)：是數據的基本單位，有時也稱為元素、結點、頂

點、記錄，可以有若干個數據項(字段、域、屬性)組成。

數據結構(DataStructure)：指的是數據之間的相互關系，即數據的組織

形式。其包括三個部分：

1、邏輯結構：數據元素之間的邏輯關系

2、存儲結構：數據元素及其關系在計算機存儲器內的表示。

3、數據的運算(算法)：即對數據施加的操作

數據的邏輯結構有兩大類：

1、線性結構：

特征是：若結構是非空集，則有且僅有一個開始結點和一個終端結點，并且所有

結點最多只有一個直接前趨和一個直接后繼。

例：一維數組、鏈表、棧、隊列、串

2、非線性結構：

特征是：一個結點可能有多個直接前趨和直接后繼。

例：多維數組、廣義表、樹、圖

數據的存儲結構有以下基本存儲方法：

1、順序存儲方法：

該方法是將邏輯上相鄰的結點存儲在物理位置上相鄰的存儲單元里，結點間的邏

輯關系由存儲單元的鄰接關系來體現，一般通過數組來實現的。

2、鏈接存儲方法：

該方法不要求邏輯上相鄰的結點在物理位置上亦相鄰，結點間的邏輯關系是由附

加的指針字段表示的。通過指針類型來實現的。

3、索引存儲方法：

該方法通常是在存儲結點信息的同時，還建立附加的索引表，索引表中的每一項

稱為索引項，索引項的一般形式是：關鍵字，地址。

4、散列存儲方法：

該方法的基本思想是根據結點的關鍵字直接計算出該結點的存儲地址，通過散列

函數實現。例：除余法散列函數、相乘取整法散列函數

?算法的基本特征：

1、可行性(Effectiveness)：針對實際問題而設計的算法，執行后能夠得到滿意

的結果。

2、確定性(Definiteness)：算法中的每一個步驟都必須有明確的定義，不允許

出現歧義性。

3、有窮性(Finiteness)：算法必須在有限時間內做完，即必須在執行有限個步

驟之后終止。

?時間復雜度：該算法執行的時間耗費，它是該算法所求解問題規模n的函數。

?空間復雜度：該算法執行時所耗費的存儲空間，它也是問題規模n的函數。

二、線性表：

?線性表(LinearList)：是由n性表0)個數據元素(結點)ai,a2,a3,,a?

組成的有限序列。對于非空的線性表，有且僅有一個開始結點a“它沒有直

接前趨；有且僅有一個終端結點出，它沒有直接后繼；其余的結點有且僅有

一個直接前趨結點和一個直接后繼結點。

*線性表的存儲結構：

1、順序存儲(SequentialList)：將線性表的結點按邏輯次序依次存放在一組地

址連續的存儲單元里，用這種方法存儲的線性表稱為順序表。

2、鏈式存儲(LinkedList)：邏輯上相鄰的結點，物理上也相鄰，存儲單元可以

是連續的，也可以是不連續的，在存儲每個結點值的同時，還存儲指向其后繼結

點的地址，用這種方法存儲的線性表稱為鏈表。

常見的運算有：

表的初始化、求表的長度、取表中的第I個結點、查找結點、插入新的結點、刪

除結點。

順序表和鏈表的比較：

1、基于空間的考慮：

A、順序表的存儲空間是靜態分配的，而鏈表的存儲空間是動態分配的。

B、順序表占的存儲空間必須是連續的，而鏈表占的存儲空間可以是連續的，也

可是不連續的

C、順序表存儲密度為1,而鏈表中的每個結點，除了數據域外，還要額外的設

置指針域，存儲密度小于1

2、基于時間的考慮：

A、在鏈表中的任何位置上進行插入和刪除，只需要修改指針，而順序表中平均

將要移動近一半的結點。

B、順序表是隨機存取結構，它的存取時間為0(1),而鏈表需從頭結點順著鏈掃

描鏈表。

總之，當線性表的長度變化不大，易于事先確定其大小時，為了節約存儲空

間，宜采用順序表作為存儲結構；當線性表的長度變化較大，難以估計其存儲規

模時，以采用鏈表作為存儲結構為好。若線性表的操作主要是進行查找，很少做

插入和刪除操作時，采用順序表做存儲結構為宜；對于頻繁進行插入和刪除的線

性表，宜采用鏈表做存儲結構。

例：關于線性表的描述中，錯誤的是()

A、線性表是線性結構B、線性表的順序存儲結構，必須占用一片連續

的存儲單元

C、線性表是單鏈表D、線性表的鏈式存儲結構，不必占用一片連續的存

儲單元

用數組表示線性表的優點是()

A、便于插入和刪除操作B、便于隨機存取

C、可以動態地分配存儲空間D、不需要占用一片連續的存儲空間

?棧(Stack)：是限制僅在表的一端進行插入和刪除運算的線性表，通常稱插

入、刪除的這一端為棧頂(Top),另一端稱為棧底(Bottom)。當表中沒有元

素時稱為空棧。是一種后進先出的線性表，又稱為LIF0表。

棧的基本運算有：

棧的初始化、判棧空、判棧滿、進棧、出棧等

棧的存儲：

順序存儲、鏈式存儲

例：若進棧的輸入序列是A、B、C、D、E,并且在它們進棧的過程中可以進

行出棧操作，則不可能出現的出棧序列是()

A、EDCBAB、DECBAC、DCEABD、ABCDE

四、隊列：

?隊列(Queue)：也是一利運算受限的線性表，它只允許在表的一端進行插入,

而在另一端進行刪除。允許刪除的一段稱為隊頭(Front),允許插入的一段

稱為隊尾(Rear)。(類似于生活中的購物排隊)。是一種先進先出的線性表，

又稱為FIFO表。

隊列的基本運算：

隊列的初始化、判隊空、判隊滿、入隊、出隊

隊列的存儲實現：

順序存儲、鏈式存儲

例：一個隊列的入隊序列是1,2,3,4,則隊列的輸出序列是()

A、4,3,2,1B、1,2,3,4C、1,4,3,2D、3,2,4,

1

五、串：

串(String)：是零個或多個字符組成的有限序列。

串中所包含的字符個數稱為該串的長度。

串中任意個連續字符組成的子序列稱為該串的子串，包含子串的串相應地稱

為王串

注：空串是任意串的子串，任意串是其自身的子串

串有串常量、串變量之分：

1、串常量在程序中只能被引用但不能改變其值，即只能讀不能寫。

2、串變量其值是可以改變的。

?串的基本運算：

求串長、串復制、串聯接、串比較、字符定位、

六、樹(非線性結構)：

?樹(Tree)：是n(n>=0)個結點的有限集T,T(n=0)為空時稱為空樹,否則它

滿足如下兩個條件：

1、有且僅有一個特定的稱為根(Root)的結點

2、其余的結點可分為m(m>=0)個互不相交的子集Tl,T2,…….，Tm,其中

每個子集本身又是一棵樹，并稱其為根的子樹(Subtree)o

在樹的樹形圖表示中，結點通常是用圓圈表示的，結點的名字一般是寫在圓

圈旁邊，有時亦可寫在圓圈內。

度(Degree)：一個結點擁有的子樹數稱為該結點的度。一棵樹的度是指該樹

中結點的最大度數。

葉子(Leaf)：度為零的結點稱為葉子或終端結點

?分支結點(Node)：度不為零的結點稱為分支結點。

?樹中某個結點的子樹之根稱為該結點的孩子(Child)結點或子結點，相應的

該結點稱為孩子結點的雙親(Parents)結點或父結點。

同一個雙親的孩子稱為兄弟結點(Sibling)

?：?結點的層數(Level)是從根起算，設根的層數為1,其余結點的層數等于其雙

求結點的層數加1.

樹中結點的最大層數稱為樹的高度(Height)或深度(Depth).

?森林(Forest)：是m(m>=0)棵互不相交的樹的集合。刪去一棵樹的根，就得

到一個森林，反之，加上一-1結點作樹根，森林就變為--棵樹。

?二叉樹(BinaryTree)：是n(n>=0)個結點的有限集，它或者是空集(n=0),

或者由一個根結點及兩棵互不相交的、分別稱作這個根的左子樹和右子樹的

二叉樹組成。

二叉樹中，每個結點最多只能有兩棵子樹.，并且有左右之分。

二叉樹的五種基本形態：

例：具有3個結點的二叉樹有兒種形態。

?滿二叉樹(FullBinaryTree)：一棵深度為k且有2k-l個結點的二叉樹稱為

滿二叉樹

完全二叉樹(CompleteBinaryTree)：若一棵二叉樹至多只有最下面的兩層

上結點的度數可以小于2,并且最下…層上的結點都集中在該層最左邊的若

干位置上，則此二叉樹稱為完全二叉樹。

二叉樹的性質：

性質1：二叉樹第I層上的結點數目最多為2一(1>=1)

性質2：深度為k的二叉樹至多有2k-l個結點(k>=l)

性質3：在任意一棵二叉樹中，若終端結點的個數為n。，度為2的結點數為“，

則no=n2+l

性質4：具有n個結點的完全二叉樹的深度為[glen]+l(取下整)或

[lag(n+D](取上整)。

例：一棵二叉樹的結點數為18個，求它的最小高度

已知度為2的結點數為15個，求葉子結點數

二叉樹的遍歷：

?遍歷(Traversal)：是指沿著某條搜索路線，依次對樹中每個結點均做一次

且僅做一次訪問。

前序遍歷：(又稱為先序遍歷、先根遍歷)

若二叉樹為空，則執行空操作。否則：

1、訪問根結點；

2、前序遍歷左子樹；

3、前序遍歷右子樹。

中序遍歷：(又稱為中根遍歷)

若二叉樹為空，則執行空操作。否則：

1、中序遍歷左子樹；

2、訪問根結點；

3、中序遍歷右子樹。

后序遍歷：(又稱為后根遍歷)

若二叉樹為空，則執行空操作。否則：

1、后序遍歷左子樹；

2、后序遍歷右子樹；

3、訪問根結點。

例：已知一棵二叉樹的中序遍歷序列是：FDGBACHE,其后序遍歷序列是：FGDBHECA

求其前序遍歷序列。

一棵二叉樹的前序遍歷序列為ABDGCFK,中序遍歷序列為DGBAFCK,則結點

的后序遍歷序列是()

A、ACFKDBGB、GDBFKCAC、KCFAGDBD、ABCDFKG

七、排序(Sort)：

所謂排序，就是指整理文件中的記錄，使之按關鍵字遞增(或遞減)次序排

列起來。

?冒泡排序(BubbleSorting)：

通過對待排序序列從后向前或從前向后(從下標較大的元素開始)，依次比較

相鄰元素的排序碼，若發現逆序則交換，使排序碼較大的元素逐漸從前部移向后

部或較小的元素逐漸從后部移向前部(從下標較大的單元移向下標較小的單元)。

直接選擇排序(SelectionSorting)：

掃描整個線性表，從中選出最小的元素，將它交換到表的最前面；然后對剩

下的子表采用同樣的方法，直到子表空為止。

直接插入排序(InsertionSorting)：

每次將一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的子文件

中的適當位置，直到全部記錄插入完成為止。

。快速排序(QuickSorting)：任取待排序序列中的某個元素作為基準(一般取

第一個元素)，通過--趟排序，將待排元素分為左右兩個子序列，左子序列

元素的排序碼均小于或等于基準元素的排序碼，右子序列的排序碼則大于基

準元素的排序碼，然后分別對兩個子序列繼續進行排序，直至整個序列有序。

各種內部排序方法的比較

時間復雜度

排序方法空間復雜度

最好時間平均時間最壞時間

直接插入0(n)0(n2)0(n2)0(1)

直接選擇0(n2)0(n2)0(n2)0(1)

冒泡0(n)0(n2)0(n2)0(1)

快速0(nylon)0(nylon)0(n2)0(glen)

堆0(nylon)0(nylon)0(nylon)0(1)

例：對一個具有n個元素的序列進行冒泡排序，在最壞情況下，要進行交換的次

數是()

A、n(n+l)/2B、n(n'l)/2C、n*n/2D、n(n+l)/2-l

對n個元素進行冒泡排序過程中，最好情況下的時間復雜性為()

A、0(1)B、0(log2n)C、0(n)D、0(n)

對n個元素進行快速排序的過程中，平均情況下的時間復雜性為()

A、0(1)B、0(glen)C、0(n2)D、0(nylon)

八、查找(Searching)：

所謂查找是指給定一個值K,在含有n個結點的表中找出關鍵字等于給定值

K的結點。若找到，則查找成功，返回該結點的信息或該結點在表中的位置;

否則查找失敗，返回相關的提示信息。

?順序查找(SequentialSearch)的基本思想是：從表的一端開始，順序掃描

線性表，依次將掃描到的結點關鍵字和給定值K相比較，若當前掃描到的結

點關鍵字與K相等，則查找成功；若掃描結束后，仍未找到關鍵字等于K的

結點，則查找失敗。順序查找即適用順序存儲結構，又適用鏈式存儲結構。

查找成功的平均查找長度為：（n為結點數目）

（1+2+3+4+???+□）/n=（n+l）/2

二分查找（BinarySearch）又稱折半查找，它是一種效率較高的查找方法，

二分查找要求線性表是有序表，即表中結點按關鍵字有序，并且要用向量作

為表的存儲結構。另外，二分查找只適用順序存儲結構，在鏈式存儲結構上

王汴立即一分杳找

查找成功時的平均魯找長度：（n為結點數目）

n+1,,.、,

lg（n+l）-l

n

當n很大時，可用近似公式：lag（n+l）-l表示

二.程序設計

2.1程序設計方法與風格

程序設計是一門技術，需要相應理論、技術、方法和工具來支持。程序設計方法

和技術的發展而言，主要經過了結構化程序設計和面向對象的程序設計階段。

養成良好的程序設計的設計風格，主要考慮下述的因素：

1.源程序文檔化

源程序文檔化應考慮如下兒點：

（1）符號名的命名：符號名的命名有一定含義，便于理解

（2）程序注釋：正確的注釋幫助讀者理解程序

（3）視覺組織：程序層次清晰

2.數據說明的方法

數據說明應考慮如下幾點：

（1）數據說明的次序規范化

（2）說明語句中變量安排有序化。

（3）使用注釋來說明復雜數據結構

3語句的結構

程序%該簡單易懂，語句構造應該簡單直接。應該注意的是：

（1）在一行內只寫一條語句

（2）程序編寫應優選考慮清晰性

（3）除非對效率有特殊要求，程序編寫要清晰第一、效率第二

（4）首先要保證程序正確，然后要求提高速度

（5）避免使用臨時變量而使程序可讀性下降

（6）避免不必要的轉移

（7）盡可能使用庫函數

（8）避免使用復雜的條件語句

（9）盡量減少使用“否定”條件的條件語句

（10）數據結構要有利于程序的簡化

（11）要模塊化，使模塊功能盡可能單一化

（12）利用信息隱藏，確保每一個模塊的獨立性

（13）從數據出發去構造程序

（14）不要修補不好的程序，要重新編寫

4.輸入和輸出

無論是批處理的輸入和輸出方式，還是交互式的輸入和輸出方式，在設計

和編程時都應該考慮如下原則：

（1）對所有的輸入數據都要檢驗數據的合理性

（2）檢查輸入項的各種重要組合的合理性

（3）輸入格式要簡單。

（4）輸入數據時，應允許使用自由格式

（5）應允許缺省值

（6）輸入一批數據時，最好使用輸入結束標志

（7）在交互式輸入/輸出方式進行輸入時，要在屏幕上使用提示符明確提示輸入

要求，在數據輸入過程中和輸入結束時應在屏幕給出狀態信息

（8）當程序設計語言對輸入格式有嚴格要求時，應保持輸入格式與輸出語句的

一致性。給所有輸入加注釋，并設計輸出報表格式。

2.2結構化程序設計

2.2.1結構化程序設計的原則

結構化程序設計方法主要原則包括：

1.自頂向下。設計程序時先考慮總體，后考慮細節

2.逐步求精。對復雜問題，逐步細化。

3.模塊化。

4.限制使用got語句

2.2.2結構化程序的基本結構與特點

結構化程序設計方法是程序設計的先進方法和。和采用結構化程序設計方法

編寫程序，可使程序結構良好、易讀、易理解、易維護。結構化程序設計方法基

本可用三種基本結構就可實現。

1.順序結構

順序結構是順序順序執行結構，即是按照程序語句的自然順序，一條?條語句地

執行。

2.選擇結構

選擇結構又稱分支結構，它包括簡單選擇和多分支選擇，這種結構可以根據給定

條件，判斷執行哪一個分支中的語句。

3.重復結構

重復結構乂稱為循環結構。它根據給定的條件判斷是否重復執行某一段相同的程

序。

2.2.3結構化程序設計原則和方法的應用

在結構化程序設計的具體實施中，要注意把握如下要素：

（1）使用程序設計語言中的順序、選擇、循環等控制結構表示程序的控制邏輯

（2）選用的控制結構只準許有一個入口和一個出口

（3）程序語句組成容易識別的程序專項，每塊只有一個入口和一個出口

（4）復雜結構應該用嵌套的基本控制結構進行組合嵌套來實現

（5）語言中所沒有的控制結構，應該采用前后一致的方法來模擬

（6）嚴格控制GOTO語句使用。

2.3面向對象的程序設計

2.3.1關于面向對象方法

面向對象（ObjectOriented）方法已經發展成為主流的軟件開發方法。面向對

象方法的形成起源于實現語言，首先對設計語言的研究，隨之形成面向對象分析

和設計方法。

面向對象方法的本質，就是主張從客觀世界固有的事物出發來構造系統，提倡用

人類在現實生活中常用的思維方法來認識、理解和描述客觀事物，強調最終建立

的系統能夠映射問題域。也就是說，系統中的對象以及對象之間的關系能夠如實

反映問題域中固有事物及其關系。

面向對象方法有如下優點：

1.與人類習慣的思維方法一致

面向對象和技術以對象為核心，對象是由數據和容許的操作組成的封裝體，

與客觀實體有直接的對應關系。對象之間通過傳遞消息互相聯系，以模擬現實世

界中不同事物彼此之間的聯系。如CD播放器、媒體播放器、軟件窗口等等

2.穩定性好

面向對象的軟件系統的結構是根據問題領域的模型建立起來的，當對系統的

功能需求變化時并不會引起軟件結構的整體變化，往往僅需要作一些局部性的修

改。

3.可重用性好

軟件重用是指在不同的軟件開發過程中重復使用相同或相似軟件元素(一般稱為

類)的過程。重用是提高軟件生產率的最主要的方法。

利用可重用的軟件成分構造新的軟件系統，一個對象類可以重復使用，對象類可

以創建，也以在已有的類上修改，但不影響原有類。

4.易于開發大型軟件產品

可以把一個大型產品看作一系列互相獨立的小產品來處理，這樣不公降低了

技術難度，而又使開發工作的管理變得容易。

5.可維護性好

一般用傳統的開發方法和面向過程的方法開發出來的軟件很難維護，而面向

對象的方法開發的軟件可維護性好。

(1)穩定性較好

(2)易于修改

(3)易于理解

(4)易于測試和調試

2.3.2面向對象方法的基本概念

關于面向對象方法，對其概念有許多不同的看法，但都涵蓋了對象及對象屬

性、方法、類、繼承、多態性兒個基本要素。

1.對象(object)

對象是面向對象方法中最基本的概念。對象用來表示客觀世界中的任何實體。

面向對象的程序設計方法中涉及的對象是系統中用來描述客觀事物的一個實體，

是構成系統的一個基本單位，它由--組表示其靜態特征的屬性和它可執行的一組

操作組成。

對象有如下特點：

(1)標識惟一性

(2)分類性

(3)多態性

(4)封裝性

(5)模塊獨立性好

2.類(Class)和實例(Instance)

將屬性、操作相似的對象歸為類，類具有共同屬性、共同方法的對象的集合。

如中圖中命令按鈕就是同類對象。

3.消息(Message)

面向對象的世界是通過對象與對象彼此的相互合作來推動的，對象間的這種相互

合作需要一個機制協助進行，這的機制稱為“消息”。

消息是一個實例與另一個實例之間傳遞的信息，它請求對象執行某一處理或回答

某一要求的信息，它統一了數據流和控制流。

一個消息由三部分組成：

(1)接收消息的對象的名稱

(2)消息標識符(也稱消息名)

(3)零個或多個參數

比如在窗體上畫一個圓,對象名MyForm,消息名Circle,參數(50,50)為圓心,25

為半徑

MyForm.Circle(50,50),25

4.繼承(Inheritance)

繼承是面向對象的方法的一個主要特征。繼承是使用已有的類定義作為基礎(直

接獲得已有的性質和特征)建立新類的定義技術。

已有的類可以當做基類引用，則新類可當做派生類引用。

如右圖就是VB中的基類：

5.多態性(Polymorphism)

對象根據所接受的消息而做出動作，同樣的消息被不同的對象接受時可導致

完全不同的行動，該現象稱為多態性

三.軟件工程基礎

一、基本概念：

軟件(Software)：軟件是一種產品(邏輯產品)，指的是計算機中程序及其說

明程序的各種文檔。“程序”是計算任務的處理對象和處理規則的描述；“文

檔”是有關計算機程序功能、設計、編制、使用的文字或圖形資料。

?軟件危機的表現：

1、軟件需求的增長得不到滿足

2、軟件開發成本和進度無法控制

3、軟件質量難以保證

4、軟件不可維護或維護程度非常低

5、軟件成本不斷提高

6、軟件開發生產效率的提高趕不上硬件的發展和應用需求的增長

?軟件工程(SoftwareEngineering)：用工程化的方法、科學知識和技術原理

來定義、開發、維護軟件的一門學科。

軟件工程的目標：

付出較低的開發成本；達到要求的軟件功能；取得較好的軟件性能；開發的

軟件易于移植；需要較低的維護費用；能按時完成開發任務，及時交付使用；

開發的軟件可靠性高。

?軟件工程研究的主要內容是軟件開發技術和軟件開發管理兩個方面。

軟件生存周期：是指一個軟件從提出開發要求開始直到該軟件報廢(停止運

行)為止的整個時期。

軟件生存周期模型：是描述軟件開發過程中各種活動如何執行的模型。

常用的模型有：瀑布模型、增量模型、螺旋模型、噴泉模型、變換模型和基

于知識的模型

瀑布模型是將軟件生存周期各個活動規定為依線性順序連接的若干階段的模型。

主要包括問題定義及可行性分析、項目開發計劃、需求分析、概要設計、詳細設

計、編碼、測試和維護幾個階段。

例：下列描述中正確的是（）

A、程序就是軟件B、軟件開發不受計算機系統的限制

C、軟件既是邏輯實體，又是物理實體D、軟件是程序、數據

與相關文檔的集合

二、軟件可行性研究與項目開發計劃：

軟件可行性研究的目的是用最小的代價在盡可能短的時間內確定該軟件項

目是否能夠開發，是否值得去開發。

可行性研究的任務：

A、技術可行性

B、經濟可行性

C、社會可行性（法律可行性）

可行性研究的具體步驟：

1、確定項目規模和目標

2、研究正在運行的系統

3、建立新系統的高層邏輯模型

4、導出和評價各種方案

5、推薦可行的方案

6、編寫可行性研究報告

三、軟件需求分析：

需求分析是指開發人員要準確理解用戶的要求，進行細致的調查分析，將用

戶非形式的需求陳述轉化為完整的需求定義，再由需求定義轉換到相應的形

式功能規約（需求規格說明）的過程。

?需求分析的基本任務：

1、問題識別

A、功能需求

B、性能需求

C、環境需求

n田戶里面熏親

2、A析與綜合，導出軟件的邏輯模型

3、編寫文檔（需求規格說明書）

?需求分析的方法：

1、結構化分析（StructuredAnalysis）：是面向數據流進行需求分析的方法。

SA方法利用圖形等半形式化的描述方式表達需求，主要描述工具：

A、數據流圖（DFD）：是SA方法中用于表示系統邏輯模型的一種工具，以圖形的

方式描繪數據在系統中流動和處理的過程。

B、數據字典（DD）：用以定義數據流圖中的各個成分的具體含義，為系統的分析、

設計及維護提供了有關元素的一致的定義和詳細的描述。

C、描述加工邏輯的結構化語言、判定表、判定樹

2、IDEF方法（是ICAMDefinition的縮寫）：

是一種用于進行復雜系統分析和設計的方法，是在結構化分析和設計技術的

基礎上提出來的。

3、面向對象分析方法（OOP）：

將客觀世界的事物抽象為對象，通過屬性和方法描述對象的狀態和行為，具

有繼承、封裝和多態性等特征。

例：軟件開發的結構化分析方法中，常用的描述軟件功能需求的工具是（）

A、業務流程圖、處理說明B、軟件流程圖、模塊說明

C、數據流程圖、數據字典D、系統流程圖、程序編碼

四、軟件概要設計：

將軟件需求轉換為軟件表示的過程。

?軟件概要設計的基本任務：

1、設計軟件系統結構

2、數據結構及數據庫設計（概要設計、邏輯設計、物理設計）：

3、編寫概要設計文檔：

4、評審：

軟件設計的方法：

模塊化：模塊在程序中是數據說明、可執行語句等程序對象的集合，或者是

單獨命名和編址的元素，如高級語言中的過程、函數、子程序等。

?模塊獨立性指每個模塊只完成系統要求的獨立的子功能，并且與其他模塊的

聯系最少且接口簡單。其度量標準是：耦合性和內聚性

耦合性也稱塊間聯系，指軟件系統結構中各模塊間相互聯系緊密程度的一種

度量。模塊之間聯系越緊密，其耦合性就越強，模塊的獨立性則越差。

?內聚性也稱塊內聯系，指模塊功能強度的度量，即一個模塊內部各個元素（語

句之間、程序段之間）彼此結合的緊密程度的度量。

將軟件系統劃分模塊時，盡量做到高內聚低耦合。

例：為了使模塊盡可能獨立，要求（）

A、模塊的內聚程序要盡量高，且各模塊間的耦合程序要盡量強

B、模塊的內聚程序要盡量高，且各模塊間的耦合程序要盡量弱

C、模塊的內聚程序要盡量低，且各模塊間的耦合程序要盡量弱

D、模塊的內聚程序要盡量低，且各模塊間的耦合程序要盡量強

五、軟件詳細設計：

主要確定每個模塊具體執行過程

軟件詳細設計的基本任務：

1、為每個模塊進行詳細的算法設計：

2、為模塊內的數據結構進行設計：

3、對數據庫進行物理設計：

4、輸入、輸出格式設計

5、編寫詳細設計說明書：

6、評審：

詳細設計常用三種工具：

圖形（流程圖、盒圖、問題分析圖PAD）、

表格（判定表）、

語言（過程設計語言，乂稱為偽碼）

六、軟件編碼：

主要是將詳細設計得到的處理過程描述轉換為基于某種計算機語言的程序

常用的計算機語言：Pascal,C、C++、Java等

七、軟件測試：

軟件測試代表了需求分析、設計、編碼的最終復審。軟件測試貫穿于軟件開

發的全過程。

?軟件測試的目的：

1、軟件測試是為了盡可能多地發現程序中的錯誤而執行程序的過程。

2、一個好的測試用例能夠發現至今尚未發現的錯誤。

3、一個成功的測試是發現了至今尚未發現的錯誤的測試。

軟件測試的原則：

1、測試用例應由輸入數據和預期的輸出數據兩部分組成。

2、測試用例不僅選用合理的輸入數據，還要選擇不合理的輸入數據

3、除了檢查程序是否做了它應該做的事

4、應制定測試計劃并嚴格執行，排除隨意性

5、長期保留測試用例

6、對發現錯誤較多的程序段，應進行更深入的測試

7、程序員避免測試自己的程序

軟件測試方法：

1、靜態測試：

是指被測試程序不在機器上運行，而是采用人工檢測和計算機輔助靜態分

析的手段對程序進行檢測。

2、動態測試：是指通過運行程序發現錯誤

A、黑盒測試法（功能測試）：

主要對軟件的接口進行測試，依據需求規格說明書，檢查程序是否滿足功能

要求。常用的技術是等價類劃分法、邊界值分析法、錯誤推測法、因果圖法、綜

合策略法

B、白盒測試法（結構測試）：

主要測試程序的內部結構和處理過程。常用的技術是語句覆蓋、條件覆蓋、

路徑覆蓋、判定覆蓋等

軟件測試的實施：

1、單元測試：

單元測試是對軟件設計的最小單位——模塊（程序單元）進行正確性檢驗測

試，主要針對模塊的以下五個基本特征進行測試：

A、模塊接口

B、局部數據結構：

C、重要的執行路徑：

D、錯誤處理測試：

E、邊界條件：

2、集成測試：

集成測試是指在單元測試的基礎上，將所有模塊按照設計要求組裝成一個完

整的系統進行的測試，故也稱組裝測試或聯合測試。

主要方法有兩種：

非漸增式測試：首先對每個模塊分別進行單元測試，然后再把所有的模塊按

設計要求組裝在一起進行測試。

漸增式測試：逐個把未經過測試的模塊組裝到已經過測試的模塊上去，進行

集成測試,每加入一個新模塊進行一次集成測試,重復此過程直至程序組裝完畢。

3、確認測試：

確認測試乂稱有效性測試，它的任務是檢查軟件的功能與性能是否與需求規

格說明書中確定的指標相符合，因而需求規格說明是確認測試的基礎。

4、系統測試：

系統測試是通過測試確認的軟件作為整個計算機系統的一個元素，與計算機

硬件、外設、支撐軟件、數據和人員等其他系統元素組合在一起，在實際運行環

境下對計算機系統進行一系列的集成測試和確認測試。

程序調試：

調試是在進行了成功的測試之后才開始的工作，目的是確定錯誤的原因和位

置，并改正錯誤，又稱為糾錯。

例：軟件測試的目的是（）

A、證明軟件的正確性B、找出軟件系統中存在的所有錯

誤

C、盡可能多地發現軟件系統中的錯誤D、證明軟件系統中存在錯誤

在軟件測試方法中，黑箱測試法和白箱測試法是常用的方法，其中黑箱測試

法主要是

用于測試（）

A、結構合理性B、軟件外部功能C、程序正確性D、程序內部邏輯

八、軟件維護：

軟件投入使用后進行的階段，是軟件生存周期中時間最長的一個階段，所花

費的精力和費用也是最多的一個階段。主要是因為：隱含的錯誤要修改；新增的

功能要加入進去；環境的變化對程序進行變動等。

軟件維護的內容有四類：

1、校正性維護：

為了識別和糾正錯誤，修改軟件性能上的缺陷，其占整個維護工作的21%

2、適應性維護：

為了使應用軟件適應環境（硬件、系統軟件、數據）的變化而修改軟件的過程

稱為適應性維護，其占整個維護工作的25%

3、完善性維護：

增加軟件功能、增強軟件性能、提高軟件運行效率而進行的維護活動稱為完

善性維護，其占整個維護工作的50%

4、預防性維護：

為了提高軟件的可維護性和可靠性而對軟件進行的修改稱為預防性維護，其

占整個維護工作的4%

例：軟件維護是指（）

A、維護軟件正常運行B、軟件的配置更新

C、對軟件的改進、適應和完善D、軟件開發期的一個階段

軟件生命周期中所花費用最多的階段是（）

A、詳細設計B、軟件編碼C、軟件測試D、軟件維護

四.數據庫原理基礎

一、基本概念:

數據處理：是指將數據轉換成信息的過程

數據管理是指對數據的組織、分類、編碼、存儲、檢索和維護提供操作手段

其經歷了以下階段：

1、人工管理

2、文件系統

3、數據庫系統

4、分布式數據庫系統階段

5、面向對象的數據庫系統階段

數據庫(Database)：是指存儲在計算機存儲設備上的結構化的相關數據的集

合，不僅包括數據本身，還包括事物之間的聯系。

數據庫應用系統(DBAS)：是指系統開發人員利用數據庫系統資源開發出來

的，面向某一類實際應用的應用軟件系統。

數據庫管理系統(DBMS)：對數據庫的建立、使用和維護進行管理和配置的軟

件系統。是數據庫系統的核心

數據庫系統(DBS):由硬件系統、數據庫集合、數據庫管理系統及相關軟件、

數據庫管理員和用戶組成。

數據庫系統的特點：

實現數據共享、減少數據冗余

采用特定的數據模型

具有較高的數據獨立性

統一的數據控制功能

實體：客觀存在并且可以相互區別的事物稱為實體。

實體的屬性：實體所具有的物性稱為實體的屬性。

?實體集：同類型的實體的集合稱為實體集。

實體型：屬性的集合表示一種實體類型，稱為實體型。

例：數據庫管理系統能實現對數據庫中數據的查詢、插入、修改和刪除，這類功

能稱為()

A、數據定義功能B、數據管理功能C、數據操縱功能D、數據控制功能

?聯系：實體之間的對應關系。

聯系的類型：

1、一對一聯系：表現為主表中的每一條記錄只與相關表中的一條記錄相關

聯。

例如：班級與班長，學校與校長

2、一對多聯系：表現為主表中的每一條記錄與相關表中的多條記錄相關聯。

例如：班級與學生，部門與職工

3、多對多聯系：表現為一個表中的多個記錄在相關表中同樣有多個記錄相

關聯。

例如：學生與課程，工程項目與零件

數據模型：不僅反映事物本身，還用來表示實體及實體之間聯系的方法。

1、層次模型：用樹形結構表示實體及其之間聯系的模型稱為層次模型。

2、網狀模型：用網狀結構表示實體及其之間聯系的模型稱為網狀模型。

3、關系模型：用二維表結構來表示實體及實體之間的聯系的模型稱為關系

模型。

一個二維表稱為一個關系，在VFP稱為數據表。一個關系不僅表示實體本

身還表示實體之間的聯系。

例：用樹形結構表示實體之間聯系的模型是()

A、關系模型B、網狀模型C、層次模型D、以上三個都是

二、關系數據庫：

*元組(Record)：在一個關系中，水平方向的行稱為元組。在VFP中稱為記錄

屬性(Field)：一個二維表中垂直方向的列稱為屬性。在VFP中稱為字段名

域(Domain)：屬性的取值范圍。根據數據類型和寬度來決定的。

?關鍵字(PrimalKey)：其值能夠惟一標識一個元組的屬性或屬性的組合。

注：關鍵字不能出現空值或重復值

?外部關鍵字(ForeignKey)：如果表中的一個字段不是本表的主關鍵字或侯

選關鍵字，而是另外一個表的主關鍵字或侯選關鍵字，這個字段在本表中稱

為外部關鍵字。

?關系性質：

二維表中元組的個數是有限的——元組個數有限性

二維表中元組均不相同——元組的惟一性

二維表中元組的次序可以任意交換——元組的次序無關性

二維表中元組的分量是不可分割的基本數據項——元組分量的原子性

二維表中屬性名各不相同——屬性名惟一性

二維表中屬性與次序無關，可任意交換——屬性的次序無關性

例：關系數據模型中表示實體和實體間的聯系的結構是()

A、樹型B、網狀C、二維表D、對象

三、關系運算：

并(Union)：是由兩個關系的元組組成的集合。(兩個關系必須具有相同的

關系模式)

差(Difference)：若有兩個相同結構的關系R和S,R差S的結果屬于R但

不屬于S的元組組成的集合。

?交(Intersection)：若有兩個相同的結構關系R和S,交的結果為兩個關系

共同的元組。

?選擇(Selection)：從關系中找出滿足給定條件的元組的操作稱為選擇。

投影(Projection)：從關系模式中指定若干個屬性組成新的關系稱為投影。

聯接(Join)：是關系的橫向結合，關系模式改變了，是多個關系的關系模

式的組合。聯接的結果是多個關系中滿足條件的元組。

2002年9月全國計算機考試VF二級考試筆試試題

一、選擇題((一)——(35)每小題2分，共70分)

下列各題A)、B)、C)、D)四個選項中，是有一個選項是正確的。請將正確

選項添涂在答題卡相應的位置上，答在試卷上不得分。

(1)在寫列四個選項中，不屬于基本關系運算的是

A)連接B)投影C)選擇D)排序

(2)如果一個班只能有一個班長，而且一個班長不能同時擔任其他班的班長，

班級和班長兩個實體之間的關系屬于

A)?對一聯系B)一對二聯系C)多對多聯系D)一對多聯系

(3)VF支持的數據模型是

A)層次數據模型B)關系數據模型C)網狀數據模型D)樹狀數據模型

(4)VF的命令窗口中鍵如CREATEDATA命令以后，屏幕會出現一個創建對話框,

要想完成同樣的工作，還可以采取如下步驟

A)單擊“文件”菜單中的“新建”按鈕，然后在新建對話框中選定“數據庫”

單選鈕，再單擊“新建文件”命令按鈕

B)單擊“文件”菜單中的“新建”按鈕，然后在新建對話框中選定“數據庫”

單選鈕，再單擊“向導”命令按鈕

C)單擊“文件”菜單中的“新建”按鈕，然后在新建對話框中選定“表”單選

鈕，再單擊“新建文件”命令按鈕

D)單擊“文件”菜單中的“新建”按鈕，然后在新建對話框中選定“表”單選

鈕，再單擊“向導”命令按鈕

(5)將內存變量定義為全局變量的VF命令是

A)LOCALB)PRIVATEC)PUBLICD)GLOBAL0(6)擴展名為DBC的文件是

A)表單文件B)數據庫表文件C)數據庫文件D)項目文件

(7)建設已經生成了名為mymenu的菜單問，執行該菜單文件的命令是

A)DOmymenuB)DOmymenu.mprC)DOmymenu.pjxD)DOmymenu.mnxO(8)

下面有關索引的描述正確的是

A)簡化里索引以后。原來的數據庫表文件中記錄的物理順序將被改變

B)索引與數據庫表的數據存儲在一個文件中

C)創建索引是創建一個指向數據庫表文件記錄的指針構成的文件

D)使用索引并不能加快對表的查詢操作

(9)若建立索引的字段值不允許重復，并且一個表中只能創建一個。它應該是

A)主索引B)唯一索引C)后選索引D)普通索引

(10)參照完整性的規則不包括

A)更新規則B)刪除規則C)插入規則D)檢索規則

(11)一數據庫名為student,要想打開該數據庫，應使用的命令

A)OPENstudentB)OPENDATAstudentC)USEDATAstudentD)USEstudent

(12)下列函數中函數值為字符型的是

A)DATE()B)TIME()C)YEAR()D)DATETIME()

(13)在下面的數據類型中默認為.F.的是

A)數值型B)字符型C)邏輯型D)日期型

(14)在下面有關HAVING子句描述錯誤的是

A)HAVING子句必須與GROUPBY子句同時使用，不能單獨使用

B)使用HAVING子句的同時不能使用WHERE子句

C)使用HAVING子句的同時可以使用WHERE子句

D)使用HAVING子句的作用是限定分組的條件

(15)——(27)使用的數據如下：

當前盤當前目錄下有數據庫db_stock,其中有數據庫表stock,dbf,該數據庫表

的內容是：股票代碼股票名稱單價交易所0600600青島啤酒7.48上海

0600601方正科技15.20上海0600602廣電電子10.40上海0600603興業

房產12.76上海0600604二紡機9.96上海0600605輕工機械14.59上海

0000001深發展7.48深圳0000002深萬科12.50深圳

(15)執行如下SQL語句后OSELECT*FROMstockINTODBFstockORDERBY單

價

A)系統將會提示出錯信息

B)會生成一個按“單價”升序排列的表文件，將原來的stock,dbf文件覆蓋

C)會生成一個按“單價”降序排列的表文件，將原來的stock,dbf文件覆蓋

D)不會生成排序文件，只能在屏幕上顯示一個按“單價”排序的結果

(16)執行下列程序以后，內存變量a的內容是OCLOSEDATABASE0a=00USEstock

OGOTOPODOWHILE.NOT.EOF()OIF單價>100a=a+10ENDIFOSKIPOENDD

A)1B)3C)5D)7

(17)有如下SQLSELECT語句OSELECT*FORMstockWHERE單價BETWEEN12.76

AND15.20與該語句等價的是

A)SELECT*FORMstockWHERE單價<=15.20.AND.單價>=12.76

B)SELECT*FORMstockWHERE單價<15.20.AND.單價>12.76

C)SELECT*FORMstockWHERE單價>=15.20.AND.單價<=12.76

D)SELECT*FORMstockWHERE單價>15.20.AND.單價<12.76

(18)如果在建立數據庫表stock,dbf時，將單價字段的字段有效性規則設為“單

價>0"，通過該設置，能保證數據的

A)實體完整性B)域完整性C)參照完整性D)表完整性

(19)在當前盤當前目錄下刪除表stock的命令是

A)DROPstockB)DELETETABLEstockC)DROPTABLEstockD)DELETEstock

(20)有如下SQP語句OSELECTmax(單價)INTOARRAYaFROMstock。執行該語

句后

A)a[l]的內容為15.2B)a[l]的內容為6

C)a[0]的內容為15.2D)a[0]的內容為6

(21)有如下SQP語句OSELECT股票代碼，avg(單價)as均價FROM

stockOGROUPBY交易所INTODBFtemp0執行該語句后temp表中第二條記錄

的“均價”字段的內容是

A)ALTERTABLEstock股票名稱WITHc(10)

B)ALTERTABLEstock股票名稱c(10)

C)ALTERTABLEstockALTRE股票名稱c(10)

D)ALTERTABLEstock股票名稱c(10)

(23)有如下SQP語句OCREATEVIEWstock_viewASSELECT*FROMstockWHERE

交易所=“深圳”0執行該語句后產生的視圖包含的記錄數個是

A)1B)2C)3D)4

(24)有如下SQP語句OCREATEVIEWview_stockASSELECT股票名稱AS名稱、

單價FROMstockO執行該語句后產生的視函含有的字段名是

A)股票名稱、單價B)名稱、單價C)名稱、單價、交易所D)股票名趁、單

價、交易所(25)下面有關對視圖的描述正確的是

A)可以使用MODIFYSTRUCTURE命令修改視圖的結構

B)視圖不能刪除，否則影響原來的數據文件

C)視圖是對表的復制產生的

D)使用對視圖進行查詢時必須事先打開該視圖所在的數據庫

(26)執行如下SQP語句后OSELECTVDISTINCT單價FROMstock；0WHERE單價

=(SELECTmin(單價)FROMstock)INTODBFstock_x0表stock_x中的記錄個

數是

A)1B)203D)4

(27)求每個交易所的平均單價的SQP語句是

A）SELECT交易所，avg（單價）FROMstockGROUPBY單價

B）SELECT交易所，avg（單價）FROMstockORDERBY單價

C）SELECT交易所，avg（單價）FROMstockORDERBY交易所

D）SELECT交易所,avg（單價）FROMstockGROUPBY交易所

（28）視圖設計器中含有的、但查詢設計器卻沒有的選項卡是

A）篩選B）排序依據C）分組依據D）更新條件

（29）下面關于查詢描述正確的是

A）可以使用CREATEVIEW打開查詢設計器

B）使用查詢設計器可以生成所有的SQP查詢語句

C）使用查詢設計器生成的SQP語句存盤后將存放在擴展名為QPR的文件中

D）使用DO語句執行查詢時，可以不帶擴展名

（30）使用報表向導定義報表時，定義報表布局的選項是

A）列數、方向、字段布局B）列數、行數、字段布局

C）行數、方向、字段布局D）列數、行數、方向

（31）能夠將表單的Visible屬性設置為.T.,并使表單成為活動對象的方法是

A）HideB）ShowC）ReleaseD）SetFocus

（32）下面對編輯框（EditBox）控制屬性的描述正確的是

A）SelLength屬性的設置可以小于0

B）當ScrollBars的屬性值為0時，編輯框內包含水平滾動條

C）SeText屬性在做界面設計時不可用，在運動時可讀寫

D）Readonly屬性值為.T.,用戶不能使用編輯框上的滾動條

（33）下面對控件的描述正確的是

A）用戶可以在組合框中進行多重選擇

B）用戶可以在列表框中進行多重選擇

C）用戶可以在一個選項組中多個選項按鈕

D）用戶對一個表單內的一組復選框中只能選中其中一個

（34）確定列表框內的某個條目是否被選定應使用的屬性是0A）value

B）ColumnCountC）ListCountD）SelectedO（35）沒有關系RI和R2,經過關系

運算得到結果是S,則S是

A）一個關系B）一個表單C）一個數據庫D）一個數組

二、填空題（每空2分，共30分）請將答案分別寫在答題卡中的序號為［1］——［5］

的橫線上，答在試卷上不得分。

（1）VisualFoxPro6.0是一個［1］位的數據棵管理系統。

（2）在連接運算中，［2］連接是去掉重復屬性的等值連接。

（3）項目管理器的［3］選項卡用于顯示和管理數據庫、自由表和查詢等。

（4）自由表的擴展名是［4］。

(5)LEFT(“123456789"，LEN(“數據庫”))的計算結果是［5］。

（6）同一個表的多個索引可以創建在一個索引文件中，索引文件名與相關的表

同名，索引文件的擴展名是［6］,這種作因稱為［7］。

（7）用來確定復選框是否被選中的屬性是［8］,用來指定顯示在復選框旁

的文字的屬性是［9］

下面各題使用如下的“教師”表和“學院”表

“教師”表職工號姓名職稱年齡工資系號011020001肖天海副教授35

2000.0001011020002王巖鹽教授403000.0002011020003劉星魂講師25

1500.0001011020004張月新講師301500.00030111020005李明玉教授

342000.0001011020006孫民山教授472100.0002011020007錢無名教

授492200.00030“學院”表0系號系名001英語002會計003工商管理

（8）使用SQP語句將一條新的記錄插入學院表0INSERT［10］學院（系號，

系名）［113（“04”，“計算機”）

（9）使用SQP語句求“工商管理”系的所有職工的工資總和。0SELECT［12］（工

資）FROM教師OWHERE系號IN（SELECT系號FROM［13］WHERE系名=“工

商管理”）

（10）使用SQP語句完成如下操作（將所有教授的工資提高5%）0［14］教師SET

工資=工資*1.05［15］職稱="教授”

2002年9月VF試題答案（僅供參考）

DABACCBCADBBCBACABCABCBBDADDCABCBDA032自然數據.DBF123456.CDX

結構復合索引valueCAPTIONINTOvalueSSUM學院UPDATEWHERE

2003年4月全國計算機等級考試VF二級筆試試題

一、選擇題（⑴~（35）每小題2分，共70分）

下列各題A）、B）、C）、D）四個選項中，只有一個選項是正確的，請將正確選項

涂寫在大題卡相應位置上，答在試卷上不得分。

（1）VisualFoxProDBMS是

A）操作系統的一部分B）操作系統支持下的系統軟件

C）一種編譯程序D）一種操作系統

（2）VisualFoxProDBMS基于的數據模型是

A）層次型B）關系型C）網狀型D）混合型

（3）設有部門和職員兩個實體，每個職員只能屬于一個部門，一個部門可以有多

名職員，

則部門與職員實體之間的聯系類型是

A)m:nB)1:mC)m:kD)1:1

(4)在VisualFoxPro中，調用表設計器建立數據庫表STUDENT.DBF的命令是

A)MODIFYSTRUCTURESTUDENTB)MODIFYCOMMANDSTUDENT

C)REATESTUDENTD)CREATETABLESTUDENT

(5)在VisualFoxPro中，關于自由表敘述正確的是

A)自由表和數據庫表是完全相同的B)自由表不能建立字段級規則和約

C)自由表不能建立候選索引D)自由表不可以加入到數據庫中

(6)在VisualFoxPro中，建立數據庫表時，將年齡字段值限制在12~14之間的

這種約束屬于

A)實體完整性約束B)域完整性約束C)參照完整性約束D)視圖完整性約

(7)在VisualFoxPro中,運行表單TLSCX的命令是

A)DOT1B)RUNFORM1T1C)DOFORMT1D)DOFROMT1

⑻使用SQL語句進行分組檢索時，為了去掉不滿足條件的分組，應當

A)使用WHERE子句B)在GROUPBY后面使用HAVING子句

C)先使用WHERE子句，再使用HAVING子句。

D)先使用HAVING子句，再使用WHERE子句

(9)在VisualFoxPro的參照完整性規則不包括

A)更新規則B)刪除規則C)查詢規則D)插入規則

(10)在VisualFoxPro中，表結構中的邏輯型、通用型、日期型字段的寬度由

系統自動給出，它們分別為：

A)k4、8B)4、4、10C)l、10、8D)2、8、8