京东 2016校园招聘笔试试题--开发笔试题.pdfVIP

京东开发笔试题 第一部分 数据结构 1、设a，b，c 三个元素的进栈次序是a，b，c，符号PUSH 与POP 分别表示对堆栈进行 一次进栈操作与一次出栈操作 （1） 请分别写出所有可能的出栈序列以及获得该出栈序列的操作序列 Abc push(a) pop(a) push(b) pop(b) push(c) pop(c) acb bac bca Cba （2） 指出不可能出现的出栈序列 Cab 2、已知某二叉树的后序遍历序列是dabec，中序遍历序列是deabc，它的前序遍历序列 是什么？ cedba 3、将长度为n 的单链表链接在长度为m 的单链表之后的算法的时间复杂度是多少？ O(n) 4、在有序表(12,24,36,48,60,72,84) 中二分查找关键字 72 时所需进行的关键字比较次数 是多少？ Mid = (low + high) /2 48 72 5、现有一圆环形路，路上有n 个加油站，第i 个加油站储存有Ni 升容量的油，每两个 加油站之间有一定的距离（km），一汽车初始无油，该车每公里消耗w 升油，请问 该车从哪个加油站出发可以绕该环形路行驶一圈。给出所有的算法及时间的复杂度。 V t n- 1 s W * t = Ni V*t = s/(n- 1) Ni = s/(n- 1) * w 6、B-树和B+树有什么区别，用在什么地方？ B+树的叶子节点包含所有关键字的信息 用处： 索引 例如 mysql 索引就是B+Tree 文件系统 1.定义任意非叶子结点最多只有M 个儿子；且M2； 2.根结点的儿子数为[2, M]； 3.除根结点以外的非叶子结点的儿子数为[M/2, M]； 4.每个结点存放至少M/2- 1 （取上整）和至多M- 1 个关键字；（至少2 个关键字） 5.非叶子结点的关键字个数=指向儿子的指针个数-1； 6.非叶子结点的关键字：K[1], K[2], …, K[M- 1]；且K[i] K[i+1] ； 7.非叶子结点的指针：P[1], P[2], …, P[M] ；其中P[1]指向关键字小于K[1]的子树，P[M] 指向关键字大于K[M- 1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树； 8.所有叶子结点位于同一层； 2.非叶子结点的子树指针与关键字个数相同； 3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）； 4.为所有叶子结点增加一个链指针； 5.所有关键字都在叶子结点出现； 第二部分 软件工程 1、软件生存周期各阶段的活动定义是什么？ 定义及规划 需求分析 软件设计 程序编码 软件测试 运行维护 2、程序的三种基本控制结构是什么？ 1. 顺 序 结 构 : 2. 选 择 ( 判 断 ) 结 构 : 3.循环结构: 3、汽车有一个发动机。汽车和发动机之间的关系是什么关系？请画出这种关系的UML 图 组合关系 第三部分 数据库 1、现有两个表Student 。StudentScore ，如下： Table ：Student Id （主键） Name Sex 1 张三 男 2 李四 男 3 翠花 女 Table ：StudentScore StudentId （Student 外键） Course Score 1 高数 80 1 数据结构 55 3