廣東財(cái)經(jīng)大學(xué)2019年研究生考研真題-809數(shù)據(jù)結(jié)構(gòu)

1、歡迎報(bào)考廣東財(cái)經(jīng)大學(xué)碩士研究生，祝你考試成功！（歡迎報(bào)考廣東財(cái)經(jīng)大學(xué)碩士研究生，祝你考試成功?。ǖ?頁共5頁）1廣東財(cái)經(jīng)大學(xué)碩士研究生入學(xué)考試試卷廣東財(cái)經(jīng)大學(xué)碩士研究生入學(xué)考試試卷考試年度：考試年度：2019年考試科目代碼及名稱：考試科目代碼及名稱：809題適用專業(yè)：適用專業(yè)：085211［友情提醒：請(qǐng)?jiān)诳键c(diǎn)提供的專用答題紙上答題，答在本卷或草稿紙上無效?。荩塾亚樘嵝眩赫?qǐng)?jiān)诳键c(diǎn)提供的專用答題紙上答題，答在本卷或草稿紙上無效?。菀?、一、單

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

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

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

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

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

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

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

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

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