昆明理工大學(xué)2014年碩士研究生招生入學(xué)考試試題(A卷)考試科目代碼：818 考試科目名稱 ：計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合 考生答題須知1 所有題目（包括填空、選擇、圖表等類型題目）答題答案必須做在考點(diǎn)發(fā)給的答題紙上，做在本試題冊(cè)上無效。請(qǐng)考生務(wù)必在答題紙上寫清題號(hào)。2 評(píng)卷時(shí)不評(píng)閱本試題冊(cè)，答題如有做在本試題冊(cè)上而影響成績(jī)的，后果由考生自己負(fù)責(zé)。3 答題時(shí)一律使用藍(lán)、黑色墨水筆或圓珠筆作答（畫圖可用鉛筆），用其它筆答題不給分。4 答題時(shí)不準(zhǔn)使用涂改液等具有明顯標(biāo)記的涂改用品。數(shù)據(jù)結(jié)構(gòu)部分一、選擇題: (25題，每題1分，共25分)1. 從一個(gè)具有n個(gè)結(jié)點(diǎn)單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功時(shí)，需平均比較 結(jié)點(diǎn)數(shù)是 。(A) n (B) n/2 (C) (n-1)/2 (D) (n+1)/22. 下面算法的空間復(fù)雜度為 。float aver(float an) int j; for (j=n;j<0;j-) printf(“%8.2f”,aj); (A) O（1） (B) O（log2n） (C) O（n） (D) O（n2）3. 在一個(gè)具有n 個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度為 。 (A) O(1) (B) O(n) (C) O(n2) (D) O(log2n)4. 在一個(gè)單鏈表中，若要?jiǎng)h除*p結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行 。(A) p->next=p->next->next; (B) p->next=p->next->next; free(p->next);(C) p->next=p->next->next; q=p->next; free(q);(D) q=p->next; p->next=p->next->next; free(q);5. 在一個(gè)鏈隊(duì)列中，f 和 r 分別為隊(duì)首尾指針，則進(jìn)行插入s 結(jié)點(diǎn)的操作時(shí)執(zhí)行 。 (A)f->next=s;f=s;(B)r->next=s;r=s;(C)s->next=r;r=s; D)s->next=f;f=s;6. 從順序存儲(chǔ)的循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，是 。(A) 先移動(dòng)隊(duì)首指針，后取出元素 (B) 先取出元素，后移動(dòng)隊(duì)首指針7. 在一棵度為3的樹中，度為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1個(gè)，度為1的結(jié)點(diǎn)數(shù)為1個(gè)，那么度為0的結(jié)點(diǎn)數(shù)為 個(gè)。(A) 4 (B) 5 (C) 6 (D) 78. 在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15個(gè)，單分支結(jié)點(diǎn)數(shù)為32個(gè)，則葉結(jié)點(diǎn)數(shù)為 個(gè)。(A) 15 (B) 16 (C) 17 (D) 479. 一棵二叉樹結(jié)點(diǎn)數(shù)為18個(gè)，則其最小高度為 ，其最大高度為 。(A) 4,16 (B)5,18 (C) 6,18 (D) 3,1810. 一棵三叉樹結(jié)點(diǎn)數(shù)為50個(gè)，則其最小高度為 。 (A) 3 (B) 4 (C) 5 (D) 6昆明理工大學(xué)2014年碩士研究生招生入學(xué)考試試題11. 由分別帶權(quán)為9，2，5，7的四個(gè)葉結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，則該樹的帶權(quán)路徑長(zhǎng)度是 。 (A) 23 (B)37 (C) 44 (D) 4612. 已知10個(gè)數(shù)據(jù)元素（54，28，16，34，73，62，95，60，26，43），按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹后，則查找值為62的結(jié)點(diǎn)所需比較的次數(shù)是3；在查找成功的情況下，查找每個(gè)元素的平均比較次數(shù)（又稱平均查找長(zhǎng)度，即查找每個(gè)元素時(shí)平均比較的結(jié)點(diǎn)數(shù)）為 。 (A) 2.5 (B)3.2 (C) 2.6 (D) 2.9 13. 在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的 倍。(A) 1/2 (B) 1 (C) 2 (D) 414. 有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要 條邊。 (A) n (B) (n+1) (C) (n-1) (D) n/215. 有n個(gè)頂點(diǎn)和e條邊的無向圖中，若采用鄰接表表示，則表頭向量的大小為 條邊。(A) n (B) (n+1) (C) (n-1) (D) n/216. 在有向圖的鄰接表中，每個(gè)頂點(diǎn)的鄰接表鏈接著該頂點(diǎn)的所有 鄰接點(diǎn)；在有向圖的逆鄰接表中，每個(gè)頂點(diǎn)的鄰接表鏈接著該頂點(diǎn)的所有 鄰接點(diǎn)；(A) 出邊，入邊 (B) 入邊，出邊17. 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)e條邊的的圖，若采用邊集數(shù)組表示，則邊集數(shù)組中的單元數(shù)至少為 個(gè)。1235467(A) n (B) n+e (C) e (D) 2e18. 如圖1所示，若從頂點(diǎn)V1出發(fā)按廣度優(yōu)先搜索法進(jìn)行遍歷可能得到的一種頂點(diǎn)序列是 。(A)V1,V2,V5,V3,V6,V7,V4 (B) V1,V5,V2,V4,V3,V7,V6 圖1(C) V1,V2,V5,V4,V3,V7,V6 (D) V1, V5,V2,V3,V7,V6,V43124561281554201089619. 如圖2所示，在該圖的最小生成樹中，各邊上權(quán)值之和是 ；在該圖的最小生成樹中，從點(diǎn)V1到點(diǎn)V6的路徑是 。 (A) 31 , (V1,V3,V4,V6) (B) 36 , (V1,V3,V4,V6) (C) 38 , (V1,V4,V6) 圖2(D) 43 , (V1,V4,V3,V6)20. 如圖3所示，該圖得到的一種拓?fù)湫蛄袨?。 (A) (V1,V4,V6,V2,V5,V3) 123456(B) (V1,V2,V3,V4,V5,V6) （C) (V1,V4,V2,V3,V6,V5) 圖3(D) (V1,V2,V4,V6,V3,V5)昆明理工大學(xué)2014年碩士研究生招生入學(xué)考試試題21. 在對(duì)長(zhǎng)度為n的順序存儲(chǔ)的有序表進(jìn)行二分查找時(shí)，對(duì)應(yīng)的二分查找判定樹的高度為 。 (A) n (B) log2n (C) log2(n+1) (D) log2(n+1) 22. 順序查找一個(gè)具有n個(gè)元素的線性表，其時(shí)間復(fù)雜度為 ，二分查找為一個(gè)具有n個(gè)元素的線性表，其時(shí)間復(fù)雜度為 。(A) O(n),O(log2n) (B)O(log2n),O(log2n) (C) O(n2),O(n) (D) O(nlog2n),O(log2n) 23. 已知一個(gè)有序表為（12，18，24，35，47，50，62，83，90，115，134），當(dāng)二分查找值為90的元素時(shí)， 次比較后查找成功；當(dāng)二分查找值為47的元素時(shí)， 次比較后查找成功。 (A) 1，4 (B) 2，4 (C) 3，2 (D) 4，224. 在順序存儲(chǔ)的線性表A30上進(jìn)行順序查找的平均查找長(zhǎng)度為 。 (A) 15 (B) 15.5 (C) 16 (D) 2025. 已知一個(gè)線性表為（38，25，74，63，52，48），假定采用H（K）=K mod 7計(jì)算散列地址進(jìn)行散列存儲(chǔ)時(shí)，若利用線性探測(cè)的開放定地址法處理沖突，則在該散列表上進(jìn)行查找的平均查找長(zhǎng)度為 ；若利用鏈接法處理沖突，則在該散列表上進(jìn)行查找的平均查找長(zhǎng)度為 。 (A) 1.5,1 (B) 1.7,3/2 (C) 2,4/3 (D) 2.3,7/6二、綜合應(yīng)用題：(2題，每題25分，共50分)1. 中綴表達(dá)式中，如果不規(guī)定運(yùn)算符的優(yōu)先級(jí)又不加括號(hào)，則運(yùn)算結(jié)果不唯一；后綴表達(dá)式中，不規(guī)定運(yùn)算符的優(yōu)先級(jí)又不需括號(hào)，就能得到唯一的運(yùn)算結(jié)果?，F(xiàn)以中綴表達(dá)式：（8+3*6）/（2+3*5-4）為例，回答如下問題：1) 利用什么原理實(shí)現(xiàn)中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式？（5分）2) 寫出中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式的算法思想。（10分）3) 用上中綴表達(dá)式為例，圖示表現(xiàn)出其轉(zhuǎn)換成后綴表達(dá)式的過程及結(jié)果。（10分）2. 在賓館管理中，要求每間客房的出租率均等，以保證維持每間客房硬件設(shè)施的一個(gè)平均磨損率?；卮鹑缦聠栴}：1）利用數(shù)據(jù)結(jié)構(gòu)中什么原理處理這一問題？（5分）2）請(qǐng)簡(jiǎn)述并畫出示意描述圖。（20分）計(jì)算機(jī)網(wǎng)絡(luò)部分一、單項(xiàng)選擇題（每小題2分，總分22分）1、按照0比特插入/刪除方法規(guī)定，在兩個(gè)標(biāo)志字段為F的比特序列中，如果檢查出連續(xù)的（）1，不管后面的比特位是0或1，都需要增加一個(gè)0。A4 B. 5 C. 6 D. 82、在（）差錯(cuò)控制方式中，只會(huì)重新傳輸那些出錯(cuò)的數(shù)據(jù)幀。A.連續(xù)工作B.停止等待 C.選擇重發(fā)D.后退N幀3、PPP協(xié)議可按功能劃分為兩層，其中負(fù)責(zé)建立、配置不同的網(wǎng)絡(luò)層協(xié)議的是（）協(xié)議。A.PPTPB.HDLCC.LCPD.NCP昆明理工大學(xué)2014年碩士研究生招生入學(xué)考試試題4、常用的A 類私有地址是 （）。A. 10.10.0.010.255.255.255 B. 10.0.0.010.255.255.255C. 10.168.0.010.168.255.255 D. 172.16.0.0172.31.255.2555、下面（）動(dòng)態(tài)路由協(xié)議屬于IGP協(xié)議，使用了鏈路狀態(tài)算法。A.BGP B.RIP C.OSPF D.EGP6、在TCP/IP協(xié)議中，UDP協(xié)議是一種( )協(xié)議。A.主機(jī)-網(wǎng)絡(luò)層B.互聯(lián)網(wǎng)絡(luò)層C.傳輸層D.應(yīng)用層7、如果有多個(gè)局域網(wǎng)需要互聯(lián)起來，并希望將局域網(wǎng)的廣播信息很好的隔離開，那么最基本的方法是用（）A.網(wǎng)橋 B.路由器C.網(wǎng)關(guān)D.中繼8、香農(nóng)定理從定量的角度描述了“帶寬”與“速率”的關(guān)系。在香農(nóng)定理的公式中與信道的最大傳輸速率相關(guān)的參數(shù)主要有信道寬度與( )A.頻率特性B.信噪比 C.相位特性D.噪聲功率9、( )用作商業(yè)機(jī)構(gòu)的頂級(jí)域名.A .com B .edu C .cn D .org E in-addr.arpa10、將模擬信號(hào)轉(zhuǎn)換為數(shù)字?jǐn)?shù)據(jù)的過程叫做（）。A.編碼B.解碼C.調(diào)制D.解調(diào)11、（）協(xié)議使用的是80端口，( )協(xié)議使用的是21端口。A.HTTP,TELNET B.DNS,TFTPC.HTTP,DNSD.HTTP,FTP二、綜合應(yīng)用題（總分53分）1、簡(jiǎn)述計(jì)算機(jī)網(wǎng)絡(luò)的主要功能。（10分）2、計(jì)算機(jī)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)有哪幾種？（10分）3、試分析TCP可靠性是如何實(shí)現(xiàn)的。（10分）4、試解釋TCP的三次握手過程。（10分）5、已知某計(jì)算機(jī)所使用的IP地址是：195.169.20.25,子網(wǎng)掩碼是：255.255.255.240，請(qǐng)計(jì)算出該計(jì)算機(jī)的網(wǎng)絡(luò)號(hào)、子網(wǎng)號(hào)、主機(jī)號(hào)。（13分）