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

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

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

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

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

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

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

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

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

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

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

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

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

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

14、頭指針，則在該鏈表最后的一個(gè)結(jié)點(diǎn)的后繼指針域中存放的是（ ）A.H的地址 B.H的值 C.表頭結(jié)點(diǎn)的值 D.首元結(jié)點(diǎn)的地址（A）32棧和隊(duì)列的共同點(diǎn)在于（ ）A.邏輯特性 B.存儲(chǔ)結(jié)構(gòu) C.運(yùn)算方法 D.元素類型（C）33棧和隊(duì)列的共同點(diǎn)在于（ ）A.都對(duì)存儲(chǔ)方法作了限制 B.都是只能進(jìn)行插入、刪除運(yùn)算C.都對(duì)插入、刪除的位置作了限制 D.都對(duì)插入、刪除兩中操作的先后順序作了限制（C）34若5個(gè)元素的進(jìn)棧序列是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)隊(duì)列中是否可以插入下一個(gè)元素

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

16、CEFH B. DGBAECHF C. GDBEHFCAD. ABCDEFGH（A）39采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹的A先序遍歷 B中序遍歷 C后序遍歷 D按層遍歷（D）40采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類似于二叉樹的A先序遍歷 B中序遍歷 C后序遍歷 D按層遍歷（D）41.已知關(guān)鍵字序列為(51，22，83，46，75，18，68，30)，對(duì)其進(jìn)行快速排序，第一趟劃分完成后的關(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ù)的 存儲(chǔ)結(jié)構(gòu) 和數(shù)據(jù)的 運(yùn)算 這三個(gè)方面的內(nèi)容。2下面程序段的時(shí)間復(fù)雜度是 O(log3n) 。i 1； while（i<=n） i = i * 3；3在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng) 表中一半 元素，具體移動(dòng)的元素個(gè)數(shù)與 表長(zhǎng)和該元素在表中的位置 有關(guān)。4當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表的元素是，應(yīng)采用 順序 存儲(chǔ)結(jié)構(gòu)。5在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，需找到它的 前驅(qū)結(jié)點(diǎn) 的地址，其時(shí)間復(fù)雜度為O（n）。6已知L是帶表頭結(jié)點(diǎn)的非空單鏈表

18、，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語(yǔ)句序列。 刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語(yǔ)句序列是 (11)(4)(14) 。刪除P結(jié)點(diǎn)的語(yǔ)句序列是 (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棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為 棧頂 。不允許插入和刪除運(yùn)算的一端稱為 棧底 。8設(shè)棧S的初始狀態(tài)為空，若元素a、

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

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

22、邊，至多有 n(n-1)/2 條邊。24在n個(gè)頂點(diǎn)的有向圖中，至少有 0 條邊，至多有 n(n-1) 條邊。25如果排序不改變關(guān)鍵字相同的記錄之間的相對(duì)次序，則稱該排序方法是穩(wěn)定的。26如果排序改變了關(guān)鍵字相同的記錄之間的相對(duì)次序，則稱該排序方法是不穩(wěn)定的。27當(dāng)待排關(guān)鍵字序列基本有序時(shí)，快速排序、簡(jiǎn)單選擇排序和直接插入排序三種排序方法中，運(yùn)行效率最高的是 直接插入排序 。28在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和是所有邊數(shù)的 2 倍。29無(wú)向圖中邊的數(shù)目等于鄰接矩陣中非零元素個(gè)數(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 。三、簡(jiǎn)答題1對(duì)鏈表設(shè)置頭結(jié)點(diǎn)的作用是什么？（至少說(shuō)出兩條好處）答：其好處有：（1）對(duì)帶頭結(jié)點(diǎn)的鏈表，在表的任何結(jié)點(diǎn)之前插入結(jié)點(diǎn)或刪除表中任何結(jié)點(diǎn)，所要做的都是修改前一個(gè)結(jié)點(diǎn)的指針域，因?yàn)槿魏卧亟Y(jié)點(diǎn)都有前驅(qū)結(jié)點(diǎn)（若鏈表沒(méi)有頭結(jié)點(diǎn)，則首元素結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，在其前插入結(jié)點(diǎn)和刪除該結(jié)點(diǎn)時(shí)操作復(fù)雜些）。（2）對(duì)帶頭結(jié)點(diǎn)的鏈

24、表，表頭指針是指向頭結(jié)點(diǎn)的非空指針，因此空表與非空表的處理是一樣的。2.寫出下列程序段的輸出結(jié)果（隊(duì)列中的元素類型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. 簡(jiǎn)述以下

25、算法的功能（棧和隊(duì)列的元素類型均為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作為緩存空間，將隊(duì)列Q中的元素進(jìn)行逆置（即相對(duì)于原順序進(jìn)行倒排）。4. 描述以下三個(gè)概念的區(qū)別：頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）。在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是什么？答：首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。為了操作方便，通常在鏈

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

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

28、 寫出先序遍歷、中序遍歷和后序遍歷的結(jié)果；（3） 寫出結(jié)點(diǎn)值c 的雙親結(jié)點(diǎn)，其左、右孩子；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）對(duì)樹適用的操作或規(guī)律都可應(yīng)用到二叉樹上。區(qū)別：（1）二叉樹是一種特殊的樹，特殊在，第一是有序樹，第二結(jié)點(diǎn)的度數(shù)不超過(guò)2；（2）普通二叉樹有3個(gè)性質(zhì)，完全二叉樹有5個(gè)性質(zhì)，普通樹是沒(méi)有這些性質(zhì)的。9. 一棵二叉樹中的結(jié)點(diǎn)的度或?yàn)?或?yàn)?，則二叉樹的枝數(shù)為2(n0-1)，其中n0是度為0的結(jié)點(diǎn)的

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

30、的第i 個(gè)孩子結(jié)點(diǎn)（若存在）的編號(hào)是多少？（4）編號(hào)為n的結(jié)點(diǎn)有右兄弟的條件是什么？如果有，其右兄弟的編號(hào)是多少？請(qǐng)給出計(jì)算和推導(dǎo)過(guò)程。11. 如果用一個(gè)循環(huán)數(shù)組q0.m-1表示隊(duì)列時(shí)，該隊(duì)列只有一個(gè)隊(duì)列頭指針front，不設(shè)隊(duì)列尾指針rear，而改置計(jì)數(shù)器count用以記錄隊(duì)列中結(jié)點(diǎn)的個(gè)數(shù)。（1）編寫實(shí)現(xiàn)隊(duì)列的三個(gè)基本運(yùn)算：判空、入隊(duì)、出隊(duì)（2）隊(duì)列中能容納元素的最多個(gè)數(shù)是多少？【此題超出教學(xué)范圍，不作解答?！緼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); 初始化一個(gè)堆棧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;回答下列問(wèn)題：(1)已知

32、以T為根指針的二叉樹如圖所示，請(qǐng)寫出執(zhí)行f13(T)的輸出結(jié)果：(2)簡(jiǎn)述算法f13的功能。14設(shè)如下圖所示的二叉樹B的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，root為根指針，結(jié)點(diǎn)結(jié)構(gòu)為：（lchild,data,rchild）。其中l(wèi)child，rchild分別為指向左右孩子的指針，data為字符型，root為根指針，試回答下列問(wèn)題：（1）對(duì)下列二叉樹B，執(zhí)行下列算法traversal(root)，試指出其輸出結(jié)果；（2）假定二叉樹B共有n個(gè)結(jié)點(diǎn)，試分析算法traversal(root)的時(shí)間復(fù)雜度。二叉樹BAB D C F G EC的結(jié)點(diǎn)類型定義如下：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）時(shí)間復(fù)雜度：15.已知有向圖的鄰接表如圖所示，請(qǐng)回答下面問(wèn)題：(1)給出該圖的鄰接矩陣；(2)從結(jié)點(diǎn)A出發(fā)，寫出該圖的深度優(yōu)先遍歷序列。16. 設(shè)要將序列Q, H, C, Y, P, A

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

35、帶頭結(jié)點(diǎn)的單向鏈表表示，結(jié)點(diǎn)數(shù)據(jù)類型如下：struct node int s; node * next;下面的算法用于求線性表的長(zhǎng)度。請(qǐng)?jiān)诜娇蛑刑钊脒m當(dāng)?shù)膬?nèi)容，將算法補(bǔ)充完整。int GetLinkLen(node *h) int s;s=0; while(h) s=s+1; h=h->next ;return(s);2設(shè)有n個(gè)順序表元素存放在數(shù)組v1vn中，數(shù)組v的最大下標(biāo)為n0，元素類型為TElem. 下面的算法用于刪除順序表中第一個(gè)值為x的元素。請(qǐng)?jiān)诜娇蛑刑钊脒m當(dāng)內(nèi)容，將算法補(bǔ)充完整。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è)計(jì)題1.從順序表中刪除值為x的元素。答：假定順序表為a，有效元素個(gè)數(shù)為n，下標(biāo)從0開(kāi)始。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.將順序存儲(chǔ)結(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.將順序存儲(chǔ)的線性表（v1, v2, , vn）改變成（v1, v3, v5,）。答：void ChangeSequence(datatype * v) for(int i=3;i<=n;i+=2) vi-i/2=vi4.從順序表中刪除重復(fù)的元素，并使剩余元素間的相對(duì)次序保持不變。答：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ù)，建立一個(gè)長(zhǎng)度為n的、不含重復(fù)元素的順序表。答：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個(gè)整數(shù)，建立帶表頭結(jié)點(diǎn)的單向鏈表。答：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