《2022年自考数据结构导论复习资料.doc》由会员分享，可在线阅读，更多相关《2022年自考数据结构导论复习资料.doc（33页珍藏版）》请在金锄头文库上搜索。
1、数据结构导论复习第一章 概论1数据：凡能被计算机存储、加工处理的对象。2数据元素：是数据的基本单位，在程序中作为一个整体而加以考虑和处理3数据项：又叫字段或域，它是数据的不可分割的最小标识单位。4逻辑结构需要注意的几点：逻辑结构与数据元素本身的内容无关逻辑结构与数据元素相对位置无关逻辑结构与所有结点的个数无关5数据元素间逻辑关系是指数据元素之间的关联方式或称“领接关系”。6四类基本逻辑结构（集合、线性结构、树形结构和图形结构）的不同特点？答：集合中任何两个结点之间都没有逻辑关系，组织形式松散；线性结构中结点按逻辑关系依次排列形成一条“锁链”；树形结构具有分支、层次特性，其形态有点像自然界中的树
2、；图状结构最复杂，其中的各个结点按逻辑关系互相缠绕，任何两个结点都可以领接。7运算是在逻辑结构层次上对处理功能的抽象8基本运算的含义？ 答：假如是S上的一些运算的集合，是的一个子集，使得中每一运算都可以“归约”为中的一个或多个运算，而中任一运算不可归约为别的运算，则称中运算为基本运算9数据结构是指由一个逻辑结构S和S上的一个基本运算集构成的整体（S ，）。10数据结构涉及数据表示和数据处理两个方面11存储结构的含义和四种基本存储方式的基本思想？答：存储结构是指按照逻辑结构的要求建立的数据的机内表示称为存储结构。一个存储结构应包含三个主要的部分：存储结点、机内表示和附加设施。 存储结构包括四种存
3、储方式，顺序存储方式、链式存储方式、索引存储方式和散列存储方式。 12运算实现与运算的联系与区别？ 答：运算指的是数据在逻辑结构S上的某种操作，运算只描述处理功能，不包括处理步骤和方法；而运算实现是指一个完成该运算功能的程序，运算实现的核心是处理步骤的规定，即算法设计。13算法的概念和分类？答：算法是指规定了求解给定类型问题所需的所有“处理步骤”及其执行顺序，使得给定类型的任何问题能在有限时间内被机械地求解。算法的类型有：运行终止的程序可执行部分、伪语言算法和非形式算法（根据描述算法语言不同）14算法在给定输入下的计算量的含义和估算的方法？ 答：算法在给定输入下的计算量是指根据该类问题的特点合
4、理地选择一种或几种操作作为“标准操作”，确定每个算法在给定输入下共执行多少次标准操作，并将此次数规定为该算法在给定输入下的计算量。 估算的方法有：最坏时间复杂度和平均时间复杂度。15最坏情况时间复杂性和平均时间复杂性的概念？ 答：最坏情况时间复杂性也称为最坏时间复杂度，是指以算法在所有输入下的计算量的最大值作为算法的计算量；平均情况时间复杂性也称为平均时间复杂度，是指以算法在所有输入下的计算量的加权平均值作为算法的计算量；16空间复杂性指的是一个算法除输入数据占存储空间之外所需要的附加存储空间的大小。17算法的性质：正确性、易读性、健壮性和高效率。第二章 线性表1线性结构：是n（n0）个结点的
5、有穷序列。2线性结构的基本特征：若至少含有一个结点，则除起始结点没有直接前趋外，其他结点有且仅有一个直接前趋；除终端节点没有直接后继外，其他结点有且仅有一个直接后继。3线性表的逻辑结构是线性结构4线性表的六种基本运算的功能？ 答：初始化INITIATE(L)，功能是建立一个空表 求表长LENGTH(L)，功能是返回线性表L的长度 读表元GET(L，i)，功能是返回线性表L的第i个结点 定位（按值查找）LOCATE(L，X),功能是返回找到的结点集合中序号的最小值，否则返回值为0（说明没有找到） 插入INSERT（L，X，i），功能是在线性表L的地i个位置上增加一个值为X的新结点（整个表长+1）
6、 删除DELETE(L，i)，功能是撤销线性表L的第i个位置结点（整个表长-1）5顺序表表示法的基本思想、特点 答：基本思想是：按照顺序存储方式，顺序表的一个存储结点存储线性表的一个结点的内容，即数据元素，所有存储结点按相应数据元素建的逻辑关系决定的次序依次排列。 特点：逻辑结构中相邻的结点在存储结构中仍相邻。6区别顺序表的容量与线性表的表长? 答：顺序表的容量是指定义顺序表时的maxsize的值，而线性表的表长是指其中包含的结点个数。7顺序表中ai的地址计算：ai的地址=b+（i-1）*l，b是首地址，l是每个结点占的空间7掌握顺序表上实现插入、删除和定位运算的三个算法P18-208单链表表
7、示法的基本思想用指针表示结点间逻辑关系9单链表的结点形式：答：由数据域和指针域两部分组成；这两部分各自的作用分别是数据域是用于存储线性表的一个数据元素的，指针域是用于存放一个指针的，该指针指向本结点所含数据元素的直接后继所在的结点。10头指针和头结点的作用？ 答：头指针是一个指向链表开始结点的指针，单链表由头指针唯一确定；头结点是我们人为地在链表的开始结点之前附加的一个结点，有了头结点之后，头指针指向头结点，不论链表是否为空，头指针总是非空的，而且头指针的设置使得对链表的第一位置上的操作和在其他位置上的操作一致。11单链表上实现插入、删除和定位三种运算的三个算法：P26-2812插入算法中所包
8、含的指针操作：s=malloc(size);sdata=x;snext=pnext;pnext=s; 删除算法中所包含的指针操作：q=pnext;pnext=qnext;free(q);13Malloc（size）的作用： 生成一个结点 形式一条指针14循环链表的组织方法：将单链表中的尾结点的NULL改成指向头结点的指针，就形成了循环链表。循环链表优点：可以从表中任一结点出发都可以向后扫描整表。15双链表的结点形式： 刻画双链表结构的对称性的语句：ppriornext= pnextprior;16顺序表的主要优点和主要缺点： 优点：无需为表示结点间的逻辑关系而增加额外的存储空间 可以方便地随机
9、存取表中的任意结点 缺点：插入和删除运算不方便 分配内存空间采用静态分配方式17链表的主要优点： 插入和删除运算方便，只需要修改指针，不需要移动结点 分配内存空间采用动态分配方式18字符串：以字符为数据元素，以线性结构为逻辑结构的数据。19串的逻辑结构（是线性结构）和串的特点（是由0个或多个字符组成的有穷序列）20串的基本运算的功能：判等EQUAL(S,T)的功能是两个串的长度要相等，而且对应位置的字符都要相同。21串的顺序存储方法（紧缩格式和非紧缩格式）和链接存储方法第三章 栈、队列和数组1栈的基本运算及由此而决定的栈的基本特点栈是一种只允许在栈顶进行插入、删除的特殊线性表；其基本特点是采用
10、“后进先出”操作；2栈的基本运算：初始化InitStack（S）进栈Push（S，X）退栈Pop（S） 读栈顶元素TOP（S）判断栈空Empty（S）3顺序栈 “上溢”、“下溢”的概念 “上溢”：顺序栈在进行进栈时，超过了顺序栈的最大的容量 “下溢”：顺序栈在进行退栈时，栈中的元素少于0个元素4进栈和退栈运算在顺序栈上的实现算法：P445顺序栈上的简单算法（初始化，判栈空，取栈顶元素）6链栈的结点形式及其描述： Data用来存放该结点的数据元素 Next用来存放指向下一个数据元素7链栈上实现进栈和退栈的算法P468链栈上的简单算法（初始化，判栈空，取栈顶元素）9 队列的基本运算及由此决定的队列
11、的特点 队列是一种只允许在对头进行插入在队尾进行删除的特殊线性表；其基本特点是采用“先进先出”操作；10顺序队上的“假溢出”及其解决方法：顺序队在进行多次入队、出队后，顺序队已经满了，但顺序队中的大部分空间是空的； 解决方法：将顺序队改成循环队11循环队队满、队空的条件： 判断循环栈满的条件：（sqrear+1）%maxsize）=sqfront 判断循环栈空的条件：sqrear= sqfront12链队的结点形式及其链队的组织方法：13在链队上实现入队、出队的算法P56-5714数组的逻辑结构是线性结构的推广15二维数组的基本运算是读与写16二维数组：，其中a00是首地址，k是每个数据元素存
12、储单元。17稀疏矩阵的三元组表示法：A=（i,j,aij）A=(1,2,3),(1,6,1),(3,1,5),（3，2，-1），（4，5，4），（5，1，-3）)第四章 树1树的定义：是n（n0）个结点的有穷集合，满足： 有且仅有一个称为根的结点 其余结点分为m（m0）个互不相交的非空集合T1，T2 Tm，这些集合中的每一个都是一棵树，称为根的子树。2树形结构的有关术语及其含义根结点双亲结点和孩子结点兄弟结点和堂兄弟结点子孙结点和祖先结点树的层次、树的高度和树的度3二叉树的逻辑结构、特点和五种基本形态（1）：二叉树是n（n0）个结点的有穷集合，满足： 有且仅有一个称为根的结点 其余结点分为2个
13、互不相交的集合T1，T2，T1是左子树，T2是右子树，且T1，T2也都是一棵二叉树。（2）特点：二叉树是棵有序树 二叉树的度2（3）五种基本形态 4二叉树的基本运算和性质（1）二叉树的基本运算： 初始化 INITIATE(BT) 求根 ROOT(BT) 求双亲PARENT(BT,X) 求左孩子 LCHILD(BT,X) 求右孩子 RCHILD(BT,X) 建树CREATE(X,LBT,RBT) 剪枝DELLEFT(BT,X) 和 DELRIGHT(BT,X)（2）二叉树的性质： 第i层上，最多有个结点 深度是K，最多总有 是针对普通二叉树 n0=n2+1 具有n个结点，深度 是针对完全二叉树
14、按照从上到下，从左到右的顺序编号， 5二叉链表的结点形式及其描述，二叉链表中各结点的联系方法及根指针的作用（1）二叉链表的结点形式data是存放该结点的数据元素，lchild是存放指向该结点的左孩子的指针，rchild是存放指向该结点的右孩子的指针。（2）根指针的作用，是用来指明根结点。6满二叉树和完全二叉树的概念（1）满二叉树是深度为K的二叉树的总共结点数为（2）完全二叉树是在满二叉树上少0个或者从最下层的最右边开始少起的二叉树7设计二叉树上基于三种遍历的简单算法8判定树和哈夫曼树的概念（1）判断树是用来描述分类过程的二叉树（2）哈夫曼树是构造带权路径长度最小的二叉树9.哈夫曼树的特性:m个权值构造的哈夫曼树的结点总数为2m-
