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