aa.txt

很值得一看,不要错过哦!相信不会让你失望的

2007-2008学年第1学期考试试题
课程名称      《算法设计与分析》       任课教师签名   蔡琼       
出题教师签名   蔡琼                    审题教师签名              
考试方式       开卷、上机              适用专业   计科0501-0503  
考试时间     （   240  ）分钟
题号	总分	评卷人
		


说明：在以下试题中现场抽签，抽中题作为试题。编程上机调试并且提交电子文档报告，以学号姓名作为文件名存储在桌面上。报告内容至少包含如下内容：
1.	学生基本情况：专业班级、学号、姓名
2.	考试题号、题目
3.	设计分析
4.	源程序代码
5.	测试用例（尽量覆盖所有分支）
6.	总结

试题：

一、编程，求一个矩阵的鞍点 (即在行上最小而在列上最大的点)。

二、整数的分划问题：对于一个正整数n的分划就是把n写成一系列正整数之和的表达式。

三、统计找数字对的出现频率：输入N（2≤N≤100）个数字（在0与9之间），然后统计出这组数中相邻两数字组成的链环数字对出现的次数。

四、编程求当N<=100时，N！的准确值。

五、螺旋阵：任意给定n值，按螺旋的方式输出方阵。

六、魔方阵：任意给定n值，输出魔方阵。

七、填写运算符:输入任意5个数x1,x2,x3,x4,x5每相邻两个数之间填上一个运算符。在填入四个运算符后，使得表达式值为y(y由键盘输入)。求出所有满足条件的表达式。

八、有10箱产品每箱有1000件，正品每件100克。其中有几箱是次品，次品每件比正品轻10克，问能否用秤只称一次，就找出哪几箱是次品。

九、编程完成下面给“余”猜数的游戏：你心里先想好一个1~100之间的整数x，将它分别除以3、4和7并得到三个余数。你把这三个余数告诉计算机，计算机能马上猜出你心中的这个数。

十、用分治法求金块问题： 老板有一袋金块(共n块，n是2的幂（n>=2）)，最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块。

十一、用分治法求解残缺棋盘问题。残缺棋盘是一个有2k×2k （k≥1）个方格的棋盘，其中恰有一个方格残缺。如图给出k=1时各种可能的残缺棋盘，其中残缺的方格用阴影表示。


       	      	 	       
                                                                                        
　　　     ①号         ②号          ③号           ④号
图   四种三格板
这样的棋盘我们称作“三格板”，残缺棋盘问题就是要用这四种三格板覆盖更大的残缺棋盘。在此覆盖中要求：
1）两个三格板不能重叠
2）三格板不能覆盖残缺方格，但必须覆盖其他所有的方格。 



十二、用分治法求数列的最大子段和。给定由n个整数组成的序列(a1, a2, …, an)，最大子段和问题要求该序列形如          的最大值（1≤i≤j≤n），当序列中所有整数均为负整数时，其最大子段和为0。例如，序列(-20, 11, -4, 13, -5, -2)的最大子段和为：  

十三、用分治法求选择问题：求一组数的第二大的数。

十四、键盘输入一个高精度的正整数N（N不超过240位） ，去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。 

十五、数列极差问题：在黑板上写了N个正整数组成的一个数列，进行如下操作:每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的记作max，最小的记作min，则该数列的极差定义为M=max-min。    

十六、设计一个算法， 把一个真分数表示为埃及分数之和的形式。所谓埃及分数，是指分子为1的形式。如：7/8=1/2+1/3+1/24。                                          

十七、数塔问题：如图所示的一个数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的数值和最大。

 

十八、给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。


十九、最长不下降子序列问题：设有n个不相同的整数组成的数列，记为:
a(1)、a(2)、……、a(n)且a(i)<>a(j) (i<>j)，若存在i1<i2<i3< … <ik ，且有a(i1)<a(i2)< … <a(ik)，则称为长度为k的不下降序列。求一个数列的最长不下降子序列。


二十、已知若干个城市的地图，求从一个城市到另一个城市的路径，要求路径中经过的城市最少。 如图表示的是从城市A到城市H的交通图。从图中可以看出，从城市A到城市H要经过若干个城市。现要找出一条经过城市最少一条路线。 

 
					

二十一、走迷宫问题 ：迷宫是许多小方格构成的矩形，在每个小方格中有的是墙（图中的“1”）有的是路（图中的“0”）。走迷宫就是从一个小方格沿上、下、左、右四个方向到邻近的方格，当然不能穿墙。设迷宫的入口是在左上角(1,1)，出口是右下角(8,8)。根据给定的迷宫，找出一条从入口到出口的路径。 


 



二十二、有如图所示的七巧板，试编写程序，使用至多四种不同颜色对七巧板进行涂色(每块涂一种颜色)，要求相邻区域的颜色互不相同，打印输出所有可能的涂色方案。
 

二十三、n皇后问题：在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。

二十四、马的遍历问题：在n＊m的棋盘中，马只能走日字。马从位置(x,y)处出发，把棋盘的每一格都走一次，且只走一次。找出所有路径。

二十五、素数环问题：把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。 

二十六、按排列树回溯搜索解决n皇后问题。         

二十七、一个有趣的高精度数据：构造一个尽可能大的数，使其从高到低前一位能被1整除，前2位能被2整除，……，前n位能被n整除。

二十八、布线问题。