复旦大学软件工程考研(MSE)数据结构复习资料PPT课件

格式：ppt
大小：2.14 MB
文档页数：10

下载文档原格式

软件工程复习范围汇总PPT课件

测试
运行运行与维护期
发现错误和排除错误测试报告
维护
改进的系统
第12页/共166页
另一独立的部门用户、高级程序员
软件生存期模型
软件生存期模型是跨越整个生存期的系统开发、运作和维护
所实施的全部过程、活动和任务的结构框架。
• 瀑布模型 • 原型模型 • 螺旋模型 • 喷泉模型
第13页/共166页
外部实体
------ 位于软件系统边界之外的信息生产者或消费者
数据流
------ 在转换之间有向流动的数据项或数据集合
数据存储文件 ------可以是数据库文件或任何形式的数据组织。箭头
向内则表示写入文件或查询文件，箭头向外则表示从文
件中读取数据或得到查询结果
第40页/共166页
输入
数据的加工或
计算、编译系统等）很重要。
第55页/共166页
OMT模型系统分析设计过程
产生需求建立模型
问题描述
分
析
阶
段
对象模型、动态模型、功能模型
结构及对象设计
设
详细的对象模型
计
详细的动态模型
阶
详细的功能模型
段
第56页/共166页
Category
Class-&-Object
Structure
1、基本过程 Attribute Method
……
第48页/共166页
2、数据字典定义符号
符号含义
例子
= 被定义为
+与 [] 或
x=a+b，则表示 x 由 a 和 b 组成 x=[a,b]，则表示 x 由 a 或由 b 组成

复旦MSE复习资料软件工程(SE05软件测试2011)

26
• 1）测试是为了验证软件已正确地实现了用户的要求。 • （2）白盒测试仅与程序的内部结构有关，完全可以不考
虑程序的功能要求。 • （3）黑盒测试的测试用例是根据程序内部逻辑设计的。 • （4）为了快速完成集成测试, 采用一次性集成方式是适
宜的。
（5）在软件开发过程中，若能推迟暴露其中的错误，则为修复和改正错误所花费的代价就会降低。
27
• 1、错。测试的目的是尽可能多地发现软件中的错误，其附带的收获才是验证该软件已正确地实现了用户的要求。
2、对
3、错。黑盒测试主要是根据程序的有关功能规格说明和覆盖准则来设计测试用例，进行测试的，不是根据程序的内部逻辑来设计测试用例。
4、错。采用一次性集成方式进行模块组装，往往成功率很低，而且出现错误时，不容易确定问题出现在什么地方，因此应采用增量式集成方式，可以把出错的范围局限到少数模块之中。
19
软件测试步骤
• 系统测试（system testing）将软件、硬件、数据库等集成为计算机系统，检查系统的功能、性能等是否符合计算机系统的要求测试方法：黑盒发现的错误：系统工程
20
测试与软件开发各阶段的关系
21
软件开发V模型
系统工程
系统测试
需求分析
确认测试
设计
集成测试
编码
单元测试
32
3
有关软件测试的错误观点
• “程序测试是证明程序正确地执行了预期的功能”。实际上，一个程序不仅要完成它所需完成的功能，而且不应完成它不该做的事。如不能把边长为0、0、0的三条边判断为等边三角形。
4
软件测试的原则
1. 应当把“尽早地和不断地进行软件测试” 作为软件开发者的座右铭。

复旦MSE复习资料-软件工程(SE02 软件需求分析2011)

其他几种关于"需求"的定义
＊需求是用户所需要的并能触发一个程序或系统开发工作的说明；＊需求是从系统外部能发现系统所具有的满足于用户的特点、功能及属性等；＊需求是指明必须实现什么的规格说明。它描述了系统的行为、特性或属性，是在开发过程中对系统的约束。
一条鸿沟
• 建造软件系统的过程中，我们经常习惯地沿用一些不规范的方法，其后果便是产生一条鸿沟--开发者开发的与用户所想得到的软件存在着巨大的"期望差异"。
数据流图举例
• 教务人员维护学生信息和课程信息，并登录学生的选课成绩；学生查询自己的成绩单。0层
数据流图举例
• * 第1层DFD图对第0层DFD图中的一个加工"学生成绩管理"进行展开。
数据流图举例
• 第2层DFD图对第1层DFD图中的一个加工"查询学生成绩"进行展开
鸿沟产生的原因
• 我们也许会问：为什么人们开发一个软件系统会比建造一座摩天大厦要难得多？ • 一是因为软件行业缺乏准确而又统一的语言来定义或描述相应的工作，真正的"需求"实际上存在于人们的头脑中； • 二是因为软件开发过程难以用一种工程化的方法来统一规范和有效实施。因此"需求"这个名词的定义不仅仅是从用户角度对系统外部行为的描述，以及从开发人员角度对系统内部特性的描述，其关键的一点是"需求"必须文档化。
软件需求包含着多个层次
• 实际上，软件需求包含着多个层次，不同层次的需求从不同角度与不同程度反映着细节问题。 IEEE软件工程标准词汇表（1997年）将需求定义为：（1）用户解决问题或达到目标所需的条件或能力。（2）系统或系统部件要满足合同、标准、规范或其它正式规定文档所需具有的条件或能力。（3）一种反映上面（1）或（2）所描述的条件或能力的文档说明。 IEEE的定义包括从用户角度（系统的外部行为），以及从开发者角度（一些内部特性）来阐述需求，其关键的问题是一定要编写需求文档。

数据结构.ppt

2020/6/19
数据结构
11
第一章概论
1.4 算法分析
一、算法评价五要素（1）正确性（2）执行算法所耗费的时间（3）执行算法所耗费的空间（4）可读性（5）健壮性
2020/6/19
数据结构
12
第一章概论
二、算法的时间复杂度
•一个算法所耗费的时间:该算法中每条语句的执行时间之和。 •每条语句的执行时间：该语句的执行次数乘以该语句执行一次所需时间。 •频度：语句重复执行的次数 •算法的时间耗费T(n)=每条语句的执行的时间
....
2020/6/19
(*L).data[数(*据L结)构.last] an
21
2.2 线性表的顺序存储
二、顺序表上的基本运算（实现） SETNULL（L）： (*L).last = -1
LENGTH(L):
(*L).last+1
GET(L,i):
(*L).data[i-1]
LOCATE(L,x)
注意: 1.数据元素ai是一个抽象的符号 2. ai可取各种数据类型 3. 一般情况下,同一线性表中的元素具有相同的数据类型 4. i是元素的序号 (1<=i<=n)
2.逻辑特征：仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继
2020/6/19
数据结构
18
二、线性表的运算
2020/6/19
数据结构
6
存储结构： •顺序存储方法：数据元素在内存中按序连续存储，
结点间的逻辑关系由存储单元的邻接关系来体现 •链接存储方法：用指针指出其直接后继结点的存储位置，
结点间的逻辑关系由存储单元的邻接关系来体现 •索引存储方法：数据元素连续存放，再设一个索引表（有序），索引表由索引项组成，每个索引项由关键字和地址构成

复旦大学软件工程考研[MSE]数据结构复习资料全

2j+1
证明
完全树的数组形式存储
完全树的数组形式存储算法
将其编号为i的结点元素存储在一维数组下标为i－1 的分量中
例题
已知数组[20,30,19,87,30,40]表示一棵完全二叉树，请画出该树。
练习答案
树的遍历
树的遍历
按某种搜索路径巡访树中每个结点，使每个结点均被访问一次仅且一次
栈的基本概念和性质
栈：
栈是限定仅在表尾进行插入和删除操作的线性表后进先出特性（LIFO）栈顶、栈底、出栈、入栈
例题
设有一个栈S，元素S1, S2, S3, S4, S5, S6依次进栈，如果6个元素的出栈顺序为S2, S3, S4, S6, S5, S1，则栈的容量至少应为多少？
树的基本概念和术语
树：
是n（n≥0）个结点的有限集在任意一棵非空树中：
1. 有且仅有一个特定的称为根的结点 2. 当n>1时，其余结点可以分为m（m>0）个互不相交的有
限集，其中每个集合本身又是一棵树，并且称为根的子树
树属于层次结构数据结构
树的基本概念和术语
节点
标签
父节点、子节点、兄弟节点、祖先节点、子孙节点
将算法3.1中8换成d
例题
十进制数1167等于八进制数——？
答案： 2217 思路：
计算方法：除余倒排法验证方法：指数相加法
习题
十进制数1167等于七进制数——？
栈的应用
表达式求值：
中缀表达式转后缀表达式
后缀表达式求值
三种表达式：
前缀表达式
+ab
例题答案
树的遍历

软件技术基础第二章(8)基本数据结构复习课PPT课件

第二章:基本数据结构复习课
1
.
复习
顺序存储结构下逆转线性表的算法。
输入：长度为n的线性表数组A(1:n) 输出：逆转后的长度为n的线性表数组A(1:n)
Procedure InvertSL(n,A) for k=1 -k+1)；A(n-k+1)=t } return
12
.
计算二叉链表深度的算法。
输入：二叉链表的头指针BT 输出：二叉链表的深度d
Procedure Depth(BT,d) d=0 if (BT=0) then return else { Depth(L(BT),d1)
if (d1>d) then d=d1 Depth(R(BT),d2) if (d2>d) then d=d2 } d=d+1 return
for j=1 to n do { if (V(k,j)>0) then
{ New(p) Num(p)=j; Val(p)=V(k,j) Next(p)=Link(k); Link(k)=p }
} } Return
14
.
if (V(k)<0) then { Next(k)=Next(Head); Next(Head)=k; Next(kk)=j } else kk=k k=j } return
7
.
反复找出给定线性单链表中结点值最小的结点，输出该值并将该结点从表中删除。
输入：线性单链表头指针Head，结点值均为正整数输出：按值从小到大输出线性单链表中的值
6
.
按值重新链接循环链表的算法。
输入：按绝对值从小到大链接的循环链表头指针Head 输出：按值从小到大链接的循环链表头指针Head

复旦MSE高级数据库技术复习资料

高级数据库技术复习资料（2011年10月）本次考试范围请关注教科书相关章节课后练习的奇数计算题部分。

一．缓冲区管理（Buffer Management）【书: P239；PPT: Storing data；答案请打印: P118-P126(以备不时之需)】课堂练习，基于LRU(least recently used)算法，计算经过get(7), get(2), get(6), pin(7), get(1), get(3), unpin(7), get(2)操作后，缓冲区中的值和Miss次数。

操作完成后，缓冲区中的值为7, 2, 3；Miss次数为6。

二．B+树（要求：给一课树，插入几个节点，删除几个节点，需要写出中间过程；约定：从左边借，右边是大于等于）【书: P257；PPT: Tree-Structured Indexes；答案请打印: P127-P145(以备不时之需)】考虑图10.27所示的秩d=2的B+树索引。

图10.271)把码值为9的数据项插入原始树，显示得到的树。

2)把码值为3的数据项插入原始树，显示得到的B+树。

插入需要多少页的读操作和多少页的写操作？答：插入需要4页的读操作，5页的写操作，并分配2个新的页。

3)把码值为8的数据项从原始树中删除，显示得到的B+树，并假设对可能的重分布检查左兄弟。

4)把码值为8的数据项从原始树中删除，显示得到的B+树，并假设对可能的重分布检查右兄弟。

5)从原始树开始插入码值为46的数据项后，再删除码值为52的数据项，显示得到的B+树。

6)把码值为91的数据项从原始树中删除，显示得到的B+树。

7)从原始树开始插入码值为59的数据项后，再删除码值为91的数据项，显示得到的B+树。

8)连续把码值为32，39，41，45和73的数据项从原始树中删除，显示得到的B+树。

三．连接操作Join algorithms（要求：给出关系R和S，求BNM、I/O次数，需要了解循环嵌套算法，尤其是块循环BNL（Block Nested Loops）算法、排序归并SMJ（Sort Merge Join）算法、HASH算法，只需要考虑一般的HASH，不需要考虑混合HASH的情况）【书: P337；PPT: Implementation of Relational Operations；答案请打印: P186-P201(以备不时之需)】相关公式：1）嵌套循环连接算法：M+M×N（M是外关系）2）块嵌套循环连接算法（没有缓冲区）：M+N3）块嵌套循环连接算法（有缓冲区）：M+N×⌈M/(B−2)⌉4）块嵌套循环连接算法（有缓冲区，并直接给出缓冲区所能容纳的页数）：M+N×⌈M/所能容纳的页数⌉5）排序归并连接算法：2×(⌈log B−1M/B⌉+1)×M+2×(⌈log B−1N/B⌉+1)×N+M+N6）排序归并连接算法（优化后）： 3×(M+N)7）哈希连接算法：3×(M+N)考虑练习14.1中关系R和S的连接。

复旦大学软件工程考研(MSE)数据结构复习资料ppt课件

17
习题
十进制数1167等于七进制数——？
精选课件PPT
18
栈的应用
表达式求值：
中缀表达式转后缀表达式
后缀表达式求值
三种表达式：
前缀表达式
+ab
中缀表达式
a+b
后缀表达式
ab+
精选课件PPT
19
例题
中缀表达式a + b × c – d转为后缀表达式是— ———？
答案： a b c×＋d－
精选课件PPT
20
例题
中缀表达式（a + b） × c – d转为后缀表达式是————？
答案： a b ＋ c×d－思路：
数字位序不变，运算符位置改变后缀表达式无括号，运算顺序同中缀表达式
精选课件PPT
21
习题
中缀表达式A-(B+C)*D/E的后缀形式是 _________________。
普通树的遍历
前根：先遍历根结点，再依次前根遍历各棵子树后根：先后根遍历各课子树，再遍历根结点已知树写遍历结果已知遍历结果画树
精选课件PPT
22
练习
中缀表达式a * ( b + c ) / d转为后缀表达式是 ————？
精选课件PPT
23
例题
计算后缀表达式1 2 + 4 * 2 /的值为——？
答案：6 思路：
顺序计算或转换为中缀表达式计算
精选课件PPT
24
习题
计算后缀表达式3 2 － 4 * 2 / 3＋的值为—— ？
精选课件PPT
25
递归
一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称为递归函数

MSE考研复习

24
计算机网络的分类
按网络覆盖的范围分类按拓扑结构分类按信息交换方式分类
25
按网络覆盖的范围分类
局域网LAN 校园网CAN 城域网MAN 广域网WAN 全球网GAN (Local Area Network) (Campus Area Network) (Metropolitan Area Network) (Wide Area Network) (Global Area Network)
报文交换分组交换
数据报虚电路方式
30
网络通信标准化组织
标准化工作的好坏对一种技术的发展有着很大的影响，缺乏国际标准将会使技术的发展处于比较混乱的状态，而盲目自由竞争的结果很可能形成多种技术体制并存且互不兼容的状态 1992年，因特网不再归美国政府管辖，因此成立了一个国际性组织叫做因特网协会ISOC （internet Society），以便对因特网进行全面管理以及在世界范围内促进其发展和使用。 ISOC下面有一个技术组织叫做因特网体系结构研究委员会 IAB (Internet Architecture Board），负责管理因特网有关协议的开发。 IAB下面又设有两个工程部。
传输介质
41
ISO/OSI参考模型
1. 物理层（The Physical Layer）
在物理线路上传输原始的二进制数据位（基本网络硬件）。
2. 数据链路层（The Data Link Layer）
数据报分组交换112虚电路分组交换在数据传送之前先建立站与站之间的一条逻辑通路不是专用的通路分组在每一个节点上仍需缓冲并在线路上进行排队等待输出一个站能和任何站建立多个虚电路也能与多个站建立虚电路每条虚电路支持特定的二个端系统之间的数据传输每个分组除了数据之外还有一个虚电路标识节点根据虚电路标识知道把这些分组引导到哪里113虚电路方式数据交换过程114虚电路分组交换提供可靠的通信功能能对差错流量顺序进行控制每个节点要有一张虚电路表存放已经建立的虚电路信息当某个节点或某条线路出故障时所有经过该节点线路的虚电路立即被破坏115数据报分组交换特点

软件工程整理ppt

• 物流系统或快递公司向客户送货、收款（只对未付款的客户），以及向系统业务员返回客户签收单都不属于本案例的网上购物系统
复旦大学计算机科学技术学院软件工程（第二版）
16
• 用况的详细描述 ➢前置条件和后置条件
前置条件和后置条件表示用况开始和结束的条件 ➢事件流（flow of events）事件流是一系列陈述句，它是从执行者的角度看，列出用况的各个步骤用况描述中可以包含条件、分支和循环例如：订购货物用况的描述如下
9
我们可以通过回答下列问题来确定执行者：
• 谁使用系统的主要功能（主执行者）？
• 谁需要从系统中得到对他们日常工作的支持？
• 谁需要维护、管理和维持系统的日常运行（副执行者）？
• 系统需要控制哪些硬件设备？
• 系统需要与哪些其他系统交互？
• 哪些人或哪些系统对系统产生的结果（值）感兴趣？
复旦大学计算机科学技术学院软件工程（第二版）
11
2. 寻找用况
可以通过让每个执行者回答以下问题来寻找用况：
• 执行者需要系统提供哪些功能？执行者需要系统做什么？
• 执行者是否需要读、创建、删除、修改或储存系统中的某类信息？
• 执行者是否要被系统中的事件提醒，或者执行者是否要提醒系统中某些事情？从功能观点看，这些事件表示什么？
• 执行者的日常工作是否因为系统的新功能（尤其是目前尚未自动化的功能）而被简化或提高了效率？
似乎20个太少，而100个太多，希望在项目规模和用况数之间保持均衡
复旦大学计算机科学技术学院软件工程（第二版）
ቤተ መጻሕፍቲ ባይዱ
13
四. 用况的描述
用况通常用正文（text）来描述,也可用活动图来描述

复旦MSE复习资料软件工程(SE03软件设计2011)

• 在设计软件结构时应追求尽可能松散的耦合。
1．耦合
耦合有以下5类：
① 数据耦合：模块间通过参数传递基本类型的数据，称为数据耦合。
② 标记耦合：模块间通过参数传递复杂的内部数据结构，称为标记耦合。此数据结构的变化将使相关的模块发生变化。
③ 控制耦合：一个模块在界面上传递一个信号（如开关值、标志量等）控制另一个模块，接收信号的模块的动作根据信号值进行调整，称为控制耦合。
– 模块之间相互调用时，传递的参数最好只有一个，最多不超过四个。
– 在设计模块时尽量做到把模块之间的连接限制到最少，模块环境的任何变化，都不应引起模块内部发生改变。
2．内聚
• 一个模块内各个元素彼此结合的紧密程度用内聚来度量。
• 理想的模块只完成一个功能，模块设计的目标之一是尽可能高的内聚。
• 模块的作用域与控制域 – 模块的作用域是指模块中判定的影响范围。 – 模块的控制域是指模块本身及其直接或间接调用的模块。
模块化
• 模块化（Modularization）是把系统分割成能完成独立功能的模块，明确规定各模块及其输入输出规格，使模块的界面不会产生任何混乱。
• 在软件工程中，模块化是大型软件设计的基本策略。在软件系统模块化时，最重要的原理是模块独立性，而模块独立性要求模块之间低耦合和模块内部高内聚。
软件设计概述
• 概要设计：将软件需求转化为数据结构和软件的系统结构。概要设计只是描绘出软件的总体框架，根据功能、性能需求和数据需求导出软件的数据结构和系统结构。
• 概括地说，概要设计进行数据设计/数据库设计和系统体系结构设计。
• 概要设计主要完成以下任务： • 制定规范； • 软件系统结构的总体设计； • 数据库设计； • 概要设计评审。

软件技术数据结构PPT课件

for (i = 0; i < num; i++) scanf("%d",
&array[i]);
printf("All of %d elements are: \n", num); // 输出提示
for (i = 0; i < num; i++) printf("%d,", array[i]); // 输出刚输入的num个数据
第6页/共16页
软件技术
1）一维数组
▲ 使用前必须定维 ▲ 作为函数的参数时，可以不定维 ▲ 作为函数的参数时，可以从函数中带出值来 ▲ 使用当中不要超界（C语言不检查） ▲ 下标从0开始，到n-1为止（与VB不同） ▲ 可用于保存向量
第7页/共16页
软件技术
2）二维数组
▲ 存储方式：按行存放 ▲ 作为函数的参数时，列必须定维 ▲ 可用于保存矩阵，用于解线性方程组
第15页/共16页
感谢您的观看！
第16页/共16页
开发平台标识符匈牙利命名法集成环境如何保持运算精度软件调试
第2页/共16页
软件技术
1 什么是数据
客观事物属性的符号表达，能输入到计算机中并被其处理 1）并非只是数字，还包括字符等 2）并非只是常量，主要是指变量 3）广义的数据 ▲ 数字、字符等常量 ▲ 简单变量、数组、结构体、链表、树、图等 ▲ 图形、影像、声音等——信息
软件技术
可调数组
if (array == 0) // 内存申请失败,提示退出 {
printf(“Error, press any key to quit\n");
exit(0); // 终止程序运行,返回操作系统 }

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

C 24
9
F 27 ZK
306
120
186
E
79
37 42 42 UDL
Round 7 (final)
107
65
32
33
C 24
9
F 27 ZK
例题
0 306 1
Letter Freq Code Bits
C
32 1110
4
D
42
101
3
120
E
0 186 1
E 120
0
1
F
24 11111
5
K
简
单
13 38 65 97 76 49 27 49’
选
择
13 27 65 97 76 49 38 49’
排
序
13 27 38 97 76 49 65 49’
示
例
13 27 38 49 76 97 65 49’
13 27 38 49 49’ 97 65 76
13 27 38 49 49’ 65 97 76
38 65 97 76 13 27 49’
tem
4p9
27 38 65 97 76 13
49’
27 38
97 76 13 65 49’
27 38 13 97 76
65 49’
27 38 13
76 97 65 49’
27 38 13 49 76 97 65 49’
49 38 65 97 76 13 27 49’
13 27 38 49 49’ 65 76 97
10
15
56
115237 056500
• 大纲描述：
• 查找的基本概念；对线性关系结构的查找，顺序查找，二分查找； • Hash查找法,常见的Hash函数(直接定址法,随机数法),hash冲突的概念, 解决冲
突的方法(开散列方法/拉链法,闭散列方法/开址定址法),二次聚集现象; • BST树定义,性质,ADT及其实现,BST树查找,插入,删除算法; • 平衡树 (AVL) 的定义,性质,ADT及其实现,平衡树查找,插入算法,平衡因子的概
AADF pr u e e
gcb
J MMJ J S ON a ar a u ul e ct o n yn p v
范围查询
• 定义:
• 在指定集合中有多少记录的关键字是落在指定范围中
• 一维的情况:
• 记录可以看作直线上的点 • 问题可以看作有多少点落入指定线段区域中
快速排序
49 38 65 97 76 13 27 49’
0
26
1
41
15
68
2
若一组关键字为（26，36，
44
41，38，44，15，68，12，
3
06
06，51，25），散列函数定
义为：H(key) = key%13。
用拉练法建立的散列表为：
4
5
36
6
38
12
51
25
练习答案
01234567891111111 0123456
例题
• 写出如右图所示树的先根、后根、层次序遍历结果
给出如图所示树的先根、后根和层次序遍历结果
练习
将如图所示树转换为二叉树
(1) 由给=根{定结T0,的点T1n，,个T其2,权…左值, 、T{nw-右1}0，,子w其树1, 中w均2每,为…一空, w棵。n-二1}，叉构树造Ti只具有有一n棵个二带叉有树权的值集w合i的F
2 7 24 3 37 42 42 120 2
7 24 32 37 42
KFCU D
42 120 LE
24 32 37 42 42 120
9
FCU D L E 27
Round 1 Z K
32
37 42 42 120
Round 2 C
33
24 U D L E
9
27F
ZK
37 42 42
120
65
UDL
数据结构 2016MSE考研冲刺
树的基本概念和术语
• 节点 • 标签 • 父节点、子节点、兄弟节
点、祖先节点、子孙节点 • 路径、树枝
• 根、叶子 • 次数 • 内部节点、外部节点 • 树的次数、K次树 • 节点层次、树的高度和深
度 • 子树 • 有序树、无序树 • 森林、果园
念; • 优先队列与堆,堆的定义,堆的生成,调整算法;范围查询;
例题
• 已知BST树如左，请画出插入16，再删除36之后的BST树
练习答案
算法代码及基本的时间复杂度分析
查找方法顺序查找二分查找 BST查找 AVL查找
平均时间 O(n)
O(logn) O(logn) O(logn)
• 基本思想
• 当冲突发生时，使用某种方法在散列表中形成一个探查序列(也称之为"链")，按此序列逐个单元的查找，直到找到一个指定的关键字或碰到一个开放的地址（单元为空）为止。
• Hj = ( H(key) + dj ) MOD m
• 1 j m-1;m为hash表长度 • dj为增量数列,各种方法的不同就区别在取不同的增量数列上
例题
• 列出如上图所示树的所有叶子结点
• 答案：K,L,F,G,M,I,J
• 列出如上图所示树的所有分支结点
• 答案：A,B,C,D,E,H
• 树A为几次树？子树B呢？
• 答案：3，2
• 前页图所示树的高度为多少？
• 答案：4
例题
• 写出左图所示二叉树的前序、中序、后序、层次序遍历结果
E
32
33
C
24
9
F
27
ZK
Round 3
42
65
L 32
33
C 24
9
F 27 ZK
120
79
E 37 42 UD
Round 4
120
79
107
E
37 42 42 UDL
32 C
65 33
24
9
F 27
ZK
Round 5
120
186
E
79
37 42 42 UDL
Round 6
107
65
32
33
(2) 在F中选取两棵根结点的权值最小的二叉树, 做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
(3) 在F中删去这两棵二叉树，加入新得的树。
(4) 重复(2) (3)，直到F只含一棵树为止。这棵树就是赫夫曼树
例题
ZKF CU D L E
2 Step 1 Z
7 111101 6
L
42
110
3
79
0
1
0 107 1
1100 6
37 42 42
UDL
0 65 1
32
C
0 33 1
24
9
0
1F
27
习题答案
• A：0110 • B：10 • C：1110 • D：1111
• E：110 • F：00 • G：0111 • H：010

商业计划书模板复旦大学软件工程PPT9

页数:66
复旦大学软件工程考研(MSE)数据结构复习资料PPT课件

页数:10
复旦大学软件工程考研(MSE)计算机系统基础复习资料

页数:27
复旦大学软件工程钱乐秋课件教案

页数:27
复旦大学《软件工程》钱乐秋课件教案PPT02

页数:35
复旦大学软件工程考研(MSE)数据结构复习资料249页PPT

页数:249
复旦大学软件工程

页数:66