1. 單選題
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的整數
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:看不清
9:某程序在執行過程中需要等待從磁碟上讀入資料,此時程序的狀態將:
A: 從就緒變為執行 B:從執行變為就緒
C: 從執行變為阻塞 D:從阻塞變為就緒
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!)
11: n從1開始,每個操作可以選擇對n加1或者對n加倍。若想獲得整數2013,最少需要多少個操作。
A:18 B:24 C:21 D;不可能
12:對於一個具有n個頂點的無向圖,若採用鄰接表資料結構表示,則存放表頭節點的陣列大小為:
A: n B: n+1 C: n-1 D:n+邊數
13:不全
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(n),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 c;};
A: 16,16 B:13,12 C:16,12 D:11,16
17:袋中有紅球,黃球,白球各一個,每次任意取一個放回,如此連續3次,則下列事件中概率是8/9的是:
A: 顏色全相同 B:顏色全不相同C:顏色全相同D:顏色無紅色
18:一個洗牌程式的功能是將n張牌的順序打亂,以下關於洗牌程式的功能定義說法最恰當的是:
A: 每張牌出現在n個位置上的概率相等
B: 每張牌出現在n個位置上的概率獨立
C: 任何連續位置上的兩張牌的內容獨立
D: n張牌的任何兩個不同排列出現的概率相等
19:用兩種顏色去染排成一個圈的6個棋子,如果通過旋轉得到則只算一種,一共有多少種染色:
A: 10 B:11 C:14: D:15
20:遞迴式的先序遍歷一個n節點,深度為d的二元樹,則需要棧空間的大小為:
A: O(n) B:O(d) C:O(logn) D:(nlogn)
第二部分:多選
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
22.關於Linux系統的負載,以下表述正確的是:
A: 通過就緒和執行的程序數來反映
B: 通過TOP命令檢視
C: 通過uptime檢視
D: Load:2.5,1.3,1.1表示系統的負載壓力在逐漸變小
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_49
3.(6分)兩個較長的單向連結串列a和b,為了找出及誒單noed滿足node in a
並且node in b。請設計空間使用盡量小的演算法(用c/c++,java 或者虛擬碼)
答案網上找的
我們定義節點的距離為節點到連結串列開始所經過的'節點數。如果兩個連結串列長度相同,則相交節點其在兩個連結串列上的距離一定相等。對於長度不同的兩個連結串列,我們可以採用對齊的方式,使其向長度短的連結串列對齊。這樣就可以應用上面的思路。具體演算法如下:
struct node
{
int v;
node *next;
};
/*
返回連結串列的長度
連結串列為空 返回0
*/
size_t listLen(node * p)
{
size_t num = 0;
while (p!=NULL)
{
num++;
p = p->next;
}
return num;
}
// 如果找到了 則返回指標 指向公共節點
// 如果不存在 則返回空指標
node * findFirstCommenNode(node * pheada, node * pheadb)
{
size_t lenA = listLen(pheada);
size_t lenB = listLen(pheadb);
node * plistA = pheada;
node * plistB = pheadb;
//調整長度
//plistA 指向較長的一個
if (lenA < lenB)
{
plistB = pheada;
plistA = pheadb;
size_t t = lenA;
lenA = lenB;
lenB = t;
}
while(lenA > lenB)
{
plistA = plistA->next;
--lenA;
}
//一樣長了
//尋找公共節點
while (plistA!=NULL && plistA != plistB)
{
plistA = plistA->next;
plistB = plistB->next;
}
return plistA;
}
演算法的空間複雜度O(1),時間複雜度O(m+n),效果不錯吧。
2、當儲存資料量超出單節點資料管理能力的時候,可以採用的辦法有資料庫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;
}
3、(8分)宿舍內5個同學一起玩對戰遊戲。每場比賽有一些人作為紅方,另一些人作為藍方。請問至少需要多少場比賽,才能使任意兩個人之間有一場紅方對藍方和藍方對紅方的比賽?
4、一個有10億條記錄的文字檔案,已按照關鍵字排好序儲存。請設計演算法,可以快速的從檔案中查詢指字關鍵字的記錄