计算机二级公共基础知识
上传者:彭明田|上传时间: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月月考生物试卷
网友关注
- 试论信息技术与文化创意产业发展
- 小刘的烦恼
- 从书法感悟人生
- 课堂实录视频拍摄制作技术标准
- “三寸金莲馆”引发的思考
- 国际“终身学习素养”研究综述
- 佛教的危害
- 佛教对中国文化的影响
- 平凡榜样 精神脊梁
- 酒文化论文
- +NBA历届冠亚军
- 斐中文化交流 走进南太平洋花园
- 谈定性与定量研究在广告认知评价中的运用
- 佛教的四大危害
- 计算
- 情天在线告诉你 我喜欢出发
- 侗族鼓楼建筑艺术的文化意义和社会功能
- 下丘神经元对FM声调制方向选择性的突触机制研究
- 基于跨文化团队断裂带的匹配领导模式_段韵柳
- 有改变才有收获
- +历届欧洲杯足球赛冠亚军
- 佛教的负面影响
- 试论制度变迁过程中的人文关怀
- 试论乡村旅游中的文化传承
- 百年接力留学潮
- 欧泊的历史文化
- 一切佛心中心梵文咒
- 试论乡村旅游原生态文化的本质特征
- 谈符号消费中的文化差异及其启示
- 谈地震灾害对房地产经济的影响及其评估方法
网友关注视频
- 冀教版小学数学二年级下册第二周第2课时《我们的测量》宝丰街小学庞志荣.mp4
- 沪教版牛津小学英语(深圳用)五年级下册 Unit 1
- 苏教版二年级下册数学《认识东、南、西、北》
- 《空中课堂》二年级下册 数学第一单元第1课时
- 外研版英语七年级下册module3 unit2第二课时
- 【获奖】科粤版初三九年级化学下册第七章7.3浓稀的表示
- 沪教版八年级下册数学练习册21.4(1)无理方程P18
- 第19课 我喜欢的鸟_第一课时(二等奖)(人美杨永善版二年级下册)_T644386
- 每天日常投篮练习第一天森哥打卡上脚 Nike PG 2 如何调整运球跳投手感?
- 苏科版数学八年级下册9.2《中心对称和中心对称图形》
- 化学九年级下册全册同步 人教版 第18集 常见的酸和碱(二)
- 七年级下册外研版英语M8U2reading
- 冀教版英语四年级下册第二课
- 沪教版牛津小学英语(深圳用) 四年级下册 Unit 12
- 8.对剪花样_第一课时(二等奖)(冀美版二年级上册)_T515402
- 沪教版牛津小学英语(深圳用) 五年级下册 Unit 10
- 河南省名校课堂七年级下册英语第一课(2020年2月10日)
- 第五单元 民族艺术的瑰宝_15. 多姿多彩的民族服饰_第二课时(市一等奖)(岭南版六年级上册)_T129830
- 【部编】人教版语文七年级下册《过松源晨炊漆公店(其五)》优质课教学视频+PPT课件+教案,辽宁省
- 第五单元 民族艺术的瑰宝_16. 形形色色的民族乐器_第一课时(岭南版六年级上册)_T3751175
- 3月2日小学二年级数学下册(数一数)
- 苏科版八年级数学下册7.2《统计图的选用》
- 沪教版八年级下册数学练习册21.3(2)分式方程P15
- 8.练习八_第一课时(特等奖)(苏教版三年级上册)_T142692
- 沪教版牛津小学英语(深圳用) 四年级下册 Unit 2
- 冀教版小学英语五年级下册lesson2教学视频(2)
- 【部编】人教版语文七年级下册《泊秦淮》优质课教学视频+PPT课件+教案,辽宁省
- 《小学数学二年级下册》第二单元测试题讲解
- 二年级下册数学第二课
- 北师大版数学四年级下册第三单元第四节街心广场
精品推荐
- 2016-2017学年高一语文人教版必修一+模块学业水平检测试题(含答案)
- 广西钦州市高新区2017届高三11月月考政治试卷
- 浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
- 浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
- 辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
- 广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
- 广西钦州市钦州港区2017届高三11月月考政治试卷
- 广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
- 广西钦州市高新区2016-2017学年高二11月月考政治试卷
- 广西钦州市高新区2016-2017学年高一11月月考政治试卷
分类导航
- 互联网
- 电脑基础知识
- 计算机软件及应用
- 计算机硬件及网络
- 计算机应用/办公自动化
- .NET
- 数据结构与算法
- Java
- SEO
- C/C++资料
- linux/Unix相关
- 手机开发
- UML理论/建模
- 并行计算/云计算
- 嵌入式开发
- windows相关
- 软件工程
- 管理信息系统
- 开发文档
- 图形图像
- 网络与通信
- 网络信息安全
- 电子支付
- Labview
- matlab
- 网络资源
- Python
- Delphi/Perl
- 评测
- Flash/Flex
- CSS/Script
- 计算机原理
- PHP资料
- 数据挖掘与模式识别
- Web服务
- 数据库
- Visual Basic
- 电子商务
- 服务器
- 搜索引擎优化
- 存储
- 架构
- 行业软件
- 人工智能
- 计算机辅助设计
- 多媒体
- 软件测试
- 计算机硬件与维护
- 网站策划/UE
- 网页设计/UI
- 网吧管理