复旦大学软件工程考研(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的连接。

上海市考研计算机复习资料数据结构与算法实战解析数据结构和算法是计算机科学与技术领域的重要基础知识，考研计算机专业的学生在备考过程中需要充分理解和掌握相关内容。

本篇文章将围绕上海市考研计算机复习资料，深入解析数据结构与算法的实战应用，以帮助考生有效提高复习效果。

1. 数据结构与算法的重要性在计算机科学与技术领域，数据结构和算法是进行程序设计和问题解决的基础。

良好的数据结构和高效的算法能够提升程序的执行效率，降低计算复杂度，并且对于解决各种现实问题具有重要意义。

因此，对于考研计算机专业的学生来说，全面理解和掌握数据结构与算法是备考过程中的必修课。

2. 数据结构与算法的实战应用在实际应用中，数据结构和算法被广泛应用于各种计算机领域，例如网络编程、数据库管理、图形图像处理等。

在网络编程中，常涉及到数据传输和存储问题，需要选取适合的数据结构进行处理，同时还需要设计高效的算法来提高数据的传输速度。

而在数据库管理方面，对于数据的增删查改操作，需要利用合适的数据结构和算法，以提高数据的访问效率。

此外，图形图像处理领域对于算法的要求更高，需要选择合适的算法来解决图像的处理、特征提取等问题。

综上所述，数据结构与算法的实战应用对于计算机专业人才的培养至关重要。

3. 上海市考研计算机复习资料在备考过程中，选择合适的复习资料对于提高复习效果起到关键作用。

上海市考研计算机复习资料是针对该地区考研计算机专业的学生所提供的学习资料，包括各个考点的重点知识、历年真题以及详细解析等内容，帮助考生全面了解考试的要求和难点。

备考阶段，考生可以根据自身情况选择适合自己的复习资料，并结合数据结构与算法的实战应用进行针对性的学习。

4. 数据结构与算法的学习方法为了更好地掌握数据结构与算法，考生可以采取以下学习方法：（1）理论学习：深入理解各种数据结构的原理和特性，学习不同算法的思想和应用场景。

（2）实践训练：通过编写程序实现各种数据结构和算法，加深对其掌握程度。

软件工程复习资料（提纲+答案）第一章软件工程的实质1、什么是软件？由什么组成？软件：是计算机系统中与硬件相互依存的另一部分，它是包括程序、数据及其相关文档组成的完整集合。

可以写作为：软件=程序+数据+文档。

2、什么是软件危机？为什么会产生？（原因）软件危机：指的是在计算机软件的开发和维护过程中所遇到的一系列严重的问题。

原因：用户需求不明确、缺乏正确的理论指导、软件规模越来越大、软件复杂度越来越高3、为什么要进行软件开发？4、软件工程的三段论？三段论：软件项目管理论、软件项目开发论、软件过程改进论5、软件工程生存期模型概念、类型、每种类型的特点？答：软件生存周期模型是描述软件开发过程中各种活动如何执行的模型。

软件生存周期模型确立了软件开发和演绎中各阶段的次序限制以及各阶段或机动的准则，确立开发过程所遵守的规定和限制，便于各种活动的协调，便于各种人员的有效通信，有利于活动重用，有利于活动管理。

常见的软件生存周期模型有瀑布模型、V模型、原型模型、增量式模型、螺旋式模型。

6、了解复用的原则第二章软件项目的需求分析1、需求分析的主要任务？（基本任务）答：需求分析阶段的基本任务是要准确的定义新系统的目标，满足用户需要，回答系统必须“做什么”的问题。

本阶段要主要有以下几方面工作：(1)问题识别，双方确定对问题的综合需求，包括：功能需求、性能需求、用户界面需求，以及可靠性、安全性、可维护性等方面的需求。

(2)建立模型，对获取的需求，进行分析细化，划分系统功能，确定系统构成，并建立系统的逻辑模型。

(3)编写文档，也就是完成“需求规格说明书”的编写工作。

2、需求分析分两大块（功能与非功能）功能需求描述系统所预期提供的功能或服务。

非功能需求是对系统提供的服务或功能给出的约束。

包括时间约束、开发过程的约束、标准等。

3、（P27）需求建模的基本方法？答：关联模型、行为模型（数据流模型和状态机模型）、数据模型、面向对象模型、结构化模型（技术：数据流图（DFD）、数据字典（DD）、系统流程图）以及其他方法（如原型法、功能列表等）4、结构化方法的代表？（P29）7状态图活动图8、理解好数据流图为什么要分层？9、UML中常用的9种图？（P32 把包图去掉）静态图：类图、对象图、构件图、实施图和包图。