教育资源为主的文档平台

当前位置: 查字典文档网> 所有文档分类> 资格考试> IT认证> 计算机二级公共基础知识

计算机二级公共基础知识

上传者:彭明田
|
上传时间:2015-04-25
|
次下载

计算机二级公共基础知识

1. 算法的基本概念

利用计算机算法为计算机解题的过程实际上是在实施某种算法。

(1)算法的基本特征

算法一般具有4个基本特征:可行性、确定性、有穷性、拥有足够的情报。

(2)算法的基本运算和操作

算法的基本运算和操作包括:算术运算、逻辑运算、关系运算、数据传输。

(3)算法的3种基本控制结构

算法的3种基本控制结构是:顺序结构、选择结构、循环结构。

(4)算法基本设计方法

算法基本设计方法:列举法、归纳法、递推、递归、减半递推技术、回溯法。

(5)指令系统

所谓指令系统指的是一个计算机系统能执行的所有指令的集合。

(2)数据结构研究的3个方面

① 数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构;

② 在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构; ③ 对各种数据结构进行的运算。

2. 逻辑结构

数据的逻辑结构是对数据元素之间的逻辑关系的描述,它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构有两个要素:一是数据元素的集合,通常记为D;二是D上的关系,它反映了数据元素之间的前后件关系,通常记为R。一个数据结构可以表示成:B=(D,R)

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

例如,如果把一年四季看作一个数据结构,则可表示成:B =(D,R)

D ={春季,夏季,秋季,冬季}

R ={(春季,夏季),(夏季,秋季),(秋季,冬季)}

3. 存储结构

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

由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同,因此,为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系(即前后件关系),在数据的存储结构中,不仅要存放各数据元素的信息,还需要存放各数据元素之间的前后件关系的信息。

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

顺序存储方式主要用于线性的数据结构,它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里,结点之间的关系由存储单元的邻接关系来体现。

链式存储结构就是在每个结点中至少包含一个指针域,用指针来体现数据元素之间逻辑上的联系。

1.2.2 线性结构和非线性结构

根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分为两大类型:线性结构与非线性结构。

(1)如果一个非空的数据结构满足下列两个条件:

① 有且只有一个根结点;

② 每一个结点最多有一个前件,也最多有一个后件。

则称该数据结构为线性结构。线性结构又称线性表。在一个线性结构中插入或删除任何一个结点后还应是线性结构。栈、队列、串等都为线性结构。

如果一个数据结构不是线性结构,则称之为非线性结构。数组、广义表、树和图等数据结构都是非线性结构。

(2)线性表的顺序存储结构具有以下两个基本特点:

① 线性表中所有元素所占的存储空间是连续的;

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

元素ai的存储地址为:ADR(ai)=ADR(a1)+(i-1)k,ADR(a1)为第一个元素的地址,k代表每个元素占的字节数。

(3)顺序表的运算有查找、插入、删除3种。

1.3 栈

1. 栈的基本概念

栈(stack)是一种特殊的线性表,是限定只在一端进行插入与删除的线性表。

在栈中,一端是封闭的,既不允许进行插入元素,也不允许删除元素;另一端是开口的,允许插入和删除元素。通常称插入、删除的这一端为栈顶,另一端为栈底。当表中没有元素时称为空栈。栈顶元素总是最后被插入的元素,从而也是最先被删除的元素;栈底元素总是最先被插入的元素,从而也是最后才能被删除的元素。

栈是按照―先进后出‖或―后进先出‖的原则组织数据的。例如,枪械的子弹匣就可以用来形象的表示栈结构。子弹匣的一端是完全封闭的,最后被压入弹匣的子弹总是最先被弹出,而最先被压入的子弹最后才能被弹出。

二级公共基础知识速学教程

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

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

① 入栈运算:在栈顶位置插入一个新元素;

② 退栈运算:取出栈顶元素并赋给一个指定的变量;

③ 读栈顶元素:将栈顶元素赋给一个指定的变量。

1.4 队列

1. 队列的基本概念

队列是只允许在一端进行删除,在另一端进行插入的顺序表,通常将允许删除的这一端称为队头,允许插入的这一端称为队尾。当表中没有元素时称为空队列。

队列的修改是依照先进先出的原则进行的,因此队列也称为先进先出的线性表,或者后进后出的线性表。例如:火车进遂道,最先进遂道的是火车头,最后是火车尾,而火车出遂道的时候也是火车头先出,最后出的是火车尾。若有队列:

Q =(q1,q2,…,qn)

那么,q1为队头元素(排头元素),qn为队尾元素。队列中的元素是按照q1,q2,…,qn的顺序进入的,退出队列也只能按照这个次序依次退出,即只有在q1,q2,…,qn-1都退队之后,qn才能退出队列。因最先进入队列的元素将最先出队,所以队列具有先进先出的特性,体现―先来先服务‖的原则。

队头元素q1是最先被插入的元素,也是最先被删除的元素。队尾元素qn是最后被插入的元素,也是最后被删除的元素。因此,与栈相反,队列又称为―先进先出‖(First In First Out,简称FIFO) 或―后进后出‖(Last In Last Out,简称LILO)的线性表。

2. 队列运算

入队运算是往队列队尾插入一个数据元素;退队运算是从队列的队头删除一个数据元素。 队列的顺序存储结构一般采用队列循环的形式。循环队列s=0表示队列空;s=1且

front=rear表示队列满。计算循环队列的元素个数:―尾指针减头指针‖,若为负数,再加其容量即可。

1.5 链表

在链式存储方式中,要求每个结点由两部分组成:一部分用于存放数据元素值,称为数据域;另一部分用于存放指针,称为指针域。其中指针用于指向该结点的前一个或后一个结点(即前件或后件)。

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

(1)线性链表

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

在某些应用中,对线性链表中的每个结点设置两个指针,一个称为左指针,用以指向其前件结点;另一个称为右指针,用以指向其后件结点。这样的表称为双向链表。

在线性链表中,各数据元素结点的存储空间可以是不连续的,且各数据元素的存储顺序与逻辑顺序可以不一致。在线性链表中进行插入与删除,不需要移动链表中的元素。 线性单链表中,HEAD称为头指针,HEAD=NULL(或0)称为空表。

如果是双项链表的两指针:左指针(Llink)指向前件结点,右指针(Rlink)指向后件结点。

线性链表的基本运算:查找、插入、删除。

(2)带链的栈

栈也是线性表,也可以采用链式存储结构。带链的栈可以用来收集计算机存储空间中所有空闲的存储结点,这种带链的栈称为可利用栈。

1.6 二叉树

1.6.1 二叉树概念及其基本性质

1. 二叉树及其基本概念

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

二级公共基础知识速学教程

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

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

在二叉树中,每一个结点的度最大为2,即所有子树(左子树或右子树)也均为二叉树。另外,二叉树中的每个结点的子树被明显地分为左子树和右子树。

在二叉树中,一个结点可以只有左子树而没有右子树,也可以只有右子树而没有左子树。当一个结点既没有左子树也没有右子树时,该结点即为叶子结点。

例如,一个家族中的族谱关系如图1-1所示:

A有后代B,C;B有后代D,E;C有后代F。

典型的二叉树如图1-1所示:

详细讲解二叉树的基本概念,见表1-2。

图1-1 二叉树图

表1-2 二叉树的基本概念

父结父结点(根)

在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点,简称树的根。例如,在图1-1中,结点A是树的根结点。

子结点和

叶子结点

在树结构中,每一个结点可以有多个后件,称为该结点的子结点。没有后件的结点称为叶子结点。例如,在图1-1中,结点D,E,F均为叶子结点。

在树结构中,一个结点所拥有的后件的个数称为该结点的度,所有结点中最大的度称为树的度。例如,在图1-1中,根结点A和结点B的度为2,结点C的度为1,叶子结点D,E,F的度为0。所以,该树的度为2。

深度

版权声明:此文档由查字典文档网用户提供,如用于商业用途请与作者联系,查字典文档网保持最终解释权!

下载文档

热门试卷

2016年四川省内江市中考化学试卷
广西钦州市高新区2017届高三11月月考政治试卷
浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
广西钦州市钦州港区2017届高三11月月考政治试卷
广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
广西钦州市高新区2016-2017学年高二11月月考政治试卷
广西钦州市高新区2016-2017学年高一11月月考政治试卷
山东省滨州市三校2017届第一学期阶段测试初三英语试题
四川省成都七中2017届高三一诊模拟考试文科综合试卷
2017届普通高等学校招生全国统一考试模拟试题(附答案)
重庆市永川中学高2017级上期12月月考语文试题
江西宜春三中2017届高三第一学期第二次月考文科综合试题
内蒙古赤峰二中2017届高三上学期第三次月考英语试题
2017年六年级(上)数学期末考试卷
2017人教版小学英语三年级上期末笔试题
江苏省常州西藏民族中学2016-2017学年九年级思想品德第一学期第二次阶段测试试卷
重庆市九龙坡区七校2016-2017学年上期八年级素质测查(二)语文学科试题卷
江苏省无锡市钱桥中学2016年12月八年级语文阶段性测试卷
江苏省无锡市钱桥中学2016-2017学年七年级英语12月阶段检测试卷
山东省邹城市第八中学2016-2017学年八年级12月物理第4章试题(无答案)
【人教版】河北省2015-2016学年度九年级上期末语文试题卷(附答案)
四川省简阳市阳安中学2016年12月高二月考英语试卷
四川省成都龙泉中学高三上学期2016年12月月考试题文科综合能力测试
安徽省滁州中学2016—2017学年度第一学期12月月考​高三英语试卷
山东省武城县第二中学2016.12高一年级上学期第二次月考历史试题(必修一第四、五单元)
福建省四地六校联考2016-2017学年上学期第三次月考高三化学试卷
甘肃省武威第二十三中学2016—2017学年度八年级第一学期12月月考生物试卷

网友关注视频

外研版英语三起6年级下册(14版)Module3 Unit1
二年级下册数学第三课 搭一搭⚖⚖
外研版八年级英语下学期 Module3
每天日常投篮练习第一天森哥打卡上脚 Nike PG 2 如何调整运球跳投手感?
【部编】人教版语文七年级下册《过松源晨炊漆公店(其五)》优质课教学视频+PPT课件+教案,辽宁省
冀教版英语三年级下册第二课
二年级下册数学第二课
沪教版八年级下册数学练习册21.4(1)无理方程P18
【部编】人教版语文七年级下册《逢入京使》优质课教学视频+PPT课件+教案,辽宁省
沪教版牛津小学英语(深圳用) 四年级下册 Unit 2
《空中课堂》二年级下册 数学第一单元第1课时
第五单元 民族艺术的瑰宝_16. 形形色色的民族乐器_第一课时(岭南版六年级上册)_T3751175
沪教版牛津小学英语(深圳用) 四年级下册 Unit 7
冀教版小学数学二年级下册第二周第2课时《我们的测量》宝丰街小学庞志荣.mp4
人教版二年级下册数学
【部编】人教版语文七年级下册《老山界》优质课教学视频+PPT课件+教案,安徽省
【部编】人教版语文七年级下册《泊秦淮》优质课教学视频+PPT课件+教案,广东省
沪教版牛津小学英语(深圳用) 五年级下册 Unit 12
冀教版小学英语五年级下册lesson2教学视频(2)
【部编】人教版语文七年级下册《逢入京使》优质课教学视频+PPT课件+教案,安徽省
沪教版八年级下次数学练习册21.4(2)无理方程P19
冀教版小学数学二年级下册第二单元《有余数除法的竖式计算》
3月2日小学二年级数学下册(数一数)
冀教版小学数学二年级下册第二单元《余数和除数的关系》
沪教版八年级下册数学练习册20.4(2)一次函数的应用2P8
沪教版牛津小学英语(深圳用) 五年级下册 Unit 10
【部编】人教版语文七年级下册《泊秦淮》优质课教学视频+PPT课件+教案,天津市
二次函数求实际问题中的最值_第一课时(特等奖)(冀教版九年级下册)_T144339
第19课 我喜欢的鸟_第一课时(二等奖)(人美杨永善版二年级下册)_T644386
化学九年级下册全册同步 人教版 第22集 酸和碱的中和反应(一)