2016年昆明理工大學(xué)818計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合考研專(zhuān)業(yè)課真題分享

1、第1頁(yè)共8頁(yè)昆明理工大學(xué)昆明理工大學(xué)20162016年碩士研究生招生入學(xué)考試試題年碩士研究生招生入學(xué)考試試題(A(A卷)考試科目代碼：818考試科目名稱(chēng)：計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合考生答題須知考生答題須知1所有題目（包括填空、選擇、圖表等類(lèi)型題目）答題答案必須做在考點(diǎn)發(fā)給的答題紙上，做在本試題冊(cè)上無(wú)效。請(qǐng)考生務(wù)必在答題紙上寫(xiě)清題號(hào)。2評(píng)卷時(shí)不評(píng)閱本試題冊(cè)，答題如有做在本試題冊(cè)上而影響成績(jī)的，后果由考生自己負(fù)責(zé)。3答題時(shí)一律使用藍(lán)、黑色墨水筆

2、或圓珠筆作答（畫(huà)圖可用鉛筆），用其它筆答題不給分。4答題時(shí)不準(zhǔn)使用涂改液等具有明顯標(biāo)記的涂改用品。數(shù)據(jù)結(jié)構(gòu)部分?jǐn)?shù)據(jù)結(jié)構(gòu)部分一、一、單項(xiàng)選擇題（共單項(xiàng)選擇題（共2525題，每題題，每題1分，共分，共2525分）分）1.對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下（）方面的內(nèi)容。(A)健壯性和可讀性（B）并行性（C）正確性（D）時(shí)空復(fù)雜度2.對(duì)線(xiàn)性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？()（A）經(jīng)常需要隨機(jī)地存取元素（B）經(jīng)常需要進(jìn)行插入和刪除操作（C）表

3、中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間（D）表中元素的個(gè)數(shù)不變3.下面程序段的時(shí)間復(fù)雜度是（）。j=0s=0while(snext=pnextnext(B)p=pnext(C)p=pnextnext(D)next=p6.若某線(xiàn)性表最常用的操作是讀取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則采用（）存儲(chǔ)方式最省時(shí)間。(A)順序表(B)雙鏈表(C)帶頭結(jié)點(diǎn)的雙循環(huán)鏈表(D)單循環(huán)鏈表7.用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)().(A)僅修

4、改頭指針(B)頭、尾指針都要修改(C)僅修改尾指針(D)頭、尾指針可能都要修改8.在順序棧中，假定以高端地址作為棧底，以top作為棧頂，則當(dāng)做出棧處理時(shí)，top的變化為()。(A)不變(B)top=0(C)top=top1(D)top=top1第3頁(yè)共8頁(yè)3124561281554201089618.在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，最多包含有()邊。(A)n(n1)2(B)n(n1)(C)n(n1)2(D)n219.在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)

5、向圖中，要連通全部頂點(diǎn)至少需要()條邊。(A)n(B)n1(C)n1(D)n220.任何一個(gè)無(wú)向連通圖的最小生成樹(shù)()(A)只有一棵(B)有一棵或多棵(C)一定有多棵(D)可能不存在。21.在有向圖的鄰接表中，每個(gè)頂點(diǎn)的鄰接表鏈接著該頂點(diǎn)的所有()鄰接點(diǎn)；在有向圖的逆鄰接表中，每個(gè)頂點(diǎn)的鄰接表鏈接著該頂點(diǎn)的所有()鄰接點(diǎn)；(A)出邊，入邊(B)入邊，出邊22.在線(xiàn)性表的存儲(chǔ)結(jié)構(gòu)中，()查找（按關(guān)鍵字查找）、插入、刪除速度慢，但順序存取和

6、隨機(jī)存取第i個(gè)元素速度快；()查找和存取速度快，但插入、刪除速度慢；()查找、插入和刪除速度快，但不能進(jìn)行順序存?。?)插入、刪除和順序存取速度快；但查找速度慢。(A)散列表，順序有序表，順序表，鏈接表(B)順序表，順序有序表，散列表，鏈接表(C)鏈接表，順序有序表，散列表，順序表(D)順序有序表，順序表，鏈接表，散列表23.用某種排序方法對(duì)關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）進(jìn)行排序時(shí)，序列的變化情況如下

7、：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84則所采用的排序方法是（）(A)選擇排序（B）希爾排序（C）歸并排序（D）快速排序24.已知一個(gè)有序表為（12，18，24，35，47，50，62，83，90，115，134），當(dāng)二分查找值為90的元素時(shí)，()次比較后查找成功；當(dāng)二分查找值為47的元素時(shí)，()次比較后查找成功。(A)

8、1，4(B)2，4(C)3，2(D)4，225.在順序存儲(chǔ)的線(xiàn)性表A[30]上進(jìn)行順序查找的平均查找長(zhǎng)度為()。(A)15(B)15.5(C)16(D)20二、綜合題：（共3題，共50分）1.在算法設(shè)計(jì)中，存儲(chǔ)結(jié)構(gòu)的設(shè)計(jì)與什么因素有關(guān)？（10分）2.在幾個(gè)居民點(diǎn)鋪設(shè)煤氣管道，每?jī)蓚€(gè)居民間的鋪設(shè)費(fèi)用是可以估算的（如右圖所示）。1)如果要求鋪設(shè)的總費(fèi)用最小，從圖的理論上，這實(shí)際上是什么求解問(wèn)題。（8分）2)請(qǐng)用Prim算法思想，從V1點(diǎn)開(kāi)始