一、選擇題
1、資料庫表設計最合理的是
A.學生{id,name,age} ,學科{id,name} 分數{學生id，學科id，分數}
B.學生{id,name,age} ,分數{學生id，學科名稱，分數}
C.分數{學生姓名，學科名稱，分數}
D.學科{id,name},分數{學生姓名，學科id，分數}
解析：C,D肯定不對，B中将學科獨立成一個表結構會更加清晰，一個實體對應一張表。
2、在資料庫系統中，産生不一緻的根本原因是
A．資料存儲量太大 B．沒有嚴格保護資料 C．未對資料進行完整性控制 D．資料備援
解析：基本概念
3、15L和27L兩個杯子可以精确地裝（）L水？
A. 53 B. 25 C. 33 D. 52
解析：設A杯15L，B杯27L，用A打兩次水，将B裝滿，最後A還剩3L，将3L水裝至B，還是用A打兩次水，将B裝滿,最後A中有6L，6+27=33.9,12,15..同理
4、考慮左遞歸文法 S->Aa|b、 A ->Ac | Sd |e，消除左遞歸後應該為（A）
A. B. C . D.
S->Aa|b S->Ab|a S->Aa|b S->Aa|b
A->bdA'|A' A->bdA'|A' A->cdA'|A' A->bdA'|A'
A->cA'|adA'|ε A->cA'|adA'|ε A->bA'|adA'|ε A->caA'|dA'|ε
解析：e為空集，消除左遞歸，即消除 有A->A*的情況，消除做遞歸的一般形式為
U = Ux1 | U x2 |y1|y2
U = y1U' |y2 U'
U' = x1U'|x2U'|e
A = Ac|Aad|bd|e
A =bdA'|A'
A'= cA'|adA'|e
5、下列排序算法中，初始資料集合對排序性能無影響的是（）
A．插入排序 B．堆排序 C．冒泡排序 D．快速排序
解析：插入和冒泡再原資料有序的情況下會出現性能的極端情況（O(n)，O(n^2)）.快速排序在對一個基本有序或已排序的數組做反向排序時，每次patition的操作，大部分元素都跑到了一遍，時間複雜度會退化到O(n^2)。
6、二分查找在一個有序序列中的時間複雜度為（）
A.O(N) B.O(logN) C.O(N*N) D.O(N*logN)
7、路由器工作在網絡模型中的哪一層（）？
A.資料鍊路層 B.實體層 C.網絡層 D.應用層
解析：相關實體硬體和OSI協定層次的對應關系：
實體層 光纖、同軸電纜 雙絞線 中繼器和集線器
資料鍊路層 網橋、交換機、網卡
網絡層 路由器
傳輸層 網關
8、對于滿足SQL92标準的SQL語句：select foo,count(foo) from pokes where foo>10 group by foo having count(*)>5 order by foo，其執行順序應該是（）
A.FROM ->WHERE -> GROUP BY -> HAVING -> SELECT ->ORDER BY
B.FROM ->GROUP BY ->WHERE -> HAVING -> SELECT ->ORDER BY
C.FROM ->WHERE -> GROUP BY -> HAVING ->ORDER -> BYSELECT
D.FROM ->WHERE ->ORDER BY -> GROUP BY -> HAVING -> SELECT
解析：SQL Select語句完整的執行順序：
1）from子句組裝來自不同資料源的資料；
2）where子句基于指定的條件對記錄行進行篩選；
3）group by子句将資料劃分為多個分組；
4）使用聚集函數進行計算；
5）使用having子句篩選分組；
6）計算所有的表達式；
7）使用order by對結果集進行排序。
隻有select選出了相應的表 才能對其排序，删除之類的操作，是以 合理的答案應該為 from --where-- group by-- having --select-- order by
９．使用深度優先算法周遊下面的圖，周遊的順序為（）
Ａ．ＡＢＣＤＥＦＧＨＩ Ｂ．ＢＣＥＨＩＦＧＤＡ Ｃ．ＡＢＣＥＦＨＩＧＤ Ｄ．ＨＩＦＥＧＢＣＤＡ
無答案
解析：
用鄰接表的方式來表示圖
A->B->C->D
B->
C->
D->E->F->G
E->
F->H->I
G->
H->
I->
圖的深度優先搜尋是沿着樹的深度周遊樹的節點，盡可能深的搜尋樹的分支。當節點v的所有邊都己被探尋過，搜尋将回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點并重複以上過程，整個程序反複進行直到所有節點都被通路為止。
是以正确的過程是 A->B->C->D->E->F->H->I->G
10．UNIX系統中，目錄結構采用
Ａ．單級目錄結構 Ｂ．二級目錄結構 Ｃ．單純樹形目錄結構 Ｄ．帶連結樹形目錄結構
11．請問下面的程式一共輸出多少個“-”？
#include <stdio.h> #include <sys/types.h> #include <unistd.h> int main(void) { int i; for(i=0; i<2; i++) { fork(); //複制父程序，調用一次，傳回兩次 printf("-"); //緩沖區資料 } return 0; } A.2個 B .4個 C.6個 D.8個
解析:
關鍵1.fock之後的代碼父程序和子程序都會運作；
關鍵2.printf(“-”);語句有buffer，是以，對于上述程式，printf(“-”);把“-”放到了緩存中，并沒有真正的輸出，在fork的時候，緩存被複制到了子程序空間，是以，就多了兩個，就成了8個，而不是6個。
12.請問下面的程式一共輸出多少個“-”？
#include <stdio.h> #include <sys/types.h> #include <unistd.h> int main(void) { int i; for(i=0; i<2; i++) { fork(); //複制父程序，調用一次，傳回兩次 printf("-\n"); //緩沖區資料 } return 0; } A.2個 B .4個 C.6個 D.8個
解析：printf("-\n")重新整理了緩沖區
13.避免死鎖的一個著名的算法是（）
A.先入現出法 B.銀行家算法 C.優先級算法 D.資源按需配置設定法
14.怎麼了解配置設定延遲（dispatch lantency）
A.配置設定器停止一個程序到開啟另一個程序的時間 B. 處理器将一個檔案寫入磁盤的時間
C. 所有處理器占用的時間 D.以上都不對
解析：分派程式停止某一個處理元使用中央處理器，并分派中央處理器給另一個處理元所需的時間，稱為分派時間（Dispatch Latency）。
15.以下哪一個不是程序的基本狀态？
A. 阻塞态 B.執行态 C.就緒态 D. 完成态
解析：程序狀态轉移圖
1：就緒->執行， 目前運作程序阻塞，排程程式選一個優先權最高的程序占有處理機；
2：執行->就緒， 目前運作程序時間片用完；
3：執行->阻塞，目前運作程序等待鍵盤輸入，進入了睡眠狀态。
4：阻塞->就緒，I/O操作完成，被中斷處理程式喚醒。
16.假定我們有3個程式，每個程式花費80%的時間進行I/O，20%的時間使用CPU。每個程式啟動時間和其需要使用進行計算的分鐘數如下，不考慮程序切換時間。
程式編号 啟動時間 需要CPU時間（分鐘）
1 00:00 3.5
2 00:10 2
3 00:15 1.5
請問在多線程/程序環境下，系統的總響應時間是（）
A.22.5 B.23.5 C.24.5 D.25.5
解答：多道程式設計時CPU使用率的求法：
隻有一個程序的時候，CPU使用率肯定是20%。
兩個程序的時候：CPu使用率是：20% + (1-20%)*20% = 36%
三個程序是：36% + (1-36%)*20% = 48.8%
其它的依次類推。
0-10分鐘的時候，隻有一個程序1在運作。
單程序CPU占有率是20%，是以這10分鐘内，程序1消耗了2分鐘的CPU。程序2是0，程序3也是0
然後在10-15分鐘内，有兩個程序在運作（1和2），雙程序的CPU使用率是36%，
是以，這五分鐘内，CPU一共利用了1.8分鐘，平均分給每個程序，是0.9分鐘。
此時，程序1已經占用了CPU 2.9分鐘，還需要0.6分鐘，這時候有三個程序在運作，所有總的CPU時間需要1.8分鐘。
三程序的CPU使用率是48.8%，是以總共需要1.8/0.488=3.69分鐘。這時，程序1已經3.5分鐘的CPu利用時間利用完了。
此時還剩下2和3号程序在運作。
2号程序還需要0.5分鐘，是以0.5×2/0.36=2.78，此時2号程序的2分鐘CPU時間也利用完了。
3号程序還需要0.4分鐘的CPU利用時間。0.4/0.2 = 2
參考 - 作業系統多道程式設計
17.在所有非搶占CPU排程算法中，系統平均響應時間最優的是（）
A.實時排程算法 B.短任務優先算法 C.時間片輪轉算法 D.先來先服務算法
18.什麼是記憶體抖動（Thrashing）?
A.非常頻繁的換頁活動 B.非常高的CPU執行活動 C.一個極長的執行程序 D.一個極大的虛拟記憶體交換活動
解析：頁面的頻繁更換，導緻整個系統效率急劇下降，這個現象稱為記憶體抖動。
抖動一般是記憶體配置設定算法不好，記憶體太小引或者程式的算法不佳引起的頁面頻繁從記憶體調入調。
19. Belay's Anomaly 出現在哪裡（）
A.記憶體管理算法 B.記憶體換頁算法 C.預防死鎖算法 D.磁盤排程算法
解析：Belady異常（Belady Anomaly）：有些情況下，頁故障率（缺頁率）可能會随着所配置設定的幀數的增加而增加。
原因：因為使用了不恰當的演算法(如FIFO)，雖然空間夠多(frame夠多)，但因為總是選到不應該被swap的page，是以反而讓page fault次數變多了。
20.下面的生産者消費者程式中，哪個不會出現死鎖，并且開銷最少？
解析：代碼太多，不做 - -
二、填空題
21.将下圖進行拓撲排序後，對應的序列為 ABCFD
解析：拓撲排序的定義:對一個有向無環圖(Directed Acyclic Graph簡稱DAG)G進行拓撲排序，是将G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若<u，v> ∈E(G)，則u線上性序列中出現在v之前。
22.下面的函數使用二分查找算法，對已按升序排序的數組傳回所要查找的數值的資料位置，請填寫缺少的兩句語句：
int* BinarySearch(int* arrayAddress, int arrayLength, int valueToSearch) { int head = 0 ; int tail = arrayLength - 1; while(head < tail) { mid = (head + tail)/2; if(arrayAddress[mid] > valueToSeatcj) tail = mid - 1; else head = mid + 1; } if(tail < arrayLength && arrayAddress[tail] == valueToSearch) return &arrayAddress[tail]; else return NULL; } tail = mid -1 ;
head = mid + 1;
23.一個有N個正數元素的一維數組（A[0], A[1], A[2]...,A[N-1]）, 求連續子數組和的最大值。
int max(int a,int b) int MaxSum(int *A, int length) { int nStart = A[0]; int nAll = A[0]; for(int i=1; i<lenght; i++) { nStart = max(nAll + A[i], 0); nAll = max(nAll, nStart); } return nAll; } nStart = max(nAll + A[i] , 0);
nAll = max(nAll, nStart);
24. 請給出二叉樹的前序周遊 abdefghc
25.最長遞增子序列（LIS）表示在一個序列中，保持遞增的最長子序列，比如（2，1，4，2，3，7，4，6）的LIS是{1,2,3,4,6},則LIS的長度是5.
對于一個有N個元素的序列，得到LIS的長度的最優時間複雜度是 O(nlogn) ，空間複雜度是o(n) 。
具體參考：
動态規劃-最長上升子序列（LIS）
26.給一系列的數1，2，3，，，n(有序的)和一個棧（stack），這個棧無限大，将這n個數按照順序放入棧中，但是随機的從棧中彈出，n=5，一共有多少中彈棧方式。42
解析：這是卡特蘭數的典型應用。Catalan數的定義令h(1)=1，Catalan數滿足遞歸式：h(n) = h(1)*h(n-1) + h(2)*h(n-2) + ... + h(n-1)h(1)，n>=2該遞推關系的解為：h(n) = C(2n,n)/(n+1)，n=1,2,3,...（其中C(2n,n)表示2n個中取n個的組合數）
h(5) = C(10,5)/6 = 42
27.請給出表達式 a + b*(c-d)/e-f 的逆波蘭式。abcd-*e/+f-
解析：先畫出式子的二叉樹，再寫出後序周遊的結果。
三、Web前端方向附加題 略
四、其他方向附加題
1.微網誌廣告投放是騰訊收入來源之一，為了保證投放的廣告對使用者更有幫助，必須分析使用者對什麼最感興趣。使用者的每條微薄都可以拆分成幾個關鍵字，騰訊微網誌每個月會收集到上T的關鍵字，請你分析出其中出現次數最多的十個關鍵字。
解析:先用Hashmap統計關鍵字的出現次數，再用“求最大的k個數”的方法，用堆來得到出現次數最大的10個關鍵字。
2.騰訊新聞首頁改版之後，為了精确掌握改版效果，需要準實時統計每篇文章的IP數量，即從文章發表之後，有多少個不同的ip的使用者讀過這篇文章。每個使用者通路請求都會被web伺服器解析，并實時傳輸到背景統計系統，請逆設計該“背景統計系統”，以完成統計。
轉載于:https://blog.51cto.com/8672742/1368210