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

1、2017年全國(guó)碩士研究生統(tǒng)一入學(xué)考試自命題試題（年全國(guó)碩士研究生統(tǒng)一入學(xué)考試自命題試題（B卷）卷）學(xué)科、專(zhuān)業(yè)名稱(chēng)：計(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ù)(專(zhuān)業(yè)學(xué)位)085211，軟件工程(專(zhuān)業(yè)學(xué)位)085212考試科目名稱(chēng)及代碼：數(shù)據(jù)結(jié)構(gòu)830考生注意：所有答案必須寫(xiě)在答題紙（卷）上，寫(xiě)在本試題上一律不給分。考生注意：所有

2、答案必須寫(xiě)在答題紙（卷）上，寫(xiě)在本試題上一律不給分。一、一、單項(xiàng)選擇題單項(xiàng)選擇題(每題每題2分，共分，共30分)1.一個(gè)隊(duì)列的入列序列是1234則隊(duì)列的輸出序列是（）。A.4321B.1234C.1432D.32412.循環(huán)隊(duì)列用數(shù)組A[0..m1]存放其元素值，已知其頭尾指針?lè)謩e是front和rear則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是()。A.(rearfrontm)%mB.rearfront1C.rearfront1D.rearfront3.

3、平衡二叉樹(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.N11B.N21C.N2N3D.N1N35.計(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é)

4、點(diǎn)進(jìn)行順序編號(hào)，則編號(hào)為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號(hào)為（）。A.2i1B.2iC.i2D.2i17.設(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)鍵字序列為(162512304711233691831)，則以增量d=5的一趟希爾排序結(jié)束后的結(jié)果為（）。A.112312918162536304

5、731B.112312916182536473031C.162312911182536304731C.9111216182325303647319.設(shè)某有向圖的鄰接表中有n個(gè)表頭結(jié)點(diǎn)和m個(gè)表結(jié)點(diǎn)，則該圖中有（）條有向邊。A.nB.n1C.mD.m110.設(shè)哈夫曼樹(shù)中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹(shù)中總共有（）個(gè)空指針域。A.2m1B.2mC.2m1D.4m11.對(duì)于線(xiàn)性表（7，34，55，25，64，46，20

6、，10）進(jìn)行散列存儲(chǔ)時(shí)，若選用H(K)=K%9作為散列函數(shù)，則散列地址為1的元素有（）個(gè)。A1B2C3D4考試科目：數(shù)據(jù)結(jié)構(gòu)共5頁(yè)，第1頁(yè)四.簡(jiǎn)答題（簡(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ù)

7、組成，現(xiàn)要查找關(guān)鍵字為363的結(jié)點(diǎn)，下面的關(guān)鍵字序列哪個(gè)不可能是在二叉樹(shù)中查到的序列？說(shuō)明原因。（5分）（1）51250501390320340382363（2）24，877，125342501，623，4213633.針對(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ù)中共有多少

8、個(gè)結(jié)點(diǎn)？（4分）4.閱讀如下程序，寫(xiě)出此程序的輸出結(jié)果（其中棧的元素類(lèi)型為）。(5分)voidmain()StackSxyInitStack(S)x=yy=sPush(Sx)Push(Sy)Pop(Sx)Push(Sk)Push(Sx)while(!StackEmpty(S))Pop(Sy)printf(y)5.給定圖1所示帶權(quán)有向圖，利用Floyd算法，求每一對(duì)頂點(diǎn)之間的最短路徑及其路徑長(zhǎng)度（要求寫(xiě)出求解過(guò)程）。（10分）圖16.一個(gè)