网易2012校园招聘笔试题目
测试工程师（网易宝）
注：貌似前2部分题目是一样，第三部分按岗位有所不同
第一部分（必做）：计算机科学基础
1、长为N的字符串中匹配长度为M的子串的算法复杂度是（）
A. O(N)
B. O(M+N)
C. O(N+logM)
D. O(M+logN)
2、以下排序算法中，哪些是稳定的排序算法（多选）（）
A.冒泡
B.插入
C.合并
D.希尔
E.快速排序
3、以下是一颗平衡二叉树，请画出插入键值3以后的这颗平衡二叉树。

4、给定两个整数集合A和B，每个集合都包含20亿个不同整数，请给出快速计算A∩B的算法，算法可使用外存，但是要求占用内存不能超过4GB。

5、请给出从N个无序的整数中计算机最小的K个整数的算法，并给出时间复杂度，其中K<<N，要求时间复杂度尽可能的低，不要求K个整数排序。

6、假设一个有8个1024字页面的逻辑地址空间,映射到一个有32帧的物理内存结构中，逻辑地址有多少位？
答案来自：/oldxul/czxt/files/f2.htm
在分页存储管理中，逻辑地址结构如下图所示：
它由两个部分组成：前一部分表示该地址所在页面的页号p；后一部分表示页内地址（页内位移）d。

页号的地址位数决定了页的多少，假设页号有20位，则地址空间中最多可容纳的页面数为220，即1MB个页面。

页内地址位数确定了每页的大小，若页内地址为12位，
则每页大小为212，即2KB。

同理，物理地址中块号的地址位数决定了块的数量。

由于页式存储管理内存空间块的大小与页面大小相同，所以物理地址中块内地址与逻辑地址中的页内地址位数相同。

解：因为页面数为8=23，故需要3位二进制数表示。

每页有1024个字节，1024=210，于是页内地址需要10位二进制数表示。

32个物理块，需要5位二进制数表示（32=25）。

（1）页的逻辑地址由页号和页内地址组成，所以需要3+10=13位二进制数表示。

（2）页的物理地址由块号和页内地址的拼接，所以需要5+10=15位二进制数表示。

得算法的使用者忽视算法的具体实现？
9、数据库系统提供两种不同类型的语言，分别是自含式语言和嵌入式语言，来供数据库管理员及开发者管理，查询和更新。

10、数据库理论中取出右侧关系中所有与左侧关系的任一元组都不匹配的元组，用空值填充所有来自左侧关系的属性，再把产生的元组加到自然连接的结果上，这种连接运算称为？
11、关于索引的概念的选择题，没有拍全
12、关于数据库事务，简述事务的特性，事务的其它东东（忘记了）
第二部分全是JAVA内容，没有拍下来
第三部分专业类，根据岗位不同，试题不同。

我做的是测试工程师（网易宝）
1、谈谈你对软件测试的理解，可以包括测试流程、测试类型、测试目的等。

请回答你认为
最重要的部分，尽量控制字数。

2、请描述http请求get和post的区别。

3、请描述进程与线程的区别。

4、现在让你测试一个程序，这个程序有三个输入框，分别是输入三角形的3条边，旁边有
一个确认按钮，你点击按钮可能会弹出这么几种结果：不是三角形，锐角三角形，直角三角形，钝角三角形，等腰三角形，等边三角形，请详细描述下测试的过程以及需要注意的点。

5、程序运行时会遇到很多系统给予的中断事件，手机系统中，中断事件是一个很常见的现
象，比如来电通知，短信提醒等。

请写出你所知的中断事件，排列出优先级，如果有一个通讯录同步软件需要测试，请写出哪些操作需要关注中断事件。

6、某大学图书馆信息管理系统需要设计一张图书信息表，请给出以下问题的答案（默认采
用MySQL语法，若采用其他数据库可注明）
a)请设计表结构，并且用SQL语句写出建表语句
b)向你设计的表中插入5条图书记录。

c)检索出“机械工业出版社”出版的2007年以后的书名包含“软件测试”的图书。

d)如果表中的某两列，比如“书名”和“出版社”需要经常一起使用查询，请用SQL
语句为该表设计一个索引以提高查询效率。

e)请描述索引的优点和缺点。

7、编程题。

存在一个名为user.csv的文件，csv中的内容是以逗号作为分隔符的，里面依次
存储了用户的id,name,mail信息。

请写一段程序，输出用户信息中mail是以163结尾的所有用户的name。

内容格式如下：
Id,name,mail
1,Kevin,Kevin@
2,micheal,micheal@
8、编程题。

编写代码把16进制表示的串转换为3进制表示的串。

例如x=”5”，则返回：”12”；
又例如：x=”F”，则返回”120”。