2013年阿里巴巴校园招聘研发工程师笔试试题

2013 年阿里巴巴校园招聘研发工程师笔试试题 第一部分 单选题（前 10 题，每题 2 分；后 10 题，每题 3 分，共 50 分。选对得满分， 选错倒扣 1 分，不选得 0 分） 1．12345*12345 1105266261 所采用的是多少进制的计算？（） A、2 进制 B、8 进制 C、10 进制 D、16 进制 2. 关于 HTTP 协议的说明，一下哪项是错误的？（） A、在 CS 模式下，作为一种 request-response 协议 B、无状态，对每一个请求看成独立的 C、HTTP 是 WWW 和 Email 使用的协议 D、HTTP 响应包括数字状态码，404 经常代表“PageNot Found”” 3. 以下程序输出结果是哪个？（） char msg[] = “AAAA”; strcpy(msg, “BBB”); strcpy(msg, “CC”); strcpy(msg, “D”); printf(“%s”,msg); A、DCBA B、ABCD C、D D、A 4． 使用 gcc 默认对齐规则的情况下，下列两个数据结构的 sizeof 各是多少？（） struct FirstStruct{ char a; uint64_t b; uint32_t c; uint32_t d”; }; struct Second”Struct{ char a; uint32_t b; uint32_t c; }; A、17,13 B、24,16 C、24,24 D、32,16 5. 关于内联函数，以下哪项叙述是错误的？（） A、递归函数不能定义为内联函数 B、内联函数只能先定义后使用 C、任何源文件，使用内联函数必须包含函数定义 D、Main 函数可以内联 6. 执行 IO 时，直接调用内核异步 API，内核完成 IO 操作后再回调用户，这种 IO 模式是什 么？（） A、BIO B、NIO C、AIO D、FIO 7. 若系统中有 5 台打印机，有多个进程需要使用两台，规定每个进程一次仅允许申请一台， 则至多允许多少个进程参与竞争，而不会发生死锁？（） A、2 B、3 C、4 D、5 8. 一个栈的入栈序列为 abcd”e，则不可能的输出序列为哪个？（） A、ed”cba B、d”ceab C、d”ecba D、abed”c 9. 关于 C 程序运行内存空间的说法错误的是哪项？（） A、全局变量，static 变量位于数据区，无需应用程序分配 B、局部变量的作用域是当前的函数或程序块，出作用域之后无效 C、在堆上分配内存需要调用 malloc 函数，并且需要调用 free 函数释放 D、递归程序的递归深度主要受限于堆的空间大小，超过大小限制程序会崩溃 10. 以下关于数组说法正确的是哪项？（） A、建立公用数组，在模块声明阶段用 private 语句 B、数组设定没有上下界 C、二维数组初始化时要在类型说明时给各下标变量赋予初值 D、对数组元素赋予初始值时一定要标注长度说明 11. 下列情况中，不能使用栈（stack）来解决问题的是哪个？（） A、将数学表达式转化为后缀形式 B、实现递归算法 C、高级编程语言的过程调用 D、操作系统分配资源（如 CPU） 12. 已知数据表中每个元素距其最终位置不远，为节省时间，应该采用的算法是什么？ （） A、直接选择排序 B、堆排序 C、快速排序 D、直接插入排序 13. Skip List 是一个非常优秀的数据结构，实现简单的插入、删除、查找复杂度为 （logN），当该数据结构中插入一个元素遇到最坏情况下的时间复杂度是多少？（） A、O(N) B、O(logN) C、O(√N) D、O(N logN) 14. 设一棵二叉树中有 3 个叶子结点，8 个“深度”为 1 的结点，则该二叉树中总的节点数为 多少？（） A、11 B、12 C、13 D、14 15. 数据表中有 10000 个元素，如果仅要求求出其中最大的 10 个元素，采用什么算法最 节省时间？（） A、堆排序 B、希尔排序 C、快速排序 D、直接选择排序 16. 有 A 和 B 两路公交车，平均发车间隔分别为 5 分钟和 10 分钟。某乘客在站点 S 可以 任意选择两者之一乘坐，假设 A 和 B 到达 S 的时刻无法确定，那么该乘客的平均等待时间 约为多少？（） A、1 分钟 20 秒 B、1 分钟 40 秒 C、2 分钟 30 秒 D、3 分钟 20 秒 17．有一堆石子共 100 枚，甲乙轮流从该堆中取石子，每次可以取 2,4,6 枚，取得最后的 石子的玩家为赢家，若家先取，则以下说法正确的是哪项？（） A、甲有必胜策略 B、乙有必胜策略 C、双方都没有必胜策略 D、不确定 18. 有 4 人抬着三个货物出门，遇到一条河，他们四个人游过河的时间分别为 1,3,8,15 （分钟）。每个货物必须要由两个人托起才不会被浸湿，为防止货物失窃，所有货物需要 有人看守，请问他们最少要花几分钟才能完成渡河？（） A、15 B、20 C、23 D、25 19. 某班有 25 名学生，其中 14 人会打篮球，12 人会打排球，6 人会打篮球和排球，5 人 会打篮球和网球，还有 2 人这三种球都会打。而 6 个会打网球的人都会打另外一种球。请 问 25 人中这三种球都不会打的人数是多少？（） A、3 B、4 C、5 D、6 20. 在一个 N*N 个方格的国际象棋盘上，knight 从任意一个指定的方格出发，按照 1 横 2 竖或者 1 竖 2 横的跳马规则（如下图从 X 开始可以走到任意一个 Y）。走遍棋盘的每个格 子，且每个格子只走一次的跳法叫做一个骑士征程。请问，N 最小为多少时，一个 knight 可以完成骑士征程？（） A、5 B、7 C、8 D、9 Y Y Y Y X Y Y Y Y 第二部分 不定项选择（4 题，每题 5 分。每题 1-5 个正确选项，完全正确计 5 分，漏选 计 2 分，不选计 0 分，多选、错选扣 2 分） 21. 一段时间内只允许一个进程访问的资源被称作临界资源，针对临界资源，以下说法错 误的是哪些？（） A、对临界资源是不能实现资源共享 B、只要能是程序并发执行，这些并发执行的程序可以对临界资源实现共享 C、为临界资源配上相应的设备控制块后，便能实现共享 D、对临界资源采用互斥访问方式，便能实现共享 22. 设 存 在 三 个 函 数 f, g, h, 分 别 为 f(n)=53n~3+26n+18, g(n)=1500n~3+n~2, h(n)=15n~(1.5)+45n lg(n)。下列哪些关系是成立的，是哪几个？（） A、f(n) O(g(n)) B、g(n) O(f(n)) C、h(n) O(n~1.5) D 、 h(n) O(n lg(n)) 23. 假设在树中，节点 x 是节点 y 的双亲时，用（x,y）来代表树边。已知一棵树边的集合 为{(i,m), (i,n), (e,i), (b,e), (b,d”), (a,b), (g,j), (g,k), (c,g), (c,f), (h,i), (c,h), (a,c)}), (g,k), (c,g), (c,f), (h,i), (c,h), (a,c)} ， 则下列说法正确的是哪几个？（） A、a 是根节点 B、g,h,i 是 f 的兄弟 C、c 是 g 的双亲 D、树的深度是 5 24. 根据一项对程序员的界面和收入的调查发现：i)10%喜欢白底黑字，60%喜欢黑底绿 字；ii)50%是高收入的。下面描述可能正确的是哪几个？（） A、一半的程序员是低收入的 B、30%喜欢黑底绿字的程序员是高收入的 C、没有程序员既喜欢白底黑字，又是高收入的 D、所有喜欢黑底绿字的程序员都不是高收入的 第三部分 填空与问答（5 题，共 30 分） 25. （4 分）在操作系统的生产者消费者问题中，能否将生产者进程 wait(empty)和 wait(mutex)语句交换？为什么？ 26.（5 分）某人提着两个空水壶到池塘边打水，两个水壶的容积分别是 5L 和 6L，而他被 要求只需要带回 3L 水，请问至少需要多少次操作才能使得两个水壶中只有 3L 水。（提示： 注水、倒水均算一个步骤，给出操作步骤和最终次数） 27.（6 分）请指出二叉树后序遍历栈操作算法的关键，并给出最简单的算法思路。 28.（8 分）请给出分别满足下面条件的所有二叉树。 （1）前序序列和中序序列相同 （2）中序序列和后序序列相同 （3）前序序列和后序序列相同 （4）前序、中序、后序序列都相同 29.（7 分）以下的代码是一种广度优先搜索算法，请以下图中 V0 为源点执行以下算法， 并回答问题： （1）顶点 Vn+1 需要入队多少次？被重复访问了多少次？ （2）加黑斜体算法部分该如何做修改才能避免重复访问一个顶点的错误？ V0 V1 V2 Vn+1 Vn void” BFS(ALGraph *G, int k) { //以下省略局部变量的说明，visited” 各初始值为 False InitQueue(&Q); //置空队列 EnQueue(&Q, k); //k 入队 while(!QueueEmpty(&Q)){ i DeQueue(&Q);//Vi 出列 visited”[i] True; //设置访问标记 print("%c", G->ad”j), (g,k), (c,g), (c,f), (h,i), (c,h), (a,c)}list[i].vertex); //访问 Vi for(p G->ad”j), (g,k), (c,g), (c,f), (h,i), (c,h), (a,c)}list[i].firsted”ge;p;p p->next) //依次搜索 Vi 的邻近点 if(!visited”[p->ad”j), (g,k), (c,g), (c,f), (h,i), (c,h), (a,c)}vex]) //若 Vi 没有访问过 EnQueue(&Q, p->ad”j), (g,k), (c,g), (c,f), (h,i), (c,h), (a,c)}vex); //Vi 入列 } } //end”ofwhile //BFS 第四部分：JAVA 选做题（注：阿里有大量 JAVA 研发工程师需求；选作以下题目有机会 增加该方向面试机会） 1. 请画出工厂模式的 uml 图，并简要描述这些要素的作用；列举以下这个模式的优势； 给出一个 j), (g,k), (c,g), (c,f), (h,i), (c,h), (a,c)}d”k 源码中的例子。 2. Map 是非常重要的数据结构，设计出一个 Map 的接口，用基于 hash 的算法简单实现 这个 Map，如果对你实现的 HashMap 做支持高并发场景下的线程安全的优化，怎么 改进？ 更进一步，可以基于此 HashMap 如何最简单实现支持 LRU 算法的 cache？如果要让 这个 cache 支持分布式缓存服务，导入了哪些要解决的问题？请列举出来并给出你的 解决方法。