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

昆明理工大學(xué)2014年碩士研究生招生入學(xué)考試試題(A卷) 考試科目代碼：818 考試科目名稱 ：計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合 考生答題須知 1． 所有題目（包括填空、選擇、圖表等類型題目）答題答案必須做在考點發(fā)給的答題紙上，做在本試題冊上無效。請考生務(wù)必在答題紙上寫清題號。 2． 評卷時不評閱本試題冊，答題如有做在本試題冊上而影響成績的，后果由考生自己負(fù)責(zé)。 3． 答題時一律使用藍(lán)、黑色墨水筆或圓珠筆作答（畫圖可用鉛筆），用其它筆答題不給分。 4． 答題時不準(zhǔn)使用涂改液等具有明顯標(biāo)記的涂改用品。 數(shù)據(jù)結(jié)構(gòu)部分 一、選擇題: (25題，每題1分，共25分) 1. 從一個具有n個結(jié)點單鏈表中查找其值等于x結(jié)點時，在查找成功時，需平均比較 結(jié)點數(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. 在一個具有n 個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復(fù)雜度為 。 (A) O(1) (B) O(n) (C) O(n2) (D) O(log2n) 4. 在一個單鏈表中，若要刪除*p結(jié)點的后繼結(jié)點，則執(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. 在一個鏈隊列中，f 和 r 分別為隊首尾指針，則進(jìn)行插入s 結(jié)點的操作時執(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. 從順序存儲的循環(huán)隊列中刪除一個元素時，是 。 (A) 先移動隊首指針，后取出元素 (B) 先取出元素，后移動隊首指針 7. 在一棵度為3的樹中，度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為1個，那么度為0的結(jié)點數(shù)為 個。 (A) 4 (B) 5 (C) 6 (D) 7 8. 在一棵二叉樹中，雙分支結(jié)點數(shù)為15個，單分支結(jié)點數(shù)為32個，則葉結(jié)點數(shù)為 個。 (A) 15 (B) 16 (C) 17 (D) 47 9. 一棵二叉樹結(jié)點數(shù)為18個，則其最小高度為 ，其最大高度為 。 (A) 4,16 (B)5,18 (C) 6,18 (D) 3,18 10. 一棵三叉樹結(jié)點數(shù)為50個，則其最小高度為 。 (A) 3 (B) 4 (C) 5 (D) 6 昆明理工大學(xué)2014年碩士研究生招生入學(xué)考試試題 11. 由分別帶權(quán)為9，2，5，7的四個葉結(jié)點構(gòu)造一棵哈夫曼樹，則該樹的帶權(quán)路徑長度是 。 (A) 23 (B)37 (C) 44 (D) 46 12. 已知10個數(shù)據(jù)元素（54，28，16，34，73，62，95，60，26，43），按照依次插入結(jié)點的方法生成一棵二叉排序樹后，則查找值為62的結(jié)點所需比較的次數(shù)是3；在查找成功的情況下，查找每個元素的平均比較次數(shù)（又稱平均查找長度，即查找每個元素時平均比較的結(jié)點數(shù)）為 。 (A) 2.5 (B)3.2 (C) 2.6 (D) 2.9 13. 在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的 倍。 (A) 1/2 (B) 1 (C) 2 (D) 4 14. 有n個頂點的無向圖中，要連通全部頂點至少需要 條邊。 (A) n (B) (n+1) (C) (n-1) (D) n/2 15. 有n個頂點和e條邊的無向圖中，若采用鄰接表表示，則表頭向量的大小為 條邊。 (A) n (B) (n+1) (C) (n-1) (D) n/2 16. 在有向圖的鄰接表中，每個頂點的鄰接表鏈接著該頂點的所有 鄰接點；在有向圖的逆鄰接表中，每個頂點的鄰接表鏈接著該頂點的所有 鄰接點； (A) 出邊，入邊 (B) 入邊，出邊 17. 對于一個具有n個頂點e條邊的的圖，若采用邊集數(shù)組表示，則邊集數(shù)組中的單元數(shù)至少為 個。 1 2 3 5 4 6 7 (A) n (B) n+e (C) e (D) 2e 18. 如圖1所示，若從頂點V1出發(fā)按廣度優(yōu)先搜索法進(jì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)值之和是 ；在該圖的最小生成樹中，從點V1到點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. 在對長度為n的順序存儲的有序表進(jìn)行二分查找時，對應(yīng)的二分查找判定樹的高度為 。 (A) n (B) log2n (C) log2(n+1) (D) log2(n+1) 22. 順序查找一個具有n個元素的線性表，其時間復(fù)雜度為 ，二分查找為一個具有n個元素的線性表，其時間復(fù)雜度為 。 (A) O(n),O(log2n) (B)O(log2n),O(log2n) (C) O(n2),O(n) (D) O(nlog2n),O(log2n) 23. 已知一個有序表為（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 24. 在順序存儲的線性表A[30]上進(jìn)行順序查找的平均查找長度為 。 (A) 15 (B) 15.5 (C) 16 (D) 20 25. 已知一個線性表為（38，25，74，63，52，48），假定采用H（K）=K mod 7計算散列地址進(jìn)行散列存儲時，若利用線性探測的開放定地址法處理沖突，則在該散列表上進(jìn)行查找的平均查找長度為 ；若利用鏈接法處理沖突，則在該散列表上進(jìn)行查找的平均查找長度為 。 (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ōu)先級又不加括號，則運算結(jié)果不唯一；后綴表達(dá)式中，不規(guī)定運算符的優(yōu)先級又不需括號，就能得到唯一的運算結(jié)果?，F(xiàn)以中綴表達(dá)式：（8+3*6）/（2+3*5-4）為例，回答如下問題： 1) 利用什么原理實現(xiàn)中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式？（5分） 2) 寫出中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式的算法思想。（10分） 3) 用上中綴表達(dá)式為例，圖示表現(xiàn)出其轉(zhuǎn)換成后綴表達(dá)式的過程及結(jié)果。（10分） 2. 在賓館管理中，要求每間客房的出租率均等，以保證維持每間客房硬件設(shè)施的一個平均磨損率?；卮鹑缦聠栴}： 1）利用《數(shù)據(jù)結(jié)構(gòu)》中什么原理處理這一問題？（5分） 2）請簡述并畫出示意描述圖。（20分） 計算機(jī)網(wǎng)絡(luò)部分 一、單項選擇題（每小題2分，總分22分） 1、按照0比特插入/刪除方法規(guī)定，在兩個標(biāo)志字段為F的比特序列中，如果檢查出連續(xù)的（）1，不管后面的比特位是0或1，都需要增加一個0。 A．4 B. 5 C. 6 D. 8 2、在（）差錯控制方式中，只會重新傳輸那些出錯的數(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、下面（）動態(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、如果有多個局域網(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)的頂級域名. A .com B .edu C .cn D .org E in-addr.arpa 10、將模擬信號轉(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、簡述計算機(jī)網(wǎng)絡(luò)的主要功能。（10分） 2、計算機(jī)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)有哪幾種？（10分） 3、試分析TCP可靠性是如何實現(xiàn)的。（10分） 4、試解釋TCP的三次握手過程。（10分） 5、已知某計算機(jī)所使用的IP地址是：195.169.20.25,子網(wǎng)掩碼是：255.255.255.240，請計算出該計算機(jī)的網(wǎng)絡(luò)號、子網(wǎng)號、主機(jī)號。（13分）