目录
对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的集合。——计算机操作对象的总称 例如:数字、字符、汉字、图形、图像、声音等信息 。
数据对象(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; //指针域
}
数据操作:在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。
插入、删除、修改、查找、排序
数据类型:高级程序设计语言支持的基本数据类型; ADT:用户自定义的数据类型。定义数据部分和操作部分,只定义到数据的逻辑结构和操作说明,不考虑存储结构和具体实现。
例如:
抽象数据类型可以通过固有的数据类型(如整型、 实型、字符型等)来表示和实现。 即利用处理器中已存在的数据类型来说明新的结构,用已经实现的操作来组合新的操作。
一.填空题 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 )