|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
第 1 頁 共 8 頁
華僑大學 2018 年碩士研究生入學考試專業課試卷
（答案必須寫在答題紙上）
招 招生專業 計算機技術
科 考試科目名稱 數據結構與 C++ 科目代碼 827
第一部分 數據結構 (共 75 分)
一. 單項選擇題（每題 2 分，共 10 分）
1. 在一個單鏈表中，將指針 q 所指結點作為指針 p 所指結點的后繼進行插
入的操作是( )。
A. q->next=p; p->next=q; B. q->next=p->next ; p->next=q;
C. q->next=p; p=p->next; D. p->next=q; q->next=p;
2. 在一棵度為 3 的樹中，度為 3 的結點個數為 2，度為 2 的結點個數為 2，
則葉子結點個數為( )。
A．4 B．5 C．6 D．7
3. 對下列四種排序方法，在排序中關鍵字比較次數同記錄初始排列無關的是
( )。
A． 直接插入 B. 二分法插入 C. 快速排序 D. 歸并排序
4. 設有一個電文，其中有 5 個不同字符，每個字符的出現次數分別為 5，3，
4，2，6，那么將這個電文進行哈夫曼編碼后得到的電文有多少個二進制
位？（ ）。
A.55 B．60 C．65 D．70
5. 后綴算數表達式串“2 4 * 5 -”的計算結果為( )
A. 1 B. 2 C. 3 D. 4
第 2 頁 共 8 頁
二. 問答題（共 40 分）
1. （8分）已知二叉樹T的后序遍歷序列是DCBFHGEA，中序遍歷序列是
BDCAFEHG。
（1） 畫出二叉樹T的樹形；（4分）
（2） 用虛線在T上添加先序線索。（4分）
2. （10分）設無向圖G包含A、B、C、D、E、F、G 7個頂點，我們用(A, B, 5)表示
頂點A和B之間有一條權值為5的無向邊。則圖G由如下無向邊構成：(A,B,2)、
(A,D,3)、(A,C,1)、(B,D,2)、(D,C,5)、(E,B,6)、(E,D,1)、(E,C,3)。
（1） 畫出圖G的帶權鄰接表，要求帶權鄰接表的每個頂點的鄰接鏈表中表結點的
頂點序號按升序排列；（5分）
（2） 請基于該鄰接表畫出普里姆（Prim）算法從頂點A出發得到的最小生成樹，
請給出生成過程；（5分）
3. （12分）已知一組記錄的關鍵字為（15，25，18，5，27，1，39，33，6，17，
13，28，23）。按哈希函數H(Key) = Key MOD 13和線性探測再散列處理沖突的
方法在地址空間A[0..13]中構造哈希表，畫出地址空間A[0..13]中每個位置存放記
錄的關鍵字，如果沒有存放記錄則留空。并計算等概率情況下，查找成功的平
均查找長度。
4. （10分）設有一個關鍵字輸入序列（4，5，6，1，2，3），試從空樹開始構造
平衡二叉排序樹，畫出每加入一個結點后二叉樹的形態，若發生不平衡，請指
出平衡調整的類型并畫出調整結果。然后計算在等概率情況下，查找成功的平
均查找長度ASL。
三．程序設計題（共 25 分）
1. （10 分）寫一個算法將結點數據降序排列的單向鏈表中的重復結點刪除。
2. （15 分）已知一無向圖 G 以鄰接表作為存儲結構，請
（1）寫出鄰接表存儲結構的定義.（2 分）
（2）編寫程序輸出圖中的所有簡單環路（簡單環路是除了第一個和最后
一個結點相同外，其余結點均不同的一條路徑）。（13 分）
第 3 頁 共 8 頁
第二部分 C++ (共 75 分)
一. 選擇題（單選，每小題 2 分，共 20 分）
1. 以下程序的運行結果為（ ）。
#include
using namespace std;
void main(void){
int i=1,j=0;
if(--i&&j++) cout
免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。
|
文章搜索
您現在的位置： 
