阿里巴巴2014秋季校園招聘 軟件研發(fā)工程師筆試題答案

1、 單選題2014研發(fā) 1. 個槽列表，以下哪些散列函數(shù)是好的散列函數(shù)1. 假設(shè)把整數(shù)關(guān)鍵碼K散列到N A: h(K)=K/N; B: h(K)=1; C: h(K)=K mod N; N-1的整數(shù)到 D: h(K)=(K+rand(N) mod N, rand(N)返回0 答案:D 2. 下面排序算法中，初始數(shù)據(jù)集的排列順序?qū)λ惴ǖ男阅軣o影響的是： A: 堆排序 B：插入排序 冒泡排序 C: D:快速排序OO答案:A（插入排序：最優(yōu)時間復(fù)雜度（n）最差時間復(fù)雜度O（n2）平均時間復(fù)雜度 ）（n2O 冒泡排序：最優(yōu)時間復(fù)雜度）平均時間復(fù)雜度（n2OO（n）最差時間復(fù)雜度 n2）（）平均時間復(fù)雜度

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

3、棧的入棧序列式 A:DECBA B:DCEBA C:ECDBA D:ABCDE 答案:C6.你認(rèn)為可以完成編寫一個C語言編譯器的語言是： A：匯編 B:C語言 C:VB D:以上全可以 答案：D 7. 關(guān)于C+/JAVA類中的static成員和對象成員的說確的是： A：static成員變量在對象構(gòu)造時候生成 B: static成員函數(shù)在對象成員函數(shù)中無法調(diào)用 C: 虛成員函數(shù)不可能是static成員函數(shù) D: static成員函數(shù)不能訪問static成員變量 答案：A 8： C答案： 9：某進(jìn)程在運行過程中需要等待從磁盤上讀入數(shù)據(jù)，此時進(jìn)程的狀態(tài)將： A: 從就緒變?yōu)檫\行 B:從運行變?yōu)榫途w

4、C: 從運行變?yōu)樽枞?D:從阻塞變?yōu)榫途w 答案：C 10：下面算法的時間復(fù)雜度為： Int f(unsigned int n) If(n=0|n=1) Return 1; Else Return n*f(n-1); A: O(1) B:O(n) C:O(N*N) D:O(n!) 答案：B，最少需要多n開始，每個操作可以選擇對加1或者對n加倍。若想獲得整數(shù)從11: n12013 少個操作。 A:18 B:24 C:21 D；不可能2013-2012-1006-503-502-251-250-125-124-62-， 對2013用除法，顯示A答案： 31-30-15-14-7-6-3-2-1 18

5、次和2，所以逆向只能-1和/2，由上過程可得+1正向只能是個頂點的無向圖，若采用鄰接表數(shù)據(jù)結(jié)構(gòu)表示，則存放表頭節(jié)點的數(shù)組大：對于一個具有n12小為： A: n B: n+1 C: n-1 D:n+邊數(shù) 答案：A ：13 可以看作是同分布的獨立重復(fù)事件，所以每一個事件hash答案:A.對于幾何中的每個字符串取 1/p，p=1/1024出現(xiàn)10的概率都是1024.，那么當(dāng)出現(xiàn)的時候，期望的次數(shù)就是 的值是：如下函數(shù)，在1432bit系統(tǒng)foo(231-3) Int foo(int x) Return x&-x; 0 B: 1 C:2 D:4：A B答案： ：對于順序存儲的線性數(shù)組，訪問節(jié)點和增加節(jié)

6、點刪除節(jié)點的時間復(fù)雜度為：15 A: O(n),O(n)B:O(n),O(1) C:O(1),O(n) D:O(n),O(n) 答案：C 3216:在為系統(tǒng)環(huán)境，編譯選項為4字節(jié)對齊，那么sizeof(B)和是：sizeof(A) Struct A Int a; short b; int c; char d; ;Struct B int a; short b; char c; int c; ; A: 16,16 B:13,12 C:16,12D:11,16 C答案：次，則下列事件中概率317:袋中有紅球，黃球，白球各一個，每次任意取一個放回，如此連續(xù) 是8/9的是： 顏色全相同D: B:顏色全

7、不相同C:顏色無紅色A: 顏色不全相同 答案：A牌的順序打亂，以下關(guān)于洗牌程序的功能定義說法最恰當(dāng)?shù)?8：一個洗牌程序的功能是將n 是： A: 每牌出現(xiàn)在n個位置上的概率相等 B: 個位置上的概率獨立每牌出現(xiàn)在n 任何連續(xù)位置上的兩牌的容獨立C: D: n牌的任何兩個不同排列出現(xiàn)的概率相等 A答案：個棋子，如果通過旋轉(zhuǎn)得到則只算一種，一共有多少種染：用兩種顏色去染排成一個圈的619 色： A: 10 B:11 C:14: D:15 答案：C個黑棋的種n）表示有n解釋：應(yīng)該有14種方案，設(shè)只有黑白兩色，默認(rèn)白色，那么，用p（ 類 6）=1（0）=p（p ）=1=p1）（5p（2）=p（4）p（=

8、3 /相鄰的一種，隔一個的一種，兩個的一種 種4的一種，一共B0B0B的一種，BB00B的一種，BB0B都相鄰的一種，=4 /）3（p 種綜上是14 20：遞歸式的先序遍歷一個n節(jié)點，深度為的二叉樹，則需要?？臻g的大小為：d A: O(n) B:O(d) C:O(logn) D:(nlogn) B答案： 第二部分：多選 1：兩個線程運行在雙核機(jī)器上，每個線程主線程如下，線程：x=1;r1=y;線程2：y=1;r2=x;21 的可能值：和。以下哪一個是r1r2是全局變量，初始為X和y0 A: r1=1,r2=1 B: r1=1,r2=0 C:r1=0,r2=0 D:r1=0,r2=1 答案：AB

9、D 系統(tǒng)的負(fù)載，以下表述正確的是：22.關(guān)于Linux 通過就緒和運行的進(jìn)程數(shù)來反映A: 通過B: TOP命令查看 查看C: 通過uptime 表示系統(tǒng)的負(fù)載壓力在逐漸變小D: Load:2.5,1.3,1.1 （對于A不確定）BC答案： ：關(guān)于排序算法的以下說法，錯誤的是：23 最壞O(N2)O(nlogn),A: 快速排序的平均時間復(fù)雜度 O(nlogn)，最壞B:堆排序平均時間復(fù)雜度O(nlogn) O(n2)C:冒泡排序平均時間復(fù)雜度O(n2),最壞 O(n2)最壞歸并排序的平均時間復(fù)雜度D:O(nlogn), D答案： 最壞O(nlogn)解釋：歸并排序的平均時間復(fù)雜度O(nlogn

10、),并且每個證書出現(xiàn)的概率24:假設(shè)函數(shù)rand_k,會隨機(jī)返回一個【1，k=2k】之間的隨機(jī)數(shù)（）（）和四則運算符，并適當(dāng)增加邏輯判斷和循環(huán)控制邏rand_7相等。目前有rand_7,通過調(diào)用 輯，下列函數(shù)可以實現(xiàn)的有： A:rand_3 B:rand_21 C:rand_23 D:rand_49 ABCD答案：能夠做到rand_x解釋：對于rand_x（xnext; ? ? ? return num; ? ? 則返回指針 指向公共節(jié)點/ 如果找到了 / 如果不存在 則返回空指針? node * findFirstCommenNode(node * pheada, node * pheadb

11、) ? ? ? size_t lenA = listLen(pheada); ? size_t lenB = listLen(pheadb); ? ? node * plistA = pheada; ? node * plistB = pheadb; ? /調(diào)整長度 /plistA ? 指向較長的一個 ? if (lenA lenB) ? ? plistA = plistA-next; ? -lenA; ? ? /?一樣長了 /?尋找公共節(jié)點 while (plistA!=NULL & plistA != plistB) ? ? plistA = plistA-next; ? plistB = plistB-next; ? ? return plistA; ? ? 算法的空間復(fù)雜度O(1)，時間復(fù)雜度O(m+n)。 28、當(dāng)存儲數(shù)據(jù)量超出單節(jié)點數(shù)據(jù)管理能力的時候，可以采用的辦法有數(shù)據(jù)庫sharding的解決方案，也就是按照一定的規(guī)律把數(shù)據(jù)分散存儲在多個數(shù)據(jù)管理節(jié)點N中（節(jié)點編號為0,1,2，N-1）。假設(shè)存儲的數(shù)據(jù)時a 請完成為數(shù)據(jù)a計算存儲節(jié)點的程序。 htmlview plaincopyprint? ? #define N 5 ? int hash(int element) return element*2654435761; ? ? int shardi