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

snowhorse712

滿分20分

學術一,二,三題/ 專業(yè)一,二,四題

要求添加足夠多的注釋

一, 精確計算階乘.

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

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

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

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

輸入: 鍵盤輸入一個正整數(shù)

輸出: 顯示輸入正整數(shù)的階乘

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

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

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

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

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

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

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

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

四, 異或運算的應用.

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

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

snowhorse712

第四題(1)a^0=a, a^a = 0, a^b=b^a, a^(b^c)=(a^b)^c[同數(shù)異或為0,數(shù)異或0還為該數(shù),異或運算可交換,異或運算滿足結合律]
(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;
}

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;}

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

kunzi55

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

snowhorse712

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

snowhorse712

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

snowhorse712

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


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