PAGEPAGE57第一章緒論一、填空題1.算法的計算量的大小稱為計算的（B）。A．效率B.復雜性C.現實實性D.難度2.算法的時時間復雜度取取決于（CC）A．問題的規模模B.待待處理數據的的初態C..A和B3.計算機算法法指的是（CC），它必須須具備（B）這三個特性性。(1)A．計計算方法B..排序方法法CC.解決問問題的步驟序序列D.調度方法(2)A．可可執行性、可可移植性、可可擴充性B.可執行性、確確定性、有窮窮性C.確定性、有有窮性、穩定定性D.易易讀性、穩定定性、安全性性4．從邏輯上可可以把數據結結構分為（C）兩兩大類。A．動態結構、靜靜態結構B．順序結結構、鏈式結結構C．線性結構、非非線性結構DD．初等結構構、構造型結結構5．以下與數據據的存儲結構構無關的術語語是（D）。A．循環隊列B.鏈鏈表CC.哈希表表D.棧棧6．以下數據結結構中，哪一一個不是線性性結構（B）？？A．廣義表B.二叉樹CC.稀疏矩矩陣D.串串7．以下那一個個術語與數據據的存儲結構構無關？（A）A．棧BB.哈希表表C.線線索樹D..雙向鏈鏈表8．在下面的程程序段中，對對x的賦值語語句的頻度為為（C）FORi:==1TOOnDOFORRj:=11TOnDDOxx:=x+11;A．O(2nn)B．．O(n)C．O((n2)D．O(llog2n)9．程序段FFORii:=n-11DOWWNTO1DOOFORjj:=1TTOiDDOIFFA[j]>A[j+1]THENNA[j]與A[j+1]對換；其中n為正整整數，則最后后一行的語句句頻度在最壞壞情況下是（D）A.O（n）B..O(nllogn)CC.O(nn3)D.OO(n2)10．以下哪個個數據結構不不是多型數據據類型（D）A．棧BB．廣義表C．有向向圖D．．字符串11．以下數據據結構中，（A）是是非線性數據據結構A．樹BB．字符串C．隊D．棧12.下列數數據中，（C）是非線性數據結構。A．棧B..隊列C..完全二二叉樹D.堆堆13．連續存儲儲設計時，存存儲單元的地地址（AA）。A．一定連續B．一定定不連續C．不一定定連續DD．部分連續續，部分不連連續14．以下屬于于邏輯結構的的是（CC）。A．順序表B.哈希希表CC.有序表DD.單鏈鏈表二、判斷題1.數據元素素是數據的最最小單位。((F)2.記錄是數數據處理的最最小單位。(T)3.數據的邏邏輯結構是指指數據的各數數據項之間的的邏輯關系；；(F)4．算法的優劣劣與算法描述述語言無關，但但與所用計算算機有關。((F)5．健壯的算法法不會因非法法的輸入數據據而出現莫名名其妙的狀態態。(T)6．算法可以用用不同的語言言描述，如果果用C語言言或PASCCAL語言等等高級語言來來描述，則算算法實際上就就是程序了。(T)7．程序一定是是算法。(T))8．數據的物理理結構是指數數據在計算機機內的實際存存儲形式。((T))9.數據結構構的抽象操作作的定義與具具體實現有關關。(F)10.在順序序存儲結構中中，有時也存存儲數據結構構中元素之間間的關系。((F)11.順序存存儲方式的優優點是存儲密密度大，且插插入、刪除運運算效率高。((F)12.數據結結構的基本操操作的設置的的最重要的準準則是，實現現應用程序與與存儲結構的的獨立。(T))13.數據的的邏輯結構說說明數據元素素之間的順序序關系,它依依賴于計算機機的儲存結構構.(FF)三、填空1．數據的物理理結構包括數據元素素的表示示和數數據關系的的表示。2.對于給定定的n個元素素,可以構造造出的邏輯結結構有集集合，線性，樹，__圖（網網）_四種。3．數據的邏輯輯結構是指數據元素素之間的邏輯輯關系。4．一個數據結結構在計算機機中表示稱為存存儲結構。5．抽象數據類類型的定義僅僅取決于它的的一組__邏邏輯特性_，而而與_其在計計算機內部如如何表示和實實現_無關，即即不論其內部部結構如何變變化，只要它它的_數學特特性_不變，都都不影響其外外部使用。6．數據結構中中評價算法的的兩個重要指指標是時間復復雜度和空間間復雜度7.數據結構構是研討數據據的_邏輯結結構_和_物理結結構_，以及及它們之間的的相互關系，并并對與這種結結構定義相應應的_操作_，設計計出相應的算算法_。8．一個算法法具有5個特特性:有窮窮性、確定性、可行性，有零個或或多個輸入、有有一個或多個個輸出。9．已知如下程程序段for(i=nn;i>=11;i--){語句句1}{x=x+1；{語句2}for(j=nn;j>i;;j--){語句句3}y=y+1;;{{語句4}}；語句1執行的頻頻度為n++1；語句句2執行的頻頻度為n；語句3執執行的頻度為為n（n+11）/2；語句句4執行的頻頻度為(nn-1)n//2。10．在下面的的程序段中，對對ｘ的賦值語語句的頻度為為(n3+3n2+2n)//6______（表示為為n的函數）for((i=1;ii<=n;ii++)for(jj=1;j<<=i;j+++)foor(k=11;k<=jj;k++))ｘ：＝ｘ＋deelta；11.下面程序序段中帶下劃劃線的語句的的執行次數的的數量級是：：log2ni=1;whiile(i<<n)i=ii*2;12.下面程程序段中帶下下劃線的語句句的執行次數數的數量級是是(nloog2n))。i=1;while(ii<n){ffor(j==1;j<==n;j+++)x=x++1;i=ii*2}13.下面程程序段中帶有有下劃線的語語句的執行次次數的數量級級是(logg2n)i=n*nwhilee(i!=11)i=i//2;14.計算機機執行下面的的語句時，語語句s的執行行次數為___(n+33)(n-22)/2______。for(ii=l；i<<n-l；ii++)forr(j=n;;j>=i;;j--)s;15.下面程程序段的時間間復雜度為___n1/22_______。(n>>1)sum==1；for(i=0;;sum<nn;i++))sum++=i;四、應用題1、有如下幾種種用二元組表表示的數據結結構，畫出它它們分別對應應的邏輯圖表表示形式，并并指出它們分分別屬于何種種結構。（注注意：<>表表示有方向，（）表表示無方向）（1）、A=（KK，R），其中：K=={a,b,,c,d,ee,,f,gg,h}RR={r}r={<a,,b>,<bb,c>,<<c,d>,,<d,e>>,<e,ff>,<f,,g>,<gg.h>}（2）、B=（KK，R），其其中：K={{a,b,cc,d,e,,f,g,hh}R=={r}rr={<d,,b>，<dd,g>,<<d,a>,,<b,c>>,<g,ee>,<g,,h>,<ee.f>}（3）、C=((K,R),,其中:K=={1,2,,3,4,55,6},RR={r}r=={(1,22),(2,,3),(22,4),((3,4),,(3,5)),(3,66),(4,,5),(44,6)}線性表、棧和隊隊列測試題姓名班級學號選擇題（共255分）（B）1、下面關于于線性表的敘敘述中，錯誤誤的是哪一個個？A．線性表采用用順序存儲，必必須占用一片片連續的存儲儲單元。B．線性表采用用順序存儲，便便于進行插入入和刪除操作作。C．線性表采用用鏈接存儲，不不必占用一片片連續的存儲儲單元。D．線性表采用用鏈接存儲，便便于插入和刪刪除操作。（A）2、若某線性表表最常用的操操作是存取任任一指定序號號的元素和在在最后進行插插入和刪除運運算，則利用用（

）存儲方式式最節省時間間。A．順序表

B．雙雙鏈表

C．帶頭結點點的雙循環鏈鏈表

DD．單循環鏈鏈表（C）3、若長度為為n的線性表采采用順序存儲儲結構，在其其第i個位置插入入一個新元素素的算法的時時間復雜度為為（

）(1<=ii<=n+11)。A.O(0))

B.OO(1)

C.O(n)

DD.O(nn2)（B）4、在單鏈表表指針為p的結點之后后插入指針為為s的結點，正正確的操作是是：A．p->neext=s;;s->neext=p-->nextt;

B．．s->nnext=pp->nexxt;p->>next==s;C．p->neext=s;;p->neext=s-->nextt;

D．．p->nnext=ss->nexxt;p->>next==s;（B）5、對于一個個頭指針為hhead的帶帶頭結點的單單鏈表，判定定該表為空表表的條件是（

）head==NNULL

BB．head-->nextt==NULLL

C．head-->nextt==heaad

DD．head-->NULLL（B）6.棧中中元素的進出出原則是A．先進進先出B.后進先出出C棧空則進進D棧滿則出出（C）7.若已已知一個棧的的入棧序列是是1，2，3，…，n，其輸出序序列為p1，p2，p3，…，pn，若p1=nn，則pi為Ａ．iＢ．．n=iＣＣ．n-i++1Ｄ．．不確定（B）8.判定定一個棧STT（最多元素素為m0）為空的的條件是Ａ．STT->topp<>0Ｂ．ST->>top=00Ｃ．．ST->ttop<>mm0Ｄ．ST->>top=mm0（A）9.判定定一個隊列QQU（最多元元素為m0）為滿隊隊列的條件是是Ａ．QU->>rear－QU->>frontt==m0ＢＢ．QU->>rear－QU->>frontt－1==m0Ｃ．QUU->froont==QU-->rearrＤ．QU->>frontt==QU->rrear+11（D）10．數組ＱＱ［ｎ］用來來表示一個循循環隊列，ｆｆ為當前隊列列頭元素的前前一位置，ｒｒ為隊尾元素素的位置，假假定隊列中元元素的個數小小于ｎ，計算算隊列中元素素的公式為（Ａ）r－f;;（Ｂ）（n＋f－r）%n;（Ｃ）n＋r－f;（Ｄ）（n＋r－f）%n11.設有有4個數據元素素a1、a2、a3和a4，對他們們分別進行棧棧操作或隊操操作。在進棧棧或進隊操作作時，按a11、a2、a3、a4次序每次次進入一個元元素。假設棧棧或隊的初始始狀態都是空空。現要進行的棧操操作是進棧兩兩次，出棧一一次，再進棧棧兩次，出棧棧一次；這時時，第一次出出棧得到的元元素是②，第二次出出棧得到的元元素是④；類似似地，考慮對對這四個數據據元素進行的的隊操作是進進隊兩次，出出隊一次，再再進隊兩次，出出隊一次；這這時，第一次次出隊得到的的元素是①，第二二次出隊得到到的元素是②。經操操作后，最后后在棧中或隊隊中的元素還還有②個。供選擇的答案：：A～D：①a1②a2③a3④a4E：①1②2③3④0答：A、B、CC、D、E分別為、、、、12.棧是是一種線性表表，它的特點點是A。設用用一維數組AA[1,…,,n]來表示示一個棧，AA[n]為棧棧底，用整型型變量T指示當前棧棧頂位置，AA[T]為棧棧頂元素。往往棧中推入（PUSH）一個新元素時，變量T的值B；從棧中彈出（POP）一個元素時，變量T的值C。設棧空時，有輸入序列a，b，c，經過PUSH，POP，PUSH，PUSH，POP操作后，從棧中彈出的元素的序列是D，變量T的值是E。供選擇的答案：：A：①先進先出②后進先出 ③進優于出 ④出優于進⑤隨機進出B，C： ①加1②減1③③不變④清0⑤加2⑥⑥減2D：①①a,b②b,c ③c,a ④b,a⑤c,b⑥a,cE：①①n+1②n+2③n ④n-1⑤n-2答：A、B、CC、D、E分別為②、②、①、⑥、④13.在做做進棧運算時時，應先判別別棧是否A；；在做退棧運運算時，應先先判別棧是否否B。當棧中中元素為n個，做進棧棧運算時發生生上溢，則說說明該棧的最最大容量為C。為了增加內存空空間的利用率率和減少溢出出的可能性，由由兩個棧共享享一片連續的的內存空間時時，應將兩棧棧的D分別設設在這片內存存空間的兩端端，這樣，只只有當EE時，才才產生上溢。供選擇的答案：：A，B：①空②滿③上溢④下溢C： ①①n-1②②n③n+1④n/2D：①長度②深度③棧頂④棧底E：①兩個棧的的棧頂同時到到達棧空間的的中心點②其中一一個棧的棧頂頂到達棧空間間的中心點③兩個棧的棧棧頂在棧空間間的某一位置置相遇④兩個棧均不空空，且一個棧棧的棧頂到達達另一個棧的的棧底答：A、B、CC、D、E分別為②、①、②、④、③判斷題（共100分）（F）1..線性表的的每個結點只只能是一個簡簡單類型，而而鏈表的每個個結點可以是是一個復雜類類型。（F）2..在表結構構中最常用的的是線性表，棧棧和隊列不太太常用。（T）3..棧是一種種對所有插入入、刪除操作作限于在表的的一端進行的的線性表，是是一種后進先先出型結構。（T）4..對于不同同的使用者，一一個表結構既既可以是棧，也也可以是隊列列，也可以是是線性表。（F）5..棧和鏈表表是兩種不同同的數據結構構。（F）6..棧和隊列列是一種非線線性數據結構構。（T）7..棧和隊列列的存儲方式式既可是順序序方式，也可可是鏈接方式式。（T）8..兩個棧共共享一片連續續內存空間時時，為提高內內存利用率，減減少溢出機會會，應把兩個個棧的棧底分分別設在這片片內存空間的的兩端。（F）9..隊是一種種插入與刪除除操作分別在在表的兩端進進行的線性表表，是一種先先進后出型結結構。（F）100.一個棧棧的輸入序列列是123445，則棧的的輸出序列不不可能是122345。填空題（共200分）1.線性表表、棧和隊列列都是線性結構，可可以在線性表表的任意位置插插入和刪除元元素；對于棧棧只能在棧頂插入和和刪除元素；；對于隊列只只能在隊尾插入和和隊頭刪除元素。2.棧是一種種特殊的線性性表，允許插插入和刪除運運算的一端稱稱為棧頂。不允允許插入和刪刪除運算的一一端稱為棧底。3.隊列列是被限定為為只能在表的的一端進行插插入運算，在在表的另一端端進行刪除運運算的線性表表。4.在一個循循環隊列中，隊隊首指針指向向隊首元素的的當前前位置。5.在具有nn個單元的循循環隊列中，隊隊滿時共有nn-1個元元素。6.向棧中壓壓入元素的操操作是先插入入數據，后移動指指針。7.從循環隊隊列中刪除一一個元素時，其其操作是先讀取元素素，后后移動指針針。8.帶表頭頭結點的空循循環雙向鏈表表的長度等于于0。9．表達式233+((122*3-2))/4+344*5/7))+108//9的后綴表表達式是__231223*2-4/345**7/++1089/+______10．已知L是是無表頭結點點的單鏈表，且且P結點既不是是首元素結點點，也不是尾尾元素結點。按按要求從下列列語句中選擇擇合適的語句句序列。a.在P結點點后插入S結點的語句句序列是：

(4)(1)

。b.在P結點點前插入S結點的語句句序列是：

7

118441

。c.在表首插插入S結點的語句句序列是：

512

。d.在表尾插插入S結點的語句句序列是：

9166

。供選擇的語句有有：（1）P->nnext=SS;（2）P->neext=PP->nexxt->neext;（3）P->neext=SS->nexxt;（4）S->nnext=P->neext;（5）S->neext=LL;（6）S->neext=NNULL;（7）Q=P;;（8）whille(P->>next!!=Q)PP=P->nnext;（9）whilee(P->nnext!==NULL))P=P-->nextt;（10）P=Q;（11）P=L;;（12）L=S;;（13）L=P;;簡答題(共155分)說明線性表、棧棧與隊的異同同點。順序隊的“假溢溢出”是怎樣產生生的？如何知知道循環隊列列是空還是滿滿？設循環隊列的容容量為40（序號從從0到39），現經經過一系列的的入隊和出隊隊運算后，有有①frontt=11，rear==19;②fronnt=19，rear==11；問在在這兩種情況況下，循環隊隊列中各有元元素多少個？？算法設計（共330分）寫一算法，從順順序表中刪除除自第i個元素開始始的k個元素。StatusDelette_k(SSqlisttL,innti,iintk)){if(ii<0||ii>L.leength|||i+k>>L.lenngth)rreturnnerroor;for((intjj=i+k;;j<L.llengthh;j++)){L.eleem[j-kk]=L.eelem[jj];}L.leength--=k;rreturnnOK;}試寫一個算法，判判別讀入的一一個以‘@’’為結束符的的字符序列是是否是“回文”。（正讀和反讀讀都相同的字字符序列為“回文”，例如，‘aabba’和和‘abcbba’是回文文，‘abccde’和和‘ababbab’則不不是回文。）StattusHuuiWen((chars[]){ inti==0; SqStacckS; InitSttack(SS); while((s[i]!!='@')) { Push((S,s[ii]); cout<<<"pussh"<<ss[i]; i++; } i=0; while((s[i]!!='@')) { chare; Pop(SS,e); cout<<<e<<""*"<<ss[i]; if(e!!=s[i]])breaak; i++; } if(s[ii]=='@@')retturn11;//返返回結果1表表示是回文，00表示不是回回文 elserreturnn0;}假設有一個循環環鏈表的長度度大于1，且表中既既無頭結點也也無頭指針。已已知s為指向鏈表表某個結點的的指針，試編編寫算法在鏈鏈表中刪除指指針s所指結點的的前趨結點。StatusDelette(LinnkListts){p=s;while(pp->nexxt->neext!=ss)///查找s的前前一個結點的的前一個結點點；p=p-->nextt;q=p->neext;p->nextt=s;deleteq;returnOK;}第6章樹和和圖自測卷卷姓名班級學號題號一二三四五總分題分1017174016100得分一、下面是有關關二叉樹的敘敘述，請判斷斷正誤（每小小題1分，共共10分）（）1..若二叉樹用用二叉鏈表作作存貯結構，則則在n個結點點的二叉樹鏈鏈表中只有nn—1個非空指針針域。（）2..二叉樹中每每個結點的兩兩棵子樹的高高度差等于11。（）3..二叉樹中每每個結點的兩兩棵子樹是有有序的。（）4..二叉樹中每每個結點有兩兩棵非空子樹樹或有兩棵空空子樹。（）5..二叉樹樹中所有結點點個數是2kk-1-1，其其中k是樹的的深度。（）6..對于一一棵非空二叉叉樹，它的根根結點作為第第一層，則它它的第i層上上最多能有22i－1個結點點。（）7..具有122個結點的完完全二叉樹有有5個度為22的結點。（）8..不同的求求最小生成樹樹的方法最后后得到的生成成樹是相同的的.（）9..有n個頂頂點的無向圖圖,采用鄰鄰接矩陣表示示,圖中的的邊數等于鄰鄰接矩陣中非非零元素之和和的一半。（）100.無向圖圖的鄰接矩陣陣一定是對稱稱矩陣，有向向圖的鄰接矩矩陣一定是非非對稱矩陣。二、填空（每空空1分，共117分）1．由３個結結點所構成的的二叉樹有種形態。2.一棵深深度為6的滿滿二叉樹有個分分支結點和個葉子。3．一棵具有有257個結結點的完全二二叉樹，它的的深度為。4．設一棵完完全二叉樹有有700個結結點，則共有有個葉子結點點。5.用5個權權值{3,2,,4,55,1}構造的哈夫夫曼（Hufffman）樹樹的帶權路徑徑長度是。6.判斷一個個無向圖是一一棵樹的條件件是_______。7.在有nn個頂點的有有向圖中，若若要使任意兩兩點間可以互互相到達，則則至少需要________條弧。8.G是一個個非連通無向向圖，共有228條邊，則則該圖至少有有_______個頂點9.N個頂點點的連通圖用用鄰接矩陣表表示時,該矩矩陣至少有_________個非零元元素。10．在有n個個頂點的有向向圖中，每個個頂點的度最最大可達_______。11．設有一稀稀疏圖G，則則G采用存儲較省省空間。12．設有一稠稠密圖G，則則G采用存儲較省空空間。13．n個頂點點e條邊的圖圖采用鄰接矩矩陣存儲，深深度優先遍歷歷算法的時間間復雜度為；若采采用鄰接表存存儲時，該算算法的時間復復雜度為。14．已知圖圖的鄰接矩陣陣，根據算法法思想，則從從頂點0出發發按深度優先先遍歷的結點點序列是。則從頂頂點0出發按按廣度優先遍遍歷的結點序序列是。三、選擇題（每每小題1分，共共17分）（）11．不含任任何結點的空空樹。（Ａ）是一棵樹樹;（Ｂ）是一一棵二叉樹;;（Ｃ）是一棵樹樹也是一棵二二叉樹;（Ｄ）既既不是樹也不不是二叉樹（）22．二叉樹是是非線性數據據結構，所以以。（Ａ）它不能用用順序存儲結結構存儲;（Ｂ）它它不能用鏈式式存儲結構存存儲;（Ｃ）順序存儲儲結構和鏈式式存儲結構都都能存儲;（Ｄ）順順序存儲結構構和鏈式存儲儲結構都不能能使用（）33.具有有n(n>00)個結點的的完全二叉樹樹的深度為。(Ａ)logg2(n)(Ｂ)logg2(n)(Ｃ)logg2(n)+11(Ｄ)log2(n)+11（）44．把一棵樹樹轉換為二叉叉樹后，這棵棵二叉樹的形形態是。（Ａ）唯一的（Ｂ）有多多種（Ｃ）有多種，但但根結點都沒沒有左孩子（ＤＤ）有多種，但但根結點都沒沒有右孩子（）55.在一個個圖中，所有有頂點的度數數之和等于圖圖的邊數的倍。A．1//2B..1C.2DD.4（）77.在一個個有向圖中，所所有頂點的入入度之和等于于所有頂點的的出度之和的的倍。A．1//2B..1C.2DD.4（）88.用鄰接接表表示圖進進行廣度優先先遍歷時，通通常是采用來實實現算法的。A．棧B..隊列C..樹D..圖（）99.深度優優先遍歷類似似于二叉樹的的A．先序遍歷B.中序序遍歷C.后序遍歷歷DD.層次次遍歷（）110.廣度度優先遍歷類類似于二叉樹樹的A．先序遍歷B.中序序遍歷C.后序遍歷歷DD.層次次遍歷11.樹是是結點的有限限集合，它A根結點，記記為T。其余余的結點分成成為m（m≥≥0）個BB的集合T1，TT2，…，Tm，每每個集合又都都是樹，此時時結點T稱為為Ti的父結點，TTi稱為T的子子結點（1≤≤i≤m）。一個個結點的子結結點個數為該該結點的C。供選擇的答案A：①有00個或1個②有0個或多多個③有且只有11個④有1個或11個以上B:①互互不相交 ②允許相交交③③允許葉結結點相交④允許樹枝枝結點相交C：①權 ②維數③次數④序答案：A=BB=C=12.二叉樹樹A。在完全全的二叉樹中中，若一個結結點沒有B，則則它必定是葉葉結點。每棵棵樹都能惟一一地轉換成與與它對應的二二叉樹。由樹樹轉換成的二二叉樹里，一一個結點N的的左子女是NN在原樹里對對應結點的C，而N的右右子女是它在在原樹里對應應結點的D。供選擇的答案A：①是特殊殊的樹②不是樹的特特殊形式③是兩棵樹的的總稱④有是只有二二個根結點的的樹形結構B:①左左子結點②右子結點點③左子結點點或者沒有右右子結點④兄弟C～D：①最最左子結點②最右子結結點③最鄰近的的右兄弟④最鄰近的的左兄弟⑤最左的兄兄弟⑥最右的兄兄弟答案：A=BB=C=D＝四、閱讀分析題題（每題5分分，共40分分）1.給定二叉叉樹的兩種遍遍歷序列，分分別是：前序遍歷序列：：D，A，CC，E，B，HH，F，G，II；中序序遍歷序列：：D，C，BB，E，H，AA，G，I，FF，圖1試畫該出二叉樹樹圖1圖2圖2圖3圖12．試寫出如圖圖1所示的二二叉樹分別按按先序、中序序、后序遍歷歷時得到的結結點序列。3.把如圖圖2所示的樹樹轉化成二叉叉樹。4.畫出圖3二二叉樹相應的的森林。5．.已知如圖圖所示的有向向圖，請給出出該圖的:頂點1234頂點123456入度321122出度022313鄰接矩陣；鄰接表；逆鄰接表。6．請對下圖的的無向帶權圖圖：寫出它的鄰接矩矩陣，并按普普里姆算法求求其最小生成成樹；寫出它的鄰接表表，并按克魯魯斯卡爾算法法求其最小生生成樹。7．已知二維數數組表示的圖圖的鄰接矩陣陣如下圖所示示。試分別畫畫出自頂點11出發進行遍遍歷所得的深深度優先生成成樹和廣度優優先生成樹。8．給定下列網網G:（110分）1試著找出網網G的最小生生成樹，畫出出其邏輯結構構圖；2用兩種不同同的表示法畫畫出網G的存存儲結構圖；；3用C語言（或或其他算法語語言）定義其其中一種表示示法（存儲結結構）的數據據類型。五、算法設計題題（前1~55題中任選22題，第6~~7題中任選選1題，共116分）1.編寫遞歸算算法，計算二二叉樹中葉子子結點的數目目。2.寫出求二二叉樹深度的的算法，先定定義二叉樹的的抽象數據類類型。3．編寫遞歸算算法，求二叉叉樹中以元素素值為x的結結點為根的子子樹的深度。4.編寫按層次次順序（同一一層自左至右右）遍歷二叉叉樹的算法。5.編寫算法判判別給定二叉叉樹是否為完完全二叉樹。6．編寫算法，由由依次輸入的的頂點數目、弧弧的數目、各各頂點的信息息和各條弧的的信息建立有有向圖的鄰接接表。解：StatuusBuiild_AddjListt(ALGrraph&&G)///輸入有向向圖的頂點數數,邊數,頂頂點信息和邊邊的信息，以以建立鄰接表表{returrnOK;;}//Builld_AdjjList7.試在鄰接矩矩陣存儲結構構上實現圖的的基本操作：：DeletteArc((G,v,ww)，即刪除除一條邊的操操作。（如果要刪除所所有從第i個個頂點出發的的邊呢？提示：將將鄰接矩陣的的第i行全部部置0）解：//設設本題中的圖圖G為有向無無權圖StatusDeletteArc((MGrapph&G,,chaarv,charrw)///在鄰接矩陣陣表示的圖GG上刪除邊((v,w){}returrnOK;;}//DDeletee_Arc答案：一、12345678910√×××××√×√×二、156n個頂點n-11條邊的連通通圖11鄰接表231,327n12鄰接矩陣398913O(n2)O(n+ee)435092(n-1)140134256601234655533102*(n-1))15三、四、1、答：前序遍歷序列：：D，A，CC，E，B，HH，F，G，II；中序序遍歷序列：：D，C，BB，E，H，AA，G，I，FF，試畫出二叉樹BB，并簡述由由任意二叉樹樹B的前序遍遍歷序列和中中序遍歷序列列求二叉樹BB的思想方法法。解：方法是：由由前序先確定定root，由由中序可確定定root的左左、右子樹。然然后由其左子子樹的元素集集合和右子樹樹的集合對應應前序遍歷序序列中的元素素集合，可繼繼續確定rooot的左右右孩子。將他他們分別作為為新的rooot，不斷遞遞歸，則所有有元素都將被被唯一確定，問問題得解。2、答：DLRR：ABDFJGKCEHILM LDR:BFJDGKACHELIM LRD：JFKGDBHLMIECA3、答：注意全部兄兄弟之間都要要連線（包括括度為2的兄兄弟）,并注意原有有連線結點一一律歸入左子子樹，新添連連線結點一律律歸入右子樹樹。4、答：注意根右邊邊的子樹肯定定是森林，而而孩子結點的的右子樹均為為兄弟。五、1、頂點1頂點123456入度321122出度022313（2）（3）12→1→43→2→64→3→5→65→16→1→2→5（4） 1→2→5→62→3→63→44→25→4→66→3→4 6、解：設起點為aa。可以直接接由原始圖畫畫出最小生成成樹，而且最最小生成樹只只有一種（類類）!鄰接矩陣為：最小生成樹最小生成樹→PRIM算法（橫橫向變化）：：VbcdefghUV-UVexlowcostta4a3a∞a∞a∞a∞a∞{a}{b,c,d,,e,f,gg,h}Vexlowcostta40c5a∞a∞a∞c5{a,c}{b,d,ee,f,g,,h}Vexlowcostt00c5b9a∞a∞c5{a,c,b}}{d,e,f,,g,h}Vexlowcostt000d7d6d5d4{a,c,b,,d}{e,f,g,,h}Vexlowcostt000d7d6d50{a,c,b,,d,h}{e,f,g}Vexlowcostt000d7g200{a,c,b,,d,h,g}{f,e}}Vexlowcostt000f3000{a,c,b,,d,h,g,ff}{e}Vexlowcostt0000000{a,c,b,,d,h,g,ff,e}}{}鄰接表為：0a→14→231b→04→25→35→49^2c→03→15→35→75^3d→15→25→47→56→65→74^4e→19→37→53^5f→36→43→62^6g→35→52→76^7h→25→34→66^克魯斯卡爾算法步驟克魯斯卡爾算法步驟(按邊歸并,堆排序)：先羅列：f2ga—3--cf—3—ea—4bd—44—h(a,b,c))(ee,f,g))(dd,h)取b—5—d,g—5--d就把三個連連通分量連接接起來了。7、8、1試著找出網網G的最小生生成樹，畫出出其邏輯結構構圖；2用兩種不同同的表示法畫畫出網G的存存儲結構圖；；3用C語言（或或其他算法語語言）定義其其中一種表示示法（存儲結結構）的數據據類型。AB———————CE————FG————D解：AB———————CE————FG————D2.可用鄰接接矩陣和鄰接接表來描述：：描述存儲結構的數據類型可參見教材或電子教案：注：描述存儲結構的數據類型可參見教材或電子教案：注：用兩個數組分別存儲頂點表和鄰接矩陣#defineINFINITYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20//假設的最大頂點數（可取為7）Typedefenum{DG,DN,AG,AN}GraphKind;//有向/無向圖，有向/無向網TypedefstructArcCell{//弧（邊）結點的定義VRTypeadj;//頂點間關系，無權圖取1或0；有權圖取權值類型InfoType*info;//該弧相關信息的指針}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];Typedefstruct{//圖的定義VertexTypevexs[MAX_VERTEX_NUM];//頂點表，用一維向量即可AdjMatrixarcs;//鄰接矩陣IntVernum,arcnum;//頂點總數（7），弧（邊）總數（9）GraphKindkind;//圖的種類標志}Mgraph;鄰接表為：0a→112→44^1b→012→220→48→59^2c→120→315→612^3d→215→610^4e→04→18→56^5f→19→46^6g→212→310五、1、intLeaafCounnt_BiTTree(BBitreeeT)///求二叉樹中中葉子結點的的數目{if(!TT)retturn00;//空空樹沒有葉子子elseif(!TT->lchhild&&&!T->rrchildd)retturn11;//葉葉子結點elsereturrnLeaaf_Couunt(T-->lchiild)+LLeaf_CCount((T->rcchild));//左子子樹的葉子數數加上右子樹的葉子子數}//LeaffCountt_BiTrree2、intGett_Deptth(BittreeTT)//求子子樹深度的遞遞歸算法{if(!TT)retturn00;else{m=GGet_Deepth(TT->lchhild);;n=GGet_Deepth(TT->rchhild);;retturn((m>n?mm:n)+11;}}//Get__Depthh3、intGett_Sub__Depthh(BitrreeT,,intxx)//求二二叉樹中以值值為x的結點點為根的子樹樹深度{if(T-->dataa==x){priintf(""%d\n"",Get__Depthh(T));;//找到到了值為x的的結點,求其其深度exiit1;}}else{if((T->lcchild))Get__Sub_DDepth((T->lcchild,,x);if((T->rcchild))Get__Sub_DDepth((T->rcchild,,x);///在左右子子樹中繼續尋尋找}}//Get__Sub_DDepth4、voidLaayerOrrder(BBitreeeT)///層序遍歷二二叉樹{InitQQueue((Q);///建立工作作隊列EnQueeue(Q,,T);whilee(!QueeueEmppty(Q))){DeQQueue((Q,p);;vissit(p));if((p->lcchild))EnQuueue(QQ,p->llchildd);if((p->rcchild))EnQuueue(QQ,p->rrchildd);}}//LayeerOrdeer5、答：intIIsFulll_Bitrree(BiitreeT)//判判斷二叉樹是是否完全二叉叉樹,是則返返回1,否則則返回0{InitQQueue((Q);flag==0;EnQueeue(Q,,T);///建立工作作隊列whilee(!QueeueEmppty(Q))){{DeQQueue((Q,p);;if((!p)fflag=11;elsseif((flag))retuurn0;;elsse{EEnQueuue(Q,pp->lchhild);;EEnQueuue(Q,pp->rchhild);;//不管管孩子是否為為空,都入隊隊列}}//whhilereturrn1;}//IsFuull_Biitree分析:該問題可可以通過層序序遍歷的方法法來解決.與與6.47相相比,作了一一個修改,不不管當前結點點是否有左右孩子子,都入隊列列.這樣當樹樹為完全二叉叉樹時,遍歷歷時得到是一一個連續的不不包含空指針的序列.反反之,則序列列中會含有空空指針.6、解：StatuusBuiild_AddjListt(ALGrraph&&G)///輸入有向向圖的頂點數數,邊數,頂頂點信息和邊邊的信息建立立鄰接表{InitAALGrapph(G);;scanff("%d"",&v);;if(v<<0)reeturnERRORR;//頂頂點數不能為為負G.vexxnum=vv;scanff("%d"",&a);;if(a<<0)reeturnERRORR;//邊邊數不能為負負G.arccnum=aa;for(mm=0;m<<v;m+++)G.vverticces[m]].dataa=getcchar());//輸輸入各頂點的的符號for(mm=1;m<<=a;m+++){t=ggetchaar();hh=getcchar());//tt為弧尾,hh為弧頭if(((i=LoocateVVex(G,,t))<00)retturnEERROR;;if(((j=LoocateVVex(G,,h))<00)retturnEERROR;;//頂點點未找到p=((ArcNoode*)mmallocc(sizeeof(ArrcNodee));if((!G.veerticees.[i]].firsstarc))G.veerticees[i]..firsttarc=pp;elsse{ffor(q==G.verrticess[i].ffirstaarc;q-->nexttarc;qq=q->nnextarrc);qq->nexxtarc==p;}p->>adjveex=j;pp->nexxtarc==NULL;;}//whhilereturrnOK;;}//Builld_AdjjList7、解：//本題中中的圖G均為為有向無權圖。StatusDelette_Arcc(MGraaph&GG,charrv,chharw))//在鄰接接矩陣表示的的圖G上刪除除邊(v,ww){if((ii=LocaateVexx(G,v)))<0)returrnERRROR;if((jj=LocaateVexx(G,w)))<0)returrnERRROR;if(G..arcs[[i][j]].adj)){G.aarcs[ii][j]..adj=00;G.aarcnumm--;}returrnOK;;}//Deleete_Arrc第9章查找自測卷答答案姓名班級A題號一二三四五總分題分1027162423100得分一、填空題（每每空1分，共共10分）1.在數據的的存放無規律律而言的線性性表中進行檢檢索的最佳方方法是順序查找找（線性查找找）。2.線性有序序表（a1，a2，a3，…，a256)是從小到大大排列的，對對一個給定的的值k，用二二分法檢索表表中與k相等等的元素，在在查找不成功功的情況下，最最多需要檢索索8次。設有有100個結結點，用二分分法查找時，最最大比較次數數是7。3.假設在有有序線性表aa[20]上上進行折半查查找，則比較較一次查找成成功的結點數數為1；比較兩次次查找成功的的結點數為2；比較較四次查找成成功的結點數數為8；平均均查找長度為為3.77。解：顯然，平均均查找長度＝＝O（logg2n）<5次（225）。但具體體是多少次，則則不應當按照照公式來計算（即（221×log221）/220＝4.66次并不正確確！）。因為為這是在假設設n＝2m-1的情況下下推導出來的的公式。應當當用窮舉法羅羅列：全部元素的查找找次數為＝（11＋2×2＋4×3＋8×4＋5×5）＝744；ASLL＝74/220=3.77！！！！4．折半查找有有序表（4，66，12，220，28，338，50，770，88，1100），若若查找表中元元素20，它它將依次與表表中元素28，6，12，20比較較大小。5.在各種查查找方法中，平平均查找長度度與結點個數數n無關的查查找方法是散列查找找。6.散列法存存儲的基本思思想是由關鍵字的值值決定數據的的存儲地址。7.有一個表表長為m的散散列表，初始始狀態為空，現現將n（n<m）個不不同的關鍵碼碼插入到散列列表中，解決決沖突的方法法是用線性探探測法。如果果這n個關鍵鍵碼的散列地地址都相同，則則探測的總次次數是n(n-1)/2=（1＋2＋…＋n-1）。(而任一元素素查找次數≤n-1)二、單項選擇題題（每小題11分，共277分）（B）11．在表長為為ｎ的鏈表中中進行線性查查找，它的平平均查找長度度為Ａ.ＡＳＬ＝＝ｎ;Ｂ.ＡＳＬ＝＝（ｎ＋１）／／２;Ｃ.ＡＳＬ＝＝＋１;ＤＤ.ＡＳＬ≈ｌｏｇ２（ｎ＋１）－－１（A）2．折半查找找有序表（44，6，100，12，220，30，550，70，888，1000）。若查找找表中元素558，則它將將依次與表中中比較大小，查查找結果是失失敗。A．20，700，30，550B．330，88，770，50C．20，550D．300，88，550（C）3．對22個個記錄的有序序表作折半查查找，當查找找失敗時，至至少需要比較較次關關鍵字。A．3B．4C．．5D．6（A）4.鏈表適用于于查找找A．順序B．．二分法C．順序序，也能二分分法D．隨機（C）5.折半搜索索與二叉搜索索樹的時間性性能A.相相同B..完全不不同CC.有時不不相同DD.數量級級都是O（llog2n）6．從供選擇的的答案中，選選出應填入下下面敘述？內的最確切切的解答，把把相應編號寫寫在答卷的對對應欄內。要進行線性查找找，則線性表表A；要進行二二分查找，則則線性表B；；要進行散列列查找，則線線性表CC。某順序存儲的表表格，其中有有900000個元素，已已按關鍵項的的值的上升順順序排列。現現假定對各個個元素進行查查找的概率是是相同的，并并且各個元素素的關鍵項的的值皆不相同同。當用順序序查找法查找找時，平均比比較次數約為為D，最大比比較次數為E。供選擇的答案：：A~C：①必必須以順序方方式存儲②必須以鏈鏈表方式存儲儲③必須以散散列方式存儲儲④④既可以以以順序方式，也也可以以鏈表表方式存儲⑤必須以順序序方式存儲且且數據元素已已按值遞增或或遞減的次序序排好⑥必須以鏈表表方式存儲且且數據元素已已按值遞增或或遞減的次序序排好D，E：①250000②300000③450000④900000答案：A=④B=⑤C=③D＝③E＝④7.從供選擇的的答案中，選選出應填入下下面敘述？內的最確切切的解答，把把相應編號寫寫在答卷的對對應欄內。數據結構反映了了數據元素之之間的結構關關系。鏈表是是一種A，它它對于數據元元素的插入和和刪除B。通通常查找線性性表數據元素素的方法有C和D兩種方方法，其中C是一種只只適合于順序序存儲結構但但E的方法法；而D是是一種對順序序和鏈式存儲儲結構均適用用的方法。供選擇的答案：：A：①順序存儲儲線性表②非順序存儲儲非線性表 ③順序存儲非非線性表 ④非順序存儲儲線性表B： ①不需需要移動結點點，不需改變變結點指針②不需要移動動結點，只需需改變結點指指針 ③只需移動結點點，不需改變變結點指針 ④既需移動結結點，又需改改變結點指針針C：①順序查查找②循環查找 ③條件查找 ④二分法查找找D：①順序查查找②隨機查找 ③二分法查找找 ④分塊查找E：①效率較較低的線性查查找 ②效率較低的的非線性查找找 ③效率較高的的非線性查找找 ④效率較高的的線性查找答案：A＝④B＝②C＝④D＝①E＝③8.從供選擇的的答案中，選選出應填入下下面敘述？內的最確切切的解答，把把相應編號寫寫在答卷的對對應欄內。在二叉排序樹中中，每個結點點的關鍵碼值值A，B一棵二二叉排序，即即可得到排序序序列。同一一個結點集合合，可用不同同的二叉排序序樹表示，人人們把平均檢檢索長度最短短的二叉排序序樹稱作最佳佳二叉排序，最最佳二叉排序序樹在結構上上的特點是C。供選擇的答案A：①比左子子樹所有結點點的關鍵碼值值大，比右子子樹所有結點點的關鍵碼值值小②比左子樹所有有結點的關鍵鍵碼值小，比比右子樹所有有結點的關鍵鍵碼值大③比左右子樹樹的所有結點點的關鍵碼值值都大④與左子樹所所有結點的關關鍵碼值和右右子樹所有結結點的關鍵碼碼值無必然的的大小關系B:①前前序遍歷②中序（對對稱）遍歷③后序遍歷歷④④層次遍歷歷C：①除最下下二層可以不不滿外，其余余都是充滿的的②除最下一層層可以不滿外外，其余都是是充滿的③每個個結點的左右右子樹的高度度之差的絕對對值不大于11④最下層的的葉子必須在在最左邊答案：A＝①B＝②C＝②9.從供選擇擇的答案中，選選出應填入下下面敘述？內的最確切切的解答，把把相應編號寫寫在答卷的對對應欄內。散列法存儲的基基本思想是根根據A來決定定B，碰撞撞（沖突）指指的是CC，處理理碰撞的兩類類主要方法是是DD。供選擇的答案A，B：①存存儲地址②元素的符符號③元素個數數④關鍵碼值值⑤⑤非碼屬性性⑥⑥平均檢索索長度⑦負載因子子⑧散列表空空間C:①兩兩個元素具有有相同序號②兩個元素素的關鍵碼值值不同，而非非碼屬性相同同③不同關鍵鍵碼值對應到到相同的存儲儲地址④負載因子子過大⑤數據元素素過多D：①線性性探查法和雙雙散列函數法法②建溢出區區法和不建溢溢出區法③除余法和折折疊法 ④拉鏈法和和開地址法答案：A＝④BB＝①CC＝③D＝④10.考慮具有有如下性質的的二叉樹：除除葉子結點外外，每個結點點的值都大于于其左子樹上上的一切結點點的值。并小小于等于其右右子樹上的一一切結點的值值。現把9個數1，22，3，…，8，9填填入右圖所示的二二叉樹的9個個結點中，并并使之具有上上述性質。此此時，n1的的值是A，n22的值是B，nn9的值是C。現欲把把放入此樹并并使該樹保持持前述性質，增增加的一個結結點可以放在在D或E。供選擇的答案A～C：①11②2③3④4⑤5⑥6⑦7⑧8⑨9D～E：①n7下面②n8下面面③n9下面面④n6下面面⑤n1與nn2之間⑥n2與nn4之間⑦n6與nn9之間⑧n3與nn6之間答案：A＝⑦B＝④C＝⑥D＝②E＝⑥三、簡答題（每每小題4分，共共16分）1.對分（折半半）查找適不不適合鏈表結結構的序列，為為什么？用二二分查找的查查找速度必然然比線性查找找的速度快，這這種說法對嗎嗎？答：不適合！雖雖然有序的單單鏈表的結點點是按從小到到大（或從大大到小）順序序排列，但因因其存儲結構構為單鏈表，查查找結點時只只能從頭指針針開始逐步搜搜索，故不能能進行折半查查找。二分查找的速度度在一般情況況下是快些，但但在特殊情況況下未必快。例例如所查數據據位于首位時時，則線性查查找快；而二二分查找則慢慢得多。2.假定對有序序表：（3，44，5，7，224，30，442，54，663，72，887，95）進進行折半查找找，試回答下下列問題：畫出描述折半查查找過程的判判定樹；若查找元素544，需依次與與哪些元素比比較？若查找元素900，需依次與與哪些元素比比較？假定每個元素的的查找概率相相等，求查找找成功時的平平均查找長度度。解：先畫出判定樹如如下（注：mmid=(11+12)//2=6）：305633774287424554722995(2)查找元元素54，需需依次與300,63,,42,54等元元素比較；(3)查找元元素90，需需依次與300,63,,87,995,722等元素比較較；（4）求ASSL之前，需需要統計每個個元素的查找找次數。判定定樹的前3層層共查找1＋＋2×2＋4×3=17次次；但最后一層未滿滿，不能用88×4，只能用用5×4=20次次，所以ASL＝11/12（117＋20）＝＝37/122≈3.083.用比較兩個個元素大小的的方法在一個個給定的序列列中查找某個個元素的時間間復雜度下限限是什么?如果要求時時間復雜度更更小,你采用用什么方法？？此方法的時時間復雜度是是多少?答：查找某個元元素的時間復復雜度下限，如如果理解為最最短查找時間間，則當關鍵鍵字值與表頭頭元素相同時時，比較1次次即可。要想想降低時間復復雜度，可以以改用Hassh查找法。此此方法對表內內每個元素的的比較次數都都是O（1）。4.設哈希（HHash）表表的地址范圍圍為0～177，哈希函數數為：H（KK）＝KMOD16。K為關鍵字，用用線性探測法法再散列法處處理沖突，輸輸入關鍵字序序列：（10，224，32，117，31，330，46，447，40，663，49）造出Hash表表，試回答下下列問題：畫出哈希表的示示意圖；若查找關鍵字663，需要依依次與哪些關關鍵字進行比比較？若查找關鍵字660，需要依依次與哪些關關鍵字比較？？假定每個關鍵字字的查找概率率相等，求查查找成功時的的平均查找長長度。解：（1）畫畫表如下：012345678910111213141516173217634924401030314647（2）查找663,首先要要與H(633)=63%%16=155號單元內容容比較，即663vs31,noo;然后順移，與446,47,,32,177,63相比比，一共比較較了6次！（3）查找600,首先要與與H(60)=60%16=112號單元內內容比較，但但因為12號號單元為空（應應當有空標記記），所以應應當只比較這這一次即可。（4）對于黑黑色數據元素素，各比較11次；共6次次；對紅色元素則各各不相同，要要統計移位的的位數。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=11/11（66＋2＋3××3）＝177/11=11.545445454554≈1.55四、分析題（每每小題6分，共共24分）1.畫出對對長度為100的有序表進進行折半查找找的判定樹，并并求其等概率率時查找成功功的平均查找找長度。解：判定樹應當當描述每次查查找的位置：：58136944771102.在一棵空的的二叉查找樹樹中依次插入入關鍵字序列列為12，77