二分查找流程圖演算法

㈠ 折半查找法在Excel函數中的運用

排序與查找不管是在Excel領域，還是其他領域，例如C語言，都有著很高的使用率。學會了這個技能，我們做起事情來更加方便快捷，省去不少時間，效率倍增。下面我們就來介紹一下折半查找在Excel函數裡面的運用。
折半查找
又稱之為二分查找，它要求目標數組中的數據是有序排列的。優點是比較次數少，查找速度快，平均性能好，適用於不經常變動而查找頻繁的有序列表。下面先來看看下面的流程圖。
為了便於大家理解，我作幾點說明：
①將需要查找的值與中間值（也叫做中位值）進行對比；
②大於中位值時，以中位作為邊界，繼續在其右側取新的中位值繼續對比；
③小於中位值時，以中位作為邊界，繼續在其左側取新的中位值繼續對比；
④等於中位值時，依次判斷其右側數值是否繼續相等，直到不相等時返回最後一個相等的數值；
⑤當中位位置與邊界重疊時，中止對比，此時如果查找值大於中位值，則返回中位值；如果查找值小於中位值，則返回中位左側數值。如果左側數值不存在，返回#N/A。
流程圖大致的介紹就是如此，不知道我描述是不是清楚，這只是一個演算法而已，不懂也不需要太過深入研究。當數據個數為偶數時，中位等於個數除以2；數據個數為奇數時，中位等於除以2
案例剖析
①如下圖所示，給出了一連串升序排列的數組，我們要找出33這個數。按照上面的介紹，我們知道中位值為24.
②第一次比較，因為33>24，所以鎖定第二次查找范圍在中位值的後面，而不是前面，前面的數字都比24小，不可能找得到33.
③第二次比較，中位值變為了31,33>31，繼續找後面的。
④依次類推，直到找到數字或者整個數組被查找完畢，沒有找到則會返回#N/A
現在或許大家還在疑問為什麼要是一個有序的序列才可以進行折半查找？下面這張圖，與之前的圖對比一下，你就知道了。
Excel中也有類似的函數，LOOKUP，我們要查找74，但是用LOOKUP函數計算出來的結果卻是49，下面就來分析一下。
①第一次比較74小於116，所以開始往前查找。
②中位值變為50.74大於50，向後查找。
③74又大於47，依舊向後。
④最後只剩下一個49了，這就是函數的返回值。

㈡ 全國計算機等級考試二級C,VB等等不同語言筆試部分的公共基礎知識考試內容是一樣的嗎

第一章 數據結構與演算法
經過對部分考生的調查以及對近年真題的總結分析，筆試部分經常考查的是演算法復雜度、數據結構的概念、棧、二叉樹的遍歷、二分法查找，讀者應對此部分進行重點學習。
詳細重點學習知識點：
1．演算法的概念、演算法時間復雜度及空間復雜度的概念
2．數據結構的定義、數據邏輯結構及物理結構的定義
3．棧的定義及其運算、線性鏈表的存儲方式
4．樹與二叉樹的概念、二叉樹的基本性質、完全二叉樹的概念、二叉樹的遍歷
5．二分查找法
6．冒泡排序法

1.1演算法
考點1 演算法的基本概念
考試鏈接：
考點1在筆試考試中考核的幾率為30%，主要是以填空題的形式出現，分值為2分，此考點為識記內容，讀者還應該了解演算法中對數據的基本運算。
計算機解題的過程實際上是在實施某種演算法，這種演算法稱為計算機演算法。
1．演算法的基本特徵：可行性、確定性、有窮性、擁有足夠的情報。
2．演算法的基本要素：
（1）演算法中對數據的運算和操作
一個演算法由兩種基本要素組成：一是對數據對象的運算和操作；二是演算法的控制結構。
在一般的計算機系統中，基本的運算和操作有以下4類：算術運算、邏輯運算、關系運算和數據傳輸。
（2）演算法的控制結構：演算法中各操作之間的執行順序稱為演算法的控制結構。
描述演算法的工具通常有傳統流程圖、N-S結構化流程圖、演算法描述語言等。一個演算法一般都可以用順序、選擇、循環3種基本控制結構組合而成。
考點2 演算法復雜度
考試鏈接：
考點2在筆試考試中，是一個經常考查的內容，在筆試考試中出現的幾率為70%，主要是以選擇的形式出現，分值為2分，此考點為重點識記內容，讀者還應該識記演算法時間復雜度及空間復雜度的概念。
1.演算法的時間復雜度
演算法的時間復雜度是指執行演算法所需要的計算工作量。
同一個演算法用不同的語言實現，或者用不同的編譯程序進行編譯，或者在不同的計算機上運行，效率均不同。這表明使用絕對的時間單位衡量演算法的效率是不合適的。撇開這些與計算機硬體、軟體有關的因素，可以認為一個特定演算法"運行工作量"的大小，只依賴於問題的規模（通常用整數n表示），它是問題規模的函數。即
演算法的工作量=f（n）
2.演算法的空間復雜度
演算法的空間復雜度是指執行這個演算法所需要的內存空間。
一個演算法所佔用的存儲空間包括演算法程序所佔的空間、輸入的初始數據所佔的存儲空間以及演算法執行過程中所需要的額外空間。其中額外空間包括演算法程序執行過程中的工作單元以及某種數據結構所需要的附加存儲空間。如果額外空間量相對於問題規模來說是常數，則稱該演算法是原地工作的。在許多實際問題中，為了減少演算法所佔的存儲空間，通常採用壓縮存儲技術，以便盡量減少不必要的額外空間。

疑難解答：演算法的工作量用什麼來計算？
演算法的工作量用演算法所執行的基本運算次數來計算，而演算法所執行的基本運算次數是問題規模的函數，即演算法的工作量=f（n），其中n是問題的規模。
1.2數據結構的基本概念
考點3 數據結構的定義
考試鏈接：
考點3在筆試考試中，是一個經常考查的內容，在筆試考試中出現的幾率為70%，主要是以選擇的形式出現，分值為2分，此考點為識記內容，讀者還應該識記數據的邏輯結構和存儲結構的概念。
數據結構作為計算機的一門學科，主要研究和討論以下三個方面：
（1）數據集合中個數據元素之間所固有的邏輯關系，即數據的邏輯結構；
（2）在對數據元素進行處理時，各數據元素在計算機中的存儲關系，即數據的存儲結構；
（3）對各種數據結構進行的運算。
數據：是對客觀事物的符號表示，在計算機科學中是指所有能輸入到計算機中並被計算機程序處理的符號的總稱。
數據元素：是數據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。
數據對象：是性質相同的數據元素的集合，是數據的一個子集。
數據的邏輯結構是對數據元素之間的邏輯關系的描述，它可以用一個數據元素的集合和定義在此集合中的若干關系來表示。數據的邏輯結構有兩個要素：一是數據元素的集合，通常記為D；二是D上的關系，它反映了數據元素之間的前後件關系，通常記為R。一個數據結構可以表示成
B=（D，R）
其中B表示數據結構。為了反映D中各數據元素之間的前後件關系，一般用二元組來表示。
數據的邏輯結構在計算機存儲空間中的存放形式稱為數據的存儲結構（也稱數據的物理結構）。
由於數據元素在計算機存儲空間中的位置關系可能與邏輯關系不同，因此，為了表示存放在計算機存儲空間中的各數據元素之間的邏輯關系（即前後件關系），在數據的存儲結構中，不僅要存放各數據元素的信息，還需要存放各數據元素之間的前後件關系的信息。
一種數據的邏輯結構根據需要可以表示成多種存儲結構，常用的存儲結構有順序、鏈接、索引等存儲結構。而採用不同的存儲結構，其數據處理的效率是不同的。因此，在進行數據處理時，選擇合適的存儲結構是很重要的。
考點4 線性結構與非線性結構
考試鏈接：
考點4在筆試考試中，雖然說不是考試經常考查的內容，但讀者還是對此考點有所了解，在筆試考試中出現的幾率為30%，主要是以填空題出現的形式出現，分值為2分，此考點為識記內容。
根據數據結構中各數據元素之間前後件關系的復雜程度，一般將數據結構分為兩大類型：線性結構與非線性結構。如果一個非空的數據結構滿足下列兩個條件：
（1）有且只有一個根結點；
（2）每一個結點最多有一個前件，也最多有一個後件。
則稱該數據結構為線性結構。線性結構又稱線性表。在一個線性結構中插入或刪除任何一個結點後還應是線性結構。如果一個數據結構不是線性結構，則稱之為非線性結構。

疑難解答：空的數據結構是線性結構還是非線性結構？
一個空的數據結構究竟是屬於線性結構還是屬於非線性結構，這要根據具體情況來確定。如果對該數據結構的演算法是按線性結構的規則來處理的，則屬於線性結構；否則屬於非線性結構。
1.3棧及線性鏈表
考點5 棧及其基本運算
考試鏈接：
考點5在筆試考試中，是一個必考的內容，在筆試考試中出現的幾率為100%，主要是以選擇的形式出現，分值為2分，此考點為重點掌握內容，讀者應該掌握棧的運算 。
1．棧的基本概念
棧是限定只在一端進行插入與刪除的線性表，通常稱插入、刪除的這一端為棧頂，另一端為棧底。當表中沒有元素時稱為空棧。棧頂元素總是後被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入的元素，從而也是最後才能被刪除的元素。棧是按照"先進後出"或"後進先出"的原則組織數據的。
2．棧的順序存儲及其運算
用一維數組S（1∶m）作為棧的順序存儲空間，其中m為最大容量。
在棧的順序存儲空間S（1∶m）中，S（bottom）為棧底元素，S（top）為棧頂元素。top=0表示棧空；top=m表示棧滿。
棧的基本運算有三種：入棧、退棧與讀棧頂元素。
（1）入棧運算：入棧運算是指在棧頂位置插入一個新元素。首先將棧頂指針加一（即top加1），然後將新元素插入到棧頂指針指向的位置。當棧頂指針已經指向存儲空間的最後一個位置時，說明棧空間已滿，不可能再進行入棧操作。這種情況稱為棧"上溢"錯誤。
（2）退棧運算：退棧是指取出棧頂元素並賦給一個指定的變數。首先將棧頂元素（棧頂指針指向的元素）賦給一個指定的變數，然後將棧頂指針減一（即top減1）。當棧頂指針為0時，說明棧空，不可進行退棧操作。這種情況稱為棧的"下溢"錯誤。
（3）讀棧頂元素：讀棧頂元素是指將棧頂元素賦給一個指定的變數。這個運算不刪除棧頂元素，只是將它賦給一個變數，因此棧頂指針不會改變。當棧頂指針為0時，說明棧空，讀不到棧頂元素。

小技巧：棧是按照"先進後出"或"後進先出"的原則組織數據，但是出棧方式有多種選擇，在考題中經常考查各種不同的出棧方式。
考點6 線性鏈表的基本概念
考試鏈接：
考點6在筆試考試中出現的幾率為30%，主要是以選擇的形式出現，分值為2分，此考點為識記內容。重點識記結點的組成。
在鏈式存儲方式中，要求每個結點由兩部分組成：一部分用於存放數據元素值，稱為數據域，另一部分用於存放指針，稱為指針域。其中指針用於指向該結點的前一個或後一個結點（即前件或後件）。
鏈式存儲方式既可用於表示線性結構，也可用於表示非線性結構。
（1）線性鏈表
線性表的鏈式存儲結構稱為線性鏈表。
在某些應用中，對線性鏈表中的每個結點設置兩個指針，一個稱為左指針，用以指向其前件結點；另一個稱為右指針，用以指向其後件結點。這樣的表稱為雙向鏈表。
（2）帶鏈的棧
棧也是線性表，也可以採用鏈式存儲結構。帶鏈的棧可以用來收集計算機存儲空間中所有空閑的存儲結點，這種帶鏈的棧稱為可利用棧。

疑難解答：在鏈式結構中，存儲空間位置關系與邏輯關系是什麼？
在鏈式存儲結構中，存儲數據結構的存儲空間可以不連續，各數據結點的存儲順序與數據元素之間的邏輯關系可以不一致，而數據元素之間的邏輯關系是由指針域來確定的。
1.4樹與二叉樹
考點7 樹與二叉樹及其基本性質
考試鏈接：
考點7在筆試考試中，是一個必考的內容，在筆試考試中出現的幾率為100%，主要是以選擇的形式出現，有時也有出現在填空題中，分值為2分，此考點為重點掌握內容。重點識記樹及二叉樹的性質。
誤區警示：
滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。應該注意二者的區別。
1、樹的基本概念
樹(tree）是一種簡單的非線性結構。在樹結構中，每一個結點只有一個前件，稱為父結點，沒有前件的結點只有一個，稱為樹的根結點。每一個結點可以有多個後件，它們稱為該結點的子結點。沒有後件的結點稱為葉子結點。
在樹結構中，一個結點所擁有的後件個數稱為該結點的度。葉子結點的度為0。在樹中，所有結點中的最大的度稱為樹的度。
2、二叉樹及其基本性質
（1）二叉樹的定義
二叉樹是一種很有用的非線性結構，具有以下兩個特點：
①非空二叉樹只有一個根結點；
②每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹和右子樹。
由以上特點可以看出，在二叉樹中，每一個結點的度最大為2，即所有子樹（左子樹或右子樹）也均為二叉樹，而樹結構中的每一個結點的度可以是任意的。另外，二叉樹中的每個結點的子樹被明顯地分為左子樹和右子樹。在二叉樹中，一個結點可以只有左子樹而沒有右子樹，也可以只有右子樹而沒有左子樹。當一個結點既沒有左子樹也沒有右子樹時，該結點即為葉子結點。
（2）二叉樹的基本性質
二叉樹具有以下幾個性質：
性質1：在二叉樹的第k層上，最多有2k-1（k≥1）個結點；
性質2：深度為m的二叉樹最多有2m-1個結點；
性質3：在任意一棵二叉樹中，度為0的結點（即葉子結點）總是比度為2的結點多一個。
性質4：具有n個結點的二叉樹，其深度至少為〔log2n〕+1，其中〔log2n〕表示取log2n的整數部分。

小技巧：在二叉樹的遍歷中，無論是前序遍歷，中序遍歷還是後序遍歷，二叉樹的葉子結點的先後順序都是不變的。
3、滿二叉樹與完全二叉樹
滿二叉樹是指這樣的一種二叉樹：除最後一層外，每一層上的所有結點都有兩個子結點。在滿二叉樹中，每一層上的結點數都達到最大值，即在滿二叉樹的第k層上有2k-1個結點，且深度為m的滿二叉樹有2m－1個結點。
完全二叉樹是指這樣的二叉樹：除最後一層外，每一層上的結點數均達到最大值；在最後一層上只缺少右邊的若干結點。
對於完全二叉樹來說，葉子結點只可能在層次最大的兩層上出現：對於任何一個結點，若其右分支下的子孫結點的最大層次為p，則其左分支下的子孫結點的最大層次或為p，或為p+1。
完全二叉樹具有以下兩個性質：
性質5:具有n個結點的完全二叉樹的深度為〔log2n〕+1。
性質6:設完全二叉樹共有n個結點。如果從根結點開始，按層次（每一層從左到右）用自然數1，2，……，n給結點進行編號，則對於編號為k（k=1，2，……，n）的結點有以下結論：
①若k=1，則該結點為根結點，它沒有父結點；若k>1，則該結點的父結點編號為INT（k/2）。
②若2k≤n，則編號為k的結點的左子結點編號為2k；否則該結點無左子結點（顯然也沒有右子結點）。
③若2k+1≤n，則編號為k的結點的右子結點編號為2k+1；否則該結點無右子結點。
考點8 二叉樹的遍歷
考試鏈接：
考點8在筆試考試中考核幾率為30%，分值為2分，讀者應該熟練掌握各種遍歷的具體演算法，能由兩種遍歷的結果推導另一種遍歷的結果。
在遍歷二叉樹的過程中，一般先遍歷左子樹，再遍歷右子樹。在先左後右的原則下，根據訪問根結點的次序，二叉樹的遍歷分為三類：前序遍歷、中序遍歷和後序遍歷。
（1）前序遍歷：先訪問根結點、然後遍歷左子樹，最後遍歷右子樹；並且，在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。
（2）中序遍歷：先遍歷左子樹、然後訪問根結點，最後遍歷右子樹；並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。
（3）後序遍歷：先遍歷左子樹、然後遍歷右子樹，最後訪問根結點；並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後訪問根結點。

疑難解答：樹與二叉樹的不同之處是什麼？
在二叉樹中，每一個結點的度最大為2，即所有子樹（左子樹或右子樹）也均為二叉樹，而樹結構中的每一個結點的度可以是任意的。
1.5查找技術
考點9 順序查找
考試鏈接：
考點9在筆試考試中考核幾率在30%，一般出現選擇題中，分值為2分，讀者應該具體掌握順序查找的演算法。
查找是指在一個給定的數據結構中查找某個指定的元素。從線性表的第一個元素開始，依次將線性表中的元素與被查找的元素相比較，若相等則表示查找成功；若線性表中所有的元素都與被查找元素進行了比較但都不相等，則表示查找失敗。
在下列兩種情況下也只能採用順序查找：
（1）如果線性表為無序表，則不管是順序存儲結構還是鏈式存儲結構，只能用順序查找。
（2）即使是有序線性表，如果採用鏈式存儲結構，也只能用順序查找。
考點10 二分法查找
考試鏈接：
考點10在筆試考試中考核幾率為30%，一般出現填空題中，分值為2分，考核比較多查找的比較次數，讀者應該具體掌握二分查找法的演算法。
二分法只適用於順序存儲的，按非遞減排列的有序表，其方法如下：
設有序線性表的長度為n，被查找的元素為i，
（1）將i與線性表的中間項進行比較；
（2）若i與中間項的值相等，則查找成功；
（3）若i小於中間項，則在線性表的前半部分以相同的方法查找；
（4）若i大於中間項，則在線性表的後半部分以相同的方法查找。

疑難解答：二分查找法適用於哪種情況？
二分查找法只適用於順序存儲的有序表。在此所說的有序表是指線性表中的元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。
這個過程一直進行到查找成功或子表長度為0為止。
對於長度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次。
1.6排序技術
考點11 交換類排序法
考試鏈接:
考點11屬於比較難的內容，一般以選擇題的形式考查，考核幾率為30%，分值約為2分，讀者應該熟練掌握幾種排序演算法的基本過程。
冒泡排序法和快速排序法都屬於交換類排序法。
（1）冒泡排序法
首先，從表頭開始往後掃描線性表，逐次比較相鄰兩個元素的大小，若前面的元素大於後面的元素，則將它們互換，不斷地將兩個相鄰元素中的大者往後移動，最後最大者到了線性表的最後。
然後，從後到前掃描剩下的線性表，逐次比較相鄰兩個元素的大小，若後面的元素小於前面的元素，則將它們互換，不斷地將兩個相鄰元素中的小者往前移動，最後最小者到了線性表的最前面。
對剩下的線性表重復上述過程，直到剩下的線性表變空為止，此時已經排好序。
在最壞的情況下，冒泡排序需要比較次數為n（n－1）/2。
（2）快速排序法
它的基本思想是：任取待排序序列中的某個元素作為基準（一般取第一個元素），通過一趟排序，將待排元素分為左右兩個子序列，左子序列元素的排序碼均小於或等於基準元素的排序碼，右子序列的排序碼則大於基準元素的排序碼，然後分別對兩個子序列繼續進行排序，直至整個序列有序。

疑難解答：冒泡排序和快速排序的平均執行時間分別是多少？
冒泡排序法的平均執行時間是O（n2），而快速排序法的平均執行時間是O（nlog2n）。

1.7 例題詳解
一、選擇題
【例1】演算法的時間復雜度取決於_______。（考點2）
A）問題的規模 B）待處理的數據的初態
C）問題的難度 D）A）和B）
解析：演算法的時間復雜度不僅與問題的規模有關，在同一個問題規模下，而且與輸入數據有關。即與輸入數據所有的可能取值范圍、輸入各種數據或數據集的概率有關。
答案：D）
【例2】在數據結構中，從邏輯上可以把數據結構分成_______。（考點3）
A）內部結構和外部結構 B）線性結構和非線性結構
C）緊湊結構和非緊湊結構 D）動態結構和靜態結構
解析：邏輯結構反映數據元素之間的邏輯關系，線性結構表示數據元素之間為一對一的關系，非線性結構表示數據元素之間為一對多或者多對一的關系，所以答案為B）。
答案：B）
【例3】以下_______不是棧的基本運算。（考點5）
A）判斷棧是否為素空 B）將棧置為空棧
C）刪除棧頂元素 D）刪除棧底元素
解析：棧的基本運算有：入棧，出棧（刪除棧頂元素），初始化、置空、判斷棧是否為空或滿、提取棧頂元素等，對棧的操作都是在棧頂進行的。
答案：D）
【例4】鏈表不具備的特點是_______。（考點6）
A）可隨機訪問任意一個結點 B）插入和刪除不需要移動任何元素
C）不必事先估計存儲空間 D）所需空間與其長度成正比
解析：順序表可以隨機訪問任意一個結點，而鏈表必須從第一個數據結點出發，逐一查找每個結點。所以答案為A）。
答案：A）
【例5】已知某二叉樹的後序遍歷序列是DACBE，中序遍歷序列是DEBAC，則它的前序遍歷序列是_______。（考點8）
A）ACBED B）DEABC
C）DECAB D）EDBAC
解析：後序遍歷的順序是"左子樹－右子樹－根結點"；中序遍歷順序是"左子樹－根結點－右子樹"；前序遍歷順序是"根結點－左子樹－右子樹"。根據各種遍歷演算法，不難得出前序遍歷序列是EDBAC。所以答案為D）。
答案：D）
【例6】設有一個已按各元素的值排好序的線性表（長度大於2），對給定的值k，分別用順序查找法和二分查找法查找一個與k相等的元素，比較的次數分別是s和b，在查找不成功的情況下，s和b的關系是_______。（考點9）
A）s=b B）s>b C）s<b D）s≥b
解析：對於順序查找，查找不成功時和給定關鍵字比較的次數為n+1。二分查找查找不成功的關鍵字比較次數為〔log2n〕+1。當n≥2時，顯然n+1>〔log2n〕+1。
答案：B）
【例7】在快速排序過程中，每次劃分，將被劃分的表（或子表）分成左、右兩個子表，考慮這兩個子表，下列結論一定正確的是_______。（考點11）
A）左、右兩個子表都已各自排好序
B）左邊子表中的元素都不大於右邊子表中的元素
C） 左邊子表的長度小於右邊子表的長度
D）左、右兩個子表中元素的平均值相等
解析：快速排序基本思想是：任取待排序表中的某個元素作為基準（一般取第一個元素），通過一趟排序，將待排元素分為左右兩個子表，左子表元素的排序碼均小於或等於基準元素的排序碼，右子表的排序碼則大於基準元素的排序碼，然後分別對兩個子表繼續進行排序，直至整個表有序。
答案：B）
二、填空題
【例1】問題處理方案的正確而完整的描述稱為_______。（考點1）
解析：計算機解題的過程實際上是在實施某種演算法，這種演算法稱為計算機演算法。
答案：演算法
【例2】一個空的數據結構是按線性結構處理的，則屬於_______。（考點4）
解析：一個空的數據結構是線性結構或是非線性結構，要根據具體情況而定。如果對數據結構的運算是按線性結構來處理的，則屬於線性結構，否則屬於非線性結構。
答案：線性結構
【例3】設樹T的度為4，其中度為1、2、3和4的結點的個數分別為4、2、1、1，則T中葉子結點的個數為_______。（考點7）
解析：根據樹的性質：樹的結點數等於所有結點的度與對應的結點個數乘積之和加1。
因此樹的結點數為1×4＋2×2＋3×1＋4×1＋1＝16。葉子結點數目等於樹結點總數減去度不為0的結點數之和，即16－（4＋2＋1＋1）＝8。
答案：8
【例4】二分法查找的存儲結構僅限於_______且是有序的。（考點10）
解析：二分查找，也稱折半查找，它是一種高效率的查找方法。但二分查找有條件限制：要求表必須用順序存儲結構，且表中元素必須按關鍵字有序(升序或降序均可）。
答案：順序存儲結構

㈢ 如何輕松考過計算機二級

方法/步驟
全國計算機二級等級考試分為兩個部分，第一項為二級公共基礎，這是所有考生都要考的，第二項為你所選的分類，如c語言程序設計等等。
就我考試的經驗來看，二級公共基礎為最易得分項，主要考察考生對概念的理解及掌握。下面為我總結的二級公共基礎中易考及必會的內容，我相信只要掌握了它，二級公共基礎這項就可以輕松過關啦。

一。數據結構與演算法：
演算法的定義
演算法是指解決方案的准確而完整的描述，是一系列解決問題的清晰指令。演算法 ≠ 程序。
演算法的5大特徵
1. 至少1個輸出：任何演算法，必須有輸出結果。2. 至少0個輸入，足夠的情報：對於復雜演算法，情報越充足，效果越好。3. 有窮性：演算法能在有限的執行步驟內、有限的時間內執行結束。4. 可行性：演算法的每一個步驟都必須能夠翻譯成計算機可執行的基本操作。5. 確定性：演算法的每一個步驟都必須描述准確，沒有歧義。
演算法的復雜度
【時間復雜度】以基本操作次數的數量級計數，不以秒計數。常見復雜度（越小越快）：O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(2^n)<O(n!)【空間復雜度】演算法執行過程中的空間開銷。【二者關系】雖然演算法中常常會以犧牲空間的方式來換取時間效率，但一般認為二者沒有必然關系。
數據結構的定義
數據結構是指計算機組織、存儲數據的方式。數據結構可分為邏輯結構和存儲結構。其中：1. 邏輯結構又分為線性結構和非線性結構。2. 存儲結構又分為順序存儲結構和鏈式存儲結構
邏輯結構
邏輯結構不關心數據如何存儲，只關心數據的組織方式。邏輯結構可分為線性結構和非線性結構。典型線性結構：棧、隊列典型非線性結構：樹（二叉樹）、網狀圖
存儲結構
存儲結構不關心數據如何組織，只關心數據的存儲方式。存儲結構又分為順序存儲結構和鏈式存儲結構。【順序存儲結構】1. 所有元素在內存中按順序排列2. 查找、修改比較不方便3. 插入、刪除比較方便【鏈式存儲結構】1. 所有元素在內存中隨機分布2. 插入、刪除比較不方便3. 查找、修改比較方便4. 由於要存儲下一元素的地址，所以需要更多的存儲空間【二者關系】二者沒有必然關系。
基本概念
1. 棧屬於邏輯結構的概念，屬於線性結構。2. 棧既可以用順序存儲結構實現，也可以用鏈式存儲結構實現。3. 棧的特點是先進後出（FILO）。4. 進出過程中，棧底指針不變，棧頂指針移動。
計算規則
視棧頂和棧底指針的指向規則而定。一般的，棧底指向首元素的前一位置（比如0），棧頂指針指向尾元素（比如5），即棧中1、2、3、4、5各存儲了一個數據。此時：棧中元素個數=棧頂指針-棧底指針（比如5-0=5）
基本概念
1. 隊列屬於邏輯結構的概念，屬於線性結構。2. 隊列既可以用順序存儲結構實現，也可以用鏈式存儲結構實現。3. 隊列的特點是先進先出（FIFO）。4. 隊頭負責出隊，隊尾負責入隊。
循環隊列
循環隊列是專門針對順序存儲結構空間固定的特點而設計的，所以一般認為循環隊列是順序存儲結構。其核心原理是：當隊尾到達隊列最大位置、而隊頭不在最小位置時如果繼續入隊，則隊尾移至隊列最小位置，從頭開始移動，形成循環。出隊時同理。
計算規則
視棧頂和棧底指針的指向規則而定。一般的，隊頭指向首元素的前一位置，隊尾指針指向尾元素。假設隊列容量為20：1. 若隊尾>隊頭（比如隊尾為7，隊頭為2）：隊列元素個數=隊尾指針-隊頭指針（7-2=5）2. 若隊頭>隊尾（比如隊尾為2，隊頭為7）：隊列元素個數=隊尾指針-隊頭指針+隊列容量（2-7+20=15）其中，第二種情況只有循環隊列中才會出現。
基本概念
1. 一個二叉樹只有一個根節點。2. 在二叉樹中，任何一個節點最多隻能有2個子節點。3. 一個節點有幾個子節點，則度為幾。度為0的節點稱為葉子節點。
常用公式
1. 第n層的節點數最多為2^(n-1)個。2. 層數為n的二叉樹，總節點數最多為2^n-1個。3. 葉子節點數 = 度為2的節點數+14. 二叉樹節點總數 = 度為2的節點數 + 度為1的節點數 + 葉子節點數
遍歷規則
先序遍歷：父節點、左子樹、右子樹中序遍歷：左子樹、父節點、右子樹後序遍歷：左子樹、右子樹、父節點其中左右子樹按此規則繼續拆分，拆分過程中也按其對應規則遍歷，直到不能再拆分為止。
順序查找
其演算法復雜度為O(n)，長度為n的線性表，最多需要n次才能找到指定元素。
順序查找最大/最小值
長度為n的線性表，所有元素隨機排列，最多需要n-1次才能找到最大/最小值。
二分查找
其演算法復雜度為O(logn)，長度為n的線性表，最多需要logn次就能找到指定元素。
二分查找使用條件
1. 使用順序存儲結構（如數組）。2. 所有元素按序排列。
按原理分類
交換類：冒泡排序、快速排序選擇類：簡單選擇排序、堆排序插入類：簡單插入排序、希爾排序
按穩定性分類
穩定：冒泡排序、簡單插入排序……不穩定（快選希堆）：快速排序、簡單選擇排序、希爾排序、堆排序
按演算法復雜度
O(n^2)：冒泡排序、簡單選擇排序、簡單插入排序O(nlogn)：快速排序、堆排序、希爾排序在一般情況下，快速排序是已知常用演算法中效率最高的。在最壞情況下，快速排序的演算法復雜度是O(n^)2。
二。軟體工程：
基本概念
可行性研究主要考慮：經濟、技術、法律。需求分析階段最重要的文檔：《軟體需求規格說明書》。《軟體需求規格說明書》的任務是統一認識，所以必須追求准確，消滅歧義。
數據流圖（DFD）
箭頭：數據流圓形、橢圓形：數據的加工方框：系統和環境的介面半開口的方框、雙杠：數據的存儲文件
數據字典
1. 是數據流圖的重要補充2. 應該包含數據流圖中提到的所有數據
概要設計
耦合性：模塊之間的關聯程度內聚性：模塊內部的關聯程度設計原則：高內聚低耦合軟體系統結構圖：深度、寬度、扇入、扇出。
詳細設計
【程序流程圖】箭頭：控制流矩形：執行步驟菱形：邏輯條件【N-S圖】【PAD圖】
基本原則
自頂向下、逐步求精、模塊化使用3種基本控制結構，限制goto語句的使用
3種控制結構
順序結構、選擇結構、循環結構
基本概念
對象是類的實例。類由兩個部分組成：屬性、方法。由同一個類定義的對象，擁有相同的屬性和方法
類的特徵
封裝型、繼承性、多態性
基本概念
測試：發現錯誤調試：診斷並改正錯誤注意：沒有一種方法可以保證軟體沒有錯誤
黑盒和白盒
【黑盒】根據軟體的外部功能設計測試用例例如：等價類劃分、邊界值分析、錯誤推測法【白盒】根據軟體的內部邏輯設計測試用例例如：基本路徑覆蓋測試、邏輯條件覆蓋測試
測試流程
單元測試：對單一模塊進行測試集成測試：對模塊間的協作進行測試確認測試：對《軟體需求規格說明書》的需求進行逐一確認系統測試：對安全、性能等系統指標進行測試回歸測試：對調試後的代碼重新進行測試
三。資料庫系統：
基本概念
數據（Data）：信息的載體。包括類型和值兩個屬性。資料庫（DB）：依照某種數據模型將數據組織並存放起來的集合。資料庫管理系統（DBMS）：系統軟體，是資料庫系統的核心，為資料庫提供底層服務。資料庫管理系統（DBAS）：基於資料庫管理系統設計的應用軟體，面向普通用戶使用。資料庫管理員（DBA）：負責資料庫設計、維護、性能、安全等工作的高科技人才。資料庫系統（DBS）：包括以上所有概念，再加上其他相關軟硬體環境的總和。
數據語言
數據定義語言：表的建立、修改和刪除數據操縱語言：表中數據的增加、刪除、修改和查詢數據控制語言：負責表中的安全性和完整性的設置
發展階段
人工管理階段 -> 文件管理階段 -> 資料庫管理階段資料庫管理階段主要解決的問題：數據共享。
獨立性
邏輯獨立性：邏輯結構修改時，應用程序不需要修改。物理獨立性：物理結構修改時，應用程序不需要修改。
三級模式
概念模式（邏輯模式）：資料庫邏輯結構的全局描述外模式（子模式）：用戶能看到的資料庫邏輯結構和描述內模式（物理模式）：資料庫的物理存儲結構和存取方法
基本概念
E(Entity)：實體R(RelationShip)：聯系一對一：學生和學號、中國公民和身份證、考生和准考證號……一對多：班長和班級、宿舍和學生……多對多：學生和課程、老師和課程……
圖示
實體：矩形聯系：菱形屬性：橢圓形
基本概念
層次模型：用「樹」的方式組織數據網狀模型：用「圖」的方式組織數據關系模型：用「二維表」的方式組織數據【關系模型】 屬性、元組【關系資料庫】欄位、記錄元組的分量是關系模型中的最小不可再分單位
數據完整性
候選鍵（候選關鍵字）：可以標識記錄唯一性的幾個欄位。主鍵（主關鍵字）：可以標識記錄唯一性的一個欄位。一個表只能有一個主關鍵字。外鍵（外部關鍵字）：如果當前表中某欄位是其他表的主鍵，則稱此欄位為外鍵。實體完整性：主鍵和候選鍵不能為空。參照完整性：對一對多關系中父表和子表之間關系的制約。自定義完整性：其他設置。如域完整性，就是對欄位取值范圍進行設置。
基本概念
【交】計算前提：兩個關系的屬性完全相同屬性規則：屬性保持不變。元組規則：對兩個關系中的元組求交集。【並】計算前提：兩個關系的屬性完全相同屬性規則：屬性保持不變。元組規則：對兩個關系中的元組求並集。【差】R-S=T計算前提：兩個關系的屬性完全相同屬性規則：屬性保持不變。元組規則：表示取R中存在且S中不存在的元組形成結果T。【笛卡兒積】RxS=T計算前提：對屬性無要求屬性規則：對兩個關系的屬性求並集。元組規則：對兩個關系的元組做全排列。【除】R/S=T計算前提：S的屬性應是R的子集屬性規則：取R中存在的屬性而S中不存在的屬性作為結果T的屬性，即對屬性做差運算。元組規則：在R中選擇與各屬性值完全相等的元組，將其對T中的屬性做投影
基本概念
【交】計算前提：兩個關系的屬性完全相同屬性規則：屬性保持不變。元組規則：對兩個關系中的元組求交集。【並】計算前提：兩個關系的屬性完全相同屬性規則：屬性保持不變。元組規則：對兩個關系中的元組求並集。【差】R-S=T計算前提：兩個關系的屬性完全相同屬性規則：屬性保持不變。元組規則：表示取R中存在且S中不存在的元組形成結果T。【笛卡兒積】RxS=T計算前提：對屬性無要求屬性規則：對兩個關系的屬性求並集。元組規則：對兩個關系的元組做全排列。【除】R/S=T計算前提：S的屬性應是R的子集屬性規則：取R中存在的屬性而S中不存在的屬性作為結果T的屬性，即對屬性做差運算。元組規則：在R中選擇與各屬性值完全相等的元組，將其對T中的屬性做投影
生命周期
【需求分析】數據流圖、數據字典、需求規格說明書【概念設計】設計E-R模型【邏輯設計】將E-R模型轉換為數據模型（主要是關系模型）【物理設計】將關系模型轉換為關系資料庫