【正文】 種遍歷的結(jié)果。在遍歷二叉樹的過程中，一般先遍歷左子樹，再遍歷右子樹。在先左后右的原則下，根據(jù)訪問根結(jié)點的次序，二叉樹的遍歷分為三類：前序遍歷、中序遍歷和后序遍歷。（1）前序遍歷：先訪問根結(jié)點、然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。（2）中序遍歷：先遍歷左子樹、然后訪問根結(jié)點，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。（3）后序遍歷：先遍歷左子樹、然后遍歷右子樹，最后訪問根結(jié)點；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。 疑難解答：樹與二叉樹的不同之處是什么？在二叉樹中，每一個結(jié)點的度最大為2，即所有子樹（左子樹或右子樹）也均為二叉樹，而樹結(jié)構(gòu)中的每一個結(jié)點的度可以是任意的?？键c9 順序查找考試鏈接：考點9在筆試考試中考核幾率在30%，一般出現(xiàn)選擇題中，分值為2分，讀者應(yīng)該具體掌握順序查找的算法。查找是指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找某個指定的元素。從線性表的第一個元素開始，依次將線性表中的元素與被查找的元素相比較，若相等則表示查找成功；若線性表中所有的元素都與被查找元素進行了比較但都不相等，則表示查找失敗。在下列兩種情況下也只能采用順序查找：（1）如果線性表為無序表，則不管是順序存儲結(jié)構(gòu)還是鏈式存儲結(jié)構(gòu)，只能用順序查找。（2）即使是有序線性表，如果采用鏈式存儲結(jié)構(gòu)，也只能用順序查找?？键c10 二分法查找考試鏈接：考點10在筆試考試中考核幾率為30%，一般出現(xiàn)填空題中，分值為2分，考核比較多查找的比較次數(shù)，讀者應(yīng)該具體掌握二分查找法的算法。二分法只適用于順序存儲的，按非遞減排列的有序表，其方法如下：設(shè)有序線性表的長度為n，被查找的元素為i，（1）將i與線性表的中間項進行比較；（2）若i與中間項的值相等，則查找成功；（3）若i小于中間項，則在線性表的前半部分以相同的方法查找；（4）若i大于中間項，則在線性表的后半部分以相同的方法查找。 疑難解答：二分查找法適用于哪種情況？二分查找法只適用于順序存儲的有序表。在此所說的有序表是指線性表中的元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。這個過程一直進行到查找成功或子表長度為0為止。對于長度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次。考點11 交換類排序法考試鏈接:考點11屬于比較難的內(nèi)容，一般以選擇題的形式考查，考核幾率為30%，分值約為2分，讀者應(yīng)該熟練掌握幾種排序算法的基本過程。冒泡排序法和快速排序法都屬于交換類排序法。（1）冒泡排序法首先，從表頭開始往后掃描線性表，逐次比較相鄰兩個元素的大小，若前面的元素大于后面的元素，則將它們互換，不斷地將兩個相鄰元素中的大者往后移動，最后最大者到了線性表的最后。然后，從后到前掃描剩下的線性表，逐次比較相鄰兩個元素的大小，若后面的元素小于前面的元素，則將它們互換，不斷地將兩個相鄰元素中的小者往前移動，最后最小者到了線性表的最前面。對剩下的線性表重復(fù)上述過程，直到剩下的線性表變空為止，此時已經(jīng)排好序。在最壞的情況下，冒泡排序需要比較次數(shù)為n（n－1）/2。（2）快速排序法它的基本思想是：任取待排序序列中的某個元素作為基準（一般取第一個元素），通過一趟排序，將待排元素分為左右兩個子序列，左子序列元素的排序碼均小于或等于基準元素的排序碼，右子序列的排序碼則大于基準元素的排序碼，然后分別對兩個子序列繼續(xù)進行排序，直至整個序列有序。 疑難解答：冒泡排序和快速排序的平均執(zhí)行時間分別是多少？冒泡排序法的平均執(zhí)行時間是O（n2），而快速排序法的平均執(zhí)行時間是O（nlog2n）。 例題詳解一、選擇題【例1】算法的時間復(fù)雜度取決于_______。（考點2）A）問題的規(guī)模 B）待處理的數(shù)據(jù)的初態(tài)C）問題的難度 D）A）和B）解析：算法的時間復(fù)雜度不僅與問題的規(guī)模有關(guān)，在同一個問題規(guī)模下，而且與輸入數(shù)據(jù)有關(guān)。即與輸入數(shù)據(jù)所有的可能取值范圍、輸入各種數(shù)據(jù)或數(shù)據(jù)集的概率有關(guān)。答案：D）【例2】在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成_______。（考點3）A）內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) B）線性結(jié)構(gòu)和非線性結(jié)構(gòu)C）緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) D）動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)解析：邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系，線性結(jié)構(gòu)表示數(shù)據(jù)元素之間為一對一的關(guān)系，非線性結(jié)構(gòu)表示數(shù)據(jù)元素之間為一對多或者多對一的關(guān)系，所以答案為B）。答案：B）【例3】以下_______不是棧的基本運算。（考點5）A）判斷棧是否為素空 B）將棧置為空棧C）刪除棧頂元素 D）刪除棧底元素解析：棧的基本運算有：入棧，出棧（刪除棧頂元素），初始化、置空、判斷棧是否為空或滿、提取棧頂元素等，對棧的操作都是在棧頂進行的。答案：D）【例4】鏈表不具備的特點是_______。（考點6）A）可隨機訪問任意一個結(jié)點 B）插入和刪除不需要移動任何元素C）不必事先估計存儲空間 D）所需空間與其長度成正比解析：順序表可以隨機訪問任意一個結(jié)點，而鏈表必須從第一個數(shù)據(jù)結(jié)點出發(fā)，逐一查找每個結(jié)點。所以答案為A）。答案：A）【例5】已知某二叉樹的后序遍歷序列是DACBE，中序遍歷序列是DEBAC，則它的前序遍歷序列是_______。（考點8）A）ACBED B）DEABCC）DECAB D）EDBAC解析：后序遍歷的順序是左子樹－右子樹－根結(jié)點；中序遍歷順序是左子樹－根結(jié)點－右子樹；前序遍歷順序是根結(jié)點－左子樹－右子樹。根據(jù)各種遍歷算法，不難得出前序遍歷序列是EDBAC。所以答案為D）。答案：D）【例6】設(shè)有一個已按各元素的值排好序的線性表（長度大于2），對給定的值k，分別用順序查找法和二分查找法查找一個與k相等的元素，比較的次數(shù)分別是s和b，在查找不成功的情況下，s和b的關(guān)系是_______。（考點9）A）s=b B）sb C）sb D）s≥b解析：對于順序查找，查找不成功時和給定關(guān)鍵字比較的次數(shù)為n+1。二分查找查找不成功的關(guān)鍵字比較次數(shù)為［log2n］+1。當n≥2時，顯然n+1［log2n］+1。答案：B）【例7】在快速排序過程中，每次劃分，將被劃分的表（或子表）分成左、右兩個子表，考慮這兩個子表，下列結(jié)論一定正確的是_______。（考點11）A）左、右兩個子表都已各自排好序B）左邊子表中的元素都不大于右邊子表中的元素C） 左邊子表的長度小于右邊子表的長度D）左、右兩個子表中元素的平均值相等解析：快速排序基本思想是：任取待排序表中的某個元素作為基準（一般取第一個元素），通過一趟排序，將待排元素分為左右兩個子表，左子表元素的排序碼均小于或等于基準元素的排序碼，右子表的排序碼則大于基準元素的排序碼，然后分別對兩個子表繼續(xù)進行排序，直至整個表有序。答案：B）二、填空題【例1】問題處理方案的正確而完整的描述稱為_______。（考點1）解析：計算機解題的過程實際上是在實施某種算法，這種算法稱為計算機算法。答案：算法【例2】一個空的數(shù)據(jù)結(jié)構(gòu)是按線性結(jié)構(gòu)處理的，則屬于_______。（考點4）解析：一個空的數(shù)據(jù)結(jié)構(gòu)是線性結(jié)構(gòu)或是非線性結(jié)構(gòu)，要根據(jù)具體情況而定。如果對數(shù)據(jù)結(jié)構(gòu)的運算是按線性結(jié)構(gòu)來處理的，則屬于線性結(jié)構(gòu)，否則屬于非線性結(jié)構(gòu)。答案：線性結(jié)構(gòu)【例3】設(shè)樹Ｔ的度為４，其中度為１、２、３和４的結(jié)點的個數(shù)分別為４、２、１、１，則Ｔ中葉子結(jié)點的個數(shù)為_______。（考點7）解析：根據(jù)樹的性質(zhì)：樹的結(jié)點數(shù)等于所有結(jié)點的度與對應(yīng)的結(jié)點個數(shù)乘積之和加１。因此樹的結(jié)點數(shù)為１４＋２２＋３１＋４１＋１＝16。葉子結(jié)點數(shù)目等于樹結(jié)點總數(shù)減去度不為０的結(jié)點數(shù)之和，即16－（４＋２＋１＋１）＝８。答案：8【例4】二分法查找的存儲結(jié)構(gòu)僅限于_______且是有序的。（考點10）解析：二分查找，也稱折半查找，它是一種高效率的查找方法。但二分查找有條件限制：要求表必須用順序存儲結(jié)構(gòu)，且表中元素必須按關(guān)鍵字有序(升序或降序均可）。答案：順序存儲結(jié)構(gòu)第2章 程序設(shè)計基礎(chǔ)經(jīng)過對部分考生的調(diào)查以及對近年真題的總結(jié)分析，筆試部分經(jīng)?？疾榈氖墙Y(jié)構(gòu)化程序設(shè)計的原則、面向?qū)ο蠓椒ǖ幕靖拍?，讀者應(yīng)對此部分進行重點學(xué)習(xí)。詳細重點學(xué)習(xí)知識點：1．結(jié)構(gòu)化程序設(shè)計方法的四個原則2．對象、類、消息、繼承的概念、類與實例的區(qū)別考點1 結(jié)構(gòu)化程序設(shè)計的原則考試鏈接：考點1在筆試考試中出現(xiàn)的幾率為30%，主要是以選擇題的形式出現(xiàn)，分值為2分，此考點為識記內(nèi)容，讀者應(yīng)該識記結(jié)構(gòu)化程序設(shè)計方法的四個主要原則。20世紀70年代提出了結(jié)構(gòu)化程序設(shè)計的思想和方法。結(jié)構(gòu)化程序設(shè)計方法引入了工程化思想和結(jié)構(gòu)化思想，使大型軟件的開發(fā)和編程得到了極大的改善。結(jié)構(gòu)化程序設(shè)計方法的主要原則為：自頂向下、逐步求精、模塊化和限制使用goto語句。 疑難解答：如何進行自頂向下設(shè)計方法？程序設(shè)計時，應(yīng)先考慮總體，后考慮細節(jié)；先考慮全局目標，后考慮局部目標；不要一開始就過多追求眾多的細節(jié)，先從最上層總目標開始設(shè)計，逐步使問題具體化。考點2 面向?qū)ο蠓椒ǖ幕靖拍羁荚囨溄樱嚎键c2在筆試考試中，是一個經(jīng)常考查的內(nèi)容，在筆試考試中出現(xiàn)的幾率為70%，主要是以填空題的形式出現(xiàn)，分值為2分，此考點為重點識記內(nèi)容，讀者應(yīng)該識記幾個基本要素的定義、對象的特征以及消息、繼承、類的定義。誤區(qū)警示：當使用對象這個術(shù)語時，既可以指一個具體的對象，也可以泛指一般的對象，但是當使用實例這個術(shù)語時，必須是指一個具體的對象。面向?qū)ο蠓椒êw對象及對象屬性與方法、類、繼承、多態(tài)性幾個基本要素。（1）對象通常把對對象的操作也稱為方法或服務(wù)。屬性即對象所包含的信息，它在設(shè)計對象時確定，一般只能通過執(zhí)行對象的操作來改變。屬性值應(yīng)該指的是純粹的數(shù)據(jù)值，而不能指對象。操作描述了對象執(zhí)行的功能，若通過信息的傳遞，還可以為其他對象使用。對象具有如下特征：標識惟一性、分類性、多態(tài)性、封裝性、模塊獨立性。（2）類和實例類是具有共同屬性、共同方法的對象的集合。它描述了屬于該對象類型的所有對象的性質(zhì)，而一個對象則是其對應(yīng)類的一個實例。類是關(guān)于對象性質(zhì)的描述，它同對象一樣，包括一組數(shù)據(jù)屬性和在數(shù)據(jù)上的一組合法操作。（3）消息消息是實例之間傳遞的信息，它請求對象執(zhí)行某一處理或回答某一要求的信息，它統(tǒng)一了數(shù)據(jù)流和控制流。一個消息由三部分組成：接收消息的對象的名稱、消息標識符（消息名）和零個或多個參數(shù)。（4）繼承廣義地說，繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義它們。繼承分為單繼承與多重繼承。單繼承是指，一個類只允許有一個父類，即類等級為樹形結(jié)構(gòu)。多重繼承是指，一個類允許有多個父類。（5）多態(tài)性對象根據(jù)所接收的消息而做出動作，同樣的消息被不同的對象接收時可導(dǎo)致完全不同的行動，該現(xiàn)象稱為多態(tài)性。 疑難解答：能舉一下現(xiàn)實中的對象及其屬性和操作嗎？一輛汽車是一個對象，它包含了汽車的屬性（如顏色、型號等）及其操作（如啟動、剎車等）。一個窗口是對象，它包含了窗口的屬性（如大小、顏色等）及其操作（如打開、關(guān)閉等）。 例題詳解一、選擇題【例1】結(jié)構(gòu)化程序設(shè)計方法提出于_______。（考點1）A）20世紀50年代 B）20世紀60年代C）20世紀70年代 D）20世紀80年代解析：20世紀70年代提出了結(jié)構(gòu)化程序設(shè)計（structured programming）的思想和方法。結(jié)構(gòu)化程序設(shè)計方法引入了工程化思想和結(jié)構(gòu)化思想，使大型軟件的開發(fā)和編程得到了極大的改善。答案：C）【例2】結(jié)構(gòu)化程序設(shè)計方法的主要原則有下列4項，不正確的是_______。（考點1）A）自下向上 B）逐步