0907《数据结构》2018年6月期末考试指导

0907《数据结构》2018年6月期末考试指导

一、考试说明

本课程为闭卷考试，满分100分，考试时间90分钟。考试题型如下： 1、选择题（每题4分，共10题） 2、填空题（每题4 分，共5题） 3、主观题（40分）

二、复习重点内容

第一章 绪论 1、数据

数据是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 2、数据元素和数据对象

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 3、数据的逻辑结构和存储结构

数据之间的相互关系称为逻辑结构。通常分为集合、线性结构、树型结构、图状结构或网状结构四类基本结构

数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。 4、数据结构的二元组表示

数据结构的形式定义为，数据结构是一个二元组： Data-Structure=(D，S)

其中：D是数据元素的有限集，S是D上关系的有限集。 5、算法的特性

算法具有以下五个特性：

（1）有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 （2）确定性：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。

（3）可行性：一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。

（4）输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。 （5）输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。 第二章 线性表

1、线性链表基本概念

结点：数据元素及直接后继的存储位置（地址）组成一个数据元素的存储结构，称为一个结点；

结点的数据域 ：结点中用于保存数据元素的部分；

结点的指针域 ：结点中用于保存数据元素直接后继存储地址的部分； 空指针：不指向任何结点，线性链表最后一个结点的指针通常是指针。

头指针：用于存放线性链表中第一个结点的存储地址。假设L为链表的头指针，它指向表中第一个结点，若L为“空”（L=NULL），则所表示的线性链表为“空”表，其长度n为“零”。

1

头结点：线性链表的第一元素结点前面的一个附加结点，称为头结点。 2、线性表的顺序存储结构

把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。

假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第I+1个数据元素的存储位置LOC( a i+1)和第i个数据元素的存储位置LOC(a I )之间满足下列关系： LOC(a i+1)=LOC(a i)+l

线性表的第i个数据元素ai的存储位置为： LOC(ai)=LOC(a1)+(I-1)*l

由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。 3、线性链表

链表是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构： （data, next）

其中：data域是数据域，用来存放结点的值。next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起的。由于上述链表的每一个结只有一个链域，故将这种链表称为单链表（Single Linked)。 第三章 栈和队列

1、栈的定义及基本运算

栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。

假设栈S=(a1，a2，a3，?an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，?an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的，只能在栈顶插入和删除元素。因此，栈称为后进先出表（LIFO）。 2、队列的定义及基本运算

队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。

先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,?an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,?an ，也就是说队列的修改是依先进先出的原则进行的。 第四章 串 1、串定义

串(String)是零个或多个字符组成的有限序列。一般记作S=“a1a2a3?an”，其中S 是串名，双引号括起来的字符序列是串值；ai(1≦i≦n)可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。长度为零的串称为空串(Empty String)，它不包含任何字符。通常将仅由一个或多个空格组成的串称为空白串(Blank String)。 要注意空串和空白串的不同，例如“ ”和“”分别表示长度为1的空白串和长度为0的空串。 第五章 数组和广义表

2

1、 数组的顺序存储方式

数组通常有两种顺序存储方式：

⑴行优先顺序——将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维的m*n数组为例，按行优先顺序存储的线性序列为： a(0,0),a(0,1),…,a(0,n-1),a(1,0),a(1,1),…a(1,n-1),……,a(m-1,0),a(m-1,1),…,a(m-1,n-1) 在PASCAL、C语言中，数组就是按行优先顺序存储的。

⑵列优先顺序——将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，A的m*n个元素按列优先顺序存储的线性序列为：

a(0,0),a(1,0),?,a(m-1,0),a(0,1),a(1,1),?a(m-1,1),??,a(0,n-1),a(1,n-1),?,a(m-1,n-1) 在FORTRAN语言中，数组就是按列优先顺序存储的。 2、 对称矩阵

在一个n阶方阵A中，若元素满足下述性质： ai j=aj i 0≦i,j≦n-1 则称A为对称矩阵。

对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。

(1).若i≧j，则ai j在下三角形中。ai j之前的i行（从第0行到第i-1行）一共有1+2+?+i=i(i+1)/2个元素，在第i行上，ai j之前恰有j个元素（即ai0,ai1,ai2,?,aij-1），因此有：

k=i*(i+1)/2+j 0≦k

(2).若i

k=j*(j+1)/2+i 0≦ k

二叉树是由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。

这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。二查树不是树的特殊情况，它们是两个概念。 2、树的存储结构 (1). 双亲表示法

在树中，除根结点没有双亲外，其他每个结点的双亲是唯一确定的。 (2). 孩子表示法

采用孩子表示法表示一棵树时，树中每个结点除了存储其自身的值之外，还必须指出其所有子女的位置。 (3). 孩子兄弟表示法

所谓孩子兄弟表示法，即在存储树中每个结点时，除了包含该结点值域外，还设置两个指针域firstchild和rightsibling，分别指向该结点的第一个子女和其右兄弟，即以二叉链表方式加以存储，因此该方法也常被称为二叉树表示法。 3、遍历二叉树

在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径巡访树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。二叉树的遍历顺序包括：先序遍历、中序遍历和后序遍历。 (1).先序遍历二叉树的操作定义为：

3