1、黃老師：       題型結構如下：       單項選擇題，15小題，30分；       填空題，5小題，10分；       綜合應用題，50分（樹、圖、查找）       算法設計與分析，2選1,10分（線性結構）試卷中一些算法只給英文名稱；考查范圍 (黑體字為建議的重點考查內容；

2、紅字為備注；藍字為擬納入的考研大綱內容)一、 緒論（一） 算法、數(shù)據(jù)結構基本概念（二） 算法分析中O（f（n）符號的含義（三） 時間復雜度簡單分析表示二、線性表（一）線性表的定義和基本操作（二）線性表的實現(xiàn)1.順序存儲2.鏈式存儲3.線性表的應用 三、棧、隊列 （一）棧和隊列的基本概念（二）棧和隊列的順序存儲結構（三）棧和隊列的鏈式存儲結構（四）棧和隊列的應用四、樹與二叉樹（一）樹的概念（二）二叉樹1.二叉樹的定義及其主要特征2.二叉樹的順序存儲結構和鏈式存儲結構3.二叉樹的遍歷及應用（三）樹、森林1. 森林與二叉樹的轉換2. 樹的存儲結構；3.樹和森林的遍歷4.線索二叉樹的基本概念

3、和構造（四）二叉樹的應用1.哈夫曼（Huffman）樹和哈夫曼編碼 2.二叉排序樹五、 圖（一）   圖的基本概念（二）   圖的存儲及基本操作1.     鄰接矩陣法2.     鄰接表法（三）   圖的遍歷1.     深度優(yōu)先搜索2.     廣度優(yōu)先搜索（四）  

4、; 圖的基本應用1.     最?。ù鷥r）生成樹2.     最短路徑3.     拓撲排序4.     關鍵路徑六、  查找 （一）   查找的基本概念（二）   順序查找法（三）   折半查找法（四）  二叉查找樹及其基本操作（只考察基本概念）（五） 平衡

5、二叉樹（只考察基本概念）（六）   散列（Hash）表（七）   查找算法的分析及應用 七、      排序（一）   排序的基本概念（二）   直接插入排序（三）   氣泡排序（bubble sort）（四）   簡單選擇排序（五）   希爾排序（shell sort）（六）   快速排

6、序（七）   堆排序（八）   二路歸并排序（merge sort）（九）  各種排序算法的比較（十）  排序算法的應用 選擇題1、順序隊列的出隊操作，正確修改隊首指針的是（ B ） （A）sq.front = (sq.front+1)%maxsize; （B）sq.front = sq.front+1; （C）sq.rear = (sq. rear +1)%maxsize; （D）sq.rear = sq. rear +1;2、非空的循環(huán)單鏈表head的尾結點（由指針p指）滿足（ C

7、 ） （A）p->next = NULL （B）p = NULL （C）p->next = head （D）p = head3、在單鍵表中，刪除p所指結點的直接后繼，其中指針修改為（ A ） （A）p->next = p->next ->next; （B）p = p->next; p->next = p->next->next; （C）p->next = p->next; （D）p = p->next ->next;4、通常要求同一邏輯結構中的所有數(shù)據(jù)元素具有相同的特性，這意味著（ B ） （A）數(shù)據(jù)元素具有同一特點

8、 （B）不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應數(shù)據(jù)項的類型也要一致 （C）每個數(shù)據(jù)元素都一樣 （D）數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等5、關于線性表，下列說法正確的是（ D ） （A）每個元素都有一個直接前驅和直接后繼 （B）線性表中至少要有一個元素 （C）表中諸元素的排列順序必須是由小到大或由大到小的 （D）除第一元素和最后一個元素外，其余每個元素都有一個且僅有一個直接前驅和直接后繼6、帶頭結點的單鏈表，其表頭指針為head，則該單鏈表為空的判斷條件是（ B ） （A）head = NULL （B）head->next = NULL （C）head->next = he

9、ad （D）head != NULL7、含n個頂點的連通圖中的任意一條簡單路徑，其長度不可能超過（C ） （A）1 （B）n/2 （C）n-1 （D）n8、設有一個順序棧S，元素S1, S2, S3, S4, S5, S6依次進棧，如果6個元素出棧的順序是S2, S3, S4, S6, S5, S1，則棧的容量至少應該是（ B ） （A）2 （B）3 （C）5 （D）69、設深度為k的二叉樹上只有度為0和度為2的結點，則這類二叉樹上所含結點的總數(shù)最少為（ C ）個 （A）k+1 （B）2k （C）2k -1 （D）2k +110、從具有n個結點的單鏈表中查找指定結點時，若查找每個結點的概率相等

10、，在查找成功的情況下，平均需要比較（ D ）個結點。 （A）n （B）n/2 （C）(n-1)/2 （D）(n+1)/211、從對順序表上的插入、刪除算法的時間復雜度分析來說，通常以（ B ）為標準進行操作。 （A）條件判斷 （B）結點移動 （C）算法表達式 （D）賦值語句12、深度為6的二叉樹最多有（ B ）個結點 （A）64 （B）63 （C）32 （D）3113、在一個單鏈表中，已知q所指結點是p所指結點的直接前驅，若在p,q之間插入s結點，則執(zhí)行（ B ）操作。 （A）s->next = p->next; p->next = s; （B）q->next = s;

11、 s->next = p; （C）p->next = s->next; s->next = p; （D）p->next = s; s->next = q;14、在線性表的下列存儲結構中，讀取元素花費時間最少的是（ D ） （A）單鏈表 （B）雙鏈表 （C）循環(huán)鏈表 （D）順序表15、以下關于哈夫曼樹的說法，錯誤的是（ D ） （A）一般在哈夫曼樹中，權值越大的葉子結點離根結點越近 （B）哈夫曼 樹中沒有度數(shù)為1的分支結點 （C）若初始森林中共有n棵二叉樹，最終求得的哈夫曼樹共有2n-1個結點 （D）若初始森林中共有n棵二叉樹，需要進行2n-1次合并后才能剩下

12、一棵最終的哈夫曼樹16.計算機算法指的是解決問題的有限運算序列，它必須具備輸入、輸出和（ B ）等5個特性。A. 可執(zhí)行性、可移植性和可擴充性 B. 可行性、確定性和有窮性C. 確定性、有窮性和穩(wěn)定性D. 易讀性、穩(wěn)定性和安全性17.線性表采用鏈表存儲地址時（ D ）。A. 必須是連續(xù)的。B. 部分地址必須是連續(xù)的。C. 一定是不連續(xù)的。 D. 連續(xù)不連續(xù)都可以。18.設循環(huán)隊列中數(shù)組的下標范圍是0n1，其頭指針front指向隊首元素，rear指向隊尾元素，則隊列的長度為（D）。Arearfront Brearfront1 C （rearfront1）（n1） D（rearfrontn1）n1

13、9線性表的鏈式存儲結構與順序（連續(xù)）存儲結構相比優(yōu)點是（C ）A所有的操作/運算 算法簡單 B便于隨機存取C 便于插入和刪除 D便于查找20.一個棧的輸入序列為A，B，C，D，E，則下列序列中不可能是棧的輸出序列的是（ B ）。AB C D A E BE D A C B C B C A D E DA E D C B22、在解決計算機主機與打印機之間速度不匹配問題時通常設置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依相同次序從該緩沖區(qū)中取出數(shù)據(jù)打印。該緩沖區(qū)作為數(shù)據(jù)結構是一個（ B）結構。A. 棧 B.隊列 C.表（Table） D.線性表23、 下面四棵樹中，數(shù)字表示相

14、應葉子結點的權值，則（ D ）是哈夫曼樹（Huffman Tree）。24、棧和隊列的共同點是（ C ）。A. 都是先進先出B. 都是先進后出 C. 只允許在端點處插入和刪除元素D. 沒有共同點25、串是一種特殊的線性表，其特殊性體現(xiàn)在（ B ）。A. 可以順序存儲B. 數(shù)據(jù)元素是一個字符C. 可以鏈接存儲D. 數(shù)據(jù)元素可以是多個字符26 帶頭節(jié)點的單鏈表head為空的判定條件是(A).A. head->next=NULL B. head=NULLC. head->next=head D. head!=NULL27 對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，該矩陣的大小是

15、（D）A. n B. (n-1)2C. n-1D. n228 設有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作（ B ）。A. 連接 B. 模式匹配C. 求子串D. 求串長29 下列排序方法中，（ C ）不易于在單鏈表上實現(xiàn)。A 直接插入排序 B冒泡排序 C 快速排序D 簡單選擇排序 30 下面關于圖的存儲的敘述中，哪一個是正確的。 （A） A用鄰接矩陣法存儲圖,占用的存儲空間數(shù)只與圖中結點個數(shù)有關,而與邊數(shù)無關   B用鄰接矩陣法存儲圖,占用的存儲空間數(shù)只與圖中邊數(shù)有關,而與結點個數(shù)無關  C用鄰接表法存儲圖，占用的存儲空間數(shù)只與圖中結點個數(shù)有關，

16、而與邊數(shù)無關  D用鄰接表法存儲圖，占用的存儲空間數(shù)只與圖中邊數(shù)有關，而與結點個數(shù)無關 31.排序方法中，從未排序序列中挑選元素，并將其依次與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為（ C ）A.快速排序 B. 起泡排序 C插入排序 D. 選擇排序32.請指出在順序表2、5、7、10、14、15、18、23、35、41、52中，用二分法查找關鍵碼12需做多少次關鍵碼比較。 （D）A.2 B.3 C. 5 D. 4 33.給定下列有向圖和初始結點V1, 按深度優(yōu)先遍歷的結點序列為(B)A、V1，V3，V4，V5，V2 B、V1，V2

17、，V4，V5，V3C、V1，V2，V5，V3，V4D、V1，V2，V3，V4，V534 順序查找法適合于存儲結構為（ B ）的線性表。A散列存儲 B 順序存儲或鏈接存儲 C 壓縮存儲 D 索引存儲35 對線性表進行二分存儲時，要求線性表必須（ C ）。A 以順序方式存儲 B以鏈接方式存儲 C 以順序方式存儲，且節(jié)點按關鍵字有序排序D 以鏈接方式存儲，且節(jié)點按關鍵字有序排序二填空題1. 若一個算法的基本語句的執(zhí)行次數(shù)為(n3+n2log2n+14n)/n2，則該算法的時間復雜度為_ O(n)_。2. 6.設棧S和隊列Q的初始狀態(tài)為空，元素a、b、c、d、e、f將依次入棧S，一個元素出棧后即進入隊

18、列Q。若這6個元素出隊列的順序是b、d、c、f、e、a，則棧S的容量至少應該是 3 ，上述過程才不會出錯。3. 設有一空隊列Q，經(jīng)Q. EnQueue(1)，Q. DeQueue ()，Q. EnQueue (2)，Q. EnQueue (3)，Q. EnQueue(4)，Q. DeQueue ()；Q. EnQueue (5)一系列操作后。隊列中從隊首到隊尾的元素依次是_ _3 4 54. 空字符串與空格串的區(qū)別在于 空格串是一個字符串，由若干空格組成；空字符串中沒有字符 。5. 7已知某二叉樹的后序遍歷序列是BDECA, 中序遍歷序列是BADCE，那么它的前序遍歷序列是 ABCDE 。6.

19、 寫出右圖所示二叉樹按后序遍歷的結果 17,23,45,65,78,09,31,53,87 。7. 寫出右圖所示二叉樹度為1的內部結點的值 09 。8. 二叉樹的第k層的結點數(shù)最多為_2k-1_。9. 已知完全二叉樹的第4層（根結點為第1層）總共只有2個結點，則其葉子結點數(shù)是 5 。10. 某表達式二叉樹按先序遍歷的結果為+a*+bcd，令a=6,b=3,c=4,d=2，則該表達式的值等于 20 。11. 弗洛伊德（Floyd）算法用于求_每一對頂點之間_的最短路徑問題。12. 構造最小生成樹的經(jīng)典算法中，_克魯斯卡爾（Kruskal）算法_更適用于求稀疏網(wǎng)的最小生成樹。13. 假定一個數(shù)列2

20、5，43，62，31，48，56，采用的散列函數(shù)為H(k)=k mod 7, 則元素48的同義詞是_62_。五應用題3632664820311 已知關鍵字序列為36, 31, 20, 32, 66, 48,依次將各元素插入到一棵初始為空的二叉排序樹，畫出對應的二叉排序樹。2 已知二叉樹如左下圖，試寫出后序遍歷結果。ACFGDB3. 現(xiàn)有森林如右上圖，請畫出對應的二叉樹。4.已知一顆二叉樹遍歷的先序序列為ABDFIGCEHJ，中序序列為BIFDGAEJHC，請畫出這顆二叉樹。答案： 5.已知一顆二叉樹如下圖所示，將此二叉樹轉換為森林。答案：6.圖G各頂點的連接關系及相應權值如下圖所示。（1）畫出

21、圖的鄰接表存儲圖示（2）從頂點1開始對圖進行廣度優(yōu)先遍歷，寫出遍歷結果；（3）使用Kruskal算法求該圖的最小生成樹，給出的形成過程。（11分）541533262646737.設Hash函數(shù)為H(K)=K mod 7，哈希表的地址空間為0，6，開始時哈希表為空，用平方探測法解決沖突，請畫出依次插入鍵值9，14，10，56，30后的哈希表。8. 在雙循環(huán)鏈表中，寫出在指針P所指結點之前插入指針S所指結點的執(zhí)行語句序列；結點定義如下：struct Node char data; Node *next;Node *back; ；9. 設右圖為某樹的二叉樹表示，請畫出該樹。10. 簡要說明快速排序的

22、排序思想, 并給出算法時間復雜度。根據(jù)所給序列（49，38，65，97，76，13，27，50），設選第一個元素為支點/參考值（pivot），寫出快速排序的第一趟排序的結果。解答：先選一個軸值（即比較的基準），通過一趟排序將待排序記錄分割成獨立的兩部分，前一部分記錄的關鍵碼均小于或等于軸值，后一部分記錄的關鍵碼均大于或等于軸值，然后分別對這兩部分重復上述方法，直到整個序列有序。11. 運用堆排序（Heapsort）方法，設初始序列為（46，88，45，39，70，58，101，10，66，34），若按教材上的算法建初始堆，畫出初始堆的樹狀圖。12. 設Hash函數(shù)為H(K)=K mod 7，哈

23、希表的地址空間為0，6，開始時哈希表為空，用線性探測法解決沖突，請畫出依次插入鍵值23，14，9，6，30，12，18后的哈希表。13.圖G各頂點的連接關系及相應權值如右圖所示。（1）畫出該圖的鄰接距陣；（2）并從頂點0開始對圖進行廣度優(yōu)先遍歷，寫出遍歷結果；（3）使用Prim算法求該圖的最小生成樹，畫出其生成過程。14. 如圖所示為一有向圖，試求：在鄰接矩陣和(逆)鄰接表存儲結構下利用深度和廣度優(yōu)先算法遍歷序列。15. 求出如圖所示的AOE網(wǎng)中所有關鍵路徑，請寫出事件的最早發(fā)生時間和最晚發(fā)生時間、活動的最早開始時間和最晚開始時間，以及求得的關鍵路徑（10分）。答案：事件V0V1V2V3V4V

24、5V6V7最早發(fā)生時間034158211925最晚發(fā)生時間035158231925活動a0a1a2a3a4a5a6a7a8a9a10a11最早開始時間00334815158211519最晚開始時間018358171511231519差值015010203200是否關鍵活動是是是是是是關鍵路徑有兩條：和16. 已知一組關鍵字為25，18，46，2，53，39，32，4，74，67，60，11，按表中元素的順序依次插入一棵初始為空的二叉排序樹，畫出插入完成之后的二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。答案：由已知關鍵字組進行構造時，是從空二叉排序樹開始依次選取關鍵字通過查找和插入

25、而生成出二叉排序樹。二叉排序樹的生成過程如下圖：關鍵字25查找成功時比較1次，關鍵字18，46查找成功時各比較2次，關鍵字4，39，53查找成功時各比較3次，關鍵字11，32，74查找成功時各比較4次，關鍵字11，67查找成功時各比較5次，關鍵字60查找成功時比較6次，則：ASL=（1*1+2*2+3*3+3*4+2*5+1*6）/12=42/12=3.517. 簡要說明快速排序的排序思想. 根據(jù)所給序列（49，38，65，97，76，13，27，50），設選第一個元素為支點/參考值（pivot），寫出快速排序的第一趟排序的結果。Solution:18. 圖G各頂點的連接關系及相應權值如右圖所

26、示。（1）畫出該圖的鄰接距陣；（2）并從頂點0開始對圖進行廣度深度優(yōu)先遍歷，寫出遍歷結果；（3）使用Prim, Kruskal算法求該圖的最小生成樹，畫出其生成過程。Prim算法求該圖的最小生成樹19. 在什么樣的情況下，等長編碼是最優(yōu)的前綴碼? 在每個字符的使用概率相同的情況下，也即在哈夫曼樹中每片葉子的權重相等的時候，等長編碼是最優(yōu)的前綴碼。19.設右圖為某樹的二叉樹表示，請畫出該樹。（或者樹到二叉樹的題）解 20.假設用于通信的電文由字符集A, B, C, D, R中的字母構成，這5個字母在電文中出現(xiàn)的頻率依次為40, 20, 10, 10, 20 。請畫出對應的 編碼哈夫曼樹（Huffman）；求出每個字符的哈夫曼編碼。四. 算法設計與分析 ：1.請設計求n的階乘的遞歸算法與非遞歸算法，其中非遞歸算法請用?；蜿犃袑崿F(xiàn)；參考答案：long Factorial1 ( long n ) if ( n