上海市高等教育自学考试

计算机科学与技术专业(专升本)

《数据结构》实践性环节考核大纲

(上海交通大学主考，2018年修订)

一、考核目标

1．掌握运用数据结构解决实际问题的能力；

2．掌握数据的逻辑结构、存储结构以及算法的运用；

3．掌握选择数据结构以及算法设计和实现的能力。

二、运行环境

1. 平台：Windows 7，Windows10等

2. 软件：Visual C++6.0、Turbo C等

三、考核方式

实行闭卷考核。

四、考核时间和日期

上机考核每次为1小时；考核日期另行规定。

五、考核范围

1、线性表的基本操作

1)  对顺序表进行初始化、查找、插入和删除等基本操作；

2)  对单链表进行初始化、查找、插入和删除等基本操作。

2、栈和队列基本操作

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

3、二叉树操作

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

4、图的遍历操作

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

5、数据查找

1)  实现顺序查找、折半查找及二叉排序查找算法，比较他们的查找速度。

6、排序

1)  实现直接插入、冒泡、直接选择、快速、堆、归并排序。比较各种排序算法的运行速度。