第一章数据结构概述
基本概念与术语
1．数据：数据是用来描述现实世界的文字，字符，图像，声音，以及能够输入到计算机中并能被计算机处理的符号。
2.数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。
（补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。）3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。（有时候也叫做属性。）
4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
（1）数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。
数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。
依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种：
a.集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。
b.线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。
c.树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素（根）之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。
d.图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个（或零个）直接后继。
（2）数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。
想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构：
a.顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。
b.链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。
5.时间复杂度分析：a.常量阶：算法的时间复杂度与问题规模n无关系T(n)=O(1)
b.线性阶：算法的时间复杂度与问题规模n成线性关系T(n)=O(n)
c.平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++
时间复杂度的大小比较：
O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n ) 6.算法与程序： （1）算法的5个特性 a、输入：有零个或多个输入 b、输出：有一个或多个输出 c、有穷性：要求序列中的指令是有限的；每条指令的执行包含有限的工作量；整个指令序列的执行在有限的时间内结束。（程序与算法的区别在于，程序不需要有有穷性） d、确定性：算法中的每一个步骤都必须是确定的，而不应当含糊、模棱两可。没有歧义。 e、可行性：算法中的每一个步骤都应当能被有效的执行，并得到确定的结果。 （2）.算法设计的要求： 1、正确性（达到预期效果，满足问题需求） 2、健壮性（能处理合法数据，也能对不合法的数据作出反应，不会产生不可预期的后果） 3、可读性（要求算法易于理解，便于分析） 4、可修改可扩展性 5、高效率（较好的时空性能） 补充内容： 1、名词解释：数据结构、二元组 数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。 二元组就是一种用来表示某个数据对象以及各个元素之间关系的有限集合。 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有两种类型，它们分别是顺序存储结构、链式存储结构 4.以下说法中，正确的是（D） A.数据元素是数据这个集合中的个体 B.数据元素均由数据项组成 C．数据项是数据的基本单位 D.数据元素是数据的最小单位 5.以下有关抽象数据类型的描述中，正确的是（B） A.抽象数据类型是一个值的集合 B.抽象数据类型是数据的逻辑结构及操作的组合 C.抽象数据类型的操作可以没有操作结果 D.抽象数据类型只能够用C语言来描述 6.在一般情况下，一个算法的时间复杂度是问题规模的函数 7.常见时间复杂度有：常数阶O（1）、线性阶O（n）、对数阶O（log 2 n）、平方阶O(n^2)、指数阶O(2^n)。通常认为，具有常数阶量级的算法是好算法，而具有指数阶量级的算法是差算法。 第二章线性表 定义：线性表是n个数据元素的有限序列。一个数据元素可由若干个数据项组成。 1. 顺序表结构 线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称为顺序表。 2. 单链表 （1）链表结点结构 线性表中的数据元素可以用任意的一组存储单元来存储，用指针表示逻辑关系逻辑相邻的两元素的存储空间可以是不连续的。 （2）链表操作算法：初始化、插入、输出、删除、遍历 初始化：p=(struct student *)malloc(sizeof(struct student)); 插入：p->next=head->next; head->next=p; 输出：printf(“%d”,p->data); 删除：q=p->next; p->next = q->next ; free(q); 结点遍历：for(p=head;p;p=p->next); ?补充内容： 1、线性表中，第一个元素没有直接前驱，最后一个元素没有直接后驱。 2、在一个单链表中，若p所指结点是q所指结点的前驱结点，则删除结点q的操作语句为 P->next = q->next ; free(q); 3、在长度为N的顺序表中，插入一个新元素平均需要移动表中N/2个元素，删除一个元素平均需要移动（N-1）/2个元素。 4、若线性表的主要操作是在最后一个元素之后插入一个元素或删除最后一个元素，则采用顺序表存储结构最节省运算时间。 5、已知顺序表中每个元素占用3个存储单元，第13个元素的存储地址为336，则顺序表的首地址为300。（第n个元素的地址即首地址+(n-1)*每个元素的存储空间， 如a[12]（第13个元素）的地址=a[0]+12*3） 6、设有一带头结点单链表L，请编写该单链表的初始化，插入、输出和删除函数。（函数名自定义） 结点定义： typedef int datatype; //结点数据类型，假设为int typedef struct node { //结点结构 datatype data; struct node *next; //双向链表还应加上*previous } Lnode, * pointer ; //结点类型,结点指针类型 typedef pointer lklist; //单链表类型，即头指针类型 初始化： lklist initlist() { pointer head; head=new node;//这是C++做法 //head=( pointer)malloc(sizeof(Lnode)); 这是C语言做法 head->next=NULL; //循环链表则是head->next=head; //双向链表应加上head->previos=NULL; return head; } 插入：（C语言中需要把head转化为全局变量才能实现此程序） int insert(lklist head,datatype x,int i){ pointer q,s; q=get(head,i-1); //找第i-1个点 if(q==NULL) //无第i-1点，即i<1或i>n+1时 { cout<<”非法插入位置!\n”; //这是C++做法，即C语言中的printf(“非法插入位 置!\n”); return 0; } s=new node;//生成新结点即C语言中的 s=( pointer)malloc(sizeof(Lnode)); s->data=x; s->next=q->next; //新点的后继是原第i个点 q->next=s; //原第i-1个点的后继是新点 return 1; //插入成功 } 删除：（C语言中需要把head转化为全局变量才能实现此程序） int delete(lklist head,int i) { pointer p,q; q=get(head,i-1); //找待删点的直接前趋 if(q==NULL || q->next==NULL) //即i<1或i>n时 {cout<<”非法删除位置!\n”;return 0;} p=q->next; //保存待删点地址 q->next=p->next; //修改前趋的后继指针 delete p; //释放结点即C语言中的free(p); return 1; //删除成 1. 不带头结点的单链表head为空的判定条件是(A ) A. head=NULL B. head->next=NULL C. head->next=head D. head!=NULL 2. 带头结点的单链表head为空的判定条件是(B ) A. head=NULL B. head->next=NULL C. head->next=head D. head!=NULL 3. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行(B ) A. s->next=p; p->next=s; B. s->next=p->next; p->next=s; C. s->next=p->next; p=s; D. p->next=s; s->next=p; 4. 在一个单链表中，若删除p所指结点的后续结点，则执行(A ) A. p->next=p->next->next; B. p=p->next; p->next=p->next->next; C. p->next=p->next D. p=p->next->next 5. 从一个具有n个结点的有序单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（B ）个结点。 A. n B. n/2 C. (n-1)/2 D. O(n㏒2n) 6. 给定有n个元素的向量，建立一个有序单链表的时间复杂度（B） A.O(1) B.O(n) C.O(n2) D.O(n㏒2n) 7.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是(B) A.O(1) B.O(n) C.O(n2) D.O(n㏒2n) 8. 在一个单链表中删除q所指结点时，应执行如下操作： q=p->next; p->next=( p->next->next ); free(q);//这种题目靠一根指针是没有办法完成的，必须要借助第二根指针。 9. 在一个单链表中p所指结点之后插入一个s所指结点时，应执行： s->next=( p->next ) p->next=(s)操作。 10. 对于一个具有n个节点的单链表,在已知所指结点后插入一个新结点的时间复杂度 是(O（1）)；在给定值为x的结点后插入一个新结点的时间复杂度是（O(n)）。11.问答题 线性表可用顺序表或链表存储。试问： (1) 两种存储表示各有哪些主要优缺点? 答：顺序表的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均需要移动一半(或近一半)元素，修改效率不高。 链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。 (2) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？ 答：应采用顺序存储表示。因为顺序存储表示的存取速度快，但修改效率低。若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用顺序存储表示较好。 第三章栈和队列 1. 栈 （1）栈的结构与定义 定义：限定仅在表尾进行插入或删除操作的线性表。 结构： typedef struct list{ int listsize; //栈的容量 struct list *head; //栈顶指针 struct list *base; //栈底指针 } （2）顺序栈操作算法：入栈、出栈、判断栈空等（这个是使用数组进行操作的，具体内容参照书本P46-47） （3）链栈的结构与定义 2. 队列 （1）队列的定义 定义：只允许在表的一端进行插入，而在另一端删除元素。 ---------------------------------------------------------------------------------------------------------------- 补充内容： 1、一个栈的入栈序列为“ABCDE”，则以下不可能的出栈序列是（B） A. BCDAE B. EDACB C. BCADE D. AEDCB 2、栈的顺序表示中，用TOP表示栈顶元素，那么栈空的条件是（D） A. TOP==STACKSIZE B. TOP==1 C. TOP==0 D. TOP==-1 3、允许在一端插入，在另一端删除的线性表称为队列。插入的一端为表头，删除的一端为表尾。 4、栈的特点是先进后出，队列的特点是先进先出。 5、对于栈和队列，无论他们采用顺序存储结构还是链式存储结构，进行插入和删除操作的时间复杂度都是O(1)（即与已有元素N无关）。 6、已知链栈Q，编写函数判断栈空，如果栈空则进行入栈操作，否则出栈并输出。（要求判断栈空、出栈、入栈用函数实现）（详看考点2） 7.出队与取队头元素的区别：出队就是删除对头的数据元素，取队头元素是获取对头的数据元素值，不需要删除。 8.链栈与顺序栈相比，比较明显的优点是：（D） A.插入操作比较容易 B.删除操作比较容易 C.不会出现栈空的情况 D.不会出现栈满的情况 考点1：队列的编程： 结构： typedef struct QNode{ int date; struct QNode *next; }QNode,*QueuePtr; typedef struct{ QueuePtr front; QueuePtr rear; }LinkQueue; 创建： LinkQueue InitQueue(LinkQueue Q) { Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); Q.front->next=NULL; return (Q); } 入队： LinkQueue EnQueue(LinkQueue Q,int e) { QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); p->date=e; p->next=NULL; Q.rear->next=p; Q.rear=p; return (Q); } 出队： LinkQueue DeQueue(LinkQueue Q) { int e; QueuePtr p; p=Q.front->next; e=p->date; Q.front=p->next; printf("%d",e); if(Q.rear==p)Q.rear=Q.front=NULL; free(p); return (Q); } 考点2：栈的编程： 创建： struct list *creat() { struct list *p; p=(struct list *)malloc(LEN); p->next=NULL; return(p); } 入栈： struct list *push(struct list *head,int a) { struct list *p; p=(struct list *)malloc(LEN); p->num=a; p->next=head; return(p); } 出栈： struct list *pop(struct list *head) { struct list *p; p=head->next; free(head); return(p); } 判断栈空： int listempty(struct list *head) { if(head->next)return 0; else return 1; } 第四章串（不是重点内容） 1.串是由零个或多个字符组成的有限序列 2.串的赋值：x=’abc’; 第五章数组和广义表（不是重点内容） 1. 多维数组中某数组元素的position求解。一般是给出数组元素的首元素地址和每个元素占用的地址空间并组给出多维数组的维数，然后要求你求出该数组中的某个元素所在的位置。 2. 明确按行存储和按列存储的区别和联系，并能够按照这两种不同的存储方式求解1中类型的题。 3. 将特殊矩阵中的元素按相应的换算方式存入数组中。这些矩阵包括：对称矩阵，三角矩阵，具有某种特点的稀疏矩阵等。熟悉稀疏矩阵的三种不同存储方式：三元组，带辅助行向量的二元组，十字链表存储。掌握将稀疏矩阵的三元组或二元组向十字链表进行转换的算法。?补充内容： 三元组： 结构： typedef struct{ int i,j; //元素行下标及列下标 int e; //元素值 }Triple; typedef struct{ int mu,nu,tu; //矩阵的行数、列数、非零元素个数 Triple data[MAXSIZE+1]; //矩阵包含的三元组表，data[0]未用 }TSMatrix; 十字链表： typedef struct OLNode{ int i,j; //元素行下标及列下标 int e; //元素值 struct OLNode *right,*down; //行的后继以及列的后继 } OLNode，*OLink; typedef struct{ int mu,nu,tu; //矩阵的行数、列数、非零元素个数 OLink *rhead,*chead; //行和列的表头指针组的首地址 }CrossList; CrossList Creat（CrossList M）{ int m,n,t; scanf(“%d%d%d”,&m,&n,&t); M.mu=m;M.nu=n;M.tu=t; M.rhead=( OLink *)malloc((m+1)*sizeof(OLink)); //开辟行表头指针组 M.chead=( OLink *)malloc((n+1)*sizeof(OLink)); //开辟行列头指针组 M.rhead[]=M.chead[]=NULL; //初始化 …… //接下来就是赋值和入链，因为内容实在过多……我就不全部抄下来了…… ｝ 第六章树和二叉树 1．树 （1）树的概念及术语 树：n（n≥0）个结点的有限集合。当n＝0时，称为空树；任意一棵非空树满足以下条件： ⑴有且仅有一个特定的称为根的结点； ⑵当n＞1时，除根结点之外的其余结点被分成m（m>0）个互不相交的有限集 合T1,T2,…,Tm，其中每个集合又是一棵树，并称为这个根结点的子树。 （2）结点的度：结点所拥有的子树的个数。 树的度：树中所有结点的度的最大值。 （3）叶子结点：度为0的结点，也称为终端结点。 分支结点：度不为0的结点，也称为非终端结点。 （4）孩子、双亲：树中某结点的子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点； 兄弟：具有同一个双亲的孩子结点互称为兄弟。 （5）路径：如果树的结点序列n1, n2, …, nk有如下关系：结点ni是ni+1的双亲 （1<=i （6）祖先、子孙：在树中，如果有一条路径从结点x到结点y，那么x就称为y的祖先，而y称为x的子孙。 （7）结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。 树的深度：树中所有结点的最大层数，也称高度。 （8）层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以 从1开始的连续自然数。 （9）有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为无序树。数据结构中讨论的一般都是有序树 （10）树通常有前序（根）遍历、后序（根）遍历和层序（次）遍历三种方式（树， 不是二叉树，没中序遍历。) 2．二叉树 （1）二叉树的定义：二叉树是n（n≥0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。 满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。 （满二叉树的特点：叶子只能出现在最下一层；只有度为0和度为2的结点。） 完全二叉树：对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同。 完全二叉树的特点： 1.在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。 2.叶子结点只能出现在最下两层，且最下层的叶子结点都集中在二叉树的左部； 3. 完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。 4. 深度为k的完全二叉树在k-1层上一定是满二叉树。 （3）二叉树的性质： 性质1：二叉树的第i层上最多有2i-1个结点（i≥1）。 性质2：一棵深度为k的二叉树中，最多有2k-1个结点，最少有k个结点。深度为k且具有2k-1个结点的二叉树一定是满二叉树 性质3：在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有: n0＝n2＋1。（一个结点的度就是指它放出的射线） 性质4：具有n个结点的完全二叉树的深度为log2n +1。 性质5：对一棵具有n个结点的完全二叉树中从1开始按层序编号，则对于任意的序号为i（1≤i≤n）的结点（简称为结点i），有： （1）如果i＞1，则结点i的双亲结点的序号为 i/2；如果i＝1，则结点i是根结点，无双 亲结点。 （2）如果2i≤n，则结点i的左孩子的序号为2i；如果2i＞n，则结点i无左孩子。（3）如果2i＋1≤n，则结点i的右孩子的序号为2i＋1；如果2i＋1＞n，则结 点i无右孩子。 3．二叉树的遍历（递归调用与访问的顺序不同而产生不同的遍历方法） （1）先序遍历 void XianXu(BiTree T){ if(T){ printf("%c",T->data); //先访问 XianXu(T->lchild); //再继续遍历 XianXu(T->rchild); } } （2）中序遍历 （3）后序遍历 4. 森林与二叉树的转换 （1）同级以左为亲，即左一结点的右孩子是与它同级的右一结点 （2）只认最左路线为亲子路线，即结点的左孩子是它下一级结点的最左的元素 5. 哈夫曼树 （1）哈夫曼树的基本概念： 哈夫曼树：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树。 （2）哈夫曼树的特点： 1. 权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。 2. 只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点. （3）哈夫曼树的构造算法思想及构造过程（森林与哈夫曼编码） 就是求各权值和路径相乘之后叠加的最小值。 ---------------------------------------------------------------------------------------------------------------------- 补充内容： 1、已知一棵完全二叉树有47个结点，则该二叉树有（C）个叶子结点。 A. 6 B. 12 C. 24 D.48 解法如下： 1+2+4+8+16=31 计算从第一层到n-1层的结点个数 47-31=16 计算第n层的叶子结点个数 16-16/2=8 计算第n-1层的叶子结点个数 所以，叶子结点数=16+8=24 计算第n层和第n-1层的总叶子结点数 2、已知遍历一棵二叉树的前序序列ABCDEFG和中序序列CBEDAFG，那么是下面哪棵树（C ）。 C图如下： A ↙↘ B F ↙↘↘ C D G ↙ E 4、完全二叉树必须满足的条件为: ：一棵具有n个结点的二叉树，它的结构与满二叉树的前n个结点的的结构相同。 5、哈夫曼树不存在度为1的结点。 6、有5个带权结点，其权值分别为2，5，3，7，11，根据哈夫曼算法构建该树，并计算该树的带权路径长度。（构建哈夫曼树，很简单，从小开始，计算相加，然后把所有叶子结点乘以等级数字然后相加。也即是：带权路径长度=叶结点的权值*路径长度）1．前序遍历和中序遍历结果相同的二叉树是（D ）。 A 根结点无左孩子的二叉树 B 根结点无右孩子的二叉树 C 所有结点只有左子树的二叉树 D 所有结点只有右子树的二叉树 2．用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组A[1] ~ A[n]中，结 点A[i]若有左子树，则左子树的根结点是（D ）。 A A[2i-1] B A[2i+1] C A[i/2] D A[2i] 3.对任何一棵二叉树T，如果其终端结点的个数为n0，度为2的结点个数为n2，则（C）。 A . n0=n2-1 B . n0=n2 C. n0=n2+1 D. 没有规律 5.对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次为（C ）。 A . h B . h+1 C. h或h+1 D 任意 6. 假定一棵度为3的树的结点个数为50，则它的最小深度为5 ，最大深度为50 。 A 3 B 4 C 5 D 6 7.试找出分别满足下列条件的所有二叉树： ⑴前序序列和中序序列相同：只有右子树 ⑵中序序列和后序序列相同：只有左子树 ⑶前序序列和后序序列相同：只有根，空二叉树 8 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法 （A） （A）正确（B）错误 9.由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法（B） （A）正确（B）错误 （这题不知道该怎么解释……应该问一下老师……） 10.已知某二叉树的后序遍历序列是dabec。中序遍历序列是debac，它的先序遍历序列是（D）。 （A）acbed （B）decab（C）deabc （D）cedba 11.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（D）。 （A）bdgcefha （B）gdbecfha （C）bdgaechf （D）gdbehfca 12.在一非空二叉树的中序遍历序列中，根结点的右边（C） （A）只有右子树上的所有结点（B）只有右子树上的部分结点 （C）只有左子树上的部分结点（D）只有左子树上的所有结点 15.任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序(B ) （A）不发生改变（B）发生改变（C）不能确定（D）以上都不对 第七章图 1.图的基本概念：图的基本术语及推论 图的结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。 设图有n个顶点，则： 有1/2 n(n-1)条边的无向图称为完全图 有n（n-1）条弧的有向图称为有向完全图 元素被多少条弧的箭头所指，它的入度就为多少；反之，出度。 第一个顶点和最后一个顶点相同的路径叫做回路或环 顶点不重复出现的路径叫简单路径 若图中任意两个顶点之间存在路径（不一定是直接相连），则称作连通图 2.邻接矩阵： W i,j 邻接矩阵的定义：A[i][j]= { 0 即VR中不存在 3. 图的遍历 （1）深度优先遍历 步骤：1.从任意顶点开始访问。 2.访问后把该元素对应的访问标志赋值为1表示已访问该数据元素 3.寻找与其有关未被访问的所有邻接顶点，并从该顶点开始进行访问 4. 重复2、3步骤直到该连通图的所有顶点均已访问完毕 （2）广度优先遍历 步骤：1.从任意顶点开始访问。 2.访问后把该元素对应的访问标志赋值为1表示已访问该数据元素 3.寻找与其有关未被访问的邻接顶点，并按顺序入列直到所有邻接顶点均已访问完 毕 4.把最先入列的顶点出列，以它为顶点开始访问 5. 重复2、3、4步骤直到该连通图的所有顶点均已访问完毕 第三次作业： #include #include #define NULL 0 #define LEN sizeof(struct student) struct student { long num; float score; struct student *next; }; int n; struct student*creat(void) { struct student *head; struct student *p1,*p2; n=0; p1=p2=(struct student*)malloc(LEN); scanf("%d,%f",&p1->num,&p2->score); head=NULL; while(p1->num!=0) { n=n+1; if(n==1)head=p1; else p2->next=p1; p2=p1; p1=(struct student*)malloc(LEN); scanf("%d,%f",&p1->num,&p1->score); } p2->next=NULL; return(head); } void print(struct student *head) { struct student *p; printf("\nNow,These %d records are:\n",n); p=head; if(head!=NULL)do { printf("%ld %5.1f\n",p->num,p->score); p=p->next; } while(p!=NULL); } struct student *del(struct student *head,long num) { sturct student *p1,*p2; if(head==NULL) { printf("\nlist null!\n");return(head); } p1=head; while(num!=p1->num&&p1->next!=NULL) { p2=p1; p1=p1->next; } if(num==p1->num) { if(p1==head)head=p1->next; else p2->next=p1->next; printf("delete:%ld\n",num); n=n-1; } else print(%ld not been found!\n",num); return(head); } struct student *insert(struct student*head,struct student*stud) { struct student *p1,*p2,*p0; p1=head; p0=stud; if(head==NULL) { head=p0;p0->next=NULL; } else { while((p0->num>p1->num)&&(p1->next!=NULL)) { p2=p1; p1=p1->next; } if(p0->num { if(head==p1)head=p0; else { p2->next=p0; p0->next=p1; } } else { p1->next=p0; p0->next=NULL; } } n=n+1; return(head): } void main() { int n struct student *head,stu; printf("input records:\n"); head=creat(); print(head); printf("请输入要删除的num:"); scanf("%ld",&m); head=del(head,m); print(head)； printf("请输入要插入的num和成绩:"); scanf("%ld,&f",&stu.num,&stu.score); head=insert(head,&stu); print(head); getchar(); } 第四次作业： #include #include #define NULL 0 #define LEN sizeof(struct list) struct list { int num; struct list *next; struct list *back; }; int n; struct list *creat(void) { struct list *head; struct list *p1,*p2; n=0; p1=(struct list*)malloc(LEN); p2=(struct list*)malloc(LEN); printf("请输入第%d个数值（按"0"结束）：",++n); scanf("%d",&p2->num); if(p2->num==0){printf("error!!\n");return(NULL);} p1->next=p2; p2->back=p1; p1->back=p2->next=NULL; head=p1; while(p2->num!=0) { n++; printf("请输入第%d个数值：",n); p2=(struct list*)malloc(LEN); scanf("%d",&p2->num); p2->next=p1->next; p2->back=p1; p1->next=p2; p2->next->back=p2; p1=p2; } return(head); } void print(struct list *head) { struct list *p; p=head->next; printf("这%d个数据是:\n",n+1); while(p->next!=NULL) { printf("%d\n",p->num); p=p->next; } printf("%d\n\n",p->num); while(p->back!=NULL) { printf("%d\n",p->num); p=p->back; } } void insert(struct list *head) { struct list *p,*s; s=head->next; p=(struct list*)malloc(LEN); printf("请输入要插入的数据："); scanf("%d",&p->num); while(s->next!=NULL) { if(p->num>s->num)s=s->next; else { p->next=s->next; p->back=s; s->next=p; p->next->back=p; break; } } if(s->next==NULL) { p->back=s; p->next=NULL; s->next=p; } n++; } void delete(struct list *head) { struct list *s; int m,l; l=n; s=head->next; printf("请输入要删除的数据："); scanf("%d",&m); do { if(m!=s->num)s=s->next; else {s->back->next=s->next;s->next->back=s->back;n--;break;} }while(s->next!=NULL); if(m==s->num){s->back->next=NULL;n--;} if(l==n)printf("error!!\n\n"); } void main() { struct list *head; int m; head=creat(); print(head); printf("1、插入数据\t2、删除数据\t0、退出\n"); printf("请输入命令的序号："); scanf("%d",&m); while(m!=0) { if(m==1)insert(head); else if(m==2)delete(head); else printf("error!!\n"); print(head); printf("请输入命令的序号："); scanf("%d",&m); } } 第五次作业： #include #include #define NULL 0 #define LEN sizeof(struct list) struct list { int num; struct list *next; }; int n; struct list *creat() { struct list *p; p=(struct list *)malloc(LEN); p->next=NULL; return(p); } struct list *push(struct list *head,int a) { struct list *p; p=(struct list *)malloc(LEN); p->num=a; p->next=head; return(p); } struct list *pop(struct list *head) { struct list *p; p=head->next; free(head); return(p); } void print(struct list *head) { if(head->next){ printf("%d\n",head->num); head=pop(head); n--; print(head); } } void main() { struct list *head; int a=1; n=0; head=creat(); while(a){ printf("请输入第%d个数据（按0结束）：",n+1); scanf("%d",&a); printf("\n"); if(a){head=push(head,a);n++;} } if(n){ printf("这%d个数据是：\n",n+1); print(head);} else printf("List NULL!!\n"); } 第六次作业： #include #include #include #define NULL 0 typedef struct QNode{ int date; struct QNode *next; }QNode,*QueuePtr; typedef struct{ QueuePtr front; QueuePtr rear; }LinkQueue; LinkQueue InitQueue(LinkQueue Q){ Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); Q.front->next=NULL; return (Q); } LinkQueue EnQueue(LinkQueue Q,int e){ 建筑物和工程设施中承受、传递荷载而起骨架作用的部分称为工程结构，简称为结构。 从几何角度来看，结构可分为三类，分别为：杆件结构、板壳结构、实体结构。 结构力学中所有的计算方法都应考虑以下三方面条件： ①力系的平衡条件或运动条件。 ②变形的几何连续条件。 ③应力与变形间的物理条件（或称为本构方程）。 结点分为：铰结点、刚结点。 铰结点：可以传递力，但不能传递力矩。 刚结点：既可以传递力，也可以传递力矩。 支座按其受力特质分为：滚轴支座、铰支座、定向支座、固定支座。 在结构计算中，为了简化，对组成各杆件的材料一般都假设为：连续的、均匀的、各向同性的、完全弹性或弹塑性的。 荷载是主动作用于结构的外力。 狭义荷载：结构的自重、加于结构的水压力和土压力。 广义荷载：温度变化、基础沉降、材料收缩。 根据荷载作用时间的久暂，可以分为：恒载、活载。 根据荷载作用的性质，可以分为：静力荷载、动力荷载。 结构的几何构造分析 在几何构造分析中，不考虑这种由于材料的应变所产生的变形。 杆件体系可分为两类： 几何不变体系------在不考虑材料应变的条件下，体系的位置和形状是不能改变的。 几何可变体系------在不考虑材料应变的条件下，体系的位置和形状是可以改变的。 自由度：一个体系自由度的个数，等于这个体系运动时可以独立改变的坐标的个数。 一点在平面内有两个自由度（横纵坐标）。 一个刚片在平面内有三个自由度（横纵坐标及转角）。 凡是自由度的个数大于零的体系都是几何可变体系。 一个支杆（链杆）相当于一个约束。可以减少一个自由度。 一个单铰（只连接两个刚片的铰）相当于两个约束。可以减少两个自由度。一个单刚结（刚性结合）相当于三个约束，可以减少三个自由度。 如果在一个体系中增加一个约束，而体系的自由度并不因而减少，则此约束称为多余约束。增加了约束，计算自由度会减少。因为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．连接n根杆件的复铰相当于个单铰，相当于个约束，一个固定铰支座相当于个约束，一个固定端支座相当于个约束。 7．切断受弯杆后再加入一个单铰，相当于去掉了个约束 8．几何不变体系的三个基本组成规则分别是三刚片规则、规则、规则。9．两刚片用一个铰和_________________相联，组成无多余约束的几何不变体系。 10．平面内一个点和一根链杆自由运动时的自由度数分别等于和。 11．从几何组成上讲，静定和超静定结构都是体系，前者多余约束而后者多余约束。 12．试判断下列图示体系的几何组成性质，图是没有多余约束的几何不变体系, 图是几何可变体系。 (a) (b) (c) 13．下列（a）图体系为几何体系；（b）图体系为几何体系；（c）图体系为体系。其中有多余联系的体系为图中的体系，此体系的自由度为，计算自由度W为。 (a) (b) (c) 二、判断题 1．三刚片用三个铰两两相联必成为几何不变体系。（） 2．某结构若计算自由度W≤0，则该结构必是几何不变体系。（） 3．当一个体系的计算自由度为零时，必为几何不变体系。（） 4．几何不变体系的自由度一定为0，而其计算自由度可能大于0。（） 5．两刚片用一个铰和一根不通过此铰的链杆连接，组成没有多余约束的几何不变体系。（） 6．瞬变体系由于经微小位移后就变成几何不变体系，所以可以作为结构形式使用。（）7．静定结构几何不变且无多余联系。（） 8．几何不变体系的计算自由度必定等于零。（） 三、单选题 1．下列哪种情况不能组成无多余约束的几何不变体系（） A.三刚片以3个铰两两相连，3个铰不在一条直线上； B.两刚片以一个铰和一个链杆相连，链杆不通过铰； C.两刚片以3个链杆相连，3个链杆不平行也不汇交； D.无。 2．图示结构的几何性质为（）。 A. 几何不变体，无多余约束 B. 几何不变体，有多余约束 C. 常变体系 D. 瞬变体系 题2图题3图题4图 3．如图所示平面杆件体系为（）。 A.几何不变无多余约束体系； B.几何不变有多余约束体系； C.瞬变体系； D.常变体系。 4.如图所示体系为（） A.几何不变无多余约束体系 B.几何不变有多余约束体系 C.几何可变体系 D.无法确定5．图示体系为（）体系 A．无多余约束几何不变 B．有多余约束几何不变 C．瞬变体系 D．常变体系 数据结构导论串讲笔记 1）已知出栈序列，写出可能的入栈序列并分析操作过程。 2）已知入栈序列，写出可能的出栈序列并分析操作过程。 [2004/1]如下图所示，输入元素为（A，B，C），在栈的输出端得到一个输出序列ABC，求出在栈的输入端所有可能的输入序列。 AB 输输 栈 【分析】A，B，C三个字符排成的序列可以有：ABC、ACB、BAC、BCA、CAB、CBA 六种，按堆栈操作的先进后出（或后进先出）的原则，只有输入序列为BCA时，输出无法得到ABC。因为输入序列为BCA时，要想先输出A，必须BCA均入栈，但这样只能得到序列ACB。其余五种输入序列都可在输出端得到序列ABC。 【解答】ABC、ACB、BAC、CAB、CBA 2．队列的操作 分析顺序队中元素入队出队操作及队列的状态。（考过） [2003/10]设有一顺序队列sq ，容量为5，初始状态时sq ．front=sq ．rear=0，画出做完下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理。 （1） d ，e ，b 入队 （2） d ，e 出队 （3） i ，j 入队 （4） b 出队 （5） n ，o ，p 入队 【解答】队列及其头尾指针的状态变化情况如下图所示 Sq.f Sq.r b e d Sq.f b Sq.f Sq.r j b i Sq.f Sq.r j i Sq.f Sq.r （a ）初态 （b ）d ，e ，b 入队 （c ） d ，e 出队 （d ） i ，j 入队 （e ）b 出队 第5步操作无法进行，因队列已满。 3．二叉树的存储结构 1） 给出一棵二叉树，画出二叉链表示意图及顺序存储示意图。（[2000/10] [2003/10] [2004/10]考过） [2003/10]画出下列二叉树的二叉链表表示图。 【解答】二叉树的二叉链表表示 B E D F H G A C B B ∧ ∧ A D ∧ C G ∧ ∧ F H ∧ ∧ E ∧ ∧ 第一章数据结构概述 基本概念与术语 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 ) 双筋计算方法： 一As与As' 1、截面计算 1）假设a s=65mm，a s'=35mm，求得h0=h-a s 2）验算是否需要双筋。Mu= f cd bh02§b（1-0.5§b） 3）取§=§b，求As'=【M- f cd bh02§（1-0.5§）】/【f sd'（h0- a s'）】 4）求As=【f cd bx+f sd'As'】/ f sd 其中x=§b h0 下面选钢筋，钢筋层净距，钢筋间净距（大于30mm和直径d），保护层厚度，再计算a s和a s' 二、已知As'，求As 5）假设a s，求得h0=h-a s 6）求受压区高度x= h0-√h02-2【M- f sd'As'（h0- a s'）】/f cd b 7）当x﹤§b h0且x﹤2 a s'时，As=M/【f sd（h0- a s'）】 当x≤§b h0且x≥2 a s'时，As=【f cd bx+f sd'As'】/ f sd 8）选择受拉钢筋直径的数量，布置截面钢筋（同上） 2、截面复核 1）检查钢筋布置是否符合规要求 2）将As=？As'=？h0=？f cd f sd' f sd 若带入x=【f sd As- f sd'As'】/f cd b ≤§b h0 ﹤2 a s' 用Mu= f sd As（h0- a s'）计算正截面承载力 若2 a s'≤x≤§b h0，矩形截面抗弯承载力 Mu= f cd bx（h0-x/2）+ f sd'As'（h0- a s'） 一、As与As'均未知 1、截面设计 1）求偏心距e0=M/N 长细比l0/h﹥5，考虑偏心增大系数η（l0/h≤5时，取η=1）假设a s= a s'=45.当ηe0﹥0.3 h0时，为大偏心，反之， ξ1=0.27+2.7 e0/ h0 ξ2=1.15-0.01l0/h η=1+1/【1400（e0/ h0）】（l0/h）2ξ1ξ2 2）令§=§b，求As'=【Ne s- f cd bh02§b（1-0.5§b）】/ f sd'（h0- a s'） ≥ρmin bh （ρmin=0.2%）取σs= f sd 求As=【f cd bh0§b+ f sd'As'-N】/ f sd≥ρmin bh 二、已知As'，求As 1）求偏心距e0=M/N 长细比l0/h﹥5，考虑偏心增大系数η（l0/h≤5时，取η=1）假设a s= a s'=45.当ηe0﹥0.3 h0时，为大偏心，反之，2）计算受压区高度x= h0-√h02-2【Ne s - f sd'As'（h0- a s'）】/f cd b 当2 a s'﹤x≤§b h0时，取σs= f sd 求As=【f cd bx+ f sd'As'-N】/ f sd 当x≤§b h0 x≤2 a s'时，As=Ne s'/ f sd（h0- a s'） 3）选钢筋，看配筋率是否符合ρ+ρ'≥0.5%，纵筋最小净距（一般为30mm），重取a s= a s'=？，计算保护层厚度是否满足要求，最小截面宽度b min 2、截面复核 1）垂直于弯矩作用平面 第一概论 1.1 引言 两项基本任务：数据表示，数据处理 软件系统生存期：软件计划，需求分析，软件设计，软件编码，软件测试，软件维护 由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立，选择和实现是数据结构的核心问题。 机外表示------逻辑结构------存储结构 处理要求-----基本运算和运算-------算法 1.2 数据，逻辑结构和运算 数据：凡是能够被计算机存储，加工的对象通称为数据 数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理。又称元素，顶点，结点，记录。 数据项：数据项组成数据元素，但通常不具有完整确定的实际意义，或不被当做一个整体对待。又称字段或域，是数据不可分割的最小标示单位。 1.2.2 数据的逻辑结构 逻辑关系：是指数据元素之间的关联方式，又称“邻接关系” 逻辑结构:数据元素之间逻辑关系的整体称为逻辑结构。即数据的组织形式。 四种基本逻辑结构： 1 集合：任何两个结点间没有逻辑关系，组织形式松散 2 线性结构：结点按逻辑关系依次排列成一条“锁链” 3 树形结构：具有分支，层次特性，形态像自然界中的树 4. 图状结构：各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接。 注意点: 1.逻辑结构与数据元素本身的形式，容无关。 2.逻辑结构与数据元素的相对位置无关 3.逻辑结构与所含结点个数无关。 运算：运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。 加工型运算：改变了原逻辑结构的“值”，如结点个数，结点容等。 引用型运算:不改变原逻辑结构个数和值，只从中提取某些信息作为运算的结果。 引用：查找，读取 加工：插入，删除，更新 同一逻辑结构S上的两个运算A和B, A的实现需要或可以利用B，而B的实现不需要利用A，则称A可以归约为B。 假如X是S上的一些运算的集合，Y是X的一个子集，使得X中每一运算都可以规约为Y中的一个或多个运算，而Y中任何运算不可规约为别的运算，则称Y中运算（相对于X）为基本运算。 将逻辑结构S和在S上的基本运算集X的整体（S,X）称为一个数据结构。数据结构包括逻辑结构和处理方式。 复习提纲 第一章数据结构概述 基本概念与术语（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、计算简图：在计算结构之前，往往需要对实际结构加以简化，表现其主要特点，略去其次要因素，用一个简化图形来代替实际结构。通常包括以下几个方面： 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）数据结构化。 （2）数据共享。 （3）数据冗余小。 （4）有较高的数据独立性。 （5）数据库系统为用户提供了使用方便的用户接口。 （6）增加了系统的灵活性。 ［简答］简述数据独立性的含义及其作用。 数据独立性是指应用程序与数据库的数据结构之间的相互独立，是数据库系统努力追求的目标。数据独立性有两层含义，如果数据库物理结构改变时，不影响数据库的整体逻辑结构、用户的逻辑结构和应用程序，这样我们就认为数据库达到了“物理数据独立性”；如果在整体逻辑结构改变时，不影响用户的逻辑结构及应用程序，那么我们就认为数据库达到了“逻辑数据独立性”。 ［选择］数据库的基本术语： 数据库：是指长期存储在计算机的、有组织的、统一管理的相关数据的集合。 数据库系统：是实现有组织地、动态地存储大量关联数据，方便多用户访问的计算机硬件、软件和数据资源组成的系统，实际上是指采用了数据库技术后的整个计算机系统。 ［简答］DBMS是数据库系统中专门用来管理数据的软件，它位于用户与操作系统（Operating System,简记为OS）之间，是用户使用数据库的接口，为用户提供了访问DB的方法，包括DB的建立、查询、更新和各种数据控制。 ［填空］DBMS总是基于某种数据模型，主要有关系型、层次型、网状型和面向对象型等。 第二节数据描述 ［填空］联系是指实体之间的关系。与一个联系有关的实体集的个数，称为联系的元数。 ［选择、填空］二元联系的三种类型： （1）一对一联系（简记为1∶1） 对于不同型实体集A和B，如果A中的一个实体最多只与B中的一个实体有联系，反之亦然，则称A和B两实体为1∶1联系。例如，一夫一妻制社会中，“丈夫”与“妻子”两实体集之间为1∶1联系。 （2）一对多联系（简记为1∶n） 如果实体集A中至少有一个实体与实体集B中多于一个的实体有联系（可以是零个、一个或多个），则称A对B为1∶n联系。例如，“母亲”和“子女” 自考02331数据构造重点总结(最后修订) 第一章概论 1.瑞士计算机科学家沃思提出：算法+数据构造=程序。算法是对数据运算描述，而数据构造涉及逻辑构造和存储构造。由此可见，程序设计实质是针对实际问题选取一种好数据构造和设计一种好算法，而好算法在很大限度上取决于描述实际问题数据构造。 2.数据是信息载体。数据元素是数据基本单位。一种数据元素可以由若干个数据项构成，数据项是具备独立含义最小标记单位。数据对象是具备相似性质数据元素集合。 3.数据构造指是数据元素之间互有关系，即数据组织形式。 数据构造普通涉及如下三方面内容：数据逻辑构造、数据存储构造、数据运算 ①数据逻辑构造是从逻辑关系上描述数据，与数据元素存储构造无关，是独立于计算机。 数据逻辑构造分类：线性构造和非线性构造。 线性表是一种典型线性构造。栈、队列、串等都是线性构造。数组、广义表、树和图等数据构造都是非线性构造。 ②数据元素及其关系在计算机内存储方式，称为数据存储构造（物理构造）。 数据存储构造是逻辑构造用计算机语言实现，它依赖于计算机语言。 ③数据运算。最惯用检索、插入、删除、更新、排序等。 4.数据四种基本存储办法：顺序存储、链接存储、索引存储、散列存储 （1）顺序存储：普通借助程序设计语言数组描述。 （2）链接存储：普通借助于程序语言指针来描述。 （3）索引存储：索引表由若干索引项构成。核心字是能唯一标记一种元素一种或各种数据项组合。 （4）散列存储：该办法基本思想是：依照元素核心字直接计算出该元素存储地址。 5.算法必要满足5个准则：输入，0个或各种数据作为输入；输出，产生一种或各种输出；有穷性，算法执行有限步后结束；拟定性，每一条指令含义都明确；可行性，算法是可行。 算法与程序区别：程序必要依赖于计算机程序语言，而一种算法可用自然语言、计算机程序语言、数学语言或商定符号语言来描述。当前惯用描述算法语言有两类：类Pascal和类C。 6.评价算法优劣：算法"对的性"是一方面要考虑。此外，重要考虑如下三点： ①执行算法所耗费时间，即时间复杂性； ②执行算法所耗费存储空间，重要是辅助空间，即空间复杂性； ③算法应易于理解、易于编程，易于调试等，即可读性和可操作性。 1.明确单向板和双向板的定义。了解单向板和双向板肋梁楼 盖截面设计与构造措施。明确单向板和双向板的受力钢筋的方向，知道单向板的薄膜效应和双向板的穹顶作用。 2.进行楼盖的结构平面布置时，应注意以下问题：受力合理； 满足建筑要求；施工方便 3.按结构型式，楼盖分为：单向板肋梁楼盖、双向板肋梁楼 盖、井式楼盖、密肋楼盖和无梁楼盖 4.按预加应力分为钢筋混凝土楼盖和预应力混凝土楼盖。 5.单向板肋梁楼盖结构平面布置方案通常有以下三种;a.主梁 横向布置，次梁纵向布置；b.主梁纵向布置，次梁横向布置；c. 只布置次梁，不设主梁 6.现浇单向板肋梁楼盖中的主梁按连续梁进行内力分析 的前提条件是什么？ 答：（ 1）次梁是板的支座，主梁是次梁的支座，柱或墙是主梁的支座。 （2）支座为铰支座--但应注意：支承在混凝土柱上的主梁，若梁柱线刚度比<3，将按框架梁计算。板、次梁均按铰接处理。 由此引起的误差在计算荷载和内力时调整。 （3）不考虑薄膜效应对板内力的影响。 （4）在传力时，可分别忽略板、次梁的连续性，按简支构件计算反力。 （5）大于五跨的连续梁、板，当各跨荷载相同，且跨度相差 大10%时，可按五跨的等跨连续梁、板计算。 7. 为什么连续梁内力按弹性计算方法与按塑性计算方法时，梁计算跨度的取值不同？ 答：从理论上讲，某一跨的计算长度应取为该跨两端支座处转动点之间的距离。以中间跨为例,按考虑塑性内力重分布计算连续梁内力时其计算跨度是取塑性铰截面之间的距离，塑性铰具有一定的长度，能承受一定的弯矩并在弯矩作用方向转动,即取净跨度;而按弹性理论方法计算连续梁内力时，则取支座中心线间的距离作为计算跨度，即取。 8. 单向板按弹性理论计算时，为何采用折算荷载？ 答：因为在按弹性理论计算时，其前提条件——计算假定中忽略了次梁对板的转动约束，这对连续板在恒荷载作用下的计算结果影响不大，但在活荷载不利布置下，次梁的转动将减小板的内力。因此，为了使计算结果更好地符合实际情况，同时也为了简化计算，采用折算荷载。 9. 按弹性理论计算单向板肋梁楼盖时，板和次梁的折算荷载分别为： 板：'2q g g =+；'2q q = 次梁：3';'44q q g g q =+= 10. 连续梁、板按弹性理论计算内力时活荷载的最不利布置位置规律（理解） a) 求某跨跨内最大正弯矩时，应在本跨布置活荷载，然后隔跨布置。 第一张概论 1.1 引言 两项基本任务：数据表示，数据处理 软件系统生存期：软件计划，需求分析，软件设计，软件编码，软件测试，软件维护 由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立，选择和实现是数据结构的核心问题。 机外表示------逻辑结构------存储结构 处理要求-----基本运算和运算-------算法 1.2 数据，逻辑结构和运算 数据：凡是能够被计算机存储，加工的对象通称为数据 数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理。又称元素，顶点，结点，记录。 数据项：数据项组成数据元素，但通常不具有完整确定的实际意义，或不被当做一个整体对待。又称字段或域，是数据不可分割的最小标示单位。 1.2.2数据的逻辑结构 逻辑关系：是指数据元素之间的关联方式，又称“邻接关系” 逻辑结构:数据元素之间逻辑关系的整体称为逻辑结构。即数据的组织形式。 四种基本逻辑结构： 1 集合：任何两个结点间没有逻辑关系，组织形式松散 2 线性结构：结点按逻辑关系依次排列成一条“锁链” 3 树形结构：具有分支，层次特性，形态像自然界中的树 4. 图状结构：各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接。 注意点: 1.逻辑结构与数据元素本身的形式，内容无关。 2.逻辑结构与数据元素的相对位置无关 3.逻辑结构与所含结点个数无关。 运算：运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。 加工型运算：改变了原逻辑结构的“值”，如结点个数，结点内容等。 引用型运算:不改变原逻辑结构个数和值，只从中提取某些信息作为运算的结果。 引用：查找，读取 加工：插入，删除，更新 同一逻辑结构S上的两个运算A和B, A的实现需要或可以利用B，而B的实现不需要利用A，则称A可以归约为B。 假如X是S上的一些运算的集合，Y是X的一个子集，使得X中每一运算都可以规约为Y中的一个或多个运算，而Y中任何运算不可规约为别的运算，则称Y中运算（相对于X）为基本运算。 将逻辑结构S和在S上的基本运算集X的整体（S,X）称为一个数据结构。数据结构包括逻辑结构和处理方式。 第一章概论 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结构力学知识点复习过程
(完整版)非常实用的数据结构知识点总结
结构力学单元复习题第一套、2.doc
数据结构导论串讲笔记
数据结构复习要点整理版
结构力学的知识点
自考02142《大数据结构导论》串讲笔记
数据结构复习提纲(整理)
结构力学主要知识点归纳
数据库和应用串讲笔记(珍藏版)
2021年自考02331数据结构重点总结最终修订
【精】混凝土结构设计知识点总结
自考02142《数据结构导论》串讲笔记
大学数据结构期末知识点重点总结
相关主题
文本预览