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

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

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

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

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

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

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

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.已知一個有序表為（12，18，24，35，47，50，62，83，90，115，134），當二分查找值為90的元素時，()次比較后查找成功；當二分查找值為47的元素時，()次比較后查找成功。(A)

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