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

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

2023年12月

期末綜合練習一

一、單項選擇題

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

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

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

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

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

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．在一個尾指針為rear的不帶頭結(jié)點的單循環(huán)鏈表中,插入一個s所指的結(jié)點,并作為第一個結(jié)點，可執(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．一個棧的進棧序列是1，2，3，4，5，則棧的不可能輸出序列是（）（進棧出?？梢越惶孢M行）。

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

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

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

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

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

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

C．8，4，2，6D．8，2，4，610．從一個棧頂指針為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．在一個鏈隊中，假設f和r分別為隊頭和隊尾指針，已生成一個結(jié)點p,要為結(jié)點p賦

1

值x,并入隊的運算為（）。

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．設有一個對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維

數(shù)組B中（數(shù)組下標從1開始），B數(shù)組共有55個元素,則該矩陣是（）階的對稱矩陣。

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

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

13．設有一個25階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標從1開始），則矩陣中元素．a(chǎn)7,6在一維數(shù)組B中的下標是（）。(矩陣中的第1個元素是a1,1）

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

14．設有一個18階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲

到一維數(shù)組B中（數(shù)組下標從1開始），則數(shù)組中第53號元素對應于矩陣中的元素是（）。(矩陣中的第1個元素是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；然再用語句________。

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

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

4

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

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

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

________。(結(jié)點的數(shù)據(jù)域為data)

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

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

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

鏈隊列為空的條件是________為真。

15．設有n階對稱矩陣A，用一維數(shù)組s壓縮存儲A的下三角元素，s的下標從零開始，

元素s[26]相應于A中的元素為_______。(矩陣中的第1個元素是a1,1）

16.對稀疏矩陣進行壓縮存儲,可采用三元組表，設a是稀疏矩陣A相應的三元組表類型（結(jié)

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

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

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

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

21．對于一棵具有________個結(jié)點的二叉樹，其相應的鏈式存儲結(jié)構(gòu)中共有n+1個指針域空.22．如圖4所示的二叉樹，其后序遍歷序列為_________。

215789346圖4

23．如圖5所示的二叉樹，其中序遍歷序列為_________。

5

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

}

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

typedefstructBnode{intkey;

structBnode*left;structBnode*right;

8

}Bnode;

Bnode*BSearch(Bnode*bt,intk)

/*bt用于接收二叉排序樹的根結(jié)點的指針，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ù)為鏈棧的進棧操作，x是要進棧的結(jié)點的數(shù)據(jù)域，top為棧頂指針

structnode

{ElemTypedata;

structnode*next;};

structnode*top;

voidPush(ElemTypex)

{

structnode*p;

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

}

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

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

(2)插入結(jié)點s,使它成為a結(jié)點的直接前驅(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)___

期末綜合練習一答案

一、單項選擇題

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．多個數(shù)據(jù)項2．圖狀結(jié)構(gòu)3．多對多4．155．226．（p->next）->prior=p->prior；7．P所指結(jié)點的直接后繼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的第一個非零元素的下標為2，3，元素為1617．A共有11個非零元素，a8,5為3618．519．7

20．中序遍歷21．n

22．51987643223．538794624．不正確

三、綜合應用題

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

期末綜合練習二

13

一、單項選擇題

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

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

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

C．數(shù)據(jù)元素不能隨機訪問D．插入操作不需要移動元素4.對鏈表,以下表達中正確的是（）。

A．不能隨機訪問任一結(jié)點B．結(jié)點占用的存儲空間是連續(xù)的

C．插入刪除元素的操作一定要要移動結(jié)點D．可以通過下標對鏈表進行直接訪問5．設有一個長度為25的順序表，要刪除第10個元素(下標從1開始),需移動元素的個數(shù)為（）。

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

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

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

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

B.p=p->next;

C.p=p->next->next;D.p->next=p;8．棧和隊列的共同特點是（）。

A．都是先進后出B．元素都可以隨機進出

C．只容許在端點處插入和刪除元素D．都是先進先出

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

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

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

輸出序列是（）（進棧出?？梢越惶孢M行）。A．8，6，2，4B．8，4，2，6

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

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

12．在一個不帶頭結(jié)點的鏈隊中，假設f和r分別為隊頭和隊尾指針，則從該對列中刪除一個結(jié)點并把結(jié)點的值保存在變量x中的運算為（）。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．設有一個18階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲

到一維數(shù)組B中（數(shù)組下標從1開始），則數(shù)組中第33號元素對應于矩陣中的元素是（）。(矩陣中的第1個元素是a1,1）

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

14．設有一個20階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標從1開始），則數(shù)組中第38號元素對應于矩陣中的元素是（）。(矩陣中的第1個元素是a1,1）

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

15．設有一個17階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲

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

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

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

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

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

18．一棵有n個結(jié)點，采用鏈式存儲的二叉樹中，共有（）個指針域被有效使用（即指針域為非空）。

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

19．一棵采用鏈式存儲的二叉樹中有n個指針域為空,該二叉樹共有（）個結(jié)點。A．n+1B．nC．n-1D．n-2

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

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

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

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

f

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

種頂點序列為（）。

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），利用快速排序，以

第一個關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(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），利用快速排序，以第

一個關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(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．線性表以（）方式存儲，能進行折半查找。

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

16

二、填空題

1．數(shù)據(jù)元素之間的抽象關(guān)系稱為________結(jié)構(gòu)。

2.數(shù)據(jù)的規(guī)律結(jié)構(gòu)在計算機中的表示稱為________結(jié)構(gòu)。

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

4.求兩個n階矩陣的乘積，算法的基本操作為________，時間繁雜度為________。5．設有一個長度為25的順序表,第8號元素到第25號元素依次存放的值

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

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

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

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

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

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

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

11．向一個棧頂指針為top的鏈棧中插入一個p所指結(jié)點時，可執(zhí)行________操作。(填兩條語句,結(jié)點的指針域為next)

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

________。(結(jié)點的指針域為next,數(shù)據(jù)域為data)

13．在一個帶頭結(jié)點的鏈隊中，設front和rear分別為隊頭和隊尾指針，則刪除一個結(jié)點

的操作為p=front->next;_______=p->next;(結(jié)點的指針域為next,p為輔助用指針)14循環(huán)鏈隊列中，設front和rear分別為隊頭和隊尾指針，(最多元素為MaxSize,采用少用一個元素的模式),判斷循環(huán)鏈隊列為滿的條件為________。

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

16．對稀疏矩陣進行壓縮存儲,可采用三元組表，一個6行7列的稀疏矩陣A相應的三元組表共有8個元素,則矩陣A共有_______個零元素。

17.一棵3度的樹，其中3度結(jié)1個，2度結(jié)2個，1度結(jié)2個，則該樹共有_______個葉結(jié)點。

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

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

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

_______個1度結(jié)點

21．如圖3所示的二叉樹，其中序遍歷序列為_________。

17

21578圖3

22．如圖2所示的二叉樹，其先序遍歷序列為_________。

21578圖4

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

24．在查找表中，通過記錄的某關(guān)鍵字能唯一地確定一個記錄，該關(guān)鍵字稱為_________。三、綜合題1．

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

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

18

34693469

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

（3）鏈接存儲上述哈夫曼樹，結(jié)點中共有多少個指針域為空,說明理由.3．（1）簡述拓撲排序的步驟。

（2）說明有向圖的拓撲序列不一定是唯一的原因。（3）如何利用拓撲排序算法判定圖是否存在回路。

（4）設有向圖G如下，寫出首先刪除頂點1的3種拓撲序列。

12345圖5

6

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

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

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

(3)請在該樹中再插入一個結(jié)點3.5作為葉結(jié)點，并使它依舊是一棵二叉排序樹。

A1A2A3A4A5A8A6A7A9圖6

19

5．設有序表為（21，22，23，24，25，26，27，28，29，30，31,32），元素的下標從0開始。

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

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

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

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

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

四、程序填空題

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

設待序的記錄序列存放在a[start],…a[end]中，按記錄的關(guā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.設有一個頭指針為head的不帶頭結(jié)點單向鏈表,且p、q是指向鏈表中結(jié)點類型的指針變量，p指向鏈表中某結(jié)點a（設鏈表中沒有結(jié)點的數(shù)據(jù)域與結(jié)點a的數(shù)據(jù)域一致）,寫出相關(guān)語句

(1).使該單向鏈表成為單向循環(huán)鏈表(2)刪去a結(jié)點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)___

期末綜合練習二答案

一、單項選擇題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．物理（存儲）

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