淘宝2011春季实习生笔试题

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[0] ，次大值 =data[1] ，遍历一次，每次比较并更新次大和最大值。最后可以 得 第二大值，适用于前N 大问题， N 非常小的情况。 

Int find(int  data[],int  count)

{

     Int number = data[0];

     Int result = data[1];

     For(int i =1 ; i<count;i++)

     {

         If(data[i]>number)

         {

            Result = number;

            Number = data[i];

         }

         Else

         {

            If(data[i]>result)

               Result=data[i];

         }

     }

     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[3][2]={1,2,3,4,5,6},*p[3]

P[0]=a[1];

则*(p[0]+1) 所代表的数组元素是  4

 

*（ p[0]+1) 代表的数组元素 a[1][1]=4;

*p[3];这个相当于同时定义了三个指针变量，而第一个指针变量 p[0] 指向了

第一行的起始地址，也就是a[1] ，所以 * （ p[0]+1) 相当于 * （ a[1]+1)

也就是a[1][1]=4 了

 

 

13.现有米 7 公斤，并有一个 50 克和 200 克的砝码，请问要称出 1350 克得米，最少需要几次？如何用程序找到最少的步骤？

答案一：最少三次，写不出代码，望交流

第一次 左 边200g+50g 砝码称 250g 的米

第二次左边   200g砝码 + 250g的米 ，称 450g的米

第三次 左边    200g砝码 +4 50g的米 ，称 650g的米

答案二：六次 ，递归算法

 

 

14. 把N 个鸡蛋放到 M 个篮子里，每个篮子不能为空，要满足：任意给出一个不超过 N 的数量，都能找到其中某几个篮子的鸡蛋和等于它。请写一个程序，输入 N,M ，然后输出所有鸡蛋的方法。

  这个完全没有思路，期待交流。

 

 

15. 大家知道，在淘宝的每一笔交易，买家和卖家都可以向对方做一个评价。开始时用一张评价信息表来存储这些评价信息。随着业务的增长，这些数据量和访问量都增加了很多。想问一下，如何设计来支撑更高的数据量和访问量呢？

   提示：从功能上，每个淘宝用户都需要看到自己对别人的评价以及别人对自己的评价，需要能够对交易的对方做出评价。你可以考虑方库分表、考虑使用缓存。可以引用搜索，但是需要你能够描述清楚你设计的结构，以及这样带来的好处，并且你的架构是能真正运转起来的。

  期待指点。

评论

38 楼 pigswimming 2011-06-30  

liberD 写道

zhanghh321 写道

yizhilong28 写道

IcyFenix 写道

kimmking 写道

我靠，四色问题，竟然只是个填空。。。

改证明题，证出了封个P99

组合数学上的经典问题，呵呵，貌似还没有严格的逻辑证明哦
这些题考的基本是数学，直接上算法思想，别一上来就想编程。

这个问题不是被证明过了吗？是美国那两个人啊，他们用了好多理论据说。

不过这里就用个填空题来考擦你 估计是考你的历史知识啊  呵呵

据说七十年代就用人用计算机证明出来了。如果我没有记错的话，是当时用了1200个小时证明出来的。


百度百科上有：http://baike.baidu.com/view/6807.htm

哥们儿，你是安阳的？俺老家的啊.....

37 楼 liberD 2011-06-30  

zhanghh321 写道

yizhilong28 写道

IcyFenix 写道

kimmking 写道

我靠，四色问题，竟然只是个填空。。。

改证明题，证出了封个P99

组合数学上的经典问题，呵呵，貌似还没有严格的逻辑证明哦
这些题考的基本是数学，直接上算法思想，别一上来就想编程。

这个问题不是被证明过了吗？是美国那两个人啊，他们用了好多理论据说。

不过这里就用个填空题来考擦你 估计是考你的历史知识啊  呵呵

据说七十年代就用人用计算机证明出来了。如果我没有记错的话，是当时用了1200个小时证明出来的。


百度百科上有：http://baike.baidu.com/view/6807.htm

36 楼 satikey 2011-06-30  

pigswimming 写道

真诚的希望大家能就13--15题讨论一下

14题，可以分成蛋数为1 2 4 8 16 32 64 128 256 这样的数字，如果篮子多了的话，拆解一个数就好

35 楼 yizhilong28 2011-06-29  

zhanghh321 写道

yizhilong28 写道

IcyFenix 写道

kimmking 写道

我靠，四色问题，竟然只是个填空。。。

改证明题，证出了封个P99

组合数学上的经典问题，呵呵，貌似还没有严格的逻辑证明哦
这些题考的基本是数学，直接上算法思想，别一上来就想编程。

这个问题不是被证明过了吗？是美国那两个人啊，他们用了好多理论据说。

不过这里就用个填空题来考擦你 估计是考你的历史知识啊  呵呵

美国那两个借助计算机，采用的是穷举法，呵呵。。。。
不过很多搞组合数学的都不承认

34 楼 306963591 2011-06-29  

题目有点意思

33 楼 pigswimming 2011-06-29  

easyhaohao 写道

国家 颜色 那题是 选择题，我当时选的 无数个。。






为什么是四个？可能题目意思我没太看懂，谁解释下。。

四色定理，网上一堆解释 ：http://zh.wikipedia.org/wiki/%E5%9B%9B%E8%89%B2%E5%AE%9A%E7%90%86

32 楼 easyhaohao 2011-06-29  

---。。。。。当时考了的。米有过。。

31 楼 lipeng88213 2011-06-29  

围观。。。

30 楼 ASCII 2011-06-29  

两个篮子五个鸡蛋怎么分？按照题目的分法这个不是bug吗？

29 楼 mahonet 2011-06-29  

zhanghh321 写道

还有啊 楼主 光纤的上行下行速度是一样的吗？  我上个月办了电信的10M宽带 他们说上行1M 下行 10M啊  我是不是被忽悠了

光纤不清楚，但是你办的电信10M的宽带是adsl的，是非对称的。

28 楼 panggezi 2011-06-29  

14题，N < 2**M有解，其余无解，都是数学题。

27 楼 zhourongyu 2011-06-29  

C通过字符串拼接，效率低下，需创建四个对象.
D和E 效率高，StringBuilder不支持多线程，在不用多线程的情况下效率更高
它两的toString方法应该是一样的，同样返回一个String对象.

26 楼 pigswimming 2011-06-29  

须等待 写道

c是字符串相加，虚拟机会做优化，用StringBuilder做优化

de..不知道

恩，这是昨天新浪微博的考试题目，在网上搜了很久：c和e创建过程是一样的. 都是采用了StringBuilder
d采用了StringBuffer 。不是特别理解

25 楼 须等待 2011-06-29  

c是字符串相加，虚拟机会做优化，用StringBuilder做优化

de..不知道

24 楼 pigswimming 2011-06-29  

谁来看看这个题目
    String a=new String("a");
    String b="b";
    String c=a+b;
    StringBuffer strBuf=new StringBuffer();
    strBuf.append("a");
    strBuf.append("b");
    String d=strBuf.toString();
    StringBuilder strBuilder=new StringBuilder();
    strBuilder.append("a");
    strBuilder.append("b");
    String e=strBuilder.toString();
    请问以上程序片段中c、d、e的字符串的创建各有什么不同？

23 楼 pigswimming 2011-06-29  

须等待 写道

悲剧了 写道

13米  说下我的想法

有砝码肯定有天平，有天平就可以利用天平先左右两遍放米

第一次：天枰一边放上砝码200然后两遍在都继续放米，可以得出放砝码那边，米得重量3400
200+x=y
x+y=7000
结果是：x值为3400

重复上述步骤：天枰一边放上全部砝码200然后两遍在都继续放米，可以得出放砝码那边，米得重量1600

200+x=y
x+y=3400

结果是：x=1600

第三步：利用两个砝码，从1600中取出250就是结果
1600-250=1350

程序要写的智能一点，值什么的都动态传入，貌似不好写，正在试

我参加笔试完了和同学讨论过，基本上就是这两种思路，一种是不断的平分米，一种就是
两边称

方法是很多，关键是代码不好写

22 楼 须等待 2011-06-29  

悲剧了 写道

13米  说下我的想法

有砝码肯定有天平，有天平就可以利用天平先左右两遍放米

第一次：天枰一边放上砝码200然后两遍在都继续放米，可以得出放砝码那边，米得重量3400
200+x=y
x+y=7000
结果是：x值为3400

重复上述步骤：天枰一边放上全部砝码200然后两遍在都继续放米，可以得出放砝码那边，米得重量1600

200+x=y
x+y=3400

结果是：x=1600

第三步：利用两个砝码，从1600中取出250就是结果
1600-250=1350

程序要写的智能一点，值什么的都动态传入，貌似不好写，正在试

我参加笔试完了和同学讨论过，基本上就是这两种思路，一种是不断的平分米，一种就是
两边称

21 楼 悲剧了 2011-06-29  

13米  说下我的想法

有砝码肯定有天平，有天平就可以利用天平先左右两遍放米

第一次：天枰一边放上砝码200然后两遍在都继续放米，可以得出放砝码那边，米得重量3400
200+x=y
x+y=7000
结果是：x值为3400

重复上述步骤：天枰一边放上全部砝码200然后两遍在都继续放米，可以得出放砝码那边，米得重量1600

200+x=y
x+y=3400

结果是：x=1600

第三步：利用两个砝码，从1600中取出250就是结果
1600-250=1350

程序要写的智能一点，值什么的都动态传入，貌似不好写，正在试

20 楼 stone2oo6 2011-06-29  

14题我认为最好的分配方式入下：
1. 保证m个框中都有鸡蛋，首先都分配1个
2. 将剩下的(n-m)按照2进制数的方式分配，并将结果减去1
如
  第一个框中是1+2^0-1
  第二个框中是1+2^1-1
  第三个框中是1+2^2-1
  如此类推，知道所有的鸡蛋分配完为止

此类分配方式的好处在于能按照2进制数的原理迅速查找到所给定鸡蛋数对应的篮框

19 楼 须等待 2011-06-29  

   笔试没有过，淘宝的笔试题看上去不高深，但是真不好做。。

LZ offer了没有？哪里参加笔试的？？