阿里校招筆試題目

時間：2022-12-10 01:42:02 筆試題目我要投稿

相關(guān)推薦

2014年阿里校招筆試題目

　　前言

2014年阿里校招筆試題目

　　我明天上午9點還有面試，今天突然看到某大牌IT公司筆試題目，必須做一下了

　　題目

　　一、單選題

　　1.假設(shè)把整數(shù)關(guān)鍵碼K散列到N個槽列表，以下哪些散列函數(shù)是好的散列函數(shù)

　　A: h(K)=K/N;

　　B: h(K)=1;

　　C: h(K)=K mod N;

　　D: h(K)=(K+rand(N)) mod N, rand(N)返回0到N-1的整數(shù)

　　選擇C，解釋：開始糾結(jié)于C和D，但是hash的特性在于常數(shù)的時間執(zhí)行插入、刪除和查找操作，用D作為hash函數(shù)無法滿足該條件，用C產(chǎn)生碰撞可以用鏈接法解決沖突，感謝@zdw12242的糾正

　　2.下面排序算法中，初始數(shù)據(jù)集的排列順序?qū)λ惴ǖ男阅軣o影響的是：

　　A: 堆排序 B：插入排序

　　C: 冒泡排序 D:快速排序

　　選擇A，解釋：(1)堆排序的時間復(fù)雜度一直都是O(nlogn),不穩(wěn)定(2)插入排序在初始有序情況下，時間復(fù)雜度為O(n),平均時間復(fù)雜度為O(n^2)，穩(wěn)定排序(3)冒泡排序在初始有序的情況下，增加交換標(biāo)示flag可將時間復(fù)雜度降到O(n),穩(wěn)定排序(4)快速排序在初始有序的情況下，可能會退化到O(n^2)，不穩(wěn)定排序

　　3. 下面說法錯誤的是：

　　A: CISC計算機比RISC計算機指令多

　　B: 在指令格式中，采用擴展操作碼設(shè)計方案的目的是為了保持指令字長不變而增加尋址空間

　　C:增加流水線段數(shù)理論上可以提高CPU頻率

　　D:馮諾依曼體系結(jié)構(gòu)的主要特征是存儲程序的工作方式

　　選擇B，解釋(1)CISC復(fù)雜指令集，RISC精簡指令集，從名字上就可以得出A正確(2)保持指令字長度不變而增加指令操作的數(shù)量(3)看樣子都覺得正確(4)馮諾依曼體系結(jié)構(gòu)的主要特點：存儲程序控制(要求計算機完成的功能，必須事先編制好相應(yīng)的程序，并輸入到存儲器中，計算機的工作過程是運行程序的過程);程序由指令構(gòu)成，指令和數(shù)據(jù)都用二進制表示;指令由操作碼和地址碼構(gòu)成;機器以cpu為中心

　　4. 不屬于馮諾依曼體系結(jié)構(gòu)必要組成部分是：

　　A:CPU B: Cache C:RAM D:ROM

　　B，解釋：馮諾依曼體系結(jié)構(gòu)必要組成部分：運算器、控制器、存儲器、輸入設(shè)備、輸出設(shè)備，Cache屬于緩存了

　　5. 一個棧的入棧序列式ABCDE則不可能的出棧序列是:

　　A:DECBA B:DCEBA C:ECDBA D:ABCDE

　　C，不解釋

　　.你認(rèn)為可以完成編寫一個C語言編譯器的語言是：

　　A：匯編 B:C語言 C:VB D:以上全可以

　　D,解釋：其實你學(xué)好編譯原理用什么語言都能寫出來

　　7. 關(guān)于C++/JAVA類中的static成員和對象成員的說法正確的是：

　　A：static成員變量在對象構(gòu)造時候生成

　　B: static成員函數(shù)在對象成員函數(shù)中無法調(diào)用

　　C: 虛成員函數(shù)不可能是static成員函數(shù)

　　D: static成員函數(shù)不能訪問static成員變量

　　C,解釋：雖然博主主要以php和c為主，php也能面向?qū)ο�，我來簡單說明一下。(1)static成員變量可以直接定義，例如public statci $a = 10; 所以A錯(2)在對象成員函數(shù)里可以通過類名：：static函數(shù)名的方法調(diào)用，我的項目中超過靜態(tài)方法(4)同樣道理，類名：：static成員變量名，這也是訪問static成員變量唯一的方法(3)是正確的，雖然我都不知道什么是虛函數(shù)，排除法可以完成

　　9：某進程在運行過程中需要等待從磁盤上讀入數(shù)據(jù)，此時進程的狀態(tài)將：

　　A: 從就緒變?yōu)檫\行 B:從運行變?yōu)榫途w

　　C: 從運行變?yōu)樽枞?D:從阻塞變?yōu)榫途w

　　C，解釋：I/O事件讓進程從running->waitting

　　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，解釋：沒啥好解釋的

　　11: n從1開始，每個操作可以選擇對n加1或者對n加倍。若想獲得整數(shù)2013，最少需要多少個操作。

　　A:18 B:24 C:21 D;不可能

　　A，解釋：數(shù)學(xué)方法->從 2013 倒推，奇數(shù) 減一，偶數(shù) 除2，編程實現(xiàn)->是一個明顯的bfs題目，編程實現(xiàn)為18,共享一下自己的bfs代碼：

#include <stdio.h>

#include <stdlib.h>

#define FINAL 2013

#define MAX 25

typedef struct num {

int d, time;

} num;

typedef struct queue {

int front, rear, count;

num data[10000000];

} queue;

void enQueue(queue *q, num d)

{

q->data[q->rear ++] = d;

q->count ++;

}

num deQueue(queue *q)

{

num res;

res = q->data[q->front ++];

q->count --;

return res;

}

int main(void)

{

int flag = 0;

num bt, one, two, s;

bt.d = 2;

bt.time = 1;

queue *q = (queue *)malloc(sizeof(queue));

q->front = q->rear = q->count = 0;

enQueue(q, bt);

while (q->count > 0) {

s = deQueue(q);

if (s.d == FINAL) {

flag = 1;

printf("%d\n", s.time);

break;

}

one.d = s.d + 1;

one.time = s.time + 1;

if (one.d <= FINAL && one.time <= MAX) {

enQueue(q, one);

}

two.d = s.d * 2;

two.time = s.time + 1;

if (two.d <= FINAL && two.time <= MAX) {

enQueue(q, two);

}

printf("%d\n", q->count);

}

if (flag == 0)

printf("不可能!\n");

return 0;

}

　　12：對于一個具有n個頂點的無向圖，若采用鄰接表數(shù)據(jù)結(jié)構(gòu)表示，則存放表頭節(jié)點的數(shù)組大小為：

　　A: n B: n+1 C: n-1 D:n+邊數(shù)

　　A，解釋：感覺沒啥好解釋的，n個頂點數(shù)組大小應(yīng)該就是n吧，如果非要從下標(biāo)從1開始，那就是n+1，蛋疼的題目，話說在ACM上寫bfs，dfs，最短路徑全是用鄰接矩陣，就誰會用鄰接表這么蛋疼的設(shè)計，又不是hash

　　13.考慮一個特殊的hash函數(shù)h，能將任一字符串hash成一個整數(shù)k，其概率p(k) = 2^(-k),k = 1,2,3,4,....對于一個未知大小的字符串集合S中的每一個元素取hash值所組成的集合為h(S).若h(s)中最大元素max h(s) =10,那么s的大小期望是

　　A：1024 B：512 C：5 D:10

　　我讀不懂題啊有沒有，我想選c

　　14.如下函數(shù)，在32bit系統(tǒng)foo(2^31-3)的值是：

　　Int foo(int x)

　　{

　　Return x&-x;

　　}

　　A： 0 B: 1 C:2 D:4

　　C,解釋：我只想說注意運算符優(yōu)先級，注意^是異或

　　15.對于順序存儲的線性數(shù)組，訪問節(jié)點和增加節(jié)點刪除節(jié)點的時間復(fù)雜度為：

　　A: O(n),O(n) B:O(n),O(1) C:O(1),O(n) D:O(n),O(n)

　　C，解釋：給定下標(biāo)，訪問為O(1)，增加和刪除節(jié)點涉及到移動操作為O(n)

　　16:在32為系統(tǒng)環(huán)境，編譯選項為4字節(jié)對齊，那么sizeof(A)和sizeof(B)是：

　　Struct A

　　{

　　int a;

　　short b;

　　int c;

　　char d;

　　};

　　Struct B

　　{

　　int a;

　　short b;

　　char c;

　　int d;

　　};

　　A: 16,16 B:13,12 C:16,12 D:11,16

　　C，解釋：字節(jié)對齊包含了每個變量自身對齊和復(fù)雜類型整體對齊。pragma pack參考鏈接：http://blog.csdn.net/wzy_1988/article/details/11834881

　　對于A：

　　int a自身對齊是4,pragma pack指定對齊也是4,因此其有效對齊為4,起始地址0x0000滿足0x0000 % 4 == 0

　　short b自身對齊是2,指定對齊是4,因此有效對齊為其最小值2,起始地址0x0004滿足0x0004 % 2 == 0

　　int c自身對齊是4,pragma pack指定對齊也是4,因此其有效對齊為4,起始地址0x0006不滿足0x0006 % 4 == 0,因此需要填充空字節(jié)，起始地址為0x0008

　　char d自身對齊是1,指定對齊是4,因此有效對齊為其最小值1,起始地址0x000C滿足0x000C % 1 == 0

　　結(jié)構(gòu)體還需要整體對齊，也就是結(jié)構(gòu)體成員最大有效對齊的倍數(shù)，0x000D不滿足 % 4 ==0, 需要需要補充3個字節(jié)，總字節(jié)數(shù)為16

　　對于B：

　　int a自身對齊是4,pragma pack指定對齊也是4,因此其有效對齊為4,起始地址0x0000滿足0x0000 % 4 == 0

　　short b自身對齊是2,指定對齊是4,因此有效對齊為其最小值2,起始地址0x0004滿足0x0004 % 2 == 0

　　char d自身對齊是1,指定對齊是4,因此有效對齊為其最小值1,起始地址0x0006滿足0x000C % 1 == 0

　　int c自身對齊是4,pragma pack指定對齊也是4,因此其有效對齊為4,起始地址0x0007不滿足 % 4 ==0,需要補充一個空字節(jié)，起始地址為0x0008

　　結(jié)構(gòu)體需要整體對齊，結(jié)構(gòu)體整體有效對齊是4,0x000C % 4 == 0,因此總字節(jié)為12

　　17.袋中有紅球，黃球，白球各一個，每次任意取一個放回，如此連續(xù)3次，則下列事件中概率是8/9的是：

　　A: 顏色全相同 B:顏色全不相同C:顏色不完全相同 D:顏色無紅色

　　C，解釋：(1)顏色全相同：C(1,3) / 27 = 1 / 9(2)顏色全不相同：3 * 2 * 1 / 27 = 2 / 9 (4)顏色無紅色: 2 * 2 * 2 / 27 = 8 / 27 (3)顏色不完全相同 = 1 - P(顏色完全相同) = 1 - 1 / 9 = 8 / 9

　　18.一個洗牌程序的功能是將n張牌的順序打亂，以下關(guān)于洗牌程序的功能定義說法最恰當(dāng)?shù)氖牵?/p>

　　A: 每張牌出現(xiàn)在n個位置上的概率相等

　　B: 每張牌出現(xiàn)在n個位置上的概率獨立

　　C: 任何連續(xù)位置上的兩張牌的內(nèi)容獨立

　　D: n張牌的任何兩個不同排列出現(xiàn)的概率相等

　　D，解釋：樂樂說選D，其實我覺得A也挺對的，這到題目我寫了一個測試洗牌的程序，但是自己測試問題很大，懷疑是隨機數(shù)獲取的問題，求大家?guī)兔χ更c：

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#define N 10

int arr[N] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

void shuffleArray()

{

int i, loc, tmp;

time_t t;

srand((unsigned int)time(&t));

// 洗牌算法

for (i = 0; i < N; i ++) {

loc = rand() % (i + 1);

tmp = arr[loc];

arr[loc] = arr[i];

arr[i] = tmp;

}

// 打印輸出

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

printf("%d ", arr[i]);

printf("\n");

}

int main(void)

{

int i, n;

while (scanf("%d", &n) != EOF) {

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

// 測試洗牌

shuffleArray();

}

return 0;

}

　　19.用兩種顏色去染排成一個圈的6個棋子，如果通過旋轉(zhuǎn)得到則只算一種，一共有多少種染色：

　　A: 10 B:11 C:14: D:15

　　不會，這么多概率題目啊，我去

　　20.遞歸式的先序遍歷一個n節(jié)點，深度為d的二叉樹，則需要�？臻g的大小為：

　　A: O(n) B:O(d) C:O(logn) D:(nlogn)

　　B，解釋：需要考慮最壞的情況，A和B我不確定啊，蛋疼

　　二、多選題

　　21.兩個線程運行在雙核機器上，每個線程主線程如下，線程1：x=1;r1=y;線程2：y=1;r2=x;

　　X和y是全局變量，初始為0。以下哪一個是r1和r2的可能值：

　　A: r1=1,r2=1

　　B: r1=1,r2=0

　　C:r1=0,r2=0

　　D:r1=0,r2=1

　　ABD，解釋：r1和r2不可能同時為0,當(dāng)一個有賦值時，必然完成了對另一個x或y的賦值

　　22.關(guān)于Linux系統(tǒng)的負(fù)載，以下表述正確的是：

　　A: 通過就緒和運行的進程數(shù)來反映

　　B: 通過TOP命令查看

　　C: 通過uptime查看

　　D: Load:2.5,1.3,1.1表示系統(tǒng)的負(fù)載壓力在逐漸變小

　　BC，解釋：ALINUX系統(tǒng)還需要包含處于waitting狀態(tài)的進程 D說明系統(tǒng)負(fù)載變大，load average分別是系統(tǒng)1分鐘，5分鐘，15分鐘的平均負(fù)載

　　23.關(guān)于排序算法的以下說法，錯誤的是：

　　A: 快速排序的平均時間復(fù)雜度O(nlogn),最壞O(N^2)

　　B:堆排序平均時間復(fù)雜度O(nlogn)，最壞O(nlogn)

　　C:冒泡排序平均時間復(fù)雜度O(n^2),最壞O(n^2)

　　D:歸并排序的平均時間復(fù)雜度O(nlogn),最壞O(n^2)

　　D，解釋：歸并排序最壞的時間復(fù)雜度也是O(nlogn)

　　24.假設(shè)函數(shù)rand_k會隨機返回一個【1，k】之間的隨機數(shù)(k>=2),并且每個證書出現(xiàn)的概率相等。目前有rand_7,通過調(diào)用rand_7()和四則運算符，并適當(dāng)增加邏輯判斷和循環(huán)控制邏輯，下列函數(shù)可以實現(xiàn)的有：

　　A:rand_3 B:rand_21 C:rand_23 D:rand_49

　　ABCD

　　填空和問答

　　25.某二叉樹的前序遍歷-+a*b-cd/ef，后續(xù)遍歷abcd-*+ef/-,問其中序遍歷序列為

　　扯淡啊，根據(jù)前序和后序沒法唯一確定中序好不好，我擦

　　26.某緩存系統(tǒng)采用LRU，緩存容量為4，并且初始為空，那么在順序訪問以下數(shù)據(jù)項的時候：1,5,1,3,5,2,4,1,2

　　出現(xiàn)緩存直接命中的次數(shù)為：()，最后緩存即將淘汰的是()

　　3,5

　　27.兩個較長的單鏈表a和b，為了找出節(jié)點node滿足node in a并且node in b。請設(shè)計空間使用盡量小的算法

　　求兩個鏈表的公共節(jié)點題目

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

typedef struct list {

int value;

struct list *next;

} list;

void addDataInList(list **root, int data)

{

list *pre, *current, *new;

current = *root;

pre = NULL;

while (current != NULL) {

pre = current;

current = current->next;

}

new = (list *)malloc(sizeof(list));

new->value = data;

new->next = NULL;

if (pre == NULL) { // 頭節(jié)點

*root = new;

} else {

pre->next = new;

}

void searchInList(list *first, int m, list *second, int n)

{

int i;

// 構(gòu)成Y的形狀

if (m > n) {

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

first = first->next;

} else {

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

second = second->next;

}

// 查找第一個公共節(jié)點

while (first != NULL && second != NULL && first->value != second->value) {

first = first->next;

second = second->next;

}

if (first == NULL && second == NULL)

printf("My God\n");

else

printf("%d\n", first->value);

}

int main(void)

{

int i, n, m, data;

list *first, *second;

while (scanf("%d %d", &m, &n) != EOF) {

// 構(gòu)造第一個鏈表

for (i = 0, first = NULL; i < m; i ++) {

scanf("%d", &data);

addDataInList(&first, data);

}

// 構(gòu)造第二個鏈表

for (i = 0, second = NULL; i < n; i ++) {

scanf("%d", &data);

addDataInList(&second, data);

}

// 第一個公共節(jié)點

searchInList(first, m, second, n);

}

return 0;

}

　　28.存儲數(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é)點的程序

　　#define N 5

　　int hash(int element){

　　return element*2654435761;

　　}

　　int shardingIndex(int a){

　　int p = hash(a);

　　_________________________; //這里是空格

　　return p;

　　}

　　p = p % N;解釋：感覺沒啥好解釋的，基本的散列函數(shù)

　　29.宿舍內(nèi)5個同學(xué)一起玩對戰(zhàn)游戲，每場比賽有一些人作為紅方，一些人作為藍方，請問至少需要多少場比賽，才能使得任意兩個人之間有一場紅方對藍方和藍方對紅方的比賽

　　4,被n多人指點之后的結(jié)果