首页 > 代码库 > 又一份阿里笔试题
又一份阿里笔试题
接踵而至的笔试啊。。。各种忙碌啊。。。
1， 假设把整数关键码K散列到有N个槽的散列表，以下哪些散列函数是好的散列函数（）
A.h(k)= K/N B.h(k)=1 C.h(k) = k mod N
D.h(k) = (K + random(N) ) mod N ，random(N)返回一个0到N的整数
2，下面的排序算法中，初始化数据集的排练顺序对算法的性能无影响的是（）
A,堆排序 B,插入排序 C,冒泡排序 D,快速排序
3，下面说法错误的是()
A,CISC计算机比RISC计算机指令多
B,在指令格式中，采用扩展操作码设计方案的目的是为了保持指令字节长度而增加寻址空间
C,增加流水线段数据理论行可以提高CPU频率
D,冯诺依曼机体系结构的主要特征是存储程序的工作方式。
4，不属于冯诺依曼机提议结构必要组成部分的是()
A,CPU B,Cache C,RAM D,ROM
5，一个栈的入栈序列为 A B C D E 则不可能的输出是（）
A,DECBA B,DCEBA C,ECDBA D,ABCDE
6，你认为可以完成编写一个C语言编译器的程序设计语言是（）
A,汇编语言 B,C语言 C,VB语言 D,以上皆可
7，关于C++/JAVA类中的static成员和对象成员的说法正确的是()
A， static成员变量在对象构造时生成
B， static成员函数在对象成员韩式中无法调用
C， 虚成员函数不能是static成员函数
D， Static成员函数不能访问static成员变量
9，某进程在运行过程中需要等待从磁盘读入数据，此时该进程的状态将()
A,从运行变为阻塞 B,从运行变为就绪 C,从就绪变为运行 D,从阻塞变为就绪
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^2) D,O(n!)
11，n从1开始，每个操作可以选择对n加1，或者对n加倍，如果想获得整数2013，只需要（）个操作
A,18 B,24 C,21 D不可能
12，对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组的大小为（） A,n B,n+1 C,n-1 D,n+边数
13，考虑一个特殊的hash函数h，能将任一字符串hash成一个整数k，其概率P(k) = 2 ^(-k)，k=1,2,3….对一个未知大小的字符串集合S中的每一个元素取hash值所组成的集合为h(S)。若h(S)中最大的元素maxh(S) = 10，那么S的大小的期望是（）
A,5 B,10 C,512 D,1024
14，如下函数，在32bit 系统foo(2^31-3) 的值是（）
Int foo(int x){
Return x&-x;
}
A,0 B,1 C,3 D,4
15，对于顺序存储的线性数组，访问结点和增加，删除结点的时间复杂度（）
A,O(n),O(n) B,O(n),O(1) C,O(1),O(n) D,O(1),O(1)
16，在32位系统环境，编译选项为4字节对齐，那么sizeof(A)和sizeof(B)是（）
Struct A{
Int a;
Short b;
Int c;
Char d;
};
Struct B{
Int a;
Short b;
Char d;
Int c;
};
A,16,16 B13,12 C,16,12 D,11,16
17，袋中有红球，黄球，白球个1个，每次任取一个又放回，如此连续抽取3次，则下列时间中概率是8/9的是（）
A， 颜色全相同 B，颜色不全相同 C，颜色全不同 D，颜色无红色
18，一个洗牌程序的功能是将n张牌的顺序打乱。一下关于洗牌程序的功能定义说法最恰当的是（）
A， 每张牌出现在n个位置上的概率相等
B， 每张牌出现在n个位置上的概率独立
C， 任何连续位置上的两张牌的内容独立
D， N张牌的任何两个不同的排列出现的概率相等
19，用两种颜色去染排成一个圈的6个旗子，如果通过旋转得到则只算一种，问一共有多少种染色模式。 A,10 B,14 C,15 D,16
20，递归式的先序遍历一个n节点，深度为d的二叉树，需要找空间的大小为（）
A,O(n) B,O(d) C,O(logn) D,O(nlogn)
二，不定项选择
21，两个线程运行在双核机器上，每个线程主程序如下，线程1，x=1;r1=y;线程2:y=1;r2=x。x和y是两个全局变量，初始化为0，一下哪一个是r1和r2的可能值（）
A,r1=1,r2=1 B,r1=1,r2=0 C,r1=0,r2=0 D,r1=0,r2=1
22，关于linux系统的负载(LOAD)，以下表述正确的是（）
A， 通过就绪和运行的进程数来反映
B， 可以通过TOP命令查看
C， 可以通过uptime查看
D， Load:2.5 1.3 1.1 表示系统的负载压力在逐渐减小
23，关于排序算法的一下说法，错误的是（）
A， 快速排序的平均时间复杂度为O(nlogn)，最快时间复杂度为O(n^2)
B， 堆排序的平均时间复杂度为O(nlogn)，最快时间复杂度为O(nlogn)
C， 冒泡排序的平均时间复杂度为O(n^2)，最快时间复杂度为O(n^2)
D， 归并排序的平均时间复杂度为O(nlogn)，最快时间复杂度为O(n^2)
24，假定函数rand_k 会随机返回一个[1,k]之间的整数(K >= 2)，并且每个整数值出现的几率相等。已知目前有rand_7的实现，请问通过调用rand_7和四则运算函数，并适当增加逻辑判断和循环等控制逻辑，下来函数可以实现的有（）
A,rand_3 B,rand_21 C,rand_23 D,rand_47
三，填空与问答
26、某缓存系统采用LRU淘汰算法，假定缓存容量为4，并且初始为空，那么在顺序访问以下数据项的时候，1、5、1、3、5、2、4、1、2，出现缓存直接命中的次数是（），最后缓存中即将准备淘汰的数据项是（）
答：直接命中的次数是3次，分别是访问1，5，1，3，5，2，4，1，2时。最后缓存中即将准备淘汰的数据项是5
27、有两个较长的单向链表a和b，为了找出节点node满足node in a 并且node in b，请设计空间使用尽量小的算法。（用C/C++/JAVA或伪码表示都可以）
答：node in a 并且node in b，就是求两个链表的公共节点吧
就是先分别遍历一遍链表A和链表B，在遍历时分别记下链表AB的长度，并且在最后看看链表A和链表B的最后一个节点是不是相同，如果相同则有公共节点，如果不同就没有公共节点。
找公共节点就是再利用两个指针，根据遍历时记录的长度，找到第一个公共节点，这个节点后面的就都是公共节点了。
28、当存储数据量超出单节点数据管理能力的时候，可以采取的办法有数据库sharding的解决方案，也就是按照一定的规律把数据分散存储在多个数据管理节点N中（节点编号0.1.2...N-1）。假设存储的数据是a，请完成为数据a计算存储节点的程序。（没学过C语言的同学也可以用伪码完成）
#define N 5
int hash(int element)
{
return element*2654435761;
}
int shardingIndex(int a)
{
int p = hash(a);
//1
return p;
}
空格1处： p %= N;
29、宿舍内5个同学一起玩对战游戏，每场比赛有一些人作为红方，另一些人作为蓝方，请问至少需要多少场比赛，才能使任意两个人之间有一场红方对蓝方和一场蓝方对红方的比赛？
答案为4场。
第四部分 JAVA选做题
1、以下每个线程输出的结果是什么？（不用关注输出的顺序，只需写出输出的结果集即可）
2、一个有10亿条记录的文本文件，已按照关键字排好序存储，请设计算法，可以快速的从文件中查找关键字的记录。
又一份阿里笔试题