317数据结构考试大纲_第1页
317数据结构考试大纲_第2页
317数据结构考试大纲_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

《数据结构》考试大纲一、考试内容概述(一)基本理论知识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．了解树的存储结构，理解树和森林转换为二叉树的方法。6．掌握树的路径长度和树的带权路径长度的计算方法，Huffman树的构造方法和Huffman编码。第七章图1．了解图的定义。2.了解图的基本术语：图及无向图、有向图、网、子图、连通图、强连通图、顶点的度、入度、出度、顶点问路径、路径长度、环。3．理解图的两种存储结构：邻接矩阵和邻接表(含逆邻接表)。4．掌握遍历图的两种方法：深度优先搜索和广度优先搜索遍历图的算法及其时间复杂度。5．理解生成树、最小生成树的概念，掌握最小生成树的构造过程(Prim算法和Kmskal算法)及其时间复杂度。6．掌握拓扑排序的方法及最短路径的计算。7．掌握求最短路径问题的Dijkstra算法，了解Floyd算法。第八章查找1．了解查找、关键字、平均查找长度等概念。2．静态查找表：掌握顺序查找(设哨兵)、折半查找算法及其效率(最坏和平均查找长度)分析，了解分块查找算法及其效率分析。3．动态查找表：掌握二叉排序树的定义、构造过程及其查找算法和效率分析，掌握平衡二叉树的定义和其构造过程。4．了解哈希表的特点，掌握构造哈希函数的方法(除留余数法等)，掌握处理冲突的方法及效率分析。第九章内部排序1．了解排序的目的、分类和排序方法的稳定性的定义。2．插人排序：掌握直接插入、折半插入排序算法和希尔排序的思想。3．快速排序：掌握起泡排序的算法和快速排序的思想。

人人文库> 全部分类> 应用文书 > 研究报告

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论