数据结构-第1章绪论习题解析

《数据结构-第1章绪论习题解析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》第一章绪论部分习题一、选择题1.下面说法错误的是。(1)算法原地工作的含义是指不需要任何额外的辅助空间。(2)在相同的规模n下，复杂度O(n)的撒在时间上总是优于复杂度O(2n)的算法。(3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。(4)同一个算法，实现语言的级别越高，执行效率越低。A、（1）B、（1）（2）C、（1）（4）D、（3）2.一个递归算法必须包括。A、递归部分B、终止条件和递归部分C、迭代部分D、终止条件和迭代部分3.数据的包括查找、插入、删除、更新、排序等操作类型。A、存储结构B、逻辑结构C、基本运算D、算法描述4.在

2、数据结构中，从逻辑上可以把数据结构分成。A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构5.与数据元素本身的形式、内容、相对位置、个数无关的是数据的。A、存储结构B、存储实现C、逻辑结构D、运算实现6.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着。A、数据具有同一特点B、不仅数据元素所包含的数据项的个数要相同,而且对应数据项的类型要一致C、每个数据元素都一样D、数据元素所包含的数据项的个数要相等7.以下说法正确的是。A、数据元素是数据的最小单位B、数据项是数据的基本单位C、数据结构是带有结构的各数据项的

3、集合D、一些表面上很不相同的数据可以有相同的逻辑结构8.以下说法错误的是。A、程序设计的实质是数据处理B、数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式C、运算实现是完成运算功能的算法或这些算法的设计D、数据处理方式总是与数据的某种相应表示形式相联系，反之亦然9.下列程序段的时间复杂度为。x=n;y=0;while(x>=(y+1)*(y+1))y=y+1;A、O(n)B、O(n1/2)C、O(1)D、O(n2)10.下列叙述中有关好的编程风格的正确描述是。A、程序中的注释是可有可无的B、对递归定义的数据结构不要使用递归过程C、过程应是自封闭的

4、，尽量少使用全程变量D、多采用一些技巧以提高程序的运行效率二、填空题1.一个算法有5个特性：有穷性、确定性、可行性、有零个或多个输入、有一个或多个输出。2.算法的时间复杂度是指该算法所求解问题规模（或频度）的函数。3.算法的可行性是指每一条指令都应在有限的时间内完成。4、线性结构的特征：逻辑上满足有且仅有一个开始结点和一个终端结点，且其余结点有且仅有唯一的一个直接前趋和一个直接后继。5.数据的存储结构被分为顺序、链接、索引存储和散列存储4种。6.从逻辑关系上讲数据结构主要分为两大类，它们是线性结构 和 非线性结构 。 三、给出下列算法的时间复杂度。1、Sum(i

5、ntn){intsum=0,i,j;for(i=1;i<=n;i++){p=1;for(j=1;j<=i;j++)p=p*j;sum=sum+p;}return(sum);}T（n）=O（n2）2、j=1;while(j<=n){j=j*2;}     T（n）=O(log2n)