公共題
選擇題 （每題5分）
1. 若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，則該二叉樹(shù)的度為0的結(jié)點(diǎn)個(gè)數(shù)是（???? ?）
A：9????B ： 11 ? ???C：12???? D：不確定?
?
2.下列排序算法中，其時(shí)間復(fù)雜度和記錄的初始排列無(wú)關(guān)的是（????? ）
A：插入排序?(預(yù)先排序，運(yùn)行時(shí)間為O(N)) ???B：堆排序 ? ???C：快速排序? (最壞情形O(N2))? D：冒泡排序?(最壞情形O(N2), 最優(yōu)O(N))
3.已知中序遍歷的序列為abcdef，高度最小的可能的二叉樹(shù)的葉子是（???? ）
A ： ace? ?????B ： acf? ???????C ： adf ? ??????D：cdf?
4.參加百年阿里培訓(xùn)的n位同學(xué)結(jié)伴去西湖旁邊為游人指路，兩人一組，他們打算先讓體重之和恰好為102公斤的同學(xué)一組，請(qǐng)給出一個(gè)算法找到這樣的組合，或者確定他們中不存在這樣的組合，其中最優(yōu)的算法時(shí)間復(fù)雜度為？（假設(shè)體重均為整數(shù)） （???? ）
A：O(log(n))????B：O(n)? ????C ： O(n log(n)) ? ??D：O(n^2)
?
5.眾所周知數(shù)據(jù)結(jié)構(gòu)中非常基本的樹(shù)結(jié)構(gòu)包括二叉查找樹(shù)（BST）。當(dāng)我們把如下序列：10，5，19，4，13，7，6，3，1按順序建立一棵BST時(shí)，樹(shù)的最大深度是？（令根節(jié)點(diǎn)深度為0，執(zhí)行不進(jìn)行平衡的基本插入） （???? ）
A：5????B ： 4? ???C：3? ???D：2?
?
6.阿里巴巴啟用了新的辦公大廈，這里的一切都充滿了現(xiàn)代感；工程師們打算在娛樂(lè)區(qū)用大小相等的圓形材料分割出一些空間，使用A,B,C三個(gè)圓形材料，最多可以將空間分為八個(gè)區(qū)域（包括圓形以外的區(qū)域），如果給你五個(gè)圓形材料，你最多可以幫助工程師們分出多少個(gè)空間？ （???? ）
A：20????B：22? ????C：26? ???D：32?
?
綜合題（每題15分）
1）?分析MergeSort的原理以及算法復(fù)雜度，并用最擅長(zhǎng)的編程語(yǔ)言實(shí)現(xiàn)Merge Sort。
MergeSort利用分治法的原理，依次減小問(wèn)題的規(guī)模。時(shí)間復(fù)雜度為O(nlog(n)), 空間復(fù)雜度為O(N);
[cpp] ?view plaincopy
void ?Mergesort( int ?*p,? int ?n)?? {?? ????void ?Msort( int ?*p,? int ?*temp,? int ?left,? int ?right);?? ????int ?*temp;?? ????if (n?<=?0?||?p?==?NULL)?? ????????return ;?? ????temp?=?(int ?*)malloc( sizeof ( int )?*?n);?? ????if (temp?==?NULL)?? ????????return ;?? ????Msort(p,?temp,?0,?n-1);??? ????free(temp);?? }?? ?? void ?Msort( int ?*p,? int ?*temp,? int ?left,? int ?right)?? {?? ????void ?Merge( int ?*p,? int ?*temp,? int ?left,? int ?rightbegin,? int ?right);?? ????int ?leftend?=?(right?+?left)/2;?? ????int ?rightbegin?=?leftend+1;?? ????if (left?<?right)?? ????{?? ????????Msort(p,?temp,?left,?leftend);?? ????????Msort(p,?temp,?rightbegin,?right);?? ????????Merge(p,?temp,?left,?rightbegin,?right);?? ????}?? }?? ?? void ?Merge( int ?*p,? int ?*temp,? int ?left,? int ?rightbegin,? int ?right)?? {?? ????int ?TempArray?=?rightbegin;?? ????int ?pos?=?left;?? ????int ?begin?=?left;?? ????while (left?<?TempArray?&&?rightbegin?<=?right)?? ????{?? ????????if (p[left]?<=?p[rightbegin])?? ????????{?? ????????????temp[pos++]?=?p[left++];?? ????????}?? ????????else ? if (p[left]?>?p[rightbegin])?? ????????{?? ????????????temp[pos++]?=?p[rightbegin++];?? ????????}?? ????}?? ????while (left?<?TempArray)?? ????????temp[pos++]?=?p[left++];?? ????while (rightbegin?<=?right)?? ????????temp[pos++]?=?p[rightbegin++];?? ????while (pos--?>=?begin)?? ????{?? ????????p[pos]?=?temp[pos];?? ????}?? }??
給定一個(gè)數(shù) t ， 以及 n 個(gè)整數(shù)，在這 n 個(gè)數(shù)中找到加和為 t 的所有組合， 例如 t = 4, n = 6, 這 6 個(gè)數(shù)為 ?[4, 3, 2, 2,?1, 1], 這樣輸出就有 4 個(gè)不同的組合它們的加和為 4: 4, 3+1, 2+2, and 2+1+1.?? 請(qǐng)?jiān)O(shè)計(jì)一個(gè)高效算法實(shí)現(xiàn)這個(gè)需求。
[cpp] ?view plaincopy
#include<iostream> ?? #include<vector> ?? ?? using ? namespace ?std;?? ?? void ?Find( int ?*p,? int ?n,? int ?sum);?? void ?Qsort( int ?*p,? int ?n);?? ?? int ?main()?? {?? ????int ?*p;?? ????int ?n;?? ????int ?sum;?? ????cin>>n;?? ????p?=?new ? int [n];?? ????for ( int ?i?=?0;?i?<?n;?++i)?? ????????cin>>p[i];?? ????cin>>sum;?? ????Qsort(p,?n);??? ????for ( int ?i?=?0;?i?<?n;?++i)?? ????????cout<<p[i]<<"?" ;?? ????cout<<endl;?? ????Find(p,?n,?sum);?? }?? ?? void ?Find( int ?*p,? int ?n,? int ?sum)?? {?? ????void ?FindSum( int ?*p,? int ?n,? int ?sum,?vector< int >?&vec);?? ????vector<int >?vec;?? ????if (p?==?NULL?||?n?<?0)?? ????????return ;?? ????if (sum?<?p[0])?? ????????return ;?? ????else ?? ????????FindSum(p,?n,?sum,vec);?? }?? ?? void ?FindSum( int ?*p,? int ?n,? int ?sum,?vector< int >?&vec)?? {?? ????if (sum?==?0)?? ????{?? ????????for (vector< int >::iterator?iter?=?vec.begin();?iter?!=?vec.end();?++iter)?? ????????????cout<<*iter<<"?" ;?? ????????cout<<endl;?? ????????return ?;?? ????}?? ????if (sum?<?*p?||?n?<?0)?? ????{?? ????????return ;?? ????}?? ????vec.push_back(*p);?? ????sum?-=?*p;?? ????FindSum(p+1,?n-1,?sum,?vec);?? ????sum?+=?*p;?? ????vec.pop_back();?? ????while (*p?==?*(p+1)?&&?p?<?p+n)? ?? ????????p++;?? ????FindSum(p+1,?n-1,?sum,?vec);?? }?? ?? void ?Qsort( int ?*p,? int ?n)?? {?? ????void ?swap( int ?*,? int ?*);?? ????int ?pivot;?? ????int ?j?=?-1;?? ????if (n?<=?1)?? ????????return ;?? ????pivot?=?p[n/2];?? ????swap(p+n/2,?p+n-1);?? ????for ( int ?i?=?0;?i?<?n-1;?++i)?? ????{?? ????????if (p[i]?<?pivot)?? ????????{?? ????????????j++;?? ????????????if (j?!=?i)?? ????????????{?? ????????????????swap(p+i,?p+j);?? ????????????}?? ????????}?? ????}?? ????swap(p+j+1,?p+n-1);?? ????Qsort(p,?j+1);?? ????Qsort(p+j+2,?n-j-2);?? }?? ?? void ?swap( int ?*a,? int ?*b)?? {?? ????int ?temp;?? ????temp?=?*a;?? ????*a?=?*b;?? ????*b?=?temp;?? }??
熱點(diǎn)題? 聊聊近期最吸引你的互聯(lián)網(wǎng)事件，談?wù)勀銓?duì)此事件的看法。
C&C++部分
選擇題 （每題5分）
1、 int main(void)
{
? int count=0; int m=779;
? while(m)
? {count++;? m=m&(m-1);}
? printf("%d\n",count); return0;
}
請(qǐng)問(wèn)最終輸出的count值為（????）?????????A：? 3???? ?B： 4?? ???C ： 5 ???? ?D： 8
?
2、 在32位操作系統(tǒng)中，我們定義如下變量
int (*n)[10];
請(qǐng)問(wèn)調(diào)用函數(shù)sizeof(n)，返回值為（???? ）??A ： 4 ?????B： 40? ???C： 8 ????D： 80
?
3、 int main(void)
{
? int i=1;? int j=i++;
? if((i++>++j) && (++i == j))i+=j;
? printf("%d\n",i);?return 0;
}
請(qǐng)問(wèn)最終輸出的i值為（????）?????????????A：? 2?? ??B ： 3 ??????C： 4???? ?D： 5
?
4、 以下敘述中正確的是（???? ）
A： 可以在一個(gè)函數(shù)中定義另一個(gè)函數(shù)?????B： main()函數(shù)必須放在其他函數(shù)之前
C ： 構(gòu)成C++ 語(yǔ)言程序的基本單位是類?????D： 所有被調(diào)用的函數(shù)一定要在調(diào)用之前進(jìn)行定義
?
綜合題 （每題15分）
有10億個(gè)數(shù)，這些數(shù)的值都在0~1000萬(wàn)之內(nèi)。請(qǐng)使用定義一個(gè)數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)這些數(shù)字的存儲(chǔ)，并實(shí)現(xiàn)函數(shù)get_bigger_count( unsigned value )，輸入一個(gè)值value，返回這10億個(gè)數(shù)中比value值大的數(shù)的數(shù)目。
要求：不能使用STL，請(qǐng)盡量考慮性能與資源的占用。??
思路：創(chuàng)建一個(gè)包含1000萬(wàn)個(gè)元素的數(shù)組，然后遍歷10億個(gè)數(shù)字，數(shù)組用來(lái)統(tǒng)計(jì)對(duì)應(yīng)數(shù)字出現(xiàn)的次數(shù)。
如果10億個(gè)數(shù)字中0~1000萬(wàn)是隨機(jī)出現(xiàn)的，可以滿足需求。如果有一個(gè)數(shù)字出現(xiàn)的次數(shù)非常的，則數(shù)組可能溢出。 ?
總結(jié)
以上是生活随笔 為你收集整理的2011阿里巴巴集团实习生招聘笔试题 CC++ 的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔 網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔 推薦給好友。
