文档介绍：《数据结构》实践环节考核指导
一、类型
课程实验考核
二、目的与要求
本课程的目的和任务是使学习者掌握各种常用的数据结构和典型算法,为学习后续计算机专业课程提供必要的基础,提高学习者运用数据结构解决实际问题的能力。本考核主要达到两个目的:
、存储结构以及算法的理解程度。
。
三、考核环境
软件要求:
DOS 操作系统或Windows环境的MS-DOS模式;
Turbo C 。
四、考核内容
1、线性表的插入和删除
要求对有序顺序表进行插入和删除操作,设数据域为整数。
要求对有序单链表进行插入和删除操作,单链表的数据域是字符串,但不允许重复的串插入表中。删除操作是根据输入的字符串,先找到相应的结果后删除之。
2、栈和队列操作
对一些简单应用问题,如进制转换、字符串输入等,利用栈或队列来实现。
3、二叉树操作
要求采用二叉链表作为存储结构,完成二叉树的建立,先序、中序和后序以及按层次遍历及求所有叶子和结点个数的操作等。
4、图的遍历操作
可采用邻接矩阵或邻接表作为存储结构,完成有向图和无向图的DFS和BFS操作。
5、数据查找
实现顺序查找、折半查找及二叉排序查找算法,比较他们的查找速度。
6、排序
实现直接插入、冒泡、直接选择、快速、堆、归并排序、并鼓励实现基数排序。比较各种排序算法的运行速度。
五、考核时间与形式
考核时间为60分钟;
采用闭卷形式,所有答案都直接做到考核盘上。
六、注意事项
1、试卷和考核盘都要清楚地书写姓名、准考证号和机号信息;
2、必须用蓝、黑色钢笔或圆珠笔书写,字迹要清楚、卷面要整洁。
3、考试期间严禁左顾右盼、交头接耳;对机器或试卷中出现的问题由监考老师负责解决。
七、题型与要求
请参考以下样题。
样题一
要求:(文件内容见附录一)复制到本地计算机的硬盘上,然后按要求填入相应的语句,调试运行,并按下面要求输入测试数据,在答题纸上写出你所填入的语句以及运行测试的结果。
题目:已知在顺序存储结构的线性表L上,以递减顺序输入几个整数:96,64,52,48,43,33,18,12,,使之能顺利完成该递减序列的插入和删除操作。设表L中不应有相同的数据元素。测试数据为:依次插入5、18、57,再依次删除48、20、12。(注:线性表从第0个位置开始存放数据。)
答案:
(1)
(2)
(3)
(4)
测试结果为:
样题二
要求:(文件内容见附录二)复制到本地计算机的硬盘上,然后按要求填入相应的语句,调试运行,并按下面要求输入测试数据,在答题纸上写出你所填入的语句以及运行测试的结果。
题目:由键盘任意键入n个正整数关键字,采用堆排序法进行排序,输出第一趟、第五趟及最后一趟的结果。测试数据为:取n=10,建立时输入25,12,53,6,45,36,7,78,62,17。
答案:
(1)
(2)
测试结果为:
样题三
要求:(文件内容见附录三)复制到本地计算机的硬盘上,然后按要求填入相应的语句,调试运行,并按