算法设计技能训练题目及说明.docx

目录1 一元稀疏多项式计算器 22 迷宫问题 23 哈夫曼编/译码器 34 教学计划编制问题 45 成绩分析问题 56 二叉排序树与平衡二叉树的实现 67 图的基本操作与实现 68 全国交通咨询模拟 69 内部排序算法的性能分析 710 背包问题的求解 711 简单个人书管理系统的设计与实现 812 简易电子表格的设计 813 停车厂模拟管理程序的设计与实现 914 农夫过河问题的求解 915 号码查询系统 101 一元稀疏多项式计算器［问题描述］ 设计一个一元稀疏多项式简单计算器［基本要求］ 一元稀疏多项式简单计算器的基本功能是：(1) 输入并建立多项式；(2) 输出多项式，输出形式为整数序列：n,cl,el, c2,e2,,,,,,, c ,e ,其中n是多项式的项数，1 1 2 2 n nc占，分别是第i项的系数和指数，序列按指数降序排序；(3) 多项式a和b相加，建立多项式a+b；(4) 多项式a和b相减，建立多项式a-b；(5) 计算多项式在x处的值6) 计算器的仿真界面选做) ［测试数据］(1) (2x+5x8-3.1xii)+(7-5x8+llx9) = (-3.1xii+llx9+2x+7)(2) (6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2-x2+7.8x15)=(-7.8x15-1.2x9-x+12x-3)(3) (l+x+x2+x3+x4+x5)+(-x3-x4)=(x5+x2+x+l)(4) (x+x3)+(-x-x3)=0(5) (x+x2+x3)+0=( x3+ x2+ x)［实现提示］ 用带表头结点的单链表存储多项式，多项式的项数存放在头结点中。

2 迷宫问题［问题描述］以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍设计一个程序, 对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论［基本要求］(1) 实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序求得 的通路以三元组(ij,d)的形式输出，其中：(i,j)指示迷宫中的一个坐标，d表示走 到下一坐标的方向2) 编写递归形式的算法，求得迷宫中所有可能的通路；(3) 以方阵形式输出迷宫及其通路选做)［测试数据］迷宫的测试数据如下：左上角(1, 1)为入口，右下角(9, 8)为出口l 2 3 4 5 6 7 8001000100010001000001101011100100001000001000101011110011100010111000000［实现提示］ 计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索， 若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得 一条通路假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路可以二维数组存储迷宫数据，通常设定入口点的下标为(1, 1),出口点的下标为(m,n)。

为处理方便起见，可在迷宫的四周加一圈障碍对于迷宫中任一位置，均可约定有东、南、 西、北四个方向可通3 哈夫曼编 / 译码器［问题描述］ 利用哈夫曼编码进行信息通讯可以大大提高信道利用率，缩短信息传输时间，降低传输 成本但是，这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数 据进行译码(复原)对于双工信道 (即可以双向传输信息的信道)，每端都需要一个完整的编 /译码系统试为这样的信息收发站写一个哈夫曼码的编译码系统［基本要求］一个完整的系统应具有以下功能：(1) 1:初始化(Initialization)从终端读入字符集大小n,及n个字符和m个权值，建立哈 夫曼树，并将它存于文件hfmtree中2) C:编码(Coding)利用已建好的哈夫曼树(如不在内存，则从文件hfmtree中读入)， 对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中3) D:解码(Decoding)利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果 存入文件 textfile 中4) P:打印代码文件(Print)将文件codefile以紧凑格式显示在终端上，每行50个代码。

同时将此字符形式的编码文件写入文件codeprint中5) T:打印哈夫曼树(Tree printing)o将已在内存中的哈夫曼树以直观的方式(树或凹入 表形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中［实现提示］可以根据题目要求把程序划成5 个模块，设计成菜单方式，每次执行一个模块后返回菜 单除了初始化(I)过程外，在每次执行时都经过一次读取磁盘文件数据这是因为如果在程 序执行后一直没有进行初始化(I)过程，为了能使后面的操作顺利进行，可以通过读取旧的数 据来进行工作比如：如果程序的工作需要的字符集和权值数据是固定的，只要在安装程序 时进行一次初始(I)化操作就可以了再次运行程序时，不管进行哪项操作都可以把需要的数 据读入到内存［算法分析］本程序主要用到了三个算法1)哈夫曼编码在初始化(I)的过程中间，要用输入的字符和权值建立哈夫曼树并求得哈夫曼编码先将 输入的字符和权值存放到一个结构体数组中，建立哈夫曼树，将计算所得的哈夫曼编码存储 到另一个结构体数组中2) 串的匹配在编码(D)的过程中间，要对已经编码过的代码译码，可利用循环，将代码中的与哈夫 曼编码的长度相同的串与这个哈夫曼编码比较，如果相等就回显并存入文件。

3) 二叉树的遍历在打印哈夫曼树(T )的过程中，因为哈夫曼树也是二叉树，所以就要利用二叉树的先序 遍历将哈夫曼树输出［测试数据］根据实验要求，在tobetrans.dat中输入”THIS PROGRAM IS MY FA/ORITE",字符集和 其频度如表 1 所示表1字符集频度表字符ABCDEFGHIJKLM频度1866423223210321154757153220字符NOPQRSTUVWXYZ频度205619250515530101122124 教学计划编制问题［问题描述］大学的每个专业都要制定教学计划假设任何专业都有固定的学习年限，每学年含两学 期，每学期的时间长度和学分上限值均相等每个专业开设的课程都是确定的，而且课程在 开设时间的安排必须满足先修关系每门课程有哪些先修课程是确定的，可以有任意多门， 也可以没有每门课恰好占一个学期试在这样的前提下设计一个教学计划编制程序 ［基本要求］(1) 输入参数包括：学期总数，一学期的学分上限，每门课的课程号(固定占3 位的字 母数字串)、学分和直接先修课的课程号2) 允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀； 二是使课程尽可能地集中在前几个学期中。

3) 若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定 的文件中计划的表格格式自行设计［测试数据］学期总数：6；学分上限：10；该专业共开设12门课，课程号从C01到C12，学分顺 序为 2， 3， 4， 3， 2， 3， 4， 4， 7， 5， 2， 3先修关系见图 1［实现提示］可设学期总数不超过12，课程总数不超过100如果输入的先修课程号不在该专业开设 的课程序列中，则作为错误处理应建立内部课程号与课程号之间的对应关系5 成绩分析问题［问题描述］ 录入、保存一个班级学生多门课程的成绩，并对成绩进行分析［基本要求］⑴通过键盘输入各学生的多门课程的成绩，建立相应的文件input.dat2) 对文件 input.dat 中的数据进行处理，要求具有如下功能：1) 按各门课程成绩排序，并生成相应的文件输出2) 计算每人的平均成绩，按平均成绩排序，并生成文件3) 求出各门课程的平均成绩、最高分、最低分、不及格人数、60~69 分人数、70~79 分人数、80~89 分人数、90 分以上人数4) 根据姓名或学号查询某人的各门课成绩，重名情况也能处理3) 界面美观［测试数据］测试数据如表2 所示。

表2成绩表学号姓名数学英语计算机001王放787790002张强896788003李浩566678004黄鹂兵898685005李浩678876006陈利风455467007尚晓7876706 二叉排序树与平衡二叉树的实现［问题描述］ 分别采用二叉链表和顺序表作存储结构，实现对二叉排序树与平衡二叉树的操作［基本要求］(1)用二叉链表作存储结构:1) 以回车('\n')为输入结束标志，输入数列L,生成一棵二叉排序树T；2) 对二叉排序树 T 作中序遍历，输出结果；3) 计算二叉排序树T查找成功的平均查找长度，输出结果；4) 输入元素x,查找二叉排序树T,若存在含x的结点，则删除该结点,并作中序遍历(执行操作 2)；否则输出信息“无 x”；5) 用数列L,生成平衡的二叉排序树BT:当插入新元素之后，发现当前的二叉排序树BT不是平衡的二叉排序树，则立即将它转换成新的平衡的二叉排序树BT；6) 计算平衡的二叉排序树BT的平均查找长度，输出结果2)用顺序表(一维数组)作存储结构:1) 以回车('\n')为输入结束标志，输入数列L,生成一棵二叉排序树T；2) 对二叉排序树T作中序遍历，输出结果；3) 计算二叉排序树T查找成功的平均查找长度，输出结果；4) 输入元素x，查找二叉排序树T:若存在含x的结点，则删除该结点,并作中序遍历(执 行操作 2)；否则输出信息“无 x”；7 图的基本操作与实现［问题描述］自选存储结构，实现对图的操作。

［基本要求］(1) 自选存储结构，输入含n个顶点(用字符表示顶点)和e条边的图G；(2) 求每个顶点的度，输出结果；(3) 指定任意顶点x为初始顶点，对图G作DFS遍历，输出DFS顶点序列(提示:使用一个栈实 现 DFS)；(4) 指定任意顶点x为初始顶点，对图G作BFS遍历，输出BFS顶点序列(提示:使用一个队列实 现 BFS)；(5) 输入顶点x,查找图G:若存在含x的顶点，则删除该结点及与之相关联的边并作DFS遍历 (执行操作3)；否则输出信息“无x”；(6) 判断图G是否是连通图，输出信息“YES”/“NO”；(7) 如果选用的存储结构是邻接矩阵,则用邻接矩阵的信息生成图G的邻接表，即复制图G,然 后再执行操作(2)；反之亦然8)自选图的其它任一种操作实现之8 全国交通咨询模拟［问题描述］处于不同目的的。