《2016搜狐校园招聘笔试题》.pdf

IT面试() 新浪微博：IT面试论坛 /free4294 微信公众账号：itmian4 更多真题请访问IT面试题库（) 2013搜狐校园招聘笔试题 1 假设二叉排序树的定义是：1、若它的左子树不为空，则左子树所有节点均小于它的根节点的 值；2 、若右子树不为空，则右子树所有节点的值均大于根节点的值；3、它的左右子树也分别 为二叉排序树。下列哪种遍历之后得到一个递增有序数列（） A 前序遍历 B 中序遍历 C 后序遍历 D 广度遍历 正确答案：B 题目解析：要是得到的序列为递增，应先访问左子树，再访问根结点，最后访问右子树，根据定义知为中序遍历 。 2 往一个栈顺序push下列元素：ABCDE ，其pop可能的顺序，下列不正确的是（） A BACDE B ACDBE C AEBCD D AEDCB 正确答案：C 题目解析： 栈的操作顺序是后进先出，不可能的顺序是pop后面插进去的元素之后，在栈中pop得顺序的倒序输出，而C不可 能pop AE之后，pop 出来的顺序只能是DCB ，不能是BCD 。 3 1100|1010， 1001^1001 ，别为（） A 1110 ， 0000 ， 1000 B 1000 ， 1001 ， 1000 C 1110 ， 1001 ， 0101 D 1000 ， 1001 ， 1000 正确答案：A 题目解析： |或操作,^异或操作，与操作。 1 | 1 = 1， 1 | 0 = 1 ， 0 | 0 = 0 1 ^ 1 = 0， 1 ^ 0 = 1 ， 0 ^ 0 = 0 1 1 = 1， 1 0 = 0 ， 0 0 = 0 4 int A[2][3] = {1, 2, 3, 4, 5, 6}, A[1][0]和*(*(A+1)+1)的值分别是（） A 4 ， 5 B 4 ， 3 C 3 ， 5 D 3 ， 4 正确答案：A 题目解析：数组是A[2][3] = {{1, 2, 3}, {4, 5, 6}} ，数组下标从0开始计数。前者是第1行第0列，后者是第1行第1列 5 序列16， 14 ， 10 ， 8 ， 7 ， 9 ， 3 ， 2 ， 4 ， 1 的说法下面哪一个正确（） A 是大顶堆 B 是小顶堆 C 不是堆 D 是二叉排序树 正确答案：A 题目解析： 二叉堆的定义 二叉堆是完全二叉树或者是近似完全二叉树。 二叉堆满足二个特性： 1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。 2 ．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。 当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子 节点的键值时为最小堆。 堆化数组为：i节点的父节点数组下表为(i-1)/2，对应的左右节点的数组下表为2*i+1和2*i+2.所以将数组回归为堆 之后就能看到是最大堆了。 6 输入若已经是排好序的，下列排序算法最快的是（） A 插入排序 B Shell排序 C 合并排序 D 快速排序 正确答案：A 题目解析： 题目是输入排好序的数据： 插入排序一遍扫描即可 Shell排序虽不需要交换数据，但也要进行几次插入排序 合并排序虽不需要交换数据，但也要进行lgn次合并 快速排序在数列有序的情况下效率是最低的 7 一种既有利于短作业又兼顾长期作业的调度方法是（） A 先来先服务 B 均衡调度 C 最短作业优先 D 最高响应比优先 正确答案：D 题目解析：最高响应比优先法(HRN，Highest Response_ratio Next)是对FCFS方式和SJF方式的一种综合平衡。 FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短，而SJF方式只考虑执行时间而未考虑等待时间的 长短。因此，这两种调度算法在某些极端情况下会带来某些不便。HRN调度策略同时考虑每个作业的等待时间长 短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。 响应比R定义如下： R =(W+T)/T = 1+W/T 其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。每当要进行作业调度时，系统计 算每个作业的响应比，选择其中R最大者投入执行。这样，即使是长作业，随着它等待时间的增加，W / T也就随 着增加，也就有机会获得调度执行。这种算法是介于FCFS和SJF之间的一种折中算法。由于长作业也有机会投入 运行，在同一时间内处理的作业数显然要少于SJF法，从而采用HRN方式时其吞吐量将小于采