四川大學(xué)201515年874計算機(jī)真題解析

1、數(shù)據(jù)結(jié)構(gòu)：1.D刪除尾元素需找到其前驅(qū)節(jié)點(diǎn)，故需遍歷鏈表。循環(huán)雙鏈表找到目標(biāo)節(jié)點(diǎn)的時間復(fù)雜度為 0(1)。2.B空間復(fù)雜度概念題，查閱王道緒論。3 .C順序結(jié)構(gòu)的存取性質(zhì)，概念題。參見王道第二章4 .C 五個序列為：62354 62534 65234 26534 263545 .B王道原題，第一個元素是n,第二個元素是n-1 ,以此類推。6 .C按行優(yōu)先存儲，故應(yīng)該為A35為第四行第六個元素，每個占據(jù)4個存儲空間。故其應(yīng)該是第三十六個元素，取存儲單元的第一個，綜上 35*4+860=10007 .D首先根據(jù)后序序列得出C是根節(jié)點(diǎn)，其次再根據(jù)中序序列可知C的右子樹為空。在后續(xù)剩下的節(jié)點(diǎn)中(DAB

2、E)可知E是左子樹的根節(jié)點(diǎn)，在中序中參照上述邏輯可將 (DEBA汾為左 右子樹。以此類推即可得出答案，參見下圖。8 .B帶入公式即可。記憶題9 .C題干沒有固定，隨意選擇。現(xiàn)選擇 Prime算法，過程如下圖10 .A完全二叉樹中，度為一的節(jié)點(diǎn)個數(shù)，要么為 0要么為1.又n0=n2+1 ,即可求出n1=0.11 .A Y是葉子節(jié)點(diǎn)，訪問 Y之后，應(yīng)返回它的父節(jié)點(diǎn)，即為X。12.B哈夫曼樹沒有度為1的節(jié)點(diǎn)，又n0=n2+1 , n0+n2=199.哈夫曼樹的編碼字符，即為求 n0節(jié)點(diǎn)個數(shù)。綜上可得。13 .D此題即為求判定樹的樹高，直接代入公式。log2(100)+1 (符號為向下取整)14 .C

3、 A選項，B樹才會引起分裂整合。B選項，應(yīng)對其進(jìn)彳T中序遍歷。C選項，正確。D選項，若每個節(jié)點(diǎn)只有左或者右子樹(一條余線)，就會退化成線性結(jié)構(gòu)，此時時間復(fù)雜度為 O(n)15.B16.A17.D H(23)=6,T6=57,故采取二次探測，根據(jù)二次探測的序列1,-1,4,- 4(平方)，可得。18.B 408原題。王道樹和森林課后習(xí)題綜合應(yīng)用題1.用快速排序可以實現(xiàn)找第k小的數(shù)，時間復(fù)雜度為O(n)。#define Max 100int Search(int a,int n,int k)快速排序?qū)ふ覕?shù)組中第k小的元素int low,high,i,j,t;k-;low=0;high=n-1;do

4、 i=low; j=high; t=alow;/將alow作為樞軸元素do while(i<j&&t<aj)若當(dāng)前元素大于樞軸元素t,則將j向左移動比較下一元素j-;if(i<j)/若當(dāng)前元素小于或等于t,則將當(dāng)前元素存入 aj;ai+=aj;while(i<j&&t>=ai)/若當(dāng)前元素小于或等于樞軸元素t,則將i向右移動比較下一元素 i+; if(i<j)/ 若當(dāng)前元素大于樞軸元素,則將元素存入aj; aj-=ai; while(i<j);ai=t;/ 樞軸元素存入ai;if(i=k)/ 若找到第k 小元素 結(jié)束循環(huán)

5、break; if(i<k)/ 說明查找的元素在右半部分 low=i+1; else/ 說明查找的元素在左半部分 high=i-1; while(i!=k);return ak;/返回第k小元素的值也可以利用堆排序求解：先建立小頂堆，然后輸出k 個最小的元素。2.(1) . 若左孩子不為空則后繼結(jié)點(diǎn)為左孩子，若左孩子為空右孩子不為空則后繼結(jié)點(diǎn)右孩子，若左右子樹都為空則后繼結(jié)點(diǎn)為父結(jié)點(diǎn)(2)的網(wǎng)湃設(shè)珈灰的修T)彳0二"以。呦孑就伽屬尊F?礴曲/火(成況1-I叫)他也M ”成批px,若相(3)將王道書上的后續(xù)非遞歸算法中訪問結(jié)點(diǎn)的地方改為判斷結(jié)點(diǎn)指針是否等于 等則輸出棧里面的內(nèi)容并

6、結(jié)束循環(huán)。計算機(jī)網(wǎng)絡(luò)：1 .A概念題2 .D概念題3 .A ICMP是網(wǎng)絡(luò)層4 .B 最大接受窗口為2的n次方-15.B CDMA為信道復(fù)用技術(shù)； ALOHA是CSMA/CD的前身，但不是隨機(jī)爭用型；D令牌環(huán)網(wǎng)為輪次訪問6 .C IP協(xié)議為網(wǎng)絡(luò)層協(xié)議，提供不可靠服務(wù)。7 .A 波特率=log2(V),比特率為每秒傳輸?shù)谋忍財?shù)。比特率和波特率既有聯(lián)系，又有區(qū)別。比特率描述的是數(shù)據(jù)，波特率描述的是信號。我們知道，數(shù)據(jù)是用信號來表示的。如果一個信號碼元只能代表 1比特，那么波特率和比特率是相等的。如果一個碼元可以表示n個比特信息，那么比特率是波特率的n倍。8 .C王道上有原話。9 .A過程如下綜合應(yīng)

7、用題1.(1)應(yīng)用層：DNS服務(wù)器地址傳輸層：socket<IP，端口號網(wǎng)絡(luò)層：IP地址(2)應(yīng)用層加上HTTP協(xié)議頭傳輸層加上TCP協(xié)議頭網(wǎng)絡(luò)層加上IP協(xié)議頭(3)應(yīng)用層：HTTP協(xié)議t#求HTML文件，DNS協(xié)議將域名轉(zhuǎn)化為IP地址傳輸層：TCP傳輸數(shù)據(jù)，UDP建立DNS鏈接 網(wǎng)絡(luò)層：IP傳輸數(shù)據(jù)2.(1)可劃分為三個子網(wǎng)，A是一個，B和C是一個，D和E是一個子網(wǎng)。主機(jī) D的網(wǎng)絡(luò)地址60/28(2)IP地址范圍：7-0(除去已經(jīng)分配的 A的地址)(3)廣播地址為75 , D和E能收到廣播信

8、息。操作系統(tǒng)1.B A選項，相應(yīng)進(jìn)程由變?yōu)樽枞麘B(tài)，等待傳輸完成。C選項，有執(zhí)行態(tài)變?yōu)樽枞麘B(tài)。D從就緒態(tài)變?yōu)樽枞? .C概念題。3 .A概念題4 .A概念題5 .D 操作系統(tǒng)為電腦底層管理一切資源，JVM是java虛擬環(huán)境，java類庫是一些庫函數(shù)，java程序調(diào)用某些庫函數(shù)執(zhí)行程序。6.B A和D選項，短作業(yè)優(yōu)先都會產(chǎn)生饑餓，使長作業(yè)長時間得不到響應(yīng)。C選項，優(yōu)先級低的進(jìn)程的不打破相應(yīng)。7.B概念題，王道書中有詳細(xì)論述，fopen的過程。8.D A,執(zhí)行態(tài)轉(zhuǎn)化為就緒態(tài)。B,執(zhí)行態(tài)轉(zhuǎn)化為終止。C,轉(zhuǎn)化為阻塞態(tài)。9.A概念題10.B概念題11 .C 2586/1024=2 538,故應(yīng)該在第三個

9、頁面，在題中就是 2號頁面，對應(yīng)的塊號為10號，再加上偏移地址538. 1024*10+538=1077812 .無答案非搶占式短作業(yè)優(yōu)先，工作序列為P1,P3,P2. 7+(2+1)+(5+9) /3=8. 此為正確答案。13 .C 首先頁框為空，所以一共產(chǎn)生三次缺頁，分別把0， 1， 2 調(diào)換入頁框。再到第一次訪問 3 的時候，應(yīng)將0 置換出去，第三次訪問0 的時候應(yīng)將頁框內(nèi)的1 號頁面置換出去。至此 5 次缺頁已產(chǎn)生。14 .A 概念題15 .C 每個進(jìn)程都分配一臺打印機(jī)的時候，每個進(jìn)程都無法獲得足夠資源，執(zhí)行完畢，故產(chǎn)生死鎖。16 .A 當(dāng)前磁頭處于108，且往序號遞增方向移動，故第一個為110，此時方向固定，直到訪問到 195 之后，再返回。故可得出序列17 .A 概念題18 .B 概念題19 .C 通過瀏覽器登陸頁面，首先需要從鍵盤輸入網(wǎng)址。過程如下：中斷處理層序- 進(jìn)程調(diào)度- 系統(tǒng)調(diào)用- 瀏覽器20 .C 概念題21 .A B， 假設(shè)一種情況，進(jìn)程映射到同一塊內(nèi)存地址，增加內(nèi)存無意義。C， 無影響。D 增加抖動次數(shù)。22 .D 銀行家算法23 .D 就緒 -運(yùn)行 -等待。24 .B 概念題25 .B 概念題26 .D FA