数据结构第一章绪论

格式：ppt
大小：363.00 KB
文档页数：43

《数据结构》习题汇编01 第一章绪论试题

《数据结构与算法设计》习题册

第一章绪论

一、单项选择题

1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 ① 以及它们之间的 ②

和运算等的学科。

①A. 数据元素 B. 计算方法 C. 逻辑存储 D. 数据映象

②A. 结构 B. 关系 C. 运算 D. 算法

2. 数据结构被形式地定义为（K，R），其中K是 ① 的有限集，R是K上的 ② 有限集。

①A. 算法 B. 数据元素 C. 逻辑结构 D. 数据操作

②A. 操作 B. 存储 C. 映象 D. 关系

3. 在数据结构中，从逻辑上可以把数据结构分成。

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

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

4. 数据结构在计算机内存中的表示是指。

A. 数据的存储结构 B. 数据结构

C. 数据的逻辑结构 D. 数据元素之间的关系

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

A. 逻辑 B. 存储 C. 逻辑和存储 D. 物理

6. 算法分析的目的是 ① ，算法分析的两个主要方面是 ② 。

①A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系

C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性

②A. 空间复杂度和时间复杂度 B. 正确性和简明性

C. 可读性和文档性 D. 数据复杂性和程序复杂性

7. 计算机算法指的是 ① ，它必须具备输入、输出和 ② 等5个特性。

①A. 计算方法 B. 排序方法

C. 解决问题的有限运算序列 D. 调度方法

②A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性

C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性

数据结构复习资料第一章绪论

第一章绪论

第 1 页（共 55 页）

第一章绪论

重点：理解算法五个要素的确切含义：①动态有穷性（能执行结束）；②确定性（对于相同的输入执行相同的路径）；③有输入；④有输出；⑤可行性（用以描述算法的操作都是足够基本的）。掌握计算语句频度和估算算法时间复杂度的方法。

难点：抽象数据类型的定义、表示和实现方法，算法时间复杂度的分析。

1.1 数据结构的基础知识

一．什么是数据结构？

一般地，用计算机解决一个具体问题时，大致需要以下几个步骤：

① 找出求解问题的数学模型

② 设计一个算法（解此模型的）

③ 编程调试

下面通过三个典型例子来说明数据结构的概念及所讨论的问题。

例1 图书馆的书目检索系统自动化问题

诸如此类的还有查号系统自动化、仓库帐目管理等。在这类文档管理的数学模型中，计算机处理的对象之间通常存在着的是一种最简单的线性关系，这类数学模型称为线性的数据结构。

例2人机对弈

解决这类问题的数学模型可称为“树形”数据结构。

“树”可以是某些非数值计算问题的数学模型，它也是一种数据结构，是一种非线性的树形数据结构。

例3多叉路口交通灯的管理问题

通常，这种交通、道路问题的数学模型是一种称为“图”的数据结构，是一种复杂的非线性的图形数据结构。

综上所述，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如第一章绪论

第 2 页（共 55 页）表、树和图之类的数据结构。

因此，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

习题-第一章绪论-数据结构

第一章绪论

1.1 简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

1.3下面程序段的时间复杂度是多少？

（1） i=s=0;

while (s

{i++;

s+=i;

}

(2) s=0;

for (i=0;i

for (j=0;j

s+=B[i][j]

sum=s;

(3) i=1;

while (i<=n)

i=i*3;

1.4 有数据逻辑结构为：

B=(K,R)

K={K1,K2,……,K9}

R={,,,,,,,,,,}

画出这个逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？

1.5 设有如图所示的逻辑结构图示，给出它的逻辑结构。

K2 K3

K6 K4

K8 K7 K5