單選題
1. 已知一棵二叉樹，如果先序遍歷的節點順序是：ADCEFGHB，中序遍歷是：CDFEGHAB，則後序遍歷結果爲：()
A. CFHGEBD
B. CDFEGHBA
C. FGHCDEBA
D. CFHGEDBA
2. 初始序列爲1 8 6 2 5 4 7 3一組數採用堆排序，當建堆(小根堆)完畢時，堆所對應的二叉樹中序遍歷序列爲：()
A. 8 3 2 5 1 6 4 7
B. 3 2 8 5 1 4 6 7
C. 3 8 2 5 1 6 7 4
D. 8 2 3 5 1 4 7 6
3. 當n=5時，下列函數的返回值是：()
int foo(int n)
{
if(n<2)returnn;
returnfoo(n-1)+foo(n-2);
}
A. 5
B. 7
C. 8
D. 10
4. S市A，B共有兩個區，人口比例爲3：5，據歷史統計A的犯罪率爲0.01%，B區爲0.015%，現有一起新案件發生在S市，那麼案件發生在A區的可能性有多大?( )
A. 37.5%
B. 32.5%
C. 28.6%
D. 26.1%
5. 靜態變量通常存儲在進程哪個區?()
A. 棧區
B. 堆區
C. 全局區
D. 代碼區
6. 查詢性能()
A. 在Name字段上添加主鍵
B. 在Name字段上添加索引
C. 在Age字段上添加主鍵
D. 在Age字段上添加索引
7. IP位址是一個( )類IP位址。
A. A
B. B
C. C
D. D
8. 下推自動識別機的語言是：()
A. 0型語言
B. 1型語言
C. 2型語言
D. 3型語言
9. 下列程序的輸出是：()
#define add(a+b) a+b
int main()
{
printf(“%d”,5*add(3+4));
return 0;
}
A. 23
B. 35
C. 16
D. 19
10. 瀏覽器訪問某頁面，HTTP協議返回狀態碼爲403時表示：()
A. 找不到該頁面
B. 禁止訪問
C. 內部服務器訪問
D. 服務器繁忙
11. 如果某系統15*4=112成立，則系統採用的是()進制。
A. 6
B. 7
C. 8
D. 9
12. 某段文字中各個字母出現的頻率分別是{a:4，b:3，o:12，h:7，i:10}，
使用哈夫曼編碼，則哪種是可能的編碼：()
A. a(000) b(001) h(01) i(10) o(11)
B. a(0000) b(0001) h(001) o(01) i(1)
C. a(000) b(001) h(01) i(10) o(00)
D. a(0000) b(0001) h(001) o(000) i(1)
13. 對於派生類的構造函數，在定義對象時構造函數的執行順序爲?()
1：成員對象的構造函數
2：基類的構造函數
3：派生類本身的構造函數
A. 123
B. 231
C. 321
D. 213
14. 如何減少換頁錯誤?()
A. 進程傾向於佔用CPU
B. 訪問局部性(locality of reference)滿足進程要求
C. 進程傾向於佔用I/O
D. 使用基於最短剩餘時間(shortest remaining time)的調度機制
15. 遞歸函數最終會結束，那麼這個函數一定?()
A. 進程傾向於佔用CPU
B. 有一個分支不調用自身
C. 使用了全局變量或者使用了一個或多個參數
D. 沒有循環調用
16. 編譯過程中，語法分析器的任務是()
A. 分析單詞是怎樣構成的
B. 分析單詞串是如何構成語言和說明的
C. 分析語句和說明是如何構成程序的
D. 分析程序的結構
17. 進程進入等待狀態有哪幾種方式?()
A. CPU調度給優先級更高的線程
B. 阻塞的線程獲得資源或者信號
C. 在時間片輪轉的`情況下，如果時間片到了
D. 獲得spinlock未果
單選題答案：D A A C C
B B C D B
A A D D D
B D
多選題
1. 下列哪兩個數據結構，同時具有較高的查找和刪除性能?
A. 有序數組
B. 有序鏈表
C. C. AVL樹
D. D. Hash表
2. 下列排序算法中，哪些時間複雜度不會超過nlogn?( )
A. 快速排序
B. 堆排序
C. 歸併排序
D. 冒泡排序
3. Unix系統中，哪些可以用於進程間的通信?( )
A. Socket
B. 共享內存
C. 消息隊列
D. 信號量
4. TCP和IP分別對應了OSI中的哪幾層?( )
A. Application layer
B. Presentation layer
C. Transport layer
D. Network layer
5. 一個棧的入棧序列是A,B,C,D,E，則棧的不可能的輸出序列是?()
A. EDCBA
B. DECBA
C. DCEAB
D. ABCDE
6. 同一進程下的線程可以共享以下?()
A. Stack
B. Data section
C. Register set
D. File fd
7. 同步機制應該遵循哪些基本準則?()
A. 空閒讓進
B. 忙則等待
C. 有限等待
D. 讓權等待
8. 設計模式中，屬於結構型模式的有哪些?()
A. 狀態模式
B. 裝飾模式
C. 代理模式
D. 觀察者模式
正確答案：CD CD BCD CD BD
BD ABCD BC
簡答題
1. 請設計一個排隊系統，能夠讓每個進入隊伍的用戶都能看到自己在隊列中所處的位置和變化，隊伍可能隨時有人加入和退出;當有人退出影響到用戶的位置排名時需要及時反饋到用戶。
答案：一個數組存儲隊列，數組的序號是加入隊列的人的順序號，數組的值是這個人的存在狀態，最新加入放在數組尾部。如果退出隊列，或者排隊到這個人，則置爲0，其他爲1。同時用一個整形數字存儲當前已經排隊到的序列號。想要了解用戶的位置，只需從已經排隊到的序列號遍歷一遍數組即可，時間複雜度O(n)。
2. A，B兩個整數集合，設計一個算法求他們的交集，儘可能的高效。
答案：如果只考慮高效，hash表，把兩個集合放進hash表裏遍歷一遍即可，O(m+n)如果考慮hash表太浪費空間，使用位存儲，遍歷位即可，時間複雜度同上。