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