2019年暨南大學研究生入學試題830數(shù)據(jù)機構考題

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

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

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

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

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

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

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