当前位置：文档库 › 自考02142《数据结构导论》串讲笔记

自考02142《数据结构导论》串讲笔记

第一张概论

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.3 存储实现和运算实现

由于逻辑结构是设计人员根据解题需要选定的数据组织形式，因此存储实现建立的机内表示应遵循选定的逻辑结构。另一方面，由于逻辑结构不包括结点内容即数据元素本身的表示，因此存储实现的另一主要内容是建立数据元素的机内表示。按上述思路建立的数据的机内表示称为数据的存储结构。

存储结构包括三部分：

1．存储结点，每个存储结点存放一个数据元素。

2．数据元素之间关联方式的表示，也就是逻辑结构的机内表示。

3．附加设施，如方便运算实现而设置的“哑结点”等。

四种基本存储方式：

1．顺序存储方式：每个存储结点只含一个数据元素。所有存储结点相继存放在一个连续的存储区里。用存储结点间的位置关系表述数据元素之间的逻辑关系。

2．链式存储方式：每个存储结点不仅含有一个数据元素，还包含一组指针。每个指针指向一个与本结点有逻辑关系的结点，即用附加的指针表示逻辑关系。

3．索引存储方式：每个存储结点只含一个数据元素，所有存储结点连续存放。此外增设一个索引表，索引指示各存储结点的存储位置或位置区间端点。

4．散列存储方式：每个结点含一个数据元素，各个结点均匀分布在存储区里，用散列函数指示各结点的存储位置或位置区间端点。

1.3.2运算实现

运算只描述处理功能，不包括处理步骤和方法；运算实现的核心是处理步骤的规定，即算法设计。

算法：算法规定了求解给定问题所需的所有处理步骤及其执行顺序，使得给定类型的任何问题能在有限时间内被机械的求解。

算法分类：

1：运行终止的程序可执行部分：又称为程序

2: 伪语言算法：不可以直接在计算机上运行，但容易编写和阅读。

3：非形式算法：用自然语言，同时可能还使用了程序设计语言或伪语言描述的算法。

1.4 算法分析

算法质量评价指标：

1．正确性：能够正确实现处理要求

2．易读性：易于阅读和理解，便于调试，修改和扩充

3．健壮性：当环境发生变化，算法能够适当做出反应或处理，不会产生不需要的运行结果

4．高效率：达到所需要的时空性能。

如何确定一个算法的时空性能，称为算法分析

一个算法的时空性能是指该算法的时间性能和空间性能，前者是算法包含的计算量，后者是算法需要的存储量。

算法在给定输入下的计算量：

1．根据该问题的特点选择一种或几种操作作为“标准操作”。

2．确定每个算法在给定输入下共执行了多少次标准操作，并将此次数规定为该算法在给定输入下的计算

若无特殊说明，将默认以赋值语句作为标准操作。

最坏情况时间复杂性：算法在所有输入下的计算量的最大值作为算法的计算量

平均时间复杂性：算法在所有输入下的计算量的加权平均值作为算法的计算量。

算法的输入规模（问题规模）是指作为该算法输入的数据所含数据元素的数目，或与此数目有关的其他参数。

常见时间复杂性量级：

1．常数阶：O（1）即算法的时间复杂性与输入规模N无关或N恒为常数。

2．对数阶：Olog2 N

3．线性阶：O(N)

4．平方阶：O（N2）

5．指数阶：O（2N次方）

通常认为指数阶量级的算法实际是不可计算的，而量级低于平方阶的算法是高效率的

第二章线性表

2.1 线性表的基本概念

线性结构：线性结构是N（N大于等于0）个结点的有穷序列。

A I 称为Ai+1的直接前趋，A i+1称为Ai 的直接后继。为满足运算的封闭性，通常允许一种逻辑结构出现不含任何结点的情况。不含任何结点的线性结构记为（）或

线性结构的基本特征：若至少含有一个结点，则除起始节点没有直接前趋外，其他结点有且只有一个直接前趋，除终端结点没有直接后继外，其他结点有且只有一个直接后继。

2.1.2线性表

线性表的逻辑结构是线性结构。所含结点个数称为线性表的长度（表长）。表长为0的是空表。

线性表的基本运算：

1．初始化initiate （L）：加工型运算，其作用是建立一个空表L= 。

2．求表长length （L）：引用型运算，其结果是线性表L的长度。

3．读表元get （L，i）：引用型运算。若1小于等于i小于等于length（L），其结果是L的第i个结点，否则为一特殊值。

4．定位（按值查找）locate（L，X）：引用型运算。若L中存在一个或多个值与X相等，结果为这些结点的序号最小值，否则，运算结果为0。

5．插入insert (L,X，i)：加工型运算。在L的第i个位置上增加一个值为X的新结点，参数i的合法取值范围是1---L+1。

6．删除delete （L，i）：加工型运算。撤销L的第i个结点ai, i的合法取值范围是1---N。

2.2 线性表的顺序实现

2.2.1顺序表

顺序表是线性表的顺序存储结构，即按顺序存储方式构造的存储结构。

顺序表基本思想：

顺序表的一个存储结点存储线性表的一个结点的内容，即数据元素（不含其他信息），所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列。

顺序表的特点：逻辑结构中相邻的结点在存储结构中仍相邻。

顺序表的类C语言描述：p17

Const maxsize=顺序表的容量

Typedef struct

{ datatype date [maxsize]

Int last;

} sqlist;

Sqlist L;

L表示线性表的长度，last-1 是终端结点在顺序表中的位置。常数maxsize为顺序表的容量。

表长https://www.wendangku.net/doc/2812414152.html,st , 终端结点L.data[https://www.wendangku.net/doc/2812414152.html,st-1]

2.2.2基本运算在顺序表上的实现

1．插入

Void inset_sqlist (sqlist L,datatype x, int i)

{ if (https://www.wendangku.net/doc/2812414152.html,st == maxsize) error(‘表满’); /*溢出*/

If (((i<1)!!(i>https://www.wendangku.net/doc/2812414152.html,st+1)) error (‘非法位置’);

For (j=https://www.wendangku.net/doc/2812414152.html,st ; j=I; j--)

L.data[j] = L.data [j-1]; /*依次后移*/

L.data[i-1 ]= x; /*置入*/

https://www.wendangku.net/doc/2812414152.html,st =https://www.wendangku.net/doc/2812414152.html,st+1 /*修改表长*/

}

2. 删除

Void delete_sqlist ( sqlist L, int I ) /*删除顺序表L中第i个位置上的结点*/

{

If ( ( i<1 ) !! (I >https://www.wendangku.net/doc/2812414152.html,st)) error (‘非法位置’);

For ( j= i+1; j= https://www.wendangku.net/doc/2812414152.html,st; j++)

L.data [j-2 ] = L.data [j-1 ]; /*依次前移，注意第一个L.data[j-2]存放ai*/

https://www.wendangku.net/doc/2812414152.html,st=https://www.wendangku.net/doc/2812414152.html,st-1 /*修改表长*/

3．定位

Int locate_sqlist (sqlist L , datatype X)

/*在顺序表中从前往后查找第一个值等于X的结点。若找到则回传该结点序号，否则回传0*/ {

I=1 ;

While ( ( i<= https://www.wendangku.net/doc/2812414152.html,st) && (L.data[i-1]!=x) ) /*注意：ai在L.data[i-1]中*/

i++; /*从前往后查找*/

if (i<=https://www.wendangku.net/doc/2812414152.html,st) return (i)

else return (0)

}

2.2.3顺序实现的算法分析

插入:平均时间复杂性：=n/2

平均时间复杂性量级为O（n）

删除：平均时间复杂性：n-1/2

平均时间复杂性量级：O（n）

定位：平均时间复杂性量级：O（n）

求表长，读表元：量级O（1）

以上分析得知：顺序表的插入，删除算法的时间性能方面是不理想的。

2.3 线性表的链接实现

顺序表的优缺点：

优点：1。无需为表示结点间的逻辑关系而增加额外的存储空间。

2．可以方便地随机存取表中的任一结点。

缺点：1。插入，删除运算不方便，除表尾位置外，其他位置上进行插入和删除操作都必须移动大量结点，效率较低。

2．由于顺序表要求占用连续的空间，存储分配职能预先进行（静态分配），因此当表长变化较大时，可能造成空间长期闲置或空间不够而溢出。

链表：采用链接方式存储的线性表称为链表

一种数据结构的链接实现是指按链式存储方式构建其存储结构，并在此链式存储结构上实现其基本运算。

2.3.1单链表

单链表表示法的基本思想：用指针表示结点间的逻辑关系。

一个存储结点包含两部分：

data 部分: 称为数据域，用于存储线性表的一个数据元素。

Next部分：称为指针域或链域，用于存放一个指针，指向本结点所含数据元素的直接后继所在的结点

终端结点的指针NULL称为空指针，不指向任何结点，只起标志作用。

Head称为头指针变量，指向单链表的第一个结点的，称为头指针。

头指针具有标识单链表的作用，故常用头指针变量来命名单链表。

单链表的类C语言描述:

Typedef struct node *pointer;

Struct node

{ datatype data;

Pointer next;

};

Typedef pointer lklist;

2.3.2单链表的简单操作

为了便于实现各种运算，通常在单链表第一个结点前增设一个类型相同的结点，称为头结点。其他结点称为表

个特殊标志或表长。

1 初始化：

Lklist initiate_lklist() /*建立一个空表*/

{

t = malloc(size);

t - > next = NULL;

return(t); }

此算法说明的问题：

1．语句t = malloc(size); 有双重作用：1 由malloc自动生成一个类型为node的新结点。2指针型变量t 得到一个值即指针，该指针指向上述新结点。

2．要生成新结点必须通过调用malloc才能实现。

3．语句t - > next=NULL的作用是将头结点*t的链域置为NULL。

4．为了建立一个空表，可定义一个lklist类型的变量head,并通过调用head =initiate_lklist( )使head成为指向一个空表的头指针。

2 求表长

Int length_lklist(lklist head) /*求表head的长度，P是pointer类型的变量*/

{ p=head;

J=0;

While (p ->next!=NULL)

{ p=p->next;

J++; }

Return (j ); }

3 按序号查找

Pointer find_lklist ( lklist head ,int I ) /*在单链表head中查找第i个结点。若找到则回传指向该结点的指针，否则回传null*/

{ p= head; j=0;

While ( p->next !=NULL)&&( j

{ p= p->next; j++; }

If (i==j) return (p);

Else return(NULL); }

4 定位

Int locate_lklist ( lklist head, datatype x)

{ p=head ; j= 0;

While ( (p->next!=NULL)&&(p->data!=x))

{ p= p->next; j++;}

If p->data ==x return(j);

Else return (0);

}

5删除

Void delete_lklist ( lklist head, int i)

If ((p!=NULL)&&(p->next!=NULL))

{q=p->next;

p->next = q->next;

free (q); }

else error(‘不存在第i个结点’) }

free是库函数，结果是释放q所指结点占用的内存空间，同时q的值变成无定义。

6 插入

Void insert_lklist( lklist head,datatyped x ,int i)

{

P=find_lklist (head, i-1);

If ( p==NULL)

Error (‘不存在第i个位置’)

Else

{ s= malloc (size); s->data= x;

s->next=p->next;

p->next =s; }

2.5 其他链表

循环链表

尾结点的链域值不是NULL,而是指向头结点的指针。优点是从任一结点出发都能通过后移操作而扫描整个循环链表。

但为找到尾结点，必须从头指针出发扫描表中所有结点。改进的方法是不设头指针而改设尾指针。这样，头结点和尾结点的位置为：rear->next->next 和rear.

双链表：在每个结点中增加一个指针域，所含指针指向前趋结点。

双链表的摘除*P的操作：p->prior->next=p->next;

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

链入操作：P后面链入*q: q->prior=p; q->next=p->next; p->next->prior=q; p->next =q;

2.6顺序实现与链接实现的比较

空间性能的比较：

存储结点中数据域占用的存储量与整个存储结点占用存储量之比称为存储密度。顺序表=1，链表<1，所有顺序表空间利用率高。但顺序表要事先估计容量，有时造成浪费。

时间性能的比较：

一种实现的时间性能是指该实现中包含的算法的时间复杂性。

定位：顺序表和链表都是O（n）

读表元：顺序表O（1），链表O（n），故当需要随机存取时，不宜采用链表。

摘除，链入：顺序表O（n），链表O（1），经常需要插入删除时不宜采用顺序表。

2.7串

串是由零个或多个字符组成的又穷序列。含零个字符的串称为空串。串中所含字符的个数称为该串的长度。两个串完全一样时称为相等的。串中任意个连续字符组成的子序列称为该串的子窜，该窜称为主窜。

串的基本运算：

1．赋值：ASSIGN(S,T):加工型运算。将串变量或串常量的值传给串变量。

2．判等：EQUAL(S,T)：引用型运算，若相等返回1，否则返回0。

3．求长：LENGTH(S)：引用型运算

4．联接：CONCAT(S,T)：引用型运算。运算结果是联接在一起形成的新串。

5．求子串：SUBSTR(S,I,j)：引用型运算：结果是串S中从第i个字符开始，由连续j个字符组成的子串。当I,j参数超过范围时，运算不能执行，也没有结果。

6．插入：INSERT(S1,I,S2)：加工型运算。将串2整个插到S1的第i个字符之后从而产生一个新串。

7．删除DELETE(S,I,J)加工型运算。从串S中删去第I个字符开始的长度为J的子串。

8．定位：INDEX(S,T)：引用型运算。若串S中存在一个与T相等的子串。则结果为S中第一个这样的子串的第一个字符在S中的位置，否则，结果为0。（要求T不是空串）

9．替换：REPLACE(S,T,R)加工型运算。在S中处处同时以串R置换T的所有出现所得的新串。

串的存储：

1．串的顺序存储：紧缩格式，非紧缩格式

2．串的链接存储：将串中每个存储结点存储的字符个数称为结点大小。结点为1时存储密度低但操作方便，大于1时存储密度高但操作不方便。

第三章栈，队列和数组

3.1 栈

栈是一种特殊的线性表，栈上的插入删除操作限定在表的某一端进行，称为栈顶。另一端称为栈底。不含任何元素的栈称为空栈。

栈又称为先进后出线性表。在栈顶进行插入运算，被称为进栈，删除被称为出栈。

栈的基本运算：

1．初始化：InitStack(S):加工型运算，设置一个空栈S.

2．进栈：push（S,X）加工型运算，将元素X插入S中，使X称为栈顶元素。

3．退栈：pop（S）加工型运算，当栈不空时，从栈中删除当前栈顶。

4．读栈顶：top（S）：引用型运算，若S不空，由X返回栈顶元素，S为空时，结果为一特殊标志。

5．判栈空empty（S）：引用型运算，若S为空栈，结果为1，否则为0

3.1.2栈的顺序实现

顺序栈由一个一维数组和一个记录栈顶位置的变量组成。

空栈中进行出栈操作，发生下溢，满栈中进行入栈操作，发生上溢。

类C语言定义：

#define sqstack_maxsize 6 /*6是栈的容量*/

Typedef struct sqstack

{ DataType dada[sqstack_maxsize];

Int top;

}SqStackTP;

栈的基本运算的实现：

1．初始化

Int InitStack(InitStackTp *sq)

Return(1); }

2. 进栈

Int push(sqstackTp *sq, datatype x)

{ if (s->top == sqstack_maxsize-1)

{error(“栈满”);return 0;}

Else{sq-top++;

Sq->data[sq->top]=x;

Return(1); }

3 退栈

Int pop(sqstackTp *sq,datatype *x)

{if (sq->top==0)

{error(“下溢”);return(0);}

Else {*x=sq->data[sq->top];

Sq->top--;

Return(1); }

4 判栈空

Int emptystack(stackTp *sq)

{if sq->top==0}

Return(1);

Else return(0); }

5 取栈顶元素

Int gettop( sqstackTp *sq, datatype *x)

{if(sq->top=0) return(0);

Else{*x =sq->data[sq->top];

Return(1); }

3.1.3栈的链接实现

链栈由栈顶指针ls唯一确定。栈中其他结点通过他们的next域链接起来。栈底结点的next域为NULL。

因为链栈本身没有容量限制，所以不会出现栈满情况。

3．1.5 栈的简单应用和递归

栈与函数调用:

函数调用时，先保存的位置后返回，后保存的位置先返回。所以每遇到一个函数调用便立刻将相应的返回位置进栈，调用结束时，栈顶元素正好是此函数的返回位置。

递归与栈：

满足递归的条件：

1．被定义项在定义中的应用具有更小的尺度。

2．被定义项在最小尺度上的定义不是递归的。

3.2队列

队列也可以看成一种受限的线性表，插入限定在表的某一端进行（队尾），删除限定在另一端进行（队头）队列又称先进先出线性表。

队列的基本运算：

1．队列初始化initQueue(Q) 加工型运算，设置一个空队列Q

2．入队列enQueue(Q,X)加工型运算，将X插入到队列Q的队尾。若原队列为空，则X为原队尾结点的后继，同时是新队列的队尾结点。

3．出队outQueue(Q,X)加工型运算，若队列Q不空，则将队头元素赋给X,并删除队头结点，其后继成为新的队头结点。

4．判队列空emptyQueue(Q) 引用型运算，若队列Q为空，则返回1，否则为0

5．读队头gethead(Q,x)引用型运算，Q不空时由参数X返回队头结点的值，否则给一特殊标志。

队列的顺序实现：

队列的顺序实现由一个一维数组及两个分别指示队头和队尾的变量组成，称为队头指针和队尾指针。约定队尾指针指示队尾元素在一维数组中的当前位置，队头指针指示队头元素在一维数组中的当前位置的前一个位置。

如果按sq.rear=sq.rear+1; sq.data[sq.rear]=x和sq.front=sq.front+1分别进行入队和出队操作，则会造成“假溢出。”

循环队列的入队操作：sq.rear=(sq.rear+1)%maxsize; sq.data[sq.rear]=x

出队操作：sq.front=(sq.front+1)%maxsize;

判断循环队列队满的条件：((sq.rear+1)%maxsize)==sq.front

队空的条件：sq.rear==sq.front

3.3数组

二维数组可以看成是一个被推广的线性表，这种线性表的每一个数据元素本身也是一个线性表。

数组只有两种基本运算：

1．读：给定一组下标，读取相应的数据元素

2．写：给定一组下标，修改相应的数据元素

数组元素的存储位置是下标的线性函数，计算存储位置所需的时间取决于乘法的时间，因此，存取任一元素的时间相等。通常将具有这一特点的存储结构成为随机存储结构。

3.3.3矩阵的压缩存储

压缩存储的基本思想：值相同的多个元素只分配一个存储空间，零元素不分配空间。

要压缩的矩阵分为两种

1．特殊矩阵：对称矩阵，三角矩阵。值相同的元素或零元素的分布有一定规律叫特殊矩阵。

对称矩阵通常存储下三角，n阶方阵需要n*(n+1)/2个存储单元

三角矩阵需要n*(n+1)/2+1个存储单元，最后一个单元存储相同的常数。

2．稀疏矩阵：零元素远多于非零元素，且非零元素的分布没有规律。

用三元组表存储稀疏矩阵，只存储非零元素。(I,j,aij)

第四章树

4.1 树的基本概念

树的定义：

树是n(n>0)个结点的有穷集合，满足：

1．有且仅有一个称为根的结点。

2．其余结点分为m(m>=)个互不相交的非空集合，这些集合中每一个都是一棵树，称为根的子树。

有关术语：

树上任一结点所拥有的子树的数目称为该结点的度。度为0的结点称为叶子或终端结点。度大于0的结点称为非终端结点或分支点。一棵树中所有结点度的最大值称为该树的度。

若结点A是B的直接前趋，则称A是B的双亲或父节点，称B为A的孩子或子节点。父节点相同的结点互称为兄弟。

一棵树的任何结点（不包括根节点）称为根的子孙，根节点称为其他节点的祖先。

结点的层数（或深度）从根开始算，根的层数为1，其他节点的层数为其双亲的层数加1。树中结点层数的最大值称为该树的高度或深度。

树的基本运算：

1．求根ROOT(T) 引用型运算，结果是树T的根结点。

2．求双亲PARENT (T,X) 引用型运算，结果是结点X在树T上的双亲，若X是树T的根或X不在T上，则结果为一特殊标志。

3．求孩子CHILD(T,X,I) 引用型运算，结果是树T上结点X的第i个孩子，若X不在T上或X没有第i个孩子，结果为一特殊标志。

4．建树CREATE (X,T1…….，TK) ，K>=1，加工型运算，建立一棵以X为根，以T1…….TK为第1……K课子树的树。

5．剪枝DELETE（T,X,i）加工型运算，删除树T上结点X的第i棵子树，若T无第i棵子树，则操作为空。

4.2 二叉树

二叉树是节点的有穷集合，它或者是空集，或者同时满足下述两个条件：

1．有且仅有一个称为根的结点。

2．其余结点分为两个互不相交的集合T1,T2，都是二叉树，并且T1,T2有顺序关系，T1在T2之前，他们分别称为根的左子树和右子树。

二叉树的五种形态：

空二叉树，只含根的二叉树，只有非空左子树的二叉树，只有非空右子树的二叉树，同时有非空左右子树的二叉树。

二叉树的基本运算：

1．初始化INITIATE(BT) 加工型运算，作用是设置一棵空二叉树

2．求根ROOT(BT)引用型运算，结果是二叉树BT的根节点，若BT为空二叉树，结果为一特殊标志。

3．求双亲PARENT(BT,X) 引用型运算，结果是结点X在二叉树BT上的双亲，若X是根或不在BT上，结果为一特殊标志

4．求左孩子LCHILD(BT,X)右孩子RCHILD(BT,X)引用型运算，结果分别为结点X在BT上的左，右孩子。若X 为BT的叶子或X不在BT上，结果为一特殊标志。

5．建树CREAT(X,LBT,RBT)加工型运算，建立一棵X为结点，LBT,RBT为左右子树的二叉树。

6．剪枝DELETEFT(BT,X)和DELETEHT(BT,X)加工型运算，删除BT结点X的左右子树，若无，运算为空。

二叉树的性质：

1．二叉树第i(i>=1)层上至多有2i-1个结点。

2．深度为K（k>=1）的二叉树至多有2k -1个结点。

3．对任何二叉树，若2度结点数为n2,则叶子数n=n2+1

深度为K（K>=1）且有2k-1结点的二叉树为满二叉树，在第K层删去最右边连续J个结点，得到一棵深度为K的完全二叉树。

完全二叉树的性质：|_x|表示不大于X的最大整数。

1．具有N个结点的完全二叉树的深度为|_|+1

2．将一棵有n个结点的完全二叉树按层编号，则对任一编号为i的结点X有：

若i=1，则结点X是根，若i>1，则X的双亲parent（X）的编号为|_i/2|

若2i>n,则结点X无左孩子（且无右孩子），否则，X的左孩子LCHILD(X)的编号为2i.

若2i+1>n,则结点X无右孩子，否则,X的右孩子RCHILD(X)的编号为2i+1

4.3 二叉树的存储结构

二叉树的链式存储结构：

二叉链表在做求双亲运算时效率不高，此时可采用三叉链表。

具有n个结点的二叉树中，一共有2n个指针域，其中只有n-1个用来指向结点的左右孩子，其余的n+1个指针域为NULL.

P81

4.3.2二叉树的顺序存储结构

按层编号然后存储。

对于非完全二叉树，可采用增加虚结点的方式转化成完全二叉树再进行存储。虚结点在数组中用特殊记号表示。但同时会浪费存储空间。

4.4. 二叉树的遍历

遍历一棵二叉树就是按某种次序系统地“访问”二叉树上所有结点，使每个节点恰好被访问一次。

先根遍历：1 访问根结点 2 先根遍历左子树3先根遍历右子树

中根遍历：1中根遍历左子树 2 访问根结点3中根遍历右子树

后根遍历：1后根遍历左子树2后根遍历右子树3访问根结点。

4.6 树和林

树的存储结构：P93

1．孩子链表示方法：头结点分为数据域和指针域，表结点分为孩子域和指针域

可以在头结点中增加双亲域，称为带双亲的孩子链表示方法。

2．孩子兄弟链表示法：存储结点均含三个域：数据域，孩子域（存放指向本结点第一个孩子的指针），兄弟域（存放指向本结点下一个兄弟的指针）。

3．双亲表示法：数据域，指针域（指示本结点的双亲所在的存储结点）

将指针域定义为高级语言中的指针类型的链式存储结构成为“动态链表”，相应的指针成为动态指针。

将指针域定义为整形，子界型的链式存储结构成为静态链表，相应的指针称为静态指针。

动态链表的结构通过库函数malloc（size）动态生成，无需事先规定表的容量。而静态链表容量须事先说明。

4.6.2树的遍历

1．先根遍历：若树非空1 访问根结点2依次先根遍历根的各个子树

2．后根遍历： 1 依次后根遍历根的各个子树2 访问根结点

3 层次遍历： 2 访问根结点2从左到右，从上到下依次访问每层。

二叉树与树，林的关系P97

将二叉树的二叉链表和数的孩子兄弟链表的左孩子指针，右孩子指针和孩子指针，兄弟指针对应起来。

与树对应的二叉树的右子树一定为空。

判定树和哈夫曼树

用于描述分类过程的二叉树称为判定树。判定树的每个非终端结点包含一个条件，因而对应于一次比较火判断，每个终端结点包含一个种类标记，对应于一种分类结果。

哈夫曼树：

给定一组值p1……pK，如何构造一棵有k个叶子且分别以这些值为权的判定树，使得其平均比较次数最小。满足上述条件的判定树称为哈夫曼树。

第五章图

图中的小圆圈称为顶点，连线称为边，连线附带的数值称为边的权。

任何两点间相关联的无向图称为无向完全图，一个N个顶点的完全无向图的边数为n(n-1)/2.

任何两顶点间都有弧的有向图称为有向完全图。一个N个顶点的有向完全图弧数位n(n-1)

每条边或弧都带权的图称为带权图或网。

一个连通图的生成树，是含有该连通图的全部顶点的一个极小联通子图。

若连通图的顶点个数位N,则生成树的边数为N-1,如果它的一个子图的边数大于N-1,则其中一定有环，如果小于，则一定不连通。

5.2 图的存储结构

邻接矩阵

对于无向图，顶点VI的度是矩阵中第I行（或列）的元素之和。

对于有向图，行元素之和为出度，列元素之和为入度。

邻接表

为每个顶点建立一个单链表，单链表中每个结点称为表结点，包括两个域，邻接点域，用以存放与VI相邻接的顶点序号，链域，用以指向同VI邻接的下一个的顶点。

另外，每个单链表设一个表头结点。每个表头结点有两个域，一个存放顶点VI的信息，另一个指向邻接表中的第一个结点。

若一个无向图有N个顶点，E条变，则它的邻接表需要N个头结点和2E个表结点，所以在边稀疏的情况下，用邻接表比邻接矩阵更节省存储空间。

对于无向图，第I个单链表中的结点个数即为VI的度。

对于有向图，第I个单链表中的结点个数只是VI的出度，为求入度，必须遍历整个邻接表，所有单链表中，邻接点域的值为I的结点个数即为入度。

有时为了方便的求入度，可以建立逆邻接表。

5.3 图的遍历

从图中某一顶点出发访遍图中其余顶点，每个顶点仅访问一次，叫做图的遍历。

增设visited[n]数组。初值为0,vi被访问后，置为1

遍历方法：深度优先搜索和广度优先搜索。

最小生成树问题

拓扑排序

第六章查找表

集合的特点：在集合这种逻辑结构中，任何结点间都不存在逻辑关系。

用来标识数据元素的数据项称为关键字，简称键，该数据项的值称为键值。

静态查找表：以集合为逻辑结构，包括三种基本运算

1．建表CREATE(ST) 加工型运算，生成一个由用户给定的若干数据元素组成的静态查找表ST.

2．查找SEARCH(ST,K)引用型运算，若ST中存在键值等于K，结果为该键在ST中的位置，否则为一特殊标志

3．读表元GET(ST,pos)引用型运算，结果是pos位置上的数据元素。

动态查找表：包括查找，读表元（同上）和以下三种基本运算。

1．插入INSERT(ST,K)加工型运算，若ST中不存在键值等于K的数据元素，则将一个键值等于K的数据元素插入到ST中。

2．删除DELETE(ST,K)加工型运算，删除ST中键值等于K的数据元素。

3．初始化INITIATE(ST)加工型运算，设置一个空的动态查找表。

6．2 静态查找表的实现

6.2.1顺序表上的查找

顺序查找法：从表的第n个位置开始，从后往前依次将各个位置上的数据元素的键值与给定值K比较。若相等，回送该位置作为结果。若不等，查找不成功。

在第0个单元设置哨岗，所有当查找不成功时，查找了n+1次。

平均查找长度ASL=（N+1）/2

6.2.2有序表的查找

二分查找法

当N较大时，ASL约等于-1

6,2,3 索引顺序表上的查找

索引顺序表由顺序表和索引表两部分组成。

两个特点：1 顺序表中的数据元素按块有序 2 索引表反映了这些快的有关特性（块内最大键值和块的起始位置）

分块查找法

平均查找长度高于顺序查找而低于二分查找。

6,3树表

6.3.1 二叉排序树

一棵二叉排序树或者是一棵空树，或者同时满足下列三个条件：

1．若它的左子树不空，则左子树上所有结点的键值均小于它的根结点的键值。

2．若它的右子树不空，则右子树上所有结点的键值均大于它的根结点的键值。

3．它的左右子树也分别是二叉排序树。

二叉排序树的中根遍历所得排序是从小到大。

二叉排序树的插入，删除后仍要保持是一棵二叉排序树。

删除时：设待删结点为P,双亲结点为F.设P是F的左孩子。

1．P为叶节点，直接置F的左指针域为空。

2．P只有一棵非空子树，直接以其根节点代替P的位置。

3．P有两颗非空子树，可用左子树根结点代替P,然后将右子树变为新的根节点的右子树。

6.3．2 平衡二叉排序树

一棵平衡二叉排序树AVL树，或者是空树，或者是一棵任一结点的左子树与右子树的高度至多差1的二叉排序树。

调整方法：

P140

6．4 散列表

散列函数是一种将键值映射为散列表中的存储位置的函数。

由散列函数决定的数据元素在散列表中的存储位置称为散列地址。

散列的基本思想是通过散列函数决定的键值与散列地址间的对应关系实现存储组织和查找运算。

散列函数的构造法：

1．数字分析法（需要事先知道大概的键值）2 除余法 3 平方取中法 4 基数转换法5随机数法

第八章排序

假定待排序的序列中存在多个记录具有相同的键值。若经过排序，这些记录的相对次序保持不变，称这种排序的方法是稳定的，否则是不稳定的。

按照排序过程涉及的存储设备的不同，分为内部排序和外部排序。内部排序指排序过程中，数据全部存放在计算机内存中，并在内存中调整记录间的相对位置。外部排序指排序过程中，数据的主要部分存放在外存中，借助内存逐步调整记录间的相对位置。

排序以键值比较和记录移动为标准操作。

8.2插入排序

分为直接插入排序，折半插入排序，表插入排序和希尔排序。

直接插入排序，方法是稳定的，时间复杂性为O(N2),空间来看，只需要一个记录的辅助空间，故空间复杂度为O（1）。

8.3交换排序

根据序列中两个记录键值的比较结果来兑换这两个记录在序列中的位置。特点是，将键值较大的记录向序列尾部移动，键值较小的记录向序列前部移动。

8.3.1冒泡排序

至多需要进行N-1趟起泡。

时间复杂性为O（n2），稳定的排序方法。

本资料由广州自考网收集整理，更多自考资料请登录https://www.wendangku.net/doc/2812414152.html,下载考试必看：自考一次通过的秘诀！

自考英语(一)课堂笔记完整版(6)

自考英语（一）课堂笔记完整版（6） Unit3（第7讲—第10讲） 4. One idea was that it reached out to “the edge of the world”。 Another idea was that at the equator the ocean would be boiling hot. 这两个都是表语从句和主句中的系动词连用的句子。结构为：主语＋系动词＋表语从句。请看下面的例句：My idea is that we contact him as soon as possible.（我的想法是我们应该尽快跟他联系。）请翻译下面的句子： 1）My suggestion is that we should put off the meeting.（我的建议是我们应该把会议延期。） 2）One advantage of solar energy is that it will never be used up.（太阳能的一个优点是用之不竭。） 3）问题是你不在时谁照管孩子。（The problem is who will take care of the children while you are away.） 4）看起来天要下雨。（It looks that it is going to rain.）请注意辨析another 和other： another由an＋other构成，只和单数可数名词连用。other可用于所有名词前。another＋单数名词表示不定的“另一个”，the other＋单数可数名词表示特指的“另一个”。请看下面的例句： 1）This idea is not very practical，will you think of another one？（这个主意不太实际，你能另想一个吗？） 2）This book is too difficult. Show me another one.（这本书太难了，给我看另外一本。） 3）Of the three books in my bag，two are published in China，the other is published in the United States.（我包里的三本书中，两本是中国出版的，另一本是美国出版的。） 4）Tom is here，but where are the other boys？（汤姆在这儿，其他的男孩在哪儿呢？） 5）I like this coat better than the other one.（两件上衣中，我更喜欢这一件。） 6）This camera is more expensive than the other one.（这架照相机比另一架贵。） boiling hot意思是“滚热的，酷热的”。此处的boiling不是形容词而是副词，表示热的程度，修饰hot. 5. Sailors were afraid that they might sail right off the earth. 此句中，that引导的名词性从句作形容词的补足语。例如： 1）I am afraid that I can not finish the article in two hours.（我担心我两小时内写不完这篇文章。）

自考英语二复习资料汇总总结

重点单词扩充讲解： 1. organizational: a 组织上的由此我们可以联想到：organize: v 组织；organization: n 组织；organizer: n 组织者请看下列习题，选择该组词里恰当的词填空： 1). Last week, our school __organized_____ a spring outing. 2). The task calls for the highest _organizational_ skill. 3). China has joined World Trade _organization_________. 4). He is the ____organizer______ of the speech contest. Answers: organized, organizational, Organization, organizer 2. objective: n 目标； a 客观的，反义词subjective: 主观的 3. predict: v 预言、预示；由此我们可以联想到：prediction: n 预言；predictable: a 可预测的；predictor: n 预言家 4. simplify: v 简化由此我们可以联想到：simple: a 简单的；simply: ad 简单地，仅仅地；simplification: n 简化；simplified: a 被简

Exercises for the above words: 1). The machine is simple_____ in operation but complex in structure. 2). Shakespeare’s Romeo and Juliet in the original is beyond our capacity while __simplified__ edition is quite easy. 3). There is no point in arguing about it, becau se it is __simply_____ a question of procedure. 4). The _simplification_____ of working process freed the workers fro heavy labor. Answers: simple; simplified; simply; simplification 5. tendency: n 趋势、倾向；tend : v 倾向于…，tend to do sth e.g. old people have the tendency of getting fatter. Or old people tend to get fatter. 6. managerial: a 经理的、经营上的；由此我们可以联想到：manage: v管理、经营；management: n; manager: n 经营者，管理者；manageable: a 可管理的、可经营的。 7. argue: v 争辩、争论，常用固定搭配：argu with sb about/over sth由于某事而同某人争论；argue sb into doing sth说服某人做某事；argue sb out of doing sth说服某人不

【精品】自考行政法与行政诉讼法一串讲笔记

自考行政法与行政诉讼法（一）串讲笔记第一编绪论第1章行政法的基本概念第一节行政一、行政的涵义 1。行政的概念 (名词解释）行政在行政法上的意义,通常指国家行政机关执行国家法律、政策，管理国家内政、外交的活动。 2。行政的分类考察 1 / 241

(1）公行政与国家行政. （名词解释）狭义的行政仅包括公行政，指公共组织，主要指国家行政机关为实现公共目的、任务而行使的执行、管理职能. （单选）国家行政属于公行政，但公行政并不等于国家行政. (2）静态行政和动态行政。（单选）静态行政的涵义是被赋予相应职能的组织单位和个人，指行政机关、行政机构、行政人员；动态行政的涵义是相应组织职能的运作，指行政活动、行政行为。 (3）形式行政和实质行政。（单选）行政执法属于实质行政。形式行政是根据主体的性质界定的行政，即只有国家行政机关进行的活动为行政;实质行政是根据主体活动的性质界定的行政，即不论主体为何公权力机关，只要其活动具有执行、管理的性质，即为行政. 2 / 241

二、行政与行政国（单选)行政法作为一个独立的法律部门,是伴随着“行政国”的产生而产生的。三、行政与法治国（单选）“行政国”产生是行政法产生和发展的基本原因,而行政法产生和发展是法治国形成的基本条件。第二节行政法一、行政法的涵义（名词解释)（05-4)（02—4)行政法是指调整行政关系，规范和控制行政权的法律规范系统。 (多选）(05—4）(02-4）行政法的内容是由行政法的调整对象决定的。行政法的调整对 3 / 241

象是行政管理关系；行政法制监督关系;行政救济关系；内部行政关系。（多选）（06—4)（03-4）属于行政管理关系的有劳动局实施行政处罚与被处罚人之间形成的关系、劳动局登记检查企业用工情况与企业之间形成的关系。（单选)海关系统的内部关系，属于垂直领导关系。二、行政法与行政权（多选)行政权从其权力内容考察，包括国防权、外交权、治安权、经济管理权、社会文化管理权等. 三、行政法的形式 4 / 241

自考公共英语(一)课文翻译(unit22)

自考公共英语（一）课文翻译（unit22） -自考串讲笔记 Unit 22 Text A 当今人们对健身的态度最近一位学生对我们说，抽出时间来增进身体健康完全是在浪费学习时间。他要我们相信，对他来说，健身运动一点也不比学打桥牌更有用。上大学和为将来的职业做准备才是他的当务之急。这个学生把身体健康看成是一种目的，而不是我们所认为的手段。人们对于个人参加体育锻炼所持意见很多，赞成的或反对的都有，他的观点只是其中的一种。很多人，包括不同年龄的大学生，用在健身活动上的时间很少。当然这里有些人可能受到身体条件的限制，运动起来非常困难，而另一些人从事的活动很费时间，只有完成之后才有机会去休闲娱乐。然而，那些能更多参加健身活动而实际上却参加得很少的大多数人又如何呢下面的哪句话更符合你说的 “我知道这很重要，但我只是现在没有时间。” “我已经很健康，而且按我的计划，保持下去没有困难。” “我应该参加得比现在多，但我没有健身器材，别人也不太支持我。”

“锻炼使我感觉糟透了，即使淋浴之后，我去上下一节课时还是浑身是汗，闻起来大概有些更衣室的味道。” 你与那些没有做出承诺的人不同，也许已承诺投入一项健身计划，但你这项活动的范围可能是比较狭隘的。如果下列某一议论和你一致，那么也许你还没有看到保持高水平的身体健康所具有的更广泛的价值。 “宿舍中每个人都在晚上跑步，所以我也跑。” “锻炼时间每消耗3500卡热量，我就可以减少一磅指肪。圣诞节之前我只需要再减十磅。” “这个周末天气凉爽宜人。星期六看起来是创造个人纪录的好日子。” “有些人可能会说我怕死。见鬼，我只是想长寿。” 如果你看到这些议论中有一条正好代表了你的态度，那么你衡量健身价值的理由不是有点近视吗我们建议你重新审视自己对健身的态度和健身对你生活其它方面的积极影响。你应该问问自己，“如果我真的处于身体最佳状态，我会取得什么成就”因为身体强健的程度很容易观察和测出，你可以很快开始看到你有能力成为的那个正在脱颖而出的人。几乎每天你都能看到进步和成就，不过请记住，人各不同，有些人会比别人进步得快。归根结底，我们认为虽然健身不能保证你活得更长，但却有助于你享受你的人生。 Unit 22

自考英语笔记2

Unit 2 Text A Taxes，Taxes，and More Taxes 搭配： 1. be sure of 确保、一定、毫无疑问/形容词词组 2. have a corner in/on sth. 垄断/动词词组 e.g. have a corner on the textile market 垄断纺织市场 have a corner in textile 对纺织品进行垄断 3. lead the world with sth. 以什么来引领世界/动词词组 4. vary in sth. 有差异 e.g. vary in ideas 想法有差异 vary sth. 改变 e.g. vary your attitude 改变你的观点 vary with 随什么而改变 vary from sth./sb. to sth./sb. 什么什么各不相同 e.g. vary from person to person 人人不同vary from place to place每个地方各不相同 5. sth. is due. 到了该什么的时间了。e.g. The federal taxes are due. 到了该收税款的时间了 6. be similar to 与什么一样/形容词词组 7. buy sth. for +多少钱/动词词组 e.g. buy a packet of cigarettes for twenty-five cents. 8. in addition to sth./doing sth.除了（表示加的概念）/名词词组 e.g. In addition to teaching，she is in charge of managing the whole school. In addition to his flat in Chaoyang，he has anther flat in Haidian. 9. in two forms 以两种形式 10. charge on sth. 收取什么的费用 e.g. charge on cars in a city.收取城内汽车的费用。 be charged with被控诉有某种罪行；be charged by sb. 由某人收取费用 charge for 收取多少价钱e.g. How much do you charge for this car？这辆车你要多少钱？ in charge 负责 e.g. Who is in charge here？谁在这负责？

自考本科英语二复习资料

自考“英语（二）”复习资料第一单元 1.常考单词： goal，objective，accomplish，predict，accompany，implement，tendency，achievement，argue，budget，define，entity 2. 常考词组： in the way，in part，point of view，contribute to，to apply for，in hand，to turn down 3. 常考句子： 1）A decision is a choice made from among alternative courses of action that are available. 2）Often managers must make a best guess at what the future will be and try to leave as little as possible to chance. 3）If there is no choice，there is no decision to be made. 4）For managers every decision has constraints based on politics，procedures，laws，precedents and the like. 5）For example，managers sometimes treat problems in an either/or fashion. 6）Decision makers must have some way of determining which of several alternatives is best - that is，which contributes the most to the achievement of organizational goals. 7）In the larger scheme of things，however，increased funding for research to improve the products might be more beneficial to the organization. 8）Some of these objectives are more important than others，but the order and degree of importance often vary form person to person and from department to department. 第二单元 1.常考单词： escape，explode，collapse，shrink，gravity，measurement，basis，launch，convincing，companion，speculation，swallow，operate，to make use of，a great many，above all 2. 常考句子： 1）Astronomers and scientists think that a black hole is a region of space into which matter has fallen and from which nothing can escape. 2）The theory is that some stars explode when their density increases to a particular point. 3）Some people think that the Start of Bethlehem could have been a supernova. 4）If a man fell into a black hole，he would think that he reached the center of it very quickly. 5）It is only recently that astronomers have begun specific research into black holes. 6）On the other hand，scientists have suggested that every advanced technology could one day make use of the energy of black holes for mankind. 第三单元 1.常考单词： weaken deteriorate debate legal request criterion ensure oppose tradition consideration disabled burden vulnerable prohibition sensitive 2. 常考词组： to debate on to make request for be opposed to to take … into account 3. 常考句子： 1）Affected with a serious disease，van Wendal was no longer able to speak clearly and he knew there was no hope of recovery and that his condition was rapidly deteriorating. 2）Van Wendel's last three months of life before being given a final，lethal injection by his doctor were filmed and first shown on television last year in the Netherlands. 3）The programme has since been bought by 20 countries and each time it is shown，it starts a nationwide debate on the subject. 4）What those people who oppose euthanasia are telling me is that dying people haven't the right. 第四单元 1.常考单词： demestic statistics diplomat exploit campaign execute convict despite de serving shelf minimum status deport 2. 常考句子： 1）There are estimated to be more than 20，000 overseas domestic servants working in Britain. 2）Of these 20，000，just under 2，000 are being exploited and abused by their employers. 3）The sad condition of women working as domestics around the world received much media attention earlier this year in several highly publicized cases. 4）A Filipino maid was executed in Singapore after being convicted of murder，despite protests form various quarters that her guilt had not been adequately established. 5）She used to work for a very low wage at a tea factory in Sri Lanka. 6）Because she found it difficult to feed her four children，she accepted a job working as a domestic in London. 7）So if they do complain，they risk being deported. 第五单元 1.常考单词： Musician，rhythmic，distinct， consciousness，originate，readily， instrument，electronic，thereby， passive，participant 2. 常考词组： to take place to take over to take on in a sense at a stretch to serve as in advance for the sake of 3. 常考句子： 1）The new music was built out of materials already in existence. 2）Folk music，old and modern， was popular among college students. 3）They freely took over elements form jazz，from American country music. 4）With records at home， listeners imitated these lighting effects as best they could. 第六单元 1.常考单词： efficiency increasingly inst all personnel expose reduc tion completion specific s witch critical intensity s cale defective 2. 常考词组： in that in question plenty of 3. 常考句子： 1）Most of today's robots are employed in the automotive industry，where they are programmed to take over such jobs as welding and spray painting automobile and truck bodies. 2）Robots，already taking over human tasks in the automotive field are beginning to be seen，although

自考英语重点语法

自考英语重点语法动名词在句子中的作用动名词是一种非限定动词，其构成同现在分词一样，即在动词原形后加-ing，在形式上同现在分词没有任何区别。动名词的用法并不算很复杂，但出现的频率却非常高，是考试常考语法项目，因此应该格外引起学生的注意。动名词在句子中不受主语的人称和数的制约，但不能做谓语。 1.作主语动名词及其短语可以用来作主语，跟一般名词或代词在句子中作主语一样，有自己的谓语/表语、宾语等等，组成完整的句子。如：Smoking does a lot of harm to one's health. （吸烟对人体非常有害。） Reading different kinds of books can enlarge your range of knowledge. （阅读各类书籍能扩大你的知识面。）但是，动名词作主语有两种特殊句型，那就是由"it"作形式主语和"there"作先行主语的两种句型。这两种特殊句型正是学生常常忽略的地方。因此，必须给予足够的重视。（1）“it”作形式主语的句型。这种句型常常表现在下列结构中： It is no good... It is not much good... It is no use... It is hardly any use... It is useless... It is not any use... It is little use... It is hardly worth... It is worth... It is worthwhile... It is a waste of time... It is difficult... It is a waste of time arguing with him. （跟他辩论是在浪费时间。） It was no use talking without taking any action. （只说不做是没有用的。）（2）“there”作先行主语的句型。这种句型通常用在否定句中，其基本形式是there is/was+动名词。 There is no denying the fact. （事实不容否认。） There is no joking over this matter. （这种事开不得玩笑。） There is no telling what she will be after she grows up. （说不准她长大后会干什么。）动名词在句子中的作用 2.动名词作表语动名词作表语形式上同进行时态一样，由be+动词-ing形式构成，但它所表达的是主语“是什么”，而不是主语“正在干什么”。 The only thing that Smith likes to do after his dinner is watching TV. （史密斯饭后唯一喜欢做的事就是看电视。） The most important thing is finding the most suitable person for this job. （最重要的事情是找到这个工作最适合的人选。） Seeing is believing. （眼见为实。）我们知道，不定式也同样可以作句子的主语和表语，所表达的意义也非常接近，但两者也有一定的区别：一般说来，动名词多表示一般行为和状态，而不定式则强调具体某次动作以及将来要发生的动作。动名词在句子中的作用 3.动名词作同位语同位语是用来说明所修饰的名词，是对该名词的进一步解释，起一个补充说明作用。动名词作同位语也起同样的作用。 His hard habit, smoking one cigarette after each meal, remains unchanged for fifty years. （他饭后一支烟这个恶习五十年没有改变。） That's my pride, speaking five languages.

自考英语(一)课堂笔记完整版(2)

自考英语（一）课堂笔记完整版（2） Unit1 4. They need hundreds of hours of study and practice，and even this will not guarantee success for every adult language learner. 注意句中hundreds of hours的用法，阅读课本第六页注解2. 请翻译下面的词组： 1）十个学生 ten students 数十个学生 tens of students 2）五百年 five hundred years 数百年hundreds of years 3）两千年 two thousand years 数千年 thousands of years 4）三百万美元 three m illion dollars 数百万美元m illions of dollars 5. Language learning is different from other kinds of learning. 句中be different from意为“与…不同”，如：My opinion is different from yours.（我的观点与你的观点不同。）请注意下面三个句子中所用的词组： Man is different from all the other anim als in his ability to learn and use a language. Man differs from all the other anim als in his ability to learn and use a language. The greatest difference between m an and all the other anim als is his ability to learn and use a language. 从上面的句子中可以看出differ是动词，different 是形容词，difference是名词。 6. … find it difficul t to succeed in language learning. … find it difficul t to succeed in other fields. 句中的i t是形式宾语（form al object），真正的宾语（real object）是不定式to succeed in language learning，此类用法在英语中很常见，请注意掌握。如：At first I found it diffi cult to rem em ber all these new words.（开始我感到记住这些单词很难。）请翻译下面的句子： 1）外面的噪音使我无法继续工作。（The noise outside m ade it diffic ult for m e to go on with m y work.）

自考英语二重点语法知识讲解

重点语法知识讲解 1．动词的时态和语态动词的时态和语态一览表时态语态一般现在时一般过去时一般将来时主动被动 do are done did were done will do will be done 现在进行时过去进行时将来进行时主动被动 are doing are being done were doing were being done will be doing现在完成时过去完成时将来完成时主动被动 have done have been done had done had been done will have done will have been done 现在完成进行时主动被动 have been doing 1．1 现在完成时发生在过去的动作一直持续到现在，或对现在仍有影响。现在完成时的标志： so far， by now/ up to now，for three years， since 1995， in the past two decades 1.2 过去完成时过去的过去。 1）said, reported, thought 等引导的间接引语中。 He missed the train. He said he had missed the train. 2）hardly…when, no sooner… than句型中表示先发生的动作 No sooner had he got up than he received the call. 3）与过去事实相反的虚拟语气中

If I had tried harder, I would have won. I wish I had done better in the exam. 1.3 完成进行时从过去一直持续到现在，没有间断。汉语提示语：一直 The water has been running the whole night. 1.4 过去时过去某一具体时间发生的事，不考虑与现在的关系。过去时的标志：yesterday， in 1995， last week，in the nineteenth century，five years ago 等等。 2．非谓语动词 2.1 非谓语动词一览表非谓语动词形式意义现在分词一般式 doing 主动 , 正在进行被动式 being done 被动 , 正在进行完成主动式 having done 主动 , 已经完成完成被动式 having been done 被动 , 已经完成过去分词 done 被动 , 已经完成动词不定式一般式 to do 主动 , 将要进行被动式 to be done 被动 , 将要进行完成主动式 to have done 主动 , 已经完成进行主动式 to be doing 主动 , 正在进行 2.2. 非谓语动词作状语

自考英语语法笔记1_第一章_绪论

第一章绪论the structure of English sentence 1.0 introduction -- The grammar unites hierarchy Higher 1.2 Words 1.2.1 Words Class

1.2.2 word formation 构词法 a. Affixation 词缀法List具体见书9-10页英语分前缀后缀和中缀，前缀加在词根之前，改变词义不改变词类。后缀加在词根之后，改变词类不改变 b. Composition 复合法两个或者两个以上的独立词构成一个复合词。 E.g.: manservant, snowfall, deadline, spotlight, world-famous, before-tax, whenever, whereas… c. Convention 转化法某个单词未经添加此罪就由一个词类转化为另一个词类。 Verbs to nouns: love, answer, doubt. Adj. to verbs: daily(=daily newspaper), final(=final exam) d. Blending 拼缀法把两个词经行裁剪，掐头去尾，然后把这两个不完整的部分拼成一个词，在某些情况下只裁剪两个词中的一个词，把一个不完整的词和一个完整的词拼成另一个词。 P+P Motel (Motor + Hotel) Smog (Smoke + Fog) Brunch (Breakfast + Lunch) W+P newscast (News + Broadcast) Workfare (Work + Welfare) P+W Medicaid (Medical + Aid) Medicare (Medical + Care) e. Back-formation 逆生法英语中有很多-or,-er结尾的名词是由动词派生而来，但也不乏通过去掉这些名词词尾派生出来的动词。 e.g. Housekeep –Housekeeper Babysit – Babysitter

英语二复习笔记6

4、解题思路及答题技巧两大原则：（1）先做主观题，再做客观题。（2）按分值合理分配时间。 1.完型填空：（1）上看下看，左看右看，充分利用上下文。（2）熟记固定搭配。 For over a hundred years Japan has consistently spent large sums of money and considerable human resources in an effort to obtain technology. Her ability to negotiate _________11 by the fact that most of the technology she wanted was no commercial secrets. Japan’s _________12 has also been strengthened by the fact that her internal market was large，so that _________13 to this market could be offered to multinational companies as an attraction to them to grant licenses. Besides，Japan’s work force was disciplined，so it was capable _________14 applying the information it acquired. Finally，American and European companies，who were _________15 licensers，felt that the Japanese companies might take a large share of the world market _________16 they were not limited by licensing agreement.

自考英语心得范文

自考英语心得范文才的有关规定，造就和选拔德才兼备的专门人才，提高全民族的欢! 自考英语心得范文一加自考专升本学习，经过一年多的学习，顺利通过了专升本课程以及加考的水平英语(一)、水平英语(二)和综合英语(二)课程。应该说，对于比较难学的英语专业，我算是在比较短的时间内取得在此与大家交流。滴的积累达到的，从量变上升到质变，即所谓的平时有好的学习习惯，才会使我们最终取得好的成绩。所以在平时的学习当中就要严格要求自己，力求扎实的功底，为日后的考试做好准备。

习惯的养成还源自对自考的正确认识。高等教育自学考试是高等教育中较为严格、对考生要求较高的一种自学形式，要想通过考试，就要有较强的自控力和坚持不懈的恒心。其中自控力是坚持不懈的保证，没有较强的自控能力，基本的学习时间无法保在此我就谈谈我的学习习惯。读，其他课程如公共课若时间不足，可注意上课笔记。二、坚听挺好每一堂课，知识的积累重在平时的点点滴滴，虽然一些需要记忆的课程，临阵磨枪有一定的作用，但基础课程仍在于平时的功夫，在于潜移默化，扎扎实实，稳步提高。三、及时的针对所学内容作总结、联系。即对所学课程及时四、考前要做的工作。大致读一遍课文，然后有针对性的增加习题训练，起到查漏补缺的作用，最后做一些模拟题型、模式。五、在不面临国考压力时，也不能松懈，而应主动培养自己的英语意识，多听英语广播、音乐，以及多看英语方面的书籍与节目等，同时如有充裕时间，可针对自身的弱点有选择的参加一些辅导班。

除了以上这几点，我认为还需要时时保持一种紧张状态，即在规定课程未全部达到要求之前，绝不能有所放松，从而争取最后的胜利。这是我的体会。我认为通过考试拿文凭不是我们的目的，更多的是为了获取真正的知识以及更好的掌握知识，为我们将来的学习和事业打下坚实的基础。所以，在努力通过考试的同时，也应注意培养自身的能力，包括运用知识的能力，适应社会的能力等。在学习的过程中，注意磨砺自己的意志，培养积极、向上、乐观的心理状态，从而迎接人生中的每一次挑战和考验。最后，我要说的是，既然大家选择了这条学习道路，就应该有恒心、有耐心并且有信心，要相信：付出的汗水中终将获得收获，这段经历将成为我们人生中特有的宝贵的财富，也将成为教会我们懂得珍惜人生的一次机会。让我们共同努力，为最后的胜利而奋斗! 自考英语心得范文二我2001年大学毕业以后一直在北京从事英语教育行业，因为一个偶然的机会我接触到了一个自考学校，我发现相当多的自考学生的英文功底不好，要想通过公共科目英语(一)(二)十分的不容易，所以我现在正在筹划开办一个校内的英语补习培训班，

自考02142《数据结构导论》串讲笔记

自考英语(一)课堂笔记完整版(6)

自考英语二复习资料汇总总结

【精品】自考行政法与行政诉讼法一串讲笔记

最新专升本英语语法重点汇总

自考公共英语(一)课文翻译(unit22)

自考英语笔记2

自考本科英语二复习资料

自考英语重点语法

自考英语(一)课堂笔记完整版(2)

自考英语二重点语法知识讲解

自考英语语法笔记1_第一章_绪论

英语二复习笔记6

自考英语心得范文