一、選擇題：15分 共10題

　　1.一個(gè)含有n個(gè)頂點(diǎn)和e條邊的簡(jiǎn)單無(wú)向圖，在其鄰接矩陣存儲(chǔ)結(jié)構(gòu)中共有____個(gè)零元素。

　　a.e　　　 b.2e　　　 c.n2-e　　 d.n2-2e

　　2.____是面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言中的一種機(jī)制。這種機(jī)制實(shí)現(xiàn)了方法的定義與具體的對(duì)象無(wú)關(guān)，而對(duì)方法的調(diào)用則可以關(guān)聯(lián)于具體的對(duì)象。

　　a.繼承(inhertance) b.模板(template)

　　c.對(duì)象的自身引用(self-reference) d.動(dòng)態(tài)綁定(dynamic binding)

　　3.應(yīng)用層dns協(xié)議主要用于實(shí)現(xiàn) 網(wǎng)絡(luò)服務(wù)功能.

　　a. ip地址到網(wǎng)絡(luò)設(shè)備名字的映射 b. ip地址到網(wǎng)絡(luò)硬件地址的映射

　　c. 網(wǎng)絡(luò)設(shè)備名字到ip地址的映射 d. 網(wǎng)絡(luò)硬件地址到ip地址的映射

　　4.linux默認(rèn)情況下，一個(gè)進(jìn)程最多能打開(kāi)多少文件?

　　a.64 b. 128 c. 512 d. 1024

　　5.下面結(jié)構(gòu)體

　　struct s1 {

　　char ch, *ptr;

　　union {

　　short a, b;

　　unsigned int c:2, d:1;

　　}

　　struct s1 *next;

　　};

　　的大小是_____：

　　a. 12字節(jié) b.16字節(jié) c.20字節(jié) d. 24字節(jié)

　　6.任何一個(gè)基于"比較"的內(nèi)部排序的算法，若對(duì)6個(gè)元素進(jìn)行排序，則在最壞情況下所需的比較次數(shù)至少為_(kāi)___。

　　a.10 b.11 c.21 d.36

　　7.以下不是進(jìn)程間通訊的是___

　　a 共享內(nèi)存 b 信號(hào)量 c線程局部存儲(chǔ) d 消息隊(duì)列

　　8.下面程序，求count的值

　　int func(x)

　　{

　　int count= 0;

　　x=9999;

　　while(x)

　　{

　　count ++;

　　x = x&(x-1);

　　}

　　return count;

　　}

　　a 8; b 10; c 5; d 11

　　9.使用malloc系統(tǒng)調(diào)用分配的內(nèi)存是在____ 上分配的?

　　a 棧; b bss; c 物理內(nèi)存; d 堆

　　10.最壞情況下，合并兩個(gè)大小為n的已排序數(shù)組所需要的比較次數(shù)_____

　　a.2n b.2n-1 c.2n+1 d.2n-2

　　二、簡(jiǎn)答題：20分，共3題

　　1.(5分)下面這段代碼是把中英文混合字符串(漢字用兩個(gè)字節(jié)表示，特點(diǎn)是第一個(gè)字節(jié)的最高位為1)中的大寫字母轉(zhuǎn)化為小寫字母，請(qǐng)找出其中的bug，注意各種異常情況。

　　for (char *piterator = szword; *piterator != 0; piterator++)

　　{

　　if (*piterator & 0x80 != 0)

　　{

　　piterator++;

　　}

　　else if (*piterator >= 'a' && *piterator <= 'z')

　　piterator += 32;

　　}

　　2.(5分)對(duì)給定的上億條無(wú)序的url，請(qǐng)按照domain、site以及path分別排序，并請(qǐng)指出排序過(guò)程中可能會(huì)遇到的哪些問(wèn)題?如何提高效率?

　　例如：，domain、site以及path的定義分別如下：

　　domain:

　　site:

　　path:

　　3.(10分)某型cpu的一級(jí)數(shù)據(jù)緩存大小為16k字節(jié)，cache塊大小為64字節(jié);二級(jí)緩存大小為256k字節(jié)，cache塊大小為4k字節(jié)，采用二路組相聯(lián)。經(jīng)測(cè)試，下面兩段代碼運(yùn)行時(shí)效率差別很大，請(qǐng)分析哪段代碼更好，以及可能的原因。

　　為了進(jìn)一步提高效率，你還可以采取什么辦法?

　　a段代碼

　　int matrix[1023][15];

　　const char *str = "this is a str";

　　int i, j, tmp, sum = 0;

　　tmp = strlen(str);

　　for(i = 0; i < 1023; i++) {

　　for(j = 0; j < 15; j++) {

　　sum += matrix[i][j] + tmp;

　　}

　　}

　　b段代碼

　　int matrix[1025][17];

　　const char *str = "this is a str";

　　int i, j, sum = 0;

　　for(i = 0; i < 17; i++) {

　　for(j = 0; j < 1025; j++) {

　　sum += matrix[j][i] + strlen(str);

　　}

　　}

　　三、編程題：30分 共1題

　　注意：要求盡可能提供完整代碼，如果可以編譯運(yùn)行酌情加分。

　　1.內(nèi)存中有一個(gè)長(zhǎng)數(shù)組，條目數(shù)為10萬(wàn)，數(shù)組單元為結(jié)構(gòu)體struct array，sizeof(struct array)為512字節(jié)。結(jié)構(gòu)有一int型成員變量weight�，F(xiàn)需要取得按weight值從大到小排序的前500個(gè)數(shù)組單元，請(qǐng)實(shí)現(xiàn)算法，要求效率盡可能高。