算法设计习题整理.doc

类型题目序号题目内容难度等级（四等）第几次上机基本应用1.输入三个系数、求一元二次方程ax2+bx+c=0的根,要求考虑a=0、实数根和复数根的情况312.有三个整数a，b，c，由键盘输入，输出其中最大者113.有分段函数：当x5时，y=2x-10.编一程序，输入x的值，输出y的值114.输入一行字符，将此字符串中最长的单词输出 315.输入三角形的三边长，求三角形面积。求三角形面积的公式为area=sqrt(s(s-a)(s-b)(s-c),其中s=(a+b+c)/2。116.输入学生的百分制成绩，将学生的成绩转换成五分制输出（先保留，学生分题的时候用了序号）117.编写程序，判断某一年是否是闰年。（闰年的条件是：能被4整除，但是不能被100整除，或者可以被400整除118.一个球从X米高度自由落下，每次落地后又反跳回原高度的一半，再落下，再反弹。求它在第10次落地时共经过多少米219.编程求圆面积、圆周长。要求圆半径由键盘输入，输出时要求有文字说明，取小数点后两位数字1110.输入一个华氏温度，要求输出摄氏温度，输出时要求有文字说明，取小数点后两位数字。公式为c=5/9(f-32)1111.用pi41-1/3+1/5-1/7+.公式求pi的近似值，直到某一项的绝对值小于10的-6次方为止2112.输入一个字符，判断它是否是大写字母，如果是，将它转换成小写字母；如果不是，不转换。然后输出最后得到的字符2113.输入整数n，求数列1+1/2+1/3+1/4+1/5+.1/n结果2114.求S=a+aa+aaa+.+aa.a(n个a)之值。其中a是一个数字，n代表a的位数。例如：2+22+222+2222+22222（此时n为5），n由键盘输入2115.给出一百分制的成绩，要求数出成绩等级A,B,C,D,E；90分以上为A, 8089分为B，7079分为C，6069分为D，60分以下为E。1116.输入一行以？为结束的字符串，分别统计其中的英文字符，空格，数字字符和其它字符的个数2117.输入三个字符后，按各字符的ASCII码从小到大的顺序输出这三个字符1118.输出整数X,Y之间的所有完数。X,Y从键盘输入。说明：一个数如果恰好等于它的因子之和，这个数称为“完数”，例如6=1+2+33119.打印出所有的水仙花数，所谓“水仙花数”是指一个三位数，其各位数字立方和等于该数本身。例如：153为水仙花数，即153=13+53+331120.输出整数X,Y之间的所有素数，X,Y从键盘输入。2121.输入字符串，输出其长度1122.输入两整数，求它们的最大公约数和最小公倍数2123.编一个程序，将两个字符串S1和S2比较，如果S1S2，输出一个正数；S1=S2，输出0；S1S2，输出一个负数。不要用strcpy函数。两个字符串用gets函数读入。输出的正数或负数的绝对值应是相比较的两个字符串相对应字符的ASCII码的差值。例如，A与C相比，由于AC，应输出负数，由于A与C的码差值为2，因此应输出-2。同理：And和Aid比较，根据第2个字符比较结果，n比i大5，因此应输出5。3124.输入一个四位数字，要求输出这四个数字字符，但每两个数字间空格。如输入1990，应输出1_9_9_02125.输入一串字符，以?结束，分别统计其中每个数字字符0，1， 9出现的次数21排序1.将一组整数逆序输出212.一个已经按升序排好序的数组。现输入一个数，要求按原来的规律将它插入数组中213.有n个人围成一圈，顺序排号（编号为n的人的下一个人编号为1）。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位。314.设整数数组中的元素按照值的升序存放，写一个函数，用折半查找法查找一个给定的值是否在数组中，找到返回值是该数在数组中的下标位置，找不到，返回值为-1。315.用选择法对10个数进行从小到大的排序316.用冒泡法对10个数进行从小到大的排序21二维数组1.求一个N*N矩阵对角线元素之和212.计算两矩阵相乘: 设有矩阵A有M*L个元素，矩阵B有L*N个元素，则矩阵C=A*B有M*N个元素313.输出下面二维数组中的最大元素及其下标214.将一个3*3的整形矩阵转置21结构体1.定义一个结构体变量存放日期（包括年、月、日），计算该日在本年中是第几天332.假设一个班有n(n=50)个学生，每人考m(mZa-z B-Yb-y C-Xc-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。342.在双向链表中，A有一个指针指向了节点B，同时，B又有一个指向A的指针。这样不仅能从链表头节点的位置遍历整个链表所有节点，也能从链表尾节点开始遍历所有节点。对于给定的一列数据，按照给定的顺序建立双向链表，按照关键字找到相应节点，输出此节点的前驱节点关键字及后继节点关键字443.通常在数学中对一元n次多项式可表示成如下形式：本题目要求采用带头结点的链表实现两个一元多项式的加运算，运算结果存储在新的链表中，并打印运算444.创建一个链表。将新生成的结点放在链表的前面。设链表中只有一个整数数据域，从键盘中输入链表结点中的整数，以0表示输入结束345.已知有两个链表a,b，每个链表中的节点包括学号、成绩，每个链表都是按学号升序从前向后排列节点，写一个函数将两链表合并，合并后的链表仍然按学号升序排列346.利用带头结点的单链表实现长整数的加法运算，假设有2个带头结点的链表存储了2个大整数A=1234567890123456789，B=98765432109876543210（链表中的每个节点存放大整数中的一位数字），求A+B的结果，并显示。（结果存放在一个新的大整数链表中）447.利用带头结点的单链表实现长整数的减法运算，假设有2个带头结点的链表存储了2个大整数A=1234567890123456789，B=98765432109876543210（链表中的每个节点存放大整数中的一位数字），求A-B的结果，并显示。（结果存放在一个新的大整数链表中）448.假设链表p和链表q中的结点值都是整数,且按结点值的递增次序链接起来的带表头结点的环形链表。各链表的表头结点的值为max,且链表中其他结点的值都小于max，在程序中取max为9999。在各个链表中，每个结点的值各不相同，但链表p和链表q可能有值相同的结点（表头结点除外）。下面的程序将链表q合并到链表p中，使得合并后的链表是按结点值递增次序链接起来的带表头结点的环形链表，且链表中各个结点的值各不相同449.设L为一单链表的头指针，单链表的每个结点由一个整数域data和指针域NEXT组成，整数在单链表中是无序的。设计算法，将链表中结点分成一个奇数链和一个偶数链，分别由P，Q指向，每个链中的数据按由小到大排列，算法中不得申请新的结点空间3410.已知一个由n（ 设n=1000）个整数组成的线性表，试设计该线性表的一种存储结构，并用标准C语言描述算法，实现将n个元素中所有大于等于19的整数放在所有小于19的整数之后。要求算法的时间复杂度为O(n),空间复杂度O(1)3411.设有一头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred（前驱指针），data（数据）和next（后继指针）域外，还有一个访问频度域freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次Locate(L,x)运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型4412.给定(已生成)一个带表头结点的单链表，设head为头指针，结点的结构为(data,next),data为整型元素，next为指针，试写出算法:按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。(要求;不允许使用数组作辅助空间)3413.利用链表分别实现两个整数集合的交集运算3414.利用带有头结点的链表实现两个多项式相加。链表头结点中包含多项式的个数和最高指数，其它结点中包含多项式的系数和指数，要求不得申请新的结点空间4415.利用链表分别实现两个整数集合的差集运算3416.利用链表分别实现两个整数集合的并集运算34递归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、1422.将正整数n表示成一系列正整数之和：n=n1+n2+nk，其中n1n2nk1，k1。 正整数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。423.计算斐波那契（Fibonacci）数列的第n项函数fib（n）。斐波那契数列为：0、1、1、2、3、，即： fib(0)=0; fib(1)=1; fib(n)=fib(n-1)+fib(n-2)（当n1时）。224.有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个）25.一个射击运动员打靶，靶一共有10环，连开10枪打中90环的可能性有多少种？请用递归算法编程实现。解析：靶上一共有10种可能1环到10环，还有可能脱靶，那就是0环，加在一起共11种可能。这是一道考循环和递归的面试题。我们在这个程序中将利用递归的办法实现打靶所有可能的演示，并计算出结果。326.八皇后问题是一个古老而著名的问题，在88格的国际象棋盘上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。使用递归实现n皇后问题427.定义递归函数digit（n, k）,它返回整数n从低位往高位数第k位的数字的值，例如 digit（15327,4）=5；digit（289,5）=0328.定义一个递归函数check（n，d），它返回布尔值，如果数字d在整数n的某位中出现，则返回true（真），否则返回false（假）。例如：check（3246,2）=true check（1725,3）=false329.顺序读入字符，以？号结束，然后以和输入相反的次序输出读入的字符，用递归函数完成3210.设计一个递归算法生成n个元素r1,r2,rn的全排列4211.将欧几里德求最大公约数的算法写成递归函数的形式。欧几里德求最大公约数算法：求整数m和n的最大公约数若（m mod n=0）最大公约数是n 否则最大公约数是 n与m mod n 的最大公约数3212.利用递归函数实现将一个十进制整数转换成二进制字符串3213.输入一个正整数N，利用递归实现求N的阶乘22综合应用1.众所周知,外国人的名是在姓的前面的，所以若要普通的按字符串字典排序不符合外国人的习惯，现在要求你写个符合外国人习惯的排序方法Input第一行为一个整数N，表示下面有N组测试数据第二行含有1个整数M，表示该组测试数据有M个名字接下来M行每行不超过100个字符Output 对于每组测试数据,输出排序后的姓名序列,每组测试数据后面加一个空行Sample Input13Tom SmithTim AliceMarry AliceSample OutputMarry AliceTim AliceTom Smith42.输入一行数字，如果我们把这行数字中的5都看成空格，那么就得到一行用空格分割的若干非负整数（可能有些整数以0开头，这些头部的0应该被忽略掉，除非这个整数就是由若干个0组成的，这时这个整数就是0）。你的任务是：对这些分割得到的整数，依从小到大的顺序排序输出。Input输入包含多组测试用例，每组输入数据只有一行数字（数字之间没有空格），这行数字的长度不大于1000。 输入数据保证：分割得到的非负整数不会大于100000000；输入数据不可能全由5组成。Output对于每个测试用例，输出分割得到的整数排序的结果，相邻的两个整数之间用一个空格分开，每组输出占一行。 Sample Input0051231232050775 Sample Output0 77 1231232043.明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N1000），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。Input输入有2行，第1行为1个正整数，表示所生成的随机数的个数：N第2行有N个用空格隔开的正整数，为所产生的随机数。Output输出也是2行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。Sample Input1020 40 32 67 40 20 89 300 400 15Sample Output815 20 32 40 67 89 300 40044.3、 给定一个长度为N(0n=10000)的序列，保证每一个序列中的数字ai是小于maxlongint的非负整数 ，编程