2017年暨南大學考研真題830數(shù)據(jù)結構

《2017年暨南大學考研真題830數(shù)據(jù)結構》由會員分享，可在線閱讀，更多相關《2017年暨南大學考研真題830數(shù)據(jù)結構（6頁珍藏版）》請在裝配圖網(wǎng)上搜索。

2017年全國碩士研究生統(tǒng)一入學考試自命題試題（B卷） ******************************************************************************************** 學科、專業(yè)名稱：計算機科學與技術、軟件工程 研究方向：計算機系統(tǒng)結構081201，計算機軟件與理論081202，計算機應用技術081203，軟件工程083500，計算機技術(專業(yè)學位) 085211，軟件工程(專業(yè)學位) 085212 考試科目名稱及代碼：數(shù)據(jù)結構830 考生注意：所有答案必須寫在答題紙（卷）上，寫在本試題上一律不給分。 一、 單項選擇題(每題2分，共30分) 1. 一個隊列的入列序列是1,2,3,4, 則隊列的輸出序列是（ ）。 A. 4,3,2,1 B. 1,2,3,4 C. 1,4,3,2 D. 3,2,4,1 2. 循環(huán)隊列用數(shù)組A[0..m-1]存放其元素值，已知其頭尾指針分別是front和rear, 則當前隊列中的元素個數(shù)是( )。 A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front 3. 平衡二叉樹的平均查找長度是( )。 A. O(n2） B. O(nlog2n） C. O(n） D. O(log2n） 4. 設F是由T1、T2和T3三棵樹組成的森林，與F對應的二叉樹為B，T1、T2和T3的結點數(shù)分別為N1、N2和N3，則二叉樹B的根結點的左子樹的結點數(shù)為（ ）。 A. N1-1 B. N2-1 C. N2+N3 D. N1+N3 5. 計算機內(nèi)部數(shù)據(jù)處理的基本單元是（ ）。 A. 數(shù)據(jù) B. 數(shù)據(jù)元素 C. 數(shù)據(jù)項 D. 數(shù)據(jù)庫 6. 設按照從上到下、從左到右的順序從1開始對完全二叉樹的結點進行順序編號，則編號為i結點的左孩子結點的編號為（ ）。 A. 2i+1 B. 2i C. i/2 D. 2i-1 7. 設用鄰接矩陣A表示有向圖G的存儲結構，則有向圖G中頂點i的入度為（ ）。 A. 第i行非0元素的個數(shù)之和 B. 第i列非0元素的個數(shù)之和 C. 第i行0元素的個數(shù)之和 D. 第i列0元素的個數(shù)之和 8. 設一組初始記錄關鍵字序列為(16, 25,12, 30,47,11, 23,36, 9,18,31)，則以增量d=5的一趟希爾排序結束后的結果為（ ）。 A. 11, 23,12, 9, 18,16, 25,36,30, 47, 31 B. 11, 23,12, 9, 16, 18, 25,36, 47, 30, 31 C. 16, 23,12, 9, 11,18, 25,36,30, 47, 31 C. 9, 11,12, 16, 18, 23, 25,30, 36, 47, 31 9. 設某有向圖的鄰接表中有n個表頭結點和m個表結點，則該圖中有（ ）條有向邊。 A. n B. n-1 C. m D. m-1 10. 設哈夫曼樹中的葉子結點總數(shù)為m，若用二叉鏈表作為存儲結構，則該哈夫曼樹中總共有（ ）個空指針域。 A. 2m-1 B. 2m C. 2m+1 D. 4m 11. 對于線性表（7，34，55，25，64，46，20，10）進行散列存儲時，若選用H(K)=K %9作為散列函數(shù)，則散列地址為1的元素有（ ）個。 A． 1 B． 2 C． 3 D． 4 考試科目： 數(shù)據(jù)結構 共 5頁，第 1 頁 12. 下面程序的時間復雜為（ ）。 for（i=1，s=0； i<=n； i++） { t=1； for(j=1；j<=i；j++) { t=t*j；s=s+t；} } A． O(n) B. O(n2) C. O(n3) D. O(n4) 13. 對于一個具有n個頂點的無向連通圖，它包含的連通分量的個數(shù)為( )。 A． 0 B．1 C． n D． n+1 14. 設無向圖G中邊的集合E={(a,b)，(a,e)，(a,c)，(b,e)，(e,d)，(d,f)，(f,c)}，則從頂點a出發(fā)進行深度優(yōu)先遍歷可以得到的一種頂點序列為（ ）。 A. aebcfd B. acfebd C. aedfcb D. aedfbc 15.設指針變量p指向雙向鏈表中結點A，指針變量s指向被插入的結點X，則在結點A的后面插入結點X的操作序列為（ ）。 A. p->next=s；s->prior=p； p->next->prior=s； s->prior=p->nest； B. s->prior=p; s->next = p->next; p->next=s; s->next->prior=s; C. p->prior=s；p->nest->prior=s；s->prior=p；s->next=p->prior； D. s->prior=p；s->next=p->next；p->next=s；p->next->prior=s； 二．填空題(每空2分，共20分) 1. 采用堆排序、快速排序、冒泡排序，對初態(tài)為有序的表，最省時間的是 。 2. 設一組初始記錄關鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結束后的結果為 。 3. 當待排記錄序列按關鍵字順序有序時，直接插入排序和冒泡排序能達到 的時間復雜度，快速排序的時間性能退化為 (以第一個關鍵字為樞軸)。 4. 判定順序棧是否為空的條件是 ，判定順序棧是否為滿的條件是 。 5. 當向B-樹中插入關鍵字時,可能引起結點的 ,最終可能導致整個B-樹的高度增加 。 6. 設散列表的長度為8，散列函數(shù)H(k)=k%7，用線性探測法解決沖突，則根據(jù)一組初始關鍵字序列(8，15，16，22，30，32)構造出的散列表的平均查找長度是 。 7. 設在一棵度數(shù)為3的樹中，度數(shù)為3的結點數(shù)有2個，度數(shù)為2的結點數(shù)有1個，度數(shù)為1的結點數(shù)有2個，那么度數(shù)為0的結點數(shù)有 個。 三．判斷題（每題1分，共10分，正確的選t，錯誤的選f） 1. 順序表查找指的是在順序存儲結構上進行查找。（ ） 2. 循環(huán)隊列中不存在隊列滿的問題。（ ） 3. n階對稱矩陣可壓縮存儲到n/2個單元的空間中。( ) 4. 一個圖的鄰接表表示法是唯一的。( ) 5. 希爾排序是穩(wěn)定的。( ) 6. 由樹轉化成二叉樹，該二叉樹的右子樹不一定為空。（ ） 7. 根據(jù)拓撲排序結果可以判斷一個有向圖中是否存在環(huán)路。（ ） 8. 稀疏矩陣的壓縮存儲可以用一個三元組表來表示稀疏矩陣中的非0元素。（ ） 9. 入棧操作和入隊列操作在鏈式存儲結構上實現(xiàn)時不需要考慮棧溢出的情況。( ) 10.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（ ） 考試科目： 數(shù)據(jù)結構 共5 頁，第 2 頁 四. 簡答題（45分） 1. 設有1000個元素組成的無序序列，希望用最快的速度挑選出其中前10個（僅挑前10個）最大元素，以下幾種排序方法中哪一種最合適？分析各排序算法, 給出原因？（7分） （1）簡單選擇排序； （2）冒泡排序； （3）堆排序； （4）歸并排序 2. 設二叉排序樹中關鍵字由1至1000的整數(shù)組成，現(xiàn)要查找關鍵字為363的結點，下面的關鍵字序列哪個不可能是在二叉樹中查到的序列？說明原因。（5分） （1）51, 250, 501, 390, 320, 340, 382, 363 （2）24，877， 125, 342, 501， 623， 421, 363 3. 針對二叉樹，回答以下問題： （1）具有n個結點的二叉樹的最小深度是多少？最大深度是多少？（4分） （2）具有n個結點的完全二叉樹中有多少個葉子結點？有多少個度為2的結點？（4分） （3）具有n0個葉子結點的完全二叉樹中共有多少個結點？（4分） 4. 閱讀如下程序，寫出此程序的輸出結果（其中棧的元素類型為char）。(5分) void main ( ) { Stack S; char x, y; InitStack(S); x=y; y=s ; Push(S,x); Push(S,y); Pop(S,x); Push(S,k); Push(S,x); while(!StackEmpty(S)) {Pop(S,y); printf(y);} } 5. 給定圖1所示帶權有向圖，利用Floyd算法，求每一對頂點之間的最短路徑及其路徑長度（要求寫出求解過程）。（10分） 圖1 6. 一個帶權無向圖的最小生成樹是否一定唯一？在什么情況下構造出的最小生成樹可能不唯一？（6分） 考試科目： 數(shù)據(jù)結構 共5頁，第 3 頁 五．算法填空（共2小題，每空2分，共20分） 1. 下面的算法是在帶頭結點的單鏈表L中第 i 個位置之前插入元素e。請在__________處填上適當內(nèi)容，使其成為一個完整算法。 typedef struct LNode{ ElemType data; struct LNode *next; }LNode, * LinkList; Status ListInsert_L (LinkList & L, int i, ElemType e) {　 p=L; j= (1) ; while (p && (j< i-1)) { p=p->next; (2) } if (!p ) return ERROR; s=(LinkList)malloc(sizeof (LNode)); s->date = e; (3) ; (4) return Ok ; } 2. 下面是一個有向圖G采用鄰接表存儲結構的拓撲排序算法。請在________處填上適當內(nèi)容，使其成為一個完整算法。 typedef struct VNode { VertexType data; ArcNode *firstarc; } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct ArcNode { int adjvex; struct ArcNode *nextarc; InfoType *info; } ArcNode; typedef struct { AdjList vertices; int vexnum, arcnum; int kind; } ALGraph; 考試科目： 數(shù)據(jù)結構 共5 頁，第 4 頁 Status TopologicalSort(ALGraph G) { // 有向圖G采用鄰接表存儲結構。若G無回路,則輸出G的頂點的一個拓撲序列并返回 OK，否則返回ERROR。 int indegree[vexnum]; FindInDegree(G, indegree); //對各頂點求入度indegree [0..vexnum-1] InitStack(S); for(i=0; inextarc) { k=p->adjvex; if(!(- -indegree[k])) （9） } } if( (10) ) return ERROR; else return OK; }//TopologicalSort 六．編寫算法（25分） 1. 編寫一個算法求二叉樹中葉子結點的個數(shù)（10分）。 2. 已知n個頂點的帶權圖用鄰接矩陣表示，試編寫算法實現(xiàn)用kruskal算法構造最小生成樹。（15分） 考試科目： 數(shù)據(jù)結構 共5 頁，第 5 頁