前端程序员面试分类真题20

前端程序员面试分类真题20一、单项选择题1.

数据结构从逻辑上分为______两大类A.顺序结构，链式结构B.静态结构，动态结构C.初等结构，构造型结构D.线性结构，非线性结构正确答案：D（江南博哥）[解析]数据的逻辑结构指反映数据元素之间逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后关系，而与它们在计算机中的存储位置无关。通常情况下，数据的逻辑结构分以下两大类：线性结构和非线性结构。线性结构是指该结构中的结点之间存在一对一的关系，其特点是开始结点和终端结点都是唯一的，除了开始结点和终端结点外，其余结点都有且仅有一个直接前驱，有且仅有一个直接后继，此类型的存储结构有：顺序表(数组)、链表、栈结构或队列结构等。非线性结构又包括集合、树形结构、图形结构或网状结构，特点是数据元素之间存在一个对多个或多个对多个的关系，其中集合是一种关系极为松散的结构。

数据的存储方法有4种：顺序存储方法、链接存储方法、索引存储方法和散列存储方法。

(1)顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。

(2)链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示。由此得到的存储表示称为链式存储结构，通常借助于程序语言的指针类型描述。

(3)索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。组成索引表的索引项由结点的关键字和地址组成。如果每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引。如果一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。

(4)散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。

通过以上分析可知，选项D正确。

2.

以下对顺序文件的描述中，错误的是______A.插入新的记录时只能加在文件末尾B.存取第i个记录，必须先搜索在它之前的i-1个记录C.如要更新文件中的记录，必须将整个文件复制D.顺序文件中物理记录的顺序和逻辑记录的顺序不一致正确答案：D[解析]顺序文件是指按记录进入文件的先后顺序存放，其逻辑顺序和物理顺序一致的文件。一切存储在顺序存取存储器(如磁带)上的文件，都只能是顺序文件。

对于选项A，插入新记录时不能插入到已经有顺序的文件中间，只能在末尾。所以，选项A正确。

对于选项B，如果查找第i个记录，必须从头开始找起，符合顺序表的性质。所以，选项B正确。

对于选项C，如果要更新，必须复制整个文件后再更新，然后再放到另外一块顺序存储器上。所以，选项C正确。

对于选项D，顺序记录的顺序和逻辑记录的顺序是一致的。所以，选项D错误。

因此，本题的答案为D。

3.

下列数据结构不是多型数据类型的是______A.堆B.栈C.字符串D.有向图正确答案：C[解析]要想选出正确答案，就需要弄明白什么是多型数据类型?一种抽象数据类型的操作可用于多种具体数据类型的操作，这就是多型数据类型。简单点说，多型有点类似于面向对象的模板，就是数据元素的类型不确定。本题中，堆、栈和有向图中的数据元素类型是不确定的，所以，选项A、选项B和选项D正确。字符串的每个元素始终都是字符(char)，而不会是别的类型，所以，字符串不是多型数据类型，选项C错误。

4.

以下关于数据结构的描述中，错误的是______A.红黑树插入操作的平均时间复杂度为O(logn)，最坏时间复杂度为O(logn)B.B+树插入操作的平均时间复杂度为O(logn)，最坏时间复杂度为O(logn)C.Hash插入操作的平均时间复杂度为O(logn)，最坏时间复杂度为O(n)D.排序链表插入操作的平均时间复杂度为O(n)，最坏时间复杂度为O(n)正确答案：C[解析]对于选项A与选项B，红黑树和B+树插入操作的平均时间复杂度都为O(logn)，最坏时间复杂度为O(logn)。所以，选项A与选项B正确。

对于选项C，散列表存储的是键值对，其查找的时间复杂度与元素数量多少无关。散列表在查找元素时是通过计算哈希码值来定位元素的位置从而直接访问元素的，因此，散列表的插入、删除和查找等操作的时间复杂度都是O(l)。所以，选项C错误。

对于选项D，排序链表的插入操作较为复杂，需要先查找位置，再执行插入，其插入的时间复杂度不是O(l)，而是O(n)，而且，其平均时间复杂度为O(n)，最坏时间复杂度也为O(n)。所以，选项D正确。

因此，本题的答案为C。

5.

实验高中的小明暗恋女神同学已经三年了，高考结束后，小明决定向女神同学表白。这天，小明来到女神楼下等待女神的出现，时间一分一秒地流逝，两个多小时过去了，女神还没有出现。小明看了下表，时针和分针的位置正好跟开始等的时候互换，请问小明一共等了女神______分钟A.165B.150C.172D.166正确答案：D[考点]逻辑题数学计算[解析]根据题目中的描述，可以画一个表示时针与分针的图例，如下图所示。

时针与分针互换

假设小明开始等待女神的那一时刻时针与分针的夹角为θ弧度，那么，等到时针与分针正好互换位置时，时针走过了θ弧度。而由于分针转动一圈表示的时间为一个小时，钟表一圈是一个圆，表示的弧度值为2π，分针因为要转若干圈才能到达时针的位置，记分钟所转圈数为n，此时分针转过的角度则为(2πn-θ)弧度。

题目强调，“时间一分一秒地流逝，两个多小时过去了，女神还没有出现”，通过这条信息可知，分针转了2到3圈，接近3圈，此时的n值取3。所以，时针转过的角度值为θ，分针转过的角度值为2π×3-θ=6π-θ。

对于时针而言，2π代表一圈，即12个小时，那么弧度θ表示的时间值为12×θ/2π小时；对于分针而言，2π代表一圈，即60分钟，那么(6π-θ)表示的是60×(6π-θ)/2π分钟。由于时钟走过的时间值与分钟走过的时间值所代表的时间量是一个量，故而二者是相等的，由此可以构建如下等式：

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

求解上述等式可知，θ=6π/13，即小明等待的时间反映在钟表上为6π/13弧度值。所以，小明一共等了12×(6π/13)/2π小时，即36/13小时，合166分钟。因此，选项D正确。

6.

如果等式12×25=311成立，那么使用的是______进制运算A.7B.8C.9D.11正确答案：C[考点]逻辑题数学计算[解析]当进行乘法运算时，无论是什么进制的数进行运算，其基本方法都是相同的，以十进制数的计算为例：2×5=10。如果是七进制，那么运算结果最后一位一定是10%7=3，相乘后进位值为10/7=1。同理，如果是八进制，相乘结果最后一位一定等于10%8=2。如果是九进制，最后一位一定是10%9=1。如果是十一进制，最后一位一定是10%11=A(类似于十六进制中，使用A表示数字10)。

本题中，计算结果为311，最后一位为1，可以排除选项A、选项B和选项D，只有选项C满足题意，所以，选项C正确。

7.

平面内一共有11个点，由它们连成48条不同的直线，由这些点可连成的三角形个数为______A.162B.158C.160D.165正确答案：C[考点]逻辑题数学计算[解析]题目告知，平面内有11个点，如果这些点中任意3个点都没有共线，那么一共有C(11，2)=55种情况。但是根据题意可知，这11个点只能连接成48条直线，那么这些点中必定有3点共线以及3点以上的共线，一共55-48=7种情况。

而这7种3点共线的情况又可以划分为以下多种情况：

(1)假设只有3点共线，令3点共线的直线有x条，那么可以组成的直线在55的基础上应该除去这些情况，即C(11，2)-x×C(3，2)+1=48，由于解算出来的x值不是整数，所以，此种情况不满足条件。

(2)假设只有4点共线，令4点共线的直线有x条，那么可以组成的直线在55的基础上应该除去这些情况，即C(11，2)-x×C(4，2)+1=48，由于解算出来的x值不是整数，所以，此种情况不满足条件。

(3)假设只有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个点能组成的三角形的个数为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[考点]逻辑题数学计算[解析]本题中，最重要的解题方法就是找出数列的规律，从而推导出最后一个数是多少。通过研究已有的7个数，不难发现：第二项+第七项=4+11=15，第三项+第六项=5+9=14，第四项+第五项=6+7=13，两个数的和依次递减。可以推出这样一个结论：第一项+第八项=16，因为第一项的值为1，所以，第八项=16-1=15。因此，选项C正确。

9.

8，8，12，24，60，______A.90B.180C.120D.240正确答案：B[考点]逻辑题数学计算[解析]本题是一个数列找规律的题目，经常出现在小学奥数或是高中生升学考试中，考察求职者的逻辑思维能力。

虽然此题中相邻项的商并不是一个常数，但它们是按照一定规律排列的。不难发现，本题中后一项除以前一项的结果构成一个等差数列，公差1/2，即除第一项以外的每一项都等于其前一项的值乘以(1+0.5×n)，n的值是从0开始的自然数。具体为：8×1=8，8×1.5=12，12×2=24，24×2.5=60，根据这一规律，60后面的数值应为60×3=180。所以，选项B正确。

10.

有A、B、C三个人负责装修房子，对于一面墙，单独工作时，A需要花费18小时砌好，B需要花费24小时，C需要花费30小时。现A、B、C三人顺序轮流砌墙，每人工作1小时换班，完工时，B总共工作了______A.8小时B.7小时44分C.7小时D.6小时48分正确答案：B[考点]逻辑题数学计算[解析]根据题目意思可知，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[考点]逻辑题数学计算[解析]首先，选定一个参考物，以12点正点时刻作为参考量，按顺时针计算算出时针与该参考量的偏移量，然后算出分针与该参考量的偏移量，二者相减可以求出时针与分针的夹角。

众所周知，时针行走一圈为360°，合12个小时，所以，时针每小时转动的角度值为360°/12=30°，下午17:32的时针偏移量为30°×(5+32/60)=166°，即时针与12点正点时刻时的夹角为166°。分针每行走一圈为360°，合1个小时(60分钟)，所以，分针每分钟转动的角度值为360°/60=6°，下午17:32的分针偏移量为6×32=192°。

时针与分针偏移量的差值即为所求解，192°-166°=26°。所以，选项B正确。

12.

若被除数为二进制数110110，除数为二进制数111，则余数为______A.100B.101C.110D.111正确答案：B[考点]逻辑题数学计算[解析]本题可以首先将二进制转换为十进制，进行求解后，再转换为二进制。

二进制数110110对应的十进制数为32+16+4+2=54，二进制数111对应的十进制数为4+2+1=7，计算54%7得到的结果为5，用二进制表示为101。所以，选项B正确。

13.

87的100次方除以7的余数是______A.1B.2C.3D.4正确答案：D[考点]逻辑题数学计算[解析]对于取余运算符%，满足如下等式关系：(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，根据等式递推可得到：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[考点]逻辑题数学计算[解析]根据矩阵运算知识，可以排除选项C与选项D，因为矩阵A与矩阵B相乘，矩阵A的列数必须与矩阵B的行数相等。

对于选项A与选项B，一个m×n的矩阵A乘以nXq的矩阵B，会用矩阵A的第一行，乘以矩阵B的第一列并相加。这一运算需要耗费n次乘法以及n-1次加法，矩阵B有q列，矩阵A有m行，所以，AxB的复杂度为m×(2n-1)×q。

根据上面的分析可知，选项A的复杂度为m×(2n-1)×p+m×(2p-1)×q，而选项B的复杂度为m×(2n-1)×q+n×(2p-1)×q，很显然，选项A的效率高于选项B。所以，选项A正确。

15.

小胖欲用积分兑换加多宝，兑换的规则是每10个积分可以兑换一瓶加多宝并返还5个积分。小胖现有200个积分，那么他最多可以兑换到的加多宝数量是______A.38B.39C.40D.41正确答案：B[考点]逻辑题数学计算[解析]本题中，根据兑换规则，每10个积分可以兑换一瓶加多宝并返还5个积分，换一个角度看，每瓶加多宝就只需要5个积分即可。表面上看，200个积分可以换200/5=40个加多宝，但是这忽略了一个前提，就是小胖手中必须至少有10个积分的时候，加多宝才能兑换，并返回5个积分，否则5个积分等价于一瓶加多宝这条结论就不成立。所以，200个积分的前190个积分可以按照每5个积分换一瓶加多宝换取，此时可以换取190/5=38瓶。当小胖手中还有最后10个积分时，他还可以兑换一瓶加多宝，同时返还5个积分，而最后剩下的5个积分是无法单独兑换加多宝的，因此，小胖手中的200个积分，最多可以兑换到的加多宝数量为39瓶。所以，选项B正确。

16.

店主销售电话卡，他分别以60元的价格销售了两张卡，其中一张赚了20%，另一张亏了20%，那么他总共赚了______元A.-10B.10C.-5D.0正确答案：C[考点]逻辑题数学计算[解析]对于店主而言，假设赚了20%的那张电话卡进价为x元，亏了20%的那张电话卡进价为y元，根据题意，可得以下两个等式：

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

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

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

两张电话卡的进价和为50+75=125(元)，而售价和为60+60=120(元)，因此，店主总共赚了120-125=-5(元)。所以，选项C正确。

17.

在一个不透明的箱子里，一共有红、黄、蓝、绿、白5种颜色的小球，每种颜色的小球大小相同、质量相等、数量充足。每个人从篮子里抽出两个小球，如果要保证有两个人抽到的小球颜色相同，那么需要抽球的人数至少为______A.11个B.8个C.16个D.13个正确答案：C[考点]排列组合与概率[解析]题目要求两个人抽到的小球颜色相同，而此题有两个关键点需要注意：第一，每个人取的是两个球，而不是一个球，所以，必须要求两个球的颜色都是一模一样的才能称为小球颜色相同；第二，每种球的数量充足，可以理解为球的数量是无限的，不存在某一种颜色的球被全部取完，后面的人无法取到的情况。由于球的颜色有5种，根据排列组合原理，5种情况下取的球的颜色可以分为两类情况：

(1)取的两个球颜色相同(每个人取的球颜色是相同的)，有5种情况。

(2)取的两个球颜色不同，C(5,2)=10，有10种情况。

以上两种情况合计共有15种情况。如果前15个人取的球颜色都不相同，那么当第16个人取球时，必然会与前面15个人中的某一个相同。由此可知，本题的答案为16个，即选项C正确。

18.

S市共有A、B两个区，人口比例为3:5。据历史统计，A区的犯罪率为0.01%，B区的犯罪率为0.015%，现有一起新案件发生在S市，那么案件发生在A区的可能性是______A.37.5%B.32.5%C.28.6%D.26.1%正确答案：C[考点]排列组合与概率[解析]根据题目可知，假设A区的人数为3X，那么，B区人口数为5X，A区犯罪的人数为3X×0.01%，B区犯罪的人数为5X×0.015%。A区犯罪的可能性=A区犯罪人数/(A区犯罪人数+B区犯罪人数)=(3X×0.01%)/(3X×0.01%+5X×0.015%)=28.6%。所以，选项C正确。

19.

在一个世世代代都重男轻女的村庄里，村长决定颁布一条法律，村子里没有生育出儿子的夫妻可以一直生育直到生出儿子为止。假设现在村子里的男女比例是1:1，这条法律颁布之后的若干年后村子的男女比例将会______A.男的多B.女的多C.一样多D.不能确定正确答案：C[考点]排列组合与概率[解析]本题中，假设为了生育男孩，每个家庭孩子个数的期望值为n，家庭孩子个数为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。

每个家庭孩子个数的期望值为2，也就是说有一个男孩一个女孩。因此，男女个数是相等的。

还有一种简单的方法可以得出这个结论：在所有出生的第一个小孩中，男女比例是1:1；在所有出生的第二个小孩中，男女比例也是1:1；以此类推，在所有出生的第n个小孩中，男女比例还是1:1。因此，男女个数总是相等的，总的男女比例是1:1。所以，选项C正确。

20.

关于主对角线(从左上角到右下角)对称的矩阵为对称矩阵。如果一个矩阵中的各个元素取值为0或1，那么该矩阵为01矩阵，大小为N×N的01对称矩阵的个数为______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[考点]排列组合与概率[解析]通过题意可知，对称矩阵可以根据对角线下方的元素推断出上方的元素。因此，只需要存储对角线及其以下的元素即可确定该矩阵内容。所以，可以得出这样一个结论，对称矩阵可由它的下三角矩阵唯一确定。

本题中，第一行需要填充1个元素，第二行需要填充2个元素…第n行需要填充n个元素，加起来有1+2+3+…+n=n(n+1)/2个元素。此外，每个数字有0或1两种可能，因此，一共有power(2,n(n+1)/2)个不同的对角矩阵。所以，本题的答案为C。

21.

在如下8×6的矩阵中，从A点移动到B点一共有______种走法。要求每次只能向上或者向右移动一格，并且不能经过点P。

矩阵A.492B.494C.496D.498正确答案：A[考点]排列组合与概率[解析]本题中要求计算两个点之间可能的路径条数，可以采用将不可能的路径条数排除的方法。假设向右走一步记为“右”，向上走一步记为“上”，在这样一个8×6的矩阵中，从A点到B点，共需要走12步，其中7步必须向右，5步必须向上，但次序可以不同。于是，选定5个设为“上”，剩下的7个设为“右”，因此，一共存在C(7,12)种可能性。同时要求P点不能走，要排除经过P点(乘法原理)的情况。A点走到P点的可能情况数是C(3,6)，从P点走到B点的可能情况数是C(4,6)，因此，本题的结果是C(7,12)-C(3,6)×C(4,6)=492。所以，选项A正确。

22.

每年9月份是找工作的季节，此时很多同学会去图书馆借阅《程序员面试笔试宝典》这本书。现在图书馆外有6名同学排队，其中3名同学要将手中的《程序员面试笔试宝典》还至图书馆，有3名同学希望从图书馆中借到《程序员面试笔试宝典》。若当前图书馆内已无库存，要保证借书的3名同学都可以借到书，请问这6位同学有多少种排队方式______A.60B.120C.180D.360正确答案：C[考点]排列组合与概率[解析]本题中，一共有6个人参与借书与还书这个动作，而图书馆之前是没有图书的，所以，要保证借书的3名同学都能借到书，必须同时满足以下三个条件：

(1)第1个同学肯定是还书的而不是借书的。如果第1个同学是借书的，那么他肯定借不到书，因为图书馆没有库存。所以，第1个同学一共对应3种可能性。

(2)最后1个同学肯定是借书的而不是还书的。如果最后1个同学是还书的，那么前面5个人肯定有3个借书的，2个还书的，最终肯定有1个人借不到书，与要求不符。所以，最后1个人一共对应3种可能性。

(3)中间的4个人分别有两个人是借书的，有两个人是还书的，一共有A(4,4)种可能性，合24种可能性。但是其中有4种可能性不合理，即4个人的借还书顺序为借借还还时为什么要排除的数量是4呢?因为借书对应2个人的行为，还书也对应2个人的行为，二者取积，其结果就是4了。

所以，一共有3×3×(24-4)=180，选项C正确。

23.

把10个不同的小球，放入3个不同的桶内，共有______种放法A.1000B.720C.59049D.360正确答案：C[考点]排列组合与概率[解析]本题中，10个球都是不一样的，3个桶也是不一样的，每一个球都可以放入任何一个桶内，每个球有3种放法，即为3^10种方法，3^10=59049。所以，选项C正确。

24.

每台物理计算机可以虚拟出20台虚拟机，假设一台虚拟机当且仅当它的宿主物理机发生故障时才会工作失常。通过5台物理机虚拟出100台虚拟机，那么以下关于这100台虚拟机故障的描述中，正确的是______A.单台虚拟机的故障率高于单台物理机的故障率B.这100台虚拟机发生故障是彼此独立的C.这100台虚拟机单位时间内出现故障的次数高于100台物理机单位时间内出现故障的次数D.无法判断这100台虚拟机和100台物理机哪个更可靠E.如果随机选出5台虚拟机组成集群，那么这个集群的可靠性和5台物理机的可靠性相同正确答案：C[考点]排列组合与概率[解析]对于选项A，由于一台虚拟机当且仅当它的宿主物理机发生故障时才会出现故障，所以，单台虚拟机的故障率等于单台物理机的故障率。因此，选项A错误。

对于选项B，由于一台虚拟机当且仅当它的宿主物理机发生故障时才会出现故障，所以，当一台物理机发生故障时，它虚拟出来的所有虚拟机都会发生故障，即每台虚拟机的故障不是完全独立的。因此，选项B错误。

对于选项C，由于一台物理机的故障会导致这台物理机虚拟出来的20台虚拟机的故障，所以，基于5台物理机搭建的100台虚拟机故障率肯定高于100台物理机。因此，选项C正确。

对于选项D，由于虚拟机的故障是相关的，很明显，100台物理机会比100台虚拟机更可靠。因此，选项D错误。

对于选项E，如果随机选择5台虚拟机，它们都是属于同一个物理机，则这5台虚拟机的故障率等于一台物理机故障率。因此，选项E错误。

25.

村长带着4对父子参加“爸爸去哪儿”节目第三季第二站某村庄的拍摄。村里为了保护小孩不被拐走，有个规矩，那就是吃饭的时候小孩左右只能是其他小孩或者自己的父母。那么4对父子在圆桌上一共有______种坐法(旋转一下，每个人面对的方向变更后算是一种新的坐法)A.144B.240C.288D.480正确答案：D[考点]排列组合与概率[解析]根据题意，可以知道位置排列只有以下两种可能，如下图所示。

两种位置排列

对于第一种方式，由于孩子和孩子是面对面的，父亲和父亲是面对面的，所以，8个位置可以等效为4个位置，孩子的位置定了，父亲的位置也就定了。而孩子的排列数为4×3×2，旋转只有4种可能(因为等效下来只有4个位置)，所以，总的坐法数量为4×4×3×2=96。

对于第二种方式，孩子的排列有4×3×2×1种，孩子的位置定了，其中两位父亲的位置就定了，剩下两位父亲就可以随意排列了，此时可以旋转8次，总的坐法数量为8×4×3×2×2=384。

综上所述，总共有384+96=480种可能。所以，选项D正确。

26.

如果兵马俑博物馆参观者到达的速率是每分钟20人，平均每个人停留20分钟，那么该博物馆至少需要容纳______人A.100B.200C.300D.400正确答案：D[考点]排列组合与概率[解析]本题中，参观者到达的速率是每分钟20人，平均每个人在馆内停留20分钟，在这20分钟里面，大家都还没走，那么总共需要同时容纳20×20=400人。所以，选项D正确。

27.

对立的两方争夺一个价值为1的物品，双方采取的策略可以分为鸽子策略和鹰策略。如果双方都是鸽子策略，那么双方各有1/2的概率获得该物品；如果双方均为鹰策略，那么双方各有1/2的概率取胜，胜方获得价值为1的物品，付出价值为1的代价，负方付出价值为1的代价；如果一方为鸽子策略，一方为鹰策略，那么鹰策略获得价值为1的物品。在争夺的结果出来之前，没人知道对方是鸽子策略还是鹰策略，当选择鸽子策略的人的比例是某一个值时，选择鸽子策略和选择鹰策略的预期收益是相同的，那么该值是______A.0.2B.0.4C.0.5D.0.7正确答案：C[考点]排列组合与概率[解析]本题中，假设选择鸽子的人的比例为p，那么选择鹰的人的比例为1-p。此时选择鸽子的预期收益为：p×1/2×1/2(对方选择鸽子的收益)+0(对方选择鹰的收益)，选择鹰的预期收益为：((1-p)×1/2×(1-1)+(1-p)×1/2×(-1))×1/2(对方选择鹰的收益)+(1-p)×1×1/2(对方选择鸽子的收益)。如果鸽子和鹰的预期收益一样，则p×1/2×1/2=(1-p)×1/2×(-1)×1/2+(1-p)×1×1/2，得到p=0.5。所以，选项C正确。

28.

毕业典礼后，某宿舍三位同学把自己的毕业帽扔了，随后每个人随机地拾起帽子，三个人中没有人选到自己原来戴的帽子的概率是______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分别代表三位同学，小写的a、b和c分别代表A、B和C三个人的帽子，那么所求概率应该是2/6=1/3。所以，选项B正确。

29.

一个合法的表达式由括号()包围，括号()可以嵌套和连接，如(())()也是合法的表达式。现有6对括号()，它们可以组成的合法表达式的个数为______A.15B.30C.64D.132正确答案：D[考点]排列组合与概率[解析]本题中，可以把左括号看作1，右括号看作0，这些括号的组合就是01的排列。此时需要满足从第一个数开始的任意连续子序列中，0的个数不多于1的个数，也就是右括号的个数不多于左括号的个数。

假设不考虑这个限制条件，那么全部的01排列共有C(2n,n)种，也就是一半为0，一半为1的情况。需要注意的是，最终的结果还需要考虑一些不符合项的内容。

在任何不符合条件的序列中，找出使得0的个数超过1的个数的第一个0的位置，然后在导致并包括这个0的部分序列中，以1代替所有的0并以0代表所有的1，结果总的序列变成一个有(n+1)个1和(n-1)个0的序列，而且这个过程是可逆的。也就是说，任何一个由(n+1)个1和(n-1)个0构成的序列都能反推出一个不符合条件的序列。所以，不符合条件的序列个数为C(2n,n-1)，合法的排列数为C(2n,n)-C(2n,n-1)=C(12,6)-C(12,5)=132。因此，选项D正确。

30.

某团队有2/5的人会写Java程序，有3/4的人会写C++程序，那么这个团队里同时会写Java程序和C++程序的至少有______人A.3B.4C.5D.8正确答案：A[考点]排列组合与概率[解析]本题中，2/5中的5和3/4中的4的最小公倍数为20，所以，会Java语言的至少有8个人(也可能是8的若干倍)，会C++语言的有15个人(也可能是15的若干倍)。那么，同时会使用Java语言和C++语言的人至少有8+15-20=3个，所以，至少有3个人同时会Java语言和CH语言。因此，选项A正确。

31.

甲乙两路公交车间隔均为10分钟，公交车发车时刻的分钟数个位分别是1和9，那么对于一个随机到达的乘客，他乘坐甲车的概率为______A.0.1B.0.2C.0.3D.0.9正确答案：B[考点]排列组合与概率[解析]本题中，对于一名乘客而言，每10分钟里面，如果他在时间区间[0,1)或[9,10]内到达公交站，那么他会乘坐公交车甲，因此他坐甲车的概率p为0.2。如果他在时间区间[1,9)内到达公交站，那么他会乘坐公交车乙，因此他乘坐乙车的概率q为0.8。所以，选项B正确。

32.

假设下图中每个正方形的边长为1，则从A到Z的最短路径条数为______

多个正方形A.11B.12C.13D.14正确答案：C[考点]排列组合与概率[解析]本题中，假设为题图的左下角与右上角补充两个小正方形，那么此时从点A到点Z需要横着走4格，竖着走2格，此时最短路径有C(6,2)或C(6,4)种情况，即(6×5)/2=15种情况。当然，最终结果不是15，由于整个图形补充了两个缺口，所以，必须在15的基础上减去2，最终结果为15-2=13。因此，选项C正确。

33.

袋中有红球、黄球和白球各一个，每次任意取一个放回，如此连续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个棋子，如果是通过旋转得到的则只能算一种排列方式，那么一共有______种染色情况A.10B.11C.14D.15正确答案：C[考点]排列组合与概率[解析]本题中，假设两种颜色分别是黑色与白色，默认情况下是白色，考虑到通过旋转得到的形式只能算为一种，那么，用P(n)表示有n个黑棋的种类，此时可以得出以下结论：

(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.

某城市发生了一起汽车撞人逃跑事件，该城市只有两种颜色的车，其中白色车占15%，黑色车占85%。事发时有一个人在现场看见似乎是一辆白色的车，但是根据专家在现场分析，在当时那种条件能看清楚的可能性是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名同学争夺3项比赛的冠军，若每项比赛只设1名冠军，则冠军的可能情况有______A.120种B.130种C.60种D.125种正确答案：D[考点]排列组合与概率[解析]本题中，由于没有明确规定各项比赛的冠军不能是同一个人，所以每一个冠军头衔都可能有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枚，假设取得最后石子的玩家为赢。若甲先取，则______A.谁都无法取胜B.乙必胜C.甲必胜D.不确定正确答案：C[考点]排列组合与概率[解析]很显然，只要先取的人保证最后剩8枚，无论后取的人取几枚石子(如果后取石子的人取2枚，则先取石子的人取6枚：如果后取石子的人取4枚，则先取石子的人取4枚；如果后取石子的人取6枚，则先取石子的人取2枚)，先取石子的人都可以取得胜利。

所以，只要先取的人能够保证最后剩余8枚即可保证自己获得胜利。那么，问题来了，如何保证呢?其实很简单，只要保证每一个回合内取的数是一个可控的固定数即可，显然，8就是这个固定数。先取的人只需要保证第一次取完后，剩下的数字是8的倍数，以后无论后取的人怎么取，只要先取的人取的石子数与后取的人取的石子数相加为8，就一定能胜。100%8=4，所以，本题中，只需要甲先取4枚石子，然后在后续的取数中，每一个回合所取数与上一个回合乙所取数之和为8，就能保证取胜。因此，选项C正确。

二、简答题1.

如何实现链表的逆序?正确答案：链表作为最基本的数据结构，它不仅在实际应用中有着非常重要的作用，而且也是程序员面试笔试中必考的内容。具体而言，它的存储特点为：可以用任意一组存储单元来存储单链表中的数据元素(存储单元可以是不连续的)，而且，除了存储每个数据元素ai外，还必须存储指示其直接后继元素的信息。这两部分信息组成的数据元素ai的存储映像称为结点。N个结点连在一块被称为链表，结点只包含其后继结点信息的链表就被称为单链表，而链表的第一个结点通常被称为头结点。

对于单链表，又可以将其分为有头结点的单链表和无头结点的单链表，如下图所示。

有头结点和无头结点

在单链表的开始结点之前附设一个类型相同的结点，称之为头结点，头结点的数据域可以不存储任何信息(也可以存放线性表的长度等附加信息)，头结点的指针域存储指向开始结点的指针(即第一个元素结点的存储位置)。

具体而言，头结点的作用主要有以下两点：

(1)对于带头结点的链表，当在链表的任何结点