数据结构知识点全面总结—
精华版
-标准化文件发布号:(9556-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII
第1章绪论
内容提要:
◆数据结构研究的内容。
针对非数值计算的程序设计问题,研究计算机的操作对象以及它们之间的关系和操作。
数据结构涵盖的内容:
◆基本概念:数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型。
数据——所有能被计算机识别、存储和处理的符号的集合。
数据元素——是数据的基本单位,具有完整确定的实际意义。
数据对象——具有相同性质的数据元素的集合,是数据的一个子集。
数据结构——是相互之间存在一种或多种特定关系的数据元素的集合,表示为:
Data_Structure=(D, R)
数据类型——是一个值的集合和定义在该值上的一组操作的总称。
抽象数据类型——由用户定义的一个数学模型与定义在该模型上的一组操作,它由基本的数据类型构成。
◆算法的定义及五个特征。
算法——是对特定问题求解步骤的一种描述,它是指令的有限序列,是一系列输入转换为输出的计算步骤。
算法的基本特性:输入、输出、有穷性、确定性、可行性
◆算法设计要求。
①正确性、②可读性、③健壮性、④效率与低存储量需求
◆算法分析。
时间复杂度、空间复杂度、稳定性
学习重点:
◆数据结构的“三要素”:逻辑结构、物理(存储)结构及在这种结构上所定义的操作(运算)。
◆用计算语句频度来估算算法的时间复杂度。
第二章线性表
内容提要:
◆线性表的逻辑结构定义,对线性表定义的操作。
线性表的定义:用数据元素的有限序列表示
◆线性表的存储结构:顺序存储结构和链式存储结构。
顺序存储定义:把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
链式存储结构: 其结点在存储器中的位置是随意的,即逻辑上相邻的数据元素在物理上不一定相邻。通过指针来实现!
◆线性表的操作在两种存储结构中的实现。
数据结构的基本运算:修改、插入、删除、查找、排序
1)修改——通过数组的下标便可访问某个特定元素并修改之。
核心语句: V[i]=x;
顺序表修改操作的时间效率是 O(1)
2) 插入——在线性表的第i个位置前插入一个元素
实现步骤:
①将第n至第i 位的元素向后移动一个位置;
②将要插入的元素写到第i个位置;
③表长加1。
注意:事先应判断: 插入位置i 是否合法表是否已满
应当符合条件: 1≤i≤n+1 或 i=[1, n+1]
核心语句:
for (j=n; j>=i; j--)
a[j+1]=a[ j ];
a[ i ]=x;
n++;
插入时的平均移动次数为:n(n+1)/2÷(n+1)=n/2≈O(n) 3) 删除——删除线性表的第i个位置上的元素
实现步骤:
①将第i+1 至第n 位的元素向前移动一个位置;
②表长减1。
注意:事先需要判断,删除位置i 是否合法?
应当符合条件:1≤i≤n 或 i=[1, n]
核心语句:
for ( j=i+1; j<=n; j++ )
a[j-1]=a[j];
n--;
顺序表删除一元素的时间效率为:T(n)=(n-1)/2 ≈O(n)
顺序表插入、删除算法的平均空间复杂度为O(1)
单链表:
(1)
用单链表结构来存放26个英文字母组成的线性表(a,b,c,…,z),请写出C语言程序。#include
#include
typedef struct node{
char data;
struct node *next;
}node;
node *p,*q,*head; //一般需要3个指针变量
int n ; // 数据元素的个数
int m=sizeof(node); /*结构类型定义好之后,每个node类型的长度就固定了,
m求一次即可*/
void build( ) //字母链表的生成。要一个个慢慢链入
{
int i;
head=(node*)malloc(m); //m=sizeof(node) 前面已求出
p=head;
for( i=1; i<26; i++) //因尾结点要特殊处理,故i≠26
{
p->data=i+‘a’-1; // 第一个结点值为字符a
p->next=(node*)malloc(m); //为后继结点“挖坑”!
p=p->next;} //让指针变量P指向后一个结点
p->data=i+‘a’-1; //最后一个元素要单独处理
p->next=NULL ; //单链表尾结点的指针域要置空!
}
}
void display() //字母链表的输出
{
p=head;
while (p) //当指针不空时循环(仅限于无头结点的情况)
{
printf("%c",p->data);
p=p->next; //让指针不断“顺藤摸瓜”
}
}
(2)单链表的修改(或读取)
(3)思路:要修改第i个数据元素,必须从头指针起一直找到该结点的指针p,
然后才能:p>data=new_value
读取第i个数据元素的核心语句是:
Linklist *find(Linklist *head ,int i)
{
int j=1;
Linklist *p;
P=head->next;
While((p!=NULL)&&(j
{
p=p->next;
j++;
}
return p;
}
3.单链表的插入
链表插入的核心语句:
Step 1:s->next=p->next;
Step 2:p->next=s ;
6.单链表的删除
删除动作的核心语句(要借助辅助指针变量q):
q = p->next; //首先保存b的指针,靠它才能找到c;p->next=q->next; //将a、c两结点相连,淘汰b结点;free(q) ; //彻底释放b结点空间
7.双向链表的插入操作:
设p已指向第 i 元素,请在第 i 元素前插入元素 x:
① ai-1的后继从 ai ( 指针是p)变为 x(指针是s) :
s->next = p ; p->prior->next = s ;
② ai 的前驱从 ai-1 ( 指针是p->prior)变为 x ( 指针是s); s->prior = p ->prior ; p->prior = s ;
8.双向链表的删除操作:
教师学生姓名上课日期月日学科数学年级八年级教材版本浙教版 类型知识讲解:√考题讲解:√本人课时统计第()课时共()课时 学案主题八下第三章《数据分析初步》复习课时数量第()课时授课时段 教学目标1、掌握平均数、中位数、众数、极差、方差的概念并进行数据处理; 2、发展学生的统计意识和数据处理的方法与能力; 教学重点、 难点重点:平均数、中位数、众数、极差、方差概念的理解和掌握;难点:会处理实际问题中的统计内容; 教学过程 知识点复习 【知识点梳理】 知识点:平均数、众数、中位数、极差、方差、标准差 表示数据集中的统计量:平均数、中位数、众数 表示数据离散的统计量:方差、标准差 1.(算术)平均数 算术平均数:一般地,对于n个数x1、x2、……、x n,我们把 12 1 ( n X x x x n =+++ ……)叫做n个数的算术平均数,简称平均数,记作X(读作x拔) 加权平均数:若一组数据中x1、x2、……、x n的个数分别是f1、f2、……、f n,则这组数据的平均数1122 1 () n n X x f x f x f n =+++ ……就叫做加权平均数(其中f1+f2+……+f n=n) f1、f2、……、f n分别叫作x1、x2、……、x n的权。“权”越大,对平均数的影响越大. 例题 (1)2、4、7、9、11、13.这几个数的平均数是_______ (2)一组数据同时减去80,所得新的一组数据的平均数为2.3,?那么原数据的平均数__________;(3)8个数的平均数是12,4个数的平均为18,则这12个数的平均数为; (4)某人旅行100千米,前50千米的速度为100千米/小时,后50千米速度为为120千米/小时,则此人的平均速度估计为()千米/小时。A、100 B、109 C、110 D、115 2.中位数 将一组数据按照由小到大(或由大到小)的顺序排列,如果数据的个数是奇数,则处于中间位置的数就是这组数据的中位数(median);如果数据的个数是偶数,则中间两个数据的平均数就是这组数据的中位数。 中位数与数据的排列位置有关,当一组数据中的个别数据相差较大时,可用中位数来描述这组数据的几种趋势。 例题 (1)某小组在一次测试中的成绩为:86,92,84,92,85,85,86,94,92,83,则这个小组本次测试成绩的中位数是() A.85 B.86 C.92 D.87.9 (2)将9个数据从小到大排列后,第个数是这组数据的中位数
第一章绪论 §1-1 结构力学的研究对象和任务 一、结构的定义:由基本构件(如拉杆、柱、梁、板等)按照合理的方式所组成的构件的体系,用以支承荷载并传递荷载起支撑作用的部分。 注:结构一般由多个构件联结而成,如:桥梁、各种房屋(框架、桁架、单层厂房)等。最简单的结构可以是单个的构件,如单跨梁、独立柱等。 二、结构的分类:由构件的几何特征可分为以下三类 1.杆件结构——由杆件组成,构件长度远远大于截面的宽度和高度,如梁、柱、拉压杆。2.薄壁结构——结构的厚度远小于其它两个尺度,平面为板曲面为壳,如楼面、屋面等。3.实体结构——结构的三个尺度为同一量级,如挡土墙、堤坝、大块基础等。 三、课程研究的对象 ?材料力学——以研究单个杆件为主 ?弹性力学——研究杆件(更精确)、板、壳、及块体(挡土墙)等非杆状结构 ?结构力学——研究平面杆件结构 四、课程的任务 1.研究结构的组成规律,以保证在荷载作用下结构各部分不致发生相对运动。探讨结构的合理形式,以便能有效地利用材料,充分发挥其性能。 2.计算由荷载、温度变化、支座沉降等因素在结构各部分所产生的力,为结构的强度计算提供依据,以保证结构满足安全和经济的要求。 3.计算由上述各因素所引起的变形和位移,为结构的刚度计算提供依据,以保证结构在使用过程中不致发生过大变形,从而保证结构满足耐久性的要求。 §1-2 结构计算简图 一、计算简图的概念:将一个具体的工程结构用一个简化的受力图形来表示。 选择计算简图时,要它能反映工程结构物的如下特征: 1.受力特性(荷载的大小、方向、作用位置) 2.几何特性(构件的轴线、形状、长度) 3.支承特性(支座的约束反力性质、杆件连接形式) 二、结构计算简图的简化原则 1.计算简图要尽可能反映实际结构的主要受力和变形特点 ..............,使计算结果安全可靠; 2.略去次要因素,便于 ..。 ..分析和 ...计算 三、结构计算简图的几个简化要点 1.实际工程结构的简化:由空间向平面简化 2.杆件的简化:以杆件的轴线代替杆件 3.结点的简化:杆件之间的连接由理想结点来代替 (1)铰结点:铰结点所连各杆端可独自绕铰心自由转动,即各杆端之间的夹角可任意改变。不存在结点对杆的转动约束,即由于转动在杆端不会产生力矩,也不会传递力矩,只能传递
数据结构知识点概括 第一章概论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位,可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 数据结构的定义: ·逻辑结构:从逻辑结构上描述数据,独立于计算机。·线性结构:一对一关系。 ·线性结构:多对多关系。 ·存储结构:是逻辑结构用计算机语言的实现。·顺序存储结构:如数组。 ·链式存储结构:如链表。 ·索引存储结构:·稠密索引:每个结点都有索引项。 ·稀疏索引:每组结点都有索引项。 ·散列存储结构:如散列表。 ·数据运算。 ·对数据的操作。定义在逻辑结构上,每种逻辑结构都有一个运算集合。 ·常用的有:检索、插入、删除、更新、排序。 数据类型:是一个值的集合以及在这些值上定义的一组操作的总称。 ·结构类型:由用户借助于描述机制定义,是导出类型。 抽象数据类型ADT:·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构,设计一个好的算法。算法取决于数据结构。 算法是一个良定义的计算过程,以一个或多个值输入,并以一个或多个值输出。 评价算法的好坏的因素:·算法是正确的; ·执行算法的时间; ·执行算法的存储空间(主要是辅助存储空间); ·算法易于理解、编码、调试。 时间复杂度:是某个算法的时间耗费,它是该算法所求解问题规模n的函数。 渐近时间复杂度:是指当问题规模趋向无穷大时,该算法时间复杂度的数量级。 评价一个算法的时间性能时,主要标准就是算法的渐近时间复杂度。 算法中语句的频度不仅与问题规模有关,还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为:常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O (n^2)、立方阶O(n^3)、……k次方阶O(n^k)、指数阶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 、内力图通常是用平行于杆轴线方向的坐标表示截面的位置,用垂直于杆轴线的坐标表示
数据的分析知识点与练习 1. 平均数与加权平均数:当给出的一组数据,都在某一常数a上下波动时,一般选用简化 平均数公式..丄I.,其中a是取接近于这组数据平均数中比较“整”的数;?当所给一组 数据中有重复多次出现的数据,常选用加权平均数公式。 (1) 2、4、7、9、11、15.这几个数的平均数是_________ (2 ) 一组数据同时减去80,所得新的一组数据的平均数为2.3,?那么原数据的平均数—; (3)8个数的平均数是12, 4个数的平均为18,则这12个数的平均数为 ____________ ; 2. 中位数:将一组数据按照由小到大(或由大到小)的顺序排列,如果数据的个数是奇 数,则处于中间位置的数就是这组数据的中位数(median);如果数据的个数是偶数,则中间 两个数据的平均数就是这组数据的中位数。 (1 )某小组在一次测试中的成绩为: 86,92,84,92,85,85,86,94,92,83,则这个小组本次测试成绩的中位数是( ) A. 85 B . 86 C . 92 D . 87.9 (2) 将9个数据从小到大排列后,第_________ 个数是这组数据的中位数 3. 众数:一组数据中出现次数最多的数据就是这组数据的众数( mode (1)一个射手连续射靶22次,其中3次射中10环,7次射中9环,9次射中8环,3次射中7环.则射中环数的中位数和众数分别为( ) A. 8,9 B . 8,8 C . 8. 5,8 D . 8. 5,9 (2)数据按从小到大排列为1, 2, 4, X, 6, 9,这组数据的中位数为5,那么这组数据的 众数是()A: 4 B : 5 C : 5.5 D : 6 4. 方差:各个数据与平均数之差的平方的平均数,记作s2.用“先平均,再求差,然后平方,最后再平均”得到的结果表示一组数据偏离平均值的情况,这个结果叫方差,计算公式 1- J )2+(XA?.)2+…+(X n--)2];方差是反映一组数据的波动大小的一个量,其值越 是s2= [(x
第一章数据结构概述 基本概念与术语 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上下波动时,一 般选用简化平均数公式,其中a是取接近于这组数据平均数中比较“整” 的数;?当所给一组数据中有重复多次出现的数据,常选用加权平均数公式。 (1)2、4、7、9、11、15.这几个数的平均数是_______ (2)一组数据同时减去80,所得新的一组数据的平均数为2.3,?那么原数据的平均数___; (3)8个数的平均数是12,4个数的平均为18,则这12个数的平均数为; 2.中位数:将一组数据按照由小到大(或由大到小)的顺序排列,如果数据的个数是奇数,则处于中间位置的数就是这组数据的中位数(median);如果数据的个数是偶数,则中间两个数据的平均数就是这组数据的中位数。 (1)某小组在一次测试中的成绩为:86,92,84,92,85,85,86,94,92,83,则这个小组本次测试成绩的中位数是() A.85 B.86 C.92 D.87.9 (2) 将9个数据从小到大排列后,第个数是这组数据的中位数 3.众数:一组数据中出现次数最多的数据就是这组数据的众数(mode) (1)一个射手连续射靶22次,其中3次射中10环,7次射中9环,9次射中8环,3次射中7环.则射中环数的中位数和众数分别为() A.8,9 B.8,8 C.8.5,8 D.8.5,9 (2)数据按从小到大排列为1,2,4,x,6,9,这组数据的中位数为5,那么这组数据的众数是() A:4 B:5 C:5.5 D: 6 2.用“先平均,再求差,然后平方差:各个数据与平均数之差的平方的平均数,记作s4.方,最后再平均”得到的结果表示一组数据偏离平均值的情况,这个结 果叫方差,计算公式2222];方差是反映一组数据的波动大小的一个量,其值越--)是s)+=[(x-)…+(x+(x n12大,波动越大,也越不稳定或不整齐。 (1)若样本x+1,x+1,…,x+1的平均数为10,方差为2,则对于样本x+2, x+2,…,22n11x+2,下列结论正确的是()n A:平均数为10,方差为 2 B:平均数为11,方差为3 C:平均数为11,方差为2 D:平均数为12,方差为4 (2)方差为2的是() A.1,2,3,4,5 B.0,1,2,3,5 C.2,2,2,2,2 D.2,2,2,3,3 5.极差:一组数据中的最大数据与最小数据的差叫做这组数据的极差(range) (1)某班数学学习小组某次测验成绩分别是63,72,49,66,81,53,92,69,则这组 数据的极差是() 复习提纲 第一章数据结构概述 基本概念与术语(P3) 1.数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2.数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2.数据元素是数据的基本单位 3.数据对象相同性质的数据元素的集合 4.数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. (1)数据的逻辑结构指数据元素之间固有的逻辑关系. (2)数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释:数据结构、二元组 2、根据数据元素之间关系的不同,数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型,它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i 自考02331数据构造重点总结(最后修订) 第一章概论 1.瑞士计算机科学家沃思提出:算法+数据构造=程序。算法是对数据运算描述,而数据构造涉及逻辑构造和存储构造。由此可见,程序设计实质是针对实际问题选取一种好数据构造和设计一种好算法,而好算法在很大限度上取决于描述实际问题数据构造。 2.数据是信息载体。数据元素是数据基本单位。一种数据元素可以由若干个数据项构成,数据项是具备独立含义最小标记单位。数据对象是具备相似性质数据元素集合。 3.数据构造指是数据元素之间互有关系,即数据组织形式。 数据构造普通涉及如下三方面内容:数据逻辑构造、数据存储构造、数据运算 ①数据逻辑构造是从逻辑关系上描述数据,与数据元素存储构造无关,是独立于计算机。 数据逻辑构造分类:线性构造和非线性构造。 线性表是一种典型线性构造。栈、队列、串等都是线性构造。数组、广义表、树和图等数据构造都是非线性构造。 ②数据元素及其关系在计算机内存储方式,称为数据存储构造(物理构造)。 数据存储构造是逻辑构造用计算机语言实现,它依赖于计算机语言。 ③数据运算。最惯用检索、插入、删除、更新、排序等。 4.数据四种基本存储办法:顺序存储、链接存储、索引存储、散列存储 (1)顺序存储:普通借助程序设计语言数组描述。 (2)链接存储:普通借助于程序语言指针来描述。 (3)索引存储:索引表由若干索引项构成。核心字是能唯一标记一种元素一种或各种数据项组合。 (4)散列存储:该办法基本思想是:依照元素核心字直接计算出该元素存储地址。 5.算法必要满足5个准则:输入,0个或各种数据作为输入;输出,产生一种或各种输出;有穷性,算法执行有限步后结束;拟定性,每一条指令含义都明确;可行性,算法是可行。 算法与程序区别:程序必要依赖于计算机程序语言,而一种算法可用自然语言、计算机程序语言、数学语言或商定符号语言来描述。当前惯用描述算法语言有两类:类Pascal和类C。 6.评价算法优劣:算法"对的性"是一方面要考虑。此外,重要考虑如下三点: ①执行算法所耗费时间,即时间复杂性; ②执行算法所耗费存储空间,重要是辅助空间,即空间复杂性; ③算法应易于理解、易于编程,易于调试等,即可读性和可操作性。 数据分析知识点总复习含答案 一、选择题 1 . (11大连)某农科院对甲、乙两种甜玉米各用 10块相同条件的试验田进行试验, 得到两个品种每公顷产量的两组数据,其方差分别为 S 甲2 = 0.002、S 乙2 = 0.03,贝y () A. 甲比乙的产量稳定 B. 乙比甲的产量稳定 【解析】 【分析】方差是刻画波动大小的一个重要的数字 .与平均数一样,仍采用样本的波动大小去 估计总体的波动大小的方法,方差越小则波动越小,稳定性也越好 . 【详解】因为S 甲=0.002 结构力学知识点总结 1.关于∞点和∞线的下列四点结论: (1) 每个方向有一个∞点(即该方向各平行线的交点)。 (2) 不同方向上有不同的∞点。 (3) 各∞点都在同一直线上,此直线称为∞线。 (4) 各有限远点都不在∞线上。 2.多余约束与非多余约束是相对的,多余约束一般不是唯一指定的。一个体系中有多个约束时,应当分清多余约束和非多余约束,只有非多余约束才对体系的自由度有影响。 3.W>0, 缺少足够约束,体系几何可变。W=0, 具备成为几何不变体系所要求 的最少约束数目。W<0,体系具有多余约束。 4.一刚片与一结点用两根不共线的链杆相连组成的体系内部几何不变且无多余约束。 两个刚片用一个铰和一根不通过此铰的链杆相联,组成无多余约束的几何不变体系。 两个刚片用三根不全平行也不交于同一点的链杆相联,组成无多余约束的几何不变体系。 9.剪力图上某点处的切线斜率等于该点处荷载集度q 的大小 ; 弯矩图上某点处的切线斜率等于该点处剪力的大小。 10. 梁上任意两截面的剪力差等于两截面间载荷图所包围的面积; 梁上任意两截面的弯矩差等于两截面间剪力图所包围的面积。 11.分布力q(y)=0时(无分布载荷),剪力图为一条水平线;弯矩图为一条斜直线。 () ()Q dM x dF x dx =2 2 ()()()Q dF x d M x q y dx dx ==-,,B A B A B A x NB NA x x x QB QA y x x B A Q x F F q dx F F q dx M M F dx =-=- =+ ? ? ? 分布力q(y) = 常数时,剪力图为一条斜直线;弯矩图为一条二次曲线。 12.只有两杆汇交的刚结点,若结点上无外力偶作用,则两杆端弯矩必大小相等,且同侧受拉。 13.对称结构受正对称荷载作用, 内力和反力均为对称(K行结点不受荷载情况)。对称结构受反对称荷载作用, 内力和反力均为反对称。 14.三铰拱支反、内力计算公式(竖向荷载、两趾等高) 第一章概论 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数据的分析知识点与常见题型总结
数据结构复习提纲(整理)
2021年自考02331数据结构重点总结最终修订
数据分析知识点总复习含答案0001
结构力学知识点总结
大学数据结构期末知识点重点总结