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

2016《數(shù)據(jù)結(jié)構域算法》復習題PAGEPAGE15復習題集─參考答案一判斷題（√）1.在決定選取何種存儲結(jié)構時，一般不考慮各結(jié)點的值如何。（√）2.抽象數(shù)據(jù)類型與計算機內(nèi)部表示和實現(xiàn)無關。（×）3.線性表采用鏈式存儲結(jié)構時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。（×）4.鏈表的每個結(jié)點中都恰好包含一個指針。（×）5.鏈表的刪除算法很簡單，因為當刪除鏈中某個結(jié)點后，計算機會自動地將后續(xù)的各個單元向前移動。（×）6.線性表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一個復雜類型。（×）7.順序表結(jié)構適宜于進行順序存取，而鏈表適宜于進行隨機存取。（×）8.線性表在物理存儲空間中也一定是連續(xù)的。（×）9.順序存儲方式只能用于存儲線性結(jié)構。（√）10.棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種后進先出型結(jié)構。（√）11.對于不同的使用者，一個表結(jié)構既可以是棧，也可以是隊列，也可以是線性表。（√）12.棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種后進先出型結(jié)構。（√）13.兩個棧共享一片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出機會，應把兩個棧的棧底分別設在這片內(nèi)存空間的兩端。（×）14.二叉樹的度為2。（√）15.若二叉樹用二叉鏈表作存貯結(jié)構，則在n個結(jié)點的二叉樹鏈表中只有n—1個非空指針域。（×）16.二叉樹中每個結(jié)點的兩棵子樹的高度差等于1。（√）17.用二叉鏈表法存儲包含n個結(jié)點的二叉樹，結(jié)點的2n個指針區(qū)域中有n+1個為空指針。（√）18.具有12個結(jié)點的完全二叉樹有5個度為2的結(jié)點。（√）19.二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其孩子結(jié)點的前面。（×）20.在冒泡法排序中，關鍵值較小的元素總是向前移動，關鍵值較大的元素總是向后移動。（×）21.計算機處理的對象可以分為數(shù)據(jù)和非數(shù)據(jù)兩大類。[計算機處理的對象都是數(shù)據(jù)]（×）22.數(shù)據(jù)的邏輯結(jié)構與各數(shù)據(jù)元素在計算機中如何存儲有關。（×）23.算法必須用程序語言來書寫。（×）24.判斷某個算法是否容易閱讀是算法分析的任務之一。（×）25.順序表是一種有序的線性表。[任何數(shù)據(jù)結(jié)構才用順序存儲都叫順序表]（√）26.分配給順序表的內(nèi)存單元地址必須是連續(xù)的。（√）27.棧和隊列具有相同的邏輯特性。[它們的邏輯結(jié)構都是線性表]（√）28.樹形結(jié)構中每個結(jié)點至多有一個前驅(qū)。（×）29.在樹形結(jié)構中，處于同一層上的各結(jié)點之間都存在兄弟關系。（×）30.如果表示圖的鄰接矩陣是對稱矩陣，則該圖一定是無向圖。（×）31.如果表示圖的鄰接矩陣是對稱矩陣，則該圖一定是有向圖。（×）32.順序查找方法只能在順序存儲結(jié)構上進行。（×）33.折半查找可以在有序的雙向鏈表上進行。（√）34.滿二叉樹中不存在度為1的結(jié)點。（×）35.完全二叉樹中的每個結(jié)點或者沒有孩子或者有兩個孩子。（√）36.對n個元素執(zhí)行快速排序，在進行第一次分組時，排序碼的比較次數(shù)總是n-1次。（√）37.在有向圖中，各頂點的入度之和等于各頂點的出度之和。一、選擇題（A）1.在n個結(jié)點的順序表中，算法的時間復雜度是O(1)的操作是：A)訪問第i個結(jié)點（1≤i≤n）和求第i個結(jié)點的直接前驅(qū)（2≤i≤n）C)刪除第i個結(jié)點（1≤i≤n）B)在第i個結(jié)點后插入一個新結(jié)點（1≤i≤n）D)將n個結(jié)點從小到大排序（C）2.算法分析的目的是：A)找出數(shù)據(jù)結(jié)構的合理性B)研究算法中的輸入和輸出的關系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個元素的地址是:（A）110（B）108（C）100（D）120（D）下列選項中與數(shù)據(jù)存儲結(jié)構無關的術語是：A.順序表B.鏈表C.鏈隊列D.棧（A）7.鏈接存儲的存儲結(jié)構所占存儲空間：（A）分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關系的指針（B）只有一部分，存放結(jié)點值（C）只有一部分，存儲表示結(jié)點間關系的指針（D）分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)（B）8.帶頭結(jié)點的單鏈表head，鏈表為空的判定條件是(A)head==NULL(B)head->next==NULL(C)head->next==head(D)head!=NULL（B）9.一個棧的輸入序列為1，2，3，…，n，若輸出序列的第一個元素是n，輸出第i（1≤i≤n）個元素是。A)不確定B)n－i＋1C)iD)n（B）10.最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是（）。A)(rear＋1)%n==frontB)rear===frontC)rear＋1==frontD)(rear－l)%n==front（A）11.循環(huán)隊列A[0..m－1]存放其元素值，用front和rear分別表示隊頭和隊尾，則當前隊列中的元素數(shù)是:(A)(rear－front＋m)%m(B)rear－front＋1(C)rear－front－1(D)rear－front（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)3B)4C)5D)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é)點的完全二叉樹的深度為:(Ａ)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(1≤i<h)層上的結(jié)點都是度為2的結(jié)點C.第i(1≤i<h)層上有2i-1個結(jié)點D.不存在度為1的結(jié)點（B）18.深度為5的二叉樹至多有（）個結(jié)點。A)32B)31C)16（A）19.用鄰接表表示圖進行深度優(yōu)先遍歷時，通常采用()結(jié)構來時實現(xiàn)算法。A)棧B)隊列C)樹D)圖（D）20.對N個記錄作順序查找時，當查找成功時，平均查找長度是（）。A)N2B)N2/2C)ND)（N﹢1)/2（B）21.當一個有n個頂點的圖用鄰接矩陣A表示時，頂點Vi的度是（）。(A)B)C)D)+（C）22．某算法的時間復雜度為O(2n)，表明該算法的（）A.問題規(guī)模是2nB.執(zhí)行時間等于2nC.執(zhí)行時間近似與2n成正比D.問題的規(guī)模近似與2n成正比（D）23．“二叉樹為空”意味著二叉樹（）A.由一些沒有賦值的空結(jié)點構成B.根結(jié)點沒有子樹C.不存在D.沒有結(jié)點（D）24．數(shù)據(jù)結(jié)構的研究內(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ù)元素之間的關系D.數(shù)據(jù)的存儲方法（D）26．數(shù)據(jù)采用順序存儲，要求（）A.存儲的是屬于線性結(jié)構的數(shù)據(jù)B.根據(jù)結(jié)點值的大小，有序存放各結(jié)點C.按存儲單元地址由低到高的順序存放各結(jié)點D.各結(jié)點存放方法有規(guī)律，能隱含表示結(jié)點間的邏輯關系（D）27．一個順序表所占存儲空間大的大小與（）無關A.順序表長度B.結(jié)點類型C.結(jié)點中各字段的類型D.結(jié)點存放順序（A）28．數(shù)據(jù)采用鏈接存儲，要求（）A.每個結(jié)點占用一片連續(xù)的存儲區(qū)域B.所有結(jié)點占用一片連續(xù)的存儲區(qū)域C.結(jié)點的最后一個字段是指針型的字段C.每個結(jié)點有多少個后繼，就設多少個指針字段（A）29．算法的時間復雜度與（）有關A.問題規(guī)模B.計算機硬件性能C.編譯程序質(zhì)量D.程序設計語言（C）30．在程序中，為了設置一個空的順序表，必須（）A.給各數(shù)組元素賦空值B.給各順序表元素賦空值C.給表示順序表長度的變量賦初始值D.給數(shù)組變量名賦初始值（D）31．若變量H是某個帶表頭結(jié)點循環(huán)單向鏈表的表頭指針，則在該鏈表最后的一個結(jié)點的后繼指針域中存放的是（）A.H的地址B.H的值C.表頭結(jié)點的值D.首元結(jié)點的地址（A）32．棧和隊列的共同點在于（）A.邏輯特性B.存儲結(jié)構C.運算方法D.元素類型（C）33．棧和隊列的共同點在于（）A.都對存儲方法作了限制B.都是只能進行插入、刪除運算C.都對插入、刪除的位置作了限制D.都對插入、刪除兩中操作的先后順序作了限制（C）34．若5個元素的進棧序列是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)隊列中是否可以插入下一個元素，（）A.與隊首指針和隊尾指針的值有關B.只與隊尾指針的值有關，與隊首指針的值無關C.只與數(shù)組大小有關，與隊首指針和隊尾指針的值無關D.與曾經(jīng)進行過多少次插入操作有關（A）36．在順序隊列中，元素的排列順序（）A.由元素插入隊列的先后順序決定B.與元素值的大小有關C.與隊首指針和隊尾指針的取值有關D.與數(shù)組大小有關（C）37．在高度為h的完全二叉樹中，（）A.度為0的結(jié)點都在第h層上B.第i(1≤i<h)層上的結(jié)點都是度為2的結(jié)點C.第i(1≤i<h)層上有2i-1個結(jié)點D.不存在度為1的結(jié)點（B）38．一顆二叉樹如圖所示，其中序遍歷的序列為：ACEACEBFGDHB.DGBAECHFC.GDBEHFCAD.ABCDEFGH（A）39．采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的A．先序遍歷B．中序遍歷C．后序遍歷D．按層遍歷（D）40．采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的A．先序遍歷B．中序遍歷C．后序遍歷D．按層遍歷（D）41.已知關鍵字序列為(51，22，83，46，75，18，68，30)，對其進行快速排序，第一趟劃分完成后的關鍵字序列是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．數(shù)據(jù)結(jié)構包括數(shù)據(jù)的邏輯結(jié)構、數(shù)據(jù)的存儲結(jié)構和數(shù)據(jù)的運算這三個方面的內(nèi)容。2．下面程序段的時間復雜度是O(log3n)。i＝1；while（i<=n）i=i*3；3．在順序表中插入或刪除一個元素，需要平均移動表中一半元素，具體移動的元素個數(shù)與表長和該元素在表中的位置有關。4．當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表的元素是，應采用順序存儲結(jié)構。5．在n個結(jié)點的單鏈表中要刪除已知結(jié)點*p，需找到它的前驅(qū)結(jié)點的地址，其時間復雜度為O（n）。6．已知L是帶表頭結(jié)點的非空單鏈表，且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->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．設棧S的初始狀態(tài)為空，若元素a、b、c、d、e、f依次進棧，得到的出棧序列是b、d、c、f、e、a，則棧S的容量至少是3。9．用S表示入棧操作，X表示出棧操作，若元素入棧的順序為1234，為了得到1342出棧順序，相應的S和X的操作串為SXSSXSXX。10．數(shù)據(jù)的邏輯結(jié)構可以分為線性和非線性兩大類。11．數(shù)據(jù)的運算用算法表示。12．邏輯上相鄰的結(jié)點在存儲器中也相鄰，這是順序存儲結(jié)構的特點。13．在長度為n的順序表上實現(xiàn)定位操作，其算法的時間復雜度為O(n)。14．為了實現(xiàn)隨機訪問，線性結(jié)構應該采用順序存儲。15．在長度為n的順序表中插入一個元素，最多要移動n個元素。16．棧的存儲結(jié)構主要有順序和鏈式兩種。17．在編寫程序的時候，如果棧的最大長度難以預先估計，則最好使用鏈式棧。18．在樹形結(jié)構中，如果某結(jié)點沒有前驅(qū)（雙親），則稱該結(jié)點為根結(jié)點；如果某結(jié)點沒有后繼（孩子），則稱該結(jié)點為葉子。19．在樹形結(jié)構中，每個結(jié)點最多只有一個前驅(qū)（雙親）。20．由3個結(jié)點所構成的二叉樹有5種形態(tài)。21．二叉樹的前序遍歷按如下三個步驟進行：=1\*GB3①訪問根結(jié)點；=2\*GB3②前序遍歷左子樹；=3\*GB3③前序遍歷右子樹?！咀⒁猓?2\*GB3②=3\*GB3③中一定要加“前序”兩字！】22．二叉樹的中序遍歷按如下三個步驟進行：=1\*GB3①中序遍歷左子樹；=2\*GB3②訪問根結(jié)點；=3\*GB3③中序遍歷左子樹?！咀⒁猓?1\*GB3①=3\*GB3③中一定要加“中序”兩字！】23．在n個頂點的無向圖中，至少有0條邊，至多有n(n-1)/2條邊。24．在n個頂點的有向圖中，至少有0條邊，至多有n(n-1)條邊。25．如果排序不改變關鍵字相同的記錄之間的相對次序，則稱該排序方法是穩(wěn)定的。26．如果排序改變了關鍵字相同的記錄之間的相對次序，則稱該排序方法是不穩(wěn)定的。27．當待排關鍵字序列基本有序時，快速排序、簡單選擇排序和直接插入排序三種排序方法中，運行效率最高的是直接插入排序。28．在一個圖中，所有頂點的度數(shù)之和是所有邊數(shù)的2倍。29．無向圖中邊的數(shù)目等于鄰接矩陣中非零元素個數(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。三、簡答題1．對鏈表設置頭結(jié)點的作用是什么？（至少說出兩條好處）答：其好處有：（1）對帶頭結(jié)點的鏈表，在表的任何結(jié)點之前插入結(jié)點或刪除表中任何結(jié)點，所要做的都是修改前一個結(jié)點的指針域，因為任何元素結(jié)點都有前驅(qū)結(jié)點（若鏈表沒有頭結(jié)點，則首元素結(jié)點沒有前驅(qū)結(jié)點，在其前插入結(jié)點和刪除該結(jié)點時操作復雜些）。（2）對帶頭結(jié)點的鏈表，表頭指針是指向頭結(jié)點的非空指針，因此空表與非空表的處理是一樣的。2.寫出下列程序段的輸出結(jié)果（隊列中的元素類型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.簡述以下算法的功能（棧和隊列的元素類型均為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作為緩存空間，將隊列Q中的元素進行逆置（即相對于原順序進行倒排）。4.描述以下三個概念的區(qū)別：頭指針、頭結(jié)點、首元結(jié)點（第一個元素結(jié)點）。在單鏈表中設置頭結(jié)點的作用是什么？答：首元結(jié)點是指鏈表中存儲線性表中第一個數(shù)據(jù)元素a1的結(jié)點。為了操作方便，通常在鏈表的首元結(jié)點之前附設一個結(jié)點，稱為頭結(jié)點，該結(jié)點的數(shù)據(jù)域中不存儲線性表的數(shù)據(jù)元素，其作用是為了對鏈表進行操作時，可以對空表、非空表的情況以及對首元結(jié)點進行統(tǒng)一處理。頭指針是指向鏈表中第一個結(jié)點（或為頭結(jié)點或為首元結(jié)點）的指針。若鏈表中附設頭結(jié)點，則不管線性表是否為空表，頭指針均不為空。否則表示空表的鏈表的頭指針為空。這三個概念對單鏈表、雙向鏈表和循環(huán)鏈表均適用。是否設置頭結(jié)點，是不同的存儲結(jié)構表示同一邏輯結(jié)構的問題。頭結(jié)點headdatalink頭指針首元結(jié)點簡而言之，頭指針是指向鏈表中第一個結(jié)點（或為頭結(jié)點或為首元結(jié)點）的指針；頭結(jié)點是在鏈表的首元結(jié)點之前附設的一個結(jié)點；數(shù)據(jù)域內(nèi)只放空表標志和表長等信息（內(nèi)放頭指針？那還得另配一個頭指針?。。。┦自亟Y(jié)點是指鏈表中存儲線性表中第一個數(shù)據(jù)元素a1的結(jié)點。5.25738^L對以下單鏈表25738^LT=L;while(T->next!=NULL){T->data=2*T->data;T=T->next;}解：代碼功能：除最后一個結(jié)點之外，每個結(jié)點的數(shù)值部分改變?yōu)樵档?倍。L單鏈表結(jié)果示意圖如下：L14104^8614104^866.請畫出下圖的鄰接矩陣和鄰接表【本題較簡單，不提供答案】7．假設二叉樹采用順序存儲結(jié)構，如圖所示。（1）畫出二叉樹表示；（2）寫出先序遍歷、中序遍歷和后序遍歷的結(jié)果；（3）寫出結(jié)點值c的雙親結(jié)點，其左、右孩子；1234567891011121314151617181920eafdgcjhib8.樹和二叉樹之間有什么樣的區(qū)別與聯(lián)系？解：聯(lián)系：（1）二叉樹是樹的一種，是一種特殊的樹；（2）對樹適用的操作或規(guī)律都可應用到二叉樹上。區(qū)別：（1）二叉樹是一種特殊的樹，特殊在，第一是有序樹，第二結(jié)點的度數(shù)不超過2；（2）普通二叉樹有3個性質(zhì)，完全二叉樹有5個性質(zhì)，普通樹是沒有這些性質(zhì)的。9.一棵二叉樹中的結(jié)點的度或為0或為2，則二叉樹的枝數(shù)為2(n0-1)，其中n0是度為0的結(jié)點的個數(shù)。證明：設總結(jié)點數(shù)為n，度數(shù)為2的結(jié)點數(shù)為n2，依題意，該二叉樹沒有度數(shù)為1的結(jié)點。那么n=n0+n2假定分枝數(shù)為B，每個結(jié)點通過一個分枝跟其雙親相連，除根結(jié)點外；這意味著除根結(jié)點外，每個結(jié)點對應一個分枝，即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é)點的第i個孩子結(jié)點（若存在）的編號是多少？（4）編號為n的結(jié)點有右兄弟的條件是什么？如果有，其右兄弟的編號是多少？請給出計算和推導過程。11.如果用一個循環(huán)數(shù)組q[0..m-1]表示隊列時，該隊列只有一個隊列頭指針front，不設隊列尾指針rear，而改置計數(shù)器count用以記錄隊列中結(jié)點的個數(shù)。（1）編寫實現(xiàn)隊列的三個基本運算：判空、入隊、出隊（2）隊列中能容納元素的最多個數(shù)是多少？【此題超出教學范圍，不作解答。】ABCDEF12.已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF，中序遍歷結(jié)果為CBAEDFABCDEF解：根據(jù)已知的前序和中序遍歷結(jié)果，建立二叉樹如圖所示。此二叉樹的后序遍歷結(jié)果為：CBEFDA13．假設以二叉鏈表表示二叉樹，其類型定義如下：typedefstructnode{chardata;structnode*lchild,*rchild;∥左右孩子指針}*BinTree；閱讀下列程序。voidf13(BinTreeT){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)已知以T為根指針的二叉樹如圖所示，請寫出執(zhí)行f13(T)的輸出結(jié)果：(2)簡述算法f13的功能。14．設如下圖所示的二叉樹B的存儲結(jié)構為二叉鏈表，root為根指針，結(jié)點結(jié)構為：（lchild,data,rchild）。其中l(wèi)child，rchild分別為指向左右孩子的指針，data為字符型，root為根指針，試回答下列問題：（1）對下列二叉樹B，執(zhí)行下列算法traversal(root)，試指出其輸出結(jié)果；（2）假定二叉樹B共有n個結(jié)點，試分析算法traversal(root)的時間復雜度。二叉樹BAABDCFGEC的結(jié)點類型定義如下：C的結(jié)點類型定義如下：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）時間復雜度：15.已知有向圖的鄰接表如圖所示，請回答下面問題：(1)給出該圖的鄰接矩陣；(2)從結(jié)點A出發(fā)，寫出該圖的深度優(yōu)先遍歷序列。16.設要將序列{Q,H,C,Y,P,A,M,S,R,D,F,X}中的關鍵碼按字母序的升序重新排列。簡述快速排序的思路，并以第一個元素為軸中心，給出用快速排序?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．假設線性表用不帶頭結(jié)點的單向鏈表表示，結(jié)點數(shù)據(jù)類型如下：structnode{ints;node*next;}下面的算法用于求線性表的長度。請在方框中填入適當?shù)膬?nèi)容，將算法補充完整。intGetLinkLen(node*h){ints;s=0;while(h){s=s+1;h=h->next;}return(s);}2．設有n個順序表元素存放在數(shù)組v[1]~v[n]中，數(shù)組v的最大下標為n0，元素類型為TElem.下面的算法用于刪除順序表中第一個值為x的元素。請在方框中填入適當內(nèi)容，將算法補充完整。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--;}}五、算法設計題1.從順序表中刪除值為x的元素。答：假定順序表為a，有效元素個數(shù)為n，下標從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.將順序存儲結(jié)構線性表（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.將順序存儲的線性表（v1,v2,…,vn）改變成（v1,v3,v5,…）。答：voidChangeSequence(datatype*v){for(inti=3;i<=n;i+=2)v[i-i/2]=v[i]}4.從順序表中刪除重復的元素，并使剩余元素間的相對次序保持不變。答：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ù)，建立一個長度為n的、不含重復元素的順序表。答：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個整數(shù)，建立帶表頭結(jié)點的單向鏈表。答：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