一、單項(xiàng)選擇題（共15題，每題1.5分，共計(jì)22.5分；每題有且僅有一個(gè)正確選項(xiàng)）   

 1. 在計(jì)算機(jī)內(nèi)部用來(lái)傳送、存貯、加工處理的數(shù)據(jù)或指令都是以（   ）形式進(jìn)行的。

 A. 二進(jìn)制碼 B. 八進(jìn)制碼  C. 十進(jìn)制碼  D. 智能拼音碼  

A

學(xué)過(guò)的都知道=。=

2. 下列說(shuō)法正確的是（   ）。  

A. CPU的主要任務(wù)是執(zhí)行數(shù)據(jù)運(yùn)算和程序控制

B. 存儲(chǔ)器具有記憶能力，其中信息任何時(shí)候都不會(huì)丟失

C. 兩個(gè)顯示器屏幕尺寸相同，則它們的分辨率必定相同

D. 個(gè)人用戶(hù)只能使用Wifi的方式連接到Internet   

A

CPU包括控制器和運(yùn)算器，顯然它的主要任務(wù)就是A

存儲(chǔ)器有主存和輔存，主存中有ROM和RAM，RAM在關(guān)機(jī)或停電情況下內(nèi)容全部丟失

C顯然不對(duì)=。=

Internet上網(wǎng)的幾種常用連接方式：1、撥號(hào)上網(wǎng)2、ISDN 3、寬帶上網(wǎng) 4.無(wú)線(xiàn)上網(wǎng)

具體了解請(qǐng)見(jiàn)百度百科：http://wenku.baidu.com/link?url=J1MSLO-SX-LJaMTSt_-XjHCXnTMfVPZmV7lyiXo9Y1OVf_edlwQWhTisZFYGNDDrdwlA_yG1ruDep9OcyMDoaJH6JU6k1gKUoStEowhciNe

3. 與二進(jìn)制小數(shù)0.1相等的十六進(jìn)制數(shù)是（   ）。 A. 0.8 B. 0.4  C. 0.2  D. 0.1   

A

又是送分的進(jìn)制轉(zhuǎn)換

 4. 下面有四個(gè)數(shù)據(jù)組，每個(gè)組各有三個(gè)數(shù)據(jù)，其中第一個(gè)數(shù)據(jù)為八進(jìn)制數(shù)，第二個(gè)數(shù)據(jù)為 十進(jìn)制數(shù)，第三個(gè)數(shù)據(jù)為十六進(jìn)制數(shù)。這四個(gè)數(shù)據(jù)組中三個(gè)數(shù)據(jù)相同的是（   ）。

 A. 120 82 50 B. 144 100 68  C. 300 200 C8  D. 1762 1010 3F2    

D

送分的進(jìn)制轉(zhuǎn)換，就算變了變形式我也認(rèn)識(shí)你=w=

5. 線(xiàn)性表若采用鏈表存儲(chǔ)結(jié)構(gòu)，要求內(nèi)存中可用存儲(chǔ)單元地址（   ）。

A. 必須連續(xù) B. 部分地址必須連續(xù) C. 一定不連續(xù) D. 連續(xù)不連續(xù)均可

D

數(shù)據(jù)結(jié)構(gòu)問(wèn)題=w=，鏈表結(jié)構(gòu)與順序結(jié)構(gòu)最大的不同在于鏈表存儲(chǔ)地址可以不連續(xù)，便于元素的插入和刪除    

6. 今有一空棧S，對(duì)下列待進(jìn)棧的數(shù)據(jù)元素序列a,b,c,d,e,f依次進(jìn)行進(jìn)棧，進(jìn)棧，出棧， 進(jìn)棧，進(jìn)棧，出棧的操作，則此操作完成后，棧S的棧頂元素為（   ）。

A. f  B. c  C. a  D. b

B

學(xué)過(guò)的導(dǎo)一下就可以了

7. 前序遍歷序列與后序遍歷序列相同的二叉樹(shù)為（   ）。

A. 非葉子結(jié)點(diǎn)只有左子樹(shù)的二叉樹(shù) B. 只有根結(jié)點(diǎn)的二叉樹(shù)  

C. 根結(jié)點(diǎn)無(wú)右子樹(shù)的二叉樹(shù) D. 非葉子結(jié)點(diǎn)只有右子樹(shù)的二叉樹(shù)   

B

前序遍歷：根左右，后序遍歷：左右根，然后畫(huà)個(gè)圖試試就知道了 

8. 如果根的高度為1，具有61個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度為（   ）。

A. 5 B. 6  C. 7  D. 8    

B，學(xué)過(guò)的應(yīng)該沒(méi)問(wèn)題，沒(méi)學(xué)過(guò)的畫(huà)一畫(huà)、算一算應(yīng)該也能過(guò)

9. 6個(gè)頂點(diǎn)的連通圖的最小生成樹(shù)，其邊數(shù)為（   ）。

A. 6 B. 5  C. 7  D. 4    

B

它都是棵樹(shù)了還有什么可說(shuō)的=。=

10. 設(shè)某算法的計(jì)算時(shí)間表示為遞推關(guān)系式T(n) = T(n - 1) + n（n為正整數(shù)）及T(0) = 1，則 該算法的時(shí)間復(fù)雜度為（   ）。 A. O(log n) B. O(n log n)  C. O(n)  D. O(n2)    

D

T(n)=T(n-1)+n

   =T(n-2)+n-1+n

   ……

   =T(0)+1+2+3+……+n

   =1+n*(n+1)/2

所以是O（n^2)

11. 具有n個(gè)頂點(diǎn)，e條邊的圖采用鄰接表存儲(chǔ)結(jié)構(gòu)，進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷運(yùn) 算的時(shí)間復(fù)雜度均為（   ）。

A. Θ(n2) B. Θ(e2)  C. Θ(ne)  D. Θ(n + e)    

D

遍歷算法中，時(shí)間復(fù)雜度主要取決于搜索鄰接點(diǎn)的個(gè)數(shù)；

鄰接矩陣存儲(chǔ)時(shí)，對(duì)于n個(gè)頂點(diǎn)每個(gè)頂點(diǎn)要遍歷n次，顯然是O(n^2)的

鄰接表存儲(chǔ)時(shí)，有n個(gè)頭結(jié)點(diǎn)和e個(gè)表結(jié)點(diǎn)，所有節(jié)點(diǎn)遍歷一遍，所以是D

12. 在數(shù)據(jù)壓縮編碼的應(yīng)用中，哈夫曼（Huffman）算法是一種采用了（   ）思想的算法

 A. 貪心 B. 分治  C. 遞推  D. 回溯    

A

沒(méi)什么可說(shuō)的，不知道的用排除法也應(yīng)該沒(méi)問(wèn)題

13. 雙向鏈表中有兩個(gè)指針域，llink和rlink，分別指回前驅(qū)及后繼，設(shè)p指向鏈表中的 一個(gè)結(jié)點(diǎn)，q指向一待插入結(jié)點(diǎn)，現(xiàn)要求在p前插入q，則正確的插入為（   ）。

A. p^.llink := q; q^.rlink := p;  p^.llink^.rlink := q; q^.llink := p^.llink;

B. q^.llink := p^.llink; p^.llink^.rlink := q;  q^.rlink := p; p^.llink := q^.rlink;

C. q^.rlink := p; p^.rlink := q;  p^.llink^.rlink := q; q^.rlink := p;

 D. p^.llink^.rlink := q; q^.rlink := p;  q^.llink := p^.llink; p^.llink := q;   

D

導(dǎo)一下就ok了

14. 對(duì)圖G中各個(gè)結(jié)點(diǎn)分別指定一種顏色，使相鄰結(jié)點(diǎn)顏色不同，則稱(chēng)為圖G的一個(gè)正常 著色。正常著色圖G所必需的最少顏色數(shù)，稱(chēng)為G的色數(shù)。那么下圖的色數(shù)是（   ）。

A. 3 B. 4 C. 5 D. 6    

A

自己試一試應(yīng)該沒(méi)問(wèn)題吧

15. 在NOI系列賽事中參賽選手必須使用由承辦單位統(tǒng)一提供的設(shè)備。下列物品中不允許選 手自帶的是（   ）。 A. 鼠標(biāo) B. 筆  C. 身份證  D. 準(zhǔn)考證    

A

排除法

二、不定項(xiàng)選擇題（共5題，每題1.5分，共計(jì)7.5分；每題有一個(gè)或多個(gè)正確選項(xiàng)，多選或少選均不得分）    

1. 以下屬于操作系統(tǒng)的有（   ）。 A. Windows XP B. UNIX  C. Linux  D. Mac OS   

ABCD

不清楚的建議上網(wǎng)查一下因?yàn)檫@應(yīng)該是第二次考了 

2. 下列屬于視頻文件格式的有（   ）。 A. AVI B. MPEG  C. WMV  D. JPEG   

 ABC

常見(jiàn)的視頻格式：視頻文件格式有不同的分類(lèi)，如：

微軟視頻 ：wmv、asf、asx

Real Player ：rm、 rmvb

MPEG視頻 ：mpg、mpeg、mpe

手機(jī)視頻 ：3gp

Apple視頻 ：mov

Sony視頻 ：mp4、m4v

其他常見(jiàn)視頻：avi、dat、mkv、flv、vob

——來(lái)自百度百科

3下列選項(xiàng)不是正確的IP地址的有（   ）。

A. 202.300.12.4 B. 192.168.0.3  C. 100:128:35:91  D. 111-103-35-21

ACD

IP地址的范圍0~225

IP地址用“點(diǎn)分十進(jìn)制”   

 4. 下列有關(guān)樹(shù)的敘述中，敘述正確的有（   ）。

A. 在含有n個(gè)結(jié)點(diǎn)的樹(shù)中，邊數(shù)只能是(n-1)條

B. 在哈夫曼樹(shù)中，葉結(jié)點(diǎn)的個(gè)數(shù)比非葉結(jié)點(diǎn)個(gè)數(shù)多1

 C. 完全二叉樹(shù)一定是滿(mǎn)二叉樹(shù)  

D. 在二叉樹(shù)的前序序列中，若結(jié)點(diǎn)u在結(jié)點(diǎn)v之前，則u一定是v的祖先  

AB

A顯然對(duì)，B的話(huà)了解哈夫曼樹(shù)的形成的話(huà)顯然是對(duì)的，

C完全二叉樹(shù)：只有最下面的兩層結(jié)點(diǎn)度能夠小于2，并且最下面一層的結(jié)點(diǎn)都集中在該層最左邊的若干位置的二叉樹(shù)，

D：根左右，在前面的也可能是根的左結(jié)點(diǎn)

5. 以下圖中一定可以進(jìn)行黑白染色的有（   ）。（黑白染色：為各個(gè)結(jié)點(diǎn)分別指定黑白 兩種顏色之一，使相鄰結(jié)點(diǎn)顏色不同。） A. 二分圖 B. 完全圖  C. 樹(shù)  D. 連通圖

AC

若一個(gè)圖的每一對(duì)不同頂點(diǎn)恰有一條邊相連，則稱(chēng)為完全圖。完全圖是每對(duì)頂點(diǎn)之間都恰連有一條邊的簡(jiǎn)單圖。n個(gè)端點(diǎn)的完全圖有n個(gè)端點(diǎn)及n(n ? 1) / 2條邊，B顯然是不可以的；

對(duì)于連通圖，形成環(huán)的話(huà)也是顯然不行的，所以是不一定的

三、

1.1075

容斥原理，反著想

1~2015，有503個(gè)能被4整除的，有403個(gè)能被5整除的，有335個(gè)能被6整除的

其中能被4、5的最小公倍數(shù)20整除的算了兩遍有100個(gè)，

能被4、6 的最小公倍數(shù)12整除的算了2遍有167個(gè)，

能被5、6 的最小公倍數(shù)30整除的算了兩遍有67個(gè)，

所以503+403+335-100-167-67=907；

在減的時(shí)候，能被4、5、6 的最小公倍數(shù)120整除的數(shù)減了3遍，

在一開(kāi)始算的時(shí)候也算了3遍，所以907種中沒(méi)有能被120整除的數(shù)，所以907+33=940；

所以共有940個(gè)能被4、 5、 6 中任意一個(gè)數(shù)整除的數(shù)

答案就是：2015-940=1075

（當(dāng)然你最小公倍數(shù)求錯(cuò)了的話(huà)怪我嘍=。=）

2.

42

二叉樹(shù)的按結(jié)點(diǎn)個(gè)數(shù)，不同形態(tài)數(shù)按照Catalan序列

其中，結(jié)點(diǎn)數(shù)為5的有(10)!/(5!*5!)/(5+1) = 42種

四

1、3 2

2、Ab （其實(shí)我也不大懂，旁邊的一位大神告訴我，其實(shí)在草稿上畫(huà)出指針和修改過(guò)程就很清楚了）

3、citizen（就是輸出最長(zhǎng)的字符串

4、31(遞歸，其實(shí)推著推著會(huì)發(fā)現(xiàn)凡是fun(0,*，*）的結(jié)果都為0，

   然后凡是fun（1，*，*）=0+1+0=1

   然后凡是fun(2,*,*)=1+1+1=3

   然后凡是fun(3,*,*)=3+3+1=7

   然后凡是fun(4,*,*)=7+7+1=15

   最后凡是fun(5,*,*)=15+1+15=31

五．

【pascal答案】

1、（1）rmax[n]:=x[n];

（2）rmax[i]:=x[i];

（3）rmax[i]:=rmax[i-1]+x[i];

（4）rmax[i]:=rmax[i+1];

（5）lmax[i-1]+rmax[i+1]（因?yàn)橐钌匍g隔一個(gè)數(shù)）

個(gè)人感覺(jué)這題還是蠻簡(jiǎn)單的，看清楚題目要求直接一遍就應(yīng)該沒(méi)什么問(wèn)題了，而且就算不會(huì)寫(xiě)也可以照著上面對(duì)稱(chēng)著改一改就可以了=。=

2、（1）v:=-1

(2)dist[i]<dist[v]

（3）v:=i;

(4)used[v]:=1;

(5)dist[i]>dist[v]+w[v,i]

個(gè)人感覺(jué)只要會(huì)Dijkstra的應(yīng)該填個(gè)大概或滿(mǎn)分應(yīng)該沒(méi)問(wèn)題的，對(duì)于我這種已經(jīng)淡忘Dijkstra而只會(huì)SPFA的渣渣看了好幾遍才填完然而還錯(cuò)了一個(gè)空，也是醉了=。=

總體感覺(jué)這一年的最后一道題簡(jiǎn)單不少=。=

                                     ——by Eirlys