2017年全國碩士研究生統(tǒng)一入學(xué)考試自命題試題B卷

1、2017年全國碩士研究生統(tǒng)一入學(xué)考試自命題試題（B卷）*學(xué)科、專業(yè)名稱：計算機(jī)科學(xué)與技術(shù)、軟件工程研究方向：計算機(jī)系統(tǒng)結(jié)構(gòu)081201，計算機(jī)軟件與理論081202，計算機(jī)應(yīng)用技術(shù)081203，軟件工程083500，計算機(jī)技術(shù)(專業(yè)學(xué)位) 085211，軟件工程(專業(yè)學(xué)位) 085212考試科目名稱及代碼：數(shù)據(jù)結(jié)構(gòu)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,12. 循環(huán)隊列

2、用數(shù)組A0.m-1存放其元素值，已知其頭尾指針分別是front和rear, 則當(dāng)前隊列中的元素個數(shù)是( )。A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front3. 平衡二叉樹的平均查找長度是( )。 A. O(n2） B. O(nlog2n） C. O(n） D. O(log2n）4. 設(shè)F是由T1、T2和T3三棵樹組成的森林，與F對應(yīng)的二叉樹為B，T1、T2和T3的結(jié)點(diǎn)數(shù)分別為N1、N2和N3，則二叉樹B的根結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)數(shù)為（ ）。 A. N1-1 B. N2-1 C. N2+N3 D. N1+N35. 計

3、算機(jī)內(nèi)部數(shù)據(jù)處理的基本單元是（ ）。 A. 數(shù)據(jù) B. 數(shù)據(jù)元素 C. 數(shù)據(jù)項 D. 數(shù)據(jù)庫6. 設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹的結(jié)點(diǎn)進(jìn)行順序編號，則編號為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號為（ ）。 A. 2i+1 B. 2i C. i/2 D. 2i-17. 設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為（ ）。 A. 第i行非0元素的個數(shù)之和B. 第i列非0元素的個數(shù)之和 C. 第i行0元素的個數(shù)之和D. 第i列0元素的個數(shù)之和8. 設(shè)一組初始記錄關(guān)鍵字序列為(16, 25,12, 30,47,11, 23,36, 9,18,31)，則以增量d=5的一趟希爾排

4、序結(jié)束后的結(jié)果為（ ）。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. 設(shè)某有向圖的鄰接表中有n個表頭結(jié)點(diǎn)和m個表結(jié)點(diǎn)，則該圖中有（ ）條有向邊。 A. nB. n-1C. mD. m-110. 設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有（ ）個空指針域。 A. 2m-

5、1B. 2mC. 2m+1D. 4m11. 對于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲時，若選用H(K)=K %9作為散列函數(shù)，則散列地址為1的元素有（ ）個。 A 1 B 2 C 3 D 4考試科目： 數(shù)據(jù)結(jié)構(gòu) 共 5頁，第 1 頁12. 下面程序的時間復(fù)雜為（ ）。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個頂點(diǎn)的無向連通圖，它包含的連通分量的個數(shù)為( )。 A 0 B1 C n D n+114.

6、 設(shè)無向圖G中邊的集合E=(a,b)，(a,e)，(a,c)，(b,e)，(e,d)，(d,f)，(f,c)，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為（ ）。A. aebcfdB. acfebdC. aedfcbD. aedfbc15.設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為（ ）。A. p->next=s；s->prior=p； p->next->prior=s； s->prior=p->nest；B. s->prior=p; s->next = p->next;

7、 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. 設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結(jié)束后的結(jié)果

8、為 。3. 當(dāng)待排記錄序列按關(guān)鍵字順序有序時，直接插入排序和冒泡排序能達(dá)到 的時間復(fù)雜度，快速排序的時間性能退化為 (以第一個關(guān)鍵字為樞軸)。4. 判定順序棧是否為空的條件是 ，判定順序棧是否為滿的條件是 。5. 當(dāng)向B-樹中插入關(guān)鍵字時,可能引起結(jié)點(diǎn)的 ,最終可能導(dǎo)致整個B-樹的高度增加 。6. 設(shè)散列表的長度為8，散列函數(shù)H(k)=k%7，用線性探測法解決沖突，則根據(jù)一組初始關(guān)鍵字序列(8，15，16，22，30，32)構(gòu)造出的散列表的平均查找長度是 。7. 設(shè)在一棵度數(shù)為3的樹中，度數(shù)為3的結(jié)點(diǎn)數(shù)有2個，度數(shù)為2的結(jié)點(diǎn)數(shù)有1個，度數(shù)為1的結(jié)點(diǎn)數(shù)有2個，那么度數(shù)為0的結(jié)點(diǎn)數(shù)有 個。三判斷題

9、（每題1分，共10分，正確的選t，錯誤的選f）1. 順序表查找指的是在順序存儲結(jié)構(gòu)上進(jìn)行查找。（ ）2. 循環(huán)隊列中不存在隊列滿的問題。（ ）3. n階對稱矩陣可壓縮存儲到n/2個單元的空間中。( ) 4. 一個圖的鄰接表表示法是唯一的。( )5. 希爾排序是穩(wěn)定的。( )6. 由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。（ ）7. 根據(jù)拓?fù)渑判蚪Y(jié)果可以判斷一個有向圖中是否存在環(huán)路。（ ）8. 稀疏矩陣的壓縮存儲可以用一個三元組表來表示稀疏矩陣中的非0元素。（ ）9. 入棧操作和入隊列操作在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實(shí)現(xiàn)時不需要考慮棧溢出的情況。( )10.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（ ）考試科目： 數(shù)

10、據(jù)結(jié)構(gòu) 共5 頁，第 2 頁四. 簡答題（45分）1. 設(shè)有1000個元素組成的無序序列，希望用最快的速度挑選出其中前10個（僅挑前10個）最大元素，以下幾種排序方法中哪一種最合適？分析各排序算法, 給出原因？（7分） （1）簡單選擇排序； （2）冒泡排序； （3）堆排序； （4）歸并排序2. 設(shè)二叉排序樹中關(guān)鍵字由1至1000的整數(shù)組成，現(xiàn)要查找關(guān)鍵字為363的結(jié)點(diǎn)，下面的關(guān)鍵字序列哪個不可能是在二叉樹中查到的序列？說明原因。（5分） （1）51, 250, 501, 390, 320, 340, 382, 363 （2）24，877， 125, 342, 501， 623， 421, 36

11、33. 針對二叉樹，回答以下問題： （1）具有n個結(jié)點(diǎn)的二叉樹的最小深度是多少？最大深度是多少？（4分） （2）具有n個結(jié)點(diǎn)的完全二叉樹中有多少個葉子結(jié)點(diǎn)？有多少個度為2的結(jié)點(diǎn)？（4分） （3）具有n0個葉子結(jié)點(diǎn)的完全二叉樹中共有多少個結(jié)點(diǎn)？（4分）4. 閱讀如下程序，寫出此程序的輸出結(jié)果（其中棧的元素類型為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

12、(S,x); while(!StackEmpty(S) Pop(S,y); printf(y); 5. 給定圖1所示帶權(quán)有向圖，利用Floyd算法，求每一對頂點(diǎn)之間的最短路徑及其路徑長度（要求寫出求解過程）。（10分） 圖16. 一個帶權(quán)無向圖的最小生成樹是否一定唯一？在什么情況下構(gòu)造出的最小生成樹可能不唯一？（6分）考試科目： 數(shù)據(jù)結(jié)構(gòu) 共5頁，第 3 頁五算法填空（共2小題，每空2分，共20分）1. 下面的算法是在帶頭結(jié)點(diǎn)的單鏈表L中第 i 個位置之前插入元素e。請在_處填上適當(dāng)內(nèi)容，使其成為一個完整算法。 typedef struct LNode ElemType data; struc

13、t 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采用鄰接表存儲結(jié)構(gòu)的拓?fù)渑判蛩惴?。請在_處填上適當(dāng)內(nèi)容，使其成為一個完整

14、算法。 typedef struct VNode VertexType data; ArcNode *firstarc; VNode, AdjListMAX_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ù)結(jié)構(gòu) 共5 頁，第 4 頁 Status TopologicalSort(ALGraph G) / 有向圖G采用鄰接表存儲結(jié)構(gòu)。若G無回路,則輸出G的頂點(diǎn)的一個拓?fù)湫蛄胁⒎祷?OK，否則返回ERROR。 int indegreevexnum; FindInDegree(G, indegree); /對各頂點(diǎn)求入度indegree 0.vexnum-1 InitStack(S); for(i=0; i<G.vexnum; +i) if( (5) ) Push(S, i); count=0; while( （6） ) (7) ; printf(i, G.verticesi.data); +count; for(p=G.verticesi.firstarc; (8) ;