自考02331数据结构重点总结(最终修订)
自考02331数据结构重点总结(最终修订)
第一章概论
1.瑞士计算机科学家沃思提出：算法+数据结构=程序。算法是对数据运算的描述，而数据结构包括逻辑结构和存储结构。由此可见，程序设计的实质是针对实际问题选择一种好的数据结构和设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。
2.数据是信息的载体。数据元素是数据的基本单位。一个数据元素可以由若干个数据项组成，数据项是具有独立含义的最小标识单位。数据对象是具有相同性质的数据元素的集合。
3.数据结构指的是数据元素之间的相互关系，即数据的组织形式。
数据结构一般包括以下三方面内容：数据的逻辑结构、数据的存储结构、数据的运算
①数据的逻辑结构是从逻辑关系上描述数据，与数据元素的存储结构无关，是独立于计算机的。
数据的逻辑结构分类:线性结构和非线性结构。
线性表是一个典型的线性结构。栈、队列、串等都是线性结构。数组、广义表、树和图等数据结构都是非线性结构。
②数据元素及其关系在计算机内的存储方式，称为数据的存储结构（物理结构）。
数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。
③数据的运算。最常用的检索、插入、删除、更新、排序等。
4.数据的四种基本存储方法:顺序存储、链接存储、索引存储、散列存储
（1）顺序存储：通常借助程序设计语言的数组描述。
（2）链接存储：通常借助于程序语言的指针来描述。
（3）索引存储：索引表由若干索引项组成。关键字是能唯一标识一个元素的一个或多个数据项的组合。
（4）散列存储：该方法的基本思想是：根据元素的关键字直接计算出该元素的存储地址。
5.算法必须满足5个准则：输入，0个或多个数据作为输入；输出，产生一个或多个输出；有穷性，算法执行有限步后结束；确定性，每一条指令的含义都明确；可行性，算法是可行的。
算法与程序的区别：程序必须依赖于计算机程序语言，而一个算法可用自然语言、计算机程序语言、数学语言或约定的符号语言来描述。目前常用的描述算法语言有两类：类Pascal和类C。
6.评价算法的优劣：算法的"正确性"是首先要考虑的。此外，主要考虑如下三点：
①执行算法所耗费的时间，即时间复杂性；
②执行算法所耗费的存储空间，主要是辅助空间，即空间复杂性；
③算法应易于理解、易于编程，易于调试等，即可读性和可操作性。
以上几点最主要的是时间复杂性，时间复杂度常用渐进时间复杂度表示。
7.算法求解问题的输入量称为问题的规模,用一个正整数n表示。
8.常见的时间复杂度按数量级递增排列依次为：常数阶0(1)、对数阶0(log2n)、线性阶0(n)、线性对数阶0(nlog2n)、平方阶0(n2)立方阶0(n3)、…、k次方阶0(n k)、指数阶0(2n)和阶乘阶0(n!)。
9.一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它是问题规模n的函数,它包括存储算法本身所占的存储空间、算法的输入输出数据所占的存储空间和算法在运行过程中临时占用的存储空间。
第二章线性表
1.数据的运算是定义在逻辑结构上的，而运算的具体实现是在存储结构上进行的。
2.只要确定了线性表存储的起始位置，线性表中任意一个元素都可随机存取，所以顺序表是一种随机存取结构。
3.常见的线性表的基本运算:
(1)置空表InitList（L）构造一个空的线性表L。
(2)求表长ListLength（L）求线性表L中的结点个数，即求表长。
(3)GetNode（L，i）取线性表L中的第i个元素。
(4)LocateNode（L，x）在L中查找第一个值为x 的元素，并返回该元素在L中的位置。若L中没有元素的值为x ，则返回0值。
(5)InsertList（L，i，x）在线性表L的第i个元素之前插入一个值为x 的新元素，表L的长度加1。
(6)DeleteList（L，i）删除线性表L的第i个元素，删除后表L的长度减1。
4.顺序存储方法：把线性表的数据元素按逻辑次序依次存放在一组地址连续的存储单元里的方法。
顺序表（Sequential List）：用顺序存储方法存储的线性表称为顺序表。顺序表是一种随机存取结构,顺序表的特点是逻辑上相邻的结点其物理位置亦相邻。
顺序表中结点a i的存储地址: LOC（a i）= LOC（a1）+（i-1）*c 1≤i≤n，
5.顺序表上实现的基本运算：
（1）插入：该算法的平均时间复杂度是O(n)，即在顺序表上进行插入运算，平均要移动一半结点（n/2）。
在第i个位置插入一个结点的移动次数为n-i+1
（2）删除：顺序表上做删除运算，平均要移动表中约一半的结点（n-1）/2，平均时间复杂度也是O(n)。
删除第i个结点移动次数为n-i
6.采用链式存储结构可以避免频繁移动大量元素。一个单链表可由头指针唯一确定，因此单链表可以用头指针的名字来命名。
①生成结点变量的标准函数 p=( ListNode *)malloc(sizeof(ListNode))； //函数malloc分配一个类型为ListNode 的结点变量的空间,并将其首地址放入指针变量p中
②释放结点变量空间的标准函数free(p)；//释放p所指的结点变量空间
③结点分量的访问方法二：p-﹥data和p-﹥next
④指针变量p和结点变量*p的关系:指针变量p的值——结点地址, 结点变量*p的值——结点内容
7.建立单链表:
（1）头插法建表：算法： p=(ListNode *)malloc(sizeof(ListNode));①//生成新结点
p->data=ch;② //将读入的数据放入新结点的数据域中
p->next=head;③ head=p;④
（2）尾插法建表：算法： p=(ListNode *)malloc(sizeof(ListNode)); ①//生成新结点p->data=ch; ② //将读入的数据放入新结点的数据域中
if (head==NULL) head=p;//新结点插入空表
else rear->next=p;③//将新结点插到*r之后
rear=p;④//尾指针指向新表尾
（3）尾插法建带头结点的单链表：
头结点及作用：头结点是在链表的开始结点之前附加一个结点。它具有两个优点:
⒈由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上操作一致,无须进行特殊处理;
⒉无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就统一了。
头结点数据域的阴影表示该部分不存储信息。在有的应用
中可用于存放表长等附加信息。
具体算法：r=head;// 尾指针初值也指向头结点
while((ch=getchar())!='\n'){
s=(ListNode *)malloc(sizeof(ListNode));//生成新结点
s->data=ch; //将读入的数据放入新结点的数据域中
r->next=s;
r=s;}
r->next=NULL;//终端结点的指针域置空，或空表的头结点指针域置空
以上三个算法的时间复杂度均为O(n)。
8.单链表上的查找：（带头结点）
（1）按结点序号查找：序号为0的是头结点。
算法：p=head;j=0;//从头结点开始扫描
while(p->next&&j
p=p->next;
j++;}
if(i==j) return p;//找到了第i个结点
else return NULL;//当i<0或i>0时，找不到第i个结点
时间复杂度：在等概率假设下，平均时间复杂度为：为n/2=O(n)
（2）按结点值查找：
具体算法：ListNode *p=head->next;//从开始结点比较。表非空，p初始值指向开始结点
while(p&&p->data!=key)//直到p为NULL或p->data为key为止
p=p->next;//扫描下一结点
return p;//若p=NULL，则查找失败，否则p指向值为key的结点
时间复杂度为：O(n)
9.插入运算：插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到a i-1与a i之间。
s=(ListNode *)malloc(sizeof(ListNode)); ② s->data=x;③ s->next=p->next;④ p->next=s;⑤
算法的时间主要耗费在查找结点上，故时间复杂度亦为O(n)。
10.删除运算
r=p->next;②//使r指向被删除的结点a i p->next=r->next③;//将a i从链上摘下free(r);④//释放结点a i的空间给存储池
算法的时间复杂度也是O（n）.p指向被删除的前一个结点。
链表上实现的插入和删除运算，无须移动结点，仅需修改指针。
11.单循环链表—在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点即可。判断空链表的条件是head==head->next;
12.仅设尾指针的单循环链表:用尾指针rear表示的单循环链表对开始结点a1和终端结点a n查找时间都是O(1)。而表的操作常常是在表的首尾位置上进行，因此，实用中多采用尾指针表示单循环链表。判断空链表的条件为rear==rear->next;
13.循环链表：循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。若在尾指针表示的单循环链表上实现，则只需修改指针，无须遍历，其执行时间是O(1)。
具体算法：
LinkList Connect(LinkList A,LinkList B) {//假设A，B为非空循环链表的尾指针
LinkList p=A->next;//①保存A表的头结点位置
A->next=B->next->next;//②B表的开始结点链接到A表尾
free(B->next);//③释放B表的头结点
B->next=p;//④
return B;//返回新循环链表的尾指针
循环链表中没有NULL指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p-＞next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。
在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。
14.双向链表:双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior。
①双链表由头指针head惟一确定的。
②带头结点的双链表的某些运算变得方便。
③将头结点和尾结点链接起来，为双（向）循环链表。
15.双向链表的前插和删除本结点操作
①双链表的前插操作
void DInsertBefore(DListNode *p,DataType x){//在带头结点的双链表中，将值为x的新结点插入*p之前，设p≠NULL
DListNode *s=malloc(sizeof(DListNode));//①
s->data=x;//②
s->prior=p->prior;//③
s->next=p;//④
p->prior->next=s;//⑤
p->prior=s;//⑥}
②双链表上删除结点*p自身的操作
void DDeleteNode(DListNode *p)
{//在带头结点的双链表中，删除结点*p，设*p为非终端结点
p->prior->next=p->next;//①
p->next->prior=p->prior;//②
free(p); }//③
与单链表上的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算法的时间复杂度均为O(1)。
16.顺序表和链表比较
时间性能：a、线性表：经常性的查找； b、链式存储结构：经常插入删除操作；
空间性能：a、对数据量大小事先能够知道的用线性表； b、数据量变化较大的用链式存储结构。
存储密度越大，存储空间的利用率越高。显然，顺序表的存储密度是1，链表的存储密度肯定小于1。
第三章栈和队列
1.栈称为后进先出（Last In First Out）的线性表，简称为LIFO表。
栈是运算受限的线性表，顺序栈也是用数组表示的。
进栈操作：进栈时，需要将S-＞top加1，①S-＞top==StackSize-1表示栈满
②"上溢"现象--当栈满时，再做进栈运算产生空间溢出的现象。
退栈操作：退栈时，需将S-＞top减1，①S-＞
top<0表示空栈
②"下溢"现象--当栈空时，做退栈运算产生的
溢出现象。
下溢是正常现象，常用作程序控制转移的条
件。
空栈时栈顶指针不能是0，只能是-1。
两个栈共享同一存储空间: 当程序中同时使用两个栈时，可以将两个栈的栈底分别设在顺序存储空间的两端，让两个栈顶各自向中间延伸。当一个栈中的元素较多而栈使用的空间超过共享空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。
当Top1=Top2-1时，栈满
2.为了克服顺序存储分配固定空间所产生的溢出和空间浪费问题。可采用链式存储结构来存储栈。链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。
链栈中的结点是动态分配的，所以可以不考虑上溢，无须定义
StackFull运算
栈的一个重要应用是实现递归，直接调用自己或间接调用自己的函
数。
3. 队列（Queue）是只允许在一端进行插入，而在另一端进行删除
的运算受限的线性表。允许删除的一端称为队头（Front），允许插
入的一端称为队尾（Rear），当队列中没有元素时称为空队列，队
列亦称作先进先出（First In First Out）的线性表，简称为FIFO
表。队列的顺序存储结构称为顺序队列，顺序队列实际上是一
个受限的线性表。
顺序队列的基本操作
①入队时：将新元素插入rear所指的位置，然后将rear加1。
②出队时：删去front所指的元素，然后将front加1并返回被删元素。
当头尾指针相等时，队列为空。
在非空队列里，头指针始终指向队头元素，而队尾指针始终指向队尾元素的下一位置。而栈顶指针指向栈顶元素。
4.循环队列：为充分利用数组空间，克服上溢，可将数组空间想象为一个环状空间，并称这种环状数组表示的队列为循环队列。
循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为：
①方法一：
if(i+1==QueueSize) i=0;//i表示front或rear
else i++;
②方法二--利用"模运算"
i=(i+1)%QueueSize；
循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件Q.front==Q.rear来判别队列是"空"还是"满"。
解决这个问题的方法至少有三种：
①另设一个标志位以区别队列是空还是满；
②设置一个计数器记录队列中元素的总数（即队列长度）。
③少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队列满即尾指针Q.rear所指的单元始终为空。
5.循环队列的基本运算:
①置队空: Q->front=Q->rear=0;
②判队空: return Q->rear==Q->front;
③判队满: return (Q->rear+1)%QueueSize==Q->front;
④入队Q->data[Q->rear]=x; //新元素插入队尾
Q->rear=(Q->rear+1)%QueueSize;
⑤出队temp=Q->data[Q->front];
Q->front=(Q->front+1)%QueueSize; //循环意义下的头指针加1
return temp;
⑥取队头元素return Q->data[Q->front];
6.队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。
为了简化处理，在队头结点之前附加一个头结点，并设队头指针指向此结点。
链队列的基本运算:（带头结点）
（1）构造空队：Q->rear=Q->front；Q->rear->next=NULL;
（2）判队空：return Q->rear==Q->front;
（3）入队：QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode));//申请新结点
p->data=x; p->next=NULL;
Q->rear->next=p; //*p链到原队尾结点后
Q->rear=p; //队尾指针指向新的尾
（4）出队：当队列长度大于1时，只需修改头结点指针，尾指针不变
s=Q->front->next; Q->front->next=s->next;
x=s->data; free(s); return x;
当队列长度等于1时，不仅要修改头结点指针，还要修改尾指针
s=Q->front->next; Q->front->next=NULL; Q->rear==Q->front;
x=s->data; free(s); return x;
（5）取队头元素：return Q->front->next->data; 因为有头结点，所以用了next
①和链栈类似，无须考虑判队满的运算及上溢。
②在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。
7.用计算机来处理计算算术表达式问题，首先要解决的问题是如何将人们习惯书写的中缀表达式转换成后缀表达式。
第四章多维数组和广义表
1.数组的顺序存储方式:一般采用顺序存储方法表示数组。
（1）行优先顺序 a11,a12,…,a1n,a21,a22,…,a2n,……，a m1,a m2,…，a mn
（2）列优先顺序 a11,a21,…,a m1,a12,a22,…,a m2,……，a1n,a2n,…，a mn
Pascal和C语言是按行优先顺序存储的，而Fortran语言是按列优先顺序存储的。
按行优先顺序存储的二维数组A mn地址计算公式
LOC(a ij)=LOC(a11)+[(i-1)×n+j-1]×d (注：此公式下界为1，如下界为0，则公式变为[i×n+j])
按列优先顺序存储的二维数组A mn地址计算公式
LOC(a ij)=LOC(a11)+[(j-1)×m+i-1]×d(注：此公式下界为1，如下界为0，则公式变为[j×m+i])
按行优先顺序存储的三维数组A mnp地址计算公式
LOC(a ijk)=LOC(a111)+[(i-1)×n×p+(j-1)×p+k-1]×d(注：此公式下界为1，如下界为0，则公式变为[i×n×p+j×p+k])
2.为了节省存储空间，可以对矩阵中有许多值相同或值为零的元素的矩阵，采用压缩存储。
特殊矩阵是指相同值的元素或零元素在矩阵中的分布有一定的规律。常见的有对称矩阵、三角矩阵。
（1）对称矩阵在一个n阶方阵A中，若元素满足下述性质： a ij=a ji0≤i，j≤n-1 称为n阶对称矩阵，它的元素是关于主对角线对称的，所以只需要存储矩阵上三角或下三角元素即可，让两个对称的元素共享一个存储空间。
矩阵元素a ij和数组元素sa【k】之间的关系是
k=i×(i+1)/2+j i≥j0≤k 对称矩阵的地址计算公式：LOC(a ij)=LOC(sa[0])+[I×(I+1)/2+J]×d，其中I=max(i,j)，J=min(i,j) （2）三角矩阵：以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵是指它的下三角(不包括主角线) 中的元素均为常数c或零；下三角矩阵的主对角线上方均为常数c或零。一般情况，三角矩阵的常数c均为零。 三角矩阵的压缩存储：三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n×(n+1)/2个，因此，三角矩阵可压缩存储在一维数组sa[n(n+1)/2+1]中，其中c存放在数组的最后一个元素中。 ①上三角矩阵中a ij和sa[k]之间的对应关系 k=i×(2n-i+1)/2+j-i 当i≤j k=n×(n+1)/2 当i＞j ②下三角矩阵中a ij和sa[k]之间的对应关系 k=i×(i+1)/2+j 当i≥j k=n×(n+1)/2 当i＜j 三角矩阵的压缩存储结构是随机存取结构。 3.稀疏矩阵:设矩阵A mn中有s个非零元素，若s远远小于矩阵元素的总数，则称A为稀疏矩阵。为了节省存储单元，可用压缩存储方法只存储非零元素。由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储非零元素所在的行、列位置，所以可用三元组(i，j，a ij)来确定非零元素。 稀疏矩阵进行压缩存储通常有两类方法：顺序存储(三元组表)和链式存储(十字链表)。稀疏矩阵的压缩存储会失去随机存取功能。 4.广义表是线性表的推广,又称列表。 广义表是n(n≥0)个元素a1，a2，…，a i，…，a n的有限序列。其中a i或者是原子或者是一个广义表。 ①广义表通常用圆括号括起来，用逗号分隔其中的元素。 ②为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。 ③若广义表Ls非空(n≥1)，则a l是LS的表头，其余元素组成的表(a1，a2，…，a n)称为Ls的表尾。 ④广义表具有递归和共享的性质 广义表的深度：一个表展开后所含括号的层数称为广义表的深度。 19.广义表是一种多层次的线性结构，实际上这就是一种树形结构。广义表的两个特殊的基本运算：取表头head(Ls)和取表尾tail(Ls).任何一个非空广义表的表头可以是原子，也可以是子表，而其表尾必定是子表。 head=(a，b)=a，tail(a，b)=(b) 对非空表A和(y)，也可继续分解。 注意:广义表()和(())不同。前者是长度为0的空表，对其不能做求表头和表尾的运算；而后者是长度为l的由空表作元素的广义表，可以分解得到的表头和表尾均是空表()。 广义表是一种有层次的非线性结构，通常采用链式存储结构，每个元素用一个结点表示，结点由3个域构成，其中一个是tag标志位，用来区分结点是原子还是子表，当tag为零时结点是子表，第二个域为slink，用以存放子表的地址；当tag为1时结点是原子，第二个域为data，用以存放元素值。 第五章树和二叉树 1.树的表示法：最常用的是树形图表示法；还有3种嵌套集合、凹形、广义表。 树结构的基本术语 （1）结点的度(Degree) 树中的一个结点拥有的子树数称为该结点的度(Degree)。一棵树的度是指该树中结点的最大度数。 度为零的结点称为叶子(Leaf)或终端结点。度不为零的结点称分支结点或非终端结点。 除根结点之外的分支结点统称为内部结点。根结点又称为开始结点。 （2）①路径（path）若树中存在一个结点序列k1，k2，…，k i，使得k i是k i+1的双亲(1≤i 一个结点的祖先是从根结点到该结点路径上所经过的所有结点，而一个结点的子孙则是以该结点为根的子树中的所有结点。 结点的层数(Level)从根起算：根的层数为1，其余结点的层数等于其双亲结点的层数加1。 双亲在同一层的结点互为堂兄弟。 树中结点的最大层数称为树的高度(Height)或深度(Depth)。 若将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树(OrderedTree)；否则称为无序树(UnoderedTree)。若不特别指明，一般讨论的树都是有序树。 森林(Forest)是m(m≥0)棵互不相交的树的集合。树和森林的概念相近。删去一棵树的根，就得到一个森林；反之，加上一个结点作树根，森林就变为一棵树。 3.二叉树与度数为2的有序树不同：在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。 二叉树的性质： 性质1二叉树第i层上的结点数目最多为2i-1(i≥1)。例如5层的二叉树，第5层上的结点数目最多为24=16 性质2深度为k的二叉树至多有2k-1个结点(k≥1)。例如深度为5的二叉树，至多有25-1=31个结点 性质3在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n o=n2+1。例如一棵深度为4的二叉 树（a），其终端结点数n0为8,度为2的结点树为7，则8=7+1，n o=n2+1成立 （b）其终端结点数n0为6,度为2的结点树为5，则6=5+1，n o=n2+1成立 满二叉树：一棵深度为k且有2k-1个结点的二又树称为满二叉树。满二叉树的特点： （1）每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。 （2）满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。 完全二叉树：若一棵深度为k的二叉树，其前k-1层是一棵满二叉树，而最下面一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。特点： （1）满二叉树是完全二叉树，完全二叉树不一定是满二叉树。 （2）在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。 （3）在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。 性质4 具有n个结点的完全二叉树的深度为。?logn?+1 或?log(n+1)? 例，具有100个结点的完全二叉树的深度为:?lg100?+1=7,26=64 27=128所以?lg100?=6,?lg(100+1)?=7 4.完全二叉树的编号特点：完全二叉树中除最下面一层外，各层都充满了结点。每一层的结点个数恰好是上一层结 点个数的2倍。从一个结点的编号就可推得其双亲，左、右孩子等结点的编号。编号从0开始 ①若i=0，则q i为根结点，无双亲；否则，q i的双亲编号为?(i-1)/2?。 ②若2i+1 ③若2i+2 对于完全二叉树而言，使用顺序存储结构既简单又节省存储空间。但对于一般二叉树来说，采用顺序存储时，为了使用结点在数组中的相对位置来表示结点之间的逻辑关系，就必须增加一些虚结点使其成为完全二叉树的形式。5.链式存储结构: 二叉树的每个结点最多有两个孩子。用链接方式存储二叉树时，每个结点除了存储结点本身的数据外，还应设置两个指针域lchild和rchild，分别指向该结点的左孩子和右孩子。结点的结构为： 二叉链表是一种常用的二叉树存储结构。 建立二叉链表方法：a、按广义表方法，靠近左括号的结点是在左子树上，而逗号右边结点是在右子树上。 b、按完全二叉树的层次顺序建立结点。 具有n个结点的二叉链表中，共有2n个指针域。其中有n-1个用来指示结点的左、右孩子，其余的n+1个为空。二叉树遍历算法中的递归终止条件是二叉树为空。 中序遍历的递归算法定义：(1)遍历左子树； (2)访问根结点； (3)遍历右子树。 先序遍历的递归算法定义：(1)访问根结点； (2)遍历左子树； (3)遍历右子树。 后序遍历得递归算法定义：(1)遍历左子树； (2)遍历右子树； (3)访问根结点。 递归工作栈中包括两项：一项是递归调用的语句编号，另一项则是指向根结点的指针。 已知一棵二叉树的前序和中序遍历序列或中序和后序遍历序列，可唯一确定一棵二叉树。具体方法如下：首先根据前序或后序遍历序列确定二叉树的各子树的的根，然后根据中序遍历序列确定各子树根的左右子树。6.线索二叉树：n个结点的二叉链表必定存在n+1个空指针域，可以利用这些空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针，这种指向前驱和后继结点的指针称为"线索"，这种加上线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。 线索链表的结点结构： 其中:ltag和rtag是增加的两个标志域，用来区分结点的左、右指针 域是指向其左、右孩子的指针，还是指向其前趋或后继的线索。 图中的实线表示指针，虚线表示线索。线索二叉树中，一个结点是叶结点的充要条件为：左、右标志均是1。 7.二叉树的线索化:把对一棵二叉线索链表结构中所有结点的空指针域按照某种遍历次序加线索的过程称为线索化。 和中序遍历算法一样，递归过程中对每结点仅做一次访问。因此对于n个结点的二叉树，线索化的算法时间复杂度为O(n)。 8.树、森林到二叉树的转换：树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。 将树转换成二叉树：①在所有兄弟结点之间加一道连线；②对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。 将一个森林转换为二叉树: 将森林中的每棵树转化成二叉树，然后再将二叉树的根节点看做兄弟连在一起，形成一棵二叉树 9.二叉树到树、森林的转换: 方式是：若二叉树中结点x是双亲y的左孩子，则把x的 右孩子，右孩子的右孩子，…，都与y用连线连起来，最后去掉所有双亲到右孩子的连线。 10.树的存储结构： 1.双亲表示法：双亲链表表示法利用树中每个结点的双亲唯一性， 在存储结点信息的同时，为每个结点附设一个指向其双亲的指针 parent，惟一地表示任何-棵树。 （1）双亲链表表示法的实现 分析：E和F所在结点的双亲域是1，它们的双亲结点在向量中的位 置是1，即B是它们的双亲。 注意：①根无双亲，其parent域为-1。 ②双亲链表表示法中指针parent向上链接，适合求指定结 点的双亲或祖先(包括根)；求指定结点的孩子或其它后代时，可能 要遍历整个数组。 2.孩子链表法：孩子链表表示法是为树中每个结点设置一个孩子链 表，并将这些结点及相应的孩子链表的头指针存放在一个向量中。 注意：①孩子结点的数据域仅存放了它们在向量空间的序号。 ②与双亲链表表示法相反，孩子链表表示便于实现涉及孩子及其子孙的运算，但不便于实现与双亲有关的运算。 ③将双亲链表表示法和孩子链表表示法结合起来，可形成双亲孩子链表表示法。 3.孩子兄弟表示法：在存储结点信息的同时，附加两个分别指向该结点最左孩子和右邻兄弟的指针域，即可得树的 孩子兄弟链表表示。 注意： 这种存储结构的最大优点是：它和二叉树的二叉链 表表示完全一样。可利用二叉树的算法来实现对树的操 作。 11.树的遍历： 一般都只给出两种次序遍历树的方法：前序(先根次序)遍历和后序(后根次序)遍历。 ①前序遍历一棵树等价于前序遍历该树对应的二叉树 ②后序遍历一棵树等价于中序遍历该树对应的二叉树。 对下面(a)图中所示的森林进行前序遍历和后序遍历，则得到该森林的前序序列和后序序列分别为ABCDEFIGJH和BDCAIFJGHE。而(b)图所示二叉树的前序序列和中序序列也分别为ABCDEFIGJH和BDCAIFJGHE。 ①前序遍历森林等同于前序遍历该森林对应的二叉树 ②后序遍历森林等同于中序遍历该森林对应的二叉树 12.从根结点到某结点之间的路径长度与该结点上权的乘积称为该结点的带权路径长度，树种所有叶子结点的带权路径长度之和称为树的带权路径长度。带权路径长度WPL最小的二叉树称为哈夫曼树或最优二叉树。 哈夫曼树不一定是二叉树。 哈夫曼树又称为最优树，是一类带权路径长度最短的树。完全二叉树就是这种路径长度最短的二叉树。 ①只有叶结点上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。 ②最优二叉树中，权越大的叶子离根越近。③最优二叉树的形态不唯一，WPL最小。 13.哈夫曼算法: 基本思想是：(1)根据给定的n个权值w l，w2，…，w n构成n棵二叉树的森林F={T1，T2，…，T n}，其中每棵二叉树T i中都只有一个权值为w i的根结点，其左右子树均空。 (2)在森林F中选出两棵根结点权值最小的树(当这样的树不止两棵树时，可以从中任选两棵)，将这两棵树合并成一棵新树，为了保证新树仍是二叉树，需要增加一个新结点作为新树的根，并将所选的两棵树的根分别作为新根的左右孩子(谁左，谁右无关紧要)，将这两个孩子的权值之和作为新树根的权值。 (3)对新的森林F重复(2)，直到森林F中只剩下一棵树为止。这棵树便是哈夫曼树。 注意：①初始森林中的n棵二叉树，每棵树有一个孤立的结点，它们既是根，又是叶子 ② n个叶子的哈夫曼树要经过n-1次合并，产生n-1个新结点。最终求得的哈夫曼树中共有2n-1个结点。 ③哈夫曼树是严格的二叉树，没有度数为1的分支结点。 14.哈夫曼编码： 数据压缩过程称为编码,反之，解压缩的过程称为解码。 设计一种长短不等的编码，则必须保证任一字符的编码都不是另一个字符编码的前缀，这种编码称为前缀编码。 可以利用二叉树来设计二进制的前缀编码，其左分支表示字符0，右分支表示字符1，则以根结点到叶结点路径上的分支字符组成的串作为该叶节点的字符编码。 因此设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作为权构造一棵哈夫曼树，由哈夫曼树求得的编码就是哈夫曼编码。 译码过程是从树根结点出发，逐个读入电文中的二进制码。 第六章图 1.图G由两个集合构成，顶点集合和边集合，也可以图G只有顶点而没有边。用尖括号表示图的有向边 在无向图中，称v i和v j相邻接，在有向图中称顶点v i邻接到v j，顶点v j邻接于v i 在无向图中，n的取值范围是0-n(n-1)/2，将具有n(n-1)/2条边的无向图称为无向完全图。 在有向图中，n的取值范围是0-n(n-1)，将具有n(n-1)条边的有向图称为有向完全图。 无向图中，顶点的度定义为以该顶点为一个端点的边的数目，有向图的度等于出度和入度之和。 在无向图中，任意两顶点都有路径，则称两顶点连通。若图G中的任意两个顶点都连通，称G为连通图。无向图的极大连通子图称为连通分量，显然，任何连通图的连通分量只有一个，即其自身，而非连通的无向图有多个连通分量。 在有向图中，图G中任意两顶点连通，称为强连通图，极大连通子图称为强连通分量。 若在一个图的每条边上标上某种数值，该数值称为该边的权。边上带权的图称为带权图，带权的连通图称为网络。 2.图的存储结构：邻接矩阵和邻接表表示法。图的顶点编号从0开始。 邻接矩阵表示法： 无向图的邻接矩阵是按主对角线对称的。若G是带权图，只要把1换成相应边上的权值即可，0的位置上可以不动或将其换成无穷大表示。无向图的邻接矩阵表示法可以仅存储主对角线以下的元素，时间复杂度为O(n2) 邻接表表示法：邻接表是图的一种链式存储结构。将无向图的邻接表称为边表，将有向图的邻接表称为出边表，将邻接表的表头向量称为顶点表。若无向图有n个顶点和e条边，则它的邻接表共有n个头结点和2e个表结点。 建立邻接表的时间复杂度是O(n+e)。图的邻接表表示不是唯一的,这是因为在每个顶点的邻接表中，各边结点的链接次序可以是任意的，其具体链接次序与边的输入次序和生成算法有关。 3.图的遍历：遍历图的算法是求解图的连通性、图的拓扑排序等算法的基础。 图的遍历常用的是深度优先搜索遍历和广度优先搜索遍历两种方法。 深度优先搜索遍历(DFS)类似于前序(先根)遍历。按访问顶点的先后次序得到的顶点序列称为图的深度优先遍历序列，或简称为DFS序列。共需要搜索n2个矩阵元素，时间复杂度为邻接矩阵O(n2)或邻接表O(n+e)。 广度优先搜索遍历(BFS)类似于树的按层次遍历，先被访问的顶点，其邻接点也先被访问，就是先进先出。 时间复杂度为邻接矩阵O(n2)或邻接表O(n+e)，空间复杂度都是O(n)。 4.生成树是连通图的包含图中所有顶点的一个极小连通子图，一个图的极小连通子图恰为一个无回路的连通图，也就是说，若图中任意添加一条边，就会出现回路，若去掉任意一条边，都会使之成为非连通图。 因此，一个具有n个顶点的生成树有且仅有n-1条边，但有n-1条边的图不一定是生成树，同一个图可以有不同的生成树。 生成树定义为：若从图的某顶点出发，可以系统的访问到图的所有顶点，则遍历时经过的边和图的所有顶点所构成的子图，称为该图的生成树。 最小生成树：图的生成树不唯一，把权值最小的生成树称为最小生成树（MST）。 构造最小生成树的算法：普里姆Prim算法的时间复杂度为O（n2）与网中边数无关适于稠密图。 克鲁斯卡尔Kruskal算法的时间复杂度为O（eloge），主要取决于边数，较适合于稀疏图。 5.最短路径：Dijkstra迪杰斯特拉算法，提出了按路径长度递增的顺序产生诸顶点的最短路径算法。 拓扑排序：子工程称为活动，顶点代表活动，有向边代表活动的先后关系。这样的有向无环图DAG称为顶点活动网，简称为AOV网。将有向无环图G中所有顶点排成一个线性序列，若 检测的方法是：对有向图构造其顶点的拓扑序列，若网中所有顶点都在他的拓扑序列中，则AOV网必定不存在环。 AOV网的拓扑序列不是唯一的。 拓扑排序的描述思想：a、在有向图中选一个没有前趋(入度为零)的顶点，且输出之。b、从有向图中删除该顶点及其与该顶点有关的所有边。c、重复上述步骤，直到全部顶点都已输出或图中剩余的顶点中没有前趋顶点为止。 d、输出剩余的无前趋结点。 拓扑排序实际上是对邻接表表示的图G进行遍历的过程。时间复杂度是O(n+e)。 第七章排序 1.如果待排序文件中存在多个关键字相同的记录，经过排序后，这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；反之，则是不稳定的。 排序在内存中处理，不涉及数据的内外存交换，称为内部排序，反之为外部排序。内部排序又分为五类：插入、选择、交换、归并和分配排序。 在排序过程中需进行两种操作：比较两个关键字的大小、改变指向记录的指针或移动记录本身，而待排序记录的存储形式一般有三种：顺序结构、链式结构和辅助表。 评价排序算法的标准：执行算法需要的时间，以及算法所需要的附加空间。还有算法本身的复杂度。 排序的时间开销，一般情况下可用算法中关键字的比较次数和记录的移动次数来衡量。 2.插入排序：每次将一个待排序记录按其关键字大小插入到前面已排好序的文件中的适当位置。 直接插入排序：每次从无序区取出第一个元素把它插入到有序区的适当位置，使之成为新的有序区，经过n-1次插入后完成。算法中R[0]作用：保存R[i]副本，监视数组下标变量j是否越界。所以R[0]称为哨兵。每次的比较是从后往前比较的。 时间复杂度最好是O(n)，最坏是O(n2)，所以是O(n2)。空间复杂度O(1)，所以是就地排序。是稳定的算法。 初始情况是有序区中只有一个元素R[1]，无序区中R[2..n]。 希尔排序(缩小增量排序)：算法不稳定。记录的总比较次数和总移动次数都要比直接插入排序少得多，特别是当n越大越明显。希尔排序的时间依赖于增量序列，最后一个增量必须是1，尽量避免增量互为倍数的情况。 3.交换排序：两两比较待排序记录的关键字，如果发现两个记录的次序相反时即进行交换，直到没有反序位置。 冒泡排序(起泡排序)：通过相邻元素之间比较和交换，使较小移向顶部，从后往前两两比较。 时间复杂度最好是O(n)，最坏是O(n2)，所以是O(n2)。是稳定的排序算法。 快速排序(划分交换排序)：是冒泡排序的改进。比较和交换从两端向中间进行。 一趟快速排序步骤：设两个指针i和j，初值分别为low和high，基准为x=R[i]，首先从j位置开始向前搜索第一个小于基准x.key的记录存入i所指位置上，i自增1，然后从i所指位置向后搜索找到第一个大于基准x.key的记录存入j所指位置上，j自减1，重复直至i=j为止。 快速排序是不稳定的。有非常好的时间复杂度，优于其他各种排序算法，O(nlog2n)，但是当记录关键字有序或基本有序时复杂度反而大了使之转变成冒泡排序为O(n2)。快速排序是递归的，需要一个栈空间，空间复杂度O(log2n)。 4.选择排序：每一趟在待排序的记录中选出关键字最小的记录，依次存放在已排序好的记录序列的最后。 直接选择排序：初始时，R[1..n]为无序区，R[1]为空；第一趟是在R[1..n]中选出最小的记录与R[1]交换，R[1]为有序区；第二趟是在R[2..n]中选出最小的记录与R[2]交换，R[1..2]为有序区。时间复杂度O(n2)，是不稳定的。初始情况是有序区为空，无序区中R[1..n]，第一趟从R[1..n]选择最小记录与R[1]交换。 堆排序：是对直接选择排序的改进，是一种树形选择排序。基本思想：在排序过程中，将记录数组R[1..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大或最小记录。 每一趟排序：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将他和无序区中最后一个记录交换。堆排序是一个不断建堆的过程。构造堆的过程：R[1]作为二叉树的根，R[2..n]依次逐层从左到右顺序排列，构成一棵完全二叉树，任意结点R[i]的左孩子是R[2i]，右孩子是R[2i+1]，双亲是R?i/2?，此称为筛选法。从?n/2?开始。每一趟的时间复杂度是O(log2n)，整个堆排序的时间复杂度是O(nlog2n)。 5.归并排序：首先将待排序文件看成n个长度为1的有序子文件，把这些子文件两两归并，得到?n/2?个长度为2的有序子文件，然后再将他们两两归并，如此反复，直到得到一个长度为n的有序文件，此称为二路归并排序。 每一趟归并排序的时间复杂度是O(n)，所以总的时间复杂度是O(nlog2n)。 6.分配排序：前面方法都至少需要进行?nlogn?次比较，而分配排序将时间复杂度降为O(n)。 箱排序(桶排序)： 基数排序：是对箱排序的改进和推广。箱排序只适用于关键字取值范围较小的情况，否则所需箱子数目太多。 每个分量可能取值的个数rd称为基数，基数的选择和关键字的分解因关键字的类型而异。d趟箱排序。 基数排序中，没有进行关键字的比较和记录的移动，而只是扫描链表和进行指针赋值，所以排序的时间主要用在修改指针上，初始化链表时间为O(n)。 7.内部排序方法分析比较：本章除基数排序外，都是在顺序表上实现的。 时间复杂度空间复杂度稳定性 插入直接插入O(n2) O(1)稳定希尔排序O(nlog2n)或O(n1.25) O(1)不稳定 交换冒泡排序O(n2) O(1)稳定快速排序O(nlog2n) O(log2n) 不稳定 选择直接选择O(n2) O(1) 不稳定堆排序O(nlog2n) O(1) 不稳定 归并排序归并排序O(nlog2n) O(n) 稳定 分配排序基数排序O(d*(rd+n))rd是基数， d是关键字位数.n是元素个数 O(rd+n) 稳定箱排序 选取排序方法时需要考虑的主要因素：a、待排序的记录个数，b、记录本身的大小和存储结构，c、关键字的分布情况，d、对排序稳定性的要求，e、时间和空间复杂度要等 排序方法的选取： a、若待排序的一组记录数目n较小(如n≤50)时，可采用插入排序或选择排序； b、n较大时，则应采用快速排序、堆排序或归并排序； c、若待排序记录按关键字基本有序时，则宜选用直接插入排序或冒泡排序； d、当n很大，而且关键字位数较少时，采用链式基数排序较好； e、关键字比较次数与记录的初始排列顺序无关的排序方法是选择排序。 一般的排序方法都可以在顺序结构上实现，当记录本身信息量较大时，可采用链式存储结构。 插入、归并、基数排序易于在链表上实现；快速排序和堆排序可以提取关键字建立索引表，然后对索引表进行排序。 第八章：查找 1.查找又称检索，是数据处理中经常使用的一种重要运算。查找也分为内查找和外查找。 运算查找的主要操作是关键字的比较，因此把查找过程中的平均比较次数(也称为平均查找长度)作为衡量算法效率优劣的标准。 2.顺序表的查找：顺序查找和二分查找 顺序查找又称线性查找：查找成功的平均查找长度(n+1)/2，即约为表长的一半。 如果查找成功和不成功机会相等，那么平均查找长度3(n+1)/4。 优点是简单，对表的结构无任何要求，无论是顺序存储和链式存储、无论是否有序，都同样适用，缺点是效率低。对于有序表来说，该算法的平均查找长度是(n+1)/2。 二分查找(折半查找)：要求查找对象的线性表必须是顺序存储结构的有序表。查找过程是递归的。 树中每个子树的根节点对应当前查找区间的中位记录R[mid]，它的左子树和右子树分别对应区间的左子表和右子表，通常将此树称为二叉判定树。由于二分查找是在有序表上进行的，所以其对应的判定树必定是一棵二叉排序树。 二叉判定树一定是二叉排序树，二叉排序树又称为二叉查找树。 从判定树上可见，关键字比较的次数恰好为该结点在树中的层数。因此，二分查找算法在查找成功时进行关键字比较的次数最多不超过判定树的深度。查找成功时的平均查找长度 (n+1)/nlog2(n+1)-1，当n很大时，可近似用log2(n+1)-1表示。因为判定树度数小于2的结点只可能在最下面的两层，所以n个结点的判定树的深度和n个结点的完全二叉树的深度相同，即为?log2(n+1)?。可见，二分查找的最坏性能和平均性能相当接近。 二叉判定树的输出：每次以?(low+high)/2?为根建树。 3.索引顺序查找(分块查找)：是一种介于顺序查找和二分查找之间的查找方法。要求分块有序，前一块的最大关键字小于后一块的最小关键字，抽取各块中的最大关键字及其起始位置构成索引表。 分块查找的基本思想是：首先查找索引表，可用二分查找或顺序查找，然后在确定的块中进行顺序查找。 平均查找长度：二分查找log(n/s+1)+s/2，顺序查找(s2+2s+n)/2s。 4.三种查找方法比较 顺序查找缺点是n较大时，查找成功约为(n+1)/2，失败需要比较n+1次。 二分查找成功时约为log2(n+1)-1，但是他要求表以顺序存储且按关键字有序，适用于表不易变动且又经常查找的情况。 分块查找的优点是，在表中插入或删除一个记录时，只要找到该记录所属的块，就可以在该块内进行插入或删除操作，因为块内记录是无序的，所以插入或删除比较容易，无需移动大量记录。主要缺点是需要增加一个辅助数组的存储空间和将初始表块排序的运算，它也不适用于链式存储结构。 上述三种查找的时间复杂度分别是O(n)、O(log2n)和O(n的平方根) 5.二叉排序树(二叉查找树)：或者是一棵空树，或者具有下面性质：a、若右子树非空，则右子树上所有结点的值均大于根节点的值。b、若左子树非空，则左子树上所有结点的值均小于根节点的值。c、左右子树本身又各是一棵二叉排序树。 由此可得，按中序遍历二叉排序树所得到的遍历序列是一个递增有序序列。 同样一组关键字序列，由于其输入顺序不同，所得到的二叉排序树也有所不同，含有n个结点的二叉排序树不是唯一的。构造二叉排序树的真正目的并不是为了排序，而是为了更好地查找，又称为二叉查找树。 二叉排序树的查找与给定值的比较次数不会超过树的深度。若二叉排序树是一颗理想的平衡树或接近理想的平衡树，则时间复杂度为O(log2n)，若退化为一棵单支树，则时间复杂度为O(n)。 二叉排序树的删除：被删除结点为p，其父结点为f。具体操作为： a、若p是叶子结点，直接删除p； b、若p只有一棵子树(左子树或右子树)，直接用p的左子树(或右子树)取代p的位置而成为f的一棵子树。即p 是左子树则p的子树变为f的左子树； c、若p既有左子树又有右子树，任选一种方法： (1)、用p的直接前驱结点代替p，即从p的左子树中选择值最大的结点s放在p的位置(用结点s的内容替换结点p内容)，然后删除结点s。s是p的左子树中最右边的结点且没有右子树； (2)、用p的直接后继结点代替p，即从p的右子树中选择值最小的结点s放在p的位置(用结点s的内容替换结点p内容)，然后删除结点s。s是p的右子树中最左边的结点且没有左子树。 在二叉排序树上实现插入和查找操作的平均时间复杂度为O(log2n)，但在最坏得情况下，会变成O(n)。 平衡二叉树：既能满足BST性质又能保证二叉排序树的深度在任何情况下均为O(log2n)。 6.B树是一种平衡的多路查找树。 一棵m(m≥3)阶的B树，或为空树，或为满足下列性质的m叉树 a、每个结点至少包含下列信息域； b、每个结点至多有m棵子树； c、若树为非空，则根结点至少有1个关键字，至多有m-1个关键字。因此，若根结点不是叶子，则它至少有两颗子树。 d、每个非根结点中所含的关键字个数满足：?m/2?-1≤n≤m-1，因为每个内部结点的度数正好是关键字总数加1，所以处根结点之外的所有非终端结点至少有?m/2?棵子树，至多有m棵子树。 在B树上插入和删除元素的运算比较复杂，它要求进行运算后的结点中关键字个数≥?m/2?-1， 在B树进行查找包括两种基本操作：在B树中查找结点、在结点中查找关键字。 7.B+树是一种文件组织的B树的变形树，通常有两个头指针root和sqt，前者指向根结点，后者指向关键字最小的叶子结点。因此可对B+树进行两种查找运算：一种是从最小关键字起进行顺序查找，一种是从根结点开始进行随机查找。 8.散列表查找是通过对记录的关键字值进行某种运算直接求出记录的地址，是一种由关键字到地址的直接转换方法。散列存储中使用的函数称为散列函数或哈希函数，散列地址或哈希地址，散列表或哈希表。 具有相同散列地址的关键字称为同义词。冲突的频度除了与散列函数H相关外，还与散列表的填满程度相关。 如何尽量避免冲突和冲突发生后如何解决冲突，就成了散列存储的两个关键问题。 散列函数的目标是使散列地址尽可能均匀的分布在散列空间上，同时使计算尽可能简单。 直接地址法：计算简单，并且没有冲突。适合于关键字的分布基本连续的情况。 数字分析法：从中提取数字分布比较均匀的若干位作为散列地址。 除余数法：p最好取小于或等于表长m的最大素数。这是一种最简单也最常用的方法。 平方取中法：折叠法：把关键字分割成位数相同的几段，分为移位叠加和边界叠加。 9.处理冲突的方法：开放定址法和拉链法。 开放定址法：线性探查法、二次探查法和双重散列法(几种方法中最好的方法)。 二次探查法：d+12，d-12，d+22，d-22 拉链法：存储结构是链表时常用。把具有相同散列地址的关键字值放在同一个单链表中，称为同义词链表。有m个散列地址就有m个链表。用拉链法处理冲突比开放定址法多占用一些存储空间用作链表指针，但它可以减少在插入和查找过程中关键字的平均比较次数(平均查找长度)。 10.查找不成功时，顺序查找和二分查找所需要进行的关键字仅取决于表长，而散列表查找所需要进行的比较次数和待查结点有关。 散列表查找，计算查找成功的平均查找长度时，除数是结点的个数，而在计算查找不成功的平均查找长度时，除数却是表长。 开放定址法：装填因子α≤1，实用中一般取0.65-0.9之间的某个值。 拉链法：α可以大于1，但一般取α≤1。 判断： 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）个节点 全国2005年10月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.若要描述数据处理的变化过程，其正确的次序应为( ) A.处理要求、基本运算和运算、算法 B.处理要求、算法、基本运算和运算 C.基本运算和运算、处理要求、算法 D.算法、处理要求、基本运算和运算 2.从运算类型角度考虑，属于引用型的运算是( ) A.插入、删除 B.删除、修改 C.查找、读取 D.查找、删除 3.若在长度为n的顺序表中插入一个结点，则其结点的移动次数( ) A.最少为0，最多为n B.最少为1，最多为n C.最少为0，最多为n+1 D.最少为1，最多为n+1 4.在一个单链表中，若p所指结点是q所指结点的前驱结点，则在结点p、q之间插入结点s的正确操作是( ) A.s->next=q；p->next=s->next B.p->next=q；p->next=s C.s->next=q->next；p->next=s D.s->next=q->next；p->next=s->next 5.若有一串数字5、6、7、8入栈，则其不可能 ．．．的输出序列为( ) A.5、6、7、8 B.8、7、6、5 C.8、7、5、6 D.5、6、8、7 6.FORTRAN语言对数组元素的存放方式通常采用( ) A.按行为主的存储结构 B.按列为主的存储结构 C.按行或列为主的存储结构 D.按行和列为主的存储结构 7.树是n个结点的有穷集合，( ) A.树的结点个数可以为0，此时称该树为空树 B.树至少含有一个根结点，不能为空 C.树至少含有一个根结点和一个叶子结点 D.树至少含有一个根结点和两个叶子结点 8.深度为k的二叉树至多有( ) A.2k个叶子 B.2k-1个叶子 C.2k-1个叶子 D.2k-1-1个叶子 9.具有10个顶点的有向完全图应具有( ) 浙02142# 数据结构导论试题第 1 页（共 4 页） 我本科在燕山大学，作为河北省的一个旅游城市，旅游季节超级多以外，真的没有开拓我太多眼界，但是鉴于老师负责而且很专业，教会了我很多知识。但是我们专业，在一二线城市，机会多，企业多，就业及科研合作机会也多，所以，选择学校，一定要先看城市，再选学校。对我而言，研究生考进北科大，也是一项很大的挑战和提升。下面是我整理的一些考研经验与心得，希望能助你一臂之力，早日考进自己理想的学校。 数学： 对于计算机科技而言，数学很重要。我们专业是以数学逻辑为基础的，数据结构是建立在数学基础之上的一门学科。可以说，数学是我们的工具书。数学真的很重要。要从3月份就开始复习，这样后面会比较轻松。建议先从基础教材着手，看完教材，要做课后练习题，测试自己是否掌握了本章节的知识。这样，高数和线性代数的课本过一遍，需要2-3个月的时间。第二阶段就要做大量的练习了，研数盒子，这个公众号的特点是习题为主，数学一定要多加练习，这个公众号就是以练习各种习题为主，每周都会发各种作业和讲解，研数盒子有一套教材叫做研数800题非常好。做的过程中，对错题要着重注意并记录一下，建立一个错题本，然后针对没做对的题，分析归纳，然后回归到课本上，查到对应章节，重新温习。这套练习要刷个3遍左右，每一遍你都会有新的认识和体会，个人觉得效果会比做3套不同的题更有效。3遍下来，精读的效果就很明显了，这就是“温故知新”的道理。10月开始，真题要开始做起来了，向上面一样，建立错题本，这个本会是你考研备考后期独一无二的宝典。总之，数学真的很重要，要自始至终坚持到底，除了反复多加练习，还要多思考。 英语： 阅读理解很重要，备考需要坚持每天2篇阅读，开始的时候要精度，好好分析一下句式，掌握好主谓宾从，整段意思也就很容易理解了。学会分析句式以后，后续就会容易很多。再就是单词部分，买一本基础的单词书<<一本单词>>，早晨背完，晚上回忆，过电影一样的，重要的单词，要熟悉到知道在哪个位置，上面的解释是什么。没事看看，不想看书的时候看看，随手看看，遍数多了，自然会记住了，或者每个考生都有自己独特的单词记忆方法，请大家用尽十八般武艺，只有一个目的——背好单词，大家也可以关注蛋核英语公众号。再说说作文，作文呢，一定要积累名言警句，有华丽的辞藻才能表达出自己的观点对不对？作文 2016年4月高等教育自学考试全国统一命题考试 数据结构导论试卷 (课程代码 02142) 本试卷共6页。满分l00分，考试时间l50分钟。 考生答题注意事项： 1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。3．第二部分为非选择题。必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。4．合理安排答题空间，超出答题区域无效。 第一部分选择题(共30分) 一、单项选择题(本大题共l5小题。每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”的相应代码涂黑。错涂、多涂或未涂均无分。 1．一个公司的组织机构是1名公司经理领导若于名部门负责人、每个部门负责人领导若干名部门员工，则适合于描述该公司组织机构的逻辑结构是 A．线性表 B．队列 C．树 D．图 2．计算n!(整数n≥0)的递归算法是：int Factorial(int n){if(n= =o)return l；else return n*Factorial(n--1)；}其时闯复杂度为 A．0(n) B．0(log2n) C．O(n0) D．O(n2) 3．将一个由指针q指向的结点插在单链表中由指针P所指向的结点之后的操作是 A．p=q； B．p--：>next=q； C．q一>next=p--：>next；p-->next=q； D．p一>next—q；q-->next—p--：>next； 4. 设初始栈为空，s表示人栈操作，x表示出栈操作，则合法的操作序列是 A．sxxssxxs B．ssxsxxxs C．ssxxxssx D．sssxxxsx 5．将递归形式描述的算法改写为功能等价的非递归形式描述的算法，通常应设置的辅助结构是 A．顺序表 B．单链表C．栈 D．队列 6．设长度为n的队列用单循环链表表示(假设表尾结点为当前队列的队尾元素)，若只设头指针，则入队操作、出队操作的时间复杂度分别为 A．O(n)、O(1) B．O(1)、O(1) C．O(1)、O(n) D．0(n)、0(n) 7．若采用顺序存储(一维数组)结构存储一棵如题7图所示的二叉树，根结点1的下标为l，剥结点4的下标为 A．4 B．5 C．6 D．7 8．按层序(自顶向下、从左到右)遍历二叉树时需借助队列作辅助结构。对高度为3的满二叉树进行层序遍历时，队列中所出现的元素个数最多是 郝斌数据结构自学笔记 --知识点+程序源代码 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) { | 全国2011年1月自学考试数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.在顺序表中查找第i个元素，时间效率最高的算法的时间复杂度为( ) A.O(1) B.O(n) C.O(log2n) D.O(n) 2.树形结构中，度为0的结点称为( ) A.树根 B.叶子 C.路径 D.二叉树 3.已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={ 数据结构复习笔记 作者: 网络转载发布日期: 无 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。如整数这个集合中，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)。 时间复杂度的分析计算请看书本上的例子，然后我们通过做练习加以领会和巩固。 数据结构习题一 -------------------------------------------------------------------------------- 数据结构导论复习 第一章概论 1．数据：凡能被计算机存储、加工处理的对象。 2．数据元素：是数据的基本单位，在程序中作为一个整体而加以考虑和处理 3．数据项：又叫字段或域，它是数据的不可分割的最小标识单位。 4．逻辑结构需要注意的几点： ①逻辑结构与数据元素本身的内容无关 ②逻辑结构与数据元素相对位置无关 ③逻辑结构与所有结点的个数无关 5．数据元素间逻辑关系是指数据元素之间的关联方式或称“领接关系”。 6．四类基本逻辑结构（集合、线性结构、树形结构和图形结构）的不同特点？ 答：集合中任何两个结点之间都没有逻辑关系，组织形式松散； 线性结构中结点按逻辑关系依次排列形成一条“锁链”； 树形结构具有分支、层次特性，其形态有点像自然界中的树； 图状结构最复杂，其中的各个结点按逻辑关系互相缠绕，任何两个结点都可以领接。 7．运算是在逻辑结构层次上对处理功能的抽象 8．基本运算的含义？ 答：假如是S上的一些运算的集合，是的一个子集，使得中每一运算都可以“归约”为中的一个或多个运算，而中任一运算不可归约为别的运算，则称中运算为基本运算 9．数据结构是指由一个逻辑结构S和S上的一个基本运算集构成的整体（S ，）。 10．数据结构涉及数据表示和数据处理两个方面 11．存储结构的含义和四种基本存储方式的基本思想？ 答：存储结构是指按照逻辑结构的要求建立的数据的机内表示称为存储结构。 一个存储结构应包含三个主要的部分：存储结点、机内表示和附加设施。 存储结构包括四种存储方式，顺序存储方式、链式存储方式、索引存储方式和散列存储方式。 12．运算实现与运算的联系与区别？ 答：运算指的是数据在逻辑结构S上的某种操作，运算只描述处理功能，不包括处理步骤和方法；而运算实现是指一个完成该运算功能的程序，运算实现的核心是处理步骤的规定，即算法设计。 13．算法的概念和分类？ 答：算法是指规定了求解给定类型问题所需的所有“处理步骤”及其执行顺序，使得给定类型的任何问题能在有限时间内被 ※特别章外部排序（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++一样，都是讲一门语言。但学习之后，发现事实并不是这样，在数据结构的学习中，有线性表，有队，有栈，有树，有图等等。这些看起来没有关系，其实之间有着千丝万缕的联系。线性表是其中最简单的，所以在前几章学习，后面依次逐章变难，学起来也很吃力。 《数据结构与算法》以基本数据结构和算法设计策略为知识单元，系统地介绍了数据结构的知识与应用、计算机算法的设计与分析方法，主要内容包括线性表、树、图和广义表、算法设计策略以及查找与排序算法等。 线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。线性表具有如下的结构特点：均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数据类型和长度。有序性：各数据元素在线性表中的位置只取决于它们的序号，数据元素之前的相对位置是线性的，即存在唯一的“第一个“和“最后一个”的数据元素，除了第一个和最后一个外，其它元素前面均只有一个数据元素直接前驱和后面均只有一个数据元素（直接后继）。在实现线性表数据元素的存储方面，一般可用顺序存储结构和链式存储结构两种方法。链式存储结构将在本网站线性链表中介绍，本章主要介绍用数组实现线性表数据元素的顺序存储及其应用。另外栈、队列和串也是线性表的特殊情况，又称为受限的线性结构。 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生 全国2014年4月高等教育自学考试 数据结构导论试题 课程代码：02142 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1.答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2.每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1.下列几种算法时间复杂度中，最小的是( A ) A.O(log2n) B.O(n) C.O(n2) D.O(1) 2.数据的存储方式中除了顺序存储方式和链式存储方式之外，还有( D ) A.索引存储方式和树形存储方式 B.线性存储方式和散列存储方式 C.线性存储方式和索引存储方式 D.索引存储方式和散列存储方式 3.表长为n的顺序表中做删除运算的平均时间复杂度为( C ) A.O(1) B.O(log2n) C.O(n) D.O(n2) 4.顺序表中定位算法(查找值为x的结点序号最小值)的平均时间复杂度为( C ) A.O(1) B.O(log2n) C.O(n) D.O(n2) 5.元素的进栈次序为A，B，C，D，E，出栈的第一个元素为E，则第四个出栈的元素为( C ) A.D B.C C.B D.A 6.带头结点的链队列中，队列头和队列尾指针分别为front和rear，则判断队列空的条件为( A ) A.front==rear B.front!=NULL C.rear!==NULL D.front==NULL 7.深度为5的二叉树，结点个数最多为( A ) 全国20XX 年10月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.在表长为n 的顺序表上做插入运算，平均要移动的结点数为（ C ） A.n/4 B.n/3 C.n/2 D.n 2.顺序表中有19个元素，第一个元素的地址为200，且每个元素占一个字节，则第14个元素的存储地址为（ B ）b+(i-1)l A.212 B.213 C.214 D.215 3.由顶点V 1，V 2，V 3构成的图的邻接矩阵为???? ??????010100110，则该图中顶点V 1的出度为（ C ） A.0 B.1 C.2 D.3 4.元素的进栈次序为A ，B ，C ，D ，E ，则退栈中不可能．．． 的序列是（ C ） A.A ，B ，C ，D ，E B.B ，C ，D ，E ，A C.E ，A ，B ，C ，D D.E ，D ，C ，B ，A 5.由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（C ） A.23 B.37 C.44 D.46 6.在已知尾指针的单循环链表中，插入一个新结点使之成为首结点，其算法的时间复杂度为（ A ） A.O （1） B.O （log 2n ） C.O （n ） D.O (n 2) 7.已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分查找值为90的元素时，查找成功时需比较的次数为（ B ） A.1 B.2 C.3 D.4 8.在查找顺序表各结点概率相等的情况下，顺序按值查找某个元素的算法时间复杂度为 （ B ） A.O (1) B.O (n) C.O (n ) D.O (log 2n) 第八章死锁习题及答案 一、填空题 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的绝对值等于信号量队列上的阻塞的进程数目。 ??????????????????????精品自学考料推荐?????????????????? 全国 2019 年 10 月高等教育自学考试 数据结构导论试题 课程代码： 02142 一、单项选择题（本大题共15 小题，每小题 2 分，共 30 分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的 括号内。错选、多选或未选均无分。 1.要将现实生活中的数据转化为计算机所能表示的形式，其转化过程依次为（） A. 逻辑结构、存储结构、机外表示 B. 存储结构、逻辑结构、机外表示 C.机外表示、逻辑结构、存储结构 D. 机外表示、存储结构、逻辑结构 2.若评价算法的时间复杂性，比较对数阶量级与线性阶量级，通常（） A.对数阶量级复杂性大于线性阶量级 B.对数阶量级复杂性小于线性阶量级 C.对数阶量级复杂性等于线性阶量级 D.两者之间无法比较 3.下列关于线性表的基本操作中，属于加工型的操作是（） A. 初始化、求表长度、插入操作 B. 初始化、插入、删除操作 C.求表长度、读元素、定位操作 D. 定位、插入、删除操作 4.在一个单链表中，若p 所指结点不是最后结点， s 指向已生成的新结点，则在p 之后插入 s 所指结点的正确操作是（）A.s–>next=p –>next; p –>next=s; C.s–>next=p; p –>next=s; B.p –>next=s –>next; s –>next=p; D.s–>next=p –>next; p=s; 5.若有三个字符的字符串序列执行入栈操作，则其所有可能的输出排列共有（） A.3 种 B.4 种 C.5 种 D.6 种 6.C 语言对数组元素的存放方式通常采用（） A. 按行为主的存储结构 B. 按列为主的存储结构 C.按行或列为主的存储结构 D. 具体存储结构无法确定 7.根据定义，树的叶子结点其度数（） A. 必大于 0 B. 必等于 0 C.必等于 1 D. 必等于 2 8.二叉树若采用二叉链表结构表示，则对于n 个结点的二叉树一定有（） A.2n 个指针域其中n 个指针为 NULL B.2n 个指针域其中n+1 个指针为 NULL C.2n-1 个指针域其中n 个指针为 NULL D.2n-1 个指针域其中n+1 个指针为 NULL 9.在一个无向图中，所有顶点的度数之和等于边数的（） A.1 倍 B.2 倍 C.3 倍 D.4 倍 10.若采用邻接表存储结构，则图的广度优先搜索类似于二叉树的（） 1 2018北大计算机考研经验分享 我本科毕业于北京科技大学计算机科学与技术专业，研究生将就读于北京大学计算机技术专业。初试考研总分接近370+分，计算机基础综合135分，在专业课上算是有些心得吧。 写这篇经验贴的初衷一是看过很多经验贴，都是比较散乱的回顾+感受，没有系统的复习方法；二是我在新祥旭考研一对一做专业课辅导老师，算是给自己打个广告吧，多说一句，我主要是针对考北大计算机专业的学生。当然，虽然打了一下广告，但是这篇帖子的经验还是希望大家认真看，我觉得还是能够对学弟学妹们有所裨益的。 ，下面主要和大家聊一聊北大计算机考研的情况，政治、英语、数学这些课我就不多说了，这几门课程的资料、老师都是比较成熟且成功的，大家在网上多看看就知道怎么回事了。今天，主要是说专业课以及北大计算机的招录情况。 【北大招录情况】 2018年北大软微计算机技术复试线：复试线为300分，单科线也是50+80。具体的招录比现在基本是没有相关数据的，但是招生人数还是可查的，根据软微学院官网数据：整个软件与微电子学院招收全日制654人，非全日制156人。其中计算机技术专业全日制招生310人， 包含推免生接近70人，留给其他考生的名额为240左右。 总之，现在是大数据时代，北大计算机技术的关注度也越来越高，所以以后考研竞争难度也会越来越大。 【参考书目】 822计算机基础综合 专业课教材 《数据结构》（C语言版）严蔚敏清华大学出版社 《计算机操作系统》汤子瀛西安电子科技大学出版社 《计算机网络》谢希仁电子工业出版社 《计算机组成原理》唐朔飞高等教育出版社 专业辅导书： 王道系列 《数据结构考研复习指导》 《计算机组成原理考研复习指导》 《操作系统考研复习指导》 《计算机网络考研复习指导》 《计算机专业基础综合考试指导全书》 《计算机专业基础综合考试名校真题精析》 《计算机专业基础综合考试最后8套模拟题》 第一章概论 1.数据：信息的载体,能被计算机识别、存储和加工处理。 2.数据元素：数据的基本单位，可由若干个数据项组成，数据项是具有独立含义的最小标识单位。 3.数据结构：数据之间的相互关系，即数据的组织形式。 它包括：1）数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，独立于计算机； 2）数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。 3）数据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用的运算：检索/插入/删除/更新/排序。 4.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的存储结构是逻辑结构用计算机语言的实现。 5.数据类型：一个值的集合及在值上定义的一组操作的总称。分为：原子类型和结构类型。 6.抽象数据类型：抽象数据的组织和与之相关的操作。优点：将数据和操作封装在一起实现了信息隐藏。 7. 抽象数据类型ADT：是在概念层上描述问题；类：是在实现层上描述问题；在应用层上操作对象（类的实例）解决问题。 8.数据的逻辑结构，简称为数据结构，有： （1）线性结构，若结构是非空集则仅有一个开始和终端结点，并且所有结点最多只有一个直接前趋和后继。 （2）非线性结构，一个结点可能有多个直接前趋和后继。 9.数据的存储结构有： 1）顺序存储，把逻辑相邻的结点存储在物理上相邻的存储单元内。 2）链接存储，结点间的逻辑关系由附加指针字段表示。 3）索引存储，存储结点信息的同时，建立附加索引表，有稠密索引和稀疏索引。 4）散列存储，按结点的关键字直接计算出存储地址。 10.评价算法的好坏是：算法是正确的；执行算法所耗的时间；执行算法的存储空间（辅助存储空间）；易于理解、编码、调试。 全国2012年1月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.结点按逻辑关系依次排列形成一条“锁链”的数据结构是( ) A.集合 B.线性结构 C.树形结构 D.图状结构 2.下面算法程序段的时间复杂度为( ) for ( int i=0; i A. 先进先出的线性表 B. 先进后出的线性表 C. 后进先出的线性表 D.随意进出的线性表 8.10阶上三角矩阵压缩存储时需存储的元素个数为( ) A.11 B.56 C.100 D.101 9.深度为k（k≥1）的二叉树，结点数最多有( ) A.2k个 B.(2k -1)个 C.2k-1个 D.(2k+1)个 10.具有12个结点的二叉树的二叉链表存储结构中，空链域NULL的个数为( ) A. 11 B.13 C. 23 D. 25 11.具有n个顶点的无向图的边数最多为( ) A.n+1 B.n(n+1) C.n(n-1)/2 D.2n(n+1) 12.三个顶点v1,v2,v3的图的邻接矩阵为 010 001 010 ?? ?? ?? ?? ?? ，该图中顶点v3的入度为( ) A. 0 B. 1 C. 2 D. 3 13.顺序存储的表格中有60000个元素，已按关键字值升序排列，假定对每个元素进行查找 的概率是相同的，且每个元素的关键字值不相同。用顺序查找法查找时，平均比较次数约为( ) A.20000 B.30000 C.40000 D.60000 14.外存储器的主要特点是( ) A.容量小和存取速度低 B.容量大和存取速度低 C.容量大和存取速度高 D.容量小和存取速度高 15.在待排数据基本有序的前提下，效率最高的排序算法是( ) A.直接插入排序 B.直接选择排序 C.快速排序 D.归并排序 浙02142# 数据结构导论试题第 2 页共 5 页 数据结构及算法知识 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）。 第一章操作系统引论 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）. 人工操作方式 电子管计算机，无操作系统，由手工控制作业的输入输出,通过控制台开关启动 程序运行。 人工操作方式的缺点： 用户独占全机。计算机及其全部资源只能由上机用户独占。数据结构期末考试复习笔记
自考数据结构导论20051年10月试卷
2021北京科技大学计算机科学与技术考研真题经验参考书
02142数据结构导论201604
郝斌数据结构自学笔记--知识点+程序源代码
全国自学考试数据结构导论试题及答案(4套)
数据结构复习笔记
自考数据结构导论复习资料
2012版《数据结构高分笔记》更新补丁之外部排序
数据结构学习总结
自考数据结构导论
全国数据结构导论10月高等教育自学考试试题与答案
操作系统可用来进行考研复习资料(1)
2020年10月全国数据结构导论自考试题及答案解析.doc
2018北大计算机考研经验分享
数据结构复习笔记
自考数据结构导论20120年01月试卷
面经笔记数据结构
操作系统第一章笔记
- 2018年10月自考02331数据结构试题及答案含评分标准
- 02331数据结构课后练习题
- 最新自考02331数据结构试题及答案含评分标准资料
- 全国2018年10月高等教育自学考试02331数据结构试题
- 全国2017年10月自考02331数据结构试卷及答案解释
- 02331数据结构201804
- 02331数据结构201404
- 自考02331数据结构真题及答案(2009-2018)
- 02331数据结构2014年4 月份历年真题附答案
- 2018年4月自考数据结构02331试题及答案
- 02331数据结构答案
- 02331数据结构2013年1 月份历年真题附答案
- (02331)数据结构串讲资料(一)
- 02331数据结构课后练习题
- 10月自考数据结构02331试题及答案解析
- 2016年4月自学考试数据结构02331试卷及答案解释完整版
- 最新全国自考数据结构(02331)试题及答案
- 02331《数据结构》自考——各章要点
- 02331数据结构201610
- 2021年自考02331数据结构重点总结最终修订