数据结构课程设计题目.doc

数据结构课程设计题目数据结构课程设计题目 1 运动会分数统计 限运动会分数统计 限 1 人完成 人完成 任务 参加运动会有 n 个学校 学校编号为 1 n 比赛分成 m 个男子项目 和 w 个 女子项目 项目编号为男子 1 m 女子 m 1 m w 不同的项目取前五名或前三名 积分 取前五名的积分分别为 7 5 3 2 1 前三名的积分分别为 5 3 2 哪些取 前五名或前三名由学生自己设定 m 20 n 20 功能要求 1 可以输入各个项目的前三名或前五名的成绩 2 能统计各学校总分 3 可以按学校编号或名称 学校总分 男女团体总分排序输出 4 可以按学校编号查询学校某个项目的情况 可以按项目编号查询取得前三或前五名的学 校 5 数据存入文件并能随时查询 6 规定 输入数据形式和范围 可以输入学校的名称 运动项目的名称 输出形式 有合理的提示 各学校分数为整形 界面要求 有合理的提示 每个功能可以设立菜单 根据提示 可以完成相关的功能 要求 存储结构 学生自己根据系统功能要求自己设计 但是要求运动会的相关数据要存储 在数据文件中 数据文件的数据读写方法等相关内容在 c 语言程序设计的书上 请自学解 决 请在最后的上交资料中指明你用到的存储结构 测试数据 要求使用 1 全部合法数据 2 整体非法数据 3 局部非法数据 进行程序 测试 以保证程序的稳定 测试数据及测试结果请在上交的资料中写明 2 飞机订票系统 限飞机订票系统 限 1 人完成 人完成 任务 通过此系统可以实现如下功能 录入 可以录入航班情况 数据可以存储在一个数据文件中 数据结构 具体数据自定 查询 可以查询某个航线的情况 如 输入航班号 查询起降时间 起飞抵达城市 航班票 价 票价折扣 确定航班是否满仓 可以输入起飞抵达城市 查询飞机航班情况 订票 订票情况可以存在一个数据文件中 结构自己设定 可以订票 如果该航班已经无票 可以提供相关可选择航班 退票 可退票 退票后修改相关数据文件 客户资料有姓名 证件号 订票数量及航班情况 订单要有编号 修改航班信息 当航班信息改变可以修改航班数据文件 要求 根据以上功能说明 设计航班信息 订票信息的存储结构 设计程序完成功能 3 文章编辑 限文章编辑 限 1 人完成 人完成 功能 输入一页文字 程序可以统计出文字 数字 空格的个数 静态存储一页文章 每行最多不超过 80 个字符 共 N 行 要求 1 分别统计出其中 英文字母数和空格数及整篇文章总字数 2 统计某一字符串在文章中出现的次数 并输 出该次数 3 删除某一子串 并将后面的字符前移 存储结构使用线性表 分别用几个子函数实现相应的功能 输入数据的形式和范围 可以输入大写 小写的英文字母 任何数字及标点符号 输出形式 1 分行输出用户输入的各行字符 2 分 4 行输出 全部字母数 数 字个数 空格个数 文章总字数 3 输出删除某一字符串后的文章 4 宿舍管理查询软件 限宿舍管理查询软件 限 1 人完成 人完成 1 任务 为宿舍管理人员编写一个宿舍管理查询软件 程序设计要求 A 采用交互工作方式 B 建立数据文件 数据文件按关键字 姓名 学号 房号 进行排序 冒泡 选择 插入排 序等任选一种 2 查询菜单 用二分查找实现以下操作 A 按姓名查询 B 按学号查询 C 按房号查询 3 打印任一查询结果 可以连续操作 5 校园导航问题 限校园导航问题 限 1 人完成 人完成 设计要求 设计你的学校的平面图 至少包括 10 个以上的场所 每两个场所间可以有不同 的路 且路长也可能不同 找出从任意场所到达另一场所的最佳路径 最短路径 6 教学计划编制问题 限教学计划编制问题 限 1 人完成 人完成 问题描述 大学的每个专业都要制定教学计划 假设任何专业都有固定的学习年限 每学年含两 学期 每学期的时间长度和学分上限值均相等 每个专业开设的课程都是确定的 而且课 程在开设时间的安排必须满足先修关系 每门课程有哪些先修课程是确定的 可以有任意 多门 也可以没有 每门课恰好占一个学期 试在这样的前提下设计一个教学计划编制程 序 基本要求 1 输入参数包括 学期总数 一学期的学分上限 每门课的课程号 固定占 3 位的 字母数字串 学分和直接先修课的课程号 2 允许用户指定下列两种编排策略之一 一是使学生在各学期中的学习负担尽量均匀 二是使课程尽可能地集中在前几个学期中 3 若根据给定的条件问题无解 则报告适当的信息 否则将教学计划输出到用户指定的 文件中 计划的表格格式自行设计 测试数据 学期总数 6 学分上限 10 该专业共开设 12 门课 课程号从 C01 到 C12 学分顺序为 2 3 4 3 2 3 4 4 7 5 2 3 先修关系如下 课程编号课程名称先决条件 C1程序设计基础无 C2离散数学C1 C3数据结构C1 C2 C4汇编语言C1 C5语言的设计和分析C3 C4 C6计算机原理C11 C7编译原理C5 C3 C8操作系统C3 C6 C9高等数学无 C10线性代数C9 C11普通物理C9 C12数值分析C9 C10 C1 实现提示 可设学期总数不超过 12 课程总数不超过 100 如果输入的先修课程号不在该专业开设的 课程序列中 则作为错误处理 应建立内部课程序号与课程号之间的对应关系 7 图书借阅管理系统 限图书借阅管理系统 限 1 人完成 人完成 主要分为两大功能 1 图书管理 增加图书 查询图书 删除图书 图书借阅 还书 2 会员管理 增加会员 查询会员 删除会员 借书信息 8 学生成绩管理 限学生成绩管理 限 1 人完成 人完成 实现功能 输入 输出 插入 删除 查找 追加 读入 显示 保存 拷贝 排序 索引 分类合计 退出 9 活期储蓄帐目管理 限活期储蓄帐目管理 限 1 人完成 人完成 活期储蓄处理中 储户开户 销户 存入 支出活动频繁 系统设计要求 1 能比较迅速地找到储户的帐户 以实现存款 取款记账 2 能比较简单 迅速地实现插入和删除 以实现开户和销户的需要 10 二叉排序树的实现 限二叉排序树的实现 限 1 人完成 人完成 用顺序和二叉链表作存储结构 1 以回车 n 为输入结束标志 输入数列 L 生成一棵二叉排 序树 T 2 对二叉排序树 T 作中序遍历 输出结果 3 输入元素 x 查找二叉排序树 T 若存在含 x 的结点 则删除该结点 并作中序遍历 执行操作 2 否则输出信息 无 x 11 最小生成树问题 限最小生成树问题 限 1 人完成 人完成 设计要求 在 n 个城市之间建设网络 只需保证连通即可 求最经济的架设方法 存储结 构采用多种 求解算法多种 12 通讯录的制作 限通讯录的制作 限 1 人完成 人完成 设计目的 用 数据结构 中的双向链表作数据结构 结合 C 语言基本知识 编写一 个通讯录管理系统 以把所学数据结构知识应用到实际软件开发中去 设计内容 本系统应完成一下几方面的功能 1 输入信息 enter 2 显示信息 display 3 查找以姓名作为关键字 search 4 删除信息 delete 5 存盘 save 6 装入 load 设计要求 1 每条信息至包含 姓名 NAME 街道 STREET 城市 CITY 邮编 EIP 国家 STATE 几项 2 作为一个完整的系统 应具有友好的界面和较强的容错能力 3 上机能正常运行 并写出课程设计报告 13 哈夫曼编码哈夫曼编码 译码器 限译码器 限 1 人完成 人完成 问题描述 设计一个利用哈夫曼算法的编码和译码系统 重复地显示并处理以下项目 直到选择退出 为止 基本要求 1 将权值数据存放在数据文件 文件名为 data txt 位于执行程序的当前目录中 2 分别采用动态和静态存储结构 3 初始化 键盘输入字符集大小 n n 个字符和 n 个权值 建立哈夫曼树 4 编码 利用建好的哈夫曼树生成哈夫曼编码 5 输出编码 6 设字符集及频度如下表 字符 空格 A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 进一步完成内容 1 译码功能 2 显示哈夫曼树 3 界面设计的优化 14 图书管理系统 限图书管理系统 限 1 人完成 人完成 问题描述 设计一个计算机管理系统完成图书管理基本业务 基本要求 1 每种书的登记内容包括书号 书名 著作者 现存量和库存量 2 对书号建立索引表 线性表 以提高查找效率 3 系统主要功能如下 采编入库 新购一种书 确定书号后 登记到图书帐目表中 如果表中已有 则只将库存 量增加 借阅 如果一种书的现存量大于 0 则借出一本 登记借阅者的书证号和归还期限 改变 现存量 归还 注销对借阅者的登记 改变该书的现存量 进一步完成内容 1 系统功能的进一步完善 2 索引表采用树表 3 设计内容 4 程序流程图 5 源程序 6 软件测试报告 包括所用到的数据及结果 15 散列 哈希 表的设计与实现 限散列 哈希 表的设计与实现 限 1 人完成 人完成 问题描述 设计散列表实现电话号码查找系统 基本要求 1 设每个记录有下列数据项 电话号码 用户名 地址 2 从键盘输入各记录 分别以电话号码和用户名为关键字建立散列表 3 采用一定的方法解决冲突 4 查找并显示给定电话号码的记录 5 查找并显示给定用户名的记录 进一步完成内容 1 系统功能的完善 2 设计不同的散列函数 比较冲突率 3 在散列函数确定的前提下 尝试各种不同类型处理冲突的方法 考察平均查找长度的变 化 16 利用栈求表达式的值 可供小学生作业 并能给出分数 利用栈求表达式的值 可供小学生作业 并能给出分数 限 限 1 人完成 人完成 要求 要求 建立试题库文件 随机产生 n 个题目 题目涉及加减乘除 带括弧的混合运算 随 时可以退出 保留历史分数 能回顾历史 给出与历史分数比较后的评价 17 二叉树的中序 前序 后序的递归 非递归遍历算法 层次序的非递归遍历算法的实现 二叉树的中序 前序 后序的递归 非递归遍历算法 层次序的非递归遍历算法的实现 应包含建树的实现 应包含建树的实现 限 限 1 人完成 人完成 要求 要求 遍历的内容应是千姿百态的 树与二叉树的转换的实现 以及树的前序 后序的递归 非递归遍历算法 层次序的非递 归遍历算法的实现 应包含建树的实现 要求 要求 遍历的内容应是千姿百态的 18 学生搭配问题 限学生搭配问题 限 1 人完成 人完成 一班有 m 个女生 有 n 个男生 m 不等于 n 现要开一个舞会 男女生分别编号坐在舞池的两 边的椅子上 每曲开始时 依次从男生和女生中各出一人配对跳舞 本曲没成功配对者坐着等 待下一曲找舞伴 请设计一系统模拟动态地显示出上述过程 要求如下 1 输出每曲配对情况 2 计算出任何一个男生 编号为 X 和任意女生 编号为 Y 在第 K 曲配对跳舞的情况 至少求 出 K 的两个值 3 尽量设计出多种算法及程序 可视情况适当加分 提示 用队列来解决比较方便 19 猴子吃桃子问题 限猴子吃桃子问题 限 1 人完成 人完成 有一群猴子摘了一堆桃子 他们每天都吃当前桃子的一半且再多吃一个 到了第 10 天就 只余下一个桃子 用多种方法实现求出原来这群猴子共摘了多少个桃子 要求 1 采用数组数据结构实现上述求解 2 采用链数据结构实现上述求解 3 采用递归实现上述求解 20 数制转换问题 限数制转换问题 限 1 人完成 人完成 任意给定一个 M 进制的数 x 请实现如下要求 1 求出此数 x 的 10 进制值 用 MD 表示 2 实现对 x 向任意的一个非 M 进制的数的转换 3 至少用两种或两种以上的方法实现上述要求 用栈解决 用数组解决 其它方法解决 21 排序综合 限排序综合 限 1 人完成 人完成 利用随机函数产生 N 个随机整数 20000 以上 对这些数进行多种方法进行排序 要求 1 至少采用三种方法实现上述问题求解 提示 可采用的方法有插入排序 希尔排序 起 泡排序 快速排序 选择排序 堆排序 归并排序 并把排序后的结果保存在不同的文件 中 2 统计每一种排序方法的性能 以上机运行程序所花费的时间为准进行对比 找出其中两 种较快的方法 3 如果采用 4 种或 4 种以上的方法者 可适当加分 22 图的遍历的实现 限图的遍历的实现 限 1 人完成 人完成 要求 1 先任意创建一个图 2 图的 DFS BFS 的递归和非递归算法的实现 3 要求用有向图和无向图分别实现 4 要求用邻接矩阵 邻接表多种结构存储实现 23 文本文件单词的检索与计数文本文件单词的检索与计数 设计要求与分析 设计要求与分析 要求编程建立一个文本文件 每个单词不包含空格且不跨行 单词由字符序列构成且区分 大小写 统计给定单词在文本文件中出现的总次数 检索输出某个单词出现在文本中的行 号 在该行中出现的次数以及位置 该设计要求可分为三个部分实现 其一 建立文本文 件 文件名由用户用键盘输入 其二 给定单词的计数 输入一个不含空格的单词 统计 输出该单词在文本中的出现次数 其三 检索给定单词 输入一个单词 检索并输出该单 词所在的行号 该行中出现的次数以及在该行中的相应位置 1 建立文本文件 2 给定单词的计数 3 检索单词出现在文本文件中的行号 次数及其位置 4 主控菜单程序的结构 头文件包含 菜单选项包含 建立文件 单词定位 单词计数 退出程序 选择 1 4 执行相应的操作 其他字符为非法 24 任意长的整数加法 限任意长的整数加法 限 1 人完成 人完成 问题描述 问题描述 设计一个程序实现两个任意长的整数的求和运算 基本要求 基本要求 利用双向循环链表 设计一个实现任意长的整数进行加法运算的演示程序 要 求输入和输出每四位一组 组间用逗号隔开 如 1 0000 0000 0000 0000 25 串的查找和替换串的查找和替换 限 限 1 人完成 人完成 问题描述 问题描述 打开一篇英文文章 在该文章中找出所有给定的单词 然后对所有给定的单词 替换为另外一个单词 再存盘 26 约瑟夫环约瑟夫环 限 限 1 人完成 人完成 问题描述 问题描述 编号为 1 2 n 的 n 个人按顺时针方向围坐一圈 每人持有一个密码 正整数 一开始任选一个正整数作为报数的上限值 m 从第一个人开始按顺时针方向自 1 开始顺 序报数 报到 m 时停止报数 报 m 的人出列 将他的密码作为新的 m 值 从他的顺时针 方向上的下一个开始重新从 1 报数 如此下去 直至所有人全部出列为止 设计一个程序 求出出列顺序 基本要求 基本要求 1 利用单循环链表作为存储结构模拟此过程 2 键盘输入总人数 初始报数上限值 m 及各人密码 3 按照出列顺序输出各人的编号 27 客户消费积分管理系统客户消费积分管理系统 限 限 1 人完成 人完成 问题描述 问题描述 针对客户的消费情况 进行客户管理 根据客户的消费积分对客户实行不同程 度的打折优惠 基本要求 基本要求 1 采用一定的存储结构进行客户信息的存储 2 对客户的信息可以进行修改 删除 添加 3 能够根据消费情况进行客户积分的计算 4 根据积分情况实行不同程度的打折优惠 28 产品进销存管理系统产品进销存管理系统 限 限 1 人完成 人完成 问题描述 问题描述 针对某一种行业的库房的产品进销存情况进行管理 基本要求 基本要求 1 采用一定的存储结构对库房的货品及其数量进行分类管理 2 可以进行产品类的添加 产品的添加 产品数量的添加 3 能够查询库房每种产品的总量 进货日期 销出数量 销售时间等 29 特殊矩阵的压缩存储算法的实现 限特殊矩阵的压缩存储算法的实现 限 1 人完成 人完成 问题描述 问题描述 对于特殊矩阵可以通过压缩存储减少存储空间 基本要求 基本要求 1 针对多种特殊矩阵进行压缩存储 并能显示压缩后的相关地址和值 2 输入在原来特殊矩阵中的地址 要求能从压缩后的矩阵中读出相应的值 30 算术表达式的求解算术表达式的求解 限 限 1 人完成 人完成 问题描述 问题描述 给定一个算术表达式 通过程序求出最后的结果 基本要求 基本要求 1 从键盘输入要求解的算术表达式 2 采用栈结构进行算术表达式的求解过程 3 能够判断算术表达式正确与否 4 对于错误表达式给出提示 5 对于正确的表达式给出最后的结果 31 实时监控报警系统实时监控报警系统 限 限 1 人完成 人完成 问题描述 问题描述 建立一个报警和出警管理的系统 基本要求 基本要求 1 采用一定的存储结构存储报警信息 要求有内容 时间 2 有一次的出警就应该在待处理的信息中删除这条信息 3 记录出警信息 4 待处理信息过多时会发出警告 32 车厢调度车厢调度 限 限 1 人完成 人完成 一列货运列车共有n节车厢 每节车厢将停放在不同的车站 假定n个车站的编号分别为 1 n 货运列车按照第n站至第1站的次序经过这些车站 车厢的编号与它们的目的地相同 为了便于从列车上卸掉相应的车厢 必须重新排列车厢 使各车厢从前至后按编号1到n的 次序排列 当所有的车厢都按照这种次序排列时 在每个车站只需卸掉最后一节车厢即可 我们在一个转轨站里完成车厢的重排工作 在转轨站中有一个入轨 一个出轨和k个缓冲铁 轨 位于入轨和出轨之间 每个缓冲铁轨的容量小于总车厢个数的1 k 图5 5a 给出了 一个转轨站 其中有k 3个缓冲铁轨H1 H2和H3 每个缓冲铁轨的容量为2个车厢 开始时 n节车厢的货车从入轨处进入转轨站 转轨结束时各车厢从右到左按照编号1至编号n的次序 离开转轨站 通过出轨处 在图5 5a 中 n 9 车厢从后至前的初始次序为 5 8 1 7 4 2 9 6 3 如下图所示 给出了按所要求的次序重新排列后的结果 具有三个缓冲铁轨的转轨站 a 开始 b 结束 要求 对于给定的初始状态与终止状态 判断是否能在指定缓冲铁轨的容量条件下调度成 功 如果能 请输出调度的过程 33 迷宫问题 栈 迷宫问题 栈 问题描述 以一个 m n 的长方阵表示迷宫 0 和 1 分别表示迷宫中的通路和障碍 设计一个程序 对 任意设定的迷宫 求出一条从入口到出口的通路 或得出没有通路的结论 基本要求 首先实现一个以链表作存储结构的栈类型 然后编写一个求解迷宫的非递归程序 求得的 通路以三元组 i j d 的形式输出 其中 i j 指示迷宫中的一个坐标 d 表示走到 下一坐标的方向 如 对于下列数据的迷宫 输出的一条通路为 1 1 1 1 2 2 3 2 3 3 1 2 测试数据 迷宫的测试数据如下 左下角 1 1 为入口 右下角 8 9 为出口 实现提示 计算机解迷宫通常用的是 穷举求解 方法 即从入口出发 顺着某个方向进行探索 若 能走通 则继续往前进 否则沿着原路退回 换一个方向继续探索 直至出口位置 求得 一条通路 假如所有可能的通路都探索到而未能到达出口 则所设的迷宫没有通路 可以二维数组存储迷宫数据 通常设定入口点的下标为 1 1 出口点的下标为 n n 为处理方便起见 可在迷宫的四周加一圈障碍 对于迷宫中任一位置 均可约定有东 南 西 北四个方向可通 选做内容 1 编写递归形式的算法 求得迷宫中所有可能的通路 2 以方阵形式输出迷宫及其通路 34 病毒测试程序病毒测试程序 本本题的任务是 当整个网络被感染后 计算有多少台机器被某个特定变种所感染 输入要求 输入由若干组测试数据组成 每组数据的第 1 行包含 2 个整数 M 和 N 1 M N 500 接下来是一个 M N 的矩阵表示网 络的初始感染状态 其中的正 负整数的意义如题目描述中所定义 下面一行给出一个正整数 Q 是将要查询的变种的个数 接下去的 Q 行里 每行给出一个 变种的类型 当 M 或 N 为 0 时 表示全部测试结束 不要对该数据做任何处理 输出要求 对每一组测试 在一行里输出被某个特定变种所感染的机器数量 35 并查集 检查网络并查集 检查网络 题目要求 给定一个计算机网络以及机器间的双向连线列表 每一条连线允许两端的计算 机进行直接的文件传输 其他计算机间若存在一条连通路径 也可以进行间接的文件传输 请写出程序判断 任意指定两台计算机 它们之间是否可以进行文件传输 输入要求 输入若干测试数据组成 对于每一组测试 第 1 行包含一个整数 N 10000 即网络中计算机的总台数 因而每台计算机可用 1 到 N 之间的一个正整数表示 接下来的 几行输入格式为 I C1 C2 或者 C 或者 C C1C2 或者 S 其中 C1 和 C2 是两台计算机的序号 I 表示在 C1 和 C2 间输入一条连线 C 表示检查 C1 和 C2 间是否可以传输文件 S 表示该组 测试结束 当 N 为 0 时 表示全部测试结束 不要对该数据做任何处理 输出要求 对每一组 C 开头的测试 检查 C1 和 C2 间是否可以传输文件 若可以 则在一 行中输出 yes 否则输出 no 当读到 S 时 检查整个网络 若网络中任意两机器间都可以传输文件 则在一行中输出 The network is connected 否则输出 There are k components 其中 k 是网络 中连通集的个数 两组测试数据之间请输出一空行分隔 36 广义表的应用广义表的应用 由于广义表在结构上较线性表复杂得多 因此 广义表的运算也不如线性表简单 本设计 要求实现的广义表的建立 查找 输出 取表头和取表尾以及求深度 求逆表等 本设计用一个主控菜单程序控制 共分为 6 个子系统 1 建立广义表 2 输出广义表 3 结点的查找 4 求广义表表头 5 求广义表表尾 6 求广义表的深度 37 网络流 宇宙旅行网络流 宇宙旅行 题目要求 在走遍了地球上的所有景点以后 旅游狂人开始计划他的宇宙旅行项目 经过谨慎调查 他目前掌握了一张各卫星空间站可以临时容纳的旅客人数列表 但旅客从一个星球飞往另 一个星球时 需要在若干卫星空间站临时停靠中转 而这些空间站不能接待任何旅客驻留 旅客必须立刻转乘另一艘飞船离开 所以空间站不能接待超过自己最大容量的旅客流 为 了估计预算 现在旅游狂人需要知道终点星球的接待站应该设计多大容量 才能使得每艘 飞船在到达时都可以保证让全部旅客下船 输入要求 输入若干组测试数据组成 每组测试数据的第 1 行包含旅行的起点星球和终点星球的名称和一个不超过 500 的正整数 N N 为 0 标志全部测试结束 不要对该数据做任何处理 接下来的 N 行里 数据格式为 sourcei capacityi 其中 sourcei 和 destinationi 是卫 星空间站的名称或起点 终点星球的名称 正整数 capacityi 是飞船从 sourcei 到 destinationi 一次能运载的最大旅客流量 每个名称是由 A Z 之间三个大写字母组成的 字符串 例如 ZJU 测试数据中不包含任何到达起点星球的信息以及任何从终点星球出发的信息 输出要求 对每一组测试 在一行里输出终点星球接待站应具有的最小容量 使得每艘飞船在到达时 都可以保证让全部旅客下船 38 猴子选大王猴子选大王 任务 一堆猴子都有编号 编号是 1 2 3 m 这群猴子 m 个 按照 1 m 的顺序围坐 一圈 从第 1 开始数 每数到第 N 个 该猴子就要离开此圈 这样依次下来 直到圈中只 剩下最后一只猴子 则该猴子为大王 输入数据 输入 m n m n 为整数 n m 输出形式 中文提示按照 m 个猴子 数 n 个数的方法 输出为大王的猴子是几号 建立 一个函数来实现此功能 39 纸牌游戏纸牌游戏 任务 编号为 1 52 张牌 正面向上 从第 2 张开始 以 2 为基数 是 2 的倍数的牌翻一次 直到最后一张牌 然后 从第 3 张开始 以 3 为基数 是 3 的倍数的牌翻一次 直到最后 一张牌 然后 从第 4 张开始 以 4 为基数 是 4 的倍数的牌翻一次 直到最后一张牌 再依次 5 的倍数的牌翻一次 6 的 7 的 直到 以 52 为基数的 翻过 输出 这时正面 向上的牌有哪些 40 拓扑排序拓扑排序 问题描述 建立图的存储结构 能够输入图的顶点和边的信息 并存储到相应存储结构中 再编写函数实现图的拓扑排序 基本要求 选择邻接表作为有向图的存储结构模拟整个过程 并输出拓扑排序的顶点序列 测试数据 利用下图中的数据调试程序 C1 C2 C3 C4C5 C6 C7 C8 C9C10 C11 C12 C1 C2 C3 C4C5 C6 C7 C8 C9C10 C11 C12 41 走迷宫走迷宫 程序开始运行时显示一个迷宫地图 迷宫中央有一只老鼠 迷宫的右下方有一个粮仓 游 戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处 要求 1 老鼠形象可辨认 可用键盘操纵老鼠上下左右移动 2 迷宫的墙足够结实 老鼠不能穿墙而过 3 正确检测结果 若老鼠在规定时间内走到粮仓处 提示成功 否则提示失败 4 找出走出迷宫的所有路径 以及最短路径 42 敢死队问题敢死队问题 有 M 个敢死队员要炸掉敌人的一碉堡 谁都不想去 排长决定用轮回数数的办法来决定 哪个战士去执行任务 如果前一个战士没完成任务 则要再派一个战士上去 现给每个战 士编一个号 大家围坐成一圈 随便从某一个战士开始计数 当数到 5 时 对应的战士就 去执行任务 且此战士不再参加下一轮计数 如果此战士没完成任务 再从下一个战士开 始数数 被数到第 5 时 此战士接着去执行任务 以此类推 直到任务完成为止 排长是不愿意去的 假设排长为 1 号 请你设计一程序 求出从第几号战士开始计数才 能让排长最后一个留下来而不去执行任务 43 HTML 文档标记匹配算法文档标记匹配算法 要求 输入一段 HTML 代码 判断该代码是否符合 HTML 的语法 提示 HTML 文档由不同的标记划分为不同的部分与层次 与括号类似 这些标记需要成对 出现 对于名为的起始标记 相应的结束标记为 常用的 HTML 标记 HTML 文档 文档标题 文档体 节的头部 居中对齐 左对齐 段落 HTML 语言有合理的嵌套 如 44 分配策略分配策略 有 n 个人去分 m 个蛋糕 每个蛋糕的底面积不等 假设蛋糕的高度是相同的 要求 1 一个人只能从某块蛋糕中分到其中的一块 不能从 2 个以上的不同蛋糕中分得蛋 糕 2 要求每个人分到的蛋糕块体积相同 同时 每个分到的蛋糕的体积是最大的 对于给定的 n m 以及 m 各蛋糕的底面积 求分配的方案 以及每人能分到多大面积的蛋糕 例如 假定有 6 个人分 3 块蛋糕 每块底面积的大小分别为 3 9 7 那么最终的分配方案为 1 人分半径为 3 蛋糕 2 人分半径为 7 的蛋糕 3 人分半径为 9 的 蛋糕 每人能分到面积为 3 的蛋糕 45 语言中平衡符号的问题语言中平衡符号的问题 要求 设 C 语言程序代码中包含如下符号 编写程序检测一段 C 代码 中上述符号是否正确 46 烫手山芋问题烫手山芋问题 一群小孩编号为 1 2 n n 0 围成一圈 有一个刚出锅的山芋在他们之间传递 假设 刚开始由 1 号拿着山芋 然后依次计数把山芋交给下一个小孩 当数到某个特定的 k 时 拿着山芋的小孩退出游戏 然后从下一个小孩重新开始计数 如此不断 最后剩下的那个 孩子就是幸运者 要求设计一个程序模拟次过程 并给出不同的 n k 组合下那个幸运者是 谁 47 入学考试问题入学考试问题 某地大学入学考试 相关信息如下 1 参加人数 10 万 2 共有 8 门考试课程 每门课程满分均为 100 分 所有课程成绩均进行了 4 舍 5 入的处理 考生的总分也照此处理 3 所有考生的考试成绩保存在文件 scores txt 中 文件格式如下 每个考生成绩一行 每行格式如下 最开始为考生姓名 然后为每门课程的分数 考生姓 名与课程分数之间 以及不同课程分数之间均用一个英文逗号隔开 如 张三 98 92 60 54 87 75 86 92 个别考生成绩行的格式可能会有误 4 共招收三个批次的学生 第一批次 30000 人 第二批次 60000 人 第三批次 10000 人 录取顺序为 第一批次 第二批次 第三批次 程序要求 1 确定每一批次的录取分数线 并将批次 分数线 实际录取人数输出到文本文件 soutput txt 中 每一批次录取信息占一行 格式自定 确定分数线时 如果在分数线处 有多名考生 则将这些考生全部录取 即每一批次的实际录取人数可能会超过预定人数 例如 假定在确定第一批次分数线时 有 7800 人的总分高于等于 750 分 有 8050 人的总 分高于等于 749 分 则第一批次分数线应确定为 749 分 实际录取人数为 8050 人 2 如果考生成绩行的格式不对 则丢弃该考生的成绩 不作为确定分数线的依据 但要求 将该考生姓名输出到文本文件 serror txt 中 格式自定 3 将总分为 650 分的考生姓名输出到文本文件 soutput txt 中 格式自定 4 将第三批次录取的所有考生的平均成绩 4 舍 5 入 输出到文本文件 soutput txt 中 格式自定 5 要求将下面两个时间值 单位为秒 输出到文件 soutput txt 的最后 从打开 scores txt 文件到读完所有考生成绩的时间 从打开 scores txt 文件到程序结束的时间 48 括号嵌套问题括号嵌套问题 某个序列完全由圆括号组成 一个 和一个 称为一对括号 且序列中的括号成对 出现 设 n 为序列中出现的括号对数 k 为序列中括号的最大嵌套深度 那么 序列 的 n 为 8 k 为 3 1 请编程判断任意给定的圆括号序列 是否是一个深度为 k 的序列 要求 1 先输入嵌套深度 k 然后输入任意一个序列 最后给出判定结果 是 不 是 或者输入序列中的括号不配对 2 可以反复输入数据 当 k 为 0 时 程序结束 while k 0 输入示例 3 2 5 输出的判定结果 测试 1 YES 测试 2 NO 测试 3 括号不配对 2 编程输出括号对数为 n 嵌套深度为 k 的所有序列 1 k nn 时 程序结束 输出结果示例 n 5 k 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 5 对括号 3 层嵌套问题 共求出 18 种情况 3 求解括号对数为 n 嵌套深度为 k 的序列的总数 不输出具体序列 1 k n 30 输入示例 3 2 15 3 20 11 输出结果 3 2 3 种 15 3 497845 种 2011 94817125 种 49 树重建树重建 给出一棵标号树的 BFS 序列和 DFS 序列 设计一个算法重新建立这棵树 结点数 n 1000 当某结点被扩展时 它的所有孩子应该按照编号从小到大的顺序访问 例如一 棵树的 BFS 序列为 43512876 DFS 序列为 43172658 则一棵满足条件的树如右图所示 输入格式 第一行输入结点数 n 第二行 n 个用空格隔开的整数 描述这棵树的 BFS 序列 第三行 n 个用空格隔开的整数 描述这棵树的 DFS 序列 输出格式 一共输出 n 1 行 每行两个整数 i j 描述一条边 表示第 i 个结点与第 j 个结点之间连一 条边 样例输入 8 4 3 5 1 2 8 7 6 4 3 1 7 2 6 5 8 样例输出 4 5 5 8 4 3 3 2 2 6 3 1 1 7 提示 我们曾经遇到过相似的题目 给出一棵二叉树的先序 中序 后续遍历中的其中两 种 要你还原这棵二叉树 而这题改为了给出 DFS 和 BFS 序列 虽然形式上变了 但是原 理还是相似的 我们只需抓住树的性质和充分利用这两个序列的特性就能把这种题目解决 拿题目数据做例子 首先 无论是 BFS 广度优先搜索 序列还是 DFS 深度优先搜索 序列 第一个点都必定是根结点 接着我们看 BFS 序列 跟在根结点 4 后面的连续若干个 结点就是 4 的儿子结点 但是究竟有多少个是 4 的儿子呢 首先 题目中的一个条件说 某结点被扩展时 它的所有孩子应该按照编号从小到大的顺序访问 因此 4 的儿子应该 是按由小到大出现在 BFS 序列中的 后面 31 所以 1 就肯定不是 4 的儿子 然 而即使后面若干个数满足升序的条件 也不一定全都是 4 的儿子 这时我们就要借助 DFS 序列了 因为 DFS 的规律是遍历完一棵子树才到另一棵 所以 4 的儿子在 DFS 序列中也是 按由小到大出现 只是它们之间可能被若干个结点隔开罢了 根据这两个条件 我们就能 判断哪些是 4 的儿子了 例如在 BFS 序列中紧挨着 4 出现的 3 5 在 DFS 序列中也是按照 由小到大的顺序先出现 3 再出现 5 因此 3 5 都是 4 的儿子 接下来怎么做呢 由于 4 的儿子都确定了 剩下的就是把 4 的每一棵子树都确定下来 而这就是一个子问题了 若我们确定了根结点有 k 个儿子 若第 i 个儿子在 DFS 中的位置 为 P1 第 i 1 个儿子在 DFS 中的位置为 P2 则在 DFS 序列中位置 P1 与 P2 之间的所有结点 就是以第 i 个儿子为根的子树的结点 而我们可以建立一个队列 每确定一个结点就把它 加到队列里面去 模拟 BFS 的过程 在模拟广搜的过程中 若当前要处理的结点为 k 由 于以 k 为根的整棵子树在 DFS 序列中是连续的一段 而究竟是那一段在前面的广搜过程中 是可以顺带求出的 然后我们利用 BFS 序列和 DFS 序列中连续的一段确定出 k 的所有儿子 并加到广搜队列里面 直到广搜结束 问题就解决了 50 背包问题的求解背包问题的求解 假设有一个能装入总体积为 T 的背包和 n 件体积分别为 w1 w2 wn 的物品 能否从 n 件物品中挑选若干件恰好装满背包 即使 w1 w2 wn T 要求找出所有满 足上述条件的解 例如 当 T 10 各件物品的体积 1 8 4 3 5 2 时 可找到下列 4 组解 1 4 3 2 1 4 5 8 2 3 5 2 提示 可利用回溯法的设计思想来解决背包问题 首先将物品排成一列 然后顺序选 取物品装入背包 假设已选取了前 i 件物品之后背包还没有装满 则继续选取第 i 1 件物 品 若该件物品 太大 不能装入 则弃之而继续选取下一件 直至背包装满为止 但如果 在剩余的物品中找不到合适的物品以填满背包 则说明 刚刚 装入背包的那件物品 不合适 应将它取出 弃之一边 继续再从 它之后 的物品中选取 如此重复 直至求得满足 条件的解 或者无解 由于回溯求解的规则规则是 后进先出 因此自然要用到栈 51 全国交通咨询模拟全国交通咨询模拟 问题描述 处于对不同目的的旅客对交通工具有不同的要求 例如 因公出差的旅 客希望在旅途中的时间尽可能短 出门旅游的游客则希望旅费尽可能省 而老年旅客则要 求中转次数最少 编制一个全国城市间的交通咨询程序 为旅客提供两种或三种最优决策 的交通咨询 基本要求 1 提供对城市信息进行编辑 如 添加或删除 的功能 2 城市之间有两种交通工具 火车和飞机 提供对列车时刻表和飞机 航班进行编辑 增设或删除 的功能 3 提供两种最优决策 最快到达或最省钱到达 全程只考虑一种交通 工具 4 旅途中耗费的总时间应该包括中转站的等候时间 5 咨询以用户和计算机的对话方式进行 由用户输入起始站 终点站 最优决策原则和交通工具 输出信息 最快需要多长时间才能到达或者最少需要多少旅费 才能到达 并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地 测试数据 实现提示 1 对全国城市交通图和班车时刻表及飞机航班表的编辑 应该提供文 件形式输入和键盘输入两种方式 飞机航班表的信息应包括 起始站的出发时间 终点站 的到达时间和票价 列车时刻表则需根据交通图给出各个路段的详细信息 例如 对于从 北京到上海的火车 需给出北京至天津 天津至徐州及徐州至各段的出发时间 到达时间 和票价信息 2 以邻接表作交通图的存储结构 表示边的结点内除含有邻接点的信 息外 包括交通工具 路程中消耗的时间和花费以及出发和到达的时间等多项属性 52 LZW 压缩器压缩器 解压器解压器 问题描述 为了节省存储空间 常常需要把文本文件采用压缩编码的方式储存 例如 一个包含 1000 个 x 的字符串和 2000 个 y 的字符串的文本文件在不压缩时占用的空间为 3002 字节 每个 x 或每个 y 占用一个字节 两个字节用来表示串的结尾 同样是这个文件 采用游 程长度编码 run length coding 可以存储为字符串 1000 x2000y 仅为 10 个字母 占 用 12 个字节 若采用二进制表示游程长度 1000 和 2000 可以进一步节约空间 如果每 个游程长度占用 2 个字节 则可以表示的最大游程长度为 2 pow 16 这样 上例中的字 符串只需要用 8 个字节来存储 当要读取编码文件时 需要对其进行解码 由压缩器 compressor 对文件进行编码 由解压器 decompressor 进行解码 1 长度 游程编码的压缩 解压 2 LZW 压缩 解压 散列 1 长度 游程编码的压缩 解压 3 霍夫曼编码压缩 解压 霍夫曼树 基本要求 要求选用二种压缩 解压策略实现压缩 解压器 1 为必选 输入的为本文文件 txt 输出的为一种自定义的文件 nz 考虑当构成文本的字符集合为 a b c z 0 1 2 9 时 请用实例测试你的压缩 解压器 你的压缩器会不会出现抖 动 压缩后的文本比原来的还要大 扩充构成文本的字符集合以便使它适应更一般的情 况 实现提示 LZW 由 Lempel Ziv 和 Welch 这三位科学家所开发的技术 该方法把文本的字符串映 射为编码 首先 为该文本中所有可能出现的字母分别分配一个代码 例如 要压缩的对 象是 aaabbbbbbbaabaaba 由 a 和 b 组成 为 a 分配代码 0 为 b 分配代码 1 字符串和编 码的关系被存储在字典中 字典如下 Key 01234567 Code AbAaaab bbbbb bbbaaaba LZW 压缩器不断的在输入文件中寻找在字典中出现的最长的前缀 p 并输出其相应的代 码 若输入文件的下一个字符为 c 则为 pc 分配下一个代码 并插入字典 这种策略称为 LZW 规则 相反 在解压时 编码表由压缩文件重新构造 LZW 原则使这种重建成为可能 如上例子 压缩时 文件中第一个在字典中出现的最长前缀是 a 输出其编码 0 然后为字符串 aa 分配代码 2 并插入到字典中 余下的字符串在字典中出现的最长前缀是 aa 输出 aa 的对应代码 2 同时为字符串 aab 分配代码 3 并将其插入到字典中 依次类推 由此 输出 0214537 解压时 要输入代码 然后用代码所表示的文本来替换这些代码 代码到文本的映 射可按下面的方法重建 首先把分配给单一字母的代码插入到字典中 象前面一样 字典 的入口为 key code 对 然而此时是根据给定的代码 key 去寻找相应的入口 而不是根 据文本 Code 压缩文件中的第一个代码对应于单一的字母 因此可以由该字母代替 对 于压缩文件中的其他代码 p 要考虑两种情况 1 在字典中 2 不在字典中 在 1 情况下 找到 p 对应的文本 text p 输出 并且 根据压缩原理可知 若在压缩 文件中代码 q 写在 p 之前且 text q 是与 q 对应的文本 则压缩器会为文本 text q 其后 紧跟 fc p text p 的第一个字符 分配一新代码 因此在字典中插入序偶 下一个代码 text q fc p 情况 2 时 只有在当前文本段形如 text q text q fc q 且 text p text q fc q 时才会发生 相应的压缩文件段是 qp 在压缩过程中 为 text q fc q 分配的代码为 p 在解压过程中 在用 text q 代替 q 后 又遇到代码 p 然而 此时字典中没有与 p 对应的 文本 因为这种情况只在解压文本段为 text p text q fc q 时才发生 因此可以对 p 解 码 当遇到一个没有定义代码文本对的代码 p 时 p 对应的文本为 text q fc q 其中 q 为 p 前面的代码 如上例子 首先 初始化字典 在其中插入 0 a 1 b 压缩的第一个代码为 0 则用 a 代替之 下一个代码 2 未定义 因为前一个代码为 0 且 text 0 a fc 0 a 则 text 2 text 0 fc 0 aa 因此用 aa 代替 2 并把 2 aa 插入字典中 下个代码 1 由 b 来替换 并把 3 text 2 fc 1 3 aab 插入字典中 依次类推 得解压结果 53 奇数阶幻方求解奇数阶幻方求解 要求必须在空间复杂度为 O N 的要求下实现 N 阶幻方的输出 Problem description 幻方是一种很有意思的数字矩阵 在很早著名的九宫八卦阵就与幻方有关 幻方的定义为 1 到 N N 的整数填入 N N 的方格中 每行和每列以及对角线的数字之和必须是相等的 你作为八卦公司的顶级程序员 现在需要你解决一个问题 将任意奇数阶的幻方找出 来 Input 输入包括多个测试集 每行为一个正奇数 N 1 N 1000 0 作为输入的结束且不 需要处理 Output 对于输入的每一个 N 输出一个它所对应的 N 阶幻方 如果存在多个 任意一个即可 每个幻方为 N N 的矩阵 对于每个幻方 每行输出幻方的一行 每行中的数字之间用一个或多个空格分开 不 同的幻方之间用一个空行分开 Sample Input 1 3 0 Sample Output 1 4 9 2 3 5 7 8 1 6 54 偶数阶幻方求解偶数阶幻方求解 对于给定的 n 求出 2 n 2 n 的幻方的所有情况 但是要去除所有等价的情形 所谓等价 就是通过旋转或翻转后相同的情形 55 城市链表城市链表 问题描述 将若干城市的信息 存入一个带头结点的单链表 结点中的城市信息包括 城市名 城市的位置坐标 要求能够利用城市名和位置坐标进行有关查找 插入 删除 更新等操 作 基本要求 1 给定一个城市名 返回其位置坐标 2 给定一个位置坐标 P 和一个距离 D 返回所有与 P 的距离小于等于 D 的城市 测试数据 由学生依据软件工程的测试技术自己确定 注意测试边界数据 56 约瑟夫生死者游戏约瑟夫生死者游戏 问题描述 约瑟夫 Joeph 问题的一种描述是 编号为 1 2 n 的 n 个人按顺时针方向围坐一 圈 每人持有一个密码 正整数 一开始任选一个正整数作为报数上限值 m 从第一个人 开始按顺时针方向自 1 开始顺序报数 报到 m 时停止报数 报 m 的人出列 将他的密码作 为新的 m 值 从他在顺时针方向上的下一个人开始重新从 1 报数 如此下去 直至所有人 全部出列为止 试设计一个程序求出出列顺序 基本要求 利用单向循环链表存储结构模拟此过程 按照出列的顺序印出各人的编号