数据结构课程设计题目2015.pdfVIP

《数据结构》课程设计题目

1.排序算法的性能分析

问题描述

设计一个测试程序，比较几种内部排序算法的关键字比较次数和移动次数以取得直观感

受。

基本求

（）对冒泡排序、直接排序、选择排序、箱子排序、堆排序、快速排序及归并排序算法进

1

行比较。

（）待排序表的表长不小于，表中数据随机产生，至少用组不同数据作比较，比较

21005

指标：关键字参加比较次数和关键字的移动次数（关键字交换记为次移动）。

3

（）输出比较结果。

3

选做内容

（）对不同表长进行比较。

1

（）验证各算法的稳定性。

2

（）输出界面的优化。

3

2.排序算法思想的可视化演示—1

基本求

排序数据随机产生，针对随机案例，对冒泡排序、箱子排序、堆排序、归并算法，提供排序

执行过程的动态图形演示。

3.排序算法思想的可视化演示—2

基本求

排序数据随机产生，针对随机案例，，对插入排序、选择排序、基数排序、快速排序算法，

提供排序执行过程的动态图形演示。

4.线性表的实现与分析

基本求

①设计并实现线性表。

②线性表分别采取数组（公式化描述）、单链表、双向链表、间接寻址存储方

式

③针对随机产生的线性表实例，实现线性表的插入、删除、搜索操作动态演示(图

形演示)。

5.等价类实现及其应用

问题描述：某工厂有一台机器能够执行n个任务，任务i的释放时间为r（是一个整数），

i

最后期限为d（也是整数）。在该机上完成每个任务都需一个单元的时间。一种可行的调

i

度方案是为每个任务分配相应的时间段，使得任务i的时间段正好位于释放时间和最后期限

之间。一个时间段不允许分配给多个任务。

基本求：

使用等价类实现以上机器调度问题。

等价类分别采取两种数据结构实现。

6.一元稀疏多项式计算器

问题描述

设计一个一元稀疏多项式简单计算器。

基本求

一元稀疏多项式简单计算器的基本功能是：

（）输入并建立多项式；

1

（）输出多项式，输出形式为整数序列：，，，，，„，，其中是多项式的

2nc1e1c2e2,cnenn

项数，，，分别是第项的系数和指数，序列按指数降序排序；

cieii

（）多项式和相加，建立多项式；

3aba+b

（）多项式和相减，建立多项式；

4aba-b

（）计算多项式在处的值；

5x

（）计算器的仿真界面（选做）

6

7.长整数的代数计算

问题描述

应用线性数据结构解决长整数的计算问题。设计数据结构完成长整数的表示和存

储，并编写算法来实现两长整数的加、减、乘、除等基本代数运算。

基本求

①长整数长度在一百位以上。

②实现两长整数在取余操作下的加、减、乘、除操作，即实现算法来求解a+bmodn,a-b

modn,abmodn,abmodn。

③输入输出均在文件中。

④分析算法的时空复杂性。

8.敢死队问题。

有个敢死队员炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪

M

个战士去执行任务。如果前一个战士没完成任务，则再派一个战士上去。现给每个战士编

一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到时，对应的战士就去执行

5

任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始