第5章 数据结构与算法 习题与答案

第五章习题

(1) 复习题

1、试述数据和数据结构的概念及其区别。 数据是对客观事物的符号表示,是信息的载体;数据结构则是指互相之间存在着一种或多种关系的数据元素的集合。(P113)

2、列出算法的五个重要特征并对其进行说明。

算法具有以下五个重要的特征:有穷性:一个算法必须保证执行有限步之后结束。确切性:算法的每一步骤必须有确切的定义。输入:一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定除了初始条件。输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法没有实际意义。可行性:算法原则上能够精确地运行,而且人们用笔和纸做有限次运算后即可完成。(P115)

3、算法的优劣用什么来衡量?试述如何设计出优秀的算法。 时间复杂度 空间复杂度(P117)

4、线性和非线性结构各包含哪些种类的数据结构?线性结构和非线性结构各有什么特点? 线性结构用于描述一对一的相互关系,即结构中元素之间只有最基本的联系,线性结构的特点是逻辑结构简单。所谓非线性结构是指,在该结构中至少存在一个数据元素,有两个或两个以上的直接前驱(或直接后继)元素。树型和图型结构就是其中十分重要的非线性结构,可以用来描述客观世界中广泛存在的层次结构和网状结构的关系。(P118 P122)

5、简述树与二叉树的区别;简述树与图的区别。

树用来描述层次结构,是一对多或多对一的关系;二叉树(Binary Tree)是个有限元素的集合,该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。二叉树是有序的,即若将其左、右子树颠倒,就成为另一棵不同的二叉树。图也称做网,是一种比树形结构更复杂的非线性结构。在图中,任意两个节点之间都可能相关,即节点之间的邻接关系可以是任意的,图表示的多对多的关系。(P121-P124)

6、请举出遍历算法在实际中使用的例子。

提示:根据实际生活中需要逐个访问处理的情况举例。

7、编写一个算法,统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。

提示:根据查找算法和串中求子串的算法,查找输入串中以单个字符形式的子串。

8、若对有n个元素的有序顺序表和无序顺序表进行顺序搜索,试就下列三种情况分别讨论

两者在等搜索概率时的平均搜索长度是否相同? (1) 搜索失败; (2) 搜索成功,且表中只有一个关键码等于给定值k的对象; (3) 搜索成功,且表中有若干个关键码等于给定值k的对象,要求一次搜索找出所有对象。

提示:根据P125-127页的查找和排序算法分别进行分析

9、顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下,对有127个元素的顺序表进行插入,平均需要移动多少个元素?删除一个元素,又平均需要移动多少个元素?

提示:根据线性表的定义进行分析。题义是进行插入和删除后仍然保持线性表的结构特性。

10、递归的含义是什么?

递归是指算法在过程中调用自身作为子算法的一种设计方法。(P128)

(2) 练习题

1、链表通常是由一个个节点构成的,每个节点的机构是由_________域和__________域构成。数据域 指针域(P119) 2、树内节点度的最大值,即树中下级节点最多的节点的下级节点个数可被称为___________。 度的最大值(P122)

3、数组在存储和处理时是以第一个元素为起点,沿着行或者列的方向逐个进行。如果是先沿着列的方向进行,一列完成再进行下一列,则称为____________;如果先沿着行的方向进行,一行进行完毕再进行下一行,则称为____________。 列序为主或列序优先 行序为主或行序优先(P120)

5、数据结构是指互相之间存在着一种或多种关系的数据元素的集合,基本的数据结构通常是___________、 ___________、___________、___________。 集合结构 线性结构 树型结构 图形结构(P113)

6、算法的基本结构有___________、___________、___________。 顺序结构 分支结构 循环结构 (P116)

7、算法的实现方式有___________、________、________、________等。 子程序 函数 模块 过程 (P117)

8、下列属于非线性结构的有___________ D(P118 P124) A 、树 B 、图 C 、 网 D、 串

9、排序的方法有__________、__________、__________、__________。 插入排序 选择排序 气泡排序 快速排序(P126)

10、递归方法一般用来解决哪些类型的问题__________、__________、__________。 数据的定义是按递归定义的 问题解法按递归算法实现 数据的结构形式是按递归定义的(P128)

11、下面叙述正确的是______。 C(P114-P116) A、算法的执行效率与数据的存储结构无关 B、算法的空间复杂度是指算法程序中指令(或语句)的条数 C、算法的有穷性是指算法必须能在执行有限个步骤之后终止 D、以上三种描述都不对

12、以下数据结构中不属于线性数据结构的是______ C(P118) A、队列 B、线性表 C、二叉树 D、栈

13、 算法的时间复杂度是指______。 A(P117) A、执行算法程序所需要的时间 B、算法程序的长度 C、算法执行过程中所需要的基本运算次数 D、算法程序中的指令条数

14、下列叙述中正确的是______。A(P118) A、线性表是线性结构 B、栈与队列是非线性结构 C、线性链表是非线性结构 D、二叉树是线性结构

15、算法的空间复杂度是指______。 D(P117) A、算法程序的长度 B、算法程序中的指令条数 C、算法程序所占的存储空间 D、 算法执行过程中所需要的存储空间

16、用树形结构来表示实体之间联系的模型称为______。B(P121) A、关系模型 B、层次模型和网状模型 C、数据模型

17、算法一般都可以用哪几种控制结构组合而成______。D(P116) A、循环、分支、递归 B、顺序、循环、嵌套 C、循环、递归、选择 D、顺序、分支、循环

18、数据的存储结构是指______。 B(P113) A、数据所占的存储空间量 B、数据的逻辑结构在计算机中的表示 C、数据在计算机中的顺序存储方式 D、存储在外存中的数据

19、在下列选项中,哪个不是一个算法一般应该具有的基本特征______。 D(P115) A、确定性 B、可行性 C、无穷性 D、拥有足够的情报

20、在计算机中,算法是指______。 C(P114) A、查询方法 B、加工方法 C、解题方案的准确而完整的描述 D、排序方法

21、线性表的顺序存储结构和线性表的链式存储结构分别是______。 B(P118) A、顺序存取的存储结构、顺序存取的存储结构

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4