A卷(研发类笔试题)
第一部分(必做): 计算机科学基础
1. (单选)软件设计中模块划分应该遵循的准则是:
2. (单选)最坏情况下时间复杂度不是n(n-1)/2的排序算法是:
3. 哈希表中解决冲突的方法通常可以分为open addressing和chaining两类, 请分别解释这两类冲突解决方法的大致实现原理
4. 简单的链表结构拥有很好的插入 删除节点性能, 但随机定位(获取链表第n个节点)操作性能不佳, 请你设计一种改进型的链表结构优化随机定位操作的性能, 给出设计思路及其改进后随机定位操作的时间复杂度
5. 什么是NP问题?列举典型的NP问题(至少两个)?对于一个给定的问题你通常如何判断它是否为NP问题?
6. 以下是一个tree的遍历算法, queue是FIFO队列, 请参考下面的tree, 选择正确的输出.
1
/ \
2
/ \ / \
4 5 6 7
queue.push(tree.root)
while(true){
node=queue.pop();
output(node.value);//输出节点对应数字
if(null==node)
for(child_node in node.children){
}
}
A. 1234567
B. 1245367
C. 1376254
D. 1327654
第二部分(选作): 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;
};
2. 请用C++实现以下print函数,打印链表I中的所有元素, 每个元素单独成一行
void print(const std::list<int> &I){
}
3. 假设某C工程包含a.c和b.c两个文件,在a.c中定义了一个全局变量foo, 在b.c中想访问这一变量时该怎么做?
4. C++中的new操作符通常完成两个工作, 分配内存及其调用相应的构造函数初始化
请问:
1) 如何让new操作符不分配内存, 只调用构造函数?
2) 这样的用法有什么用?
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;
}
6. 什么是C++ Traits? 并举例说明
第三部分(选作): JAVA程序设计
1. (单选)以下Java程序运行的结构是:
public class Tester{
public static void main(String[] args){
}
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){
}
}
第四部分(选作): 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,
Account varchar(30)
);
CREATE TABLE Photo(
PhotoId bigint, --照片唯一id
UserId bigint,
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
001 张三
002 李四
003 王五
004 赵六
005 钱七
006 孙八
..............
由于人员年龄有可能相等, 请写出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}
</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()
测试用例接口Itest:
String getModule()
int getResult()
报警函数:
void alertMessage(String message)
public static void getTestReport(ISuite suite){
}