期末复习之数据结构 第1章 绪论

目录

一.课本知识点

Q1: 数据类型和抽象数据类型的区别：

Q2：抽象数据类型如何定义？

Q3：抽象数据类型如何表示和实现？

二.练习题

题组一：

题组二：

题组三:

一.课本知识点

对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的集合。——计算机操作对象的总称 例如：数字、字符、汉字、图形、图像、声音等信息 。

数据对象(data object)数据元素数据的一个子集

数据元素(data element)：数据的基本单位

数据项(Data item)：是数据的不可分割的最小单位

数据结构：数据元素

数据结构的形式定义（逻辑结构）
Data_Structure=（D, S）
D：元素的有限集合
S：关系的有限集合

数据结构按数据元素之间关系的不同特性，从逻辑结构上通常有4类基本结构 （1）集合 结构中的数据元素除了“同属于一个集合”外，别无其它关系。 （2）线性结构 结构中的数据元素之间存在一对一的关系，是线性结构。 （3）树形结构 结构中的数据元素之间存在一对多的关系，是非线性结构。 （4）图状结构或网状结构 结构中的数据元素之间存在多对多的关系，是非线性结构

存储结构（物理结构）：逻辑结构在计算中的映象（表示） （1）顺序存储结构 （2）链式存储结构 （3）索引 （4）散列

1. 顺序存储结构：用一组连续的存储单元依次 存储数据元素，数据元素之 间的逻辑关系由元素的存储位置来表示。

2. 链式存储结构:用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示

实现：用结构体，指针
Typedef struct Lnode {
    ElemType         data;         //数据域
     struct Lnode   *next;        //指针域
}

数据操作：在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。
插入、删除、修改、查找、排序

• 数据类型（Data Type）：一组值的集合以及定义于这个值集上的一组操作的总称。
• 抽象数据类型（Abstract Data Type，ADT）: 指一个数学模型（数据结构）以及定义在该模型上的一组操作。 ADT实质上和数据类型是一个概念

Q1: 数据类型和抽象数据类型的区别：

数据类型：高级程序设计语言支持的基本数据类型； ADT：用户自定义的数据类型。定义数据部分和操作部分，只定义到数据的逻辑结构和操作说明，不考虑存储结构和具体实现。

Q2：抽象数据类型如何定义？

例如：

Q3：抽象数据类型如何表示和实现？

抽象数据类型可以通过固有的数据类型（如整型、 实型、字符型等）来表示和实现。 即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。

• 算法：算法是对特定问题求解步骤的一种描述，是指令的有限序列。
• 算法的5个基本特征：

1. 有穷性:一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
2. 确定性：算法中的每一条指令必须有确切的含义，在任何条件下，只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出。
3. 可行性: 算法要足够基本，算法描述的操作可以通过已经实现的基本操作执行有限次来实现
4. 输入: 一个算法有零个或多个输入。
5. 输出: 一个算法有一个或多个输出。

• 算法设计的要求

1. 正确性：首先，算法应当满足具体问题的需求。其次满足下面四个要求。 a.不含语法错误； b.对于某几组输入数据能够得出满足要求的结果； c.程序对于精心选择的典型、苛刻且带有刁难性的组输入数据能够得出满足要求的结果； d.程序对于一切合法的输入数据都能得出满足要求的结果。(算法维护阶段要解决的主要问题)
2. 可读性：算法主要是为了人的阅读与交流，其次才是为计算机执行。晦涩难读的程序易于隐藏较多错误而难以调试；程序设计和编写阶段，都需要易于理解。
3. 健壮性： 当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。 并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。
4. 高效率与低存储量需求：效率指的是算法执行时间； 存储量指的是算法执行过程中所需的最大存储空间。

• 时间复杂度：一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)。算法时间度量记做：T (n) = O(f(n))

• 空间复杂度：S(n) = O( g(n) )
• 算法的存储量包括:

1. 输入数据所占空间：只取决与问题本身，和算法无关
2. 程序本身所占空间：很少，可以忽略；
3. 辅助变量所占空间：只需要分析辅助变量所占额外空间。

二.练习题

题组一：

一．填空题 1. 数据结构被形式地定义为（D, R），其中D是 元素 的有限集合，R是D上的 关系 有限集合。 2. 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。 3. 线性结构中元素之间存在 一对一 关系，树形结构中元素之间存在 一对多 关系，图形结构中元素之间存在 多对多 关系。 4. 数据的存储结构可用四种基本的存储方法表示，它们分别是 顺序 存储结构、 链式 存储结构、索引、散列。 5. 一个算法的效率可分为 时间 效率和 空间 效率。 6．数据结构是研讨数据的_ 逻辑 _结构和_ 存储 _结构，以及它们之间的相互关系，并对与这种结构定义相应的_ 操作运算 _，设计出相应的 算法 _。 7. 下面程序段中带下划线的语句的执行次数的数量级是( n^2 )。 int i=1; while (i<n){ for (int j=1;j<=n;j++){ x=x+1; } i=i*2; } 8.设有数据结构(D, R)，其中 D={d1, d2, d3, d4} R={r}， r={（d1, d2）（d2, d3）（d3, d4）} 问数据结构D是那种类型的数据结构 线性 _。 二．选择题 1．连续存储设计时，存储单元的地址（ A ）。 A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续 2. 数据结构中，与所使用的计算机无关的是数据的 C 结构. A) 存储 B) 物理 C) 逻辑 D) 物理和存储 3. 算法分析的目的是_____C_______ A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性 4. 计算机算法必须具备输入、输出和 B 等5个特性。 A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性 5. 下面说法错误的是（ C ） (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 6．从逻辑上可以把数据结构分为（ C ）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 三．判断题 1. 数据元素是数据的最小单位。( 0 ) 2. 数据项是数据处理的最小单位。 ( 1 ) 3. 数据的逻辑结构是指数据的各数据元素之间的逻辑关系；( 0 ) 4．数据的物理结构是指数据在计算机内的实际存储形式。( 1 ) 5. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( 0 ) 6. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. ( 0 )

题组三: