《数据结构》-软件工程

一、 《数据结构》考试大纲 I．考试性质 普通高等学校本科插班生招生考试是由专科毕业生参加的选拔性考试。高等学校根据考生的成绩，按已确定的招生，德、智、体全面衡量，择优录取。因此，本科插班生考试应有较高的信度、效度、必要的区分度和适当的难度。 II．考试内容 1、 基本概念 理解数据的含意 理解逻辑结构、存储结构、算法及三者之间的关系 理解算法的五个特征 了解算法时间、空间需求的大O表示法 2、 向量、链表、栈、队 掌握向量及其插入、删除算法 掌握链表、静态链表（单链表、双向链表、循环链表）及相关算法 掌握栈及顺序栈、链栈的进栈、出栈等算法 掌握队及顺序队、链队的进队、出队等算法 了解栈和队的应用，理解递归 理解串及C语言中串的表示 掌握串的模式匹配算法 3、 树和二叉树 掌握树的概念及相关术语 掌握二叉树的概念、相关术语、性质及存储结构 掌握二叉树的遍历算法 掌握树（森林）与二叉树的对应关系 掌握树（森林）的存储结构及遍历方法 掌握赫夫曼（Huffman）树的构造及应用 4、 图 掌握图的概念、相关术语及存储结构 掌握图的遍历算法 掌握最小生成树、最短路径、拓扑排序、关键路径等算法 5、 查找 掌握顺序查找、二分查找算法 掌握二叉排序树的查找、插入及删除算法 理解平衡二叉排序树及插入时的平衡方法 掌握哈希（Hash）表的查找 了解查找成功及失败的平均查找长度 6、 内部排序 掌握排序的概念及相关术语 掌握直接插入排序算法 掌握希尔（Shell）排序算法 掌握快速排序算法 掌握堆排序算法 掌握归并排序算法 理解基数排序算法 了解二分插入、表插入、起泡、简单选择等排序算法 了解上述排序算法的时间复杂度、空间复杂度、稳定性 了解上述部分排序算法的适用场合