![点击分享此内容可以赚币 分享](/master/images/share_but.png)
数据结构复习资料.doc
《数据结构复习资料.doc》由会员分享,可在线阅读,更多相关《数据结构复习资料.doc(26页珍藏版)》请在咨信网上搜索。
1、数据结构的定义 数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。数据结构:是指数据以及数据元素相互之间的联系,可以看作是相互之间存在着某种特定关系的数据元素的集合。 对数据结构的内容包括以下几个方面: 数据的逻辑结构,指数据元素之间的逻辑关系。 数据的存储结构,指数据元素及其关系在计算机存储器中的存储方式,也称为数据的物理结构。 数据运算,指施加在数据上的操作。 算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中,每一条指令表示一个或多个操作。 粗略地说,算法是为了求解问题而给出的一个指令序列,程序是算法的一种具体实现。 一个
2、算法必须满足以下五个重要特性:1. 有穷性 2. 确定性 3. 可行性 4. 有输入 5. 有输出算法的重要特征(1) 有穷性: 算法在有穷步之后结束,每一步在有穷时间内完成。(2) 确定性: 算法中的每一条指令有明确的含义,无二义性。 (3) 可行性: 可通过已经实现的基本运算执行有限次来实现算法中的所有操作。 算法分析的两个主要方面是分析算法的时间复杂度和空间复杂度。算法的执行时间主要与问题的规模有关。问题规模是一个与输入有关的量。语句频度是指算法中该语句被重复执行的次数。算法中所有语句的频度之和记作(n),是该算法所求解问题规模的函数。当问题规模趋向无穷大时,(n)的数量级称为渐进时间复
3、杂度,简称时间复杂度,记作(n)=O(f(n)。 通常采用算法中表示基本运算的语句的频度来分析算法的时间复杂度。 例题:1. 数据结构中的逻辑结构是指(),物理结构是指()。2. 算法的基本特征包括有穷性、( )、( )、有输入和输出 。3. 算法的有穷性是指()。4. 算法的确定性是指()。5. 算法的可行性是指()。6. 算法分析的两个主要方面是分析算法的()和空间复杂度。7. 语句频度是指( 算法中该语句被重复执行的次数 )。 8. 设n为正整数,对下面的程序段,写出语句、的频度及该程序段的时间复杂度。 for (i=1; i =n; i+) s=0; n for (j=1; j nex
4、t; if (p) s = p-next;p-next = NULL; p = s;s = s -next;p-next = head - next;head - next = p;p = s;s = s -next;p-next = head - next;head - next = p;F 将原链表看成由两部分组成:已经完成逆置的部分和未完成逆置的部分。F 设置两个指针p和s,p指向已完成逆置部分链表的第一个结点,s指向未逆置部分的第一个结点。F 初始时令指针p指向第一个元素结点,s指向p所指结点的后继。将第一个元素结点的指针域置为空。F 将未逆置部分的结点逐个插入到头结点之后。算法:vo
5、id reverse(LinkList head) /带头结点的单链表逆置 p = head-next; if (!p) return; s = p-next; p-next = NULL; while (s) p = s; s = s - next; p - next = head - next; head-next = p; 第三章 栈和队列F 栈是后进先出的线性表,队列是先进先出的线性表;F 在应用中,栈和队列都是容器,因此需要判断是否“栈空”或“队空”;F 采用顺序存储结构时,栈和队列都可能存在“溢出”问题,分别称为“栈满”、“队满”;F 采用顺序结构的队列常见形式是循环队列。F 栈的
6、运算演示(1)A、B、C、D四个元素依次进入一个栈,再依次出栈,得到一个输出序列DCBA 。 例题1. 用S、X分别表示入栈、出栈操作,若元素入栈顺序为1、2、3、4,为得到出栈序列1、3、4、2,则相应的S和X操作串是( SXSSXSXX )。2. 若push、pop分别表示入栈、出栈操作,初始栈为空且元素a、b、c依次进栈,则经过操作序列push、push、pop、pop、push、pop之后,得到的出栈序列为( b a c )。 3. 如果进栈的序列为1、2、3, 则不能得到的出栈序列为( 3 1 2 )。 令队列空间中的一个单元闲置,使得在任何时刻,保持Q.rear和Q.front之间
7、至少间隔一个空闲单元 MAXSIZE=8 F 队列满(full): (Q.rear+1)%MAXSIZE = Q.front F 队列空: Q.rear=Q.front F 队列长度: (Q.rear - Q.front+ MAXSIZE)% MAXSIZE例题1. 在循环队列结构中(队列空间容量为M),.rear指向队尾元素所在位置,.front指向队头元素所在位置,则队列的长度为( (Q.rear - Q.front + 1 + M) % M )。2. 用循环链表表示的队列长度为n,若只设头指针,则出队和入队的时间复杂度分别是( O(1) )和(O(n));若只设尾指针,则出队和入队的时间
8、复杂度分别是(O(1))和(O(1))。1. 若以域变量rear和length分别指示循环队列中队尾元素的位置和队列中元素的个数。请完善下面的入队列和出队列的算法。 #define MAXSIZE 100 /最大队列长度 typedef struct Qelemtype *base; /base为队列所在存储区域的首地址 int length; /队列长度 int rear; /队尾元素位置 SqQueue;1. 若以域变量rear和length分别指示循环队列中队尾元素的位置和队列中元素的个数。请完善下面的入队列和出队列的算法。 #define MAXSIZE 100 /最大队列长度 typ
9、edef struct Qelemtype *base; /base为队列所在存储区域的首地址 int length,rear; /队列长度和队尾元素位置 SqQueue; Status EnQueue(SqQueue &Q, Qelemtype e) /将元素e插入队列Q if( (1) ) return ERROR;/队列满,无法插入 Q.rear (2) ; /计算元素e的插入位置 (3) e; /在队尾加入新的元素 Q.length+; /队列长度加1 return OK; / (1) Q.length MAXSIZE (2) (Q .rear + 1) MAXSIZE (3) Q.b
10、aseQ .rear 第四章 串1. 了解串的基本运算2. 了解串的模式匹配算法第六章 树和二叉树二叉树或者是一棵空树;或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成 满二叉树中所有分支结点都有左孩子和右孩子, 叶结点都集中在二叉树的最后一层。满二叉树结点的编号:从树根为1开始,按照层数从小到大、同一层从左到右的次序进行。 完全二叉树中,最多只有最下面两层的结点的度数可以小于2,最下面一层的叶结点都排列在该层最左边的位置上。完全二叉树结点的编号:从树根为1开始,按照层数从小到大、同一层从左到右的次序进行。例题1. 一棵满二叉树中共有n个结点,其中有m个叶子结点,则n和m的关系为
11、( n=2m-1 )。 2. 在完全二叉树中,若一个结点没有左孩子子结点,则它一定没有( B )。 A父结点 B右孩子结点 C左兄弟结点 D右兄弟结点性质1 非空二叉树上第i层上至多有2i-1个结点i1。性质2 高度为h的二叉树至多有2h-1个结点(h1)。性质3 非空二叉树上叶结点数(度为0)等于双分支结点数(度为2)加1。 性质4 对完全二叉树中编号为i的结点(1in,n1,n为结点数),可以算出其左孩子结点、右孩子结点和父结点的编号(若这些结点存在)。 性质5 具有n个(n0)结点的完全二叉树的高度为log2 (n+1) 或 log2n+1。F 二叉树的顺序存储指的是用元素在数组中的下标
12、表示一个结点与其孩子和父结点的关系.F 一般用二叉链表存储二叉树(每个结点有两个指针域)F 树的遍历是访问树中每个结点仅一次的过程。可以认为遍历是把所有的结点放在一条线上,或者将一棵树进行线性化的处理。F 先序遍历DLR、中序遍历LDR、后序遍历LRDF 层序遍历F 先序遍历DLR:访问根结点、先序遍历左子树、先序遍历右子树F 中序遍历LDR:中序遍历左子树、访问根结点、中序遍历右子树F 后序遍历LRD:后序遍历左子树、后序遍历右子树、访问根结点F 先序遍历:访问根结点、先序遍历左子树、先序遍历右子树。下图的先序遍历序列为A B D E G C F。F 中序遍历:中序遍历左子树、访问根结点、中
13、序遍历右子树。下图的中序遍历序列为D B G E A C F。F 后序遍历:后序遍历左子树、后序遍历右子树、访问根结点。下图的后序遍历序列为D G E B F C A。F 层序遍历:先根后子树、先左子树后右子树。下图的层序遍历序列为A B C D E F G。例题1. 在有n个结点的二叉树的二叉链表中必定存在(n+1)个空链域。2. 前序遍历序列与中序遍历序列相同的二叉树为( D )。 A. 根结点无左子树的二叉树 B. 根结点无右子树的二叉树 C. 只有根结点的二叉树或非叶子结点只有左子树的二叉树 D. 只有根结点的二叉树或非叶子结点只有右子树的二叉树 3. 已知一棵二叉树的先序遍历序列为A
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 复习资料
![提示](https://www.zixin.com.cn/images/bang_tan.gif)
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【丰****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【丰****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。