2012圖像所復試編程試卷(回憶)

snowhorse712

滿分20分

學術一,二,三題/ 專業一,二,四題

要求添加足夠多的注釋

一, 精確計算階乘.

一個32 位整型變量無法精確表示大數的階乘, 但一個整型數組卻可表示.

算法思路: 當階乘結果為不超過10的4次方的十進制正整數時, 可用一個整型數組( int nFactorial[4] )來依次存放階乘的每一位數字. 比如, 5!=120可被記錄為nFactorial[0]= 0, nFactorial[1] = 2, nFactorial[2] = 1, nFactorial[3] = 0.

當已計算出k的階乘, 要計算(k+1)的階乘時, 將記錄k的階乘的數組的每一位都與(k+1)相乘, 乘積依然存在數組的對應位上. 最后, 從最低位開始, 依次向高位循環處理每個位中大于9的數. 若數大于9，則需要進位. 將數的10的倍數進到高一位上，將數的小于10的余數存在原來的位中.一直到所有位中的數都小于10為止.

(1)(6分) 按此思路, 當已知階乘結果為一個不超過10的1000次方的十進制整數時, 寫出計算正整數階乘的完整C/C++代碼.

輸入: 鍵盤輸入一個正整數

輸出: 顯示輸入正整數的階乘

(2)(2分) 完善代碼, 實現鍵盤輸入是否滿足要求的檢查功能.

(3)(2分) 寫出幾種測試用例.

二, 有一個浮點型數組記錄了1000個浮點數(float fData[1000]).

(1)(3分) 編寫C/C++代碼, 求出這1000個數中最大的10個數.

(2)(3分) 寫出能實現從1000億個數中尋找最大的10個數的算法思路.

三, 已知一個指向單向鏈表的某個非頭非尾節點的指針(node* pCurrent).  pCurrent 指向的地址中僅保存2個指針, 一個是指向下一個節點的Next指針(pCurrent-> Next), 另一個是指向節點本身數據的Data指針(pCurrent-> Data). 編寫一個C/C++函數, 實現以下功能:

(1)(2分) 保留鏈表的原有順序,在原鏈表中刪除這個已知節點的下一個節點.

(2)(2分) 保留鏈表的原有順序,在原鏈表中刪除這個已知節點.

四, 異或運算的應用.

(1) (2分) 列舉異或運算的性質.

(2) (2分) 已知一個記錄了1000個整數的整數型數組. 將這1000個整數打亂順序后,只將其中的999個整數記錄在另一個數組中.請利用異或運算的性質編寫一個C/C++函數, 找出缺少的那一個整數.

snowhorse712

第一題,(1)初始化數組, 鍵盤輸入, 按照思路循環計算, 進位,輸出結果. 輸出結果時,高位中的多余的零應去掉,然后,從首個有效位到最低位依次輸出數組.
(2)用scanf("%s", cs)來接受鍵盤輸入的字符串, 再用atoi()將字符串轉換為整數n,  再用itoa()將n轉換為字符串css, 用strcmp()比較cs和css, 相同說明輸入的是整數,不同則非法. 但不知如何確定輸入的整數是否太大...感覺要用到數學知識(斯特靈公式...)...
(3)測試用例,
3.1 下邊界0!=1!=1,
3.2 合法值5!=120, 11!=...,
3.3 上邊界460!, 461!(結果為1000位10進制整數的上界), 462!(越界)
3.4 非法值 (abc)!提示非法, (1.3)!, (-0)!提示非法,
3.5 退出條件 (-2)!, (-1)!...
等...


補充內容 (2012-4-12 14:45):
450就越界鳥...449!有998位

snowhorse712

第二題,(1)部分排序.
(2)分組,1000個一組, 每組求前10. 然后,每 100個組的結果再合并為一組, 每組再求前10, ...,直到最后求出整體前10.
疑問:前10個數...應該數值可以相同哈

snowhorse712

第三題,(1) node* pTemp = pCurrent->Next; pCurrent->Next = pTemp->Next; delete(pTemp->Data);pTemp->Data=NULL;delete(pTemp);pTemp=NULL;

kunzi55

總的來說，復試編程還是很考能力的。 相比微機就簡單多了全是概念  哈哈   

snowhorse712

編程初看,都能做.但要得高分,還真要能力.
第三題(2),應該是不知道鏈表的頭.否則,和第一題解法一樣就行了. 但不知道頭咋知道指向pCurrent的指針哪...
昨晚想了一個辦法.
... pTemp0 = pCurrent->Data;(這里題目缺少Data指針的具體類型哈...)
node* pTemp1 = pCurrent->Next;
pCurrent->Next = pTemp1->Next;
pCurrent->Data = pTemp1->Data;
if(pTemp0 != NULL){delete pTemp0; pTemp0 = NULL;}
if(pTemp1->Data != NULL){delete pTemp1->Data; pTemp1->Data = NULL;}
if(pTemp1 != NULL){delete pTemp1; pTemp1 = NULL;}

補充內容 (2012-4-11 11:03):
這個鏈表應該沒有環,否則,刪某個節點,可能會出問題..

snowhorse712

第四題(1)a^0=a, a^a = 0, a^b=b^a, a^(b^c)=(a^b)^c[同數異或為0,數異或0還為該數,異或運算可交換,異或運算滿足結合律]
(2)int MyFind(int nArray0[1000], int nArray1[999])
{
int nResult = nArray0[0];
int i;
for(i=1;i<1000;i++)
{nResult ^= nArray0[i];}
for(i=0;i<999;i++)
{nResult ^= nArray1[i];}
return nResult;
}