計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)

一.數(shù)據(jù)結(jié)構(gòu)與算法

一、基本概念：

?數(shù)據(jù)(Data)：信息的載體，能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的物理符號(hào)。

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

音、動(dòng)畫、圖像)。

數(shù)據(jù)元素(DataElement)：是數(shù)據(jù)的基本單位，有時(shí)也稱為元素、結(jié)點(diǎn)、頂

點(diǎn)、記錄，可以有若干個(gè)數(shù)據(jù)項(xiàng)(字段、域、屬性)組成。

數(shù)據(jù)結(jié)構(gòu)(DataStructure)：指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織

形式。其包括三個(gè)部分：

1、邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系

2、存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示。

3、數(shù)據(jù)的運(yùn)算(算法)：即對(duì)數(shù)據(jù)施加的操作

數(shù)據(jù)的邏輯結(jié)構(gòu)有兩大類：

1、線性結(jié)構(gòu)：

特征是：若結(jié)構(gòu)是非空集，則有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有

結(jié)點(diǎn)最多只有一個(gè)直接前趨和一個(gè)直接后繼。

例：一維數(shù)組、鏈表、棧、隊(duì)列、串

2、非線性結(jié)構(gòu)：

特征是：一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼。

例：多維數(shù)組、廣義表、樹、圖

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有以下基本存儲(chǔ)方法：

1、順序存儲(chǔ)方法：

該方法是將邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏

輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)，一般通過數(shù)組來實(shí)現(xiàn)的。

2、鏈接存儲(chǔ)方法：

該方法不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附

加的指針字段表示的。通過指針類型來實(shí)現(xiàn)的。

3、索引存儲(chǔ)方法：

該方法通常是在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，還建立附加的索引表，索引表中的每一項(xiàng)

稱為索引項(xiàng)，索引項(xiàng)的一般形式是：關(guān)鍵字，地址。

4、散列存儲(chǔ)方法：

該方法的基本思想是根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址，通過散列

函數(shù)實(shí)現(xiàn)。例：除余法散列函數(shù)、相乘取整法散列函數(shù)

?算法的基本特征：

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

的結(jié)果。

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

出現(xiàn)歧義性。

3、有窮性(Finiteness)：算法必須在有限時(shí)間內(nèi)做完，即必須在執(zhí)行有限個(gè)步

驟之后終止。

?時(shí)間復(fù)雜度：該算法執(zhí)行的時(shí)間耗費(fèi)，它是該算法所求解問題規(guī)模n的函數(shù)。

?空間復(fù)雜度：該算法執(zhí)行時(shí)所耗費(fèi)的存儲(chǔ)空間，它也是問題規(guī)模n的函數(shù)。

二、線性表：

?線性表(LinearList)：是由n性表0)個(gè)數(shù)據(jù)元素(結(jié)點(diǎn))ai,a2,a3,,a?

組成的有限序列。對(duì)于非空的線性表，有且僅有一個(gè)開始結(jié)點(diǎn)a“它沒有直

接前趨；有且僅有一個(gè)終端結(jié)點(diǎn)出，它沒有直接后繼；其余的結(jié)點(diǎn)有且僅有

一個(gè)直接前趨結(jié)點(diǎn)和一個(gè)直接后繼結(jié)點(diǎn)。

*線性表的存儲(chǔ)結(jié)構(gòu)：

1、順序存儲(chǔ)(SequentialList)：將線性表的結(jié)點(diǎn)按邏輯次序依次存放在一組地

址連續(xù)的存儲(chǔ)單元里，用這種方法存儲(chǔ)的線性表稱為順序表。

2、鏈?zhǔn)酱鎯?chǔ)(LinkedList)：邏輯上相鄰的結(jié)點(diǎn)，物理上也相鄰，存儲(chǔ)單元可以

是連續(xù)的，也可以是不連續(xù)的，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還存儲(chǔ)指向其后繼結(jié)

點(diǎn)的地址，用這種方法存儲(chǔ)的線性表稱為鏈表。

常見的運(yùn)算有：

表的初始化、求表的長(zhǎng)度、取表中的第I個(gè)結(jié)點(diǎn)、查找結(jié)點(diǎn)、插入新的結(jié)點(diǎn)、刪

除結(jié)點(diǎn)。

順序表和鏈表的比較：

1、基于空間的考慮：

A、順序表的存儲(chǔ)空間是靜態(tài)分配的，而鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的。

B、順序表占的存儲(chǔ)空間必須是連續(xù)的，而鏈表占的存儲(chǔ)空間可以是連續(xù)的，也

可是不連續(xù)的

C、順序表存儲(chǔ)密度為1,而鏈表中的每個(gè)結(jié)點(diǎn)，除了數(shù)據(jù)域外，還要額外的設(shè)

置指針域，存儲(chǔ)密度小于1

2、基于時(shí)間的考慮：

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

將要移動(dòng)近一半的結(jié)點(diǎn)。

B、順序表是隨機(jī)存取結(jié)構(gòu)，它的存取時(shí)間為0(1),而鏈表需從頭結(jié)點(diǎn)順著鏈掃

描鏈表。

總之，當(dāng)線性表的長(zhǎng)度變化不大，易于事先確定其大小時(shí)，為了節(jié)約存儲(chǔ)空

間，宜采用順序表作為存儲(chǔ)結(jié)構(gòu)；當(dāng)線性表的長(zhǎng)度變化較大，難以估計(jì)其存儲(chǔ)規(guī)

模時(shí)，以采用鏈表作為存儲(chǔ)結(jié)構(gòu)為好。若線性表的操作主要是進(jìn)行查找，很少做

插入和刪除操作時(shí)，采用順序表做存儲(chǔ)結(jié)構(gòu)為宜；對(duì)于頻繁進(jìn)行插入和刪除的線

性表，宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。

例：關(guān)于線性表的描述中，錯(cuò)誤的是()

A、線性表是線性結(jié)構(gòu)B、線性表的順序存儲(chǔ)結(jié)構(gòu)，必須占用一片連續(xù)

的存儲(chǔ)單元

C、線性表是單鏈表D、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，不必占用一片連續(xù)的存

儲(chǔ)單元

用數(shù)組表示線性表的優(yōu)點(diǎn)是()

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

C、可以動(dòng)態(tài)地分配存儲(chǔ)空間D、不需要占用一片連續(xù)的存儲(chǔ)空間

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

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

素時(shí)稱為空棧。是一種后進(jìn)先出的線性表，又稱為L(zhǎng)IF0表。

棧的基本運(yùn)算有：

棧的初始化、判?？铡⑴袟M、進(jìn)棧、出棧等

棧的存儲(chǔ)：

順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)

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

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

A、EDCBAB、DECBAC、DCEABD、ABCDE

四、隊(duì)列：

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

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

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

又稱為FIFO表。

隊(duì)列的基本運(yùn)算：

隊(duì)列的初始化、判隊(duì)空、判隊(duì)滿、入隊(duì)、出隊(duì)

隊(duì)列的存儲(chǔ)實(shí)現(xiàn)：

順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)

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

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

1

五、串：

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

串中所包含的字符個(gè)數(shù)稱為該串的長(zhǎng)度。

串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串，包含子串的串相應(yīng)地稱

為王串

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

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

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

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

?串的基本運(yùn)算：

求串長(zhǎng)、串復(fù)制、串聯(lián)接、串比較、字符定位、

六、樹(非線性結(jié)構(gòu))：

?樹(Tree)：是n(n>=0)個(gè)結(jié)點(diǎn)的有限集T,T(n=0)為空時(shí)稱為空樹,否則它

滿足如下兩個(gè)條件：

1、有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn)

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

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

在樹的樹形圖表示中，結(jié)點(diǎn)通常是用圓圈表示的，結(jié)點(diǎn)的名字一般是寫在圓

圈旁邊，有時(shí)亦可寫在圓圈內(nèi)。

度(Degree)：一個(gè)結(jié)點(diǎn)擁有的子樹數(shù)稱為該結(jié)點(diǎn)的度。一棵樹的度是指該樹

中結(jié)點(diǎn)的最大度數(shù)。

葉子(Leaf)：度為零的結(jié)點(diǎn)稱為葉子或終端結(jié)點(diǎn)

?分支結(jié)點(diǎn)(Node)：度不為零的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)。

?樹中某個(gè)結(jié)點(diǎn)的子樹之根稱為該結(jié)點(diǎn)的孩子(Child)結(jié)點(diǎn)或子結(jié)點(diǎn)，相應(yīng)的

該結(jié)點(diǎn)稱為孩子結(jié)點(diǎn)的雙親(Parents)結(jié)點(diǎn)或父結(jié)點(diǎn)。

同一個(gè)雙親的孩子稱為兄弟結(jié)點(diǎn)(Sibling)

?：?結(jié)點(diǎn)的層數(shù)(Level)是從根起算，設(shè)根的層數(shù)為1,其余結(jié)點(diǎn)的層數(shù)等于其雙

求結(jié)點(diǎn)的層數(shù)加1.

樹中結(jié)點(diǎn)的最大層數(shù)稱為樹的高度(Height)或深度(Depth).

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

到一個(gè)森林，反之，加上一-1結(jié)點(diǎn)作樹根，森林就變?yōu)?-棵樹。

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

或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的、分別稱作這個(gè)根的左子樹和右子樹的

二叉樹組成。

二叉樹中，每個(gè)結(jié)點(diǎn)最多只能有兩棵子樹.，并且有左右之分。

二叉樹的五種基本形態(tài)：

例：具有3個(gè)結(jié)點(diǎn)的二叉樹有兒種形態(tài)。

?滿二叉樹(FullBinaryTree)：一棵深度為k且有2k-l個(gè)結(jié)點(diǎn)的二叉樹稱為

滿二叉樹

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

上結(jié)點(diǎn)的度數(shù)可以小于2,并且最下…層上的結(jié)點(diǎn)都集中在該層最左邊的若

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

二叉樹的性質(zhì)：

性質(zhì)1：二叉樹第I層上的結(jié)點(diǎn)數(shù)目最多為2一(1>=1)

性質(zhì)2：深度為k的二叉樹至多有2k-l個(gè)結(jié)點(diǎn)(k>=l)

性質(zhì)3：在任意一棵二叉樹中，若終端結(jié)點(diǎn)的個(gè)數(shù)為n。，度為2的結(jié)點(diǎn)數(shù)為“，

則no=n2+l

性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[glen]+l(取下整)或

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

例：一棵二叉樹的結(jié)點(diǎn)數(shù)為18個(gè)，求它的最小高度

已知度為2的結(jié)點(diǎn)數(shù)為15個(gè)，求葉子結(jié)點(diǎn)數(shù)

二叉樹的遍歷：

?遍歷(Traversal)：是指沿著某條搜索路線，依次對(duì)樹中每個(gè)結(jié)點(diǎn)均做一次

且僅做一次訪問。

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

若二叉樹為空，則執(zhí)行空操作。否則：

1、訪問根結(jié)點(diǎn)；

2、前序遍歷左子樹；

3、前序遍歷右子樹。

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

若二叉樹為空，則執(zhí)行空操作。否則：

1、中序遍歷左子樹；

2、訪問根結(jié)點(diǎn)；

3、中序遍歷右子樹。

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

若二叉樹為空，則執(zhí)行空操作。否則：

1、后序遍歷左子樹；

2、后序遍歷右子樹；

3、訪問根結(jié)點(diǎn)。

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

求其前序遍歷序列。

一棵二叉樹的前序遍歷序列為ABDGCFK,中序遍歷序列為DGBAFCK,則結(jié)點(diǎn)

的后序遍歷序列是()

A、ACFKDBGB、GDBFKCAC、KCFAGDBD、ABCDFKG

七、排序(Sort)：

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

列起來。

?冒泡排序(BubbleSorting)：

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

相鄰元素的排序碼，若發(fā)現(xiàn)逆序則交換，使排序碼較大的元素逐漸從前部移向后

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

直接選擇排序(SelectionSorting)：

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

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

直接插入排序(InsertionSorting)：

每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子文件

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

?？焖倥判?QuickSorting)：任取待排序序列中的某個(gè)元素作為基準(zhǔn)(一般取

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

元素的排序碼均小于或等于基準(zhǔn)元素的排序碼，右子序列的排序碼則大于基

準(zhǔn)元素的排序碼，然后分別對(duì)兩個(gè)子序列繼續(xù)進(jìn)行排序，直至整個(gè)序列有序。

各種內(nèi)部排序方法的比較

時(shí)間復(fù)雜度

排序方法空間復(fù)雜度

最好時(shí)間平均時(shí)間最壞時(shí)間

直接插入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)

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

數(shù)是()

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

對(duì)n個(gè)元素進(jìn)行冒泡排序過程中，最好情況下的時(shí)間復(fù)雜性為()

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

對(duì)n個(gè)元素進(jìn)行快速排序的過程中，平均情況下的時(shí)間復(fù)雜性為()

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

八、查找(Searching)：

所謂查找是指給定一個(gè)值K,在含有n個(gè)結(jié)點(diǎn)的表中找出關(guān)鍵字等于給定值

K的結(jié)點(diǎn)。若找到，則查找成功，返回該結(jié)點(diǎn)的信息或該結(jié)點(diǎn)在表中的位置;

否則查找失敗，返回相關(guān)的提示信息。

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

線性表，依次將掃描到的結(jié)點(diǎn)關(guān)鍵字和給定值K相比較，若當(dāng)前掃描到的結(jié)

點(diǎn)關(guān)鍵字與K相等，則查找成功；若掃描結(jié)束后，仍未找到關(guān)鍵字等于K的

結(jié)點(diǎn)，則查找失敗。順序查找即適用順序存儲(chǔ)結(jié)構(gòu)，又適用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

查找成功的平均查找長(zhǎng)度為：（n為結(jié)點(diǎn)數(shù)目）

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

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

二分查找要求線性表是有序表，即表中結(jié)點(diǎn)按關(guān)鍵字有序，并且要用向量作

為表的存儲(chǔ)結(jié)構(gòu)。另外，二分查找只適用順序存儲(chǔ)結(jié)構(gòu)，在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上

王汴立即一分杳找

查找成功時(shí)的平均魯找長(zhǎng)度：（n為結(jié)點(diǎn)數(shù)目）

n+1,,.、,

lg（n+l）-l

n

當(dāng)n很大時(shí)，可用近似公式：lag（n+l）-l表示

二.程序設(shè)計(jì)

2.1程序設(shè)計(jì)方法與風(fēng)格

程序設(shè)計(jì)是一門技術(shù)，需要相應(yīng)理論、技術(shù)、方法和工具來支持。程序設(shè)計(jì)方法

和技術(shù)的發(fā)展而言，主要經(jīng)過了結(jié)構(gòu)化程序設(shè)計(jì)和面向?qū)ο蟮某绦蛟O(shè)計(jì)階段。

養(yǎng)成良好的程序設(shè)計(jì)的設(shè)計(jì)風(fēng)格，主要考慮下述的因素：

1.源程序文檔化

源程序文檔化應(yīng)考慮如下兒點(diǎn)：

（1）符號(hào)名的命名：符號(hào)名的命名有一定含義，便于理解

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

（3）視覺組織：程序?qū)哟吻逦?/p>

2.數(shù)據(jù)說明的方法

數(shù)據(jù)說明應(yīng)考慮如下幾點(diǎn)：

（1）數(shù)據(jù)說明的次序規(guī)范化

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

（3）使用注釋來說明復(fù)雜數(shù)據(jù)結(jié)構(gòu)

3語句的結(jié)構(gòu)

程序%該簡(jiǎn)單易懂，語句構(gòu)造應(yīng)該簡(jiǎn)單直接。應(yīng)該注意的是：

（1）在一行內(nèi)只寫一條語句

（2）程序編寫應(yīng)優(yōu)選考慮清晰性

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

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

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

（6）避免不必要的轉(zhuǎn)移

（7）盡可能使用庫函數(shù)

（8）避免使用復(fù)雜的條件語句

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

（10）數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡(jiǎn)化

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

（12）利用信息隱藏，確保每一個(gè)模塊的獨(dú)立性

（13）從數(shù)據(jù)出發(fā)去構(gòu)造程序

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

4.輸入和輸出

無論是批處理的輸入和輸出方式，還是交互式的輸入和輸出方式，在設(shè)計(jì)

和編程時(shí)都應(yīng)該考慮如下原則：

（1）對(duì)所有的輸入數(shù)據(jù)都要檢驗(yàn)數(shù)據(jù)的合理性

（2）檢查輸入項(xiàng)的各種重要組合的合理性

（3）輸入格式要簡(jiǎn)單。

（4）輸入數(shù)據(jù)時(shí)，應(yīng)允許使用自由格式

（5）應(yīng)允許缺省值

（6）輸入一批數(shù)據(jù)時(shí)，最好使用輸入結(jié)束標(biāo)志

（7）在交互式輸入/輸出方式進(jìn)行輸入時(shí)，要在屏幕上使用提示符明確提示輸入

要求，在數(shù)據(jù)輸入過程中和輸入結(jié)束時(shí)應(yīng)在屏幕給出狀態(tài)信息

（8）當(dāng)程序設(shè)計(jì)語言對(duì)輸入格式有嚴(yán)格要求時(shí)，應(yīng)保持輸入格式與輸出語句的

一致性。給所有輸入加注釋，并設(shè)計(jì)輸出報(bào)表格式。

2.2結(jié)構(gòu)化程序設(shè)計(jì)

2.2.1結(jié)構(gòu)化程序設(shè)計(jì)的原則

結(jié)構(gòu)化程序設(shè)計(jì)方法主要原則包括：

1.自頂向下。設(shè)計(jì)程序時(shí)先考慮總體，后考慮細(xì)節(jié)

2.逐步求精。對(duì)復(fù)雜問題，逐步細(xì)化。

3.模塊化。

4.限制使用got語句

2.2.2結(jié)構(gòu)化程序的基本結(jié)構(gòu)與特點(diǎn)

結(jié)構(gòu)化程序設(shè)計(jì)方法是程序設(shè)計(jì)的先進(jìn)方法和。和采用結(jié)構(gòu)化程序設(shè)計(jì)方法

編寫程序，可使程序結(jié)構(gòu)良好、易讀、易理解、易維護(hù)。結(jié)構(gòu)化程序設(shè)計(jì)方法基

本可用三種基本結(jié)構(gòu)就可實(shí)現(xiàn)。

1.順序結(jié)構(gòu)

順序結(jié)構(gòu)是順序順序執(zhí)行結(jié)構(gòu)，即是按照程序語句的自然順序，一條?條語句地

執(zhí)行。

2.選擇結(jié)構(gòu)

選擇結(jié)構(gòu)又稱分支結(jié)構(gòu)，它包括簡(jiǎn)單選擇和多分支選擇，這種結(jié)構(gòu)可以根據(jù)給定

條件，判斷執(zhí)行哪一個(gè)分支中的語句。

3.重復(fù)結(jié)構(gòu)

重復(fù)結(jié)構(gòu)乂稱為循環(huán)結(jié)構(gòu)。它根據(jù)給定的條件判斷是否重復(fù)執(zhí)行某一段相同的程

序。

2.2.3結(jié)構(gòu)化程序設(shè)計(jì)原則和方法的應(yīng)用

在結(jié)構(gòu)化程序設(shè)計(jì)的具體實(shí)施中，要注意把握如下要素：

（1）使用程序設(shè)計(jì)語言中的順序、選擇、循環(huán)等控制結(jié)構(gòu)表示程序的控制邏輯

（2）選用的控制結(jié)構(gòu)只準(zhǔn)許有一個(gè)入口和一個(gè)出口

（3）程序語句組成容易識(shí)別的程序?qū)ｍ?xiàng)，每塊只有一個(gè)入口和一個(gè)出口

（4）復(fù)雜結(jié)構(gòu)應(yīng)該用嵌套的基本控制結(jié)構(gòu)進(jìn)行組合嵌套來實(shí)現(xiàn)

（5）語言中所沒有的控制結(jié)構(gòu)，應(yīng)該采用前后一致的方法來模擬

（6）嚴(yán)格控制GOTO語句使用。

2.3面向?qū)ο蟮某绦蛟O(shè)計(jì)

2.3.1關(guān)于面向?qū)ο蠓椒?/p>

面向?qū)ο螅∣bjectOriented）方法已經(jīng)發(fā)展成為主流的軟件開發(fā)方法。面向?qū)?/p>

象方法的形成起源于實(shí)現(xiàn)語言，首先對(duì)設(shè)計(jì)語言的研究，隨之形成面向?qū)ο蠓治?/p>

和設(shè)計(jì)方法。

面向?qū)ο蠓椒ǖ谋举|(zhì)，就是主張從客觀世界固有的事物出發(fā)來構(gòu)造系統(tǒng)，提倡用

人類在現(xiàn)實(shí)生活中常用的思維方法來認(rèn)識(shí)、理解和描述客觀事物，強(qiáng)調(diào)最終建立

的系統(tǒng)能夠映射問題域。也就是說，系統(tǒng)中的對(duì)象以及對(duì)象之間的關(guān)系能夠如實(shí)

反映問題域中固有事物及其關(guān)系。

面向?qū)ο蠓椒ㄓ腥缦聝?yōu)點(diǎn)：

1.與人類習(xí)慣的思維方法一致

面向?qū)ο蠛图夹g(shù)以對(duì)象為核心，對(duì)象是由數(shù)據(jù)和容許的操作組成的封裝體，

與客觀實(shí)體有直接的對(duì)應(yīng)關(guān)系。對(duì)象之間通過傳遞消息互相聯(lián)系，以模擬現(xiàn)實(shí)世

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

2.穩(wěn)定性好

面向?qū)ο蟮能浖到y(tǒng)的結(jié)構(gòu)是根據(jù)問題領(lǐng)域的模型建立起來的，當(dāng)對(duì)系統(tǒng)的

功能需求變化時(shí)并不會(huì)引起軟件結(jié)構(gòu)的整體變化，往往僅需要作一些局部性的修

改。

3.可重用性好

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

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

利用可重用的軟件成分構(gòu)造新的軟件系統(tǒng)，一個(gè)對(duì)象類可以重復(fù)使用，對(duì)象類可

以創(chuàng)建，也以在已有的類上修改，但不影響原有類。

4.易于開發(fā)大型軟件產(chǎn)品

可以把一個(gè)大型產(chǎn)品看作一系列互相獨(dú)立的小產(chǎn)品來處理，這樣不公降低了

技術(shù)難度，而又使開發(fā)工作的管理變得容易。

5.可維護(hù)性好

一般用傳統(tǒng)的開發(fā)方法和面向過程的方法開發(fā)出來的軟件很難維護(hù)，而面向

對(duì)象的方法開發(fā)的軟件可維護(hù)性好。

(1)穩(wěn)定性較好

(2)易于修改

(3)易于理解

(4)易于測(cè)試和調(diào)試

2.3.2面向?qū)ο蠓椒ǖ幕靖拍?/p>

關(guān)于面向?qū)ο蠓椒?，?duì)其概念有許多不同的看法，但都涵蓋了對(duì)象及對(duì)象屬

性、方法、類、繼承、多態(tài)性兒個(gè)基本要素。

1.對(duì)象(object)

對(duì)象是面向?qū)ο蠓椒ㄖ凶罨镜母拍睢?duì)象用來表示客觀世界中的任何實(shí)體。

面向?qū)ο蟮某绦蛟O(shè)計(jì)方法中涉及的對(duì)象是系統(tǒng)中用來描述客觀事物的一個(gè)實(shí)體，

是構(gòu)成系統(tǒng)的一個(gè)基本單位，它由--組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組

操作組成。

對(duì)象有如下特點(diǎn)：

(1)標(biāo)識(shí)惟一性

(2)分類性

(3)多態(tài)性

(4)封裝性

(5)模塊獨(dú)立性好

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

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

如中圖中命令按鈕就是同類對(duì)象。

3.消息(Message)

面向?qū)ο蟮氖澜缡峭ㄟ^對(duì)象與對(duì)象彼此的相互合作來推動(dòng)的，對(duì)象間的這種相互

合作需要一個(gè)機(jī)制協(xié)助進(jìn)行，這的機(jī)制稱為“消息”。

消息是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信息，它請(qǐng)求對(duì)象執(zhí)行某一處理或回答

某一要求的信息，它統(tǒng)一了數(shù)據(jù)流和控制流。

一個(gè)消息由三部分組成：

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

(2)消息標(biāo)識(shí)符(也稱消息名)

(3)零個(gè)或多個(gè)參數(shù)

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

為半徑

MyForm.Circle(50,50),25

4.繼承(Inheritance)

繼承是面向?qū)ο蟮姆椒ǖ囊粋€(gè)主要特征。繼承是使用已有的類定義作為基礎(chǔ)(直

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

已有的類可以當(dāng)做基類引用，則新類可當(dāng)做派生類引用。

如右圖就是VB中的基類：

5.多態(tài)性(Polymorphism)

對(duì)象根據(jù)所接受的消息而做出動(dòng)作，同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致

完全不同的行動(dòng)，該現(xiàn)象稱為多態(tài)性

三.軟件工程基礎(chǔ)

一、基本概念：

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

明程序的各種文檔?！俺绦颉笔怯?jì)算任務(wù)的處理對(duì)象和處理規(guī)則的描述；“文

檔”是有關(guān)計(jì)算機(jī)程序功能、設(shè)計(jì)、編制、使用的文字或圖形資料。

?軟件危機(jī)的表現(xiàn)：

1、軟件需求的增長(zhǎng)得不到滿足

2、軟件開發(fā)成本和進(jìn)度無法控制

3、軟件質(zhì)量難以保證

4、軟件不可維護(hù)或維護(hù)程度非常低

5、軟件成本不斷提高

6、軟件開發(fā)生產(chǎn)效率的提高趕不上硬件的發(fā)展和應(yīng)用需求的增長(zhǎng)

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

來定義、開發(fā)、維護(hù)軟件的一門學(xué)科。

軟件工程的目標(biāo)：

付出較低的開發(fā)成本；達(dá)到要求的軟件功能；取得較好的軟件性能；開發(fā)的

軟件易于移植；需要較低的維護(hù)費(fèi)用；能按時(shí)完成開發(fā)任務(wù)，及時(shí)交付使用；

開發(fā)的軟件可靠性高。

?軟件工程研究的主要內(nèi)容是軟件開發(fā)技術(shù)和軟件開發(fā)管理兩個(gè)方面。

軟件生存周期：是指一個(gè)軟件從提出開發(fā)要求開始直到該軟件報(bào)廢(停止運(yùn)

行)為止的整個(gè)時(shí)期。

軟件生存周期模型：是描述軟件開發(fā)過程中各種活動(dòng)如何執(zhí)行的模型。

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

于知識(shí)的模型

瀑布模型是將軟件生存周期各個(gè)活動(dòng)規(guī)定為依線性順序連接的若干階段的模型。

主要包括問題定義及可行性分析、項(xiàng)目開發(fā)計(jì)劃、需求分析、概要設(shè)計(jì)、詳細(xì)設(shè)

計(jì)、編碼、測(cè)試和維護(hù)幾個(gè)階段。

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

A、程序就是軟件B、軟件開發(fā)不受計(jì)算機(jī)系統(tǒng)的限制

C、軟件既是邏輯實(shí)體，又是物理實(shí)體D、軟件是程序、數(shù)據(jù)

與相關(guān)文檔的集合

二、軟件可行性研究與項(xiàng)目開發(fā)計(jì)劃：

軟件可行性研究的目的是用最小的代價(jià)在盡可能短的時(shí)間內(nèi)確定該軟件項(xiàng)

目是否能夠開發(fā)，是否值得去開發(fā)。

可行性研究的任務(wù)：

A、技術(shù)可行性

B、經(jīng)濟(jì)可行性

C、社會(huì)可行性（法律可行性）

可行性研究的具體步驟：

1、確定項(xiàng)目規(guī)模和目標(biāo)

2、研究正在運(yùn)行的系統(tǒng)

3、建立新系統(tǒng)的高層邏輯模型

4、導(dǎo)出和評(píng)價(jià)各種方案

5、推薦可行的方案

6、編寫可行性研究報(bào)告

三、軟件需求分析：

需求分析是指開發(fā)人員要準(zhǔn)確理解用戶的要求，進(jìn)行細(xì)致的調(diào)查分析，將用

戶非形式的需求陳述轉(zhuǎn)化為完整的需求定義，再由需求定義轉(zhuǎn)換到相應(yīng)的形

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

?需求分析的基本任務(wù)：

1、問題識(shí)別

A、功能需求

B、性能需求

C、環(huán)境需求

n田戶里面熏親

2、A析與綜合，導(dǎo)出軟件的邏輯模型

3、編寫文檔（需求規(guī)格說明書）

?需求分析的方法：

1、結(jié)構(gòu)化分析（StructuredAnalysis）：是面向數(shù)據(jù)流進(jìn)行需求分析的方法。

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

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

方式描繪數(shù)據(jù)在系統(tǒng)中流動(dòng)和處理的過程。

B、數(shù)據(jù)字典（DD）：用以定義數(shù)據(jù)流圖中的各個(gè)成分的具體含義，為系統(tǒng)的分析、

設(shè)計(jì)及維護(hù)提供了有關(guān)元素的一致的定義和詳細(xì)的描述。

C、描述加工邏輯的結(jié)構(gòu)化語言、判定表、判定樹

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

是一種用于進(jìn)行復(fù)雜系統(tǒng)分析和設(shè)計(jì)的方法，是在結(jié)構(gòu)化分析和設(shè)計(jì)技術(shù)的

基礎(chǔ)上提出來的。

3、面向?qū)ο蠓治龇椒ǎ∣OP）：

將客觀世界的事物抽象為對(duì)象，通過屬性和方法描述對(duì)象的狀態(tài)和行為，具

有繼承、封裝和多態(tài)性等特征。

例：軟件開發(fā)的結(jié)構(gòu)化分析方法中，常用的描述軟件功能需求的工具是（）

A、業(yè)務(wù)流程圖、處理說明B、軟件流程圖、模塊說明

C、數(shù)據(jù)流程圖、數(shù)據(jù)字典D、系統(tǒng)流程圖、程序編碼

四、軟件概要設(shè)計(jì)：

將軟件需求轉(zhuǎn)換為軟件表示的過程。

?軟件概要設(shè)計(jì)的基本任務(wù)：

1、設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu)

2、數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫設(shè)計(jì)（概要設(shè)計(jì)、邏輯設(shè)計(jì)、物理設(shè)計(jì)）：

3、編寫概要設(shè)計(jì)文檔：

4、評(píng)審：

軟件設(shè)計(jì)的方法：

模塊化：模塊在程序中是數(shù)據(jù)說明、可執(zhí)行語句等程序?qū)ο蟮募希蛘呤?/p>

單獨(dú)命名和編址的元素，如高級(jí)語言中的過程、函數(shù)、子程序等。

?模塊獨(dú)立性指每個(gè)模塊只完成系統(tǒng)要求的獨(dú)立的子功能，并且與其他模塊的

聯(lián)系最少且接口簡(jiǎn)單。其度量標(biāo)準(zhǔn)是：耦合性和內(nèi)聚性

耦合性也稱塊間聯(lián)系，指軟件系統(tǒng)結(jié)構(gòu)中各模塊間相互聯(lián)系緊密程度的一種

度量。模塊之間聯(lián)系越緊密，其耦合性就越強(qiáng)，模塊的獨(dú)立性則越差。

?內(nèi)聚性也稱塊內(nèi)聯(lián)系，指模塊功能強(qiáng)度的度量，即一個(gè)模塊內(nèi)部各個(gè)元素（語

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

將軟件系統(tǒng)劃分模塊時(shí)，盡量做到高內(nèi)聚低耦合。

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

A、模塊的內(nèi)聚程序要盡量高，且各模塊間的耦合程序要盡量強(qiáng)

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

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

D、模塊的內(nèi)聚程序要盡量低，且各模塊間的耦合程序要盡量強(qiáng)

五、軟件詳細(xì)設(shè)計(jì)：

主要確定每個(gè)模塊具體執(zhí)行過程

軟件詳細(xì)設(shè)計(jì)的基本任務(wù)：

1、為每個(gè)模塊進(jìn)行詳細(xì)的算法設(shè)計(jì)：

2、為模塊內(nèi)的數(shù)據(jù)結(jié)構(gòu)進(jìn)行設(shè)計(jì)：

3、對(duì)數(shù)據(jù)庫進(jìn)行物理設(shè)計(jì)：

4、輸入、輸出格式設(shè)計(jì)

5、編寫詳細(xì)設(shè)計(jì)說明書：

6、評(píng)審：

詳細(xì)設(shè)計(jì)常用三種工具：

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

表格（判定表）、

語言（過程設(shè)計(jì)語言，乂稱為偽碼）

六、軟件編碼：

主要是將詳細(xì)設(shè)計(jì)得到的處理過程描述轉(zhuǎn)換為基于某種計(jì)算機(jī)語言的程序

常用的計(jì)算機(jī)語言：Pascal,C、C++、Java等

七、軟件測(cè)試：

軟件測(cè)試代表了需求分析、設(shè)計(jì)、編碼的最終復(fù)審。軟件測(cè)試貫穿于軟件開

發(fā)的全過程。

?軟件測(cè)試的目的：

1、軟件測(cè)試是為了盡可能多地發(fā)現(xiàn)程序中的錯(cuò)誤而執(zhí)行程序的過程。

2、一個(gè)好的測(cè)試用例能夠發(fā)現(xiàn)至今尚未發(fā)現(xiàn)的錯(cuò)誤。

3、一個(gè)成功的測(cè)試是發(fā)現(xiàn)了至今尚未發(fā)現(xiàn)的錯(cuò)誤的測(cè)試。

軟件測(cè)試的原則：

1、測(cè)試用例應(yīng)由輸入數(shù)據(jù)和預(yù)期的輸出數(shù)據(jù)兩部分組成。

2、測(cè)試用例不僅選用合理的輸入數(shù)據(jù)，還要選擇不合理的輸入數(shù)據(jù)

3、除了檢查程序是否做了它應(yīng)該做的事

4、應(yīng)制定測(cè)試計(jì)劃并嚴(yán)格執(zhí)行，排除隨意性

5、長(zhǎng)期保留測(cè)試用例

6、對(duì)發(fā)現(xiàn)錯(cuò)誤較多的程序段，應(yīng)進(jìn)行更深入的測(cè)試

7、程序員避免測(cè)試自己的程序

軟件測(cè)試方法：

1、靜態(tài)測(cè)試：

是指被測(cè)試程序不在機(jī)器上運(yùn)行，而是采用人工檢測(cè)和計(jì)算機(jī)輔助靜態(tài)分

析的手段對(duì)程序進(jìn)行檢測(cè)。

2、動(dòng)態(tài)測(cè)試：是指通過運(yùn)行程序發(fā)現(xiàn)錯(cuò)誤

A、黑盒測(cè)試法（功能測(cè)試）：

主要對(duì)軟件的接口進(jìn)行測(cè)試，依據(jù)需求規(guī)格說明書，檢查程序是否滿足功能

要求。常用的技術(shù)是等價(jià)類劃分法、邊界值分析法、錯(cuò)誤推測(cè)法、因果圖法、綜

合策略法

B、白盒測(cè)試法（結(jié)構(gòu)測(cè)試）：

主要測(cè)試程序的內(nèi)部結(jié)構(gòu)和處理過程。常用的技術(shù)是語句覆蓋、條件覆蓋、

路徑覆蓋、判定覆蓋等

軟件測(cè)試的實(shí)施：

1、單元測(cè)試：

單元測(cè)試是對(duì)軟件設(shè)計(jì)的最小單位——模塊（程序單元）進(jìn)行正確性檢驗(yàn)測(cè)

試，主要針對(duì)模塊的以下五個(gè)基本特征進(jìn)行測(cè)試：

A、模塊接口

B、局部數(shù)據(jù)結(jié)構(gòu)：

C、重要的執(zhí)行路徑：

D、錯(cuò)誤處理測(cè)試：

E、邊界條件：

2、集成測(cè)試：

集成測(cè)試是指在單元測(cè)試的基礎(chǔ)上，將所有模塊按照設(shè)計(jì)要求組裝成一個(gè)完

整的系統(tǒng)進(jìn)行的測(cè)試，故也稱組裝測(cè)試或聯(lián)合測(cè)試。

主要方法有兩種：

非漸增式測(cè)試：首先對(duì)每個(gè)模塊分別進(jìn)行單元測(cè)試，然后再把所有的模塊按

設(shè)計(jì)要求組裝在一起進(jìn)行測(cè)試。

漸增式測(cè)試：逐個(gè)把未經(jīng)過測(cè)試的模塊組裝到已經(jīng)過測(cè)試的模塊上去，進(jìn)行

集成測(cè)試,每加入一個(gè)新模塊進(jìn)行一次集成測(cè)試,重復(fù)此過程直至程序組裝完畢。

3、確認(rèn)測(cè)試：

確認(rèn)測(cè)試乂稱有效性測(cè)試，它的任務(wù)是檢查軟件的功能與性能是否與需求規(guī)

格說明書中確定的指標(biāo)相符合，因而需求規(guī)格說明是確認(rèn)測(cè)試的基礎(chǔ)。

4、系統(tǒng)測(cè)試：

系統(tǒng)測(cè)試是通過測(cè)試確認(rèn)的軟件作為整個(gè)計(jì)算機(jī)系統(tǒng)的一個(gè)元素，與計(jì)算機(jī)

硬件、外設(shè)、支撐軟件、數(shù)據(jù)和人員等其他系統(tǒng)元素組合在一起，在實(shí)際運(yùn)行環(huán)

境下對(duì)計(jì)算機(jī)系統(tǒng)進(jìn)行一系列的集成測(cè)試和確認(rèn)測(cè)試。

程序調(diào)試：

調(diào)試是在進(jìn)行了成功的測(cè)試之后才開始的工作，目的是確定錯(cuò)誤的原因和位

置，并改正錯(cuò)誤，又稱為糾錯(cuò)。

例：軟件測(cè)試的目的是（）

A、證明軟件的正確性B、找出軟件系統(tǒng)中存在的所有錯(cuò)

誤

C、盡可能多地發(fā)現(xiàn)軟件系統(tǒng)中的錯(cuò)誤D、證明軟件系統(tǒng)中存在錯(cuò)誤

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

法主要是

用于測(cè)試（）

A、結(jié)構(gòu)合理性B、軟件外部功能C、程序正確性D、程序內(nèi)部邏輯

八、軟件維護(hù)：

軟件投入使用后進(jìn)行的階段，是軟件生存周期中時(shí)間最長(zhǎng)的一個(gè)階段，所花

費(fèi)的精力和費(fèi)用也是最多的一個(gè)階段。主要是因?yàn)椋弘[含的錯(cuò)誤要修改；新增的

功能要加入進(jìn)去；環(huán)境的變化對(duì)程序進(jìn)行變動(dòng)等。

軟件維護(hù)的內(nèi)容有四類：

1、校正性維護(hù)：

為了識(shí)別和糾正錯(cuò)誤，修改軟件性能上的缺陷，其占整個(gè)維護(hù)工作的21%

2、適應(yīng)性維護(hù)：

為了使應(yīng)用軟件適應(yīng)環(huán)境（硬件、系統(tǒng)軟件、數(shù)據(jù)）的變化而修改軟件的過程

稱為適應(yīng)性維護(hù)，其占整個(gè)維護(hù)工作的25%

3、完善性維護(hù)：

增加軟件功能、增強(qiáng)軟件性能、提高軟件運(yùn)行效率而進(jìn)行的維護(hù)活動(dòng)稱為完

善性維護(hù)，其占整個(gè)維護(hù)工作的50%

4、預(yù)防性維護(hù)：

為了提高軟件的可維護(hù)性和可靠性而對(duì)軟件進(jìn)行的修改稱為預(yù)防性維護(hù)，其

占整個(gè)維護(hù)工作的4%

例：軟件維護(hù)是指（）

A、維護(hù)軟件正常運(yùn)行B、軟件的配置更新

C、對(duì)軟件的改進(jìn)、適應(yīng)和完善D、軟件開發(fā)期的一個(gè)階段

軟件生命周期中所花費(fèi)用最多的階段是（）

A、詳細(xì)設(shè)計(jì)B、軟件編碼C、軟件測(cè)試D、軟件維護(hù)

四.數(shù)據(jù)庫原理基礎(chǔ)

一、基本概念:

數(shù)據(jù)處理：是指將數(shù)據(jù)轉(zhuǎn)換成信息的過程

數(shù)據(jù)管理是指對(duì)數(shù)據(jù)的組織、分類、編碼、存儲(chǔ)、檢索和維護(hù)提供操作手段

其經(jīng)歷了以下階段：

1、人工管理

2、文件系統(tǒng)

3、數(shù)據(jù)庫系統(tǒng)

4、分布式數(shù)據(jù)庫系統(tǒng)階段

5、面向?qū)ο蟮臄?shù)據(jù)庫系統(tǒng)階段

數(shù)據(jù)庫(Database)：是指存儲(chǔ)在計(jì)算機(jī)存儲(chǔ)設(shè)備上的結(jié)構(gòu)化的相關(guān)數(shù)據(jù)的集

合，不僅包括數(shù)據(jù)本身，還包括事物之間的聯(lián)系。

數(shù)據(jù)庫應(yīng)用系統(tǒng)(DBAS)：是指系統(tǒng)開發(fā)人員利用數(shù)據(jù)庫系統(tǒng)資源開發(fā)出來

的，面向某一類實(shí)際應(yīng)用的應(yīng)用軟件系統(tǒng)。

數(shù)據(jù)庫管理系統(tǒng)(DBMS)：對(duì)數(shù)據(jù)庫的建立、使用和維護(hù)進(jìn)行管理和配置的軟

件系統(tǒng)。是數(shù)據(jù)庫系統(tǒng)的核心

數(shù)據(jù)庫系統(tǒng)(DBS):由硬件系統(tǒng)、數(shù)據(jù)庫集合、數(shù)據(jù)庫管理系統(tǒng)及相關(guān)軟件、

數(shù)據(jù)庫管理員和用戶組成。

數(shù)據(jù)庫系統(tǒng)的特點(diǎn)：

實(shí)現(xiàn)數(shù)據(jù)共享、減少數(shù)據(jù)冗余

采用特定的數(shù)據(jù)模型

具有較高的數(shù)據(jù)獨(dú)立性

統(tǒng)一的數(shù)據(jù)控制功能

實(shí)體：客觀存在并且可以相互區(qū)別的事物稱為實(shí)體。

實(shí)體的屬性：實(shí)體所具有的物性稱為實(shí)體的屬性。

?實(shí)體集：同類型的實(shí)體的集合稱為實(shí)體集。

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

例：數(shù)據(jù)庫管理系統(tǒng)能實(shí)現(xiàn)對(duì)數(shù)據(jù)庫中數(shù)據(jù)的查詢、插入、修改和刪除，這類功

能稱為()

A、數(shù)據(jù)定義功能B、數(shù)據(jù)管理功能C、數(shù)據(jù)操縱功能D、數(shù)據(jù)控制功能

?聯(lián)系：實(shí)體之間的對(duì)應(yīng)關(guān)系。

聯(lián)系的類型：

1、一對(duì)一聯(lián)系：表現(xiàn)為主表中的每一條記錄只與相關(guān)表中的一條記錄相關(guān)

聯(lián)。

例如：班級(jí)與班長(zhǎng)，學(xué)校與校長(zhǎng)

2、一對(duì)多聯(lián)系：表現(xiàn)為主表中的每一條記錄與相關(guān)表中的多條記錄相關(guān)聯(lián)。

例如：班級(jí)與學(xué)生，部門與職工

3、多對(duì)多聯(lián)系：表現(xiàn)為一個(gè)表中的多個(gè)記錄在相關(guān)表中同樣有多個(gè)記錄相

關(guān)聯(lián)。

例如：學(xué)生與課程，工程項(xiàng)目與零件

數(shù)據(jù)模型：不僅反映事物本身，還用來表示實(shí)體及實(shí)體之間聯(lián)系的方法。

1、層次模型：用樹形結(jié)構(gòu)表示實(shí)體及其之間聯(lián)系的模型稱為層次模型。

2、網(wǎng)狀模型：用網(wǎng)狀結(jié)構(gòu)表示實(shí)體及其之間聯(lián)系的模型稱為網(wǎng)狀模型。

3、關(guān)系模型：用二維表結(jié)構(gòu)來表示實(shí)體及實(shí)體之間的聯(lián)系的模型稱為關(guān)系

模型。

一個(gè)二維表稱為一個(gè)關(guān)系，在VFP稱為數(shù)據(jù)表。一個(gè)關(guān)系不僅表示實(shí)體本

身還表示實(shí)體之間的聯(lián)系。

例：用樹形結(jié)構(gòu)表示實(shí)體之間聯(lián)系的模型是()

A、關(guān)系模型B、網(wǎng)狀模型C、層次模型D、以上三個(gè)都是

二、關(guān)系數(shù)據(jù)庫：

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

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

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

?關(guān)鍵字(PrimalKey)：其值能夠惟一標(biāo)識(shí)一個(gè)元組的屬性或?qū)傩缘慕M合。

注：關(guān)鍵字不能出現(xiàn)空值或重復(fù)值

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

選關(guān)鍵字，而是另外一個(gè)表的主關(guān)鍵字或侯選關(guān)鍵字，這個(gè)字段在本表中稱

為外部關(guān)鍵字。

?關(guān)系性質(zhì)：

二維表中元組的個(gè)數(shù)是有限的——元組個(gè)數(shù)有限性

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

二維表中元組的次序可以任意交換——元組的次序無關(guān)性

二維表中元組的分量是不可分割的基本數(shù)據(jù)項(xiàng)——元組分量的原子性

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

二維表中屬性與次序無關(guān)，可任意交換——屬性的次序無關(guān)性

例：關(guān)系數(shù)據(jù)模型中表示實(shí)體和實(shí)體間的聯(lián)系的結(jié)構(gòu)是()

A、樹型B、網(wǎng)狀C、二維表D、對(duì)象

三、關(guān)系運(yùn)算：

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

關(guān)系模式)

差(Difference)：若有兩個(gè)相同結(jié)構(gòu)的關(guān)系R和S,R差S的結(jié)果屬于R但

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

?交(Intersection)：若有兩個(gè)相同的結(jié)構(gòu)關(guān)系R和S,交的結(jié)果為兩個(gè)關(guān)系

共同的元組。

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

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

聯(lián)接(Join)：是關(guān)系的橫向結(jié)合，關(guān)系模式改變了，是多個(gè)關(guān)系的關(guān)系模

式的組合。聯(lián)接的結(jié)果是多個(gè)關(guān)系中滿足條件的元組。

2002年9月全國計(jì)算機(jī)考試VF二級(jí)考試筆試試題

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

下列各題A)、B)、C)、D)四個(gè)選項(xiàng)中，是有一個(gè)選項(xiàng)是正確的。請(qǐng)將正確

選項(xiàng)添涂在答題卡相應(yīng)的位置上，答在試卷上不得分。

(1)在寫列四個(gè)選項(xiàng)中，不屬于基本關(guān)系運(yùn)算的是

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

(2)如果一個(gè)班只能有一個(gè)班長(zhǎng)，而且一個(gè)班長(zhǎng)不能同時(shí)擔(dān)任其他班的班長(zhǎng)，

班級(jí)和班長(zhǎng)兩個(gè)實(shí)體之間的關(guān)系屬于

A)?對(duì)一聯(lián)系B)一對(duì)二聯(lián)系C)多對(duì)多聯(lián)系D)一對(duì)多聯(lián)系

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

A)層次數(shù)據(jù)模型B)關(guān)系數(shù)據(jù)模型C)網(wǎng)狀數(shù)據(jù)模型D)樹狀數(shù)據(jù)模型

(4)VF的命令窗口中鍵如CREATEDATA命令以后，屏幕會(huì)出現(xiàn)一個(gè)創(chuàng)建對(duì)話框,

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

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

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

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

單選鈕，再單擊“向?qū)А泵畎粹o

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

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

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

鈕，再單擊“向?qū)А泵畎粹o

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

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

A)表單文件B)數(shù)據(jù)庫表文件C)數(shù)據(jù)庫文件D)項(xiàng)目文件

(7)建設(shè)已經(jīng)生成了名為mymenu的菜單問，執(zhí)行該菜單文件的命令是

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

下面有關(guān)索引的描述正確的是

A)簡(jiǎn)化里索引以后。原來的數(shù)據(jù)庫表文件中記錄的物理順序?qū)⒈桓淖?/p>

B)索引與數(shù)據(jù)庫表的數(shù)據(jù)存儲(chǔ)在一個(gè)文件中

C)創(chuàng)建索引是創(chuàng)建一個(gè)指向數(shù)據(jù)庫表文件記錄的指針構(gòu)成的文件

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

(9)若建立索引的字段值不允許重復(fù)，并且一個(gè)表中只能創(chuàng)建一個(gè)。它應(yīng)該是

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

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

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

(11)一數(shù)據(jù)庫名為student,要想打開該數(shù)據(jù)庫，應(yīng)使用的命令

A)OPENstudentB)OPENDATAstudentC)USEDATAstudentD)USEstudent

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

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

(13)在下面的數(shù)據(jù)類型中默認(rèn)為.F.的是

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

(14)在下面有關(guān)HAVING子句描述錯(cuò)誤的是

A)HAVING子句必須與GROUPBY子句同時(shí)使用，不能單獨(dú)使用

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

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

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

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

當(dāng)前盤當(dāng)前目錄下有數(shù)據(jù)庫db_stock,其中有數(shù)據(jù)庫表stock,dbf,該數(shù)據(jù)庫表

的內(nèi)容是：股票代碼股票名稱單價(jià)交易所0600600青島啤酒7.48上海

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

房產(chǎn)12.76上海0600604二紡機(jī)9.96上海0600605輕工機(jī)械14.59上海

0000001深發(fā)展7.48深圳0000002深萬科12.50深圳

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

價(jià)

A)系統(tǒng)將會(huì)提示出錯(cuò)信息

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

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

D)不會(huì)生成排序文件，只能在屏幕上顯示一個(gè)按“單價(jià)”排序的結(jié)果

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

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

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

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

AND15.20與該語句等價(jià)的是

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

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

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

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

(18)如果在建立數(shù)據(jù)庫表stock,dbf時(shí)，將單價(jià)字段的字段有效性規(guī)則設(shè)為“單

價(jià)>0"，通過該設(shè)置，能保證數(shù)據(jù)的

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

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

A)DROPstockB)DELETETABLEstockC)DROPTABLEstockD)DELETEstock

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

句后

A)a[l]的內(nèi)容為15.2B)a[l]的內(nèi)容為6

C)a[0]的內(nèi)容為15.2D)a[0]的內(nèi)容為6

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

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

的“均價(jià)”字段的內(nèi)容是

A)ALTERTABLEstock股票名稱WITHc(10)

B)ALTERTABLEstock股票名稱c(10)

C)ALTERTABLEstockALTRE股票名稱c(10)

D)ALTERTABLEstock股票名稱c(10)

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

交易所=“深圳”0執(zhí)行該語句后產(chǎn)生的視圖包含的記錄數(shù)個(gè)是

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

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

單價(jià)FROMstockO執(zhí)行該語句后產(chǎn)生的視函含有的字段名是

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

價(jià)、交易所(25)下面有關(guān)對(duì)視圖的描述正確的是

A)可以使用MODIFYSTRUCTURE命令修改視圖的結(jié)構(gòu)

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

C)視圖是對(duì)表的復(fù)制產(chǎn)生的

D)使用對(duì)視圖進(jìn)行查詢時(shí)必須事先打開該視圖所在的數(shù)據(jù)庫

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

=(SELECTmin(單價(jià))FROMstock)INTODBFstock_x0表stock_x中的記錄個(gè)

數(shù)是

A)1B)203D)4

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

A）SELECT交易所，avg（單價(jià)）FROMstockGROUPBY單價(jià)

B）SELECT交易所，avg（單價(jià)）FROMstockORDERBY單價(jià)

C）SELECT交易所，avg（單價(jià)）FROMstockORDERBY交易所

D）SELECT交易所,avg（單價(jià)）FROMstockGROUPBY交易所

（28）視圖設(shè)計(jì)器中含有的、但查詢?cè)O(shè)計(jì)器卻沒有的選項(xiàng)卡是

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

（29）下面關(guān)于查詢描述正確的是

A）可以使用CREATEVIEW打開查詢?cè)O(shè)計(jì)器

B）使用查詢?cè)O(shè)計(jì)器可以生成所有的SQP查詢語句

C）使用查詢?cè)O(shè)計(jì)器生成的SQP語句存盤后將存放在擴(kuò)展名為QPR的文件中

D）使用DO語句執(zhí)行查詢時(shí)，可以不帶擴(kuò)展名

（30）使用報(bào)表向?qū)Фx報(bào)表時(shí)，定義報(bào)表布局的選項(xiàng)是

A）列數(shù)、方向、字段布局B）列數(shù)、行數(shù)、字段布局

C）行數(shù)、方向、字段布局D）列數(shù)、行數(shù)、方向

（31）能夠?qū)⒈韱蔚腣isible屬性設(shè)置為.T.,并使表單成為活動(dòng)對(duì)象的方法是

A）HideB）ShowC）ReleaseD）SetFocus

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

A）SelLength屬性的設(shè)置可以小于0

B）當(dāng)ScrollBars的屬性值為0時(shí)，編輯框內(nèi)包含水平滾動(dòng)條

C）SeText屬性在做界面設(shè)計(jì)時(shí)不可用，在運(yùn)動(dòng)時(shí)可讀寫

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

（33）下面對(duì)控件的描述正確的是

A）用戶可以在組合框中進(jìn)行多重選擇

B）用戶可以在列表框中進(jìn)行多重選擇

C）用戶可以在一個(gè)選項(xiàng)組中多個(gè)選項(xiàng)按鈕

D）用戶對(duì)一個(gè)表單內(nèi)的一組復(fù)選框中只能選中其中一個(gè)

（34）確定列表框內(nèi)的某個(gè)條目是否被選定應(yīng)使用的屬性是0A）value

B）ColumnCountC）ListCountD）SelectedO（35）沒有關(guān)系RI和R2,經(jīng)過關(guān)系

運(yùn)算得到結(jié)果是S,則S是

A）一個(gè)關(guān)系B）一個(gè)表單C）一個(gè)數(shù)據(jù)庫D）一個(gè)數(shù)組

二、填空題（每空2分，共30分）請(qǐng)將答案分別寫在答題卡中的序號(hào)為［1］——［5］

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

（1）VisualFoxPro6.0是一個(gè)［1］位的數(shù)據(jù)棵管理系統(tǒng)。

（2）在連接運(yùn)算中，［2］連接是去掉重復(fù)屬性的等值連接。

（3）項(xiàng)目管理器的［3］選項(xiàng)卡用于顯示和管理數(shù)據(jù)庫、自由表和查詢等。

（4）自由表的擴(kuò)展名是［4］。

(5)LEFT(“123456789"，LEN(“數(shù)據(jù)庫”))的計(jì)算結(jié)果是［5］。

（6）同一個(gè)表的多個(gè)索引可以創(chuàng)建在一個(gè)索引文件中，索引文件名與相關(guān)的表

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

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

的文字的屬性是［9］

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

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

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

1500.0001011020004張?jiān)滦轮v師301500.00030111020005李明玉教授

342000.0001011020006孫民山教授472100.0002011020007錢無名教

授492200.00030“學(xué)院”表0系號(hào)系名001英語002會(huì)計(jì)003工商管理

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

系名）［113（“04”，“計(jì)算機(jī)”）

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

資）FROM教師OWHERE系號(hào)IN（SELECT系號(hào)FROM［13］WHERE系名=“工

商管理”）

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

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

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

DABACCBCADBBCBACABCABCBBDADDCABCBDA032自然數(shù)據(jù).DBF123456.CDX

結(jié)構(gòu)復(fù)合索引valueCAPTIONINTOvalueSSUM學(xué)院UPDATEWHERE

2003年4月全國計(jì)算機(jī)等級(jí)考試VF二級(jí)筆試試題

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

下列各題A）、B）、C）、D）四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)是正確的，請(qǐng)將正確選項(xiàng)

涂寫在大題卡相應(yīng)位置上，答在試卷上不得分。

（1）VisualFoxProDBMS是

A）操作系統(tǒng)的一部分B）操作系統(tǒng)支持下的系統(tǒng)軟件

C）一種編譯程序D）一種操作系統(tǒng)

（2）VisualFoxProDBMS基于的數(shù)據(jù)模型是

A）層次型B）關(guān)系型C）網(wǎng)狀型D）混合型

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

名職員，

則部門與職員實(shí)體之間的聯(lián)系類型是

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

(4)在VisualFoxPro中，調(diào)用表設(shè)計(jì)器建立數(shù)據(jù)庫表STUDENT.DBF的命令是

A)MODIFYSTRUCTURESTUDENTB)MODIFYCOMMANDSTUDENT

C)REATESTUDENTD)CREATETABLESTUDENT

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

A)自由表和數(shù)據(jù)庫表是完全相同的B)自由表不能建立字段級(jí)規(guī)則和約

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

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

這種約束屬于

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

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

A)DOT1B)RUNFORM1T1C)DOFORMT1D)DOFROMT1

⑻使用SQL語句進(jìn)行分組檢索時(shí)，為了去掉不滿足條件的分組，應(yīng)當(dāng)

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

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

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

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

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

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

系統(tǒng)自動(dòng)給出，它們分別為：

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