研究生数据结构大纲

发表于   |   分类于   |     |  

College of Software Engineering
Undergraduate Course Syllabus
Course ID 311036030 Course Name Data Structures & Algorithm
Course
Attribute
□Compulsory □Selective Course Language □English █Chinese
Credit Hour 3 Period 48
Semester □First Fall □First Spring █Second Fall □Second Spring
□Third Fall □Third Spring □Fourth Fall □Fourth Spring
Instructors Li xiaohua，Zuo hang，Sun Jieping, Zhu Hong
Description
This course thoroughly covers key data structures at the undergraduate
level. With a focus on how to assess costs and benefits, it teaches students
how to create efficient data structures and algorithms and how to adopt
to new design challenges. Students are taught how to assess applications
needs to find data structures with matching capabilities.

Prerequisites C Language Programming
Discrete Mathematics

Textbook A Practical Introduction to Data Structures and Algorithm Analysis，Clifford A.
Shaffer，Prentice Hall 2001. Second Edition
Resource
①A.V.Aho,J.E.Hopcroft and J.D.Ullman,Data Structures and Algorithms,by Addison——Wesley
Publishing Company,Inc.,1983
② Cliford A. Shaffer，A Practical Introduction to Data Structures and Algorithm Analysis——
C++)，Publishing house of electronics industry.
Grading assignments, class participation (40%), final exam (60%)
Topics

  1. Data Structures and Algorithms. 1h
    A Philosophy of Data Structures. Abstract Data Types and Data Structures. Problems, Algorithms,
    and Programs.
  2. Mathematical Preliminaries. 2h
    2
    ets and Relations. Miscellaneous Notation. Logarithms. Recursion. Summations and Recurrences.
    Mathematical Proof Techniques. Estimating.
  3. Algorithm Analysis. 2h
    Introduction. Best, Worst, and Average Cases. A Faster Computer, or a Faster Algorithm?
    Asymptotic Analysis. Calculating the Running Time of a Program. Analyzing Problems. Common
    Misunderstandings. Multiple Parameters. Space Bounds. Some Practical Considerations.
  4. Lists, Stacks, and Queues. 10h
    Lists. The Dictionary ADT. Stacks. Queues.
  5. Binary Trees. 6h
    Definitions and Properties. Binary Tree Traversals. Binary Tree Node Implementations. Binary
    Search Trees. Heaps and Priority Queues. Huffman Coding Trees.
  6. Non-Binary Trees. 4h
    General Tree Definitions and Terminology. The Parent Pointer Implementation. General Tree
    Implementations. K -ary Trees. Sequential Tree Implementations.
  7. Internal Sorting. 5h
    Sorting Terminology and Notation. Three …Q(n2
    ) Sorting Algorithms. Shell sort. Quick sort.
    Merge sort. Heap sort. Bin sort and Radix Sort. An Empirical Comparison of Sorting Algorithms.
    Lower Bounds for Sorting.
  8. File Processing and External Sorting. 2h
    Primary versus Secondary Storage. Disk Drives. Buffers and Buffer Pools. The Programmer’s
    View of Files. External Sorting. Simple Approaches to External Sorting. Replacement Selection.
    Multi-way Merging.
  9. Searching. 3h
    Searching Sorted Arrays. Self-Organizing Lists. Searching in Sets. Hashing.
  10. Indexing. 3h
    Linear Indexing. ISAM. Tree Indexing. 2-3 Trees. B-Trees.
  11. Graphs. 9h
    Terminology and Representations. Graph Implementations. Graph Traversals. Shortest-Paths
    Problems. Minimum-Cost Spanning Trees.
    3
    Total:
    Lecture: 47 QA: 1
    Tools &
    Environment
    This course will require to use VC++ 6.0 software for programming
    Projects
    Project: City database Management System
    Requirements:
    1） Using BST or linked lis t to store the records；
    2） Each node should contain the name of city and the coordination of city(denoted using x,y)；
    3） Organize the node in database according to the name of city
    4） Insert single or multiple nodes, delete or index node in accordance with name or coordination.
    5） Print all records which have certain distance with a given city
    6） Statistic the runtime of each operation
    7) encourage adding in innovate functions
    Development environment:
    VC++ 6.0

Version No： 1.0
Author： Xiaohua Li Date： 2008-7 -15
Auditor： Mei Hong Date： 2008-7-25
Signature of leader：
Date： 2008-7-30

中文翻译：

软件工程学院
本科课程大纲
课程编号311036030课程名称数据结构与算法
课程
属性
□强制□选修课程语言□英语█中文
信用时间3期48
学期□第一次秋季□第一次春季█第二次秋季□二春
□ 三季□第三弹□第四秋季□第四弹簧
导师李晓华，佐恒，孙吴阶平，朱虹
介绍
本课程涵盖彻底在本科关键数据结构
水平。重点关注如何评估成本和收益，它教会学生
如何创建高效的数据结构和算法，以及如何
应对新的设计挑战。

前提条件C语言编程
离散数学

教科书数据结构和算法分析的实践介绍，Clifford A.Shaffer
，Prentice Hall 2001.第二版
资源
①A.V.Aho，JEHopcroft和JDUllman，数据结构和算法，Addison - Wesley
Publishing Company，Inc.，1983
②Cliford A. Shaffer，数据结构与算法分析实践介绍 -
C ++）电子工业出版社。
分级任务，班级参与（40％），期末考试（60％）
专题

  1. 数据结构和算法。1h
    数据结构的哲学。抽象数据类型和数据结构。问题，算法
    和程序。
  2. 数学初步 2h
    2
    ets和关系。杂项符号 对数。递归。总结和反复。
    数学证明技术。估计。
  3. 算法分析。2h
    简介 最佳，最差和平均的案例。更快的计算机，还是更快的算法？
    渐近分析。计算程序的运行时间。分析问题 常见的
    误解。多个参数。空间界限 一些实际注意事项
  4. 列表，堆栈和队列。10h
    列表。词典ADT。堆栈。队列。
  5. 二叉树。6h
    定义和属性。二叉树遍历。二叉树节点实现。二进制
    搜索树。堆和优先队列。霍夫曼编码树。
  6. 非二叉树。4h
    通用树定义和术语。父指针实现。一般树的
    实现。Kary树。顺序树实现。
  7. 内部排序 5h
    排序术语和符号。三… Q（n2
    ）排序算法。外壳排序。快速排序
    合并排序 堆排序 Bin排序和基数排序。排序算法的实证比较。
    下限排序。
  8. 文件处理和外部排序。2h
    主要与次要存储。磁盘驱动器 缓冲池和缓冲池。程序员的
    文件视图。外部排序。外部排序的简单方法。更换选择
    多路合并
  9. 搜索。3h
    搜索排序数组。自组织名单 搜索集合。散列。
  10. 索引。3h
    线性索引。ISAM。树索引。2-3棵树。B-树。
  11. 图表。9h
    术语和表示。图表实现。图形遍历。最短路径
    问题。最小成本生成树。
    3
    总计：
    讲座：47 QA：1
    工具与
    环境
    本课程将需要使用VC ++ 6.0软件编程
    项目
    项目：城市数据库管理系统
    要求：
    1）使用BST或链接存储记录;
    2）每个节点应包含城市的名称和城市的协调（用x，y表示）;
    3）根据城市的名称组织数据库中的节点
    4）根据名称或协调插入单个或多个节点，删除或索引节点。

版本号：1.0
作者：李晓华
日期：2008-7-15
审计人
：梅红日期：2008-7-25 领导签名：日期：2008-7-30

打赏鼓励一下。