第一章绪论习题解析(答).doc

《数据结构》第一章绪论部分习题 一、选择题 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. 在数据结构中，从逻辑上可以把数据结构分成 。 A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 5. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的 。 A、存储结构 B、存储实现 C、逻辑结构 D、运算实现 6. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 。 A、数据具有同一特点 B、不仅数据元素所包含的数据项的个数要相同,而且对应数据项的类型要一致 C、每个数据元素都一样 D、数据元素所包含的数据项的个数要相等 7. 以下说法正确的是 。 A、数据元素是数据的最小单位 B、数据项是数据的基本单位 C、数据结构是带有结构的各数据项的集合 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、过程应是自封闭的，尽量少使用全程变量 D、多采用一些技巧以提高程序的运行效率 二、填空题 1. 一个算法有5个特性：有穷性 、 确定性 、 可行性、有零个或多个输入、有一个或多个输出。 2. 算法的时间复杂度是指该算法所求解问题规模（或频度）的函数。 3. 算法的可行性是指每一条指令都应在有限的时间内完成。 4、线性结构的特征：逻辑上满足有且仅有一个开始结点和一个终端结点，且其余结点有 且仅有唯一的一个直接前趋和一个直接后继。 5. 数据的存储结构被分为顺序 、 链接、索引存储和散列存储4种。 6. 从逻辑关系上讲数据结构主要分为两大类，它们是线性结构? 和? 非线性结构?。? 三、给出下列算法的时间复杂度。 1、Sum(int n) { int sum=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)