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

數(shù)據(jù)結(jié)構(gòu)期末綜合練習(xí)

2023年12月

期末練習(xí)一

一、單項選擇題

1.一種邏輯結(jié)構(gòu)在存儲時（）。

A.只要存儲數(shù)據(jù)元素間的關(guān)系B.只能采用一種存儲結(jié)構(gòu)

C.可采用不同的存儲結(jié)構(gòu)1）.只要存儲數(shù)據(jù)元素的值

2.同一種邏輯結(jié)構(gòu)（）。

A.只能有唯一的存儲結(jié)構(gòu)B.可以有不同的存儲結(jié)構(gòu)

C.只能表達(dá)某一種數(shù)據(jù)元素之間的關(guān)系D.以上三種說法均不對的

3.對鏈表，以下敘述中對的的是（）。

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

C.插入刪除元素的操作一定要要移動結(jié)點D.可以通過下標(biāo)對鏈表進(jìn)行直接訪問

4.鏈表所具有的特點是（）。

A.可以隨機(jī)訪問任一結(jié)點B.占用連續(xù)的存儲空間

C.插入刪除元素的操作不需要移動元素結(jié)點D.可以通過下標(biāo)對鏈表進(jìn)行直接訪問

5.線性表在存儲后，假如相關(guān)操作是:規(guī)定已知第i個結(jié)點的位置訪問該結(jié)點的前驅(qū)結(jié)點，則

采用（）存儲方式是不可行的。

A.單鏈表B.雙鏈表C.單循環(huán)鏈表D.順序表

6.數(shù)據(jù)的物理結(jié)構(gòu)（）。

A.與數(shù)據(jù)的邏輯結(jié)構(gòu)無關(guān)B.僅僅涉及數(shù)據(jù)元素的表達(dá)

C.只涉及數(shù)據(jù)元素間關(guān)系的表達(dá)D.涉及數(shù)據(jù)元素的表達(dá)和關(guān)系的表達(dá)

7.棧和隊列的共同特點是（）o

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

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

8.線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（）的關(guān)系。

A.一對一B.一對多

9.元素2,4,6,8按順序依次進(jìn)棧，按該棧的的也許輸出序列依次入隊列，該隊列的也許輸

出序列是（）（進(jìn)棧出?？梢越惶孢M(jìn)行）。

A.8,6,2,4B.8,4,2,6

C.6,2,4,8D.8,6,4,2

10.以下表中可以隨機(jī)訪問的是（）。

A.單向鏈表B.雙向鏈表

C.單向循環(huán)鏈表D.順序表

11.在一個不帶頭結(jié)點的鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，則從該對列中刪除一

個結(jié)點并把結(jié)點的值保存在變量x中的運(yùn)算為（）。

A.x=r->data；r=r->next；B.r=r->next;x=r->data

C.x=f->data;f=f->next;D.f=f->next;x=f->data

12.算法的時間復(fù)雜度與（）有關(guān)。

A.所使用的計算機(jī)B.與計算機(jī)的操作系統(tǒng)

C.與算法自身D.與數(shù)據(jù)結(jié)構(gòu)

13.設(shè)有一個20階的對稱矩陣A,采用壓縮存儲的方式,將其下三角部分以行序為主序存儲

到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則數(shù)組中第38號元素相應(yīng)于矩陣中的元素是

（）。

A.3io,8B.a?,eC.ao,2D.a

8,5

14.設(shè)有一個長度為n的順序表，要刪除第i個元素需移動元素的個數(shù)為（）。

A.n-i+1B.n_iC.n-i一1D.i

15.在C語言中，分別存儲"S"和's',各需要占用（）字節(jié)。

A.一個和兩個B.兩個C.一個D.兩個和一個

16.在一個單鏈表中，p、q分別指向表中兩個相鄰的結(jié)點,且q所指結(jié)點是p所指結(jié)點的直

接后繼，現(xiàn)要刪除q所指結(jié)點，可用的語句是（）。

A.p=q->nextB.p—>next=qC,p—>next=q->nextD.q->n

ext=NULL

17.一棵有n個結(jié)點,采用鏈?zhǔn)酱鎯Φ亩鏄渲?共有（）個指針域被有效使用（即指針

域為非空）。

A.n+1B.nC.n_1D.n-2

18.從一個棧頂指針為top的鏈棧中刪除一個結(jié)點時,用變量x保存被刪結(jié)點的值，則執(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;

19.在一棵二叉樹中，若編號為i的結(jié)點存在雙親結(jié)點，則雙親結(jié)點的順序編號為（）。

A.i/2.0B.i/2向下取整C.2i+1

D.i+2

20.在一個鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，則刪除一個結(jié)點的運(yùn)算為（）o

A.r=f—>next；B.r=r->next;C.f=f—>next；D.f=

r->next;

21.設(shè)一棵哈夫曼樹共有2n+1個結(jié)點，則該樹有（）個非葉結(jié)點。

A.nB.n+1C.n-lD.2n

22.一個棧的進(jìn)棧序列是a,b,c,d,e,則棧的不也許輸出序列是（）（進(jìn)棧出棧可以交

替進(jìn)行）。

A.dceabB.edcbaC.decbaD.abcde

23.一棵完全二叉樹共有4層，且第4層上有2個結(jié)點，該樹共有（）個非葉子結(jié)點

（根為第一層）。

A.5B.4C.3D.9

24.有一個長度為10的有序表，按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的

平均比較次數(shù)為（）。

A.26/10B.29/10C.29/9D.31/10

25.如圖1所示的一個圖,若從頂點a出發(fā),按廣度優(yōu)先搜索法進(jìn)行遍歷,則也許得到的一種頂

點序列為（）。

A.abedfcB.acfebdC.aebcdfD.aebcfd

圖1

26.排序算法中，從未排序序列中依次取出元素與己排序序列（初始為空）中的元素進(jìn)行比較

（規(guī)定比較次數(shù)盡量少），然后將其放入己排序序列的對的位置的方法是（）=

A.冒泡B.直接插入C.折半插入D.選擇排序

27.一組記錄的關(guān)鍵字序列為（56,30,89,66,48,50,94,87,100）,運(yùn)用快速排序，以

第一個關(guān)鍵字為分割元素，通過一次劃分后結(jié)果為（）。

A.30,50,48,56,66,89,94,100,87B.50,30,48,56,6

6,89,94,87,100

C.48,30,50,56,66,89,94,87,1001）.50,30,48,66,56,89,94,8

7,100

28.設(shè)有一個10階的對稱矩陣A,采用壓縮存儲的方式，將其下三角部分以行序為主存儲到

一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素A&5在一維數(shù)組B中的下標(biāo)是（）。

A.33B.32C.85D.41

29.線性表以（）方式存儲，能進(jìn)行折半查找。

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

C.多對多D.每一個元素都有一個直接前驅(qū)和一個直接后繼

30.在一個無向圖中，所有頂點的度數(shù)之和等于邊數(shù)的（）倍。

A.3B.2.5C,1.5D.2

二、填空題

1.數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的表達(dá)稱為結(jié)構(gòu)。

2.棧和隊列的操作特點分別是和o

3.求兩個n階矩陣的乘積，算法的基本操作為，時間復(fù)雜度為o

4.結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為結(jié)構(gòu)。

5.設(shè)有一個長度為25的順序表，第8號元素到第25號元素依次存放的值為8,9,10,11,-2

5,

某人想要在第8個元素前插入1個元素7（也就是插入元素作為新表的第8個元素），他

的做法是從第8號元素開始,直到第25號元素依次向后移動1個位置,然后把7存放在

8號位置，其結(jié)果是新表中第25號元素的值為o

6.根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性，通?？煞譃榧?、線性、、四類基本結(jié)

構(gòu)。

7.在雙向鏈表中，要在p所指的結(jié)后插入q所指的結(jié)點（設(shè)q所指的結(jié)點已賦值），

其中所用的一條語句（p->next）->prior=q；的功能是使P所指結(jié)點的

_指向qo

8.規(guī)定在n個數(shù)據(jù)元素中找其中值最大的元素，設(shè)基本操作為元素間的比較。則比較的次數(shù)

和算法的時間復(fù)雜度分別為和o

9.設(shè)有一個帶頭結(jié)點的，頭指針為head的單向鏈表,P指向表中某一個結(jié)點，且有

p->next==NULL,現(xiàn)要刪除頭結(jié)點，并使該單向鏈表構(gòu)導(dǎo)致單向循環(huán)鏈表，通過

操作head=head->next;。

10.在一個單向鏈表中p所指結(jié)點之后插入一個s所指向的結(jié)點時，應(yīng)執(zhí)行

和p->next=s；的操作。

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

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

12.在二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，通常每個結(jié)點中設(shè)立三個域，它們是值域、

______________________________O

13循環(huán)鏈隊列中，設(shè)fr。nt和rear分別為隊頭和隊尾指針，（最多元素為MaxSize,采用少

用一

個元素的模式），判斷循環(huán)鏈隊列為滿的條件為o

14.一棵二叉樹中順序編號為i的結(jié)點，若它存在左、右孩子，則左、右孩子編號分別為一

15.對稀疏矩陣進(jìn)行壓縮存儲，可采用三元組表，一個6行7列的稀疏矩陣A相應(yīng)的三元組

表共有8個元素，則矩陣A共有個零元素。

16.向一個棧頂指針為h的鏈棧中插入一個s所指結(jié)點時,可執(zhí)行s->next=h;和。

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

_____個葉結(jié)點。

18.在一個鏈隊中，設(shè)f和r分別為隊頭和隊尾指針，則插入s所指結(jié)點的操作為和

r=s;（結(jié)點的指針域為next）

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

____________個［度結(jié)點

20.設(shè)有一棵深度為4的完全二叉樹，第四層上有5個結(jié)點，該樹共有個結(jié)點。（根

所在結(jié)點為第1層）

21.如圖2所示的二叉樹，其先序遍歷序列為。

圖2

22.對稀疏矩陣進(jìn)行壓縮存儲，矩陣中每個非零元素相應(yīng)的三元組涉及該元素的

和三項信息。

23.在查找表中，通過記錄的某關(guān)鍵字能唯一地擬定一個記錄，該關(guān)鍵字稱為

____O

24.在對一組記錄(55,39,97,22,16,73,65,47,88)進(jìn)行直接插入排序時，當(dāng)把第7個記

錄65插入到有序表時，為尋找插入位置需比較次。

三、綜合題

1.(1)對給定權(quán)值3,1,4,4,5,6,構(gòu)造深度為5的哈夫曼樹。(設(shè)根為第1層)

(2)求樹的帶權(quán)途徑長度。

(3)鏈接存儲上述哈夫曼樹，結(jié)點中共有多少個個指針域為空，說明理由.

2.

(1)以2,3,4,7,8,9作為葉結(jié)點的權(quán)，構(gòu)造一棵哈夫曼樹(規(guī)定每個結(jié)點的左子樹根結(jié)

點的權(quán)小于等于右子樹根結(jié)點的權(quán))，給出相應(yīng)權(quán)重值葉結(jié)點的哈夫曼編碼。

(2)一棵哈夫曼樹有n個葉結(jié)點，它一共有多少個結(jié)點?簡述理由？

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

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

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

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

Al

圖3

4.一組記錄的關(guān)鍵字序列為(46,79,56,38,40,84)

(1)運(yùn)用快速排序的方法，給出以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果(給出逐次互換元

素的過程，規(guī)定以升序排列)

(2)對上述序列用堆排序的方法建立大根堆，規(guī)定以二叉樹逐次描述建堆過程。

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

(1)畫出對上述有序表進(jìn)行折半查找所相應(yīng)的鑒定樹(規(guī)定以數(shù)據(jù)元素作為樹結(jié)點)

(2)給出二叉排序樹的定義，針對上述折半查找所相應(yīng)的鑒定樹的構(gòu)造過程，說明鑒定樹

是否是二叉排序樹(設(shè)樹中沒有相同結(jié)點)？

(3)為了查找元素5.5,通過多少次元素間的比較才干擬定不能查到？

6.設(shè)查找表為(50,60,75,85,96,98,105,110,120,130)

(1)說出進(jìn)行折半查找成功查找到元素120需要進(jìn)行多少次元素間的比較？

(2)為了折半查找元素95,通過多少次元素間的比較才干擬定不能查到？

(3)畫出對上述有序表進(jìn)行折半查找所相應(yīng)的鑒定樹(規(guī)定以數(shù)據(jù)元素作為樹結(jié)點)

四、程序填空題

1.以下函數(shù)為直接選擇排序算法，對a[l…a[n]中的記錄進(jìn)行直接選擇排序，完畢程

序中的空格

typedefstruct

{intkey;

}NODE;

voidseIsort(N0DEa[],intn)

(

?inti,j,k;

NODEtemp;

for(i=1;i<=_⑴；i++)

(

8k=i;

。for(j=i+1；j<=(2)；j++)

?if(a[j],key<aEk].key)_(3)；

?if(i!=k)

{

emp=a[i];

6o___(4);

8(5)；

00

。}

)

2.以下是用尾插法建立帶頭結(jié)點且有n個結(jié)點的單向鏈表的程序，結(jié)點中的數(shù)據(jù)域從

前向后依次為1,2,3,……,n,完畢程序中空格部分。

NODE*create(n)

{NODE*head,*p,*q;

inti;

p=(NODE*)ma11oc(sizeof(NODE))；

head=(1);(2);p->next=NULL;/*建立頭結(jié)點*/

for(i=l;i<=n;i++)

{P=_Q)___________________；

p-^data=i；

pTnext=NULL；

q->next=(4);

(5);

return(head);

3.設(shè)有一個頭指針為head的不帶頭結(jié)點單向鏈表，且p、q是指向鏈表中結(jié)點類型的

指針變量，p指向鏈表中某結(jié)點a(設(shè)鏈表中沒有結(jié)點的數(shù)據(jù)域與結(jié)點a的數(shù)據(jù)域相同),

寫出相關(guān)語句

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

(2)刪去a結(jié)點

q=p;x=p->data;

whi1e(q—>next!=NULL)q=q—>next；

_(1)—

q=p;p=p->next；

whi1e(p->data!=x)

{q=p；

-(2)—

)

一(3)

4.以下程序是中序遍歷二叉樹的遞歸算法的程序,完畢程序中空格部分(樹結(jié)構(gòu)中左、右

指針域分別為1eft和right,數(shù)據(jù)域data為字符型,BT指向根結(jié)點)。

voidInorder(structBTreeNode*BT)

{if(BT!=NULL){

_￡U______________________；

(2);

J_3J_______________________；

)

)

期末復(fù)習(xí)一答案

一、單項選擇題

1.C2.B3.A4.C5.A6.D7.C8.A9.D10.D11.C

12.C13.C14.B15.D16.C17.C18.A19.B20.C2

1.A22.A23.B24.B25.C26.C27.B28.A29.C3

0.D

二、填空題

1.物理(存儲)

2.后進(jìn)先出、先進(jìn)先出

3.乘法0(/)

4.圖狀(網(wǎng)狀)

5.8

6.樹形圖狀

7.直接前驅(qū)的左指針

8.n-1,0(n)、

9.p->next=head;

10.s->next=p->next；

11.d=top->data；top=top—>next;

12.左指針右指針

13.front==(rear+1)%MaxSize

14.2i2i+l

15.34

16.h=s;

17.13

18.r->next=s；

19.1

20.12

21.

22.行下標(biāo)、列下標(biāo)、非零元素值

23.主關(guān)鍵字

24.3

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

圖4

(2)WPL=3*4+l*4+4*3+6*2+4*2+5*2=58

(3)共11個結(jié)點,22個指針域，除根結(jié)點外，每個結(jié)點相應(yīng)一個指針域.，共10個指針域非空,

有22-10=12個空指針域,

2.

(1)

圖5

2:1110

3:1111

4：110

7：00

8:01

9:10

(2)2n-l個，由于非葉結(jié)點數(shù)比葉結(jié)點數(shù)少一個。

3.

(1)A1A2A4A7A8A5A9A3A6

(2)

(3)

圖6

4.

(1)初始序列

同79,56,38,40,84

40,79,56,38回，84

40,國，56,38,79,84

40,38,56,畫,79,84

40,38,園56,79,84

40,38國56,79,84

圖7

(2)二叉排序樹或者是一棵空樹，或者是一棵具有下列性質(zhì)的二叉排：若它的左子樹

非空，則左子樹的所有結(jié)點的值都小于它的根結(jié)點的值;若它的右子樹非空，則右子

樹的所有結(jié)點的值都大于(若允許結(jié)點有相同的值，則大于等于)它的根結(jié)點的值；

左，右子樹也是一棵二叉排序樹，按定義鑒定樹是二叉排序樹。

(3)3次

6.

(1)3次

(2)4次

(3)

圖8

四、程序填空題

1.(l)n-l

(2)n

(3)k=j

(4)a[i]=a[k]

(5)a[k]=temp

(1)P

(2)q=p

(3)(NODE*)ma11oc(sizeof(NODE))

(4)p

(5)q=p

3.

(1)q->next=head;

(2)p=p—>next；

(3)q->next=p->next;

4.

(1)Inorder(BT->left)

(2)printf(,BT->data)

(3)Inorder(BT->right)

期末練習(xí)二

一、單項選擇題

1.結(jié)構(gòu)中的元素之間存在一對多的關(guān)系是（）o

A.集合B.線性結(jié)構(gòu)

C.樹形結(jié)構(gòu)D.圖狀結(jié)構(gòu)

2.在C語言中，順序存儲長度為3的字符串，需要占用（）個字節(jié)。

A.4B.3C.6D.12

3.對不帶頭結(jié)點的單向鏈表，判斷是否為空的條件是（）（設(shè)頭指針為head）。

A.head==NULLB.head->next==NULL

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

4.串函數(shù)StrCat（a,b）的功能是進(jìn)行串（）。

A.比較B.復(fù)制C.賦值D.連接

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.一棵有n個結(jié)點采用鏈?zhǔn)酱鎯Φ亩鏄渲?，共有（）個指針域為空。

A.n+1B.nC.n-lD.n-2

7.一個棧的進(jìn)棧序列是1,2,3,4,5,則棧的不也許輸出序列是（）（進(jìn)棧出?？梢越?/p>

替進(jìn)行）。

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

8.設(shè)一棵哈夫曼樹共有n個非葉結(jié)點,則該樹有（）個葉結(jié)點。

A.nB.n+1C.n-lD.2n

9.一個隊列的入隊序列是2,4,6,8,按該隊列的輸出序列使各元素依次入棧，該棧的也許

輸出序列是（）。

A.8,6,4,2B.6,2,4,8

C.8,4,2,6D.8,2,4,6

10.從一個棧頂指針為top的鏈棧中刪除一個結(jié)點時，用變量x保存被刪結(jié)點的值，則執(zhí)行

（）。

A.x=top->data;top=topfnext；B.x=top—>data;

C.top=top—>next;x=top->data;D.top=top->next;x=data；

11.在一個鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，已生成一個結(jié)點P,要為結(jié)點P賦

值X,并入隊的運(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.一棵完全二叉樹共有5層，且第5層上有六個結(jié)點，該樹共有（）個結(jié)點。

A.30B.20C.21I）.23

13.設(shè)有一個25階的對稱矩陣A,采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到

一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素.a7,6在一維數(shù)組B中的下標(biāo)是（）。

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

14.在一個無向圖中，所有頂點的度數(shù)之和等于邊數(shù)的（）倍。

A.3B.2.5C.1.5D.2

15.以下程序段的結(jié)果是c的值為（）。

chara[5]="1236789"，int*p=a,intc=0;

while（*p++）c++;

A.8.B.7C.10D.12

16.已知如圖1所示的一個圖,若從頂點修出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則也許得到的

一種頂點序列為（）o

A.VMV4V8V5V3V6V7B.VMVMVMV6V7

C.V1V2V4V8V3V5V6V7D.%V3V6V7V2V4V5V8

圖1

17.一棵有23個結(jié)點，采用鏈?zhǔn)酱鎯Φ亩鏄渲校灿校ǎ﹤€指針域為空。

A.24B.25C.23D.45

18.已知如圖2所示的一個圖，若從頂點a出發(fā),按廣度優(yōu)先搜索法進(jìn)行遍歷，則也許得到的一

種頂點序列為（）。

A.abcedfB.abcefdC.aebcfdD.acfdeb

19.在一棵二叉樹中，若編號為i的結(jié)點是其雙親結(jié)點的左孩子，則雙親結(jié)點的順序編號為

（）。

A.i/2B.2i-lC.2i+lD.i/

2-1

20.對二叉排序樹進(jìn)行（）遍歷，可以使遍歷所得到的序列是有序序列.

A.按層次B.后序C.中序D.前序

21.設(shè)一棵哈夫曼樹共有2n+1個葉結(jié)點,則該樹有（）個葉結(jié)點。

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

22.在有序表｛2,4,7,14,34,43,47,64,75,80,90,97,120｝中，用折半查找法查找

值80時，經(jīng)（）次比較后查找成功。

A.4B.2C.3D.5

23.已知如圖3所示的一個圖,若從頂點a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則也許得到的

一種頂點序列為（）。

A.abecdfB.acfebdC.aebcfdD.aedbfc

24.有一個長度為9的有序表,按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的平

均比較次數(shù)為（）。

A.25/10B.25/9C.20/9D.17/9

25.已知如圖4所示的一個圖,若從頂點B出發(fā)，按廣度優(yōu)先法進(jìn)行遍歷,則也許得到的一種

頂點序列為（）。

A.BADEHCFGB.ADEHCGFC.BADECHFGD.BADEHCFG

圖4

26.排序算法中，從未排序序列中依次取出元素與已排序序列（初始為空）中的元素進(jìn)行比

較（規(guī)定比較次數(shù)盡量少），然后將其放入已排序序列的對的位置的方法是（）。

A.冒泡B.直接插入C.折半插入D.選擇排序

27.一組記錄的關(guān)鍵字序列為（46,38,56,40,79,84）,運(yùn)用快速排序，以第一個關(guān)鍵

字為分割元素，通過一次劃分后結(jié)果為（）。

A.40,38,46,79,56,84B.40,38,46,56,79,84

C.40,38,46,84,56,79D.38,40,46,56,79,84

28.一組記錄的關(guān)鍵字序列為（46,79,56,38,40,84）,運(yùn)用快速排序，以第一個關(guān)

鍵字為分割元素,通過一次劃分后結(jié)果為（）。

A.40,38,46,79,56,84B.40,38,46,56,79,84

C.40,38,46,84,56,79D.38,40,46,56,79,84

29.在有序表｛21,23,28,33,43,45,46,73,77,78,89,99,106｝中，用折半查找值

43時，經(jīng)（）次比較后查找成功。

A.6B.3C.8D.4

30.排序方法中,從尚未排序序列中挑選元素,并將其依次放入已排序序列（初始為空）的一端

的方法，稱為（）排序。

A.歸并B.插入C.快速D.選擇

二、填空題

1.本書中介紹的樹形結(jié)構(gòu)和屬非線性結(jié)構(gòu)。

2.在二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，通常每個結(jié)點中設(shè)立三個域，它們是、、

右指針。

3.設(shè)有一個長度為18的順序表，要在第4個元素之前插入2個元素（也就是插入元素作為

新表的第5個和第4個元素），則最少要移動元素的個數(shù)為（）。

4.一棵二叉樹中順序編號為i的結(jié)點，若它存在左、右孩子，則左、右孩子編號分別為

5.在雙向鏈表中，要刪除p所指的結(jié)點,可以先用語句（p->prior）—>next=p—>next;然

再用語句。

6.串的兩種最基本的存儲方式是和。

7.在一個單向鏈表中p所指結(jié)點之后插入一個s所指向的結(jié)點時,應(yīng)執(zhí)行s->next=p->next;

和的操作.

8.一棵有2n-1個結(jié)點的二叉樹，其每一個非葉結(jié)點的度數(shù)都為2，則該樹共有個葉

結(jié)點。

9.一個棧和一個隊列的輸入序列都為abcdefg，它們也許有相同的輸出序列嗎？。

（若沒有則回答沒有，若有則寫出序列,進(jìn)棧出?？梢越惶孢M(jìn)行）。

10.對于一棵具有n個結(jié)點的二叉樹，其相應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)中共有個指針域為空。

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

o（結(jié)點的數(shù)據(jù)域為data）

12.遍歷二叉排序樹可得到一個有序序列。

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

斷循環(huán)鏈隊列為空的條件是為真。

14.如圖5所示的二叉樹，其后序遍歷序列為。

圖5

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

構(gòu)體類型）變量，a中的一個成員項是三元組類型的結(jié)構(gòu)體數(shù)組data,按書中定義,

若a.data[0].i=2;a.data[O].j=3;a.data[0].v=16;它提供的A數(shù)組的相關(guān)信息有

16.如圖6所示的二叉樹，其先序遍歷序列為

圖6

17.設(shè)有一棵深度為5的完全二叉樹，該樹共有20個結(jié)點，第五層上有個葉結(jié)點。

（根所在結(jié)點為第1層）

18.圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是的。（回答對的

或不對的）

19.中序遍歷樹可得到一個有序序列。

20.二叉樹為二叉排序的充足必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩

子的值。這種說法是的。（回答對的或不對的）

21.如圖7所示的二叉樹，其后序遍歷序列為o

A

圖7

22.對記錄序列排序是指按記錄的某個關(guān)鍵字排序，記錄序列按排序結(jié)果是唯

一的。

23.給定一組權(quán)重值，構(gòu)造哈夫曼樹，哈夫曼樹的高度一定是唯一的，這種說法是

的。(回答對的或不對的)

24.按某關(guān)鍵字對記錄序列排序，若__________________在排序前和排序后仍保持它們的前

后關(guān)系，則排序算法是穩(wěn)定的，否則是不穩(wěn)定的。

三、綜合題

1.(1)說明什么是頂點活動網(wǎng)(AOV網(wǎng))和拓?fù)湫蛄?/p>

(2)設(shè)有向圖G如下，寫出3種拓?fù)湫蛄校?/p>

(3)在圖G中增長一條邊，使圖G僅有一條拓?fù)湫蛄?/p>

圖8

2.設(shè)查找表為(16,15,20,53,64,7),

(1)用冒泡法對該表進(jìn)行排序(規(guī)定升序排列)，寫出每一趟的排序過程，通常對n個元

素進(jìn)行冒泡排序要進(jìn)行多少趟冒泡?第j趟要進(jìn)行多少次元素間的比較？

(2)在排序后的有序表的基礎(chǔ)上，畫出對其進(jìn)行折半查找所相應(yīng)的鑒定樹.(規(guī)定以數(shù)據(jù)元

素作為樹結(jié)點)

3.如下是一棵二叉排序樹,A1,A2,…A9代表1,2,3,...9中各個不同數(shù)字，

(1)給出對該樹中序遍歷的結(jié)果

(2)A3.A5,A7的值各為多少？

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

4.

(1)設(shè)有查找表{5,14,2,6,18,7,4,16,3},依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹。

(2)說明如何由序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果，對上述二叉排序給出中序遍

歷的結(jié)果。

5.

(1)設(shè)有查找表{17,26,14,16,15,30,18,19,28},依次取表中數(shù)據(jù)構(gòu)造一棵二叉

排序樹.

(2)對上述二叉樹給出后序遍歷的結(jié)果

(3).對上述二叉樹給出中后序遍歷的結(jié)果

(4))在上述二叉樹中查找元素15共要進(jìn)行多少次元素的比較?

6.(1)對給定權(quán)值2,1,3,3,4,5,構(gòu)造哈夫曼樹。

(2)同樣用上述權(quán)值構(gòu)造另一棵哈夫曼樹，使兩棵哈夫曼樹有不同的高度，并分別求兩

棵樹的帶權(quán)途徑長度。

四、程序填空題

1.以下函數(shù)是二叉排序樹的查找算法，若二叉樹為空，則返回根結(jié)點的指針，否則，返回

值是指向樹結(jié)點的結(jié)構(gòu)指針P(查找成功P指向查到的樹結(jié)點，不成功P指向為NULL)完

畢程序中的空格

typedefstructBnode

{intkey;

structBnode*left；

structBnode*right；

}Bnode；

Bnode*BSearch(Bnode*bt,intk)

/*bt用于接受二叉排序樹的根結(jié)點的指針,k用以接受要查找的關(guān)鍵字*/

{Bnode*p;

if(bt==____(1))

return(bt);

P=bt;

whi1e(p->key!=_(2))。

{if(k<p—>key)?。

—(3);

else(4)了

if(p==NULL)break;

)

return(____(5))；

}

)

3.設(shè)有一個頭指針為head的不帶頭結(jié)點單向鏈表,P、q是指向鏈表中結(jié)點類型的指

針變量，p指向鏈表中結(jié)點a,(設(shè)鏈表中沒有結(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；

_⑵_____

}

s->next=p;

_(3)—

答案

一、單項選擇題

1.C2.A3.A4.D5.D6.A7.B8.B9.A10.A11.B12.C

13.D14.D15.B16.A17.A18.B19.A20.C21.C22.A

23.D24.B25.C26.C27.B28.B29.B30.D

二、填空題

1.圖狀結(jié)構(gòu)

2.值域左指針

3.15

4.2i和2i+l

5.(p->next)->prior=p->prior；

6.順序存儲鏈?zhǔn)酱鎯?/p>

7.p—>next=s;

8.n9.abcdefg

10.n+1

11.d=top->data;

12.中序

13.front==rear

14.gdbeihfca

15.A的第一個非零元素的下標(biāo)為2,3,元素為16

16.abdefcg

17.5

18.對的

19.二叉排序

20.不對的

21.

22.主關(guān)鍵字

23.不對的

24.關(guān)鍵字相等的記錄

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

1.

⑴原序列16152053647

71516205364

I、)

圖10

2.

(1)原序列16152053647

71516205364

(2)

圖11

(3)平均查找長度二(1*1+2*2+3*3)/6=14/6

3.

(1)

圖12

(2)中序遍歷

中序2,3,4,5,6,7,14,16,18

4.

圖13

(2)中序遍歷

中序2,3,4,5,6,7,14,16,18

圖15

wp12=45

wpll=45

四、程序填空題

1.(1)NULL

(2)k

(3)p=p->left

(4)p=p—>right

(5)p

2.

(1)&a

⑵d-next=NULL

(3)p->data

(4)p=p->next

(5)p!=NULL

3.

(1)q—>next!=NULL

(2)p=p->next;

(3)q->next=s；

4.

(1)Postorder(BT->1eft)

(2)Postorder(BT->right)

(3)printf("%c”,BT-〉data)

期末練習(xí)三

一、單項選擇題

1.數(shù)據(jù)結(jié)構(gòu)在計算機(jī)內(nèi)存中的表達(dá)是指（）。

A.數(shù)據(jù)元素之間的關(guān)系B.數(shù)據(jù)的存儲結(jié)構(gòu)

C.數(shù)據(jù)元素的類型D.數(shù)據(jù)的邏輯結(jié)構(gòu)

2.在數(shù)據(jù)結(jié)構(gòu)和算法中，與所使用的計算機(jī)有關(guān)的是（）o

A.數(shù)據(jù)元數(shù)間的抽象關(guān)系B.數(shù)據(jù)的存儲結(jié)構(gòu)

C.算法的時間復(fù)雜度I）.數(shù)據(jù)的邏輯結(jié)構(gòu)

3.結(jié)構(gòu)中的元素之間存在多對多的關(guān)系是（）。

A.集合B.線性結(jié)構(gòu)

C.樹形結(jié)構(gòu)1）.圖狀結(jié)構(gòu)

4.對順序表，以下敘述中對的的是（）。

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

B.各個數(shù)據(jù)元素的首地址是連續(xù)的

C.數(shù)據(jù)元素不能隨機(jī)訪問

D.插入操作不需要移動元素

5.設(shè)有一個長度為20的順序表，要在第5個元素之前插入1個元素（也就是插入元素作為

新表的第5個元素），則移動元素個數(shù)為（）。

A.15B.16C.5D.4

6.設(shè)有一個長度為25