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

1、2015年全國(guó)碩士研究生統(tǒng)一入學(xué)考試自命題試題（年全國(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àng)選擇題

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

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

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

5、500個(gè)結(jié)點(diǎn)的完全二叉樹具有一個(gè)孩子的結(jié)點(diǎn)個(gè)數(shù)最多為（）。A1B250C0D249考試科目：數(shù)據(jù)結(jié)構(gòu)共5頁(yè)，第1頁(yè)考試科目：數(shù)據(jù)結(jié)構(gòu)共5頁(yè)，第2頁(yè)10存儲(chǔ)圖的鄰接表中，鄰接表的大小不但與圖的頂點(diǎn)個(gè)數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。（）四.簡(jiǎn)答題（簡(jiǎn)答題（45分）分）1.簡(jiǎn)述下列算法的功能。（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)鍵字依次插入一棵初始為空的二叉排序樹。畫出二叉排序樹的生成過(guò)程。（10分）3.關(guān)鍵字序列T=(63，55，48，37，20，90，84，32），對(duì)其從小到大排序，以第一個(gè)關(guān)鍵字為