数据结构》实验教学大纲

课程代码

045100162

课程名称

数据结构

英文名称

DataStructure

课程类别

专业基础课

课程性质

必修

学时

总学时: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 DataStructures and Algorithm Analysis (2nd edition)”, PublishingHouse of Electronics Industry (Chinese Publisher), 2009

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

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

制定人及发布时间

吕建明2019415


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

实验项目编号

实验项目名称

实验学时

实验内容提要

实验类型

实验要求

每组人数

主要仪器设备与软件

1

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

4

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

设计性

必做

1

台式电脑

C++编程环境

ACMOJ平台

2

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

4

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


设计性

必做

1

台式电脑

C++编程环境

ACMOJ平台

3

排序与查找算法

4

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


设计性

必做

1

台式电脑

C++编程环境

ACMOJ平台

4

图的表示及算法

4

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

设计性

必做

1

台式电脑

C++编程环境

ACMOJ平台




DataStructuresSyllabus

CourseCode

045100162

CourseTitle

DataStructures

CourseCategory

DisciplinaryBasic Course

CourseNature

CompulsoryCourse

ClassHours

Total64     Lab16  Other (MOOC):  8

Credits

3.5

Semester

3rdsemester

Institute

Schoolof Computer Science and Engineering

ProgramOriented

ComputerScience and Technology, Network Engineering, Information Security

TeachingLanguage

Chinese-EnglishBilingual Teaching

Prerequisites

C++Programming

StudentOutcomes (Special Training Ability)

№2.ProblemAnalysis: An ability to identify, formulate and analyze complexengineering problems, reaching to substantiated conclusions usingbasic principles of mathematics, science, and engineering.

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


TeachingObjectives

Afterthe course, the students will enhance their ability in thefollowing aspects:

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

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

3.Students can design the data structures and algorithms to addressthe specific demands from complex computer engineering problemscreatively, and have the ability of problem analysis, modeling andimplementation of complex computer systems.

CourseDescription

DataStructure is a very important disciplinary basic course ofcomputer science. The main topics of this course include logicalstructures, storage structures, algorithm design and algorithmevaluation.  The course may help students to understand the basicdata structures including list, stack, queue, tree and graph, andsome basic algorithms such as searching and sorting. Moreover, thestudents are trained to grasp the algorithm design techniquesrelated to different data structures in specific engineeringproblems. In a word, Data Structureis a coursecovering a lot of theoretical and practical topics simultaneously.

Instrumentsand Equipments

DesktopComputer for each student

C++environment

AMCOJ Platform

ExperimentReport

Experimentreport is not necessary.  The online judgment is available.

Assessment

Participationand MOOC exercises: 10%

Labassignment: 20%

Finaloperating examination: 10%

Finalexam: 60%

TeachingMaterials and Reference Books

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

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

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

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

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

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

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

[8]William F.WilliamT.DataStructures with C++PrenticeHallInc.1996

Preparedby Whom and When

JianmingLv 15/4/2019

DataStructures”ExperimentalTeaching Arrangements

No.

ExperimentItem

ClassHours

ContentSummary

Category

Requirements

Numberof StudentsEach Group

Instruments,Equipments and Software

1

List, stack, queue

4

learn the logical structuresof linear lists, and learn the implementation methods of stacksand queues

Design

Compulsory

1

DesktopComputer for each student

C++environment

AMC OJPlatform

2

Algorithms of binary trees andgeneral trees

4

Learn the use cases of variedstorage structures of binary trees, and learn how to implement therecursive algorithms based on binary trees.


Design

Compulsory

1

DesktopComputer for each student

C++environment

AMC OJPlatform

3

Sortingand searching

4

Learnto implement the frequently-used sorting algorithms, and learn thesearch algorithms of hash tables


Design

Compulsory

1

DesktopComputer for each student

C++environment

AMCOJ Platform

4

Graph

4

Learnthe varied storage structures and construction algorithms ofgraphs, and learn some algorithms to solve classic graph problems

Design

Compulsory

1

DesktopComputer for each student

C++environment

AMCOJ Platform