青島科技大學(xué)2017年碩士研究生入學(xué)考試試題

考試科目：數(shù)據(jù)結(jié)構(gòu)

注意事項：

1.本試卷共 三 道大題（共計22個小題），滿分150分；

2.本卷屬試題卷，答題另有答題卷，答案一律寫在答題卷上，寫在該試題卷上或草紙上均無效。要注意試卷清潔，不要在試卷上涂劃；

3.必須用藍(lán)、黑鋼筆或簽字筆答題，其它均無效。            

------------------------------------------------------

一．選擇題(每題2分，共30分)

1.數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)結(jié)構(gòu)的（  ）以及它們的操作。

A）理想與邏輯  B）存儲和抽象  C）理想和抽象  D）邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)

2.指出下面程序段的時間復(fù)雜度（  ）。

i=1;

While(i<n)i=i*2;

A）O(1)    B)O(log2n)     C)O(n)     D)O(nlog2n)

3.下列敘述中正確的是（）。

A）線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯�結(jié)構(gòu)  

B）棧的操作特點是先進(jìn)先出

C）二維數(shù)組是每個數(shù)據(jù)元素本身為一個線性表的線性表

D）隊列的操作特點是后進(jìn)先出

4.鏈棧和順序棧相比一個比較明顯的優(yōu)勢是（）。

A）插入操作更加方便     B）刪除操作更加方便

C）不會出現(xiàn)�？盏那闆r    D）通常不會出現(xiàn)棧滿的情況

5.元素a,b,c,d,e依次進(jìn)入初始為空的棧中，若元素進(jìn)棧后可以停留，可出棧，直到所有的元素都出棧，則在所有可能的出棧序列中，以元素d開頭的出棧序列有（）。

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

6.在一個單鏈表中，若P所指結(jié)點是最后結(jié)點，在P之后插入S所指結(jié)點，則執(zhí)行（）。

A）S->next=P; P->next=S;   B）S->next=P->next; P=S;

C）S->next=P->next; P->next=S;   D）P->next=S;  S->next=P;

7．具有n個葉子結(jié)點的哈夫曼樹，所有結(jié)點個數(shù)為（）。

A）2n  B） 2n+1  C） 2n-2    D） 2n-1

8.一棵深度為K的完全二叉樹至少有(   )結(jié)點。

A）2k+1  B） 2k-1  C） 2k-1 -1  D） 2k+1

9.平面上有五個點A(5,3),B(3,5),C(2,1),D(3,3),E(5,1)。以這五點作為完全圖G的

點，每兩點之間的距離是圖G中對應(yīng)邊的權(quán)值。以下哪條邊不是圖G的最小生成樹中的（）。

A）EA   B） AD     C）DE     D）BD

10． 二叉樹T的層次遍歷序列為A B C D E F G H I，已知A是C的父結(jié)點，D是G的父結(jié)點，F(xiàn)是I的父結(jié)點，樹中所有結(jié)點的最大深度為3（根結(jié)點深度設(shè)為0），可知F的父結(jié)點為（）。

A） B   B）E    C）D      D）C

11.設(shè)棧的初始狀態(tài)為空，元素a,b,c,d,e,f,g依次進(jìn)棧，以下出棧序列不可能出現(xiàn)的是（）。

A）a,b,c,e,d,f,g  B）g,e,f,d,c,b,a  C）b,c,a,f,e,g,d  D）d,c,f,e,b,a,g

12．一個n階對稱矩陣，如果以行或列為主序存入內(nèi)存，則容量為（）。

A) n*n    B) n*n/2      C) n*(n+1)/2    D) (n+1)*(n+1)/2

13.n個頂點的強連通圖至少有( )條邊，其形狀是（）。

A)n*（n-1)，樹狀     B)n+1，有回路    C) n-1，無回路    D)n，環(huán)狀

14.若用冒泡法對序列(10,14,26,29,41,52)從大到小排序，則需要進(jìn)行（）次比較。

A) 3   B) 15      C) 10    D)25

15．具有12個關(guān)鍵字的有序表，若查找每個元素的概率相同，進(jìn)行二分查找的平均查找長度為( )。

A)4     B)2.5     C)3.1      D)5

二．應(yīng)用題（60分） 

1.（15分）什么是最優(yōu)樹？假設(shè)用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。

① 試為這8個字母設(shè)計赫夫曼編碼。

② 試設(shè)計另一種由二進(jìn)制表示的等長編碼方案。

③ 對于上述實例，比較兩種方案的優(yōu)缺點。

2.（15分）什么是關(guān)鍵路徑？什么是關(guān)鍵活動？試對下圖所示的AOE-網(wǎng)：

① 求這個工程最早可能在什么時間結(jié)束；    

② 求每個活動的最早開始時間和最遲開始時間；

③ 確定哪些活動是關(guān)鍵活動

3.（15分）假設(shè)線性表的關(guān)鍵字集合為key={32,75,31,63,48,94,25,47,18,70},散列地址空間為HT[11]，若采用除留余數(shù)法構(gòu)造散列函數(shù)和鏈地址法處理沖突，試求出每一元素的散列地址，畫出最后得到的散列表，并求出等概率下查找成功的平均查找長度。

4. (15分)閱讀以下算法： 

①該算法是什么樣排序算法；該算法待排序記錄的存儲結(jié)構(gòu)是什么？

②簡述該排序算法的思想；

③設(shè)待排序的關(guān)鍵字序列為{12，2，16，30，28，10，16*，20，6，18}，試寫出使用該排序方法，每趟排序結(jié)束后關(guān)鍵字序列的狀態(tài)；

void  Sort ( SqList &L )

  { for ( i = 2;  i <= L.length ; ++i )

     {  L.r[0] = L.r[i]; low = 1 ; high = i-1 ;

         while ( low <= high )       

            {  m = ( low + high ) / 2 ; 

          if  (  L.r[0].key < L.r[m]. key  )  high = m -1 ;

        else  low = m + 1; 

          }

        for ( j=i-1; j>=high+1; - - j ) L.r[j+1] = L.r[j];

       L.r[high+1] = L.r[0];

   }

}  // Sort

三．算法設(shè)計題（60分）

1.（20分）已知head是指向帶頭結(jié)點的單鏈表的頭指針，試編寫以下算法：

①統(tǒng)計單鏈表中結(jié)點個數(shù)的算法；

②刪除單鏈表中值為x的算法；

2.（20分）設(shè)以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，寫出如下算法：

①用先序遍歷的方法，統(tǒng)計二叉樹中度為1的結(jié)點的個數(shù)；

②用層次遍歷的方法，統(tǒng)計二叉樹中度為1的結(jié)點的個數(shù)；

3.（20分）寫出如下算法：

①創(chuàng)建一個有向圖鄰接表的存儲結(jié)構(gòu)的算法；

②寫出利用該存儲結(jié)構(gòu)實現(xiàn)對有向圖進(jìn)行拓?fù)渑判虻乃惴ǎ?/p>