算法设计习题整理112.doc

个人收集整理 勿做商业用途
类型
题目序号
题目内容
难度等级（四等）
第几次上机
基本应用
1.
输入三个系数、求一元二次方程ax2+bx+c=0的根,要求考虑a=0、实数根和复数根的情况
3
1
2.
有三个整数a，b，c,由键盘输入，输出其中最大者
1
1
3.
有分段函数：当x〈-5时，y=x+10； 当-5≤x≤5时，y=x/2;当x〉5时，y=2x—10。
编一程序，输入x的值，输出y的值
1
1
4.
输入一行字符，将此字符串中最长的单词输出
3
1
5.
输入三角形的三边长，求三角形面积.求三角形面积的公式为area=sqrt(s(s-a)（s-b)（s—c））,其中s=（a+b+c)/2。
1
1
6.
输入学生的百分制成绩，将学生的成绩转换成五分制输出
（先保留，学生分题的时候用了序号）
1
1
7.
编写程序，判断某一年是否是闰年.(闰年的条件是：能被4整除，但是不能被100整除，或者可以被400整除
1
1
8.
一个球从X米高度自由落下，每次落地后又反跳回原高度的一半，再落下，再反弹。求它在第10次落地时共经过多少米
2
1
9.
编程求圆面积、圆周长。要求圆半径由键盘输入，输出时要求有文字说明，取小数点后两位数字
1
1
10.
输入一个华氏温度,要求输出摄氏温度，输出时要求有文字说明，取小数点后两位数字。公式为c=5/9(f-32)
1
1
11.
用pi4≈1—1/3+1/5—1/7+..。公式求pi的近似值，直到某一项的绝对值小于10的-6次方为止
2
1
12.
输入一个字符，判断它是否是大写字母，如果是，将它转换成小写字母；如果不是，不转换。然后输出最后得到的字符
2
1
13.
输入整数n，求数列1+1/2+1/3+1/4+1/5+。..1/n结果
2
1
14.
求S=a+aa+aaa+。..+aa。..a（n个a)之值.其中a是一个数字，n代表a的位数.例如：2+22+222+2222+22222（此时n为5)，n由键盘输入
2
1
15.
给出一百分制的成绩，要求数出成绩等级’A’,’B'，’C’,'D’,’E’；90分以上为'A'， 80~89分为‘B’,70~79分为‘C’,60~69分为‘D’，60分以下为‘E'。
1
1
16.
输入一行以‘?'为结束的字符串，分别统计其中的英文字符，空格，数字字符和其它字符的个数
2
1
17.
输入三个字符后，按各字符的ASCII码从小到大的顺序输出这三个字符
1
1
18.
输出整数X,Y之间的所有完数。X,Y从键盘输入.说明:一个数如果恰好等于它的因子之和,这个数称为“完数”，例如6=1+2+3
3
1
19.
打印出所有的水仙花数，所谓“水仙花数”是指一个三位数，其各位数字立方和等于该数本身。例如:153为水仙花数，即153=13+53+33
1
1
20.
输出整数X，Y之间的所有素数，X,Y从键盘输入.
2
1
21.
输入字符串，输出其长度
1
1
22.
输入两整数，求它们的最大公约数和最小公倍数
2
1
23.
编一个程序，将两个字符串S1和S2比较,如果S1〉S2，输出一个正数；S1=S2，输出0；S1<S2，输出一个负数.不要用strcpy函数。两个字符串用gets函数读入.输出的正数或负数的绝对值应是相比较的两个字符串相对应字符的ASCII码的差值。例如,’A’与’C’相比，由于'A'〈’C’，应输出负数，由于'A’与’C’的码差值为2，因此应输出"—2"。同理：”And"和"Aid”比较，根据第2个字符比较结果，'n’比’i’大5,因此应输出”5".
3
1
24.
输入一个四位数字，要求输出这四个数字字符，但每两个数字间空格。如输入1990，应输出”1_9_9_0”
2
1
25.
输入一串字符，以’？'结束，分别统计其中每个数字字符‘0’，‘1',…… ‘9’出现的次数
2
1
排序
1.
将一组整数逆序输出
2
1
2.
一个已经按升序排好序的数组.现输入一个数，要求按原来的规律将它插入数组中
2
1
3.
有n个人围成一圈，顺序排号（编号为n的人的下一个人编号为1）。从第一个人开始报数（从1到3报数)，凡报到3的人退出圈子，问最后留下的是原来第几号的那位。
3
1
4.
设整数数组中的元素按照值的升序存放，写一个函数，用折半查找法查找一个给定的值是否在数组中，找到返回值是该数在数组中的下标位置,找不到，返回值为—1.
3
1
5.
用选择法对10个数进行从小到大的排序
3
1
6.
用冒泡法对10个数进行从小到大的排序
2
1
二维数组
1.
求一个N*N矩阵对角线元素之和
2
1
2.
计算两矩阵相乘: 设有矩阵A有M*L个元素，矩阵B有L*N个元素，则矩阵C=A*B有M*N个元素
3
1
3.
输出下面二维数组中的最大元素及其下标
2
1
4.
将一个3*3的整形矩阵转置
2
1
结构体
1.
定义一个结构体变量存放日期（包括年、月、日)，计算该日在本年中是第几天
3
3
2.
假设一个班有n（n<=50)个学生，每人考m（m<=5）门课,求每个学生的平均成绩和每门课的平均成绩，并输出各科成绩均大于等于平均成绩的学生数量
3
3
3.
大学生运动会成绩管理系统，记录某校运动会上的运动项目，包括50、100、200,400，1500米，跳高，跳远，标枪，铅球铁饼等.实现按团体总分高低排出院系团体名次及总分
3
3
4.
构建简单的手机通讯录,通讯录中联系人的基本信息包括：姓名、手机号码、办公室电话、邮箱地址、住址等信息。实现根据姓名查询联系人功能.找到输入该人的信息,否则输出“无此人”.
3
3
5.
个人帐簿管理系统记录某人的全部日常各项开支情况，包括食品消费，房租,子女教育费用，水电费，医疗费等。要求输出某一年中每月的开支排列(按金额从大到小进行排序）
3
3
6.
设用字符数组存储一个人阅读文章的内容,要求找出已阅读的内容相同（对应的字符相同，阅读量相差在5%之内）的人员集合。
4
3
7.
设用字符数组存储一个人阅读文章的内容，要求找出阅读的文章内容相近的人员集合。文章内容相近的定义是：设文章由单词构成，单词之间由空格间隔，文章的单词组定义为文章中所有不重复出现的单词的集合，若两篇文章中 单词组中不相同的单词个数不超过5％，则认为两篇文章的内容相近
4
3
8.
地区的城市分布可以用一个图形表示，顶点表示城市，边表示城市之间的道路，边上的权表示道路的长度,城市的信息包括城市的人口数量，城市的地理位置（经度和纬度)，城市的名称等，定义姐妹城市为:两城市的经度或纬度相差不超过5度，人口数量之差不超过5万人，且两城市之间有直接相连的道路，编程序找出地区中所有的姐妹城市对
4
3
9.
地区的城市分布可以用一个图形表示,顶点表示城市，边表示城市之间的道路，边上的权表示道路的长度，城市的信息包括城市的人口数量，城市的地理位置（经度和纬度），城市的名称等,定义姐妹城市为：两城市的经度或纬度相差不超过5度,人口数量之差不超过5万人，且两城市之间有直接相连的道路限定两城市之间有间接相连的道路，多个满足条件的城市构成姐妹城市群，找出地区中的所有姐妹城市群
4
3
10.
分配房间问题：按房间容量从小到大的次序输入20个房间号及房间容量,组成结构体数组。再输入若干班号和班级人数。对于这些班，依输入次序按人数分配最合适的房间。输出班号,人数，有无房间分配给该班，及分配房号,容量（人数）。注意:一个房间只能分配给一个班,一个班也只能分配一个房间。提示：定义两个结构体数组，第一个结构体包括房间号，容量，是否已经分配;第二个结构体包括班号，人数,是否有房间分配给该班,分配的房号，容量（人数)
4
3
11.
利用结构体方式定义日期,日期的格式采用YYYY/MM/DD的格式，输入两个日期数据,输出两个之间的相差天数.
3
3
12.
利用结构体方式定义日期，日期的格式采用YYYY/MM/DD的格式，输入一个日期数据和整型数据N,输出N天之后的日期。
3
3
13.
利用结构体方式定义日期，日期的格式采用YYYY/MM/DD的格式，输入一个日期数据和整型数据N,输出N天之前的日期.
3
3
14.
利用结构体方式定义时间，时间的格式采用YYYY/MM/DD hh：mm:ss的格式，输入两个时间数据，计算两个不同时间之间相差的秒数
3
3
15.
已知一组学生信息（学号，姓名，出生日期,出生时刻，籍贯），目前能够确认这组学生中包含若干对双胞胎，请你编写程序，识别出所有的双胞胎，并输出全部双胞胎信息。双胞胎的识别要根据姓名(同姓），出生日期（同一天），出生时刻（相差5分钟)，籍贯（相同）等4个信息共同决定.
3
3
16.
已知有A、B两组球队参加比赛，每组有8支队伍(队伍名称，胜场数、平场数、负场数，排名)，首先进行小组赛，然后进行淘汰赛，请根据比赛成绩给出第二轮对阵关系图。
说明:小组赛中成绩的计算方法胜一场得3分，平一场得1分，负一场得0分，如果总得分相同，则按照队伍名称的字母顺序升序排列。淘汰赛的对阵方式为A1vsB8，A2vsB7,A3vsB6,A4vsB5，A5vsB4，A6vsB3，A7vsB2,A8vsB1
4
3
17.
学校组织若干队伍学生进行辩论会比赛，每个队伍由四名同学组成，分别担任第一辩手、第二辩手,第三辩手和第四辩手，若干评委需要为队伍进行整体打分以及为每个辩手单独打分，整体打分项和个人打分项包含辩驳能力、风度、语言表达和论据内容等4项.请你编写程序实现根据每个评委的打分，完成队伍排名和个人辩手排名。
说明：单项综合计分方法为去掉评委中的一个最高分和一个最低分之后的平均分
3
3
文件
1.
从键盘输入一个字符串，将小写字母全部转换成大写字母，然后输出到一个磁盘文件“test”中保存。输入的字符串以!结束
3

2.
有一个磁盘文件存放了职工的数据，职工的数据包括：职工号，姓名，性别,年龄，住址，工资，健康状况,文化程度,今要求只将职工的姓名、工资数据抽出另建一个简明的职工工资文件。
3

3.
有五个学生，每个学生有3门课的成绩，从键盘输入以上数据（包括学生号，姓名，三门课成绩），计算出平均成绩，原有的数据和计算出的平均分数存放在磁盘文件”stud"中
3

4.
有10个学生,每个学生的数据包括学号、姓名、3门课的成绩。从键盘输入10个学生数据,要求打印出3门课总平均成绩,以及具有最高平均分的学生的数据（包括学号、姓名、3门课的成绩、平均分数）
3

5.
提取文件中所有出现的单词，统计每个单次出现的频次，按出现的频次由高到底输出到另外一个文件中
3

6.
有一行电文译文下面规律译成密码:
A-〉Z　a—〉z
B->Y　b—〉y
C—>X　c—>x
…
即第一个字母变成第26个字母，第i个字母变成第（26-i+1）个字母。非字母字符不变,要求编程序将密码回原文，并打印出密码和原文
3
是否必须用文件
7.
设有一个整数文件，对文件中的整数求和，并计算平均值输出
3

链表
1.
检测两条链表是否存在相同元素,假设有两条带头结点的链表A、B,A中存储的数据有10、12、15、39、78、28，B中存储的数据有12、13、24、39、56、78，则输出39、78。
3
4
2.
在双向链表中，A有一个指针指向了节点B,同时,B又有一个指向A的指针。这样不仅能从链表头节点的位置遍历整个链表所有节点，也能从链表尾节点开始遍历所有节点。对于给定的一列数据，按照给定的顺序建立双向链表，按照关键字找到相应节点，输出此节点的前驱节点关键字及后继节点关键字
4
4
3.
通常在数学中对一元n次多项式可表示成如下形式：

本题目要求采用带头结点的链表实现两个一元多项式的加运算,运算结果存储在新的链表中，并打印运算
4
4
4.
创建一个链表。将新生成的结点放在链表的前面.设链表中只有一个整数数据域，从键盘中输入链表结点中的整数，以0表示输入结束
3
4
5.
已知有两个链表a,b，每个链表中的节点包括学号、成绩，每个链表都是按学号升序从前向后排列节点，写一个函数将两链表合并，合并后的链表仍然按学号升序排列
3
4
6.
利用带头结点的单链表实现长整数的加法运算，假设有2个带头结点的链表存储了2个大整数A=1234567890123456789，B=98765432109876543210（链表中的每个节点存放大整数中的一位数字），求A+B的结果,并显示。（结果存放在一个新的大整数链表中）
4
4
7.
利用带头结点的单链表实现长整数的减法运算,假设有2个带头结点的链表存储了2个大整数A=1234567890123456789，B=98765432109876543210（链表中的每个节点存放大整数中的一位数字）,求A-B的结果，并显示。（结果存放在一个新的大整数链表中）
4
4
8.
假设链表p和链表q中的结点值都是整数,且按结点值的递增次序链接起来的带表头结点的环形链表。各链表的表头结点的值为max,且链表中其他结点的值都小于max,在程序中取max为9999.在各个链表中，每个结点的值各不相同，但链表p和链表q可能有值相同的结点（表头结点除外）。下面的程序将链表q合并到链表p中，使得合并后的链表是按结点值递增次序链接起来的带表头结点的环形链表，且链表中各个结点的值各不相同
4
4
9.
设L为一单链表的头指针，单链表的每个结点由一个整数域 data和指针域NEXT组成，整数在单链表中是无序的.设计算法，将链表中结点分成一个奇数链和一个偶数链,分别由P，Q指向,每个链中的数据按由小到大排列，算法中不得申请新的结点空间
3
4
10.
已知一个由n( 设n=1000）个整数组成的线性表，试设计该线性表的一种存储结构，并用标准C语言描述算法,实现将n个元素中所有大于等于19的整数放在所有小于19的整数之后.要求算法的时间复杂度为O（n),空间复杂度O（1)
3
4
11.
设有一头指针为L的带有表头结点的非循环双向链表,其每个结点中除有pred(前驱指针）,data(数据）和next(后继指针）域外,还有一个访问频度域freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次Locate（L,x）运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L，x)运算的算法,该运算为函数过程，返回找到结点的地址，类型为指针型
4
4
12.
给定(已生成)一个带表头结点的单链表，设head为头指针，结点的结构为(data,next）,data为整型元素,next为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间.（要求；不允许使用数组作辅助空间）
3
4
13.
利用链表分别实现两个整数集合的交集运算
3
4
14.
利用带有头结点的链表实现两个多项式相加。链表头结点中包含多项式的个数和最高指数,其它结点中包含多项式的系数和指数,要求不得申请新的结点空间
4
4
15.
利用链表分别实现两个整数集合的差集运算
3
4
16.
利用链表分别实现两个整数集合的并集运算
3
4
递归
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
4
2
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。
4
2
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时）。
2
2
4.
有1堆桃子共 m 个，由 n 只猴子分配这些桃子。每次到达桃子堆放地的猴子只有1只，而且每个猴子都会平均分 1 次桃子。
第1只到达的猴子将桃子平均分成 n 等份，但发现多 k ( k < n ）个，于是,将多余的k个扔掉，然后拿走其中的1份。
第2只猴子同样将剩余的桃子又分成 n 等份，也发现多 k 个，并同样将多余的 k 个扔掉,然后拿走其中1份。3
之后的每只猴子都这样（将剩余的桃子又分成 n 等份，也发现多 k 个，并将多余的 k 个扔掉,然后拿走其中1份)。
现在假设最后一只猴子分配后至少可以拿走1个桃子,请根据输入的 n 和 k值，编程计算最小的 m。（比如，n=3,k=1，则最小的m是25，最后一个分得3个）

2
5.
一个射击运动员打靶，靶一共有10环，连开10枪打中90环的可能性有多少种?请用递归算法编程实现。解析:靶上一共有10种可能——1环到10环，还有可能脱靶，那就是0环，加在一起共11种可能。这是一道考循环和递归的面试题.我们在这个程序中将利用递归的办法实现打靶所有可能的演示，并计算出结果。
3
2
6.
八皇后问题是一个古老而著名的问题，在8×8格的国际象棋盘上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。使用递归实现n皇后问题
4
2
7.
定义递归函数digit（n, k),它返回整数n从低位往高位数第k位的数字的值，例如 digit（15327，4）=5；digit（289,5）=0
3
2
8.
定义一个递归函数check(n，d），它返回布尔值，如果数字d在整数n的某位中出现，则返回true（真），否则返回false（假）。例如：check(3246，2）=true check（1725，3）=false
3
2
9.
顺序读入字符，以‘？’号结束，然后以和输入相反的次序输出读入的字符，用递归函数完成
3
2
10.
设计一个递归算法生成n个元素｛r1，r2,…,rn｝的全排列
4
2
11.
将欧几里德求最大公约数的算法写成递归函数的形式。
欧几里德求最大公约数算法：求整数m和n的最大公约数
若（m mod n==0）最大公约数是n 否则最大公约数是 n与m mod n 的最大公约数
3
2
12.
利用递归函数实现将一个十进制整数转换成二进制字符串
3
2
13.
输入一个正整数N,利用递归实现求N的阶乘
2
2
综合应用
1.
众所周知，外国人的名是在姓的前面的，所以若要普通的按字符串字典排序不符合外国人的习惯，现在要求你写个符合外国人习惯的排序方法
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

4

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

Sample Input
0051231232050775

Sample Output
0 77 12312320

4

3.
明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性,他先用计算机生成了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

4

4.
3、 给定一个长度为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

4

5.
奇偶交换排序如下所述：第一趟对所有奇数i，将a[i] 和a［i+1］ 进行比较;第二趟对所有偶数i,将a[i] 和a[i+1］ 进行比较，若a［i]>a［i+1］，则将两者进行交换；第三趟对奇数i,第四趟对偶数i ……一次类推,直到整个序列有序。试问，这种排序方法的结束条件是什么,编写奇偶交换排序函数
3

6.
迷宫问题：以一个m×n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。在任意一个位置中，可沿上、下、左、右四个方向前进（在有通路的条件下)。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路,或得出没有通路的结论
4
2
7.
设用带权邻接矩阵表示一个图中结点之间的边和边上的耗费，编程序求出两个顶点之间的路径(顶点的序列）和路径上的耗费.进一步可以求出耗费最小的路径
4
3
8.
建立某航班的乘客订票链表。链表的每个结点包括乘客名和订票张数，且链表是按照乘客名的字典次序排列的。第一个结点是一个特殊结点，它的乘客名是空格字符串,订票张数是该航班已订票张数（开始设置为零），每当输入一个乘客名及订票张数时，系统应首先检查已订票张数加新订票张数是否超过该航班允许订票张数（例如200）,若超出，只能订较少的张数或不能订.然后需检查在链表中有无同名的，如果有则在原订票张数上增加，否则在适当位置上插入新结点。当输入订票张数为负数时，表示退票。退票必须能查到同名结点，否则为错。退票张数超过原定张数，只能退原定张数.如果已全退，应将该结点删除。修改头结点，输出每次实际订、退票数及其他错误信息。当输入名字为“zzzz”时,结束订票过程并输出链表数据
4
3
9.
编写程序实现大整数的加法运算
4
重复
10.
编写程序实现大整数的减法运算
4
重复