数据结构与算法“高级数据结构”教学设计 北京大学信息科学技术学院张铭 1.高级数据结构在课程中的定位和前测知识点 为满足一些特定需要,人们可以对简单数据结构进行扩展,实现一些功能更为强大、具有 更多操作的高级数据结构。本章可以作为《数据结构与算法》课程的提高内容,根据学生的 接受程度选择讲授的深浅。 高级数据结构一章主要介绍了几种常用的高级线性结构和高级树结构。多维数组是向量 的扩充。广义表在文本处理、人工智能和计算机图形学等领域都得到了广泛的应用。Trie和 Patricia树结构被广泛地运用于字符串存储,存储和检索字符串都有很高的效率。改进二叉 搜索树与普通二叉树相比能够提高检索效率,在现实中有广泛的应用。 希望学生能够掌握多维数组和广义表的使用,了解常用存储管理技术,理解Trie结构 和 Patricia树结构、掌握改进的二叉搜索树的原理和使用 前测知识点要求如下,可以根据需要给学生补充 (1)广义表的操作 (2)伙伴系统地址的计算: (3)动态规划算法; (4) Huffman树的原理 2.学习目标 (1)掌握高级线性结构的概念 (2)掌握多维数组的概念、存储表示、基本运算 (3)掌握广义表的概念、存储表示、基本运算; (4)掌握存储管理技术; (5)理解Trie树结构和 Patricia树结构原理及其应用; (6)理解二叉搜索树的几个变体,掌握平衡的二叉搜索树的几种变换; 3.知识点和学时分配 理论授课4学时。 以下内容是本课程要求的基本教学内容,在授课中必须完全涵盖,主讲教师可以根据学 生的状况、教师的科研背景等在某些方面进行扩展和对学生进行引导,以扩大适当学生的涉 猎面。对于非计算机类的学生,可以不讲高级树结构 各知识点建议授课时间如下 多维数组 0.5小时 广义表 1小时 存储管理技术 0.5小时 Trie结构和 Patricia树1小时 改进的二叉搜索树 4.重点和难点数据结构与算法“高级数据结构”教学设计 北京大学信息科学技术学院 张铭 1. 高级数据结构在课程中的定位和前测知识点 为满足一些特定需要,人们可以对简单数据结构进行扩展,实现一些功能更为强大、具有 更多操作的高级数据结构。本章可以作为《数据结构与算法》课程的提高内容，根据学生的 接受程度选择讲授的深浅。 高级数据结构一章主要介绍了几种常用的高级线性结构和高级树结构。多维数组是向量 的扩充。广义表在文本处理、人工智能和计算机图形学等领域都得到了广泛的应用。Trie 和 Patricia 树结构被广泛地运用于字符串存储，存储和检索字符串都有很高的效率。改进二叉 搜索树与普通二叉树相比能够提高检索效率，在现实中有广泛的应用。 希望学生能够掌握多维数组和广义表的使用，了解常用存储管理技术，理解 Trie 结构 和 Patricia 树结构、掌握改进的二叉搜索树的原理和使用。 前测知识点要求如下，可以根据需要给学生补充 （1）广义表的操作； （2）伙伴系统地址的计算； （3）动态规划算法； （4）Huffman 树的原理； 2．学习目标 （1）掌握高级线性结构的概念； （2）掌握多维数组的概念、存储表示、基本运算； （3）掌握广义表的概念、存储表示、基本运算； （4）掌握存储管理技术； （5）理解 Trie 树结构和 Patricia 树结构原理及其应用； （6）理解二叉搜索树的几个变体，掌握平衡的二叉搜索树的几种变换； 3. 知识点和学时分配 理论授课４学时。 以下内容是本课程要求的基本教学内容，在授课中必须完全涵盖，主讲教师可以根据学 生的状况、教师的科研背景等在某些方面进行扩展和对学生进行引导，以扩大适当学生的涉 猎面。对于非计算机类的学生，可以不讲高级树结构。 各知识点建议授课时间如下： 多维数组 0.5 小时 广义表 1 小时 存储管理技术 0.5 小时 Trie 结构和 Patricia 树 1 小时 改进的二叉搜索树 1 小时 4．重点和难点