1、2014年云南昆明理工大學(xué)計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合考研真題A卷數(shù)據(jù)結(jié)構(gòu)部分一、選擇題: (25題，每題1分，共25分)1. 從一個具有n個結(jié)點(diǎn)單鏈表中查找其值等于x結(jié)點(diǎn)時，在查找成功時，需平均比較 結(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;jnext=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-

2、next; p-next=p-next-next; free(q);5. 在一個鏈隊列中，f 和 r 分別為隊首尾指針，則進(jìn)行插入s 結(jié)點(diǎn)的操作時執(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é)點(diǎn)數(shù)為2個，度為2的結(jié)點(diǎn)數(shù)為1個，度為1的結(jié)點(diǎn)數(shù)為1個，那么度為0的結(jié)點(diǎn)數(shù)為 個。(A) 4 (B) 5 (C) 6 (D) 78. 在一棵二叉樹中，雙分支結(jié)點(diǎn)

3、數(shù)為15個，單分支結(jié)點(diǎn)數(shù)為32個，則葉結(jié)點(diǎn)數(shù)為 個。(A) 15 (B) 16 (C) 17 (D) 479. 一棵二叉樹結(jié)點(diǎn)數(shù)為18個，則其最小高度為 ，其最大高度為 。(A) 4,16 (B)5,18 (C) 6,18 (D) 3,1810. 一棵三叉樹結(jié)點(diǎn)數(shù)為50個，則其最小高度為 。 (A) 3 (B) 4 (C) 5 (D) 611. 由分別帶權(quán)為9，2，5，7的四個葉結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，則該樹的帶權(quán)路徑長度是 。 (A) 23 (B)37 (C) 44 (D) 4612. 已知10個數(shù)據(jù)元素（54，28，16，34，73，62，95，60，26，43），按照依次插入結(jié)點(diǎn)的方法生成

4、一棵二叉排序樹后，則查找值為62的結(jié)點(diǎn)所需比較的次數(shù)是3；在查找成功的情況下，查找每個元素的平均比較次數(shù)（又稱平均查找長度，即查找每個元素時平均比較的結(jié)點(diǎn)數(shù)）為 。 (A) 2.5 (B)3.2 (C) 2.6 (D) 2.9 13. 在一個無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的 倍。(A) 1/2 (B) 1 (C) 2 (D) 414. 有n個頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要 條邊。 (A) n (B) (n+1) (C) (n-1) (D) n/215. 有n個頂點(diǎn)和e條邊的無向圖中，若采用鄰接表表示，則表頭向量的大小為 條邊。(A) n (B) (n+1) (C) (n-1)

5、 (D) n/216. 在有向圖的鄰接表中，每個頂點(diǎn)的鄰接表鏈接著該頂點(diǎn)的所有 鄰接點(diǎn)；在有向圖的逆鄰接表中，每個頂點(diǎn)的鄰接表鏈接著該頂點(diǎn)的所有 鄰接點(diǎn)；(A) 出邊，入邊 (B) 入邊，出邊17. 對于一個具有n個頂點(diǎn)e條邊的的圖，若采用邊集數(shù)組表示，則邊集數(shù)組中的單元數(shù)至少為 個。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)

6、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

7、,V2,V4,V6,V3,V5)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的元素時

8、， 次比較后查找成功；當(dāng)二分查找值為47的元素時， 次比較后查找成功。 (A) 1，4 (B) 2，4 (C) 3，2 (D) 4，224. 在順序存儲的線性表A30上進(jìn)行順序查找的平均查找長度為 。 (A) 15 (B) 15.5 (C) 16 (D) 2025. 已知一個線性表為（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)

9、 2.3,7/6二、綜合應(yīng)用題：(2題，每題25分，共50分)1. 中綴表達(dá)式中，如果不規(guī)定運(yùn)算符的優(yōu)先級又不加括號，則運(yùn)算結(jié)果不唯一；后綴表達(dá)式中，不規(guī)定運(yùn)算符的優(yōu)先級又不需括號，就能得到唯一的運(yùn)算結(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)中什么原理

10、處理這一問題？（5分）2）請簡述并畫出示意描述圖。（20分）計算機(jī)網(wǎng)絡(luò)部分一、單項選擇題（每小題2分，總分22分）1、按照0比特插入/刪除方法規(guī)定，在兩個標(biāo)志字段為F的比特序列中，如果檢查出連續(xù)的（）1，不管后面的比特位是0或1，都需要增加一個0。A4 B. 5 C. 6 D. 82、在（）差錯控制方式中，只會重新傳輸那些出錯的數(shù)據(jù)幀。A.連續(xù)工作B.停止等待 C.選擇重發(fā)D.后退N幀3、PPP協(xié)議可按功能劃分為兩層，其中負(fù)責(zé)建立、配置不同的網(wǎng)絡(luò)層協(xié)議的是（）協(xié)議。A.PPTPB.HDLCC.LCPD.NCP4、常用的A 類私有地址是 （）。A. 55

11、 B. 55C. 55 D. 555、下面（）動態(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、如果有多個局域網(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 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,TFTPC.HTTP,DNSD.HTT