考研计算机－习题精炼和重点回顾 绪论

考研计算机－习题精炼和重点回顾 绪论内容摘要：

考研计算机－习题精炼和重点回顾 绪论 1对数据结构，下列结论不正确的是 应的存储结构也必相同 储结构和基本操作 3 个方面组成 正确答案是：【A】解析：选项 A 错误的原因是相同的逻辑结构可以由不同的存储结构来实现，例如线性表可以用顺序存储结构和链式存储结构来实现。 数据结构的操作在不同存储结构下有不同的实现。 2以下属于逻辑结构的是 正确答案是：【C 】解析：选项 A、B、D 都属于存储结构。 其中选项 C 有序表是线性表的特例，要求每个元素的值按其逻辑顺序非降序排列，它是逻辑结构。 3若一个问题既可以用迭代方式也可以用递归方式求解，则（ ）的方法具有最高的时空效率。 正确答案是：【A】解析：递归函数在执行过程中会多次重复已做过的计算，还会引起一系列的函数调用和返回，需要较多的时间开销和空间开销。 因此，实现相同功能，迭代算法比递归算法更高效。 4一个递归算法必须包括 正确答案是：【D】解析：递归算法一般有两部分：一是递归部分，它把复杂化简，把规模较大的问题化为规模相对较小的问题求解；另一部分为递归终止条件，即把规模减小到可以直接求解的时候，就通过直接处理的语句给出递归终止的条件。 5下面算法的时间复杂度是（ ）。 i=1,k=100;i=(y+1)*(y+1)y+; A.O(n) B. ) D. 正确答案是：【D】解析：程序每次循环将 y 的值增加 1，然后比较 n 与(y+1)2 大小，所以总共要进行 次比较。 所以算法的时间复杂度为 O( )。 8设 n 为偶数，分析下面程序段中算法的时间复杂度是（ ）。 i,j,m=0;i=1; i<=n; i+) j=2*i; j<=n; j+) m+; A.O(n) B. ) D. 正确答案是：【B】解析：算法的基本操作是 m+，由于内循环从 2*in，即 i 的最大值满足：2in，in/2，所以该语句的频度是9设 n 为正整数，分析下面程序段中加下划线的语句的执行次数是（ ）。 i,j,k,x=0,y=0;i=1; i<=n; i+) j=1; j<=i; j+) k=1; k<=j; k+)x=x+y; A. B. C. D. 正确答案是：【C 】解析：程序段中加下划线的语句的执行次数是：10下面说法错误的是（ ）。 （1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模 n 下，复杂度 O(n)的算法在时间上总是优于复杂度 O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低 A.(1) B.(1),(2) C.(1),(4) D.(3) 正确答案是：【A】解析：算法原地工作的含义指空间复杂度 O(1)据结构分为数据结构，逻辑结构和存储结构。 1）一般情况下，算法中基本运算次数 T(n)是问题规模 n（输入量的多少，称之为问题规模）的某个函数 f(n)，记作：T(n) (f(n) 注意：有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。 常见的渐进时间复杂度有：(1)(n)( (2n) O(n!) O(（2）以下算法的时间复杂度是（ A ）。 f (n) x=1; x=2*x; A.O(B. O(n) C. O(D. O(分析：基本运算是语句 x=2*x，设其执行时间为 T(n)，则有 2T(n)n，。