文档介绍：该【计算机二级公共基础知识 】是由【艾米】上传分享，文档一共【13】页，该文档可以免费在线阅读，需要了解更多关于【计算机二级公共基础知识 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。计算机二级公共基础知识
第2页
第一章数据结构与算法
算法:是指解题方案的准确而完整的描述。
算法不等于程序,也不等于计算方法,程序的编制不可能优于算法的设计。
算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。特征包括:
(1)可行性;
(2)确定性,算法中每一步骤都必须有明确定义,不充许有模棱两可的解释,不允许有多义性;
(3)有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止,包括合理的执行时间的含义;
(4)拥有足够的情报。
算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构。
算法的三种基本控制结构:顺序结构、选择结构、循环结构。
算法复杂度包括:算法时间复杂度和算法空间复杂度。
算法时间复杂度是指执行算法所需要的计算工作量。
算法空间复杂度是指执行这个算法所需要的内存空间。
(D)
(BG)
,则其空间复杂度必定小
,则其时间复杂度也必定大
,而与数据的存储结构无关
栈是限定在一端进行插入与删除运算的线性表。
在栈中,允许插入与删除的一端称为栈顶,不允许插入与删除的另一端称为栈底。栈顶元素总是最后被插入的元素,栈底元素总是最先被插入的元素。即栈是按照“先进后出”或“后进先出”的原则组织数据的。
栈的基本运算:
第3页
,元素个数为0或空间容量。
二叉树是一种非线性结构,它具有以下两个特点:
1)非空二叉树只有一个根结点;
2)每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。
根据二叉树的概念可知,二叉树的度可以为0(叶结点)、1(只有一棵子
树)或2(有2棵子树)。
二叉树考点1:
在任意一棵二叉树中,度数为0的结点(即叶子结点)总比度为2的结点多一个。叶子数(度为0)=度为2结点数+1
二叉树考点2:
二叉树的深度即二叉树的层次数
二叉树考点3:
总结点数=度为2的结点数+度为1的结点数+度为0的结点数(叶子)
,其中叶子结点只有1个,则该二叉树的深度为(假设根结点在第1层)_____。(7)
,其中5个是叶子结点,则度为1的结点数为____。(16)_
解析:叶子结点数=度为2的结点数+1
5=?+1
求得度为2的结点数为4
总结点数=度为2的结点数+度为1的结点数+度为0的结点数(叶子)
25=4+?+5
求得度为1的结点数为16
二叉树考点4:二叉树的遍历
二叉树的遍历是指不重复地访问二叉树中的所有结点。
二叉树的遍历可以分为以下三种:
(1)前序遍历:若二叉树为空,则结束返回。否则:首先访问根结点,然后遍历
左子树,最后遍历右子树。
(2)中序遍历:若二叉树为空,则结束返回。否则:首先遍历左子树,然后访问
根结点,最后遍历右子树。
(3)后序遍历:若二叉树为空,则结束返回。否则:首先遍历左子树,然后遍历
右子树,最后访问根结点。
第4页
进行前序遍历的结果为_____(ABDYECFXZ)
由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的称为线性表。线性表是由n(n≥0)个数据元素组成的一个有限序列,表中的每一个数据元素,除了第一个外,有且只有一个前件,除了最后一个外,有且只有一个后件。线性表中数据元素的个数称为线性表的长度。线性表可以为空表。
线性表是一种存储结构,它的存储方式:顺序和链式。
线性表的顺序存储结构具有两个基本特点:
(1)线性表中所有元素所占的存储空间是连续的;
(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
由此可以看出,在线性表的顺序存储结构中,其前后件两个元素在存储空间中是紧邻的,且前件元素一定存储在后件元素的前面,可以通过计算机直接确定第i个结点的存储地址。
顺序表的插入、删除运算
线性表的链式存储结构(线性链表)
数据结构中的每一个结点对应于一个存储单元,这种存储单元称为存储结点,简称结点。
结点由两部分组成:
(1)用于存储数据元素值,称为数据域;
(2)用于存放指针,称为指针域,用于指向前一个或后一个结点。
在链式存储结构中,存储数据结构的存储空间可以不连续,各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的。
链式存储方式既可用于表示线性结构,也可用于表示非线性结构。
线性结构条件:
(1)有且只有一个根结点;
(2)每一个结点最多有一个前件,也最多有一个后件。
第5页
非线性结构:不满足线性结构条件的数据结构。
(A)
解析:常见的线性结构有:队列、栈。非线性结构有:树、二叉树
(CE)
(不相同)
(多于)
,也可以是不连续的
,即是将无序的记录序列调整为有序记录序列的一种操作。
冒泡排序、快速排序、直接插入排序:
假设线性表的长度为n,则在最坏情况下,需要比较的次数为n(n-1)/2
堆排序:
在最坏情况下,需要比较的次数为nlog2n
顺序查找又称为顺序搜索。顺序查找一般是指在线性表中查找指定的元素
下面两种情况
(即表中元素排序是无序的),则不管是顺序存储结构还是链式存储结构,都只能用顺序查找
,如果采用链式存储结构,也只能用于顺序查找
二分查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排序(即从小到大,但允许相邻元素值相等)。
当有序线性表为顺序存储时才能采用二分查找,对于长度为n的有序线性表,在最坏情况下,二分查找只需要比较log2n次,而顺序查找需要比较n次。
,在最坏情况下,比较次数不是n(n-1)/2的排序方法是(C)
第6页
,最坏情况下需要比较的次数是(A)
(log2n) (nlog2n) (n2) (n)
,最坏情况下需要比较的次
(B)
第二章软件工程基本概念
、数据及相关文档的完整集合。
软件按功能分为应用软件、系统软件、支撑软件(或工具软件)。
软件危机主要表现在成本、质量、生产率等问题。
软件周期:软件产品从提出、实现、使用维护到停止使用退役的过程。
软件生命周期三个阶段:软件定义、软件开发、运行维护,主要活动阶段是:
(1)可行性研究与计划制定;
(2)需求分析;
(3)软件设计;
(4)软件实现;
(5)软件测试;
(6)运行和维护。
衡量软件模块独立性使用耦合性和内聚性两个定性的度量标准。
在程序结构中各模块的内聚性越强,则耦合性越弱。优秀软件应高内聚,低耦合。
内聚性是指一个模块内部各个元素间彼此结合的紧密程度
耦合性是指模块间相互连接的紧密程度
软件测试的目的:发现错误而执行程序的过程。
软件测试方法:静态测试和动态测试。
静态测试包括代码检查、静态结构分析、代码质量度量。不实际运行软件,主要通过人工进行。
动态测试:是基本计算机的测试,主要包括白盒测试方法和黑盒测试方法。
白盒测试:在程序内部进行,主要用于完成软件内部CAO作的验证。主要方法有逻辑覆盖、基本基路径测试。
黑盒测试:在黑盒测试方法中,设计测试用例的主要根据是程序外部功能。主要方法有等价类划分法、边界值分析法、错误推测法、因果图等。
第7页
软件测试过程一般按4个步骤进行:单元测试、集成测试、验收测试(确认测试)和系统测试。
程序调试的任务是诊断和改正程序中的错误,主要在开发阶段进行。
:(C)
该图是
-R图 -S图
第三章数据库设计基础
数据库管理系统:一种系统软件,负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等,是数据库的核心。
(1)数据定义语言:负责数据的模式定义与数据的物理存取构建;
(2)数据操纵语言:负责数据的操纵,如查询与增、删、改等;
(3)数据控制语言:负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等。
数据语言按其使用方式具有两种结构形式:交互式命令(又称自含型或自主型语言)宿主型语言(一般可嵌入某些宿主语言中)。
数据库管理员:对数据库进行规划、设计、维护、监视等的专业管理人员。
数据库系统:由数据库(数据)、数据库管理系统(软件)、数据库管理员(人员)、硬件平台(硬件)、软件平台(软件)五个部分构成的运行实体。
数据库应用系统:由数据库系统、应用软件及应用界面三者组成。文件系统阶段:提供了简单的数据共享与数据管理能力,但是它无法提供完整的、统一的、管理和数据共享的能力。层次数据库与网状数据库系统阶段:为统一与共享数据提供了有力支撑。
关系数据库系统阶段
数据库系统的基本特点:数据的集成性、数据的高共享性与低冗余性、数据独立性(物理独立性与逻辑独立性)、数据统一管理与控制。
第8页
:
(1)概念模式:数据库系统中全局数据逻辑结构的描述,全体用户公共数据视图;
(2)外模式:也称子模式与用户模式。是用户的数据视图,也就是用户所见到的数据模式;
(3)内模式:又称物理模式,它给出了数据库物理存储结构与物理存取方法。
数据模型
数据模型的概念:是数据特征的抽象,从抽象层次上描述了系统的静态特征、动态行为和约束条件,为数据库系统的信息表与操作提供一个抽象的框架。描述了数据结构、数据操作及数据约束。
E-R模型的基本概念
(1)实体:现实世界中的事物;
(2)属性:事物的特性;
(3)联系:现实世界中事物间的关系。实体集的关系有一对一、一对多、多对多的联系。
,实体B和C是一对一的联系,则实体A和C的联系是________。一间宿舍可住多个学生,则实体宿舍和学生之间的联系是________。(一对多)(一对多)
E-R模型三个基本概念之间的联接关系:实体是概念世界中的基本单位,属性有属性域,每个实体可取属性域内的值。一个实体的所有属性值叫元组。
E-R模型的图示法:(1)实体集表示法;(2)属性表法;(3)联系表示法。
在二维表中凡能唯一标识元组的最小属性称为键或码。从所有侯选健中选取一个作为用户使用的键称主键。表A中的某属性是某表B的键,则称该属性集为A的外键或外码。
关系中的数据约束:
(1)实体完整性约束:约束关系的主键中属性值不能为空值;
(2)参照完全性约束:是关系之间的基本约束;
(3)用户定义的完整性约束:它反映了具体应用中数据的语义要求。
关系数据库系统的特点之一是它建立在数据理论的基础之上,有很多数据理论可以表示关系模型的数据操作,其中最为著名的是关系代数与关系演算。
关系模型的基本运算:
插入(2)删除(3)修改(4)查询(包括投影、选择、笛卡尔积运算)
第9页
解析:
----------------------------------------------------------------------
第10页