公共基礎知識復習資料(含例題詳解) - 下載本文

买足球彩票技巧 www.lbmkq.icu

公共基礎知識資料

第一章 數據結構與算法

【考點1】算法的基本概念

算法:是指一組有窮的指令集,是解題方案的準確而完整的描述。算法不等于程序,也不等于計算方法。 算法的基本特征:

確定性,算法中每一步驟都必須有明確定義,不允許有多義性;

有窮性,算法必須能在有限的時間內做完,即能在執行有限個步驟后終止; 可行性,算法原則上能夠精確地執行; 擁有足夠的情報。

算法的組成要素:一個算法由數據對象的運算和操作以及其控制結構這兩部分組成。 算法的基本運算和操作:算術運算,邏輯運算,關系運算,數據傳輸。 算法的基本控制結構:順序,選擇,循環。

算法基本設計方法:列舉法、歸納法、遞推、遞歸、減半遞推技術。 【考點2】算法的復雜度

算法效率的度量——算法的復雜度:時間復雜度和空間復雜度。 算法時間復雜度:指執行算法所需要的計算工作量。通常,一個算法所用的時間包括編譯時間和運行時間。 算法空間復雜度:指執行這個算法所需要的內存空間。包括算法程序所占的空間,輸入的初始數據所占的空間,算法執行過程中所需的額外空間。 空間復雜度和時間復雜度并不相關。

(4)算法的空間復雜度是指

A)算法在執行過程中所需要的計算機存儲空間 B)算法所處理的數據量 C)算法程序中的語句或指令條數 D)算法在執行過程中所需要的臨時工作單元數 【考點3】數據結構的基本概念

數據:數據是客觀事物的符號表示,是能輸入到計算機中并被計算程序識別和處理的符號的總稱,如文檔,聲音,視頻等。

數據元素:數據元素是數據的基本單位。

數據對象:數據對象是性質相同的數據元素的集合。

數據結構:是指由某一數據對象中所有數據成員之間的關系組成的集合。

【考點4】邏輯結構和存儲結構

數據結構可分為數據的邏輯結構和存儲結構。

數據的邏輯結構是對數據元素之間的邏輯關系的描述,與數據的存儲無關,是面向問題的,是獨立于計算機的。它包括數據對象和數據對象之間的關系。

數據的存儲結構也稱為數據的物理結構,是數據在計算機中的存放的方式,是面向計算機的,它包括數據元素的存儲方式和關系的存儲方式。

數據結構和邏輯結構的關系:一種數據的邏輯結構可以表示成多種存儲結構即數據的邏輯結構和存儲結構不一定一一對應。

常見的存儲結構有:順序,鏈接,索引等。采用不同的存儲結構其數據處理的效率是不同的。 【考點5】線性結構和非線性結構

線性結構的條件(一個非空數據結構):(1)有且只有一個根結點;(2)每一個結點最多有一個前件,也最多有一個后件。

非線性結構:不滿足線性結構條件的數據結構。

棧、隊列、雙向鏈表是線性結構,樹、二叉樹為非線性結構。 【考點6】線性表及其順序存儲結構

線性表是由一組數據元素構成,數據元素的位置只取決于自己的序號,元素之間的相對位置是線性的。 在復雜線性表中,由若干項數據元素組成的數據元素稱為記錄;由多個記錄構成的線性表稱為文件。 非空線性表的結構特征:

(1)有且只有一個根結點a1,它無前件;

(2)有且只有一個終端結點an,它無后件;

(3)除根結點與終端結點外,其他所有結點有且只有一個前件,也有且只有一個后件。 結點個數n稱為線性表的長度,當n=0時,稱為空表。 線性表的順序存儲結構具有以下兩個基本特點: (1)線性表中所有元素所占的存儲空間是連續的;

(2)線性表中各數據元素在存儲空間中是按邏輯順序依次存放的。

元素ai的存儲地址為:ADR(ai)=ADR(a1)+(i-1)*k,ADR(a1)為第一個元素的地址,k代表每個元素占的字節數。 順序表的運算:查找、插入、刪除。 【考點7】線性鏈表

線性鏈表是線性表的鏈式存儲結構,數據結構中的每一個結點對應于一個存儲單元,這種存儲單元稱為存儲結點,簡稱結點。結點由兩部分組成:(1) 用于存儲數據元素值,稱為數據域;(2) 用于存放指針,稱為指針域,用于指向前一個或后一個結點。

在鏈式存儲結構中,存儲數據結構的存儲空間可以不連續,各數據結點的存儲順序與數據元素之間的邏輯關系可以不一致,而數據元素之間的邏輯關系是由指針域來確定的。

鏈式存儲方式既可用于表示線性結構,也可用于表示非線性結構。 線性單鏈表中,HEAD稱為頭指針,HEAD=NULL(或0)稱為空表。

雙向鏈表有兩個指針:左指針(Llink)指向前件結點,右指針(Rlink)指向后件結點。

循環鏈表:循環鏈表與單鏈表的不同的是它的最后一個結點的指針域存放的事指向第一個結點的指針而單鏈表存放的是空指針。

線性鏈表的基本運算:查找、插入、刪除。 【考點8】棧 1、棧的基本概念

棧是一種特殊的線性表,只允許在表的一端進行插入和刪除的線性表;插入,刪除的一端為棧頂,另一端為棧底;當表中沒有元素時為空棧。

棧是一種后進先出(或先進后出Last In First Out)的線性表。棧具有記憶功能。棧的實例:火車調度,子彈夾。

2、棧的存儲結構

順序存儲結構:用一組地址連續的存儲單元即一維數組來存儲; 鏈式存儲:用線性鏈表來存儲; 3、棧的基本運算

(1) 入棧運算,在棧頂位置插入元素;

(2) 退棧運算,刪除元素(取出棧頂元素并賦給一個指定的變量); (3) 讀棧頂元素,將棧頂元素賦給一個指定的變量,此時指針無變化。

(1)假設一個長度為50的數組(數組元素的下標從0到49)作為棧的存儲空間,棧底指針bottom指向棧底元素,棧頂指針top指向棧頂元素,如果bottom=49,top=30(數組下標),則棧中具有【1】個元素。 (2)下列數據結果中,能夠按照“先進后出”原則存取數據的是 A) 循環隊列

B) 棧

C)隊列 D)二叉樹

(1)下列敘述中正確的是

A)棧是“先進先出”的線性表 B)隊列是“先進先出”的線性表 C)循環隊列是非線性結構

D)有序性表既可以采用順序存儲結構,也可以采用鏈式存儲結構

(1)一個棧的初始狀態為空。現將元素1、2、3、4、5、A、B、C、D、E 依次入棧,然后 再依次出棧,則元素出棧的順序是( )。

A)12345ABCDE B)EDCBA54321 C)ABCDE12345 D)54321EDCBA 【考點9】隊列

1.隊列的基本概念

隊列是一種特殊的線性表,只允許在表的一端插入,在另一端刪除,允許插入的一端是隊尾(rear),允許刪除的一端為隊頭(front);當表中沒有元素是空隊列;隊列是一種先進先出的線性表。(FIFO) 2、隊列的存儲結構 順序存儲:一維數組。 鏈式存儲:線性鏈表。 3、隊列的運算:

(1) 入隊運算:從隊尾插入一個元素; (2) 退隊運算:從隊頭刪除一個元素。

隊列的順序存儲結構一般采用循環隊列的形式。循環隊列s=0表示隊列為空;s=1且front=rear表示隊滿。 計算循環隊列的元素個數:“尾指針減頭指針”,若為負數,再加其容量即可。 (3)對于循環隊列,下列敘述中正確的是 A)隊頭指針是固定不變的 B)隊頭指針一定大于隊尾指針 C)隊頭指針一定小于隊尾指針

D)隊頭指針可以大于隊尾指針,也可以小于隊尾指針 (2)下列敘述中正確的是( )。

A)循環隊列有隊頭和隊尾兩個指針,因此,循環隊列是非線性結構

B)在循環隊列中,只需要隊頭指針就能反映隊列中元素的動態變化情況 C)在循環隊列中,只需要隊尾指針就能反映隊列中元素的動態變化情況 D)循環隊列中元素的個數是由隊頭指針和隊尾指針共同決定

【考點10】樹的基本概念

樹是一種非線性結構,是n個結點的有限集。當n=0 時為空樹,n>0時為非空樹。結點的度:結點所擁有的子樹的個數。

葉子結點:度為0的結點。

分支結點:除葉子結點以外的結點。

結點的層次:根結點在第一層,同一層上左右結點的子結點在下一層。 樹的深度:所處層次最大的那個結點的層次。 樹的度:樹中所有結點的度的最大值。 【考點11】二叉樹及其基本性質 1、二叉樹的概念

二叉樹是一種特殊的樹形結構,每個結點最多只有兩棵子樹,且有左右之分不能互換,因此,二叉樹有五種不同的形態。

2、二叉樹的性質

性質1 在二叉樹的第k層上,最多有2k-1(k≥1)個結點。 性質2 深度為m的二叉樹最多有2m-1個結點。

性質3 在任意一棵二叉樹中,度為0的結點(葉子結點)總是比度為2的結點多一個。

性質4 具有n個結點的二叉樹,其深度不小于[log2n]+1,其中[log2n]表示為log2n的整數部分。 3、二叉樹的存儲結構。

(1)下列數據結構中,屬于非線性結構的是 A)循環隊列 B) 帶鏈隊列 C) 二叉樹 D)帶鏈棧

(3)某二叉樹有5個度為2的結點,則該二叉樹中的葉子結點數是

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

(1)某二叉樹有5個度為2的結點以及3個度為1的結點,則該二叉樹中共有 【1】 個結點。 【考點12】滿二叉樹與完全二叉樹

滿二叉樹:除最后一層外,每一層上的所有結點都有兩個子結點。在滿二叉樹中,每一層上的結點數都達到最大值,即在滿二叉樹的第k層上有2k-1個結點,且深度為m的滿二叉樹有2m-1個結點。

完全二叉樹是指這樣的二叉樹:除最后一層外,每一層上的結點數均達到最大值;在最后一層上只缺少右邊的若干結點。

滿二叉樹是完全二叉樹,而完全二叉樹一般不是滿二叉樹。 【考點13】完全二叉樹的性質

性質1 具有n個結點的完全二叉樹的深度為[log2n]+1。 性質2 完全二叉樹中度為1的結點數為0或1。

(1)設一棵完全二叉樹共有700個結點,則在該二叉樹中有 【1】 個葉子結點。

(1)【1】 350 【解析】 完全二叉樹中,設高度為n,則除h層外其它層結點數都到達最大,可以算出h=10,1至9層結點個數為2^9-1=511,最后一層結點個數為700-511=189個,189/2=95,除最后一層外共有結點2^(9-1)-95=161個,所以所有的結點個數為:189+161=350個。

【考點14】二叉樹的遍歷

前序遍歷:先訪問根結點、然后遍歷左子樹,最后遍歷右子樹;并且,在遍歷左、右子樹時,仍然先訪問根結點,然后遍歷左子樹,最后遍歷右子樹。

中序遍歷:先遍歷左子樹、然后訪問根結點,最后遍歷右子樹;并且,在遍歷左、右子樹時,仍然先遍歷左子樹,然后訪問根結點,最后遍歷右子樹。

后序遍歷:先遍歷左子樹、然后遍歷右子樹,最后訪問根結點;并且,在遍歷左、右子樹時,仍然先遍歷左子樹,然后遍歷右子樹,最后訪問根結點。

【考點15】順序查找

順序查找是從表的一端開始,依次掃描表中的各個元素,并與所要查找的數進行比較。 在下列兩種情況下也只能采用順序查找:

(1)如果線性表為無序表,則不管是順序存儲結構還是鏈式存儲結構,只能用順序查找。 (2)即使是有序線性表,如果采用鏈式存儲結構,也只能用順序查找。 【考點16】二分查找

二分查找的條件:(1)用順序存儲結構 (2)線性表是有序表。

對于長度為n的有序線性表,在最壞情況下,二分法查找只需比較log2n次,而順序查找需要比較n次。

(3)在長度為n 的有序線性表中進行二分查找,最壞情況下需要比較的次數是( )。 A)O(n) B)O(n2) C)O(log2n) D)O(nlog2n) 【考點17】排序 1、交換排序

(1)冒泡排序法,在最壞的情況下,冒泡排序需要比較次數為n(n-1)/2。 (2)快速排序法 ,在最壞的情況下,快速排序需要比較次數為n(n-1)/2。 2、插入類排序法:

(1)簡單插入排序法,最壞情況需要n(n-1)/2次比較; (2)希爾排序法,最壞情況需要O(n1.5)次比較。(大寫O是算法復雜度的表示方法) 3、選擇類排序法:

(1)簡單選擇排序法,最壞情況需要n(n-1)/2次比較; (2)堆排序法,最壞情況需要O(nlog2n)次比較。

相比以上幾種(除希爾排序法外),堆排序法的時間復雜度最小。

(4)下列排序方法中,最壞情況下比較次數最少的是 A)冒泡排序 B)簡單選擇排序 C)直接插入排序 D)堆排序

第二章 程序設計基礎

【考點1】程序設計方法與風格

形成良好的程序設計風格需注意:

1、源程序文檔化; 2、數據說明的方法; 3、語句的結構; 4、輸入和輸出。