試卷作業(yè)數(shù)據(jù)結(jié)構(gòu)（信息）-數(shù)據(jù)結(jié)構(gòu)B期末考試 A卷及參考答案

一、單項(xiàng)選擇題（每小題2分，共30分）

1.設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素el、e2、e3、e4、e5和e6依次進(jìn)入棧S,一

個元素出棧后即進(jìn)入Q,若6個元素出隊(duì)的序列是e2、e4、e3、e6、e5和el,則棧

S的容量至少是（）個。

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

2.銀行業(yè)務(wù)叫號系統(tǒng)采用了（）數(shù)據(jù)結(jié)構(gòu)。

A.棧B.廣義表C.圖D.隊(duì)列

3.按照二叉樹的定義，具有3個結(jié)點(diǎn)的不同形狀的二叉樹有（）種。

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

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

A.動態(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)

5.非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足（）0

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

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

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

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

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

7.一個隊(duì)列的入隊(duì)序列是1,2,3,4,則隊(duì)列的輸出序列是（）<.

A.4,3,2,1B.1,2,3,4

C.1,4,3,2D.3,2,4,1

8.串的長度是指（）o

A.串中所含字符的個數(shù)B.串中所含不同字母的個數(shù)

C.串中所含不同字符的個數(shù)D.串中所含非空格字符的個數(shù)

9.具有10個葉子結(jié)點(diǎn)的二叉樹中有（）個度為2的結(jié)點(diǎn)。

A.8B.9C.10D.11

10.某二叉樹結(jié)點(diǎn)的中序序列為ABCDEFG,后序序列為BDCAFGE,則其左子樹中結(jié)

點(diǎn)數(shù)目為（）

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

11.設(shè)森林F對應(yīng)的二叉樹B有m個結(jié)點(diǎn)，B的右子樹結(jié)點(diǎn)個數(shù)為n,森林F中第一棵

樹的結(jié)點(diǎn)個數(shù)是（）

A.m-nB.m-n-1C.n+1D.m+n

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

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

13.堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列（）是一個堆。

A.91,31,56,23,15,68B.91,56,31,68,15,23

C.15,56,23,91,31,68D.15,31,23,91,56,68

14.以下內(nèi)部排序方法中，平均時間復(fù)雜度為O（nk?gn）,最壞情況下時間復(fù)雜度為O（n2）

的是（）?

A.快速排序B.堆排序C.直接選擇排序D.插入排序

15.對一組數(shù)據(jù)（84,47,25,15,21）排序，數(shù)據(jù)的排列次序在排序過程中變化如下：

（1）8447251521（2）1547258421（3）1521258447（4）1521254784則采

用的排序方法是（）

A.選擇排序B.起泡排序C.快速排序D.插入排序

二、判斷題（正確的劃錯誤的劃“X”，每小題1分，共15分）

1.算法獨(dú)立于具體的程序設(shè)計(jì)語言，與具體的計(jì)算機(jī)無關(guān)。（）

2.線性表采用鏈?zhǔn)酱鎯r，結(jié)點(diǎn)內(nèi)部的存儲空間可以是不連續(xù)的。（）

3.棧和隊(duì)列的存儲方式，既可以是順序方式，又可以是鏈?zhǔn)椒绞健＃ǎ?/p>

4.哈夫曼樹的結(jié)點(diǎn)總個數(shù)一定是偶數(shù)。（）

5.已知二叉樹的先序遍歷序列和中序遍歷序列，可以畫出這棵二叉樹（）o

6.有e條邊的無向圖，在其對應(yīng)的鄰接表中有e個結(jié)點(diǎn)。（）

7.連通分量指的是無向圖的極大連通子圖。（）

8.起泡排序算法在最好情況下的時間復(fù)雜度為O（n）。（）

9.在哈希表的查找過程中的“比較”操作是無法避免的。（）

10.不論是入隊(duì)列操作還是入棧操作，在順序存儲結(jié)構(gòu)上都需要考慮“溢出”情況。（）

11.完全二叉樹不一定是平衡二叉樹。（）

12.雙向鏈表可隨機(jī)訪問任一結(jié)點(diǎn)。（）

13.空串和空白串是相同的。（）

14.抽象數(shù)據(jù)類型（ADT）包括定義和實(shí)現(xiàn)兩方面，其中定義是獨(dú)立于實(shí)現(xiàn)的，定義僅給

出一個ADT的邏輯特性，不必考慮如何在計(jì)算機(jī)中實(shí)現(xiàn)。（）

15.堆是完全二叉樹，完全二叉樹不一定是堆。（）

三、填空題（每空1分，共15分）

1.n個記錄的折半查找，若查找失敗，進(jìn)行了（1）次比較。

2.在單鏈表中，指針D所指結(jié)點(diǎn)有后繼的條件是（2）。（結(jié)點(diǎn)構(gòu)成：data和next）

3.棧的特點(diǎn)是（3）。

4.判斷循環(huán)隊(duì)列是否隊(duì)滿的條件表達(dá)式是（Q.rear和Q.front的關(guān)系）

5.完全二叉樹中的結(jié)點(diǎn)個數(shù)為n,則編號最大的分支結(jié)點(diǎn)的編號為

6.如果二叉樹中有10個葉結(jié)點(diǎn),12個度為1的結(jié)點(diǎn)，則該二叉樹的總結(jié)點(diǎn)數(shù)為（個。

7.如果A有7個兄弟，而B是A的雙親，則B的度是（7）。

8.若無向圖中有n個頂點(diǎn)，則其完全無向圖恰有（8）條邊。

9.如果具有n個頂點(diǎn)的圖是一個環(huán)，則它有（9）棵生成樹。

10.普里姆（Prim）算法的時間復(fù)雜度是（10）,與圖中的邊數(shù)無關(guān)，它適合求（11）

圖的最小生成樹。

11.順序查找有n個元素的線性表，若查找成功時的平均查找長度為（12）.

12.高度為5的二叉樹，其結(jié)點(diǎn)最少有（13）個,最多有（14）個。

13.操作是是二叉樹各種操作的基礎(chǔ)。

四、算法填空（每空2分，共10分）

1.在順序表L的第i個元素之前插入新的元素e

StatusListInsert（SqList&L,inti,ElemTypee）｛

if（i<l||i>L.length+1）returnERROR;//插入位置不合法

for（j=L.length;j>i;j-）

⑴；//將第i個及后面的元素后移

L.elem[i-1]=e;//插入e

⑵；//表的長度增加1

returnOK;

）

2.下面程序段的功能是實(shí)現(xiàn)一趟快速排序，請?jiān)谙聞澗€處填上正確的語句。

intPartition（Sqlist&L,intlow,inthigh）｛

〃以L.r[Iow]為主記錄,對子系列L.r[low.?.high]的一趟劃分

temp=L.r[Iow];

while（low<high）｛〃進(jìn)行一趟劃分

while(low<high&&L,r[high].key>=temp.key)—high;

L.r[low]=L.r[high];

while(low<high&&L.r[Iow].key<=temp.key)++low;

L.r[high]=L.r[low];

}

⑶：〃找到主記錄的位置low

returnlow;

)

voidQsort(Sqlist&L,intlow,inthigh){〃遞歸算法實(shí)現(xiàn)

if((4)){〃長度大于1

loc=Partition(L,low,high);〃將L.r[Iow...high]一分為—

Qsort(L,low,loc-1);//對低子表遞歸排序

⑸；〃對高子表遞歸排序

)

)

voidQuickSort(SqListL){〃對順序表L做快速排序

Qsort(L,1,L.length);

)

五、綜合題(每小題6分，共30分)

1.給定葉結(jié)點(diǎn)(a,b,c,d,e,f,g),權(quán)值分別為{24,12,17,10,27,2,8}，畫出對應(yīng)的哈夫曼樹，并

寫出各葉結(jié)點(diǎn)的哈夫曼編碼。(6分)

2.已知一棵二叉樹的后序遍歷序列為EICBGAHDF,中序遍歷序列為CEIFGBADH,

請畫出這棵二叉樹，寫出其前序，并把這棵二叉樹轉(zhuǎn)換成相應(yīng)的樹(或森林)。(6分)

3.假設(shè)一個有向圖的頂點(diǎn)集為{1,2,3,4,5,6},其鄰接矩陣如

010010-

圖1所示。（6分）

000101

（1）請根據(jù)鄰接矩陣畫出該圖（圖中頂點(diǎn)的排列位置如100100

圖2）；000010

000000

（2）分別求每一個頂點(diǎn)的入度和出度；-000010-

（3）請寫出一個從頂點(diǎn)3出發(fā)進(jìn)行廣度優(yōu)先搜索的遍歷序列。

①G)

0@

OG)

圖2

4.對于非連通圖，每個連通分量中的頂點(diǎn)和遍歷

錚O0?

時走過的邊一起構(gòu)成若干棵生成樹，這些連通

分量的生成樹組成非連通圖的生成森林。畫出

圖3從頂點(diǎn)A出發(fā)，按深度優(yōu)先遍歷得到的

生成森林。（6分）

圖3

5.一個帶權(quán)網(wǎng)絡(luò)如圖4所示。從頂點(diǎn)1開始，用克魯

斯卡爾（Kruskal）算法求出該網(wǎng)的最小生成樹。要

求在答題卷上畫出最小生成樹的產(chǎn)生過程，并用

<>括起來的數(shù)字標(biāo)號反映最小生成樹中各條邊的

求取次序。（6分）

圖4

、單項(xiàng)選擇題（每小題2分，共30分）

1~5ADCBC6~10CBABD11-15ACDAA

二、判斷題（正確的劃“J”，錯誤的劃“X”，每小題1分，共15分）

1~5VVVXV6~10XVVVV11-15vxxvv

三、填空題（每空1分，共15分）

1[10g2n]+l2p->next!=NULL3FILO或LIFO

4Q.rear==Q.front5[n/2]631

788n(n-l)/29n

10O(n2)11稠密圖12n/2

135143115遍歷

四、算法填空（每空2分，共10分）

(1)L.elem[j]=L.elem[j-1](2)L.Iength++或L.length=L.length+1

(3)L.r[low]=temp(4)low<high

(5)Qsort(L,loc+1,high)

五、綜合題（每小題6分，共30分）

哈夫曼編碼（3.5分，每個編碼0.5分）a:01b:110c:llld:001e:10f:0000

g:0001

哈夫曼樹和哈夫曼編碼都不唯一，只要滿足條件都可以。

2.已知一棵二叉樹的后序遍歷序列為EICBGAHDF,中序遍歷序列為CE1EGBADH,請畫出這棵二叉樹,