阿里巴巴2016校园招聘 研发工程师（二）详解

##单选题
#####1、使用KMP算法在文本串S中找模式串P是一种常见的方法。假设S=P={xyxyyxxyx}，亦即将S对自己进行匹配，匹配过程中正确的next数组是____。

A. 0,1,1,2,2,1,2,2,3
B. 0,1,2,2,3,1,2,2,3
C. 0,1,1,2,3,1,2,2,3
D. 0,1,1,2,3,1,1,2,3
E. 0,1,2,2,3,1,1,2,3
F. 0,1,2,2,2,1,1,2,3

######解析：
$KMP$ 算法中的 $next[]$ 是起到失配时回跳的功能，在一定程度减少进行多余的匹配，$next[]$ 是根据模式串 $P$ 生成的，所以这里 $S$ 是什么并不是重点。

这个问题有一个小瑕疵，那就是如果 $next[0]$ 设置不同值，后续生成的 $next[]$ 也会不一样，虽然不一样，但是这同样都是 $KMP$ 算法生成的正确的 $next[]$。

如果说，$next[0]$ 设置为 $-1$ 来表示不存在相同最大前缀，那么 $next[i]$ 是满足 $x[i-next[i]\sim i-1]=x[0\sim next[i]-1]$ 的最大值（就是 $x$ 的自身匹配）。

这样通过 $KMP$ 则会生成一个 $-1,0,0,1,2,0,1,1,2$ 的 $next[]$，可是显然，选项中不存在这个选项，并且清晰的可以看到，所有选项的第一项都是 $0$，所以也就意味着默认 $next[0]=0$，那么我们只需要对上述的 $next[]$ 整体偏移（自增）一即可得到本题中正确的 $next[]$。

i	0	1	2	3	4	5	6	7	8
P	x	y	x	y	y	x	x	y	x
next	0	1	1	2	3	1	2	2	3

那么前面所说的 $next[]$ 满足的条件也随之有略微的改动：$next[0]$ 设置为 $0$ 来表示不存在相同最大前缀，那么 $next[i]$ 是满足 $x[i-next[i]+1\sim i-1]=x[0\sim next[i]-2]$ 的最大值。

只要记住这个条件，这种类型的问题都将迎刃而解。

#####2、将整数数组（7-6-3-5-4-1-2）按照堆排序的方式原地进行升序排列，请问在整个排序过程中，元素3的数组下标发生过____次改变。

A. 0
B. 1
C. 2
D. 3
E. 4
F. 5

######解析：
堆排序的过程主要分为三步：
一：将原序列建成大根堆（小根堆），初始化为无序区；
二：将根与无序区最后一个元素交换，交换后的最后一个元素变成有序区，当所有都变成有序区时结束；
三：调整无序区变为合法的大根堆（小根堆），返回第二步，继续操作。

在这里，我们需要按照升序排序，所以需要用到大根堆，这样每次都会将无序区最大后移，保证大的放后边。

具体过程如下：
7 6 3 5 4 1 2，初始序列满足大根堆
2 6 3 5 4 1 7，交换
6 5 3 2 4 1 7，调整
1 5 3 2 4 6 7，交换
5 4 3 2 1 6 7，调整
1 4 3 2 5 6 7，交换
4 2 3 1 5 6 7，调整
1 2 3 4 5 6 7，交换
3 1 2 4 5 6 7，调整，移动一次
2 1 3 4 5 6 7，交换，移动两次
2 1 3 4 5 6 7，调整
1 2 3 4 5 6 7，交换
1 2 3 4 5 6 7，调整
1 2 3 4 5 6 7，交换，所有无序区均变为有序区

从这个过程我们会发现，一共移动了两次，但是也许你也发现了中间早就已经存在一次完美的升序情况，后边却依然多此一举要调整，那是因为此时无序区依然存在，就像最后两次操作，已经有序了却依然要执行，因为还有一个位置是无序区。

#####3、某程序猿每天接老婆下班回家。他在6点准时下班从公司开车出发，由于路上可能存在的堵车情况，到老婆公司门口的时间点均匀的分布在6点20到6点30之间。老婆根据他的下班时间做了估计，到公司门口的时间点均匀的分布在6点25到6点30之间，如果他比老婆晚到公司门口将会挨骂，那么他被骂的概率是____。

A. 1/4
B. 1/3
C. 1/2
D. 2/3
E. 3/4
F. 以上都不对

######解析：
由于均匀分布，程序员有一半可能性在 $6:25\sim 6:30$ 之间到，而老婆百分之百可能性在 $6:25\sim 6:30$ 到，在这个时间段儿程序员先到的可能性等于老婆先到的可能性，也是一半，所以一半的一半，也就是 $\frac{1}{4}$。

#####4、A为整数数组， N为A的数组长度，请问执行以下代码，最坏情况下的时间复杂度为____。

void fun(int A[], int n) {                                                                       
    for (int i = n - 1; i >= 1; i--) {                                                          
        for (int j = 0; j < i; j++) {                                                            
            if (A[j] > A[j+1]) {                                                                
                int tmp = A[j + 1];                                                              
                A[j + 1] = A[j];
                A[j] = tmp;
         }
      }
   }
}

A. O(N)
B. O(N^2)
C. O(Nlog(N))
D. O(log(N))
E. O(N^3)
F. 无法确定

######解析：
这是一个简单的从小到大排序的函数，不管是否是最坏情况，复杂度均为 $O(n^2)$。只能说，最坏情况下，交换次数多一些，对比次数是不会增多的。

也可以用数学来证明，$n-1+n-2+n-3+\dots +3+2+1$，等差数列求和 $\frac{n\ast (n-1)}{2}$，拆开也就是 $\frac{n^2}{2}-\frac{n}{2}$，忽略低次幂以及常数项，最后复杂度是 $O(n^2)$。

#####5、有一个单向链表队列中有一个A、B两个相邻元素，有一个指针p指向元素A，现将一个指针r指向的S元素要插入到A和B之间，该进行操作____。

A. p->next=p->next->next
B. r->next=p;p->next=r->next
C. r->next=p->next;p->next=r
D. r=p->next;p->next=r->next
E. r->next=p;p->next=r
F. p=p->next->next

######解析：
将一个元素插入只需要两步，先将 $r\text{->}next$ 指向 $B$，再将 $p\text{->}next$ 指向 $r$ 即可。

#####6、A、B、C、D四人应聘一个程序员职位，此职务的要求条件是：Java熟练；懂数据库开发；会Web开发；有Ｃ++经验。谁满足的条件最多，谁就被雇用。（1）把上面四个要求条件两两组合，每个组合都恰有一人满足。同时已知（2）A和Bjava熟练（3）B和C会Web（4）C和D懂数据库（5）D有C++经验那么，被雇用的是____。

A. A
B. B
C. C
D. D
E. 四人机会均等
F. 以上均错

######解析：
一个十分考验思维逻辑的题。按照原题给定条件我们可以首先确定，$Java和Dataase$、$Java$ 和 C++、$Web$ 和 C++ 是没有对应人的，那么一定有人还掌握着其他技能。

所以经过推导可以得到：

*	A	B	C	D
Java	Y	Y	N	N
Web	N	Y	Y	N
Database	Y	N	Y	Y
C++	N	Y	N	Y

#####7、在1,2,3,…1000中，有____个数各位乘积为0。

A. 100
B. 101
C. 172
D. 181
E. 190
F. 191

######解析：
如果这是一个编程题，那么就是数位 $dp$ 了，可是这是一个选择题，并且是笔试题，那么应该不会给我们跑程序的机会吧~~~

所以就自己手算一下吧……我们先算一下 $1\sim 100$，一共有 $10$ 个，$101\sim 200$ 则有 $19$ 个，后边也是，则最后答案是 $10+19\ast 9=181$ 个。

#####8、某单链表有5个元素，设单链表的节点结构为(data,next)，5个元素的data依次为（1、2、3、4、5），已知指针q指向节点3，指针p指向节点4，那么下面操作能将链表变为data依次为（1、2、3、5）的是____。（其中temp为节点类型指针，默认指向NULL）

A. q=p->next;
B. p=q->next;
C. p->next=q->next;
D. q->next=p->next; delete q;
E. p->data=p->next->data; p->next=p->next->next; delete p->next;
F. temp=p->next; p->next=temp->next; p->data=temp->data; delete temp;temp=NULL;

######解析：
根据题意，我们需要删除一个结点 $4$，或者将 $5$ 拷贝到 $4$，然后删除原本的 $5$。

$A、B、C$ 很明显是错误的，$D$ 的第一步是对的，但是第二步删除的应该是 $p$，$E$ 的前两步是对的，企图拷贝然后删除多余的，可是删除时，$p$->$next$ 已经改变了，为 $NULL$，显然无法删除最后一个多余的结点，故，选 $F$。

#####9、以下函数中，和其他函数不属于一类的是____。
A. strcpy
B. strncpy
C. snprintf
D. strcat
E. strtok
F. strncat

######解析：
这个题略微有些常识都能做对，我们完全不必知道每个函数是做什么的，众所周知，凡是一类函数，一般都是位于同一个库的，并且函数名有很大可能性具有相同前缀（并不是绝对）。

针对于这道题，我们的关键不在于自己记了多少函数的功能，因为库太庞大了，很多东西我们可能完全不会用到，所以没有必要什么都记得，不然要文档做什么？

这里除去 $C$ 选项外，都是字符串操作函数，很明显的特征是 $str$ 前缀，所以不用迟疑，秒选 $C$。

#####10、已知二叉树中有45个叶节点，有25个度为1的节点，则二叉树的总结点数为____。

A. 112
B. 113
C. 114
D. 115
E. 116
F. 117

######解析：
计算节点数有一个公式需要熟记，$N0=N2＋1$，即叶子节点数等于度为 $2$ 的结点数 $+1$。

所以本题，根据叶子节点数计算得到度为 $2$ 的结点数 $44$ 个，总结点数 $=45+25+44=114$。

#####11、将1,2,3,…,99,100任意排列成一个圈，相邻两数的差的绝对值求和最多为____。

A. 100
B. 198
C. 200
D. 500
E. 2500
F. 5000

######解析：
一个贪心问题，想要最大，我们可以采取将所有未选择数中的最大值与最小值两两排在一起重新排列的策略，即按照 $100,1,99,2,98,3...51,50$ 排列首位衔接成环，最后答案则是 $99+98+...+2+1+50=5000$。

#####12、在一个100人的团队活动中，主持人小猿亮出了一幅裙子的照片，大喊：”看出蓝黑色的举手！“，团队中有45人举手，然后小猿又喊：”看出白金色的举手！“，团队中有40人举手。机灵的小猿发现，有人从未举过手，有人举手了两次，两轮举手分出的四类人的数目恰好构成一个等差数列。请问有____人既能看出蓝黑色又能看出白金色。

A. 0
B. 15
C. 30
D. 35
E. 50
F. 55

######解析：
举手为 $Y$，不举手为 $N$，总共有四种状态，$NN,NY,YN,YY$。

由题可知，$YN+YY=45,NY+YY=40,NN+NY+YN+YY=100$。

这里存在一个坑点，题目说的四个状态指的是啥也没看到、看到黑色、看到金色、既看到黑色又看到金色的，即 $NN,YN+YY,NY+YY,YY$。

所以我们能够得出：$NN=100-(45+40)+YY=15+YY$，
那么四个状态则可以表示为 $15+YY,40,45,YY$，显然 $YY<40$，等差 $d<=5$，等差数列一定是 $YY,40,45,YY+15$，则 $YY=35$。

#####13、某操作系统采用分页存储管理方式，下图给出了进程A的页表结构。如果物理页的大小为512字节，那么进程A逻辑地址为0x0457（十六 进制）的变量存放在____号物理内存页中。
#####进程A页表：
| 逻辑页 | 物理页 |
| : - : | : - : |
| 0 | 9 |
| 1 | 2 |
| 2 | 4 |
| 3 | 6 |
| 4 | 5 |

A. 9
B. 2
C. 4
D. 6
E. 8
F. 5

######解析：
首先，我们需要计算的是，$0x0457$ 的二进制是 $0000010001010111$，由于每页是 $512$ 字节，也就是九位二进制，所以我们可以忽略后九位二进制，因为这是页内地址，摘出来 $0000010$，我们很容易得到它是位于第二个逻辑页，对应的物理页则是 $4$ 号。

#####14、有一个扔骰子得返现的游戏：你扔一个骰子，扔到多少就可以得到和点数相同的返现。例如你扔到3，可以得到3元返现；扔到1，可以得到1元返现。当你扔完第一次骰子，看到点数后，你需要做出如下选择：
#####一：拿这个点数对应的返现，放弃扔第二次骰子；
#####二：再扔一次骰子，但此时你只能拿第二次扔的点数对应的返现。
#####那么，玩一轮这个游戏的期望收益是____元。

A. 3.5
B. 3.75
C. 4
D. 4.25
E. 4.5
F. 4.75

######解析：
题目没有明确说明什么时候放弃继续扔，所以我们按照使期望最大来操作。

如果第一次扔的是 $1$，那应该重新扔，因为重新扔大于 $1$ 的概率为 $\frac{5}{6}>\frac{1}{2}$，同理如果是 $2,3$ 都应该重新扔；如果第一次扔的是 $4$，则不再扔，因为重新扔大于 $4$ 的概率为 $\frac{1}{3}<\frac{1}{2}$，同理如果是 $5,6$ 都不再重新扔。

所以最后期望为：$(0+0+0+4+5+6)\ast \frac{1}{6}+\frac{1}{2}\ast (1+2+3+4+5+6)\ast \frac{1}{6}=4.25$

#####15、袋子中分别一叠纸币，其中5元面值的纸币6张，10元面值的纸币5张，20元面值的纸币4张，从袋子中任意取4张纸币，则每种面值至少取到一张的概率为____。

A. 8/91
B. 25/91
C. 48/91
D. 53/91
E. 60/91
F. 63/91

######解析：
组合问题，分别考虑三种情况的和除以总情况数即可。

$\frac{C_6^2\ast C_5^1\ast C_4^1+C_6^1\ast C_5^2\ast C_4^1+C_6^1\ast C_5^1\ast C_4^2}{C_{15}^4}=\frac{48}{91}$

#####16、有关下述Java代码描述正确的选项是____。

public class TestClass {
   private static void testMethod(){
        System.out.println("testMethod");
   }
   public static void main(String[] args) {
        ((TestClass)null).testMethod();
   }
}

A. 编译不通过
B. 编译通过，运行异常，报NullPointerException
C. 编译通过，运行异常，报IllegalArgumentException
D. 编译通过，运行异常，报NoSuchMethodException
E. 编译通过，运行异常，报Exception
F. 运行正常，输出testMethod

######解析：
代码正确，所以编译一定通过，也不涉及什么逻辑问题，不存在什么异常，所以运行正常，调用这个函数输出 $testMethod$。

至于为什么是正确的，看如下几点：
1）此处是类对方法的调用，不是对象对方法的调用。
2）方法是 $static$ 静态方法，直接使用“类.方法”即可，因为静态方法使用不依赖对象是否被创建。
$null$ 可以被强制类型转换成任意类型（不是任意类型对象），于是可以通过它来执行静态方法。
3）非静态的方法用“对象.方法”的方式，必须依赖对象被创建后才能使用，若将 $testMethod()$ 方法前的 $static$ 去掉，则会报空指针异常 。

#####17、下列java程序的输出结果为____。

public class Example{
    String str=new String("hello");
    char[]ch={'a','b'};
    public static void main(String args[]){
        Example ex=new Example();
        ex.change(ex.str,ex.ch);
        System.out.print(ex.str+" and ");
        System.out.print(ex.ch);
    }
    public void change(String str,char ch[]){
        str="test ok";
        ch[0]='c';
    }
}

A. hello and ab
B. hello and cb
C. hello and a
D. test ok and ab
E. test ok and cb
F. test ok and c

######解析：
$Java$ 中存在两种参数的传递，分别是值传递和引用传递，基本类型和 $String$ 都是值传递，对象和数组都是引用传递，值传递不会在函数中改变参数原本的值，相当于重新创建了一个对象，而引用传递时直接在自身上修改。所以在调用 $change()$ 时，对 $str$ 没有实质性的修改，而对 $ch$ 进行了修改，输出时两者用 $"and"$ 衔接则输出 $helloandcb$。

#####18、下列 java 程序输出结果为______。

int i=0;
Integer j = new Integer(0);
System.out.println(i==j);
System.out.println(j.equals(i));

A. true,false
B. true,true
C. false,true
D. false,false
E. 对于不同的环境结果不同
F. 程序无法执行

######解析：
没什么好说的，变量 $i$ 等于 $0$，对象 $j$ 初始化为 $0$。在数值上两者是相等的，所以用 $==$ 或者 $equals()$ 判断均返回 $true$。

#####19、如果下列的公式成立：78+78=123，则采用的是_______进制表示的。

A. 11
B. 12
C. 13
D. 14
E. 15
F. 以上都不对

######解析：
这个题没什么技巧，将 $78$ 按照不同进制计算，获取答案看是否是 $123$ 即可。

按照 $11$ 进制结果是 $145$，No；
按照 $12$ 进制结果是 $134$，No;
按照 $13$ 进制结果是 $123$，Yes;
已经得到正确答案，后续的都不需要再算了。

#####20、一个长度为100的循环链表，指针A和指针B都指向了链表中的同一个节点，A以步长为1向前移 动，B以步长为3向前移 动，一 共需要同时移动多少步A和B才能再次指向同一个节点____。

A.99
B.100
C.101
D.49
E.50
F.51

#####解析：
设需要 $x$ 步，则由题可得，$x\%100=3\ast x\%100$，接着最简单的做法就是代入了。