2018年溫州大學(xué)碩士研究生招生考試試題-831數(shù)據(jù)結(jié)構(gòu)

1、20182018年碩士研究生招生考試試題（年碩士研究生招生考試試題（A卷）卷）科目代碼及名稱：科目代碼及名稱：831數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)適用專業(yè)：適用專業(yè)：081201計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)081202計(jì)算機(jī)軟件與理論計(jì)算機(jī)軟件與理論第1頁(yè)，共頁(yè)，共4頁(yè)（請(qǐng)考生在答題紙上答題，在此試題紙上答題無(wú)效請(qǐng)考生在答題紙上答題，在此試題紙上答題無(wú)效）一、一、單項(xiàng)選擇題（單項(xiàng)選擇題（10小題，每小題小題，每小題4分，共分，共40分）分）1.計(jì)算機(jī)

2、所處理的數(shù)據(jù)一般具有某種內(nèi)在聯(lián)系，這是指（）。A.數(shù)據(jù)和數(shù)據(jù)之間存在某種關(guān)系B.數(shù)據(jù)元素和數(shù)據(jù)元素之間存在某種關(guān)系C.數(shù)據(jù)元素內(nèi)部具有某種結(jié)構(gòu)D.數(shù)據(jù)項(xiàng)和數(shù)據(jù)項(xiàng)之間存在某種關(guān)系2.順序存儲(chǔ)方式只能用于線性結(jié)構(gòu)，不能用于非線性結(jié)構(gòu)。這個(gè)斷言是（）。A.正確的B.錯(cuò)誤的3.設(shè)某算法完成對(duì)n個(gè)元素進(jìn)行處理，所需的時(shí)間是T(n)=100nlog2n200n500，則該算法的時(shí)間復(fù)雜度是（）。A.O(1)B.O(n)C.O(nlogn)D.O(n

3、lognn)4.采用順序存儲(chǔ)的兩個(gè)棧它的共享空間為S[1…m]，top[i]代表第i個(gè)棧（i=1，2）的棧頂，棧1的底在S[1]，棧2的底在S[m]，則棧滿的條件是（）。A.top[2]top[1]=0B.top[1]1=top[2]C.top[1]top[2]=mD.top[1]=top[2]5.已知二叉樹(shù)有50個(gè)葉子結(jié)點(diǎn)，則該二叉樹(shù)的總結(jié)點(diǎn)數(shù)至少應(yīng)有（）個(gè)。A.99B.100C.101D.1026.無(wú)向圖G有16條邊，度為4的頂點(diǎn)有

4、3個(gè)，度為3的頂點(diǎn)有4個(gè)，其余頂點(diǎn)的度均小于3，則圖G至少有（）個(gè)頂點(diǎn)。A.10B.11C.12D.137.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣表示，則該矩陣的大小是（）。A.nB.(n1)2C.n1D.n28.適合于折半查找的表的存儲(chǔ)方式及元素排列要求為（）。A.鏈接存儲(chǔ)，元素?zé)o序B.鏈接存儲(chǔ)，元素有序C.順序存儲(chǔ)，元素?zé)o序D.順序存儲(chǔ)，元素有序9.排序算法的穩(wěn)定性是指（）。A.經(jīng)過(guò)排序之后，能使值相同的數(shù)據(jù)保持原順序中的相對(duì)

5、位置不變B.經(jīng)過(guò)排序之后，能使值相同的數(shù)據(jù)保持原順序中的絕對(duì)位置不變C.排序算法的性能與待排序元素的數(shù)量關(guān)系不大D.排序算法的性能與待排序元素的數(shù)量關(guān)系密切10.5個(gè)不同的數(shù)據(jù)元素進(jìn)行直接插入排序，最多需要進(jìn)行（）次比較。A.8B.14C.15D.25二、二、簡(jiǎn)答題（簡(jiǎn)答題（4小題，每小題小題，每小題10分，共分，共40分）分）1找出滿足以下條件的所有二叉樹(shù)：（1）二叉樹(shù)的前序序列與中序序列相同；（2）二叉樹(shù)的中序序列與后序序列相同；（

6、3）二叉樹(shù)的前序序列與后序序列相同。2假設(shè)通訊電文中只用到A，B，C，D，E，F(xiàn)六個(gè)字母，它們?cè)陔娢闹谐霈F(xiàn)的相對(duì)頻率分別為：8，3，16，10，5，20。（1）構(gòu)造哈夫曼樹(shù)。（2）計(jì)算該哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度WPL。3己知序列355，672，91，83，781，34，410，76，125，320，建大根堆。4已知序列122163082841020618，請(qǐng)按照下面的快速排序算法，給出該序列作升序排列時(shí)前三趟的結(jié)果。20182018年碩士

7、研究生招生考試試題（年碩士研究生招生考試試題（A卷）卷）科目代碼及名稱：科目代碼及名稱：831數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)適用專業(yè)：適用專業(yè)：081201計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)081202計(jì)算機(jī)軟件與理論計(jì)算機(jī)軟件與理論第3頁(yè)，共頁(yè)，共4頁(yè)2.（15分）設(shè)計(jì)判斷二叉樹(shù)是否為二叉排序樹(shù)的算法。二叉排序樹(shù)的結(jié)構(gòu)如下：typedefintKeyTypetypedefstructNodeKeyTypekey關(guān)鍵字的值structNodeleft左指針

8、structNoderight右指針BSTNodeBSTree3.（15分）編寫(xiě)一個(gè)算法，對(duì)順序表進(jìn)行二分查找。順序表的存儲(chǔ)結(jié)構(gòu)描述如下：typedefintElementTypetypedefstructElementTypearray存放元素的數(shù)組intlength已經(jīng)有多少元素intcapacity容量SeqList給定的函數(shù)原型如下：intbinarySearch(SeqListlistElementTypek)4.（25分）給

9、定無(wú)向帶權(quán)圖，編寫(xiě)最小生成樹(shù)算法（Prim）。預(yù)置代碼如下：預(yù)置代碼如下：#include#include#include#defineMAXVEX200最大頂點(diǎn)數(shù)typedefVertexTypestructGraphStructtypedefstructGraphStructGraphtypedefstructENodeintadjVertex該邊所指的頂點(diǎn)的位置intweight邊的權(quán)structENodenextEdge指向下一