阿里校招筆試題目

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

相關推薦

2014年阿里校招筆試題目

　　前言

2014年阿里校招筆試題目

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

　　題目

　　一、單選題

　　1.假設把整數關鍵碼K散列到N個槽列表，以下哪些散列函數是好的散列函數

　　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的整數

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

　　2.下面排序算法中，初始數據集的排列順序對算法的性能無影響的是：

　　A: 堆排序 B：插入排序

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

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

　　3. 下面說法錯誤的是：

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

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

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

　　D:馮諾依曼體系結構的主要特征是存儲程序的工作方式

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

　　4. 不屬于馮諾依曼體系結構必要組成部分是：

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

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

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

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

　　C，不解釋

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

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

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

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

　　A：static成員變量在對象構造時候生成

　　B: static成員函數在對象成員函數中無法調用

　　C: 虛成員函數不可能是static成員函數

　　D: static成員函數不能訪問static成員變量

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

　　9：某進程在運行過程中需要等待從磁盤上讀入數據，此時進程的狀態將：

　　A: 從就緒變為運行 B:從運行變為就緒

　　C: 從運行變為阻塞 D:從阻塞變為就緒

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

　　10：下面算法的時間復雜度為：

　　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加倍。若想獲得整數2013，最少需要多少個操作。

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

　　A，解釋：數學方法->從 2013 倒推，奇數減一，偶數除2，編程實現->是一個明顯的bfs題目，編程實現為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個頂點的無向圖，若采用鄰接表數據結構表示，則存放表頭節點的數組大小為：

　　A: n B: n+1 C: n-1 D:n+邊數

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

　　13.考慮一個特殊的hash函數h，能將任一字符串hash成一個整數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.如下函數，在32bit系統foo(2^31-3)的值是：

　　Int foo(int x)

　　{

　　Return x&-x;

　　}

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

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

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

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

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

　　16:在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 d;

　　};

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

　　C，解釋：字節對齊包含了每個變量自身對齊和復雜類型整體對齊。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,因此需要填充空字節，起始地址為0x0008

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

　　結構體還需要整體對齊，也就是結構體成員最大有效對齊的倍數，0x000D不滿足 % 4 ==0, 需要需要補充3個字節，總字節數為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,需要補充一個空字節，起始地址為0x0008

　　結構體需要整體對齊，結構體整體有效對齊是4,0x000C % 4 == 0,因此總字節為12

　　17.袋中有紅球，黃球，白球各一個，每次任意取一個放回，如此連續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張牌的順序打亂，以下關于洗牌程序的功能定義說法最恰當的是：

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

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

　　C: 任何連續位置上的兩張牌的內容獨立

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

　　D，解釋：樂樂說選D，其實我覺得A也挺對的，這到題目我寫了一個測試洗牌的程序，但是自己測試問題很大，懷疑是隨機數獲取的問題，求大家幫忙指點：

#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個棋子，如果通過旋轉得到則只算一種，一共有多少種染色：

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

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

　　20.遞歸式的先序遍歷一個n節點，深度為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,當一個有賦值時，必然完成了對另一個x或y的賦值

　　22.關于Linux系統的負載，以下表述正確的是：

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

　　B: 通過TOP命令查看

　　C: 通過uptime查看

　　D: Load:2.5,1.3,1.1表示系統的負載壓力在逐漸變小

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

　　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)

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

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

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

　　ABCD

　　填空和問答

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

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

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

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

　　3,5

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

　　求兩個鏈表的公共節點題目

#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) { // 頭節點

*root = new;

} else {

pre->next = new;

}

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

{

int i;

// 構成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;

}

// 查找第一個公共節點

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) {

// 構造第一個鏈表

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

scanf("%d", &data);

addDataInList(&first, data);

}

// 構造第二個鏈表

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

scanf("%d", &data);

addDataInList(&second, data);

}

// 第一個公共節點

searchInList(first, m, second, n);

}

return 0;

}

　　28.存儲數據量超出單節點數據管理能力的時候，可以采用的辦法有數據庫sharding的解決方案，也就是按照一定的規律把數據分散存儲在多個數據管理節點N中(節點編號為0,1,2，，，，N-1)。假設存儲的數據時a 請完成為數據a計算存儲節點的程序

　　#define N 5

　　int hash(int element){

　　return element*2654435761;

　　}

　　int shardingIndex(int a){

　　int p = hash(a);

　　_________________________; //這里是空格

　　return p;

　　}

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

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

　　4,被n多人指點之后的結果

【阿里校招筆試題目】相關文章：