2017華科軟件專業課分享

P灰灰 · 發表于 2017-7-9 20:50

本帖最后由 as3652553 于 2017-11-30 21:13 編輯

2017年華中科技大學887數據結構與算法分析

一．名詞解釋（25分，1個5分）
1.1堆分配存儲表示
1.2完全圖
1.3樹的結點層次
1.4拓撲排序
1.5時間復雜度

二．選擇題（25分，1個5分）
2.1 折半查找的平均時間復雜度是（B）
A. 1                                                       B.logn
C. n                                                       D. n

2.2
int frog｛
if(n==0)
return 1;
else
return （n+frog（n-1）/2）;
｝
上述算法時間復雜度是多少（B）
A. logn                                              B.n
C.  nlogn                                     D. (n)`2

2.3一個算法的時間復雜度與什么有關（D）
A. 存儲器的大小                               B. 編程語言
C. 計算機的主頻                               D. 循環執行的次數

2.4具有20個樹葉的二叉樹中只有1個孩子的結點個數是11，則這個二叉樹總的結點個數是多少（A）
A. 50                                              B.49
C. 51                                              D.52

2.5下列關于隊列說話不正確的是（B）
A. 先進先出                                     B.后進先出
C. 插入刪除只能在端點             D. 插入刪除在不同點進行

三．簡答題（60分）

3.1｛1，2，3，4，5，6，7，8｝利用數組建成一個最大堆并使用堆排序將其排序唯一個升序數組。要求畫出所有中間過程。

3.2 先序為 ABDFGHCE 中序 BFDHGACE 畫出該樹

3.3給出一個鄰接矩陣畫出克魯斯卡爾算法具體過程
00  4 4 2 1
4 00  1  00 2
4 1  00 5 3
2 00  5  00 4
1 2 3 4 00

3.4 13個權值為5， 18，12，13，4，6，7，9，28，16，20，30，2
給出哈夫曼樹并設計編碼

3.5給出輸出結果并說明函數功能。
void Print(int w)
{
int i;
if (w!=0)
{
Print(w-1);
for(i=1:i<=w;i++)
printf(“%d, ”,w);
printf(“/n”);
}
}

四．算法設計（40分）（編碼困難可以寫偽代碼，會適當扣分）
4.1求二叉樹所有具有兩個子女的結點個數，如果根節點為空，則返回0。
typedef struct Bintreenode{
int data；
struct Bintreenode *right；
struct Bintreenode *left；
} *Bintreenode；
4.2 一個長度為n數組由負數 0 正數組成，編寫函數，將其重新排序為前面都是負數，中間都是0  .后面都是正數的結構。要求時間復雜度為n。
關于2018華科軟院887復習八套卷
本套試題針對2018華科軟件887數據結構與算法分析而制，內容與往年大綱一致，鑒于15-17年題型難度趨于穩定，本套卷將嚴格按照往年出題風格，希望各位考生能考到理想的成績。

附2015-2017考研真題題型。
1名詞解釋（25分，1個5分）
5個名詞留一大段空白給出解釋。
例：完全圖（2017）

答：若一個圖的每一對不同頂點恰有一條邊相連，則稱為完全圖。完全圖是每對頂點之間都恰連有一條邊的簡單圖。n個端點的完全圖有n個端點及n(n ? 1) / 2條邊。

范圍：數據結構的概念，時間復雜度，線性表，棧隊列，樹，圖，排序算法，查找。
將總結出的算法解釋背誦即可。

2.選擇題（25分，1個5分）
選擇題中經常出現關于時間復雜度的分析。（17年考了3道）
2.1 折半查找的平均時間復雜度是（B）
A. 1                                                       B.logn
C. n                                                       D. n

2.2
int frog｛
if(n==0)
return 1;
else
return （n+frog（n-1）/2）;
｝
上述算法時間復雜度是多少（B）
A. logn                                              B.n
C.  nlogn                                        D. (n)`2

2.3一個算法的時間復雜度與什么有關（D）
A. 存儲器的大小                               B. 編程語言
C. 計算機的主頻                               D. 循環執行的次數
堆棧的概念，樹圖中的計算題。

3.簡答題（60分）

5道題
樹的二道。（前中得后，中后得前，后序表達式，最優二叉樹）
圖的一道。（給出圖，寫出過程）普里姆，克魯斯卡爾，迪杰斯特拉
排序一道。近幾年經常考關于堆排序得知識。
給出代碼，寫出運行結果。（一道）

4.算法設計（40分）（編碼困難可以寫偽代碼，會適當扣分）

基本上每年2道，一道線性表，一道樹的，圖的代碼沒考過。
例：求出鏈表L的倒數第N個結點的data。
先別急的寫代碼
首先用注釋的形式寫出代碼的大概過程

/*輸入：鏈表L，結點K
定義兩個結點指針p1，p2指向該鏈表的頭結點，利用p1遍歷整個鏈表，記下長度n
然后再利用p2往后遍歷n-k個結點
輸出：結點K的data
異常：沒有第K個結點，輸入為空指針*/

之后再是代碼

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)
｛
。。。。
｝
寫代碼需要充分考慮所有的測試用例