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

昆明理工大學2014年碩士研究生招生入學考試試題(A卷)考試科目代碼：818考試科目名稱：計算機學科專業(yè)基礎綜合考生答題須知.所有題目(包括填空、選擇、圖表等類型題目)答題答案必須做在考點發(fā)給的答題紙上，做在本試題冊上無效。請考生務必在答題紙上寫清題號。.評卷時不評閱本試題冊，答題如有做在本試題冊上而影響成績的，后果由考生自己負責。.答題時一律使用藍、黑色墨水筆或圓珠筆作答(畫圖可用鉛筆)，用其它筆答題不給分。.答題時不準使用涂改液等具有明顯標記的涂改用品。數(shù)據(jù)結(jié)構(gòu)部分一、選擇題：(25題，每題1分，共25分).從一個具有n個結(jié)點單鏈表中查找其值等于x結(jié)點時，在查找成功時，需平均比較結(jié)點數(shù)是。(A)n(B)n/2(C)(n-1)/2(D)(n+1)/22.下面算法的空間復雜度為。floataver(floata[n]){intj;for(j=n;j<0;j--)printf("%8.2f"，明]);(A)O(1)(B)O(log2n)(C)O(n)(D)O(n).在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復雜度為。(A)O(1)(B)O(n)(C)O(n2)(D)O(log2n).在一個單鏈表中，若要刪除*p結(jié)點的后繼結(jié)點，則執(zhí)行。p->next=p->next->next;p->next=p->next->next;free(p->next);p->next=p->next->next;q=p->next;free(q);q=p->next;p->next=p->next->next;free(q);.在一個鏈隊列中，f和r分別為隊首尾指針，則進行插入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;做了一個入隊操作，新節(jié)點當做尾結(jié)點.從順序存儲的循環(huán)隊列中刪除一個元素時，是。(A)先移動隊首指針，后取出元素(B)先取出元素，后移動隊首指針.在一棵度為3的樹中，度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為1個，那么度為0的結(jié)點數(shù)為個。TOC\o"1-5"\h\z(A)4(B)5(C)6(D)7樹中結(jié)點數(shù)等于所有2點度數(shù)的和加1.在一棵二叉樹中，雙分支結(jié)點數(shù)為15個，單分支結(jié)點數(shù)為32個，則葉結(jié)點數(shù)為個。(A)15(B)16(C)17(D)4715+1.一棵二叉樹結(jié)點數(shù)為18個，則其最小高度為—，其最大高度為一。(A)4,16(B)5,18(C)6,18(D)3,1810g2(18)+1.一棵三叉樹結(jié)點數(shù)為50個，則其最小高度為。(A)3(B)4(C)5(D)6

昆明理工大學2014年碩士研究生招生入學考試試題.由分別帶權(quán)為9,2,5,7的四個葉結(jié)點構(gòu)造一棵哈夫曼樹，則該樹的帶權(quán)路徑長度(A)23(B)37(C)44(D)46.已知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.在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的倍。(A)1/2(B)1(C)2(D)4.有n個頂點的無向圖中，要連通全部頂點至少需要條邊。(A)n(B)(n+1)(C)(n-1)(D)n/2.有n個頂點和e條邊的無向圖中，若采用鄰接表表示，則表頭向量的大小為條邊。(A)n(B)(n+1)(C)(n-1)(D)n/2.在有向圖的鄰接表中，每個頂點的鄰接表鏈接著該頂點的所有鄰接點；在有向圖的逆鄰接表中，每個頂點的鄰接表鏈接著該頂點的所有鄰接點；(A)出邊，入邊(B)入邊，出邊.對于一個具有n個頂點e條邊的的圖，若采用邊集數(shù)組表示，則邊集數(shù)組中的單元數(shù)至少為(A)n(B)n+e(C)e(D)2e.如圖1所示，若從頂點V1出發(fā)按廣度優(yōu)先搜索法進行遍歷可能得到的一種頂點序列是。V1,V2,V5,V3,V6,V7,V4V1,V5,V2,V4,V3,V7,V6圖1V1,V2,V5,V4,V3,V7,V6V1,V5,V2,V3,V7,V6,V4.如圖2所示，在該圖的最小生成樹中，各邊上權(quán)值之和是在該圖的最小生成樹中，從點V1到點V6的路徑是31,(V1,V3,V4,V6)36,(V1,V3,V4,V6)38,(V1,V4,V6)圖243,(V1,V4,V3,V6)已選定點里離目標定點最近的.如圖3所示，該圖得到的一種拓撲序列為。(V1,V4,V6,V2,V5,V3)(V1,V2,V3,V4,V5,V6)(V1,V4,V2,V3,V6,V5)圖3(V1,V2,V4,V6,V3,V5)(1)、找到一個沒有后繼的頂點(如果有一條邊從A指向B,那么B是A的后繼)。(2)、從圖中刪除這個頂點，在列表的前面插入頂點的標記。(3)、重復步驟1和2.直到所有的頂點都從圖中刪除。這時列表顯示的頂點順序就是拓撲排序的結(jié)果。昆明理工大學2014年碩士研究生招生入學考試試題.在對長度為n的順序存儲的有序表進行二分查找時，對應的二分查找判定樹的高度為。(A)n(B)_log2n_|(C)_log2(n+1)J(D)10g2(n+1).順序查找一個具有n個元素的線性表，其時間復雜度為,二分查找為一個具有n個元素的線性表，其時間復雜度為。(A)O(n),O(1og2n)(B)O(log2n),O(1og2n)(C)O(n2),O(n)(D)O(n1og2n),O(1og2n)二分查找好比二叉樹里樹的層數(shù).已知一個有序表為(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根據(jù)二分法查找的查找過程，首先將90與表中中間的元素50進行比較，由于90大于50,所以在線性表的后半部分查找。第二次與比較的元素是后半部分的中間元素，即90,這時兩者相等，即查找成功。.在順序存儲的線性表A[30]上進行順序查找的平均查找長度為。(A)15(B)15.5(C)16(D)20(n+1)/2.已知一個線性表為(38,25,74,63,52,48),假定采用H(K)=Kmod7計算散列地址進行散列存儲時，若利用線性探測的開放定地址法處理沖突，則在該散列表上進行查找的平均查找長度為;若利用鏈接法處理沖突，則在該散列表上進行查找的平均查找長度為。(A)1.5,1(B)1.7,3/2(C)2,4/3(D)2.3,7/6、綜合應用題：(2題，每題25分，共50分).中綴表達式中，如果不規(guī)定運算符的優(yōu)先級又不加括號，則運算結(jié)果不唯一；后綴表達式中，不規(guī)定運算符的優(yōu)先級又不需括號，就能得到唯一的運算結(jié)果?，F(xiàn)以中綴表達式：(8+3*6)/(2+3*5-4)為例，回答如下問題：TOC\o"1-5"\h\z1)利用什么原理實現(xiàn)中綴表達式轉(zhuǎn)換成后綴表達式？(5分)棧的數(shù)據(jù)結(jié)構(gòu)2)寫出中綴表達式轉(zhuǎn)換成后綴表達式的算|法思想。(10分)3)用上中綴表達式為例，圖示表現(xiàn)出其轉(zhuǎn)換成后綴表達式的過程及結(jié)果。(10分)轉(zhuǎn)換方法，對公式字符串進行逐位判斷。遇到公式中的變量直接輸出，運行符入棧。入棧時，比較棧頂運算符與入棧運算符的高低，再行出棧和入棧。中綴表達式轉(zhuǎn)后綴表達式遵循以下原則：.遇到操作數(shù)，直接輸出；.棧為空時，遇到運算符，入棧；.遇到左括號，將其入棧；.遇到右括號，執(zhí)行出棧操作，并將出棧的元素輸出，直到彈出棧的是左括號，左括號不輸出；.遇到其他運算符‘+“-“*"時，彈出所有優(yōu)先級大于或等于該運算符的棧頂元素，然后將該運算符入棧；.最終將棧中的元素依次出棧2.在賓館管理中，要求每間客房的出租率均等，以保證維持每間客房硬件設施的一個平均磨損率?；卮鹑缦聠栴}：1）利用《數(shù)據(jù)結(jié)構(gòu)》中什么原理處理這一問題？（5分）2）請簡述并畫出示意描述圖。（20分）?用數(shù)據(jù)結(jié)構(gòu)中的隊列，把所有空房排成一個隊。每次接待客人入住，從隊頭分配住房：客人結(jié)賬退房，退掉的房間排入隊尾。4-4023018137產(chǎn)空空―計算機網(wǎng)絡部分一、單項選擇題（每小題2分，總分22分）1、按照0比特插入/刪除方法規(guī)定，在兩個標志字段為F的比特序列中，如果檢查出連續(xù)的（）1,不管后面的比特位是0或1,都需要增加一個0。A.4B.5C.6D.82、在（）差錯控制方式中，只會重新傳輸那些出錯的數(shù)據(jù)幀。A.連續(xù)工作B.停止等待C.選擇重發(fā)D.后退N幀3、PPP協(xié)議可按功能劃分為兩層，其中負責建立、配置不同的網(wǎng)絡層協(xié)議的是（）協(xié)議。A.PPTPB.HDLCC.LCPD.NCP昆明理工大學2014年碩士研究生招生入學考試試題4、常用的A類私有地址是（）。A.?55B.?55C.?55D.?555、下面（）動態(tài)路由協(xié)議屬于IGP協(xié)議，使用了鏈路狀態(tài)算法。A.BGPB.RIPC.OSPFD.EGP6、在TCP/IP協(xié)議中，UDPB議是一種（）協(xié)議。A.主機-網(wǎng)絡層B.互聯(lián)網(wǎng)絡層C.傳輸層D.應用層7、如果有多個局域網(wǎng)需要互聯(lián)起來，并希望將局域網(wǎng)的廣播信息很好的隔離開，那么最基本的方法是用（）A.網(wǎng)橋B.路由器C.網(wǎng)關D.中繼8、香農(nóng)定理從定量的角度描述了帶寬”與速率”的關系。在香農(nóng)定理的公式中與信道的最大傳輸TOC\o"1-5"\h\z速率相關的參數(shù)主要有信道寬度與（）A.頻率特性B.信噪比C.相位特性D.噪聲功率9、（）用作商業(yè)機構(gòu)的頂級域名.A.comB.eduC.cnD.orgE10、將模擬信號轉(zhuǎn)換為數(shù)字數(shù)據(jù)的過程叫做（）。A.編碼B.解碼C.調(diào)制D.解調(diào)11、（）協(xié)議使用的是80端口，（）協(xié)議使用的是21端口。A.HTTP,TELNETB.DNS,TFTPC.HTTP,DNSD.HTTP,FTP二、綜合應用題（總分53分）1、簡述計算機網(wǎng)絡的主要功能。（10分）數(shù)據(jù)通信，資源共享，分布處理，集中管理，均衡負荷2、計算機網(wǎng)絡拓撲結(jié)構(gòu)有哪幾種？（10分）總線型拓撲、星型拓撲、環(huán)型拓撲、樹型拓撲和混合型拓撲3、試分析TCP可靠性是如何實現(xiàn)的。（10分）首先，為了防止數(shù)據(jù)在傳輸?shù)倪^程中被損壞，每個信息包都包含一個校驗碼，這個校驗碼頭就是一個用來保證信息包在傳輸過程中沒有被更改的代碼，當信息到達目的地的時候，接收方會對比較驗碼和收到的信息中的數(shù)據(jù)，如果校驗碼不對，則被信息包將被省略。第二，為了防止信息包丟失，TCP會要求接收方每收到一個信息包都反饋一下，如果接收方?jīng)]有提供反饋，發(fā)送方會自動重發(fā)一次，一直到接收方收到為止，或者它會判斷網(wǎng)絡鏈接斷開了，就會在程序中返回一個錯誤的提示。第三，為了防止信息包重復或順序錯誤，TCP每傳送一個信息包都會傳送一個序號，接收方會檢查這個序號，確保收到該信息包，并把全部信息包按順序重新合并，同時，如果接收方看到一個已接收了的序號，則這個信息包就會被丟棄。4、試解釋TCP的三次握手過程。（10分）第一次握手：建立連接時，客戶端發(fā)送syn包（syn=j）到服務器，并進入SYN_SEND狀態(tài)