【数据结构课程】算法设计题
题目01.
文本编辑
编写一个程序，能够让用户输入一页文字，每行最多不超过80个字符，共N行； 程序可以统计出文字、数字、空格的个数，做插入、删除等操作；能够查找一个或多个字符是否在文档中；能够保存文件，并能对已有的文件打开进行修改。可参考Windows的记事本操作。
相关数据结构：线性结构，查找、插入、删除操作，或者KMP算法 题目02.
校园导航问题
设计深圳大学的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。
相关数据结构：图的表示，最短路径算法 题目03.
迷宫求解
迷宫用一个二维数组表示，其元素值有两个：0和1，0表示通路，1表示阻塞。数组左上方元素为迷宫入口，右下方元素为迷宫出口。要求寻找一条从入口到出口的通路（不一定是最短的）。
相关数据结构：栈 题目04.
表达式求值
输入一个四则运算表达式，按照运算符优先级计算表达式的结果。要求表达式以一个字符串的形式输入；表达式支持浮点数和负数运算；支持加减乘除和括号运算。
相关数据结构：栈 题目05.
八皇后问题
在国际象棋盘上放8个皇后，国际象棋棋盘共有8行8列，皇后可以吃掉与之同行、同列、同一对角线上的其他皇后。为让她们共存，请编写算法找出各种放置方法。
相关数据结构：线性结构+穷举法，或者树结构+回溯法 题目06.
Huffman码的编/译码系统
利用Huffman树进行编码和解码。要求对一个字符串（支持英文、数字和符号即可，长度任意）进行Huffman编码，并输出编码结果。
要求接受一个Huffman编码系统，然后对另一串已编码的Huffman串进行译码，并输出字符串。要求能够支持合法性和非法性检查。
相关数据结构：树结构，Huffman算法 题目07.
二叉树构建方法
实现二叉树构建的三种方法：
1. 已知二叉树的数组存储结构，运用性质5构建二叉树，并输出树状的二叉树结构 2. 已知二叉树的先序和中序遍历结果，构建二叉树，并输出树状的二叉树结构 3. 已知二叉树的中序和后序遍历结果，构建二叉树，并输出树状的二叉树结构 相关数据结构：树结构，树的遍历 题目08.
散列查找电话号码
设计一张散列表实现对电话记录的查找。要求每个电话记录包含：用户名、电话号码、地址；从键盘输入多条电话记录，用户名（汉语拼音形式）为关键字建立散列表；采用一定的方法解决冲突；要求能够查找并显示电话记录的完整信息；
相关数据结构：Hash函数、Hash冲突、Hash表 题目09.
最经济通信网
在n个城市之间建立通信网络，每两个城市之间的线路建设成本各不相同，设计算法在最节省成本的条件下建立这个通信网。
相关数据结构：图结构、最小生成树算法 题目10.
关键路径
一个工程项目包含若干个活动，有些活动是可以同时进行，有些活动之间有先后顺序，每个活动都有不同的活动时间。设计算法找出完成工程的最短时间以及最短路径。
相关数据结构：AOE网、关键路径算法 题目11.
平衡二叉树的构建与遍历
给定一个关键字序列，生成一棵AVL树（平衡二叉排序树）；并输出该AVL树的先根遍历序列和中根遍历序列。
相关数据结构：树结构、平衡二叉树算法 题目12.
链式基数排序
对一个关键字序列采用链式基数排序方法进行排序，要求支持扑克牌的排序，包括花色的比较和数值比较。在数值比较重，1（即Ace）是最大，其他从小到达依次为2-10JQK。
相关数据结构：链式基数排序 题目13.
n阶幻方问题
一个n阶幻方是把从1到n2的整数赶往一个n阶方阵，每一个数只出现一次。要求每一行、每一列、第一条主对角线的和都相等。设计一个算法，找出所有的n阶幻方
相关数据结构：线性结构、贪心法 题目14.
多机调度问题
设有n个独立的作业（1, 2, …, n）， 这n个作业由m台相同的机器进行加工处理。作业
可以在任何一台机器上加工处理，但必须一次性完成。作业需要的加工时间都不相同，设计一个算法，使所给n个作业在尽可能短的时间内由m台机器处理完成
相关数据结构：队列、贪心法 题目15.
图着色问题
给定一个连通图 G，用K种颜色对G中的顶点着色，使任意两个相邻顶点着色不同，设计一个算法求图G的最小色数K。
相关数据结构：图结构、贪心法 题目16.
世界名画陈列馆问题
世界名画陈列馆由m x n个陈列室组成，为防止名画被盗，需要在陈列室中设置警卫机器人哨位。 每个警卫机器人除了监视它所在的陈列室外，还可监视与它所在陈列室相邻的上、下、左、右4个陈列室。 设计一个算法，安排警卫机器人哨位，使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下，且所用的警卫机器人最少
相关数据结构：回溯法 题目17.
大整数计算器问题
设计程序，实现大整数（200位以内的整数）的加、减、乘、除四则运算，输出这两个大整数的和、差、积、商及余数。
相关数据结构：线性结构
题目18. 排队打水问题
有n个人排队到r个水龙头去打水，他们装满水桶的时间t1、t2、……、tn为整数且各不相等，请安排他们的打水顺序才能使他们总共花费的时间最少。
相关数据结构：贪心法 题目19.
最近点对问题
在二维平面上的 n 个点中，如何快速的找出最近的一对点，请尽量降低时间复杂度。
相关数据结构：分治法\\穷举法 题目20.
棋盘覆盖问题
在一个2k×2k个方格组成的棋盘中,若有一个方格是黑色，其他为白色。任务是用包含3个方格的L型牌覆盖所有白色方格，且黑色方格不能覆盖，且任意白色方格不能被两个或更多牌覆盖。
相关数据结构：递归法、分治法 题目21.
循环赛日程表问题
有n=2k个运动员进行网球循环赛，需要设计比赛日程表。每个选手都必须与其他n-1个选手比赛一次，且每个选手每天只能参加一次比赛，循环赛共进行n-1天。按此要求设计一张比赛日程表，它又n行和n-1列，第i行表示第i个选手，第j列表示第j天，第i行j列表示第i号选手在第j天要比赛的选手编号。
相关数据结构：递归法、分治法 题目22.
马周游问题
国际象棋棋盘共有8行8列，国际象棋中的马走法比较特殊：每步棋先横走或直走一格，
然后再斜走一格；或者先斜走一格，最后再横走或竖走一格。假设马在棋盘的某一位置，它是否可能只走63步，正好将除起点外的其他63个位置各走一次？如果有一种这样的走法，则称所走的这条路线为一匹马的周游路线。设计一个算法，找出一匹马的周游路线。
相关数据结构：树结构、分治法 题目23.
最佳调度问题
假设有n 个任务由k 个可并行工作的机器完成。完成任务i 需要的时间为Ti。试设计一个算法找出完成这n 个任务的最佳调度，使得完成全部任务的时间最早。
相关数据结构：回溯法 题目24.
金块分配问题
老板有一袋金块（共x块，x是2的n次法），将有2名最优秀的雇员每人得到其中的
一块，排名第一的雇员得到袋子中最重的金块，排名第二的雇员得到袋子中最轻的金块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重的金块和最轻的金块。
相关数据结构：分治法 题目25.
最长公共子序列问题
如果Z既是X的子序列，又是其它字符序列的子序列，而且Z是这些字符序列中最长的子序列，则称Z为这些字符序列的最长公共子序列设计程序。
在一个目录下，有若干程序文档，请查找出重复最大的两篇文档。要求：对两篇程序文档中，每个函数作最长公共子序列比较。相同字符最多的两篇文档为最终要求的文档。
相关数据结构：KMP算法、穷举法、动态归划法 题目26.
乘船问题
有N个人，第i个人的重量为Wi，每艘船的最大载重量为C，且每次最多载两人，要相关数据结构：贪心法 题目27.
狱吏问题
求用最少的船装所有的人。
某国王对囚犯进行大赦，让一狱吏n次通过一排锁着的n间牢房，每通过一次，按所定规划转动n间牢房中的某些门锁，每转动一次，原来锁着的被打开，原来打开的被锁上；通过n次后，门锁开着的，牢房中的犯人放出，否则犯人不得获释。
相关数据结构：穷举法 题目28.
导弹拦截问题
某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。假设导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，并依次输出被拦截的导弹飞来时候的高度。（假如：依次飞来的导弹高度为：389，207，155，300，299，170，158，65；最大拦截导弹数目为6，即389，300，299，170，158，65）
相关数据结构：动态规划法 题目29.
求最大行走路线问题
在一个NxN的棋盘上，每个格子中有若干粒麦子。假设起点为左上角的格子，且规定每次只能向右或向下走一格，请设计一个行走路线，使经过的格子中的麦子数目最多。
相关数据结构：动态规划法 题目30.
内存管理之伙伴系统算法（适用已学操作系统）
伙伴系统是操作系统使用的一种动态存储管理方法，包含分配和回收操作。在伙伴系统中，无论占用块还是空闲块，块大小都是2k个字。当用户申请n个字的内存空间，系统将分配2k个字的内存块给用户，由此可利用的空闲块大小也只能是2的k次方。
了解伙伴系统算法，实现伙伴系统的空间表结构，并实现内存分配和回收功能。程序输出结果要显示内存状态图、分区说明表和空闲分区表。
相关数据结构：线性结构 题目31.
CPU调度之多级反馈队列（适用已学操作系统）
实现CPU调度的多级反馈队列算法，调度对象是进程，包含属性：名称、到达时间、运行时间等，属性可根据算法需要自行添加。每级队列时间片长度是上一级的两倍。本算法假定同一时间只有一个进程进入队列，不考虑时间片用不完赠送的情况，当一个进程没有用完时间片就结束，不赠送时间，立刻调度下一个进程。提示：用队列对象来编程会更简单。
要求程序输出结果要有进程调度顺序、进程完成时间、进程调度过程说明，有良好的结果界面。
相关数据结构：线性结构
题目32. CPU调度系列算法（适用已学操作系统）
实现CPU调度的时间片轮转算法（抢占式）、高响应比算法（非抢占式）、短作业优先（非抢占式），调度对象是进程，包含属性：名称、到达时间、运行时间等，属性可根据算法需要自行添加。提示：用队列对象来编程会更简单。
其中，时间片轮转算法要考虑时间片用不完赠送的情况。要求程序输出结果要有进程调度顺序、进程完成时间、进程调度过程说明，有良好的结果界面。
相关数据结构：线性结构 题目33.
内存管理之连续分配算法（适用已学操作系统）
实现内存管理的连续分配多个算法，包括首适应、循环首适应、最坏适应、最佳适应算法，要求实现内存空间表结构，并实现内存分配和回收功能。程序输出结果要显示内存状态图、分区说明表和空闲分区表。
相关数据结构：线性结构 题目34.
磁盘调度系列（适用已学操作系统）
实现磁盘调度的先来先服务、最短寻道时间优先、电梯调度、循环扫描四个算法。调度对象是进程，包含属性：编号、磁道号。注意，算法还包含其他设置需要自行添加。要求程序输出结果要有进程调度顺序、每次调度移动距离，平均移动距离，有良好的结果界面
相关数据结构：线性结构
