計算機二級公共基礎知識總結***2***

　　1.5 線性連結串列

　　資料結構中的每一個結點對應於一個儲存單元，這種儲存單元稱為儲存結點，簡稱結點。 結點由兩部分組成：***1***用於儲存資料元素值，稱為資料域;***2***用於存放指標，稱為指標域，用於指向前一個或後一個結點。 在鏈式儲存結構中，儲存資料結構的儲存空間可以不連續，各資料結點的儲存順序與資料元素之間的邏輯關係可以不一致，而資料元素之間的邏輯關係是由指標域來確定的。 鏈式儲存方式即可用於表示線性結構，也可用於表示非線性結構。

　　線性連結串列，HEAD稱為頭指標，HEAD=NULL***或0***稱為空表，如果是兩指標：左指標***Llink***指向前件結點，右指標***Rlink***指向後件結點。

　　線性連結串列的基本運算：查詢、插入、刪除。

　　1.6 樹與二叉樹

　　樹是一種簡單的非線性結構，所有元素之間具有明顯的層次特性。

　　在樹結構中，每一個結點只有一個前件，稱為父結點，沒有前件的結點只有一個，稱為樹的根結點，簡稱樹的根。每一個結點可以有多個後件，稱為該結點的子結點。沒有後件的結點稱為葉子結點。

　　在樹結構中，一個結點所擁有的後件的個數稱為該結點的度，所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。

　　二叉樹的特點：***1***非空二叉樹只有一個根結點;***2***每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。

　　二叉樹的基本性質：

　　***1***在二叉樹的第k層上，最多有2k-1***k≥1***個結點; ***2***深度為m的二叉樹最多有2m-1個結點;

　　***3***度為0的結點***即葉子結點***總是比度為2的結點多一個; ***4***具有n個結點的二叉樹，其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數部分;

　　***5***具有n個結點的完全二叉樹的深度為[log2n]+1;

　　***6***設完全二叉樹共有n個結點。如果從根結點開始，按層序***每一層從左到右***用自然數1，2，„.n給結點進行編號***k=1,2„.n***，有以下結論：

　　①若k=1，則該結點為根結點，它沒有父結點;若k>1，則該結點的父結點編號為INT***k/2***;

　　②若2k≤n，則編號為k的結點的左子結點編號為2k;否則該結點無左子結點***也無右子結點***;

　　③若2k+1≤n，則編號為k的結點的右子結點編號為2k+1;否則該結點無右子結點。 滿二叉樹是指除最後一層外，每一層上的所有結點有兩個子結點，則k層上有2k-1個結點深度為m的滿二叉樹有2m-1個結點。

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

　　二叉樹儲存結構採用鏈式儲存結構，對於滿二叉樹與完全二叉樹可以按層序進行順序儲存。

　　二叉樹的遍歷：

　　***1***前序遍歷***DLR***，首先訪問根結點，然後遍歷左子樹，最後遍歷右子樹; ***2***中序遍歷***LDR***，首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹; ***3***後序遍歷***LRD***首先遍歷左子樹，然後訪問遍歷右子樹，最後訪問根結點。

　　1.7 查詢技術

　　順序查詢的使用情況： ***1***線性表為無序表; ***2***表採用鏈式儲存結構。

　　二分法查詢只適用於順序儲存的有序表，對於長度為n的有序線性表，最壞情況只需比較log2n次。

　　1.8 排序技術

　　排序是指將一個無序序列整理成按值非遞減順序排列的有序序列。

　　交換類排序法：***1***氣泡排序法，需要比較的次數為n***n-1***/2; ***2***快速排序法。 插入類排序法：***1***簡單插入排序法，最壞情況需要n***n-1***/2次比較;***2***希爾排序法，最壞情況需要O***n1.5***次比較。

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

　　計算機二級總結：程式設計基礎

　　2.1 程式設計設計方法和風格

　　如何形成良好的程式設計風格 1、源程式文件化; 2、資料說明的方法; 3、語句的結構; 4、輸入和輸出。

　　註釋分序言性註釋和功能性註釋，語句結構清晰第一、效率第二。

　　2.2 結構化程式設計

　　結構化程式設計方法的四條原則是：1. 自頂向下;2. 逐步求精;3.模組化;4.限制使用goto語句。

　　結構化程式的基本結構和特點：

　　***1***順序結構：一種簡單的程式設計，最基本、最常用的結構;

　　***2***選擇結構：又稱分支結構，包括簡單選擇和多分支選擇結構，可根據條件，判斷應該選擇哪一條分支來執行相應的語句序列;

　　***3***重複結構：又稱迴圈結構，可根據給定條件，判斷是否需要重複執行某一相同程式段。

　　2.3 面向物件的程式設計

　　面向物件的程式設計：以60年代末挪威奧斯陸大學和挪威計算機中心研製的SIMULA語言為標誌。

　　面向物件方法的優點：

　　***1***與人類習慣的思維方法一致; ***2***穩定性好; ***3***可重用性好;

　　***4***易於開發大型軟體產品; ***5***可維護性好。

　　物件是面向物件方法中最基本的概念，可以用來表示客觀世界中的任何實體，物件是實體的抽象。面向物件的程式設計方法中的物件是系統中用來描述客觀事物的一個實體，是構成系統的一個基本單位，由一組表示其靜態特徵的屬性和它可執行的一組操作組成。

　　屬性即物件所包含的資訊，操作描述了物件執行的功能，操作也稱為方法或服務。 物件的基本特點： ***1***標識惟一性; ***2***分類性; ***3***多型性; ***4***封裝性;

　　***5***模組獨立性好。

　　類是指具有共同屬性、共同方法的物件的集合。所以類是物件的抽象，物件是對應類的一個例項。

　　訊息是一個例項與另一個例項之間傳遞的資訊。

　　訊息的組成包括***1***接收訊息的物件的名稱;***2***訊息識別符號，也稱訊息名; ***3***零個或多個引數。

　　繼承是指能夠直接獲得已有的性質和特徵，而不必重複定義他們。 繼承分單繼承和多重繼承。單繼承指一個類只允許有一個父類，多重繼承指一個類允許有多個父類。

　　多型性是指同樣的訊息被不同的物件接受時可導致完全不同的行動的現象。

計算機二級公共基礎知識總結“的人還看了：