计算机-数据结构与算法
第一章 数据结构与算法
1.1 算法
1
描述。
算法规定了解决某类问题所需的操作语句以及执行顺序，使其能通过有限的指令语句，在一定时间内解决问题。
算法是一个操作序列、有限长度，目的是解决某类问题。
*：算法不等于程序，也不等于计算方法。程序的编制不可能优于算法的设计。
2、算法的基本特征
（1）可行性。针对实际问题而设计的算法，执行后能够得到满意的结果。
（2）确定性。每一条指令的含义明确，无二义性。并且在任何条件下，算法只有唯一的一条执行路径，即相同的输入只能得出相同的输出。
（3）有穷性。算法必须在有限的时间内完成。有两重含义，一是算法中的操作步骤为有限个，二是每个步骤都能在有限时间内完成。
（4）拥有足够的情报。指的是有足够的输入和输出。
*：综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。
3、算法的基本要素
一个算法通常由两种基本要素组成：一是对数据对象的运算和操作；二是算法的控制结构。
(1）算法中对数据的运算和操作
每个算法实际上市按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。因此，计算机算法就是计算机能处理的操作所组成的指令序列。 在一般的计算机系统中，基本的运算和操作有以下四类：
①算术运算：主要包括加、减、乘、除等运算；
②逻辑运算：主要包括与(AND)、或(OR)、非(NOT)
等运算；
③关系运算：主要包括大于、小于、等于、不等于等运算
④数据传输：主要包括赋值、输入、输出等操作。
(2)算法的控制结构
顺序、选择和循环。
4、算法的基本方法（计算机解题的过程实际上是在实施某种算法）
（1）列举法（列举所有解决方案）
根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。
（2）归纳法（特殊->一般）适合于列举量为无限的情况
通过列举少量的特殊情况，经过分析，最后找出一般的关系。
（3）递推法（已知->未知）
从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。
（4）递归法（逐层分解）
将一个复杂的问题归结为若干个较简单的问题，然后将这些较简单的每一个问题再归结为更简单的问题
（5）减半递推法
“减半”是指将问题的规模减半，而问题的性质不变，所谓“递推”是指重复“减半”的过程。
（6）回溯法
复杂应用，找出解决问题的线索，然后沿着这个线索逐步多次“探”、“试”。
5、算法复杂度主要包括时间复杂度和空间复杂度。
算法的复杂度是衡量算法好坏的量度。
（1）算法时间复杂度是指执行算法所需要的计算工作量，可以用执行算法的过程中所需基本运算的执行次数来度量。
影响计算机工作量的主要因素：
第一：基本运算次数；第二：问题规模。
下面的方法不能用来度量算法的时间复杂度：
第一：算法程序的长度或算法程序中的语句（指令）条数；
第二：算法程序所执行的语句条数；
第三：算法程序执行的具体时间
（2
一个算法所用的内存空间包括： 1）算法程序所占用的存储空间；
2）输入的初始数据所占的存储空间；3）算法执行过程中的额外空间。
6、考题练习：
1）下列叙述正确的是（）
（A）算法就是程序
（B）算法强调的是利用技巧提高程序执行效率
（C）设计算法时只需考虑结果的可靠性
（D）以上三种说法都不对
2）下面叙述正确的是（）
（A）算法的执行效率与数据的存储结构无关
（B）算法的空间复杂度是指算法程序中指令（或语句）的条数
（C）算法的有穷性是指算法必须能在执行有限个步骤之后终止
（D）以上三种描述都不对
3）下列叙述中正确的是（）
（A）一个算法的空间复杂度大，则其时间复杂度也必定大
（B）一个算法空间复杂度大，则其时间复杂度必定小
（C）一个算法的时间复杂度大，则其时间复杂度必定小
（D）以上三种说法都不对
4）算法的空间复杂度是指（）
（A）算法程序中变量的个数
（B）算法程序中的指令条数
（C）算法程序中各控制变量所占的额外空间
（D）算法执行过程中所需要的存储空间
1.2 数据结构的基本概念
1、基本概念：
1）数据：在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。2）数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
3）数据结构：是指相互有关联的数据元素的集合。
线性表
栈
线性结构队列
数据的逻辑结构树形结构
非线性结构
图形结构
顺序存储
数据的存储结构
链式存储
数据的运算：检索、排序、插入、删除、修改
2、逻辑结构：数据元素之间的逻辑关系，从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。
3、存储（物理）结构：是指数据元素及其关系在计算机内存中的表示，即数据的逻辑结构在计算机存储空间中的存放形式。
注意：对于同一个逻辑结构来说，采用不同的存储结构，其数据处理的效率是不同的。因此，在数据处理时，选择合适的存储结构很重要。
各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定相同。
由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系（即前后间关系）在数据结构中，不仅要存放各数据元素的本身，而且还需要存放各数据元素之间的前后件关系的信息。
4、逻辑结构与物理结构的关系：
（1）一种逻辑结构可以用不同的物理结构来实现
（2）逻辑结构决定了算法的设计
（3）物理结构决定了算法的实现
数据结构的图形表示：表示数据结构的常用方法：二元关系表和图形表示。
例：一年四季的数据结构可以表示成：
用图形表示为：
1） 数据元素：用中间标有元素值的方框来表示，称为数据结点，简称为结点。
2） 元素之间的前后关系：用一条有向线段从前件结点指向后件结点（有时可以省略箭头） 例如：家庭成员数据结构可以表示称为：
在数据结构中，没有前件的结点称为根结点，没有后件的结点称为终端结点（也称为叶子结点）其它的称为内部结点。
5、线性结构与非线性结构
数据结构的分类：
根据数据结构中各数据元素之间的前后关系的复杂度，一般将数据结构分成两大类：线性结构和非线性结构。
注意：线性结构与非线性结构是在数据的逻辑结构概念下的一种划分方法，与数据的存储结构无关。前面说过，一种数据的逻辑结构根据需要可以表示成多种存储结构，但只要数据的逻辑结构是属于线性结构，则该逻辑结构的任意一种存储结构也都属于线性结构。
6、线性结构的定义：
如果一个非空的数据结构满足下列两个条件：
（1） 有且只有一个根结点（每有前件的结点称为根结点）
（2） 每个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构，线
性结构又称为线性表。
（3） 线性结构的操作。
在一个线性结构中插入或删除任何一个结点后还应是线性结构。
1.3 线性表及其顺序存储结构
1、线性表就是线性结构。线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。线性表是由n(n ≥0)个数据元素组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件
2、线性表的顺序存储结构也称为顺序表。
3、线性表的顺序存储结构具有两个基本特点：（1）线性表中所有元素所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的，其前后两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。
4、线性表的长度：是指线性表中数据元素的个数，当N=0时，称为空表。
5、通常定义一个一维数组来表示线性表的顺序存储空间，用一维数组来存放线性表时，该一维数组的长度不要定义为太短，也不要定义为太长。
6、顺序表（线性表的顺序结构）的插入运算：在一般情况下，要在第i（1≤i≤n）个元素之前插入一个新元素时，首先要从最后一个（即第n个）元素开始，直到第i个元素之间共n-i+1个元素依次向后移动一个位置，移动结束后，第i个位置就被空出，然后将新元素插入到第i项。插入结束后，线性表的长度就增加了1。
7、顺序表的删除运算：在一般情况下，要删除第i（1≤i≤n）个元素时，则要从第i+1个元素开始，直到第n个元素之间共n-i个元素依次向前移动一个位置。删除结束后，线性表的长度就减小了1。
*：进行顺性表的删除运算时也需要移动元素，在等概率情况下，平均需要移动（n-1）/2个元素。插入、删除运算不方便。
例题：选择正确表示线性表(A1,A2,A3,A4)的顺序结构是（）
综上所述：线性表的顺序存储结构对于经常需要变动的大线性表就不合适了，因为插入和删除的效率比较低。
线性表的顺序存储的缺点
第一、在插入和删除时需要移动元素（除栈和队列之外）
第二、上溢（或下溢）
1.4 栈
1、栈的定义：展示一种特殊的线性表，即限定在一端进行插入与删除的线性表。
2、栈顶、栈底的定义：在栈中，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈顶元素总是最后被插入的元素，栈底元素总是最先被插入的元素。
3、栈的操作原则：是按照“先进后出”或“后进先出”的原则组织数据的。
4、栈的基本运算：1）插入元素称为入栈运算；
2）删除元素称为退栈运算；
3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。
5、栈具有记忆功能。
6、注意：1）在顺序存储结构下，栈的插入与删除运算都不需要移动表中其他数据元素；
2）在栈中，栈顶指针动态反映了栈中元素的变化情况。
7、在顺序结构下的读栈顶元素是指将栈顶元素赋值给一个指定的变量。（读不是删除，删除一定要先读。在只读的情况下，原来是多少，读后还是多少）
8、读栈顶元素过程中应注意的问题：
1）读栈顶元素不删除栈顶元素，只是将它的值赋给一个变量。因此在这个运算中栈顶指针不会改变；
2）当栈顶指针为0时，说明栈为空，读不到栈顶元素。
1.5
1
线性表。
2、允许插入的一端叫队尾。尾指针（Rear）指向队尾元素。
允许删除的一端叫对头。头指针（front）指向排头元素的前一个位置（队头）。
3、数据操作方法：队列是“先进先出”或“后进后出”的线性表。
4、队列运算包括：1）入队运算：从队尾插入一个元素；
2）退队运算：从队头删除一个元素。
5、在顺序存储结构下，队列的插入与删除运算都不需要移动表中其他数据元素。
6、循环队列及其运算：所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置，因此，从头指针front指向的后一个位置直到队尾指针rear指向的位置之间，所有的元素均为队列中的元素。
7、确定循环队列中元素个数的方法如下：
设循环队列的容量为M，
如果rear>front，则循环队列中的元素个数为rear-front；
如果rear 8、循环队列的运算有两个： 1）入队运算：是在循环队列的队尾加入一个新元素，也就是rear+1； 2）退队运算：是在先能换队列的排头位置退出一个元素并赋给指定的变量，也就是 front+1。 1.6 线性链表 对于大的线性表或者变动频繁的线性表不宜用顺序存储，应该用链式存储。 1、链式存储方式的特点： （1）在链式存储结构中，存储数据结构的存储空间可以是不连续的。 （2）各结点的存储顺序与数据元素之间的逻辑关系可以不一致。 2、线性链表：线性表的链式存储结构称为线性链表，是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接来实现的。 3、线性表顺序存储的缺点： （1）插入或删除的运算效率很低。在顺序存储的线性表中，插入或删除数据元素时需要移动大量的数据元素； （2）线性表的顺序存储结构下，线性表的存储空间不便于扩充； （3）线性表的顺序存储结构不便于对存储空间的动态分配。 注意：线性链表是线性表的链式存储结构；带链的栈是栈的链式存储结构；带链的队列是队列的链式存储结构。 4、线性链表的存储结点的定义：为了适应线性链表的链式存储结构，计算机存储空间被划分为一个一个小块，每个小块占若干个字节，通常称这些小块为存储结点。 存储结点=数据域+指针域 头指针：在线性链表中，头指针（head）很关键，不的丢失。 最后一个结点的指针域：线性链表的最后一个结点的指针域为空（用NULL或0来表示）5、在链式存储方式中，每个结点由两部分组成：一部分用于存放数据元素的值，称为数据域；另一部分用于存放指针，称为指针域，用于指向该结点的前一个或后一个结点（即前件或后件），如下图所示： 线性链表分为单链表、双向链表和循环链表三种类型。 在单链表中，每一个结点只有一个指针域，由这个指针只能找到其后件结点，而不能找到其 前件结点。因此，在某些应用中，对于线性链表中的每个结点设置两个指针，一个称为左指 针，指向其前件结点；另一个称为右指针，指向其后件结点，这种链表称为双向链表，如下 图所示： 3、线性链表的基本运算 （1）在线性链表中包含指定元素的结点之前插入一个新元素。 *：在线性链表中插入元素时，不需要移动数据元素，只需要修改相关结点指针即可，也不 会出现“上溢”现象。 （2）在线性链表中删除包含指定元素的结点。 *：在线性链表中删除元素时，也不需要移动数据元素，只需要修改相关结点指针即可。 （3）将两个线性链表按要求合并成一个线性链表。（4）将一个线性链表按要求进行分解。 （5）逆转线性链表。（6）复制线性链表。 （7）线性链表的排序。（8）线性链表的查找。 *：线性链表不能随机存取。 4、循环链表及其基本运算 在线性链表中，其插入与删除的运算虽然比较方便，但还存在一个问题，在运算过程中对于 空表和对第一个结点的处理必须单独考虑，使空表与非空表的运算不统一。为了克服线性链 表的这个缺点，可以采用另一种链接方式，即循环链表。 与前面所讨论的线性链表相比，循环链表具有以下两个特点：1）在链表中增加了一个表头 结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点，而循 环链表的头指针指向表头结点；2）循环链表中最后一个结点的指针域不是空，而是指向表 头结点。即在循环链表中，所有结点的指针构成了一个环状链。 下图a是一个非空的循环链表，图b是一个空的循环链表： 循环链表的优点主要体现在两个方面：一是在循环链表中，只要指出表中任何一个结点的位 置，就可以从它出发访问到表中其他所有的结点，而线性单链表做不到这一点；二是由于在 循环链表中设置了一个表头结点，在任何情况下，循环链表中至少有一个结点存在，从而使 空表与非空表的运算统一。 *：循环链表是在单链表的基础上增加了一个表头结点，其插入和删除运算与单链表相同。 但它可以从任一结点出发来访问表中其他所有结点，并实现空表与非空表的运算的统一。 data next 数据域指针域 a1a2a n-1 HEAD…a n^ (a)结点结构(b)一个非空的线性链表示意图 右指针 左指针数据域 (a)结点结构 ^a1^ a n a2… HEAD (b)一个非空的双向链表示意图 1.6 树与二叉树 1、树的基本概念 层次特性。 结点的定义：数据元素+若干指向子树的分支。 结点的度得定义：子树的个数，即拥有的后件个数称为该结点的度。 树的度得定义：树中所有结点的度的最大值。 叶子结点的定义：度为零的结点，即没有后件的结点。 分支结点的定义：度大于非零的结点。 结点的层次（深度）的定义：假设根结点的层次为1，第I 层得结点的子树根结点的层次为I+1。 树的深度的定义：树中叶子结点所在的最大层次。 2、二叉树及其基本性质 （1）什么是二叉树 它具有以下两个特点：1）非空二叉树只有一个根结点； 2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。 *：根据二叉树的概念可知，二叉树的度可以为零（叶结点）、1（只有一棵子树）或2（有2棵子树）。 （2）二叉树的基本性质 性质1 在二叉树的第k 层上，最多有 个结点。 性质2 深度为m 的二叉树最多有个 个结点。 性质3 在任意一棵二叉树中，度数为0的结点（即叶子结点）总比度为2的结点多一个。性质4 具有n 个结点的二叉树，其深度至少为 ，其中 表示取 的整数部分。 3、满二叉树与完全二叉树 满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。 完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。 *：根据完全二叉树的定义可得出：度为1的结点的个数为0或1。 下图a 表示的是满二叉树，下图b 表示的是完全二叉树： 完全二叉树还具有如下两个特性： )1(21≥-k k 1 2-m 1][log 2+n ][log 2n n 2log (a)满二叉树(b)完全二叉树 性质5 具有n 个结点的完全二叉树深度为 。 性质6 设完全二叉树共有n 个结点，如果从根结点开始，按层序（每一层从左到右）用自然数1，2，…，n 给结点进行编号，则对于编号为k （k=1，2，…，n ）的结点有以下结论： ①若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点的编号为INT(k/2)。 ②若2k ≤n ，则编号为k 的左子结点编号为2k ；否则该结点无左子结点（显然也没有右子结点）。 ③若2k+1≤n ，则编号为k 的右子结点编号为2k+1；否则该结点无右子结点。 4、二叉树的存储结构 在计算机中，二叉树通常采用链式存储结构。 与线性链表类似，用于存储二叉树中各元素的存储结点也由两部分组成：数据域和指针域。但在二叉树中，由于每一个元素可以有两个后件（即两个子结点），因此，用于存储二叉树的存储结点的指针域有两个：一个用于指向该结点的左子结点的存储地址，称为左指针域；另一个用于指向该结点的右子结点的存储地址，称为右指针域。 *：一般二叉树通常采用链式存储结构，对于满二叉树与完全二叉树来说，可以按层序进行顺序存储。 5、二叉树的遍历 二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历可以分为以下三种： （1）前序遍历（DLR ）：若二叉树为空，则结束返回。否则：首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。 （2）中序遍历（LDR ）：若二叉树为空，则结束返回。否则：首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。 （3）后序遍历（LRD ）：若二叉树为空，则结束返回。否则：首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。 1.7 查找技术 查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。 查找结果：（查找成功：找到；查找不成功：没找到。） 平均查找长度：查找过程中关键字和给定值比较的平均次数。 1、顺序查找 基本思想：从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。 在平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中一半的元素进行比较，最坏情况下需要比较n 次。 顺序查找一个具有n 个元素的线性表，其平均复杂度为O （n ）。 下列两种情况下只能采用顺序查找： 1）如果线性表是无序表（即表中的元素是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。 2）即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。 1][log 2 n 第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（） A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（） A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（） A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学 2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学 2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学 2001 一、10（3分）】 FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换； 其中 n为正整数，则最后一行的语句频度在最坏情况下是（） 习题参考答案 一．选择题 1.从逻辑上可以把数据结构分为（C)两大类。 A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 2.在下面的程序段中，对x的斌值语句的频度为（C)。 for( t＝1；k＜＝n;k＋＋） for（j=1;j＜＝n; j＋＋） x=x十1； A. O(2n) B. O (n) C. O (n2)． D. O（1og2n) 3.采用链式存储结构表示数据时，相邻的数据元素的存储地址（C)。 A.一定连续B．一定不连续 C.不一定连续 D.部分连续，部分不连续 4.下面关于算法说法正确的是（D）。 A.算法的时间复杂度一般与算法的空间复杂度成正比 B.解决某问题的算法可能有多种，但肯定采用相同的数据结构 C.算法的可行性是指算法的指令不能有二义性 D.同一个算法，实现语言的级别越高，执行效率就越低 5.在发生非法操作时，算法能够作出适当处理的特性称为（B）。 A.正确性 B.健壮性 C.可读性 D.可移植性 二、判断题 1.数据的逻辑结构是指数据的各数据项之间的逻辑关系。（√） 2.顺序存储方式的优点是存储密度大，且插人、删除运算效率高。（×） 3.数据的逻辑结构说明数据元素之间的次序关系，它依赖于数据的存储结构。（×） 4.算法的优劣与描述算法的语言无关，但与所用计算机的性能有关。（×） 5.算法必须有输出，但可以没有输人。（√） 三、筒答题 1．常见的逻辑结构有哪几种，各自的特点是什么？常用的存储结构有哪几种，各自的特点是什么？ 【答】常见的四种逻辑结构： ①集合结构：数据元素之间是“属于同一个集合” ②线性结构：数据元素之间存在着一对一的关系 ③树结构：数据元素之间存在着一对多的关系 ④结构：数据元素之间存在着多对多的关系。 常见的四种存储结构有： ①顺序存储：把逻辑上相邻的元素存储在物理位置相邻的存储单元中。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。 ②链接存储：对逻辑上相邻的元素不要求物理位置相邻的存储单元，元素间的逻辑关系通过附设的指针域来表示。 ③索引存储：通过建立索引表存储结点信息的方法，其中索引表一般存储结点关键字和一个地点信息，可通过该地址找到结点的其他信息。 ④散列存储：根据结点的关键字直接计算出该结点的存储地址的方法。 2．简述算法和程序的区别。 【解答】一个算法若用程序设计语言来描述，则它就是一个程序。算法的含义与程序十分相 全国计算机二级考试 第一章数据结构与算法 1.一个算法一般都可以用_____、_____ 、 _____三种控制结构组合完成。 [解析]顺序、选择（分支）、循环（重复） 一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是________。 [解析]算法的控制结构 在一般的计算机系统中，有算术运算、逻辑运算、关系运算和________四类基本的操作和运算。 [解析]数据传输 2.常用于解决“是否存在”或“有多少种可能”等类型的问题（例如求解不定方程的问题）的算法涉及基本方法是（） A．列举法 B.归纳法 C.递归法 D.减半递推法 [解析]列举就是列举出所有可能性，将所有可能性统统列举出来，然后解决问题的方法。所以A 3.根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的，这是算法设计基本方法中的____。 [解析]列举法 4.通过列举少量的特殊情况，经过分析，最后找出一般的关系的算法设计思想是（） A．列举法 B.归纳法 C.递归法 D.减半递推法 [解析]B 5.在用二分法求解方程在一个闭区间的实根时，采用的算法设计技术是（） A．列举法 B.归纳法 C.递归法 D.减半递推法 [解析]二分法就是从一半处比较，减半递推技术也称分治法，将问题减半。所以D 6.将一个复杂的问题归结为若干个简单的问题，然后将这些较简单的问题再归结为更简单的问题，这个过程可以一直做下去，直到最简单的问题为止，这是算法设计基本方法中的___。如果一个算法P显式地调用自己则称为___。如果算法P调用另一个算法Q,而算法Q又调用算法P，则称为_____. [解析]递归法直接递归间接递归调用 7.算法中各操作之间的执行顺序称为_____。描述算法的工具通常有_____、_____ 、 _____。 [解析]控制结构传统流程图、N-S结构化流程图、算法描述语言 8.从已知的初始条件出发，逐步推出所要求的各中间结果和最后结果，这 数据结构与算法设计知识点 试题类型： 本课程为考试科目（闭卷笔试），试题类型包括：概念填空题（10 %），是非判断题（10 %），单项选择题（40 %），算法填空题（10%），算法应用题（20 %)，算法设计题（10 %）。 第一章绪论 重点容及要求： 1、了解与数据结构相关的概念（集合、数据、数据元素、数据项、关键字、元 素之间的关系等）。 数据：所有能被输入到计算机中，且能被计算机处理的符号的 集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定 的符号表示形式。 数据元素：是数据（集合）中的一个“个体”，数据结构中的基 本单位，在计算机程序常作为一个整体来考虑和处理。 数据项：是数据结构中讨论的最小单位，数据元素可以是一个或 多个数据项的组合 关键码：也叫关键字（Key），是数据元素中能起标识作用的数据 项。 其中能起到唯一标识作用的关键码称为主关键码（简称主码）； 否则称为次关键码。通常，一个数据元素只有一个主码，但可以有多 个次码。 关系：指一个数据集合中数据元素之间的某种相关性。 数据结构：带“结构”的数据元素的集合。这里的结构指元素之 间存在的关系。 数据类型：是一个值的集合和定义在此集合上的一组操作的总 称。 2、掌握数据结构的基本概念、数据的逻辑结构（四种）和物理结构（数据元素 的表示与关系的表示、两类存储结构：顺序存储结构和链式存储结构）。 数据结构包括逻辑结构和物理结构两个层次。 数据的逻辑结构：是对数据元素之间存在的逻辑关系的一种抽象的描述，可以用一个数据元素的集合和定义在此集合上的若干关系来表示 逻辑结构有四种：线性结构、树形结构、图状结构、集合结构数据的物理结构：是其逻辑结构在计算机中的表示或实现，因此又称其为存储结构。 存储结构：顺序存储结构和链式存储结构 顺序存储结构：利用数据元素在存储器中相对位置之间的某种特定的关系来表示数据元素之间的逻辑关系； 链式存储结构：除数据元素本身外，采用附加的“指针”表示数据元素之间的逻辑关系。 3、了解算法分析的基本方法，掌握算法时间复杂度相关的概念。 算法：是为了解决某类问题而规定的一个有限长的操作序列 或处理问题的策略 一个算法必须满足以下五个重要特性：1．有穷性2．确定性3．可行性4．有输入 5．有输出 设计算法时，通常还应考虑满足以下目标： 1.正确性， 2.可读性， 3.健壮性 4.高效率与低存储量需求 第一章绪论 一．选择题 1．数据结构被形式地定义为（K，R），其中K是①_B_的有限集合，R是K上的②_D_的有限集合。 ①A．算法B．数据元素C．数据操作D．逻辑结构 ②A．操作B．映象C．存储D．关系 2．算法分析的目的是①C，算法分析的两个主要方面是②A。 ①A．找出数据结构的合理性 B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进 D．分析算法的易懂性和文档性 ②A．空间复杂性和时间复杂性 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性 3．在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为(B) A．逻辑结构B．顺序存储结构 C．链表存储结构D．以上都不对 4．数据结构中，在逻辑上可以把数据结构分成：( C ）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构5．以下属于顺序存储结构优点的是（A ）。 A．存储密度大B．插入运算方便 C．删除运算方便D．可方便地用于各种逻辑结构的存储表示 6．数据结构研究的内容是（D ）。 A．数据的逻辑结构B．数据的存储结构 C．建立在相应逻辑结构和存储结构上的算法D．包括以上三个方面 7．链式存储的存储结构所占存储空间（A ）。 A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B．只有一部分，存放结点值 C．只有一部分，存储表示结点间关系的指针 D．分两部分，一部分存放结点值，另一部分存放结点所占单元数 8．一个正确的算法应该具有5 个特性，除输入、输出特性外，另外3 个特性是（A ）。 A．确定性、可行性、有穷性B．易读性、确定性、有效性C．有穷性、稳定性、确定性D．可行性、易读性、有穷性9．以下关于数据的逻辑结构的叙述中正确的是（A）。 A．数据的逻辑结构是数据间关系的描述 B．数据的逻辑结构反映了数据在计算机中的存储方式 C．数据的逻辑结构分为顺序结构和链式结构 D．数据的逻辑结构分为静态结构和动态结构 10．算法分析的主要任务是（C ）。 A．探讨算法的正确性和可读性B．探讨数据组织方式的合理性C．为给定问题寻找一种性能良好的解决方案D．研究数据之间的逻辑关系 二．解答 设有一数据的逻辑结构为：B=(D, S)，其中： D={d1, d2, …, d9} S={ 《数据结构与算法设计》习题册 第一章绪论 一、单项选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运 算等的学科。 ①A. 数据元素 B. 计算方法 C. 逻辑存储 D. 数据映象 ②A. 结构 B. 关系 C. 运算 D. 算法 2.数据结构被形式地定义为（K，R），其中K是①的有限集，R是K上的②有限集。 ①A. 算法 B. 数据元素 C. 逻辑结构 D. 数据操作 ②A. 操作 B. 存储 C. 映象 D. 关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构 4.数据结构在计算机内存中的表示是指。 A. 数据的存储结构 B. 数据结构 C. 数据的逻辑结构 D. 数据元素之间的关系 5.在数据结构中，与所使用的计算机无关的是数据的结构。 A. 逻辑 B. 存储 C. 逻辑和存储 D. 物理 6.算法分析的目的是①，算法分析的两个主要方面是②。 ①A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ②A. 空间复杂度和时间复杂度 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 7.计算机算法指的是①，它必须具备输入、输出和②等5个特性。 ①A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ②A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 8.在以下叙述中，正确的是。 A. 线性表的线性存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C. 栈的操作方式是先进先出 D. 队列的操作方式是先进后出 9.在决定选取何种存储结构时，一般不考虑。 A. 各结点的值如何 B. 结点个数的多少 C. 对数据有哪些运算 D. 所用编程语言实现这种结构是否方便 10.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储。 第一章 数据结构与算法 1.1 算法 1 描述。 算法规定了解决某类问题所需的操作语句以及执行顺序，使其能通过有限的指令语句，在一定时间内解决问题。 算法是一个操作序列、有限长度，目的是解决某类问题。 *：算法不等于程序，也不等于计算方法。程序的编制不可能优于算法的设计。 2、算法的基本特征 （1）可行性。针对实际问题而设计的算法，执行后能够得到满意的结果。 （2）确定性。每一条指令的含义明确，无二义性。并且在任何条件下，算法只有唯一的一条执行路径，即相同的输入只能得出相同的输出。 （3）有穷性。算法必须在有限的时间内完成。有两重含义，一是算法中的操作步骤为有限个，二是每个步骤都能在有限时间内完成。 （4）拥有足够的情报。指的是有足够的输入和输出。 *：综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。 3、算法的基本要素 一个算法通常由两种基本要素组成：一是对数据对象的运算和操作；二是算法的控制结构。 (1）算法中对数据的运算和操作 每个算法实际上市按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。因此，计算机算法就是计算机能处理的操作所组成的指令序列。 在一般的计算机系统中，基本的运算和操作有以下四类： ①算术运算：主要包括加、减、乘、除等运算； ②逻辑运算：主要包括与(AND)、或(OR)、非(NOT) 等运算； ③关系运算：主要包括大于、小于、等于、不等于等运算 ④数据传输：主要包括赋值、输入、输出等操作。 (2)算法的控制结构 顺序、选择和循环。 4、算法的基本方法（计算机解题的过程实际上是在实施某种算法） （1）列举法（列举所有解决方案） 根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。 （2）归纳法（特殊->一般）适合于列举量为无限的情况 通过列举少量的特殊情况，经过分析，最后找出一般的关系。 （3）递推法（已知->未知） 从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。 （4）递归法（逐层分解） 将一个复杂的问题归结为若干个较简单的问题，然后将这些较简单的每一个问题再归结为更简单的问题 （5）减半递推法 “减半”是指将问题的规模减半，而问题的性质不变，所谓“递推”是指重复“减半”的过程。 （6）回溯法 复杂应用，找出解决问题的线索，然后沿着这个线索逐步多次“探”、“试”。 5、算法复杂度主要包括时间复杂度和空间复杂度。 算法的复杂度是衡量算法好坏的量度。 （1）算法时间复杂度是指执行算法所需要的计算工作量，可以用执行算法的过程中所需基本运算的执行次数来度量。 影响计算机工作量的主要因素： 第一：基本运算次数；第二：问题规模。 下面的方法不能用来度量算法的时间复杂度： 第一：算法程序的长度或算法程序中的语句（指令）条数； 第二：算法程序所执行的语句条数； 第三：算法程序执行的具体时间 （2 一个算法所用的内存空间包括： 1）算法程序所占用的存储空间； 2）输入的初始数据所占的存储空间；3）算法执行过程中的额外空间。 6、考题练习： 1）下列叙述正确的是（） （A）算法就是程序 （B）算法强调的是利用技巧提高程序执行效率 （C）设计算法时只需考虑结果的可靠性 （D）以上三种说法都不对 2）下面叙述正确的是（） （A）算法的执行效率与数据的存储结构无关 （B）算法的空间复杂度是指算法程序中指令（或语句）的条数 （C）算法的有穷性是指算法必须能在执行有限个步骤之后终止 （D）以上三种描述都不对 3）下列叙述中正确的是（） （A）一个算法的空间复杂度大，则其时间复杂度也必定大 （B）一个算法空间复杂度大，则其时间复杂度必定小 （C）一个算法的时间复杂度大，则其时间复杂度必定小 二级公共基础知识第一章数据结构与算法练习一 1.栈和队列的共同特点是（只允许在端点处插入和删除元素）。 2.如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是（e2,e4,e3,e1）。 3.栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是（DCBEA）。 4.栈通常采用的两种存储结构是（线性存储结构和链表存储结构）。 5.下列关于栈的叙述正确的是（D）。 A.栈是非线性结构 B.栈是一种树状结构 C.栈具有先进先出的特征 D.栈有后进先出的特征 6.链表不具有的特点是（B）。 A.不必事先估计存储空间 B.可随机访问任一元素 C.插入删除不需要移动元素 D.所需空间与线性表长度成正比 7.用链表表示线性表的优点是（便于插入和删除操作）。 8.在单链表中，增加头结点的目的是（方便运算的实现）。 9.循环链表的主要优点是（从表中任一结点出发都能访问到整个链表）。 10.线性表L＝（a1,a2,a3,……ai,……an），下列说法正确的是（D）。 A.每个元素都有一个直接前件和直接后件 B.线性表中至少要有一个元素 C.表中诸元素的排列顺序必须是由小到大或由大到小 D.除第一个和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件 11.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）。 A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续不连续都可以 12.线性表的顺序存储结构和线性表的链式存储结构分别是（随机存取的存储结构、顺序存取的存储结构）。 13.树是结点的集合，它的根结点数目是（有且只有1）。 14.在深度为5的满二叉树中，叶子结点的个数为（31）。 15.具有3个结点的二叉树有（5种形态）。 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为（13）。 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（cedba）。 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为（DGEBHFCA）。 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（gdbehfca）。 20.数据库保护分为：（安全性控制）、（完整性控制）、并发性控制和数据的恢复。 二级公共基础知识第一章数据结构与算法练习二 1. 在计算机中，算法是指（解题方案的准确而完整的描述） 2.在下列选项中，哪个不是一个算法一般应该具有的基本特征（无穷性） 说明：算法的四个基本特征是：可行性、确定性、有穷性和拥有足够的情报。 3. 算法一般都可以用哪几种控制结构组合而成（顺序、选择、循环） 4.算法的时间复杂度是指（算法执行过程中所需要的基本运算次数） 5. 算法的空间复杂度是指（执行过程中所需要的存储空间） 第一章绪论 1. 从逻辑上可以把数据结构分为（ C ）两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 2. 在下面的程序段中，对x的赋值语句的频度为（ C ）。 For（k=1；k<=n；k++） For（j=1；j<=n；j++） x=x＋1； A．O(2n) B．O(n) C．O(n2) D．O(log2n) 3. 采用顺序存储结构表示数据时，相邻的数据元素的存储地址（ A ）。 A．一定连续B．一定不连续 C．不一定连续D．部分连续、部分不连续 4. 下面关于算法的说法，正确的是（ D ）。 A．算法的时间复杂度一般与算法的空间复杂度成正比 B．解决某问题的算法可能有多种，但肯定采用相同的数据结构 C．算法的可行性是指算法的指令不能有二义性 D．同一个算法，实现语言的级别越高，执行效率就越低 5. 在发生非法操作时，算法能够作出适当处理的特性称为（ B ）。 A．正确性B．健壮性C．可读性D．可移植性 第二章线性表 1. 线性表是（ A ）。 A．一个有限序列，可以为空B．一个有限序列，不能为空 C．一个无限序列，可以为空D．一个无限序列，不能为空 2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（ A ）个元素。 A．n/2 B．（n＋1）/2 C．（n－1）/2 D．n 3．线性表采用链式存储时，其地址（ D ）。 A．必须是连续的B．部分地址必须是连续的 C．一定是不连续的D．连续与否均可以 4．用链表表示线性表的优点是（C）。 A．便于随机存取B．花费的存储空间较顺序存储少 C．便于插入和删除D．数据元素的物理顺序与逻辑顺序相同 5．链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（ C ）存储方式最节省运算时间。 第一章绪论 一、选择题 1. 算法的计算量的大小称为计算的（ B ）。 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（ C ） A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（ C ）它必须具备（ B ）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性4．一个算法应该是（）。 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（） A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（） (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（ C ）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（ D ）。 A．循环队列 B. 链表 D. 栈 9．以下数据结构中，（ D ）是线性结构 A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下数据结构中，（ A ）是非线性数据结构 A．树 B．字符串 C．队 D．栈 11．连续存储设计时，存储单元的地址（ A ）。 A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续12．以下属于逻辑结构的是（ C ）。 A．顺序表 C.有序表 D. 单链表 二、填空 1．数据的物理结构包括的表示和的表示。 2. 对于给定的n个元素,可以构造出的逻辑结构有（1），（2），（3），__（4）_四种。 3．数据的逻辑结构是指。 4．一个数据结构在计算机中称为存储结构。 5．抽象数据类型的定义仅取决于它的一组__（1）_，而与_（2）_无关，即不论其内部结构如何变化，只要它的_（3）_不变，都不影响其外部使用。 6．数据结构中评价算法的两个重要指标是 7. 数据结构是研讨数据的_（1）_和_（2）_，以及它们之间的相互关系，并对与这种结构定义相应的_（3）_，设计出相应的（4）_。 8．一个算法具有5个特性: （1）、（2）、（3），有零个或多个输入、有一个或多个输出。 9. 下面程序段的时间复杂度为__O(n)______。(n>1) sum=1； for (i=0;sum 第一章绪论习题练习答案 1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。 ● 数据：指能够被计算机识别、存储和加工处理的信息载体。 ● 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。 ● 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。 ● 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。 ● 逻辑结构：指数据元素之间的逻辑关系。 ● 存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构. ● 线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。 ● 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。 1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。 答： 例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。这张登记表中，每个学生的各项体检信息排在一行上。这个表就是一个数据结构。每个记录(有姓名，学号，身高和体重等 字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构是线性结构。 这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢? 即用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题。 在这个表的某种存储结构基础上，可实现对这张表中的记录进行查询，修改，删除等操作。对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。 1.3 常用的存储表示方法有哪几种? 答： 常用的存储表示方法有四种: ● 顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。 ● 链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示。由此得到的存储表示称为链式存储结构,通常借助于程序语言的指针类型描述。 ● 索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。组成索引表的索引项由结点的关键字和地址组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（Dense Index）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。 ● 散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。 1.4 设三个函数f,g,h分别为f(n)=100n3+n2+1000 , g(n)=25n3+5000n2 , h(n)=n1.5+5000nlgn 请判断下列关系是否成立： (1) f(n)=O(g(n)) (2) g(n)=O(f(n)) (3) h(n)=O(n1.5) (4) h(n)=O(nlgn) 分析： 数学符号"O"的严格的数学定义： 若T（n）和f（n）是定义在正整数集合上的两个函数，则T（n）=O（f（n））表示存在正的常数C和n0， 作业布置 作业一 第一章 1.1 什么是数据对象、数据元素、数据结构？ 1.2 什么是数据类型？什么是抽象数据类型？ 1.3 什么是算法？它有哪些特性？它与程序有何区别？ 1.4 试判定下列计算过程是否为一个算法？ 1)开始 2)n<=0 3)n=n+1 4)重复3) 5)结束 1.5 用图形表示下列数据结构： 1) S=(D, R) , D={a,b,c,d,e,f,g} , R={ 2.1 试编写一个算法，将一个顺序表逆置，并使用最少的辅助存储空间实现。 2.2 试编写一个算法，将两个元素值递减排列的顺序表合并为一个非递增的顺序表。 2.3 试编写一个算法，计算带头结点的循环单链表的长度。 2.4 试编写一个算法，在一个递增有序排列的单链表中插入一个新结点x，并保持有序。2.5 试编写一个算法，将一个单链表逆置。 2.6 试编写一个算法，在一个双向循环链表中将结点x插入到指定结点p之前。 2.7 试编写一个算法，计算一个循环队列中包含的元素个数。 2.8 试编写一个算法，实现对一个以只带尾指针的循环单链表表示的队列的入队出队操作。 >> 查看/完成作业：作业二 作业三 3.1 设字符串S=＂good＂，T=＂I am a student＂，R=＂!＂，求： （1）CONCAT(T，R，S) （2）SUBSTR(T，8，7) （3）Len(T) （4）index(T，＂a＂) （5）insert(T，S，8) （6）replace(T，SUBSTR(T，8，7) ，＂teacher＂) 3.2 计算下列串的next值： （1）a a a b c a a b a （2）a b a a b c a c b （3）a b c a b c a c b （4）b a b b a b a b 《数据结构与算法》第1章绪论测试题 适用班级：数技19101-19104、物联19103-10104 测试时间：60分钟 一、填空题（每空3分，共45分） 1. 位是数据的最小单位，数据元素是数据的基本单位。 2.计算机所处理的数据一般具备某种内在联系，这是指元素和元素之间存在的某种关系。 3.一个算法具有正确性，可读性，健壮性，效率与存储量需求。 4.算法的时间复杂度与问题的规模有关。 5.某算法的时间复杂度 O(n2)，表明该算法的与n2成正比。 6.数据采用链式存储结构时，要求每个结点占用一片连续的存储区域。 7.数据的逻辑结构是指数据元素之间逻辑关系的整体。 8.数据结构通常分为以下4类基本结构：集合、线性结构、树形结构和图结构。 9.顺序存储映像和非顺序存储印象，得到两种不同的存储结构：线性存储结构和非线性储存结构。 10.在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有一个前驱结点。 11.在图状结构中，每个结点的前驱结点数和后继结点数可以有任意多个。 12.一个算法具有5个特性：有穷性，确定性，可行性，有零个或多个输出。 13.算法中的每条指令都必须有确切的含义，不能具有二义性，表现算法特性中的确定性。 14.数据在计算机的存储器中表示时，逻辑上相邻的两个数据元素对应的物理地址也是相邻的，这种存储结构称之为顺序储存结构。 15.算法分析的目的是找出数据结构的合理性，算法分析的两个主要方面是空间复杂度和 时间复杂度。 二、判断题（每题2分，共20分） 1.数据对象就是一组任意数据元素的集合（ f ） 2.数据对象是具有相同性质的数据元素的集合（ t ） 3.数据对象是由有限个类型相同的数据元素构成的（ t ） 4.数据的逻辑结构与各数据元素在计算机中如何存储有关（ f ） 5.逻辑结构不相同的数据，必须采用不同类型的存储方式（ t ） 6.数据的逻辑结构是指数据的各数据项之间的逻辑关系（ f ） 7.算法的优劣与算法描述语言无关，但与所用的计算机有关（ f ） 8.程序一定是算法（ f ） 9.算法最终必须由计算机实现（ f ）数据结构 习题 第一章 绪论
数据结构与算法第1章参考答案
全国计算机二级考试 数据结构与算法
大数据结构与算法设计知识点
数据结构与算法习题库(考前必备)
数据结构习题汇编01 第一章 绪论 试题
计算机-数据结构与算法
第一章数据结构与算法练习一
《数据结构与算法》习题：选择题、判断题
数据结构及应用算法教程习题--第一章
中南大学数据结构与算法_第1章绪论课后作业答案
数据结构与算法课后作业
《数据结构与算法》第一章绪论测试试题
相关文档
- 第1章 数据结构与算法的概念
- 数据结构与算法第1章参考答案
- 数据结构与算法习题库(考前必备)
- 第一章数据结构与算法
- 《数据结构与算法》第一章绪论测试试题
- 数据结构与算法 习题答案第1章
- 第一章数据结构与算法练习一
- 数据结构及应用算法教程习题--第一章
- 数据结构与算法习题库(考前必备)
- 大数据结构与算法设计知识点
- 数据结构与算法第1章参考答案08
- 数据结构与算法课后作业
- 数据结构与算法第三版第1章参考答案
- 计算机-数据结构与算法
- 数据结构与算法分析 PPT
- 数据结构 习题 第一章 绪论
- 第一章 数据结构与算法概论
- 数据结构与算法习题册参考答案
- 中南大学数据结构与算法_第1章绪论课后作业答案
- 全国计算机二级考试 数据结构与算法