《数据结构》教学大纲
“Data Structures” Syllabus
Course Code | |
Course Title | Data Structures |
Course Category | Specialty Basic Courses |
Course Nature | Compulsory Course |
Class Hours | Total: 64 Lab:16 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) |
|
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 (1)Introduction of Data Structures 2 hours (2)Algorithm 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. (1)List 3 hours (2)Stack 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 (1)Definition and storage of binary tree 2 hours (2)Traversal of binary tree, binary search tree 2 hours (3)Heap 2 hours (4)Huffman 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 (1)Definition and basic storage structures of general trees 2 hours (2)Sequential 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. 5. Search 6 hours (1)Introduction of search algorithms, and hash tables 2 hours (2)Collision resolution 2 hours (3)Implementation 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 (1)linear index 1 hours (2)2-3 tree 2 hours (3)B+ 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 (1)insertion sort, bubble sort, selection sort 1 hours (2)shell sort 1 hours (3)quick sort, merge sort 2 hours (4)heap 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 (1)basic terminology and storage structure of graph 1 hours (2)graph traversal 2 hours (3)topological sort 1 hour (4)shortest path problem 2 hours (5)minimum 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. 9. Application of Data Structures 3 hours (1)Review of the basic data structures 1 hour (2)Application 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语言版),清华大学出版社,2003年7月再版; [5]肖南峰,赵洁,数据结构与算法设计,电子工业出版社,2006年12月出版; [6] 傅清祥,王晓东,算法与数据结构,电子工业出版社,2001; [7] 吴文虎,王建德,实用算法的分析与程序设计,电子工业出版社,1998; [8] William F.,William T.,Data Structures with C++,Prentice Hall,Inc.,1996; |
Prepared by Whom and When | Jianming Lv 15/4/2019 |
《数据结构》实验教学大纲
课程代码 | 045100162 |
课程名称 | 数据结构 |
英文名称 | Data Structure |
课程类别 | 专业基础课 |
课程性质 | 必修 |
学时 | 总学时:64 实验学时:16 其他学时(MOOC): 8 |
学分 | 3.5 |
开课学期 | 第三学期 |
开课单位 | 计算机科学与工程学院 |
适用专业 | 计算机科学与技术、网络工程、信息安全 |
授课语言 | 中英文双语授课 |
先修课程 | 高级语言程序设计C++ |
毕业要求(专业培养能力) | 本课程对学生达到如下毕业要求有如下贡献: №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 |
制定人及发布时间 | 吕建明2019年4月15日 |
《数据结构》实验教学内容与学时分配
实验项目编号 | 实验项目名称 | 实验学时 | 实验内容提要 | 实验类型 | 实验要求 | 每组人数 | 主要仪器设备与软件 |
1 | 线性表、栈和队列结构及相关算法 | 4 | 熟悉线性表的逻辑结构特性;掌握栈和队列的实现方法 | 设计性 | 必做 | 1 | 台式电脑 C++编程环境 ACMOJ平台 |
2 | 树与二叉树的表示及相关算法 | 4 | 熟悉二叉树的结构特性以及各种存储结构的特点及适用范围;掌握基于二叉树的递归算法实现。 | 设计性 | 必做 | 1 | 台式电脑 C++编程环境 ACMOJ平台 |
3 | 排序与查找算法 | 4 | 掌握常用的排序方法,并能实现各种排序算法;掌握哈希表查找的算法。 | 设计性 | 必做 | 1 | 台式电脑 C++编程环境 ACMOJ平台 |
4 | 图的表示及算法 | 4 | 熟悉图的各种存储结构及其构造算法;了解并掌握图的应用问题的经典算法。 | 设计性 | 必做 | 1 | 台式电脑 C++编程环境 ACMOJ平台 |
“Data Structures” Syllabus
Course Code | 045100162 |
Course Title | Data Structures |
Course Category | |
Course Nature | Compulsory Course |
Class Hours | Total: 64 Lab:16 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语言版),清华大学出版社,2003年7月再版; [5]肖南峰,赵洁,数据结构与算法设计,电子工业出版社,2006年12月出版; [6] 傅清祥,王晓东,算法与数据结构,电子工业出版社,2001; [7] 吴文虎,王建德,实用算法的分析与程序设计,电子工业出版社,1998; [8] William F.,William T.,Data Structures with C++,Prentice Hall,Inc.,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 |