c、数据结构笔试题目　

《c、数据结构笔试题目　》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、C++、数据结构笔试题目1.设一棵完全二叉树有700个结点，则在该二叉树中有多少个叶子结点如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为的结点一一对应，这棵二叉树称为完全二叉树。可以根据公式进行推导，假设n0是度为0的结点总(即叶子结点数)，nl是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0=n2+l，则n=n0+nl+n2(其中n为完全二叉树的结点总由上述公式把n2消去得：n=2n0+n1-1,由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0=(n+l)/2或n0=n/2

2、，合并成一个公式：n0=(n+l)/2，就可根据完全二叉树的结点总数计算出叶子结点数。700/2=350个叶子节点数据成员必须在类定义的外部定义。不象普通数据成员，static成员不是通过类构造函数进行初始化，而是应该在定义时进行初始化。静态数据成员的用途之一是统计有多少个对象实际存静态数据成员不能在类中初始化，实际上类定义只是在描述对象的蓝图，在其中指定初值是不允许的。也不能在构造函数中初始化该成员，因为静态数据成员为类的各个对象共享，那么每次创建一个类的对象则静态数据成员都要被重新初始化^includeclassA{public://A(){

3、i=3;}//不注释掉会出现链接错误voidfoo(){printf("%d"，i);private:staticinti://如果换成staticinti=10;出错};intA::i=l0;//static变量在类外定义voidmain(){Aa;0;}3.求函数返回值，输入x=9999;intfuncintcountx=0;while(x)countx++;x=x(x-1);}returncountx;}结果呢？知道了这是统计9999的二进制数值中有多少个1的函数，且有9999=9X1024+512+256+159X1024中含有1的个

4、数为2;512中含有1的个数为1;256中含有1的个数为1;15中含有1的个数为4;故共有1的个数为8,结果为8。10⑻-1=0111，正好是原数取反。这就是原理。用这种方法来求1的个数是很效率很高的。不必去一个一个地移位。循环次数最少。3.分析下面的程序structslinti:8;intj:4;inta:3;doubleb;};structs2{inti:8;intj:4;doubleb;inta:3;};printf(〃sizeof(sl)=%d〃，sizeof(si));printf(〃sizeof(s2)=%d〃，sizeof(

5、s2));result:16,24第一个structsl{inti:8;intj:4;inta:3;doubleb:理论上是这样的，首先是i在相对0的位置，占8位一个字节，然后，j就在相对一个字节的位置，由于一个位置的字节数是4位的倍数，因此不用对齐，就放在那里了，然后是a，要在3位的倍数关系的位置上，因此要移一位，在15位的位置上放下，目前总共是18位，折算过来是2字节2位的样子，由于double是8字节的，因此要在相对0要是8个字节的位置上放下，因此从18位开始到8个字节之间的位置被忽略，直接放在8字节的位置了，因此，总共是16字节。1.一个

6、位域必须存储在同一个字节中，不能跨两个字节。如一个字节所剩空间不够存放另一位域时，应从下一单元起存放该位域。也可以有意使某位域从下一单元开始例如：structbsunsigneda:4unsigned:0/*空域*/unsignedb:4/*从下一单元开始存放*/unsignedc:4在这个位域定义中，a占第一字节的4位，后4位填0表示不使用，b从第二字节开始，占用4位，c占用4位。1.由于位域不允许跨两个字节，因此位域的长度不能大于一个字节的长度，也就是说不能超过8位二进位2.位域可以无位域名，这时它只用来作填充或调整位置。无名的位域是不能使用

7、的。例如：structk{inta:1int:2/*该2位不能使用*/intb:3intc:2};从以上分析可以看出，位域在本质上就是一种结构类型，不过其成员是按二进位分配的。3.在对齐为4的情况下分析下面程序的结果structBBB{Iongnum;char*name:shortintdata;charha;shortba[5]:}*P;p=OxlO00000;p+Ox200=:(U1ong)p+0x200=:(char*)p+0x200=;解答：假设在32位CPU上，sizeof(long)=4bytessizeof(char氺)=4byte

8、ssizeof(shortint)=sizeof(short)=2bytessizeof(char)=1bytes由于是4字节对齐，si