国家电网招聘考试中公2022国家电网公司招聘考试辅导用书计算机类专业知识

《中公版·2022国家电网公司招聘考试辅导用书：计算机类专业知识》本书具有两大特色：
1.依据大纲，精心研发
依据国家电网公司招聘高校毕业生考试大纲，体例科学。本书内容包含数据结构与算法、数据库系统、计算机网络、操作系统、计算机组成与体系结构、信息新技术六大块知识。
2.双色印刷，重点突出
本书条例清晰、重点突出地讲解国家电网公司招聘考试计算机类专业知识内容。

《中公版·2022国家电网公司招聘考试辅导用书：计算机类专业知识》本书依据国家电网公司招聘高校毕业生考试计算机类专业知识大纲，由中公教育国有企业招聘考试研究中心精心编写。本书的编写目标是让考生全面了解国家电网计算机类专业考试内容，夯实基础，提升能力。

章数据结构与算法（1）
节 数据结构基本概念与算法评价（2）
第二节 线性表（5）
第三节 栈和队列（12）
第四节 数组与特殊矩阵（19）
第五节 树和二叉树（23）
第六节 图（39）
第七节 查找（57）
第八节 内部排序（74）
第九节 外部排序（86）
第二章 数据库系统（89）
节 数据库基本概念（90）
第二节 数据模型（98）
第三节 关系数据库基本理论（103）
第四节 关系数据库标准语言SQL（109）
第五节 关系查询处理和查询优化（125）
第六节 数据库安全性（127）
第七节 数据库完整性（131）
第八节 数据库恢复技术（136）
第九节 并发控制（139）
第十节 关系数据库设计理论（142）
第三章 计算机网络（147）
节 网络基本概念（148）
第二节 数据通信基础理论（156）
第三节 物理层（162）
第四节 数据链路层（168）
第五节 网络层（181）
第六节 运输层（198）
第七节 应用层（208）
第八节 网络安全（213）
第九节 无线网络与移动网络（226）
第四章 操作系统（229）
节 操作系统基本概念（230）
第二节 进程管理（238）
第三节 处理机调度（246）
第四节 存储器管理（256）
第五节 虚拟存储器管理（265）
第六节 I/O设备管理（271）
第七节 文件系统（283）
第五章 计算机组成与体系结构（291）
节 计算机系统基本概念（292）
第二节 数据的机器级表示（299）
第三节 运算方法和运算部件（308）
第四节 指令系统（313）
第五节 中央处理器（321）
第六节 指令流水线（327）
第七节 存储器分层体系结构（330）
第八节 互连与输入输出系统（341）
第六章 信息新技术（355）
节 分布式数据处理（356）
第二节 物联网基础（362）
第三节 大数据基础（369）
第四节 神经网络和机器学习基础知识（374）
第五节 典型硬件技术基础（378）

　　　　章
　　　　数据结构与算法

　　　　一、数据结构基本概念
　　　　（一）与数据结构相关的基本术语
　　　　（1）数据
　　　　数据是描述客观事物的数、字符以及所有能够输入到计算机中并被计算机程序识别和处理的符号的集合。例如，整数、字符串、图像、语音都属于数据。
　　　　（2）数据元素
　　　　数据元素是数据的基本单位，是计算机访问或处理的基本单位。例如，一个班级学生名册中的每个学生记录都属于数据元素。
　　　　（3）数据项
　　　　一个数据元素可以由多个数据项组成。数据项又称字段、域或属性。例如，学生的学号、姓名、性别等都属于数据项，它们组合起来构成一个数据元素。
　　　　（4）数据对象
　　　　数据对象是具有一定关系的相同性质数据元素的集合。例如，一个大写字母就是一个数据元素，由大写字母构成的集合可表示为{A,B,…,Z}，该集合就是一个数据对象。
　　　　（5）数据结构
　　　　数据结构是由与特定问题相关的某一数据元素的集合和该集合中数据元素之间的关系组成的。
　　　　（二）逻辑结构和存储结构
　　　　（1）逻辑结构
　　　　数据的逻辑结构是指数据元素之间的逻辑关系。数据的逻辑结构与数据元素在计算机中存储的位置无关。常见的数据逻辑结构可分为以下几类。
　　　　①集合：集合中的任意两个数据元素之间都没有逻辑关系，只是属于同一个集合，如图1-1-1所示。
　　　　②线性结构：线性结构中的数据元素之间存在“一对一”的关系，如图1-1-2所示。
　　　　③树形结构：树形结构中的数据元素之间存在“一对多”的关系，如图1-1-3所示。
　　　　④图状结构：图状结构中的数据元素之间存在“多对多”的关系，如图1-1-4所示。

　　　　（2）存储结构
　　　　数据的存储结构是指数据元素及其逻辑关系在计算机中的表示，或者说是数据的逻辑结构在计算机存储空间中的存放形式。常见的数据存储结构可分为以下几类。
　　　　①顺序存储：逻辑上相邻的数据元素存放到物理位置上也相邻的存储单元中。使用顺序存储结构可以随机存取数据元素，但是在进行插入和删除操作时需要移动数据元素。
　　　　②链式存储：不要求逻辑上相邻的数据元素在物理位置上也相邻，数据元素之间的逻辑关系由附加的链接指针指示。链式存储结构的存储密度比顺序存储结构小，查找速度也相对较慢，但是插入和删除操作较为灵活。
　　　　③索引存储：在存储数据元素信息的同时，还需要建立附加的索引表。
　　　　④散列存储：根据数据元素的关键字通过一个函数直接计算出该数据元素的存储地址。
　　　　二、算法评价
　　　　（一）算法的定义
　　　　算法是对特定问题求解步骤的一种描述，是一系列解决问题的清晰指令。
　　　　（二）算法的特征
　　　　①有穷性：算法必须在执行有穷步之后终止，即一个算法的操作步骤是有限的。
　　　　②确定性：算法中的每一条指令都必须有确切的含义，并且对于特定的输入有特定的输出。
　　　　③有输入：算法有零个或多个输入，它们是算法开始运算前赋予参与运算的各个变量的初始值。
　　　　④有输出：算法有一个或多个输出，输出的值应是算法计算得出的结果。
　　　　⑤可行性：算法是能够执行的，且算法中每一条运算都必须是足够基本的，也就是说算法中定义的操作都是可以通过可实现的基本运算执行有限次来实现的。
　　　　（三）算法的评价
　　　　评价一个算法的优劣，主要有以下几个标准。
　　　　①正确性：算法在正确的输入条件下能够正确地执行，并且满足具体问题的要求。正确性是评价一个算法优劣重要的标准。
　　　　②健壮性：算法对非法输入的处理能力。当输入的数据非法时，算法也能做出反应或进行适当处理。
　　　　③可读性：算法可供人们阅读的容易程度。可读性好，有助于人们理解、测试和修改算法。
　　　　④空间复杂度：执行算法所需要的存储空间。
　　　　⑤时间复杂度：执行算法所需要的计算工作量。时间复杂度的计算方法如下：
　　　　a.确定算法中的基本操作以及问题的规模。其中，基本操作是指重复执行次数和算法执行时间成正比的操作。简单地说，当基本操作执行完时，算法也就基本结束了。通常情况下，基本操作是内层循环内的语句。
　　　　b.根据基本操作的执行情况计算出n的规模函数f(n)，时间复杂度T(n)=O（ f(n)中增长快的项/此项的系数）。
　　　　在计算时间复杂度时，有的算法中输入的数据规模和数据本身会影响基本操作的执行次数。对于这种情况，如果题目中没有特殊要求，一般按照坏情况来计算，也就是按照使得基本操作执行次数多的输入来计算时间复杂度。
　　　　 例题1 求出以下算法的时间复杂度。（ ）
　　　　void example(int n){
　　　　 int i=1,j=100;
　　　　 while(i　　　　 j;
　　　　 i =2;
　　　　 }
　　　　}
　　　　A.O(n/2) B.O(n2) C.O(n) D.O()
　　　　【答案】C。解析：算法中只有一个while循环，取循环内部的语句作为基本操作， j;和i =2;都可以作为基本操作。由循环条件i　　　　 例题2 求出以下算法的时间复杂度。（ ）
　　　　void example(int n){
　　　　 int i,j,sum=0;
　　　　 for(i=1;i　　　　 for(j=i;j　　　　 sum ;
　　　　}
　　　　A.O(n) B.O(n2)
　　　　C.O(1) D.O(n2/2)
　　　　【答案】B。解析：由于算法中内层循环内的语句是sum ;，因此sum ;是基本操作。显然n为问题规模，可以计算出语句sum ;的执行次数为f (n)=n(n-1)/2=n2/2-n/2，在f (n)中增长快的项为n2/2，因此时间复杂度T(n)=O(n2)。

　　　　一、线性表的基础知识
　　　　（一）线性表的定义
　　　　线性表是一种基本、简单、常用的数据结构。线性表是由n（n≥0）个类型相同的数据元素（简称元素）组成的有限序列。线性表的长度是指线性表中元素的个数。空表是指长度为0的线性表。
　　　　（二）线性表的特点
　　　　若线性表非空，则具有以下特点：
　　　　①线性表中一定存在的个元素。
　　　　②线性表中一定存在的后一个元素。
　　　　③除个元素之外，其他元素有且仅有一个直接前趋（前件）。
　　　　④除后一个元素之外，其他元素有且仅有一个直接后继（后件）。
　　　　⑤线性表中的每一个元素都具有相同的数据类型，且不能是子表。
　　　　⑥线性表中的每一个元素都有位置和值。位置又称下标，决定了该元素在线性表中的位置和前趋、后继的逻辑关系；值是该元素的具体内容。
　　　　⑦线性表中元素的值与它的位置之间可以有特定关系，也可以没有。
　　　　二、线性表的存储结构和基本操作
　　　　（一）线性表的顺序存储结构和基本操作
　　　　线性表的顺序存储结构是指用一组地址连续的存储单元依次存储线性表中的各个元素。在顺序存储结构的线性表中，逻辑结构上相邻的元素在物理存储单元中也相邻。采用顺序存储结构的线性表称为顺序表。
　　　　1.顺序表中元素存储地址的计算
　　　　假设顺序表中有n个元素，每个元素占用m个存储单元，个元素的地址为Loc(a1)，则第i个元素的地址Loc(ai)的计算公式为Loc(ai)=Loc(a1) (i-1)×m。
　　　　 例题 已知一个一维数组采用顺序存储结构存储元素，每个元素占用4个存储单元，第8个元素的地址为144，那么个元素的地址为（ ）。
　　　　A.108 B.180
　　　　C.116 D.112
　　　　【答案】C。解析：每个元素占用4个存储单元，并且第8个元素的地址为144，那么个元素的地址为144-(8-1)×4=116。
　　　　2.顺序表的存储结构
　　　　顺序表的存储结构如图1-2-1所示。
　　　　
　　　　图1-2-1　顺序表的存储结构
　　　　3.顺序表的基本操作
　　　　（1）插入
　　　　在顺序表中插入一个新元素，若要求插入后仍保持表中各元素原来的相对位置关系，就要做元素的成块移动，如图1-2-2所示。

　　　　图1-2-2　顺序表插入元素前、后的状态
　　　　（2）删除
　　　　在顺序表中删除一个元素，若要求删除后仍保持表中各元素原来的相对位置关系，仍需做元素的成块移动，如图1-2-3所示。

　　　　图1-2-3　顺序表删除元素前、后的状态
　　　　（二）线性表的链式存储结构和基本操作
　　　　线性表的链式存储结构是指用一组任意的存储单元来存储线性表中的各个元素，存储单元的地址可以连续，也可以不连续，元素间的逻辑关系由链接指针来指示。
　　　　1.单链表
　　　　（1）单链表的节点结构
　　　　单链表的节点结构如图1-2-4所示。

　　　　图1-2-4　单链表的节点结构
　　　　其中，data表示数据域，用于存放数据；next表示指针域，用于存放下一个节点的位置。
　　　　单链表的一般结构定义如下：
　　　　typedef struct ListNode{
　　　　 int data; //数据域，其数据类型可以根据需求改变
　　　　 struct ListNode *next; //指针域
　　　　}ListNode,*LinkList;
　　　　（2）带头节点的单链表
　　　　带头节点的非空单链表的结构如图1-2-5所示，带头节点的空单链表的结构如图1-2-6所示。

　　　　图1-2-5　带头节点的非空单链表

　　　　图1-2-6　带头节点的空单链表
　　　　设头指针为L，则当前链表为空的条件为L->next==NULL;。
　　　　（3）不带头节点的单链表
　　　　不带头节点的单链表的结构如图1-2-7所示。

　　　　图1-2-7　不带头节点的单链表
　　　　设头指针为L，则当前链表为空的条件为L==NULL;。
　　　　（4）单链表的基本操作
　　　　假设在指针p所指节点ai-1之后插入指针s所指节点x，如图1-2-8所示，操作语句如下：
　　　　s->next=p->next;
　　　　p->next=s;

　　　　图1-2-8　插入节点
　　　　假设删除指针p所指节点ai-1的后继节点（即指针q所指节点ai），如图1-2-9、图1-2-10所示，操作语句如下：
　　　　q=p->next;
　　　　p->next=q->next;
　　　　free(q);

　　　　图1-2-9　删除节点前

　　　　图1-2-10　删除节点后
　　　　2.循环链表
　　　　（1）循环链表的定义
　　　　循环链表又称循环单链表，是单链表的另一种形式，它是一个首尾相接的链表。将单链表中后一个节点的后继指针指向头节点，就得到了循环链表。
　　　　（2）循环链表的三种形态
　　　　循环链表有三种形态，带头节点的空循环链表的结构如图1-2-11所示，带头节点的非空循环链表的结构如图1-2-12所示，带尾指针的循环链表的结构如图1-2-13所示。

　　　　图1-2-11　带头节点的空循环链表

　　　　图1-2-12　带头