2023年计算机二级公共基础知识总结.doc
《2023年计算机二级公共基础知识总结.doc》由会员分享,可在线阅读,更多相关《2023年计算机二级公共基础知识总结.doc(17页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、计算机二级公共基本知识总结第一章 数据构造与算法1.1 算法算法:是指解题方案精确而完整描述。算法不等于程序,也不等计算机办法,程序编制不也许优于算法设计。算法基本特性:是一组严谨地定义运算顺序规则,每一种规则都是有效,是明确,此顺序将在有限次数下终结。特性涉及:(1)可行性;(2)拟定性,算法中每一环节都必要有明拟定义,不充许有模棱两可解释,不允许有多义性;(3)有穷性,算法必要能在有限时间内做完,即能在执行有限个环节后终结,涉及合理执行时间含义;(4)拥有足够情报。算法基本要素:一是对数据对象运算和操作;二是算法控制构造。指令系统:一种计算机系统能执行所有指令集合。基本运算和操作涉及:算术
2、运算、逻辑运算、关系运算、数据传播。算法控制构造:顺序构造、选取构造、循环构造。算法基本设计办法:列举法、归纳法、递推、递归、减斗递推技术、回溯法。算法复杂度:算法时间复杂度和算法空间复杂度。算法时间复杂度是指执行算法所需要计算工作量。算法空间复杂度是指执行这个算法所需要内存空间。1.2 数据构造基本基本概念数据构造研究三个方面:(1)数据集合中各数据元素之间所固有逻辑关系,即数据逻辑构造;(2)在对数据进行解决时,各数据元素在计算机中存储关系,即数据存储构造;(3)对各种数据构造进行运算。数据构造是指互有关于联数据元素集合。数据逻辑构造涉及:(1)表达数据元素信息;(2)表达各数据元素之间先
3、后件关系。数据存储构造有顺序、链接、索引等。线性构造条件:(1)有且只有一种根结点;(2)每一种结点最多有一种前件,也最多有一种后件。非线性构造:不满足线性构造条件数据构造。13 线性表及其顺序存储构造线性表由一组数据元素构成,数据元素位置只取决于自己序号,元素之间相对位置是线性。在复杂线性表中,由若干项数据元素构成数据元素称为记录,而由各种记录构成线性表又称为文献。非空线性表构造特性:(1)且只有一种根结点a1,它无前件;(2)有且只有一种终端结点an,它无后件;(3)除根结点与终端结点外,其她所有结点有且只有一种前件,也有且只有一种后件。结点个数n称为线性表长度,当n=0时,称为空表。线性
4、表顺序存储构造具有如下两个基本特点:(1)线性表中所有元素所占存储空间是连续;(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存储。ai存储地址为:ADR(ai)=ADR(a1)+(i-1)k,,ADR(a1)为第一种元素地址,k代表每个元素占字节数。顺序表运算:插入、删除。 (详见14-16页)14 栈和队列栈是限定在一端进行插入与删除线性表,允许插入与删除一端称为栈顶,不允许插入与删除另一端称为栈底。栈按照“先进后出”(FILO)或“后进先出”(LIFO)组织数据,栈具有记忆作用。用top表达栈顶位置,用bottom表达栈底。栈基本运算:(1)插入元素称为入栈运算;(2)删除元素称为退
5、栈运算;(3)读栈顶元素是将栈顶元素赋给一种指定变量,此时指针无变化。队列是指允许在一端(队尾)进入插入,而在另一端(队头)进行删除线性表。Rear指针指向队尾,front指针指向队头。队列是“先进行出”(FIFO)或“后进后出”(LILO)线性表。队列运算涉及(1)入队运算:从队尾插入一种元素;(2)退队运算:从队头删除一种元素。循环队列:s=0表达队列空,s=1且front=rear表达队列满15 线性链表数据构造中每一种结点相应于一种存储单元,这种存储单元称为存储结点,简称结点。结点由两某些构成:(1)用于存储数据元素值,称为数据域;(2)用于存储指针,称为指针域,用于指向前一种或后一种
6、结点。在链式存储构造中,存储数据构造存储空间可以不连续,各数据结点存储顺序与数据元素之间逻辑关系可以不一致,而数据元素之间逻辑关系是由指针域来拟定。链式存储方式即可用于表达线性构造,也可用于表达非线性构造。线性链表,HEAD称为头指针,HEAD=NULL(或0)称为空表,假如是两指针:左指针(Llink)指向前件结点,右指针(Rlink)指向后件结点。线性链表基本运算:查找、插入、删除。16 树与二叉树树是一种简朴非线性构造,所有元素之间具有明显层次特性。在树构造中,每一种结点只有一种前件,称为父结点,没有前件结点只有一种,称为树根结点,简称树根。每一种结点可以有各种后件,称为该结点子结点。没
7、有后件结点称为叶子结点。在树构造中,一种结点所拥有后件个数称为该结点度,所有结点中最大度称为树度。树最大层次称为树深度。二叉树特点:(1)非空二叉树只有一种根结点;(2)每一种结点最多有两棵子树,且分别称为该结点左子树与右子树。二叉树基本性质:(1)在二叉树第k层上,最多有2k-1(k1)个结点;(2)深度为m二叉树最多有2m-1个结点;(3)度为0结点(即叶子结点)总是比度为2结点多一种;(4)具有n个结点二叉树,其深度至少为log2n+1,其中log2n表达取log2n整数某些;(5)具有n个结点完全二叉树深度为log2n+1;(6)设完全二叉树共有n个结点。假如从根结点开始,按层序(每一
8、层从左到右)用自然数1,2,.n给结点进行编号(k=1,2.n),有如下结论:若k=1,则该结点为根结点,它没有父结点;若k1,则该结点父结点编号为INT(k/2);若2kn,则编号为k结点左子结点编号为2k;否则该结点无左子结点(也无右子结点);若2k+1n,则编号为k结点右子结点编号为2k+1;否则该结点无右子结点。满二叉树是指除最后一层外,每一层上所有结点有两个子结点,则k层上有2k-1个结点深度为m满二叉树有2m-1个结点。完全二叉树是指除最后一层外,每一层上结点数均达成最大值,在最后一层上只缺少右边若干结点。二叉树存储构造采用链式存储构造,对于满二叉树与完全二叉树可以按层序进行顺序存
9、储。二叉树遍历:(1)前序遍历(DLR),一方面访问根结点,然后遍历左子树,最后遍历右子树;(2)中序遍历(LDR),一方面遍历左子树,然后访问根结点,最后遍历右子树;(3)后序遍历(LRD)一方面遍历左子树,然后访问遍历右子树,最后访问根结点。17 查找技术顺序查找使用状况:(1)线性表为无序表;(2)表采用链式存储构造。二分法查找只合用于顺序存储有序表,对于长度为n有序线性表,最坏状况只需比较log2n次。18 排序技术排序是指将一种无序序列整顿成按值非递减顺序排列有序序列。互换类排序法:(1)冒泡排序法,需要比较次数为n(n-1)/2;(2)迅速排序法。插入类排序法:(1)简朴插入排序法
10、,最坏状况需要n(n-1)/2次比较;(2)希尔排序法,最坏状况需要O(n1.5)次比较。选取类排序法:(1)简朴选取排序法,最坏状况需要n(n-1)/2次比较;(2)堆排序法,最坏状况需要O(nlog2n)次比较。第二章 程序设计基本21 程序设计设计办法和风格如何形成良好程序设计风格1、源程序文档化; 2、数据阐明办法;3、语句构造; 4、输入和输出。注释分前言性注释和功能性注释,语句构造清楚第一、效率第二。22 构造化程序设计构造化程序设计办法四条原则是:1. 自顶向下;2. 逐渐求精;3.模块化;4.限制使用goto语句。构造化程序基本构造和特点:(1)顺序构造:一种简朴程序设计,最基
11、本、最惯用构造;(2)选取构造:又称分支构造,涉及简朴选取和多分支选取构造,可依照条件,判断应当选取哪一条分支来执行相应语句序列;(3)反复构造:又称循环构造,可依照给定条件,判断与否需要反复执行某一相似程序段。23 面向对象程序设计面向对象程序设计:以60年代末挪威奥斯陆大学和挪威计算机中心研制SIMULA语言为标志。面向对象办法长处:(1)与人类习惯思维办法一致;(2)稳定性好;(3)可重用性好;(4)易于开发大型软件产品;(5)可维护性好。对象是面向对象办法中最基本概念,可以用来表达客观世界中任何实体,对象是实体抽象。面向对象程序设计办法中对象是系统中用来描述客观事物一种实体,是构成系统
12、一种基本单位,由一组表达其静态特性属性和它可执行一组操作构成。属性即对象所涉及信息,操作描述了对象执行功能,操作也称为办法或服务。对象基本特点:(1)标记惟一性;(2)分类性;(3)多态性;(4)封装性;(5)模块独立性好。类是指具有共同属性、共同办法对象集合。因此类是对象抽象,对象是相应类一种实例。消息是一种实例与另一种实例之间传递信息。消息构成涉及(1)接受消息对象名称;(2)消息标记符,也称消息名;(3)零个或各种参数。继承是指可以直接获得已有性质和特性,而不必反复定义她们。继承分单继承和多重继承。单继承指一种类只允许有一种父类,多重继承指一种类允许有各种父类。多态性是指同样消息被不同对
13、象接受时可导致完全不同行动现象。第三章 软件工程基本31 软件工程基本概念计算机软件是涉及程序、数据及有关文档完整集合。软件特点涉及:(1)软件是一种逻辑实体;(2)软件生产与硬件不同,它没有明显制作过程;(3)软件在运营、有效期间不存在磨损、老化问题;(4)软件开发、运营对计算机系统具有依赖性,受计算机系统限制,这导致了软件移植问题;(5)软件复杂性高,成本昂贵;(6)软件开发涉及诸多社会因素。软件按功能分为应用软件、系统软件、支撑软件(或工具软件)。软件危机重要体当前成本、质量、生产率等问题。软件工程是应用于计算机软件定义、开发和维护一整套办法、工具、文档、实践原则和工序。软件工程涉及3个
14、要素:办法、工具和过程。软件工程过程是把软件转化为输出一组彼此有关资源和活动,涉及4种基本活动:(1)P-软件规格阐明;(2)D-软件开发;(3)C-软件确认;(4)A-软件演进。软件周期:软件产品从提出、实现、使用维护到停止使用退役过程。软件生命周期三个阶段:软件定义、软件开发、运营维护,重要活动阶段是:(1)可行性研究与筹划制定;(2)需求分析;(3)软件设计;(4)软件实现;(5)软件测试;(6)运营和维护。软件工程目的和与原则:目的:在给定成本、进度前提下,开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足顾客需求产品。基本目的:付出
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2023 计算机 二级 公共 基础知识 总结
限制150内