多态性有哪些？（静态和动态，分别叙述了一下虚函数和函数重载）{ 分为静态多态性和动态多态性，静态就是在编译时就已经确定了，动态是在程序运行时 才能确定。像函数重载，就是多个函数具有相同的函数名，但是函数的参数类型， 个数，顺序必须有所不同。如果基类和派生类成员函数原型一致，则派生类的成员函数将覆盖基类的。 动态多态性的话像虚函数，在派生类中重新定义虚函数时，原型必须与基类一致。在程序运行 期间，使用一个基类指针动态地指向基类或派生类的对象，再调用虚函数。}动态绑定怎么实现？（基类与派生类指针和引用的转换问题）{ 必须通过基类的引用或指针进行函数调用,还必须是虚函数。那么就会发生动态绑定。}类型转换有哪些？（四种类型转换）{ 有static_cast,const_cast,dynamic_cast,reinterpret_cast四种， 那么static_cast实现不同数据类型之间的转换，如把int转换为float(写法是 f=static_cast (i) ); const_cast是取消const属性，可以将const类型的指针变为非const类型的指针 dynamic_cast主要用于基类和派生类之间的转换，会检查操作是否有效，不成功的话，指针会返回null,引用 会抛出异常。 reinterpret_cast会对二进制数据进行重新的解释，可以进行无关类型之间的转换，但是很不安全。}操作符重载？{ 要用到 operator 关键字，如 bool operator ==(参数)，(如果重载操作符是类成员，则左操作数必须是该类 的对象，该操作符才会被调用，如果该操作符的左操作数是其他的类型，则需要被重载为全局名字空间的成员。) C++中 =(赋值运算符),[](下标运算符),()(函数调用运算符),和->（成员指向）必须被定义为类成员操作符。 像成员选择符(.)、域名解析 操作符(::)、条件操作符外(?:)不能被重载，重载操作符不能改变他们的操作符优先级， 不能改变操作数的个数。 （T& operator ++ ()//前置增量 T& operator ++ (int) //后置增量 ）}内存对齐的原则？{ （1）每一个数据成员的偏移量必须是自身长度的倍数，像int，则地址必须是4的倍数。 （2）结构本身也要对齐，对齐将按照#pragma pack指定的数值和结构(或联合)最大数据成员长度中，比较小的那个进行}模板怎么实现？{ 格式就是 template 定义类模板如 template ,创建对象时如A a;在类模板外定义成员函数时， 类似void A ::func(){}，参数可以是类型形参，非类型形参和模板形参，非模板类型的形参 只能是整型，指针和引用}指针和const的用法？{ 最简单的指针如 int* p,说明p是指向一个int型数据的指针，还有指针数组，写法如 int *p[3], 代表数组里 的全是指针，还有数组指针，写法如 int (*p)[3],指针指向的内容是一个数组，还有函数指针，写法如 int (*p)(int); 代表指向的是有一个int型参数求且返回值是int的函数。还有二级指针。 const声明变量需要初始化，且不能被修改，如果修饰指针的话，主要有两种情况，如 const int* p这种所指内 容是常量，不可被修改，另外一种如 int *const p,则指针是常量，所指内容可修改。在类中使用的话，可以 修饰类的数据成员，不能在类中初始化，要在构造函数的初始化列表里初始化。const 可以修饰函数的参数， 返回值以及整个函数，参数可能是指针或引用，则加了const可以保护其内容，一般修饰函数的话const放在 函数体后，则函数不能修改数据成员或者调用其他非const成员函数。}const 和 #define的区别？{ 编译器处理方式不同，宏在预处理阶段替换，const在编译阶段替换。类型和安全检查不同，宏没有类型，不做安全 检查，const有类型，在编译阶段做安全检查。}虚函数、纯虚函数、析构函数？{ 虚函数和纯虚函数都要加 virtual 修饰，虚函数可以直接被使用，也可以被子类重载以后以多态形式调用，而 纯虚函数在基类里只有声明没有定义，必须在子类中实现之后才能被使用。含有纯虚函数的类被称为抽象类， 纯虚函数后加 =0， 抽象类是不能被实例化的 析构函数在类名前加~, 当对象的生命周期结束时，会自动执行析构函数。一个类只能由一个析构函数，不能被 重载。static局部对象在函数调用结束时对象并不释放，只在main函数结束或调用exit函数结束程序时，才调用 static 局部对象的析构函数。全局对象同理，如果是用new 动态建立的，当用delete释放该对象时，先调用该对象 的析构函数。}内联函数（内联函数的优点以及和宏定义的区别）{ 内联函数相当于自动地用函数的形式添加进代码，可以提高效率。编译器会对内联函数的参数做安全检查或自动类型转换， 而宏定义不会。内联函数可以访问类的私有成员变量，而宏定义则不能，在类中声明同时定义的成员函数，自动转化为 内联函数。内联函数中复杂的操作，如循环和递归调用将不被关联。}typedef 的用法{ 它与#define有些类似，但有不同。typedef定义一种类型的别名，而不是简单的宏替换，可以帮助结构体定义别名， 用typedef来定义与平台无关的类型。比如定义一个REAL的浮点类型，如果在支持long double 的平台上,可以将long double 定义别名REAL,在不支持long double的平台上，再改成 typedef double REAL。}c语言和c++有什么区别？{ C是面向过程，C++是面向对象 最突出的部分是多了类的概念，由此衍生出封装，继承，重载，多态等。封装有点像结构体，但是结构体不能定义变量的访问 权限，结构体也不能被继承，C++可以实现运算符的重载。 C++引入了模板，使得C++可以实现泛型编程。 待补充。。。}二叉树的非递归遍历代码？{ void PreOrderVisit(Node* root) { MyStack K; K.Init(); Node* p=root; while(p!=NULL||!K.Empty()) { while(p!=NULL) { Visit(p->data); K.Push(p); p=p->lchild; } if(!K.Empty()) { p=K.Pop(); p=p->rchild; } } } void InOrderVisit(Node* root) { MyStack K; K.Init(); Node* p=root; while(p!=NULL||!K.Empty()) { while(p!=NULL) { K.Push(p); p=p->lchild; } if(!K.Empty()) { p=K.Pop(); Visit(p->data); p=p->rchild; } } } void LastOrderVisit(Node* root)//设置一个标记，到第二次访问时才输出 { MyStack K; K.Init(); Node* p=root; Node* temp=NULL; while(p!=NULL||!K.Empty()) { while(p!=NULL) { p->IsFirst=true; K.Push(p); p=p->lchild; } if(!K.Empty()) { temp=K.Pop(); if(temp->IsFirst==true) { temp->IsFirst=false; K.Push(temp); p=temp->rchild; } else { Visit(temp->data); p=NULL; } } } }}继承机制中对象之间是如何转换的？{ 从派生类向基类的类型转换只对指针和引用类型有效。基类向派生类不存在隐式类型转换，使用dynamic_cast}继承机制中引用和指针之间如何转换？{ 基类向派生类转换，用dynamic_cast转换，首先检查基类指针是否真正指向一个派生类对象，再做相应处理，成功 返回派生类对象，失败则返回空指针。派生类向基类转换，可以用dynamic_cast或者直接进行类型转换。}虚函数、虚函数表里面内存如何分配？{ 对于无虚函数覆盖的继承：虚函数按照其声明顺序放在虚函数表中；父类的虚函数在其子类的虚函数的前面。 对于 有虚函数覆盖的继承：派生类中起覆盖作用的虚函数放在原基类虚函数的位置；没有被覆盖的虚函数依旧。 对于无 虚函数覆盖的多重继承：每个父类都有自己的虚函数表；派生类的虚函数被放在了第一个父类的虚函数表中（按照声 明顺序排序）。 对于有虚函数覆盖的多重继承：派生类中起覆盖作用的虚函数放在原基类虚函数的位置；没有被覆 盖的虚函数依旧。}如何实现只能动态分配类对象、不能定义类对象？{ 把类的构造函数和析构函数设为protected属性。类对象不能访问，但是派生类可以继承，也可以访问。 同时，创建create和destroy两个函数，用于创建类对象。 （create函数设为static,原因是，创建对象的时候A *p=A::create().只有静态成员函数才能有类名直接访问）}红黑树的定义和解释？{ 一棵红黑树是指一棵满足下述性质的二叉搜索树（BST, binary search tree）： 1. 每个结点或者为黑色或者为红色。 2. 根结点为黑色。 3. 每个叶结点(实际上就是NULL指针)都是黑色的。 4. 如果一个结点是红色的，那么它的两个子节点都是黑色的（也就是说，不能有两个相邻的红色结点）。 5. 对于每个结点，从该结点到其所有子孙叶结点的路径中所包含的黑色结点数量必须相同。 红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条 从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。 前面说了，红黑树，是一种二叉查找树，既然是二叉查找树，那么它必满足二叉查找树的一般性质。 红黑树是通过节点分为红、黑两种颜色并根据一定的规则确保在一定程度上是平衡的，从而保证在红黑树中查找、 删除、插入操作都只需要O（logk）的时间。}静态成员函数和数据成员又什么意义？{ A 声明为static的类成员或者成员函数便能在类的范围内共同享，类域中的全局变量。 B 派生类对象与基类对象共享基类的静态数据成员。 D 静态数据成员不能在类定义里边初始化，只能在class body外初始化。 E 静态成员函数没有this指针，它不能返回非静态成员，因为除了对象会调用它外，类本身也可以调用。静态 成员函数不可以调用类的非静态成员。因为静态成员函数不含this指针。 F 非静态成员函数可以任意地访问静态成员函数和静态数据成员。}explicit是干什么用的？{ 这个关键字的作用是将编译器隐式转换的功能给屏蔽掉。}模板特化的概念，为什么特化？{ 通常又有一些特殊的情况，不能直接使用泛型模板展开实现,所以要用到模板特化 一是特化为绝对类型；比如特化为 double,float 等 template<> class Compare {}; 二是特化为引用，指针类型；比如 const T*,const T& ; template class Compare {}; 三是特化为另外一个类模板。 template struct SpecializedType { T1 x1; T1 x2; }; template class Compare >{}; 对于特殊类型, 比如说指针, 其拷贝就和基本数据类型不同. 这是为了处理这种特殊情况就需要类模板特化, 用于处理特定类型的特殊情况.}strcpy函数的编写？{ char *strcpy(char *strDes,const char *strSrc) { assert(strSrc!=NULL); char *p=strDes; while(*strSrc!='\0') { *p++=*strSrc++; } *p='\0'; return strDes; }}strcpy返回类型是干嘛用的？{ 当strcpy失败的时候就能从返回值判断出来。 有时候函数原本不需要返回值，但为了增加灵活性如支持链式表达，可以附加返回值。 方便嵌套使用}strcpy和memcpy的区别{ 复制的内容不同。strcpy只能复制字符串，而memcpy可以复制任意内容，例如字符数组、整型、结构体、类等。 复制的方法不同。strcpy遇到被复制字符的串结束符"\0"才结束，memcpy则是根据其第3个参数决定复制的长度。}一个由C/C++编译的程序占用的内存有几个部分?{ 栈区（stack）—由编译器自动分配释放，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。 堆区（heap）— 一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS 。注意它与数据结构中的堆是两回事， 分配方式倒是类似于链表。 全局区（静态区）（static）—，全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域， 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。 - 程序结束后有系统释放 文字常量区 —常量字符串就是放在这里的。 程序结束后由系统释放 程序代码区—存放函数体的二进制代码。}栈区和堆区的区别？{ 栈：在Windows下,栈是向低地址扩展的数据结构，是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的 最大容量是系统预先规定好的，在 WINDOWS下，栈的大小是2M（也有的说是1M，总之是一个编译时就确定的常数）， 如果申请的空间超过栈的剩余空间时，将提示overflow。因此，能从栈获得的空间较小。 堆：堆是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的，自然是 不连续的，而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见， 堆获得的空间比较灵活，也比较大。}内存泄露{ 内存泄漏(memory leak)指由于疏忽或错误造成程序未能释放已经不再使用的内存的情况。内存泄漏并非指内存在 物理上的消失，而是应用程序分配某段内存后，由于设计错误，失去了对该段内存的控制，因而造成了内存的浪费。 一般我们常说的内存泄漏是指堆内存的泄漏。堆内存是指程序从堆中分配的，大小任意的（内存块的大小可以在程序 运行期决定），使用完后必须显式释放的内存}内存溢出有哪些因素？{ (1) 使用非类型安全(non-type-safe)的语言如 C/C++ 等，不检查数组越界，也不检查类型安全。 (2) 以不可靠的方式存取或者复制内存缓冲区，超过缓冲区长度大小之类的。 (3) 编译器设置的内存缓冲区太靠近关键数据结构。}new 和 malloc的区别，delete和free的区别？{ malloc与free是C++/C语言的标准库函数，new/delete是C++的运算符。 简而言之 new/delete能进行对对象进行构造和析构函数的调用进而对内存进行更加详细的工作，而malloc/free不能。 malloc在申请内存的时候，必须要提供申请的长度，而返回的指针是void*型，必须要强转才能成为需要的类型。 这是因为new 内置了sizeof、类型转换和类型安全检查功能。 对于用户自定义的对象而言，用maloc/free无法满足动态管理对象的要求。}为什么要用static_cast转换而不用c语言中的转换？{ Static_cast转换，它会检查类型看是否能转换，有类型安全检查。}异常机制怎么回事？{ try ,throw ,catch ,抛出异常用throw,捕获异常用catch. 如果没有找到处理代码，程序就调用C++标准库中定义的函数terminate()。 terminate()的缺省行为是调用abort() ，指示从程序非正常退出。}迭代器删除元素会发生什么？{ 对于vector和string，指向其删除点之后位置的迭代器、引用和指针都会失效。 对于deque，删除除首尾位置之 外的任何元素都会使所有迭代器、引用和指针失效。 对于list，指向容器其他位置的迭代器，引用和指针仍有效。 对于插入操作，影响与删除操作一样。}vector中的reserve函数和resize函数的区别？{ reserve并不改变容器内实际元素数量，它仅影响vector预先分配多大的内存空间，而且只有当需要的内存空间 超过当前容量时，reserve调用才会改变vector的容量，此时一般将容量扩充1倍； resize只改变容器中元素的 数目，而不是容器的容量。}必须在构造函数初始化里进行初始化的数据成员又哪些？{ 对象成员的初始化，const修饰的成员的初始化，引用成员的初始化，子类调用父类的构造函数初始化父类成员}auto_ptr类{ auto_ptr 是C++标准库提供的类模板，auto_ptr对象通过初始化指向由new创建的动态内存，它是这块内存的 拥有者，一块内存不能同时被分给两个拥有者。当auto_ptr对象生命周期结束时，其析构函数会将auto_ptr对 象拥有的动态内存自动释放。避免内存泄露，即使发生异常，通过异常的栈展开过程也能将动态内存释放。 auto_ptr不支持new 数组。 2. auto_ptr需要包含的头文件 #include int* p = new int(33); auto_ptr api(p); 可以利用已经存在的智能指针来构造新的智能指针 因为一块动态内存智能由一个智能指针独享，所以在拷贝构造或赋值时都会发生拥有权转移的过程。 防止两个auto_ptr对象拥有同一个对象（一块内存） 警惕智能指针作为参数！ auto_ptr不能初始化为指向非动态内存 auto_ptr常用的成员函数： 1) get() 返回auto_ptr指向的那个对象的内存地址。 2) reset() 重新设置auto_ptr指向的对象。类似于赋值操作，但赋值操作不允许将一个普通指针指直接 赋给auto_ptr，而reset()允许 3) release() 返回auto_ptr指向的那个对象的内存地址,并释放对这个对象的所有权。 1、auto_ptr不能共享所有权。 2、auto_ptr不能指向数组 3、auto_ptr不能作为容器的成员。 4、不能通过赋值操作来初始化auto_ptr，这是因为auto_ptr 的构造函数被定义为了explicit 5、不要把auto_ptr放入容器}shared_ptr类{ boost::shared_ptr可以共享对象的所有权，也可以使用在stl的容器中 boost::shared_ptr的管理机制其实并不复杂，就是对所管理的对象进行了引用计数， 当新增一个boost::shared_ptr对该对象进行管理时，就将该对象的引用计数加一； 减少一个boost::shared_ptr对该对象进行管理时，就将该对象的引用计数减一， 如果该对象的引用计数为0的时候，说明没有任何指针对其管理，才调用delete释放其所占的内存。}求二叉树最近公共祖先{ 其实嘛，首先数一下两个结点的深度，然后比较深的那个往上走（深-浅）步，最后同时往上走， 肯定会命中最近共同父节点的。 这棵树如果自己实现就加个父指针，从当前节点向上走到根节点，这条路沿路节点做一下标记，然后从第2个 节点向上走，第一次遇到曾经标记过的节点就是最近公共祖先，一直走到根节点都没遇到就属于不同的两棵树。}链表反转{ //为了反转这个单链表，我们先让头结点的next域指向结点2，再让结点1的next域指向结点3，最后将结 //点2的next域指向结点1，就完成了第一次交换，顺序就变成了Header-结点2-结点1-结点3-结点4-NULL，然后进行 //相同的交换将结点3移动到结点2的前面，然后再将结点4移动到结点3的前面就完成了反转， List* ReverseList(List* L) { List *temp=NULL; List *p=NULL; if(L==NULL) return NULL; temp=L->next; while(temp->next!=NULL) { p=temp->next; temp->next=p->next; p->next=L->next; L->next=p; } return L; }}链表排序{struct Node{ int key; Node* next; Node(int _key,int _next):key(_key),next(_next){}};Node* GetPartion(Node* st,Node* en){ int key=st->key; Node* p=st; Node* q=p->next; while(q!=en) { if(q->key next; swap(p->key,q->key); } q=q->next; } swap(p->key,st->key); return p;}void QuickSort(Node* st,Node* en){ if(st!=en) { Node* p=GetPartion(st,en); QuickSort(st,p); QuickSort(p->next,en); }}}面向对象和面向过程的区别{ 面向过程就是分析出解决问题所需要的步骤，然后用函数把这些步骤一步一步实现。 面向对象是把构成问题事务分解成各个对象，对外界来说，事物是直接使用的，不用去管他内部的情况。 面向对象和面向过程的主要区别就是数据是单独存储还是与操作存储在一起。对面向过程而言，数据是独立的。 而在面向对象中，对象本身就提供了存储数据的空间（类的数据成员），这样就是函数的参数传递简单多了， 而且提供了数据封装后，数据的访问也变可靠了。 待补充。。。}手写kMP{ 原理：kmp算法是找到一个字符串模板在另一个字符串中的所有匹配点，首先预处理出模板每个位置的失配指针，用自己匹配自己，计算f每一个位置之前的字符串的前缀和后缀公共部分的最大长度。然后就是匹配 的过程。 void GetFail(const char* P,int* fail) { int L=strlen(P); fail[0]=fail[1]=0; for(int i=1;i '9') return 0; valid=true; while(*str>='0'&&*str<='9') { ret=ret*10+(*str-'0'); if((tag&&ret>INT_MAX+1LL)||(!tag&&ret>INT_MAX)) { valid=false; return 0; } str++; } if(tag) ret*=-1; return (int)ret;}}缓冲区溢出漏洞，越界漏洞{ 使用像strcpy这类不安全函数，这种函数对用户的输入不作任何检查,分配的内存空间是有限的， 如果输入超长的字符串，必然会导致溢出。 缓冲区溢出中，最为危险的是堆栈溢出，因为入侵者可以利用堆栈溢出，在函数返回时改变返回程序的地址， 让其跳转到任意地址，带来的危害一种是程序崩溃导致拒绝服务，另外一种就是跳转并且执行一段恶意代码}线程和进程的区别{ 简而言之,一个程序至少有一个进程,一个进程至少有一个线程. 线程的划分尺度小于进程，使得多线程程序的并发性高。 另外，进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大地提高了程序的运行效率。 线程在执行过程中与进程还是有区别的。每个独立的线程有一个程序运行的入口、顺序执行序列和程序的出口。 但是线程不能够独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制。 从逻辑角度来看，多线程的意义在于一个应用程序中，有多个执行部分可以同时执行。但操作系统并没有将多 个线程看做多个独立的应用，来实现进程的调度和管理以及资源分配。这就是进程和线程的重要区别。 线程是进程的一个实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位.线程自己基本 上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈),但是它可与同属一个 进程的其他的线程共享进程所拥有的全部资源. 如果我们把进程比喻为一个运行在电脑上的软件，那么一个软件的执行不可能是一条逻辑执行的，必定有多个分 支和多个程序段，就好比要实现程序A，实际分成 a，b，c等多个块组合而成。}C++11 的特性{ 1、 初始化列表应用更广泛 2、 auto的引入，foreach循环 3、 C++ 11 中的Lambda表达式用于定义并创建匿名的函数对象，以简化编程工作。 4、 C++11 还增加了防止基类被继承和防止子类重写函数的能力.这是由特殊的标识符final来完成的 5、 C++11 通过引入一个新的关键字nullptr充当单独的空指针常量，可以隐式转换任意类型的指针或指向成员的指针的类型, 6、 constexpr:constexpr可以说是对const变量的扩展，它只是约束const变量的右侧的式子必须能在编译时就能算出值 待补充。。。}B+树和B-树{ B-树 { 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]； 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的 子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树； B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果 命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为 空，或已经是叶子结点；任何一个关键字出现且只出现在一个结点中； } B+树 { 非叶子结点的子树指针与关键字个数相同； 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树 为所有叶子结点增加一个链指针； 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的； 不可能在非叶子结点命中； 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储 （关键字）数据的数据层； }}C++内存管理{ 在C++中，内存分成5个区，他们分别是堆、栈、自由存储区、全局/静态存储区和常量存储区。 栈，在执行函数时，函数内局部变量的存储单元都可以在栈上创建，函数执行结束时这些存储单元自动被释放。 栈内存分配运算内置于处理器的指令集中，效率很高，但是分配的内存容量有限。 堆，就是那些由new分配的内存块，他们的释放编译器不去管，由我们的应用程序去控制，一般一个new就要对应 一个delete。如果程序员没有释放掉，那么在程序结束后，操作系统会自动回收。 自由存储区，就是那些由malloc等分配的内存块，他和堆是十分相似的，不过它是用free来结束自己的生命的。 全局/静态存储区，全局变量和静态变量被分配到同一块内存中，在以前的C语言中，全局变量又分为初始化的和 未初始化的，在C++里面没有这个区分了，他们共同占用同一块内存区。 常量存储区，这是一块比较特殊的存储区，他们里面存放的是常量，不允许修改。}extern用法{ 在源文件A里定义的函数，在其它源文件里是看不见的（即不能访问）。为了在源文件B里能调用这个函数， 应该在B的头部加上一个外部声明 用到关键字extern,主要是全局变量和函数。 extern "C"的主要作用就是为了能够正确实现C++代码调用其他C语言代码。加上extern "C"后， 会指示编译器这部分代码按C语言的进行编译，而不是C++的。}无序数组找出第K大的数{ 方法一：快速排序，因为每次操作，以某个数为基准，它之前的数都<=它，之后的数都>=它，每次递归根据 判断只需去找一边。 方法二：二分[最小数，最大数]，然后做统计，最后推出那个数 方法三：先建立一个K个数的最大堆，然后判断是否要替换堆顶的值。 方法四：如果数的方位不是很大，可以用一个计数数组计数每个数出现的次数，最后从小到大扫一遍。}最大堆的代码实现{ #include #include #include using namespace std;void HeapAdjust(int *data,int id,int L){ while(id*2+1 data[id*2+1]) nid=id*2+2; } if(data[id] =0;i--) HeapAdjust(data,i,L); for(int i=L-1;i>0;i--) { swap(data[i],data[0]); HeapAdjust(data,0,i); }}int main(){ int data[]={ 3,2,5,6,4,7,8,1}; HeapSort(data,8); for(int i=0;i<8;i++) printf("%d ",data[i]); puts(""); return 0;}}hashtable和hashmap的区别{ HashMap不是线程安全的，HashTable是线程安全的 hastmap是一个接口 是map接口的子接口，是将键映射到值的对象，其中键和值都 是对象，并且不能包含重复键，但可以包含重复值。HashMap允许null key和null value， 而hashtable不允许。 最大的不同是，Hashtable的方法是Synchronize(同步)的，而HashMap不是}string和stringbuffer的区别{ String类对象为不可变对象，一旦你修改了String对象的值，隐性重新创建了一个新的对象， 释放原String对象，StringBuffer类对象为可修改对象，可以通过append()方法来修改值 String类对象的性能远不如StringBuffer类。}JVM内存模型{ 1. 程序计数器，用来选取下一条要执行的指令 2. Java虚拟机栈，用于存储局部变量表、操作栈、动态链接、方法出口等信息 3. 本地方法栈，而本地方法栈则是为虚拟机使用到的Native（一个Native Method就是一个java调用非java代码的接口。） 方法服务 4. Java 堆，所有的对象实例以及数组都要在堆上分配 5. 方法区，是各个线程共享的内存区域，它用于存储已被虚拟机加载的类信息、常量、静态变量、即时编译器编译后 的代码等数据}给出一个链表，判断是否有环{ p每次走一步，q每次走2步，这样如果存在循环节，我们假设循环节长度为m，那么肯定存在一个整数i 使得(p+i)%m=(q+2*i)%m,这样我们就可以判断是否存在循环节了。}100 个数中找重复数字{ 对所有的数据进行异或运算，最后的结果就是重复的数字 因为1到99都存在，因此可以对所有的数组求和然后减去(1+2+3……+99),最后的结果就是重复的数字。 类似于哈希的方法，记录每个数据出现的次数或者来标记是否出现过，如果在遍历数组的工程中发现某个数据已经出现过， 则该数字就是所求的重复数字。}有一个长度为100数组，里面的数字从0到99，其中有2个数字重复，请找出重复的那个数。{ 记录每个数据出现的次数或者来标记是否出现过，如果在遍历数组的工程中发现某个数据已经出现过， 则该数字就是所求的重复数字。 假设a重复了2次，b缺失，则数组求和以后减去(1+2+3+……+99)以后得到的就是a-b的值，同时对数组求 平方和然后减去(1*1+2*2+……+99*99)得到a*a-b*b的值，然后解方程组可以得到a的值，同时也可以得到b的值。}HTTP中Get和Post的区别{ GET请求的数据会附在URL之后，以?分割URL和传输数据，参数之间以&相连， POST把提交的数据则放置在是HTTP包的包体中。 GET的URL会有长度上的限制，则POST的数据则可以非常大。 POST比GET安全，因为数据在地址栏上不可见。}给你n个不重复的整数，随机找出m个不重复的整数，要求时间和空间复杂度都是O(m){ 把取出来的数与后面交换，再在前面的数中随机取}自我介绍（一分钟版本和三分钟版本）家庭情况为什么不考研你为什么想做研发（相关岗位的工作）？（以C/C++研发工程师为例）以后的职业规划？最大的优点和缺点你对这个岗位的理解你有什么想问我的？{ 对新人会怎么进行培养？ 我进去之后会做什么？ 就我之前的表现来看，您觉得我表现得好与坏的地方有哪些？ 主要用到什么技术？ ......}判断俩个链表是否相交{ 如果它们相交，则最后一个结点一定是共有的，则只需要判断最后一个结点是否相同即可。 时间复杂度为O(len1+len2)。对于相交的第一个结点，则可求出两个链表的长度，然后用长的减去短的得到一 个差值 K，然后让长的链表先遍历K个结点，然后两个链表再开始比较。}判断俩个链表是否相交，如果链表可能有环列?{ 1.先判断带不带环 2.如果都不带环，就判断尾节点是否相等 3.如果都带环，判断一链表上俩指针相遇的那个节点，在不在另一条链表上。 如果在，则相交，如果不在，则不相交。 //判断链表是否有环bool IsLoop(node *head, node **firstLoop, node **lastNode){ node *first = head; node *second = head; if(NULL == head || NULL == head->next) { return false; } do { first = first->next; //first走一步 second = second->next->next; //second走两步 }while(second && second->next && first != second); if(first == second) { *firstLoop = first; //保存环的首节点 return true; } else { *lastNode = first->next; //保存尾节点 //printf("%d\n", first->next->data); return false; } return false;}//判断两链表是否相交//1.如果都不带环，就判断尾节点是否相等//2.如果都带环，判断一链表上俩指针相遇的那个节点，在不在另一条链表上。bool IsCross(node *head1, node *head2){ node *firstLoop1 = NULL; node *firstLoop2 = NULL; node *lastNode1 = NULL; node *lastNode2 = NULL; if(NULL == head1 || NULL == head2) { printf("Link is Empty!\n"); exit(1); } bool isLoop1 = IsLoop(head1, &firstLoop1, &lastNode1); bool isLoop2 = IsLoop(head2, &firstLoop2, &lastNode2); if(!isLoop1 && !isLoop2) //两个都无环 { return (lastNode1 == lastNode2); } else if(isLoop1 != isLoop2) //一个有环，另一个无环 { return false; } else //两个都有环，判断环里的节点是否能到达另一个链表环里的节点 { node *temp = firstLoop1->next; while(temp != firstLoop1) { if(temp == firstLoop2) //判断第二个链表里的环节点是否在第一个链表中 return true; temp = temp->next; } } return false;}}判断整数序列是不是二元查找树的后序遍历结果{ #include #include #include using namespace std;bool dfs(const int a[],int l,int r){ if(l>=r) return true; int x=l; while(a[r]>a[x]) x++; for(int i=x;i #include #include using namespace std;const int maxn=105;void Reverse(char *S,int x,int y){ while(x #include using namespace std;struct Node{ int v; Node* l; Node* r;};Node* head=NULL;Node* index=NULL;void ListLink(Node* t){ t->l=index; if(index==NULL) head=t; else index->r=t; index=t; printf("%d ",t->value);}void InOrderBSTree(Node* t){ if(t==NULL) return; if(t->l!=NULL) InOrderBSTree(t->l); ListLink(t); if(t->r!=NULL) InOrderBSTree(t->r);}int main(){ return 0;}}查找单向链表中倒数第K个节点{ 设置两个指针，第一个先走K+1 步，第二个指针不动，然后再一起走，直到第一个指针走到链表末尾。}字符串的赋值运算符重载{ String& operator = (const String& str) { if(this==&str) return *this; if(data!=NULL) delete []data; data=new char[strlen(str)+1]; strcpy(data,str.data); return *this; }}从尾到头输出链表{ 1.递归 2.用栈维护}O(1)时间删除链表节点{ 把下一个结点值拷贝到该节点，实际删除下一个结点。如果该节点是尾节点，则遍历链表删除。时间复杂度O(1)}找出数组中两个只出现一次的数字{ 全部异或一遍，必然得到不为0的值，找到该值第一个为1的位，然后根据数组中的数是否该位上有1分成两组，在分别 找出答案。}在字符串中删除特定的字符{ 设置两个指针p,q,p指向的是删除的字符则跳过，否则把p指向的字符赋值给q,然后两个同时向前走一步。}内存泄漏 怎么处理{ 良好的编码习惯，尽量在涉及内存的程序段，检测出内存泄露。 使用智能指针 直接重载C++ new操作符，实现垃圾回收。初始化一个内存池，当内存池满的时候，进行垃圾回收操作。}指针和引用的区别{ 指针：指针是一个变量，只不过这个变量存储的是一个地址，指向内存的一个存储单元；而引用跟原来的变 量实质上是同一个东西，只不过是原变量的一个别名而已 指针的值可以为空，但是引用的值不能为NULL，并且引用在定义的时候必须初始化； 可以有const指针，但是没有const引用}C++析构函数为什么要为虚函数{ 在实现多态时，当用基类操作派生类，在析构时防止只析构基类而不析构派生类的状况发生。避免内存泄露}STL内存分配{ 当用户用new构造一个对象的时候，其实内含两种操作：1）调用::operator new申请内存；2）调用该对象的构造函数构造此对象的内容 当用户用delete销毁一个对象时，其实内含两种操作：1）调用该对象的析构函数析构该对象的内容；2）调用::operator delete释放内存}map的迭代器失效问题{ 删除一个元素之后不能用++,迭代器失效了，可以使迭代器指向删除之后重新调整容器的下一个位置。}LRU算法{const int maxn=5;struct LRU{private: int Size; int stk[maxn];public: bool IsEmpty(){ return Size==0; } bool IsFull(){ return Size==maxn-1; } int IndexOfValue(int v) { for(int i=0;i =1;i--) { if(isupper(S[i])) continue; int j=i; while(j>=0&&islower(S[j])) j--; if(j<0) break; char temp=S[j]; for(int k=j;k 操作符，否则将引擎放弃使用索引而进行全表扫描 应尽量避免在 where 子句中对字段进行 null 值判断，否则将导致引擎放弃使用索引而进行全表扫描 拆分表： 分区将数据在物理上分隔开，不同分区的数据可以制定保存在处于不同磁盘上的数据文件里 使用数据库缓存 常用查询，建立索引，使用索引 尽可能的使用 varchar/nvarchar 代替 char/nchar 应尽量避免在 where 子句中使用 or 来连接条件 对于连续的数值，能用 between 就不要用 in 了}STL{ vector 有insert操作，erase操作，底层容器是数组 list 底层容器是双向链表，push_back,push_front ,empty deque 底层数据结构是一个中央控制器加缓冲区，用堆来保存 stack 底层容器是list或deque queue 底层容器是list或deque priority_queue 底层容器是vector,以heap来管理 set,map,multimap,multiset 底层用红黑树 hash_set,hash_map用哈希表}测试用例{ 在边界测试中，对于有n个输入变量的程序，基本边界值分析的测试用例个数为4n+1。 在健壮性测试中，对于有n个输入变量的程序，健壮性测试的测试用例个数为6n+1。 对于有n个输入变量的程序，最坏情况测试的测试用例个数为5^n。 对于有n个输入变量的程序，健壮最坏情况测试的测试用例个数为7^n。}TCP/IP{ HTTP（超文本传输协议）是一个基于请求与响应模式的、无状态的、应用层的协议。 HTTP是应用层协议，TCP，UDP是传输层协议。 文件传输协议FTP、电子邮件传输协议SMTP、域名系统服务DNS、HTTP协议等都同是应用层协议。 HTTP协议 状态代码有三位数字组成，第一个数字定义了响应的类别，且有五种可能取值： 1xx：指示信息--表示请求已接收，继续处理 2xx：成功--表示请求已被成功接收、理解、接受 3xx：重定向--要完成请求必须进行更进一步的操作 4xx：客户端错误--请求有语法错误或请求无法实现 5xx：服务器端错误--服务器未能实现合法的请求 常见状态代码、状态描述、说明： 200 OK //客户端请求成功 400 Bad Request //客户端请求有语法错误，不能被服务器所理解 401 Unauthorized //请求未经授权，这个状态代码必须和WWW-Authenticate报头域一起使用 403 Forbidden //服务器收到请求，但是拒绝提供服务 404 Not Found //请求资源不存在，eg：输入了错误的URL 500 Internal Server Error //服务器发生不可预期的错误 503 Server Unavailable //服务器当前不能处理客户端的请求，一段时间后可能恢复正常}