C++、数据结构笔试题目
1.设一棵完全二叉树有700个结点，则在该二叉树中有多少个叶子结点
如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，这棵二叉树称为完全二叉树。
可以根据公式进行推导，假设n0是度为0的结点总数(即叶子结点数)，n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0=n2+1，则n= n0+n1+n2(其中n为完全二叉树的结点总数)，由上述公式把n2消去得：n= 2n0+n1-1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0=(n+1)/2或n0=n/2，合并成一个公式：n0=(n+1) /2 ，就可根据完全二叉树的结点总数计算出叶子结点数。
700/2=350个叶子节点
2.static 数据成员必须在类定义的外部定义。不象普通数据成员，static成员不是通过类构造函数进行初始化，而是应该在定义时进行初始化。
静态数据成员的用途之一是统计有多少个对象实际存在。
静态数据成员不能在类中初始化，实际上类定义只是在描述对象的蓝图，在其中指定初值是不允许的。也
不能在构造函数中初始化该成员，因为静态数据成员为类的各个对象共享，那么每次创建一个类的对象则
静态数据成员都要被重新初始化
#include
class A
{
public:
// A() {i=3;} // 不注释掉会出现链接错误
void foo()
{ printf("%d\n",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的函数，且有
9999=9×1024+512+256+15
9×1024中含有1的个数为2;
512中含有1的个数为1;
256中含有1的个数为1;
15中含有1的个数为4;
故共有1的个数为8，结果为8。
1000 - 1 = 0111，正好是原数取反。这就是原理。
用这种方法来求1的个数是很效率很高的。
不必去一个一个地移位。循环次数最少。
4.分析下面的程序
struct s1
{
int i: 8;
int j: 4;
int a: 3;
double b;
};
struct s2
{
int i: 8;
int j: 4;
double b;
int a:3;
};
printf("sizeof(s1)= %d\n", sizeof(s1));
printf("sizeof(s2)= %d\n", sizeof(s2));
result: 16, 24
第一个struct s1
{
int 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 bs
{
unsigned a:4
unsigned :0 /*空域*/
unsigned b:4 /*从下一单元开始存放*/
unsigned c:4
}
在这个位域定义中，a占第一字节的4位，后4位填0表示不使用，b从第二字节开始，占用4位，c占用4位。
2. 由于位域不允许跨两个字节，因此位域的长度不能大于一个字节的长度，也就是说不能超过8位二进位
3. 位域可以无位域名，这时它只用来作填充或调整位置。无名的位域是不能使用的。例如：
struct k
{
int a:1
int :2 /*该2位不能使用*/
int b:3
int c:2
};
从以上分析可以看出，位域在本质上就是一种结构类型， 不过其成员是按二进位分配的。
5.在对齐为4的情况下 分析下面程序的结果
struct BBB
{
long num;
char *name;
short int data;
char ha;
short ba[5];
}*p;
p=0x1000000;
p+0x200=____;
(Ulong)p+0x200=____;
(char*)p+0x200=____;
解答：假设在32位CPU上，
sizeof(long) = 4 bytes
sizeof(char *) = 4 bytes
sizeof(short int) = sizeof(short) = 2 bytes
sizeof(char) = 1 bytes
由于是4字节对齐，
sizeof(struct BBB) = sizeof(*p)
= 4 + 4 + 2 + 1 + 1/*补齐*/ + 2*5 + 2/*补齐*/ = 24 bytes (经Dev-C++验证)