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