1.BMP格式圖像，圖像深度為24位，一個512*1024的點陣圖像所占空間是多少？
[html]
答：(24/8)B*512*1024=1.5M
2.十進制數字-3轉換為3進制的補碼結果是多少？
[cpp] view plaincopy
答：-3可以表示為：符號位負號可表示為1, 3為十進制，可以表示為13，轉換成三進制為110（符號位不變，3轉變為10），補碼的計算是源碼的反碼加1，110的反碼為112（最高位為符號位不變，10反碼為12（因為三進制中1的反碼為1,2的反碼為0，0 的反碼為2）），反碼加1後就是120
3.兩個進程同時執行以下一段代碼，其中不可能的結果是：
[html]
代碼如下：
A=5;
A=A+1 ;
printf("%d",A);
A 5,6 B 6，5 C 6,7 D 7,6
答：B,D，選項記不太清楚了，答案也是不太確定，望大牛指點。
4.pid_t pid=fork();
if(pid<0)
cout<<-1<<endl;
else if(pid==0)
cout<<0<<endl;
else
cout<<1<<endl;
不可能的答案是：
A 0 B 1 C 1,0 D 0,1
[cpp] view plaincopy
答案待定。C,D應該是可能的。
5 忘了
6. 6雙不同的襪子，取四只，恰有一雙襪子的情況有幾種？
[cpp]
答： 6*（C（10,2）-5）=240. 其中C(10,2)是從10只襪子選2只的種類。
7. 32位及其能否處理超過4G的內存？
[cpp]
不能，因為32為編制最大是4G，即便是所有的內存都存放地址，而不存放數據，也只能放4G的內存。
8.樹有時候比哈希快？
不太清楚
9.簡述一下LRU算法
[cpp]
什麼是LRU算法? LRU是Least Recently Used的縮寫，即最近最少使用頁面置換算法，是為虛擬頁式存儲管理服務的。 關於操作系統的內存管理，如何節省利用容量不大的內存為最多的進程提供資源，一直是研究的重要方向。而內存的虛擬存儲管理，是現在最通用，最成功的方式—— 在內存有限的情況下，擴展一部分外存作為虛擬內存，真正的內存只存儲當前運行時所用得到信息。這無疑極大地擴充了內存的功能，極大地提高了計算機的並發度。虛擬頁式存儲管理，則是將進程所需空間劃分為多個頁面，內存中只存放當前所需頁面，其余頁面放入外存的管理方式。 然而，有利就有弊，虛擬頁式存儲管理減少了進程所需的內存空間，卻也帶來了運行時間變長這一缺點：進程運行過程中，不可避免地要把在外存中存放的一些信息和內存中已有的進行交換，由於外存的低速，這一步驟所花費的時間不可忽略。因而，采取盡量好的算法以減少讀取外存的次數，也是相當有意義的事情。 對於虛擬頁式存儲，內外存信息的替換是以頁面為單位進行的——當需要一個放在外存的頁面時，把它調入內存，同時為了保持原有空間的大小，還要把一個內存中頁面調出至外存。自然，這種調動越少，進程執行的效率也就越高。那麼，把哪個頁面調出去可以達到調動盡量少的目的？我們需要一個算法。 自然，達到這樣一種情形的算法是最理想的了——每次調換出的頁面是所有內存頁面中最遲將被使用的——這可以最大限度的推遲頁面調換，這種算法，被稱為理想頁面置換算法。可惜的是，這種算法是無法實現的。編輯本段差距 為了盡量減少與理想算法的差距，產生了各種精妙的算法，最近最少使用頁面置換算法便是其中一個。LRU算法的提出，是基於這樣一個事實：在前面幾條指令中使用頻繁的頁面很可能在後面的幾條指令中頻繁使用。反過來說，已經很久沒有使用的頁面很可能在未來較長的一段時間內不會被用到。這個，就是著名的局部性原理 ——比內存速度還要快的cache，也是基於同樣的原理運行的。因此，我們只需要在每次調換時，找到最近最少使用的那個頁面調出內存。這就是LRU算法的全部內容。
10.有甲，乙兩個箱子，甲箱子中方了800個紅球，200個藍球，乙中放了200個紅球，800個藍球（後面的忘了，想起來了再寫）
11.n個無序整數，已知第i個數在排好序的序列中的位置為j，滿足|i-j|<=K,請設計一種排序算法，對該序列進行排序。注：算法時間復雜度為O（nlgn）的得0分，復雜度為O(nk)
的得兩分，總分是20分。
[cpp]
答：由以上條件判斷最小的數字一定在前k個中，於是可以講前k個數建立一個最小堆，然後把根元素取出，該根元素就是最小數，然後將第k+1個數放入堆中，因為第二小的數字肯定在下標為1到k+1的位置范圍內，所以調整最小堆之後，根元素就是第二小元素，取出該元素，將第k+2個元素放入堆中，。。。。。。以此類推，按照元素從堆中取出的順序就是已經排好序的序列。該算法時間復雜度為O(nlgk)，確切的說是（n-k）lgk,
12.有一個字符串排列 a,b,c,d,aa,ba,ca,da,ab,bb,cb,db,ac,bc,cc,dc,ad,bd,cd,dd..........
編程實現：1.ababab是第幾個字符串？
2，第78個字符串是什麼？
3.第n個字符串是什麼？
[cpp]
初看起來比較抽象，但是我們如果把每一個字符串前後顛倒，問題就明朗多了，加入我們做如下映射：a---1, b---2,c---3,d---4，那麼以上的每一個字符串前後顛倒後再做一下數字映射就變成了：1,2,3,4,11,12,13,14,21,22,23,24,..........是不是很熟悉了，很像四進制編碼吧！只是把0換成了4，如果求某一字符串的位置，則做數字映射之後的計算就簡單多了，比如ababab翻轉後為bababa，轉化為數字後就是：212121，位置就是（（（（（2*4+1）*4）+2）*4+1）*4+2）*4+1；就是做一個特殊四進制到十進制的轉換。有了這個思路下面的題目就好做多了。
