威海自考考试大纲02142数据结构导论

第一章    概论

算法+数据结构=程序

从宏观上看，数据、数据元素和数据项实际上反映了数据组织的三个层次，数据可由若干个数据   元素组成，而数据元素又可由若干个数据项组成。

数据的逻辑结构是指数据元素之间的逻辑关系。

集合中任意两个结点之间都没有邻接关系，组织形式松散；

线性结构中结点按逻辑关系依次排列形成一条“链”，结点之间一个一个依次相邻接；

树形结构具有分支、层次特性，其形态像自然界中的树，上层的结点可以和下层多个结点相   邻接，但下层结点只能和上层的一个结点相邻接；

图结构最复杂，其中任何两个结点都可以相邻接。

第二章    线性表

线性表（Linear List）是一种线性结构，它是由 n（n>0）个数据元素组成的有穷序列。

线性表的顺序存储：将表中的结点依次存放在计算机内存中一组连续的存储单元中，一般使用数   组来表示顺序表。

顺序表的插入与删除：元素的移动次数不仅与顺序表的长度 n 有关，还与插入的位置 i 有关。

线性表的链接存储：各个结点在内存中的存储位置并不一定连续，可存放在内存的不同位置。   5.单链表的插入：p->next=q->next 和 q->next=p 两条语句的执行顺序不能颠倒。

6 单链表上的删除：p=q->next;Q->next=p->next;free (p); 7.双向循环链表的删除：

（1）p->prior->next=p->next;    //p 前驱结点的后链指向 p 的后继结点

（2）p->next->prior=p->prior;   //p 后继结点的前链指向 p 的前驱结点

（3）free (p) ;    '    //释放的空间8.双向循环链表的插入：

（1）t 一〉prior=p;

（2）t->next=p->next；

（3）p->next->prior=t；

（4）p->next=t；

第三章    栈、队列和数组

栈的概念：栈是运算受限的线性表，这种线性表上的插入和删除运算限定在表的某一端进行。允   许进行插入和删除的一端称为栈顶，另一端称为栈底。不含任何数据元素的栈称为空栈。处于栈顶位   置的数据元素称为栈顶元素。

栈的运算特点：后进先出。

栈的插入和删除操作分别称为进栈和出栈。

双栈满的条件：top1+1=top2（假设 top1） 5.栈的简单应用与递归：函数调用应用栈

顺序队列的入队操作：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;

循环队列满条件：（（CQ.rear+1）%maxsize==CQ.front）成立队列空条件：（CQ.rear==CQ.front）成立

矩阵的压缩存储：针对一些有许多值相同的元素或零元素的高阶矩阵，为了节省空间，对这类矩阵采用多个值相同的元素只分配一个存储空间，零元素不存储的策略，这一方法称为矩阵的压缩存储。

特殊矩阵：n 阶的对称矩阵和三角矩阵占用存储空间大小为：

（1）对称矩阵。若一个 n 阶方阵 A 中的元素满足下述条件：n(n+1)/2 11.稀疏矩阵的三元组表示法：

（i,j,a_ij）,i 表示行序号，j 表示列序号，a_ij 是非零元素的值。

第四章    树和二叉树

树的概念：可为空，若不空，左右子树互不相交。

叶子：度为 0 的结点

二叉树的概念：二叉树(Binary Tree)是 n(n≥0)个元素的有限集合，该集合或者为空，或者由一个根及两棵互不相交的左子树和右子树组成，其中左子树和右子树也均为二叉树。

二叉树的性质：

二叉树第 i（i≥1）层上至多有 2i1 个结点。

深度为 k（k≥1）的二叉树至多有 2k 1 个结点。

对任何一棵二叉树，若度数为 0 的结点（叶结点）个数为 n₀，度数为 2 的结点个数为 n₂，则n₀=n₂+1。

含有 n 个结点的完全二叉树的深度为 log2n +1。

完全二叉树结点编号关系：编号 i 的双亲为i / 2 ，左孩子为 2*i，右孩子为 2*i+1

二叉树的顺序存储：用一维数组来实现。对非完全二叉树不成立。如果需要顺序存储非完全二叉   树，首先必须将其转化为完全二叉树，可增设若干个虚拟结点。但这种方法造成了空间的浪费。

二叉树的链式存储：二叉树有不同的链式存储结构，其中最常用的是二叉链表与三叉链表。

每个二叉链表还必须有一个指向根结点的指针，该指针称为根指针。对二叉链表的访问只能从根   指针开始。

二叉树遍历的递归实现：

先序遍历：根-左-右

中序遍历：左-根-右

后序遍历：左-右-根

二叉树的层次遍历：二叉树的层次遍历是指从二叉树根结点的这一层开始，逐层向下遍历，在每   一层上按从左到右的顺序对结点逐个访问。层次遍历可用队列来实现。

树的存储结构：

（1）孩子链表表示法；（2）带双亲的孩子链表表示法。；（3）孩子兄弟链表；（4）双亲表示法。   孩子兄弟链表的结构形式与二叉链表完全相同，但结点中指针的含义不同。

树、二叉树、森林的关系：

树（森林）转化成二叉树：①左孩子=左孩子；②兄弟=右孩子。

二叉树转换成树（森林）：①左孩子=左孩子；②右孩子=兄弟。

森林的遍历：

森林有两种遍历方法：先序遍历和中序遍历

对森林转换成的二叉树分别进行先序遍历和中序遍历，可以分别得到与该森林的先序序列和中序   序列相同的序列。

分类与判定树：用于描述分类过程的二叉树称为判定树。

哈夫曼树的构造：两个最小的结点构造新结点。   n 个结点构成的哈夫曼树共有 2n-1 个结点。

哈夫曼编码：左 0 右 1

第五章    图

任何两点之间都有边的无向图称为无向完全图。一个具有 n 个顶点的无向完全图的边数为C2 =nn-1/2 。任何两点之间都有弧的有向图称为有向完全图。一个具有 n 个顶点的有向完全图的弧数为P2 =nn-1 。

含有 n 个结点的图的生成树的边的数目一定为 n-1，若大于，说明有环。

图的存储结构

邻接矩阵：无向图的邻接矩阵是一个对称矩阵。

邻接表：有向图邻接表的表长等于点的出度，逆邻接表的表长等于点的入度。

图的遍历：遍历图的基本方法有两种：深度优先搜索和广度优先搜索。

连通图的深度优先搜索：深度优先搜索遍历类似于树的先序遍历。（注意：可回退）

连通图的广度优先搜索：广度优先搜索遍历类似于树的按层次遍历的过程。

图的应用：

最小生成树

①最小生成树的概念：一个图的最小生成树是图所有生成树中权总和最小的生成树。

②构造最小生成树的 Prim 算法：从一个顶点出发添加权值小的边。

③构造最小生成树的克鲁斯卡尔（Kruskal）方法：从多有边当中选择权值最小的边。

单源最短路径（Dijkstra 算法）

拓扑排序：

前提条件：完成拓扑排序的前提条件是 AOV 网中不允许出现回路。步骤：

图中选择一个入度为 0 的顶点，输出该顶点；

从图中删除该顶点及其相关联的弧，调整被删弧的弧头结点的入度(入度减 1);

重复执行(1)、(2)直到所有入度为 0 的顶点均被输出，拓扑排序完成，或者图中再也没有入度

为 0 的顶点。

第六章    查找

基本概念：查找表的逻辑结构是集合。

静态查找表的操作：查找、读取。动态查找表的操作：查找、读取。插入、删除。

静态查找表：

顺序表上的查找：

通常用“数据元素的键值与给定值的比较次数”作为衡量查找算法好坏的依据，称上述比较次数   为查找长度。但是，查找长度与键值在顺序表中位置有关，且差别很大。鉴于这种情况，可以将“查   找成功时的平均查找长度”（记为 ASL）作为评价查找算法时间性能的度量。

ASL=PiCi ，其中 P_i 为查找第 i 个元素（即给定值 key 与顺序表中第 i 个元素的键值相等）的

i=1

概率，且 C_i 表示在找到第 i 个元素时，与给定值已进行比较的键值个数。

有序表上的查找：如果顺序表中数据元素是按照键值大小的顺序排列的，则称为有序表。在   这种存储表示下，查找运算可以用效率更高的二分查找法实现。

假定有序表是按键值从小到大有序。二分查找算法如下：

int SearchBin(SqTable T,KeyType key)

/*在有序表 T 中，用二分查找法查找键值等于 key 的元素，变量 low,high 分别标记查找区间的下界和上届*/

{    int low.high;    //置查找区间初值low=1;high=T.n;

while(low<=high)

{    //区间长度不为 0 时继续查找

mid=(low+high)/2;    //对区间进行折半，”/”为整除if(key==T.elem[mid].key)return mid;

else if(key在前半区间查找

else low=mid+1;    //在后半区间查找

}

return 0;

}

二分查找的查找长度不超过 log2n +1。当 n 较大时可得ASLb≈log2 n+1-1

二分查找的时间性能比顺序查找好。而相比顺序查找而言，二分查找要求表元素是排好序的。

索引顺序表上的查找：通过索引将顺序表分割为若干块，而顺序表呈现出“按块有序”的性质。

二叉排序树：

定义：一棵二叉排序树(又称二叉查找树)或者是一棵空二叉树，或者是具有下列性质的二叉

树：

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

②若它的右子树不空，则右子树上所有结点的键值均大于它的根结点键值；   根的左、右子树也分别为二叉排序树。

二叉排序树上的查找：

二叉排序树上的查找长度不仅与结点数 n 有关，也与二叉排序树的生成过程有关。

二叉排序树上的插入：查找不成功才可以执行插入操作。

二叉排序树上的查找分析

二叉排序树上的平均查找长度是介于 O（n）和 O（ log2n ）之间的，其查找效率与树的形态有关。二叉排序树的平均查找长度ASL≤1+log2n。

散列表：设有散列函数 H 和键值k1,k2 ，若k1≠k2 ,但是Hk1 =Hk2  ，则称这种现象为冲突，

且称k1,k2 是相对于 H 的同义词。

常用散列法：除留余数法：H (key) = key mod p (p≤n)。为了减少冲突，通常选 p 为小于散列表长度的素数。

散列表的实现：

线性探测法

d+1,d+2,…，m-1,0,1,…,d-1

非同义词之间对同一个散列地址的争夺现象称为“堆积”。为了减少堆积的机会，应设法使后继   散列地址尽量均匀地分散在整个散列表中。

二次探测法

d₀=H(key)

d_i= (d₀±i²) mod m

第七章    排序

类别	方法	方式	时间复杂度	稳定性
插入排序	直接插入排序	类似图书馆中整理图书过程	O(n2 )	稳定
交换排序	冒泡排序	轻者在上，重者在下	O(n2 )	稳定
	快速排序	工作区间 x，指针 i,j	平均O(n log2 n) 最坏 O(n2 )	不稳定
选择排序	直接选择排序	直接选择最小值交换	平均、最坏均为 O(n log2 n)	不稳定
	堆排序	初建堆-初始堆-筛选	O(n2 )	不稳定
归并排序	二路归并排序	有序序列合并，同时排序		稳定

以上就是东营自考考试大纲02142数据结构导论的全部内容，关注本站，获取更多关于自考的备考资料，助力自考上岸。