一、簡答題(30)
1：數(shù)據(jù)庫以及線程發(fā)生死鎖的原理及必要條件，如何避免死鎖
答：
產(chǎn)生死鎖的原因主要是：
(1) 因為系統(tǒng)資源不足。
(2) 進程運行推進的順序不合適。
(3) 資源分配不當(dāng)?shù)取?/p>
產(chǎn)生死鎖的四個必要條件：
(1)互斥條件：一個資源每次只能被一個進程使用。
(2)請求與保持條件：一個進程因請求資源而阻塞時，對已獲得的資源保持不放。
(3)不剝奪條件:進程已獲得的資源，在末使用完之前，不能強行剝奪。
(4)循環(huán)等待條件:若干進程之間形成一種頭尾相接的循環(huán)等待資源關(guān)系。
避免死鎖：
死鎖的預(yù)防是通過破壞產(chǎn)生條件來阻止死鎖的產(chǎn)生，但這種方法破壞了系統(tǒng)的并行性和并發(fā)性。
死鎖產(chǎn)生的前三個條件是死鎖產(chǎn)生的必要條件，也就是說要產(chǎn)生死鎖必須具備的條件，而不是存在這3個條件就一定產(chǎn)生死鎖，那么只要在邏輯上回避了第四個條件就可以避免死鎖。
避免死鎖采用的是允許前三個條件存在，但通過合理的資源分配算法來確保永遠不會形成環(huán)形等待的封閉進程鏈，從而避免死鎖。該方法支持多個進程的并行執(zhí)行，為了避免死鎖，系統(tǒng)動態(tài)的確定是否分配一個資源給請求的進程。
預(yù)防死鎖：具體的做法是破壞產(chǎn)生死鎖的四個必要條件之一
2：面向?qū)ο蟮娜齻�基本元素，五個基本原則
答：
三個基本元素：
封裝
繼承
多態(tài)
五個基本原則：
單一職責(zé)原則(Single-Resposibility Principle):一個類，最好只做一件事，只有一個引起它的變化。單一職責(zé)原則可以看做是低耦合、高內(nèi)聚在面向?qū)ο笤瓌t上的引申，將職責(zé)定義為引起變化的原因，以提高內(nèi)聚性來減少引起變化的原因。
開放封閉原則(Open-Closed principle):軟件實體應(yīng)該是可擴展的，而不可修改的。也就是，對擴展開放，對修改封閉的。
Liskov替換原則(Liskov-Substituion Principle):子類必須能夠替換其基類。這一思想體現(xiàn)為對繼承機制的約束規(guī)范，只有子類能夠替換基類時，才能保證系統(tǒng)在運行期內(nèi)識別子類，這是保證繼承復(fù)用的基礎(chǔ)。
依賴倒置原則(Dependecy-Inversion Principle):依賴于抽象。具體而言就是高層模塊不依賴于底層模塊，二者都同依賴于抽象;抽象不依賴于具體，具體依賴于抽象。
接口隔離原則(Interface-Segregation Principle):使用多個小的專門的接口，而不要使用一個大的總接口。
3：windows內(nèi)存管理的機制以及優(yōu)缺點
答：
分頁存儲管理基本思想：
用戶程序的地址空間被劃分成若干固定大小的區(qū)域，稱為“頁”，相應(yīng)地，內(nèi)存空間分成若干個物理塊，頁和塊的大小相等�？蓪⒂脩舫绦虻娜我豁摲旁趦�(nèi)存的任一塊中，實現(xiàn)了離散分配。
分段存儲管理基本思想：
將用戶程序地址空間分成若干個大小不等的段，每段可以定義一組相對完整的邏輯信息。存儲分配時，以段為單位，段與段在內(nèi)存中可以不相鄰接，也實現(xiàn)了離散分配。
段頁式存儲管理基本思想：
分頁系統(tǒng)能有效地提高內(nèi)存的利用率，而分段系統(tǒng)能反映程序的邏輯結(jié)構(gòu)，便于段的共享與保護，將分頁與分段兩種存儲方式結(jié)合起來，就形成了段頁式存儲管理方式。
在段頁式存儲管理系統(tǒng)中，作業(yè)的地址空間首先被分成若干個邏輯分段，每段都有自己的段號，然后再將每段分成若干個大小相等的頁。對于主存空間也分成大小相等的頁，主存的分配以頁為單位。
段頁式系統(tǒng)中，作業(yè)的地址結(jié)構(gòu)包含三部分的內(nèi)容：段號 頁號 頁內(nèi)位移量
程序員按照分段系統(tǒng)的地址結(jié)構(gòu)將地址分為段號與段內(nèi)位移量，地址變換機構(gòu)將段內(nèi)位移量分解為頁號和頁內(nèi)位移量。
為實現(xiàn)段頁式存儲管理，系統(tǒng)應(yīng)為每個進程設(shè)置一個段表，包括每段的段號，該段的頁表始址和頁表長度。每個段有自己的頁表，記錄段中的每一頁的頁號和存放在主存中的物理塊號。
二、程序設(shè)計題(40)
1：公司里面有1001個員工，現(xiàn)在要在公司里面找到最好的羽毛球選手，也就是第一名，每個人都必須參賽，問至少要比賽多少次才能夠找到最好的羽毛球員工。
答：兩兩比賽，分成500組剩下一人，類似于歸并排序的方式，比出冠軍后，讓冠軍之間再比，主要是要想想多余的那一個選手如何處理，必然要在第一次決出冠軍后加入比賽組。
2：現(xiàn)在有100個燈泡，每個燈泡都是關(guān)著的，第一趟把所有的燈泡燈泡打開，第二趟把偶數(shù)位的燈泡制反(也就是開了的關(guān)掉，關(guān)了的打開)，第三趟讓第3,6,9....的燈泡制反.......第100趟讓第100個燈泡制反，問經(jīng)過一百趟以后有多少燈泡亮著
答：
1.對于每盞燈，拉動的次數(shù)是奇數(shù)時，燈就是亮著的，拉動的次數(shù)是偶數(shù)時，燈就是關(guān)著的。
2.每盞燈拉動的次數(shù)與它的編號所含約數(shù)的個數(shù)有關(guān)，它的編號有幾個約數(shù)，這盞燈就被拉動幾次。
3.1——100這100個數(shù)中有哪幾個數(shù)，約數(shù)的個數(shù)是奇數(shù)。我們知道一個數(shù)的約數(shù)都是成對出現(xiàn)的，只有完全平方數(shù)約數(shù)的個數(shù)才是奇數(shù)個。
所以這100盞燈中有10盞燈是亮著的。
它們的編號分別是： 1、4、9、16、25、36、49、64、81、100。
3：有20個數(shù)組，每個數(shù)組有500個元素，并且是有序排列好的，現(xiàn)在在這20500個數(shù)中找出排名前500的數(shù)
答：TOP-K問題，用個數(shù)為K的最小堆來解決
4. 字符串左移，void pszStringRotate(char pszString, intnCharsRotate),比如ABCDEFG，移3位變DEFGABC，要求空間復(fù)雜度O(1)，時間復(fù)雜度O(n)
三、系統(tǒng)設(shè)計題(30)
現(xiàn)在有一個手機，手機上的鍵盤上有這樣的對應(yīng)關(guān)系，2對應(yīng)"abc",3對應(yīng)"def".....手機里面有一個userlist用戶列表，當(dāng)我們輸入942的時候出來拼音的對應(yīng)可能是“xia”，“zha”，“xi”，“yi”等，當(dāng)我們輸入9264的時候出來是yang，可能是“樣”，“楊”，“往”等，現(xiàn)在我們輸入一個字符串?dāng)?shù)字，比如926等，要在電話簿userlist中查找出對應(yīng)的用戶名和電話號碼并返回結(jié)果。
C++語言: 電話號碼對應(yīng)的英語單詞(注意此題的非遞歸做法)
#include
#include
#define N 4 //電話號碼個數(shù)
using namespace std;
char c[][10] = {"","","ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ"};//存儲各個數(shù)字所能代表的字符
int number[N] = {2, 4 ,7, 9}; //存儲電話號碼
int total[10] = {0, 0, 3, 3, 3, 3, 3, 4, 3, 4}; //各個數(shù)組所能代表的字符總數(shù)
int answer[N]; //數(shù)字目前所代表的字符在其所能代表的字符集中的位置,初始為0
void Search(int number, int n); //非遞歸的辦法
void RecursiveSearch(int number, int cur, char ps, int n); //遞歸的辦法
int main()
{
//Search(number, N);
char ps[N+1] = {0};
RecursiveSearch(number, 0, ps, N);
return 0;
}
void Search(int number, int n)
{
int i;
while(1)
{
for(i=0; i
printf("%c", c[number[i]][answer[i]]);
printf("\n");
int k = n-1; //用k和while循環(huán)來解決擴展性問題,模擬了遞歸
while(k >= 0)
{
if(answer[k] < total[number[k]]-1)
{
++answer[k];
break;
}
else
{
answer[k] = 0;
--k;
}
}
if(k < 0)
break;
}
}
/遞歸的解法: number為存儲電話號碼的數(shù)組,pos為當(dāng)前處理的數(shù)字在number中的下標(biāo),初始為0
ps為一外部數(shù)組,用于存放字母,n代表電話號碼的長度(個數(shù))
此遞歸的方法好理解,比上面非遞歸的辦法好寫易懂
/
void RecursiveSearch(int number, int pos, char ps, int n)
{
int i;
for(i=0; i
{
ps[pos] = c[number[pos]][i];
if(pos == n-1)
cout<
else
RecursiveSearch(number, pos+1, ps, n);
}
}
