自考02331数据结构重点总结(最终修订)

【2331】数据结构考试要点概论- 基本概念和术语（一）数据（Data）数据是信息的载体。

它能够被计算机识别、存储和加工处理，是计算机程序加工的"原料"。

随着计算机应用领域的扩大，数据的范畴包括：整数、实数、字符串、图像和声音等。

数据元素（Data Element）数据元素是数据的基本单位。

数据元素也称元素、结点、顶点、记录。

一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。

数据项是具有独立含义的最小标识单位。

数据结构（Data Structure）数据结构指的是数据之间的相互关系，即数据的组织形式。

1．数据结构一般包括以下三方面内容：①数据元素之间的逻辑关系，也称数据的逻辑结构（Logical Structure）；数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。

数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

②数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（Storage Structure）；数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。

对机器语言而言，存储结构是具体的。

一般，只在高级语言的层次上讨论存储结构。

③数据的运算，即对数据施加的操作。

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

最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。

所谓抽象的操作，是指我们只知道这些操作是"做什么"，而无须考虑"如何做"。

只有确定了存储结构之后，才考虑如何具体实现这些运算。

为了增加对数据结构的感性认识，下面举例来说明有关数据结构的概念。

【例1．1】学生成绩表，见下表。

注意：在表中指出数据元素、数据项、开始结点和终端结点等概念（1）逻辑结构表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、各科成绩及平均成绩等数据项组成。

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

数据元素是数据的基本单位，可以由若干个数据项组成。

数据项是具有独立含义的最小标识单位。

数据结构的定义：逻辑结构：从逻辑结构上描述数据，独立于计算机。

线性结构：一对一关系。

线性结构：多对多关系。

存储结构：是逻辑结构用计算机语言的实现。

顺序存储结构：如数组。

链式存储结构：如链表。

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

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

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

数据运算。

对数据的操作。

定义在逻辑结构上，每种逻辑结构都有一个运算集合。

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

数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。

原子类型：由语言提供。

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

抽象数据类型ADT:是抽象数据的组织和与之的操作。

相当于在概念层上描述问题。

优点是将数据和操作封装在一起实现了信息隐藏。

程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。

算法取决于数据结构。

算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。

评价算法的好坏的因素：算法是正确的；执行算法的时间；执行算法的存储空间（主要是辅助存储空间）；算法易于理解、编码、调试。

时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。

渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。

评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。

算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。

时间复杂度按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n〃2)、立方阶O(n”)、……k次方阶O(n”)、指数阶O(2M)。

空间复杂度：是某个算法的空间耗费，它是该算法所求解问题规模n的函数。

算法的时间复杂度和空间复杂度合称算法复杂度。

return ;
}
if ( L -> length >= ListSize ){
printf (" overflow ");
return ;
}
for ( j - L -> length -1; j >= i -1; j --)
L ->data [ j +1]= L -> data [ j ]; //从最后一个元素开始逐一后移
线性表的基本运算
上述运算仅仅是线性表的基本运算，不是其全部运 算。因为对不同问题的线性表，所需要的运算可能不同。 因此，对于实际问题中涉及其他更为复杂的运算，可用 基本运算的组合来实现。
线性表的基本运算
【例2.1】假设有两个线性表 LA 和 LB 分别表示两个 集合 A 和 B ，现要求一个新集合 A = A∪B 。
线性表的逻辑定义
数据元素“一个接一个的排列”的关系叫做 线性关系，线性关系的特点是“一对一”，在计 算机领域用“线性表”来描述这种关系。另外， 在一个线性表中数据元素的类型是相同的，或者 说线性表是由同一类型的数据元素构成的，如学 生情况信息表是一个线性表，表中数据元素的类 型为学生类型；一个字符串也是一个线性表：表 中数据元素的类型为字符型等等。
,
a2
i
,…,
ai-1
,
a．aii++1．1 , ．…,
an
)
an
线性表n的-1逻辑结an构和存储结构都发…生了相应的变化， 与插入运算相反，插…入是向后移动元素，而删除运算则
是向前移M动AX元-1 素，除非i=n 时直接删除终端元素，不需移
动元素。
删除前
删除后

数据结构知识点总结数据结构知识点总结：一、数据结构概述数据结构定义及分类●线性结构●非线性结构●数组●链表●栈●队列●树●图●散列表二、线性结构⒈数组●定义●数组的操作：插入、删除、查找、更新●二维数组⒉链表●定义●特点●单链表●双链表●循环链表●链表的操作：插入、删除、查找、更新⒊栈●定义●特点●栈的顺序存储结构●栈的链式存储结构●栈的应用⒋队列●特点●队列的顺序存储结构●队列的链式存储结构●队列的应用三、非线性结构⒈树●定义●结点●树的类型：二叉树，多叉树，满二叉树，完全二叉树●二叉树的存储结构：顺序存储，链式存储●二叉树的遍历：先序遍历，中序遍历，后序遍历●二叉树的应用：赫夫曼树，二叉搜索树⒉图●定义●图的存储结构：邻接矩阵，邻接表●图的遍历：深度优先搜索，广度优先搜索●最短路径算法四、散列表（哈希表）●定义●散列函数●冲突解决方法：拉链法，开放地质法附件：无法律名词及注释：⒈数据结构：指在计算机科学中，数据组织、管理和存储的方式。

⒉线性结构：数据元素之间存在一对一关系的结构。

⒊非线性结构：数据元素之间存在一对多或多对多关系的结构。

⒋数组：一种线性结构，由相同数据类型的元素组成，通过下标进行访问。

⒌链表：一种线性结构，由一系列结点构成，每个结点中包含数据和指向下一个结点的指针。

⒍栈：一种特殊的线性结构，只能在一端进行插入和删除操作的数据结构。

⒎队列：一种特殊的线性结构，只能在一端进行插入操作，在另一端进行删除操作的数据结构。

⒏树：一种非线性结构，由结点和边组成，每个结点可以有多个子结点。

⒐图：一种非线性结构，由一组顶点和一组边组成，顶点之间可以有多种关系。

⒑散列表：一种根据关键字直接访问数据的数据结构，通过散列函数将关键字映射到相应的存储位置。

数据结构必考知识点总结在准备考试时，了解数据结构的基本概念和相关算法是非常重要的。

以下是一些数据结构的必考知识点总结：1. 基本概念数据结构的基本概念是非常重要的，包括数据、数据元素、数据项、数据对象、数据类型、抽象数据类型等的概念。

了解这些概念有助于更好地理解数据结构的本质和作用。

2. 线性表线性表是数据结构中最基本的一种，它包括顺序表和链表两种实现方式。

顺序表是将数据元素存放在一块连续的存储空间内，而链表是将数据元素存放在若干个节点中，每个节点包含数据和指向下一个节点的指针。

了解线性表的概念和基本操作是非常重要的。

3. 栈和队列栈和队列是两种特殊的线性表，它们分别具有后进先出和先进先出的特性。

栈和队列的实现方式有多种，包括数组和链表。

掌握栈和队列的基本操作和应用是数据结构的基本内容之一。

4. 树结构树是一种非线性的数据结构，它包括二叉树、多路树、二叉搜索树等多种形式。

了解树的基本定义和遍历算法是必考的知识点。

5. 图结构图是一种非线性的数据结构，它包括有向图和无向图两种形式。

了解图的基本概念和相关算法是非常重要的，包括图的存储方式、遍历算法、最短路径算法等。

6. 排序算法排序是一个非常重要的算法问题，掌握各种排序算法的原理和实现方式是必不可少的。

常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序等。

7. 查找算法查找是另一个重要的算法问题，包括顺序查找、二分查找、哈希查找、树查找等。

了解各种查找算法的原理和实现方式是必考的知识点之一。

8. 算法复杂度分析算法的时间复杂度和空间复杂度是评价算法性能的重要指标，掌握复杂度分析的方法和技巧是非常重要的。

9. 抽象数据类型ADT是数据结构的一种概念模型，它包括数据的定义和基本操作的描述。

了解ADT的概念和实现方式是非常重要的。

10. 动态存储管理动态存储管理是数据结构中一个重要的问题，包括内存分配、内存释放、内存回收等。

了解动态存储管理的基本原理和实现方式是必考的知识点之一。

星形测针的校正
测头的测力和测针的长度
测力影响测量精度 选择适合测针长度的测头，注意测力和测针长度（重量）的协调。 自动更换测针组的校正必须成组校正
测针长度与触发角度
测量元素的分析
单击此处添加文本具体内容
PART.02
元素的测针半径补偿
点的半径补偿方向，以坐标系的轴向和测头回退方向为准。
测量元素的分析
测针校正的方法
量块、环规、球 测头校正有多种方法：可以利用量块、环规进行测量，改变测针直径直到测量出准确结果。 最好的校正是使用标准球，既可以测准直径，又可以得出测针的位置关系。
为什么测针的等效直径小于名义值
只有接触后才能触发。 触发后的计数锁存的时间。 测量机停止时惯性。 测针变形。 测针越长，等效直径越小。 校正测针的速度要与测量速度一致。
面、线的测头补偿。 圆、圆柱、圆锥的半径补偿。 曲线、曲面的半径补偿。 测量误差和测点的数量
测量元素的分析
测量距离 小平面的距离。 测孔还是测圆柱。
坐标系
单击此处添加文本具体内容
PART.03
测量公差（如：位置度）的需要。 程序测量的需要。 准确测量的需要。 辅助测量。
零件坐标系
为什么建零件坐标系
几个难题
小圆弧
小于1/4圆，会出现很大的测量误差，分辨力、重复性原因。增加测量点。 改变方法，测量轮廓。 拟合的方法。（根据具体情况，探讨）
拟合法测量小圆弧
几个难题
同轴度
基准与被测的关系。 测量方法的限制。 按照实际使用的情况处理。
同轴度测量
窄平面的平行和垂直度 窄平面对矢量方向影响大的因素。 输入参考长度的选择。 转换测面为测线。
回转体零件坐标系
单击此处添加正文，文字是您思想的提炼，为了演示发布的良好效果，请言简意赅地阐述您的观点。您的内容已经简明扼要，字字珠玑，但信息却千丝万缕、错综复杂，需要用更多的文字来表述；但请您尽可能提炼思想的精髓，否则容易造成观者的阅读压力，适得其反。

自考02331数据结构重点总结(最终修订)第一章概论1.瑞士计算机科学家沃思提出：算法+数据结构=程序。

算法是对数据运算的描述，而数据结构包括逻辑结构和存储结构。

由此可见，程序设计的实质是针对实际问题选择一种好的数据结构和设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。

2.数据是信息的载体。

数据元素是数据的基本单位。

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

数据对象是具有相同性质的数据元素的集合。

3.数据结构指的是数据元素之间的相互关系，即数据的组织形式。

数据结构一般包括以下三方面内容：数据的逻辑结构、数据的存储结构、数据的运算①数据的逻辑结构是从逻辑关系上描述数据，与数据元素的存储结构无关，是独立于计算机的。

数据的逻辑结构分类:线性结构和非线性结构。

线性表是一个典型的线性结构。

栈、队列、串等都是线性结构。

数组、广义表、树和图等数据结构都是非线性结构。

②数据元素及其关系在计算机内的存储方式，称为数据的存储结构（物理结构）。

数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。

③数据的运算。

最常用的检索、插入、删除、更新、排序等。

4.数据的四种基本存储方法:顺序存储、链接存储、索引存储、散列存储（1）顺序存储：通常借助程序设计语言的数组描述。

（2）链接存储：通常借助于程序语言的指针来描述。

（3）索引存储：索引表由若干索引项组成。

关键字是能唯一标识一个元素的一个或多个数据项的组合。

（4）散列存储：该方法的基本思想是：根据元素的关键字直接计算出该元素的存储地址。

5.算法必须满足5个准则：输入，0个或多个数据作为输入；输出，产生一个或多个输出；有穷性，算法执行有限步后结束；确定性，每一条指令的含义都明确；可行性，算法是可行的。

算法与程序的区别：程序必须依赖于计算机程序语言，而一个算法可用自然语言、计算机程序语言、数学语言或约定的符号语言来描述。

02331数据结构一、单选题1.下列程序段的时间复杂度为( D )s=0；for(i=1；i<n ；i++)for(j=1；j<n ；j++)s+=i*j ；A.O(1)B.O(n)C.O(2n)D.O(n 2)2.假设某个带头结点的单链表的头指针为head ，则判定该表为空表的条件是( B )A.head==NULL ；B.head->next==NULL ；C.head!=NULL ；D.head->next==head ；3.栈是一种操作受限的线性结构，其操作的主要特征是( B )A.先进先出B.后进先出C.进优于出D.出优于进4.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front 和rear 。

若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为( B )A.(rear-front-1)％nB.(rear-front)％nC.(front-rear+1)％nD.(rear-front+n)％n5.判断两个串大小的基本准则是( D )52A.两个串长度的大小B.两个串中首字符的大小C.两个串中大写字母的多少D.对应的第一个不等字符的大小6.二维数组A[4][5]按行优先顺序存储，若每个元素占2个存储单元，且第一个元素A[0][0]的存储地址为1000，则数组元素A[3][2]的存储地址为( C )A.1012B.1017C.1034D.10367.高度为5的完全二叉树中含有的结点数至少为( A )A.16B.17C.31D.328.已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为( C )A.5B.8C.11D.189.下列关键字序列中，构成大根堆的是( D )A.5，8，1，3，9，6，2，7B.9，8，1，7，5，6，2，33C.9，8，6，3，5，l ，2，7D.9，8，6，7，5，1，2，310.对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为( B )A.1539B.1549C.1551D.155512.估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的 ( A )。

自考02331数据结构真题及答案(2009-2018)自考02331数据结构真题及答案(2009-2018)数据结构是计算机科学与技术领域中的一门基础课程，通过研究数据的组织、存储和管理方式，以及不同数据结构之间的相互关系和运算方法，提高算法效率和问题解决能力。

在自考02331数据结构课程中，真题及其答案对于学生来说是很重要的复习资料。

本文将提供自考02331数据结构真题及答案的综合整理，希望对广大自考学子的备考有所帮助。

一、2009年自考02331数据结构真题及答案1. (1) 数据除了数值外还可以是什么类型的？答：数据除了数值类型外还可以是字符型、字符串型、布尔型等。

(2) 数据的逻辑结构和物理结构分别指什么？答：数据的逻辑结构指数据之间的关系及其运算规律，如线性结构、树形结构、图形结构等；数据的物理结构指数据在计算机内存中的存储方式，如顺序存储、链式存储等。

2. 用C语言编写一个递归函数，计算n的阶乘。

答：以下是一个计算n的阶乘的递归函数的C语言代码：```cint factorial(int n) {if(n == 0 || n == 1) {return 1;}return n * factorial(n-1);}```二、2018年自考02331数据结构真题及答案1. 请给出二叉树的定义，并用C语言实现二叉树的结点结构。

答：二叉树是一种特殊的树结构，每个结点最多有两个子结点。

以下是用C语言实现二叉树结点结构的代码：```ctypedef struct BinaryNode {int data; // 结点存储的数据struct BinaryNode* left; // 左子结点指针struct BinaryNode* right; // 右子结点指针} BinaryNode;```2. 请解释线性表的顺序存储和链式存储，并分别给出其对应的存储结构。

答：线性表是一种数据元素之间存在一对一关系的数据结构。

02331数据结构《02331 数据结构》在当今数字化的时代，数据结构作为计算机科学中的重要基石，对于解决各种实际问题起着至关重要的作用。

02331 数据结构这一特定的课程或者领域，涵盖了丰富而深入的知识体系，让我们一同来探索它的奥秘。

数据结构是什么？简单来说，它是组织和存储数据的方式，以便于能够高效地访问、操作和管理这些数据。

就好比我们整理自己的房间，如果东西随意堆放，找起来会非常麻烦，但如果我们把书籍放在书架上，衣服放进衣柜，杂物放进抽屉，那么就能迅速找到我们需要的东西。

在计算机中，数据结构就是为了让数据的存储和操作变得有序和高效。

在02331 数据结构中，常见的数据结构包括数组、链表、栈、队列、树和图等。

数组是一种最简单也最常见的数据结构。

它就像一排连续的格子，每个格子都有固定的位置和编号。

优点是可以通过索引快速访问元素，但缺点是插入和删除元素比较麻烦，因为可能需要移动大量的数据。

链表则与数组不同，它的元素不是连续存储的，每个元素都包含了指向下一个元素的指针。

这使得链表在插入和删除元素时非常方便，只需要修改指针的指向即可，但访问特定位置的元素就需要从头开始遍历。

栈和队列是两种特殊的线性结构。

栈遵循“后进先出”的原则，就像往一个桶里放东西，最后放进去的会最先被拿出来。

而队列则是“先进先出”，就像排队买票，先到的先买。

树是一种分层的数据结构，其中最常见的是二叉树。

二叉树的每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉搜索树则是一种特殊的二叉树，它的左子树中的节点值都小于根节点的值，右子树中的节点值都大于根节点的值。

这使得在二叉搜索树中查找、插入和删除元素的效率很高。

图是一种更为复杂的数据结构，用于表示对象之间的关系。

图由顶点和边组成，边可以有权重，表示顶点之间的连接强度或距离。

学习 02331 数据结构，不仅仅是了解这些数据结构的定义和特点，更重要的是要学会如何在实际问题中选择合适的数据结构。

自考数据结构重点(珍藏版)自考数据结构重点(珍藏版)一、介绍数据结构是计算机科学中非常重要的概念，它涉及到组织、管理和存储数据的方法。

掌握数据结构的核心概念对于程序设计和算法的实现至关重要。

本文将介绍自考数据结构课程的重点内容，帮助您更好地理解和应用这些知识。

二、线性表1. 数组数组是最简单的一种数据结构，它是一种线性表的结构，其中的元素按照一定顺序排列。

我们可以通过数组下标来访问和修改对应位置的元素。

2. 链表链表是另一种常用的线性表结构，它由一系列节点组成。

每个节点包含数据和指向下一个节点的指针。

链表的优点是插入和删除操作的效率较高，但访问任意位置的元素需要遍历整个链表。

三、栈和队列1. 栈栈是一种具有后进先出（LIFO）特点的数据结构，主要包含入栈和出栈两种操作。

入栈将元素压入栈顶，出栈将栈顶元素移除。

2. 队列队列是一种具有先进先出（FIFO）特点的数据结构，主要包含入队和出队两种操作。

入队将元素插入队尾，出队将队头元素移除。

四、树树是一种自然且常用的数据结构，它具有层次结构和分支结构的特点。

1. 二叉树二叉树是树结构中最简单且常见的一种形式。

每个节点最多有两个子节点，分别是左子节点和右子节点。

2. 二叉搜索树二叉搜索树是一种特殊的二叉树，它的左子树中的值都小于根节点，右子树中的值都大于根节点。

这个特点使得二叉搜索树在查找和插入操作上有较高的效率。

五、图图是一种非线性的数据结构，它由节点和边组成。

图的节点可以表示不同的实体，边表示节点之间的联系。

1. 有向图和无向图有向图中的边有方向性，而无向图中的边没有方向性。

2. 最短路径算法最短路径算法用于计算两个节点之间的最短路径长度。

常见的最短路径算法包括迪杰斯特拉算法和弗洛伊德算法。

六、排序算法排序算法用于将一组数据按照特定顺序进行排列。

1. 冒泡排序冒泡排序通过交换相邻的元素来进行排序。

它重复地遍历数列，每次比较相邻的两个元素，将较大的元素移动到后面。

数据结构考试重点必背在数据结构考试中，掌握并熟练运用一些重点概念和知识点是非常关键的。

这些重点知识点不仅能够帮助我们对数据结构的基本概念有深入的理解，还能够在解决实际的编程问题中发挥重要作用。

本文将详细介绍数据结构考试中的一些重点知识点，供大家参考。

一、线性表1. 线性表的定义和基本操作：线性表是由n个数据元素构成的有限序列，其中n为表的长度。

基本操作包括插入、删除、查找等。

2. 顺序存储结构与链式存储结构：顺序存储结构使用数组实现，查找效率高；链式存储结构使用链表实现，插入删除效率高。

3. 单链表、双链表与循环链表：单链表每个节点只有一个指针指向下一个节点，双链表每个节点有两个指针分别指向前一个和下一个节点，循环链表将尾节点的指针指向头节点。

二、栈和队列1. 栈的定义和基本操作：栈是一种特殊的线性表，只允许在一端进行插入和删除操作，称为栈顶。

基本操作包括入栈和出栈。

2. 栈的应用：括号匹配、四则运算表达式求值、迷宫求解等。

3. 队列的定义和基本操作：队列是一种特殊的线性表，采用先进先出的原则。

基本操作包括入队和出队。

4. 队列的应用：生产者消费者问题、打印任务调度等。

三、树与二叉树1. 树的定义和基本概念：树是n（n >= 0）个节点的有限集合，其中存在唯一的根节点，其余节点构成m个互不相交的子集，每个集合本身又可以看作一棵树。

2. 二叉树的基本概念：二叉树是一种特殊的树结构，每个节点最多有两个子节点，分别为左子节点和右子节点。

3. 二叉树的遍历方式：前序遍历、中序遍历和后序遍历。

遍历过程分别为先遍历根节点、先遍历左子树再遍历右子树、先遍历右子树再遍历左子树。

四、图1. 图的定义和基本概念：图是由节点和边组成的一种数据结构，用于描述事物之间的关系。

节点表示事物，边表示事物之间的联系。

2. 图的分类：无向图、有向图、带权图等。

3. 图的遍历方式：深度优先遍历和广度优先遍历。

深度优先遍历使用栈实现，广度优先遍历使用队列实现。

10月自考数据结构02331试题及答案解析10月自考数据结构02331试题及答案解析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+13．栈采用不同的存储方式时，下列关于出栈过程的叙述中，正确的是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开始按行优先连续存放，则元素a[8][5]的起始地址是A．SA+141 B．SA+144 C．SA+222 D．SA+2556．广义表A=(x，((y)，((a))，A))的深度是A．2 B．3 C．4 D．∞7．一棵左子树为空的二叉树在前序线索化后，其空指针域个数为A．0 B．1 C．2 D．不确定8．下列关于哈夫曼树的叙述中，错误的是A．用n个结点构造的哈夫曼树是唯一的B．哈夫曼树中只有度为0或度为2的结点C．树中两个权值最小的结点可能是兄弟结点D．同一结点集构造的二叉树中，哈夫曼树的WPL最小9．6个顶点的强连通图中，含有的边数至少是A．4 B．5 C．6 D．710．对题l0图进行深度优先搜索遍历，下列选项中，正确的遍历序列是12．有向图采用邻接矩阵存储，某一行中非零元素的个数等于A．对应顶点v的度B．对应顶点v的出度C．对应顶点v的入度D．依附于对应顶点v的边数13．下列选项中，符合堆定义的是A．{102，24，55，60，89，93}B．{24，89，55，60，93，102}C．{102，93，55，60，89，24}D．{102，60。

第1章概论(一) 课程内容1.1 引言1.2 数据、逻辑结构和运算1.3存储实现和运算实现(二) 学习的目的与要求本章集中介绍贯穿和应用与数据结构课程始终的基本概念和主要工具，概括反映了后继各章的基本问题，为进入具体内容的学习提供了必要的引导。

本章总的要求是：理解数据、数据元素和数据项的概念及其相互关系；理解逻辑结构、基本运算和数据结构的概念、意义和分类；理解存储结构与逻辑结构的关系；了解机内表示的级别和四种基本存储方式；理解算法的概念；了解算法分析的基本概念、时间复杂性及其量级的概念。

本章重点是逻辑结构和数据结构的概念。

难点是算法的时间复杂性分析。

第2章线性表(一) 课程内容2.1 线性表的基本慨念2.2 线性表的顺序实现2.3 线性表的链实现2.4 其它运算在单链表上的实现2.5 其它链表2.6 顺序实现与链接实现的比较2.7 串(二) 学习的目的与要求顺序表和单链表分别是最简单、基本的顺序存储结构和链式存储结构。

顺序表和单链表上实现基本运算的算法是数据结构中最简单、基本的算法。

这些内容构成以下各章的重要基础，因此本章是本课程的重点之一。

维持对本章有较高的要求：深刻理解线性结构的定义和特点；理解线性表的概念；熟练掌握顺序表和单链表的组织方法及实现基本运算的算法；掌握在顺序表和单链表上进行算法设计的基本技能；了解顺序表与链表的优缺点；了解串的概念、运算和存储方法。

本章重点：线性结构的定义和特点；线性表的运算；顺序表和单链表的组织方法和算法设计。

难点：单链表上的算法设计。

第3章栈、队列和数组(一) 课程内容3.1 栈3.2 队列3.3 数组3.4 综合应用示例栈和队列的逻辑结构与线性表的逻辑结构相同，二维数组逻辑结构可以看成是线性结构的推广；而它们的运算都可以看成是线性表运算的限制。

本章总的要求是：理解栈和队列的定义、特点及与线性表的异同；熟悉顺序栈和链栈的组织方法，队满、队空的判断条件及其描述；掌握链队的组织方法、算法并能自行设计其它简单算法。

1、二叉树并非是树的特殊情形，它们是两种不同的数据结构。

2、在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序。

而在二叉树中，即使是一个孩子也有左右之分。

3、在直接插入排序中，每次取出的未排序数字是从后往前依次比较的。

如：对于记录(54,38,96,23,15,72,60,45,83)，当把第7个记录60插入时，需比较3 次。

解：前6个已排序好记录15,23,38,54,72,96，所以从后往前要比较96,72和54。

在快速排序中，前后的i和j是从后面的j开始比较的，比较者不动，被替换者后(前)移如：对于记录(51,22,83,46,75,18,68,30)解：第一趟划分：哨兵R[0]=i=51,先从j=30比较，30<51,30替换51，i=22，i≯51，后移i=83,83>51,83替换30，j=68，依次继续。

冒泡排序中，最好与最坏时间复杂度不相同。

无论待排序列是否有序(即不受数据初始状态影响)，时间复杂度都是O(n2)的排序算法是直接选择排序。

记录关键字比较次数与记录的初始排列次序无关的是直接选择排序。

在待排序的记录关键字序列基本有序的前提下，效率最高的排序方法是直接插入排序，效率最低的是快速排序。

2013.1.23对同一个基本有序的待排序序列分别进行堆排序、快速排序和冒泡排序，最省时间的是4、对于哈夫曼编码，应该先构造哈夫曼树：每次取权值最小的两个结点(包含新生成的结点)放一起生成新结点。

至于左右孩子之分，按照编码字出现的先后顺序去决定(还是左小右大)。

关于哈夫曼树的一些解释：哈夫曼树不唯一，和你左右子树的编码有关。

但最小带权路径长度唯一。

你记住每次都是从集合中寻找两个最小元素，权值相加之后形成的那个元素得重新放入集合参与新的比较。

递归下去生成的树才没有问题，否则弄不好就是一个单枝树上去了。

你最好采取我建议的规则，自己设置一个优先级。

自考《数据结构》各章要点一第一章概论数据就是指能够被计算机识别、存储和加工处理的信息的载体。

数据元素是数据的基本单位，可以由若干个数据项组成。

数据项是具有独立含义的最小标识单位。

数据结构的定义：·逻辑结构：从逻辑结构上描述数据，独立于计算机。

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

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

·存储结构：是逻辑结构用计算机语言的实现。

·顺序存储结构：如数组。

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

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

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

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

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

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

·数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。

·原子类型：由语言提供。

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

抽象数据类型ADT：·是抽象数据的组织和与之的操作。

相当于在概念层上描述问题。

·优点是将数据和操作封装在一起实现了信息隐藏。

程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。

算法取决于数据结构。

算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。

评价算法的好坏的因素：·算法是正确的；·执行算法的时间；·执行算法的存储空间(主要是辅助存储空间)；·算法易于理解、编码、调试。

时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。

渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。

评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。

算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。

时间复杂度按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、……k次方阶O(n^k)、指数阶O(2^n)。

第1章概论1.数据结构的作用、意义、基本概念和术语，要求达到“识记”层次。

1.1数据结构所研究的内容；在计算机科学中的作用和意义；Wirth关于程序的定义公式。

1.2数据、数据元素、数据对象、数据项、数据结构等概念的定义。

1.3数据的逻辑结构、存储结构及数据运算的含义及其相互关系。

1.4数据结构的两大类逻辑结构和四种常用的存储表示方法。

2.算法的描述和分析，要求达到“领会”层次。

2.1算法、算法的时间复杂度和空间复杂度等概念。

2.2一个完整算法需要满足的五个准则；算法与程序的关系。

2.3算法的分析方法；对于一般算法能分析其时间复杂度。

第2章线性表1.线性表的逻辑结构，要求达到“识记”层次。

1.1线性表的逻辑定义和性质。

1.2线性表上定义的基本运算。

2.线性表的顺序存储结构和基本运算，要求达到“领会”层次。

2.1顺序表的定义及特点。

2.2顺序表上进行插入和删除操作的实现及时间性能分析。

2.3理解求顺序表逆置和极值及定位两种算法的实现过程。

3.线性表链式存储结构的不同形式及基本运算，要求达到“领会”层次。

3.1单链表、循环链表、双向链表的定义及特点。

3.2单链表上实现建表、查找、插入和删除等基本算法，并分析其时间复杂度。

3.3用尾指针表示单循环链表的意义。

3.4双向链表上的插入和删除操作。

4.利用顺序表和链表设计算法解决应用问题，要求达到“综合应用”层次。

5.顺序表和链表的比较，要求达到“领会”层次。

第3章栈和队列1.栈的逻辑结构、存储结构及相关算法，要求达到“简单应用”层次。

1.1栈的逻辑定义、特点及运算。

1.2顺序栈和链栈上实现进栈、退栈等基本运算。

1.3顺序栈的上溢和下溢问题，如何防止溢出。

2.队列的逻辑结构、存储结构及相关算法，要求达到“简单应用”层次。

2.1队列的逻辑定义、特点及运算。

2.2顺序循环队列的表述；队空和队满的判定；顺序循环队列上入队、出队等基本算法。

2.3链队列的表述；带头结点和不带头结点两种情况下链队列上的基本算法。