软件开发实习生转码平台笔试_软件开发实习生笔试题

软件开发实习生转码平台笔试由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“软件开发实习生笔试题”。

1.操作系统采用时间片轮转策略调度进程，是为了___a____。

A.多个进程都能得到系统的及时响应

B.最先调度优先级较高的进程

C.最先调度占用CPU时间短的进程

D.最先调度占用IO时间短的进程

2.导致操作系统出现死锁的原因不包括___a___。

A.系统中产生了资源依赖的环形链

B.当进程因请求资源而阻塞时，不释放本身已经获取的资源

C.对于一个进程占有的资源，在其未主动释放前，不能强制剥夺

D.同一时间内，资源能被不同进程共享

3.观察下面的三角形。给出第10行的序列之和：___19683_____1 12 3 2 13 6 7 6 3 14 10 16 19 16 10 4 1

…

4.一个平面内，被任意条直线划分而成的区域，最少用____c__种颜色着色，使得相邻的区域颜色不同。

A.1B.2C.3D.45.一棵具有30个结点的二叉树，其空指针的数目为：_____31_

6.快速排序平均时间复杂度是__O(n*log2n)____，平均空间复杂度是__O(log2n)___.最差情况的时间复杂度是__O(n2)____，最差情况的空间复杂度是____O(log2n)__.7.下面函数的平均时间复杂度为：___O(1)______

int f(unsigned int n){

if(n

if(n==1)return 1;

return3*f(n-1)-4*f(n-2);

}

8.某规则二叉树的定义是：对于树中任意两个叶结点A、B, 它们与根节点的距离分别为da、db，|da-db|

9.假设有两台通过网络互联的电脑A、B，A需要将自己的一棵二叉树结构传输到B。请设计一种编码、解码方法（不要求代码实现）。二叉树结点结构如下 struct Node{

struct Node * left;

struct Node* right;

charvalue;}

10.在一个大文件中有100亿个32位整数，乱序排列，要求找出中位数。内存限制为512M。写出算法设计思路，并分析时间复杂度。

答：第一步:把10G整数每2G读入一次内存，然后一次遍历这536,870,912个数据。每个数据用位运算“>>”取出最高8位(31-24)。这8bits(0-255)最多表示255个桶，那么可以根据8bit的值来确定丢入第几个桶。最后把每个桶写入一个磁盘文件中，同时在内存中统计每个桶内数据的数量，自然这个数量只需要255个整形空间即可。

第二步：根据内存中255个桶内的数量，计算中位数在第几个桶中。很显然，2,684,354,560个数中位数是第1,342,177,280个。假设前127个桶的数据量相加，发现少于1,342,177,280，把第128个桶数据量加上，大于1,342,177,280。说明，中位数必在磁盘的第128个桶中。而且在这个桶的第1,342,177,280-N(0-127)个数位上。N(0-127)表示前127个桶的数据量之和。然后把第128个文件中的整数读入内存。(平均而言，每个文件的大小估计在10G/128=80M左右，当然也不一定，但是超过2G的可能性很小)。

第三步：继续以内存中的整数的次高8bit进行桶排序(23-16)。过程和第一步相同，也是255个桶。

第四步：一直下去，直到最低字节(7-0bit)的桶排序结束。我相信这个时候完全可以在内存中使用一次快排就可以了。

整个过程的时间复杂度在O(n)的线性级别上(没有任何循环嵌套)。但主要时间消耗在第一步的第二次内存-磁盘数据交换上，即10G数据分255个文件写回磁盘上。一般而言，如果第二步过后，内存可以容纳下存在中位数的某一个文件的话，直接快排就可以了。