第一章概论
数据就是指能够被计算机识别、存储和加工处理的信息的载体。
数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。
数据结构的定义：
·逻辑结构：从逻辑结构上描述数据，独立于计算机。
·线性结构：一对一关系。
·线性结构：多对多关系。
·存储结构：是逻辑结构用计算机语言的实现。
·顺序存储结构：如数组。
·链式存储结构：如链表。
·索引存储结构：·稠密索引：每个结点都有索引项。
·稀疏索引：每组结点都有索引项。
·散列存储结构：如散列表。
·数据运算。·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。
·常用的有：检索、插入、删除、更新、排序。
数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。
·原子类型：由语言提供。
·结构类型：由用户借助于描述机制定义，是导出类型。
抽象数据类型ADT：·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。
·优点是将数据和操作封装在一起实现了信息隐藏。
程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。
算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。
评价算法的好坏的因素：·算法是正确的；
·执行算法的时间；
·执行算法的存储空间（主要是辅助存储空间）；
·算法易于理解、编码、调试。
时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。
渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。
评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。
算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。
时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O（n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。
空间复杂度：是某个算法的空间耗费，它是该算法所求解问题规模n的函数。
算法的时间复杂度和空间复杂度合称算法复杂度。
第二章线性表
线性表是由n≥0个数据元素组成的有限序列。n=0是空表；非空表，只能有一个开始结点，有且只能有一个终端结点。
线性表上定义的基本运算：
·构造空表：Initlist（L）
·求表长：Listlength（L）
·取结点：GetNode（L，i）
·查找：LocateNode（L，x）
·插入：InsertList（L，x，i）
·删除：Delete（L，i）
顺序表是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的。地址计算：LOCa（i）=LOCa（1）+（i-1）*d；（首地址为1）
在顺序表中实现的基本运算：
·插入：平均移动结点次数为n/2；平均时间复杂度均为O（n）。
·删除：平均移动结点次数为（n-1）/2；平均时间复杂度均为O（n）。
线性表的链式存储结构中结点的逻辑次序和物理次序不一定相同，为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还存储了其后继结点的地址信息（即指针或链）。这两部分信息组成链表中的结点结构。一个单链表由头指针的名字来命名。
单链表运算：·建立单链表·头插法：s->next=head；head=s；生成的顺序与输入顺序相反。平均时间复杂度均为O（n）。
·尾插法：head=rear=null；if（head=null） head=s；else r->next=s；r=s；平均时间复杂度均为O（n）
·加头结点的算法：对开始结点的操作无需特殊处理，统一了空表和非空表。
·查找·按序号：与查找位置有关，平均时间复杂度均为O（n）。
·按值：与输入实例有关，平均时间复杂度均为O（n）。
·插入运算：p=GetNode（L，i-1）；s->next=p->next；p->next=s；平均时间复杂度均为O（n）
·删除运算：p=GetNode（L，i-1）；r=p->next；p->next=r->next；free（r）；平均时间复杂度均
为O（n）
单循环链表是一种首尾相接的单链表，终端结点的指针域指向开始结点或头结点。链表终止条件是以指针等
于头指针或尾指针。
采用单循环链表在实用中多采用尾指针表示单循环链表。优点是查找头指针和尾指针的时间都是O（1），不
用遍历整个链表。
双链表就是双向链表，就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior，形成两条不同
方向的链。由头指针head惟一确定。
双链表也可以头尾相链接构成双（向）循环链表。
双链表上的插入和删除时间复杂度均为O （1）。
顺序表和链表的比较：
·基于空间：
·顺序表的存储空间是静态分配，存储密度为1；适于线性表事先确定其大小时采用。
·链表的存储空间是动态分配，存储密度＜1；适于线性表长度变化大时采用。
·基于时间：
·顺序表是随机存储结构，当线性表的操作主要是查找时，宜采用。
·以插入和删除操作为主的线性表宜采用链表做存储结构。
·若插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。
第三章栈和队列
栈（Stack）是仅限制在表的一端进行插入和删除运算的线性表，称插入、删除这一端为栈顶，另一端称为栈底。表中无元素时为空栈。栈的修改是按后进先出的原则进行的，我们又称栈为LIFO表（Last In First Out）。通常栈有顺序栈和链栈两种存储结构。
栈的基本运算有六种：
·构造空栈：InitStack（S）
·判栈空： StackEmpty（S）
·判栈满： StackFull（S）
·进栈： Push（S，x）
·退栈： Pop（S）
·取栈顶元素：StackTop（S）
在顺序栈中有“上溢”和“下溢”的现象。
·“上溢”是栈顶指针指出栈的外面是出错状态。
·“下溢”可以表示栈为空栈，因此用来作为控制转移的条件。
顺序栈中的基本操作有六种：·构造空栈·判栈空·判栈满·进栈·退栈·取栈顶元素
链栈则没有上溢的限制，因此进栈不要判栈满。链栈不需要在头部附加头结点，只要有链表的头指针就可以了。
链栈中的基本操作有五种：·构造空栈·判栈空·进栈·退栈·取栈顶元素
队列（Queue）是一种运算受限的线性表，插入在表的一端进行，而删除在表的另一端进行，允许删除的一
端称为队头（front），允许插入的一端称为队尾（rear），队列的操作原则是先进先出的，又称作FIFO表（First In First Out） .队列也有顺序存储和链式存储两种存储结构。
队列的基本运算有六种：
·置空队：InitQueue（Q）
·判队空：QueueEmpty（Q）
·判队满：QueueFull（Q）
·入队：EnQueue（Q，x）
·出队：DeQueue（Q）
·取队头元素：QueueFront（Q）
顺序队列的“假上溢”现象：由于头尾指针不断前移，超出向量空间。这时整个向量空间及队列是空的却产生
了“上溢”现象。
为了克服“假上溢”现象引入循环向量的概念，是把向量空间形成一个头尾相接的环形，这时队列称循环队列。
判定循环队列是空还是满，方法有三种：
·一种是另设一个布尔变量来判断；
·第二种是少用一个元素空间，入队时先测试（（rear+1）%m = front）？满：空；
·第三种就是用一个计数器记录队列中的元素的总数。
队列的链式存储结构称为链队列，一个链队列就是一个操作受限的单链表。为了便于在表尾进行插入（入队）的操作，在表尾增加一个尾指针，一个链队列就由一个头指针和一个尾指针唯一地确定。链队列不存在队满和上
溢的问题。在链队列的出队算法中，要注意当原队中只有一个结点时，出队后要同进修改头尾指针并使队列变空。
第四章串
串是零个或多个字符组成的有限序列。
·空串：是指长度为零的串，也就是串中不包含任何字符（结点）。
·空白串：指串中包含一个或多个空格字符的串。
·在一个串中任意个连续字符组成的子序列称为该串的子串，包含子串的串就称为主串。
·子串在主串中的序号就是指子串在主串中首次出现的位置。
·空串是任意串的子串，任意串是自身的子串。
串分为两种： ·串常量在程序中只能引用不能改变；
·串变量的值可以改变。
串的基本运算有：
·求串长strlen（char*s）
·串复制strcpy（char*to，char*from）
·串联接strcat（char*to，char*from）
·串比较charcmp（char*s1，char*s2）
·字符定位strchr（char*s，charc）
。串是特殊的线性表（结点是字符），所以串的存储结构与线性表的存储结构类似。串的顺序存储结构简称
为顺序串。
顺序串又可按存储分配的不同分为： ·静态存储分配：直接用定长的字符数组来定义。优点是涉及串长的操作速度快，但不适合插入、链接操作。
·动态存储分配：是在定义串时不分配存储空间，需要使用时按所需串的长度分配存储单元。
串的链式存储就是用单链表的方式存储串值，串的这种链式存储结构简称为链串。链串与单链表的差异只是
它的结点数据域为单个字符。
为了解决“存储密度”低的状况，可以让一个结点存储多个字符，即结点的大小。
顺序串上子串定位的运算：又称串的“模式匹配”或“串匹配”，是在主串中查找出子串出现的位置。在串匹配中，将主串称为目标（串），子串称为模式（串）。这是比较容易理解的，串匹配问题就是找出给定模式串P在给定
目标串T中首次出现的有效位移或者是全部有效位移。最坏的情况下时间复杂度是O（（n-m+1）m），假如
m与n同阶的话则它是O（n^2）。链串上的子串定位运算位移是结点地址而不是整数
第五章多维数组和广义表
数组一般用顺序存储的方式表示。存储的方式有：
·行优先顺序，也就是把数组逐行依次排列。PASCAL、C
·列优先顺序，就是把数组逐列依次排列。FORTRAN
地址的计算方法：
·按行优先顺序排列的数组：LOCa（ij）=LOCa（11）+（（i-1）*n+（j-1））*d.
·按列优先顺序排列的数组：LOCa（ij）=LOCa（11）+（（j-1）*n+（i-1））*d.
矩阵的压缩存储：为多个相同的非零元素分配一个存储空间；对零元素不分配空间。
特殊矩阵的概念：所谓特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。
稀疏矩阵的概念：一个矩阵中若其非零元素的个数远远小于零元素的个数，则该矩阵称为稀疏矩阵。
特殊矩阵的类型：·对称矩阵：满足a（ij）=a（ji）。元素总数n（n+1）/2.I=max（i，j），J=min（i，j），LOCa（ij）=LOC（sa[0]）+（I*（I+1）/2+J）*d.
·三角矩阵： ·上三角阵：k=i*（2n-i+1）/2+j-i，LOCa（ij）=LOC（sa[0]）+k*d.
·下三角阵：k=i*（i+1）/2+j，LOCa（ij）=LOC（sa[0]）+k*d.
·对角矩阵：k=2i+j，LOCa（ij）=LOC（sa[0]）+k*d.
稀疏矩阵的压缩存储方式用三元组表把非零元素的值和它所在的行号列号做为一个结点存放在一起，用这些
结点组成的一个线性表来表示。但这种压缩存储方式将失去随机存储功能。加入行表记录每行的非零元素在三元
组表中的起始位置，即带行表的三元组表。
广义表是n（n≥0）个元素的有限序列，其中的元素是原子或者是一个广义表。
广义表表头和表尾的概念： ·若广义表LS非空（n≥1），则这个广义表的第一个元素就是表头。
·其余的元素组成的表称为LS的表尾，所以表尾必是一个子表。
广义表有两种表示法，一种是括号表示法，一种是图形表示法。
广义表与树（形结构）相对应，这个广义表就是纯表。
如果一个广义表的结点又可以被其他结点所共享，则这个表称为再入表。
允许递归的表称为递归表。
线性表∈纯表（树）∈再入表∈递归表 .可见，广义表是对线性表和树的推广。
广义表有两个特殊的基本运算： ·取表头head（LS）：取表中的第一个数据元素，不能对空表操作。
·取表尾tail（LS）；取除表头外，其余数据元素构成的子表，不能对空表操作。
第六章树
树是n个结点的有限集合，非空时必须满足：只有一个称为根的结点；其余结点形成m个不相交的子集，并
称根的子树。
根是开始结点；结点的子树数称度；度为0的结点称叶子（终端结点）；度不为0的结点称分支结点（非终
端结点）；除根外的分支结点称内部结点；
有序树是子树有左，右之分的树；无序树是子树没有左，右之分的树；森林是m个互不相交的树的集合；
树的四种不同表示方法：·树形表示法；·嵌套集合表示法；·凹入表示法·广义表表示法。
二叉树的定义：是n≥0个结点的有限集，它是空集（n=0）或由一个根结点及两棵互不相交的分别称作这个
根的左子树和右子树的二叉树组成。
二叉树不是树的特殊情形，与度数为2的有序树不同。
二叉树的4个重要性质：
·二叉树上第i层上的结点数目最多为2^（i-1）（i≥1）。；
·深度为k的二叉树至多有（2^k）-1个结点（k≥1）；
·在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1；
·具有n个结点的完全二叉树的深度为int（log2n）+1.
满二叉树是一棵深度为k，结点数为（2^k）-1的二叉树；完全二叉树是满二叉树在最下层自右向左去处部
分结点；
二叉树的顺序存储结构就是把二叉树的所有结点按照层次顺序存储到连续的存储单元中。（存储前先将其画
成完全二叉树）
树的存储结构多用的是链式存储。BinTNode的结构为lchild|data|rchild，把所有BinTNode类型的结点，加上一个指向根结点的BinTree型头指针就构成了二叉树的链式存储结构，称为二叉链表。它就是由根指针root
唯一确定的。共有2n个指针域，n+1个空指针。
根据访问结点的次序不同可得三种遍历：先序遍历（前序遍历或先根遍历），中序遍历（或中根遍历）、后
序遍历（或后根遍历）。时间复杂度为O（n）。
利用二叉链表中的n+1个空指针域来存放指向某种遍历次序下的前趋结点和后继结点的指针，这些附加的指
针就称为“线索”，加上线索的二叉链表就称为线索链表。线索使得查找中序前趋和中序后继变得简单有效，但对
于查找指定结点的前序前趋和后序后继并没有什么作用。
树和森林及二叉树的转换是唯一对应的。
转换方法：
·树变二叉树：兄弟相连，保留长子的连线。
·二叉树变树：结点的右孩子与其双亲连。
·森林变二叉树：树变二叉树，各个树的根相连。
树的存储结构：·有双亲链表表示法：结点data | parent，对于求指定结点的双亲或祖先十分方便，但不适于求指定结点的孩子及后代。
·孩子链表表示法：为树中每个结点data | next设置一个孩子链表firstchild，并将data | firstchild存放在一个向量中。
·双亲孩子链表表示法：将双亲链表和孩子链表结合。
·孩子兄弟链表表示法：结点结构leftmostchild |data | rightsibing，附加两个分别指向该结点的最左孩子和右邻兄弟的指针域。
树的前序遍历与相对应的二叉树的前序遍历一致；树的后序遍历与相对应的二叉树的中序遍历一致。
树的带权路径长度是树中所有叶结点的带权路径长度之和。树的带权路径长度最小的二叉树就称为最优二叉树（即哈夫曼树）。
在叶子的权值相同的二叉树中，完全二叉树的路径长度最短。
哈夫曼树有n个叶结点，共有2n-1个结点，没有度为1的结点，这类树又称为严格二叉树。
变长编码技术可以使频度高的字符编码短，而频度低的字符编码长，但是变长编码可能使解码产生二义性。如00、01、0001这三个码无法在解码时确定是哪一个，所以要求在字符编码时任一字符的编码都不是其他字符编码的前缀，这种码称为前缀码（其实是非前缀码）。
哈夫曼树的应用最广泛地是在编码技术上，它能够容易地求出给定字符集及其概率分布的最优前缀码。哈夫曼编码的构造很容易，只要画好了哈夫曼树，按分支情况在左路径上写代码0，右路径上写代码1，然后从上到下到叶结点的相应路径上的代码的序列就是该结点的最优前缀码。
第七章图
图的逻辑结构特征就是其结点（顶点）的前趋和后继的个数都是没有限制的，即任意两个结点之间之间都可能相关。
图GraphG=（V，E），V是顶点的有穷非空集合，E是顶点偶对的有穷集。
有向图Digraph：每条边有方向；无向图Undigraph：每条边没有方向。
有向完全图：具有n*（n-1）条边的有向图；无向完全图：具有n*（n-1）/2条边的无向图；
有根图：有一个顶点有路径到达其它顶点的有向图；简单路径：是经过顶点不同的路径；简单回路是开始和终端重合的简单路径；
网络：是带权的图。
图的存储结构：
·邻接矩阵表示法：用一个n阶方阵来表示图的结构是唯一的，适合稠密图。
·无向图：邻接矩阵是对称的。
·有向图：行是出度，列是入度。
建立邻接矩阵算法的时间是O（n+n^2+e），其时间复杂度为O（n^2）
·邻接表表示法：用顶点表和邻接表构成不是唯一的，适合稀疏图。·顶点表结构 vertex | firstedge，指针域存放邻接表头指针。
·邻接表：用头指针确定。 ·无向图称边表；
·有向图又分出边表和逆邻接表；
·邻接表结点结构为 adjvex | next，
时间复杂度为O（n+e），空间复杂度为O（n+e）。
图的遍历： ·深度优先遍历：借助于邻接矩阵的列。使用栈保存已访问结点。
·广度优先遍历：借助于邻接矩阵的行。使用队列保存已访问结点。
生成树的定义：若从图的某个顶点出发，可以系统地访问到图中所有顶点，则遍历时经过的边和图的所有顶点所构成的子图称作该图的生成树。
最小生成树：图的生成树不唯一，从不同的顶点出发可得到不同的生成树，把权值最小的生成树称为最小生成树（MST）。
构造最小生成树的算法： ·Prim算法的时间复杂度为O（n^2）与边数无关适于稠密图。
·Kruskal算法的时间复杂度为O（lge），主要取决于边数，较适合于稀疏图。
最短路径的算法：·Dijkstra算法，时间复杂度为O（n^2）。·类似于prim算法。
拓扑排序：是将有向无环图G中所有顶点排成一个线性序列，若
拓扑排序也有两种方法：·无前趋的顶点优先，每次输出一个无前趋的结点并删去此结点及其出边，最后得到的序列即拓扑序列。
·无后继的结点优先：每次输出一个无后继的结点并删去此结点及其入边，最后得到的序列是逆拓扑序列。
第八章排序
记录中可用某一项来标识一个记录，则称为关键字项，该数据项的值称为关键字。
排序是使文件中的记录按关键字递增（或递减）次序排列起来。
·基本操作：比较关键字大小；改变指向记录的指针或移动记录。
·存储结构：顺序结构、链表结构、索引结构。
经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的，否则排序算法是不稳定的。
排序过程中不涉及数据的内、外存交换则称之为“内部排序”（内排序），反之，若存在数据的内外存交换，则称之为外排序。
内部排序方法可分五类：插入排序、选择排序、交换排序、归并排序和分配排序。
评价排序算法好坏的标准主要有两条：执行时间和所需的辅助空间，另外算法的复杂程序也是要考虑的一个因素。
插入排序：·直接插入排序： ·逐个向前插入到合适位置。
·哨兵（监视哨）有两个作用： ·作为临变量存放R[i]
·是在查找循环中用来监视下标变量j是否越界。
·直接插入排序是就地的稳定排序。时间复杂度为O（n^2），比较次数为（n+2）（n-1）/2；移动次数为（n+4）（n-1）/2；
·希尔排序： ·等间隔的数据比较并按要求顺序排列，最后间隔为1.
·希尔排序是就地的不稳定排序。时间复杂度为O（n^1.25），比较次数为（n^1.25）；移动次数为（1.6n^1.25）；
交换排序：
·冒泡排序：·自下向上确定最轻的一个。·自上向下确定最重的一个。·自下向上确定最轻的一个，后自上向下确定最重的一个。
·冒泡排序是就地的稳定排序。时间复杂度为O（n^2），比较次数为n（n-1）/2；移动次数为3n（n-1）/2；
·快速排序：·以第一个元素为参考基准，设定、动两个指针，发生交换后指针交换位置，直到指针重合。重复直到排序完成。
·快速排序是非就地的不稳定排序。时间复杂度为O（nlog2n），比较次数为n（n-1）/2；
选择排序：
·直接选择排序： ·选择最小的放在比较区前。
·直接选择排序就地的不稳定排序。时间复杂度为O（n^2）。比较次数为n（n-1）/2；
·堆排序 ·建堆：按层次将数据填入完全二叉树，从int（n/2）处向前逐个调整位置。
·然后将树根与最后一个叶子交换值并断开与树的连接并重建堆，直到全断开。
·堆排序是就地不稳定的排序，时间复杂度为O（nlog2n），不适宜于记录数较少的文件。
归并排序： ·先两个一组排序，形成（n+1）/2组，再将两组并一组，直到剩下一组为止。
·归并排序是非就地稳定排序，时间复杂度是O（nlog2n），
分配排序：·箱排序： ·按关键字的取值范围确定箱子数，按关键字投入箱子，链接所有非空箱。
·箱排序的平均时间复杂度是线性的O（n）。
·基数排序：·从低位到高位依次对关键字进行箱排序。
·基数排序是非就稳定的排序，时间复杂度是O（d*n+d*rd）。
各种排序方法的比较和选择： ·。待排序的记录数目n；n较大的要用时间复杂度为O（nlog2n）的排序方法；
·记录的大小（规模）；记录大最好用链表作为存储结构，而快速排序和堆排序在链表上难于实现；
·关键字的结构及其初始状态；
·对稳定性的要求；
·语言工具的条件；
·存储结构；
·时间和辅助空间复杂度。
第九章查找
查找的同时对表做修改操作（如插入或删除）则相应的表称之为动态查找表，否则称之为静态查找表。
衡量查找算法效率优劣的标准是在查找过程中对关键字需要执行的平均比较次数（即平均查找长度ASL）。
线性表查找的方法：
·顺序查找：逐个查找，ASL=（n+1）/2；
·二分查找：取中点int（n/2）比较，若小就比左区间，大就比右区间。用二叉判定树表示。ASL=（∑（每层结点数*层数））/N.
·分块查找。要求“分块有序”，将表分成若干块内部不一定有序，并抽取各块中的最大关键字及其位置建立有序索引表。
二叉排序树（BST）定义是：二叉排序树是空树或者满足如下性质的二叉树： ·若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
·若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
·左、右子树本身又是一棵二叉排序树。
二叉排序树的插入、建立、删除的算法平均时间性能是O（nlog2n）。
二叉排序树的删除操作可分三种情况进行处理： ·*P是叶子，则直接删除*P，即将*P的双亲*parent中指向*P的指针域置空即可。
·*P只有一个孩子*child，此时只需将*child和*p的双亲直接连接就可删去*p.
·*p有两个孩子，则先将*p结点的中序后继结点的数据到*p，删除中序后继结点。
关于B-树（多路平衡查找树）。它适合在磁盘等直接存取设备上组织动态的查找表，是一种外查找算法。建立的方式是从下向上拱起。
散列技术：将结点按其关键字的散列地址存储到散列表的过程称为散列。散列函数的选择有两条标准：简单和均匀。
常见的散列函数构的造方法：
·。平方取中法：hash=int（（x^2）%100）
·。除余法：表长为m，hash=x%m
·。相乘取整法：hash=int（m*（x*A-int（x*A））；A=0.618
·。随机数法：hash=random（x）。
处理冲突的方法：·开放定址法： ·一般形式为hi=（h（key）+di）%m1≤i≤m-1，开放定址法要求散列表的装填因子α≤1.
·开放定址法类型： ·线性探查法：address=（hash（x）+i）%m；
·二次探查法：address=（hash（x）+i^2）%m；
·双重散列法：address=（hash（x）+i*hash（y））%m；
·拉链法： ·是将所有关键字为同义词的结点链接在同一个单链表中。
·拉链法的优点： ·拉链法处理冲突简单，且无堆积现象；
·链表上的结点空间是动态申请的适于无法确定表长的情况；
·拉链法中α可以大于1，结点较大时其指针域可忽略，因此节省空间；
·拉链法构造的散列表删除结点易实现。
·拉链法也有缺点：当结点规模较小时，用拉链法中的指针域也要占用额外空间，还是开放定址法省空间。
第十章文件
文件是性质相同的记录的集合。记录是文件中存取的基本单位，数据项是文件可使用的最小单位，数据项有时称字段或者属性。
文件·逻辑结构是一种线性结构。
·操作有：检索和维护。并有实时和批量处理两种处理方式。
文件·存储结构是指文件在外存上的组织方式。
·基本的组织方式有：顺序组织、索引组织、散列组织和链组织。
·常用的文件组织方式：顺序文件、索引文件、散列文件和多关键字文件。
评价一个文件组织的效率，是执行文件操作所花费的时间和文件组织所需的存储空间。
检索功能的多寡和速度的快慢，是衡量文件操作质量的重要标志。
顺序文件是指按记录进入文件的先后顺序存放、其逻辑顺序和物理顺序一致的文件。主关键字有序称顺序有序文件，否则称顺序无序文件。
一切存储在顺序存储器（如磁带）上的文件都只能顺序文件，只能按顺序查找法存取。
顺序文件的插入、删除和修改只能通过复制整个文件实现。
索引文件的组织方式：通常是在主文件之外建立一张索引表指明逻辑记录和物理记录之间一一对应的关系，它和主文件一起构成索引文件。
索引非顺序文件中的索引表为稠密索引。索引顺序文件中的索引表为稀疏索引。
若记录很大使得索引表也很大时，可对索引表再建立索引，称为查找表。是一种静态索引。
索引顺序文件常用的有两种：
·ISAM索引顺序存取方法：是专为磁盘存取文件设计的，采用静态索引结构。
·VSAM虚拟存储存取方法：采用B+树作为动态索引结构，由索引集、顺序集、数据集组成。
散列文件是利用散列存储方式组织的文件，亦称为直接存取文件。
散列文件
·优点是：文件随机存放，记录不需要排序；插入删除方便；存取速度快；不需要索引区，节省存储空间。
·缺点是：不能进行顺序存取，只能按关键字随机存取，且询问方式限地简单询问，需要重新组织文件。
多重表文件：对需要查询的次关键字建立相应的索引，对相同次关键字的记录建一个链表并将链表头指针、长度、次关键字作为索引表的索引项。
倒排表：次关键字索引表称倒排表，主文件和倒排表构成倒排文件。
文章来源：https://www.doczj.com/doc/644246518.html,/p/zk.html更多自考资源资料下载完全免费
数据结构导论复习 第一章概论 1．数据：凡能被计算机存储、加工处理的对象。 2．数据元素：是数据的基本单位，在程序中作为一个整体而加以考虑和处理 3．数据项：又叫字段或域，它是数据的不可分割的最小标识单位。 4．逻辑结构需要注意的几点： ①逻辑结构与数据元素本身的内容无关 ②逻辑结构与数据元素相对位置无关 ③逻辑结构与所有结点的个数无关 5．数据元素间逻辑关系是指数据元素之间的关联方式或称“领接关系”。 6．四类基本逻辑结构（集合、线性结构、树形结构和图形结构）的不同特点？ 答：集合中任何两个结点之间都没有逻辑关系，组织形式松散； 线性结构中结点按逻辑关系依次排列形成一条“锁链”； 树形结构具有分支、层次特性，其形态有点像自然界中的树； 图状结构最复杂，其中的各个结点按逻辑关系互相缠绕，任何两个结点都可以领接。 7．运算是在逻辑结构层次上对处理功能的抽象
8．基本运算的含义？ 答：假如是S上的一些运算的集合，是的一个子集，使得中每一运算都可以“归约”为中的一个或多个运算，而中任一运算不可归约为别的运算，则称中运算为基本运算 9．数据结构是指由一个逻辑结构S和S上的一个基本运算集构成的整体（S ，）。 10．数据结构涉及数据表示和数据处理两个方面 11．存储结构的含义和四种基本存储方式的基本思想？ 答：存储结构是指按照逻辑结构的要求建立的数据的机内表示称为存储结构。 一个存储结构应包含三个主要的部分：存储结点、机内表示和附加设施。 存储结构包括四种存储方式，顺序存储方式、链式存储方式、索引存储方式和散列存储方式。 12．运算实现与运算的联系与区别？ 答：运算指的是数据在逻辑结构S上的某种操作，运算只描述处理功能，不包括处理步骤和方法；而运算实现是指一个完成该运算功能的程序，运算实现的核心是处理步骤的规定，即算法设计。 13．算法的概念和分类？ 答：算法是指规定了求解给定类型问题所需的所有“处理步骤”及其执行顺序，使得给定类型的任何问题能在有限时间内被
全国2011年1月高等教育自学考试 数据结构试题 课程代码：02331 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下列选项中与数据存储结构无关的术语是（） A.顺序表 B.链表 C.链队列 D.栈 2.将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是（） A.n-1 B.n C.2n-1 D.2n 3.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则向队列中插入新元素时，修改指针的操作是（） A.rear=(rear-1)%m; B.front=(front+1)%m; C.front=(front-1)%m; D.rear=(rear+1)%m; 4.递归实现或函数调用时，处理参数及返回地址，应采用的数据结构是（） A.堆栈 B.多维数组 C.队列 D.线性表 5.设有两个串p和q，其中q是p的子串，则求q在p中首次出现位置的算法称为（） A.求子串 B.串联接 C.串匹配 D.求串长 6.对于广义表A，若head(A)等于tail(A)，则表A为（） A.( ) B.(( )) C.(( ),( )) D.(( ),( ),( )) 7.若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是 （）A.结点均无左孩子的二叉树 B.结点均无右孩子的二叉树
C.高度为n的二叉树 D.存在度为2的结点的二叉树 8.若一棵二叉树中度为l的结点个数是3，度为2的结点个数是4，则该二叉树叶子结点的个数是（） A.4 B.5 C.7 D.8 9.下列叙述中错误的是（） A.图的遍历是从给定的源点出发对每一个顶点访问且仅访问一次 B.图的遍历可以采用深度优先遍历和广度优先遍历 C.图的广度优先遍历只适用于无向图 D.图的深度优先遍历是一个递归过程 10.已知有向图G=(V，E)，其中V={V1，V2，V3，V4}，E={
第 1 章计算机系统结构的基本概念 1.1 解释下列术语 层次结构：按照计算机语言从低级到高级的次序，把计算机系统按功能划分成多级层次结构，每 一层以一种不同的语言为特征。这些层次依次为：微程序机器级，传统机器语言机器级， 汇编语言机器级，高级语言机器级，应用语言机器级等。 虚拟机：用软件实现的机器。 然后再在这低翻译：先用转换程序把高一级机器上的程序转换为低一级机器上等效的程序， 一级机器上运行，实现程序的功能。 解释：对于高一级机器上的程序中的每一条语句或指令，都是转去执行低一级机器上的一段等效 程序。执行完后，再去高一级机器取下一条语句或指令，再进行解释执行，如此反复， 直到解释执行完整个程序。 计算机系统结构：传统机器程序员所看到的计算机属性，即概念性结构与功能特性。 在计算机技术中，把这种本来存在的事物或属性，但从某种角度看又好像不存在的概念称为透 明性。 计算机组成：计算机系统结构的逻辑实现，包含物理机器级中的数据流和控制流的组成以及逻 辑设计等。 计算机实现：计算机组成的物理实现，包括处理机、主存等部件的物理结构，器件的集成度和速度，模块、插件、底板的划分与连接，信号传输，电源、冷却及整机装配技术等。 系统加速比：对系统中某部分进行改进时，改进后系统性能提高的倍数。 Amdahl 定律：当对一个系统中的某个部件进行改进后，所能获得的整个系统性能的提高， 受限于该部件的执行时间占总执行时间的百分比。 而是相对地簇聚。包程序的局部性原理：程序执行时所访问的存储器地址不是随机分布的， 括时间局部性和空间局部性。 CPI：每条指令执行的平均时钟周期数。 测试程序套件：由各种不同的真实应用程序构成的一组测试程序，用来测试计算机在各个方面的 处理性能。
自考数据构造重点（整顿） 第一章概论 1.瑞士计算机科学家沃思提出：算法+数据构造=程序。算法是对数据运算描述，而数据构造涉及逻辑构造和存储构造。由此可见，程序设计实质是针对实际问题选取一种好数据构造和设计一种好算法，而好算法在很大限度上取决于描述实际问题数据构造。 2.数据是信息载体。数据元素是数据基本单位。一种数据元素可以由若干个数据项构成，数据项是具备独立含义最小标记单位。数据对象是具备相似性质数据元素集合。 3.数据构造指是数据元素之间互有关系，即数据组织形式。 数据构造普通涉及如下三方面内容：数据逻辑构造、数据存储构造、数据运算 ①数据逻辑构造是从逻辑关系上描述数据，与数据元素存储构造无关，是独立于计算机。 数据逻辑构造分类：线性构造和非线性构造 ②数据元素及其关系在计算机内存储方式，称为数据存储构造（物理构造）。 数据存储构造是逻辑构造用计算机语言实现，它依赖于计算机语言。 ③数据运算。最惯用检索、插入、删除、更新、排序等。 4.数据四种基本存储办法：顺序存储、链接存储、索引存储、散列存储 （1）顺序存储：普通借助程序设计语言数组描述。 （2）链接存储：普通借助于程序语言指针来描述。 （3）索引存储：索引表由若干索引项构成。核心字是能唯一标记一种元素一种或各种数据项组合。 （4）散列存储：该办法基本思想是：依照元素核心字直接计算出该元素存储地址。 5.算法必要满足5个准则：输入，0个或各种数据作为输入；输出，产生一种或各种输出；有穷性，算法执行有限步后结束；拟定性，每一条指令含义都明确；可行性，算法是可行。 算法与程序区别：程序必要依赖于计算机程序语言，而一种算法可用自然语言、计算机程序语言、数学语言或商定符号语言来描述。当前惯用描述算法语言有两类：类Pascal和类C。 6.评价算法优劣：算法"对的性"是一方面要考虑。此外，重要考虑如下三点： ①执行算法所耗费时间，即时间复杂性； ②执行算法所耗费存储空间，重要是辅助空间，即空间复杂性； ③算法应易于理解、易于编程，易于调试等，即可读性和可操作性。 以上几点最重要是时间复杂性，时间复杂度惯用渐进时间复杂度表达。
自考02331数据结构重点总结(最终修订) 第一章概论 1.瑞士计算机科学家沃思提出：算法+数据结构=程序。算法是对数据运算的描述，而数据结构包括逻辑结构和存储结构。由此可见，程序设计的实质是针对实际问题选择一种好的数据结构和设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。 2.数据是信息的载体。数据元素是数据的基本单位。一个数据元素可以由若干个数据项组成，数据项是具有独立含义的最小标识单位。数据对象是具有相同性质的数据元素的集合。 3.数据结构指的是数据元素之间的相互关系，即数据的组织形式。 数据结构一般包括以下三方面内容：数据的逻辑结构、数据的存储结构、数据的运算 ①数据的逻辑结构是从逻辑关系上描述数据，与数据元素的存储结构无关，是独立于计算机的。 数据的逻辑结构分类:线性结构和非线性结构。 线性表是一个典型的线性结构。栈、队列、串等都是线性结构。数组、广义表、树和图等数据结构都是非线性结构。 ②数据元素及其关系在计算机内的存储方式，称为数据的存储结构（物理结构）。 数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。 ③数据的运算。最常用的检索、插入、删除、更新、排序等。 4.数据的四种基本存储方法:顺序存储、链接存储、索引存储、散列存储 （1）顺序存储：通常借助程序设计语言的数组描述。 （2）链接存储：通常借助于程序语言的指针来描述。 （3）索引存储：索引表由若干索引项组成。关键字是能唯一标识一个元素的一个或多个数据项的组合。 （4）散列存储：该方法的基本思想是：根据元素的关键字直接计算出该元素的存储地址。 5.算法必须满足5个准则：输入，0个或多个数据作为输入；输出，产生一个或多个输出；有穷性，算法执行有限步后结束；确定性，每一条指令的含义都明确；可行性，算法是可行的。 算法与程序的区别：程序必须依赖于计算机程序语言，而一个算法可用自然语言、计算机程序语言、数学语言或约定的符号语言来描述。目前常用的描述算法语言有两类：类Pascal和类C。 6.评价算法的优劣：算法的"正确性"是首先要考虑的。此外，主要考虑如下三点： ①执行算法所耗费的时间，即时间复杂性； ②执行算法所耗费的存储空间，主要是辅助空间，即空间复杂性； ③算法应易于理解、易于编程，易于调试等，即可读性和可操作性。
自考02331数据构造重点总结(最后修订) 第一章概论 1.瑞士计算机科学家沃思提出：算法+数据构造=程序。算法是对数据运算描述，而数据构造涉及逻辑构造和存储构造。由此可见，程序设计实质是针对实际问题选取一种好数据构造和设计一种好算法，而好算法在很大限度上取决于描述实际问题数据构造。 2.数据是信息载体。数据元素是数据基本单位。一种数据元素可以由若干个数据项构成，数据项是具备独立含义最小标记单位。数据对象是具备相似性质数据元素集合。 3.数据构造指是数据元素之间互有关系，即数据组织形式。 数据构造普通涉及如下三方面内容：数据逻辑构造、数据存储构造、数据运算 ①数据逻辑构造是从逻辑关系上描述数据，与数据元素存储构造无关，是独立于计算机。 数据逻辑构造分类：线性构造和非线性构造。 线性表是一种典型线性构造。栈、队列、串等都是线性构造。数组、广义表、树和图等数据构造都是非线性构造。 ②数据元素及其关系在计算机内存储方式，称为数据存储构造（物理构造）。 数据存储构造是逻辑构造用计算机语言实现，它依赖于计算机语言。 ③数据运算。最惯用检索、插入、删除、更新、排序等。 4.数据四种基本存储办法：顺序存储、链接存储、索引存储、散列存储 （1）顺序存储：普通借助程序设计语言数组描述。 （2）链接存储：普通借助于程序语言指针来描述。 （3）索引存储：索引表由若干索引项构成。核心字是能唯一标记一种元素一种或各种数据项组合。 （4）散列存储：该办法基本思想是：依照元素核心字直接计算出该元素存储地址。 5.算法必要满足5个准则：输入，0个或各种数据作为输入；输出，产生一种或各种输出；有穷性，算法执行有限步后结束；拟定性，每一条指令含义都明确；可行性，算法是可行。 算法与程序区别：程序必要依赖于计算机程序语言，而一种算法可用自然语言、计算机程序语言、数学语言或商定符号语言来描述。当前惯用描述算法语言有两类：类Pascal和类C。 6.评价算法优劣：算法"对的性"是一方面要考虑。此外，重要考虑如下三点： ①执行算法所耗费时间，即时间复杂性； ②执行算法所耗费存储空间，重要是辅助空间，即空间复杂性； ③算法应易于理解、易于编程，易于调试等，即可读性和可操作性。
自考数据结构公式汇总 1.O(1)、O(log2n)、O(n)、O(nlog2n)、O(n2)、 O(n3)、O(n k)、O(2n)。 2.在顺序表中第i个位置插入一个结点的移动次数为n-i+1，插入平均移动n/2次，删 除顺序表第i个结点移动次数为n-i，平均移动(n-1)/2次。 3.定义变量p=(LinkList)malloc(sizeof(ListNode))或 p=(LinkNode*)malloc(sizeof(ListNode)) 4.单循环链表判断空：head= =head->next 5.共享向量空间判断满top1=top2-1 6.入队EnQueue，出队DeQueue，front=rear空队列，循环队列克服假上溢 7.循环队列判断队满(rear+1)%m=front，循环队列指针移动方向顺时针。判队列长度 (rear-front+m)%m 8.链队列判空：Q->front=Q->rear=NULL 9.求串长strlen，串复制strcpy(to,from)，联接strcat(to,from)，串比较strcmp(s1 大就大于s1小就小于，小写字母>大写字母)，字符定位strchr 10.串的子串定位（模式匹配）下标从0开始，最坏情况下时间复杂度比较次数 O((n-m+1)m) 11.二维数组下标为0公式：行优先LOC(a00)+[i*n+j]*d，列优先LOC(a00)+[j*m+i]*d 12.三维数组下标为0公式：三维数组A mnp按行优先LOC(a ijk)=LOC(a000)+[i*n*p+j*p+k]*d 13.对称矩阵一共有n(n+1)/2个元素，存储位置 k=I*(I+1)/2+J(I=max(i,j),J=min(i,j))下标0开始 14.上三角矩阵：k=i*(2n-i+1)+j-i，下三角矩阵：k=i*(i+1)/2+j。上三角i>j下三角 i
2015年lO月高等教育自学考试全国统一命题考试 数据结构试卷 (课程代码02331) 本试卷共8页。满分l00分。考试时间l50分钟。 考生答题注意事项： 1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸. 2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。 3．第二部分为非选择题。必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。 4．合理安排答题空间．超出答题区域无效。 第一部分选择题 一、单项选择题(本大题共l5小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡” 的相应代码涂黑。未涂、错涂或多涂均无分。
1．下列选项中，不属于线性结构的是 A．网 B．栈 C．队列 D．线性表 2．长度为n的顺序表，删除位置i上的元素(0≤i≤n一1)，需要移动的元素个数为 A．n—i B．n—i—l C．i D．i+1 3．栈采用不同的存储方式时，下列关于出栈过程的叙述中，正确的是 A．顺序栈需要判定栈空，链栈也需要判定 B．顺序栈需要判定栈空，而链栈不需要判定 C．顺序栈不需要判定栈空，而链栈需要判定 D．顺序栈不需要判定栈空，链栈也不需要判定 4．若一个栈以数组V[0．．n-1]存储，初始栈顶指针top为n，则x入栈的正确操作是 A．top=top+1；V[top]=x B．V[top]=x；top=top+1 C．top=top一1；V[mp]=x D．V[top]=x；top=top—l 5．在二维数组a[9][10]中：每个数组元素占用3个存储空间，从首地址SA开始按行优先
第一章节数据库系统基本概念 1．文件系统中的数据独立性是指(设备)独立性。 2．在数据库方式下的信息处理中，(数据)占据了中心位置。 3．DBMS是位于(用户)和(OS)之间的一层数据管理软件。 4．数据模型不仅描述数据本身的特点，还要描述(数据之间的联系)。 5．DBS中，用户的数据和磁盘中的数据之间转换由(DBMS)实现。 6．在层次、网状模型中，用（指针）导航数据；而在关系模型中，用（关键码）导航数据。7．数据库的三级模式结构是对(数据)的三个抽象级别。 8．DBS中存放三级结构定义的DB称为(数据字典)。 9．DBS的全局结构体现了其(模块功能)结构。 10．DBMS为应用程序运行时开辟的DB系统缓冲区，主要用于(数据传输)和(模式转换)。11．层次模型用(树)型结构来表示实体间的联系。 12．在数据的人工管理阶段，程序与数据是(一一对应)的关系。 13．定义数据库的安全性和完整性的工作由(DBA)完成。 14．数据独立性的好处是(数据存储方式的变化不会影响到应用程序的使用)。 15．数据库的三级体系结构使用户能抽象地使用数据，不必关心(数据在计算机中的表示和存储) 。 16．概念设计阶段用到实体、实体集、属性和实体标识符等4个术语；逻辑设计阶段用到字段、记录、文件和关键码等4个术语； 第二章节数据库设计和ER模型 1．ER数据模型一般在数据（概念设计)阶段使用。 2．“为哪些表，在哪些字段上，建立什么样的索引”这一设计内容应该属于数据库设计中的(物理设计)阶段。 3．数据模型是用来描述数据库的结构和语义的，数据模型有（概念数据模型）和（结构数据模型）两类，ER模型是(概念数据模型)。 4．数据实施阶段包括两项重要的工作，一项是数据(载入)，另一项是应用程序的编码和调试。5．ER图向关系模型转化要解决的问题是如何将实体和实体之间的联系转换成关系模式，如何确定这些关系模式的(属性和键)。 6．数据库的物理设计是对一个给定的（基本数据）模型选取一个最合适应用环境的物理结构的过程。 7．数据库设计中，将(各局部ER之间的联系)分ER图集成时，主要任务是增补。 8．数据库应用系统设计中逻辑设计的主要内容是把ER模型的(实体和联系)转换为关系模式。 9．ER方法是(概念数据模型)设计的方法。 10．现实世界到机器世界过渡的中间层次是(概念模型)。 11．概念设计的目标是(企业组织信息需求)产生反映的数据库概念结构，即概念模式。12．在DBD中，子类具有一个重要的性质：(继承性)。 13．DBD的逻辑设计分成两大部分：（DB逻辑结构设计和应用程序设计）。 14．关系模型用(关键码)表示实体之间的联系。 15．DBS的维护工作由(DBA) 承担。 16．概念设计是设计能够反映用户需求的数据库概念结构，即概念模型。 17．ER模型是人们认识客观世界的一种方法、工具。 18．ER模型具有客观性和主观性两重含义。 第三章节关系模式设计理论
绝密★考试结束前 全国2014年4月高等教育自学考试 数据结构试题 课程代码：02331 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1.答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2.每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸” 的相应代码涂黑。错涂、多涂或未涂均无分。 1.与数据存储结构无关 ．．的概念是 A.栈 B.链表 C.顺序表 D.二叉链表 2.顺序表中有10个数据元素，若第一个元素的存储地址是1000，则最后一个元素地址是1036，第5个元素的地址是 A．1010 B.1016 C.1018 D.1019 3.设栈的初始状态为空，元素1、2、3、4、5、6依次入栈，得到的出栈序列是（2,4,3,6,5,1）,则栈的容量至少是 A.2 B.3 C.4 D..6 4.下列关于队列的叙述中,错误 ．．的是 A.队列是一种先进先出的线性表 B.队列是一种后进后出的线性表 C.循环队列中进行出队操作时要判断队列是否为空 1
D.在链队列中进行入队操作时要判断队列是否为满 5.对稀疏矩阵进行压缩存储的目的是 A.便于运算 B.节省存储空间 C.便于输入输出 D.降低时间复杂度 6.一棵二叉树的第7层上最多含有的结点数为 A.14 B.64 C.127 D.128 7.下列选项为完全二叉树的是 8.用邻接表表示n个顶点e条边的无向图,其边表结点的总数是 A. n×e B. e C. 2e D. n+e 9.无向图中所有顶点的度数之和与所有边数之比是 A.1/2 B.1 C.2 D.4 10.采用邻接矩阵存储图时,广度优先搜索遍历算法的时间复杂度为 A. O（n） B. O（n+e） C. O（n2） D. O（n3） 11.对序列（15,9,7,8,20,-1,4）进行排序,若一趟排序后的结果为（-1,15,9,7,8,20,4）,则采用的排序方法是 A.归并排序 B.快速排序 C.直接选择排序 D.冒泡排序 12.比较次数与待排序列初始状态无关的排序方法是 A.快速排序 B.冒泡排序 C.直接插入排序 D.直接选择排序 13.查找较快,且插入和删除操作也比较方便的查找方法是 A.分块查找 B.二分查找 C.顺序查找 D.折半查找 14.下列关于m阶B树的叙述中,错误 ．．的是 2
： 第一张概论 引言 两项基本任务：数据表示，数据处理 软件系统生存期：软件计划，需求分析，软件设计，软件编码，软件测试，软件维护 由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立，选择和实现是数据结构的核心问题。 机外表示------逻辑结构------存储结构 ~ 处理要求-----基本运算和运算-------算法 数据，逻辑结构和运算 数据：凡是能够被计算机存储，加工的对象通称为数据 数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理。又称元素，顶点，结点，记录。 数据项：数据项组成数据元素，但通常不具有完整确定的实际意义，或不被当做一个整体对待。又称字段或域，是数据不可分割的最小标示单位。 — 1.2.2 数据的逻辑结构 逻辑关系：是指数据元素之间的关联方式，又称“邻接关系” 逻辑结构:数据元素之间逻辑关系的整体称为逻辑结构。即数据的组织形式。 四种基本逻辑结构： 1 集合：任何两个结点间没有逻辑关系，组织形式松散 2 线性结构：结点按逻辑关系依次排列成一条“锁链” 3 树形结构：具有分支，层次特性，形态像自然界中的树 { 4. 图状结构：各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接。 注意点: 1.逻辑结构与数据元素本身的形式，内容无关。 2.逻辑结构与数据元素的相对位置无关 3.逻辑结构与所含结点个数无关。 运算：运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。 。 加工型运算：改变了原逻辑结构的“值”，如结点个数，结点内容等。 引用型运算:不改变原逻辑结构个数和值，只从中提取某些信息作为运算的结果。 引用：查找，读取 加工：插入，删除，更新 同一逻辑结构S上的两个运算A和B, A的实现需要或可以利用B，而B的实现不需要利用A，则称A可以归约为B。
第一概论 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）称为一个数据结构。数据结构包括逻辑结构和处理方式。
全国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={
自考《数据库系统原理》串讲笔记 第一章数据库基础知识 学习目的与要求： 本章属于基础知识，主要是对一些概念的理解和记忆。没有难点，相对的重点是数据模型的四个层次，数据库管理系统的功能，数据库系统的全局结构。 考核知识点与考核要求 1.1数据管理技术的发展阶段（识记） 1.2数据描述的术语（领会） 1.3数据抽象的级别（领会） 1.4数据库管理系统(DBMS) (领会) 1.5数据库系统（DBS）（领会） 1.1 数据管理技术的发展 几个数据库的基本术语： 数据：描述事物的符号记录 数据处理:是指从某些已知的数据出发，推导加工出一些新的数据，这些新的数据又表示了新的信息。 数据管理:是指数据的收集、整理、组织、存储、维护、检索、传送等操作，这部分操作是数据处理业务的基本环节，而且是任何数据处理业务中必不可少的共有部分。 数据管理技术：对数据的收集、整理、组织、存储、维护、检索、传送等操作，基本目的就是从大量的，杂乱无章的，难以理解的数据中筛选出有意义的数据。 数据处理是与数据管理相联系的，数据管理技术的优劣，将直接影响数据处理的效率。 1.人工管理阶段（20世纪50年代中期以前） １）数据不保存在机器中； ２）没有专用软件对数据进行管理； ３）只有程序的概念，没有文件的概念； ４）数据面向程序。 2. 文件系统阶段特点与缺陷（20世纪50年代后期至60年代中期） １）数据可长期保存在磁盘上； ２）数据的逻辑结构与物理结构有了区别； ３）文件组织呈现多样化； ４）数据不再属于某个特定程序，可以重复使用； ５）对数据的操作以记录为单位。 文件系统三个缺陷： １）数据冗余性 ２）数据不一致性
2016年10月高等教育自学考试全国统一命题考试 数据结构试卷 （课程代码02331） 本试卷共7页，满分100分，考试时间150分钟。 考生答题注意事项： 1 ?本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸 2. 第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑' 3. 第二部分为非选择题。毖须注明大、小题号，使用0. 5毫米黑色字迹签字笔作答。 4 ?合理安排答题空间，超出答题区域无效。 第一部分选择题（共30分） 一、单项选择题（本大题共15小题，每小题2分，共30分＞ 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”的相应代码涂黑。错涂、多涂或未涂均无分。 1. 下列选项中，不属于线性结构特征的是 A.数据元素之间存在线性关系 B .结构中只有一个幵始结点 C.结构中只有一个终端结点 D .每个结点都仅有一个直接前趋
2. 设17个元素的顺序表中，若将第个元素e 移动到第个位置,
不改变除e外其他元素之间的相对次序，则需移动的表中元素个数是 A. AM B, i-i C.上汁】D讨3 .若用一个大小为7的数组作为循环队列的存储结构，且当前rew和盘Ont的值分别 为2和4,在此之前的操作是从队列中删除了一个元素及加入两个元素，请问这3 个操作之前rear和矗Ont的值分别是 A. 0 和I B . 0 和3 C . 3 和6 D . 4 和5 4 .已知广义表LS=(((a)) , ((b , (c)) , (d , (e , f))) , 0) , LS 的长度是 A. 2 B . 3 C . 4 D. 5 5.—棵完全二叉树T的全部k个叶结点都在同一层中且每个分支结点都有两个孩子结点 于中包含的结点数是 A. k B. 2k-1 C k2 D .2k-1 6.如果某二叉树的前序遍历序列为abced，中序遍历序列为cebda，则该二叉树的后序遍历序列是 A. cedba B decba C ecdba D . ecbad 7.—个森林有m棵树，顶点总数为n,则森林中含有的总边数是 A. m B. n-l C n-m n+m 8.设图的邻接矩阵A如下所示。各顶点的度依次是
??????????????????????精品自学考料推荐?????????????????? 全国 2018 年 10 月高等教育自学考试 数据结构试题 课程代码： 02331 一、单项选择题（本大题共15 小题，每小题 2 分，共 30 分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选 均无分。 1．数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 2．算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 3．在线性表的下列运算中，不．改变数据元素之间结构关系的运算是（） A ．插入 B ．删除 C．排序 D ．定位 4．若进栈序列为 1， 2， 3，4， 5， 6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（） A ． 3，2， 6， 1， 4， 5 B ．3， 4， 2，1， 6， 5 C． 1， 2， 5， 3，4， 6 D ．5， 6， 4， 2， 3，1 5．设串 sl=″ Data Structures with Java ″ ,s2=″it ″，则子串定位函数index(s1,s2)的值为 （）A ． 15 B ．16 C． 17 D ．18 6．二维数组 A[8][9] 按行优先顺序存储，若数组元素A[2][3] 的存储地址为 1087，A[4][7] 的存储地址为1153，则数组元素 A[6][7] 的存储地址为（） A ． 1207 B ．1209 1
全国2006年10月高等教育自学考试 数据结构试卷 课程代码：02331 一、单项选择题<本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．数据结构是<） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 2．算法分析的目的是<） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 3．在线性表的下列运算中，不．改变数据元素之间结构关系的运算是<） A．插入B．删除 C．排序D．定位 4．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为<）A．3，2，6，1，4，5 B．3，4，2，1，6，5 C．1，2，5，3，4，6 D．5，6，4，2，3，1 5．设串sl=″Data Structures with Java″,s2=″it″，则子串定位函数index(s1,s2>的值为 <）A．15 B．16 C．17 D．18 6．二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为<） A．1207 B．1209 C．1211 D．1213 7．在按层次遍历二叉树的算法中，需要借助的辅助数据结构是<） A．队列B．栈 C．线性表D．有序表 8．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系<） A．不一定相同B．都相同
1 全国2008年1月高等教育自学考试 数据结构试题 课程代码：02331 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.逻辑上通常可以将数据结构分为（ ） A.动态结构和静态结构 B.顺序结构和链式结构 C.线性结构和非线性结构 D.初等结构和组合结构 2.在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（ ） A.访问第i 个元素的前驱（1
第一章概论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 数据结构的定义： ·逻辑结构：从逻辑结构上描述数据，独立于计算机。 ·线性结构：一对一关系。 ·线性结构：多对多关系。 ·存储结构：是逻辑结构用计算机语言的实现。 ·顺序存储结构：如数组。 ·链式存储结构：如链表。 ·索引存储结构：·稠密索引：每个结点都有索引项。 ·稀疏索引：每组结点都有索引项。 ·散列存储结构：如散列表。 ·数据运算。·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用的有：检索、插入、删除、更新、排序。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 ·原子类型：由语言提供。 ·结构类型：由用户借助于描述机制定义，是导出类型。 抽象数据类型ADT：·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。 算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。 评价算法的好坏的因素：·算法是正确的； ·执行算法的时间； ·执行算法的存储空间（主要是辅助存储空间）； ·算法易于理解、编码、调试。 时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。
渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O（n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。 空间复杂度：是某个算法的空间耗费，它是该算法所求解问题规模n的函数。 算法的时间复杂度和空间复杂度合称算法复杂度。 第二章线性表 线性表是由n≥0个数据元素组成的有限序列。n=0是空表；非空表，只能有一个开始结点，有且只能有一个终端结点。 线性表上定义的基本运算： ·构造空表：Initlist（L） ·求表长：Listlength（L） ·取结点：GetNode（L，i） ·查找：LocateNode（L，x） ·插入：InsertList（L，x，i） ·删除：Delete（L，i） 顺序表是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的。地址计算：LOCa（i）=LOCa（1）+（i-1）*d；（首地址为1） 在顺序表中实现的基本运算： ·插入：平均移动结点次数为n/2；平均时间复杂度均为O（n）。 ·删除：平均移动结点次数为（n-1）/2；平均时间复杂度均为O（n）。 线性表的链式存储结构中结点的逻辑次序和物理次序不一定相同，为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还存储了其后继结点的地址信息（即指针或链）。这两部分信息组成链表中的结点结构。一个单链表由头指针的名字来命名。 单链表运算：·建立单链表·头插法：s->next=head；head=s；生成的顺序与输入顺序相反。平均时间复杂度均为O（n）。 ·尾插法：head=rear=null；if（head=null） head=s；else r->next=s；r=s；平均时间复杂度均为O（n）
一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．在数据结构中，数据的逻辑结构可以分成（） A．内部结构和外部结构 B．线性结构和非线性结构 C．紧凑结构和非紧揍结构 D．动态结构和静态结构 2．在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（） A．数据元素的相邻地址表示 B．数据元素在表中的序号表示 C．指向后继元素的指针表示 D．数据元素的值表示 3．设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是（） s -> next = p -> next; p -> next = s; t = p -> data; p -> data = s -> data; s ->data = t; A．结点*p与结点*s的数据域互换 B．在p所指结点的元素之前插入元素 C．在p所指结点的元素之后插入元素 D．在结点*p之前插入结点*s 4．栈和队列都是（） A．限制存取位置的线性结构 B．顺序存储的线性结构 C．链式存储的线性结构 D．限制存取位置的非线性结构 5．若数组s[0..n-1]为两个栈s1和s2的共用存储空间，且仅当s[0..n-1]全满时，各栈才不能进行进
栈操作，则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为（）A．1和n+1 B．1和n/2 C．－1和n D．－1和n+1 6．执行下列程序段后，串X的值为（） S=??abcdefgh??; T=??xyzw??; substr (X,S,2,strlen(T)); substr (Y,S, stelen(T),2); strcat (X,Y); A．??cdefgh?? B．??cdxyzw?? C．??cdefxy?? D．??cdefef?? 7．多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为（） A．数组的元素处在行和列两个关系中 B．数组的元素必须从左到右顺序排列 C．数组的元素之间存在次序关系 D．数组是多维结构，内存是一维结构 8．从广义表LS＝（(p, q), r, s）中分解出原子q的运算是（） A．tail (head (LS)) B．head (tail (head (LS))) C．head (tail (LS)) D．tail (tail (head (LS))) 9．在具有n个叶子结点的严格二叉树中，结点总数为（） A．2n+1 B．2n C．2n-1 D．2n-2 10．若