華中科技大學軟件學院2011年研究生入學考試試題

duck0135

華中科技大學軟件學院2011年研究生入學考試試題

數據結構與算法

一.術語解釋：（25'）

  1 線性表

  2 樹的結點的層次

  3 排序

  4 完全圖

  5 最小生成樹

二.單項選擇：（25'）

  1 在數組{1，2，3，4，5，6，7，8，9，10}中折半查找5，需要的比較次數是（）

     A  1        B  2           C  3          D  4

  2 假定問題規模為N時，某遞歸算法的時間復雜度記為T（N），已知T(1)=1，

T(N)=2T(N/2)+N/2，用O表示的時間復雜度為（）

A  O(N)     B  O(NlogN)    C  O(N2)     D  O(N2logN)

  3 一棵二叉樹的先序遍歷輸出為ABCDEFGH，中序遍歷為CBEDAFHG，則其先序遍歷輸出為（）【此題的確問的是先序遍歷】

     A  CBDEAFGH              B  CBEDAFHG

     C  BCEDFAHG              D  以上都不對

  4 棧和隊列的共同點是（）

     A  先進先出                 B  后進先出

     C  插入刪除只能在端點進行   D  沒有共同點

  5 起泡排序的時間復雜度是（C）【此題原試卷將答案附上了】

A  O(N)     B  O(NlogN)    C  O(N2)     D  O(N2logN)

三.簡答（60'）

      1 用一個數組實現兩個棧，盡可能利用存儲空間，寫出兩個棧的插入、刪除操作算法。

      2 已知一組關鍵字為{27、25、23、37、35、33、77、75、73、97、95、93、103}，按哈希函數H(key)=key Mod 11（表長11），用連地址法處理沖突，畫出哈希表。

      3 一個遞歸函數具有如下形式

                  Void func(int  n)

                     {

                        if(n>0)

                         {

                           func(n/2);

                           printf("d%",n*n);

                           func(n/2);

                         }

                        return;

                     }

          請依次寫出fun(1)，fun(2)，fun(3)，fun(5)執行的結果，其時間復雜度為多少？

      4 一個通信網絡中共有九中字符，其概率分別為0.14、0.23、0.15、0.03、0.18、0.1、0.02、0.11、0.04，畫出相應的赫夫曼樹來設計其赫夫曼編碼。

      5  V?→V?→V?→∧； V?→V?→V5→∧ ； V3→V5→V6→∧ ；  V4→∧；

         V5 →V7 →V8 →∧ ； V6→V8→∧；  V7 →∧ ；  V8→V9→∧ ；  V9→∧，

          畫出這個邏輯結構的圖示，分別寫出從V?出發的深度優先和廣度優先搜索序列。

四.應用編程題：（40'）

        1 在一個整形數組a中既有負數又有正數，編寫一個算法將a中所有負數移到整數之前， 要求其時間復雜度為O(n)，n為數組長度，并且只使用常數個輔助空間。

          例如：a[ ]={1,2,3,4,-1,1,-2,-1,-4}執行算法后的輸出為a[ ]={-4,-1,-2,-1,1,4,3,2,1}

        2 編寫一個C函數，輸入一個二叉樹的根節點，返回這棵樹中所有值大于0的節點值之和，如果根為空，返回0。

二叉樹的鏈式存儲結構對應的C語言的結點類型定義如下：

typedef struct node{  

ElemType data;  

struct node *lchild;  

struct node *rchild;  

}BTree;

說明：1.本試題為回憶版試題，某些題目的數值或者語言表述可能與原版不一致；   

           2.本試題僅供大家學習交流使用，嚴禁用于各類商業用途。

hotsummer86

專業課比中科大簡單。。。最起碼知識點少很多很多。。

magicyang112

編程題出題點和北航的好像啊。。。我囧 不過這題量最多只有北航的70%吧。。。。3小時？。。。。
中科的數據結構確實很難 很多很生的出題點。。。

zzfxjk

LZ.計算機不是全國統考啊!是不是有些院校還是自主考試啊?這是怎么回事啊?12年的求教....

ffwwd456

雖然我不是這個專業的........這個很像二級里的公共基礎[qq:13]

ewlwl

想了解華科軟院的同學可以論壇短信我，愿意回答各種有關問題[qq:20]

rocdevil

謝謝

沫小蝸

分享哈皮