1.操作系统采用时间片轮转策略调度进程,是为了___a____。
A.多个进程都能得到系统的及时响应
B.最先调度优先级较高的进程
C.最先调度占用CPU时间短的进程
D.最先调度占用IO时间短的进程
2.导致操作系统出现死锁的原因不包括___a___。
A.系统中产生了资源依赖的环形链
B.当进程因请求资源而阻塞时,不释放本身已经获取的资源
C.对于一个进程占有的资源,在其未主动释放前,不能强制剥夺
D.同一时间内,资源能被不同进程共享
3.观察下面的三角形。给出第10行的序列之和:___19683_____
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 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个文件写回磁盘上。一般而言,如果第二步过后,内存可以容纳下存在中位数的某一个文件的话,直接快排就可以了。