京东开发笔试题

1、京东开发笔试题第一部分数据结构1、设a, b, c三个元素的进栈次序是 a, b, c,符号push与pop分别表示对堆栈进行 一次进栈操作与一次出栈操作(1) 请分别写出所有可能的出栈序列以及获得该出栈序列的操作序列abc, acb, bca, cba, bac(2) 指出不可能出现的出栈序列cab2、已知某二叉树的后序遍历序列是 dabec,中序遍历序列是deabc,它的前序遍历序列 是什么？(cedba)3、将长度为n的单链表链接在长度为 m的单链表之后的算法的时间复杂度是多少？o(m)4、在有序表(12,24,36,48,60,72,84)中二分查找关键字 72时所需进行的关键字比较次

2、数 是多少？( 2 )5、现有一圆环形路，路上有n个加油站，第i个加油站储存有ni升容量的油，每两个加油站之间有一定的距离(km), 一汽车初始无油，该车每公里消耗w升油，请问该车从哪个加油站出发可以绕该环形路行驶一圈。给出所有的算法及时间的复杂度。6、b-w和b+树有什么区别，用在什么地方？第二部分软件工程1、软件生存周期各阶段的活动定义是什么？包括软件定义阶段、软件开发阶段和软件使用、维护和更新换代阶段。软件定义阶段的基本任务是确定软件系统的工程需要软件开发阶段包括概要设计、详细设计、实现、组装测试和确认测试5个阶段2、程序的三种基本控制结构是什么？顺序选择循环3、汽车有一个发动机。汽车和

3、发动机之间的关系是什么关系？请画出这种关系的uml图第三部分数据库1、现有两个表 student。studentscore,如下: table: studentid (主键)namesex1张三男2李四男3翠花女table: studentscorestudentid (student 外键)coursescore1高数801数据结构553高数704数据结构80(1)写出 student、studentscore 的建表语句create table student id, name, sex create table stdentscorestudentid,course, score (2)

4、写出 student、studentscore 之间 left join, right join和 inner join 的 sql 语句(3)写出 student、studentscore 之间 left join, right join和 inner join 的结果，样式如 下：select * from stdent left join studentscore on student.id = studentcore.ididnamesexcoursescore(4) 在student中插入一条新记录(4,王五，男)，请写出对应的sql语句insert into student val

5、ues()4,王五，男)(5)写出统计所有的课程考试及格(=60)的人数的sql语句，结果要包含课程和人数字段select course,count(name)as 人数 from stdentsocre group by course where socre60第四部分逻辑1、你让工人为你工作 7天，给工人的回报是1根金条。金条平分成相连的 7段，你必 须在每天结束时给他们1段金条，如果只许你两次把金条弄断，你如何给你的工人付费？ 1,2,42、请把1盒蛋糕分成8份，分给8个人，但蛋糕盒里还必须留有一份最后一个人吃蛋糕盒里的蛋糕3、u2合唱团在赶往演唱会场的途中必须跨过1座桥，4个人从桥的同

6、一端出发，你得帮助他们到达另一端，天色很暗，而他们只有一只手电筒。一次同时最多可以有2人一起过桥，而过桥的时候必须持有手电筒，所以就得有人把手电筒带来带去，来回桥的两端。4个人的步行速度各不同，若 2人同行则以比较慢的人速度为准。 bono需要花1 分钟过桥，edge需花2分钟过桥，adam需花5分钟过桥，larry需花10分钟过桥。请 写出最短的时间和步骤。1,2过去，1回来，5,10过去，2回来，1,2过去=17分4、有7克、2克祛码各一个，天平一只，如何只用这些物品3次将140的盐分为50,90,个、克各一份？ 过5、4,4,10,10,运用加减乘除，怎么得出 24点？(10 0 - 4

7、) 4 +第五部分其它1、请阐述进程和线程的区别进程是程序的一次执行， 线程可以理解为进程中执行的一段程序的片段。进程间是独立的，线程运行在进程空间中，进程无法突破进程边界存取其他进程内的存储空间，而线程由于存在于进程空间内，所以同一进程所产生的线程共享同一内存空间。2、常用的内存管理方法有哪几种块式管理段式管理（每次分配的大小不固定）页式管理（每次分配的大小固定）段页式（整体分段，段内分页，和整体分页，页内分段）3、请说出iso网络参考模型有哪几层，并简单描述每一层功能osi参考模型各层的功能1、物理层：该层是网络通信的数据传输介质，由连接不同结点的电缆与设备共同构 成。主要功能是：利用传输

8、介质为数据链路层提供物理连接，负责处理数据传输并 监控数据出错率，以便数据流的透明传输。2、数据链路层： 主要功能是：在物理层提供的服务基础上，在通信的实体间建立数据链路连接，传输以“帧”为单位的数据包，并采用差错控制与流量控制方法，使有 差错的物理线路变成无差错的数据链路。3、网络层：主要功能是：为数据在结点之间传输创建逻辑链路，通过路由选择算法为 分组通过通信子网选择最适当的路径，以及实现拥塞控制、网络互联等功能。4、传输层：主要功能是向用户提供可靠的端到端（end-to-end）服务，处理数据包错误、数据包次序，以及其他一些关键传输问题。传输层向高层屏蔽了下层数据通信的细 节，因此，它是计算机通信体系结构中关键的一层。5、会话层：主要功能是：负责维扩两个结点之间的传输链接，以便确保点到点传输不 中断，以及管理数据交换等功能。6、表示层：主要功能是：用于处理在两个通信系统中交换信息的表示方式，主要包括 数据格式变换、数据加密与解密、数据压缩与恢复等功能。7、应用层：主要功能是：为应用软件提供了很多服务， 例如文件服务器、数据库服务、 电子邮件与其他网络软件服务。第六部分java1、java多线程有几种实现方法？2、 string 与 stringbuffer 的区别3、arraylist和vector主要区别是什么