数据结构笔记数据结构

第一章概论

1.数据：信息的载体,能被计算机识别、存储和加工处理。

2.数据元素：数据的基本单位，可由若干个数据项组成，数据项是具有独立含义的最小标识单位。

3.数据结构：数据之间的相互关系，即数据的组织形式。

它包括：1）数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，独立于计算机；

2）数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。

3）数据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用的运算：检索/插入/删除/更新/排序。

4.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的存储结构是逻辑结构用计算机语言的实现。

5.数据类型：一个值的集合及在值上定义的一组操作的总称。分为：原子类型和结构类型。

6.抽象数据类型：抽象数据的组织和与之相关的操作。优点：将数据和操作封装在一起实现了信息隐藏。

7. 抽象数据类型ADT：是在概念层上描述问题；类：是在实现层上描述问题；在应用层上操作对象（类的实例）解决问题。

8.数据的逻辑结构，简称为数据结构，有：

（1）线性结构，若结构是非空集则仅有一个开始和终端结点，并且所有结点最多只有一个直接前趋和后继。

（2）非线性结构，一个结点可能有多个直接前趋和后继。

9.数据的存储结构有：

1）顺序存储，把逻辑相邻的结点存储在物理上相邻的存储单元内。

2）链接存储，结点间的逻辑关系由附加指针字段表示。

3）索引存储，存储结点信息的同时，建立附加索引表，有稠密索引和稀疏索引。

4）散列存储，按结点的关键字直接计算出存储地址。

10.评价算法的好坏是：算法是正确的；执行算法所耗的时间；执行算法的存储空间（辅助存储空间）；易于理解、编码、调试。

11.算法的时间复杂度T(n)：是该算法的时间耗费，是求解问题规模n的函数。记为O(n)。

时间复杂度按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、……k次方阶O(n^k)、指数阶O(2^n)。13.算法的空间复杂度S(n)：是该算法的空间耗费，是求解问题规模n的函数。

12.算法衡量：是用时间复杂度和空间复杂度来衡量的，它们合称算法的复杂度。

13. 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。

第二章线性表

1.线性表：是由n(n≥0)个数据元素组成的有限序列。

2.线性表的基本运算有：

1）InitList(L),构造空表，即表的初始化；

2）ListLength(L),求表的结点个数，即表长；

3）GetNode(L,i),取表中第i个结点，要求1≤i≤ListLength(L)；

4）LocateNode(L,x)查找L中值为x的结点并返回结点在L中的位置，有多个x则返回首个，没有则返回特殊值表示查找失败。5）InsertList(L,x,i)在表的第i个位置插入值为x的新结点，要求1≤i≤ListLength(L)+1；

6）DeleteList(L,i)删除表的第i个位置的结点，要求1≤i≤ListLength(L)；

3.顺序表：把线性表的结点按逻辑次序存放在一组地址连续的存储单元里。

4.顺序表结点的存储地址计算公式：Loc(ai)=Loc(a1)+(i-1)*C；1≤i≤n

5.顺序表上的基本运算

（1）插入

void insertlist(seqlist *L,datatype x,int i)

{

int j;

if(i<1||i>L->length+1)

error(“position error”);

if(L->length>=listsize)

error(“overflow”);

for(j=L->length-1;j>=i-1;j--)

L->data[j+1]=L->data[j]; 结点后移

L->data[i-1]=x;

L->length++;

}

在顺序表上插入要移动表的n/2结点，算法的平均时间复杂度为O(n)。

（2）删除

void delete (seqlist *L,int i)

{

int j;

if(i<1||i>L->length)

error(“position error”);

for(j=i;j<=L->length-1;j++)

L->data[j-1]=L->data[j]; 结点前移

L->length--;

}

在顺序表上删除要移动表的（n+1）/2结点，算法的平均时间复杂度为O(n)。

6.单链表：只有一个链域的链表称单链表。

在结点中存储结点值和结点的后继结点的地址，data next data是数据域，next是指针域。（1）建立单链表。时间复杂度为O(n)。

加头结点的优点：1）链表第一个位置的操作无需特殊处理；2）将空表和非空表的处理统一。（2）查找运算。时间复杂度为O(n)。

1）按序号查找。

Listnode * getnode(linklist head,int i)

{

int j;

listnode *p;

p=head;j=0;

while(p->next&&j

p=p->next; 指针下移

j++;

}

if(i==j)

return p;

else

return NULL;

}

2）按值查找。

Listnode * locatenode(linklist head ,datatype key)

{

listnode *p=head->next;

while(p&&p->data!=key)

p=p->next;

return p;

}

（3）插入运算。时间复杂度为O(n)。

Void insertlist(linklist head ,datatype x, int i)

{

listnode *p;

p=getnode(head,i-1);

if(p==NULL);

error(“position error”);

s=(listnode *)malloc(sizeof(listnode));

s->data=x;

s->next=p->next;

p->next=s;

}

（4）删除运算。时间复杂度为O(n)。

Void deletelist(linklist head ,int i)

{

listnode *p ,*r;

p=getnode(head ,i-1);

if(p==NULL||p->next==NULL)

error(“position error”);

r=p->next;

p->next=r->next;

free(r);

}

7.循环链表：是一种首尾相连的链表。特点是无需增加存储量，仅对表的链接方式修改使表的处理灵活方便。

8.空循环链表仅由一个自成循环的头结点表示。

9.很多时候表的操作是在表的首尾位置上进行，此时头指针表示的单循环链表就显的不够方便，改用尾指针rear来表示单循环链表。用头指针表示的单循环链表查找开始结点的时间是O(1),查找尾结点的时间是O(n)；用尾指针表示的单循环链表查找开始结点和尾结点的时间都是O(1)。

10.在结点中增加一个指针域，prior|data|next。形成的链表中有两条不同方向的链称为双链表。

1) 双链表的前插操作。时间复杂度为O(1)。

Void dinsertbefore(dlistnode *p ,datatype x)

{

dlistnode *s=malloc(sizeof(dlistnode));

s->data=x;

s->prior=p->prior;

s->next=p;

p->prior->next=s;

p->prior=s;

}

2) 双链表的删除操作。时间复杂度为O(1)。

Void ddeletenode(dlistnode *p)

{

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

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

free(p);

}

11.顺序表和链表的比较

1）基于空间的考虑：顺序表的存储空间是静态分配的，链表的存储空间是动态分配的。顺序表的存储密度比链表大。因此，在线性表长度变化不大，易于事先确定时，宜采用顺序表作为存储结构。

2）基于时间的考虑：顺序表是随机存取结构，若线性表的操作主要是查找，很少有插入、删除操作时，宜用顺序表结构。对频繁进行插入、删除操作的线性表宜采用链表。若操作主要发生在表的首尾时采用尾指针表示的单循环链表。

12.存储密度=（结点数据本身所占的存储量）/（整个结点结构所占的存储总量）

存储密度：顺序表=1，链表<1。

第三章栈和队列

1.栈是限制仅在表的一端进行插入和删除运算的线性表又称为后进先出表（LIFO表）。插入、删除端称为栈顶，另一端称栈底。表中无元素称空栈。

2.栈的基本运算有：

1）initstack(s),构造一个空栈；

2）stackempty(s),判栈空；

3）stackfull(s),判栈满；

4）push(s,x),进栈；

5）pop (s),退栈；

6）stacktop(s)，取栈顶元素。

3.顺序栈：栈的顺序存储结构称顺序栈。

4.当栈满时，做进栈运算必定产生空间溢出，称“上溢”。当栈空时，做退栈运算必定产生空间溢出，称“下溢”。上溢是一种错误应设法避免，下溢常用作程序控制转移的条件。

5.在顺序栈上的基本运算：

1）置空栈。

Void initstack(seqstack *s)

{

s->top=-1;

}

2)判栈空。

int stackempty(seqstack *s)

{

return s->top==-1;

}

3)判栈满。

int stackfull(seqstack *s)

{

return s->top==stacksize-1;

}

4)进栈。

Void push(seqstack *s,datatype x)

{

if(stackfull(s))

error(“stack overflow”);

s->data[++s->top]=x;

}

5)退栈。

Datatype pop(seqstack *s)

{

if(stackempty(s))

error(“stack underflow”);

return S->data[s->top--];

}

6)取栈顶元素。

Dtatatype stacktop(seqstack *s)

{

if(stackempty(s))

error(“stack underflow”);

return S->data[s->top];

}

6.链栈：栈的链式存储结构称链栈。栈顶指针是链表的头指针。

7.链栈上的基本运算：

1）建栈。

Void initstack(linkstack *s)

{

s->top=NULL;

}

2)判栈空。

Int stackempty (linkstack *s)

{

return s->top==NULL;

}

3) 进栈。

Void push(linkstack *s,datatype x)

{

stacknode *p=(stacknode *)malloc(sizeof(stacknode)); p->data=x;

p->next=s->top;

s->top=p;

}

4) 退栈。

Datatype pop(linksatck *s)

{

datatype x;

stacknode *p=s->top;

if(stackempty(s))

error(“stack underflow”);

x=p->data;

s->top=p->next;

free(p);

return x;

}

5) 取栈顶元素。

Datatype stacktop(linkstack *s)

{

if(stackempty(s))

error(“stack is empty”);

return s->top->data;

}

8.队列是一种运算受限的线性表，允许删除的一端称队首，允许插入的一端称队尾。队列又称为先进先出线性表，FIFO表。

9.队列的基本运算：

1）initqueue(q),置空队；

2）queueempty(q),判队空；

3）queuefull(q),判队满；

4）enqueue(q,x),入队；

5）dequeue(q),出队；

6）queuefront(q),返回队头元素。

10.顺序队列：队列的顺序存储结构称顺序队列。设置front和rear指针表示队头和队尾元素在向量空间的位置。

11.顺序队列中存在“假上溢”现象，由于入队和出队操作使头尾指针只增不减导致被删元素的空间无法利用，队尾指针超过向量空间的上界而不能入队。

12.为克服“假上溢”现象，将向量空间想象为首尾相连的循环向量，存储在其中的队列称循环队列。i=(i+1)%queuesize

13.循环队列的边界条件处理：由于无法用front==rear来判断队列的“空”和“满”。

解决的方法有：

1）另设一个布尔变量以区别队列的空和满；

2）少用一个元素，在入队前测试rear在循环意义下加1是否等于front；

3）使用一个记数器记录元素总数。

14.循环队列的基本运算：

1) 置队空。

Void initqueue(cirqueue *q)

{

q->front=q->rear=0;

q->count=0;

}

2) 判队空。

Int queueempty(cirqueue *q)

{

return q->count==0;

}

3) 判队满。

Int queuefull(cirqueue *q)

{

return q->count==queuesize;

}

4) 入队。

Void enqueue(cirqueue *q ,datatype x)

{

if(queuefull(q))

error(“queue overfolw”);

q->count++;

q->data[q->rear]=x;

q->rear=(q->rear+1)%queuesize;

}

5) 出队。

Datatype dequeue(cirqueue *q)

{

datatype temp;

if(queueempty(q))

error(“queue underflow”);

temp=q->data[q->front];

q->count--;

q->front=(q->front+1)%queuesize;

return temp;

}

6) 取队头元素。

Datatype queuefront(cirqueue *q)

{

if(queueempty(q))

error(“queue is empty”);

return q->data[q->front];

}

15.链队列：队列的链式存储结构称链队列，链队列由一个头指针和一个尾指针唯一确定。

16.链队列的基本运算：

1) 建空队。

Void initqueue(linkqueue *q)

{

q->front=q->rear=NULL;

}

2) 判队空。

Int queueempty(linkqueue *q)

{

return q->front==NULL&&q->rear==NULL;

}

3) 入队。

Void enqueue(linkqueue *q,datatype x)

{

queuenode *p=(queuenode *)malloc(sizeof(queuenode));

p->data=x;

p->next=NULL;

if(queueempty(q))

q-front=q->rear=p;

else{

q->rear->next=p;

q->rear=p;

}

}

4) 出队。

Datatype dequeue(linkqueue *q)

{

datatype x;

queuenode *p;

if(queueempty(q))

error(“queue is underflow”);

p=q->front;

x=p->data;

q->front=p->next;

if(q->rear==p) q->rear=NULL;

free(p);

return x;

}

5) 取队头元素。

Datatype queuefront(linkqueue *q)

{

if(queueempty(q))

error(“queue is empty”);

return q->front->data;

}

第四章串

1.串：是由零个或多个字符组成的有限序列；包含字符的个数称串的长度；

2.空串：长度为零的串称空串；空白串：由一个或多个空格组成的串称空白串；

子串：串中任意个连续字符组成的子序列称该串的子串；主串：包含子串的串称主串；

子串的首字符在主串中首次出现的位置定义为子串在主串中的位置；

3.空串是任意串的子串；任意串是自身的子串；

串常量在程序中只能引用但不能改变其值；串变量取值可以改变；

4.串的基本运算

1）int strlen(char *s);求串长。

2）char *strcpy(char * to,char * from);串复制。

3）char *strcat(char * to,char * from);串联接。

4）int strcmp(char *s1,char *s2);串比较。

5）char *strchr(char *s,char c);字符定位。

5.串的存储结构：

（1）串的顺序存储：串的顺序存储结构称顺序串。按存储分配不同分为：

1）静态存储分配的顺序串：

直接用定长的字符数组定义，以“\0”表示串值终结。

#define maxstrsize 256

typedef char seqstring[maxstrsize];

seqstring s;

不设终结符，用串长表示。

Typedef struct{

Char ch[maxstrsize];

Int length;

}seqstring;

以上方式的缺点是：串值空间大小是静态的，难以适应插入、链接等操作。

2）动态存储分配的顺序串：

简单定义：typedef char * string;

复杂定义：typedef struct{

char *ch;

int length;

}hstring;

（2）串的链式存储：串的链式存储结构称链串。链串由头指针唯一确定。类型定义：typedef struct node{

char data;

struct node *next;

}linkstrnode;

typedef linkstrnode *linkstring;

linkstring s;

将结点数据域存放的字符个数定义为结点的大小。结点大小不为1的链串类型定义：#define nodesize 80

typedef struct node{

char data[nodesize];

struct node * next;

}linkstrnode;

6.串运算的实现

（1）顺序串上的子串定位运算。

1）子串定位运算又称串的模式匹配或串匹配。主串称目标串；子串称模式串。

2）朴素的串匹配算法。时间复杂度为O(n^2)。比较的字符总次数为（n-m+1）m。Int naivestrmatch(seqstring t,seqstring p)

{

int i,j,k;

int m=p.length;

int n=t.length;

for(i=0;i<=n-m;i++){

j=0;k=i;

while(j

j++;k++;

}

if (j==m) return i;

}

return –1;

}

（2）链串上的子串定位运算。时间复杂度为O(n^2)。比较的字符总次数为（n-m+1）m。Linkstrnode * lilnkstrmatch(linkstring T, linkstring P)

{

linkstrnode *shift, *t, *p;

shift=T;

t=shift;p=P;

while(t&&p){

if(t->data==p->data){

t=t->next;

p=p->next;

}

else{

shift=shift->next;

t=shift;

p=P;

}

}

if(p==NULL)

return shift;

else

return NULL;

}

第五章多维数组和广义表

1.多维数组：一般用顺序存储的方式表示数组。

2.常用方式有：1）行优先顺序，将数组元素按行向量排列；

2）列优先顺序，将数组元素按列向量排列。

3.计算地址的函数：LOC(Aij)=LOC(Ac1c2)+((i-c1)*(d2-c2+1)+j-c2)*d

4.矩阵的压缩存储：为多个非零元素分配一个存储空间；对零元素不分配存储空间。

（1）对称矩阵：在一个n阶的方阵A中，元素满足Aij=Aji 0<=i,j<=n-1;称为对称矩阵。元素的总数为：n(n+1)/2;

设：I=i或j中大的一个数；J=i或j中小的一个数；

则：k=I*(I+1)/2+J;

地址计算：LOC(Aij)=LOC(sa[k])=LOC(sa[0])+k*d= LOC(sa[0])+ (I*(I+1)/2+J )*d

（2）三角矩阵：以主对角线划分，三角矩阵有上三角和下三角；上三角的主对角线下元素均为常数c；下三角的主对角线上元素均为常数c。

元素总数为：(n(n+1)/2)+1;

以行优先顺序存放的Aij与SA[k]的关系：

上三角阵：k=i*(2n-i+1)/2+j-i;

下三角阵：k=i*(i+1)/2+j;

（3）对角矩阵：所有的非零元素集中在以主对角线为中心的带状区域，相邻两侧元素均为零。|i-j|>(k-1)/2

以行优先顺序存放的Aij与SA[k]的关系：k=2i+j;

5.稀疏矩阵：当矩阵A中有非零元素S个，且S远小于元素总数时，称为稀疏矩阵。

对其压缩的方法有顺序存储和链式存储。

（1）三元组表：将表示稀疏矩阵的非零元素的三元组（行号、列号、值）按行或列优先的顺序排列得到的一个结点均是三元组的线性表，将该表的线性存储结构称为三元组表。其类型定义：

#define maxsize 10000

typedef int datatype;

typedef struct{

int i,j;

datatype v;

}trituplenode;

typedef struct{

trituplenode data[maxsize];

int m,n,t;

}tritupletable;

（2）带行表的三元组表：在按行优先存储的三元组表中加入一个行表记录每行的非零元素在三元组表中的起始位置。类型定义：#define maxrow 100

typedef struct{

tritulpenode data[maxsize];

int rowtab[maxrow];

int m, n, t;

}rtritulpetable;

6.广义表：是线性表的推广，广义表是n个元素的有限序列，元素可以是原子或一个广义表，记为LS。

7.若元素是广义表称它为LS的子表。若广义表非空，则第一个元素称表头，其余元素称表尾。

8.表的深度是指表展开后所含括号的层数。

9.把与树对应的广义表称为纯表，它限制了表中成分的共享和递归；

10.允许结点共享的表称为再入表；

11.允许递归的表称为递归表；

12.相互关系：线性表∈纯表∈再入表∈递归表；

13.广义表的特殊运算：1）取表头head(LS)；2）取表尾tail(LS);

第六章树

1.树：是n个结点的有限集T，T为空时称空树，否则满足：

1）有且仅有一个特定的称为根的结点；

2）其余结点可分为m个互不相交的子集，每个子集本身是一棵树，并称为根的子树。

2.树的表示方法：1）树形表示法；2）嵌套集合表示法；3）凹入表表示法；4）广义表表示法；

3.一个结点拥有的子树数称为该结点的度；一棵树的度是指树中结点最大的度数。

4.度为零的结点称叶子或终端结点；度不为零的结点称分支结点或非终端结点

5.根结点称开始结点，根结点外的分支结点称内部结点；

6.树中某结点的子树根称该结点的孩子；该结点称为孩子的双亲；

7.树中存在一个结点序列K1，K2，…Kn，使Ki为Ki+1的双亲，则称该结点序列为K1到Kn的路径或道路；

8.树中结点K到Ks间存在一条路径，则称K是Ks的祖先，Ks是K的子孙；

9.结点的层数从根算起，若根的层数为1，则其余结点层数是其双亲结点层数加1；双亲在同一层的结点互为堂兄弟；树中结点最大层数称为树的高度或深度；

10.树中每个结点的各个子树从左到右有次序的称有序树，否则称无序树；

11.森林是m棵互不相交的树的集合。

12.二叉树：是n个结点的有限集，它或为空集，或由一个根结点及两棵互不相交的、分别称为该根的左子树和右子树的二叉树组成。

13.二叉树不是树的特殊情况，这是两种不同的数据结构；它与无序树和度为2的有序树不同。

14.二叉树的性质：

1）二叉树第i层上的结点数最多为2^(i-1)；

2）深度为k的二叉树至多有2^k-1个结点；

3）在任意二叉树中，叶子数为n0，度为2的结点数为n2，则n0=n2+1；

15.满二叉树是一棵深度为k的且有2^k-1个结点的二叉树；

16.完全二叉树是至多在最下两层上结点的度数可以小于2，并且最下层的结点集中在该层最左的位置的二叉树；

17.具有N个结点的完全二叉树的深度为log2N取整加1；

18.二叉树的存储结构

（1）顺序存储结构：把一棵有n个结点的完全二叉树，从树根起自上而下、从左到右对所有结点编号，然后依次存储在一个向量b[0~n]中，b[1~n]存放结点，b[0]存放结点总数。

各个结点编号间的关系：

1）i=1是根结点；i>1则双亲结点是i/2取整；

2）左孩子是2i, 右孩子是2i+1；（要小于n）

3）i>（n/2取整）的结点是叶子；

4）奇数没有右兄弟，左兄弟是i-1；

5）偶数没有左兄弟，右兄弟是i+1；

（2）链式存储结构

结点的结构为：lchild|data|rchild ；相应的类型说明：

typedef char data;

typedef struct node{

datatype data;

structnode *lchild , *rchild;

}bintnode;

typedef bintnode * bintree;

19.在二叉树中所有类型为bintnode的结点和一个指向开始结点的bintree类型的头指针构成二叉树的链式存储结构称二叉链表。

20.二叉链表由根指针唯一确定。在n个结点的二叉链表中有2n个指针域，其中n+1个为空。

21.二叉树的遍历方式有：前序遍历、中序遍历、后序遍历。时间复杂度为O(n)。

22.线索二叉树：利用二叉链表中的n+1个空指针域存放指向某种遍历次序下的前趋和后继结点的指针，这种指针称线索。加线索的二叉链表称线索链表。相应二叉树称线索二叉树。

23.线索链表结点结构：lchild|ltag|data|rtag|rchild；ltag=0,lchild是指向左孩子的指针；ltag=1,lchild是指向前趋的线索；rtag=0,rchild是指向右孩子的指针；rtag=1,rchild是指向后继的线索；

24.查找*p在指定次序下的前趋和后继结点。算法的时间复杂度为O(h)。线索对查找前序前趋和后序后继帮助不大。

25.遍历线索二叉树。时间复杂度为O(n)。

26.树、森林与二叉树的转换

（1）树、森林与二叉树的转换

1）树与二叉树的转换：1}所有兄弟间连线；2}保留与长子的连线，去除其它连线。该二叉树的根结点的右子树必为空。

2）森林与二叉树的转换：1}将所有树转换成二叉树；2}将所有树根连线。

（2）二叉树与树、森林的转换。是以上的逆过程。

27.树的存储结构

（1）双亲链表表示法：为每个结点设置一个parent指针，就可唯一表示任何一棵树。Data|parent

（2）孩子链表表示法：为每个结点设置一个firstchild指针，指向孩子链表头指针，链表中存放孩子结点序号。Data|firstchild。（3双亲孩子链表表示法：将以上方法结合。Data|parent|firstchild

（4）孩子兄弟链表表示法：附加两个指向左孩子和右兄弟的指针。Leftmostchild|data|rightsibling

28.树和森林的遍历：前序遍历一棵树等价于前序遍历对应二叉树；后序遍历等价于中序遍历对应二叉树。

29.最优二叉树（哈夫曼树）：树的路径长度是从树根到每一结点的路径长度之和。将树中的结点赋予实数称为结点的权。

30.结点的带权路径是该结点的路径长度与权的乘积。树的带权路径长度又称树的代价，是所有叶子的带权路径长度之和。

31.带权路径长度最小的二叉树称最优二叉树（哈夫曼树）。

32.具有2n-1个结点其中有n个叶子，并且没有度为1的分支结点的树称为严格二叉树。

33.哈夫曼编码

34.对字符集编码时，要求字符集中任一字符的编码都不是其它字符的编码前缀，这种编码称前缀码。

35.字符出现频度与码长乘积之和称文件总长；字符出现概率与码长乘积之和称平均码长；

36.使文件总长或平均码长最小的前缀码称最优前缀码

37.利用哈夫曼树求最优前缀码，左为0，右为1。编码平均码长最小；没有叶子是其它叶子的祖先，不可能出现重复前缀。

第七章图

1.图：图G是由顶点集V和边集E组成，顶点集是有穷非空集，边集是有穷集；

2.G中每条边都有方向称有向图；有向边称弧；边的始点称弧尾；边的终点称弧头；G中每条边都没有方向的称无向图。

3.顶点n与边数e的关系：无向图的边数e介于0~n(n-1)/2之间，有n(n-1)/2条边的称无向完全图；有向图的边数e介于

0~n(n-1)之间，有n(n-1)条边的称有向完全图；

4.无向图中顶点的度是关联与顶点的边数；有向图中顶点的度是入度与出度的和。

所有图均满足：所有顶点的度数和的一半为边数。

5.图G（V，E），如V’是V的子集，E’是E的子集，且E’中关联的顶点均在V’中，则G’(V’,E’)是G的子图。

6.在有向图中，从顶点出发都有路径到达其它顶点的图称有根图；

7.在无向图中，任意两个顶点都有路径连通称连通图；极大连通子图称连通分量；

8.在有向图中，任意顺序两个顶点都有路径连通称强连通图；极大连通子图称强连通分量；

9.将图中每条边赋上权，则称带权图为网络。

10.图的存储结构：

（1）邻接矩阵表示法：邻接矩阵是表示顶点间相邻关系的矩阵。n个顶点就是n阶方阵。

无向图是对称矩阵；有向图行是出度，列是入度。

（2）邻接表表示法：对图中所有顶点，把与该顶点相邻接的顶点组成一个单链表，称为邻接表，adjvex|next,如要保存顶点信息加入data；对所有顶点设立头结点，vertex|firstedge,并顺序存储在一个向量中；vertex保存顶点信息，firstedge保存邻接表头指针。

11.邻接矩阵表示法与邻接表表示法的比较：

1）邻接矩阵是唯一的，邻接表不唯一；

2）存储稀疏图用邻接表，存储稠密图用邻接矩阵；

3）求无向图顶点的度都容易，求有向图顶点的度邻接矩阵较方便；

4）判断是否是图中的边，邻接矩阵容易，邻接表最坏时间为O(n)；

5）求边数e，邻接矩阵耗时为O(n^2)，与e无关，邻接表的耗时为O(e+n)；

12.图的遍历：

（1）图的深度优先遍历：类似与树的前序遍历。按访问顶点次序得到的序列称DFS序列。

对邻接表表示的图深度遍历称DFS，时间复杂度为O(n+e); 对邻接矩阵表示的图深度遍历称DFSM，时间复杂度为O(n^2); （2）图的广度优先遍历：类似与树的层次遍历。按访问顶点次序得到的序列称BFS序列。

对邻接表表示的图广度遍历称BFS，时间复杂度为O(n+e); 对邻接矩阵表示的图广度遍历称BFSM，时间复杂度为O(n^2);

13. 将没有回路的连通图定义为树称自由树。

14.生成树：连通图G的一个子图若是一棵包含G中所有顶点的树，该子图称生成树。

有DFS生成树和BFS生成树，BFS生成树的高度最小。

非连通图生成的是森林。

15.最小生成树：将权最小的生成树称最小生成树。（是无向图的算法）

（1）普里姆算法：

1）确定顶点S、初始化候选边集T[0~n-2]；formvex|tovex|lenght

2）选权值最小的T[i]与第1条记录交换；

3）从T[1]中将tovex取出替换以下记录的fromvex计算权；若权小则替换，否则不变；

4）选权值最小的T[i]与第2条记录交换；

5）从T[2]中将tovex取出替换以下记录的fromvex计算权；若权小则替换，否则不变；

6）重复n-1次。

初始化时间是O(n),选轻边的循环执行n-1-k次，调整轻边的循环执行n-2-k；算法的时间复杂度为O(n^2)，适合于稠密图。（2）克鲁斯卡尔算法：

1）初始化确定顶点集和空边集；对原边集按权值递增顺序排序；

2）取第1条边，判断边的2个顶点是不同的树，加入空边集，否则删除；

3）重复e次。

对边的排序时间是O(elog2e)；初始化时间为O(n)；执行时间是O(log2e)；算法的时间复杂度为O(elog2e)，适合于稀疏图。

16. 路径的开始顶点称源点，路径的最后一个顶点称终点；

17.单源最短路径问题：已知有向带权图，求从某个源点出发到其余各个顶点的最短路径；

18.单目标最短路径问题：将图中每条边反向，转换为单源最短路径问题；

19.单顶点对间最短路径问题：以分别对不同顶点转换为单源最短路径问题；

20.所有顶点对间最短路径问题：分别对图中不同顶点对转换为单源最短路径问题；

21.迪杰斯特拉算法：

1）初始化顶点集S[i],路径权集D[i],前趋集P[i]；

2）设置S[s]为真，D[s]为0；

3）选取D[i]最小的顶点加入顶点集；

4）计算非顶点集中顶点的路径权集；

5）重复3）n-1次。

算法的时间复杂度为O(n^2)。

22.拓扑排序：对一个有向无环图进行拓扑排序，是将图中所有顶点排成一个线性序列，满足弧尾在弧头之前。这样的线性序列称拓扑序列。

（1）无前趋的顶点优先：总是选择入度为0的结点输出并删除该顶点的所有边。

设置各个顶点入度时间是O(n+e)，设置栈或队列的时间是O(n)，算法时间复杂度为O(n+e)。

（2）无后继的顶点优先：总是选择出度为0的结点输出并删除该顶点的所有边。

设置各个顶点出度时间是O(n+e)，设置栈或队列的时间是O(n)，算法时间复杂度为O(n+e)。

求得的是逆拓扑序列。

第八章排序

1.文件：由一组记录组成，记录有若干数据项组成，唯一标识记录的数据项称关键字；

2.排序是将文件按关键字的递增（减）顺序排列；

3.排序文件中有相同的关键字时，若排序后相对次序保持不变的称稳定排序，否则称不稳定排序；

4.在排序过程中，文件放在内存中处理不涉及数据的内、外存交换的称内排序，反之称外排序；

5.排序算法的基本操作：1）比较关键字的大小；2）改变指向记录的指针或移动记录本身。

6.评价排序方法的标准：1）执行时间；2）所需辅助空间，辅助空间为O(1)称就地排序；另要注意算法的复杂程度。

7.若关键字类型没有比较运算符，可事先定义宏或函数表示比较运算。

8.插入排序

（1）直接插入排序

算法中引入监视哨R[0]的作用是：1）保存R[i]的副本；2）简化边界条件，防止循环下标越界。

关键字比较次数最大为(n+2)(n-1)/2；记录移动次数最大为(n+4)(n-1)/2；

算法的最好时间是O(n)；最坏时间是O(n^2)；平均时间是O(n^2)；是一种就地的稳定的排序；

（2）希尔排序

实现过程：是将直接插入排序的间隔变为d。d的取值要注意：1）最后一次必为1；2）避免d值互为倍数；

关键字比较次数最大为n^1.25；记录移动次数最大为1.6n^1.25；

算法的平均时间是O(n^1.25)；是一种就地的不稳定的排序；

9.交换排序

（1）冒泡排序

实现过程：从下到上相邻两个比较，按小在上原则扫描一次，确定最小值，重复n-1次。

关键字比较次数最小为n-1、最大为n(n-1)/2；记录移动次数最小为0，最大为3n(n-1)/2；

算法的最好时间是O(n)；最坏时间是O(n^2)；平均时间是O(n^2)；是一种就地的稳定的排序；

（2）快速排序

实现过程：将第一个值作为基准，设置i,j指针交替从两头与基准比较，有交换后,交换j，i。i=j时确定基准，并以其为界限将序列分为两段。重复以上步骤。

关键字比较次数最好为nlog2n+nC(1)、最坏为n(n-1)/2；

算法的最好时间是O(nlog2n)；最坏时间是O(n^2)；平均时间是O(nlog2n)；辅助空间为O(log2n)；是一种不稳定排序；

10.选择排序

（1）直接选择排序

实现过程：选择序列中最小的插入第一位，在剩余的序列中重复上一步，共重复n-1次。

关键字比较次数为n(n-1)/2；记录移动次数最小为0，最大为3(n-1)；

算法的最好时间是O(n^2)；最坏时间是O(n^2)；平均时间是O(n^2)；是一种就地的不稳定的排序；

（2）堆排序

实现过程：把序列按层次填入完全二叉树，调整位置使双亲大于或小于孩子，建立初始大根或小根堆，调整树根与最后一个叶子的位置，排除该叶子重新调整位置。

算法的最好时间是O(nlog2n)；最坏时间是O(nlog2n)；平均时间是O(nlog2n)；是一种就地的不稳定排序；

11.归并排序

实现过程：将初始序列分为2个一组，最后单数轮空，对每一组排序后作为一个单元，对2个单元排序，直到结束。

算法的最好时间是O(nlog2n)；最坏时间是O(nlog2n)；平均时间是O(nlog2n)；辅助空间为O(n)；是一种稳定排序；

12.分配排序

（1）箱排序

实现过程：按关键字的取值范围确定箱子的个数，将序列按关键字放入箱中，输出非空箱的关键字。

在桶内分配和收集，及对各桶进行插入排序的时间为O(n),算法的期望时间是O(n),最坏时间是O(n^2)。

（2）基数排序

实现过程：按基数设置箱子，对关键字从低位到高位依次进行箱排序。

算法的最好时间是O(d*n+d*rd)；最坏时间是O(d*n+d*rd)；平均时间是O(d*n+d*rd)；辅助空间O(n+rd)；是一种稳定排序；

13.各种内部排序方法的比较和选择：

（1）按平均时间复杂度分为：

1) 平方阶排序：直接插入、直接选择、冒泡排序；

2) 线性对数阶：快速排序、堆排序、归并排序；

3) 指数阶：希尔排序；

4) 线性阶：箱排序、基数排序。

（2）选择合适排序方法的因素：

1)待排序的记录数；2)记录的大小；3)关键字的结构和初始状态；4)对稳定性的要求；

5)语言工具的条件；6)存储结构；7)时间和辅助空间复杂度。

（3）结论：

1) 若规模较小可采用直接插入或直接选择排序；

2) 若文件初始状态基本有序可采用直接插入、冒泡或随机快速排序；

3) 若规模较大可采用快速排序、堆排序或归并排序；

4) 任何借助于比较的排序，至少需要O(nlog2n)的时间，箱排序和基数排序只适用于有明显结构特征的关键字；

5) 有的语言没有提供指针及递归，使归并、快速、基数排序算法复杂；

6) 记录规模较大时为避免大量移动记录可用链表作为存储结构，如插入、归并、基数排序，但快速、堆排序在链表上难以实现，可提取关键字建立索引表，然后对索引表排序。

第九章查找

1.查找的同时对表做修改操作(如插入或删除)则相应的表称之为动态查找表，否则称之为静态查找表。

2.衡量一个查找算法次序优劣的标准是在查找过程中对关键字需要执行的平均比较次数(即平均查找长度ASL).

3.线性表上进行查找的方法主要有三种：顺序查找、二分查找和分块查找。

（1）顺序查找的算法基本思想：是从表的一端开始顺序扫描线性表，依次将扫描到的结点关键字与给定值K比较，若当前扫描到的结点关键字与k相等则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。

1）顺序查找方法可用链式存储结构和顺序存储结构实现。

2）在顺序存储结构的顺序查找算法中所设的哨兵是为了简化循环的边界条件而引入的附加结点(元素)，其作用是使for循环中省

去判定防止下标越界的条件从而节省了比较的时间。

3）在等概率情况下，查找成功时其平均查找长度约为表长的一半(n+1)/2.查找失败的话其平均查找长度为n+1.

（2）二分查找(又称折半查找)，它的算法思想：是对一有序表中的元素，从初始的查找区间开始，每经过一次与当前查找区间的中点位置上的结点关键字进行比较，若相等，则查找成功，否则，当前查找区间的缩小一半，按k值大小在某半个区间内重复相同的步骤进行查找，直到查找成功或失败为止。

1）二分查找在等概率的情况下查找成功的平均查找长度ASL为lg(n+1)-1,在查找失败时所需比较的关键字个数不超过判定树的深度，最坏情况下查找成功的比较次数也不超过判定树的深度┌lg(n+1)┐(不小于lg(n+1)的最小整数)

2）二分查找只适用于顺序存储结构而不能用链式存储结构实现。因为链表无法进行随机访问，如果要访问链表的中间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。

（3）分块查找(又称索引顺序查找)的基本思想：是将原表分成若干块，各块内部不一定有序，但表中的块是"分块有序"的，并抽取各块中的最大关键字及其起始位置建立索引表。因为索引表是有序的，分块查找就是先用二分查找或顺序查找确定待查结点在哪一块，然后在已确定的块中进行顺序查找(不能用二分查找，因为块内是无序的)。分块查找实际上是两次查找过程，它的算法效率介与顺序查找和二分查找之间。

4.以上三种查找方法的比较如下表：

查找算法存储结构优点缺点适用于

顺序查找顺序结构

链表结构算法简单且对表的结构无任何要求查找效率低n较小的表的查找和查找较少但改动较多的表(用链表作存储结构)

二分查找顺序结构查找效率高关键字要有序且只能用顺序存储结构实现特别适用于一经建立就很少改动又经常需要查找的线

性表

分块查找顺序结构

链表在表中插入或删除记录时就只要在该记录所属块内操作，因为块内记录的存放是随意的，所以插入和删除比较容易要增加一个辅助数组的存储空间，并要进行将初始表分块排序运算适用于有分块特点的记录，如一个学校的学生登记表可按系号或班号分块。

5.树的查找：以树做为表的组织形式有一个好处，就是可以实现对动态查找表进行高效率的查找。这里讲到了二叉排序树和B-树，以及在这些树表上进行查找和修改操作的方法。

6.二叉排序树(BST)又称二叉查找树，其定义是：二叉排序树要或者是空树或者满足如下性质的二叉树：

1)若它的左子树非空，则左子树上所有结点的值均小于根结点的值；

2)若它的右子树非空，则右子树上所有结点的值均大于根结点的值；

3)左、右子树本身又是一棵二叉排序树。

（1）二叉排序树实际上是满足BST性质的二叉树。

（2）二叉排序树的插入、建立的算法平均时间性能是O(nlgn),但其执行时间约为堆排序的2至3倍。二叉排序树的删除操作可分三种情况进行处理：

1)*P是叶子，则直接删除*P，即将*P的双亲*parent 中指向*P的指针域置空即可。

2)*P只有一个孩子*child,此时只需将*child和*p的双亲直接连接就可删去*p.

3)*p有两个孩子,则将操作转换成删除*p结点的中序后继，在删去它之前把这个结点的数据复制到原来要删的结点位置上就完成了删除。

（3）二叉排序树上的查找和二分查找类似，它的关键字比较次数不超过树的深度。在最好的情况下，二叉排序树在生成的过程中比较匀称，此时的叉排序树是平衡的二叉树(也就是树中任一结点的左右子树的高度大致相同)，它的高度约为1.44lgn，完全平衡的二叉树高度约为lgn.在最坏的情况下，输入的实例产生的二叉排序树的高度将达到O(n),这种情况应当避免。

7.关于B-树(多路平衡查找树)。它适合在磁盘等直接存取设备上组织动态的查找表，是一种外查找算法。

B树的阶是指B-树的度数，B-树的结点具有k个孩子时，该结点必有k-1(k>=2)个关键字。

实际上B-树是二叉排序树的推广，它就是一棵m叉树，且满足四个性质，这些性质与二叉排序树有相似之处，请仔细理解之。

8.上面的几种查找方法均是建立在比较关键字的基础上，因此它们的平均和最坏情况下所需的比较次数的下界是lgn+O(1).

9.散列技术：可以无需任何比较就找到待查关键字，其查找的期望时间为O(1).

散列表的概念：就是将所有可能出现的关键字的集合U(全集)映射到一个表T[0..m-1]的下标集上，这个表就是散列表。

10.而关键字与这个表地址之间以什么样的关系发生联系呢，这就要通过一个函数来建立，这个函数是以U中的关键字为自变量，以相应结点的存储地址为函数值，它就称为散列函数。将结点按其关键字的散列地址存储到散列表的过程称为散列。

11.根据某种散列函数，一个关键字的散列函数值是唯一的，但是有可能两个或多个不同关键字的函数值是相同的，这时就会把几个结点存储到同一个表位置上，这时就造成冲突(或碰撞)现象，这两个关键字称为该散列函数的同义词。

要完全(不是"安全")避免冲突需满足两个条件，一是关键字集合U不大于散列表长m，另一个是选择合适的散列函数,如果用

h(ki)=0)这样的函数的话，看看有什么结果。

12.通常情况下U总是大大于m的，因此不可能完全避免冲突。冲突的频繁程度还与表的填满程度相关。装填因子α表示表中填入的结点数与表长的比值，通常取α≤1，因为α越大，表越满，冲突的机会也越大。

13.散列函数的选择有两条标准：简单和均匀。看看h(ki)=0这样的函数，简单是简单，但绝不均匀。

14.下面是常见的几种散列函数构的造方法：

（1）平方取中法

（2）除余法：它是用表长m来除关键字，取余数作为散列地址。若选除数m是关键字的基数的幂次，就会使得高位不同而低位相同的关键字互为同义词。因此最好选取素数为除数.

（3）相乘取整法：有两个步骤，先用关键字key乘上某个常数A(0)

（4）随机数法，此法以关键字为自变量，通过一随机函数得到的值作为散列地址。

15.处理冲突的方法：当不可避免发生冲突时，就必须对冲突加以解决，使发生冲突的同义词能存储到表中。

16.通常有两类方法处理冲突：开放定址法和拉链法。前者是将所有结点均存放在散列T[0..m-1]中，后者是将互为同义词的结点链成一个单链表，而将此链表的头指针放在散列表中。

17.开放定址法的一般形式为：hi=(h(key)+di)%m 1≤i≤m-1

18.开放定址法要求散列表的装填因子α≤1。开放定址法又有线性探查法、二次探查法和双重散列法之分。

（1）由于线性探查法在构造散列表时，遇到冲突(有同义词)的时候会按探查序列向后面的空地址插入，从而使原来应插入到此位置的结点又与它发生冲突，当一连串的位置均已有结点时，本应插入到这些位置的结点又只能将其插入到更后面的同一个空结点上，这种散列地址不同的结点争夺同一个后继散列地址的现象就是聚集或堆积。(注意，同义词发生冲突不是堆积)

为了减小堆积现象的发生，可以用二次探查法和双重散列法进行探查。

（2）拉链法解决冲突的做法是，将所有关键字为同义词的结点链接在同一个单链表中。

19.与开放定址法相比，拉链法有如下几个优点：

(1)拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；(简单无堆积)

(2)由于拉链法中各链表上的结点空间是动态申请的，故它更适于造表前无法确定表长的情况；(动态申表长)

(3)开放定址法为减少冲突要求装填因子α较小，当结点规模较大时会浪费很多空间，拉链法中α可以大于1，且结点较大时，其指针域可忽略不计，因此节省空间；(空间可节省)

(4)拉链法构造的散列表删除结点易实现，而开放定址法中则不能真正删除结点只能做删除标记。(删除易实现)

20.拉链法也有缺点：当结点规模较小时，用拉链法中的指针域也要占用额外空间，还是开放定址法省空间。

21.在散列表上的运算有查找、插入和删除,主要是查找。这三个操作的算法并不复杂，也容易理解。关于查找操作的时间性能，可看教材p202的表9.1。由表可见，散列表的平均查找长度不是结点个数n的函数，而是装填因子α的函数。α越小，冲突的概率越小，但空间的浪费将增加，当α大小合适时，散列表上的平均查找长度就是一个常数，时间性能是O(1).

第十章文件

1. 对数据结构来说，文件是性质相同的记录的集合。

2.

2.记录是文件中存取的基本单位，数据项是文件可使用的最小单位，数据项有时称字段或者属性。主关键字项(唯一标识一个记录的字段)、次关键字项、主关键字、次关键字。单关键字文件、多关键字文件等。

3.文件的逻辑结构是一种线性结构。

4.文件上的操作主要有两类：检索和维护。并有实时和批量处理两种处理方式。

5.文件的存储结构是指文件在外存上的组织方式，基本的组织方式有：顺序组织、索引组织、散列组织和链组织。文件组织的各种方式往往是这四种基本方式的结合。

6.常用的文件组织方式：顺序文件、索引文件、散列文件和多关键字文件。

7.评价一个文件组织的效率，是执行文件操作所花费的时间和文件组织所需的存储空间。通常文件组织的主要目的，是为了能高效、方便地对文件进行操作，而检索功能的多寡和速度的快慢，是衡量文件操作质量的重要标志。

8.顺序文件：是指按记录进入文件的先后顺序存放、其逻辑顺序和物理顺序一致的文件。

1）一切存储在顺序存储器(如磁带)上的文件都只能顺序文件。这种顺序文件只能按顺序查找法存取(注意，没有折半法了)

2）存储在直接存取存储器(如磁盘)上的顺序文件可以顺序查找法存取，也可以用分块查找法或二分查找法存取。

3）顺序文件多用于磁带。

9.索引文件：组织方式：通常是在文件本身(主文件)之外，另外建立一张表，它指明逻辑记录和物理记录之间一一对应的关系，这张表就叫做索引表，它和主文件一起构成索引文件。

1）索引非顺序文件中的索引表为稠密索引。索引顺序文件中的索引表为稀疏索引。

2）若记录很大使得索引表也很大时，可对索引表再建立索引，称为查找表。通常可达四级索引。

10.索引顺序文件：是最常用的文件组织：因为索引顺序文件的主文件也是有序的，所以它既适合于随机存取也适合于顺序存取。另一方面，索引非顺序文件的索引是稠密索引，而索引顺序文件的稀疏索引，占用空间较少，因此索引顺序文件是最常用的一种文件组织。

1）索引顺序文件常用的有两种：ISAM文件和VSAM文件

11.散列文件：是利用散列存储方式组织的文件，亦称为直接存取文件。

1）它类似于散列表，即根据文件中关键字的特点，设计一个散列函数和处理冲突的方法，将记录散列到存储设备上。与散列表不同的是，对于文件来说，记录通常是成组存放的，若干个记录组成一个存储单位，称为桶。对散列而言，处理冲突的方法主要采用拉链法。

2）散列文件的优点是:文件随机存放，记录不需要排序；插入删除方便；存取速度快；不需要索引区，节省存储空间。缺点是：不能进行顺序存取，只能按关键字随机存取，且询问方式限地简单询问，需要重新组织文件。

12.对被查询的次关键字也建立相应的索引，则这种包含有多个次关键字索引的文件称为多关键字文件。

1）两种多关键字文件的组织方法：多重表文件和倒排表。

2）一般的文件组织中，是先找记录，然后再找到该记录所含的各次关键字；而倒排文件是先给定次关键字，然后查找含有该次关键字的各个记录，因此称为倒排。

转自：https://www.wendangku.net/doc/e614561735.html,/nixun/archive/2005/10/06/495716.aspx

第一天时间:9/11/2003

真想不到,第一次上课竟然会是"9.11"事件纪念日.美国竟然还是不改老毛病,伊拉克战争死了多少平民百姓啊?!!!在此请先为

死难者默哀3分钟,老美如果再这样多管闲事下去,上帝会二度惩罚美国人的啊！

能听到周SIR讲课真的挺开心的,我觉得他讲课比某些高程(高级工程师)还深动[转载时注：此处应该是生动](当然,他的数据结构水平应该不亚于高程),为了考中程,上学期的<算法分析>选修课我也去揍了揍热闹.可惜由于SARS的关系,课只上了将近一半就停了.可以说我报程序员的原因就是因为有周SIR开导我们,听他的课真的是一种享受,不像大学里的某些人,水平不怎么高还在这里作威作福.

好了,发了这么多劳骚,开始转入正题了.

读这文章的人想必都是想报考或者将考程序员的同志们吧!首先一点必须问问自己,我考程序员的目的到底是为了什么?如果你的答案是:"只是为了拿一本证书".那我劝你早点GIVE UP吧!那样学起来会很累,因为没有兴趣.如果你想加入程序员的行列,为将来开发打下坚实的基础,那就试着看完这一小篇读书笔记吧!或许会对你有所帮助.

有句话必须记住:程序员考试仅仅是为了检验自己学到的而已,仅此而已!我想这便是程序员考试的最终意义所在吧!有些事情更注重过程!

数据结构

知识:

1.数据结构中对象的定义,存储的表示及操作的实现.

2.线性:线性表、栈、队列、数组、字符串（广义表不考）

树：二叉树

集合：查找，排序

图(不考)

能力：

分析，解决问题的能力

过程：

● 确定问题的数据。

● 确定数据间的关系。

● 确定存储结构（顺序－数组、链表－指针）

● 确定算法

● 编程

● 算法评价（时间和空间复杂度，主要考时间复杂度）

一、数组

1、存放于一个连续的空间

2、一维～多维数组的地址计算方式

已知data[0][0]的内存地址，且已知一个元素所占内存空间Ｓ求data[i][j]在内存中的地址。

公式：（add+(i*12+j)*S)(假设此数组为data[10][12])

注意：起始地址不是data[0][0]时候的情况。起始地址为data[-3][8]和情况；

3、顺序表的定义

存储表示及相关操作

4、顺序表操作中时间复杂度估计

5、字符串的定义（字符串就是线性表），存储表示

模式匹配算法（简单和KMP（不考））

6、特殊矩阵：存储方法（压缩存储（按行，按列））

三对角：存储于一维数组

三对角问题：已知A ij能求出在一维数组中的下标k;已知下标k求A ij。

7、稀疏矩阵：定义，存储方式：三元组表、十字链表（属于图部分，不考）

算法

● 数组中元素的原地逆置；对换

● 在顺序表中搜索值为X的元素；

● 在有序表中搜索值为X的元素；（折半查找）

● 在顺序表中的第i个位置插入元素X；

● 在顺序表中的第i个位置删除元素X；

● 两个有序表的合并；算法？

线性表数据结构定义：

数据结构期末考试复习笔记

判断： 1.线性表的链式存储结构优于顺序存储错误 2.单链表的每个节点都恰好包含一个指针域错误 3.线性表中的元素都可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因 此属于同一数据对象正确 4.在线性表的顺序存储结构中，逻辑上相邻的两个元素在屋里位置上并不一定紧邻。错 误 5.在线性表的数据结构中，插入和删除元素时，移动元素的个数和该元素的位置有关。正 确 6.顺序存储的线性表可以实现随机存取正确 7.栈一定是顺序存储的线性结构错误 8.一个栈的输入序列为A，B,C,D，可以得到输入序列为C,A,B,D 错误 9.队列是一种后进先出的线性表错误 10.树结构中每个节点最多只有一个直接前驱正确 11.二叉树的前序遍历中，任意一个节点均处于其子树节点的前面正确 12.在栈空的情况下，不能做出出栈操作，否则产生溢出正确 13.在前序遍历二叉树的序列中，任何节点的子树的所有节点都是直接跟在该节点之后正 确 填空： 1.在N个节点的顺序表中删除一个节点平均需要移动（（N-1）/2）个节点，具体的移 动次数取决于（表长N和删除位置） 2.在单链表中除首节点外，任意节点的存储位置都由（直接前驱）节点中的指针指示 3.树中节点的最大层次称为树的（度） 4.由一颗二叉树的前序序列和（中）序列可唯一确定这棵二叉树 5.哈弗曼树的带权路径长度（最小）的二叉树 6.二插排序树任意节点的关键字值（大于）其左子树中各节点的关键字值（小于）其 右子树中的各节点关键字值 7.二分查找法，表中元素必须按（关键字有序）存放 选择： 1.用单链表方式存储的线性表，储存每个节点需要两个域，一个数据域，另一个是（B 指针域） 2.设A1，A2，A3为三个节点；P，10，,2代表地址，则如下的链表存储结构称为（B 单链表） 3.单链表的存储密度（C 小于1） 4.在线性表中（B 中间元素）只有一个直接前驱和一个直接后续 5.两个指针P和Q，分别指向单链表的两个元素P所指元素时Q所指元素前驱的条 件是（D P==Q） 6.在栈中存取数据的原则是（B 后进先出） 7.顺序栈判空的条件是（C top==-1） 8.串是一种特殊的线性表，其特殊性体现在（B 数据元素是一个字符） 9.求字符串T和字符串S中首次出现的位置的操作为（C 串的模式匹配） 10.深度为H的二叉树至多有（B 2H-1）个节点

2021北京科技大学计算机科学与技术考研真题经验参考书

我本科在燕山大学，作为河北省的一个旅游城市，旅游季节超级多以外，真的没有开拓我太多眼界，但是鉴于老师负责而且很专业，教会了我很多知识。但是我们专业，在一二线城市，机会多，企业多，就业及科研合作机会也多，所以，选择学校，一定要先看城市，再选学校。对我而言，研究生考进北科大，也是一项很大的挑战和提升。下面是我整理的一些考研经验与心得，希望能助你一臂之力，早日考进自己理想的学校。 数学： 对于计算机科技而言，数学很重要。我们专业是以数学逻辑为基础的，数据结构是建立在数学基础之上的一门学科。可以说，数学是我们的工具书。数学真的很重要。要从3月份就开始复习，这样后面会比较轻松。建议先从基础教材着手，看完教材，要做课后练习题，测试自己是否掌握了本章节的知识。这样，高数和线性代数的课本过一遍，需要2-3个月的时间。第二阶段就要做大量的练习了，研数盒子，这个公众号的特点是习题为主，数学一定要多加练习，这个公众号就是以练习各种习题为主，每周都会发各种作业和讲解，研数盒子有一套教材叫做研数800题非常好。做的过程中，对错题要着重注意并记录一下，建立一个错题本，然后针对没做对的题，分析归纳，然后回归到课本上，查到对应章节，重新温习。这套练习要刷个3遍左右，每一遍你都会有新的认识和体会，个人觉得效果会比做3套不同的题更有效。3遍下来，精读的效果就很明显了，这就是“温故知新”的道理。10月开始，真题要开始做起来了，向上面一样，建立错题本，这个本会是你考研备考后期独一无二的宝典。总之，数学真的很重要，要自始至终坚持到底，除了反复多加练习，还要多思考。 英语： 阅读理解很重要，备考需要坚持每天2篇阅读，开始的时候要精度，好好分析一下句式，掌握好主谓宾从，整段意思也就很容易理解了。学会分析句式以后，后续就会容易很多。再就是单词部分，买一本基础的单词书<<一本单词>>，早晨背完，晚上回忆，过电影一样的，重要的单词，要熟悉到知道在哪个位置，上面的解释是什么。没事看看，不想看书的时候看看，随手看看，遍数多了，自然会记住了，或者每个考生都有自己独特的单词记忆方法，请大家用尽十八般武艺，只有一个目的——背好单词，大家也可以关注蛋核英语公众号。再说说作文，作文呢，一定要积累名言警句，有华丽的辞藻才能表达出自己的观点对不对？作文

郝斌数据结构自学笔记--知识点+程序源代码

郝斌数据结构自学笔记 --知识点+程序源代码 By-HZM 1_什么叫做数据结构 数据结构概述 定义 我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找某个元素，删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应的操作也叫算法。 ~ 数据结构=个体的存储+个体的关系存储 算法=对存储数据的操作 2_衡量算法的标准 算法 解题的方法和步骤 ~ 衡量算法的标准 1）时间复杂度：大概程序执行的次数，而非执行的时间 2）空间复杂度：算法执行过程中大概所占用的最大内存 3）难易程度 4）健壮性 3_数据结构的特点 【 数据结构的地位 数据结构是软件中最核心的课程 程序=数据的存储+数据的操作+可以被计算机执行的语言 4_预备知识_指针_1 5_预备知识_指针_2 * 指针的重要性： 指针是C语言的灵魂 定义：

地址： 地址是内存单元的编号,从0开始的非负整数，范围：0-FFFFFFFF【0-4G-1】 CPU=====地址线，控制线，数据线=====内存 指针： … 指针就是地址，地址就是指针。 指针变量是存放内存单元地址的变量。 指针的本质是一个操作受限的非负整数。 分类： 1.基本类型的指针 2.指针和数组的关系 ? 变量并不一定连续分配，随机分配内存。 内存： 内存是多字节组成的线性一维存储空间。 内存的基本划分单位是字节。 每个字节含有8位，每一位存放1个0或1个1. 内存和编号是一一对应的。 （ 软件在运行前需要向操作系统申请存储空间。在软件运行期间，该软件所占空间不再分配给其他软件。当软件运行完毕后，操作系统将回收该内存空间（操作系统并不清空该内存空间中遗留下来的数据）。 NOTE：1）指针变量也是变量，普通变量前不能加*，常亮和表达式前不能加&。 2）局部变量只在本函数内部使用。 如何通过被调函数修改主调函数中普通变量的值。 1）实参为相关变量的地址； < 2）形参为以该变量的类型为类型的指针变量； 3）在被调函数中通过 *形参变量名的形式的形式就可以修改主函数。 CASE 1 #include<> int main(void) { |

数据结构复习笔记

数据结构复习笔记 作者: 网络转载发布日期: 无 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。如整数这个集合中，10这个数就可称是一个数据元素.又比如在一个数据库(关系式数据库)中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。 数据结构的定义虽然没有标准，但是它包括以下三方面内容：逻辑结构、存储结构、和对数据的操作。这一段比较重要，我用自己的语言来说明一下，大家看看是不是这样。 比如一个表(数据库)，我们就称它为一个数据结构，它由很多记录(数据元素)组成，每个元素又包括很多字段(数据项)组成。那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从结点(其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但说的是同一个东东)之间的关系来分析的，对于这个表中的任一个记录(结点)，它只有一个直接前趋，只有一个直接后继(前趋后继就是前相邻后相邻的意思)，整个表只有一个开始结点和一个终端结点，那我们知道了这些关系就能明白这个表的逻辑结构了。 而存储结构则是指用计算机语言如何表示结点之间的这种关系。如上面的表，在计算机语言中描述为连续存放在一片内存单元中，还是随机的存放在内存中再用指针把它们链接在一起，这两种表示法就成为两种不同的存储结构。(注意，在本课程里，我们只在高级语言的层次上讨论存储结构。) 第三个概念就是对数据的运算，比如一张表格，我们需要进行查找，增加，修改，删除记录等工作，而怎么样才能进行这样的操作呢? 这也就是数据的运算，它不仅仅是加减乘除这些算术运算了，在数据结构中，这些运算常常涉及算法问题。 弄清了以上三个问题，就可以弄清数据结构这个概念。 -------------------------------------------------------------------------------- 通常我们就将数据的逻辑结构简称为数据结构，数据的逻辑结构分两大类：线性结构和非线性结构(这两个很容易理解) 数据的存储方法有四种：顺序存储方法、链接存储方法、索引存储方法和散列存储方法。-------------------------------------------------------------------------------- 下一个是难点问题，就是算法的描述和分析，主要是算法复杂度的分析方法及其运用。首先了解一下几个概念。一个是时间复杂度，一个是渐近时间复杂度。前者是某个算法的时间耗费，它是该算法所求解问题规模n的函数，而后者是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此，在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度T(n)=O(f(n)简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。 此外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。 常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。 时间复杂度的分析计算请看书本上的例子，然后我们通过做练习加以领会和巩固。 数据结构习题一 --------------------------------------------------------------------------------

2012版《数据结构高分笔记》更新补丁之外部排序

※特别章外部排序（2012版《数据结构高分笔记》更新补丁） ·外部排序简介 所谓外部排序，即对外存中的数据进行排序（相对于内部排序而言），也可以说是对文件中的数据进行排序。有了内部排序算法，为什么还要外部排序？因为文件太大，内存放不下。外排做法可以概括为一句话：将内存作为工作空间来调整外存中数据的位置。 具体可以分成以下三个要点： ①文件在外存中的组织； ②文件在内存中的排序； ③文件在内外存之间的交换。 说明：本补丁是2012年数据结构考研大纲新增内容，虽然知识点不多，但由于第一年被列入考试范围，所以大家要重视。 ·归并排序法 归并排序法是外排序中最常用的方法，分为两个执行阶段。第一阶段：将文件中的数据分段输入到内存中，在内存中用内排序方法对其分类，这样排序完的文件段称作归并段，然后将其写回外存中而在外存中形成了许多初始归并段。第二阶段：对这些初始归并段采用某种归并方法，进行多遍归并，最后在外存上形成整个文件的单一归并段，也就完成了这个文件的外排序。 说明：外排序中的归并排序法和内排序中的归并法是类似的，都是由小单元逐渐归并成单元的过程，注意对比，加深理解。 归并排序算法分两个阶段： 1.初始归并段的形成 其过程是根据缓冲区大小，由文件输入（由外存读入内存）记录，当记录充满缓冲区后，选择最小的（以递增排序为例）记录输出（由内存写出到外存），其空缺位置由下一个输入记录来取代，输出的记录成为当前初始归并段的一部分。如果新输入的记录不能成为当前生成的归并段的一部分，即它比生成的当前部分归并段最大的记录要小（如例1中的关键字11，比15要小，不可能出现在当前归并段中），它将等待生成下一个归并段时提供选择。反复进行上述操作，直到所有新输入的记录关键字都小于最后输出记录的关键字时（如步骤9中的所有关键字都比83小，则以83为结尾的归并段生成完毕），就生成了一个初始归并段。接着继续生成下一个归并段，直到全部记录都处理完毕为止。 下面通过例题来具体说明一下。 例1.设输入文件的各个记录的关键字为： 15,19,04,83,12,27,11,25,16,34,26,07,10,90,06, ... ... 假设内存缓冲区可容纳4个记录，成初始归并段。如下表所示，给出了生成初始归并段过程中各步的缓冲区内容和输出结果。

数据结构学习总结

数据结构学习总结 经过一学期的学习，我对数据结构有了我自己的认识。一开始，我以为它和C语言和C++一样，都是讲一门语言。但学习之后，发现事实并不是这样，在数据结构的学习中，有线性表，有队，有栈，有树，有图等等。这些看起来没有关系，其实之间有着千丝万缕的联系。线性表是其中最简单的，所以在前几章学习，后面依次逐章变难，学起来也很吃力。 《数据结构与算法》以基本数据结构和算法设计策略为知识单元，系统地介绍了数据结构的知识与应用、计算机算法的设计与分析方法，主要内容包括线性表、树、图和广义表、算法设计策略以及查找与排序算法等。 线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。线性表具有如下的结构特点：均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数据类型和长度。有序性：各数据元素在线性表中的位置只取决于它们的序号，数据元素之前的相对位置是线性的，即存在唯一的“第一个“和“最后一个”的数据元素，除了第一个和最后一个外，其它元素前面均只有一个数据元素直接前驱和后面均只有一个数据元素（直接后继）。在实现线性表数据元素的存储方面，一般可用顺序存储结构和链式存储结构两种方法。链式存储结构将在本网站线性链表中介绍，本章主要介绍用数组实现线性表数据元素的顺序存储及其应用。另外栈、队列和串也是线性表的特殊情况，又称为受限的线性结构。 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生

数据结构复习笔记

第一章概论 1.数据：信息的载体,能被计算机识别、存储和加工处理。 2.数据元素：数据的基本单位，可由若干个数据项组成，数据项是具有独立含义的最小标识单位。 3.数据结构：数据之间的相互关系，即数据的组织形式。 它包括：1）数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，独立于计算机； 2）数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。 3）数据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用的运算：检索/插入/删除/更新/排序。 4.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的存储结构是逻辑结构用计算机语言的实现。 5.数据类型：一个值的集合及在值上定义的一组操作的总称。分为：原子类型和结构类型。 6.抽象数据类型：抽象数据的组织和与之相关的操作。优点：将数据和操作封装在一起实现了信息隐藏。 7. 抽象数据类型ADT：是在概念层上描述问题；类：是在实现层上描述问题；在应用层上操作对象（类的实例）解决问题。 8.数据的逻辑结构，简称为数据结构，有： （1）线性结构，若结构是非空集则仅有一个开始和终端结点，并且所有结点最多只有一个直接前趋和后继。 （2）非线性结构，一个结点可能有多个直接前趋和后继。 9.数据的存储结构有： 1）顺序存储，把逻辑相邻的结点存储在物理上相邻的存储单元内。 2）链接存储，结点间的逻辑关系由附加指针字段表示。 3）索引存储，存储结点信息的同时，建立附加索引表，有稠密索引和稀疏索引。 4）散列存储，按结点的关键字直接计算出存储地址。 10.评价算法的好坏是：算法是正确的；执行算法所耗的时间；执行算法的存储空间（辅助存储空间）；易于理解、编码、调试。

操作系统可用来进行考研复习资料(1)

第八章死锁习题及答案 一、填空题 1．进程的“同步”和“互斥”反映了进程间① 和② 的关系。 【答案】①直接制约、②间接制约 【解析】进程的同步是指在异步环境下的并发进程因直接制约而互相发送消息，进行相互合作、相互等待，使得各进程按一定的速度执行的过程；而进程的互斥是由并发进程同时共享公有资源而造成的对并发进程执行速度的间接制约。 2．死锁产生的原因是① 和② 。 【答案】①系统资源不足、②进程推进路径非法 【解析】死锁产生的根本原因是系统的资源不足而引发了并发进程之间的资源竞争。由于资源总是有限的，我们不可能为所有要求资源的进程无限地提供资源。而另一个原因是操作系统应用的动态分配系统各种资源的策略不当，造成并发进程联合推进的路径进入进程相互封锁的危险区。所以，采用适当的资源分配算法，来达到消除死锁的目的是操作系统主要研究的课题之一。 3．产生死锁的四个必要条件是① 、② 、③ 、 ④ 。 【答案】①互斥条件、②非抢占条件、③占有且等待资源条件、④循环等待条件 【解析】 互斥条件：进程对它所需的资源进行排它性控制，即在一段时间内，某资源为一进程所独占。 非抢占条件：进程所获得的资源在未使用完毕之前，不能被其它进程强行夺走，即只能由获得资源的进程自己释放。 占有且等待资源条件：进程每次申请它所需的一部分资源，在等待新资源的同时，继续占有已分配到的资源， 循环等待条件：存在一进程循环链，链中每一个进程已获得的资源同时被下一个进程所请求。 4．在操作系统中，信号量是表示① 的物理实体，它是一个与② 有关的整型变量，其值仅能由③ 原语来改变。 【答案】①资源，②队列，③P-V 【解析】信号量的概念和 P-V原语是荷兰科学家 E．W．Dijkstra提出来的。信号量是一个特殊的整型量，它与一个初始状态为空的队列相联系。信号量代表了资源的实体，操作系统利用它的状态对并发进程共享资源进行管理。信号量的值只能由P-V原语来改变。 5．每执行一次P原语，信号量的数值S减1。如果S>=0，该进程① ；若S<0，则② 该进程，并把它插入该③ 对应的④ 队列中。 【答案】①继续执行，②阻塞（等待），③信号量，④阻塞（等待） 【解析】从物理概念上讲，S＞0时的数值表示某类资源可用的数量。执行 一次P原语，意味着请求分配一个单位的资源，因此描述为S=S－1。当S<0时，表示已无资源，这时请求资源的进程将被阻塞，把它排在信号量S的等待队列中。此时，S的绝对值等于信号量队列上的阻塞的进程数目。

面经笔记数据结构

数据结构及算法知识 1.字典树构造及其优化与应用 字典树的核心就是空间换时间，利用字符串的公共前缀来避免无谓的字符串比较，降低查询时间 性质： - 根结点不包含字符，除了根结点每个结点都包含一个字符 - 从根结点到某一结点的路径经过的字符连接起来就是该结点对于的字符串 - 查询和建树可以同时进行 有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。 思路：首先要求得每个词的频率，1G无法放入内存，需要分成多个小文件，对每个小文件的词进行统计 （1）散列分治：顺序读取文件，对每个词，可以hash(x)P00(只要不小于1024个文件，是为了保证每个小文件可以放入内存)，这样被映射为5000个小文件，每个文件大概200K，每个文件最少1250个单词 （2）对于每个小文件，利用hash_map/字典树记录每个单词出现的频率，（3）用100个元素的最小堆，选出每个文件中的频率最大的100个单词 （4）对这5000个小文件进行归并排序，选出最大的100个。 2.大规模文本文件，全是单词，求前10词频的单词（Top k问题是热门问题）

3.如何判断时间，空间复杂度是否为O（logn） 最直观的判断就是程序中采用了二分，且二分后只运算数据的一半。但如果两部分都运算的话，时间复杂度就是O(nlogn)了。其实不一定是二分，只不过二分比较常用罢了 4.各个算法的时间和空间复杂度 5.M个有序链表取前k大个元素

6.红黑树的调整 红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一倍 1.每个节点要么是红色，要么是黑色。 2.根节点必须是黑色 3.红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）。 4.对于每个节点，从该点至null（树尾端）的任何路径，都含有相同个数的黑色节点。 在树的结构发生改变时（插入或者删除操作），往往会破坏上述条件3或条件4，需要通过调整使得查找树重新满足红黑树的条件。 调整可以分为两类：一类是颜色调整，即改变某个节点的颜色；另一类是结构调整，即改变检索树的结构关系。结构调整过程包含两个基本操作：左旋（Rotate Left），右旋（RotateRight）。

2018北大计算机考研经验分享

2018北大计算机考研经验分享 我本科毕业于北京科技大学计算机科学与技术专业，研究生将就读于北京大学计算机技术专业。初试考研总分接近370+分，计算机基础综合135分，在专业课上算是有些心得吧。 写这篇经验贴的初衷一是看过很多经验贴，都是比较散乱的回顾+感受，没有系统的复习方法；二是我在新祥旭考研一对一做专业课辅导老师，算是给自己打个广告吧，多说一句，我主要是针对考北大计算机专业的学生。当然，虽然打了一下广告，但是这篇帖子的经验还是希望大家认真看，我觉得还是能够对学弟学妹们有所裨益的。 ，下面主要和大家聊一聊北大计算机考研的情况，政治、英语、数学这些课我就不多说了，这几门课程的资料、老师都是比较成熟且成功的，大家在网上多看看就知道怎么回事了。今天，主要是说专业课以及北大计算机的招录情况。 【北大招录情况】 2018年北大软微计算机技术复试线：复试线为300分，单科线也是50+80。具体的招录比现在基本是没有相关数据的，但是招生人数还是可查的，根据软微学院官网数据：整个软件与微电子学院招收全日制654人，非全日制156人。其中计算机技术专业全日制招生310人，

包含推免生接近70人，留给其他考生的名额为240左右。 总之，现在是大数据时代，北大计算机技术的关注度也越来越高，所以以后考研竞争难度也会越来越大。 【参考书目】 822计算机基础综合 专业课教材 《数据结构》（C语言版）严蔚敏清华大学出版社 《计算机操作系统》汤子瀛西安电子科技大学出版社 《计算机网络》谢希仁电子工业出版社 《计算机组成原理》唐朔飞高等教育出版社 专业辅导书： 王道系列 《数据结构考研复习指导》 《计算机组成原理考研复习指导》 《操作系统考研复习指导》 《计算机网络考研复习指导》 《计算机专业基础综合考试指导全书》 《计算机专业基础综合考试名校真题精析》 《计算机专业基础综合考试最后8套模拟题》

操作系统第一章笔记

第一章操作系统引论 1、Android DOS LINUX WINDOWS Symbian iOS UNIX CentOS是操作系统 2、计算机系统的组成 计算机系统：计算机硬件：运算器、控制器、存储器、输入设备、输出设备 计算机软件：包括操作系统 3、相关概念 裸机：没有配置任何软件的计算机。 软件:是在硬件基础之上对硬件的性能加以扩充和完善。 虚拟机：一个裸机在每加上一层软件后，就变成了一个功能更强的机器，我们把这种“功能更强的机器”称之为“虚拟机”或“扩展机”。 4、操作系统的定义 操作系统（operating system，简称OS）操作系统是一组控制和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及方便用户使用的程序的集合。操作系统是系统软件的核心。 5、操作系统的目标 （1）.方便性：用户通过命令使用计算机 （2）.有效性：保持忙碌且内外存数据有序,节省空间 （3）.可扩充性：采用层次化结构便于增加和修改 （4）.开放性：遵循OSI国际标准彼此兼容实现互连 6、操作系统的作用 （1）OS作为用户与计算机硬件系统的接口 （2）OS作为计算机系统资源的管理者 （3）OS用作扩充机器 7、推动操作系统发展的主要动力 ?不断提高计算机资源利用率 ?方便用户 ?器件的不断更新换代 ?计算机体系结构的不断发展 ?不断的提出新的要求 8、计算机的发展过程 计算机发展分为四个阶段： ?1946～50年代末：第一代，电子管时代，无操作系统。 ?50年代末～60年代中：第二代，晶体管时代，批处理系统。 ?60年代中～70年代中：第三代：集成电路时代，多道程序设计。 ?70年代中期～至今：第四代：大规模、超大规模集成电路时代，分时系统。 9、操作系统的发展过程 （1）. 人工操作方式 电子管计算机，无操作系统，由手工控制作业的输入输出,通过控制台开关启动 程序运行。 人工操作方式的缺点： 用户独占全机。计算机及其全部资源只能由上机用户独占。

自考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、考研题目大致分为两种类型，一类是基本概念、技术和方法（即问答题），一类是基本原理的综合应用（即应用题）。P、V操作题肯定考。 2、一般说来，具体操作系统如Windows、Linux/Unix不考，但讲解原理时引用的UNIX实现方法还要考（主要集中在4-6章）。 3、内容：1-9章，重点4-6章。 4、考试的思路两方面兼顾：灵活运用与知识点的全面掌握 说明：蓝色表示重要概念、技术和方法，绿色表示应用。 第1章操作系统概述 ●资源、资源管理的观点 ●操作系统、操作系统的地位和作用、操作系统的特征、操作系统的设计目标 ●历史上著名的操作系统 ●研究操作系统的观点 ●操作系统分类（工作方式，特点，追求目标，与其它类型的区别，吞吐量，时间片） 第2章操作系统的硬件环境 ●CPU状态，管态和目态，程序状态字 ●存储体系 ●缓冲技术 ●中断系统 ●中断、中断源、中断类型（强迫性中断[硬件故障中断、程序性中断、时钟中断、控制 台中断、输入输出中断]，自愿性中断） ●中断响应（中断寄存器，程序状态字，中断响应过程） ●中断处理、各类中断事件的处理 中断优先级、中断屏蔽、中断嵌套处理 ●时钟 第3章作业管理 ●用户与操作系统的接口（操作员级接口，程序员级接口） ●批处理系统作业管理（作业组成，作业控制语言，作业说明书，作业输入[预输入程序， 数入井，作业表，预输入表，收容状态]，作业调度，作业调度的必要条件，设计作业调度算法的准则，作业调度算法[先来先服务，短作业优先，最高响应比优先，优先数，均衡调度]，作业调度与进程调度的关系，作业的控制执行过程，作业的完成[缓输出程序，输出井]）

全国2010年1月自考数据结构导论考试试题,答案,笔记

全国2010年1月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未 选均无分。 1.下述文件中适合于磁带存储的是（ A ） A.顺序文件 B.索引文件 C.散列文件 D.多关键字文件 2.某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为（ D ） A.acbed B.becab C.deabc D.cedba 3.含有n个结点的二叉树用二叉链表表示时，空指针域个数为( C ) A.n-1 B.n C.n+1 D.n+2 注：子域为2n个，有n-1个孩子。 4.在一个图中，所有顶点的度数之和与图的边数的比是( C) A.1∶2 B.1∶1 C.2∶1 D.4∶1 5.长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为( A) A.O(1) B.O(1og2n) 二分法注：若只有尾指针，那么入和出都为O(1) C.O(n) （入队） D.O(n2) -冒泡 6.下述几种排序方法中，要求内存量最大的是( C ) A.插入排序 B.快速排序 C.归并排序 D.选择排序 7.对n个不同值进行冒泡排序，在元素无序的情况下比较的次数为( D) A.n-1 B.n C.n+1 D.n(n-1)／2 8.对线性表进行二分查找时，要求线性表必须( C) A.以顺序方式存储 B.以链式方式存储 C.以顺序方式存储，且结点按关键字有序排列 D.以链接方式存储，且结点按关键字有序排列 9.在表长为n的顺序表上做删除运算，其平均时间复杂度为( B ) A.O(1) B.O(n) 注：在双向循环链表中，删除最后一个结点 C.O(nlog2n) D.O(n2) 的时间复杂度为O(1)

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

： 第一张概论 引言 两项基本任务：数据表示，数据处理 软件系统生存期：软件计划，需求分析，软件设计，软件编码，软件测试，软件维护 由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立，选择和实现是数据结构的核心问题。 机外表示------逻辑结构------存储结构 ~ 处理要求-----基本运算和运算-------算法 数据，逻辑结构和运算 数据：凡是能够被计算机存储，加工的对象通称为数据 数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理。又称元素，顶点，结点，记录。 数据项：数据项组成数据元素，但通常不具有完整确定的实际意义，或不被当做一个整体对待。又称字段或域，是数据不可分割的最小标示单位。 — 1.2.2 数据的逻辑结构 逻辑关系：是指数据元素之间的关联方式，又称“邻接关系” 逻辑结构:数据元素之间逻辑关系的整体称为逻辑结构。即数据的组织形式。 四种基本逻辑结构： 1 集合：任何两个结点间没有逻辑关系，组织形式松散 2 线性结构：结点按逻辑关系依次排列成一条“锁链” 3 树形结构：具有分支，层次特性，形态像自然界中的树 { 4. 图状结构：各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接。 注意点: 1.逻辑结构与数据元素本身的形式，内容无关。 2.逻辑结构与数据元素的相对位置无关 3.逻辑结构与所含结点个数无关。 运算：运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。 。 加工型运算：改变了原逻辑结构的“值”，如结点个数，结点内容等。 引用型运算:不改变原逻辑结构个数和值，只从中提取某些信息作为运算的结果。 引用：查找，读取 加工：插入，删除，更新 同一逻辑结构S上的两个运算A和B, A的实现需要或可以利用B，而B的实现不需要利用A，则称A可以归约为B。

数据结构笔记精编版

//2018/5/23 数据结构概述： 预备知识 模块一：线性结构 连续存储[数组] 离散结构[链表] 线性结构的两种常见应用之一栈（堆栈） 线性结构的两种常见应用之二队列 专题：递归 1.1+ 2......+100的和 2.求阶乘 3.汉诺塔 4.走迷宫 模块二：非线性结构 树 图 模块三：查找和排序 折半查找 排序：冒泡插入选择快速排序归并排序补录：Java中容器和数据结构相关知识 Iterator接口 Map 哈希表 严蔚敏---高一凡---黄国瑜

//2018/5/24 数据结构概述 定义 我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找或删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应操作叫做算法。 特定的数据类型:个体如何保存 特定的存储结构:个体与个体的关系如何保存 数据结构 = 个体的存储 + 个体关系的存储 算法（狭义） = 对存储数据的操作 算法：即解题的方法和步骤 衡量算法的标准 1.时间复杂度[重要] 大概程序要执行的次数，而非执行的时间 2.空间复杂度[重要] 算法执行过程中大概所占用的最大内存 3.难易程度 4.健壮性 数据结构的地位 数据结构是软件中最核心的课程。 程序 = 数据的存储 + 数据的操作 + 可以被计算机执行的语言

预备知识： 指针 结构体 动态内存的分配和释放 指针： 指针的重要性: 表示一些复杂的数据结构 快速的传送数据 使函数返回一个以上的值 能否直接访问硬件 能够方便的使用数组和字符串 是理解面向对象语言中引用的基础 指针是C语言的灵魂 定义 地址 内存单元的编号 从0开始的非负整数 范围0-FFFFFFFF 【0 到 4G-1】 注：无论一个变量有多大，其地址只用第一个字节的地址表示， 均只占四个字节。 指针 指针就是地址地址就是指针 指针变量就是存放内存单元地址的变量 指针本质上就是一个操作受限的非负整数 分类

“数据结构”读书笔记

“数据结构”读书笔记示例：第2章线性表 学习线索：逻辑结构→基本运算定义→存储结构→基本运算实现（复杂度分析→应用实例） 1. 逻辑结构：是由n(n≥0)个数据元素组成的有限序列。 2. 基本运算定义：（P.16） （1）Init_List(L)，线性表初始化； （2）Length _ List (L)，求线性表的长度； （3）Get_ List (L，i)，取表元； （4）Locate_ List (L，x)，按值查找； （5）Insert_ List (L，x，i)；插入操作； （6）Delete_ List (L，i)，删除操作。 3. 存储结构： （1）顺序表：把线性表的结点按逻辑次序存放在一组地址连续的存储单元里。 顺序存储的结构体定义： typedef struct { datatype data[MAXSIZE]; /* 一维数组子域*/ int last; /* 表长度子域*/ } SeqList; /* 顺序存储的结构体类型*/ 4-1. 顺序表的基本运算的实现（算法及其复杂度分析、应用实例：顺序表的划分、合并、比较大小） （2）单链表：只有一个链域的链表称单链表。 结点结构： Data（节点值）Next（后继结点地址） 其中data是数据域，next是指针域 链式存储的结构体定义： typedef struct lnode { datatype data; /* 数据子域*/ struct lnode *next; /* 指针子域*/ } LNode，*LinkList; /* 链式存储的结点结构类型*/ 4-2. 单链表的基本运算的实现（算法及其复杂度分析、应用实例：链表逆置、归并） 单链表的发展：循环链表、双向链表 顺序表和链表的比较 1）基于空间： 2）基于时间：“数据结构”读书笔记（线性结构部分）

[整理][郝斌老师]自学数据结构大纲笔记

[整理][郝斌老师]自学数据结构大纲笔记 [郝斌老师]自学数据结构大纲笔记 数据结构概述(教材选用严蔚敏、吴伟民，该书程序是伪算法 具体的程序是高一凡，西电的，大牛，只有 程序。还有一本书，台湾的黄国瑜自己写的 只有思路，程序是另外一个合作的清华的写 的，可惜很多错的。) 学完数据结构之后会对面向过程的函数有一个更深的了解 定义 我们如何把现实中大量而复杂的问题以特定的数据类型(单 个数据怎样存储,)和特定的存储结构(个体的关系) 保存到主存储器(内存)中，以及在此基础上为实现某个功能 (比如查找某个元素，删除某个元素，对所有元素进行排序) 而执行的相应操作，这个相应的操作也叫算法。(比如班里有 15个人，其信息量也许一个数组就搞定了，但是假如10000个， 怎么办,内存也许没有这么多连续的空间，所以我们改用链表， you see这就是与存储有关系。又比如，人事管理系统的信息存储， 因为存在着上下级的关系，所以数组和链表就无能为力了， 这时候我们用树，再比如我们做的是交通图，站和站之间肯定要连通，这时候以上的存储方式又无能为力了，所以我们又有了图。图 就是每个结点都可以和其他结点产生联系。所以当我们要解决 问题时，首先要解决的是如何把这些问题转换成数据，先保存 到我们的主存中，)

数据结构 = 个体 + 个体的关系 算法 = 对存储数据的操作 算法 解题的方法和步骤 衡量算法的标准 1、时间复杂度 大概程序要执行的次数，而非执行的时间。 2、空间复杂度 算法执行过程中大概所占用的最大内存 3、难易程度(主要是应用方面看重) 4、健壮性(不能别人给一个非法的输入就挂掉) 数据结构的地位 数据结构是软件中最核心的课程 程序 = 数据的存储，数据的操作，可以被计算机执行的语言(已经提供) (学完数据结构，想用一种语言去实现它，必须有指针，数据结构java 版，就胡扯，变味，因为我们要讲链表，就是通过指针链在一起的。比如在java中A aa = new A();本质上，aa是个地址) 预备知识 指针 指针的重要性:(内存是可以被CPU直接访问的，硬盘不行 主要靠地址总线，数据总线，控制总线。) 指针是C语言的灵魂 定义 地址

数据结构复习笔记

数据结构复习笔记 一、绪论 1.数据：能被计算机表示、存储和加工处理的一切信息（数值型和非数值型） 2.数据的基本单位：数据元素 3.组成数据元素的不可分割的最小单位：数据项 4.数据对象：性质相同的数据元素的集合 5.数据类型：指定一种数据对象的类型 6.数据的逻辑结构：指数据之间的逻辑关系, 即指数据元素之间的关联方式或邻接关系 7.数据的存储结构：指数据在计算机中存储的位置 8.运算的集合：定义在逻辑结构上的一组操作 9.数据结构: 按照某种逻辑关系组织起来的一批数据, 按一定的存储方法把它存储在计算机中, 并在这些数据上定义了一个运算的集合 10.逻辑结构分类：线性结构、集合、树形结构、图型或网状结构 11.线性结构：仅一个开始结点、仅一个终端结点；其它都是内部结点，且都有且仅有一个前驱和一个后驱（一对一） 12.集合：结构中数据元素只具有“同属于一个集合”的关系 13.树型结构的特点：有且仅有一个根结点，其它结点有且仅有一个前驱结点，对于非根结点都存在从根到该结点的一条路径（一对多） 14.图型结构的特点：结构中的数据元素存在多对多的关系 15.存储结构：顺序存储结构、链式存储结构 16.顺序存储结构特点：逻辑结构上相邻的两个元素在物理结构上也相邻. 即前驱的结束是后继的开始 17.链式存储结构：存储空间不连续，但保持了逻辑关系 18.算法的五个特征：有穷性、确定性、可行性、输入、输出 19.算法与程序的区别：程序不一定满足有穷性；程序是机器可执行的语言编写的 20.算法评价：正确、简单、可读、健壮、高效 21.算法分析方法：事后统计和事前分析、时间复杂度和空间复杂度 22.影响算法时间代价的因素：输入规模、算法效率、输入顺序、机器、设计者 23.Ο(1)＜O(log2n)＜O (n)＜O (nlog2n)＜O (n2)＜O (n3)＜…＜O (2n)＜O (n!) 二、线性表 1.线性结构特点：唯一第一数据元素、唯一最后数据元素、其他数据元素仅有一个前趋和仅有一个后驱 2.顺序表的优点：无需为表示数据元素之间的逻辑关系而增加额外存储空间；可方便地随机存取表中任一元素 3.顺序表的缺点：预先为数据元素分配空间；插入和删除时必须移动大量元素 4.单链表的插入：newnode→next = p→next；p→next = newnode 5.单链表的删除：p→next = q→next；delete q 6.双向链表的删除：current ->prior->next= current ->next；current ->next->prior= current ->prior；delete current 7.双向链表的插入：p->prior=current；p->next= current ->next；current->next->prior=p；current->next=p 8.顺序表与链表：顺序表结点总数大概确定，表中结点数目稳定（插删操作少）；链表结点数目不预知且动态变化 三、栈和队列 1.栈的逻辑结构：允许插入和删除的一端称为栈顶，另一端称为栈底，特点是后进先出或先进后出 2.先进后出题：若abc顺序入栈，a入栈后可以直接出栈 3.队列的逻辑结构：在一端进行插入操作（队尾），而另一端进行删除操作的线性表（队头），特点是先进先出 4.队满判定条件：(rear+1) % QueueSize==front