廣東財經大學2019年研究生考研真題-809數(shù)據(jù)結構

1、歡迎報考廣東財經大學碩士研究生，祝你考試成功?。g迎報考廣東財經大學碩士研究生，祝你考試成功！（第1頁共5頁）1廣東財經大學碩士研究生入學考試試卷廣東財經大學碩士研究生入學考試試卷考試年度：考試年度：2019年考試科目代碼及名稱：考試科目代碼及名稱：809題適用專業(yè)：適用專業(yè)：085211［友情提醒：請在考點提供的專用答題紙上答題，答在本卷或草稿紙上無效?。荩塾亚樘嵝眩赫堅诳键c提供的專用答題紙上答題，答在本卷或草稿紙上無效?。菀弧⒁?、單

2、項選擇題（單項選擇題（1010題，每題題，每題2分，共分，共2020分）分）1、設n是描述問題規(guī)模的非負整數(shù)，下面的程序片段的時間復雜度是________。i=2while(inextpri=ppripprinext=pnextBpnext=pnextnextpnextpri=pCpprinext=pppri=ppripriDppri=pnextnextpnext=ppripri3、設棧S和隊列Q的初始狀態(tài)為空，元素e1、e2、e3、e

3、4、e5和e6依次進入棧S，一個元素出棧后即進入Q，若6個元素出隊的序列是e2、e4、e3、e6、e5和e1，則棧S的容量至少應該是________。A2B3C4D64、設有一個遞歸算法如圖1所示則計算fact(n)需要調用該函數(shù)的次數(shù)為________。An1Bn1CnDn2intfact(intn)n大于等于0if(n=0)return1elsereturnnfact(n1)圖1圖25、對圖2所示的帶權有向圖，若采用迪杰斯特拉(Di

4、jkstra)算法求從原點a到其他各頂點的最短路徑，則得到的第一條最短路徑的目標頂點是b，第二條最短路徑的目標頂點是c，后續(xù)得到的其余各最短路徑的目標頂點依次是________。Af，d，eBe，d，fCd，e，fDf，e，d6、串“ababaaababaa”的next數(shù)組為________。A012345678999B012121111212C0123012322345D0112342234567、對二叉樹的結點從1開始進行連續(xù)編號，

5、要求每個結點的編號大于其左、右孩子的編號，同一結點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用________遍歷實現(xiàn)編號。A先序B.中序C.后序D.從根開始按層次遍歷8、下面關于B和B樹的敘述中，不正確的是________。AB樹和B樹都是平衡的多叉樹BB樹和B樹都可用于文件的索引結構CB樹和B樹都能有效地支持順序檢索DB樹和B樹都能有效地支持隨機檢索9、對一組數(shù)據(jù)(2，121688510)進行排序，若前三趟排序結果如下：歡

6、迎報考廣東財經大學碩士研究生，祝你考試成功?。g迎報考廣東財經大學碩士研究生，祝你考試成功！（第3頁共5頁）3到的一趟快速排序結果為________。三、三、綜合應用題（綜合應用題（6題，每題題，每題1010分，共分，共6060分）分）1、設一棵二叉樹的先序序列：ABDFCEGH，中序序列：BFDAGEHC(1)畫出這棵二叉樹。(2)畫出這棵二叉樹的后序線索樹。(3)將這棵二叉樹轉換成對應的樹(或森林)。2、假設用于通信的電文僅由8個字

7、母組成，字母在電文中出現(xiàn)的概率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。(1)試為這8個字母設計赫夫曼(Huffman)編碼。(2)從數(shù)學期望的角度計算各字符赫夫曼編碼的平均長度；若這8個字母采用二進制等長編碼，各字符的平均編碼長度至少是多大？(3)簡述赫夫曼編碼的特點以及它試圖達到目標。3、已知無向圖G的邏輯結構圖如圖6所示，試回答下述問題。(1)畫出圖G的鄰接矩陣。(2)依據(jù)你畫出的鄰接矩

8、陣，若從編號為１的頂點出發(fā)遍歷該圖，請畫出其深度優(yōu)先生成樹。(3)依據(jù)你畫出的鄰接矩陣，若從編號為１的頂點出發(fā)遍歷該圖，請畫出其廣度優(yōu)先生成樹。(4)試說明深度優(yōu)先遍歷、廣度優(yōu)先遍歷需要分別借助什么數(shù)據(jù)結構方可實現(xiàn)。圖6圖74、求圖7所示的帶權連通圖G的最小生成樹(MST)，請回答下列問題：(1)若使用克魯斯卡爾(Kruskal)算法求圖G的MST，請依次寫出算法選出的邊；(2)若使用普利姆(Prim)算法，從頂點A開始求圖G的MST，

9、請依次寫出算法選出的邊；(3)圖Ｇ的MST唯一嗎？(4)請說明在什么情況下帶權連通圖的MST才會唯一。5、已知哈希函數(shù)為H(key)=key%11，哈希表長度為13，用平方探測再散列處理沖突。表中已存放6個記錄，它們的存儲地址為：addr(22)=0、addr(12)=1、addr(24)=2、addr(32)=10、addr(54)=10沖突，調整至11、addr(59)=4；其余地址為空。(1)寫出存儲地址計算式（H0＝？Hi＝？）

10、(2)現(xiàn)有第七個關鍵字65，寫出其存儲地址計算過程（要求寫出每一步的計算式和沖突處理）。(3)若查找關鍵字65的記錄，需依次與哪些關鍵字進行比較？(4)若刪除54應如何處理？6、已知一組關鍵值序列503，87，512，61，908，170，897，275，653，462，試采用堆排序法對該組序列進行降序排序，要求：(1)對該組序列進行降序排序，建立的初始堆應為大根堆還是小根堆？(2)用二叉樹的形式畫出所建立的初始堆；(3)畫出第一次輸出