計算機等級考試公共基礎知識,第2頁,計算機二級考試公共基礎知識大綱,數(shù)據(jù)結(jié)構(gòu)與算法程序設計基礎軟件工程基礎數(shù)據(jù)庫設計基礎,這四個方面在試卷中出現(xiàn)的情況是：選擇題10個（20分），填空題5個（10分），總分值占到了試卷卷面分的30，是一個不小的比例。,第3頁,計算機二級考試公共基礎知識試卷分析,第4頁,算法算法的基本概念2.算法復雜度的概念和意義,一、基本數(shù)據(jù)結(jié)構(gòu)與算法,數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的概念線性表棧和隊列樹與二叉樹查找技術(shù)排序技術(shù),對于等級考試，這個部分的考核重點主要在算法和數(shù)據(jù)結(jié)構(gòu)的基本概念、二叉樹(遍歷、結(jié)點），還有排序和查找考試中也經(jīng)常會涉及到。,第5章數(shù)據(jù)結(jié)構(gòu)與算法,5.1算法基礎5.2數(shù)據(jù)結(jié)構(gòu)5.3棧5.4隊列,5.5鏈表5.6樹與二叉樹5.7查找5.8排序,本章要求,算法的基本概念；算法復雜度的概念和意義(時間復雜度與空間復雜度)數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念線性表的定義；線性表的順序存儲結(jié)構(gòu)及其插入與刪除運算棧和隊列的定義；棧和隊列的順序存儲結(jié)構(gòu)及其基本運算,本章要求,線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運算樹的基本概念；二叉樹的定義及其存儲結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷順序查找與二分法查找算法；基本排序算法(交換類排序,選擇類排序,插入類排序),5.1算法基礎(P191),5.1.1算法的基本概念5.1.2算法復雜性分析,5.1.1算法的基本概念(P191),所謂算法是指解決問題的方法和步驟。算法的基本特征：可行性：算法中有待執(zhí)行的運算和操作必須是相當基本的，都是能夠精確地進行的。例：在算法中不允許出現(xiàn)分母為0的情況。算法執(zhí)行者甚至不需要掌握算法的含義即可根據(jù)該算法的每一步驟要求進行操作，并最終得出正確的結(jié)果。確定性：算法的每一個步驟必須要確切地定義。即算法中所有有待執(zhí)行的動作必須嚴格而不含混地進行規(guī)定，不能有歧義性。有窮性：一個算法在執(zhí)行有窮步之后必須結(jié)束。擁有足夠的情報：一個算法執(zhí)行的結(jié)果總是與輸入的初始數(shù)據(jù)有關，不同的輸入將會有不同的結(jié)果輸出。,算法的基本要素,1.算法中對數(shù)據(jù)的運算和操作算術(shù)運算：主要包括加、減、乘、除等運算。邏輯運算：主要包括“與”、“或”、“非”等運算。關系運算：主要包括“大于”、“小于”、“等于”、“不等于”等運算。數(shù)據(jù)傳輸：主要包括賦值、輸入、輸出等操作2.算法的控制結(jié)構(gòu)算法中各操作之間的執(zhí)行順序稱為算法的控制結(jié)構(gòu)。一個算法一般都可以用順序、選擇、循環(huán)三種基本控制結(jié)構(gòu)組合而成。,三種控制結(jié)構(gòu),算法設計基本方法,（1）列舉法（2）歸納法（3）遞推（4）遞歸（5）減半遞推技術(shù)（6）回溯法,列舉法的基本思是根據(jù)提出的問題，列舉所有可能的情況，并用問題中給定的條件檢驗哪些是需要的，哪些是不需要的。列舉法的特點是算法比較簡單。但當列舉的可能情況較多時，列舉算法的計算量將會很大。因此，盡量使得列舉法能在一個局部范圍內(nèi)進行。列舉算法雖然是一種比較原始的方法，其運算量比較大，但在有些實際問題中（如尋找路徑、査找、搜索等問題）、局部使用列舉法卻是很有效的，因此，列舉算法是計算機算法中的一個基礎算法。,(1)列舉法,歸納法的基本思想是，通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關系。歸納法要比列舉法更能反映問題的本質(zhì)，并且可以解決列舉量為無限的問題。但是，從一個實際問題中總結(jié)歸納出一般的關系，并不是一件容易的事情，尤其是要歸納出一個數(shù)學模型更為困難。從本質(zhì)上講，歸納就是通過觀察一些簡單而特殊的情況，最后總結(jié)出一般性的結(jié)論。歸納是一種抽象，即從特殊現(xiàn)象中找出一般關系。但由于在歸納的過程中不可能對所有的情況進行列舉，因此，最后由歸納得到的結(jié)論還只是一種猜測，還需要對這種猜測加以必要的證明。實際上，通過精心觀察而得到的猜測得不到證實或最后證明猜測是錯的，也是常有的事。,(2)歸納法,（3）遞推,遞推，是指初始條件或是問題本身已經(jīng)給定，或是通過對問題的分析與化簡而確定。遞推本質(zhì)上也屬于歸納法，工程上許多遞推關系式實際上是通過對實際問題的分析與歸納而得到的，因此，遞推關系式往往是歸納的結(jié)果。遞推算法在數(shù)值計算中是極為常見的。但是，對于數(shù)值型的遞推算法必須要注意數(shù)值計算的穩(wěn)定性問題。,（4）遞歸,人們在解決一些復雜問題時，為了降低問題的復雜程度（如問題的規(guī)模等，一般總是將問題逐層分解，最后歸結(jié)為一些最簡單的問題。這種將問題逐層分解的過程，實際上并沒有對問題進行求解，而只是當解決了最后那些最簡單的問題后，再沿著原來分解的逆過程逐步進行綜合，這就是遞歸的基本思想。遞歸分為直接遞歸與問接遞歸兩種。如果一個算法顯式地調(diào)用自己則稱為直接遞歸。如果算法F調(diào)用另一個算法P，而算法P又調(diào)用算法F，則稱為間接遞歸調(diào)用。,遞歸調(diào)用實例:求n的階乘,#includeintfact(intn)intf;if(nnext,a2,p,p,s,s,p-next=s,插入前：,插入后：,s-next=p-next;p-next=s;,刪除指針p所指的結(jié)點后的結(jié)點,a1,a3,a2,p,刪除前：,刪除后：,a1,a3,a2,p,p-next=p-next-next,s,s=p-next,釋放結(jié)點后：,a1,a3,p,free(s),單鏈表的刪除,p-next=p-next-next;,鏈式棧棧也是線性表，也可以采用鏈式存儲結(jié)構(gòu)，棧的鏈式結(jié)構(gòu)和單鏈表存儲結(jié)構(gòu)基本相同，單鏈表的頭指針含義為棧的棧頂指針。插入和刪除結(jié)點只能通過棧頂指針在棧頂端進行。帶鏈的?？梢杂脕硎占嬎銠C存儲空間中所有空閑的存儲結(jié)點，這種帶鏈的棧稱為可利用棧。鏈式隊列隊列的鏈式結(jié)構(gòu)也和單鏈表的存儲結(jié)構(gòu)基本相同，不過鏈式隊列有兩個指針，一個隊首指針，一個隊尾指針。,5.6樹和二叉樹(P205),5.6.1樹的基本概念定義：樹(tree)是n(n=0)個結(jié)點的有限集T當n0時，空樹當n0時有且僅有一個特定的結(jié)點，稱為樹的根(root)當n1時，其余結(jié)點可分為m(m0)個互不相交的有限集T1,T2,Tm，其中每一個集合本身又是一棵樹，稱為根的子樹(subtree)特點：樹中至少有一個結(jié)點根樹中各子樹是互不相交的集合,A,只有根結(jié)點的樹n=1,有子樹的樹n1,根,子樹,現(xiàn)實中的例子,定義：度為2的有序樹遞歸定義：二叉樹是n(n0)個結(jié)點的有限集，它或為空樹(n=0)，或由一個根結(jié)點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成特點每個結(jié)點至多有二棵子樹(即不存在度大于2的結(jié)點)二叉樹的子樹有左、右之分，且其次序不能任意顛倒基本形態(tài),左孩子,右孩子,5.6.2二叉樹概念及其基本性質(zhì)(P206),二叉樹基本性質(zhì),滿二叉樹與完全二叉樹,滿二叉樹是指這樣的一種二叉樹：(1)除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。(2)在滿二叉樹中，每一層上的結(jié)點數(shù)都達到最大值，即在滿二叉樹的第k層上有2k-1個結(jié)點，(3)在深度為m的滿二叉樹共有2m-1個結(jié)點。完全二叉樹是指這樣的二叉樹：(1)除最后一層外，每一層上的結(jié)點數(shù)均達到最大值；(2)在最后一層上只缺少右邊的若干結(jié)點。,理想平衡二叉樹,性質(zhì)1：具有n個結(jié)點的完全二叉樹的深度為log2n+1。性質(zhì)2：設完全二叉樹共有n個結(jié)點。如果從根結(jié)點開始，按層次（每一層從左到右）用自然數(shù)1，2，n給結(jié)點進行編號，則對于編號為k（k=1，2，n）的結(jié)點有以下結(jié)論：若k=1，則該結(jié)點為根結(jié)點，它沒有父結(jié)點；若k1，則該結(jié)點的父結(jié)點,編號為k/2；若2kn，則編號為k的結(jié)點的左子結(jié)點編號為2k；否則該結(jié)點無左子結(jié)點（顯然也沒有右子結(jié)點）；若2k+1n，則編號為k的結(jié)點的右子結(jié)點編號為2k+1；否則該結(jié)點無右子結(jié)點。,完全二叉樹的性質(zhì),遍歷的定義按一定規(guī)律走遍樹的各個頂點，且使每一頂點僅被訪問一次，即找一個完整而有規(guī)律的走法，以得到樹中所有結(jié)點的一個線性排列.常用方法前序遍歷：先訪問根結(jié)點,然后分別先序遍歷左子樹、右子樹中序遍歷：先中序遍歷左子樹，然后訪問根結(jié)點，最后中序遍歷右子樹后序遍歷：先后序遍歷左、右子樹，然后訪問根結(jié)點,5.6.3二叉樹的遍歷(P208),前序遍歷:,DLR,前序遍歷序列：ABDC,LDR,中序遍歷序列：BDAC,中序遍歷:,LRD,后序遍歷序列：DBCA,后序遍歷:,前序遍歷：,中序遍歷：,后序遍歷：,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,作業(yè),1.,2.若某二叉樹的前序遍歷訪問順序是abdgcefh,中序遍歷訪問順序是dgbaechf,畫出其二叉樹結(jié)構(gòu)并計算后序遍歷順序。,5.7查找(P208),查找(search):也稱檢索，即根據(jù)給定的某個值，在查找表中確定一個其關鍵字等于給定值的第一條記錄(元素)或全部記錄。若表中存在這樣的記錄，則查找成功，通常要求返回該記錄存儲位置；若不存在這樣的記錄，表明查找失敗，返回特定值。,順序查找(SequentialSearch)：又稱線性查找，它是一種最簡單最基本查找方法。思路：(1)從順序表的一端開始，依次將每個元素關鍵字同給定值K進行比較，(2)若某個元素關鍵字等于K，則查找成功，返回該元素所在下標，(3)若直到所有元素都比較完畢，仍找不到關鍵字為K的元素，則查找失敗，返回特定值(常用-1表示)。,5.7.1順序查找(P208),順序查找時間復雜度為O(n),缺點：速度較慢，查找成功最多需比較n次，平均查找長度約為表長一半。優(yōu)點：算法簡單，適應面廣，對表結(jié)構(gòu)無任何要求。,順序查找性能分析：,在下列兩種情況下也只能采用順序查找：如果線性表為無序表，則不管是順序存儲結(jié)構(gòu)還是鏈式存儲結(jié)構(gòu)，只能用順序查找；即使是有序線性表，如果采用鏈式存儲結(jié)構(gòu)，也只能用順序查找。,二分查找(BinarySearch)：又稱折半查找。作為二分查找對象的表必須是順序存儲的有序表。查找過程：首先取整個有序表A0An-1的中點元素Amid(mid=(n-1)/2)的關鍵字與K比較,Amid.key=K成功，返回mid,Amid.keyK在A0Amid-1中繼續(xù)找,Amid.keyK在Amid+1An-1中繼續(xù)找,5.7.2二分法查找(P210),查找96過程如下：,排序定義將一組雜亂無章的記錄按一定的規(guī)律順次排列起來。排序目的便于查找。排序域通常數(shù)據(jù)記錄有多個屬性域,即多個數(shù)據(jù)項,其中有一個屬性域可用來區(qū)分記錄,作為排序依據(jù)。該域即為排序域或排序項。每個數(shù)據(jù)表用哪個屬性域作為排序域，要視具體的應用需要而定。排序碼排序域中的每一個值。,存放在數(shù)據(jù)表中,按某個域的值排序,5.8排序(P212),排序算法的好壞如何衡量時間效率空間效率占內(nèi)存輔助空間的大小穩(wěn)定性排序算法的穩(wěn)定性如果在記錄序列中有兩個記錄ri和rj,它們的排序碼ki=kj,且在排序之前,記錄ri排在rj前面。如果在排序之后,對象ri仍在對象rj的前面,則稱這個排序方法是穩(wěn)定的,否則稱這個排序方法是不穩(wěn)定的。,排序算法的時間開銷排序算法的時間開銷是衡量算法好壞的最重要的標志。排序基本操作比較兩個關鍵字大小將記錄從一個位置移動到另一個位置排序的時間開銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動次數(shù)來衡量。,基本思想兩兩比較待排序記錄的排序碼，如果發(fā)生逆序（即排列順序與排序后的次序正好相反），則交換之，直到所有記錄都排好序為止。,5.8.1交換類排序法(P212),排序過程（升序）將最后一條記錄（第n條記錄）的排序碼與倒數(shù)第二條記錄（第n-1條記錄）的排序碼進行比較，若為逆序，即rn-1rn-2，則交換；然后比較第n-1記錄與第n-2條記錄；依次類推，直至第2條記錄和第1條記錄比較為止第一趟冒泡排序，結(jié)果排序碼最小的記錄被安置在第條記錄上。對后n-1個記錄進行第二趟冒泡排序，結(jié)果使關鍵字次小的記錄被安置在第條記錄位置。重復上述過程，直到“在一趟排序過程中沒有進行過交換記錄的操作”為止，即沒有記錄交換。,(1)冒泡排序法(P212),例,4938659776132730,初始排序碼,1349386597762730,第一趟,1327493865977630,第二趟,1327304938659776,第三趟,第四趟,第五趟,76,13,27,97,13,76,76,27,30,13,27,65,13,49,30,27,27,38,38,13,97,65,38,49,97,49,30,30,30,97,65,38,49,76,1327303849657697,1327303849657697,在最壞的情況下，N個數(shù)冒泡排序需要比較次數(shù)為n(n-1)/2。時間復雜度為O(n2)。,（2）快速排序法（劃分排序）,基本思想對冒泡排序的改進，從待排序列中任取一個元素(例如取第一個)作為基準元素，通過從區(qū)間兩端向中間順序進行比較和交換，使所有比基準元素的排序碼小的元素一律前放，所有比它大的元素一律后放，形成左右兩個子表，然后把基準元素交換到左右兩個子表的交界處，這樣，左子表中所有元素的排序碼均小于等于基準元素的排序碼，右子表中所有元素的排序碼均大于等于基準元素的排序碼；然后再對各子表重新選擇基準元素并依此規(guī)則調(diào)整，直到每個子表的元素只剩一個或為空。此時便為有序序列了。,排序過程對rst中記錄進行一趟快速排序，附設兩個指針i和j，設基準元素為rp=rs，x=rp.stn初始時令i=s+1,j=t首先從j所指位置向前搜索第一個排序碼小于x的記錄。再從i所指位置起向后搜索，找到第一個排序碼大于x的記錄。交換Ai和Aj。重復上述兩步，直至i=j或i=j+1為止再分別對兩個子序列進行快速排序，直到每個子序列只含有一個記錄或為空為止。,45531836723048931536第一次劃分：30361836154548937253第二次劃分：18153036364548937253第三次劃分：15183036364548537293第四次劃分：15183036364548537293,5.8.2插入類排序法,（1）直接插入排序基本思想：每步將一個待排序的記錄,按其排序碼大小,插入到前面已經(jīng)排好序的一組記錄的適當位置上,直到記錄全部插入為止。直接插入排序排序過程：先將序列中第1個記錄看成是一個有序子序列，然后從第2個記錄開始，逐個進行插入，直至整個序列有序，整個排序過程為n-1趟插入。,例,49386597761327,i=238(3849)6597761327,i=365(384965)97761327,i=497(38496597)761327,i=576(3849657697)1327,i=613(133849657697)27,i=1(),i=7(133849657697)27,27,97,76,65,49,38,27,（2）希爾排序法,基本思想是：將待排序列分為若干組，在每組內(nèi)進行直接插入排序，以使整個序列基本有序，然后對整個序列進行直接插入排序。關鍵在于如何分組，常用辦法是第一輪取步長為初始長度n的一半，即間隔為n/2的元素為一組；以后每輪的步長為上次的一半（縮小增量法）；此方法稱為折半插入排序。,折半插入排序排序過程：在已形成的有序表中用折半查找方法確定插入位置的排序。,例:數(shù)據(jù)（51，45，80，36，14，75，58，96）P21551，45，80，36，14，75，58，96,基本策略第i趟在后面n-i個待排記錄中選取排序碼最小的（或最大的）記錄作為有序序列中的第i個記錄。,5.8.3選擇類排序法,排序過程（升序）首先通過n-1次關鍵字比較，從n個記錄中找出關鍵字最小的記錄，將它與第一個記錄交換。再通過n-2次比較，從剩余的n-1個記錄中找出關鍵字次小的記錄，將它與第二個記錄交換。重復上述操作，共進行n-1趟排序后，排序結(jié)束。,（1）直接選擇排序,例,初始：49386597761327,i=1,13,49,一趟：13386597764927,i=2,27,38,六趟：13273849657697,排序結(jié)束：13273849657697,堆的定義：n個元素的序列(k0,k1,kn-1)，當且僅當滿足下列關系時，稱之為堆。,或,(i=0,1,.,n/2-1),kik2ikik2i+1,kik2ikik2i+1,例（96，83，27，38，11，9）,例(13，38，27，50，76，65，49，97）,可將堆序列看成完全二叉樹，則堆頂元素（完全二叉樹的根）必為序列中n個元素的最小值或最大值。,（2）堆排序,堆排序：將無序序列建成一個堆，得