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

對線性表，在以下哪種情況下應(yīng)當(dāng)采用鏈表表示？()〔A〕經(jīng)常需要隨機地存取元素〔B〕經(jīng)常需要進(jìn)行插入和刪除操作〔C〕表中元素需要占據(jù)一片連續(xù)的存儲空間〔D〕表中元素的個數(shù)不變當(dāng)數(shù)據(jù)在存儲單元不連續(xù)時，采用鏈表比較好，連續(xù)時線性好下面程序段的時間復(fù)雜度是〔〕。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設(shè)單鏈表中指針p指向結(jié)點Ａ，假設(shè)要刪除Ａ之后的結(jié)點〔結(jié)點假設(shè)存在〕，那么需修改指針的操作是〔〕。(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);假設(shè)某線性表最常用的操作是讀取任一指定序號的元素和在最后進(jìn)行插入和刪除運算，那么采用〔〕存儲方式最省時間。

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

(A)不變(B)top=0(C)top=top-1(D)top=top+1昆明理工大學(xué)2024年碩士研究生招生入學(xué)考試試題一個棧的入棧序列為123，入棧時可以出棧，那么以下序列中不可能是出棧序列的是()(A)231 (B)321(C)312 (D)123輸入受限的雙端隊列是指元素只能從隊列的一端輸入，但可以從隊列的兩端輸出，如以下列圖。假設(shè)有8、1、4、2依次進(jìn)入輸入受限的雙端隊列，那么得不到輸出序列().。輸入受限的雙端隊列 (A).2、8、1、4(B).1、4、8、2(C).4、2、1、8(D).2、1、4、8棧和隊列的共同特點是()。(A)只允許在端點處插入和刪除元素 (B)都是先進(jìn)后出(C)都是先進(jìn)先出 (D)沒有共同點給定一個有n個元素的有序線性表。假設(shè)采用順序存儲結(jié)構(gòu)，那么在等概率前提下，刪除其中的一個元素平均需要移動個元素。(A).(n+1)/2(B).n/2(C).(n-1)/2(D).1在具有n個單元的順序存儲的循環(huán)隊列中，假定front、rear分別為隊首和隊尾指針，那么判斷隊滿的條件是().。

〔A〕(rear%n)==front〔B〕((front+1%n)==rear〔C〕((rear-1)%n)==front〔D〕((rear+1)%n)==front一個中綴算術(shù)表達(dá)式a+〔b-x〕*y，那么對應(yīng)的后綴算術(shù)表達(dá)式為().。

(A)abxy-*+;(B)abx-+y*;

(C)abx-y*+;(D)abxy*-+;設(shè)有一個二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個元素占一個空間，問A[3][3](10)存放在什么位置？().腳注(10)表示用10進(jìn)制表示。(A)688(B)678(C)692〔D〕696計算公式A[i][j]：A[0][0]+nj+i;644+2*n+2=676；n=15;A[3][3]=644+3*15+3=692；樹最適合用來表示()。(A)有序數(shù)據(jù)元素(B)無序數(shù)據(jù)元素(C)元素之間具有分支層次關(guān)系的數(shù)據(jù)(D)元素之間無聯(lián)系的數(shù)據(jù)在有n個結(jié)點的二叉鏈表中，值非空的鏈域的個數(shù)為()。

(A)n-1(B)2n-1(C)n+1(D)2n+1在一個具有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)入邊，出邊在線性表的存儲結(jié)構(gòu)中，()查找〔按關(guān)鍵字查找〕、插入、刪除速度慢，但順序存取和隨機存取第i個元素速度快；()查找和存取速度快，但插入、刪除速度慢；()查找、插入和刪除速度快，但不能進(jìn)行順序存?。?)插入、刪除和順序存取速度快；但查找速度慢。散列表，順序有序表，順序表，鏈接表順序表，順序有序表，散列表，鏈接表鏈接表，順序有序表，散列表，順序表順序有序表，順序表，鏈接表，散列表用某種排序方法對關(guān)鍵字序列〔25，84，21，47，15，27，68，35，20〕進(jìn)行排序時，序列的變化情況如下：

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〕，當(dāng)二分查找值為90的元素時，()次比較后查找成功；當(dāng)二分查找值為47的元素時，()次比較后查找成功。

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

(A)15(B)15.5(C)16(D)20二、綜合題：〔共3題，共50分〕在算法設(shè)計中，存儲結(jié)構(gòu)的設(shè)計與什么因素有關(guān)？〔10分〕數(shù)據(jù)的邏輯結(jié)構(gòu)3131245612815542010896如果要求鋪設(shè)的總費用最小，從圖的理論上，這實際上是什么求解問題?！?分〕最小生成樹請用Prim算法思想，從V1點開始，畫出鋪設(shè)方案選邊的圖示過程?！?2分〕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

//最后插入基準(zhǔn)46昆明理工大學(xué)2024年碩士研究生招生入學(xué)考試試題計算機網(wǎng)絡(luò)局部一、單項選擇題〔每空1分，總分20分〕1、Internet中域名與IP地址之間的翻譯是由__(1)__來完成的。

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

A．HTTPB．HTMLC．FTPD．SNMP

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

A中繼器B網(wǎng)橋C.交換機D.路由器4、路由器是一種常用的網(wǎng)絡(luò)互連設(shè)備，它工作在OSI／RM的〔4〕上，在網(wǎng)絡(luò)中它能夠根據(jù)網(wǎng)絡(luò)通信的情況〔5〕，并識別〔6〕·相互別離的網(wǎng)絡(luò)經(jīng)路由器互連后〔7〕。

(4)：A．物理層B．?dāng)?shù)據(jù)鏈路層C．網(wǎng)絡(luò)層D．傳輸層

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

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

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

C．形成了一個邏輯上單一的網(wǎng)絡(luò)D．成為假設(shè)干個互連的子網(wǎng)

5、ADSL對應(yīng)的中文術(shù)語是__(8)__。

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

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

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

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

A.routeB.pingC.netstatD.ipconfig10、在以下網(wǎng)絡(luò)效勞中，__(13)__是遠(yuǎn)程登陸效勞，默認(rèn)端口號為__(14)__。

〔13〕A.WWWB.FTPC.BBSD.Telnet

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

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

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

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

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

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

D．將該Web頁面的地址參加到"歷史記錄"13、在Windows的網(wǎng)絡(luò)屬性配置中，“默認(rèn)網(wǎng)關(guān)〞應(yīng)該設(shè)置為_(17)_的地址。

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

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

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

昆明理工大學(xué)2024年碩士研究生招生入學(xué)考試試題二、綜合應(yīng)用題〔總分55分〕1、制作交叉雙絞線(一端按EIA/TIA568A線序，另一端按EIA/TIA568B線序)時，其中一端的線序如圖(a)所示，另一端線序如圖(b)所示，將