二級公共ppt(關(guān)于二級公共)

1.關(guān)于二級公共基礎(chǔ)知識

二級公共基礎(chǔ)知識考試大綱

基 本 要 求

(1)掌握算法的基本概念。

(2)掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作。

(3)掌握基本排序和查找算法。

(4)掌握逐步求精的結(jié)構(gòu)化程序設(shè)計方法。

(5)掌握軟件工程的基本方法，具有初步應(yīng)用相關(guān)技術(shù)進(jìn)行軟件開發(fā)的能力。

(6)掌握數(shù)據(jù)庫的基本知識，了解關(guān)系數(shù)據(jù)庫的設(shè)計。

考 試 內(nèi) 容

1. 基本數(shù)據(jù)結(jié)構(gòu)與算法

(1)算法的基本概念：算法復(fù)雜度的概念和意義（時間復(fù)雜度與空間復(fù)雜度）。

(2)數(shù)據(jù)結(jié)構(gòu)的定義：數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。

(3)線性表的定義：線性表的順序存儲結(jié)構(gòu)及其插入與刪除運(yùn)算。

(4)棧和隊(duì)列的定義：棧和隊(duì)列的順序存儲結(jié)構(gòu)及其基本運(yùn)算。

(5)線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。

(6)樹的基本概念：二叉樹的定義及其存儲結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。

(7)順序查找與二分法查找算法：基本排序算法（交換類排序，選擇類排序，插入類排序）。

2. 程序設(shè)計基礎(chǔ)

(1)程序設(shè)計方法與風(fēng)格。

(2)結(jié)構(gòu)化程序設(shè)計。

(3)面向?qū)ο蟮某绦蛟O(shè)計方法，對象，方法，屬性及繼承與多態(tài)性。

3. 軟件工程基礎(chǔ)

(1)軟件工程基本概念，軟件生命周期概念，軟件工具與軟件開發(fā)環(huán)境。

(2)結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。

(3)結(jié)構(gòu)化設(shè)計方法，總體設(shè)計與詳細(xì)設(shè)計。

(4)軟件測試的方法，白盒測試與黑盒測試，測試用例設(shè)計，軟件測試的實(shí)施，單元測試、集成測試和系統(tǒng)測試。

(5)程序的調(diào)試，靜態(tài)調(diào)試與動態(tài)調(diào)試。

4. 數(shù)據(jù)庫設(shè)計基礎(chǔ)

(1)數(shù)據(jù)庫的基本概念：數(shù)據(jù)庫，數(shù)據(jù)庫管理系統(tǒng)，數(shù)據(jù)庫系統(tǒng)。

(2)數(shù)據(jù)模型：實(shí)體聯(lián)系模型及E-R圖，從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。

(3)關(guān)系代數(shù)運(yùn)算：包括集合運(yùn)算及選擇、投影、連接運(yùn)算，數(shù)據(jù)庫規(guī)范化理論。

(4)數(shù)據(jù)庫設(shè)計方法和步驟：需求分析、概念設(shè)計、邏輯設(shè)計和物理設(shè)計的相關(guān)策略。

考 試 方 式

(1)公共基礎(chǔ)知識的考試方式為筆試，與C語言程序設(shè)計（C++語言程序設(shè)計、Java語言程序設(shè)計、Visual Basic語言程序設(shè)計、Visual FoxPro數(shù)據(jù)庫程序設(shè)計、Access數(shù)據(jù)庫程序設(shè)計或Delphi語言程序設(shè)計）的筆試部分合為一張?jiān)嚲怼９不A(chǔ)知識部分占全卷的30分。

(2)公共基礎(chǔ)知識有10道選擇題和5道填空題。

2.求計算機(jī)二級公共基礎(chǔ)知識

計算機(jī)二級公共基礎(chǔ)知識總結(jié)數(shù)據(jù)結(jié)構(gòu)與算法1.1 算法算法：是指解題方案的準(zhǔn)確而完整的描述。

算法不等于程序，也不等計算機(jī)方法，程序的編制不可能優(yōu)于算法的設(shè)計。算法的基本特征：是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，每一個規(guī)則都是有效的，是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。

特征包括：（1）可行性；（2）確定性，算法中每一步驟都必須有明確定義，不充許有模棱兩可的解釋，不允許有多義性；（3）有窮性，算法必須能在有限的時間內(nèi)做完，即能在執(zhí)行有限個步驟后終止，包括合理的執(zhí)行時間的含義；（4）擁有足夠的情報。算法的基本要素：一是對數(shù)據(jù)對象的運(yùn)算和操作；二是算法的控制結(jié)構(gòu)。

指令系統(tǒng)：一個計算機(jī)系統(tǒng)能執(zhí)行的所有指令的集合?；具\(yùn)算和操作包括：算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸。

算法的控制結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。算法基本設(shè)計方法：列舉法、歸納法、遞推、遞歸、減斗遞推技術(shù)、回溯法。

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

算法空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。1.2 數(shù)據(jù)結(jié)構(gòu)的基本基本概念數(shù)據(jù)結(jié)構(gòu)研究的三個方面：（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；（2）在對數(shù)據(jù)進(jìn)行處理時，各數(shù)據(jù)元素在計算機(jī)中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)；（3）對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。

數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。數(shù)據(jù)的邏輯結(jié)構(gòu)包含：（1）表示數(shù)據(jù)元素的信息；（2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。

數(shù)據(jù)的存儲結(jié)構(gòu)有順序、鏈接、索引等。線性結(jié)構(gòu)條件：（1）有且只有一個根結(jié)點(diǎn)；（2）每一個結(jié)點(diǎn)最多有一個前件，也最多有一個后件。

非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。1.3 線性表及其順序存儲結(jié)構(gòu)線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號，元素之間的相對位置是線性的。

在復(fù)雜線性表中，由若干項(xiàng)數(shù)據(jù)元素組成的數(shù)據(jù)元素稱為記錄，而由多個記錄構(gòu)成的線性表又稱為文件。非空線性表的結(jié)構(gòu)特征：（1）且只有一個根結(jié)點(diǎn)a1，它無前件；（2）有且只有一個終端結(jié)點(diǎn)an，它無后件；（3）除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個前件，也有且只有一個后件。

結(jié)點(diǎn)個數(shù)n稱為線性表的長度，當(dāng)n=0時，稱為空表。線性表的順序存儲結(jié)構(gòu)具有以下兩個基本特點(diǎn)：（1）線性表中所有元素的所占的存儲空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。

ai的存儲地址為：ADR(ai)=ADR(a1)+(i-1)k,,ADR(a1)為第一個元素的地址，k代表每個元素占的字節(jié)數(shù)。順序表的運(yùn)算：插入、刪除。

（詳見14--16頁）1.4 棧和隊(duì)列棧是限定在一端進(jìn)行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧按照“先進(jìn)后出”（FILO）或“后進(jìn)先出”（LIFO）組織數(shù)據(jù)，棧具有記憶作用。

用top表示棧頂位置，用bottom表示棧底。棧的基本運(yùn)算：（1）插入元素稱為入棧運(yùn)算；（2）刪除元素稱為退棧運(yùn)算；（3）讀棧頂元素是將棧頂元素賦給一個指定的變量，此時指針無變化。

隊(duì)列是指允許在一端（隊(duì)尾）進(jìn)入插入，而在另一端（隊(duì)頭）進(jìn)行刪除的線性表。Rear指針指向隊(duì)尾，front指針指向隊(duì)頭。

隊(duì)列是“先進(jìn)行出”（FIFO）或“后進(jìn)后出”（LILO）的線性表。隊(duì)列運(yùn)算包括（1）入隊(duì)運(yùn)算：從隊(duì)尾插入一個元素；（2）退隊(duì)運(yùn)算：從隊(duì)頭刪除一個元素。

循環(huán)隊(duì)列：s=0表示隊(duì)列空，s=1且front=rear表示隊(duì)列滿1.5 線性鏈表數(shù)據(jù)結(jié)構(gòu)中的每一個結(jié)點(diǎn)對應(yīng)于一個存儲單元，這種存儲單元稱為存儲結(jié)點(diǎn)，簡稱結(jié)點(diǎn)。結(jié)點(diǎn)由兩部分組成：（1）用于存儲數(shù)據(jù)元素值，稱為數(shù)據(jù)域；（2）用于存放指針，稱為指針域，用于指向前一個或后一個結(jié)點(diǎn)。

在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。鏈?zhǔn)酱鎯Ψ绞郊纯捎糜诒硎揪€性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。

線性鏈表，HEAD稱為頭指針，HEAD=NULL（或0）稱為空表，如果是兩指針：左指針（Llink）指向前件結(jié)點(diǎn)，右指針（Rlink）指向后件結(jié)點(diǎn)。線性鏈表的基本運(yùn)算：查找、插入、刪除。

1.6 樹與二叉樹樹是一種簡單的非線性結(jié)構(gòu)，所有元素之間具有明顯的層次特性。在樹結(jié)構(gòu)中，每一個結(jié)點(diǎn)只有一個前件，稱為父結(jié)點(diǎn)，沒有前件的結(jié)點(diǎn)只有一個，稱為樹的根結(jié)點(diǎn)，簡稱樹的根。

每一個結(jié)點(diǎn)可以有多個后件，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。

在樹結(jié)構(gòu)中，一個結(jié)點(diǎn)所擁有的后件的個數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹的度。樹的最大層次稱為樹的深度。

二叉樹的特點(diǎn)：（1）非空二叉樹只有一個根結(jié)點(diǎn)；（2）每一個結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。二叉樹的基本性質(zhì)：（1）在二叉樹的第k層上，最多有2k-1(k≥1)個結(jié)點(diǎn)；（2）深度為m的二叉樹最多有2m-1個結(jié)點(diǎn)；（3）度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個；（4）具有n個結(jié)點(diǎn)的二叉樹，。

3.計算機(jī)二級公共基礎(chǔ)知識要點(diǎn)

為了方便計算機(jī)等級試，特意整理出來的。

第一章數(shù)據(jù)結(jié)構(gòu)與算法1算法是解題方案的準(zhǔn)確而完整的描述，它不等于程序，也不等于計算方法。基本特征：可行性、確定性、有窮性、擁有足夠的情報。

2算法復(fù)雜度主要包括時間復(fù)雜度和空間復(fù)雜度。時間復(fù)雜度：用來衡量算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù)。

空間復(fù)雜度：用來衡量算法執(zhí)行過程中所需要的存儲空間。3數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容：（1）數(shù)據(jù)的邏輯結(jié)構(gòu)（2）數(shù)據(jù)的存儲結(jié)構(gòu)（3）對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算4研究數(shù)據(jù)結(jié)構(gòu)的主要目的：提高數(shù)據(jù)處理的效率。

5數(shù)據(jù)結(jié)構(gòu)的定義：指相互關(guān)聯(lián)的數(shù)據(jù)元素的集合。6數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系，數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲空間的存放形式。

同一種邏輯結(jié)構(gòu)可以采用不同存儲結(jié)構(gòu)，但影響數(shù)據(jù)處理效率。7數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)常見線性結(jié)構(gòu)：線性表、棧、隊(duì)列、線性鏈表常用非線性結(jié)構(gòu)：樹、二叉樹、圖8線性表示由n(n>=0)個相同類型的數(shù)據(jù)元素構(gòu)成的有限序列。

結(jié)構(gòu)特征：（1）數(shù)據(jù)元素在表中的位置由序號決定，數(shù)據(jù)元素之間的相對位置是線性的（2）對于一個非空線性表，有且只有一個根節(jié)點(diǎn)a1，它無前件，有且只有一個終端結(jié)點(diǎn)an，它無后件，除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個前件，也有且只有一個后件。基本存儲結(jié)構(gòu)：（1）順序存儲（2）鏈?zhǔn)酱鎯?順序表的插入運(yùn)算時需要移動元素，在等概率情況下，平均需要移動n/2個元素。

10進(jìn)行順序表的刪除運(yùn)算時也需要移動元素，在等概率情況下，平均移動（n-1）/2個元素。11棧只能在棧頂插入或刪除元素，是一種先進(jìn)后出FILO（或稱為后入先出LIFO）的線性表。

12隊(duì)列是只能從隊(duì)尾插入元素，在隊(duì)頭刪除元素，是一種先進(jìn)先出FIFO（或后入后出LILO）的線性表。13線性鏈表不能隨機(jī)存取。

14在線性鏈表中插入元素時，不需要移動數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點(diǎn)指針即可，也不會出現(xiàn)“上溢”現(xiàn)象。15在線性鏈表中刪除元素時，也不需要移動數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點(diǎn)指針即可。

16循環(huán)鏈表實(shí)單鏈表基礎(chǔ)上增加了一個表頭結(jié)點(diǎn)，其插入和刪除運(yùn)算與單鏈表相同，可以從任意結(jié)點(diǎn)出發(fā)來訪問表中其他所有結(jié)點(diǎn)，并實(shí)現(xiàn)空表與非空表的運(yùn)算。17一般二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，對于滿二叉樹與完全二叉樹來說，可以按層序進(jìn)行順序存儲。

18二分查找知識用于順序存儲的線性表，對于無序線性表和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)只能用順序查找。19冒泡排序是每一趟都會把較小的元素先前移動，最壞比較次數(shù)是n(n-1)/2。

20簡單插入排序法是將無序序列中的各元素依次插入到已經(jīng)有序的線性表中，最壞比較次數(shù)為n(n-1)/2。21希爾排序法的基本思想：將無序序列劃分成若干個子序列（又相隔某個增量h的元素組成）分別進(jìn)行直接插入排序，待整個序列中的元素基本有序（增量足夠?。r，在對全體元素進(jìn)行一次直接插入排序。

因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下（接近最好情況），效率是很高的。22選擇排序每一趟都是找出無序序列中的最小一個元素，最壞比較次數(shù)為n(n-1)/2。

23排序技術(shù)：（1）交換排序法：冒泡排序、快速排序（2）插入排序法：簡單插入排序法、希爾排序（3）選擇排序法：簡單選擇排序法、堆排序法。

4.求計算機(jī)二級公共基礎(chǔ)知識部分的知識總結(jié)

1、算法問題處理方案的正確而完整的描述稱為【算法】。

算法分析的目的是，分析算法的效率以求改進(jìn)。算法的基本特征是【可行性】、【確定性】、【有窮性】和擁有足夠情報。

算法的有窮性是指：算法程序的運(yùn)行時間是有限的。算法的復(fù)雜度是衡量算法好壞的度量，分為【時間復(fù)雜度】和【空間復(fù)雜度】。

時間復(fù)雜度是指執(zhí)行算法所需要的【計算工作量】；算法的空間復(fù)雜度是指算法執(zhí)行過程中所需的【存儲空間】。算法時間復(fù)雜度或空間復(fù)雜度中的一項(xiàng)的值，沒有辦法推出另一項(xiàng)的值。

2、數(shù)據(jù)結(jié)構(gòu)索引屬于存儲結(jié)構(gòu)（物理結(jié)構(gòu)）。循環(huán)隊(duì)列屬于【存儲結(jié)構(gòu)】。

數(shù)據(jù)的存儲結(jié)構(gòu)又稱為物理結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲空間中的存放形式。一個邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)影響數(shù)據(jù)處理的效率。

程序執(zhí)行的效率與數(shù)據(jù)的存儲結(jié)構(gòu)密切相關(guān)。數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈的隊(duì)列屬于【線性結(jié)構(gòu)】。

線性表的存儲結(jié)構(gòu)主要分為順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。順序存儲結(jié)構(gòu)的存儲一定是連續(xù)的，鏈?zhǔn)酱鎯Φ拇鎯臻g不一定是連續(xù)的。

有序線性表既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。隊(duì)列是一種特殊的線性表，循環(huán)隊(duì)列按照【先進(jìn)先出】原則組織數(shù)據(jù)。

循環(huán)隊(duì)列是隊(duì)列的【順序】存儲結(jié)構(gòu)。數(shù)據(jù)的獨(dú)立性分為【物理獨(dú)立】性和【邏輯獨(dú)立性】。

當(dāng)數(shù)據(jù)的存儲結(jié)構(gòu)改變時，其邏輯結(jié)構(gòu)可以不變，因此，基于邏輯結(jié)構(gòu)的應(yīng)用程序可以不用修改，稱為【物理獨(dú)立性】。3、棧和隊(duì)列棧是一種特殊的線性表，是只能在一端進(jìn)行插入和刪除的線性表，特點(diǎn)是先進(jìn)后出棧是【先進(jìn)后出】的線性表；棧具有記憶作用；對棧的插入與刪除操作中，不需要改變【棧底指針】。

假定讓元素1、2、3、A、B依次入棧，則出棧的順序是：B、A、3、2、1。棧與隊(duì)列都是線性結(jié)構(gòu)，樹是非線性結(jié)構(gòu)。

支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是【?！俊Ｅc隊(duì)列的共同點(diǎn)是，都只允許在【端點(diǎn)處】插入和刪除元素。

棧只能順序存儲的描述是錯誤的。?？梢杂小卷樞蚝玩?zhǔn)健績煞N存儲方式。

隊(duì)列是允許在一段插入，在另一端進(jìn)行刪除的線性表，其特點(diǎn)是【先進(jìn)先出】。循環(huán)隊(duì)列中元素的個數(shù)是由隊(duì)頭指針和隊(duì)尾指針共同決定。

循環(huán)隊(duì)列的頭指針為front，尾指針為rear，容量為maxSize，則循環(huán)隊(duì)列中元素的個數(shù)是【 （rear-front+maxSize） mod maxSize】。4、線性鏈表線性鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。

用鏈表表示線性表的優(yōu)點(diǎn)是【便于插入和刪除操作】。線性鏈表的存儲空間不一定連續(xù)，且個元素的存儲順序是任意的。

5、樹與二叉樹在樹結(jié)構(gòu)中，一個結(jié)點(diǎn)所擁有的后件（繼）的個數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹的度。二叉樹各結(jié)點(diǎn)的度只可能取值0、1、2，不可能是其它值。

換言之，知道了度為1結(jié)點(diǎn)數(shù)量的前提下，葉子結(jié)點(diǎn)或度為2的結(jié)點(diǎn)中知道其一，就可以求出總的結(jié)點(diǎn)數(shù)。上述的計算公式，關(guān)鍵要能夠應(yīng)用，例如，深度為7的滿二叉樹，度為2的結(jié)點(diǎn)數(shù)量是多少？既然是滿二叉樹，葉子結(jié)點(diǎn)的數(shù)量就是第7層的結(jié)點(diǎn)數(shù)量，也就是26，可以算出葉子結(jié)點(diǎn)為64，因此度為2的結(jié)點(diǎn)數(shù)是63（葉子結(jié)點(diǎn)數(shù)減去1）。

二叉樹的前序遍歷、中序遍歷、后續(xù)遍歷：前中后三個詞是相對于根來講的，前序是【根-->左-->右】，中序是【左-->根-->右】，后續(xù)是【左-->右-->根】。具體操作為：先序遍歷（D L R）： 訪問根結(jié)點(diǎn)，按先序遍歷左子樹，按先序遍歷右子樹。

中序遍歷（L D R）： 按中序遍歷左子樹，訪問根結(jié)點(diǎn)，按中序遍歷右子樹。后序遍歷（L R D）： 按后序遍歷左子樹，按后序遍歷右子樹，訪問根結(jié)點(diǎn)。

下面以中序遍歷為例，來講解實(shí)際的解題方法：對一棵樹，將根結(jié)點(diǎn)下的左子樹用一個橢圓圈起來，右子樹也用一個橢圓圈起來。之后，在左子樹上標(biāo)記上1，在根結(jié)點(diǎn)標(biāo)記上2，在右子樹上標(biāo)記上3。

對在左邊橢圓內(nèi)的左子樹，現(xiàn)在把它單獨(dú)拿出來分析。把它的左子樹圈起來標(biāo)上1.1，根結(jié)點(diǎn)標(biāo)記上1.2，右子樹標(biāo)上1.3。

按照上述方法依次往下，直到樹不能拆分，然后按照“左-->根--->右”的順序?qū)懗鼋Y(jié)點(diǎn)的訪問先后即可。6、查找技術(shù)對于長度為n的線性表，順序查找最壞情況下需要比較n次。

（對數(shù)據(jù)是否有序沒有要求）?！?順序查找最好情況下查詢次數(shù)是1，最壞情況下是n，平均為（1+n）/2。

對于長度為n的有序線性表，二分法最壞情況下只需要比較log2n次。（數(shù)據(jù)必須有序）能用二分法進(jìn)行查找的是【順序存儲的有序線性表】。

7、排序技術(shù)對于長度為n的線性表，【冒泡排序、快速排序、簡單插入排序、簡單選擇排序】這四種排序方式在最壞情況下的比較次數(shù)相同，都是【n(n-1)/2】。堆排序的效率最高，是【nlog2n】。

★★ 希爾排序最壞情況下需要次比較【n1.5】。希爾排序?qū)儆凇静迦腩惻判蚍ā俊?/p>

已知數(shù)據(jù)表A中每個元素距最終位置不遠(yuǎn)，為節(jié)省時間，應(yīng)該采用的算法是【直接插入排序】。選擇排序、插入排序、快速排序、歸并排序中對內(nèi)存要求最大的是【歸并排序】。

第二部分 軟件工程基礎(chǔ) 1、軟件工程基本概念軟件是包括【程序】、【數(shù)據(jù)】及【相關(guān)文檔】的完整集合，軟件是一種邏輯產(chǎn)品。軟件工程三要素包括【方法、工具。

5.關(guān)于二級公共基礎(chǔ)知識

二級公共基礎(chǔ)知識考試大綱基 本 要 求（1）掌握算法的基本概念。

（2）掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作。（3）掌握基本排序和查找算法。

（4）掌握逐步求精的結(jié)構(gòu)化程序設(shè)計方法。（5）掌握軟件工程的基本方法，具有初步應(yīng)用相關(guān)技術(shù)進(jìn)行軟件開發(fā)的能力。

（6）掌握數(shù)據(jù)庫的基本知識，了解關(guān)系數(shù)據(jù)庫的設(shè)計。考 試 內(nèi) 容1. 基本數(shù)據(jù)結(jié)構(gòu)與算法（1）算法的基本概念：算法復(fù)雜度的概念和意義（時間復(fù)雜度與空間復(fù)雜度）。

（2）數(shù)據(jù)結(jié)構(gòu)的定義：數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。（3）線性表的定義：線性表的順序存儲結(jié)構(gòu)及其插入與刪除運(yùn)算。

（4）棧和隊(duì)列的定義：棧和隊(duì)列的順序存儲結(jié)構(gòu)及其基本運(yùn)算。（5）線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。

（6）樹的基本概念：二叉樹的定義及其存儲結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。（7）順序查找與二分法查找算法：基本排序算法（交換類排序，選擇類排序，插入類排序）。

2. 程序設(shè)計基礎(chǔ)（1）程序設(shè)計方法與風(fēng)格。（2）結(jié)構(gòu)化程序設(shè)計。

（3）面向?qū)ο蟮某绦蛟O(shè)計方法，對象，方法，屬性及繼承與多態(tài)性。3. 軟件工程基礎(chǔ)（1）軟件工程基本概念，軟件生命周期概念，軟件工具與軟件開發(fā)環(huán)境。

（2）結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。（3）結(jié)構(gòu)化設(shè)計方法，總體設(shè)計與詳細(xì)設(shè)計。

（4）軟件測試的方法，白盒測試與黑盒測試，測試用例設(shè)計，軟件測試的實(shí)施，單元測試、集成測試和系統(tǒng)測試。（5）程序的調(diào)試，靜態(tài)調(diào)試與動態(tài)調(diào)試。

4. 數(shù)據(jù)庫設(shè)計基礎(chǔ)（1）數(shù)據(jù)庫的基本概念：數(shù)據(jù)庫，數(shù)據(jù)庫管理系統(tǒng)，數(shù)據(jù)庫系統(tǒng)。（2）數(shù)據(jù)模型：實(shí)體聯(lián)系模型及E-R圖，從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。

（3）關(guān)系代數(shù)運(yùn)算：包括集合運(yùn)算及選擇、投影、連接運(yùn)算，數(shù)據(jù)庫規(guī)范化理論。（4）數(shù)據(jù)庫設(shè)計方法和步驟：需求分析、概念設(shè)計、邏輯設(shè)計和物理設(shè)計的相關(guān)策略。

考 試 方 式（1）公共基礎(chǔ)知識的考試方式為筆試，與C語言程序設(shè)計（C++語言程序設(shè)計、Java語言程序設(shè)計、Visual Basic語言程序設(shè)計、Visual FoxPro數(shù)據(jù)庫程序設(shè)計、Access數(shù)據(jù)庫程序設(shè)計或Delphi語言程序設(shè)計）的筆試部分合為一張?jiān)嚲怼９不A(chǔ)知識部分占全卷的30分。

（2）公共基礎(chǔ)知識有10道選擇題和5道填空題。

6.二級公共基礎(chǔ)知識該怎么復(fù)習(xí)就要考計算機(jī)二級了,公共

至少要把教材通讀兩遍，把該記住的知識點(diǎn)都記牢，并且加以復(fù)習(xí)鞏固。

可以根據(jù)考試大綱，對所做題型進(jìn)行適當(dāng)分類整理。也需要多做做往年的真題和模擬題了。

但是做這些題的時候不能大致看一眼，覺得自己會做就忽略不計，要反復(fù)練習(xí)，認(rèn)真分析，最好再加以總結(jié)。要熟練掌握其操作步驟，考前一定要再重新練習(xí)一遍操作。

因?yàn)榭荚囀怯袝r間限制的，考試時心情又比較緊張，如果不熟練的話，很容易導(dǎo)致時間不夠或者操作錯誤的時候亂了陣腳。全國計算機(jī)等級考試（，簡稱NCRE），是經(jīng)原國家教育委員會（現(xiàn)教育部）批準(zhǔn)，由教育部考試中心主辦，面向社會，用于考查應(yīng)試人員計算機(jī)應(yīng)用知識與技能的全國性計算機(jī)水平考試體系。

二級考核計算機(jī)基礎(chǔ)知識和使用一種高級計算機(jī)語言編寫程序以及上機(jī)調(diào)試的基本技能。

7.計算機(jī)國家二級公共基礎(chǔ)知識部分誰有資料啊

公共基礎(chǔ)知識 基本要求 1.掌握算法的基本概念。 2.掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作。 3.掌握基本排序和查找算法。 4.掌握逐步求精的結(jié)構(gòu)化程序設(shè)計方法。 5.掌握軟件工程的基本方法，具有初步應(yīng)用相關(guān)技術(shù)進(jìn)行軟件開發(fā)的能力。 6.掌握數(shù)據(jù)庫的基本知識，了解關(guān)系數(shù)據(jù)庫的設(shè)計。 考試內(nèi)容 一、基本數(shù)據(jù)結(jié)構(gòu)與算法 1.算法的基本概念；算法復(fù)雜度的概念和意義（時間復(fù)雜度與空間復(fù)雜度）。 2.數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。 3.線性表的定義；線性表的順序存儲結(jié)構(gòu)及其插入與刪除運(yùn)算。 4.棧和隊(duì)列的定義；棧和隊(duì)列的順序存儲結(jié)構(gòu)及其基本運(yùn)算。 5.線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。 6.樹的基本概念；二叉樹的定義及其存儲結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。 7.順序查找與二分法查找算法；基本排序算法（交換類排序，選擇類排序，插入類排序）。 二、程序設(shè)計基礎(chǔ) 1.程序設(shè)計方法與風(fēng)格 2.結(jié)構(gòu)化程序設(shè)計。 3.面向?qū)ο蟮某绦蛟O(shè)計方法，對象，方法，屬性及繼承與多態(tài)性。 三、軟件工程基礎(chǔ) 1.軟件工程基本概念，軟件生命周期概念，軟件工具與軟件開發(fā)環(huán)境。 2.結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。 3.結(jié)構(gòu)化設(shè)計方法，總體設(shè)計與詳細(xì)設(shè)計。 4.軟件測試的方法，白盒測試與黑盒測試，測試用例設(shè)計，軟件測試的實(shí)施，單元測試、集成測試和系統(tǒng)測試。 5.程序的調(diào)試，靜態(tài)調(diào)試與動態(tài)調(diào)試。 四、數(shù)據(jù)庫設(shè)計基礎(chǔ) 1.數(shù)據(jù)庫的基本概念：數(shù)據(jù)庫，數(shù)據(jù)庫管理系統(tǒng)，數(shù)據(jù)庫系統(tǒng)。 2.數(shù)據(jù)模型，實(shí)體聯(lián)系模型及E―R圖，從E―R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。 3.關(guān)系代數(shù)運(yùn)算，包括集合運(yùn)算及選擇、投影、連接運(yùn)算，數(shù)據(jù)庫規(guī)范化理 論。 4.數(shù)據(jù)庫設(shè)計方法和步驟：需求分析、概念設(shè)計、邏輯設(shè)計和物理設(shè)計的相關(guān)策略。 考試方式 1.公共基礎(chǔ)知識的考試方式為筆試，與C語言程序設(shè)計（C++語言程序設(shè)計、Java語言程序設(shè)計、Visual Basic語言程序設(shè)計、Visual FoxPro數(shù)據(jù)庫程序設(shè)計或Access數(shù)據(jù)庫程序設(shè)計）的筆試部分合為一張?jiān)嚲恚不A(chǔ)知識部分占全卷的30分。 2.公共基礎(chǔ)知識有l(wèi)0道選擇題和5道填空題。 C語言程序設(shè)計 基本要求 1.熟悉TURBO C集成環(huán)境。 2.熟練掌握結(jié)構(gòu)化程序設(shè)計的方法，具有良好的程序設(shè)計風(fēng)格。 3.掌握程序設(shè)計中簡單的數(shù)據(jù)結(jié)構(gòu)和算法。 4.TURBO C的集成環(huán)境下，能夠編寫簡單的C程序，并具有基本的糾錯和調(diào)試程序的能力。 考試內(nèi)容 一、C語言的結(jié)構(gòu) 1.程序的構(gòu)成，MAIN函數(shù)和其他函數(shù)。 2.頭文件，數(shù)據(jù)說明，函數(shù)的開始和結(jié)束標(biāo)志。 3.源程序的書寫格式。 4.C語言的風(fēng)格。 二、數(shù)據(jù)類型及其運(yùn)算 1.C的數(shù)據(jù)類型（基本類型，構(gòu)造類型，指針類型，空類型）及其定義方法。 2.C運(yùn)算符的種類、運(yùn)算優(yōu)先級和結(jié)合性。 3.不同類型數(shù)據(jù)間的轉(zhuǎn)換與運(yùn)算。 4.C表達(dá)式類型（賦值表達(dá)式，算術(shù)表達(dá)式，關(guān)系表達(dá)式，邏輯表達(dá)式，條件表達(dá)式，逗號表達(dá)式）和求值規(guī)則。 三、基本語句 1.表達(dá)式語句，空語句，復(fù)合語句。 2.數(shù)據(jù)的輸入與輸出，輸入輸出函數(shù)的調(diào)用。 3.復(fù)合語句。 4.GOTO語句和語句標(biāo)號的使用。 四、選擇結(jié)構(gòu)程序設(shè)計 1.用IF語句實(shí)現(xiàn)選擇結(jié)構(gòu)。 2.用SWITCH語句實(shí)現(xiàn)多分支選擇結(jié)構(gòu)。 3.選擇結(jié)構(gòu)的嵌套。 五、循環(huán)結(jié)構(gòu)程序設(shè)計 1.FOR循環(huán)結(jié)構(gòu)。 2.WHILE和DO WHILE循環(huán)結(jié)構(gòu)。 3.CONTINUE語句和BREAK語句。 4.循環(huán)的嵌套。 六、數(shù)組的定義和引用 1.一維數(shù)組和多維數(shù)組的定義、初始化和引用 2.字符串與字符數(shù)組。 七、函數(shù) 1.庫函數(shù)的正確調(diào)用。 2.函數(shù)的定義方法。 3.函數(shù)的類型和返回值。 4.形式參數(shù)與實(shí)在參數(shù)，參數(shù)值的傳遞。 5.函數(shù)的正確調(diào)用，嵌套調(diào)用，遞歸調(diào)用。 6.局部變量和全局變量。 7.變量的存儲類別（自動，靜態(tài)，寄存器，外部），變量的作用域和生存期。 8.內(nèi)部函數(shù)與外部函數(shù)。 八、編譯預(yù)處理 1.宏定義：不帶參數(shù)的宏定義；帶參數(shù)的宏定義。 2.“文件包含”處理。 九、指針 1.指針與指針變量的概念，指針與地址運(yùn)算符。 2.變量、數(shù)組、字符串、函數(shù)、結(jié)構(gòu)體的指針以及指向變量、數(shù)組、字符串、函數(shù)、結(jié)構(gòu)體的指針變量