数据结构考试重点.docx

数据结构考试重点.docx

《数据结构考试重点.docx》由会员分享，可在线阅读，更多相关《数据结构考试重点.docx（9页珍藏版）》请在冰点文库上搜索。

数据结构考试重点

数据结构

第一章绪论

1、数据结构的定义：

按照某种逻辑关系组织起来的数据集、数据与数据间的逻辑关系在计算机存储器中的存储形式以及定义在数据集上的一组操作与操作的实现这三个方面统称为数据结构。

2、数据主要分为两大类：

数值型数据和非数值类型数据。

数值型数据主要包括整数、实数和复数等；非数值类型数据包括字符、字符串、文字、声音、图形、图像等。

3、数据结构的逻辑结构是指数据元素的集合以及定义在该集合上的数据元素之间的一种或多种特定关系。

4、数据结构的逻辑结构是根据解决问题的功能目标而建立的；

数据结构的存储结构是根据解决问题的性能要求而建立的。

5、数据类型是一个具体相同性质的值的集合以及定义在该集合上的一组操作的总称。

数据类型定义了数据的性质、取值范围以及对数据所能进行的一组操作。

6、根据数据元素之间逻辑关系的不同特性，可将数据结构分为：

集合、线性机构、树形结构和图状结构。

7、一个非空的线性结构的逻辑特点：

1.只有一个数据元素没有前驱，称其为“第一个”元素；2.只有一个数据元素没有后继，称其为“最后一个”元素；3.除第一个元素外，其余数据元素有且只有一个前驱；4.除最后一个元素外，其余数据元素有且只有一个后继。

8、算法是指为解决一个问题而采用的方法和步骤；

9、算法的五个特性：

1.有穷性：

算法必须在有限步骤及有限时间内终止，并计算出结果；2.确定性：

算法的每一个操作步骤都有确切的含义，即无二义性；3.算法的每一个操作步骤，都是有效的、可行的；4.输入：

一个算法有零个或多个输入，这些输入取自于某个特定对象的集合；5.输出：

一个算法必须有一个或多个输出。

算法的目的是为了求解，通过算法所求得的“解”即是算法的输出。

注意，计算机算法的输出不一定就是计算机显示或打印输出，一个算法得到的结果实际就是算法的输出。

第二章线性表

10、线性表是一种最基本而且应用最广泛的数据结构，其特点是结构中的各数据元素之间存在着一对一的关系，是一种最典型的线性结构。

11、线性表是具有相同特性的数据元素的一个有限序列。

12、线性表中的数据元素在位置上是有序的，相邻的元素之间存在着序偶关系。

13、顺序表的顺序存储结构是指把线性表中所有数据元素，按照其逻辑顺序依次存储到计算机存储器中从指定位置开始的一块连续的存储空间中，数据元素间的存储（物理）位置即表示了它的逻辑位置。

14、顺序表基本操作的实现：

1.初始化操作；2.求长度操作；3.判空操作；4.清空操作；5.取元素操作；6.按值查找操作；7.插入操作；8.删除操作。

15、算法的空间效率是指算法在计算机上运行时所需存储空间的大小。

算法的空间复杂度用大O记法表示为：

S（n）=O（f（n））

随着问题规模n的增大，算法运行时所需辅助存储空间的增长率的数量级为f（n）。

若算法运行时所占的存储空间与问题规模无关，是个常量，则称这种算法为原地工作，其空间复杂度用O

（1）表示。

16、顺序表的优缺点：

优点：

a.实现方法简单，各种高级语言中都有数组，容易实现；

b.访问元素的速度快，因为在顺序表中逻辑上相邻的两个元素在存储位置上也必定相邻，所以只要知道了第一个元素的地址，其他任何一个元素的地址都可通过简单的计算求得，故可实现随机存取，即顺序表L的第i个元素即为L.base[i-1]。

缺点：

a.需占用连续的存储区，存储要求高，不能利用小块存储区；

b.由于在顺序表中逻辑上相邻的两个元素在存储位置上也必定相邻，所以在进行插入和删除操作时，需要进行大量的元素移动操作，影响了算法效率。

17、通常把使用链式存储结构来实现的线性表称为链表。

18、线性表的链式存储结构是用一组任意的存储单元来存放线性表中的数据元素，这组存储单元既可以是连续的，也可以是不连续的，甚至可以零散分布在内存中的任意位置上。

19、链表的相关概念：

1.首元结点，指链表中用于存储线性表的第一各数据元素的结点；2.头结点，在链表中为了便于进行插入和删除等操作，为链表增设一个辅助结点，称该辅助结点为链表的头结点。

头结点在链表中可有可无；3.头指针，是指向链表中第一个结点的指针，可以唯一地表示一个链表；4.空指针，当链表中某个结点的指针域为空时，称该结点的指针域为空指针。

20、链表的表长是指链表中存放数据元素的结点数目。

21、链表分为单链表、双向链表和循环链表。

22、单链表的建立操作：

1.头插法建立单链表：

在单链表的建立过程中，总是将由读入元素所生成的结点插入到链表的表首端，即插入时始终将新生成结点作为第1个结点插入。

2.尾插法建立单链表：

与头插法正好相反，在单链表的建立过程中，其每次都是将所生成的新结点插入到单链表尾端，即在插入时始终是新生成结点作为最后一个结点插入。

23、链表的优缺点：

优点：

a.能充分利用内存中的小块存储区；

b.便于进行插入和删除操作，在进行插入和删除操作时不需要进行元素的移动，只需修改相应结点的指针域即可。

缺点：

a.与顺序表相比，其实现方法较复杂，特别在对双链表进行操作时不仅要考虑向后指向的“链”，还需考虑向前指向的“链”；

b.无法像顺序表那样实现随机存取，在链表中要找某个结点只能从表头开始向后寻找；

c.在链表的每个结点需要附加存储关系信息（指针域），因此当问题规模较小且基本一定时，链表所需存储空间比顺序表多。

第三章栈与队列

24、栈的定义：

栈是一种将插入操作与删除操作限制在同一段进行的特殊线性表。

在这个特殊的线性表中，进行插入与删除操作的一端称为栈顶（Top），另一端则称为栈底（Bottom）。

也就是说栈的插入操作与删除操作均在栈顶端进行，其中，插入操作称为入栈操作（Push），删除操作称为出栈操作（Pop）。

不含任何元素的栈称为空栈。

25、栈具有后进先出或者说为先进后出的特性，故栈又称为后进先出表或先进后出表。

26、栈的基本操作：

初始化、销毁、判空、清空、入栈、出栈、取栈顶、求栈长及遍历。

27、经试探可行则行进，不可行则返回重新试探的方法称为回溯法。

28、一个概念、函数等对象用自己来定义自己，则称该对象为递归定义的。

在程序设计语言中，一个算法直接或间接调用自己，则称该算法为递归算法。

29、递归法则：

1.基准情形法则。

递归定义中的基准情形即递归出口，它本身不再使用递归定义，是递归的结束条件；2.不断推进法则。

不断推进法则是指在递归求解过程中，每一次递归调用都必须使求解状况朝接近基准情形的方向推进。

30、队列是一种插入操作限制在一端进行而删除操作限制在另一端进行的特殊线性表。

在这个特殊的线性表中进行插入操作的一端成为队尾，进行删除操作的一端称为队头。

在队列尾端进行的插入操作称为入队操作，而在队列头端进行的删除操作称为出队操作。

不含任何元素的队列称为空队。

31、队列具有先进先出或者说后进后出的重要特性，故队列又称为先进先出表或后进后出表。

第四章串

32、串的定义：

串是由零个或多个任意字符组成的有限序列，一般记作：

S=“s1s2…si…sn”（n≥0）。

其中S是串名，用双引号括起来的字符序列为串值，但引号本身并不属于串的内容，它的作用是为了避免与变量名或数的常量相混淆。

Si（1≤i≤n）称为串的元素，它可以是任意字母、数字或者是其他字符，是构成串的基本单位，i是它在整个串中的序号。

n为串的长度，表示串中所包含的字符个数。

例如，串S1=“abcd”，串的元素为一个字母，其长度为5。

而在串S2=“123456”，串的元素为一个数字，其长度为6。

33、串的静态顺序存储结构利用的是数组的静态分配方式，它是为每个定义的字符串分配一个固定长度的连续存储区域，将字符串中的字符顺序地存放在存储区域的各个单元里。

实质上就是将串定义成字符数组，利用串名可以直接访问串值。

用这种表示方式，串的存储空间在编译时确定，其大小不能改变。

34、串的动态顺序存储结构仍是为每个定义的字符串分配一个连续存储区域，将字符串中的字符顺序地存放在这组存储区域中的各个单元里，只是这个存储区域不是在操作前分配的固定长度的区域，而是在操作过程中根据需要动态分配得到的，即在程序运行时为每个产生的串分配一块实际串长所需的存储空间，若分配成功，则返回指向该存储空间起始地址的指针，作为串的基址。

第五章数组和广义表

35、数组是n个相同数据类型的数据元素a0，a1，…，an-1构成的占用一块地址连续的内存单元的有限序列。

数组中任意一个元素可以用该元素在数组中的位置来表示，数组元素的位置通常称作数组的下标。

36、在大多数语言中采用以行序为主序的存储方式，如C语言、C++语言和Pascal语言；在Fortran等少数语言中采用以列序为主序的存储方式。

37、常见的特殊矩阵：

对称矩阵、三角矩阵和带状矩阵。

对称矩阵：

在一个n阶方阵A中，若元素满足下述兴致：

aij=aji（1≤i，j≤n），则称A为n阶对称矩阵。

三角矩阵：

以主对角线划分，n阶三角矩阵有n阶上三角矩阵和n阶下三角矩阵两种。

n阶上三角矩阵的下三角（不包括主对角线）中的元素均为常数c（或0）。

n阶下三角矩阵正好相反，它的主对角线上方均为常数c（或0）。

带状矩阵：

带状矩阵是指所有非零元素均集中在以对角线为中心的带状区域中的n阶方阵。

38、常见的稀疏矩阵存储方法：

三元组顺序表和十字链表。

39、三元组顺序表：

将表示稀疏矩阵非零元素的三元组按行优先或列优先（一般情况下为行优先）的顺序排列，并以此存储在向量中，这种稀疏矩阵的顺序存储结构称为三元组顺序表。

40、在广义表中，每个结点既可以属于基本数据类型，也可以属于广义表类型。

41、广义表的定义是一个递归定义，它和线性表之间的不同之处在于：

数据元素之间不仅有先后关系，更有元素内部的层次关系。

42、广义表的长度是指表中数据元素的个数，需要注意的是数据元素可能是原子，也可能是子表；

广义表的深度是指表中层次关系的最大深度，即所含括弧的重数，需要注意：

“原子”深度为0，“空表”的深度为1。

43、广义表的特性：

1.广义表是一个多层次的结构。

表中元素可以是子表，子表的元素还可以是子表；2.广义表可为其他广义表所共享。

在实际应用中，利用共享特性可以节约存储空间来；3.广义表可以是一个递归的表。

递归表的深度是无穷值，长度则是有限值。

44、广义表的存储形式：

头尾链表和扩展线性链表。

第六章树

45、树形结构是一种典型的非线性结构，在形状上类似于自然界中倒立的树，所有元素之间具有明显的层次关系和分支关系。

现实生活中，操作系统的文件管理、家族的族谱关系和社会机构的组成等都可以用树形象地表示。

46、树是n（n≥0）个结点的有限集。

若n=0，称为空树；否则，在任何一棵非空树中满足以下条件：

1.有且仅有一个特定的没有前驱的结点称为根结点；2.当n>1时，其余结点可分为m（m>0）个互不相交的有限集合T1，T2，…，Tm。

其中每个集合本身又是一棵树，称为根结点的子树。

47、树的定义具有递归性，即树的定义中还有树。

它刻画了树的固有特性：

一棵非空子树由一个根结点及若干子树构成，而子树又可以由其根结点和若干棵更小的子树构成。

48、树的基本术语：

1.结点的度和树的度；2.孩子、双亲和兄弟；3.结点的层次和树的高度；4.路径和路径长度；5.有序树和无序树；6.森林。

49、树的高度：

空树的高度为0；在非空树中，所有结点的最大层次称为树的高度（或深度）。

50、二叉树的概念：

二叉树是一种重要的树形结构，在计算机领域有着十分广泛的应用。

任何一棵树都可以转换成一个与之对应的二叉树，从而对树的表示与处理便可用二叉树的表示和相关运算来实现。

二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。

其特点是它是一棵有序树，每个结点的度最大为2。

51、满二叉树：

在一棵二叉树中，如果所有分支结点的度均为2，且所有叶子结点在同一层上，则这棵二叉树称为满二叉树。

52、完全二叉树：

对满二叉树从树根为1开始，按照从上到下、每层从左到右的原则对其顺序编号。

满二叉树是完全二叉树的特例。

53、二叉树的性质：

1.在二叉树的第i层上至少有2i-1个结点（i>0）；2.深度为k的二叉树上至多含2k-1个结点（k≥1）；3.对任何一棵非空二叉树，如果它含有n0个叶子结点，n2个度为2的结点，那么：

n0=n2+1；4.具有n个结点的完全二叉树的深度为[log2n]+1;5.对有n个结点的完全二叉树编号后，则对任意一个编号为i的结点：

a.若i=1，则该结点是二叉树的根，无双亲；否则，其双亲结点编号为[i/2]结点;b.若2i>n，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点；c.若2i+1>n，则该结点无右孩子结点，否则，编号为2i+1的结点为其右孩子结点。

54、二叉树的顺序存储结构是用一组地址连续的存储单元来存放二叉树的数据元素。

55、二叉树的链式存储结构：

在链式存储结构中，结点之间的逻辑关系是通过指针实现的。

由于二叉树中每个结点最多有两个孩子结点，所以每个结点结构中，除了数据域data外，还需要设置两个指针域LChild和RChild，分别指向左孩子和右孩子，这种存储结构称为二叉链表。

56、二叉树的二叉链表和三叉链表的特点：

1.它们均由root唯一确定，如二叉树为空，则root=NULL；2.具有n个结点的二叉链表，共有2n个指针域，其中具有n+1个空链域；3.在三叉链表中易于查找某个结点的双亲，而在二叉链表中则需要遍历整棵树才能查找某结点的双亲。

57、二叉树遍历是按照一定的路径访问二叉树中的每个结点，而且每个结点仅被访问一次。

58、DLR:

先序遍历；LDR:

中序遍历；LRD:

后序遍历。

第七章图

59、图是一种比线性表和树更为复杂的非线性结构。

在图中，数据元素间的关系是多对多的，任何两个元素间都可能存在关系，元素之间的关系是任意的。

60、在图中，通常将数据元素称为顶点，而将数据元素之间的关系称为边。

61、图的相关术语：

无向图和有向图；完全图；稀疏图、稠密图、子图；权和网；顶点的度、入度和出度；路径、路径长度、回路、简单路径和简单回路；连通图、连通分量；强连通图、强连通分量；生成树和生成森林。

62、图的邻接矩阵存储方法又称为数组表示法，其方法是用一个一维数组来存储图中顶点的信息，用一个二维数组来存储图中顶点之间的领接关系的信息。

63、图的遍历操作是指从图中的某个顶点出发，按照某种方法对图中的所有顶点进行访问，使每个顶点都被访问且仅被访问一次。

第八章查找

64、为了取得某一条数据，必须扫描某一范围的数据，这个扫描的过程就是查找。

65、关键字是数据元素中某个项或组合项的值，用它可以标识一个数据元素。

能唯一确定一个数据元素的关键字，称为主关键字；

不能唯一确定一个数据元素的关键字，称为次关键字。

66、查找表：

是由具有同一类型（属性）的数据元素所构成的集合，分为静态查找表和动态查找表两类。

静态查找表：

仅对查找表进行查找操作，而不能改变的表的结构；

动态查找表：

仅查找表除进行查找操作外，可能还要向表中插入新的数据元素，或删除表中已存放的数据元素，即可以改变表的结构。

67、二分查找：

二分查找又称折半查找，它是一种效率较高的查找方法。

二分查找要求查找表是有序表，即表中各数据元素按关键字值有序。