数据结构与算法习题与答案

1、第四章习题 (P111-113 )一、 复习题1、试述数据和数据结构的概念及其区别。 数据是对客观事物的符号表示，是信息的载体；数据结构那么是指互相之间存在着一种或多种关系 的数据元素的集合。 ( P93)2、列出算法的五个重要特征并对其进行说明。 算法具有以下五个重要的特征：有穷性：一个算法必须保证执行有限步之后结束。确切性：算法 的每一步骤必须有确切的定义。 输入：一个算法有 0 个或多个输入， 以刻画运算对象的初始情况， 所谓 0 个输入是指算法本身定除了初始条件。输出：一个算法有一个或多个输出，以反映对输入 数据加工后的结果。没有输出的算法没有实际意义。可行性：算法原那么上能够精确地运

2、行，而且 人们用笔和纸做有限次运算后即可完成。 ( P95)3、算法的优劣用什么来衡量？试述如何设计出优秀的算法。时间复杂度 空间复杂度( P97-98 )4、线性和非线性结构各包含哪些种类的数据结构？线性结构和非线性结构各有什么特点？ 线性结构用于描述一对一的相互关系，即结构中元素之间只有最根本的联系，线性结构的特点是 逻辑结构简单。所谓非线性结构是指，在该结构中至少存在一个数据元素，有两个或两个以上的 直接前驱(或直接后继)元素。树型和图型结构就是其中十分重要的非线性结构，可以用来描述 客观世界中广泛存在的层次结构和网状结构的关系。(P99-105 )5、简述树与二叉树的区别；简述树与图的

3、区别。 树用来描述层次结构，是一对多或多对一的关系；二叉树( Binary Tree )是个有限元素的集合， 该集合或者为空、或者由一个称为根 (root) 的元素及两个不相交的、被分别称为左子树和右子树 的二叉树组成。二叉树是有序的，即假设将其左、右子树颠倒，就成为另一棵不同的二叉树。图也 称做网，是一种比树形结构更复杂的非线性结构。在图中，任意两个节点之间都可能相关，即节 点之间的邻接关系可以是任意的，图表示的多对多的关系。( P102-P104)6、请举出遍历算法在实际中使用的例子。 提示：根据实际生活中需要逐个访问处理的情况举例。7、编写一个算法，统计在一个输入字符串中各个不同字符出现

4、的频度。用适当的测试数据来验 证这个算法。提示：根据查找算法和串中求子串的算法，查找输入串中以单个字符形式的子串。8、假设对有 n 个元素的有序顺序表和无序顺序表进行顺序搜索，试就以下三种情况分别讨论两者 在等搜索概率时的平均搜索长度是否相同 ?(1) 搜索失败；(2) 搜索成功，且表中只有一个关键码等于给定值k 的对象；(3) 搜索成功，且表中有假设干个关键码等于给定值k 的对象，要求一次搜索找出所有对象。提示：根据 P106-109 页的查找和排序算法分别进行分析9、顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下，对有127 个元素的顺序表进行插入，平均需要移动多少个元

5、素?删除一个元素，又平均需要移动多少个元素?提示：根据 P99 线性表的定义进行分析。题义是进行插入和删除后仍然保持线性表的结构特性。10、递归的含义是什么？递归是指算法在过程中调用自身作为子算法的一种设计方法。 P109-110 练习题一填空题1、链表通常是由一个个节点构成的，每个节点的机构是由 域和 域构成。数据域 指针域 P99 2、树内节点度的最大值，即树中下级节点最多的节点的下级节点个数可被称为度的最大值 P1023、数组在存储和处理时是以第一个元素为起点，沿着行或者列的方向逐个进行。如果是先沿着 列的方向进行，一列完成再进行下一列，那么称为 ；如果先沿着行的方向进行，一行进行完毕再

6、进行下一行，那么称为 。列序为主或列序优先 行序为主或行序优先 P102二选择题1、数据结构是指互相之间存在着一种或多种关系的数据元素的集合，根本的数据结构通常是A、集合结构B、线性结构C、树型结构D图形结构A B C DP93-94 2、算法的根本结构有 。A、顺序结构B、分支结构C、循环结构D跳跃结构A B C P96-97 3、算法的实现方式有 A、子程序B、函数A B C DP98C、模块D 、过程4、以下属于非线性结构的有 。A 、树B 、图C 、 网D、串A B C( P102-105 )5、排序的方法有 _ 。A 、插入排序B、选择排序C 、冒泡排序 D 、快速排序A B C D

7、 (P106-108 )6、递归方法一般用来解决哪些类型的问题？A、数据的定义是按递归定义的B问题解法按递归算法实现C、数据的结构形式是按递归定义的D问题的复杂程度超过一般算法能够解决的A B C D P1097、 下面表达正确的选项是 。A、算法的执行效率与数据的存储结构无关B、算法的空间复杂度是指算法程序中指令或语句的条数C、算法的有穷性是指算法必须能在执行有限个步骤之后终止D、以上三种描述都不对C P958、 以下数据结构中不属于线性数据结构的是 。A、队列B、线性表C、二叉树D栈C P99-104 9、算法的时间复杂度是指 。A、执行算法程序所需要的时间B、算法程序的长度C、算法执行过

8、程中所需要的根本运算次数D、算法程序中的指令条数A P9810、 以下表达中正确的选项是 。A、线性表是线性结构B栈与队列是非线性结构C、线性链表是非线性结构D二叉树是线性结构A P9911、设一棵完全二叉树共有699 个结点，那么在该二叉树中的叶子结点数为 A、 349B、 350C、 255D、 351B P10412、算法的空间复杂度是指 A、算法程序的长度C、算法程序所占的存储空间D P98B算法程序中的指令条数D、 算法执行过程中所需要的存储空间13、 用树形结构来表示实体之间联系的模型称为 。A、关系模型B、层次模型C、网状模型D数据模型B P102 14、算法一般都可以用哪几种控

9、制结构组合而成 。A、循环、分支、递归B顺序、循环、嵌套C、循环、递归、选择D顺序、选择、循环D P9715、数据的存储结构是指 。B、数据的逻辑结构在计算机中的表示D存储在外存中的数据A、数据所占的存储空间量C、数据在计算机中的顺序存储方式B P9416、 在以下选项中，哪个不是一个算法一般应该具有的根本特征 。A、确定性B、可行性C、无穷性D拥有足够的情报CD P9517、 在计算机中，算法是指 。A、查询方法B、加工方法C、解题方案的准确而完整的描述D排序方法C P9518、数据处理的最小单位是 A、数据B、数据元素C P9319、 算法分析的目的是 。A、找出数据结构的合理性 C、分析

10、算法的易懂性和可靠性D P9820、用链表表示线性表的优点是 A、便于插入和删除操作C、花费的存储空间较顺序存储少A B D P99-100 21、栈和队列的共同点是 A、都是先进后出C、只允许在端点处插入和删除元素C P100-101 C、数据项D、数据结构B找出算法中输入和输出之间的关系D分析算法的效率以求改良B数据元素的物理顺序与逻辑顺序相同D便于随机存取B都是先进先出D没有共同点三讨论题1、试比拟快速排序和气泡排序方法。起泡排序首先将第一个记录的关键字与第二个记录的关键字进行比拟，假设与需要的顺序不 符，那么将两个记录交换，然后比拟第二个记录和第三个记录的关键字。依次类推，直至第n-1

11、 个记录和第 n 个记录的关键字进行过比拟为止。起泡排序在排序过程中需进行n-1 趟排序，并作等数量级的记录移动。快速排序是对起泡排序的一种改良。其根本思想是：通过一趟排序将待排记 录分割成独立的两局部，其中一局部记录的关键字均比另一局部记录的关键字小，那么可分别对这 两局部记录进行排序，以到达整个序列有序。在所有同数量级的此类先进的 排序方法中，就平均时间而言，快速排序是目前被认为是最实用的一种排序方法。 P107-108 2、试述递归方法的优缺点。递归策略只需少量的程序就可描述递归是指算法在过程中调用自身作为子算法的一种设计方法。出解题过程所需要的屡次重复计算，大大地减少了程序的代码量。由

12、于递归引起一系列的函数调 用，并且可能会有一系列的重复计算，递归算法的执行效率相对较低。在递归调用的过程当中系 统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出。 P1093、某石油公司方案建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路径 或南或北 与主管道相连。 如果给定 n 口油井的位置， 即它们的 x 坐标和 y 坐标，应如何确定主管道的最优位置，即使各油井到主管道之间的输油管道 长度总和的最小位置？ 提示：选择适宜的数据结构对问题进行描述 解题提示：可以使用微积分中的求最大、最小值的算法4、 考虑对数组 A中的n个数的排序：开始时先找出A的最小元素并放在另一个数组B的第一个位置上。然后找出 A中次最小元素并放在 B的第二个位置上，