算法设计基础题目 (1).doc

结构体方面的题目
1、定义一个结构体变量（包括年、月、日），编程序，要求输入年月日,计算并输出该日
在本年中第几天。注意本题一定要定义结构体变量，否则本实验成绩无效。
Input
输入三个整数(并且三个整数是合理的,既比如当输入月份的时候应该在1 至12 之间，
不应该超过这个范围)否则输出Input error!
Output
输出一个整数.既输入的日期是本月的第几天。
Sample Input
1985 1 20
2006 3 12
Sample Output
20
71

2、假设一个班有n(n<=50)个学生，每人考m(m<=5)门课，求每个学生的平均成绩和每门课的平均成绩，并输出各科成绩均大于等于平均成绩的学生数量。
Input
输入数据有多个测试实例，每个测试实例的第一行包括两个整数n和m，分别表示学生数和课程数。然后是n行数据，每行包括m个整数（即：考试分数）。
Output
对于每个测试实例，输出3行数据，第一行包含n个数据，表示n个学生的平均成绩，结果保留两位小数；第二行包含m个数据，表示m门课的平均成绩，结果保留两位小数；第三行是一个整数，表示该班级中各科成绩均大于等于平均成绩的学生数量。
每个测试实例后面跟一个空行。
Sample Input
2 2
5 10
10 20
Sample Output
7.50 15.00
7.50 15.00
1

3、构建简单的手机通讯录（最多容纳250名联系人的信息），通讯录中联系人的基本信息包括：姓名、手机号码、办公室电话、邮箱地址、住址等信息。实现根据姓名查询联系人功能。

4、大学生运动会成绩管理系统，记录某校运动会上的运动项目，包括50、100、200，400，1500米，跳高，跳远，标枪，铅球铁饼等。实现按团体总分高低排出院系团体名次及总分。

5、个人帐簿管理系统记录某人的全部日常各项开支情况，包括食品消费，房租，子女教育费用，水电费，医疗费等。要求输出某一年中每月的开支排列（按金额从大到小进行排序）。

关于链表方面的题目

1、 检测两条链表是否存在相同元素，假设有两条带头结点的链表A、B，A中存储的数据有10、12、15、39、78、28，B中存储的数据有12、13、24、39、56、78，则输出39、78。
2、在双向链表中，A有一个指针指向了节点B，同时，B又有一个指向A的指针。这样不仅能从链表头节点的位置遍历整个链表所有节点，也能从链表尾节点开始遍历所有节点。对于给定的一列数据，按照给定的顺序建立双向链表，按照关键字找到相应节点，输出此节点的前驱节点关键字及后继节点关键字。
Input
第一行两个正整数n（代表节点个数），m（代表要找的关键字的个数）。接下来n行每行有一个整数为关键字key（数据保证关键字在数列中没有重复）。接下来有m个关键字，每个占一行。
Output
对给定的每个关键字，输出此关键字前驱节点关键字和后继节点关键字。如果给定的关键字没有前驱或者后继，则不输出。给定关键字为每个输出占一行。

3、通常在数学中对一元n次多项式可表示成如下形式：

本题目要求采用带头结点的链表实现两个一元多项式的加运算，运算结果存储在新的链表中，并打印运算。

4、利用带头结点的单链表实现长整数的加法运算，假设有2个带头结点的链表存储了2个大整数A=1234567890123456789，B=98765432109876543210（链表中的每个节点存放大整数中的一位数字），求A+B的结果，并显示。（结果存放在一个新的大整数链表中）

5、利用带头结点的单链表实现长整数的减法运算，假设有2个带头结点的链表存储了2个大整数A=1234567890123456789，B=98765432109876543210（链表中的每个节点存放大整数中的一位数字），求A-B的结果，并显示。（结果存放在一个新的大整数链表中）

递归函数
1、找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5，r=3的所有组合为： （1）5、4、3 （2）5、4、2 （3）5、4、1 （4）5、3、2 （5）5、3、1 （6）5、2、1 （7）4、3、2 （8）4、3、1 （9）4、2、1 （10）3、2、1

2、将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。
正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。
例如正整数6有如下11种不同的划分：
6；
5+1；
4+2，4+1+1；
3+3，3+2+1，3+1+1+1；
2+2+2，2+2+1+1，2+1+1+1+1；
1+1+1+1+1+1。
Input
第一行是测试数据的数目M（1<=M<=10）。以下每行均包含一个整数n（1<=n<=10）。
OutPut
输出每组测试数据有多少种分法。
Sample Input
1
6
Sample Output
11

3、 计算斐波那契（Fibonacci）数列的第n项函数fib（n）。
斐波那契数列为：0、1、1、2、3、……，即：
fib(0)=0;
fib(1)=1;
fib(n)=fib(n-1)+fib(n-2)（当n>1时）。

4、猴子分桃问题
有1堆桃子共 m 个，由 n 只猴子分配这些桃子。每次到达桃子堆放地的猴子只有1只，而且每个猴子都会平均分 1 次桃子。
第1只到达的猴子将桃子平均分成 n 等份，但发现多 k ( k < n )个，于是，将多余的k个扔掉，然后拿走其中的1份。
第2只猴子同样将剩余的桃子又分成 n 等份，也发现多 k 个，并同样将多余的 k 个扔掉，然后拿走其中1份。
之后的每只猴子都这样（将剩余的桃子又分成 n 等份，也发现多 k 个，并将多余的 k 个扔掉，然后拿走其中1份）。
现在假设最后一只猴子分配后至少可以拿走1个桃子，请根据输入的 n 和 k值，编程计算最小的 m。（比如，n=3，k=1，则最小的m是25，最后一个分得3个）
Input
输入由键盘输入，共1行
这一行由两个整数n和k组成，分别代表n只猴子和多余的k个桃子
output
输出只有一行，为所计算的m
Sample Input
3 1
Sample Output
25

5、一个射击运动员打靶，靶一共有10环，连开10枪打中90环的可能性有多少种？请用递归算法编程实现。解析：靶上一共有10种可能——1环到10环，还有可能脱靶，那就是0环，加在一起共11种可能。这是一道考循环和递归的面试题。我们在这个程序中将利用递归的办法实现打靶所有可能的演示，并计算出结果。

6、八皇后问题是一个古老而著名的问题，在8×8格的国际象棋盘上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。使用递归实现n皇后问题。

排序及综合应用
1、输入三个字符后，按各字符的ASCII码从小到大的顺序输出这三个字符
Input
输入数据有多组，每组占一行，有三个字符组成，之间无空格。
Output
对于每组输入数据，输出一行，字符中间用一个空格分开。
Sample Input
qwe
asd
zxc
Sample Output
e q w
a d s
c x z

2、众所周知,外国人的名是在姓的前面的，所以若要普通的按字符串字典排序不符合外国人的习惯，现在要求你写个符合外国人习惯的排序方法
Input
第一行为一个整数N，表示下面有N组测试数据
第二行含有1个整数M，表示该组测试数据有M个名字
接下来M行每行不超过100个字符
Output
对于每组测试数据,输出排序后的姓名序列,每组测试数据后面加一个空行
Sample Input
1
3
Tom Smith
Tim Alice
Marry Alice

Sample Output

Marry Alice
Tim Alice
Tom Smith

3、输入一行数字，如果我们把这行数字中的‘5’都看成空格，那么就得到一行用空格分割的若干非负整数（可能有些整数以‘0’开头，这些头部的‘0’应该被忽略掉，除非这个整数就是由若干个‘0’组成的，这时这个整数就是0）。你的任务是：对这些分割得到的整数，依从小到大的顺序排序输出。
Input
输入包含多组测试用例，每组输入数据只有一行数字（数字之间没有空格），这行数字的长度不大于1000。
输入数据保证：分割得到的非负整数不会大于100000000；输入数据不可能全由‘5’组成。
Output
对于每个测试用例，输出分割得到的整数排序的结果，相邻的两个整数之间用一个空格分开，每组输出占一行。

Sample Input
0051231232050775

Sample Output
0 77 12312320

4、 明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤1000），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。
Input
输入有2行，第1行为1个正整数，表示所生成的随机数的个数：N
第2行有N个用空格隔开的正整数，为所产生的随机数。
Output
输出也是2行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

Sample Input
10
20 40 32 67 40 20 89 300 400 15

Sample Output
8
15 20 32 40 67 89 300 400

5、 给定一个长度为N(0<n<=10000)的序列，保证每一个序列中的数字a[i]是小于maxlongint的非负整数 ，编程要求求出整个序列中第k大的数字减去第k小的数字的值m，并判断m是否为质数。(0<k<=n)
Input
第一行为2个数n，k（含义如上题）
第二行为n个数，表示这个序列
Output
如果m为质数则
第一行为'Yes' ,否则为'No'(没有引号）
第二行为这个数m
Sample Input
5 2
1 2 3 4 5

Sample Output
Yes
2