全国计算机二级公共基础详细.pdf资源-CSDN文库

版权申诉

40 浏览量 2022-07-14 18:25:05 上传评论收藏 1.45MB PDF 举报

资源详情

资源评论

第1章数据结构与算法

1.1 算法

1.1.1 算法的基本概念

算法是指对解题方案的准确而完整的描述。简单地说，就是解决问题的操作步骤。

值得注意的是，算法不等于数学上的计算方法，也不等于程序。在用计算机解决实际问

题时，往往先设计算法，用某种表达方式（如流程图）描述，然后再用具体的程序设计语言

描述此算法（即编程）。在编程时由于要受到计算机系统运行环境的限制，因此，程序的编

制通常不可能优于算法的设计。

1.1.1.1 算法的基本特征

一般来说，一个算法应具有以下 4个基本特征。

（1）可行性（Effectiveness）：算法在特定的执行环境中执行，应当能够得出满意的结果，

即必须有一个或多个输出。

（2）确定性（ Definiteness）：算法中的每一个步骤都必须有明确的定义，不允许有模棱

两可的解释和多义性。

（3）有穷性（ Finiteness）：算法必需在有限时间内做完，即算法必需能在执行有限个步

骤之后终止。

（4）拥有足够的情报：要使算法有效必需为算法提供足够的情报。当算法拥有足够的情

报时，此算法才是有效的；而当提供的情报不够时，算法可能无效。

1.1.1.2 算法的基本要素

通常，一个算法由两种基本要素组成。

对数据对象的运算和操作；

算法的控制结构，即运算或操作时间的顺序。

（1）算法中对数据的运算和操作

在一般的计算机系统中，基本的运算和操作有以下 4类，如表 1-1所示。

表1-1 4类基本的运算和操作

（2）算法的控制结构

一个算法的功能不仅仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算

法中各操作之间的执行顺序称为算法的控制结构。

算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直

接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、 N-S结构化

流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环 3种基本控制结构组合

而成。

1.1.1.3 算法设计的基本方法

虽然设计算法是一件非常困难的工作，但是算法设计也不是无章可循，人们经过实践，

总结和积累了许多行之有效的方法。常用的几种算法设计方法有列举法、归纳法、递推法、

递归法、减半递推技术和回溯法。

1.1.1.4 算法设计的要求

通常一个好的算法应达到如下目标：

（1）正确性（ Correctness）

正确性大体可以分为以下 4个层次：

①程序不含语法错误；

②程序对于几组输入数据能够得出满足规格说明要求的结果；

③程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明

要求的结果；

④程序对于一切合法的输入数据都能产生满足规格说明要求的结果。

（2）可读性（ Readability ）

算法主要是为了方便人的阅读与交流，其次才是其执行。可读性好有助于用户对算法的

理解；晦涩难懂的程序易于隐藏较多错误，难以调试和修改。

（3）健壮性（ Robustness）

当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出

结果。

（4）效率与低存储量需求

效率指的是程序执行时，对于同一个问题如果有多个算法可以解决，执行时间短的算法

效率高；存储量需求指算法执行过程中所需要的最大存储空间。

1.1.2 算法的复杂度

算法的复杂度是算法效率的度量，是评价算法优劣的重要依据。

算法复杂度包括算法的时间复杂度和算法的空间复杂的。

1.1.2.1 算法的时间复杂度

算法的时间复杂度是指执行算法所需要的计算工作量。

为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与

所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多

细节无关。

算法的计算工作量是用算法所执行的基本运算次数来度量的，而算法所执行的基本运算

次数是问题规模（通常用整数 n表示）的函数。即

算法的工作量 =f（n）

例如，在 N×N矩阵相乘的算法中，整个算法的执行时间与该基本操作（乘法）重复执

行的次数 n

成正比，也就是时间复杂度为 n

，即

f（n） =O（n

）

在有的情况下，算法中的基本操作重复执行的次数还随问题的输入数据集不同而不同。

例如在起泡排序的算法中，当要排序的数组 a初始序列为自小至大有序时，基本操作的执行

次数为 0；当初始序列为自大至小有序时，基本操作的执行次数为 n（n－1）/2。对这类算法，

可以采用平均性态和最坏情况复杂性两种方法来分析。

1.1.2.2 算法的空间复杂度

算法的空间复杂度是指执行这个算法所需要的内存空间。

一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间

以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元

以及某种数据结构所需要的附加存储空间。如果额外空间量相对于问题规模来说是常数，则

称该算法是原地（ in place）工作的。在许多实际问题中，为了减少算法所占的存储空间，

通常采用压缩存储技术，以便尽量减少不必要的额外空间。

1.2 数据结构的基本概念

1.2.1 数据结构的定义

数据结构是计算机科学与技术领域广泛使用的一个基本术语，用来反映数据的内部构

成。在给出数据结构的定义之前，我们先弄清楚几个概念。

数据（ data）：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中

并被计算机程序处理的符号的总称。

数据元素（ data element）：是数据的基本单位，在计算机程序中通常作为一个整体进行

考虑和处理。

数据对象（ data object）：是性质相同的数据元素的集合，是数据的一个子集。

简单地说，数据结构是指相互关联的数据元素的集合，即数据的组织形式。所谓结构，

就是指数据元素之间的前后件关系（或称直接前驱与直接后继关系）。

例如，在考虑一日三餐的时间顺序关系时， " 早餐 " 是" 午餐 " 的前件（或直接前驱），而"

午餐 " 是" 早餐 " 的后件（或直接后继）；同样， "午餐 " 是" 晚餐 " 的前件， " 晚餐 " 是" 午餐 " 的后

件。

又例如，在考虑学历的顺序关系时， " 小学 " 是" 初中 " 的前件，而 " 初中 "是小学的后件。

同样， " 初中 " 是" 高中 " 的前件， " 高中 " 是" 初中 " 的后件。

前后件关系是数据元素之间的一个基本关系，但前后件关系所表示的实际意义随具体对

象的不同而不同。一般来说，数据元素之间的任何关系都可以用前后件关系来描述。

数据结构的两个要素 --" 数据 " 和"结构 " 是紧密联系在一起的， " 数据 " 是有结构的数据，

而不是无关联的、松散的；而 " 结构 " 就是数据元素间的关系，是由数据的特性所决定的。

数据结构作为计算机的一门学科，主要研究和讨论以下三个方面：

（1）数据集合中个数据元素之间所固有的逻辑关系，即数据的逻辑结构；

（2）在对数据元素进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；

（3）对各种数据结构进行的运算。

讨论以上问题的目的是为了提高数据处理的效率，即提高数据处理的速度以及尽量节省

在数据处理过程中所占用的计算机存储空间。

1.2.1.1 数据的逻辑结构

由数据结构的定义可知，一个数据结构应包含以下两方面信息：

（1）表示数据元素的信息；

（2）表示各数据元素之间的前后件关系。

在此定义中，并没有考虑数据元素的存储，所以上述的数据结构实际上是数据的逻辑结

构。

数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和

定义在此集合中的若干关系来表示。

数据的逻辑结构有两个要素：一是数据元素的集合，通常记为 D；二是 D 上的关系，它

反映了数据元素之间的前后件关系，通常记为 R。一个数据结构可以表示成

B= （D，R）

其中 B表示数据结构。为了反映 D中各数据元素之间的前后件关系，一般用二元组来表

示。

例如，如果把一日三餐看作一个数据结构，则可表示成

B=（D ，R）

D={ 早餐，午餐，晚餐 }

R={ （早餐，午餐），（午餐，晚餐） }

数据的逻辑结构包括线性结构、树型结构图、网状结构图和集合图 4种。

1.2.1.2 数据的存储结构

数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理

结构）。在进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，而且

各数据元素在计算机存储空间中的位置关系与它们的逻辑关系可能不同。

由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此，为了表示存

放在计算机存储空间中的各数据元素之间的逻辑关系（即前后件关系），在数据的存储结构

中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。

一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、

索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据

处理时，选择合适的存储结构是很重要的。

1.2.2 数据结构的图形表示

数据结构除了用二元关系表示外，还可以直观地用图形表示。

在数据结构的图形表示中，对于数据集合 D中的每一个数据元素用中间标有元素值的方

框表示，一般称之为数据结点，并简称为结点；为了进一步表示各数据元素之间的前后件关

系，对于关系 R中的每一个二元组，用一条有向线段从前件结点指向后件结点。

例如，例如，一日三餐的数据结构可以用如图 1-5 (a)所示的图形来表示。

又例如，军职数据结构可以用如图 1-5 (b)所示的图形来表示。

在数据结构中，没有前件的结点称为根结点；没有后件的结点称为终端结点（也称为叶

子结点）。

一个数据结构中的结点可能是在动态变化的。根据需要或在处理过程中，可以在一个数

据结构中增加一个新结点（称为插入运算），也可以删除数据结构中的某个结点（称为删除

运算）。插入与删除是对数据结构的两种基本运算。除此之外，对数据结构的运算还有查找、

分类、合并、分解、复制和修改等。

1.2.3 线性结构与非线性结构

如果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。在只有

一个数据元素的数据结构中，删除该数据元素，就得到一个空的数据结构；在一个空的数据

结构中插入一个新的元素后变成非空。

根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类

型：线性结构与非线性结构。

如果一个非空的数据结构满足下列两个条件：

（1）有且只有一个根结点；

（2）每一个结点最多有一个前件，也最多有一个后件。

则称该数据结构为线性结构。

线性结构又称为线性表。由此可见，在线性结构中，各数据元素之间的前后件关系是很

简单的。

需要特别说明的是，在一个线性表中插入或删除任何一个结点后还应是线性结构。

如果一个数据结构不是线性结构，则称之为非线性结构。在非线性结构中，各数据元素

之间的前后件关系要比线性结构复杂。链式结构是总常用的非线性结构。

线性结构与非线性结构都可以是空的数据结构。对于空的数据结构，如果对该数据结构

的运算是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。

1.3 线性表及顺序存储结构

1.3.1 线性表的定义

线性表是一种最简单且最常见的线性数据结构。

线性表是 n（n≥0）个元素构成的有限序列（ a

，a

，…， a

）。表中除了第一个外的每

个元素，有且只有一个前件；除最后一个元素外的每个元素，有且只有一个后件。即线性表

要么是一个空表，要么可以表示为

（a

，a

，…， a

）

其中 a

（i=1，2，…， n）是属于数据对象的元素，通常也称其为线性表中的一个结点。

同一线性表中的数据元素必定具有相同的特性，即属于同一数据对象。

每个数据元素的具体含义，在不同情况下各不相同，它可以是一个数或一个字符，也可

以是一个具体事物，甚至其他更复杂的信息。

例如，英文字母表（ A ，B，C，…， Z）是一个长度为 26的线性表，其中每个字母字符

就是一个数据元素；

线性表中元素的个数 n（n≥ 0）定义为线性表的长度，当 n=0时，称为空表。线性表的

长度是可以变的，当向线性表中插入一个元素时，线性表的长度加 1；当删除线性表中的一

个元素时，线性表的长度减 1。

1.3.2 线性表的顺序存储结构

通常，线性表可以采用顺序存储和链式存储，本小节主要讨论顺序存储结构。

线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素。

线性表的顺序存储结构具备如下两个基本特征：

（1）线性表中的所有元素所占的存储空间是连续的；

（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

用顺序存储结构存储的线性表称为顺序表。在顺序表中，其前、后件两个元素在存储空

间中是紧邻的，且前件元素一定存储在后件元素的前面。

剩余49页未读，继续阅读

评论收藏

内容反馈

版权申诉

全国计算机二级公共基础详细.pdf

评论0

最新资源

全国计算机二级公共基础详细.pdf

评论0

最新资源

相关推荐

计算机二级公共基础知识.pdf

全国计算机二级公共基础知识.pdf

全国计算机2级公共基础知识.pdf

全国计算机等级考试二级公共基础知识教程.pdf

全国VF计算机二级公共基础考点.pdf

计算机二级公共基础参考.pdf

计算机二级公共基础电子书.pdf

计算机二级公共基础试题.pdf

计算机二级公共基础题库.pdf

计算机组成原理课后习题答案

《科研伦理与学术规范》期末考试及答案2023

Latex中文论文模板A4双栏，适用课程论文

哈尔滨工业大学ppt模板

北理工数值分析试题（含2020,2018,2015,2014,2013等）

2024北森题库（含答案）

北京科技大学研究生英语科技论文写作MOOC参考答案

火热！！cfa一级2024最新notes下载

DATA数据治理工程师(CDGA)资料【电子书+学习要点+题库+真题】

大唐杯A组文字题库资料

【word最新版】2023年秋季 信息素养-学术研究的必修课 期末考试答案 研究生MOOC 易搜索.docx

NOC指导教师认证真题

2024年北森测评题库

citespace6.2.4安装包

华为OD机试真题.pdf

全国中小学信息技术创新与实践大赛（NOC）指导教师认证真题

小黑课堂计算机二级WPSOffice题库安装包1.9.exe

考研历年真题2009-2022年 考研408历年真题及解析（含答案与解析）无水印

系统架构设计师第二版-知识点背诵默写本

【word最新版】2023年秋季信息素养-学术研究的必修课期末考试答案研究生MOOC 易搜索.docx

考研历年真题2009-2022年考研408历年真题及解析（含答案与解析）无水印