恩,今天去参加了网易的笔试。题目随后更新。
1.长度为M字符串匹配与长度为N的字符串匹配的时间复杂度?
我查了查,O(M + N)。KMP能做到。
这里:http://blog.csdn.net/meixr/article/details/6456896
2.排序的稳定性:选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法
3.二叉平衡树的插入问题。
此时,插入3之后,画出新的二叉树?
插入3后,变成不平衡的了:如下:
节点5右旋一次:
节点2左旋一次:
4.求两个集合A和B的公共元素
5.Top K 算法;
6.数据库的概念:事务的定义?事务的属性?事务隔离级别的高低?
7.哪种设计模式可以使得调用者不关心具体算法?
策略模式
8.编程
8.1求解题目:没有看懂
8.2自己实现一个hashtable表
8.3如何限制栈对象的生成?如何限制堆对象的生成?
之前转载的那篇《C++内存管理》最后一章节——《对象内存大会战》有详细地描述。我转录如下:
禁止产生堆对象:
那么怎样禁止产生堆对象了?我们已经知道,产生堆对象的唯一方法是使用new操作,如果我们禁止使用new不就行了么。再进一步,new操作执行时会调用operator new,而operator new是可以重载的。方法有了,就是使new operator为private,为了对称,最好将operator delete也重载为private。现在,你也许又有疑问了,难道创建栈对象不需要调用new吗?是的,不需要,因为创建栈对象不需要搜索内存,而是直接调整堆栈指针,将对象压栈,而operator new的主要任务是搜索合适的堆内存,为堆对象分配空间,
禁止产生栈对象:
前面已经提到了,创建栈对象时会移动栈顶指针以“挪出”适当大小的空间,然后在这个空间上直接调用对应的构造函数以形成一个栈对象,而当函数返回时,会调用其析构函数释放这个对象,然后再调整栈顶指针收回那块栈内存。在这个过程中是不需要operator new/delete操作的,所以将operator new/delete设置为private不能达到目的。当然从上面的叙述中,你也许已经想到了:将构造函数或析构函数设为私有的,这样系统就不能调用构造/析构函数了,当然就不能在栈中生成对象了。
9.C++程序题目。写出运算结果
10.1是普通函数调用虚函数的结果
10.2是默认参数的问题。类似于这道题,记住:默认参数不参与动态绑定,与虚函数无关。
#include <iostream>
using namespace std;
class A
{
public:
virtual void Fun(int number = 10)
{
std::cout << "A::Fun with number " << number<<endl;
}
};
class B: public A
{
public:
virtual void Fun(int number = 20)
{
std::cout << "B::Fun with number " << number<<endl;
}
};
int main()
{
B b;
A &a = b;
a.Fun();
return 0;
} //虚函数动态绑定=>B,非A,缺省实参是编译时候确定的=>10,非20
10.3是C++各种成员变量的初始化问题。
主要是staitc,const,static const的问题;这里有详细地解答
http://blog.csdn.net/yjkwf/article/details/6067267
在C++中,static静态成员变量不能在类的内部初始化。在类的内部只是声明,定义必须在类定义体的外部,通常在类的实现文件中初始化,如:double Account::Rate=2.25;static关键字只能用于类定义体内部的声明中,定义时不能标示为static
在C++中,const成员变量也不能在类定义处初始化,只能通过构造函数初始化列表进行,并且必须有构造函数。
const数据成员 只在某个对象生存期内是常量,而对于整个类而言却是可变的。因为类可以创建多个对象,不同的对象其const数据成员的值可以不同。所以不能在类的声明中初始化const数据成员,因为类的对象没被创建时,编译器不知道const数据成员的值是什么。
const数据成员的初始化只能在类的构造函数的初始化列表中进行。要想建立在整个类中都恒定的常量,应该用类中的枚举常量来实现,或者static cosnt。
class Test
{
public:
Test():a(0){}
enum {size1=100,size2=200};
private:
const int a;//只能在构造函数初始化列表中初始化
static int b;//在类的实现文件中定义并初始化
const static int c;//与 static const int c;相同。
};
int Test::b=0;//static成员变量不能在构造函数初始化列表中初始化,因为它不属于某个对象。
cosnt int Test::c=0;//注意:给静态成员变量赋值时,不需要加static修饰符。但要加cosnt
附加题目
1.
2.XML的格式问题