C_C++笔试题附答案

C_C++笔试题附答案

选择题，每道题目只有一个正确答案（每题5分）1、已知F(0)=1,F(1)=1,F(n+1)=F(n)+F(n-1)，F(2011)%5=()A.0B.1C.2D.3E.42、以下排序算法平均时间复杂度最高(也就是最耗时，最慢)的是（）A.归并B.快速排序C.冒泡D.堆排3、计算最小生成树的克鲁斯卡尔算法，其本质是()A.贪心算法B.动态规划算法C.分治算法D.回溯算法4、以下概念与进程间通讯无关的是()A.信号(signal)B.管道C.共享内存D.运行时识别5、现有以下代码，编译不通过，应该修改的是： structTest { Test(int){} Test(){} voidfun(){} }; intmain() { Testa(1）;//语句1 a.fun();//语句2 Testb();//语句3 b.fun();//语句4 return0; } A.语句1B.语句2C.语句3D.语句4填空题（每空5份）1、一个空瓶子可以装n千克的水，现在一共有m千克的水，m和n都是正整数。需要p个瓶子才可以全部装下。请用一个语句，使用m和n来计算p=__________2、unsignedlongval;chara=0x96;charb=0x81;val=b<<8|a;问val=___？3、在C++中，构造函数______为虚函数，析构函数_______为虚函数。在Java中，对象的析构由Java虚拟机负责，所以不存在这个问题。（空白处填“可以”或者“不可以”）4、union{inta;chars[4096];}stack;nsizeof(stack)的结果是_________简答题（20分）1、一个参数既可以是const还可以是volatile吗？解释为什么。2、选择不同语言的同学请注意审题。选择C的同学请回答这个问题请举例说明’#’和’##’用于定义宏（macro）时，各有什么作用。（红旗公司某年笔试题）选择C++，Java的同学请回答这个问题（2006年某通讯产品公司笔试题）请设计一个单例类（singleton）编程题，任选一题作答即可，可以使用C/C++/Java中的任何一种（20分）1、（GameTheory）Stan和Ollie做乘法游戏，将一个数p乘以2到9之间一个整数。一开始p总是等于1。在游戏开始之前，指定一个很大的整数n（在32位整形的表示范围内），谁最先得到p>=n者获胜。假如总是Stan先开始游戏。请写一个程序，其输入为n，如果Stan获胜，则输出为“Stanwins”，否则输出“Olliewins”。（改自Nim游戏）2、（组合数学和算法设计）请使用回溯算法打印出”ABCDEFG”这七个字母的全排列。（某数据库公司2008年笔试题）3、（算法设计）最大子段和问题，输入一个长度为n的整数序列（A1,A2,……,An），从中找出一段连续的子序列，使得这个序列的和最大。请设计一个时间复杂度为O(n)的算法。智力题，任选一题做答即可（10分）1、U2合唱团在17分钟内得赶到演唱会场,途中必需跨过一座桥,四个人从桥的同一端出发,你得帮助他们到达另一端,天色很暗,而他们只有一只手电筒。一次同时最多可以有两人一起过桥,而过桥的时候必须持有手电筒,所以就得有人把手电筒带来带去,来回桥两端。手电筒是不能用丢的方式来传递的。四个人的步行速度各不同,若两人同行则以较慢者的速度为准。BONO需花1分钟过桥,EDGE需花2分钟过桥,ADAM需花5分钟过桥,LARRY需花10分钟过桥,他们要如何在17分钟内过桥呢?（微软研究院面试题）2、每个飞机只有一个油箱，飞机之间可以相互加油(注意是相互,没有加油机)，一箱油可供一架飞机绕地球飞半圈，问题:为使至少一架飞机绕地球一圈回到起飞时的飞机场，至少需要出动几架飞机？(所有飞机从同一机场起飞,而且必须安全返回机场，不允许中途降落，中间没有飞机场)选择题：1.D；找规律，20次一个循环。2.C3.A4.D5.C填空题：1、p=(m+n–1)/n;或者p=(m%n==0)?m/n:m/n+1;n2、0xffffff96;提示：（1）注意运算的优先级。（2）注意使用char类型做为右值时符号位的奇怪行为。本题回答0x96也算对。3、不可以；可以4、4096。注意union的内存分布。简答题：1、可以，用const和volatile同时修饰变量，表示这个变量在程序内部是只读的，不能改变的，只在程序外部条件变化下改变，并且编译器不会优化这个变量。每次使用这个变量时，都要小心地去内存读取这个变量的值，而不是去寄存器读取它的备份。2、C语言部分。#的作用在于将宏参数进行字符化处理。##用于连接两个参数。面向对象语言部分。设计模式的内容。要点在于私有构造函数和静态成员函数。例如：classSingleton{private:staticSingleton*pInstance;Singleton(){pInstance=NULL;}public:staticSingleton*getInstance(){if(!pInstance)pInstance=newSingleton();returnpInstance;};};编程题：1、可能题意没有说明白，导致大家在答题时做出了各种理解。这一个博弈的游戏。Stan和Ollie都足够聪明，他们可以任意选择2~9之间的某一个数进行游戏。所以，这个游戏是存在必胜策略的。所有博弈论的题目，都有一个基本的分析方法：必胜状态和必败状态。所有可以到达必败状态的状态，都是必胜状态；只能到达必胜状态的，都是必败状态。所以，可以看到当2<=n<=9时，Stan可以任选一个数，立即获胜。而如果10<=n<=18时，无论Stan采用什么策略，都是必败的。所以这个规律就是2~9时Stan必胜；10~18时，Stan必败；19~18*9时，Stan必胜……依次类推。规律就是乘2乘9。2、这个递归函数可以使用伪码写这样子：chars[10]="ABCDEFG";intused[10];//用于记录当前字母是否已经使用过chartemp[10];//用于存储临时结果nvoidmake(intn){if(n==7)打印结果else{for(inti=0;i<7;i++){if(该字母未使用){标记为已使用;将其放入临时结果的第n位;make(n+1);将已使用标志复位;}}}}1、最大子段和问题，是经典的动态规划问题。伪码表示如下：for(inti=0;i_max)_max=tempSum;}这样就可以得到最大子段和，但是题目还要求找出相应的连续子序列，因此还需要使用额外的变量来记录子序列的开始和结束。智力题：1、尽量让时间差不多的人一起走。答案是1（这里用过桥所用时间来代指题目中的人物）与2过桥，1回来，5与10过桥，2回来，1与2一起过桥。正好17分钟。2、假设3架飞机分别为A、B、C，同时起飞，飞行至1/8处，其中一架(A)分油后，安全返航；剩余两架(BC)飞行到1/4处时，其中一架(B)分油后，安全返航；A降落后加完油，在B返回后马上起飞，逆向接应C；同样B降落后加完油，也立即逆向起飞，接应AC；AC在逆向1/4处相遇，分油后，同飞行；3架(ABC)飞机在逆向1/8处相遇，分油后继续飞行，这样就可以完成任务了。所以，3架飞机飞5次就可以完成任务。