《数据结构及算法习题及.doc》由会员分享，可在线阅读，更多相关《数据结构及算法习题及.doc（6页珍藏版）》请在金锄头文库上搜索。
1、第四章习题（P111-113）一、复习题1、试述数据和数据结构的看法及其差异。数据是对客观事物的符号表示，是信息的载体；数据结构则是指互相之间存在着一种或多种关系的数据元素的会集。（P93）2、列出算法的五个重要特点并对其进行说明。算法拥有以下五个重要的特点：有穷性：一个算法必定保证执行有限步此后结束。确实性：算法的每一步骤必定有确实的定义。输入：一个算法有0个或多个输入，以刻画运算对象的初始状况，所谓0个输入是指算法自己定除了初始条件。输出：一个算法有一个或多个输出，以反响对输入数据加工后的结果。没有输出的算法没有实质意义。可行性：算法原则上可以精确地运行，而且人们用笔和纸做有限次运算后即可
2、达成。（P95）3、算法的利害用什么来衡量？试述如何设计出优秀的算法。时间复杂度空间复杂度（P97-98）4、线性和非线性结构各包含哪些种类的数据结构？线性结构和非线性结构各有什么特点？线性结构用于描述一对一的互相关系，即结构中元素之间只有最基本的联系，线性结构的特点是逻辑结构简单。所谓非线性结构是指，在该结构中最少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树型和图型结构就是其中十分重要的非线性结构，可以用来描述客观世界中广泛存在的层次结构和网状结构的关系。（P99-105）5、简述树与二叉树的差异；简述树与图的差异。树用来描述层次结构，是一对多或多对一的关系；二叉树（B
3、inaryTree）是个有限元素的会集，该会集也许为空、也许由一个称为根(root)的元素及两个不订交的、被分别称为左子树和右子树的二叉树组成。二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不相同的二叉树。图也称做网，是一种比树形结构更复杂的非线性结构。在图中，任意两个节点之间都可能相关，即节点之间的毗邻关系可以是任意的，图表示的多对多的关系。（P102-P104）6、请举出遍历算法在实质中使用的例子。提示：依照实质生活中需要逐个接见办理的状况举例。7、编写一个算法，统计在一个输入字符串中各个不相同字符出现的频度。用合适的测试数据来验证这个算法。提示：依照查找算法和串中求子串的算法，查找
4、输入串中以单个字符形式的子串。8、若对有n个元素的有序次序表和无序次序表进行次序找寻，试就以下三种状况分别谈论两者在等找寻概率时的平均找寻长度可否相同?(1) 找寻失败；(2)找寻成功，且表中只有一个要点码等于给定值k的对象；(3)找寻成功，且表中有若干个要点码等于给定值k的对象，要求一次找找寻出所有对象。提示：依照P106-109页的查找和排序算法分别进行解析9、次序表的插入和删除要求依旧保持各个元素原来的次序。设在等概率状况下，对有127个元素的次序表进行插入，平均需要搬动多少个元素?删除一个元素，又平均需要搬动多少个元素?提示：依照P99线性表的定义进行解析。题义是进行插入和删除后依旧保
5、持线性表的结构特点。10、递归的含义是什么？递归是指算法在过程中调用自己作为子算法的一种设计方法。（P109-110）二、练习题（一）填空题1、链表平时是由一个个节点组成的，每个节点的机构是由数据域指针域（P99）_域和_域组成。2、树内节点度的最大值，即树中下级节点最多的节点的下级节点个数可被称为度的最大值（P102）_。3、数组在储藏和办理时是以第一个元素为起点，沿着行也许列的方向逐个进行。若是是先沿着列的方向进行，一列达成再进行下一列，则称为_；若是先沿着行的方向进行，一行进行达成再进行下一行，则称为_。列序为主或列序优先行序为主或行序优先（P102）（二）选择题1、数据结构是指互相之间
6、存在着一种或多种关系的数据元素的会集，基本的数据结构平时是A、会集结构B、线性结构C、树型结构D、图形结构ABCD（P93-94）_。2、算法的基本结构有A、次序结构ABC（P96-97）_。B、分支结构C、循环结构D、跳跃结构3、算法的实现方式有A、子程序ABCD（P98）_。B、函数C、模块D、过程4、以部下于非线性结构的有A、树B、图ABC（P102-105）_。C、网D、串5、排序的方法有_。A、插入排序B、选择排序ABCD（P106-108）C、冒泡排序D、快速排序6、递归方法一般用来解决哪些种类的问题？A、数据的定义是按递归定义的C、数据的结构形式是按递归定义的ABCD（P109）
7、B、问题解法按递归算法实现D、问题的复杂程度高出一般算法可以解决的7、下面表达正确的选项是_。A、算法的执行效率与数据的储藏结构没关B、算法的空间复杂度是指算法程序中指令（或语句）的条数C、算法的有穷性是指算法必定能在执行有限个步骤此后停止D、以上三种描述都不对C（P95）8、以下数据结构中不属于线性数据结构的是A、队列B、线性表C（P99-104）_。C、二叉树D、栈9、算法的时间复杂度是指_。A、执行算法程序所需要的时间B、算法程序的长度C、算法执行过程中所需要的基本运算次数A（P98）D、算法程序中的指令条数10、以下表达中正确的选项是_。A、线性表是线性结构B、栈与队列是非线性结构C、
8、线性链表是非线性结构A（P99）D、二叉树是线性结构11、设一棵完满二叉树共有699个结点，则在该二叉树中的叶子结点数为A、349B、350C、255D、351B（P104）_。12、算法的空间复杂度是指_。A、算法程序的长度C、算法程序所占的储藏空间D（P98）B、算法程序中的指令条数D、算法执行过程中所需要的储藏空间13、用树形结构来表示实体之间联系的模型称为_。A、关系模型B、层次模型C、网状模型B（P102）D、数据模型14、算法一般都可以用哪几种控制结构组合而成_。A、循环、分支、递归B、次序、循环、嵌套C、循环、递归、选择D（P97）D、次序、选择、循环15、数据的储藏结构是指_。
9、A、数据所占的储藏空间量B、数据的逻辑结构在计算机中的表示C、数据在计算机中的次序储藏方式B（P94）D、储藏在外存中的数据16、在以下选项中，哪个不是一个算法一般应该拥有的基本特点A、确定性B、可行性C、无量性CD（P95）_。D、拥有足够的情报17、在计算机中，算法是指_。A、盘问方法B、加工方法C（P95）C、解题方案的正确而完满的描述D、排序方法18、数据办理的最小单位是_A、数据B、数据元素C（P93）C、数据项D、数据结构19、算法解析的目的是_。A、找出数据结构的合理性B、找出算法中输入和输出之间的关系C、解析算法的易懂性和可靠性D（P98）D、解析算法的效率以求改进20、用链表
10、表示线性表的优点是_。A、便于插入和删除操作B、数据元素的物理次序与逻辑次序相同C、开销的储藏空间较次序储藏少ABD（P99-100）D、便于随机存取21、栈和队列的共同点是_A、都是先进后出B、都是先进先出C、只赞同在端点处插入和删除元素C（P100-101）D、没有共同点（三）谈论题1、试比较快速排序平和泡排序方法。起泡排序第一将第一个记录的要点字与第二个记录的要点字进行比较，若与需要的次序不符，则将两个记录交换，尔后比较第二个记录和第三个记录的要点字。依次类推，直至第n-1个记录和第n个记录的要点字进行过比较为止。起泡排序在排序过程中需进行n-1趟排序，并作等数量级的记录搬动。快速排序是
11、对起泡排序的一种改进。其基本思想是：经过一趟排序将待排记录切割成独立的两部分，其中一部分记录的要点字均比另一部分记录的要点字小，则可分别对这两部分记录进行排序，以达到整个序列有序。在所有同数量级的此类(先进的)排序方法中，就平均时间而言，快速排序是目前被认为是最合用的一种排序方法。（P107-108）2、试述递归方法的优缺点。递归是指算法在过程中调用自己作为子算法的一种设计方法。递归策略只需少量的程序即可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。由于递归引起一系列的函数调用，而且可能会有一系列的重复计算，递归算法的执行效率相对较低。在递归调用的过程中间系统为每一层的返回点、局部量等开辟了栈来储藏。递归次数过多简单造成栈溢出。（P109）3、某石油公司计划建筑一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路径（或南或北）与主管道相连。若是给定n口油井的地址，即它们的x坐标和y坐标，应如何确定主管道的最优地址，即使各油井到主管道之间的输油管道长度总和的最小地址？提示：选择合适的数据结构对问题进行描述解题提示：可以使用微积分中的求最大、最小值的算法4、考虑对数组A中的n个数的排序：开始时先找出A的最小元素并放在另一个数组B
