2015暨南大學(xué)數(shù)據(jù)結(jié)構(gòu)

1、2015年全國碩士研究生統(tǒng)一入學(xué)考試自命題試題（B卷）*學(xué)科、專業(yè)名稱：計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程研究方向：計(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考生注意：所有答案必須寫在答題紙（卷）上，寫在本試題上一律不給分。 一. 單項(xiàng)選擇題(每題2分，共30分) 1線性表采用鏈?zhǔn)酱鎯r(shí),其地址( ) 。 A必須是連續(xù)的 B.部分地址必須是連續(xù)的 C.一定是不連續(xù)的 D.連續(xù)與否均可以2若有一個(gè)棧的輸入序列是1，2，3，n，輸出序列

2、的第一個(gè)元素是n,則第i個(gè)輸出元素是（ ）。 A. n-i B. n-i-1 C. n-i+1 D. 不確定3. 已知單鏈表上一結(jié)點(diǎn)的指針為p，則刪除該結(jié)點(diǎn)后繼的正確操作語句是（ ）。A. s= p->next; p=p->next; free(s); Bp=p->next; free(p);C. s= p->next; p->next=s->next; free(s); Dp=p->next; free(p->next);4. 若使用鄰接矩陣表示某有向圖，則矩陣中非零元素的個(gè)數(shù)等于（ ）。A. 圖中頂點(diǎn)的數(shù)目 B. 圖中邊的數(shù)目 C. 圖中邊的

3、數(shù)目的兩倍 D. 無法確定5. 下列哪種排序需要的附加存儲開銷最大( )。 A快速排序 B.堆排序 C.歸并排序 D.插入排序6. 下面哪一方法可以判斷出一個(gè)有向圖是否有環(huán)（即回路）（ ）。A拓?fù)渑判?B. 求最短路徑 C. 求最小生成樹 D. 廣度優(yōu)先遍歷7. 具有n個(gè)頂點(diǎn)的無向圖至少應(yīng)有（ ）條邊才能確保是一個(gè)連通圖.An-1 Bn Cn+1 D2n8. 對線性表進(jìn)行折半查找時(shí),要求線性表必須 ( ) 。 A.以順序方式存儲 B. 以順序方式存儲,且結(jié)點(diǎn)按關(guān)鍵字有序排序C. 以鏈接方式存儲 D.以鏈接方式存儲,且結(jié)點(diǎn)按關(guān)鍵字有序排序9若使用二叉鏈表作為樹的存儲結(jié)構(gòu)，在有n個(gè)結(jié)點(diǎn)的二叉鏈表中

4、非空的鏈域的個(gè)數(shù)為( ) 。 A. n-1 B. 2n-1 C. n+1 D. 2n+110在內(nèi)部排序中,排序時(shí)不穩(wěn)定的有( ) 。 A. 插入排序 B. 冒泡排序 C. 快速排序 D.歸并排序11. 一個(gè)具有500 個(gè)結(jié)點(diǎn)的完全二叉樹具有一個(gè)孩子的結(jié)點(diǎn)個(gè)數(shù)最多為（ ）。A1 B250 C0 D249考試科目： 數(shù)據(jù)結(jié)構(gòu) 共5 頁，第 1 頁12. 從未排序序列中取出一個(gè)元素，并將其依次插入已排序序列的方法，稱為 （ ）。. 希爾排序 . 歸并排序 . 插入排序 . 選擇排序13. 如果希望對二叉排序樹遍歷的結(jié)果是升序的，應(yīng)采用（ ）遍歷方法。A先序 B中序 C后序 D層次14. 隊(duì)列操作的原

5、則是（ ） A先進(jìn)先出 B后進(jìn)先出 C只能進(jìn)行插入 D只能進(jìn)行刪除15. 在用鄰接表表示有向圖的情況下,假設(shè)n為圖的頂點(diǎn)數(shù)目, e為圖的邊數(shù)目,建立圖的算法的時(shí)間復(fù)雜度為( )。 AO(n+e) BO(n2) CO(n×e) DO(n3)二填空題(每空2分，共20分)1循環(huán)鏈表的主要優(yōu)點(diǎn)是 。2根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性, 基本邏輯結(jié)構(gòu)分為 、 線性結(jié)構(gòu) 、 樹形結(jié)構(gòu)和 四種。3對一棵完全二叉樹中按照從上到下、從左到右的順序從1開始順序編號，則編號為11雙親結(jié)點(diǎn)的編號為 ，編號為10的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)（若存在）的編號為 。4下面程序段的時(shí)間復(fù)雜度是 。S=0;for( i=0;i

6、<N; i+) for(j=0; j<2N+1; j+) S+;5深度為h 的滿二叉樹共有 個(gè)結(jié)點(diǎn)。6一棵m階非空B-樹，每個(gè)結(jié)點(diǎn)最多有 棵子樹，除根之外的所有非終端結(jié)點(diǎn)至少有 棵子樹。 7在單鏈表中，若要在指針p所指結(jié)點(diǎn)后插入指針s所指結(jié)點(diǎn)，則需要執(zhí)行下列兩條語句： 。三判斷題（每題1分，共10分，正確的選t，錯(cuò)誤的選f）1數(shù)據(jù)元素是數(shù)據(jù)的基本單位。（ ）2線性表中的每一個(gè)元素都有一個(gè)前驅(qū)和后繼元素。（ ）3當(dāng)向二叉排序樹中插入一個(gè)結(jié)點(diǎn)，則該結(jié)點(diǎn)一定成為葉子結(jié)點(diǎn)。（ ）4帶權(quán)無向圖的最小生成樹是唯一的。( )5設(shè)有序的關(guān)鍵字序列是（2，5，8，9，12，14，16，18，20，2

7、2，25），當(dāng)用折半查找方法查找關(guān)鍵字22時(shí)，需經(jīng)3次比較運(yùn)算。（ ）6一棵m階B+樹中每個(gè)結(jié)點(diǎn)最多有m個(gè)關(guān)鍵碼，最少有2個(gè)關(guān)鍵碼。( )7根據(jù)拓?fù)渑判蚪Y(jié)果可以判斷一個(gè)有向圖中是否存在環(huán)路。 （ ） 8圖的深度優(yōu)先搜索中可以采用棧來暫存剛訪問過的頂點(diǎn)。 （ ）9已知一顆樹的先序序列和后序序列，一定能構(gòu)造出該樹。 （ ）考試科目： 數(shù)據(jù)結(jié)構(gòu) 共5 頁，第 2 頁10存儲圖的鄰接表中，鄰接表的大小不但與圖的頂點(diǎn)個(gè)數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。（ ）四. 簡答題（45分）1. 簡述下列算法的功能。（6分）typedef struct BiTNode TElemType data; struct Bi

8、TNode *lchild, *rchild; BiTNode, *BiTree;void Process(BiTree T) IniStack(S); P=T; while (P|!StackEmpty(S) if (P) push(&S, P); P=P->lchild; else pop(&S, P); printf(P->data);P=P->rchild; 2. 假設(shè)表中關(guān)鍵字序列為（7,6,9,10，14,8），將關(guān)鍵字依次插入一棵初始為空的二叉排序樹。畫出二叉排序樹的生成過程。（10 分）3. 關(guān)鍵字序列 T=(63，55，48，37，20，90

9、，84，32），對其從小到大排序，以第一個(gè)關(guān)鍵字為樞軸（支點(diǎn)），寫出快速排序具體實(shí)現(xiàn)過程（10分）。 4. 一個(gè)有六個(gè)頂點(diǎn)v1,v2,v3,v4,v5,v6的網(wǎng)的鄰接矩陣如圖1所示，解答下列問題：（1） 畫出該網(wǎng)（2分） （2） 能否寫出一種拓?fù)渑判蛐蛄?，若可以，寫出一種拓?fù)渑判蛐蛄校?分）（3） 求出從頂點(diǎn)v1到其他各頂點(diǎn)之間的最短路徑，并寫出計(jì)算過程。（8） 圖 1.考試科目： 數(shù)據(jù)結(jié)構(gòu) 共5 頁，第 3 頁5. 設(shè)用于通信的電文由字符集a, b,c,d,e,f,g中的字母構(gòu)成，它們在電文中出現(xiàn)的頻度分別為0.34,0.12,0.10,0.08,0.13,0.20,0.03,如何為這7個(gè)字

10、母設(shè)計(jì)二進(jìn)制前綴編碼使得電文總長最短，寫出編碼過程。（7分）五算法填空，（每空2分,共20分）1. 以下算法功能是:插入元素e到隊(duì)列Q中, 完成算法的空格部分。typedef struct Qnode QElemType data; struct Qnode *next; Qnode, *QueuePtr; typedef struct QueuePtr front; /隊(duì)頭 QueuePtr rear; /隊(duì)尾 LinkQueue; status EnQueue(LinkQueue &Q, QElemType e) P= (QueuePtr)malloc(sizeof(Qnode);

11、 if ( ) exit(OVERFLOW); P->data= P->next= =P; Q.rear= ; Return OK; 2. 以下程序?yàn)閳D的深度優(yōu)先遍歷算法，完成算法的空格部分。 Boolean visitedMax; /訪問標(biāo)志數(shù)組 Status (*VisitFunc)(int v); /訪問函數(shù)變量 void DFStraverse( Graph G , Status(*visit)(int v) vistFunc=visit; for (v=0;v<G.vexnum;+v) visitedv=False; for (v=0; ； +v) if ( ) DFS(G, v); void DFS(Graph G, int v) visitedv= ; VisitFunc(V); for (w=FirstAdjvex(G,v); ; w= NextAdjVex(G,v,w) ) if (!visitedw)