數(shù)據(jù)結(jié)構(gòu)試卷期末試卷(2023年06級C)(信息)

數(shù)據(jù)結(jié)構(gòu)試題（C卷）學(xué)號：姓名：評分：.單項(xiàng)選擇題(30分)對二叉樹從1開始進(jìn)行連續(xù)編號，要求每個(gè)結(jié)點(diǎn)的編號大于其左右孩子的編號，同一個(gè)結(jié)點(diǎn)的左右孩子中，其左孩子的編號小于其右孩子的編號，則可采用_______次序的遍歷實(shí)現(xiàn)編號。a．先序b．中序c．后序d．從根開始的層次遍歷在有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹中，其結(jié)點(diǎn)總數(shù)為_________。a.不確定b.2nc.2n+1d.2n-1任何一個(gè)無向連通圖的最小生成樹_______。a.只有一棵b.有一棵或多棵c.一定有多棵d.可能不存在將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層上從左到右依次對結(jié)點(diǎn)進(jìn)行編號，根結(jié)點(diǎn)的編號為1，則編號為49的結(jié)點(diǎn)的左孩子編號為_________。

a.98b.99下列排序算法中，______算法可能會(huì)出現(xiàn)下面情況：初始數(shù)據(jù)有序時(shí)，花費(fèi)的時(shí)間反而最多。a．堆排序b．冒泡排序c．快速排序d．SHELL排序下圖為AOV網(wǎng)，其可能的拓?fù)溆行蛐蛄袨開_______。a.CAEBDF;b.CABFED;c.CABEDFd.CEABFDAADEFCB將上圖看作無向圖，其從C出發(fā)的廣度優(yōu)先遍歷結(jié)果為_______：a.CABDEFb.CDFEBAc.CDEAFBd.CABFED一個(gè)二叉樹按順序方式存儲(chǔ)在一個(gè)維數(shù)組中，如圖01234567891011121314ABCDEFGHIJ則結(jié)點(diǎn)E在二叉樹的第層。

a、1 b、2 c、3 d、4下列序列中，_______是執(zhí)行第一趟快速排序后得到的序列(排序的關(guān)鍵字類型是字符串)。a.[da，ax，eb，de，bb]ff[ha，gc]b.[cd，eb，ax，da]ff[ha，gc，bb]c.[gc，ax，eb，cd，bb]ff[da，ha]d.[ax，bb，cd，da]ff[eb，gc，ha]二分查找法要求查找表中各元素的鍵值必須是________排列。a.遞增或遞減b.遞增c.遞減d.無序填空作圖簡答題（共70分）：如下圖已知哈希表為空，哈希函數(shù)為H（Key）=KeyMOD11,沖突解決方法分別用線性探測再散列和二次探測再散列。填入在依次插入關(guān)鍵字14，37，25，16之后的情況，并求等概率情況下查找不成功時(shí)的平均查找長度。（1）線性探測再散列012345678910（2）二次探測再散列012345678910已知圖G的鄰接表如下，畫出圖G的所有連通分量。已知一字符串bbcbdebcecbcab，試設(shè)計(jì)赫夫曼編碼并畫出相應(yīng)的赫夫曼樹。用堆排序算法(“大頂堆”排序算法)對關(guān)鍵字進(jìn)行排序，請先建“大頂堆”，然后輸出一個(gè)堆頂元素,再調(diào)整成堆：初始狀態(tài){40，33，24，67，46，79，30，70}所建大頂堆{}輸出一個(gè)堆頂元素調(diào)整后{}用快速排序（取第一個(gè)元素作為樞軸或支點(diǎn)）對下列關(guān)鍵字進(jìn)行排序（圖示）7033796746243040寫出兩趟排序的結(jié)果。一次劃分之后:;分別進(jìn)行快速排序分別再一次劃分之后:.對下面的3階B樹依次插入關(guān)鍵碼60，14，6，畫出插入三個(gè)關(guān)鍵碼后并刪除關(guān)鍵碼20后的結(jié)果（每一步的結(jié)果）。202010401216305028設(shè)初始?xì)w并段為(10,15,31,∞),(9,20,∞),(22,34,37,∞),(6,15,42,∞),(12,37,∞),(84,95,∞),試?yán)脭≌邩溥M(jìn)行6路歸并，畫出選出最小的2個(gè)關(guān)鍵碼的過程。數(shù)據(jù)結(jié)構(gòu)期末試題答案數(shù)據(jù)結(jié)構(gòu)期末試題答案

一、單選題：判斷下列各小題敘述的正誤。對，在題號前的括號內(nèi)填入“√”；錯(cuò)，在題號前的括號內(nèi)填入“×”。（每小題3分，共24分）

(1)向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動(dòng)（）個(gè)元素。

A8B63.5C63D7

(2)設(shè)有一個(gè)二元數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個(gè)元素占一個(gè)空間，則A[4][5]在（）位置，(10)表明用10進(jìn)數(shù)表示。

A692(10)B626(10)C709(10)D724(10)

(3)一個(gè)有順序表有255個(gè)對象，采用順序搜索法查表，平均搜索長度為（）

A128B127C126D255

(4)含5個(gè)節(jié)點(diǎn)(元素值均不相同)的二叉搜索樹有（）種

A54B42C36D65

(5)在分析折半搜索的性能時(shí)常加入失敗結(jié)點(diǎn)，即外結(jié)點(diǎn)，從而形成擴(kuò)充的二叉樹。若設(shè)失敗結(jié)點(diǎn)i所在層為l，那么搜索失敗到達(dá)失敗結(jié)點(diǎn)時(shí)所做的數(shù)據(jù)比較次數(shù)是（）。

Ali+1Bli+2Cli-1Dli

(6)設(shè)有一個(gè)含200個(gè)表項(xiàng)的散列表，用線性探查法解決沖突，按關(guān)鍵碼查詢時(shí)找到一個(gè)表項(xiàng)的平均探查次數(shù)不超過1.5，則散列存儲(chǔ)空間應(yīng)能夠至少容納（）個(gè)表項(xiàng)。（搜索成功的平均搜索長度為Snl=(1+1/(1-a))/2,其中a為裝填因子

A400B526C624D676

(7)n個(gè)頂點(diǎn)的連通圖至少有（）條邊

An-1BnCn+1D0

(8)一個(gè)二叉樹按順序方式存儲(chǔ)在一個(gè)一維數(shù)組中，如圖

則結(jié)點(diǎn)E在二叉樹的第（）層。

A1B2C3D4

二、閱讀理解題：說明下面遞歸過程的功能（10分）

intunknown(BinTreeNode*t){

//指針t是二叉樹的跟指針。

if(t==NULL)return0;

elseif(t->leftChild==NULL&&t->rightChild==NULL)return1;

elsereturnunknown(t->leftChild)+unknown(t->rightChild);

}

三、簡答題（每小題12分，共36分）

1.如下所示的連通圖，請畫出

（1）以頂點(diǎn)為根的深度優(yōu)先生成樹；（6分）

（2）如果有關(guān)節(jié)點(diǎn)，請找出所有的關(guān)節(jié)點(diǎn)。（6分）

2、設(shè)有13個(gè)初始?xì)w并段，其長度分別為28，16，37，42，5，9，13，14，20，17，30，12，18。試畫出4路歸并時(shí)的最佳歸并樹，并計(jì)算它的帶權(quán)路徑長度WPL。

3、設(shè)散列表HT[0..12]，即表的大小為m=13。采用雙散列法解決沖突。散列函數(shù)和再散列函數(shù)分別為：

H0(key)=key%13;注：%是求余數(shù)運(yùn)算(=mod)

Hi=(hi-1+REV(key+1)%11+1)%13;i=1,2,3,...,m-1

其中，函數(shù)REV(x)表示顛倒10進(jìn)制數(shù)x的各位，如REV(37)=73REV(7)=7等。若插入的關(guān)鍵碼序列為{2，8，31，20，19，18，53，27}。試畫出插入這8個(gè)關(guān)鍵碼后的散列表。

四、（10分）

已知一棵二叉樹如下，請分別寫出按前序、中序、后序和層次遍歷時(shí)得到的結(jié)點(diǎn)序列。

五、綜合算法題（10）分

有一種簡單的排序算法，叫做記數(shù)排序(countSorting)。這種排序算法對一個(gè)待排序的表(用數(shù)組表示)進(jìn)行排序，并將排序結(jié)果存放到另一個(gè)新的表中。必須注意的是，表中所有待排序的關(guān)鍵碼互不相同。記數(shù)排序算法針對表中的每個(gè)記錄，掃描待排序的表一趟，統(tǒng)計(jì)表中有多少個(gè)記錄的關(guān)鍵碼比該記錄的關(guān)鍵碼小。假設(shè)針對某一個(gè)記錄，統(tǒng)計(jì)出的記數(shù)值為c，那么，這個(gè)記錄在新的有序表中的合適的存放位置即為c。

(1)給出適用于記數(shù)排序的數(shù)據(jù)表定義；(4分)

(2)使用C++語言編寫實(shí)現(xiàn)記數(shù)排序的算法；(4分)

(3)對于有n個(gè)記錄的表，關(guān)鍵碼比較次數(shù)是多少？(2分)

六、程序填空題(10分)

下面給出的是一個(gè)在二叉樹中查找值為x的結(jié)點(diǎn)，并打印該結(jié)點(diǎn)所有祖先結(jié)點(diǎn)的算法。在此算法中，假設(shè)值為x的結(jié)點(diǎn)不多于一個(gè)。此算法采用后序的非遞歸遍歷形式。因退棧時(shí)需要區(qū)分其左、右子樹是否已經(jīng)遍歷，故在結(jié)點(diǎn)進(jìn)棧時(shí)附帶有一個(gè)標(biāo)志，=0，進(jìn)入左子樹，=1，進(jìn)入右子樹。用棧ST保存結(jié)點(diǎn)指針ptr以及標(biāo)志tag。top是棧頂指針。

voidprint(BintreeNode*t;Type&x){

stackST;inti,top;

top=0;//置空棧

while(t!=NULL&&t->data!=xlltop!=0){

while(t!=NULL&&t->data!=x){//尋找值為x的結(jié)點(diǎn)

1____________;

ST[top].ptr=t;//進(jìn)棧

ST[top].tag=0;

2_____________;

}

if(t!=NULL&&t->data==x)//找到值為x的結(jié)點(diǎn)

for(i=1;3_______________;i++)

cout<<ST.ptr->data<<endl;

else{

while(top>0&&ST[top].tag==1)//未找到值為x的結(jié)點(diǎn)

top--;

if(top>0){

ST[top].tag=1;//轉(zhuǎn)向右子樹

4__________________;

}

}

}

}/*print*/

(1)請將缺失的語句補(bǔ)上(共4分，每空1分)

(2)請給出對于右圖所示的二叉樹，使用上述算法搜索值為9的結(jié)點(diǎn)和值為10的結(jié)點(diǎn)的結(jié)果，以及在棧ST中的變化。(top是棧頂指針)(6分)引用:試題答案試題

一、(1)B(2)C(3)A(4)B(5)D(6)A(7)A(8)B

二、計(jì)算二叉樹的葉結(jié)點(diǎn)個(gè)數(shù)。

三、1.

(1)該連通圖從出發(fā)做深度優(yōu)先搜索，得到的深度優(yōu)先生成樹為：

(2)關(guān)節(jié)點(diǎn)為

2.因?yàn)?13-1)%(4-1)=12%3=0，所以不需要添加空段。最佳歸并樹為

WPS=(5+9+13+12+16+14+17+18+28+37+20+30)*2+42=480

3.散列表HT[0..12]，散列函數(shù)與再散列函數(shù)為

H0(key)=keymod13;

Hi=(Hi-1+REV(key+1)mod11+1)mod13

插入關(guān)鍵碼序列為{2，8，31，20，19，18，53，27}

H0(2)=2，比較次數(shù)為1H0(8)=8，比較次數(shù)為1

H0(31)=5，比較次數(shù)為1H0(20)=7，比較次數(shù)為1

H0(19)=6，比較次數(shù)為1H0(18)=5，沖突,H1=9，比較次數(shù)為2

H0(53)=1，比較次數(shù)為1H0(27)=1，沖突,H1=7,沖突H2=0，比較次數(shù)為3

插入8個(gè)關(guān)鍵碼后的散列表

四、前序：A，B，D，G，C，E，F(xiàn)，H

中序：D，G，B，A，E，C，H，F(xiàn)

后序：G，D，B，E，H，F(xiàn)，C，A

層次：A，B，C，D，E，F(xiàn)，G，H

五、(1)constintDefaultSize=100;

template<classType>classdatalist;//數(shù)據(jù)表的前視聲明

template<classType>classElement{//數(shù)據(jù)表無元素類的定義

private:

Typekey;//關(guān)鍵碼

fieldotherdata;//其它數(shù)據(jù)成員

public:

TypegetKey(){returnkey;}//取當(dāng)前結(jié)點(diǎn)的關(guān)鍵碼

voidsetKey(constTypex){key=x;}//將當(dāng)前結(jié)點(diǎn)的關(guān)鍵碼修改為x

}

template<classType>classdatalist{//用順序表來存儲(chǔ)待排序的元素，這些元素的類型是Type

public:

datalist(intMaxSz=DefaultSize):MaxSize(Maxsz),CurrentSize(0)

{Vector=newElement<Type>[MaxSz];}

private:

Element<Type>*Vector;//存儲(chǔ)待排序元素的向量

intMaxSize,CurrentSize;//最大元素個(gè)數(shù)與當(dāng)前元素個(gè)數(shù)

}

(2)[解答1]

template<classType>

voidcountsort(datalist<Type>&initList,datalist<Type>&resultList){

inti,,j,c;Typerefer;

for(i=0;i<initList,CurrentSize;i++){

c=0;

refer:=initList.Vector.getKey();

for(j=0;j<initList.CurrentSize;j++)

if(initList.Vector[j].getKey()<refer)c++,

resultList.Vector[c]=initList.Vector

}

resultList.CurrentSize=initList.CurrentSize;

}

[解答2]

template<classType>

voidcountsort(datalist<Type>&initList{

int*c=newint[initList.CurrentSize];

for(inti=0;i<initList.CurrentSize;i++)c=0;

for(i=0;i<initList.CurrentSize-1;i++)

for(intj=i+1;j<initList.CurrentSize;j++)

if(initList.Vector[j].getKey()<initList.Vector.getKey())c++;

elsec[j]++;

for(i=0;i<initList.CurrentSize;i++)

resultList.Vector[c]=initList.Vector;

resultList.CurrentSize=initList.CurrentSize;

}

（3）[解答一]關(guān)鍵碼比較次數(shù)為

[解答二]關(guān)鍵碼比較次數(shù)為

六、(1)top++t=t->leftChildi<=topt=ST[top].ptr->rightChild

(2)搜索值為9的結(jié)點(diǎn)

ptrtagptrtag

搜索值為10的結(jié)點(diǎn)

ptrtagptrtagptrtagptrtagptrtagptrtag

ptrtagptrtagptrtagptrtagptrtag數(shù)據(jù)結(jié)構(gòu)期末考核試題樣例及解答

一、單選題從供選擇的答案中選出正確的答案，將其編號填入括號中。

1.在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為（）。

A．內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu)B.靜態(tài)結(jié)構(gòu)與動(dòng)態(tài)結(jié)構(gòu)

C.線性結(jié)構(gòu)與非線性結(jié)構(gòu)D.緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)

2.采用線性鏈表表示一個(gè)向量時(shí)，要求占用的存儲(chǔ)空間地址（）。

A.必須是連續(xù)的B.部分地址必須是連續(xù)的

C.一定是不連續(xù)的D.可連續(xù)可不連續(xù)

3.采用順序搜索方法查找長度為n的順序表時(shí)，搜索成功的平均搜索長度為（）。

A.nB.n/2C.(n-1)/2D.(n+1)/2

4.在一個(gè)單鏈表中，若q結(jié)點(diǎn)是p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q與p之間插入結(jié)點(diǎn)s，則執(zhí)行（）。

A.s→link=p→link;p→link=s;B.p→link=s;s→link=q;

C.p→link=s→link;s→link=p;D.q→link=s;s→link=p;

5.如果想在4092個(gè)數(shù)據(jù)中只需要選擇其中最小的10個(gè)，采用（）方法最好。

A.起泡排序B.堆排序C.直接選擇排序D.快速排序

6.設(shè)有兩個(gè)串t和p，求p在t中首次出現(xiàn)的位置的運(yùn)算叫做（）。

A.求子串B.模式匹配C.串替換D.串連接

7.在數(shù)組A中，每一個(gè)數(shù)組元素A[i,j]占用3個(gè)存儲(chǔ)字，行下標(biāo)i從1到8，列下標(biāo)j從1到10。所有數(shù)組元素相繼存放于一個(gè)連續(xù)的存儲(chǔ)空間中，則存放該數(shù)組至少需要的存儲(chǔ)字?jǐn)?shù)是（）。

A.80B.100C.240D.270

8.將一個(gè)遞歸算法改為對應(yīng)的非遞歸算法時(shí)，通常需要使用（）。

A.棧B.隊(duì)列C.循環(huán)隊(duì)列D.優(yōu)先隊(duì)列

9.一個(gè)隊(duì)列的進(jìn)隊(duì)列順序是1,2,3,4，則出隊(duì)列順序?yàn)椋ǎ?/p>

A.4,3,2,1B.2,4,3,1

C.1,2,3,4D.3,2,1,4

10.在循環(huán)隊(duì)列中用數(shù)組A[0..m-1]存放隊(duì)列元素，其隊(duì)頭和隊(duì)尾指針分別為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是（）。

A.(front-rear+1)%mB.(rear-front+1)%m

C.(front-rear+m)%mD.(rear-front+m)%m

二、判斷題判斷下列各個(gè)敘述的正誤。對，在題號前的括號內(nèi)填入"?"；錯(cuò)，在題號前的括號內(nèi)填入"?"。

()1.算法的運(yùn)行時(shí)間涉及加、減、乘、除、轉(zhuǎn)移、存、取等基本運(yùn)算。要想準(zhǔn)確地計(jì)算總運(yùn)算時(shí)間是不可行的。

()2.二維數(shù)組是數(shù)組元素為一維數(shù)組的線性表，因此二維數(shù)組元素之間是線性結(jié)構(gòu)。

()3.順序表用一維數(shù)組作為存儲(chǔ)結(jié)構(gòu)，因此順序表是一維數(shù)組。

()4.通常使用兩個(gè)類來協(xié)同表示單鏈表，即鏈表的結(jié)點(diǎn)類和鏈表類。

()5.棧和隊(duì)列都是順序存取的線性表，但它們對存取位置的限制不同。

()6.在使用后綴表示實(shí)現(xiàn)計(jì)算器類時(shí)用到一個(gè)棧類的實(shí)例，其作用是暫存運(yùn)算對象。

()7.具有n個(gè)結(jié)點(diǎn)的完全二叉樹的高度為?log2n?+1。（n?0,根在第0層）

()8.為度量一個(gè)搜索算法的效率，需要在時(shí)間和空間兩個(gè)方面進(jìn)行分析。

()9.閉散列法通常比開散列法時(shí)間效率更高。

()10.一棵m階B樹中每個(gè)結(jié)點(diǎn)最多有m個(gè)關(guān)鍵碼，最少有2個(gè)關(guān)鍵碼。

三、填空題把合適的內(nèi)容添到橫線上。

1.對于一個(gè)單鏈接存儲(chǔ)的線性表，假定表頭指針指向鏈表的第一個(gè)結(jié)點(diǎn)，則在表頭插入結(jié)點(diǎn)的時(shí)間復(fù)雜度為________，在表尾插入結(jié)點(diǎn)的時(shí)間復(fù)雜度為________。

2.假定一棵三叉樹（即度為3的樹）的結(jié)點(diǎn)個(gè)數(shù)為50，則它的最小高度為________，假定樹根結(jié)點(diǎn)為第0層。

3．一棵高度（假定樹根結(jié)點(diǎn)為第0層）為4的完全二叉樹中的結(jié)點(diǎn)數(shù)最少為________個(gè)，最多為________個(gè)。

4.在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通所有頂點(diǎn)則至少需要________條邊。

5．從有序表(12,18,30,43,56,78,82,95)中分別折半查找43和56元素時(shí)，其查找長度分別為________和________。

6．對一棵二叉搜索樹進(jìn)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè)________。

7.在開散列表中，處理沖突的方法為________法，在閉散列表中，處理沖突的方法為____________法。

8．在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算（即調(diào)整為子堆的過程）的時(shí)間復(fù)雜度為________，整個(gè)堆排序過程的時(shí)間復(fù)雜度為________。

9.快速排序在平均情況下的時(shí)間復(fù)雜度為________，在最壞情況下的時(shí)間復(fù)雜度為________。

10．在二路歸并排序中，對n個(gè)記錄進(jìn)行歸并的趟數(shù)為________。

四、運(yùn)算題

1.假定一棵普通樹的廣義表表示為a(b(e),c(f(h,i,j),g),d)，分別寫出先根、后根、按層遍歷的結(jié)果。

先根：

后根：

按層：

2．若一個(gè)圖的邊集為{(A,B),(A,C),(A,D),(B,D),(C,F),(D,E),(D,F)}，從頂點(diǎn)A開始分別對該圖進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索，要求頂點(diǎn)值小的鄰接點(diǎn)被優(yōu)先訪問，則寫出得到的深度優(yōu)先搜索和廣度優(yōu)先搜索的頂點(diǎn)序列。

深度優(yōu)先搜索得到的頂點(diǎn)序列：

廣度優(yōu)先搜索得到的頂點(diǎn)序列：

3．已知一個(gè)二叉搜索樹的廣義表表示為38(25(16),52(,74(68(,72),90)))，在下表中填寫出每個(gè)元素的比較次數(shù)。

12345678

3825521674689072

4.假定一個(gè)待散列存儲(chǔ)的線性表為(32,75,29,63,48,94,25,46,18,70)，散列地址空間為HT[13]，若采用除留余數(shù)法構(gòu)造散列函數(shù)和線性探測法處理沖突，試求出每一元素在閉散列表中的初始散列地址和最終散列地址，畫出最后得到的散列表，求出平均查找長度。

12345678910

元素32752963489425461870

初始散列地址

最終散列地址

0123456789101112

散列表

平均查找長度：

5.已知一組記錄為(46,74,53,14,26,38,86,65,27,34)，給出采用快速排序法進(jìn)行排序時(shí)每一趟的排序結(jié)果。

五、算法分析題

1．給出下列每個(gè)遞歸過程的執(zhí)行結(jié)果。

(1)voidunknown(intw){

if(w){

unknown(w-1);

for(inti=1;i<=w;i++)cout<<w;

cout<<endl;

}

}

調(diào)用語句為unknown(4)。

(2)voidunknown(intn){

cout<<n%10;

if(n/10)unknown(n/10);

}

調(diào)用語句為unknown(582)。

(3)intunknown(intm){

intvalue;

if(!m)value=3;

elsevalue=unknown(m-1)+5;

returnvalue;

}

執(zhí)行語句為cout<<unknown(3)。

2.填空。設(shè)有一個(gè)帶表頭結(jié)點(diǎn)的雙向鏈表L，每個(gè)結(jié)點(diǎn)有4個(gè)數(shù)據(jù)成員：指向前驅(qū)結(jié)點(diǎn)的指針prior、指向后繼結(jié)點(diǎn)的指針next、存放數(shù)據(jù)的成員data和訪問頻度freq。所有結(jié)點(diǎn)的freq初始時(shí)都為0。每當(dāng)在鏈表上進(jìn)行一次L.Locate(x)操作時(shí)，令元素值為x的結(jié)點(diǎn)的訪問頻度freq加1，并將該結(jié)點(diǎn)前移，鏈接到與它的訪問頻度相等的結(jié)點(diǎn)后面，使得鏈表中所有結(jié)點(diǎn)保持按訪問頻度遞減的順序排列，以使頻繁訪問的結(jié)點(diǎn)總是靠近表頭。

函數(shù)中有些語句缺失,請將它們補(bǔ)上。

template<classType>

voidDblList<Type>::Locate(Type&x){//查找x結(jié)點(diǎn)

DblNode<Type>*p=first->next;

while(p!=first&&)p=p->next;

if(p!=first){//鏈表中存在x

;//該結(jié)點(diǎn)的訪問頻度加1

DblNode<Type>*current=p;//從鏈表中摘下這個(gè)結(jié)點(diǎn)

current->prior->next=current->next;

current->next->prior=current->prior;

p=current->prior;//尋找重新插入的位置

while(p!=first&&)

p=p->prior;

current->next=;//插入在p之后

current->prior=p;

p->next->prior=current;

p->next=;

}

elsecout<<"Sorry.Notfind!\n";//沒找到

}

缺失的語句為：

①

②

③

④

⑤

3.假定btnode為二叉樹中的結(jié)點(diǎn)類型，它含有數(shù)值域data、左指針域lchild和右指針域rchild，下面函數(shù)中的參數(shù)BT指向一棵二叉樹的樹根結(jié)點(diǎn)，X為給定元素，請給出該函數(shù)的功能。

btnode*AAA(btnode*BT,datatypeX)

{

if(BT==NULL)returnNULL;

else{

if(BT->data==X)returnBT;//返回值為X結(jié)點(diǎn)的指針

else{

btnode*mt;

if(mt=AAA(BT->lchild,X))returnmt;

elseif(mt=AAA(BT->rchild,X))returnmt;

elsereturnNULL;

}

}

}

六、算法設(shè)計(jì)題

1．設(shè)計(jì)一個(gè)算法，從樹根指針為rbitreptr的二叉樹中刪除結(jié)點(diǎn)值為x的子樹，若刪除成功則返回1，否則返回0。假定在算法中不要求回收被刪除子樹中的所有街道，算法中的bitreptr為結(jié)點(diǎn)指針類型，所指結(jié)點(diǎn)類型包含三個(gè)域，即值域data，左指針域lchild和右指針域rchild。

intdeleteSubtree(bitreptr&r,datatypex);

2.已知二叉搜索樹中的結(jié)點(diǎn)類型用BtreeNode表示，被定義為:

structBtreeNode{ElemTypedata;BtreeNode*left,*right;};

其中data為結(jié)點(diǎn)值域，left和right分別為指向左、右孩子結(jié)點(diǎn)的指針域。假定具有BtreeNode*類型的指針參數(shù)BST指向一棵二叉搜索樹的根結(jié)點(diǎn)，試根據(jù)下面的函數(shù)聲明編寫一個(gè)非遞歸算法，向BST樹中插入值為item的結(jié)點(diǎn)，若樹中不存在item結(jié)點(diǎn)則進(jìn)行插入并返回1表示插入成功，若樹中已存在item結(jié)點(diǎn)則不插入并返回0表示插入失敗。

intInsert(BTreeNode*&BST,constElemType&item);引用:參考解答

一、單選題:

1.C2.D3.D4.D5.B6.B7.C8.A9.C10.D

二、判斷題

1.?2.?3.?4.?5.?6.?7.?8.?9.?10.?

三、填空題

1.O(1)O(n)

2．4

3．1631

4.n-1

5.13

6.有序序列

7.鏈接開放定址

8．O(log2n)O(nlog2n)

9．O(nlog2n)O(n2)

10．?log2n?

四、運(yùn)算題

1.先根：a,b,e,c,f,h,i,j,g,d;

后根：e,b,h,i,j,f,g,c,d,a;

按層：a,b,c,d,e,f,g,h,i,j

2.深度優(yōu)先搜索得到的頂點(diǎn)序列：A,B,D,E,F,C

廣度優(yōu)先搜索得到的頂點(diǎn)序列：A,B,C,D,F,E

3．12345678

3825521674689072

12233445

4．平均查找長度為14/10。

12