《數(shù)據(jù)結(jié)構(gòu)》試卷四含答案

《數(shù)據(jù)結(jié)構(gòu)》試卷四

一、選擇題（本題共20分，每小題1分）

1.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（）。

A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

2.線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（）。

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

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

3.不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（）。

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

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

4.在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間

插入S結(jié)點(diǎn)，則執(zhí)行（）。

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

C.q->next=s;s->next=p;D.p-next=s;s->next=q;

5.從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需

平均比較（）個(gè)結(jié)點(diǎn)。

A.nB.n/2

C.(n-l)/2D.(n+l)/2

6.一個(gè)棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是（)o

A.edcbaB.decbaC.dceabD.abcde

7.判定一個(gè)循環(huán)隊(duì)列QU（最多元素為m0)為滿隊(duì)列的條件是（

A.QU->front==QU->rearB.QU->front!=QU->rear

C.QU->front==(QU->rear+l)%mOD.QU->front!=(QU->rear+l)%mO

8.棧和隊(duì)列的共同點(diǎn)是（)

A.都是先進(jìn)后出B.都是先進(jìn)先出

C.只允許在端點(diǎn)處插入和刪除元素D.沒(méi)有共同點(diǎn)

9.數(shù)組A中，每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從1到8,列下標(biāo)j從1至也0,

從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，元素A[8][5]的起始地址為

()o

A.SA+141B.SA+144

C.SA+222D.SA+225

10.廣義表((a,b),c,d)的表尾是()o

A.aB.b

C.(a,b)D.(c,d)

11.設(shè)矩陣A是一個(gè)對(duì)稱矩陣，為了節(jié)省存儲(chǔ)，將其下三角部分（如下圖所示）按行序

存放在一維數(shù)組B[l,n（n-l）/2]中,對(duì)下三角部分中任一元素ai,j（i?j）,在一維數(shù)

組B的下標(biāo)位置k的值是（

A.i(i-l)/2+j-lB.i(i-l)/2+j

C.i(i+l)/2+j-lD.i(i+l)/2+j

au

aa

A2l22

13.已知某二叉樹(shù)的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷

序列是（）。

A.acbedB.decabC.deabcD.cedba

14.按照二叉樹(shù)的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)有（）種。

A.3B.4

C.5D.6

15.設(shè)高度為h的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹(shù)中所包含

的結(jié)點(diǎn)數(shù)至少為（）。

A.2hB.2h-l

C.2h+lD.h+1

16.在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（）倍。

A.1/2B.1C.2D.4

17.在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂點(diǎn)至少需要（）條邊。

A.nB.n+1

C.n-lD.n/2

18.已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下圖所示，根據(jù)有向圖的深度優(yōu)先遍歷算法，從

頂點(diǎn)vl出發(fā)，所得到的頂點(diǎn)序列是（)o

?24

?「I+「口

A.vl,v2,v3,v5,v4B.vl,v2,v3,v4,v5

C.vl,v3,v4,v5,v2D.vl,v4,v3,v5,v2

19.采用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為

()o

A.nB.n/2

C.(n+1)/2D.(n-l)/2

20.快速排序方法在（）情況下最不利于發(fā)揮其長(zhǎng)處。

A.要排序的數(shù)據(jù)量太大B.要排序的數(shù)據(jù)中含有多個(gè)相同值

C.要排序的數(shù)據(jù)已基本有序D.要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù)

二、填空題（本題共20分，每空1分）

1.根據(jù)數(shù)據(jù)元素之間的不同特征，通常有四類基本結(jié)構(gòu):一和

2.下面程序段的時(shí)間復(fù)雜度是:

for(i=0；i<n；i++)

for(j=0；j<m；j++)

A[i][j]=0；

3.向一個(gè)長(zhǎng)度為n的線性表中的第i個(gè)元素(iWiWn)之前插入一個(gè)元素時(shí)，需向

后移動(dòng)個(gè)元素。

4.在一個(gè)單鏈表中的p所指結(jié)點(diǎn)之前插入一個(gè)s所指結(jié)點(diǎn)時(shí)，可執(zhí)行如下操作：

(1)s->next=;

(2)p-next=s;

(3)t=p->data;

(4)p->data=;

(5)s->data=;

5.深度為k的完全二叉樹(shù)至少有一個(gè)結(jié)點(diǎn)，至多有一個(gè)結(jié)點(diǎn)，若按自上而下，從

左到右次序給結(jié)點(diǎn)編號(hào)(從1開(kāi)始)，則編號(hào)最小的葉子結(jié)點(diǎn)的編號(hào)是—o

6.一個(gè)廣義表為(a,(a,b),d,e,((i,j),k)),則該廣義表的深度為。

7.有一棵樹(shù)如下圖所示，回答下面的問(wèn)題：結(jié)點(diǎn)k3的度是—；這棵樹(shù)的度為—；

這棵樹(shù)的深度是—o

8.在對(duì)一組記錄(54,38,96,23,15,72,60,45,83)進(jìn)行直接插入排序時(shí)，當(dāng)把第

七個(gè)記錄60插入到有序表時(shí)，為尋找插入位置需比較次。

9.隊(duì)列的插入操作在_____進(jìn)行，刪除操作在_______進(jìn)行。

10.判定一個(gè)有向圖中是否存在回路，即是否含有環(huán)，可以使用方法。

三、閱讀程序?qū)懡Y(jié)果(本題共20分，每小題5分)

1.單鏈表中，指針P指向某結(jié)點(diǎn)，執(zhí)行以下操作后，請(qǐng)用一句話描述程序執(zhí)行的結(jié)

果是什么？

q=p->next;

p->data=p->next->data;

p->next=p->next->next;

free(q);

2.閱讀下面二分查找程序代碼，填充空白位置，使算法完整。

intBinSearch(SeqListR,KeyTypek)

{intlow=l,high=n,mid;

while(low〈二high)

{mid=(low+high)/2;

if(R[mid].key==k)returnmid;

if(R[mid].key>k)①;

else②;}

return0;

3.如下圖所示給出了圖G及對(duì)應(yīng)的鄰接表，根據(jù)給定的dfs算法，從頂點(diǎn)8出

發(fā)，寫(xiě)出其搜索序列。

Adjlistgl;

voiddfs(intv)

{structvexnode*p;

printf(zz%d，z,v);

visited[v]=l;

P=gl[v]->link;/*gl是該圖的鄰接表的表頭指針數(shù)組*/

while(p!=NULL)

{if(visited[p->adjvex]==O)dfs(p->adjvex);

p=p->next;}

)

二一03->03

2二fI“，I44引El

3二HZQHIQ-dZI

4二7G「4~H81T

6二一HJHZQ

7二.卜|4[m

8乎EBHZH^ZmZEl

4.二叉樹(shù)采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，將第四題綜合題3中的二叉樹(shù)，運(yùn)行下面的遞歸

算法，請(qǐng)寫(xiě)出最后的返回結(jié)果是什么？

intcount(btree*b)

{intnuml,num2;

if(b==NULL)return(0);

elseif(b->left==NULL&&b->right==NULL)return(1);

else{numl=count(b-〉left);

num2=count(b->right);

return(numl+num2);}

)

四、綜合題(本題共30分，每小題5分)

1.有一份電文中共使用五個(gè)字符：a、b、c、d、e,它們的出現(xiàn)頻率依次為{4、7、

5、2、9},試畫(huà)出對(duì)應(yīng)的哈夫曼樹(shù)(注意：構(gòu)造哈夫曼樹(shù)過(guò)程中請(qǐng)按左子樹(shù)根結(jié)點(diǎn)的權(quán)

值小于等于右子樹(shù)根結(jié)點(diǎn)的權(quán)值次序構(gòu)造)，并求出每個(gè)字符的哈夫曼編碼。

2.利用普里姆算法，從節(jié)點(diǎn)1出發(fā)構(gòu)造出如下圖所示的圖G的一棵最小生成樹(shù)。

3.一棵二叉樹(shù)如下面的圖所示，要求：

(1)寫(xiě)出對(duì)此二叉樹(shù)進(jìn)行中序遍歷時(shí)得到的結(jié)點(diǎn)序列。

(2)畫(huà)出由此二叉樹(shù)轉(zhuǎn)換得到的森林。

4.請(qǐng)畫(huà)出，將元素3和元素6依次插入到下圖所示的平衡二叉樹(shù)中的結(jié)果，要求仍然

保持為一棵平衡二叉樹(shù)。

5.一組元素為(46,25,78,62,12,37,70,29),要求:

(1)畫(huà)出按元素排列順序輸入生成的一棵二叉排序樹(shù)。

(2)畫(huà)出在二叉排序樹(shù)中，刪除元素46后的結(jié)果

6.設(shè)哈希表長(zhǎng)度為11,哈希函數(shù)h(key)=key/IE給定的關(guān)鍵字為1,13,12,34,

38,33,2,22。試畫(huà)出用線性探查法解決沖突時(shí)所構(gòu)造的哈希表。并計(jì)算在查找成

功時(shí)候的平均查找長(zhǎng)度。

五、算法題(本題共10分)

假設(shè)線性表中包含n個(gè)數(shù)據(jù)元素，請(qǐng)寫(xiě)出順序存儲(chǔ)方式下對(duì)n個(gè)元素的冒泡排序

算法。具體存儲(chǔ)結(jié)構(gòu)如下:

#defineMaxsize20

TypedefintKeyType;

Typedefstruct{

KeyTypekey;〃關(guān)鍵字項(xiàng)

InfoTypeotherinfo;〃其它數(shù)據(jù)項(xiàng)

}RedType;//記錄類型

Typedefstruct{

RedTyper[Maxsize+1];〃:r[0]閑置或者用做哨兵單元

Intlength;〃順序表長(zhǎng)度

}SqList;〃順序表類型

參考答案

一、選擇題（本題共20分，每題1分）

12345678910

CDACDCCCCD

11121314151617181920

BDCCBBCCCC

二、填空題（本題共20分，每空1分）

1.集合、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、網(wǎng)狀結(jié)構(gòu)

2.0（m*n）

3.n-i+1

4.①p->next②s->data③t

5.①②2*-1③2~+1

6.3層

7.①2②3③4

8.3

9.隊(duì)尾、對(duì)頭

10.拓?fù)渑判?/p>

三、閱讀程序?qū)懡Y(jié)果（本題共20分，每小題5分

1.刪除了P結(jié)點(diǎn)

2.high=mid-l;low=mid+1;

3.搜索序列為：8,4,2,1,3,6,7,50

4.返回結(jié)果是2

四、綜合題（本題共30分，每小題5分）

1.解：依題意，各字符對(duì)應(yīng)的哈夫曼編碼以及相應(yīng)的哈夫曼樹(shù)結(jié)果如下:

a：011b：10c：00d：010e：11

2.解：使