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

数据结构导论复习

第一章概论

1．数据：凡能被计算机存储、加工处理的对象。

2．数据元素：是数据的基本单位，在程序中作为一个整体而加以考虑和处理

3．数据项：又叫字段或域，它是数据的不可分割的最小标识单位。

4．逻辑结构需要注意的几点：

①逻辑结构与数据元素本身的内容无关

②逻辑结构与数据元素相对位置无关

③逻辑结构与所有结点的个数无关

5．数据元素间逻辑关系是指数据元素之间的关联方式或称“领接关系”。

6．四类基本逻辑结构（集合、线性结构、树形结构和图形结构）的不同特点？

答：集合中任何两个结点之间都没有逻辑关系，组织形式松散；

线性结构中结点按逻辑关系依次排列形成一条“锁链”；

树形结构具有分支、层次特性，其形态有点像自然界中的树；

图状结构最复杂，其中的各个结点按逻辑关系互相缠绕，任何两个结点都可以领接。

7．运算是在逻辑结构层次上对处理功能的抽象

8．基本运算的含义？

答：假如是S上的一些运算的集合，是的一个子集，使得中每一运算都可以“归约”为中的一个或多个运算，而中任一运算不可归约为别的运算，则称中运算为基本运算

9．数据结构是指由一个逻辑结构S和S上的一个基本运算集构成的整体（S ，）。

10．数据结构涉及数据表示和数据处理两个方面

11．存储结构的含义和四种基本存储方式的基本思想？

答：存储结构是指按照逻辑结构的要求建立的数据的机内表示称为存储结构。

一个存储结构应包含三个主要的部分：存储结点、机内表示和附加设施。

存储结构包括四种存储方式，顺序存储方式、链式存储方式、索引存储方式和散列存储方式。

12．运算实现与运算的联系与区别？

答：运算指的是数据在逻辑结构S上的某种操作，运算只描述处理功能，不包括处理步骤和方法；而运算实现是指一个完成该运算功能的程序，运算实现的核心是处理步骤的规定，即算法设计。

13．算法的概念和分类？

答：算法是指规定了求解给定类型问题所需的所有“处理步骤”及其执行顺序，使得给定类型的任何问题能在有限时间内被

机械地求解。

算法的类型有：运行终止的程序可执行部分、伪语言算法和非形式算法（根据描述算法语言不同）

14．算法在给定输入下的计算量的含义和估算的方法？

答：算法在给定输入下的计算量是指根据该类问题的特点合理地选择一种或几种操作作为“标准操作”，确定每个算法在给定输入下共执行多少次标准操作，并将此次数规定为该算法在给定输入下的计算量。估算的方法有：最坏时间复杂度和平均时间复杂度。

15．最坏情况时间复杂性和平均时间复杂性的概念？

答：最坏情况时间复杂性也称为最坏时间复杂度，是指以算法在所有输入下的计算量的最大值作为算法的计算量；平均情况时间复杂性也称为平均时间复杂度，是指以算法在所有输入下的计算量的加权平均值作为算法的计算量；

16．空间复杂性指的是一个算法除输入数据占存储空间之外所需要的附加存储空间的大小。

17．算法的性质：正确性、易读性、健壮性和高效率。

第二章线性表

1．线性结构：是n（n≥0）个结点的有穷序列。

2．线性结构的基本特征：若至少含有一个结点，则除起始结点没有直接前趋外，其他结点

有且仅有一个直接前趋；除终端节点没有直接后继外，其他结点

有且仅有一个直接后继。

3．线性表的逻辑结构是线性结构

4．线性表的六种基本运算的功能？

答：⑴初始化(L)，功能是建立一个空表

⑵求表长(L)，功能是返回线性表L的长度

⑶读表元(L，i)，功能是返回线性表L的第i个结点

⑷定位（按值查找）(L，X),功能是返回找到的结点集合

中序号的最小值，否则返回值为0（说明没有找到）

⑸插入（L，X，i），功能是在线性表L的地i个位置上

增加一个值为X的新结点（整个表长+1）

⑹删除(L，i)，功能是撤销线性表L的第i个位置结点

（整个表长-1）

5．顺序表表示法的基本思想、特点

答：基本思想是：按照顺序存储方式，顺序表的一个存储结点存储线性表的一个结点的内容，即数据元素，所有存储结点按相应数据元素建的逻辑关系决定的次序依次排列。

特点：逻辑结构中相邻的结点在存储结构中仍相邻。

6．区别顺序表的容量与线性表的表长?

答：顺序表的容量是指定义顺序表时的的值，而线性表的表长是指其中包含的结点个数。

7．顺序表中的地址计算：的地址（1）*l，b是首地址，l是每个结点占的空间

7．掌握顺序表上实现插入、删除和定位运算的三个算法P18-20 8．单链表表示法的基本思想——用指针表示结点间逻辑关系9．单链表的结点形式：

答：由数据域和指针域两部分组成；这两部分各自的作用分别是数据域是用于存储线性表的一个数据元素的，指针域是用于存放一个指针的，该指针指向本结点所含数据元素的直接后继所在的结点。

10．头指针和头结点的作用？

答：头指针是一个指向链表开始结点的指针，单链表由头指针唯一确定；头结点是我们人为地在链表的开始结点之前附加的一个结点，有了头结点之后，头指针指向头结点，不论链表是否为空，头指针总是非空的，而且头指针的设置使得对链表的第一位置上的操作和在其他位置上的操作一致。11．单链表上实现插入、删除和定位三种运算的三个算法：P26-28 12．插入算法中所包含的指针操作：()→→→→;

删除算法中所包含的指针操作：→→→(q);

13．（）的作用：

①生成一个结点

②形式一条指针

14．循环链表的组织方法：将单链表中的尾结点的改成指向头结点的指针，就形成了循环链表。循环链表优点：可以从表中任一结点出发都可以向后扫描整表。

15

刻画双链表结构的对称性的语句：p→→ p→→;

16．顺序表的主要优点和主要缺点：

优点：①无需为表示结点间的逻辑关系而增加额外的存储空间

②可以方便地随机存取表中的任意结点

缺点：①插入和删除运算不方便

②分配内存空间采用静态分配方式

17．链表的主要优点：

①插入和删除运算方便，只需要修改指针，不需要移动结点

②分配内存空间采用动态分配方式

18．字符串：以字符为数据元素，以线性结构为逻辑结构的数据。19．串的逻辑结构（是线性结构）和串的特点（是由0个或多个字符组成的有穷序列）

20．串的基本运算的功能：判等()的功能是两个串的长度要相等，而且对应位置的字符都要相同。

21．串的顺序存储方法（紧缩格式和非紧缩格式）和链接存储方法

第三章栈、队列和数组

1．栈的基本运算及由此而决定的栈的基本特点

栈是一种只允许在栈顶进行插入、删除的特殊线性表；其基本特点是采用“后进先出”操作；

2．栈的基本运算：①初始化（S）②进栈（S，X）③退栈（S）

④读栈顶元素（S）⑤判断栈空（S）3．顺序栈“上溢”、“下溢”的概念

“上溢”：顺序栈在进行进栈时，超过了顺序栈的最大的容量“下溢”：顺序栈在进行退栈时，栈中的元素少于0个元素4．进栈和退栈运算在顺序栈上的实现算法：P44

5．顺序栈上的简单算法（初始化，判栈空，取栈顶元素）6．链栈的结点形式及其描述：

用来存放该结点的数据元素

用来存放指向下一个数据元素

7．链栈上实现进栈和退栈的算法P46

8．链栈上的简单算法（初始化，判栈空，取栈顶元素）

9．队列的基本运算及由此决定的队列的特点

队列是一种只允许在对头进行插入在队尾进行删除的特殊线性表；其基本特点是采用“先进先出”操作；

10．顺序队上的“假溢出”及其解决方法：顺序队在进行多次入队、出队后，顺序队已经满了，但顺序队中的大部分空间是空的；

解决方法：将顺序队改成循环队

11．循环队队满、队空的条件：

判断循环栈满的条件：（（→1））→ 判断循环栈空的条件：→ →

12．链队的结点形式及其链队的组织方法：

13．在链队上实现入队、出队的算法P56-57 14．数组的逻辑结构是线性结构的推广 15．二维数组的基本运算是读与写 16．二维数组：

，其中

a[0][0]是首地址，k 是每个数据元素存储单元。 17．稀疏矩阵的三元组表示法：（）

((1,2,3),(1,6,1),(3,1,5),（3，2，-1），（4，5，4），（5，1，-3）)

第四章 树

1．树的定义：是n （n>0）个结点的有穷集合，满足： ①有且仅有一个称为根的结点

②其余结点分为m （m ≥0）个互不相交的非空集合T1，T2…… ，这些集合中的每一个都是一棵树，称为根的子树。 2．树形结构的有关术语及其含义

front

rear

①根结点

②双亲结点和孩子结点

③兄弟结点和堂兄弟结点

④子孙结点和祖先结点

⑤树的层次、树的高度和树的度

3．二叉树的逻辑结构、特点和五种基本形态

（1）：二叉树是n（n≥0）个结点的有穷集合，满足：

①有且仅有一个称为根的结点

②其余结点分为2个互不相交的集合T1，T2，T1是左子树，

T2是右子树，且T1，T2也都是一棵二叉树。

（2）特点：①二叉树是棵有序树

②二叉树的度≤2

（3）五种基本形态

4．二叉树的基本运算和性质

（1）二叉树的基本运算：

①初始化 ()

②求根 ()

③求双亲()

④求左孩子 () 求右孩子 ()

⑤建树()

⑥剪枝() 和 ()

（2）二叉树的性质：

①第i

层上，最多有

个结点

②深度是K，最多总有是针对普通二叉树

③n02+1

④具有n个结点，深度

是针对完全二叉树

⑤按照从上到下，从左到右的顺序编号，

5．二叉链表的结点形式及其描述，二叉链表中各结点的联系方法及根指针的作用

（1）二叉链表的结点形式

该结点的左孩子的指针，是存放指向该结点的右孩子的指针。（2）根指针的作用，是用来指明根结点。

6．满二叉树和完全二叉树的概念

（1）满二叉树是深度为K的二叉树的总共结点数为

（2）完全二叉树是在满二叉树上少0个或者从最下层的最右边开始少起的二叉树

7．设计二叉树上基于三种遍历的简单算法

8．判定树和哈夫曼树的概念

（1）判断树是用来描述分类过程的二叉树

（2）哈夫曼树是构造带权路径长度最小的二叉树

9.哈夫曼树的特性:

①m个权值构造的哈夫曼树的结点总数为21

②m个权值构造的哈夫曼树后权值都处在叶子结点上

③在哈夫曼树中，权值越大离根越近

④在哈夫曼树中，没有度为1的结点

10.将树转化成二叉树时，得到的二叉树的右子树永远为空

11.在n个结点的二叉链表中，总共有2n个指针，其中，非空指

针数为1，空指针数为1

12. 三叉链表的好处是方便每个结点找其双亲结点

13.讨论树、森林和二叉树的关系目的是想借助二叉树上的运算

方法来实现对树的一些运算

14.

时，必须要有中序序列

15.

附录：树这章可以出的应用题

1.二叉树 二叉链表图

2. 二叉链表图 二叉树

3. 二叉树 操作规则： ①完全化

1 2 3 4 5 6 7 8 9 10 11 12

13

4.顺序存储结构图 二叉树

（是上题中的逆操作）

5. 二叉树写出先序、中序和后序遍历

先序（）

中序（）

后序（）

先序和中序或者先序和后序序列二叉树

（1）先序序列：中序序列：

（2）后序序列：

中序序列：

7.树孩子链表表示法

9.树 双亲表示法

树 二叉树

二叉树 (b)

(c)

自考数据结构导论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 页）

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

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

02142数据结构导论201604

2016年4月高等教育自学考试全国统一命题考试 数据结构导论试卷 (课程代码 02142) 本试卷共6页。满分l00分，考试时间l50分钟。 考生答题注意事项： 1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。3．第二部分为非选择题。必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。4．合理安排答题空间，超出答题区域无效。 第一部分选择题(共30分) 一、单项选择题(本大题共l5小题。每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”的相应代码涂黑。错涂、多涂或未涂均无分。 1．一个公司的组织机构是1名公司经理领导若于名部门负责人、每个部门负责人领导若干名部门员工，则适合于描述该公司组织机构的逻辑结构是 A．线性表 B．队列 C．树 D．图 2．计算n!(整数n≥0)的递归算法是：int Factorial(int n){if(n= =o)return l；else return n*Factorial(n--1)；}其时闯复杂度为 A．0(n) B．0(log2n) C．O(n0) D．O(n2) 3．将一个由指针q指向的结点插在单链表中由指针P所指向的结点之后的操作是 A．p=q； B．p--：>next=q； C．q一>next=p--：>next；p-->next=q； D．p一>next—q；q-->next—p--：>next； 4. 设初始栈为空，s表示人栈操作，x表示出栈操作，则合法的操作序列是 A．sxxssxxs B．ssxsxxxs C．ssxxxssx D．sssxxxsx 5．将递归形式描述的算法改写为功能等价的非递归形式描述的算法，通常应设置的辅助结构是 A．顺序表 B．单链表C．栈 D．队列 6．设长度为n的队列用单循环链表表示(假设表尾结点为当前队列的队尾元素)，若只设头指针，则入队操作、出队操作的时间复杂度分别为 A．O(n)、O(1) B．O(1)、O(1) C．O(1)、O(n) D．0(n)、0(n) 7．若采用顺序存储(一维数组)结构存储一棵如题7图所示的二叉树，根结点1的下标为l，剥结点4的下标为 A．4 B．5 C．6 D．7 8．按层序(自顶向下、从左到右)遍历二叉树时需借助队列作辅助结构。对高度为3的满二叉树进行层序遍历时，队列中所出现的元素个数最多是

全国自学考试数据结构导论试题及答案(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.树

自考数据结构导论

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

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

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

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

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)

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

全国 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数据结构导论份真题及答案.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.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）称为一个数据结构。数据结构包括逻辑结构和处理方式。

浙江省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.下列说法错误的是( )。

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

4《数据结构导论》复习题

数据结构导论模拟试题 一、考试题型及分值分布： 1、单项选择题(本大题共15小题，每小题2分，共30分) 2、填空题(本大题共13小题，每小题2分，共26分) 3、应用题(本大题共5小题，每小题6分，共30分) 4、算法设计题(本大题共2小题，每小题7分，共14分) 二、单项选择题和填空题样题参考 （一）单项选择题 1. 在二维数组中，每个数组元素同时处于（）个向量中. A. 0 B. 1 C. 2 D. n 2. 已知单链表A长度为m，单链表B长度为n，它们分别由表头指针所指向，若将B 整体连接到A的末尾，其时间复杂度应为（）. A. O(1) B. O(m) C. O(n) D. O(m+n) 3. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( ). A. front == rear B. front != NULL C. rear != NULL D. front == NULL 4. 若让元素1,2,3依次进栈，则出栈次序不可能出现( )种情况. A. 3,2,1 B. 2,1,3 C. 3,1,2 D. 1,3,2 5. 图的广度优先搜索类似于树的（）遍历. A. 先根 B. 中根 C. 后根 D. 层次 6. 下面程序段的时间复杂度为( ). for(int i=0; ilink=s; B.s->link=top->link; top->link=s; C. s->link=top; top=s; D. s->link=top; top=top->link; 10. 一棵具有35个结点的完全二叉树的高度为( ).假定空树的高度为-1. A. 5 B. 6 C. 7 D. 8 11. 一个有n个顶点和n条边的无向图一定是( ) 的. A．连通 B．不连通 C．无回路 D．有回路 12. 在一个长度为n的顺序表的任一位置插入一个新元素的时间复杂度为（）. A. O(n) B. O(n/2) C. O(1) D. O(n2) 13. 已知广义表为A((a,b,c),(d,e,f))，从A中取出原子e的运算是（）. A．Tail(Head(A)) B．Head(Tail(A)) C．Head(Tail(Head(Tail(A)))) D．Head(Head(Tail(Tail(A))))

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

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