一、单项选择题

1. 数据结构是研究非数值计算问题中的数据对象以及它们之间的（　）和操作算法的学科。

A. 结构

B. 关系

C. 运算

D. 算法

2. 在数据结构中，与所使用的计算机无关的是数据的（　）结构。

A. 存储

B. 物理

C. 逻辑

D. 物理和存储

3. 以下数据结构中，（　）是非线性数据结构。

A. 集合

B. 线性表

C. 数组

D. 树

4. 计算机算法是指（　）。

A. 计算方法

B. 排序方法

C. 解决问题的有限运算序列

D. 调度方法

5. 算法分析的目的是（　）。

A. 找出数据结构的合理性

B. 研究算法中的输入和输出的关系

C. 分析算法的效率以求改进

D. 分析算法的易懂性和文档性

6. 某个算法的时间复杂度为 O （ n ² ），表明该算法的（　）。

A. 问题规模是 n ²

B. 问题规模与 n ² 成正比

C. 执行时间是 n ²

D. 执行时间与 n ² 成正比

二、填空题

1. 根据数据元素间存在的逻辑关系不同，数据的逻辑结构分为__________、__________、__________和__________；在计算机内采用不同方式表示这些逻辑关系，因而存储结构有__________和__________两种。

2. 算法的5个重要特性是__________、__________、__________、输入、输出。

3. 算法健壮性是指____________________。

4. 已知如下程序段

其中，语句1的执行次数为__________；语句2的执行次数为__________。

三、简答

1. 简述数据结构与数据类型的区别与联系。

2. 简述程序与算法的区别与联系。

3. 算法具有什么特性？评价算法好坏的指标有哪些？

4. 数据的逻辑结构和存储结构分别有哪些种类？

5. 何谓抽象数据类型？请你谈谈对它的理解。

6. 分析以下各程序段的时间复杂度。

（1）i=1；s=0；

while（i＜n）

{s=s+10*i；

i++；

}

（2）i=1；j=0；

while（i+j＜n）

if（i＞j）j++；

else i++

（3）y=1；

while（y*y＜=n） y=y+1；

（4）i=n；

while（i＞0）i=i/2；

（5）for（i=1；i＜=n；i++）

for（j=1；j＜=n；j++）

for（k=1；k＜=n；k++）

s++；

（6）for（i=1；i＜=n；i++）

for（j=1；j＜=i；j++）

s++；

（7）设 n 是偶数，运行下面的程序段后，计算语句m=m+1的次数，并给出该程序段的时间复杂度。

7. 对下列用二元组表示的数据结构，试分别画出对应的逻辑结构图，并指出属于何种结构。

（1） A =（ D ， R ），其中 D ={ x ， y ， z ， p }， R ={}；

（2） B =（ D ， R ），其中 D ={ a ， b ， c ， d ， e }， R ={（ a ， b ），（ b ， e ），（ e ， d ），（ d ， c ）}；

（3） G =（ D ， R ），其中 D ={ a ， b ， c ， d ， e }， R ={（ a ， d ），（ c ， e ），（ b ， e ），（ a ， b ），（ b ， c ），（ d ， e ）}；

（4） T =（ D ， R ），其中 D ={1，2，3，4，5，6}， R ={（6，5），（6，2），（2，3），（2，4），（2，1）}； Qg68xRgNLL2Alt4PKwolzIobK89BAecSuba1H8NUaYBpz8tjuCTiuUfvlL1EXv6r