- 相關(guān)推薦
C++、數(shù)據(jù)結(jié)構(gòu)筆試題目
1.設(shè)一棵完全二叉樹(shù)有700個(gè)結(jié)點(diǎn)，則在該二叉樹(shù)中有多少個(gè)葉子結(jié)點(diǎn)
如果一棵具有n個(gè)結(jié)點(diǎn)的深度為k的二叉樹(shù)，它的每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中編號(hào)為1~n的結(jié)點(diǎn)一一對(duì)應(yīng)，這棵二叉樹(shù)稱(chēng)為完全二叉樹(shù)。
可以根據(jù)公式進(jìn)行推導(dǎo)，假設(shè)n0是度為0的結(jié)點(diǎn)總數(shù)(即葉子結(jié)點(diǎn)數(shù))，n1是度為1的結(jié)點(diǎn)總數(shù)，n2是度為2的結(jié)點(diǎn)總數(shù)，由二叉樹(shù)的性質(zhì)可知：n0=n2+1，則n= n0+n1+n2(其中n為完全二叉樹(shù)的結(jié)點(diǎn)總數(shù))，由上述公式把n2消去得：n= 2n0+n1-1，由于完全二叉樹(shù)中度為1的結(jié)點(diǎn)數(shù)只有兩種可能0或1，由此得到n0=(n+1)/2或n0=n/2，合并成一個(gè)公式：n0=(n+1) /2 ，就可根據(jù)完全二叉樹(shù)的結(jié)點(diǎn)總數(shù)計(jì)算出葉子結(jié)點(diǎn)數(shù)。
700/2=350個(gè)葉子節(jié)點(diǎn)
2.static 數(shù)據(jù)成員必須在類(lèi)定義的外部定義。不象普通數(shù)據(jù)成員，static成員不是通過(guò)類(lèi)構(gòu)造函數(shù)進(jìn)行初始化，而是應(yīng)該在定義時(shí)進(jìn)行初始化。
靜態(tài)數(shù)據(jù)成員的用途之一是統(tǒng)計(jì)有多少個(gè)對(duì)象實(shí)際存在。
靜態(tài)數(shù)據(jù)成員不能在類(lèi)中初始化，實(shí)際上類(lèi)定義只是在描述對(duì)象的藍(lán)圖，在其中指定初值是不允許的。也
不能在構(gòu)造函數(shù)中初始化該成員，因?yàn)殪o態(tài)數(shù)據(jù)成員為類(lèi)的各個(gè)對(duì)象共享，那么每次創(chuàng)建一個(gè)類(lèi)的對(duì)象則
靜態(tài)數(shù)據(jù)成員都要被重新初始化
#include
class A
{
public:
// A() {i=3;} // 不注釋掉會(huì)出現(xiàn)鏈接錯(cuò)誤
void foo()
{ printf("%d\n",i);
}
private:
static int i; //如果換成static int i=10;出錯(cuò)
};
int A::i=10; //static變量在類(lèi)外定義
void main()
{
A a;
a.foo();
}
3.求函數(shù)返回值，輸入x=9999;
int func ( x )
{
int countx = 0;
while ( x )
{
countx ++;
x = x&(x-1);
}
return countx;
}
結(jié)果呢?
知道了這是統(tǒng)計(jì)9999的二進(jìn)制數(shù)值中有多少個(gè)1的函數(shù)，且有
9999=9×1024+512+256+15
9×1024中含有1的個(gè)數(shù)為2;
512中含有1的個(gè)數(shù)為1;
256中含有1的個(gè)數(shù)為1;
15中含有1的個(gè)數(shù)為4;
故共有1的個(gè)數(shù)為8，結(jié)果為8。
1000 - 1 = 0111，正好是原數(shù)取反。這就是原理。
用這種方法來(lái)求1的個(gè)數(shù)是很效率很高的。
不必去一個(gè)一個(gè)地移位。循環(huán)次數(shù)最少。
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
第一個(gè)struct s1
{
int i: 8;
int j: 4;
int a: 3;
double b;
};
理論上是這樣的，首先是i在相對(duì)0的位置，占8位一個(gè)字節(jié)，然后，j就在相對(duì)一個(gè)字節(jié)的位置，由于一個(gè)位置的字節(jié)數(shù)是4位的倍數(shù)，因此不用對(duì)齊，就放在那里了，然后是a，要在3位的倍數(shù)關(guān)系的位置上，因此要移一位，在15位的位置上放下，目前總共是18位，折算過(guò)來(lái)是2字節(jié)2位的樣子，由于double是8 字節(jié)的，因此要在相對(duì)0要是8個(gè)字節(jié)的位置上放下，因此從18位開(kāi)始到8個(gè)字節(jié)之間的位置被忽略，直接放在8字節(jié)的位置了，因此，總共是16字節(jié)。
1. 一個(gè)位域必須存儲(chǔ)在同一個(gè)字節(jié)中，不能跨兩個(gè)字節(jié)。如一個(gè)字節(jié)所剩空間不夠存放另一位域時(shí)，應(yīng)從下一單元起存放該位域。也可以有意使某位域從下一單元開(kāi)始。例如：
struct bs
{
unsigned a:4
unsigned :0 /*空域*/
unsigned b:4 /*從下一單元開(kāi)始存放*/
unsigned c:4
}
在這個(gè)位域定義中，a占第一字節(jié)的4位，后4位填0表示不使用，b從第二字節(jié)開(kāi)始，占用4位，c占用4位。
2. 由于位域不允許跨兩個(gè)字節(jié)，因此位域的長(zhǎng)度不能大于一個(gè)字節(jié)的長(zhǎng)度，也就是說(shuō)不能超過(guò)8位二進(jìn)位
3. 位域可以無(wú)位域名，這時(shí)它只用來(lái)作填充或調(diào)整位置。無(wú)名的位域是不能使用的。例如：
struct k
{
int a:1
int :2 /*該2位不能使用*/
int b:3
int c:2
};
從以上分析可以看出，位域在本質(zhì)上就是一種結(jié)構(gòu)類(lèi)型， 不過(guò)其成員是按二進(jìn)位分配的。
5.在對(duì)齊為4的情況下 分析下面程序的結(jié)果
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=____;
解答：假設(shè)在32位CPU上，
sizeof(long) = 4 bytes
sizeof(char *) = 4 bytes
sizeof(short int) = sizeof(short) = 2 bytes
sizeof(char) = 1 bytes
由于是4字節(jié)對(duì)齊，
sizeof(struct BBB) = sizeof(*p)
= 4 + 4 + 2 + 1 + 1/*補(bǔ)齊*/ + 2*5 + 2/*補(bǔ)齊*/ = 24 bytes (經(jīng)Dev-C++驗(yàn)證)
p=0x1000000;
p+0x200=____;
= 0x1000000 + 0x200*24 指針加法，加出來(lái)的是指針類(lèi)型的字節(jié)長(zhǎng)度的整倍數(shù)。就是p偏移sizeof(p) *0x200.
(Ulong)p+0x200=____;
= 0x1000000 + 0x200 經(jīng)過(guò)ulong后，這已經(jīng)不再是指針加法，而變成一個(gè)數(shù)值加法了
(char*)p+0x200=____;
= 0x1000000 + 0x200*1 結(jié)果類(lèi)型是char*，這兒的1是char的數(shù)據(jù)類(lèi)型是1字節(jié)
6.分析一下下面程序的輸出結(jié)果
#i nclude
#i nclude
#i nclude
#i nclude
#i nclude
#i nclude
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 <
cout << aa.b2 <
}
答案： -16和1
首先sizeof(AA)的大小為4,b1和b2分別占5bit和2bit.
經(jīng)過(guò)strcpy和memcpy后,aa的4個(gè)字節(jié)所存放的值是:
0,1,2,3的ASC碼，即00110000,00110001,00110010,00110011
所以，最后一步：顯示的是這4個(gè)字節(jié)的前5位，和之后的2位
分別為：10000,和01
因?yàn)閕nt是有正負(fù)之分,所以是-16和1
7.改錯(cuò)：
#i nclude
int main(void) {
int **p;
int arr[100];
p = &arr;
return 0;
}
答案：
int **p; //二級(jí)指針
&arr; //得到的是指向第一維為100的數(shù)組的指針
應(yīng)該這樣寫(xiě)#i nclude
int main(void) {
int **p, *q;
int arr[100];
q = arr;
p = &q;
return 0;
}
8.寫(xiě)一個(gè)內(nèi)存拷貝函數(shù),不用任何庫(kù)函數(shù).
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.將一個(gè)數(shù)字字符串轉(zhuǎn)換為數(shù)字."1234" -->1234
int convert(char* str)
{
int k = 0;
while (*str != '\0')
{
k = k * 10 + (*str++) - '0';
}
return k;
}
10.寫(xiě)出運(yùn)行結(jié)果
#include
#include
#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 = %s\n", var1_p);
printf("var2 = %s\n", var2_p);
return 0;
}
答案：var1 = bbbb
var2 = var1
宏中"#"和"##"的用法
一、一般用法
我們使用#把宏參數(shù)變?yōu)橐粋�(gè)字符串,用##把兩個(gè)宏參數(shù)貼合在一起.
用法:
#include
#include
using namespace std;
#define STR(s) #s
#define CONS(a,b) int(a##e##b)
int main()
{
printf(STR(vck)); // 輸出字符串"vck"
printf("%d\n", CONS(2,3)); // 2e3 輸出:2000
return 0;
}
二、當(dāng)宏參數(shù)是另一個(gè)宏的時(shí)候
需要注意的是凡宏定義里有用'#'或'##'的地方宏參數(shù)是不會(huì)再展開(kāi).
1, 非'#'和'##'的情況
#define TOW (2)
#define MUL(a,b) (a*b)
printf("%d*%d=%d\n", TOW, TOW, MUL(TOW,TOW));
這行的宏會(huì)被展開(kāi)為：
printf("%d*%d=%d\n", (2), (2), ((2)*(2)));
MUL里的參數(shù)TOW會(huì)被展開(kāi)為(2).
2, 當(dāng)有'#'或'##'的時(shí)候
#define A (2)
#define STR(s) #s
#define CONS(a,b) int(a##e##b)
printf("int max: %s\n", STR(INT_MAX)); // INT_MAX #include
這行會(huì)被展開(kāi)為：
printf("int max: %s\n", "INT_MAX");
printf("%s\n", CONS(A, A)); // compile error
這一行則是：
printf("%s\n", int(AeA));
A不會(huì)再被展開(kāi), 然而解決這個(gè)問(wèn)題的方法很簡(jiǎn)單. 加多一層中間轉(zhuǎn)換宏.
加這層宏的用意是把所有宏的參數(shù)在這層里全部展開(kāi), 那么在轉(zhuǎn)換宏里的那一個(gè)宏(_STR)就能得到正確的
宏參數(shù).
#define A (2)
#define _STR(s) #s
#define STR(s) _STR(s) // 轉(zhuǎn)換宏
#define _CONS(a,b) int(a##e##b)
#define CONS(a,b) _CONS(a,b) // 轉(zhuǎn)換宏
printf("int max: %s\n", STR(INT_MAX)); // INT_MAX,int型的最大值，為一個(gè)變量
#include
輸出為: int max: 0x7fffffff
STR(INT_MAX) --> _STR(0x7fffffff) 然后再轉(zhuǎn)換成字符串;
printf("%d\n", CONS(A, A));
輸出為：200
CONS(A, A) --> _CONS((2), (2)) --> int((2)e(2))
11:此題考查的是C的變長(zhǎng)參數(shù),就像標(biāo)準(zhǔn)函數(shù)庫(kù)里printf()那樣.
#include
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
{
i = va_arg( p , int);
for (; i; i &=i-1 )
++k;
}
return k;
}
這段程序的輸出是:
(a) 7
(b) 6
(c) 5
(d) 3
答案: (c)
在C編譯器通常提供了一系列處理可變參數(shù)的宏，以屏蔽不同的硬件平臺(tái)造成的差異，增加程序的可移性。這些宏包括va_start、 va_arg和va_end等。
采用ANSI標(biāo)準(zhǔn)形式時(shí)，參數(shù)個(gè)數(shù)可變的函數(shù)的原型聲明是：
type funcname(type para1, type para2, ...)
這種形式至少需要一個(gè)普通的形式參數(shù)，后面的省略號(hào)不表示省略，而是函數(shù)原型的一部分。type是函數(shù)返回值和形式參數(shù)的類(lèi)型。
不同的編譯器，對(duì)這個(gè)可變長(zhǎng)參數(shù)的實(shí)現(xiàn)不一樣 ，gcc4.x中是內(nèi)置函數(shù).
關(guān)于可變長(zhǎng)參數(shù),可參閱
http://www.upsdn.net/html/2004-11/26.html
http://www.upsdn.net/html/2004-11/24.html
程序分析
va_list p; /*定義一個(gè)變量 ,保存函數(shù)參數(shù)列表 的指針*/
va_start( p , n); /*用va_start宏初始化變量p, va_start宏的第2個(gè)參數(shù)n, 是一個(gè)固定的參數(shù),
必須是我們自己定義的變長(zhǎng)函數(shù)的最后一個(gè)入棧的參數(shù)也就是調(diào)用的時(shí)候參數(shù)列表里的第1個(gè)參數(shù)*/
for (; j
{ i = va_arg( p , int); /*va_arg取出當(dāng)前的參數(shù), 并認(rèn)為取出的參數(shù)是一個(gè)整數(shù)(int)*/
for (; i; i &=i-1 ) /*判斷取出的i是否為0*/
++k; /* 如果i不為0, k自加, i與i-1進(jìn)行與邏輯運(yùn)算, 直到i 為0
這是一個(gè)技巧，下面會(huì)談到它的功能*/}
當(dāng)我們調(diào)用ripple函數(shù)時(shí)，傳遞給ripple函數(shù)的 參數(shù)列表的第一個(gè)參數(shù)n的值是3 .
va_start 初始化 p指向第一個(gè)未命名的參數(shù)(n是有名字的參數(shù)) ,也就是 is 5 (第一個(gè)).
每次對(duì) va_arg的調(diào)用，都將返回一個(gè)參數(shù)，并且把 p 指向下一個(gè)參數(shù).
va_arg 用一個(gè)類(lèi)型名來(lái)決定返回的參數(shù)是何種類(lèi)型,以及在 var_arg的內(nèi)部實(shí)現(xiàn)中決定移動(dòng)多大的距離才
到達(dá)下一個(gè) 參數(shù)
(; i; i&=i-1) k++ /* 計(jì)算i有多少bit被置1 */
5用二進(jìn)制表示是 (101) 2
7用二進(jìn)制表示 (111) 3
所以 k 返回 5(2+3),也即本題應(yīng)該選c
因?yàn)閕與i-1的最右邊的那位(最低位) 肯定是不同，如果i1,i-1肯定是0，反之亦然. i & i-1 這個(gè)運(yùn)算，在二相補(bǔ)的數(shù)字系統(tǒng)中，將會(huì)消除最右邊的1位
12.要對(duì)絕對(duì)地址0x100000賦值，我們可以用(unsigned int*)0x100000 = 1234;
那么要是想讓程序跳轉(zhuǎn)到絕對(duì)地址是0x100000去執(zhí)行，應(yīng)該怎么做?
答案：*((void (*)( ))0x100000 ) ( );
首先要將0x100000強(qiáng)制轉(zhuǎn)換成函數(shù)指針,即:
(void (*)())0x100000
然后再調(diào)用它:
*((void (*)())0x100000)();
用typedef可以看得更直觀些:
typedef void(*)() voidFuncPtr;
*((voidFuncPtr)0x100000)();
13.7.C++中為什么用模板類(lèi)。
答：(1)可用來(lái)創(chuàng)建動(dòng)態(tài)增長(zhǎng)和減小的數(shù)據(jù)結(jié)構(gòu)
(2)它是類(lèi)型無(wú)關(guān)的，因此具有很高的可復(fù)用性。
(3)它在編譯時(shí)而不是運(yùn)行時(shí)檢查數(shù)據(jù)類(lèi)型，保證了類(lèi)型安全
(4)它是平臺(tái)無(wú)關(guān)的，可移植性
(5)可用于基本數(shù)據(jù)類(lèi)型
【C++、數(shù)據(jù)結(jié)構(gòu)筆試題目】相關(guān)文章：
C++工程師筆試題目11-25
C++筆試題03-25
C++ 筆試題08-09
c++一些筆試題目和整理的答案08-09
Sony C++筆試題02-11
普天C++筆試題02-18
筆試題目11-06
聚網(wǎng)科技C++筆試題07-20
普天C++筆試題面試技巧11-06
微軟筆試題目03-16