2025年软考软件设计师专题九数据结构知识.pdfVIP

专题九：数据构造知识

数据构造是计算机软件的一门基础课程,计算机科学各个领域及有的应用软件都要用到

多种数据构造.语言编译要使用栈、散列表及语法树；操作系统中用队列、存储管理表及目录

树等；数据库系统运用线性表、多链表及索引树等进行数据管理；而在人工智能领域，依求解

问题性质的差异将波及到多种不一样的数据构造，如广义表、集合、有哪些信誉好的足球投注网站树及多种有向图等等。

学习数据构造目的是要熟悉某些最常用的数据构造，明确数据构造内在的逻辑系，懂得它们

在计算机中的存储表达，并结合多种经典应用阐明它们在进行多种操作时的动态性质及实际的

执行算法，深入提高软件计和编程水平。通过对不一样存储构造和对应算法的对比，增强我们

根据求解问题的性质选择合理的数据构造，并将问题求解算法的空间、时间及复杂性控制在一

定范围的能力。

软件设计师考试大纲对数据构造部分的规定是纯熟掌握常用数据构造和常用算法，因此，

本专题从数据构造的概述出发，对基本的概念引出常用的数据构造类型的简介和讲解，同步在

讲解多种数据构造中间采用算法与数据构造相结合的方式，在算法环节中使用数据构造，对数

据构造的重点、难点进行了分析，最终讲解了与数据构造紧密有的排序和查找算法，以及某

些以往考试题的分析。

1.数据构造概述

数据构造研究了计算机需要处理的数据对象和对.象之间的系；刻画了应用中波及

到的数据的逻辑组织；也描述了数据在计算机中怎样存储、传送、转换。

学习数据构造注意的问题：

■系统掌握基本数据构造的特点及其不一样实现。

■理解并掌握多种数据构造上重要操作的实现及其性能（时间、空间）的分析。

■掌握多种数据构造的使用特性，在算法设计中可以进行选择。

■掌握常用的递归、回溯、迭代、递推等措施的设计

■掌握自顶向下、逐渐求精的程序设计措施。

■掌握自顶向下、逐渐求精的程序设计措施。

在学习数据构造的知识之前，我们要理解一下数据构造中的基本概念。

数据：对客观事物的符号表达，在计算机中就是指所有能输入到计算机中并被计算机程序

所处理的符号的总称。

数据项是数据的不可分割的最小单位;

数据元素是数据的基本单位，在计算机程序中一般作为一种整体进行处理；一种数据元素

可由若干个数据项构成。

数据对象是性质相似的数据元素的集合，是数据的一种子集。

数据构造上的基本操作

♦插入操作♦删除操作♦更新操作♦查找操作♦排序操作

数据构造是指数据对象及互相关系和构造措施，一种数据构造B形式上可以用一种

二元组表达为B=（A,R）o其中，A是数据构造中的数据（称为结点）的#空有限集合，

R是定义在A上的关系的非空有限集合。

根据数据元素之间的关系的不一样特性，一般有下列4类基本构造。

集合一一构造中的数据元素除了“同属于一种集合”的关系外，别无其他

关系。

线性构造一一构造中的数据元素之间存在一种对一种的关系。

树形构造一一构造中的元素之间存在一种对多种的关系。

图状构造或网状构造一一构造中的元素之间存在多种对多种的关系。

数据构造中，结点与结点间的互相关系是数据的逻辑构造。数据构造在计算机中的

表达（又称为映象）称为数据的物理构造，也称存储构造。

数据元素之间的关系在计算机中有两种不一样的表达方式次序映象和非次序映象，

并由此得到两种不一样的存储构造次序存储构造和旌式存储构造。

任何一种算法的设计取决于选定的数据（逻辑）构造，而算法的实现依赖于采用的

存储构造。

数据的逻辑构造分为两类

线性构造线性表、栈、