暨南大學(xué)計算機830數(shù)據(jù)結(jié)構(gòu)2015年真題

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

2、單項選擇題(每題每題2分，共分，共30分)1線性表采用鏈式存儲時其地址()。A必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)與否均可以2若有一個棧的輸入序列是1，2，3，…，n，輸出序列的第一個元素是n則第i個輸出元素是（）。A.niB.ni1C.ni1D.不確定3.已知單鏈表上一結(jié)點的指針為p，則刪除該結(jié)點后繼的正確操作語句是（）。A.s=pnextp=pnextfree(s)Bp=pnextfree(p)C.s=pn

3、extpnext=snextfree(s)Dp=pnextfree(pnext)4.若使用鄰接矩陣表示某有向圖，則矩陣中非零元素的個數(shù)等于（）。A.圖中頂點的數(shù)目B.圖中邊的數(shù)目C.圖中邊的數(shù)目的兩倍D.無法確定5.下列哪種排序需要的附加存儲開銷最大()。A快速排序B.堆排序C.歸并排序D.插入排序6.下面哪一方法可以判斷出一個有向圖是否有環(huán)（即回路）（）。A拓撲排序B.求最短路徑C.求最小生成樹D.廣度優(yōu)先遍歷7.具有n個頂點的無向圖

4、至少應(yīng)有（）條邊才能確保是一個連通圖.An1BnCn1D2n8.對線性表進行折半查找時要求線性表必須()。A.以順序方式存儲B.以順序方式存儲且結(jié)點按關(guān)鍵字有序排序C.以鏈接方式存儲D.以鏈接方式存儲且結(jié)點按關(guān)鍵字有序排序9若使用二叉鏈表作為樹的存儲結(jié)構(gòu)，在有n個結(jié)點的二叉鏈表中非空的鏈域的個數(shù)為()。A.n1B.2n1C.n1D.2n110在內(nèi)部排序中排序時不穩(wěn)定的有()。A.插入排序B.冒泡排序C.快速排序D.歸并排序11.一個具有

5、500個結(jié)點的完全二叉樹具有一個孩子的結(jié)點個數(shù)最多為（）。A1B250C0D249考試科目：數(shù)據(jù)結(jié)構(gòu)共5頁，第1頁考試科目：數(shù)據(jù)結(jié)構(gòu)共5頁，第2頁10存儲圖的鄰接表中，鄰接表的大小不但與圖的頂點個數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。（）四.簡答題（簡答題（45分）分）1.簡述下列算法的功能。（6分）typedefstructBiTNodeTElemTypedatastructBiTNodelchildrchildBiTNodeBiTreevo

6、idProcess(BiTreeT)IniStack(S)P=Twhile(P||!StackEmpty(S))if(P)push(P=Plchildelsepop(printf(Pdata)P=Prchild2.假設(shè)表中關(guān)鍵字序列為（76910，148），將關(guān)鍵字依次插入一棵初始為空的二叉排序樹。畫出二叉排序樹的生成過程。（10分）3.關(guān)鍵字序列T=(63，55，48，37，20，90，84，32），對其從小到大排序，以第一個關(guān)鍵字為