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號