數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習(xí)（2023年12月）

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習(xí)（2023年12月）數(shù)據(jù)結(jié)構(gòu)期末綜合練習(xí)

2023年12月

期末綜合練習(xí)一

一、單項(xiàng)選擇題

1.數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指()。A．?dāng)?shù)據(jù)元素之間的關(guān)系B．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C．?dāng)?shù)據(jù)元素的類(lèi)型D．?dāng)?shù)據(jù)的規(guī)律結(jié)構(gòu)2.結(jié)構(gòu)中的元素之間存在一對(duì)多的關(guān)系是（）。A．集合B．線(xiàn)性結(jié)構(gòu)C．樹(shù)形結(jié)構(gòu)D．圖狀結(jié)構(gòu)

3.對(duì)不帶頭結(jié)點(diǎn)的單向鏈表,判斷是否為空的條件是（）（設(shè)頭指針為head）。A．head==NULLB．head->next==NULL

C．head->next==headD．head=NULL

4.設(shè)有一個(gè)長(zhǎng)度為20的順序表，要在第5個(gè)元素之前插入1個(gè)元素（也就是插入元素作為新表的第5個(gè)元素），則移動(dòng)元素個(gè)數(shù)為（）。A．15B．16C.5D．4

5.在一個(gè)不帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p、q分別指向表中第一個(gè)結(jié)點(diǎn)和尾結(jié)點(diǎn)，現(xiàn)要?jiǎng)h除第一個(gè)結(jié)點(diǎn)，可用的語(yǔ)句是（）。

A．p=q->next;p=p->next;B．p->next=q;p=p->next;C．p->next=q->next;q=p;D．p=p->next;q->next=p;

6．在一個(gè)尾指針為rear的不帶頭結(jié)點(diǎn)的單循環(huán)鏈表中,插入一個(gè)s所指的結(jié)點(diǎn),并作為第一個(gè)結(jié)點(diǎn)，可執(zhí)行（）。

A．rear?next=s;s?next=rear?nextB．rear?next=s?next;C．rear=s?nextD．s?next=rear?next;rear?next=s;7．一個(gè)棧的進(jìn)棧序列是1，2，3，4，5，則棧的不可能輸出序列是（）（進(jìn)棧出?？梢越惶孢M(jìn)行）。

A．12345B．43512C．45321D．54321

8．元素a，b，c,d按順序依次進(jìn)棧，則該棧的可能輸出序列是（）（進(jìn)棧出?？梢越惶孢M(jìn)行）。

A．c,a,b，dB．d，b，c,a

C．a(chǎn),c，b，dD．d，c，a,b

9．一個(gè)隊(duì)列的入隊(duì)序列是2，4，6，8，按該隊(duì)列的輸出序列使各元素依次入棧，該棧的可能輸出序列是（）。

A．8，6，4，2B．6，2，4，8

C．8，4，2，6D．8，2，4，610．從一個(gè)棧頂指針為top的鏈棧中取棧頂元素，用變量x保存該元素的值，則執(zhí)行（）。A．x=top->data;top=top?next;B．x=top->data;

C．top=top->next;x=top->data;D．top=top->next;x=data;

11．在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，已生成一個(gè)結(jié)點(diǎn)p,要為結(jié)點(diǎn)p賦

1

值x,并入隊(duì)的運(yùn)算為（）。

A.p->data=x;p->next=NULL;f->next=p;f=p;B．p->data=x;p->next=NULL;r->next=p;r=p;C．p->data=x;p->next=r;r=s;D．p->data=x;p->next=f;f=s;

12．設(shè)有一個(gè)對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維

數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），B數(shù)組共有55個(gè)元素,則該矩陣是（）階的對(duì)稱(chēng)矩陣。

(矩陣中的第1個(gè)元素是a1,1）

A．5B．20C．10D．15

13．設(shè)有一個(gè)25階的對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣中元素．a(chǎn)7,6在一維數(shù)組B中的下標(biāo)是（）。(矩陣中的第1個(gè)元素是a1,1）

A．34B．14C．26D．27

14．設(shè)有一個(gè)18階的對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)

到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則數(shù)組中第53號(hào)元素對(duì)應(yīng)于矩陣中的元素是（）。(矩陣中的第1個(gè)元素是a1,1）

A．a(chǎn)8,5,B．a(chǎn)10,8C．a(chǎn)8,1,D．a(chǎn)7,615.以下程序段的結(jié)果是c的值為（）。

chara[8]=“1236789〞,int*p=a,intc=0;while(*p++)c++;

A．8,B．7C．10D．1216.以下程序段的結(jié)果是c的值為（）。

char*a[5]={“12378〞,“1237〞,“1236789〞,“1237〞,“123708〞};inti,c=0;for(i=0;iprior）->next=p->next；然再用語(yǔ)句________。

7．在雙向鏈表中，要?jiǎng)h除p所指的結(jié)點(diǎn)，其中所用的一條語(yǔ)句（p->prior）->next=p->next；的功能是：使P所指結(jié)點(diǎn)的直接前驅(qū)的右指針指向________。

8．在一個(gè)單向鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指向的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行s->next=p->next;和_______的操作.

4

9．設(shè)有一個(gè)頭指針為head的單向鏈表，p指向鏈表中的某結(jié)點(diǎn)，若要使該鏈表成為單向循環(huán)鏈表，可用語(yǔ)句while(p->next!=NULL)p=p->next;和________。10．一個(gè)棧和一個(gè)隊(duì)列的輸入序列都為abcdefg，它們可能有一致的輸出序列嗎？_________。（若沒(méi)有則回復(fù)沒(méi)有，若有則寫(xiě)出序列,進(jìn)棧出?？梢越惶孢M(jìn)行）。

11．向一個(gè)棧頂指針為top的鏈棧中插入一個(gè)p所指結(jié)點(diǎn)時(shí)，某人用語(yǔ)句top=p；p->next=top;這樣做的結(jié)果使p所指向的結(jié)點(diǎn)的指針域指向了_______。

12.從一個(gè)棧頂指針為top的鏈棧中取棧頂元素，用d保存棧頂元素的值，可執(zhí)行

________。(結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閐ata)

13．在一個(gè)鏈隊(duì)中，設(shè)front和rear分別為隊(duì)頭和隊(duì)尾指針，則s所指結(jié)點(diǎn)(數(shù)據(jù)域已賦值)的

入隊(duì)操作為s->next=NULL;.________和rear=s;

14.循環(huán)鏈隊(duì)列中，設(shè)front和rear分別為隊(duì)頭和隊(duì)尾指針，(最多元素為MaxSize,),判斷循環(huán)

鏈隊(duì)列為空的條件是________為真。

15．設(shè)有n階對(duì)稱(chēng)矩陣A，用一維數(shù)組s壓縮存儲(chǔ)A的下三角元素，s的下標(biāo)從零開(kāi)始，

元素s[26]相應(yīng)于A中的元素為_(kāi)______。(矩陣中的第1個(gè)元素是a1,1）

16.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ),可采用三元組表，設(shè)a是稀疏矩陣A相應(yīng)的三元組表類(lèi)型（結(jié)

構(gòu)體類(lèi)型）變量，a中的一個(gè)成員項(xiàng)是三元組類(lèi)型的結(jié)構(gòu)體數(shù)組data，按書(shū)中定義，若a.data[0].i=2;a.data[0].j=3;a.data[0].v=16;它提供的A數(shù)組的相關(guān)信息有_______

17．對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ),可采用三元組表，設(shè)a是稀疏矩陣A相應(yīng)的三元組表類(lèi)型（結(jié)構(gòu)體類(lèi)型）變量，a中的一個(gè)成員項(xiàng)是三元組類(lèi)型的結(jié)構(gòu)體數(shù)組data，按書(shū)中定義，若data的下標(biāo)從零開(kāi)始，最終一個(gè)元素下標(biāo)為10，又a.data[10].i=8;a.data[10].j=5;a.data[10].v=36;它提供的A矩陣的相關(guān)信息有_______。

18．設(shè)有一棵深度為5的完全二叉樹(shù)，該樹(shù)共有20個(gè)結(jié)點(diǎn),第五層上有個(gè)葉結(jié)點(diǎn)。（根所在結(jié)點(diǎn)為第1層）

19．設(shè)有一棵有78個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，該樹(shù)共有_________層。（根所在結(jié)點(diǎn)為第1層）20．________樹(shù)可得到一個(gè)有序序列。

21．對(duì)于一棵具有________個(gè)結(jié)點(diǎn)的二叉樹(shù)，其相應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中共有n+1個(gè)指針域空.22．如圖4所示的二叉樹(shù)，其后序遍歷序列為_(kāi)________。

215789346圖4

23．如圖5所示的二叉樹(shù)，其中序遍歷序列為_(kāi)________。

5

=j+1;k--)__(5)___=a[k];a[j+1]=a[0];}

}

2．以下函數(shù)是二叉排序樹(shù)的查找算法，若二叉樹(shù)為空，則返回根結(jié)點(diǎn)的指針，否則，返回值是指向樹(shù)結(jié)點(diǎn)的結(jié)構(gòu)指針p（查找成功p指向查到的樹(shù)結(jié)點(diǎn)，不成功p指向?yàn)镹ULL）完成程序中的空格

typedefstructBnode{intkey;

structBnode*left;structBnode*right;

8

}Bnode;

Bnode*BSearch(Bnode*bt,intk)

/*bt用于接收二叉排序樹(shù)的根結(jié)點(diǎn)的指針，k用以接收要查找的關(guān)鍵字*/{Bnode*p;

if(bt==___(1)_____)return(bt);

p=bt;

while(p->key!=__(2)______){if(kkey)___(3)_____;

else___(4)_____;if(p==NULL)break;}

return(___(5)_____);}

3．以下函數(shù)為鏈棧的進(jìn)棧操作，x是要進(jìn)棧的結(jié)點(diǎn)的數(shù)據(jù)域，top為棧頂指針

structnode

{ElemTypedata;

structnode*next;};

structnode*top;

voidPush(ElemTypex)

{

structnode*p;

p=(structnode*)malloc(___(1)_____);p->data=x;___(2)_____;_____(3)___;}

}

4.設(shè)有一個(gè)頭指針為head的不帶頭結(jié)點(diǎn)單向鏈表，p、q是指向鏈表中結(jié)點(diǎn)類(lèi)型的指針變量，p指向鏈表中結(jié)點(diǎn)a,（設(shè)鏈表中沒(méi)有結(jié)點(diǎn)的數(shù)據(jù)域與結(jié)點(diǎn)a的數(shù)據(jù)域一致）,寫(xiě)出相關(guān)語(yǔ)句

(1).使該單向鏈表成為單向循環(huán)鏈表

(2)插入結(jié)點(diǎn)s,使它成為a結(jié)點(diǎn)的直接前驅(qū)q=p;x=p->data;

while（__(1)___）q=q->next;q->next=head;q=p;p=p->next;while(p->data!=x){q=p;

9

__(2)___}

s->next=p;__(3)___

期末綜合練習(xí)一答案

一、單項(xiàng)選擇題

1．B2．C3．A4．B5．D6．D7．B8．C9．A10．B11．B12．C13．D14．B15．B16．A17．A18．A19．A20．D21．C22．D23．D24．C25．C26．A27．B28．A29．B

二、填空題1．多個(gè)數(shù)據(jù)項(xiàng)2．圖狀結(jié)構(gòu)3．多對(duì)多4．155．226．（p->next）->prior=p->prior；7．P所指結(jié)點(diǎn)的直接后繼8．p->next=s;9．p->next=head;10．a(chǎn)bcdefg11．p本身

12．d=top->data;13．rear->next=s;14．front==rear15．a(chǎn)7,6

16．A的第一個(gè)非零元素的下標(biāo)為2，3，元素為1617．A共有11個(gè)非零元素，a8,5為3618．519．7

20．中序遍歷21．n

22．51987643223．538794624．不正確

三、綜合應(yīng)用題

10

1．（1）a

cb

de

圖8

（2）dleft（4）p=p->right（5）p3

（1）sizeof(structnode)（2）p->next=top（3）top=p4.

(1)q->next!=NULL(2)p=p->next;(3)q->next=s;

1426161830151928圖12

期末綜合練習(xí)二

13

一、單項(xiàng)選擇題

1.在數(shù)據(jù)結(jié)構(gòu)和算法中，與所使用的計(jì)算機(jī)有關(guān)的是（）。A．?dāng)?shù)據(jù)元數(shù)間的抽象關(guān)系B．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C．算法的時(shí)間繁雜度D．?dāng)?shù)據(jù)的規(guī)律結(jié)構(gòu)2.一種規(guī)律結(jié)構(gòu)在存儲(chǔ)時(shí)（）。

A．只要存儲(chǔ)數(shù)據(jù)元素間的關(guān)系B．只能采用一種存儲(chǔ)結(jié)構(gòu)C．可采用不同的存儲(chǔ)結(jié)構(gòu)D．只要存儲(chǔ)數(shù)據(jù)元素的值3.對(duì)順序表,以下表達(dá)中正確的是()。

A．用一組地址連續(xù)的存儲(chǔ)單元依次存放線(xiàn)性表的數(shù)據(jù)元素B．各個(gè)數(shù)據(jù)元素的首地址是連續(xù)的

C．?dāng)?shù)據(jù)元素不能隨機(jī)訪(fǎng)問(wèn)D．插入操作不需要移動(dòng)元素4.對(duì)鏈表,以下表達(dá)中正確的是（）。

A．不能隨機(jī)訪(fǎng)問(wèn)任一結(jié)點(diǎn)B．結(jié)點(diǎn)占用的存儲(chǔ)空間是連續(xù)的

C．插入刪除元素的操作一定要要移動(dòng)結(jié)點(diǎn)D．可以通過(guò)下標(biāo)對(duì)鏈表進(jìn)行直接訪(fǎng)問(wèn)5．設(shè)有一個(gè)長(zhǎng)度為25的順序表，要?jiǎng)h除第10個(gè)元素(下標(biāo)從1開(kāi)始),需移動(dòng)元素的個(gè)數(shù)為（）。

A．9B．10C．15D．16

6．線(xiàn)性表在存儲(chǔ)后,假使相關(guān)操作是:要求已知第i個(gè)結(jié)點(diǎn)的位置訪(fǎng)問(wèn)該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，則采用（）存儲(chǔ)方式是不可行的。

A．單鏈表B．雙鏈表C．單循環(huán)鏈表D．順序表7.設(shè)單向鏈表中,指針p指向結(jié)點(diǎn)A，若要?jiǎng)h除A的直接后繼，則所需修改指針的操作為()。

A.p->next=p->next->next;

B.p=p->next;

C.p=p->next->next;D.p->next=p;8．棧和隊(duì)列的共同特點(diǎn)是（）。

A．都是先進(jìn)后出B．元素都可以隨機(jī)進(jìn)出

C．只容許在端點(diǎn)處插入和刪除元素D．都是先進(jìn)先出

9．元素1，3，5，7按順序依次進(jìn)棧，按該棧的可能輸出序列依次入隊(duì)列，該隊(duì)列的可能輸出序列是（）。（進(jìn)棧出?？梢越惶孢M(jìn)行）。A．7，5，3，1B．7，3，1,5

C．7，5，1，3D．5,1，3，7

10．元素2，4，6，8按順序依次進(jìn)棧，按該棧的的可能輸出序列依次入隊(duì)列，該隊(duì)列的可能

輸出序列是（）（進(jìn)棧出棧可以交替進(jìn)行）。A．8，6，2，4B．8，4，2，6

C．6，2，4，8D．8，6，4，2

11．對(duì)一個(gè)棧頂指針為top的鏈棧進(jìn)行進(jìn)棧操作，設(shè)P為待進(jìn)棧的結(jié)點(diǎn)，則執(zhí)行（）。A．p=top->next;top=top?next;B．p->next=top;C．p->next=top;top=p;D．top=p;

12．在一個(gè)不帶頭結(jié)點(diǎn)的鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則從該對(duì)列中刪除一個(gè)結(jié)點(diǎn)并把結(jié)點(diǎn)的值保存在變量x中的運(yùn)算為（）。A．x=r?data；r=r?next;B．r=r?next;x=r?dataC．x=f?data；f=f?next;D．f=f?next;x=f?data

14

13．設(shè)有一個(gè)18階的對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)

到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則數(shù)組中第33號(hào)元素對(duì)應(yīng)于矩陣中的元素是（）。(矩陣中的第1個(gè)元素是a1,1）

A．a(chǎn)7,6B．a(chǎn)10,8C．a(chǎn)9,2D．a(chǎn)8,5

14．設(shè)有一個(gè)20階的對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則數(shù)組中第38號(hào)元素對(duì)應(yīng)于矩陣中的元素是（）。(矩陣中的第1個(gè)元素是a1,1）

A．a(chǎn)10,8B．a(chǎn)7,6C．a(chǎn)9,2D．a(chǎn)8,5

15．設(shè)有一個(gè)17階的對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)

到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣中元素

a10,6在一維數(shù)組B中的下標(biāo)是

（）。(矩陣中的第1個(gè)元素是a1,1）

A．45,B．18C．51D．5316．在C語(yǔ)言中，分別存儲(chǔ)“S〞和‘s’，各需要占用（）字節(jié)。A．一個(gè)和兩個(gè)B．兩個(gè)C．一個(gè)D．兩個(gè)和一個(gè)17．串函數(shù)StrCmp（“ABCd〞，“ABCD〞）的值為（）。

A．0B．-1C．1D．3

18．一棵有n個(gè)結(jié)點(diǎn)，采用鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)中，共有（）個(gè)指針域被有效使用（即指針域?yàn)榉强眨?/p>

A．n+1B．nC．n-1D．n-2

19．一棵采用鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)中有n個(gè)指針域?yàn)榭?該二叉樹(shù)共有（）個(gè)結(jié)點(diǎn)。A．n+1B．nC．n-1D．n-2

20．在一棵二叉樹(shù)中，若編號(hào)為i的結(jié)點(diǎn)存在雙親結(jié)點(diǎn)，則雙親結(jié)點(diǎn)的順序編號(hào)為（）。A．i/2.0B．i/2向下取整C．2i+1D．i+2

21．設(shè)一棵哈夫曼樹(shù)共有n個(gè)非葉結(jié)點(diǎn)，則該樹(shù)有（）個(gè)結(jié)點(diǎn)。

A．2nB．2n+2C．2n-1D．2n+122．設(shè)一棵哈夫曼樹(shù)共有2n+1個(gè)結(jié)點(diǎn)，則該樹(shù)有（）個(gè)非葉結(jié)點(diǎn)。A．nB．n+1C．n-1D．2n

23．一棵結(jié)點(diǎn)數(shù)31abecd圖1

f

26．如圖2所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先探尋法進(jìn)行遍歷，則可能得到的一

種頂點(diǎn)序列為（）。

A．a(chǎn)bedfcB．a(chǎn)cfebdC．a(chǎn)ebcdfD．a(chǎn)ebcfd

abecdf

圖2

27．一組記錄的關(guān)鍵字序列為（46,20,30,79，56，38，40，84,90,110），利用快速排序，以

第一個(gè)關(guān)鍵字為分割元素，經(jīng)過(guò)一次劃分后結(jié)果為（）。A．20,30,40，38，46，79，56，84,90,100B．40，20,30,38，46，56，79，84,90,110C．30,20,40，38，46，84，56，79,90,100

D．20,3038，40，46，56，79，84,90,100

28．一組記錄的關(guān)鍵字序列為（56，30,89，66，48，50，94,87,100），利用快速排序，以第

一個(gè)關(guān)鍵字為分割元素，經(jīng)過(guò)一次劃分后結(jié)果為（）。

A．30，50,48，56，66，89，94,100,87B．50，30,48，56，66，89，94,87,100C．48，30,50，56，66，89，94,87,100D．50，30,48，66，56，89，94,87,10029．一組記錄的關(guān)鍵字序列為（75，63，95，80，53，45，38，20），利用堆排序（堆頂元素是最大元素）的方法建立的初始堆為（）。A．95，80，75，63，53，45，38，20B．95，63，75，80，53，45，38，20c.95,80,45,63,53,75,38,20

D．95,80,75,20,53,45,38,6330．線(xiàn)性表以（）方式存儲(chǔ)，能進(jìn)行折半查找。

A．關(guān)鍵字有序的鏈接B．順序C．關(guān)鍵字有序的順序D．?dāng)?shù)組

16

二、填空題

1．?dāng)?shù)據(jù)元素之間的抽象關(guān)系稱(chēng)為_(kāi)_______結(jié)構(gòu)。

2.數(shù)據(jù)的規(guī)律結(jié)構(gòu)在計(jì)算機(jī)中的表示稱(chēng)為_(kāi)_______結(jié)構(gòu)。

3．要求在n個(gè)數(shù)據(jù)元素中找值最大的元素，其基本操作為_(kāi)_______。算法的時(shí)間繁雜度為_(kāi)______。

4.求兩個(gè)n階矩陣的乘積，算法的基本操作為_(kāi)_______，時(shí)間繁雜度為_(kāi)_______。5．設(shè)有一個(gè)長(zhǎng)度為25的順序表,第8號(hào)元素到第25號(hào)元素依次存放的值

為8,9,10,11,?,25，某人想要?jiǎng)h除第8個(gè)元素，他的做法是從第25號(hào)元素開(kāi)始,直到第9號(hào)元素依次向前移動(dòng)1個(gè)位置,其結(jié)果新表中第9號(hào)元素的值為（）。6．設(shè)有一個(gè)長(zhǎng)度為25的順序表,第8號(hào)元素到第25號(hào)元素依次存放的值為8,9,10,11,?25,某人想要在第8個(gè)元素前插入1個(gè)元素7（也就是插入元素作為新表的第8個(gè)元素），他的做法是從第8號(hào)元素開(kāi)始,直到第25號(hào)元素依次向后移動(dòng)1個(gè)位置,然后把7存放在8號(hào)位置，其結(jié)果是新表中第25號(hào)元素的值為（）。

7．在雙向鏈表中，要在p所指的結(jié)后插入q所指的結(jié)點(diǎn)(設(shè)q所指的結(jié)點(diǎn)已賦值)，可以

先用語(yǔ)句q->next=p->next;（p->next）->prior=q；然后再用語(yǔ)句q->prior=p;和語(yǔ)句________。

8．在雙向鏈表中，要在p所指的結(jié)后插入q所指的結(jié)點(diǎn)(設(shè)q所指的結(jié)點(diǎn)已賦值)，

其中所用的一條語(yǔ)句（p->next）->prior=q；的功能是使P所指結(jié)點(diǎn)的_______指向q。9．在一個(gè)單向鏈表中，要?jiǎng)h除p所指結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)。則可以用操作________。（用一條語(yǔ)句）

10．設(shè)有一個(gè)帶頭結(jié)點(diǎn)的，頭指針為head的單向鏈表，p指向表中某一個(gè)結(jié)點(diǎn)，且有

p->next==NULL,現(xiàn)要?jiǎng)h除頭結(jié)點(diǎn)，并使該單向鏈表構(gòu)造成單向循環(huán)鏈表，通過(guò)操作head=head->next;________。

11．向一個(gè)棧頂指針為top的鏈棧中插入一個(gè)p所指結(jié)點(diǎn)時(shí)，可執(zhí)行________操作。(填兩條語(yǔ)句,結(jié)點(diǎn)的指針域?yàn)閚ext)

12．從一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用d保存被刪結(jié)點(diǎn)的值，可執(zhí)行

________。(結(jié)點(diǎn)的指針域?yàn)閚ext,數(shù)據(jù)域?yàn)閐ata)

13．在一個(gè)帶頭結(jié)點(diǎn)的鏈隊(duì)中，設(shè)front和rear分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)

的操作為p=front->next;_______=p->next;(結(jié)點(diǎn)的指針域?yàn)閚ext,p為輔助用指針)14循環(huán)鏈隊(duì)列中，設(shè)front和rear分別為隊(duì)頭和隊(duì)尾指針，(最多元素為MaxSize,采用少用一個(gè)元素的模式),判斷循環(huán)鏈隊(duì)列為滿(mǎn)的條件為_(kāi)_______。

15．設(shè)有n階對(duì)稱(chēng)矩陣A，用一維數(shù)組s壓縮存儲(chǔ)A的下三角元素，s的下標(biāo)從零開(kāi)始，最后一個(gè)元素的下標(biāo)為27，則n=_______。(矩陣中的第1個(gè)元素是a1,1）

16．對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ),可采用三元組表，一個(gè)6行7列的稀疏矩陣A相應(yīng)的三元組表共有8個(gè)元素,則矩陣A共有_______個(gè)零元素。

17.一棵3度的樹(shù)，其中3度結(jié)1個(gè)，2度結(jié)2個(gè)，1度結(jié)2個(gè)，則該樹(shù)共有_______個(gè)葉結(jié)點(diǎn)。

18.一棵有8個(gè)權(quán)重值構(gòu)造的哈夫曼數(shù)，共有個(gè)結(jié)點(diǎn)。

19．一棵有7個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，其1度結(jié)點(diǎn)數(shù)的個(gè)數(shù)為2，則該樹(shù)共有_______個(gè)結(jié)點(diǎn)

20．一棵有18個(gè)結(jié)點(diǎn)的二叉樹(shù)，其2度結(jié)點(diǎn)數(shù)的個(gè)數(shù)為8，則該樹(shù)共有

_______個(gè)1度結(jié)點(diǎn)

21．如圖3所示的二叉樹(shù)，其中序遍歷序列為_(kāi)________。

17

21578圖3

22．如圖2所示的二叉樹(shù)，其先序遍歷序列為_(kāi)________。

21578圖4

23．二叉排序樹(shù)或者是一棵空樹(shù)，或者是一棵具有以下性質(zhì)的二叉排：若它的左子樹(shù)非空，則左子樹(shù)的所有結(jié)點(diǎn)的值都小于它的根結(jié)點(diǎn)的值；若它的右子樹(shù)非空，則右子的所有結(jié)點(diǎn)的值都大于（若允許結(jié)點(diǎn)有一致的值，則大于等于）它的根結(jié)點(diǎn)的值。這種說(shuō)法是__________的。(回復(fù)正確或不正確)

24．在查找表中，通過(guò)記錄的某關(guān)鍵字能唯一地確定一個(gè)記錄，該關(guān)鍵字稱(chēng)為_(kāi)________。三、綜合題1．

(1)以3，4，5，8，9，10作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹(shù)。(2)給出相應(yīng)權(quán)重值葉結(jié)點(diǎn)的哈夫曼編碼。

(3)一棵哈夫曼樹(shù)有2n-1個(gè)結(jié)點(diǎn)，它是共有多少個(gè)權(quán)重值構(gòu)造而成的？簡(jiǎn)述理由？

18

34693469

2．（1）對(duì)給定權(quán)值3，1，4，4，5，6，構(gòu)造深度為5的哈夫曼樹(shù)。(設(shè)根為第1層)(2)求樹(shù)的帶權(quán)路徑長(zhǎng)度。

（3）鏈接存儲(chǔ)上述哈夫曼樹(shù)，結(jié)點(diǎn)中共有多少個(gè)指針域?yàn)榭?說(shuō)明理由.3．（1）簡(jiǎn)述拓?fù)渑判虻牟襟E。

（2）說(shuō)明有向圖的拓?fù)湫蛄胁灰欢ㄊ俏ㄒ坏脑?。?）如何利用拓?fù)渑判蛩惴ㄅ卸▓D是否存在回路。

（4）設(shè)有向圖G如下，寫(xiě)出首先刪除頂點(diǎn)1的3種拓?fù)湫蛄小?/p>

12345圖5

6

4.(1)如下的一棵樹(shù),給出先序遍歷序列

(2)把1,2,3,4,5,6,7,8,9填人,使它成為一棵二叉排序樹(shù)

提醒：設(shè)圖中的樹(shù)是二叉排序樹(shù)，找出中序遍歷序列與1，2，…9的對(duì)應(yīng)關(guān)系

(3)請(qǐng)?jiān)谠摌?shù)中再插入一個(gè)結(jié)點(diǎn)3.5作為葉結(jié)點(diǎn)，并使它依舊是一棵二叉排序樹(shù)。

A1A2A3A4A5A8A6A7A9圖6

19

5．設(shè)有序表為（21，22，23，24，25，26，27，28，29，30，31,32），元素的下標(biāo)從0開(kāi)始。

（1）說(shuō)出有哪幾個(gè)元素需要經(jīng)過(guò)4次元素間的比較才能成功查到。

（2）畫(huà)出對(duì)上述有序表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(shù)（樹(shù)結(jié)點(diǎn)用數(shù)值表示）（3）設(shè)查找元素為5，需要進(jìn)行多少次元素間的比較才能確定不能查到。（4）求在等概率條件下，成功查找的平均比較次數(shù)？

6．設(shè)查找表為(5,6,7,8,9,10,11,12,13,14)

（1）畫(huà)出對(duì)上述有序表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(shù)(要求以數(shù)據(jù)元素作為樹(shù)結(jié)點(diǎn))(2)給出二叉排序樹(shù)的定義,針對(duì)上述折半查找所對(duì)應(yīng)的判定樹(shù)的構(gòu)造過(guò)程,說(shuō)明判定樹(shù)是否是二叉排序樹(shù)(設(shè)樹(shù)中沒(méi)有一致結(jié)點(diǎn))？

(3)為了查找元素5.5，經(jīng)過(guò)多少次元素間的比較才能確定不能查到？

四、程序填空題

1．以下程序是快速排序的算法

設(shè)待序的記錄序列存放在a[start],…a[end]中，按記錄的關(guān)鍵字進(jìn)行快速排序，先進(jìn)行一次劃分，再分別進(jìn)行遞歸調(diào)用

voidquicksort(NODEa[],intstart,intend){inti，j;NODEmid;if(start>=end)return;

i=start;j=end;mid=a[i];while(iif(idata=x;

p->next=NULL;

___(2)_____;

rear=___(3)_____;}

4.設(shè)有一個(gè)頭指針為head的不帶頭結(jié)點(diǎn)單向鏈表,且p、q是指向鏈表中結(jié)點(diǎn)類(lèi)型的指針變量，p指向鏈表中某結(jié)點(diǎn)a（設(shè)鏈表中沒(méi)有結(jié)點(diǎn)的數(shù)據(jù)域與結(jié)點(diǎn)a的數(shù)據(jù)域一致）,寫(xiě)出相關(guān)語(yǔ)句

(1).使該單向鏈表成為單向循環(huán)鏈表(2)刪去a結(jié)點(diǎn)q=p;x=p->data;

while（q->next!=NULL）q=q->next;__(1)___

q=p;p=p->next;while(p->data!=x){q=p;__(2)___}

__(3)___

期末綜合練習(xí)二答案

一、單項(xiàng)選擇題1．B2．C3．A4．A5．C6．A7．A8．C9．A10．D11．C12．C13．D14．C15．C16．D17．C18．C19．C20．B21．D22．A23．A24．B25．A26．C27．B28．B29．A30．C

二、填空題1．規(guī)律

2．物理（存儲(chǔ)）

22

3．元素間的比較O(n)4．乘法O(n3)5．256．8

7．p->next=q；

8．直接前驅(qū)的左指針9．p->next=p->next->next;10．p->next=head;

11．p->next=top;top=p；

12．d=top->dat