阿里巴巴集团2014秋季校园招聘笔试题
轉載請標明出處,原文地址:http://blog.csdn.net/hackbuteer1/article/details/11931173
第一部分 單選題(前10題,每題2分;后10題,每題3分,共50分,選對得滿分,選錯倒扣1分,不選得0分)
1、假設把整數關鍵碼K散列到有N個槽的散列表,以下哪些散列函數是好的散列函數()
A、h(K)=K mod N;
B、h(K)=1;
C、h(K)=K/N;
D: h(K)=(K+rand(N)) mod N, rand(N)返回一個0到N-1的整數
2. 下面排序算法中,初始數據集的排列順序對算法的性能無影響的是()
A、堆排序 ? ? ?B、插入排序
C、冒泡排序 ? ?D、快速排序
3、下面說法錯誤的是:
A、CISC計算機比RISC計算機指令多
B、馮諾依曼機體系結構的主要特征是存儲程序的工作方式
C、增加流水線段數理論上可以提高CPU頻率
D、在指令格式中,采用擴展操作碼設計方案的目的是為了保持指令字長不變而增加尋址空間
4、不屬于馮諾依曼機體系結構必要組成部分的是:
A、CPU ? ? ? ? ?B、Cache ? ? ? ?C、RAM ? ? ? ?D、ROM
5、一個棧的入棧序列式ABCDE,則不可能的出棧序列是:
A、DECBA ? ? ? ? ?B、DCEBA ? ? ? ? ?C、ECDBA ? ? ? D、ABCDE
6.你認為可以完成編寫一個C語言編譯器的設計語言是:
A、匯編語言 ? ? ? ?B、C語言 ? ? ? C、VB語言 ? ? ? D、以上皆可
7. 關于C++/JAVA類中的static成員和對象成員的說法正確的是:
A、虛成員函數不可能是static成員函數
B、static成員函數在對象成員函數中無法調用
C、static成員變量在對象構造時生成
D、static成員函數不能訪問static成員變量
8、
C、13個
9、某進程在運行過程中需要等待從磁盤上讀入數據,此時該進程的狀態將:
A、從就緒變為運行 ? ? ? B、從運行變為就緒
C、從運行變為阻塞 ? ? ? D、從阻塞變為就緒
10、下面算法的時間復雜度為:
11、n從1開始,每個操作可以選擇對n加1或者對n加倍。若想獲得整數2013,最少需要多少個操作。
A、24 ? ? ? ?B、21 ? ? ? ? C、18 ? ? ? D、不可能
12、對于一個具有n個頂點的無向圖,若采用鄰接表數據結構表示,則存放表頭節點的數組大小為:
A、n ? ? ? ? B、n+1 ? ? ? C、n-1 ? ? ?D、n+邊數
14:如下函數,在32bit系統foo(2^31-3)的值是:
int foo(int x) {return x&-x; } A、0 ? ? ? ? B、1 ? ? ? ? ?C、2 ? ? ? ? D、4
15、對于順序存儲的線性數組,訪問節點和增加、刪除節點的時間復雜度為:
A、O(n),O(n) ? ? ? ? B、O(n),O(1) ? ? ? ? C、O(1),O(n) ? ? ? ? ?D、O(1),O(1)
16、在32位系統環境中,編譯選項為4字節對齊,那么sizeof(A)和sizeof(B)是:
struct A {int a;short b;int c;char d; }; struct B {int a;short b;char d;int c; }; A、16,16 ? ? ? ? ? ? ? B、16,12 ? ? ? ? ? ?C、13,12 ? ? ? D、11,16
17、袋中有紅球,黃球,白球各一個,每次任意取一個又放回,如此連續抽取3次,則下列事件中概率是8/9的是:
A、顏色不全相同 ? ? ? ? ? ?B、顏色全相同 ? ? ? ? ?C、顏色全不同 ? ? ? ? D、顏色無紅色
18、一個洗牌程序的功能是將n張牌的順序打亂,以下關于洗牌程序的功能定義說法最恰當的是:
A、任何連續位置上的兩張牌的內容獨立
B、n張牌的任何兩個不同排列出現的概率相等
C、每張牌出現在n個位置上的概率相等
D、每張牌出現在n個位置上的概率獨立
19、用兩種顏色去染排成一個圈的6個棋子,如果通過旋轉得到則只算一種,一共有多少種染色模式。
A、10 ? ? ? ? B、14 ? ? ? ? C、15 ? ? ? ? D、16
20、遞歸式的先序遍歷一個n節點,深度為d的二叉樹,則需要棧空間的大小為:
A: O(logn) ? ? ? ? ? B:O(nlogn) ? ? ? ? ?C:O(n) ? ? ? ? ? ? D:(d)
第二部分 不定向選項(4題,每題5分,完全正確計5分,漏選計2分,不選計0分,多選、錯選計-2分)
轉載請標明出處,原文地址: http://blog.csdn.net/hackbuteer1/article/details/11931173
21、兩個線程運行在雙核機器上,每個線程主線程如下,線程1:x=1;r1=y;線程2:y=1;r2=x;
x和y是全局變量,初始為0。以下哪一個是r1和r2的可能值:
A、r1=0,r2=0
B、r1=1,r2=0
C、r1=1,r2=1
D、r1=0,r2=1
22、關于Linux系統的負載(Load),以下表述正確的是:
A: Load:2.5,1.3,1.1表示系統的負載壓力在逐漸減小
B: 通過就緒和運行的進程數來反映
C: 通過TOP命令查看
D: 通過uptime查看
23、關于排序算法的以下說法,錯誤的是:
A、歸并排序的平均時間復雜度O(nlogn),最壞時間復雜度O(n^2)
B、堆排序平均時間復雜度O(nlogn),最壞時間復雜度O(nlogn)
C、冒泡排序平均時間復雜度O(n^2),最壞時間復雜度O(n^2)
D、快速排序的平均時間復雜度O(nlogn),最壞時間復雜度O(N^2)
24、假設函數rand_k會隨機返回一個【1,k】之間的隨機數(k>=2),并且每個證書出現的概率相等。目前有rand_7,通過調用rand_7()和四則運算符,并適當增加邏輯判斷和循環控制邏輯,下列函數可以實現的有:
A、rand_3 ? ? ? ? B、rand_21 ? ? ? ? ?C、rand_23 ? ? ? ? D、rand_47
第三部分 填空與問答
25、某二叉樹的前序遍歷序列為-+a*b-cd/ef,后序遍歷序列為abcd-*+ef/-,問其中序遍歷序列是:
26、某緩存系統采用LRU淘汰算法,假定緩存容量為4,并且初始為空,那么在順序訪問以下數據項的時候,1、5、1、3、5、2、4、1、2,出現緩存直接命中的次數是(),最后緩存中即將準備淘汰的數據項是()
27、有兩個較長的單向鏈表a和b,為了找出節點node滿足node in a 并且 node in b,請設計空間使用盡量小的算法。(用C/C++/JAVA或偽碼表示都可以)
28、當存儲數據量超出單節點數據管理能力的時候,可以采取的辦法有數據庫sharding的解決方案,也就是按照一定的規律把數據分散存儲在多個數據管理節點N中(節點編號0.1.2...N-1)。假設存儲的數據是a,請完成為數據a計算存儲節點的程序。(沒學過C語言的同學也可以用偽碼完成)
#define N 5 int hash(int element) {return element*2654435761; } int shardingIndex(int a) {int p = hash(a);//1return p; } 空格1處: ? ? p %= N;
29、宿舍內5個同學一起玩對戰游戲,每場比賽有一些人作為紅方,另一些人作為藍方,請問至少需要多少場比賽,才能使任意兩個人之間有一場紅方對藍方和一場藍方對紅方的比賽?
答案為4場。
第四部分 JAVA選做題
1、以下每個線程輸出的結果是什么?(不用關注輸出的順序,只需寫出輸出的結果集即可)
2、一個有10億條記錄的文本文件,已按照關鍵字排好序存儲,請設計算法,可以快速的從文件中查找關鍵字的記錄。
轉載請標明出處,原文地址: http://blog.csdn.net/hackbuteer1/article/details/11931173
C++選做題
Part I
假設你有一臺計算機,配置如下:
48GB內存
16核CPU,3.0GHz
12塊2TB SATA硬盤
有兩個數據文件A和B,A的大小是40GB,B的大小是2TB,A和B的文件格式一樣,都包含等長的100字節的記錄,記錄的前20個字節表示key,后80個字節表示value,所有的key和value都由數字和大小寫字母組成(0-9 A-Z a-z),同一個文件中的key沒有排序,也沒有重復。
文件A和B都切成了1GB(1*10^9字節)的數據塊(名為A000001、A000002......A000010、B000001、B000002......B002000),均勻分布在6塊硬盤上。
請問如何用最快的方法找到A和B之間共同的key,以及他們對應的value值(建議輸出格式如下所示:<key><空格><A中對應value><空格><B中對應value>)
請描述你的方法里面用到的關鍵的數據結構和算法,估算這個方法需要的內存空間和運算時間,并說明你的推導過程。
Part II
如果你有100臺服務器,每臺配置如上描述,它們通過千兆網絡組成一個集群,任意兩臺之間的帶寬可以達到1000Mbps,同時假設文件A和B的大小也放大100倍(各位4TB和200TB),并且被切分成1GB的碎片,均勻分布在100臺服務器上。
請問如何用最快的方法找到A和B之間共同的key,以及他們對應的value值(建議輸出格式如下所示:<key><空格><A中對應value><空格><B中對應value>)
請描述你的方法里面用到的關鍵的數據結構和算法,估算這個方法需要的內存空間、網絡流和運算時間,并說明你的推導過程。
轉載請標明出處,原文地址: http://blog.csdn.net/hackbuteer1/article/details/11931173
代碼
總結
以上是生活随笔為你收集整理的阿里巴巴集团2014秋季校园招聘笔试题的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 迅雷2014校园招聘笔试题
- 下一篇: 2015届华为校园招聘机试题