一、填空題(5分每題，一共8題)

　　1、兩個(gè)人A(速度為a)、B(速度為b)在一直路上相向而行。在A、B距離為s的時(shí)候，A放出一個(gè)鴿子C(速度為c)，C飛到B后，立即掉頭飛向A，遇到A在掉頭飛向B......就這樣在AB之間飛來(lái)飛去，直到A、B相遇，這期間鴿子共飛行路程為?

　　答案是：s*c/(a+b)

　　2、(he)的平方=she。h、e、s代表的數(shù)字?

　　答案是：分別代表2、5、6

　　3、運(yùn)算(93&-8)的結(jié)果為：88

　　4、將一個(gè)無(wú)序整數(shù)數(shù)組構(gòu)造成一個(gè)最大堆，最差時(shí)間復(fù)雜度為：

　　5、int *p = &n;

　　那么*p的值是()

　　A、p的值 B、p的地址 C、n的值 D、n的地址

　　6、一個(gè)完全二叉樹(shù)有770個(gè)節(jié)點(diǎn)，那么其葉子的個(gè)數(shù)為：385

　　7、有一個(gè)二維數(shù)組a[1...100 , 1...65]有100行，65列，我們以行序?yàn)橹餍颍�如果該�?shù)組的基地址是10000，且每個(gè)元素占2個(gè)存儲(chǔ)單元，請(qǐng)問(wèn)a[56 , 22]的存儲(chǔ)地址是：17194

　　8、以下代碼輸出結(jié)果是：

　　[cpp] view plaincopyclass B

　　{

　　public:

　　B()

　　{

　　cout<<"B constructor\n";

　　s = "B";

　　}

　　void f()

　　{

　　cout<

　　}

　　private:

　　string s;

　　};

　　class D : public B

　　{

　　public:

　　D() : B()

　　{

　　cout<<"D constructor\n";

　　s = "D";

　　}

　　void f()

　　{

　　cout<

　　}

　　private:

　　string s;

　　};

　　int main(void)

　　{

　　B *b = new D();

　　b->f();

　　((D*)b)->f();

　　delete b;

　　return 0;

　　}

　　輸出結(jié)果是

　　B constructor

　　D constructor

　　BD

　　二、編程題

　　1、數(shù)組乘積(15分)

　　輸入：一個(gè)長(zhǎng)度為n的整數(shù)數(shù)組input

　　輸出：一個(gè)長(zhǎng)度為n的整數(shù)數(shù)組result，滿(mǎn)足result[i] = input數(shù)組中除了input[i]之外所有數(shù)的乘積(假設(shè)不會(huì)溢出)。比如輸入：input = {2,3,4,5}，輸出result = {60,40,30,24}

　　程序時(shí)間和空間復(fù)雜度越小越好。

　　C/C++：

　　int *cal(int* input , int n);

　　Java:

　　int[] cal(int[] input);

　　[cpp] view plaincopyint *cal(int* input , int n)

　　{

　　int i ;

　　int *result = new int[n];

　　result[0] = 1;

　　for(i = 1 ; i < n ; ++i)

　　result[i] = result[i-1]*input[i-1];

　　result[0] = input[n-1];

　　for(i = n-2 ; i > 0 ; --i)

　　{

　　result[i] *= result[0];

　　result[0] *= input[i];

　　}

　　return result;

　　}

　　2、異形數(shù)(25分)

　　在一個(gè)長(zhǎng)度為n的整形數(shù)組a里，除了三個(gè)數(shù)字只出現(xiàn)一次外，其他的數(shù)字都出現(xiàn)了2次。請(qǐng)寫(xiě)程序輸出任意一個(gè)只出現(xiàn)一次的數(shù)字，程序時(shí)間和空間復(fù)雜度越小越好。

　　例如： a = {1,3,7,9,5,9,4,3,6,1,7}，輸出4或5或6

　　C/C++：

　　void find(int* a , int n);

　　Java:

　　void find(int[] a);

　　[cpp] view plaincopy// lowbit表示的是某個(gè)數(shù)從右往左掃描第一次出現(xiàn)1的位置

　　int lowbit(int x)

　　{

　　return x&~(x-1);

　　}

　　void find(int* a , int n)

　　{

　　int i , xors;

　　xors = 0;

　　for(i = 0 ; i < n ; ++i)

　　xors ^= a[i];

　　// 三個(gè)數(shù)兩兩的異或后lowbit有兩個(gè)相同，一個(gè)不同，可以分為兩組

　　int fips = 0;

　　for(i = 0 ; i < n ; ++i)

　　fips ^= lowbit(xors ^ a[i]);

　　// 表示的是：flips=lowbit(a^b)^lowbit(a^c)^lowbit(b^c)

　　int b; // 假設(shè)三個(gè)只出現(xiàn)一次的其中一個(gè)數(shù)為b

　　b = 0;

　　for(i = 0 ; i < n ; ++i)

　　{

　　if(lowbit(xors ^ a[i]) == fips)

　　b ^= a[i];

　　}

　　// 成功找到三個(gè)數(shù)中一個(gè)數(shù)

　　cout<

　　}

　　3、朋友圈(25分)

　　假如已知有n個(gè)人和m對(duì)好友關(guān)系(存于數(shù)字r)。如果兩個(gè)人是直接或間接的好友(好友的好友的好友...)，則認(rèn)為他們屬于同一個(gè)朋友圈，請(qǐng)寫(xiě)程序求出這n個(gè)人里一共有多少個(gè)朋友圈。

　　假如：n = 5 ， m = 3 ， r = {{1 , 2} , {2 , 3} , {4 , 5}}，表示有5個(gè)人，1和2是好友，2和3是好友，4和5是好友，則1、2、3屬于一個(gè)朋友圈，4、5屬于另一個(gè)朋友圈，結(jié)果為2個(gè)朋友圈。

　　最后請(qǐng)分析所寫(xiě)代碼的時(shí)間、空間復(fù)雜度。評(píng)分會(huì)參考代碼的正確性和效率。

　　C/C++：

　　int friends(int n , int m , int* r[]);

　　Java:

　　int friends(int n , int m , int[][] r);

　　[cpp] view plaincopy// 簡(jiǎn)單的并查集應(yīng)用

　　int set[10001];

　　inline int find(int x) //帶路徑優(yōu)化的并查集查找算法

　　{

　　int i , j , r;

　　r = x;

　　while(set[r] != r)

　　r = set[r];

　　i = x;

　　while(i != r)

　　{

　　j = set[i];

　　set[i] = r;

　　i = j;

　　}

　　return r;

　　}

　　inline void merge(int x , int y) //優(yōu)化的并查集歸并算法

　　{

　　int t = find(x);

　　int h = find(y);

　　if(t < h)

　　set[h] = t;

　　else

　　set[t] = h;

　　}

　　int friends(int n , int m , int* r[])

　　{

　　int i , count;

　　for(i = 1 ; i <= n ; ++i) //初始化并查集，各點(diǎn)為孤立點(diǎn)，分支數(shù)為n

　　set[i] = i;

　　for(i = 0 ; i < m ; ++i)

　　merge(r[i][0] , r[i][1]);

　　count = 0;

　　for(i = 1 ; i <= n ; ++i)

　　{

　　if(set[i] == i)

　　++count;

　　}

　　return count;

　　}



熱門(mén)搜索的相關(guān)文章推薦：
DTT集團(tuán)筆試真題
普華永道PWC筆試題目
神州數(shù)碼筆試題
網(wǎng)通校園招聘筆試真題