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