2019年暨南大學(xué)研究生入學(xué)試題830數(shù)據(jù)機(jī)構(gòu)考題

1、2019年全國碩士研究生統(tǒng)一入學(xué)考試自命題試題（年全國碩士研究生統(tǒng)一入學(xué)考試自命題試題（A卷）卷）招生專業(yè)與代碼：計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程、網(wǎng)絡(luò)空間安全、工程碩士研究方向：計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)081201，計(jì)算機(jī)軟件與理論081202，計(jì)算機(jī)應(yīng)用技術(shù)081203，軟件工程083500，計(jì)算機(jī)技術(shù)(專業(yè)學(xué)位)085211，網(wǎng)絡(luò)空間安全083900考試科目名稱及代碼：數(shù)據(jù)結(jié)構(gòu)830考生注意：所有答案必須寫在答題紙（卷）上，寫在本試題上一律不給分

2、?？忌⒁猓核写鸢副仨殞懺诖痤}紙（卷）上，寫在本試題上一律不給分。一、單項(xiàng)選擇題單項(xiàng)選擇題(每題每題2分，共分，共3030分)1.在任意一棵二叉樹的先序序列和后序序列中，各葉子之間的相對次序關(guān)系()。A不一定相同B互為逆序C都不相同D都相同2.深度為4的二叉樹至多有結(jié)點(diǎn)數(shù)為（）。A.18B.14C.15D.163.在一個具有n個頂點(diǎn)的有向圖中，若所有頂點(diǎn)的入度數(shù)之和為m，則所有頂點(diǎn)的度數(shù)之和為（）。AmBm1Cm1D2m4.快速排序在

3、()情況下最不利于發(fā)揮其長處。A.被排序的數(shù)據(jù)量太大.B.被排序數(shù)據(jù)中含有多個相同的關(guān)鍵字C.被排序的數(shù)據(jù)完全無序D.被排序的數(shù)據(jù)已基本有序5.一組記錄的關(guān)鍵字為（458055404285）則利用堆排序的方法建立的初始堆為（）。A.（804555404285)B.(858055404245)C.(858055454240)D.(855580424540)6.對有18個元素的有序表（下標(biāo)為1~18）作折半查找則查找A[3]的比較序列的下標(biāo)

4、為()。A.123B.9523C.953D.94237.具有n個頂點(diǎn)的完全有向圖的邊數(shù)為()。A.n(n1)2B.n(n1)C.n2D.n218.利用逐點(diǎn)插入法建立序列（50724385752035456530）對應(yīng)的二叉排序樹以后，查找元素35要進(jìn)行（）。A.4次B.5次C.3次D.2次9.判定一個有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ猓€可以用（）。A求最短路徑的Floyd方法B求最短路徑的Dijkstra方法C廣度優(yōu)先遍歷算

5、法D深度優(yōu)先遍歷算法10.對于一個具有n個頂點(diǎn)的無向連通圖，它包含的連通分量的個數(shù)為（）。A0B1CnDn111.在一個單鏈表中若p所指的結(jié)點(diǎn)不是最后一個結(jié)點(diǎn)在p之后插入s所指的結(jié)點(diǎn)則執(zhí)行()。A.snext=ppnext=sB.pnext=ssnext=pC.p=ssnext=pnextD.snext=pnextpnext=s考試科目：數(shù)據(jù)結(jié)構(gòu)共5頁，第1頁考試科目：數(shù)據(jù)結(jié)構(gòu)共5頁，第2頁四.簡答題（簡答題（40分）分）1.設(shè)G為有n

6、個頂點(diǎn)的無向連通圖，證明G至少有n1條邊。（7分）2.什么是線索二叉樹？一棵二叉樹的中序遍歷序列為djbaechif，前序遍歷序列為abdjcefhi請畫出該二叉樹的后序線索二叉樹。（7分）3.已知某通訊電文僅有A、B、C、D、E、F六個字符構(gòu)成，其出現(xiàn)頻率分別為235148257請給出他們的Huffman編碼以及求解過程。(7分）4、給定一棵二叉鏈表存儲的二叉樹，試用文字描述判定一棵二叉樹是否是完全二叉樹的算法基本思想。（7分）5.已

7、知一棵完全二叉樹共有67個結(jié)點(diǎn)，試求:（7分）(1)樹的深度；(2)度為1的結(jié)點(diǎn)數(shù)；(3)葉子結(jié)點(diǎn)數(shù)；6.對給定的一組關(guān)鍵字序列（2918254758125110）寫出用歸并排序方法進(jìn)行排序的變化過程。（5分）五算法填空算法填空（共2小題，每空小題，每空2分，共分，共20分）1.若二叉排序樹T中存在其關(guān)鍵字等于key的數(shù)據(jù)元素時，則下面算法刪除該數(shù)據(jù)元素結(jié)點(diǎn)，并返回TRUE；否則返回FALSE。請?jiān)赺_______處填上適當(dāng)內(nèi)容，使其成