答題說(shuō)明：

　　1.答題時(shí)間90分鐘，請(qǐng)注意把握時(shí)間;

　　2.試題分為四個(gè)部分：?jiǎn)雾?xiàng)選擇題(10題，20分)、不定向選擇題(4題，20分)、填空問(wèn)答(5題，40分)、綜合體(1題，20分);

　　3.其他一些亂七八糟的考試說(shuō)明。

　　一、單項(xiàng)選擇題

　　1.下列說(shuō)法不正確的是：(D)

　　A.SATA硬盤(pán)的速度速度大約為500Mbps/s

　　B.讀取18XDVD光盤(pán)數(shù)據(jù)的速度為1Gbps

　　C.前兆以太網(wǎng)的數(shù)據(jù)讀取速度為1Gpbs

　　D.讀取DDR3內(nèi)存數(shù)據(jù)的速度為100Gbps

　　解析：

　　DDR3內(nèi)存讀取速度約為1.6Gbps

　　2.(D)不能用于Linux中的進(jìn)程通信

　　A.共享內(nèi)存

　　B.命名管道

　　C.信號(hào)量

　　D.臨界區(qū)

　　3.設(shè)在內(nèi)存中有P1,P2,P3三道程序，并按照P1,P2,P3的優(yōu)先級(jí)次序運(yùn)行，其中內(nèi)部計(jì)算和IO操作時(shí)間由下表給出(CPU計(jì)算和IO資源都只能同時(shí)由一個(gè)程序占用)：

　　P1:計(jì)算60ms---》IO 80ms---》計(jì)算20ms

　　P2:計(jì)算120ms---》IO 40ms---》計(jì)算40ms

　　P3:計(jì)算40ms---》IO 80ms---》計(jì)算40ms

　　完成三道程序比單道運(yùn)行節(jié)省的時(shí)間是(C)

　　A.80ms

　　B.120ms

　　C.160ms

　　D.200ms

　　4.兩個(gè)等價(jià)線(xiàn)程并發(fā)的執(zhí)行下列程序，a為全局變量，初始為0，假設(shè)printf、++、--操作都是原子性的，則輸出不肯哪個(gè)是(A)

　　void foo() {

　　if(a <= 0) {

　　a++;

　　}

　　else {

　　a--;

　　}

　　printf("%d", a);

　　}

　　A.01

　　B.10

　　C.12

　　D.22

　　5.給定fun函數(shù)如下，那么fun(10)的輸出結(jié)果是(C)

　　int fun(int x) {

　　return (x==1) ? 1 : (x + fun(x-1));

　　}

　　A.0

　　B.10

　　C.55

　　D.3628800

　　6.在c++程序中，如果一個(gè)整型變量頻繁使用，最好將他定義為(D)

　　A.auto

　　B.extern

　　C.static

　　D.register

　　7.長(zhǎng)為n的字符串中匹配長(zhǎng)度為m的子串的復(fù)雜度為(B)

　　A.O(N)

　　B.O(M+N)

　　C.O(N+LOGM)

　　D.O(M+LOGN)

　　解析： KMP算法

　　8.判斷一包含n個(gè)整數(shù)a[]中是否存在i、j、k滿(mǎn)足a[i] + a[j] = a[k]的時(shí)間復(fù)雜度為()

　　A. O(n3)

　　B.O(n2lgn)

　　C.O(n2)

　　D.O(nlgn)

　　解析：O(N2)的算法能想一大堆，雖然最終我選的C，比如說(shuō)用hash的話(huà)，三維遍歷可以輕松編程二維遍歷，但是總感覺(jué)是不是應(yīng)該有nlgn的算法。

　　9.三次射擊能中一次的概率是0.95，請(qǐng)問(wèn)一次射擊能中的概率是多少?(A)

　　A.0.63

　　B.0.5

　　C.**

　　D.0.85

　　10.下列序排算法中最壞復(fù)雜度不是n(n-1)/2的是_(D)

　　A.快速序排 B.冒泡序排 C.直接插入序排 D.堆序排

　　二、不定向選擇題

　　1.阻塞、就緒、運(yùn)行的三態(tài)轉(zhuǎn)換

　　2.一個(gè)棧的入棧數(shù)列為：1、2、3、4、5、6;下列哪個(gè)是可能的出棧順序。(選項(xiàng)不記得)

　　3.下列哪些代碼可以使得a和b交換數(shù)值。(選項(xiàng)不記得)

　　4.A和B晚上無(wú)聊就開(kāi)始數(shù)星星。每次只能數(shù)K個(gè)(20<=k<=30)A和B輪流數(shù)。最后誰(shuí)把星星數(shù)完誰(shuí)就獲勝，那么當(dāng)星星數(shù)量為多少時(shí)候A必勝?

　　A.2013 B.2886 C.4026 D......E.....(選項(xiàng)不記得)

　　三、填空問(wèn)答題

　　1.給你一個(gè)整型數(shù)組A[N]，完成一個(gè)小程序代碼(20行之內(nèi))，使得A[N]逆向，即原數(shù)組為1，2，3，4，逆向之后為4，3，2，1

　　void revense(int * a,int n) {

　　}

　　2.自選調(diào)度方面的問(wèn)題，題目很長(zhǎng)，就是給你三個(gè)線(xiàn)程，分別采用先來(lái)先分配的策略和最短執(zhí)行之間的調(diào)度策略，然后計(jì)算每個(gè)線(xiàn)程從提交到執(zhí)行完成的時(shí)間。題目實(shí)在太長(zhǎng)，還有幾個(gè)表格�？疾斓氖遣僮飨到y(tǒng)里面作業(yè)調(diào)度算法先進(jìn)先出和最短作業(yè)優(yōu)先。

　　3.有個(gè)苦逼的上班族，他每天忘記定鬧鐘的概率為0.2，上班堵車(chē)的概率為0.5，如果他既沒(méi)定鬧鐘上班又堵車(chē)那他遲到的概率為1.0，如果他定了鬧鐘但是上班堵車(chē)那他遲到的概率為0.9，如果他沒(méi)定鬧鐘但是上班不堵車(chē)他遲到的概率為0.8，如果他既定了鬧鐘上班又不堵車(chē)那他遲到的概率為0.0，那么求出他在60天里上班遲到的期望。

　　4.戰(zhàn)報(bào)交流：戰(zhàn)場(chǎng)上不同的位置有N個(gè)戰(zhàn)士(n>4)，每個(gè)戰(zhàn)士知道當(dāng)前的一些戰(zhàn)況，現(xiàn)在需要這n個(gè)戰(zhàn)士通過(guò)通話(huà)交流，互相傳達(dá)自己知道的戰(zhàn)況信息，每次通話(huà)，可以讓通話(huà)的雙方知道對(duì)方的所有情報(bào)，設(shè)計(jì)算法，使用最少的通話(huà)次數(shù)，是的戰(zhàn)場(chǎng)上的n個(gè)士兵知道所有的戰(zhàn)況信息，不需要寫(xiě)程序代碼，得出最少的通話(huà)次數(shù)。

　　5.有N個(gè)人，其中一個(gè)明星和n-1個(gè)群眾，群眾都認(rèn)識(shí)明星，明星不認(rèn)識(shí)任何群眾，群眾和群眾之間的認(rèn)識(shí)關(guān)系不知道，現(xiàn)在如果你是機(jī)器人R2T2，你每次問(wèn)一個(gè)人是否認(rèn)識(shí)另外一個(gè)人的代價(jià)為O(1)，試設(shè)計(jì)一種算法找出明星，并給出時(shí)間復(fù)雜度(沒(méi)有復(fù)雜度不得分)。

　　解答：這個(gè)問(wèn)題等價(jià)于找未知序列數(shù)中的最小數(shù)，我們將reg這個(gè)函數(shù)等價(jià)為以下過(guò)程：，如果i認(rèn)識(shí)j，記作i大于等于j,同樣j不一定大于等于i,滿(mǎn)足要求，i不認(rèn)識(shí)j記作i

　　int finds(S,N)

　　{

　　int flag=0;//用于判定是否有明星，即當(dāng)前最小數(shù)另外出現(xiàn)幾次

　　int temp=0;//存放最小數(shù)在S中的位置

　　for(i=1;i

　　{

　　if(!reg(S[i],S[temp])//如果temp標(biāo)號(hào)的數(shù)小于i標(biāo)號(hào)的數(shù)