2012年廣東暨南大學數(shù)據(jù)結(jié)構(gòu)考研真題

1、2012年廣東暨南大學數(shù)據(jù)結(jié)構(gòu)考研真題學科與專業(yè)名稱：計算機技術(shù)，軟件工程考試科目代碼與名稱：830 數(shù)據(jù)結(jié)構(gòu)考生注意：所有答案必須寫在答題紙（卷）上，寫在本試題上一律不給分。 一. 選擇題(每題2分，共30分)1隊列操作的原則是（ ）。A. 先進先出 B. 后進先出 C. 只能進行插入 D. 只能進行刪除2. 一個棧的進棧序列是a, b, c, d, e, 則棧的不可能的輸出序列是（ ）。 A. edcba B. decba C. dceab D. abcde3. 采用順序查找法查找長度為n的線性表時,每個元素的平均查找長度為 （ ）。 A. n B. n/2 C.(n+1)/2 D.(n-

2、1)/24. 線性表的鏈接實現(xiàn)有利于( )運算。A. 讀表元素 B.插入 C. 查找 D. 定位5. 設(shè)單鏈表中指針p指著結(jié)點A,若要刪除A之后的結(jié)點(若存在),則需要修改指針的操作為( )。A. p-next=p-next-next B. p=p-nextC. p=p-next-next D. p-next=p6. 在內(nèi)部排序中,排序時不穩(wěn)定的有( )。A. 插入排序 B. 冒泡排序 C. 快速排序 D. 歸并排序7. 在AOE網(wǎng)中，完成工程的最短時間是（ ）。A從源點到匯點的最長路徑的長度 B從源點到匯點的最短路徑的長度C最長的回路的長度 D最短的回路的長度8以下（ ） 方法所用輔助存儲空

3、間最大。A 堆排序 B 希爾排序 C快速排序 D歸并排序9具有8個頂點的無向圖至少應(yīng)有（ ）條邊才能確保是一個連通圖。A5 B6 C7 D810. 對具有n個結(jié)點的有序表中折半查找時，其時間復(fù)雜度是（ ）。 AO(nlog2n） BO(log2n） CO(n） DO(n2）11如果希望對平衡二叉樹遍歷的結(jié)果是升序的，應(yīng)采用（ ）遍歷方法。 A先序 B中序 C后序 D層次12. 稀疏矩陣一般的壓縮存儲方法有兩種,即:（ ）。 A. 二維數(shù)組和三維數(shù)組 B. 三元組和散列 C. 三元組和十字鏈表 D. 散列和十字鏈表13. 循環(huán)隊列中是否可以插入下一個元素 （ ）。 A. 與曾經(jīng)進行過多少次插入操

4、作有關(guān). B. 只與隊尾指針的值有關(guān),與隊頭指針的值無關(guān). C. 只與數(shù)組大小有關(guān),與隊首指針和隊尾指針的值無關(guān) D. 與隊頭指針和隊尾指針的值有關(guān).14. 在線索化二叉樹中，T所指結(jié)點沒有左子樹的充要條件是（ ）。AT-left=NULL BT-ltag=1 Ct-ltag=1且t-left=Null D以上都不對15. 以下說法中不正確的是（ ）。A無向圖中的極大連通子圖稱為連通分量B連通圖的廣度優(yōu)先搜索中一般要采用隊列來暫存剛訪問過的頂點C圖的深度優(yōu)先搜索中一般要采用棧來暫存剛訪問過的頂點D有向圖的遍歷不可采用廣度優(yōu)先搜索方法二填空題(每題2分，共20分)1一組記錄（50，40，95，2

5、0，15，70，60，45，80）進行冒泡排序時，第一趟需進行相鄰記錄的交換的次數(shù)為 。2數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別 。3由n個權(quán)值構(gòu)成的哈夫曼樹共有 個結(jié)點。4在散列表(hash)查找中，評判一個散列函數(shù)優(yōu)劣的兩個主要條件是： 和 。5單鏈表中設(shè)置頭結(jié)點的作用是 。6一棵深度為k的滿二叉樹的結(jié)點總數(shù)為 ，一棵深度為k的完全二叉樹的結(jié)點總數(shù)的最小值為 。7一個無向圖有n個頂點和e條邊，則所有頂點的度的和為 。8在二叉鏈表中判斷某指針p所指結(jié)點為葉子結(jié)點的條件是 。9堆棧是一種操作受限的線性表，它只能在線性表的 進行插入和刪除操作，對棧的訪問是按照 的原則進行的。10若某記錄序列的

6、關(guān)鍵字序列是（235，346，021，558，256），用鏈式基數(shù)排序方法排序，第一次收集的結(jié)果是 。三判斷題（每題1分，共10分，正確的選t，錯誤的選f）1如果T2是由樹T1轉(zhuǎn)換而來的二叉樹,那T1中結(jié)點的先序就是T2中結(jié)點的先序。（ ）2在一個有向圖的鄰接表或逆鄰接表中，如果某個頂點的鏈表為空，則該頂點的度一定為零。（ ）3線性表中的每一個元素都有一個前驅(qū)和后繼元素。（ ）4按中序遍歷一顆二叉排序樹所得到的中序遍歷序列f是一個遞增序列。（ ）5若網(wǎng)中有幾條關(guān)鍵路徑，提高一條關(guān)鍵路徑上的活動的速度，不能導(dǎo)致整個工程縮短工期。 （ ）6一顆滿二叉樹同時又是一顆平衡樹。（ ）7數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)

7、的物理結(jié)構(gòu)、邏輯結(jié)構(gòu)以及它們之間的相互關(guān)系。（ ）8. 拓撲排序是一種內(nèi)部排序的算法。( ) 9.已知一顆樹的先序序列和后序序列，一定能構(gòu)造出該樹。（ ）10n階對稱矩陣可壓縮存儲到n2/2個元的空間中。( )四. 簡答題（50分）1. 給定關(guān)鍵字序列 T=(65，57，45，39，12，98，86，35），采用快速排序算法，以第一個元素為樞軸，對該序列由小到大排序，并寫出具體排序過程。 (8分)2. 簡述下列算法的功能。（6分）void Process(LinkList &L, int x, int y) / L線性表的元素遞增有序排列 LinkList p=L, q, s; if (p-n

8、ext) & (xnext & p-next-datanext; If (p-next) return ERROR; q=p-next; while (q-next & q-next-datanext; free(s); p-next=q-next;free(q); 3. 使用克魯斯卡爾算法構(gòu)造出圖1所示的圖G的一棵最小生成樹（要求寫出構(gòu)造過程）。（10分） 圖14. 已知一個圖如圖2所示，若從頂點a出發(fā)，按深度優(yōu)先搜索法進行遍歷，寫出可能得到的一種頂點序列；按廣度優(yōu)先搜索法進行遍歷，寫出可能得到的一種頂點序列。 (4分) 圖25. 給定圖3所示帶權(quán)有向圖及其鄰接矩陣，利用Floyd算法，求每

9、一對頂點之間的最短路徑及其路徑長度（要求寫出求解過程）。 （12分） 圖3 6給出一組關(guān)鍵字的序列為 12，15，34，37，39，22，38，66，74，80，107 ，假設(shè)哈希函數(shù)為Hash(key)=key mod 11，畫出按照鏈地址法處理沖突構(gòu)造所得的哈希表，并在記錄的查找概率相等的前提下，計算成功查找的平均查找長度。（10分）五算法填空，（每空2分,共16分）1. 下面的算法將元素e加入隊列Q中，請在處填上適當內(nèi)容，使其成為一個完整算法。typedef struct QNode QElemType data; struct QNode *next; QNode, *QueuePtr

10、;typedef struct QueuePtr front; / 隊頭指針 QueuePtr rear; / 隊尾指針 LinkQueue, * LinkQueuePtr;Boolean EnQueue (LinkQueuePtr Q, QElemType e) /元素e加入到隊列Q中 p = ; if (!p) return FALSE; p-data = e; p-next = ; = p; Q-rear = ; return TRUE;2. 下面是先序遍歷二叉樹的算法非遞歸算法，請在處填上適當內(nèi)容，使其成為一個完整算法。typedef struct BiTNode / 結(jié)點結(jié)構(gòu) TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指針 BiTNode, *BiTree;void PreOrderTraverse(BiTree ,Status(*Visit)(TElemType) /采用二叉鏈表存儲結(jié)構(gòu),Visit是對結(jié)點操作的