華東交大數(shù)據(jù)結(jié)構(gòu)自測(cè)卷及答案

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

）存儲(chǔ)方式式最節(jié)省時(shí)間間。A．順序表

B．雙雙鏈表

C．帶頭結(jié)點(diǎn)點(diǎn)的雙循環(huán)鏈鏈表

DD．單循環(huán)鏈鏈表（C）3、若長(zhǎng)度為為n的線性表采采用順序存儲(chǔ)儲(chǔ)結(jié)構(gòu)，在其其第i個(gè)位置插入入一個(gè)新元素素的算法的時(shí)時(shí)間復(fù)雜度為為（

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

B.OO(1)

C.O(n)

DD.O(nn2)（B）4、在單鏈表表指針為p的結(jié)點(diǎn)之后后插入指針為為s的結(jié)點(diǎn)，正正確的操作是是：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、對(duì)于一個(gè)個(gè)頭指針為hhead的帶帶頭結(jié)點(diǎn)的單單鏈表，判定定該表為空表表的條件是（

）head==NNULL

BB．head-->nextt==NULLL

C．head-->nextt==heaad

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

(4)(1)

。b.在P結(jié)點(diǎn)點(diǎn)前插入S結(jié)點(diǎn)的語(yǔ)句句序列是：

7

118441

。c.在表首插插入S結(jié)點(diǎn)的語(yǔ)句句序列是：

512

。d.在表尾插插入S結(jié)點(diǎn)的語(yǔ)句句序列是：

9166

。供選擇的語(yǔ)句有有：（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;;簡(jiǎn)答題(共155分)說明線性表、棧棧與隊(duì)的異同同點(diǎn)。順序隊(duì)的“假溢溢出”是怎樣產(chǎn)生生的？如何知知道循環(huán)隊(duì)列列是空還是滿滿？設(shè)循環(huán)隊(duì)列的容容量為40（序號(hào)從從0到39），現(xiàn)經(jīng)經(jīng)過一系列的的入隊(duì)和出隊(duì)隊(duì)運(yùn)算后，有有①frontt=11，rear==19;②fronnt=19，rear==11；問在在這兩種情況況下，循環(huán)隊(duì)隊(duì)列中各有元元素多少個(gè)？？算法設(shè)計(jì)（共330分）寫一算法，從順順序表中刪除除自第i個(gè)元素開始始的k個(gè)元素。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;}試寫一個(gè)算法，判判別讀入的一一個(gè)以‘@’’為結(jié)束符的的字符序列是是否是“回文”。（正讀和反讀讀都相同的字字符序列為“回文”，例如，‘a(chǎn)abba’和和‘a(chǎn)bcbba’是回文文，‘a(chǎn)bccde’和和‘a(chǎn)babbab’則不不是回文。）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;//返返回結(jié)果1表表示是回文，00表示不是回回文 elserreturnn0;}假設(shè)有一個(gè)循環(huán)環(huán)鏈表的長(zhǎng)度度大于1，且表中既既無頭結(jié)點(diǎn)也也無頭指針。已已知s為指向鏈表表某個(gè)結(jié)點(diǎn)的的指針，試編編寫算法在鏈鏈表中刪除指指針s所指結(jié)點(diǎn)的的前趨結(jié)點(diǎn)。StatusDelette(LinnkListts){p=s;while(pp->nexxt->neext!=ss)///查找s的前前一個(gè)結(jié)點(diǎn)的的前一個(gè)結(jié)點(diǎn)點(diǎn)；p=p-->nextt;q=p->neext;p->nextt=s;deleteq;returnOK;}第6章樹和和圖自測(cè)卷卷姓名班級(jí)學(xué)號(hào)題號(hào)一二三四五總分題分1017174016100得分一、下面是有關(guān)關(guān)二叉樹的敘敘述，請(qǐng)判斷斷正誤（每小小題1分，共共10分）（）1..若二叉樹用用二叉鏈表作作存貯結(jié)構(gòu)，則則在n個(gè)結(jié)點(diǎn)點(diǎn)的二叉樹鏈鏈表中只有nn—1個(gè)非空指針針域。（）2..二叉樹中每每個(gè)結(jié)點(diǎn)的兩兩棵子樹的高高度差等于11。（）3..二叉樹中每每個(gè)結(jié)點(diǎn)的兩兩棵子樹是有有序的。（）4..二叉樹中每每個(gè)結(jié)點(diǎn)有兩兩棵非空子樹樹或有兩棵空空子樹。（）5..二叉樹樹中所有結(jié)點(diǎn)點(diǎn)個(gè)數(shù)是2kk-1-1，其其中k是樹的的深度。（）6..對(duì)于一一棵非空二叉叉樹，它的根根結(jié)點(diǎn)作為第第一層，則它它的第i層上上最多能有22i－1個(gè)結(jié)點(diǎn)點(diǎn)。（）7..具有122個(gè)結(jié)點(diǎn)的完完全二叉樹有有5個(gè)度為22的結(jié)點(diǎn)。（）8..不同的求求最小生成樹樹的方法最后后得到的生成成樹是相同的的.（）9..有n個(gè)頂頂點(diǎn)的無向圖圖,采用鄰鄰接矩陣表示示,圖中的的邊數(shù)等于鄰鄰接矩陣中非非零元素之和和的一半。（）100.無向圖圖的鄰接矩陣陣一定是對(duì)稱稱矩陣，有向向圖的鄰接矩矩陣一定是非非對(duì)稱矩陣。二、填空（每空空1分，共117分）1．由３個(gè)結(jié)結(jié)點(diǎn)所構(gòu)成的的二叉樹有種形態(tài)。2.一棵深深度為6的滿滿二叉樹有個(gè)分分支結(jié)點(diǎn)和個(gè)葉子。3．一棵具有有257個(gè)結(jié)結(jié)點(diǎn)的完全二二叉樹，它的的深度為。4．設(shè)一棵完完全二叉樹有有700個(gè)結(jié)結(jié)點(diǎn)，則共有有個(gè)葉子結(jié)點(diǎn)點(diǎn)。5.用5個(gè)權(quán)權(quán)值{3,2,,4,55,1}構(gòu)造的哈夫夫曼（Hufffman）樹樹的帶權(quán)路徑徑長(zhǎng)度是。6.判斷一個(gè)個(gè)無向圖是一一棵樹的條件件是_______。7.在有nn個(gè)頂點(diǎn)的有有向圖中，若若要使任意兩兩點(diǎn)間可以互互相到達(dá)，則則至少需要________條弧。8.G是一個(gè)個(gè)非連通無向向圖，共有228條邊，則則該圖至少有有_______個(gè)頂點(diǎn)9.N個(gè)頂點(diǎn)點(diǎn)的連通圖用用鄰接矩陣表表示時(shí),該矩矩陣至少有_________個(gè)非零元元素。10．在有n個(gè)個(gè)頂點(diǎn)的有向向圖中，每個(gè)個(gè)頂點(diǎn)的度最最大可達(dá)_______。11．設(shè)有一稀稀疏圖G，則則G采用存儲(chǔ)較省省空間。12．設(shè)有一稠稠密圖G，則則G采用存儲(chǔ)較省空空間。13．n個(gè)頂點(diǎn)點(diǎn)e條邊的圖圖采用鄰接矩矩陣存儲(chǔ)，深深度優(yōu)先遍歷歷算法的時(shí)間間復(fù)雜度為；若采采用鄰接表存存儲(chǔ)時(shí)，該算算法的時(shí)間復(fù)復(fù)雜度為。14．已知圖圖的鄰接矩陣陣，根據(jù)算法法思想，則從從頂點(diǎn)0出發(fā)發(fā)按深度優(yōu)先先遍歷的結(jié)點(diǎn)點(diǎn)序列是。則從頂頂點(diǎn)0出發(fā)按按廣度優(yōu)先遍遍歷的結(jié)點(diǎn)序序列是。三、選擇題（每每小題1分，共共17分）（）11．不含任任何結(jié)點(diǎn)的空空樹。（Ａ）是一棵樹樹;（Ｂ）是一一棵二叉樹;;（Ｃ）是一棵樹樹也是一棵二二叉樹;（Ｄ）既既不是樹也不不是二叉樹（）22．二叉樹是是非線性數(shù)據(jù)據(jù)結(jié)構(gòu)，所以以。（Ａ）它不能用用順序存儲(chǔ)結(jié)結(jié)構(gòu)存儲(chǔ);（Ｂ）它它不能用鏈?zhǔn)绞酱鎯?chǔ)結(jié)構(gòu)存存儲(chǔ);（Ｃ）順序存儲(chǔ)儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)绞酱鎯?chǔ)結(jié)構(gòu)都都能存儲(chǔ);（Ｄ）順順序存儲(chǔ)結(jié)構(gòu)構(gòu)和鏈?zhǔn)酱鎯?chǔ)儲(chǔ)結(jié)構(gòu)都不能能使用（）33.具有有n(n>00)個(gè)結(jié)點(diǎn)的的完全二叉樹樹的深度為。(Ａ)logg2(n)(Ｂ)logg2(n)(Ｃ)logg2(n)+11(Ｄ)log2(n)+11（）44．把一棵樹樹轉(zhuǎn)換為二叉叉樹后，這棵棵二叉樹的形形態(tài)是。（Ａ）唯一的（Ｂ）有多多種（Ｃ）有多種，但但根結(jié)點(diǎn)都沒沒有左孩子（ＤＤ）有多種，但但根結(jié)點(diǎn)都沒沒有右孩子（）55.在一個(gè)個(gè)圖中，所有有頂點(diǎn)的度數(shù)數(shù)之和等于圖圖的邊數(shù)的倍。A．1//2B..1C.2DD.4（）77.在一個(gè)個(gè)有向圖中，所所有頂點(diǎn)的入入度之和等于于所有頂點(diǎn)的的出度之和的的倍。A．1//2B..1C.2DD.4（）88.用鄰接接表表示圖進(jìn)進(jìn)行廣度優(yōu)先先遍歷時(shí)，通通常是采用來實(shí)實(shí)現(xiàn)算法的。A．棧B..隊(duì)列C..樹D..圖（）99.深度優(yōu)優(yōu)先遍歷類似似于二叉樹的的A．先序遍歷B.中序序遍歷C.后序遍歷歷DD.層次次遍歷（）110.廣度度優(yōu)先遍歷類類似于二叉樹樹的A．先序遍歷B.中序序遍歷C.后序遍歷歷DD.層次次遍歷11.樹是是結(jié)點(diǎn)的有限限集合，它A根結(jié)點(diǎn)，記記為T。其余余的結(jié)點(diǎn)分成成為m（m≥≥0）個(gè)BB的集合T1，TT2，…，Tm，每每個(gè)集合又都都是樹，此時(shí)時(shí)結(jié)點(diǎn)T稱為為Ti的父結(jié)點(diǎn)，TTi稱為T的子子結(jié)點(diǎn)（1≤≤i≤m）。一個(gè)個(gè)結(jié)點(diǎn)的子結(jié)結(jié)點(diǎn)個(gè)數(shù)為該該結(jié)點(diǎn)的C。供選擇的答案A：①有00個(gè)或1個(gè)②有0個(gè)或多多個(gè)③有且只有11個(gè)④有1個(gè)或11個(gè)以上B:①互互不相交 ②允許相交交③③允許葉結(jié)結(jié)點(diǎn)相交④允許樹枝枝結(jié)點(diǎn)相交C：①權(quán) ②維數(shù)③次數(shù)④序答案：A=BB=C=12.二叉樹樹A。在完全全的二叉樹中中，若一個(gè)結(jié)結(jié)點(diǎn)沒有B，則則它必定是葉葉結(jié)點(diǎn)。每棵棵樹都能惟一一地轉(zhuǎn)換成與與它對(duì)應(yīng)的二二叉樹。由樹樹轉(zhuǎn)換成的二二叉樹里，一一個(gè)結(jié)點(diǎn)N的的左子女是NN在原樹里對(duì)對(duì)應(yīng)結(jié)點(diǎn)的C，而N的右右子女是它在在原樹里對(duì)應(yīng)應(yīng)結(jié)點(diǎn)的D。供選擇的答案A：①是特殊殊的樹②不是樹的特特殊形式③是兩棵樹的的總稱④有是只有二二個(gè)根結(jié)點(diǎn)的的樹形結(jié)構(gòu)B:①左左子結(jié)點(diǎn)②右子結(jié)點(diǎn)點(diǎn)③左子結(jié)點(diǎn)點(diǎn)或者沒有右右子結(jié)點(diǎn)④兄弟C～D：①最最左子結(jié)點(diǎn)②最右子結(jié)結(jié)點(diǎn)③最鄰近的的右兄弟④最鄰近的的左兄弟⑤最左的兄兄弟⑥最右的兄兄弟答案：A=BB=C=D＝四、閱讀分析題題（每題5分分，共40分分）1.給定二叉叉樹的兩種遍遍歷序列，分分別是：前序遍歷序列：：D，A，CC，E，B，HH，F(xiàn)，G，II；中序序遍歷序列：：D，C，BB，E，H，AA，G，I，F(xiàn)F，圖1試畫該出二叉樹樹圖1圖2圖2圖3圖12．試寫出如圖圖1所示的二二叉樹分別按按先序、中序序、后序遍歷歷時(shí)得到的結(jié)結(jié)點(diǎn)序列。3.把如圖圖2所示的樹樹轉(zhuǎn)化成二叉叉樹。4.畫出圖3二二叉樹相應(yīng)的的森林。5．.已知如圖圖所示的有向向圖，請(qǐng)給出出該圖的:頂點(diǎn)1234頂點(diǎn)123456入度321122出度022313鄰接矩陣；鄰接表；逆鄰接表。6．請(qǐng)對(duì)下圖的的無向帶權(quán)圖圖：寫出它的鄰接矩矩陣，并按普普里姆算法求求其最小生成成樹；寫出它的鄰接表表，并按克魯魯斯卡爾算法法求其最小生生成樹。7．已知二維數(shù)數(shù)組表示的圖圖的鄰接矩陣陣如下圖所示示。試分別畫畫出自頂點(diǎn)11出發(fā)進(jìn)行遍遍歷所得的深深度優(yōu)先生成成樹和廣度優(yōu)優(yōu)先生成樹。8．給定下列網(wǎng)網(wǎng)G:（110分）1試著找出網(wǎng)網(wǎng)G的最小生生成樹，畫出出其邏輯結(jié)構(gòu)構(gòu)圖；2用兩種不同同的表示法畫畫出網(wǎng)G的存存儲(chǔ)結(jié)構(gòu)圖；；3用C語(yǔ)言（或或其他算法語(yǔ)語(yǔ)言）定義其其中一種表示示法（存儲(chǔ)結(jié)結(jié)構(gòu)）的數(shù)據(jù)據(jù)類型。五、算法設(shè)計(jì)題題（前1~55題中任選22題，第6~~7題中任選選1題，共116分）1.編寫遞歸算算法，計(jì)算二二叉樹中葉子子結(jié)點(diǎn)的數(shù)目目。2.寫出求二二叉樹深度的的算法，先定定義二叉樹的的抽象數(shù)據(jù)類類型。3．編寫遞歸算算法，求二叉叉樹中以元素素值為x的結(jié)結(jié)點(diǎn)為根的子子樹的深度。4.編寫按層次次順序（同一一層自左至右右）遍歷二叉叉樹的算法。5.編寫算法判判別給定二叉叉樹是否為完完全二叉樹。6．編寫算法，由由依次輸入的的頂點(diǎn)數(shù)目、弧弧的數(shù)目、各各頂點(diǎn)的信息息和各條弧的的信息建立有有向圖的鄰接接表。解：StatuusBuiild_AddjListt(ALGrraph&&G)///輸入有向向圖的頂點(diǎn)數(shù)數(shù),邊數(shù),頂頂點(diǎn)信息和邊邊的信息，以以建立鄰接表表{returrnOK;;}//Builld_AdjjList7.試在鄰接矩矩陣存儲(chǔ)結(jié)構(gòu)構(gòu)上實(shí)現(xiàn)圖的的基本操作：：DeletteArc((G,v,ww)，即刪除除一條邊的操操作。（如果要?jiǎng)h除所所有從第i個(gè)個(gè)頂點(diǎn)出發(fā)的的邊呢？提示：將將鄰接矩陣的的第i行全部部置0）解：//設(shè)設(shè)本題中的圖圖G為有向無無權(quán)圖StatusDeletteArc((MGrapph&G,,chaarv,charrw)///在鄰接矩陣陣表示的圖GG上刪除邊((v,w){}returrnOK;;}//DDeletee_Arc答案：一、12345678910√×××××√×√×二、156n個(gè)頂點(diǎn)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(xiàn)，G，II；中序序遍歷序列：：D，C，BB，E，H，AA，G，I，F(xiàn)F，試畫出二叉樹BB，并簡(jiǎn)述由由任意二叉樹樹B的前序遍遍歷序列和中中序遍歷序列列求二叉樹BB的思想方法法。解：方法是：由由前序先確定定root，由由中序可確定定root的左左、右子樹。然然后由其左子子樹的元素集集合和右子樹樹的集合對(duì)應(yīng)應(yīng)前序遍歷序序列中的元素素集合，可繼繼續(xù)確定rooot的左右右孩子。將他他們分別作為為新的rooot，不斷遞遞歸，則所有有元素都將被被唯一確定，問問題得解。2、答：DLRR：ABDFJGKCEHILM LDR:BFJDGKACHELIM LRD：JFKGDBHLMIECA3、答：注意全部兄兄弟之間都要要連線（包括括度為2的兄兄弟）,并注意原有有連線結(jié)點(diǎn)一一律歸入左子子樹，新添連連線結(jié)點(diǎn)一律律歸入右子樹樹。4、答：注意根右邊邊的子樹肯定定是森林，而而孩子結(jié)點(diǎn)的的右子樹均為為兄弟。五、1、頂點(diǎn)1頂點(diǎn)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、解：設(shè)起點(diǎn)為aa?？梢灾苯咏佑稍紙D畫畫出最小生成成樹，而且最最小生成樹只只有一種（類類）!鄰接矩陣為：最小生成樹最小生成樹→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就把三個(gè)連連通分量連接接起來了。7、8、1試著找出網(wǎng)網(wǎng)G的最小生生成樹，畫出出其邏輯結(jié)構(gòu)構(gòu)圖；2用兩種不同同的表示法畫畫出網(wǎng)G的存存儲(chǔ)結(jié)構(gòu)圖；；3用C語(yǔ)言（或或其他算法語(yǔ)語(yǔ)言）定義其其中一種表示示法（存儲(chǔ)結(jié)結(jié)構(gòu)）的數(shù)據(jù)據(jù)類型。AB———————CE————FG————D解：AB———————CE————FG————D2.可用鄰接接矩陣和鄰接接表來描述：：描述存儲(chǔ)結(jié)構(gòu)的數(shù)據(jù)類型可參見教材或電子教案：注：描述存儲(chǔ)結(jié)構(gòu)的數(shù)據(jù)類型可參見教材或電子教案：注：用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)表和鄰接矩陣#defineINFINITYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20//假設(shè)的最大頂點(diǎn)數(shù)（可取為7）Typedefenum{DG,DN,AG,AN}GraphKind;//有向/無向圖，有向/無向網(wǎng)TypedefstructArcCell{//?。ㄟ叄┙Y(jié)點(diǎn)的定義VRTypeadj;//頂點(diǎn)間關(guān)系，無權(quán)圖取1或0；有權(quán)圖取權(quán)值類型InfoType*info;//該弧相關(guān)信息的指針}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];Typedefstruct{//圖的定義VertexTypevexs[MAX_VERTEX_NUM];//頂點(diǎn)表，用一維向量即可AdjMatrixarcs;//鄰接矩陣IntVernum,arcnum;//頂點(diǎn)總數(shù)（7），?。ㄟ叄┛倲?shù)（9）GraphKindkind;//圖的種類標(biāo)志}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)///求二叉樹中中葉子結(jié)點(diǎn)的的數(shù)目{if(!TT)retturn00;//空空樹沒有葉子子elseif(!TT->lchhild&&&!T->rrchildd)retturn11;//葉葉子結(jié)點(diǎn)elsereturrnLeaaf_Couunt(T-->lchiild)+LLeaf_CCount((T->rcchild));//左子子樹的葉子數(shù)數(shù)加上右子樹的葉子子數(shù)}//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的結(jié)點(diǎn)點(diǎn)為根的子樹樹深度{if(T-->dataa==x){priintf(""%d\n"",Get__Depthh(T));;//找到到了值為x的的結(jié)點(diǎn),求其其深度exiit1;}}else{if((T->lcchild))Get__Sub_DDepth((T->lcchild,,x);if((T->rcchild))Get__Sub_DDepth((T->rcchild,,x);///在左右子子樹中繼續(xù)尋尋找}}//Get__Sub_DDepth4、voidLaayerOrrder(BBitreeeT)///層序遍歷二二叉樹{InitQQueue((Q);///建立工作作隊(duì)列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);///建立工作作隊(duì)列whilee(!QueeueEmppty(Q))){{DeQQueue((Q,p);;if((!p)fflag=11;elsseif((flag))retuurn0;;elsse{EEnQueuue(Q,pp->lchhild);;EEnQueuue(Q,pp->rchhild);;//不管管孩子是否為為空,都入隊(duì)隊(duì)列}}//whhilereturrn1;}//IsFuull_Biitree分析:該問題可可以通過層序序遍歷的方法法來解決.與與6.47相相比,作了一一個(gè)修改,不不管當(dāng)前結(jié)點(diǎn)點(diǎn)是否有左右孩子子,都入隊(duì)列列.這樣當(dāng)樹樹為完全二叉叉樹時(shí),遍歷歷時(shí)得到是一一個(gè)連續(xù)的不不包含空指針的序列.反反之,則序列列中會(huì)含有空空指針.6、解：StatuusBuiild_AddjListt(ALGrraph&&G)///輸入有向向圖的頂點(diǎn)數(shù)數(shù),邊數(shù),頂頂點(diǎn)信息和邊邊的信息建立立鄰接表{InitAALGrapph(G);;scanff("%d"",&v);;if(v<<0)reeturnERRORR;//頂頂點(diǎn)數(shù)不能為為負(fù)G.vexxnum=vv;scanff("%d"",&a);;if(a<<0)reeturnERRORR;//邊邊數(shù)不能為負(fù)負(fù)G.arccnum=aa;for(mm=0;m<<v;m+++)G.vverticces[m]].dataa=getcchar());//輸輸入各頂點(diǎn)的的符號(hào)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;;//頂點(diǎn)點(diǎn)未找到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均為為有向無權(quán)圖。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章查找自測(cè)卷答答案姓名班級(jí)A題號(hào)一二三四五總分題分1027162423100得分一、填空題（每每空1分，共共10分）1.在數(shù)據(jù)的的存放無規(guī)律律而言的線性性表中進(jìn)行檢檢索的最佳方方法是順序查找找（線性查找找）。2.線性有序序表（a1，a2，a3，…，a256)是從小到大大排列的，對(duì)對(duì)一個(gè)給定的的值k，用二二分法檢索表表中與k相等等的元素，在在查找不成功功的情況下，最最多需要檢索索8次。設(shè)有有100個(gè)結(jié)結(jié)點(diǎn)，用二分分法查找時(shí)，最最大比較次數(shù)數(shù)是7。3.假設(shè)在有有序線性表aa[20]上上進(jìn)行折半查查找，則比較較一次查找成成功的結(jié)點(diǎn)數(shù)數(shù)為1；比較兩次次查找成功的的結(jié)點(diǎn)數(shù)為2；比較較四次查找成成功的結(jié)點(diǎn)數(shù)數(shù)為8；平均均查找長(zhǎng)度為為3.77。解：顯然，平均均查找長(zhǎng)度＝＝O（logg2n）<5次（225）。但具體體是多少次，則則不應(yīng)當(dāng)按照照公式來計(jì)算（即（221×log221）/220＝4.66次并不正確確?。?。因?yàn)闉檫@是在假設(shè)設(shè)n＝2m-1的情況下下推導(dǎo)出來的的公式。應(yīng)當(dāng)當(dāng)用窮舉法羅羅列：全部元素的查找找次數(shù)為＝（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.在各種查查找方法中，平平均查找長(zhǎng)度度與結(jié)點(diǎn)個(gè)數(shù)數(shù)n無關(guān)的查查找方法是散列查找找。6.散列法存存儲(chǔ)的基本思思想是由關(guān)鍵字的值值決定數(shù)據(jù)的的存儲(chǔ)地址。7.有一個(gè)表表長(zhǎng)為m的散散列表，初始始狀態(tài)為空，現(xiàn)現(xiàn)將n（n<m）個(gè)不不同的關(guān)鍵碼碼插入到散列列表中，解決決沖突的方法法是用線性探探測(cè)法。如果果這n個(gè)關(guān)鍵鍵碼的散列地地址都相同，則則探測(cè)的總次次數(shù)是n(n-1)/2=（1＋2＋…＋n-1）。(而任一元素素查找次數(shù)≤n-1)二、單項(xiàng)選擇題題（每小題11分，共277分）（B）11．在表長(zhǎng)為為ｎ的鏈表中中進(jìn)行線性查查找，它的平平均查找長(zhǎng)度度為Ａ.ＡＳＬ＝＝ｎ;Ｂ.ＡＳＬ＝＝（ｎ＋１）／／２;Ｃ.ＡＳＬ＝＝＋１;ＤＤ.ＡＳＬ≈ｌｏｇ２（ｎ＋１）－－１（A）2．折半查找找有序表（44，6，100，12，220，30，550，70，888，1000）。若查找找表中元素558，則它將將依次與表中中比較大小，查查找結(jié)果是失失敗。A．20，700，30，550B．330，88，770，50C．20，550D．300，88，550（C）3．對(duì)22個(gè)個(gè)記錄的有序序表作折半查查找，當(dāng)查找找失敗時(shí)，至至少需要比較較次關(guān)關(guān)鍵字。A．3B．4C．．5D．6（A）4.鏈表適用于于查找找A．順序B．．二分法C．順序序，也能二分分法D．隨機(jī)（C）5.折半搜索索與二叉搜索索樹的時(shí)間性性能A.相相同B..完全不不同CC.有時(shí)不不相同DD.數(shù)量級(jí)級(jí)都是O（llog2n）6．從供選擇的的答案中，選選出應(yīng)填入下下面敘述？?jī)?nèi)的最確切切的解答，把把相應(yīng)編號(hào)寫寫在答卷的對(duì)對(duì)應(yīng)欄內(nèi)。要進(jìn)行線性查找找，則線性表表A；要進(jìn)行二二分查找，則則線性表B；；要進(jìn)行散列列查找，則線線性表CC。某順序存儲(chǔ)的表表格，其中有有900000個(gè)元素，已已按關(guān)鍵項(xiàng)的的值的上升順順序排列。現(xiàn)現(xiàn)假定對(duì)各個(gè)個(gè)元素進(jìn)行查查找的概率是是相同的，并并且各個(gè)元素素的關(guān)鍵項(xiàng)的的值皆不相同同。當(dāng)用順序序查找法查找找時(shí)，平均比比較次數(shù)約為為D，最大比比較次數(shù)為E。供選擇的答案：：A~C：①必必須以順序方方式存儲(chǔ)②必須以鏈鏈表方式存儲(chǔ)儲(chǔ)③必須以散散列方式存儲(chǔ)儲(chǔ)④④既可以以以順序方式，也也可以以鏈表表方式存儲(chǔ)⑤必須以順序序方式存儲(chǔ)且且數(shù)據(jù)元素已已按值遞增或或遞減的次序序排好⑥必須以鏈表表方式存儲(chǔ)且且數(shù)據(jù)元素已已按值遞增或或遞減的次序序排好D，E：①250000②300000③450000④900000答案：A=④B=⑤C=③D＝③E＝④7.從供選擇的的答案中，選選出應(yīng)填入下下面敘述？?jī)?nèi)的最確切切的解答，把把相應(yīng)編號(hào)寫寫在答卷的對(duì)對(duì)應(yīng)欄內(nèi)。數(shù)據(jù)結(jié)構(gòu)反映了了數(shù)據(jù)元素之之間的結(jié)構(gòu)關(guān)關(guān)系。鏈表是是一種A，它它對(duì)于數(shù)據(jù)元元素的插入和和刪除B。通通常查找線性性表數(shù)據(jù)元素素的方法有C和D兩種方方法，其中C是一種只只適合于順序序存儲(chǔ)結(jié)構(gòu)但但E的方法法；而D是是一種對(duì)順序序和鏈?zhǔn)酱鎯?chǔ)儲(chǔ)結(jié)構(gòu)均適用用的方法。供選擇的答案：：A：①順序存儲(chǔ)儲(chǔ)線性表②非順序存儲(chǔ)儲(chǔ)非線性表 ③順序存儲(chǔ)非非線性表 ④非順序存儲(chǔ)儲(chǔ)線性表B： ①不需需要移動(dòng)結(jié)點(diǎn)點(diǎn)，不需改變變結(jié)點(diǎn)指針②不需要移動(dòng)動(dòng)結(jié)點(diǎn)，只需需改變結(jié)點(diǎn)指指針 ③只需移動(dòng)結(jié)點(diǎn)點(diǎn)，不需改變變結(jié)點(diǎn)指針 ④既需移動(dòng)結(jié)結(jié)點(diǎn)，又需改改變結(jié)點(diǎn)指針針C：①順序查查找②循環(huán)查找 ③條件查找 ④二分法查找找D：①順序查查找②隨機(jī)查找 ③二分法查找找 ④分塊查找E：①效率較較低的線性查查找 ②效率較低的的非線性查找找 ③效率較高的的非線性查找找 ④效率較高的的線性查找答案：A＝④B＝②C＝④D＝①E＝③8.從供選擇的的答案中，選選出應(yīng)填入下下面敘述？?jī)?nèi)的最確切切的解答，把把相應(yīng)編號(hào)寫寫在答卷的對(duì)對(duì)應(yīng)欄內(nèi)。在二叉排序樹中中，每個(gè)結(jié)點(diǎn)點(diǎn)的關(guān)鍵碼值值A(chǔ)，B一棵二二叉排序，即即可得到排序序序列。同一一個(gè)結(jié)點(diǎn)集合合，可用不同同的二叉排序序樹表示，人人們把平均檢檢索長(zhǎng)度最短短的二叉排序序樹稱作最佳佳二叉排序，最最佳二叉排序序樹在結(jié)構(gòu)上上的特點(diǎn)是C。供選擇的答案A：①比左子子樹所有結(jié)點(diǎn)點(diǎn)的關(guān)鍵碼值值大，比右子子樹所有結(jié)點(diǎn)點(diǎn)的關(guān)鍵碼值值小②比左子樹所有有結(jié)點(diǎn)的關(guān)鍵鍵碼值小，比比右子樹所有有結(jié)點(diǎn)的關(guān)鍵鍵碼值大③比左右子樹樹的所有結(jié)點(diǎn)點(diǎn)的關(guān)鍵碼值值都大④與左子樹所所有結(jié)點(diǎn)的關(guān)關(guān)鍵碼值和右右子樹所有結(jié)結(jié)點(diǎn)的關(guān)鍵碼碼值無必然的的大小關(guān)系B:①前前序遍歷②中序（對(duì)對(duì)稱）遍歷③后序遍歷歷④④層次遍歷歷C：①除最下下二層可以不不滿外，其余余都是充滿的的②除最下一層層可以不滿外外，其余都是是充滿的③每個(gè)個(gè)結(jié)點(diǎn)的左右右子樹的高度度之差的絕對(duì)對(duì)值不大于11④最下層的的葉子必須在在最左邊答案：A＝①B＝②C＝②9.從供選擇擇的答案中，選選出應(yīng)填入下下面敘述？?jī)?nèi)的最確切切的解答，把把相應(yīng)編號(hào)寫寫在答卷的對(duì)對(duì)應(yīng)欄內(nèi)。散列法存儲(chǔ)的基基本思想是根根據(jù)A來決定定B，碰撞撞（沖突）指指的是CC，處理理碰撞的兩類類主要方法是是DD。供選擇的答案A，B：①存存儲(chǔ)地址②元素的符符號(hào)③元素個(gè)數(shù)數(shù)④關(guān)鍵碼值值⑤⑤非碼屬性性⑥⑥平均檢索索長(zhǎng)度⑦負(fù)載因子子⑧散列表空空間C:①兩兩個(gè)元素具有有相同序號(hào)②兩個(gè)元素素的關(guān)鍵碼值值不同，而非非碼屬性相同同③不同關(guān)鍵鍵碼值對(duì)應(yīng)到到相同的存儲(chǔ)儲(chǔ)地址④負(fù)載因子子過大⑤數(shù)據(jù)元素素過多D：①線性性探查法和雙雙散列函數(shù)法法②建溢出區(qū)區(qū)法和不建溢溢出區(qū)法③除余法和折折疊法 ④拉鏈法和和開地址法答案：A＝④BB＝①CC＝③D＝④10.考慮具有有如下性質(zhì)的的二叉樹：除除葉子結(jié)點(diǎn)外外，每個(gè)結(jié)點(diǎn)點(diǎn)的值都大于于其左子樹上上的一切結(jié)點(diǎn)點(diǎn)的值。并小小于等于其右右子樹上的一一切結(jié)點(diǎn)的值值。現(xiàn)把9個(gè)數(shù)1，22，3，…，8，9填填入右圖所示的二二叉樹的9個(gè)個(gè)結(jié)點(diǎn)中，并并使之具有上上述性質(zhì)。此此時(shí)，n1的的值是A，n22的值是B，nn9的值是C?，F(xiàn)欲把把放入此樹并并使該樹保持持前述性質(zhì)，增增加的一個(gè)結(jié)結(jié)點(diǎn)可以放在在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(zhuǎn)＝②E＝⑥三、簡(jiǎn)答題（每每小題4分，共共16分）1.對(duì)分（折半半）查找適不不適合鏈表結(jié)結(jié)構(gòu)的序列，為為什么？用二二分查找的查查找速度必然然比線性查找找的速度快，這這種說法對(duì)嗎嗎？答：不適合！雖雖然有序的單單鏈表的結(jié)點(diǎn)點(diǎn)是按從小到到大（或從大大到小）順序序排列，但因因其存儲(chǔ)結(jié)構(gòu)構(gòu)為單鏈表，查查找結(jié)點(diǎn)時(shí)只只能從頭指針針開始逐步搜搜索，故不能能進(jìn)行折半查查找。二分查找的速度度在一般情況況下是快些，但但在特殊情況況下未必快。例例如所查數(shù)據(jù)據(jù)位于首位時(shí)時(shí)，則線性查查找快；而二二分查找則慢慢得多。2.假定對(duì)有序序表：（3，44，5，7，224，30，442，54，663，72，887，95）進(jìn)進(jìn)行折半查找找，試回答下下列問題：畫出描述折半查查找過程的判判定樹；若查找元素544，需依次與與哪些元素比比較？若查找元素900，需依次與與哪些元素比比較？假定每個(gè)元素的的查找概率相相等，求查找找成功時(shí)的平平均查找長(zhǎng)度度。解：先畫出判定樹如如下（注：mmid=(11+12)//2=6）：305633774287424554722995(2)查找元元素54，需需依次與300,63,,42,54等元元素比較；(3)查找元元素90，需需依次與300,63,,87,995,722等元素比較較；（4）求ASSL之前，需需要統(tǒng)計(jì)每個(gè)個(gè)元素的查找找次數(shù)。判定定樹的前3層層共查找1＋＋2×2＋4×3=17次次；但最后一層未滿滿，不能用88×4，只能用用5×4=20次次，所以ASL＝11/12（117＋20）＝＝37/122≈3.083.用比較兩個(gè)個(gè)元素大小的的方法在一個(gè)個(gè)給定的序列列中查找某個(gè)個(gè)元素的時(shí)間間復(fù)雜度下限限是什么?如果要求時(shí)時(shí)間復(fù)雜度更更小,你采用用什么方法？？此方法的時(shí)時(shí)間復(fù)雜度是是多少?答：查找某個(gè)元元素的時(shí)間復(fù)復(fù)雜度下限，如如果理解為最最短查找時(shí)間間，則當(dāng)關(guān)鍵鍵字值與表頭頭元素相同時(shí)時(shí)，比較1次次即可。要想想降低時(shí)間復(fù)復(fù)雜度，可以以改用Hassh查找法。此此方法對(duì)表內(nèi)內(nèi)每個(gè)元素的的比較次數(shù)都都是O（1）。4.設(shè)哈希（HHash）表表的地址范圍圍為0～177，哈希函數(shù)數(shù)為：H（KK）＝KMOD16。K為關(guān)鍵字，用用線性探測(cè)法法再散列法處處理沖突，輸輸入關(guān)鍵字序序列：（10，224，32，117，31，330，46，447，40，663，49）造出Hash表表，試回答下下列問題：畫出哈希表的示示意圖；若查找關(guān)鍵字663，需要依依次與哪些關(guān)關(guān)鍵字進(jìn)行比比較？若查找關(guān)鍵字660，需要依依次與哪些關(guān)關(guān)鍵字比較？？假定每個(gè)關(guān)鍵字字的查找概率率相等，求查查找成功時(shí)的的平均查找長(zhǎng)長(zhǎng)度。解：（1）畫畫表如下：012345678910111213141516173217634924401030314647（2）查找663,首先要要與H(633)=63%%16=155號(hào)單元內(nèi)容容比較，即663vs31,noo;然后順移，與446,47,,32,177,63相比比，一共比較較了6次?。?）查找600,首先要與與H(60)=60%16=112號(hào)單元內(nèi)內(nèi)容比較，但但因?yàn)?2號(hào)號(hào)單元為空（應(yīng)應(yīng)當(dāng)有空標(biāo)記記），所以應(yīng)應(yīng)當(dāng)只比較這這一次即可。（4）對(duì)于黑黑色數(shù)據(jù)元素素，各比較11次；共6次次；對(duì)紅色元素則各各不相同，要要統(tǒng)計(jì)移位的的位數(shù)。“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.畫出對(duì)對(duì)長(zhǎng)度為100的有序表進(jìn)進(jìn)行折半查找找的判定樹，并并求其等概率率時(shí)查找成功功的平均查找找長(zhǎng)度。解：判定樹應(yīng)當(dāng)當(dāng)描述每次查查找的位置：：58136944771102.在一棵空的的二叉查找樹樹中依次插入入關(guān)鍵字序列列為12，77