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

一、單項選擇題（每小題2分，共30分）

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

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

S的容量至少是（）個。

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

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

A.棧B.廣義表C.圖D.隊列

3.按照二叉樹的定義，具有3個結點的不同形狀的二叉樹有（）種。

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

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

A.動態(tài)結構和靜態(tài)結構B.線性結構和非線性結構

C.緊湊結構和非緊湊結構D.內部結構和外部結構

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

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

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

6.棧和隊列的共同點是（)o

A.都是先進后出B.都是先進先出

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

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

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個葉子結點的二叉樹中有（）個度為2的結點。

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

10.某二叉樹結點的中序序列為ABCDEFG,后序序列為BDCAFGE,則其左子樹中結

點數(shù)目為（）

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

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

樹的結點個數(shù)是（）

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

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

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

13.堆是一種有用的數(shù)據(jù)結構。下列關鍵碼序列（）是一個堆。

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.以下內部排序方法中，平均時間復雜度為O（nk?gn）,最壞情況下時間復雜度為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.算法獨立于具體的程序設計語言，與具體的計算機無關。（）

2.線性表采用鏈式存儲時，結點內部的存儲空間可以是不連續(xù)的。（）

3.棧和隊列的存儲方式，既可以是順序方式，又可以是鏈式方式。（）

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

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

6.有e條邊的無向圖，在其對應的鄰接表中有e個結點。（）

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

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

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

10.不論是入隊列操作還是入棧操作，在順序存儲結構上都需要考慮“溢出”情況。（）

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

12.雙向鏈表可隨機訪問任一結點。（）

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

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

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

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

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

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

2.在單鏈表中，指針D所指結點有后繼的條件是（2）。（結點構成：data和next）

3.棧的特點是（3）。

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

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

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

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

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

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

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

圖的最小生成樹。

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

12.高度為5的二叉樹，其結點最少有（13）個,最多有（14）個。

13.操作是是二叉樹各種操作的基礎。

四、算法填空（每空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.下面程序段的功能是實現(xiàn)一趟快速排序，請在下劃線處填上正確的語句。

intPartition（Sqlist&L,intlow,inthigh）｛

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

temp=L.r[Iow];

while（low<high）｛〃進行一趟劃分

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){〃遞歸算法實現(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.給定葉結點(a,b,c,d,e,f,g),權值分別為{24,12,17,10,27,2,8}，畫出對應的哈夫曼樹，并

寫出各葉結點的哈夫曼編碼。(6分)

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

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

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

010010-

圖1所示。（6分）

000101

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

圖2）；000010

000000

（2）分別求每一個頂點的入度和出度；-000010-

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

①G)

0@

OG)

圖2

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

錚O0?

時走過的邊一起構成若干棵生成樹，這些連通

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

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

生成森林。（6分）

圖3

5.一個帶權網絡如圖4所示。從頂點1開始，用克魯

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

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

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

求取次序。（6分）

圖4

、單項選擇題（每小題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,請畫出這棵二叉樹,