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 <stdio.h>
class A
{
public:
//    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的函数，且有
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)= %dn", sizeof(s1));
printf("sizeof(s2)= %dn", 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++验证)

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 nclude<iostream.h>
＃i nclude <string.h>
＃i nclude <malloc.h>
＃i nclude <stdio.h>
＃i nclude <stdlib.h>
＃i nclude <memory.h>
typedef struct AA
{
         int b1:5;
         int b2:2;
}AA;
void main()
{
        AA aa;
        char cc[100];
        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和1

7.改错：

＃i nclude <stdio.h>
int main(void) {
     int **p;
     int arr[100];
     p = &arr;
     return 0;
}
答案：
int **p; //二级指针
&arr; //得到的是指向第一维为100的数组的指针
应该这样写＃i nclude <stdio.h>
int main(void) {
int **p, *q;
int arr[100];
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" -->1234

int convert(char* str)
{
   int k = 0;
   while (*str != '')
   {
      k = k * 10 + (*str++) - '0';
   }
   return k;
}

10.写出运行结果

#include <stdio.h>
#include <string.h>

#define STRCPY(a, b) strcpy(a##_p, #b)
#define STRCPY1(a, b) strcpy(a##_p, b##_p)

int main(void) {
        char var1_p[20];
        char var2_p[30];

        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 = bbbb
var2 = var1
宏中"#"和"##"的用法

一、一般用法

我们使用#把宏参数变为一个字符串,用##把两个宏参数贴合在一起.
用法:
#include<cstdio>
#include<climits>
using namespace std;
#define STR(s) #s
#define CONS(a,b) int(a##e##b)
int main()
{
printf(STR(vck)); // 输出字符串"vck"
printf("%dn", CONS(2,3)); // 2e3 输出:2000
return 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<climits>
这行会被展开为：
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<climits>
输出为: int max: 0x7fffffff

STR(INT_MAX) --> _STR(0x7fffffff) 然后再转换成字符串；
printf("%dn", CONS(A, A));
输出为：200
CONS(A, A) --> _CONS((2), (2)) --> int((2)e(2))

11:此题考查的是C的变长参数,就像标准函数库里printf()那样.

#include<stdarg.h>
int 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 (; j<n; ++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中是内置函数.
关于可变长参数,可参阅

http://www.upsdn.net/html/2004-11/26.html
http://www.upsdn.net/html/2004-11/24.html

程序分析
va_list p;  /*定义一个变量 ,保存函数参数列表 的指针*/
va_start( p , n);     /*用va_start宏初始化变量p,  va_start宏的第2个参数n, 是一个固定的参数,

必须是我们自己定义的变长函数的最后一个入栈的参数也就是调用的时候参数列表里的第1个参数*/
for (; j<n; ++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的调用，都将返回一个参数，并且把 p 指向下一个参数.
va_arg 用一个类型名来决定返回的参数是何种类型,以及在 var_arg的内部实现中决定移动多大的距离才

到达下一个 参数
(; i; i&=i-1) k++        /* 计算i有多少bit被置1 */
5用二进制表示是 (101) 2
7用二进制表示 (111) 3
所以 k 返回 5(2+3),也即本题应该选c

   因为i与i-1的最右边的那位(最低位) 肯定是不同，如果i1,i-1肯定是0，反之亦然.  i & i-1 这个运算，在二相补的数字系统中，将会消除最右边的1位

12.要对绝对地址0x100000赋值，我们可以用(unsigned int*)0x100000 = 1234;
   那么要是想让程序跳转到绝对地址是0x100000去执行，应该怎么做？

　　答案：*((void (*)( ))0x100000 ) ( );
　　首先要将0x100000强制转换成函数指针,即:
　　(void (*)())0x100000
　　然后再调用它:
　　*((void (*)())0x100000)();
　　用typedef可以看得更直观些:
　　typedef void(*)() voidFuncPtr;
　　*((voidFuncPtr)0x100000)();

13.7.C++中为什么用模板类。
答：(1)可用来创建动态增长和减小的数据结构
（2）它是类型无关的，因此具有很高的可复用性。
（3）它在编译时而不是运行时检查数据类型，保证了类型安全
（4）它是平台无关的，可移植性
（5）可用于基本数据类型