研发实习题目2015-阿里

1.

下列叙述中正确的是？

循环队列中元素的个数是有队头指针和队尾指针共同决定。

队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。
循环队列是将顺序队列首尾相连形成的，随着插入元素或删除元素的进行，其队头指针及队尾指针是在不断变化的，有时可能会出现队头指针大于队尾指针的情况，也可能是队尾指针大于队头指针。

2.
以下指令集架构属于复杂指令集架构的是？
常用的精简指令集 RISC 微处理器包括 DECAlpha 、 ARC 、 ARM 、 AVR 、 MIPS 、 PA-RISC 、 PowerArchitecture( 包括 PowerPC)和 SPARC 等。 复杂指令 CISC如X86。

3.
有两个N*N的矩阵A和B，想要在PC上按矩阵乘法基本算法编程实现计算A*B。假设N较大，本机内存也很大，可以存下A、B和结果矩阵。那么，为了计算速度，A和B在内存中应该如何存储（按行存指先存储第一行，再第二行，直到最后一行；按列存指先存储第一列，再第二列，直到最后一列）？

我们来看看传统的分块矩阵相乘：
很明显依然是行乘以列的方式。

再来看看Strassen矩阵相乘：
同样是分块，只是计算方式不同
 
很明显，涉及到行的加法(a+b,c+d,e+f,g+h)，列的减法(f-h,g-e,b-d,a-c)，对角线的加法(a+d,e+h)以及行列的乘法，所以无论是
A按行存，B按行存。
A按行存，B按列存。
计算速度都是差不多的。
而如果用的是传统矩阵相乘法，按B选项的方式存储计算速度更快。综上所述，我觉得答案应该选B。
4.
IP数据报头采用（）字节序，在此字节序下从低地址到高地址0x1234的表示形式为 （） 。
0x1234其实是0x00001234.
其实 big endian 是指低地址存放最高有效字节（ MSB ），而 little endian 则是低地址存放最低有效字节（ LSB ）。 所有网络协议也都是采用 big endian 的方式来传输数据的。所以有时我们也会把 big endian 方式称之为网络字节序。当两台采用不同字节序的主机通信时，在发送数据之前都必须经过字节序的转换成为网络字节序后再进 行传输。
5.
1
2
3
4
5
6
7
8
struct T {
    char a;
    int *d;
    int b;
    int c:16;
    double e;
};
T *p;
在64位系统以及64位编译器下，以下描述正确的是

sizeof(p) == 8  P为指针，64位系统地址占8个字节
sizeof(*p) == 24 根据内存对齐  32字节  a_ _ _ _ _ _ _ | * d  8字节|  | b4字节|  |c2字节|_ _ |e8字节|
sizeof(p->a) == 1 正确
sizeof(p->e) == 8  double
在64位系统下，地址占64位，即指针占64位，8个字节。所以，*p所占的内存是这要的：
a：本身占1个字节，字节对齐占7个字节，共8个字节
d：64位指针，占8字节
b：占32位，4个字节
c:16 ：占16位，2个字节，字节对齐占2个字节，共4个字节
e：64位，8个字节
6.
shell排序的平均复杂度是O(nlogn)~O(n2)，最好的情况O(n1.3)，最坏的情况O(n2)
快速排序的平均复杂度是O(nlogn)，           最好的情况O(nlogn)，最坏的情况O(n2)
直接插入排序的平均复杂度是O(n2)，         最好的情况O(n)，      最坏的情况O(n2)
冒泡排序的平均复杂度是O(n2),                   最好的情况O(n),        最坏的情况O(n2)
7.
在N个乱序数字中查找第k大的数字，时间复杂度可以减小至
在一个元素个数为N的数组里，找到升序排在N/5位置的元素的最优算法时间复杂度是
题目又没说要考虑空间复杂度！那就基数排序或者计数排序搞一搞，时间复杂度O(n)。
然后数一数，第N/5个数，不就行了噻！
BFPRT算法解决的问题十分经典，即从某n个元素的序列中选出第k大（第k小）的元素，通过巧妙的分 析，BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似，当然，为使得算法在最坏情况下，依然能达到o(n)的时间复杂 度，五位算法作者做了精妙的处理。
算法步骤：
1. 将n个元素每5个一组，分成n/5(上界)组。
2. 取出每一组的中位数，任意排序方法，比如插入排序。
3. 递归的调用selection算法查找上一步中所有中位数的中位数，设为x，偶数个中位数的情况下设定为选取中间小的一个。
4. 用x来分割数组，设小于等于x的个数为k，大于x的个数即为n-k。
5. 若i==k，返回x；若i<k，在小于x的元素中递归查找第i小的元素；若i>k，在大于x的元素中递归查找第i-k小的元素。
终止条件：n=1时，返回的即是i小元素。
答案解析：解法1：我们可以对这个乱序数组按照从大到小先行排序，然后取出前k大，总的时间复杂度为O(n*logn + k)。
     解法2：利用选择排序或交互排序，K次选择后即可得到第k大的数。总的时间复杂度为O(n*k)
     解法3：利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：
      1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；
      2. Sa中元素的个数大于等于k，则返回Sa中的第k大数。时间复杂度近似为O(n)
     解法4：二分[Smin,Smax]查找结果X，统计X在数组中出现，且整个数组中比X大的数目为k-1的数即为第k大数。时间复杂度平均情况为O(n*logn)
     解法5：用O(4*n)的方法对原数组建最大堆，然后pop出k次即可。时间复杂度为O(4*n + k*logn)
     解法6：维护一个k大小的最小堆，对于数组中的每一个元素判断与堆顶的大小，若堆顶较大，则不管，否则，弹出堆顶，将当前值插入到堆中。时间复杂度O(n * logk)
     解法7：利用hash保存数组中元素Si出现的次数，利用计数排序的思想，线性从大到小扫描过程中，前面有k-1个数则为第k大数，平均情况下时间复杂度O(n)
8.
设集合A={1,2,3},A上的关系R＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，则R不具备 ()?

假设集合A，以及基于A上的关系R
自反： 如果a是A的元素，那么<a,a>是R的元素 
反自反： 如果a是A的元素，那么<a,a>不是R的元素 
对称：如果<a,b>是R的元素，那么<b,a>是R的元素 
反对称：如果<a,b>，<b,a>是R的元素，那么a,b相等 
传递：如果<a,b>，<b,c>是R的元素，那么<a,c>是R的元素
9.
无锁化编程有哪些常见方法？
A.针对计数器，可以使用原子加
B.只有一个生产者和一个消费者，那么就可以做到免锁访问环形缓冲区（Ring Buffer）
C.RCU（Read-Copy-Update），新旧副本切换机制，对于旧副本可以采用延迟释放的做法
D.CAS（Compare-and-Swap），如无锁栈，无锁队列等待
A 这方法虽然不太好，但是常见
B ProducerConsumerQueue就是这个，到处都是
C linux kernel里面大量使用
D 本质上其实就是乐观锁，操作起来很困难。。单生产者多消费者或者多生产者单消费者的情况下比较常见，也不容易遇到ABA问题。

10.
主机甲和主机乙间已建立一个TCP连接，主机甲向主机乙发送了两个连续的TCP段，分别包含300字节和500字节的有效载荷，第一个段的序列号为200，主机乙正确接收到两个段后，发送给主机甲的确认序列号是？

确认序列号=原始序列号+TCP段的长度，所以第一次的确认序列号为200+300=500，第二次确认序列号为500+500=1000，选D。
11.
以下措施中，不可能改进分布式系统读写(IO)性能的有____。
网络从千兆网升级为万兆网
优化调度系统，尽量做到任务与数据相近（Locality）
数据预取机制
实现异步读写机制

异步I/O不但不能提高i/O性能，有时反而有损I/O性能，因为Linux内核级别异步I/O不支持缓存操作，每次都必须从硬盘读取数据。与同步非阻塞I/O相比的优点在于：将异步I/O提交到内核后，内核会通知I/O设备独立的执行操作，这样服务进程可以继续充分占有CPU，而且，当大量读操作堆积到I/O设备的队列中，将会发挥内核的“电梯算法”优势，从而降低读磁盘成本。所以一般在读取文件时才使用异步I/O。
12.
将一个从大到小的数组，用以下排序方法排序成从小到大的，（）最快。
排序方法        平均情况        最好情况        最坏情况        辅助空间        稳定性
冒泡排序         O(n^2)           O(n)              O(n^2)            O(1)                稳定
选择排序         O(n^2)          O(n^2)            O(n^2)            O(1)              不稳定
插入排序         O(n^2)           O(n)              O(n^2)            O(1)                稳定
希尔排序O(n*log(n))~O(n^2) O(n^1.3)       O(n^2)            O(1)              不稳定
堆排序          O(n*log(n))     O(n*log(n))    O(n*log(n))       O(1)              不稳定
归并排序       O(n*log(n))     O(n*log(n))    O(n*log(n))       O(n)                稳定
快速排序       O(n*log(n))     O(n*log(n))      O(n^2)            O(1)              不稳定

冒泡排序经过优化以后，最好时间复杂度可以达到O(n)。设置一个标志位，如果有一趟比较中没有发生任何交换，可提前结束，因此在正序情况下，时间复杂度为O(n)。选择排序在最坏和最好情况下，都必须在剩余的序列中选择最小（大）的数，与已排好序的序列后一个位置元素做交换，依次最好和最坏时间复杂度均为O(n^2)。插入排序是在把已排好序的序列的后一个元素插入到前面已排好序(需要选择合适的位置)的序列中，在正序情况下时间复杂度为O(n)。堆是完全二叉树，因此树的深度一定是log(n)+1，最好和最坏时间复杂度均为O(n*log(n))。归并排序是将大数组分为两个小数组，依次递归，相当于二叉树，深度为log(n)+1，因此最好和最坏时间复杂度都是O(n*log(n))。快速排序在正序或逆序情况下，每次划分只得到比上一次划分少一个记录的子序列，用递归树画出来，是一棵斜树，此时需要n-1次递归，且第i次划分要经过n-i次关键字比较才能找到第i个记录，因此时间复杂度是\sum_{i=1}^{n-1}(n-i)=n(n-1)/2，即O(n^2)。
13.
有一台带一个千兆网卡的服务器A，会把接收到的消息转发给另外两台带一个千兆网卡的服务器B和C，B和C上面的一个服务进程处理一条10K字节的消息需要2毫秒。如果在B和C上面各跑80个服务进程，在不考虑CPU负载和进程切换、内存占用、传输损耗和交互损耗的情况下，B和C服务器每秒一共大约可以处理______条10K字节的消息。
"一个服务进程处理一条10K字节的消息需要2毫秒",则一进程500*10K/S，现在有2*80个进程，则最终处理160*500*10k/S，所以结果80000。
千兆网卡每秒最多处理数据是1000/8=125Mb=125000kb=12500个10k
你们是不是忘了千兆网卡的单位是bit，也就是每秒只能发125000KB，最多处理12500条

14.
叶子节点数为3，所以度为2的节点数=3-1=2（这是由假设度为2的节点数为a，叶子节点为b，则b=a+1这个结论得到的，这个结论可以证明的）。所以总节点数=2+8+3=13

15.
10个相同的糖果，分给三个人，每个人至少要得一个。有()种不同分法
10个糖果排列好9个空，取两个作为分割点，为36个,组合公式C(9,2)

16.
x每次与x-1进行一次与（&）操作，就会导致x二进制中的1减少一个。通过函数fun可知，x二进制中有多少位1就会进行多少次与计算。

17.
下面所述步骤中，不是创建进程所必须的步骤是？
由调度程序为进程分配CPU,运行时才分配CPU。
1,申请空白PCB（进程控制块）；
2,为新进程分派资源；
3,初始化PCB；
4,将新进程插入就绪队列；

18.

1
2
int a=25;
print_value(&a);
则下面函数的正确输出结果是______。
1
2
3
4
void print_value(int* x)
{
    printf(“%x\n”,++*x);
}

printf(“%x\n”,++*x); 先把x的值加上1再16进制输出。1a