數(shù)據(jù)結(jié)構(gòu)統(tǒng)考測試及答案

數(shù)據(jù)結(jié)構(gòu)統(tǒng)考

一、單項選擇題(10小題，每小題1分，共10分)

1.以下數(shù)據(jù)結(jié)構(gòu)中，(A)是非線性數(shù)據(jù)結(jié)構(gòu)。

A.樹B.字符串C.隊D.棧

2.程序段

for(i=n-l;i>=l;i—)

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

if(A[jJ>Alj+l])

A[j]與A[j+1]對換；

其中n為正整數(shù)，則最后一行的語句頻度在最壞情況下是(D)。

A.O(n)B.O(nlogn)C.O(n3)D.O(n2)

3.拓撲序列是無環(huán)有向圖中所有頂點的一個線性序列，圖中任意路徑中的各個頂點在該圖的

拓撲序列中保持先后關(guān)系,B)不是下圖所示有向圖的一個拓撲序列。

c3

A.clc2c3c4c5c6c7

c7

c4B.clc2c4c5c6c3c7

c2c6C.clc2c4c6c3c5c7

D.c2c1c4c6c3c5c7

4.對于n個關(guān)鍵字序列｛"當(dāng)且僅當(dāng)滿足關(guān)系kiWk2i且kiWk2i+i⑵Wn,2i+l

■)稱其為小根堆,反之，當(dāng)且僅當(dāng)滿足關(guān)系ki》k"且ki》k2i+i(2iWn,2i+lWn)則為大根

堆，以下序列中(D)符合堆的定義。

A.(4,10,23,72,39,15,18)B.68,27,23,12,8,36,9)

C.0,10,18,72,39,23,15)D.(58,36,27,12,8,23,9)

5.在若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間

復(fù)雜度為(C)(l<=i<=n)o

A.0(0)B.O(l)C.O(n)D.O(n2)

6.當(dāng)在一個有序的順序存儲表上查找一個數(shù)據(jù)時，即可用折半查找，也可用順序查找，但前

者比后者的查找速度(C)。

A.必定快B.不一定

C.在大部分情況下要快D.取決于表遞增還是遞咸

7.在采用二次探測法處理沖突所構(gòu)成的閉散列表上進行查找，可能要探測多個位置，在查找

成功的情況下，所探測的這些位置的鍵值(A)。

A.不一定都是同義詞B.一定都是同義詞

C.一定都不是同義詞D.都相同

第1頁共4頁

8.表達式a*（b+c）-d的后綴表達式是（B）o

A.abcd*+-B.abc+*d-C.abc*+d?D.-+*abcd

9.數(shù)組A[0..5,0..6]的每個元素占5個字節(jié)，將其按列優(yōu)先次序存儲在起始地址為1000的內(nèi)

存單元中，則元素A[5,5]的地址是（A）o

A.1175B.1180C.1205D.1210

10.下面關(guān)于求關(guān)鍵路徑的說法不正確的是（A）。

A.求關(guān)鍵路徑是以拓撲排序為基礎(chǔ)的

B.一個事件的最早開始時間與以該事件為尾的弧的活動最早開始時間相同

C.一個事件的最遲開始時間為以該事件為尾的弧的活動最遲開始時間與該活動的持續(xù)

時間的差

D.關(guān)鍵活動一定位于關(guān)鍵路徑上

二、簡單填空題（10小題，20個空，每空1分，共20分）

1■當(dāng)兩個棧共享一存儲區(qū)時，棧利用一維數(shù)組data[l..nj表示，棧I由低向高延伸，棧2由高

向低延伸，棧1棧頂指針為topi,棧2為top2,則當(dāng)棧1空時，topi為-1,棧滿時為

top1+1==top2o

2.對于一個具有n個結(jié)點的單鏈表，在已知的結(jié)點p后插入一個新結(jié)點的時間復(fù)雜度為

0（1）在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為0（n）o

3?按照書本定義的循環(huán)隊列，設(shè)front指向隊頭元素的前一個位置，rear指向隊尾元素的位置,

設(shè)實現(xiàn)循環(huán)隊列的空間大小為QueueSize,那么循環(huán)隊列的空的條件為front==rear,

滿的條件為（rear+1）%QueueSize==front。

4.用一維數(shù)組B與列優(yōu)先存放帶狀矩陣A,A中的非零元素A[i,j]（lWiWn,i-2WjWi+2）,B

中的第8個元素是A中的第_Lji，第3列的元素。

5.深度為H的完全二叉樹至少有2—個結(jié)點;至多有2&1個結(jié)點。

6.快速排序法在基本有序或（正序或逆序）情況下最不利于發(fā)揮其長處,在每次劃

分元素個數(shù)都基本相等（相同意思均可）情況下最易發(fā)揮其長處。

7.順序查找n個元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為n次；當(dāng)使

用監(jiān)視哨時，若查找失敗，則比較關(guān)鍵字的次數(shù)為n+1。

8.平衡二叉樹又稱AVL樹,最小不平衡子樹是指在平衡二叉樹的構(gòu)造過程中，以距離插

入點最近的、且平衡因子的絕對值大于1或＞1或=2的結(jié)點為根的子樹。

9.設(shè)無向圖G=（V,E）有n個頂點，e條邊，若采用鄰接矩陣存儲圖，其空間復(fù)雜度為

0（。，在此基礎(chǔ)上進行廣度優(yōu)先搜索的時間復(fù)雜度為0（吟。

10.先根次序遍歷森林的結(jié)果正好等同于按先序遍歷對應(yīng)的二叉樹,后根次序遍歷森

林正好等同于按飛遍歷對應(yīng)的二叉樹。

第2頁共4頁

三、應(yīng)用題(10小題，每小題6分，共60分)

評分：每小題6分，每空3分

1.每一棵樹都能唯一的轉(zhuǎn)換為它所對應(yīng)的二叉樹。若已知一棵二叉樹的前序序列是

BEFCGDH,中序序歹IJ是FEBGCHD,貝IJ它的后序序歹”是(FEGHDCB)；設(shè)

上述二叉樹是由某棵樹轉(zhuǎn)換而成，則該樹的先根次序序列是(BEFCGDH)o

2.己知有序表為(12,18,24,35,47,50,62,83,90,115,134),當(dāng)用二分法查找90時需(2)次

查找成功，查100時，需(3)次才能確定不成功。

3.給定一組數(shù)據(jù)｛6,2,7,10,3,12｝以它構(gòu)造一棵哈夫曼樹，則樹高為(5),帶權(quán)

路徑長度WPL的值為(113)。

4.利用逐點插入法建立序列(50,72,43,85,75,20,35,45,65,30)對應(yīng)的二叉排序

樹，該二叉排序樹的深度為(5),查找成功的平均查找長度為(3)。

5.已知一個線性表(38,25,74,63,52,48),假定采用散列函數(shù)h(key)=key%12計算

散列地址，并散列存儲在散列表中，若采用線性探測方法解決沖突，查找63需要比較

(2)次，該散列表的裝填因子a為(0.5)。

6.題6圖表示一個地區(qū)的通訊網(wǎng)，邊表示城市間的通訊線路，邊上的權(quán)表示架設(shè)線路花費的

代價，選擇能溝通每個城市且總代價最省的n-1條線路，總代價是(18)；選擇的線路是

((a,b)l,(a,f)2,(b,c)5,(c,d)3,(c,e)4,(e,h)3)o

題6圖

7.如圖題7圖所示的無向圖，如果采用鄰接表存儲該圖，則從頂點1出發(fā)按深度優(yōu)先遍歷的

頂點序列是(125967384)按廣度優(yōu)先遍歷的頂點序列是(123456789)0

8.設(shè)有輸入序列(2,3,1,5,4,9,8,7,6),借助輔助?；蜉o助隊列得到序列(1,2,3,4,5,6,7,8,9),問最

少需要(2)個輔助棧，或最少需要(3)個輔助隊列。

9.如圖題9圖所示的二叉樹，將其轉(zhuǎn)換成對應(yīng)的森林，問：該森林中共有(3)棵樹,

(A)結(jié)點的度最大。

題9圖

10.設(shè)用序列(23,20,11,31,13,27),構(gòu)造一個小頂堆，該小頂堆的葉子元素包括(31,20,27)；

對該小頂堆進行堆排序，第一趟排序并調(diào)整后的順序表為(13,20,23,31,27,11)o

第3頁共4頁

四、算法設(shè)計題(2小題，每小題5分，共10分)

1.設(shè)計一個算法判斷單鏈表是否為有序表，假設(shè)有序表是升序的。

template<classT>

boolIsOrder(Node<T>*head)

(

Node<T>*p;

p=head->next;//I分

while(p&&p->next)//I分