一、 客觀題: (總分，60分，每題4分共15題)
1
關(guān)于HTTP協(xié)議的說法，以下哪些說法是不正確的()
A. 有狀態(tài)，前后請求有關(guān)聯(lián)關(guān)系
B. FTP也可以使用HTTP協(xié)議
C. HTTP響應(yīng)包括數(shù)字狀態(tài)碼，300代表此次請求有正確返回
D. HTTP和TCP、UDP是在網(wǎng)絡(luò)分層里是同一層次的協(xié)議
2
以下代碼運行結(jié)果為()
#include
int main() {
uint32_t a = 100;
while(a > 0){
--a;
}
printf("%d",a);
return 0;
}
A. -1
B. 100
C. 0
D. 死循環(huán)
3
以下哪種排序算法需要開辟額外的儲存空間()
A. 選擇排序
B. 歸并排序
C. 快速排序
D. 堆排序
4
如果將固定塊大小的文件系統(tǒng)中的塊大小設(shè)置大一些，會造成()
A. 更好的磁盤吞吐量和更差的磁盤空間使用率
B. 更好的磁盤吞吐量和更好的磁盤空間使用率
C. 更差的磁盤吞吐量和更好的磁盤空間使用率
D. 更差的磁盤吞吐量和更差的磁盤空間使用率
5
若一顆二叉樹的前序遍歷為a,e,b,d,c，后序遍歷為b,c,d,e,a，則根節(jié)點的孩子節(jié)點()
A. 只有e
B. 有e,b
C. 有e,c
D. 不確定
6
在一個世世代代都重男輕女的村莊里，村長決定頒布一條法律:村子里沒有生育出兒子的夫妻可以一直生育指導(dǎo)生出兒子位置，假設(shè)現(xiàn)在村子的男女比例是1:1，這條法律頒布之后的若干年后村子的男女比例將會()
A. 男的多
B. 女的多
C. 一樣多
D. 不確定
7
批處理操作系統(tǒng)目的是()
A. 提高操作系統(tǒng)資源利用率
B. 提高系統(tǒng)與用戶的交互性能
C. 減少用戶作業(yè)的等待時間
D. 降低用戶作業(yè)的周轉(zhuǎn)時間
8
設(shè)有一個關(guān)系:DEPT(DNO,DNAME)，如果要找出倒數(shù)第三個字母為W，并且至少包含4個字母的DNAME,則查詢條件子句應(yīng)寫成WHERE DNAME LIKE()
A. '__W_%'
B. '_%W__'
C. '_W__'
D. '_W_%'
9
已知的一個無向圖(邊為正數(shù))中頂點A，B的一條最短路P，如果把各個邊的權(quán)重(即相鄰連個頂點的距離)變?yōu)樵瓉淼?倍，那么在新圖中，P忍讓是A，B之間的最短路。以上說法()錯誤。
A. 不確定
B. 正確
C. 錯誤
10
如下程序的時間復(fù)雜度為(其中m>1,e>0)()
x = m;
y = 1;
while (x - y > e){
x = (x + y)/2;
y = m/x;
}
print(x);
A. log m
B. m2
C. m1/2
D. m1/3
11
求fun(484)的返回值()
bool fun(int n){
int sum = 0;
for (int i = 1; n > sum; i = i+2)
sum = sum + i;
return (n == sum);
}
A. True
B. False
12
關(guān)于主對角線(從左上角到右下角)對稱的矩陣為對稱矩陣: 如果一個矩陣中的各個元素取值為0或1，那么該矩陣為01矩陣，求大小為N*N的01對陣矩陣的個數(shù)? ( )
A. power(2, n)
B. power(2, n*n/2)
C. power(2,(n*n + n)/2)
D. power(2,(n*n - n)/2)
13
現(xiàn)代的語言(如java)的編譯器的詞法分析主要依靠()
A. 有限狀態(tài)自動機
B. 確定下推自動機
C. 非確定下推自動機
D. 圖靈機
14
如下函數(shù)的f(1)的值為()
int f(int n) {
static int i = 1;
if (n >= 5)
return n;
n = n+i;
i++;
return f(n);
}
A. 5
B. 6
C. 7
D. 8
15
123456789101112...2014除以9的余數(shù)是____
二、 編程題: (總分，40分，每題20分)
16
給定字符串(ASCII碼 0~255)數(shù)組，請在不開辟額外空間的情況下刪除開始和結(jié)尾處的空格，并將中間的多個連續(xù)的空格合并成一個。例如:" i am a little boy. ",變成"i am a little boy."，語言不限，但不要用偽代碼作答，函數(shù)輸入輸出請參考如下的函數(shù)原型:
C++ 函數(shù)原型:
void FormatString(char str[], int len){
}
17
給定一顆二叉樹，以及其中的兩個node(地址均非空)，要求給出這兩個node的一個公共父節(jié)點，使得這個父節(jié)點與兩個節(jié)點的路徑之和最小，描述你程序的最壞時間復(fù)雜度，并實現(xiàn)具體函數(shù)，函數(shù)輸入輸出請參考如下的函數(shù)原型:
C++ 函數(shù)原型:
struct TreeNode {
TreeNode* left;//指向左子樹
TreeNode* right;//指向右子樹
TreeNode* father;//指向父親節(jié)點
};
TreeNode* LowestCommonAncestor(TreeNode* first, TreeNode* second) {
}
三、 附加題: (總分20分)
18
有n枚硬幣按照0到n-1對它們進行編號，其中編號為i的硬幣面額為Vi。兩個人輪流從剩下硬幣中取出一枚硬幣歸自己所有，但每次取硬幣的時候只能取剩下的硬幣中編號最小的硬幣或者編號的硬幣，在兩個都采用策略的情況下，作為先手取硬幣的你請編寫程序計算出你能獲得硬幣總面額的值? (請簡述算法原理，時間復(fù)雜度并實現(xiàn)具體的程序)，語言不限。
int MaxValue(int V[], int n) {
}