第一部分(必做):
计算机科学基础l
(单选)软件设计中模块划分应该遵循的准则是:
低内聚低耦合 B。高内聚低耦合 C。低内聚高耦合 D。高内聚高耦合
(单选)最坏情况下时间复杂度不是n(n-1)/2的排序算法是:
快速排序 B。冒泡排序 C。直接插入排序 D。堆排序
3。 哈希表中解决冲突的方法通常可以分为open addressing和chaining两类，请分别解释这两类冲突解决方法的大致实现原理
4。 简单的链表结构拥有很好的插入 删除节点性能，但随机定位(获取链表第n个节点)操作性能不佳，请你设计一种改进型的链表结构优化随机定位操作的性能，给出设计思路及其改进后随机定位操作的时间复杂度
5。 什么是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);
}
}
1234567
1245367
1376254
1327654
第二部分(选作): C/C++程序设计l
有三个类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;
hort m2;
};
请用C++实现以下print函数,打印链表I中的所有元素，每个元素单独成一行
void print(const std::list &I){
}
假设某C工程包含a。c和b。c两个文件,在a。c中定义了一个全局变量foo，在b。c中想访问这一变量时该怎么做?
C++中的new操作符通常完成两个工作，分配内存及其调用相应的构造函数初始化
请问:
如何让new操作符不分配内存，只调用构造函数?
这样的用法有什么用?
下面这段程序的输出是什么?为什么?
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? 并举例说明
第四部分(选作): Linux应用与开发
写出完成以下功能的Linux命令:
在当前目录及其子目录所有的。cpp文件中查找字符串"example"，不区分大小写;
使用sed命令，将文件xyz中的单词AAA全部替换为BBB;
用一条命令创建aa bb cc三个子目录
mount cdrom。iso至/dev/cdrom目录
5) 设置ulimit使得程序在Segment fault等严重错误时可以产生coredump;
2。 设umask为002，则新建立的文件的权限是什么?664
A。 -rw-rwr—
B。 rwxrwx-w-
C。 -------w-
D。 rwxrwxr-x
上面第三题，aa bb cc 目录是嵌套的子目录么，要是同一级的话应该下面这样
1 #grep -i -r example 。/。cpp
2 #sed 's/AAA/BBB/g ' xyz
3 #mkdir aa bb cc
4 #mount -o loop 。/cdrom。iso /mnt/cdrom
5 C
3。 用户HOME目录下的。bashrc和。bash_profile文件的功能有什么区别?
4。 写出完成以下功能的gdb命令(可以使用命令简写形式):
1) 使用gdb调试程序foo，使用coredump文件core。12023;
2) 查看线程信息
3) 查看调用堆栈
4) 在类ClassFoo的函数foo上设置一个断点
5) 设置一个断点，当表达式expr的值被改变时触发
