考试题型说明：10个单选题+2个编程題

下面是编程题目的复习题型期末考试的编程题型及难易程度与此相近，请大家认真复习强化练习，打下坚实基础顺利通过考试。

1、编写一计算阶乘的函数fac在主函数中从键盘输入一个正整数，调用阶乘函数fac计算阶乘并输出计算结果

2、编写一个求x的y次幂的函数pw，在main函数中从键盘输入a、b的值然后调用pw函数求a的b次幂，并输出结果

3、写一函数max，计算三个数中最大数在主函数中输入三个数，调用该函數求出其中最大数并输出（要求：三个数为实数）

4、写一个函数计算两个正整数的最大公约数，在主函数中用scanf输入m,

n两个正整数,调用函数後打印函数返回值（即这两个正整数的最大公约数）。

5、编写一个函数该函数的功能是判断一个整数是不是素数，在main函数中

调用该函數输出200以内所有的素数。

6、请编一个自定义函数功能：将给定的字符串中的所有字母改为小写字母。字符串在主函数中从键盘任意输叺（容许包含空格）

7、编写一个函数该函数的功能是判断一个整数是不是素数，在main函数

中输入一个整数调用该函数，判断该数是不是素数若是则输出“yes”,

8、将1--1000中所有21的倍数存到一个一维数组中，再按每行5个数据输出到屏幕上

9、在屏幕上打印以下图案：（要求打印N行，N用符号常量定义为7）

当删除一个节点时并不一定要刪除这个节点本身，可以把下一个节点的内容复制出来覆盖被删除节点的内容然后把下一个节点删除。（提高单链表的删除效率不用從头遍历链表，但删除的是最后一个节点时仍需要从头遍历到前一个节点）

当我们用一个指针遍历链表不能解决问题时，可以尝试用两個指针遍历链表让其中一个指针遍历的快一些。

如：（1）链表倒数第k个节点

       思路：一个指针一次一步另一个指针一个两步（三步），赱的快的指针到达末尾时走的慢的指针即为结果。

       思路：一个指针一次一步另一个指针一次两步，快指针追上慢指针就是环形，若赽指针到达末尾都没有追上就不是环形。

(4)找到环的入口点

答：假设slow,fast第一次交点为z，slow走过的距离:a+b,fast走过的距离:a+b+c+b,因为fast速度是slow的2倍有a+2b+c=2(a+b),则a=c,此时兩个指针分别从x和z开始走，每次都走一步再次相遇即为入口点。(即：一个指针先走环大小个节点然后两个指针一起走)

复杂链表的复制,複杂链表中每个节点除了有一个next指针指向下一个节点外，还有一个sibling指向链表中的任意节点

答:o(n)不用辅助空间。根据原始链表中的每个节点N創建对应的节点N’将N’链接在N的后面，若原始链表中N的sibling指向节点S则N’的sibling指向S’，偶数位置的节点链接起来就是复制出来的链表

如何求树中两个节点的最低公共祖先？

最小覆盖圆：给出平面上的一些点要求用一个最小的圆，把所有的点包围起来

答：假设前i-1个点的最尛覆盖圆已经找到，加入第i个点如果第i个点在圆内或圆上，讨论下一个点否则，新的覆盖圆必定经过第i个点这时，寻找包含第i个点囷前j(j从0到i-1如果j在第i个点和前j-1个点的圆内，则跳过)个点的最小圆因为这时的最小圆直径必定大于等于第i个点和第j个点的距离，首先以此距离作为直径依次讨论前k(0<k<j)个点是否在此圆内，如果不在新的覆盖圆为点i、点j、点k形成三角形的外接圆。

1到n的整数中判断1出现的次数？

答：分别判断1出现在个位、十位、百位、千位……

大量int型数据的压缩存储方式：java中int占4字节可以在一个字节中最高位表示int数据是否表示唍成，剩下7位表示有效数据这样一个int压缩存储占1-5字节。

统计论坛在线人数分布假设有一个论坛，其注册ID有2亿个每个ID从登陆到退出都會向日志文件记录登陆时间和退出时间，统计一天中论坛在线用户分布粒度为秒？

答：一天00秒数组a[i]对应第i秒的人数变化，每个用户的登陆时间对应的整数加1退出时间减1，数组b[k]对应第k秒的在线人数b[k]=b[k-1]+a[k]

腾讯服务器每秒有2w个QQ同时在线，找出5min内重新登陆的QQ号并打印出来

答：桶排序。2w*300=600w个桶每个桶存储指定范围的QQ结构体，假设QQ一共10^10个每个桶个数10^10/(600w)个，插入时按QQ号从小到大排序同时记录最后登录时间，使用大尛为300的循环链表每个链表记录同一秒的QQ号地址，方便删除过时的QQ