《算法与数据结构》练习一(答案)

《《算法与数据结构》练习一(答案)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、习题一一、选择题1、数据结构是一门研究非数值计算的程序设计问题中的操作対象以及它们之间的（B）和运算的学科。A.结构B.关系C.运算D.算法2、在数据结构屮，从逻辑上可以把数据结构分成（C）。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.逻辑结构和存储结构3、线性表的逻辑顺序和存储顺序总是-•致的，这种说法（B）oA・正确B.不正确4、算法分析的目的是（C）oA.找出算法的合理性C.分析算法的冇效性以求改进C.无法确定D.以上答案都不对B.研究算法的输人与输出关系D.分析算法的易懂性二、填空题1、数据是信息的载体，是对客观事物的符号表示，它能够被计

2、算机识别、存储、加工和处理，数拋是对能够冇效的输人到计算机中并R能够被计算机处理的符号的总称。例如,数学中所用到的整数和实数，文本编辑所用到的字符串等。2、数据元素是数据的基本单位,有些情况下也称为元素、结点、顶点、记录等。3、数据项是数据不可分割的最小单元,是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为—数据项。4、简而言Z,数据结构是数据Z间的相互关系,即数据的组织形式。5、数据的逻辑结构是指数据Z间的逻辑关系。逻辑结构是从逻辑关系上描述数据,它与貝体存储无关，是独立于计算机的。因此逻辑结构可以看作是从貝体问题抽象出來的数学模烈。6、数据的

3、存储结构指数据元素及其关系在计算机存储器内的表示。存储结构是逻辑结构在计算机里的实现，也称Z为映像。7、数据的运算是指对数据施加的操作。它定义在数据的逻辑结构Z上，每种逻辑结构都冇一个数据的运算。常用的有：查找、排序、插人、删除、更新等操作。8、数据逻辑结构可以分为四种基本的类型，集合结构川的元素除了仅仅只是同属于一个集介_，不存在什么关系。9、数据逻辑结构的四种基本类型中，线迪丄中的元索是一种一对一的关系，这种结构的特征是：若结构是非空集，则有且只有一个开始结点和一个终端结点，并且所有结点最多只能有一个直接前驱和一个直接后继。10、数据逻辑结构的四种基本类型中，树形结构小的

4、元索是一种一对多的关系。11、图型结构或图状结构是一种多对-多的关系。在这种逻辑结构中，所有结点均可以有多个前驱和多个后继。12、有时也可将树型结构、集合和图型结构称为卄线性结构,这样数据的逻辑结构就可以分为线性结构和非线性结构两大类。13、顺序存储方式是指逻辑上相邻的结点被存储到物理上也相邻的存储单元中。这种存储结构只存储结点的数值，不存储结点之间的关系，结点之间的关系是通过存储单元的相邻关系隐含的表示出来的。14、链接存储方式是种存储方法,不要求逻辑上相邻的结点在物理上也相邻，即数据元素可以存储在任意的位置上。16、散列存储方式是利用结点关键字的值盲接计算出该结点存储单元

5、地址,然后将结点按某种方式存人该地址的一种方法。17、所谓算法（Algorithm）是对特定问题求解方法和步骤的一种描述，它是指令的一组有限序列,其中每个指令表示一个或多个操作。18、算法的鱼L性是指算法必须能够在执行有限个步骤之后结束，并且每个步骤都必须在有穷的时间内完成。19、算法的确定性是指算法中的每一个步骤必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。并且，在任何条件下，算法只能有惟一的一条执行路径，即只要输人是相同的就只能得到相同的输出结果。2（）、算法的可行性又称为算法的能行性,是指算法屮描述的操作是可以通过已经实现的基本运算执行冇限一次来实现,即

6、算法的具体实现应该能够被计算机执行。21、判断一个算法的好坏主要以下几个标准：ill确性,可读煌_、健壮性、效率。22、算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机运行时间的长短和所占据空间的人小。23、空间复朵度（SPaceComplexity）也是度量一个算法好坏的标准，它所描述的是算法在运行过程中所占用存储空间的大小。三、判断题1、顺序存储方式只能用于存储线性结构。（X）树型结构也可以用顺序方式进行存储。2、数据元索是数据的最小单位。（X）数据元索是数据的基木单位，数据项是数据的最小单位。3、算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级

7、语言描述，则算法实际上就是程序了。（X）算法用各种计算机语言描述表现为一个程序，但是不等于程序，程序逻辑不-定能满足有穷性。4、数据结构是带有结构的数据元素的集合。（对）5、数据的逻辑结构是指各元索之间的逻辑关系，是川户根据需要而建立的。（对）6、数据结构、数据元素、数据项在计算机屮的映像分别称为存储结构、结点、数据域。（对）7、数据的物理结构是指数据在计算机中实际的存储形式。（对）8、具有存取任一元素的时间相等这一特点的存储结构称为随机存取结构。（対）四、综合题1、用大O形式表示下而算法的时间复杂度：