題目二： 　　1寫(xiě)出下列算法的時(shí)間復(fù)雜度。 　　(1)冒泡排序; 　　(2)選擇排序; 　　(3)插入排序; 　　(4)快速排序; 　　(5)堆排序; 　　(6)歸并排序; 　　2寫(xiě)出下列程序在X86上的運(yùn)行結(jié)果。 　　struct mybitfields 　　{ 　　unsigned short a : 4; 　　unsigned short b : 5; 　　unsigned short c : 7; 　　}test 　　void main(void) 　　{ 　　int i; 　　test.a=2; 　　test.b=3; 　　test.c=0; 　　i=((short )&test); 　　printf("%d\n",i); 　　} 　　3寫(xiě)出下列程序的運(yùn)行結(jié)果。 　　unsigned int i=3; 　　cout< 　　4寫(xiě)出下列程序所有可能的運(yùn)行結(jié)果。 　　int a; 　　int b; 　　int c; 　　void F1() 　　{ 　　b=a2; 　　a=b; 　　} 　　void F2() 　　{ 　　c=a+1; 　　a=c; 　　} 　　main() 　　{ 　　a=5; 　　//Start F1,F2 in parallel 　　F1(); F2(); 　　printf("a=%d\n",a); 　　} 　　5考察了一個(gè)CharPrev()函數(shù)的作用。 　　6對(duì) 16 Bits colors的處理，要求： 　　(1)Byte轉(zhuǎn)換為RGB時(shí)，保留高5、6bits; 　　(2)RGB轉(zhuǎn)換為Byte時(shí)，第2、3位置零。 　　7一個(gè)鏈表的操作，注意代碼的健壯和安全性。要求： 　　(1)增加一個(gè)元素; 　　(2)獲得頭元素; 　　(3)彈出頭元素(獲得值并刪除)。 　　8一個(gè)給定的數(shù)值由左邊開(kāi)始升位到右邊第N位，如 0010<<1 == 0100 或者 0001 0011<<4 == 0011 0000 　　請(qǐng)用C或者C++或者其他X86上能運(yùn)行的程序?qū)崿F(xiàn)。 　　附加題(只有在完成以上題目后，才獲準(zhǔn)回答) 　　In C++, what does "explicit" mean? what does "protected" mean? 　　題目三： 　　某棟寫(xiě)字樓6層，有1部電梯，請(qǐng)編寫(xiě)一個(gè)電梯仿真程序 　　A.考慮如下條件 　　1.每層樓都有上行和下行兩個(gè)按鍵 　　2. 電梯一開(kāi)始停在1層 　　3. 電梯可以容納8個(gè)人 　　4. 乘坐電梯的客人的請(qǐng)求頻率，時(shí)間間隔和到達(dá)樓層是隨機(jī)的 　　5. 電梯的上下一層需要1秒 　　6. 電梯空間有限，同時(shí)只能容納一定數(shù)量的客人，如果已經(jīng)達(dá)到人數(shù)額度，電梯將不理會(huì)任何請(qǐng)求 　　7.不考慮客人請(qǐng)求當(dāng)前樓層和不請(qǐng)求樓層的情況 　　8. 電梯的響應(yīng)延遲為0(比如，電梯往3樓上行，3樓的客人在電梯到達(dá)3樓之前按上行鍵，程序有權(quán)調(diào)度電梯在3樓開(kāi)門(mén)) 　　9. 電梯的開(kāi)關(guān)門(mén)時(shí)間和客人上下電梯時(shí)間為0，勻速運(yùn)行 　　10. 電梯調(diào)度算法不能預(yù)讀尚未發(fā)生的請(qǐng)求(比如在10秒的時(shí)候電梯無(wú)法預(yù)知11秒時(shí)某層客人的請(qǐng)求) 　　11.客人請(qǐng)求發(fā)生在整數(shù)秒 　　B.目標(biāo) 　　1. 在運(yùn)送所有客人到達(dá)目標(biāo)樓層的前提下電梯的總行程盡可能小 　　2. 設(shè)計(jì)一個(gè)接口，實(shí)現(xiàn)調(diào)度算法的可替換性(比如，通過(guò)重新實(shí)現(xiàn)該接口可以使系統(tǒng)使用其它算法) 　　C. 輸入和輸出 　　輸入: 　　input.txt 　　客人的請(qǐng)求序列，格式為到達(dá)時(shí)間，所在樓層，請(qǐng)求樓層，假設(shè)該輸入是按照時(shí)間遞增的 　　比如： 　　input.txt 　　1 2 3 　　2 3 1 　　在1秒的時(shí)候有客人請(qǐng)求從2層到3層，2秒的時(shí)候有客人請(qǐng)求從3層到1層 　　輸出: 設(shè)計(jì)一種簡(jiǎn)單實(shí)用的輸出可以清晰地反映電梯的運(yùn)轉(zhuǎn)情況 　　題目四： 　　選擇題部分 　　1. 以下哪些不是棧的基本操作 　　A. push 　　B. pop 　　C. 判斷棧是否為空 　　D. 棧排序 　　2.兩個(gè)有序數(shù)組 大小都是 n，現(xiàn)在要對(duì)它們進(jìn)行合并排序。 問(wèn)最壞情況下，需要比較多少次? 　　A. 2n+1 　　B. 2n 　　C.2n-1 　　D…記不清了 　　3. (an 表示第 n 個(gè)常數(shù)， x^5 表示 x 的 5 次方) 　　f(x)= a0x^0 + a1x^1+a2x^2+……anx^n 　　對(duì)于固定的 n，f(x)的時(shí)間復(fù)雜度以及空間復(fù)雜度分別是多少? 　　A. o(n^2)，o(n) 　　B.o(n)，o(1) 　　C 　　D 都記不住了 　　4.是個(gè)概率題，大概意思是這樣的 　　現(xiàn)在有 800 個(gè)人，但是只有 400 份獎(jiǎng)品，有一對(duì)夫婦都參加抽獎(jiǎng)，但是他們最多抽到一份獎(jiǎng)，現(xiàn)在問(wèn) 　　他們倆能抽到一份獎(jiǎng)的概率是多少? 　　A.0.5 　　B.0.75 　　C. (0.5,0.75) 　　D. (0.75,1) 　　5. 現(xiàn)有一鏈表當(dāng)前指示節(jié)點(diǎn)為 currentNode, 生成了一個(gè)新節(jié)點(diǎn) newNode,問(wèn)要把 newNode 插入到currentNode 之后 ，該怎么做? 　　A… 　　B… 　　C. newNode->next = currentNode->next, currentNode->next = newNode. 　　D… 　　6. 問(wèn)以下哪些特征不是 interPted language(解釋型語(yǔ)言)所獨(dú)有的： 　　(我們知道一般分為兩種：解釋型語(yǔ)言 VB,Shell,批處理等;編譯型語(yǔ)言，C，java 等。各有優(yōu)點(diǎn) ) 　　A. 平臺(tái)無(wú)關(guān)性。(明顯不對(duì)，因?yàn)?java 才是平臺(tái)無(wú)關(guān)的) 　　B. 執(zhí)行速度較快(這個(gè)問(wèn)題，以前做作業(yè)時(shí)就沒(méi)爭(zhēng)論清楚，自己感覺(jué)解釋型語(yǔ)言不需要編譯，速度能快一些，但是重復(fù)執(zhí)行時(shí)，編譯型語(yǔ)言只需要編譯一次，效率高……) 　　C. 可以定義動(dòng)態(tài)變量(應(yīng)該兩種都可以) 　　D.以上都不對(duì) 　　7.給了一個(gè)二叉樹(shù)，讓求后序遍歷的結(jié)果。 　　這個(gè)題如果知道后序遍歷，肯定就可以做出來(lái)了。 　　盡管不難 還是要搞清楚三者的區(qū)別(哈哈) 　　先序 左根右 　　中序 根左右 　　后序 左右根 　　8.問(wèn)以下幾種排序方法，在最壞情況下時(shí)間復(fù)雜度小于 o(n^2)的是哪一種(這個(gè)題目記得不是很清楚了) 　　A.快排 　　B.插入排序 　　C.合并排序 　　D.棧排序 　　9. 現(xiàn)有 n+1 這么大的存儲(chǔ)空間(可以理解有這么一個(gè)大小為 n+1 的數(shù)組)，中間存了[1,n+1]范圍內(nèi)的n 個(gè)數(shù)，說(shuō)明丟失了一個(gè)數(shù)，現(xiàn)在要找出這個(gè)丟失的數(shù)，問(wèn)最好情況下時(shí)間復(fù)雜度是多少 　　A.o(1) 　　B.o(n) 　　C.o(n^2) 　　D.o(nlogn) 　　10.是一道程序題，由于太長(zhǎng)，無(wú)從記憶…… 　　編程題部分用 C,C++,C#,或 Java 中的一種來(lái)編寫(xiě)以下程序。 　　現(xiàn)在給你一個(gè) 字符串，其中特殊的字符只有兩種 space(空格)(" ")，newline(換行)(/n)。 現(xiàn)在讓你來(lái)去除其中多余的空格。具體要求 　　1.連續(xù)的空格只能當(dāng)保留其中一個(gè) 　　2. 該字符串的開(kāi)頭不能有空格 　　3. 該字符串的結(jié)尾不能有空格 　　4. 任何/n 的前面或才后面都不能存在多余的空格 　　為了得到很高的分?jǐn)?shù)，還需要滿足以下條件 　　1.不能申請(qǐng)新的字符串空間 　　2.對(duì)給出的字符串只能遍歷一遍 　　不能使用任何庫(kù)函數(shù)。 　　我們給了兩個(gè)供你調(diào)用的函數(shù) 　　int intIsSpace(char str)() 　　當(dāng)字符不為空格時(shí)，將返回 0 　　當(dāng)字符為空格時(shí)，將返回其它任意非 0 值 　　int intIsNewLine(char str)()當(dāng)字符不為換行時(shí)，將返回 0 　　當(dāng)字符為換行時(shí)，將返回其它任意非 0 值 　　程序編寫(xiě)完成后，請(qǐng)編寫(xiě)測(cè)試用例，并說(shuō)明它完成的作用。