第一章概述习题
一、单选题
1、研究数据结构就是研究( D )。

A、数据的逻辑结构
B、数据的存储结构
C、数据的逻辑结构和存储结构
D、数据的逻辑结构、存储结构及其数据在运算上的实现
2、以下说法正确的是(C )。

A、数据元素是数据的最小单位
B、数据项是数据的基本单位
C、数据结构是带有结构的各数据项的集合
D、一些表面上很不相同的数据可以有相同的逻辑结构.
3、在数据结构中，数据的逻辑结构可以分成（C ）。

A. 内部结构和外部结构
B. 紧凑结构和非紧揍结构
C. 线性结构和非线性结构
D. 动态结构和静态结构
4、数据元素及其关系在计算机存储器内的表示，称为数据的（D ）。

A. 线性结构
B. 非线性结构
C. 逻辑结构
D. 存储结构
5、计算机算法必须具备输入、输出、（ B ）等5个特性。

A 可行性、可移植性和可扩展性
B 可行性、确定性和有穷性
C 确定性、有穷性和稳定性
D 易读性、安全性和稳定性
6、下面关于算法的叙述中错误的是（ A ）。

A. 一个算法应有一个或多个输入。

B. 算法最终必须由计算机程序实现
C. 为解决某问题的算法同为该问题编写的程序含义是相同的
D. 算法中的每条指令都必须有明确的含义
7、若一个算法的时间复杂度用T(n)表示，其中n的含义是（C ）。

A. 循环层数
B. 语句条数
C. 问题规模
D. 函数数量
8、下面说法正确的是（A）。

A. 健壮的算法不会因非法的数据输入而出现莫名其妙的状态
B. 程序一定是算法
C. 算法的时间复杂度只依赖于问题的规模
D. 算法的优劣与算法描述语言无关，但与所用计算机有关
9、下面程序段的时间复杂性的数量级为（C ）
for (i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x=x+1;
A O(1)
B O(n)
C O(n2)
D O(n3)
10、有如下函数fact(n)，其时间复杂度为( C )。

int fac(int n)
{ if(n＜＝1) reurn1;
else return (n*fac(n-1) );
}
A O(n2)
B O(logn)
C O(n)
D O(n1/2)
11、下面说法错误的是（A ）。

(1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法
（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
（4）同一个算法，实现语言的级别越高，执行效率就越低
A．(1) B.(1),(2) C.(1),(4) D.(3)
二、判断题
1.数据元素是数据的最小单位。

（×）
2. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。

（√）
3. 数据的物理结构是指数据在计算机内的实际存储形式。

（√）
4. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的存储结构。

( × )
5. 同一算法，实现语言的级别越高，执行效率就越快。

（×）
三、简答题
设n为正整数。

利用大"O"记号，将下列程序段的执行时间表示为n的函数。

(1) i=1; k=0;
while(i<=n-1)
{
k += 10*i;
i++;
}
答案：O（n）
(2) i=1; j=0;
while(i+j<=n)
{
if(i>j) j++;
else i++;
}
答案：O（n）
(3) x=n; y=0; // n 是不小于1 的常数
while(x>=(y+1)*(y+1))
y++;
答案：O（n1/2）
(4) x=91; y=100;
while(y>0)
{ if(x>100) { x -= 10; y--; }
else x++;
}
答案：O（1）
（5）i=1;
while(i<=n)
i=i*3;
答案：O（logn）。