全國計算機二級公共基礎(chǔ)知識--復(fù)習(xí)

1、全國計算機二級公共基礎(chǔ)知識-復(fù)習(xí)全國計算機二級公共基礎(chǔ)知識一、數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)之間的相互關(guān)系，即數(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ù)之間的邏輯關(guān)系，而物理上的數(shù)據(jù)結(jié)構(gòu)反映數(shù)據(jù)在計算機內(nèi)部的存儲安排。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存在的形式。算法是解題的步驟，是指令的有限序列。它們規(guī)定了解決某一特定類型問題的一系列運算，是對解題方案的準(zhǔn)確與完整的描述。一個問題的解決方案要以算法為基礎(chǔ)。 概念介紹 算法的時間復(fù)雜度：算法的時間復(fù)雜度是指執(zhí)行算法所需要

2、的計算工作量。算法的工作量用算法所執(zhí)行的基本運算次數(shù)來度量，而算法所執(zhí)行的基本運算次數(shù)是問題規(guī)模的函數(shù)，即 算法的工作量=f(n)其中n是問題的規(guī)模。 例如，兩個n階矩陣相乘所需要的基本運算(即兩個實數(shù)的乘法)次數(shù)為n3，即計算工作量為n3，也就是時間復(fù)雜度為n3。 算法的空間復(fù)雜度：算法的空間復(fù)雜度一般是指執(zhí)行這個算法所需要的內(nèi)存空間。數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素相互之間的關(guān)系，稱為結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)：是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(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ù)元素在計算機存儲空間中的位置關(guān)系與它們的邏輯關(guān)系不一定

3、是相同的。同一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以根據(jù)需要表示成任意一種或幾種不同的存儲結(jié)構(gòu)。數(shù)據(jù)的順序存儲方式：是將邏輯上相鄰的結(jié)點存儲在物理位置上亦相鄰的存儲單元里。也就是將所有存儲結(jié)點相繼存入在一個連續(xù)相鄰的存儲區(qū)里。數(shù)據(jù)的鏈?zhǔn)酱鎯Ψ绞剑菏窃诖鎯γ總€結(jié)點信息的同時，增加一個指針來表示結(jié)點間的邏輯關(guān)系。該方式不要求邏輯上相鄰結(jié)點在物理位置上亦相鄰，結(jié)點間的邏輯關(guān)系是由附加的指針字段表示的。因此，鏈?zhǔn)酱鎯Y(jié)構(gòu)中的每個結(jié)點都由兩部分組成：一部分用于存儲結(jié)點本身的信息，稱為數(shù)據(jù)域；另一部分用于存儲該結(jié)點的后繼結(jié)點(或前驅(qū)結(jié)點)的存儲單元地址，稱為指針域。指針域可以包含一個或多個指針，這由結(jié)點之間的關(guān)系所決定。線

4、性結(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)也稱為線性表。注：某個元素直接相鄰的前一個元素稱為此元素的前驅(qū)、直接相鄰的后一個元素稱為此元素的后繼。非線性結(jié)構(gòu)的邏輯特征：在一個非空的數(shù)據(jù)結(jié)構(gòu)中，某數(shù)據(jù)元素可能有多于一個前驅(qū)或后繼。如樹型結(jié)構(gòu)等。習(xí)題：（一）選擇題(單選)1. 算法的時間復(fù)雜度是指（d）a) 算法的執(zhí)行時間b) 算法所處理的數(shù)據(jù)量c) 算法程序中的語句或指令條數(shù)d)

5、算法在執(zhí)行過程中所需要的基本運算次數(shù)線性表線性表是由同一類型的數(shù)據(jù)元素構(gòu)成的一種線性的數(shù)據(jù)結(jié)構(gòu)。是一種最基本、最常用的數(shù)據(jù)結(jié)構(gòu)。線性表常用的存儲方式有兩種：順序存儲方式和鏈接存儲方式。線性表的數(shù)學(xué)定義：l=(a1,a2,a3,an)說明：線性表是具有相同類型的n(n0)個數(shù)據(jù)元素組成的有限序列。l：為表的名稱。ai(i=1,2, ,n)：為表的元素，也稱為線性表中的一個結(jié)點。它可以是一個數(shù)、一個字符、一個字符串，也可以是一條記錄，還可以是復(fù)雜的數(shù)據(jù)對象。a1是a2的前驅(qū)、a2是a1的后繼， a2是a3的前驅(qū)、a3是a2的后繼，依次類推。n：為線性表的長度(元素個數(shù))，當(dāng)n=0時稱線性表為空表。

6、線性表的特點：在非空的線性表中：存在唯一的一個“第一個元素”(根結(jié)點)。存在唯一的一個“最后一個元素”(終端結(jié)點)。除第一個元素外，其他的元素均有唯一的前驅(qū)。除最后一個元素外，其他的元素均有唯一的后繼。棧和隊列棧和隊列本質(zhì)上也是線性表，只是它們的操作受到了限制。棧棧是限定僅在表尾進行插入和刪除操作的線性表。表尾稱為棧頂(top)，表頭稱為棧底(bottom)。棧這種數(shù)據(jù)結(jié)構(gòu)，類似于子彈夾，底端是封閉的，最后壓入的子彈總是最先被彈出，最先壓入的子彈只能最后被彈出。棧頂元素總是最后被插入的元素，從而也是最先能被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后能被刪除的元素。即棧是按照“先進后

7、出”或“后進先出”的原則組織數(shù)據(jù)的。因此，棧也被稱為“先進后出”表或“后進先出”表。由此可以看出，棧具有記憶作用。隊列隊列是指只允許在表的一端插入元素、在另一端刪除元素的線性表。允許插入的一端稱為隊尾(rear)，允許刪除的一端稱為隊頭(front)。在隊列這種數(shù)據(jù)結(jié)構(gòu)中，最先插入的元素將最先能夠被刪除，反之最后插入的元素將最后才能被刪除。因此，隊列又稱為“先進先出”或“后進后出”的線性表。樹和二叉樹樹樹形結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)中一種很重要的非線性結(jié)構(gòu)。在樹形結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性。樹形結(jié)構(gòu)很像自然界中的樹，像一棵倒長的樹。在現(xiàn)實生活中，能用樹形結(jié)構(gòu)表示的例子很多。參見下面的

8、圖形：樹形結(jié)構(gòu)的基本特征及基本術(shù)語：以下圖為例：樹的根：在樹形結(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ù)

9、稱為該結(jié)點的度。如：上圖中根結(jié)點r的度是4；結(jié)點t的度是3；結(jié)點p、q、d、o、y、w的度都為1。葉子結(jié)點的度為0。樹的度：在樹形結(jié)構(gòu)中，所有結(jié)點中的最大的度稱為樹的度。如：上圖中樹的度為4，因為結(jié)點r的度最大，是4。樹的深度：在樹形結(jié)構(gòu)中，樹的最大層數(shù)稱為樹的深度(或高度)。如：上圖中樹的深度是5。說明：樹形結(jié)構(gòu)具有明顯的層次關(guān)系，即樹是一種層次結(jié)構(gòu)。在樹形結(jié)構(gòu)中一般按如下原則分層：1) 根結(jié)點在第1層。2) 其余結(jié)點的層數(shù)等于其父結(jié)點的層數(shù)加1。子樹：在樹形結(jié)中，以某結(jié)點的一個子結(jié)點為根構(gòu)成的樹稱為該結(jié)點的一棵子樹。如：上圖中，結(jié)點r有4棵子樹，它們分別以k、p、q、d為根結(jié)點；結(jié)點p有1

10、棵子樹，其根結(jié)點為n；結(jié)點t有3棵子樹，它們分別以w、z、a為根結(jié)點。在樹形結(jié)構(gòu)中，子樹間互不相交，葉子結(jié)點沒有子樹。森林：森林是m(m0)棵互不相交的樹的集合。刪去一棵樹的根，就得到一個森林；反之，加上一個結(jié)點作樹根，森林就變?yōu)橐豢脴洹６鏄?1) 二叉樹的特點 非空二叉樹只有一個根結(jié)點。 二叉樹中的每個結(jié)點，最多有兩棵子樹，分另稱為該結(jié)點的左子樹與右子樹。當(dāng)一個結(jié)點即沒有左子樹也沒有右子樹時，該結(jié)點就是葉子結(jié)點。在下面的圖中，左面是只有根結(jié)點的二叉樹，右面是深度為4的二叉樹： (2) 滿二叉樹與完全二叉樹1) 滿二叉樹：滿二叉樹是指除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。就是說，在

11、滿二叉樹中，每一層上的結(jié)點數(shù)都達到最大值，即在滿二叉樹的第k層上有2i-1(k1)個結(jié)點，且深度為k的滿二叉樹有2k-1(k1)個結(jié)點。在下圖中分別是深度為2、3、4的滿二叉樹：滿二叉樹中不存在度數(shù)為1的結(jié)點，每個分支結(jié)點均有兩棵深度相同的子樹，且葉子結(jié)點都在最下一層。2) 完全二叉樹：若一棵二叉樹最多只有最下面的兩層上結(jié)點的度數(shù)可以小于2，并且最下一層上的所有結(jié)點都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。在下圖的4棵二叉樹中，分別是深度為3和4的完全二叉樹：滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去若干結(jié)點后得到的二叉樹仍然

12、是一棵完全二叉樹。在完全二叉樹中，若某個結(jié)點沒有左子結(jié)點，則它一定沒有右子結(jié)點，即該結(jié)點必是葉子結(jié)點。(3) 二叉樹的性質(zhì)假設(shè)定義根結(jié)點的層數(shù)為1(注意：有些資料中規(guī)定根結(jié)點的層數(shù)為0)。性質(zhì)1：在二叉樹的第i層上，最多有2i-1(i1)個結(jié)點。性質(zhì)2：深度為k的二叉樹最多有2k-1(k1)個結(jié)點。性質(zhì)3：在任意二叉樹中，若度為0的結(jié)點(即葉子結(jié)點)的個數(shù)為n0，度為2的結(jié)點的個數(shù)為n2，則：n0= n2+1(對于完全二叉樹還有如下屬性)性質(zhì)4：具有n個結(jié)點的完全二叉樹，其深度為log2n+1。注：log2n表示取log2n的整數(shù)部分。性質(zhì)5：如果將一棵有n個結(jié)點的完全二叉樹自頂向下、同一層自

13、左向右連續(xù)給結(jié)點編號1、2、3、n，則對于任意結(jié)點i(1in)有如下結(jié)論：1) 如果i=1，此結(jié)點為根結(jié)點，無前驅(qū)(即無父結(jié)點)；如果i>1，則該結(jié)點的父結(jié)點編號為int(i/2)。也可表示成i/2，都表示取整數(shù)。2)如果2i>n，則結(jié)點i無左子結(jié)點，顯然也沒有右子結(jié)點，是葉子結(jié)點。如果2in，則結(jié)點i的左子結(jié)點是編號為2i的結(jié)點。3) 如果2i+1>n，則結(jié)點i無右子結(jié)點。如果2i+1n，則結(jié)點i的右子結(jié)點的編號為2i+1。(4) 二叉樹的遍歷二叉樹的遍歷就是遵從某種次序，訪問二叉樹中的所有結(jié)點，使得每個結(jié)點僅被訪問一次。一棵非空二叉樹是由根結(jié)點、左子樹和右子樹三部分組成。

14、因此遍歷一棵非空二叉樹的問題就可以分解為三項“子任條”： 訪問根結(jié)點(假設(shè)用d表示)。 遍歷左子樹(假設(shè)用l表示)。 遍歷右子樹(假設(shè)用r表示)。在遍歷二叉樹的過程中，一般先遍歷左子樹，然后再遍歷右子樹。在先左后右的原則下，根據(jù)訪問根結(jié)點的次序，二叉樹的遍歷可分為三種：前序遍歷(dlr)、中序遍歷(ldr)、后序遍歷(lrd)。 以下圖中的二叉樹為例： 前序遍歷(dlr)： 首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。在遍歷左、右子樹時，仍然先訪問子樹的根結(jié)點，然后遍歷其左子樹，最后遍歷其右子樹。即，前序遍歷是指訪問所有的根結(jié)點(包括子樹的根結(jié)點)都在遍歷其左、右子樹之前。 前序遍歷的操作

15、： 若二叉樹為空，則結(jié)束反返回。否則： 訪問根結(jié)點 前序遍歷左子樹 前序遍歷右子樹如，對上圖中的二叉樹進行前序遍歷的結(jié)果是：f c a d b e g h p 中序遍歷(ldr)： 首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。在遍歷左、右子樹時，仍然先遍歷其左子樹，然后訪問子樹的根結(jié)點，最后遍歷其右子樹。即，中序遍歷是指訪問所有的根結(jié)點(包括子樹的根結(jié)點)都在遍歷其左子樹之后、在遍歷其右子樹之前。 中序遍歷的操作： 若二叉樹為空，則結(jié)束反返回。否則： 中序遍歷左子樹 訪問根結(jié)點 中序遍歷右子樹如，對上圖中的二叉樹進行中序遍歷的結(jié)果是：a c b d f e h g p 后序遍歷(lrd)：

16、 首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。在遍歷左、右子樹時，仍然先遍歷其左子樹，然后遍歷其右子樹，最后訪問子樹的根結(jié)點。即，后序遍歷是指訪問所有的根結(jié)點(包括子樹的根結(jié)點)都在遍歷其左、右子樹之后。 后序遍歷的操作： 若二叉樹為空，則結(jié)束反返回。否則： 后序遍歷左子樹 后序遍歷右子樹 訪問根結(jié)點如，對上圖中的二叉樹進行后序遍歷的結(jié)果是：a b d c h p g e f查找查找又稱檢索。查找是指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找某個指定的元素。通常，根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，應(yīng)采用不同的查找方法。 順序查找順序查找又稱順序搜索或線性查找。順序查找一般是指在線性表中查找指定的元素。順序查找的基本思想

17、：在n個結(jié)點組成的線性表中，從線性表的一端開始，依次將線性表中的元素與被查元素進行比較，若相等則表示找到，即查找成功；若線性表中所有的元素都與被查元素進行了比較但都不相等，則表示線性表中沒有要找的元素，即查找失敗。在順序查找中，查找成功時最多需要比較n次、最少比較1次、平均比較次數(shù)約為表長的一半。查找失敗時比較n+1次。順序查找的時間復(fù)雜度為o(n)。對于無序表(即表中的元素的排列是無序的)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表(有序的和無序的)，只能用順序查找。順序查找的優(yōu)點：算法簡單而適用范圍廣。對表中元素的排列次序無要求，既可以是按關(guān)鍵字排列的有序表，也可以是無序表；對表的存儲結(jié)構(gòu)也無任何要求，既適用于

18、順序存儲的順序表，也適用于鏈接存儲的鏈表。 順序查找的缺點： 查找效率低，平均查找長度較大。當(dāng)n很大時不宜采用順序查找。 二分查找二分查找又稱折半查找。它是一種查找效率較高的查找方法。該方法只適用于順序存儲結(jié)構(gòu)的有序表。通常是指有序表中的元素按值升序排列(非遞減有序排列)。二分查找不能用于鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表。 二分查找的基本思想：參見“c語言程序設(shè)計”或“vb程序設(shè)計”課件的相應(yīng)內(nèi)容動畫。 對于長度為n的有序線性表，查找成功時最多需要比較log2(n+1)次、最少比較1次、平均查找長度近似log2n。當(dāng)查找失敗時，比較log2n或log2(n+1)次。 不管二分查找成功與否，其時間復(fù)雜度均為

19、o(log2n)。 二分查找的最壞性能和平均性能相當(dāng)接近。 排序 排序就是將文件中的記錄進行整理，使之按照關(guān)鍵字進行遞增或遞減的順序排列起來，成為一個有序序列的過程。在本節(jié)所介紹的排序方法中，其排序的對象一般認(rèn)為是順序存儲的線性表，在程序設(shè)計語言中就是一維數(shù)組。 這里的排序算法，都是針對升序排序。 交換排序 交換排序是兩兩比較待排序記錄的關(guān)鍵字，若發(fā)現(xiàn)兩個記錄關(guān)鍵字的次序相反時即進行交換，直到?jīng)]有反序的記錄為止。下面介紹兩種常用的交換排序。(1) 冒泡排序冒泡排序的基本思想：參見“c語言程序設(shè)計”或“vb程序設(shè)計”課件的相應(yīng)內(nèi)容動畫。 對于長度為n的線性表，在最壞情況下，冒泡排序需要經(jīng)過n/2

20、遍的掃描，比較次數(shù)為n(n-1)/2。 冒泡排序算法的平均時間復(fù)雜度為o(n2)，空間復(fù)雜度為o(1)。(2) 快速排序快速排序的基本思想： 參見下圖： 從線性表中選取一個元素，設(shè)為t，將線性表后面小于t的元素移到前面，將線性表前面大于t的元素移到后面，結(jié)果就把線性表分成了兩部分(稱為兩個子表)，t插入到其分界線的位置處，這個過程稱為線性表的分割。通過對線性表的一次分割，就以t為分界線，將線性表分成了前后兩個子表，且前面子表中的所有元素均不大于t，后面子表中的所有元素均不小于t。 如果對分割后的各子表再按上述原則進行分割，并且這種分割過程可以一直做下去，隨著對各子表不斷地進行分割，劃分出的子表

21、會越來越多(一次只能對一個子表進行再分割處理)，直到所有子表中的元素都排好序為止，則此時的線性表就變成了有序表。 對于長度為n的線性表：在最壞情況下，快速排序比較次數(shù)為n(n-1)/2。算法的時間復(fù)雜度為o(n2)，空間復(fù)雜度為o(n)。 在最好情況下，快速排序算法的時間復(fù)雜度為o(nlog2n)，空間復(fù)雜度為o(log2n)。快速排序算法的平均時間復(fù)雜度是o(nlog2n)，平均比較次數(shù)不大于(n+1)log2n 插入排序 插入排序是每次將一個待排序的記錄按其關(guān)鍵字大小，插入到前面已排好的序列中的適當(dāng)位置，直到全部記錄插入為止。(1) 直接插入排序 快速排序的基本思想：請查看相關(guān)資料。 對于

22、長度為n的線性表：在最壞情況下，直接插入排序比較次數(shù)為n(n-1)/2。算法的時間復(fù)雜度為o(n2)。(2) 希爾排序 希爾排序的基本思想：請查看相關(guān)資料。 對于長度為n的線性表：在最壞情況下希爾排序比較次數(shù)為o。 選擇排序 選擇排序的基本思想是：每一遍在n-i+1(i=1,2,n-1)個待排序記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個記錄，直到全部記錄排完為止。(1) 直接選擇排序 選擇排序的基本思想：參見“c語言程序設(shè)計”或“vb程序設(shè)計”課件的相應(yīng)內(nèi)容動畫。 在最壞情況下，直接選擇排序比較次數(shù)為n(n-1)/2。(2) 堆排序 希爾排序的基本思想：請查看相關(guān)資料。 在最壞情況下，堆排

23、序比較次數(shù)為o(nlog2n)。習(xí)題：（一）選擇題(單選)1. 下列敘述中正確的是( d )a）棧是“先進先出”的線性表b）隊列是“先進后出”的線性表c）循環(huán)隊列是非線性結(jié)構(gòu)d）有序線性表既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)2. 下列關(guān)于棧的敘述中正確的是( a )a) 棧頂元素最先被刪除 b) 棧頂元素最后才能被刪除c) 棧底元素永遠(yuǎn)不能被刪除 d) 以上三種說法都不對3. 下列敘述中正確的是( b )a) 有一個以上根結(jié)點的數(shù)據(jù)結(jié)構(gòu)不一定是非線性結(jié)構(gòu)b) 只有一個根結(jié)點的數(shù)據(jù)結(jié)構(gòu)不一定是線性結(jié)構(gòu)c) 循環(huán)鏈表是非線性結(jié)構(gòu)d) 雙向鏈表是非線性結(jié)構(gòu)4. 支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是(

24、 a )a) 棧 b) 樹 c) 隊列 d) 二叉樹5. 某二叉樹有5個度為2的結(jié)點，則該二叉樹中的葉子結(jié)點數(shù)是( c )a）10 b）8 c）6 d）4提示：在任意二叉樹中，若度為0的結(jié)點(即葉子結(jié)點)的個數(shù)為n0，度為2的結(jié)點的個數(shù)為n2，則：n0= n2+1 即 n0(葉子結(jié)點數(shù))=5+1=66. 某二叉樹共有7個結(jié)點，其中葉子結(jié)點只有1個，則該二叉樹的深度為(假設(shè)根結(jié)點在第一層)( d )a) 3 b) 4 c) 6 d)77. 下列排序方法中，最壞情況下比較次數(shù)最少的是( d )a）冒泡排序 b）簡單選擇排序 c）直接插入排序 d）堆排序8. 下列敘述中正確的是( a )a) 對長度

25、為n的有序鏈表進行查找，最壞的情況下需要的比較次數(shù)為nb) 對長度為n的有序鏈表進行對分查找，最壞的情況下需要的比較次數(shù)為（n/2）c) 對長度為n的有序鏈表進行對分查找，最壞的情況下需要的比較次數(shù)為(log2n)d) 對長度為n的有序鏈表進行對分查找，最壞的情況下需要的比較次數(shù)為(nlog2n)(二) 填空題1. 假設(shè)用一個長度為50的數(shù)組（數(shù)組元素的下標(biāo)從0到49）作為棧的存儲空間，棧底指針bottom指向棧底元素，棧頂指針top指向棧頂元素，如果bottom=49,top=30(數(shù)組下標(biāo))，則棧中具有_個元素。 答案：202. 一個隊列的初始狀態(tài)為空?，F(xiàn)將元素a、b、c、d、e、f、5、

26、4、3、2、1一次入隊，然后再一次退隊，則元素退隊的順序為_。答案：a、b、c、d、e、f、5、4、3、2、13. 設(shè)某循環(huán)隊列的容量為50，如果頭指針front=45(指向隊頭元素的前一個位置)，尾指針rear=10（指向隊尾元素），則該循環(huán)隊列中共有_個元素。答案：154. 設(shè)二叉樹如下：abcdefgh對該二叉樹進行后序遍歷的結(jié)果為_。答案：e、d、b、g、h、f、c、a5. 一棵二叉樹的中序遍歷結(jié)果為dbeafc，前序遍歷結(jié)果為abdecf，則后序遍歷結(jié)果為_。答案：debfca6. 有序線性表能進行二分查找的前提是該線性表必須是_存儲。答案：順序二、軟件工程基礎(chǔ)計算機軟件是計算機系統(tǒng)

27、中與硬件相互依存的另一部分，是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。軟件由兩部分組成：一是機器可執(zhí)行的程序和數(shù)據(jù)；二是機器不可執(zhí)行的，與軟件開發(fā)、運行、維護、使用等有關(guān)的文檔。軟件的分類 軟件按功能可以分為：應(yīng)用軟件、系統(tǒng)軟件、支撐軟件(或工具軟件)。 應(yīng)用軟件：是為解決特定領(lǐng)域的應(yīng)用而開發(fā)的軟件。 系統(tǒng)軟件：是計算機管理自身資源，提高計算機使用效率并為計算機用戶提供各種服務(wù)的軟件。支撐軟件：是介于系統(tǒng)軟件和應(yīng)用軟件之間，協(xié)助用戶開發(fā)軟件的工具性軟件。軟件生命周期通常將軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的過程稱為軟件生命周期。參見下圖： 結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析的常用工具：數(shù)據(jù)流圖(d

28、fd)：是描述數(shù)據(jù)處理過程的工具，是需求理解的邏輯模型的圖形表示，它直接支持系統(tǒng)的功能建模。數(shù)據(jù)字典(dd)：是結(jié)構(gòu)化分析方法的核心。判定樹判定表結(jié)構(gòu)化設(shè)計方法常見的過程設(shè)計工具：圖形工具：程序流程圖，n-s圖，pad圖(問題分析圖)，hipo表格工具：判定表。語言工具：pdl(偽碼)軟件設(shè)計的基本原理 1) 抽象：是一種思維工具，就是把事物本質(zhì)的共同特性提取出來而不考慮其他細(xì)節(jié)。 2) 模塊化：是指把一個待開發(fā)的軟件分解成若干小的簡單的部分。如高級語言中的過程、函數(shù)、子程序等。每個模塊可以完成一個特定的子功能，各個模塊可以按一定的方法組裝起來成為一個整體，從而實現(xiàn)整個系統(tǒng)的功能。 3) 信息

29、隱蔽：是指在一個模塊內(nèi)包含的信息(過程或數(shù)據(jù))，對于不需要這些信息的其他模塊來說是不能訪問的。4) 模塊獨立性：是指每個模塊只完成系統(tǒng)要求的獨立的子功能，并且與其他模塊的聯(lián)系最少且接口簡單。模塊的獨立程度是評價設(shè)計好壞的重要度量標(biāo)準(zhǔn)。衡量軟件的模塊獨立性使用耦合性和內(nèi)聚性兩個定性的度量標(biāo)準(zhǔn)。內(nèi)聚性：是一個模塊內(nèi)部各個元素間彼此結(jié)合的緊密程度的度量。內(nèi)聚是從功能角度來度量模塊內(nèi)的聯(lián)系。內(nèi)聚性是信息隱蔽和局部化概念的自然擴展。一個模塊的內(nèi)聚性越強則該模塊的模塊獨立性越強。作為軟件結(jié)構(gòu)設(shè)計的設(shè)計原則，要求每一個模塊的內(nèi)部都具有很強的內(nèi)聚性，它的各個組成部分彼此都密切相關(guān)。耦合性：耦合性是模塊間相互連

30、接的緊密程度的度量。一個模塊與其他模塊的耦合性越強則該模塊的模塊獨立性越弱。原則上講，模塊化設(shè)計總是希望模塊間的耦合表現(xiàn)為非直接耦合方式。但是，由于問題所固有的復(fù)雜性和結(jié)構(gòu)化設(shè)計的原則，非直接耦合往往是不存在的。耦合性與內(nèi)聚性是模塊獨立性的兩個定性標(biāo)準(zhǔn)，耦合性與內(nèi)聚性是相互聯(lián)系的。在程序結(jié)構(gòu)中，各模塊的內(nèi)聚性越強，則耦合性越弱。一般優(yōu)秀的軟件設(shè)計，應(yīng)盡量做到高內(nèi)聚，低耦合，即減弱模塊之間的耦合性和提高模塊內(nèi)的的內(nèi)聚性，有利于提高模塊的獨立性。軟件測試軟件測試是在軟件投入運行前對軟件需求、設(shè)計、編碼的最后審核。軟件測試是為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程。軟件測試應(yīng)當(dāng)制定明確的測試計劃并按計劃執(zhí)行。軟

31、件測試的目的：是發(fā)現(xiàn)錯誤。軟件測試方法和技術(shù)：若從是否需要執(zhí)行被測軟件的角度，可以分為靜態(tài)測試和動態(tài)測試方法。若按照功能劃分可以分為白盒測試和黑盒測試方法。靜態(tài)測試：包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量等。靜態(tài)測試不實際運行軟件，主要通過人工進行。動態(tài)測試：是基于計算機的測試，是為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程。需要精心設(shè)計一批測試用例，并利用這些測試用例去運行程序，以發(fā)現(xiàn)程序錯誤的過程。測試用例的格式為： (輸入值集),(輸出值集)白盒測試：也稱結(jié)構(gòu)測試或邏輯驅(qū)動測試。它是根據(jù)軟件產(chǎn)品的內(nèi)部工作過程，檢查內(nèi)部成分，以確認(rèn)每種內(nèi)部操作符合設(shè)計規(guī)格要求。白盒測試把測試對象看作一個打開的盒子，允許

32、測試人員利用程序內(nèi)部的邏輯結(jié)構(gòu)及有關(guān)信息來設(shè)計或選擇測試用例，對程序所有的邏輯路徑進行測試。通過在不同點檢查程序的狀態(tài)來了解實際的運行狀態(tài)是否與預(yù)期的一致。所以，白盒測試是在程序內(nèi)部進行，主要用于完成軟件內(nèi)部操作的驗證。白盒測試的主要方法有邏輯覆蓋、基本路徑測試等。黑盒測試：也稱功能測試或數(shù)據(jù)驅(qū)動測試。黑盒測試是對軟件已經(jīng)實現(xiàn)的功能是否滿足需求進行測試和驗證。黑盒測試完全不考慮程序內(nèi)部的邏輯結(jié)構(gòu)和內(nèi)部特征，只依據(jù)程序的需求和功能規(guī)格說明，檢查程序的功能是否符合它的功能說明。所以，黑盒測試是在軟件接口處進行，完成功能驗證。黑盒測試只檢查程序功能是否按照需求規(guī)格說明書的規(guī)定正常使用，程序是否能適當(dāng)

33、地接收輸入數(shù)據(jù)而產(chǎn)生正確的輸出信息，并且保持外部信息(如數(shù)據(jù)庫或文件)的完整性。黑盒測試主要診斷功能不對或遺漏、界面錯誤、數(shù)據(jù)結(jié)構(gòu)或外部數(shù)據(jù)庫訪問錯誤、性能錯誤、初始化和終止條件錯誤。黑盒測試方法主要有等價類劃分法、邊界值分析法、錯誤推測法、因果圖等，主要用于軟件確認(rèn)測試。程序調(diào)試在對程序進行了成功的測試之后，將進入程序調(diào)試(通常稱debug，即排錯)。程序調(diào)試的任務(wù)是診斷和改正程序中的錯誤。它與軟件測試不同，軟件測試是盡可能多地發(fā)現(xiàn)軟件中的錯誤，并找出軟件錯誤的具體位置。軟件測試貫穿整個軟件生命期，調(diào)試主要在開發(fā)階段。習(xí)題：（一）選擇題(單選)1. 軟件按功能可以分為：應(yīng)用軟件、系統(tǒng)軟件和支

34、撐軟件（或工具軟件）。下面屬于應(yīng)用軟件的是( c )a) 編譯程序 b) 操作系統(tǒng) c) 教務(wù)管理系統(tǒng) d) 匯編程序2. 軟件按功能可分為：應(yīng)用軟件、系統(tǒng)軟件、和支撐軟件（或工具軟件）。下面屬于系統(tǒng)軟件的是( b )a) 編輯軟件 b)操作系統(tǒng) c)教務(wù)管理系統(tǒng) d)瀏覽器、3. 軟件(程序)調(diào)試的任務(wù)是( a )a) 診斷和改正程序中的錯誤 b) 盡可能多的發(fā)現(xiàn)程序中的錯誤c) 發(fā)現(xiàn)并改正程序中的所有錯誤 d) 確定程序中錯誤的性質(zhì)4. 下面敘述中錯誤的是( a )a) 軟件測試的目的是發(fā)現(xiàn)錯誤并改正錯誤b) 對被調(diào)試的程序進行“錯誤定位”是程序調(diào)試的必要步驟c) 程序調(diào)試通常也稱為deb

35、ugd) 軟件測試應(yīng)嚴(yán)格執(zhí)行測試計劃，排除測試的隨意性5. 耦合性和內(nèi)聚性是對模塊獨立性度量的兩個標(biāo)準(zhǔn)。下列敘述中正確的是( b )a) 提高耦合性、降低內(nèi)聚性有利于提高模塊的獨立性b) 降低耦合性、提高內(nèi)聚性有利于提高模塊的獨立性c) 耦合性是指一個模塊內(nèi)部各個元素間彼此結(jié)合的緊密程度d) 內(nèi)聚性是指模塊間互相連接的緊密程度6. 數(shù)據(jù)流圖(dfd圖)是( c )a) 軟件概要設(shè)計的工具 b) 軟件詳細(xì)設(shè)計的工具c) 結(jié)構(gòu)化方法的需求分析工具 d) 面向?qū)ο蠓椒ǖ男枨蠓治龉ぞ?. 軟件生命周期可分為定義階段，開發(fā)階段和維護階段。詳細(xì)設(shè)計屬于( b )a) 定義階段 b) 開發(fā)階段 c) 維護階

36、段 d) 上述三個階段8. 在軟件開發(fā)中，需求分析階段產(chǎn)生的主要文檔是( d )a) 軟件集成測試計劃 b) 軟件詳細(xì)設(shè)計說明書 c) 用戶手冊 d) 軟件需求規(guī)格說明書9. 結(jié)構(gòu)化程序所要求的基本結(jié)構(gòu)不包括( b )a) 順序結(jié)構(gòu) b) goto跳轉(zhuǎn) c) 選擇(分支)結(jié)構(gòu) d) 重復(fù)(循環(huán))結(jié)構(gòu)10. 下面描述中錯誤的是( a )a) 系統(tǒng)總體結(jié)構(gòu)圖支持軟件系統(tǒng)的詳細(xì)設(shè)計b) 軟件設(shè)計是將軟件需求轉(zhuǎn)換為軟件表示的過程c) 數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫設(shè)計是軟件設(shè)計的任務(wù)之一d) pad圖是軟件詳細(xì)設(shè)計的表示工具(二) 填空題1. 軟件測試可分為白盒測試和黑盒測試。基本路徑測試屬于_測試。答案：白盒2.

37、 符合結(jié)構(gòu)化原則的三種基本控制結(jié)構(gòu)是：選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)和_。答案：順序結(jié)構(gòu)3. 軟件是_、數(shù)據(jù)和文檔的集合。答案：程序4. 對軟件設(shè)計的最小單位(模塊或程序單元)進行的測試通常為_測試。答案：單元 或 模塊三、數(shù)據(jù)庫設(shè)計基礎(chǔ)計算機應(yīng)用的三大領(lǐng)域：科學(xué)計算、數(shù)據(jù)處理、過程控制。數(shù)據(jù)庫系統(tǒng)的基本概念數(shù)據(jù)(data)：就是描述事物的符號記錄。數(shù)據(jù)庫(db)：是數(shù)據(jù)的集合，它具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個應(yīng)用程序所共享。數(shù)據(jù)庫中的數(shù)據(jù)具有“集成”、“共享”的特點。數(shù)據(jù)庫管理系統(tǒng)(dbms)：是數(shù)據(jù)庫的機構(gòu)，是一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫中的數(shù)據(jù)組織、數(shù)據(jù)操縱

38、、數(shù)據(jù)維護、控制及保護和數(shù)據(jù)服務(wù)等。數(shù)據(jù)庫管理系統(tǒng)是數(shù)據(jù)庫系統(tǒng)的核心。數(shù)據(jù)庫管理系統(tǒng)一般提供相應(yīng)的數(shù)據(jù)語言(data language)來完成相應(yīng)的功能：數(shù)據(jù)定義語言(ddl)：負(fù)責(zé)數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建。數(shù)據(jù)操縱語言(dml)：負(fù)責(zé)數(shù)據(jù)的操縱，包括查詢及增、刪、改等操作。數(shù)據(jù)控制語言(dcl)：負(fù)責(zé)數(shù)據(jù)完整性、安全性的定義與檢查以及并發(fā)控制、故障恢復(fù)等功能，包括系統(tǒng)初啟程序、文件讀寫與維護程序、存取路徑管理程序、緩沖區(qū)管理程序、安全性控制程序、完整性檢查程序、并發(fā)控制程序、事務(wù)管理程序、運行日志管理程序、數(shù)據(jù)庫恢復(fù)程序等。數(shù)據(jù)庫管理員(dba)：由于數(shù)據(jù)庫的共享性，因此對數(shù)據(jù)庫的

39、規(guī)劃、設(shè)計、維護、監(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ù)庫應(yīng)用系統(tǒng)(dbas)：是數(shù)據(jù)庫系統(tǒng)再加上應(yīng)用軟件及應(yīng)用界面這三者所組成。e-r模型該模型將現(xiàn)實世界的要求轉(zhuǎn)化成實體、聯(lián)系、屬性等幾個基本概念，以及它們間的兩種基本聯(lián)接關(guān)系，并且可以用一種圖非常直觀地表示出來。下面是e-r模型的基本概念。目前較為有名的概念模型有e-r模型、擴充的e-r模型、面向?qū)ο竽Ｐ图爸^詞模型等。實體：現(xiàn)實世界中的事物可以抽象成為實體。實體是概念世界中的

40、基本單位，它們是客觀存在的且又相互區(qū)別的事物。凡是有共性的實體可組成一個集合稱實體集。如學(xué)生a和學(xué)生b，他們都是實體，他們又都是學(xué)生，從而組成一個學(xué)生實體集。 屬性：現(xiàn)實世界中的事物均有一些特性，這些特性可以用屬性來表示。屬性刻畫了實體的特征。一個實體往往可以有若干個屬性。 聯(lián)系：現(xiàn)實世界中事物間的關(guān)聯(lián)稱為聯(lián)系。在概念世界中聯(lián)系反映了實體集間的一定關(guān)系。如工人與設(shè)備間的操作關(guān)系，上、下級間的領(lǐng)導(dǎo)關(guān)系等。 實體集間的聯(lián)系有多種，就實體集的個數(shù)而言有： 1) 兩個實體集間的聯(lián)系。2) 多個實體集間的聯(lián)系。3) 一個實體集內(nèi)部的聯(lián)系：是一個實體集內(nèi)的不同實體間的聯(lián)系。實體集間聯(lián)系的個數(shù)可以是單個也可

41、以是多個，包括：一對一的聯(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)接關(guān)系。 1) 實體集表示法 用矩形表示實體集，在矩形內(nèi)寫上該實體集的名字。如實體集學(xué)生(student)、課程(course)可表示為： 2) 屬性表示法 用橢圓形表示屬性，在橢圓形內(nèi)寫上該屬性的名稱。如學(xué)生有屬性：學(xué)號

42、(s#)、姓名(sn)及年齡(sa)，可表示為： 3) 聯(lián)系表示法 用菱形表示聯(lián)系，在菱形內(nèi)寫上聯(lián)系名。如學(xué)生與課程間的聯(lián)系sc，可表示為： 上面是三個基本概念分別用三種幾何圖形表示。下面是它們之間的聯(lián)接關(guān)系的圖形表示。 4) 實體集或聯(lián)系與屬性間的聯(lián)接關(guān)系屬性依附于實體集，屬性也依附于聯(lián)系，因此它們之間分別有聯(lián)接關(guān)系。參見下圖： 其中：c#(課程號)、cn(課程名)、p#(預(yù)修課號) 5) 實體集與聯(lián)系間的聯(lián)接關(guān)系 如下圖表示實體集與聯(lián)系間的聯(lián)接關(guān)系： 還可以在線段邊上注明其對應(yīng)的函數(shù)關(guān)系，如1:1、1:n、n:m等。下圖表示student與course間有多對多聯(lián)系： 兩個實體集間聯(lián)系叫二

43、元聯(lián)系，多個實體集間聯(lián)系叫多元聯(lián)系。下圖聯(lián)系fpu是一種三元聯(lián)系(工廠、產(chǎn)品與用戶間的聯(lián)系)： 下面是實體間多種聯(lián)系圖： (a)圖：公司職工(enployee)間上、下級管理(manage)的聯(lián)系。即一個實體集內(nèi)部可以有多種聯(lián)系。(b)圖：教師(t)與學(xué)生(s)之間可以有教學(xué)(e)聯(lián)系也可以有管理(m)聯(lián)系。即實體集間可以有多種聯(lián)系。 下面是e-r圖的一個實例圖 關(guān)系模型關(guān)系模型采用二維表來表示，簡稱表。二維表由表框架(frame)及表的元組(tuple)組成。表框架由n個命名的屬性(attribute)組成，n稱為屬性元數(shù)(arity)。每個屬性有一個取值范圍，稱為值域(domain)。表框

44、架對應(yīng)了關(guān)系的模式，即類型的概念。在表框架中按行可以存放數(shù)據(jù)，每行數(shù)據(jù)稱為元組，實際上，一個元組是由n個元組分量所組成，每個元組分量是表框架中每個屬性的投影值。一個表框架可以存放m個元組，m稱為表的基數(shù)(cardinality)。一個n元表框架及框架內(nèi)m個元組構(gòu)成了一個完整的二維表。 關(guān)系框架與關(guān)系元組構(gòu)成了一個關(guān)系。一個語義相關(guān)的關(guān)系集合構(gòu)成一個關(guān)系數(shù)據(jù)庫。關(guān)系的框架稱為關(guān)系模式，而語義相關(guān)的關(guān)系模式集合構(gòu)成了關(guān)系數(shù)據(jù)庫模式。 滿足下面7個性質(zhì)的二維表稱為關(guān)系(relation)： 1) 元組個數(shù)有限性：二維表中元組個數(shù)是有限的。2) 元組的惟一性：二維表中元組均不相同。3) 元組的次序無關(guān)性：二維表中元組的次序可以任意交換。4) 元組分量的原子性：二維表中元組的分量是不可分割的基本數(shù)據(jù)項。5) 屬性名惟一性：二維表中屬性名各不相同。6) 屬性的次序無關(guān)性：二維表中屬性與次序無關(guān)，可任意交換。7) 分量值域的同一性：二維表屬性的分量具有與該屬性相同的值域。以二維表(關(guān)系)為基本結(jié)構(gòu)所建立的模型稱為關(guān)系模型。 在關(guān)系模型中的一個重要概念是鍵(key)或碼。鍵具有標(biāo)識元組、建立元組間聯(lián)系等重要作用。鍵或碼：在二維表中凡能惟一標(biāo)識元組的最小屬性集稱為該表的鍵或碼。候選鍵或候選碼：二維表中可能有