1.构建一个类MySingleton,这类只能有一个例子. 思路: 写构造函数private构造函数可以通过成员静态函数调用:) 例: #include "iostream.h" class MySingleton { private: static MySingleton* _instance; MySingleton(){ cout << "Construct MySingleton" << endl; } ///私有构造函数 ~MySingleton(){ cout << "Destroy MySingleton" << endl; } public: static MySingleton& GetInstanceRef() { if (_instance == 0) _instance = new MySingleton; return *_instance; } static MySingleton* GetInstancePtr() { return &GetInstanceRef(); } static ReleaseInstance() { if (_instance != 0) { delete _instance; _instance=0; } } }; MySingleton* MySingleton::_instance=0; int main(int argc, char* argv[]) { MySingleton& my=MySingleton::GetInstanceRef(); MySingleton::ReleaseInstance(); return 0; } 2.为什么两次结果不同？ #include "stdio.h" char* Test1() { char string[10]; char* str="0123456"; return string; } char* Test2() { char string[10]; char* str="0123456"; return str; } void main() { printf("%s\n",Test1()); printf("%s\n",Test2()); } 1.程序的输出是什么？(F) #include "stdafx.h" #include "stdio.h" int main() { int i,sum; for( i=1;i<=3;i ) sum =i; printf("%d",sum); return 0; } sum没有初始化，所以结果是不可预测的。 补充:在VC debug中,如果int类型变量不初始化，一般初始化为0xcccccccc。 而在release初始化，初始化值是不同的。在使用变量时，我们不应该依赖编译器 初始化，但要初始化自己的显式。 扩展： 局部变量在栈中，值不确定(前面说的不对，与编译器无关，因为在声明局部变量时，即使是初始值编译后，也要加一个赋值句，也就是说 int i=0; 等于 int i; i=0；两个句子！！没有一个编译器会对局部变量如此愚蠢，默认值...) 全局和static在静态区.也就是程序的数据段.因为这个数据段不像动态分配，无论如何都要写东西.所以默认情况自然是0。如果你想有一个随机值编译器，你必须一个接一个地生成随机数。.这里赋予初值，不需要再有一个赋值句。.因为这个值写在程序二进制文件中.如果定义了全局变量int i=1; 打开二进制，可以在i的地址上找到写着1的值. 学会分析汇编代码：反汇编每个C语言代码 2.写结构函数和赋值运算符(T) #include "iostream.h" class Test { public: int m_i; public: Test(); ///默认构建函数.当Test t2;时调用 Test(int i); //Test t1(4)；调用时间 Test(const Test& t); //复制构造函数.当Test t2=t1;或Test t2(t1);时调用 Test& operator=(const Test&); ///赋值运算符函数重载.t2=t1;时调用 }; Test::Test() { m_i=0; } Test::Test(int i) { m_i=i; } Test::Test(const Test& t) { m_i=t.m_i; } Test& Test::operator=(const Test& t) { m_i=t.m_i; return *this; } void main() { Test t1(4); Test t2; t2=t1; cout<<t2.m_i<<endl; } 注意： Test t2=t1; 和 Test t2; t2t1; 是不一样的。前者调用拷贝构造函数，后者先调用默认构造函数，然后调用赋值运算符函数。 3.虚函数(F) 多态性可以改善代码的组织性和可读性，同时也使创建的程序具有可扩展性。而虚函数是实现多态的重要方法。 而虚函数又是通过虚表和虚表指针实现的。 4.cast (以后程序中转换都用这几个操作符，以示专业,哈哈) There are several casting operators specific to the C++ language. These operators are intended to remove some of the ambiguity and danger inherent in old style C language casts. These operators are: dynamic_cast Used for conversion of polymorphic types. 使用该操作符时，必须: 1.开启/GR编译选项，可以通过Project->Settings->C/C++->Category下的C/C++ Language(Enable ... RTTI) 2.被转换的指针必须是多态类,也就是带虚函数的类,被转换成的类和被转换类可以没有任何关系 3.不能将const转换为非const 所以dynamic_cast是最安全的转换，只有能够安全的转换时才能转换成功，转换时优先考虑dynamic_cast static_cast Used for conversion of nonpolymorphic types. 使用该操作符时，必须： 1.被转换成的类和被转换类必须是继承关系，否则编译都通不过 2.即使是多态类也可以转换，但没有安全性，不会转换失败，仅仅把指针的值赋过去而已 3.不能将const转换为非const const_cast Used to remove the const, volatile, and __unaligned attributes. 使用该操作符时，必须： 1.只能转换同一类型，去掉const,volatile, and __unaligned属性。 reinterpret_cast Used for simple reinterpretation of bits. 跟C中老的转换完全一样，不在迫不得已的情况下，不要用它。 Use const_cast and reinterpret_cast as a last resort, since these operators present the same dangers as old style casts. However, they are still necessary in order to completely replace old style casts. 例： class B { public: virtual ~B(); }; B::~B() { } class D : public B { /*...*/ }; void f(B* pb) { D* pd1 = dynamic_cast<D*>(pb); // pb必须是多态类,且将父类转换为子类是不安全的,所以转换失败,pd1 = NULL D* pd2 = static_cast<D*>(pb); // 而static_cast不管这些，只管硬转 } void main() { B* pb = new B(); f(pb); system("pause"); } 5.写一个双向链表 6.关于成员变量初始化顺序 根据成员变量在类中声明的先后顺序进行初始化。 7.纯虚函数,虚析构函数(理解得不清楚) 例: #include "iostream.h" class Base1 { public: ~Base1(){cout<<"~Base1\n";} }; class Derived1:public Base1 { public: ~Derived1(){cout<<"~Derived1\n";} }; class Base2{ public: virtual ~Base2(){cout<<"~Base2\n";} }; class Derived2:public Base2{ public: ~Derived2(){cout<<"~Derived2\n";} }; void main(){ Base1* bp=new Derived1; delete bp; Base2* b2p=new Derived2; delete b2p; } 结果： ~Base1 ~Derived2 ~Base2 注： 当想通过基类指针操纵子类对象时，如果析构函数不是虚函数，那么在delete时子类的构造函数将不会被调用。 当基类的析构函数是虚的时，子类的析构函数会覆盖基类的析构函数，所以，delete时会调用基类的析构函数，而在子类析构函数最后，又会调用基类的析构函数，所以出现上面的结果。 8.写一个单链表 9.写个is-a和has-a(T) 组合常常被称为"has-a"(有)关系，比如"在小汽车中有发动机" 继承常常被称为"is-a"(是)关系， 比如"圆形是一种形体" 当我们在选择使用组合还是继承时就可以根据这两种模型判断。 你可以说小汽车是发动机吗？不能。所以我们选择组合 你可以说圆形里面有形体吗？不能。所以我们用继承 has-a： class Engine{ public: void start() const{} void stop() const{} }; class Wheel{ public: void inflate(int psi) const{} }; class Car{ public: Engine engine; Wheel wheel[4]; }; void main() { Car car; } is-a： class Pet{ public: void eat() const{} }; class Goldfish:public Pet{ public: void swim() const{} }; void main() { Goldfish goldfish; } 10.struct vs. class. struct默认成员是public class默认默认成员是private 除此之外两者没有本质上的区别。 但一般习惯上我们在定义纯数据结构的时候用struct.否则用class. 11.STL里面vector的实现(内部空间的申请与分配) 12.怎样使一个class不能被实例化 1.构造函数私有化2.抽象类 13.私有继承和public继承的区别 私有集成表示父类的所有共有函数在子类中都变成了私有函数，外部函数通过子类指针或对象不能访问父类的共有函数。 注意：私有继承并不是子类的成员函数也不能访问父类的共有函数，父类的所有保护或共有成员在子类的成员函数中都是可以访问的。 什么继承只能影响继承树外的访问!谨记!不要混淆了。 14.void *p的问题 不能使用++等指针算术(会出现error C2036: 'void *' : unknown size) 15.引用和指针的区别与联系 引用类似于常量指针，一旦初始化，不能更改 16.简述一下hash算法 17.一个32位的数据，怎样找到最左边的一个1 18.一个4*4的格子，填入1~15 然后给个目标状态，怎样去搜索。 19.给你100万个数据，数据的值在0~65535之间 用最快的速度排序 20.最后一个问题： 如果我们的一个软件产品，用户回复说：运行速度很慢，你怎么处理 21.n位的2进制数据怎样找最左边的1，如果是在最左位，这个数是负数，否则的话，左移 一位，看是否变成负数，这是O(n)的算法，O(n/2)的算法：二分方式查找 22.广度优先搜索+启发式 23.统计每个数字出现的频率 24.八皇后问题，详述解法 ---轻松搞定 25.kmp快速匹配算法 ---不算轻松的搞定 26.无向图中两点间最短路问题 ---伟大的迪杰克斯拉算法 27.空间中任意给两个向量，求角平分线 他给了个提示，解决 28.什么是平衡树 ---光说上概念来了，其他的不会了（昨晚光看b-,b+树了） 29.哈夫曼编码问题 ---回答的有些混乱 30.求1~10000的素数 ---筛选法，有点细节没处理好 31.有向图求环 ---我只会搜索，在他的提示下，还是没有做出来 32.给n个点，求凸包问题 ---hiahia，牛X一把，用二分作的！ 33.堆排序 ---明确地告诉了他，俺忘了 34.四则运算 (1)给一个前缀表达式，然后求解 ---勉强做上来了 (2)给一个中缀表达式，求解 ---更勉强的作上来了 35.正则表达式 ---一开始不知道什么东西，后来他一解释，原来是正规式，刚考完，轻 松搞定 36.STL中container有哪些？ 答：vector，list，set，multiset，map，multimap，deque，bitset 2.map中的数据存储方式是什么？ 答：Hashtable 3.map和hashmap有什么区别？ 答：不知道。 4.hashmap是标准库中的吗？ 答：不是。 5.vector中的erase方法跟algorithm的remove有什么区别？ 答：我不怎么清楚，只知道remove_if可以用function object。还有可能vector自带的erase在执行过后会有一些优化的方法吧。 6.function object是什么？ 答：（这个我说了半天，反正就是描述一下） 2. 一般在什么时候构造函数被声明成private呢？ 答：比如要阻止编译器生成默认的copy constructor 3. 什么时候编译器会生成默认的copy constructor呢？ 答：只要自己没写，而程序中需要，都会生成 4. 如果你已经写了一个构造函数，编译器还会生成copy constructor吗？ 答：会 7. 为什么说如果一个类作为基类，则它的析构函数要声明成virtual的？ 答：(Effective C++ 条款14，我当时刚刚复习过，呵呵) 8. inline的函数和#define有什么区别？ 答：类型检查 9. inline是什么意思？ 答：就是不产生call，直接把函数的代码嵌入程序。但是inline不是强制的，是 编译器根据需要决定函数是否真的被inline 10. 那你说说什么时候会真的被inline，什么时候不会呢？ 答：（略） 11. 如果把一个类的成员函数写在类的声明中是什么意思？ 答：inline 12. public继承和private继承有什么架构上的区别？ 答：public是is-a的关系，private是has-a的关系 13. 在多继承的时候，如果一个类继承同时继承自class A和class B，而class A和 B中都有一个函数叫foo()，如何明确的在子类中指出override哪个父类的foo()？ 答：虚拟继承吧……（我想了半天也不记得这个怎么弄了，他也就没有继续难为 我） 14. 虚拟继承的语法是什么？ 答：class C : public A, virtual public B 15. 部分模版特例化（我忘了他当时怎么翻译这个词的了，反正就是partial temp late specialization）和全部模版特例化有什么区别？ 答：（想了半天）就是是不是还有一个通用的模版的区别。这个特性在VC中不支 持，所以我不是很熟悉，不好意思…… 16. 哦？VC不支持？你确定 答：确定！（.net刚出的时候，我特意看过MSDN，上面写着VC7.0中有3个C++的 特性没有支持，其中就有这个，没想到他连这个都考！） 1.编一个函数，使一个单向链表转置 2.拆解一个整数，比如4,可以拆解成 4=3+1 4=2+2 4=2+1+1 4=1+1+1+1 4.不用库函数，实现strcpy或者memcpy等函数 1．已知strcpy 函数的原型是： char *strcpy(char *strDest, const char *strSrc); 其中strDest 是目的字符串，strSrc 是源字符串。不调用C++/C 的字符串库函数，请编写函数strcpy 答案： char *strcpy(char *strDest, const char *strSrc) { if ( strDest == NULL || strSrc == NULL) //VC上的strcpy函数是没有这个检查的，如果传递NULL，程序直接出线访问非法内存 return NULL ; if ( strDest == strSrc) return strDest ; char *tempptr = strDest ; while( (*strDest++ = *strSrc++) != '\0') ; return tempptr ; } 2．已知类String 的原型为： class String { public: String(const char *str = NULL); // 普通构造函数 String(const String &other); // 拷贝构造函数 ~ String(void); // 析构函数 String & operate =(const String &other); // 赋值函数 private: char *m_data; // 用于保存字符串 }; 请编写String 的上述4 个函数。 答案： String::String(const char *str) { if ( str == NULL ) //strlen在参数为NULL时会抛异常才会有这步判断 { m_data = new char[1] ; m_data[0] = '' ; } else { m_data = new char[strlen(str) + 1]; strcpy(m_data,str); } } String::String(const String &other) { m_data = new char[strlen(other.m_data) + 1]; strcpy(m_data,other.m_data); } String & String::operator =(const String &other) { if ( this == &other) return *this ; delete []m_data; m_data = new char[strlen(other.m_data) + 1]; strcpy(m_data,other.m_data); return *this ; } String::~ String(void) { delete []m_data ; } 3.简答 1. 头文件中的ifndef/define/endif 是干什么用的? 答:防止该头文件被重复包含 2.#include <filename.h> 和#include “filename.h” 有什么区别？ 答：对于#include <filename.h> ，编译器从标准库路径开始搜索filename.h 对于#include "filename.h"，编译器从用户的工作路径开始搜索filename.h 3. 在C++ 程序中调用被C 编译器编译后的函数，为什么要加extern "C"? 答：C++语言支持函数重载，C 语言不支持函数重载。函数被C++编译后在库中的名字与C 语言的不同。假设某个函数的原型为： void foo(int x, int y); 该函数被C 编译器编译后在库中的名字为_foo ， 而C++ 编译器则会产生像_foo_int_int 之类的名字。 C++提供了C 连接交换指定符号extern“C”来解决名字匹配问题。 4.一个类有基类、内部有一个其他类的成员对象，构造函数的执行顺序是怎样的? 答：先执行基类的(如果基类当中有虚基类，要先执行虚基类的，其他基类则按照声明派生类时的顺序依次执行)，再执行成员对象的，最后执行自己的。 3.5 请描述一个你熟悉的设计模式(Autodesk) 6.在UML 中，聚合(aggregation)和组合(composition)有什么区别 (Autodesk) 答案：聚合关系更强，类似于pages 和book 的关系;组合关系要弱，类似于books和bookshelf 的关系。 7.C#和C++除了语法上的差别以外，有什么不同的地方？(Autodesk，Microsoft) 答案：（C#我只是了解，不是很精通） (1) c#有垃圾自动回收机制，程序员不用担心对象的回收。(2)c#严禁使用指针，只能处理对象。如果希望使用指针，则仅可在unsafe 程序块中能使用指针。(3)c#只能单继承。(4)必须通过类名访问静态成员。不能像C++中那样，通过对象访问静态成员。(5)在子类中覆盖父类的虚函数时必须用关键字override,覆盖父类的方法要用关键字new 8.ADO.net 和ADO 的区别？ 答案：实际上除了“能够让应用程序处理存储于DBMS 中的数据“这一基本相似点外，两者没有太多共同之处。但是ADO 使用OLE DB 接口并基于微软的COM 技术，而ADO.NET 拥有自己的ADO.NET 接口并且基于微软的.NET 体系架构。众所周知.NET 体系不同于COM 体系，ADO.NET 接口也就完全不同于ADO和OLE DB 接口，这也就是说ADO.NET 和ADO是两种数据访问方式。ADO.net 提供对XML 的支持。 9. new delete 与malloc free 的区别 ( Autodesk) 答案：用malloc 函数不能初始化对象，new 会调用对象的构造函数。delete 会调用对象的destructor，而free 不会调用对象的destructor. 10. #define DOUBLE(x) x+x (Autodesk) i = 5*DOUBLE(10)； i 是多少？正确的声明是什么？ 答案：i 为60。正确的声明是#define DOUBLE(x) (x+x) 11. 有哪几种情况只能用intialization list 而不能用assignment? (Autodesk) 答案：当类中含有const、reference 成员变量；基类的构造函数都需要参数；类中含有其他类的成员对象，而该类的构造函数都需要参数。 12. C++是不是类型安全的？ (Autodesk) 答案：不是。两个不同类型的指针之间可以强制转换。C#是类型安全的。 13. main 函数执行以前，还会执行什么代码？ (Autodesk) 答案：全局对象的构造函数会在main 函数之前执行。 13. 描述内存分配方式以及它们的区别。 (Autodesk , Microsoft) 答案： (1) 从静态存储区域分配。内存在程序编译的时候就已经分配好，这块内存在程序的整个运行期间都存在。例如全局变量，static 变量。 (2) 在栈上创建。在执行函数时，函数内局部变量的存储单元都可以在栈上创建，函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集。 (3) 从堆上分配，亦称动态内存分配。程序在运行的时候用malloc 或new 申请任意多少的内存，程序员自己负责在何时用free 或delete 释放内存。动态内存的生存期由我们决定，使用非常灵活，但问题也最多。 14. 什么是虚拟存储器？virtual memory 怎样映射到physical memory?页面替换算法有哪些？ (Microsoft) 见操作系统 p238 页。掌握的页面替换算法NRU，FIFO，第二次机会页面替换算法，LRU 15. 有四个同样的容器，里面装满了粒数相同的药丸，正常药丸的质量为m,变质药丸的质量为m+1,现在已知这四个容器中，有一个装的全是变质药丸，用电子秤只称一次，找出哪个容器装的是变质药丸 （Microsoft） 答案：把四个容器依次编号为1、2、3、4，然后从中分别取出1、2、3、4 粒药丸，称这10 粒药丸的质量，如果质量为10m+1,则说明第一个容器装的是变质药丸，如果为10m+2 则说明第二个装的变质药丸，依次类推。 16. 比较一下C++中static_cast 和 dynamic_cast 的区别。 (Autodesk） 答案：dynamic_casts在帮助你浏览继承层次上是有限制的。它不能被用于缺乏虚函数的类型上，它被用于安全地沿着类的继承关系向下进行类型转换。如你想在没有继承关系的类型中进行转换，你可能想到static_cast 17. 当一个类A 中没有生命任何成员变量与成员函数,这时sizeof(A)的值是多少，如果不是零，请解释一下编译器为什么没有让它为零。（Autodesk） 答案：肯定不是零。我举个反例，如果是零的话，声明一个class A[10]对象数组，而每一个对象占用的空间是零，这时就没办法区分A[0],A[1]…了 18. 在8086 汇编下，逻辑地址和物理地址是怎样转换的？（Intel） 答案：通用寄存器给出的地址，是段内偏移地址，相应段寄存器地址*10H+通用寄存器内地址，就得到了真正要访问的地址。 20. 描述一下C++的多态 （microsoft） 答案：C++的多态表现在两个部分，一个是静态连编下的函数重载，运算符重载；动态连编下的虚函数、纯虚函数（抽象类） 4.写出BOOL,int,float,指针类型的变量a 与零的比较语句。 答案： BOOL : if ( !a ) int : if ( a == 0) float : const EXPRESSION EXP = 0.000001 if ( a < EXP && a >-EXP) pointer : if ( a != NULL) 5.请说出const 与#define 相比优点 答案： （1） const 常量有数据类型，而宏常量没有数据类型。编译器可以对前者进行类型安全检查。而对后者只进行字符替换，没有类型安全检查，并且在字符替换可能会产生意料不到的错误。 （2） 有些集成化的调试工具可以对const 常量进行调试，但是不能对宏常量进行调试。 6．简述数组与指针的区别 数组要么在静态存储区被创建（如全局数组），要么在栈上被创建。指针可以随时指向任意类型的内存块。 (1)修改内容上的差别 char a[] = “hello”; a[0] = ‘X’; char *p = “world”; // 注意p 指向常量字符串 p[0] = ‘X’; // 编译器不能发现该错误，运行时错误 (2) 用运算符sizeof 可以计算出数组的容量（字节数）。sizeof(p),p 为指针得到的是一个指针变量的字节数，而不是p 所指的内存容量。C++/C 语言没有办法知道指针所指的内存容量，除非在申请内存时记住它。注意当数组作为函数的参数进行传递时，该数组自动退化为同类型的指针。 char a[] = "hello world"; char *p = a; cout<< sizeof(a) << endl; // 12 字节 cout<< sizeof(p) << endl; // 4 字节 计算数组和指针的内存容量 void Func(char a[100]) { cout<< sizeof(a) << endl; // 4 字节而不是100 字节 } 7．类成员函数的重载、覆盖和隐藏区别 答案： 成员函数被重载的特征： (1)相同的范围（在同一个类中）； (2)函数名字相同； (3)参数不同； (4)virtual 关键字可有可无。 覆盖是指派生类函数覆盖基类函数，特征是： (1)不同的范围（分别位于派生类与基类）； (2)函数名字相同； (3)参数相同； (4)基类函数必须有virtual 关键字。 “隐藏”是指派生类的函数屏蔽了与其同名的基类函数，规则如下： (1)如果派生类的函数与基类的函数同名，但是参数不同。此时，不论有无virtual关键字，基类的函数将被隐藏（注意别与重载混淆）。 (2)如果派生类的函数与基类的函数同名，并且参数也相同，但是基类函数没有virtual 关键字。此时，基类的函数被隐藏（注意别与覆盖混淆） 8．There are two int variables: a and b, don’t use “if”, “? :”, “switch” or other judgement statements, find out the biggest one of the two numbers. 答案：( ( a + b ) + abs( a – b ) ) / 2 9．如何打印出当前源文件的文件名以及源文件的当前行号？ 答案： cout << __FILE__ ; cout<<__LINE__ ; __FILE__和__LINE__是系统预定义宏，这种宏并不是在某个文件中定义的，而是由编译器定义的。 10．main 主函数执行完毕后，是否可能会再执行一段代码，给出说明？ 答案：可以，可以用_onexit 注册一个函数，它会在main 之后执行int fn1(void), fn2(void), fn3(void), fn4 (void); void main( void ) { String str("zhanglin"); _onexit( fn1 ); _onexit( fn2 ); _onexit( fn3 ); _onexit( fn4 ); printf( "This is executed first.\n" ); } int fn1() { printf( "next.\n" ); return 0; } int fn2() { printf( "executed " ); return 0; } int fn3() { printf( "is " ); return 0; } int fn4() { printf( "This " ); return 0; } The _onexit function is passed the address of a function (func) to be called when the program terminates normally. Successive calls to _onexit create a register of functions that are executed in LIFO (last-in-first-out) order. The functions passed to _onexit cannot take parameters. 11．如何判断一段程序是由C 编译程序还是由C++编译程序编译的？ 答案： #ifdef __cplusplus cout<<"c++"; #else cout<<"c"; #endif 12．文件中有一组整数，要求排序后输出到另一个文件中 答案： void Order(vector<int> &data) //起泡排序 { int count = data.size() ; int tag = false ; for ( int i = 0 ; i < count ; i++) { for ( int j = 0 ; j < count - i - 1 ; j++) { if ( data[j] > data[j+1]) { tag = true ; int temp = data[j] ; data[j] = data[j+1] ; data[j+1] = temp ; } } if ( !tag ) break ; } } void main( void ) { vector<int>data; ifstream in("c:\\data.txt"); if ( !in) { cout<<"file error!"; exit(1); } int temp; while (!in.eof()) { in>>temp; data.push_back(temp); } in.close(); Order(data); ofstream out("c:\\result.txt"); if ( !out) { cout<<"file error!"; exit(1); } for ( i = 0 ; i < data.size() ; i++) out<<data[i]<<" "; out.close(); } 13．排序方法比较 (intel) 排序方法 平均时间 最坏时间 辅助存储 直接插入排序 起泡排序 快速排序 简单选择排序 堆排序 归并排序 基数排序 14．一个链表的结点结构 struct Node { int data ; Node *next ; }; typedef struct Node Node ; (1)已知链表的头结点head,写一个函数把这个链表逆序 ( Intel) Node * ReverseList(Node *head) //链表逆序 { if ( head == NULL || head->next == NULL ) return head; Node *p1 = head ; Node *p2 = p1->next ; Node *p3 = p2->next ; p1->next = NULL ; while ( p3 != NULL ) { p2->next = p1 ; p1 = p2 ; p2 = p3 ; p3 = p3->next ; } p2->next = p1 ; head = p2 ; return head ; } (2)已知两个链表head1 和head2 各自有序，请把它们合并成一个链表依然有序。 Node * Merge(Node *head1 , Node *head2) { if ( head1 == NULL) return head2 ; if ( head2 == NULL) return head1 ; Node *head = NULL ; Node *p1 = NULL; Node *p2 = NULL; if ( head1->data < head2->data ) { head = head1 ; p1 = head1->next; p2 = head2 ; } else { head = head2 ; p2 = head2->next ; p1 = head1 ; } Node *pcurrent = head ; while ( p1 != NULL && p2 != NULL) { if ( p1->data <= p2->data ) { pcurrent->next = p1 ; pcurrent = p1 ; p1 = p1->next ; } else { pcurrent->next = p2 ; pcurrent = p2 ; p2 = p2->next ; } } if ( p1 != NULL ) pcurrent->next = p1 ; if ( p2 != NULL ) pcurrent->next = p2 ; return head ; } (2)已知两个链表head1 和head2 各自有序，请把它们合并成一个链表依然有序，这次要求用递归方法进行。 ( Autodesk) 答案： Node * MergeRecursive(Node *head1 , Node *head2) { if ( head1 == NULL ) return head2 ; if ( head2 == NULL) return head1 ; Node *head = NULL ; if ( head1->data < head2->data ) { head = head1 ; head->next = MergeRecursive(head1->next,head2); } else { head = head2 ; head->next = MergeRecursive(head1,head2->next); } return head ; } 15.不运行程序写出该程序的运行结果?(T) 答案： #include "iostream.h" class B { public: B() { cout<<"default constructor"<<endl; } ~B() { cout<<"destructed"<<endl; } B(int i):data(i) { cout<<"constructed by parameter " << data <<endl; } private: int data; }; B Play( B b) { return b ; } int main(int argc, char* argv[]) { B temp = Play(5); return 0; } 运行结果： constructed by parameter 5 destructed destructed 注释：上面这个题主要涉及自动类型转换。 见<<Thinking in C++>>中296页。在C和C++中，如果编译器看到一个表达式或函数使用了一个不适合的内部类型，他经常会执行一个自动类型转换，从现在的类型到所要求的类型。在C++中，可以通过定义自动类型转换函数来为用户定义类型达到相同效果。这些函数有两种类型：特殊类型的构造函数和重载的运算符。在上例中，Play需要一个B类型的参数，但是我们传入的实参类型是int,此时，编译器会查看是否有适当的自动类型转换函数将int转变为B.显然，通过构造函数B(int i)可以实现。当Play返回之后，产生了一个临时B对象，然后编译器调用拷贝构造函数用临时对象初始化temp.因为我们没有定义拷贝构造函数，所以编译器默认产生一个拷贝构造函数，它的功能仅仅是进行位拷贝而已。这一条语句执行完，临时对象被销毁，调用析构函数。当出了main函数后，temp调用析构函数。:) 16.写一个函数,找出一个整数数组中，第二大的数(microsoft)(T) 注意:类似于1 4 4 4这样的序列将认为1是第二大数 答案：(这是别人的答案,我使了一下,有点错,像上面的那种序列会找出结果为4,而不是1) const int MINNUMBER = -32767 ; int find_sec_max( int data[] , int count) // { int maxnumber = data[0] ; int sec_max = MINNUMBER ; for ( int i = 1 ; i < count ; i++) { if ( data[i] > maxnumber ) { sec_max = maxnumber ; maxnumber = data[i] ; } else { if ( data[i] > sec_max )//没考虑到data[i]等于maxnumber但data[i]大于sec_max 这种情况,应该什么都不做 sec_max = data[i] ; } } return sec_max ; } (这是我的答案)： const int MINNUMBER=0x10000000; bool find_sec_max(int data[],int count,int* result) { int maxnumber;int sec_num; maxnumber=data[0]; sec_num=MINNUMBER; for(int i=1;i<count;i++) { if(data[i]>maxnumber) { sec_num=maxnumber; maxnumber=data[i]; continue; } if(data[i]<maxnumber) { if(data[i]>sec_num) sec_num=data[i]; } } if(sec_num==MINNUMBER) return false; *result=sec_num; return true; } 17.写一个在一个字符串中寻找一个子串第一个位置的函数(T) 这个题目的一般算法比较简单我就不给出了，如果要求高效率的话请参见数据结构中的KMP 算法，不过在笔试时间有限情况下，写出那个算法还是挺难的。 布鲁特-福斯算法(简单,低效率): bool find(char* source,char* desc,int* pos)//pos用来接收匹配时主串的数组下标 { for(int i=0;i<strlen(source);i++) { for(int j=0;j<strlen(desc);j++) { if(source[i+j]!=desc[j]) break; if(j==strlen(desc)-1) { *pos=i; return true; } } } return false; } KMP算法(复杂,高效率): 1.用c实现两个128位正整数的最小公倍数 主要考虑大数类 1.#include "stdio.h" int iszero(unsigned char a[],int n) { int i; for(i=0;i<n;i++) if(a[i]!='0') return 0; return 1; } void init(unsigned char a[],int n,unsigned char c) { int i; for(i=0;i<n;i++) a[i]=c; } void copy(unsigned char a[],unsigned char b[],int n) { int i; for(i=0;i<n;i++) b[i]=a[i]; } int len(unsigned char a[],int an) { for(int i=0;i<an;i++) if(a[i]==0) return i; } void standard(unsigned char a[],int an) { int la,i; la=len(a,an); if(la<an) { for(i=0;i<la;i++) { a[an-i]=a[la-i]; } for(i=la;i<an;i++) { a[an-i]='0'; } } } int greater(unsigned char a[],int an,unsigned char b[],int bn) { int i,la,lb; la=len(a,an); lb=len(b,bn); if(la>lb) return 1; if(la<lb) return -1; for(i=0;i<la;i++) { if(a[an-la+i]>b[an-la+i]) return 1; if(a[an-la+i]<b[an-la+i]) return -1; } return 0; } void minus(unsigned char a[],int an,unsigned char b[],int bn,unsigned char c[],int cn) { int i,la,lb,carry=0; la=len(a,an); lb=len(b,bn); if(greater(a,an,b,bn)<0) return; init(c,cn,'0'); for(i=0;i<la;i++) { c[an-1-i]=a[an-1-i]-b[an-1-i]-carry+'0'; carry=0; if (c[an-1-i]<'0') { c[an-1-i]+=10;carry=1;} } } void mod(unsigned char a[],int an,unsigned char b[],int bn,unsigned char c[],int cn) { init(c,cn,'0'); while(greater(a,an,b,bn)>=0) { minus(a,an,b,bn,c,cn); copy(c,a,cn); } } void main() { unsigned char a[128],b[128],c[128],d[128],e[128]; int i; init(a,128,NULL); init(b,128,NULL); init(c,128,NULL); init(d,128,NULL); printf("input a:\n"); scanf("%c",&a[i]); printf("input b:\n"); scanf("%c",&b[i]); standard(a,128); standard(b,128); if(greater(a,128,b,128)<0) { copy(a,c,128); copy(b,a,128); copy(c,b,128); } copy(a,c,128); copy(b,d,128); init(e,128,'0'); mod(c,128,d,128,e,128); while(iszero(e,128)==0) { copy(d,c,128); copy(e,d,128); init(e,128,'0'); mod(c,128,d,128,e,128); } for(i=0;i<len(d,128);i++) printf("%c",d[i]); } 求的是最大公约数,用char a[128]放数据 2.Windows中COM编程中如何判断两个interface的指针是同一个父COM对象 3.TCP/IP连接的唯一性如何确定 三次握手 6.线程的优缺点，编程中应该注意的问题 线程执行开销小，但不利于资源的管理和保护；而进程刚好相反。 面试时最经常被问到的问题（Frenquently asked interview questions）之C/C++篇 选择自 mxclxp 的 Blog - [ 找工作 ] 面试时最经常被问到的问题（Frenquently asked interview questions）之C/C++篇 选择自 mxclxp 的 Blog 以下接连几篇文章来自于：http://www.acetheinterview.com，本人只是做了搜集整理工作。希望对大家有用。 C/C++ Questions & Answers (1’ ~ 21’) 1、What is polymorphism? 'Polymorphism' is an object oriented term. Polymorphism may be defined as the ability of related objects to respond to the same message with different, but appropriate actions. In other words, polymorphism means taking more than one form. Polymorphism leads to two important aspects in Object Oriented terminology - Function Overloading and Function Overriding. Overloading is the practice of supplying more than one definition for a given function name in the same scope. The compiler is left to pick the appropriate version of the function or operator based on the arguments with which it is called. Overriding refers to the modifications made in the sub class to the inherited methods from the base class to change their behaviour. 2、What is operator overloading? When an operator is overloaded, it takes on an additional meaning relative to a certain class. But it can still retain all of its old meanings. Examples: 1) The operators >> and << may be used for I/O operations because in the <iostream> header, they are overloaded. 2) In a stack class it is possible to overload the + operattor so that it appends the contents of one stack to the contents of another. But the + operator still retains its original meaning relative to other types of data. Also Polymorphism can be achieved in C++ through operator overloading 3、Declare a void pointer. I think the answer is simply void* p; malloc is just the library function called to allocated some memory and of course a void pointer will be returned , but it is the declaration of a void pointer. 4、What are templates? C++ Templates allow u to generate families of functions or classes that can operate on a variety of different data types, freeing you from the need to create a separate function or class for each type. Using templates, u have the convenience of writing a single generic function or class definition, which the compiler automatically translates into a specific version of the function or class, for each of the different data types that your program actually uses. Many data structures and algorithms can be defined independently of the type of data they work with. You can increase the amount of shared code by separating data-dependent portions from data-independent portions, and templates were introduced to help you do that. 5、Type-define a function pointer which takes a int and float as parameter and returns a float *. the pointer to function can be type defined as: typedef float*(*pf)(int a, float b) tagPF; 6、What does the following C statement do? while(*c++ = *d++); assuming c and d are pointers to characters. String copy is performed indeed but be careful with the space allocated for the destination string. Check this example: char s1[10]="abcde"; char s2[3]; char* c,*d; c=s2; d=s1; while(*c++ = *d++); printf("%s - %s\n",s1,s2); The code is string copy. But it does not add a null pointer to the end（＊）. There should also be a check for overlapping addresses（O）. 7、How do you call a C module within a C++ module. You should use extern "C" for functions, compiled by C compiler and called within a C++ class. You should do that to force the linker to resolve the function name (precisely, the mangling of the name) correctly. 8、What is the difference between run time binding and compile time binding? Discuss. Compile Time Binding : In case of operator overloading and function overloading the name of the function is resolved during the compile time . Even if there are two or more functions with the same name the compiler mangles the name so that each function is uniquely identified . This has to be resolved at compile time and is known as compile-time binding or early binding. Run Time Binding : In case of polymorphism (virtual functions) if a base class pointer(or reference) is allocated a pointer(or reference) of derived class the actual function called is determined only during runtime through the virtual table entry . This is runtime binding or late binding 9、Compare and contrast C++ and Java. 1>Platform Independent : Java code is said to be a multiplatform code and can run on any platform because after the compilation of the source code byte code(s) are created rather than a binary code so it can run on any platform which supports JVM concept but on the contrast at time(s) it slows down the application tremendously 2> Garbage Collection : Java handles freeing up of the memory but this is not guranteed since the GC thread has the lowest priority 3>Operator Overloading : is not provided in Java,but what are the advantages of Operator Overloading but one may question what are its advantages, well it makes a more readable and a modular code. In c++ cin and cout objects can also be overloaded which again leads to a better readability and flexibility 4> Multiple Inheritance : Java does provide multiple inheritance in form of Interfaces, In Java a class can not inherit from more than one class but it definitely can implement any number of interfaces 5> Templates: in c++ give such a lot of flexibility and avoids redundant coding which again is not provided by Java 10、Why does C/C++ give better run-time performance then Java? That's because the Java bytecode is interpreted, not compiled. Programs written in C are compiled into binaries which can be executed by a specific computer processor. Programs written in Java require one more step -- they must be interpreted by the Java "virtual machine" before running on a particular computer architecture. As a result, a computer running a Java program has to execute more machine-language instructions to do the same amount of work than a computer running an equivalent program written in C. 11、Does C++ come with in-built threading support. No. C++ does not support in-built Multithreading. To do so, you must use the operating system functions manually. (Better use pthread library.) 12、Class A derived B derived C. All have foo(). I cast C to A and call foo(). What happens?（＊） --foo() for class C will be called. --it depends. if in A foo is defined as virtual function. then call C's foo(), if it doesn't defined virtual, then call A's foo() --Actually, if access is NOT specified, it deafults to private derivation. In private derivation, binding is static. So, whether foo is declared virtual or not it still defaults to static binding. So, A->foo() is called. However, If a public derivation is specified from C <-- B and B <-- A, then if foo() is virtual C->foo() is called; if foo() is non virtual A->foo() is called. --But I think there is an important thing neglected by all of you, that is ‘cast C to A’, NOT ‘cast C* to A*’, So the correct answer is A.foo() will be called. 13、All classes A, B, C have default constructor, foo() that calls parent foo() and allocates 100 bytes to their own private local variable, and a destructor that frees the 100 bytes. I create a C object and then destroy it. What's the problem? Did all the memory get freed? What if I create C, cast to A, and then destroy it. How would I make sure memory is freed? --destructor must be "virtual" and each destructor must call parent destructor 14、What errors are caught at compile time vs link time? Syntactical and symantical errors (code errors) are caught at compile time. Dependency errors (for example resolving function calls or errors in including other modules) are caught at link time. 15、What is the value of "a" after this? int (*a) [10]; a++; int (*a)[10]; represents the declaration of a pointer to an array of ten integers. So the value of a is initially some address allocated by the compiler and don't rely on the fact the address is 0 as it happens for static variables. The value can be zero if you add the "static" keyword in front of declaration but I don't advise you to further use this pointer to access some elements. If the integer is n bytes ( 2 or 4 depending on the language) it is true that the value of a will be increase with 10*n. Test this program to understand: #include <stdio.h> void main(int argc,char*argv[]) { int b[10]={1,2,3,4}; int (*a)[10]; printf("%p\n", a); // invalid address!! printf("%d\n",(*a)[0]); // runtime error!! a++; // advance 10 * sizeof(int) bytes printf("%p\n", a); a=&b; printf("%p\n", a); printf("%d\n",(*a)[0]); } 16、What is wrong with this? main(){ int *ptr; *ptr=10; } Actual reality is like this. When the pointer is declared it contains some garbage value as u know. Conceptually speaking it points to location indicated by that "garbage memory address". Now when we assign some value to *a ; i.e. *a=12; we are trying to place 12 in the memory cell number indicated by 'a' ; which in this case is any random memory address because it is garbage. So the program will be compiled fine. But when run ; if the garbage value assigned to 'a' is invalid (or restricted by OS) memory address ; the OS will generate error. So its upto OS. But technically program is fine. -Dhiraj 17、Given int n, i=10, j=20, x=3, y = 100; What is the value of n and y at the end of each of the following expressions? a) n = (i > j) && (x < ++y); b) n = (j - i) && (x < y++); c) n = (i < j) 1> n = 0, y = 100, second condition will not be evaluated. 2> n = 1, y = 101 3> n = 1, y = 100 18、int x = 5; int y = 7; What is the value of x and y after the expression y+=x++; Y = 12 and X = 6 Why? because X will be incremented after y = Y+X has been carried out and result has been assigned to Y. if it would have been y+=++x then the value of y would have been equal to 13 and x = 6 I am sure about this Mohit 19、What's the difference between C and C++? C is Top Down Approach C++ is Bottom Up Programming approach. C does not support OOP (Object Oriented Programming) and do not support PolyMorphism, Inheritence, Encapsulation, Function OverLoading. There is an important difference but often neglected by many people is the error handling. Some common C style commands and there corresponding C++ style commands are shown below. Console I/O *********** C === printf("Hello World!\n"); scanf("%s", name); C++ === cout << "Hello World!" << endl; cin >> name; Comments ******** C === /* comment */ C++ === // comment File extensions *************** C === .c, .h C++ === .C, .h, .CPP, .HPP File I/O ********* C === out = fopen("output_file.dat", "wb"); in = fopen("input_file.dat", "rb"); C++ === ofstream out("output_file.dat"); ifstream in("input_file.dat"); Dynamic Memory ************** C === text = (char *) malloc(1000); free(text); C++ === text = new char[1000]; delete [] text; Constants ********* C === #define PI 3.14159 C++ === const float PI = 3.14159; Macros ****** C === #define MAX(a,b) ((a) > (b) ? (a) : (b)) C++ === inline int MAX(int a, int b) { return a > b ? a : b; } 20、What does Public and Private mean in C++ --Public: Makes class memebrs accessible outside the class. It can be accessed in the C code. Private: Makes the members specified accessible only to the class and it's functions. --public / private have two different meanings in C++: 1. To specify the access privilege of the class members. 2. To specify what type of inheritance. 21、Is it possible to keep 2 stacks in a single array, if one grows from position one of the array, and the other grows from the last position. Write a procedure PUSH(x,s) that pushes element x onto stack S, where S is one or the other of these two stacks. Include all necessary error checks (Sent by Puneet Saraf) The question did not ask for a suggestion. It is definitely possible to implement 2 stacks using a single array. The array shud be visible to both stacks (and therefore be global, or shud provide equivalent effect). Also the stack tops shud be taken care of. one top will decrement everytime the push method is called and one would be incremented. As soon as s1.top==s2.top we shud throw an exception. 面试常考问题 1、文档在开发中的作用及重要性； 2、数据结构问题：树、二叉树、链表、队列、堆栈； 3、数据库基本知识：B_Tree、R_Tree等； 5、怎样使程序易于维护； 6、指针和引用； （1）int x = 20; Int* ptrx = &x; //声明指针，并赋值 Int z = *ptrx;//重引用指针（dereferencing pointer） 注：ptrx——x的内存地址 *ptrx——ptrx所指向的对象的值，即x的值 （2）引用（Reference） MyStruct* pStruct = new MyStruct; MyStruct& Ref = *pStruct; Ref.x = 100; 等同于 MyStruct& Ref = * new MyStruct; Ref.x = 100; （3）引用与指针的区别： 指针可以先声明再赋值； 而引用不可以，它必须在声明时就进行初始化。 用C++编程实现大数相乘的功能。编译工具不限，请在答卷中说明即可。答卷包括源代码和可执行文件。 1.A,B分别为500位以内的一个大数，请求出A*B的结果。 下面的内容可以用来验证你的功能 A= 2183924444444444448888888888888888888888500000000000000438888888888888333333333333333333333333333333333111111111111111111000000000004444444444444444475888888888888888888888888888888888888888888883499999999999999999999999999999999999999999992000000000000000000000 B= 38888888888899999999999999999999999999889999999999999999999999999999100000000000000000000000000036666666666666661711111111111111111111111111111111111111111111111111348999999999999999999999999998888888888899999999999999999999999999888888 A*B= 084930395061752661061728395061777777777522422632098761127690123456793012863061771166662666666618468966109876954310325589229851913558393813401259061729635920987666893089578354567901238378268246046746553283882310883951686248900617446672363367064666164327067654325713840070635796642855308566777190063032654321512917291554358024685185185209632790088518518570858122174339502222222222218728367117098765432038886985777777777777777778376548008888888888800000000000000000000000000888896000000000000000000000 *********************************************************************************** A= 218392444444444444044444444444444444758888888888888888888888888888888888888888888834999999999999999999999999999999999999999999920000008888888888888888888888500000000000000438888888888888333333333333333333333333333333333111111111111111111000000000004444444444444444475888888888888888888888888888888888888888888883499999999999999999999999999999999999999999992000000000000000000000 B= 3888888888889111111111111111111111111111111111111134899999999999999999999999999888888888889999999999999999999999999988889999999999999999999999999889999999999999999999999999999100000000000000000000000000036666666666666661711111111111111111111111111111111111111111111111111348999999999999999999999999998888888888899999999999999999999999999888888 A*B= 849303950617332480716049382715960495050000000000075071856804938271595422716049358240661801514251279012345678567901197203289571890122213845216790101408926381553092451407322634369444889174728395421728870318501187493790032617231707162296327851777431594889514539637277961784902110117269133818928788889019453983152957149517479011147523897533290301876458567845648319801409015506155920707870899113855038252567844183512690493833136047957481657679192421780617446915023580255777346144427654325713840070635796642855308566777190063032654321512917291554358024685185185209632790088518518570858122174339502222222222218728367117098765432038886985777777777777777778376548008888888888800000000000000000000000000888896000000000000000000000 [题目完] #include <iostream> #include <Cstring> const int MSL = 500; const int MRL = 1000; using namespace std; void Initial(char* A); void ShiftLeft(char* A, int time); void Add(char* A, char* B); void Print(char* A); int main () { char A[MSL] = "21839244444444444488888888888888888888885" "00000000000000438888888888888333333333333" "33333333333333333333311111111111111111100" "00000000044444444444444444758888888888888" "88888888888888888888888888888883499999999" "99999999999999999999999999999999999200000" "0000000000000000"; //{'\0'}; char B[MSL] = "38888888888899999999999999999999999999889" "99999999999999999999999999910000000000000" "00000000000000366666666666666617111111111" "11111111111111111111111111111111111111111" "34899999999999999999999999999888888888889" "9999999999999999999999999888888"; //{'\0'}; char C[MRL]; char D[MRL]; Initial(C); Initial(D); //cin>>A; //cin>>B; int fal = strlen(A); int fbl = strlen(B); int carry = 0; for(int i = 0; i < fbl; i++) { carry = 0; Initial(C); for(int j = 0; j < fal; j++) { int k = MRL - j - 1; int g = fal - j - 1; int h = fbl - i - 1; int facta = A[g] - 48; int factb = B[h] - 48; int result = facta * factb + carry; C[k] = (char)((result % 10) + 48); carry = result / 10; } C[MRL - j - 1] = (char)(carry + 48); ShiftLeft(C, i); Add(D, C); } Print(D); return 0; } void Initial(char* A) { for(int i = 0; i < MRL; i++) { A[i] = '0'; } return; } void ShiftLeft(char* A, int time) { for(int j = 0; j < time; j++) { for(int i = 0; i < MRL - 1; i++) { A[i] = A[i + 1]; } A[MRL - 1] = '0'; } return; } v