第四章习题（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、数组在存储和处理时是以第一个元素为起点，沿着行或者列的方向逐个进行。

如果是先沿着列的方向进行，一列完成再进行下一列，则称为____________；如果先沿着行的方向进行，一行进行完毕再进行下一行，则称为____________。

列序为主或列序优先行序为主或行序优先（P102）（二）选择题1、数据结构是指互相之间存在着一种或多种关系的数据元素的集合，基本的数据结构通常是__。

A、集合结构B、线性结构C、树型结构D、图形结构ABCD （P93-94）2、算法的基本结构有_________。

A、顺序结构B、分支结构C、循环结构D、跳跃结构ABC（P96-97）3、算法的实现方式有___________。

A 、子程序B、函数C、模块 D、过程ABCD （P98）4、下列属于非线性结构的有___________。

A 、树B 、图C 、网D、串ABC（P102-105）5、排序的方法有__________。

A 、插入排序B、选择排序 C 、冒泡排序D、快速排序ABCD （P106-108）6、递归方法一般用来解决哪些类型的问题？A 、数据的定义是按递归定义的B、问题解法按递归算法实现C 、数据的结构形式是按递归定义的D、问题的复杂程度超过一般算法能够解决的ABCD （P109）7、下面叙述正确的是______。

A、算法的执行效率与数据的存储结构无关B、算法的空间复杂度是指算法程序中指令（或语句）的条数C、算法的有穷性是指算法必须能在执行有限个步骤之后终止D、以上三种描述都不对C （P95）8、以下数据结构中不属于线性数据结构的是______。

A、队列B、线性表C、二叉树D、栈C（P99-104）9、算法的时间复杂度是指______。

A、执行算法程序所需要的时间B、算法程序的长度C、算法执行过程中所需要的基本运算次数D、算法程序中的指令条数A（P98）10、下列叙述中正确的是______。

A、线性表是线性结构B、栈与队列是非线性结构C、线性链表是非线性结构D、二叉树是线性结构A（P99）11、设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为______。

A、349B、350C、255D、351B（P104）12、算法的空间复杂度是指______。

A、算法程序的长度B、算法程序中的指令条数C、算法程序所占的存储空间D、算法执行过程中所需要的存储空间D（P98）13、用树形结构来表示实体之间联系的模型称为______。

A、关系模型B、层次模型C、网状模型D、数据模型B（P102）14、算法一般都可以用哪几种控制结构组合而成______。

A、循环、分支、递归B、顺序、循环、嵌套C、循环、递归、选择D、顺序、选择、循环D（P97）15、数据的存储结构是指______。

A、数据所占的存储空间量B、数据的逻辑结构在计算机中的表示C、数据在计算机中的顺序存储方式D、存储在外存中的数据B（P94）16、在下列选项中，哪个不是一个算法一般应该具有的基本特征______。

A、确定性B、可行性C、无穷性D、拥有足够的情报C（P95）17、在计算机中，算法是指______。

A、查询方法B、加工方法C、解题方案的准确而完整的描述D、排序方法C（P95）18、数据处理的最小单位是______A、数据B、数据元素C、数据项D、数据结构C（P93）19、算法分析的目的是______。

A、找出数据结构的合理性B、找出算法中输入和输出之间的关系C、分析算法的易懂性和可靠性D、分析算法的效率以求改进D（P98）20、用链表表示线性表的优点是______。

A、便于插入和删除操作B、数据元素的物理顺序与逻辑顺序相同C、花费的存储空间较顺序存储少D、便于随机存取A B D（P99-100）21、栈和队列的共同点是______A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点C（P100-101）（三）讨论题1、试比较快速排序和气泡排序方法。

起泡排序首先将第一个记录的关键字与第二个记录的关键字进行比较，若与需要的顺序不符，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。

依次类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。

起泡排序在排序过程中需进行n-1趟排序，并作等数量级的记录移动。

快速排序是对起泡排序的一种改进。

其基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。

在所有同数量级的此类(先进的)排序方法中，就平均时间而言，快速排序是目前被认为是最实用的一种排序方法。

（P107-108）2、试述递归方法的优缺点。

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

递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

由于递归引起一系列的函数调用，并且可能会有一系列的重复计算，递归算法的执行效率相对较低。

在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。

递归次数过多容易造成栈溢出。

（P109）3、某石油公司计划建造一条由东向西的主输油管道。

该管道要穿过一个有n口油井的油田。

从每口油井都要有一条输油管道沿最短路径（或南或北）与主管道相连。

如果给定n口油井的位置，即它们的x坐标和y坐标，应如何确定主管道的最优位置，即使各油井到主管道之间的输油管道长度总和的最小位置？[提示：选择合适的数据结构对问题进行描述]解题提示：可以使用微积分中的求最大、最小值的算法4、考虑对数组A中的n个数的排序：开始时先找出A的最小元素并放在另一个数组B的第一个位置上。

然后找出A中次最小元素并放在B的第二个位置上，对Ａ中余下的元素继续这个过程。

这个算法称为选择排序，请写出这个算法在其最佳和最坏情况下的时间代价。

解题提示：可以先对含有3个数的数组进行排序，计算时间代价，再依次对含有多个数的数组进行分析，得出最终结果。

5、分别在数组和链表中进行搜索和排序，试比较哪一种操作更简单，说明理由。

解题提示：结合文中的线形结构的存储方法，结合存储方法选择P106-109页的几种排序算法进行比较。