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
class A
{
public:
// A() {i=3;} // 不注釋掉會出現鏈接錯誤
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.求函數返回值，輸入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)= %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位一個字節，然后，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
#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.
經過strcpy和memcpy后,aa的4個字節所存放的值是:
0,1,2,3的ASC碼，即00110000,00110001,00110010,00110011
所以，最后一步：顯示的是這4個字節的前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的數組的指針
應該這樣寫#i nclude
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 != '\0')
{
k = k * 10 + (*str++) - '0';
}
return k;
}
10.寫出運行結果
#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
宏中"#"和"##"的用法
一、一般用法
我們使用#把宏參數變為一個字符串,用##把兩個宏參數貼合在一起.
用法:
#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;
}
二、當宏參數是另一個宏的時候
需要注意的是凡宏定義里有用'#'或'##'的地方宏參數是不會再展開.
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里的參數TOW會被展開為(2).
2, 當有'#'或'##'的時候
#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不會再被展開, 然而解決這個問題的方法很簡單. 加多一層中間轉換宏.
加這層宏的用意是把所有宏的參數在這層里全部展開, 那么在轉換宏里的那一個宏(_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型的最大值，為一個變量
#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的變長參數,就像標準函數庫里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標準形式時，參數個數可變的函數的原型聲明是：
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
{ 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)可用于基本數據類型
【C++、數據結構筆試題目】相關文章：
C++工程師筆試題目11-25
C++筆試題03-25
C++ 筆試題08-09
c++一些筆試題目和整理的答案08-09
Sony C++筆試題02-11
普天C++筆試題02-18
筆試題目11-06
聚網科技C++筆試題07-20
普天C++筆試題面試技巧11-06
微軟筆試題目03-16