优酷笔试（一）_可能性不低于90% 最多选多少人

时间：2014.04.18

地点：基地二楼

------------------------------------------------------------------

1、已知中国人的血型分布约为A型：30%，B型：20%，O型：40%，AB型：10%，则任选一批中国人作为用户调研对象，希望他们中至少有一个是B型血的可能性不低于90%，那么最少需要选多少人？

A、7     B、9      C、11     D、13

解答：至少有一个是B型不低于90%这个事件的对立面对应于没有一个是B型的概率小于10%，而一个人不是B型的概率为0.8，所以即可得 0.8^N<0.1

即Nlog0.8<log0.1，容易得N>10.31885，取11即可。

2、广告系统为了做地理位置定向，将IPV4分割为627672个区间，并标识了地理位置信息，区间之间无重叠，用二分查找将IP地址映射到地理位置信息，请问在最坏的情况下，需要查找多少次？

A、17     B、18      C、19     D、20

解答：我在有篇博文里说了，二分查找的时间复杂度为O(logn)，也是我们一般人当前见识过的唯一位O(logn)的算法，我不知道还有没有，可能见识浅薄，若还有，希望大家告诉我呀。那么求 log627672的值就可以了，注意在计算机里默认都是以2为底的对数，答案为20

3、有四只老鼠一块出去偷食物（每个都偷了），回来时，族长问它们都偷了什么，老鼠A说：我们每个都偷了奶酪。老鼠B说：我只偷了一颗樱桃。老鼠C说：我没偷奶酪。老鼠D说：有些人没偷奶酪。族长观察了一下，发现它们当中只有一只老鼠说了实话，那么是哪只老鼠说了实话？
A、老鼠A        B、老鼠B        C、老鼠C       D、老鼠D

解答：假设A是实话，则其余都是假话，再去验证，B,C,D说的确实是假话，就拿D来说吧，它说有人没偷奶酪，但确实都偷了啊，不是假话么。

     假设B说实话，其余都是假话，A的假可以说明，有人没偷奶酪，这会导致D说的是对的，于是推出一个悖论

    嗯，剩余情况也是如此，这类题可先假定，然后得出结论，在去验证，错误的答案往往会得出一个悖论。

4、到商店里买200的商品返还100的优惠券（可以在本商店代替现金）。如果使用优惠券买东西不能获得新的优惠券，那么买200返100优惠券，实际上省多少？
A、50%
B、66.7%
C、75%
D、33.3%

解答：买了300块钱的东西，实际上只付了200，节省1/3

6、一家人有两个孩子，性别未知，现在打电话给其中一个孩子得知是女孩，问另一个孩子也是女孩的概率是多少？

A、1/4        B、1/2        C、1/3       D、1/5

解答：两个孩子1表示男，0表示女，那么就要 00 01 10 11 四种等概率情况，得知有一女，那么就是 00 01 10情况，在此情况下得到00的概率就是1/3啊

7、关于非空二叉树的性质，下面哪个结论不正确(D)

A、有两个节点的节点一定比没有子节点的节点少一个      n0 = n2 + 1
B、根节点所在的层数为第0层，则第i层最多有2^i个节点
C、若知道二叉树的前序遍历序列和中序遍历序列，则一定可以推出后序遍历序列。
D、堆一定是一个完全二叉树

解答：为什么说二叉说度为0的节点总比度为2的节点多一个呢，首先：度即对应于树上长出的边，从节点出发来看，度为0的节点不发出边，度为1的节点发出一条边，度为2的节点发出两条边，那么二叉树度的总数N=0*n0+1*n1+2*n2。然而，我们再从另外一个角度看，二叉树的所有节点都是由一条边发出来得，根节点除外，于是二叉树的度的总数又可以表示为N=n0+n1+n2-1(即总度数等于总节点数-1，因为只有根节点不是由边发出来得）。

另外堆是一种完全二叉树或者近似完全二叉树，并不是非得完全二叉树，完全二叉树的朴素定义是：假设有一个满二叉树，在一个新的深度上从左到右添加叶子节点，那么所有新的叶子节点都有相同的深度，比添加前大1，并且总是先往最左边添加新节点，这样的树成为完全二叉树，而堆比如下面也是一个堆，但并不是完全二叉树呢：

8、快速排序的平均时间复杂度和最坏时间复杂度是（）
A、O（n^2）, O(n^2)
B、O（n^2）, O(nlgn)
C、O(nlgn) , O(nlgn)
D、O(nlgn) , O(n^2)

解答：快速排序的最坏情况运行时间是O(n*n)，但平均情况运行时间和最优运行时间都是O(nlogn)，要想获得一个好的运行时间，需要选择一个好的基准元素。

9、有一串数字 6 7 4 2 8 1 6 （），请问括号中的数字最可能是（）
A、6       B、7       C、8       D、9

解答：6*7=42,4*4=28,4*2=8,2*8=16......

10、下面哪项不是链表优于数组的特点？
A、方便删除     B、方便插入    C、长度可变    D、存储空间小

解答：链表的删除插入只有简单的改变指针指向即可，长度可变是理所当然的，为什么说存储空间小呢，因为在同样大小空间下，链表的节点好要存放指针，浪费有额外的空间。

11、给定声明 const char * const * pp; 下属操作或说明正确的是（）
A、pp++
B、(*pp)++
C、(**pp) = 'c';
D、以上都不对

解答；肿么样，这么看，首先pp是个指针，这是确定无疑的; const char * const (* pp)。然后，我们也知道const int 和int const是没有区别的，所有如果我们把const char* 当做一种类型的话，即(const char*) const和const (const char*)也是无区别的，所有可以知道指针pp指向的内容是个const的（const char*)类型数据，即我们不能通过指针pp去改变pp指向的内存中的内容，然后该内容中存在的数据还是一个指针，我们也不能通过这个指针去改变它所指向的内存中的内容。但pp本身是个普通的指针，所以对pp的操作是可行的。

12、有下列代码正确的是（）

std::string name1 = "youku";
const char* name2 = "youku";
char name3[] = {'y','o','u','k','u'};
size_t l1 = name1.size();
size_t l2 = strlen(name2);
size_t l3 = sizeof(name2);
size_t l4 = sizeof(name3);
size_t l5 = strlen(name3);

A、l1 = 5     l2 = 5     l3 = 4      l4 = 5     l5 = 不确定
B、l1 = 5     l2 = 5     l3 = 5      l4 = 5     l5 = 不确定
C、l1 = 5     l2 = 6     l3 = 5      l4 = 5     l5 = 5
D、l1 = 5     l2 = 6     l3 = 5      l4 = 5     l5 = 6

解答：1.返回字串的长度，2.strlen返回C风格字串长度，末尾的空格不会计算在内，3.name2是一个指针变量，大小为4byte，4.name3为数组名，在这计算的整个数组的大小，为5, 5.对这样的数组进行计算将得到未定义的结果，这需要了解strlen()函数的实现机制，strlen函数有可能是沿着数组name3在内存中的位置不断向前寻找，直到遇到空字符才停下下，在这里，name3虽然是字符数组，但不是以空字符作为结束的，所以会产生未定义的结果。