1.簡(jiǎn)述數(shù)據(jù)庫(kù)以及線程死鎖產(chǎn)生的原理及必要條件，簡(jiǎn)述如何避免死鎖。

1）互斥條件：指進(jìn)程對(duì)所分配到的資源進(jìn)行排它性使用，即在一段時(shí)間內(nèi)某資源只由一個(gè)進(jìn)程占用。如果此時(shí)還有其它進(jìn)程請(qǐng)求資源，則請(qǐng)求者只能等待，直至占有資源的進(jìn)程用畢釋放。

 

2）請(qǐng)求和保持條件：指進(jìn)程已經(jīng)保持至少一個(gè)資源，但又提出了新的資源請(qǐng)求，而該資源已被其它進(jìn)程占有，此時(shí)請(qǐng)求進(jìn)程阻塞，但又對(duì)自己已獲得的其它資源保持不放。

 

3）不剝奪條件：指進(jìn)程已獲得的資源，在未使用完之前，不能被剝奪，只能在使用完時(shí)由自己釋放。

4）環(huán)路等待條件：指在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程——資源的環(huán)形鏈，即進(jìn)程集合{P0，P1，P2，···，Pn}中的P0正在等待一個(gè)P1占用的資源；P1正在等待P2占用的資源，……，Pn正在等待已被P0占用的資源。

如何避免：破壞上述四個(gè)必要條件之一。

 

2.請(qǐng)列舉面向?qū)ο笤O(shè)計(jì)的三個(gè)基本要素和五種主要設(shè)計(jì)原則。

答：三個(gè)基本要素：繼承、封裝、多態(tài)

主要設(shè)計(jì)原則：?jiǎn)我宦氊?zé)原則、里氏代換原則、依賴倒置原則、接口隔離原則、迪米特原則、開放-封閉原則。具體參考：

http://blog.csdn.net/kuzuozhou/article/details/8043265

 

3.簡(jiǎn)述windows內(nèi)存管理的幾種方式及優(yōu)缺點(diǎn)。

 

二、算法和程序設(shè)計(jì)

1.公司組織一次羽毛球比賽，采用淘汰機(jī)制，假設(shè)公司有1001個(gè)人，如果要評(píng)出“公司羽毛球第一高手”的稱號(hào)，至少需要進(jìn)行多少場(chǎng)比賽？請(qǐng)簡(jiǎn)述設(shè)計(jì)過程，并寫出代碼模擬比賽過程。

 

2.一百個(gè)燈泡排成一排，第一輪將所有燈泡打開；第二輪每隔一個(gè)燈泡關(guān)掉一個(gè)。即排在偶數(shù)的燈泡被關(guān)掉，第三輪每隔兩個(gè)燈泡，將開著的燈泡關(guān)掉，關(guān)掉的燈泡打開。依次類推，第100輪結(jié)束的時(shí)候，還有幾盞燈泡亮著。

思路： 

 

1．對(duì)于每盞燈，拉動(dòng)的次數(shù)是奇數(shù)時(shí)，燈就是亮著的，拉動(dòng)的次數(shù)是偶數(shù)時(shí)，燈就是關(guān)著的。 

2．每盞燈拉動(dòng)的次數(shù)與它的編號(hào)所含約數(shù)的個(gè)數(shù)有關(guān)，它的編號(hào)有幾個(gè)約數(shù)，這盞燈就被拉動(dòng)幾次。 

3．1—100這100個(gè)數(shù)中有哪幾個(gè)數(shù)，約數(shù)的個(gè)數(shù)是奇數(shù)。 

 

我們知道：一個(gè)數(shù)的約數(shù)都是成對(duì)出現(xiàn)的，只有完全平方數(shù)約數(shù)的個(gè)數(shù)才是奇數(shù)個(gè)。 

 

所以這100盞燈中有10盞燈是亮著的，它們的編號(hào)分別是：1、4、9、16、25、36、49、64、81、100

 

研究生三年級(jí)的解法是這樣的：

1．對(duì)于每盞燈，拉動(dòng)的次數(shù)是奇數(shù)時(shí)，燈就是亮著的，拉動(dòng)的次數(shù)是偶數(shù)時(shí)，燈就是關(guān)著的。 

2．每盞燈拉動(dòng)的次數(shù)與它的編號(hào)所含約數(shù)的個(gè)數(shù)有關(guān)，它的編號(hào)有幾個(gè)約數(shù)，這盞燈就被拉動(dòng)幾次。 

3．1—100這100個(gè)數(shù)中有哪幾個(gè)數(shù)，約數(shù)的個(gè)數(shù)是奇數(shù)。 

 

 

3.假定有20個(gè)有序數(shù)組，每個(gè)數(shù)組有500個(gè)數(shù)字，數(shù)字類型32位uint數(shù)值，現(xiàn)在需要取出這10000個(gè)數(shù)字中最大的500個(gè)，怎么做？

 

4. 字符串左移，void *pszStringRotate(char *pszString, intnCharsRotate),比如ABCDEFG，移3位變DEFGABC，要求空間復(fù)雜度O（1），時(shí)間復(fù)雜度O（n）

三、系統(tǒng)設(shè)計(jì)題

手機(jī)上通常采用九鍵鍵盤輸入。即：1-9個(gè)數(shù)字分別對(duì)應(yīng)一定的英文字母（如：2對(duì)應(yīng)ABC, 3對(duì)應(yīng)DEF，...)，因此，用戶可以方便的輸入中文內(nèi)容。比如，用戶輸入“926”，可以對(duì)應(yīng)“WXYZ”，“ABC"和”MNO“的一系列組合”WAN”，“YAN"、”ZAO“等，這些對(duì)應(yīng)“萬”，“嚴(yán)”，“早”等漢字的中文拼音。

要求我們把這樣的輸入方式應(yīng)用在我們的手機(jī)聯(lián)系人查找功能上。有一個(gè)聯(lián)系人列表UserList，記錄了（姓名，手機(jī)號(hào)）這樣的組合，通過輸入的數(shù)字字符串NumStr，按照下面的規(guī)則把對(duì)應(yīng)的聯(lián)系人查找出來，返回一個(gè)ReaultList。

規(guī)則：

1.手機(jī)號(hào)能連續(xù)部分匹配輸入的數(shù)字字符串NumStr。如輸入NumStr=926，則手機(jī)號(hào)為13926811111會(huì)被查出來；

2.聯(lián)系人姓名中的漢字轉(zhuǎn)化成拼音后能夠連續(xù)匹配輸入數(shù)字字符串NumStr對(duì)應(yīng)的英文字母組合，如：輸入NumStr=926，則聯(lián)系人“王二”、“萬事通”會(huì)被查找出來。因?yàn)?ldquo;王二”的“王”的拼音“WANG”中含有“WAN”，和“926”能匹配。

輸入：

聯(lián)系人列表UserList<UserName, PhoneNo>；漢字拼音射射表Dict，數(shù)字拼音字符串NumStr。

輸出：

符合規(guī)則的聯(lián)系人列表ResultList<UserName, PhoneNo>。