第1章 绪论

一、选择题

1. 从逻辑结构上可以把数据结构分为( ?c??)。

A. 静态结构和动态结构 ?????B. 紧凑结构和非紧凑结构 ?

C. 线性结构和非线性结构 ???D. 内部结构和外部结构

2. 顺序存储表示中数据元素之间的逻辑关系是由（ ??c???）表示的。

A.?指针??????B. 逻辑顺序 ??????C. 存储位置 ??????D. 问题的上下文

3. 链式存储表示中数据元素之间的逻辑关系是由（ ??A?）表示的。

A.?指针??????B. 逻辑顺序 ??????C. 存储位置 ??????D. 问题的上下文

4. 若某算法的时间复杂度是O(n2?) ，表明该算法（ D?）。

A. 问题规模是n2??????????B. 执行时间是n2????

C. 问题规模与n2成正比 ???D. 执行时间与n2成正比

5. 算法的时间复杂度与（A??）有关。

A. 问题规模 ??????B. 计算机硬件的运行速度 ??

C. 源程序的长度 ??D. 编译后机器代码的质量

6. 算法必须具备（ ?B??）这3个特性

A. 可执行性，可移植性，可扩充性?????B. 可执行性，确定性，有穷性??

C. 确定性，有穷性，稳定性 ??????????D. 易读性，稳定性，安全性

7. 下面程序段的时间复杂度为（ C???）。

for( i=0; i<m; i++)

???for(j=0; j<n; j++)

???????a[i][j]=i*j;

A. O(m2)???????B. O(n2)????????C. O(m×n)??????D. O(m+n)

8. 以下程序段中，S语句的执行次数是（ ?C?） ??

for( i=1; i<=n; i++)

??for(j=i; j<=n; j++)

??????S；

A. ?n ???B. n2???C. n(n+1)/2 ????D. n(n+1)

二、填空题

1. 数据元素之间的4种基本结构是：集合、?图结构?????、??树结构????、??线性结构????。

2. 线性结构中元素的关系是一对一，树形结构中元素的关系是?一对多????????，图形结构中元素的关系是???多对多???????。

3. 顺序存储结构中数据元素的存储位置与其???元素在数组的下标?????是对应的。

4. 算法效率的度量方法有：事后统计方法和??事前分析估算的方法法????????????。

5. 一个好算法应达到的目标有：?正确性?????、?可读性?????、?健壮性?????、??效率????、???低存储量????。

6. 抽象数据类型可细分为3种：??原子类型????、??固定聚合类型??????和?可变聚合类型???????。

7. 抽象数据类型的定义一般包括3方面：?数据对象?????????、?数据关系????????、??基本操作???????。

三、判断题

1. 数据结构主要研究非数值型数据。（??对）

2. 数据的逻辑结构相同则对应的存储结构也相同。（错??）

3. 数据的逻辑结构独立于其存储结构。（ 对?）

4. 数据元素是数据的最小单位。（ 错?）数据项

5. 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。（ 对?）

6. 数据的逻辑结构与数据元素本身的内容和形式无关。（对??）

7. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ 错?）数据元素

8. 抽象数据类型只是一个数学模型。（ 错?）

9. 算法和程序原则上没有区别，在 讨论数据结构时二者是通用的。（ 错?）

10. 数据结构是数据元素的集合和该集合中各数据元素之间关系的集合。（ 对?）

11. 顺序存储方式只能用于线性结构，不能用于非线性结构。（ 错?）

四、简答题

1. 什么是数据结构，写出数据结构的形式定义。

2. 什么是算法，算法的5个特性是什么？

3. 数据的逻辑结构分为线性结构和非线性结构,这两类结构各自的特点是什么?

五、应用题

1. 按增长率从小到大的顺序排列下列各函数：

n2，n，

，n!，(2/3)n 。 ?

2. 写出以下各函数的功能，并求出其时间复杂度。

(1) int fun1(int n)

{ ??int ?i, x;

i=2; ???????x=(int )sqrt(n);

while(i<=x)

{ ?if (n%i==0) ?break;

???i++;

}

if ( i>x) return 1; ???

else ?return 0;

}

(2) int fun2(int n)

???{ ?int i, p=1, sum=0;

??????for( i=1; i<=n; i++)

???????{ ??p=p*i;

???????????sum=sum+p;

???????}

??????return(sum);

???}

(3) int fun3(int n)

{ ?int i, j, p, sum=0;

??????for( i=1; i<=n; i++)

??????{ ?p=1;

?????????for(j=1; j<=i; j++)

????????????p=p*j;

?????????sum=sum+p;

??????}

return(sum);

???}

????????