全國計算機等級考試

二級公共基礎知識約12課時青島工學院學習方法邏輯推理運算必須理解概念性、理論性知識點要加強記憶適當記憶一些名詞與所學的VF程序設計知識結合起來，以增加對知識的理解能力做大量習題青島工學院一、數據結構與算法考點提示：1.算法的基本概念；算法復雜度的概念和意義（時間復雜度與空間復雜度）。2.數據結構的定義；數據的邏輯結構與存儲結構；數據結構的圖形表示；線性結構與非線性結構的概念。3.線性表的定義；線性表的順序存儲結構及其插入與刪除運算。4.棧和隊列的定義；棧和隊列的順序存儲結構及其基本運算。5.線性單鏈表、雙向鏈表與循環鏈表的結構及其基本運算。6.樹的基本概念；二叉樹的定義及其存儲結構；二叉樹的前序、中序和后序遍歷。7.順序查找與二分法查找算法；基本排序算法（交換類排序，選擇類排序，插入類排序）。青島工學院本章考點點評及考核情況考點點評：該部分屬于重點考核知識點，在此7個考點中，經常會考到的知識點是1、4、6點，特別是二叉樹的遍歷，基本上每年必考的內容。分值情況：本部分內容所占分值在3-5分。青島工學院1.1算法算法：

是指解題方案的準確而完整的描述。算法不等于程序，也不等于計算方法；算法是解題思路，而程序是解題思路在其編譯環境中的具體描述。算法的特征：（1）可行性：在具體環境中可執行和正確與否（2）確定性：每一步必須有明確的定義（3）有窮性：在有限步驟（時間）內執行完畢（4）擁有足夠的情報：初始數據或初始狀態必須要充足且正確。青島工學院算法的基本要素： 一是對數據對象的運算和操作（四類） 二是算法的控制結構（各操作之間的執行順序）。基本運算和操作包括： 算術運算、邏輯運算、關系運算、數據傳輸。算法的控制結構：

順序、選擇、循環。算法設計的基本方法： 列舉法、歸納法、遞推、遞歸、減半遞推技術、回溯法。青島工學院算法復雜度(包括)：

算法時間復雜度和算法空間復雜度。算法時間復雜度： 是指執行算法所需要的計算工作量（運算的執行次數）。衡量算法時間復雜度的主要因素：

一方面依賴于問題的規模，（如N×N矩陣乘法運算，f(n)=O(n3)）另一方面，某些情況下還和問題的輸入數據集有關（如冒泡排序）,此時用兩種方法分析：（1）平均性態：用基本運算次數的加權平均值來衡量----A(n)=（2）最壞情況復雜性：最大執行次數

----W(n)=青島工學院算法空間復雜度： 是指執行算法所占用的空間，包括算法程序所占用的空間、輸入的初始數據所占用的空間、算法執行過程中所需要的額外空間。算法設計的要求：（1）正確性 （2）可讀性 （3）健壯性（4）效率與低存儲量需求青島工學院例題算法的時間復雜度是指______。

A.執行算法程序所需要的時間

B.算法程序的長度

C.算法執行過程中所需要的基本運算次數

D.算法程序中的指令條數算法的空間復雜度是指______。

A.算法程序的長度

B.算法程序中的指令條數

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

D.執行算法所需要的空間下面敘述正確的是______。

A.算法的執行效率與數據的存儲結構無關

B.算法的空間復雜度是指算法程序中指令（或語句）的條數

C.算法的有窮性是指算法必須能在執行有限個步驟之后終止

D.以上三種描述都不對(C)(D)(C)青島工學院算法一般都可以用哪幾種控制結構組合而成______。

A.循環、分支、遞歸

B.順序、循環、嵌套

C.循環、遞歸、選擇

D.順序、選擇、循環在下列選項中，哪個不是一個算法一般應該具有的基本特征______。

A.確定性 B.可行性 C.無窮性 D.擁有足夠的情報算法的時間復雜度取決于_____。

A.問題的規模 B.待處理數據的初態

C.問題的難度 D.A和B在計算機中，算法是指______。

A.查詢方法

B.加工方法

C.解題方案的準確而完整的描述

D.排序方法(D)(C)(D)(C)青島工學院1.2數據結構的基本概念數據結構（兩個，注意區分）： 反映數據元素之間關系的表示。數據結構研究的三個方面：（1）各數據元素之間所固有的邏輯關系，即數據的邏輯結構；（2）各數據元素在計算機中的存儲關系，即數據的存儲結構（又叫物理結構）；（3）對各種數據結構進行的運算。數據的邏輯結構：（1）表示數據元素的信息；（2）表示各數據元素之間的前后件關系。 數據的邏輯結構是數據元素之間固有的，是與計算機硬件沒有關系的結構青島工學院數據邏輯結構的四種形式： 集合、線性結構、樹形結構、圖形結構數據存儲結構： 是指數據的邏輯結構在計算機存儲空間中的存放形式，也稱數據的物理結構。

數據的物理結構反映的是數據的存儲方法，這受到具體的物理存儲介質制約(與計算機硬件有關系)。數據存儲結構的三種形式：

順序、鏈接、索引。數據結構中的數據元素，其邏輯結構和存儲結構不一定相同。青島工學院按邏輯（前后件）關系的復雜程度，將數據的邏輯結構簡單分為線性結構和非線性結構：線性結構（什么是線性結構？線性結構有那幾個？）（線性表、線性鏈表、棧、隊列）：（1）有且只有一個根結點；（2）每一個結點最多有一個前件，也最多有一個后件。在一個線性結構中插入或刪除任何一個節點后還應該是線性結構。非線性結構：不滿足線性結構條件的數據結構。線性結構和非線性結構都可以是空數據結構，對于空數據結構的運算是按線性結構的規則來處理的，則屬于線性結構；否則屬于非線性結構。圖1.5線性結構特列青島工學院例題在數據結構中，與所使用的計算機無關的數據結構是_____。

A.邏輯

B.存儲

C.邏輯和存儲

D.物理在數據結構中，從邏輯上可以把數據結構分成______。

A.動態結構和靜態結構

B.緊湊結構和非緊湊結構

C.線性結構和非線性結構

D.內部結構和外部結構數據的存儲結構是指______。

A.數據所占的存儲空間量

B.數據的邏輯結構在計算機中的表示

C.數據在計算機中的順序存儲方式

D.存儲在外存中的數據(A)(C)(B)青島工學院1.3線性表及順序存儲結構線性表（是什么？是表？是線表？）：

線性表是最常用且最簡單的一種線性數據結構。簡言之，一個線性表是n個數據元素的有限序列。線性表有兩種存儲結構（順序存儲和鏈式存儲）如26個英文字母的字母表（A,B,C,D……,Z）是一個線性表，表中的數據元素是單個字母字符。數據元素的定義在不同情況下各不相同 在復雜線性表中，一個數據元素可以由若干個數據項（item）組成。在這種情況下，常把數據元素稱為記錄（record），含有大量記錄的線性表又稱文件（file）青島工學院姓名學號性別年齡班級健康狀況王曉林790631男18計1健康陳紅790632女20計1一般……每個學生的情況為一個記錄，它由姓名、學號、性別、年齡、班級和健康狀況等6個數據項組成青島工學院非空線性表的結構特征：（1）有且只有一個根結點a1，它無前件；（2）有且只有一個終端結點an，它無后件；（3）除根結點與終端結點外，其他所有結點有且只有一個前件，也有且只有一個后件。結點個數n稱為線性表的長度，當n=0時，稱為空表。青島工學院線性表的順序存儲結構(典型結構是數組存儲)： 指用一組地址連續的存儲單元依次存儲線性表的數據元素。線性表的順序存儲結構具有以下兩個基本特點：（1）線性表順序存儲結構中所有元素所占的存儲空間是連續的；（2）線性表順序存儲結構中各數據元素在存儲空間中是按邏輯順序依次存放的。ai的存儲地址為：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)為第一個元素的地址，k代表每個元素占的字節數。可以看出，順序存儲是一種隨機存取的存儲結構,鏈式存儲是一種順序存取的存儲結構。只要知道某元素地址，其他任何元素地址都可以計算出來青島工學院順序表的運算（時間復雜度）： 插入： 在平均情況下，要插入一個元素，需要移動表中一半的元素。 刪除： 在平均情況下，要刪除一個元素，需要移動表中一半的元素。

線性表順序存儲缺點：：線性表的順序存儲結構，插入和刪除元素時需大量移動元素，故不便于插入和刪除操作青島工學院例題對長度為N的線性表進行順序查找，在最壞情況下所需要的比較次數為______。

A.N+1 B.N C.(N+1)/2 D.N/2順序存儲方法是把邏輯上相鄰的結點存儲在物理位置______的存儲單元中。用數組表示線性的優點是（）A．便于插入和刪除操作 B．便于隨機存儲C．可以動態地分配存儲空間D．不需要占用一片相鄰的存儲單元(B)相鄰(B)青島工學院1.4棧和隊列（線性結構）棧：

是限定在一端進行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。 棧按照“先進后出”（FILO）或“后進先出”（LIFO）組織數據，棧具有記憶作用。用top表示棧頂位置，用bottom表示棧底。棧的基本運算：（1）插入元素稱為入棧運算；（2）刪除元素稱為退棧運算；（3）讀棧頂元素

還有初始化、置空、判斷棧是否為空或滿青島工學院隊列：

是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。Rear指針指向隊尾（最后一個元素），front指針指向隊頭（第一個元素的前面）。隊列是“先進先出”（FIFO）或“后進后出”（LILO）的線性表。隊列運算：（1）入隊運算：從隊尾插入一個元素；（2）退隊運算：從隊頭刪除一個元素。青島工學院例題下列關于棧的敘述中正確的是______。

A.在棧中只能插入數據

B.在棧中只能刪除數據

C.棧是先進先出的線性表

D.棧是先進后出的線性表棧和隊列的共同點是______。

A.都是先進后出

B.都是先進先出

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

D.沒有共同點棧底至棧頂依次存放元素A、B、C、D，在第五個元素E入棧前，棧中元素可以出棧，則出棧序列可能是______。

A.CABED

B.DBCEA

C.CDABE

D.DCBEA(D)(C)(D)青島工學院下列關于隊列的敘述中正確的是______。

A.在隊列中只能插入數據

B.在隊列中只能刪除數據

C.隊列是先進先出的線性表

D.隊列是先進后出的線性表下列不是棧的運算的是______。

A.刪除棧頂元素

B.刪除棧底元素

C.判斷棧是否為空

D.將棧置為空棧若進棧序列為1，2，3，4，進棧過程中可以出棧，則下列不可能的一個出棧序列是______。

A.1432 B.2341 C.3142 D.3421棧的基本運算有三種：入棧、退棧和______。在一個容量為15的循環隊列中，若頭指針front=6，尾指針rear=9，則該循環隊列中共有______個元素(C)(B)(C)讀棧(3)計算公式是：：（尾指針-頭指針+容量）%容量青島工學院下列關于線性表、棧和隊列的敘述，錯誤的是（）A．線性表是給定的n（n必須大于零）個元素組成的序列B．線性表允許在表的任何位置上進行插入和刪除操作C．棧只允許在一端進行插入和刪除操作D．隊列允許在一端進行插入在另一端進行刪除一個隊列的入隊序列是1，2，3，4，則隊列的輸出序列是（）A．4，3，2，1 B．1，2，3，4C．1，4，3，2 D．3，2，4，1設初始輸入序列為1，2，3，4，5，利用一個棧產生輸出序列，下列（）序列是不可能通過棧產生的。A．1，2，3，4，5 B．5，3，4，1，2C．4，3，2，1，5 D．3，4，5，2，1(A)(B)(B)青島工學院設棧S的初始狀態為空，6個元素入棧的順序為e1，e2，e3，e4，e5和e6。若出棧的順序是e2，e4，e3，e6，e5，e1，則棧S的容量至少應該是（）

A．6 B．4 C．3 D．2(C)青島工學院1.5線性鏈表

由于順序存儲有一些缺點，某些情況我們需采用鏈式存儲結構。鏈式結構中的每一個數據結點對應于一個存儲單元，這種存儲單元稱為存儲結點，簡稱結點。結點由兩部分組成：（1）用于存儲數據元素值，稱為數據域；（2）用于存放指針，稱為指針域，指向前一個或后一個結點。線性鏈表： 在定義的鏈表中，若只含有一個指針域來存放下一個元素的地址，稱單鏈表或線性鏈表。青島工學院在鏈式存儲結構中，存儲數據結構的存儲空間可以不連續，各數據結點的存儲順序與數據元素之間的邏輯關系可以不一致，而數據元素之間的邏輯關系是由指針域來確定的。鏈式存儲方式既可用于表示線性結構，也可用于表示非線性結構。 線性鏈表中，HEAD稱為頭指針，HEAD=NULL（或0）稱為空表。 單鏈表只有一個指針域，只能順指針向鏈尾掃描，為彌補這一缺點，可設置兩個指針，左指針（Llink）指向前件結點，右指針（Rlink）指向后件結點。這樣的線性鏈表稱為雙向鏈表。線性鏈表的基本運算：查找、插入、刪除。青島工學院查找：在線性鏈表中，即使知道被訪問結點的序號i，也不能像順序存儲那樣直接按序號i訪問結點，而只能從鏈表的head出發，順指針域next逐個往下搜索，直到找到第i個結點為止。因此，鏈表不是隨機存取結構,而是順序存取結構。插入：青島工學院例題下列敘述中正確的是______。

A.線性表是線性結構

B.棧與隊列是非線性結構

C.線性鏈表是非線性結構

D.二叉樹是線性結構線性表的順序存儲結構和線性表的鏈式存儲結構分別是______。

A.順序存取的存儲結構、順序存取的存儲結構

B.隨機存取的存儲結構、順序存取的存儲結構

C.隨機存取的存儲結構、隨機存取的存儲結構

D.任意存取的存儲結構、任意存取的存儲結構在循環鏈表中，增加頭結點的目的是______。

A.方便運算的實現

B.使單鏈表至少有一個結點

C.標識表結點中首結點的位置

D.說明單鏈表是線性表的鏈式存儲實現

(A)(B)(A)青島工學院用鏈表表示線性表的優點是______。

A.便于插入和刪除操作

B.數據元素的物理順序與邏輯順序相同

C.花費的存儲空間較順序存儲少

D.便于隨機存取鏈不具備的特點是______。

A.可以隨機訪問任意一個節點

B.插入和刪除不需要移動任何元素

C.不必事先估計存儲空間

D.所需空間與其長度成正比對線性表，下列情況下應當采用鏈表表示的是______。

A.經常需要隨機的存取元素

B.經常需要進行插入和刪除操作

C.表中元素需要占據一片連續空間

D.表中元素個數不變(A)(A)(B)青島工學院如果最常用的操作是取第i個結點及其前驅，最省時間的存儲方式是______。

A.單鏈表 B.雙向鏈表 C.單循環鏈表D.順序表與單鏈表相比，雙向鏈表的優點之一是______。

A.插入、刪除操作更加簡單

B.可以隨機訪問

C.可以省略表頭指針和表尾指針

D.順序訪問相鄰結點更加靈活若已知一個棧的進棧序列是1，2，3。。。N，其輸出序列是p1,p2……pn，若p1=n，則pi為______。

A.i B.n-i C.n-i+1D.不確定可以用帶表頭結點的鏈表表示線性表，也可以用不帶表頭結點的鏈表表示線性表，前者最主要的好處是（）A．可以加快對表的遍歷 B．使空表和非空表的處理統一C．節省存儲空間 D．可以提高存取表元素的速度(D)(D)(C)(B)青島工學院1.6樹與二叉樹樹是一種簡單的非線性結構，元素之間具有明顯的層次特性。在樹結構中，每一個結點只有一個前件，稱為父結點，沒有前件的結點只有一個，稱為樹的根結點，簡稱樹的根。每一個結點可以有多個后件，稱為該結點的子結點。沒有后件的結點稱為葉子結點。在樹結構中，一個結點所擁有的后件的個數稱為該結點的度，所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。青島工學院樹的性質：（1）樹所有結點的度之和比結點總數小1（2）樹所有結點的度之和與邊的條數之和相等青島工學院二叉樹的特點：（1）非空二叉樹只有一個根結點；（2）每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。AΦ空樹只有根節點只有左子樹只有右子樹兩棵子樹二叉樹的五種形態：青島工學院二叉樹的基本性質：（1）度為0的結點（即葉子結點）總是比度為2的結點多一個；（n0=n2+1常用于求某個度的結點數）（2）在二叉樹的第k層上，最多有2^(k-1)(k≥1)個結點； （求單層最多節點數）（3）深度為k的二叉樹最多有2^k-1個結點； （求樹的最多結點總數）（4）具有n個結點的二叉樹，其深度至少為int[log2n]+1

（二叉樹的最小深度）青島工學院滿二叉樹

一顆深度為k且有2k-1個結點的二叉樹稱為滿二叉樹(可見，滿二叉樹結點總數一定是奇數)完全二叉樹

深度為k的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應（5）具有n個結點的完全二叉樹的深度為[log2n]+1或

[log2（n+1）]；（求完全二叉樹的深度）青島工學院二叉樹存儲結構 常采用鏈式存儲結構，對于滿二叉樹與完全二叉樹可以按層序進行順序存儲。二叉樹的遍歷（按某種次序，訪問二叉樹中的所有結點，使得每個結點僅被訪問一次）：（1）前序（根）遍歷（DLR），首先訪問根結點，然后遍歷左子樹，最后遍歷右子樹；（2）中序（根）遍歷（LDR），首先遍歷左子樹，然后訪問根結點，最后遍歷右子樹；（3）后序（根）遍歷（LRD），首先遍歷左子樹，然后訪問遍歷右子樹，最后訪問根結點。注意，遍歷時子樹也要遵循遍歷規則。前：ABDIJEKCFG中：IDJBKEAFCG后：IJDKEBFGCA規律：前序遍歷第一個節點是樹的根，后續遍歷最后一個節點是樹的根。青島工學院例題下列有關樹的概念錯誤的是（）A．一棵樹中只有一個無前驅的結點B．一棵樹的度為樹中各個結點的度數之和C．一棵樹中，每個結點的度數之和等于結點總數減1D．一棵樹中每個結點的度數之和與邊的條數之和相等下面關于二叉樹的敘述正確的是（）A．一棵二叉樹中葉子結點的個數等于度為2的結點個數加1B．一棵二叉樹中結點個數要大于0C．二叉樹中任何一個結點要么是葉，要么恰有兩個子女D．二叉樹中，任何一個結點的左子樹和右子樹上的結點個數一定相等B(A)青島工學院設n，m為一棵二叉樹上的兩個結點，在中序遍歷中，n在m前的條件是（）A．n在m右子樹上 B．n是m的祖先C．n在m左子樹上 D．n是m的子孫以下數據結構中不屬于線性數據結構的是______。

A.隊列 B.線性表 C.二叉樹 D.棧在一棵二叉樹上第5層的結點數最多是______。

A.8 B.16 C.32 D.15在深度為5的滿二叉樹中，葉子結點的個數為______。

A.32 B.31 C.16 D.15設一棵完全二叉樹共有699個結點，則在該二叉樹中的葉子結點數為______。

A.349 B.350 C.255 D.351樹最適合用來表示______。A．有序數據元素 B．無序數據元素C．元素之間具有分支層次關系的數據D．元素之間無聯系的數據(C)(C)(B)(C)(B)(C)青島工學院設有下列二叉樹：

對此二叉樹中序遍歷的結果為______。

A.ABCDEF B.DBEAFC

C.ABDECF D.DEBFCA已知二叉樹后序遍歷序列是dacbe，中序遍歷序列是deabc，它的前序遍歷序列是______。

A.cedba

B.acbed

C.decab

D.edbac(B)(D)青島工學院設樹T的度為4，其中度為1，2，3，4的結點個數分別為4，2，1，1。則T中的葉子結點數為______。

A.8 B.7 C.6 D.5一棵二叉樹的前序遍歷序列是ABDGCFK，中序遍歷序列是DGBAFCK，則結點的后序遍歷序列是（）A．ACFKDBG B．GDBFKCAC．KCFAGDB D．ABCDFKG一棵二叉樹共有70個葉子節點和80個度為1的節點，則該二叉樹的總節點數為（）

A.219 B.221 C.229 D.231(A)(B)(A)青島工學院1.7查找技術順序查找：

從表的一端開始，順序掃描線性表只能使用順序查找的情況：（1）線性表為無序表（不管是順序存儲還是鏈式存儲）；（2）表采用鏈式存儲結構（即使是有序存儲）。最壞情況需要比較n次二分查找：

把表不斷折半，和中值比較

******二分查找只適用于順序存儲的有序表 對于長度為n的有序線性表，最壞情況只需比較log2n次青島工學院對長度為N的線性表進行順序查找，在最壞情況下所需要的比較次數為______。

A.N+1 B.N C.(N+1)/2 D.N/2對長度為N的線性表進行二分查找，在最壞情況下所需要的比較次數為______。

A.N+1 B.log2n C.(N+1)/2 D.N/2對線性表進行折半查找時，要求線性表必須（）A．以順序方式存儲B．以鏈接方式存儲C．以順序方式存儲，且結點按關鍵字有序排列D．以鏈接方式存儲，且結點按關鍵字有序排列在順序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找關鍵碼值11，所需要的比較次數是______。(B)(B)(C)(4)青島工學院1.8排序技術交換類排序法：（1）冒泡排序法，最壞需要比較的次數為n(n-1)/2

。（2）快速排序法,最壞需要比較的次數為n2

插入類排序法：（1）簡單插入排序法，最壞需要比較的次數為n(n-1)/2

。（2）希爾排序法,最壞需要比較的次數為n1.5選擇類排序法：（1）簡單選擇排序法，最壞需要比較的次數為n(n-1)/2

。（2）堆排序法，最壞情況需要nlog2n次比較。青島工學院例題希爾排序法屬于哪一種類型的排序法______。

A.交換類排序法

B.插入類排序法

C.選擇類排序法

D.建堆排序法在最壞情況下，冒泡排序的時間復雜度為______。在最壞情況下，堆排序需要比較的次數為______。(B)O（n2

）---n的平方青島工學院二、程序設計基礎1.形成良好的程序設計風格應注意的因素2.結構化程序設計的主要原則3.結構化程序的基本結構與特點4.結構化程序設計的原則和方法的應用5.面向對象程序設計的主要優點6.面向對象方法的基本概念（對象、類和實例、消息、繼承和多態性）分值情況：所占分值1-2分注意區分：結構化程序設計和面向對象程序設計青島工學院本章學習方法

這兩章以概述的形式簡介了規范化開發軟件的方法。與數據結構不同，這兩章內容主要是記憶性的知識點。程序設計基礎的內容與大綱改革前添加了面向對象程序設計的內容，大家可以對本章進行幾次細讀后了解即可；軟件工程基礎這章主要考核內容為結構化分析及結構化設計方法（即SA及SD，約占50%），信息量較大，其次是軟件測試（約占20%），考生需要將相關的概念及規則背誦，在以后有機會進行程序開發時這些知識可以得到深刻理解。青島工學院2.1程序設計方法與風格

當今主導程序設計風格：“清晰第一，效率第二”良好的程序設計風格應注意的因素：1、源程序文檔化；符號命名要有規則正確的注釋：注釋分序言性注釋（一般寫在程序最前面，說明程序功能）和功能性注釋（語句功能、模塊功能、語句狀態說明等）視覺組織2、數據說明的方法；3、語句的結構；4、輸入和輸出。青島工學院例題結構化程序設計主要強調的是______。

A.程序的規模 B.程序的易讀性

C.程序的執行效率 D.程序的可移植性（本題不好，可不看）對建立良好的程序設計風格，下面描述正確的是______。

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

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

C.充分考慮程序的執行效率

D.程序的注釋可有可無源程序文檔化要求程序應加注釋，注釋一般分為序言性注釋和______。功能性注釋的主要內容不包括______。

A.程序的功能 B.語句的功能

C.模塊的功能 D.數據的狀態(B)(A)(功能性注釋)(A)青島工學院2.2結構化程序設計結構化程序設計方法的四條原則是：1.自頂向下；2.逐步求精；3.模塊化；4.限制使用goto語句。結構化程序的基本結構和特點：（1）順序結構：按照語句的自然順序，一條一條的執行；（2）選擇結構：又稱分支結構，包括簡單選擇和多分支選擇結構，可根據條件，判斷應該選擇哪一條分支來執行相應的語句序列；（3）重復結構：又稱循環結構，可根據給定條件，判斷是否需要重復執行某一相同程序段。包括直到型循環和當型循環。青島工學院結構化程序設計原則和方法的應用（也比較重要，學有余力的同學可以看看）

雖然結構化程序設計方法有很多優點，但它仍是一種面向過程的設計方法。缺點：：：它把數據和處理數據的過程分離為相互獨立的實體，當數據結構改變時，所有相關的處理過程的都要進行相應的修改，程序的可重用性差。青島工學院例題結構化程序設計方法的主要原則可以概括為自頂向下、逐步求精、______和限制使用goto語句。結構化程序設計的三種基本邏輯結構是順序、選擇和______下面描述中，符合結構化程序設計風格的是______。

A.使用順序、選擇和重復（循環）三種基本控制結構表示程序的控制邏輯

B.模塊只有一個入口，可以有多個出口

C.注重提高程序的執行效率

D.不使用goto語句

(A)青島工學院2.3面向對象的程序設計

傳統的程序設計方法是面向過程的（也就是面向過程的結構化程序設計），其核心方法是以算法為核心。面向對象程序設計以對象為核心。對象是由數據和容許的操作組成的封裝體，與客觀實體有直接的對應關系。對象之間通過傳遞消息互相聯系，以模擬現實世界中不同事物彼此之間的聯系。面向對象方法的優點：（1）與人類習慣的思維方法一致；（2）穩定性好；（3）可重用性好； （4）易于開發大型軟件產品；（5）可維護性好。********面向對象的模型中，最基本的概念是對象和類。青島工學院對象是面向對象方法中最基本的概念，可以用來表示客觀世界中的任何實體，對象是現實世界實體的抽象。面向對象的程序設計方法中的對象是系統中用來描述客觀事物的一個實體，是構成系統的一個基本單位，由一組表示其靜態特征的屬性和它可執行的一組操作組成。屬性即對象所包含的特征信息，描述對象的狀態操作描述了對象執行的功能，操作也稱為方法或服務。對象的基本特點：（1）標識惟一性：對象是可以互相區分的（2）分類性：將具有相同屬性和操作的對象抽象成類（3）多態性：同一個操作可以是不同對象的行為（4）封裝性：從外面看只能看到對象的外部特征，而不知道也無需知道數據的具體結構以及實現操作的算法。封裝性實現了信息的隱蔽，保證對象不受外部的破壞和干擾。（5）模塊獨立性：對象是一個封裝體。信息的隱蔽使模塊通過有限的接口傳遞消息，降低了模塊的耦合。青島工學院類是指具有共同屬性、共同方法的對象的集合。所以類是對象的抽象，對象是對應類的一個實例。消息是一個實例與另一個實例之間傳遞的信息。消息的組成包括：（1）接收消息的對象的名稱（誰）；（2）消息標識符，也稱消息名（做）；（3）零個或多個參數（什么）。繼承是指能夠直接獲得已有的性質和特征，而不必重復定義他們。是類之間共享屬性和操作的機制（提高可重用性，減少冗余）繼承分單繼承（改良）和多重繼承（嫁接）。單繼承指一個類只允許有一個父類，多重繼承指一個類允許有多個父類。青島工學院例題下面對對象概念描述錯誤的是______。

A.任何對象都必須有繼承性

B.對象是屬性和方法的封裝體

C.對象間的通訊靠消息傳遞

D.操作是對象的動態性屬性在面向對象方法中，一個對象請求另一對象為其服務的方式是通過發送______。

A.調用語句B.命令C.口令D.消息信息隱蔽的概念與下列哪個概念直接相關______。

A.軟件結構定義 B.模塊獨立性

C.模塊類型劃分 D.模塊耦合度面向對象的開發方法中，類與對象的關系是______。

A.具體與抽象 B.抽象與具體

C.整體與部分 D.部分與整體

(A)(D)(B)(B)青島工學院三、軟件工程基礎1.軟件工程基本概念，軟件生命周期概念，軟件工具與軟件開發環境。2.結構化分析方法，數據流圖，數據字典，軟件需求規格說明書。3.結構化設計方法，總體設計與詳細設計。4.軟件測試的方法，白盒測試與黑盒測試，測試用例設計，軟件測試的實施，單元測試、集成測試和系統測試。5.程序的調試，靜態調試與動態調試。青島工學院考點點評及考核情況考點點評：該部分內容考核不是很多。相對來說，考核比較多的是第4、5點，且有關白盒測試和黑盒測試的內容是經常考核的。分值情況：所占分值為2-3分。青島工學院3.1軟件工程的基本概念計算機軟件是包括程序、數據及相關文檔的完整集合。軟件的特點包括：（1）軟件是一種邏輯實體；（2）軟件的生產與硬件不同，它沒有明顯的制作過程；（3）軟件在運行、使用期間不存在磨損、老化問題；（4）軟件的開發、運行對計算機系統具有依賴性，受計算機系統的限制，這導致了軟件移植的問題；（5）軟件復雜性高，成本昂貴；（6）軟件開發涉及諸多的社會因素。軟件按功能分為應用軟件、系統軟件、支撐軟件（或工具軟件）。青島工學院軟件工程是應用于計算機軟件的定義、開發和維護的一整套方法、工具、文檔、實踐標準和工序。軟件工程包括3個要素：方法、工具和過程。軟件工程過程是把軟件轉化為輸出的一組彼此相關的資源和活動，包含4種基本活動：（1）P(計劃)——軟件規格說明； （2）D（執行）——軟件開發；（3）C（檢查）——軟件確認； （4）A（處理）——軟件演進。軟件生命周期：軟件產品從提出、實現、使用維護到停止使用退役的過程。青島工學院軟件生命周期三個階段:軟件定義、軟件開發、運行維護（時間最長），主要活動階段包括：可行性研究和計劃制定，需求分析，軟件設計，軟件實現，軟件測試，運行和維護軟件生命周期的主要活動階段為：

（1）可行性研究和計劃制定。確定待開發軟件系統的開發目標和總的要求，給出它在功能、性能、可靠性以及接口等方面的可能方案，制定完成開發任務的實施計劃。

（2）需求分析。對待開發軟件提出的需求進行分析并給出詳細定義，即準確地確定軟件系統的功能。編寫軟件規格說明書及初步的用戶手冊，提交評審。

（3）軟件設計。系統設計人員和程序設計人員應該在反復理解軟件需求的基礎上，給出軟件的結構、模塊的劃分、功能的分配以及處理流程。

（4）軟件實現。把軟件設計轉換成計算機可以接受的程序代碼。即完成源程序的編碼，編寫用戶手冊、操作手冊等面向用戶的文檔，編寫單元測試計劃。

（5）軟件測試。在設計測試用例的基礎上，檢驗軟件的各個組成部分。編寫測試分析報告。

（6）運行和維護。將已交付的軟件投入運行，并在運行使用中不斷地維護，根據新提出的需求進行必要而且可能的擴充和刪改。青島工學院其中，可行性研究的目的就是用最小的代價確定在問題定義階段確定的目標是否實現。可行性內容包括經濟可行性研究、技術可行性研究、法律可行性研究、開發方案的選擇性研究。軟件設計階段根據復雜程度可分為概要設計和詳細設計兩個階段。整個軟件生命周期中，最長的階段就是使用維護階段青島工學院例題在軟件生命周期中，能準確地確定軟件系統必須做什么和必須具備哪些功能的階段是______。

A.概要設計 B.詳細設計

C.可行性分析 D.需求分析下面不屬于軟件工程的3個要素的是______。

A.工具B.過程C.方法D.環境軟件開發的結構化生命周期方法將軟件生命周期劃分成______。

A.定義、開發、運行維護

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

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

D.需求分析、功能定義、系統設計

(D)(D)(A)青島工學院3.2結構化分析方法需求分析是指用戶對目標軟件系統在功能、行為、性能、設計約束等方面的期望，需求分析的任務是發現需求、求精、建模和定義需求的過程。需求分析將建立所需的數據模型、功能模型和控制模型需求分析階段的4個方面工作： 需求獲取、需求分析、編寫需求規格說明書、需求評審常見的需求分析方法有：（1）結構化需求分析方法：主要有面向數據流的結構化分析方法、面向數據結構的jackson方法和面向數據結構的結構化數據系統開發方法（2）面向對象的分析的方法。青島工學院結構化分析方法的實質：著眼于數據流，自頂向下，逐層分解，建立系統的處理流程，以數據流圖和數據字典為主要工具,建立系統的邏輯模型。結構化分析的常用工具（1）數據流圖； （2）數據字典；（3）判定樹； （4）判定表數據流圖（DFD）：描述數據處理過程的工具，它以圖形的方式描繪數據在系統中流動和處理的過程，它只反應系統必須完成的邏輯功能，所以是一種功能模型。青島工學院數據字典（DD）：對DD中所有與系統相關的數據元素的一個有組織的列表，以及精確的、嚴格的定義，使得用戶和系統分析員對于輸入、輸出、存儲成分和中間計算結果有共同的理解。

數據字典是結構化分析的核心。數據流圖和數據字典共同組成系統的邏輯模型。軟件需求規格說明書的作用：1、便于用戶、開發人員進行理解和交流。2、作為軟件開發工作的基礎和依據。3、作為確認測試和驗收的依據。青島工學院例題需求分析階段的任務是確定______。

A.軟件開發方法 B.軟件開發工具

C.軟件開發費用 D.軟件系統功能下列不屬于結構化分析的常用工具的是______。

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

C.判定樹 D.PAD圖在數據流圖（DFD）中，帶有名字的箭頭表示______。A.控制程序的執行順序 B.模塊之間的調用關系C.數據的流向 D.程序的組成成分(D)(D)(C)青島工學院在結構化方法中，用數據流程圖（DFD）作為描述工具的軟件開發階段是______。A.可行性分析 B.需求分析C.詳細設計 D.程序編碼下列敘述中，不屬于軟件需求規格說明書的作用的是______。A.便于用戶、開發人員進行理解和交流B.反映出用戶問題的結構，可以作為軟件開發工作的基礎和依據C.作為確認測試和驗收的依據D.便于開發人員進行需求分析(B)(D)青島工學院3.3結構設計方法

軟件設計是開發階段最重要的步驟，是將需求準確地轉化為完整的軟件產品或系統的唯一途徑。軟件設計是確定系統的物理模型。軟件設計的基本原理：

抽象、模塊化、信息隱蔽和模塊獨立性模塊的獨立程度是評價設計好壞的最重要度量標準，衡量軟件模塊獨立性使用耦合性和內聚性兩個定性的度量標準。在程序結構中各模塊的內聚性越強，則耦合性越弱。優秀軟件應高內聚，低耦合。結構化設計方法的基本要求是，在詳細設計階段，為了確保模塊邏輯清晰，就應該要求所有的模塊只使用單入口、單出口以及順序、選擇和循環3種基本控制結構。青島工學院面向數據流的設計方法，主要是分析信息在系統中加工和流動的情況。典型的數據流類型有兩種：變換型和事務型。詳細設計：主要確定每個模塊具體執行過程，也稱過程設計。詳細設計的結果基本上決定了最終的程序代碼的質量。常見的詳細設計工具有：圖形工具（程序流程圖（PFD）、盒圖（N-S）、問題分析圖（PAD）和HIPO）表格工具（判定表）語言工具（過程設計語言PDL(偽碼)）。青島工學院例題下列工具中屬于需求分析常用工具的是______。A.PAD B.PFDC.N-S D.DFD在進行軟件設計時應該遵守的最主要的原理是______。A.抽象 B.模塊化 C.模塊獨立 D.信息隱蔽(D)(C)青島工學院3.4軟件測試軟件測試：使用人工或自動手段來運行或測定某個系統的過程，用以檢驗它是否滿足規定的需求或是弄清預期結果與實際結果之間的差別。軟件測試的目的：為發現錯誤而執行程序的過程。

靜態測試：主要通過人工測試。(不用測試實例)

動態測試：利用計算機進行測試。軟件測試白盒測試黑盒測試青島工學院白盒測試（結構測試）：在程序內部進行，主要用于完成軟件內部操作的驗證，如果想用白盒測試出所有錯誤，則至少要把所有可能的路徑都執行一次。主要方法有邏輯覆蓋、基本路徑測試。黑盒測試：主要診斷功能錯誤或遺漏、界面錯誤、數據結構或外部數據庫訪問錯誤、性能錯誤、初始化和終止條件錯，用于軟件確認。主要方法有等價類劃分法、邊界值分析法、錯誤推測法等。軟件測試過程一般按4個步驟進行：單元測試：發現各個模塊內可能存在的錯誤，主要依據詳細設計說明書和源程序集成測試：發現和接口有關的錯誤，主要依據概要設計說明書驗收測試（確認測試）：運用黑盒測試法驗證軟件的功能是否滿足需求規格說明書的需求，軟件配置是否正確、完整。系統測試：在真實的工作環境下檢驗軟件是否正常工作青島工學院例題在軟件工程中，白箱測試法可用于測試程序的內部結構。此方法將程序看做是______。

A.循環的集合 B.地址的集合

C.路徑的集合 D.目標的集合在測試中，下列說法錯誤的是______。

A.測試是為了發現程序中的錯誤而執行程序的過程

B.測試為了表明程序的正確性

C.好的測試方案是極可能發現迄今為止尚未發現的錯誤的測試方案

D.成功的測試是發現了至今尚未發現的錯誤的測試軟件測試基本方法中，下列______不用測試實例。

A.白盒測試 B.動態測試 C.黑盒測試 D.靜態測試(C)(B)(D)青島工學院3.5程序的調試軟件測試主要為了發現錯誤，它的執行貫穿軟件生命周期，而程序調試的任務是診斷和改正程序中的錯誤，主要在開發階段進行；程序調試的基本步驟：（1）錯誤定位；（2）修改設計和代碼，以排除錯誤；（3）進行回歸測試，防止引進新的錯誤。軟件調試可分表靜態調試和動態調試。靜態調試主要是指通過人的思維來分析源程序代碼和排錯，是主要的設計手段，而動態調試是輔助靜態調試。主要調試方法有：（1）強行排錯法；（2）回溯法；（3）原因排除法。青島工學院例題

下列不屬于軟件調試技術的是______。A.強行排錯法 B.集成測試法C.回溯法 D.原因排除法軟件調試的目的是______。A.發現錯誤 B.改正錯誤C.改善軟件的性能 D.挖掘軟件的潛能(B)(B)青島工學院四、數據庫設計基礎數據庫、數據庫管理系統、數據庫系統數據庫系統的發展，數據庫系統的基本特點，數據庫系統的結構體系實體聯系模型及E-R圖，從E-R圖導出關系數據模型集合運算及選擇、投影、連接運算，數據規范化理論數據庫設計方法和步驟：需求分析、概念設計、邏輯設計和物理設計的相關策略數據庫管理青島工學院考點點評及考核情況考點點評：該部分內容的重要程度僅次于第一部分，基本上每個考核點在以往考試中都會涉及到，其中，數據模型和關系運算基本上每年都考。分值情況：所占分值為3-5分。青島工學院本章學習方法

數據庫是當前軟件處理的信息核心，目前大部分軟件都是基于數據庫的，因此學習一下數據庫知識對程序開發也是很有幫助的。本章主要的考核點是關系模型、關系代數及數據庫系統的基本概念，其余的知識點了解即可，其中數據庫的設計和管理可以結合著軟件工程來看，考生會發現這兩者有很多相似之處。除了關系代數會考一些簡單的計算問題外，其余的都是以概念題的形式考核，大家需要仔細的閱讀。青島工學院4.1數據庫系統的基本概念數據：實際上就是描述事物的符號記錄。數據的特點：有一定的結構，有型與值之分，如整型、實型、字符型等。而數據的值給出了符合定型的值。數據庫(DB)：是數據的集合，具有統一的結構形式并存放于統一的存儲介質內，是多種應用數據的集成，并可被各個應用程序共享。數據庫存放數據是按數據所提供的數據模式存放的，具有集成與共享的特點。數據庫管理系統(DBMS)：一種系統軟件，負責數據庫中的數據組織、數據操縱、數據維護、控制及保護和數據服務等，是數據庫系統的核心。青島工學院數據庫管理系統功能：（1）數據模式定義：即為數據庫構建其數據框架；（2）數據存取的物理構建：為數據模式的物理存取與構建提供有效的存取方法與手段；（3）數據操縱：為用戶使用數據庫的數據提供方便，如查詢、插入、修改、刪除等以及簡單的算術運算及統計；（4）數據的完整性、安全性定義與檢查；（5）數據庫的并發控制與故障恢復；（6）數據的服務：如拷貝、轉存、重組、性能監測、分析等。為完成以上六個功能，數據庫管理系統提供以下的數據語言：（1）數據定義語言(DDL)：負責數據的模式定義與數據的物理存取構建；（2）數據操縱語言(DML)：負責數據的操縱，如查詢與增、刪、改等；（3）數據控制語言(DCL)：負責數據完整性、安全性的定義與檢查以及并發控制、故障恢復等。青島工學院數據語言按其使用方式具有兩種形式：交互式命令(又稱自含型或自主型語言)、嵌入式命令（宿主型語言）。數據庫管理員（DBA）：對數據庫進行規劃、設計、維護、監視等的專業管理人員。數據庫系統(DBS)：由數據庫（數據）、數據庫管理系統（軟件）、數據庫管理員（人員）、硬件平臺（硬件）、軟件平臺（軟件）五個部分構成的運行實體。數據庫應用系統(DBAS)：由數據庫系統、應用軟件及應用界面三者組成。數據庫發展階段：人工管理階段文件系統階段層次與網狀數據庫系統階段關系數據庫系統階段數據庫應用系統DBAS數據庫管理系統DBMS數據庫DB數據庫系統DBS青島工學院數據庫系統的三級模式：（1）外模式：也稱子模式與用戶模式。是用戶的數據視圖。也就是用戶所見到的數據模式；(一個數據庫可以有多個外模式)(視圖)（2）概念模式（邏輯模式或模式）：數據庫系統中全局數據邏輯結構的描述，全體用戶公共數據視圖，不涉及具體的硬件和軟件環境，一個數據庫只有一個概念模式；（3）內模式：又稱物理模式，它給出了數據庫物理存儲結構與物理存取方法。（索引存取）（一個數據庫只有一個內模式）數據庫系統的兩級映射：（1）外模式到概念模式的映射。（2）概念模式到內模式的映射；青島工學院例題數據庫系統的核心是______。(B)A.數據模型 B.數據庫管理系統C.軟件工具 D.數據庫下列敘述中正確的是______。(C)A.數據庫是一個獨立的系統，不需要操作系統的支持B.數據庫設計是指設計數據庫管理系統C.數據庫技術的根本目標是要解決數據共享的問題D.數據庫系統中，數據的物理結構必須與邏輯結構一致下列模式中，能夠給出數據庫物理存儲結構與物理存取方法的是______。(A)A.內模式 B.外模式C.概念模式 D.邏輯模式青島工學院在數據管理技術的發展過程中，經歷了人工管理階段、文件系統階段和數據庫系統階段。其中數據獨立性最高的階段是______。

(A)A.數據庫系統 B.文件系統C.人工管理 D.數據項管理索引存取屬于______。

(B)A.模式 B.內模式 C.外模式 D.概念模式數據處理的最小單位是______。(C)A.數據B.數據元素C.數據項D.數據結構下列有關數據庫的描述，正確的是______。(C)A.數據庫是一個DBF文件