自考数据结构导论复习资料

查看数据结构简介第一章概论1.数据：可以由计算机存储和处理的所有对象。2.资料要素：资料的基本单位，程式会将其视为整体来考量与处理3.资料项目：也称为栏位或栏位，是资料不可分割的最小识别单位。逻辑结构需要注意的几个事项：逻辑结构与数据元素本身的内容无关逻辑结构与数据元素的相对位置无关逻辑结构与所有节点的数量无关5.数据元素之间的逻辑关系是指数据元素的关联方式或“关联关系”。6.四种类型的基本逻辑结构(集合、线性结构、树状结构和图形结构)的不同特性？答：集合的两个节点之间没有逻辑关系，有松散形式的组织。在线性结构中，节点根据逻辑关系按顺序排列，形成“链”。树状结构具有分支和层次特性，其形式与自然的树有点相似。图形结构最复杂，每个节点根据逻辑关系交织在一起，可以连接两个节点。运算是逻辑结构层级中处理功能的抽象8.基本运算的意义？如果A: s中的某些运算的集合，中的每个运算可以“减少”为中的一个或多个运算，如果其中一个不能“减少”为另一个运算，则中间运算称为基本运算9.数据结构是指由一个逻辑结构s和s中的一组基本运算组成的整体(s，)10.数据结构包括两个方面：数据表示法和数据处理11.存储结构的含义和四种基本存储方法的基本思路？答：存储结构是根据逻辑结构要求构建的数据的机器内表示法，称为存储结构。存储结构应包含三个主要部分：存储节点、内部表示和其他设施。存储结构包括四种存储方法：顺序存储、链存储、索引存储和散列存储。12.运算实现和运算的连接和差异？答：运算仅说明处理功能，不包括处理步骤和方法，而是指数据在逻辑结构s中的操作。运算实现是执行相应运算功能的程序，运算实现的核心是算法设计，即处理阶段的规则。13.算法的概念和分类？答：算法确定了解决给定类型的问题所需的所有“处理步骤”及其执行顺序，以便在有限时间内机械解决给定类型的所有问题。算法的类型包括退出的程序可执行部分、伪语言算法和非格式算法(取决于描述算法语言)14.给定输入下算法的计算意义和估计方法？答：算法在给定输入上计算的数量取决于该问题的性质，合理地选择一个或多个操作作为“标准操作”，以确定每个算法在给定输入上执行的标准操作的总数，并将此数量规定为该算法在给定输入上执行的计算量。估计方法是最坏的时间复杂性和平均时间复杂性。15.最坏的时间复杂性和平均时间复杂性的概念？a:最坏的时间复杂性，也称为最坏的时间复杂性，是算法计算出的所有输入的最大数量。平均时间复杂性，也称为平均时间复杂性，是算法在所有输入上计算出的金额的加权平均值。16.空间复杂性表示输入数据不占用存储空间的算法所需的额外存储空间量。17.算法的特性：准确性、可读性、健壮性和效率。第二章路线表1.线性结构：n(n0)节点的有限序列。2.线性结构的基本特性：如果至少有一个节点，则除了起始节点没有直接电位外，其他节点只有一种直接的倾向。除了最终节点没有直接后缀外，其他节点有一个直接后缀。线性表格的逻辑结构是线性结构4.线性表格的六个基本运算功能？答：初始化initiate (l)，创建空表的功能查找返回路线表l长度的表长度(l)读取表元素GET(L，I)，该元素是返回线性表L的I节点定位(按值查找)LOCATE(L，x)，返回找到的节点集的序列号最小值。否则，返回值为0(找不到说明)93m在线性表格L的固定I位置插入INSERT(L，x，I)，其具有加入值为x的新节点(完整表格长度1)的功能删除DELETE(L，I)，它具有取消线性表L的第一个位置节点(总表长度-1)的功能5.顺序表表示的基本思路和特征答：基本思路是顺序表中的一个存储节点存储线性表中一个节点的内容。也就是说，数据元素按所有存储节点由这些数据元素构建的逻辑关系确定的顺序存储。特征：逻辑结构中相邻的节点在存储结构中仍然相邻。区分顺序表格的容量和定线表格中表格的长度吗？答：顺序表格的容量表示定义顺序表格时的maxsize值，线性表格的表格长度表示包含的节点数。7.在顺序表中计算ai的地址：ai的地址=b (i-1)*l，b是第一个地址，l是每个节点占用的空间7.确定插入、删除和定位操作的顺序表的三种算法P18-208.单个链接列表表示的基本思路用指针表示节点之间的逻辑关系9.单个链接列表节点格式：答：数据字段和指针字段。这两部分的作用是数据字段用于存储线性表中的数据元素，指针字段用于存储指向此节点包含的数据元素的直接后缀节点的指针。10.头指针和头节点的作用？答：头指针是指向关联列表中起始节点的指针，单个链接列表由头指针唯一确定。头节点是在连接列表中的起始节点之前人工连接的节点，如果有头节点，则头指针指向头节点。无论关联列表是否为空，头指针始终不为空，头指针的设置与关联列表中第一个位置的操作在不同位置的操作相匹配。11.插入、删除和定位单个列表的三种算法：P26-2812.插入算法中包含的指针动作：s=malloc(size)；sdata=x；snext=pnext；pnext=s；删除算法中包含的指针动作：q=pnext；pnext=qnext；free(q)；13.malloc (size)的角色：创建节点形态指针14.如何配置循环链接列表：将单个链接列表中尾部节点的NULL更改为指向头节点的指针，以创建循环链接列表。回路连结表格的优点：您可以从表格的所有节点向后扫描整个表格。15.双链路列表的节点类型：说明双列表结构对称性的门：ppriornext=pnextprior；16.顺序表的主要优点和主要缺点：优点：不需要添加额外的存储空间来表示节点之间的逻辑关系易于随机访问表中的所有节点。缺点：插入和删除运算不方便使用静态分配分配分配内存空间关联列表的主要优点：插入和删除运算很方便，只需修改指针，无需移动节点利用动态分配方法分配内存空间18.字符串：以文字作为数据元素，以线性结构作为逻辑结构的数据。19.字符串逻辑结构(线性结构)和字符串特性(由零个或多个字符组成的有限序列)20.字符串的基本运算功能：相同(s，t)的功能是两个字符串的长度必须相同，该位置的字符必须全部相同。21.字符串顺序存储方法(紧缩和未压缩格式)和链接存储方法第三章堆栈、队列和数组1.堆栈的基本运算及其确定的堆栈的基本特性堆叠是特殊的定线表格，仅允许在堆叠顶部插入和删除。基本特征是使用“后进先出”工作。2.堆栈基本运算：初始化init stack(S)堆栈推送(S，X)堆栈Pop(S)读堆栈顶层元素(s) 堆栈空(s)3.顺序堆栈“溢出”、“底流”概念溢出：顺序堆栈移动到堆栈时，超过顺序堆栈的最大容量底流：顺序堆栈清空堆栈时，堆栈中的元素少于04.顺序堆栈中堆栈和堆栈计算的实现算法：P445.顺序堆栈的简单算法(初始化、空堆栈判断、选择顶部堆栈元素)链堆栈中节点的形状和说明：用于存储Data节点的数据元素Next用于指向以下数据点7.在链堆栈中实现堆栈和堆栈的算法P468.链堆栈的简单算法(初始化、空堆栈、顶部堆栈元素)9.队列的基本运算及其确定的队列的特性队列是只能插入到对手中删除的特殊线表。基本特征是使用“先进先出”工作。10.顺序团队中的“假溢出”及其解决方法：顺序团队排入多个队列，出队后顺序队列已满，但顺序团队中的空间大部分是空的；解决方法：将顺序团队更改为循环团队11.循环队满了，队空了的条件：判断循环堆叠已满的条件：(sqrear 1)%maxsize)=sqfront判断循环堆叠为空的条件：sqrear=sqfront12.链组的节点形式和链组方法：13.链组中入队和出队算法P56-57的实现数组的逻辑结构是线性结构的一般化。15.二维数组的基本运算是读写16.2d阵列：其中a00是第一个位址，k是每个资料元素的储存单位。17.稀疏矩阵的三元组表示：A=(i，j，aij)A=(1，2，3)，(1，6，1)，(3，1，5)，(3，2，-1)，(4，5，4)，(5，1，-)第四章树1.树定义：n(n0)个节点的可怜集合，满足以下条件：只有一个节点叫根。剩余节点是m(m0)的非相交非空集T1，T2.分为TM，每个都是根的子树。树状结构中的相关术语及其含义根节点父节点和儿童节点兄弟节点和堂兄弟节点后代节点和祖先节点树的水平、树的高度和树的程度二叉树的逻辑结构、特征和五种基本形式(1):二进制树是n(n0)节点的有限集合，满足以下条件：只有一个节点叫根。其馀节点是两个不相交的集合T1、T2、T1是左侧子树，T2是右侧子树，T1、T2都是二叉树。(2)特征：二叉树是有序树。二叉树图2(3)五种基本形式二叉树的基本运算和性质(1)二叉树的基本运算：初始化启动器(Bt)根(Bt)父PARENT(BT，X)求出左边孩子LCHILD(BT，X)，求出右边孩子RCHILD(BT，X)创建树(x，lbt，rbt)修剪DELLEFT(BT，X)和DELRIGHT(BT，X)(2)二叉树的特性：第I层，最大节点深度为k，最多以普通二叉树为目标。n0=n2 1 n个节点，深度完全二叉树从上到下，从左到右编号，5.二进制链接的节点格式和说明、二进制链接中每个节点的连接方法以及根指针的作用(1)二进制链接的节点形式Data是存放该节点的数据元素，lchild是存放该节点左侧孩子的指针，rchild是存放该节点右侧孩子的指针。(2)根指针用于表示根节点的作用。完全二叉树和完全二叉树概念(1)整个二进制树为k深度的二进制树的节点总数为(2)完整的二进制树是整个二进制树中零个或更少的一个，或从底部右侧开始的二进制树基于二叉树中三个遍历的简单算法设计8.晶体树和霍夫曼树的概念(1)判断树是用于描述分类过程的二进制树(2)哈夫曼树是构成加权路径的最小二进制树9.霍夫曼树的特征：由m个权重组成的霍夫曼树的节点总数为2m-1由m个权重组成的霍夫曼树的权重在叶子节点上在霍夫曼树中，权重越大，离根部越近霍夫曼树没有图1的节点10.将树转换为二进制树时，结果二进制树的右侧子树始终为空11.n个节点的辅助链接列表中总共有2n个指针。其中非空指针的数量为n-1，空指针的数量为n 112.三次链接的优点是，每个节点可以轻松找到自己的父节点13.讨论树、树系和二进制树之间的关系的目的是使用二进制树的运算方法对树执行一些运算14.要将第一个、中间和最后一个遍历序列中的两个还原为唯一的二叉树，必须存在中间序列15.附录：树可能出现的应用问题1.二叉树二进制列表图表2.二进制列表二进制树(以上问题的反向操作)二叉树顺序存储结构图操作规则：完美化从上到下，从左到右编号依次存放相应的排列座位abcdefgh1 2 3 4 5 6 7 8 9