经典笔试面试题总结(一)

男娘i 2022-08-08 19:52 173阅读 0赞

1、文件长度是一个大于0的整数，用变量unsignedfile\_length; 来表示，把文件分成块，每块的长度也是一个大于0的整数，用变量unsigned block\_length; 来表示，则文件被分成的块数为（）

A、file\_length/block\_length

B、file\_length/block\_length+1

C、(file\_length+block\_length-1)/block\_length

D、((file\_length-1)/block\_length+1

2、函数的局部变量所需存储空间，是在哪里分配的（）

A、进程的数据段 B、进程的栈上 C、进程的堆上 D、以上都可以

3、以下STL的容器存放的数据，哪个肯定是排好序的（）

A、vector B、deque C、list D、map

4、已知一段文本有1382个字符，使用了1382个字节进行存储，这段文本全部是由a、b、c、d、e这5个字符组成，a出现了354次，b出现了483次，c出现了227次，d出现了96次，e出现了232次，对这5个字符使用哈夫曼（Huffman）算法进行编码，则以下哪些说法正确（）

A、使用哈夫曼算法编码后，用编码值来存储这段文本将花费最少的存储空间

B、使用哈夫曼算法进行编码，a、b、c、d、e这5个字符对应的编码值是唯一确定的

C、使用哈夫曼算法进行编码，a、b、c、d、e这5个字符对应的编码值可以有多套，但每个字符编码的位（bit）数是确定的

D、b这个字符的哈夫曼编码值位数应该最短，d这个字符的哈夫曼编码值位数应该最长

5、下列表达式中，不合法的是（） 
已知：double d = 3.2; int n = 3; 
A、d<<2; 
B、d/n 
C、!d && (n-3) 
D、(d-0.2)|n

6、在使用浏览器打开一个网页的过程中，浏览器会使用的网络协议包括（）

A、DNS B、TCP C、HTTP  D、Telnet

8、拷贝构造函数的特点是（）

A、该函数名同类名，也是一种构造函数，该函数返回自身引用

B、该函数只有一个参数，必须是对某个对象的引用

C、每个类都必须有一个拷贝初始化构造函数，如果类中没有说明拷贝构造函数，则编译器系统会自动生成一个缺省拷贝构造函数，作为该类的保护成员

D、拷贝初始化构造函数的作用是将一个已知对象的数据成员值拷贝给正在创建的另一个同类的对象

9、下列关于虚函数的说法正确的是（）

A、在构造函数中调用类自己的虚函数，虚函数的动态绑定机制还会生效。

B、在析构函数中调用类自己的虚函数，虚函数的动态绑定机制还会生效。

C、静态函数不可以是虚函数

因为静态成员函数没有this，也就没有存放vptr的地方，同时其函数的指针存放也不同于一般的成员函数，其无法成为一个对象的虚函数的指针以实现由此带来的动态机制。静态是编译时期就必须确定的，虚函数是运行时期确定的。

D、虚函数可以声明为inline

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

因此，内联函数是个静态行为，而虚函数是个动态行为，他们之间是有矛盾的。

函数的inline属性是在编译时确定的，然而，virtual的性质则是在运行时确定的，这两个不能同时存在，只能有一个选择，文件中声明inline关键字只是对编译器的建议，编译器是否采纳是编译器的事情。

我并不否认虚函数也同样可以用inline来修饰，但你必须使用对象来调用，因为对象是没有所谓多态的，多态只面向行为或者方法，但是C++编译器，无法保证一个内联的虚函数只会被对象调用，所以一般来说，编译器将会忽略掉所有的虚函数的内联属性。

相关知识点：什么函数不能声明为虚函数？

一个类中将所有的成员函数都尽可能地设置为虚函数总是有益的。

设置虚函数须注意：

1：只有类的成员函数才能说明为虚函数；

2：静态成员函数不能是虚函数；

3：内联函数不能为虚函数；

4：构造函数不能是虚函数；

5：析构函数可以是虚函数，而且通常声明为虚函数。

（1）一位老师有2个推理能力很强的学生，他告诉学生他手里有以下的牌：

黑桃：2 ， 5 ， 7 ， 9 ， J ， K

红心：3 ， 4 ， 9 ， J ， K

梅花：5 ， 8 ， 9 ， Q

方块：2 ， 7 ， 8

然后从中拿出一张牌，告诉A这张牌的大小，告诉了B这张牌的花色；

A：我不知道这张是什么牌

B：我就知道你肯定不知道这张是什么牌

A：现在我知道

B：现在我也知道了

请问这张是什么牌？

答：方块8

（3）说明指针与引用的区别。  
答：

●指针是一个实体，而引用仅是个别名；  
●引用只能在定义时被初始化一次，之后不可变；指针可变；引用“从一而终”，指针可以“见异思迁”；  
●引用没有const，指针有const，const的指针不可变；  
●引用不能为空，指针可以为空；  
●“sizeof 引用”得到的是所指向的变量(对象)的大小，而“sizeof 指针”得到的是指针本身的大小；  
●指针和引用的自增(++)运算意义不一样；  
●引用是类型安全的，而指针不是 (引用比指针多了类型检查  
从内存分配上看：程序为指针变量分配内存区域，而引用不分配内存区域。指针：指向另一个内存空间的变量，我们可以通过它来索引另一个内存空间的内容，本身有自己的内存空间。

传统C语言的内部类型转换：

C语言传统的转化很简单。

比如：

double d=5.0;

int a=(int)d;

这个感觉和java差不多。

C++有四个内部类型转换操作符：const\_cast，reinterpret\_cast，static\_cast，dynamic\_cast。

const\_cast

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

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

一、常量指针被转化成非常量指针，并且仍然指向原来的对象；

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

三、常量对象被转换成非常量对象。

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

class B

public:

intm\_iNum;

B()

;

\};

void foo()

const B b1;

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

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

b2.m\_iNum = 200; //fine?

intmain()

foo();

return 0;

上面的代码编译时会报错，因为b1是一个常量对象，不能对它进行改变；

使用const\_cast把它转换成一个非常量对象引用，就可以对它的数据成员任意改变。

const\_cast用于类型转换掉表达式的const或volatileness属性。通过使用const\_cast，你向人们和编译器强调你通过类型转换想做的只是改变一些东西的constness或者volatileness属性。这个含义被编译器所约束。如果你试图使用const\_cast来完成修改constness 或者volatileness属性之外的事情，你的类型转换将被拒绝。

reinterpret\_cast

reinterpret\_cast是C++里的强制类型转换符。 它的本质是重新解释引用或者指针所对应的比特模型（类型），引用或者指针所指向的内存区域的数据不会变化。

例1：

int \*n= new int ;

double \*d=reinterpret\_cast<double\*>(n);

例2：

int n=9;

double &d=reinterpret\_cast<double&> (n);

在进行计算以后, d 包含无用值. 这是因为引用或者指针所指向的内存区域的数据不会变化。reinterpret\_cast仅仅重新解释引用或者指针所对应的比特模型（类型），而static\_cast却进行了二进制转换

例如：

intn=9; double d=static\_cast < double > (n);

上面的例子中, 我们将一个变量从 int 转换到 double。这些类型的二进制表达式是不同的。

要将整数 9 转换到 双精度 整数 9， static\_cast 需要正确地为双精度整数 d 补足比特位。其结果为9.0。

而reinterpret\_cast的行为却不同:

例3：

intn=9;

double d=reinterpret\_cast<double & > (n);

这次, 结果有所不同. 在进行计算以后, d 包含无用值. 这是因为reinterpret\_cast仅仅重新解释引用或者指针所对应的比特模型（类型）

因此, 你需要谨慎使用reinterpret\_cast.

注意：在例3中n和d的确对应不同的内存单元。

它似乎和reinterpret\_cast仅仅重新解释引用或者指针所对应的比特模型（类型）相矛盾。

其实不矛盾。例3的本质如下：

intn=9;

reinterpret\_cast<double & > temp=reinterpret\_cast<double& > (n);

double d=temp;//注意这里本质是拷贝。当然n和d的确对应不同的内存单元

static\_cast

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

该运算符把expression转换为type-id类型，但没有运行时类型检查来保证转换的安全性。它主要有如下几种用法：

①用于类层次结构中基类（父类）和派生类（子类）之间指针或引用的转换。

进行上行转换（把派生类的指针或引用转换成基类表示）是安全的；

进行下行转换（把基类指针或引用转换成派生类表示）时，由于没有动态类型检查，所以是不安全的。

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

③把空指针转换成目标类型的空指针。

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

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

C++中static\_cast和reinterpret\_cast的区别

C++primer第五章里写了编译器隐式执行任何类型转换都可由static\_cast显示完成;reinterpret\_cast通常为操作数的位模式提供较低层的重新解释

1、C++中的static\_cast执行非多态的转换，用于代替C中通常的转换操作。因此，被做为隐式类型转换使用。比如：

inti;

float f = 166.7f;

i =static\_cast<int>(f);

此时结果，i的值为166。

2、C++中的reinterpret\_cast主要是将数据从一种类型的转换为另一种类型。所谓“通常为操作数的位模式提供较低层的重新解释”

也就是说将数据以二进制存在形式的重新解释。比如：

inti;

char \*p = "This is a example.";

i =reinterpret\_cast<int>(p);

此时结果，i与p的值是完全相同的。reinterpret\_cast的作用是说将指针p的值以二进制（位模式）的方式被解释为整型，

并赋给i，//i 也是指针，整型指针；一个明显的现象是在转换前后没有数位损失。

dynamic\_cast

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

该运算符把expression转换成type-id类型的对象。Type-id必须是类的指针、类的引用或者void \*；

如果type-id是类指针类型，那么expression也必须是一个指针，如果type-id是一个引用，那么expression也必须是一个引用。

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

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

class B\{

public:

int m\_iNum;

virtual void foo();

\};

class D:public B\{

public:

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

\};

void func(B \*pb)\{

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

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

在上面的代码段中，如果pb指向一个D类型的对象，pd1和pd2是一样的，并且对这两个指针执行D类型的任何操作都是安全的；

但是，如果pb指向的是一个B类型的对象，那么pd1将是一个指向该对象的指针，对它进行D类型的操作将是不安全的（如访问m\_szName），

而pd2将是一个空指针。

注意：B要有虚函数，否则会编译出错；static\_cast则没有这个限制。

作为四个内部类型转换操作符之一的dynamic\_cast和传统的C风格的强制类型转换有着巨大的差别。除了dynamic\_cast以外的转换，

其行为的都是在编译期就得以确定的，转换是否成功，并不依赖被转换的对象。而dynamic\_cast则不然。

首先，dynamic\_cast依赖于RTTI信息，其次，在转换时，dynamic\_cast会检查转换的source对象是否真的可以转换成target类型，这种检查不是语法上的，而是真实情况的检查。先看RTTI相关部分，通常，许多编译器都是通过vtable找到对象的RTTI信息的，

这也就意味着，如果基类没有虚方法，也就无法判断一个基类指针变量所指对象的真实类型,

这时候，dynamic\_cast只能用来做安全的转换,例如从派生类指针转换成基类指针.而这种转换其实并不需要dynamic\_cast参与.也就是说,dynamic\_cast是根据RTTI记载的信息来判断类型转换是否合法的.

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

class A\{

public:

intm\_iNum;

virtual void f()\{\}

\};

class B:public A\{

\};

class D:public A\{

\};

void foo()\{

B\*pb = new B;

pb->m\_iNum = 100;

D\*pd1 = static\_cast<D \*>(pb); //compile error

D\*pd2 = dynamic\_cast<D \*>(pb); //pd2 is NULL

delete pb;

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

下面再看一个例子:

struct B1\{

virtual ~B1()\{\}

\};

struct B2\{

virtual ~B2()\{\}

\};

struct D1 : B1, B2\{\};

int main()

D1 d;

B1\* pb1 = &d;

B2\* pb2 = dynamic\_cast<B2\*>(pb1);//L1

B2\* pb22 = static\_cast<B2\*>(pb1); //L2

return 0;

上述定义中可以看到,B1和B2是不相关的类,从L1可以看到,dynamic\_cast允许这种转换:只要B1存在多态方法.

L2将编译失败,static\_cast并不允许两个完全不相干的类互相转换.

（5）写个简单的函数，用于判断CPU的字节序（littleendian/big endian）

//若处理器是Big\_endian的，则返回0；若是Little\_endian的，则返回1。

intcheckCPU(void)

union

int a;

char b;

\}c;

c.a = 1;

return (c.b == 1);

1）列出几种你了解的IPC机制。

答：共享内存：是一片指定的物理内存区域，这个区域通常是在存放正常程序数据区域的外面, 它允许两个或多个进程共享一给定的存储区，是针对其他通信机制运行效率较低而设计的。使得多个进程可以访问同一块内存空间，是最快的可用IPC形式。往往与其它通信机制，如信号量结合使用，来达到进程间的同步及互斥。

信号量（semaphore）：主要作为进程间以及同一进程不同线程之间的同步手段。

套接口（Socket）：更为一般的进程间通信机制，可用于不同机器之间的进程间通信。起初是由Unix系统的BSD分支开发出来的，但现在一般可以移植到其它类Unix系统上。

消息队列(MessageQueue)是一个结构化的排序内存段表，这个队列是进程存放或检索数据的地方，是一个消息的链表，可以被多个进程所共享。

（2）列举一种死锁发生的场景，并给出解决方案。

答：最经典的场景就是生产者/消费者，生产者线程生产物品，然后将物品放置在一个空缓冲区中供消费者线程消费。消费者线程从缓冲区中获得物品，然后释放缓冲区。由于生产者/消费者都在操作缓冲区，容易导致死锁的发生。

可以通过添加锁的保护来对缓冲区进行互斥的访问，保证某一时刻只有一个线程对缓冲区进行操作，当缓冲区满的时候，生产者线程就会挂起，同时通知消费者线程。而缓冲区空的时候，消费者线程就会挂起，同时通知生产者线程。

（4）举例说明什么是MVC。

答：MVC是一个设计模式，它强制性的使应用程序的输入、处理和输出分开。使用MVC应用程序被分成三个核心部件：模型、视图、控制器。它们各自处理自己的任务。

视图是用户看到并与之交互的界面。对老式的Web应用程序来说，视图就是由HTML元素组成的界面，在新式的Web应用程序中，HTML依旧在视图中扮演着重要的角色，作为视图来讲，它只是作为一种输出数据并允许用户操纵的方式。

模型表示企业数据和业务规则。在MVC的三个部件中，模型拥有最多的处理任务。由于应用于模型的代码只需写一次就可以被多个视图重用，所以减少了代码的重复性。

控制器接受用户的输入并调用模型和视图去完成用户的需求。所以当单击Web页面中的超链接和发送HTML表单时，控制器本身不输出任何东西和做任何处理。它只是接收请求并决定调用哪个模型构件去处理请求，然后用确定用哪个视图来显示模型处理返回的数据。

2、爸爸、妈妈、妹妹、小强，至少两个人同一生肖的概率是多少？

A、41/96 B、55/96 C、72/128 D、90/128

5、已知一张员工数据表A的表结构如图，请用一条SQL语句列出所有的工作岗位（JOB字段）的平均工资，并将其按照平均工资用升序排列。

A \{

ENAME VARCHAR(20)

JOB VARCHAR(20)

SALARY NUMBER(5)

select job,avg(salary) ass from a group by job order by s asc;

6、描述在浏览器中敲入一个网址并按下回车后所发生的事情（尽量详细）

答：浏览器输入网址之后，首先

步骤1：需要查找域名的IP地址，DNS查找过程如下：

（1）浏览器缓存–浏览器的缓存DNS记录一段时间。有趣的是，操作系统没有告诉浏览器储存DNS记录的时间，这样不同浏览器会储存各自固定的一个时间（2分钟到30分钟不等）。

（2）系统缓存–如果在浏览器缓存里没有找到需要的记录，浏览器会做一个系统调用（windows里是gethostbyname）。这样便可获得系统缓存中的记录。

（3）路由器缓存–接着，前面的查询请求发向路由器，它一般会有自己的DNS缓存。

（4）ISP (InternetService Provider) DNS 缓存–接下来要check的就是ISP缓存DNS的服务器。在这一般都能找到相应的缓存记录。

（5）递归搜索–你的ISP的DNS服务器从跟域名服务器开始进行递归搜索，从.com顶级域名服务器到Facebook的域名服务器。一般DNS服务器的缓存中会有.com域名服务器中的域名，所以到顶级服务器的匹配过程不是那么必要了。

步骤2：浏览器给web服务器发送一个HTTP请求。请求中也包含浏览器存储的该域名的cookies。可能你已经知道，在不同页面请求当中，cookies是与跟踪一个网站状态相匹配的键值。这样cookies会存储登录用户名，服务器分配的密码和一些用户设置等。Cookies会以文本文档形式存储在客户机里，每次请求时发送给服务器。

步骤3：服务的永久重定向响应

步骤4：浏览器跟踪重定向地址

步骤5：服务器“处理”请求

步骤6：服务器发回一个HTML响应

步骤7：浏览器开始显示HTML

步骤8：浏览器发送获取嵌入在HTML中的对象

1.语法解析网址，如果你的网址不合法则抛异常，比如

你录入 http://www.baidu.com 浏览器就调用http协议

录入ftp://ftp.tsinghua.edu.cn 浏览器就调用ftp协议

录入浏览器不识别的协议则报错

以下只针对http协议

2.查询cache

网址被分段解析后，浏览器首先在本地缓存查询cache，如果cache被标明是最新的则直接使用缓存内容。

3.DNS解析（可选）

向dns缓存服务(DNS client)或服务器查询域名对应的ip

4.连接服务器（可选）

tcp/ip 握手连接服务器，如果已经有了被保持的连接，则复用此连接（Connection: Keep-Alive）

5.发送http请求

向指定ip发送请求，具体http header定义查看 rfc文档

例如如果本地有cache但不能确定是否是最新的cache则发送

If-Modified-Since 和 If-None-Match 头

6.接收服务器响应

如果服务器响应为重定向（301或302）则浏览器必须取响应的Location ，然后重复1-6步骤。

如果服务器响应为304，则浏览器使用本地cache

如果响应为200，则接收具体的数据。

7.断开同服务器的连接（可选）

如果服务器响应为Connection:Keep-Alive，则需要保持连接，备后继http使用

8.写cache

将可以缓存的内容保存到cache

7.kmp算法：

\#include<iostream>

using namespace std;

void getNext(char \*substr, int \*next)

int len = strlen(substr);

int k = -1;

int j = 0;

next\[0\] = -1;

while (j < len)

if (k == -1 || substr\[j\] == substr\[k\])

k++;

j++;

next\[j\] = k;

else

k = next\[k\];

int strstr(char\* src, char\* substr)

int len = strlen(src);

int lensub = strlen(substr);

int \*next =  new int\[lensub\];

getNext(substr, next);

int i = 0;

int j = 0;

while (i < len)

if (src\[i\] == substr\[j\]||j==-1)

i++;

j++;

else

j = next\[j\];

if (j == lensub)

return i - j;

return \-1;

int main()

char \*src =  "abbcdefgabc";

char \*substr =  "abc";

cout << strstr(src, substr)<< endl;

getchar();

return 0;

2、在操作系统中最常用来被作为存储文件关系的数据结构是（）

A、链表 B、数组 C、堆栈 D、树

5、下列关于一个类的静态成员的描述中，不正确的是（）

A、该类的对象共享其静态成员变量的值

B、静态成员变量可被该类的所有方法访问

C、该类的静态方法只能访问该类的静态成员变量

D、该类的静态数据成员变量的值不可修改

假如我们把整条道路看成是一个【进程】的话，

那么马路中间白色虚线分隔开来的各个车道就是进程中的各个【线程】了。

①这些线程(车道)共享了进程(道路)的公共资源(土地资源)。

②这些线程(车道)必须依赖于进程(道路)，也就是说，线程不能脱离于进程而存在(就像离开了道路，车道也就没有意义了)。

③这些线程(车道)之间可以并发执行(各个车道你走你的，我走我的)，也可以互相同步(某些车道在交通灯亮时禁止继续前行或转弯，必须等待其它车道的车辆通行完毕)。

④这些线程(车道)之间依靠代码逻辑(交通灯)来控制运行，一旦代码逻辑控制有误(死锁，多个线程同时竞争唯一资源)，那么线程将陷入混乱，无序之中。

⑤这些线程(车道)之间谁先运行是未知的，只有在线程刚好被分配到CPU时间片(交通灯变化)的那一刻才能知道

注：

由于用于互斥的信号量sem与所有的并发进程有关，所以称之为公有信号量。公有信号量的值反映了公有资源的数量。只要把临界区置于P(sem)和V(sem)之间，即可实现进程间的互斥。就象火车中的每节车厢只有一个卫生间，该车厢的所有旅客共享这个公有资源：卫生间，所以旅客间必须互斥进入卫生间，只要把卫生间放在P(sem)和V(sem)之间，就可以到达互斥的效果。

进程/线程同步的方式和机制，进程间通信

一、进程/线程间同步机制。

临界区、互斥区、事件、信号量四种方式

临界区（Critical Section）、互斥量（Mutex）、信号量（Semaphore）、事件（Event）的区别

1、临界区：通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。在任意时刻只允许一个线程对共享资源进行访问，如果有多个线程试图访问公共资源，那么在有一个线程进入后，其他试图访问公共资源的线程将被挂起，并一直等到进入临界区的线程离开，临界区在被释放后，其他线程才可以抢占。

2、互斥量：采用互斥对象机制。 只有拥有互斥对象的线程才有访问公共资源的权限，因为互斥对象只有一个，所以能保证公共资源不会同时被多个线程访问。互斥不仅能实现同一应用程序的公共资源安全共享，还能实现不同应用程序的公共资源安全共享 .互斥量比临界区复杂。因为使用互斥不仅仅能够在同一应用程序不同线程中实现资源的安全共享，而且可以在不同应用程序的线程之间实现对资源的安全共享。

3、信号量：它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目 .信号量对象对线程的同步方式与前面几种方法不同，信号允许多个线程同时使用共享资源，这与操作系统中的PV操作相同。它指出了同时访问共享资源的线程最大数目。它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目。

PV操作及信号量的概念都是由荷兰科学家E.W.Dijkstra提出的。信号量S是一个整数，S大于等于零时代表可供并发进程使用的资源实体数，但S小于零时则表示正在等待使用共享资源的进程数。

P操作申请资源：

（1）S减1；

（2）若S减1后仍大于等于零，则进程继续执行；

（3）若S减1后小于零，则该进程被阻塞后进入与该信号相对应的队列中，然后转入进程调度。

V操作释放资源：

（1）S加1；

（2）若相加结果大于零，则进程继续执行；

（3）若相加结果小于等于零，则从该信号的等待队列中唤醒一个等待进程，然后再返回原进程继续执行或转入进程调度。

4、事 件： 通过通知操作的方式来保持线程的同步，还可以方便实现对多个线程的优先级比较的操作 .

总结：

1．互斥量与临界区的作用非常相似，但互斥量是可以命名的，也就是说它可以跨越进程使用。所以创建互斥量需要的资源更多，所以如果只为了在进程内部是用的话使用临界区会带来速度上的优势并能够减少资源占用量。因为互斥量是跨进程的互斥量一旦被创建，就可以通过名字打开它。

2．互斥量（Mutex），信号灯（Semaphore），事件（Event）都可以被跨越进程使用来进行同步数据操作，而其他的对象与数据同步操作无关，但对于进程和线程来讲，如果进程和线程在运行状态则为无信号状态，在退出后为有信号状态。所以可以使用WaitForSingleObject来等待进程和线程退出。

3．通过互斥量可以指定资源被独占的方式使用，但如果有下面一种情况通过互斥量就无法处理，比如现在一位用户购买了一份三个并发访问许可的数据库系统，可以根据用户购买的访问许可数量来决定有多少个线程/进程能同时进行数据库操作，这时候如果利用互斥量就没有办法完成这个要求，信号灯对象可以说是一种资源计数器。

二、进程间通信方式

由于比较容易混淆，我们把进程间通信方法也列在这里做比较。

程间通信就是在不同进程之间传播或交换信息，那么不同进程之间存在着什么双方都可以访问的介质呢？进程的用户空间是互相独立的，一般而言是不能互相访问的，唯一的例外是共享内存区。但是，系统空间却是“公共场所”，所以内核显然可以提供这样的条件。除此以外，那就是双方都可以访问的外设了。在这个意义上，两个进程当然也可以通过磁盘上的普通文件交换信息，或者通过“注册表”或其它数据库中的某些表项和记录交换信息。广义上这也是进程间通信的手段，但是一般都不把这算作“进程间通信”。因为那些通信手段的效率太低了，而人们对进程间通信的要求是要有一定的实时性。

进程间通信主要包括管道, 系统IPC(包括消息队列,信号量,共享存储), SOCKET.

管道分为有名管道和无名管道，无名管道只能用于亲属进程之间的通信，而有名管道则可用于无亲属关系的进程之间。

消息队列用于运行于同一台机器上的进程间通信，与管道相似；

共享内存通常由一个进程创建，其余进程对这块内存区进行读写。得到共享内存有两种方式：映射/dev/mem设备和内存映像文件。前一种方式不给系统带来额外的开销，但在现实中并不常用，因为它控制存取的是实际的物理内存；

本质上，信号量是一个计数器，它用来记录对某个资源（如共享内存）的存取状况。一般说来，为了获得共享资源，进程需要执行下列操作：

（1）测试控制该资源的信号量；

（2）若此信号量的值为正，则允许进行使用该资源，进程将进号量减1；

（3）若此信号量为0，则该资源目前不可用，进程进入睡眠状态，直至信号量值大于0，进程被唤醒，转入步骤（1）；

（4）当进程不再使用一个信号量控制的资源时，信号量值加1，如果此时有进程正在睡眠等待此信号量，则唤醒此进程。

套接字通信并不为Linux所专有，在所有提供了TCP/IP协议栈的操作系统中几乎都提供了socket，而所有这样操作系统，对套接字的编程方法几乎是完全一样的

三、进程/线程同步机制与进程间通信机制比较

很明显2者有类似，但是差别很大

同步主要是临界区、互斥、信号量、事件

进程间通信是管道、内存共享、消息队列、信号量、socket

共通之处是，信号量和消息（事件）

其他资料：

进程间通讯(IPC)方法主要有以下几种：

管道/FIFO/共享内存/消息队列/信号

1.管道中还有命名管道和非命名管道(即匿名管道)之分，非命名管道(即匿名管道)只能用于父子进程通讯，命名管道可用于非父子进程，命名管道就是FIFO，管道是先进先出的通讯方式

2.消息队列是用于两个进程之间的通讯，首先在一个进程中创建一个消息队列，然后再往消息队列中写数据，而另一个进程则从那个消息队列中取数据。需要注意的是，消息队列是用创建文件的方式建立的，如果一个进程向某个消息队列中写入了数据之后，另一个进程并没有取出数据，即使向消息队列中写数据的进程已经结束，保存在消息队列中的数据并没有消失，也就是说下次再从这个消息队列读数据的时候，就是上次的数据！！！！

3.信号量，它与WINDOWS下的信号量是一样的，所以就不用多说了

4.共享内存，类似于WINDOWS下的DLL中的共享变量，但LINUX下的共享内存区不需要像DLL这样的东西，只要首先创建一个共享内存区，其它进程按照一定的步骤就能访问到这个共享内存区中的数据，当然可读可写

以上几种方式的比较：

1.管道：速度慢，容量有限，只有父子进程能通讯

2.FIFO：任何进程间都能通讯，但速度慢

3.消息队列：容量受到系统限制，且要注意第一次读的时候，要考虑上一次没有读完数据的问题

4.信号量：不能传递复杂消息，只能用来同步

5.共享内存区：能够很容易控制容量，速度快，但要保持同步，比如一个进程在写的时候，另一个进程要注意读写的问题，相当于线程中的线程安全，当然，共享内存区同样可以用作线程间通讯，不过没这个必要，线程间本来就已经共享了同一进程内的一块内存

6、操作系统中，以下哪种方式无法实现进程同步？

A、Ctitical Section B、Mutex C、Semaphore D、Event

11、下列代码运行后，result的值是多少（）

List<int> ints = new List<int>()\{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15\};

var query = from i in ints

where i%2 == 0 || i%3 == 0

select i;

ints.RemoveAt(1);

int result = query.Count();

A、7 B、8 C、9 D、10

13、在.NET中，char类型占几个字节（）

A、1 B、2 C、4 D、运行时根据平台确定

14、下列哪个是C\#中运行时常量的定义方法（）

A、public static readonly int Port = 47896

B、public const intPort = 47896

C、public static constint Port = 47896

D、public static sealedint Port = 47896

16、下面的代码发生了多少次装箱操作（）

String.Format("\{0\}:\{1\} , \{2\} , \{3\}\}" ,2012 , 1.ToString() , "2" , DateTime.Now);

A、1 B、2 C、3  D、4

呵呵，你说的强制转换就包含有装箱拆箱操作的，装箱就是把值类型转换成引用类型，反之就是拆箱。举个简单的例子：

int i=5;

object o=i;装箱

int j=(int)o;拆箱

15、在C\#中类的默认访问级别是什么（该类不是内部类）（）

A、internal  B、public C、protectedinternal D、private

1、 已知memcpy的函数为： void\*memcpy(void \*dest , const void\* src , size\_t count)其中dest是目的指针，src是源指针。不调用c++/c的memcpy库函数，请编写memcpy。

\#include<iostream>

\#include<assert.h>

using namespace std;

void\* memcpy1(void \*dest, const void\* src,size\_t count)

assert(dest!= NULL&&src != NULL);

assert(count>= 0);

char\*pdest = (char\*)dest;

char\*psrc = (char\*)src;

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

\*(pdest++)= \*(psrc++);

returndest;

int main()

charsrc\[\] = "abbcdefgabc";

char\*substr = "1234";

cout<< (char\*)memcpy1(src,substr,3) << endl;

getchar();

return0;

1、用适当的方法统计出下面字符串中出现次数最多的字符，已知字符串为：

Welcome to our company Software EngineerRecruitment Examination.

\#include<iostream>

\#include<assert.h>

using namespace std;

char MostTimes(char\* str)

inthash\[255\];

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

hash\[i\]= 0;

while(\*str != '\\0')

if(\*str >= 'a'&&\*str <= 'z' || \*str >= 'A'&&\*str <='Z')

hash\[\*str\]++;

str++;

intmax = 0;

charx;

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

if(hash\[i\]>max)

max= hash\[i\];

x= i;

returnx;

int main()

charsrc\[\] = "Welcome to our company Software Engineer RecruitmentExamination.";

char\*substr = "1234";

cout<< MostTimes(src) << endl;

getchar();

return0;

题目一：子串分离

题目描述：

通过键盘输入任意一个字符串序列，字符串可能包含多个子串，子串以空格分隔。请编写一个程序，自动分离出各个子串，并使用’,’将其分隔，并且在最后也补充一个’,’并将子串存储。

如果输入“abc def gh i d”，结果将是abc,def,gh,i,d,

要求实现函数：

void DivideString(const char \*pInputStr,long lInputLen, char \*pOutputStr);

【输入】 pInputStr： 输入字符串

lInputLen： 输入字符串长度

【输出】 pOutputStr： 输出字符串，空间已经开辟好，与输入字符串等长；

【注意】只需要完成该函数功能算法，中间不需要有任何IO 的输入输出

示例

输入：“abc def gh i d”

输出：“abc,def,gh,i,d,”

\#include<iostream>

\#include<assert.h>

using namespace std;

void DivideString(const char \*pInputStr,long lInputLen, char \*pOutputStr)

inti=0;

while(\*pInputStr != '\\0')

if(\*pInputStr != ' ')

pOutputStr\[i++\]= \*pInputStr;

elseif (\*pInputStr == ' '&&\*(pInputStr - 1) != ' ')

pOutputStr\[i++\]= ',';

pInputStr++;

if(pOutputStr\[i - 1\] != ',')

pOutputStr\[i++\]= ',';

pOutputStr\[i\]= '\\0';

int main()

char\*src = "abc def gh i d ";

char\*substr = "1234";

intn = strlen(src);

char\*pOutputStr = new char\[n+1\];

DivideString(src,n, pOutputStr);

cout<< pOutputStr << endl;

getchar();

return0;

题目二：逆序链表输出。

题目描述：

将输入的一个单向链表，逆序后输出链表中的值。链表定义如下：

typedef struct tagListNode

int value;

struct tagListNode \*next;

\}ListNode;

要求实现函数：

void converse(ListNode \*\*head);

【输入】head： 链表头节点，空间已经开辟好

【输出】head： 逆序后的链表头节点

【返回】无

\#include<iostream>

\#include<assert.h>

using namespace std;

typedef struct tagListNode

intvalue;

structtagListNode \*next;

\}ListNode;

void converse(ListNode \*\*head)

ListNode\*p;

ListNode\*q;

ListNode\*r;

p= (\*head)->next;

q= p->next;

r= q->next;

p->next= NULL;

while(q != NULL)

q->next= p;

p= q;

q= r;

if(r == NULL)

continue;

r= r->next;

(\*head)->next = p;

int main()

ListNode\*head = new ListNode;

head->value= -1;

head->next= NULL;

ListNode\*p = head;

ListNode\*q;

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

q= new ListNode;

q->value= i;

q->next= NULL;

p->next= q;

p= q;

p= head->next;

while(p != NULL)

cout<< p->value << endl;

p= p->next;

converse(&head);

p=head->next;

while(p != NULL)

cout<< p->value << endl;

p= p->next;

getchar();

return0;

socket过程就是socket的server和client整个流程写下来。

解：

sockets（套接字）编程有三种，流式套接字（SOCK\_STREAM），数据报套接字（SOCK\_DGRAM），原始套接字（SOCK\_RAW）；基于TCP的socket编程是采用的流式套接字。

服务器端编程的步骤：

1：加载套接字库，创建套接字(WSAStartup()/socket())；

2：绑定套接字到一个IP地址和一个端口上(bind())；

3：将套接字设置为监听模式等待连接请求(listen())；

4：请求到来后，接受连接请求，返回一个新的对应于此次连接的套接字(accept())；

5：用返回的套接字和客户端进行通信(send()/recv())；

6：返回，等待另一连接请求；

7：关闭套接字，关闭加载的套接字库(closesocket()/WSACleanup())。

客户端编程的步骤：

1：加载套接字库，创建套接字(WSAStartup()/socket())；

2：向服务器发出连接请求(connect())；

3：和服务器端进行通信(send()/recv())；

4：关闭套接字，关闭加载的套接字库(closesocket()/WSACleanup())。

第一式: 加载/释放Winsock库:

1.加载方法:

WSADATA wsa;

/\*初始化socket资源\*/

if (WSAStartup(MAKEWORD(1,1),&wsa) !=0)

return; //代表失败

2.释放方法:

WSACleanup();

第二式: 构造SOCKET:

1.服务端:构造监听SOCKET,流式SOCKET.

SOCKET Listen\_Sock = socket(AF\_INET, SOCK\_STREAM, 0)

2.客户端:构造通讯SOCKET,流式SOCKET.

SOCKET Client\_Sock = socket(AF\_INET,SOCK\_STREAM, 0)

第三式:配置监听地址和端口:

1.服务端: SOCKADDR\_INserverAddr

ZeroMemory((char\*)&serverAddr,sizeof(serverAddr));

serverAddr.sin\_family = AF\_INET;

serverAddr.sin\_port = htons(1234); /\*本地监听端口:1234\*/

serverAddr.sin\_addr.s\_addr = htonl(INADDR\_ANY); /\*有IP\*/

第四式: 绑定SOCKET:

1.服务端:绑定监听SOCKET.

bind(Listen\_Sock,(struct sockaddr \*)&serverAddr,sizeof(serverAddr))

第五式: 服务端/客户端连接:

1.服务端:等待客户端接入.

SOCKET Command\_Sock = accept(Listen\_Sock, ...)

2.客户端:请求与服务端连接.

int ret = connect(Client\_Sock, ...)

第六式: 收/发数据:

1.服务端:等待客户端接入.charbuf\[1024\].

接收数据:recv(Command\_Sock,buf,...)

或

发送数据:send(Command\_Sock,buf,...)

2.客户端:请求与服务端连接.charbuf\[1024\].

发送数据:send(Client\_Sock,buf,...)

或

接收数据:recv(Client\_Sock,buf,...)

第七式: 关闭SOCKET:

1.服务端:关闭SOCKET.

closesocket(Listen\_Sock)

closesocket(Command\_Sock)

2.客户端:关闭SOCKET.

closesocket(Client\_Sock)

\#include <stdio.h>

\#include <Winsock2.h>

void main()

WORDwVersionRequested;

WSADATA wsaData;

interr;

wVersionRequested = MAKEWORD( 1, 1 );

err= WSAStartup( wVersionRequested, &wsaData );

if (err != 0 ) \{

return;

if (LOBYTE( wsaData.wVersion ) != 1 ||

HIBYTE( wsaData.wVersion ) != 1 ) \{

WSACleanup( );

return;

SOCKET sockSrv=socket(AF\_INET,SOCK\_STREAM,0);

SOCKADDR\_IN addrSrv;

addrSrv.sin\_addr.S\_un.S\_addr=htonl(INADDR\_ANY);

addrSrv.sin\_family=AF\_INET;

addrSrv.sin\_port=htons(6000);

bind(sockSrv,(SOCKADDR\*)&addrSrv,sizeof(SOCKADDR));

listen(sockSrv,5);

SOCKADDR\_IN addrClient;

intlen=sizeof(SOCKADDR);

while(1)

SOCKET sockConn=accept(sockSrv,(SOCKADDR\*)&addrClient,&len);

char sendBuf\[50\];

sprintf(sendBuf,"Welcome %s tohere!",inet\_ntoa(addrClient.sin\_addr));

send(sockConn,sendBuf,strlen(sendBuf)+1,0);

char recvBuf\[50\];

recv(sockConn,recvBuf,50,0);

printf("%s\\n",recvBuf);

closesocket(sockConn);

\#include <stdio.h>

\#include <Winsock2.h>

void main()

WORDwVersionRequested;

WSADATA wsaData;

interr;

wVersionRequested = MAKEWORD( 1, 1 );

err= WSAStartup( wVersionRequested, &wsaData );

if (err != 0 ) \{

return;

if (LOBYTE( wsaData.wVersion ) != 1 ||

HIBYTE( wsaData.wVersion ) != 1 ) \{

WSACleanup( );

return;

SOCKET sockClient=socket(AF\_INET,SOCK\_STREAM,0);

SOCKADDR\_IN addrSrv;

addrSrv.sin\_addr.S\_un.S\_addr=inet\_addr("127.0.0.1");

addrSrv.sin\_family=AF\_INET;

addrSrv.sin\_port=htons(6000);

connect(sockClient,(SOCKADDR\*)&addrSrv,sizeof(SOCKADDR));

send(sockClient,"hello",strlen("hello")+1,0);

charrecvBuf\[50\];

recv(sockClient,recvBuf,50,0);

printf("%s\\n",recvBuf);

closesocket(sockClient);

WSACleanup();

对TCP/IP、UDP、Socket编程这些词你不会很陌生吧？随着网络技术的发展，这些词充斥着我们的耳朵。那么我想问：  
  
1. 什么是TCP/IP、UDP？  
2. Socket在哪里呢？  
3. Socket是什么呢？  
4. 你会使用它们吗？  
  
**什么是TCP/IP、UDP？**

TCP/IP（Transmission Control Protocol/Internet Protocol）即传输控制协议/网间协议，是一个工业标准的协议集，它是为广域网（WANs）设计的。  
UDP（User Data Protocol，用户数据报协议）是与TCP相对应的协议。它是属于TCP/IP协议族中的一种。  
这里有一张图，表明了这些协议的关系。  
  
  
  
图1

TCP/IP协议族包括运输层、网络层、链路层。现在你知道TCP/IP与UDP的关系了吧。  
**Socket在哪里呢？**  
在图1中，我们没有看到Socket的影子，那么它到底在哪里呢？还是用图来说话，一目了然。

图2

原来Socket在这里。  
**Socket是什么呢？**  
 Socket是应用层与TCP/IP协议族通信的中间软件抽象层，它是一组接口。在设计模式中，Socket其实就是一个门面模式，它把复杂的TCP/IP协议族隐藏在Socket接口后面，对用户来说，一组简单的接口就是全部，让Socket去组织数据，以符合指定的协议。  
**你会使用它们吗？**  
前人已经给我们做了好多的事了，网络间的通信也就简单了许多，但毕竟还是有挺多工作要做的。以前听到Socket编程，觉得它是比较高深的编程知识，但是只要弄清Socket编程的工作原理，神秘的面纱也就揭开了。  
一个生活中的场景。你要打电话给一个朋友，先拨号，朋友听到电话铃声后提起电话，这时你和你的朋友就建立起了连接，就可以讲话了。等交流结束，挂断电话结束此次交谈。 生活中的场景就解释了这工作原理，也许TCP/IP协议族就是诞生于生活中，这也不一定。

图3

先从服务器端说起。服务器端先初始化Socket，然后与端口绑定(bind)，对端口进行监听(listen)，调用accept阻塞，等待客户端连接。在这时如果有个客户端初始化一个Socket，然后连接服务器(connect)，如果连接成功，这时客户端与服务器端的连接就建立了。客户端发送数据请求，服务器端接收请求并处理请求，然后把回应数据发送给客户端，客户端读取数据，最后关闭连接，一次交互结束。  
在这里我就举个简单的例子，我们走的是TCP协议这条路（见图2）。例子用MFC编写，运行的界面如下：

图4

图5

在客户端输入服务器端的IP地址和发送的数据，然后按发送按钮，服务器端接收到数据，然后回应客户端。客户端读取回应的数据，显示在界面上。  
下面是接收数据和发送数据的函数：

int Receive(SOCKETfd,char \*szText,int len)

\{  
int cnt;  
int rc;  
cnt=len;

while(cnt>0)  
\{  
rc=recv(fd,szText,cnt,0);  
if(rc==SOCKET\_ERROR)  
\{  
return-1;  
\}

if(rc==0)

returnlen-cnt;

szText+=rc;

cnt-=rc;

returnlen;

\}  
  
int Send(SOCKET fd,char \*szText,int len)  
\{

intcnt;

intrc;

cnt=len;

while(cnt>0)

rc=send(fd,szText,cnt,0);

if(rc==SOCKET\_ERROR)

return-1;

if(rc==0)

returnlen-cnt;

szText+=rc;

cnt-=rc;

returnlen;

**服务器端：**

在服务器端，主要是启动Socket和监听线程。

\#defineDEFAULT\_PORT 2000

voidCServerDlg::OnStart()

sockaddr\_inlocal;

DWORD dwThreadID= 0;

local.sin\_family=AF\_INET;

//设置的端口为DEFAULT\_PORT。

local.sin\_port=htons(DEFAULT\_PORT);

//IP地址设置成INADDR\_ANY,让系统自动获取本机的IP地址。

local.sin\_addr.S\_un.S\_addr=INADDR\_ANY;

//初始化Socket

m\_Listening= socket(AF\_INET,SOCK\_STREAM,0);

if(m\_Listening== INVALID\_SOCKET)

return;

//将本地地址绑定到所创建的套接字上

if(bind(m\_Listening,(LPSOCKADDR)&local,sizeof(local))== SOCKET\_ERROR )

closesocket(m\_Listening);

return;

//创建监听线程，这样也能响应界面上操作。

m\_hListenThread= ::CreateThread(NULL,0,ListenThread,this,0,&dwThreadID);

m\_StartBtn.EnableWindow(FALSE);

m\_StopBtn.EnableWindow(TRUE);

\}  
  
监听线程函数：  
DWORD WINAPI CServerDlg::ListenThread(LPVOID lpparam)  
\{

CServerDlg\*pDlg = (CServerDlg\*)lpparam;

if(pDlg== NULL)

return0;

SOCKET Listening= pDlg->m\_Listening;

//开始监听是否有客户端连接。

if(listen(Listening,40)== SOCKET\_ERROR)

return0;

charszBuf\[MAX\_PATH\];

//初始化

memset(szBuf,0,MAX\_PATH);

while(1)

SOCKETConnectSocket;

sockaddr\_in ClientAddr;

int nLen= sizeof(sockaddr);

//阻塞直到有客户端连接，不然多浪费CPU资源。

ConnectSocket= accept(Listening,(sockaddr\*)&ClientAddr,&nLen);

//都到客户端的IP地址。

char\*pAddrname = inet\_ntoa(ClientAddr.sin\_addr);

pDlg->Receive(ConnectSocket,szBuf,100);

//界面上显示请求数据。

pDlg->SetRequestText(szBuf);

strcat(szBuf,":我是老猫，收到（");

strcat(szBuf,pAddrname);

strcat(szBuf,"）");

//向客户端发送回应数据

pDlg->Send(ConnectSocket,szBuf,100);

return0;

服务器端一直在监听是否有客户端连接，如有连接，处理客户端的请求，给出回应，然后继续监听。

**客户端：**

客户端的发送函数：

\#defineDEFAULT\_PORT 2000

void CClientDlg::OnSend()

DWORD dwIP= 0;

TCHARszText\[MAX\_PATH\];

memset(szText,0,MAX\_PATH);

m\_IP.GetWindowText(szText,MAX\_PATH);

//把字符串形式的IP地址转成IN\_ADDR结构需要的形式。

dwIP= inet\_addr(szText);

m\_RequestEdit.GetWindowText(szText,MAX\_PATH);

sockaddr\_inlocal;

SOCKETsocketTmp;

//必须是AF\_INET,表示该socket在Internet域中进行通信

local.sin\_family=AF\_INET;

//端口号

local.sin\_port=htons(DEFAULT\_PORT);

//服务器的IP地址。

local.sin\_addr.S\_un.S\_addr=dwIP;

初始化Socket

socketTmp=socket(AF\_INET,SOCK\_STREAM,0);

//连接服务器

if(connect(socketTmp,(LPSOCKADDR)&local,sizeof(local))< 0)

closesocket(socketTmp);

MessageBox("连接服务器失败。");

return;

//发送请求，为简单只发100字节，在服务器端也规定100字节。

Send(socketTmp,szText,100);

//读取服务器端返回的数据。

memset(szText,0,MAX\_PATH);

//接收服务器端的回应。

Receive(socketTmp,szText,100);

TCHARszMessage\[MAX\_PATH\];

memset(szMessage,0,MAX\_PATH);

strcat(szMessage,szText);

//界面上显示回应数据。

m\_ReplyBtn.SetWindowText(szMessage);

closesocket(socketTmp);

客户端就一个函数完成了一次通信。在这里IP地址为何用127.0.0.1呢？使用这个IP地址，服务器端和客户端就能运行在同一台机器上，这样调试方便多了。当然你可以在你朋友的机器上运行Server程序(本人在局域网中测试过)，在自己的机器上运行Client程序，当然输入的IP地址就该是你朋友机器的IP地址了。  
简单的理论和实践都说了，现在Socket编程不神秘了吧？希望对你有些帮助。

数据结构二叉树的遍历，给了个二叉树，前序、中序、后序、层次写出来。

void PreOrder(BiTNode \*root)

if(root==NULL)

return ;

printf("%c ", root->data); //输出数据

PreOrder(root->lchild); //递归调用，前序遍历左子树

PreOrder(root->rchild); //递归调用，前序遍历右子树

//中序遍历的算法程序

void InOrder(BiTNode \*root)

if(root==NULL)

return ;

InOrder(root->lchild); //递归调用，前序遍历左子树

printf("%c ", root->data); //输出数据

InOrder(root->rchild); //递归调用，前序遍历右子树

//后序遍历的算法程序

void PostOrder(BiTNode \*root)

if(root==NULL)

return ;

PostOrder(root->lchild); //递归调用，前序遍历左子树

PostOrder(root->rchild); //递归调用，前序遍历右子树

printf("%c ", root->data); //输出数据

int visit(BiTree T)

if(T)

printf("%c ",T->data);

return 1;

else

return 0;

void LeverTraverse(BiTree T) //非递归层次遍历二叉树

queue <BiTree> Q;

BiTree p;

p= T;

if(visit(p)==1)

Q.push(p);

while(!Q.empty())

p = Q.front();

Q.pop();

if(visit(p->lchild) == 1)

Q.push(p->lchild);

if(visit(p->rchild) == 1)

Q.push(p->rchild);

5、两圆相切转圏问题——一个小圆半径是1厘米，一个大圆半径是5厘米，小圆沿着大圆转圈，请问要转几圈可以转完大圈？这个问题在行测题做过，就是公转自转的问题，不管大小圆半径是多少，外切转圏要转R/r+1圏，内切转圏转R/r-1圈。

注：小圆在大圆外时，自转方向和公转方向相同，所以转了R/r+1;小圆在大圆内时，自转方向和公转方向不同，所以转了R/r-1。

1、 二叉树的前序遍历的递归和非递归的可执行程序

//前序遍历的算法程序

void PreOrder(BiTNode \*root)

if(root==NULL)

return ;

printf("%c ", root->data); //输出数据

PreOrder(root->lchild); //递归调用，前序遍历左子树

PreOrder(root->rchild); //递归调用，前序遍历右子树

/\*

二叉树的非递归前序遍历，前序遍历思想：先让根进栈，只要栈不为空，就可以做弹出操作，

每次弹出一个结点，记得把它的左右结点都进栈，记得右子树先进栈，这样可以保证右子树在栈中总处于左子树的下面。

\*/

void PreOrder\_Nonrecursive(BiTree T) //先序遍历的非递归

if(!T)

return ;

stack<BiTree> s;

s.push(T);

while(!s.empty())

BiTree temp = s.top();

cout<<temp->data<<" ";

s.pop();

if(temp->rchild)

s.push(temp->rchild);

if(temp->lchild)

s.push(temp->lchild);

快速排序的实现代码：

void QuickSort(int \*a, int left,intright)

if (left > right)

return;

int x = a\[left\];

int i = left;

int j = right;

while (i < j)

while (i<j&&a\[j\] > x)

j--;

if (i < j)

a\[i++\] = a\[j\];

while (i<j&&a\[i\] < x)

i++;

if (i < j)

a\[j--\] = a\[i\];

a\[i\] = x;

QuickSort(a,left,i-1);

QuickSort(a,i+1, right);

字符串拼接函数的实现strcat()

\#include <iostream>

\#include <assert.h>

using namespace std;

//连接字符串

char\* mystrcat(char\* destStr, const char\* srcStr) //如果两个字符串是同一个字符串呢？

assert(destStr != NULL &&srcStr != NULL);

char\* temp = destStr;

while (\*destStr !=  '\\0')

\++destStr;

while (\*srcStr!='\\0')

\*destStr++ = \*srcStr++;

\*destStr = '\\0';

return temp;  //为了实现链式操作，将目的地址返回

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

char str1\[25\] =  "Hello world";

char str2\[\] =  "Hello World";

cout << mystrcat(str1,str2) << endl;

getchar();

return 0;

大数相乘

\#include<iostream>

using namespace std;

const int N = 100;

void getdigital(char \*s1, int \*a)

int len=strlen(s1);

for (int i = len - 1,j=0; i >= 0; i--,j++)

a\[j\] = s1\[i\]-'0';

char \*multiple(char \*s1, char \*s2, char \*s3)

int a\[N\];

int b\[N\];

int c\[2 \* N\];

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

a\[i\] = 0;

b\[i\] = 0;

c\[i\] = 0;

for (int i = N; i < 2\*N; i++)

c\[i\] = 0;

getdigital(s1,a);

getdigital(s2, b);

for (int i = 0; a\[i\] !=0; i++)

for (int j = 0; b\[j\]!=0; j++)

c\[i + j\] += a\[i\] \* b\[j\];

int i = 0;

for (i = 0; c\[i\] != 0; i++)

c\[i + 1\] += c\[i\] / 10;

c\[i\] = c\[i\] % 10;

if (c\[i\] != 0)

i++;

s3\[i\] = '\\0';

i--;

for (int j = 0; i>=0;j++,i--)

s3\[j\] = c\[i\] + '0';

return s3;

int main()

char s1\[N\];

char s2\[N\];

char s3\[2 \* N\];

cin >> s1;

cin >> s2;

cout<<multiple(s1, s2,s3)<<endl;

getchar();

return 0;

归并排序的实现

\#include<iostream>

using namespace std;

const int N = 100;

void getdigital(char \*s1, int \*a)

intlen=strlen(s1);

for(int i = len - 1,j=0; i >= 0; i--,j++)

a\[j\]= s1\[i\]-'0';

char \*multiple(char \*s1, char \*s2, char\*s3)

inta\[N\];

intb\[N\];

intc\[2 \* N\];

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

a\[i\]= 0;

b\[i\]= 0;

c\[i\]= 0;

for(int i = N; i < 2\*N; i++)

c\[i\]= 0;

getdigital(s1,a);

getdigital(s2,b);

for(int i = 0; a\[i\] !=0; i++)

for(int j = 0; b\[j\]!=0; j++)

c\[i+ j\] += a\[i\] \* b\[j\];

inti = 0;

for(i = 0; c\[i\] != 0; i++)

c\[i+ 1\] += c\[i\] / 10;

c\[i\]= c\[i\] % 10;

if(c\[i\] != 0)

i++;

s3\[i\]= '\\0';

i--;

for(int j = 0; i>=0;j++,i--)

s3\[j\]= c\[i\] + '0';

returns3;

int main()

chars1\[N\];

chars2\[N\];

chars3\[2 \* N\];

cin>> s1;

cin>> s2;

cout<<multiple(s1,s2, s3)<<endl;

getchar();

return0;

4、文件按a~z编号，aa~az,ba~bz...za...zz...aaa...aaz,aba~abz...这样的方法进行编号。给定任意一个编号，输出文件是第几个文件。并写出测试方法。简单，把编号看成26进制，这题就是一个十进制和26进制的进制转换问题了。

\#include<iostream>

\#include<cmath>

using namespace std;

int convert26to10(char \*a, int &n)

n= 0;

intlen = strlen(a);

int\*b = new int\[len\];

for(int i = 0,j=len-1; i < len; i++,j--)

b\[i\]= a\[j\] - 'a';

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

n+= b\[i\] \* pow(26, i);

n++;

returnn;

int main()

chara\[\] = "ace";

intn;

convert26to10(a,n);

cout<< n << endl;

getchar();

数据库中的索引

使用索引可快速访问数据库表中的特定信息。索引是对数据库表中一列或多列的值进行排序的一种结构，例如 employee 表的姓（lname）列。如果要按姓查找特定职员，与必须搜索表中的所有行相比，索引会帮助您更快地获得该信息。

索引提供指向存储在表的指定列中的数据值的指针，然后根据您指定的排序顺序对这些指针排序。数据库使用索引的方式与您使用书籍中的索引的方式很相似：它搜索索引以找到特定值，然后顺指针找到包含该值的行。

在数据库关系图中，您可以在选定表的“索引/键”属性页中创建、编辑或删除每个索引类型。当保存索引所附加到的表，或保存该表所在的关系图时，索引将保存在数据库中。有关详细信息，请参见创建索引。

注意;并非所有的数据库都以相同的方式使用索引。有关更多信息，请参见数据库服务器注意事项，或者查阅数据库文档。

作为通用规则，只有当经常查询索引列中的数据时，才需要在表上创建索引。索引占用磁盘空间，并且降低添加、删除和更新行的速度。在多数情况下，索引用于数据检索的速度优势大大超过它的。

索引列

可以基于数据库表中的单列或多列创建索引。多列索引使您可以区分其中一列可能有相同值的行。

如果经常同时搜索两列或多列或按两列或多列排序时，索引也很有帮助。例如，如果经常在同一查询中为姓和名两列设置判据，那么在这两列上创建多列索引将很有意义。

确定索引的有效性：

检查查询的 WHERE 和 JOIN 子句。在任一子句中包括的每一列都是索引可以选择的对象。

对新索引进行试验以检查它对运行查询性能的影响。

考虑已在表上创建的索引数量。最好避免在单个表上有很多索引。

检查已在表上创建的索引的定义。最好避免包含共享列的重叠索引。

检查某列中唯一数据值的数量，并将该数量与表中的行数进行比较。比较的结果就是该列的可选择性，这有助于确定该列是否适合建立索引，如果适合，确定索引的类型。

索引类型

根据数据库的功能，可以在数据库设计器中创建三种索引：唯一索引、主键索引和聚集索引。有关数据库所支持的索引功能的详细信息，请参见数据库文档。

提示：尽管唯一索引有助于定位信息，但为获得最佳性能结果，建议改用主键或唯一约束。

唯一索引

唯一索引是不允许其中任何两行具有相同索引值的索引。

当现有数据中存在重复的键值时，大多数数据库不允许将新创建的唯一索引与表一起保存。数据库还可能防止添加将在表中创建重复键值的新数据。例如，如果在 employee 表中职员的姓 (lname) 上创建了唯一索引，则任何两个员工都不能同姓。

主键索引

数据库表经常有一列或列组合，其值唯一标识表中的每一行。该列称为表的主键。

在数据库关系图中为表定义主键将自动创建主键索引，主键索引是唯一索引的特定类型。该索引要求主键中的每个值都唯一。当在查询中使用主键索引时，它还允许对数据的快速访问。

聚集索引

在聚集索引中，表中行的物理顺序与键值的逻辑（索引）顺序相同。一个表只能包含一个聚集索引。

如果某索引不是聚集索引，则表中行的物理顺序与键值的逻辑顺序不匹配。与非聚集索引相比，聚集索引通常提供更快的数据访问速度。

关系数据库用得数据结构是什么类型的数据结构

二维表

数据库索引优缺点

创建索引可以大大提高系统的性能:

第一，通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。

第二，可以大大加快数据的检索速度，这也是创建索引的最主要的原因。

第三，可以加速表和表之间的连接，特别是在实现数据的参考完整性方面特别有意义。

第四，在使用分组和排序子句进行数据检索时，同样可以显著减少查询中分组和排序的时间。

第五，通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。

增加索引也有许多不利的方面:

第一，创建索引和维护索引要耗费时间，这种时间随着数据量的增加而增加。

第二，索引需要占物理空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，如果要建立聚簇索引，那么需要的空间就会更大。

第三，当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，这样就降低了数据的维护速度。

索引是建立在数据库表中的某些列的上面。因此，在创建索引的时候，应该仔细考虑在哪些列上可以创建索引，在哪些列上不能创建索引。一般来说，应该在这些列上创建索引，例如：

在经常需要搜索的列上，可以加快搜索的速度；

在作为主键的列上，强制该列的唯一性和组织表中数据的排列结构；

在经常用在连接的列上，这些列主要是一些外键，可以加快连接的速度；

在经常需要根据范围进行搜索的列上创建索引，因为索引已经排序，其指定的范围是连续的；

在经常需要排序的列上创建索引，因为索引已经排序，这样查询可以利用索引的排序，加快排序查询时间；

在经常使用在WHERE子句中的列上面创建索引，加快条件的判断速度。

session、cookie和cache的区别是什么

通俗的说：这三个都是用来保存数据的

session把数据保存在服务器端，每一个用户都有属于自己的Session，与别人的不冲突

就是说，你登陆系统后，你的信息（如账号、密码等）就会被保存在服务器上一个单独的session中，当你退出系统后服务器就会丢掉这个session，你的数据也就没了，必须再次登陆，如果登陆超时也会被丢掉，要看人家系统是怎么设置的了

Cookie同session一样是保存你个人信息的，不过是保存在客户端，也就是你使用的电脑上，并且不会被丢掉，除非你删除浏览器Cookie

Cache是保存系统上的信息的，因为从Cache中读数据比较快，所有有些系统（网站）会把一些经常被使用的数据放到Cache里，提高访问速度，优化系统性能

1、Application:用于保存所有用户共用的数据信息。在Asp.Net中类似的配置数据最好保存在Web.config文件中。如果使用Application对象，一个需要考虑的问题是任何写操作都要在Aapplication\_OnStart事件（global.asax)中完成。尽管使用Application.Lock和Application.Unlock方法来避免写操作的同步，但是它串行化了Application对象的请求，当网站访问量大的时候会产生眼中的性能瓶颈。因此对号不要用此对象保存大的数据集。

2、Session:用于保存每个用户的专用信息。Session中的信息保存在web服务器的内存中，保存的数据量可大可小。当session超时或者被关闭是将自动释放保存的数据信息。

3、Cookie:用于保存客户浏览器请求服务器页面的请求信息，其有效期可以人为设置，而且其存储的数据量很受限制，因此不要保存数据集及其他大量数据。而且Cookie以明文方式将数据信息保存在客户端的计算机中，因此最好不要保存敏感的未加密的数据。

4、ViewState:常用于保存单个用户的状态信息，可以保存大量数据但是过多使用会影响应用成勋的性能。所有WEB服务器控件都使用ViewState在页面回发期间保存自己的状态信息。每个控件都有自己的ViewSate,不用时，最好关闭以节省资源。

5、Cache:用于在Http请求间保存页面和数据。它允许将频繁访问的大量服务器资源存储在内存中，当用户发出相同的请求是服务器不再次处理而是将Cache中保存的信息返回给用户，节省了服务器处理请求时间。

6、隐藏域：Hidden控件属于Html类型的服务器控件，可以实现隐藏域的功能，他和其他的控件没什么区别，只是不会再浏览器上显示，始终处于隐藏状态。

7、查询字符串：将传递的值连接在URL后面，然后通过Response.Redirect方法实现客户端的重定向。

Session是由应用服务器维持的一个服务器端的存储空间，用户在连接服务器时，会由服务器生成一个唯一的SessionID,用该SessionID 为标识符来存取服务器端的Session存储空间。而SessionID这一数据则是保存到客户端，用Cookie保存的，用户提交页面时，会将这一 SessionID提交到服务器端，来存取Session数据。这一过程，是不用开发人员干预的。所以一旦客户端禁用Cookie，那么Session也会失效。

服务器也可以通过URL重写的方式来传递SessionID的值，因此不是完全依赖Cookie。如果客户端Cookie禁用，则服务器可以自动通过重写URL的方式来保存Session的值，并且这个过程对程序员透明。

可以试一下，即使不写Cookie，在使用request.getCookies();取出的Cookie数组的长度也是1，而这个Cookie的名字就是JSESSIONID，还有一个很长的二进制的字符串，是SessionID的值。

Cookie是客户端的存储空间，由浏览器来维持。

为什么会有cookie呢,大家都知道，http是无状态的协议，客户每次读取web页面时，服务器都打开新的会话，而且服务器也不会自动维护客户的上下文信息，那么要怎么才能实现网上商店中的购物车呢，session就是一种保存上下文信息的机制，它是针对每一个用户的，变量的值保存在服务器端，通过SessionID来区分不同的客户,session是以cookie或URL重写为基础的，默认使用cookie来实现，系统会创造一个名为JSESSIONID的输出cookie，我们叫做session cookie,以区别persistent cookies,也就是我们通常所说的cookie,注意session cookie是存储于浏览器内存中的，并不是写到硬盘上的，这也就是我们刚才看到的JSESSIONID，我们通常情是看不到JSESSIONID的，但是当我们把浏览器的cookie禁止后，web服务器会采用URL重写的方式传递Sessionid，我们就可以在地址栏看到sessionid=KWJHUG6JJM65HS2K6之类的字符串。

明白了原理，我们就可以很容易的分辨出persistent cookies和session cookie的区别了，网上那些关于两者安全性的讨论也就一目了然了，session cookie针对某一次会话而言，会话结束session cookie也就随着消失了，而persistent cookie只是存在于客户端硬盘上的一段文本（通常是加密的），而且可能会遭到cookie欺骗以及针对cookie的跨站脚本攻击，自然不如session cookie安全了。

通常session cookie是不能跨窗口使用的，当你新开了一个浏览器窗口进入相同页面时，系统会赋予你一个新的sessionid，这样我们信息共享的目的就达不到了，此时我们可以先把sessionid保存在persistent cookie中，然后在新窗口中读出来，就可以得到上一个窗口SessionID了，这样通过session cookie和persistent cookie的结合我们就实现了跨窗口的session tracking（会话跟踪）。

在一些web开发的书中，往往只是简单的把Session和cookie作为两种并列的http传送信息的方式，session cookies位于服务器端，persistent cookie位于客户端，可是session又是以cookie为基础的，明白的两者之间的联系和区别，我们就不难选择合适的技术来开发web service了。

如果有几千个session，怎么提高效率

分子目录存放session提高效率

session是存储在什么地方，以什么形式存储的

session变量保存在网页服务器中，你不能直接修改，当然，调用程序中的setAttribute()方法当然可以了。cookie存储的可不是具体的数据，要不岂不是太不安全了，谁都可以修改session变量了，网站也毫无安全性可言。实际，在cookie中，存储的是一个sessionId，它标示了一个服务器中的session变量，通过这种方式，服务器就知道你到底是那个session了。顺便说一句，如果客户端不支持cookie,session也是可以实现的，在服务器端通过urlEncoder，可以实现sessionId的传递。所以，记住客户端只存储session标识，实际内容在网页服务器中。

session是存在服务器的内存中 每个会话对应一个sessionId 通过sessionId开区分是那个会话的session,是以键值对的形式存储

Tomcat 中的 Session 是放在org.apache.catalina.session.ManagerBase 类中，

以 HashMap 格式存放，key 为 sessionId, value 为 org.apache.catalina.Session 接口，

这个接口由 org.apache.catalina.session.StandardSession 类实现，这个类同时实现了

HttpSession 接口。

实际上 Tomcat 中所使用的 HttpSession 实现并不把 StandardSession 拿来直接使用的，

而是为这个类做了个 org.apache.catalina.session.StandardSessionFacade 的门面，这个

门面什么事情都没做过，只是委托其内部属性的 StandardSession 去做。

另外，StandardSession，也就是 HttpSession 在 Tomcat 中实现的根源，其中的数据，也就

是我们采用 session.setAttribute(key, value); 设置进去的值是采用一个 Hashtable来存放的。

什么是hashtable，如何解决hash冲突

哈希法又称散列法、杂凑法以及关键字地址计算法等，相应的表称为哈希表。这种方法的基本思想是：首先在元素的关键字k和元素的存储位置p之间建立一个对应关系f，使得p=f(k)，f称为哈希函数。创建哈希表时，把关键字为k的元素直接存入地址为f(k)的单元；以后当查找关键字为k的元素时，再利用哈希函数计算出该元素的存储位置p=f(k)，从而达到按关键字直接存取元素的目的。

当关键字集合很大时，关键字值不同的元素可能会映象到哈希表的同一地址上，即 k1≠k2 ，但 H（k1）=H（k2），这种现象称为冲突，此时称k1和k2为同义词。实际中，冲突是不可避免的，只能通过改进哈希函数的性能来减少冲突。

综上所述，哈希法主要包括以下两方面的内容：

1）如何构造哈希函数

2）如何处理冲突。

8.4.1 哈希函数的构造方法

构造哈希函数的原则是：①函数本身便于计算；②计算出来的地址分布均匀，即对任一关键字k，f(k) 对应不同地址的概率相等，目的是尽可能减少冲突。

下面介绍构造哈希函数常用的五种方法。

1． 数字分析法

如果事先知道关键字集合，并且每个关键字的位数比哈希表的地址码位数多时，可以从关键字中选出分布较均匀的若干位，构成哈希地址。例如，有80个记录，关键字为8位十进制整数d1d2d3…d7d8，如哈希表长取100，则哈希表的地址空间为：00~99。假设经过分析，各关键字中 d4和d7的取值分布较均匀，则哈希函数为：h(key)=h(d1d2d3…d7d8)=d4d7。例如，h(81346532)=43，h(81301367)=06。相反，假设经过分析，各关键字中 d1和d8的取值分布极不均匀， d1 都等于5，d8 都等于2，此时，如果哈希函数为：h(key)=h(d1d2d3…d7d8)=d1d8，则所有关键字的地址码都是52，显然不可取。

2． 平方取中法

当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。

例：我们把英文字母在字母表中的位置序号作为该英文字母的内部编码。例如K的内部编码为11，E的内部编码为05，Y的内部编码为25，A的内部编码为01, B的内部编码为02。由此组成关键字“KEYA”的内部代码为11052501，同理我们可以得到关键字“KYAB”、“AKEY”、“BKEY”的内部编码。之后对关键字进行平方运算后，取出第7到第9位作为该关键字哈希地址，如图8.23所示。

<table> 
 <tbody> 
 <tr> 
 <td> 关键字 </td> 
 <td> 内部编码 </td> 
 <td> 内部编码的平方值 </td> 
 <td> H(k)关键字的哈希地址 </td> 
 </tr> 
 <tr> 
 <td> KEYA </td> 
 <td> 11050201 </td> 
 <td> 122157778355001 </td> 
 <td> 778 </td> 
 </tr> 
 <tr> 
 <td> KYAB </td> 
 <td> 11250102 </td> 
 <td> 126564795010404 </td> 
 <td> 795 </td> 
 </tr> 
 <tr> 
 <td> AKEY </td> 
 <td> 01110525 </td> 
 <td> 001233265775625 </td> 
 <td> 265 </td> 
 </tr> 
 <tr> 
 <td> BKEY </td> 
 <td> 02110525 </td> 
 <td> 004454315775625 </td> 
 <td> 315 </td> 
 </tr> 
 </tbody> 
</table>

图8.23平方取中法求得的哈希地址

3． 分段叠加法

这种方法是按哈希表地址位数将关键字分成位数相等的几部分（最后一部分可以较短），然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。具体方法有折叠法与移位法。移位法是将分割后的每部分低位对齐相加，折叠法是从一端向另一端沿分割界来回折叠（奇数段为正序，偶数段为倒序），然后将各段相加。例如：key=12360324711202065,哈希表长度为1000，则应把关键字分成3位一段，在此舍去最低的两位65，分别进行移位叠加和折叠叠加，求得哈希地址为105和907，

4． 除留余数法

假设哈希表长为m，p为小于等于m的最大素数，则哈希函数为

h（k）=k % p ，其中%为模p取余运算。

例如，已知待散列元素为（18，75，60，43，54，90，46），表长m=10，p=7，则有

h(18)=18 % 7=4 h(75)=75 %7=5 h(60)=60 % 7=4

h(43)=43 % 7=1 h(54)=54 %7=5 h(90)=90 % 7=6

h(46)=46 % 7=4

此时冲突较多。为减少冲突，可取较大的m值和p值，如m=p=13，结果如下：

h(18)=18 % 13=5 h(75)=75 %13=10 h(60)=60 % 13=8

h(43)=43 % 13=4 h(54)=54 %13=2 h(90)=90 % 13=12

h(46)=46 % 13=7

5． 伪随机数法

采用一个伪随机函数做哈希函数，即h(key)=random(key)。

在实际应用中，应根据具体情况，灵活采用不同的方法，并用实际数据测试它的性能，以便做出正确判定。通常应考虑以下五个因素：

（1）计算哈希函数所需时间（简单）。

（2）关键字的长度。

（3）哈希表大小。

（4）关键字分布情况。

（5）记录查找频率

8.4.2 处理冲突的方法

通过构造性能良好的哈希函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是哈希法的另一个关键问题。创建哈希表和查找哈希表都会遇到冲突，两种情况下解决冲突的方法应该一致。下面以创建哈希表为例，说明解决冲突的方法。常用的解决冲突方法有以下四种：

1. 开放定址法

这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：

Hi=（H（key）+di）% m i=1，2，…，n

其中H（key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。主要有以下三种：

（1）线性探测再散列

dii=1，2，3，…，m-1

这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。

（2）二次探测再散列

di=12，-12，22，-22，…，k2，-k2 ( k<=m/2 )

这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。

（3）伪随机探测再散列

di=伪随机数序列。

具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），并给定一个随机数做起点。

例如，已知哈希表长度m=11，哈希函数为：H（key）= key % 11，则H（47）=3，H（26）=4，H（60）=5，假设下一个关键字为69，则H（69）=3，与47冲突。如果用线性探测再散列处理冲突，下一个哈希地址为H1=（3 + 1）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 + 2）% 11 = 5，还是冲突，继续找下一个哈希地址为H3=（3 + 3）% 11 = 6，此时不再冲突，将69填入5号单元，参图8.26 (a)。如果用二次探测再散列处理冲突，下一个哈希地址为H1=（3 + 12）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 - 12）% 11 = 2，此时不再冲突，将69填入2号单元，参图8.26 (b)。如果用伪随机探测再散列处理冲突，且伪随机数序列为：2，5，9，……..，则下一个哈希地址为H1=（3 + 2）% 11 = 5，仍然冲突，再找下一个哈希地址为H2=（3 + 5）% 11 = 8，此时不再冲突，将69填入8号单元，参图8.26 (c)。

从上述例子可以看出，线性探测再散列容易产生“二次聚集”，即在处理同义词的冲突时又导致非同义词的冲突。例如，当表中i, i+1 ,i+2三个单元已满时，下一个哈希地址为i, 或i+1 ,或i+2，或i+3的元素，都将填入i+3这同一个单元，而这四个元素并非同义词。线性探测再散列的优点是：只要哈希表不满，就一定能找到一个不冲突的哈希地址，而二次探测再散列和伪随机探测再散列则不一定。

2. 再哈希法

这种方法是同时构造多个不同的哈希函数：

Hi=RH1（key） i=1，2，…，k

当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

3. 链地址法

这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

例如，已知一组关键字（32，40，36，53，16，46，71，27，42，24，49，64），哈希表长度为13，哈希函数为：H（key）= key % 13，则用链地址法处理冲突的结果如图8.27所示：

图8.27 链地址法处理冲突时的哈希表

4、建立公共溢出区

这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

数组和链表的区别

数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据，很少或不插入和删除元素，就应该用数组。

链表恰好相反，链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了。

\*C++语言中可以用数组处理一组数据类型相同的数据，但不允许动态定义数组的大小，即在使用数组之前必须确定数组的大小。而在实际应用中，用户使用数组之前有时无法准确确定数组的大小，只能将数组定义成足够大小，这样数组中有些空间可能不被使用，从而造成内存空间的浪费。链表是一种常见的数据组织形式，它采用动态分配内存的形式实现。需要时可以用new分配内存空间，不需要时用delete将已分配的空间释放，不会造成内存空间的浪费。

(1) 从逻辑结构角度来看

a, 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。

b,链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）

(2)从内存存储角度来看

a,(静态)数组从栈中分配空间, 对于程序员方便快速,但自由度小。

b, 链表从堆中分配空间, 自由度大但申请管理比较麻烦.

什么是虚拟内存管理

虚拟内存用硬盘空间做内存来弥补计算机RAM空间的缺乏。当实际RAM满时（实际上，在RAM满之前），虚拟内存就在硬盘上创建了。当物理内存用完后，虚拟内存管理器选择最近没有用过的，低优先级的内存部分写到交换文件上。这个过程对应用是隐藏的，应用把虚拟内存和实际内存看作是一样的。

每个运行在WindowsNT下的应用被分配到4GB的属于自己的虚拟地址空间（2GB给应用，2GB给操作系统）。

使用虚拟内存存在这样的问题，那就是读写硬盘的速度大大慢于读写实际RAM的速度。这就是当NT系统在没有足够的内存时程序运行慢的原因。

虚拟内存是文件数据交叉链接的活动文件。是WINDOWS目录下的一个"WIN386.SWP"文件，这个文件会不断地扩大和自动缩小。

就速度方面而言,CPU的L1和L2缓存速度最快，内存次之，硬盘再次之。但是虚拟内存使用的是硬盘的空间，为什么我们要使用速度最慢的硬盘来做为虚拟内存呢？因为电脑中所有运行的程序都需要经过内存来执行，如果执行的程序很大或很多，就会导致我们只有可怜的256M/512M内存消耗殆尽。而硬盘空间动辄几十G上百G，为了解决这个问题，Windows中运用了虚拟内存技术，即拿出一部分硬盘空间来充当内存使用...

手动设置虚拟内存

在默认状态下，是让系统管理虚拟内存的，但是系统默认设置的管理方式通常比较保守，在自动调节时会造成页面文件不连续，而降低读写效率，工作效率就显得不高，于是经常会出现“内存不足”这样的提示，下面就让我们自已动手来设置它吧。

①用右键点击桌面上的“我的电脑”图标，在出现的右键菜单中选“属性”选项打开“系统属性”窗口。在窗口中点击“高级”选项卡，出现高级设置的对话框

②点击“性能”区域的“设置”按钮，在出现的“性能选项”窗口中选择“高级”选项卡，打开其对话框。

③在该对话框中可看到关于虚拟内存的区域，点击“更改”按钮进入“虚拟内存”的设置窗口。选择一个有较大空闲容量的分区，勾选“自定义大小”前的复选框，将具体数值填入“初始大小”、“最大值”栏中，而后依次点击“设置→确定”按钮即可，最后重新启动计算机使虚拟内存设置生效。

块设备和字符设备有什么区别

Linux中I/O设备分为两类：字符设备和块设备。两种设备本身没有严格限制，但是，基于不同的功能进行了分类。

(1) 字符设备：提供连续的数据流，应用程序可以顺序读取，通常不支持随机存取。相反，此类设备支持按字节/字符来读写数据。举例来说，键盘、串口、调制解调器都是典型的字符设备。

(2) 块设备：应用程序可以随机访问设备数据，程序可自行确定读取数据的位置。硬盘、软盘、CD-ROM驱动器和闪存都是典型的块设备，应用程序可以寻址磁盘上的任何位置，并由此读取数据。此外，数据的读写只能以块(通常是512B)的倍数进行。与字符设备不同，块设备并不支持基于字符的寻址。

总结一下，这两种类型的设备的根本区别在于它们是否可以被随机访问。字符设备只能顺序读取，块设备可以随机读取。

块设备（blockdevice）

是一种具有一定结构的随机存取设备，对这种设备的读写是按块进行的，他使用缓冲区来存放暂时的数据，待条件成熟后，从缓存一次性写入设备或从设备中一次性读出放入到缓冲区，如磁盘和文件系统等

字符设备（Characterdevice）：这是一个顺序的数据流设备，对这种设备的读写是按字符进行的，而且这些字符是连续地形成一个数据流。他不具备缓冲区，所以对这种设备的读写是实时的，如终端、磁带机等。

系统中能够随机（不需要按顺序）访问固定大小数据片（chunks）的设备被称作块设备，这些数据片就称作块。最常见的块设备是硬盘，除此以外，还有软盘驱动器、CD-ROM驱动器和闪存等等许多其他块设备。注意，它们都是以安装文件系统的方式使用的——这也是块设备一般的访问方式。

另一种基本的设备类型是字符设备。字符设备按照字符流的方式被有序访问，像串口和键盘就都属于字符设备。如果一个硬件设备是以字符流的方式被访问的话，那就应该将它归于字符设备；反过来，如果一个设备是随机（无序的）访问的，那么它就属于块设备。

Linux块设备这两种类型的根本区别在于它们是否可以被随机访问——换句话说就是，能否在访问设备时随意地从一个位置跳转到另一个位置。举个例子，键盘这种设备提供的就是一个数据流，当你敲入“fox”这个字符串时，键盘驱动程序会按照和输入完全相同的顺序返回这个由三个字符组成的数据流。如果让键盘驱动程序打乱顺序来读字符串，或读取其他字符，都是没有意义的。所以键盘就是一种典型的字符设备，它提供的就是用户从键盘输入的字符流。对键盘进行读操作会得到一个字符流，首先是“f”，然后是“o”，最后是“x”，最终是文件的结束(EOF)。当没人敲键盘时，字符流就是空的。硬盘设备的情况就不大一样了。硬盘设备的驱动可能要求读取磁盘上任意块的内容，然后又转去读取别的块的内容，而被读取的块在磁盘上位置不一定要连续，所以说硬盘可以被随机访问，而不是以流的方式被访问，显然它是一个块设备。

内核管理块设备要比管理字符设备细致得多，需要考虑的问题和完成的工作相比字符设备来说要复杂许多。这是因为字符设备仅仅需要控制一个位置—当前位置—而块设备访问的位置必须能够在介质的不同区间前后移动。所以事实上内核不必提供一个专门的子系统来管理字符设备，但是对块设备的管理却必须要有一个专门的提供服务的子系统。不仅仅是因为块设备的复杂性远远高于字符设备，更重要的原因是块设备对执行性能的要求很高；对硬盘每多一分利用都会对整个系统的性能带来提升，其效果要远远比键盘吞吐速度成倍的提高大得多。

进程和线程的区别和联系

进程，是并发执行的程序在执行过程中分配和管理资源的基本单位，是一个动态概念，竟争计算机系统资源的基本单位。每一个进程都有一个自己的地址空间，即进程空间或（虚空间）。进程空间的大小只与处理机的位数有关，一个 16 位长处理机的进程空间大小为 216 ，而 32 位处理机的进程空间大小为 232 。进程至少有 5 种基本状态，它们是：初始态，执行态，等待状态，就绪状态，终止状态。

线程，在网络或多用户环境下，一个服务器通常需要接收大量且不确定数量用户的并发请求，为每一个请求都创建一个进程显然是行不通的，——无论是从系统资源开销方面或是响应用户请求的效率方面来看。因此，操作系统中线程的概念便被引进了。线程，是进程的一部分，一个没有线程的进程可以被看作是单线程的。线程有时又被称为轻权进程或轻量级进程，也是 CPU 调度的一个基本单位。

说到这里，我们对进程与线程都有了一个大体上的印象，现在开始说说二者大致的区别。

进程的执行过程是线状的，尽管中间会发生中断或暂停，但该进程所拥有的资源只为该线状执行过程服务。一旦发生进程上下文切换，这些资源都是要被保护起来的。这是进程宏观上的执行过程。而进程又可有单线程进程与多线程进程两种。我们知道，进程有一个进程控制块 PCB ，相关程序段和 该程序段对其进行操作的数据结构集 这三部分，单线程进程的执行过程在宏观上是线性的，微观上也只有单一的执行过程；而多线程进程在宏观上的执行过程同样为线性的，但微观上却可以有多个执行操作（线程），如不同代码片段以及相关的数据结构集。线程的改变只代表了 CPU 执行过程的改变，而没有发生进程所拥有的资源变化。出了 CPU 之外，计算机内的软硬件资源的分配与线程无关，线程只能共享它所属进程的资源。与进程控制表和 PCB 相似，每个线程也有自己的线程控制表 TCB ，而这个 TCB 中所保存的线程状态信息则要比 PCB 表少得多，这些信息主要是相关指针用堆栈（系统栈和用户栈），寄存器中的状态数据。进程拥有一个完整的虚拟地址空间，不依赖于线程而独立存在；反之，线程是进程的一部分，没有自己的地址空间，与进程内的其他线程一起共享分配给该进程的所有资源。

线程可以有效地提高系统的执行效率，但并不是在所有计算机系统中都是适用的，如某些很少做进程调度和切换的实时系统。使用线程的好处是有多个任务需要处理机处理时，减少处理机的切换时间；而且，线程的创建和结束所需要的系统开销也比进程的创建和结束要小得多。最适用使用线程的系统是多处理机系统和网络系统或分布式系统。

1.定义

进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动,进程是系统进行资源分配和调度的一个独立单位.

线程是进程的一个实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位.线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈),但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源.

2.关系

一个线程可以创建和撤销另一个线程;同一个进程中的多个线程之间可以并发执行.

相对进程而言，线程是一个更加接近于执行体的概念，它可以与同进程中的其他线程共享数据，但拥有自己的栈空间，拥有独立的执行序列。

3.区别

进程和线程的主要差别在于它们是不同的操作系统资源管理方式。进程有独立的地址空间，一个进程崩溃后，在保护模式下不会对其它进程产生影响，而线程只是一个进程中的不同执行路径。线程有自己的堆栈和局部变量，但线程之间没有单独的地址空间，一个线程死掉就等于整个进程死掉，所以多进程的程序要比多线程的程序健壮，但在进程切换时，耗费资源较大，效率要差一些。但对于一些要求同时进行并且又要共享某些变量的并发操作，只能用线程，不能用进程。

1) 简而言之,一个程序至少有一个进程,一个进程至少有一个线程.

2) 线程的划分尺度小于进程，使得多线程程序的并发性高。

3) 另外，进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大地提高了程序的运行效率。

4) 线程在执行过程中与进程还是有区别的。每个独立的线程有一个程序运行的入口、顺序执行序列和程序的出口。但是线程不能够独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制。

5) 从逻辑角度来看，多线程的意义在于一个应用程序中，有多个执行部分可以同时执行。但操作系统并没有将多个线程看做多个独立的应用，来实现进程的调度和管理以及资源分配。这就是进程和线程的重要区别。

4.优缺点

线程和进程在使用上各有优缺点：线程执行开销小，但不利于资源的管理和保护；而进程正相反。同时，线程适合于在SMP机器上运行，而进程则可以跨机器迁移。

简述TCP网关连接交互细节

建立连接：

理解：窗口和滑动窗口

TCP的流量控制

TCP使用窗口机制进行流量控制

什么是窗口？

连接建立时，各端分配一块缓冲区用来存储接收的数据，并将缓冲区的尺寸发送给另一端接收方发送的确认信息中包含了自己剩余的缓冲区尺寸剩余缓冲区空间的数量叫做窗口

2. TCP的流控过程（滑动窗口）

TCP(TransmissionControl Protocol)　传输控制协议

三次握手

TCP是主机对主机层的传输控制协议，提供可靠的连接服务，采用三次握手确认建立一个连接:

位码即tcp标志位,有6种标示:

SYN(synchronous建立联机)

ACK(acknowledgement确认)

PSH(push传送)

FIN(finish结束)

RST(reset重置)

URG(urgent紧急)

Sequencenumber(顺序号码)

Acknowledgenumber(确认号码)

客户端TCP状态迁移：

CLOSED->SYN\_SENT->ESTABLISHED->FIN\_WAIT\_1->FIN\_WAIT\_2->TIME\_WAIT->CLOSED

服务器TCP状态迁移：

CLOSED->LISTEN->SYN收到->ESTABLISHED->CLOSE\_WAIT->LAST\_ACK->CLOSED

各个状态的意义如下：

LISTEN -侦听来自远方TCP端口的连接请求；

SYN-SENT-在发送连接请求后等待匹配的连接请求；

SYN-RECEIVED- 在收到和发送一个连接请求后等待对连接请求的确认；

ESTABLISHED-代表一个打开的连接，数据可以传送给用户；

FIN-WAIT-1- 等待远程TCP的连接中断请求，或先前的连接中断请求的确认；

FIN-WAIT-2- 从远程TCP等待连接中断请求；

CLOSE-WAIT- 等待从本地用户发来的连接中断请求；

CLOSING-等待远程TCP对连接中断的确认；

LAST-ACK- 等待原来发向远程TCP的连接中断请求的确认；

TIME-WAIT-等待足够的时间以确保远程TCP接收到连接中断请求的确认；

CLOSED -没有任何连接状态；

TCP/IP协议中，TCP协议提供可靠的连接服务，采用三次握手建立一个连接，如图1所示。

（1）第一次握手：建立连接时，客户端A发送SYN包（SYN=j）到服务器B，并进入SYN\_SEND状态，等待服务器B确认。

（2）第二次握手：服务器B收到SYN包，必须确认客户A的SYN（ACK=j+1），同时自己也发送一个SYN包（SYN=k），即SYN+ACK包，此时服务器B进入SYN\_RECV状态。

（3）第三次握手：客户端A收到服务器B的SYN＋ACK包，向服务器B发送确认包ACK（ACK=k+1），此包发送完毕，客户端A和服务器B进入ESTABLISHED状态，完成三次握手。

完成三次握手，客户端与服务器开始传送数据。

关闭连接：

由于TCP连接是全双工的，因此每个方向都必须单独进行关闭。这个原则是当一方完成它的数据发送任务后就能发送一个FIN来终止这个方向的连接。收到一个 FIN只意味着这一方向上没有数据流动，一个TCP连接在收到一个FIN后仍能发送数据。首先进行关闭的一方将执行主动关闭，而另一方执行被动关闭。

CP的连接的拆除需要发送四个包，因此称为四次挥手(four-way handshake)。客户端或服务器均可主动发起挥手动作，在socket编程中，任何一方执行close()操作即可产生挥手操作。

（1）客户端A发送一个FIN，用来关闭客户A到服务器B的数据传送。

（2）服务器B收到这个FIN，它发回一个ACK，确认序号为收到的序号加1。和SYN一样，一个FIN将占用一个序号。

（3）服务器B关闭与客户端A的连接，发送一个FIN给客户端A。

（4）客户端A发回ACK报文确认，并将确认序号设置为收到序号加1。

TCP采用四次挥手关闭连接如图2所示。

由于TCP连接是全双工的，因此每个方向都必须单独进行关闭。这原则是当一方完成它的数据发送任务后就能发送一个FIN来终止这个方向的连接。收到一个 FIN只意味着这一方向上没有数据流动，一个TCP连接在收到一个FIN后仍能发送数据。首先进行关闭的一方将执行主动关闭，而另一方执行被动关闭。

TCP协议的连接是全双工连接，一个TCP连接存在双向的读写通道。

简单说来是 “先关读，后关写”，一共需要四个阶段。以客户机发起关闭连接为例：

1.服务器读通道关闭

2.客户机写通道关闭

3.客户机读通道关闭

4.服务器写通道关闭

关闭行为是在发起方数据发送完毕之后，给对方发出一个FIN（finish）数据段。直到接收到对方发送的FIN，且对方收到了接收确认ACK之后，双方的数据通信完全结束，过程中每次接收都需要返回确认数据段ACK。

详细过程：

第一阶段 客户机发送完数据之后，向服务器发送一个FIN数据段，序列号为i；

1.服务器收到FIN(i)后，返回确认段ACK，序列号为i+1，关闭服务器读通道；

2.客户机收到ACK(i+1)后，关闭客户机写通道；

（此时，客户机仍能通过读通道读取服务器的数据，服务器仍能通过写通道写数据）

第二阶段 服务器发送完数据之后，向客户机发送一个FIN数据段，序列号为j；

3.客户机收到FIN(j)后，返回确认段ACK，序列号为j+1，关闭客户机读通道；

4.服务器收到ACK(j+1)后，关闭服务器写通道。

这是标准的TCP关闭两个阶段，服务器和客户机都可以发起关闭，完全对称。

FIN标识是通过发送最后一块数据时设置的，标准的例子中，服务器还在发送数据，所以要等到发送完的时候，设置FIN（此时可称为TCP连接处于半关闭状态，因为数据仍可从被动关闭一方向主动关闭方传送）。如果在服务器收到FIN(i)时，已经没有数据需要发送，可以在返回ACK(i+1)的时候就设置FIN(j)标识，这样就相当于可以合并第二步和第三步.

写出10个常用的linux命令和参数

1． cat 连接文件并显示

（1）语法：cat\[选项\]文件列表

2． cd 改变当前工作目录

（1）语法：cd目录名

（2）参数：

目录名：改变到选定的目录名。如果没有指定目录，就返回用户本户目录。

3． cp 拷贝文件

（1）语法：cp\[选项\] 源文件 目标文件

cp\[选项\] 源文件组 目标目录

4． find 非常有力的查询工具

（1）语法：find目录列表 匹配标准

（2）参数：

目录列表：希望查询文件或文件集的目录列表 目录间用空格分隔。

匹配标准：希望查询的文件的匹配标准或说明。

5． grep 在文件中查找模式当找到时报告

（1）语法：grep \[选项\] 正则表达式 文件列表

egrep \[选项\] 正则表达式 文件列表

fgrep \[选项\] 串 文件列表

（2）参数：

文件列表：可选的用空格分隔的文件列表。用于查询给出的串或正则表达式。若为空则查询标准输入。

正则表达式：要查询的正则表达式。正则表达式是ed使用的一种格式。参阅用户手册查正则表达式的定义。

串：希望在文件中查到的串。

6． ls 列出文件系统中的文件

（1）语法：ls \[选项\] \[文件列表\]

（2）参数：

\-a：显示所有文件，包括当前目录和父目录。

\-l：给出长表。长表显示文件的详细内容，如：文件类型，权限，连接或目录计数，所有者，组，按字节文件大小，文件的最近修改时间和文件名。

7． more 通用的按页显示

（1）语法：more \[选项\] 文件名

8． rm 从文件系统中删除文件及整个目录

（1）语法：rm \[选项\] 文件列表

（2）参数：

文件列表：希望删除的用空格分隔i的文件列表，可以包括目录名。

9. vi 最常用的文本编辑

（1）语法：vi 文件名

对指定的文件执行vi编辑程序。

10. who 报告当前系统上的用户和其他用户及登录信息

（1） 语法：who \[选项\] utmp式的文件

who am i

11.chmod 改变文件模式

（1）语法：chmod\[选项\]模式文件列表

12. file查看文件类型

（1）语法：file \[-c\]\[-z\] \[-L\] \[-f文件\] \[-m文件\] 文件列表

13. kill允许送一个信号到当前运行的进程

（1）语法：kill \[信号\] 进程号

14. less通用的按页显示文件，类似more，允许在文件中向前和向后移动

（1）语法：less \[选项\] 文件名

15. mkdir在文件系统中建立新目录

（1）语法：mkdir \[-m模式\] \[-p目录名\] 目录

16. mv 改文件改名，移动文件到一个新的目录，或两者都作

（1）语法：mv \[-f\]\[-i\] 文件1 文件2

17．passwd 维护用户口令

（1）语法：passwd \[名字\]

（2）参数：

名字：改变用户名的口令。只有超级用户可做到此工作。

18．ps 报告进程状态

（1）语法：ps \[选项\]

没有选项能在终端上给出当前执行进程的画面。下面是ps命令可能的选项。

19．pwd 报告现行正在工作的或当前目录

（1）语法：pwd

20．rmdir 删除目录

（1）语法：rmdir –p 目录表

如何查看磁盘剩余空间

df -hl 查看磁盘剩余空间

df -h 查看每个根路径的分区大小

du -sh \[目录名\] 返回该目录的大小

du -sm \[文件夹\] 返回该文件夹总M数

如何查看端口是否被占用

netstat -anp | grep portno

如何查看某个进程所占用的内存

(1)top

top命令是Linux下常用的性能分析工具，能够实时显示系统中各个进程的资源占用状况，类似于Windows的任务管理器

可以直接使用top命令后，查看%MEM的内容。可以选择按进程查看或者按用户查看，如想查看oracle用户的进程内存使用情况的话可以使用如下的命令：

$ top -u oracle

内容解释：

PID：进程的ID

USER：进程所有者

PR：进程的优先级别，越小越优先被执行

NInice：值

VIRT：进程占用的虚拟内存

RES：进程占用的物理内存

SHR：进程使用的共享内存

S：进程的状态。S表示休眠，R表示正在运行，Z表示僵死状态，N表示该进程优先值为负数

%CPU：进程占用CPU的使用率

%MEM：进程使用的物理内存和总内存的百分比

TIME+：该进程启动后占用的总的CPU时间，即占用CPU使用时间的累加值。

COMMAND：进程启动命令名称

常用的命令：

P：按%CPU使用率排行

T：按MITE+排行

M：按%MEM排行

(2)pmap

可以根据进程查看进程相关信息占用的内存情况，(进程号可以通过ps查看)如下所示：

$ pmap -d 14596

(3)ps

如下例所示：

$ ps -e -o'pid,comm,args,pcpu,rsz,vsz,stime,user,uid' 其中rsz是是实际内存

$ ps -e -o'pid,comm,args,pcpu,rsz,vsz,stime,user,uid' | grep oracle | sort -nrk5

其中rsz为实际内存，上例实现按内存排序，由大到小

用两个线程实现1-100的输出

\#include<stdlib.h>

\#include<stdio.h>

\#include<unistd.h>

\#include<pthread.h>

int n =1;

int N =100;

pthread\_mutex\_tmutex;

pthread\_mutex\_init(&mutex);

intpv=1;//条件

void\*func1()

while(n < N+1)

if(pv==1)//

pthread\_mutex\_lock(&mutex);

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

n++;

pv=2;//

pthread\_mutex\_unlock(&mutex);

if(n == N+1)

pthread\_exit(NULL);

void\*func2()

while(n < N+1)

if(pv==2)

pthread\_mutex\_lock(&mutex);

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

n++;

pv=1;

pthread\_mutex\_unlock(&mutex);

if(n == N+1)

pthread\_exit(NULL);

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

pthread\_t pid1,pid2;

if((pthread\_create(&pid1,NULL,func1,NULL)) != 0)

printf("pthread createerror\\n");

if((pthread\_create(&pid2,NULL,func2,NULL))!= 0)

printf("pthread createerror\\n");

pthread\_join(pid1,NULL);

pthread\_join(pid2,NULL);

return 0;

把一个文件夹中所有01结尾的文件前十行内容输出

(1) 文件夹下文件的遍历。像这种题其实是最简单的，因为不同的操作系统会提供不同的 API ，直接去调用就行了。比如 windows 的 FindFirstFile FindNextFile 。

(2) 字符串的处理。获取文件路径(字符串)的后两个字母，然后和 “01″ 比较

(3) 文件读写。这个就更简单了。文件打开，一行一行的读就行了。

inline函数是否占用运行时间

a.从inline的原理，我们可以看出，inline的原理，是用空间换取时间的做法，是以代码膨胀（复制）为代价，仅仅省去了函数调用的开销，从而提高函数的执行效率。如果执行函数体内代码的时间，相比于函数调用的开销较大，那么效率的收获会很少。所以，如果函数体代码过长或者函数体重有循环语句，if语句或switch语句或递归时，不宜用内联

b.关键字inline 必须与函数定义体放在一起才能使函数成为内联，仅将inline 放在函数声明前面不起任何作用。内联函数调用前必须声明。

进程的调度算法

一、先来先服务和短作业(进程)优先调度算法

1．先来先服务调度算法

先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。

2．短作业(进程)优先调度算法

短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。

二、高优先权优先调度算法

1．优先权调度算法的类型

为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引入了最高优先权优先(FPF)调度算法。此算法常被用于批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度算法，还可用于实时系统中。当把该算法用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业装入内存。当用于进程调度时，该算法是把处理机分配给就绪队列中优先权最高的进程，这时，又可进一步把该算法分成如下两种。

1) 非抢占式优先权算法

在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。

2) 抢占式优先权调度算法

在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。因此，在采用这种调度算法时，是每当系统中出现一个新的就绪进程i 时，就将其优先权Pi与正在执行的进程j 的优先权Pj进行比较。如果Pi≤Pj，原进程Pj便继续执行；但如果是Pi>Pj，则立即停止Pj的执行，做进程切换，使i 进程投入执行。显然，这种抢占式的优先权调度算法能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。

2．高响应比优先调度算法

在批处理系统中，短作业优先算法是一种比较好的算法，其主要的不足之处是长作业的运行得不到保证。如果我们能为每个作业引入前面所述的动态优先权，并使作业的优先级随着等待时间的增加而以速率a 提高，则长作业在等待一定的时间后，必然有机会分配到处理机。该优先权的变化规律可描述为：

操作系统

由于等待时间与服务时间之和就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为：

操作系统

由上式可以看出：

(1) 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。

(2) 当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。

(3) 对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。简言之，该算法既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务。因此，该算法实现了一种较好的折衷。当然，在利用该算法时，每要进行调度之前，都须先做响应比的计算，这会增加系统开销。

三、基于时间片的轮转调度算法

1．时间片轮转法

1) 基本原理

在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU 分配给队首进程，并令其执行一个时间片。时间片的大小从几ms 到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内响应所有用户的请求。

2．多级反馈队列调度算法

前面介绍的各种用作进程调度的算法都有一定的局限性。如短进程优先的调度算法，仅照顾了短进程而忽略了长进程，而且如果并未指明进程的长度，则短进程优先和基于进程长度的抢占式调度算法都将无法使用。而多级反馈队列调度算法则不必事先知道各种进程所需的执行时间，而且还可以满足各种类型进程的需要，因而它是目前被公认的一种较好的进程调度算法。在采用多级反馈队列调度算法的系统中，调度算法的实施过程如下所述。

(1) 应设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，……，第i+1个队列的时间片要比第i个队列的时间片长一倍。

(2) 当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n 队列便采取按时间片轮转的方式运行。

(3) 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1～(i-1)队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1～(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。

页面替换算法

(1) 随机算法，即RAND算法（Randomalgorithm）。利用软件或硬件的随机数发生器来确定主存储器中被替换的页面。这种算法最简单，而且容易实现。但是，这种算法完全没有利用主存储器中页面调度情况的历史信息，也没有反映程序的局部性，所以命中率比较低。

(2) 先进先出算法，即FIFO算法（First-InFirst-Out algorithm）。这种算法选择最先调入主存储器的页面作为被替换的页面。它的优点是比较容易实现，能够利用主存储器中页面调度情况的历史信息，但是，没有反映程序的局部性。因为最先调入主存的页面，很可能也是经常要使用的页面。

(3) 近期最少使用算法，即LFU算法（LeastFrequently Used algorithm）。这种算法选择近期最少访问的页面作为被替换的页面。显然，这是一种非常合理的算法，因为到目前为止最少使用的页面，很可能也是将来最少访问的页面。该算法既充分利用了主存中页面调度情况的历史信息，又正确反映了程序的局部性。但是，这种算法实现起来非常困难，它要为每个页面设置一个很长的计数器，并且要选择一个固定的时钟为每个计数器定时计数。在选择被替换页面时，要从所有计数器中找出一个计数值最大的计数器。因此，通常采用如下一种相对比较简单的方法。

(4) 最久没有使用算法，即LRU算法（LeastRecently Used algorithm）。这种算法把近期最久没有被访问过的页面作为被替换的页面。它把LFU算法中要记录数量上的"多"与"少"简化成判断"有"与"无"，因此，实现起来比较容易。

(5) 最优替换算法，即OPT算法（OPTimalreplacement algorithm）。上面介绍的几种页面替换算法主要是以主存储器中页面调度情况的历史信息为依据的，它假设将来主存储器中的页面调度情况与过去一段时间内主存储器中的页面调度情况是相同的。显然，这种假设不总是正确的。最好的算法应该是选择将来最久不被访问的页面作为被替换的页面，这种替换算法的命中率一定是最高的，它就是最优替换算法。

要实现OPT算法，唯一的办法是让程序先执行一遍，记录下实际的页地址流情况。根据这个页地址流才能找出当前要被替换的页面。显然，这样做是不现实的。因此，OPT算法只是一种理想化的算法，然而，它也是一种很有用的算法。实际上，经常把这种算法用来作为评价其它页面替换算法好坏的标准。在其它条件相同的情况下，哪一种页面替换算法的命中率与OPT算法最接近，那么，它就是一种比较好的页面替换算法。

用户态和内核态的区别

当一个任务（进程）执行系统调用而陷入内核代码中执行时，我们就称进程处于内核运行态（或简称为内核态）。此时处理器处于特权级最高的（0级）内核代码中执行。当进程处于内核态时，执行的内核代码会使用当前进程的内核栈。每个进程都有自己的内核栈。当进程在执行用户自己的代码时，则称其处于用户运行态（用户态）。即此时处理器在特权级最低的（3级）用户代码中运行。当正在执行用户程序而突然被中断程序中断时，此时用户程序也可以象征性地称为处于进程的内核态。因为中断处理程序将使用当前进程的内核栈。这与处于内核态的进程的状态有些类似。

内核态与用户态是操作系统的两种运行级别,跟intel cpu没有必然的联系,intel cpu提供Ring0-Ring3三种级别的运行模式，Ring0级别最高，Ring3最低。Linux使用了Ring3级别运行用户态，Ring0作为内核态，没有使用Ring1和Ring2。Ring3状态不能访问Ring0的地址空间，包括代码和数据。Linux进程的4GB地址空间，3G-4G部分大家是共享的，是内核态的地址空间，这里存放在整个内核的代码和所有的内核模块，以及内核所维护的数据。用户运行一个程序，该程序所创建的进程开始是运行在用户态的，如果要执行文件操作，网络数据发送等操作，必须通过write，send等系统调用，这些系统调用会调用内核中的代码来完成操作，这时，必须切换到Ring0，然后进入3GB-4GB中的内核地址空间去执行这些代码完成操作，完成后，切换回Ring3，回到用户态。这样，用户态的程序就不能随意操作内核地址空间，具有一定的安全保护作用。

至于说保护模式，是说通过内存页表操作等机制，保证进程间的地址空间不会互相冲突，一个进程的操作不会修改另一个进程的地址空间中的数据。

1. 用户态和内核态的概念区别

究竟什么是用户态，什么是内核态，这两个基本概念以前一直理解得不是很清楚，根本原因个人觉得是在于因为大部分时候我们在写程序时关注的重点和着眼的角度放在了实现的功能和代码的逻辑性上，先看一个例子：

1）例子

voidtestfork()\{

if(0 = =fork())\{

printf(“createnew process success!\\n”);

printf(“testforkok\\n”);

这段代码很简单，从功能的角度来看，就是实际执行了一个fork()，生成一个新的进程，从逻辑的角度看，就是判断了如果fork()返回的是0则打印相关语句，然后函数最后再打印一句表示执行完整个testfork()函数。代码的执行逻辑和功能上看就是如此简单，一共四行代码，从上到下一句一句执行而已，完全看不出来哪里有体现出用户态和进程态的概念。

如果说前面两种是静态观察的角度看的话，我们还可以从动态的角度来看这段代码，即它被转换成CPU执行的指令后加载执行的过程，这时这段程序就是一个动态执行的指令序列。而究竟加载了哪些代码，如何加载就是和操作系统密切相关了。

2）特权级

熟悉Unix/Linux系统的人都知道，fork的工作实际上是以系统调用的方式完成相应功能的，具体的工作是由sys\_fork负责实施。其实无论是不是Unix或者Linux，对于任何操作系统来说，创建一个新的进程都是属于核心功能，因为它要做很多底层细致地工作，消耗系统的物理资源，比如分配物理内存，从父进程拷贝相关信息，拷贝设置页目录页表等等，这些显然不能随便让哪个程序就能去做，于是就自然引出特权级别的概念，显然，最关键性的权力必须由高特权级的程序来执行，这样才可以做到集中管理，减少有限资源的访问和使用冲突。

特权级显然是非常有效的管理和控制程序执行的手段，因此在硬件上对特权级做了很多支持，就Intel x86架构的CPU来说一共有0~3四个特权级，0级最高，3级最低，硬件上在执行每条指令时都会对指令所具有的特权级做相应的检查，相关的概念有CPL、DPL和RPL，这里不再过多阐述。硬件已经提供了一套特权级使用的相关机制，软件自然就是好好利用的问题，这属于操作系统要做的事情，对于Unix/Linux来说，只使用了0级特权级和3级特权级。也就是说在Unix/Linux系统中，一条工作在0级特权级的指令具有了CPU能提供的最高权力，而一条工作在3级特权级的指令具有CPU提供的最低或者说最基本权力。

3）用户态和内核态

现在我们从特权级的调度来理解用户态和内核态就比较好理解了，当程序运行在3级特权级上时，就可以称之为运行在用户态，因为这是最低特权级，是普通的用户进程运行的特权级，大部分用户直接面对的程序都是运行在用户态；反之，当程序运行在0级特权级上时，就可以称之为运行在内核态。

虽然用户态下和内核态下工作的程序有很多差别，但最重要的差别就在于特权级的不同，即权力的不同。运行在用户态下的程序不能直接访问操作系统内核数据结构和程序，比如上面例子中的testfork()就不能直接调用sys\_fork()，因为前者是工作在用户态，属于用户态程序，而sys\_fork()是工作在内核态，属于内核态程序。

当我们在系统中执行一个程序时，大部分时间是运行在用户态下的，在其需要操作系统帮助完成某些它没有权力和能力完成的工作时就会切换到内核态，比如testfork()最初运行在用户态进程下，当它调用fork()最终触发sys\_fork()的执行时，就切换到了内核态。

2. 用户态和内核态的转换

1）用户态切换到内核态的3种方式

a. 系统调用

这是用户态进程主动要求切换到内核态的一种方式，用户态进程通过系统调用申请使用操作系统提供的服务程序完成工作，比如前例中fork()实际上就是执行了一个创建新进程的系统调用。而系统调用的机制其核心还是使用了操作系统为用户特别开放的一个中断来实现，例如Linux的int 80h中断。

b. 异常

当CPU在执行运行在用户态下的程序时，发生了某些事先不可知的异常，这时会触发由当前运行进程切换到处理此异常的内核相关程序中，也就转到了内核态，比如缺页异常。

c. 外围设备的中断

当外围设备完成用户请求的操作后，会向CPU发出相应的中断信号，这时CPU会暂停执行下一条即将要执行的指令转而去执行与中断信号对应的处理程序，如果先前执行的指令是用户态下的程序，那么这个转换的过程自然也就发生了由用户态到内核态的切换。比如硬盘读写操作完成，系统会切换到硬盘读写的中断处理程序中执行后续操作等。

这3种方式是系统在运行时由用户态转到内核态的最主要方式，其中系统调用可以认为是用户进程主动发起的，异常和外围设备中断则是被动的。

2）具体的切换操作

从触发方式上看，可以认为存在前述3种不同的类型，但是从最终实际完成由用户态到内核态的切换操作上来说，涉及的关键步骤是完全一致的，没有任何区别，都相当于执行了一个中断响应的过程，因为系统调用实际上最终是中断机制实现的，而异常和中断的处理机制基本上也是一致的，关于它们的具体区别这里不再赘述。关于中断处理机制的细节和步骤这里也不做过多分析，涉及到由用户态切换到内核态的步骤主要包括：

\[1\] 从当前进程的描述符中提取其内核栈的ss0及esp0信息。

\[2\] 使用ss0和esp0指向的内核栈将当前进程的cs,eip,eflags,ss,esp信息保存起来，这个过程也完成了由用户栈到内核栈的切换过程，同时保存了被暂停执行的程序的下一

条指令。

\[3\] 将先前由中断向量检索得到的中断处理程序的cs,eip信息装入相应的寄存器，开始

执行中断处理程序，这时就转到了内核态的程序执行了。

平面上N个点，每两个点都确定一条直线，求出斜率最大的那条直线所通过的两个点（斜率不存在的情况不考虑）。时间效率越高越好。

3个点A,B,C,把它们的按x坐标排序。假设排序后的顺序是ABC，那么有两种情况：

1.ABC共线，则k(AB)=k(BC)=k(AC)

2.ABC不共线，则ABC将形成一个三角形，那么k(AC)<max(k(AB),k(BC))

其中k()表示求斜率。

所以程序的基本步骤就是：

1.把N个点按x坐标排序。

2.遍历，求相邻的两个点的斜率，找最大值。

时间复杂度Nlog(N)。

先把这些点按x坐标从小到大排序，斜率最大的两点必然是挨一起的两个点，所以排序O(n\* lg n)，遍历一次O(n)就够了

关系型数据库的主要特征

1）数据集中控制，在文件管理方法中，文件是分散的，每个用户或每种处理都有各自的文件，这些文件之间一般是没有联系的，因此，不能按照统一的方法来控制、维护和管理。而数据库则很好地克服了这一缺点，可以集中控制、维护和管理有关数据。

2）数据独立，数据库中的数据独立于应用程序，包括数据的物理独立性和逻辑独立性，给数据库的使用、调整、优化和进一步扩充提供了方便，提高了数据库应用系统的稳定性。

3）数据共享，数据库中的数据可以供多个用户使用，每个用户只与库中的一部分数据发生联系；用户数据可以重叠，用户可以同时存取数据而互不影响，大大提高了数据库的使用效率。

4）减少数据冗余，数据库中的数据不是面向应用，而是面向系统。数据统一定义、组织和存储，集中管理，避免了不必要的数据冗余，也提高了数据的一致性。

5）数据结构化，整个数据库按一定的结构形式构成，数据在记录内部和记录类型之间相互关联，用户可通过不同的路径存取数据。

6）统一的数据保护功能，在多用户共享数据资源的情况下，对用户使用数据有严格的检查，对数据库规定密码或存取权限，拒绝非法用户进入数据库，以确保数据的安全性、一致性和并发控制。

override和overload的区别

Override是重写：方法名称、参数个数，类型，顺序，返回值类型都是必须和父类方法一致的。它的关系是父子关系

Overload是重载:方法名称不变，其余的都是可以变更的。它的关系是同一个类，同一个方法名，不同的方法参数或返回值。

编程并实现一个八皇后的解法

\#include<iostream>

usingnamespace std;

voidswap(int &a, int &b)

int temp = a;

a = b;

b = temp;

boolcheck(int \*a, int n)

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

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

if (a\[i\] - a\[j\] == i -j || a\[i\] - a\[j\] == j - i)

return false;

return true;

voidpermutation(int \*a,int begin,int n)

if (begin == n)

if (check(a, n))

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

cout <<a\[i\];

cout << endl;

else

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

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

permutation(a, begin +1, n);

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

voideightQueue()

const int n = 8;

int \*a = new int\[n\];

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

a\[i\] = i;

permutation(a, 0, n);

intmain()

eightQueue();

getchar();

链表的归并排序

\#include<iostream>

usingnamespace std;

typedefstruct node\{

int data;

struct node \*next;

\} node;

voidpush(node \*\*head, int data)

node \*a = new node;

a->data = data;

a->next = \*head;

\*head = a;

node\*merge(node \*a, node \*b)

node \*result = NULL;

if (a == NULL)

return b;

if (b == NULL)

return a;

if (a->data <= b->data)

result = a;

result->next =merge(a->next, b);

else

result = b;

result->next = merge(a,b->next);

return result;

voidsplitList(node \*head, node \*\*a,node \*\*b)

if (head==NULL||head->next==NULL)

\*a = head;

\*b = NULL;

return;

node \*m = head->next;

node \*n = head;

while (m != NULL)

m = m->next;

if (m != NULL)

n = n->next;

m = m->next;

\*a = head;

\*b = n->next;

n->next = NULL;

voidmergeSort(node \*\*headRef)

node \*head = \*headRef;

node \*a = NULL;

node \*b = NULL;

if (head == NULL || (head)->next ==NULL)

return;

else\{

splitList(head,&a,&b);

mergeSort(&a);

mergeSort(&b);

\*headRef=merge(a,b);

intmain()

node \*head = NULL;

push(&head, 3);

push(&head, 1);

push(&head, 4);

push(&head, 5);

push(&head, 7);

push(&head, 2);

node \*t = head;

while (t != NULL)

cout <<t->data<<'\\t';

t = t->next;

mergeSort(&head);

t = head;

while (t != NULL)

cout << t->data<< '\\t';

t = t->next;

getchar();

在数据库中如何创建一个表

Create table tbl\_a(vol\_a int,vol\_bvarchar(20));

创建后如何添加一个记录、删除一个记录

Insert intotbl\_a(vol\_a,vol\_b) values(30,”wang”);

Delete fromtbl\_a where vol\_a=30;

Updatatbl\_a set vol\_a=40 where vol\_b=”wang”;

Selectvol\_a,vol\_b from tbl\_a where vol\_a=30;

编写C++中的两个类 一个只能在栈中分配空间 一个只能在堆中分配。

//HeapOnly.cpp

\#include<iostream>

usingnamespace std;

classHeapOnly

public:

HeapOnly() \{ cout << "constructor."<< endl; \}

void destroy() const \{ delete this; \}

private:

~HeapOnly() \{ cout << "destroy."; \}

\};

int main()

HeapOnly \*p = new HeapOnly;

p->destroy();

//HeapOnly h;

getchar();

return 0;

//StackOnly.cpp

\#include<iostream>

usingnamespace std;

classStackOnly

public:

StackOnly() \{ cout << "constructor."<< endl; \}

~StackOnly() \{ cout << "destructor."<< endl; \}

private:

void\* operator new(size\_t)\{\};

\};

int main()

StackOnly s;

//StackOnly \*p = new StackOnly;

getchar();

return 0;

请编写能直接实现strstr()函数功能的代码

\#include<iostream>

usingnamespace std;

char\*strstr1(const char \*s1, const char \*s2)

int len2=strlen(s2);

for (; \*s1; ++s1)

if (strncmp(s1, s2, len2) ==0)

return (char\*)s1;

return NULL;

intmain()

char \*a = "abcdeeeeef";

char \*b = "ef";

char \*p=strstr1(a, b);

cout << p << endl;

getchar();

每个飞机只有一个油箱， 飞机之间可以相互加油（注意是相互，没有加油机） 一箱油可供一架飞机绕地球飞半圈， 问题：为使至少一架飞机绕地球一圈回到起飞时的飞机场，至少需要出动几架飞机？（所有飞机从同一机场起飞，而且必须安全返回机场，不允许中途降落，中间没有飞机场.

至少需要三架飞机。（两架飞机是显然不可能的，这个都不用说什么）。前提假设当然是：加油、掉头、降落和起飞的时间分别是0。

加油方案和步骤分别是：

1. 三架飞机同时从机场O起飞，方向为顺时针，此时三架飞机的油量分别是：A: 1, B: 1, C: 1。

2. 当A飞行至半圈的1/4位置时，此时飞机的油量分别是：A: 3/4, B: 3/4, C: 3/4。此时C分别给A和B加满油，三架飞机当前油量分别是：A: 1, B: 1, C: 1/4。C返回机场。A、B继续向前飞行。

3. 当A飞行至半圈的1/2位置时，此时C已经返回机场，三家飞机此时油量分别是：A: 3/4, B: 3/4, C: 0。此时B给A加满油，C加满油，此时三架飞机的油量分别是：A: 1, B: 1/2, C: 1。然后B返回机场，A继续向前飞行。

4. 当A飞行至半圈位置时，B已经返回机场并且加满了油（假设加油时间为0），此时，B和C沿逆时针方向飞行，三架飞机当前油量分别是：A: 1/2, B: 1, C: 1。A继续向前飞行。

5. 当A飞行至另外半圈的1/4位置时，三架飞机剩余油量分别是：A: 1/4, B: 3/4, C: 3/4。此时，C给B加满油。此时三架飞机油量分别是：A: 1/4, B: 1, C: 1/2。C返回机场，B和A继续向前飞行。

6. 当A飞行至另外半圈的1/2位置时，C已经返回机场，A和B相遇，此时三架飞机剩余油量分别是：A: 0, B: 3/4, C: 0。B给A加1/4的油，三架飞机剩余油量：A: 1/4, B: 1/2, C: 1。C加满油从机场逆时针飞出，B返回机场，A继续向前飞行。

7. 当A飞行至另外半圈的3/4位置时，A和C相遇。此时三架飞机的油量分别是：A: 0, B: 1/4, C: 3/4。C给A加1/4的油，此时三架飞机的油量分别是：A: 1/4, B: 1/4, C: 1/2。C掉头返回机场，A和B继续向前飞行。

8. 三架飞机顺利回到机场！

static的作用

C++的static有两种用法：面向过程程序设计中的static和面向对象程序设计中的static。前者应用于普通变量和函数，不涉及类；后者主要说明static在类中的作用。

一、面向过程设计中的static

1、静态全局变量

在全局变量前，加上关键字static，该变量就被定义成为一个静态全局变量。我们先举一个静态全局变量的例子，如下：

\#include<iostream>

usingnamespace std;

staticint n; //定义静态全局变量

voidfn()

n++;

cout<<n<<endl;

int main(void)

n = 20;

cout<<n<<endl;

fn();

return 0;

静态全局变量有以下特点：

该变量在全局数据区分配内存；

未经初始化的静态全局变量会被程序自动初始化为0（自动变量的值是随机的，除非它被显式初始化）；

静态全局变量在声明它的整个文件都是可见的，而在文件之外是不可见的；

静态变量都在全局数据区分配内存，包括后面将要提到的静态局部变量。对于一个完整的程序，在内存中的分布情况如下图

代码区

全局数据区

堆区

栈区

一般程序的由new产生的动态数据存放在堆区，函数内部的自动变量存放在栈区。自动变量一般会随着函数的退出而释放空间，静态数据（即使是函数内部的静态局部变量）也存放在全局数据区。全局数据区的数据并不会因为函数的退出而释放空间。细心的读者可能会发现，Example 1中的代码中将

staticint n; //定义静态全局变量

改为

intn; //定义全局变量

程序照样正常运行。

的确，定义全局变量就可以实现变量在文件中的共享，但定义静态全局变量还有以下好处：

静态全局变量不能被其它文件所用；

其它文件中可以定义相同名字的变量，不会发生冲突；

您可以将上述示例代码改为如下：

//File1

\#include<iostream>

usingnamespace std;

voidfn();

staticint n; //定义静态全局变量

intmain(void)

n = 20;

cout<<n<<endl;

fn();

return 0;

//File2

\#include<iostream>

usingnamespace std;

externint n;

voidfn()

n++;

cout<<n<<endl;

编译并运行这个程序，您就会发现上述代码可以分别通过编译，但运行时出现错误。试着将

staticint n; //定义静态全局变量

改为

intn; //定义全局变量

再次编译运行程序，细心体会全局变量和静态全局变量的区别。

2、静态局部变量

在局部变量前，加上关键字static，该变量就被定义成为一个静态局部变量。

我们先举一个静态局部变量的例子，如下：

\#include<iostream>

usingnamespace std;

voidfn();

intmain(void)

fn();

return 0;

voidfn()

static int n = 10;

cout<<n<<endl;

n++;

通常，在函数体内定义了一个变量，每当程序运行到该语句时都会给该局部变量分配栈内存。但随着程序退出函数体，系统就会收回栈内存，局部变量也相应失效。

但有时候我们需要在两次调用之间对变量的值进行保存。通常的想法是定义一个全局变量来实现。但这样一来，变量已经不再属于函数本身了，不再仅受函数的控制，给程序的维护带来不便。

静态局部变量正好可以解决这个问题。静态局部变量保存在全局数据区，而不是保存在栈中，每次的值保持到下一次调用，直到下次赋新值。

静态局部变量有以下特点：

（1）该变量在全局数据区分配内存；

（2）静态局部变量在程序执行到该对象的声明处时被首次初始化，即以后的函数调用不再进行初始化；

（3）静态局部变量一般在声明处初始化，如果没有显式初始化，会被程序自动初始化为0；

（4）它始终驻留在全局数据区，直到程序运行结束。但其作用域为局部作用域，当定义它的函数或语句块结束时，其作用域随之结束；

3、静态函数

在函数的返回类型前加上static关键字,函数即被定义为静态函数。静态函数与普通函数不同，它只能在声明它的文件当中可见，不能被其它文件使用。

静态函数的例子：

\#include<iostream>

usingnamespace std;

staticvoid fn(); //声明静态函数

intmain(void)

fn();

return 0;

voidfn() //定义静态函数

int n = 10;

cout<<n<<endl;

定义静态函数的好处：

静态函数不能被其它文件所用；

其它文件中可以定义相同名字的函数，不会发生冲突；

二、面向对象的static关键字（类中的static关键字）

1、静态数据成员

在类内数据成员的声明前加上关键字static，该数据成员就是类内的静态数据成员。先举一个静态数据成员的例子。

\#include<iostream>

usingnamespace std;

classMyclass

private:

int a , b , c;

static int sum; //声明静态数据成员

public:

Myclass(int a , int b , int c);

void GetSum();

\};

intMyclass::sum = 0; //定义并初始化静态数据成员

Myclass::Myclass(inta , int b , int c)

this->a = a;

this->b = b;

this->c = c;

sum += a+b+c;

voidMyclass::GetSum()

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

intmain(void)

Myclass M(1 , 2 , 3);

M.GetSum();

Myclass N(4 , 5 , 6);

N.GetSum();

M.GetSum();

return 0;

可以看出，静态数据成员有以下特点：

对于非静态数据成员，每个类对象都有自己的拷贝。而静态数据成员被当作是类的成员。无论这个类的对象被定义了多少个，静态数据成员在程序中也只有一份拷贝，由该类型的所有对象共享访问。也就是说，静态数据成员是该类的所有对象所共有的。对该类的多个对象来说，静态数据成员只分配一次内存，供所有对象共用。所以，静态数据成员的值对每个对象都是一样的，它的值可以更新；

静态数据成员存储在全局数据区。静态数据成员定义时要分配空间，所以不能在类声明中定义。在Example 5中，语句int Myclass::Sum=0;是定义静态数据成员；

静态数据成员和普通数据成员一样遵从public,protected,private访问规则；

因为静态数据成员在全局数据区分配内存，属于本类的所有对象共享，所以，它不属于特定的类对象，在没有产生类对象时其作用域就可见，即在没有产生类的实例时，我们就可以操作它；

静态数据成员初始化与一般数据成员初始化不同。静态数据成员初始化的格式为：

＜数据类型＞＜类名＞::＜静态数据成员名＞=＜值＞

类的静态数据成员有两种访问形式：

＜类对象名＞.＜静态数据成员名＞ 或 ＜类类型名＞::＜静态数据成员名＞

如果静态数据成员的访问权限允许的话（即public的成员），可在程序中，按上述格式来引用静态数据成员 ；

静态数据成员主要用在各个对象都有相同的某项属性的时候。比如对于一个存款类，每个实例的利息都是相同的。所以，应该把利息设为存款类的静态数据成员。这有两个好处，第一，不管定义多少个存款类对象，利息数据成员都共享分配在全局数据区的内存，所以节省存储空间。第二，一旦利息需要改变时，只要改变一次，则所有存款类对象的利息全改变过来了；

同全局变量相比，使用静态数据成员有两个优势：

静态数据成员没有进入程序的全局名字空间，因此不存在与程序中其它全局名字冲突的可能性；

可以实现信息隐藏。静态数据成员可以是private成员，而全局变量不能；

2、静态成员函数

与静态数据成员一样，我们也可以创建一个静态成员函数，它为类的全部服务而不是为某一个类的具体对象服务。静态成员函数与静态数据成员一样，都是类的内部实现，属于类定义的一部分。普通的成员函数一般都隐含了一个this指针，this指针指向类的对象本身，因为普通成员函数总是具体的属于某个类的具体对象的。通常情况下，this是缺省的。如函数fn()实际上是this->fn()。但是与普通函数相比，静态成员函数由于不是与任何的对象相联系，因此它不具有this指针。从这个意义上讲，它无法访问属于类对象的非静态数据成员，也无法访问非静态成员函数，它只能调用其余的静态成员函数。下面举个静态成员函数的例子。

\#include<iostream>

usingnamespace std;

classMyclass

private:

int a , b , c;

static int sum; //声明静态数据成员

public:

Myclass(int a , int b , int c);

static void GetSum(); //声明静态成员函数

\};

intMyclass::sum = 0; //定义并初始化静态数据成员

Myclass::Myclass(inta , int b , int c)

this->a = a;

this->b = b;

this->c = c;

sum += a+b+c; //非静态成员函数可以访问静态数据成员

voidMyclass::GetSum() //静态成员函数的实现

//cout<<a<<endl; //错误代码，a是非静态数据成员

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

intmain(void)

Myclass M(1 , 2 , 3);

M.GetSum();

Myclass N(4 , 5 , 6);

N.GetSum();

Myclass::GetSum();

return 0;

关于静态成员函数，可以总结为以下几点：

出现在类体外的函数定义不能指定关键字static；

静态成员之间可以相互访问，包括静态成员函数访问静态数据成员和访问静态成员函数；

非静态成员函数可以任意地访问静态成员函数和静态数据成员；

静态成员函数不能访问非静态成员函数和非静态数据成员；

由于没有this指针的额外开销，因此静态成员函数与类的全局函数相比速度上会有少许的增长；

调用静态成员函数，可以用成员访问操作符(.)和(->)为一个类的对象或指向类对象的指针调用静态成员函数，也可以直接使用如下格式：

＜类名＞::＜静态成员函数名＞（＜参数表＞）

调用类的静态成员函数。

写string类的构造，析构，拷贝函数——这题大约出现过4次左右，包括编程和程序填空，程序员面试宝典上有这题，也算是个经典笔试题，出现几率极大

\#include<iostream>

usingnamespace std;

classString\{

public:

String(const char \*str);

String(const String &other);

String &operator =(const String&other);

show();

~String();

private:

char \*str\_data;

\};

String::String(constchar \*str=NULL)

if (str == NULL)

str\_data = new char\[1\];

str\_data\[0\] = '\\0';

else

int len = strlen(str);

str\_data = new char\[len+1\];

strncpy(str\_data, str, len+1);

String::String(constString &other)

int len = strlen(other.str\_data);

str\_data = new char\[len + 1\];

strncpy(str\_data, other.str\_data,len+1);

String&String::operator =(const String &other)

if (this == &other)

return \*this;

else

delete\[\] str\_data;

int len =strlen(other.str\_data);

str\_data = new char\[len + 1\];

strncpy(str\_data,other.str\_data, len+1);

return \*this;

String::~String()\{

delete\[\] str\_data;

String::show()

cout << str\_data << endl;

intmain()

char \*a = "abcdef";

char \*b = "1234";

String m(a);

String n;

m = n;

m.show();

n.show();

getchar();

有一个整数数组，请求出两两之差绝对值最小的值，记住，只要得出最小值即可，不需要求出是哪两个数。

\#include<iostream>

\#include<algorithm>

usingnamespace std;

int a\[\]= \{-3,4,2,7,25,0,8,-2\};

intmain()

int len =sizeof(a)/sizeof(int);

sort(a,a+len);//调用sort(b,e)方法

int min =50;

for(int i=len-1; i>0;i--)

min =(abs(a\[i\]-a\[i-1\])>min)?min:abs(a\[i\]-a\[i-1\]);

cout<<"min"<<min<<endl;

getchar();

return 0;

最近点对：

最近点对\_分治算法O(nlgn)

思路：对所有点先按x不减排序，二分x，得到点集S1，点集S2，通过递归求得S1，S2的最小点对距离d1，d2；D=min\{d1,d2\}；合并S1，S2：找到在S1，S2划分线左右距离为D的所有点，按y不减(不增也可以)排序 循环每个点找它后面6个点的最小距离；最后即求得最小点对距离。若要求得点对坐标，在求值是保存点的坐标即可。

平面上N个点，没两个点都确定一条直线，求出斜率最大的那条直线所通过的两个点（斜率不存在的情况不考虑）。时间效率越高越好。

可以证明，一个点与它相邻的点相连时斜率最大。

先把N个点按x排序。斜率k最大值为max(斜率(point\[i\],point\[i+1\])) 0 <=i <n-2。

复杂度Nlog(N)。

写一个函数，检查字符是否是整数，如果是，返回其整数值。

longstrtoint(char \*str,int length)\{

if(length > 1) \{

return str\[0\]=='-' ? strtoint(str,length-1)\*10-(str\[length-1\]-'0') : strtoint(str,length-1)\*10+str\[length-1\]-'0';

\} else \{

return str\[0\]=='-' ? -1/10 :str\[0\]-'0';

怎样编写一个程序，把一个有序整数数组放到二叉树中

\#include<iostream>

usingnamespace std;

structTreeNode

int m\_nValue;

TreeNode \*m\_pLeft;

TreeNode \*m\_pRight;

\};

//把一个有序整数数组放到二叉树

voidRecurCreateTree(int \*p, int length, TreeNode \*&pHead)

if (length > 0)

pHead = new TreeNode;

int mid = length / 2;

pHead->m\_nValue = p\[mid\];

pHead->m\_pLeft = NULL;

pHead->m\_pRight = NULL;

RecurCreateTree(p, mid,pHead->m\_pLeft);

RecurCreateTree(p + mid + 1,length - mid - 1, pHead->m\_pRight);;

else

pHead = NULL;

//中序递归遍历

voidMidRecurTraversal(TreeNode\* pHead)

if (NULL != pHead)

MidRecurTraversal(pHead->m\_pLeft);

cout << pHead->m\_nValue<< " ";

MidRecurTraversal(pHead->m\_pRight);

intmain(int argc, char\* argv\[\])

int arr\[\] = \{ 1, 2, 3, 4, 5, 6, 7, 8,9, 10, 11, 12 \};

TreeNode \*pHead = NULL;

RecurCreateTree(arr, sizeof(arr) /sizeof(arr\[0\]), pHead);

MidRecurTraversal(pHead);

cout << endl;

getchar();

return 0;

怎样从顶部开始逐层打印二叉树结点数据？请编程

voidPrint2(Node \*root)

queue<Node\*> q;

q.push(root);

while(!q.empty())

Node \*t = q.front();

q.pop();

cout << t->v;

if (t->lchild) q.push(t->lchild);

if (t->rchild) q.push(t->rchild);

cout << endl;

编程实现两个正整数的除法

思路 ： 100/7，可以试着7\*1,7\*2, 7\*3, ... ,7\*14做，但这样子太慢了。于是有人说以2的指数次递增，也就是7\*1,7\*2,7\*4,7\*8，好了，因为7\*16>100，所以这个时候就100-7\*8=44接着下一次循环。

可以这里理解了。100 = 7 \* 8 +7 \* 4+7\*2 + 2.

\#include<iostream>

usingnamespace std;

intdiv1(const int x, const int y) \{

int left\_num = x;

int result = 0;

while (left\_num >= y) \{

int multi = 1;

while (y \* multi <=(left\_num >> 1)) \{

multi = multi <<1;

result += multi;

left\_num -= y \* multi;

return result;

intmain()

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

getchar();

return 0;

在排序数组中，找出给定数字的出现次数。比如\[1, 2, 2, 2, 3\] 中2的出现次数是3次

\#include<iostream>

usingnamespace std;

voidequal\_range1(int a\[\], int len, int x)

int low = 0, high = len - 1;

int mid;

int count = 0;

while (low <= high)

mid = (low + high) / 2;

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

//cout << mid<< endl;

break;

else if(x<mid)

high = mid - 1;

else low = mid + 1;

if (low>high)

cout << "没有找到"<< x << endl;

else

int k = mid - 1;

while (k >= 0 &&a\[k\] == x)

//cout << k--<< endl;

k--;

count++;

k = mid + 1;

count++;

while (k <= len - 1&& a\[k\] == x)

//cout << k++<< endl;

k++;

count++;

cout << count << endl;

intmain()

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

equal\_range1(a, 7, 3);

getchar();

return 0;

一个整数数列，元素取值可能是0~65535中的任意一个数，相同数值不会重复出现。0是例外，可以反复出现。

插入排序-》最大值-最小值<=4

给你一个凸多边形，你怎么用一条线，把它分成面积相等的两部分

方法很简单，不论它是个怎么样的不规则图形，都存在一条直线把它分成面积相等和两部分只需在图形上任找一个点然后通过这个点挂一根细线，等图形固定后，通过这条细线的直线就把它分成面积相等的两部分。理由：因为等图形固定后，通过这条细线分成的两部分实际重量是相等的，而平面图形的质地是均匀的，因此重量相等实际就是这个平面图形的面积相等

给出两个二叉树的根结点，判断这两个二叉树是否同构，同构即表示两棵树形状形式，只是value不同而已。

bool\_istongG(Node\* t1, Node\* t2)

if(NULL == t1 || NULL == t2)

return (NULL == t1) && (NULL ==t2);

return \_istongG(t1->left, t2->left)&& \_istongG(t1->right, t2->right)；

Map set(底层基于红黑树实现)的操作

手写快排非递归实现；

\#include<iostream>

\#include<stack>

usingnamespace std;

int partition(int\*a, int low, int high)

int temp = a\[low\];

while (low < high)

while(low<high&&a\[high\] > temp)

high--;

a\[low\] = a\[high\];

while(low<high&&a\[low\] <= temp)

low++;

a\[high\] = a\[low\];

a\[low\] = temp;

return low;

void quick(int\*a, int low, int high)

if (low < high)

int mid = partition(a, low,high);

stack<int> s;

if (mid - 1 > low)

s.push(low);

s.push(mid - 1);

if (mid + 1 < high)

s.push(mid + 1);

s.push(high);

while (!s.empty())

high = s.top();

s.pop();

low = s.top();

s.pop();

mid = partition(a,low, high);

if (mid - 1 > low)

s.push(low);

s.push(mid -1);

if (mid + 1 < high)

s.push(mid +1);

s.push(high);

intmain(void)

int i, a\[11\] = \{ 20, 11, 12, 5, 6, 13,8, 9, 14, 7, 10 \};

printf("排序前的数据为：\\n");

for (i = 0; i < 11; ++i)

printf("%d ", a\[i\]);

printf("\\n");

//qsort(a , 0 , 10);

quick(a, 0, 10);

printf("排序后的数据为：\\n");

for (i = 0; i < 11; ++i)

printf("%d", a\[i\]);

printf("\\n");

getchar();

return 0;

用最快速度求两个数组之交集算法。

比如A=\{6，2，4，1\},B=\{2，9，4，3\}，那么A&B=\{2，4\}。

算法一：在大多数情况，也就是一般的情况下，大家都能想出最暴力的解法，通常也就是采用遍历或者枚举的办法来解决问题。

该题需要找出两个数组的交集，最简单的一个办法就是用A数组里面的所有数去匹配B数组里面的数。假设两个数组的大小都是n，那么这种遍历的时间复杂度为O(n^2)。这个也是最复杂的情况了。

算法二：通常下，除了用暴力枚举的问题，还有另外一种外万金油的解法----预处理。其实思想和C语言中的预处理一样，对数据记性归一化处理。说白了，在这里就是对数组排序。我们知道数组排序的算法时间复杂度最低是O(nlogn)，可以看到数量级已经低于算法一的时间复杂度。

那么在排好序好，怎么得到数组的交集呢？

假设我们已经有了两个排好序的数组：

A=\{1，2，4，6\}

B=\{2，3，4，9\}

那么我们只要分别对A和B设置两个指针i,j（或者直接说是下标），进行循环，伪代码如下：

int count()

total=i=j=0;

while(i<n&& j<n)

if(a\[i\]<b\[j\])i++;

elseif(a\[i\]>b\[j\])j++

else

total++;

return total;

时间复杂度为O(n)

综合排序的时间复杂度则整体复杂度为：O(nlogn)

算法三：如果只是会了上面两种，还只能说是计算机的菜鸟，而且一般面试或者笔试题也不会这么简单。那么比O(nlogn)时间复杂度更低的是多少呢？一般就是O(n)。我们可以思考一下计数排序的算法。也就是把两个数组A和B都遍历到一个新的数组里，然后在统计重复的数字即可，这个时间复杂度就是O(n)。当然，计数排序是有条件的，也就是要求数组内数字的范围是已知并且不是很大。

算法四：上面的算法实现简单，也很容易达到题目的要求，但是还是有一些瑕疵，也就是非完美方案，同样根据算法三我们可以想出用哈希函数或者哈希表来解决问题。也就是将数组A哈希到哈希表中，然后继续将数组B哈希到哈希表中，如果发生哈希碰撞则统计加1，最后可以得出数组的交集。时间复杂度也就是哈希所有元素的复杂度O(n)。

提示词实现Trie树+hash

Hash表记录的存储特性是，存储在附近的记录没有任何关系，只能进行单记录精确查找！

而Tire树相对于Hash表虽然查找效率低，但：

1、可以快速完成大量记录的部分匹配

2、应该还能用文件存储聚集的类似数据，以应对内存的不足

文章最短摘要生成

解法：使用双指针，双指针对于很多算法设计很有价值。

算法的思想是采用两个指针，开始两个指针都指向缓冲区的头部，尾指针向后扫描，直到头指针和尾指针中间包含了全部的关键字，那么头指针向后移动，直到包含全部关键字这个条件失败，这时截取字串并和已取得的最小字串比较，如果小则替换。头指针、尾指针都向后一个位置(这点很重要，开始就忘记了移动头指针，导致程序出错)，继续扫描。

另外，由于一个关键字可能重复多次，因此在判断是否包含全部关键字时要采用计数机制，才能保证查看的准确。这样只要头指针和尾指针扫描两次字符串就可以完成生成算法。

\#include<iostream>

\#include<string>

\#include<map>

usingnamespace std;

classKeyWordChecker \{

public:

KeyWordChecker() :current\_state\_(false) \{\}

void AddKeyWord(const std::string&word) \{

if (keywords\_.find(word) ==keywords\_.end()) \{

keywords\_\[word\] = 0;

bool IsContainAllKeyWord(conststd::string& word, bool add) \{

if (keywords\_.find(word) ==keywords\_.end()) \{

return current\_state\_;

if (add) \{

keywords\_\[word\]++;

else \{

keywords\_\[word\]--;

std::map<std::string,int>::iterator begin = keywords\_.begin();

int counter = 0;

while (begin != keywords\_.end())\{

if (begin->second> 0) \{

counter++;

else \{

break;

begin++;

if (counter ==keywords\_.size()) \{

current\_state\_ = true;

return true;

else \{

current\_state\_ =false;

return false;

private:

std::map<std::string, int>keywords\_;

bool current\_state\_;

\};

std::stringGenerateSnippet(const std::string& content, KeyWordChecker\*keyword\_checker) \{

int begin = 0;

int end = 0;

std::string snippet;

int min\_length = content.size();

while (end < content.size()) \{

if(!keyword\_checker->IsContainAllKeyWord(std::string(1, content\[end\]), true))\{

end++;

continue;

while (begin <= end&& keyword\_checker->

IsContainAllKeyWord(std::string(1,content\[begin\]), false)) \{

begin++;

if (end - begin + 1 <min\_length) \{

snippet =content.substr(begin, end - begin + 1);

min\_length = end -begin + 1;

end++;

begin++;

return snippet;

intmain(int argc, char\*\* argv) \{

std::string content ="abbbbbcaaadebmmmmdcfg";

KeyWordChecker keyword\_checker;

keyword\_checker.AddKeyWord("b");

keyword\_checker.AddKeyWord("d");

std::string snippet =GenerateSnippet(content, &keyword\_checker);

//printf("snippet:%s\\n",snippet.c\_str());

cout << snippet.c\_str();

getchar();

1、试着用最小的比较次数去寻找数组中的最大值和最小值。

解法一：

扫描一次数组找出最大值；再扫描一次数组找出最小值。

比较次数2N-2

解法二：

将数组中相邻的两个数分在一组， 每次比较两个相邻的数，将较大值交换至这两个数的左边，较小值放于右边。

对大者组扫描一次找出最大值，对小者组扫描一次找出最小值。

比较1.5N-2次，但需要改变数组结构

解法三：

每次比较相邻两个数，较大者与MAX比较，较小者与MIN比较，找出最大值和最小值。

C++中虚函数工作原理和(虚)继承类的内存占用大小计算

一、虚函数的工作原理

虚函数的实现要求对象携带额外的信息，这些信息用于在运行时确定该对象应该调用哪一个虚函数。典型情况下，这一信息具有一种被称为 vptr（virtual table pointer，虚函数表指针）的指针的形式。vptr 指向一个被称为 vtbl（virtual table，虚函数表）的函数指针数组，每一个包含虚函数的类都关联到 vtbl。当一个对象调用了虚函数，实际的被调用函数通过下面的步骤确定：找到对象的 vptr 指向的 vtbl，然后在 vtbl 中寻找合适的函数指针。

虚拟函数的地址翻译取决于对象的内存地址，而不取决于数据类型(编译器对函数调用的合法性检查取决于数据类型)。如果类定义了虚函数，该类及其派生类就要生成一张虚拟函数表，即vtable。而在类的对象地址空间中存储一个该虚表的入口，占4个字节，这个入口地址是在构造对象时由编译器写入的。所以，由于对象的内存空间包含了虚表入口，编译器能够由这个入口找到恰当的虚函数，这个函数的地址不再由数据类型决定了。故对于一个父类的对象指针，调用虚拟函数，如果给他赋父类对象的指针，那么他就调用父类中的函数，如果给他赋子类对象的指针，他就调用子类中的函数(取决于对象的内存地址)。

虚函数需要注意的大概就是这些个地方了，之前在More effective C++上好像也有见过，不过这次在Visual C++权威剖析这本书中有了更直白的认识，这本书名字很牛逼，看看内容也就那么回事，感觉名不副实，不过说起来也是有其独到之处的，否则也没必要出这种书了。

每当创建一个包含有虚函数的类或从包含有虚函数的类派生一个类时，编译器就会为这个类创建一个虚函数表（VTABLE）保存该类所有虚函数的地址，其实这个VTABLE的作用就是保存自己类中所有虚函数的地址，可以把VTABLE形象地看成一个函数指针数组，这个数组的每个元素存放的就是虚函数的地址。在每个带有虚函数的类中，编译器秘密地置入一指针，称为v p o i n t e r（缩写为V P T R），指向这个对象的V TA B L E。当构造该派生类对象时，其成员VPTR被初始化指向该派生类的VTABLE。所以可以认为VTABLE是该类的所有对象共有的，在定义该类时被初始化；而VPTR则是每个类对象都有独立一份的，且在该类对象被构造时被初始化。

通过基类指针做虚函数调用时（也就是做多态调用时），编译器静态地插入取得这个VPTR，并在VTABLE表中查找函数地址的代码，这样就能调用正确的函数使晚捆绑发生。为每个类设置VTABLE、初始化VPTR、为虚函数调用插入代码，所有这些都是自动发生的，所以我们不必担心这些。

\#include<iostream>

usingnamespace std;

class A

public:

virtual void fun1()

cout << "A::fun1()"<< endl;

virtual void fun2()

cout << "A::fun2()"<< endl;

\};

class B : public A

public:

void fun1()

cout << "B::fun1()"<< endl;

void fun2()

cout << "B::fun2()"<< endl;

\};

int main()

A \*pa = new B;

pa->fun1();

delete pa;

system("pause");

return 0;

毫无疑问，调用了B::fun1()，但是B::fun1()不是像普通函数那样直接找到函数地址而执行的。真正的执行方式是：首先取出pa指针所指向的对象的vptr的值，这个值就是vtbl的地址，由于调用的函数B::fun1()是第一个虚函数，所以取出vtbl第一个表项里的值，这个值就是B::fun1()的地址了，最后调用这个函数。因此只要vptr不同，指向的vtbl就不同，而不同的vtbl里装着对应类的虚函数地址，所以这样虚函数就可以完成它的任务，多态就是这样实现的。

而对于class A和class B来说，他们的vptr指针存放在何处？其实这个指针就放在他们各自的实例对象里。由于class A和class B都没有数据成员，所以他们的实例对象里就只有一个vptr指针。

虚拟函数使用的缺点

优点讲了一大堆，现在谈一下缺点，虚函数最主要的缺点是执行效率较低，看一看虚拟函数引发的多态性的实现过程，你就能体会到其中的原因，另外就是由于要携带额外的信息（VPTR），所以导致类多占的内存空间也会比较大，对象也是一样的。

含有虚函数的对象在内存中的结构如下:

classA

private:

int a;

int b;

public:

virtual void fun0()

cout<<"A::fun0"<<endl;

\};

1、直接继承

那我们来看看编译器是怎么建立VPTR指向的这个虚函数表的，先看下面两个类：

classbase

private:

int a;

public:

void bfun()

virtual void vfun1()

virtual void vfun2()

\};

classderived : public base

private:

int b;

public:

void dfun()

virtual void vfun1()

virtual void vfun3()

\};

每当创建一个包含有虚函数的类或从包含有虚函数的类派生一个类时，编译器就为这个类创建一个VTABLE。在这个表中，编译器放置了在这个类中或在它的基类中所有已声明为virtual的函数的地址。如果在这个派生类中没有对在基类中声明为virtual的函数进行重新定义，编译器就使用基类的这个虚函数地址。（在derived的VTABLE中，vfun2的入口就是这种情况。）然后编译器在这个对象中放置VPTR。当使用简单继承时，对于每个对象只有一个VPTR。VPTR必须被初始化为指向相应的VTABLE，这在构造函数中发生。

一旦VPTR被初始化为指向相应的VTABLE，对象就"知道"它自己是什么类型。但只有当虚函数被调用时这种自我认知才有用。

没有虚函数类对象的大小正好是数据成员的大小，包含有一个或者多个虚函数的类对象编译器向里面插入了一个VPTR指针(void \*)，指向一个存放函数地址的表就是我们上面说的VTABLE，这些都是编译器为我们做的我们完全可以不关心这些。所以有虚函数的类对象的大小是数据成员的大小加上一个VPTR指针(void \*)的大小。

总结一下VPTR 和 VTABLE 和类对象的关系:

每一个具有虚函数的类都有一个虚函数表VTABLE，里面按在类中声明的虚函数的顺序存放着虚函数的地址，这个虚函数表VTABLE是这个类的所有对象所共有的，也就是说无论用户声明了多少个类对象，但是这个VTABLE虚函数表只有一个。

在每个具有虚函数的类的对象里面都有一个VPTR虚函数指针，这个指针指向VTABLE的首地址，每个类的对象都有这么一种指针。

2、虚继承

这个是比较不好理解的，对于虚继承，若派生类有自己的虚函数，则它本身需要有一个虚指针，指向自己的虚表。另外，派生类虚继承父类时，首先要通过加入一个虚指针来指向父类，因此有可能会有两个虚指针。

二、(虚)继承类的内存占用大小

首先，平时所声明的类只是一种类型定义，它本身是没有大小可言的。 因此，如果用sizeof运算符对一个类型名操作，那得到的是具有该类型实体的大小。

计算一个类对象的大小时的规律：

1、空类、单一继承的空类、多重继承的空类所占空间大小为：1（字节，下同）；

2、一个类中，虚函数本身、成员函数（包括静态与非静态）和静态数据成员都是不占用类对象的存储空间的；

3、因此一个对象的大小≥所有非静态成员大小的总和；

4、当类中声明了虚函数（不管是1个还是多个），那么在实例化对象时，编译器会自动在对象里安插一个指针vPtr指向虚函数表VTable；

5、虚承继的情况：由于涉及到虚函数表和虚基表，会同时增加一个（多重虚继承下对应多个）vfPtr指针指向虚函数表vfTable和一个vbPtr指针指向虚基表vbTable，这两者所占的空间大小为：8（或8乘以多继承时父类的个数）；

6、在考虑以上内容所占空间的大小时，还要注意编译器下的“补齐”padding的影响，即编译器会插入多余的字节补齐；

7、类对象的大小=各非静态数据成员（包括父类的非静态数据成员但都不包括所有的成员函数）的总和+ vfptr指针(多继承下可能不止一个)+vbptr指针(多继承下可能不止一个)+编译器额外增加的字节。

示例一：含有普通继承

classA

\};

classB

char ch;

virtual void func0() \{ \}

\};

classC

char ch1;

char ch2;

virtual void func() \{ \}

virtual void func1() \{ \}

\};

class D:public A, public C

int d;

virtual void func() \{ \}

virtual void func1() \{ \}

\};

class E:public B, public C

int e;

virtual void func0() \{ \}

virtual void func1() \{ \}

\};

intmain(void)

cout<<"A="<<sizeof(A)<<endl; //result=1

cout<<"B="<<sizeof(B)<<endl; //result=8

cout<<"C="<<sizeof(C)<<endl; //result=8

cout<<"D="<<sizeof(D)<<endl; //result=12

cout<<"E="<<sizeof(E)<<endl; //result=20

return 0;

前面三个A、B、C类的内存占用空间大小就不需要解释了，注意一下内存对齐就可以理解了。

求sizeof(D)的时候，需要明白，首先VPTR指向的虚函数表中保存的是类D中的两个虚函数的地址，然后存放基类C中的两个数据成员ch1、ch2，注意内存对齐，然后存放数据成员d，这样4+4+4=12。

求sizeof(E)的时候，首先是类B的虚函数地址，然后类B中的数据成员，再然后是类C的虚函数地址，然后类C中的数据成员，最后是类E中的数据成员e，同样注意内存对齐，这样4+4+4+4+4=20。

示例二：含有虚继承

classCommonBase

int co;

\};

classBase1: virtual public CommonBase

public:

virtual void print1() \{ \}

virtual void print2() \{ \}

private:

int b1;

\};

classBase2: virtual public CommonBase

public:

virtual void dump1() \{ \}

virtual void dump2() \{ \}

private:

int b2;

\};

classDerived: public Base1, public Base2

public:

void print2() \{ \}

void dump2() \{ \}

private:

int d;

\};

sizeof(Derived)=32，其在内存中分布的情况如下：

classDerived size(32):

\+---

| +--- (base class Base1)

| | \{vfptr\}

| | \{vbptr\}

| | b1

| +---

| +--- (base class Base2)

| | \{vfptr\}

| | \{vbptr\}

| | b2

| +---

| d

\+---

\+--- (virtual base CommonBase)

| co

\+---

示例3：

classA

public:

virtual void aa() \{ \}

virtual void aa2() \{ \}

private:

char ch\[3\];

\};

class B:virtual public A

public:

virtual void bb() \{ \}

virtual void bb2() \{ \}

\};

intmain(void)

cout<<"A's size is"<<sizeof(A)<<endl;

cout<<"B's size is"<<sizeof(B)<<endl;

return 0;

执行结果：A's size is 8

B's size is 16

说明：对于虚继承，类B因为有自己的虚函数，所以它本身有一个虚指针，指向自己的虚表。另外，类B虚继承类A时，首先要通过加入一个虚指针来指向父类A，然后还要包含父类A的所有内容。因此是4+4+8=16。

两种多态实现机制及其优缺点

除了c++的这种多态的实现机制之外，还有另外一种实现机制，也是查表，不过是按名称查表，是smalltalk等语言的实现机制。这两种方法的优缺点如下：

（1）、按照绝对位置查表，这种方法由于编译阶段已经做好了索引和表项(如上面的call \*(pa->vptr\[1\]) )，所以运行速度比较快；缺点是：当A的virtual成员比较多（比如1000个），而B重写的成员比较少（比如2个），这种时候，B的vtableＢ的剩下的998个表项都是放Ａ中的vitruel成员函数的指针，如果这个派生体系比较大的时候，就浪费了很多的空间。

比如：ＧＵＩ库，以ＭＦＣ库为例，ＭＦＣ有很多类，都是一个继承体系；而且很多时候每个类只是１，２个成员函数需要在派生类重写，如果用Ｃ＋＋的虚函数机制，每个类有一个虚表，每个表里面有大量的重复，就会造成空间利用率不高。于是ＭＦＣ的消息映射机制不用虚函数，而用第二种方法来实现多态，那就是：

（２）、按照函数名称查表，这种方案可以避免如上的问题；但是由于要比较名称，有时候要遍历所有的继承结构，时间效率性能不是很高。（关于ＭＦＣ的消息映射的实现，看下一篇文章）

３、总结：

如果继承体系的基类的virtual成员不多，而且在派生类要重写的部分占了其中的大多数时候，用Ｃ＋＋的虚函数机制是比较好的；

但是如果继承体系的基类的virtual成员很多，或者是继承体系比较庞大的时候，而且派生类中需要重写的部分比较少，那就用名称查找表，这样效率会高一些，很多的ＧＵＩ库都是这样的，比如ＭＦＣ，ＱＴ。

ＰＳ：其实，自从计算机出现之后，时间和空间就成了永恒的主题，因为两者在98%的情况下都无法协调，此长彼消；这个就是计算机科学中的根本瓶颈之所在。软件科学和算法的发展，就看能不能突破这对时空权衡了。呵呵。。

何止计算机科学如此，整个宇宙又何尝不是如此呢？最基本的宇宙之谜，还是时间和空间。

C++如何不用虚函数实现多态

可以考虑使用函数指针来实现多态

\#include<iostream>

usingnamespace std;

typedefvoid (\*fVoid)();

classA

public:

static void test()

printf("hello A\\n");

fVoid print;

A()

print = A::test;

\};

class B : public A

public:

static void test()

printf("hello B\\n");

B()

print = B::test;

\};

intmain(void)

A aa;

aa.print();

B b;

A\* a = &b;

a->print();

return 0;

这样做的好处主要是绕过了vtable。我们都知道虚函数表有时候会带来一些性能损失。

快排、堆排

voidQuickSort(int \*a, int left,int right)

if (left > right)

return;

int x = a\[left\];

int i = left;

int j = right;

while (i < j)

while (i<j&&a\[j\] >x)

j--;

if (i < j)

a\[i++\] = a\[j\];

while (i<j&&a\[i\] <x)

i++;

if (i < j)

a\[j--\] = a\[i\];

a\[i\] = x;

QuickSort(a,left,i-1);

QuickSort(a,i+1, right);

voidHeapfy(int A\[\], int idx, int max) //建立最大堆

int left = idx \* 2 + 1;

int right = left + 1;

int largest = idx;

if(left<max&&A\[left\]>A\[idx\])\{ largest = left; \}

if (right<max&&A\[largest\]<A\[right\])\{largest = right; \}

if (largest != idx)

int temp = A\[largest\];

A\[largest\] = A\[idx\];

A\[idx\] = temp;

Heapfy(A, largest, max);

voidHeapSort(int A\[\], int ll)

int len = ll;

for (int i = len / 2 - 1; i >= 0;--i)

Heapfy(A, i, len);

for (int i = len - 1; i >= 1; --i)

int temp = A\[0\];

A\[0\] = A\[i\];

A\[i\] = temp;

Heapfy(A, 0, i);

intmain()

int a\[\] = \{ 3, 2, 5, 1, 3, 7, 6, 8 \};

int n = sizeof(a) / sizeof(a\[0\]);

//DoubleBubbleSort(a, n);

//MergeSort(a, 0, n-1);

//QuickSort(a, 0, n - 1);

//ShellSort(a, n);

HeapSort(a, n);

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

cout << a\[i\] << '\\t';

getchar();

TCP和UDP的区别以及应用有什么不同？

答：TCP与UDP的区别

TCP---传输控制协议,提供的是面向连接、可靠的字节流服务。当客户和服务器彼此交换数据前，必须先在双方之间建立一个TCP连接，之后才能传输数据。TCP提供超时重发，丢弃重复数据，检验数据，流量控制等功能，保证数据能从一端传到另一端。

UDP---用户数据报协议，是一个简单的面向数据报的运输层协议。UDP不提供可靠性，它只是把应用程序传给IP层的数据报发送出去，但是并不能保证它们能到达目的地。由于UDP在传输数据报前不用在客户和服务器之间建立一个连接，且没有超时重发等机制，故而传输速度很快。

应用： HTTP协议在运输层采用的就是TCP协议，在浏览器中输入IP地址后，与服务器建立连接，采用的就是TCP协议，是一种面向连接、可靠的字节流服务。

当强调传输性能而不是传输的完整性时，如：音频、多媒体应用和视频会议时，UDP是最好的选择。另外，腾讯QQ采用也是UDP协议。

UDP

UDP 与 TCP 的主要区别在于 UDP 不一定提供可靠的数据传输。事实上，该协议不能保证数据准确无误地到达目的地。UDP 在许多方面非常有效。当某个程序的目标是尽快地传输尽可能多的信息时（其中任意给定数据的重要性相对较低），可使用 UDP。ICQ 短消息使用 UDP 协议发送消息。

许多程序将使用单独的TCP连接和单独的UDP连接。重要的状态信息随可靠的TCP连接发送，而主数据流通过UDP发送。

TCP

TCP的目的是提供可靠的数据传输，并在相互进行通信的设备或服务之间保持一个虚拟连接。TCP在数据包接收无序、丢失或在交付期间被破坏时，负责数据恢复。它通过为其发送的每个数据包提供一个序号来完成此恢复。记住，较低的网络层会将每个数据包视为一个独立的单元，因此，数据包可以沿完全不同的路径发送，即使它们都是同一消息的组成部分。这种路由与网络层处理分段和重新组装数据包的方式非常相似，只是级别更高而已。

为确保正确地接收数据，TCP要求在目标计算机成功收到数据时发回一个确认（即 ACK）。如果在某个时限内未收到相应的 ACK，将重新传送数据包。如果网络拥塞，这种重新传送将导致发送的数据包重复。但是，接收计算机可使用数据包的序号来确定它是否为重复数据包，并在必要时丢弃它。

TCP与UDP的选择

如果比较UDP包和TCP包的结构，很明显UDP包不具备TCP包复杂的可靠性与控制机制。与TCP协议相同，UDP的源端口数和目的端口数也都支持一台主机上的多个应用。一个16位的UDP包包含了一个字节长的头部和数据的长度，校验码域使其可以进行整体校验。（许多应用只支持UDP，如：多媒体数据流，不产生任何额外的数据，即使知道有破坏的包也不进行重发。）

很明显，当数据传输的性能必须让位于数据传输的完整性、可控制性和可靠性时，TCP协议是当然的选择。当强调传输性能而不是传输的完整性时，如：音频和多媒体应用，UDP是最好的选择。在数据传输时间很短，以至于此前的连接过程成为整个流量主体的情况下，UDP也是一个好的选择，如：DNS交换。把SNMP建立在UDP上的部分原因是设计者认为当发生网络阻塞时，UDP较低的开销使其有更好的机会去传送管理数据。TCP丰富的功能有时会导致不可预料的性能低下，但是我们相信在不远的将来，TCP可靠的点对点连接将会用于绝大多数的网络应用。

解析：

实际生活中，一些事物往往会拥有两个或两个以上事物的属性，为了解决这个问题，C++引入了多重继承的概念，C++允许为一个派生类指定多个基类，这样的继承结构被称做多重继承。举个例子：

人（Person）可以派生出作家（Author）和程序员（Programmer），然而程序员作者同时拥有作家和程序员的两个属性，即既能编程又能写作，如下图所示。

多继承的概念和优缺点

使用多重继承的例子程序如下：

\#include<iostream>

usingnamespace std;

classPerson

public:

void sleep() \{cout <<"sleep" << endl;\}

void eat() \{cout <<"eat" << endl;\}

\};

classAuthor : public Person //Author继承自Person

public:

void writeBook() \{cout <<"write Book" << endl;\}

\};

class Programmer : public Person //Programmer继承自Person

public:

void writeCode() \{cout <<"write Code" << endl;\}

\};

class Programmer\_Author : public Programmer,public Author //多重继承

\};

int main()

Programmer\_Author pa;

pa.writeBook(); //调用基类Author的方法

pa.writeCode(); //调用基类Programmer的方法

pa.eat(); //编译错误，eat()定义不明确

pa.sleep(); //编译错误，sleep()定义不明确

return 0;

多重继承的优点很明显，就是对象可以调用多个基类中的接口，如代码31行与代码32行对象pa分别调用Author类的writeBook()函数和Programmer类的writeCode()函数。

多重继承的缺点是什么呢？如果派生类所继承的多个基类有相同的基类，而派生类对象需要调用这个祖先类的接口方法，就会容易出现二义性。代码33、34行就是因为这个原因而出现编译错误的。因为通过多重继承的Programmer\_Author类拥有Author类和Programmer类的一份拷贝，而Author类和Programmer类都分别拥有Person类的一份拷贝，所以Programmer\_Author类拥有Person类的两份拷贝，在调用Person类的接口时，编译器会不清楚需要调用哪一份拷贝，从而产生错误。对于这个问题通常有两个解决方案：

（1）加上全局符确定调用哪一份拷贝。比如pa.Author::eat()调用属于Author的拷贝。

（2）使用虚拟继承，使得多重继承类Programmer\_Author只拥有Person类的一份拷贝。比如在11行和17行的继承语句中加入virtual就可以了。

classAuthor : virtual public Person //Author虚拟继承自Person

classProgrammer : virtual public Person //Programmer虚拟继承自Person

多重继承的概念和优缺点？

答案：

实际生活中，一些事物往往会拥有两个或两个以上事物的属性，为了解决这个问题，C++引入了多重继承的概念。

多重继承的优点是对象可以调用多个基类中的接口。

多重继承的缺点是容易出现继承向上的二义性。

内联函数和宏的区别与联系

内联函数与宏定义

在C中，常用预处理语句\#define来代替一个函数定义。例如：

\#define MAX(a，b)((a)>(b)?(a):(b))

该语句使得程序中每个出现MAX(a,b)函数调用的地方都被宏定义中后面的表达式((a)>(b)?(a):(b))所替换。

宏定义语句的书写格式有过分的讲究，MAX与括号之间不能有空格，所有的参数都要

放在括号里。尽管如此，它还是有麻烦：

int a=1，b=0；

MAX(a++,b)； //a被增值2次

MAX(a++,b+10)； //a被增值1次

MAX(a,"Hello")； //错误地比较int和字符串，没有参数类型检查

MAX( )函数的求值会由于两个参数值的大小不同而产生不同的副作用。

MAX(a++,b)的值为2，同时a的值为3；

MAX(a++,b+10)的值为10，同时a的值为2。

如果是普通函数，则MAX(a,"HellO")会受到函数调用的检查，但此处不会因为两个参数类型不同而被编译拒之门外。幸运的是，通过一个内联函数可以得到所有宏的替换效能和所有可预见的状态以及常规函数的类型检查：

inline intMAX(int a，int b)

returna>b?a:b；

1.内联函数与宏的区别：

传统的宏定义函数可能会引起一些麻烦。

ex：

\#define F(x) x+x

void main()\{int i=1;F(i++);\}

这里x将被加两次。

内联函数被编译器自动的用函数的形势添加进代码，而不会出现这种情况。

内联函数的使用提高了效率（省去了很多函数调用汇编代码如：call和ret等）。

2.内联函数的使用：

所有在类的声明中定义的函数将被自动认为是内联函数。

class A()

void c();// not a inline function;

void d()\{ print("d() is ainline function.");\}

如果想将一个全局函数定义为内联函数可用，inline关键字。

inline a()\{print("a() is a inlinefunction.");\}

注意：

在内联函数中如果有复杂操作将不被内联。如：循环和递归调用。

总结：

将简单短小的函数定义为内联函数将会提高效率。

用内联取代宏代码

C++ 语言支持函数内联，其目的是为了提高函数的执行效率（速度）。

在C程序中，可以用宏代码提高执行效率。宏代码本身不是函数，但使用起来象函数。预处理器用复制宏代码的方式代替函数调用，省去了参数压栈、生成汇编语言的CALL调用、返回参数、执行return等过程，从而提高了速度。使用宏代码最大的缺点是容易出错，预处理器在复制宏代码时常常产生意想不到的边际效应。例如

\#defineMAX(a, b) (a) > (b) ? (a) : (b)

语句

result =MAX(i, j) + 2 ;

将被预处理器解释为

result =(i) > (j) ? (i) : (j) + 2 ;

由于运算符‘+’比运算符‘:’的优先级高，所以上述语句并不等价于期望的

result =( (i) > (j) ? (i) : (j) ) + 2 ;

如果把宏代码改写为

\#defineMAX(a, b) ( (a) > (b) ? (a) :(b) )

则可以解决由优先级引起的错误。但是即使使用修改后的宏代码也不是万无一失的，例如语句

result =MAX(i++, j);

将被预处理器解释为

result =(i++) > (j) ? (i++) : (j);

对于C++ 而言，使用宏代码还有另一种缺点：无法操作类的私有数据成员。

让我们看看C++ 的“函数内联”是如何工作的。对于任何内联函数，编译器在符号表里放入函数的声明（包括名字、参数类型、返回值类型）。如果编译器没有发现内联函数存在错误，那么该函数的代码也被放入符号表里。在调用一个内联函数时，编译器首先检查调用是否正确（进行类型安全检查，或者进行自动类型转换，当然对所有的函数都一样）。如果正确，内联函数的代码就会直接替换函数调用，于是省去了函数调用的开销。这个过程与预处理有显著的不同，因为预处理器不能进行类型安全检查，或者进行自动类型转换。假如内联函数是成员函数，对象的地址（this）会被放在合适的地方，这也是预处理器办不到的。

C++ 语言的函数内联机制既具备宏代码的效率，又增加了安全性，而且可以自由操作类的数据成员。所以在C++ 程序中，应该用内联函数取代所有宏代码，“断言assert”恐怕是唯一的例外。assert是仅在Debug版本起作用的宏，它用于检查“不应该”发生的情况。为了不在程序的Debug版本和Release版本引起差别，assert不应该产生任何副作用。如果assert是函数，由于函数调用会引起内存、代码的变动，那么将导致Debug版本与Release版本存在差异。所以assert不是函数，而是宏。

内联函数的编程风格

关键字inline必须与函数定义体放在一起才能使函数成为内联，仅将inline放在函数声明前面不起任何作用。如下风格的函数Foo不能成为内联函数：

inlinevoid Foo(int x, int y); // inline仅与函数声明放在一起

voidFoo(int x, int y)

…

而如下风格的函数Foo则成为内联函数：

voidFoo(int x, int y);

inlinevoid Foo(int x, int y) // inline与函数定义体放在一起

…

所以说，inline是一种“用于实现的关键字”，而不是一种“用于声明的关键字”。一般地，用户可以阅读函数的声明，但是看不到函数的定义。尽管在大多数教科书中内联函数的声明、定义体前面都加了inline关键字，但我认为inline不应该出现在函数的声明中。这个细节虽然不会影响函数的功能，但是体现了高质量C++/C程序设计风格的一个基本原则：声明与定义不可混为一谈，用户没有必要、也不应该知道函数是否需要内联。

定义在类声明之中的成员函数将自动地成为内联函数，例如

class A

public:

voidFoo(int x, int y) \{ … \} // 自动地成为内联函数

将成员函数的定义体放在类声明之中虽然能带来书写上的方便，但不是一种良好的编程风格，上例应该改成：

// 头文件

class A

public:

voidFoo(int x, int y)；

// 定义文件

inlinevoid A::Foo(int x, int y)

…

慎用内联

内联能提高函数的执行效率，为什么不把所有的函数都定义成内联函数？

如果所有的函数都是内联函数，还用得着“内联”这个关键字吗？

内联是以代码膨胀（复制）为代价，仅仅省去了函数调用的开销，从而提高函数的执行效率。如果执行函数体内代码的时间，相比于函数调用的开销较大，那么效率的收获会很少。另一方面，每一处内联函数的调用都要复制代码，将使程序的总代码量增大，消耗更多的内存空间。以下情况不宜使用内联：

（1）如果函数体内的代码比较长，使用内联将导致内存消耗代价较高。

（2）如果函数体内出现循环，那么执行函数体内代码的时间要比函数调用的开销大。

类的构造函数和析构函数容易让人误解成使用内联更有效。要当心构造函数和析构函数可能会隐藏一些行为，如“偷偷地”执行了基类或成员对象的构造函数和析构函数。所以不要随便地将构造函数和析构函数的定义体放在类声明中。

一个好的编译器将会根据函数的定义体，自动地取消不值得的内联（这进一步说明了inline不应该出现在函数的声明中）。

C++ 语言中的重载、内联、缺省参数、隐式转换等机制展现了很多优点，但是这些优点的背后都隐藏着一些隐患。正如人们的饮食，少食和暴食都不可取，应当恰到好处。我们要辨证地看待C++的新机制，应该恰如其分地使用它们。虽然这会使我们编程时多费一些心思，少了一些痛快，但这才是编程的艺术。

类的构造函数、析构函数与赋值函数

构造函数、析构函数与赋值函数是每个类最基本的函数。它们太普通以致让人容易麻痹大意，其实这些貌似简单的函数就象没有顶盖的下水道那样危险。

每个类只有一个析构函数和一个赋值函数，但可以有多个构造函数（包含一个拷贝构造函数，其它的称为普通构造函数）。对于任意一个类A，如果不想编写上述函数，C++编译器将自动为A产生四个缺省的函数，如

A(void);// 缺省的无参数构造函数

A(constA &a); // 缺省的拷贝构造函数

~A(void);// 缺省的析构函数

A &operate =(const A &a); // 缺省的赋值函数

这不禁让人疑惑，既然能自动生成函数，为什么还要程序员编写？

原因如下：

（1）如果使用“缺省的无参数构造函数”和“缺省的析构函数”，等于放弃了自主“初始化”和“清除”的机会，C++发明人Stroustrup的好心好意白费了。

（2）“缺省的拷贝构造函数”和“缺省的赋值函数”均采用“位拷贝”而非“值拷贝”的方式来实现，倘若类中含有指针变量，这两个函数注定将出错。

对于那些没有吃够苦头的C++程序员，如果他说编写构造函数、析构函数与赋值函数很容易，可以不用动脑筋，表明他的认识还比较肤浅，水平有待于提高。

本章以类String的设计与实现为例，深入阐述被很多教科书忽视了的道理。String的结构如下：

classString

public:

String(constchar \*str = NULL); // 普通构造函数

String(constString &other); // 拷贝构造函数

~String(void); // 析构函数

String& operate =(const String &other); // 赋值函数

private:

char \*m\_data; // 用于保存字符串

\};

使用信号量

一、什么是信号量

为了防止出现因多个程序同时访问一个共享资源而引发的一系列问题，我们需要一种方法，它可以通过生成并使用令牌来授权，在任一时刻只能有一个执行线程访问代码的临界区域。临界区域是指执行数据更新的代码需要独占式地执行。而信号量就可以提供这样的一种访问机制，让一个临界区同一时间只有一个线程在访问它，也就是说信号量是用来调协进程对共享资源的访问的。

信号量是一个特殊的变量，程序对其访问都是原子操作，且只允许对它进行等待（即P(信号变量))和发送（即V(信号变量))信息操作。最简单的信号量是只能取0和1的变量，这也是信号量最常见的一种形式，叫做二进制信号量。而可以取多个正整数的信号量被称为通用信号量。这里主要讨论二进制信号量。

二、信号量的工作原理

由于信号量只能进行两种操作等待和发送信号，即P(sv)和V(sv),他们的行为是这样的：

P(sv)：如果sv的值大于零，就给它减1；如果它的值为零，就挂起该进程的执行

V(sv)：如果有其他进程因等待sv而被挂起，就让它恢复运行，如果没有进程因等待sv而挂起，就给它加1.

举个例子，就是两个进程共享信号量sv，一旦其中一个进程执行了P(sv)操作，它将得到信号量，并可以进入临界区，使sv减1。而第二个进程将被阻止进入临界区，因为当它试图执行P(sv)时，sv为0，它会被挂起以等待第一个进程离开临界区域并执行V(sv)释放信号量，这时第二个进程就可以恢复执行。

fgets(s,n,f)

给你个例子：

\#include<stdio.h>

voidmain()

FILE\*stream;

charbuf\[128\];

stream=fopen("time.text","r");//打开文件（保证有该文件存在）

fgets(buf,128,stream);//读取字符

printf("%s\\n",buf);

fclose(stream);

如上例可见：

fgets（s,n,f）中的s为获得数据地址，n为获得数据的总字符数，f为需要读出字符的文件指针。上面长度为N,以数组来说，0开头，所以读取到buf\[n-1\]处。

设计范式（范式,数据库设计范式,数据库的设计范式）是符合某一种级别的关系模式的集合

范式说明

第一范式（1NF）：数据库表中的字段都是单一属性的，不可再分。这个单一属性由基本类型构成，包括整型、实数、字符型、逻辑型、日期型等

第二范式（2NF）：数据库表中不存在非关键字段对任一候选关键字段的部分函数依赖（部分函数依赖指的是存在组合关键字中的某些字段决定非关键字段的情况），也即所有非关键字段都完全依赖于任意一组候选关键字。

第三范式（3NF）：在第二范式的基础上，数据表中如果不存在非关键字段对任一候选关键字段的传递函数依赖则符合第三范式。所谓传递函数依赖，指的是如果存在"A → B → C"的决定关系，则C传递函数依赖于A。因此，满足第三范式的数据库表应该不存在如下依赖关系：关键字段 → 非关键字段x → 非关键字段y

鲍依斯-科得范式（BCNF）：在3NF的基础上，库表中任何字段对任一候选关键字段的传递函数依赖都不存在。

满足范式要求的数据库设计是结构清晰的，同时可避免数据冗余和操作异常。这并不意味着不符合范式要求的设计一定是错误的，在数据库表中存在1：1或1：N关系这种较特殊的情况下，合并导致的不符合范式要求反而是合理的。

死锁产生的原因及四个必要条件

产生死锁的原因主要是：

（1） 因为系统资源不足。

（2） 进程运行推进的顺序不合适。

（3） 资源分配不当等。

如果系统资源充足，进程的资源请求都能够得到满足，死锁出现的可能性就很低，否则

就会因争夺有限的资源而陷入死锁。其次，进程运行推进顺序与速度不同，也可能产生死锁。

产生死锁的四个必要条件：

（1） 互斥条件：一个资源每次只能被一个进程使用。

（2） 请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。

（3） 不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺。

（4） 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。

这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之一不满足，就不会发生死锁。

死锁的解除与预防：

理解了死锁的原因，尤其是产生死锁的四个必要条件，就可以最大可能地避免、预防和

解除死锁。所以，在系统设计、进程调度等方面注意如何不让这四个必要条件成立，如何确定资源的合理分配算法，避免进程永久占据系统资源。此外，也要防止进程在处于等待状态的情况下占用资源。因此，对资源的分配要给予合理的规划。

迭代器和指针的区别以及迭代器失效

1.指针和iterator都支持与整数进行+，-运算，而且其含义都是从当前位置向前或者向后移动n个位置

2.指针和iterator都支持减法运算，指针-指针得到的是两个指针之间的距离，迭代器-迭代器得到的是两个迭代器之间的距离

3.通过指针或者iterator都能够修改其指向的元素

通过上面这几点看，两者真的很像，但是两者也有着下面的几个不同地方

1. cout操作符可以直接输出指针的值，但是对迭代器进行在操作的时候会报错。通过看报错信息和头文件知道，迭代器返回的是对象引用而不是对象的值，所以cout只能输出迭代器使用\*取值后的值而不能直接输出其自身。

2.指针能指向函数而迭代器不行，迭代器只能指向容器

这就说明了迭代器和指针其实是完全不一样的概念来的。指针是一种特殊的变量,它专门用来存放另一变量的地址，而迭代器只是参考了指针的特性进行设计的一种STL接口。

迭代器是指针的抽象和泛化。所以，指针是一种迭代器。

迭代器是类，不过表现的像指针，因为它重载了解引用和指向操作符。指针可以看作是简化的迭代器迭代器是类，不过表现的像指针，因为它重载了解引用和指向操作符。指针可以看作是简化的迭代器

迭代器是一个泛型类，里面有很多重载函数。

什么是友元？

我们已知道类具有封装和信息隐藏的特性。只有类的成员函数才能访问类的私有成员，程序中的其他函数是无法访问私有成员的。非成员函数可以访问类中的公有成员，但是如果将数据成员都定义为公有的，这又破坏了隐藏的特性。另外，应该看到在某些情况下，特别是在对某些成员函数多次调用时，由于参数传递，类型检查和安全性检查等都需要时间开销，而影响程序的运行效率。

为了解决上述问题，提出一种使用友元的方案。友元是一种定义在类外部的普通函数或类，但它需要在类体内进行说明，为了与该类的成员函数加以区别，在说明时前面加以关键字friend。友元不是成员函数，但是它可以访问类中的私有成员。友元的作用在于提高程序的运行效率，但是，它破坏了类的封装性和隐藏性，使得非成员函数可以访问类的私有成员。

delete、new的用法

在 C++ 中，你也许经常使用 new和 delete 来动态申请和释放内存，但你可曾想过以下问题呢？

new 和 delete 是函数吗？

new \[\] 和 delete \[\] 又是什么？什么时候用它们？

你知道 operator new 和 operatordelete 吗？

为什么 new \[\] 出来的数组有时可以用delete 释放有时又不行？

…

如果你对这些问题都有疑问的话，不妨看看我这篇文章。

new 和 delete 到底是什么？

如果找工作的同学看一些面试的书，我相信都会遇到这样的题：sizeof 不是函数，然后举出一堆的理由来证明 sizeof 不是函数。在这里，和 sizeof 类似，new 和 delete 也不是函数，它们都是 C++ 定义的关键字，通过特定的语法可以组成表达式。和 sizeof 不同的是，sizeof 在编译时候就可以确定其返回值，new 和 delete 背后的机制则比较复杂。

继续往下之前，请你想想你认为 new 应该要做些什么？也许你第一反应是，new 不就和 C 语言中的 malloc 函数一样嘛，就用来动态申请空间的。你答对了一半，看看下面语句：

string\*ps = new string("hello world");

你就可以看出 new 和 malloc 还是有点不同的，malloc申请完空间之后不会对内存进行必要的初始化，而 new 可以。所以 new expression 背后要做的事情不是你想象的那么简单。在我用实例来解释 new 背后的机制之前，你需要知道 operator new 和 operator delete 是什么玩意。

operatornew 和 operator delete

这两个其实是 C++ 语言标准库的库函数，原型分别如下：

void\*operator new(size\_t); //allocate anobject

void\*operator delete(void \*); //free anobject

void\*operator new\[\](size\_t); //allocate anarray

void\*operator delete\[\](void \*); //free anarray

后面两个你可以先不看，后面再介绍。前面两个均是 C++ 标准库函数，你可能会觉得这是函数吗？请不要怀疑，这就是函数！C++ Primer 一书上说这不是重载 new 和 delete 表达式（如 operator= 就是重载 = 操作符），因为 new 和 delete 是不允许重载的。但我还没搞清楚为什么要用 operator new 和 operator delete 来命名，比较费解。我们只要知道它们的意思就可以了，这两个函数和 C 语言中的 malloc 和 free 函数有点像了，都是用来申请和释放内存的，并且malloc申请内存之后不对内存进行初始化，直接返回申请内存的指针。

我们可以直接在我们的程序中使用这几个函数。

new 和 delete 背后机制

知道上面两个函数之后，我们用一个实例来解释new 和 delete 背后的机制：

我们不用简单的 C++ 内置类型来举例，使用复杂一点的类类型，定义一个类 A：

class A

public:

A(int v) : var(v)

fopen\_s(&file, "test","r");

~A()

fclose(file);

private:

int var;

FILE \*file;

\};

很简单，类 A 中有两个私有成员，有一个构造函数和一个析构函数，构造函数中初始化私有变量 var 以及打开一个文件，析构函数关闭打开的文件。

我们使用

class\*pA = new A(10);

来创建一个类的对象，返回其指针 pA。

简单总结一下：

首先需要调用上面提到的 operatornew 标准库函数，传入的参数为 class A 的大小，这里为 8 个字节，至于为什么是 8 个字节，你可以看看《深入 C++ 对象模型》一书，这里不做多解释。这样函数返回的是分配内存的起始地址，这里假设是 0x007da290。

上面分配的内存是未初始化的，也是未类型化的，第二步就在这一块原始的内存上对类对象进行初始化，调用的是相应的构造函数，这里是调用 A:A(10); 这个函数，从图中也可以看到对这块申请的内存进行了初始化，var=10, file 指向打开的文件。

最后一步就是返回新分配并构造好的对象的指针，这里 pA 就指向 0x007da290 这块内存，pA 的类型为类 A 对象的指针。

所有这三步，你都可以通过反汇编找到相应的汇编代码，在这里我就不列出了。

好了，那么 delete 都干了什么呢？还是接着上面的例子，如果这时想释放掉申请的类的对象怎么办？当然我们可以使用下面的语句来完成：

deletepA;

delete 就做了两件事情：

调用 pA 指向对象的析构函数，对打开的文件进行关闭。

通过上面提到的标准库函数 operatordelete 来释放该对象的内存，传入函数的参数为 pA 的值，也就是 0x007d290。

好了，解释完了 new 和 delete 背后所做的事情了，是不是觉得也很简单？不就多了一个构造函数和析构函数的调用嘛。

如何申请和释放一个数组？

我们经常要用到动态分配一个数组，也许是这样的：

string\*psa = new string\[10\]; //array of 10empty strings

int \*pia= new int\[10\]; //array of 10 uninitialized ints

上面在申请一个数组时都用到了 new \[\]这个表达式来完成，按照我们上面讲到的 new 和 delete 知识，第一个数组是 string 类型，分配了保存对象的内存空间之后，将调用 string 类型的默认构造函数依次初始化数组中每个元素；第二个是申请具有内置类型的数组，分配了存储 10 个 int 对象的内存空间，但并没有初始化。

如果我们想释放空间了，可以用下面两条语句：

delete\[\] psa;

delete \[\]pia;

都用到 delete \[\] 表达式，注意这地方的 \[\]一般情况下不能漏掉！我们也可以想象这两个语句分别干了什么：第一个对 10 个 string 对象分别调用析构函数，然后再释放掉为对象分配的所有内存空间；第二个因为是内置类型不存在析构函数，直接释放为 10 个 int 型分配的所有内存空间。

这里对于第一种情况就有一个问题了：我们如何知道 psa 指向对象的数组的大小？怎么知道调用几次析构函数？

这个问题直接导致我们需要在 new \[\] 一个对象数组时，需要保存数组的维度，C++ 的做法是在分配数组空间时多分配了 4 个字节的大小，专门保存数组的大小，在 delete \[\] 时就可以取出这个保存的数，就知道了需要调用析构函数多少次了。

还是用图来说明比较清楚，我们定义了一个类A，但不具体描述类的内容，这个类中有显示的构造函数、析构函数等。那么当我们调用

class A\*pAa = new A\[3\];

时需要做的事情如下：

申请时在数组对象的上面还多分配了 4 个字节用来保存数组的大小，但是最终返回的是对象数组的指针，而不是所有分配空间的起始地址。

这样的话，释放就很简单了：

delete\[\] pAa;

这里要注意的两点是：

调用析构函数的次数是从数组对象指针前面的4 个字节中取出；

传入 operator delete\[\] 函数的参数不是数组对象的指针 pAa，而是 pAa 的值减 4。

为什么 new/delete 、new\[\]/delete\[\] 要配对使用？

其实说了这么多，还没到我写这篇文章的最原始意图。从上面解释的你应该懂了 new/delete、new\[\]/delete\[\] 的工作原理了，因为它们之间有差别，所以需要配对使用。但偏偏问题不是这么简单，这也是我遇到的问题，如下这段代码：

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

delete\[\]pia;

这肯定是没问题的，但如果把 delete\[\]pia; 换成 delete pia; 的话，会出问题吗？

这就涉及到上面一节没提到的问题了。上面我提到了在 new \[\] 时多分配 4 个字节的缘由，因为析构时需要知道数组的大小，但如果不调用析构函数呢（如内置类型，这里的 int 数组）？我们在 new \[\] 时就没必要多分配那 4 个字节， delete \[\] 时直接到第二步释放为 int 数组分配的空间。如果这里使用 delete pia;那么将会调用 operator delete 函数，传入的参数是分配给数组的起始地址，所做的事情就是释放掉这块内存空间。不存在问题的。

这里说的使用 new \[\] 用 delete 来释放对象的提前是：对象的类型是内置类型或者是无自定义的析构函数的类类型！

我们看看如果是带有自定义析构函数的类类型，用 new \[\] 来创建类对象数组，而用 delete 来释放会发生什么？用上面的例子来说明：

class A\*pAa = new class A\[3\];

deletepAa;

那么 delete pAa; 做了两件事：

调用一次 pAa 指向的对象的析构函数；

调用 operatordelete(pAa); 释放内存。

显然，这里只对数组的第一个类对象调用了析构函数，后面的两个对象均没调用析构函数，如果类对象中申请了大量的内存需要在析构函数中释放，而你却在销毁数组对象时少调用了析构函数，这会造成内存泄漏。

上面的问题你如果说没关系的话，那么第二点就是致命的了！直接释放 pAa 指向的内存空间，这个总是会造成严重的段错误，程序必然会奔溃！因为分配的空间的起始地址是 pAa 指向的地方减去 4 个字节的地方。你应该传入参数设为那个地址！

同理，你可以分析如果使用 new 来分配，用 delete\[\] 来释放会出现什么问题？是不是总会导致程序错误？

总的来说，记住一点即可：new/delete、new\[\]/delete\[\]要配套使用总是没错的！

typename的用法

1, 什么地方使用？用在模板定义里，标明其后的模板参数是类型参数。

例如

template<typename T, typename Y>

Tfoo(const T& t, const Y& y)\{//....\};

templace<typenameT>

classCTest

private:

T t;

public:

//...

其实，这里最常用的是使用关键字class，而且二者功能完全相同，这里的class和定义类时的class完全是两回事，C++当时就是为了减少关键字，才使用了class。但最终却不得不引入了typename，究竟是

什么原因呢？请看第二条，也就是typename的第二个用法。

2, 模板中标明“内嵌依赖类型名”

这里有三个词，内嵌、依赖、类型名。那么什么是“内嵌依赖类型名(nested dependent type name)”？

请看SGI STL里的一个例子, 只是STL中count范型算法的实现：

template<class \_InputIter, class \_Tp>

typenameiterator\_traits<\_InputIter>::difference\_type

count(\_InputIter\_\_first, \_InputIter \_\_last, const \_Tp& \_\_value) \{

\_\_STL\_REQUIRES(\_InputIter, \_InputIterator);

\_\_STL\_REQUIRES(typenameiterator\_traits<\_InputIter>::value\_type,

\_EqualityComparable);

\_\_STL\_REQUIRES(\_Tp, \_EqualityComparable);

typename iterator\_traits<\_InputIter>::difference\_type\_\_n = 0;

for ( ; \_\_first != \_\_last; ++\_\_first)

if (\*\_\_first == \_\_value)

\++\_\_n;

return \_\_n;

这里有三个地方用到了typename：返回值、参数、变量定义。分别是：

typenameiterator\_traits<\_InputIter>::difference\_type

typenameiterator\_traits<\_InputIter>::value\_type

typenameiterator\_traits<\_InputIter>::difference\_type \_\_n = 0;

difference\_type， value\_type就是依赖于\_InputIter（模板类型参数）的类型名。源码如下：

template<class \_Iterator>

structiterator\_traits \{

typedef typename \_Iterator::iterator\_categoryiterator\_category;

typedef typename \_Iterator::value\_type value\_type;

typedef typename\_Iterator::difference\_type difference\_type;

typedef typename \_Iterator::pointer pointer;

typedef typename \_Iterator::reference reference;

\};

内嵌是指定义在类名的定义中的。以上difference\_type和value\_type都是定义在iterator\_traits中的。

依赖是指依赖于一个模板参数。typenameiterator\_traits<\_InputIter>::difference\_type中difference\_type依赖于模板参数\_InputIter。

类型名是指这里最终要指出的是个类型名，而不是变量。例如iterator\_traits<\_InputIter>::difference\_type完全有可能是类iterator\_traits<\_InputIter>类里的一个static对象。而且当我们这样写的时候，C＋＋默认就是解释为一个变量的。所以，为了和变量区分，必须使用typename告诉编译器。

那么是不是所有的T::type\_or\_variable,或者tmpl<T>:type\_or\_variable都需要使用typename呢？不是，有以下两个例外。

3 例外

（1）类模板定义中的基类列表。

例如

template<classT>

classDerived: public Base<T>::XXX

...

（2）类模板定义中的初始化列表。

Derived(intx) : Base<T>::xxx(x)

...

为什么这里不需要呢？因为编译器知道这里需要的是类型还是变量，（1）基类列表里肯定是类型名，（2）初始化列表里肯定是成员变量名。

编程判断一个数是否为2的幂

boolfun(int v)

bool flag = 0;

if((v>0)&&(v&(v-1))==0)

flag = 1;

return flag;

汉诺塔时间复杂度怎么求 求过程计算过程

假设移动n个圆盘需要f(n)次移动

首先考虑一个圆盘，只需一步就可以了f(1)=1……①

现在考虑n个圆盘，假设开始圆盘在A柱，可以先把A柱的上面n-1个圆盘移到B，再将A剩下的一个移到C，最后将B的n-1个移到C。总共需要f(n)=2f(n-1)+1……②

根据①②两式，可求出f(n)=2^n-1 所以O(n)=2^n

2、 计算两个字符串的是否相似（字符的种类，和出现次数相同）

先比较strlen，如果不相等，直接返回false

根据ASCII码建表 str\[255\],然后比较字符的出现次数，如有一个不同，返回false。

然后比较位置吧。有一个不同，就返回true。

定义二叉树，节点值为int，计算二叉树中的值在\[a,b\]区间的节点的个数。

任意一种方式遍历二叉树，如果值在 \[a，b\] 之间，计数器+1

一条路有k可坑，每次能跳平方数步长（14 9 16。。），不能跳到坑里，从a跳到b最少几步？

动态规划：

f(n)=min(f(第一个大于n的平方数-n),f(n-第一个小于n的平方数))+1

给一个整数数组，求数组中重复出现次数大于数组总个数一半的数

算法思路：1，最容易想到的就是将这个数组排序，然后取出中间的数。最好的排序算法的时间复杂度是O(nlogn).这显然不符合某些公司的要求。

2，遍历一遍数组即找出我们所求的数。在遍历的过程中如果每次删除两个不同的数，那么，在剩下的数的列表中，我们所求的这个数的数量仍然超过总数的一半。

intFind(int arr\[\], int N)

int candidate;

int nTimes, i;

for(i = 0; i < N; i++)

if(nTimes == 0)

candidate = arr\[i\];

nTimes++;

else

if(candidate == arr\[i\])

nTimes++;

else

nTime--;

return candidate;

这里有一个扩展问题，说一个数组中有三个数，他们在数组中的出现次数都大于1/4，请问如何找出这三个数?

思路是类似的，同样，每次删除4个不同的ID，不影响“那三个ID在剩余ID中出现仍然超过1/4”这一事实，因此我们可以每次删除4个不同的ID，直到剩下3个ID为止。具体编程中怎么体现“删除四个不同ID”这一动作呢？我是这样做的。用candidate\[3\]记录三个候选ID，用count\[3\]记录它们的累积次数，然后遍历整个ID列表，每处理一个ID，若与candidate\[i\]中的某一个相同，则count\[i\]++，若与三个都不同，则说明找到了四个互不相同的ID，将三个count\[i\]--，也就相当于“删除了四个不同ID”，若某一个count\[i\]==0，则更新之。

不用递归和辅助空间对二叉树进行遍历

递归和非递归的进行二叉树的遍历从某种意义上来讲都是需要辅助空间的。那么进行非递归的和不需要辅助空间的遍历会有这种可能吗？答案是肯定的，应用线索二叉树，这样就能把左子树或者右子树为空的节点利用起来，二叉树线索之后就可能找到某个节点的前区或者后继。一个含有n个节点的二叉树，可定会有n+1个指针是空的。所有利用这n+1一个指针就能将二叉树线索化而不遗漏任何一个节点。

下面给出利用这种线索化来遍历二叉树的中序遍历，现在只研究到中序遍历：

1，设置变量current= root

2，如果current的左子树是空的，打印这个节点的value，然后将current设置为current->rchild.

3，如果current的左子树不为空，那么找到左子树中序遍历最后一个节点，既然是最后的一个了，那么这个节点的右子树是空的，让它指向current，然后让current指向其左子树。

下面的代码并没有破坏原来树的结构，在线索化遍历之后又重新还原树原来的样子，下面是代码：

\#include<iostream>

usingnamespace std;

typedefstruct tree\_node\_s \{

int value;

struct tree\_node\_s\* lchild;

struct tree\_node\_s\* rchild;

\}tree\_node\_t;

tree\_node\_t\*createNode(int value) \{

tree\_node\_t\* node =(tree\_node\_t\*)malloc(sizeof(tree\_node\_t));

node->value = value;

node->lchild = NULL;

node->rchild = NULL;

return node;

voidinorderTraverse(tree\_node\_t\* root) \{

if (root) \{

inorderTraverse(root->lchild);

cout << root->value <<" ";

inorderTraverse(root->rchild);

voiditerativeTraverse(tree\_node\_t\* root) \{

tree\_node\_t\* current = root;

tree\_node\_t\* prev = NULL;

while (NULL != current) \{

if (NULL == current->lchild) \{

cout << current->value<< " ";

current = current->rchild;

\} else \{

prev = current->lchild;

while (prev->rchild &&prev->rchild != current)

prev = prev->rchild;

if (NULL == prev->rchild) \{

prev->rchild = current;

current =current->lchild;

\} else \{

prev->rchild = NULL;

cout << current->value <<" ";

current =current->rchild;

intmain(int argc, char\* argv\[\]) \{

tree\_node\_t\* root = createNode(1);

root->lchild = createNode(2);

root->rchild = createNode(3);

root->lchild->lchild =createNode(4);

root->lchild->rchild =createNode(5);

iterativeTraverse(root);

cout << endl;

inorderTraverse(root);

cin.get();

return 0;

介绍一下STL，具体说明STL如何实现vector。

解析：

前面例题已经介绍过了STL，因此这里不再赘述，只说明STL如何实现vector。

vector的定义如下：

template<class \_Ty, class \_A =allocator<\_Ty> >

class vector \{

……

\};

这里省略了中间的成员。其中\_Ty类型用于表示vector中存储的元素类型，\_A默认为allocator<\_Ty>类型。

这里需要说明的是allocator类，它是一种“内存配置器”，负责提供内存管理（可能包含内存分配、释放、自动回收等能力）相关的服务。于是对于程序员来说，就不用关心内存管理方面的问题。

vector支持随机访问，因此为了效率方面的考虑，它内部使用动态数组的方式实现的。当进行insert或push\_back等增加元素的操作时，如果此时动态数组的内存不够用，就要动态的重新分配，一般是当前大小的两倍，然后把原数组的内容拷贝过去。所以，在一般情况下，其访问速度同一般数组，只有在重新分配发生时，其性能才会下降。例如下面的程序：

\#include <iostream>

\#include <vector>

using namespace std;

int main()

vector<int> v; //初始时无元素，容量为0

cout << v.capacity()<< endl;

v.push\_back(1) ; //容量不够，分配1个元素内存

cout << v.capacity()<< endl;

v.push\_back(2); //容量不够，分配2个元素内存

cout << v.capacity()<< endl;

v.push\_back(3); //容量不够，分配4个元素内存

cout << v.capacity()<< endl;

v.push\_back(4);

v.push\_back(5); //容量不够，分配8个元素内存

cout << v.capacity()<< endl;

v.push\_back(6);

v.push\_back(7);

v.push\_back(8);

v.push\_back(9); //容量不够，分配16个元素内存

cout << v.capacity()<< endl;

return 0;

下面是各个执行步骤：

（1）代码7行，初始化时v无元素（size为0），且容量（capacity）也为0。

（2）代码9行，在数组末尾添加元素1，由于容量不够，因此allocator分配1个int大小的内存，并把整数1复制到这个内存中。

（3）代码11行，在数组末尾添加元素2。此时容量为1，但元素个数需要变为2，因此容量不够，于是allocator先分配原来容量的2倍大小的内存（即2个int大小的内存），然后把原来数组中的1和新加入的2拷贝到新分配的内存中，最后释放原来数组的内存。

（4）代码13行，在数组末尾添加元素3。此时容量为2，而元素个数需要变为3，因此容量也不够。和（3）相同，allocator分配4个int的内存，然后把原来数组中的1、2以及新加入的3拷贝到新分配的内存，最后释放原数组的内存。

（5）代码15行，在数组末尾添加元素3。此时容量为4，而元素个数需要变为3，因此容量足够，不需要分配内存，直接把4拷贝到数组的最后即可。

以后的操作不再赘述。注意vector的size()和capacity()是不同的，前者表示数组中元素的多少，后者表示数组有多大的容量。由上面的分析可以看出，使用vector的时候需要注意内存的使用，如果频繁地进行内存的重新分配，会导致效率低下。

答案：

STL（StandardTemplate Library），即标准模板库，是一个具有工业强度的，高效的C++程序库。它被容纳于C++标准程序库中，包括容器、算法、迭代器组件。

vector内部使用动态数组的方式实现的。如果动态数组的内存不够用，就要动态的重新分配，一般是当前大小的两倍，然后把原数组的内容拷贝过去。所以，在一般情况下，其访问速度同一般数组，只有在重新分配发生时，其性能才会下降。它的内部使用allocator类进行内存管理，程序员不需要自己操作内存。

vector<int> array;

array.push\_back(1 );

array.push\_back(2 );

array.push\_back(3 );

for(vector <int>::size\_type i=array.size()-1; i>=0; --i ) // 反向遍历array数组

cout < < array\[i\] < <endl;

当我运行代码的时候，没有输出 3 2 1，而是输出了一大堆很大的数字，为什么？

于是我修改了代码

for(vector<int>::size\_type j=array.size();j>0;j--)

cout < < "element is " < <array\[j-1\] < <endl;

这样就输出了 3 2 1，倒是为什么呢？

答案:size\_type 是 unsignedint型的,也就是说, i用于大于0,第一种做法会陷入死循环!

当i=0时,再--i,i=0xFFFFFFFF.引用一个无效的元素,然后程序就崩溃了!

建议用iterator迭代子来操作!

字符串移动（字符串为\*号和26个字母的任意组合，把\*号都移动到最左侧，把字母移到最右侧并保持相对顺序不变），要求时间和空间复杂度最小。

voidArrange(char \*str , int n)

int i , k = n-1;

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

if(str\[i\] != '\*')

if(str\[k\] == '\*')

str\[k\] =str\[i\];

str\[i\] = '\*';

\--k;

7、说说outer join、inner join、left join、right join的区别是什么？

内连接：进行连接的两个表对应的相匹配的字段完全相同的连接。join

外连接又分为左外连接和右外连接。

左连接即LEFT OUTER JOIN：

两个表进行左连接时会返回左边表中的所有的行和右边表中与之相匹配的列值没有相匹配的用空值代替。

右连接即RIGHT OUTER JOIN：

两个表进行右连接时会返回右边表中的所有的行和左边表中与之相匹配的列值没有相匹配的用空值代替。

我们建立两张表，students、class并插入测试数据

students

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

id name classId

1 name1 1

2 name2 null

3 name3 2

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

class

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

id name

1 class1

2 class2

3 class3

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

实验结果如下：

mysql>select s.name,c.name from students s join class c where s.classId=c.id ; （注：inner join和join一样）

\+-------+-------+

|name | class |

\+-------+-------+

| name1| 1 |

| name3| 2 |

\+-------+-------+

2 rowsin set

mysql>select s.name,c.name from students s left join class c on s.classId=c.id ; （left join 和 left outerjoin 一样）

\+-------+-------+

|name | class |

\+-------+-------+

| name1| 1 |

| name2| NULL |

| name3| 2 |

\+-------+-------+

3 rowsin set

mysql>select s.name,c.name from students s right join class c on s.classId=c.id ; （right join 和 right outerjoin 一样）

\+-------+-------+

|name | class |

\+-------+-------+

| name1| 1 |

| name3| 2 |

|NULL | 3 |

\+-------+-------+

3 rowsin set

经典笔试面试题总结(一)

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 js笔试经典面试题

相关 Java经典面试题总结（一）

相关经典公司java笔试编程题题_经典笔试编程题--Java实现

相关 css经典面试题总结

相关经典笔试面试题(二)

相关经典笔试面试题总结(一)

相关经典面试题（一）

相关 STL笔试面试题总结

相关 JavaSE基础总结（笔试面试题）

相关 Java笔试面试-消息队列面试题总结