《数据结构与数据库》复习.pptVIP

  1. 1、本文档共30页,可阅读全部内容。
  2. 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
* 《数据结构》复习 (仅供复习参考,考试范围不受此课件的限制) · 数据结构 70分 参考题型: 填空,选择,判断: 解答题: 算法题: · 对算法的要求:根据教学知识点的难易和重要性,将相关的算法理解和应用分三个层次进行要求: 层次1) 能阅读和理解算法,能结合具体数据给出算法执行结果; 层次2) 能写出算法的伪代码; 层次3) 能灵活运用算法,对实际问题进行算法设计。 第一章 序论 数据结构的知识点: 数据的逻辑结构 数据的存储结构 对数据的运算(运算的定义和运算的实现) 抽象数据类型的概念和表示方法 第一章 序论 算法的知识点: 算法的定义 算法的特性 算法的时间分析和空间分析方法 第二章 线性表 5个主要知识点: 线性表的定义 线性表的存储表示----顺序表,链表 线性表的运算在不同存储结构上的实现 有序表的操作 线性表的应用 第二章 线性表 线性表顺序存储结构的特点: 逻辑上相邻的元素在物理上也相邻; 不需要为表示元素之间的逻辑相邻关系开辟附加空间; 可以随机访问数据元素; 插入和删除元素时需要大量移动元素。 第二章 线性表 线性表链式存储结构的特点: 逻辑上相邻的元素在物理上不一定相邻; 需要为表示元素之间的逻辑相邻关系开辟附加空间:指针域; 无法随机访问数据元素; 插入和删除元素时不需要大量移动元素,只要修改相关结点的指针值即可。 第二章 线性表 几种常用的线性链表: 单链表 循环单链表(既可以用头指针引导,又可以用尾指针引导) 双向链表 双向循环链表 第二章 线性表 带头结点的链表和不带头结点的链表在操作上有差别. 判表空条件: 带头结点时 不带头结点时 单链表 head-next==NULL head==NULL 循环单链表 head==head-next head==NULL 第三章 栈和队列 栈和队列都是插入和删除操作受到限制的特殊线性表; 栈的特点: 后进先出(LIFO) 队列的特点:先进先出(FIFO) 第三章 栈和队列 栈的操作: 顺序栈:顺序表操作的特例 链栈:单链表操作的特例 第三章 栈和队列 队列的操作: 链队列:带头结点、头指针和尾指针的单链表,入队端在表尾,出队端在表头。 循环链队列:可以只用一个尾指针 用定长数组作为队列的存储结构时,一般采用循环队列的形式----循环队列。 第三章 栈和队列 队列的操作: 链队列:带头结点、头指针和尾指针的单链表,入队端在表尾,出队端在表头。 循环链队列:可以只用一个尾指针 用定长数组作为队列的存储结构时,一般采用循环队列的形式 第三章 栈和队列 循环队列: 数组:Q[1..maxsize-1] front指向对头元素 rear指向队尾元素的下一个 队列的最大容量:maxsize-1 0 6 5 4 3 2 1 7 front rear a5 a1 a2 a3 a4 第三章 栈和队列 循环队列的计算公式Q[0..maxsize-1]: 入队: rear = ( rear+1 ) mod maxsize 出队: front = ( front +1 ) mod maxsize 队空条件: front == rear 队满条件: front == (rear+1) mod maxsize 队列长度: (rear – front + maxsize) mod maxsize 第三章 栈和队列 循环队列的计算公式Q[1..maxsize]: 入队: rear = rear mod maxsize+1 出队: front = front mod maxsize +1 队空条件: front == rear 队满条件: front == rear mod maxsize+1 队列长度: (rear – front + maxsize) mod maxsize 第4章 数组 数组知识点: 多维数组行优先和列优先的存储方式; 数组元素地址的计算方法; 特殊矩阵的压缩存储方法以及下标变换算公式的推导; 稀疏矩阵的压缩存储技术----三元组表、十字链表。 第6章 树和二叉树 知识点(1): 树和二叉树的定义 二叉树的(5个)性质 完全二叉树的特点 二叉树的存储结构,主要掌握二叉链表 二叉树的遍历算法以及二叉树常用运算 第6章 树和二叉树 知识点(2): 表达式的二叉树表示 树的存储结构 树、森林与二叉树的相互转换 树和森林的遍历 哈夫曼树的定义和构造,哈夫曼编码方法 第7章 图 知识点(1): 图的概念: 有向图,无向图 路径,回路(环),简单路径,简单环 无向连通图、连通分量 有向强连通图、强连通分量 完全图 第7章 图 知识点(2): 生成

文档评论(0)

jdy261842 + 关注
实名认证
文档贡献者

分享好文档!

1亿VIP精品文档

相关文档