第一章 概论

一 引言

填空题

1. 简单的说，数据结构是研究非数值计算的程序设计问题中计算机的操作对象以及以及他们之间的关系和操作的一门课程。具体的说，数据结构指的是数据元素之间的逻辑结构，存储结构及其数据的抽象运算。
2. 著名的瑞士计算机科学院沃思（N. Wirth）教授曾提出：算法 + 数据结构 = 程序，这里的数据结构指的是数据的逻辑结构和存储结构，而算法则是对数据运算的描述。

二 基本概念和常用术语

单选题，填空题

1. 数据元素是数据的基本单位
2. 数据对象是具有相同性质的数据元素的集合，是数据的一个子集。
3. 数据项是具有独立含义的最小标识单位

填空题

1. 数据元素之间的逻辑（或抽象）关系，也称为数据的逻辑结构。数据的逻辑结构是从逻辑关系上描述数据的，它与数据元素的存储结构无关，是独立于计算机的。
2. 数据元素及其关系在计算机内的存储方式称为数据的存储结构（物理结构）。
3. 数据的逻辑结构可分为线性结构和非线性结构两大类。

单选题，填空题

1. 顺序存储结构是把逻辑上相邻的结点存储在物理位置上也相邻的连续存储单元里，由此得到的存储结构称为顺序存储结构。
2. 链接存储方法是用一组不一定连续的存储单元存储逻辑上相邻的元素，元素间的逻辑关系是由附加的指针域表示的，由此得到的存储结构称为链式存储结构

三 算法的描述和分析

填空题

1. 假如将算法中基本操作的重复执行次数看成是问题规模n的某个函数f(n)，算法的渐近时间复杂度记作：T(n) = O(f(n))。它表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，其中f(n)一般为算法中频率最大的语句频度。在分析算法时，往往岁算法的时间复杂度和渐近时间复杂度不予区分，而经常是将渐近时间复杂度T(n) = O(f(n))简称为时间复杂度。
2. 一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它是对一个算法在运行过程中临时占用存储空间大小的度量，是问题规模n的函数。

单选题

一个完整算法需要满足五个准则即：输入，输出，有穷性，确定性和可行性。