16年研究生昆明理工計算機818考試題目和答案

第1頁共11頁昆明理工大學2016年碩士研究生招生入學考試試題(A卷)考試科目代碼：818考試科目名稱：計算機學科專業(yè)基礎綜合考生答題須知所有題目（包括填空、選擇、圖表等類型題目）答題答案必須做在考點發(fā)給的答題紙上，做在本試題冊上無效。請考生務必在答題紙上寫清題號。評卷時不評閱本試題冊，答題如有做在本試題冊上而影響成績的，后果由考生自己負責。答題時一律使用藍、黑色墨水筆或圓珠筆作答（畫圖可用鉛筆），用其它筆答題不給分。答題時不準使用涂改液等具有明顯標記的涂改用品。數據結構部分單項選擇題（共25題，每題1分，共25分）對一個算法的評價，不包括如下（）方面的內容。(A)．健壯性和可讀性（B）并行性（C）正確性（D）時空復雜度

對線性表，在下列哪種情況下應當采用鏈表表示？()（A）經常需要隨機地存取元素（B）經常需要進行插入和刪除操作（C）表中元素需要占據一片連續(xù)的存儲空間（D）表中元素的個數不變當數據在存儲單元不連續(xù)時，采用鏈表比較好，連續(xù)時線性好下面程序段的時間復雜度是（）。j=0;s=0;while(s<n){j++;s=s+j;}(A)O（√n）(B)O（√2n）(C)O（n）(D)O（n2）從一個長度為n的順序表中，如果刪除第i個元素時，需要向前移動（）個元素。

(A)n-i(B)n-i+1(C)n-i-1(D)i設單鏈表中指針p指向結點Ａ，若要刪除Ａ之后的結點（結點若存在），則需修改指針的操作是（）。(A)p->next=p->next->next(B)p=p->next(C)p=p->next->next(D)next=pq:=p^.next;

p^.next:=p^.next^.next;

dispose(q);若某線性表最常用的操作是讀取任一指定序號的元素和在最后進行插入和刪除運算，則采用（）存儲方式最省時間。

(A)順序表(B)雙鏈表(C)帶頭結點的雙循環(huán)鏈表(D)單循環(huán)鏈表順序表便于存取,如果要插入,刪除則需要移動大量的數據,工作量大.而在末尾的插入刪除既不需要了.鏈表方便與插入,刪除存取的話需要遍歷整個鏈表,工作量大.用鏈接方式存儲的隊列，在進行插入運算時().(A)僅修改頭指針(B)頭、尾指針都要修改(C)僅修改尾指針(D)頭、尾指針可能都要修改在順序棧中，假定以高端地址作為棧底，以top作為棧頂，則當做出棧處理時，top的變化為()。

(A)不變(B)top=0(C)top=top-1(D)top=top+1昆明理工大學2016年碩士研究生招生入學考試試題在一個具有n個頂點的無向圖中，最多包含有()邊。

(A)n(n-1)/2(B)n(n-1)(C)n(n+1)/2(D)n2在一個具有n個頂點的無向圖中，要連通全部頂點至少需要()條邊。

(A)n(B)n+1(C)n-1(D)n/2任何一個無向連通圖的最小生成樹()

(A)只有一棵(B)有一棵或多棵(C)一定有多棵(D)可能不存在。在有向圖的鄰接表中，每個頂點的鄰接表鏈接著該頂點的所有()鄰接點；在有向圖的逆鄰接表中，每個頂點的鄰接表鏈接著該頂點的所有()鄰接點；

(A)出邊，入邊(B)入邊，出邊在線性表的存儲結構中，()查找（按關鍵字查找）、插入、刪除速度慢，但順序存取和隨機存取第i個元素速度快；()查找和存取速度快，但插入、刪除速度慢；()查找、插入和刪除速度快，但不能進行順序存??；()插入、刪除和順序存取速度快；但查找速度慢。散列表，順序有序表，順序表，鏈接表順序表，順序有序表，散列表，鏈接表鏈接表，順序有序表，散列表，順序表順序有序表，順序表，鏈接表，散列表用某種排序方法對關鍵字序列（25，84，21，47，15，27，68，35，20）進行排序時，序列的變化情況如下：

20，15，21，25，47，27，68，35，84

15，20，21，25，35，27，47，68，84

15，20，21，25，27，35，47，68，84

則所采用的排序方法是（）

(A)選擇排序（B）希爾排序（C）歸并排序（D）快速排序已知一個有序表為（12，18，24，35，47，50，62，83，90，115，134），當二分查找值為90的元素時，()次比較后查找成功；當二分查找值為47的元素時，()次比較后查找成功。

(A)1，4(B)2，4(C)3，2(D)4，2在順序存儲的線性表A[30]上進行順序查找的平均查找長度為()。

(A)15(B)15.5(C)16(D)20二、綜合題：（共3題，共50分）在算法設計中，存儲結構的設計與什么因素有關？（10分）數據的邏輯結構3131245612815542010896如果要求鋪設的總費用最小，從圖的理論上，這實際上是什么求解問題。（8分）最小生成樹請用Prim算法思想，從V1點開始，畫出鋪設方案選邊的圖示過程。（12分）3.一組待排序的記錄為（46,79,56,38,40,84），寫出從小到大：①利用冒泡排序第一,二趟的變化序列;（10分）46,56,38,40,79,8446,38,40,56,79,84②利用快速排序第一趟的變化序列;（10分）40，38，46，56，79，84)

[],79,56,38,40,84

40,79,56,38,[],84

//從后往前掃找到40比46小，交換

40,[],56,38,79,84

//從前往后掃找到79比46大，交換

40,38,56,[],79,84

//從后往前掃找到38比46小，交換

40,38,[],56,79,84

//從前往后掃找到56比46大，交換

40,38,46,56,79,84

//最后插入基準46昆明理工大學2016年碩士研究生招生入學考試試題計算機網絡部分一、單項選擇題（每空1分，總分20分）1、Internet中域名與IP地址之間的翻譯是由__(1)__來完成的。

A.域名服務器B.代理服務器C．FTP服務器D．Web服務器2、瀏覽器與WWW服務器之間傳輸信息時使用的協(xié)議是___(2)___。

A．HTTPB．HTMLC．FTPD．SNMP

3、屬于物理層的互連設備是_(3)_。

A中繼器B網橋C.交換機D.路由器4、路由器是一種常用的網絡互連設備，它工作在OSI／RM的（4）上，在網絡中它能夠根據網絡通信的情況（5），并識別（6）·相互分離的網絡經路由器互連后（7）。

(4)：A．物理層B．數據鏈路層C．網絡層D．傳輸層

(5)：A．動態(tài)選擇路由B．控制數據流量C．調節(jié)數據傳輸率D．改變路由結構

(6)：A．MAC地址B．網絡地址C．MAC地址和網絡地址D．MAC地址和網絡地址的共同邏輯地址

(7)：A．形成了一個更大的物理網絡B．仍然還是原來的網絡

C．形成了一個邏輯上單一的網絡D．成為若干個互連的子網

5、ADSL對應的中文術語是__(8)__。

A．分析數字系統(tǒng)層B．非對稱數字線

C．非對稱數字用戶線D．異步數字系統(tǒng)層HDSL對稱6、以下網絡設備中，工作于網絡層的設備是__(9)__。A．調制解調器B.以太網交換機C.集線器D.路由器7、在Windows中，可以提供WWW服務的軟件是__(10)__。

A.IISB.ISAC.ISPD.ASP8、網絡/22中最多可用的主機地址是__(11)__。

A.1024B.1023C.1022D.1000昆明理工大學2016年碩士研究生招生入學考試試題9、通過__(12)__命令可以查看當前計算機的TCP連接狀態(tài)。

A.routeB.pingC.netstatD.ipconfig10、在下列網絡服務中，__(13)__是遠程登陸服務，默認端口號為__(14)__。

（13）A.WWWB.FTPC.BBSD.Telnet

（14）A．21B．23C．25D．8011、在網絡地址中劃分出10個大小相同的子網，每個子網最多有___(15)___個可用的主機地址。

A．2046B．2048C．4094D．4096

12、在瀏覽Web頁面時，發(fā)現(xiàn)了自己需要經常使用的Web頁面，此時最好的方法是___(16)___。

A．將該Web頁面的地址加入到"收藏夾"

B．將該Web頁面的地址加入到"地址簿"

C．將該Web頁面的地址加入到"notepad"

D．將該Web頁面的地址加入到"歷史記錄"13、在Windows的網絡屬性配置中，“默認網關”應該設置為_(17)_的地址。

A．DNS服務器B．Web服務器C．路由器D．交換機14、電子郵件通常使用的協(xié)議有_(18)_。A．SMTP和POP3B．SMTP和RMONC．RMON和SNMPD．SNMP和POP315、Internet中用于文件傳輸的是_(19)_。

A．DHCP服務器B．DNS服務器C．FTP服務器D．路由器16、代理服務器可以提供_(20)_功能。

A．信息轉發(fā)B．路由選擇C．域名解析D．幀封裝

昆明理工大學2016年碩士研究生招生入學考試試題二、綜合應用題（總分55分）1、制作交叉雙絞線(一端按EIA/TIA568A線序，另一端按EIA/TIA568B線序)時，其中一端的線序如圖(a)所示，另一端線序如圖(b)所示，將圖(b)中(1)～(8)處空缺的顏色名稱填寫出來（每空2.5分，20分）。2、某公司內部有一個采用TCP/IP作為傳輸協(xié)議的100Base-TX局域網，包括1臺服務器和20臺客戶機，通過一臺16端口的交換機與一臺8端口共享集線器級連，其網絡結構如下圖所示。服務器上運行DHCP服務軟件，客戶機的IP地址由DHCP服務程序自動分配。（15分）

[問題1]

連接主機A與交換機的單根網線的最大長度為多少?(5分)100m[問題2]

該局域網中的集線器每個端口平均享有的帶寬是多少?(5分)以一個10M的HUB和一個10M的交換機為例,HUB的每個端口帶寬(正在使用)之和等于10M.而交換機是每個端口都是10M100/8兆帶寬[問題3]｝

為了控制局域網用戶訪問Internet時只能進行WWW瀏覽，網管應該在路由器上采取什么措施?(5分)策略設置，只讓TCP80的端口進行傳輸