全國計算機二級公共基礎知識復習復習資料重點

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

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

或攵據(jù)結(jié)構(gòu)指的是數(shù)據(jù)之間的相互關系，即數(shù)據(jù)的組織形式。

數(shù)據(jù)結(jié)構(gòu)用來反映一個數(shù)據(jù)的內(nèi)部構(gòu)成，即一個數(shù)據(jù)由哪些成分構(gòu)成、以

什么方式構(gòu)成、呈現(xiàn)什么樣的結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)有邏輯上的數(shù)據(jù)結(jié)

構(gòu)中口物理上的數(shù)據(jù)結(jié)構(gòu)之分。邏輯上的數(shù)據(jù)結(jié)構(gòu)反映數(shù)據(jù)之間的

邏輯關系，而物理上的數(shù)據(jù)結(jié)構(gòu)反映數(shù)據(jù)在計算機內(nèi)部的存儲安排。數(shù)據(jù)結(jié)

構(gòu)是數(shù)據(jù)存在的形式。

算法是解題的步驟，是指令的有限序列。它們規(guī)定了解決某一特定

類型問題的一系列運算，是對解題方案的準確與完整的描述。一個問題的

解決方案要以算法為基礎。

1.1概念介紹

?算法的時間復雜度：

算法的時間復雜度是指執(zhí)行算法所需要的計算工作量。

算法的工作量用算法所執(zhí)行的基本運算次數(shù)來度量，而算法所執(zhí)行的基本

運算次數(shù)是問題規(guī)模的函數(shù)，即

算法的工作量二f(n)

其中n是問題的規(guī)模。

彳列出口，兩個n階矩陣相乘所需要的基本運算(即兩個實數(shù)的乘法)次數(shù)

為即計算工作量為1?,也就是時間復雜度為

?算法的空間復雜度：

算法的空間復雜度一般是指執(zhí)行這個算法所需要的內(nèi)存空間。

?數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)元素相互之間的關系，稱為結(jié)構(gòu)。

數(shù)據(jù)的邏輯結(jié)構(gòu)：是指反映數(shù)據(jù)元素之間邏輯關系的數(shù)據(jù)結(jié)構(gòu)。

?數(shù)據(jù)的存儲結(jié)構(gòu)

數(shù)據(jù)的存儲結(jié)構(gòu)：是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式。也

稱數(shù)據(jù)的物理結(jié)構(gòu)。

各數(shù)據(jù)元素在計算機存儲空間中的位置關系與它們的邏輯關系不一定是

相同的。同一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以根據(jù)需要表示成任意一種或幾種不同的

存儲結(jié)構(gòu)。

數(shù)據(jù)的順序存儲方式：是將邏輯上相鄰的結(jié)點存儲在物理位置上亦

相鄰的存儲單元里。也就是將所有存儲結(jié)點相繼存入在一個連續(xù)相鄰的存儲區(qū)

里。

數(shù)據(jù)的鏈式存儲方式：是在存儲每個結(jié)點信息的同時，增加一個

指針來表示結(jié)點間的邏輯關系。該方式不要求邏輯上相鄰結(jié)點在物理位置上亦

相鄰，結(jié)點間的邏輯關系是由附加的指針字段表示的。因此，鏈式存儲結(jié)構(gòu)

中的每個結(jié)點都由兩部分組成：一部分用于存儲結(jié)點本身的信息，稱為數(shù)據(jù)

域；另一部分用于存儲該結(jié)點的后繼結(jié)點（或前驅(qū)結(jié)點）的存儲單元地址，稱為

指針域。指針域可以包含一個或多個指針，這由結(jié)點之間的關系所決定。

?線性結(jié)構(gòu)和非線性結(jié)構(gòu)

如果在一個線性結(jié)構(gòu)中，一個數(shù)據(jù)元素都沒有，則稱該數(shù)據(jù)結(jié)構(gòu)為空數(shù)據(jù)

結(jié)構(gòu)。

線性結(jié)構(gòu)的邏輯特征：在一個非空的數(shù)據(jù)結(jié)構(gòu)中，除第一個數(shù)據(jù)

元素只有一個后繼沒有前驅(qū)、最后一個數(shù)據(jù)元素只有一個前驅(qū)沒有后繼外，其

他的每一個數(shù)據(jù)元素僅有一個前驅(qū)和一個后繼。線性結(jié)構(gòu)也稱為線，性表。

注：某個元素直接相鄰的前一個元素稱為此元素的前3區(qū)、直接相鄰的后

一個元素稱為此元素的后欠L

非線性結(jié)構(gòu)的邏輯外寺征：在一個非空的數(shù)據(jù)結(jié)構(gòu)中，某數(shù)據(jù)元素

可能有多于一個前驅(qū)或后繼。如樹型結(jié)構(gòu)等。

習題：

（-）選擇題（單選）

1.算法的時間復雜度是指（D）

A）算法的執(zhí)行時間

B）算法所處理的數(shù)據(jù)量

0算法程序中的語句或指令條數(shù)

D）算法在執(zhí)行過程中所需要的基本運算次數(shù)

1.2線性表

線性表是由同一類型的數(shù)據(jù)元素構(gòu)成的一種線性的數(shù)據(jù)結(jié)構(gòu)。是一種最

基本、最常用的數(shù)據(jù)結(jié)構(gòu)。線性表常用的存儲方式有兩種：順序存儲方式和鏈

接存儲方式。

線性表的數(shù)學定義：

L=（ai,a2,a3,…,aQ

說明：

線性表是具有相同類型的n（n2O）個數(shù)據(jù)元素組成的有限序列。

L：為表的名稱。

ai（i=l,2,...,n）：為表的元素，也稱為線性表中的一個結(jié)點。它可以是一個

數(shù)、一個字符、一個字符串，也可以是一條記錄，還可以是復雜的數(shù)據(jù)對象。

ai是a2的前驅(qū)、a?是a1的后繼，a2是a3的前驅(qū)、a3是a2的后繼，…，依次

類推。

n：為線性表的長度(元素個數(shù))，當n=0時稱線性表為空表。

線性表的特點：

在非空的線性表中：存在唯一的一個“第一個元素”(根結(jié)點)。存在唯一

的一個“最后一個元素”(終端結(jié)點)。除第一個元素外，其他的元素均有唯一

的前驅(qū)。除最后一個元素外，其他的元素均有唯一的后繼。

1.3棧和隊列

棧和隊列本質(zhì)上也是線性表，只是它們的操作受到了限制。

1.3.1棧

棧是限定僅在表尾進行插入和刪除操作的線性表。表尾稱為棧頂(top),表

頭稱為棧底(bottom)。

棧這種數(shù)據(jù)結(jié)構(gòu)，類似于子彈夾，底端是封閉的，最后壓入的子彈總是最

先被彈出，最先壓入的子彈只能最后被彈出。

棧頂元素總是最后被插入的元素，從而也是最先能被刪除的元素；棧底元

素總是最先被插入的元素，從而也是最后能被刪除的元素。即棧是按照“先進

后出”或“后進先出”的原則組織數(shù)據(jù)的。因此，棧也被稱為“先進后

出”表或“后進先出”表。由此可以看出，棧具有記憶作用。

1.3.2隊列

隊列是指只允許在表的一端插入元素、在另一端刪除元素的線性表。允許插入

的一端稱為隊尾(rear)，允許刪除的一端稱為隊頭(front)。

在隊列這種數(shù)據(jù)結(jié)構(gòu)中，最先插入的元素將最先能夠被刪除，反之最后插入

的元素將最后才能被刪除。因此，隊列又稱為“先進先出”或“后

進后出”的線性表。

1.4樹和二叉樹

1.4.1樹

樹形結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)中一種很重要的非線性結(jié)構(gòu)。在樹形結(jié)構(gòu)中，所有

數(shù)據(jù)元素之間的關系具有明顯的層次特性。樹形結(jié)構(gòu)很像自然界中的樹，像

一棵倒長的樹。在現(xiàn)實生活中，能用樹形結(jié)構(gòu)表示的例子很多。參見下面的

樹形結(jié)構(gòu)的基本特征及基本術語:

以下圖為例:

樹的根：

在樹形結(jié)構(gòu)中，沒有前驅(qū)的結(jié)點只有一個，稱為樹的根結(jié)點，簡稱為樹

的根。如：上圖中的“R”。

父結(jié)點：

在樹形結(jié)構(gòu)中，每一個結(jié)點（除了樹的根結(jié)點）只有一個前驅(qū)，稱為父結(jié)點。

如：上圖中的“R”是K、P、Q、D的父結(jié)點；“N”是X、Y的父結(jié)點。

子結(jié)點：

在樹形結(jié)構(gòu)中，每個結(jié)點可以有多個后繼，稱為該結(jié)點的子結(jié)點。

如：上圖中的K、P、Q、D是“R”的子結(jié)點；X、Y是“N”的子結(jié)點。

葉子結(jié)點：

在樹形結(jié)構(gòu)中，沒有后繼的結(jié)點稱為葉子結(jié)點，也稱終端結(jié)點。

如：上圖中的C、M、F、E、X、G、S、L、Z、A均為葉子結(jié)點。

結(jié)點的度：

在樹形結(jié)構(gòu)中，一個結(jié)點所擁有的后繼個數(shù)稱為該結(jié)點的度。

如：上圖中根結(jié)點R的度是4；結(jié)點T的度是3；結(jié)點P、Q、D、0、Y、

W的度都為1。葉子結(jié)點的度為0。

樹的度：

在樹形結(jié)構(gòu)中，所有結(jié)點中的最大的度稱為樹的度。如：上圖中樹的度

為4,因為結(jié)點R的度最大，是4。

樹的深度：

在樹形結(jié)構(gòu)中，樹的最大層數(shù)稱為樹的深度(或高度)o如：上圖中樹的

深度是5。說明：樹形結(jié)構(gòu)具有明顯的層次關系，即樹是一種層次結(jié)構(gòu)。

在樹形結(jié)構(gòu)中一般按如下原則分層：

1)根結(jié)點在第1層。

2)其余結(jié)點的層數(shù)等于其父結(jié)點的層數(shù)加lo

子樹：

在樹形結(jié)中，以某結(jié)點的一個子結(jié)點為根構(gòu)成的樹稱為該結(jié)點的一棵子

樹。

如：上圖中，結(jié)點R有4棵子樹，它們分別以K、P、Q、D為根結(jié)點；結(jié)點

P有1棵子樹，其根結(jié)點為N；結(jié)點T有3棵子樹，它們分別以W、Z、A為

根結(jié)點。

在樹形結(jié)構(gòu)中，子樹間互不相交，葉子結(jié)點沒有子樹。

森林：

森林是M(MNO)棵互不相交的樹的集合。刪去一棵樹的根，就得到一個

森林；反之，加上一個結(jié)點作樹根，森林就變?yōu)橐豢脴洹?/p>

1.4.2二叉樹

(1)二叉樹的特點

①非空二叉樹只有一個根結(jié)點。

②二叉樹中的每個結(jié)點，最多有兩棵子樹，分另稱為該結(jié)點的左子樹與

右子樹。當一個結(jié)點即沒有左子樹也沒有右子樹時，該結(jié)點就是葉子結(jié)點。在

下面的圖中，左面是只有根結(jié)點的二叉樹，右面是深度為4的二叉樹：

(2)滿二叉樹與完全二叉樹

1)滿二叉樹:

滿二叉樹是指除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。

就是說，在滿二叉樹中，每一層上的結(jié)點數(shù)都達到最大值，即在滿二叉

樹的第k層上有2M(k2i)個結(jié)點，且深度為k的滿二叉樹有2k-1(k^1)

個結(jié)點。

在下圖中分別是深度為2、3,4的滿二叉樹:

E

(a)深度為2的滿二叉樹(b)深度為3的滿二叉樹(C)深度為4的滿二叉樹

圖1.32滿二叉樹

滿二叉樹中不存在度數(shù)為1的結(jié)點，每個分支結(jié)點均有兩棵深度相同的子樹,

且葉子結(jié)點都在最下一層。

2)完全二叉樹:

若一棵二叉樹最多只有最下面的兩層上結(jié)點的度數(shù)可以小于2,并且最下

一層上的所有結(jié)點都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二

叉樹。

在下圖的4棵二叉樹中，分別是深度為3和4的完全二叉樹:

(?)深度為3的完全二叉樹(b)深度為4的完全二叉樹

田1.33完全二叉樹

滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。

在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去若干結(jié)點后得到的二叉樹仍

然是一棵完全二叉樹。

在完全二叉樹中，若某個結(jié)點沒有左子結(jié)點，則它一定沒有右子結(jié)點，即

該結(jié)點必是葉子結(jié)點。

(3)二叉樹的性質(zhì)

假設定義根結(jié)點的層數(shù)為1(注意：有些資料中規(guī)定根結(jié)點的層數(shù)為0)。

性質(zhì)1：在二叉樹的第i層上，最多有2i-1(i21)個結(jié)點。

性質(zhì)2：深度為k的二叉樹最多有2k-1(k21)個結(jié)點。

性質(zhì)3：在任意二叉樹中，若度為o的結(jié)點(即葉子結(jié)點)的個數(shù)為no，度

為2的結(jié)點的個數(shù)為及，則：nO=n2+1

(對于完全二叉樹還有如下屬性)

性質(zhì)4：具有n個結(jié)點的完全二叉樹，其深度為[Iog2n]+1o/i：[log2n]

表示取log2n的整數(shù)部分。性質(zhì)5：如果將一棵有n個結(jié)點的完全二叉樹自

頂向下、同一層自左向右連續(xù)給結(jié)點編號1、2、3、…、n,則對于任意結(jié)

點i(lWiWn)有如下結(jié)論：

1）如果i=l,此結(jié)點為根結(jié)點，無前驅(qū)（即無父結(jié)點）；

如果i>l,則該結(jié)點的父結(jié)點編號為Int（i/2）o也可表示成[i/2],

都表示取整數(shù)。

2）如果2i>n,則結(jié)點i無左子結(jié)點，顯然也沒有右子結(jié)點，是葉子結(jié)點。

如果2iWn,則結(jié)點i的左子結(jié)點是編號為2i的名吉點。

3）如果2i+l>n,則結(jié)點i無右子結(jié)點。

如果2i+lWn,則結(jié)點i的右子結(jié)點的編號為2i+1o

（4）二叉樹的遍歷

二叉樹的遍歷就是遵從某種次序，訪問二叉樹中的所有結(jié)點，使得每

個結(jié)點僅被訪問一次。

一棵非空二叉樹是由根結(jié)點、左子樹和右子樹三部分組成。因此遍歷一棵

非空二叉樹的問題就可以分解為三項“子任條”：

①訪問根結(jié)點（假設用D表示）。

②遍歷左子樹（假設用L表示）。

③遍歷右子樹（假設用R表示）。

在遍歷二叉樹的過程中，一般先遍歷左子樹，然后再遍歷右子樹。在先

左后右的原則下，根據(jù)訪問根結(jié)點的次序，二叉樹的遍歷可分為三種：前序

遍歷（DLR）、中序遍歷（LDR）、后序遍歷（LRD）。

以下圖中的二叉樹為例:

前序遍歷（DLR）:

首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹;在遍歷左、右子

樹時，仍然先訪問子樹的根結(jié)點，然后遍歷其左子樹，最后遍歷其右子樹。即,

前序遍歷是指訪問所有的根結(jié)點（包括子樹的根結(jié)點）都在遍歷其左、右子樹之

刖。

前序遍歷的操作：

若二叉樹為空，則結(jié)束反返回。否則：

①訪問根結(jié)點

②前序遍歷左子樹

③前序遍歷右子樹

如，對上圖中的二叉樹進行前序遍歷的結(jié)果是：FCADBEGHP

中序遍歷（LDR）:

首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。在

遍歷左、右子樹時，仍然先遍歷其左子樹，然后訪問子樹的根結(jié)點，最后遍

歷其右子樹。即，中序遍歷是指訪問所有的根結(jié)點（包括子樹的根結(jié)點渚R在遍

歷其左子樹之后、在遍歷其右子樹之前。

中序遍歷的操作：

若二叉樹為空，則結(jié)束反返回。否則：

①中序遍歷左子樹

②訪問根結(jié)點

③中序遍歷右子樹

如，對上圖中的二叉樹進行中序遍歷的結(jié)果是：ACBDFEHGP

后序遍歷（LRD）：

首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。

在遍歷左、右子樹時，仍然先遍歷其左子樹，然后遍歷其右子樹，最后訪問

子樹的根結(jié)點。即，后序遍歷是指訪問所有的根結(jié)點（包括子樹的根結(jié)點）都在

遍歷其左、右子樹之后。

后序遍歷的操作：

若二叉樹為空，則結(jié)束反返回。否則：

①后序遍歷左子樹

②后序遍歷右子樹

③訪問根結(jié)點

如，對上圖中的二叉樹進行后序遍歷的結(jié)果是：ABDCHPGEF

1.5查找

查找又稱檢索。查找是指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找某個指定的元素。

通常，根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，應采用不同的查找方法。

1.5.1順序查找

順序查找又稱順序搜索或線性查找。順序查找一般是指在線性表中查找指

定的元素。

順序查找的基本思想：

在n個結(jié)點組成的線性表中，從線性表的一端開始，依次將線性表中的元

素與被查元素進行比較，若相等則表示找到，即查找成功；若線性表中所有的

元素都與被查元素進行了比較但都不相等，則表示線性表中沒有要找的元素，

即查找失敗。

在順序查找中，查找成功時最多需要比較n次、最少

比較1次、平均比較次數(shù)約為表長的一半。查找失敗時比

較n+1次。

順序查找的時間復雜度為0（n）。

對于無序表（即表中的元素的排列是無序的）和鏈式存儲結(jié)構(gòu)的線性表（有序

的和無序的），只能用順序查找。

順序查找的優(yōu)點：

算法簡單而適用范圍廣。對表中元素的排列次序無要求，既可以是按

關鍵字排列的有序表，也可以是無序表；對表的存儲結(jié)構(gòu)也無任何要求，既

適用于順序存儲的順序表，也適用于鏈接存儲的鏈表。

順序查找的缺點：

查找效率低，平均查找長度較大。當n很大時不宜采用順序查找。

1.5.2二分查找

二分查找又稱折半查找。它是一種查找效率較高的查找方法。該方法只

適用于順序存儲結(jié)構(gòu)的有序表。通常是指有序表中的元素按值升序排列(非遞

減有序排列)0二分查找不能用于鏈式存儲結(jié)構(gòu)的線性表。

二分查找的基本思想：參見“C語言程序設計”或“VB程序設計”課件的

相應內(nèi)容動畫。

對于長度為n的有序線性表，查找成功時最多需

要比較Iog2(n+1)次、最少比較1次、平均查找長度近

似Iog2no當查找失敗時，比較log2n或Iog2(n+1)

次。

不管二分查找成功與否，其時間復雜度均為

0(log2n)o

二分查找的最壞性能和平均性能相當接近。

1.6排序

排序就是將文件中的記錄進行整理，使之按照關鍵字進行遞增或遞減的

順序排列起來，成為一個有序序列的過程。在本節(jié)所介紹的排序方法中，其

排序的對象一般認為是順序存儲的線性表，在程序設計語言中就是一維數(shù)組。

這里的排序算法，都是針對升序排序。

1.6.1交換排序

交換排序是兩兩比較待排序記錄的關鍵字，若發(fā)現(xiàn)兩個記錄關鍵字的次序

相反時即進行交換，直到?jīng)]有反序的記錄為止。下面介紹兩種常用的交換排

序。

(1)冒泡排序

冒泡排序的基本思想：參見“C語言程序設計”或“VB程序設計”課件的

相應內(nèi)容動畫。

對于長度為n的線性表，在最壞情況下，冒泡

排序需要經(jīng)過n/2遍的掃描，比較次數(shù)為n(n-1)/2o

冒泡排序算法的平均時間復雜度為0(n2),空

間復雜度為0(1)。

(2)快速排序

快速排序的基本思想：

參見下圖：

分割

分割

快速排序示意圖

從線性表中選取一個元素，設為T,將線性表后面小于T的元素移到前

面，將線性表前面大于T的元素移到后面，結(jié)果就把線性表分成了兩部分(稱

為兩個子表)，T插入到其分界線的位置處，這個過程稱為線性表的分割。通

過對線性表的一次分割，就以T為分界線，將線性表分成了前后兩個子表，且

前面子表中的所有元素均不大于T,后面子表中的所有元素均不小于T。

如果對分割后的各子表再按上述原則進行分割，并且這種分割過程可以一

直做下去，隨著對各子表不斷地進行分割，劃分出的子表會越來越多(一次只

能對一個子表進行再分割處理)，直到所有子表中的元素都排好序為止，則此

時的線性表就變成了有序表。

對于長度為n的線性表：

在最壞情況下，快速排序比較次數(shù)為n(n-1)/2。算

法的時間復雜度為0(n2),空間復雜度為0(n)。

在最好情況下，快速排序算法的時間復雜度為

0(nlog2n),空間復雜度為0(log2n)。

快速排序算法的平均時間復雜度是0(nlog2n),平

均比較次數(shù)不大于(n+1)Iog2n

1.6.2插入排序

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

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

(1)直接插入排序

快速排序的基本思想：請查看相關資料。

對于長度為n的線性表：

在最壞情況下，直接插入排序比較次數(shù)為n(n-1)/2。

算法的時間復雜度為0(n2)。

(2)希爾排序

希爾排序的基本思想：請查看相關資料。

對于長度為n的線性表：

在最壞情況下希爾排序比較次數(shù)為0(n1.5)。

1.6.3選擇排序

選擇排序的基本思想是：每一遍在n-i+l(i=l,2,…,n-l)個待排序記錄中選取關

鍵字最小的記錄作為有序序列中第i個記錄，直到全部記錄排完為止。

（1）直接選擇排序

選擇排序的基本思想：參見“C語言程序設計”或“VB程序設計”課件的

相應內(nèi)容動畫。

在最壞情況下，直接選擇排序比較次數(shù)為

n（n-1）/2o

（2）堆排序

希爾排序的基本思想：請查看相關資料。

在最壞情況下，堆排序比較次數(shù)為0（nlog2n）。

習題：

（-）選擇題（單選）

1.下列敘述中正確的是（D）

A）棧是“先進先出”的線性表

B）隊列是“先進后出”的線性表

C）循環(huán)隊列是非線性結(jié)構(gòu)

D）有序線性表既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈式存儲結(jié)構(gòu)

2.下列關于棧的敘述中正確的是（A）

A）棧頂元素最先被刪除B）棧頂元素最后才能被刪除

0棧底元素永遠不能被刪除D）以上三種說法都不對

3.下列敘述中正確的是（B）

A）有一個以上根結(jié)點的數(shù)據(jù)結(jié)構(gòu)不一定是非線性結(jié)構(gòu)

B）只有一個根結(jié)點的數(shù)據(jù)結(jié)構(gòu)不一定是線性結(jié)構(gòu)

0循環(huán)鏈表是非線性結(jié)構(gòu)

D）雙向鏈表是非線性結(jié)構(gòu)

4.支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是（A）

A）棧B）樹C）隊列D）二叉樹

5.某二叉樹有5個度為2的結(jié)點，則該二叉樹中的葉子結(jié)點數(shù)是（C）

A）10B）8C）6D）4

提示：在任意二叉樹中，若度為0的結(jié)點（即葉子結(jié)點）的個數(shù)為no,度為2的結(jié)點的個

數(shù)為n2,則：n0=n2+l即nO（葉子結(jié)點數(shù)）=5+1=6

6.某二叉樹共有7個結(jié)點，其中葉子結(jié)點只有1個，則該二叉樹的深度為（假設根結(jié)點

在第一層）（D）

A）3B）4C）6D）7

7.下列排序方法中，最壞情況下比較次數(shù)最少的是（D）

A）冒泡排序B）簡單選擇排序C）直接插入排序D）堆排序

8.下列敘述中正確的是（A）

A）對長度為n的有序鏈表進行查找，最壞的情況下需要的比較次數(shù)為n

B）對長度為n的有序鏈表進行對分查找，最壞的情況下需要的比較次數(shù)為（n/2）

0對長度為n的有序鏈表進行對分查找，最壞的情況下需要的比較次數(shù)為（logzn）

D）對長度為n的有序鏈表進行對分查找，最壞的情況下需要的比較次數(shù)為（nlogzn）

（-）填空題

1.假設用一個長度為50的數(shù)組（數(shù)組元素的下標從0到49）作為棧的存儲空間，棧底指

針bottom指向棧底元素，棧頂指針top指向棧頂元素，如果bottom=49,top=30（數(shù)組下標）,

則棧中具有個元素。

答案：20

2.一個隊列的初始狀態(tài)為空?，F(xiàn)將元素A、B、C、D、E、F、5、4、3、2、1一次入隊，然

后再一次退隊，則元素退隊的順序為。

答案：A、B、C、D、E、F、5、4、3、2、1

3.設某循環(huán)隊列的容量為50,如果頭指針front=45（指向隊頭元素的前一個位置），尾

指針rear=10（指向隊尾元素），則該循環(huán)隊列中共有個元素。

答案：15

4.設二叉樹如下:

對該二叉樹進行后序遍歷的結(jié)果為

答案：E、D、B、G、H、F、C、A

5.一棵二叉樹的中序遍歷結(jié)果為DBEAFC,前序遍歷結(jié)果為ABDECF,則后

序遍歷結(jié)果為o

答案：DEBFCA

6.有序線性表能進行二分查找的前提是該線性表必須是存儲。

答案：順序

二、軟件工程基礎

計算機軟件是計算機系統(tǒng)中與硬件相互依存的另一部分，是包括程序、數(shù)

據(jù)及相關文檔的完整集合。

軟件由兩部分組成：一是機器可執(zhí)行的程序和數(shù)據(jù)；二是機器不可執(zhí)行的，

與軟件開發(fā)、運行、維護、使用等有關的文檔。

軟件的分類

軟件按功能可以分為：應用軟件、系統(tǒng)軟件、支撐軟件（或工具軟件）。

應用軟件：是為解決特定領域的應用而開發(fā)的軟件。

系統(tǒng)軟件：是計算機管理自身資源，提高計算機使用效率并為計算機用

戶提供各種服務的軟件。

支撐軟件：是介于系統(tǒng)軟件和應用軟件之間，協(xié)助用戶開發(fā)軟件的工具性

軟件。

軟件生命周期

通常將軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的過程稱為軟件

生命周期。參見下圖：

結(jié)構(gòu)化分析方法

結(jié)構(gòu)化分析的常用工具：

數(shù)據(jù)流圖（DFD）：是描述數(shù)據(jù)處理過程的工具，是需求理解的邏輯模型的

圖形表示，它直接支持系統(tǒng)的功能建模。

數(shù)據(jù)字典（DD）：是結(jié)構(gòu)化分析方法的核心。

判定樹

判定表

結(jié)構(gòu)化設計方法

常見的過程設計工具：

圖形工具：程序流程圖，N-S圖，PAD圖（問題分析圖），HIPO

表格工具：判定表。

語言工具：PDL（偽碼）

軟件設計的基本原理

1）抽象：是一種思維工具，就是把事物本質(zhì)的共同特性提取出來而不考

慮其他細節(jié)。

2）模塊化：是指把一個待開發(fā)的軟件分解成若干小的簡單的部分。如高級

語言中的過程、函數(shù)、子程序等。每個模塊可以完成一個特定的子功能，各個

模塊可以按一定的方法組裝起來成為一個整體，從而實現(xiàn)整個系統(tǒng)的功能。

3）信息隱蔽：是指在一個模塊內(nèi)包含的信息（過程或數(shù)據(jù)），對于不需要這

些信息的其他模塊來說是不能訪問的。

4）模塊獨立性：是指每個模塊只完成系統(tǒng)要求的獨立的子功能，并且與其他

模塊的聯(lián)系最少且接口簡單。模塊的獨立程度是評價設計好壞的重要度量標

準。衡量軟件的模塊獨立性使用耦合性和內(nèi)聚性兩

個定性的度量標準。

內(nèi)聚性：是一個模塊內(nèi)部各個元素間彼此結(jié)合的緊密程度的度量。內(nèi)

聚是從功能角度來度量模塊內(nèi)的聯(lián)系。

內(nèi)聚性是信息隱蔽和局部化概念的自然擴展。一個模塊的內(nèi)聚性越強則

該模塊的模塊獨立性越強。作為軟件結(jié)構(gòu)設計的設計原則，要求每一個模塊的

內(nèi)部都具有很強的內(nèi)聚性，它的各個組成部分彼此都密切相關。

耦合性：耦合性是模塊間相互連接的緊密程度的度量。

一個模塊與其他模塊的耦合性越強則該模塊的模塊獨立性越弱。原則上講,

模塊化設計總是希望模塊間的耦合表現(xiàn)為非直接耦合方式。但是，由于問題所

固有的復雜性和結(jié)構(gòu)化設計的原則，非直接耦合往往是不存在的。

耦合性與內(nèi)聚性是模塊獨立性的兩個定性標準，耦合性與內(nèi)聚性是相互

聯(lián)系的。在程序結(jié)構(gòu)中，各模塊的內(nèi)聚性越強，則耦合性越弱。一般優(yōu)秀

的軟件設計，應盡量做到高內(nèi)聚，低耦合，即減弱模塊之間的耦合性和提高

模塊內(nèi)的的內(nèi)聚性，有利于提高模塊的獨立性。

軟件測試

軟件測試是在軟件投入運行前對軟件需求、設計、編碼的最后審核。軟件

測試是為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程。軟件測試應當制定明確的測試計劃并

按計劃執(zhí)行。

軟件測試的目的：是發(fā)現(xiàn)錯誤。

軟件測試方法和技術：若從是否需要執(zhí)行被測軟件的角度，可以分為靜態(tài)

測試和動態(tài)測試方法。若按照功能劃分可以分為白盒測試和黑盒測試方法。

靜態(tài)測試：包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量等。靜態(tài)測試不

實際運行軟件，主要通過人工進行。

動態(tài)測試：是基于計算機的測試，是為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程。需

要精心設計一批測試用例，并利用這些測試用例去運行程序，以發(fā)現(xiàn)程序錯誤

的過程。測試用例的格式為：

［（輸入值集）,（輸出值集）］

白盒測試：也稱結(jié)構(gòu)測試或邏輯驅(qū)動測試。它是根據(jù)軟件產(chǎn)品的內(nèi)部工作

過程，檢查內(nèi)部成分，以確認每種內(nèi)部操作符合設計規(guī)格要求。白盒測試

把測試對象看作一個打開的盒子，允許測試人員利用程序內(nèi)部的邏輯結(jié)構(gòu)及有

關信息來設計或選擇測試用例，對程序所有的邏輯路徑進行測試。通過在不同

點檢查程序的狀態(tài)來了解實際的運行狀態(tài)是否與預期的一致。所以，白盒測

試是在程序內(nèi)部進行，主要用于完成軟件內(nèi)部操作的驗證。

白盒測試的主要方法有邏輯覆蓋、基本路徑測試等。

黑盒測試：也稱功能測試或數(shù)據(jù)驅(qū)動測試。黑盒測試是對軟件已經(jīng)實現(xiàn)的

功能是否滿足需求進行測試和驗證。黑盒測試完全不考慮程序內(nèi)部的邏輯結(jié)構(gòu)

和內(nèi)部特征，只依據(jù)程序的需求和功能規(guī)格說明，檢查程序的功能是否符合

它的功能說明。所以，黑盒測試是在軟件接口處進行，完成功能驗證。黑盒

測試只檢查程序功能是否按照需求規(guī)格說明書的規(guī)定正常使用，程序是否能適

當?shù)亟邮蛰斎霐?shù)據(jù)而產(chǎn)生正確的輸出信息，并且保持外部信息（如數(shù)據(jù)庫或文件）

的完整性。

黑盒測試主要診斷功能不對或遺漏、界面錯誤、數(shù)據(jù)結(jié)構(gòu)或外部數(shù)據(jù)庫訪

問錯誤、性能錯誤、初始化和終止條件錯誤。黑盒測試方法主要有等價類劃分

法、邊界值分析法、錯誤推測法、因果圖等，主要用于軟件確認測試。

程序調(diào)試

在對程序進行了成功的測試之后，將進入程序調(diào)試（通常稱Debug,即排

錯）。程序調(diào)試的任務是診斷和改正程序中的錯誤。

它與軟件測試不同，軟件測試是盡可能多地發(fā)現(xiàn)軟件中的錯

誤，并找出軟件錯誤的具體位置。軟件測試貫穿整

個軟件生命期，調(diào)試主要在開發(fā)階段。

習題：

（-）選擇題（單選）

1.軟件按功能可以分為：應用軟件、系統(tǒng)軟件和支撐軟件（或工具軟件）。下面屬于應用

軟件的是（C）

A）編譯程序B）操作系統(tǒng)C）教務管理系統(tǒng)D）匯編程序

2.軟件按功能可分為：應用軟件、系統(tǒng)軟件、和支撐軟件（或工具軟件）。下面屬于系統(tǒng)

軟件的是（B）

A）編輯軟件B）操作系統(tǒng)C）教務管理系統(tǒng)D）瀏覽器、

3.軟件（程序）調(diào)試的任務是（A）

A）診斷和改正程序中的錯誤B）盡可能多的發(fā)現(xiàn)程序中的錯誤

0發(fā)現(xiàn)并改正程序中的所有錯誤D）確定程序中錯誤的性質(zhì)

4.下面敘述中錯誤的是（A）

A）軟件測試的目的是發(fā)現(xiàn)錯誤并改正錯誤

B）對被調(diào)試的程序進行“錯誤定位”是程序調(diào)試的必要步驟

C）程序調(diào)試通常也稱為Debug

D）軟件測試應嚴格執(zhí)行測試計劃，排除測試的隨意性

5.耦合性和內(nèi)聚性是對模塊獨立性度量的兩個標準。下列敘述中正確的是（B）

A）提高耦合性、降低內(nèi)聚性有利于提高模塊的獨立性

B）降低耦合性、提高內(nèi)聚性有利于提高模塊的獨立性

C）耦合性是指一個模塊內(nèi)部各個元素間彼此結(jié)合的緊密程度

D）內(nèi)聚性是指模塊間互相連接的緊密程度

6.數(shù)據(jù)流圖（DFD圖）是（C）

A）軟件概要設計的工具B）軟件詳細設計的工具

0結(jié)構(gòu)化方法的需求分析工具D）面向?qū)ο蠓椒ǖ男枨蠓治龉ぞ?/p>

7.軟件生命周期可分為定義階段，開發(fā)階段和維護階段。詳細設計屬于（B）

A）定義階段B）開發(fā)階段0維護階段D）上述三個階段

8.在軟件開發(fā)中，需求分析階段產(chǎn)生的主要文檔是（D）

A）軟件集成測試計劃B）軟件詳細設計說明書0用戶手冊D）軟件需求規(guī)格說

明書

9.結(jié)構(gòu)化程序所要求的基本結(jié)構(gòu)不包括（B）

A）順序結(jié)構(gòu)B）60T0跳轉(zhuǎn)C）選擇（分支）結(jié)構(gòu)D）重復（循環(huán)）結(jié)構(gòu)

10.下面描述中錯誤的是（A）

A)系統(tǒng)總體結(jié)構(gòu)圖支持軟件系統(tǒng)的詳細設計

B)軟件設計是將軟件需求轉(zhuǎn)換為軟件表示的過程

0數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫設計是軟件設計的任務之一

D)PAD圖是軟件詳細設計的表示工具

(二)填空題

1.軟件測試可分為白盒測試和黑盒測試?；韭窂綔y試屬于測試。

答案：白盒

2.符合結(jié)構(gòu)化原則的三種基本控制結(jié)構(gòu)是：選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)和

答案：順序結(jié)構(gòu)

3.軟件是、數(shù)據(jù)和文檔的集合。

答案：程序

4.對軟件設計的最小單位(模塊或程序單元)進行的測試通常為測試。

答案：單元或模塊

三、數(shù)據(jù)庫設計基礎

計算機應用的三大領域：科學計算、數(shù)據(jù)處理、過程控制。

數(shù)據(jù)庫系統(tǒng)的基本概念

數(shù)據(jù)(Data)：就是描述事物的符號記錄。

數(shù)據(jù)庫(DB)：是數(shù)據(jù)的集合，它具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲

介質(zhì)內(nèi)，是多種應用數(shù)據(jù)的集成，并可被各個應用程序所共享。數(shù)據(jù)庫中

的數(shù)據(jù)具有“集成”、“共享”的特點。

數(shù)據(jù)庫管理系統(tǒng)(DBMS)：是數(shù)據(jù)庫的機構(gòu)，是一種系統(tǒng)軟件，負責數(shù)

據(jù)庫中的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護、控制及保護和數(shù)據(jù)服務等。數(shù)據(jù)庫

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

數(shù)據(jù)庫管理系統(tǒng)一般提供相應的數(shù)據(jù)語言(DataLanguage)來完成相應的功

能:

數(shù)據(jù)定義語言(DDL)：負責數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建。

數(shù)據(jù)操縱語言(DML)：負責數(shù)據(jù)的操縱，包括查詢及增、刪、改等操作。

數(shù)據(jù)控制語言(DCL)：負責數(shù)據(jù)完整性、安全性的定義與檢查以及并發(fā)控

制、故障恢復等功能，包括系統(tǒng)初啟程序、文件讀寫與維護程序、存取路徑管

理程序、緩沖區(qū)管理程序、安全性控制程序、完整性檢查程序、并發(fā)控制程序、

事務管理程序、運行日志管理程序、數(shù)據(jù)庫恢復程序等。

數(shù)據(jù)庫管理員(DBA)：由于數(shù)據(jù)庫的共享性，因此對數(shù)據(jù)庫的規(guī)劃、設計、

維護、監(jiān)視等需要有專人管理，稱他們?yōu)閿?shù)據(jù)庫管理員。

數(shù)據(jù)庫系統(tǒng)(DBS)：由數(shù)據(jù)庫(數(shù)據(jù))、數(shù)據(jù)庫管理系統(tǒng)(軟件)、數(shù)據(jù)庫管理

員(人員)、系統(tǒng)硬件平臺(硬件)、系統(tǒng)軟件平臺(軟件)這五部分組成，稱為數(shù)

據(jù)庫系統(tǒng)。

數(shù)據(jù)庫應用系統(tǒng)(DBAS):是數(shù)據(jù)庫系統(tǒng)再加上應用軟件及應用界面這三

者所組成。

E-R模型

該模型將現(xiàn)實世界的要求轉(zhuǎn)化成實體、聯(lián)系、屬性等幾個基本概念，以及

它們間的兩種基本聯(lián)接關系，并且可以用一種圖非常直觀地表示出來。下

面是E-R模型的基本概念。

目前較為有名的概念模型有E-R模型、擴充的E-R模型、面向?qū)ο竽Ｐ图?/p>

謂詞模型等。

實體：現(xiàn)實世界中的事物可以抽象成為實體。實體是概念世界中的基本單

位，它們是客觀存在的且又相互區(qū)別的事物。凡是有共性的實體可組成一個

集合稱實體集。如學生A和學生B,他們都是實體，他們又都是學生，從

而組成一個學生實體集。

屬性：現(xiàn)實世界中的事物均有一些特性，這些特性可以用屬性來表示。屬

性刻畫了實體的特征。一個實體往往可以有若干個屬性。

聯(lián)系：現(xiàn)實世界中事物間的關聯(lián)稱為聯(lián)系。在概念世界中聯(lián)系反映了實

體集間的一定關系。如工人與設備間的操作關系，上、下級間的領導關系等。

實體集間的聯(lián)系有多種，就實體集的個數(shù)而言有：

1)兩個實體集間的聯(lián)系。

2)多個實體集間的聯(lián)系。

3)一個實體集內(nèi)部的聯(lián)系：是一個實體集內(nèi)的不同實體間的聯(lián)系。

實體集間聯(lián)系的個數(shù)可以是單個也可以是多個，包括：

一對一的聯(lián)系，簡記為1:1

一對多或多對一的聯(lián)系，簡記為1:M或M:1(其中M也可以小寫)

多對多的聯(lián)系，簡記為M:N或m:n

E-R模型由上面三個基本概念組成。由實體、聯(lián)系、屬性三者結(jié)合起來才

能表示現(xiàn)實世界。

E-R圖：E-R模型可以用一種非常直觀的圖的形式表示，這種圖稱為E-R

圖。在E-R圖中我們分別用下面不同的幾何圖形表示E-R模型中的三個概念

與兩個聯(lián)接關系。

1)實體集表示法

用矩形表示實體集，在矩形內(nèi)寫上該實體集的名字。如實體集學生

(student)>課程(course)可表示為：

studentcourse

實體集表示法

2)屬性表示法

用橢圓形表示屬性，在橢圓形內(nèi)寫上該屬性的名稱。如學生有屬性：學

號(S#)、姓名(Sn)及年齡(Sa),可表示為:

(^Sn^)

屬性表示法

3)聯(lián)系表示法

用菱形表示聯(lián)系，在菱形內(nèi)寫上聯(lián)系名。如學生與課程間的聯(lián)系SC,

可表示為:

上面是三個基本概念分別用三種幾何圖形表示。下面是它們之間的聯(lián)接關系

的圖形表示。

4）實體集或聯(lián)系與屬性間的聯(lián)接關系

屬性依附于實體集，屬性也依附于聯(lián)系，因此它們之間分別有聯(lián)接關系。

其中：C#（課程號）、Cn（課程名）、P#（預修課號）

5）實體集與聯(lián)系間的聯(lián)接關系

如下圖表示實體集與聯(lián)系間的聯(lián)接關系：

還可以在線段邊上注明其對應的函數(shù)關系，如1:1、l:n、n:m等。下圖表

示student與course間有多對多聯(lián)系：

下圖

聯(lián)系FPU是一種三元聯(lián)系(工廠、產(chǎn)品與用戶間的聯(lián)系)：

下面是實體間多種聯(lián)系圖:

(a)圖：公司職工(enployee"可上、下級管理(manage)的聯(lián)系。即一個實體

集內(nèi)部可以有多種聯(lián)系。

(b)圖：教師(T)與學生(S)之間可以有教學(E)聯(lián)系也可以有管理(M)聯(lián)系。

即實體集間可以有多種聯(lián)系。

關系模型

關系模型采用二維表來表示，簡稱表。

二維表由表框架(Frame)及表的元組(Tuple)組成。表框架由n個命名的屬性

(Attribute)組成，n稱為屬性元數(shù)(Arity)。每個屬性有一個取值范圍，稱為值

域(Domain)。表框架對應了關系的模式，即類型的概念。

在表框架中按行可以存放數(shù)據(jù)，每行數(shù)據(jù)稱為元組，實際上，一個元組

是由n個元組分量所組成，每個元組分量是表框架中每個屬性的投影值。一

個表框架可以存放m個元組，m稱為表的基數(shù)(Cardinality)。

一個n元表框架及框架內(nèi)m個元組構(gòu)成了一個完整的二維表。

關系框架與關系元組構(gòu)成了一個關系。一個語義相關的關系集合構(gòu)

成一個關系數(shù)據(jù)庫。關系的框架稱為關系模式，而語義相關的關系模式集

合構(gòu)成了關系數(shù)據(jù)庫模式。

滿足下面7個性質(zhì)的二維表稱為關系（Relation）：

1）元組個數(shù)有限性：二維表中元組個數(shù)是有限的。

2）元組的惟一性：二維表中元組均不相同。

3）元組的次序無關性：二維表中元組的次序可以任意交換。

4）元組分量的原子性：二維表中元組的分量是不可分割的基本數(shù)據(jù)項。

5）屬性名惟一性：二維表中屬性名各不相同。

6）屬性的次序無關性：二維表中屬性與次序無關，可任意交換。

7）分量值域的同一性：二維表屬性的分量具有與該屬性相同的值域。

以二維表（關系）為基本結(jié)構(gòu)所建立的模型稱為關系模型。

在關系模型中的一個重要概念是鍵（Key）或碼。鍵具有標識元組、建立元

組間聯(lián)系等重要作用。

鍵或碼：在二維表中凡能惟一標識元組的最小屬性集稱為該表的鍵或碼。

候選鍵或候選碼：二維表中可能有若干個鍵，它們稱為該表的候選鍵

（CandidataKey）或候選碼。

主鍵或主碼：從二維表的所有候選鍵中選取一個作為用戶使用的鍵，稱為

主鍵（PrimaryKey）或主碼。一般主鍵也簡稱為鍵或碼。

外鍵或外碼：表A中的某屬性集是某表B的鍵，則稱該屬性集為A的

外鍵（ForeignKey）或外碼。

表中一定要有鍵，因為如果表中所有屬性的子集均不是鍵，則表中屬性的

全集必為鍵（稱為全鍵），因此也一定有主鍵。

在關系元組的分量中允許出現(xiàn)空值（NullValue）以表示信息空缺?？罩涤?/p>

于表示未知的值或不可能出現(xiàn)的值，一般用NULL表示。一般關系數(shù)據(jù)庫

系統(tǒng)都支持空值，但是有兩個限制：關系的主鍵中不允許出現(xiàn)空值，因為如

主鍵為空值則失去了其元組標識的作用；需要定義有關空值的運算。

關系代數(shù)

關第代數(shù)是關于關系數(shù)據(jù)庫的理論。

數(shù)據(jù)庫設計與管理

數(shù)據(jù)庫設計是數(shù)據(jù)庫應用的核心。

數(shù)據(jù)庫設計的四個階段，參見下圖:

DBMS模彗

DBMS條件

硬件、OS支膜

數(shù)據(jù)庫內(nèi)模式

數(shù)據(jù)庫設計的四個階段

從E-R圖向關系模式轉(zhuǎn)換

參見下表:

E-R模型與關系間的比較裊

E-R模型

關系E-R模型關系

屬性

屬性實體集關系

?

實體

元組聯(lián)系關系

習題:

（-）選擇題（單選）

1.數(shù)據(jù)庫應用系統(tǒng)中的核心問題是（A）

A