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