1、全国自考数据结构导论（绪论）模拟试卷 1 及答案与解析一、单项选择题1 以下说法中，正确的是_。（A）数据元素是数据这个集合中的个体（B）数据元素均由数据项组成（C）数据项是数据的基本单位（D）数据元素是数据的最小单位2 以下不属于数据的逻辑结构的是_。（A）顺序（B）树（C）图（D）集合3 在数据结构中，从逻辑上可以把数据结构分成_。（A）线性结构和非线性结构（B）紧凑结构和非紧凑结构（C）动态结构和静态结构（D）内部结构和外部结构4 线性表若采用链式存储结构时，要求内存中可用存储单元的地址_。（A）必须是连续的（B）部分地址必须是连续的（C）一定是不连续的（D）连续或不连续都可以5 通常要
2、求同一逻辑结构中的所有数据元素具有相同的特性，这意味着_。（A）每个数据元素都一样（B）数据元素具有同一特点（C）数据元素所包含的数据项的个数要相等（D）不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致6 算法是指_。（A）程序（B）计算方法（C）操作的描述（D）问题求解步骤的描述7 以下有关抽象数据类型的描述中，正确的是_。（A）抽象数据类型是一个值的集合（B）抽象数据类型是数据的逻辑结构及操作的组合（C）抽象数据类型的操作可以没有操作结果（D）抽象数据类型只能用 C 语言来描述8 分析下列程序段的时间复杂度是_。i=1：while(i，画出这个逻辑结构的图示，并确定相对于
3、关系 R，哪些结点是开始结点，哪些结点是终端结点?25 设有如下图所示的逻辑结构，给出它的逻辑结构。26 有如下递归函数 fact(n)，分析其时间复杂度。fact(int n)if(nsqrt(n)print f(”d 是一个素数n”，n);elseprint f(”d 不是一个素数n”，n);(2)s uml (int n) *n 为一个正整数 *int P=1，sum=0 ，i；for(i=1；i，该逻辑结构式一个树形结构，其树根为 k1，叶子结点为 k2、k5、k7 和 k9。【知识模块】 绪论26 【正确答案】 设 fact(n)的运行时间函数是 T(n)。该函数中语句的运行时间是O
4、(1)，语句的运行时间是 T(n 一 1)+O(1)，其中 O(1)为运算的时间。因此则：T(n)=O(1)+T(n 一 1) =2*O(1)+T(n 一 2) =(n 一 1)*O(1)+T(1) =n*O(1) =O(n) 即 fact(n)的时间复杂度为 O(n)。【知识模块】 绪论27 【正确答案】 算法的时间复杂度是由嵌套最深层语句的频度决定的。 (1)prime的嵌套最深层语句： i+； 它的频度由条件(n i)!=0i*10 )。 (2)sum1 的嵌套最深层语句： P*=i；Sum+=p； 它的频度为 n 次，所以其时间复杂度是 O(n)。 (3)sum2 的嵌套最深层语句： P*=j； 它的频度为 1+2+3+n=n(n+1)2 次，所以其时间复杂度是 O(n2)。【知识模块】 绪论28 【正确答案】 该算法中主要语句的频度分别是： n+1 n(n+1) n2 n2(n+1) n3 n2 则时间复杂度为所有语句的频度之和 T(n)=2n3+3n2+2n+1=O(n3)。【知识模块】 绪论
