2012创新工场校园招聘笔试题

1，以下关于面向对象的描述错误的是：

A：面向对象的基本特性是封装，继承和多态

B，构造函数不可以是虚函数，析构函数可以是虚函数

C，子类重新定义父类虚函数的方法叫做重载

D，多态是为了接口重用，封装和继承是为了代码重用

2，在分时操作系统中，进程调度采用（）算法

A，先来先服务（用于作业，进程调度）

B，最到优先权（批处理系统多用，也可用于实时系统）

C，时间片轮转（分时系统多用）

D，随机

3，以下哪个字符串不能被正则表达式a(bc?)d匹配到？

A，abc  B，abd  C，abc  D ,acd

4，以下关于多线程的叙述错误的是：

A,线程同步的方法包括使用临界区，互斥量，信号量等

B,两个线程同时对简单类型全局变量进行写操作也需要互斥

C，实现可重入函数时，对自动变量也要用互斥量加以保护

D，可重入函数不可以调用不可重入函数

5，以下哪种排序是不稳定排序：

A，冒泡 B，插入排序 C，归并排序 D，快速排序

6，若串=’software’，其子串数目为：

A，8 ，B，37  C，36，D，9

7，某系统中有3个并发进程，都需要同类资源4 个，试问该系统不会发生死锁的最少资源数是：

A，9， B，10， C，11 D，12

8，HASH函数冲突处理方式不包括以下哪一项：

A，开放定址法 B，链地址法 C，插入排序法 D，公共溢出区发

9，有ABCDEF 六个城市，每一个城市都和其他所有城市直接相连，问从A——B有多少种连接方式，路径不允许在两个城市之间往返

A，78 ，B,65 ，C43 ，D，以上都错

10，,100101110换算成十进制应该是：

1.求两个大于2的31次方的整数的乘机，只能使用32位整数且给出精确结果。

答案:1.定义三个int数组a,b,c;存放2个乘数和最后的乘积。将十进制的两个数存放在a,b中，然后用一个嵌套循环将a[]b[]按位相乘，将结果放到c[]中相应的位置上，再进行一些进位的简单处理就可得到最终结果。(譬如99*99,则a[0]=9,a[1]=9,b[0=9],b[1]=9;那么第一步a[0]*b[0]=81放入c[0]和c[1]中，c[0]=1,c[1]=8;a[0]*b[1]=81,放入c[1]和c[2]中，则c[1]=8+1=9,c[2]=8;以此类推)

2.一篇文章有n（10<n<100）个段落，第i个段落有number[i]个单词，设计算法，不得调用库函数，找出第m个单词属于第几个段落，查询共有k（k>10000）次，说明时间复杂度。（段落编号从0开始）

答案：1，.定义一个线性表，下标是单词个数，内容是该单词所属的段落，这样直接查询线性表第m位置的内容，时间复杂度为O(1)，不过单词数多耗费空间大。或者用二分查找，定义一个数组，下标为段落，内容为该段落以及之前段落所有单词数量总和，时间复杂度O（log2n）,空间占用低。

2，List<Integer> wordToPara = new ArrayList<Integer>();
int p = 0;
for(int i=0;i<n;i++) {
for(int j=0;j<number[i];j++) {
wordToPara[p] = i;
p++;
}
}

int whichWord = scanner.nextInt();
System.out.println(wordToPara.get(whichWord));

预处理：时间复杂度：单词总个数
查询：时间复杂度：O(1)
空间复杂度：单词总个数。

3.A,B,C,D,E五个人捕鱼后已凌晨，大家便睡觉。早上A第一个醒来，将鱼均分成五份，把多余的一条鱼扔掉，拿走自己的一份，B第二个醒来，也将鱼均分为五份，把多余的一条鱼扔掉，拿走自己的一份。CDE依次醒来，也按同样的方法拿鱼，问他们合伙至少捕了几条鱼。

答案：1，.总共6条鱼往上穷举。

2，暴力破解的

至少要3121鱼
最初有3121条鱼
第1个人丢掉了1条鱼，剩余3120条鱼，分成5份，每份624条,他拿走了624条，剩余2496条
第2个人丢掉了1条鱼，剩余2495条鱼，分成5份，每份499条,他拿走了499条，剩余1996条
第3个人丢掉了1条鱼，剩余1995条鱼，分成5份，每份399条,他拿走了399条，剩余1596条
第4个人丢掉了1条鱼，剩余1595条鱼，分成5份，每份319条,他拿走了319条，剩余1276条
第5个人丢掉了1条鱼，剩余1275条鱼，分成5份，每份255条,他拿走了255条，剩余1020条

public class DividingFish {

public static void main(String[] args) {

int begin = 1;
int mans = 5;
int beforeDivide = 0;
int each = begin;

while (mans > 1) {

beforeDivide = each * 5 + 1;

if (beforeDivide % 4 == 0) {
mans--;
each = beforeDivide / 4;
}

else {
mans = 5;
begin += 2;
each = begin;
}

}

System.out.println("至少要" + (beforeDivide * 5 / 4 + 1) + "鱼");

displayDividing(beforeDivide*5/4+1);
}

public static void displayDividing(int fishnum) {
System.out.println("最初有" + fishnum + "条鱼");
for (int i = 1; i <= 5; i++) {
System.out.println("第" + i + "个人丢掉了1条鱼，" +
"剩余" + (fishnum - 1) + "条鱼，" +
"分成5份，每份" + (fishnum - 1) / 5 + "条," +
"他拿走了" + (fishnum - 1) / 5 + "条，" +
"剩余" + (fishnum - 1) / 5 * 4 + "条");
fishnum = (fishnum - 1) / 5 * 4;
}
}

}

3，class Div {
public static void main(String [] args){
int f = 6;
int p = 5;
boolean bingo = false;
do{
int i = f, j=1;
for(; j<=p; j++){
if((i - 1)%p != 0){
f++;
break;
}else{
i = (i - 1)*(p-1)/p;
}

}
if(j == p+1)
bingo = true;
}while(!bingo);

System.out.println(f);
}
}

4，public class test3 {
public static void main(String[] args){
int x=6;
while(!Num(x)){
x++;
}
System.out.println(x);
}
public static boolean Num(int n){
int k=n;
for( int i=0;i<5;i++){

if((k-1)%5==0&&k>5){
k=((k-1)/5*4);
}
else{return false;}
if(i==4&&k>5)return true;
}
return false;
}

}

输出：3121

5，package com.tang.study;

public class Fish {
public static void main(String[] args) {
System.out.println(getFish(5));
}

public static int getFish(int m) {
int nums = 6;
while (true) {
if (isOK(nums, m)) {
break;
}
nums++;
}
return nums;

}

private static boolean isOK(int nums, int m) {
if (m == 0) {
return true;
}
if (nums % 5 != 1) {
return false;
} else {
nums = nums - (nums - 1) / 5 - 1;
return isOK(nums, m - 1);
}
}
}
result:3121

6，两种思路，一种从初始总鱼数开始枚举，另一种从最后剩下的鱼数开始枚举。第一种从6开始递增，步进值为5（至少要过了第一次划分）；第二种从4开始递增，步进值为4（同理，剩下的是四份，需要被4整除）。

7，我说下我的思路吧，我首先用暴力破解，得出结果是３１２１，然后又试着分析了一下，发现可以从不同的角度以很简单的方法解出这道题。
　　假设最后e分后还剩x条鱼，那么d拿鱼后，还剩5/4x+1,那么c分后还剩5/4(5/4x+1),...依些类推，可以推出a分之前的总鱼数为pow(5/4,5)x+pow(5/4,4)+pow(5/4,3)+...+1;后面就是等比数列，可以手算，4*pow(5/4,5)-4;所以总结果为pow（5/4,5）*(x+4)-4,所以这个问题在这里已经水落石出了，就是求得x+4可以整除pow(4,5)的最小数，pow(4,5)=1024,所以最后至少剩102４-4＝1020条鱼，总的结果代入进去即可，为pow(5,5)-4=3121条鱼。

8，public class Fish {

public static void main(String args[])
{
int personNum = 5;
int fishNum = personNum + 1;

while(true)
{
int tempPersonNum = personNum;
int tempFish = fishNum;

while(tempPersonNum > 0)
{
if(tempFish <= personNum || tempFish % personNum != 1)
{
fishNum += 1;
while(fishNum % personNum != 1)
{
fishNum++;
}
break;
}

tempFish -= (tempFish / personNum + 1);
tempPersonNum--;
}

if(tempPersonNum == 0)
{
break;
}
}

System.out.println(fishNum);
}

}

9，c++版本：

#include <iostream>

int fish(int total_num);

int main()
{
std::cout << "total number = " << fish(1) << std::endl;
return 0;
}

int fish(int total_num)
{
int tmp_num = total_num;
int man_num = 5;

while(man_num > 0)
{
if( (tmp_num - 1) % 5 )
{
man_num = 5;
++ total_num;
tmp_num = total_num;
continue;
// return fish( total_num + 1 );
// if{}里面换成这个就是递归，不过还可以改改，不必要写这么多。
}

tmp_num = (tmp_num -1) * 4 / 5;
-- man_num;
}

return total_num;
}