2006年11月ATI(下屬AMD)筆試題及答案
ATI筆試題共有8個題目： 1：windows API裡面用於執行緒同步的有哪些？
答案：共有12個API
1) 臨界區共有五個API
(1)InitializeCriticalSection
此函式用於設定臨界區物件，即對臨界區物件初始化。該函式必須在執行EnterCriticalSection前呼叫。單個程序的執行緒可以為互斥同步使用臨界區物件。程序負責分配臨界區物件使用的記憶體，可以通過對CRITICAL_SECTION型別變數的定義和使用來實現。
(2)EnterCriticalSection
此函式用於等待指定的臨界區物件的所有權。授予呼叫執行緒所有權後，該函式返回，臨界區物件在單個程序的各執行緒內強制互斥同步。在執行緒擁有臨界區物件以後，對同一個臨界區物件應呼叫EnterCriticalSection函式，防止發生死鎖。在退出臨界區後用LeaveCriticalSe- ction函式使其他執行緒可以進入臨界區。
(3)TryEnterCriticalSection
此函式用沒有阻塞的方式試圖進入一個臨界區。若函式呼叫成功，則進行呼叫的執行緒擁有對臨界區的所有權，否則立即返回。
(4)LeaveCriticalSection
此函式用於釋放對臨界區物件的所有權。每次執行緒對同一個物件執行EnterCriticalSection或TryEnterCriticalSection都必須呼叫
LeaveCriticalSection函式。
(5)DeleteCriticalSection
此函式用於刪除一個臨界區物件，釋放所有與不再為自己所控制的臨界區物件有關的資源。一個臨界區物件被刪除，就不能再對其呼叫函式EnterCriticalSection，函式TryEnterCriticalSection和函式LeaveCriticalSection了。
2) 互斥和訊號量共有7個API
(1) CreateMutex
此函式用於建立命名或未命名的互斥物件。這些互斥物件用於程序同步，當互斥物件不為任何執行緒擁有時才處於訊號態，否則將處於非訊號態。若要執行緒釋放其所有權，則執行緒在每次互斥物件處於非訊號態時都呼叫函式ReleaseMutex。當不再需要互斥物件時可以使用函式CloseHandle來關閉互斥物件。當所有互斥物件的開啟控制代碼都關閉時，就刪除互斥物件。
(2)OpenMutex
用於返回存在的已命名互斥物件的控制代碼。該函式允許多個程序開啟同一個互斥物件的控制代碼。該函式的呼叫一定要在函式CreateMutex建立互斥物件之後，當不需要控制代碼時可以呼叫CloseHandle函式。
(3)ReleaseMutex
此函式用於釋放互斥物件。若函式呼叫成功，互斥物件處於訊號態。
(4)CreateSemaphore
此函式用於建立已命名或未命名的訊號量物件，訊號量用計數器實現同步。每次取訊號量時（可利用函式WaitForSingleObject來取），訊號量計數器遞減；每次ReleaseSemaphore釋放訊號量值時，訊號量計數器遞增。計數永遠不會小於0或大於在lSemMaxCount引數中定義的值。
(5)OpenSemaphore
用於開啟一個已經存在的命名的訊號量物件。該訊號量必須是函式CreateSemaphore建立的。如果不再需要時，可以用函式CloseHandle關閉返回的控制代碼。
(6)WaitForSingleObject
此函式僅當在引數列表中指定的物件處於訊號態或超過了超時間隔時，該函式才返回。
(7)ReleaseSemaphore
用來遞增訊號量的計數。對於CreateSemaphore函式建立的物件使用，計數可以達到設定的最大計數值。
2: windows核心記憶體分為paged memory和 nonpaged memory，請問有什麼區別？
答案：
paged memory：是指可以分頁的'記憶體，可以交換到硬碟檔案上。
Nonpaged memory：不可分頁，也就是不能交換到硬碟檔案上。有些記憶體，比如驅動程式，核心程式碼是不允許交換出去的，應該常駐記憶體，就使用nonpaged memory。
3：請問什麼情況下，cache中只放指令（資料直接從儲存器存取）比cache中放資料和指令的效率高？
答案：計算密集型 cache中只放指令（資料直接從儲存器存取）比cache中放資料和指令的效率高，可以充分利用指令的區域性原理。
4：RISC和CISC等其他指令集相比有哪些優點，請至少舉出5個。
答案：
(1)定址方式少且簡單，一般為2—3種，最多不超過4種，絕不出現儲存器間接定址方式。
(2)指令集中的指令數目一般少於100種，指令格式一般少於4種。
(3)指令功能簡單，控制器多采用硬佈線方式，以期更快的執行速度。
(4)平均而言，所有指令的執行時間為一個處理時鐘週期。
(5)指令格式中用於指派整數暫存器的個數不少於32個，用於指派浮點數暫存器的個數不少於16個。
(6)強調通用暫存器資源的優化使用。
(7)支援指令流水並強調指令流水的優化使用。
5：選擇題：如果兩個節點x，y，preorder遍歷，x在y之前，postorder遍歷,x在y之後，請問x，y的關係為：
A x是y的左兄弟 B x是y的右兄弟
C x是y的祖先 D x是y的後裔
答案：C
6：請問下面程式如果執行會出現什麼結果？如果有錯誤請指出並改正。
include
include
class mystring{
public:
mystring(){
m_str=NULL;
}
mystring(mystring& str){
if(m_str!=NULL){
delete []m_str;
}
m_str=new char[strlen(str.m_str)];
strcpy(m_str,str.m_str);
}
mystring & operator=(const char *str){
if(m_str!=NULL){
delete []m_str;
}
m_str=new char[strlen(str)+1];
strcpy(m_str,str);
}
~mystring(){
if(m_str!=NULL){
delete m_str;
}
}
private:
char *m_str;
};
int main(){
mystring str1;
str1="hello world";
mystring str2;
str2=str1;
mystring str3=str2;
return 0;
}
~
答案：
程式執行會出現記憶體釋放錯誤
錯誤共有四處，分別在下面改正的程式碼中標出。
include
include
class mystring{ public: mystring(){ m_str=NULL; } mystring(mystring& str){
/*if(m_str!=NULL){ delete []m_str; }*/
//錯誤1，因為m_str沒有被初始化，所以此處可能為NULL，也可能不為NULL，如果不為null，則會出錯，因為m_str是一個隨機的值。 m_str=new char[strlen(str.m_str)+1];
//錯誤2：長度應該＋1 strcpy(m_str,str.m_str); }
mystring & operator=(mystring& str){
//錯誤3：缺少賦值過載函式 if(m_str!=NULL){ delete []m_str; } m_str=new char[strlen(str.m_str)+1];
//錯誤2：長度應該＋1 strcpy(m_str,str.m_str); } mystring & operator=(const char *str){ if(m_str!=NULL){ delete []m_str; } m_str=new char[strlen(str)+1]; strcpy(m_str,str); } ~mystring(){ if(m_str!=NULL){ delete []m_str;
//錯誤4：解構函式中，應該析構陣列 } } private: char *m_str; }; int main(){ mystring str1; str1="hello world"; mystring str2; str2=str1; mystring str3=str2; return 0; } ~
7：100個乒乓球取勝之道，A，B兩個人輪流拿，A先拿，一次只能拿［1,5］個，獲勝者為拿到最後一個球的人。請問A第一次該拿幾個？以後又該怎麼拿，才能夠確保獲勝？
答案：A先拿4個，然後B拿，設B拿x個，則每次A拿6-x個即可。
8：有編號1－50的人，依次排列，然後單號出列，然後剩下的人重新編號，單號出列，依次類推，最後剩下一個人，請問這個人原來編號是多少號？如果是每一次雙號出列，請問這個人原來編號是多少？
答案：單號出列：32號
雙號出列：1號