暨南大學(xué)計(jì)算機(jī)830數(shù)據(jù)結(jié)構(gòu)2014年真題

1、2014年招收攻讀碩士學(xué)位研究生入學(xué)考試試題年招收攻讀碩士學(xué)位研究生入學(xué)考試試題(A卷)招生專業(yè)與代碼：計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)081201，計(jì)算機(jī)軟件與理論081202，計(jì)算機(jī)應(yīng)用技術(shù)081203，軟件工程083500，計(jì)算機(jī)技術(shù)(專業(yè)學(xué)位)085211，軟件工程(專業(yè)學(xué)位)085212考試科目名稱及代碼：數(shù)據(jù)結(jié)構(gòu)830考生注意：所有答案必須寫在答題紙（卷）上，寫在本試題上一律不給分。一選擇題一選擇題(每題每題2分，共分，共3030分)1.數(shù)據(jù)

2、結(jié)構(gòu)是研究數(shù)據(jù)的()以及它們之間的相互關(guān)系.A.理想結(jié)構(gòu)物理結(jié)構(gòu)B.理想結(jié)構(gòu)抽象結(jié)構(gòu)C.物理結(jié)構(gòu)邏輯結(jié)構(gòu)D.抽象結(jié)構(gòu)邏輯結(jié)構(gòu)2.線性表的鏈接實(shí)現(xiàn)有利于()運(yùn)算A.插入B.讀表元素C.查找D.定位3從一個長度為n的順序表中刪除第i個元素（1≤i≤n）時，需向前移動（）個元素.A.niB.ni1C.ni1D.i4.具有n個頂點(diǎn)的完全有向圖的邊數(shù)為().A.n(n1)2B.n(n1)C.n2D.n215.快速排序在()情況下最不利于發(fā)揮其長處

3、.A.被排序的數(shù)據(jù)量太大.B.被排序數(shù)據(jù)中含有多個相同的關(guān)鍵字.C.被排序的數(shù)據(jù)完全無序D.被排序的數(shù)據(jù)已基本有序6.線性表采用鏈?zhǔn)酱鎯r其地址().A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)與否均可以7.一個棧的進(jìn)棧序列是abcde則棧的不可能的輸出序列是()A.edcbaB.decbaC.dceabD.abcde8.采用順序查找法查找長度為n的線性表時每個元素的平均查找長度為()A.nB.n2C.(n1)2D

4、.(n1)29.下列哪種排序需要的附加存儲開銷最大().A快速排序B堆排序C歸并排序D插入排序10.具有6個頂點(diǎn)的無向圖至少應(yīng)有（）條邊才能確保是一個連通圖.A5B6C7D811.對具有n個結(jié)點(diǎn)的有序表中折半查找時，其時間復(fù)雜度是().A.O(log2n）B.O(nlog2n）C.O(n）D.O(n2）12.通過一趟排序就能從整個記錄序列中選擇出具有最大（或最小）關(guān)鍵字的記錄，這種排序方法是().A.歸并排序B.快速排序C.直接插入排序

5、D.堆排序考試科目：數(shù)據(jù)結(jié)構(gòu)共4頁，第1頁四簡答題（共四簡答題（共4545分）分）1.已知一棵二叉樹的中序?yàn)镃DBAGFHE后序?yàn)镈CBGHFEA畫出這棵二叉樹.(6分)2.如圖1所示的AOE網(wǎng)(V1表示工程的開始V8表示工程的結(jié)束)假設(shè)工程從時間0開始求出所有事件和活動允許發(fā)生的最早及最晚時間并給出關(guān)鍵路徑.(14分)圖13.簡述下列算法的功能.（6分）voidprocess(SqlistWhile（iL.lengthf(j=i1jL