课程代码

045100162

课程名称

数据结构

英文名称

Data Structure

课程类别

专业基础课

课程性质

必修

学时

总学时：64 实验学时：16

学分

3.5

开课学期

第三学期

开课单位

计算机科学与工程学院

适用专业

计算机科学与技术创新班、联合班

授课语言

英文授课

先修课程

无

课程对毕业要求的支撑

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

1. 设计/开发解决方案：能够设计针对计算机工程复杂问题的解决方案，设计满足特定需求的计算机软硬件系统，并能够在设计环节中体现创新意识，考虑社会、健康、安全、法律、文化以及环境等因素。

2. 研究：培养学生具备计算机系统相关知识并对计算机工程复杂问题进行研究，具有计算机系统研发基本能力、具备问题分析和建模的能力，具有系统级的认知能力和实践能力，掌握自底向上和自顶向下的问题分析方法。

课程目标

1. 期望学生通过使用合适的数据类型和算法来提高他们的编程技能。[1、2、3]

2. 该课程为计算机科学课程提供必要的编程背景。[1、2]

课程简介

本课程探讨了计算机科学中的一些基础数据结构和算法，并学习用C ++实现它们。 数据结构包括链表，堆栈，队列，树，堆，哈希表和图。此外，本课程还讨论了包括搜索，排序，遍历树和图，散列以及最短路径的算法。

教学内容与学时分配

（1）引言和算法分析（2学时）

• 学习数据结构的动机

• 数据结构的基本知识

• 在时间复杂性，Big-O，Big-Omega和Big-Theta方面评估算法的性能。

（2）列表，堆栈和队列（5学时）

• 基于数组的列表和链表的算法和实现。还有他们的优点和缺点

• 栈和队列的算法和实现

（3）二叉树（7学时）

• 二叉树，二叉搜索树和堆的算法

• 树的详细实现包括时间复杂度的降低

（4）非二叉树（5学时）

• 非二叉树的实现方法及其优缺点

• 非二叉树的遍历算法

（5）内部排序（6学时）

• 基本和简单的排序方法：冒泡，插入和选择排序

• 介绍了进步排序方法的实现和算法

（6）搜索（6学时）

• 顺序排序方法及其改进方法

• 堆的介绍和处理碰撞的方法

（7）索引（6学时）

• 线性索引和非线性索引

• 讨论了树结构索引的详细算法，包括2-3树，B树和B +树。

（8）图（7学时）

• 图的探索

• 从图形到树的转换

• 在图中实现经典算法，包括生成树和最短路径算法

（9）高级树结构（4学时）

• 处理不平衡树问题的先进方法：AVL

• 间隔堆的详细实现

实验教学（包括上机学时、实验学时、实践学时）

（1）列表，堆栈和队列（4学时）

• 在表上实现

• 使用列表，堆栈和队解决问题

（2）二叉树和非二叉树（4学时）

• 用指针实现非二叉树

• 使用二叉树和非二叉树解决问题

（3）排序和搜索（4学时）

• 实现排序和搜索方法

• 使用排序和搜索方法解决问题

（4）索引和图表（4学时）

• 实现B-树

• 图探索

• 使用图解决问题

教学方法

讲座，教程，实验室，讨论，中期测试，考试

考核方式

考勤：10%

作业：15%

期中考试：25%

期末考试（闭卷）：50%

教材及参考书

现用教材：Clifford A. Shaffer, “A Practical Introduction to Data Structures and Algorithm Analysis (3rd edition)”, Publishing House of Electronics Industry (Chinese Publisher), 2013

主要参考资料：

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

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

制定人及制定时间

陈百基，2019年4月14日

Course Code

045100162

Course Title

Data Structure

Course Category

Specialty Basic Courses

Course Nature

Compulsory Course

Class Hours

Total Teaching Hours: 64  Lab Hours: 16

Credits

3.5

Semester

Third Semester

Institute

School of Computer Science and Engineering

Program Oriented

Innovation Class

Teaching Language

English

Prerequisites

Student Outcomes

 (Special Training Ability)

This course helps student to enhance their ability in the following aspect:

1. Design / Development Solutions: An ability to design solutions for computer engineering complex problems, to design computer hardware and software systems that meet with specific requirements, and to embody innovation awareness in the design process and take into account social, health, safety, cultural and environmental factors.

2. Research: An ability to develop computer system-related knowledge and research computer engineering complex issues, to develop the basic capacity of computer systems research & development, systematic cognitive and practice, master the Bottom-up and top-down problem analysis methods.

Course Objectives

1. The students are expected to enhance their programming skill by using suitable data types and algorithm.[1,2,3]

2. The course provides the essential programming background for computer science courses.[1,2]

Course Description

This course explores a number of fundamental data structures and algorithms in computer science, and learn to implement them in C++. The data structures include linked lists, stacks, queues, trees, heaps, hash tables, and graphs. In addition, this course also discusses the algorithms including searching, sorting, traversing trees and graph, hashing, and finding shortest paths in graphs.

Teaching Content and Class Hours Distribution

(1) Introduction and Algorithm Analysis(2 teaching hours)

• Motivation of learning data structure

• The basic knowledge of data structure.

• Evaluation on the performance of an algorithm in terms of time complexity, Big-O, Big-Omega, and Big-Theta.

(2) Lists, Stacks and Queues(5 teaching hours)

• The algorithm and implementation of array-based list and linked list. Also their pros and cons

• The algorithm and implementation of Stack and Queues

(3) Binary Tree(7 teaching hours)

• The algorithm of Binary Tree, Binary Search Tree, and Heap

• The detail implementation of the tree including the time complexity reduction

(4) Non-Binary Tree(5 teaching hours)

• The implementation methods of non-binary tree, and their pros and cons

• Traversal algorithm of non-binary tree

(5) Internal Sorting(6 teaching hours)

• The basic and simple sorting methods: Bubble, Insertion and Selection sort

• The implementation and algorithm of advances sorting methods are also introduced

(6) Searching(6 teaching hours)

• The sequential sort methods and the way to improve their performance

• Introduction on Heap and the methods of dealing with collision

(7) Indexing(6 teaching hours)

• Linear Indexing and Non-linear indexing

• Detail algorithm of Tree structure indexing is discussed including the 2-3 Tree, B-Tree and B+ Tree.

(8) Graph(7 teaching hours)

• Traversal of graph

• Transformation from graph to tree

• Implementation of classic algorithms in Graph, including spanning tree and shortest path algorithm

(9) Advanced Tree Structures(4 teaching hours)

• AVL tree

• Interval heap

Experimental Teaching

(1) List, Stack and Queues(4 teaching hours)

• Implementation on List

• Solve problems using List, Stack and Queue

(2) Binary Tree and Non-Binary Tree(4 teaching hours)

• Implement non-binary tree with pointers

• Solve problems using Binary Tree and Non-Binary Tree

(3) Sorting and Searching(4 teaching hours)

• Implement sorting and search method

• Solve problems using sorting and search methods

(4) Indexing and Graph(4 teaching hours)

• Implement B-tree

• Traversal the graph

• Solve problem using graph

Teaching Method

Lecture, tutorial, Lab, discussion, mid-term tests, Examination

Examination Method

Participation:10%

Lab Assignment:15%

Mid-Term Test:25%

Final Exam (Close Book):50%

Teaching Materials and Reference Books

Clifford A. Shaffer, “A Practical Introduction to Data Structures and Algorithm Analysis (3rd edition)”, Publishing House of Electronics Industry (Chinese Publisher), 2013

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

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

Prepared by Whom and When

Patrick P.K. Chan, 2019/4/14

课程代码

045100162

课程名称

数据结构

英文名称

Data Structure

课程类别

专业基础课

课程性质

必修

学时

总学时：64实验学时：16

学分

3.5

开课学期

第三学期

开课单位

计算机科学与工程学院

适用专业

计算机科学与技术创新班、联合班

授课语言

英文授课

先修课程

无

课程对毕业要求的支撑

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

1. 设计/开发解决方案：能够设计针对计算机工程复杂问题的解决方案，设计满足特定需求的计算机软硬件系统，并能够在设计环节中体现创新意识，考虑社会、健康、安全、法律、文化以及环境等因素。

2. 研究：培养学生具备计算机系统相关知识并对计算机工程复杂问题进行研究，具有计算机系统研发基本能力、具备问题分析和建模的能力，具有系统级的认知能力和实践能力，掌握自底向上和自顶向下的问题分析方法。

课程目标

该课程的目标是：

 1.加强学生对数据结构的了解[1、2]

2.提高应用数据结构解决实际问题的技巧[3]

课程简介

本课程探讨了计算机科学中的一些基础数据结构和算法，并学习用C ++实现它们。 数据结构包括链表，堆栈，队列，树，堆，哈希表和图。此外，本课程还讨论了包括搜索，排序，遍历树和图，散列以及最短路径的算法。

主要仪器设备与软件

具有C ++环境和ACM客户端的计算机

ACM平台

实验报告

无

考核方式

参与率: 20%

正确率: 80%

教材及参考书

(3rd edition)”, Publishing House of Electronics Industry (Chinese Publisher), 2013

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

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

制定人及制定时间

陈百基，2019年4月14日

实验项目编号

实验项目名称

实验学时

实验内容提要

实验类型

实验要求

每组人数

主要仪器设备与软件

1

链表，堆栈

4

实验包括2个基本问题与1个有难度的问题。学生需要利用基础的编程知识与链表，堆栈概念完成实验。

验证性

选做

1

台式电脑

C++编程环境

ACM平台

2

二叉树与树

4

实验包括完成2个基本问题与1个有难度的问题。学生需要利用基础的编程知识与树结构的相关知识完成实验。

验证性

选做

1

台式电脑

C++编程环境

ACM平台

3

排序与查找

4

实验包括完成2个基本问题与1个有难度的问题。学生需要利用基础的编程知识与链表，堆栈，树，排序与查找算法的相关知识完成实验。

验证性

选做

1

台式电脑

C++编程环境

ACM平台

4

寻址与图

4

实验包括完成2个基本问题与1个有难度的问题。学生需要利用基础的编程知识与链表，堆栈，树，寻址与图结构算法的相关知识完成实验。

验证性

选做

1

台式电脑

C++编程环境

ACM平台

Course Code

045100162

Course Title

Data Structure

Course Category

Disciplinary Basic Course

Course Nature

Compulsory Course

Class Hours

Total Teaching Hours: 64 Lab Hours: 16 (include Computer Usage Hours:16)

Credits

3.5

Semester

Third Semester

Institute

School of Computer Science and Engineering

Program Oriented

Innovation Class

Teaching Language

English

Prerequisites

/

Student Outcomes (Special Training Ability)

This course helps student to enhance their ability in the following aspect:

1. Design / Development Solutions: An ability to design solutions for computer engineering complex problems, to design computer hardware and software systems that meet with specific requirements, and to embody innovation awareness in the design process and take into account social, health, safety, cultural and environmental factors.

2. Research: An ability to develop computer system-related knowledge and research computer engineering complex issues, to develop the basic capacity of computer systems research & development, systematic cognitive and practice, master the Bottom-up and top-down problem analysis methods.

Course Objectives

The objectives of the course are:

1. Strengthen students’ knowledge of data structure

2. Enhance the skill of applying data structure to solve real problems

Course Description

This course explores a number of fundamental data structures and algorithms in computer science, and learn to implement them in C++. The data structures include linked lists, stacks, queues, trees, heaps, hash tables, and graphs. In addition, this course also discusses the algorithms including searching, sorting, traversing trees and graph, hashing, and finding shortest paths in graphs.

Instruments and Equipments

Computer with C++ environment and ACM client

Server with ACM server

Experiment Report

Not required

Assessment

Participation: 20%

Correctness: 80%

Teaching Materials and Reference Books

 Clifford A. Shaffer, “A Practical Introduction to Data Structures and Algorithm Analysis (3rd edition)”, Publishing House of Electronics Industry (Chinese Publisher), 2023

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

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

Prepared by Whom and  When

Patrick P.K. Chan, 2019/4/14

No.

Experiment Item

Class Hours

Content Summary

Category

Requirements

Number of Students Each Group

Instruments, Equipments and Software

1

List, Stack and Queue

4

3 Questions: 2 basic and 1 difficult questions

The questions are required to use the technique of Link, Stack and Queue Data Structures

Demonstration

Elective

1

Desktop Computer for each student

- C++ environment

- AMC Platform client software

ACM Platform Server

2

Binary Tree and Non-Binary Tree

4

3 Questions: 2 basic and 1 difficult questions

The questions are required to use the technique of Binary Tree and Non-Binary Tree Data Structures

Demonstration

Elective

1

Desktop Computer for each student

- C++ environment

- AMC Platform client software

ACM Platform Server

3

Sorting and Searching

4

3 Questions: 2 basic and 1 difficult questions

The questions are required to use the technique of Link, Stack, Queue, Tree and also the Sorting and Searching algorithms

Demonstration

Elective

1

Desktop Computer for each student

- C++ environment

- AMC Platform client software

ACM Platform Server

4

Indexing and Graph

4

3 Questions: 2 basic and 1 difficult questions

The questions are required to use the technique of Link, Stack, Queue, Tree, Graph and also the indexing algorithms

Demonstration

Elective

1

Desktop Computer for each student

- C++ environment

- AMC Platform client software

ACM Platform Server