2023年數(shù)據(jù)結構(本)期末綜合練習(12月)

數(shù)據(jù)結構期末綜合練習

2023年12月

期末練習一

一、單項選擇題

1.一種邏輯結構在存儲時（）。

A.只要存儲數(shù)據(jù)元素間的關系B.只能采用一種存儲結構

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

2.同一種邏輯結構（）。

A.只能有唯一的存儲結構B.可以有不同的存儲結構

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

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

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

C.插入刪除元素的操作一定要要移動結點D.可以通過下標對鏈表進行直接訪問

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

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

C.插入刪除元素的操作不需要移動元素結點D.可以通過下標對鏈表進行直接訪問

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

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

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

6.數(shù)據(jù)的物理結構（）。

A.與數(shù)據(jù)的邏輯結構無關B.僅僅涉及數(shù)據(jù)元素的表達

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

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

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

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

8.線性結構中數(shù)據(jù)元素的位置之間存在（）的關系。

A.一對一B.一對多

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

出序列是（）（進棧出?？梢越惶孢M行）。

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

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

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

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

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

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

個結點并把結點的值保存在變量x中的運算為（）。

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.算法的時間復雜度與（）有關。

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

C.與算法自身D.與數(shù)據(jù)結構

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

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

（）。

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

8,5

14.設有一個長度為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分別指向表中兩個相鄰的結點,且q所指結點是p所指結點的直

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

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

ext=NULL

17.一棵有n個結點,采用鏈式存儲的二叉樹中,共有（）個指針域被有效使用（即指針

域為非空）。

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

18.從一個棧頂指針為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;

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

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

D.i+2

20.在一個鏈隊中，假設f和r分別為隊頭和隊尾指針，則刪除一個結點的運算為（）o

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

r->next;

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

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

22.一個棧的進棧序列是a,b,c,d,e,則棧的不也許輸出序列是（）（進棧出?？梢越?/p>

替進行）。

A.dceabB.edcbaC.decbaD.abcde

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

（根為第一層）。

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

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

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

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

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

點序列為（）。

A.abedfcB.acfebdC.aebcdfD.aebcfd

圖1

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

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

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

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

第一個關鍵字為分割元素，通過一次劃分后結果為（）。

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

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

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

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

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

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

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

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

二、填空題

1.數(shù)據(jù)的邏輯結構在計算機中的表達稱為結構。

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

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

4.結構中的數(shù)據(jù)元素存在多對多的關系稱為結構。

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

5,

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

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

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

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

構。

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

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

_指向qo

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

和算法的時間復雜度分別為和o

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

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

操作head=head->next;。

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

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

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

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

12.在二叉樹的鏈式存儲結構中，通常每個結點中設立三個域，它們是值域、

______________________________O

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

用一

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

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

15.對稀疏矩陣進行壓縮存儲，可采用三元組表，一個6行7列的稀疏矩陣A相應的三元組

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

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

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

_____個葉結點。

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

r=s;（結點的指針域為next）

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

____________個［度結點

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

所在結點為第1層）

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

圖2

22.對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素相應的三元組涉及該元素的

和三項信息。

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

____O

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

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

三、綜合題

1.(1)對給定權值3,1,4,4,5,6,構造深度為5的哈夫曼樹。(設根為第1層)

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

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

2.

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

點的權小于等于右子樹根結點的權)，給出相應權重值葉結點的哈夫曼編碼。

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

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

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

提醒：設圖中的樹是二叉排序樹,找出中序遍歷序列與1,2,…9的相應關系

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

Al

圖3

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

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

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

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

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

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

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

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

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

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

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

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

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

四、程序填空題

1.以下函數(shù)為直接選擇排序算法，對a[l…a[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.以下是用尾插法建立帶頭結點且有n個結點的單向鏈表的程序，結點中的數(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;/*建立頭結點*/

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

{P=_Q)___________________；

p-^data=i；

pTnext=NULL；

q->next=(4);

(5);

return(head);

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

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

寫出相關語句

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

(2)刪去a結點

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.以下程序是中序遍歷二叉樹的遞歸算法的程序,完畢程序中空格部分(樹結構中左、右

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

voidInorder(structBTreeNode*BT)

{if(BT!=NULL){

_￡U______________________；

(2);

J_3J_______________________；

)

)

期末復習一答案

一、單項選擇題

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.后進先出、先進先出

3.乘法0(/)

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

5.8

6.樹形圖狀

7.直接前驅的左指針

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.行下標、列下標、非零元素值

23.主關鍵字

24.3

三、綜合應用題

圖4

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

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

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

2.

(1)

圖5

2:1110

3:1111

4：110

7：00

8:01

9:10

(2)2n-l個，由于非葉結點數(shù)比葉結點數(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)二叉排序樹或者是一棵空樹，或者是一棵具有下列性質的二叉排：若它的左子樹

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

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

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

(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)

期末練習二

一、單項選擇題

1.結構中的元素之間存在一對多的關系是（）o

A.集合B.線性結構

C.樹形結構D.圖狀結構

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

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

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

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

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

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

A.比較B.復制C.賦值D.連接

5.在一個不帶頭結點的單循環(huán)鏈表中,p、q分別指向表中第一個結點和尾結點，現(xiàn)要刪除第

一個結點，可用的語句是（）。

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個結點采用鏈式存儲的二叉樹中，共有（）個指針域為空。

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

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

替進行）。

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

8.設一棵哈夫曼樹共有n個非葉結點,則該樹有（）個葉結點。

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的鏈棧中刪除一個結點時，用變量x保存被刪結點的值，則執(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.在一個鏈隊中，假設f和r分別為隊頭和隊尾指針，已生成一個結點P,要為結點P賦

值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.一棵完全二叉樹共有5層，且第5層上有六個結點，該樹共有（）個結點。

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

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

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

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

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

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

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

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

while（*p++）c++;

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

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

一種頂點序列為（）o

A.VMV4V8V5V3V6V7B.VMVMVMV6V7

C.V1V2V4V8V3V5V6V7D.%V3V6V7V2V4V5V8

圖1

17.一棵有23個結點，采用鏈式存儲的二叉樹中，共有（）個指針域為空。

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

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

種頂點序列為（）。

A.abcedfB.abcefdC.aebcfdD.acfdeb

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

（）。

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

2-1

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

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

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

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)先搜索法進行遍歷，則也許得到的

一種頂點序列為（）。

A.abecdfB.acfebdC.aebcfdD.aedbfc

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

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

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

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

頂點序列為（）。

A.BADEHCFGB.ADEHCGFC.BADECHFGD.BADEHCFG

圖4

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

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

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

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

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

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.一組記錄的關鍵字序列為（46,79,56,38,40,84）,運用快速排序，以第一個關

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

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.本書中介紹的樹形結構和屬非線性結構。

2.在二叉樹的鏈式存儲結構中，通常每個結點中設立三個域，它們是、、

右指針。

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

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

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

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

再用語句。

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

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

和的操作.

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

結點。

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

（若沒有則回答沒有，若有則寫出序列,進棧出棧可以交替進行）。

10.對于一棵具有n個結點的二叉樹，其相應的鏈式存儲結構中共有個指針域為空。

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

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

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

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

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

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

圖5

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

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

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

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

圖6

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

（根所在結點為第1層）

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

或不對的）

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

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

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

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

A

圖7

22.對記錄序列排序是指按記錄的某個關鍵字排序，記錄序列按排序結果是唯

一的。

23.給定一組權重值，構造哈夫曼樹，哈夫曼樹的高度一定是唯一的，這種說法是

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

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

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

三、綜合題

1.(1)說明什么是頂點活動網(wǎng)(AOV網(wǎng))和拓撲序列

(2)設有向圖G如下，寫出3種拓撲序列，

(3)在圖G中增長一條邊，使圖G僅有一條拓撲序列

圖8

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

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

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

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

素作為樹結點)

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

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

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

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

4.

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

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

歷的結果。

5.

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

排序樹.

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

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

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

6.(1)對給定權值2,1,3,3,4,5,構造哈夫曼樹。

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

棵樹的帶權途徑長度。

四、程序填空題

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

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

畢程序中的空格

typedefstructBnode

{intkey;

structBnode*left；

structBnode*right；

}Bnode；

Bnode*BSearch(Bnode*bt,intk)

/*bt用于接受二叉排序樹的根結點的指針,k用以接受要查找的關鍵字*/

{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.設有一個頭指針為head的不帶頭結點單向鏈表,P、q是指向鏈表中結點類型的指

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

寫出相關語句

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

(2)插入結點s,使它成為a結點的直接前驅

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.圖狀結構

2.值域左指針

3.15

4.2i和2i+l

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

6.順序存儲鏈式存儲

7.p—>next=s;

8.n9.abcdefg

10.n+1

11.d=top->data;

12.中序

13.front==rear

14.gdbeihfca

15.A的第一個非零元素的下標為2,3,元素為16

16.abdefcg

17.5

18.對的

19.二叉排序

20.不對的

21.

22.主關鍵字

23.不對的

24.關鍵字相等的記錄

三、綜合應用題

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)

期末練習三

一、單項選擇題

1.數(shù)據(jù)結構在計算機內存中的表達是指（）。

A.數(shù)據(jù)元素之間的關系B.數(shù)據(jù)的存儲結構

C.數(shù)據(jù)元素的類型D.數(shù)據(jù)的邏輯結構

2.在數(shù)據(jù)結構和算法中，與所使用的計算機有關的是（）o

A.數(shù)據(jù)元數(shù)間的抽象關系B.數(shù)據(jù)的存儲結構

C.算法的時間復雜度I）.數(shù)據(jù)的邏輯結構

3.結構中的元素之間存在多對多的關系是（）。

A.集合B.線性結構

C.樹形結構1）.圖狀結構

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

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

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

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

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

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

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

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

6.設有一個長度為25