第4章数据结构与算法习题与答案.pdf

第四章习题（ P111-113） 一、 复习题 1、试述数据和数据结构的概念及其区别。 数据是对客观事物的符号表示，是信息的载体；数据结构则是指互相之间存在着一种或多种关系 的数据元素的集合。 （P93） 2、列出算法的五个重要特征并对其进行说明。 算法具有以下五个重要的特征：有穷性：一个算法必须保证执行有限步之后结束。确切性：算法 的每一步骤必须有确切的定义。 输入：一个算法有 0 个或多个输入， 以刻画运算对象的初始情况， 所谓 0 个输入是指算法本身定除了初始条件。输出：一个算法有一个或多个输出，以反映对输入 数据加工后的结果。没有输出的算法没有实际意义。可行性：算法原则上能够精确地运行，而且 人们用笔和纸做有限次运算后即可完成。 （P95） 3、算法的优劣用什么来衡量？试述如何设计出优秀的算法。 时间复杂度空间复杂度（ P97-98 ） 4、线性和非线性结构各包含哪些种类的数据结构？线性结构和非线性结构各有什么特点？ 线性结构用于描述一对一的相互关系，即结构中元素之间只有最基本的联系，线性结构的特点是 逻辑结构简单。所谓非线性结构是指，在该结构中至少存在一个数据元素，有两个或两个以上的 直接前驱（或直接后继）元素。树型和图型结构就是其中十分重要的非线性结构，可以用来描述 客观世界中广泛存在的层次结构和网状结构的关系。 （P99-105 ） 5、简述树与二叉树的区别；简述树与图的区别。 树用来描述层次结构，是一对多或多对一的关系；二叉树（ Binary Tree ）是个有限元素的集合， 该集合或者为空、 或者由一个称为根 (root) 的元素及两个不相交的、 被分别称为左子树和右子树的 二叉树组成。二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。图也称 做网，是一种比树形结构更复杂的非线性结构。在图中，任意两个节点之间都可能相关，即节点 之间的邻接关系可以是任意的，图表示的多对多的关系。 （P102-P104） 6、请举出遍历算法在实际中使用的例子。 提示：根据实际生活中需要逐个访问处理的情况举例。 7、编写一个算法，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验 证这个算法。 提示：根据查找算法和串中求子串的算法，查找输入串中以单个字符形式的子串。 8、若对有 n 个元素的有序顺序表和无序顺序表进行顺序搜索，试就下列三种情况分别讨论两者 在等搜索概率时的平均搜索长度是否相同 ? (1) 搜索失败； (2) 搜索成功，且表中只有一个关键码等于给定值 k 的对象； (3) 搜索成功，且表中有若干个关键码等于给定值 k 的对象，要求一次搜索找出所有对象。 提示：根据 P106-109 页的查找和排序算法分别进行分析 9、顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下，对有 127 个元 素的顺序表进行插入，平均需要移动多少个元素 ?删除一个元素，又平均需要移动多少个元素 ? 提示：根据 P99 线性表的定义进行分析。题义是进行插入和删除后仍然保持线性表的结构特性。 10、递归的含义是什么？ 递归是指算法在过程中调用自身作为子算法的一种设计方法。 （P109-110 ） 二、 练习题 （一）填空题 1、链表通常是由一个个节点构成的，每个节点的机构是由 _________ 域和 __________ 域构成。 数据域指针域（ P99） 2、树内节点度的最大值，即树中下级节点最多的节点的下级节点个数可被称为 ___________ 。 度的最大值（ P102） 3、数组在存储和处理时是以第一个元素为起点，沿着行或者列的方向逐个进行。如果是先沿着 列的方向进行，一列完成再进行下一列，则称为 ____________ ；如果先沿着行