管理信息化大數(shù)據(jù)分析華東交大數(shù)據(jù)結(jié)構(gòu)自測(cè)卷及答案

管理信息化大數(shù)據(jù)分析華東交大數(shù)據(jù)結(jié)構(gòu)自測(cè)卷及答案第一章緒論一、填空題1.算法的計(jì)算量的大小稱為計(jì)算的（BA．效率B.復(fù)雜性C.現(xiàn)實(shí)性D.難度2.算法的時(shí)間復(fù)雜度取決于（C）A．問(wèn)題的規(guī)模B.待處理數(shù)據(jù)的初態(tài)C.A和B3.計(jì)算機(jī)算法指的是（CB）這三個(gè)特性。(1)A．計(jì)算方法B.排序方法C.解決問(wèn)題的步驟序列D.調(diào)度方法(2)A．可執(zhí)行性、可移植性、可擴(kuò)充性B.可執(zhí)行性、確定性、有窮性C.確定性、有窮性、穩(wěn)定性D.易讀性、穩(wěn)定性、安全性4．從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（C）兩大類。A．動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B．順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)C．線性結(jié)構(gòu)、非線性結(jié)構(gòu)D．初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)5．以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)的術(shù)語(yǔ)是（DA．循環(huán)隊(duì)列B.鏈表C.哈希表D.棧6．以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)不是線性結(jié)構(gòu)（B）？A．廣義表B.二叉樹(shù)C.稀疏矩陣D.串7．以下那一個(gè)術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)？（A）A．棧B.哈希表C.線索樹(shù)D.雙向鏈表8．在下面的程序段中，對(duì)x的賦值語(yǔ)句的頻度為（C）FORi:=1TOnDOFORj:=1TOnDOx:=x+1;A．O(2n)B．O(n)C．O(n2)D．O(log2n)9．程序段FORi:=n-1DOWNTO1DOFORj:=1TOiDOIFA[j]>A[j+1]THENA[j]與A[j+1]對(duì)換；其中n為正整數(shù)，則最后一行的語(yǔ)句頻度在最壞情況下是（D）A.O（n）B.O(nlogn)C.O(n3)D.O(n2)10．以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)不是多型數(shù)據(jù)類型（D）A．棧B．廣義表C．有向圖D．字符串11A）是非線性數(shù)據(jù)結(jié)構(gòu)A．樹(shù)B．字符串C．隊(duì)D．棧12.C）是非線性數(shù)據(jù)結(jié)構(gòu)。A．棧B.隊(duì)列C.完全二叉樹(shù)D.堆13．連續(xù)存儲(chǔ)設(shè)計(jì)時(shí)，存儲(chǔ)單元的地址（AA．一定連續(xù)B．一定不連續(xù)C．不一定連續(xù)D．部分連續(xù)，部分不連續(xù)14．以下屬于邏輯結(jié)構(gòu)的是（CA．順序表B.哈希表C.有序表D.單鏈表二、判斷題1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。(F)2.記錄是數(shù)據(jù)處理的最小單位。(T)3.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系；(F)4．算法的優(yōu)劣與算法描述語(yǔ)言無(wú)關(guān)，但與所用計(jì)算機(jī)有關(guān)。(F)5．健壯的算法不會(huì)因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。(T)6C語(yǔ)言或PASCAL際上就是程序了。(T)7．程序一定是算法。(T)8．?dāng)?shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲(chǔ)形式。(T)9.數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實(shí)現(xiàn)有關(guān)。(F)10.在順序存儲(chǔ)結(jié)構(gòu)中，有時(shí)也存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。(F)11.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。(F)12.數(shù)據(jù)結(jié)構(gòu)的基本操作的設(shè)置的最重要的準(zhǔn)則是，實(shí)現(xiàn)應(yīng)用程序與存儲(chǔ)結(jié)構(gòu)的獨(dú)立。(T)13.數(shù)據(jù)的邏輯結(jié)構(gòu)說(shuō)明數(shù)據(jù)元素之間的順序關(guān)系,它依賴于計(jì)算機(jī)的儲(chǔ)存結(jié)構(gòu).(F)三、填空1．?dāng)?shù)據(jù)的物理結(jié)構(gòu)包括數(shù)據(jù)元素的表示和數(shù)據(jù)關(guān)系的表示。2.對(duì)于給定的n個(gè)元素,可以構(gòu)造出的邏輯結(jié)構(gòu)有集合，線性，樹(shù)，__圖（網(wǎng)）

_四種。3．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系。4．一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中表示稱為存儲(chǔ)結(jié)構(gòu)。5．抽象數(shù)據(jù)類型的定義僅取決于它的一組__邏輯特性_，而與_其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)__數(shù)學(xué)特性_6．?dāng)?shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是時(shí)間復(fù)雜度和空間復(fù)雜度7.數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的_邏輯結(jié)構(gòu)_和_物理結(jié)構(gòu)_結(jié)構(gòu)定義相應(yīng)的_操作_，設(shè)計(jì)出相應(yīng)的算法_。8．一個(gè)算法具有5個(gè)特性:有窮性、確定性、可行性，有零個(gè)或多個(gè)輸入、有一個(gè)或多個(gè)輸出。9．已知如下程序段for(i=n;i>=1;i--){語(yǔ)句1}{x=x+1；{語(yǔ)句2}for(j=n;j>i;j--){語(yǔ)句3}y=y+1;{語(yǔ)句4}}；語(yǔ)句1執(zhí)行的頻度為n+1；語(yǔ)句2執(zhí)行的頻度為n；語(yǔ)句3執(zhí)行的頻度為n（n+1）/2；語(yǔ)句4執(zhí)行的頻度為(n-1)n/2。10．在下面的程序段中，對(duì)ｘ的賦值語(yǔ)句的頻度為(n3+3n2+2n)/6_____（表示為n的函數(shù)）for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)ｘ：＝ｘ＋delta；11.下面程序段中帶下劃線的語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)是：log2ni=1;while(i<n)i=i*2;12.下面程序段中帶下劃線的語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)是(nlog2n)。i=1;while(i<n){for(j=1;j<=n;j++)x=x+1;i=i*2}13.下面程序段中帶有下劃線的語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)是(log2n)i=n*nwhile(i!=1)i=i/2;14.計(jì)算機(jī)執(zhí)行下面的語(yǔ)句時(shí)，語(yǔ)句s的執(zhí)行次數(shù)為_(kāi)_(n+3)(n-2)/2_____。for(i=l；i<n-l；i++)for(j=n;j>=i;j--)s;15.下面程序段的時(shí)間復(fù)雜度為_(kāi)_n1/2______。(n>1)sum=1；for(i=0;sum<n;i++)sum+=i;四、應(yīng)用題1并指出它們分別屬于何種結(jié)構(gòu)。（注意：<>表示有方向，（）表示無(wú)方向）（1）、A=（K，R），其中：K={a,b,c,d,e,,f,g,h}R={r}r={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g.h>}（2）、B=（K，R），其中：K={a,b,c,d,e,f,g,h}R={r}r={<d,b>，<d,g>,<d,a>,<b,c>,<g,e>,<g,h>,<e.f>}（3）、C=(K,R),其中:K={1,2,3,4,5,6},R={r}r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}線性表、棧和隊(duì)列測(cè)試題姓名班級(jí)學(xué)號(hào)一、選擇題（共25分）（B）1、下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？A．線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。B．線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C．線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。D．線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。（A2、若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（）存儲(chǔ)方式最節(jié)省時(shí)間。A．順序表B．雙鏈表C．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D．單循環(huán)鏈表（C3、若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（）(1<=i<=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)（B）4、在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是：A．p->next=s;s->next=p->next;B．s->next=p->next;p->next=s;C．p->next=s;p->next=s->next;D．p->next=s->next;p->next=s;（B）5、對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是（）A．head==NULLB．head->next==NULLC．head->next==headD．head->NULL（B）6.棧中元素的進(jìn)出原則是A．先進(jìn)先出B.后進(jìn)先出C?？談t進(jìn)D棧滿則出（C）7.若已知一個(gè)棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為Ａ．iＢ．n=iＣ．n-i+1Ｄ．不確定（B）8.判定一個(gè)棧ST（最多元素為m0）為空的條件是Ａ．ST->top<>0Ｂ．ST->top=0Ｃ．ST->top<>m0Ｄ．ST->top=m0（A）9.判定一個(gè)隊(duì)列QU（最多元素為m0）為滿隊(duì)列的條件是Ａ．QU->rear－QU->front==m0Ｂ．QU->rear－QU->front－1==m0Ｃ．QU->front==QU->rearＤ．QU->front==QU->rear+1（D）10．?dāng)?shù)組Ｑ［ｎ］用來(lái)表示一個(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ù)元素a1a2a3和a4?；蜻M(jìn)隊(duì)操作時(shí)，按a1、a2、a3、a4次序每次進(jìn)入一個(gè)元素。假設(shè)棧或隊(duì)的初始狀態(tài)都是空?，F(xiàn)要進(jìn)行的棧操作是進(jìn)棧兩次，出棧一次，再進(jìn)棧兩次，出棧一次；這時(shí)，第一次出棧得到的元素是②，第二次出棧得到的元素是④；類似地，考慮對(duì)這四個(gè)數(shù)據(jù)元素進(jìn)行的隊(duì)操作是進(jìn)隊(duì)兩次，出隊(duì)一次，再進(jìn)隊(duì)兩次，出隊(duì)一次；這時(shí)，第一次出隊(duì)得到的元素是①，第二次出隊(duì)得到的元素是②。經(jīng)操作后，最后在棧中或隊(duì)中的元素還有②個(gè)。供選擇的答案：A～D：①a1②a2③a3④a4E：①1②2③3④0答：A、B、C、D、E分別為、、、、12.棧是一種線性表，它的特點(diǎn)是A。設(shè)用一維數(shù)組A[1,…,n]來(lái)表示一個(gè)棧，A[n]為棧底，用整型變量T指示當(dāng)前棧頂位置，A[T]為棧頂元素。往棧中推入（PUSH）一個(gè)新元素時(shí)，變量T的值B；從棧中彈出（POP）一個(gè)元素時(shí)，變量T的值C。設(shè)棧空時(shí)，有輸入序列a，b，c，經(jīng)過(guò)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、C、D、E分別為②、②、①、⑥、④13.在做進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否A；在做退棧運(yùn)算時(shí)，應(yīng)先判別棧是否B。當(dāng)棧中元素為n個(gè)，做進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說(shuō)明該棧的最大容量為C。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí)，應(yīng)將兩棧的D分別設(shè)在這片內(nèi)存空間的兩端，這樣，只有當(dāng)E時(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á)?？臻g的中心點(diǎn)③兩個(gè)棧的棧頂在?？臻g的某一位置相遇④兩個(gè)棧均不空，且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底答：A、B、C、D、E分別為②、①、②、④、③二、判斷題（共10分）（F）1.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。（F）2.在表結(jié)構(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)。（F）6.棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。（T）7.棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。（T）8.兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。（F）9.隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。（F）10.一個(gè)棧的輸入序列是12345，則棧的輸出序列不可能是12345。三、填空題（共20分）1.線性表、棧和隊(duì)列都是線性結(jié)構(gòu)，可以在線性表的任意位置插入和刪除元素；對(duì)于棧只能在棧頂插入和刪除元素；對(duì)于隊(duì)列只能在隊(duì)尾插入和隊(duì)頭刪除元素。2.棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為棧頂。不允許插入和刪除運(yùn)算的一端稱為棧底。3.隊(duì)列是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。4.在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的當(dāng)前位置。5.在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有n-1個(gè)元素。6.向棧中壓入元素的操作是先插入數(shù)據(jù)，后移動(dòng)指針。7.從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是先讀取元素，后移動(dòng)指針。8.帶表頭結(jié)點(diǎn)的空循環(huán)雙向鏈表的長(zhǎng)度等于0。9．表達(dá)式23+((12*3-2)/4+34*5/7)+108/9的后綴表達(dá)式是__23123*2-4/345*7/++1089/+_____10LP結(jié)點(diǎn)既不是首元素結(jié)點(diǎn)，也不是尾元素結(jié)點(diǎn)。按要求從下列語(yǔ)句中選擇合適的語(yǔ)句序列。a.在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語(yǔ)句序列是：(4)(1)。b.在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語(yǔ)句序列是：711841。c.在表首插入S結(jié)點(diǎn)的語(yǔ)句序列是：512。d.在表尾插入S結(jié)點(diǎn)的語(yǔ)句序列是：916。供選擇的語(yǔ)句有：（1）P->next=S;（2）P->next=P->next->next;（3）P->next=S->next;（4）S->next=P->next;（5）S->next=L;（6）S->next=NULL;（7）Q=P;（8）while(P->next!=Q)P=P->next;（9）while(P->next!=NULL)P=P->next;（10）P=Q;（11）P=L;（12）L=S;（13）L=P;四、簡(jiǎn)答題(共15分)1、說(shuō)明線性表、棧與隊(duì)的異同點(diǎn)。2、順序隊(duì)的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊(duì)列是空還是滿？3、設(shè)循環(huán)隊(duì)列的容量為40（序號(hào)從0到39算后，有①front=11，rear=19;②front=19，rear=11；問(wèn)在這兩種情況下，循環(huán)隊(duì)列中各有元素多少個(gè)？五、算法設(shè)計(jì)（共30分）1、寫(xiě)一算法，從順序表中刪除自第i個(gè)元素開(kāi)始的k個(gè)元素。StatusDelete_k(SqlistL,inti,intk){if(i<0||i>L.length||i+k>L.length)returnerror;for(intj=i+k;j<L.length;j++){L.elem[j-k]=L.elem[j];}L.length-=k;returnOK;}2、試寫(xiě)一個(gè)算法，判別讀入的一個(gè)以為結(jié)束符的字符序列是否是“回文。（正讀和反讀都相同的字符序列為“回文‘a(chǎn)bba’‘a(chǎn)bcba’是回文，‘a(chǎn)bcde’和‘a(chǎn)babab’StatusHuiWen(chars[]){inti=0;SqStackS;InitStack(S);while(s[i]!='@'){Push(S,s[i]);cout<<"push"<<s[i];i++;}i=0;while(s[i]!='@'){chare;Pop(S,e);cout<<e<<"*"<<s[i];if(e!=s[i])break;i++;}if(s[i]=='@')return1;//返回結(jié)果1表示是回文，0表示不是回文elsereturn0;}3、假設(shè)有一個(gè)循環(huán)鏈表的長(zhǎng)度大于1s為s所指結(jié)點(diǎn)的前趨結(jié)點(diǎn)。StatusDelete(LinkLists){p=s;while(p->next->next!=s)//查找s的前一個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)；p=p->next;q=p->next;p->next=s;deleteq;returnOK;}第6章樹(shù)和圖自測(cè)卷姓名班級(jí)學(xué)號(hào)題號(hào)一二三四五總分題分1017174016100得分一、下面是有關(guān)二叉樹(shù)的敘述，請(qǐng)判斷正誤（每小題1分，共10分）（）1.若二叉樹(shù)用二叉鏈表作存貯結(jié)構(gòu)，則在n個(gè)結(jié)點(diǎn)的二叉樹(shù)鏈表中只有n—1個(gè)非空指針域。（）2.二叉樹(shù)中每個(gè)結(jié)點(diǎn)的兩棵子樹(shù)的高度差等于1。（）3.二叉樹(shù)中每個(gè)結(jié)點(diǎn)的兩棵子樹(shù)是有序的。（）4.二叉樹(shù)中每個(gè)結(jié)點(diǎn)有兩棵非空子樹(shù)或有兩棵空子樹(shù)。（）5.二叉樹(shù)中所有結(jié)點(diǎn)個(gè)數(shù)是2k-1-1，其中k是樹(shù)的深度。（）6.對(duì)于一棵非空二叉樹(shù)，它的根結(jié)點(diǎn)作為第一層，則它的第i層上最多能有2i－1個(gè)結(jié)點(diǎn)。（）7.具有12個(gè)結(jié)點(diǎn)的完全二叉樹(shù)有5個(gè)度為2的結(jié)點(diǎn)。（）8.不同的求最小生成樹(shù)的方法最后得到的生成樹(shù)是相同的.9.有n個(gè)頂點(diǎn)的無(wú)向圖,采用鄰接矩陣表示,圖中的邊數(shù)等于鄰接矩陣中非零元素之和的一半。（）10.無(wú)向圖的鄰接矩陣一定是對(duì)稱矩陣，有向圖的鄰接矩陣一定是非對(duì)稱矩陣。二、填空（每空1分，共17分）1．由３個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹(shù)有種形態(tài)。2.一棵深度為6的滿二叉樹(shù)有個(gè)分支結(jié)點(diǎn)和個(gè)葉子。3．一棵具有257個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，它的深度為。4．設(shè)一棵完全二叉樹(shù)有700個(gè)結(jié)點(diǎn)，則共有個(gè)葉子結(jié)點(diǎn)。5.用5個(gè)權(quán)值{3,2,4,5,1}構(gòu)造的哈夫曼（Huffman）樹(shù)的帶權(quán)路徑長(zhǎng)度是。6.判斷一個(gè)無(wú)向圖是一棵樹(shù)的條件是______。7.在有n個(gè)頂點(diǎn)的有向圖中，若要使任意兩點(diǎn)間可以互相到達(dá)，則至少需要______條弧。8.G是一個(gè)非連通無(wú)向圖，共有28條邊，則該圖至少有______個(gè)頂點(diǎn)9.N個(gè)頂點(diǎn)的連通圖用鄰接矩陣表示時(shí),該矩陣至少有_______個(gè)非零元素。10．在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)______。11．設(shè)有一稀疏圖G，則G采用存儲(chǔ)較省空間。12．設(shè)有一稠密圖G，則G采用存儲(chǔ)較省空間。13．n個(gè)頂點(diǎn)e條邊的圖采用鄰接矩陣存儲(chǔ)，深度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為；若采用鄰接表存儲(chǔ)時(shí)，該算法的時(shí)間復(fù)雜度為。140出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是。則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是。三、選擇題（每小題1分，共17分）（）1．不含任何結(jié)點(diǎn)的空樹(shù)。（Ａ）是一棵樹(shù);（Ｂ）是一棵二叉樹(shù);（Ｃ）是一棵樹(shù)也是一棵二叉樹(shù);（Ｄ）既不是樹(shù)也不是二叉樹(shù)（）2．二叉樹(shù)是非線性數(shù)據(jù)結(jié)構(gòu)，所以。（Ａ）它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ);（Ｂ）它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ);（Ｃ）順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ);（Ｄ）順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用（）3.具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為。(Ａ)log2(n)(Ｂ)log2(n)(Ｃ)log2(n)+1(Ｄ)log2(n)+1（）4．把一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)后，這棵二叉樹(shù)的形態(tài)是。（Ａ）唯一的（Ｂ）有多種（Ｃ）有多種，但根結(jié)點(diǎn)都沒(méi)有左孩子（Ｄ）有多種，但根結(jié)點(diǎn)都沒(méi)有右孩子（）5.在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的倍。A．1/2B.1C.2D.4（）7.在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的倍。A．1/2B.1C.2D.4（）8.用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常是采用來(lái)實(shí)現(xiàn)算法的。A．棧B.隊(duì)列C.樹(shù)D.圖（）9.深度優(yōu)先遍歷類似于二叉樹(shù)的A．先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷（）10.廣度優(yōu)先遍歷類似于二叉樹(shù)的A．先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷11.樹(shù)是結(jié)點(diǎn)的有限集合，它A根結(jié)點(diǎn)，記為T(mén)。其余的結(jié)點(diǎn)分成為m（m≥0）個(gè)B的集合T1，T2，…，Tm，每個(gè)集合又都是樹(shù)，此時(shí)結(jié)點(diǎn)T稱為T(mén)i的父結(jié)點(diǎn)，Ti稱為T(mén)的子結(jié)點(diǎn)（1≤i≤mC。供選擇的答案A：①有0個(gè)或1個(gè)②有0個(gè)或多個(gè)③有且只有1個(gè)④有1個(gè)或1個(gè)以上B:①互不相交②允許相交③允許葉結(jié)點(diǎn)相交④允許樹(shù)枝結(jié)點(diǎn)相交C：①權(quán)②維數(shù)③次數(shù)④序答案：A=B=C=12.二叉樹(shù)A。在完全的二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)沒(méi)有B，則它必定是葉結(jié)點(diǎn)。每棵樹(shù)N的左子女是N在原樹(shù)里對(duì)應(yīng)結(jié)點(diǎn)的C，而N的右子女是它在原樹(shù)里對(duì)應(yīng)結(jié)點(diǎn)的D。供選擇的答案A：①是特殊的樹(shù)②不是樹(shù)的特殊形式③是兩棵樹(shù)的總稱④有是只有二個(gè)根結(jié)點(diǎn)的樹(shù)形結(jié)構(gòu)B:①左子結(jié)點(diǎn)②右子結(jié)點(diǎn)③左子結(jié)點(diǎn)或者沒(méi)有右子結(jié)點(diǎn)④兄弟C～D：①最左子結(jié)點(diǎn)②最右子結(jié)點(diǎn)③最鄰近的右兄弟④最鄰近的左兄弟⑤最左的兄弟⑥最右的兄弟答案：A=B=C=D＝四、閱讀分析題（每題5分，共40分）1.給定二叉樹(shù)的兩種遍歷序列，分別是：前序遍歷序列：D，A，C，E，B，H，F(xiàn)，G，I；中序遍歷序列：D，C，B，E，H，A，G，I，F(xiàn)，試畫(huà)該出二叉樹(shù)2．試寫(xiě)出如圖1所示的二叉樹(shù)分別按先序、中序、后序遍歷時(shí)得到的結(jié)點(diǎn)序列。3.把如圖2所示的樹(shù)轉(zhuǎn)化成二叉樹(shù)。4.畫(huà)出圖3二叉樹(shù)相應(yīng)的森林。5．.已知如圖所示的有向圖，請(qǐng)給出該圖的:（1）每個(gè)頂點(diǎn)的入/出度；（2）鄰接矩陣；（3）鄰接表；（4）逆鄰接表。6．請(qǐng)對(duì)下圖的無(wú)向帶權(quán)圖：（1）寫(xiě)出它的鄰接矩陣，并按普里姆算法求其最小生成樹(shù)；（2）寫(xiě)出它的鄰接表，并按克魯斯卡爾算法求其最小生成樹(shù)。7．已知二維數(shù)組表示的圖的鄰接矩陣如下圖所示。試分別畫(huà)出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)。8．給定下列網(wǎng)G:（10分）1試著找出網(wǎng)G的最小生成樹(shù)，畫(huà)出其邏輯結(jié)構(gòu)圖；2用兩種不同的表示法畫(huà)出網(wǎng)G的存儲(chǔ)結(jié)構(gòu)圖；3用C語(yǔ)言（或其他算法語(yǔ)言）定義其中一種表示法（存儲(chǔ)結(jié)構(gòu)）的數(shù)據(jù)類型。五、算法設(shè)計(jì)題（前1~5題中任選2題，第6~7題中任選1題，共16分）1.編寫(xiě)遞歸算法，計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目。2.寫(xiě)出求二叉樹(shù)深度的算法，先定義二叉樹(shù)的抽象數(shù)據(jù)類型。3．編寫(xiě)遞歸算法，求二叉樹(shù)中以元素值為x的結(jié)點(diǎn)為根的子樹(shù)的深度。4.編寫(xiě)按層次順序（同一層自左至右）遍歷二叉樹(shù)的算法。5.編寫(xiě)算法判別給定二叉樹(shù)是否為完全二叉樹(shù)。6．編寫(xiě)算法，由依次輸入的頂點(diǎn)數(shù)目、弧的數(shù)目、各頂點(diǎn)的信息和各條弧的信息建立有向圖的鄰接表。解：StatusBuild_AdjList(ALGraph&G)//輸入有向圖的頂點(diǎn)數(shù),邊數(shù),頂點(diǎn)信息和邊的信息，以建立鄰接表{returnOK;}//Build_AdjList7.試在鄰接矩陣存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)圖的基本操作：DeleteArc(G,v,w)，即刪除一條邊的操作。（如果要?jiǎng)h除所有從第i個(gè)頂點(diǎn)出發(fā)的邊呢？提示：將鄰接矩陣的第i行全部置0）解：//設(shè)本題中的圖G為有向無(wú)權(quán)圖StatusDeleteArc(MGraph&G,charv,charw)//在鄰接矩陣表示的圖G上刪除邊(v,w){}returnOK;}//Delete_Arc答案：一、12345678910√×××××√×√×二、156n個(gè)頂點(diǎn)n-1條邊的連通圖11鄰接表231,327n12鄰接矩陣398913O(n2)O(n+e)435092(n-1)14533102*(n-1)15三、四、1、答：前序遍歷序列：D，A，C，E，B，H，F(xiàn)，G，I；中序遍歷序列：D，C，B，E，H，A，G，I，F(xiàn)，試畫(huà)出二叉樹(shù)B，并簡(jiǎn)述由任意二叉樹(shù)B的前序遍歷序列和中序遍歷序列求二叉樹(shù)B的思想方法。解：方法是：由前序先確定root，由中序可確定root的左、右子樹(shù)。然后由其左子樹(shù)的元素集合和右子樹(shù)的集合對(duì)應(yīng)前序遍歷序列中的元素集合，可繼續(xù)確定root的左右孩子。將他們分別作為新的root，不斷遞歸，則所有元素都將被唯一確定，問(wèn)題得解。2、答：DLR：ABDFJGKCEHILMLDR:BFJDGKACHELIMLRD：JFKGDBHLMIECA3、答：注意全部兄弟之間都要連線（包括度為2的兄弟）,并注意原有連線結(jié)點(diǎn)一律歸入左子樹(shù)，新添連線結(jié)點(diǎn)一律歸入右子樹(shù)。4、答：注意根右邊的子樹(shù)肯定是森林，而孩子結(jié)點(diǎn)的右子樹(shù)均為兄弟。五、1、5、(1)

（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→46、解：設(shè)起點(diǎn)為a?？梢灾苯佑稍紙D畫(huà)出最小生成樹(shù)，而且最小生成樹(shù)只有一種（類）!鄰接矩陣為：043405593505555076549703630252065460PRIM算法（橫向變化）：VbcdefghUV-UVexaaaaaaa{a}{b,c,d,e,f,lowcos43∞∞∞∞∞g,h}tVexa0caaac{a,c}{b,d,e,f,g,lowcos45∞∞∞5h}tVex00cbaac{a,c,b}{d,e,f,g,h}lowcos59∞∞5tVex000dddd{a,c,b,d}{e,f,g,h}lowcos7654tVex000ddd0{a,c,b,d,{e,f,g}lowcos765h}tVex000dg00{a,c,b,d,{f,e}lowcos72h,g}tVex000f000{a,c,b,d,{e}lowcos3h,g,f}tVex0000000{a,c,b,d,{}lowcosh,g,f,e}t鄰接表為：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^先羅列：f---2---ga—3--cf—3—ea—4---bd—4—h(a,b,c)(e,f,g)(d,h)取b—5—d,g—5--d就把三個(gè)連通分量連接起來(lái)了。7、8、1試著找出網(wǎng)G的最小生成樹(shù)，畫(huà)出其邏輯結(jié)構(gòu)圖；2用兩種不同的表示法畫(huà)出網(wǎng)G的存儲(chǔ)結(jié)構(gòu)圖；3用C語(yǔ)言（或其他算法語(yǔ)言）定義其中一種表示法（存儲(chǔ)結(jié)構(gòu)）的數(shù)據(jù)類型。解：1.最小生成樹(shù)可直接畫(huà)出，如右圖所示。AB———————C2.可用鄰接矩陣和鄰接表來(lái)描述：鄰接表為：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、intLeafCount_BiTree(BitreeT)//求二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目{if(!T)return0;//空樹(shù)沒(méi)有葉子elseif(!T->lchild&&!T->rchild)return1;//葉子結(jié)點(diǎn)elsereturnLeaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子樹(shù)的葉子數(shù)加上右子樹(shù)的葉子數(shù)}//LeafCount_BiTree2、intGet_Depth(BitreeT)//求子樹(shù)深度的遞歸算法{if(!T)return0;else{m=Get_Depth(T->lchild);n=Get_Depth(T->rchild);return(m>n?m:n)+1;}}//Get_Depth3、intGet_Sub_Depth(BitreeT,intx)//求二叉樹(shù)中以值為x的結(jié)點(diǎn)為根的子樹(shù)深度{if(T->data==x){printf("%d\n",Get_Depth(T));//找到了值為x的結(jié)點(diǎn),求其深度exit1;}}else{if(T->lchild)Get_Sub_Depth(T->lchild,x);if(T->rchild)Get_Sub_Depth(T->rchild,x);//在左右子樹(shù)中繼續(xù)尋找}}//Get_Sub_Depth4、voidLayerOrder(BitreeT)//層序遍歷二叉樹(shù){InitQueue(Q);//建立工作隊(duì)列EnQueue(Q,T);while(!QueueEmpty(Q)){DeQueue(Q,p);visit(p);if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);}}//LayerOrder5、答：intIsFull_Bitree(BitreeT)//判斷二叉樹(shù)是否完全二叉樹(shù),是則返回1,否則返回0{InitQueue(Q);

flag=0;EnQueue(Q,T);//建立工作隊(duì)列while(!QueueEmpty(Q)){{DeQueue(Q,p);if(!p)flag=1;elseif(flag)return0;else

{EnQueue(Q,p->lchild);EnQueue(Q,p->rchild);//不管孩子是否為空,都入隊(duì)列}}//whilereturn1;}//IsFull_Bitree分析:該問(wèn)題可以通過(guò)層序遍歷的方法來(lái)解決.與6.47相比,作了一個(gè)修改,不管當(dāng)前結(jié)點(diǎn)是否有左右孩子,都入隊(duì)列.這樣當(dāng)樹(shù)為完全二叉樹(shù)時(shí),遍歷時(shí)得到是一個(gè)連續(xù)的不包含空指針的序列.反之,則序列中會(huì)含有空指針.6、StatusBuild_AdjList(ALGraph&G)//輸入有向圖的頂點(diǎn)數(shù),邊數(shù),頂點(diǎn)信息和邊的信息建立鄰接表{InitALGraph(G);scanf("%d",&v);if(v<0)returnERROR;//頂點(diǎn)數(shù)不能為負(fù)G.vexnum=v;scanf("%d",&a);if(a<0)returnERROR;//邊數(shù)不能為負(fù)G.arcnum=a;for(m=0;m<v;m++)G.vertices[m].data=getchar();//輸入各頂點(diǎn)的符號(hào)for(m=1;m<=a;m++){t=getchar();h=getchar();//t為弧尾,h為弧頭if((i=LocateVex(G,t))<0)returnERROR;if((j=LocateVex(G,h))<0)returnERROR;//頂點(diǎn)未找到p=(ArcNode*)malloc(sizeof(ArcNode));if(!G.vertices.[i].firstarc)G.vertices[i].firstarc=p;else{for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc);q->nextarc=p;

}p->adjvex=j;p->nextarc=NULL;}//whilereturnOK;}//Build_AdjList7、解：//本題中的圖G均為有向無(wú)權(quán)圖。StatusDelete_Arc(MGraph&G,charv,charw)//在鄰接矩陣表示的圖G上刪除邊(v,w){if((i=LocateVex(G,v))<0)returnERROR;if((j=LocateVex(G,w))<0)returnERROR;if(G.arcs[i][j].adj){G.arcs[i][j].adj=0;G.arcnum--;}returnOK;}//Delete_Arc第9章查找自測(cè)卷答案姓名班級(jí)A題號(hào)一二三四五總分題分1027162423100得分一、填空題（每空1分，共10分）1.在數(shù)據(jù)的存放無(wú)規(guī)律而言的線性表中進(jìn)行檢索的最佳方法是順序查找（線性查找）。2.a1a2a3a256)k表中與k相等的元素，在查找不成功的情況下，最多需要檢索8次。設(shè)有100個(gè)結(jié)點(diǎn)，用二分法查找時(shí)，最大比較次數(shù)是7。3.假設(shè)在有序線性表a[20]上進(jìn)行折半查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為1；比較兩次查找成功的結(jié)點(diǎn)數(shù)為2；比較四次查找成功的結(jié)點(diǎn)數(shù)為8；平均查找長(zhǎng)度為3.7。解：顯然，平均查找長(zhǎng)度＝O（log2n）<5次（25來(lái)計(jì)算（即（21×log221/20＝4.6n＝2m-1的情況下推導(dǎo)出來(lái)的公式。應(yīng)當(dāng)用窮舉法羅列：全部元素的查找次數(shù)為＝（1＋2×2＋4×3＋8×4＋5×5）＝74；ASL＝74/20=3.7?。?！4．折半查找有序表（4，6，12，20，28，38，50，70，88，10020，它將依次與表中元素28，6，12，20比較大小。5.在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是散列查找。6.散列法存儲(chǔ)的基本思想是由關(guān)鍵字的值決定數(shù)據(jù)的存儲(chǔ)地址。7.有一個(gè)表長(zhǎng)為mn（n<m解決沖突的方法是用線性探測(cè)法。如果這n個(gè)關(guān)鍵碼的散列地址都相同，則探測(cè)的總次數(shù)是n(n-1)/2=（1＋2＋…＋n-1）。(而任一元素查找次數(shù)≤n-1)二、單項(xiàng)選擇題（每小題1分，共27分）（B）1．在表長(zhǎng)為ｎ的鏈表中進(jìn)行線性查找，它的平均查找長(zhǎng)度為Ａ.ＡＳＬ＝ｎ;Ｂ.ＡＳＬ＝（ｎ＋１）／２;Ｃ.ＡＳＬ＝＋１;Ｄ.ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１（A）2．折半查找有序表（4，6，10，12，20，30，50，70，88，10058，則它將依次與表中比較大小，查找結(jié)果是失敗。A．20，70，30，50B．30，88，70，50C．20，50D．30，88，50（C）3．對(duì)22個(gè)記錄的有序表作折半查找，當(dāng)查找失敗時(shí)，至少需要比較次關(guān)鍵字。A．3B．4C．5D．6（A）4.鏈表適用于查找A．順序B．二分法C．順序，也能二分法D．隨機(jī)（C）5.折半搜索與二叉搜索樹(shù)的時(shí)間性能A.相同B.完全不同C.有時(shí)不相同D.數(shù)量級(jí)都是O（log2n）6．從供選擇的答案中，選出應(yīng)填入下面敘述？?jī)?nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。要進(jìn)行線性查找，則線性表A；要進(jìn)行二分查找，則線性表B；要進(jìn)行散列查找，則線性表C。90000時(shí)，平均比較次數(shù)約為D，最大比較次數(shù)為E。供選擇的答案：A~C：①必須以順序方式存儲(chǔ)②必須以鏈表方式存儲(chǔ)③必須以散列方式存儲(chǔ)④既可以以順序方式，也可以以鏈表方式存儲(chǔ)⑤必須以順序方式存儲(chǔ)且數(shù)據(jù)元素已按值遞增或遞減的次序排好⑥必須以鏈表方式存儲(chǔ)且數(shù)據(jù)元素已按值遞增或遞減的次序排好D，E：①25000②30000③45000④90000答案：A=④B=⑤C=③D＝③E＝④7.從供選擇的答案中，選出應(yīng)填入下面敘述？?jī)?nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。數(shù)據(jù)結(jié)構(gòu)反映了數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系。鏈表是一種A，它對(duì)于數(shù)據(jù)元素的插入和刪除B。通常查找線性表數(shù)據(jù)元素的方法有C和D兩種方法，其中C是一種只適合于順序存儲(chǔ)結(jié)構(gòu)但E的方法；而D是一種對(duì)順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)均適用的方法。供選擇的答案：A：①順序存儲(chǔ)線性表②非順序存儲(chǔ)非線性表③順序存儲(chǔ)非線性表④非順序存儲(chǔ)線性表B：①不需要移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針②不需要移動(dòng)結(jié)點(diǎn)，只需改變結(jié)點(diǎn)指針③只需移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針④既需移動(dòng)結(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)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。在二叉排序樹(shù)中，每個(gè)結(jié)點(diǎn)的關(guān)鍵碼值A(chǔ)，B一棵二叉排序，即可得到排序序列。同

佳二叉排序，最佳二叉排序樹(shù)在結(jié)構(gòu)上的特點(diǎn)是C。供選擇的答案A：①比左子樹(shù)所有結(jié)點(diǎn)的關(guān)鍵碼值大，比右子樹(shù)所有結(jié)點(diǎn)的關(guān)鍵碼值?、诒茸笞訕?shù)所有結(jié)點(diǎn)的關(guān)鍵碼值小，比右子樹(shù)所有結(jié)點(diǎn)的關(guān)鍵碼值大③比左右子樹(shù)的所有結(jié)點(diǎn)的關(guān)鍵碼值都大④與左子樹(shù)所有結(jié)點(diǎn)的關(guān)鍵碼值和右子樹(shù)所有結(jié)點(diǎn)的關(guān)鍵碼值無(wú)必然的大小關(guān)系B:①前序遍歷②中序（對(duì)稱）遍歷③后序遍歷④層次遍歷C：①除最下二層可以不滿外，其余都是充滿的②除最下一層可以不滿外，其余都是充滿的③每個(gè)結(jié)點(diǎn)的左右子樹(shù)的高度之差的絕對(duì)值不大于1④最下層的葉子必須在最左邊

答案：A＝①B＝②C＝②9.從供選擇的答案中，選出應(yīng)填入下面敘述？?jī)?nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。散列法存儲(chǔ)的基本思想是根據(jù)A來(lái)決定B，碰撞（沖突）指的是C，處理碰撞的兩類主要方法是D。供選擇的答案A，B：①存儲(chǔ)地址②元素的符號(hào)③元素個(gè)數(shù)④關(guān)鍵碼值⑤非碼屬性⑥平均檢索長(zhǎng)度⑦負(fù)載因子⑧散列表空間C:①兩個(gè)元素具有相同序號(hào)②兩個(gè)元素的關(guān)鍵碼值不同，而非碼屬性相同③不同關(guān)鍵碼值對(duì)應(yīng)到相同的存儲(chǔ)地址④負(fù)載因子過(guò)大⑤數(shù)據(jù)元素過(guò)多D：①線性探查法和雙散列函數(shù)法②建溢出區(qū)法和不建溢出區(qū)法③除余法和折疊法④拉鏈法和開(kāi)地址法答案：A＝④B＝①C＝③D＝④10.考慮具有如下性質(zhì)的二叉樹(shù)：除葉子結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)的值都大于其左子樹(shù)上的一切結(jié)點(diǎn)的值。并小于等于其右子樹(shù)上的一切結(jié)點(diǎn)的值?，F(xiàn)把9個(gè)數(shù)123，…，89填入右圖所示的二叉樹(shù)的9此時(shí)，n1的值是A，n2的值是B，n9的值是C?，F(xiàn)欲把放入此樹(shù)并使該樹(shù)保持前述性質(zhì)，增加的一個(gè)結(jié)點(diǎn)可以放在D或E。供選擇的答案A～C：①1②2③3④4⑤5⑥6⑦7⑧8⑨9D～E：①n7下面②n8下面③n9下面④n6下面⑤n1與n2之間⑥n2與n4之間⑦n6與n9之間⑧n3與n6之間答案：A＝⑦B＝④C＝⑥D(zhuǎn)＝②E＝⑥三、簡(jiǎn)答題（每小題4分，共16分）1.對(duì)分（折半）查找適不適合鏈表結(jié)構(gòu)的序列，為什么？用二分查找的查找速度必然比線性查找的速度快，這種說(shuō)法對(duì)嗎？結(jié)構(gòu)為單鏈表，查找結(jié)點(diǎn)時(shí)只能從頭指針開(kāi)始逐步搜索，故不能進(jìn)行折半查找。二分查找的速度在一般情況下是快些，但在特殊情況下未必快。例如所查數(shù)據(jù)位于首位時(shí)，則線性查找快；而二分查找則慢得多。2.假定對(duì)有序表：（3，4，5，7，24，30，42，54，63，72，87，95答下列問(wèn)題：（1）畫(huà)出描述折半查找過(guò)程的判定樹(shù)；（2）若查找元素54，需依次與哪些元素比較？（3）若查找元素90，需依次與哪些元素比較？（4）假定每個(gè)元素的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。解：（1）先畫(huà)出判定樹(shù)如下（注：mid=(1+12)/2=6）：3056337428795(2)查找元素54，需依次與30,63,42,54等元素比較；(3)查找元素90，需依次與30,63,87,95,72等元素比較；（4）求ASL之前，需要統(tǒng)計(jì)每個(gè)元素的查找次數(shù)。判定樹(shù)的前3層共查找1＋2×2＋4×3=17次；但最后一層未滿，不能用8×4，只能用5×4=20次，所以ASL＝1/12（17＋20）＝37/12≈3.083.用比較兩個(gè)元素大小的方法在一個(gè)給定的序列中查找某個(gè)元素的時(shí)間復(fù)雜度下限是什么?如果要求時(shí)間復(fù)雜度更小,你采用什么方法？此方法的時(shí)間復(fù)雜度是多少?相同時(shí)，比較1次即可。要想降低時(shí)間復(fù)雜度，可以改用Hash查找法。此方法對(duì)表內(nèi)每個(gè)元素的比較次數(shù)都是O（14.設(shè)哈希（Hash）表的地址范圍為0～17，哈希函數(shù)為：H（K）＝KMOD16。K為關(guān)鍵字，用線性探測(cè)法再散列法處理沖突，輸入關(guān)鍵字序列：（10，24，32，17，31，30，46，47，40，63，49）造出Hash表，試回答下列問(wèn)題：（1）畫(huà)出哈希表的示意圖；（2）若查找關(guān)鍵字63，需要依次與哪些關(guān)鍵字進(jìn)行比較？（3）若查找關(guān)鍵字60，需要依次與哪些關(guān)鍵字比較？（4）假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。解：（1）畫(huà)表如下：012345678910111213141516173217634924401030314647（2）查找63,首先要與H(63)=63%16=15號(hào)單元內(nèi)容比較，即63vs31,no;然后順移，與46,47,32,17,63相比，一共比較了6次?。?60,首先要與H(60)=60%16=1212（4）對(duì)于黑色數(shù)據(jù)元素，各比較1次；共6次；對(duì)紅色元素則各不相同，要統(tǒng)計(jì)移位的位數(shù)?！?3”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11（6＋2＋3×3）＝17/11=1.454≈1.55四、分析題（每小題6分，共24分）1.畫(huà)出對(duì)長(zhǎng)度為10的有序表進(jìn)行折半查找的判定樹(shù)，并求其等概率時(shí)查找成功的平均查找長(zhǎng)度。解：判定樹(shù)應(yīng)當(dāng)描述每次查找的位置：528136947102.在一棵空的二叉查找樹(shù)中依次插入關(guān)鍵字序列為12，7，17，11，16，2，13，9，21，4，請(qǐng)畫(huà)出所得到的二叉查