第1章习题(带答案).doc

1.与数据元素本身的形式、内容、相对位置、个数无关的是数据的 ( )。
A. 存储结构 B. 逻辑结构
C. 算法 D. 操作
2．下列说法中，正确的是 。
A． 数据是数据元素的基本单位
B． 数据元素是数据项中不可分割的最小可标识单位
C． 数据可由若干个数据元素构成
D． 数据项可由若干个数据元素构成
3. 算法的优劣与算法描述语言无关，但与所用计算机有关。（错）
4. 算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。（错）
5.以下是各算法所有语句频度之和的表达式，其中和2n3+3n2+1000时间复杂度相同的是( )
A）TA(n)=2n2+1000n B）TB(n)= n3-n2log2n-1000
C）TC(n)= n2log2n+n2 D）TD(n)= n2+1000
6.在数据结构中，从逻辑上可以把数据结构分为 ( )。
A）动态结构和非动态结构 B)紧凑结构和非紧凑结构
C)线性结构和非线性结构 D)内部结构和外部结构
7.____数据元素_____是数据的基本单位，____数据项_____是数据不可分割的最小单位。
8. 下面的算法计算实数x (x > 0)的非负整数n (n ³ 0)次幂, 其时间复杂度是__ O(log2n) ___。
double Power(double x, int n)
{
double y = 1;
if (n > 0)
{
y = Power(x, n / 2);
y *= y;
if (n % 2 == 1) y *= x;
}
return y;
}
9. 数据元素之间的关系在计算机中有两种不同的表示方法: 顺序映象和_非顺序映象_, 由此得到两种不同的存储结构: 顺序存储结构和__链式存储结构_。
10.常见的存储结构有( 顺序存储 )结构，( 链式存储 )结构等两种。
11.常见的数据结构有( 线性 )结构，( 树形 )结构，( 图状 )结构等三种。
12．下列程序段的时间复杂度是 O(n1/2)
i=0;s=0;
while(s<n)do
{i++;s=s+i;}
13．若某算法中基本语句总的执行次数为f(n)=,则算法的时间复杂度为 。
A．不确定 B. C. D.
14．算法分析的目的是分析算法的效率以加以改进，其包括 两个方面。
A．数据复杂性和程序复杂性 B. 正确性和简明性
C．可读性和文档性 D. 时间复杂性和空间复杂性
15．下列程序段的时间复杂度是 O(nm)
for (i=1;i<=n;i++)
for(j=i;j<=m;j++)
A[i][j]=0;
16．若某算法中基本语句总的执行次数为f(n)=3n2＋5n＋10000,则算法的时间复杂度为_______。
A．O（10000） B. C. D.
17．下列说法中，正确的是 。
A.数据是数据元素的基本单位
B.数据元素是数据的不可分割的最小单位
C.数据项是数据的不可分割的最小单位
D.数据项可由若干个数据元素构成
18．数据结构是指相互之间存在一种或多种特定关系的__ 数据元素___的集合, 而这种关系也称为___逻辑结构 __。
19．下列程序段的时间复杂度是 O（n2） 。
for (i=1;i<=n;i++)
for(j=2;j<=n;j++) A[j][i]=i＋j;
20.以下说法正确的是( )
A、数据元素是数据的最小单位 B、数据项是数据的基本单位
C、数据结构是带有结构的各数据项的集合
D、数据结构是带有结构的数据元素的集合
21.数据不可分割的最小单位是__________。
A．数据元素 B.数据项 C.数据对象 D.数据结构
22.__ 数据元素 是数据的基本单位, 在计算机程序中通常作为一个整体进行考虑和处理。
23.数据的逻辑结构是对数据之间关系的描述, 可分为集合、__线性 _结构、树形结构和__图状__结构。
24.数据的存储结构是数据的逻辑结构在计算机存储器中的实现, 可分为顺序存储、__链式 存储、索引存储和___散列 __存储4种方式。
25.抽象数据类型可表示为三元组(D, S, P)表示, 其中D是数据对象, S是D上的关系, P是对D的__操作 ___。
26.___算法 _是对特定问题求解步骤的一种描述, 是指令的有限序列。
27.下面算法的时间复杂度是___O(n) __。
int Fac(int n)
{
int f;
if (n == 0) f = 1;
else f = n * Fac(n - 1);
return f;
}
28.算法的五个重要特性包括有穷性、确定性、__可行性___、输入和输出。
A) 可行性 B) 健壮性 C) 可读性 D) 稳定性
29. 数据类型是一个值的集合和定义在这个值集上的一组___操作_ _的总称。
30.下面是4种算法的时间复杂度, 其中效率最高的是_____。
A) O(2n) B) O(n2) C) O(log2n) D) O(nlog2n)
31.___ 数据 _是对客观事物的符号表示, 在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
32.一个数据元素可由若干个_数据项 组成, 它是数据的不可分割的最小单位。