软件开发实习生-转码平台-笔试.docx

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

第一篇：软件开发实习生-转码平台-笔试1.操作系统采用时间片轮转策略调度进程，是为了___a____。A.多个进程都能得到系统的及时响应B.最先调度优先级较高的进程C.最先调度占用CPU时间短的进程D.最先调度占用IO时间短的进程2.导致操作系统出现死锁的原因不包括___a___。A.系统中产生了资源依赖的环形链B.当进程因请求资源而阻塞时，不释放本身已经获取的资源C.对于一个进程占有的资源，在其未主动释放前，不能强制剥夺D.同一时间内，资源能被不同进程共享3.观察下面的三角形。给出第10行的序列之和：___19683_____1123213676314101619161041…4.一个平面内，被任意条直线划分而成的区域，最少用____c__种颜色着色，使得相邻的区域颜色不同。A.1B.2C.3D.45.一棵具有30个结点的二叉树，其空指针的数目为：_____31_6.快速排序平均时间复杂度是__O(n*log2n)____，平均空间复杂度是__O(log2n)___.最差情况的时间复杂度是__O(n2)____，最差情况的空间复杂度是____O(log2n)__.7.下面函数的平均时间复杂度为：___O(1)______intf(unsignedintn){if(nif(n==1)return1;return3*f(n-1)-4*f(n-2);}8.某规则二叉树的定义是：对于树中任意两个叶结点A、B,它们与根节点的距离分别为da、db，|da-db|9.假设有两台通过网络互联的电脑A、B，A需要将自己的一棵二叉树结构传输到B。请设计一种编码、解码方法（不要求代码实现）。二叉树结点结构如下structNode{structNode*left;structNode*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个文件写回磁盘上。一般而言，如果第二步过后，内存可以容纳下存在中位数的某一个文件的话，直接快排就可以了。第二篇：Java软件开发工程师笔试软件开发工程师(JAVA)笔试题请在120分钟以内做答一、选择题1、下面哪项是不合法的标识符：（）A.$personsB.TwoUsersC.*pointD._endlineE.final美元符下划线字母数字不能以数字开头不能是关键字2、下列运算符合法的是（）A．&&B．C．ifD．:=算术逻辑关系赋值位3、下面描述中哪两项相等：（）[选择两项]A.B.C.D.E.F.G.金属片动作标签的使用：＜jsp:useBeanid=“test”class=“hall.SimpleBean”/＞＜jsp:setPropertyname=“test”property=“message”value=“HellopilationfailsC.Anexceptionisthrownatruntime？？？？？18、阅读下面的程序1.publicclassOuter{2.publicvoidsomeOuterMethod(){3.//Line34.}5.publicclassInner(){}6.publicstaticvoidmain(St