2012年暨南大學(xué)數(shù)據(jù)結(jié)構(gòu)全國考研真題.doc

1、暨南大亭a' JINAN UNIVERSITY2012年全國碩士研究生統(tǒng)一入學(xué)考試自命題試題* 學(xué)科與專業(yè)名稱：計算機技術(shù)，軟件工程 考試科目代碼與名稱：830數(shù)據(jù)結(jié)構(gòu)考生注意：所有答案必須寫在答題紙（卷）上，寫在本試題上一律不給分。一.選擇題（每題2分，共30分）1 .隊列操作的原則是（）?？荚嚳颇浚簲?shù)據(jù)結(jié)構(gòu)共5頁，第2 頁A.先進先出B.后進先出C.只能進行插入D.只能進行刪除則棧的不可能的輸出序列是（2 . 一個棧的進棧序列是a, b, c, d, e,A. edcbaB. decbaC.dceabD. abcde3 .采用順序查找法查找長度為n的線性表時，每個元素的平均查找長度

2、為（）。A. n B. n/2C.（n+1）/2D.（n-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.從源點到匯點的最長路徑

3、的長度B.從源點到匯點的最短路徑的長度C.最長的回路的長度D.最短的回路的長度8 .以下（）方法所用輔助存儲空間最大。A.堆排序B.希爾排序C.快速排序D.歸并排序9 .具有8個頂點的無向圖至少應(yīng)有（）條邊才能確保是一個連通圖。A. 5B. 6C. 7D. 810 .對具有n個結(jié)點的有序表中折半查找時，其時間復(fù)雜度是（）。A. O（nlog2n）B. O（log2n）C. O（n）D, O（n2）11 .如果希望對平衡二叉樹遍歷的結(jié)果是升序的，應(yīng)采用（）遍歷方法。A.先序B.中序C.后序D.層次12 .稀疏矩陣一般的壓縮存儲方法有兩種，即：（）。A.二維數(shù)組和三維數(shù)組B.三元組和散列C.三元組

4、和十字鏈表D.散列和十字鏈表13 .循環(huán)隊列中是否可以插入下一個元素（）。A.與曾經(jīng)進行過多少次插入操作有關(guān).B.只與隊尾指針的值有關(guān)，與隊頭指針的值無關(guān).C.只與數(shù)組大小有關(guān)，與隊首指針和隊尾指針的值無關(guān)D.與隊頭指針和隊尾指針的值有關(guān).14 .在線索化二叉樹中，T所指結(jié)點沒有左子樹的充要條件是（）。A. T->left=NULLB. T->ltag=1C. t->ltag=1 且 t->left=NullD.以上都不對15.以下說法中不正確的是（）。A.無向圖中的極大連通子圖稱為連通分量B .連通圖的廣度優(yōu)先搜索中一般要采用隊列來暫存剛訪問過的頂點C .圖的深度優(yōu)先

5、搜索中一般要采用棧來暫存剛訪問過的頂點D.有向圖的遍歷不可采用廣度優(yōu)先搜索方法二.填空題（每題2分，共20分）1 . 一組記錄（50, 40, 95, 20, 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條邊，則所有

6、頂點的度的和為 。8 .在二叉鏈表中判斷某指針p所指結(jié)點為葉子結(jié)點的條件是 9 .堆棧是一種操作受限的線性表，它只能在線性表的 進行插入和刪除操作，對棧的 訪問是按照 的原則進行的。10 .若某記錄序列的關(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ū)和后繼元素。

7、（）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)造出該樹。（）10 . n階對稱矩陣可壓縮存儲到n2/2個元的空間中。（）4 .簡答題（50分）1 .給定關(guān)鍵字序列T=（65, 57, 45, 39, 12, 98, 86, 35）,采用快速排序算法，以第一個元素為樞軸，對該序

8、列由小到大排序，并寫出具體排序過程。 （8分）2 .簡述下列算法的功能。（6分）void Process（LinkList &L, int x, int y） / L 線性表的元素遞增有序排列LinkList p=L, q, s;if （p->next） && （x<=y） while （p->next && p->next->data<=x） p=p->next;If （p->next） return ERROR;q=p->next;while （q->next && q-&g

9、t;next->data<y） s=q; q=q->next; free（s）; p->next=q->next;free（q）;3 .使用克魯斯卡爾算法構(gòu)造出圖1所示的圖G的一棵最小生成樹（要求寫出構(gòu)造過程）。（10分）圖1考試科目：數(shù)據(jù)結(jié)構(gòu)共5頁，第5頁4 .已知一個圖如圖2所示，若從頂點a出發(fā)，按深度優(yōu)先搜索法進行遍歷，寫出可能得到的一種頂點序列；按廣度優(yōu)先搜索法進行遍歷,寫出可能得到的一種頂點序列。（4分）圖25 .給定圖3所示帶權(quán)有向圖及其鄰接矩陣，利用 Floyd算法，求每一對頂點之間的最短路 徑及其路徑長度（要求寫出求解過程）。（12分）圖36 .給

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

11、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;struc

12、t BiTNode *lchild, *rchild; / 左右孩子指針 BiTNode, *BiTree;void PreOrderTraverse(BiTree ,Status(*Visit)(TElemType) 采用二叉鏈表存儲結(jié)構(gòu)，Visit是對結(jié)點操作的應(yīng)用函數(shù)InitStack(S);BiTree p=T;while() if (p) Visit(p->data);p=p->lchild;else ;p=; 6 .編寫算法(24)1 .試編寫統(tǒng)計二叉樹中葉子結(jié)點個數(shù)的算法。(10分)2 .設(shè)計一個圖的數(shù)組表示存儲結(jié)構(gòu)，并編寫采用數(shù)組表示法構(gòu)造一個無向網(wǎng)的算法。(14分

13、)大作文贈送以下資料考研英語作文模板（英語一）考研英語大作文一般是看圖寫作，從一幅圖分析含義及意義，所以只需要幾個好的模板，根據(jù)題目套上去就行了。題目反映的意義無非三種：積極，消極和中性。所以我準備了三個不同類型的模板，到時候大家根據(jù)題目自己分析一個寫作方向，再結(jié)合模板，把內(nèi)容填進模板就好了。模板只是保證文章結(jié)構(gòu)不過于混亂 ， 具體的寫作還希望大家多背歷年寫作真題和資料書上的作文，總結(jié)出自己喜歡的句子背下來，背熟之后根據(jù)原文的中文意義用自己的語言再把文章寫出來，這樣才能得到更好的效果。切記：模板只能起到應(yīng)急和保證結(jié)構(gòu)的作用，真正寫好作文拿高分還需要自己不斷地背誦和練習(xí)，祝大家考試順利！模板一：

14、積極（圖畫反映了什么積極現(xiàn)象，我們應(yīng)提倡 ）（開頭：為了避免跟大部分模板有重復(fù)之嫌，我們可以在第一句寫 一句跟作文話題有關(guān)的句子，俗語和諺語皆可，也可以是一句關(guān)于話題的感悟。如果實在寫不出可以不寫）,The picture above symbolically/subtlyillustrate/demonstrate that （描述圖畫） 。Below the drawing, there is a caption which indicates （圖片下的標題）.。或者：【on the drawing, thereare huge Chinese characters reads （圖片上

15、的中文字） .Undoubtedly， we can deduce from the cartoon that the painter is trying to show us that （主旨）.。To begin with , 。Inaddition, .。 （小結(jié)） .。As far as I am concerned ， it is high time that we highlighted the significance ofand cultivated the citizens awareness that.is essential to us。onlyby enforcing

16、these measures into practice， can our society be more harmoniou，s our economy be more prosperous and we， as individuals ， embrace more promising prospect。模板二：消極（圖畫反映了什么消極現(xiàn)象，我們應(yīng)采取行動改變） （開頭：為了避免跟大部分模板有重復(fù)之嫌，我們可以在第一句寫一句跟作文話題有關(guān)的句子，俗語和諺語皆可，也可以是一句關(guān)于話題的感悟。如果實在寫不出可以不寫）,The picture above symbolically/subtlyil

17、lustrate/demonstrate that （描述圖畫） 。Below the drawing , there is a caption which indicates （圖片下的標題）.?；蛘撸骸緊n the drawing, thereare huge Chinese characters reads （圖片上的中文字） .Undoubtedly， we can deduce from the cartoon that due attention has to be paidto the issue of。The causes of this phenomenon are as f

18、ollows To beginwith, oIn addition, .。Last but not least , 。If we let this situation continue as it is , ourwill suffer a greatdestruction/damage/injury。 The problem will be worse and worse 。As far as I am concerned , It is imperative for us to take drastic and effective measuresto reverse the distur

19、bing trend revealed in the above picture。On the one hand, .。 on the other hand, .。Only by enforcing thesemeasures into practice can we curb the current phenomenon surmount this difficulty , and we will have a brilliant future。模板三：中性（圖畫反映的現(xiàn)象是一把雙刃劍，只要好好利用） （開頭：為了避免跟大部分模板有重復(fù)之嫌，我們可以在第一句寫 一句跟作文話題有關(guān)的句子，俗語和諺語皆可，也可以是一句關(guān)于話題的感悟。 如果實在寫不出可以不寫）,The picture above symbolically/subtlyillustr