阿里2014实习生招聘
问：某国家非常重男轻女，若一户人家生了一个女孩，便要继续生，直到得到男孩为止。假设生男生女概率相等，请问平均每户人家有（1）个女孩。
答：此题即高数中的级数。
引申：
int f(int x){
int s=0;
while(x--) s+=f(x);
return max(x,1);
}
//若调用f(35),此程序运行时间（）
若调用f(35),主流PC上此程序运行时间（D）
A.几毫秒 B.几秒 C.几分钟 D.几小时
答：函数调用--复杂度
f(1)-1;f(2)-1;f(3)-2;f(4)-4;f(5)-8;f(6)-16;...;f(n)=pow(2,n-2);
f(35)=pow(2,33)=O(pow(10,9)),主流计算机一秒执行语句数O(pow(10,6)),一小时=O(pow(10,3)秒,相除得1,所以在小时级别。
问：将n条长度均为m的有序链表进行合并，合并以后的链表也保持有序。时间复杂度为多少？
答：
思路一：对长度为a和b的有序表进行归并，复杂度是Ｏ（ａ＋ｂ）。构造n个权重均为m的叶结点，对其构造最优二叉树。则树中所有非叶结点的权值和即为所求。答案为O(n*m*log(下标：2)(真数：n)).
引申：
对长度为n的无序数组（链表同样适用）进行二路归并排序，复杂度为n*log(n).
分析：对长度为a和b的有序表进行归并，复杂度是Ｏ（ａ＋ｂ）。
每趟归并将有序表的数目减少一半，初始可视为n个长度为1的有序表，所以共
lg(n)/lg(2)趟归并。
每趟归并，调用n/(2*length)次归并函数将n/length个长度为length的有序表进行两两归并。每次归并复杂度是Ｏ（2*length）。所以每趟归并复杂度是O(n)。
总的复杂度为O（n*log(n)）。
思路二：等价于n*m个元素，初始状态无序，归并到log(下：2)(真：m)趟时，后续的复杂度。
问：ABCD四人夜里要过一座桥，每次最多过两人，过桥必须有手电筒。他们只有一只手电筒，四人过桥时间分别是1、2、5、10。问：安排最优方案，使过桥时间最短。
答：时间长的一块过，相当于并行处理，效率高。所以：AB-A-CD-B-AB=2+1+10+2+2=17min.
有两个链表A和B，试求其首个公共结点的地址。
问：判断一棵树是否是完全二叉树的算法：
答：完全二叉树具有性质——如果一个结点没有左子树，那么它一定没有右子树。利用此性质，在广度优先搜索中对遍历结点逐一判断。
问：八个人的单打比赛，选手编号由强至弱为1~8，当实力相差两个等级内（含）才有爆冷门的可能。也就是说8号存在打败6号的可能。这八个人进行1/4决赛、半决赛和决赛。问所有可能夺冠的选手中，编号最大的是几号？（6）
答：尚没发现通用解法。
问：2的100次方mod 7等于（2）。
答：公约数只有1的两个数，叫做互质数。
mod,取余数运算符，7 mod 5=2;c++中为‘%’运算符。
费马小定理：a是整数，p是质数，且a,p互质，则[a的(p-1)次方mod p]恒等于1。
此题有pow(2,6)%7=1。pow(2,100)=(2的6次方)的16次方*2的4次方，故答案为16 mod 7=2。
所谓两棵二叉树T1与T2相似，是指
1.都是空树；
2.都只有根结点；
3.T1左子树和右子树与T2左子树和右子树均相似。
验证算法:
bool is_similar(node*t1,node*t2){//判断两棵树是否相似
if(!t1&&!t2) return true;
if(!t1||!t2) return false;
if (is_similar(t1->lchild,t2->lchild)&&\
is_similar(t1->rchild,t2->rchild))
return true;
return false;
}
问：【2012研招真题】在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束都至少能够确定一个元素最终位置的方法是（A）
a.简单选择排序 b.希尔排序c.快速排序d.堆排序e.二路归并排序
A.acd B.ace C.bcd D.cde
答：简单选择排序每次都选择未排序列中最小的元素放入最终位置。
希尔排序每次是对等步长的序列进行排序，得到的是局部有序。
堆排序，每趟堆顶的元素就是待排序列中最大或最小的（大根堆或小根堆)。
快速排序每趟后都将基准元素放入到最终位置。
归并排序会得到若干局部有序结果。
跳跃链表是一种随机化数据结构，基于并联的链表，其效率可比拟于二叉查找树(对于大多数操作需要O(log n)平均时间)，并且对并发算法友好。
跳跃列表是按层建造的。底层是一个普通的有序链表。每个更高层都充当下面列表的"快速跑道"，这里在层 i 中的元素按某个固定的概率 p 出现在层 i+1 中。平均起来，每个元素都在 1/(1-p) 个列表中出现，而最高层的元素(通常是在跳跃列表前端的一个特殊的头元素)在 O(log1/pn) 个列表中出现。
查找的总体代价是 O(log1/p n/p).
如果某系统15*4=112成立，则系统采用的是（6）进制。
答：设为x进制。由题得(x+5)*4=x*x+x+2,解得x=6.
设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W},请写出按二路归并方法对该序列进行一趟扫描后的结果，为？
答：D，Q，F，X，A，P，B，N，M，Y，C，W；
共12个元素，第一趟实现两两有序，共12/2=6对。
关键码序列{Q,H,C,Y,Q,A,M,S,R,D,F,X}，要求递增排序，若采用初始步长为4 的希尔排序，则一趟扫描的结果是？
若采用以第一个元素为基准的快速排序，则一趟排序的结果为？
答：Q,A,C,S,Q,D,F,X,R,H,M,Y;(1,5,10有序，2,6,11有序，...)
F,H,C,D,Q,A,M,Q,R,S,Y,X。(要细心)
