数据结构章节练习题及答案1

1、第1章概论L数据、数据元素、数据结构、数据类型的含义分别是什么？数据：对客观事物的符号表示，在计算机科学中是指所有能输入 到计算机中并由计算机程序处理的符号的总称。数据元素：数据的基本单位，在计算机程序中通常作为一个整体 考虑。数据结构：数据元素之间的关系+运算，是以数据为成员的结构, 是带结构的数据元素的集合，数据元素之间存在着一种或多种特定的 关系。数据类型：数据类型是用来区分不同的数据；由于数据在存储时 所需要的容量各不相同，不同的数据就必须要分配不同大小的内存空 间来存储，所有就要将数据划分成不同的数据类型。数据类型包含取 值范围和基本运算等概念。.什么是数据的逻辑结构？什么是数据的物

2、理结构？数据的逻 辑结构与物理结构的区别和联系是什么？逻辑结构：数据的逻辑结构定义了数据结构中数据元素之间的相 互逻辑关系。数据的逻辑结构包含下面两个方面的信息：数据元素的信息；各数据元素之间的关系。物理结构：也叫储存结构，是指逻辑结构的存储表示，即数据 的逻辑结构在计算机存储空间中的存放形式，包括结点的数据和结点 间关系的存储表示。数据的逻辑结构和存储结构是密不可分的，一个操作算法的设计 取决于所选定的逻辑结构，而算法的实现依赖于所采与的存储结构。 采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数 据处理时,针对不同问题，选择合理的逻辑结构和存储结构非常重要。,数据结构的主要操作

3、包括哪些？对于各种数据结构而言，他们在基本操作上是相似的，最常用的 操作有：创立：建立一个数据结构；清除：清除一个数据结构；插入：在数据结构中增加新的结点；删除：把指定的结点从数据结构中删除；访问：对数据结构中的结点进行访问；更新：改变指定结点的值或改变指定的某些结点之间的关系；查找：在数据结构中查找满足一定条件的结点；排序：对数据结构中各个结点按指定数据项的值，以升序或降 序重新排列。.什么是抽象数据类型？如何定义抽象数据类型？抽象数据类型(Abstract Data Type简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作。ADT是与具体的物理存储 无关的数据类型，因此，不管A

4、DT的内部结构如何变化，只要其数 据结构的特性不变，都不影响其外部使用。对抽象数据类型的描述一般用（D,R,P）三元组表示，抽象数据类 型的定义格式为：ADT抽象数据类型名（数据对象D：数据对象的定义,数据关系R：数据关系的定义基本操作P：基本操作的定义 ADT抽象数据类型名其中，D是数据对象，R是D上的关系集，P是对D的基本操作 集。数据对象和数据关系的定义用伪代码来描述。基本操作的定义格 式为：基本操作名（参数表）初始条件：初始条件描述,操作结果：操作结果描述初始条件说明操作执行之前数据结构和参数应满足的条件；操作 结果说明操作完成后，数据结构的变化状况和应返回的结果。.什么是算法？算法的

5、基本特征是什么？算法：是在有限的步骤内解决数学问题的过程，是以一步接一步 的方式来详细描述计算机如何将输入转化为所要求的输出的过程，即 算法是对计算机上执行的计算过程的具体描述。一个有效的算法必须 满足的五个重要特性： 有穷性：算法必须能在有限的时间内做完，即在任何情况下, 算法必须能在执行有限个步骤之后终止，都不能陷入无穷循环中。确定性：算法中的每一个步骤，必须经过明确的定义，并且 能够被计算机所理解和执行，而不能是抽象和模糊的概念，更不允许 有二义性。输入：算法有。个或多个输入值，来描述算法开始前运算对 象的初始情况，这是算法执行的起点或是依据。个输入是指算法本 身给出了运算对象的初始条件

6、。 输出：算法至少有1个或多个输出值，反映对运算对象的处 理结果，没有输出的算法没有任何意义。可行性：算法中要做的运算都是基本运算，能够被精确地进 行。即算法中执行的任何计算都可以被分解为基本的运算步，每个基 本的运算步都可以在有限的时间内完成。.什么是算法分析？算法分析主要考虑哪几方面的内容？ 算法的研究与实际问题直接相关，用来解一个问题可以有很多不同的算法，他们之间的效果可能会有很大差异。算法设计者最关心的 就是什么是有效的算法，如何评价一个算法的优劣，如何从多种算法 中选择好的算法。除了要首先考虑算法的正确性外，还要分析和评价 算法的性能。分析和评价算法的性能主要要考虑以下两个方面：时间

7、代价：执行算法所耗费的时间。一个好的算法首先应该比其他算法的运行时间代价要小。算法的时间代价的大小用算法的时间 复杂度来度量。空间代价：执行算法所耗费的存储空间，主要是辅助空间。算 法运行所需的空间消耗是衡量算法优劣的另一个重要因素。算法的空 间代价的大小用算法的空间复杂度来度量。.分析下面算法的时间复杂度。(1)答：时间复杂度为M(2)时间复杂度：n(3)时间复杂度：A(4)时间复杂度：n2(5)时间复杂度：O(log2n).算法设计中的递归、穷举、递推和迭代等算法的基本思想是什么？递推法：是利用问题本身所具有的一种递推关系求解问题的一种 方法。它把问题求解分成假设干步，找出相邻几步的关系，

8、从而到达求 解问题的目的。具有如下性质的问题可以采用递推法：当得到问题规 模为i-1的解后，由问题的递推性质，能构造出问题规模为i的解。 因此，程序可以从i=0或i=l出发，由i-1规模的解，通过递推, 获得问题规模为i的解，直至得到问题规模为n的解。递归法：递归策略是利用函数直接或间接地调用自身来完成某个 计算过程。能采用递归描述的算法通常有这样的特征：为求解规模为 n的问题，设法将它分解成规模较小的问题，然后从这些小问题的解 方便地构造出更大问题的解，并且这些规模较小的问题也能采用同样 的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解 构造出较大规模问题的解。穷举法：穷举搜索法

9、也称穷举法或搜索法是对可能是解的众多候 选解按某种顺序进行 逐一枚举和检验，并从中找出那些符合要求的 候选解作为问题的解。迭代法：数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程，为实现这一过程所 使用的方法统称为迭代法。溯策略.算法设计中的分治策略、贪心策略、动态规划策略、以及分支定界策略的基本思想是什么?溯策略分治策略的基本思想是把一个规模为n的问题划分为假设干个规模较小、且与原问题相似的子问题，然后分别求解这些子问题，最后把各子结果合并得到整个问题的解。分解的子问题通常与原问题相 似，所以可以递归地使用分治策略来求解。贪心策略的基本思想是把一个整体最优问题分解为一系列的最优选择问题，决策一旦做出，就不能再更改。它是通过假设干次的贪心 选择而得出最优解（或较优解）的一种解题策略。动态规划策略与贪心策略类似，将一个问题划分为重复的子问 题，通过对相同子问题的求解来解决较大问题，即将一个问题的解决 方案视为一系列决策的结果。不同的是，在贪心策略中，每采用一次 贪心准那么便做出一个不可撤回的决策，可能得不到问题的最优解。而 在动态规划中，处理要按照某种规那么进行选择，还要考察每个最优决 策序列中是否包含一个最优子序列，目的是得到问题的最优解。回溯策略也叫试探法，它的基本思想是：在一