2022年云南专升本考试大纲数据结构考试大纲.docx

数据结构考试大纲一、考试内容概述（一）基本理论知识1. 数据结构的基本概念和基本术语，算法的描述，算法的时间复杂度和空间复杂 度分析。2. 线性表的定义，在线性表上常进行的基本操作，这些操作在顺序和链式存储结 构下的实现及复杂度分析。3. 栈和队列的定义、特点、表示方法和实现。4. 串的定义及其基本操作。5. 数组的定义、运算和存储、稀疏矩阵的压缩存储、广义表的定义和基本操作。6. 树的定义、基本术语和存储结构，二又树的定义和性质、二又树的存储结构及 其各种操作，Huffman和Huffman编码。7. 图的定义和常用术语、图的存储结构及其遍历操作，求最小生成树、最短路径 的算法，拓扑排序。8. 各种查找方法的算法、适用范围及时间复杂度的分析。9. 各种内排序算法的基本思想和算法的时间复杂度分析，不同排序方法的比较。（二）基本技能1. 能阅读用类C语言编写的算法。2. 能分析算法所实现的功能、运行结果和时间、空间复杂度。3. 能根据要求用类C语言编写一些经典、常用算法。二、考试形式考试采用闭卷、笔答的考试方式。满分：150分（单科成绩）。考试时间：120分钟。三、试题难易程度分布较易试题约占50%中等试题约占30%较难试题约占20%四、题型及题型分值分布单选题 约占20%多选题 约占10%填空题 约占15%算法阅读题约占10%综合题 约占30%程序设计题约占15%五、内容比例第一章绪论 约占5%第二章线性表约占10%第三章栈和队列约占15%第四章串 约占5%第五章数组和广义表 约占5%第六章树和二叉树 约占15%了解二叉树线索化的实质及线索化的过程。4. 了解树的存储结构，理解树和森林转换为二叉树的方法。5. 掌握树的路径长度和树的带权路径长度的计算方法，Huffman树的构造方法和 Huffman 编码。第七章图1. 了解图的定义。2. 了解图的基本术语：图及无向图、有向图、网、子图、连通图、强连通图、顶点 的度、入度、出度、顶点问路径、路径长度、环。3. 理解图的两种存储结构：邻接矩阵和邻接表（含逆邻接表）。4. 掌握遍历图的两种方法：深度优先搜索和广度优先搜索遍历图的算法及其时间 复杂度。5. 理解生成树、最小生成树的概念，掌握最小生成树的构造过程（Prim算法和 Kmskal算法）及其时间复杂度。6. 掌握拓扑排序的方法及最短路径的计算。7. 掌握求最短路径问题的Dijkstra算法，了解Floyd算法。第八章查找1. 了解查找、关键字、平均查找长度等概念。2. 静态查找表：掌握顺序查找（设哨兵）、折半查找算法及其效率（最坏和平均查找 长度）分析，了解分块查找算法及其效率分析。3. 动态查找表：掌握二叉排序树的定义、构造过程及其查找算法和效率分析，掌 握平衡二又树的定义和其构造过程。4. 了解哈希表的特点，掌握构造哈希函数的方法（除留余数法等），掌握处理冲突 的方法及效率分析。第九章内部排序1. 了解排序的目的、分类和排序方法的稳定性的定义。2. 插人排序：掌握直接插入、折半插入排序算法和希尔排序的思想。3. 快速排序：掌握起泡排序的算法和快速排序的思想。4. 选择排序：掌握简单的选择排序的算法和堆的定义、堆排序的思想。5. 理解归并排序的思想、基数排序的思想及特点。6. 了解各种内部排序方法的比较。