1、全國計算機等級考試二級公共基礎知識考點公共基礎知識 基本要求 1掌握算法的基本概念。 2掌握基本數據結構及其操作。 3掌握基本排序和查找算法。 4掌握逐步求精的結構化程序設計方法。 5掌握軟件工程的基本方法，具有初步應用相關技術進行軟件開發的能力。 6掌握數據庫的基本知識，了解關系數據庫的設計。 考試內容 一、基本數據結構與算法 1算法的基本概念；算法復雜度的概念和意義(時間復雜度與空間復雜度）。 2數據結構的定義；數據的邏輯結構與存儲結構；數據結構的圖形表示；線性結構與非線性結構的概念。 3線性表的定義；線性表的順序存儲結構及其插入與刪除運算。 4棧和隊列的定義；棧和隊列的順序存儲結構及其基

2、本運算。 5線性單鏈表、雙向鏈表與循環鏈表的結構及其基本運算。 6樹的基本概念；二叉樹的定義及其存儲結構；二叉樹的前序、中序和后序遍歷。 7順序查找與二分法查找算法；基本排序算法(交換類排序，選擇類排序，插入類排序)。 二、數據庫設計基礎 1數據庫的基本概念：數據庫，數據庫管理系統，數據庫系統。 2數據模型，實體聯系模型及ER圖，從ER圖導出關系數據模型。 3關系代數運算，包括集合運算及選擇、投影、連接運算，數據庫規范化理論。 4數據庫設計方法和步驟：需求分析、概念設計、邏輯設計和物理設計的相關策略三、程序設計基礎 1程序設計方法與風格 2結構化程序設計。 3面向對象的程序設計方法，對象，方法

3、，屬性及繼承與多態性。 四、軟件工程基礎 1軟件工程基本概念，軟件生命周期概念，軟件工具與軟件開發環境。 2結構化分析方法，數據流圖，數據字典，軟件需求規格說明書。 3結構化設計方法，總體設計與詳細設計。 4軟件測試的方法，白盒測試與黑盒測試，測試用例設計，軟件測試的實施，單元測試、集成測試和系統測試。 5程序的調試，靜態調試與動態調試。 全國計算機等級考試二級公共基礎講義之一算法與數據結構本章應考點撥：本章內容在筆試中會出現5-6個題目，是公共基礎知識部分出題量比較多的一章，所占分值也比較大，約10分。1.1算法1、算法的基本概念：是指解題方案的準確而完整的描述。 算法不等于程序，也不等于計

4、算機方法，程序的編制不可能優于算法的設計。 2、算法的基本特征（1）可行性 針對實際問題而設計的算法，執行后能夠得到滿意的結果。（2）確定性 每一條指令的含義明確，無二義性。并且在任何條件下，算法只有唯一的一條執行路徑，即相同的輸入只能得出相同的輸出。（3）有窮性 算法必須在有限的時間內完成。有兩重含義，一是算法中的操作步驟為有限個，二是每個步驟都能在有限時間內完成。（4）擁有足夠的情報 算法中各種運算總是要施加到各個運算對象上，而這些運算對象又可能具有某種初始狀態，這就是算法執行的起點或依據。因此，一個算法執行的結果總是與輸入的初始數據有關，不同的輸入將會有不同的結果輸出。當輸入不夠或輸入錯

5、誤時，算法將無法執行或執行有錯。一般說來，當算法擁有足夠的情報時，此算法才是有效的；而當提供的情報不夠時，算法可能無效。*：綜上所述，所謂算法，是一組嚴謹地定義運算順序的規則，并且每一個規則都是有效的，且是明確的，此順序將在有限的次數下終止。3、算法復雜度主要包括時間復雜度和空間復雜度。（1）算法時間復雜度是指執行算法所需要的計算工作量，可以用執行算法的過程中所需基本運算的執行次數來度量。同一個算法用不同的語言實現，或者用不同的編譯程序進行編譯，或者在不同的計算機上運行，效率均不同。這表明使用絕對的時間單位衡量算法的效率是不合適的。撇開這些與計算機硬件、軟件有關的因素，可以認為一個特定算法&q

6、uot;運行工作量"的大小，只依賴于問題的規模（通常用整數n表示），它是問題規模的函數。即算法的工作量=f（n）（2）算法空間復雜度是指執行這個算法所需要的內存空間。一個算法所占用的存儲空間包括算法程序所占的空間、輸入的初始數據所占的存儲空間以及算法執行過程中所需要的額外空間。其中額外空間包括算法程序執行過程中的工作單元以及某種數據結構所需要的附加存儲空間。如果額外空間量相對于問題規模來說是常數，則稱該算法是原地工作的。在許多實際問題中，為了減少算法所占的存儲空間，通常采用壓縮存儲技術，以便盡量減少不必要的額外空間?！舅惴曨}】1、算法的時間復雜度是指 CA) 執行算法程序所需要的時

7、間 B) 算法程序的長度C) 算法執行過程中所需要的基本運算次數 D) 算法程序中的指令條數2、算法的基本特征是可行性、確定性、 有窮性 和擁有足夠的情報。3、算法的空間復雜度是指 CA) 算法程序的長度 B) 算法程序中的指令條數C) 算法程序所占的存儲空間 D) 執行過程中所需要的存儲空間4、在計算機中，算法是指 BA) 加工方法 B) 解題方案的準確而完整的描述 C) 排序方法 D) 查詢方法5、算法的工作量大小和實現算法所需的存儲單元多少分別稱為算法的 【1】 時間復雜度和空間復雜度 1.2 數據結構的基本概念1、數據結構是指相互有關聯的數據元素的集合。2、數據結構主要研究和討論以下三

8、個方面的問題：（1）數據集合中各數據元素之間所固有的邏輯關系，即數據的邏輯結構。數據的邏輯結構有兩個要素：一是數據元素的集合；二是此集合上的關系，它反映了數據元素之間的前后件關系（2）在對數據進行處理時，各數據元素在計算機中的存儲關系，即數據的存儲結構。數據的邏輯結構在計算機存儲空間中的存放形式稱為數據的存儲結構（也稱數據的物理結構）由于數據元素在計算機存儲空間中的位置關系可能與邏輯關系不同，因此，為了表示存放在計算機存儲空間中的各數據元素之間的邏輯關系（即前后件關系），在數據的存儲結構中，不僅要存放各數據元素的信息，還需要存放各數據元素之間的前后件關系的信息。數據的存儲結構有順序、鏈接、索引

9、等。1）順序存儲。它是把邏輯上相鄰的結點存儲在物理位置相鄰的存儲單元里。由此得到的存儲表示稱為順序存儲結構。2）鏈接存儲。它不要求邏輯上相鄰的結點在物理位置上亦相鄰，結點間的邏輯關系是由附加的指針字段表示的。由此得到的存儲表示稱為鏈式存儲結構。3）索引存儲：除建立存儲結點信息外，還建立附加的索引表來標識結點的地址。同一種邏輯結構的數據可以采用不同的存儲結構，而采用不同的存儲結構，其數據處理的效率是不同的。因此，在進行數據處理時，選擇合適的存儲結構是很重要的。（3）對各種數據結構進行的運算。3、數據結構的圖形表示一個數據結構除了用二元關系表示外，還可以直觀地用圖形表示。在數據結構的圖形表示中，對

10、于數據集合D中的每一個數據元素用中間標有元素值的方框表示，一般稱之為數據結點，并簡稱為結點；為了進一步表示各數據元素之間的前后件關系，對于關系R中的每一個二元組，用一條有向線段從前件結點指向后件結點。4、根據數據結構中各數據元素之間前后件關系的復雜程度，數據結構分為兩大類型：線性結構和非線性結構。（1）線性結構（非空的數據結構）條件：v 有且只有一個根結點wx3 ；v 每一個結點最多有一個前件，也最多有一個后件。*：常見的線性結構有線性表（棧、隊列是線性表的特例）（2）非線性結構：不滿足線性結構條件的數據結構。*：常見的非線性結構有樹、二叉樹和圖等。【數據結構基本概念習題】1、根據數

11、據結構中各數據元素之間前后件關系的復雜程度，一般將數據結構分成A) 動態結構和靜態結構 B) 緊湊結構和非緊湊結構C) 線性結構和非線性結構 D) 內部結構和外部結構 2、數據結構包括數據的邏輯結構、數據的 【2】 以及對數據的操作運算。 存儲結構3、數據的基本單位是 【5】 。 數據元素4、下列敘述中，錯誤的是A) 數據的存儲結構與數據處理的效率密切相關B) 數據的存儲結構與數據處理的效率無關C) 數據的存儲結構在計算機中所占的空間不一定是連續的D) 一種數據的邏輯結構可以有多種存儲結構5、數據的存儲結構是指A）數據所占的存儲空間 C）數據在計算機中的順序存儲方式B）數據的邏輯結構在計算機中

12、的表示 D）存儲在外存中的數據6、順序存儲方法是把邏輯上相鄰的結點存儲在物理位置 【2】 的存儲單元中。 相鄰7、數據處理的最小單位是 A) 數據 B) 數據元素 C) 數據項D) 數據結構8、數據結構作為計算機的一門學科，主要研究數據的邏輯結構、對各種數據結構進行的運算，以及 A) 數據的存儲結構 B) 計算方法 C) 數據映象 D) 邏輯存儲9、數據結構中，與所使用的計算機無關的是數據的A) 存儲結構 B) 物理結構C) 邏輯結構 D) 物理和存儲結構 10、數據的邏輯結構有線性結構和 【1】 兩大類。 非線性結構1.3 線性表及其順序存儲結構1、線性表是由n(n0)個數據元素組成的一個有

13、限序列，表中的每一個數據元素，除了第一個和最后一個外，有且只有一個前件、后件。線性表中數據元素的個數稱為線性表的長度。線性表可以為空表。*：線性表有兩種存儲方式：順序和鏈式。2、線性表的順序存儲結構（也稱為順序表）具有兩個基本特點：（1）線性表中所有元素所占的存儲空間是連續的；（2）線性表中各數據元素在存儲空間中是按邏輯順序依次存放的，即順序表中邏輯上相鄰的元素的物理位置必定緊鄰。（即邏輯結構和物理存儲結構是一致的、一一對應的）3、順序表的插入、刪除運算（1）順序表的插入運算：在一般情況下，要在第i（1in）個元素之前插入一個新元素時，首先要從最后一個（即第n個）元素開始，直到第i個元素之間共

14、n-i+1個元素依次向后移動一個位置，移動結束后，第i個位置就被空出，然后將新元素插入到第i項。插入結束后，線性表的長度就增加了1。*：插入運算時需要移動元素，在等概率情況下，平均需要移動n/2個元素。（2）順序表的刪除運算：在一般情況下，要刪除第i（1in）個元素時，則要從第i+1個元素開始，直到第n個元素之間共n-i個元素依次向前移動一個位置。刪除結束后，線性表的長度就減小了1。*：刪除運算時也需要移動元素，在等概率情況下，平均需要移動（n-1）/2個元素。v 插入、刪除運算不方便。在長度為n的順序表中插入、刪除一個元素的時間復雜度都為O(n)。（3）即查找操作：可實現隨機訪問、隨機存取元

15、素在順序表中，其前后件兩個元素在存儲空間中是緊鄰的，且前件元素一定存儲在后件元素的前面，即順序存儲結構通過元素的相對存儲地址來表示元素之間的關系，可以通過計算機直接確定第i個結點的存儲地址。ai的存儲地址為：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)為第一個元素的地址，k代表每個元素占的字節數。線性表順序存儲的優點是可以隨機訪問、隨機存取元素即實現查找操作比較方便，換句話說，順序表是一種隨機存取的存儲結構。線性表順序存儲的缺點：（1）插入或刪除數據元素時需要移動大量的數據元素，運算效率很低。；（2）順序表的存儲空間不便于擴充；（3）不便于對存儲空間的動態分配1.4 線性鏈表

16、線性表的鏈式存儲結構稱為線性鏈表，是一種物理存儲單元上非連續、非順序的存儲結構（存儲數據結構的存儲空間可以不連續，各數據結點的存儲順序與數據元素之間的邏輯關系可以不一致），數據元素的邏輯關系是通過鏈表中的指針鏈接來實現的。因此，在鏈式存儲方式中，每個結點由兩部分組成：一部分用于存放數據元素的值，稱為數據域；另一部分用于存放指針，稱為指針域，用于指向該結點的前一個或后一個結點（即前件或后件）。線性鏈表分為單鏈表、雙向鏈表和循環鏈表三種類型。在單鏈表（如下圖）中，每一個結點只有一個指針域，由這個指針只能找到其后件結點，而不能找到其前件結點。因此，在某些應用中，對于線性鏈表中的每個結點設置兩個指針，

17、一個稱為左指針，指向其前件結點；另一個稱為右指針，指向其后件結點，這種鏈表稱為雙向鏈表，如下圖所示： 3、線性鏈表的基本運算（1）在線性鏈表中包含指定元素的結點之前插入一個新元素。*：在線性鏈表中插入元素時，不需要移動數據元素，只需要修改相關結點指針即可。（2）在線性鏈表中刪除包含指定元素的結點。*：在線性鏈表中刪除元素時，也不需要移動數據元素，只需要修改相關結點指針即可。（3）將兩個線性鏈表按要求合并成一個線性鏈表。（4）將一個線性鏈表按要求進行分解。（5）逆轉線性鏈表。         &#

18、160;   （6）復制線性鏈表。（7）線性鏈表的排序。           （8）線性鏈表的查找。4、循環鏈表及其基本運算在線性鏈表中，其插入與刪除的運算雖然比較方便，但還存在一個問題，在運算過程中對于空表和對第一個結點的處理必須單獨考慮，使空表與非空表的運算不統一。為了克服線性鏈表的這個缺點，可以采用另一種鏈接方式，即循環鏈表。與前面所討論的線性鏈表相比，循環鏈表具有以下兩個特點：1）在鏈表中增加了一個表頭結點，其數據域為任意或者根據需要來設置，指針域指向線性表的第一個元

19、素的結點，而循環鏈表的頭指針指向表頭結點；2）循環鏈表中最后一個結點的指針域不是空，而是指向表頭結點。即在循環鏈表中，所有結點的指針構成了一個環狀鏈。下圖a是一個非空的循環鏈表，圖b是一個空的循環鏈表：循環鏈表的優點主要體現在兩個方面：一是在循環鏈表中，只要從表中任何一個結點出發就訪問到表中其他所有的結點，而線性單鏈表做不到這一點；二是由于在循環鏈表中設置了一個表頭結點，在任何情況下，循環鏈表中至少有一個結點存在，從而使空表與非空表的運算統一。*：循環鏈表是在單鏈表的基礎上增加了一個表頭結點，其插入和刪除運算與單鏈表相同。鏈式存儲結構的特點（優缺點）插入、刪除靈活方便，不需要移動結點，只要改變

20、結點中指針域的值即可。適合于線性表是動態變化的,不進行頻繁查找操作、但經常進行插入刪除時使用。 鏈表的查找只能從頭指針開始順序查找。 【線性表習題】1、線性表的順序存儲結構和線性表的鏈式存儲結構分別是A) 順序存取的存儲結構、順序存取的存儲結構B) 隨機存取的存儲結構、順序存取的存儲結構C) 隨機存取的存儲結構、隨機存取的存儲結構D) 任意存取的存儲結構、任意存取的存儲結構 2、鏈表不具有的特點是A) 不必事先估計存儲空間 B) 可隨機訪問任一元素C) 插入刪除不需要移動元素 D) 所需空間與線性表長度成正比3、數據結構分為邏輯結構與存儲結構，線性鏈表屬于 【1】 。 4、順序存儲方法是把邏輯

21、上相鄰的結點存儲在物理位置 【2】 的存儲單元中。5、長度為n的順序存儲線性表中，當在任何位置上插入一個元素概率都相等時，插入一個元素所需移動元素的平均個數為 【1】 。6、線性表L=(a1,a2,a3,ai，an)，下列說法正確的是A) 每個元素都有一個直接前件和直接后件B) 線性表中至少要有一個元素C) 表中諸元素的排列順序必須是由小到大或由大到小D) 除第一個元素和最后一個元素外，其余每個元素都有一個且只有一個直接前件和直接后件7、根據數據結構中各數據元素之間前后件關系的復雜程度，一般將數據結構分成A) 動態結構和靜態結構 B) 緊湊結構和非緊湊結構C) 線性結構和非線性結構 D) 內部

22、結構和外部結構8、當線性表采用順序存儲結構實現存儲時，其主要特點是 【1】 。9、線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址A) 必須是連續的 B) 部分地址必須是連續的C) 一定是不連續的 D) 連續不連續都可以10、下列敘述中，錯誤的是A) 數據的存儲結構與數據處理的效率密切相關B) 數據的存儲結構與數據處理的效率無關C) 數據的存儲結構在計算機中所占的空間不一定是連續的D) 一種數據的邏輯結構可以有多種存儲結構 11、用鏈表表示線性表的優點是A) 便于隨機存取 B) 花費的存儲空間較順序存儲少C) 便于插入和刪除操作 D) 數據元素的物理順序與邏輯順序相同12、在單鏈表中，

23、增加頭結點的目的是A) 方便運算的實現 B) 使單鏈表至少有一個結點C) 標識表結點中首結點的位置 D) 說明單鏈表是線性表的鏈式存儲實現13、循環鏈表的主要優點是A) 不再需要頭指針了B) 從表中任一結點出發都能訪問到整個鏈表C) 在進行插入、刪除運算時，能更好的保證鏈表不斷開D) 已知某個結點的位置后，能夠容易的找到它的直接前件1.5 棧和隊列（特殊的線性表）1、棧及其基本運算棧是限定在一端進行插入與刪除運算的線性表。在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂元素總是最后被插入的元素，棧底元素總是最先被插入的元素。即棧是按照“先進后出”或“后進先出”的原則

24、組織數據的。由此看出，棧具有記憶作用。棧的基本運算：1）插入元素稱為入棧運算首先將棧頂指針加一（即top加1），然后將新元素插入到棧頂指針指向的位置；2）刪除元素稱為退棧運算首先將棧頂指針指向的元素賦給一個指定的變量，然后將棧頂指針減一（即top減1）3）讀棧頂元素是將棧頂元素賦給一個指定的變量，此時指針無變化。棧的存儲方式和線性表類似，也有兩種，即順序棧（插入和刪除是不需要移動棧中其它數據元素）和鏈式棧。2、隊列及其基本運算隊列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。尾指針（Rear）指向隊尾元素，頭指針（front）指向排頭元素的前一個位置（隊頭）。隊列是“先進

25、先出”或“后進后出”的線性表。隊列運算包括：1）入隊運算：從隊尾插入一個元素；2）退隊運算：從隊頭刪除一個元素。循環隊列：是隊列的順序存儲結構常用形式。所謂循環隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環狀空間，供隊列循環使用。在循環隊列中，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置，因此，從頭指針front指向的后一個位置直到隊尾指針rear指向的位置之間，所有的元素均為隊列中的元素。【棧和隊列習題】1、棧和隊列的共同特點是A)都是先進先出 B) 都是先進后出 C) 只允許在端點處插入和刪除元素 D) 沒有共同點2、如果進棧序

26、列為e1,e2,e3,e4，則可能的出棧序列是A) e3,e1,e4,e2 B) e2,e4,e3,e1 C) e3,e4,e1,e2 D) 任意順序3、一些重要的程序語言(如C語言和Pascal語言) 允許過程的遞歸調用。而實現遞歸調用中的存儲分配通常用A) 棧 B) 堆 C) 數組 D) 鏈表4、棧底至棧頂依次存放元素A、B、C、D，在第五個元素E入棧前，棧中元素可以出棧，則出棧序列可能是A) ABCED B) DCBEA C) DBCEA D) CDABE 5、棧通常采用的兩種存儲結構是A) 線性存儲結構和鏈表存儲結構 B) 散列方式和索引方式C) 鏈表存儲結構和數組 D) 線性存儲結構

27、和非線性存儲結構6、棧和隊列通常采用的存儲結構是 【1】 。7、下列數據結構中，按先進后出原則組織數據的是A) 線性鏈表 B) 棧 C) 循環鏈表 D) 順序表8、當循環隊列非空且隊尾指針等于隊頭指針時，說明循環隊列已滿，不能進行入隊運算。這種情況稱為 【2】 。 9、下列關于棧的敘述中正確的是）在棧中只能插入數據 B）在棧中只能刪除數據C）棧是先進先出的線性表 D）棧是后進先出的線性表10、下列關于隊列的敘述中正確的是）在隊列中只能插入數據 B）在隊列中只能刪除數據C）隊列是先進先出的線性表 D）隊列是后進先出的線性表1.6 樹與二叉樹1、樹的基本概念樹是一種簡單的非線性結構。在樹這種數據結

28、構中，所有數據元素之間的關系具有明顯的層次特性。在樹結構中，每一個結點只有一個前件，稱為父結點。沒有前件的結點只有一個，稱為樹的根結點，簡稱樹的根。每一個結點可以有多個后件，稱為該結點的子結點。沒有后件的結點稱為葉子結點。在樹結構中，一個結點所擁有的后件的個數稱為該結點的度，所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。2、二叉樹及其基本性質（1）什么是二叉樹二叉樹是一種很有用的非線性結構，它具有以下兩個特點：1）非空二叉樹只有一個根結點；2）每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。（五種基本形態：空樹、只有根結點的二叉樹、右子樹為空的二叉樹、左子樹為空的二叉樹、

29、左、右子樹均非空的二叉樹）*：根據二叉樹的概念可知，二叉樹的度可以為0（葉結點）、1（只有一棵子樹）或2（有2棵子樹）。（2）二叉樹的基本性質性質1  在二叉樹的第i層上，最多有2i-1個結點（i1）。性質2  深度為k的二叉樹最多有2K-1個結點(K1）。v 滿二叉樹：如果一個深度為K的二叉樹擁有2 K -1個結點，則將它稱為滿二叉樹。即除最后一層外，每一層上的所有結點都有兩個子結點。v 完全二叉樹：除最后一層外，每一層上的結點數均達到最大值；在最后一層上只缺少右邊的若干結點。完全二叉樹的特點v 葉子結點只可能在層次最大的兩層上出現v 對任意結點，若其右分支下的子孫的最大

30、層次是l ，則其左分支下的子孫的最大層次必是l 或l+1完全二叉樹還具有如下兩個特性：性質5  具有n個結點的完全二叉樹深度為ëlog2nû+1，其中ëlog2nû取log2n的整數部分。性質6  設完全二叉樹共有n個結點，如果從根結點開始，按層序（每一層從左到右）用自然數1，2，n給結點進行編號，則對于編號為k（k=1，2，n）的結點有以下結論：若k=1，則該結點為根結點，它沒有父結點；若k>1，則該結點的父結點的編號為INT(k/2)。若2kn，則編號為k的左子結點編號為2k；否則該結點無左子結點（顯然也沒有右子結點）。若2

31、k+1n，則編號為k的右子結點編號為2k+1；否則該結點無右子結點。<注意>一棵滿二叉樹一定是一棵完全二叉樹，而一棵完全二叉樹不一定是滿二叉樹。下圖a表示的是滿二叉樹，下圖b表示的是完全二叉樹：性質3  在任意一棵二叉樹中，度數為0的結點（即葉子結點）總比度為2的結點多一個。（如果度為0的結點（葉子）個數為n0，度為2的結點個數為n2，則n0=n2+1。）性質4  具有n個結點的二叉樹，其深度至少為ëlog2nû+1，其中ëlog2nû 取log2n的整數部分。3、二叉樹的存儲結構在計算機中，二叉樹通常采用鏈式存儲結構。與

32、線性鏈表類似，用于存儲二叉樹中各元素的存儲結點也由兩部分組成：數據域和指針域。但在二叉樹中，由于每一個元素可以有兩個后件（即兩個子結點），因此，用于存儲二叉樹的存儲結點的指針域有兩個：一個用于指向該結點的左子結點的存儲地址，稱為左指針域；另一個用于指向該結點的右子結點的存儲地址，稱為右指針域。*：一般二叉樹通常采用鏈式存儲結構，對于滿二叉樹與完全二叉樹來說，可以wx6 。5、二叉樹的遍歷所謂遍歷二叉樹是指按某種順序訪問二叉樹中的每個結點一次且僅一次的過程，即不重復地訪問二叉樹中的所有結點。二叉樹的遍歷可以分為以下三種：（1）前（先）序遍歷（DLR）：若二叉樹為空，則結束返回。否則：首

33、先訪問根結點，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左右子樹時，仍然先訪問根結點，然后遍歷左子樹，最后遍歷右子樹。（2）中序遍歷（LDR）：若二叉樹為空，則結束返回。否則：首先遍歷左子樹，然后訪問根結點，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結點，最后遍歷右子樹。（3）后序遍歷（LRD）：若二叉樹為空，則結束返回。否則：首先遍歷左子樹，然后遍歷右子樹，最后訪問根結點，并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結點。1.7 查找技術查找：根據給定的某個值，在查找表中確定一個其關鍵字等于給定值的數據元素。查找結果：（查找成功：找到；

34、查找不成功：沒找到。）平均查找長度：查找過程中關鍵字和給定值比較的平均次數。1、順序查找基本思想：從表中的第一個元素開始，將給定的值與表中逐個元素的關鍵字進行比較，直到兩者相符，查到所要找的元素為止。否則就是表中沒有要找的元素，查找不成功。在平均情況下，利用順序查找法在線性表中查找一個元素，大約要與線性表中一半的元素進行比較，最壞情況下需要比較n次。順序查找一個具有n個元素的線性表，其平均復雜度為O（n）。下列兩種情況下只能采用順序查找：1）如果線性表是無序表（即表中的元素是無序的），則不管是順序存儲結構還是鏈式存儲結構，都只能用順序查找。2）即使是有序線性表，如果采用鏈式存儲結構，也只能用順

35、序查找。2、二分法查找：二分法查找只適用于順序存儲的有序表，且表中元素必須按wx7 。思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認找不到該記錄為止。查找過程：1）若中間項（中間項mid=(n-1)/2，mid的值四舍五入取整）的值等于x，則說明已查到；2）若x小于中間項的值，則在線性表的前半部分查找；3）若x大于中間項的值，則在線性表的后半部分查找。特點：比順序查找方法效率高。在長度為n的有序線性表中進行二分法查找，最壞的情況下，需要比較log2n次，其時間復雜度為O（log2n）。1.8 排序技術排序是指將一個無序序列整理成按值非遞減順序排列的有序序列，即是將

36、無序的記錄序列調整為有序記錄序列的一種操作。交換類排序法：冒泡排序法，最壞情況下需要比較的次數為n(n-1)/2， 快速排序法，最壞情況下需要比較的次數為n(n-1)/2；插入類排序法：簡單插入排序法，最壞情況需要n(n-1)/2次比較，希爾排序法，最壞情況需要O(n1.5)次比較； 選擇類排序法：簡單選擇排序法，最壞情況需要n(n-1)/2次比較，堆排序法，最壞情況需要O(nlog2n)次比較。 全國計算機等級考試二級公共基礎講義之二數據庫設計基礎4.l 數據庫系統的基本概念考點1 數據、數據庫1數據數據(Data)是數據庫中存儲的基本對象。數據的定義：描述事物

37、的符號記錄。計算機中的數據一般分為兩部分，其中一部分存放于計算機內存中，與程序僅有短時間的交互關系，隨著程序的結束而消亡，它們被稱為臨時性數據；而另一部分數據則對系統起著長期持久的作用，它們被稱為持久性數據。數據庫系統屬于持久性數據。數據的種類：文字、圖形、圖像和聲音。數據有型(Type)與值(Value)之分，數據的型給出了數據的表示類型，如整型、實型、字符型等。數據的特點：數據與其語義是不可分的。2數據庫數據庫(DataBase，DB)是長期儲存在計算機內、有組織的、可共享的大量數據集合。數據庫存放數據是按數據所提供的數據模式存放的，它能構造復雜的數據結構，以建立數據間的內在聯系與復雜的關

38、系，從而構成數據的全局結構模式。數據庫的特點：(1)數據按一定的數據模型組織、描述和儲存；(2)可為各種用戶共享；(3)冗余度較??；(4)數據獨立性較高；(5)易擴展。考點2 數據庫管理系統1數據庫管理系統的概念數據庫管理系統(DataBase Management System，DBMS)是數據庫的機構，它是一種系統軟件，負責數據庫中的數據組織、數據操作、數據維護、數據控制及保護和數據服務等。數據庫管理系統有如下功能：(l)數據模式定義。數據庫管理系統負責為數據庫構建模式；(2)數據存取的物理構建。數據庫管理系統負責為數據模式的物理存取及構建提供有效的存取方法與手段；(3)數據操縱

39、。數據庫管理系統一般提供查詢、插入、修改以及刪除數據的功能。它還具有做簡單算術運算及統計的能力和強大的過程性操作能力；(4)數據的完整性、安全性定義與檢查。數據庫中的數據具有內在語義上的關聯性與一致性，它們構成了數據的完整性；(5)數據庫的并發控制與故障恢復。數據庫管理系統必須對多個應用程序的并發操作做必要的控制以保證數據不受破壞，這就是數據庫的并發控制；數據庫中的數據一旦遭受破壞，數據庫管理系統必須有能力及時進行恢復，這就是數據庫的故障恢復；(6)數據的服務。數據庫管理系統提供對數據庫中數據的多種服務功能，如數據拷貝、轉儲、重組、性能監測、分析等。為完成數據庫管理系統的功能，數據庫管理系統提

40、供相應的數據語言(Data Language)：(l)數據定義語言(Data Definition Language，DDL)。該語言負責數據的模式定義與數據的物理存取構建。(2)數據操縱語言(Data Manipulation Language， DML )。該語言負責數據的操縱，包括查詢及增加、刪除、修改等操作。(3)數據控制語言(Data Control Language， DCL)。該語言負責數據完整性、安全性的定義與檢查以及并發控制、故障恢復等功能。上述數據語言按其使用方式可分為交互式命令語言和宿主型語言兩種結構形式。2數據庫管理員數據庫管理員(DataBase Administra

41、tor，DBA)是指對數據庫的規劃、設計、維護、監視等的人員。數據庫管理員的主要工作如下：(1)數據庫設計(Database Design)。DBA的主要任務之一是數據庫設計，具體地說是進行數據模式的設計；(2)數據庫維護。DBA必須對數據庫中的數據安全性、完整性、并發控制及系統恢復、數據定期轉儲等進行實施與維護；(3)改善系統性能，提高系統效率。DBA必須隨時監視數據庫的運行狀態，不斷調整內部結構，使系統保持最佳狀態與效率。考點3 數據庫系統   1數據庫系統數據庫系統(DataBase System， DBS)是指在計算機系統中引入數據庫后的系統構成。在不引起

42、混淆的情況下常常把數據庫系統簡稱為數據庫。    數據庫系統的構成：數據庫系統由數據庫(數據)、數據庫管理系統(及其開發工具)、應用系統、數據庫管理員、系統平臺之一硬件平臺(硬件)、系統平臺之二軟件平臺(軟件)5部分構成。硬件平臺包括以下兩項：(l)計算機：它是系統中硬件的基礎平臺；(2)網絡：數據庫系統今后將以建立在網絡上為主，而其結構形成又以客戶/服務器(C/S)方式與瀏覽器/服務器(B/S)方式為主。軟件平臺包括以下3項：(l)操作系統：它是系統的基礎軟件平臺；(2)數據庫系統開發工具：它包括過程性程序設計語言(如C，C+等)，也包括可視化開發工具VB，PB

43、、Delphi等，它還包括近期與Internet有關的HTML和XML等。(3)接口軟件：在網絡環境下數據庫系統中數據庫與應用程序，數據庫與網絡間存在著多種接口，它們需要接口軟件進行連接，這些接口軟件包括ODBC、JDBC、OLEDB、COBBA、COM及DOOM等。2數據庫應用系統數據庫應用系統(DataBase Application System，DBAS )是數據庫再加上應用軟件及應用界面這三者所組成，具體包括數據庫、數據庫管理系統、數據庫管理員，硬件平臺、應用軟件及應用界面。數據庫的7個部分以一定的邏輯結構方式組成一個有機的整體，如圖4-1所示。 圖4-1數據庫系統的軟硬件

44、層次結構下面以一個用戶讀取某數據記錄為例，展示在數據庫中訪問數據的具體執行過程，該過程如圖4-2所示。(1)用戶程序中有一條讀數據庫記錄的DML語句，當計算機執行到該語句時，即向DBMS發出讀取相應記錄的命令。(2) DBMS接到該命令后，首先訪問該用戶對應子模式，檢查該操作是否在合法授權范圍內及欲讀記錄的正確性、有效性，若不合法則拒絕執行，并向應用程序狀態返回區發出回答狀態信息；反之執行下一步。(3)DBMS讀取模式描述并從子模式映射到全局模式，從而確定所需的邏輯記錄類型。(4)DBMS從邏輯模式映射到存儲模式，從而確定讀入哪些物理記錄以及具體的地址信息。(5)DBMS向操作系統發出從指定地

45、址讀取記錄的命令。(6)操作系統執行讀命令，按指定地址從數據庫中把記錄讀入系統緩沖區，并在操作結束后向DBMS作出回答。(7) DBMS按照模式將讀入系統緩沖區中內容映射成用戶要求讀取的邏輯記錄。(8) DBMS將導出的邏輯記錄送入用戶工作區，并將操作執行情況的狀態信息返回給用戶。(9) DBMS將已執行的操作載入運行日志。(10)應用程序根據返回的狀態信息決定是否利用該數據進行操作等。 圖4-2 數據庫系統訪問數據的步驟考點4 數據庫系統的發展數據管理技術的發展經歷了3個階段，見表4-1：(1)人工管理階段(20世紀40年代中20世紀50年代中)；(2)文件系統

46、階段(20世紀50年代末20世紀60年代中)；(3)數據庫系統階段(20世紀60年代末現在)。表4-1 各階段特點的詳細說明 人工管理階段的特點：(1)數據的管理者：應用程序，數據不保存；(2)數據面向的對象：某一應用程序；(3)數據的共享程度：無共享、冗余度極大；(4)數據的獨立性：不獨立，完全依賴于程序；(5)數據的結構化：無結構；(6)數據控制能力：應用程序自己控制。人工管理階段應用程序與數據對應關系如圖4-3所示。 圖4-3 人工管理階段應用程序與數據之間的關系文件管理階段的特點：(1)數據的管理者：文件系統，數據可長期保存；(2)數據面向的對象

47、：某一應用程序；(3)數據的共享程度：共享性差、冗余度大；(4)數據的結構化：記錄內有結構，整體無結構；(5)數據的獨立性：獨立性差，數據的邏輯結構改變必須修改應用程序；(6)數據控制能力：應用程序自己控制。文件階段應用程序與數據之間的對應關系如圖4-4所示。 圖4-4 文件階段應用程序與數據之間的對應關系數據庫系統階段的特點：(1)數據的管理者：DBMS;(2)數據面向的對象：現實世界；(3)數據的共享程度：共享性高；(4)數據的獨立性：高度的物理獨立性和一定的邏輯獨立性；(5)數據的結構化：整體結構化；(6)數據控制能力：由DBMS統一管理和控制。一、數據庫系統的基本概

48、念數據、數據庫、數據庫管理系統1.數據處理的最小單位是(C)。A.數據 B.數據元素 C.數據項 D.數據結構2.下列有關數據庫的描述，正確的是(C)。A.數據庫是一個DBF文件 B.數據庫是一個關系C.數據庫是一個結構化的數據的集合 D.數據庫是一組文件3.下述關于數據庫系統的敘述中正確的是(A) A.數據庫系統減少了數據冗余 B.數據庫系統避免了一切冗余C.數據庫系統避免了一切數據的重復 D.數據庫系統比文件系統能管理更多的數據4.下列有關數據庫的描述正確的是(D)。A.數據處理是將信息轉化為數據的過程B.數據的物理獨立性是指當數據的邏輯結構改變時，數據的存儲結構不變C.關系中的每一列稱為

49、元組，一個元組就是一個字段D.如果一個關系中的屬性或屬性組并非該關系的關鍵字，但它是另一個關系的關鍵字，則稱其為本關系的外關鍵字5.下列4項說法中不正確的是(C)。A.數據庫減少了數據冗余 B.數據庫中的數據可以共享C.數據庫避免了一切數據的重復 D.數據庫具有較高的數據獨立性6.下列敘述中。不屬于數據庫系統的是(D)。A.數據庫 B.數據庫管理系統 C.數據庫管理員 D.數據庫應用系統7.數據庫系統的核心是(數據庫管理系統)。8.數據庫、數據庫系統和數據庫管理系統之間的關系是(數據庫系統包括數據庫和數據庫管理系統)。9.為用戶與數據庫系統提供接口的語言是(數據操縱語言(DML)。數據庫管理系

50、統一般提供的數據語言有：數據庫定義語言(DDL)：負責數據的模式定義與數據的物理存取構建數據操縱語言(DML)：負責數據的操縱，包括查詢及增、刪、改變等操作數據庫控制語言(DCL)：負責數據完整性、安全性的定義與檢查以及并發控制、故障恢復等2. 數據庫系統的發展10.在數據管理技術的發展過程中經歷了人工管理階段、文件系統階段和數據庫系統階段。其中數據獨立性最高的階段是(數據庫系統)。11.在數據管理技術發展過程中，文件系統與數據庫系統的主要區別是數據庫系統具有(A)。A.特定的數據模型 B.數據無冗余 C.數據可共享 D.專門的數據管理軟件12.相對于數據庫系統，文件系統的主要缺陷有數據關聯差

51、、數據不一致性和(冗余性)。13.分布式數據庫系統不具有的特點是( D)。 A.數據分布性和邏輯整體性 B.位置透明性和復制透明性 C.分布性 D.數據冗余來源：3.數據庫系統的基本特點數據獨立性 是數據與程序間的互不依賴性，即數據庫中數據獨立于應用程序而不依賴于應用程序。也就是說，數據的邏輯結構、存儲結構和存取方式的改變都不會影響應用程序。數據獨立性包括物理獨立性和 邏輯獨立性 兩個含義。當數據的物理結構(存儲結構、存取方式等)改變時，不影響數據庫的邏輯結構從而不致引起應用程序的變化，這是指數據的 物理獨立性 。4.數據庫系統的內部結構數據庫系統在其內部具有三級模式及二級映射，三級模式分別是

52、概念級模式、內部級模式與外部級模式，二級映射分別是概念級到內部級的映射以及外部級到概念級的映射。這種三級模式與二級映射構成了數據庫系統內部抽象結構體系。14.單個用戶使用的數據視圖的描述稱為(外模式)。索引屬于(內模式)。二、數據模型1數據模型的基本概念數據模型是數據庫設計的核心。其內容有三個部分：數據結構、數據操作和數據約束數據模型按不同應用層次分3種類型，它們是概念數據模型、邏輯數據模型和物理數據模型。概念數據模型簡稱概念模型，是面向客觀世界、面向用戶的模型；是整個數據模型的基礎。與具體的數據庫管理系統無關，著重于對客觀事件的結構描述以及它們之間的內在聯系的刻畫。常用的有E-R模型、擴充的

53、E-R模型等。邏輯數據模型又稱數據模型，是面向數據庫系統的模型，著重于數據庫系統一級的實現。概念模型只有在轉換成數據模型后才有可能在數據庫中得以表示。常見的有層次模型、網狀模型和關系模型。數據庫管理系統常見的數據模型有層次模型、網狀模型和 關系模型 3種。15.下列數據模型中，具有堅實理論基礎的是(C)。A.層次模型   B.網狀模型   C.關系模型   D.以上3個都是16.下列說法中，不屬于數據模型所描述的內容的是(C)。A.數據結構   B.數據操作   C.數據查詢   D.數據約束2E-R模型17.實體是信息世界中廣泛使用的一個術語，它用于表示(C)。A.有生命的事物   B.無生命的事物   C.實際存在的事物   D.一切事物18.E-R模型由 實體 、聯系 和 屬性 三個基本概念組成。19.將ER圖轉換到關系模式時，實體與聯系都可以表示成(關系)。20.下列敘述中，正確的是(A)。A.用ER圖能夠表示實體集間一對一的聯系、一對多的聯系和多對多的聯系B.用ER圖只能表示實體集之問一對一的