2017年全國(guó)碩士研究生統(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ě)在答題紙（卷）上，寫(xiě)在本試題上一律不給分。 一、 單項(xiàng)選擇題(每題2分，共30分) 1. 一個(gè)隊(duì)列的入列序列是1,2,3,4, 則隊(duì)列的輸出序列是（ ）。A. 4,3,2,1 B. 1,2,3,4 C. 1,4,3,2 D. 3,2,4,12. 循環(huán)隊(duì)列用數(shù)組A0.m-1存放其元素值，已知其頭尾指針?lè)謩e是front和rear, 則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是( )。A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front3. 平衡二叉樹(shù)的平均查找長(zhǎng)度是( )。 A. O(n2） B. O(nlog2n） C. O(n） D. O(log2n）4. 設(shè)F是由T1、T2和T3三棵樹(shù)組成的森林，與F對(duì)應(yīng)的二叉樹(shù)為B，T1、T2和T3的結(jié)點(diǎn)數(shù)分別為N1、N2和N3，則二叉樹(shù)B的根結(jié)點(diǎn)的左子樹(shù)的結(jié)點(diǎn)數(shù)為（ ）。 A. N1-1 B. N2-1 C. N2+N3 D. N1+N35. 計(jì)算機(jī)內(nèi)部數(shù)據(jù)處理的基本單元是（ ）。 A. 數(shù)據(jù) B. 數(shù)據(jù)元素 C. 數(shù)據(jù)項(xiàng) D. 數(shù)據(jù)庫(kù)6. 設(shè)按照從上到下、從左到右的順序從1開(kāi)始對(duì)完全二叉樹(shù)的結(jié)點(diǎn)進(jìn)行順序編號(hào)，則編號(hào)為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號(hào)為（ ）。 A. 2i+1 B. 2i C. i/2 D. 2i-17. 設(shè)用鄰接矩陣A表示有向圖G的存儲(chǔ)結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為（ ）。 A. 第i行非0元素的個(gè)數(shù)之和B. 第i列非0元素的個(gè)數(shù)之和 C. 第i行0元素的個(gè)數(shù)之和D. 第i列0元素的個(gè)數(shù)之和8. 設(shè)一組初始記錄關(guān)鍵字序列為(16, 25,12, 30,47,11, 23,36, 9,18,31)，則以增量d=5的一趟希爾排序結(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個(gè)表頭結(jié)點(diǎn)和m個(gè)表結(jié)點(diǎn)，則該圖中有（ ）條有向邊。 A. nB. n-1C. mD. m-110. 設(shè)哈夫曼樹(shù)中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹(shù)中總共有（ ）個(gè)空指針域。 A. 2m-1B. 2mC. 2m+1D. 4m11. 對(duì)于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲(chǔ)時(shí)，若選用H(K)=K %9作為散列函數(shù)，則散列地址為1的元素有（ ）個(gè)。 A 1 B 2 C 3 D 4考試科目： 數(shù)據(jù)結(jié)構(gòu) 共 5頁(yè)，第 1 頁(yè)12. 下面程序的時(shí)間復(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. 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向連通圖，它包含的連通分量的個(gè)數(shù)為( )。 A 0 B1 C n D n+114. 設(shè)無(wú)向圖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; 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. 采用堆排序、快速排序、冒泡排序，對(duì)初態(tài)為有序的表，最省時(shí)間的是 。2. 設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結(jié)束后的結(jié)果為 。3. 當(dāng)待排記錄序列按關(guān)鍵字順序有序時(shí)，直接插入排序和冒泡排序能達(dá)到 的時(shí)間復(fù)雜度，快速排序的時(shí)間性能退化為 (以第一個(gè)關(guān)鍵字為樞軸)。4. 判定順序棧是否為空的條件是 ，判定順序棧是否為滿的條件是 。5. 當(dāng)向B-樹(shù)中插入關(guān)鍵字時(shí),可能引起結(jié)點(diǎn)的 ,最終可能導(dǎo)致整個(gè)B-樹(shù)的高度增加 。6. 設(shè)散列表的長(zhǎng)度為8，散列函數(shù)H(k)=k%7，用線性探測(cè)法解決沖突，則根據(jù)一組初始關(guān)鍵字序列(8，15，16，22，30，32)構(gòu)造出的散列表的平均查找長(zhǎng)度是 。7. 設(shè)在一棵度數(shù)為3的樹(shù)中，度數(shù)為3的結(jié)點(diǎn)數(shù)有2個(gè)，度數(shù)為2的結(jié)點(diǎn)數(shù)有1個(gè)，度數(shù)為1的結(jié)點(diǎn)數(shù)有2個(gè)，那么度數(shù)為0的結(jié)點(diǎn)數(shù)有 個(gè)。三判斷題（每題1分，共10分，正確的選t，錯(cuò)誤的選f）1. 順序表查找指的是在順序存儲(chǔ)結(jié)構(gòu)上進(jìn)行查找。（ ）2. 循環(huán)隊(duì)列中不存在隊(duì)列滿的問(wèn)題。（ ）3. n階對(duì)稱矩陣可壓縮存儲(chǔ)到n/2個(gè)單元的空間中。( ) 4. 一個(gè)圖的鄰接表表示法是唯一的。( )5. 希爾排序是穩(wěn)定的。( )6. 由樹(shù)轉(zhuǎn)化成二叉樹(shù)，該二叉樹(shù)的右子樹(shù)不一定為空。（ ）7. 根據(jù)拓?fù)渑判蚪Y(jié)果可以判斷一個(gè)有向圖中是否存在環(huán)路。（ ）8. 稀疏矩陣的壓縮存儲(chǔ)可以用一個(gè)三元組表來(lái)表示稀疏矩陣中的非0元素。（ ）9. 入棧操作和入隊(duì)列操作在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)時(shí)不需要考慮棧溢出的情況。( )10.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（ ）考試科目： 數(shù)據(jù)結(jié)構(gòu) 共5 頁(yè)，第 2 頁(yè)四. 簡(jiǎn)答題（45分）1. 設(shè)有1000個(gè)元素組成的無(wú)序序列，希望用最快的速度挑選出其中前10個(gè)（僅挑前10個(gè)）最大元素，以下幾種排序方法中哪一種最合適？分析各排序算法, 給出原因？（7分） （1）簡(jiǎn)單選擇排序； （2）冒泡排序； （3）堆排序； （4）歸并排序2. 設(shè)二叉排序樹(shù)中關(guān)鍵字由1至1000的整數(shù)組成，現(xiàn)要查找關(guān)鍵字為363的結(jié)點(diǎn)，下面的關(guān)鍵字序列哪個(gè)不可能是在二叉樹(shù)中查到的序列？說(shuō)明原因。（5分） （1）51, 250, 501, 390, 320, 340, 382, 363 （2）24，877， 125, 342, 501， 623， 421, 3633. 針對(duì)二叉樹(shù)，回答以下問(wèn)題： （1）具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)的最小深度是多少？最大深度是多少？（4分） （2）具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中有多少個(gè)葉子結(jié)點(diǎn)？有多少個(gè)度為2的結(jié)點(diǎn)？（4分） （3）具有n0個(gè)葉子結(jié)點(diǎn)的完全二叉樹(shù)中共有多少個(gè)結(jié)點(diǎn)？（4分）4. 閱讀如下程序，寫(xiě)出此程序的輸出結(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(S,x); while(!StackEmpty(S) Pop(S,y); printf(y); 5. 給定圖1所示帶權(quán)有向圖，利用Floyd算法，求每一對(duì)頂點(diǎn)之間的最短路徑及其路徑長(zhǎng)度（要求寫(xiě)出求解過(guò)程）。（10分） 圖16. 一個(gè)帶權(quán)無(wú)向圖的最小生成樹(shù)是否一定唯一？在什么情況下構(gòu)造出的最小生成樹(shù)可能不唯一？（6分）考試科目： 數(shù)據(jù)結(jié)構(gòu) 共5頁(yè)，第 3 頁(yè)五算法填空（共2小題，每空2分，共20分）1. 下面的算法是在帶頭結(jié)點(diǎn)的單鏈表L中第 i 個(gè)位置之前插入元素e。請(qǐng)?jiān)赺處填上適當(dāng)內(nèi)容，使其成為一個(gè)完整算法。 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è)有向圖G采用鄰接表存儲(chǔ)結(jié)構(gòu)的拓?fù)渑判蛩惴?。?qǐng)?jiān)赺處填上適當(dāng)內(nèi)容，使其成為一個(gè)完整算法。 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 頁(yè)，第 4 頁(yè) Status TopologicalSort(ALGraph G) / 有向圖G采用鄰接表存儲(chǔ)結(jié)構(gòu)。若G無(wú)回路,則輸出G的頂點(diǎn)的一個(gè)拓?fù)湫蛄胁⒎祷?OK，否則返回ERROR。 int indegreevexnum; FindInDegree(G, indegree); /對(duì)各頂點(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) ; p=p->nextarc) k=p->adjvex; if(!(- -indegreek) （9） if( (10) ) return ERROR; else return OK;/TopologicalSort六編寫(xiě)算法（25分）1. 編寫(xiě)一個(gè)算法求二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)（10分）。2. 已知n個(gè)頂點(diǎn)的帶權(quán)圖用鄰接矩陣表示，試編寫(xiě)算法實(shí)現(xiàn)用kruskal算法構(gòu)造最小生成樹(shù)。（15分）考試科目： 數(shù)據(jù)結(jié)構(gòu) 共5 頁(yè)，第 5 頁(yè)