第一部分(必做): 计算机科学基础
1. (单选)软件设计中模块划分应该遵循的准则是:
A.低内聚低耦合 B.高内聚低耦合 C.低内聚高耦合 D.高内聚高耦合
答案：B 高内聚低耦合，是软件工程中的概念，是判断设计好坏的标准，主要是面向对象的设计，主要是看类的内聚性是否高，耦合度是否低。 高内聚 内聚就是一个模块内各个元素彼此结合的紧密程度，高内聚就是一个模块内各个元素彼此结合的紧密程度高。 所谓高内聚是指一个软件模块是由相关性很强的代码组成，只负责一项任务，也就是常说的单一责任原则。 低耦合：一个软件结构内不同模块之间互连程度的度量(耦合性也叫块间联系。指软件系统结构中各模块间相互联系紧密程度的一种度量。模块之间联系越紧密，其耦合性就越强，模块的独立性则越差，模块间耦合的高低取决于模块间接口的复杂性，调用的方式以及传递的信息。) 对于低耦合，粗浅的理解是： 一个完整的系统，模块与模块之间，尽可能的使其独立存在。 也就是说，让每个模块，尽可能的独立完成某个特定的子功能。 模块与模块之间的接口，尽量的少而简单。 如果某两个模块间的关系比较复杂的话，最好首先考虑进一步的模块划分。 这样有利于修改和组合。
2. (单选)最坏情况下时间复杂度不是n(n-1)/2的排序算法是:
A.快速排序 B.冒泡排序 C.直接插入排序 D.堆排序
答案：D 堆排序的最坏时间复杂度与最好时间复杂度都是O(nlog（n）)。快速排序的最坏运行时间是O(n^2)，期望运行时间复杂度是O(nlg(n))。冒泡排序的时间复杂度是O(n^2)，直接插入排序的最坏与平均时间复杂度都是O(n^2)。
3. 哈希表中解决冲突的方法通常可以分为open addressing和chaining两类, 请分别解释这两类冲突解决方法的大致实现原理
答案：开放寻址法：在开放寻执法中所有元素都放在散列表中，当药插入一个元素时，可以连续的检测散列表的各项，直到找到一个空槽为止。 开放寻址法常用的探查序列方法有三种：1,线性探查，2、二次探查，3、双重探查。 线性探查：给定一个三列函数F（n），给定关键字k，查找散列表中的T(F(k))，如果该槽为空则插入，如果不为空则探查T(F(k)+1)槽，直到找到空槽为止，如果探查到列表的尾部还没找到空位，则从散列表的T(0)开始查找。 二次探查：散列函数为h(k,i)=(h'(k)+c1*i+c1*i^2).初始探查位置为T(h(k)),如果该槽不为空则在此基础上加上一个便宜量。该偏移量依赖于i的二次方形式。 双重探查：开放寻址法中最好的一个寻址方法。产生的排列较随机。散列函数形式为 h(k)=(h1(k)+i*h2(k))mod m 链接法散列是在每一个槽中放置一个链表指针，映射到某一个槽中的元素按照一定的次序插入链表指针指向的链表中。
4. 简单的链表结构拥有很好的插入 删除节点性能, 但随机定位(获取链表第n个节点)操作性能不佳, 请你设计一种改进型的链表结构优化随机定位操作的性能, 给出设计思路及其改进后随机定位操作的时间复杂度
我能想到的最优解决方案是将链表改为双向循环链表。并在链表头中增加一个链表长度数据域。该域记录了链表的长度。如果要找的第n个节点小于链表长度的一半，则正向查找，否则逆向查找。时间复杂度是O(n/2)
5. 什么是NP问题?列举典型的NP问题(至少两个)?对于一个给定的问题你通常如何判断它是否为NP问题?
P问题是可以在多项式时间内被确定机(通常意义的计算机)解决的问题.NP(Non-Deterministic Polynomial, 非确定多项式)问题,是指可以在多项式时间内被非确定机(它可以猜,他总是能猜到最能满足你需要的那种选择,如果你让他解决n皇后问题,他只要猜n次就能完成----每次都是那么幸运)解决的问题.它是说P问题是否等于NP问题,也即是否所有在非确定机上多项式可解的问题都能在确定机上用多项式时间求解. 换句话说NP问题不能再确定机上在多项式时间内解决。 较为著名的NP难问题1、欧几里得旅行商问题（非双调）。用最少的耗费走完所有节点，且要形成回路，每个节点只走一次。 背袋问题：货物n个，有各自重量，两个包，如何分货物，使两个包重量之差最小。我们可以通过判定与规约的方法判断一个问题是否是NP难。简单地，熟记常见的NP难问题模型，如果碰到的问题转化成的模型要比某一NP难问题还要复杂，或者这两个模型等价，则可判定碰到的问题是NP难问题。
6. 以下是一个tree的遍历算法, queue是FIFO队列, 请参考下面的tree, 选择正确的输出.
1
/ \
2 3
/ \ / \
4 5 6 7
queue.push(tree.root)
while(true){
node=queue.pop();
output(node.value);//输出节点对应数字
if(null==node)
break;
for(child_node in node.children){
queue.push(child_node);
}
}
A. 1234567
B. 1245367
C. 1376254
D. 1327654
答：A
第二部分(选作): C/C++程序设计
1. 有三个类A B C定义如下, 请确定sizeof(A) sizeof(B) sizeof(C)的大小顺序, 并给出理由
struct A{
A() {}
~A() {}
int m1;
int m2;
};
struct B{
B() {}
~B() {}
int m1;
char m2;
static char m3;
};
struct C{
C() {}
virtual~C() {}
int m1;
short m2;
};
本题考查的是类的内存对齐。 输出结果为sizeof(A)=8,sizeof(B)=8,sizeof(12).详细请参考：
类的内存对齐（类的sizeof）
2. 请用C++实现以下print函数,打印链表I中的所有元素, 每个元素单独成一行
void print(const std::list<int> &I){
}
#include<iostream>
#include<list>
using namespace std;
void Print(const list<int>&L)
{
list<int>::const_iterator it;
for(it=L.begin();it!=L.end();it++)
{
cout<<*it<<endl;
}
}
int main()
{
list<int>L(10,42);
Print(L);
return 0;
}
3. 假设某C工程包含a.c和b.c两个文件,在a.c中定义了一个全局变量foo, 在b.c中想访问这一变量时该怎么做?
在b.c中extern （类型）foo；
4. C++中的new操作符通常完成两个工作, 分配内存及其调用相应的构造函数初始化
请问:
1) 如何让new操作符不分配内存, 只调用构造函数?
2) 这样的用法有什么用?
classname *f=new((void*)10)classname(); 作用是：将对象放置在内存的特殊位置，是在已有的内存块上面创建对象。 用于需要反复创建并删除的对象上，可以降低分配释放内存的性能消耗
5. 下面这段程序的输出是什么?为什么?
class A{
public:
A(){p();}
virtual void p(){print("A")}
virtual ~A(){p();}
};
class B{
public:
B(){p();}
void p(){print("B")}
~B(){p();}
};
int main(int, char**){
A* a=new B();
delete a;
}
语法错误！对象B不能实例化A
6. 什么是C++ Traits? 并举例说明
原生指针类型信息的提取。这个题目有点深。需要进一步研究。
第三部分(选作): JAVA程序设计
1. (单选)以下Java程序运行的结构是:
public class Tester{
public static void main(String[] args){
Integer var1=new Integer(1);
Integer var2=var1;
doSomething(var2);
System.out.print(var1.intValue());
System.out.print(var1==var2);
}
public static void doSomething(Integer integer){
integer=new Integer(2);
}
}
A. 1true
B. 2true
C. 1false
D. 2false
2. (单选)往OuterClass类的代码段中插入内部类声明, 哪一个是正确的:
public class OuterClass{
private float f=1.0f;
//插入代码到这里
}
A.
class InnerClass{
public static float func(){return f;}
}
B.
abstract class InnerClass{
public abstract float func(){}
}
C.
static class InnerClass{
protected static float func(){return f;}
}
D.
public class InnerClass{
static static float func(){return f;}
}
3. Java中的interface有什么作用? 举例说明哪些情况适合用interface, 哪些情况下适合用抽象类.
4. Java多线程有哪几种实现方式? Java中的类如何保证线程安全? 请说明ThreadLocal的用法和适用场景
5. 线程安全的Map在JDK 1.5及其更高版本环境 有哪几种方法可以实现?
6.
1) 简述Java ClassLoader的模型, 说明其层次关系及其类加载的主要流程即可.
2) TypeA.class位于classpath下, /absolute_path/TypeA.class为其在文件系统中的绝对路径, 且类文件小于1k, MyClassLoader为一个自定义的类加载器, 下面的这段类加载程序是否正确, 如果有错请指出哪一行有错, 简述理由
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStream;
public class Tester{
public static void main(String[] args){
MyClassLoader cl1=new MyClassLoader();
try{
File f=new File("/absolute_path/TypeA.class");
byte[] b=new byte[1024];
InputStream is=new FileInputStream(f);
int I=is.read(b);
Class c=cl1.defineMyClass(null,b,0,1);
TypeA a=(TypeA)c.newInstance();
}catch(Exception e){
e.printStacktrace();
}
}
}
第四部分(选作): Linux应用与开发
1. 写出完成以下功能的Linux命令:
1) 在当前目录及其子目录所有的.cpp文件中查找字符串"example", 不区分大小写;
2) 使用sed命令, 将文件xyz中的单词AAA全部替换为BBB;
3) 用一条命令创建aa bb cc三个子目录
4) mount cdrom.iso至/dev/cdrom目录
5) 设置ulimit使得程序在Segment fault等严重错误时可以产生coredump;
2. 设umask为002, 则新建立的文件的权限是什么?
A. -rw-rwr--
B. rwxrwx-w-
C. -------w-
D. rwxrwxr-x
3. 用户HOME目录下的.bashrc和.bash_profile文件的功能有什么区别?
4. 写出完成以下功能的gdb命令(可以使用命令简写形式):
1) 使用gdb调试程序foo, 使用coredump文件core.12023;
2) 查看线程信息
3) 查看调用堆栈
4) 在类ClassFoo的函数foo上设置一个断点
5) 设置一个断点, 当表达式expr的值被改变时触发
5.
1) 例举Linux下多线程编程常用的pthread库提供的函数名并给出简要说明(至少给出5个)
2) pthread库提供哪两种线程同步机制, 列出主要API
3) 使用pthread库的多线程程序编译时需要加什么连接参数?
第五部分(选作): Windows开发
1. DC(设备上下文)有哪几类? 区别在哪里?
2. 碰撞检测是游戏中经常要用到的基本技术 对于二维情况, 请回答以下问题:
1). 如何判断一个点在一个多边形内
2). 如何判断两个多边形相交
3). 如何判断两个点集所形成的完全图所围的区域是否相交
3. PostMessage SendMessage和PostThreadMessage的区别是什么
4. 什么叫Alpha混合? 当前流行的图片格式中哪些支持alpha通道? Layered Window和普通Window有什么区别?
5. 如果要实现一个多线程(非MFC)程序, 选择多线程CRT, 创建线程的时候应该用CreateThread还是_beginthreadex(), 为什么?
当你打算实现一个多线程(非MFC)程序，你会选择一个单线程的CRT(C运行时库)吗？如果你的回答是NO, 那么会带来另外一个问题，你选择了CreateThread来创建一个线程吗? 大多数人也许会立刻回答YES。可是很不幸，这是错误的选择。
我先来说一下我的结论，待会告诉你为什么。
如果要作多线程(非MFC)程序，在主线程以外的任何线程内
- 使用malloc(),free(),new
- 调用stdio.h或io.h,包括fopen(),open(),getchar(),write(),printf(),errno
- 使用浮点变量和浮点运算函数
- 调用那些使用静态缓冲区的函数如: asctime(),strtok(),rand()等。
你就应该使用多线程的CRT并配合_beginthreadex(该函数只存在于多线程CRT), 其他情况下你可以使用单线程的CRT并配合CreateThread。
因为对产生的线程而言，_beginthreadex比之CreateThread会为上述操作多做额外的簿记工作，比如帮助strtok()为每个线程准备一份缓冲区。
然而多线程程序极少情况不使用上述那些函数(比如内存分配或者io)，所以与其每次都要思考是要使用_beginthreadex还是CreateThread,不如就一棍子敲定_beginthreadex。
当然你也许会借助win32来处理内存分配和Io，这时候你确实可以以单线程crt配合CreateThread，因为io的重任已经从crt转交给了win32。这时通常你应该使用HeapAlloc，HeapFree来处理内存分配，用CreateFile或者GetStdHandle来处理 Io。
还有一点比较重要的是_beginthreadex传回的虽然是个unsigned long,其实是个线程Handle(事实上_beginthreadex在内部就是调用了CreateThread)，所以你应该用 CloseHandle来结束他。千万不要使用ExitThread()来退出_beginthreadex创建的线程，那样会丧失释放簿记数据的机会，应该使用_endthreadex.
第六部分(选作): 数据库开发
1. 基于哈希的索引和基于树的索引有什么区别?
2. User表用于记录用户相关信息, Photo表用于记录用户的照片信息, 两个表的定义如下:
CREATE TABLE User( --用户信息表
UserId bigint, --用户唯一id
Account varchar(30) --用户唯一帐号
);
CREATE TABLE Photo( --照片信息表
PhotoId bigint, --照片唯一id
UserId bigint, --照片所属用户id
AccessCount int, --访问次数
Size bigint --照片文件实际大小
)
1) 请给出SQL打印帐号为"dragon"的用户访问次数最多的5张照片的id;
2) 给出SQL打印拥有总的照片文件大小(total_size)最多的前10名用户的id, 并根据total_size降序排列
3) 为优化上面两个查询, 需要在User和Photo表上建立什么样的索引?
4) 简述索引对数据库性能的影响?
3. 什么是两阶段提交协议?
4. 数据库事务基本概念:
1) 什么是事务的ACID性质?
2) SQL标准中定义的事务隔离级别有哪四个?
3) 数据库中最常用的是哪两种并发控制协议?
4) 列举你所知的数据库管理系统中采用的并发控制协议
5. 数据库中有表User(id, name, age):
表中数据可能会是以下形式:
id name age
001 张三 56
002 李四 25
003 王五 56
004 赵六 21
005 钱七 39
006 孙八 56
..............
由于人员年龄有可能相等, 请写出SQL语句, 用于查询age最大的人员中, id最小的一个记录
6. 并发访问数据库时常使用连接池, 请问使用连接池的好处是什么? 对于有多台应用服务器并发访问一台中心数据库的情况, 数据库访问往往成为系统瓶颈, 请问在应用服务器上设计和使用连接池时该注意哪些问题, 以保证系统的可靠性 正确性和整体性能. 假设每台应用服务器都执行相同的任务并且负载均衡.
第七部分(选作): Web开发
1. 以下哪一条Javascript语句会产生运行错误:
A. var obj=( );
B. var obj=[ ];
C. var obj={ };
D. var obj=/ /;
2. 如下页面代码(示例代码DOCTYPE为Strict)
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="zh" lang="zh">
<head>
<title>测试</title>
<meta http-equiv="content-type" content="text/html; charset=gbk" />
<meta http-equiv="content-style-type" content="text/cee" />
<meta http-equiv="content-script-type" content="text/javascript" />
<script type="text/css">
*{margin:0; padding:0}
html{width:100%; height:100%;
overflow:scroll; overflow-x:auto;
text-align:center; border:0}
.test{height:200px}
</script>
</head>
<body>
<div class="text"> </div>
</body>
</html>
假设a.jpg图片的规格是200pxX100px, 请给出当前背景图片距div.a顶部距离的计算方式和结果(css)
3. HTTP协议相关知识
A) 常见的HTTP Request头字段有哪些?
B) web服务器如何区分访问者是普通浏览用户还是搜索引擎的Spider?
C) cookie按生命周期分类分为哪两类? 其生命周期分别是多长? 向浏览器设置cookie时cookie有哪些属性可以设置, 分别起到什么作用?
D) HTTP协议中Keep-Alive是什么意思? 使用Keep-Alive有何好处, 对服务器会有什么不利的影响? 对于不利的影响有什么解决方案
4. 简述你最常用的Web服务器的一种或者几种, 并说明如何在Web服务器和应用服务器之间建立反向代理
5. 简述你所了解的MVC各层次的常用开发框架, 说明其特点
6. 简述Web应用环境下远程调用的几种方式, 并且从性能 异构性等方面比较其优劣
第八部分(选作): Flash开发
7. flash和js如何交互?
8. flash中的事件处理分哪几个过程 Event对象的target和currentTarget有什么区别?
第九部分(选作): 软件测试
1. 请描述你对测试的了解, 内容可以涉及测试流程, 测试类型, 测试方法, 测试工具等
2. 如果有一天你早上上班, 发现不能上网了, 你会用什么步骤找出问题所在?
3. Web应用中实现了好友功能, 用户可以给别人发"加为好友"的请求, 发了请求后可以取消请求, 对方收到请求后, 可以选择接受或者拒绝. 互为好友的两个人, 每个人都可以单方面删除对方, 请设想尽可能多的路径对此功能设计测试用例, 每个用例包括测试步骤和预期结果
4. 公司开发了一个web聊天工具, 用于网络用户之间的聊天, 一个人同时可以和多个人聊天, 功能类似于MSN等等IM工具
要求该系统能承受1万个在线用户, 平均每个用户会和3个人同时聊天, 在网络条件正常的情况下, 要求用户收到消息的延迟时间不超过1分钟. 现在需要对系统进行性能测试, 验证系统是否达到预定要求, 请你写一个性能测试方案. 提示如下:
1) 性能测试的过程一般都是模拟大量客户端操作, 同时监控服务器的性能和客户端相应, 根据服务器的性能指标和客户端响应状况进行分析和判断
2) 系统的性能问题可以从两个角度考虑, 一个是服务器问题, 设计得不好的程序, 在大负载或者长时间运行情况下, 服务器会down机; 另一个是客户端问题, 在负载大的时候, 客户端响应会变慢
3) 在答题中, 可以不涉及性能测试工具, 监控工具等细节, 把你的测试思路说清楚就可以
5. 自动功能测试中会将测试用例组织成测试集合来统一运行, 测试集合suite按功能分类可以有若干个模块module, 每个模块module下包含若干个测试用例test. 现测试集合已经运行完毕, 但是需要在测试报告中统计各个模块的用例失败率, 将失败率超过20%的模块名与其失败率记录下来报警, 请编写实现上述功能的getTestReport函数. 可使用Java或C++等您熟悉的编程语言, 提供的接口及方法如下:
测试集合接口Isuite:
Collection<ITest>getTests() //得到测试集合下的所有测试用例test
测试用例接口Itest:
String getModule() //得到该用例对应的模块名称module
int getResult() //得到该用例的执行结果:0失败 1成功
报警函数:
void alertMessage(String message)
public static void getTestReport(ISuite suite){
//你的实现写在这里
}