1.平均速度最快的排序演算法是______。
Shell排序
快速排序
氣泡排序
插入排序
2014-03-29 18:36:02
2.某服務程序的QPS(沒秒處理的請求個數)較低,在空閒時間RT(響應時間)比較合理。在壓力下CPU佔用率20%左右。那麼可能存在的問題是______。
該程序的某個處理過程的程式碼需要提高速度
該程序依賴的服務可能存在效能瓶頸
該程序需要增加執行緒數
該程序可能有一個鎖的粒度太大
2014-03-29 18:36:16
3.無鎖化程式設計有哪些常見方法?______ 。
針對計數器,可以使用原子加
只有一個生產者和一個消費者,那麼就可以做到免鎖訪問環形緩衝區(Ring Buffer)
RCU(Read-Copy-Update),新舊副本切換機制,對於舊副本可以採用延遲釋放的做法
CAS(Compare-and-Swap),如無鎖棧,無鎖佇列等待
2014-03-29 18:37:00
2014-03-29 18:37:00
4.假設棧S和佇列Q的初始狀態為空,元素a、b、c、d、e、f依次通過S和Q,即每一個元素必須先進棧,之後再出棧進入佇列。若這6個元素出隊的順序是b、d、c、f、e、a,則棧S的容量至少應該為______。
3
4
5
6
2014-03-29 18:37:11
5.設棧S初始狀態為空。元素a,b,c,d,e,f依次通過棧S,若出棧的順序為c,f,e,d,b,a,則棧S的容量至少應該為______ 。
3
4
5
6
2014-03-29 18:37:25
6.一個單向連結串列,頭指標和尾指標分別為p,q,以下_____項操作的複雜度受佇列長度的影響?
刪除頭部元素
刪除尾部元素
頭部元素之前插入一個元素
尾部元素之後插入一個元素
2014-03-29 18:37:33
7.集合A={1,2,3},A上的關係R={(1,1),(2,2),(2,3),(3,2),(3,3)},則R不具備 。
自反性
傳遞性
對稱性
反對稱性
2014-03-29 18:37:44
8.件裝置的壽命通常符合指數分佈,即無記憶性,也就是如果一個裝置當前正常工作,那麼剩餘預期壽命和已經工作的時間無關。假定某種裝置1000臺,在一年之內壞掉500臺(無維修),那麼在有維修(裝置壞掉立刻換新的)的情況下,一年之內需要換______臺該裝置。
400臺
500臺
753臺
1000臺
2014-03-29 18:37:53
9.一個int64_t型別的變數轉換成一個double型別的變數,可能存在的問題是______。
精度損失
大小溢位
轉換失敗
無以上問題
2014-03-29 18:38:04
10.標準unix環境下,一個擁有3個執行緒的程序呼叫fork產生的子程序中,其執行緒個數為______。
1
2
3
4
2014-03-29 18:38:15
11.你有一個3X3X3的立方體。你現在在正面左上的頂點,需要移動到對角線的背面右下的頂點中。每次移動不限距離,但只能從前至後、從左至右、從上至下運動,即不允許斜向或後退。有______種方法。
9
90
180
1680
2014-03-29 18:38:28
12 兩個N*N的矩陣A和B,想要在PC上按矩陣乘法基本演算法程式設計實現計算A*B。假設N較大,本機記憶體也很大,可以存下A、B和結果矩陣。那麼,為了計算速度,A和B在記憶體中應該採用的儲存方法是______。(按行存指先儲存第一行,再第二行,直到最後一行;按列存指先儲存第一列,再第二列,直到最後一列)
A按行存,B按行存
A按行存,B按列存
A按列存,B按行存
A按列存,B按列存
2014-03-29 18:38:37
13.知一個遞迴演算法的演算法複雜度計算公式為T(n)=T(n/2)+n,則T(n)的演算法複雜度為____。
O(n)
O(logn) O(n2)
O(nlogn)
2014-03-29 18:38:53
14.慮如下程式存在的問題是__________。
class A {
public:
A(B* b) : _b(b) {}
~A() { b;}
private:
B* _b;
};
int main()
{
B b;
A(&b);
return 0;
}
double free 重複釋放
stack free 堆疊釋放
memory leak 記憶體洩露
無以上問題
2014-03-29 18:39:01
2014-03-29 18:39:01
15.21、26、65、99、10、35、18、77分成若干組,要求每組中任意兩個數都互質,至少要分成______組。
3
4
2
5
2014-03-29 18:39:09
16.設某虛擬儲存系統的實體記憶體只有3個頁(page),當程序A訪問虛擬頁的序列依次是1, 2, 3, 4, 2, 7, 5, 3, 5, 7, 4, 3, 當頁面淘汰演算法為先進先出(FIFO)且記憶體在剛開始為空,那程序A遭遇的頁面失效次數為_____。
7次
8次
9次
10次
2014-03-29 18:39:18
17.於一個二元搜尋樹,以下遍歷方式中,______可以得到一個遞增數列。 先序遍歷
中序遍歷
後序遍歷
層次遍歷
2014-03-29 18:39:25
18. 兩個N*N的矩陣A和B,想要在PC上按矩陣乘法基本演算法程式設計實現計算A*B。假設N較大,本機記憶體也很大,可以存下A、B和結果矩陣。那麼,為了計算速度,A和B在記憶體中應該如何儲存(按行存指先儲存第一行,再第二行,直到最後一行;按列存指先儲存第一列,再第二列,直到最後一列) A按行存,B按行存。
A按行存,B按列存。
A按列存,B按行存。
A按列存,B按列存。
2014-03-29 18:39:31
19.個容器類資料結構,讀寫平均,使用鎖機制保證執行緒安全。如果要綜合提高該資料結構的訪問效能,最好的辦法是______。
只對寫操作加鎖,不對讀操作加鎖
讀操作不加鎖,採用copyOnWrite的方式實現寫操作
分割槽段加鎖
無法做到
2014-03-29 18:39:40
20.設炮彈發射3次,射中目標區域的概率是0.95,那麼,發射1次射中目標區域的概率約是 。
0.32
0.63 0.50
0.73
2014-03-29 18:39:47
21正則表示式 2[0-4]d|25[0-5]|[01]?dd?$ 能匹配以下哪個表示式 ?
255
256
2
25a
2014-03-29 18:39:54
22.叉樹的廣度優先遍歷序列為A B C D E F G H I,已知A是C的父結點,D 是G 的父結點,F 是I 的父結點,樹中所有結點的最大深度為3(根結點深度設為0),可知E的父結點可能是 _____。 A
B
C
D
F
2014-03-29 18:40:02
23.服務程序的QPS(沒秒處理的請求個數)較低,在空閒時間RT(響應時間)比較合理。在壓力下CPU佔用率20%左右。那麼可能存在的問題是______。
該程序的某個處理過程的程式碼需要提高速度
該程序依賴的服務可能存在效能瓶頸
該程序需要增加執行緒數
該程序可能有一個鎖的粒度太大
2014-03-29 18:40:09
24.無鎖化程式設計有哪些常見方法?______ 。
針對計數器,可以使用原子加
只有一個生產者和一個消費者,那麼就可以做到免鎖訪問環形緩衝區(Ring Buffer)
RCU(Read-Copy-Update),新舊副本切換機制,對於舊副本可以採用延遲釋放的做法
CAS(Compare-and-Swap),如無鎖棧,無鎖佇列等待
2014-03-29 19:18:33
25.有個學校的15個女生一直3個一群上學。請問該如何安排才能使這些女生每週7天每天都和兩個不同的同伴結伴同行呢?例如:用A到O來標識這些女孩,7天A正好和B到O這14個女孩各同行一次。而B到O每個人和都和其他14個女孩各同行一次。
26.含有n個關鍵字的`B樹上查詢時,從根節點到關鍵位元組點的路徑上涉及的節點數不超過__________。
2014-03-29 19:18:59
27.下是一段基於連結串列的棧的實現程式碼,請補充空白處的程式碼。
class Stack {
Node top;
Object pop() {
if (top != null) {
Object item = ;
(1) top=;
return item;
}
return null;
}
void push(Object item) {
Node t = new Node(item);
(2)
top = t;
}
}
class Node{
Node next;
Object data;
public Node(Object item){
data = item;
}
}
(1) top=
(2)=top
2014-03-29 19:19:09
選做題(注:阿里有大量JAVA研發工程師需求;選作以下題目有機會增加該方向面試機會)
天貓雙十一有個積分換墨盒的活動,總共有50萬臺天貓魔盒(box),每個使用者(user)可以用99個天貓積分(point)兌換一臺魔盒,且每人限換一臺。 請設計一套java介面並實現下單(order)邏輯。
參考(但不侷限於)下面的下單邏輯:
1、建立訂單
2、扣減使用者積分
3、扣減魔盒庫存
4、下單成功
同時請回答:
1、資料庫表結構如何設計,有哪些表,分別有什麼作用?
2、下單過程中哪些地方可能成為瓶頸?如何解決或改善?
3、是否會用到資料庫事務,哪些地方會用到?如果不用資料庫事務,如何保證資料的一致性?
java介面那個你看書上的定義,安要求定義函式
函式明用英文就可以了。不過介面這個不一定對
資料表格三張,魔盒表,使用者表,和魔盒與使用者關係表
瓶頸會存在與對各個表格儲存過程中。比如魔盒數量修改,使用者分數修改,使用者兌換魔盒記錄等
改善的一個方法就是使用者建立頂點時先讀取使用者和魔盒關係表,如果有記錄,則不必讀取後兩張表,儘量節約時間愛你
儘量節約時間
其他方法也可以考慮,可以在表格設計和處理順序上考慮下
需要資料庫事物,只要用在資料表格的資料修改中,比如修改積分,魔盒數量等,用資料庫事物是做安全的保證資料一致性的方法。不用其實也可以,需要在程式碼中體現。但不利於以後的維護等
基本是些意思嗎,具體的記不清了
2014-03-29 19:19:23
29.長度為100的環形雙向連結串列,A指標順時針方向每次走3步,B指標逆時針方向每次走5步,每次走完判斷是否相遇,初始狀態B在A逆時針方向相距20,走100次,AB指標能相遇幾次?
30.下C語言程式片段用於估測CPU的cache引數(容量,延遲等): #define MAX_SIZE (64*1024*1024L)
#define STRIDE (128)
#define STEP (4096)
#define REPEAT (1000*1000L)
double t[MAX_SIZE/STEP];
int d[MAX_SIZE/sizeof(int)];
t[0] = 0;
long foot_print;
for (foot_print = STEP; foot_print < MAX_SIZE; foot_print += STEP) {
long i;
for (i = 0; i < foot_print; i += STRIDE)
{
long next = (i + STRIDE) % foot_print;
d[i/sizeof(int)] = next/sizeof(int);
}
int m = 0;
double t1 = get_time_second();
for (i = 0; i < REPEAT; ++i)
{
; // **
}
double t2 = get_time_second();
t[foot_print/STEP] = t2 t1;
printf(“%dt”, x); // avoid compiler optimization
}
// record t[] ?
假設CPU具有L1/L2/L3三層cache,cache line長度小於128B,硬體預取已經關閉。
請補全標記**的行,完成其功能;