《数据结构》教学大纲

课程代码

045100162

课程名称

数据结构

英文名称

Data Structure

课程类别

专业基础课

课程性质

必修

学时

总学时:64 实验学时:16  其他学时(MOOC:  8

学分

3.5

开课学期

第三学期

开课单位

计算机科学与工程学院

适用专业

计算机科学与技术、网络工程、信息安全

授课语言

中英文双语授课

先修课程

高级语言程序设计C++

课程对毕业要求的支撑

本课程对学生达到如下毕业要求有如下贡献:

№2.问题分析:能够应用数学、自然科学和工程科学的基本原理,识别、表达、并通过文献研究分析计算机复杂工程问题,以获得有效结论。

3.设计/开发解决方案:能够设计针对复杂与计算机相关工程问题的解决方案,设计满足特定需求的系统、单元(部件)或工艺流程,并能够在设计环节中体现创新意识,考虑社会、健康、安全、法律、文化以及环境等因素。


课程目标

完成课程后,学生将具备以下能力:

  1. 掌握线性表、树与二叉树、图等基础数据结构,以及掌握分析算法时间复杂度和空间复杂度的方法。

  2. 能够灵活应用数据结构知识,对现实中的工程问题进行分析,对适用的数据结构以及算法进行对比论证。

  3. 能够设计针对计算机工程复杂问题的解决方案,设计满足特定需求的数据结构和算法,并能够在设计环节中体现创新意识。具有较复杂计算机系统研发基本能力,具备问题分析和建模的能力。

课程简介

数据结构是计算机学科各专业的一门重要专业基础课程。本课程主要论述数据的逻辑结构、存储结构、算法设计以及算法评价四方面的内容,使学生对线性表、栈、队列、树、图等各种数据结构以及查找、排序等基础算法有深入的了解;还要求学生针对具体的工程问题,系统地掌握在不同的数据结构上进行有关算法设计的思想和技巧。数据结构是一门理论性和实践性都很强的课程。


教学内容与学时分配

(一)绪论部分                           4学时

1)思政教育与课程介绍  2学时

2)算法复杂度分析     2学时

教学要求:了解数据结构在国民经济和社会发展中的重要作用,了解数据结构在计算机专业教学体系中的重要位置。要求掌握数据结构的定义,基本术语以及数据结构的基本类型;了解数据结构与算法的关系;并掌握算法复杂度的定义以及分析方法。

重点:数据结构的基本类型以及相应的应用场景。

难点:算法复杂度的分析方法。


(二)线性表                             5学时

1)线性表            3学时

2)栈与队列          2学时

教学要求:掌握线性表的定义,存储实现方法,以及插入、删除、定位等基本运算;学习栈和队列的基本定义、基本操作,并灵活运用线性表解决现实工程问题。

重点:线性表的数组和链表两种实现方法的优点和缺点,以及实现线性表的插入、删除和定位等基本运算算法。掌握栈的入栈、出栈和队列的入队、出队操作。

难点:掌握单链表及循环链表上进行综合应用算法设计;在循环队列上进行入队、出队以及求队列长度操作。


(三)二叉树                              8学时

1)二叉树的定义、存储    2学时

2)二叉树的遍历、二叉查找树    2学时

3)堆    2学时

4)哈夫曼树    2学时

教学要求:学习二叉树的基本定义,存储实现方式,掌握二叉树遍历、查找等基本操作;学习堆和哈夫曼树的基本原理和实现方法。

重点:基于链接和数组两种存储结构的二叉树实现方法;基于递归的二叉树遍历算法;二叉查找树的查找、删除节点、添加节点操作的实现。

难点:堆的构建以及插入删除节点的算法实现;哈夫曼树和哈夫曼编码的原理。


(四)普通树                              4学时

1)普通树的定义以及基本存储结构    2学时

2)普通树的序列化存储结构    2学时

教学要求:学习普通树的基本定义、遍历算法;掌握树的基本存储结构的原理;重点:掌握左孩子右兄弟树的实现方法;了解普通树和森林与二叉树的相互转换方法。

难点:掌握普通树的序列化存储的方法。


(五)查找6学时

1)查找概述、哈希表的原理、哈希函数设计    2学时

2)冲突解决策略    2学时

3)哈希表的实现    2学时

教学要求:掌握查找的基本原理,学习二分查找法;掌握哈希表的原理、构建以及相关操作。

重点:哈希表的原理,哈希函数的设计方法,以及哈希表的插入、删除算法的实现。

难点:哈希表的冲突解决策略。


(六)索引                               5学时

1)线性索引   1学时

22-3树    2学时

3B+树    2学时

教学要求:掌握索引的作用,学习线性索引、2-3树索引以及B/B+树索引的构建方法,以及算法复杂度分析方法。

重点:线性索引和2-3树索引的插入、删除和查找算法;B树和B+树的定义。

难点:B树和B+树的插入、删除和查找算法。


(七)排序                               6学时

1)插入排序、冒泡排序、选择排序    1学时

2)希尔排序    1学时

3)快速排序、归并排序    2学时

4)堆排序、基数排序 2学时


教学要求:掌握排序算法的定义、排序算法的稳定性分析方法、排序算法的设计与实现、排序算法的复杂度对比分析、以及排序算法的应用。

重点:快速排序算法、归并排序算法以及堆排序算法的实现。

难点:希尔排序算法的原理、实现,快速排序算法的改进。


(八)图7学时

1)图的基本术语、存储结构 1学时

2)图的遍历 2学时

3)拓扑排序 1学时

4)最短路径问题 2学时

5)最小生成树 1学时

教学要求:掌握图的定义、实现方法,学习图的遍历算法、拓扑排序算法、最短路径算法以及最小生成树算法

重点:图的邻接表和邻接矩阵两种实现方法的原理以及优缺点对比,基于递归函数的图的遍历算法的实现,拓扑排序算法的实现方法以及应用。

难点:Dijkstra最短路径算法、Floyd最短路径算法、以及最小生成树算法。


(九)数据结构综合运用   3学时

1)基础数据结构的回顾 1学时

2)基于实例的数据结构综合运用 2学时

教学要求:对前面所教授过的线性表、树、图基础数据结构进行系统的回顾;并结合实例分析面向实际工程问题的数据结构设计方法。


实验教学(包括上机学时、实验学时、实践学时)

实验学时为16学时,以上机的形式进行。

教学方法

课程教学以课堂教学、课外作业、MOOC教学、综合讨论、线上实验等方法共同实施。

考核方式

本课程注重过程考核,成绩比例为:

考勤和MOOC线上作业:10%

平时实验:20%

期末机试:10%

期末考试(闭卷):60%


教材及参考书

 [1] Clifford A. Shaffer, “A Practical Introduction to Data Structures and Algorithm Analysis (2nd edition)”, Publishing House of Electronics Industry (Chinese Publisher), 2009

[2] Adam Drozdek, “Data Structures and Algorithms in C++ (2nd edition)”, Brooks/Cole, 2001

[3] Nell Dale, “C++ Data Structures (3rd edition)”, Jones and Bartlett Publishers, Inc, 2003

 [4]严蔚敏,吴伟民,数据结构(C语言版),清华大学出版社,20037月再版;

 [5]肖南峰,赵洁,数据结构与算法设计,电子工业出版社,200612月出版;

[6] 傅清祥,王晓东,算法与数据结构,电子工业出版社,2001

[7] 吴文虎,王建德,实用算法的分析与程序设计,电子工业出版社,1998

[8] William F.William T.Data Structures with C++Prentice HallInc.1996

制定人及制定时间

吕建明 2019415

 “Data Structures” Syllabus

Course Code

 045100162

Course Title

Data Structures

Course Category

Specialty Basic Courses

Course Nature

Compulsory Course

Class Hours

Total64     Lab16   Other (MOOC):  8

Credits

3.5

Semester

3rdsemester

Institute

School of Computer Science and Engineering

Program Oriented

Computer Science and Technology, Network Engineering, Information Security

Teaching Language

Chinese-English Bilingual Teaching

Prerequisites

C++ Programming

 Student Outcomes

 (Special Training Ability)

  1. Problem Analysis: An ability to identify, formulate and analyze complex engineering problems, reaching to substantiated conclusions using basic principles of mathematics, science, and engineering.

  2. Design / Development Solutions: An ability to design solutions for complex engineering problems and innovatively design systems, components or process that meet specific needs with societal, public health, safety, legal, cultural and environmental considerations.


Course Objectives

After the course, the students will enhance their ability in the following aspects:

1. Students will understand the basic data structures including lists, binary trees, general trees, and graphs, and master the time and spatial complexity analysis techniques of algorithms.

2. Students can use the data structure knowledge flexibly for the engineering problems in real world, and do comparison among different data structures.

3. Students can design the data structures and algorithms to address the specific demands from complex computer engineering problems creatively, and have the ability of problem analysis, modeling and implementation of complex computer systems.

Course Description

Data Structure is a very important disciplinary basic course of computer science. The main topics of this course include logical structures, storage structures, algorithm design and algorithm evaluation.  The course may help students to understand the basic data structures including list, stack, queue, tree and graph, and some basic algorithms such as searching and sorting. Moreover, the students are trained to grasp the algorithm design techniques related to different data structures in specific engineering problems. In a word, Data structure is a course covering a lot of theoretical and practical topics simultaneously.

Teaching Content and Class Hours Distribution

1. Introduction.     4 hours

1Introduction of Data Structures    2 hours

2Algorithm complexity analysis    2 hours


Teaching Requirements: students are required to understand the definition, terminology, and basic types of data structures; understand the relationship between data structures and algorithms; and grasp the definition and analysis technologies of algorithm complexity; understand the important application of data structures for society development.

Key Points: the basic types of data structures and related use cases.

Difficult Points: the methods to analyze algorithm complexity.

2. List     5 hours.

1List              3 hours

2Stack and Queue    2 hours


Teaching Requirements: students are required to understand the definition, storage structures of lists; learn the basic operations of lists such as insertion, remove and search; learn the basic definitions and operations of stacks and queues; and apply lists to solve practical engineer problems flexibly.  

Key Points:  the advantages and disadvantages of array-based and link-based list; the basic algorithms of lists such as insertion, remove and search; push and pop operation of stacks; enqueue and dequeue operation of queues.

Difficult Points: algorithm design of singly-linked lists and doubly-linked lists; the enqueue, dequeue, and length counting operations of circular queues.


3. Binary Tree       8 hours

1Definition and storage of binary tree      2 hours

2Traversal of binary tree, binary search tree   2 hours

3Heap    2 hours

4Huffman Tree    2 hours


Teaching Requirements: learn the basic definitions and storage structures of binary trees; grasp the traversal and search operations of binary trees; learn the basic theory and implementation methods of heaps and Huffman trees.

Key Points: implementation of link-based and array-based binary trees; recursive traversal algorithms of binary trees; implementation of search, remove and insertion operations of binary trees.

Difficult Points: heap construction; insertion and remove operations of heaps; Huffman tree and Huffman coding.


4. General Tree   4 hours

1Definition and basic storage structures of general trees  2 hours

2Sequential implementation of general trees  2 hours


Teaching Requirements: students are required to learn the definition and traversal algorithms of general trees; and grasp the basic storage structures of general trees.

Key points: implementation of left-child right-sibling trees; transferring general trees and forests into binary trees.
Difficult points: sequential implementation of general trees.


5. Search 6 hours

1Introduction of search algorithms, and hash tables  2  hours

2Collision resolution  2 hours

3Implementation of hash tables  2 hours


Teaching Requirements: students are required to understand the theory of basic search; learn the binary search algorithms; learn the basic theory, construction and related operations of hash tables.

Key points: theory of hash tables; design of hash functions; insertion, remove algorithms of hash tables.

Difficult points: Collision resolution strategies of hash tables.


6. Indexing     5 hours

1linear index   1 hours

22-3 tree    2 hours

3B+ tree    2 hours


Teaching Requirements: students are required to study the function of indexes; learn the construction of linear indexes, 2-3 tree, and B/B+ tree indexes and analysis of the complexity of related algorithms.

Key points:  the insertion, remove, search algorithms of linear indexes and 2-3 tree indexes; the definition of B/B+ trees.

Difficult points: the insertion, remove and search algorithms of B/B+ trees.


7. Sorting    6 hours

1insertion sort, bubble sort, selection sort   1 hours

2shell sort    1 hours

3quick sort, merge sort    2 hours

4heap sort, radix sort      2 hours


Teaching Requirements: students are required to understand the definition of sorting algorithms; learn the methods to analyze the steadiness of sorting algorithms; learn design and implementation of sorting algorithms; and learn the complexity analysis, comparison and application of sorting algorithms.

Key points: implementation of the quick sort, the merge sort and the heap sort algorithms.

Difficult points: basic theory and implementation of the shell sort algorithm; improvement of the quick sort algorithm.


8.  Graph.    7 hours

1basic terminology and storage structure of graph  1 hours

2graph traversal     2 hours

3topological sort    1 hour

4shortest path problem 2 hours

5minimum cost spanning tree  1 hour


Teaching Requirements: students are required to understand the definition and implementation of graphs; and learn the graph traversal algorithms, the topological sorting algorithm, the shortest path algorithms and minimum cost spanning tree algorithms.

Key points: adjacency matrix and adjacency list of graphs; recursive graph traversal algorithms, topological sorting algorithms.

Difficult points: the Dijkstra shortest path algorithm, the Floyd shortest path algorithm and the minimum spanning tree algorithms.


9Application of Data Structures   3 hours

1Review of the basic data structures   1 hour

2Application analysis of data structures in real use case  2 hours

Teaching Requirements: review of the basic data structures including lists, trees and graphs; design of data structures towards real practical engineering problems.



Experimental Teaching

16 hours of experiments in labs

Teaching Method

Teaching in classrooms, homework, MOOC online teaching, online discussion, and online experiment.

Examination Method

Participation and MOOC exercises: 10%

Lab assignment: 20%

Final operating examination: 10%

Final exam: 60%

Teaching Materials and Reference Books

[1] Clifford A. Shaffer, “A Practical Introduction to Data Structures and Algorithm Analysis (2nd edition)”, Publishing House of Electronics Industry (Chinese Publisher), 2009

[2] Adam Drozdek, “Data Structures and Algorithms in C++ (2nd edition)”, Brooks/Cole, 2001

[3] Nell Dale, “C++ Data Structures (3rd edition)”, Jones and Bartlett Publishers, Inc, 2003

 [4]严蔚敏,吴伟民,数据结构(C语言版),清华大学出版社,20037月再版;

 [5]肖南峰,赵洁,数据结构与算法设计,电子工业出版社,200612月出版;

[6] 傅清祥,王晓东,算法与数据结构,电子工业出版社,2001

[7] 吴文虎,王建德,实用算法的分析与程序设计,电子工业出版社,1998

[8] William F.William T.Data Structures with C++Prentice HallInc.1996

Prepared by Whom and When

Jianming Lv 15/4/2019


数据结构》实验教学大纲

课程代码

045100162

课程名称

数据结构

英文名称

Data Structure

课程类别

专业基础课

课程性质

必修

学时

总学时:64 实验学时:16  其他学时(MOOC:  8

学分

3.5

开课学期

第三学期

开课单位

计算机科学与工程学院

适用专业

计算机科学与技术、网络工程、信息安全

授课语言

中英文双语授课

先修课程

高级语言程序设计C++

毕业要求(专业培养能力)

本课程对学生达到如下毕业要求有如下贡献:

№2.问题分析:能够应用数学、自然科学和工程科学的基本原理,识别、表达、并通过文献研究分析计算机复杂工程问题,以获得有效结论。

3.设计/开发解决方案:能够设计针对复杂与计算机相关工程问题的解决方案,设计满足特定需求的系统、单元(部件)或工艺流程,并能够在设计环节中体现创新意识,考虑社会、健康、安全、法律、文化以及环境等因素。


课程培养学生的能力(教学目标)

完成课程后,学生将具备以下能力:

  1. 掌握线性表、树与二叉树、图等基础数据结构,以及掌握分析算法时间复杂度和空间复杂度的方法。

  2. 能够灵活应用数据结构知识,对现实中的工程问题进行分析,对适用的数据结构以及算法进行对比论证。

  3. 能够设计针对计算机工程复杂问题的解决方案,设计满足特定需求的数据结构和算法,并能够在设计环节中体现创新意识。具有较复杂计算机系统研发基本能力,具备问题分析和建模的能力。

课程简介

数据结构是计算机学科各专业的一门重要专业基础课程。本课程主要论述数据的逻辑结构、存储结构、算法设计以及算法评价四方面的内容,使学生对线性表、栈、队列、树、图等各种数据结构以及查找、排序等基础算法有深入的了解;还要求学生针对具体的工程问题,系统地掌握在不同的数据结构上进行有关算法设计的思想和技巧。数据结构是一门理论性和实践性都很强的课程。


主要仪器设备与软件

台式电脑

C++ 编程环境

ACM OJ平台

实验报告

在线自动评判,无须提交实验报告

考核方式

本课程注重过程考核,成绩比例为:

考勤和MOOC线上作业:10%

平时实验:20%

期末机试:10%

期末考试(闭卷):60%

教材、实验指导书及教学参考书目

[1] Clifford A. Shaffer, “A Practical Introduction to Data Structures and Algorithm Analysis (2nd edition)”, Publishing House of Electronics Industry (Chinese Publisher), 2009

[2] Adam Drozdek, “Data Structures and Algorithms in C++ (2nd edition)”, Brooks/Cole, 2001

[3] Nell Dale, “C++ Data Structures (3rd edition)”, Jones and Bartlett Publishers, Inc, 2003

制定人及发布时间

吕建明2019415


数据结构》实验教学内容与学时分配

实验项目编号

实验项目名称

实验学时

实验内容提要

实验类型

实验要求

每组人数

主要仪器设备与软件

1

线性表、栈和队列结构及相关算法

4

熟悉线性表的逻辑结构特性;掌握栈和队列的实现方法

设计性

必做

1

台式电脑

C++编程环境

ACMOJ平台

2

树与二叉树的表示及相关算法

4

熟悉二叉树的结构特性以及各种存储结构的特点及适用范围;掌握基于二叉树的递归算法实现。


设计性

必做

1

台式电脑

C++编程环境

ACMOJ平台

3

排序与查找算法

4

掌握常用的排序方法,并能实现各种排序算法;掌握哈希表查找的算法。


设计性

必做

1

台式电脑

C++编程环境

ACMOJ平台

4

图的表示及算法

4

熟悉图的各种存储结构及其构造算法;了解并掌握图的应用问题的经典算法。

设计性

必做

1

台式电脑

C++编程环境

ACMOJ平台


 “Data StructuresSyllabus

Course Code

045100162

Course Title

Data Structures

Course Category

Disciplinary Basic Course

Course Nature

Compulsory Course

Class Hours

Total64     Lab16   Other (MOOC):  8

Credits

3.5

Semester

3rdsemester

Institute

School of Computer Science and Engineering

Program Oriented

Computer Science and Technology, Network Engineering, Information Security

Teaching Language

Chinese-English Bilingual Teaching

Prerequisites

C++ Programming

Student Outcomes (Special Training Ability)

№2.Problem Analysis: An ability to identify, formulate and analyze complex engineering problems, reaching to substantiated conclusions using basic principles of mathematics, science, and engineering.

3.Design / Development Solutions: An ability to design solutions for complex engineering problems and innovatively design systems, components or process that meet specific needs with societal, public health, safety, legal, cultural and environmental considerations.


Teaching Objectives

After the course, the students will enhance their ability in the following aspects:

1. Students will understand the basic data structures including lists, binary trees, general trees, and graphs, and master the time and spatial complexity analysis techniques of algorithms.

2. Students can use the data structure knowledge flexibly for the engineering problems in real world, and do comparison among different data structures.

3. Students can design the data structures and algorithms to address the specific demands from complex computer engineering problems creatively, and have the ability of problem analysis, modeling and implementation of complex computer systems.

Course Description

Data Structure is a very important disciplinary basic course of computer science. The main topics of this course include logical structures, storage structures, algorithm design and algorithm evaluation.  The course may help students to understand the basic data structures including list, stack, queue, tree and graph, and some basic algorithms such as searching and sorting. Moreover, the students are trained to grasp the algorithm design techniques related to different data structures in specific engineering problems. In a word, Data Structureis a course covering a lot of theoretical and practical topics simultaneously.

Instruments and Equipments

Desktop Computer for each student

C++ environment

AMC OJ Platform

Experiment Report

Experiment report is not necessary.  The online judgment is available.

Assessment

Participation and MOOC exercises: 10%

Lab assignment: 20%

Final operating examination: 10%

Final exam: 60%

Teaching Materials and Reference Books

[1] Clifford A. Shaffer, “A Practical Introduction to Data Structures and Algorithm Analysis (2nd edition)”, Publishing House of Electronics Industry (Chinese Publisher), 2009

[2] Adam Drozdek, “Data Structures and Algorithms in C++ (2nd edition)”, Brooks/Cole, 2001

[3] Nell Dale, “C++ Data Structures (3rd edition)”, Jones and Bartlett Publishers, Inc, 2003

 [4]严蔚敏,吴伟民,数据结构(C语言版),清华大学出版社,20037月再版;

 [5]肖南峰,赵洁,数据结构与算法设计,电子工业出版社,200612月出版;

[6] 傅清祥,王晓东,算法与数据结构,电子工业出版社,2001

[7] 吴文虎,王建德,实用算法的分析与程序设计,电子工业出版社,1998

[8] William F.William T.Data Structures with C++Prentice HallInc.1996

Prepared by Whom and When

Jianming Lv 15/4/2019

 “Data Structures”Experimental Teaching Arrangements

No.

Experiment Item

Class Hours

Content Summary

Category

Requirements

Number of StudentsEach Group

Instruments, Equipments and Software

1

 List, stack, queue

4

 learn the logical structures of linear lists, and learn the implementation methods of stacks and queues

Design

Compulsory

1

Desktop Computer for each student

C++ environment

AMC OJ Platform

2

 Algorithms of binary trees and general trees

4

 Learn the use cases of varied storage structures of binary trees, and learn how to implement the recursive algorithms based on binary trees.


Design

Compulsory

1

Desktop Computer for each student

C++ environment

AMC OJ Platform

3

Sorting and searching

4

Learn to implement the frequently-used sorting algorithms, and learn the search algorithms of hash tables


Design

Compulsory

1

Desktop Computer for each student

C++ environment

AMC OJ Platform

4

Graph

4

Learn the varied storage structures and construction algorithms of graphs, and learn some algorithms to solve classic graph problems

Design

Compulsory

1

Desktop Computer for each student

C++ environment

AMC OJ Platform