数据结构考研知识点总结

数据结构考研真题及知识点解析

考察目标

1. 掌握数据结构的基本概念、基本原理和基本方法。

2. 掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。

3. 能够运用数据结构的基本原理和方法进行问题的分析与求解；具备采用C、C++或Java语言设计与实现算法的能力。

第2章线性表

一、考研知识点

（一）线性表的定义和基本操作

（二）线性表的实现

1.顺序存储

2.链式存储

3.线性表的应用

二、考查重点

1．线性结构的特点；

2．线性表在顺序存储及链式存储方式下的基本操作及其应用；

3．线性表的顺序存储及链式存储情况下，其不同和优缺点比较，及其各自适用的场合。单链表中设置头指针、循环链表中设置尾指针而不设置头指针的各自好处；

4．能分析所写算法的时间和空间复杂度。

分析：

线性表是一种最简单的数据结构，在线性表方面，主要考查线性表的定义和基本操作、线性表的实现。在线性表实现方面，要掌握的是线性表的存储结构，包括顺序存储结构和链式存储结构，特别是链式存储结构，是考查的重点。另外，还要掌握线性表的基本应用。

线性表一章在线性结构的学习乃至整个数据结构学科的学习中，其作用都是不可低估的。线性表一章小的知识点比较少，一般会出一个综合题，并且容易和第三章、第九章和第十章的内容结合来考，注意对基本知识的理解，能够利用书上的理论解决具体问题。学习过程中要注意多积累，多看、多写一些相关算法。

三、考研真题

（一）选择题

近几年第2章没有考选择题，只有两个计算时间复杂度的题目，因为此章主要是线性表的操作，而且又是这门课的一个基础，考综合题的可能性比较大，可以和第3章、第9章和第10章的内容结合来出题。

1．（11年）设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（ A ）。

x=2;

while(x

A.O(logn)

B.O(n)

C.O(nlogn)

D.O(n2)

2.（12年）求整数n（n>=0）的阶乘的算法如下，其时间复杂度是（ B ）。

int fact(int n)

{

if(n<=1) return 1;

return n*fact(n-1);

}

A. o(log

2n) B. O(n) C. O(nlog

2

n) D. O(n2)

分析：考查的是算法时间复杂度的计算。可以放在第二章，实际这内容贯穿每一章内容中算法的度量。

（二）综合题

1.（09年）已知一个带有表头结点的单链表结点结构为(data,link)，假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data值，并返回1；否则，只返回0。要求：

（1）描述算法的基本设计思想；

（2）描述算法的详细实现步骤；

（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C++或JAVA语言实现），关键之处给出简要注释。

分析：此题考查线性表的链式存储，主要是线性表的基本操作的应用。做此题时要把握算法的效率。

（1）算法基本思想如下：从头到尾遍历单链表，并用指针p指向当前结点的前k个结点。当遍历到链表的最后一个结点时，指针p所指向的结点即为所查找的结点。

（2）详细实现步骤：增加两个指针变量和一个整型变量，从链表头向后遍历，其中指针p1指向当前遍历的结点，指针p指向p1所指向结点的前k个结点，如果p1之前没有k 个结点，那么p指向表头结点。用整型变量i表示当前遍历了多少结点，当i>k时，指针p 随着每次遍历，也向前移动一个结点。当遍历完成时，p或者指向表头结点，或者指向链表中倒数第k个位置上的结点。

（3）算法描述：

int locate(Linklist list, int k)

{

p1=list->link;

p=list;

i=1;

while(p1)

{

p1=p1->link;

i++;

if(i>k)p=p->next; //如果i>k，则p也后移

}

if(p==list)return 0; //链表没有k个结点

else

{

printf(“%\n”,p->data);

return 1;

}

}

2.（10年）设将n(n,1)个整数存放到一维数组R中，试设计一个在时间和空间两方面尽可能有效的算法，将R中保有的序列循环左移P（0﹤P﹤n）个位置，即将R中的数据由（X0 X1 ……Xn-1）变换为（Xp Xp+1 ……Xn-1 X0 X1 ……Xp-1）要求：（1）给出算法的基本设计思想。

（2）根据设计思想，采用C或C++或JAVA语言表述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度和空间复杂度

分析：此题考查的是数组的操作，线性表的顺序存储的核心就是数组，因此此题实质上是考查的线性表的顺序存储的操作及其应用。做此题时要考虑算法的时间和空间复杂度。

解法一：

（1）算法的基本设计思想：可以将这个问题看做是把数组ab转化成数组ba（a代表数组的前p个元素，b代表数组中余下的n-p个元素），先将a逆置得到a-1b，再将b逆置得到a-1b-1，最后将整个a-1b-1逆置得到（a-1b-1）-1=ba。设reverse函数执行将数组元素逆置的操作，对abcdefgh向左循环移动3（p=3）个位置的过程如下：

reverse(0,p-1)得到cbadefgh；

reverse(p,n-1)得到cbahgfde；

reverse(0,n-1)得到defghabc。

注：reverse中，两个参数分别表示数组中待转换元素的始末位置。

（2）算法描述：

void reverse(int R[], int low, int high)

{//将数组中从low到high的元素逆置

int temp;

for(i=0;i<=(high-low)/2;i++)

{

temp=R[low+i];

R[l0ow+i]=R[high-i];

R[high-i]=temp;

}

}

void converse(int R[], int n, int p)

{

reverse(R,0,p-1);

reverse(R,p,n-1);

reverse(R,0,n-1);

}

（3）上述算法中三个reverse函数的时间复杂度分别是O(p/2)、O((n-p)/2)、O(n/2)，故所设计算法的时间复杂度为O(n)，空间复杂度为O(1)。

解法二：

算法思想：创建大小为p的辅助数组S，将R中前p个整数依次暂存在S中，同时将R 中后n-p个整数左移，然后将S中暂存的p个数依次放回到R中的后续单元。

时间复杂度为O(n)，空间复杂度为O(p)。

3.（11年）一个长度为L（L>=1）的生序列S，处在第┌L/2┐个位置的数称为S的中位数，例如，若序列S1=（11,13,15,17,19），则S1的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=（2,4,6,8,20），则S1和S2的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间方面都尽可能高效的算法，找出两个序列A和B的中位数。要求：

（1）给出算法的基本设计思想。

（2）根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释。

分析：此题考查线性表的顺序存储，主要是线性表的基本操作的应用。做此题时要把握

算法的效率。

（1）算法的基本设计思想如下：

分别求出序列A 和B的中位数，设为a和b，求序列A和B的中位数过程如下：

1）若a=b，则a或b即为所求中位数，算法结束；

2）若a

3）若a>b，则舍弃序列A中较大的一半，同时舍弃序列B中较小的一半，要求舍弃的长度相等；

在保留的两个升序序列中，重复过程1）-3），直到两个序列中只含一个元素时为止，较小者即为所求的中位数。

（2）算法实现如下：

int M_search(int A[],int B[].int n)

{

int s1=0,d1=n-1,m1,s2=0,d2=n-1,m2;

//分别表示序列A和B的首位数、末尾数和中位数

While(s1!=d1||s2!=d2)

{

m1=(s1+d1)/2;

m2=(s2+d2)/2;

if(A[m1]==B[m2]) return A[m1];

else if(A[m1

if(s1+d1)%2==0

{s1=m1;d2=m2;}

else{s1=m1+1;d2=m2;}

else

if(s1+d1)%2==0

{d1=m1;s2=m2;}

else{d1=m1+1;s2=m2;}

}

return A[s1]

}

（3）算法的时间复杂度为O(logn)，空间复杂度为O(1)。

4.（12年）假定采用带头结点的单链表，如果有共同后缀，长度分别为len1和len2（这个条件是我查了一些资料后加上的，网上给的资料这个题目不完整），则可共享相同的后缀存储空间，例如，“loading”和“Beijing”，如下图所示。

设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为（data，next），请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置（如图中字符i所在结点的位置p）。要求：

（1）给出算法的基本设计思想。

（2）根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度。

分析：两个单链表有公共结点，则从公共结点开始，它们的next都指向同一个结点。由于每个单链表结点只有一个next域，因此，从第一个公共结点开始，之后它们所有的结点都是重合的，不可能再出现分叉。因此，我们判断两个链表是不是有重合的部分，只要分别遍历两个链表到最后一个结点。如果两个尾结点是一样的，说明它们有公共结点；否则两个链表没有公共的结点。

因为两个链表长度不一定一样，在顺序遍历两个链表到尾结点时，并不能保证在两个链表上同时到达尾结点。假设一个链表比另一个长k个结点，我们先在长的链表上遍历k个结点，之后再同步遍历，此时能够保证同时到达最后一个结点。在遍历中，第一个相同的结点就是第一个公共结点。

（1）算法思想：根据两个单链表的长度，求出它们的长度之差；在长的单链表上先遍历长度之差个结点；同步遍历两个单链表，直接找到相同的结点，若有相同结点返回该节点，若没有则一直到链表结束。

（2）算法实现：

LinkList search（LinkList str1， LinkList str2， int len1， int2）

{

if（len1>len2）

{long=str1->next; short=str2->next; k=len1-len2;}

else { long=str2->next; short=str1->next; k=len2-len1;}

while(k) {long=long->next; k--;}

while(long)

{

if(long==short) return long;

else { long=long->next; short=short->next;}

}

return NULL;

}

（3）由于每个表仅遍历一遍，因此算法时间复杂度为O(len1+len2)，空间复杂度为O(1)。

四、练习题

（一）选择题

1．下述哪一条是顺序存储结构的优点？（ A ）

A．存储密度大 B．插入运算方便

C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示

2．下面关于线性表的叙述中，错误的是哪一个？（ B ）

A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

3．线性表是具有n个（ C ）的有限序列（n>0）。

A．表元素 B．字符 C．数据元素 D．数据项 E．信息项

4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。

A．单链表 B．仅有头指针的单循环链表

C．双链表 D．仅有尾指针的单循环链表

6．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1<=i<=n+1)。

A. O(0)

B. O(1)

C. O(n)

D. O(n2)

7. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ C ）。

A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)

8．线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ C ）。

A．O（i） B．O（1） C．O（n） D．O（i-1）

（二）综合题

1．掌握线性表中几个最基本的操作算法

（1）链表的建立

头插法建表

void reatelistf(linklist &head，int n)

{ // 逆序输入 n 个数据元素，建立带头结点的单链表

linklist p;

head =(linklist)malloc(sizeof(LNode));

head->next=NULL;

for(i=n;i>0;i--)

{ p=(linklist)malloc(sizeof(LNode));

Scanf(“%d”, &p->data);

p–>next=head->next;

head->next=p;

}

}

尾插法建表

void creater(linklist &head)

{ char ch; linklist p,r;

head->next=NULL; r=head;

while((ch=getchar( )!=‘ ’)

{ p=(linklist)malloc(sizeof(LNode));

p->data=ch;

p->next=r->next;

r–>next=p;

r=p;

}

}

（2）逆置操作

顺序表的就地逆置

void reverse(SqList &A)

{

for(i=1,j=A.length;i

A.elem[i]<->A.elem[j]; //元素交换

}

链表的就地逆置

void LinkList_reverse(Linklist &L)

{

p=L->next; q=p->next;

while (q)

{

r=q->next;

q->next=p;

p=q; q=r;

}

L->next->next=NULL; //修改第一个元素的指针值

L->next=p; //修改表头结点指针值

}

（3）线性表的合并

顺序表的合并：顺序存储的线性表la，lb的关键字为整数，元素非递减有序，线性表空间足够大，试编写高效算法，将lb中元素合并到la中，使新的la的元素仍非递减有序。

分析：从后往前插入，避免移动元素

void union (Sqlist la, Sqlist lb)

{

m=la.length; n=lb.length;

k=m+n; i=m; j=n; //循环指针赋值，从后往前比较

while (i>0&&j>0)

{

if (la.elem[i]>=lb.elem[j])

{la.elem[k]=la.elem[i]; k--; i--;}

else

{la.elem[k]=lb.elem[j]; k--; j--; }

}

if(j>0) //判断lb是否为空

{ la.elem[k]=lb.elem[j]; k--; j--;}

la.length=m+n;

}

链表的合并：把元素递增排列的链表A和B合并为C，且C中元素递减排列，使用原结点空间。

分析：本算法的思想是，按从小到大的顺序依次把A和B的元素插入新表的头部pc处，因为合并以后是逆序，因此采用头插法，最后处理A或B的剩余元素。

LinkList Union( LinkList A, LinkList B, LinkList C)

{

pa=A->next; pb=B->next; C=A;A->next=null;

while(pa!=null && pb!=null)

if(pa->data<=pb->data)

{

r=pa->next; pa->next=C->next;

C->next=pa; pa=r;

}

else

{

r=pb->next; pb->next=C->next;

C->next=pb; pb=r;

while(pa!=null)

{r=pa->next; pa->next=C->next; C->next=pa; pa=r; }

while(pb!=null)

{r=pb->next; pb->next=C->next; C->next=pb; pb=r; }

return C;

}

（4）链表的拆分：设L为一单链表的头指针，单链表的每个结点由一个整数域 data 和指针域next组成，整数在单链表中是无序的。设计算法，将链表中结点分成一个奇数链和一个偶数链，算法中不得申请新的结点空间。

分析：利用原链表空间，在原链表的分解过程中新建链表。

void discreat( linklist L)

{

s=L->next; p=L;

p->next=NULL; q->next=NULL;

while(s!=NULL)

{

r=s->next;

if( s->data%2!=0) //奇数链链接

{ s->next=p->next; p->next=s;}

else //偶数链链接

{s->next=q->next; q->next=s;}

s=r;

}

}

2．算法练习

（1）试编写在带头结点的单链表中删除最小值结点的高效算法。

void delete ( linklist L)

{

p=L->next; pre=L; q=p;

while (p->next!=NULL) //找最小值元素，pre指向最小值的前驱

{

if (p->next->datadata) {pre=p; q=p->next;}

p=p->next;

}

pre->next=q->next;

free (q);

}

分析：此算法的高效在于在循环过程中利用最小值结点的前驱指针进行比较，比较结束后直接保留了最小值结点的前驱，方便进行删除操作。

（2）设单链表的表头指针为h，结点结构由data和next两个域构成，其中data域为字符型。写出算法dc(h,n),判断该链表的前n个字符是否中心对称。例如 xyx, xyyx都是中心对称。

分析：判断链表中数据是否中心对称，通常使用栈。将链表的前一半元素依次进栈。在处理链表的后一半元素时，当访问到链表的一个元素后，就从栈中弹出一个元素，两元素比较，若相等，则将链表中下一元素与栈中再弹出元素比较，直至链表到尾。这时若栈是空栈，则得出链表中心对称的结论；否则，当链表中一元素与栈中弹出元素不等时，结论为链表非中心对称，结束算法的执行。

int dc（Linklist h,int n）

{∥ h是带头结点的n个元素单链表，链表中结点的数据域是字符。

char s[]; int i=1;∥i记结点个数， s字符栈

p=h->next;∥p是链表的工作指针，指向待处理的当前元素。

for（i=1;i<=n/2;i++）∥ 链表前一半元素进栈。

{ s[i]=p->data; p=p->next; }

i--; ∥恢复最后的i值

if（n%2==1）p=p->next;∥若n是奇数，后移过中心结点。

while（p!=null && s[i]==p->data）

{i--; p=p->next;}∥测试是否中心对称。

if（p==null）return 1;∥链表中心对称

else return 0;∥链表不中心对称

}∥算法结束。

（3）已知两个单链表A和B,其头指针分别为heada和headb，编写一个过程从单链表A中删除自第i个元素起的共len个元素，然后将单链表A插入到单链表B的第j个元素之前。

分析：在单链表中删除自第i个元素起的共len个元素，应从第1个元素起开始计数，记到第i个时开始数len个，然后将第i-1个元素的后继指针指向第i+len个结点，实现了在A链表中删除自第i个起的len个结点。这时应继续查到A的尾结点，得到删除元素后的A链表。再查B链表的第j个元素，将A链表插入之。插入和删除中应注意前驱后继关系，不能使链表“断链”。另外，算法中应判断i，len和j的合法性。

Linklist DelInsert（Linklist heada, Linklist headb,int i,j,len）

{∥heada和headb均是带头结点的单链表。

if（i<1 || len<1 || j<1）

{printf（“参数错误\n”）；exit（0）；}∥参数错，退出算法。

p=heada；∥p为链表A的工作指针，初始化为A的头指针

k=0；∥计数

while（p!=null && k

{k++；p=p->next；}

if（p==null）

{printf（“给的%d太大\n”,i）；exit（0）；} ∥i太大，退出算法q=p->next；∥q为工作指针，初始指向A链表第一个被删结点。

k=0；

while（q!=null && k

{k++；u=q，q=q->next；free（u）；} ∥删除结点，后移指针。

if（k

{printf（“给的%d太大\n”,len）；exit（0）；}

p->next=q；∥A链表删除了len个元素。

if (heada->next!=null)∥heada->next=null说明链表中结点均已删除，无需往B 表插入

{

while（p->next!=null）p= p->next；∥找A的尾结点。

q=headb；∥q为链表B的工作指针。

k=0；∥计数

while（q!=null && k

{k++；q= q->next；}∥查找成功时，q指向第j-1个结点

if（q==null）

{printf（“给的%d太大\n”,j）；exit（0）；}

p->next=q->next；∥将A链表链入

q->next=heada->next；∥A的第一元素结点链在B的第j-1个结点之后}//if

free（heada）；∥释放A表头结点。

}

（4）按1，3，5，...4，2的顺序重排双向循环链表L中的所有结点。

分析：next链和pre链的调整分开进行。从前往后调整奇数链，然后从后往前调整偶数链，最后修改pre指针。

void Reform ( DuLinkList &L)

{

p=L->next;

while (p->next!=L &&p->next->next!=L)

{

p->next=p->next->next;

p=p->next;

} // 从前往后调整奇数链

if (p->next==L) p->next=L->pre->pre;

else p->next=L->pre;// 根据链表中元素个数是奇数还是偶数处理表尾结点

p=p->next;

while (p->pre->pre!=L)

{

p->next=p->pre->pre;

p=p->next;

}//从后往前调整偶数链

p->next=L;

for (p=L; p->next!=L; p=p->next) p->next->pre=p;

//重新修改前驱指针

L->pre=p;

}

第3章栈和队列

一、考研知识点

（一）栈和队列的基本概念

（二）栈和队列的顺序存储结构

（三）栈和队列的链式存储结构

（四）栈和队列的应用

二、考查重点

1．栈和队列的特点，及其应用；

2．栈的顺序存储和链式存储的入栈和出栈操作，以及判断栈的空和满的条件；

3．队列的顺序存储和链式存储的入队和出队操作，以及判断队列空和满的条件；

4．理解栈与递归的关系，利于对以后章节（树和图）的学习和复习。

分析：

栈和队列是两种特殊的线性表，在这方面，要求我们掌握栈和队列的基本概念，以及他们之间的区别。对于栈和队列的存储结构(包括顺序存储结构、链式存储结构)要有较深的理解，对于栈和队列的应用，例如，排队问题、子程序调用问题、表达式问题等，要搞清楚。

此章内容是线性表的深化，如果线性表理解的好，这一章就比较容易。这一章小的知识点比较多，一般容易出选择题，从09-12年的考研真题来看，主要是考查栈和队列的特点及其应用、栈的入栈出栈操作和队列的入队出队操作、判断栈和队列的空与满的条件。一般不会单独出综合题，如果出综合题会将栈和队列作为其他结构中一个小环节出题，比如和线性表结合，作为实现递归的工具和二叉树结合等。

三、考研真题

（一）选择题

1.（09年）为解决计算机和打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。

A.栈

B.队列

C.树

D.图

分析：答案是B，此题可以认为考查队列的特点，也可以看做是考查四种数据结构的特点。

2.（09年）设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队顺序是bdcfeag，则栈S的容量至少是（）。

A.1

B.2

C.3

D.4

分析：答案是C，此题考查栈的入栈和出栈操作和队列的入队和出队操作。

3.（10年）若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行。但不允许连续三次进行退栈工作，则不可能得到的出栈序列是（）。

A.dcebfa

B.cbdaef

C.dbcaef

D.afedcb

分析：答案是D，此题考查栈的入栈和出栈操作，但题目出的不是太严谨，严格说应该是CD两个答案。

4.（10年）某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是（ C ）

A.bacde

B.dbace

C.dbcae

D.ecbad

分析：答案是C，此题考查队列的入队和出队操作。

5．（11年）元素a，b，c，d，e依次进入初始为空的栈中，若元素进栈后可停留、可进栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是

A.3

B.4

C.5

D.6

分析：答案是B，出栈序列必为d_c_b_a.e的顺序不定，在任意一个“_”上都有可能。

6．（11年）已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front和rear 分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是

A.0,0

B.0，n-1

C.n-1,0

D.n-1,n-1

分析：答案是B，插入元素时，front不变，rear+1，而插入第一个元素之后，队尾要指向尾元素，显然，rear初始应该为n-1，front为0

7.（12年）已知操作符包括’+’、’-’、’*’、’/’、’(’和’)’。将中缀表达式a+b-a*((c+d)/e-f)+g转换为等价的后缀表达式ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始为空，则转换过程中同时保存在栈中的操作符的最大个数是（）。

A. 5

B. 7

C. 8

D. 11

分析：答案是A，此题考查栈的应用，将中缀表达式转化为后缀表达式，转化过程中利用两个栈分别存放操作符和转化后的表达式，要明确两个栈中元素的进出情况。

（二）综合题

10年考研综合题的第二题如果用解法二，可以认为考查了队列的基本操作，因为栈和队列本身是线性结构，所以考试时可以综合来考，和第2章的内容没有太明显的界限。

四、练习题

（一）选择题

1. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ B ）。

A.不确定

B.n-i+1

C.i

D.n-i

2. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（ D ）。

A. i-j-1

B. i-j

C. j-i+1

D. 不确定的

3. 输入序列为ABC，可以变为CBA时，经过的栈操作为（ B ）。

A. push,pop,push,pop,push,pop

B. push,push,push,pop,pop,pop

C. push,push,pop,pop,push,pop

D. push,pop,push,push,pop,pop

4.循环队列存储在数组A[0..m]中，则入队时的操作为（ D ）。

A. rear=rear+1

B. rear=(rear+1) mod (m-1)

C. rear=(rear+1) mod m

D. rear=(rear+1)mod(m+1)

5. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（ B ）？

A. 1和 5

B. 2和4

C. 4和2

D. 5和1

（二）综合题

这一章一般不会单独出综合题，和其他章节的结合在相关章节中有例题体现。

第5章数组和广义表

一、考研知识点

特殊矩阵的压缩存储

二、考查重点

一维数组属于线性表范畴，但多维数组不属于线性表。在这方面，主要掌握数组的存储

结构，例如按行优先、按列优先等，某个元素存在的地址是什么。对于特殊矩阵(二维数组)的压缩存储原理也要搞清楚。

重点考查特殊矩阵的压缩存储中矩阵中元素在存储空间中地址的计算，只要掌握计算的方法就行，计算时需要特别注意矩阵首元素的下标值以及存储空间首元素的下标值。

三、考研真题

近几年此知识点没有出题。

四、练习题

1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ B ）。

A.13

B.33

C.18

D.40

2. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( B )。

A.BA+141

B.BA+180

C.BA+222

D.BA+225

3. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（ B ）。

A.808

B.818

C.1010

D.1020

4. 将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A 中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（ B ）。

A. 198

B. 195

C. 197

D. 196

5. 二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中（）内的正确答案。

（1）存放A至少需要（ E ）个字节；

（2）A的第8列和第5行共占（ A ）个字节；

（3）若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素（ B ）的起始地址一致。

（1）A.90 B.180 C.240 D.270 E.540

（2）A.108 B.114 C.54 D.60 E.150

（3）A.A[8,5] B.A[3,10] C.A[5,8] D. A[0,9]

6. 设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为( B )。

A.i(i-l)/2+j

B.j(j-l)/2+i

C.j(j-l)/2+i-1

D.i(i-l)/2+j-1

第6章树和二叉树

一、考研知识点

（一）树的基本概念

（二）二叉树

1.二叉树的定义及其主要特征

2.二叉树的顺序存储结构和链式存储结构

3.二叉树的遍历

4.线索二叉树的基本概念和构造

（三）树、森林

1.树的存储结构

2.森林与二叉树的转换

3.树和森林的遍历

（四）树与二叉树的应用

哈夫曼（Huffman）树和哈夫曼编码

二、考查重点

1．二叉树的定义与特点；

2．二叉树的性质及应用；

3．二叉树的遍历（遍历过程及算法实现）；

4．线索二叉树的构造；

5．树的存储及树与二叉树的转换；

6．哈夫曼树构造和哈夫曼编码。

分析：

二叉树和树是两种不同的概念，这一点是必须要搞清楚的。在这个部分，我们要掌握树的定义、二叉树的定义及主要特征(特殊的二叉树、二叉树的性质)。在二叉树的顺序存储结构和链式存储结构方面，特别是链式存储结构，因为很多应用都是建立在链式存储基础上，例如，二叉树的遍历(前序遍历、中序遍历、后序遍历)就是一种典型的应用。

在特殊的二叉树中，完全二叉树的概念是必须要搞清楚的，其次，线索二叉树的基本概念和构造。多棵独立的树就组成了森林，树的存储结构和遍历、森林的遍历、树和二叉树的转换、森林和二叉树的转换等知识，也要了解。

最后就是树的应用，通常会作为综合应用类试题出现，包括等价类问题、哈夫曼(Huffman)树和哈夫曼编码等。

此章知识点比较多，并且每个知识点都可能出题，因此要做到对每一个知识点的理解和掌握，选择题和综合题都可以出，综合题一般会现在二叉树的遍历及其应用、树与二叉树的转换和哈夫曼树的构造及哈夫曼编码。

三、考研真题

（一）选择题

1.（09年）给定二叉树如图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3,7,5,6,1,2,4，则其遍历方式是（）。

A.LRN

B.NRL

C.RLN

D.RNL

分析：答案是D，此题考查二叉树的遍历。

2.（09年）已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是（）。

A.39

B.52

C.111

D.119

分析：答案是C，此题考察二叉树的性质2以及完全二叉树的概念。

3.（09年）将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是（）。

I.父子关系

II.兄弟关系

III.u的父结点与v的父结点是兄弟关系

A.只有II

B.I和II

C.I和III

D.I、II和III

分析：答案是B，此题考查树与二叉树的转换，因为u是v的父结点，若v是u的左子树，则u与v是父子关系，若v是u的右子树，则u与v是兄弟关系。

4.（10年）下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（）。

分析：答案是D，此题考查二叉树的线索化。

5.（10年）在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶节点个数是（）。

A.41

B.82

C.113

D.122

分析：答案是B，此题考查二叉树的性质，利用二叉树的性质3的证明思路进行求解。

6.（10年）对n(n大于等于2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（）。

A.该树一定是一棵完全二叉树

B.树中一定没有度为1的结点

C.树中两个权值最小的结点一定是兄弟结点

D.树中任一非叶结点的权值一定不小于下一层任一结点的权值

分析：答案是A，此题考查哈夫曼树的构造，以及哈夫曼树的特点。

7．（11年）若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（）。

A.257

B.258

C.384

D.385

分析：答案是C，考查二叉树的性质，叶结点个数为你n则度为2的结点个数为n-1，总结点个数为偶数，则度为1的结点个数为1，因此2n=768。

8．（11年）若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1，则该二叉树的中序遍历序列不会是（）。

A.1,2,3,4

B.2,3,4,1

C.3,2,4,1

D.4,3,2,1

分析：答案是C，考查二叉树的遍历。此题可以用画图的方式进行判断。

9．（11年）已知一棵有2011个结点的树，其叶结点个数116，该树对应的二叉树中无右孩子的结点个数是（）。

A.115

B.116

C.1895

D.1896

分析：答案是D，此题考查二叉树和树的转换。考虑一种特殊的情况，设题意中的树是如下图所示的结构，则对应的二叉树中仅有前115个叶结点有右孩子。

10.（年）若一棵二叉树的前序遍历序列为a,e,b,d,c，后序遍历序列为b,c,d,e,a，则根结点的孩子结点（）。

A. 只有e

B. 有e、b

C. 有e、c

D. 无法确定

分析：答案为A。此题考查二叉树的遍历，根据我们的常识，由前序序列和后序序列不能确定二叉树，但此题并不是确定二叉树而是确定二叉树的根结点的孩子结点，因为根结点可以确定，仔细分析前序和后序序列，可以判断出孩子结点只有e，因此答案为A。

（二）综合题

1.（12年）设有6个有序表A、B、C、D、E、F，分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成一个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。

（1）请写出合并方案，并求出最坏情况下比较的总次数。

（2）根据你的合并过程，描述N（N>=2）个不等长升序表的合并策略，并说明理由。

分析：根据排序中的归并排序的思想，多个有序表通过两两归并可以得到一个有序表，因为多个归并段的长度不同，在进行两两归并时要想减少比较的次数，是先将元素少的表进行归并，再归并元素多的表。这样这个问题就转化为最优二叉树的构造问题，将6个有序表的长度看做6个叶子结点的权值，由此构造最优二叉树。

（此分析是根据个人理解做的，暂时没有权威机构的标准答案）

四、练习题

（一）选择题

1.一个具有1025个结点的二叉树的高h为（ C ）。

A．11 B．10 C．11至1025之间 D．10至1024之间

2．一棵二叉树高度为h，所有结点的度或为0或为2，则这棵二叉树最少有( B )结点。

A．2h B．2h-1 C．2h+1 D．h+1

3.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( C )次序的遍历实现编号。

A．先序 B．中序 C．后序 D．从根开始按层次遍历

4.某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ C ）的二叉树。

A．空或只有一个结点 B．任一结点无左子树

C．高度等于其结点数 D．任一结点无右子树

5.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为( C ) 。

A.X的双亲

B.X的右子树中最左的结点

C.X的左子树中最右结点

D.X的左子树中最右叶结点

6.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是( B )。

A.0

B.1

C.2

D.不确定

（二）综合题

1.二叉树的基本遍历算法

（1）二叉树前序、中序、后序和层次遍历的非递归算法

前序

void PreOrder(Bitree T)

{

InitStack(S);

Push(S,T);

while(!StackEmpty(S))

{

pop(S,p);

visit(p->data);

if (p->rchild!=NULL) push(S,p->rchild);

if (p->lchild!=NULL) push(S,p->lchild);

}

}

中序

void InOrder(Bitree T)

{

InitStack(S); p=T;

while(!StackEmpty(S)||p!=NULL)

{

while(p!=NULL)

{ push(S,p); p=p->lchild; }

if(!StackEmpty(S))

{

pop(S,p);

visit(p->data);

p=p->rchild;

}

}

}

后序

void PostOrder(Bitree T)

{

Bitree stack[], p;

int tag[], top=0; p=T;

while(top>0||p!=NULL)

{

while(p!=NULL)

{ top++; stack[top]=p; tag[top]=0; p=p->lchild; }

if(top>0)

{

p=stack[top];

while(tag[top]==1)

{ top--; visit(p->data); p=stack[to}

if(top>0)

{ p=stack[top]; p=p->rchild; tag[top]=1;}

}

}

}

层次

void LayerOrder(Bitree T)

{

InitQueue(Q);

EnQueue(Q,T);

while(!QueueEmpty(Q))

{

DeQueue(Q,p);

visit(p->data);

if(p->lchild) EnQueue(Q,p->lchild);

if(p->rchild) EnQueue(Q,p->rchild);

}

}

（2）二叉树遍历递归算法的应用

求二叉树中叶子结点的数目

int LeafCount_BiTree(Bitree T)

{

if(!T) return 0; //空树没有叶子

else if(!T->lchild&&!T->rchild) return 1;

else

return Leaf_Count(T->lchild)+Leaf_Count(T>rchild);

}

交换所有结点的左右子树。

void Bitree_Revolute(Bitree T)

{

if(T!=NULL)

T->lchild<->T->rchild;

if(T->lchild) Bitree_Revolute(T->lchild);

if(T->rchild) Bitree_Revolute(T->rchild);

}

求二叉树中以值为x的结点为根的子树深度。

int Get_Sub_Depth(Bitree T,int x)

{

if(T->data==x)

{ printf("%d\n",Get_Depth(T)); exit 1; }

else

{

if(T->lchild) Get_Sub_Depth(T->lchild,x);

if(T->rchild) Get_Sub_Depth(T->rchild,x);

}

}

int Get_Depth(Bitree T)

{

if(!T) return 0;

else

{

m=Get_Depth(T->lchild);

n=Get_Depth(T->rchild);

return (m>n?m:n)+1;

}

}

判断两棵树是否相似的递归算法。

int Bitree_Sim(Bitree B1,Bitree B2)

{

if(!B1&&!B2) return 1;

else if(B1&&B2)

return(Bitree_Sim(B1->lchild,B2->lchild)

&&Bitree_Sim(B1->rchild,B2->rchild)) else return 0;

}

2.二叉树非递归遍历算法的应用

（1）判断一二叉树是否为完全二叉树。

int Full_Bitree(Bitree T)

{

InitQueue(Q); flag=0;

EnQueue(Q,T);

while(!QueueEmpty(Q))

{

DeQueue(Q,p);

if(!p) flag=1;

else if(flag) return 0;

else {

EnQueue(Q,p->lchild);

EnQueue(Q,p->rchild);

}

}

return 1;

}

（2）在二叉树中查找值为x的结点，编写算法输出x的所有祖先。

void PostOrder(Bitree T，int x)

{

Bitree stack[], p;

int tag[], top=0; p=T;

while(top>0||p!=NULL)

{

while(p!=NULL&&p->data!=x)

{ top++; stack[top]=p; tag[top]=0; p=p->lchild; }

if(p->data==x)

{

printf(“”);

for(i=1;i<=top;i++) printf(stack[i]->data);

return;

}

while(tag[top]==1&&top>1)top--;

if(top>0)

{ p=stack[top]; p=p->rchild; tag[top]=1;}

}

}

分析：二叉树遍历算法的应用中关键的一个环节是分析要实现相关功能应该选择二叉树的哪一种遍历方式有利于实现，如以上两个例子中分别选用二叉树的层次遍历和后序遍历实现具体操作，主要对遍历算法稍加处理就可以实现了。

3．从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。

分析：树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。

4．如果给出了一个二叉树结点的前序序列和中序序列，能否构造出此二叉树?若能，请证明之。若不能，请给出反例。如果给出了一个二叉树结点的前序序列和后序序列，能否构造出此二叉树?若能，请证明之。若不能，请给出反例。

分析：给定二叉树结点的前序序列和对称序（中序）序列，可以唯一确定该二叉树。因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边（设l个元素）表示左子树，若左边无元素，则说明左子树为空；右边（设r个元素）是右子树，若为空，则右子树为空。根据前序遍历中“根-—左子树—右子树”的顺序，则由从第二元素开始的l个结点序列和中序序列根左边的l个结点序列构造左子树，由前序序列最后r个元素序列与中序序列根右边的r个元素序列构造右子树。

由二叉树的前序序列和后序序列不能唯一确定一棵二叉树，因无法确定左右子树两部分。例如，任何结点只有左子树的二叉树和任何结点只有右子树的二叉树，其前序序列相同，后序序列相同，但却是两棵不同的二叉树。

5．给定一组数列（15,8,10,21,6,19,3）分别代表字符A,B,C,D,E,F,G出现的频度，试叙述建立哈夫曼树的算法思想，画出哈夫曼树，给出各字符的编码值，并说明这种编码的优点。

历史知识点归纳总结1

第1课中国古代早期的政治制度 一、夏商（BC2070年-BC1600年） 1、时间： 夏朝：BC2070年-BC1600年 商朝：BC1600年-BC1046年 2、政治制度： ⑴王位世袭制 ①建立：禹死后，他的儿子启登上王位。 ②特点： a、父死子继或者兄终弟及 b、神化王权 ③影响： a、标志着我国氏族制度的瓦解，奴隶制社会的确立 b、是私有制发展到一定阶段的产物，顺应了历史发展潮流，推动了人类社会的进 步。 ⑵初步建立的从中央到地方的行政管理制度 ①内容： 中央设有相、卿士等掌管政务； 地方封候和伯，候和伯作为臣服于商朝的方国首领，定期向商王纳贡，并奉命征伐。 ②特点：最高执政集团尚未实现权力的高度集中。 二、西周 1、时间：BC1046年-BC771年 2、政治制度 ⑴分封制

①目的：巩固统治 ②内容： a.对象：周王把土地和人民授予王族（燕、鲁、晋、卫、吴）、功臣（齐）、古代帝王的后代（宋、陈、许、楚），让他们建立诸侯国，拱卫王室。 b.被封诸侯的义务：服从周王的命令、镇守疆土、随从作战、交纳贡赋、朝觐述职 c.被封诸侯的权利：再分封、设官员、建武装、征赋役 ③特点： a.分封对象：分封对象多元化，但以同姓亲族为主体。 b..纵向联系：严格的等级序列 ④评价： 积极性：a、加强了周天子对地方的统治，周王确立了“天下共主”的地位。 b、密切了同周边各少数民族的关系，利于开发边远地区，扩大统治区域。 C、有利于周文化的传播。 消极性：在分封制下，受封的诸侵在自己的领地内，享有相当大的独立性，不利于中央集权。 ⑤兴衰过程： 分封制起源于何时，学术界说法不一，西周时，分封制相当发达，进入成熟时期，西周后期，王权衰落，分封制遭到破坏。 ⑥衰落原因 a、周王室衰落，诸侯势力的发展。 b、根本原因：生产力的发展，井田制瓦解。 （2）宗法制 ①目的：为了加强分封制形成的统治秩序，解决贵族之间在权力、财产和土地继承上的矛盾。 ②内容：宗法制是用父系血缘的亲疏来维系政治等级、巩固国家统治的制度。它严格确立了大宗、小宗体系。

九年级世界历史知识点汇总

九年级世界历史知识点汇总 1、文艺复兴的意义： 文艺复兴推动了欧洲文化思想领域的繁荣，为欧洲资本主义社会的产生奠定了思想文化基础。是资产阶级叩响近代社会大门的思想解放运动，促进资本主义的发展。 2、新航路开辟的意义： a.新航路开辟使欧洲与亚洲、非洲、美洲联系日益密切，世界开始连成一个整体，是经济全球化的开始。打破了以往世界各个地区相互隔绝和孤立发展的局面。 b.促进欧洲资本主义的产生和发展 c.随着新航路的开辟，一场持续了数百年的殖民掠夺、扩张与侵略活动也从此开始了，欧洲资本主义的触角开始伸向世界各地。 3、英国资产阶级革命历史意义和影响： ①推翻了封建专制统治，走上了资本主义道路，率先开始了工业革命，有利于资本主义的发展②推动了欧洲资产阶级革命运动的发展③是世界近代史的开端 4、美国独立战争的历史意义： 既是民族解放战争，又是资产阶级革命;①推翻了英国的殖民统治，赢得了民族独立，走上了资本主义道路，开创了民主政治的先河，有利于美国资本主义的发展;②推动欧美资产阶级革命 5、法国大革命的历史意义： ①彻底摧毁了法国的封建统治，走上了资本主义道路，有利于资本主义的发

展，②使民主共和思想广为传播，③对人类社会的发展产生了深远影响。 6、评价拿破仑： 拿破仑是法国大革命时期杰出的资产阶级政治家和军事家，也是一个军事独裁者。他掌握政权后，采取各种措施发展资本主义工商业，制定和颁布了《法典》，确立了资本主义社会的立法规范。他所进行的早期战争捍卫了法国大革命的成果，动摇了欧洲大陆的封建统治，但后期进行的战争，侵犯了欧洲许多国家的主权，掠夺了各国人民的财富，激起了各国人民的反抗，最终葬送了法兰西第一帝国。 7、工业革命影响： ①生活方面：出现的交通工具方便了人们的出行，扩大了人类的活动范围，密切了世界各地的联系。 ②生产力：机器生产代替了手工，产生了巨大的生产力。 ③社会关系方面：使社会日益分裂为两大直接对立阶级，即工业资产阶级和工业无产阶级。 ④国际关系方面：资本主义最终战胜封建主义。率先完成工业革命的西方资本主义国家逐步确立起对世界的统治，世界形成了西方先进、东方落后的局面。 8、工业革命给中国带来了怎样的影响 (1)率先完成工业革命的英国对中国发动鸦片战争，中国开始沦为半殖民地半封建社会; (2)地主阶级洋务派向西方学习，掀起了洋务运动; 工业革命的启示：科技是第一生产力。坚持科教兴国战略、科学发展观。 9、俄国农奴制改革的意义： 积极影响：是沙皇自上而下实行的资产阶级性质的改革，废除农奴制，有利

结构力学知识点复习过程

建筑物和工程设施中承受、传递荷载而起骨架作用的部分称为工程结构，简称为结构。 从几何角度来看，结构可分为三类，分别为：杆件结构、板壳结构、实体结构。 结构力学中所有的计算方法都应考虑以下三方面条件： ①力系的平衡条件或运动条件。 ②变形的几何连续条件。 ③应力与变形间的物理条件（或称为本构方程）。 结点分为：铰结点、刚结点。 铰结点：可以传递力，但不能传递力矩。 刚结点：既可以传递力，也可以传递力矩。 支座按其受力特质分为：滚轴支座、铰支座、定向支座、固定支座。 在结构计算中，为了简化，对组成各杆件的材料一般都假设为：连续的、均匀的、各向同性的、完全弹性或弹塑性的。 荷载是主动作用于结构的外力。 狭义荷载：结构的自重、加于结构的水压力和土压力。 广义荷载：温度变化、基础沉降、材料收缩。 根据荷载作用时间的久暂，可以分为：恒载、活载。 根据荷载作用的性质，可以分为：静力荷载、动力荷载。 结构的几何构造分析 在几何构造分析中，不考虑这种由于材料的应变所产生的变形。 杆件体系可分为两类： 几何不变体系------在不考虑材料应变的条件下，体系的位置和形状是不能改变的。 几何可变体系------在不考虑材料应变的条件下，体系的位置和形状是可以改变的。 自由度：一个体系自由度的个数，等于这个体系运动时可以独立改变的坐标的个数。 一点在平面内有两个自由度（横纵坐标）。 一个刚片在平面内有三个自由度（横纵坐标及转角）。 凡是自由度的个数大于零的体系都是几何可变体系。 一个支杆（链杆）相当于一个约束。可以减少一个自由度。 一个单铰（只连接两个刚片的铰）相当于两个约束。可以减少两个自由度。一个单刚结（刚性结合）相当于三个约束，可以减少三个自由度。 如果在一个体系中增加一个约束，而体系的自由度并不因而减少，则此约束称为多余约束。增加了约束，计算自由度会减少。因为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）。

初中世界历史知识点总结

初中世界历史知识点总结 对第一次工业革命历史功绩的学习，同学们要认真学习，很好的掌握第一次工业革命对历史的影响。以下内容是xx为您精心整理的，欢迎参考！ 识记简述“三角贸易”的基本内容，了解资本原始积累的野蛮与残酷性。 影响：①大批黑人在运送途中丧身。②使非洲丧失大量劳动力，长期贫穷落后。③欧洲积累了巨额资本，推动了欧洲资本主义的快速发展。 北：九上P54-55 从16世纪起，欧洲殖民者为补充和增加美洲殖民地的劳动力，开始从非洲贩运黑人。他们带着廉价工业品从欧洲出发，到非洲购买、换取甚至直接猎取黑人，用船运到美洲，卖给种植园主充当奴隶，然后带着满船的黄金、白银和欧洲需要的经济作物返回欧洲。由于这种交易的全程航线呈三角形，因此史称“三角贸易”。 “三角贸易”持续了几百年，使非洲丧失了难以计数的人口。许多黑人在运往美洲的途中丧生。 通过以上对第一次工业革命历史功绩的学习，同学们要认真学习，很好的掌握第一次工业革命对历史的影响。 通过上面对三角贸易知识点的学习，希望同学们可以很

好的掌握此知识点，并能很好的帮助同学们的考试工作。 武昌起义和中华民国成立： a、1911年10月10日，武昌城内新军工程营的革命党人起义，第二天起义军占领武昌，接着，汉阳，汉口的新军起义，革命在武汉三镇取得胜利。这一年是旧历辛亥年，历史上称这次革命为辛亥革命。10月11日，起义军成立湖北军政府，宣布废除宣统年号，建立中华民国。 b、1912年元旦，中华民国临时政府成立。孙中山为中华民国临时大总统。 C、《同盟会的政治纲领》是：“驱逐鞑虏，恢复中华，建立民国，平均地权。”孙中山在《民报》发刊词中，把同盟会的革命纲领阐发为“民族、民权、民生”三大主义。成为孙中山领导辛亥革命的指导思想。 希望上面对武昌起义和中华民国成立历史知识的复习学习，同学们对上面的知识能很好的掌握学习。 1．洋务派的口号、代表人物；洋务派为“自强”“求富”创办的主要军事工业和民用工业；评价洋务运动在中国近代化进程中的地位和作用P29-30 洋务运动的代表人物：洋务派在中央以恭亲王奕讠斤为代表，在地方以曾国藩、李鸿章、左宗棠、张之洞为代表。 口号和创办的主要企业：洋务运动前期以“自强”为口号，创办一批近代军事工业。有李鸿章创办的江南制造总局，

结构力学单元复习题第一套、2.doc

结构力学一、二单元复习资料 一、填空题 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．常变体系

初中历史知识点归纳汇总

初中历史2019/2020学年第一学期七年级（上册）复习知识点 ★第一课祖国境内的远古居民 一、我国最早的人类1．我国境内已知的最早的人类是元谋人，距今约170万年。2．人和动物的根本区别是会不会制造工具。二、北京人北京人距今约70-20万年，保留猿的特征，但手脚分工明显，能制造和使用工具，使用打制石器。★第三课华夏之祖一、华夏之祖——黄帝和炎帝，人文初祖——黄帝二、尧舜禹的“禅让”1．夏朝的建立，标志着奴隶制度开始了。我国奴隶社会开始于公元前21世纪。2．约公元前2070年，禹建立夏朝，是我国历史上第一个王朝。夏朝的建立,标志着我国早期国家的建立。★第四课夏、商、西周的兴亡一、夏朝的兴衰1．禹死后，把王位传给他的儿子启，使世袭制度代替禅让制，“家天下”取代了“公天下”。2．约公元前1600年，汤战胜桀，夏灭商建。公元前1046年，商、周在牧野大战。商灭，武王建立周朝，定都镐，又称镐京，历史上叫西周。二、西周的分封制1．目的：为了巩固统治，西周实行分封制。2．内容：周天子把土地和平民、奴隶，分给亲属、功臣等，封他们为诸侯。诸侯必须服从周天子的命令，向天子交纳贡品，平时镇守疆土，战时带兵随从天子作战。3．作用：开发了边远地区，加强了统治，使西周成为一个强盛的国家。★第五课灿烂的青铜文明1．在原始社会末期，我国已经出现了青铜器。商朝是我国青铜文化的灿烂时期。著名的青铜器有司母戊鼎(造型雄伟)和四羊方尊(造型精美)。2．与商周同期，我国西南地区的成都平原，也盛行一种独特的青铜文化，这就是举世闻名的“三星堆”文化。那里出土的青铜面具、大型青铜立人像、青铜神树等，引起中外人士的瞩目。★第六课春秋战国的纷争一、春秋争霸1．公元前770年，周平王东迁洛邑，史称“东周”。东周分为春秋和战国两个时期。2．齐桓公任用管仲为相，积极改革内政，发展生产；同时改革军制，组建强大的军队，以“尊王攘夷”为号令，逐步成为春秋第一霸主。3．公元前7世纪后期，晋楚双方城濮大战后晋文公成为中原霸主。百年后，楚庄王做了中原霸主。 二、战国七雄1．战国七雄按东南西北到中间的顺序排列为齐、楚、秦、燕、赵、魏、韩。 2．发生于公元前260年，秦、赵之间决定性战役是长平之战。长平之战使东方六国再也无力抵挡秦国。 ★第七课大变革的时代一、铁农具和牛耕的使用1．春秋时期是我国奴隶制度瓦解时期，战国时期是我国封建制度的形成时期。2．我国农业发展史上的一次革命是指牛耕。牛耕：最迟春秋末年使用，战国推广。铁农具：春秋出现，战国推广。二、著名的都江堰战国时期，李冰为秦国修筑的都江堰是举世闻名的防洪灌溉工程。成都平原成为“天府之国”。三、商鞅变法1．时间、地点：公元前356年，秦国。2．内容：①国家承认土地私有，允许自由买卖。②奖励耕战，生产粮食布帛多的人，可免除徭役；根据军功大小授予爵位和田宅，废除没有军功的旧贵族的特权。③建立县制，由国君直接派官吏治理。3．作用：经过商鞅变法，秦国的经济得到了发展，军队战斗力不断增强，发展成为战国后期最富强的封建国家。★第八课中华文化的勃兴（一）1．我国有文字可考的历史，从商朝开始。2．商朝人刻在龟甲或兽骨上的文字，称为“甲骨文”。★第九课中华文化的勃兴（二）1．孔子是春秋晚期人，其言论记录在《论语》中，他提出“仁”的学说，主张“爱人”，“为政以德” ，教育上提出：因材施教，温故而知新，老老实实的学习态度。《论语》由孔子弟子整理编写。2．老子是春秋晚期人，其学说记录在《道德经》中，他认为一切事物都有对立面，对立的双方能够相互转化。《道德经》由战国时期道家学派整理而成。3．墨子是战国时期人，主张“兼爱”、“非攻”，反对以大欺小、以强凌弱，支持正义战争。4．孟子是战国人，认为“春秋无义战”，反对一切战争。主张“仁政”治国，轻徭薄赋，强调保护环境。5．韩非是战国末期人，主张改革，反对空谈仁义，提倡法制。6．孙武是春秋晚期人，著有《孙子兵法》一书，其军事思想是：“知彼知己，百战不殆。” ★第十课“秦王扫六合”一、秦统一六国和中央集权统治的建立1．灭六国时间：从公元前230年至前221年，秦王嬴政陆续灭掉六国。2．秦朝建立：前221年，建立起我国历史上第一个统一的中央集权的封建国家——秦朝，定都咸阳。3．中央集权统治的建立（1）目的：为了加强统治创立了封建专制主义的中央集权制度。（2）最高统治者是皇帝，中央设丞相，太尉，御史大夫分管行政、军事和监察（3）地方推行郡县制度。（县制起源于商鞅变法，一直沿用到今天） 二、秦朝巩固统一的措施1．政治上：建立起我国历史上第一个统一的中央集权的封建国家2．经济上：统一货币（统一使用圆开方孔铜钱）、度量衡。3．文化上：统一文字（把小篆作为全国规范文字）4．思想上：焚书坑儒。5．军事上：反击匈奴，北筑长城（西起临洮，东到辽东）。南凿灵渠，开发南疆。6．秦统一后在地方上推行郡县制度。★第十二课大一统的汉朝1．汉武帝的大一统具体措施：（1）政治上：汉武帝接受主父偃的建议，颁布“推恩令”，允许诸王将自己的封地分给子弟，建立较小的侯国，削弱了诸侯国的力量；（2）思想上：接受董仲舒“罢黜百家，独尊儒术”的建议，把儒家思想作为封建社会的正统思想，儒家思想在中国古代的统治地位由此确立。（3）军事上：对匈奴展开多次大规模的反击战，基本解除匈奴对北部边郡的威胁。（4）经济上：将铸币权和盐铁经营权收归中央，统一铸造五铢钱。★第十五课汉通西域和丝绸之路一、张骞通西域1．西域位置：西汉时期，人们把今甘肃玉门关和阳关以西，也就是今天新疆地区和更远的地方。2．张骞两次通西域：（1）公元前138年，张骞第一次出使西域。（目的：

数据结构复习要点(整理版).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. 云南元谋人是我国境内已知的最早人类，距今约一百七十万年。 2. 人和动物的根本区别是会不会制造工具。 3. 距今约70—20万年的北京人生活在北京西南周口店龙骨山的山洞里，使用打击石器，使用天然火，过着群居生活，是早期人类原始社会。 4. 我国是世界上发现远古人类遗址最多的国家。 5. 山顶洞人距今约三万年前，在北京人活动过的地区生活，仍用打击石器，但已掌握磨光和钻孔技术，会人工取火，靠采集、狩猎为生。他们生活的集体也进入母系氏族公社时期。 6. 氏族：是由血缘关系结合起来的，由一个共同的祖先繁衍下来他们居住在一起，共同劳动、共同生活，没有贫富贵贱的差别的这样一种集体。 7. 山顶洞人的生活比北京人有哪些进步？ 代表文化距今时间体质形态工具制造生产活动观念社会组织 北京人约70万－20万年保留猿的某些特征打制石器采集、狩猎原始人群 山顶洞人约18000年和现代人基本相同开始掌握磨光和钻孔技术：骨针采集、狩猎懂得爱美氏族 8. 我国是世界上最早种植水稻和粟的国家。 9. 生活在长江流域的河姆渡原始居民（距今约七千年）和生活在黄河流域的半坡原始居民（距今约五六千年）使用磨制石器，开始原始农耕的定居生活。河姆渡人住着干栏式房子便于通风防潮；半坡人住在半地穴式的房子里。

10. 炎帝和黄帝是我国传说中黄河流域著名的部落首领，涿鹿之战中两部落联合起来，大败蚩尤，随后结成联盟，经过长期发展，形成了日后的华夏族。 11. 部落是指在原始社会中许多近亲的氏族共同组成部落，若干部落又组成部落联盟。 12. 黄帝被后人尊称为“人文初祖”。 13. 尧舜禹时期采用“禅让”的方法推举部落联盟首领。 14. 约公元前2070年，禹建立夏朝；夏朝是我国历史上第一个王朝，从此，我国漫长的原始社会结束，奴隶社会开始，世袭制代替了禅让制，“公天下”变成了“家天下”。 15. 约公元前1600年黄河下游的商部落国君——汤战胜桀，建立商朝。 16. 商王盘庚迁都到殷，故后人又称商朝为殷朝。 17. 周文王任用贤人姜尚，重视农业生产，使国力逐步强大起来。公元前1046年，文王的儿子周武王伐纣，牧野之战灭亡商朝建立西周，定都镐京。 18. 公元前771年，西周灭亡。公元前770年，周平王迁都洛邑，东周开始。 19. 世界上现存最大的青铜器是司母戊鼎。 20. 举世闻名的“三星堆”文化是与商周同期的我国成都平原盛行和一种独特的青铜文化，著名的有青铜面具、青铜立人像、青铜神树等。 21. 我国是世界上最早发明瓷器的国家。商朝早期就开始烧制原始青瓷。

结构力学的知识点

双筋计算方法： 一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．性質：資產階級民主革命 2．結果：①推翻了沙皇の專制統治，建立了資產階級臨時政府。②二月革命後の兩個政權並存の局面：資產階級臨時政府（主要政權）和工人士兵代表蘇維埃。 二.俄國十月革命 1．時間：1917年11月（列寧到彼得格勒の起義總指揮部——斯莫爾尼宮，領導起義）2．原因：①第一次世界大戰給俄國人民帶來了深重の苦難。②臨時政府繼續實行反人民の對外政策，（繼續進行世界大戰）並力圖撲滅國內の革命火焰。 3．結果：推翻了資產階級臨時政府，並建立了第一個工人士兵蘇維埃政府——人民委員會，列 寧當選為主席。 4．蘇維埃政府采取の措施：①建立新型の無產階級政權，②將銀行、鐵路和大工業企業收歸國有，③頒布《土地法令》，沒收地主和寺院の土地分配給農民耕種，④同德國和奧匈帝國議和，退出第一次世界大戰。 5．1918年3月蘇維埃俄國首都從彼得格勒遷到莫斯科。 6．1920年粉碎了外國武裝幹涉和國內の反革命叛亂，取得了國內戰爭の勝利，鞏固了世界上第一個無產階級國家。（為了戰勝敵人蘇維埃政權采取：①加強紅軍の建設，②實行了經濟上高度集中の“戰時共產主義”政策。） 7．十月革命の曆史意義：①俄國十月社會主義革命是人類曆史上第一次獲得勝利の社會主義革命，世界上第一個社會主義國家由此誕生。②十月革命の勝利沉重打擊了帝國主義の統治，推動了國際社會主義運動の發展，鼓舞了殖民地半殖民地人民の解放鬥爭。 第2課對社會主義道路の探索 蘇俄進入和平建設時期の首要任務是：恢複被戰爭嚴重破壞了の經濟。一．列寧の探索 1．在列寧の領導下，1921年蘇俄開始實行新經濟政策，允許多種經濟並存，大力發展商品經濟，促進國民經濟の恢複和發展。（1924年列寧逝世） 2．1922年底蘇維埃社會主義共和國聯盟成立，簡稱“蘇聯”。後來共有15個加盟共和國。二．斯大林の探索 1．措施：①1928~1937年，完成第一、第二個五年計劃，重點發展重工業。②蘇聯加快了實農為化の步伐。 2．作用：蘇聯由全傳統の農業國變成強盛の工業國，國防力量也大為加強。全國基本實現社會主義工業化和農業集體化。 3．蘇聯在1936年通過新憲法，宣布蘇聯是“工農社會主義國家”。新憲法の制定，標志著蘇聯高度集中の經濟政治體制の形成。這一體制也被稱為“斯大林模式”。（特點：政治上——高度集權，忽視民主；經濟上——計劃經濟，排斥市場） 4．斯大林模式の影響：在一定曆史階段裏發揮過積極の作用，但後來它嚴重阻礙了蘇聯の

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

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

2020年高考历史一轮复习知识点总结 世界古代史

2020年高考历史一轮复习知识点总结 世界古代史 政治方面 古希腊与古罗马 （一）雅典民主政治：包含：（1）梭伦改革（2）克里斯提尼改革（3）伯利克里改革 基本特点：人民主权，轮番而至；古希腊城邦的主要特征：小国寡民，各邦长期独立自治 体现：（1）公民大会：最高权力机关，审议并决定一切国家大事 （2）五百人议事会：公民大会的附属机构，负责公民大会的提案，主持；监督大会决议落实 （3）民众法庭：日常司法机关，终审高级公职人员任职资格；审判等司法职能 积极评价：雅典民主制度为人类提供了一种集体管理的新形势，创造出法治基础上的选举制，任期制， 比例代表制等民主运作方式，为后世民主政治发展提供宝贵经验。 局限：雅典的民主制度不是现代意义上的民主，只是成年男性公民的民主 （二）罗马法 1.内容：（1）开端：十二铜表法：a.内容：内容庞杂，包括民法、刑法、诉讼法，基本上是过去未成文法 的汇编，明确维护私有财产权和贵族的既得利益。 （2）完备：《查士丁尼民法大全》：《查士丁尼法典》《查士丁尼法学总论》《查士丁尼学说汇纂》《查士丁尼新敕》 2.评价：以《十二铜表法》为开端，《查士丁尼民法大全》为总结的罗马法，在维系罗马帝国的统治中起重要作用。现代资本主义法制的发展与罗马法的复兴是密不可分的，自19世纪以来，欧洲大多数国家均以罗马法为基础来制定本国的法律制度。 思想方面

人文精神起源——古希腊哲学 1.智者学派：（1）背景：商品经济的发展和民主政治的高度繁荣 前5世纪（2）代表人物：普罗塔格拉 （3）主张：把关注的重点从认识自然转移到认识社会上来，提倡怀疑精神，反对封建迷信， 强调人的价值作用。“人是万物的尺度” 2.苏格拉底：（1）主张：哲学：认识人自己 强调知识的作用，认为知识即美德，认为人只有具有知识才能达到善 （2）意义：开创了古希腊哲学的新方向，是希腊哲学真正成为一门认识人的学问 他推崇知识和自由探索的理性精神对后世西方哲学产生了深远影响

结构力学主要知识点归纳

结构力学主要知识点 一、基本概念 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 、内力图通常是用平行于杆轴线方向的坐标表示截面的位置，用垂直于杆轴线的坐标表示

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

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