淘宝2011春季实习生笔试题
<div class="Section0">1. 现有千兆光纤连接机器A和B ,机器A提供web网页服务,网页大小1K字节,机器B通过浏览器下载,求最有可能下载速度的最大上限;（C）C> 100000页/秒
光纤的上行和下行是一样的:要知道网络传输速度一定要明白网络传输速度的单位。我们一般说的百兆、千兆网络的单位是bps（比特率，即位/秒，bit /s），比如我们说网卡或光纤的传输速度是百兆，也就是100Mbps的意思。而在实际应用中（Widnwos、网际快车、迅雷等）使用的传输单位是字节 /秒（Byte/s)。电脑中1字节=8位，因此100兆的光纤速度等于12.5MB/s(即100Mbps/s除以8）
2. 单链表中每个节点中包括一个指针link,它指向该节点的后继节点。现要将指针q指向的新节点插入到指针p指向的单链表节点之后，下面的操作序列中哪一个是正确的？（C）
C> q->link=p->link;p->link=q;
3. 假设地图上每个国家都用矩形表示，那么最少用（4）种颜色着色，使得有共同边界的国家都披上不同颜色？
4.快速排序算法的时间复杂度为O( nlog2n),但在（A）情况下，该算法效率近似O(n2)
A> 初始序列有序或基本有序
5.若有声明：int I,j ==2,*p=&I;则能完成i=j赋值功能的语句是（B）
A) i=*p; B) * p =*&j; C) i=&j; D) i=**p;
解释：
A) i=*p; (*p)即为i，也就是i=i，错。。
C) i=&j; 将变量j的地址赋给i，错。。
D) i=**p; (*p)是个整型变量i，*(*p)就不知道是什么东西了，语法不对，错。。
B) *p就是i，*&j就是*(&j)，也就是j，整个语句就是i=j。。对
6.有宏定义“defineF(a,b) a*b”,那么“F(3+6,8--5)”的值为（B）
A.27 B.46 C.67 D.21
7.一个栈的入栈顺序是1,2,3，……n,如果出栈序列的第一个元素是n,那么输出第i()个元素害是（B）
A不确定 B.n-i+1 C.1 D,n-i.
8.已知一算术表达式的中缀形式为A+B*C-D/E,后缀表达式为ABC*+DE/-,其前缀形式为（D）
A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE
9.线性表L=（a1,a2,......an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均要移动的元素个数是 (n-1)/2
10.找到数组中第二大元素
Data中包含的都是正整数，count表示data 中元素的个数，count>1
思路：
最大值=data，次大值=data，遍历一次，每次比较并更新次大和最大值。最后可以得第二大值，适用于前N大问题，N非常小的情况。
Int find(int data[],int count)
{
Int number = data;
Int result = data;
For(int i =1 ; i<count;i++)
{
If(data>number)
{
Result = number;
Number = data;
}
Else
{
If(data>result)
Result=data;
}
}
Return result;
}
11.假定x=9999,下面函数的返回值是 8
统计1的个数
-------------------------------------
int func(int x)
{
int countx = 0;
while(x)
{
countx++;
x = x&(x-1);
}
return countx;
}
假定x = 9999
10011100001111
答案: 8
思路: 将x转化为2进制，看含有的1的个数。
注: 每执行一次x = x&(x-1)，会将x用二进制表示时最右边的一个1变为0，因为x-1将会将该位(x用二进制表示时最右边的一个1)变为0。
12.有以下定义和语句
Int a={1,2,3,4,5,6},*p
P=a;
则*(p+1)所代表的数组元素是 4
*（p+1)代表的数组元素a=4;
*p;这个相当于同时定义了三个指针变量，而第一个指针变量p指向了
第一行的起始地址，也就是a，所以*（p+1)相当于*（a+1)
也就是a=4了
13.现有米7公斤，并有一个50克和200克的砝码，请问要称出1350克得米，最少需要几次？如何用程序找到最少的步骤？
答案一：最少三次，写不出代码，望交流
第一次左边200g+50g砝码称250g的米
第二次左边 200g砝码+250g的米，称450g的米
第三次左边 200g砝码+450g的米，称650g的米
答案二：六次 ，递归算法
14.把N个鸡蛋放到M个篮子里，每个篮子不能为空，要满足：任意给出一个不超过N的数量，都能找到其中某几个篮子的鸡蛋和等于它。请写一个程序，输入N,M，然后输出所有鸡蛋的方法。
这个完全没有思路，期待交流。
15.大家知道，在淘宝的每一笔交易，买家和卖家都可以向对方做一个评价。开始时用一张评价信息表来存储这些评价信息。随着业务的增长，这些数据量和访问量都增加了很多。想问一下，如何设计来支撑更高的数据量和访问量呢？
提示：从功能上，每个淘宝用户都需要看到自己对别人的评价以及别人对自己的评价，需要能够对交易的对方做出评价。你可以考虑方库分表、考虑使用缓存。可以引用搜索，但是需要你能够描述清楚你设计的结构，以及这样带来的好处，并且你的架构是能真正运转起来的。
期待指点。
页:
[1]