数据结构与算法任务书-总论.doc

算法与数据结构课程设计任务书 （2014级软件工程本科专业） 题目类型：软件工程（R） 指导教师： 李睿 题目简介 扫雷问题。有些个人计算机会带有一个名为Minesweeper的游戏。该游戏界面是一个网格，网格中的有些方块是雷。编写一个程序以读取文件，该文件中存放着网格中的行数、列数以及网格本身。网格会含有一些标记为o的方块，这些就是雷。其他方块不是雷，将会标记上问号（？）。程序的输出就是输出这个网格。雷依然会标记成o，而那些不含雷的方块会替换成一个数字，以表明邻近雷的个数。最大数字将是8。（4） 例如： 5 5 ?o??? 2 2o211 o??o? 3 o33o2 ??o?o 4 34o4o oo?o? 5 oo4o2 ?o??? 6 3o311 求素数问题。埃拉托色尼筛法（Sieve of Eratosthenes）是一种用来求所有小于N的素数的方法。从建立一个整数2~N的表着手，寻找i?的整数，编程实现此算法，并讨论运算时间。（1） 方程求解问题。方程A5+B5+C5+D5+E5=F5刚好有一个满足0≤A≤B≤C≤D≤E≤F≤75的整数解。请编写一个求出该解的程序。（3） 最短字符串问题。编写一个程序，从输入中读取字符串，并按长度顺序，最短字符串优先的原则输出它们。如果有若干字符串具有相同的长度，就按字母顺序输出它们。（3） 计算1的个数问题。编写递归程序，返回十进制数N的二进制表示中1的个数。（2） 排序重构问题。令A为一个由N个已特殊排序数组成的数列：A1，A2，…，AN，其中A1=0。令B为N（N-1）/2个数（定义为Bij=Ai-Aj(ij)）组成的数列。例如，A=0，1，5，8，那么D=1，3，4，5，7，8。请完成： 编写程序，根据A构造D； 编写程序，构造与D相对应的某一个数列A，注意A不是唯一的。（4） 占用网格计算问题。考虑一个N*N的网格，其中某些方格已被占用。如果两个方格共用公共的边，就说它们属于同一个组，如图示，一组为4个被占用的方格，3组为两个被占用的方格，2个方格被单独占用。假设格子用二维数组来表示。请编写实现下列目的程序： 给定组中的某个方格，计算组的大小； 计算不同组的数目； 3）列出所有的组。（4） ● ● ● ● ● ● ● ● ● ● ● ● 递归替换问题。编写程序，扩展C/C++源文件中的#include指令（以递归的方式）。请以文件名的内容替换形如下面的代码行。 #include “filename” （3） 数据删除问题。编写删除具有N个数据项的数组A中所有重复项的程序，返回A中仍有的数据项。要求运行时间在O（NlogN）。（2） 随机走步问题。以下在x-y坐标系上进行的游戏属于二维的随机行走。从原点（0，0）开始，每次迭代都是由向左、向上、向右和向下一个单位的随机步构成。当行走者返回原始点时，行走结束。在二维世界这种情况发生的概率为1，而在三维世界概率小于1。请编写一个进行100次独立随机行走程序，并计算每个方向的步数的平均数。（4） 表达式转换问题。请编写一个读取中缀表达式并生成后缀表达式的程序。（2） 表达式转换问题。请编写一个读取后缀表达式并生成中缀表达式的程序。（2） 课程选修问题。学生需要修一定数量的课程才能毕业，而这些课程会有一些必须遵循的选修顺序。假设每个学期都开所有课程，并且学生所修课程数量不限制。给出课程和先修课程的列表，求出一个满足最小学期数要求的时间表。以你的专业情况为背景设计。（3） 通过单字符置换可以将一个单词改为另一个单词。假设存在一个5字母单词的字典。给出一个算法确定单词A是否可以通过一系列的单字符置换转换为单词B，并且如果可以的话，输出相应的单词序列。例如，bleed通过序列bleed、blend、blond、blood转换为blood。（4） 编写一个以行为单位的文本编辑器。内部文件的副本被保存成由各个行组成的链表。为了能在文件中上移或下移，必须维护一个双链表。大部分命令使用只有一个字符的字符串表示。有些是两个字符，并且要求一个参数（或者两个）。（6） 表一，所支持的命令行 命令 功能 l 移到顶部 a 在当前行之后添加文本，直到本行出现’.’字符 d 删除当前行 dr num num 删除若干行 f name 更改当前行的名称 g num 转到指定的行 h 获得帮助 i 与a类似，在当前行之前添加文本行 m num 将当前行移到指定行数之后 m