前端程序員面試分類真題20

前端程序員面試分類真題20一、單項選擇題1.

數(shù)據(jù)結(jié)構(gòu)從邏輯上分為______兩大類A.順序結(jié)構(gòu)，鏈?zhǔn)浇Y(jié)構(gòu)B.靜態(tài)結(jié)構(gòu)，動態(tài)結(jié)構(gòu)C.初等結(jié)構(gòu)，構(gòu)造型結(jié)構(gòu)D.線性結(jié)構(gòu)，非線性結(jié)構(gòu)正確答案：D（江南博哥）[解析]數(shù)據(jù)的邏輯結(jié)構(gòu)指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)，其中的邏輯關(guān)系是指數(shù)據(jù)元素之間的前后關(guān)系，而與它們在計算機(jī)中的存儲位置無關(guān)。通常情況下，數(shù)據(jù)的邏輯結(jié)構(gòu)分以下兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性結(jié)構(gòu)是指該結(jié)構(gòu)中的結(jié)點之間存在一對一的關(guān)系，其特點是開始結(jié)點和終端結(jié)點都是唯一的，除了開始結(jié)點和終端結(jié)點外，其余結(jié)點都有且僅有一個直接前驅(qū)，有且僅有一個直接后繼，此類型的存儲結(jié)構(gòu)有：順序表(數(shù)組)、鏈表、棧結(jié)構(gòu)或隊列結(jié)構(gòu)等。非線性結(jié)構(gòu)又包括集合、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)，特點是數(shù)據(jù)元素之間存在一個對多個或多個對多個的關(guān)系，其中集合是一種關(guān)系極為松散的結(jié)構(gòu)。

數(shù)據(jù)的存儲方法有4種：順序存儲方法、鏈接存儲方法、索引存儲方法和散列存儲方法。

(1)順序存儲方法：它是把邏輯上相鄰的結(jié)點存儲在物理位置相鄰的存儲單元里，結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲表示稱為順序存儲結(jié)構(gòu)，通常借助程序語言的數(shù)組描述。

(2)鏈接存儲方法：它不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰，結(jié)點間的邏輯關(guān)系是由附加的指針字段表示。由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)，通常借助于程序語言的指針類型描述。

(3)索引存儲方法：除建立存儲結(jié)點信息外，還建立附加的索引表來標(biāo)識結(jié)點的地址。組成索引表的索引項由結(jié)點的關(guān)鍵字和地址組成。如果每個結(jié)點在索引表中都有一個索引項，則該索引表稱之為稠密索引。如果一組結(jié)點在索引表中只對應(yīng)一個索引項，則該索引表稱為稀疏索引。

(4)散列存儲方法：就是根據(jù)結(jié)點的關(guān)鍵字直接計算出該結(jié)點的存儲地址。

通過以上分析可知，選項D正確。

2.

以下對順序文件的描述中，錯誤的是______A.插入新的記錄時只能加在文件末尾B.存取第i個記錄，必須先搜索在它之前的i-1個記錄C.如要更新文件中的記錄，必須將整個文件復(fù)制D.順序文件中物理記錄的順序和邏輯記錄的順序不一致正確答案：D[解析]順序文件是指按記錄進(jìn)入文件的先后順序存放，其邏輯順序和物理順序一致的文件。一切存儲在順序存取存儲器(如磁帶)上的文件，都只能是順序文件。

對于選項A，插入新記錄時不能插入到已經(jīng)有順序的文件中間，只能在末尾。所以，選項A正確。

對于選項B，如果查找第i個記錄，必須從頭開始找起，符合順序表的性質(zhì)。所以，選項B正確。

對于選項C，如果要更新，必須復(fù)制整個文件后再更新，然后再放到另外一塊順序存儲器上。所以，選項C正確。

對于選項D，順序記錄的順序和邏輯記錄的順序是一致的。所以，選項D錯誤。

因此，本題的答案為D。

3.

下列數(shù)據(jù)結(jié)構(gòu)不是多型數(shù)據(jù)類型的是______A.堆B.棧C.字符串D.有向圖正確答案：C[解析]要想選出正確答案，就需要弄明白什么是多型數(shù)據(jù)類型?一種抽象數(shù)據(jù)類型的操作可用于多種具體數(shù)據(jù)類型的操作，這就是多型數(shù)據(jù)類型。簡單點說，多型有點類似于面向?qū)ο蟮哪０?，就是?shù)據(jù)元素的類型不確定。本題中，堆、棧和有向圖中的數(shù)據(jù)元素類型是不確定的，所以，選項A、選項B和選項D正確。字符串的每個元素始終都是字符(char)，而不會是別的類型，所以，字符串不是多型數(shù)據(jù)類型，選項C錯誤。

4.

以下關(guān)于數(shù)據(jù)結(jié)構(gòu)的描述中，錯誤的是______A.紅黑樹插入操作的平均時間復(fù)雜度為O(logn)，最壞時間復(fù)雜度為O(logn)B.B+樹插入操作的平均時間復(fù)雜度為O(logn)，最壞時間復(fù)雜度為O(logn)C.Hash插入操作的平均時間復(fù)雜度為O(logn)，最壞時間復(fù)雜度為O(n)D.排序鏈表插入操作的平均時間復(fù)雜度為O(n)，最壞時間復(fù)雜度為O(n)正確答案：C[解析]對于選項A與選項B，紅黑樹和B+樹插入操作的平均時間復(fù)雜度都為O(logn)，最壞時間復(fù)雜度為O(logn)。所以，選項A與選項B正確。

對于選項C，散列表存儲的是鍵值對，其查找的時間復(fù)雜度與元素數(shù)量多少無關(guān)。散列表在查找元素時是通過計算哈希碼值來定位元素的位置從而直接訪問元素的，因此，散列表的插入、刪除和查找等操作的時間復(fù)雜度都是O(l)。所以，選項C錯誤。

對于選項D，排序鏈表的插入操作較為復(fù)雜，需要先查找位置，再執(zhí)行插入，其插入的時間復(fù)雜度不是O(l)，而是O(n)，而且，其平均時間復(fù)雜度為O(n)，最壞時間復(fù)雜度也為O(n)。所以，選項D正確。

因此，本題的答案為C。

5.

實驗高中的小明暗戀女神同學(xué)已經(jīng)三年了，高考結(jié)束后，小明決定向女神同學(xué)表白。這天，小明來到女神樓下等待女神的出現(xiàn)，時間一分一秒地流逝，兩個多小時過去了，女神還沒有出現(xiàn)。小明看了下表，時針和分針的位置正好跟開始等的時候互換，請問小明一共等了女神______分鐘A.165B.150C.172D.166正確答案：D[考點]邏輯題數(shù)學(xué)計算[解析]根據(jù)題目中的描述，可以畫一個表示時針與分針的圖例，如下圖所示。

時針與分針互換

假設(shè)小明開始等待女神的那一時刻時針與分針的夾角為θ弧度，那么，等到時針與分針正好互換位置時，時針走過了θ弧度。而由于分針轉(zhuǎn)動一圈表示的時間為一個小時，鐘表一圈是一個圓，表示的弧度值為2π，分針因為要轉(zhuǎn)若干圈才能到達(dá)時針的位置，記分鐘所轉(zhuǎn)圈數(shù)為n，此時分針轉(zhuǎn)過的角度則為(2πn-θ)弧度。

題目強(qiáng)調(diào)，“時間一分一秒地流逝，兩個多小時過去了，女神還沒有出現(xiàn)”，通過這條信息可知，分針轉(zhuǎn)了2到3圈，接近3圈，此時的n值取3。所以，時針轉(zhuǎn)過的角度值為θ，分針轉(zhuǎn)過的角度值為2π×3-θ=6π-θ。

對于時針而言，2π代表一圈，即12個小時，那么弧度θ表示的時間值為12×θ/2π小時；對于分針而言，2π代表一圈，即60分鐘，那么(6π-θ)表示的是60×(6π-θ)/2π分鐘。由于時鐘走過的時間值與分鐘走過的時間值所代表的時間量是一個量，故而二者是相等的，由此可以構(gòu)建如下等式：

(12θ/2π)×60=60×(6π-θ)/2π

求解上述等式可知，θ=6π/13，即小明等待的時間反映在鐘表上為6π/13弧度值。所以，小明一共等了12×(6π/13)/2π小時，即36/13小時，合166分鐘。因此，選項D正確。

6.

如果等式12×25=311成立，那么使用的是______進(jìn)制運算A.7B.8C.9D.11正確答案：C[考點]邏輯題數(shù)學(xué)計算[解析]當(dāng)進(jìn)行乘法運算時，無論是什么進(jìn)制的數(shù)進(jìn)行運算，其基本方法都是相同的，以十進(jìn)制數(shù)的計算為例：2×5=10。如果是七進(jìn)制，那么運算結(jié)果最后一位一定是10%7=3，相乘后進(jìn)位值為10/7=1。同理，如果是八進(jìn)制，相乘結(jié)果最后一位一定等于10%8=2。如果是九進(jìn)制，最后一位一定是10%9=1。如果是十一進(jìn)制，最后一位一定是10%11=A(類似于十六進(jìn)制中，使用A表示數(shù)字10)。

本題中，計算結(jié)果為311，最后一位為1，可以排除選項A、選項B和選項D，只有選項C滿足題意，所以，選項C正確。

7.

平面內(nèi)一共有11個點，由它們連成48條不同的直線，由這些點可連成的三角形個數(shù)為______A.162B.158C.160D.165正確答案：C[考點]邏輯題數(shù)學(xué)計算[解析]題目告知，平面內(nèi)有11個點，如果這些點中任意3個點都沒有共線，那么一共有C(11，2)=55種情況。但是根據(jù)題意可知，這11個點只能連接成48條直線，那么這些點中必定有3點共線以及3點以上的共線，一共55-48=7種情況。

而這7種3點共線的情況又可以劃分為以下多種情況：

(1)假設(shè)只有3點共線，令3點共線的直線有x條，那么可以組成的直線在55的基礎(chǔ)上應(yīng)該除去這些情況，即C(11，2)-x×C(3，2)+1=48，由于解算出來的x值不是整數(shù)，所以，此種情況不滿足條件。

(2)假設(shè)只有4點共線，令4點共線的直線有x條，那么可以組成的直線在55的基礎(chǔ)上應(yīng)該除去這些情況，即C(11，2)-x×C(4，2)+1=48，由于解算出來的x值不是整數(shù)，所以，此種情況不滿足條件。

(3)假設(shè)只有n(n＞4)點共線，方法同上，也無法滿足條件。

(4)若同時有3點共線及4點共線兩種情況，令3點共線的直線有x條，4點共線的有y條，則有C(11，2)-xC(3，2)-yC(4，2)+x+y=48，即2x+5y=7，所以，x=1，y=1。這11個點中，必定有一組3點共線，并且還有一組4點共線。由于3點共線、4點共線都不能組成三角形，所以，這11個點能組成的三角形的個數(shù)為C(11，3)-C(3，3)-C(4，3)=165-1-3=160(本題不考慮三角形兩邊之和大于第三邊的要求)。

(5)若同時有3點共線、4點共線及5點共線三種情況，分析方法相同。計算可知方程無解，超過以上情況的多點共線情況也不符合題意。

所以，本題的答案為160，選項C正確。

8.

1，4，5，6，7，9，11，______A.8B.12C.15D.100正確答案：C[考點]邏輯題數(shù)學(xué)計算[解析]本題中，最重要的解題方法就是找出數(shù)列的規(guī)律，從而推導(dǎo)出最后一個數(shù)是多少。通過研究已有的7個數(shù)，不難發(fā)現(xiàn)：第二項+第七項=4+11=15，第三項+第六項=5+9=14，第四項+第五項=6+7=13，兩個數(shù)的和依次遞減。可以推出這樣一個結(jié)論：第一項+第八項=16，因為第一項的值為1，所以，第八項=16-1=15。因此，選項C正確。

9.

8，8，12，24，60，______A.90B.180C.120D.240正確答案：B[考點]邏輯題數(shù)學(xué)計算[解析]本題是一個數(shù)列找規(guī)律的題目，經(jīng)常出現(xiàn)在小學(xué)奧數(shù)或是高中生升學(xué)考試中，考察求職者的邏輯思維能力。

雖然此題中相鄰項的商并不是一個常數(shù)，但它們是按照一定規(guī)律排列的。不難發(fā)現(xiàn)，本題中后一項除以前一項的結(jié)果構(gòu)成一個等差數(shù)列，公差1/2，即除第一項以外的每一項都等于其前一項的值乘以(1+0.5×n)，n的值是從0開始的自然數(shù)。具體為：8×1=8，8×1.5=12，12×2=24，24×2.5=60，根據(jù)這一規(guī)律，60后面的數(shù)值應(yīng)為60×3=180。所以，選項B正確。

10.

有A、B、C三個人負(fù)責(zé)裝修房子，對于一面墻，單獨工作時，A需要花費18小時砌好，B需要花費24小時，C需要花費30小時?，F(xiàn)A、B、C三人順序輪流砌墻，每人工作1小時換班，完工時，B總共工作了______A.8小時B.7小時44分C.7小時D.6小時48分正確答案：B[考點]邏輯題數(shù)學(xué)計算[解析]根據(jù)題目意思可知，A工作1小時完成整個工程量的1/18，B工作1小時完成整個工程量的1/24，C工作1小時完成整個工程量的1/30。由于A、B、C三個人順序輪流砌，每人工作1小時換班，所以，A、B、C三個人每3小時的工程量為1/18+1/24+1/30，合計47/360。而360除以47得7余31，也就是說，三個人一共工作了7個3小時后，還剩余31/360的工作量未能完成。此時輪到A工作，A每小時完成整個工程量的1/18，所以，剩下31/360-1/18=11/360的工程量需要B來完成。完成11/360的工程量，B需要花費的時間為11×24/360=11/15小時。由此可知，B的工作時間為7小時+(11/15)×60分鐘，即7小時44分。因此，選項B正確。

11.

假如何老師看到擺鐘的時間是17時32分，那么此時時針跟分針的最小夾角是______A.25度B.26度C.28度D.32度正確答案：B[考點]邏輯題數(shù)學(xué)計算[解析]首先，選定一個參考物，以12點正點時刻作為參考量，按順時針計算算出時針與該參考量的偏移量，然后算出分針與該參考量的偏移量，二者相減可以求出時針與分針的夾角。

眾所周知，時針行走一圈為360°，合12個小時，所以，時針每小時轉(zhuǎn)動的角度值為360°/12=30°，下午17:32的時針偏移量為30°×(5+32/60)=166°，即時針與12點正點時刻時的夾角為166°。分針每行走一圈為360°，合1個小時(60分鐘)，所以，分針每分鐘轉(zhuǎn)動的角度值為360°/60=6°，下午17:32的分針偏移量為6×32=192°。

時針與分針偏移量的差值即為所求解，192°-166°=26°。所以，選項B正確。

12.

若被除數(shù)為二進(jìn)制數(shù)110110，除數(shù)為二進(jìn)制數(shù)111，則余數(shù)為______A.100B.101C.110D.111正確答案：B[考點]邏輯題數(shù)學(xué)計算[解析]本題可以首先將二進(jìn)制轉(zhuǎn)換為十進(jìn)制，進(jìn)行求解后，再轉(zhuǎn)換為二進(jìn)制。

二進(jìn)制數(shù)110110對應(yīng)的十進(jìn)制數(shù)為32+16+4+2=54，二進(jìn)制數(shù)111對應(yīng)的十進(jìn)制數(shù)為4+2+1=7，計算54%7得到的結(jié)果為5，用二進(jìn)制表示為101。所以，選項B正確。

13.

87的100次方除以7的余數(shù)是______A.1B.2C.3D.4正確答案：D[考點]邏輯題數(shù)學(xué)計算[解析]對于取余運算符%，滿足如下等式關(guān)系：(a×b)%c=(a%c)×(b%c)%c，所以，(87^100)%7=(87%7)^100%7=(3^100)%7。對于任意n(n≥0)，(3^n)%7只存在6種可能，依次為1、3、2、6、4和5，根據(jù)等式遞推可得到：87^100%7=3^100%7=9^50%7=2^50%7=32^10%7=4^10%7=16^5%7=2^5%7=32%7=4。所以，選項D正確。

14.

計算三個稠密矩陣A、B、C的乘積ABC，假定三個矩陣的尺寸分別為m×n、n×p和p×q，且m＜n＜p＜q，以下計算順序中，效率最高的是______A.(AB)CB.A(BC)C.(AC)BD.(BC)A正確答案：A[考點]邏輯題數(shù)學(xué)計算[解析]根據(jù)矩陣運算知識，可以排除選項C與選項D，因為矩陣A與矩陣B相乘，矩陣A的列數(shù)必須與矩陣B的行數(shù)相等。

對于選項A與選項B，一個m×n的矩陣A乘以nXq的矩陣B，會用矩陣A的第一行，乘以矩陣B的第一列并相加。這一運算需要耗費n次乘法以及n-1次加法，矩陣B有q列，矩陣A有m行，所以，AxB的復(fù)雜度為m×(2n-1)×q。

根據(jù)上面的分析可知，選項A的復(fù)雜度為m×(2n-1)×p+m×(2p-1)×q，而選項B的復(fù)雜度為m×(2n-1)×q+n×(2p-1)×q，很顯然，選項A的效率高于選項B。所以，選項A正確。

15.

小胖欲用積分兌換加多寶，兌換的規(guī)則是每10個積分可以兌換一瓶加多寶并返還5個積分。小胖現(xiàn)有200個積分，那么他最多可以兌換到的加多寶數(shù)量是______A.38B.39C.40D.41正確答案：B[考點]邏輯題數(shù)學(xué)計算[解析]本題中，根據(jù)兌換規(guī)則，每10個積分可以兌換一瓶加多寶并返還5個積分，換一個角度看，每瓶加多寶就只需要5個積分即可。表面上看，200個積分可以換200/5=40個加多寶，但是這忽略了一個前提，就是小胖手中必須至少有10個積分的時候，加多寶才能兌換，并返回5個積分，否則5個積分等價于一瓶加多寶這條結(jié)論就不成立。所以，200個積分的前190個積分可以按照每5個積分換一瓶加多寶換取，此時可以換取190/5=38瓶。當(dāng)小胖手中還有最后10個積分時，他還可以兌換一瓶加多寶，同時返還5個積分，而最后剩下的5個積分是無法單獨兌換加多寶的，因此，小胖手中的200個積分，最多可以兌換到的加多寶數(shù)量為39瓶。所以，選項B正確。

16.

店主銷售電話卡，他分別以60元的價格銷售了兩張卡，其中一張賺了20%，另一張?zhí)澚?0%，那么他總共賺了______元A.-10B.10C.-5D.0正確答案：C[考點]邏輯題數(shù)學(xué)計算[解析]對于店主而言，假設(shè)賺了20%的那張電話卡進(jìn)價為x元，虧了20%的那張電話卡進(jìn)價為y元，根據(jù)題意，可得以下兩個等式：

(1)x×(1+20%)=60

(2)y×(1-20%)=60

所以，x=50(元)，y=75(元)。

兩張電話卡的進(jìn)價和為50+75=125(元)，而售價和為60+60=120(元)，因此，店主總共賺了120-125=-5(元)。所以，選項C正確。

17.

在一個不透明的箱子里，一共有紅、黃、藍(lán)、綠、白5種顏色的小球，每種顏色的小球大小相同、質(zhì)量相等、數(shù)量充足。每個人從籃子里抽出兩個小球，如果要保證有兩個人抽到的小球顏色相同，那么需要抽球的人數(shù)至少為______A.11個B.8個C.16個D.13個正確答案：C[考點]排列組合與概率[解析]題目要求兩個人抽到的小球顏色相同，而此題有兩個關(guān)鍵點需要注意：第一，每個人取的是兩個球，而不是一個球，所以，必須要求兩個球的顏色都是一模一樣的才能稱為小球顏色相同；第二，每種球的數(shù)量充足，可以理解為球的數(shù)量是無限的，不存在某一種顏色的球被全部取完，后面的人無法取到的情況。由于球的顏色有5種，根據(jù)排列組合原理，5種情況下取的球的顏色可以分為兩類情況：

(1)取的兩個球顏色相同(每個人取的球顏色是相同的)，有5種情況。

(2)取的兩個球顏色不同，C(5,2)=10，有10種情況。

以上兩種情況合計共有15種情況。如果前15個人取的球顏色都不相同，那么當(dāng)?shù)?6個人取球時，必然會與前面15個人中的某一個相同。由此可知，本題的答案為16個，即選項C正確。

18.

S市共有A、B兩個區(qū)，人口比例為3:5。據(jù)歷史統(tǒng)計，A區(qū)的犯罪率為0.01%，B區(qū)的犯罪率為0.015%，現(xiàn)有一起新案件發(fā)生在S市，那么案件發(fā)生在A區(qū)的可能性是______A.37.5%B.32.5%C.28.6%D.26.1%正確答案：C[考點]排列組合與概率[解析]根據(jù)題目可知，假設(shè)A區(qū)的人數(shù)為3X，那么，B區(qū)人口數(shù)為5X，A區(qū)犯罪的人數(shù)為3X×0.01%，B區(qū)犯罪的人數(shù)為5X×0.015%。A區(qū)犯罪的可能性=A區(qū)犯罪人數(shù)/(A區(qū)犯罪人數(shù)+B區(qū)犯罪人數(shù))=(3X×0.01%)/(3X×0.01%+5X×0.015%)=28.6%。所以，選項C正確。

19.

在一個世世代代都重男輕女的村莊里，村長決定頒布一條法律，村子里沒有生育出兒子的夫妻可以一直生育直到生出兒子為止。假設(shè)現(xiàn)在村子里的男女比例是1:1，這條法律頒布之后的若干年后村子的男女比例將會______A.男的多B.女的多C.一樣多D.不能確定正確答案：C[考點]排列組合與概率[解析]本題中，假設(shè)為了生育男孩，每個家庭孩子個數(shù)的期望值為n，家庭孩子個數(shù)為n的概率為p(n)，那么，可以有如下推理：

P(1)=0.5

//有一個孩子，只有可能是男孩，因此，概率為0.5

P(2)=0.5×0.5

//有兩個孩子，第一胎是女孩，第二胎是男孩

P(3)=0.5×0.5×0.5

//有三個孩子，第一胎是女孩，第二胎是女孩，第三胎是男孩

P(n)=0.5^n

//有n個孩子，前n-1胎都是女孩，最后一胎是男孩

家庭孩子的期望值為：1×p(1)+2×p(2)+…+n×p(n)=2。

每個家庭孩子個數(shù)的期望值為2，也就是說有一個男孩一個女孩。因此，男女個數(shù)是相等的。

還有一種簡單的方法可以得出這個結(jié)論：在所有出生的第一個小孩中，男女比例是1:1；在所有出生的第二個小孩中，男女比例也是1:1；以此類推，在所有出生的第n個小孩中，男女比例還是1:1。因此，男女個數(shù)總是相等的，總的男女比例是1:1。所以，選項C正確。

20.

關(guān)于主對角線(從左上角到右下角)對稱的矩陣為對稱矩陣。如果一個矩陣中的各個元素取值為0或1，那么該矩陣為01矩陣，大小為N×N的01對稱矩陣的個數(shù)為______A.power(2,n)B.power(2,n×n/2)C.power(2,(n×n+n)/2)D.power(2,(n×n-n)/2)正確答案：C[考點]排列組合與概率[解析]通過題意可知，對稱矩陣可以根據(jù)對角線下方的元素推斷出上方的元素。因此，只需要存儲對角線及其以下的元素即可確定該矩陣內(nèi)容。所以，可以得出這樣一個結(jié)論，對稱矩陣可由它的下三角矩陣唯一確定。

本題中，第一行需要填充1個元素，第二行需要填充2個元素…第n行需要填充n個元素，加起來有1+2+3+…+n=n(n+1)/2個元素。此外，每個數(shù)字有0或1兩種可能，因此，一共有power(2,n(n+1)/2)個不同的對角矩陣。所以，本題的答案為C。

21.

在如下8×6的矩陣中，從A點移動到B點一共有______種走法。要求每次只能向上或者向右移動一格，并且不能經(jīng)過點P。

矩陣A.492B.494C.496D.498正確答案：A[考點]排列組合與概率[解析]本題中要求計算兩個點之間可能的路徑條數(shù)，可以采用將不可能的路徑條數(shù)排除的方法。假設(shè)向右走一步記為“右”，向上走一步記為“上”，在這樣一個8×6的矩陣中，從A點到B點，共需要走12步，其中7步必須向右，5步必須向上，但次序可以不同。于是，選定5個設(shè)為“上”，剩下的7個設(shè)為“右”，因此，一共存在C(7,12)種可能性。同時要求P點不能走，要排除經(jīng)過P點(乘法原理)的情況。A點走到P點的可能情況數(shù)是C(3,6)，從P點走到B點的可能情況數(shù)是C(4,6)，因此，本題的結(jié)果是C(7,12)-C(3,6)×C(4,6)=492。所以，選項A正確。

22.

每年9月份是找工作的季節(jié)，此時很多同學(xué)會去圖書館借閱《程序員面試筆試寶典》這本書?，F(xiàn)在圖書館外有6名同學(xué)排隊，其中3名同學(xué)要將手中的《程序員面試筆試寶典》還至圖書館，有3名同學(xué)希望從圖書館中借到《程序員面試筆試寶典》。若當(dāng)前圖書館內(nèi)已無庫存，要保證借書的3名同學(xué)都可以借到書，請問這6位同學(xué)有多少種排隊方式______A.60B.120C.180D.360正確答案：C[考點]排列組合與概率[解析]本題中，一共有6個人參與借書與還書這個動作，而圖書館之前是沒有圖書的，所以，要保證借書的3名同學(xué)都能借到書，必須同時滿足以下三個條件：

(1)第1個同學(xué)肯定是還書的而不是借書的。如果第1個同學(xué)是借書的，那么他肯定借不到書，因為圖書館沒有庫存。所以，第1個同學(xué)一共對應(yīng)3種可能性。

(2)最后1個同學(xué)肯定是借書的而不是還書的。如果最后1個同學(xué)是還書的，那么前面5個人肯定有3個借書的，2個還書的，最終肯定有1個人借不到書，與要求不符。所以，最后1個人一共對應(yīng)3種可能性。

(3)中間的4個人分別有兩個人是借書的，有兩個人是還書的，一共有A(4,4)種可能性，合24種可能性。但是其中有4種可能性不合理，即4個人的借還書順序為借借還還時為什么要排除的數(shù)量是4呢?因為借書對應(yīng)2個人的行為，還書也對應(yīng)2個人的行為，二者取積，其結(jié)果就是4了。

所以，一共有3×3×(24-4)=180，選項C正確。

23.

把10個不同的小球，放入3個不同的桶內(nèi)，共有______種放法A.1000B.720C.59049D.360正確答案：C[考點]排列組合與概率[解析]本題中，10個球都是不一樣的，3個桶也是不一樣的，每一個球都可以放入任何一個桶內(nèi)，每個球有3種放法，即為3^10種方法，3^10=59049。所以，選項C正確。

24.

每臺物理計算機(jī)可以虛擬出20臺虛擬機(jī)，假設(shè)一臺虛擬機(jī)當(dāng)且僅當(dāng)它的宿主物理機(jī)發(fā)生故障時才會工作失常。通過5臺物理機(jī)虛擬出100臺虛擬機(jī)，那么以下關(guān)于這100臺虛擬機(jī)故障的描述中，正確的是______A.單臺虛擬機(jī)的故障率高于單臺物理機(jī)的故障率B.這100臺虛擬機(jī)發(fā)生故障是彼此獨立的C.這100臺虛擬機(jī)單位時間內(nèi)出現(xiàn)故障的次數(shù)高于100臺物理機(jī)單位時間內(nèi)出現(xiàn)故障的次數(shù)D.無法判斷這100臺虛擬機(jī)和100臺物理機(jī)哪個更可靠E.如果隨機(jī)選出5臺虛擬機(jī)組成集群，那么這個集群的可靠性和5臺物理機(jī)的可靠性相同正確答案：C[考點]排列組合與概率[解析]對于選項A，由于一臺虛擬機(jī)當(dāng)且僅當(dāng)它的宿主物理機(jī)發(fā)生故障時才會出現(xiàn)故障，所以，單臺虛擬機(jī)的故障率等于單臺物理機(jī)的故障率。因此，選項A錯誤。

對于選項B，由于一臺虛擬機(jī)當(dāng)且僅當(dāng)它的宿主物理機(jī)發(fā)生故障時才會出現(xiàn)故障，所以，當(dāng)一臺物理機(jī)發(fā)生故障時，它虛擬出來的所有虛擬機(jī)都會發(fā)生故障，即每臺虛擬機(jī)的故障不是完全獨立的。因此，選項B錯誤。

對于選項C，由于一臺物理機(jī)的故障會導(dǎo)致這臺物理機(jī)虛擬出來的20臺虛擬機(jī)的故障，所以，基于5臺物理機(jī)搭建的100臺虛擬機(jī)故障率肯定高于100臺物理機(jī)。因此，選項C正確。

對于選項D，由于虛擬機(jī)的故障是相關(guān)的，很明顯，100臺物理機(jī)會比100臺虛擬機(jī)更可靠。因此，選項D錯誤。

對于選項E，如果隨機(jī)選擇5臺虛擬機(jī)，它們都是屬于同一個物理機(jī)，則這5臺虛擬機(jī)的故障率等于一臺物理機(jī)故障率。因此，選項E錯誤。

25.

村長帶著4對父子參加“爸爸去哪兒”節(jié)目第三季第二站某村莊的拍攝。村里為了保護(hù)小孩不被拐走，有個規(guī)矩，那就是吃飯的時候小孩左右只能是其他小孩或者自己的父母。那么4對父子在圓桌上一共有______種坐法(旋轉(zhuǎn)一下，每個人面對的方向變更后算是一種新的坐法)A.144B.240C.288D.480正確答案：D[考點]排列組合與概率[解析]根據(jù)題意，可以知道位置排列只有以下兩種可能，如下圖所示。

兩種位置排列

對于第一種方式，由于孩子和孩子是面對面的，父親和父親是面對面的，所以，8個位置可以等效為4個位置，孩子的位置定了，父親的位置也就定了。而孩子的排列數(shù)為4×3×2，旋轉(zhuǎn)只有4種可能(因為等效下來只有4個位置)，所以，總的坐法數(shù)量為4×4×3×2=96。

對于第二種方式，孩子的排列有4×3×2×1種，孩子的位置定了，其中兩位父親的位置就定了，剩下兩位父親就可以隨意排列了，此時可以旋轉(zhuǎn)8次，總的坐法數(shù)量為8×4×3×2×2=384。

綜上所述，總共有384+96=480種可能。所以，選項D正確。

26.

如果兵馬俑博物館參觀者到達(dá)的速率是每分鐘20人，平均每個人停留20分鐘，那么該博物館至少需要容納______人A.100B.200C.300D.400正確答案：D[考點]排列組合與概率[解析]本題中，參觀者到達(dá)的速率是每分鐘20人，平均每個人在館內(nèi)停留20分鐘，在這20分鐘里面，大家都還沒走，那么總共需要同時容納20×20=400人。所以，選項D正確。

27.

對立的兩方爭奪一個價值為1的物品，雙方采取的策略可以分為鴿子策略和鷹策略。如果雙方都是鴿子策略，那么雙方各有1/2的概率獲得該物品；如果雙方均為鷹策略，那么雙方各有1/2的概率取勝，勝方獲得價值為1的物品，付出價值為1的代價，負(fù)方付出價值為1的代價；如果一方為鴿子策略，一方為鷹策略，那么鷹策略獲得價值為1的物品。在爭奪的結(jié)果出來之前，沒人知道對方是鴿子策略還是鷹策略，當(dāng)選擇鴿子策略的人的比例是某一個值時，選擇鴿子策略和選擇鷹策略的預(yù)期收益是相同的，那么該值是______A.0.2B.0.4C.0.5D.0.7正確答案：C[考點]排列組合與概率[解析]本題中，假設(shè)選擇鴿子的人的比例為p，那么選擇鷹的人的比例為1-p。此時選擇鴿子的預(yù)期收益為：p×1/2×1/2(對方選擇鴿子的收益)+0(對方選擇鷹的收益)，選擇鷹的預(yù)期收益為：((1-p)×1/2×(1-1)+(1-p)×1/2×(-1))×1/2(對方選擇鷹的收益)+(1-p)×1×1/2(對方選擇鴿子的收益)。如果鴿子和鷹的預(yù)期收益一樣，則p×1/2×1/2=(1-p)×1/2×(-1)×1/2+(1-p)×1×1/2，得到p=0.5。所以，選項C正確。

28.

畢業(yè)典禮后，某宿舍三位同學(xué)把自己的畢業(yè)帽扔了，隨后每個人隨機(jī)地拾起帽子，三個人中沒有人選到自己原來戴的帽子的概率是______A.1/2B.1/3C.1/4D.1/6正確答案：B[考點]排列組合與概率[解析]本題中，不考慮任何情況，撿到帽子的情況有3×2×1=6種。

每個人都不能撿到自己的帽子，情況有兩種：A-c、B-a、C-b或者A-b、B-c、C-b，其中大寫的A、B和C分別代表三位同學(xué)，小寫的a、b和c分別代表A、B和C三個人的帽子，那么所求概率應(yīng)該是2/6=1/3。所以，選項B正確。

29.

一個合法的表達(dá)式由括號()包圍，括號()可以嵌套和連接，如(())()也是合法的表達(dá)式?，F(xiàn)有6對括號()，它們可以組成的合法表達(dá)式的個數(shù)為______A.15B.30C.64D.132正確答案：D[考點]排列組合與概率[解析]本題中，可以把左括號看作1，右括號看作0，這些括號的組合就是01的排列。此時需要滿足從第一個數(shù)開始的任意連續(xù)子序列中，0的個數(shù)不多于1的個數(shù)，也就是右括號的個數(shù)不多于左括號的個數(shù)。

假設(shè)不考慮這個限制條件，那么全部的01排列共有C(2n,n)種，也就是一半為0，一半為1的情況。需要注意的是，最終的結(jié)果還需要考慮一些不符合項的內(nèi)容。

在任何不符合條件的序列中，找出使得0的個數(shù)超過1的個數(shù)的第一個0的位置，然后在導(dǎo)致并包括這個0的部分序列中，以1代替所有的0并以0代表所有的1，結(jié)果總的序列變成一個有(n+1)個1和(n-1)個0的序列，而且這個過程是可逆的。也就是說，任何一個由(n+1)個1和(n-1)個0構(gòu)成的序列都能反推出一個不符合條件的序列。所以，不符合條件的序列個數(shù)為C(2n,n-1)，合法的排列數(shù)為C(2n,n)-C(2n,n-1)=C(12,6)-C(12,5)=132。因此，選項D正確。

30.

某團(tuán)隊有2/5的人會寫Java程序，有3/4的人會寫C++程序，那么這個團(tuán)隊里同時會寫Java程序和C++程序的至少有______人A.3B.4C.5D.8正確答案：A[考點]排列組合與概率[解析]本題中，2/5中的5和3/4中的4的最小公倍數(shù)為20，所以，會Java語言的至少有8個人(也可能是8的若干倍)，會C++語言的有15個人(也可能是15的若干倍)。那么，同時會使用Java語言和C++語言的人至少有8+15-20=3個，所以，至少有3個人同時會Java語言和CH語言。因此，選項A正確。

31.

甲乙兩路公交車間隔均為10分鐘，公交車發(fā)車時刻的分鐘數(shù)個位分別是1和9，那么對于一個隨機(jī)到達(dá)的乘客，他乘坐甲車的概率為______A.0.1B.0.2C.0.3D.0.9正確答案：B[考點]排列組合與概率[解析]本題中，對于一名乘客而言，每10分鐘里面，如果他在時間區(qū)間[0,1)或[9,10]內(nèi)到達(dá)公交站，那么他會乘坐公交車甲，因此他坐甲車的概率p為0.2。如果他在時間區(qū)間[1,9)內(nèi)到達(dá)公交站，那么他會乘坐公交車乙，因此他乘坐乙車的概率q為0.8。所以，選項B正確。

32.

假設(shè)下圖中每個正方形的邊長為1，則從A到Z的最短路徑條數(shù)為______

多個正方形A.11B.12C.13D.14正確答案：C[考點]排列組合與概率[解析]本題中，假設(shè)為題圖的左下角與右上角補充兩個小正方形，那么此時從點A到點Z需要橫著走4格，豎著走2格，此時最短路徑有C(6,2)或C(6,4)種情況，即(6×5)/2=15種情況。當(dāng)然，最終結(jié)果不是15，由于整個圖形補充了兩個缺口，所以，必須在15的基礎(chǔ)上減去2，最終結(jié)果為15-2=13。因此，選項C正確。

33.

袋中有紅球、黃球和白球各一個，每次任意取一個放回，如此連續(xù)3次，則下列事件中概率是8/9的是______A.顏色不全相同B.顏色全不相同C.顏色全相同D.顏色無紅色正確答案：A[考點]排列組合與概率[解析]對于選項A，如果每次任取一個球，則取到一個紅球、一個黃球和一個白球的概率相等，均為1/3，所以，顏色不全相同的概率P1=1-C(3,1)×1/3×1/3×1/3=8/9。因此，選項A正確。

對于選項B，顏色全不相同的概率P2=C(3,1)×C(2,1)/(3×3×3)=2/9。因此，選項B錯誤。

對于選項C，顏色全相同的概率P3=C(3,1)×1/3×1/3×1/3=1/9。因此，選項C錯誤。

對于選項D，顏色無紅色，表明在3次取球的過程中，每次取到的都是其他顏色的球，顏色無紅色的概率P4=2/3×2/3×2/3=8/27。因此，選項D錯誤。

34.

用兩種顏色去染排成一個圈的6個棋子，如果是通過旋轉(zhuǎn)得到的則只能算一種排列方式，那么一共有______種染色情況A.10B.11C.14D.15正確答案：C[考點]排列組合與概率[解析]本題中，假設(shè)兩種顏色分別是黑色與白色，默認(rèn)情況下是白色，考慮到通過旋轉(zhuǎn)得到的形式只能算為一種，那么，用P(n)表示有n個黑棋的種類，此時可以得出以下結(jié)論：

(1)p(0)=p(6)=1。全是白色或者全是黑色，分別只存在1種可能情況。

(2)p(1)=p(5)=1。1個白棋子與5個黑棋子或者1個黑棋子與5個白棋子，分別只存在1種可能情況。

(3)P(2)=p(4)=3。分別存在3種可能，分別是黑白棋子相鄰，黑白棋子隔一個，黑白棋子隔兩個。

(4)p(3)=4。3個黑棋子與3個白棋子，一共4種組合，分別是黑黑黑白白白、黑黑白黑白白、黑黑白白黑白、黑白黑白黑白。

一共有P(0)+P(1)+P(2)+P(3)+P(4)+P(5)+P(6)=14種染色方案。所以，選項C正確。

35.

某城市發(fā)生了一起汽車撞人逃跑事件，該城市只有兩種顏色的車，其中白色車占15%，黑色車占85%。事發(fā)時有一個人在現(xiàn)場看見似乎是一輛白色的車，但是根據(jù)專家在現(xiàn)場分析，在當(dāng)時那種條件能看清楚的可能性是80%。那么，肇事車是白車的概率是______A.12%B.29%C.41%D.80%正確答案：C[考點]排列組合與概率[解析]本題中，肇事車的情況一共存在著以下4種可能性：

(1)如果肇事車是白色車，被正確識別的概率P1=15%×80%=12%。

(2)如果肇事車是白色車，被看成是黑車的概率P2=15%×20%=3%。

(3)如果肇事車是黑色車，被正確識別的概率P3=85%×80%=68%。

(4)如果肇事車是黑色車，被看成是白車的概率P4=85%×20%=17%。

所以，肇事車是白色車的概率P=P1/(P1+P4)=12%/(12%+17%)=41.3%。因此，選項C正確。

36.

有5名同學(xué)爭奪3項比賽的冠軍，若每項比賽只設(shè)1名冠軍，則冠軍的可能情況有______A.120種B.130種C.60種D.125種正確答案：D[考點]排列組合與概率[解析]本題中，由于沒有明確規(guī)定各項比賽的冠軍不能是同一個人，所以每一個冠軍頭銜都可能有5種不同的情況，由乘法原理可知，冠軍的可能情況有5×5×5=125種。所以，選項D正確。

37.

從一副牌(52張，不含大小王)里抽出兩張牌，其中一紅一黑的概率是______A.25/51B.1/3C.1/2D.26/51正確答案：D[考點]排列組合與概率[解析]每副牌中，有4種花色的牌以及大小王，各個花色的牌都是13張，分別為1、2、3、4、5、6、7、8、9、10、J、Q、K。從52張牌中抽兩張牌，一共有C(52,2)種情況。一紅指的是紅桃與方片，一黑指的是黑桃與梅花，抽到一紅的可能情況有C(26,1)種，抽到一黑的可能情況有C(26,1)種，所以，抽到一紅一黑的概率P=C(26,1)×C(26,1)/C(52,2)=26/51。因此，選項D正確。

38.

有一堆石子共100枚，甲乙輪流從堆中取石子，每次可取2枚、4枚或6枚，假設(shè)取得最后石子的玩家為贏。若甲先取，則______A.誰都無法取勝B.乙必勝C.甲必勝D.不確定正確答案：C[考點]排列組合與概率[解析]很顯然，只要先取的人保證最后剩8枚，無論后取的人取幾枚石子(如果后取石子的人取2枚，則先取石子的人取6枚：如果后取石子的人取4枚，則先取石子的人取4枚；如果后取石子的人取6枚，則先取石子的人取2枚)，先取石子的人都可以取得勝利。

所以，只要先取的人能夠保證最后剩余8枚即可保證自己獲得勝利。那么，問題來了，如何保證呢?其實很簡單，只要保證每一個回合內(nèi)取的數(shù)是一個可控的固定數(shù)即可，顯然，8就是這個固定數(shù)。先取的人只需要保證第一次取完后，剩下的數(shù)字是8的倍數(shù)，以后無論后取的人怎么取，只要先取的人取的石子數(shù)與后取的人取的石子數(shù)相加為8，就一定能勝。100%8=4，所以，本題中，只需要甲先取4枚石子，然后在后續(xù)的取數(shù)中，每一個回合所取數(shù)與上一個回合乙所取數(shù)之和為8，就能保證取勝。因此，選項C正確。

二、簡答題1.

如何實現(xiàn)鏈表的逆序?正確答案：鏈表作為最基本的數(shù)據(jù)結(jié)構(gòu)，它不僅在實際應(yīng)用中有著非常重要的作用，而且也是程序員面試筆試中必考的內(nèi)容。具體而言，它的存儲特點為：可以用任意一組存儲單元來存儲單鏈表中的數(shù)據(jù)元素(存儲單元可以是不連續(xù)的)，而且，除了存儲每個數(shù)據(jù)元素ai外，還必須存儲指示其直接后繼元素的信息。這兩部分信息組成的數(shù)據(jù)元素ai的存儲映像稱為結(jié)點。N個結(jié)點連在一塊被稱為鏈表，結(jié)點只包含其后繼結(jié)點信息的鏈表就被稱為單鏈表，而鏈表的第一個結(jié)點通常被稱為頭結(jié)點。

對于單鏈表，又可以將其分為有頭結(jié)點的單鏈表和無頭結(jié)點的單鏈表，如下圖所示。

有頭結(jié)點和無頭結(jié)點

在單鏈表的開始結(jié)點之前附設(shè)一個類型相同的結(jié)點，稱之為頭結(jié)點，頭結(jié)點的數(shù)據(jù)域可以不存儲任何信息(也可以存放線性表的長度等附加信息)，頭結(jié)點的指針域存儲指向開始結(jié)點的指針(即第一個元素結(jié)點的存儲位置)。

具體而言，頭結(jié)點的作用主要有以下兩點：

(1)對于帶頭結(jié)點的鏈表，當(dāng)在鏈表的任何結(jié)點