2014阿里巴巴校园招聘软件研发工程师笔试真题及答案

2014 阿里巴巴校园招聘软件研发工程师笔试真题及答案 1. 假设把整数关键码 K 散列到 N 个槽列表，以下哪些散列函数是好的散列函数 A: h(K)=K/N; B: h(K)=1; C: h(K)=K mod N; D: h(K)=(K+rand(N)) mod N, rand(N)返回 0 到 N-1 的整数 答案:D 2. 下面排序算法中，初始数据集的排列顺序对算法的性能无影响的是： A: 堆排序 B：插入排序 C: 冒泡排序 D:快速排序 答案:A（插入排序：最优时间复杂度插入排序：最优时间复杂度 O（插入排序：最优时间复杂度n）最差时间复杂度最差时间复杂度 O（插入排序：最优时间复杂度n^2）最差时间复杂度平均时间复杂度 O（插入排序：最优时间复杂度n^2）最差时间复杂度 冒泡排序：最优时间复杂度 O（插入排序：最优时间复杂度n）最差时间复杂度最差时间复杂度 O（插入排序：最优时间复杂度n^2）最差时间复杂度平均时间复杂度 O（插入排序：最优时间复杂度n^2）最差时间复杂度 快速排序：最优时间复杂度 O（插入排序：最优时间复杂度nlogn）最差时间复杂度最差时间复杂度 O（插入排序：最优时间复杂度n^2）最差时间复杂度平均时间 复杂度 O（插入排序：最优时间复杂度nlogn）最差时间复杂度 堆排序：最优时间复杂度 O（插入排序：最优时间复杂度nlogn）最差时间复杂度最差时间复杂度 O（插入排序：最优时间复杂度nlogn）最差时间复杂度平均时间 复杂度 O（插入排序：最优时间复杂度nlogn）最差时间复杂度）最差时间复杂度 3. 下面说法错误的是： A: CISC 计算机比 RISC 计算机指令多 B: 在指令格式中，采用扩展操作码设计方案的目的是为了保持指令字长不变而增加 寻址空间 C:增加流水线段数理论上可以提高 CPU 频率 D:诺依曼体系结构的主要特征是存储程序的工作方式 答案:B 4. 不属于诺依曼体系结构必要组成部分是： A:CPU B: Cache C:RAM D:ROM 答案:B 5. 一个栈的入栈序列式 ABCDE 则不可能的出栈序列是: A:DECBA B:DCEBA C:ECDBA D:ABCDE 答案:C 6.你认为可以完成编写一个 C 语言编译器的语言是： A：汇编 B:C 语言 C:VB D:以上全可以 答案：D 7. 关于 C++/JAVA 类中的 static 成员和对象成员的说确的是： A：static 成员变量在对象构造时候生成 B: static 成员函数在对象成员函数中无法调用 C: 虚成员函数不可能是 static 成员函数 D: static 成员函数不能访问 static 成员变量 答案：A 8： 答案：C 9：某进程在运行过程中需要等待从磁盘上读入数据，此时进程的状态将： A: 从就绪变为运行 B:从运行变为就绪 C: 从运行变为阻塞 D:从阻塞变为就绪 答案：C 10：下面算法的时间复杂度为： Int f(unsigned int n) { If(n==0||n==1) Return 1; Else Return n*f(n-1); } A: O(1) B:O(n) C:O(N*N) D:O(n!) 答案：B 11: n 从 1 开始，每个操作可以选择对 n 加 1 或者对 n 加倍。若想获得整数 2013，最少 需要多少个操作。 A:18 B:24 C:21 D；不可能不可能 答案：A， 对 2013 用除法，显示 2013->2012->1006->503->502->251->250>125->124->62->31->30->15->14->7->6->3->2->1 正向只能是+1 和×2，所以逆向只能-1 和/2，由上过程可得 18 次 12：对于一个具有 n 个顶点的无向图，若采用邻接表数据结构表示，则存放表头节点的数 组大小为： A: n B: n+1 答案：A 13： C: n-1 D:n+边数 答案:A.对于几何中的每个字符串取 hash 可以看作是同分布的独立重复事件，所以每一个 事件出现 10 的概率都是 p=1/1024，那么当出现的时候，期望的次数就是 1/p，1024. 14：如下函数，在 32bit 系统 foo(2^31-3)的值是： Int foo(int x) { Return x&-x; } A： 0 B: 1 C:2 D:4 答案：B 15：对于顺序存储的线性数组，访问节点和增加节点删除节点的时间复杂度为： A: O(n),O(n)B:O(n),O(1) C:O(1),O(n) D:O(n),O(n) 答案：C 16:在 32 为系统环境，编译选项为 4 字节对齐，那么 sizeof(A)和 sizeof(B)是： Struct A { Int a; short b; int c; char d; }; Struct B { int a; short b; char c; int c; }; A: 16,16 B:13,12 C:16,12D:11,16 答案：C 17:袋中有红球，黄球，白球各一个，每次任意取一个放回，如此连续 3 次，则下列事件 中概率是 8/9 的是： A: 颜色不全相同 B:颜色全不相同 C:颜色全相同 D:颜色无红色 答案：A 18：一个洗牌程序的功能是将 n 牌的顺序打乱，以下关于洗牌程序的功能定义说法最恰当 的是： A: 每牌出现在 n 个位置上的概率相等 B: 每牌出现在 n 个位置上的概率独立 C: 任何连续位置上的两牌的容独立 D: n 牌的任何两个不同排列出现的概率相等 答案：A 19：用两种颜色去染排成一个圈的 6 个棋子，如果通过旋转得到则只算一种，一共有多少 种染色： A: 10 B:11 C:14: D:15 答案：C 解释：应该有 14 种方案，设只有黑白两色，默认白色，那么，用 p（插入排序：最优时间复杂度n）最差时间复杂度表示有 n 个黑棋 的种类 p（插入排序：最优时间复杂度0）最差时间复杂度=p（插入排序：最优时间复杂度6）最差时间复杂度=1 p（插入排序：最优时间复杂度1）最差时间复杂度=p（插入排序：最优时间复杂度5）最差时间复杂度=1