|
|
发表于 2019-12-13 20:57:37
|
显示全部楼层
1 字符串距离（65分）
目的：字符串是一种基础且广泛使用的数据结构，与字符串相关的题目既可
以考察基本程序设计能力和技巧，也可以考查算法设计能力。
题目：求字符串之间距离
要求：设有字符串 X，称在 X 的头尾及中间插入任意多个空格后构成的新
字符串为 X 的扩展串，如字符串 X 为“abcbcd”，则字符串“abcb□cd”，“□a□bcbcd□”
和“abcb□cd□”都是 X 的扩展串，这里“□”代表空格字符。如果 A1 是字符串 A 的
扩展串，B1 是字符串 B 的扩展串，A1 与 B1 具有相同的长度，那么定义字符串
A1 与 B1 的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定
义为它们的 ASCII 码的差的绝对值，而空格字符与其它任意字符之间的距离为
已知的定值 K，空格字符与空格字符的距离为 0。在字符串 A、B 的所有扩展串
中，必定存在两个等长的扩展串 A1、B1，使得 A1 与 B1 之间的距离达到最小，
将这一距离定义为字符串 A、B 的距离。请编写程序，求出字符串 A、B 的距离。 2 求最长公共子串（70分）
求解 2 个字符串的最长公共子串。输入的 2 个字符串可以从键盘读入，也可
以从两个文本文件中读入。
实现提示：对于采用动态规划法和后缀树算法的，要对算法设计思想能够进
行详细阐述，并分析算法的时间复杂和空间复杂度。能够详细阐述多种算法并设
计完成的，总分可达到 80 分。 3 集合运算（60分）
问题描述：
设有两个用单链表表示的集合 A、B，其元素类型是 int 且以递增方式存储，
其头结点分别为 a、b。要求下面各问题中的结果集合同样以递增方式存储，结
果集合不影响原集合。
实现要求：
（1）编写集合元素测试函数 IN_SET，如果元素已经在集合中返回 0，否则
返回 1；
（2）编写集合元素输入并插入到单链表中的函数 INSERT_SET，保证所输
入的集合中的元素是唯一且以递增方式存储在单链表中；
（3）编写集合元素输出函数，对建立的集合链表按递减方式输出；
（4）编写求集合 A、B 的交 C=A∩B 的函数，并输出集合 C 的元素；
（5）编写求集合 A、B 的并 D=A∪B 的函数，并输出集合 D 的元素；
（6）求集合 A 与 B 的对称差 E=（A-B）∪（B-A） 的函数，并输出集合 D
的元素；
（7）设计一个菜单，具有输入集合元素、求集合 A、B 的交 C、求集合 A、
B 的并 D、求集合 A 与 B 的对称差 E、退出等基本的功能。
测试数据：由读者自定，但集合 A、B 的元素个数不得少于 16 个。
4 二叉树结点染色问题（70分）
目的：二叉树是常用的重要非线性数据结构，在客观世界中有着广泛的应用。
通过本题可以加深对于二叉树这一数据结构的理解。掌握二叉树的存储结构及各
种操作。
要求：一棵二叉树可以按照如下规则表示成一个由 0、 1、 2 组成的字符序列，
我们称之为“二叉树序列 S”：
例如，下图所表示的二叉树可以用二叉树序列 S=21200110 来表示。
任务是要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或
蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，
那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉树序列，请求出
这棵树中最多和最少有多少个点能够被染成绿色。
5 散列表的设计与实现（65分）
任务：设计散列表实现电话号码查找系统。
要求：
①设每个记录有下列数据项：用户名、电话号码、地址；
②从键盘输入各记录，以用户名（汉语拼音形式）为关键字建立散列表；
③采用一定的方法解决冲突；
④查找并显示给定电话号码的记录；
可以选作内容：
①系统功能的完善；
②设计不同的散列函数，比较冲突率；
③在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均
查找长度的变化。
6 求有向图简单路径（80分）
简单路径：如果一条路径上的顶点除了起点和终点可以相同外，其它顶点均
不相同，则称此路径为一条简单路径；起点和终点相同的简单路径称为回路（或
环）。
要求：
①求出有向图中从起点到终点的所有简单路径。其中起点和终点可以由用户
自行设定。
②求出有向图中从起点到终点的指定长度（如 K）的所有简单路径。其中起
点和终点可以由用户自行设定。 7 关键路径问题（80分）
问题描述：设计一个程序求出完成整项工程至少需要多少时间以及整项工程
中的关键活动。
基本要求： （1）对一个描述工程的 AOE 网，应判断其是否能够顺利进行。
（2）若该工程能顺利进行，输出完成整项工程至少需要多少时间，以及每
一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。
8 布尔表达式真值问题（80分）
目的：本课程设计是求中缀算术表达式真值问题。求中缀算术表达式值的问
题是数据结构中栈的一个典型应用。通过本题，学生应掌握中缀表达式和后缀表
达式的转换方法和后缀表达式求值问题。
要求：已知某种类型的布尔表达式由“T”、“F”、“！”、“&”和“|”组成，其中，
“T”代表真值 True，“F”代表真值 False，“！”代表逻辑非运算，“&”代表逻辑与运
算，“|”代表逻辑或运算。并且，运算符“！”、“&”和“|”的优先级为：“！”最高，
“|”最低，“&”介于“！”和“|”之间。你的任务是，计算给定布尔表达式的真值。
例如，布尔表达式“（T|T）&F&（F|T）”的真值为“F”. 9 字符串模式匹配算法比较（70分）
用三种以上方法实现字符串模式匹配，比如 BF、KMP 和 BM 方法等，并利
用科学合理的方法针对这几种方法进行性能比较。
10 排序算法及性能对比（70分）
编程实现快速排序、堆排序、希尔排序、冒泡排序、归并排序算法，学生可
增加其它排序算法，并完成不同排序算法的性能对比分析。
要求：
①时间性能包括平均时间性能、最好情况下的时间性能、最差情况下的时间
性能等。
②实验数据应具有说服力，包括：
规模范围要大（如从 100 到 10000）
数据的初始特性类型要多，因而需要具有随机性；
实验数据的组数要多，即同一规模的数组要多选几种不同类型的数据来实验。
③算法所用时间必须是机器时间，也可以包括比较和交换元素的次数。
④实验分析及其结果要能以清晰的方式来描述，如数学公式或图表等。
⑤要给出实验的方案及其分析。
11 广义表实现（80分）
选择合适的存储结构表示广义表，并能实现下列运算要求：
①用大写字母表示广义表，用小写字母表示原子，并提供设置广义表的值的
功能。
②取广义表 L 的表头和表尾的函数 head（L）和 tail（L）。
③能用这两个函数的复合形式求出广义表中的指定元素。
④由广义表的字符串形式到广义表的转换函数 Lists Str_ToLists_（S）；
例如
Str_ToLists_（“ （a,（a,b）,c）”）的值为一个广义表。
⑤由广义表到广义表的字符串形式的转换函数 char * Lists_To_Str（L）。
⑥最好能设置多个广义表。
12 后缀表达式计算器（全部完成85分，完成①和②75分）
目的：后缀表达式不包含括号，运算符放在两个运算对象的后面，所有的计
算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：
2 1 + 3 *,即（2 + 1） * 3
通过本课程设计，应使学生掌握后缀表达式的特点、栈的基本方法和基本原
理，培养学生运用语言编程及调试的能力，运用数据结构解决简单的实际问题的
能力，为后续计算机专业课程的学习打下坚实的基础。
要求：实现一个简单的后缀表达式计算器。假定表达式里的基本数值为实数，
可用的运算符包括+,-,*,/,^，其中的 ^ 表示求幂运算。
①假定输入表达式里的数和运算符之间都有空格，这样可以简化输入的处理；
②输入的算术表达式以分号为结束符。计算器应该能输入并计算一系列表达
式，遇到一行的第一个字符就是分号时程序结束。
③上题的计算器增加一元函数功能，允许表达式里写 sin, cos, tan, log（自然
对数）等函数，还可以考虑加入自定义的其他数学函数。（选做） |
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2019-12-6 15:03:08
置顶卡
千斤顶
显身卡
楼主
谢谢你，帮我开张了