京东2015年应届生招聘笔试题
一、 客观题: (总分，60分，每题4分共15题)
1
关于HTTP协议的说法，以下哪些说法是不正确的()
A. 有状态，前后请求有关联关系
B. FTP也可以使用HTTP协议
C. HTTP响应包括数字状态码，300代表此次请求有正确返回
D. HTTP和TCP、UDP是在网络分层里是同一层次的协议
2
以下代码运行结果为()
#include
int main() {
uint32_t a = 100;
while(a > 0){
--a;
}
printf("%d",a);
return 0;
}
A. -1
B. 100
C. 0
D. 死循环
3
以下哪种排序算法需要开辟额外的储存空间()
A. 选择排序
B. 归并排序
C. 快速排序
D. 堆排序
4
如果将固定块大小的文件系统中的块大小设置大一些，会造成()
A. 更好的磁盘吞吐量和更差的磁盘空间使用率
B. 更好的磁盘吞吐量和更好的磁盘空间使用率
C. 更差的磁盘吞吐量和更好的磁盘空间使用率
D. 更差的磁盘吞吐量和更差的磁盘空间使用率
5
若一颗二叉树的前序遍历为a,e,b,d,c，后序遍历为b,c,d,e,a，则根节点的孩子节点()
A. 只有e
B. 有e,b
C. 有e,c
D. 不确定
6
在一个世世代代都重男轻女的村庄里，村长决定颁布一条法律:村子里没有生育出儿子的夫妻可以一直生育指导生出儿子位置，假设现在村子的男女比例是1:1，这条法律颁布之后的若干年后村子的男女比例将会()
A. 男的多
B. 女的多
C. 一样多
D. 不确定
7
批处理操作系统目的是()
A. 提高操作系统资源利用率
B. 提高系统与用户的交互性能
C. 减少用户作业的等待时间
D. 降低用户作业的周转时间
8
设有一个关系:DEPT(DNO,DNAME)，如果要找出倒数第三个字母为W，并且至少包含4个字母的DNAME,则查询条件子句应写成WHERE DNAME LIKE()
A. '__W_%'
B. '_%W__'
C. '_W__'
D. '_W_%'
9
已知的一个无向图(边为正数)中顶点A，B的一条最短路P，如果把各个边的权重(即相邻连个顶点的距离)变为原来的2倍，那么在新图中，P忍让是A，B之间的最短路。以上说法()错误。
A. 不确定
B. 正确
C. 错误
10
如下程序的时间复杂度为(其中m>1,e>0)()
x = m;
y = 1;
while (x - y > e){
x = (x + y)/2;
y = m/x;
}
print(x);
A. log m
B. m2
C. m1/2
D. m1/3
11
求fun(484)的返回值()
bool fun(int n){
int sum = 0;
for (int i = 1; n > sum; i = i+2)
sum = sum + i;
return (n == sum);
}
A. True
B. False
12
关于主对角线(从左上角到右下角)对称的矩阵为对称矩阵: 如果一个矩阵中的各个元素取值为0或1，那么该矩阵为01矩阵，求大小为N*N的01对阵矩阵的个数? ( )
A. power(2, n)
B. power(2, n*n/2)
C. power(2,(n*n + n)/2)
D. power(2,(n*n - n)/2)
13
现代的语言(如java)的编译器的词法分析主要依靠()
A. 有限状态自动机
B. 确定下推自动机
C. 非确定下推自动机
D. 图灵机
14
如下函数的f(1)的值为()
int f(int n) {
static int i = 1;
if (n >= 5)
return n;
n = n+i;
i++;
return f(n);
}
A. 5
B. 6
C. 7
D. 8
15
123456789101112...2014除以9的余数是____
二、 编程题: (总分，40分，每题20分)
16
给定字符串(ASCII码 0~255)数组，请在不开辟额外空间的情况下删除开始和结尾处的空格，并将中间的`多个连续的空格合并成一个。例如:" i am a little boy. ",变成"i am a little boy."，语言不限，但不要用伪代码作答，函数输入输出请参考如下的函数原型:
C++ 函数原型:
void FormatString(char str[], int len){
}
17
给定一颗二叉树，以及其中的两个node(地址均非空)，要求给出这两个node的一个公共父节点，使得这个父节点与两个节点的路径之和最小，描述你程序的最坏时间复杂度，并实现具体函数，函数输入输出请参考如下的函数原型:
C++ 函数原型:
struct TreeNode {
TreeNode* left;//指向左子树
TreeNode* right;//指向右子树
TreeNode* father;//指向父亲节点
};
TreeNode* LowestCommonAncestor(TreeNode* first, TreeNode* second) {
}
三、 附加题: (总分20分)
18
有n枚硬币按照0到n-1对它们进行编号，其中编号为i的硬币面额为Vi。两个人轮流从剩下硬币中取出一枚硬币归自己所有，但每次取硬币的时候只能取剩下的硬币中编号最小的硬币或者编号最大的硬币，在两个都采用最优策略的情况下，作为先手取硬币的你请编写程序计算出你能获得硬币总面额的最大值? (请简述算法原理，时间复杂度并实现具体的程序)，语言不限。
int MaxValue(int V[], int n) {
}
