A卷(研发类笔试题)
第一部分(必做): 计算机科学基础
1. (单选)软件设计中模块划分应该遵循的准则是:
A.低内聚低耦合 B.高内聚低耦合 C.低内聚高耦合 D.高内聚高耦合
2. (单选)最坏情况下时间复杂度不是n(n-1)/2的排序算法是:
A.快速排序 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);
}
}
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程序设计