严蔚敏《数据结构》冲刺串讲与模拟四套卷.pdfVIP

严蔚敏《数据结构》冲刺串讲与模拟四套卷 第 １讲　线性结构 本讲主要内容要求 ·数据结构基本概念 ·线性表的链式和顺序存储 ·限定性线性表—栈和队列 ·串 ·数组与广义表 一、数据结构基本概念 考点 重点与难点 考试中常见题型 复习思路与方法 （１）数据结构概念； 本章中的几个基本概念； （２）抽象数据类型定义； 填空题、简答 数据、数据对象、数据结构、数据类 １．熟记基本概念； （３）逻辑结构； 题、问答题、计 型；算法及算法描述；算法的时间 ２．熟练分析算法时间复杂度； （４）存储结构； 算题 复杂度和空间复杂度分析 （５）算法的定义和评价； １．数据结构的基本概念 ·数据（Ｄａｔａ） ·数据元素（ＤａｔａＥｌｅｍｅｎｔ） ·数据对象（ＤａｔａＯｂｊｅｃｔ） ·数据结构（ＤａｔａＳｔｒｕｃｔｕｒｅ） ·数据类型（ＤａｔａＴｙｐｅ） ·数据抽象与抽象数据类型 ２．算法 （Ａｌｇｏｒｉｔｈｍ） 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个 操作。 （１）算法的特性： ·有穷性 ·确定性 ·可行性 — １— 考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课程　电话：４００６８８５３６５ ·输入 ·输出 （２）算法设计的要求 ·正确性 ·可读性 ·健壮性 ·通用性 ·效率与存储量需求 （３）“正确”分４个层次： ·程序不含语法错误 ·程序对于几组输入数据能够得出满足规格说明要求的结果； ·程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的 结果； ·程序对于一切合法的输入数据都能产生满足规格说明要求的结果。 通常以第３层意义的正确性作为衡量一个程序是否合格的标准。 （４）算法分析应用举例 一般地，常用最深层循环内的语句中的原操作的执行频度（重复执行的次数）来表示。 表示时间复杂度的阶有： Ｏ（１）：常量时间阶　　　　　 Ｏ（ｎ）：线性时间阶 Ｏ（ｌｏｇｎ）：对数时间阶　　　　 Ｏ（ｎｌｏｇｎ）：线性对数时间阶 ｋ Ｏ（ｎ）：ｋ ２，ｋ次方时间阶 ≥ 二、线性表的链式和顺序存储 考点 重点与难点 考试中常见题型 复习思路与方法 １．掌握线性表特点及抽象数据 本章中的线性表的特点； 顺序表和单链表上实现 选择 题、填 空 类型定义； 顺序定义及实现、线性链表、循环 的各种基本操作及相关 题、算法设计题 ２．熟练掌握顺序表和链表操 链表、双向链表 的时间性能分析 作； 顺序存储结构中，很容易实现线性表的一些操作：初始化、赋值、查找、修改、