第一章绪论习题解析

《第一章绪论习题解析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章绪论一，选择题1．组成数据的基本单位是（　）A．数据项　　B．数据类型　　C．数据元素　　D．数据变量数据（data）：对客观事物的符号表示，在计算机科学中指所有能输入到计算机并被计算机程序处理的符号的总称。数据元素（dataelement）：数据的基本单位。在计算机程序中通常作为一个整体进行考虑和处理。数据项（dataitem）：数据的不可分割的最小单位。一个数据元素可由若干个数据项组成。数据对象（dataobject）：性质相同的数据元素的集合，是数据的一个子集。数据结构（datastruc

2、ture）：相互之间存在一种或多种特定关系的数据元素的集合。（数据元素的集合、数据元素之间关系的集合）数据结构形式定义为：数据结构是一个二元组：Data_Structure=(D,S)D是数据元素的有限集，S是D上关系的有限集结构（structure）：数据元素之间的关系。4种基本结构：集合、线性结构、树形结构、图状结构或网状结构。2．数据结构是研究数据的（　）以及它们之间的相互关系。A．理想结构，物理结构　　B．理想结构，抽象结构C．物理结构，逻辑结构　　D．抽象结构，逻辑结构逻辑结构又称逻辑关系，

3、物理结构又称存储结构。数据结构在计算机中的表示称为数据的物理结构（存储结构），又称映像。数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像、非顺序映像。对应的两种存储结构：顺序存储结构、链式存储结构3．算法分析的两个主要方面是（）A．正确性和简单性　　B．可读性和文档性C．数据复杂性和程序复杂性　D．时间复杂度和空间复杂度算法（algorithm）：对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。算法的5个特性：有穷性、确定性、可行性、输入、输出。算法设计的要

4、求：正确性（correctness）、可读性（readability）、健壮性（robustness）、效率与低存储量需求。算法效率的度量：事后统计和事前分析估算。用高级程序语言编写的程序在计算机上运行时消耗的时间取决于：算法选用的策略、问题的规模、书写程序的语言（语言级别越高，执行效率越低）、编译程序所产生机器代码的质量、机器执行指令的速度。时间复杂度（asymptotictimecomplexity）：以基本操作重复执行的次数作为算法的时间度量。有时算法中基本操作重复执行次数随输入数据集不同而不同

5、，所以一般讨论算法在最坏情况下的时间复杂度。空间复杂度（spacecomplexity）4．算法分析的目的是（）。A．找出数据结构的合理性　B．研究算法中的输入和输出的关系C．分析算法的效率以求改进　D．分析算法的易懂性和文档性5.算法的时间复杂度取决于（）A．问题的规模B.待处理数据的初态C.A和B　Ｄ．以上都不是6．一个算法应该是（）。A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.7.下面关于算法说法错误的是（）A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写

6、的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上几个都是错误的算法的确定性说的是指令不能有二义性。8．从逻辑上可以把数据结构分为（）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构9．程序段for(i=n-1;i>=1;i--)for(j=1j<=i;j++)if(A[j]>A[j+1])A[j]与A[j+1]对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（）A．O（n）B．O(nlogn)C.．O(n3)D．O(n2)10．

7、连续存储设计时，存储单元的地址（）。A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续二，判断题1．数据结构的抽象操作的定义与具体实现有关。(×)2．数据结构是数据对象与对象中数据元素之间关系的集合。√（×）数据元素数据元素之间关系3．在顺序存储结构中，有时也存储数据结构中元素之间的关系。×(√)4．数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用的需要建立的。（√）5．算法和程序原则上没有区别，在讨论数据结构是两者是通用的。（×）6．同一数据逻辑结构中的所有数据元素都具有相同的

8、特性是指数据元素所包含的数据项的个数都相等。（×）7．数据的逻辑结构与数据元素本身的内容和形式无关。（√）8．算法的优劣与算法描述语言无关，但与所用计算机有关。(×)9．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。(√)10．算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。(×)三，填空1．数据的物理结构包括数据元素的表示和数据元素间关系的表示。2.对于给定的n个元素,可以构造出的逻辑结构有集合，