15085 王小凤主讲严蔚敏《数据结构》考研冲刺串讲与模拟四套卷.pdf考研数据结构很好的复习材料

文件名称: 15085 王小凤主讲严蔚敏《数据结构》考研冲刺串讲与模拟四套卷.pdf

所属分类: 讲义

开发工具:

文件大小: 3mb

下载次数: 0

上传时间: 2019-07-03

提供者: zjz0712********

下载 (3mb)

不能下载？报告错误

详细说明：考研数据结构很好的复习材料，考点清晰适合学习数据结构的同学们。考试点(www.kaoshidian.com)名师精品课程电话:400-6885-365 输入输出 (2)算法设计的要求 ·正确性 ·可读性健壮性通用性 ·效率与存储量需求 (3)“正确”分4个层次 ·程序不含语法错误 ·程序对于几组输入数据能够得出满足规格说明要求的结果; ·程序对于精心选择的典型、苛刻而带有刁难性的几组输亼欻据能够得岀满是规格说明要求的结果程序对于一切合法的输入数据都能产生满足规格说明要求的结果。通常以第3层意义的正确性作为衡量一个程序是否合格的标准。 (4)算法分析应用举例一般地,常用最深层循环内的语句中的原操作的执行频度(重复执行的次数)来表示。表示时间复杂度的阶有: O(1):常量时间阶 O(n):线性时间阶 O( logn):对数时间阶 O( nlogn):线性对数时间阶 0(n):k≥2,k次方时间阶二、线性表的链式和顺序存储考点重点与难点考试中常见题型复习思路与方法 1.掌握线性表特点及抽象数据本章中的线性表的特点顺序表和单链表上实现选择题、填空类型定义顺序定义及实现线性链表循环的各种基本操作及相关题、算法设计题2.熟练掌握顺序表和链表操链表、双向链表的时间性能分析作顺序存储结构中,很容易实现线性表的一些操作:初始化、赋值、査找、修改、插入、删除、求长度单线性链式的基本操作严蔚敏《数据结枸》冲剌串讲与模拟四套卷 1.建立单链表动态地建立单链表的常用方法有如下两种:头插入法,尾插入法。 (1)头插入法建表每次插入的结点都作为链表的第一个结点。生成的链表中结点的次序和输入的顺序相反。 (2)尾插入法建表尾插法是将新结点插入钊当前链表的表尾,使其成为当前链表的尾结点。牛成的次序和输入的次序相同。 2.双向链表双冋链表( Double linked list):指的是构成链表的每个结点中设立两个指针域:一个指向其直接前趋的指针域 prior,一个指向其直接后继的指针域next。这样形成的链表中有两个方向不同的链,故称为双向链表。三、限定性线性表一栈考点重点与难点考试中常见题犁复习思路与方法栈的基本操作 1.熟练掌握栈的工作原理 2.栈类的实现填空题栈的原理 3.栈的应用和算法选择题 2.掌握栈的顺序和链式存储结 4.递归的概念递归工作原理编程题构下的基本操作 5.栈与递归 3.掌握栈与递归的关系结点出栈:首先执行top减1,使top指向栈顶元素的存储位置,然后将栈顶元素取出。 bottom bottom bottom 空栈元素a进栈元素b,c进栈 bottom bottom 元素c退栈元素d,e,进栈 (动态)堆栈变化示基图 1.两栈共享技术(双端栈): 主要利用了栈“栈底位置不变,而栈顶位置动态变化”的特性。首先为两个栈申请一个共享的维数组空间SM],将两个栈的栈底分别放在一维数组的两端,分别是0),M-1。共享栈的空间示意为:p0]和top[1]分别为两个栈顶指示器。 Stack. 0 M-1 top[(1I 试点(ww.kaoshidian.com)名师精品课程电话:4006885365 2.栈的链式表示栈的链式存储结构称为链栈,是运算受限的单链表。其插入和删除操作只能在表头位置上进行。因此,链栈没有必要像单链表那样附加头结点,栈顶指针卹p就是链表的头指针。下图是栈的链式存储表示形式。 p→匚N 空栈链栈存储形式非空栈链栈的结点类型说明如下: typedef struct Stack_Node struct Stack Node *'s next I Stack_Node 四、限定性线性表一队列考点重点与难点考试中常见题型复与思路与方法 1.熟练掌握驮列的工作原理 1.队列的基本操作填空题 2.掌握队列的顺序和链式存储 2.队列的实现队列的原理选择题结构下的基本操作 3.队列的应用和算法编程题 3.掌握栈与递归的关系 Q rear Q rear Q rear rea Q fronm Q frond a)空队列(b)入队3个元素(c出队3个元素(d)入队2个元素图36队列示意图 1.循环队列为充分利用向量空间,克服上述“假溢出”现象的方法是:将为队列分配的向量空间看成为一个首尾相接的圆环,并称这种队列为循环队列( Circular Queue)。队列的链式存储表示队列的链式存储结构简称为链队列,它是限制仅在表头进行删除操作和表尾进行插入操作的单链表严蔚敏《数据结枸》冲刺串讲与模拟四套卷需要两类不同的结点:数据元素结点,队列的队首指针和队尾指针的结点。五、串考点重点与难点考试中常见题型复习思路与方法的概念、术语和基本操作和存储熟练掌握串的概念、术诘填空题、选择结构串的模式匹配算法熟练掌握串的操作题、编程题串的模式匹配算法掌握串的模式匹配思路串的模式匹配算法模式匹配(模范匹配):子串在主串中的定位称为模式匹配或串匹(字符串匹配)。模式匹配成功是指在主串S中能够找到模式串T,否则,称模式串T在主串S中不存在。六、数组与广义表考点重点与难点考试中常见题型复习思路与方法理解数组的定义数组的顺序存储数组的顺序存储和压缩结构及矩阵的存储压缩存储计算; 选择题、填空|1掌握数组元素存储方式和下标计算公式; 理解广义表的定义及存储结构题、算法设计题广义表长度和深度计算 2.熟练广义表操作; 以二维数组Am为例,假设每个元素只占一个存储单元,“以行为主”存放数组,下标从1开始,首元素an的地址为Lc-1,1]求任意元素an的地址,可由如下计算公式得到: Ioc[i,]=Loc[1,1]+n×(i-1)+(j-1) 如果每个元素占e个存储单元,则任意元素a的地址计算公式为 cLi,j」=Lwcl1,1」+(n×(i-1)+j-1)×size 特殊矩阵的压缩存储特殊矩阵压缩存储的压缩原则是:对有规律的元素和值相同的元素只分配一个存储单元,对于零元素不分[空间。三角矩阵(下三角矩阵、上三角矩阵和对称矩阵)和带状矩阵。 (1)稀疏矩阵的三元组表表示法 (2)稀疏矩阵的链式冇储结构:十字链表广义表( Lists,又称为列表):是由n(n全0)个元素组成的有穷序列:LS=(a1,a2,…,an)其中a 或者是原子项,或者是一个广义表。LS是广义表的名字,n为它的长度。若a1是广义表,则称为LS的子表。 (1)广义表的头尾链表存储结构 (2)广义表的同层节点链存储结构七、小结线性结构分为线性表、栈、队列、串、数组和广义表。 ·本讲主要对其类型定义和基本操作以及应用进行讲解。试点(ww.kaoshidian.com)名师精品课程电话:4006885365 第2讲非线性结构数据结构屮非线性结构主要分为树形和图形结构。本讲对这两部分內容进行复习总结。、树与二叉树考点重点与难点考试中常见题型复习思路与方法 1.树与二叉树的基本概念, 2.完全二又树与满二叉树的基本概念和性质 3.二又树与树、树林之间的转换 4.二叉树的顺序存储结构与二叉链表存储结构 5.二叉树的前序遍历、中序遍历叉链表基础上各种遍熟练掌握树、二叉树基本概念, 后序遍历和按层次遍历,以及在历算法(重点为非递归算填空题、选择叉链表基础上各种遍历算法(重点法)的设计与应用; 掌握二叉树基本定理,遍历方为非递归算法)的设计与应用二义树的线索化; 编程题、构造题式、哈大曼树的构造和WPL计哈夫曼树的构造和编码算以及哈夫曼编码 6.线索二叉树 7.哈大曼( Huffman)树的基概念,哈夫曼树的构造与带杈路径长度(WPL)的计算及其应用。 8.遍历二叉树 9.树和森林的关系及遍历 1.二又树的五种基本形态 (a)空二叉数只有根结(只有左子点的二叉树树的二叉树 (d左右子树均(e)只有右子树非空的二义树的二义树 2.二又树的性质性质1:在二叉树的第i层上至多有2-个结点(i≥1)。性质2:深度为k的二叉树至多有2-1个结点(k≥1)。性质3:对任意一棵二叉树T,若终端结点数为n,而其度数为2的结点数为n2,则n=n2+1 性质4:具有n个结点的完全二叉树的深度为llog2n」+1。性质5:对于具有n个结点的完全二叉树,如果按照从上到下和从左到右的顺序对二叉树中的所严蔚敏《数据结枃》冲刺串讲与模拟四套卷有结点从1开始顺序编号,则对于任意的序号为i的结点有: (1)若i=1,则i无双亲结点若i>1,则i的双亲结点为i/2 (2)若2米i>n,则i无左孩子若2*i≤n,则i结点的左孩子结点为2*i (3)若2*i+1>n,则i无右孩子若2i+1≤n,则i的右孩子结点为2*i+1 3.二叉树的存储结构叉树的结构是非线性的,每一结点最多可有两个后继。二叉树的冇储结构有两种:顺序冇储结构和链式冇储结构。对于如下图的二叉树,其先序、屮序、后序遍历的序列为先序遍历:A、B、D、F、G、C、E、H。中序遍历:B、F、D、G、A、C、E、H。后序遍历:F、G、D、B、HE、C、A。 C 4.先序遍历递归算法 voidPre Order( Bi'lree root *先序遍历二叉树,rot为指向二叉树(或某一子树)根结点的指针*/ if root!=NULL) Visit(rot->data);/*访问根结点*/ PreOrder(root-> LChild);/米先序遍历左子树*/ PreOrder(root-> RChild);/*先序遍历右子树* 线索二叉树结构:为了区分孩子结点和前驱后继结点,为结点结构增设两个标志域。 LChild Ltag Data rtag RChild 其中: 0 LChild域指示结点的左孩子 Ltag= l1 L Child域指示结点的遍历前驱 7 试点(ww.kaoshidian.com)名师精品课程电话:4006885365 0 RChild域指示结点的右孩子 g 1 RChild域指示结点的遍历后继 5.树的有储结构树的存储结构根据应用的不同而不同。 (1)双亲表示法(顺序存储结构) (2)孩子链表表示法 ·定长结点结构不定长结点结构复合链表结构 (3)孩子兄弟表示法(二叉树表示法) 以二义链表作为树的存储结构,其结点形式如卜图(a)所示两个指针域:分别指向结点的第一个子结点和下一个兄弟结点。结点类型定义如下 pedef struct CSnode em Iype data struct CSnode firstchild, nextsibing i ANOde 图所示树的孩子兄弟表示的存储结构如图 firstchild data nextsibing 孩子结点兄弟结点 (a)结点结构 ①0 (b)树 LAEALCA 囚 (c)孩子兄弟存储结构树及孩子兄弟存储结构 6.二叉树转换成树 (1)加虚线。 (2)去连线。严蔚敏《数据结枸》冲剌串讲与模拟四套卷 (3)规整化 R B (E)(C (C)还原后的树 a)加虚线后 (b)去连线后二叉树向树的转换过程 7.树和森林的遍历树的遍历由树结构的定义可知,树的遍历有二种方法。先根遍历后根遍历 A B E K C)(D)(F(G(H 图6-23树 Huffman编码方法以宇符集C作为叶子结点,次数或频度集W作为结点的权值来构造 Huffman树。规定 Huffman 树中左分支代表“0”,右分支代表“1”。从根结点到每个叶∫结点所经历的路径分支上的“0”或“1”所组成的字符串,为该结点所对应的编码,称之为 Huffman编码。每个字符都是叶子结点,不可能出现在根结点到其它字符结点的路径上,所以一个字符的Hu man编码不可能是另一个字符的 Huffman编码的前缀。二、图考点重点与难点考试中常见题型复习思路与方法 1.图的基本概念、名词术语; 2.图的各种存储方法和基本操作熟练掌握图的存储结构和概念 3.图的深度优先搜索与广度优先搜索; 最小生成树、拓扑排序填空题、选择熟练堂握图的最小生成树、拓 4最小(代价)生成树、最短路径、关键路径的求取题、编程题计扑排序和关键路径的原理和算算题法 AOV网与拓扑排序以及AOE网与熟练掌握图的遍历关键路径的基本概念与求解过程。

(系统自动生成,下载前可以参看下载内容)