北大数据结构课件,内部资料,精品

数据结构课程的知识体系和教学实践

张铭许卓群杨冬青唐世渭/文

一、数据结构知识体系

计算机科学已经深入应用到各个领域，不仅有效地解决了各种工程和科学计算中的数值计算问题，而且也有效地解决了许多文本处理、信息检索、数据库管理、图像识别、人工智能等非数值的数据处理问题。数据结构有助于程序员更有效地组织数据、设计高效的算法、完成高质量的程序以满足错综复杂的实际需要。

数据结构是计算机学科的重要分支研究领域。数据结构和算法在计算机学科中的地位十分重要，其他计算机科学领域及有关的应用软件都要使用到各种数据结构。数据结构是算法分析与设计、操作系统、软件工程、数据库概论、编译技术、计算机图形学、人机交互等专业基础课和专业课程的先行课程。语言编译要使用栈、散列表及语法树；操作系统中用队列、存储管理表及目录树等；数据库系统运用线性表，多链表及索引树等进行数据管理；而在人工智能领域，依求解问题性质的差异将涉及到各种不同的数据结构，如广义表，集合、搜索树及各种有向图等等。

美国IEEE和ACM的教学计划CC2001把《算法与数据结构》列入计算机以及信息技术相关学科专业的本科必修基础课程。在我国，《数据结构》已经作为理工科非计算机专业必修的信息技术基础课程之一。世界上许多科技人员对学习、研究数据结构都非常重视，对于从事计算机科学及其应用的科技工作者来说，数据结构更是必须透彻地掌握的重要基础。

1．数据的逻辑结构、存储结构和运算

从字面上来看，数据结构就是指数据间的相互关系。具体到计算机环境，谈到任何一种结构时，都自然地联系着作用在这种类型的数据上的运算（即函数），为了在计算机上执行这些运算，我们有必要把这些数据以某种方式存储在计算机中。因此，我们可以认为，所谓数据结构，就是由某种逻辑关系组织起来的一批数据，按一定的存储方法被存储于计算机中，并在这些数据上定义了一个运算的集合。也就是说，数据结构具有三个方面：数据的逻辑结构、数据的存储结构和数据的运算。

常见逻辑关系有：线性结构、树形结构、图结构和文件结构。其中，线性结构是最简单的数据结构，例如，程序设计语言中往往都会介绍的线性表（包括数组和链表）、栈、队列、向量、字符串等。其中，字符串就是每个结点都是单个字符的线性表。实际上多维数组和广义表也是线性结构的推广。另外，文件其本质也是线性结构，不过由于存储在外存中，对文件数据的访问速度非常慢，因此，仔细研究文件结构和基于文件的外排序也是很有必要的。二叉树和树是非常重要的数据结构，其应用十分灵活而广泛。二叉树可以看作是树的特例。例如，语言编译中要用到语法树，操作系统有目录树，数据库系统需要用索引树等进行数据管理，而在人工智能领域，需要用到搜索树等。许多真实世界的问题都可以图来抽象地定义。例如，一张交通图可以用数据结构的图来形象化地表示：用结点表示城市，用边表示连接城市的高速公路；Web网页的关系也可以表示为图：Web网页作为结点，网页之间的链接作为边。图是一种最通用的逻辑结构，实际上，图?树?二叉树?线性表。

常见的存储方法有：顺序方法、链接方法、索引方法、散列方法。其中，索引存储又分为线性和树形两种。文件结构的索引则往往用树形结构。

对于一种数据结构，往往需要定义一些运算。例如，建立数据结构、清除数据结构、

插入一个新数据元素、删除某个数据元素、修改某个数据元素、排序、检索等。作为最常用的算法，排序和检索历来是数据结构讨论中的重点问题。排序算法最能够体现算法的魅力，它对算法速度要求非常高，其中内排序主要考虑的是怎样减少关键码之间的比较次数和记录交换次数，以提高排序速度。可以证明所有基于比较的排序算法的时间代价是Θ(n log n)，这也是排序问题的时间代价；而外排序则考虑外存的特性，尽量减少访外操作，以提高排序速度。检索则考虑怎样提高检索速度，这往往是与存储方法有关的。例如，我们可以利用索引存储来加快检索。散列表、B树和B+树等高效的数据结构都具有极好的检索性能。

2．算法的效率问题

每一种数据结构与其相关的算法都有时间、空间开销和效率等问题。每当面临一个新的设计问题时，设计者都应该要权衡时间空间开销，设计出更有效的数据结构和算法，以适应问题的需要。

基本问题包括：对于给定的一类问题，最好的算法是什么？需要多少存储空间和时间？空间与时间的折衷方案是什么？存取数据最好的方法是什么？最好算法的最坏情况是什么？平均来说，算法的运行好到何种程度？算法一般化到何种程度——即什么类型的问题可以用类似的方法处理？

这就涉及到算法分析技术，许多数据结构教材都揉合了一些基本的算法分析技术，这有助于读者根据问题的性质选择合理的数据结构，并对时间空间复杂性进行必要的控制。

3．抽象数据类型

事实上，数据结构的三个侧面，以数据的逻辑结构和数据的运算定义更为重要。因为很多时候人们并不关心数据的存储结构和运算的具体实现。1983年Aho等人把数据结构的存储与实现细节剥离，定义了抽象数据类型（简称“ADT”）的概念。抽象数据类型是定义了一组运算的数学模型。例如栈结构，栈中元素的数学特性(即逻辑结构)表现为线性表，它们是有序的；栈的主要运算是进栈(push)、出栈(pop)、判栈空(isEmpty)等。这里我们并不涉及栈的存储方式以及栈中元素的类型等。这种抽象的数据类型可以在较高级的算法中直接引用，而不用考虑它的实现细节。这就使得设计者可以在不同的设计阶段采用不同的抽象数据类型作为设计的基础，在适当的抽象层次上考虑程序的结构和算法，从而很好地支持了逻辑设计和物理实现的分离，支持封装和信息隐蔽。

大多数教材都是以数据的逻辑结构为主线，顺序介绍线性结构、树形结构、图结构和文件结构。在介绍每种数据结构时，再讨论其存储结构以及相关的算法。例如对于线性表，如果考虑到存储，可以分为数组和链表；考虑到运算的特殊性，则可以分为向量、栈和队列。对于一些比较重要的算法，再列出单独的章节来讨论，例如排序、检索、索引、存储管理等。

二、数据结构的教学目的

Peter J．Denning等人认为，计算机学科分为理论、抽象、设计这三个形态。我们把数据结构课程所涉及的主要方面整理为：

1. 理论

(1) 算法的数学基础。例如，有关图论、组合论等，特别是递归、递推、归纳等分析

方法。

(2) 算法的时间和空间度量。

2．抽象

(1) 排序、检索等重要问题类的有效算法，以及最好、最差和一般性能的分析比较。

(2) 重要数据结构技术，例如分治法(二分检索、快速排序、归并排序)、贪心算法

（Huffman编码、Prim算法、Kruskal算法、Dijstra算法）、动态规划（Prim算法、

Dijstra算法、Floyd算法、最佳二叉搜索树）、栈的引用（深度优先周游）、队列的

应用（广度优先周游）。

3．设计

(1)掌握并灵活应用常用的基本数据结构的抽象数据类型、各种基本存储方法及其主

要的算法，例如线性结构（包括一维数组、链表、栈、队列、字符串等）、二叉树、

树、图、文件；

(2)排序、检索、索引等重要问题类的算法的选择、实现和测试。例如，各种排序方

法的实验时间比较，散列、倒排索引、B树等应用。

(3) 存储管理的实现与测试。例如可利用空间表、无用单元收集、伙伴系统。

数据结构这门课程不仅仅要让学生掌握那些链表、树、图是如何实现的。设置这门课程有三个目的：第一个目的是让学生懂得“数据结构＋算法＝程序”；第二个目的是培养数据抽象的能力；第三个目的是使得学生把数据结构和算法理论与编程实践相结合，能够在实际的工程实践中灵活地予以应用。

在达到前两个目的时，学生就基本具备了解决现实未知问题的能力，再辅以必要的综合上机项目训练，可以达到第三个目的。

总而言之，通过数据结构课程的教学，学生需要掌握以下四个方面的知识和能力：（1）掌握并灵活应用常用的基本数据结构的抽象数据类型、各种基本存储方法、主要的算法，例如线性结构、二叉树、树、图、文件；（2）掌握并简单应用常用的排序、检索和索引算法和方法；（3）掌握基本的算法设计和分析技术，并对自己设计的数据结构和算法进行简单的分析；（4）在进行程序设计、调试、测试的课程项目训练（即上机实习训练）过程中，要求学生综合应用所学到的数据结构和算法知识，学会分析研究数据对象的特性，以便选择合适的数据结构和存贮结构以及相应的算法，合理地组织数据、有效地表示数据、有效地处理数据，书写的程序结构清楚、正确易读，提高程序设计的质量。

三、数据结构教材编写思路

1987年高教社出版的许卓群等编写的《数据结构》被很多高校的计算机系采用为数据结构课程主教材。该书已经连续再印刷近二十次，并于1992获得教育部教材优秀奖和国家教材优秀奖。在多年的使用过程中，国内很多读者建议更新部分内容，补充一些电子教案，并希望在算法的伪代码编码风格方面，由类PASCAL 改为类 C++语言。

我们采纳这些建议，由北京大学信息科学技术学院许卓群、杨冬青、唐世渭、张铭这四位多年从事《数据结构》教学和研究的教员一起修订《数据结构》教材。作者围绕中国计算机科学与技术学科教程CCC2002和美国IEEE和ACM的教学计划CC2001所规定的基本知识点，参考国内外的最新数据结构教材，编写第二版《数据结构》。

1．第二版的主要修订原则

z基本内容和知识点不做大的变动，不增加难度。

z考虑采用最广为程序员所使用的C++语言作为算法描述语言，从而使得抽象数据类型(ADT)的概念得到更自然的体现，更本质地体现数据结构的思想，而且所定义的

数据结构类能够方便地被重用。

z为了保证教材的易读性，尽量回避C/C++中比较麻烦的内容，例如C的指针的指针的指针等折磨人的东西，C++的类的继承、虚函数等。

z使用参数化的模板（template），从而提高算法中数据类型的通用性，支持高效的代码重用。在后面的章节中，尽量使用STL (Standard Template Library，标准C++类

库)所提供的栈、队列等基本数据结构。

z删除原来的逆转链周游二叉树、Robson周游算法、Siklossy周游算法、关键路径等内容。

z增加了Patricia树、伸展树等复杂树结构，k-d树、PR四分树、R*树等空间数据结构。

z每一章中都增补了比较多的综合上机实习题（即项目实习）。

z为了配合教材的发行，我们将编写概念清晰、内容充实的多媒体演示讲稿以及用标准C++模板编写的可执行的源程序代码。出版社可以考虑带光盘发行，或提供网站。

2．第二版新大纲的考虑

第一版完全按照逻辑结构的角度来安排内容。每一种数据结构都有一些比较复杂的算法。作者在给辅修数据结构的外系学生使用该教材时，只能选择一些比较浅显的内容，学生们感觉跳跃性比较大。而在使用该教材给计算机专业的学生讲课时，又常常感觉到树和图等基本数据结构太靠后，已经快到学期结束了，不好给学生布置大的上机实习题。

考虑到数据结构这门课程基本知识点的划分，根据我们多年教学经验，作者对第二版的目录进行了比较大的调整。第二版以中国计算机科学与技术学科教程CCC2002中的PF3基本数据结构、AL1算法分析基础、AL3基本算法为核心内容，分为基本数据结构、排序和检索、高级数据结构这三个部分。首先，第一部分（共6章）从逻辑结构的角度系统地介绍各种基本数据结构，即概论、线性表(包括向量、栈和队列)、字符串、二叉树、树和图。概论讨论了数据结构的定义、抽象数据类型和基本的算法分析技术。然后，第二部分（共4章）从算法的角度讨论排序、检索和索引算法，索引算法新增加了关于文本文件的倒排索引，倒排索引是当前信息检索和搜索引擎技术的关键技术。考虑到计算机学科的应用性以及学生灵活应用数据结构解决实际问题的需要，第三部分（共2章）介绍了数据结构的高级主题，例如广义表和稀疏矩阵等更复杂的线性表结构，Trie结构、A VL树、伸展树等复杂树结构，k-d树、PR四分树、R*树等空间数据结构，把存储管理作为线性结构的典型应用予以介绍，把决策树和博弈树作为树型结构的典型应用加以介绍。最后附录布置了一个学期综合上机实习题“搜索引擎”，并简单介绍了其中涉及的图搜索、倒排索引等技术。

其中第一部分是最基本的内容，教员可以根据学生的程度选择第二部分、第三部分一些内容来讲解。该教材能够适应不同的读者的学习需要以及教员的教学安排，特别为教师安排上机实习提供了极大的方便。

四、教学策略

数据结构课程中，既有很多灵活的与离散数学（尤其是图论、组合数学）有关的证明题，又有大量算法设计题。而且该课程对程序设计能力的要求很高，需要学生动手编写实习题以应用并掌握数据结构知识。对于计算机专业的学生来说，学习《数据结构》之前应该先修《计算引论》（或称“计算概论”，“计算机文化基础”）、《面向对象程序设计实习》、《集合论与图论》这三门课程。对于只有“计算概论”基础的非计算机专业的学生，可以适当减少数学证明的要求，不要求设计比较复杂的算法。

为了搞好“数据结构”这门重要主干基础课程的教学工作，作者以热忱的工作态度、以科研工作的钻研精神认真投入教学研究。投入了大量精力和时间，建立了全新的教学体系，尽力完善各个教学环节。

1．启发式教学，培养学生的创造性思维和主动学习精神

在数据结构教学中，对于每种数据结构都从其数学特性入手，先介绍其抽象数据类型，然后再讨论其不同的存储方法。与学生一起讨论研究不同存储方法的可能算法，结合算法分

析来讨论各种存储方法和算法的利弊，摒弃那些不适宜的方法。这样，充分调动了学生思维积极性，学到了数据结构的思维方法以及从事科研的基本方法。

2．与科研结合，在教学中引进新的理论和技术内容

尽量把科研中涉及到的与《数据结构》课程相关的新理论和技术、优秀论文介绍给学生，拓展了教学内容。例如，给学生讲解“搜索引擎”中的数据结构技术（主要涉及到图搜索、排序和索引技术），讲解当前网络和数据库的研究热点“XML（扩展标记语言）”。

3．加强实践环节的训练

北京大学计算机系历来十分重视实践环节的训练。《数据结构》课程一直为每学期4学分/每周4学时，每位学生的上机实习时间每学期约80小时。从2003届北京大学信息学院计算机专业的学生开始，《数据结构》将改为两门课程，即《算法与数据结构》和《数据结构实习》，在同一个学期讲授，分别为每学期3学分/每周3学时，每学期2学分/每周2学时。改革的目的主要是加强上机实践，每位学生的数据结构上机实习时间增加为每学期120小时。

数据结构是一门理论和实践结合比较紧密的课程，每周都布置6道书面作业或小程序实习（全学期约70道），每个学期布置6道大的上机实习题（其中最后一道是2-3人合作的学期综合上机实习题，例如“搜索引擎”、“XML数据管理”等）。组织助教认真检查习题和上机题，并编写了参考答案公布在网上。

4．采用新的教育技术，提高教学效果；

建立了一个高质量的课程网站https://www.docsj.com/doc/7a17898382.html,/mzhang/ds/index.htm。网站主要内容有：多媒体演示讲稿、标准C++模板编写的可执行的源程序代码、习题和上机题及其参考答案。课程网站还有一个BBS讨论版，每个学期都会有约700个数据结构主题讨论。教员每周都组织助教讲解习题中的问题和难点，并组织学生讨论习题和上机题中的问题、以及各种不同解法及其效率。

5．严格要求，教书育人，培养好学风。

为了防止学生抄袭上一届的作业和上机题，每一届都重新布置新的书面习题和上机题。另外，还要求学生在提交的书面作业、电子版程序和报告中，都写上“诚实代码”——“我XXX真诚地保证：我自己独立地完成了整个作业和程序从分析、设计到编码的所有工作。我没有抄袭任何其他人的作业。”学生纷纷反映这种自己以人格保证的形式，大大减少了抄袭现象。

五、结束语

作者试用第二版给电子商务学生授课，把最基本的内容安排在前6章讲解完，然后简单介绍了第7章的内排序，其他内容让感兴趣的学生自学。电子商务的学生们反映课程内容非常充实，知识点掌握得很牢固。在给北大信息学院计算机专业的二年级本科生试用第二版教材时，在接近一半的学期课程时间就讲完了前6章，重要的章节都可以安排比较综合的上机实习题；在开始讲解排序与检索的同时，可以开始安排学期综合上机实习题；最后第11-12章比较高级的数据结构内容只是讲座性的内容，没有上机实习的压力，而学生也面临期末考始复习了。从学生评估以及系领导对往届学生的调查情况来看，到了高年级以后，学生们都反映数据结构是知识拓展非常广、非常有用的课程。

作者希望，通过数据结构的学习，学生们能养成严谨的科学作风，学到科学的思维方法，提高设计高质量程序的能力，奠定扎实的软件开发基础。

北京大学

北京大学 中国第二届世界史研究生精品课程班 招生简章 一、宗旨 中国的快速崛起要求我们加强世界历史学科建设，这是国内知识界和教育界人士正在增加的共识。大家切身感受到，中国的快速崛起是一个世界性现象，也是一个历史现象。改变着世界秩序，也改写着世界历史。无论是其产生的正面效应，还是面临的严峻挑战，对中国和世界来说都是一些前所未见的问题，需要从事基础学科研究的学者做出根本性回答。以研究人类历史发展进程和大国兴衰规律为己任的世界历史学科，应该回答这样的问题。但是，由于各种原因，中国世界历史教学和研究，已经严重落后于发达国家，越来越不适应中国国际地位快速提高的时代要求。因此，有计划培养中国新一代世界历史学者，成为当务之急。 国务院学位办公室从2003年开始，大力推出研究生教育创新工程，面向全国高校研究生举办“世界历史研究生精品课程班”，为完成这个任务提供了重要契机。作为中国世界历史学科重镇的北京大学历史学系，积极响应有关号召，在2003年成功举办“中国第一届世界历史研究生精品课程班”，在社会上引起较大反响，对有关高校的世界历史教学和科研，起了良好的推动作用。我系会商北京大学研究生院等单位，决定在今年暑假期间举办“中国第二届世界历史研究生精品课程班”，欢迎全国高等院校研究生报名参加。 二、特点 （1）本课程班授课教授质量高：将在继承我国世界史人才培养优良传统，注重基本理论、基础知识和基本素质培养之基础上，强调教学内容的前沿性、科学性和国际性。依托北京高校和科研机构雄厚的研究力量，并邀请全国和欧美国家的著名教授前来授课。

（2）本课程班创新点多：教育观念创新：开门办学，邀集海内外一流教授，培育全国最优秀研究生，注意招收“西、少、边”地区院校研究生；教育体制创新：打破师生单位所有制，实现教育资源共享；教学内容创新：安排成组重点专题，方便学生在比较的视野中深化思考；授课方法创新：用最短时间把有关专题的前沿和精髓介绍给学生，并为学生留出时间和授课教授进行切磋。 （3）本课程班学员在学习期间，可以利用北京大学图书馆和北京大学历史学系图书和信息资源。 （4）本课程班欢迎旁听，不收取费用。 三、授课计划 本届课程班开设“美国历史与国际关系研究”和“欧洲研究与史学理论”两组专题，每个专题14讲，共计28讲，每讲4个小时，有关主持人和主讲教授如下： 第一组专题：“美国历史与国际关系研究”（主持人：美国宾州印第安纳大学历史系王希教授） 王希——美国宾州印第安纳大学历史系教授、北京大学长江学者、北京大学 历史学系兼职教授（8讲） 1、“20世纪60年代以来美国史学的发展”(Trends and Challenges of the Study of American History since 1960s) 2、“人民主权” 思想的英国起源与美国的建立”(The English Origins of “Popular Sovereignty” and the Founding of Ameri can Republic) 3、“斯科特案与美国公民资格的种族化”(The Dred Scott Case and the Racialization of American Citizenship) 4、“美国内战与美国人历史记忆的政治”(The Civil War and the Politics of Americans’ Historical Memories) 5、“自由主义在美国历史中的转型”(Liberalism and Its Transformations in American History) 6、“美国历史上的国家建设”(1) (国家制度) (State-building in American History) 7、“美国历史上的国家建设”(2) (公民队伍与核心价值观) (Nation-building in American History) 8、“在全球化时代对美国史研究和教学的重新思考”(Rethinking the Study and Teaching of America in Global Perspective) 何顺果——北京大学历史学系教授（1讲，下同） “美利坚文明的历史起源” 资中筠——中国社会科学院美国研究所研究员、前所长

数据结构与算法-北大 HW11 B_B+树

北京大学信息学院2007年秋季学期《数据结构与算法A(实验班)》课程作业 张铭编写并发布 mzhang@https://www.docsj.com/doc/7a17898382.html, 第11次作业，12月17日（周一）课前提交，电子稿提交时间12月17日开课之前提交。 11.1 偶数阶的B 树插入上溢出时，中 位数有两个，需要注意采用统一的策略。例如，取第二个中位数， 即分裂后左(1)/2m ?????个关键码，右(1)/2m ?????； 或者取第一个中位数，分裂后左(1)/2m ????? 右(1)/2m ?????。请画出对右图的4阶B 树进行下来操作后的B 树。 (1) 分裂时采用第2个中位数为 分界码，请画出插入关键码113后的B 树；分析插入操作的访外次数。 (2) 分裂时采用第1个中位数为分界码，请画出插入关键码113后的B 树；分析插入操 作的访外次数。 (3) 在原树中删除关键码50；分析删除操作的访外次数（与1、2题无关，从根重新开 始操作）。 11.2 已知一组关键码为(20, 30, 50, 52, 60, 68, 70)，试依次插入关键码。 (1) 生成一棵3阶的B +树，画出插入所有关键码后B 树的结构。 (2) 画出删除50后的B + 状态，分析删除操作的访外次数。 11.3 假设一个数据文件每个记录对象需要占用128 字节（其中关键码占用4字节），且所 有记录均已按关键码有序地存储在主磁盘文件中。设磁盘页块大小为2048（= 2K ）字节，若主存中有12M 空间可以用来存储索引结构，索引项中每一个地址指针占8 字节。请简要回答以下问题（请写明你的计算过程）。 （1） 使用B 树索引，B 树的阶m 1最多可以为多少？4层m 1阶B 树，最多可以索引多 少字节的数据文件？ （2） 使用B +树索引，B +树的阶m 2最多可以为多少? （3） 假设B +树的叶层各结点链接成双链结构，B +树的叶结点阶m 2’可以跟内部结点不 一样，则阶m 2’为多少? （4） 在第(3)小题的基础上，计算4层B +树（内部结点为m 2阶，叶结点m 2’阶），最多 可以索引多少字节的数据文件？ （5） 假设尽量把B +树的头几层放入内存（本题规定不能超过12M ），那么给定关键码， 通过B +树查找到(4)小题中主数据文件的一个记录，最少几次访外？最多几次访 外？ 11.4 对于下面两种B +树，列表给出他们在1、2、3、4和5层（独根是一层树）的不同情 况下，能够存储的最大记录数和最小记录数。 (1) 对于教材定义那样的B +树，其内部结点阶为50，叶结点阶为50。 (2) 如讲义P89那样的混合型B +树，其内部结点阶为55，叶结点阶为25（叶结点除关 键码，还索引部分记录信息）。 4阶B 树

北京大学操作系统期末试题有答案

操作系统原理试题 一. 名词解释题 1. 中断—— 2. 进程控制块(PCB)――它是进程实体的一部分，是操作系统最重要的记录型数据结构, 是进程存在的唯一标识 3. 虚时钟 4. 段式管理 5. 文件控制块(FCB) 6. 对换(SWAPPING) 7. 系统调用 8. 绝对路径名 9. 特别文件 10.虚设备技术 11.管道 12.中断接收 13.恢复现场 14.页式管理 15.作业步 16.字符流文件 17.通道 18.页面淘汰 19.多道程序设计 20.死锁 21.当前目录 22.快表 23.作业调度 24.原语 25.中断屏蔽 26.地址映射 27.文件目录 28.死锁避免 29.原语 31. CPU 状态 32.虚存

二 . 填空题 1. 分时系统追求的目标是 __及时响应 ___. 2. 用户进程从目态 （常态）转换为管态 （特态）的唯一途径是 ___ 中断 ________ . 3. 从静态的观点看 , 操作系统中的进程是由程序段、数据和 __ 作业控制块 PCB__ 三 部分组成 . 4. 在系统内核中必须包括的处理模块有进程调度、原语管理和 __中断处理 __. 5. 批处理操作系统中 , 作业存在的唯一标志是 _作业控制块 PCB ___. 6. 操作系统中的一种同步机制 , 由共享资源的数据及其在该数据上的一组操作组成 , 该同步机制称为 _管程 ______________ . 7. 在可变分区存储管理中 , 为实现地址映射 , 一般由硬件提供两个寄存器 , 一个是基 址寄存器 , 另一个是 _限长寄存器 ___. 8. 联想寄存器 （相联存储器 ） 的最重要、最独到的特点是 _按内容并行查找 ___. 9. 在虚拟段式存储管理中 , 若逻辑地址的段内地址大于段表中该段的段长 , 则发生 __ 地址越界 __中断 . 10. 文件系统中若文件的物理结构采用顺序结构 , 则文件控制快 FCB 中关于文件的物 理位置应包括 ___ 首块地址和文件长度 _. 11. 在操作系统设计时确定资源分配算法 , 以消除发生死锁的任何可能性 , 这种解决死 锁的方法是 __死锁预防 __. 12. 选择对资源需求不同的作业进行合理搭配 , 并投入运行是由 _作业调度算法 ___来完 成的. 13. 实时系统应具有两个基本特征 : 及时性和 ___可靠性 ___. 14. 磁带上的文件只能采用 _顺序 ______ 存取方式 . 15. 不让死锁发生的策略可以分成静态和动态的两种 , 死锁避免属于 __动态的 ___. 16. 在 UNIX 系统中 , 文件分成三类 , 即普通文件 , 目录文件和 ___特殊文件 __. 17. 在磁盘调度策略中有可能使 I/O 请求无限期等待的调度算法是 __最短寻道时间优先 18. 进程获得了除CPU 外的所有资源,一旦获得CPU 即可执行,这时进程处于—就绪 _ 状态 . 19. ______________________________________________________ 为实现CPU 与外部设备的并行工作，系统必须引入一通道 ____________________________________ 硬件基础. 20. 操作系统为保证不经文件拥有者授权 , 任何其它用户不能使用该文件所提出的解决 措施是 ___文件保密 __. 21. 两个或两个以上程序在计算机系统中同处于开始和结束之间的状态 , 这就称为 __ 并发 ___. 33. 磁盘调度 34. 缓冲技术 36. 进程调度 37. 虚设备 39. 死锁预防 40. 临界资源 — 42. 交换技术 43. 互斥区 段时间内只允许一个进程访问的资源，也称为独立资源

高等代数-北京大学第三版--北京大学精品课程

第一学期第一次课 第一章 代数学的经典课题 §1 若干准备知识 1.1.1 代数系统的概念 一个集合，如果在它里面存在一种或若干种代数运算，这些运算满足一定的运算法则，则称这样的一个体系为一个代数系统。 1.1.2 数域的定义 定义（数域） 设K 是某些复数所组成的集合。如果K 中至少包含两个不同的复数，且K 对复数的加、减、乘、除四则运算是封闭的，即对K 内任意两个数a 、b （a 可以等于b ），必有 K b a b K ab K b a ∈≠∈∈±/0时，，且当，，则称K 为一个数域。 例1.1 典型的数域举例： 复数域C ；实数域R ；有理数域Q ；Gauss 数域：Q (i) = {b a +i |b a ,∈Q }，其中i =1-。 命题 任意数域K 都包括有理数域Q 。 证明 设K 为任意一个数域。由定义可知，存在一个元素0≠∈a K a ，且。于是 K a a K a a ∈= ∈-=10， 。 进而∈?m Z 0>, K m ∈+??++=111。 最后，∈?n m ,Z 0>， K n m ∈，K n m n m ∈-=-0。这就证明了Q ?K 。证毕。 1.1.3 集合的运算，集合的映射（像与原像、单射、满射、双射）的概念 定义(集合的交、并、差) 设S 是集合，A 与B 的公共元素所组成的集合成为A 与B 的交集，记作B A ?；把A 和B 中的元素合并在一起组成的集合成为A 与B 的并集，记做B A ?；从集合A 中去掉属于B 的那些元素之后剩下的元素组成的集合成为A 与B 的差集，记做B A \。 定义（集合的映射） 设A 、B 为集合。如果存在法则f ，使得A 中任意元素a 在法则f 下对应B 中唯一确定的元素（记做)(a f ），则称f 是A 到B 的一个映射，记为 ). (, :a f a B A f α→ 如果B b a f ∈=)(，则b 称为a 在f 下的像，a 称为b 在f 下的原像。A 的所有元素在f 下的像构成的B 的子集称为A 在f 下的像，记做)(A f ，即{}A a a f A f ∈=|)()(。 若,'A a a ∈≠?都有),'()(a f a f ≠ 则称f 为单射。若 ,B b ∈?都存在A a ∈，使得b a f =)(，则称f 为满射。如果f 既是单射又是满射，则称f 为双射，或称一一对应。 1.1.4 求和号与求积号 1．求和号与乘积号的定义. 为了把加法和乘法表达得更简练，我们引进求和号和乘积号。 设给定某个数域K 上n 个数n a a a ,,,21Λ，我们使用如下记号：

数据结构考试题8

要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。 一、单项选择题（选择最准确的一项，共15小题，每小题2分，共计30分） 1. 数据结构是指。 A. 一种数据类型 B. 数据的存储结构 C. 一组性质相同的数据元素的集合 D. 相互之间存在一种或多种特定关系的数据元素的集合 2. 以下算法的时间复杂度为。 void fun(int n) { int i=1,s=0; while (i<=n) { s+=i+100; i++; } } A. O(n) B. O(n) C. O(nlog2n) D. O(log2n) 3. 在一个长度为n的有序顺序表中删除其中第一个元素值为x的元素时，在查找元素x时采用二分查找方法，此时删除算法的时间复杂度为。 A. O(n) B. O(nlog2n) C. O(n2) D. O(n) 4. 若一个栈采用数组s[0..n-1]存放其元素，初始时栈顶指针为n，则以下元素x进栈的正确操作是。 A.top++;s[top]=x; B.s[top]=x;top++; C.top--;s[top]=x; B.s[top]=x;top--; 5. 设环形队列中数组的下标为0～N-1，其队头、队尾指针分别为front和rear（front 指向队列中队头元素的前一个位置，rear指向队尾元素的位置），则其元素个数为。 A. rear-front B. rear-front-1 C. (rear-front)％N+1 D. (rear-front+N)％N 6. 若用一个大小为6的数组来实现环形队列，队头指针front指向队列中队头元素的

北京大学1997硕士入学数据结构试题

北京大学1997硕士入学数据结构试题 1 （16分） 填空 ① 设只包含要根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数 为，最小结点数为。 ② 某二叉树结点的对称序序列为A，B，C，D，E，F，G，后序序列为B，D，C，A，F，G，E，则该二叉树结点的前序序列为，该二叉树对应的树林包括棵树。 ③ 求具有最小带权外部路径长度的扩充二叉树的算法称为算法，对于给出的一组权W={10，12，16，21，30}，通过该算法求出的扩充二叉树的带权外部路径长度为。 ④ 设有关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是；若采用以第一个元素为分界元素的快速排序法，则一趟扫描的结果是。 2 （10分） 请简要回答下列问题 ① 什么是抽象数据类型？试举一例说明之。 ② 什么是广义表？请简述广义表与线性表的主要区别。 3 （6分） 给定关键码序列（26，25，20，33，21，24，45，204，42，38，29，31），要用散列法进行存储，规定负载因子a=0.6。 ① 请给出除余法的散列函数。 ② 用开地址线性探查法解决碰撞，请画出插入所有的关键码后得到的散列表，并指出发生碰撞的次数。 4 （6分） 本题要求在检索各结点的概率不相等的条件下构造最佳二叉排序树。给出关键码集合 { B, E, H} key1 key2 key3

以及权的序列 ( 9 4 5 8 6 1 3) p1 p2 p3 q0 q1 q2 q3 请构造最佳二叉排序树。 5 （12分） ① 请画出往图1的5阶B-树中插入一个关键码390后得到的B-树，以及再删除关键码150后得到的B-树。 ② 包括n个关键码的m阶B-树在一次检索中最多涉及多少个结点？（要求写出推导过程） 图1 题5图 6 （10分） 如图2所示是一棵正在进行插入运算的AVL树，关键码70的插入使它失去了平衡，按照AVL树的插入方法，需要对它的结构进行调整以恢复平衡。 ①请画出调整后的AVL树。 ②假设AVL树用llink-rlink法存储，T是指向根结点的指针、请用PASCAL（或C）语句表示出这个高速的过程。 （说明：不必写出完整的程序，只需用几个语句表示出在本题所给的具体情况下调整过程中指针的变化。在调整过程中还有两个指针变量p和q可以使用）。

北大2015年秋季学期数据结构课程作业

2015年秋季学期《数据结构》课程作业 一. 单选题，每空有一个正确选择，请将正确的选择填在题号前边。（每空1分，共30分） 1.鼓励独立完成作业，严惩抄袭！数据的逻辑结构被形式地定义为B=(K,R),其中K 是 ____C__的有限集合，R是K上的___H___的有限集合。（第一章） a 存储 b 数据操作c数据元素d操作 e逻辑结构 f 映象 g算法h关系 2.以下关于算法的说法不正确的是____B _________。（第一章） a 一个算法应包含有限个步骤 b算法越简单越好 c算法中的所有操作都可以通过已经实现的基本操作运算有限次实现之 d算法中的每个步骤都能在有限时间内完成 3．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03， 07>，<03，08>，<03，09>}，则数据结构A是______B________。（第一章） a 线性结构 b 树型结构 c 物理结构 d 图型结构 4.下面程序段的时间复杂度为___C___（第一章） int sum=0; for(i=0; i

北大PKU 慕课 EDX 数据结构与算法 第七章图 quiz答案与解析

第七章树

PROBLEM 2 (1/1 分) 一个深度为h的满k叉树，最多有多少个结点？（独根树深度为0）There is a full k-ary tree, whose depth is h. How many nodes can it have at most? (The depth of a tree, which only has a root node, is 0.) k^(h-1) k^h (k^(h+1)-1)/(k-1) (k^(h+1)-1)/(k-1) - 正确 (k^h-1)/(k-1) Explanation 层数---节点数 number of levels---number of nodes 0---1 1---k 2---k^2 3---k^3 .... h---k^h 所以答案是： so, the answer is： 1+k+k^2+k^3+...+k^h = (k^(h+1)-1)/(k-1)

PROBLEM 3 (1/1 分) 2-3树是一种特殊的树，它满足两个条件： （1）每个内部结点有两个或三个子结点；（2）所有的叶结点到根的路径长度相同； 如果一棵2-3树有9个叶结点，那么它可能有_________个非叶结点。(多项) 2-3 tree is a special kind of tree, it satisfy: （1）Every internal node has 2 or 3 child nodes. (2)All the leaf nodes have the same length of the path to the root node. If a 2-3 tree has 9 leaf nodes, then it may have __________ non-leaf nodes.（There are more than one correct answers） 4, 7, - 正确 4 5 6 7 Explanation 倒数第二层若是3个结点，深度为2，加上根结点，一共4个非叶子结点。 倒数第二层若是4个结点，深度为3，倒数第三层（第二层）有2个结点，一共4+2+1=7个非叶子结点。 If the second level from the bottom has 3 nodes, the depth of tree will be 2, and the tree will has 4 non-leaf nodes, including the root node. If the second level from the bottom has 4 nodes, the depth of tree will be 3, the third level from the bottom will has 2 nodes, and the tree will has 4+2+1=7 non-leaf nodes

北京大学各院系课程设置一览

北京大学各院系课程设置一览 前言 很多同学希望了解在北京大学各院系的某个年级要学习哪些课程，但又不容易查到课程表。本日志充当搬运工作用，将各院系开设课程列于下方，以备查询。 查询前必读 注释： ※在课程名称后标注含义如下： 标注（必）表示此课程为专业必修课，是获得学士学位必须通过的课程； 标注（限）表示此课程为专业任选课（原称专业限选课），各院系规定需在所有专业任选课中选修足够的学分（通常为30~40）以获取学士学位； 标注（通）表示此课程为通选课，非本院系本科生可选修此类课程，并计入通选课所需总学分；通选课无年级限制； 标注（公）表示此课程为全校任选课（原称公共任选课），此类课程不与学位挂钩，公选课无年级限制。 标注（体）表示此课程为体育课，每名学生必须且仅能选修4.0学分体育课；男生必须选修“太极拳”，女生必须选修“健美操”。 ※实际上，多数专业必修课及专业选修课也没有年级限制。对应的年级是“培养方案”推荐的修该门课程的适当年级。 ※不开设任何专业必修课的院系为研究生院或其他不招收本科生的部门，如马克思主义学院、武装部等。 ※由于在某些院系下有不同专业方向，标注为必修课的课程可能并不对于所有学生均为必修（如外国语学院的各个语种分支）。相关信息请咨询相应院系教务。 ※多数课程可以跨院系选修，但可能需缴纳额外学费。 ※院系编号为学号中表示院系字段的数字，因院系调整原因，编号并不连续。“系”可能为院级单位，具体以相应主页标示为准。 ※课程名称后标注数字表示学分。一般情况下，对于非实验课及非习题课，每学分表示平均每周有一节50分钟时长课程，16-18周。 ※院系设置的课程不一定由本院系开设。 ※医学部课程仅包含在本部的课程内容。 ※本一览表不包括政治课、军事理论课、英语课、文科计算机基础、辅修及双学位课程。※本一览表不提供上课地点及主讲教师信息，请与相应院系教务联系。 001 数学科学学院 https://www.docsj.com/doc/7a17898382.html,/ 一年级秋季学期 数学分析（I）（必）5.0 数学分析（I）习题（必）0.0 高等代数（I）（必）5.0 高等代数（I）习题（必）0.0 几何学（必）5.0 几何学习题（必）0.0 一年级春季学期 数学分析（II）（必）5.0

北京大学数据结构与算法信科数算2007秋期末考试题

北京大学信息科学技术学院考试试卷 考试科目：数据结构与算法A 姓名： 学号： 考试时间： 2008年 1 月 9 日 教师: 张铭、赵海燕、王腾蛟、宋国杰 以下为试题和答题纸，共 4 页。 题号 一 二 三 四 五六 七 八 总分 分数 阅卷人

第 1 页 一、（共30分，每空3分）填空 1. 1．无向图G=(V , E)，其中：V={a, b, c, d, e, f}, E={(a, b), (a, e), (a, c), (b, e), (c, f), (f, d), (e, d)}，对该图进行深度优先遍历，得到的顶点序列正确的是____。 A ．a,b,e,c,d,f B ．a,c,f,e,b,d C ．a,e,b,c,f,d D ．a,e,d,f,c,b 2. 下图中的强连通分量的个数为________个。 3. 设有向图G 如下: 写出所有拓扑序列:___________________________________________ 添加一条弧________________________之后, 则仅有唯一的拓扑序列. 4. 请问下面哪些操作在已排序数据上实施比在无序的数据上快 ？ A ．找最小值 B. 计算算术平均值 C. 找中位数 D. 找出现次数最多的值 5. 序列{15，142，51，68，121，46，57，575，60，89，185 }按最低位优先法进 行基数排序，进行一次分配和收集后得到的序列 。 6. 设输入的关键码满足k 1>k 2>…>k n ，缓冲区大小为m ，用最小值堆进行置换-选择 排序方法可产生____个初始归并段。 7. 在包含n 个关键码的线性表中进行顺序检索，若检索第i 个关键码的概率为p i , 且 分布如下： n n n n p p p p 21,21,....,41,211121====?? 成功检索的平均检索长度是_______________。 8. 假设计算机系统有2048个字节的磁盘块，要存储的每一条记录中4个字节是关 键码，磁盘指针4个字节，64个字节是数据字段。记录已经排序，顺序地存储

各高校心理学精品课程(视频)集锦

各高校心理学精品课程（视频）集锦 ? ? ?北师大社会心理王芳 52:09播放: 33 ?? ? ? ?华东师范大学精品课程心理学导... 43:17 ?播放: 113 ?

? ? ?华东师范大学精品课程教育心理... 84:23 ?播放: 37 ? ? ? ?华东师范大学精品课程变态心理... 44:55 ?播放: 42 ? ? ?

?华东师范大学精品课程教育心理... 54:25 ?播放: 102 ? ? ? ?北京大学精品课程医学心理学—胡... 52:10 ?播放: 103 ? ? ? ?北京大学精品课程实验心理学—朱... 47:22 ?播放: 183 ? ? ?

?南京师范大学心理学史汪凤炎 46:46 ?播放: 16 ? ? ? ?华南师范大学精品课程教育心理... 67:09 ?播放: 46 ? ? ? ?华东师范大学精品课程实验心理... 40:44 ?播放: 24 ? ? ? ?华南师范大学教育心理学何先友 53:02

?播放: 79 ? ? ? ?3位心理学大师咨询录像C 合理... 29:48 ?播放: 41 ? ? ? ?3位心理学大师咨询录像 A罗杰斯 46:23 ?播放: 36 ? ? ?北京师范大学精品课程发展心理... 52:06 播放: 55 ?

? ? ? ?北京师范大学精品课程普通心理... 50:36 ? ?播放: 72 ? ? ? ?北京师范大学精品课程普通心理... 26:58 ?播放: 36 ? ? ? ?北京师范大学精品课程发展心理... 60:39 播放: 36 ? ?

北京大学数据结构基础-chap6

数据结构与算法(五) 张铭主讲 采用教材：张铭，王腾蛟，赵海燕编写 高等教育出版社，2008. 6 （“十一五”国家级规划教材） 张铭《数据结构与算法》

第五章 二叉树 ?二叉树的概念 ?二叉树的抽象数据类型?深度优先搜索 ?宽度优先搜索?二叉树的存储结构?二叉搜索树 ?堆与优先队列?Huffman树及其应用 H G E A B C D F I 第五章二叉树

第五章二叉树 5.4 二叉搜索树 二叉搜索树 ?Binary Search Tree （BST ） ?或者是一棵空树； ?或者是具有下列性质的二叉树： ?对于任何一个结点，设其值为K ?则该结点的左子树(若不空)的任意一个结点的值都小于K ；?该结点的右子树(若不空)的任意一个结点的值都大于K ；? 而且它的左右子树也分别为BST ?性质: 中序遍历是正序的（由小到大的排列） 15 1822 51 7 8921 3 488 60 93 35 17 65

BST 示意图 wim wen yum xul wul xal wan zol wil zom yo xem zi yon

检索19 1219 2251 7 8 9 2 1 3 4 88 60 93 35 16 6?只需检索二个子树之一 ?直到K被找到 ?或遇上树叶仍找不到，则不存在 5

二叉树 5.4 二叉搜索树 插入17 ?首先是检索，若找到则不允许插入?若失败，则在该位置插入一个新叶?保持BST性质和性能！ 1219 22 51 7 8 9 2 13 4 88 60 93 35 16 6 17 2’ 5

北京大学1997硕士入学数据结构试题

北京大学1997硕士入学数据结构试题

北京大学1997硕士入学数据结构试题 1 （16分） 填空 ① 设只包含要根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数 为，最小结点数 为。 ② 某二叉树结点的对称序序列为A，B，C，D，E，F，G，后序序列为B，D，C，A，F，G，E，则该二叉树结点的前序序列 为，该二叉树对应的树林包括棵树。 ③ 求具有最小带权外部路径长度的扩充二 叉树的算法称为算法，对于给出的一组权W={10，12，16，21，30}，通过该算法求出的扩充二叉树的带权外部路径 长度为。

④ 设有关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是；若采用以第一个元素为分界元素的快速排序法，则一趟扫描的结果 是。 2 （10分） 请简要回答下列问题 ① 什么是抽象数据类型？试举一例说明之。 ② 什么是广义表？请简述广义表与线性表 的主要区别。 3 （6分） 给定关键码序列（26，25，20，33，21，24，45，204，42，38，29，31），要用散列法进行存储，规定负载因子a=0.6。 ① 请给出除余法的散列函数。

② 用开地址线性探查法解决碰撞，请画出插入所有的关键码后得到的散列表，并指出发生碰撞的次数。 4 （6分） 本题要求在检索各结点的概率不相等的条件下构造最佳二叉排序树。给出关键码集合 { B, E, H} key1 key2 key3 以及权的序列 ( 9 4 5 8 6 1 3) p1 p2 p3 q0 q1 q2 q3 请构造最佳二叉排序树。 5 （12分）

部分大学精品课程网址

中山大学精品课程 https://www.docsj.com/doc/7a17898382.html,/sysujpkc/ 华南理工大学精品课程 https://www.docsj.com/doc/7a17898382.html,/course/ 上海交通大学课程中心 https://www.docsj.com/doc/7a17898382.html, 西北工业大学精品课程 https://www.docsj.com/doc/7a17898382.html,/ 厦门大学精品课程 https://www.docsj.com/doc/7a17898382.html,/ 清华大学精品课程 https://www.docsj.com/doc/7a17898382.html, 复旦大学精品课程 https://www.docsj.com/doc/7a17898382.html,/ 西安交通大学教育资源共享网 https://www.docsj.com/doc/7a17898382.html,/html/zhucaidan3.htm 大连理工大学精品课程 https://www.docsj.com/doc/7a17898382.html,/（非教育网访问入口：https://www.docsj.com/doc/7a17898382.html,/）华中科技大学精品课程 https://www.docsj.com/doc/7a17898382.html,/ 北京邮电大学精品课程（网络教学平台） https://www.docsj.com/doc/7a17898382.html,/superCourse/index.jsp 中国科学技术大学精品课程 https://www.docsj.com/doc/7a17898382.html,/jpkc/ 山东大学精品课程 https://www.docsj.com/doc/7a17898382.html,/jingpin.htm 中南大学精品课程 https://www.docsj.com/doc/7a17898382.html,/jpkc/ 重庆大学精品课程 https://www.docsj.com/doc/7a17898382.html,/eol/homepage/common/index_jpk.jsp 同济大学精品课程 https://www.docsj.com/doc/7a17898382.html,/Able.Acc2.Web/Page_ExcellentCourseAll.aspx 兰州大学精品课程 http://202.201.1.71/eol/homepage/common/index_jpk.jsp（新网站） http://202.201.1.71/jpk/（旧网站） 吉林大学精品课程 https://www.docsj.com/doc/7a17898382.html,/G2S/ShowSystem/CourseExcellence.aspx 对外经济贸易大学精品课程 http://202.204.171.11/jingpin/default.htm（教育网入口） https://www.docsj.com/doc/7a17898382.html,/jingpin/default.htm（公网入口） 北京大学精品课程 https://www.docsj.com/doc/7a17898382.html,/pkujpk/ 广东外语外贸大学精品课程 https://www.docsj.com/doc/7a17898382.html,/jwc/bestcourse/

北大数据结构课件,内部资料,精品

数据结构课程的知识体系和教学实践 张铭许卓群杨冬青唐世渭/文 一、数据结构知识体系 计算机科学已经深入应用到各个领域，不仅有效地解决了各种工程和科学计算中的数值计算问题，而且也有效地解决了许多文本处理、信息检索、数据库管理、图像识别、人工智能等非数值的数据处理问题。数据结构有助于程序员更有效地组织数据、设计高效的算法、完成高质量的程序以满足错综复杂的实际需要。 数据结构是计算机学科的重要分支研究领域。数据结构和算法在计算机学科中的地位十分重要，其他计算机科学领域及有关的应用软件都要使用到各种数据结构。数据结构是算法分析与设计、操作系统、软件工程、数据库概论、编译技术、计算机图形学、人机交互等专业基础课和专业课程的先行课程。语言编译要使用栈、散列表及语法树；操作系统中用队列、存储管理表及目录树等；数据库系统运用线性表，多链表及索引树等进行数据管理；而在人工智能领域，依求解问题性质的差异将涉及到各种不同的数据结构，如广义表，集合、搜索树及各种有向图等等。 美国IEEE和ACM的教学计划CC2001把《算法与数据结构》列入计算机以及信息技术相关学科专业的本科必修基础课程。在我国，《数据结构》已经作为理工科非计算机专业必修的信息技术基础课程之一。世界上许多科技人员对学习、研究数据结构都非常重视，对于从事计算机科学及其应用的科技工作者来说，数据结构更是必须透彻地掌握的重要基础。 1．数据的逻辑结构、存储结构和运算 从字面上来看，数据结构就是指数据间的相互关系。具体到计算机环境，谈到任何一种结构时，都自然地联系着作用在这种类型的数据上的运算（即函数），为了在计算机上执行这些运算，我们有必要把这些数据以某种方式存储在计算机中。因此，我们可以认为，所谓数据结构，就是由某种逻辑关系组织起来的一批数据，按一定的存储方法被存储于计算机中，并在这些数据上定义了一个运算的集合。也就是说，数据结构具有三个方面：数据的逻辑结构、数据的存储结构和数据的运算。 常见逻辑关系有：线性结构、树形结构、图结构和文件结构。其中，线性结构是最简单的数据结构，例如，程序设计语言中往往都会介绍的线性表（包括数组和链表）、栈、队列、向量、字符串等。其中，字符串就是每个结点都是单个字符的线性表。实际上多维数组和广义表也是线性结构的推广。另外，文件其本质也是线性结构，不过由于存储在外存中，对文件数据的访问速度非常慢，因此，仔细研究文件结构和基于文件的外排序也是很有必要的。二叉树和树是非常重要的数据结构，其应用十分灵活而广泛。二叉树可以看作是树的特例。例如，语言编译中要用到语法树，操作系统有目录树，数据库系统需要用索引树等进行数据管理，而在人工智能领域，需要用到搜索树等。许多真实世界的问题都可以图来抽象地定义。例如，一张交通图可以用数据结构的图来形象化地表示：用结点表示城市，用边表示连接城市的高速公路；Web网页的关系也可以表示为图：Web网页作为结点，网页之间的链接作为边。图是一种最通用的逻辑结构，实际上，图?树?二叉树?线性表。 常见的存储方法有：顺序方法、链接方法、索引方法、散列方法。其中，索引存储又分为线性和树形两种。文件结构的索引则往往用树形结构。 对于一种数据结构，往往需要定义一些运算。例如，建立数据结构、清除数据结构、

北京大学数据结构与算法2016-2017数据结构与算法final-ans

北京大学信息科学技术学院考试试卷考试科目：数据结构与算法A 姓名：学号： 考试时间： 2016 年 1 月 6 日任课教师: 以下为试题和答题纸(答案写在答题纸上)，包括本页共 6 页。

第一题填空题（每空1分，共8分） 1.设无向图G = (V,E)中V={1, 2, 3, 4, 5, 6, 7}，E={(1,2), (1,3), (2,3), (4,5), (3,6), (4,7), (5,7)}。则图G包含的不同生成森林的个数为_____9____。 注释：其中若两个生成森林的边集不同，则认为它们是不同的生成森林。2.若对下面的无向图以1为起点运行单源最短路径的Dijkstra算法，则在 Dijkstra算法的过程中，每一步依次被选出的顶点依次是 _1,2,4,3,7,5,6,8,9,10___。若忽略边权，以6为起点进行一次广度优先周游，将得到一棵广度优先搜索的生成树。设仅包含一个结点的树高度为1，则该生成树的高度为_3_，树的最深层结点集合为_1,5,7,10__。 第一空回答2,4,3,7,5,6,8,9,10也算对 3.用某种排序方法对序列（25, 84, 21, 47, 15, 27, 68, 35, 20）进行排序时，若序 列的变化情况如下，则所采用的排序方法为__快速排序__。 25, 84, 21, 47, 15, 27, 68, 35, 20 20, 15, 21, 25, 47, 27, 68, 35, 84 15, 20, 21, 25, 35, 27, 47, 68, 84 15, 20, 21, 25, 27, 35, 47, 68, 84 4.假设Shell排序的增量序列是(2k, 2k-1, … , 2, 1)，其中k=[log2 n]。若待排序序 列是正序的（已经排好）或逆序的，则Shell排序的时间复杂度分别是 __O(nlogn)_、O(nlogn)_。 各0.5分 5.设输入的关键码满足k1>k2>…>k n，缓冲区大小为m。在n=150, m=25的情况 下，用最小值堆进行置换-选择排序方法可产生初始归并段的个数为 ___6____。

数据结构与算法-北大 HW4 BST、堆、Huffman

第4次作业，10月15日9：00课间提交，电子稿提交时间10月15日8：00之前。 4.1 假设BST允许重复关键码，在插入关键码K时，找到同义词K’, 那么K插入在K’为根的右子树中，当作右子树中序周游的第一个结点。 编写一个递归函数printRange，传入一个BST的根，一个较小的值和一个较大的值，按照顺序打印出介于两个值之间的所有结点，并返回重复关键码数目。函数printRange应尽可能少地访问BST的结点。PrintRange的原型为： template int printRange(BinaryTreeNode *root, T min, T max); 注释：重复关键码数目作为函数值返回。1 1 1 2 2 2 3 5的重复关键码数目是6，打印“重复关键码1 1 1 2 2 2”。1 2 3 4 5返回0，打印“重复关键码集为空”。 4.2 除了查找、插入和删除操作以外，有的应用还需要合并和分裂操作，请实现下面三种操作： （1） C.ThreeWayJoin(A, x, B)： 构建C，C由原来在A和B中的元素以及元素x构成。假设A中元素的关键字小于x.key，B中元素的关键字大于x.key。最后将A和B设置为空。 （2） C.TwoWayJoin(A, B)： 构建C，C由原来在A和B中的元素构成。假设A中所有元素的关键字小于B中所有元素的关键字。最后将A和B设置为空。 （3） A.Split(i, B, x, C)： 分裂为三部分：B包含A中所有关键字小于i的元素；如果A含关键字为i的元素，则将该元素复制到x，并返回x的指针，否则返回0；C包含A中所有关键字大于i的元素。最后将A设置为空。 4.3定义：双堆是一棵完全二叉树。该树或者为空，或者满足下列性质： （1） 根结点不含元素。 （2） 左子树是最小堆。 （3） 右子树是最大堆。 （4） 若右子树不空，设i为左子树中的任意结点，j为右子树中的对应结点。若这样的j 不存在，则令j为右子树中对应i的父结点。结点i中的key小于或等于结点j中的key。 左下图是一个双堆。最小堆的根结点含5，最大堆的根结点含45。最小堆结点10与最大堆结点25对应。最小堆中结点9，在性质（4）中定义的结点j是最大堆中结点40。 根据双堆定义，在具有n个元素的双堆中（n > 1），最小元素在最小堆的根结点中，最大元素在最大堆的根结点中。若n = 1，则最小和最大元素相同，在最小堆的根结点中。 在左下图插入4，j指向双堆中的新结点，i为其最小堆中对应结点。为了满足性质（4），交换4和19，然后调整最小堆。