6.2 笔试真题 & 详解
1．烧一根不均匀的绳子，从头烧到尾总共需要 1 个小时，问如何用烧绳子的方法来确定半小时的时间呢？
2．10 个海盗抢到了100 颗宝石，每一颗都一样大小且价值连城。他们决定这么分：
（1）抽签决定自己的号码（1~10）；
（2）首先，由1 号提出分配方案，然后大家表决，当且仅当超过半数的人同意时，按照他的方案进行分配，否则将被扔进大海喂鲨鱼；
（3）如果1 号死后，再由2 号提出分配方案，然后剩下的4 个人进行表决，当且仅当超过半数的人同意时，按照他的方案进行分配，否则将被扔入大海喂鲨鱼；
（4）依此类推
条件：每个海盗都是很聪明的人，都能很理智地做出判断，从而做出选择。
问题：第一个海盗提出怎样的分配方案才能使自己的收益最大化？
3．为什么下水道的盖子是圆的？
4．中国有多少辆汽车？
5．你让工人为你工作7 天，回报是一根金条，这根金条平分成相连的7 段,你必须在每天结束的时候给他们一段金条。如果只允许你两次把金条弄断，你如何给你的工人付费？
6．有一辆火车以每小时15 公里的速度离开北京直奔广州，同时另一辆火车以每小时20 公里的速度从广州开往北京。如果有一只鸟，以30 公里每小时的速度和两辆火车同时启动，从北京出发，碰到另一辆车后就向相反的方向返回去飞，就这样依次在两辆火车之间来回地飞，直到两辆火车相遇。请问， 这只鸟共飞行了多长的距离？
7．你有两个罐子以及50 个红色弹球和50 个蓝色弹球，随机选出一个罐子，随机选出一个弹球放入罐子，怎样给出红色弹球最大的选中机会？在你的计划里，得到红球的几率是多少？
8．想像你站在镜子前，请问，为什么镜子中的影像可以左右颠倒，却不能上下颠倒呢？
9．如果你有无穷多的水，一个3 公升的提捅，一个5 公升的提捅，两只提捅形状上下都不均匀，问你如何才能准确称出4 公升的水？
10．你有一桶果冻，其中有黄色、绿色、红色三种，闭上眼睛抓取同种颜色的两个。抓取多少次就可以确定你肯定有两个同一颜色的果冻？
11．连续整数之和为1000 的共有几组？
12．从同一地点出发的相同型号的飞机，可是每架飞机装满油只能绕地球飞半周，飞机之间可以加油，加完油的飞机必须回到起点。问至少要多少架次，才能满足有一架绕地球一周。
参考答案：1．两边一起烧。
2．96，0，1，0，1，0，1，0，1，0。
3．因为口是圆的。
4．很多。
5．分1，2，4。
6．6/7 北京到广州的距离。
7．100%。
8．平面镜成像原理（或者是“眼睛是左右长的”）。
9．3 先装满，倒在5 里，再把3 装满，倒进5 里。把5 里的水倒掉，把3 里
剩下的水倒进5 里，再把3 装满，倒进5 里，ok！
10．一次。
11．首先1000 为一个解。连续数的平均值设为x，1000 必须是x 的整数倍。
假如连续数的个数为偶数个，x 就不是整数了。x 的2 倍只能是5，25，125 才行。
因为平均值为12.5,要连续80 个达不到。125/2=62.5 是可以的。即62，63，61，
64，等等。连续数的个数为奇数时，平均值为整数。1000 为平均值的奇数倍。
1000=2×2×2×5×5×5；x 可以为2，4，8，40，200 排除后剩下40 和200 是可以的。所以答案为平均值为62.5，40，200，1000 的4 组整数。
12．答案是5 架次。一般的解法可以分为如下两个部分：
（1）直线飞行
一架飞机载满油飞行距离为1，n 架飞机最远能飞多远？在不是兜圈没有迎头接应的情况，这问题就是n 架飞机能飞多远？存在的极值问题是不要重复飞行，比如两架飞机同时给一架飞机加油且同时飞回来即可认为是重复，或者换句话说，离出发点越远，在飞的飞机就越少，这个极值条件是显然的，因为n 架飞机带的油是一定的，如重复，则浪费的油就越多。比如最后肯定是只有一架飞机全程飞行，注意“全程”这两个字，也就是不要重复的极值条件。如果是两架飞机的话，肯定是一架给另一架加满油，并使剩下的油刚好能回去，就说第二架飞机带的油耗在3 倍于从出发到加油的路程上，有三架飞机第三架带的油耗在倍于从出发到其加油的路程上，所以n 架飞机最远能飞行的距离为s=1+1/3+?+1/（2n+1）这个级数是发散的，所以理论上只要飞机足够多最终可以使一架飞机飞到无穷远，当然实际上不可能一架飞机在飞行1/（2n+1）时间内同时给n个飞机加油。
（2）可以迎头接应加油
一架飞机载满油飞行距离为1/2，最少几架飞机能飞行距离1？也是根据不要重复飞行的极值条件，得出最远处肯定是只有一架飞机飞行，这样得出由1/2处对称两边1/4 肯定是一架飞机飞行，用上面的公式即可知道一边至少需要两架飞机支持，（1/3+1/5）/2>1/4（左边除以2 是一架飞机飞行距离为1/2），但是有一点点剩余，所以想像为一个滑轮（中间一个飞机是个绳子，两边两架飞机是个棒）的话，可以滑动一点距离，就说加油地点可以在一定距离内变动（很容)易算出来每架飞机的加油地点和加油数量，等等
题目二：1写出下列算法的时间复杂度。
(1)冒泡排序；
(2)选择排序；
(3)插入排序；
(4)快速排序；
(5)堆排序；
(6)归并排序；
2写出下列程序在X86上的运行结果。
struct mybitfields
{
unsigned short a : 4;
unsigned short b : 5;
unsigned short c : 7;
}test
void main(void)
{
int i;
test.a=2;
test.b=3;
test.c=0;
i=*((short *)&test);
printf("%d\n",i);
}
3写出下列程序的运行结果。
unsigned int i=3;
cout<<i * -1;
4写出下列程序所有可能的运行结果。
int a;
int b;
int c;
void F1()
{
b=a*2;
a=b;
}
void F2()
{
c=a+1;
a=c;
}
main()
{
a=5;
//Start F1,F2 in parallel
F1(); F2();
printf("a=%d\n",a);
}
5考察了一个CharPrev()函数的作用。
6对 16 Bits colors的处理，要求：
（1）Byte转换为RGB时，保留高5、6bits；
（2）RGB转换为Byte时，第2、3位置零。
7一个链表的操作，注意代码的健壮和安全性。要求：
（1）增加一个元素；
（2）获得头元素；
（3）弹出头元素（获得值并删除）。
8一个给定的数值由左边开始升位到右边第N位，如 0010<<1 == 0100 或者 0001 0011<<4 == 0011 0000
请用C或者C++或者其他X86上能运行的程序实现。
附加题（只有在完成以上题目后，才获准回答）
In C++, what does "explicit" mean? what does "protected" mean?
题目三：某栋写字楼6层，有1部电梯，请编写一个电梯仿真程序
A.考虑如下条件
1.每层楼都有上行和下行两个按键
2. 电梯一开始停在1层
3. 电梯可以容纳8个人
4. 乘坐电梯的客人的请求频率，时间间隔和到达楼层是随机的
5. 电梯的上下一层需要1秒
6. 电梯空间有限，同时只能容纳一定数量的客人，如果已经达到人数额度，电梯将不理会任何请求
7.不考虑客人请求当前楼层和不请求楼层的情况
8. 电梯的响应延迟为0（比如，电梯往3楼上行，3楼的客人在电梯到达3楼之前按上行键，程序有权调度电梯在3楼开门）
9. 电梯的开关门时间和客人上下电梯时间为0，匀速运行
10. 电梯调度算法不能预读尚未发生的请求（比如在10秒的时候电梯无法预知11秒时某层客人的请求)
11.客人请求发生在整数秒
B.目标
1. 在运送所有客人到达目标楼层的前提下电梯的总行程尽可能小
2. 设计一个接口，实现调度算法的可替换性（比如，通过重新实现该接口可以使系统使用其它算法）
C. 输入和输出
输入:
input.txt
客人的请求序列，格式为到达时间，所在楼层，请求楼层，假设该输入是按照时间递增的
比如：
input.txt
1 2 3
2 3 1
在1秒的时候有客人请求从2层到3层，2秒的时候有客人请求从3层到1层
输出: 设计一种简单实用的输出可以清晰地反映电梯的运转情况
题目四：选择题部分
1. 以下哪些不是栈的基本操作
A. push
B. pop
C. 判断栈是否为空
D. 栈排序
2.两个有序数组 大小都是 n，现在要对它们进行合并排序。 问最坏情况下，需要比较多少次？
A. 2n+1
B. 2n
C.2n-1
D…记不清了
3. （an 表示第 n 个常数， x^5 表示 x 的 5 次方）
f（x）= a0*x^0 + a1*x^1+a2*x^2+……an*x^n
对于固定的 n，f（x）的时间复杂度以及空间复杂度分别是多少？
A. o（n^2），o（n）
B.o（n），o（1）
C
D 都记不住了
4.是个概率题，大概意思是这样的
现在有 800 个人，但是只有 400 份奖品，有一对夫妇都参加抽奖，但是他们最多抽到一份奖，现在问
他们俩能抽到一份奖的概率是多少？
A.0.5
B.0.75
C. （0.5,0.75）
D. （0.75,1）
5. 现有一链表当前指示节点为 currentNode, 生成了一个新节点 newNode,问要把 newNode 插入到currentNode 之后 ，该怎么做？
A…
B…
C. newNode->next = currentNode->next, currentNode->next = newNode.
D…
6. 问以下哪些特征不是 interpreted language（解释型语言）所独有的：
（我们知道一般分为两种：解释型语言 VB,Shell,批处理等；编译型语言，C，java 等。各有优点 ）
A. 平台无关性。（明显不对，因为 java 才是平台无关的）
B. 执行速度较快（这个问题，以前做作业时就没争论清楚，自己感觉解释型语言不需要编译，速度能快一些，但是重复执行时，编译型语言只需要编译一次，效率高……）
C. 可以定义动态变量（应该两种都可以）
D.以上都不对
7.给了一个二叉树，让求后序遍历的结果。
这个题如果知道后序遍历，肯定就可以做出来了。
尽管不难 还是要搞清楚三者的区别（哈哈）
先序 左根右
中序 根左右
后序 左右根
8.问以下几种排序方法，在最坏情况下时间复杂度小于 o（n^2）的是哪一种（这个题目记得不是很清楚了）
A.快排
B.插入排序
C.合并排序
D.栈排序
9. 现有 n+1 这么大的存储空间（可以理解有这么一个大小为 n+1 的数组），中间存了[1,n+1]范围内的n 个数，说明丢失了一个数，现在要找出这个丢失的数，问最好情况下时间复杂度是多少
A.o（1）
B.o（n）
C.o（n^2）
D.o（nlogn）
10.是一道程序题，由于太长，无从记忆……
编程题部分用 C,C++,C#,或 Java 中的一种来编写以下程序。
现在给你一个 字符串，其中特殊的字符只有两种 space（空格）（" "），newline（换行）（/n）。 现在让你来去除其中多余的空格。具体要求
1.连续的空格只能当保留其中一个
2. 该字符串的开头不能有空格
3. 该字符串的结尾不能有空格
4. 任何/n 的前面或才后面都不能存在多余的空格
为了得到很高的分数，还需要满足以下条件
1.不能申请新的字符串空间
2.对给出的字符串只能遍历一遍
不能使用任何库函数。
我们给了两个供你调用的函数
int intIsSpace（char str）（）
当字符不为空格时，将返回 0
当字符为空格时，将返回其它任意非 0 值
int intIsNewLine（char str）（）当字符不为换行时，将返回 0
当字符为换行时，将返回其它任意非 0 值
程序编写完成后，请编写测试用例，并说明它完成的作用。
题目五：Questions #1
1) How would you calculate the hash value of a string?
2) List two major requirements of a hashing function
Questions #2: Logical expressionsAssuming A, B, C are conditions. You can write logical expression that yields specific results. For example,
Expression “ A or B” will give above result |
Expression “ (not A) and B” will give above result |
Please write the simplest logical expression that will give the following results (using only
and, or, not operators)
Expression: |
Expression: |
Please rewrite the following If statements (in C) into just one If statement
For example,
if ( a > 10 )
{
if ( b < 5 )
{
Run();
}
}
can be rewritten as if ( a > 10 && b < 5 ) { Run(); }
Please rewrite the following if statement:
if ( a > 10 && b < 5)
{
if ( a > 15 )
{
Run();
}
}
else if ( b > 6 )
{
Run();
}
Questions #3
Please write a function in C to copy one string to another, while return the largest letter in the string. Please do not use any C runtime function.
char StringCopy( char *pszSrc, char *pszDst, int maxSize ) pszSrc: points to the source stringpszDst: points to the target string, where source string will be copied to
maxSize: max. number of characters allowed to be copied
The following code will display “Z”
char sz[100];
char ch;
ch = StringCopy( “Test Zoo”, sz );
printf( ch );
Questions #4Binary tree can be used for storing and searching data. Please draw a binary tree, constructed by entering the following numbers in sequence:
8, 3, 10, 50, 9, 20, 1, -5, 2, 70, 35, 45, -10, 49, 0
Please draw a balanced binary tree using the same set of numbers as above.
Questions #5Please define the data structure required to store a linked list of integer and write a routine to delete an integer from a given linked list of integers.
Questions #6Please explain the difference between array and link-list.
If you are asked to implement a stack, will you use array, or link-list, or both? What are the limitations of using each one?
Questions #7 (Windows Programming)What is a message pump in Windows?
Please list names of Windows message that is sent when:
- A window is created: ______________________
- A window needs to be painted: ______________________
- A window is destroyed: ______________________
1．改错
#include <stdio.h>
#include <String.h>
class CBuffer
{
char * m_pBuffer;
int m_size;
public:
CBuffer()
{
m_pBuffer=NULL;
}
~CBuffer()
{
Free();
}
void Allocte(int size) （3） {
m_size=size;
m_pBuffer= new char[size];
}
private:
void Free()
{
if(m_pBuffer!=NULL)
{
delete m_pBuffer;
m_pBuffer=NULL;
}
}
public:
void SaveString(const char* pText) const
{
strcpy(m_pBuffer, pText);
}
char* GetBuffer() const
{
return m_pBuffer;
}};
void main (int argc, char* argv[])
{
CBuffer buffer1;
buffer1.SaveString("Microsoft");
printf(buffer1.GetBuffer());
}
答：改正后
主要改正 SaveString 函数
将
void SaveString(const char* pText) const
{
strcpy(m_pBuffer, pText);
}
改为
void SaveString(const char* pText) （1）
{
Allocte(strlen(pText)+1); （2）
strcpy(m_pBuffer, pText);
}
原因：
（1） const 成员函数表示不会修改数据成员，而 SaveString 做不到，去掉 const 声明
（2） m_pBuffer 指向 NULL，必须用 Allocte 分配空间才能赋值。
（3） 另外需要将 Allocte 成员函数声明为私有成员函数更符合实际
2.下来程序想打印“Welcome MSR Asia”，改正错误
#include <stdio.h>
#include <string.h>
char * GetName (void)
{
//To return “MSR Asia” String
char name[]="MSR Asia";
return name;
}
void main(int argc, char* argv[])
{
char name[32];
//Fill in zeros into name
for(int i=0;i<=32;i++)
{
name[i]='\0';}
//copy “Welcome” to name
name="Welcome";
//Append a blank char
name[8]=" ";
//Append string to name
strcat(name,GetName());
//print out
printf(name);
}
答：改正后为
#include <stdio.h>
#include <string.h>
char * GetName (void)
{
//To return “MSR Asia” String
//char name[]="MSR Asia"; （1）
char *name=(char *)malloc(strlen("MSR Asia")+1);
strcpy(name,"MSR Asia");
return name;
}
void main(int argc, char* argv[])
{
char name[32];
//Fill in zeros into name
for(int i=0;i<=32;i++)
{
name[i]='\0';
}
//copy “Welcome” to name
//name="Welcome"; （2）
strcat(name,"Welcome ");
//Append a blank char
// name[8]=' '; （3）
//Append string to name
char *p=GetName(); （4）
strcat(name,p);
free (p);
//print out
printf(name);
}
原因：（1）在函数内部定义的变量在函数结束时就清空了，必须动态分配内存（2）字符串赋值语句错误，应该用 strcat
（3）该语句无效，可去掉
（4）定义一个指针指向动态分配的内存，用完后需用 free 语句释放
3．写出下面程序的输出结果
#include <stdio.h>
class A
{
public:
void FuncA()
{
printf("FuncA called\n");
}
virtual void FuncB()
{
printf("FuncB called\n");
}
};
class B: public A
{
public:
void FuncA()
{
A::FuncA();
printf("FuncAB called\n");
}
virtual void FuncB()
{
printf("FuncBB called\n");
}
};
void main(void)
{
B b;
A *pa;
pa=&b;
A *pa2=new A;
b.FuncA(); （1）
b.FuncB(); （2）
pa->FuncA(); （3）pa->FuncB(); （4）
pa2->FuncA(); （5）
pa2->FuncB();
delete pa2;
}
答：
1．b.FuncA(); 输出
FuncA called
FuncAB called
2．b.FuncB();输出
FuncBB called
上两者好理解，直接调用类 B 的相应成员函数
3．pa->FuncA();输出
FuncA called 调用类 A 的 FuncA()
4．pa->FuncB();输出
FuncBB called 调用类 B 的 FuncB()，原因是 C++的动态决议机制，当基类函数声明为 virtual 时，指向派生
类对象的基类指针来调用该函数会选择派生类的实现，除非派生类没有才调用基类的虚函数。还有一点注
意的是：指向基类类型的指针可以指向基类对象也可以指向派生类对象，如 pa=&b;
5. pa2->FuncA();
pa2->FuncB();输出
FuncA called
FuncB called
这也好理解，直接调用类 A 的相应成员函数
4．In the main() function, after ModifyString(text) is called, what’s the value of ‘text’?
#include <stdio.h>
#include <string.h>
int FindSubString(char* pch)
{
int count=0;
char* p1=pch;
while(*p1!='\0')
{
if(*p1==p1[1]-1)
{
p1++;
count++;
}
else
{
break;
}
}int count2=count;
while(*p1!='\0')
{
if(*p1==p1[1]+1)
{
p1++;
count2--;
}
else
{
break;
}
}
if(count2==0)
return count;
return 0;
}
void ModifyString(char* pText)
{
char* p1=pText;
char* p2=p1;
while(*p1!='\0')
{
int count=FindSubString(p1);
if(count>0){
*p2++=*p1;
sprintf(p2, "%I", count);
while(*p2!= '\0')
{
p2++;
}
p1+=count+count+1;
}
else{
*p2++=*p1++;
}}
void main(void)
{
char text[32]="XYBCDCBABABA";
ModifyString(text);
printf(text);
}
答：我不知道这个结构混乱的程序到底想考察什么，只能将最后运行结果写出来是 XYBCDCBAIBAAP1912
给定一单链表的表头指针和指向其中一个节点的指针，要求以该指针为头将原链表逆序排列，例如：
N1->N2->N3->N4->N5->NULL pHEAD = N1，pSTART = N3，返回 N3->N2->N1->N5->N4->NULL
N1->N2->N3->N4->N5->NULL pHEAD = N1，pSTART = N5，返回这个 N5->N4->N3->N2->N1->NULL
N1->N2->N3->N4->N5->NULL pHEAD = N1，pSTART = N1，返回这个 N1->N5->N4->N3->N2->NULL
不允许额外分配存储空间，不允许递归，可以使用临时变量。
typedef struct node {
int value;
struct node *next;
} node;
void ReverseList(node **pHead, node *pStart){
node *t1, *t2, *it=*pHead;
t1 = it->next;
while(t1 != 0){
t2 = t1->next;
t1->next = (it == pStart?0:it);
it = t1;
t1 = t2;
}
(*pHead)->next = it;
*pHead = pStart;
}附加了测试代码后的完整程序，抄了一部分 chaoslawful 的，呵呵
#include <stdio.h>
#include <stdarg.h>
#include <stdlib.h>
typedef struct node {
int value;struct node *next;
} node;
void ReverseList(node **pHead, node *pStart){
node *t1, *t2, *it=*pHead;
t1 = it->next;
while(t1 != 0){
t2 = t1->next;
t1->next = (it == pStart?0:it);
it = t1;
t1 = t2;
}
(*pHead)->next = it;
*pHead = pStart;
}
void PrintList(node *pHead){
node *it=pHead;
while(it){
printf("%d ",it->value);
it=it->next;
}
}
void ConstructList(node **pHead,...)
{
node *q=0;
va_list ap;
int i;
va_start(ap, pHead);
while (1){
i = va_arg(ap,int);
if(i<0)
break;
if(!q){
*pHead=q=(node *)malloc(sizeof(node));
q->value=i;
q->next=0;
} else {
q->next=(node *)malloc(sizeof(node));
q=q->next;
q->value=i;
q->next=0;
}}
}
void SetStart(node *it, node **pStart, int i)
{
while(i-- > 0 && it->next != 0){
it = it->next;
}
*pStart = it;
}
int main(){
node *pHead=(node *)malloc(sizeof(node *));
node *pStart=(node *)malloc(sizeof(node *));
ConstructList(&pHead,1,2,3,4,5,-1);
PrintList(pHead);
SetStart(pHead, &pStart, 2);
ReverseList(&pHead, pStart);
PrintList(pHead);
return 1;
}
题目七：1.写出 a*(b-c*d)+e-f/g*(h+i*j-k)的逆波兰表达式
2.面向对象语言中 public,proteced,private 的区别
3.SAX 和 DOM 的区别以及各自优缺点
4.进程和线程区别
5.假设现有一个功能，用户点击一个按钮后就会自动发送一封邮件到用户的邮箱。现在
用户反映没有受到邮件。你怎么去发现并解决问题
6.用 Java 写一个 Singleton 类
7.2 个有序 List，请用 Java 写一个合并函数合并他们,返回一个有序 List
public List Merge(List a,List b){
}
题目八：1.求下面函数的返回值（微软）
int func(x)
{
int countx = 0;
while(x)
{
countx ++;
x = x&(x-1);
}
return countx;
}
假定 x = 9999。 答案：8
思路：将 x 转化为 2 进制，看含有的 1 的个数。
2. 什么是“引用”？申明和使用“引用”要注意哪些问题？
答：引用就是某个目标变量的“别名”(alias)，对应用的操作与对变量直接操作效果完全相同。
申明一个引用的时候，切记要对其进行初始化。引用声明完毕后，相当于目标变量名有两个名称，即该目标原名称和引用名，不能再把该引用名作为其他变量名的别名。声明一个引用，不是新定义了一个变量，它只表示该引用名是目标变量名的一个别名，它本身不是一种数据类型，因此引用本身不占存储单元，系统也不给引用分配存储单元。不能建立数组的引用。
3. 将“引用”作为函数参数有哪些特点？
（1）传递引用给函数与传递指针的效果是一样的。这时，被调函数的形参就成为原来主调函数中的实参变量或对象的一个别名来使用，所以在被调函数中对形参变量的操作就是对其相应的目标对象（在主调函数中）的操作。
（2）使用引用传递函数的参数，在内存中并没有产生实参的副本，它是直接对实参操作；而使用一般变量传递函数的参数，当发生函数调用时，需要给形参分配存储单元，形参变量是实参变量的副本；如果传递的是对象，还将调用拷贝构造函数。因此，当参数传递的数据较大时，用引用比用一般变量传递参数的效率和所占空间都好。
（3）使用指针作为函数的参数虽然也能达到与使用引用的效果，但是，在被调函数中同样要给形参分配存储单元，且需要重复使用"*指针变量名"的形式进行运算，这很容易产生错误且程序的阅读性较差；另一方面，在主调函数的调用点处，必须用变量的地址作为实参。而引用更容易使用，更清晰。
4. 在什么时候需要使用“常引用”？
如果既要利用引用提高程序的效率，又要保护传递给函数的数据不在函数中被改变，就应使用常引用。常引用声明方式：const 类型标识符 &引用名=目标变量名；
例 1
int a ;
const int &ra=a;
ra=1; //错误
a=1; //正确
例 2
string foo( );
void bar(string & s);
那么下面的表达式将是非法的：
bar(foo( ));bar("hello world");
原因在于 foo( )和"hello world"串都会产生一个临时对象，而在 C++中，这些临时对象都是const 类型的。因此上面的表达式就是试图将一个 const 类型的对象转换为非 const 类型，这是非法的。
引用型参数应该在能被定义为 const 的情况下，尽量定义为 const 。
5. 将“引用”作为函数返回值类型的格式、好处和需要遵守的规则?
格式：类型标识符 &函数名（形参列表及类型说明）{ //函数体 }
好处：在内存中不产生被返回值的副本；（注意：正是因为这点原因，所以返回一个局部变量的引用是不可取的。因为随着该局部变量生存期的结束，相应的引用也会失效，产生runtime error!
注意事项：
（1）不能返回局部变量的引用。这条可以参照 Effective C++[1]的 Item 31。主要原因是局部变量会在函数返回后被销毁，因此被返回的引用就成为了"无所指"的引用，程序会进入未知状态。
（2）不能返回函数内部 new 分配的内存的引用。这条可以参照 Effective C++[1]的 Item 31。
虽然不存在局部变量的被动销毁问题，可对于这种情况（返回函数内部 new 分配内存的引用），又面临其它尴尬局面。例如，被函数返回的引用只是作为一个临时变量出现，而没有被赋予一个实际的变量，那么这个引用所指向的空间（由new分配）就无法释放，造成memory leak。
（3）可以返回类成员的引用，但最好是 const。这条原则可以参照 Effective C++[1]的 Item 30。
主要原因是当对象的属性是与某种业务规则（business rule）相关联的时候，其赋值常常与某些其它属性或者对象的状态有关，因此有必要将赋值操作封装在一个业务规则当中。如果其它对象可以获得该属性的非常量引用（或指针），那么对该属性的单纯赋值就会破坏业务规则的完整性。
（4）流操作符重载返回值申明为“引用”的作用：
流操作符<<和>>，这两个操作符常常希望被连续使用，例如：cout << "hello" << endl; 因此这两个操作符的返回值应该是一个仍然支持这两个操作符的流引用。可选的其它方案包括：返回一个流对象和返回一个流对象指针。但是对于返回一个流对象，程序必须重新（拷贝）构造一个新的流对象，也就是说，连续的两个<<操作符实际上是针对不同对象的！这无法让人接受。对于返回一个流指针则不能连续使用<<操作符。因此，返回一个流对象引用是惟一选择。这个唯一选择很关键，它说明了引用的重要性以及无可替代性，也许这就是 C++语言中引入引用这个概念的原因吧。 赋值操作符=。这个操作符象流操作符一样，是可以连续使用的，例如：x = j = 10;或者(x=10)=100;赋值操作符的返回值必须是一个左值，以便可以被继续赋值。因此引用成了这个操作符的惟一返回值选择。
例 3
＃i nclude <iostream.h>
int &put(int n);
int vals[10];
int error=-1;
void main()
{
put(0)=10; //以 put(0)函数值作为左值，等价于 vals[0]=10;
put(9)=20; //以 put(9)函数值作为左值，等价于 vals[9]=20;
cout<<vals[0];cout<<vals[9];
}
int &put(int n)
{
if (n>=0 && n<=9 ) return vals[n];
else { cout<<"subscript error"; return error; }
}
（5）在另外的一些操作符中，却千万不能返回引用：+-*/ 四则运算符。它们不能返回引用，Effective C++[1]的 Item23 详细的讨论了这个问题。主要原因是这四个操作符没有 side effect，因此，它们必须构造一个对象作为返回值，可选的方案包括：返回一个对象、返回一个局部变量的引用，返回一个 new 分配的对象的引用、返回一个静态对象引用。根据前面提到的引用作为返回值的三个规则，第 2、3 两个方案都被否决了。静态对象的引用又因为((a+b) ==(c+d))会永远为 true 而导致错误。所以可选的只剩下返回一个对象了。
6. “引用”与多态的关系？
引用是除指针外另一个可以产生多态效果的手段。这意味着，一个基类的引用可以指向它的派生类实例。
例 4
Class A; Class B : Class A{...}; B b; A& ref = b;
7. “引用”与指针的区别是什么？
指针通过某个指针变量指向一个对象后，对它所指向的变量间接操作。程序中使用指针，程序的可读性差；而引用本身就是目标变量的别名，对引用的操作就是对目标变量的操作。此外，就是上面提到的对函数传 ref 和 pointer 的区别。
8. 什么时候需要“引用”？
流操作符<<和>>、赋值操作符=的返回值、拷贝构造函数的参数、赋值操作符=的参数、其它情况都推荐使用引用。
以上 2-8 参考：https://blog.csdn.net/wfwd/archive/2006/05/30/763551.aspx
9. 结构与联合有和区别？
1. 结构和联合都是由多个不同的数据类型成员组成, 但在任何同一时刻, 联合中只存放了一个被选中的成员（所有成员共用一块地址空间）, 而结构的所有成员都存在（不同成员的存放地址不同）。
2. 对于联合的不同成员赋值, 将会对其它成员重写, 原来成员的值就不存在了, 而对于结构的不同成员赋值是互不影响的。
10. 下面关于“联合”的题目的输出？
a)
＃i nclude <stdio.h>
union
{
int i;
char x[2];
}a;
void main()
{
a.x[0] = 10;a.x[1] = 1;
printf("%d",a.i);
}
答案：266 (低位低地址，高位高地址，内存占用情况是 Ox010A）
b)
main()
{
union{ /*定义一个联合*/
int i;
struct{ /*在联合中定义一个结构*/
char first;
char second;
}half;
}number;
number.i=0x4241; /*联合成员赋值*/
printf("%c%c\n", number.half.first, mumber.half.second);
number.half.first='a'; /*联合中结构成员赋值*/
number.half.second='b';
printf("%x\n", number.i);
getch();
}
答案： AB (0x41 对应'A',是低位；Ox42 对应'B',是高位）
6261 (number.i 和 number.half 共用一块地址空间）
11. 已知 strcpy 的函数原型：char *strcpy(char *strDest, const char *strSrc)其中 strDest 是目的字符串，strSrc 是源字符串。不调用 C++/C 的字符串库函数，请编写函数 strcpy。
答案：
char *strcpy(char *strDest, const char *strSrc)
{
if ( strDest == NULL || strSrc == NULL)
return NULL ;
if ( strDest == strSrc)
return strDest ;
char *tempptr = strDest ;
while( (*strDest++ = *strSrc++) != \0 )
;
return tempptr ;
}
12. 已知 String 类定义如下：
class String
{
public:
String(const char *str = NULL); // 通用构造函数
String(const String &another); // 拷贝构造函数~ String(); // 析构函数
String & operater =(const String &rhs); // 赋值函数
private:
char *m_data; // 用于保存字符串
};
尝试写出类的成员函数实现。
答案：
String::String(const char *str)
{
if ( str == NULL ) //strlen 在参数为 NULL 时会抛异常才会有这步判断
{
m_data = new char[1] ;
m_data[0] = '\0' ;
}
else
{
m_data = new char[strlen(str) + 1];
strcpy(m_data,str);
}
}
String::String(const String &another)
{
m_data = new char[strlen(another.m_data) + 1];
strcpy(m_data,other.m_data);
}
String& String::operator =(const String &rhs)
{
if ( this == &rhs)
return *this ;
delete []m_data; //删除原来的数据，新开一块内存
m_data = new char[strlen(rhs.m_data) + 1];
strcpy(m_data,rhs.m_data);
return *this ;
}
String::~String()
{
delete []m_data ;
}
13. .h 头文件中的 ifndef/define/endif 的作用？
答：防止该头文件被重复引用。
14. ＃i nclude<file.h> 与 ＃i nclude "file.h"的区别？
答：前者是从 Standard Library 的路径寻找和引用 file.h，而后者是从当前工作路径搜寻并引用 file.h。
15.在 C++ 程序中调用被 C 编译器编译后的函数，为什么要加 extern “C”？
首先，作为 extern 是 C/C++语言中表明函数和全局变量作用范围（可见性）的关键字，该关键字告诉编译器，其声明的函数和变量可以在本模块或其它模块中使用。
通常，在模块的头文件中对本模块提供给其它模块引用的函数和全局变量以关键字 extern声明。例如，如果模块 B 欲引用该模块 A 中定义的全局变量和函数时只需包含模块 A 的头文件即可。这样，模块 B 中调用模块 A 中的函数时，在编译阶段，模块 B 虽然找不到该函数，但是并不会报错；它会在连接阶段中从模块 A 编译生成的目标代码中找到此函数extern "C"是连接申明(linkage declaration),被 extern "C"修饰的变量和函数是按照 C 语言方式编译和连接的,来看看 C++中对类似 C 的函数是怎样编译的：
作为一种面向对象的语言，C++支持函数重载，而过程式语言 C 则不支持。函数被 C++编译后在符号库中的名字与 C 语言的不同。例如，假设某个函数的原型为：void foo( int x, int y );该函数被 C 编译器编译后在符号库中的名字为_foo，而 C++编译器则会产生像_foo_int_int之类的名字（不同的编译器可能生成的名字不同，但是都采用了相同的机制，生成的新名字称为“mangled name”）。
_foo_int_int 这样的名字包含了函数名、函数参数数量及类型信息，C++就是靠这种机制来实现函数重载的。例如，在 C++中，函数 void foo( int x, int y )与 void foo( int x, float y )编译生成的符号是不相同的，后者为_foo_int_float。
同样地，C++中的变量除支持局部变量外，还支持类成员变量和全局变量。用户所编写程序的类成员变量可能与全局变量同名，我们以"."来区分。而本质上，编译器在进行编译时，与函数的处理相似，也为类中的变量取了一个独一无二的名字，这个名字与用户程序中同名的全局变量名字不同。
未加 extern "C"声明时的连接方式
假设在 C++中，模块 A 的头文件如下：
// 模块 A 头文件 moduleA.h
#ifndef MODULE_A_H
#define MODULE_A_H
int foo( int x, int y );
#endif
在模块 B 中引用该函数：
// 模块 B 实现文件 moduleB.cpp
＃i nclude "moduleA.h"
foo(2,3);
实际上，在连接阶段，连接器会从模块 A 生成的目标文件 moduleA.obj 中寻找_foo_int_int这样的符号！
加 extern "C"声明后的编译和连接方式加 extern "C"声明后，模块 A 的头文件变为：
// 模块 A 头文件 moduleA.h
#ifndef MODULE_A_H
#define MODULE_A_H
extern "C" int foo( int x, int y );
#endif
在模块 B 的实现文件中仍然调用 foo( 2,3 )，其结果是：
（1）模块 A 编译生成 foo 的目标代码时，没有对其名字进行特殊处理，采用了 C 语言的方式；
（2）连接器在为模块 B 的目标代码寻找 foo(2,3)调用时，寻找的是未经修改的符号名_foo。如果在模块 A 中函数声明了 foo 为 extern "C"类型，而模块 B 中包含的是 extern int foo( int x,int y ) ，则模块 B 找不到模块 A 中的函数；反之亦然。
所以，可以用一句话概括 extern “C”这个声明的真实目的（任何语言中的任何语法特性的诞生都不是随意而为的，来源于真实世界的需求驱动。我们在思考问题时，不能只停留在这个语言是怎么做的，还要问一问它为什么要这么做，动机是什么，这样我们可以更深入地理解许多问题）：实现 C++与 C 及其它语言的混合编程。
明白了 C++中 extern "C"的设立动机，我们下面来具体分析 extern "C"通常的使用技巧：extern "C"的惯用法
（1）在 C++中引用 C 语言中的函数和变量，在包含 C 语言头文件（假设为 cExample.h）时，需进行下列处理：
extern "C"
{
＃i nclude "cExample.h"
}
而在 C 语言的头文件中，对其外部函数只能指定为 extern 类型，C 语言中不支持 extern "C"
声明，在.c 文件中包含了 extern "C"时会出现编译语法错误。
C++引用 C 函数例子工程中包含的三个文件的源代码如下：
/* c 语言头文件：cExample.h */
#ifndef C_EXAMPLE_H
#define C_EXAMPLE_H
extern int add(int x,int y);
#endif
/* c 语言实现文件：cExample.c */
＃i nclude "cExample.h"
int add( int x, int y )
{
return x + y;
}// c++实现文件，调用 add：cppFile.cpp
extern "C"
{
＃i nclude "cExample.h"
}
int main(int argc, char* argv[])
{
add(2,3);
return 0;
}
如果 C++调用一个 C 语言编写的.DLL 时，当包括.DLL 的头文件或声明接口函数时，应加extern "C" { }。
（2）在 C 中引用 C++语言中的函数和变量时，C++的头文件需添加 extern "C"，但是在 C语言中不能直接引用声明了extern "C"的该头文件，应该仅将C文件中将C++中定义的extern"C"函数声明为 extern 类型。
C 引用 C++函数例子工程中包含的三个文件的源代码如下：
//C++头文件 cppExample.h
#ifndef CPP_EXAMPLE_H
#define CPP_EXAMPLE_H
extern "C" int add( int x, int y );
#endif
//C++实现文件 cppExample.cpp
＃i nclude "cppExample.h"
int add( int x, int y )
{
return x + y;
}
/* C 实现文件 cFile.c
/* 这样会编译出错：＃i nclude "cExample.h" */
extern int add( int x, int y );
int main( int argc, char* argv[] )
{
add( 2, 3 );
return 0;
}
15 题目的解答请参考《C++中 extern “C”含义深层探索》注解：
16. 关联、聚合(Aggregation)以及组合(Composition)的区别？
涉及到 UML 中的一些概念：关联是表示两个类的一般性联系，比如“学生”和“老师”就是一种关联关系；聚合表示 has-a 的关系，是一种相对松散的关系，聚合类不需要对被聚合类负责，如下图所示，用空的菱形表示聚合关系：从实现的角度讲，聚合可以表示为:class A {...} class B { A* a; .....}
而组合表示 contains-a 的关系，关联性强于聚合：组合类与被组合类有相同的生命周期，组合类要对被组合类负责，采用实心的菱形表示组合关系：
实现的形式是:
class A{...} class B{ A a; ...}
参考文章：https://blog.csdn.net/wfwd/archive/2006/05/30/763753.aspx
https://blog.csdn.net/wfwd/archive/2006/05/30/763760.aspx
17.面向对象的三个基本特征，并简单叙述之？
1. 封装：将客观事物抽象成类，每个类对自身的数据和方法实行 protection(private,protected,public)
2. 继承：广义的继承有三种实现形式：实现继承（指使用基类的属性和方法而无需额外编码的能力）、可视继承（子窗体使用父窗体的外观和实现代码）、接口继承（仅使用属性和方法，实现滞后到子类实现）。前两种（类继承）和后一种（对象组合=>接口继承以及纯虚函数）构成了功能复用的两种方式。
3. 多态：是将父对象设置成为和一个或更多的他的子对象相等的技术，赋值之后，父对象就可以根据当前赋值给它的子对象的特性以不同的方式运作。简单的说，就是一句话：允许将子类类型的指针赋值给父类类型的指针。
18. 重载（overload)和重写(overried，有的书也叫做“覆盖”）的区别？
常考的题目。
从定义上来说：重载：是指允许存在多个同名函数，而这些函数的参数表不同（或许参数个数不同，或许参数类型不同，或许两者都不同）。
重写：是指子类重新定义复类虚函数的方法。
从实现原理上来说：
重载：编译器根据函数不同的参数表，对同名函数的名称做修饰，然后这些同名函数就成了不同的函数（至少对于编译器来说是这样的）。如，有两个同名函数： functionfunc(p:integer):integer;和 function func(p:string):integer;。那么编译器做过修饰后的函数名称可能是这样的：int_func、str_func。对于这两个函数的调用，在编译器间就已经确定了，是静态的。也就是说，它们的地址在编译期就绑定了（早绑定），因此，重载和多态无关！
重写：和多态真正相关。当子类重新定义了父类的虚函数后，父类指针根据赋给它的不同的子类指针，动态的调用属于子类的该函数，这样的函数调用在编译期间是无法确定的（调用的子类的虚函数的地址无法给出）。因此，这样的函数地址是在运行期绑定的（晚绑定）。
19. 多态的作用？
主要是两个：1. 隐藏实现细节，使得代码能够模块化；扩展代码模块，实现代码重用；2. 接口重用：为了类在继承和派生的时候，保证使用家族中任一类的实例的某一属性时的正确调用。
20. Ado 与 Ado.net 的相同与不同？
除了“能够让应用程序处理存储于 DBMS 中的数据“这一基本相似点外，两者没有太多共同之处。但是 Ado 使用 OLE DB 接口并基于微软的 COM 技术，而 ADO.NET 拥有自己的
ADO.NET 接口并且基于微软的.NET 体系架构。众所周知.NET 体系不同于 COM 体系，ADO.NET 接口也就完全不同于 ADO 和 OLE DB 接口，这也就是说 ADO.NET 和 ADO 是两种数据访问方式。ADO.net 提供对 XML 的支持。
21. New delete 与 malloc free 的联系与区别?
答案：都是在堆(heap)上进行动态的内存操作。用 malloc 函数需要指定内存分配的字节数并且不能初始化对象，new 会自动调用对象的构造函数。delete 会调用对象的 destructor，而free 不会调用对象的 destructor.
22. #define DOUBLE(x) x+x ，i = 5*DOUBLE(5)； i 是多少？
答案：i 为 30。
23. 有哪几种情况只能用 intialization list 而不能用 assignment?
答案：当类中含有 const、reference 成员变量；基类的构造函数都需要初始化表。
24. C++是不是类型安全的？
答案：不是。两个不同类型的指针之间可以强制转换（用 reinterpret cast)。C#是类型安全的。
25. main 函数执行以前，还会执行什么代码？
答案：全局对象的构造函数会在 main 函数之前执行。
26. 描述内存分配方式以及它们的区别?
1） 从静态存储区域分配。内存在程序编译的时候就已经分配好，这块内存在程序的整个运行期间都存在。例如全局变量，static 变量。
2） 在栈上创建。在执行函数时，函数内局部变量的存储单元都可以在栈上创建，函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集。
3） 从堆上分配，亦称动态内存分配。程序在运行的时候用 malloc 或 new 申请任意多少的内存，程序员自己负责在何时用 free 或 delete 释放内存。动态内存的生存期由程序员决定，使用非常灵活，但问题也最多。
27.struct 和 class 的区别
答案：struct 的成员默认是公有的，而类的成员默认是私有的。struct 和 class 在其他方面是功能相当的。
从感情上讲，大多数的开发者感到类和结构有很大的差别。感觉上结构仅仅象一堆缺乏封装和功能的开放的内存位，而类就象活的并且可靠的社会成员，它有智能服务，有牢固的封装屏障和一个良好定义的接口。既然大多数人都这么认为，那么只有在你的类有很少的方法并且有公有数据（这种事情在良好设计的系统中是存在的!）时，你也许应该使用 struct 关键字，否则，你应该使用 class 关键字。
28.当一个类 A 中没有生命任何成员变量与成员函数,这时 sizeof(A)的值是多少，如果不是零，请解释一下编译器为什么没有让它为零。（Autodesk）
答案：肯定不是零。举个反例，如果是零的话，声明一个 classA[10]对象数组，而每一个对象占用的空间是零，这时就没办法区分 A[0],A[1] 了。
29. 在 8086 汇编下，逻辑地址和物理地址是怎样转换的？（Intel）
答案：通用寄存器给出的地址，是段内偏移地址，相应段寄存器地址*10H+通用寄存器内地址，就得到了真正要访问的地址。
30. 比较 C++中的 4 种类型转换方式？
请参考：https://blog.csdn.net/wfwd/archive/2006/05/30/763785.aspx，重点是static cast, dynamic cast 和 reinterpret cast 的区别和应用。
31.分别写出 BOOL,int,float,指针类型的变量 a 与“零”的比较语句。
答案：BOOL : if ( !a ) or if(a)
int : if ( a == 0)
float : const EXPRESSION EXP = 0.000001
if ( a < EXP && a >-EXP)
pointer : if ( a != NULL) or if(a == NULL)
32.请说出 const 与#define 相比，有何优点？
答案：1） const 常量有数据类型，而宏常量没有数据类型。编译器可以对前者进行类型安全检查。而对后者只进行字符替换，没有类型安全检查，并且在字符替换可能会产生意料不到的错误。
2） 有些集成化的调试工具可以对 const 常量进行调试，但是不能对宏常量进行调试。
33.简述数组与指针的区别？
数组要么在静态存储区被创建（如全局数组），要么在栈上被创建。指针可以随时指向任意类型的内存块。
(1)修改内容上的差别
char a[] = “hello”;
a[0] = ‘X’;
char *p = “world”; // 注意 p 指向常量字符串
p[0] = ‘X’; // 编译器不能发现该错误，运行时错误
(2) 用运算符 sizeof 可以计算出数组的容量（字节数）。sizeof(p),p 为指针得到的是一个指针变量的字节数，而不是 p 所指的内存容量。C++/C 语言没有办法知道指针所指的内存容量，除非在申请内存时记住它。注意当数组作为函数的参数进行传递时，该数组自动退化为同类型的指针。
char a[] = "hello world";
char *p = a;
cout<< sizeof(a) << endl; // 12 字节
cout<< sizeof(p) << endl; // 4 字节
计算数组和指针的内存容量
void Func(char a[100])
{
cout<< sizeof(a) << endl; // 4 字节而不是 100 字节
}
34.类成员函数的重载、覆盖和隐藏区别？
答案：
a.成员函数被重载的特征：
（1）相同的范围（在同一个类中）；
（2）函数名字相同；
（3）参数不同；
（4）virtual 关键字可有可无。
b.覆盖是指派生类函数覆盖基类函数，特征是：
（1）不同的范围（分别位于派生类与基类）；
（2）函数名字相同；
（3）参数相同；
（4）基类函数必须有 virtual 关键字。c.“隐藏”是指派生类的函数屏蔽了与其同名的基类函数，规则如下：
（1）如果派生类的函数与基类的函数同名，但是参数不同。此时，不论有无 virtual 关键字，
基类的函数将被隐藏（注意别与重载混淆）。
（2）如果派生类的函数与基类的函数同名，并且参数也相同，但是基类函数没有 virtual 关键字。此时，基类的函数被隐藏（注意别与覆盖混淆）
35. There are two int variables: a and b, don’t use “if”, “? :”, “switch” or other judgement statements, find out the biggest one of the two numbers.
答案：( ( a + b ) + abs( a - b ) ) / 2
36. 如何打印出当前源文件的文件名以及源文件的当前行号？
答案：
cout << __FILE__ ;
cout<<__LINE__ ;
__FILE__和__LINE__是系统预定义宏，这种宏并不是在某个文件中定义的，而是由编译器定义的。
37. main 主函数执行完毕后，是否可能会再执行一段代码，给出说明？
答案：可以，可以用_onexit 注册一个函数，它会在 main 之后执行 int fn1(void), fn2(void), fn3(void), fn4 (void);
void main( void )
{
String str("zhanglin");
_onexit( fn1 );
_onexit( fn2 );
_onexit( fn3 );
_onexit( fn4 );
printf( "This is executed first.\n" );
}
int fn1()
{
printf( "next.\n" );
return 0;
}
int fn2()
{
printf( "executed " );
return 0;
}
int fn3()
{
printf( "is " );
return 0;
}
int fn4()
{
printf( "This " );return 0;
}
The _onexit function is passed the address of a function (func) to be called when the program terminates normally. Successive calls to _onexit create a register of functions that are executed in LIFO (last-in-first-out) order. The functions passed to _onexit cannot take parameters.
38. 如何判断一段程序是由 C 编译程序还是由 C++编译程序编译的？
答案：
#ifdef __cplusplus
cout<<"c++";
#else
cout<<"c";
#endif
39.文件中有一组整数，要求排序后输出到另一个文件中
答案：
＃i nclude<iostream>
＃i nclude<fstream>
using namespace std;
void Order(vector<int>& data) //bubble sort
{
int count = data.size() ;
int tag = false ; // 设置是否需要继续冒泡的标志位
for ( int i = 0 ; i < count ; i++)
{
for ( int j = 0 ; j < count - i - 1 ; j++)
{
if ( data[j] > data[j+1])
{
tag = true ;
int temp = data[j] ;
data[j] = data[j+1] ;
data[j+1] = temp ;
}
}
if ( !tag )
break ;
}
}
void main( void )
{
vector<int>data;
ifstream in("c:\\data.txt");
if ( !in){
cout<<"file error!";
exit(1);
}
int temp;
while (!in.eof())
{
in>>temp;
data.push_back(temp);
}
in.close(); //关闭输入文件流
Order(data);
ofstream out("c:\\result.txt");
if ( !out)
{
cout<<"file error!";
exit(1);
}
for ( i = 0 ; i < data.size() ; i++)
out<<data[i]<<" ";
out.close(); //关闭输出文件流
}
40. 链表题：一个链表的结点结构
struct Node
{
int data ;
Node *next ;
};
typedef struct Node Node ;
(1)已知链表的头结点 head,写一个函数把这个链表逆序 ( Intel)
Node * ReverseList(Node *head) //链表逆序
{
if ( head == NULL || head->next == NULL )
return head;
Node *p1 = head ;
Node *p2 = p1->next ;
Node *p3 = p2->next ;
p1->next = NULL ;
while ( p3 != NULL )
{
p2->next = p1 ;
p1 = p2 ;p2 = p3 ;
p3 = p3->next ;
}
p2->next = p1 ;
head = p2 ;
return head ;
}
(2)已知两个链表 head1 和 head2 各自有序，请把它们合并成一个链表依然有序。(保留所有
结点，即便大小相同）
Node * Merge(Node *head1 , Node *head2)
{
if ( head1 == NULL)
return head2 ;
if ( head2 == NULL)
return head1 ;
Node *head = NULL ;
Node *p1 = NULL;
Node *p2 = NULL;
if ( head1->data < head2->data )
{
head = head1 ;
p1 = head1->next;
p2 = head2 ;
}
else
{
head = head2 ;
p2 = head2->next ;
p1 = head1 ;
}
Node *pcurrent = head ;
while ( p1 != NULL && p2 != NULL)
{
if ( p1->data <= p2->data )
{
pcurrent->next = p1 ;
pcurrent = p1 ;
p1 = p1->next ;
}
else
{
pcurrent->next = p2 ;
pcurrent = p2 ;
p2 = p2->next ;}
}
if ( p1 != NULL )
pcurrent->next = p1 ;
if ( p2 != NULL )
pcurrent->next = p2 ;
return head ;
}
(3)已知两个链表 head1 和 head2 各自有序，请把它们合并成一个链表依然有序，这次要求用递归方法进行。 (Autodesk)
答案：
Node * MergeRecursive(Node *head1 , Node *head2)
{
if ( head1 == NULL )
return head2 ;
if ( head2 == NULL)
return head1 ;
Node *head = NULL ;
if ( head1->data < head2->data )
{
head = head1 ;
head->next = MergeRecursive(head1->next,head2);
}
else
{
head = head2 ;
head->next = MergeRecursive(head1,head2->next);
}
return head ;
}
41. 分析一下这段程序的输出 (Autodesk)
class B
{
public:
B()
{
cout<<"default constructor"<<endl;
}
~B()
{
cout<<"destructed"<<endl;
}
B(int i):data(i) //B(int) works as a converter ( int -> instance of B)
{cout<<"constructed by parameter " << data <<endl;
}
private:
int data;
};
B Play( B b)
{
return b ;
}
(1) results:
int main(int argc, char* argv[]) constructed by parameter 5
{ destructed B(5)形参析构
B t1 = Play(5); B t2 = Play(t1); destructed t1 形参析构
return 0; destructed t2 注意顺序！
} destructed t1
(2) results:
int main(int argc, char* argv[]) constructed by parameter 5
{ destructed B(5)形参析构
B t1 = Play(5); B t2 = Play(10); constructed by parameter 10
return 0; destructed B(10)形参析构
} destructed t2 注意顺序！
destructed t1
42. 写一个函数找出一个整数数组中，第二大的数 （microsoft）
答案：
const int MINNUMBER = -32767 ;
int find_sec_max( int data[] , int count)
{
int maxnumber = data[0] ;
int sec_max = MINNUMBER ;
for ( int i = 1 ; i < count ; i++)
{
if ( data[i] > maxnumber )
{
sec_max = maxnumber ;
maxnumber = data[i] ;
}
else
{
if ( data[i] > sec_max )
sec_max = data[i] ;
}
}
return sec_max ;}
43. 写一个在一个字符串(n)中寻找一个子串(m)第一个位置的函数。
KMP 算法效率最好，时间复杂度是Ｏ(n+m)。
44. 多重继承的内存分配问题：
比如有 classA: public class B, public class C {}
那么 A 的内存结构大致是怎么样的？
这个是 compiler-dependent 的, 不同的实现其细节可能不同。
如果不考虑有虚函数、虚继承的话就相当简单；否则的话，相当复杂。
可以参考《深入探索 C++对象模型》，或者：
https://blog.csdn.net/wfwd/archive/2006/05/30/763797.aspx
45. 如何判断一个单链表是有环的？（注意不能用标志位，最多只能用两个额外指针）
struct node { char val; node* next;}
bool check(const node* head) {} //return false : 无环；true: 有环
一种 O（n）的办法就是（搞两个指针，一个每次递增一步，一个每次递增两步，如果有环
的话两者必然重合，反之亦然）：
bool check(const node* head)
{
if(head==NULL) return false;
node *low=head, *fast=head->next;
while(fast!=NULL && fast->next!=NULL)
{
low=low->next;
fast=fast->next->next;
if(low==fast) return true;
}
return false;
}