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

1、2012年全國碩士研究生統(tǒng)一入學(xué)考試自命題試題年全國碩士研究生統(tǒng)一入學(xué)考試自命題試題學(xué)科與專業(yè)名稱：計算機技術(shù)，軟件工程考試科目代碼與名稱：830數(shù)據(jù)結(jié)構(gòu)考生注意：所有答案必須寫在答題紙（卷）上，寫在本試題上一律不給分。一.選擇題選擇題(每題每題2分，共分，共30分)1隊列操作的原則是（）。A.先進先出B.后進先出C.只能進行插入D.只能進行刪除2.一個棧的進棧序列是abcde則棧的不可能的輸出序列是（）。A.edcbaB.decbaC

2、.dceabD.abcde3.采用順序查找法查找長度為n的線性表時每個元素的平均查找長度為（）。A.nB.n2C.(n1)2D.(n1)24.線性表的鏈接實現(xiàn)有利于()運算。A.讀表元素B.插入C.查找D.定位5.設(shè)單鏈表中指針p指著結(jié)點A若要刪除A之后的結(jié)點(若存在)則需要修改指針的操作為()。A.pnext=pnextnextB.p=pnextC.p=pnextnextD.pnext=p6.在內(nèi)部排序中排序時不穩(wěn)定的有()。A.插入

3、排序B.冒泡排序C.快速排序D.歸并排序7.在AOE網(wǎng)中，完成工程的最短時間是（）。A從源點到匯點的最長路徑的長度B從源點到匯點的最短路徑的長度C最長的回路的長度D最短的回路的長度8以下（）方法所用輔助存儲空間最大。A堆排序B希爾排序C快速排序D歸并排序9具有8個頂點的無向圖至少應(yīng)有（）條邊才能確保是一個連通圖。A5B6C7D810.對具有n個結(jié)點的有序表中折半查找時，其時間復(fù)雜度是（）。AO(nlog2n）BO(log2n）CO(n）

4、DO(n2）11如果希望對平衡二叉樹遍歷的結(jié)果是升序的，應(yīng)采用（）遍歷方法。A先序B中序C后序D層次考試科目：數(shù)據(jù)結(jié)構(gòu)共5頁，第1頁三判斷題（每題三判斷題（每題1分，共分，共10分，正確的選分，正確的選t，錯誤的選，錯誤的選f）1如果T2是由樹T1轉(zhuǎn)換而來的二叉樹那T1中結(jié)點的先序就是T2中結(jié)點的先序。（）2在一個有向圖的鄰接表或逆鄰接表中，如果某個頂點的鏈表為空，則該頂點的度一定為零。（）3線性表中的每一個元素都有一個前驅(qū)和后繼元素。

5、（）4按中序遍歷一顆二叉排序樹所得到的中序遍歷序列f是一個遞增序列。（）5若網(wǎng)中有幾條關(guān)鍵路徑，提高一條關(guān)鍵路徑上的活動的速度，不能導(dǎo)致整個工程縮短工期。（）6一顆滿二叉樹同時又是一顆平衡樹。（）7數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的物理結(jié)構(gòu)、邏輯結(jié)構(gòu)以及它們之間的相互關(guān)系。（）8.拓撲排序是一種內(nèi)部排序的算法。()9.已知一顆樹的先序序列和后序序列，一定能構(gòu)造出該樹。（）10n階對稱矩陣可壓縮存儲到n22個元的空間中。()四.簡答題（簡答題（50分）

6、分）1.給定關(guān)鍵字序列T=(65，57，45，39，12，98，86，35），采用快速排序算法，以第一個元素為樞軸，對該序列由小到大排序，并寫出具體排序過程。(8分)2.簡述下列算法的功能。（6分）voidProcess(LinkListif((pnext)If(pnext)returnERRq=pnextwhile(qnextfree(s)pnext=qnextfree(q)3.使用克魯斯卡爾算法構(gòu)造出圖1所示的圖G的一棵最小生成樹（