數(shù)據(jù)結(jié)構(gòu)與算法復習題及參考答案

1、2016數(shù)據(jù)結(jié)構(gòu)域算法復習題復習題集參考答案一判斷題（）1. 在決定選取何種存儲結(jié)構(gòu)時，一般不考慮各結(jié)點的值如何。（）2. 抽象數(shù)據(jù)類型與計算機內(nèi)部表示和實現(xiàn)無關(guān)。（×）3. 線性表采用鏈式存儲結(jié)構(gòu)時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。（×）4. 鏈表的每個結(jié)點中都恰好包含一個指針。（×）5.鏈表的刪除算法很簡單，因為當刪除鏈中某個結(jié)點后，計算機會自動地將后續(xù)的各個單元向前移動。（×）6. 線性表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一個復雜類型。（×）7. 順序表結(jié)構(gòu)適宜于進行順序存取，而鏈表適宜于進行隨機存取。 （

2、15;）8. 線性表在物理存儲空間中也一定是連續(xù)的。（×）9. 順序存儲方式只能用于存儲線性結(jié)構(gòu)。（）10.棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種后進先出型結(jié)構(gòu)。（）11.對于不同的使用者，一個表結(jié)構(gòu)既可以是棧，也可以是隊列，也可以是線性表。 （）12.棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種后進先出型結(jié)構(gòu)。（）13.兩個棧共享一片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出機會，應(yīng)把兩個棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。（×）14.二叉樹的度為2。（）15.若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個結(jié)點的二叉樹鏈表中只有n1個非空

3、指針域。（×）16.二叉樹中每個結(jié)點的兩棵子樹的高度差等于1。 （）17.用二叉鏈表法存儲包含n個結(jié)點的二叉樹，結(jié)點的2n個指針區(qū)域中有n+1個為空指針。（）18.具有12個結(jié)點的完全二叉樹有5個度為2的結(jié)點。（）19.二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其孩子結(jié)點的前面。（×）20.在冒泡法排序中，關(guān)鍵值較小的元素總是向前移動，關(guān)鍵值較大的元素總是向后移動。（×）21.計算機處理的對象可以分為數(shù)據(jù)和非數(shù)據(jù)兩大類。計算機處理的對象都是數(shù)據(jù)（×）22.數(shù)據(jù)的邏輯結(jié)構(gòu)與各數(shù)據(jù)元素在計算機中如何存儲有關(guān)。（×）23.算法必須用程序語言來書寫。（

4、×）24.判斷某個算法是否容易閱讀是算法分析的任務(wù)之一。（×）25.順序表是一種有序的線性表。任何數(shù)據(jù)結(jié)構(gòu)才用順序存儲都叫順序表（）26.分配給順序表的內(nèi)存單元地址必須是連續(xù)的。（）27.棧和隊列具有相同的邏輯特性。它們的邏輯結(jié)構(gòu)都是線性表（）28.樹形結(jié)構(gòu)中每個結(jié)點至多有一個前驅(qū)。（×）29.在樹形結(jié)構(gòu)中，處于同一層上的各結(jié)點之間都存在兄弟關(guān)系。（×）30.如果表示圖的鄰接矩陣是對稱矩陣，則該圖一定是無向圖。（×）31.如果表示圖的鄰接矩陣是對稱矩陣，則該圖一定是有向圖。（×）32.順序查找方法只能在順序存儲結(jié)構(gòu)上進行。（×

5、;）33.折半查找可以在有序的雙向鏈表上進行。（）34.滿二叉樹中不存在度為1的結(jié)點。（×）35.完全二叉樹中的每個結(jié)點或者沒有孩子或者有兩個孩子。（）36.對n個元素執(zhí)行快速排序，在進行第一次分組時，排序碼的比較次數(shù)總是n-1次。（）37.在有向圖中，各頂點的入度之和等于各頂點的出度之和。一、選擇題（A）1. 在n個結(jié)點的順序表中，算法的時間復雜度是O(1)的操作是：A) 訪問第i個結(jié)點（1in）和求第i個結(jié)點的直接前驅(qū)（2in） C) 刪除第i個結(jié)點（1in）B) 在第i個結(jié)點后插入一個新結(jié)點（1in） D) 將n個結(jié)點從小到大排序（C）2. 算法分析的目的是：A) 找出數(shù)據(jù)結(jié)構(gòu)

6、的合理性 B) 研究算法中的輸入和輸出的關(guān)系C) 分析算法的效率以求改進 D) 分析算法的易懂性和文檔性（A）3. 算法分析的兩個主要方面是：A) 空間復雜性和時間復雜性 B) 正確性和簡明性C) 可讀性和文檔性 D) 數(shù)據(jù)復雜性和程序復雜性（C）4. 計算機算法指的是：A) 計算方法 B) 排序方法 C) 解決問題的有限運算序列 D) 調(diào)度方法（B）5. 計算機算法必須具備輸入、輸出和 等5個特性。A) 可行性、可移植性和可擴充性 B) 可行性、確定性和有窮性C) 確定性、有窮性和穩(wěn)定性 D) 易讀性、穩(wěn)定性和安全性（B）6. 一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5

7、個元素的地址是:（A）110 （B）108 （C）100 （D）120（D）下列選項中與數(shù)據(jù)存儲結(jié)構(gòu)無關(guān)的術(shù)語是：A.順序表 B.鏈表 C.鏈隊列 D.棧（A）7. 鏈接存儲的存儲結(jié)構(gòu)所占存儲空間：（A）分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針（B）只有一部分，存放結(jié)點值（C） 只有一部分，存儲表示結(jié)點間關(guān)系的指針（D） 分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)（B）8. 帶頭結(jié)點的單鏈表head，鏈表為空的判定條件是(A)head = NULL (B) head->next =NULL ( C) head->next =head (D) head

8、!=NULL（B）9. 一個棧的輸入序列為1，2，3，n，若輸出序列的第一個元素是n，輸出第i（1in）個元素是。A) 不確定 B) ni1 C) i D) ni（B）10. 最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是 （ ）。 A) (rear1)% n=front B) rear=front C) rear1=front D) (rearl) % n=front（A）11. 循環(huán)隊列A0.m1存放其元素值，用front和rear分別表示隊頭和隊尾，則當前隊列中的元素數(shù)是:(A) (rearfrontm)%m (B) rearfront1 (C) rearf

9、ront1 (D) rearfront（B）12. 若用一個大小為6的數(shù)值來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為:(A) 1和5 (B) 2和4 (C) 4和2 ( D) 5和1（C）13. 按照二叉樹的定義，具有3個結(jié)點的二叉樹有（ ）種。A) 3 B) 4 C) 5 D) 6 利用排列組合知識來做（B）14. 若一棵二叉樹中度為l的結(jié)點個數(shù)是3，度為2的結(jié)點個數(shù)是4，則該二叉樹葉子結(jié)點的個數(shù)是:(A) 4 (B) 5 (C) 7 (D) 8（B）15. 具有n(n>0)個結(jié)點的完全二叉樹的深

10、度為:() élog2(n)ù () ë log2(n)û () ë log2(n) û+1 () élog2(n)+1ù（D）16. 對一個滿二叉樹，m個葉子，n個結(jié)點，深度為h，則:(A) n = h+m (B) h+m = 2n (C) m = h-1 (D) n = 2h-1（C）17在高度為h的完全二叉樹中，表述正確的是（ ）A.度為0的結(jié)點都在第h層上 B.第i(1i<h)層上的結(jié)點都是度為2的結(jié)點C.第i(1i<h)層上有2i-1個結(jié)點 D.不存在度為1的結(jié)點（B）18. 深度為5的二叉樹

11、至多有（ ）個結(jié)點。A) 32 B) 31 C) 16 D) 10（A）19. 用鄰接表表示圖進行深度優(yōu)先遍歷時，通常采用( )結(jié)構(gòu)來時實現(xiàn)算法。A) 棧 B) 隊列 C) 樹 D) 圖（D）20. 對N個記錄作順序查找時，當查找成功時，平均查找長度是（ ）。A) N2 B) N2/2 C) N D)（N1)/2（B）21. 當一個有n個頂點的圖用鄰接矩陣A表示時，頂點Vi的度是（ ）。(A) B) C) D)+（C）22某算法的時間復雜度為O(2n)，表明該算法的（ ）A.問題規(guī)模是2n B.執(zhí)行時間等于2n C.執(zhí)行時間近似與2n成正比 D.問題的規(guī)模近似與2n成正比（D）23“二叉樹為空

12、”意味著二叉樹（ ）A.由一些沒有賦值的空結(jié)點構(gòu)成 B.根結(jié)點沒有子樹 C.不存在 D.沒有結(jié)點（D）24數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容不涉及（ ）A.數(shù)據(jù)如何組織 B.數(shù)據(jù)如何存儲 C.數(shù)據(jù)的運算如何實現(xiàn) D.算法用什么語言描述（C）25在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲A.數(shù)據(jù)的處理方法 B.數(shù)據(jù)元素的類型 C.數(shù)據(jù)元素之間的關(guān)系 D.數(shù)據(jù)的存儲方法（D）26數(shù)據(jù)采用順序存儲，要求（ ）A.存儲的是屬于線性結(jié)構(gòu)的數(shù)據(jù) B.根據(jù)結(jié)點值的大小，有序存放各結(jié)點C.按存儲單元地址由低到高的順序存放各結(jié)點 D.各結(jié)點存放方法有規(guī)律，能隱含表示結(jié)點間的邏輯關(guān)系（D）27一個順序表所占存儲空間

13、大的大小與（ ）無關(guān)A.順序表長度 B.結(jié)點類型 C.結(jié)點中各字段的類型 D.結(jié)點存放順序（A）28數(shù)據(jù)采用鏈接存儲，要求（ ）A.每個結(jié)點占用一片連續(xù)的存儲區(qū)域 B.所有結(jié)點占用一片連續(xù)的存儲區(qū)域C.結(jié)點的最后一個字段是指針型的字段 C.每個結(jié)點有多少個后繼，就設(shè)多少個指針字段（A）29算法的時間復雜度與（ ）有關(guān)A.問題規(guī)模 B.計算機硬件性能 C.編譯程序質(zhì)量 D.程序設(shè)計語言（C）30在程序中，為了設(shè)置一個空的順序表，必須（ ）A.給各數(shù)組元素賦空值 B.給各順序表元素賦空值 C.給表示順序表長度的變量賦初始值 D.給數(shù)組變量名賦初始值（D）31若變量H是某個帶表頭結(jié)點循環(huán)單向鏈表的表

14、頭指針，則在該鏈表最后的一個結(jié)點的后繼指針域中存放的是（ ）A.H的地址 B.H的值 C.表頭結(jié)點的值 D.首元結(jié)點的地址（A）32棧和隊列的共同點在于（ ）A.邏輯特性 B.存儲結(jié)構(gòu) C.運算方法 D.元素類型（C）33棧和隊列的共同點在于（ ）A.都對存儲方法作了限制 B.都是只能進行插入、刪除運算C.都對插入、刪除的位置作了限制 D.都對插入、刪除兩中操作的先后順序作了限制（C）34若5個元素的進棧序列是1,2,3,4,5，則不可能得到出棧序列（ ）A.1，2，3，4，5 B.3，4，2，5，1 C.4，2，1，3，5 D.5，4，3，2，1（A）35順序循環(huán)隊列中是否可以插入下一個元素

15、，（ ）A.與隊首指針和隊尾指針的值有關(guān) B.只與隊尾指針的值有關(guān)，與隊首指針的值無關(guān)C.只與數(shù)組大小有關(guān)，與隊首指針和隊尾指針的值無關(guān) D.與曾經(jīng)進行過多少次插入操作有關(guān)（A）36在順序隊列中，元素的排列順序（ ）A.由元素插入隊列的先后順序決定 B.與元素值的大小有關(guān)C.與隊首指針和隊尾指針的取值有關(guān) D.與數(shù)組大小有關(guān)（C）37在高度為h的完全二叉樹中，（ ）A.度為0的結(jié)點都在第h層上 B.第i(1i<h)層上的結(jié)點都是度為2的結(jié)點C.第i(1i<h)層上有2i-1個結(jié)點 D.不存在度為1的結(jié)點（B）38一顆二叉樹如圖所示，其中序遍歷的序列為：ACEBFGDHA. ABDG

16、CEFH B. DGBAECHF C. GDBEHFCAD. ABCDEFGH（A）39采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的A先序遍歷 B中序遍歷 C后序遍歷 D按層遍歷（D）40采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的A先序遍歷 B中序遍歷 C后序遍歷 D按層遍歷（D）41.已知關(guān)鍵字序列為(51，22，83，46，75，18，68，30)，對其進行快速排序，第一趟劃分完成后的關(guān)鍵字序列是A.(18,22,30,46,51,68,75,83)B.(30,18,22,46,51,75,83,68)C.(46,30,22,18,51,75,68,83)D.(30,22,1

17、8,46,51,75,68,83)二、填空題1數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 邏輯結(jié)構(gòu) 、數(shù)據(jù)的 存儲結(jié)構(gòu) 和數(shù)據(jù)的 運算 這三個方面的內(nèi)容。2下面程序段的時間復雜度是 O(log3n) 。i 1； while（i<=n） i = i * 3；3在順序表中插入或刪除一個元素，需要平均移動 表中一半 元素，具體移動的元素個數(shù)與 表長和該元素在表中的位置 有關(guān)。4當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表的元素是，應(yīng)采用 順序 存儲結(jié)構(gòu)。5在n個結(jié)點的單鏈表中要刪除已知結(jié)點*p，需找到它的 前驅(qū)結(jié)點 的地址，其時間復雜度為O（n）。6已知L是帶表頭結(jié)點的非空單鏈表

18、，且P結(jié)點既不是首元結(jié)點，也不是尾結(jié)點，試從下列提供的答案中選擇合適的語句序列。 刪除P結(jié)點的直接后繼結(jié)點的語句序列是 (11)(4)(14) 。刪除P結(jié)點的語句序列是 (10)(12)(7)(4)(14) 。(1) P = P->next ; (2) P->next = P; (3) P->next = P->next->next(4) P->next = P->next->next; (5) while(P!=NULL) P = P->next ;(6) while(Q->next != NULL) P = Q; Q=Q->

19、next;(7) while(P->next != Q) P = P->next;(8) while(P->next->next != Q) P = P->next;(9) while(P->next->next != NULL) P = P->next;(10) Q = P; (11) Q = P->next; (12) P = L ; (13) L = L->next; (14) free(Q);7棧是一種特殊的線性表，允許插入和刪除運算的一端稱為 棧頂 。不允許插入和刪除運算的一端稱為 棧底 。8設(shè)棧S的初始狀態(tài)為空，若元素a、

20、b、c、d、e、f依次進棧，得到的出棧序列是b、d、c、f、e、a，則棧S的容量至少是 3 。9用S表示入棧操作，X表示出棧操作，若元素入棧的順序為1234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為 SXSSXSXX 。10數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為 線性 和 非線性 兩大類。11數(shù)據(jù)的運算用 算法 表示。12邏輯上相鄰的結(jié)點在存儲器中也相鄰，這是 順序 存儲結(jié)構(gòu)的特點。13在長度為n的順序表上實現(xiàn)定位操作，其算法的時間復雜度為 O(n) 。14為了實現(xiàn)隨機訪問，線性結(jié)構(gòu)應(yīng)該采用 順序 存儲。15在長度為n的順序表中插入一個元素，最多要移動 n 個元素。16棧的存儲結(jié)構(gòu)主要有 順序 和 鏈

21、式 兩種。17在編寫程序的時候，如果棧的最大長度難以預先估計，則最好使用 鏈式 棧。18在樹形結(jié)構(gòu)中，如果某結(jié)點 沒有前驅(qū)（雙親） ，則稱該結(jié)點為根結(jié)點；如果某結(jié)點 沒有后繼（孩子） ，則稱該結(jié)點為葉子。19在樹形結(jié)構(gòu)中，每個結(jié)點最多只有一個前驅(qū)（雙親）。20 由3個結(jié)點所構(gòu)成的二叉樹有 5 種形態(tài)。 21二叉樹的前序遍歷按如下三個步驟進行： 訪問根結(jié)點 ； 前序遍歷左子樹 ； 前序遍歷右子樹 ?！咀⒁猓褐幸欢ㄒ印扒靶颉眱勺?！】22二叉樹的中序遍歷按如下三個步驟進行：中序遍歷左子樹 ； 訪問根結(jié)點 ；中序遍歷左子樹 。【注意：中一定要加“中序”兩字！】23在n個頂點的無向圖中，至少有 0 條

22、邊，至多有 n(n-1)/2 條邊。24在n個頂點的有向圖中，至少有 0 條邊，至多有 n(n-1) 條邊。25如果排序不改變關(guān)鍵字相同的記錄之間的相對次序，則稱該排序方法是穩(wěn)定的。26如果排序改變了關(guān)鍵字相同的記錄之間的相對次序，則稱該排序方法是不穩(wěn)定的。27當待排關(guān)鍵字序列基本有序時，快速排序、簡單選擇排序和直接插入排序三種排序方法中，運行效率最高的是 直接插入排序 。28在一個圖中，所有頂點的度數(shù)之和是所有邊數(shù)的 2 倍。29無向圖中邊的數(shù)目等于鄰接矩陣中非零元素個數(shù)的 0.5 倍。30折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它將依

23、次與表中元素 28，6，12，20 比較大小。31在有序表（2，4，6，8，10，12，14，16，18）上用折半查找法查找元素9，其中第二次被比較的元素是 4 。32在有序表（2，4，6，8，10，12，14，16，18）上用折半查找法查找元素9，其中第三次被比較的元素是 6 。三、簡答題1對鏈表設(shè)置頭結(jié)點的作用是什么？（至少說出兩條好處）答：其好處有：（1）對帶頭結(jié)點的鏈表，在表的任何結(jié)點之前插入結(jié)點或刪除表中任何結(jié)點，所要做的都是修改前一個結(jié)點的指針域，因為任何元素結(jié)點都有前驅(qū)結(jié)點（若鏈表沒有頭結(jié)點，則首元素結(jié)點沒有前驅(qū)結(jié)點，在其前插入結(jié)點和刪除該結(jié)點時操作復雜些）。（2）對帶頭結(jié)點的鏈

24、表，表頭指針是指向頭結(jié)點的非空指針，因此空表與非空表的處理是一樣的。2.寫出下列程序段的輸出結(jié)果（隊列中的元素類型QElem Type為char）。void main( )Queue Q; Init Queue (Q);Char x=e; y=c;EnQueue (Q,h); EnQueue (Q,r); EnQueue (Q, y);DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,a); while(!QueueEmpty(Q) DeQueue (Q,y); printf(y); ;Printf(x);解：char3. 簡述以下

25、算法的功能（棧和隊列的元素類型均為int）。void algo3(Queue &Q)Stack S; int d;InitStack(S);while(!QueueEmpty(Q) DeQueue (Q,d); Push(S,d);while(!StackEmpty(S) Pop(S,d); EnQueue (Q,d); 解：利用棧S作為緩存空間，將隊列Q中的元素進行逆置（即相對于原順序進行倒排）。4. 描述以下三個概念的區(qū)別：頭指針、頭結(jié)點、首元結(jié)點（第一個元素結(jié)點）。在單鏈表中設(shè)置頭結(jié)點的作用是什么？答：首元結(jié)點是指鏈表中存儲線性表中第一個數(shù)據(jù)元素a1的結(jié)點。為了操作方便，通常在鏈

26、表的首元結(jié)點之前附設(shè)一個結(jié)點，稱為頭結(jié)點，該結(jié)點的數(shù)據(jù)域中不存儲線性表的數(shù)據(jù)元素，其作用是為了對鏈表進行操作時，可以對空表、非空表的情況以及對首元結(jié)點進行統(tǒng)一處理。頭指針是指向鏈表中第一個結(jié)點（或為頭結(jié)點或為首元結(jié)點）的指針。若鏈表中附設(shè)頭結(jié)點，則不管線性表是否為空表，頭指針均不為空。否則表示空表的鏈表的頭指針為空。這三個概念對單鏈表、雙向鏈表和循環(huán)鏈表均適用。是否設(shè)置頭結(jié)點，是不同的存儲結(jié)構(gòu)表示同一邏輯結(jié)構(gòu)的問題。 頭結(jié)點headàdatalink 頭指針 首元結(jié)點簡而言之，頭指針是指向鏈表中第一個結(jié)點（或為頭結(jié)點或為首元結(jié)點）的指針；頭結(jié)點是在鏈表的首元結(jié)點之前附設(shè)的一個結(jié)點；數(shù)

27、據(jù)域內(nèi)只放空表標志和表長等信息（內(nèi)放頭指針？那還得另配一個頭指針?。┦自亟Y(jié)點是指鏈表中存儲線性表中第一個數(shù)據(jù)元素a1的結(jié)點。5. 25738L對以下單鏈表執(zhí)行下列語句，簡述代碼的功能，并畫出單鏈表結(jié)果示意圖。T = L;while(T->next != NULL) T->data = 2 * T->data; T = T->next;解：代碼功能：除最后一個結(jié)點之外，每個結(jié)點的數(shù)值部分改變?yōu)樵档?倍。L單鏈表結(jié)果示意圖如下：14104866. 請畫出下圖的鄰接矩陣和鄰接表【本題較簡單，不提供答案】7假設(shè)二叉樹采用順序存儲結(jié)構(gòu)，如圖所示。（1） 畫出二叉樹表示；（2）

28、 寫出先序遍歷、中序遍歷和后序遍歷的結(jié)果；（3） 寫出結(jié)點值c 的雙親結(jié)點，其左、右孩子；1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20eafdgcjhib8. 樹和二叉樹之間有什么樣的區(qū)別與聯(lián)系？解：聯(lián)系：（1）二叉樹是樹的一種，是一種特殊的樹；（2）對樹適用的操作或規(guī)律都可應(yīng)用到二叉樹上。區(qū)別：（1）二叉樹是一種特殊的樹，特殊在，第一是有序樹，第二結(jié)點的度數(shù)不超過2；（2）普通二叉樹有3個性質(zhì)，完全二叉樹有5個性質(zhì)，普通樹是沒有這些性質(zhì)的。9. 一棵二叉樹中的結(jié)點的度或為0或為2，則二叉樹的枝數(shù)為2(n0-1)，其中n0是度為0的結(jié)點的

29、個數(shù)。證明：設(shè)總結(jié)點數(shù)為n，度數(shù)為2的結(jié)點數(shù)為n2，依題意，該二叉樹沒有度數(shù)為1的結(jié)點。那么n= n0+ n2 假定分枝數(shù)為B，每個結(jié)點通過一個分枝跟其雙親相連，除根結(jié)點外；這意味著除根結(jié)點外，每個結(jié)點對應(yīng)一個分枝，即B=n-1 ,根據(jù)二叉樹的性質(zhì)3，n2=n0+1 ,于是B=n-1= n0+ n2-1= n0+ n0-1-1=2(n0-1)10. 一個深度為L的滿K叉樹有以下性質(zhì)：第L層上的結(jié)點都是葉子結(jié)點，其余各層上每個結(jié)點都有K棵非空子樹，如果按層次順序從1開始對全部結(jié)點進行編號，求：（1）各層的結(jié)點的數(shù)目是多少？（2）編號為n的結(jié)點的雙親結(jié)點（若存在）的編號是多少？（3）編號為n的結(jié)點

30、的第i 個孩子結(jié)點（若存在）的編號是多少？（4）編號為n的結(jié)點有右兄弟的條件是什么？如果有，其右兄弟的編號是多少？請給出計算和推導過程。11. 如果用一個循環(huán)數(shù)組q0.m-1表示隊列時，該隊列只有一個隊列頭指針front，不設(shè)隊列尾指針rear，而改置計數(shù)器count用以記錄隊列中結(jié)點的個數(shù)。（1）編寫實現(xiàn)隊列的三個基本運算：判空、入隊、出隊（2）隊列中能容納元素的最多個數(shù)是多少？【此題超出教學范圍，不作解答?！緼BCDEF12. 已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF，中序遍歷結(jié)果為CBAEDF，畫出此二叉樹。并給出其后序遍歷的結(jié)果。解：根據(jù)已知的前序和中序遍歷結(jié)果，建立二叉樹如圖所示。

31、 此二叉樹的后序遍歷結(jié)果為：CBEFDA13假設(shè)以二叉鏈表表示二叉樹，其類型定義如下：typedef struct node char data;struct node*lchild, *rchild; 左右孩子指針 *BinTree；閱讀下列程序。void f13(BinTree T)InitStack(S); 初始化一個堆棧Swhile(T | !StackEmpty(S)while(T)Push(S,T);T=T->lchild;if(!StackEmpty(S)T=Pop(S);printf(“%c”,T->data);T=T->rchild;回答下列問題：(1)已知

32、以T為根指針的二叉樹如圖所示，請寫出執(zhí)行f13(T)的輸出結(jié)果：(2)簡述算法f13的功能。14設(shè)如下圖所示的二叉樹B的存儲結(jié)構(gòu)為二叉鏈表，root為根指針，結(jié)點結(jié)構(gòu)為：（lchild,data,rchild）。其中l(wèi)child，rchild分別為指向左右孩子的指針，data為字符型，root為根指針，試回答下列問題：（1）對下列二叉樹B，執(zhí)行下列算法traversal(root)，試指出其輸出結(jié)果；（2）假定二叉樹B共有n個結(jié)點，試分析算法traversal(root)的時間復雜度。二叉樹BAB D C F G EC的結(jié)點類型定義如下：struct nodechar data;struct

33、node *lchild, rchild;C算法如下：void traversal(struct node *root)if (root) printf(“%c”, root->data); traversal(root->lchild); printf(“%c”, root->data);traversal(root->rchild);解：（1）輸出結(jié)果：ABCCEEBDFFGG（2）時間復雜度：15.已知有向圖的鄰接表如圖所示，請回答下面問題：(1)給出該圖的鄰接矩陣；(2)從結(jié)點A出發(fā)，寫出該圖的深度優(yōu)先遍歷序列。16. 設(shè)要將序列Q, H, C, Y, P, A

34、, M, S, R, D, F, X中的關(guān)鍵碼按字母序的升序重新排列。簡述快速排序的思路，并以第一個元素為軸中心，給出用快速排序?qū)π蛄幸惶藪呙璧慕Y(jié)果。解：快速排序的思路：（1）從序列中任意選取一個元素作為樞軸，以樞軸為標準將序列劃分成三部分。第一部分的所有元素比樞軸小，第二部分是樞軸自己，第三部分的所有元素比樞軸大。這樣處理以后，樞軸的位置已經(jīng)排好。（2）對上述劃分的第一部分序列和第三部分序列循環(huán)執(zhí)行第（1）步的操作，直到劃分的序列中只有一個元素為止。針對題目給定的序列，快速排序一趟掃描的結(jié)果是：F, H, C, D, P, A, M, Q, R, S, Y, X.四、算法填空1假設(shè)線性表用不

35、帶頭結(jié)點的單向鏈表表示，結(jié)點數(shù)據(jù)類型如下：struct node int s; node * next;下面的算法用于求線性表的長度。請在方框中填入適當?shù)膬?nèi)容，將算法補充完整。int GetLinkLen(node *h) int s;s=0; while(h) s=s+1; h=h->next ;return(s);2設(shè)有n個順序表元素存放在數(shù)組v1vn中，數(shù)組v的最大下標為n0，元素類型為TElem. 下面的算法用于刪除順序表中第一個值為x的元素。請在方框中填入適當內(nèi)容，將算法補充完整。void DeleValue (TElem x) int i, j; i=1; While( vi

36、!=x && i<=n ) i=i+1; if(i<=n) for(j=n;j>i;j-) vj-1=vj; n- ;五、算法設(shè)計題1.從順序表中刪除值為x的元素。答：假定順序表為a，有效元素個數(shù)為n，下標從0開始。int DeleteReapeatValue(datatype * a, int * pNum, datatype x) int i, k, n; n=*pNum; k=0; for(i=0;i<n;i+)If(ai=x) k+;Else ai-k=ai;*pNum=n-1;return k;2.將順序存儲結(jié)構(gòu)線性表（v1, v2, , vn

37、）改變成（vk+1,vk+2, vn,v1,v2, vk）。答：void ChangeSequence(datatype * v) datatype aSIZE; for(int i=1;i<n;i+) ai=vi; for(i=1;i<=n;i+) v(k+i)%n=ai;3.將順序存儲的線性表（v1, v2, , vn）改變成（v1, v3, v5,）。答：void ChangeSequence(datatype * v) for(int i=3;i<=n;i+=2) vi-i/2=vi4.從順序表中刪除重復的元素，并使剩余元素間的相對次序保持不變。答：int Delet

38、eAllReapeatValue(datatype * a, int * pNum) int n=*pNum; int i , j ; for(i=0;i<n;i+) for(j=i+1; j<n;j+) if(ai!= INFINITY && ai=aj) aj= INFINITY; return DeleteReapeatValue(a,pNum, INFINITY);5.從鍵盤輸入一系列整數(shù)，建立一個長度為n的、不含重復元素的順序表。答：int CreateSequence() int aSIZE; int i=0, j, k; while(i<n) s

39、canf(“%d”, &k); for(j=0; j<=i ; j+) if(aj=k) break; if(j>i) a+i=k;6.從鍵盤輸入n個整數(shù)，建立帶表頭結(jié)點的單向鏈表。答：LinkList CreateList() int i=0 , j , k; LinkList head=(Node*)malloc(sizeof(Node); Node* r=head,*p=NULL; While(i<n) scanf(“%d”, &k); p=head->next; while(p)if(p->data=k) break;p=p->next; if(p=NULL) s=(Node*)malloc(sizeof(Node); s->data=k; r->next=s; r=s i+; ret