浙江工业大学自考《数据结构》实践考核大纲

浙江工业大学自考《数据结构》实践考核大纲已经公布，讲解了《数据结构》实验内容、实验要求、考核标准等相关内容，详情见下文：

浙江工业大学自考《数据结构》实践考核大纲

《数据结构》实验

一、实验内容

1. 单链表的插入和删除：要求单链表的数据域是字符串，完成单链表的初始化、插入、删除操作，插入时不允许重复的串插入表中。

2. 栈操作：采用顺序存储结构,完成建栈、数据元素入栈与出栈、判断栈空、判断栈满等操作。

3. 二叉树操作：采用二叉链表作为存储结构,完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作等。

4. 图的遍历操作：可采用邻接矩阵或邻接表作为存储结构，完成有向图和无向图的DFS和BFS操作。

5. 数据查找：实现顺序查找、折半查找以及在二叉排序树上的查找算法，比较它们的查找速度。实验时所输入的数据可按有序和随机产生去组织。

6. 排序：实现直接插入、冒泡、直接选择、快速、堆、归并等排序算法，比较各种排序算法的速度。

二、实验要求

在实验内容中选择一个完整的题目，在VC++环境下完成实验。要求写出实验报告，上交电子DOC文档。

三、考核标准

1. 上交实验报告前，指导教师检查程序和实验结果。通过若干个提问，检查实验的独立完成情况。

2. 依据实验报告，检查实验内容是否符合要求。

四、实验报告样本

数据结构实验报告

设计者：***** 考号：******************* 联系电话*****************

1. 实验选题 查找、排序算法的实现和效率分析。

2. 实验要求和目的

要求: 随机产生 N=100、200、500、1000、2000个整数并存放于数组A[N]中。用顺序查找、冒泡排序实现各组数字的查找和排序，并计算出平均比较次数和平均移动次数。

目的: 通过这次实验，了解查找、排序算法的实现，并对算法的效率进行分析。

3. 实验设计

数据结构设计: 数学模型为动态一维整型数组。

4. 测试

⑴ 顺序查找算法测试

在DOS界面下运行SEARCH程序,在界面提示出"请输入需查找数组中数字的个数:"后，打入数组的N值，界面上将显示出数组中所有数字，然后在界面提示出"请输入需查找的数字:"后，键入一个查找数开始进行查找，运行结束后如果找到该数，界面上将显示该数在数组中所在的位置，否则显示"未找到!"，同时还会显示查找的比较次数。

例：N值为50时，键入数组中存在的任一数值，屏幕上出现该数在数组中的位置。同时显示出比较的次数。

顺序查找的平均查找长度为(N+1)/2.

⑵ 冒泡排序算法测试

在DOS界面下运行SORT程序，在界面提示出"请输入需排序数组的个数:"后，打入数组的N值，界面上将数组中数字按原有的顺序予以显示，程序运行完毕后，显示出排序后的数组数字，同时显示出数据交换的次数。

例：N值为50时，屏幕上将数组中数字按原有的顺序予以显示，程序运行完毕后，显示出排序后的数组数字，同时显示出数据交换的次数为547。

5. 心得

通过该次实验，掌握了查找和排序算法的实现方法，熟悉了C语言的使用。顺序查找算法平均查找长度较大，特别是当N很大时，查找效率较低，但具有算法简单的优点。冒泡排序是内部排序算法中较好的一种排序方法。

来源：http://www.sce.zjut.edu.cn/index.php/management/article_detail/3819?mark=0