|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
2016年暨南大學計算機科學與技術、軟件工程830數據結構考研真題考研試題
2016年全國碩士研究生統一入學考試自命題試題（A卷）
********************************************************************************************
學科、專業名稱：計算機科學與技術、軟件工程
研究方向：計算機系統結構081201，計算機軟件與理論081202，計算機應用技術081203，軟件工程083500，計算機技術(專業學位) 085211，軟件工程(專業學位) 085212
考試科目名稱及代碼：數據結構830
| 考生注意：所有答案必須寫在答題紙（卷）上，寫在本試題上一律不給分。 |
| 一、 單項選擇題(每題2分，共30分)
1. 在線索化二叉樹中，T所指結點沒有左子樹的充要條件是（ ）。
A. T-> lchild=NULL B. T->ltag=1
C. t->ltag=1且t-> lchild =Null D. 以上都不對
2. 一個帶有頭結點的單鏈表為空的判定條件是 ( )。
A. head == NULL B. head->next == NULL
C. head->next == head D. head != NULL
3. 線性鏈表不具有的特點是（ ）。
A. 隨機訪問 B. 不必預估所需存儲空間大小
C. 插入與刪除時不必移動元素 D. 所需空間與線性表長度成正比
4. 在下面的排序方法中，穩定的是（ ）。
A. 希爾排序 B. 堆排序 C. 插入排序 D. 快速排序
5.設有n個待排序的記錄關鍵字，則在堆排序中需要（ ）輔助記錄空間。
A．O(1) B. O(n) C. O(nlog2n) D. O(n2)
6. 數組A［５］［６］的每個元素占5個字節，將其按行優先次序存儲。假設A[1][1]元素的存儲地址為1000，則元素A［５，５］的存儲地址為( )。
A. 1140 B. 1145 C. 1120 D. 1125
7. 高度為n的完全二叉樹的結點數至少為（ ）。
A. 2n-1 B. 2n-1+1 C. 2n D. 2n+1
8. 設有一個無向圖G=（V，E）和G’=（V’，E’），如果G’為G的生成樹，則下面不正確的說法是（ ）。
A．G’為G 的子圖 B．G’為G 的連通分量
C．G’為G的極小連通子圖且V’=V D．G’為G的一個無環子圖 9. 在有向圖的鄰接表存儲結構中，頂點V在表結點中出現的次數是（ ）。
A. 頂點V的度 B. 頂點V的出度
C. 頂點V的入度 D. 依附于頂點V的邊數
10. 關鍵路徑是事件結點網絡中( )。
A．最短的回路 B．從源點到匯點的最短路徑
C．最長的回路 D．從源點到匯點的最長路徑
| 考試科目： 數據結構 共 5 頁，第 1 頁
|
11. 一個有n個結點的無向圖最多有（ ）條邊。
A. n B. n-1 C. n(n-1) D. n(n-1)/2
12. 對某個無向圖的鄰接矩陣來說，( )。
A．第i行上的非零元素個數和第i列的非零元素個數一定相等
B．矩陣中的非零元素個數等于圖中的邊數
C．第i行上，第i列上非零元素總數等于頂點vi的度數
D．矩陣中非全零行的行數等于圖中的頂點數
13. 平衡二叉樹的平均查找長度是 ( )。
A. O(n2） B. O(nlog2n） C. O(n） D. O(log2n）
14. 下列哪種排序需要的附加存儲開銷最大( )。
A. 快速排序 B. 堆排序 C. 歸并排序 D. 插入 排序
15. 設一數列的順序為1,2,3,4,5,6, 通過棧操作可以得到（ ）的輸出序列。
A. 3,2,5,6,4,1 B. 1,5,4,6,2,3
C. 6,4,3,2,5,1 D. 3,5,6,2,4,1
二．填空題(每空2分，共20分)
1. 在一個長度為n的順序表中刪除第i個元素時，需向前移動 個元素。
2. 設數組Data[0..m]作為循環隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針
則執行出隊操作時front指針的值應更新為 front= 。
3. 在單鏈表中，若要刪除指針p所指結點的后一結點，則需要執行下列語句：（設q為指針
變量）q=p->next; ； 。
4. 在有n個結點的二叉鏈表中，值為NULL的鏈域的個數為 。
5. 二叉樹中度為0的結點數為30，度為1的結點數為30，總結點數為 。
6. 在堆排序的過程中，對任一分支結點進行篩選運算的時間復雜度為 ，整個堆排序過程的時間復雜度為 。
7. 對于n個記錄（假設每個記錄含d個關鍵字）進行鏈式基數排序，總共需要進行 趟分配和收集。
8. 設有向圖G中有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，則該圖的一種拓撲序列為 。
三．判斷題（每題1分，共10分，正確的選t，錯誤的選f）
1. 在n個頂點的無向圖中，若邊數>n-1，則該圖必是連通圖。 （ ）
2. 具有n個結點的二叉排序樹有多種，其中樹高最小的二叉排序樹是最佳的（ ）
3. 使用散列法存儲時，哈希表的大小可隨意選取，通常取10的倍數。（ ）
4. 向一個二叉排序樹插入新的結點時，新插入的結點總是葉子結點（ ）
5. 數據元素是數據的最小單位。（ ）
6. 普里姆(Prim)算法相對于克魯斯卡爾(Kruskal)算法更適合求一個稀疏圖G的最小生成樹。（ ）
7. 向二叉排序樹中插入一個新結點，需要比較的次數可能大于此二叉樹的高度h。（ ）
8. 向一棵B_樹插入元素的過程中，若最終引起樹根結點的分裂，則新樹高度為原樹的高度加1。（ ）
9. 無向圖的鄰接矩陣一定是對稱陣。 ( )
10. 對小根堆進行層次遍歷可以得到一個有序序列。（ ）
| 考試科目： 數據結構 共5 頁，第 2 頁
| 四. 簡答題（45分）
1. 已知二叉樹的前序遍歷序列是AEFBGCDHIKJ，中序遍歷序列是EFAGBCHKIJD，求解下列問題： (1) 畫出此二叉樹。（4分） (2) 將該二叉樹轉換成森林。（4分）
2. 設有一組關鍵字（71,23,73,14,55,89,33,43,48）,采用哈希函數：H(key)=key %10，采
用開放地址的二次探測再散列方法解決沖突，試在散列地址空間中對該關鍵字序列(按從左
到右的次序)構造哈希表，并計算在查找概率相等的前提下，成功查找的平均查找長度。
（7分）
3. 設有一組初始記錄關鍵字為(3,1,4,6,8,2,5)，要求構造一棵平衡二叉樹，并給出構造過程。
（5分）
4. 對圖1所示的無向加權圖完成下列要求：
（1）寫出它的鄰接表；（5分）
（2）按克魯斯卡爾（Kruskal）算法求其最小生成樹，并給出其過程。（6分）
（3）給出從頂點a開始的深度優先搜索序列和深度優先生成樹。（4分）
圖 1
5. 已知序列(142,543,123,65,453,879,572,434,111,242,811,102)。
(1) 采用希爾排序對該序列作升序排序，請給出第一趟排序的結果（初始步長為7）。（5分）
(2) 采用堆排序對該序列作升序排序，請給出初始堆以及第一趟排序的結果。（5分）
五．算法填空，（每空2分,共20分）
1. 下面算法實現對一個不帶頭結點的單鏈表L進行就地（不增加額外存儲空間）逆置。請在__________處填上適當內容，使其成為一個完整算法。
typedef int DataType;
typedef struct {
DataType data;
struct Node *next;
}Node;
typedef Node * LinkList;
| 考試科目： 數據結構 共5 頁，第 3 頁
| LinkList Reverse(LinkList L)
{
LinkList p, q;
if (!L) return; //鏈表為空返回
p=L->next; q=L->next; L->next=NULL;
while(q)
{
q=q->next;
(1)
(2)
p=q;
}
return L;
}
2. 下面是一個采用二叉鏈表存儲結構, 中序遍歷線索二叉樹T的算法。 Visit是對結點操作的應用函數。請在__________處填上適當內容，使其成為一個完整算法。
/*二叉樹的二叉線索存儲表示*/
Typedef enum PointerTag{Link, Thread};
typedef struct BiThrNode {
TelemType data;
struct BiThrNode *lchild, *rchild;
PointerTag LTag, RTag;
} BiThrNode, *BiThrTree;
Status InOrderTraverse_Thr(BiThrTree T, Status(* Visit)(TelemType e))
{
BiThrNode *p;
p= (3)
while(p!=T){ //空樹或遍歷結束時p==T
while(p->LTag==Link) (4)
if(!Visit(p->data)) return ERROR;
while (p->RTag==Thread && (5)
{
(6)
Visit（p->data）； }
(7)
}
return OK;
}
| 考試科目： 數據結構 共5 頁，第 4 頁
| 3. 下面是一個利用遞歸對二叉排序樹進行查找的算法。請在__________處填上適當內容，使其成為一個完整算法。
typedef struct BTreeNode {
TelemType data;
struct BTreeNode *lchild, *rchild;
} BTreeNode;
bool Find(BTreeNode* T, TelemType& item)
{
if( (8) )
return FALSE; //查找失敗
else {
if (item==T->data) //查找成功
return TRUE;
else if(item<T->data)
return Find( (9) , item );
else
return Find( (10) , item );
}
}
六．編寫算法（25分）
1. 設有一組初始記錄關鍵字序列（K1，K2，…，Kn），要求設計一個算法能夠在O(n)的時間復雜度內將線性表劃分成兩部分，其中左半部分的每個關鍵字均小于Ki，右半部分的每個關鍵字均大于等于Ki。（10分）
2. 設有一整型數組w保存n個字符的權值（均大于0），請寫出
(1) 構造赫夫曼樹(Huffman)的算法。（8分）
(2) 求各字符赫夫曼編碼的算法。（7分）
| 考試科目： 數據結構 共5 頁，第 5 頁
免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。
|
文章搜索
您現在的位置： 
