IT公司面试题总结(五).doc

1.设一棵完全二叉树有700个结点，则在该二叉树中有多少个叶子结点如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1n的结点一一对应，这棵二叉树称为完全二叉树。可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0n21，则n= n0n1n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n= 2n0+n11，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0（n1）/2或n0n/2，合并成一个公式：n0（n1） /2 ，就可根据完全二叉树的结点总数计算出叶子结点数。700/2=350个叶子节点2.static 数据成员必须在类定义的外部定义。不象普通数据成员，static成员不是通过类构造函数进行初始化，而是应该在定义时进行初始化。静态数据成员的用途之一是统计有多少个对象实际存在。静态数据成员不能在类中初始化，实际上类定义只是在描述对象的蓝图，在其中指定初值是不允许的。也不能在构造函数中初始化该成员，因为静态数据成员为类的各个对象共享，那么每次创建一个类的对象则静态数据成员都要被重新初始化#include class Apublic:/ A() i=3; / 不注释掉会出现链接错误void foo() printf(%dn,i);private:static int i; /如果换成static int i=10;出错;int A:i=10; /static变量在类外定义void main()A a;a.foo();3.求函数返回值，输入x=9999;int func （ x ）int countx = 0;while ( x )countx +;x = x&(x-1);return countx;结果呢？知道了这是统计9999的二进制数值中有多少个1的函数，且有9999910245122561591024中含有1的个数为2；512中含有1的个数为1；256中含有1的个数为1；15中含有1的个数为4；故共有1的个数为8，结果为8。1000 - 1 = 0111，正好是原数取反。这就是原理。用这种方法来求1的个数是很效率很高的。不必去一个一个地移位。循环次数最少。4.分析下面的程序struct s1int i: 8;int j: 4;int a: 3;double b;struct s2int i: 8;int j: 4;double b;int a:3;printf(sizeof(s1)= %dn, sizeof(s1);printf(sizeof(s2)= %dn, sizeof(s2);result: 16, 24第一个struct s1int i: 8;int j: 4;int a: 3;double b;理论上是这样的，首先是i在相对0的位置，占8位一个字节，然后，j就在相对一个字节的位置，由于一个位置的字节数是4位的倍数，因此不用对齐，就放在那里了，然后是a，要在3位的倍数关系的位置上，因此要移一位，在15位的位置上放下，目前总共是18位，折算过来是2字节2位的样子，由于double是8 字节的，因此要在相对0要是8个字节的位置上放下，因此从18位开始到8个字节之间的位置被忽略，直接放在8字节的位置了，因此，总共是16字节。1. 一个位域必须存储在同一个字节中，不能跨两个字节。如一个字节所剩空间不够存放另一位域时，应从下一单元起存放该位域。也可以有意使某位域从下一单元开始。例如： struct bsunsigned a:4unsigned :0 /*空域*/unsigned b:4 /*从下一单元开始存放*/unsigned c:4在这个位域定义中，a占第一字节的4位，后4位填0表示不使用，b从第二字节开始，占用4位，c占用4位。2. 由于位域不允许跨两个字节，因此位域的长度不能大于一个字节的长度，也就是说不能超过8位二进位3. 位域可以无位域名，这时它只用来作填充或调整位置。无名的位域是不能使用的。例如：struct kint a:1int :2 /*该2位不能使用*/int b:3int c:2;从以上分析可以看出，位域在本质上就是一种结构类型， 不过其成员是按二进位分配的。5.在对齐为4的情况下 分析下面程序的结果struct BBBlong num；char *name;short int data;char ha;short ba5;*p;p=0x1000000;p+0x200=_;(Ulong)p+0x200=_;(char*)p+0x200=_;解答：假设在32位CPU上，sizeof(long) = 4 bytessizeof(char *) = 4 bytessizeof(short int) = sizeof(short) = 2 bytessizeof(char) = 1 bytes由于是4字节对齐，sizeof(struct BBB) = sizeof(*p)= 4 + 4 + 2 + 1 + 1/*补齐*/ + 2*5 + 2/*补齐*/ = 24 bytes (经Dev-C+验证)p=0x1000000;p+0x200=_;= 0x1000000 + 0x200*24 指针加法，加出来的是指针类型的字节长度的整倍数。就是p偏移sizeof(p) *0x200.(Ulong)p+0x200=_;= 0x1000000 + 0x200 经过ulong后，这已经不再是指针加法，而变成一个数值加法了(char*)p+0x200=_;= 0x1000000 + 0x200*1结果类型是char*，这儿的1是char的数据类型是1字节6.分析一下下面程序的输出结果i ncludei nclude i nclude i nclude i nclude i nclude typedef struct AA int b1:5; int b2:2;AA;void main() AA aa; char cc100; strcpy(cc,0123456789abcdefghijklmnopqrstuvwxyz); memcpy(&aa,cc,sizeof(AA); cout aa.b1 endl; cout aa.b2 endl;答案： -16和首先sizeof(AA)的大小为4,b1和b2分别占5bit和2bit.经过strcpy和memcpy后,aa的4个字节所存放的值是:0,1,2,3的ASC码，即00110000,00110001,00110010,00110011所以，最后一步：显示的是这个字节的前位，和之后的位分别为：10000,和01因为int是有正负之分,所以是-16和17.改错：i nclude int main(void) int *p; int arr100; p = &arr; return 0;答案：int *p; /二级指针&arr; /得到的是指向第一维为100的数组的指针应该这样写i nclude int main(void) int *p, *q;int arr100;q = arr;p = &q;return 0;8.写一个内存拷贝函数,不用任何库函数.void* memcpy(void* pvTo, const void* pvFrom, size_t size) assert(pvTo != NULL) & (pvFrom != NULL); byte* pbTo = pvTo; byte* pbFrom = pbFrom; while (size- 0) *pbTo+ = *pbFrom+; return pvTo;9.将一个数字字符串转换为数字.1234 -1234int convert(char* str) int k = 0; while (*str != 0) k = k * 10 + (*str+) - 0; return k;10.写出运行结果#include #include #define STRCPY(a, b) strcpy(a#_p, #b)#define STRCPY1(a, b) strcpy(a#_p, b#_p)int main(void) char var1_p20; char var2_p30; strcpy(var1_p, aaaa); strcpy(var2_p, bbbb); STRCPY1(var1, var2); STRCPY(var2, var1); printf(var1 = %sn, var1_p); printf(var2 = %sn, var2_p); return 0;答案：var1 = bbbbvar2 = var1宏中#和#的用法一、一般用法我们使用#把宏参数变为一个字符串,用#把两个宏参数贴合在一起.用法:#include#includeusing namespace std;#define STR(s) #s#define CONS(a,b) int(a#e#b)int main()printf(STR(vck); / 输出字符串vckprintf(%dn, CONS(2,3); / 2e3 输出:2000return 0;二、当宏参数是另一个宏的时候需要注意的是凡宏定义里有用#或#的地方宏参数是不会再展开.1, 非#和#的情况#define TOW (2)#define MUL(a,b) (a*b)printf(%d*%d=%dn, TOW, TOW, MUL(TOW,TOW);这行的宏会被展开为：printf(%d*%d=%dn, (2), (2), (2)*(2);MUL里的参数TOW会被展开为(2).2, 当有#或#的时候#define A (2)#define STR(s) #s#define CONS(a,b) int(a#e#b)printf(int max: %sn, STR(INT_MAX); / INT_MAX #include这行会被展开为：printf(int max: %sn, INT_MAX);printf(%sn, CONS(A, A); / compile error这一行则是：printf(%sn, int(AeA);A不会再被展开, 然而解决这个问题的方法很简单. 加多一层中间转换宏.加这层宏的用意是把所有宏的参数在这层里全部展开, 那么在转换宏里的那一个宏(_STR)就能得到正确的宏参数.#define A (2)#define _STR(s) #s#define STR(s) _STR(s) / 转换宏#define _CONS(a,b) int(a#e#b)#define CONS(a,b) _CONS(a,b) / 转换宏printf(int max: %sn, STR(INT_MAX); / INT_MAX,int型的最大值，为一个变量#include输出为: int max: 0x7fffffffSTR(INT_MAX) - _STR(0x7fffffff) 然后再转换成字符串；printf(%dn, CONS(A, A);输出为：200CONS(A, A) - _CONS(2), (2) - int(2)e(2)11:此题考查的是C的变长参数,就像标准函数库里printf()那样.#includeint ripple ( int , .);main() int num; num = ripple ( 3, 5,7); printf( %d , num);int ripple (int n, .) int i , j; int k; va_list p; k= 0; j = 1; va_start( p , n); for (; jn; +j) i = va_arg( p , int); for (; i; i &=i-1 ) +k; return k;这段程序的输出是:(a) 7(b) 6(c) 5(d) 3答案: (c)在C编译器通常提供了一系列处理可变参数的宏，以屏蔽不同的硬件平台造成的差异，增加程序的可移性。这些宏包括va_start、 va_arg和va_end等。采用ANSI标准形式时，参数个数可变的函数的原型声明是：type funcname(type para1, type para2, .)这种形式至少需要一个普通的形式参数，后面的省略号不表示省略，而是函数原型的一部分。type是函数返回值和形式参数的类型。不同的编译器，对这个可变长参数的实现不一样 ，gcc4.x中是内置函数.关于可变长参数,可参阅/html/2004-11/26.html/html/2004-11/24.html程序分析va_list p;/*定义一个变量 ,保存函数参数列表 的指针*/va_start( p , n); /*用va_start宏初始化变量p,va_start宏的第2个参数n, 是一个固定的参数,必须是我们自己定义的变长函数的最后一个入栈的参数也就是调用的时候参数列表里的第1个参数*/for (; jn; +j) /* j从1开始, 遍历所有可变参数 */ i = va_arg( p , int); /*va_arg取出当前的参数,并认为取出的参数是一个整数(int)*/for (; i; i &=i-1 ) /*判断取出的i是否为0*/ +k; /* 如果i不为0, k自加, i与i-1进行与逻辑运算, 直到i 为0这是一个技巧，下面会谈到它的功能*/当我们调用ripple函数时，传递给ripple函数的 参数列表的第一个参数n的值是3 .va_start 初始化 p指向第一个未命名的参数(n是有名字的参数) ,也就是 is 5 (第一个).每次对 va_arg