自考指导

自考《数据结构》实践环节试题考核指导一

《数据结构》实践环节考核指导

一、类型

课程实验考核

二、目的与要求

本课程的目的和任务是使学习者掌握各种常用的数据结构和典型算法，为学习后续计算机专

业课程提供必要的基础，提高学习者运用数据结构解决实际问题的能力。本考核主要达到两

个目的：

1．检查学生对数据的逻辑结构、存储结构以及算法的理解程度。

2．检查学生对数据结构的选择以及算法设计和实现的应用能力。

三、考核环境

软件要求：

DOS操作系统或Windows环境的MS-DOS模式；

TurboC3.0系统。

四、考核内容

1、线性表的插入和删除

要求对有序挨次表进行插入和删除操作，设数据域为整数。

要求对有序单链表进行插入和删除操作，单链表的数据域是字符串，但不允许重复的串插入

表中。删除操作是按照输入的字符串，先找到相应的结果后删除之。

2、栈和队列操作

对一些简单应用问题，如进制转换、字符串输入等，利用栈或队列来实现。

3、二叉树操作

要求采用二叉链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历及

求所有叶子和结点个数的操作等。

4、图的遍历操作

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

5、数据查找

实现挨次查找、折半查找及二叉排序查找算法，比力他们的查找速度。

6、排序

实现直接插入、冒泡、直接选择、快速、堆、归并排序、并鼓励实现基数排序。比力各种排

序算法的运行速度。

五、考核时间与形式

考核时间为60分钟；

采用闭卷形式，所有答案都直接做到考核盘上。

六、注意事项

1、试卷和考核盘都要清楚地书写姓名、准考证号和机号信息；

2、必需用蓝、黑色钢笔或圆珠笔书写，笔迹要清楚、卷面要整洁。

3、考试期间严禁左顾右盼、窃窃私语；对机器或试卷中出现的问题由监考老师负责解决。

七、题型与要求

请参考以下样题。

样题一

要求：将考试目录下的c源程序test1.c（文件内容见附录一）复制到本地计算机的硬盘上，

然后按要求填入相应的语句，调试运行，并按下面要求输入测试数据，在答题纸上写出你所

填入的语句以及运行测试的结果。

标题问题：已知在挨次存储结构的线性表L上，以递减挨次输入几个整数：96，64，52，

48，43，33，18，12，在test1.c中填入相应语句，使之能顺利完成该递减序列的插入和删

除操作。设表L中不应有相同的数据元素。测试数据为：依次插入5、18、57，再依次删除

48、20、12。（注：线性表从第0个位置开始存放数据。）

答案：

（1）

（2）

（3）

（4）

测试结果为：

样题二

要求：将考试目录下的c源程序test2.c（文件内容见附录二）复制到本地计算机的硬盘上，

然后按要求填入相应的语句，调试运行，并按下面要求输入测试数据，在答题纸上写出你所

填入的语句以及运行测试的结果。

标题问题：由键盘任意键入n个正整数关键字，采用堆排序法进行排序，输出第一趟、第五

趟及最后一趟的结果。测试数据为：取n=10，建立时输入25，12，53，6，45，36，7，78，

62，17。

答案：

（1）

（2）

测试结果为：