數(shù)據(jù)結(jié)構(gòu)期末試卷

一、單選題（40分）

1.【單選題】（2分）

樹的路徑長度是從樹根到每個結(jié)點的路徑長度的（）。

A.平均值

OB.總和

C.最大值

D.最小值

2.【單選題】（2分）

某二叉樹的先序序列和后續(xù)序列正好相反，則該二叉樹一定是（）。

A.任一結(jié)點無右孩子

OB.空或只有一個結(jié)點

C.高度等于其結(jié)點數(shù)

D.任一結(jié)點無左孩子

3.【單選題】（2分）

若一棵完全二叉樹的先序遍歷序列為ABDHGECF,則以下說法錯誤的是（）。

A.結(jié)點C的深度為3

B.結(jié)點C是葉結(jié)點

C.結(jié)點C的高度為1

OD.結(jié)點C是A的右孩子結(jié)點

4.【單選題】（2分）

關(guān)于圖的存儲結(jié)構(gòu)，（）是錯誤的。

A.若一個有向圖的鄰接矩陣的對角線以下的元素為0,則該圖的拓?fù)湫蛄斜囟ù嬖冢?/p>

OB.鄰接表只用于有向圖的存儲，鄰接矩陣適用于有向圖和無向圖；

C.使用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中的頂點數(shù)

有關(guān)，與邊數(shù)無關(guān)；

D.存儲無向圖的鄰接矩陣是對稱的，故只需存儲鄰接矩陣的下三角部分

5.【單選題】（2分）

假設(shè)利用一個數(shù)組s□順序存儲一個棧，用top作為棧頂指針，top=-1表示?？?，當(dāng)棧未滿時，元素x進棧的

操作是（）。

A.s[++top]=x;

B.s[top--]=x;

C.s[--top]=x;

0D.s[top++]=x;

6.【單選題】（2分）

下列排序方法中，哪一個是穩(wěn)定的排序方法？（）

OA.二分法插入排序

B.直接選擇排序

C.希爾排序

D.快速排序

7.【單選題】（2分）

設(shè)散列表長m=14,散列函數(shù)為h（key）=keymod11,表中僅有4個結(jié)點h（15）=4,

h（38）=5,h（61）=6,h（84）=7,若采用線性探測法處理沖突，則關(guān)鍵字49的結(jié)點地址為（）。

OA.8

B.9

C.3

D.5

8.【單選題】（2分）

棧和隊列具有相同的（）。

A.運算

OB.存儲結(jié)構(gòu)

C.抽象數(shù)據(jù)類型

D.邏輯結(jié)構(gòu)

9.【單選題】（2分）

帶頭結(jié)點的雙向循環(huán)鏈表L為空的判斷條件是（）.

A.L->prior==NULL&8iL-next==L

B.L->prior==L&&L->next==NULL

C.L->prior=NULL&&L-next==NULL

OD.L->prior==L&&L->next==L

10.【單選題】（2分）

線性表的順序存儲結(jié)構(gòu)是一種（）。

OA.順序存取的存儲結(jié)構(gòu)

B.隨機存取的存儲結(jié)構(gòu)

C.索引存取的存儲結(jié)構(gòu)

D.散列存取的存儲結(jié)構(gòu)

11.【單選題】（2分）

折半查找與二叉排序樹的時間性能（）。

A.相同

B.數(shù)量級都是。（n）

OC.有時不同

D.完全不同

12.【單選題】（2分）

用直接插入排序方法對下面四個序列進行排序（從小到大），元素比較次數(shù)最少的是（）。

A.90,75,80,55,20,35,100,40

OB.20,35,55,40,75,80,90,100

C.35,40,20,55,70,100,90,80

D.100,35,40,90,80,55,20,75

13.【單選題】（2分）

在有n個葉結(jié)點的哈夫曼樹中，非葉結(jié)點的總數(shù)是（）。

A.2n

OB.2n-1

C.n-1

D.n

14.【單選題】（2分）

以下說法正確的是（）

A.一個圖的鄰接矩陣表示不唯一,鄰接表表示不唯一

B.一個圖的鄰接矩陣表示唯一，鄰接表表示唯一

OC.一個圖的鄰接矩陣表示唯一，鄰接表表示不唯一

D.一個圖的鄰接矩陣表示不唯一，鄰接表表示唯一

15.【單選題】（2分）

在一棵二叉排序樹上，查找關(guān)鍵字為35的結(jié)點，依次比較的關(guān)鍵字可能有（）。

A.46,28,18,36,35

OB.46,36,18,28,35

C.18,36,28,46,35

D.28,36,18,46,35

16.【單選題】（2分）

分別用下列序列構(gòu)造二叉排序樹，與用其他3個序列所構(gòu)造的結(jié)果不同的是（）。

A.{100,120,110,130,80,60,90）

B.{100,80,60,90,120,130,110）

C.{100,80,90,60,120,110,130）

OD.{100,60,80,90,120,110,130）

17.【單選題】（2分）

對序列{15,9,7,8,20,-1,4}進行排序,進行一趟后數(shù)據(jù)的排列變?yōu)閧4,9,-1,8.20,7,15）;則

采用的是（）排序。

OA.希爾

B.快速

C.冒泡

D.選擇

18.【單壁】（2分）

設(shè)一組初始記錄關(guān)鍵詞為{55,63,50,38,75,80f30,60）,利用篩選法建立的初始〃隈堆為（）。

A.30,38,50,55,60,63,75,80

B.30,55,63,50,38,75,80,60

C.30,38,55,63,75,80,50,60

D.30,38,50,60,75,80,55,63

19.【單選題】(2分)

下面的程序段中，對x的賦值語句的頻度為()。

for(k=1;k<=n;k++)

for(j=1;j<=n;j++)

x=x+1;

A.O(n)

0B.0(nA2)

C.0(2n)

D.O(logn)

20.【單選題】(2分)

在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復(fù)雜度是()。

A.0(1)

0B.0(n)

C.O(n2)

D.O(nlogn)

21?【簡答題】(6分)

以關(guān)鍵字序列(230.309,675.141,927,779,594,090,338,822)為例,分別寫出執(zhí)行以下排序

算法的各趟排序結(jié)束時.關(guān)鍵字序列的狀態(tài)。

(1)歸并播序:(2)基數(shù)排序

有下列運行時間函數(shù)，分別寫Hl相應(yīng)的大。表示的運行時間。

(1)T(n)=2A6;

(2)T(n)=10n2+2n+50;

(3)T(n)=n3+50n2+1;

(4)T(n)=2T(n/2)+n,n>1;當(dāng)n=1時，T(n)=1

23?【簡答題】(5分)

將關(guān)鍵字｛9,10,14,30,11,12,7｝散列存儲到散列表中，算列表的存儲空間是一個下標(biāo)從。開始的一

維數(shù)組，散列函數(shù)為H(Key)=(key*3)mod7,處理沖突的法規(guī)范為線性再散列發(fā)，要求裝填因子為0.7。

(1)請畫出所構(gòu)造的散列表。

(2)分別計算出等概率情況下，查找成功和查找不成功的平均查找長度。

24.【簡(6分)

有一個帶頭結(jié)點的單鏈表L,設(shè)計一個函數(shù)使其元素遞減有序。其中單鏈表結(jié)構(gòu)定義如下：

structLnode｛

intdata;

structLnode*next;

)；

25.【簡答題】(5分)

將(for,case,while,class,protected,virtual,public,private,do,template,const,if,int)中的關(guān)鍵字依

次插入初態(tài)為空的二叉排序樹中，請畫出所得到的樹T,然后畫出刪去for之后的一義排序樹T；

設(shè)頂點表示村莊，有向邊代表交通路線。若要建立一家醫(yī)院，試問建立在那個村莊能使得各村莊總體上的交

通代價最小，寫出計算過程。

編寫函數(shù)判斷以鄰接矩陣存儲的有向圖是否存在一條從V