国家二级计算机公共基础知识考试考点.pdf_计算机二级基础知识资源-CSDN文库

版权申诉

61 浏览量 2022-07-14 20:10:36 上传评论收藏 238KB PDF 举报

资源详情

资源评论

2009年全国计算机等级考试 ( 二级公共基础知识 ) 考试考点

第一章数据结构与算法

经过对部分考生的调查以及对近年真题的总结分析，笔试部分经常考查的是算法复杂

度、数据结构的概念、栈、二叉树的遍历、二分法查找，读者应对此部分进行重点学习。

详细重点学习知识点：

1．算法的概念、算法时间复杂度及空间复杂度的概念

2．数据结构的定义、数据逻辑结构及物理结构的定义

3．栈的定义及其运算、线性链表的存储方式

4．树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历

5．二分查找法

6．冒泡排序法

1.1 算法

考点1 算法的基本概念

考试链接：

考点1在笔试考试中考核的几率为 30%，主要是以填空题的形式出现，分值为 2分，此考点为识记内容，读

者还应该了解算法中对数据的基本运算。

计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。

1．算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。

2．算法的基本要素：

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

一个算法由两种基本要素组成：一是对数据对象的运算和操作；二是算法的控制结构。

在一般的计算机系统中，基本的运算和操作有以下 4类：算术运算、逻辑运算、关系运算和

数据传输。

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

描述算法的工具通常有传统流程图、 N-S结构化流程图、算法描述语言等。一个算法一

般都可以用顺序、选择、循环 3种基本控制结构组合而成。

考点 2 算法复杂度

考试链接：

考点2在笔试考试中，是一个经常考查的内容，在笔试考试中出现的几率为 70%，主要是以选择的形式出现，

分值为2分，此考点为重点识记内容，读者还应该识记算法时间复杂度及空间复杂度的概念。

1.算法的时间复杂度

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

同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机

上运行，效率均不同。这表明使用绝对的时间单位衡量算法的效率是不合适的。撇开这些与

计算机硬件、软件有关的因素，可以认为一个特定算法 " 运行工作量 " 的大小，只依赖于问题

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

算法的工作量 =f （n）

2.算法的空间复杂度

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

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

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

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

称该算法是原地工作的。在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩

存储技术，以便尽量减少不必要的额外空间。

疑难解答：算法的工作量用什么来计算？

算法的工作量用算法所执行的基本运算次数来计算，而算法所执行的基本运算次数是问题规模的函数，

即算法的工作量 =f（n），其中 n是问题的规模。

1.2 数据结构的基本概念

考点3 数据结构的定义

考试链接：

考点3在笔试考试中，是一个经常考查的内容，在笔试考试中出现的几率为 70%，主要是以选择的形式出现，

分值为2分，此考点为识记内容，读者还应该识记数据的逻辑结构和存储结构的概念。

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

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

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

构；

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

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

机程序处理的符号的总称。

数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

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

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

定义在此集合中的若干关系来表示。数据的逻辑结构有两个要素：一是数据元素的集合，通

常记为 D；二是 D上的关系，它反映了数据元素之间的前后件关系，通常记为 R。一个数据

结构可以表示成

B=（D，R）

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

示。

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

结构）。

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

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

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

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

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

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

考点4 线性结构与非线性结构

考试链接：

考点4在笔试考试中，虽然说不是考试经常考查的内容，但读者还是对此考点有所了解，在笔试考试中出现

的几率为 30%，主要是以填空题出现的形式出现，分值为 2分，此考点为识记内容。

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

型：线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件：

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

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

则称该数据结构为线性结构。线性结构又称线性表。在一个线性结构中插入或删除任何

一个结点后还应是线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。

疑难解答：空的数据结构是线性结构还是非线性结构？

一个空的数据结构究竟是属于线性结构还是属于非线性结构，这要根据具体情况来确定。如果对该数

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

1.3 栈及线性链表

考点5 栈及其基本运算

考试链接：

考点5在笔试考试中，是一个必考的内容，在笔试考试中出现的几率为 100%，主要是以选择的形式出现，

分值为2分，此考点为重点掌握内容，读者应该掌握栈的运算。

1．栈的基本概念

栈是限定只在一端进行插入与删除的线性表，通常称插入、删除的这一端为栈顶，另一

端为栈底。当表中没有元素时称为空栈。栈顶元素总是后被插入的元素，从而也是最先被删

除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。栈是按照 "

先进后出 "或 " 后进先出 " 的原则组织数据的。

2．栈的顺序存储及其运算

用一维数组 S（1∶m）作为栈的顺序存储空间，其中 m为最大容量。

在栈的顺序存储空间 S（1∶m）中，S（ bottom ）为栈底元素， S（top）为栈顶元素。 top=0

表示栈空； top=m表示栈满。

栈的基本运算有三种：入栈、退栈与读栈顶元素。

（1）入栈运算：入栈运算是指在栈顶位置插入一个新元素。首先将栈顶指针加一（即

top加1），然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后

一个位置时，说明栈空间已满，不可能再进行入栈操作。这种情况称为栈 " 上溢 " 错误。

（2）退栈运算：退栈是指取出栈顶元素并赋给一个指定的变量。首先将栈顶元素（栈

顶指针指向的元素）赋给一个指定的变量，然后将栈顶指针减一（即 top减 1）。当栈顶指针

为0时，说明栈空，不可进行退栈操作。这种情况称为栈的 " 下溢 " 错误。

（3）读栈顶元素：读栈顶元素是指将栈顶元素赋给一个指定的变量。这个运算不删除

栈顶元素，只是将它赋给一个变量，因此栈顶指针不会改变。当栈顶指针为 0时，说明栈空，

读不到栈顶元素。

小技巧：栈是按照 " 先进后出 " 或" 后进先出 " 的原则组织数据，但是出栈方式有多种选择，在考题

中经常考查各种不同的出栈方式。

考点6 线性链表的基本概念

考试链接：

考点6在笔试考试中出现的几率为 30%，主要是以选择的形式出现，分值为 2分，此考点为识记内容。重点

识记结点的组成。

在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数

据域，另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结

点（即前件或后件）。

链式存储方式既可用于表示线性结构，也可用于表示非线性结构。

（1）线性链表

线性表的链式存储结构称为线性链表。

在某些应用中，对线性链表中的每个结点设置两个指针，一个称为左指针，用以指向其

前件结点；另一个称为右指针，用以指向其后件结点。这样的表称为双向链表。

（2）带链的栈

栈也是线性表，也可以采用链式存储结构。带链的栈可以用来收集计算机存储空间中所

有空闲的存储结点，这种带链的栈称为可利用栈。

疑难解答：在链式结构中，存储空间位置关系与逻辑关系是什么？

在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的

逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。

1.4 树与二叉树

考点7 树与二叉树及其基本性质

考试链接：

考点7在笔试考试中，是一个必考的内容，在笔试考试中出现的几率为 100%，主要是以选择的形式出现，

有时也有出现在填空题中，分值为 2分，此考点为重点掌握内容。重点识记树及二叉树的性质。

误区警示：

满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。应该注意二者的区别。

1、树的基本概念

树(tree）是一种简单的非线性结构。在树结构中，每一个结点只有一个前件，称为父结

点，没有前件的结点只有一个，称为树的根结点。每一个结点可以有多个后件，它们称为该

结点的子结点。没有后件的结点称为叶子结点。

在树结构中，一个结点所拥有的后件个数称为该结点的度。叶子结点的度为 0。在树中，

所有结点中的最大的度称为树的度。

2、二叉树及其基本性质

（1）二叉树的定义

二叉树是一种很有用的非线性结构，具有以下两个特点：

①非空二叉树只有一个根结点；

②每一个结点最多有两棵子树，且分别称为该结点的左子树和右子树。

由以上特点可以看出，在二叉树中，每一个结点的度最大为 2，即所有子树（左子树或

右子树）也均为二叉树，而树结构中的每一个结点的度可以是任意的。另外，二叉树中的每

个结点的子树被明显地分为左子树和右子树。在二叉树中，一个结点可以只有左子树而没有

右子树，也可以只有右子树而没有左子树。当一个结点既没有左子树也没有右子树时，该结

点即为叶子结点。

（2）二叉树的基本性质

二叉树具有以下几个性质：

性质 1：在二叉树的第 k层上，最多有 2k-1（k≥1）个结点；

性质 2：深度为 m的二叉树最多有 2m-1个结点；

性质 3：在任意一棵二叉树中，度为 0的结点（即叶子结点）总是比度为 2的结点多一个。

性质 4：具有 n个结点的二叉树，其深度至少为［ log

n］+1，其中［ log

n］表示取 log

的整数部分。

小技巧：在二叉树的遍历中，无论是前序遍历，中序遍历还是后序遍历，二叉树的叶子结点的先

后顺序都是不变的。

3、满二叉树与完全二叉树

满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点。

在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第 k层上有 2k-1个结点，

且深度为 m的满二叉树有 2m－1个结点。

完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最

后一层上只缺少右边的若干结点。

对于完全二叉树来说，叶子结点只可能在层次最大的两层上出现：对于任何一个结点，

若其右分支下的子孙结点的最大层次为 p，则其左分支下的子孙结点的最大层次或为 p，或为

p+1。

完全二叉树具有以下两个性质：

性质 5:具有 n个结点的完全二叉树的深度为［ log

2n］+1。

性质 6:设完全二叉树共有 n个结点。如果从根结点开始，按层次（每一层从左到右）用

自然数 1，2，……， n给结点进行编号，则对于编号为 k（k=1 ，2，……， n）的结点有以下

结论：

①若 k=1 ，则该结点为根结点，它没有父结点；若 k>1 ，则该结点的父结点编号为 INT

（k/2 ）。

②若 2k≤n，则编号为 k的结点的左子结点编号为 2k；否则该结点无左子结点（显然也没

有右子结点）。

③若 2k+1≤n，则编号为 k的结点的右子结点编号为 2k+1；否则该结点无右子结点。

考点8 二叉树的遍历

考试链接：

考点8在笔试考试中考核几率为 30%，分值为 2分，读者应该熟练掌握各种遍历的具体算法，能由两种遍历

的结果推导另一种遍历的结果。

在遍历二叉树的过程中，一般先遍历左子树，再遍历右子树。在先左后右的原则下，根

据访问根结点的次序，二叉树的遍历分为三类：前序遍历、中序遍历和后序遍历。

（1）前序遍历：先访问根结点、然后遍历左子树，最后遍历右子树；并且，在遍历左、

右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

（2）中序遍历：先遍历左子树、然后访问根结点，最后遍历右子树；并且，在遍历左、

右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。

（3）后序遍历：先遍历左子树、然后遍历右子树，最后访问根结点；并且，在遍历左、

右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。

疑难解答：树与二叉树的不同之处是什么？

在二叉树中，每一个结点的度最大为 2，即所有子树（左子树或右子树）也均为二叉树，而树结构中

的每一个结点的度可以是任意的。

1.5 查找技术

剩余24页未读，继续阅读

评论收藏

内容反馈

版权申诉

国家二级计算机公共基础知识考试考点.pdf

评论0

最新资源

国家二级计算机公共基础知识考试考点.pdf

评论0

最新资源

相关推荐

全国计算机等级考试之二级公共基础知识考点汇总.pdf

全国计算机二级公共基础知识必背考点.pdf

国家二级计算机公共基础知识考试考点十二.pdf

全国计算机等级考试二级公共基础知识考点说课.pdf

计算机二级access公共基础知识考点汇总.pdf

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

2010年9月计算机等级考试二级公共基础知识考点分析.pdf

9月计算机等级考试二级公共基础知识考点分析.pdf

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

全国计算机二级Access上机考试考点二级公共基础知识考前解析.pdf

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

全国计算机二级Access上机考试考点 二级公共基础知识考前解析.pdf

全国计算机二级Access上机考试考点&二级公共基础知识考前解析.pdf

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

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

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

哈尔滨工业大学ppt模板

2024北森题库（含答案）

大唐杯A组文字题库资料

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

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

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

NOC指导教师认证真题

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

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

citespace6.2.4安装包

华为OD机试真题.pdf

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

全国计算机二级Access上机考试考点二级公共基础知识考前解析.pdf

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