没有合适的资源？快使用搜索试试~ 我知道了~

首页2019中科大算法设计与分析期末复习重点.pdf

2019中科大算法设计与分析期末复习重点.pdf

算法设计与分析

期末考试

需积分: 44 27 下载量 177 浏览量更新于2023-03-03 评论 2 收藏 997KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

试读

15页

为2019年1月考试而准备的复习重点。根据张署老师2019秋季给的重点，自己又结合之前讲课的ppt总结而成，涵盖了所有考点，精简意赅，建议看完老师ppt后再来看我总结的知识点。

资源详情

资源评论

资源推荐

19级算法设计与分析期末复习重点

数据结构

红黑树

红黑树的性质

1.本身是一棵二叉查找树

2.每个结点要么是黑色要么是红色

3.树根结点的颜色为黑色

4.叶结点(nil)为黑色

5.如果某个结点为红色，则它的左、右孩子结点均为黑色

6. 对树中任一结点，所有从该结点出发到其叶结点的路径中均包含相同数目的

黑色结点

红黑树的操作及时间

插入：时间复杂度O（lgn）

删除：时间复杂度O（lgn）

查找结点，找前驱、后继：时间复杂度O（lgn）

红黑树的应用

序统计树

概念

序统计就是在一系列数中找出最大、最小值，某个数的序值等操作。

解决动态序统计问题

Size[x]域的定义为：以x为根的子树所包含的内部结点数(包括x本身)

Size[x]=Size[x.le]+Size[x.right]+1

找第i个最小值操作：算法时间：O(lgn)

求x的序值操作：算法时间：O(lgn)

完成一次插入或删除操作：时间为O(lgn)

区间树

概念

关键字=区间的低端点

新增域int：区间的端点值

新增域max：x.max=Max(x.int.high, x.le.max, x.right.max )

查找操作：算法时间O(lgn)

数据结构的扩张步骤

1. 挑选一个合适的基本数据结构

2. 决定在基本数据结构上应增加的信息

3. 修改基本数据结构上的操作并维持原有的性能

4. 修改或设计新的操作

定理

1.具有n个内部结点的红黑树高度h最多为2lg(n+1) ，即h=O（lgn）

2.黑高度：黑高度bh(x)表示从x结点出发(不包含x结点)到其叶结点路径上的黑色

结点个数。

3.令f为具有n个结点的红黑树扩张后的一个域，如果结点x的f域值仅需通过结点

x、le[x]、right[x]以及f(le[x])、f(right[x])就可获得，那么插入和删除操作对树T

中所有结点f值进行维护将维持O(lgn)的性能

区间树的查找算法，要么返回与i重叠的某个结点，要么返回为空表示树T中未找

到与i重叠的区间。

二项堆

二项树

定义

仅包含一个结点的有序树是一棵二项树称为B0树。

二项树Bk由二棵Bk-1树组成

其中一棵Bk-1树的根作为另一棵Bk-1树根的最左孩子(k≥0)。

性质

1. 有2^k个结点，即n=2^k

2. 树的高度为k , 即k=lgn（注：二项树的高度从0开始计数）

3. 深度为i处恰好有个结点 0≤i≤k

4. 根的度最大且为k，若根的孩子从左到右编号为k-1,k-2,…,1,0，则孩子i恰好

是子树Bi的根。

5. 一棵具有n个结点的二项树中,任一结点的最大度为lgn

二项堆

定义

二项堆H是一个满足下述条件的二项树的集合：

①H中的每棵二项树满足最小堆性质

②对任意的非负整数k，H中至多有一棵二项树根的度为k（保证每一棵二项

树度的唯一性）

根表的性质

eg：head[H]------->B0-------->B2-------->B3

①根表为一单链表

②根表链接所有二项树的根结点

③根表按照度的递增序链接

二项堆的操作

1. 创建空堆：算法时间O（1）

2. 插入结点：算法时间O(lgn)

①将待插入结点变为一个只有一个结点的二项堆

②合并两个二项堆

3. 合并堆H1，H2：算法时间O(lgn)

① 先把两个根表合并为一个根表

②合并度相同的两颗二项树。（如果有3个度相等的二项树，优先合并后两

个）

4. 取最小值：算法时间O(lgn)

遍历根表

5. 抽取最小值：算法时间O(lgn)

① 把该二项树根结点移除，所有孩子形成一个二项堆

②合并两个二项堆

6. x减值为k：算法时间O(lgn)

冒泡上升

7. 从堆中删除结点x：算法时间O(lgn)

①将该节点x减值为负无穷

②调用抽取最小值操作。

Fib堆

Fib堆的定义

1. Fib堆是一具有最小堆有序的树的集合。

2. 每棵树均满足最小堆性质

3. 树不要求一定是二项树

4. 操作的时间分析采用平摊分析方法

根表的性质

1. 根表链接堆中所有树根结点

2. 根表中度不再唯一

3. 根表不需要按照度的递增序排列

4. 根表头指针改用Min[H]表示，指向根表中具有最小值的树根结点

剩余14页未读，继续阅读

中科大算法导论期末试卷及答案

算法导论期末试卷以及其答案，期末算法导论备考资料。中科大算法导论期末试卷及答案中科大算法导论期末试卷及答案

中科大_研究生_算法设计与分析_最新期末复习资料15年试卷答案.rar

daydayluck

粉丝: 7
资源: 3

上传资源快速赚钱

我的内容管理收起

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

会员权益专享

2019中科大算法设计与分析期末复习重点.pdf

评论0

会员权益专享

最新资源

2019中科大算法设计与分析期末复习重点.pdf

评论0

中科大算法导论期末试卷及答案

中科大_研究生_算法设计与分析_最新期末复习资料15年试卷答案.rar

中科大算法设计与分析课堂作业答案

中科大算法设计与分析复习资料csdn

算法设计与分析期末复习csdn

数值分析期末复习笔记.docx

算法设计与分析期末期末设计

计算机算法设计与分析期末考试复习题csdn

周培德 计算几何:算法设计与分析.pdf

计算机常用数值算法与程序(c++版).pdf

广州大学算法设计与分析期末试卷 csdn

算法设计与分析期末知识点csdn

算法设计与分析 期末不挂科

山东大学2019年-数据结构-期末试卷真题.pdf

算法设计与分析第二版王红梅pdf

屈婉玲算法设计与分析第二版pdf

算法设计与分析李春葆pdf

hnu算法设计与分析期末试卷

捷联惯导matlab算法,捷联惯导算法与组合导航原理讲义.pdf

厦门大学 算法设计与分析 pdf

会员权益专享

最新资源

周培德计算几何:算法设计与分析.pdf

算法设计与分析期末不挂科

厦门大学算法设计与分析 pdf