秋数据结构与算法课程设计题目要求_徐红梅.docVIP

一、学生成绩管理 1. 问题描述 要求以学生成绩管理业务为背景，设计一个“学生成绩管理系统”程序。对于学校来讲，学生成绩管理系统是不可缺少的组成部分，主要是对学生成绩资料的录入、浏览、插入和删除等基本功能的实现。 2. 设计要求 编制一个学生成绩管理程序。设学生成绩以一个学生一条记录的形式存储，每个学生记录包含的信息有学号和各门功课的成绩。设每位学生学习数学、英语、语文、物理和化学5门课程。 3. 数据结构 本课程设计使用单链表作为实现该问题的数据结构。 4. 问题分析 程序设计一般由算法和数据结构两部分组成。管理学生的成绩适合用单链表，方便随时插入和删除学生记录，实现动态管理。一个学生作为一个结点，该结点类型为结构体，结构体中的域表示学生的属性。每个结点除了存放属性外，还存放指向后继结点的指针。 二、马踏棋盘 1. 问题描述 设计一个国际象棋的马踏遍棋盘的演示程序。 2. 设计要求 （1）程序的输入：设计程序按要求输入马的初始位置（相应的坐标）。 （2）程序的输出：程序的设计完成后应给出马从初始位置走遍棋盘的过程，并按照求出的行走路线的顺序，将数字1，2，…，64依次填入一个8*8的方阵并输出。 3. 数据结构 本课程设计使用的数据结构是栈，利用顺序栈来实现。 4. 问题分析 所谓马踏棋盘问题，是指将马随机放在国际象棋的8*8棋盘的某个方格中，马按走棋规则（马走日子）进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。由用户自行指定一个马的初始位置，求出马的行走路线，并按照求出的行走路线的顺序，将数字1，2，…，64依次填入一个8*8的方阵并输出。 从用户给出的初始位置开始判断，按照顺时针顺序，每次产生一个新的路点，并验证此路点的可用性，需要考虑的是当前路点是否超出棋盘范围和此路点是否已经走过，如果新路点可用，则入栈，并执行下一步，重复进行如上步骤，每次按照已走路点的位置生成新路点。如果一个新路点的可扩展路点数为0，进行回溯，直到找到一个马能踏遍棋盘的行走路线并输出。 三、停车场管理 1. 问题描述 设停车场是一个可停放n辆汽车的长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在之后入的车辆必须先退出车场让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在离开停车场时必须按停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据进行模拟管理。 1. 问题描述 实现大整数（200位以内的整数）的加、减、乘、除运算。 2. 设计要求 设计程序实现两个大整数的四则运算，输出这两个大整数的和、差、积、商及余数。 3. 数据结构 本课程设计采用顺序串来实现。 4. 问题分析 由于整数数据存储位数有限，因此引入串的概念，将整型数据用字符串进行存储，利用字符串的一个字符存储大整数的一位数值，然后根据四则运算规则，对相应位依次进行相应运算，同时保存进位，从而实现大整数精确的运算。 具体设计思路如下： （1）计算大整数加法时，采用数学中列竖式的方法，从个位（即字符串的最后一个字符）开始逐位相加，超过或达到10则进位，同时将该位计算结果存到另一个字符串中，直至加完大整数的所有位为止。 （2）计算大整数减法时，首先调用库函数strcmp判断这两个大整数是否相等，如果相等则结果为0，否则用compare函数判断被减数和减数的大小关系，进而确定结果为正数还是负数，然后对齐位依次进行减法，不够减则向前借位，直至求出每一位减法之后的结果。 （3）计算大整数乘法时，首先让乘数的每一位都和被乘数进行乘法运算，两个乘数之积与进位相加作为当前位乘积，求得当前位的同时获取进位值，进而实现大整数的乘法运算。 （4）计算大整数除法时，类似做减法，基本思想是反复做减法，从被除数里最多能减去多少次除数，所求得的次数就是商，剩余不够减的部分则是余数，这样便可计算出大整数除法的商和余数。 五、魔方阵 1. 问题描述 魔方阵是一个古老的智力问题，它要求在一个m*m的矩阵中填入1~m2的数字（m为奇数），使得每一行、每一列、每条对角线的累加和都相等。 2. 设计要求 （1）输入魔方阵的行数m，要求m为奇数，程序对所输入的m作简单的判断，如m有错，能给出适当的提示信息。 （2）实现魔方阵。 （3）输出魔方阵。 3. 数据结构 本课程设计使用的数据结构是数组。 4. 问题分析 解魔方阵问题的方法很多，这里采用如下规则生成魔方阵。 （1）由1开始填数，将1