18自考数据结构串讲资料

更多优质自考资料尽在百度贴吧自考乐园俱乐部（迎...欢迎...止不住的惊喜等着你.........自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园....俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部）欢❤加入❤交流自考《数据结构》串讲资料目录第一部分课程简介.....................................3第二部分各章串讲.....................................4第一章绪论......................................4第一节数据结构的基本概念和术语（识记）........4第二节学习数据结构的意义（识记）..............6第三节算法和算法分析（领会）..................6第二章线性表...................................7第一节线性表的逻辑结构（识记）................8第二节线性表的顺序存储结构（综合应用）........8第三节线性表的链式存储结构（综合应用）........9第三章栈与队列..................................10第一节栈（综合应用）.........................11第二节队列（综合应用）.......................13第三节栈与队列的应用实例（领会）.............17第四章串........................................18第一节基本概念与基本运算（领会）.............19第二节串的存储结构（简单应用）...............19第三节串的模式匹配算法.......................21第五章数组和广义表..............................21第一节多维数组（领会）.......................22第二节矩阵的压缩存储（领会）.................24第三节广义表的概念（领会）...................26第六章树........................................29第一节树的概念（领会）.......................29第二节二叉树（简单应用）.....................30第三节二叉树的遍历（综合应用）...............33第四节线索二叉树（领会）.....................35第五节树和森林（领会）.......................37第五节哈夫曼树及其应用（简单应用）...........41第七章图........................................44第一节图的概念（领会）.......................44第二节图的存储结构（简单应用）...............46第三节图的遍历（简单应用）...................48第四节生成树和昀小生成树（领会）.............49第五节昀短路径（领会）.......................50第六节拓扑排序（领会）.......................53第八章内部排序................................56第一节基本概念（识记）.......................57第二节插入排序（综合应用）...................58更多优质自考资料尽在百度贴吧自考乐园俱乐部（迎...欢迎...止不住的惊喜等着你.........自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园....俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部）欢❤加入❤交流第三节交换排序（综合应用）...................62第四节选择排序（综合应用）...................65第五节归并排序（领会）.......................70第六节分配排序（领会）.......................72第七节各种内部排序方法的比较和选择...........75第九章查找....................................75第一节基本概念（识记）.......................76第二节线性表的查找（简单应用）...............76第三节树的查找（简单应用）...................79第四节散列技术（简单应用）...................89第十章文件....................................91第一节文件的基本概念（识记）.................92第二节顺序文件（识记）.......................92第三节索引文件（识记）.......................92更多优质自考资料尽在百度贴吧自考乐园俱乐部（迎...欢迎...止不住的惊喜等着你.........自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园....俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部）欢❤加入❤交流《数据结构》全国高等教育自学考试指导委员会组编，黄刘生主编，经济科学出版社2000版。第一部分课程简介一、课程性质、特点数据结构是高等教育自学考试计算机及应用专业（独立本科段）考试计划中一门专业基础课，在计算机软件的各个领域中均会使用到数据结构的有关知识。本课程的目的和任务是使应考者较全面地掌握各种常用的数据结构，为学习后续软件课程提供必要的基础，提高运用数据结构解决实际问题的能力。二、课程地位《数据结构》作为一门独立的课程昀早是在美国的一些大学开设的，1968年美国Donald.Knuth教授开创了数据结构的昀初体系，他所著的《计算机程序设计技巧》系统地阐述数据的逻辑结构和存储结构及其操作的著作，是《数据结构》的经典之作。20世纪60年代末出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们越来越重视数据结构，认为程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法，即程序=数据结构+算法。从70年代开始，《数据结构》得到了迅速发展，数据结构的研究不仅涉及到计算机硬件，而且和计算机软件的研究有着更密切的关系，无论是编译程序、操作系统、数据库还是信息检索，都涉及到数据元素的组织以及在存储器中的分配。数据结构技术成为设计和实现编译程序、操作系统、数据系统及其它系统程序和大型应用程序的关键技术。《数据结构》的学习越来越被人们所重视，成为构建计算机类专业群的重要课程。三、指定教材四、前导课程与后续课程本课程的先修课程为离散数学和高级语言程序设计，后续课程为操作系统、数据库原理等。数据结构中存储结构及基本运算的实现需要程序设计的基本知识和编程的经验及能力，本课程的大部分实例均是用C语言实现的，故要求较熟练地掌握C语言。五、学习目的与要求数据结构是介于数学、计算机硬件和计算机软件之间的一门计算机科学与技术专业的核心课程，是高级程序设计语言、编译原理、操作系统、数据库、人工智能等课程的基础。同时，数据结构技术也广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。数据结构的内容包括抽象、实现和评价三个层次，从数据表示和数据处理上看有五个基本组成“要素”分别是逻辑结构，存储结构、基本运算、算法及不同数据结构的比较与算法分析。通过学习，使学生初步具备分析问题、解决问题的能力，养成良好的程序设计风格，积聚和提高基本的分析设计能力，并培养团队写作能力。为后续课程的学习打下坚实的基础。基本要求：1．从数据结构的逻辑结构、存储结构和数据的运算三个方面去掌握线性表、栈、队列、串、数组、广义表、树、图和文件等常用的数据结构。2．掌握在各种常用的数据结构上实现的排序和查找运算。3．对算法的时间和空间复杂度性有一定的分析能力。更多优质自考资料尽在百度贴吧自考乐园俱乐部（迎...欢迎...止不住的惊喜等着你.........自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园....俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部）欢❤加入❤交流4．针对简单的应用问题，应能选择合适的数据结构及设计有效的算法解决之。六、试卷结构数据结构的每份试题中，对不同能力层次要求的分值比例大致为：“识记”占20%，“领会”占30%，“简单应用”占30%，“综合应用”占20%。试题难度分四档：易、较易、较难、难，比例大致为：2：3：3：2题型题量及分值第一题单项选择题本大题共15小题，每小题2分，共30分第二题填空题本大题共10小题，每小题2分，共20分第三题解答题本大题共4小题，每小题5分，共20分第四题算法阅读题本大题共4小题，每小题5分，共20分第五题算法设计题本大题共1小题，共10分第第二部分各章串讲一章绪论一、课程内容与要求本章相主要内容有数据结构的基本概念和术语，学习数据结构的意义及算法的描述和分析。介绍了数据结构中常用的基本概念和术语，以及学习数据结构的意义，要求了解本章介绍的各种基本概念和术语，掌握算法描述和分析的方法。二、本章重点难点本章重点是了解数据结构的逻辑结构、存储结构及数据结构的运算三方面的概念机相互关系，难点就是算法复杂度的分析方法。三、考情分析本章主要考查一些数据结构的基本术语的概念（09年1月选择题1题考查了数据项的概念）算法复杂度的分析（08年10月单选题2题，09年10月分单选题2题考查了算法复杂度的求法）四、串讲内容引论对于一个课题，在计算机领域，一般遵循下面的解决原则：需求分析总体设计模块分割建立数学模型解数学模型的算法程序编制调试结果数据结构涉及到：数学模型的建立和对该模型具体实现的对应的算法。数据结构的地位：数学、硬件、软件之间。核心专业基础课.第一节数据结构的基本概念和术语（识记）1.基本术语更多优质自考资料尽在百度贴吧自考乐园俱乐部（迎...欢迎...止不住的惊喜等着你.........自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园....俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部）欢❤加入❤交流数据：是信息的载体，能够被计算机识别存储和加工处理。（数字、字符、声音、图形、图像等等）数据元素：数据的基本单位。可以进一步细分为若干数据项，数据项是昀小单位，不能再细分。常常作为一个整体进行考虑和处理，如纪录/结构。数据项：数据的不可分割的昀小单位，如结构中的域。数据对象：性质相同的数据元素的集合，是数据的一个子集2.数据结构定义：是数据之间的相互关系，及数据的组织形式，相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括以下三方面内容：（1）数据元素之间的逻辑关系。也称为数据的逻辑结构（2）数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（3）数据的运算，即对数据施加的操作数据类型：所谓数据类型是一个值的集合及在这些值上定义的一组操作的总称。按“值”是否可以分解，可将数据类型划分为