微軟2019校長筆試真題及答案(二)

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