【转】C/C++ 面试题集锦

【转】C/C++ 面试题集锦
2011年07月10日
　　1.多态类中的虚函数表是Compile-Time，还是Run-Time时建立的?
　　第1题：虚函数表是Compile-Time时建立的
　　2.将一个 1M -10M 的文件，逆序存储到另一个文件，就是前一个文件的最后一个字符存到新文件的第一个字符，以此类推。
　　第2题：有很多不同的解法，用C还是C++、要简单还是要效率、允不允许用STL等都相关。基本想法是：如果用C，就用文件读写函数和文件指针定位函数（read, write, lseek）从输入文件的文件尾开始一个一个字符反向地读，每读一个字符，文件指针都要重定位，再顺序输出到结果文件。如果用C++/STL，就定义一个容器（vector, deque都行,list则空间效率太差），将整个输入文件一次读到容器里，用reverse反一个序，再输出到结果文件。
　　3.main主函数执行完毕后，是否可能会再执行一段代码?
　　第3题：当然有，用户自定义类型的全局变量和一些类里面的静态成员都需要析构，这些工作是在main()函数结束以后做的
　　4.一个父类写了一个virtual 函数，如果子类覆盖它的函数不加virtual ,也能实现多态?在子类的空间里，有没有父类的这个函数，或者父类的私有变量?
　　第4题：可以，只要函数中的形参类型一致就行，返回值类型可以不一样。
　　5.给一个字符串、例如“ababc”要求返回“ab”. 因为“ab”连续重复出现且最长。
　　用C/C＋＋语言写一函数完成该算法，给出复杂度
　　第5题：有点难度，一下子想不出好点子。最简单的是用三层循环来重复比较，复杂度是O(n^3)，感觉应该有更好的算法。
　　6.对序列1、1、2、3、5、8、13…… 是Fab..数列
　　2、3、5、13……是Fab..质数数列，因为他们与自己前面的Fab...数列都互质
　　给出k，返回第k小的Fab..质数
　　第6题：无算法可言，纯粹的考编程，需要一个判断是否互质的函数，然后用两层循环（外循环生成Fab数，内循环判断是否与已有数列的所有数互质）去找数列中的质数并计数，计到k时输出就是了。
　　7.101个硬币100真、1假，真假区别在于重量。请用无砝码天平称两次给出真币重还是假币重的结论。
　　第7题：先在天平的左边放30个，记为A，右边放30个，记为B，剩下41个，记为C。如果A=B，则假币在C中，再左边放C，左右放A+B中的41个，若C重则假币重，若C轻则假币轻。如果A>B，则C全为真币，从C中取30个换掉B，若A重则假币重，若A轻则假币轻，若A=C则B含假币且假币轻。如果A内存，定义则要分配内存
　　10.请写出下面代码在 32 位平台上的运行结果，并说明 sizeof 的性质：
　　#include
　　#include
　　int main(void)
　　{
　　char a[30];
　　char *b = (char *)malloc(20 * sizeof(char));
　　printf("%d\n", sizeof(a));
　　printf("%d\n", sizeof(b));
　　printf("%d\n", sizeof(a[3]));
　　printf("%d\n", sizeof(b+3));
　　printf("%d\n", sizeof(*(b+4)));
　　return 0 ;
　　}
　　第10题：运行结果如下：
　　30
　　4
　　1
　　4
　　1
　　12.请完成以下题目。注意，请勿直接调用 ANSI C 函数库中的函数实现。
　　a)请编写一个 C 函数，该函数给出一个字节中被置 1 的位的个数，并请
　　给出该题的至少一个不同解法。
　　b)请编写一个 C 函数，该函数将给定的一个字符串转换成整数。
　　c)请编写一个 C 函数，该函数将给定的一个整数转换成字符串。
　　d)请编写一个 C 函数，该函数将一个字符串逆序。
　　e)请编写一个 C 函数，该函数在给定的内存区域搜索给定的字符，并返回
　　该字符所在位置索引值。
　　f)请编写一个 C 函数，该函数在一个字符串中找到可能的最长的子字符串，
　　该字符串是由同一字符组成的。
　　给出演示上述函数功能的一个简单程序，并请编写对应的 Makefile 文件
　　13.我们需要编写一个图形相关的应用程序，需要处理大量图形(Shape)信息，图形有矩形(Rectangle)，正方形(Square)，圆形 (Circle)等种类，应用需要计算这些图形的面积，并且可能需要在某个设备上进行显示(使用在标准输出上打印信息的方式做为示意)。
　　a)请用面向对象的方法对以上应用进行设计，编写可能需要的类
　　b)请给出实现以上应用功能的示例性代码，从某处获取图形信息，
　　并且进行计算和绘制
　　c)如果你的Square继承自Rectangle，请给出理由，如果不是，
　　请给出理由，并且请比较两种方式的优劣
　　d)请问你所编写的类，在如下代码中会有何表现，请解释
　　void test_rectangle_area(Rectangle& r)
　　{
　　r.set_width(10);
　　r.set_height(15);
　　assert(r.area() == 150);
　　}
　　第13题：Shape是基类，有纯虚函数area()、draw()等；Rectangle、Square、Circle是派生类，重载各自的area()、draw()等。不建议Square派生自Rectangle，如果有继承关系，可以不用重写area()、draw()，但是对于Square要求的长宽相等则不好控制。象d)中的代码，就可能会异常中止。
　　14.假设现有一个单向的链表，但是只知道只有一个指向该节点的指针p，并且假设这个节点不是尾节点，试编程实现删除此节点
　　第14题：O(1)的办法：用p指向的节点的下一节点的值替换p指向的节点的值，然后删除p指向的节点的下一节点。
　　15.写一个程序，把一个100以内的自然数分解因数。（自然数分解因数就是将一个自然数分解为几个素数的乘积，提示,由于该数不是很大,所以可以将质数保存在数组中,以加快计算速度)
　　16.编写一个Identify的分配、释放的函数，为1－10000之间的自然数。
　　17.分别实现itoa和atoi.
　　18.Consider the following code:
　　#include
　　#include
　　int main(int argc, char *argv[]) {
　　int i = 1;
　　char buf[4];
　　strcpy(buf, "AAAA");
　　printf("%d\n", i);
　　return 0;
　　}
　　a) When compiled and executed on x86, why does this program usually not output what the programmer intended?
　　b) Name several ways in which the security problem that causes this program not to output what the programmer intended can be prevented WITHOUT changing the code.
　　第18题："AAAA"字符串实际上占了5个字节（最后有一个\0），因此strcpy到buf时引起了溢出。在x86环境下，溢出的结果可能是将i清0了，因此会输出0。
　　19.int w=1,x=2,y=3,z=4;
　　m=(w
　　main()
　　{
　　FILE *fp;
　　int i,a[4]={1,2,3,4},b;
　　fp=fopen("data.dat","wb");//这里帮忙解释一下
　　for(i=0;i中的各节点比较，如果没有发现一样的，则循环处理A的下一个节点；如果有则将B中与p相同的节点删掉，然后再在A中循环找与p相同的节点删掉，删完所有B和A中与p相同的节点后再循环处理A的下一个节点。
　　22.
　　char * GetStr()
　　{
　　char *tmp;
　　tmp = "123"
　　return tmp;
　　}
　　void main()
　　{
　　printf("%s", GetStr());
　　}
　　会输出123吗？123创建在堆上还是栈上呢？123的空间是什么时候释放的？
　　第22题：会输出123。123既不在堆上，也不栈上，它是在正文段（即与程序的代码同一段），它的空间是静态空间，程序执行完后，与整个程序一起释放。
　　23.
　　字符指针、浮点数指针、以及函数指针这三种类型的变量哪个占用的内存最大？为什么？
　　类ClassB从ClassA派生，那么ClassA *a = new ClassB(…); 试问该表达是否合法？为什么？
　　如果ClassA中定义并实现虚函数int func(void)，ClassB中也实现该函数，那么上述变量a->func()将调用哪个类里面的函数？如果int func(void)不是虚函数，情况又如何？为什么？
　　char **p, a[16][8]; 问：p=a是否会导致程序在以后出现问题？为什么？
　　如下所述的if else和switch语句哪个的效率高？为什么？
　　在同一个进程中，一个模块是否可以通过指针操作破坏其它模块的内存，为什么？
　　应用程序在运行时的内存包括代码区和数据区，其中数据区又包括哪些部分？
　　第23题：所有指针占的空间都一样，通常等于机器的字长。因为它们并不直接存放数据，而是存放一个数据存放地点的地址码，无论放什么数据，地址码所占的空间是一样的。
　　合法。基类的指针可以指向派生类的对象，反之则不行。
　　调用类B的函数；如果不是虚函数，则调用类A的函数。虚函数的调用是在运行期根据对象的实际类型动态绑定的，非虚成员函数的绑定则是在编译期根据变量类型决定的。
　　后面几个小题太微妙，不敢乱答，以免误人子弟！
　　24.Assignment 2: Picture Processing
　　Use C++, Java, or similar languages or/and any middleware such as EJB and J2EE to process a picture with a high resolution (3 Mega Pixels for example). Use some methodologies to degrade the resolution of the picture to make it quicker for browsing. Then divide the degraded picture into 9 sectors equally. Click any of the 9 sectors will result a detailed picture for this sector with the same resolution as that of the original picture. This assignment is designed for you to demonstrate your ability to handle pictures.
　　25.用>,|,&实现一个WORD(2个字节)的高低位交换!!
　　第25题：(w >> | (w 内存来做缓冲,大小自定,但这四个缓冲的大小要一样,并且是连续的!
　　第26题：代码如下：
　　char *p = malloc(4*SIZE_PER_BUF);
　　p1 = p;
　　p2 = p1 + SIZE_PER_BUF;
　　p3 = p2 + SIZE_PER_BUF;
　　p4 = p3 + SIZE_PER_BUF;
　　27.有一浮点型数组A,用C语言写一函数实现对浮点数组A进行降序排序,并输出结果,要求要以数组A作为函数的入口.(建议用冒泡排序法)
　　28.找错：
　　#include
　　#include
　　class Base
　　{
　　private:
　　char * name;
　　public:
　　Base(char * className)
　　{
　　name = new char[strlen(className)];
　　strcpy(name, className);
　　}
　　~Base()
　　{
　　delete name;
　　}
　　char * copyName()
　　{
　　char newname [256];
　　strcpy(newname, name);
　　return newname;
　　}
　　char * getName()
　　{
　　return name;
　　}
　　static void print(Base base)
　　{
　　printf("name: %s\n" , base.name);
　　}
　　};
　　class Subclass : public Base
　　{
　　public:
　　Subclass(char * className) : Base(className)
　　{
　　}
　　};
　　int main()
　　{
　　Base * pBase = new Subclass("test");
　　Base::print(*pBase);
　　printf("name: %s\n", pBase->getName());
　　printf("new name: %s\n", pBase->copyName());
　　return 0;
　　}
　　第28题：Base::Base(char*)构造函数中，new分配的空间比所需的少一个字节，strcpy会导致溢出。
　　Base::copyName()函数中，返回的char*指向局部变量newname，局部变量会在函数返回时释放，导致返回值无效。
　　Base::print(Base)采用传值的方式调用，会引发一个Base的复制构造函数，而Base没有定义复制构造函数，则编译器给出一个缺省的，这个缺省的复制构造函数会导致两个Base对象的成员变量name指向同一块内存；这样其中一个对象析构时，这块共用的内存将被释放，导致另一个对象的name指向一个无效的地址。
　　29.编写一个函数，函数接收一个字符串,是由十六进制数组成的一组字符串,函数的功能是把接到的这组字符串转换成十进制数字.并将十进制数字返回.
　　第29题：使用了C的两个库函数：strtol和sprintf
　　void hex2dec(char const* hex, char *dec)
　　{
　　char *p;
　　sprintf(dec, "%ld", strtol(hex, &p, 16));
　　}
　　30.编写一个函数将一条字符串分成两部分，将前半部分按ASCII码升序排序，后半部分不变，（如果字符串是奇数则中间的字符不变，）最后再将前后两部分交换，然后将该字符串输出，
　　测试字符串“ADZDDJKJFIEJHGI”
　　第30题：用STL：
　　#include
　　#include
　　using namespace std;
　　int main(void)
　　{
　　char str[] = "ADZDDJKJFIEJHGI";
　　int len = sizeof(str) - 1;
　　cout =MAX_SRM)
　　return (NULL_SRM);
　　else
　　return SRM_no;
　　}
　　第32题：程序贴的有问题，可能缺了几行
　　33. 写出程序运行结果
　　int sum(int a)
　　{
　　auto int c=0;
　　static int b=3;
　　c+=1;
　　b+=2;
　　return(a+b+C);
　　}
　　void main()
　　{
　　int I;
　　int a=2;
　　for(I=0;I的内存空间为：_____
　　第36题：在32位字长的系统下，占48字节。a占的空间应该在12个指针的空间，如果每个指针4字节，就是48字节
　　37.编写一个函数，要求输入年月日时分秒，输出该年月日时分秒的下一秒。如输入2004年12月31日23时59分59秒，则输出2005年1月1日0时0分0秒。
　　第37题：用C的库函数，可以偷一下懒：
　　{
　　struct tm stm, *pstm;
　　time_t tmt;
　　cout > stm.tm_year >> stm.tm_mon >> stm.tm_mday >> stm.tm_hour
　　>> stm.tm_min >> stm.tm_sec;
　　stm.tm_year -= 1900;
　　stm.tm_mon --;
　　stm.tm_isdst = 0;
　　tmt = mktime(&stm) + 1;
　　pstm = localtime(&tmt);
　　cout tm_year+1900 tm_mon+1 tm_mday tm_hour tm_min tm_sec >1;
　　if(s>1)IsTwoPow(s);
　　return (s==1)?TRUE:FALSE;//大概是这个意思，但是这一句似乎不该这么返回！
　　}
　　第38题：前面写过的，这题有点意思
　　bool IsTwoPower(int s)
　　{
　　return (s > 0) && ((s & (s-1))==0);
　　}
　　39 A，B从一堆玻璃球（共100个）里向外拿球，规则如下：
　　(1)A先拿，然后一人一次交替着拿；
　　（2）每次只能拿1个或2个或4个；
　　（3）谁拿最后一个球，谁就是最后的失败者；
　　问A，B谁将是失败者？写出你的判断步骤。
　　第39题：A是失败者。当且仅当球数为3n+1时，A是失败者，否则B是。使用归纳法：容易验证球数分别为1，2，3时，失败者分别是A，B，B；当球数为3n+1时，A有三个选择：
　　a) 拿1个球，剩3n个，轮到B拿，根据归纳这时后拿者即A为失败者；
　　b) 拿2个球，剩3n-1个，轮到B拿，根据归纳这时后拿者即A为失败者；
　　c) 拿4个球，剩3(n-1)-1个，轮到B拿，根据归纳这时后拿者即A为失败者；
　　当球数为3n时，A选择拿2个，剩3(n-1)+1个，轮到B拿，根据归纳这时先拿者即B为失败者；当球数为3n-1时，A选择拿1个或4个，剩3(n-1)+1个或3(n-2)+1个，轮到B拿，根据归纳这时先拿者即B为失败者。
　　40.已知：无序数组，折半查找，各元素值唯一。
　　函数原型是：Binary_Seach(int array[], int iValue, int iCount)
　　array是数组，在里面用折半查找的方法找等于iValue的值，找到返回1否则0，iCount是元素个数
　　第40题：使用二分查找的前题是数组已排序，所以要先对数组排序，再进行查找。如果用STL的话，可以写成：
　　sort(array, array+iCount);
　　return binary_search(array, array+iCount, iValue);
　　不过这会修改array里的元素次序，如果不允许修改的话，就需要一个临时数组用于排序和查找。
　　41.统计一个字符串中字符出现的次数
　　第41题：如果用STL的话，很容易：
　　return count(str, str+strlen(str), ch);
　　42.100位以上的超大整数的加法（主要考虑数据结构和加法的实现）。
　　第42题：用一个vector表示一个超大整数，每个元素表示其中4位数字（十进制），从低位到高位存储。实现加法时，将两个vector的每个元素依次相加，如果结果大于9999则向下一个元素进位。
　　43.对如下电文："CASTCASTSATATATASA"给出Huffman编码。
　　第43题：先统计各字母的出现次数：C=2，A=7，S=4，T=5
　　再得出编码：A=0，T=10，C=110，S=111
　　代入原串得到：11001111011001111011101001001001110
　　44.int (* (*f)(int, int))(int)表示什么含义？
　　第44题：定义一个函数指针类型的变量f，f可以指向一个函数，该函数以两个int为参数，并且返回值是这样一种函数指针类型：它指向一个以单个int为参数并返回int值的函数。拆开来写的话，可以写成：
　　typedef int (*T)(int);
　　T (*f)(int, int);
　　45.x=x+1，x+=1，x++，为这三个语句的效率排序。并说明为什么。
　　第45题：从左到右效率递增。如果x是内置类型的话，x++可以被编译为一条高效的机器指令，x+=1也可以编译为一条机器指令但指令里带有操作数1，而x=x+1则要编译多条机器指令，包括取值、运算、存值。如果x是用户定义类型的话，三个语句的效率要视用户对运算符的重载情况而定，但通常用户会首先实现operator++，然后是operator+=，它们两个的效率可能较为接近，最后会用operator+=来实现operator+，它的效率通常会最低。
　　46.中缀表达式 A-(B+C/D)*E的后缀形式是什么？
　　第46题：ABCD/+E*-，或者清楚一些：A((B(CD/)+)E*)-
　　47.struct S1
　　{
　　char c;
　　int i;
　　};
　　sizeof(S1) = ?
　　class X{
　　public:
　　X();
　　virtual ~X();
　　void myMemberFunc();
　　static void myStaticFunc();
　　virtual void myVirtualFunc();
　　private:
　　int i;
　　char * pstr;
　　char a;
　　}
　　sizeof(X) = ?
　　第47题：结果要视机器字长以及编译器对齐开关的设置而定，32位字长机器下缺省设置的结果是：
　　sizeof(S1) = 8 为了对齐i，c占了4字节，i再占4字节
　　sizeof(X) = 16 i占4字节，pstr也占4字节，本为a可以只要1字节，但由于定义了虚拟成员函数，后面要加一个vptr，为了对齐vptr，a占了4字节，最后vptr也是4字节
　　48.找出两个字符串中最大子字符串,如"abractyeyt","dgdsaeactyey"的最大子串为"actyet"
　　第48题：用C++的string类，可以省不少事：
　　#include
　　#include
　　using namespace std;
　　string longestCommonSubstring(string const& s1, string const& s2)
　　{
　　int n = min(s1.length(), s2.length());
　　int len1 = s1.length();
　　string ss;
　　for (int i = n; i > 0; --i)
　　{
　　for (int j = 0; j  j)
　　Method:
　　choose the element in the middle of the sequence as comparison element x
　　let i = 0 and j = n-1
　　while ij
　　search the first element ai which is greater than or equal to x
　　search the last element aj which is less than or equal to x
　　if ij
　　exchange ai and aj
　　let i = i+1 and j = j-1
　　After partitioning the sequence, Quicksort treats the two parts recursively by the same procedure.
　　The recursion ends whenever a part consists of one element only.
　　第50题：典型的习题，没意思，不写了
　　51.写一算法检测单向链表中是否存在环(whether there is a loop in a link list),
　　要求算法复杂度(Algorithm's complexity是O(n)) 并只使用常数空间(space is O(c)).
　　注意，你只知道一个指向单向链表头的指针。链表的长度是不定的，而且环出现的地方也是不定的，环有可能在头，有可能在中间。而且要求是检测, 不能破坏环的结构.
　　第51题：设两个指针，开始时全部指向链表头，然后开始循环，每次循环中一个指针下移一项，另一个指针下移两项，一直循环至以下两个条件之一被满足：
　　如果有一个指针回到了链表头，则该链表无环；
　　如果两个指针相等，则该链表有环。
　　52.设下列函数已经通过了调试
　　bool Sort_Array(ArrayType * Pinputarray, ArrayType * Poutarray);
　　该函数在内存中排序，能把字节数最大为100M字节的ArrayType类型的数组排序。其中ArrayType是一个预定义的数组类型（细节无关紧要），Pinputarray，Poutarray分别为排序前
　　的指针和排序后的指针。
　　请用c语言的伪码风格设计一个算法，他调用上面给出的函数完成下列从输入到输出的任务：
　　输入：排序前的大文件，名称为char * pinoutfilename ，其内容为用分号分隔的ArrayType类型的数组元素，可装满4个100M字节的数组。
　　输出：排序后的大文件char * poutoutfilename。
　　第52题：分四次从输入文件中读数据，每次读100M字节，每次读完后调用Sort_Array将这100M字节的数据排序，并分别输出成四个100M的临时文件；
　　取两个100M临时文件进行合并排序，输出为一个200M的临时文件；
　　同样再将另两个100M临时文件合并为一个200M临时文件；
　　最后将两个200M临时文件合并排序，输出结果文件。
　　53.用最有效率的方法算出2乘以8等於几？
　　第53题：8 << 1
　　54.
　　1.错误的转义字符是 (ｃ )
　　A.'\091' B.'\\'
　　C.'\0' D.'\''
　　2.若数组名作实参而指针变量作形参，函数调用实参传给形参的是 (ｄ )
　　A.数组的长度 B.数组第一个元素的值
　　C.数组所有元素的值 D.数组第一个元素的地址
　　3.变量的指针含意是指变量的 (ｂ )
　　A.值 B.地址
　　C.存储 D.名字
　　5.某文件中定义的静态全局变量(或称静态外部变量)其作用域是 (ｄ )
　　A.只限某个函数 B.本文件
　　C.跨文件 D.不限制作用域
　　第54题：楼主给出的答案有点问题，我认为应该是：
　　D、D、B、B
　　55.
　　1. 解二次方程:a*x*x+b*x+c
　　int Quadratic( double a,double b,double c,double& x1,double& x2);
　　返回值：解的个数
　　2. 最大公约数
　　DWORD Divisor( DWORD dwFirst, DWORD dwSecond );
　　返回值：最大公约数
　　3. 根据蒙特卡洛算法计算圆周率
　　double PI( DOWRD dwCount/*测试次数*/ )；
　　返回值：PI
　　4. 无符号整数乘法，乘数为32bit，结果为64bit
　　提示：32bit整数分解为16bit相乘
　　void Multiply( DWORD dwFirst, DWORD dwSecond, DWORD& dwHigh, DWORD& dwLower );
　　5. 链表排序(从小到大)
　　节点定义为：
　　struct Node{
　　int nValue;
　　struct Node* pNext;
　　};
　　最后一个节点的pNext = NULL.
　　Node* SortChain( Node* pHead );
　　返回值：链表头