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

2017年全國碩士研究生統(tǒng)一入學考試自命題試題（ B卷）********************************************************************************************學科、專業(yè)名稱：計算機科學與技術、軟件工程研究方向：計算機系統(tǒng)結構 081201，計算機軟件與理論081202，計算機應用技術081203，軟件工程083500，計算機技術（專業(yè)學位）085211，軟件工程（專業(yè)學位）085212考試科目名稱及代碼：數(shù)據(jù)結構 830考生注意：所有答案必須寫在答題紙（卷）上，寫在本試題上一律不給分。

單項選擇題（每題2分，共30分）一個隊列的入列序列是 1,2,3,4,則隊列的輸出序列是（ ）。A.4,3,2,1 B.1,2,3,4 C.1,4,3,2A.4,3,2,1 B.1,2,3,4 C.1,4,3,2循環(huán)隊列用數(shù)組A[0..m-1]存放其元素值，已知其頭尾指針分別是的元素個數(shù)是（A. （rear-front+m）%m B. rear-front+1平衡二叉樹的平均查找長度是 （ ）°A. O（n2） B.0（nlog2n）設F是由T1、T2和T3三棵樹組成的森林，與數(shù)分別為N1、N2和N3，則二叉樹BA. N1-1 B.N2-1計算機內(nèi)部數(shù)據(jù)處理的基本單元是（A.數(shù)據(jù) B.數(shù)據(jù)元素5.frontD.3,2,4,1和rear,則當前隊列中C.rear-front-1D.rear-frontC.O(n)D.O(log2n)F對應的二叉樹為B，T1、T2和T3的結點子樹的結點數(shù)為(）。C.N2+N3D.N1+N3C.數(shù)據(jù)項D.數(shù)據(jù)庫）。設按照從上到下、從左到右的順序從 1開始對完全二叉樹的結點進行順序編號，則編號為結點的左孩子結點的編號為（ ）。A.2i+1B.2i C.i/2 D.2i-1A.2i+1B.2i C.i/2 D.2i-1設用鄰接矩陣A表示有向圖G的存儲結構，則有向圖 G中頂點i的入度為（ ）°第i行非0元素的個數(shù)之和 B.第i列非0元素的個數(shù)之和C.第i行0元素的個數(shù)之和 D.第i列0元素的個數(shù)之和設一組初始記錄關鍵字序列為 （16,25,12,30,47,11,23,36,9,18,31），則以增量d=5的一趟希爾排序結束后的結果為（ ）°9.10.11.A.11,23,12,9,18,16,25,36,30,47,31C.16,23,12,9,11,18,25,36,30,47,31設某有向圖的鄰接表中有 n個表頭結點和A.n B.n-19.10.11.A.11,23,12,9,18,16,25,36,30,47,31C.16,23,12,9,11,18,25,36,30,47,31設某有向圖的鄰接表中有 n個表頭結點和A.n B.n-1設哈夫曼樹中的葉子結點總數(shù)為個空指針域。11,23,12,9,16,18,25,36,47,30,319,11,12,16,18,23,25,30,36,47,31m個表結點，則該圖中有( )條有向邊。m D.m-1C.m，若用二叉鏈表作為存儲結構，則該哈夫曼樹中總共有A.2m-1 B.2m對于線性表（7，34，55，25,為散列函數(shù)，則散列地址為C.2m+1 D.4m64，46,20，10）進行散列存儲時，若選用H（K）=K%9作1的元素有（ ）個。A. 1 B. 2 C. 3考試科目： 數(shù)據(jù)結構共5頁，第1頁TOC\o"1-5"\h\z下面程序的時間復雜為( )。for(i=1,s=0;i<=n; i++) {t=1;for(j=1;j<=i;j++){t=t*j;s=s+t;} }A. 0(n) B. 0(n2) C.0(n3) D.0(n4)對于一個具有n個頂點的無向連通圖，它包含的連通分量的個數(shù)為 ( )。A. 0 B.1 C.n D. n+1設無向圖G中邊的集合E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)}，則從頂點a出發(fā)進行深度優(yōu)先遍歷可以得到的一種頂點序列為( )。A.aebcfdB.acfebdC.aedfcb D.aedfbc設指針變量p指向雙向鏈表中結點A，指針變量s指向被插入的結點 X，則在結點A的后面插入結點X的操作序列為( )。p_>next=s;s->prior=p; p_>next->prior=s; s->prior=p->nest;s->prior=p;s_>next=p_>next;p_>next=s;s_>next->prior=s;p->prior=s;p_>nest->prior=s;s->prior=p;s_>next=p->prior;s->prior=p;s_>next=p->next;p_>next=s;p_>next->prior=s;填空題（每空2分，共20分）采用堆排序、快速排序、冒泡排序，對初態(tài)為有序的表，最省時間的是設一組初始記錄關鍵字序列為 （49,38,65,97,76,13,27,50），則第4趟直接選擇排序結束后的結果為 。當待排記錄序列按關鍵字順序有序時，直接插入排序和冒泡排序能達到 的時間復雜度，快速排序的時間性能退化為 （以第一個關鍵字為樞軸）。判定順序棧是否為空的條件是 ，判定順序棧是否為滿的條件當向B-樹中插入關鍵字時，可能引起結點的 ， 最終可能導致整個 B-樹的高TOC\o"1-5"\h\z度增加 。設散列表的長度為 8,散列函數(shù)H（k）=k%7,用線性探測法解決沖突，則根據(jù)一組初始關鍵字序列（8,15,16,22,30,32）構造出的散列表的平均查找長度是 。設在一棵度數(shù)為3的樹中，度數(shù)為3的結點數(shù)有2個，度數(shù)為2的結點數(shù)有1個，度數(shù)為1的結點數(shù)有2個，那么度數(shù)為0的結點數(shù)有 個。判斷題（每題1分，共10分，正確的選t，錯誤的選f）順序表查找指的是在順序存儲結構上進行查找。 （ ）循環(huán)隊列中不存在隊列滿的問題。 （ ）n階對稱矩陣可壓縮存儲到 n/2個單元的空間中。（）一個圖的鄰接表表示法是唯一的。 （）希爾排序是穩(wěn)定的。（）由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。 （ ）根據(jù)拓撲排序結果可以判斷一個有向圖中是否存在環(huán)路。 （）稀疏矩陣的壓縮存儲可以用一個三元組表來表示稀疏矩陣中的非 0元素。（ ）入棧操作和入隊列操作在鏈式存儲結構上實現(xiàn)時不需要考慮棧溢出的情況。 （）數(shù)據(jù)元素是數(shù)據(jù)的最小單位。 （ ）簡答題（45分）設有1000個元素組成的無序序列，希望用最快的速度挑選出其中前 10個（僅挑前10TOC\o"1-5"\h\z個）最大元素，以下幾種排序方法中哪一種最合適？分析各排序算法 ，給出原因？ （7分）（1）簡單選擇排序； （2）冒泡排序； （3）堆排序； （4）歸并排序設二叉排序樹中關鍵字由 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針對二叉樹，回答以下問題：（1） 具有n個結點的二叉樹的最小深度是多少？最大深度是多少？（ 4分）（2）具有n個結點的完全二叉樹中有多少個葉子結點？有多少個度為 2的結點？（4分）（3） 具有no個葉子結點的完全二叉樹中共有多少個結點？（ 4分）閱讀如下程序，寫出此程序的輸出結果（其中棧的元素類型為 char）。（5分）voidmain（）{StackS;charx,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）;}}給定圖1所示帶權有向圖，利用Floyd算法，求每一對頂點之間的最短路徑及其路徑長度（要求寫出求解過程）。（10分）圖1一個帶權無向圖的最小生成樹是否一定唯一？在什么情況下構造出的最小生成樹可能不唯一？（6分）五?算法填空(共2小題，每空2分，共20分)下面的算法是在帶頭結點的單鏈表 L中第i個位置之前插入元素 e。請在 處填上適當內(nèi)容，使其成為一個完整算法。typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;StatusListInsert_L(LinkList&L,inti,ElemTypee){p=L;j=(1);while(p&&(j<i-1)){p=p->next;(2) }if(!p)returnERROR;s=(LinkList)malloc(sizeof(LNode));s->date=e;;(4)returnOk;}下面是一個有向圖 G采用鄰接表存儲結構的拓撲排序算法。請在 處填上適當內(nèi)容，使其成為一個完整算法。typedefstructVNode{VertexTypedata;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstructArcNode{intadjvex;structArcNode*nextarc;InfoType *info;}ArcNode;typedefstruct{AdjListvertices;intvexnum,arcnum;int kind;}ALGraph;StatusTopologicalSort(ALGraphG){vexnum-1]InitStack(S);for(i=0;i<;++i){if((5) )Push(S,i); }count=0;while( (6) ){⑺；prin