经典笔试面试题(二)

╰+攻爆jí腚メ 2022-08-08 19:53 221阅读 0赞

1. 拷贝构造函数参数为什么是引用。

在C++中，构造函数，拷贝构造函数，析构函数和赋值函数(赋值运算符重载)是最基本不过的需要掌握的知识。但是如果我问你“拷贝构造函数的参数为什么必须使用引用类型？”这个问题，你会怎么回答？ 或许你会回答为了减少一次内存拷贝？ 很惭愧的是，我的第一感觉也是这么回答。不过还好，我思索一下以后，发现这个答案是不对的。

原因：

如果拷贝构造函数中的参数不是一个引用，即形如CClass(const CClass c\_class)，那么就相当于采用了传值的方式(pass-by-value)，而传值的方式会调用该类的拷贝构造函数，从而造成无穷递归地调用拷贝构造函数。因此拷贝构造函数的参数必须是一个引用。

需要澄清的是，传指针其实也是传值，如果上面的拷贝构造函数写成CClass(const CClass\* c\_class)，也是不行的。如果这里是指针的话，那么它不能称之为拷贝构造函数，而是一个普通的构造函数。参数是指针而已。默认的拷贝构造函数依然会生成。事实上，只有传引用不是传值外，其他所有的传递方式都是传值。

先从一个小例子开始：（自己测试一下自己看看这个程序的输出是什么？

\#include<iostream>

using namespace std;

class CExample

private:

int m\_nTest;

public:

CExample(int x) : m\_nTest(x) //带参数构造函数

cout << "constructor with argument"<<endl;

// 拷贝构造函数，参数中的const不是严格必须的，但引用符号是必须的

CExample(const CExample & ex) //拷贝构造函数

m\_nTest = ex.m\_nTest;

cout << "copy constructor"<<endl;

CExample& operator = (const CExample &ex) //赋值函数(赋值运算符重载)

cout << "assignment operator"<<endl;

m\_nTest = ex.m\_nTest;

return \*this;

void myTestFunc(CExample ex)

\};

int main(void)

CExample aaa(2);

CExample bbb(3);

bbb = aaa;

CExample ccc = aaa;

bbb.myTestFunc(aaa);

return 0;

这个例子的输出结果是：

constructor with argument // CExample aaa(2);

constructor with argument // CExample bbb(3);

assignment operator // bbb = aaa;

copy constructor // CExample ccc = aaa;

copy constructor // bbb.myTestFunc(aaa);

如果你能一眼看出就是这个结果的话，恭喜你，可以站起来扭扭屁股，不用再往下看了。

如果你的结果和输出结果有误差，那拜托你谦虚的看完。

第一个输出： constructor with argument // CExample aaa(2);

如果你不理解的话，找个人把你拖出去痛打一顿，然后嘴里还喊着“我是二师兄，我是二师兄.......”

第二个输出：constructor with argument // CExample bbb(3);

分析同第一个

第三个输出： assignment operator // bbb = aaa;

第四个输出： copy constructor // CExample ccc = aaa;

这两个得放到一块说。肯定会有人问为什么两个不一致。原因是， bbb对象已经实例化了，不需要构造，此时只是将aaa赋值给bbb，只会调用赋值函数，就这么简单，还不懂的话，撞墙去！但是ccc还没有实例化，因此调用的是拷贝构造函数，构造出ccc，而不是赋值函数，还不懂的话，我撞墙去！！

第五个输出： copy constructor // bbb.myTestFunc(aaa);

实际上是aaa作为参数传递给bbb.myTestFunc(CExample ex)， 即CExample ex = aaa；和第四个一致的， 所以还是拷贝构造函数，而不是赋值函数， 如果仍然不懂， 我的头刚才已经流血了，不要再让我撞了，你就自己使劲的再装一次吧。

通过这个例子，我们来分析一下为什么拷贝构造函数的参数只能使用引用类型。

看第四个输出： copy constructor // CExample ccc = aaa;

构造ccc，实质上是ccc.CExample(aaa); 我们假如拷贝构造函数参数不是引用类型的话，那么将使得 ccc.CExample(aaa)变成aaa传值给ccc.CExample(CExample ex)，即CExample ex = aaa，因为 ex 没有被初始化， 所以 CExampleex = aaa 继续调用拷贝构造函数，接下来的是构造ex，也就是 ex.CExample(aaa)，必然又会有aaa传给CExample(CExample ex), 即 CExample ex = aaa;那么又会触发拷贝构造函数，就这下永远的递归下去。

所以绕了那么大的弯子，就是想说明拷贝构造函数的参数使用引用类型不是为了减少一次内存拷贝，而是避免拷贝构造函数无限制的递归下去。

附带说明，在下面几种情况下会调用拷贝构造函数：

a、 显式或隐式地用同类型的一个对象来初始化另外一个对象。如上例中，用对象c初始化d；

b、 作为实参(argument)传递给一个函数。如CClass(constCClass c\_class)中，就会调用CClass的拷贝构造函数；

c、 在函数体内返回一个对象时，也会调用返回值类型的拷贝构造函数；

d、 初始化序列容器中的元素时。比如vector<string> svec(5)，string的缺省构造函数和拷贝构造函数都会被调用；

e、 用列表的方式初始化数组元素时。stringa\[\] = \{string(“hello”), string(“world”)\}; 会调用string的拷贝构造函数。

如果在没有显式声明构造函数的情况下，编译器都会为一个类合成一个缺省的构造函数。如果在一个类中声明了一个构造函数，那么就会阻止编译器为该类合成缺省的构造函数。和构造函数不同的是，即便定义了其他构造函数(但没有定义拷贝构造函数)，编译器总是会为我们合成一个拷贝构造函数。

另外函数的返回值是不是引用也有很大的区别，返回的不是引用的时候，只是一个简单的对象，此时需要调用拷贝构造函数，否则，如果是引用的话就不需要调用拷贝构造函数。

\#include<iostream>

using namespace std;

class A

private:

int m\_nTest;

public:

A()

A(const A& other) //构造函数重载

m\_nTest = other.m\_nTest;

cout << "copy constructor"<<endl;

A& operator =(const A& other)

if(this != &other)

m\_nTest = other.m\_nTest;

cout<<"Copy Assign"<<endl;

return \*this;

\};

A fun(A &x)

return x; //返回的不是引用的时候，需要调用拷贝构造函数

int main(void)

Atest;

fun(test);

system("pause");

return 0;

分享一道笔试题目，编译运行下图中的C++代码，结果是什么？（A）编译错误；（B）编译成功，运行时程序崩溃；（C）编译运行正常，输出10。请选择正确答案并分析原因。

class A

private:

int value;

public:

A(int n)

value = n;

A(A other)

value = other.value;

void Print()

cout<<value<<endl;

\};

int main(void)

Aa = 10;

Ab = a;

b.Print();

return 0;

答案：编译错误。在复制构造函数中传入的参数是A的一个实例。由于是传值，把形参拷贝到实参会调用复制构造函数。因此如果允许复制构造函数传值，那么会形成永无休止的递归并造成栈溢出。因此C++的标准不允许复制构造函数传值参数，而必须是传引用或者常量引用。在Visual Studio和GCC中，都将编译出错。

2. 设计一个不能被继承的类。

在C\#中定义了关键字sealed，被sealed修饰的类不能被继承。在Java中同样也有关键字final表示一个类型不能被继承。在C++中没有类似于sealed和final的关键字，所以我们只有自己来实现。

很多人都能够想到，类的构造函数和析构函数是关键。因为子类的构造函数会自动调用父类的构造函数。子类的析构函数也会自动调用父类的析构函数。所以要想使一个类不能被继承，只有把它的构造函数和析构函数都定义为私有函数，那么当一个类试图从这个类继承的时候，必然会先调用构造函数而产生编译错误，从而导致继承失败。

这个不能被继承类的构造函数和析构函数都是私有函数，那么怎样才能得到该类的实例呢？这倒不难，可以通过定义公有的静态函数来创建和释放类的实例，实现该类不能被继承但能被实例化的功能。

基于这个思路，我们可以写出如下代码：

\#include<iostream>

using namespace std;

class SealedClass

private: // 私有成员

SealedClass() \{ \}; // 构造函数

~SealedClass() \{ \}; // 析构函数

public:

int m\_number;

static SealedClass\* GetInstance(int number) // 用于构造的函数

SealedClass \* pInstance = new SealedClass();

pInstance->m\_number = number;

return pInstance;

static void DeleteInstance(SealedClass\* pInstance) // 用于析构的函数

delete pInstance;

pInstance = 0;

\};

int main(void)

SealedClass \* p = SealedClass::GetInstance(9);

cout<<"m\_number is :"<<p->m\_number<<endl;

SealedClass::DeleteInstance(p);

cout<<"m\_number is :"<<p->m\_number<<endl;

return 0;

3. 张老师的生日是哪一天

小明和小强都是张老师的学生，张老师的生日是某月某日，2人都不知道张老师的生日。

生日是下列10组中一天：

3月4日 3月5日 3月8日

6月4日 6月7日

9月1日 9月5日

12月1日 12月2日 12月8日

张老师把月份告诉了小明，把日子告诉了小强，张老师问他们知道他的生日是那一天吗？

小明说：如果我不知道的话，小强肯定也不知道。

小强说：本来我也不知道，但是现在我知道了。

小明说：哦，那我也知道了。

请根据以上对话推断出张老师生日是哪一天？

分析问题：

首先分析这10组日期，经观察不难发现，只有6月7日和12月2日这两组日期的日数是唯一的，而小明的第一话说明他所掌握的月份之内没有唯一的日子存在。由此可见，如果生日是6月或12月的话，那么小强就有可能知道，因为日子7和2是唯一的，所以不可能是6月和12月；

现在剩下3 月和9月，则张老师的生日只能是下面的几个日子：

3月4日 3月5日 3月8日

9月1日 9月5日

小强说：本来我也不知道，但是现在我知道了。凭借日子就知道了月份，因此日子在剩下的3月和9月中没有重复，即不是5日。

而小强知道了，小明也知道了，说明月份是9。因为如果月份是3的话，有4、8两个数字，小明就不可能知道，这样张老师的生日就只能是9月1日了。

4. 小猴最多能运回多少根香蕉

一个小猴子边上有100根香蕉，它要走过50米才能到家，每次它最多搬50根香蕉，它每走1米就要吃掉一根，请问它最多能把多少根香蕉搬到家？

分析问题：

小猴每次最多能够带50根香蕉，所以第一次要留在原地50根香蕉，假设第一次走出n米后，再带n根香蕉返回，剩余的50-2n根香蕉就放在距家50-n米处了。

若要搬尽量多的香蕉回家，则50-2n>0，所以n<25。然后小猴带n根香蕉返回出发点，搬剩下的50根香蕉到距家50-n米处，此时还剩下100-3n根香蕉。

由原题可知，小猴每次走出一段再返回后都要多吃几根香蕉，所以要想多搬回香蕉，办法就是尽量少返回，而返回的原因是一次最多能够搬50根，当香蕉多余50根的时候一次不能搬尽，要返回再搬，所以第一次走出n米，返回剩余的50根到距家50-n米处，剩余100-3n根，根据上面的分析，100-3n要小于50，由于每次返回都要多消耗2n根，所以n要尽量小，即剩余的根数要尽量大且小于50。

则 100-3n<=50

得 n<=17

所以第一次应走出17米后再返回，剩余100-17\*3=49根，此时距家33米，所以到家最多能够剩余16根香蕉。

5. 剩下的是什么牌

有9张纸牌，分别为1至9。甲、乙、丙、丁四人取牌，每人取2张。现已知：

甲取的两张牌之和是10；

乙取的两张牌之差是1；

丙取的两张牌之积是24；

丁取的两张牌之商是3；

请问剩下的一张是什么？

A、6 B、3 C、7 D、4

分析问题：

由于丙取的两张牌之积是24，则只有两种可能：3和8、4和6

由于丁取的两张牌之商是3；则只有三种可能：1和3、2和6、3和9

（1）假设丙拿的是3和8，那么丁只能拿2和6，甲只能拿1和9，乙只能拿4和5了，这样剩下一张7，满足条件。

（2）假设丙拿的是4和6，丁拿1和3，那么甲只能拿2和8，而乙只剩下5、7、9没有两张之差为1的两张牌可取了，所以这种拿法不成立。

（3）假设丙拿的是4和6，丁拿3和9，那么甲只能拿2和8，而乙只剩下1、5、7没有两张之差为1的两张牌可取了，所以这种拿法不成立。

所以丙拿的是3和8，丁拿的是2和6，乙拿的是4和5，甲拿的是1和9，剩下一张7。

6. 有100盏灯，从1~100编上号，开始时所有的灯都是关着的。第一次，把所有编号是1的倍数的灯的开关状态改变一次；第二次，把所有编号是2的倍数的灯的开关状态改变一次；第三次，把所有编号是3的倍数的灯的开关状态改变一次； 依此类推，直到把所有编号是100的倍数的灯的开关状态改变一次。 问，此时所有开着的灯的编号。

由于最开始时灯是灭的，那么只有经过奇数次改变开关状态的灯是亮的。根据题意可知一个数字有多少约数就要按下开关多少次，所以最后亮着的灯的数学解释就是：灯的编号有奇数个不同的约数。为什么是这样呢？举个例子8，他被1和8各约一次，被2和4各约一次。总共被约了4次，所以被关了。而36被约了9次，所以开了。

一个数的约数按出现的奇偶个数分为以下两种：

约数是成对出现的，比如8的约数对为：（1,8）、（2，4）

约数是单个出现的，比如36的约数对为：（1,36）、（2，18）、（3，12）、（4,9）、（6）

可以看出6自己单独是36的约数，而不是和别的数连在一起的。所以只有平方数才会有奇数个整型约数，才满足本题的要求。从1到100的平方数为：1、4、9、16、25、36、49、64、81、100，所以只有这些灯是亮的。

答：编号为1、4、9、16、25、36、49、64、81、100的灯是亮的。

7. 有两个父亲分别给他们的儿子一些钱，其中一个父亲给了儿子150元，另一个父亲给了儿子100元钱。但两个儿子却说他们一共只得了150元，那100元哪里去了呢？

答：这三个人是祖孙三代，爷爷付出了150元钱，爸爸得到50元钱，儿子得到100元钱。

8. 有两位盲人，他们都各自买了两对黑袜和两对白袜，八对袜子的布质、大小完全相同，而每对袜子都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。他们每人怎样才能取回黑袜和白袜各两对呢？

将每对袜子拆开一人一只。

9. 有个村子，村民的发色只有黑、红两种，没有可供看到自己发色的物品。村里的传统是知道自己发色的自杀可以上天堂，反之，下地狱。但是不可以问村子中的人。有3个很想上天堂的人，天天在广场上聚会，有一天一个外乡人路过，打破了平静。他说，你们中间至少有一个人是红头发的，然后走了。3个人听后回家苦思，第2天照常聚会，回去后2个人自杀成功，上了天堂。最后1个人第3天看到只有自己1个人后，也会去开开心心地自杀成功，上了天堂。问：他们分别是什么发色？

正确的应该是：前两个人是红，第三个是黑

解释：

第一天：他们听说外乡人说：至少有一个是红头发。假设只有一个人是红头发，那么他看到对面两人都是黑发，他就知道自己是红发，第一天就会自杀了；但第一天没有人自杀，证明至少有两人是红头发。

第二天：假设三个人都是红头发，每个人看到的对面都是两个红头发，就不能肯定自己是什么颜色；但第二天有人自杀成功了，说明有人是黑头发。因为那两个红头发的人看到的对面的人都是一个红，一个黑，他们就知道自己肯定是红头发。

第三天：第三个人看见前两个人都自杀成功了，他就能推出自己是黑头发了

10. 一群人开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种，黑的至少有一顶。每个人都能看到其他人帽子的颜色，却看不到自己的。主持人先让大家看看别人头上戴的是什么帽子，然后关灯，如果有人认为自己戴的是黑帽子，就打自己一个耳光。第一次关灯，没有声音。于是再开灯，大家再看一遍，关灯时仍然鸦雀无声。一直到第三次关灯，才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子？3个

这是道典型的逻辑题，奥妙就在你得作个假设。假如只有一个人戴黑帽子，那他看到所有人都戴白帽，在第一次关灯时就应打耳光，所以应该不止一个人戴黑帽子；如果有两顶黑帽子，第一次两人都只看到对方头上的黑帽子，不敢确定自己的颜色，但到第二次关灯，这两人应该明白，如果自己戴着白帽，那对方早在上一次就应打耳光了，因此自己戴的也是黑帽子―――于是也会有两个人打耳光；可事实是第三次才响起打耳光声，说明全场有三顶黑帽，依此类推，应该是关几次灯，有几顶黑帽。

11. 有50家人家，每家一条狗。有一天警察通知，50条狗当中有病狗，行为和正常狗不一样。每人只能通过观察别人家的狗来判断自己家的狗是否生病，而不能看自己家的狗，如果判断出自己家的狗病了，就必须当天一枪打死自己家的狗。结果，第一天没有枪声，第二天没有枪声，第三天开始一阵枪响，问：一共死了几条狗？答：死了3条（第几天枪响就有几条）。

简单分析：从有一条不正常的狗开始，显然第一天将会听到一声枪响。这里的要点是你只需站在那条不正常狗的主人的角度考虑。

有两条的话思路继续，只考虑有两条不正常狗的人，其余人无需考虑。通过第一天他们了解了对方的信息。第二天杀死自己的狗。换句话说每个人需要一天的时间证明自己的狗是正常的。有三条的话，同样只考虑那三个人，其中每一个人需要两天的时间证明自己的狗是正常的狗。

12. 下面的代码输出的结果是什么，并简单分析结果。

\#include <stdio.h>

//无符号数与有符号数相加

int main(int argc, char \*\*argv)

unsignedint a = 6;

intb = -12;

if(a+b> 0)

printf("dsds\\n");

printf("a+b=%d\\n", a+b);

printf("a+b=%p\\n", (void \*)(a+b));

else

printf("ssss\\n");

printf("a+b=%d\\n", a+b);

printf("a+b=%p\\n", (void \*)(a+b));

return0;

答案：

dsds

a+b=-6

a+b=0xFFFFFFFA

原因：当无符号数与有符号数相加时，将相加后的结果转化为无符号数，为什么第一个结果是-6呢，因为%d输出的时候是按照有符号数输出的。第二个输出语句就是按照内存里的内容输出的。为什么是0xFFFFFFFA，-6的补码就是0xFFFFFFFA，计算机在内存中存储数据的格式是补码的格式，所以打印出来的结果就是一个大于0的数。这就充分说明了a+b>0了。

13. 下面的函数有什么错误：

int square(volatile int \*ptr)

return\*ptr \* \*ptr;

编译器将产生类似下面的代码：

int square(volatile int \*ptr)

inta,b;

a= \*ptr;

b= \*ptr;

returna \* b;

由于\*ptr的值可能被意想不到的改变，因此a和b可能是不同的。结果，这段代码可能返不是你所期望的平方值！正确的代码如下：

long square(volatile int \*ptr)

inta;

a=\*ptr;

returna \* a;

14. malloc（0）你注意过吗？下面分析这段代码：

\#include<stdio.h>

\#include<stdlib.h>

//malloc（0）函数 返回值不空

int main(int argc, char \*\*argv)

char\*pointer;

if((pointer= (char \*)malloc(0)) == NULL)

printf("isnull pointer\\n");

printf("pointer:%p\\n",pointer);

\*pointer= 'a';

printf("%c\\n",\*pointer);

free(pointer);

else

printf("isvalited pointer\\n");

printf("pointer:%p\\n",pointer);

\*pointer= 'b';

printf("%c\\n",\*pointer);

free(pointer);

return0;

malloc(0)返回堆上的任意一个字节的地址，并且返回的地址空间可以对其进行操作。

运行结果：

is valited pointer

pointer:0x7f23adff

15. Typedef 在C语言中频繁用以声明一个已经存在的数据类型的同义字。也可以用预处理器做类似的事。例如，思考一下下面的例子，那个更好，为什么？

\#define dPS struct s \*

typedef struct s \* tPS;

答案是：typedef更好。思考下面的例子：

dPS p1,p2;

tPS p3,p4;

第一个扩展为

struct s \* p1, p2;

上面的代码定义p1为一个指向结构的指，p2为一个实际的结构，这也许不是你想

要的。第二个例子正确地定义了p3 和p4 两个指针。

16. C语言同意一些令人震惊的结构,下面的结构是合法的吗，如果是它做些什么？

int a = 5, b = 7, c;

c = a+++b;

上面的代码被处理成：

c = (a++) + b;

因此, 这段代码执行后的结果是： a = 6, b = 7, c = 12。

17. 一道关于宏的面试题及解答

\#include<iostream>

using namespace std;

\#define SQR(X) X\*X

int main(void)

inta = 10;

intk = 2;

intm = 1;

a/= SQR(k+m)/SQR(k+m);

printf("%d\\n",a);

return0;

这道题目的结果是什么啊？

【解答】

典型错误1：

SQR(k+m)/SQR(k+m) = 1;

最后得到a = 10;

原因：\#define 只是宏定义而已，在编译前会将\#define定义的内容进行替换，然后进行编译。这一点与函数大不相同。结果认为是10，很可能将SQR这个宏定义当作函数来用了。

典型错误2：

进行宏替换，得：

a /= (k+m)\*(k+m)/(k+m)\*(k+m);

=> a /= (k+m)\*1\*(k+m);

=> a = a/9;

=> a = 1;

原因：宏替换是按照宏定义进行的严格不变的替换，所以上面的替换结果应该为：

a /= k+m\*k+m/k+m\*k+m;

=> a /= 2+1\*2+1/2+1\*2+2;

=> a /= 7;

=> a = 1;

【评析】

该题目主要考查两点：

1、慎用宏定义，如果需要用宏，考虑是否可以通过函数、模板、或const定义等代替之。例如本题，使用函数实现可以轻松避免以上问题。

2、宏定义的方式：在所有参数上一定要加括号。本题中\#define SQR(X) X\*X 就属于不良风格的宏定义方式，良好的风格应该为：\#define SQR(X) (X)\*(X)，这样，计算的结果就是a /= (k+m)\*(k+m)/(k+m)\*(k+m)，最后结果仍为1。或者定义为：\#defineSQR(X) ((X)\*(X))，这样最后的结果是10。

3. 1/2的结果为多少，不要说是0.5啊，结果为整数，所以为0.

18. 操作系统中的同步和异步有什么区别？分别应用在什么场合？

答：同步，就是说你的程序在执行某一个操作时一直等待直到操作完成。最常见的例子就是SendMessage。该函数发送一个消息给某个窗口，在对方处理完消息之前，这个函数不返回。当对方处理完毕以后，该函数才把消息处理函数所返回的 LRESULT值返回给调用者。

异步，就是说程序在执行某一个操作时，只是发出开始的指令；由另外的并行程序执行这段代码，当完成时再通知调用者。当一个客户端通过调用 Connect函数发出一个连接请求后，调用者线程立刻可以朝下运行。当连接真正建立起来以后，socket底层会发送一个消息通知该对象。

打个比喻：

有一个男的看上了两个漂亮MM 想通过写信的方式跟他们交流感情这两个MM分别是 A女、B女

同步：他先给A女写了封信然后发了出去。等了好几天 A女给他回了信，之后他才给B女写信。就是说等到一个任务返回或者结束他才继续往下做他想做的任务。

异步：他先给A女写了封信，然后发了出去，马上又给B女写了封信也发了出去。就是说不用等到一个任务结束就去做下一个任务。

但是如果第一个任务需要第二个任务的返回值那就得用同步让第一个任务等待第二个任务结束后，获取第二个任务的返回值，在继续往下做。

并行：两个帅哥同时给这两个妹妹写信。

同步和异步的简单区别：

举个例子：普通B/S模式（同步）AJAX技术（异步）

同步：提交请求->等待服务器处理->处理完毕返回这个期间客户端浏览器不能干任何事

异步: 请求通过事件触发->服务器处理（这是浏览器仍然可以作其他事情）->处理完毕

\--------------------------------------------------------------------------------------------------------------------

同步就是你叫我去吃饭，我听到了就和你去吃饭；如果没有听到，你就不停的叫，直到我告诉你听到了，才一起去吃饭。

异步就是你叫我，然后自己去吃饭，我得到消息后可能立即走，也可能等到下班才去吃饭。

所以，要我请你吃饭就用同步的方法，要请我吃饭就用异步的方法，这样你可以省钱。

\--------------------------------------------------------------------------------------------------------------------

举个例子：打电话是同步，发消息是异步。

19. 数据库的ACID特定是什么？以及他们分别应用的场合

答：ACID是指数据库事务具有的四个特性：原子性、一致性、隔离性、持久性

原子性：事务是数据库的逻辑工作单位，事务中包括的操作要么都做，要么都不做。只有使据库事务中所有的操作都执行成功，才算整个事务成功；事务中任何一个SQL语句执行失败，那么已经执行成功的SQL语句也必须撤销，数据库状态应该回滚（ROLLBACK）到执行事务前的状态。

一致性：如果在执行事务之前数据库是一致的，那么在执行事务之后数据库也还是一致的；事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态。因此当数据库只包含成功事务提交的结果时，就说数据库处于一致性状态。如果数据库系统运行中发生故障，有些事务尚未完成就被迫中断，这些尚未完成的事务对数据库所做的修改有一部分已写入物理数据库，这时数据库就处于一种不正确的状态，或者说是不一致的状态。例如某公司在银行中有A、B两个账号，现在公司想从A中减去一万元，存入账号B。那么就可以定义一个事务，该事务包括两个操作，第一个操作就是从账号A减去一万元，第二个操作就是向账号B中加入一万元。这两个操作要么全做，要么全不做，数据库都处于一致性状态。如果只做一个操作则用户逻辑上就会发生错误，少了一万元，这时数据库就处于不一致状态。可见一致性与原子性是密切相关的。

隔离性：一个事务的执行不能被其他事务干扰。即一个事务内部的操作及使用的数据对其他并发事务是隔离的，并发执行的各个事务之间不能互相干扰。独立的数据库事务集合以不相互冲突的方式执行。仍使用这个银行类比，考虑两个客户同时在帐户之间转移资金。数据库必须分别跟踪两个转帐；否则，资金可能进入错误的帐户。

持久性：指一个事务一旦提交，它对数据库中数据的改变就应该是永久性的。接下来的其他操作或故障不应该对其执行结果有任何影响。 只要事务成功结束，它对数据库所做的更新就必须永久保存下来。即使发生系统崩溃，重新启动数据库系统后，数据库还能恢复到事务成功结束时的状态。

20. 判断字符串是否为IP地址

思路：输入字符串的时候，把分隔符“.”读取出来，然后判断分隔符旁边的数字是否在0~~255之间，然后判断是否合法。

\#include <stdio.h>

\#include <string.h>

int main(void)

charstr\[31\],temp\[31\];

inta,b,c,d;

while(gets(str)!=NULL)

if(sscanf(str,"%d.%d.%d.%d ",&a,&b,&c,&d)==4 && a>=0 && a<=255 && b>=0 && b<=255&& c>=0 && c<=255 && d>=0 && d<=255)

sprintf(temp,"%d.%d.%d.%d",a,b,c,d); //把格式化的数据写入字符串temp

if(strcmp(temp,str)==0)

printf("YES\\n");

else

printf("NO\\n");

else

printf("NO\\n");

return0;

21. 指针和数组的区别？

数组名相当于一个常指针，不能作为左值为他赋值。

22. 进程和线程的区别？

进程和线程的关系：

（1）一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。

（2）资源分配给进程，同一进程的所有线程共享该进程的所有资源。

（3）处理机分给线程，即真正在处理机上运行的是线程。

（4）线程在执行过程中，需要协作同步。不同进程的线程间要利用消息通信的办法实现同步。线程是指进程内的一个执行单元,也是进程内的可调度实体。

进程与线程的区别：

（1）调度：线程作为调度和分配的基本单位，进程作为拥有资源的基本单位

（2）并发性：不仅进程之间可以并发执行，同一个进程的多个线程之间也可并发执行

（3）拥有资源：进程是拥有资源的一个独立单位，线程不拥有系统资源，但可以访问隶属于进程的资源.

（4）系统开销：在创建或撤消进程时，由于系统都要为之分配和回收资源，导致系统的开销明显大于创建或撤消线程时的开销。

23. 两个进程之间的通信方式有哪几种？

（1）管道（pipe）及有名管道（namedpipe）：管道可用于具有亲缘关系的父子进程间的通信，有名管道除了具有管道所具有的功能外，它还允许无亲缘关系进程间的通信。

（2）信号（signal）：信号是在软件层次上对中断机制的一种模拟，它是比较复杂的通信方式，用于通知进程有某事件发生，一个进程收到一个信号与处理器收到一个中断请求效果上可以说是一致的。

（3）消息队列（messagequeue）：消息队列是消息的链接表，它克服了上两种通信方式中信号量有限的缺点，具有写权限得进程可以按照一定得规则向消息队列中添加新信息；对消息队列有读权限得进程则可以从消息队列中读取信息。

（4）共享内存（sharedmemory）：可以说这是最有用的进程间通信方式。它使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据得更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等。

（5）信号量（semaphore）：主要作为进程之间及同一种进程的不同线程之间得同步和互斥手段。

（6）套接字（socket）：这是一种更为一般得进程间通信机制，它可用于网络中不同机器之间的进程间通信，应用非常广泛。

操作系统的主要任务是管理计算机的软件、硬件资源。现代操作系统的主要特点是多用户和多任务，也就是程序的并行执行，windows如此linux也是如此。所以操作系统就借助于进程来管理计算机的软、硬件资源，支持多任务的并行执行。要并行执行就需要多进程、多线程。因此多进程和多线程间为了完成一定的任务，就需要进行一定的通信。而线程间通信又和进程间的通信不同。由于进程的数据空间相对独立而线程是共享数据空间的，彼此通信机制也很不同。

线程间通信：由于多线程共享地址空间和数据空间，所以多个线程间的通信是一个线程的数据可以直接提供给其他线程使用，而不必通过操作系统（也就是内核的调度）。

进程间的通信则不同，它的数据空间的独立性决定了它的通信相对比较复杂，需要通过操作系统。以前进程间的通信只能是单机版的，现在操作系统都继承了基于套接字（socket）的进程间的通信机制。这样进程间的通信就不局限于单台计算机了，实现了网络通信。

进程的通信机制主要有：管道、有名管道、消息队列、信号量、共享空间、信号、套接字。

管道：它传递数据是单向性的，只能从一方流向另一方，也就是一种半双工的通信方式；只用于有亲缘关系的进程间的通信，亲缘关系也就是父子进程或兄弟进程；没有名字并且大小受限，传输的是无格式的流，所以两进程通信时必须约定好数据通信的格式。管道它就像一个特殊的文件，但这个文件之存在于内存中，在创建管道时，系统为管道分配了一个页面作为数据缓冲区，进程对这个数据缓冲区进行读写，以此来完成通信。其中一个进程只能读一个只能写，所以叫半双工通信，为什么一个只能读一个只能写呢?因为写进程是在缓冲区的末尾写入，读进程是在缓冲区的头部读取，他们各自的数据结构不同，所以功能不同。

有名管道：看见这个名字就能知道个大概了，它于管道的不同的是它有名字了。这就不同与管道只能在具有亲缘关系的进程间通信了。它提供了一个路径名与之关联，有了自己的传输格式。有名管道和管道的不同之处还有一点是,有名管道是个设备文件，存储在文件系统中，没有亲缘关系的进程也可以访问，但是它要按照先进先出的原则读取数据。同样也是单双工的。

消息队列：是存放在内核中的消息链表，每个消息队列由消息队列标识符标识，于管道不同的是，消息队列存放在内核中，只有在内核重启时才能删除一个消息队列，内核重启也就是系统重启，同样消息队列的大小也是受限制的。

信号量：也可以说是一个计数器，常用来处理进程或线程同步的问题，特别是对临界资源的访问同步问题。临界资源：为某一时刻只能由一个进程或线程操作的资源，当信号量的值大于或等于0时，表示可以供并发进程访问的临界资源数，当小于0时，表示正在等待使用临界资源的进程数。更重要的是，信号量的值仅能由PV操作来改变。

共享内存：就是分配一块能被其他进程访问的内存。共享内存可以说是最有用的进程间通信方式，也是最快的IPC形式。首先说下在使用共享内存区前，必须通过系统函数将其附加到进程的地址空间或说为映射到进程空间。两个不同进程A、B共享内存的意思是，同一块物理内存被映射到进程A、B各自的进程地址空间。进程A可以即时看到进程B对共享内存中数据的更新，反之亦然。由于多个进程共享同一块内存区域，必然需要某种同步机制，互斥锁和信号量都可以。采用共享内存通信的一个显而易见的好处是效率高，因为进程可以直接读写内存，而不需要任何数据的拷贝。对于像管道和消息队列等通信方式，则需要在内核和用户空间进行四次的数据拷贝，而共享内存则只拷贝两次数据：一次从输入文件到共享内存区，另一次从共享内存区到输出文件。实际上，进程之间在共享内存时，并不总是读写少量数据后就解除映射，有新的通信时，再重新建立共享内存区域。而是保持共享区域，直到通信完毕为止，这样，数据内容一直保存在共享内存中，并没有写回文件。共享内存中的内容往往是在解除映射时才写回文件的。因此，采用共享内存的通信方式效率是非常高的。

信号：信号是在软件层次上对中断机制的一种模拟，在原理上，一个进程收到一个信号与处理器收到一个中断请求可以说是一样的。信号是异步的，一个进程不必通过任何操作来等待信号的到达，事实上，进程也不知道信号到底什么时候到达。信号是进程间通信机制中唯一的异步通信机制，可以看作是异步通知，通知接收信号的进程有哪些事情发生了。信号机制经过POSIX实时扩展后，功能更加强大，除了基本通知功能外，还可以传递附加信息。信号事件的发生有两个来源：硬件来源(比如我们按下了键盘或者其它硬件故障)；软件来源。信号分为可靠信号和不可靠信号，实时信号和非实时信号。进程有三种方式响应信号1.忽略信号2.捕捉信号3.执行缺省操作。

套接字：这一块在网络编程那一块讲的很多，在此就不在说拉。

24. 以下哪些协议不是应用层通信协议？(D)

A、HTTP、TELNET B、FTP、SMTP C、SNMP、NBNS D、ICMP、ARP

ICMP: ICMP是（Internet ControlMessage Protocol）Internet控制报文协议。它是TCP/IP协议族的一个子协议，用于在IP主机、路由器之间传递控制消息。控制消息是指网络通不通、主机是否可达、路由是否可用等网络本身的消息。这些控制消息虽然并不传输用户数据，但是对于用户数据的传递起着重要的作用。

协议族:TCP/IP协议族

归属: 网络层协议

作用: 在主机与路由器之间传递控制信息

ARP: 地址解析协议，即ARP（AddressResolution Protocol），是根据IP地址获取物理地址的一个TCP/IP协议。主机发送信息时将包含目标IP地址的ARP请求广播到网络上的所有主机，并接收返回消息，以此确定目标的物理地址；收到返回消息后将该IP地址和物理地址存入本机ARP缓存中并保留一定时间，下次请求时直接查询ARP缓存以节约资源。地址解析协议是建立在网络中各个主机互相信任的基础上的，网络上的主机可以自主发送ARP应答消息，其他主机收到应答报文时不会检测该报文的真实性就会将其记入本机ARP缓存；由此攻击者就可以向某一主机发送伪ARP应答报文，使其发送的信息无法到达预期的主机或到达错误的主机，这就构成了一个ARP欺骗。ARP命令可用于查询本机ARP缓存中IP地址和MAC地址的对应关系、添加或删除静态对应关系等。相关协议有RARP、代理ARP。NDP用于在IPv6中代替地址解析协议。

工作过程

主机A的IP地址为192.168.1.1，MAC地址为0A-11-22-33-44-01；

主机B的IP地址为192.168.1.2，MAC地址为0A-11-22-33-44-02；

当主机A要与主机B通信时，地址解析协议可以将主机B的IP地址（192.168.1.2）解析成主机B的MAC地址，以下为工作流程：

第1步：根据主机A上的路由表内容，IP确定用于访问主机B的转发IP地址是192.168.1.2。然后A主机在自己的本地ARP缓存中检查主机B的匹配MAC地址。

第2步：如果主机A在ARP缓存中没有找到映射，它将询问192.168.1.2的硬件地址，从而将ARP请求帧广播到本地网络上的所有主机。源主机A的IP地址和MAC地址都包括在ARP请求中。本地网络上的每台主机都接收到ARP请求并且检查是否与自己的IP地址匹配。如果主机发现请求的IP地址与自己的IP地址不匹配，它将丢弃ARP请求。

第3步：主机B确定ARP请求中的IP地址与自己的IP地址匹配，则将主机A的IP地址和MAC地址映射添加到本地ARP缓存中。

第4步：主机B将包含其MAC地址的ARP回复消息直接发送回主机A。

第5步：当主机A收到从主机B发来的ARP回复消息时，会用主机B的IP和MAC地址映射更新ARP缓存。本机缓存是有生存期的，生存期结束后，将再次重复上面的过程。主机B的MAC地址一旦确定，主机A就能向主机B发送IP通信了。

在OSI模型中ARP协议属于链路层；而在TCP/IP模型中，ARP协议属于网络层。

25. Ping命令是使用以下哪个协议实现的（D）

A、UDP B、ARP C、IGMP D、ICMP E、SMTP

ICMP（Internet ControlMessage Protocol ）网际控制报文协议的一个重要应用就是分组网间探测Ping，用来测试两个主机之间的连通性。Ping使用了ICMP回送请求与回送回答报文，Ping是应用层直接使用网络层ICMP的一个例子，它没有通过运输层的TCP或UDP。

26. 以下哪个协议通常用来收取邮件（C）

A、SMTP B、MAIL C、POP3 D、SNMP（简单网络管理协议 属于应用层） E、ICMP

SMTP（Simple Mail TransferProtocol）简单邮件发送协议

POP3（Post Office Protocol）邮局协议

SMTP和POP3都属于应用层协议

一个电子邮件系统具有三个主要组成构件，就是用户代理、邮件服务器以及邮件发送协议（SMTP）和邮件读取协议（POP3）

不要把SMTP和POP3协议弄混。发件人的用户代理向发送方邮件服务器发送邮件，以及发送方邮件服务器向接收方邮件服务器发送邮件，都是使用SMTP协议。而POP3协议则是用户代理从接受方邮件服务器上读取邮件的时候所使用的协议。

27. CSMA/CD发生在OSI模型中的哪一层（B）

CSMA/CD（Carrier Sense MultipleAccess with Collision Detection）即带冲突检测的载波监听多路访问技术,应用在 OSI 的第二层数据链路层

它的工作原理是: 发送数据前先侦听信道是否空闲 ,若空闲，则立即发送数据。若信道忙碌，则等待一段时间至信道中的信息传输结束后再发送数据；若在上一段信息发送结束后，同时有两个或两个以上的节点都提出发送请求，则判定为冲突。若侦听到冲突,则立即停止发送数据，等待一段随机时间,再重新尝试。

其原理简单总结为：先听后发，边发边听，冲突停发，随机延迟后重发

CSMA/CA工作过程

当发射端希望发送数据时，首先检测介质是否空闲，若是介质为空闲时，送出RTS（Request To Send请求发送），RTS信号包括发射端的地址、接收端的地址、下一笔数据将持续发送的时间等信息，接收端收到RTS信号后，将响应短信号CTS（Clear To Send），CTS信号上也RTS内记录的持续发送的时间，当发射端收到CTS包后，随即开始发送数据包。接收端收到数据包后，将以包内的CRC（CyClic Redundancy Check，循环冗余校验）的数值来检验包数据是否正确，若是检验结果正确时，接收端将响应ACK包，告知发射端数据己经被成功地接收。当发射端没有收到接收端的ACK包时，将认为包在传输过程中丢失，而一直重新发送包.

28. 什么函数不能声明为虚函数（AD）

A、构造函数 B、析构函数 C、成员函数 D、友元函数

因为C++不支持友元函数的继承，对于没有继承特性的函数没有虚函数的说法。

29. C++函数中那些不可以被声明为虚函数的函数

常见的不能声明为虚函数的有：普通函数（非成员函数）；静态成员函数；内联成员函数；构造函数；友元函数。

1、为什么C++不支持普通函数为虚函数？

普通函数（非成员函数）只能被overload，不能被override，声明为虚函数也没有什么意思，因此编译器会在编译时邦定函数。

2、为什么C++不支持构造函数为虚函数？

这个原因很简单，主要是从语义上考虑，所以不支持。因为构造函数本来就是为了明确初始化对象成员才产生的，然而virtual function主要是为了再不完全了解细节的情况下也能正确处理对象。另外，virtual函数是在不同类型的对象产生不同的动作，现在对象还没有产生，如何使用virtual函数来完成你想完成的动作。（这不就是典型的悖论）

3、为什么C++不支持内联成员函数为虚函数？

其实很简单，那内联函数就是为了在代码中直接展开，减少函数调用花费的代价，虚函数是为了在继承后对象能够准确的执行自己的动作，这是不可能统一的。（再说了，inline函数在编译时被展开，虚函数在运行时才能动态的邦定函数）

4、为什么C++不支持静态成员函数为虚函数？

这也很简单，静态成员函数对于每个类来说只有一份代码，所有的对象都共享这一份代码，他也没有要动态绑定的必要性。

5、为什么C++不支持友元函数为虚函数？

因为C++不支持友元函数的继承，对于没有继承特性的函数没有虚函数的说法。

1、顶层函数：顶层函数属于c++库函数，多态的运行期行为体现在虚函数上，虚函数通过继承方式来体现出多态作用，顶层函数不属于成员函数，是不能被继承的。

2、构造函数：

（1）构造函数不能被继承，因而不能声明为virtual函数。

（2）构造函数一般是用来初始化对象，只有在一个对象生成之后，才能发挥多态的作用，如果将构造函数声明为virtual函数，则表现为在对象还没有生成的情况下就使用了多态机制，因而是行不通的，如下例：

\#include <iostream>

using namespace std;

class B

public:

B() \{\}

virtual void show()

cout<<"\*\*\*"<<endl;

\};

class D:public B

public:

D() \{\}

void show()

cout<<"==="<<endl;

\};

int main(void)

B\*pb;

Dd; //先生成对象

pb=&d;

pb->show(); //再体现多态

pb=new D(); //先调用构造函数

pb->show(); //再多态

delete pb;

return 0;

3、static函数：不能被继承，只属于该类。

我的理解是：效果是能继承，机理是不继承。静态成员函数就一份实体，在父类里；子类继承父类时也无需拷贝父类的静态函数，但子类可以使用父类的静态成员函数——所以我得出“效果是能继承，机理是不继承”的结果——个人理解，仅供参考。

4、友元函数：友元函数不属于类的成员函数，不能被继承。

5、inline函数：inline函数和virtual函数有着本质的区别，inline函数是在程序被编译时就展开，在函数调用处用整个函数体去替换，而virtual函数是在运行期才能够确定如何去调用的，因而inline函数体现的是一种编译期机制，virtual函数体现的是一种运行期机制。此外，一切virtual函数都不可能是inline函数。

30. 数据存储在磁盘上的排列方式会影响I/O服务的性能，一个圆环的磁道上有10个物理块，10个数据记录R1------R10存放在这个磁道上。假设磁盘的旋转速度为20ms/周，磁盘当前处在R1的开头处，若系统顺序扫描后将数据放入单缓冲区内，处理数据的时间为4ms（然后再读取下个记录），则处理这10个记录的最长时间为（C）

A、180ms B、200ms C、204ms D、220ms

(2+4)\*10+(2\*8)\*9 = 204每个记录单次的读取时间为2ms(20/10);4ms是处理时间,一共要处理10次.8是读取一个记录后,磁头要再经过多少个物理块才能达到下一个要读的记录位置.

如：第1个记录读取后(R1),并处理完记录后,这时磁头会达到R4处.需经过R4,R5,R6,R7,R8,R9,R10,R1,才能再次读取R2.由于开始的时间是在R1处,所以处理10个记录要旋转9次.16):(2+4)\*10= 60ms如果当R1处理完(2+4),磁头所在的位置如果是R2,那就是最优的.依次下来的记录都是最优.顺序为：R1,R8,R5,R2,R9,R6,R3,R10,R7,R4

31. 随着IP网络的发展，为了节省可分配的注册IP地址，有一些地址被拿出来用于私有IP地址，以下不属于私有IP地址范围的是（C）

在现在的网络中，IP地址分为公网IP和私有IP地址。公网IP是在Internet使用的IP地址，而私有IP地址是在局域网中使用的IP地址。由于我们目前使用的IP V4协议的限制，现在IP地址的数量是有限的。这样，我们就不能为居于网中的每一台计算机分配一个公网IP。所以，在局域网中的每台计算机就只能使用私有IP地址了，如我们常见的192.168.0.\*，就是私有IP地址。私有IP地址是一段保留的IP地址。只是使用在局域网中，在Internet上是不使用的。私有IP地址的范围有：

10.0.0.0-10.255.255.255/8 子网掩码：255.0.0.0

172.16.0.0—172.31.255.255/12 子网掩码：255.240.0.0

192.168.0.0-192.168.255.255/16 子网掩码：255.255.0.0

上述的IP地址都是可以使用在局域网中的。

32. 表达式“X=A+B\*（C--D）/E”的后缀表示形式可以为（C）

A、XAB+CDE/-\*= B、XA+BC-DE/\*=

C、XABCD-\*E/+= D、XABCDE+\*/=

后缀表达式即为二叉树的后续遍历。非叶节点存放运算符，叶节点存放操作数。

33. （B）设计模式将抽象部分与它的实现部分相分离。

A、Singleton（单例） B、 Bridge（桥接）

C、Composite（组合）D、 Facade（外观）

桥接模式（Bridge），桥梁模式的用意是"将抽象化(Abstraction)与实现化(Implementation)脱耦，使得二者可以独立地变化"。这句话有三个关键词，也就是抽象化、实现化和脱耦。

抽象化存在于多个实体中的共同的概念性联系，就是抽象化。作为一个过程，抽象化就是忽略一些信息，从而把不同的实体当做同样的实体对待。

实现化抽象化给出的具体实现，就是实现化。

脱耦所谓耦合，就是两个实体的行为的某种强关联。而将它们的强关联去掉，就是耦合的解脱，或称脱耦。在这里，脱耦是指将抽象化和实现化之间的耦合解脱开，或者说是将它们之间的强关联改换成弱关联。将两个角色之间的继承关系改为聚合关系，就是将它们之间的强关联改换成为弱关联。因此，桥梁模式中的所谓脱耦，就是指在一个软件系统的抽象化和实现化之间使用组合/聚合关系而不是继承关系，从而使两者可以相对独立地变化。这就是桥梁模式的用意。

由抽象化角色和修正抽象化角色组成的抽象化等级结构。

由实现化角色和两个具体实现化角色所组成的实现化等级结构。

桥梁模式所涉及的角色有：

抽象化(Abstraction)角色：抽象化给出的定义，并保存一个对实现化对象的引用。

修正抽象化(Refined Abstraction)角色：扩展抽象化角色，改变和修正父类对抽象化的定义。

实现化(Implementor)角色：这个角色给出实现化角色的接口，但不给出具体的实现。必须指出的是，这个接口不一定和抽象化角色的接口定义相同，实际上，这两个接口可以非常不一样。实现化角色应当只给出底层操作，而抽象化角色应当只给出基于底层操作的更高一层的操作。

具体实现化(Concrete Implementor)角色：这个角色给出实现化角色接口的具体实现。

例子：

\#include<iostream>

using namespace std;

class HandSet\{

public:

virtualvoid run() = 0;

\};

class HandSetRecord :public HandSet\{

public:

voidrun()\{

cout<< "通讯录..." << endl;

\};

class HandSetGame :public HandSet\{

public:

voidrun()\{

cout<< "游戏..." << endl;

\};

class HandSetBrand\{

public:

voidSetHandSet(HandSet &handseter)

handset= &handseter;

virtualvoid run()\{

handset->run();

protected:

HandSet\*handset;

\};

class HandSetBrandA :public HandSetBrand\{

voidrun()\{

handset->run();

cout<< "A品牌" << endl;

\};

class HandSetBrandB :public HandSetBrand\{

voidrun()\{

handset->run();

cout<< "B品牌" << endl;

\};

int main()\{

HandSetBrand\*handsetbrand=new HandSetBrandA;

handsetbrand->SetHandSet(\*(newHandSetRecord));

handsetbrand->run();

handsetbrand= new HandSetBrandB;

handsetbrand->SetHandSet(\*(newHandSetGame));

handsetbrand->run();

handsetbrand= new HandSetBrand;

handsetbrand->SetHandSet(\*(newHandSetGame));

handsetbrand->run();

34. C++将父类的析构函数定义为虚函数，下列正确的是哪个？(A)

A、释放父类指针时能正确释放子类对象

B、释放子类指针时能正确释放父类对象

C、这样做是错误的

D、以上全错

C++的多态肯定是使用父类的指针指向子类的对象，所以肯定是释放子类的对象，如果不使用虚函数的话，父类的指针就只能够释放父类的对象。

35. typedef char \*String\_t; 和 \#defineString\_d char \* 这两句在使用上有什么区别？

答：typedef char \*String\_t 定义了一个新的类型别名，有类型检查。而\#defineString\_d char \* 只是做了个简单的替换，无类型检查，前者在编译的时候处理，后者在预编译的时候处理。

同时定义多个变量的时候有区别，主要区别在于这种使用方式String\_t a,b; String\_d c,d; a,b ,c都是char\*类型，而d为char类型.由于typedef还要做类型检查。。\#define没有。。所以typedef比\#define安全。。

36. 到商店里买200的商品返还100优惠券（可以在本商店代替现金）。请问实际上折扣是多少？

答：由于优惠券可以代替现金，所以可以使用200元优惠券买东西，然后还可以获得100元的优惠券。

假设开始时花了x元，那么可以买到 x + x/2 + x/4 + ...的东西。所以实际上折扣是50%.（当然，大部分时候很难一直兑换下去，所以50%是折扣的上限）

如果使用优惠券买东西不能获得新的优惠券，那么

总过花去了200元，可以买到200+100元的商品，所以实际折扣为 200/300 = 67.7%.

37. 题目：已知rand7() 可以产生 1~7 的7个数（均匀概率），利用rand7() 产生rand10() 1~10（均匀概率）

rand7 产生的数概率是一样的,即1~7出现概率一样，由于我们对结果做了一定的筛选只能通过 1~5，而1~5出现的概率也是一样的，又由于范围为1~5 所以 temp1 出现 1~5的概率为1/5 ,同理后面的 出现 temp2 的概率为 1/2.首先temp1出现在1~5的概率为1/5，而temp2出现 1~2 的概率为1/2，也就是说5\*(temp2-1) 出现5或0的概率为1/2,所以假如你要得到1~5的数的话那么 5\*（temp2-1）必须0，所以因为你要保证 5\*（temp2-1）=0，这个概率只有1/2,再加上你前面指定1~5 的概率为1/5 ,所以结果为 1/5\*1/2=1/10

int rand10()

int temp1;

int temp2;

temp1 = rand7();

\}while(temp1>5);

temp2 = rand7();

\}while(temp2>2);

returntemp1+5\*(temp2-1);

int rand10()

int i;

do \{

i = 7 \* (rand7() - 1) + rand5();

\} while(i > 51);

return i % 10 + 1;

38. 对一个正整数作如下操作：如果是偶数则除以2，如果是奇数则加1，如此进行直到1时操作停止，求经过9次操作变为1的数有多少个？55

第9次操作：结果1由2产生。1个被操作数

8：结果2只能由4产生。1个被操作数

7：结果4由8、3产生。2个

6：结果8由16、7产生；结果3由6产生。共3个

5：结果16由32、15产生；结果7由14产生；结果6由12、5产生。共5个…

每次操作，偶数（2除外）都由该数减1和该数的2倍得来，奇数只由该数的2倍得来

各次操作的操作对象个数为：1，1，2，3，5，8，13，21，34，…

本题可以通过所给的变换规律，由易到难，确定操作可变为1的数组成斐波拉契数列，再根据所发现的规律求出经过9次操作变为1的数的个数。

39. OFFSETOF(s, m)的宏定义，s是结构类型，m是s的成员，求m在s中的偏移量。

\#define OFFSETOF(s,m) ((int)&(((s\*)0)->m))

用地址零作为起始地址，强制转换成结构体类型，然后取出成员的地址，转换成int类型，就可以得到偏移量了。

40. 给定一个字符串，求出其最长的重复子串。

思路：使用后缀数组，对一个字符串生成相应的后缀数组后，然后再排序，排完序依次检测相邻的两个字符串的开头公共部分。

这样的时间复杂度为：

生成后缀数组 O(N)

排序 O(NlogN\*N) 最后面的 N 是因为字符串比较也是 O(N)

依次检测相邻的两个字符串 O(N \* N)

总的时间复杂度是 O(N^2\*logN),

解答：

对于类似从给定的文本中，查找其中最长的重复子字符串的问题，可以采用“后缀数组”来高效地完成此任务。后缀数组使用文本本身和n个附加指针（与文本数组相应的指针数组）来表示输入文本中的n个字符的每个子字符串。

首先,如果输入字符串存储在c\[0..n-1\]中，那么就可以使用类似于下面的代码比较每对子字符串：

maxlen = -1

for i = \[0, n)

for j = (i, n)

if (thislen = comlen(&c\[i\], &c\[j\])) > maxlen

maxlen = thislen

maxi = i

maxj = j

当作为comlen函数参数的两个字符串长度相等时，该函数便返回这个长度值，从第一个字符开始：

int comlen(char \*p, char\* q)

i = 0

while \*p && (\*p++ = \*q++)

i++

return i

由于该算法查看所有的字符串对，所以它的时间和n的平方成正比。下面便是使用“后缀数组”的解决办法。

如果程序至多可以处理MAXN个字符，这些字符被存储在数组c中：

\#define MAXN 5000000

char c\[MAXN\], \*a\[MAXN\];

在读取输入时，首先初始化a,这样，每个元素就都指向输入字符串中的相应字符：

while (ch = getchar()) != EOF

a\[n\] = &c\[n\];

c\[n++\] = ch;

c\[n\] = 0 //将数组c中的最后一个元素设为空字符，以终止所有字符串。

这样，元素a\[0\]指向整个字符串，下一个元素指向以第二个字符开始的数组的后缀，等等。如若输入字符串为"banana",该数组将表示这些后缀：

a\[0\]:banana

a\[1\]:anana

a\[2\]:nana

a\[3\]:ana

a\[4\]:na

a\[5\]:a

由于数组a中的指针分别指向字符串中的每个后缀，所以将数组a命名为"后缀数组"

第二，对后缀数组进行快速排序，以将后缀相近的（变位词）子串集中在一起

qsort(a, n, sizeof(char\*), pstrcmp)后

a\[0\]:a

a\[1\]:ana

a\[2\]:anana

a\[3\]:banana

a\[4\]:na

a\[5\]:nana

第三，使用以下comlen函数对数组进行扫描比较邻接元素，以找出最长重复的字符串：

fori = \[0, n)

if comlen(a\[i\], a\[i+1\]) > maxlen

maxlen = comlen(a\[i\], a\[i+1\])

maxi = i

printf("%.\*s/n", maxlen, a\[maxi\])

由于少了内层循环，只是多了一次排序，因此该算法的运行时间为O(nlogn).

\#include <stdio.h>

\#include <stdlib.h>

\#include <string.h>

\#define MAXCHAR 5000 //最长处理5000个字符

char c\[MAXCHAR\], \*a\[MAXCHAR\];

int comlen( char \*p, char \*q )\{

int i = 0;

while(\*p && (\*p++ == \*q++) )

\++i;

return i;

int pstrcmp( const void \*p1, const void \*p2)\{

return strcmp( \*(char\* const \*)p1, \*(char\* const\*)p2 );

int main()\{

char ch;

int n=0;

int i, temp;

int maxlen=0, maxi=0;

printf("Please input yourstring:\\n");

while( (ch=getchar())!='\\n' )\{

a\[n\]=&c\[n\];

c\[n++\]=ch;

c\[n\]='\\0';

qsort( a, n, sizeof(char\*), pstrcmp );

for(i=0; i<n-1; ++i )\{

temp=comlen( a\[i\], a\[i+1\] );

if( temp>maxlen )\{

maxlen=temp;

maxi=i;

printf("%.\*s\\n",maxlen, a\[maxi\]);

system("PAUSE");

return 0;

41. 对于一个内存地址是32位、内存页是8KB的系统。0X0005F123这个地址的页号与页内偏移分别是多少。

页面大小是8KB，那么页内偏移量是从0x0000（0）~ 0x1FFF（2的13次方 - 1）。0x5F123/8K=2E，余数是1123；则页号是47页，页内偏移量应该是0X00001123。

42. 如果X大于0并小于65536，用移位法计算X乘以255的值为： (X<<8)-X

X<<8-X是不对的，因为移位运算符的优先级没有减号的优先级高，首先计算8-X为0，X左移0位还是8。

43. 以下两个语句的区别是：第一个动态申请的空间里面的值是随机值，第二个进行了初始化，里面的值为0

int \*p1 = new int\[10\];

int \*p2 = new int\[10\]();

44. 计算机在内存中存储数据时使用了大、小端模式，请分别写出A=0X123456在不同情况下的首字节是，大端模式：0X12 小端模式：0X56 X86结构的计算机使用 小端 模式。

一般来说，大部分用户的操作系统（如windows, FreeBsd,Linux）是小端模式的。少部分，如MAC OS，是大端模式的。

45. 头文件中ifndef / define / endif 是做什么用的

想必很多人都看过“头文件中的 \#ifndef/\#define/\#endif 防止该头文件被重复引用”。但是是否能理解“被重复引用”是什么意思？是不能在不同的两个文件中使用include来包含这个头文件吗？如果头文件被重复引用了，会产生什么后果？是不是所有的头文件中都要加入\#ifndef/\#define/\#endif 这些代码？

其实“被重复引用”是指一个头文件在同一个cpp文件中被include了多次，这种错误常常是由于include嵌套造成的。比如：存在a.h文件\#include "c.h"而此时b.cpp文件导入了\#include"a.h" 和\#include "c.h"此时就会造成c.h重复引用。

头文件被重复引用引起的后果：

有些头文件重复引用只是增加了编译工作的工作量，不会引起太大的问题，仅仅是编译效率低一些，但是对于大工程而言编译效率低下那将是一件多么痛苦的事情。

有些头文件重复包含，会引起错误，比如在头文件中定义了全局变量(虽然这种方式不被推荐，但确实是C规范允许的)这种会引起重复定义。

是不是所有的头文件中都要加入\#ifndef/\#define/\#endif 这些代码？

答案：不是一定要加，但是不管怎样，用ifnde xxx \#define xxx\#endif或者其他方式避免头文件重复包含，只有好处没有坏处。个人觉得培养一个好的编程习惯是学习编程的一个重要分支。

下面给一个\#ifndef/\#define/\#endif的格式：

\#ifndef A\_H意思是"if not define a.h" 如果不存在a.h

接着的语句应该\#defineA\_H 就引入a.h

最后一句应该写\#endif 否则不需要引入

46. 代码里有时可以看到extern “C”，这语句是做什么用的

时常在cpp的代码之中看到这样的代码:

\#ifdef \_\_cplusplus

extern "C" \{

\#endif

//一段代码

\#ifdef \_\_cplusplus

\#endif

这样的代码到底是什么意思呢？首先，\_\_cplusplus是cpp中的自定义宏，那么定义了这个宏的话表示这是一段cpp的代码，也就是说，上面的代码的含义是:如果这是一段cpp的代码，那么加入extern "C"\{和\}处理其中的代码。

要明白为何使用extern "C"，还得从cpp中对函数的重载处理开始说起。在c++中，为了支持重载机制，在编译生成的汇编码中，要对函数的名字进行一些处理，加入比如函数的返回类型等等.而在C中，只是简单的函数名字而已，不会加入其他的信息.也就是说:C++和C对产生的函数名字的处理是不一样的.

比如下面的一段简单的函数，我们看看加入和不加入extern "C"产生的汇编代码都有哪些变化:

int f(void)

return 1;

在加入extern "C"的时候产生的汇编代码是:

.file "test.cxx"

.text

.align 2

.globl \_f

.def \_f; .scl 2; .type 32; .endef

\_f:

pushl %ebp

movl %esp， %ebp

movl $1， %eax

popl %ebp

ret

但是不加入了extern "C"之后

.file "test.cxx"

.text

.align 2

.globl \_\_Z1fv

.def \_\_Z1fv; .scl 2; .type 32; .endef

\_\_Z1fv:

pushl %ebp

movl %esp， %ebp

movl $1， %eax

popl %ebp

ret

两段汇编代码同样都是使用gcc -S命令产生的，所有的地方都是一样的，唯独是产生的函数名，一个是\_f，一个是\_\_Z1fv。

明白了加入与不加入extern "C"之后对函数名称产生的影响，我们继续我们的讨论:为什么需要使用extern "C"呢？C++之父在设计C++之时，考虑到当时已经存在了大量的C代码，为了支持原来的C代码和已经写好C库，需要在C++中尽可能的支持C，而extern "C"就是其中的一个策略。

试想这样的情况:一个库文件已经用C写好了而且运行得很良好，这个时候我们需要使用这个库文件，但是我们需要使用C++来写这个新的代码。如果这个代码使用的是C++的方式链接这个C库文件的话，那么就会出现链接错误.我们来看一段代码:首先，我们使用C的处理方式来写一个函数，也就是说假设这个函数当时是用C写成的:

//f1.c

extern "C"

void f1()

return;

编译命令是:gcc -c f1.c -o f1.o 产生了一个叫f1.o的库文件。再写一段代码调用这个f1函数:

// test.cxx

//这个extern表示f1函数在别的地方定义，这样可以通过编译，但是链接的时候还是需要

//链接上原来的库文件.

extern void f1();

int main()

f1();

return 0;

通过gcc -c test.cxx -o test.o 产生一个叫test.o的文件。然后，我们使用gcctest.o f1.o来链接两个文件，可是出错了，错误的提示是:

test.o(.text + 0x1f):test.cxx: undefinereference to 'f1()'

也就是说，在编译test.cxx的时候编译器是使用C++的方式来处理f1()函数的，但是实际上链接的库文件却是用C的方式来处理函数的，所以就会出现链接过不去的错误:因为链接器找不到函数。

因此，为了在C++代码中调用用C写成的库文件，就需要用extern "C"来告诉编译器:这是一个用C写成的库文件，请用C的方式来链接它们。

比如，现在我们有了一个C库文件，它的头文件是f.h，产生的lib文件是f.lib，那么我们如果要在C++中使用这个库文件，我们需要这样写:

extern "C"

\#include "f.h"

回到上面的问题，如果要改正链接错误，我们需要这样子改写test.cxx:

extern "C"

extern void f1();

int main()

f1();

return 0;

重新编译并且链接就可以过去了.

总结

C和C++对函数的处理方式是不同的.extern"C"是使C++能够调用C写作的库文件的一个手段，如果要对编译器提示使用C的方式来处理函数的话，那么就要使用extern "C"来说明。

47. 平均要取多少个(0,1)中的随机数才能让和超过1

先用程序估算一下

from \_\_future\_\_ import division

import random

N = 1000000

sums = 0

for i in range(N):

count = 0

s= 0

while 1:

s += random.random()

count += 1

if s > 1:

sums += count

break

print sums / N

三次给出的结果分别是

2.716957 2.718334 2.71885

2.718不就是e的味道吗，下面证明一下

先取两个特例

特例1：x+y < 1——两个随机数之和小于1

结果是紫色部分，为1/2

特例2：x+y+z< 1——三个随机数之和小于1

结果为深底下面的，占整个体积的1/6(锥体积：1/3\*底面积\*好=1/3 \* 1/2 \* 1 \*1)

这个 1/6 可以利用截面与底面的相似比关系，通过简单的积分求得：

∫(0..1)(x^2)\*1/2 dx = 1/6

推广：四个 0 到 1 之间的随机数之和小于 1 的概率就等于四维立方体一角的“体积”，它的“底面”是一个体积为 1/6 的三维体，在第四维上对其进行积分便可得到其“体积”

∫(0..1)(x^3)\*1/6 dx = 1/24

依此类推， n 个随机数之和不超过 1 的概率就是 1/n! ，反过来 n 个数之和大于 1 的概率就是 1 – 1/n! ，因此加到第 n 个数才刚好超过 1 的概率就是

(1 –1/n!) – (1 – 1/(n-1)!) = (n-1)/n!

因此，要想让和超过 1 ，需要累加的期望次数为

∑(n=2..∞) n \* (n-1)/n! = ∑(n=1..∞) n/n! = e

48. 设rand（s，t）返回\[s,t\]之间的随机小数，利用该函数在一个半径为R的圆内找随机n个点，并给出时间复杂度分析

在半径为R的圆内找随机的n个点，既然是找点，那么就需要为其建立坐标系，如果建立平面直角坐标系，以圆心为原点，建立半径为R的圆的直角坐标系。要使随机的点在圆内，则必须使其所找的点 point 的x，y坐标的绝对值小于R，问题转化为：随机的找n个圆内的点，使其x，y坐标的绝对值均小于R。这里以x为例，首先 x 应满足 -R<= x <= R； y同理。这样产生的点均在以圆心为中心，边长为2R的正放形内，需要另外判断其距离R的值。本文介绍采用极坐标的形式，建立圆的极坐标系，则圆内的任意一点满足 P(ρ,θ)（用ρ表示线段OP的长度，θ表示从Ox到OP的角度angle），此时问题转化为：找一点，使其到圆心的距离OP大于等于0 小于R，极角大于等于0 小于360，则OP=rand(0, R) ，当 OP== R 时重新寻找，angle = rand(0,360) ，当angle==360时，重新寻找。每找到一个点p，将其与之前所找到的所有点进行比较，若重合，则继续寻找，否则将其加入到已找到的点集合中，直到找到n个点。

存放点的数据结构

typedef struct Point\{

double r;

double angle;

\}Point;

算法流程：

for( i=n ; i >0; i--)

产生 p.r =rand(0,R)，且p.r != R

产生 p.rangle =rand(0,360) ,且 p.rangle != 360

遍历所有产生的点，若 p 已经存在，则重新生成该点

否则将其加入到产生的点集合中

生成第n个点，需要先遍历前n-1个点，时间复杂度为O(n)，故生成n个点的时间复杂度为O(n^2)

49. 为分析用户行为，系统常需存储用户的一些query，但因query非常多，故系统不能全存，设系统每天只存m个query，现设计一个算法，对用户请求的query进行随机选择m个，请给一个方案，使得每个query被抽中的概率相等，并分析之，注意：不到最后一刻，并不知用户的总请求量。

如果记录小于m，则把它们都放入系统中，此时他们是等概率的，概率值都为1，从第m+1个开始，以概率m/(m+1)的概率取第m+1个数，然后把它与m个数中的一个进行随机交换，显然第m+1个数的概率为m/(m+1).

如果取到了第m+1个数，则m个数中必须出去一个，留下的概率为(m-1)/m，此时概率为取到的概率\*留下来的概率=m/(m+1)\*(m-1)/m=(m-1)/(m+1).

如果没有取到，则m个数全留下，此时概率为(1-m/(m+1))=1/(m+1).

所以两者之和为m/(m+1).即取到每一个数的概率为m/(m+1).分子为系统的容量，分母为取得第n个数。

50. C++ STL中vector的相关问题：

（1）、调用push\_back时，其内部的内存分配是如何进行的？

（2）、调用clear时，内部是如何具体实现的？若想将其内存释放，该如何操作？

vector的工作原理是系统预先分配一块CAPACITY大小的空间，当插入的数据超过这个空间的时候，这块空间会让某种方式扩展，但是你删除数据的时候，它却不会缩小。vector为了防止大量分配连续内存的开销，保持一块默认的尺寸的内存，clear只是清数据了，未清内存，因为vector的capacity容量未变化，系统维护一个的默认值。

有什么方法可以释放掉vector中占用的全部内存呢?

标准的解决方法如下

template < class T >

void ClearVector( vector< T >& vt)

vector< T > vtTemp;

veTemp.swap( vt );

事实上，vector根本就不管内存，它只是负责向内存管理框架acquire/release内存，内存管理框架如果发现内存不够了，就malloc，但是当vector释放资源的时候(比如destruct), stl根本就不调用free以减少内存，因为内存分配在stl的底层：stl假定如果你需要更多的资源就代表你以后也可能需要这么多资源(你的list, hashmap也是用这些内存)，所以就没必要不停地malloc/free。如果是这个逻辑的话这可能是个trade-off

一般的STL内存管理器allocator都是用内存池来管理内存的，所以某个容器申请内存或释放内存都只是影响到内存池的剩余内存量，而不是真的把内存归还给系统。这样做一是为了避免内存碎片，二是提高了内存申请和释放的效率——不用每次都在系统内存里寻找一番。

51. 求一个全排列函数

\#include<iostream>

using namespace std;

void swap(char &a, char &b)

chartemp = a;

a= b;

b= temp;

void permutation(char \*a, int k, int m)

if(k == m)

cout<< a << endl;

return;

for(int i = k; i< m; i++)

swap(a\[k\],a\[i\]);

permutation(a,k + 1, m);

swap(a\[k\],a\[i\]);

int main()\{

charstr\[\] = "12345";

permutation(str,0, 5);

getchar();

52. 进程切换需要注意哪些问题？

保存现有进程的当前的状态。具体如下：

保存处理器PC寄存器的值到被中止进程的私有堆栈；

保存处理器PSW寄存器的值到被中止进程的私有堆栈；

保存处理器SP寄存器的值到被中止进程的进程控制块；

保存处理器其他寄存器的值到被中止进程的私有堆栈；

自待运行进程的进程控制块取SP值并存入处理器的寄存器SP；

自待运行进程的私有堆栈恢复处理器各寄存器的值；

自待运行进程的私有堆栈中弹出PSW值并送入处理器的PSW；

自待运行进程的私有堆栈中弹出PC值并送入处理器的PC。

53. 编程实现两个正整数的除法，当然不能用除法操作符

\#include<iostream>

using namespace std;

int div1(int x, int y)

intresult = 0;

while(x >= y)

intmulti = 1;

while(y\*multi <= (x >> 1))

multi=multi<< 1;

result+= multi;

x= x - y\*multi;

returnresult;

int main(void)

cout<< div1(100, 5) << endl;

return0;

54. 现在有一个数组，已知一个数出现的次数超过了一半，请用O(n)的复杂度的算法找出这个数。

\#include<iostream>

using namespace std;

int div1(int \*a,int num)

intx=a\[0\], y=1;

for(int i = 1; i < num; i++)

if(y == 0)

x= a\[i\];

y= 1;

continue;

if(a\[i\] == x)

y++;

elseif (a\[i\] != x)

y--;

returnx;

int main(void)

inta\[\] = \{ 1, 2, 3, 4, 2, 2, 1, 2, 2, 2 \};

cout<< div1(a, 10) << endl;

return0;

55. 求取字符串长度，不使用while、for等循环语句和字符串处理函数。

\#include<iostream>

using namespace std;

int strlen1(char \*str)

if(\*str == '\\0')

return0;

else

return1 + strlen1(str + 1);

int main(void)

char\*a = "abcdefg";

cout<< strlen1(a) << endl;

return0;

56. Printf()返回值为返回的字符个数。

int main(void)

inti=43;

printf("%d",printf("%d",printf("%d",i))); //这个是嵌套的，应该先运行最里面的那个printf，输出43，然后printf返回2，在输出2后printf返回值为1，最后输出1

return0;

57. 现在有1千万个随机数，随机数的范围在1到1亿之间。现在要求写出一种算法，将1到1亿之间没有在随机数中的数求出来。

解决办法：

一）用一个32位的整数32位表示32个数，1亿/32 =3125000，使用3.125 \* 4M byte空间即可保存1亿个数，即index\[3125000\].

二）对于数n，(n-1) / 32 为其在数组中的下标，table\[(n- 1) % 32\]与数组中下标(n-1)/32的值使用或操作。

三）表table中值为 table\[ 0 \]=0x00000001,

table\[ 1\]=0x00000002,

... ...

table\[29\]=0x20000000,

table\[31\]=0x80000000, 等这样的表示方式，具体的数值使用查表法加快速度。

四）最后算某值是否存在，使用与操作即可计算出。

数据存储比如：

第一个N=30是一个随机数，则存储可以表示为：index\[(30-1)/32\] = index\[0\] = index\[0\] || table\[(30-1)%32\] = 0 || 0x20000000 = 0x20000000；

第二个N=31是一个随机数，则存储可以表示为：index\[(31-1)/32\] = index\[0\] = index\[0\] || table\[(31-1)%32\] = 0x20000000 || 0x40000000 = 0x60000000；

... ...

依次类推，即可。

数据验证比如：

1. 当要查询30是否存在的时候，由于：(30-1)/32= 0；(30-1)%32=29；我们只需要计算：index\[0\] & table\[29\] 是真还是假，就可以得出30是否存在。

2. 当要查询31是否存在的时候，由于：(31-1)/32= 0；(31-1)%32=30；我们只需要计算：index\[0\] & table\[30\] 是真还是假，就可以得出31是否存在。

... ...

依次类推，即可。

小结：

通过分析此题目，首先这种思路和方法，在一定程度上用相对小的空间存储了大量的数据，节省了比较大的内存空间；在运算方面，位运算的速度相当来说效率是比较高的，因而也再一定程度上节省了时间复杂。

总之，这种存储方式和思维方式，在一定方面能够有效的解决海量数据存储与运算。基于此题目，凡是大量数据筛选，判断是否存在等问题，我们都可以借鉴此题目的思维和方法。

58. 判断点是否在多边形内的问题？

我知道有两种方法：

1、累计角度法

过此点连接多边形的每一顶点，各相邻边角度之和为360度，则此点在多边形内。 否则为0度，在多边形外部。

2、射线法

过此点向任意角度发一条射线，若与多边形的各条边交点个数之和为偶数，则此点在多边形之外，否则在多边形之内。 若有交点为多边形顶点则要另选一条射线重算。

请问哪种方法好一点（时间复杂度）？

方法一对凹多边形可能会出现问题吧。

59. 8\*8的棋盘上面放着64个不同价值的礼物，每个小的棋盘上面放置一个礼物（礼物的价值大于0），一个人初始位置在棋盘的左上角，每次他只能向下或向右移动一步，并拿走对应棋盘上的礼物，结束位置在棋盘的右下角，请设计一个算法使其能够获得最大价值的礼物。

//经典的动态规划

//dp\[i\]\[j\] 表示到棋盘位置（i，j）上可以得到的最大礼物值

//dp\[i\]\[j\] = max( dp\[i\]\[j-1\] , dp\[i-1\]\[j\] )+ value\[i\]\[j\] （0<i，j<n）

int i, j, n = 8;

dp\[0\]\[0\] = value\[0\]\[0\];

for( i = 1 ; i < n ; i++ )

dp\[i\]\[0\]= dp\[i-1\]\[0\] + value\[i\]\[0\];

for( j = 1 ; j < n ; j++ )

dp\[0\]\[j\]= dp\[0\]\[j-1\] + value\[0\]\[j\];

for( i = 1 ; i < n ; i++ )

for(j = 1 ; j < n ; j++ )

dp\[i\]\[j\]= max( dp\[i\]\[j-1\] , dp\[i-1\]\[j\] ) + value\[i\]\[j\];

cout<<dp\[n-1\]\[n-1\]<<endl;

60. 有N＋2个数，N个数出现了偶数次，2个数出现了奇数次（这两个数不相等），问用O（1）的空间复杂度，找出这两个数，不需要知道具体位置，只需要知道这两个值。

求解：如果只有一个数出现过奇数次，这个就比较好求解了，直接将数组中的元素进行异或，异或的结果就是只出现过奇数次的那个数。

但是题目中有2个数出现了奇数次？，求解方法如下：

假设这两个数为a，b，将数组中所有元素异或结果x=a^b，判断x中位为1的位数（注：因为a！=b，所以x！=0，我们只需知道某一个位为1的位数k，例如0010 1100，我们可取k=2或者3，或者5），然后将x与数组中第k位为1的数进行异或，异或结果就是a，b中一个，然后用x异或，就可以求出另外一个。

为什么呢？因为x中第k位为1表示a或b中有一个数的第k位也为1，假设为a，我们将x与数组中第k位为1的数进行异或时，也就是将x与a外加上其他第k位为1的出现过偶数次的数进行异或，化简即为x与a异或，结果是b。

代码如下：

void getNum(int a\[\],int length)

int s = 0;//保存异或结果

for(int i=0;i<length;i++)

s=s^a\[i\];

int temp1 = s; //临时保存异或结果

int temp2 = s; //临时保存异或结果

int k=0;

while((temp1&1) == 0) //求异或结果中位为1的位数

temp1 = temp1>>1;

k++;

for(int i=0;i<length;i++)

if((a\[i\]>>k)&1) //将s与数组中第k位为1的数进行异或，求得其中一个数

//cout<<a\[i\]<<" ";

s=s^a\[i\];

cout<<s<<" "<<(s^temp2)<<endl; //(s^temp2)用来求另外一个数

61. do while(0)在宏定义中的应用。

看linux源码时,经常发现有宏定义用

\#define XYZ \\

do\{...\} while(0)

这是一个奇怪的循环，它根本就只会运行一次，为什么不去掉外面的do\{..\}while结构呢？原来这也是非常巧妙的技巧。在工程中可能经常会引起麻烦，而上面的定义能够保证这些麻烦不会出现。下面是解释：

假设有这样一个宏定义

\#define macro(condition) \\

if(condition) dosomething()

现在在程序中这样使用这个宏：

if(temp)

macro(i);

else

doanotherthing();

一切看起来很正常，但是仔细想想。这个宏会展开成：

if(temp)

if(i) dosomething();

else

doanotherthing();

这时的else不是与第一个if语句匹配，而是错误的与第二个if语句进行了匹配，编译通过了，但是运行的结果一定是错误的。

为了避免这个错误，我们使用do\{….\}while(0) 把它包裹起来，成为一个独立的语法单元，从而不会与上下文发生混淆。同时因为绝大多数的编译器都能够识别do\{…\}while(0) 这种无用的循环并进行优化，所以使用这种方法也不会导致程序的性能降低。

此外，这是为了含多条语句的宏的通用性。因为默认规则是宏定义最后是不能加分号的，分号是在引用的时候加上的。

在MFC的afx.h文件里面，你会发现很多宏定义都是用了do...while(0)或do...while(false)。

为了看起来更清晰，这里用一个简单点的宏来演示：

\#define SAFE\_DELETE(p) do\{ delete p; p =NULL \} while(0)

假设这里去掉do...while(0),

\#define SAFE\_DELETE(p) delete p; p = NULL;

那么以下代码：

if(NULL != p) SAFE\_DELETE(p)

else ...do sth...

就有两个问题，

1) 因为if分支后有两个语句，else分支没有对应的if，编译失败。

2) 假设没有else, SAFE\_DELETE中的第二个语句无论if测试是否通过，会永远执行。

你可能发现，为了避免这两个问题，我不一定要用这个令人费解的do...while, 我直接用\{\}括起来就可以了

\#define SAFE\_DELETE(p) \{ delete p; p = NULL;\}

的确，这样的话上面的问题是不存在了，但是我想对于C++程序员来讲，在每个语句后面加分号是一种约定俗成的习惯，这样的话，以下代码:

if(NULL != p) SAFE\_DELETE(p);

else ...do sth...

由于if后面的大括号后面加了一个分号，导致其else分支就无法通过编译了（原因同上），所以采用do...while(0)是做好的选择了。

如果使用名家的方法

\#define SAFE\_FREE(p) do \{free(p);p=NULL;\} while(0)

那么

if(NULL!=p)

SAFE\_FREE(p);

else

do something

展开为

if(NULL!=p)

\{ free(p);p=NULL;\}

while(0);

else

do something

好了这样就一切太平了。

62. 给定如下的n\*n的数字矩阵，每行从左到右是严格递增，每列的数据也是严格递增.

1 3 7 15 16

2 5 8 18 19

4 6 9 22 23

10 13 17 24 28

20 21 25 26 33

现在要求设计一个算法，给定一个数k 判断出k是否在这个矩阵中。描述算法并且给出时间复杂度（不考虑载入矩阵的消耗）

方法一

从右上角开始（从左下角开始也是一样的），然后每步往左或往下走。

这样每步都能扔掉一行或者一列，最坏的情况是被查找的元素位于另一个对角，需要2N步，因此这个算法是o(n)的，而且代码简洁直接。

bool stepWise(int mat\[\]\[N\] , int key , int&row , int &col)

if(key < mat\[0\]\[0\] || key > mat\[N-1\]\[N-1\])

return false;

row = 0;

col = N-1;

while(row < N && col >= 0)

if(mat\[row\]\[col\] == key ) //查找成功

return true;

else if(mat\[row\]\[col\] < key )

\++row;

else

\--col;

return false;

方法二（分治法）

首先，我们注意到矩阵中的元素总是把整个矩阵分成四个更小的矩阵。例如，中间的元素9把整个矩阵分成如下图所示的四块。由于四个小矩阵也是行列有序的，问题自然而然地划分为四个子问题。每次我们都能排除掉四个中的一个子问题。假如我们的查找目标是21，21>9，于是我们可以立即排除掉9左上方的那块，因为那个象限的元素都小于或等于9。

以下是这种二维二分的代码，矩阵的维度使用l、u、r、d刻画的，其中l和u表示左上角的列和行，r和d表示右下角的列和行。

bool quadPart(int mat\[\]\[N\] , int key , intl , int u , int r , int d , int &row , int &col)

if(l > r || u > d)

return false;

if(key < mat\[u\]\[l\] || key > mat\[d\]\[r\])

return false;

int mid\_col = (l+r)>>1;

int mid\_row = (u+d)>>1;

if(mat\[mid\_row\]\[mid\_col\] == key) //查找成功

row = mid\_row;

col = mid\_col;

return true;

else if(l == r && u == d)

return false;

if(mat\[mid\_row\]\[mid\_col\] > key)

\{ // 分别在右上角、左上角、左下角中查找

return quadPart(mat , key , mid\_col+1 , u , r , mid\_row , row , col)||

quadPart(mat , key , l ,mid\_row+1 , mid\_col , d , row , col) ||

quadPart(mat , key , l , u ,mid\_col , mid\_row , row , col) ;

else

\{ // 分别在右上角、左下角、右下角中查找

return quadPart(mat , key , mid\_col+1 , u , r , mid\_row , row , col)||

quadPart(mat , key , l ,mid\_row+1 , mid\_col , d , row , col) ||

quadPart(mat , key , mid\_col+1 ,mid\_row+1 , r , d , row , col) ;

bool quadPart(int mat\[\]\[N\] , int key , int&row , int &col)

return bool quadPart(mat , key , 0 , 0 , N-1 , N-1 , row , col);

63. 下面的程序可以从1....n中随机输出m个不重复的数。请填空

knuth(int n, int m)

srand((unsigned int)time(0));

for (int i=0; i<n; i++)

if (rand()%(n-i)<m)

cout<<i<<endl;

(m--);

64. 下列代码的输出为：B

\#include "iostream"

\#include "vector"

using namespace std;

int main(void)

vector<int>array;

array.push\_back(100);

array.push\_back(300);

array.push\_back(500);

vector<int>::iteratoritor;

for(itor=array.begin();itor!=array.end();itor++)

if(\*itor==300)

itor= array.erase(itor);

for(itor=array.begin();itor!=array.end();itor++)

cout<<\*itor<<"";

return0;

A、100 300 300 500 B、100 300 500C、100 500 D、程序错误

vector在erase之后，指向下一个元素的位置，其实进行erase操作时将后面所有元素都向前移动，迭代器位置没有移动。itor=array.erase(itor) erase返回下一个元素的地址，相当于给itor一个新值。

65. 在win32平台下，以下哪种方式无法实现进程同步？A

A、CriticalSection B、Event C、Mutex D、Semaphore

66. 按照升序排列的一组数据123456798，下面哪种排序法在空间和时间上最优？C

A、快速排序 B、冒泡排序 C、插入排序 D、堆排序

插入排序从后面插入的时候，只要把8和9交换一下就行了，遍历到前面都不再有任何操作。冒泡排序第一次循环把9沉到最后面，然后第二次循环发现没有任何交换操作，说明已经排好序了。

67. 5+55+555+...+555..5（12个5）所得之和的末三位数是多少

可以很显然看出他们尾数均是5，十二个5相加为60，所以个位是0，十一个5相加为55再加进位的6是61，所以十位为1，10个五相加为50再加进位的6为56，所以百位为6，故得和的最后三位是610。

68. 下面代码中for循环共执行了多少次？

unsigned short i,j;

for(i=0,j=2; i!=j; i+=5, j+=7)

\{\}

unsigned short占用2个字节，当数据范围到头了（2^16-1），就又从0开始计数了，这个其实就是两辆汽车行驶在一个圆圈里的汽车追及问题。一个速度为5，一个速度为7，当速度为7的超越速度为5的时候，两个汽车就相遇了，2 + 7n - 5n = 2^16 所以共循环了32767次。

69. 高度为1的平衡二叉树节点为1个，高度为5的平衡二叉树节点最少多少个？

递推关系

A(1)=1

A(2)=2

A(n+2)=A(n+1)+A(n)+1

子树高度为n+1,n以及根节点

你可以照这个以此类推就可以得出答案了。算下A（4）=7

设f（n）为高度为n的平衡二叉树最少含有的节点数，则：f(1) = 1;f(2) = 2; f(3) = 4;f(4) = 7;……

这些可以通过画图就能得到，但是当n很大时呢？其实有如下结论：f(n) = f(n-1) + f(n-2) +1,(n>=3)。这个递推结论如何得到的呢？

引导问题：求一棵二叉树的节点数目：

假设一颗二叉树T，其左右子树分别为TL,TR。又假设T的节点数目为F(T),TL，TR的节点数目分别为F(TL),F(TR)。则显然：

F(T) = F(TL) + F(TR) + 1。

本文的问题：求高度为n的平衡二叉树最小需要多少节点：

同样假设T为高度为n的平衡二叉树，其需要最少的节点数目为F(n)。又假设TL，TR为T的左右子树，因此TL，TR也为平衡二叉树。假设F1,F2为TL，TR的最少节点数，则，F(n) = F1+F2 +1。那么F1,F2 到底等于多少呢？由于TL，TR与T一样是平衡二叉树，又由于我们知道T的最少节点数是F(n),其中n为T的高度，因此如果我们知道TL，TR的高度就可以知道F1,F2的值了。由平衡二叉树的定义可以知道，TL和TR的高度要么相同，要么相差1，而当TL与TR高度相同(即:都等于n-1)时，我们算出来的F(n)并不能保证最小，因此只有当TL与TR高度相差一(即：一个高度为n-1，一个高度为n-2)时，计算出来的F(n)才能最小。此时我们假设TL比TR高度要高1(即：TL高度为n-1，TR高度为n-2)，则有：F1 = F(n-1),F2 = F(n-2)。因此得到结论：F(n) = F(n-1)+ F(n -2 ) + 1!

这个地方推导思路稍微有点不清晰，应该都能明白，这个问题本来是很简单的问题，通过这个问题，我们可以看出递归的思想在树结构中的重要性，通过递归将问题抽象为多个规模更小的同类问题是解决这类问题的关键！当然，编程计算的时候一般用递推来计算较好(递归时会使用函数堆栈，函数堆栈是有限的，小心溢出).

70. 问题：在80X86架构下，输出什么值？填空题。

union Test

char a\[4\];

short b;

\};

Test test;

test.a\[0\]=256;

test.a\[1\]=255;

test.a\[2\]=254;

test.a\[3\]=253;

printf("%d\\n",test.b);

short类型占2个字节，如果右边是低地址，左边是高地址，那么存储如下：

1111 1111 0000 0000

test.a\[1\] test.a\[0\]

显然b占用上面的2个字节，最高位为1，则是一个负数，取反+1后，得到-256（1000 0001 0000 0000）

71. C++什么时候使用拷贝构造函数？

在下面几种情况下会调用拷贝构造函数：

a显式或隐式地用同类型的一个对象来初始化另外一个对象。用对象c初始化d；

b作为实参(argument)传递给一个函数。如CClass(constCClass c\_class)中，就会调用CClass的拷贝构造函数；

c在函数体内返回一个对象时，也会调用返回值类型的拷贝构造函数；

d初始化序列容器中的元素时。比如vector<string> svec(5)，string的缺省构造函数和拷贝构造函数都会被调用；

e用列表的方式初始化数组元素时。stringa\[\] = \{string(“hello”), string(“world”)\}; 会调用string的拷贝构造函数。

72. 复杂链表的复制

题目：有一个复杂链表，其结点除了有一个m\_pNext指针指向下一个结点外，还有一个m\_pSibling指向链表中的任一结点或者NULL。其结点的C++定义如下：

struct ComplexNode

int m\_nValue;

ComplexNode\* m\_pNext;

ComplexNode\* m\_pSibling;

\};

请完成函数ComplexNode\* Clone(ComplexNode\* pHead)，以复制一个复杂链表。

分析：在常见的数据结构上稍加变化，这是一种很新颖的面试题。要在不到一个小时的时间里解决这种类型的题目，我们需要较快的反应能力，对数据结构透彻的理解以及扎实的编程功底。

看到这个问题，我的第一反应是分成两步：第一步是复制原始链表上的每个链表，并用m\_pNext链接起来。第二步，假设原始链表中的某节点N的m\_pSibling指向结点S。由于S的位置在链表上有可能在N的前面也可能在N的后面，所以要定位N的位置我们需要从原始链表的头结点开始找。假设从原始链表的头结点开始经过s步找到结点S。那么在复制链表上结点N的m\_pSibling的S’，离复制链表的头结点的距离也是s。用这种办法我们就能为复制链表上的每个结点设置m\_pSibling了。

对一个含有n个结点的链表，由于定位每个结点的m\_pSibling，都需要从链表头结点开始经过O(n)步才能找到，因此这种方法的总时间复杂度是O(n2)。

由于上述方法的时间主要花费在定位结点的m\_pSibling上面，我们试着在这方面去做优化。我们还是分为两步：第一步仍然是复制原始链表上的每个结点N，并创建N’，然后把这些创建出来的结点链接起来。这里我们对<N，N’>的配对信息放到一个哈希表中。第二步还是设置复制链表上每个结点的m\_pSibling。如果在原始链表中结点N的m\_pSibling指向结点S，那么在复制链表中，对应的N’应该指向S’。由于有了哈希表，我们可以用O(1)的时间根据S找到S’。

第二种方法相当于用空间换时间，以O(n)的空间消耗实现了O(n)的时间效率。

接着我们来换一种思路，在不用辅助空间的情况下实现O(n)的时间效率。第三种方法的第一步仍然是根据原始链表的每个结点N，创建对应的N’。这一次，我们把新创建的每个结点N’链接在原先结点N的后面。代码如下：

/\*

Clone all nodes in a complex linked listwith head pHead,

and connect all nodes with m\_pNext link

\*/

void CloneNodes(ComplexNode\* pHead)

ComplexNode\* pNode = pHead;

while(pNode != NULL)

ComplexNode \*pCloned = new ComplexNode();

pCloned->m\_nValue = pNode->m\_nValue;

pCloned->m\_pNext = pNode->m\_pNext;

pCloned->m\_pSibling = NULL;

pNode->m\_pNext = pCloned; //将新复制的结点链接在原始结点的后面

pNode = pCloned->m\_pNext;

第二步是设置我们复制出来的链表上的结点的m\_pSibling。假设原始链表上的N的m\_pSibling指向结点S，那么其对应复制出来的N’是N->m\_pNext，同样S’也是S->m\_pNext。这就是我们在上一步中把每个结点复制出来的结点链接在原始结点后面的原因。有了这样的链接方式，我们就能在O(1)中就能找到每个结点的m\_pSibling了。代码如下：

/\*

Connect sibling nodes in a complex linklist

\*/

void ConnectSiblingNodes(ComplexNode\*pHead)

ComplexNode\* pNode = pHead;

while(pNode != NULL) //遍历链表更新随机指针

ComplexNode \*pCloned = pNode->m\_pNext;

if(pNode->m\_pSibling != NULL)

pCloned->m\_pSibling = pNode->m\_pSibling->m\_pNext; //新复制结点的随机指针就是原始结点的随机指针指向的结点的下一个结点

pNode = pCloned->m\_pNext;

第三步是把这个长链表拆分成两个：把奇数位置的结点链接起来就是原始链表，把偶数位置的结点链接出来就是复制出来的链表。要实现这一步，也不是很难的事情。其对应的代码如下：

/\*

Split a complex list into two:

Reconnect nodes to get the original list,and its cloned list

\*/

ComplexNode\* ReconnectNodes(ComplexNode\*pHead)

ComplexNode\* pNode = pHead;

ComplexNode\* pClonedHead = NULL;

ComplexNode\* pClonedNode = NULL;

if(pNode != NULL)

pClonedHead = pClonedNode = pNode->m\_pNext;

pNode->m\_pNext = pClonedNode->m\_pNext;

pNode = pNode->m\_pNext;

while(pNode != NULL)

pClonedNode->m\_pNext = pNode->m\_pNext; //把偶数位置的结点链接起来就是复制出来的新链表

pClonedNode = pClonedNode->m\_pNext;

pNode->m\_pNext = pClonedNode->m\_pNext; //把奇数位置的结点链接起来就是原始链表

pNode = pNode->m\_pNext;

return pClonedHead;

我们把上面三步合起来，就是复制链表的完整过程：

ComplexNode\* Clone(ComplexNode\* pHead)

CloneNodes( pHead );

ConnectSiblingNodes( pHead );

return ReconnectNodes( pHead );

73. 下面程序的正确输出结果为（E）

class test

public:

voidprint()

cout<<"test"<<endl;

\};

int main(void)

test\*t = new test();

t->print();

t= NULL;

t->print();

return0;

A、编译不通过 B、运行时必然出错退出 C、运行时可能出错退出

D、test E、test test F、test 随机信息

print是一个类级别的东西，也就是说它和类的实例(或者类的对象)没有任何关系，这也就是说“并未使用this指针”，在这种情况下，print仅与test的类型有关，而不管t是什么东西，只要是类类型的指针就可以调用这个函数。

对象级别的东西，比如类中的某个非静态成员变量，这种东西和类的实例有关，因此它使用this指针。

74. 类型转换

首先回顾一下C++类型转换：

C++类型转换分为：隐式类型转换和显式类型转换

第1部分. 隐式类型转换

又称为“标准转换”，包括以下几种情况：

1) 算术转换(Arithmeticconversion) : 在混合类型的算术表达式中, 最宽的数据类型成为目标转换类型。

int ival = 3;

double dval = 3.14159;

ival + dval;//ival被提升为double类型

2)一种类型表达式赋值给另一种类型的对象：目标类型是被赋值对象的类型

int \*pi = 0; // 0被转化为int \*类型

ival = dval; // double->int

例外：void指针赋值给其他指定类型指针时，不存在标准转换，编译出错

3)将一个表达式作为实参传递给函数调用，此时形参和实参类型不一致：目标转换类型为形参的类型

extern double sqrt(double);

cout << "The square root of 2 is" << sqrt(2) << endl;

//2被提升为double类型：2.0

4)从一个函数返回一个表达式，表达式类型与返回类型不一致：目标转换类型为函数的返回类型

double difference(int ival1, int ival2)

return ival1 - ival2;

//返回值被提升为double类型

第2部分. 显式类型转换

被称为“强制类型转换”(cast)

C 风格： (type-id)

C++风格： static\_cast、dynamic\_cast、reinterpret\_cast、和const\_cast..

关于强制类型转换的问题，很多书都讨论过，写的最详细的是C++ 之父的《C++ 的设计和演化》。最好的解决方法就是不要使用C风格的强制类型转换，而是使用标准C++的类型转换符：static\_cast, dynamic\_cast。标准C++中有四个类型转换符：static\_cast、dynamic\_cast、reinterpret\_cast、和const\_cast。下面对它们一一进行介绍。

static\_cast

用法：static\_cast < type-id > ( expression )

说明：该运算符把expression转换为type-id类型，但没有运行时类型检查来保证转换的安全性。

来源：为什么需要static\_cast强制转换？

情况1：void指针->其他类型指针

情况2：改变通常的标准转换

情况3：避免出现可能多种转换的歧义

它主要有如下几种用法：

用于类层次结构中基类和子类之间指针或引用的转换。进行上行转换（把子类的指针或引用转换成基类表示）是安全的；进行下行转换（把基类指针或引用转换成子类指针或引用）时，由于没有动态类型检查，所以是不安全的。

用于基本数据类型之间的转换，如把int转换成char，把int转换成enum。这种转换的安全性也要开发人员来保证。

把void指针转换成目标类型的指针(不安全!!)

把任何类型的表达式转换成void类型。

注意：static\_cast不能转换掉expression的const、volitale、或者\_\_unaligned属性。

dynamic\_cast

用法：dynamic\_cast < type-id > ( expression )

说明：该运算符把expression转换成type-id类型的对象。Type-id必须是类的指针、类的引用或者void \*；如果type-id是类指针类型，那么expression也必须是一个指针，如果type-id是一个引用，那么expression也必须是一个引用。

来源：为什么需要dynamic\_cast强制转换？

简单的说，当无法使用virtual函数的时候

典型案例：

Wicrosoft公司提供给我们一个类库，其中提供一个类Employee.以头文件Eemployee.h和类库.lib分发给用户

显然我们并无法得到类的实现的源代码

//Emplyee.h

class Employee

public:

virtual int salary();

\};

class Manager : public Employee

public:

int salary();

\};

class Programmer : public Employee

public:

int salary();

\};

我们公司在开发的时候建立有如下类:

class MyCompany

public:

void payroll(Employee \*pe);

\};

void MyCompany::payroll(Employee \*pe)

//do something

但是开发到后期，我们希望能增加一个bonus()的成员函数到W$公司提供的类层次中。

假设我们知道源代码的情况下，很简单，增加虚函数：

//Emplyee.h

class Employee

public:

virtual int salary();

virtual int bonus();

\};

class Manager : public Employee

public:

int salary();

\};

class Programmer : public Employee

public:

int salary();

int bonus();

\};

//Emplyee.cpp

int Programmer::bonus()

payroll()通过多态来调用bonus()

class MyCompany

public:

void payroll(Employee \*pe);

\};

void MyCompany::payroll(Employee \*pe)

//do something

//pe->bonus();

但是现在情况是，我们并不能修改源代码，怎么办？dynamic\_cast华丽登场了！

在Employee.h中增加bonus()声明，在另一个地方定义此函数，修改调用函数payroll().重新编译，ok

//Emplyee.h

class Employee

public:

virtual int salary();

\};

class Manager : public Employee

public:

int salary();

\};

class Programmer : public Employee

public:

int salary();

int bonus();//直接在这里扩展

\};

//somewhere.cpp

int Programmer::bonus()

//define

class MyCompany

public:

void payroll(Employee \*pe);

\};

void MyCompany::payroll(Employee \*pe)

Programmer \*pm = dynamic\_cast<Programmer \*>(pe);

//如果pe实际指向一个Programmer对象,dynamic\_cast成功，并且开始指向Programmer对象起始处

if(pm)

//call Programmer::bonus()

//如果pe不是实际指向Programmer对象，dynamic\_cast失败，并且pm = 0

else

//use Employee member functions

dynamic\_cast主要用于类层次间的上行转换和下行转换，还可以用于类之间的交叉转换。

在类层次间进行上行转换时，dynamic\_cast和static\_cast的效果是一样的；在进行下行转换时，dynamic\_cast具有类型检查的功能，比static\_cast更安全。

class Base

public:

int m\_iNum;

virtual void foo();

\};

class Derived:public Base

public:

char \*m\_szName\[100\];

\};

void func(Base \*pb)

Derived \*pd1 = static\_cast<Derived \*>(pb);

Derived \*pd2 = dynamic\_cast<Derived \*>(pb);

在上面的代码段中，

如果pb实际指向一个Derived类型的对象，pd1和pd2是一样的，并且对这两个指针执行Derived类型的任何操作都是安全的；

如果pb实际指向的是一个Base类型的对象，那么pd1将是一个指向该对象的指针，对它进行Derived类型的操作将是不安全的（如访问m\_szName），而pd2将是一个空指针(即0，因为dynamic\_cast失败)。

另外要注意：Base要有虚函数，否则会编译出错；static\_cast则没有这个限制。这是由于运行时类型检查需要运行时类型信息，而这个信息存储在类的虚函数表（关于虚函数表的概念，详细可见<Inside c++ object model>）中，只有定义了虚函数的类才有虚函数表，没有定义虚函数的类是没有虚函数表的。

另外，dynamic\_cast还支持交叉转换（cross cast）。如下代码所示。

class Base

public:

intm\_iNum;

virtualvoid f()\{\}

\};

class Derived1 : public Base

\};

class Derived2 : public Base

\};

void foo()

Derived1\*pd1 = new Derived1;

pd1->m\_iNum= 100;

Derived2\*pd2 = static\_cast<Derived2 \*>(pd1); //compile error

Derived2\*pd3 = dynamic\_cast<Derived2 \*>(pd1); //pd2 is NULL

deletepd1;

\}在函数foo中，使用static\_cast进行转换是不被允许的，将在编译时出错；而使用 dynamic\_cast的转换则是允许的，结果是空指针。

reinpreter\_cast

用法：reinpreter\_cast<type-id> (expression)

说明：type-id必须是一个指针、引用、算术类型、函数指针或者成员指针。它可以把一个指针转换成一个整数，也可以把一个整数转换成一个指针（先把一个指针转换成一个整数，在把该整数转换成原类型的指针，还可以得到原先的指针值）。

该运算符的用法比较多。

const\_cast

用法：const\_cast<type\_id> (expression)

说明：该运算符用来修改类型的const或volatile属性。除了const 或volatile修饰之外， type\_id和expression的类型是一样的。

常量指针被转化成非常量指针，并且仍然指向原来的对象；常量引用被转换成非常量引用，并且仍然指向原来的对象；常量对象被转换成非常量对象。

Voiatile和const类试。举如下一例：

class B\{

public:

int m\_iNum;

void foo()\{

const B b1;

b1.m\_iNum = 100; //comile error

B b2 = const\_cast<B>(b1);

b2. m\_iNum = 200; //fine

上面的代码编译时会报错，因为b1是一个常量对象，不能对它进行改变；使用const\_cast把它转换成一个非常量对象，就可以对它的数据成员任意改变。注意：b1和b2是两个不同的对象。

75. std::vector::iterator重载了下面哪些运算符？(ACD)

A、++ B、>> C、\*（前置） D、==

76. 下列运算符，在C++语言中不能重载的是（BC）

A、\* B、？： C、：： D、delete

77. 在排序方法中，元素比较次数与元素的初始排列无关的是（d）

A、Shell 排序 B、归并排序 C、直接插入排序 D、选择排序

A、C肯定不选的，归并排序的在merge中是跟序列有关，如果有序，比较次数最少n/2，最糟是元素错落n-1。而选择排序比较次数与关键字的初始状态无关，总的比较次数N=(n-1)+(n-2)+...+1=n\*(n-1)/2。所以 应该是选择排序！

78. 关于struct和class，下列说法正确的是（AC）

A、struct的成员默认是public，class的成员默认是private

B、struct不能继承，class可以继承

C、struct可以有无参构造函数

D、struct的成员变量只能是public

若不明确指定，来自class的继承按照private继承处理，来自struct的继承按照public继承处理；都可使用public/private/protected修饰符，都可以有无参构造函数

79. 定义一个函数指针，指向的函数有两个int形参并且返回一个函数指针，返回的指针指向一个有一个int形参且返回int的函数？A

A、int (\*(\*F)(int,int))(int)

B、int (\*F)(int, int)

C、int (\*(\*F)(int,int))

D、\*(\*F)(int, int)(int)

80. 声明一个指向含有10个元素的数组的指针，其中每个元素是一个函数指针，该函数的返回值是int，参数是int\*，正确的是（C）

A、（int \*p\[10\]）（int\*）;

B、int \[10\]\*p（int \*）;

C、int (\*(\*p)\[10\])(int\*);

D、int ((int \*)\[10\])\*p;

81. 下面代码的输出是多少？

class A

public:

A() \{ cout<<"A"<<endl; \}

~A()\{ cout<<"~A"<<endl; \}

\};

class B:public A

public:

B(A&a):\_a(a)

cout<<"B"<<endl;

~B()

cout<<"~B"<<endl;

private:

A\_a;

\};

int main(void)

Aa; //很简单，定义a的时候调用了一次构造函数

Bb(a); //这里b里面的\_a是通过成员初始化列表构造起来的

//而且是通过copyconstructor构造的是b的成员对象\_a的，这里是编译器默认的，因此在构造好\_a前，先调用基类构造函数

//然后才是构造自身,顺序就是A()->\_a->B()（局部）

//因此这里有两个A,一个B

//在return之前进行析构

/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/

/\*析构是按照定义对象的反顺序来的，而且同一个对象按照构造的反顺序来的，因此这里先

析构b然后才是a，那么b的构造顺序是上面的A()->\_a->B()（局部），反过来，就是B()（局部）->\_a->A()

因此得到的就是~B->~A->~A

在b之后就是析构a

最后结果就是

~B->~A->~A->~A\*/

return0;

82. 假设有一个硬币，抛出字（背面）和花（正面）的概率都是0.5，而且每次抛硬币与前次结果无关。现在做一个游戏，连续地抛这个硬币，直到连续出现两次字为止，问平均要抛多少次才能结束游戏？注意，一旦连续抛出两个“字”向上游戏就结束了，不用继续抛

上面这个题目我第一次见到是在pongba的TopLanguage的一次讨论上，提出问题的人为Shuo Chen，当时我给出了一个解法，自认为已经相当简单了，先来考虑一下抛硬币的过程：首先先抛一枚硬币，如果是花，那么需要重头开始；如果是字，那么再抛一枚硬币，新抛的这枚如果也是字，则游戏结束，如果是花，那么又需要重头开始。根据这个过程，设抛硬币的期望次数为T，可以得到关系：

T = 1 + 0.5T + 0.5( 1 + 0.5 \* 0 + 0.5T)

解方程可得到 T = 6。

或者根据公式，需要连续抛出n个字的一般情形，结果相当简洁：Tn = 2^(n+1) - 2，其中Tn为首次出现连续的n个字的期望投掷数。

83. 12个高矮不同的人，排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问排列方式有多少种?

这个笔试题，很YD，因为把某个递归关系隐藏得很深。

问题分析:

我们先把这12个人从低到高排列，然后，选择6个人排在第一排，那么剩下的6个肯定是在第二排。

用0表示对应的人在第一排，用1表示对应的人在第二排，那么含有6个0，6个1的序列，就对应一种方案。

比如000000111111就对应着

第一排:0 1 2 3 4 5

第二排:6 7 8 9 10 11

010101010101就对应着