文档库 最新最全的文档下载
当前位置:文档库 › 数据结构问题解答

数据结构问题解答

数据结构问题解答
数据结构问题解答

数据结构问题解答

第一章绪论

一、基本问题解答:

1、什么叫数据结构?如何理解“数据结构”?如何树立数据结构的学习体系?

广义上的数据结构指的是:逻辑结构和物理结构。狭义上的数据结构专指逻辑结构,就是元素间的逻辑关系,主要类型有:集合型,线性结构,树型,图型!整个数据结构的课程就是围绕着以上几种数据类型展开的,加上基于这些结构的基本操作:插入,删除,查找,取元素,取长度等等。另外还有基于这些数据结构的较为复杂的算法:查找和排序。在严老师和其他很多的数据结构教材中都把查找和排序作为了一个独立的部分,这一部分实际上主要在探讨算法,而不在是结构本身了。算法的概念将在后面提到。

2、数据的物理结构和逻辑结构

定义数据结构,当计算机程序运行时,程序就按照定义给这些数据分配了空间。而数据定义,是在定义其逻辑结构。以链表为列,在实际定义时,一个个的结点,由于其指针域可以指向另一个结点,那么依靠这种指向关系,就可在逻辑上建立起一条链状结构!但是,在实际的程序执行时,是不会有这样的一条链的,而是通过在一个结点空间的某个空间内填入了下一个结点的地址!这样的每个有数据和地址的结点,才是其物理结构。

3、算法的概念、分析,算法时间复杂度的含义及分析

算法就是解决问题的方法或策略。一个算法好与坏的评价标准是:正确,可读,健壮,效率高,空间省!

设计算法时,应该按照严教材上关于类C(或类P)语言的描述来作,格式为:

status fun_name{

//算法说明

...

for{ .... };//典型功能及复杂语句后加注释

...

}//fun_name

注意写好注释!不求多,但求精

时间复杂度:分析算法效率的重要工具。主要是靠推算语句执行次频度而得来的。时间复杂度考查的是“某数量级”的概念,即:T(n)=O(f(n))中,存在正的常数C和n0,使得当n>=n0时,0<=T(N)<=C*F(N)

当空间复杂度为O(1)时,称算法为就地工作(原地工作)。

算法时间复杂度的分析:时间复杂度的分析说到底是分析当系统规模增大时,系统所耗费时间的数量级。数量级的定义见上。简而言之,2n^2,6n^2,n^2是同一数量级,因为由n^2可推出其它两个(常数相乘)。此外,当时间复杂度的公式中出现n的多项式时,应该以高阶为准。因为此时影响总体变化规律的是高阶项的值。在分析时间复杂度时,应该以程序或算法中执行次数最多的语句为准,通常情况下是最内层循环的时间复杂茺,最内层语句的执行次数计算出来后,取最高的次数,然后去掉该项中的常数因子即可。

空间复杂度的度量主要是看当系统规模n增大时,系统所占用的额外空间是否也在增大,按怎么的规律增大。如果没有增大,即额外空间始终是个常数,算法就是原地工作!

4、算法设计规范

1>在算法设计中,第一个牵涉到的概念是:算法说明。

它是写在过程或函数首部以下的注释内容。虽是注释内容,却是必不可少的。在测试中也占有相当大的作用。此说明主要包括:算法的功能,参数表中各参数的含义及输入输出定义;算法中引用了哪些全局变量或外部定义的变量,它们的作用,入口初值,以及应该满足哪些限制条件。如:链表是否带头结点,表中元素是否有序,如果有序是递增还是递减等等!必要时,算法说明还可用来陈述算法思想,采用的存储结构等。递归算法的说明特别重要,读者应该力求将它写为算法的严格定义。几个例子:

2.29procedure DifferenceSqlist(V AR a;Sqlist;b,c:Sqlist);

{删去增序顺序表中那些既在增序顺序表中B出现又在增序顺序表C中出现的元素}

2.33procedure Sqlistlinkedlist(V AR lc,ld,loinkedList;llinkedList);

{将线性表ll分割为3个循环链表lc,ld和lo,}

{其中每个循环链表只含一类字符,分别为['A'..'Z']、['0'..'9']和其它字符。}

2>注释与断言

在难懂的语句和关键的语句(段)之后加以注释可以大大提高程序的可读性。注释要恰当,并非越多越好;此外,注释句的抽象程度应略高于语句(段)。

断言是注释的一种特殊写法,它是一个逻辑谓词,陈述算法执行到此点时应满足的条件,即这种形式:当、、、时,、、。最重要的就是算法的入口断言与else 分支断言。如果算法不含有参数佥性检测的代码段,书写入口断言是最低限度的要求。

3>输入、输出

三种方式:

a、通过专门的输入/出语句:read,write,scanf,printf等

b、通过参数表中的参数传递

c、通过全局及外部变量

4>错误处理

三种处理方式:

a、error语句实现

b、通过函数返回错误代码或错误状态值

c、exit语句实现

提倡使用第二种方式来实现错误处理

5>语句的使用与算法结构

避免使用goto语句,算法结构结构应该同层次对齐,下一层向上一层缩进两格,并以适当的符号标识语句段的开始与结束:[],{ }

6>基本运算

未明确要求的,不得直接用教科书上的基本运算

非用不可的,要将这些基本运算的代码全部写出

7>几点建议

a、建议以图说明算法

b、建议在算法书写完毕后,用边界条件的值验证一下算法能否正确执行

5、类P与类C大比拼

许多朋友问我类P与类C有啥区别,哪个更好?考试的时候用哪个语言?其实,这些都是一些很基础的问题,不客气地说这是考研门外汉的问题。类P 较类C的教材版本出得早,在后期的类C版数据中省去了类P中的一些内容,比如:栈一章的递归到非递归的转化等。但并不能因此就说类C版要差,事实上,类C的更符合当前考试和应用的发展趋势,从整体认同度而言,个人建议还是用类C好一点,原因:一,C语言本身很灵活,程序简洁,是真正的程序员用的语言,更是一个计算机研究生必须掌握的;二,C语言本身在实际项目的应用中是一种通用语言,软件公司绝大多数是要精通VC的,学好C的DS其意义更深远一些。另外,考虑到考上后绝大多数研友都会被导师拉去作项目,而作项目时多用的也是C!三,就交流范围而言,现在计算机版里用C的人要多得多,所以,交流的机会应该要多一些,这样提高的也快些。四,其它原因。至于考试的时候用哪一个,应该以报考学校的要求为准,如果没有作要求的,请参照一下该校给出的历年题的标准答案是用哪种语言。当然,一般情况下,用两种语言都行,只要算法正确,就会得分。

下面,罗列一下类C与类P的不同:

---------------------------------------

|类P|类 C ---------------------------------------

类型定义|TYPE、、、RECORD、、、END|TYPEDEF、、、{、、、}

---------------------------------------

常量定义|CONST|#DEFINE

---------------------------------------

函数定义|PROC(或FUNC)名(参数)[] |STATUS(VOID)名(参数);{}

---------------------------------------

语句段|[、、、]|{、、、}

---------------------------------------

条件语句|IF、、THEN、、ELSE|IF()、、ELSE、、---------------------------------------

赋值语句|:=|=

---------------------------------------

比较运算|=|==

---------------------------------------

多分支语句|CASE变量名OF|SWITCH(表达式){

(只写一种)|值1:、、、|CASE值1:、、、、;

BREAK;

|、、、|、、、

|ELSE语句|DEFAULT:语句N +1

|ENDC;|}

---------------------------------------

循环语句|WHILE条件DO[、、、、]|WHILE条件{、、、}|REPEAT、、、UNTIL()|DO{、、、}WHILE ()

|FOR(初值)TO(终值)DO[语句]|FOR(初值;条件;表达式){语句}

---------------------------------------

出错处理|ERROR(‘错误’)|EXIT(出错代码)---------------------------------------

输入/出|READ,WRITE|SCANF,PRINTF ---------------------------------------

注释|{}|//

---------------------------------------

基本函数|MAX,MIN,ABS,EOF,EOLN,上下取整|上下取整分别为FLOOR,CEIL

---------------------------------------

逻辑运算|AND,OR,NOT,CAND,COR|&&,||,!

--------------------------------

-------

注:以上不同之处在具体算法中的体现,请参照教材P版P25页和C版P24页的对应算法。

二、本章习题集中常考及已考题

1.1相同

1.2相同

1.3相似

1.4无

1.5相似

1.6相似

1.7相似

1.8相似

1.9相似

1.10相同

1.11相似(时间复杂度的比较)

1.12相似(时间复杂度的比较)

1.13无

1.14相似于1.10

1.15无

三、本章例题及习题分析

由于本章较为简单,此部分省略。

数据结构--序言在可视化化程序设计的今天,借助于集成开发环境可以很快地生成程序,程序设计不再是计算机专业人员的专利。很多人认为,只要掌握几种开发工具就可以成为编程高手,其实,这是一种误解。要想成为一个专业的开发人员,至少需要以下三个条件:

能够熟练地选择和设计各种数据结构和算法。

至少要能够熟练地掌握一门程序设计语言。

熟知所涉及的相关应用领域的知识。

其中,后两个条件比较容易实现,而第一个条件则需要花相当的时间和精力才能够达到,它是区分一个程序设计人员水平高低的一个重要标志,数据结构贯穿程序设计的始终,缺乏数据结构和算法的深厚功底,很难设计出高水平的具有专业水准的应用程序。曾经有一本经典计算机专业书籍叫做《数据结构+算法=程序》,也说明了数据结构和算法的重要性。

《数据结构》是计算机科学与工程的基础研究之一,掌握该领域的知识对于我们进一步进行高效率的计算机程序开发非常重要。无论在中国还是在美国,《数据结构》一直是大学的计算机专业重要的专业基础课。例如,在著名的美国的加州大学伯克利分校(著名的BSD Unix的发源地,很多Unix操作系统由它派生而来或带有它的痕迹——例如FreeBSD、Sun公司的Solaris、IBM的AIX),就用一个学期开设《数据结构和算法》课程(在这之前,用一个学期开设《C++程序设计》课程)。

现行的中学相关的计算机教程或者是关于怎样使用Windows操作系统及其工具、或者是有关办公软件的使用,或者是打字教程。计算机对他们始终有一种神秘感,也许是理论导向吧,因为不可能每个人将来都成为计算机专业人员。

作为一个中学生,在学完C/C++以后,关键的问题是怎样熟练地应用和巩固。本网站希望能够结合《数据结构》和相关的数、理、化知识来巩固C/C++。其实《数据结构》并不难。可以说,数据结构贯穿于我们的数学课程之中,只是思考问题方法的不同。在大学的《数据结构》教程中,很多生僻的词语、晦涩难懂的语句,连大学生就感到望而生畏。本网站将集合小学和中学的数学、物理、化学教材,深入浅出地讲解这门课程。希望不但能够对学习电脑有所帮助,更希望能够对数理化的学习起到一个促进作用。

在学习《数据结构》之前,要求学生有C/C++基础。可以这样说,C/C++是其他程序设计语言的基础。掌握了C/C++,学习其他语言就会易如反掌。例如,

微软的MFC类库基于C++;ATL基于C++中的模板类;Java语言基于C++思想,其编程风格与C++差别很小;C++ Builder又是基于C++;Delphi中的有关对象的概念与C++中的对象几乎完全一致。C++相比其他语言具有与计算机硬件集合紧密、代码效率高,这是Java语言和其他高级语言所无法比拟的。这样,C/C++对于学习计算机系统结构有很大的好处。

第一章:概论(包括习题与答案及要点)

--------------------------------------------------------------------------------

本章的重点是了解数据结构的逻辑结构、存储结构、数据的运算三方面的概念及相互关系,难点是算法复杂度的分析方法。

需要达到<识记>层次的基本概念和术语有:数据、数据元素、数据项、数据结构。特别是数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。数据结构的两大类逻辑结构和四种常用的存储表示方法。

需要达到<领会>层次的内容有算法、算法的时间复杂度和空间复杂度、最坏的和平均时间复杂度等概念,算法描述和算法分析的方法、对一般的算法要能分析出时间复杂度。

--------------------------------------------------------------------------------

对于基本概念,仔细看书就能够理解,这里简单提一下:

数据就是指能够被计算机识别、存储和加工处理的信息的载体。

数据元素是数据的基本单位,有时一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。如整数这个集合中,10这个数就可称是一个数据元素.又比如在一个数据库(关系式数据库)中,一个记录可称为一个数据元素,而这个元素中的某一字段就是一个数据项。

数据结构的定义虽然没有标准,但是它包括以下三方面内容:逻辑结构、存储结构、和对数据的操作。这一段比较重要,我用自己的语言来说明一下,大家看看是不是这样。

比如一个表(数据库),我们就称它为一个数据结构,它由很多记录(数据

元素)组成,每个元素又包括很多字段(数据项)组成。那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从结点(其实也就是元素、记录、顶点,虽然在各种情况下所用名字不同,但说的是同一个东东)之间的关系来分析的,对于这个表中的任一个记录(结点),它只有一个直接前趋,只有一个直接后继(前趋后继就是前相邻后相邻的意思),整个表只有一个开始结点和一个终端结点,那我们知道了这些关系就能明白这个表的逻辑结构了。

而存储结构则是指用计算机语言如何表示结点之间的这种关系。如上面的表,在计算机语言中描述为连续存放在一片内存单元中,还是随机的存放在内存中再用指针把它们链接在一起,这两种表示法就成为两种不同的存储结构。(注意,在本课程里,我们只在高级语言的层次上讨论存储结构。)

第三个概念就是对数据的运算,比如一张表格,我们需要进行查找,增加,修改,删除记录等工作,而怎么样才能进行这样的操作呢? 这也就是数据的运算,它不仅仅是加减乘除这些算术运算了,在数据结构中,这些运算常常涉及算法问题。

弄清了以上三个问题,就可以弄清数据结构这个概念。

--------------------------------------------------------------------------------

通常我们就将数据的逻辑结构简称为数据结构,数据的逻辑结构分两大类:线性结构和非线性结构(这两个很容易理解)

数据的存储方法有四种:顺序存储方法、链接存储方法、索引存储方法和散列存储方法。

--------------------------------------------------------------------------------

下一个是难点问题,就是算法的描述和分析,主要是算法复杂度的分析

方法及其运用。首先了解一下几个概念。一个是时间复杂度,一个是渐近时间复杂度。前者是某个算法的时间耗费,它是该算法所求解问题规模n的函数,而后者是指当问题规模趋向无穷大时,该算法时间复杂度的数量级。

当我们评价一个算法的时间性能时,主要标准就是算法的渐近时间复杂度,因此,在算法分析时,往往对两者不予区分,经常是将渐近时间复杂度T(n)=O(f(n)简称为时间复杂度,其中的f(n)一般是算法中频度最大的语句频度。

此外,算法中语句的频度不仅与问题规模有关,还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。

常见的时间复杂度,按数量级递增排列依次为:常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。

时间复杂度的分析计算请看书本上的例子,然后我们通过做练习加以领会和巩固。

数据结构习题一

--------------------------------------------------------------------------------

1.1 简述下列概念:数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。

◆数据:指能够被计算机识别、存储和加工处理的信息载体。

◆数据元素:就是数据的基本单位,在某些情况下,数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。

◆数据类型:是一个值的集合以及在这些值上定义的一组操作的总称。

◆数据结构:指的是数据之间的相互关系,即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。

◆逻辑结构:指各数据元素之间的逻辑关系。

◆存储结构:就是数据的逻辑结构用计算机语言的实现。

◆线性结构:数据逻辑结构中的一类,它的特征是若结构为非空集,则该结构有且只有一个开始结点和一个终端结点,并且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。

◆非线性结构:数据逻辑结构中的另一大类,它的逻辑特征是一个结点可能有多个直接前趋和直接后继。

--------------------------------------------------------------------------------

1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。

◆例如有一张学生成绩表,记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。每个记录(有姓名,学号,成绩等字段)就是一个结点,对于整个表来说,只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录),其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构。

那么我们怎样把这个表中的数据存储到计算机里呢? 用高级语言如何表示各结点之间的关系呢? 是用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题,我们都是从高级语言的层次来讨论这个问题的。(所以各位赶快学C语言吧)。

最后,我们有了这个表(数据结构),肯定要用它,那么就是要对这张表中的记录进行查询,修改,删除等操作,对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。

--------------------------------------------------------------------------------

1.3 常用的存储表示方法有哪几种?

常用的存储表示方法有四种:

◆顺序存储方法:它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。

◆链接存储方法:它不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。

◆索引存储方法:除建立存储结点信息外,还建立附加的索引表来标识结点的地址。

◆散列存储方法:就是根据结点的关键字直接计算出该结点的存储地址。

--------------------------------------------------------------------------------

1.4 设三个函数f,g,h分别为f(n)=100n^3+n^2+1000 , g(n)=25n^3+5000n^2 ,

h(n)=n^1.5+5000nlgn 请判断下列关系是否成立:

(1) f(n)=O(g(n))

(2) g(n)=O(f(n))

(3) h(n)=O(n^1.5)

(4) h(n)=O(nlgn)

◆(1)成立。

◇这里我们复习一下渐近时间复杂度的表示法T(n)=O(f(n)),这里的"O"是数学符号,它的严格定义是"若T(n)和f(n)是定义在正整数集合上的两个函数,则T(n)=O(f(n))表示存在正的常数C和n0 ,使得当n≥n0时都满足0≤T(n)≤C·f(n)。"用容易理解的话说就是这两个函数当整型自变量n趋向于无穷大时,两者的比值是一个不等于0的常数。这么一来,就好计算了吧。第(1)题中两个函数的最高次项都是n^3,因此当n→∞时,两个函数的比值是一个常数,所以这个关系式是成立的。

◆(2)成立。

◆(3)成立。

◆(4)不成立。

--------------------------------------------------------------------------------

1.5 设有两个算法在同一机器上运行,其执行时间分别为100n^2和2^n,要使前者快于后者,n至少要多大?

◆15

◇最简单最笨的办法就是拿自然数去代呗。假定n取为10,则前者的值是10000,后者的值是1024,小于前者,那我们就加个5,用15代入得前者为22500,后者为32768,已经比前者大但相差不多,那我们再减个1,用14代入得,前者为19600,后者为16384,又比前者小了,所以结果得出来就是n至少要是15.

--------------------------------------------------------------------------------

1.6 设n为正整数,利用大"O"记号,将下列程序段的执行时间表示为n的函数。

1.6 设n为正整数,利用大"O"记号,将下列程序段的执行时间表示为n的函数。

(1) i=1; k=0

while(i{ k=k+10*i;i++;

} ◆T(n)=n-1

∴T(n)=O(n)

◇这个函数是按线性阶递增的

(2) i=0; k=0;

do{

k=k+10*i; i++;

}

while(i∴T(n)=O(n)

◇这也是线性阶递增的

(3) i=1; j=0;

while(i+j<=n)

{

if (ielse i++;

} ◆T(n)=n/2

∴T(n)=O(n)

◇虽然时间函数是n/2,但其数量级仍是按线性阶递增的。

(4)x=n; // n>1

while (x>=(y+1)*(y+1))

y++; ◆T(n)=n1/2

∴T(n)=O(n1/2)

◇最坏的情况是y=0,那么循环的次数是n1/2次,这是一个按平方根阶递增的函数。

(5) x=91; y=100;

while(y>0)

if(x>100)

{x=x-10;y--;}

else x++; ◆T(n)=O(1)

◇这个程序看起来有点吓人,总共循环运行了1000次,但是我们看到n 没有? 没。这段程序的运行是和n无关的,就算它再循环一万年,我们也不管他,只是一个常数阶的函数。

--------------------------------------------------------------------------------

1.7 算法的时间复杂度仅与问题的规模相关吗?

◆No,事实上,算法的时间复杂度不仅与问题的规模相关,还与输入实例中的元素取值等相关,但在最坏的情况下,其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时,一般就是以最坏情况下的时间复杂度为准的。

--------------------------------------------------------------------------------

1.8 按增长率由小至大的顺序排列下列各函数:2^100, (2/3)^n,(3/2)^n,n^n , , n! ,2^n ,lgn ,n^lgn, n^(3/2)

◇分析如下:2^100 是常数阶;(2/3)^n和(3/2)^n是指数阶,其中前者是随n的增大而减小的;n^n是指数方阶;√n 是方根阶, n! 就是n(n-1)(n-2)... 就相当于n次方阶;2^n 是指数阶,lgn是对数阶,n^lgn是对数方阶, n^(3/2)是3/2次方阶。根据以上分析按增长率由小至大的顺序可排列如下:

◆(2/3)^n < 2^100 < lgn < √n < n^(3/2) < n^lgn < (3/2)^n < 2^n < n! < n^n

--------------------------------------------------------------------------------

1.9 有时为了比较两个同数量级算法的优劣,须突出主项的常数因子,而将低次项用大"O"记号表示。例如,设T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n), T2(n)=

2.0nlgn-2n=2.0lgn+O(n), 这两个式子表示,当n足够大时T1(n)优于T2(n),因为前者的常数因子小于后者。请用此方法表示下列函数,并指出当n足够大时,哪一个较优,哪一个较劣?

函数大"O"表示优劣

(1) T1(n)=5n^2-3n+60lgn ◆5n^2+O(n) ◆较差

(2) T2(n)=3n^2+1000n+3lgn ◆3n^2+O(n) ◆其次

(3) T3(n)=8n^2+3lgn ◆8n^2+O(lgn) ◆最差

(4) T4(n)=1.5n^2+6000nlgn ◆1.5n^2+O(nlgn) ◆最优

第一章概论复习要点

本章的复习要点是:

数据、数据元素、数据结构(包括逻辑结构、存储结构)以及数据类型的概念、数据的逻辑结构分为哪两大类,及其逻辑特征、数据的存储结构可用的四种基本存储方法。

时间复杂度与渐近时间复杂度的概念,如何求算法的时间复杂度。

可能出的题目有选择题、填空题或简答题。如:

.........是数据的基本单位,.........是具有独立含义的最小标识单位。

什么是数据结构?什么是数据类型?

数据的............与数据的存储无关,它是独立于计算机的。

数据的存储结构包括顺序存储结构、链式存储结构.......................、...........................

设n为正整数,利用大O记号,将该程序段的执行时间表示为n的函数,则下列程序段的时间复杂度可表示为:(....)

x=91;y=100;

while(y>10)

if(x>100){x=x-10;y--;}

else x++;

A. O(1)

B.O(x)

C.O(y)

D.O(n)

等等。

顺便一提,基本概念和基本理论的掌握是得分的基本手段

数据结构与算法基础知识总结

数据结构与算法基础知识总结 1 算法 算法:是指解题方案的准确而完整的描述。 算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。 算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。特征包括: (1)可行性; (2)确定性,算法中每一步骤都必须有明确定义,不充许有模棱两可的解释,不允许有多义性; (3)有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止,包括合理的执行时间的含义; (4)拥有足够的情报。 算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构。 指令系统:一个计算机系统能执行的所有指令的集合。 基本运算和操作包括:算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构:顺序结构、选择结构、循环结构。 算法基本设计方法:列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度:算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面: (1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构; (2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;(3)对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含: (1)表示数据元素的信息; (2)表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件:

(1)有且只有一个根结点; (2)每一个结点最多有一个前件,也最多有一个后件。 非线性结构:不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构 线性表由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。 在复杂线性表中,由若干项数据元素组成的数据元素称为记录,而由多个记录构成的线性表又称为文件。 非空线性表的结构特征: (1)且只有一个根结点a1,它无前件; (2)有且只有一个终端结点an,它无后件; (3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。结点个数n称为线性表的长度,当n=0时,称为空表。 线性表的顺序存储结构具有以下两个基本特点: (1)线性表中所有元素的所占的存储空间是连续的; (2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为:adr(ai)=adr(a1)+(i-1)k,,adr(a1)为第一个元素的地址,k代表每个元素占的字节数。 顺序表的运算:插入、删除。(详见14--16页) 4 栈和队列 栈是限定在一端进行插入与删除的线性表,允许插入与删除的一端称为栈顶,不允许插入与删除的另一端称为栈底。 栈按照“先进后出”(filo)或“后进先出”(lifo)组织数据,栈具有记忆作用。用top表示栈顶位置,用bottom表示栈底。 栈的基本运算:(1)插入元素称为入栈运算;(2)删除元素称为退栈运算;(3)读栈顶元素是将栈顶元素赋给一个指定的变量,此时指针无变化。 队列是指允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。rear指针指向队尾,front指针指向队头。 队列是“先进行出”(fifo)或“后进后出”(lilo)的线性表。 队列运算包括(1)入队运算:从队尾插入一个元素;(2)退队运算:从队头删除一个元素。循环队列:s=0表示队列空,s=1且front=rear表示队列满

结构设计常见问题解答

结构设计常见问题解答

1.梁裂缝控制与粱端弯矩调幅矛盾的解答 2.次梁对整体刚度贡献与点铰接问题 3.位移比与周期比对扭转控制有什么区别 4.质疑:周期折减系数 5.为什么不用pkpm自动梁配筋,而是要对SATWE信息手动配筋 6.大小偏心柱与单双偏压问题 1、板厚一般怎么取,与跨度有什么关系? 2、布置梁的时候,一般梁与梁之间的间距多少经济?(包括次梁的) 3、住宅楼的梁高一般怎么取? 4、框架结构柱距多少较为经济? 5、纯框架结构适合的高度和层数? 6、框架柱的混凝土等级一般怎么取? 7、框架结构的变形特性? 8、混凝土中,温度收缩怎么处理? 9、剪力墙高宽比多少为宜? 10、剪力墙混凝土等级一般取多少? 11、合理的剪力墙数量? 12、框架结构合理的重量范围? 13、怎么估算柱子截面? 14、轴压比超了怎么调? 15、位移比不满足怎么调?

16、周期比不满足怎么调? 17、位移角不满足怎么调? 18、PKPM建模中怎么降板? 19、PKPM中板厚为零和房间开洞的区别? 20、PKPM中虚梁怎么建? 21、什么情况下点铰? 22、超筋了怎么处理? 23、基础设计时,什么情况下要输入详细的地质资料? 24、基础底标高怎么考虑? 25、活荷载折减在PKPM中折减怎么实现? 1. 梁裂缝控制与粱端弯矩调幅矛盾的解答 a支座弯矩调幅与截面裂缝宽度验算是一对矛盾,对支座调幅处理的目的是为适当减小支座弯矩,而对支座截面进行裂缝宽度计算往往又需要加大截面的配筋,从而又加大了支座截面的弯矩。支座不调幅时支座弯矩大,截面配筋大,裂缝宽度不能满足规范要求,及多配

常见结构的认识

常见结构的认识 第一单元结构与设计第一节常见结构的认识 (1) 一、教材分析 本课时内容是本单元的基础性知识,对后面的章节起着提纲挈领的作用。 第一小节“无处不在的结构”通过对自然界、技术领域和社会领域三个层面的分析,说明了结构无处不在,给出了结构的一般含义。教材特别强调了结构的多种多样决定了事物存在的性质,这个观点作为结构思想方法的重要组成部分,贯穿于这一章的始终。在这一节中,用“魁北克大桥的坍塌”为例说明合理结构的重要性,给学生以心灵的震撼,引起他们对结构的重视,提醒学生进行结构设计时要有高度的责任感。 第二小节“结构与力”从力学的角度让学生学习结构,并给出了结构的受力分析方法,由于受到学生的知识水平限制,教材只进行定性的分析,要求学生体验和学习力的分析方法。力的分析方法是这一小节的重点。 二、学情分析 通过系统的学习《技术与设计1》,学生对设计中的结构有了一定的感性认识,但对于结构的作用的认识还是比较模糊、零散的,因此,学生在学习人类如何利用自然界中的结构,解决实际生活中的一些技术问题时还存在一定的困难。在物理课程中,学生已经掌握了一定的力学知识,并可以画出一些简单物体的受力图,但对分析一些基本结构如何受力、构件内部产生的内力及单位横截面上所产生的应力还有一定的困难。 三、教学目标 1. 知识与技能目标 了解结构的含义,能举出不同领域的实例,知道结构无处不在。了解结构与力的关系。 2. 过程与方法目标 能够通过对简单案例,分析结构是如何承受力的。 3. 情感态度与价值观目标 通过案例分析,提高理解和分析问题的能力,培养全面、系统的分析问题的能力,激发学习激情和兴趣。 四、教学重点、难点 重点:结构的含义;结构决定事物存在的性质,结构受力的分析方法。 难点:结构受力的分析方法。 五、教学方法、策略 方法:案例分析法、讨论法、实践体验法 策略设计: (1)这两个小节的的教学要具备初中物理学科的基本力学知识,根据学生掌握程度的不同,建议在进行本节教学前先复习相关知识。 (2)本节内容与学生生活实际联系紧密,教师应有针对性的指导学生收集资料和实物素材,如案例、阅读材料、典型的结构设计实例等,为学生提供丰富的学习背景。其形式可以是挂图、多媒体课件或图片、视频等,以丰富和拓展本节单元教学的内容,激发学生学习兴趣。 (3)教学中先从世界上处处有结构讲起,自然界、社会领域、技术领域都有结构问题,并用具体案例来说明结构是如何决定事物性质的,接着再讲解人类是如何模拟自然结构来解决技术问题的,最后用“魁北克大桥的坍塌”来阐述进行结构设计要有强烈的责任感。不能将过多的精力花在社会领域结构的理解上,应以技术领域的结构为主要学习对象。 (4)指导好“魁北克大桥的坍塌”的阅读过程,同时可以补充一些类似的最近发生的例子,如地铁施工造成附近小区地面塌陷等。 (5) 在进行结构与力的教学时,结合学生比较熟悉的事物来讲解,例如,秋千的吊索主

苏教版化学高中《人类对原子结构的认识》word教案

第三单元人类对原子结构的认识 第一课时 教学目标: 1.知识目标:知道化学科学的主要研究对象,了解化学学科的发展趋势 通过原子结构模型演变的学习,了解科学家探索原子结构的艰难过程 了解钠、镁、氧等常见元素的原子的核外电子的排布情况 2.能力方法:知道原子在化学反应中常通过电子的得失使最外层达到稳定结构 通过氧化镁的形成了解镁与氧气发生化学反应的本质 3.情感态度:通过各种原子结构模型的学习,体验科学实验,科学思维对创造性 工作的重要作用 教学重点: 1.通过各种原子结构模型的发展演变,体验科学探索的艰难过程 2.理解镁和氧气发生化学反应的本质 教学难点:原子在化学反应中通过电子得失形成稳定结构 镁和氧气发生化学的本质 教学方法:阅读讨论法、讲授法、探究法、情感体验法 教学过程: 一、原子结构模型的演变 [阅读讨论] 1.阅读课本p26-27 2.讨论a.原子结构模型演变 b.科学探索的精神、严谨科学态度 实验在科学探究中重要性 3.讲授内容:体验科学探究对艰难过程 [科学探究] 1. 在原子结构模型的演变中,是什么让汤姆生、卢瑟福、玻尔等人否定前人的 科学的发展离子不开社会的进步,没有社会的进步,不可能造就出玻尔等伟大的科学家,没有ɑ粒子散射实验,不会有卢瑟福的含核模型诞生,没有氢原子光谱的实验,不会有玻尔的行星轨道式原子模型的诞生。

3. 原子结构模型的演变过程给我们的启迪 (1) 化学认识发展过程中的继承、积累、突破和革命。 (2) 实验方法是科学研究的一种重要方法,实验手段的不断进步是化学科学的关 键 (3) 科学研究、科学发现是无止境的。 二、核外电子排布 [阅读课本]:常见原子的核外电子排布 1. [拓展研究]核外电子排布规律:(1) 核外电子总是尽先排布在能量较低的电子层,然后由里向外,排布在能量逐步升高的电子层 (2) 原子核外各电子层最多容纳2n2个电子(表示电子层数)。 (3) 原子最外野电子数目不能超过8个(第一层不能超过2个) (4) 次外层电子数目不能超过18个(第一层为次外层时不能超过2个),倒数第三 层电子数目不能超过32个。 2.1-18号元素原子核外电子排布示意图 [迁移拓展] 活泼金属易失去电子形成稳定阳离子,活泼非金属易得到电子形成稳定阴离子 (1) 原子:核电荷数=核外电子数,如Na、Ca、Al、F、Cl、S等示意图。 (2) 阳离子:核电荷数>核外电子数,如Na+、Ca2+、Al3+等示意图。 (3) 阴离子:核电荷数<核外电子数,如F-、Cl-、S2-等示意图。 [问题解决] (1)内容见课本、同学交流讨论 (2)知识拓展元素化合价得失电子数目的关系 ①金属元素一般为正化合价,失去电子的数目即为化合价的数值,如Na、K失去最外层1个电子均为+1价,Mg、Ca失去最外层2个电子均为+2价,Al 失去最外层3个电子均为+3价。 ②非金属元素既可以为正化合价也可以为负化合价,活泼非金属元素的最低负化合价的数值即为得到电子的数目。如:F、Cl易得到1个电子,最低化合价均为-1价;O、S易得到2个电子,最低体例价均为-2价。 [小结] 1.原子结构模型的演变 2.化合价与核外电子排布 [练习]在1991年前后,物理学家卢瑟福把一束变速运动的ɑ粒子(质量为氢原子的4倍,带2个单位正电荷),射向一片极薄的金箔。他惊奇地发现,过去一直认为原子是“实心球”,而四这种“实心球”紧密排列而成的金箔,竟能让大多数ɑ粒子畅通无阻地通过,就像金箔不在那儿似的,但也有极少数ɑ粒子发生偏转,被笔直地弹回。根椐以上实验能得出关于金箔中金原子结构的一些结论。试写出其中的三点: (1) ; (2) ; (3) ;

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

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

结构设计常见问题问答

结构设计常见问题问答 1、住宅工程中顶层为坡屋顶,屋顶是否需设水平楼板?顶层为坡屋顶时层高有无限制?总高度应如何计算? 住宅工程中的坡屋顶,如不利用时檐口标高处不一定设水平楼板。关于顶层为坡屋顶时层高的计算问题新规范未做具体规定,结构设计时由设计人员根据实际情况而定,取质点的计算高度仍不超过4m.檐口标高处不设水平楼板时,按抗震规范,总高度可以算至檐口(此处檐口指结构外墙体和屋面结构板交界处的屋面结构板顶)。檐口标高附近有水平楼板,且坡屋顶不是轻型装饰屋顶时,上面三角形部分为阁楼,此阁楼在结构计算上应做为一层考虑,高度可取至山尖墙的一半处,即对带阁楼的坡屋面应算至山尖墙的二分之一高度处。 2、砖墙基础埋深较大,构造柱是否应伸至基础底部?较大洞口两侧要设构造柱加强,一般多大的洞口算较大洞口? 新规范,但应伸入室外地面下500mm,或锚入浅于500mm的基础圈梁内,两条满足其中的一条即可。但需注意此处的基础圈梁是指位于基础内的,不是一般位于相对标高±0.0m 的墙体圈梁。构造柱的钢筋伸入基础圈梁内应满足锚固长度的要求。 X&Qs$对于底层框架砖房的砖房部分,一般允许将砖房部分的构造柱锚固于底部的框架柱或钢筋混凝土抗震墙内(上层与下层的侧移刚度比应满足要求)。:新规范表,内纵墙和横墙的较大洞口,指2000mm 以上的洞口;外纵墙的较大洞口,则由设计人员根据开间和门窗洞尺寸的具体情况确定。 3、填充墙的构造柱与多层砌体房屋的构造柱有何不同? 填充墙设构造柱,属于非结构构件的连接,与多层砌体房屋设置的钢筋混凝土构造柱有一定差异,应结合具体情况分析确定。如挑梁端部设置填充墙构造柱,挑梁在计算时应考虑构造柱传递来的荷载。 4、抗震新规范 新规范,主要指不要在墙体厚度内开洞,烟道等应设在墙外,成为附墙烟道等,以免墙体应力集中。 5、底层框架结构的计算高度如何取?若取到基础顶,抗震墙厚度取1/20层高,是否过大? 计算高度的取值应根据实际情况而定,主要是看地坪的嵌固情况而定,若嵌固得好,如作刚性地坪或有连续的地基梁,可以从嵌固处取,否则从基础顶;抗震墙厚取1/20层高,这里的层高与计算高度的概念不同,是指从一层地坪到一层楼板顶的高度。 6、多层砌体房屋和底部框架、内框架房屋室内外高差大于0.6m时,房屋总高度允许比表,但不应多于1m,那么此时是否仍可将小数点后第一位数四舍五入吗? 多层砌体房屋和底部框架、内框架房屋,若室内外高差大于0.6m时,房屋总高度允许比新规范,但不应多于1m.因已将总高度值适当增加,故此时不应再将小数点后第一位数四舍五入,即增加值不大于1m.

人们对原子结构的认识过程

回顾历史:人们对原子结构的认识过程 科学研究工作的一种重要方法—-假说与模型 1、公元前5世纪,我国墨翟认为构成物质的微粒为“端”,意指不能再分的质点;战国时《庄子·天下篇》一书中提出:物质无限可分的思想。 公元前4世纪,希腊哲学家德谟克利特等人认为:万物是由大量的不可分割的微粒构成的,即原子;而且原子有不同的形态。 2、19世纪初,英国科学家道尔顿提出近代原子学说。 道尔顿原子模型:原子是构成物质的基本粒子,它非常小,不可再分,内 部没有任何结构,就像一个小球一样。 实心球模型 道尔顿提出原子模型虽然多半处于想象,但也有符合科学研究基本原则的

地方,所以是合理的想象。 3、1897年,英国科学家汤生逊发现了电子。 汤姆生的原子模型:原子由带正电荷的主体和带负电荷的电子组成,电子像镶嵌在蛋糕中的葡萄干那样处于正电荷的“海洋”中。这个模型中电子与正电荷的分布是处于想象的,因为没有实验证明。 浸入模型(枣糕模型) 4、1911年,卢瑟福提出原子模型: 原子由带正电的原子核和带负电的电子构成,在原子的中心有一个很小的核,原子核集中了原子的绝大多数质量和全部的正电荷,电子在核外 空间绕着核旋转。

卢瑟福原子行星模型 5.玻尔的原子壳型结构: 电子依据能量不同,在原子核外不同区域(电子层)运动。 玻尔原子壳型结构 6.奥地利物理学家薛定谔提出电子云模型(几率说): 电子云是近代对电子用统计的方法,在核外空间分布方式的形象描绘,

我们不能预言电子在某一时刻究竟出现在核外空间的哪个地方,只能知道它在某处出现的机会有多少,即几率密度大小,用小白点的疏密来表示。小白点密处表示电子出现的几率密度大,小白点疏处几率密度小,看上去好像一片带负电的云状物笼罩在原子核周围,因此叫电子云。 薛定谔电子云模型

数据结构基础知识大全

/** *名词解释1、数据:是信息的载体,能够被计算机识别、存储和加工处理。 *2、数据元素:是数据的基本单位,也称为元素、结点、顶点、记录。一个数据元素可以由若干个数据项组成,数据项是具有独立含义的最小标识单位。 *3、数据结构:指的是数据及数据之间的相互关系,即数据的组织形式,它包括数据的逻辑结构、数据的存储结构和数据的运算三个方面的内容。 *4、数据的逻辑结构:指数据元素之间的逻辑关系,即从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。 *5、数据的存储结构:指数据元素及其关系在计算机存储器内的表示。是数据的逻辑结构用计算机语言的实现,是依赖于计算机语言的。 *6、线性结构:其逻辑特征为,若结构是非空集,则有且仅有一个开始结点和一个终端结点,并且其余每个结点只有一个直接前趋和一个直接后继。 *7、非线性结构:其逻辑特征为一个结点可能有多个直接前趋和直接后继。 *8、算法:是任意一个良定义的计算过程,它以一个或多个值作为输入,并产生一个或多个值作为输出;即一个算法是一系列将输入转换为输出的计算步骤。 *9、算法的时间复杂度T(n):是该算法的时间耗费,它是该算法所求解问题规模n趋向无穷大时,我们把时间复杂度T(n)的数量级(阶)称为算法的渐近时间复杂度。 *10、最坏和平均时间复杂度:由于算法中语句的频度不仅与问题规模n有关,还与输入实例等因素有关;这时可用最坏情况下时间复杂度作为算法的时间复杂度。而平均时间复杂度是指所有的输入实例均以等概率出现的情况下,算法的期望运行时间。 *11、数据的运算:指对数据施加的操作。数据的运算是定义在数据的逻辑结构上的,而实现是要在存储结构上进行。 *12、线性表:由n(n≥0)个结点组成的有限序列。其逻辑特征反映了结点间一对一的关系(一个结点对应一个直接后继,除终端结点外;或一个结点对应一个直接前趋,除开始结点外),这是一种线性结构。 *13、顺序表:顺序存储的线性表,它是一种随机存取结构。通过将相邻结点存放在相邻物理位置上来反映结点间逻辑关系。 *14、单链表:每个结点有两个域:一个值域data;另一个指针域next,用来指向该结点的直接后继结点。头指针是它的充分必要的信息。单链表是一种单向的结构。 *15、双链表:每个结点中增加了一个prior,用来指向该点的直接前趋结点。它是一种双向、对称的结构。 *16、循环链表:是一种首尾相接的链表。单循环链表形成一个next链环,而双循环链表形成next链环和prior链环。 *17、存储密度:是指结点数据本身所占的存储量和整个结点结构所占的存储量之比。顺序表的存储密度为1,而链表的存储密度小于1。 *18、栈:只允许在一端进行插入、删除运算的线性表,称为“栈”(stack)。 *19、LIFO表:即后进先出表,修改操作按后进先出的原则进行。譬如栈就是一种LIFO 表。 *20、顺序栈:采用顺序存储结构的栈,称为顺序栈。 *21、链栈:采用链式存储结构的栈,称为链栈。 *22、队列:只允许在一端进行插入、另一端进行删除运算的线性表,称为“队列”(queue)。*23、FIFO表:即先进先出表。譬如队列就是一种FIFO表。 *24、顺序队列:采用顺序存储结构的队列,称为顺序队列。 *25、循环队列:为克服顺序队列中假上溢现象,将向量空间想象为一个首尾相接的圆环,

建筑结构设计常见问题

建筑结构设计中常见问题及应对策略分析摘要:随着我国建筑行业发展规模不断扩大、发展速度不断加快的同时,建筑功能、建筑结构相关问题日益突出,在建设过程中或多或少的会出现这样、那样的问题,给建筑的安全性埋下大量的隐患。因此,在新时代发展,如何不断优化房屋建筑结构设计,有效的提高房屋建筑的安全性、完善房屋建筑的功能性,成为广大人们群众普遍关注和重点研究的话题之一。 引言 近年来,我国经济快速发展,人民生活水平不断提高,人们对建筑的要求越来越高,因此,建筑业的发展速度不断加快。人们所居住的房屋逐渐由单层、小层向高层复杂化变化,房屋的建筑结构设计也由简单的砖混结构变的多种多样。建筑结构设计的好坏直接影响到人们居住的质量高低。因此,对房屋建筑进行结构设计的同时,必须及时找出设计中的常见问题并及时找好方法解决,以此来保障房屋建筑产品的安全。 一、建筑结构设计概述 由于建筑物功能不同,建筑物分类方法也多种多样。根据建筑物使用功能,可分为民用建筑、工业建筑两种;根据建筑物的结构材料,可分为砌体结构、钢结构、混凝土结构、木结构、混合结构;根据建筑物层数,可分为超高层、高层、多层、单层建筑;根据建筑物的结构形式,可分为筒体结构、剪力墙结构、框架结构、排架结构等。建筑结构是建筑物功能的基础环节,建筑结构设计是建筑设计的重要部

分,其具体过程为:方案设计、结构分析、构件设计、绘制施工图。为了保证建筑结构的安全性和可靠性,在结构设计时应注意以下内容:一是计算方面:应考虑各种结构构件的承载极限,并进行验算;二是由于建筑结构会受到多种作用力,在结构设计时应综合考虑各种作用力;三是抗震方面:我国抗震设防的烈度为 6~9 度,在建筑结构设计时应根据所在地区的房屋高度、结构类型、烈度等情况确定抗震等级。 二、房屋建筑结构设计过程中常见问题 1、结构布置不合理 建筑房屋的设计结构越规则,结构的布置才能越合理,这是建筑房屋结构设计的中心环节。一方面要注意建筑的平、立面外形尺寸大小和抗侧力物体布置的局面,满足承载力分布等各种因素的综合要求。另一方面,由于很多因素都可以造成结构的不规则,特别是针对于复杂的建筑结构,利用若干已经简单化的定量指标来划分不规则的程度并明确限定范围是几乎不可能的。 由于对规范标明的相应的设计规定不了解和对结构抗震理念的缺乏,有些房屋结构的设计人员在结构设计时不注重相关规则,导致建筑过程中出现了规则性不好、抗震性差的房屋。这主要表现在以下几点:(1)设计后的建筑平面凹凸不平,规则性差。(2)导致楼层错层。高层建筑中错层问题较严重时,会阻断楼层的楼板连续性,对建筑结构抗震十分不利。(3)在高层建筑结构中采用了两种或以上的复杂结构。例如错层结构、带转换层结构和多塔楼结构等,都属于复杂

数据结构复习要点(整理版).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讲 人类对原子结构的认识 1.原子 原子的英文名(Atom)是从?τομοζ(atomos ,“不可切分的”)转化而来。很早以前,希腊和印度的哲学家就提出了原子的不可切分的概念。17和18世纪时,化学家发现了物理学的依据:对于某些物质,不能通过化学手段将其继续的分解。19世纪晚期和20世纪早期,物理学家发现了亚原子粒子以及原子的内部结构,由此证明原子并不是不能进一步切分。 原子是一种元素能保持其化学性质的最小单位,一个原子包含有一个致密的原子核及若干围绕在原子核周围带负电的电子,原子核由带正电的质子和电中性的中子组成。在原子中,质子数与电子数相同,原子表现为电中性。如果质子数和电子数不相同,就成为带有正电荷或者负电荷的离子。根据质子和中子数量的不同,原子的类型也不同,质子数决定了该原子属于哪一种元素。原子是一个极小的物体,其质量也很微小,原子的99.9%的重量集中在原子核,其中的质子和中子有着相近的质量,目前可用扫描隧道显微镜观察并拨动单个原子,下图为超高真空多功能扫描隧道显微镜,中图为显微镜下的硅原子结构,右图为在扫描隧道显微镜下科学家拨动49个铁原子排列在钢表面上形成的一个圆形栅栏。 2.构成物质的微粒

构成物质的微粒有原子、分子和离子。 原子是化学变化中的最小微粒,能直接构成物质,如金刚石、石墨等。 分子是构成物质的一种微粒,更多的研究结果表明,分子是由原子结合而成的,如:He、O2、O3、H2O、CO2、H2SO4等。 原子可以通过得到或失去电子形成离子,离子也是构成物质的微粒,如氯化钠就是由Na+和Cl-构成的。 1.原子结构的演变 原子结构模型是科学家根据自己的认识,对原子结构的形象描摹,一种模型代表了人类对原子结构认识的一个阶段。人类认识原子的历史是漫长的,也是无止境的。原子结构模型主要经历了以下演变过程: 道尔顿原子模型(1803年):原子是组成物质的基本粒子,它们是坚实的、不可再分的实心球体。 汤姆生原子模型(1904年):原子是一个平均分布着正电荷的粒子,其中镶嵌着许多电子,中和了正电荷,形成中性原子,俗称“枣糕式”模型,糕体相当于原子核,分散在其中的枣子相当于电子。 卢瑟福原子模型(1911年):在原子的中心有一个带正电荷的核,它的质量几乎等于原子的全部质量,电子在它的周围沿着不同的轨道运转,就像行星围绕太阳运转。玻尔原子模型(1913年):电子在原子核外空间的一定轨道上绕核做高速的圆周运动。 2.原子的组成 原子是化学反应中的最小微粒,在化学反应中不可分割。科学研究表明,绝大多数原子的原子核由质子和中子构成,质子、中子和电子的质量、所带电荷各不相同。1个质子带1个单位的正电荷,1个电子带1个单位的负电荷,中子不显电性。原子核内的质子数与原子核外的电子数相等,所以原子呈电中性。原子核所含质子数,也就是所带的正电荷数又称核电荷数。科学家发现不同元素的原子所含的质子数各

数据结构教程李春葆第4版知识点习题答案

第1章绪论 知识点归纳 一、数据结构概述 1.数据结构的定义 (1)基本概念 数据是描述客观事物的数和字符的集合,是计算机能操作的对象的总称,也是计算机处理信息的某种特定的符号表示形式。 (2)相关术语 ① 数据元素 数据元素又称元素、节点、顶点、记录等。数据元素是数据的基本单位。有时候,一个数据元素可以由若干个数据项组成。 ② 数据项 数据项又称字段或域,它是具有独立含义的最小数据单位。 ③ 数据对象 数据对象是性质相同的数据元素的集合,它是数据的子集。 (3)数据结构的内容 ① 数据元素之间的逻辑关系,即数据的逻辑结构,它是数据结构在用户面前呈现的形式。 ② 数据元素及其关系在计算机存储器中的存储方式,即数据的存储结构,又称数据的物理结构。 ③ 施加在数据上的操作,即数据的运算。 (4)逻辑结构 数据的逻辑结构是从逻辑关系(主要是指数据元素的相邻关系)上描述数据的,它与数据的存储无关,是独立于计算机的。因此,数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 (5)存储结构 数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示(又称映像),也就是逻辑结构在计算机中的存储方式,它是依赖于计算机语言的。一般只在高级语言(例如C/C++语言)的层次上讨论存储结构。 数据的运算最终需在对应的存储结构上用算法实现。 总之,数据结构是一门讨论“描述现实世界实体的数学模型(通常为非数值计算)及其之上的运算在计算机中如何表示和实现”的学科。 (6)数据结构的表示 对于一种数据结构,其逻辑结构总是惟一的,但它可能对应多种存储结构,并且在不同的存储结构中,同一运算的实现过程可能不同。 描述数据结构通常采用二元组表示:

1.1常见结构的认识 作业

1.1常见结构的认识 1.[2017.4浙江学考]如图所示是一种手动冲压机,扳动手柄,通过连杆带动压杆运动。下列关于该冲压机的分析中,正确的是() A.压杆只能上下移动,不能转动,压杆与机座之间的连接属于刚连接 B.冲压时连杆受压 C.冲压机重心的垂线偏离支撑面中心,提高了冲压时的稳定性 D.手柄上施加力F时,压杆向上运动 第1题第2题 2.[2016.4浙江学考]如图所示为一款机械手。在力F作用下,拉杆通过连杆带动夹持手绕着销轴转动,将工件夹紧。连杆和夹持手的主要受力形式是() A.连杆受拉、夹持手受弯曲 B.连杆受压、夹持手受压 C.连杆受压、夹持手受弯曲 D.连杆受弯曲、夹持手受弯曲 第2题第3题 3[2016.3浙江高考]如图所示是一款钣金剪的结构示意图。在加力杆上施加力F时,以下构件的主要受力形式是() A.连杆受拉、加力杆受弯曲 B.连杆受压、加力杆受弯曲 C.连杆受拉、加力杆受压 D.连杆受压、加力杆受压 4[2015.9浙江高考] 如图所示是一款平衡吊,吊臂为平行四边形机构,能在铅垂面内运动。在图示位置,构件1、构件2的主要受力形式是() A.构件1受拉,构件2受弯曲 B.构件1受拉,构件2受拉 C.构件1受弯曲,构件2受拉 D.构件1受弯曲,构件2受

5..[2014.3浙江学考]下列四个椅子,其中杆件受拉的是() 6.[2014.3浙江高考]如图所示为某支架的试验方案,支架在同一垂直平面内对称放置。立柱和转臂的主要受力形式是() A.立柱受压、转臂受弯 B.立柱受压、转臂受扭转 C.立柱受扭转、转臂受弯 D.立柱受弯、转臂受压 第68题第7题 7.[2013浙江学考]如图所示的汽车举升机,其升降臂可托住汽车底盘,并提升汽车,以便汽车底部的检查维护。升降臂的主要受力形式是() A.受拉 B.受弯曲 C.受扭转 D.受压 8.[2013.3浙江高考]如图所示的篮球架,仅考虑自重的情况下,下列受力分析中正确的是() A.立柱受压,横梁受弯曲,拉杆受拉 B.立柱受扭转,横梁受弯曲,拉杆受拉 C.立柱受压,横梁受弯曲,拉杆受压 D.立柱受压,横梁受拉,拉杆受压

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

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

数据结构基础知识整理

数据结构基础知识整理 *名词解释1、数据:是信息的载体,能够被计算机识别、存储和加工处理。 *2、数据元素:是数据的基本单位,也称为元素、结点、顶点、记录。一个数据元素可 以由若干个数据项组成,数据项是具有独立含义的最小标识单位。 *3、数据结构:指的是数据及数据之间的相互关系,即数据的组织形式,它包括数据的 逻辑结构、数据的存储结构和数据的运算三个方面的内容。 *4、数据的逻辑结构:指数据元素之间的逻辑关系,即从逻辑关系上描述数据,它与数 据的存储无关,是独立于计算机的。 *5、数据的存储结构:指数据元素及其关系在计算机存储器内的表示。是数据的逻辑结 构用计算机语言的实现,是依赖于计算机语言的。 *6、线性结构:其逻辑特征为,若结构是非空集,则有且仅有一个开始结点和一个终端 结点,并且其余每个结点只有一个直接前趋和一个直接后继。 *7、非线性结构:其逻辑特征为一个结点可能有多个直接前趋和直接后继。 *8、算法:是任意一个良定义的计算过程,它以一个或多个值作为输入,并产生一个或 多个值作为输出;即一个算法是一系列将输入转换为输出的计算步骤。 *9、算法的时间复杂度T(n):是该算法的时间耗费,它是该算法所求解问题规模n趋向无穷大时,我们把时间复杂度T(n)的数量级(阶)称为算法的渐近时间复杂度。 *10、最坏和平均时间复杂度:由于算法中语句的频度不仅与问题规模n有关,还与输入实例等因素有关;这时可用最坏情况下时间复杂度作为算法的时间复杂度。而平均时间复杂度是指所有的输入实例均以等概率出现的情况下,算法的期望运行时间。 *11、数据的运算:指对数据施加的操作。数据的运算是定义在数据的逻辑结构上的,而 实现是要在存储结构上进行。 *12、线性表:由n(n≥0)个结点组成的有限序列。其逻辑特征反映了结点间一对一的关 系(一个结点对应一个直接后继,除终端结点外;或一个结点对应一个直接前趋,除开始结点外),这是一种线性结构。 *13、顺序表:顺序存储的线性表,它是一种随机存取结构。通过将相邻结点存放在相邻 物理位置上来反映结点间逻辑关系。 *14、单链表:每个结点有两个域:一个值域data;另一个指针域next,用来指向该结

44个结构设计常见问题解析(干货)

44个结构设计常见问题解析(干货) 1、结构类型如何选择? 解释: (1)对于高度不超过150米的多高层项目一般都选择采用钢筋混凝土结构; (2)对于高度超过150米的高层项目则可能会采用钢结构或混凝土结构类型; (3)对于落后偏远地区的民宅或小工程则可能采用砌体结构类型. 2、结构体系如何选择? 解释:对于钢筋混凝土结构,当房屋高度不超过120米时,一般均为三大常规结构体系——框架结构、剪力墙结构、框架—剪力墙结构. (1)对于学校、办公楼、会所、医院以及商场等需要较大空间的建筑, 当房屋高度不超过下表时,一般选择框架结构; 当房屋高度超过下表时,一般选择框架-剪力墙结构; (2)对于高层住宅、公寓、酒店等隔墙位置固定且空间较小的建筑项目一般选择剪力墙结构.当高层住宅、公寓、酒店项目底部一层或若干层因建筑功能要求(如大厅或商业)需要大空间时,一般采用部分框支剪力墙结构.

(3)对于高度大于100米的高层写字楼,一般采用框架-核心筒结构. 3、40米高的办公楼采用框架结构合理吗? 解释:不合理.7度区框架结构经济适用高度为30米,超过30米较多时应在合适的位置(如楼梯、电梯、辅助用房)布置剪力墙,形成框架-剪力墙结构体系.这样子剪力墙承受大部分水平力,大大减小框架部分受力,从而可以减小框架柱、框架梁的截面和配筋,使得结构整体更加经 济合理. 4、框架结构合理柱网及其尺寸? 解释: (1)柱网布置应有规律,一般为正交轴网. (2)普通建筑功能的多层框架结构除个别部位外不宜采用单跨框架,学校、医院等乙类设防建筑以及高层建 筑不应采用单跨框架. (3)仅从结构经济性考虑,低烈度区(6度、7度)且风压小(小于0.4)者宜采用用大柱网(9米左右);高烈度区(8度及以上)者宜采用中小柱网(4~6米左右). (4)一般情况下,柱网尺寸不超过12米;当超过12米时可考虑采用钢结构.

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

第一章概论 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.插入 找到的叶是插入位置,若插入后该叶中关键码 个数

相关文档