《計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合.doc（5頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

昆明理工大學(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)/2 2. 下面算法的空間復(fù)雜度為 。 float aver(float a[n]) { int j; for (j=n;j<0;j--) printf(“%8.2f”,a[j]); } (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) 7 8. 在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15個(gè)，單分支結(jié)點(diǎn)數(shù)為32個(gè)，則葉結(jié)點(diǎn)數(shù)為 個(gè)。 (A) 15 (B) 16 (C) 17 (D) 47 9. 一棵二叉樹結(jié)點(diǎn)數(shù)為18個(gè)，則其最小高度為 ，其最大高度為 。 (A) 4,16 (B)5,18 (C) 6,18 (D) 3,18 10. 一棵三叉樹結(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) 46 12. 已知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) 4 14. 有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要 條邊。 (A) n (B) (n+1) (C) (n-1) (D) n/2 15. 有n個(gè)頂點(diǎn)和e條邊的無向圖中，若采用鄰接表表示，則表頭向量的大小為 條邊。 (A) n (B) (n+1) (C) (n-1) (D) n/2 16. 在有向圖的鄰接表中，每個(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è)。 1 2 3 5 4 6 7 (A) n (B) n+e (C) e (D) 2e 18. 如圖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,V4 3 1 2 4 5 6 12 8 15 5 4 20 10 8 9 6 19. 如圖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) 1 2 3 4 5 6 (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，2 24. 在順序存儲(chǔ)的線性表A[30]上進(jìn)行順序查找的平均查找長(zhǎng)度為 。 (A) 15 (B) 15.5 (C) 16 (D) 20 25. 已知一個(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。 A．4 B. 5 C. 6 D. 8 2、在（）差錯(cuò)控制方式中，只會(huì)重新傳輸那些出錯(cuò)的數(shù)據(jù)幀。 A. 連續(xù)工作 B. 停止等待 C. 選擇重發(fā) D.后退N幀 3、PPP協(xié)議可按功能劃分為兩層，其中負(fù)責(zé)建立、配置不同的網(wǎng)絡(luò)層協(xié)議的是（）協(xié)議。 A. PPTP B. HDLC C. LCP D. NCP 昆明理工大學(xué)2014年碩士研究生招生入學(xué)考試試題 4、常用的A 類私有地址是 （）。 A. 10.10.0.0～10.255.255.255 B. 10.0.0.0～10.255.255.255 C. 10.168.0.0～10.168.255.255 D. 172.16.0.0～172.31.255.255 5、下面（）動(dòng)態(tài)路由協(xié)議屬于IGP協(xié)議，使用了鏈路狀態(tài)算法。 A.BGP B.RIP C.OSPF D.EGP 6、在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.arpa 10、將模擬信號(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,TFTP C.HTTP,DNS D.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分）