1、騰訊2014校園招聘軟件開發類筆試試題考試時長：120分鐘一不定項選擇題（共 25題，每題4分，共100分，少選、錯選、多選均不得分）1已知一棵二叉樹，如果先序遍歷的節點順序是：ADCEFGHB ,中序遍歷是：CDFEGHAB ,則后序遍歷結果為：（D）A. CFHGEBDA B . CDFEGHBA C . FGHCDEBA D . CFHGEDBA2下列哪兩個數據結構，同時具有較高的查找和刪除性能？ （ CD）A.有序數組B .有序鏈表C . AVL樹 D . Hash表3下列排序算法中，哪些時間復雜度不會超過nlogn ? （ BC ）A .快速排序 B .堆排序 C .歸并排序 D .

2、冒泡排序4初始序列為1 8 6 2 5 4 7 3 一組數采用堆排序，當建堆（小根堆）完畢時，堆所對應的二 叉樹中序遍歷序列為：（A）8 3 2 5 1 6 4 73 2 8 5 1 4 6 73 8 2 5 1 6 7 48 2 3 5 1 4 7 65當n=5時，下列函數的返回值是：（A）int foo（int n）（if（nlchild!=NULL)if (t-rchild!=NULL) N2+;else NL+;else if (t-rchild!=NULL) NR+;else N0+;if(t-lchild!=NULL) count(t-lchild);if(t-rchild!=NU

3、LL) count(t-rchild);/* call form :if(t!=NULL) count(t);*/三、其他方向簡答題(共 2題，每題20分)，選作題，不計入總分)6 / 161請設計一個排隊系統，能夠讓每個進入隊伍的用戶都能看到自己在隊列中所處的位置和變化，隊伍可能隨時有人加入和退出；當有人退出影響到用戶的位置排名時需要及時反饋到用戶。2 A, B兩個整數集合，設計一個算法求他們的交集，盡可能的高效。阿里巴巴2014秋季校園招聘-軟件研發工程師筆試題2013-09-21 22:381089 人閱讀評論(4)收藏舉報校園招聘阿里巴巴軟件研發算法百度1.單選題1.假設把整數關鍵碼

4、K散列到N個槽列表，以下哪些散列函數是好的散列函數h(K)=K/N;h(K)=1;h(K)=K mod N;h(K)=(K+rand(N) mod N, rand(N) 返回 0到 N-1 的整數答案:D.下面排序算法中，初始數據集的排列順序對算法的性能無影響的是：A:堆排序B:插入排序C:冒泡排序D:快速排序答案:A (插入排序：最優時間復雜度O (n)最差時間復雜度 O (n2)平均時間復雜度 O(nA2)冒泡排序：最優時間復雜度O (n)最差時間復雜度 O 5人2)平均時間復雜度O (門人2 )7 / 16快速排序：最優時間復雜度O (nlogn)最差時間復雜度 O (M2)平均時間復雜

5、度 O (nlogn )堆排序：最優時間復雜度O (nlogn )最差時間復雜度 O (nlogn)平均時間復雜度O (nlogn ).下面說法錯誤的是：A: CISC計算機比RISC計算機指令多B:在指令格式中，采用擴展操作碼設計方案的目的是為了保持指令字長不變而增 加尋址空間C:增加流水線段數理論上可以提高CPU頻率D:馮諾依曼體系結構的主要特征是存儲程序的工作方式答案:B.不屬于馮諾依曼體系結構必要組成部分是：A:CPU B: Cache C:RAM D:ROM答案:B. 一個棧的入棧序列式 ABCDE則不可能的出棧序列是：A:DECBA B:DCEBA C:ECDBA D:ABCDE答

6、案:C.你認為可以完成編寫一個C語言編譯器的語言是：A:匯編B:C語言C:VB D:以上全可以答案：D.關于C+/JAVA類中的static成員和對象成員的說法正確的是：A： static成員變量在對象構造時候生成: static成員函數在對象成員函數中無法調用C:虛成員函數不可能是static成員函數8 / 16D: static成員函數不能訪問 static成員變量答案：A8:答案：C9:某進程在運行過程中需要等待從磁盤上讀入數據，此時進程的狀態將:A:從就緒變為運行B:從運行變為就緒C:從運行變為阻塞D:從阻塞變為就緒答案：C10:下面算法的時間復雜度為：Int f(unsigned i

7、nt n) (If(n=0|n=1)Return 1;Else9 / 16Return n*f(n-1);)A: O(1) B:O(n) C:O(N*N) D:O(n!)答案：Bn從1開始，每個操作可以選擇對n力口1或者對n加倍。若想獲得整數2013 ,最少需要多少個操作。A:18B:24C:21 D;不可能答案：A,2013用除法，顯示2013-2012-1006-503-502-251-250-125-124-62-31-30-15-14-7-6-3-2-1正向只能是+1和X2,所以逆向只能-1和/2,由上過程可得18次12:對于一個具有n個頂點的無向圖，若采用鄰接表數據結構表示，則存放表

8、頭節點的數 組大小為：A: n B: n+1 C: n-1 D:n+ 邊數答案：A13:13.考慮一個特殊的hash函數h,能將任一字符串hash睨一個整微k,其撤率 P(k)=27- k),，b,對一個未知大小的字符串集合S中的錘一個元素取hash值所組成的集合為h(S),若htS)中最大的元素max h二 那么S的大小的期望是一。1024 Bs 512 C、5 D. 10答案:A.對于幾何中的每個字符串取hash可以看作是同分布的獨立重復事件，所以每一個事件出現10的概率都是p=1/1024 ,那么當出現的時候，期望的次數就是1/p, 1024.14：如下函數，在 32bit系統foo(2

9、A31-3)的值是：Int foo(int x)(10 / 16Return x&-x;)A:0 B: 1C:2 D:4答案：B15:對于順序存儲的線性數組，訪問節點和增加節點刪除節點的時間復雜度為：A: O(n),O(n)B:O(n),O(1) C:O(1),O(n) D:O(n),O(n)答案：C16:在32為系統環境，編譯選項為 4字節對齊，那么 sizeof(A)和sizeof(B)是:Struct A Int a;short b;int c;char d;);Struct B int a;short b;char c;int c;);A: 16,16B:13,12C:16,12D:1

10、1,16答案：C11 / 163次，則下列事件中概17:袋中有紅球，黃球，白球各一個，每次任意取一個放回，如此連續 率是8/9的是：A:顏色不全相同 B:顏色全不相同C:顏色全相同D:顏色無紅色答案：A18: 一個洗牌程序的功能是將n張牌的順序打亂，以下關于洗牌程序的功能定義說法最恰當的是：A:每張牌出現在n個位置上的概率相等B:每張牌出現在 n個位置上的概率獨立C:任何連續位置上的兩張牌的內容獨立D: n張牌的任何兩個不同排列出現的概率相等答案：A19:用兩種顏色去染排成一個圈的 6個棋子，如果通過旋轉得到則只算一種，一共有多少種 染色：10 B:11 C:14: D:15答案：C解釋：應該

11、有14種方案，設只有黑白兩色，默認白色，那么，用 p (n)表示有n個黑棋的 種類p (0) =p (6) =1p (1) =p (5) =1p (2) =p (4) =3 相鄰的一種，隔一個的一種，兩個的一種p (3) =4 都相鄰的一種， BB0B的一種，BB00B的一種，B0B0B的一種，一共4種綜上是14種20:遞歸式的先序遍歷一個n節點，深度為d的二叉樹，則需要棧空間的大小為：A: O(n) B:O(d) C:O(logn) D:(nlogn)12 / 16答案：B第二部分：多選21 :兩個線程運行在雙核機器上，每個線程主線程如下，線程1: x=1;r1=y;線程2 : y=1;r2

12、=x;X和y是全局變量，初始為0。以下哪一個是r1和r2的可能值：A: r1=1,r2=1r1=1,r2=0C:r1=0,r2=0D:r1=0,r2=1答案：ABD22.關于Linux系統的負載，以下表述正確的是：A:通過就緒和運行的進程數來反映B:通過TOP命令查看C:通過uptime查看D: Load:2.5,1.3,1.1表示系統的負載壓力在逐漸變小答案：BC (對于A不確定)23:關于排序算法的以下說法，錯誤的是：A:快速排序的平均時間復雜度O(nlogn),最壞O(N，)B:堆排序平均時間復雜度O(nlogn),最壞O(nlogn)C:冒泡排序平均時間復雜度O(nV),最壞O(n，)

13、D:歸并排序的平均時間復雜度O(nlogn),最壞O(n)答案：D解釋：歸并排序的平均時間復雜度O(nlogn),最壞O(nlogn)24:假設函數rand_k會隨機返回一個【1, k】之間的隨機數(k=2 ),并且每個證書出現的13 / 16 概率相等。目前有rand_7,通過調用rand_7 （）和四則運算符，并適當增加邏輯判斷和循環 控制邏輯，下列函數可以實現的有：A:rand_3 B:rand_21 C:rand_23 D:rand_49答案：ABCD解釋：對于rand_x （x5,1,3- 5,1,3,2- 1,3,2,4- 3,2,4,1- 3,4,1,2- 首先1調入內存，然后5

14、調入內存，然后1調入內存（命中緩存），然后3調入內存，然后2調 入內存，然后4調入內存（將最少使用的 5置換出內存），然后1調入內存（命中緩存），然后 2調入內存（命中緩存）。最后，最少使用的3將面臨被置換出的危險。27、兩個較長的單向鏈表a和b,為了找出及談單 noed滿足node in a并且node in b。請設計空間使用盡量小的算法（用c/c+ , java或者偽代碼）html view plaincopyprint?I struct node;14 /1634567S91011121314151617IS192021上工232425 第27282930313233343536373

15、S39404142 書444546int v;node *next;)；/*返回鏈表的長度鏈表為空返回0*/size_t listLen(node * p) (size_t num = 0;while (p!=NULL) (num+;p = p-next;)return num;)/如果找到了則返回指針指向公共節點/如果不存在則返回空指針node * findFirstCommenNode(node * pheada, node * pheadb) (size_t lenA = listLen(pheada);size_t lenB = listLen(pheadb);node * plist

16、A = pheada;node * plistB = pheadb;調整長度/plistA指向較長的一個 if (lenA lenB)(plistA = plistA-next;-lenA;)一樣長了尋找公共節點while (plistA!=NULL & plistA != plistB)15 / 1644849505152(plistA = plistA-next;plistB = plistB-next;)return plistA;)算法的空間復雜度 O(1),時間復雜度O(m+n)。28、當存儲數據量超出單節點數據管理能力的時候，可以采用的辦法有數據庫sharding的解決方案，也就是按照一定的規律把數據分散存儲在多個數據管理節點N中(節點編號為0,1,2 , N-1 )。假設存儲的數據時 a請完成為數據a計算存儲節點的程序。html view plaincopyprint?#