2012年9月12日优酷土豆校园招聘会笔试试题.doc-资料库

第1页 / 共6页

第2页 / 共6页

第3页 / 共6页

第4页 / 共6页

第5页 / 共6页

第6页 / 共6页

2012 年 9 月 12 日优酷土豆校园招聘会笔试试题选择题 1、已知中国人的血型分布约为 A 型：30%，B 型：20%，O 型：40%，AB 型：10%，则任选一批中国人作为用户调研对象，希望他们中至少有一个是 B 型血的可能性不低于 90%，那么最少需要选多少人？ A、7 B、9 C、11 D、13 2、广告系统为了做地理位置定向，将 IPV4 分割为 627672 个区间，并标识了地理位置信息，区间之间无重叠，用二分查找将 IP 地址映射到地理位置信息，请问在最坏的情况下，需要查找多少次？ A、17 B、18 C、19 D、20 3、有四只老鼠一块出去偷食物（每个都偷了），回来时，族长问它们都偷了什么，老鼠 A 说：我们每个都偷了奶酪。老鼠 B 说：我只偷了一颗樱桃。老鼠 C 说：我没偷奶酪。老鼠 D 说：有些人没偷奶酪。族长观察了一下，发现它们当中只有一只老鼠说了实话，那么是哪只老鼠说了实话？ A、老鼠 A B、老鼠 B C、老鼠 C D、老鼠 D 4、到商店里买 200 的商品返还 100 的优惠券（可以在本商店代替现金）。如果使用优惠券买东西不能获得新的优惠券，那么买 200 返 100 优惠券，实际上省多少？ A、50% B、66.7% C、75% D、33.3% 5、在数据库逻辑设计中，当将 E-R 图转换为关系模式时，下面的做法哪一个不正确？ A、一个实体类型转换为一个关系模式 B、一个联系类型转换为一个关系模式 C、由实体类型转换成的关系模式的主键是该实体类型的主键 D、由联系类型转换成的关系模式的属性是与该联系类型相关的诸实体类型的属性的全体 6、一家人有两个孩子，性别未知，现在打电话给其中一个孩子得知是女孩，问另一个孩子也是女孩的概率是多少？ A、1/4 B、1/2 C、1/3 D、1/5 7、关于非空二叉树的性质，下面哪个结论不正确(D) A、有两个节点的节点一定比没有子节点的节点少一个 n0 = n2 + 1 B、根节点所在的层数为第 0 层，则第 i 层最多有 2^i 个节点 C、若知道二叉树的前序遍历序列和中序遍历序列，则一定可以推出后序遍历序列。 D、堆一定是一个完全二叉树

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) 9、有一串数字 6 7 4 2 8 1 6 （），请问括号中的数字最可能是（） A、6 B、7 C、8 D、9 10、下面哪项不是链表优于数组的特点？ A、方便删除 B、方便插入 C、长度可变 D、存储空间小 11、给定声明 const char * const * pp; 下属操作或说明正确的是（） A、pp++ B、(*pp)++ C、(**pp) = 'c'; D、以上都不对 12、有下列代码正确的是（） [cpp] view plaincopyprint? 1. std::string name1 = "youku"; 2. const char* name2 = "youku"; 3. char name3[] = {'y','o','u','k','u'}; 4. size_t 5. size_t 6. size_t 7. size_t 8. size_t l1 l2 l3 l4 l5 = = = = = name1.size(); strlen(name2); sizeof(name2); sizeof(name3); strlen(name3); A、l1 = 5 B、l1 = 5 C、l1 = 5 D、l1 = 5 l2 = 5 l3 = 4 l4 = 5 l5 = 不确定 l2 = 5 l2 = 6 l2 = 6 l3 = 5 l3 = 5 l3 = 5 l4 = 5 l4 = 5 l4 = 5 l5 = 不确定 l5 = 5 l5 = 6 13、Test 执行后的输出是： [cpp] view plaincopyprint? 1. void Test() 2. { 3. class B

4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. { public: B(void) { } cout<<"B\t"; ~B(void) cout<<"~B\t"; { } }; struct C { C(void) { } cout<<"C\t"; ~C(void) cout<<"~C\t"; { } }; struct D : B { D() { } ~D() { } cout<<"D\t"; cout<<"~D\t"; private: C c; };

39. 40. } D d; A、B B、D C、C D、C C C D D B B ~D ~B ~B ~C D ~D ~ C ~B ~C ~D B ~D ~C ~B 14、下列四种排序中（D）的空间复杂度最大 A、快速排序 B、冒泡排序 C、希尔排序 D、堆 15、设一棵二叉树的深度为 k，则该二叉树最多有（D）个节点。 A、2k-1 B、2^k C、2^(k-1) D、2^k-1 16、下面函数的功能是（） [cpp] view plaincopyprint? 1. int fun(char *x) 2. { 3. 4. 5. 6. } char *y = x; while(*y++); return (y-x-1); A、求字符串的长度 B、比较两个字符串的大小 C、将字符串 x 复制到字符串 y D、将字符串 x 连接到字符串 y 后面 17、k 为 int 类型，以下 while 循环执行（）次。 [cpp] view plaincopyprint? 1. unsigned int k = 20; 2. while(k >= 0) 3. --k; A、20 次 B、一次也不执行 C、死循环 D、21 次 18、关于 Cookie 和 Session 的概念哪一个是对的 A、Cookie 存储在客户端，但过期时间设置在服务器上 B、Session 存储在客户端，但过期时间设置在服务器上 C、Cookie 中可以存储 ASCII 空格‘ ’，而 Session 中不行

D、Cookie 可以设置生效的路径，而 Session 则不能 19、以下关于链式存储结构的叙述中哪一条是不正确的？ A、结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构 B、逻辑上相邻的结点物理上不必邻接 C、可以通过计算直接确定第 i 个结点的存储地址 D、插入、删除运算操作方便，不必移动结点 20、32 位机器上，定义 int **a[3][4]，这个数组占多大的空间（） A、64 填空题 B、12 C、48 D、128 1、设数组定义为 a[60][70]，每个元素占 2 个存储单元，数组按照列优先存储，元素 a[0][0] 的地址为 1024，那么元素 a[32][58]的地址为（8048） 2、在一个娱乐节目上，主持人提供有三扇门（假设为 A、B、C），只有 1 扇门后面有奖品，另两扇门后面是空的，而主持人知道具体哪扇门后有奖品。首先，当你选择了一扇门之后（假设 A），主持人会把剩下两扇门中的一扇没有奖品的门打开（假设打开的空门为 B），现在你有一次机会决定是否要交换重新选择，如果你坚持选择 A，你中奖的概率是（1/3），如果你交换选择 C，你中奖的概率是（2/3） http://en.wikipedia.org/wiki/Monty_Hall_problem 假设你选择的 1 门，而主持人打开的是 3 门，则奖品在 2 门后面的概率是 3、一棵深度为 h 的满二叉树，其最末一层共有（2^h）个节点（根节点深度为 0） 4、下面程序的运行结果为（1 3 2） [cpp] view plaincopyprint? 1. void foo(int *a , int *b) 2. { 3. 4. 5. 6. } 7. *a *b *a = = = *a *a *a + - - *b; *b; *b; 8. void main() 9. {

10. 11. 12. 13. 14. 15. } int a foo(&a foo(&b foo(&c = , , , 1 , b = 2 , c = 3; &b); &c); &a); printf("%d %d %d\n",a,b,c); 5、4 个结点可以构造出（14）个不同的二叉树 6、设有 n 个无序的记录关键字，则直接插入排序的时间复杂度为（O(n^2)），快速排序的平均时间复杂度为（O(nlgn)） 7、设一组初始记录关键字序列为（20,18,22,16,30,19），则以 20 为中轴的一趟快速排序结果为（19,18,16,20,30,22） 8、C 语言的函数参数传递方式有传递值 9、分配在堆上和栈上的内存，哪一个需要手动进行内存释放？和传递地址 Catalan 数堆上的内存问答题：一、有一个单向循环链表队列，从头开始报数，当报到 m 或者 m 的倍数的元素出列，根据出列的先后顺序重新组成单向循环链表。函数原型： void reorder(Node **head , int m) 二、优酷是中国第一的视频网站，每天有上亿的视频被观看，现在公司请研发人员找出最热门的视频。该问题的输入可以简化为一个字符串文件，每一行都表示一个视频 id，然后要找出出现次数最多的前 100 个视频 id，将其输出，同时输出该视频的出现次数。 1、假设每天的视频播放次数为 3 亿次，被观看的视频数量为一百万个，每个视频 ID 的长度为 20 个字节，限定使用的内存为 1G。请先描述做法，再写代码。 2、假设每个月的视频播放次数为 100 亿次，被观看的视频数量为 1 亿个，每个视频 ID 的长度为 20 个字节，一台机器被限定使用的内存为 1G。那么想找这个月被播放次数最多的前 100 个视频，应该怎么做？请描述清楚可能的办法。解析：海量数据的处理。无法一次性装入内存，可先 hash 之分为多个文件处理，堆或者 Trie 树统计次数，求出每个文件中的 Top 100。归并之求出总的 top 100。对于第二问：还可以 hadoop mapReduce 处理之。首先统计每个视频被观看次数，得到键值对，其中 id 为视频 id，cnt 为视频被观看次数。以 cnt 作为关键字建立最小堆。遍历所有键值对，若堆的 size 小于 100，则将键值对直接插入堆，否则比较键值对和堆顶元素大小，若 cnt 大于堆顶元素的 cnt，则弹出堆顶元素并将键值对插入堆。对于第一问，由于 id 个数较少，统计部分可直接使用 stl 的 map 容器。对于第二问，由于 id 个数太大，直接 hash 内存不够，需要 mapReduce。三、给你一个由 n-1 个整数组成的未排序的序列，其元素都是 1 到 n 中的不同的整数。请写出一个寻找序列中缺失整数的线性时间算法。

资料库

2012年9月12日优酷土豆校园招聘会笔试试题.doc

相关推荐

求职招聘

热门标签

最新资料