1、精心整理全國計算機二級公共基礎知識一、數據結構與算法數據結構指的是數據之間的相互關系，即數據的組織形式。數據結構用來反映一個數據的內部構成， 即一個數據由哪些成分構成、以什l I - 算法是解題的步驟，是指令的有限序列。它們規定了解決某一特定類型 問題的一系列運算，是對解題方案的準確與完整的描述。一個問題的解決方案要 以算法為基礎。；.； - -.V .、 V | 1.1概念介紹算法的時間復雜度：算法的時間復雜度 是指執行算法所需要的計算工作量。算法的工作量用算法所執行的基本運算次數來度量， 而算法所執行的基本運 算次數是問題規模的函數，即算法的工作量=f(n)其中n是問題的規模。例如，兩個n

2、階矩陣相乘所需要的基本運算（即兩個實數的乘法）次數為n3,即計算工作量為n3，也就是時間復雜度為n3o算法的空間復雜度：算法的空間復雜度一般是指執行這個算法所需要的內存空間。數據的邏輯結構數據元素相互之間的關系，稱為結構。:b I K y數據的邏輯結構：是指反映數據元素之間邏輯關系的數據結構。數據的存儲結構數據的存儲結構：是數據的邏輯結構在計算機存儲空間中的存放形式。也稱 數據的物理結構。各數據元素在計算機存儲空間中的位置關系與它們的邏輯關系不一定是相同的。同一種數據的邏輯結構可以根據需要表示成任意一種或幾種不同的存儲結 構。窩養沐I數據的順序存儲方式：是將邏輯上相鄰的結點存儲在物理位置上亦

3、相鄰的存儲單元里。也就是將所有存儲結點相繼存入在一個連續相鄰的存儲區 里。數據的鏈式存儲方式：是在存儲每個結點信息的同時，增加一個指 針來表示結點間的邏輯關系。該方式不要求邏輯上相鄰結點在物理位置上亦相 鄰，結點間的邏輯關系是由附加的指針字段表示的。因此，鏈式存儲結構中的每個結點都由兩部分組成：一部分用于存儲結點本身的信息，稱為 數據域；另一部分用于存儲該結點的后繼結點（或前驅結點）的存儲單元地址，稱為 指針域。指針域可以包含一個或多個指針，這由結點之間的關系所決定。線性結構和非線性結構如果在一個線性結構中，一個數據元素都沒有，則稱該數據結構為空數據結構。線性結構的邏輯特征：在一個非空的數據結

4、構中，除第一個數據元 *11 / -素只有一個后繼沒有前驅、最后一個數據元素只有一個前驅沒有后繼外，其他的 、 t I :鼻每一個數據元素僅有一個前驅和一個后繼。線性結構也稱為線性表0:- sI 0)棵互不相交的樹的集合。刪去一棵樹的根，就得到一個森 林；反之，加上一個結點作樹根，森林就變為一棵樹。1.4.2二叉樹心Vl| I1,1,(1) 二叉樹的特點 非空二叉樹只有一個根結點。 二叉樹中的每個結點，最多有兩棵子樹，分另稱為該結點的左子樹與右子樹。當一個結點即沒有左子樹也沒有右子樹時，該結點就是葉子結點。在下面的 圖中，左面是只有根結點的二叉樹，右面是深度為4的二叉樹：(2) 滿二叉樹與完全

5、二叉樹1)滿二叉樹：滿二叉樹是指除最后一層外，每一層上的所有結點都有兩個子結點。就是說，在滿二叉樹中，每一層上的結點數都達到最大值，即在滿二叉樹的第k層上有2i-1(k 1)個結點，且深度為k的滿二叉樹有2k-1(k 1)個結 I點。在下圖中分別是深度為2、3、4的滿二叉樹：滿二叉樹中不存在度數為1的結點，每個分支結點均有兩棵深度相同的子樹，且葉子結點都在最下一層。2)完全二叉樹：若一棵二叉樹最多只有最下面的兩層上結點的度數可以小于2 ,并且最下一層上的所有結點都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉 樹。在下圖的4棵二叉樹中，分別是深度為3和4的完全二叉樹：滿二叉樹是完全二叉樹

6、，完全二叉樹不一定是滿二叉樹。在滿二叉樹的最下一層上，從最右邊開始連續刪去若干結點后得到的二叉樹仍然、 I i *是一棵完全二叉樹。在完全二叉樹中，若某個結點沒有左子結點，則它一定沒有右子結點，即該結點必是葉子結點。(3)二叉樹的性質.1假設定義根結點的層數為1(注意：有些資料中規定根結點的層數為 0)。性質1：在二叉樹的第i層上，最多有2i-1(i 1)個結點。性質2：深度為k的二叉樹最多有2k-1(k 1)個結點。;.； - -.V | 、性質3 :在任意二叉樹中，若度為0的結點(即葉子結點)的個數為no，度為2的結點的個數為n2，貝U： n0=n2+1(對于完全二叉樹還有如下屬性)性質4

7、：具有n個結點的完全二叉樹，其深度為log2n+1。注：Iog2n表示取Iog2n的整數部分。性質5:如果將一棵有n個結點的完全二叉樹自頂 向下、同一層自左向右連續給結點編號1、2、3、n，則對于任意結點i(1 i 1，則該結點的父結點編號為lnt(i/2) 。也可表示成i/2，都 表示取整數。2）如果2in,則結點i無左子結點，顯然也沒有右子結點，是葉子結點。 如果2iwn,貝U結點i的左子結點是編號為2i的結點。3）如果2i+1n,則結點i無右子結點。如果2i+1II .（ I內容動畫。在最壞情況下，直接選擇排序比較次數為n（n-1）/2。（2）堆排序希爾排序的基本思想：請查看相關資料。在

8、最壞情況下，堆排序比較次數為O（nlog2n）。習題：;/ - -.V ”. | I （一）選擇題（單選）1. 下列敘述中正確的是（D）A ）棧是“先進先出”的線性表B ）隊列是“先進后出”的線性表C）循環隊列是非線性結構D）有序線性表既可以采用順序存儲結構，也可以采用鏈式存儲結構2. 下列關于棧的敘述中正確的是 （A）A）棧頂元素最先被刪除 B）棧頂元素最后才能被刪除C）棧底元素永遠不能被刪除 D）以上三種說法都不對3. 下列敘述中正確的是（B）A）有一個以上根結點的數據結構不一定是非線性結構B）只有一個根結點的數據結構不一定是線性結構C）循環鏈表是非線性結構D）雙向鏈表是非線性結構4. 支

9、持子程序調用的數據結構是 （A）A）棧B）樹C）隊列D）二叉樹5. 某二叉樹有5個度為2的結點，則該二叉樹中的葉子結點數是（C）A）10B）8 C）6D）4提示：在任意二叉樹中，若度為0的結點（即葉子結點）的個數為nO,度為2的結點的個數為n2，則：n0=n2+1即n0（葉子結點數）=5+1=66. 某二叉樹共有7個結點，其中葉子結點只有1個，則該二叉樹的深度為（假設根結點在第 一層）（D）A）3B）4C）6D）77. 下列排序方法中，最壞情況下比較次數最少的是（D）A ）冒泡排序B）簡單選擇排序 C）直接插入排序 D）堆排序8. 下列敘述中正確的是（A）A）對長度為n的有序鏈表進行查找，最壞

10、的情況下需要的比較次數為nB）對長度為n的有序鏈表進行對分查找，最壞的情況下需要的比較次數為（n/2）C）對長度為n的有序鏈表進行對分查找，最壞的情況下需要的比較次數為（log?n）D）對長度為n的有序鏈表進行對分查找，最壞的情況下需要的比較次數為（nlog2n）（二）填空題1假設用一個長度為50的數組（數組元素的下標從0到49）作為棧的存儲空間，棧底指針bottom指向棧底元素，棧頂指針top指向棧頂元素，如果 bottom=49,top=30（數組下標），則棧中具有個元素。答案：202. 一個隊列的初始狀態為空。現將元素A、B C、D E、F、5、4、3、2、1 一次入隊，然后再一次退隊，

11、則元素退隊的順序為 。答案：A B、C、D、E、F、5、4、3、2、13. 設某循環隊列的容量為50,如果頭指針front=45（指向隊頭元素的前一個位置 ），尾指針rear=10 （指向隊尾元素），則該循環隊列中共有個元素。答案：154. 設二叉樹如下：對該二叉樹進行后序遍歷的結果為 答案：E、D、B、G H F、C A 5. 一棵二叉樹的中序遍歷結果為 DBEAFC，前序遍歷結果為 ABDECF，則后序遍歷結果為。答案：DEBFCA6. 有序線性表能進行二分查找的前提是該線性表必須是 存儲。答案：順序二、軟件工程基礎計算機軟件是計算機系統中與硬件相互依存的另一部分，是包括程序、數據及相關文

12、檔的完整集合。軟件由兩部分組成：一是機器可執行的程序和數據；二是機器不可執行的， 與軟件開發、運行、維護、使用等有關的文檔。軟件的分類軟件按功能可以分為：應用軟件、系統軟件、支撐軟件 (或工具軟件)。 應用軟件：是為解決特定領域的應用而開發的軟件。系統軟件：是計算機管理自身資源，提高計算機使用效率并為計算機用戶提供各 種服務的軟件。支撐軟件：是介于系統軟件和應用軟件之間， 協助用戶開發軟件的工具性軟 件。 - ； ； 、: / Vj- J7技汽i,飛該模型將現實世界的要求轉化成實體、聯系、屬性等幾個基本概念，以及它 們間的兩種基本聯接關系，并且可以用一種圖非常直觀地表示出來。下面是E-R模型的

13、基本概念。目前較為有名的概念模型有 E-R模型、擴充的E-R模型、面向對象模型及 謂詞模型等。實體：現實世界中的事物可以抽象成為實體。實體是概念世界中的基本單位， 它們是客觀存在的且又相互區別的事物。凡是有共性的實體可組成一個集合稱實 體集。如學生A和學生B，他們都是實體，他們又都是學生，從而組成一個學 生實體集。屬性：現實世界中的事物均有一些特性，這些特性可以用屬性來表示。屬性刻畫 了實體的特征。一個實體往往可以有若干個屬性。聯系：現實世界中事物間的關聯稱為聯系。在概念世界中聯系反映了實體集間的一定關系。如工人與設備間的操作關系，上、下級間的領導關系等。實體集間的聯系有多種，就實體集的個數而

14、言有：1）兩個實體集間的聯系。2）多個實體集間的聯系。3）個實體集內部的聯系：是一個實體集內的不同實體間的聯系。實體集間聯系的個數可以是單個也可以是多個，包括：一對一的聯系，簡記為1:1、 t I :*一對多或多對一的聯系，簡記為 1：M或M:1（其中M也可以小寫） 多對多的聯系，簡記為 M:N或m:nE-R模型由上面三個基本概念組成。由實體、聯系、屬性三者結合起來才能表示 現實世界。E-R圖：E-R模型可以用一種非常直觀的圖的形式表示，這種圖稱為E-R圖。在E-R圖中我們分別用下面不同的幾何圖形表示 E-R模型中的三個概念與兩個聯接 關系。1）實體集表示法用矩形表示實體集，在矩形內寫上該實體

15、集的名字。如實體集學生（student）、課程（course）可表示為：2）屬性表示法用橢圓形表示屬性，在橢圓形內寫上該屬性的名稱。如學生有屬性：學號（S#）、姓名（Sn）及年齡（Sa），可表示為：3）聯系表示法用菱形表示聯系，在菱形內寫上聯系名。如學生與課程間的聯系SC,可表示為：上面是三個基本概念分別用三種幾何圖形表示。 下面是它們之間的聯接關系的圖 形表示。4）實體集或聯系與屬性間的聯接關系屬性依附于實體集，屬性也依附于聯系，因此它們之間分別有聯接關系。參見下圖：其中：C#(課程號)、Cn(課程名)、P#(預修課號)5) 實體集與聯系間的聯接關系如下圖表示實體集與聯系間的聯接關系：還可以

16、在線段邊上注明其對應的函數關系， 如1:1、1:n、n:m等。下圖表示student 與course間有多對多聯系：兩個實體集間聯系叫二元聯系，多個實體集間聯系叫多元聯系。下圖聯系FPU是一種三元聯系(工廠、產品與用戶間的聯系)：下面是實體間多種聯系圖：(a)圖：公司職工(enployee)間上、下級管理(manage)的聯系。即一個實體集內部 可以有多種聯系。(b)圖：教師(T)與學生(S)之間可以有教學(E)聯系也可以有管理(M)聯系。即 實體集間可以有多種聯系。下面是E-R圖的一個實例圖 /I I *11 5.11 、1弋汽、汎*.I關系模型關系模型采用二維表來表示，簡稱表。二維表由表框

17、架(Frame)及表的元組(Tuple)組成。表框架由n個命名的屬性 ;.； - -.V | (Attribute)組成，n稱為屬性元數(Arity)。每個屬性有一個取值范圍，稱為值域 (Doma in)。表框架對應了關系的模式，即類型的概念。.- . . /. / I / -在表框架中按行可以存放數據，每行數據稱為元組，實際上，一個元組是由 n個元組分量所組成，每個元組分量是表框架中每個屬性的投影值。一個表框架 可以存放m個元組，m稱為表的基數(Cardinality)。一個n元表框架及框架內m個元組構成了一個完整的二維表。關系框架與關系元組構成了一個關系。一個語義相關的關系集合構成一個關系

18、 數據庫。關系的框架稱為關系模式，而語義相關的關系模式集合構成了關系數據 庫模式。滿足下面7個性質的二維表稱為關系(Relation):1) 元組個數有限性：二維表中元組個數是有限的。2）元組的惟一性：二維表中元組均不相同。3）元組的次序無關性：二維表中元組的次序可以任意交換。4）元組分量的原子性：二維表中元組的分量是不可分割的基本數據項。5）屬性名惟一性：二維表中屬性名各不相同。6）屬性的次序無關性：二維表中屬性與次序無關，可任意交換。7）分量值域的同一性：二維表屬性的分量具有與該屬性相同的值域。以二維表（關系）為基本結構所建立的模型稱為關系模型。在關系模型中的一個重要概念是鍵（Key）或碼

19、。鍵具有標識元組、建立元組間聯 系等重要作用。鍵或碼：在二維表中凡能惟一標識元組的最小屬性集稱為該表的鍵或碼。候選鍵或候選碼：二維表中可能有若干個鍵，它們稱為該表的候選鍵k II I 1.1* I j（Ca ndidataKey）或候選碼。主鍵或主碼：從二維表的所有候選鍵中選取一個作為用戶使用的鍵，稱為主鍵（PrimaryKey）或主碼。一般主鍵也簡稱為鍵或碼。外鍵或外碼：表A中的某屬性集是某表B的鍵，則稱該屬性集為A的外鍵 （Foreig nKey）或外碼。表中一定要有鍵，因為如果表中所有屬性的子集均不是鍵，則表中屬性的全集必為鍵（稱為全鍵），因此也一定有主鍵。在關系元組的分量中允許出現空值

20、（NullValue）以表示信息空缺。空值用于表 示未知的值或不可能出現的值，一般用 NULL表示。一般關系數據庫系統都支 持空值，但是有兩個限制：關系的主鍵中不允許出現空值，因為如主鍵為空值則 失去了其元組標識的作用；需要定義有關空值的運算。V* V J關系代數關第代數是關于關系數據庫的理論。數據庫設計與管理數據庫設計是數據庫應用的核心。數據庫設計的四個階段，參見下圖：從E-R圖向關系模式轉換參見下表：習題:（一）選擇題（單選）1. 數據庫應用系統中的核心問題是（A）A）數據庫設計B）數據庫系統設計 C）數據庫維護D）數據庫管理員培訓2. 將E-R圖轉換為關系模式時，實體和聯系都可以表示為（C）A）屬性B）鍵C）關系D）域3. 負責數據庫中查詢操作的數據庫語言是（C）A）數據定義語言B）數據管理語言C）數據操縱語言D）數據控制語言4. 數據庫管理系統中負責數據模式定義的語言是（A）A）數據定義語言B）數據管理語言C）數據操縱語言D）數據控制語言5. 在學生管理的關系數據庫中，存取一個學生信息的數據單位是（D）A）文件B）數據庫C）字段D）記錄6. 定義無符號整數類為Ulnt，下面可以作為類 Ulnt