[精品]公共基础复习资料.docx.pdf
《[精品]公共基础复习资料.docx.pdf》由会员分享,可在线阅读,更多相关《[精品]公共基础复习资料.docx.pdf(6页珍藏版)》请在三一文库上搜索。
1、武汉工程职业技术学院全国计算机等级考试二级公 共基础知识 第一章数据结构与算法 1.1算法 私I:是指解题方案的准确而完整的描述。 算法不等于程序,也不等计算机方法,程序的编制不可能优于算法 的设计。 算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则 都是冇效的,是叨确的,此顺序将在冇限的次数下终止。 特征包括: (1)可行性; (2)确定性,算法中每一步骤都必须有明确定义,不充许有 模棱两可的解释,不允许有多义性; (3)有穷性,算法必须能在有限的时间内做完,即能在执行 有限个步骤后终止,包括合理的执行时间的含义; (4)拥有足够的情报。 算法的基本要素: ?是对数据对彖的运算和操
2、作;二是算法的控制 结构。 指令系统:一个计算机系统能执行的所有指令的集介。 基本运算包括:算术运算、逻辑运算、关系运算、数据传输。算法 的控制结构:01 页序结构、选择结构、循环结构 算法基本设计方法: 列举法、归纳法、递推、递归、减斗递 推技术、 回溯法。 算法复杂度:僚法时间复杂圍和僚法空间复翔。算法时间复杂度 是指执行算法所需要的计算丁作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 1.2数据结构的基本基木概念 数据结构研究的二个方面: (1)数据集介中各数据元素Z间所固有的逻辑关系,即圜 据的逻辑结构I; (2)在对数据进行处理时,各数据元素在计算机屮的存储关 系,即I数据
3、的存储结岡; (3)对各种数据结构进行的运算。 数据结构是指相互有关联的数据元索的集合 数据的逻辑结构包含: (1)表示数据元索啲信息; (2)表示各数据元素之间的而后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件: (1)有且只有一个根结点; (2)每一个结点最多有一个询件,也最多有一个后件。 卄?线性结构:不满足线性结构条件的数据结构。 1. 3线性表及其顺序存储结构 須殛是曲一组数据元索构成,数据元索的位置只取决丁?自 己的序 号,元素之间的相对位置是线性的。 在复杂线性表屮,由若干项数据元素组成的数据元素称为凰园, 而由多个记录构成的线性表又称为反囲。 非空线性表的结构特
4、征: (1)且只有一个根结点al,它无前件; (2)冇且只冇一个终端结点an,它无后件; (3) 除根结点与终端结点外,其他所有结点有冃只有一个前 件,也有且只有一个后件。结点个数n称为| 线性表的氏產当 n=0时,称为丽。 线性农的顺序存储结构具有以下两个基木特点: (1)线性农屮所有兀素的所占的存储空间是连续的; (2)线性表中各数据元素在存储空间中是按逻辑顺序依次存 放的。 ai 的存储I也卯:为:ADR(ai)=ADR (al)+(i-l)k, ADR(al)为第一个元素的地址,k代表每个元索占的字节数。 顺序表的运算:插入、删除。(详见14-16页) 1. 4栈和队列 囲是限定在一端
5、进行 -插入打删除的线性表,允许插入打删除的一 端称为栈顶,不允许插入号删除的另一端称为栈底C 栈按照F先 进后可(FILO)或进先Hfl (LIFO)组织数 据,栈具有记 忆作用。用top表示栈顶位置,用bottom表 示栈底。 栈的基木运算;(1)插入元素称为入栈运算;(2)删除元素 称为退栈运算;(3)读栈顶元索是将栈顶元索赋给一个指定的 变量,此时指针无变化。 队列是指允许在一端(队尾)进入插入,而在另一端(队头) 进行删除的线性表。Rear指针指向队尾,front指针指向队 头。 队列是卩先进行;r(FIFO)或 后进后出 “ (LILO )的线 性 表。 队列运算包括(1)入队运算
6、:从队尾插入一个元素;(2)退 队运算:从队头删除一个元素。 循环队列:s=0表示队列空,s=l H. front=rear表示队列满 1. 5线性链表 数据结构中的每个结点对应于个存储单兀,这种存储单元称为 存储结点,简称 | 结点| 。 结点山两部分组成:(1)用于存储数据元素值,称为做丽; (2)用于存放指针,称为唾國,用于指向前一个或后一个结 点。 在链式存储结构中,存储数据结构的存储空间可以不连续,各数 据结点的存储顺序与数据元素之间的逻辑关系可以不?致,而数 据元素之间的逻辑关系是由指针域來确定的。 链式存储方式即町用于表示线性结构,也町用于表示非线性结 构。 线性链表,HEAD称
7、为头指针,HEAD = NULL (或0)称为 如果是两指针:匡画(Llink)指向前件结点,固|W| (Rlink)指向后件结点。 线性链表的基本运算:查找、插入、删除。 1. 6树与二叉树 树是种简单 ?的非线性结构 , 所有元素之间具有明显的层次特性。 在树结构中,每一个结点只冇一个前件,称为父结点,没有前件 的结点只有一个,称为树的根结点, 简称树的根。每一 个结点可以有多个后件,称为该结点的子结点。没有后件的结点 称为叶了结点。 在树结构中,一个结点所拥有的后件的个数称为该结点的的深度。 二叉树的特点:(1)非空二叉树只有 ?个根结点;(2)每 ?个结点最 多冇两棵了树,且分別称为该
8、结点的左了树与右 子树。 二叉树的慕木性质: (1)在一义树的笫k层上,最多冇2k?l(knl)个结点 ; (2)深度为m的?- 义树最多有2m?l个结点; (3)度为0的结点 (即叶子结点 ) 总是比度为2的结点多 一个 ; (4)具有n个结点的二叉树,其深度至少为Iog2n + lz 英中 log2nS示取Iog2n的整数部分; (5)具有n个结点的完全二叉树的深度为Iog2n + 1; (6)设完全二叉树共冇n个结点。如果从根结点开始,按层序 ( 每 一 层从 左到 右 ) 用B然 数1, 2, ,.n给结 点进行编 号 (k=l,2n),有以下结论: 若k=l,则该结点为根结点,它没有
9、父结点;若kl, 则该结点的 父结点编号为INT(k/2); 若2kSn,则编号为k的结点的左子结点编号为2k;否 则该结 点无左子结点 ( 也无右子结点 ); 若2k+ln,则编号为k的结点的右子结点编号为2k+l;否则 该结点无右子结点。 满-义树是指除最后一层外,每一反上的所有结点有两个子结点, 则k层上冇2k-l个结点深度为m的满一?义树冇2m?l个结点。 I完全二叉树I是指除址肩一层外, 侮一从卜 -的结点数均达到最大 值,在最后 - 层上只缺少右边的若丁结点。 一叉树存储结构采用 | 链式存储结同,对于满二叉树与完全二义树 町以按层序进行顺序存储。 二叉树的遍丿力: (1) 前序遍
10、历|(DLR),首先访问根结点,然麻遍历左子树 , 最遍历 右了树; (2) | 丁序遍历|(LDR),杵先遍历人子树, 然后访问根结点,最丿 匸遍历右子树; (3) 听序遍同(LRD)首先遍历左子树,然后访问遍历右子树, 垠后访问根结点。 1. 7查找技术 顺序杳找的使用情况: (1)线性表为无序表; (2)表釆用链式存储结构。 二分法查找只适用丁 | 顺序存储的有序表I,对于长度为n的有 序 线性表,最坏情况只需比较|log2n|次。 1. 8排序技术 排序是指将一个无序序列整理成按值非递减顺序排列的冇序序列。 交换类排序法:(1)冒泡排序法,需要比较的次数为 n(n?l)/2|;(2)快
11、速排序法。 插入类排序法:(1)简单插入排序法,最坏情况需要|n(n?l)/2| 次比较 ;(2)希尔排序法,戢坏情况需要阪頁次比较。 选择类排序法:(1)简单选择排序法, 最坏情况需要n(n?l)/2|次 比较;(2)堆排序法,最坏情况需要?ngn) 次比较。 第二章程序设计基础 2. 1程序设计设计方法和风格 如何形成良好的程序设计风格 1、源程序文档化;2、数据说明的方法; 3、 语句的结构 ;4、输入和输出。 结构化程序的里木结构和特点: (1)顺序结构:一种简单的程序设计,最基本、最常用的结构; (2)选择结构:又称分支结构,包括简单选择和多分支选择结构, 町根据条件,判断应该选择哪
12、一条分支來执行相应的语句序列; (3)循环结构: 可根据给定条件, 判断是否需要重复执行某一相 同程序段。 2. 3面向对彖的程序设计 面向对象的程序设计:以60年代末挪威奥斯陆人学和挪威计算机 屮心研制的SIMULA语言为标志。 面向对彖方法的优点: (1) 与人类习惯的思维方法一致; (2) 稳定性好 ; (3) 可重用性好 ; (4) 易于开发大型软件产品; (5) 可维护性好。 徑是面向对象方法中最基本的概念,町以川來表示客观世界中的任 何实体,对象是实体的抽象。 面向对彖的程序设计方法屮的对象是系统屮用來描述客观事物的 一个实体,是构成系统的一个基本单位,山一组表示其静态特征的 属性
13、和它可执行的一组操作组成。 丽即对彖所包含的信息 , 操作描述了对象执行的功能,操作也称为 丽或厕。 对象的基本特点: (1) 标识惟 ?性; (2) 分类性; (3) 多态性; (4) 封装性; (5) 模块独立性好。 医| 是指具有共同属性、共同方法的对象的集合。所以类是对彖的 抽象,对象是对应类的一个实例。 消思I是个实例与另 ?个实例之间传递的信息。 消息的组成包括(1)接收消息的对象的名称;(2)消息标 识 符,也称消息名;(3)零个或多个参数。 殛是指能够宜接获得已育的性质和特征,而不必帀复定义他们。 继承分单继承和多重继承。单继承指个类只允许有?个父 类,多重 继承指?个类允许冇
14、多个父类。 度, 所有结点屮最人的度称为树的度。树的最大从次称为树 诙是指同样的消息被不同的对象接受时可导致完全不同的行动的 现象 第三章软件工程基础 3. 1软件工程基本概念计算机软件是包括画 | 、丽及柳关文糧的 完整集合。软件的特点包扌 !5: (1)软件是 - 种逻辑实体; (2)软件的生产与硕件不同,它没有明显的制作过程; (3)软件在运行、使用期间不存在磨损、老化问题; (4)软件的开发、运行对计算机系统具有依赖性,受计算机 系统的限制,这导致了软件移植的问题; (5)软件复杂性高,成木昂贵; (6)软件开发涉及诸多的补会因素。 软件按功能分为应用软件、系统软件、支撑软件(或匚具软
15、 件)。 软件危机主要表现在成本、质量、生产率等问题。 软件工住I是应用丁 ?计算机软件的定义、开发和维护的一整套方 法、工具、文档、实践标准和工序。 软件I程包括3个要素:网、审和丽。 软件工程过程是把软件转化为输出的一组彼此相关的资源和活 动,包含4种基本活动: (1) P- 一软件规格说明 ; (2) D- 一软件开发; (3) C- 一软件确认; (4) A- 一软件演进。 软件周则:软件产品从捉出、实现、使用维护到停止使用退役的 过程。 软件个命周期厂个阶段 : 嗽件定図、I软件开发I、| 运行维护丄要 活动阶段是: (1)可行性研究与计划制定; (2)需求分析; (3)软件设计;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 精品 公共 基础 复习资料 docx
链接地址:https://www.31doc.com/p-5618875.html