角的度量知识结构图

栈和队列习题答案

第三章栈和队列习题答案 一、基础知识题 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题： (1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈) (2)能否得到出栈序列1423和1432并说明为什么不能得到或者如何得到。 (3)请分析1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。 答：(1)出栈序列为：1324 (2)不能得到1423序列。因为要得到14的出栈序列，则应做Push(1),Pop(),Push(2),Push (3),Push(4),Pop()。这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。能得到1432的出栈序列。具体操作为：Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。 (3)在1，2 ，3 ，4 的24种排列中，可通过相应入出栈操作得到的序列是： 1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321 不能得到的序列是： 1423,2413,3124,3142,3412,4123,4132,4213,4231,4312 链栈中为何不设置头结点 答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。 循环队列的优点是什么如何判别它的空和满 答：循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何若只设尾指针呢答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。 指出下述程序段的功能是什么 (1) void Demo1(SeqStack *S){ int i; arr[64] ; n=0 ; while ( StackEmpty(S)) arr[n++]=Pop(S); for (i=0, i< n; i++) Push(S, arr[i]); } .. // 设Q1已有内容，Q2已初始化过 while ( ! QueueEmpty( &Q1) ) { x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); n++;} for (i=0; i< n; i++) { x=DeQueue(&Q2) ; EnQueue( &Q1, x) ; EnQueue( &Q2, x);} 答： (1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的

结构力学知识点复习过程

建筑物和工程设施中承受、传递荷载而起骨架作用的部分称为工程结构，简称为结构。 从几何角度来看，结构可分为三类，分别为：杆件结构、板壳结构、实体结构。 结构力学中所有的计算方法都应考虑以下三方面条件： ①力系的平衡条件或运动条件。 ②变形的几何连续条件。 ③应力与变形间的物理条件（或称为本构方程）。 结点分为：铰结点、刚结点。 铰结点：可以传递力，但不能传递力矩。 刚结点：既可以传递力，也可以传递力矩。 支座按其受力特质分为：滚轴支座、铰支座、定向支座、固定支座。 在结构计算中，为了简化，对组成各杆件的材料一般都假设为：连续的、均匀的、各向同性的、完全弹性或弹塑性的。 荷载是主动作用于结构的外力。 狭义荷载：结构的自重、加于结构的水压力和土压力。 广义荷载：温度变化、基础沉降、材料收缩。 根据荷载作用时间的久暂，可以分为：恒载、活载。 根据荷载作用的性质，可以分为：静力荷载、动力荷载。 结构的几何构造分析 在几何构造分析中，不考虑这种由于材料的应变所产生的变形。 杆件体系可分为两类： 几何不变体系------在不考虑材料应变的条件下，体系的位置和形状是不能改变的。 几何可变体系------在不考虑材料应变的条件下，体系的位置和形状是可以改变的。 自由度：一个体系自由度的个数，等于这个体系运动时可以独立改变的坐标的个数。 一点在平面内有两个自由度（横纵坐标）。 一个刚片在平面内有三个自由度（横纵坐标及转角）。 凡是自由度的个数大于零的体系都是几何可变体系。 一个支杆（链杆）相当于一个约束。可以减少一个自由度。 一个单铰（只连接两个刚片的铰）相当于两个约束。可以减少两个自由度。一个单刚结（刚性结合）相当于三个约束，可以减少三个自由度。 如果在一个体系中增加一个约束，而体系的自由度并不因而减少，则此约束称为多余约束。增加了约束，计算自由度会减少。因为w=s-n . 瞬变体系：本来是几何可变、经微小位移后又成为几何不变的体系称为瞬变体系。 实铰：两个刚片（地基也算一个刚片），如果用两根链杆给链接上，并且两根链杆能在其中一个刚片上交于一点，所构成的铰就叫实铰。 瞬铰：两个刚片（地基也算一个刚片），如果用两根链杆给链接上，两根链杆在两刚片间没有交于一点，而是在两根链杆的延长线上交于一点，从瞬时微小运动来看，这就是瞬铰了。两根链杆所起的约束作用等效于在链杆交点处上面放了一个单铰的约束作用。通常所起作用为转动。 截面上应力沿杆轴切线方向的合力，称为轴力。轴力以拉力为正。 截面上应力沿杆轴法线方向的合力称为剪力。剪力以绕微段隔离体顺时针转者为正。 截面上应力对截面形心的力矩称为弯矩。在水平杆件中，当弯矩使杆件下部受拉时，弯矩为正。 作轴力图和剪力图要注明正负号。作弯矩图时，规定弯矩图的纵坐标应画在受拉纤维一边，不注明正负号。 通常在桁架的内力计算中，采用下列假定： ①桁架的结点都是光滑的铰结点； ②各杆的轴线都是直线并通过铰的中心； ③荷载和支座反力都作用在结点上。 根据几何构造的特点，静定平面桁架可分为三类：简单桁架，联合桁架，复杂桁架。 在单杆的前提下，当结点无荷载作用时，单杆的内力必为零。此单杆称为零杆。 由链杆和梁式杆组成的结构，称为组合结构。 链杆只受轴力作用；梁式杆除受轴力作用外，还受弯矩和剪力作用。 三铰拱受力特点： ①在竖向荷载作用下，梁没有水平反力，而拱则有推力。 ②由于推力的存在，三铰拱截面上的弯矩比简支梁的弯矩小。弯矩的降低，使拱能更充分地发挥材料的作用。 ③在竖向荷载作用下，梁的截面内没有轴力，而拱的截面内轴力较大，且一般为压力。 合理拱轴线：在固定荷载作用下使拱处于无弯矩、无剪力、而只有轴力作用的轴线。 合理轴线：通常指具有不同高跨比的一组抛物线。 影响线 内力影响线：表示单位移动荷载作用下内力变化规律的图形。无论在剪力、弯矩、支座反力的影响线图中都需要标上正负号。影响线是研究移动荷载最不利位置和计算内力最大值（或最小值）的基本工具。 荷载：特定单位移动荷载P=1 固定、任意荷载最不利位置：如果荷载移动到某个位置，使某量Z达到最大值，则此荷载位置称为最不利位置。 影响线的一个重要作用，就是用来确定荷载的最不利位置。 定出荷载最不利位置判断的一般原则是：应当把数量大、排列密的荷载放在影响线竖距较大的部位。 计算结构的位移目的有两个： ①一个目的是验算结构的刚度，即验算结构的位移是否超过允许的位移限值。 ②另一个目的是为超静定结构的内力分析打下基础。 产生位移的原因主要有下列三种： ①荷载作用②温度变化和材料胀缩③支座沉降和制造误差 一组力可以用一个符号P表示，相应的位移也可用一个符号Δ表示，这种夸大了的力和位移分别称为广义力和广义位移。 图乘法的应用条件：①杆段应是等截面直杆段。②两个图形中至少应有一个是直线，标距y0 应取自直线图中。 互等定理包括四个普遍定理：①功的互等定理②位移互等定理 ③反力互等定理④位移反力互等定理。 3、对称结构就是指： ①结构的几何形式和支承情况对某轴对称。 ②杆件截面和材料性质也对此轴对称。（因而杆件的截面刚度EI对此轴对称） 4、对称荷载：对称荷载绕对称轴对折后，左右两部分的荷载彼此重合（作用点相对应、数值相等、方向相同） 反对称荷载：反对称荷载绕对称轴对折后，左右两部分的荷载正好相反（作用点相对应、数值相等、方向相反） 超静定结构有一个重要特点，就是无荷载作用时，由于其他因素（如：支座移动、温度改变、材料收缩、制造误差）的作用也可以产生内力。 超静定结构：由于其他因素（如：支座移动、温度改变、材料收缩、制造误差）的作用可以产生位移也可以产生内力。 静定结构：由于其他因素（如：支座移动、温度改变、材料收缩、制造误差）的作用可以产生位移但不能产生内力。 力法：多余未知力静定结构变形协调（位移相等） 位移法：结构独立结点位移（角、线位移）超静定单杆（是用位移表示的）平衡方程 2、系数EAi /Li是使杆端产生单位位移时所需施加的杆端力，称为杆件的刚度系数。 体系的自由度指的是确定物体位置所需要的最少坐标数目。 拱的基本特点是在竖向荷载作用下会产生水平支座反力。 .静定结构的特性：（1）静定结构的全部约束反力与内力都可以用静力平衡方程求得。（2）温度变化、支座位移不引起静定结构的内力。3)当一个平衡力系作用在静定结构的某一自身几何不变的杆上时，静定结构只在该力系作用的杆段内产生内力。(4).作用在静定结构的某一自身为几何不变的杆 段上的某一荷载，若用在该段上的一个等效 力系来代替，则结构仅在该段上的内力发生 变化，其余部分内力不变。 1.平面杆件结构分类？ 梁、刚架、拱、桁架、组合结构。 2.请简述几何不变体系的俩刚片规则。 两刚片用一个铰和一根不通过该铰链中心的链杆或不全交于一点也不全平行的三根链杆相联，则组成的体系是几何不变的，并且没有多余约束。 3.请简述几何不变体系的三刚片规则。 三刚片用不共线的三个铰两两相联或六根链杆两两相联，则组成的体系是几何不变体系，且没有多余约束。 4.从几何组成分析上来看什么是静定结构，什么是超静定结构？(几何特征) 无多余约束的几何不变体系是静定结构，有多余约束的几何不变体系是超静定结构，有几个多余约束，即为几次超静定。 5.静定学角度分析说明什么是静定结构，什么是超静定结构？ 只需要利用静力平衡条件就能计算出结构全部支座反力和构件内力的结构称为静定结构；全部支座反力和构件内力不能只用静力平衡条件确定的结构称为超静定结构。 6.如何区别拱和曲梁 杆轴为曲线且在竖向荷载作用下能产生水平推力的结构，称为拱；杆轴为曲线，但在竖向荷载作用下无水平推力产生，称为曲梁。 7.合理拱轴的条件？ 在已知荷载作用下，如所选择的三铰拱轴线能使所有截面上的弯矩均等于零，则此拱轴线为合理拱轴线。 仅供学习与参考

(完整版)非常实用的数据结构知识点总结

数据结构知识点概括 第一章概论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 数据结构的定义： ·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。 ·线性结构：多对多关系。 ·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。 ·链式存储结构：如链表。 ·索引存储结构：·稠密索引：每个结点都有索引项。 ·稀疏索引：每组结点都有索引项。 ·散列存储结构：如散列表。 ·数据运算。 ·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用的有：检索、插入、删除、更新、排序。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 ·结构类型：由用户借助于描述机制定义，是导出类型。 抽象数据类型ADT：·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。 算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。 评价算法的好坏的因素：·算法是正确的； ·执行算法的时间； ·执行算法的存储空间（主要是辅助存储空间）； ·算法易于理解、编码、调试。 时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。 渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O （n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。

知识结构图

九年级第六单元知识结构图 一、单元分析与提示 1.本单元共四篇文章，三篇史传篇幅较长，囊括了初中文言文学习的多种要求，五首词是古代诗词中的经典词作，从内容、风格、艺术上都各具典型性和代表性。 2.在本单元的学习过程中，学生不但可以积累重要的文言文知识，还可以增长历史知识并受到古人智慧、勇气和节操方面的感染和激励。 3.学习这个单元的内容，引导学生去同古人作心灵对话，理解他们特殊的思想情感，从这些历史资料中去发现和领会中华民族那种为追求理想、报效国家，而甘于“鞠躬尽瘁，死而后已”的传统精神，弘扬中华民族的传统美德。 4.指导学生用历史唯物主义观点去认识历史事件和历史人物，引导学生结合时代背景、社会风貌，体会历史人物的思想感情和历史作用，脱离特定环境审视人物的做法是不足取的。树立正确的偶像观、英雄观人生观和远大抱负；帮助学生学会运用历史唯物主义的观点和方法评价历史人物。 5.朗读在文言文的教学中具有特别重要的作用，因此，教学时应该采用多种朗读方式。如齐读、散读、个人朗读、分组朗读等方式，既加深学生对课文的理解，又让学生尽可能在课堂上识记相关名句。书读百遍，其义自见。 6.培养学生自主、合作、探究式学习，鼓励学生通过自己的思考，去掌握知识，掌握学习知识的方法。在教学中，可以让学生互相质疑，“有疑而问”或是“明知故问”，互相取长补短，从而掌握文章的大意，进一步熟悉学习文言文的方法。 二、单元教学目标 1.反复地诵读，熟悉并背诵重要的篇章，提高阅读能力，学会一些阅读技巧。 了解有关作者、文体及相关知识，积累文言词语，培养文言语感。 2.借助注释和工具书理解文意，进一步培养学生把文言文翻译成现代文的能力。 3.积累古今异义词，揣摩、品味精彩文句，提高语言运用能力。 4.欣赏古代诗词，体会作者表达的思想感情，并与作者产生思想共鸣。 5.从文章中学到历史人物的勇气、魄力和智慧，并从他们身上汲取精华，传承美德，砥砺意志，自强不息。 三、单元教学重点 1.了解一些文学常识及中国几大历史著作的有关知识。 2.反复地诵读，熟悉并背诵重要的篇章，提高阅读能力，学会一些阅读技巧。 3.培养学生把文言文翻译成现代文的能力。掌握文言实词和虚词。 4.欣赏古代诗词，体会作者表达的思想感情，并与作者产生思想共鸣。 四、单元教学难点 1.学生对特定的历史背景难以理解。 2.对古今异义词的理解和掌握有较大的难度，应重点训练。 3.文言文的一些语法知识与现代文的有所不同，学生难以理解和把握。 4.指导学生，从文章中学到历史人物的勇气、魄力和智慧，并受到思想教育。 五、单元教学设想 1.熟读成诵法：古代诗文教学中，诵读是十分关键的环节，学生能流畅诵读，对课文内容才能真正掌握，而且诵读本身就能够使学生感受到作品的美，受到美的熏陶和感染。 2.疏通文意法：借助注释和工具书掌握浅显的文言词语，归纳积累重要词语，掌握疏通文言文内容的技巧和方法。

数据结构复习要点(整理版).docx

第一章数据结构概述 基本概念与术语 1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。 2. 数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。 (补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 ) 3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。(有时候也 叫做属性。) 4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 (1)数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。 数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。 依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种： 1. 集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。 2. 线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。 3. 树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素 (根)之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。 4. 图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个(或零个)直接后继。 (2)数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构： 1. 顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。 2. 链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。 5. 时间复杂度分析：1.常量阶：算法的时间复杂度与问题规模n 无关系T(n)=O(1) 2. 线性阶：算法的时间复杂度与问题规模 n 成线性关系T(n)=O(n) 3. 平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++ 时间复杂度的大小比较： O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n )

结构力学主要知识点归纳

结构力学主要知识点 一、基本概念 1、计算简图：在计算结构之前，往往需要对实际结构加以简化，表现其主要特点，略去其次要因素，用一个简化图形来代替实际结构。通常包括以下几个方面： A 、杆件的简化：常以其轴线代表 B 、支座和节点简化： ①活动铰支座、固定铰支座、固定支座、滑动支座； ②铰节点、刚节点、组合节点。 C 、体系简化：常简化为集中荷载及线分布荷载 D 、体系简化：将空间结果简化为平面结构 2、结构分类： A 、按几何特征划分：梁、拱、刚架、桁架、组合结构、悬索结构。 B 、按内力是否静定划分： ①静定结构：在任意荷载作用下，结构的全部反力和内力都可以由静力平衡条件确定。 ②超静定结构：只靠平衡条件还不能确定全部反力和内力，还必须考虑变形条件才能确定。 二、平面体系的机动分析 1、体系种类 A 、几何不变体系：几何形状和位置均能保持不变；通常根据结构有无多余联系，又划分为无多余联系的几何不变体系和有多余联系的几何不变体系。 B 、几何可变体系：在很小荷载作用下会发生机械运动，不能保持原有的几何形状和位置。常具体划分为常变体系和瞬变体系。 2、自由度：体系运动时所具有的独立运动方程式数目或者说是确定体系位置所需的独立坐标数目。 3、联系：限制运动的装置成为联系（或约束）体系的自由度可因加入的联系而减少，能减少一个自由度的装置成为一个联系 ①一个链杆可以减少一个自由度，成为一个联系。②一个单铰为两个联系。 4、计算自由度：)2(3r h m W +-=,m 为刚片数，h 为单铰束，r 为链杆数。 A 、W>0,表明缺少足够联系，结构为几何可变； B 、W=0，没有多余联系； C 、W<0,有多余联系，是否为几何不变仍不确定。 5、几何不变体系的基本组成规则： A 、三刚片规则：三个刚片用不在同一直线上的三个单铰两两铰联，组成的体系是几何不变的，而且没有多余联系。 B 、二元体规则：在一个刚片上增加一个二元体，仍未几何不变体系，而且没有多余联系。 C 、两刚片原则：两个刚片用一个铰和一根不通过此铰的链杆相联，为几何不变体系，而且没有多余联系。 6、虚铰：连接两个刚片的两根链杆的作用相当于在其交点处的一个单铰。虚铰在无穷远处的体系分析可见结构力学P20，自行了解。 7、静定结构的几何构造为特征为几何不变且无多余联系。 三、静定梁与静定钢架 1、内力图绘制： A 、内力图通常是用平行于杆轴线方向的坐标表示截面的位置，用垂直于杆轴线的坐标表示

第3章 栈和队列

《数据结构》 第3章栈和队列 共85题 一、单选 1. (1)分题目ID号：10705 题目难度：容易 设对一组数据的处理具有“后进先出”的特点，则应采用的数据结构是【1】 A. 队列 B. 栈 C. 顺序表 D. 二叉树题目答案：B 2. (1)分题目ID号：10706 题目难度：容易 若进栈序列为3、5、7、9，进栈和出栈可穿插进行，则不可能的出栈序列是【1】 A. 7，5，3，9 B. 9，5，7，3 C. 9，7，5，3 D. 7，5，9，3 题目答案：B 3. (1)分题目ID号：10707 题目难度：较难 设用一维数组A[m]存储栈，令A[m-1]为栈底，t指示当前栈顶的位置。如果栈不空，则出栈时应使【1】 A. t=t+l B. t=t-1 C. t=m-1 D. 不改变t 题目答案：A 4. (1)分题目ID号：10708 题目难度：容易 设用一维数组A[m]存储栈，令A[0]为栈底，top指示当前钱顶的位置，当把栈清空时所要执行的操作是【1】 A. top-- B. top=0 C. top=-1 D. top=m-1 题目答案：C 5. (1)分题目ID号：10709 题目难度：容易 设栈s的初始状态为空，如果进栈序列为1、2、3、4、5、6，出栈序列为3、2、5、6、4、1，则s的容量至少是【1】 A. 6 B. 4 C. 2 D. 3 题目答案：D 6. (1)分题目ID号：10710 题目难度：容易 设栈s最多能容纳4个元素，现有A、B、C、D、E、F六个元素按顺序进栈，以下可能的出栈序列是【1】 A. E、D、C、B、A、F B. B、C、E、F、A、D C. C、B、E、D、A、F D. A、D、F、E、B、C 题目答案：C

圆中知识结构图

关于《圆》的知识结构整理 一．主要定理及其作用： 1．圆心角, 弧,弦,弦心距之间的关系定理: 在同圆或等圆中,如果①两个圆心角②两条弧,③两条弦④两条弦心距中,有一组量相等,那么它们所对应的其余各组量都分别相等：（等弧---等角---等弦……） 用的最多的依据： ①在同圆或等圆中,如果两个圆心角相等,那么它们所对的两条弧相等 ②等弧所对的圆心角相等： ③在同圆或等圆中,如果两条弦相等,那么它们所对的两条弧相等 ④等弧所对的两条弦相等 2．垂径定理: 如果一条直线①过圆心；②垂直于弦；③平分弦；④平分劣弧；⑤平分优弧.只要具备其中两个条件,就可推出其余三个结论. （直角三角形---等弧……）用的最多的依据： ①垂直于弦的直径平分弦,并且平分弦所的两条弧 ②平分弦(非直径)的直径垂直于这条弦,并且平分这条弦所对的两条弧. ③一条弦的垂直平分线||经过圆心，并且平分这条弦所对的两条弧 ④平分弧的直径过圆心的直线垂直平分这条弧所对的弦. 3．圆周角定理: (1)直径所对的圆周角是直角； (2)90°的圆周角所对的弦是直径。 (3)一条弧所对的圆周角等于它所对的圆心角的一半； (4)同弧所对的圆周角相等； (5)等弧所对的圆周角相等； (6)在同圆或等圆中，相等的圆周角所对的弧相等； （等弧---等角---直角三角形） 4．切线的性质定理： 圆的切线垂直于经过切点的半径（直径）。(垂直关系) 5．切线的判定定理： 经过半径的外端，并且垂直于这条半径的直线是圆的切线。 6．切线长定理： 从圆外一点引圆的两条切线，它们的切线长相等，这一点和圆心的连线平分两条切线的夹角。（等弦---等弧---等角） 7．相切和相交两圆的性质定理： 如果两圆相切，连心线必过切点。如果两圆相交，连心线垂直平分公共弦 二．主要辅助线及其作用： 1．作弦心距：弦的中点．弧的中点。 2．过某一点作弦：构造相等的圆周角。 3．作直径：构造直角三角形和同弧所对的圆周角。 4．连结过切点的半径：“题中若有圆切线圆心切点连一连”。 5．两圆相切和两圆相交时，作连心线和公共弦。

数据结构复习提纲(整理)

复习提纲 第一章数据结构概述 基本概念与术语（P3） 1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2．数据元素是数据的基本单位 3．数据对象相同性质的数据元素的集合 4．数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. （1）数据的逻辑结构指数据元素之间固有的逻辑关系. （2）数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释：数据结构、二元组 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i

结构力学各章重要内容、知识点、难点

结构力学各章重要内容、知识点、难点 1、绪论 知识点：结构和结构的分类，结构力学的任务，结构的计算简图与杆件结构分类，荷载的分类。 重点：结构的计算简图选择原则、简化要点，结点和支座的变形和受力特性。难点：活载，铰结点、刚结点、组合结点的特点。 2、平面体系的几何组成分析 知识点：自由度、约束、瞬铰、多余约束等概念, 体系自由度计算公式，平面几何不变体系的组成规则，瞬变体系的特性，静定、超静定结构的几何 组成。 重点：应用平面几何不变体系的组成规则分析平面杆系的几何组成。 难点：复杂平面杆系的几何分析。 3、静定梁和静定刚架 知识点：截面法计算指定截面的内力，利用微分关系作内力图，分段迭加法画弯矩图，简支斜梁的计算，多跨静定梁的组成特点及计算。静定平面刚 架的特点、几何组成及型式，反力的计算，内力的计算和内力图的绘制， 内力图的校核。 重点：分段迭加法画弯矩图；多跨静定梁反力、内力的计算及内力图绘制；静定平面刚架内力的计算和内力图。 难点：简支斜梁的计算；已知弯矩图，绘制剪力图、轴力图。 4、三铰拱 知识点：三铰拱的组成和类型，三铰拱的反力和内力，三铰拱的受力特点，合理轴线。 重点：三铰拱的反力和内力计算。 难点：三铰拱截面剪力和轴力的计算。 5、静定桁架和组合结构 知识点：桁架的特点和组成分类，结点法、截面法和联合法求桁架内力，组合结构的内力计算。 重点：特殊杆内力判断，结点法、截面法和联合法求桁架内力，组合结构的内力计算。 难点：复杂桁架内力计算，组合结构中梁式杆的弯矩图。 6、虚功原理和结构位移计算 知识点：位移计算的目的；变形体系的虚功原理；结构位移计算的一般公式； 静定结构在荷载作用下的位移计算；图乘法；静定结构由于温度变化 及支座移动下的位移计算；线弹性结构的互等定理。 重点：静定结构在荷载作用下的位移计算。 难点：图乘法。 7、力法 知识点：超静定结构和超静定次数，力法的基本结构、基本未知量、及其物理意义，利用对称性简化力法计算，超静定结构位移的计算。 重点：根据力法基本方程物理意义列各类结构在各种外界因素作用时的基本方程并计算内力和位移，对称结构取“半边结构”。 难点：支座移动时的力法计算，计算超静定结构位移时基本结构的选择，力法

数据结构第三章栈和队列3习题

第三章栈和队列试题 一、单项选择题 1.栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 2.当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时， 首先应执行（）语句修改top指针。 A. top++; B. top--; C. top = 0; D. top; 3.若让元素1,2,3依次进栈，则出栈次序不可能出现（）种情况。 A. 3, 2, 1 B. 2, 1, 3 C. 3, 1, 2 D. 1, 3, 2 4.在一个顺序存储的循环队列中，队头指针指向队头元素的（）位置。 A. 前一个 B. 后一个 C. 当前 D. 后面 5.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。 A. n-2 B. n-1 C. n D. n+1 6.从一个顺序存储的循环队列中删除一个元素时，需要（）。 A. 队头指针加一 B. 队头指针减一 C. 取出队头指针所指的元素 D. 取出队尾指针所指的元素 7.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front+1 == rear B. rear+1 == front C. front == 0 D. front == rear 8.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL 9.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一 个由指针s所指的结点，则应执行操作（）。 A. top->link = s; B.s->link = top->link; top->link = s; C. s->link = top; top = s; D. s->link = top; top = top->link; 10.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点， 并将被摘除结点的值保存到x中，则应执行操作（）。 A. x = top->data; top = top->link; B. top = top->link; x = top->data; C. x = top; top = top->link; D. x = top->data; 11.设循环队列的结构是 #define MaxSize 100 typedef int ElemType;

2021年自考02331数据结构重点总结最终修订

自考02331数据构造重点总结(最后修订) 第一章概论 1.瑞士计算机科学家沃思提出：算法+数据构造=程序。算法是对数据运算描述，而数据构造涉及逻辑构造和存储构造。由此可见，程序设计实质是针对实际问题选取一种好数据构造和设计一种好算法，而好算法在很大限度上取决于描述实际问题数据构造。 2.数据是信息载体。数据元素是数据基本单位。一种数据元素可以由若干个数据项构成，数据项是具备独立含义最小标记单位。数据对象是具备相似性质数据元素集合。 3.数据构造指是数据元素之间互有关系，即数据组织形式。 数据构造普通涉及如下三方面内容：数据逻辑构造、数据存储构造、数据运算 ①数据逻辑构造是从逻辑关系上描述数据，与数据元素存储构造无关，是独立于计算机。 数据逻辑构造分类：线性构造和非线性构造。 线性表是一种典型线性构造。栈、队列、串等都是线性构造。数组、广义表、树和图等数据构造都是非线性构造。 ②数据元素及其关系在计算机内存储方式，称为数据存储构造（物理构造）。 数据存储构造是逻辑构造用计算机语言实现，它依赖于计算机语言。 ③数据运算。最惯用检索、插入、删除、更新、排序等。 4.数据四种基本存储办法：顺序存储、链接存储、索引存储、散列存储 （1）顺序存储：普通借助程序设计语言数组描述。 （2）链接存储：普通借助于程序语言指针来描述。 （3）索引存储：索引表由若干索引项构成。核心字是能唯一标记一种元素一种或各种数据项组合。 （4）散列存储：该办法基本思想是：依照元素核心字直接计算出该元素存储地址。 5.算法必要满足5个准则：输入，0个或各种数据作为输入；输出，产生一种或各种输出；有穷性，算法执行有限步后结束；拟定性，每一条指令含义都明确；可行性，算法是可行。 算法与程序区别：程序必要依赖于计算机程序语言，而一种算法可用自然语言、计算机程序语言、数学语言或商定符号语言来描述。当前惯用描述算法语言有两类：类Pascal和类C。 6.评价算法优劣：算法"对的性"是一方面要考虑。此外，重要考虑如下三点： ①执行算法所耗费时间，即时间复杂性； ②执行算法所耗费存储空间，重要是辅助空间，即空间复杂性； ③算法应易于理解、易于编程，易于调试等，即可读性和可操作性。

大学数据结构期末知识点重点总结

第一章概论 1.数据结构描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作，涉及数据的逻辑结构、存储结构和运算 2.数据的逻辑结构是从具体问题抽象出来的数学模型，反映了事物的组成结构及事物之间的逻辑关系 可以用一组数据（结点集合K）以及这些数据之间的一组二元关系（关系集合R）来表示：(K, R) 结点集K是由有限个结点组成的集合，每一个结点代表一个数据或一组有明确结构的数据 关系集R是定义在集合K上的一组关系，其中每个关系r（r∈R）都是K×K上的二元关系 3.数据类型 a.基本数据类型 整数类型(integer)、实数类型(real)、布尔类型(boolean)、字符类型（char）、指针类型（pointer）b.复合数据类型 复合类型是由基本数据类型组合而成的数据类型；复合数据类型本身，又可参与定义结构更为复杂的结点类型 4.数据结构的分类：线性结构（一对一）、树型结构（一对多）、图结构（多对多） 5.四种基本存储映射方法：顺序、链接、索引、散列 6.算法的特性：通用性、有效性、确定性、有穷性 7.算法分析：目的是从解决同一个问题的不同算法中选择比较适合的一种，或者对原始算法进行改造、加工、使其优化 8.渐进算法分析 a．大Ο分析法：上限，表明最坏情况 b．Ω分析法：下限，表明最好情况 c．Θ分析法：当上限和下限相同时，表明平均情况 第二章线性表 1.线性结构的基本特征 a.集合中必存在唯一的一个“第一元素” b.集合中必存在唯一的一个“最后元素” c.除最后元素之外，均有唯一的后继 d.除第一元素之外，均有唯一的前驱 2.线性结构的基本特点:均匀性、有序性 3.顺序表 a.主要特性：元素的类型相同；元素顺序地存储在连续存储空间中，每一个元素唯一的索引值；使用常数作为向量长度 b. 线性表中任意元素的存储位置：Loc(ki) = Loc(k0) + i * L（设每个元素需占用L个存储单元） c. 线性表的优缺点： 优点：逻辑结构与存储结构一致；属于随机存取方式，即查找每个元素所花时间基本一样 缺点：空间难以扩充 d.检索：ASL=【Ο（1）】 e.插入：插入前检查是否满了，插入时插入处后的表需要复制【Ο（n）】 f.删除：删除前检查是否是空的，删除时直接覆盖就行了【Ο（n）】 4.链表 4.1单链表 a.特点：逻辑顺序与物理顺序有可能不一致；属于顺序存取的存储结构，即存取每个数据元素所花费的时间不相等 b.带头结点的怎么判定空表：head和tail指向单链表的头结点 c.链表的插入（q->next=p->next; p->next=q;）【Ο（n）】 d.链表的删除（q=p->next; p->next = q->next; delete q;）【Ο（n）】 e.不足：next仅指向后继，不能有效找到前驱 4.2双链表 a.增加前驱指针，弥补单链表的不足 b.带头结点的怎么判定空表:head和tail指向单链表的头结点 c.插入：（q->next = p->next; q->prev = p; p->next = q; q->next->prev = q;） d.删除：（p->prev->next = p->next; p->next->prev = p->prev; p->prev = p->next = NULL; delete p;） 4.3顺序表和链表的比较 4.3.1主要优点 a.顺序表的主要优点 没用使用指针，不用花费附加开销；线性表元素的读访问非常简洁便利 b.链表的主要优点 无需事先了解线性表的长度；允许线性表的长度有很大变化；能够适应经常插入删除内部元素的情况 4.3.2应用场合的选择 a.不宜使用顺序表的场合 经常插入删除时，不宜使用顺序表；线性表的最大长度也是一个重要因素 b.不宜使用链表的场合 当不经常插入删除时，不应选择链表；当指针的存储开销与整个结点内容所占空间相比其比例较大时，应该慎重选择 第三章栈与队列 1.栈 a.栈是一种限定仅在一端进行插入和删除操作的线性表；其特点后进先出；插入：入栈（压栈）；删除：出栈（退栈）；插入、删除一端被称为栈顶（浮动），另一端称为栈底（固定）；实现分为顺序栈和链式栈两种 b.应用： 1）数制转换 while (N) { N%8入栈； N=N/8;} while (栈非空){ 出栈； 输出；} 2）括号匹配检验 不匹配情况：各类括号数量不同；嵌套关系不正确 算法： 逐一处理表达式中的每个字符ch： ch=非括号：不做任何处理 ch=左括号：入栈 ch=右括号：if (栈空) return false else { 出栈，检查匹配情况， if (不匹配) return false } 如果结束后，栈非空，返回false 3）表达式求值 3.1中缀表达式： 计算规则：先括号内，再括号外；同层按照优先级，即先乘*、除/,后加+、减-；相同优先级依据结合律，左结合律即为先左后右 3.2后缀表达式： <表达式> ::= <项><项> + | <项><项>－|<项> <项> ::= <因子><因子> * |<因子><因子>/|<因子> <因子> ::= <常数> ?<常数> ::= <数字>|<数字><常数> <数字> ∷= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 3.3中缀表达式转换为后缀表达式 InfixExp为中缀表达式，PostfixExp为后缀表 达式 初始化操作数栈OP，运算符栈OPND； OPND.push('#'); 读取InfixExp表达式的一项 操作数：直接输出到PostfixExp中； 操作符： 当‘（’：入OPND; 当‘）’：OPND此时若空，则出错；OPND若 非空，栈中元素依次弹出，输入PostfixExpz 中，直到遇到‘（’为止；若为‘（’，弹出即 可 当‘四则运算符’：循环（当栈非空且栈顶不是 ‘（’&& 当前运算符优先级>栈顶运算符优先 级），反复弹出栈顶运算符并输入到 PostfixExp中，再将当前运算符压入栈 3.4后缀表达式求值 初始化操作数栈OP； while （表达式没有处理完) { item = 读取表达式一项; 操作数：入栈OP； 运算符：退出两个操作数， 计算，并将结果入栈} c.递归使用的场合：定义是递归的；数据结构是 递归的；解决问题的方法是递归的 2.队列 a.若线性表的插入操作在一端进行，删除操作 在另一端进行，则称此线性表为队列 b.循环队列判断队满对空： 队空：front==rear；队满： (rear+1)%n==front 第五章二叉树 1.概念 a. 一个结点的子树的个数称为度数 b.二叉树的高度定义为二叉树中层数最大的叶 结点的层数加1 c.二叉树的深度定义为二叉树中层数最大的叶 结点的层数 d.如果一棵二叉树的任何结点，或者是树叶， 或者恰有两棵非空子树，则此二叉树称作满二 叉树 e.如果一颗二叉树最多只有最下面的两层结点 度数可以小于2；最下面一层的结点都集中在 该层最左边的位置上，则称此二叉树为完全二 叉树 f.当二叉树里出现空的子树时，就增加新的、特 殊的结点——空树叶组成扩充二叉树，扩充二 叉树是满二叉树 外部路径长度E：从扩充的二叉树的根到每个 外部结点（新增的空树叶）的路径长度之和 内部路径长度I：扩充的二叉树中从根到每个内 部结点（原来二叉树结点）的路径长度之和 2.性质 a. 二叉树的第i层（根为第0层，i≥0）最多有 2^i个结点 b. 深度为k的二叉树至多有2k+1-1个结点 c. 任何一颗二叉树，度为0的结点比度为2的 结点多一个。n0 = n2 + 1 d. 满二叉树定理：非空满二叉树树叶数等于其 分支结点数加1 e. 满二叉树定理推论：一个非空二叉树的空子 树(指针)数目等于其结点数加1 f. 有n个结点（n>0）的完全二叉树的高度为 ?log2(n+1)?，深度为?log2(n+1)?? g. 对于具有n个结点的完全二叉树，结点按层 次由左到右编号，则有： 1) 如果i = 0为根结点；如果i>0，其父结点 编号是(i-1)/2 2) 当2i+1∈N，则称k是k'的父结点，k'是 的子结点 若有序对及∈N，则称k' k″互为兄弟 若有一条由k到达ks的路径，则称k是 的祖先，ks是k的子孙 2.树/森林与二叉树的相互转换 a.树转换成二叉树 加线: 在树中所有兄弟结点之间加一连线 抹线: 对每个结点，除了其最左孩子外， 与其余孩子之间的连线 旋转: 45° b.二叉树转化成树 加线：若p结点是双亲结点的左孩子，则将 的右孩子，右孩子的右孩子， 所有右孩子，都与p的双亲用线连起来 线 调整：将结点按层次排列，形成树结构 c.森林转换成二叉树 将各棵树分别转换成二叉树 将每棵树的根结点用线相连 为轴心，顺时针旋转，构成二叉树型结构 d.二叉树转换成森林 抹线：将二叉树中根结点与其右孩子连线，及 沿右分支搜索到的所有右孩子间连线全部抹 掉，使之变成孤立的二叉树 还原：将孤立的二叉树还原成树 3.周游 a.先根(次序)周游 若树不空，则先访问根结点，然后依次先根周 游各棵子树 b.后根(次序)周游 若树不空，则先依次后根周游各棵子树，然后 访问根结点 c.按层次周游 若树不空，则自上而下自左至右访问树中每个 结点 4.存储结构 “左子/右兄”二叉链表表示法：结点左指针指 向孩子，右结点指向右兄弟，按树结构存储， 无孩子或无右兄弟则置空 5. “UNION/FIND算法”（等价类） 判断两个结点是否在同一个集合中，查找一个 给定结点的根结点的过程称为FIND 归并两个集合，这个归并过程常常被称为 UNION “UNION/FIND”算法用一棵树代表一个集合， 如果两个结点在同一棵树中，则认为它们在同 一个集合中；树中的每个结点（除根结点以外） 有仅且有一个父结点；结点中仅需保存父指针 信息，树本身可以存储为一个以其结点为元素 的数组 6.树的顺序存储结构 a. 带右链的先根次序表示法 在带右链的先根次序表示中，结点按先根次序 顺序存储在一片连续的存储单元中 每个结点除包括结点本身数据外，还附加两个 表示结构的信息字段，结点的形式为: info是结点的数据；rlink是右指针，指向结点 的下一个兄弟；ltag是一个左标记，当结点没 有子结点（即对应二叉树中结点没有左子结点 时），ltag为1，否则为0 b. 带双标记位的先根次序表示法 规定当结点没有下一个兄弟（即对应的二叉树 中结点没有右子结点时）rtag为1，否则为0 c. 带双标记位的层次次序表示法 结点按层次次序顺序存储在一片连续的存储单 元中 第七章图 1.定义 a.假设图中有n个顶点，e条边： 含有e=n(n-1)/2条边的无向图称作完全图 含有e=n(n-1) 条弧的有向图称作有向完全图 若边或弧的个数e < nlogn，则称作稀疏图， 否则称作稠密图 b. 顶点的度(TD)=出度(OD)+入度(ID) 顶点的出度: 以顶点v为弧尾的弧的数目 顶点的入度: 以顶点v为弧头的弧的数目 c.连通图、连通分量 若图G中任意两个顶点之间都有路径相通，则 称此图为连通图 若无向图为非连通图，则图中各个极大连通子 图称作此图的连通分量 d.强连通图、强连通分量 对于有向图，若任意两个顶点之间都存在一条 有向路径，则称此有向图为强连通图 否则，其各个极大强连通子图称作它的强连通 分量 e.生成树、生成森林 假设一个连通图有n个顶点和e条边，其中n-1 条边和n个顶点构成一个极小连通子图，称该 极小连通子图为此连通图的生成树 对非连通图，则将由各个连通分量构成的生成 树集合称做此非连通图的生成森林 2.存储结构 a.相邻矩阵表示法 表示顶点间相邻关系的矩阵 若G是一个具有n个顶点的图，则G的相邻矩 阵是如下定义的n×n矩阵： A[i,j]=1，若(Vi, Vj)(或)是图G的边 A[i,j]=0，若(Vi, Vj)(或)不是图G的边 b.邻接表表示法 为图中每个顶点建立一个单链表，第i个单链表 中的结点表示依附于顶点Vi的边（有向图中指 以Vi为尾的弧）（建立单链表时按结点顺序建 立） 3.周游 a. 深度优先周游： 从图中某个顶点V0出发，访问此顶点，然后依 次从V0的各个未被访问的邻接点出发，深度优 先搜索遍历图中的其余顶点，直至图中所有与 V0有路径相通的顶点都被访问到为止 b. 广度优先周游： 从图中的某个顶点V0出发，并在访问此顶点之 后依次访问V0的所有未被访问过的邻接点，随 后按这些顶点被访问的先后次序依次访问它们 的邻接点，直至图中所有与V0有路径相通的顶 点都被访问到为止，若此时图中尚有顶点未被 访问，则另选图中一个未曾被访问的顶点作起 始点，重复上述过程，直至图中所有顶点都被 访问到为止 4.拓扑排序 拓扑排序的方法是：1）选择一个入度为0的顶 点且输出之 2）从图中删掉此顶点及所有的出边 3）回到第1步继续执行，直至图空或者图不空 但找不到无前驱（入度为0）的顶点为止 5.单源最短路径（Dijkstra算法） 6.每对顶点间的最短路径（Floyd算法） 7.最小生成树 a.Prim算法 b.Kruskal算法 c.两种算法比较：Prim算法适合稠密图， Kruskal算法适合稀疏图 第八章内排序 算法最大时间平均时间 直接插入排 序 Θ(n2) Θ(n2) 冒泡排序Θ(n2) Θ(n2) 直接选择排 序 Θ(n2) Θ(n2) Shell排序Θ(n3/2) Θ(n3/2) 快速排序Θ(n2) Θ(nlog n) 归并排序Θ(nlog n) Θ(nlog n) 堆排序Θ(nlog n) Θ(nlog n) 桶式排序Θ(n+m) Θ(n+m) 基数排序Θ(d·(n+r)) Θ(d·(n+r)) 最小时间S(n) 稳定性 Θ(n) Θ(1) 稳定 Θ(n) Θ(1) 稳定 Θ(n2) Θ(1) 不稳定 Θ(n3/2) Θ(1) 不稳定 Θ(nlog n) Θ(log n) 不稳定 Θ(nlog n) Θ(n) 稳定 Θ(nlog n) Θ(1) 不稳定 Θ(n+m) Θ(n+m) 稳定 Θ(d·(n+r)) Θ(n+r) 稳定 第十章检索 1.平均检索长度（ASL）是待检索记录集合中元 素规模n的函数，其定义为： ASL= Pi为检索第i个元素的概率;Ci为找到第i个元 素所需的比较次数 2.散列 a.除余法 用关键码key除以M(取散列表长度)，并取余 数作为散列地址 散列函数为：hash(key) ＝key mod M b.解决冲突的方法 开散列方法：把发生冲突的关键码存储在散列 表主表之外（在主表外拉出单链表） 闭散列方法：把发生冲突的关键码存储在表中 另一个位置上 c.线性探查 基本思想：如果记录的基位置存储位置被占用， 就在表中下移，直到找到一个空存储位置；依 次探查下述地址单元：d0+1，d0+2，...，m-1， 0，1，...，d0-1；用于简单线性探查的探查 函数是:p(K, i) = i d.散列表的检索 1.假设给定的值为K，根据所设定的散列函数h， 计算出散列地址h(K) 2. 如果表中该地址对应的空间未被占用，则检 索失败，否则将该地址中的值与K比较 3. 若相等则检索成功；否则，按建表时设定的 处理冲突方法查找探查序列的下一个地址，如 此反复下去，直到某个地址空间未被占用（可 以插入），或者关键码比较相等（有重复记录， 不需插入）为止 e.散列表的删除：删除后在删除地点应加上墓 碑（被删除标记） f.散列表的插入：遇到墓碑不停止，知道找到真 正的空位置 第十一章索引技术 1.概念： a.主码：数据库中的每条记录的唯一标识 b.辅码：数据库中可以出现重复值的码 2.B树 a.定义：B树定义：一个m阶B树满足下列条 件： (1) 每个结点至多有m个子结点； (2) 除根和叶外 其它每个结点至少有??个子结点； (3) 根结点至少有两个子结点 例外(空树，or独根) (4) 所有的叶在同一层,可以有??- 1到m-1个 关键码 (5) 有k个子结点的非根结点恰好包含k-1个关 键码 b.查找 在根结点所包含的关键码K1，…，Kj中查找给 定的关键码值(用顺序检索(key少)/二分检索 (key多))；找到：则检索成功;否则，确定要查 的关键码值是在某个Ki和Ki+1之间，于是取 pi所指结点继续查找;如果pi指向外部结点， 表示检索失败. c.插入 找到的叶是插入位置，若插入后该叶中关键码 个数