第一部分 单选题（前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 SecondStruct{ 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. 一个栈的入栈序列为abcde，则不可能的输出序列为哪个？（） A、edcba B、dceab C、decba D、abedc
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 Y Y X 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)}，则下列说法正确的是哪几个？（）
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
Vn V1 V2
Vn+1
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(\//访问Vi for(p G->adjlist[i].firstedge;p;p p->next) //依次搜索Vi的邻近点 if(!visited[p->adjvex]) //若Vi没有访问过 EnQueue(&Q, p->adjvex); //Vi入列 } //endofwhile //BFS
第四部分：JAVA选做题（注：阿里有大量JAVA研发工程师需求；选作以
下题目有机会增加该方向面试机会）
1. 请画出工厂模式的uml图，并简要描述这些要素的作用；列举以下这个模式的优势；给
出一个jdk源码中的例子。
2. Map是非常重要的数据结构，设计出一个Map的接口，用基于hash的算法简单实现这
个Map，如果对你实现的HashMap做支持高并发场景下的线程安全的优化，怎么改进？
更进一步，可以基于此HashMap如何最简单实现支持LRU算法的cache？如果要让这个cache支持分布式缓存服务，导入了哪些要解决的问题？请列举出来并给出你的解决方法。
2016年阿里巴巴校园招聘笔试试题研发工程师
