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

2016《數(shù)據(jù)結(jié)構(gòu)域算法》復(fù)習(xí)題PAGEPAGE15復(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ī)存取。（×）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)的二叉樹鏈表中只有n—1個(gè)非空指針域。（×）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ǔ)言來書寫。（×）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)行。（×）33.折半查找可以在有序的雙向鏈表上進(jìn)行。（√）34.滿二叉樹中不存在度為1的結(jié)點(diǎn)。（×）35.完全二叉樹中的每個(gè)結(jié)點(diǎn)或者沒有孩子或者有兩個(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)訪問第i個(gè)結(jié)點(diǎn)（1≤i≤n）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（2≤i≤n）C)刪除第i個(gè)結(jié)點(diǎn)（1≤i≤n）B)在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1≤i≤n）D)將n個(gè)結(jié)點(diǎn)從小到大排序（C）2.算法分析的目的是：A)找出數(shù)據(jù)結(jié)構(gòu)的合理性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)解決問題的有限運(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個(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!=NULL（B）9.一個(gè)棧的輸入序列為1，2，3，…，n，若輸出序列的第一個(gè)元素是n，輸出第i（1≤i≤n）個(gè)元素是。A)不確定B)n－i＋1C)iD)n（B）10.最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則隊(duì)空的條件是（）。A)(rear＋1)%n==frontB)rear===frontC)rear＋1==frontD)(rear－l)%n==front（A）11.循環(huán)隊(duì)列A[0..m－1]存放其元素值，用front和rear分別表示隊(duì)頭和隊(duì)尾，則當(dāng)前隊(duì)列中的元素?cái)?shù)是:(A)(rear－front＋m)%m(B)rear－front＋1(C)rear－front－1(D)rear－front（B）12.若用一個(gè)大小為6的數(shù)值來實(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)3B)4C)5D)6[（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)的完全二叉樹的深度為:(Ａ)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(1≤i<h)層上的結(jié)點(diǎn)都是度為2的結(jié)點(diǎn)C.第i(1≤i<h)層上有2i-1個(gè)結(jié)點(diǎn)D.不存在度為1的結(jié)點(diǎn)（B）18.深度為5的二叉樹至多有（）個(gè)結(jié)點(diǎn)。A)32B)31C)16（A）19.用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常采用()結(jié)構(gòu)來時(shí)實(shí)現(xiàn)算法。A)棧B)隊(duì)列C)樹D)圖（D）20.對(duì)N個(gè)記錄作順序查找時(shí)，當(dāng)查找成功時(shí)，平均查找長(zhǎng)度是（）。A)N2B)N2/2C)ND)（N﹢1)/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.問題規(guī)模是2nB.執(zhí)行時(shí)間等于2nC.執(zhí)行時(shí)間近似與2n成正比D.問題的規(guī)模近似與2n成正比（D）23．“二叉樹為空”意味著二叉樹（）A.由一些沒有賦值的空結(jié)點(diǎn)構(gòu)成B.根結(jié)點(diǎn)沒有子樹C.不存在D.沒有結(jié)點(diǎn)（D）24．?dāng)?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．?dāng)?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ǔ)空間大的大小與（）無(wú)關(guān)A.順序表長(zhǎng)度B.結(jié)點(diǎn)類型C.結(jié)點(diǎn)中各字段的類型D.結(jié)點(diǎn)存放順序（A）28．?dāng)?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.問題規(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)單向鏈表的表頭指針，則在該鏈表最后的一個(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，5B.3，4，2，5，1C.4，2，1，3，5D.5，4，3，2，1（A）35．順序循環(huán)隊(duì)列中是否可以插入下一個(gè)元素，（）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ā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(1≤i<h)層上的結(jié)點(diǎn)都是度為2的結(jié)點(diǎn)C.第i(1≤i<h)層上有2i-1個(gè)結(jié)點(diǎn)D.不存在度為1的結(jié)點(diǎn)（B）38．一顆二叉樹如圖所示，其中序遍歷的序列為：ACEACEBFGDHB.DGBAECHFC.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,18,46,51,75,68,83)二、填空題1．?dāng)?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)的非空單鏈表，且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->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、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．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)可以分為線性和非線性兩大類。11．?dāng)?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ī)訪問，線性結(jié)構(gòu)應(yīng)該采用順序存儲(chǔ)。15．在長(zhǎng)度為n的順序表中插入一個(gè)元素，最多要移動(dòng)n個(gè)元素。16．棧的存儲(chǔ)結(jié)構(gòu)主要有順序和鏈?zhǔn)絻煞N。17．在編寫程序的時(shí)候，如果棧的最大長(zhǎng)度難以預(yù)先估計(jì)，則最好使用鏈?zhǔn)綏！?8．在樹形結(jié)構(gòu)中，如果某結(jié)點(diǎn)沒有前驅(qū)（雙親），則稱該結(jié)點(diǎn)為根結(jié)點(diǎn)；如果某結(jié)點(diǎn)沒有后繼（孩子），則稱該結(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)行：=1\*GB3①訪問根結(jié)點(diǎn)；=2\*GB3②前序遍歷左子樹；=3\*GB3③前序遍歷右子樹?！咀⒁猓?2\*GB3②=3\*GB3③中一定要加“前序”兩字！】22．二叉樹的中序遍歷按如下三個(gè)步驟進(jìn)行：=1\*GB3①中序遍歷左子樹；=2\*GB3②訪問根結(jié)點(diǎn)；=3\*GB3③中序遍歷左子樹?！咀⒁猓?1\*GB3①=3\*GB3③中一定要加“中序”兩字！】23．在n個(gè)頂點(diǎn)的無(wú)向圖中，至少有0條邊，至多有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，它將依次與表中元素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)的作用是什么？（至少說出兩條好處）答：其好處有：（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)（若鏈表沒有頭結(jié)點(diǎn)，則首元素結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，在其前插入結(jié)點(diǎn)和刪除該結(jié)點(diǎn)時(shí)操作復(fù)雜些）。（2）對(duì)帶頭結(jié)點(diǎn)的鏈表，表頭指針是指向頭結(jié)點(diǎn)的非空指針，因此空表與非空表的處理是一樣的。2.寫出下列程序段的輸出結(jié)果（隊(duì)列中的元素類型QElemType為char）。voidmain(){QueueQ;InitQueue(Q);Charx=’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)述以下算法的功能（棧和隊(duì)列的元素類型均為int）。voidalgo3(Queue&Q){StackS;intd;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)。為了操作方便，通常在鏈表的首元結(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)的問題。頭結(jié)點(diǎn)headdatalink頭指針首元結(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ù)據(jù)域內(nèi)只放空表標(biāo)志和表長(zhǎng)等信息（內(nèi)放頭指針？那還得另配一個(gè)頭指針?。。。┦自亟Y(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。5.25738^L對(duì)以下單鏈表25738^LT=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é)果示意圖如下：L14104^8614104^866.請(qǐng)畫出下圖的鄰接矩陣和鄰接表【本題較簡(jiǎn)單，不提供答案】7．假設(shè)二叉樹采用順序存儲(chǔ)結(jié)構(gòu)，如圖所示。（1）畫出二叉樹表示；（2）寫出先序遍歷、中序遍歷和后序遍歷的結(jié)果；（3）寫出結(jié)點(diǎn)值c的雙親結(jié)點(diǎn)，其左、右孩子；1234567891011121314151617181920eafdgcjhib8.樹和二叉樹之間有什么樣的區(qū)別與聯(lián)系？解：聯(lián)系：（1）二叉樹是樹的一種，是一種特殊的樹；（2）對(duì)樹適用的操作或規(guī)律都可應(yīng)用到二叉樹上。區(qū)別：（1）二叉樹是一種特殊的樹，特殊在，第一是有序樹，第二結(jié)點(diǎn)的度數(shù)不超過2；（2）普通二叉樹有3個(gè)性質(zhì)，完全二叉樹有5個(gè)性質(zhì)，普通樹是沒有這些性質(zhì)的。9.一棵二叉樹中的結(jié)點(diǎn)的度或?yàn)?或?yàn)?，則二叉樹的枝數(shù)為2(n0-1)，其中n0是度為0的結(jié)點(diǎn)的個(gè)數(shù)。證明：設(shè)總結(jié)點(diǎn)數(shù)為n，度數(shù)為2的結(jié)點(diǎn)數(shù)為n2，依題意，該二叉樹沒有度數(shù)為1的結(jié)點(diǎn)。那么n=n0+n2假定分枝數(shù)為B，每個(gè)結(jié)點(diǎn)通過一個(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開始對(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)的第i個(gè)孩子結(jié)點(diǎn)（若存在）的編號(hào)是多少？（4）編號(hào)為n的結(jié)點(diǎn)有右兄弟的條件是什么？如果有，其右兄弟的編號(hào)是多少？請(qǐng)給出計(jì)算和推導(dǎo)過程。11.如果用一個(gè)循環(huán)數(shù)組q[0..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é)果為CBAEDFABCDEF解：根據(jù)已知的前序和中序遍歷結(jié)果，建立二叉樹如圖所示。此二叉樹的后序遍歷結(jié)果為：CBEFDA13．假設(shè)以二叉鏈表表示二叉樹，其類型定義如下：typedefstructnode{chardata;structnode*lchild,*rchild;∥左右孩子指針}*BinTree；閱讀下列程序。voidf13(BinTreeT){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;}}}回答下列問題：(1)已知以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為根指針，試回答下列問題：（1）對(duì)下列二叉樹B，執(zhí)行下列算法traversal(root)，試指出其輸出結(jié)果；（2）假定二叉樹B共有n個(gè)結(jié)點(diǎn)，試分析算法traversal(root)的時(shí)間復(fù)雜度。二叉樹BAABDCFGEC的結(jié)點(diǎn)類型定義如下：C的結(jié)點(diǎn)類型定義如下：structnode{chardata;structnode*lchild,rchild;};C算法如下：voidtraversal(structnode*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)回答下面問題：(1)給出該圖的鄰接矩陣；(2)從結(jié)點(diǎn)A出發(fā)，寫出該圖的深度優(yōu)先遍歷序列。16.設(shè)要將序列{Q,H,C,Y,P,A,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è)線性表用不帶頭結(jié)點(diǎn)的單向鏈表表示，結(jié)點(diǎn)數(shù)據(jù)類型如下：structnode{ints;node*next;}下面的算法用于求線性表的長(zhǎng)度。請(qǐng)?jiān)诜娇蛑刑钊脒m當(dāng)?shù)膬?nèi)容，將算法補(bǔ)充完整。intGetLinkLen(node*h){ints;s=0;while(h){s=s+1;h=h->next;}return(s);}2．設(shè)有n個(gè)順序表元素存放在數(shù)組v[1]~v[n]中，數(shù)組v的最大下標(biāo)為n0，元素類型為TElem.下面的算法用于刪除順序表中第一個(gè)值為x的元素。請(qǐng)?jiān)诜娇蛑刑钊脒m當(dāng)內(nèi)容，將算法補(bǔ)充完整。voidDeleValue(TElemx){inti,j;i=1;While(v[i]!=x&&i<=n)i=i+1;if(i<=n){for(j=n;j>i;j--)v[j-1]=v[j];n--;}}五、算法設(shè)計(jì)題1.從順序表中刪除值為x的元素。答：假定順序表為a，有效元素個(gè)數(shù)為n，下標(biāo)從0開始。intDeleteReapeatValue(datatype*a,int*pNum,datatypex){inti,k,n;n=*pNum;k=0;for(i=0;i<n;i++){If(a[i]==x)k++;Elsea[i-k]=a[i];}*pNum=n-1;returnk;}2.將順序存儲(chǔ)結(jié)構(gòu)線性表（v1,v2,…,vn）改變成（vk+1,vk+2,…,vn,v1,v2,…,vk）。答：voidChangeSequence(datatype*v){datatypea[SIZE];for(inti=1;i<n;i++)a[i]=v[i];for(i=1;i<=n;i++)v[(k+i)%n]=a[i];}3.將順序存儲(chǔ)的線性表（v1,v2,…,vn）改變成（v1,v3,v5,…）。答：voidChangeSequence(datatype*v){for(inti=3;i<=n;i+=2)v[i-i/2]=v[i]}4.從順序表中刪除重復(fù)的元素，并使剩余元素間的相對(duì)次序保持不變。答：intDeleteAllReapeatValue(datatype*a,int*pNum){intn=*pNum;inti,j;for(i=0;i<n;i++)for(j=i+1;j<n;j++)if(a[i]!=INFINITY&&a[i]==a[j])a[j]=INFINITY;returnDeleteReapeatValue(a,pNum,INFINITY);}5.從鍵盤輸入一系列整數(shù)，建立一個(gè)長(zhǎng)度為n的、不含重復(fù)元素的順序表。答：intCreateSequence(){inta[SIZE];inti=0,j,k;while(i<n){scanf(“%d”,&k);for(j=0;j<=i;j++)if(a[j]==k)break;if(j>i)a[++i]=k;}}6.從鍵盤輸入n個(gè)整數(shù)，建立帶表頭結(jié)點(diǎn)的單向鏈表。答：LinkListCreateList(){inti=0,j,k;LinkListhead=(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=si++;}}ret