数据结构导论复习题

第一章概论

数据就是指能够被计算机识别、存储和加工处理的信息的载体。

数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。

数据结构的定义：·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。

·线性结构：多对多关系。

·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。

·链式存储结构：如链表。

·索引存储结构：·稠密索引：每个结点都有索引项。

·稀疏索引：每组结点都有索引项。

·散列存储结构：如散列表。

·数据运算。·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。

·常用的有：检索、插入、删除、更新、排序。

数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。·原子类型：由语言提供。

·结构类型：由用户借助于描述机制定义，是导出类型。

抽象数据类型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；适于线性表长度变化大时采用。

·基于时间：

·顺序表是随机存储结构，当线性表的操作主要是查找时，宜采用。

·以插入和删除操作为主的线性表宜采用链表做存储结构。

·若插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。

线性表和数组

概念：

一、线性表：是N个元素构成的有限序列。

顺序存贮结构：地址计算，插入、删除。

链式存贮结构：单链表，查找、插入、删除。

循环链表：

双向链表：

二、数组：

以行为主；

以列为主；计算地址：

三、栈：是一种特殊的线性表，这种表只能在固定的一端进行插入与删除运算。

队列：是另一种特殊的线性表，删除运算限定在表的一端进行，而插入运算在另一端进行。

第三章栈和队列

栈（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）。链串上的子串定位运算位移是结点地址而不是整数

串

概念：是由N个字符组成的有限序列。

存贮结构：

顺序表示法：

1、紧缩格式

2、非紧缩格式

3、以单字节为单位的存贮方式

链式表示法：

串名的存贮映象：

第五章多维数组和广义表

数组一般用顺序存储的方式表示。存储的方式有：·行优先顺序，也就是把数组逐行依次排列。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，然后从上到下到叶结点的相应路径上的代码的序列就是该结点的最优前缀码。

树

一、概念：

树：是一个或多个结点的有穷集合T，且满足以下条件：

1、有且仅有一个指定的称作树根的结点；

2、除根以外的其余结点被分成m个不相交的集合，这些集合的每一个又都是树，并且称为根的子树。

结点的度：结点N的子树数称为结点的度。

树的度：树T中各结点的度的最大值称的树T的度。

叶子：树中度为0的结点称为叶子（终端结点）。

分枝结点：树中度不为0的结点称为分枝结点（非终端结点）。

双亲和孩子：若树中结点P的一棵子树的根是结点C，则我们称P是C的双亲或父母，反之称C是P 的孩子。

结点的层数：树的层数为1，其余任一结点的层数等于它的双亲的层数加1.

树的深度：树中各结点的层数的最大值称为T的深度（高度）。

兄弟和堂兄弟：同一双亲的孩子之间互称为兄弟，其双亲在同一层的结点互为堂兄弟。

祖先和子孙：一个点的祖先是指从树的根到该结点所经分枝上的所有结点。一个结点的子树的所有结点都称为该结点的子孙。

有序树和无序树：如果树中结点各棵子树规定从左至右是有次序的，则称树为有序树，否则为无序树。

森林：N棵互不相交的树的集合称为森林。

二、树的存贮表示：

1、双亲数组表示：记录型一维数组：data，parent

2、孩子链表表示法：

·多重链表表示法： data，degree，link1，link2…

·单链表表示法：data，likn

3、左孩子右兄弟链表示法：lchild，data，rsibling

三、二叉树：

1、概念：是有限个结点的集合，它或者为空集，或者是由一个根结点以及两棵互不相交的且分别称为根的左子树和右子树的二叉树组成。五种形态：空，根，左，右，左右

2、性质：

·位于二叉树第I层上的结点，最多为2I-1；（I）=1

·深度为K的二叉树的结点总数，最多为2K-1（K）=1

·N0=N2+1

满二叉树：一棵深度为K的具有2K-1个结点的二叉树

完全二叉树：在一棵二叉树中，若所有结点的度为0或为2的二叉树

顺序二叉树：如果深度为K的具有N个结点的二叉树，它的每一个结点都与深度为K的满二叉树中顺序编号是1到N的结点相对应的二叉树。

三、二叉树的存贮表示：

1、顺序存贮：

2、链表表示：lchild，data，rchlid

3、遍历：

·前序：根—左—右

·中序：左—根—右

·后序：左—右—根

四、线索二叉树：

五、树的二叉树表示，森林与二叉树的转换。

六、路径长度：树中一个结点到另一个结点之关的路径由这两个结点之间的分枝所构成，路径上的分枝数目称为它的路径长度。

哈夫曼树：WPL，哈夫曼码

第七章图

图的逻辑结构特征就是其结点（顶点）的前趋和后继的个数都是没有限制的，即任意两个结点之间之间都可能相关。

图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中所有顶点排成一个线性序列，若∈E（G），则在线性序列u在v 之前，这种线性序列称为拓扑序列。

拓扑排序也有两种方法：·无前趋的顶点优先，每次输出一个无前趋的结点并删去此结点及其出边，最后得到的序列即拓扑序列。

·无后继的结点优先：每次输出一个无后继的结点并删去此结点及其入边，最后得到的序列是逆拓扑序列。

图

概念：一个图G由两个集合V和E组成，V是有限的非空顶点集，E是用顶点对表示的边集。

无向图，有向图；

邻接，关联，邻接到（于），关联于，孤立顶点。

顶点的度：图G中关联于顶点V的边的数目称为V的度。

所有顶点的度等于边的两倍。

子图

完全图：每对顶点之间都有一条边相连的图。在有向图中，每对顶点之间都有两条有向边相互关联的图。

在无向完全图中，边的总数为Cn2=n（n-1）/2

在有向完全图中，边的总数为Pn2=n（n-1）

路径：由边组成。

回路

连通图：对于无向图，如果图中任何两顶点都是可达的，则称此图为连能图。

对于有向图，如果图中任何两个顶点都是相互可达的，则此有向图是强连通的，如果图中任何两顶点至少有一个顶点另一个顶点可达，则称此有向图是单向连通的。

强连通分量：有向图的最大强连通子图称为它的强连通分量。树图：其本质特征是连通性和无圈性，把不含圈的无向连通图称为树图。

网络：是每条边上带有数量指标的连通图。

邻接矩阵，邻接表

第八章排序

记录中可用某一项来标识一个记录，则称为关键字项，该数据项的值称为关键字。

排序是使文件中的记录按关键字递增（或递减）次序排列起来。

·基本操作：比较关键字大小；改变指向记录的指针或移动记录。

·存储结构：顺序结构、链表结构、索引结构。

经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的，否则排序算法是不稳定的。

排序过程中不涉及数据的内、外存交换则称之为“内部排序”（内排序），反之，若存在数据的内外存交换，则称之为外排序。

内部排序方法可分五类：插入排序、选择排序、交换排序、归并排序和分配排序。

评价排序算法好坏的标准主要有两条：执行时间和所需的辅助空间，另外算法的复杂程序也是要考虑的一个因素。

插入排序：·直接插入排序：·逐个向前插入到合适位置。

·哨兵（监视哨）有两个作用：·作为临变量存放R

·是在查找循环中用来监视下标变量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，结点较大时其指针域可忽略，因此节省空间；

·拉链法构造的散列表删除结点易实现。

·拉链法也有缺点：当结点规模较小时，用拉链法中的指针域也要占用额外空间，还是开放定址法省空间。

查找

查找：就是确定一个已给的数据是否出现在某个数据表中。

域（字段）：组成记录的每个数据项。

关键字：通常记录中总存在某个或某组数据项，它们的值能唯一标识一个记录，这个（组）数据项称为关键字。

方法：顺序

二分

线性插值

分区

二叉排序树：如果将记录的键码按二叉树的结构来组织，并且假定树中任意非叶子结点的键码大于其左子树所有结点的键码（若左子树存在的话），而小于其右子树所有结点的键码（如右子树存在的话），这样的二叉树叫二叉排序树（二叉查找树）。哈希查找：

哈希函数：能把关键字映射成记录存贮地址的函数。

哈希表：假定数组HT[0··m-1]为存贮记录的地址空间，哈希函数H以每个记录的关键字值K作为输入，产生一个落在[0··m-1]内的整数H（K），并以它作为K所标识的记录在表HT中的地址或索引号，这样产生的记录表H（K）叫做··]

构造哈希函数的方法：

直接定址法

除留余数法

平方取中法

折叠法与移位法

数字分析法

冲突处理：

开放定址法： 1、线性探测法 2、伪随机探测法

链地址法

第十章文件

文件是性质相同的记录的集合。记录是文件中存取的基本单位，数据项是文件可使用的最小单位，数据项有时称字段或者属性。

文件·逻辑结构是一种线性结构。

·操作有：检索和维护。并有实时和批量处理两种处理方式。

文件·存储结构是指文件在外存上的组织方式。

·基本的组织方式有：顺序组织、索引组织、散列组织和链组织。

·常用的文件组织方式：顺序文件、索引文件、散列文件和多关键字文件。

评价一个文件组织的效率，是执行文件操作所花费的时间和文件组织所需的存储空间。

检索功能的多寡和速度的快慢，是衡量文件操作质量的重要标志。

顺序文件是指按记录进入文件的先后顺序存放、其逻辑顺序和物理顺序一致的文件。主关键字有序称顺序有序文件，否则称顺序无序文件。

一切存储在顺序存储器（如磁带）上的文件都只能顺序文件，只能按顺序查找法存取。

顺序文件的插入、删除和修改只能通过复制整个文件实现。

索引文件的组织方式：通常是在主文件之外建立一张索引表指明逻辑记录和物理记录之间一一对应的关系，它和主文件一起构成索引文件。

索引非顺序文件中的索引表为稠密索引。索引顺序文件中的索引表为稀疏索引。

若记录很大使得索引表也很大时，可对索引表再建立索引，称为查找表。是一种静态索引。

索引顺序文件常用的有两种：

·ISAM索引顺序存取方法：是专为磁盘存取文件设计的，采用静态索引结构。

·VSAM虚拟存储存取方法：采用B+树作为动态索引结构，由索引集、顺序集、数据集组成。

散列文件是利用散列存储方式组织的文件，亦称为直接存取文件。

散列文件

·优点是：文件随机存放，记录不需要排序；插入删除方便；存取速度快；不需要索引区，节省存储空间。

·缺点是：不能进行顺序存取，只能按关键字随机存取，且询问方式限地简单询问，需要重新组织文件。

多重表文件：对需要查询的次关键字建立相应的索引，对相同次关键字的记录建一个链表并将链表头指针、长度、次关键字作为索引表的索引项。

倒排表：次关键字索引表称倒排表，主文件和倒排表构成倒排文件。

数据结构导论串讲笔记

一、考试题型及分数分布情况：

1、选择题：共15小题，每小题2分，共30分。

2、填空题：共13小题，每小题2分，共26分。

选择题和填空题涵盖全书八章的内容，大部分章2道题，个别章1道题。主要是考试大纲中要求“识记”和“领会”的内容，注重对基础知识的考核。

3、应用题：共6小题，每小题5分，共30分。

主要是考试大纲要求“简单应用”的内容。全书可以以应用题的方式出考题的知识点共17类，在后面的讲解中，我将给大家详细讲解。

4、算法设计题：共2小题，每小题7分，共14分。

主要是考试大纲中要求“综合应用”的内容。考核点主要集中在第2章的有关单链表的算法、第4章的二叉树遍历的有关算法和第8章的排序的相关算法。

二、学习建议：

1、在听每一章的串讲之前，认真阅读教材相关内容。原因在于串讲语速快，考点堆积，需要对课程内容的熟知。

2、在听完每一章的串讲之后，要做参考书上该章的“同步训练”及历年考试真题涉及本章的题目。（建议考生看一下机械工业出版社2005年5月出版的《数据结构导论学习辅导与真题解析》）。

3、全书可以以应用题的方式出考题的17类知识点（放一本小书，内容是附件：十七类可能出应用题的考点.doc），每一个考点都要搜集整理出一道典型的题目及题目的解答。

4、考生要尽量多搜集第2章的有关单链表的算法、第4章的二叉树遍历的有关算法和第8章的排序的相关算法，多分析多写，做好充分准备。

5、最后做几套模拟试题，注意严格按正式考试进行，积累应对考试的经验。

自考数据结构导论20051年10月试卷

全国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 页）

全国自学考试数据结构导论试题及答案(4套)

全国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={，，，，,，，,，}，则图G的拓扑序列是 ( ) A.V1,V3,V4,V6,V2,V5,V7 B.V1,V3,V2,V6,V4,V5,V7 C.V1,V3,V4,V5,V2,V6,V7 D.V1,V2,V5,V3,V4,V6,V7 4.有关图中路径的定义，表述正确的是( ) A.路径是顶点和相邻顶点偶对构成的边所形成的序列 B.路径是不同顶点所形成的序列 C.路径是不同边所形成的序列 D.路径是不同顶点和不同边所形成的集合 5.串的长度是指( ) A.串中所含不同字母的个数 B.串中所含字符的个数 C.串中所含不同字符的个数 D.串中所含非空格字符的个数 6.组成数据的基本单位是( ) A.数据项 B.数据类型 C.数据元素 D.数据变量 7.程序段 i=n；x=0； do{x=x+5*i；i--；}while （i>0）； 的时间复杂度为( ) A.O（1） B.O（n） C.O（n2） D.O(n3) 8.与串的逻辑结构不同的 ．．．数据结构是( ) A.线性表 B.栈 C.队列 D.树

数据结构导论试题和部分答案

全国2012年1月数据结构导论试题课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 1.结点按逻辑关系依次排列形成一条“锁链”的数据结构是( )A.集合 B.线性结构 C.树形结构 D.图状结 构 2.下面算法程序段的时间复杂度为( ) for ( int i=0; i

数据结构导论年月试题

二00一年下半年全国高等教育自学考试 数据结构导论试卷 一、单项选择题 1.若给定有n个元素的向量,则建立一个有序单向链表的时间复杂性的量级是( ) A.O(1) B.O(n) C.O(n2) D.O(nlog2n) 2.在一个具有n个结点的单链表达中查找值为m的某结点,若查找成功，则平均比较（） A．n B.n/2 C.(n-1)/2 D.(n+1)/2 3．研究数据结构就是研究（） A.数据的逻辑结构 B.数据的存储结构 C.数据的逻辑结构和存储结构 D.数据的逻辑结构,存储结构及其数据在运算上的实现 4.为了方便地对图状结构的数据进行存取操作，则其数据存储结构宜采用（）方式。 A、顺序存储 B、链式存储 C、索引存储 D、散列存储 5．二维数组A[10……20，5……10]采用行序为主序方式存储，每个数据元素占4个存储单元，且A[10，5]的存储地址是1000，则A[18，9]的地址是（） A、1208 B、1212 C、1368 D、1364 6．设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树中共有（）个结点。 A、13 B、12 C、26 D、25 7．下列几种结构中属于树型结构的是（） 8．设无向图G=（V、E）和G’=（V’，E’），如G’为G的生成树，则下面不正确的说法是（） A、G’为G的连通分量 B、G’为G的无环子图 C、G’为G的子图 D、G’为G的极小连通子图且V’=V 9．下列说法中不正确的是（） A、无向图的极大连通子图称为连通分量 B、连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C、图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D、有向图的遍历不可采用广度优先搜索方法 10．对有序表（18，20，25，34，48，62，74，85）用二分查找法查找85，所需的比较次数为（） A、1次 B、2次 C、3次 D、4次 11．散列表的平均查找长度（） A、与处理冲突方法有关而与表的长度无关 B、与处理冲突方法无关而与表的长度有关 C、与处理冲突方法有关且与表的长度有关 D、与处理冲突方法无关且与表的长度无关 12．对ISAM文件的删除记录时，一般（） A、只需做删除标志 B、需移动记录 C、需改变指针 D、一旦删除就需做整理 13．顺序文件适宜于（） A、直接存取 B、成批处理 C、按关键字存取 D、随机存取 14．一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用（）方法。 A、快速排序 B、堆排序 C、插入排序 D、二路归并排序

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

数据结构导论复习 第一章概论 1．数据：凡能被计算机存储、加工处理的对象。 2．数据元素：是数据的基本单位，在程序中作为一个整体而加以考虑和处理 3．数据项：又叫字段或域，它是数据的不可分割的最小标识单位。 4．逻辑结构需要注意的几点： ①逻辑结构与数据元素本身的内容无关 ②逻辑结构与数据元素相对位置无关 ③逻辑结构与所有结点的个数无关 5．数据元素间逻辑关系是指数据元素之间的关联方式或称“领接关系”。 6．四类基本逻辑结构（集合、线性结构、树形结构和图形结构）的不同特点？ 答：集合中任何两个结点之间都没有逻辑关系，组织形式松散； 线性结构中结点按逻辑关系依次排列形成一条“锁链”； 树形结构具有分支、层次特性，其形态有点像自然界中的树； 图状结构最复杂，其中的各个结点按逻辑关系互相缠绕，任何两个结点都可以领接。 7．运算是在逻辑结构层次上对处理功能的抽象

8．基本运算的含义？ 答：假如是S上的一些运算的集合，是的一个子集，使得中每一运算都可以“归约”为中的一个或多个运算，而中任一运算不可归约为别的运算，则称中运算为基本运算 9．数据结构是指由一个逻辑结构S和S上的一个基本运算集构成的整体（S ，）。 10．数据结构涉及数据表示和数据处理两个方面 11．存储结构的含义和四种基本存储方式的基本思想？ 答：存储结构是指按照逻辑结构的要求建立的数据的机内表示称为存储结构。 一个存储结构应包含三个主要的部分：存储结点、机内表示和附加设施。 存储结构包括四种存储方式，顺序存储方式、链式存储方式、索引存储方式和散列存储方式。 12．运算实现与运算的联系与区别？ 答：运算指的是数据在逻辑结构S上的某种操作，运算只描述处理功能，不包括处理步骤和方法；而运算实现是指一个完成该运算功能的程序，运算实现的核心是处理步骤的规定，即算法设计。 13．算法的概念和分类？ 答：算法是指规定了求解给定类型问题所需的所有“处理步骤”及其执行顺序，使得给定类型的任何问题能在有限时间内被

自考数据结构导论

全国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 )

02142数据结构导论2010年1 月份真题及答案

2010年1月高等教育自学考试全国统一命题考试 数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下述文件中适合于磁带存储的是（） A.顺序文件 B.索引文件 C.散列文件 D.多关键字文件 2.某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为（） A.acbed B.becab C.deabc D.cedba 3.含有n个结点的二叉树用二叉链表表示时，空指针域个数为( ) A.n-1 B.n C.n+1 D.n+2 4.在一个图中，所有顶点的度数之和与图的边数的比是( ) A.1∶2 B.1∶1 C.2∶1 D.4∶1 5.长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为( ) A.O(1) B.O(1og2n) C.O(n) D.O(n2) 6.下述几种排序方法中，要求内存量最大的是( ) A.插入排序 B.快速排序 C.归并排序 D.选择排序 7.对n个不同值进行冒泡排序，在元素无序的情况下比较的次数为( ) A.n-1 B.n C.n+1 D.n(n-1)／2 8.对线性表进行二分查找时，要求线性表必须( ) A.以顺序方式存储 B.以链式方式存储 C.以顺序方式存储，且结点按关键字有序排列 D.以链接方式存储，且结点按关键字有序排列

9.在表长为n的顺序表上做删除运算，其平均时间复杂度为( ) A.O(1) B.O(n) C.O(nlog2n) D.O(n2) 10.当利用大小为n的数组顺序存储一个队列时，该队列的最大容量为( ) A.n-2 B.n-1 C.n D.n+1 11.有关插入排序的叙述，错误的 ．．．是( ) A.插入排序在最坏情况下需要O(n2)时间 B.插入排序在最佳情况可在O(n)时间内完成 C.插入排序平均需要O(nlog2n)时间 D.插入排序的空间复杂度为O(1) 12.有关树的叙述正确的是( ) A.每一个内部结点至少有一个兄弟 B.每一个叶结点均有父结点 C.有的树没有子树 D.每个树至少有一个根结点与一个叶结点。 13.循环队列存储在数组元素A[0]至A[m]中，则入队时的操作为( ) A.rear=rear+1 B.rear=(rear+1)％(m-1) C.rear=(rear+1)％m D.rear=(rear+1)％(m+1) 14.关于串的的叙述，不正确 ．．．的是( ) A.串是字符的有限序列 B.空串是由空格构成的串 C.替换是串的一种重要运算 D.串既可以采用顺序存储，也可以采用链式存储 15.对称矩阵A[N][N]，A[1][1]为首元素，将下三角(包括对角线)元素以行优先顺序存储到一维数组元素T[1]至T[N(N+1)／2]中，则任一上三角元素A[i][j]存于T[k]中，下标k为( ) A.i(i-1)／2+j B.j(j-1)／2+i C.i(j-i)／2+1 D.j(i-1)／2+l 二、填空题(本大题共13小题，每小题2分，共26分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16.下列程序段的时间复杂度为____________。 for(i=1；i<=n；i++) for(j=1；j<=n；j++)

《数据结构导论》考纲、试题、答案

《数据结构导论》考纲、试题、答案 一、考试说明 本课程为闭卷考试（开卷考试、上交论文、上交作品等考查类课程无考试指导）（根据课程考核实际方式选择），考试时间90分钟，考试题型包括以下题型中的三种（根据每门课程的实际确定题型及分值所占比例）： 1、判断题（正确打√，错误打×，每题3分，共15分） 2、填空（每空2分，共20分） 3、选择题（每题3分，共15分） 4、名词解释（每小题4分，共20分） 5、简答题（每题6分，共30分） 备注：以上题型供参考 二、课程知识要点 第一章 ◆数据结构 ◆实例 第二章 ◆银行排队顺序存储 ◆学生健康登记表 第三章 ◆栈和队列 ◆回文 ◆杨辉三角 第四章 ◆串 ◆文本加密 第五章 ◆内部排序 ◆查找

◆二叉树 第六章 ◆树 ◆图 ◆数组 第七章 ◆文件 ◆外部排序 备注：根据教材实际章节汇总要点，突出需要掌握的重点内容 三、重点习题 1、判断题 ◆具有n 个结点的线索二叉树上，含有n+1个线索。 ◆三叉链表属于二叉树存储结构。 ◆哈夫曼树不存在度为1的结点。 ◆栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 ◆栈和队列的存储方式既可是顺序方式，也可是链接方式。 ◆二叉树中每个结点的两棵子树是有序的。 2、填空 ◆数据的逻辑结构指 ◆一个算法的时间复杂度 ◆单链表中，增加头结点的目的 ◆表长为0的线性表 ◆串的长度 ◆若两个串的长度相等且对应位置上的字符也相等 ◆常用的插入排序 ◆常用的处理冲突的方法 ◆常用的选择排序方法 ◆衡量一个算法的优劣主要考虑 ◆在有n个结点的二叉链表中，空链域的个数 ◆常用的选择排序方法

全国数据结构导论10月高等教育自学考试试题与答案

全国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)

2010年1月自考数据结构导论真题

全国2010年1月自学考试数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下述文件中适合于磁带存储的是（） A.顺序文件 B.索引文件 C.散列文件 D.多关键字文件 2.某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为（） A.acbed B.becab C.deabc D.cedba 3.含有n个结点的二叉树用二叉链表表示时，空指针域个数为( ) A.n-1 B.n C.n+1 D.n+2 4.在一个图中，所有顶点的度数之和与图的边数的比是( ) A.1∶2 B.1∶1 C.2∶1 D.4∶1 5.长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为( ) A.O(1) B.O(1og2n) C.O(n) D.O(n2) 6.下述几种排序方法中，要求内存量最大的是( ) A.插入排序 B.快速排序 C.归并排序 D.选择排序 7.对n个不同值进行冒泡排序，在元素无序的情况下比较的次数为( ) A.n-1 B.n C.n+1 D.n(n-1)／2 8.对线性表进行二分查找时，要求线性表必须( ) A.以顺序方式存储 B.以链式方式存储 C.以顺序方式存储，且结点按关键字有序排列 D.以链接方式存储，且结点按关键字有序排列 9.在表长为n的顺序表上做删除运算，其平均时间复杂度为( ) A.O(1) B.O(n)

C.O(nlog2n) D.O(n2) 10.当利用大小为n的数组顺序存储一个队列时，该队列的最大容量为( ) A.n-2 B.n-1 C.n D.n+1 11.有关插入排序的叙述，错误的 ．．．是( ) A.插入排序在最坏情况下需要O(n2)时间 B.插入排序在最佳情况可在O(n)时间内完成 C.插入排序平均需要O(nlog2n)时间 D.插入排序的空间复杂度为O(1) 12.有关树的叙述正确的是( ) A.每一个内部结点至少有一个兄弟 B.每一个叶结点均有父结点 C.有的树没有子树 D.每个树至少有一个根结点与一个叶结点。 13.循环队列存储在数组元素A[0]至A[m]中，则入队时的操作为( ) A.rear=rear+1 B.rear=(rear+1)％(m-1) C.rear=(rear+1)％m D.rear=(rear+1)％(m+1) 14.关于串的的叙述，不正确 ．．．的是( ) A.串是字符的有限序列 B.空串是由空格构成的串 C.替换是串的一种重要运算 D.串既可以采用顺序存储，也可以采用链式存储 15.对称矩阵A[N][N]，A[1][1]为首元素，将下三角(包括对角线)元素以行优先顺序存储到一维数组元素T[1]至T[N(N+1)／2]中，则任一上三角元素A[i][j]存于T[k]中，下标k为( ) A.i(i-1)／2+j B.j(j-1)／2+i C.i(j-i)／2+1 D.j(i-1)／2+l 二、填空题(本大题共13小题，每小题2分，共26分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16.下列程序段的时间复杂度为____________。 for(i=1；i<=n；i++) for(j=1；j<=n；j++) for(k=1；k<=n；k++) s=i+j+k； 17.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为____________。

自考数据结构导论试题真题

全国 2004年 1 月高等教育自学考试 数据 结构导论试题 课程代码： 02142 、单项选择题（本大题共 15 小题，每小题 2 分，共 30 分） 在每小题列出的四个备选项中只有一个是符合题目要求的， 请将其代码填写在题后的 括号内。错选、多选或未选均无分。 1．下列数据组织形式中， （ ）的各个结点可以任意邻接。 A ．集合 B ．树形结构 C ．线性结构 D ．图状结构 2．设某二维数组 A[ 1..n ，1..n]，则在该数组中用顺序查找法查找一个元素的时间复杂 性的量级为（ ） A ．O （log 2n ） B ． O （n ） 2 C ．O （nlog 2n ） D ．O （n 2） 3．在线性表的下列存储结构中，读取元素花费时间最少的是（ A ．单链表 B ．双链表 C ．循环链表 D ．顺序表 4．将一个头指针为 p 的单链表中的元素按与原单链表相反的次序存放，则下列算法段 中的空白处应为 q=NULL; while (p!=NULL) { ( D ． 5．数组通常具有两种基本运算， 即（ A ．创建和删除 C ．读和写 6．除根结点外，树上每个结点（ A ．可有任意多个孩子、任意多个双亲 B ．可有任意多个孩子、一个双亲 C ．可有一个孩子、任意多个双亲 D ．只有一个孩子、一个双亲 p=q; r=q; q=p; p=p -> next; q -> next=r; q=p; r=q; p=p -> next; q -> next=r; r=q; p=p -> next; q=p; q A ． B ． C ． ） B ．索引和修改

7．具有 100 个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、 右孩子，其余（）个指针域为空。 9．如果无向图 G 必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是（） A．G 肯定不是完全图B．G 一定不是连通图 C．G 中一定有回路D． G 有 2 个连通分量 10．若构造一棵具有 n 个结点的二叉排序树，最坏的情况下其深度不会超过（ ）A ． n/2 C．（n+1）/2 D． n+1 11．若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值 的前面，下次的查找区间为从原开始位置至（） B．该中间位置－ 1 D ．该中间位置／ 2 ） B．索引存取 D．直接存取 13．若检索顺序文件各个记录的概率相同，设文件占用的页块数为n，则按关键字存取 时的平均访问外存次数为 （ ） A ．n/2 B ．n C ．n/4 D ． log n 1 4 ．下列关键码序列 中， 属于堆的是 （ ） A ．（15，30，22，93，52 ， 71) B ． （15 ， 71 ， 30 ， 22 ， 93 ， 52) C（15，52，22，3071) D（933052221571) 15．已知 10 个数据元素为（ 54，28， 16，34，73， 62，95，60，26，43），对该数列按从小到大排序，经过一趟冒泡排序后的序列为（） A16283454736260264395 B ．28 ， 16 ， 34 ， 54 ， 62 ， 73 ， 60 ， 26 ， 43 ， 95 C ．28 ， 16 ， 34 ， 54 ， 62 ， 60 ， 73 ， 26 ， 43 ， 95 D ．16 ， 28 ， 34 ， 54 ， 62 ， 60 ， 73 ， 26 ， 43 ， 95 A ． 50 C．100 8．邻接表是图的一种（ A ．顺序存储结构C．索引存储结构 B． 99 D．101 ） B．链式存储结构 B．n A ．该中间位置 C ．该中间位置＋ 1 12．散列文件不能（ A ．随机存取 C．按关键字存取

2020年10月全国数据结构导论自考试题及答案解析.doc

??????????????????????精品自学考料推荐?????????????????? 全国 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

自考02142《数据结构导论》串讲笔记

第一张概论 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）称为一个数据结构。数据结构包括逻辑结构和处理方式。

02142数据结构导论份真题及答案.doc

2012年10月高等教育自学考试全国统一命题考试 数据结构导论试题 课程代码：02142 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的。错选、多选或未选均无分。 1.下面几种算法时间复杂度阶数中，值最大的是 A.O(nlog2n) B.O(n2) C.O(n) D.O(2n) 2.即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果，这种算法好坏的评价因素称为 A.正确性 B.易读性 C.健壮性 D.时空性 3.设顺序表的长度为100，则在第40个元素之后插入一个元素所需移动元素的个数为 A.40 B.60 C.61 D.100 4.设带头结点的单循环链表的头指针为head，则判断该链表是否为空的条件是 A. head->next==head B. head->next==NULL C. head!=NULL D. head==NULL 5.在链栈的运算中，不需要 ．．．判断栈是否为空的是 A.出栈 B.进栈 C.取栈顶元素 D.求链栈的元素个数 6.一个队列的输入序列是A，B，C，D，则该队列的输出序列是 A.A，B，C，D B.B，C，D，A C.D，C，B，A D.C，D，B，A 7.以行序为主序的二维数组a［3］［5］中，第一个元素a［0］［0］的存储地址是100，每个元素占2个存储单元，则a［1］［2］的存储地址是 A.100 B.108 C.114 D.116 8.对任何一棵二叉树T，若叶结点数为5个，则度为2的结点个数为 A.4 B.5 C.6 D.无法确定 9.m个叶结点的哈夫曼树中，其结点总数为 A.m B.2m+1

自考数据结构导论20120年01月试卷

全国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 页

自考02142《数据结构导论》串讲笔记

： 第一张概论 引言 两项基本任务：数据表示，数据处理 软件系统生存期：软件计划，需求分析，软件设计，软件编码，软件测试，软件维护 由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立，选择和实现是数据结构的核心问题。 机外表示------逻辑结构------存储结构 ~ 处理要求-----基本运算和运算-------算法 数据，逻辑结构和运算 数据：凡是能够被计算机存储，加工的对象通称为数据 数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理。又称元素，顶点，结点，记录。 数据项：数据项组成数据元素，但通常不具有完整确定的实际意义，或不被当做一个整体对待。又称字段或域，是数据不可分割的最小标示单位。 — 1.2.2 数据的逻辑结构 逻辑关系：是指数据元素之间的关联方式，又称“邻接关系” 逻辑结构:数据元素之间逻辑关系的整体称为逻辑结构。即数据的组织形式。 四种基本逻辑结构： 1 集合：任何两个结点间没有逻辑关系，组织形式松散 2 线性结构：结点按逻辑关系依次排列成一条“锁链” 3 树形结构：具有分支，层次特性，形态像自然界中的树 { 4. 图状结构：各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接。 注意点: 1.逻辑结构与数据元素本身的形式，内容无关。 2.逻辑结构与数据元素的相对位置无关 3.逻辑结构与所含结点个数无关。 运算：运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。 。 加工型运算：改变了原逻辑结构的“值”，如结点个数，结点内容等。 引用型运算:不改变原逻辑结构个数和值，只从中提取某些信息作为运算的结果。 引用：查找，读取 加工：插入，删除，更新 同一逻辑结构S上的两个运算A和B, A的实现需要或可以利用B，而B的实现不需要利用A，则称A可以归约为B。

浙江省1月自学考试数据结构导论试题及答案解析

浙江省2018年1月自学考试数据结构导论试题 课程代码：02142 一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号 内。每小题1分，共14分) 1.计算机算法指的是( )。 A.计算方法 B.排序方法 C.解决某一问题的有限运算序列 D.调度方法 2.在一个单链表中，若p↑结点不是最后结点，在p↑之后插入s↑结点，则实行( )。 A. s↑.next:=p；p↑.next=s; B. s↑.next:=p↑.next;p↑.next:=s； C. s↑.next:=p↑.next;p:=s; D. p↑.next:=s;s↑.next=p; 3.某个向量第一元素的存储地址为100，每个元素的长度为2，则第五个元素的地址是( )。 A.110 B.108 C.100 D.120 4.循环队列用数组A［0..m-1］存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素 个数是( )。 A.(rear-front+m) MOD m B.rear-front+1 C.rear-front-1 D.rear-front 5.栈和队列的共同特点是( )。 A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素 D.没有共同点 6.深度为n的二叉树中所含叶子结点的个数最多为( )个。 A.2n B.n C.2n-1 D.2n-1 7.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 8.下面的二叉树中，( )不是完全二叉树。 9.下列说法错误的是( )。

数据结构导论

数据结构导论const maxsize=顺序表的容量； typedf struct {datatype data[maxsize]; int last; {sqlist; sqlist L; 顺序表的插入算法： void insert_sqlist(sqlist L,datetype x,int i) { if(https://www.wendangku.net/doc/bd14491363.html,st==maxsize)error(…表潢?)； if((i<1)||(i>https://www.wendangku.net/doc/bd14491363.html,st+1))error(…非法位置?)； for(j=https://www.wendangku.net/doc/bd14491363.html,st;j=i;j--) L.data[j]=L.data[j-1]; L.data[i-1]=X; https://www.wendangku.net/doc/bd14491363.html,st=https://www.wendangku.net/doc/bd14491363.html,st+1 } 顺序表的删除算法： void delete_sqlist(sqlist L,int i); { if((i<1)||(i>https://www.wendangku.net/doc/bd14491363.html,st)) error(非法位置)； for(j=i+1;j=https://www.wendangku.net/doc/bd14491363.html,st;j++) L.data[j-2]=L.data[j-1]; https://www.wendangku.net/doc/bd14491363.html,st=https://www.wendangku.net/doc/bd14491363.html,st-1 } 顺序表的查找算法： int locate_sqlist(sqlist L,datatype X) { i=1; while((i<=https://www.wendangku.net/doc/bd14491363.html,st)&&(L.data[i-1]!=x)) i++; if(i<=https://www.wendangku.net/doc/bd14491363.html,st) return(i) else return(0) } 单链表类型定义 typedef struct node *pointer; struct node {datatype data; pointer next; }; typedef pointer lklist;