第一部分 單選題(前10題，每題2分;后10題，每題3分。選對(duì)得滿分，選錯(cuò)倒扣1分，不選得0分)
1、一次內(nèi)存訪問(wèn)，SSD硬盤(pán)訪問(wèn)和SATA硬盤(pán)隨機(jī)訪問(wèn)的時(shí)間分別是()
A、幾微秒，幾毫秒，幾十毫秒 B、幾十納秒，幾十微秒，幾十毫秒
C、幾十納秒，幾十微秒，幾十毫秒 D、幾微秒，幾十微秒，幾十毫秒
2、8進(jìn)制數(shù)256，轉(zhuǎn)化成7進(jìn)制數(shù)是(B)
A、356 B、336 C、338 D、346
3、某網(wǎng)絡(luò)的IP地址空間為192.168.5.0/24，采用定長(zhǎng)子網(wǎng)劃分，子網(wǎng)掩碼為255.255.255.248，則該網(wǎng)絡(luò)的最大子網(wǎng)個(gè)數(shù)、每個(gè)子網(wǎng)內(nèi)最大可分配地址個(gè)數(shù)各位(C)
A、8,32 B、32,8 C、32,6 D、8,30
4、以下關(guān)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)說(shuō)法錯(cuò)誤的是(A)
A、查找節(jié)點(diǎn)時(shí)鏈?zhǔn)酱鎯?chǔ)比順序存儲(chǔ)快
B、每個(gè)節(jié)點(diǎn)是由數(shù)據(jù)域和指針域組成
C、比順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)密度小
D、邏輯上不相鄰的節(jié)點(diǎn)物理上可能相鄰
5、假定一個(gè)二維數(shù)組的定義語(yǔ)句為“int a[3][4]={{3,4},{2,8,6}};”，則元素a[1][2]的值為(A)
A、6 B、4 C、2 D、8
6、下面函數(shù)的功能是(C)
int fun (char s)
{
char p=s;
while(p++);
return p-s-1;
}
A、計(jì)算字符串的位(bit)數(shù) B、復(fù)制一個(gè)字符串
C、求字符串的長(zhǎng)度 D、求字符串存放的位置
7、判斷有向圖是否存在回路，利用(A)方法最佳
A、拓?fù)渑判?B、求最短路徑
C、求關(guān)鍵路徑 D、廣度優(yōu)先遍歷
8、依次讀入數(shù)據(jù)元素序列{a,b,c,d,e,f,g}進(jìn)棧，元素進(jìn)棧或出棧順序是未知的，下列序列中，不可能成為�？諘r(shí)彈出的元素構(gòu)成序列的有(D)
A、{d,e,c,f,b,g,a} B、{c,d,b,e,f,a,g} C、{e,f,d,g,c,b,a} D、{f,e,g,d,a,c,b}
9、下列有關(guān)圖的遍歷說(shuō)法中，不正確的是(C)
A、有向圖和無(wú)向圖都可以進(jìn)行遍歷操作
B、基本遍歷算法兩種：深度遍歷和廣度遍歷
C、圖的遍歷必須用遞歸實(shí)現(xiàn)
D、圖的遍歷算法可以執(zhí)行在有回路的圖中
10、在16位機(jī)器上跑下列foo函數(shù)的結(jié)果是(B)
void foo()
{
int i = 65536;
cout << i <<”,”;
i = 65535;
cout << i;
}
A、-1,65535 B、0,-1 C、-1,-1 D、0,65535
11、有一段年代久遠(yuǎn)的C++代碼，內(nèi)部邏輯復(fù)雜，現(xiàn)在需要利用其實(shí)現(xiàn)一個(gè)新的需求，假定有以下可行的方案，應(yīng)當(dāng)優(yōu)先選擇(D)
A、修改老代碼的接口，滿足新的需求
B、將老代碼拋棄，自己重新實(shí)現(xiàn)類似的邏輯
C、修改老代碼的內(nèi)部邏輯，滿足新的需求
D、在這段代碼之外寫(xiě)一段代碼，調(diào)用該代碼的一些模塊，完成新功能需求
12、在5個(gè)頁(yè)框上使用LRU頁(yè)面替換算法，當(dāng)頁(yè)框初始為空時(shí)，引用序列為0、1、7、8、6、2、3、7、2、9、8、1、0、2，系統(tǒng)將發(fā)生(C)次缺頁(yè)
A、13 B、12 C、11 D、8
分析：缺頁(yè)為：0、1、7、8、6、2、3、9、8、1、0，共11次
緩沖區(qū)可以設(shè)置為最小(A)
A、18M B、12M C、6M D、24M
分析：
TCP協(xié)議原理：TCP每發(fā)送一個(gè)報(bào)文段，就啟動(dòng)一個(gè)定時(shí)器，如果在定時(shí)器超時(shí)之后還沒(méi)有收到ACK確認(rèn)，就重傳該報(bào)文。
如圖所示，數(shù)據(jù)包由A的緩沖區(qū)發(fā)往B，B在收到數(shù)據(jù)包以后，回發(fā)一個(gè)ACK確認(rèn)包給A，之后A將該數(shù)據(jù)包從緩沖區(qū)釋放。因此，該數(shù)據(jù)包會(huì)一直緩存在A的緩沖區(qū)，直到一個(gè)ACK確認(rèn)為止。題目要求在100s內(nèi)發(fā)送100GB數(shù)據(jù)，網(wǎng)絡(luò)的傳輸速率至少是1G/s，某個(gè)數(shù)據(jù)包n在A中緩存的時(shí)間就是數(shù)據(jù)包n從A到B，再加上該數(shù)據(jù)包的ACK從B到A的時(shí)間：21500km/(2108m/s)=1.510-2s，該段時(shí)間A中緩存的數(shù)據(jù)量至少是1G/s1.510-2s約為15M
14、有3個(gè)節(jié)點(diǎn)的二叉樹(shù)可能有(A)種
A、5 B、13 C、12 D、15
15、設(shè)某文件經(jīng)內(nèi)排序后得到100個(gè)初始?xì)w并段(初始順串)，若使用多路歸并排序算法，且要求三趟歸并完成排序，問(wèn)歸并路數(shù)最少為(D)
A、8 B、7 C、6 D、5
分析：m個(gè)元素k路歸并的歸并趟數(shù)s=logk(m)，代入數(shù)據(jù)：logk(100)?3
16、一個(gè)優(yōu)化的程序可以生成一n個(gè)元素集合的所有子集，那么該程序的時(shí)間復(fù)雜度是(B)
A、O(n!) B、O(2n) C、O(n2) D、O(n log n)
17、快速排序在已經(jīng)有序的情況下效率最差，復(fù)雜度為(B)
A、O(n log n) B、O(n2) C、O(n1.5) D、O(n2 log n)
18、從一副牌(52張，不含打小怪)里抽出兩張牌，其中一紅一黑的概率是(D)
A、25/51 B、1/3 C、1/2 D、26/51
分析：52張牌從中抽兩張，就是C522種情況，一紅一黑是C261 C261種情況，概率P = C261 C261 / C522 =26/51
19、有一堆石子共100枚，甲乙輪流從該堆中取石子，每次可取2、4或6枚，若取得最后的石子的玩家為贏，若甲先取，則(C)
A、誰(shuí)都無(wú)法取勝 B、乙必勝 C、甲必勝 D、不確定
分析：先取的人只需要保證最后剩8枚就勝了。而要保證最后剩8枚，則必須要保證每一個(gè)回合內(nèi)取的數(shù)是一個(gè)可控的固定數(shù)，顯然這個(gè)數(shù)字是8，所以只需要保證第一次取完后，剩下的數(shù)字是8的倍數(shù)，就一定能勝。100除以8余數(shù)為4，故而，甲先取4枚，之后每一個(gè)回合所取數(shù)與上一個(gè)回合乙所取數(shù)之和為8，就能保證必勝。
20、現(xiàn)有一完全的P2P共享協(xié)議，每次兩個(gè)節(jié)點(diǎn)通訊后都能獲取對(duì)方已經(jīng)獲取的全部信息，現(xiàn)在使得系統(tǒng)中每個(gè)節(jié)點(diǎn)都知道所有節(jié)點(diǎn)的文件信息，共17個(gè)節(jié)點(diǎn)，假設(shè)只能通過(guò)多次兩個(gè)對(duì)等節(jié)點(diǎn)之間通訊的方式，則最少需要(C)次通訊
A、32 B、31 C、30 D、29
分析：如上圖1所示，假設(shè)有5個(gè)節(jié)點(diǎn)，按連線1、2、3、4通訊之后，節(jié)點(diǎn)4和5就掌握了所有節(jié)點(diǎn)的信息，之后，1、2、3節(jié)點(diǎn)只需跟4或5任一節(jié)點(diǎn)通訊一次即連線5、6、7就可保證每個(gè)節(jié)點(diǎn)都知道所有節(jié)點(diǎn)的信息，總的通訊次數(shù)是(n-1)+(n-2)=2n-3次。
如果將所有節(jié)點(diǎn)分成兩組，如圖2所示，兩組中的節(jié)點(diǎn)分別按連線1-8順序通訊之后，節(jié)點(diǎn)4和5就掌握了1-5所有節(jié)點(diǎn)的信息，節(jié)點(diǎn)9和0就掌握了6-0所有節(jié)點(diǎn)的信息，再按連線9、10通訊之后，節(jié)點(diǎn)4、5、9、0就掌握了1-0所有節(jié)點(diǎn)的信息，剩下的節(jié)點(diǎn)只需跟4、5、9、0任一節(jié)點(diǎn)通訊一次就可保證每個(gè)節(jié)點(diǎn)知道所有節(jié)點(diǎn)信息，和圖1相比，多了9和10兩次通訊，總的通訊次數(shù)是(2n1-3)+(2n2-3)+2=2n-4次(n1和n2分別表示分組中元素個(gè)數(shù))。
分3組的情況是(2n1-3)+(2n2-3)+(2n3-3)+6=2n-3次
分4組的情況是(2n1-3)+(2n2-3)+(2n3-3)+(2n4-3)+8=2n-4次
第二部分 不定項(xiàng)選擇(每題五分，每題有1-5個(gè)正確選項(xiàng)，完全正確計(jì)5分，漏選計(jì)2分不選計(jì)0分，多選、錯(cuò)選計(jì)-2分)
21、2-3樹(shù)是一種特殊的樹(shù)，它滿足兩個(gè)條件：
(1)每個(gè)內(nèi)部節(jié)點(diǎn)有兩個(gè)或三個(gè)子節(jié)點(diǎn);
(2)所有的葉節(jié)點(diǎn)到根的路徑長(zhǎng)度相同;
如果一顆2-3樹(shù)有9個(gè)葉節(jié)點(diǎn)，下列數(shù)量個(gè)非葉節(jié)點(diǎn)的2-3樹(shù)可能存在的有(BE)
A、8 B、7 C、6 D、5 E、4
分析：根據(jù)條件(2)，葉節(jié)點(diǎn)只能在同一層，根據(jù)條件(1)，上一層的父節(jié)點(diǎn)只能是3個(gè)或4個(gè)，只能是如下圖所示的兩種結(jié)果
22、下列有關(guān)進(jìn)程的說(shuō)法中，錯(cuò)誤的是(ABC)
A、進(jìn)程與程序是一億對(duì)應(yīng)的 B、進(jìn)程與作業(yè)時(shí)一一對(duì)應(yīng)的
C、進(jìn)程是靜態(tài)的 D、進(jìn)程是動(dòng)態(tài)的過(guò)程
