公共基础知识考试点
第1章数据结构与算法考点1:算法具有4个基本特征:可行性、确定性、有穷性、拥有足够的情报。确定性:是指算法中每一个步骤都必须是有明确定义的,不允许模棱两可的定义有穷性:是指算法必须能在有限的时间内做完一个算法由两种基本要素组成:一是对数据对象的运算和操作,二是算法的控制结构考点2:算法复杂度包括时间复杂度和空间复杂度时间复杂度执行算法所需要的计算
工作量空间复杂度执行这个算法所需要的内存空间考点3:数据结构一:讨论的
问题:1.数据元素之间的逻辑关系,即数据的逻辑结构2.数据元素在
计算机中的存储关系,即数据的存储结构3.对各种数据结构进行的运算考点4:数据结构分为两大类型:线性结构与非线性结构。(1)如果一个非空的数据结构满足下列两个条件:①有且只有一个根结点;②每一个结点最多有一个前件,也最多有一个后件。则称该数据结构为线性结构。如果一个数据结构不是线性结构,则称之为非线性结构。考点5:线性表特点:(1)线性表中所有元素所占的存储空间是连续的(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的考点5:栈的基本概念栈(stack)是一种特殊的线性表,是限定只在一端进行插入与删除的线性表。
栈是按照“先进后出”或“后进先出”的原则组织数据的。考点6:队列的基本概念队列是只允许在一端进行删除,在另一端进行插入的顺序表,通常将允许删除的这一端称为队头,允许插入的这一端称为队尾。当表中没有元素时称为空队列。即先进先出表。循环队列就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用考点7:链表在链式存储方式中,要求每个结点由两部分组成:一部分用于存放数据元素值,称为数据域;另一部分用于存放指针,称为指针域。其中指针用于指向该结点的前一个或后一个结点(即前件或后件)。考点8:二叉树性质(1)在树结构中,每一个结点只有一个前件,称为父结点,没有父结点的只有一个,成为根结点(2)没有后件的结点成为叶子结点(3)一个结点所拥有的后件个数称为该结点的度,在树中,所有结点中最大的度称为树的度(4)树的最大层次称为树的深度(5)在二叉树的第k层上,最多有2^(k-1)个结点(6)深度为m的二叉树最多有2^m-1个结点(7)任意一棵二叉树,度为0的结点(即叶子结点)总是比度为2的结点多一个(8)满二叉树:除最后一层外,每一层上的所有结点都有两个子节点(9)完全二叉树:除最后一层外,每一层上的结点数都达到最大值,在最后一层上只缺少右边的若干结点考点9:二叉树的遍历根据访问根结点的次序,二叉树的遍历分为三类:前序遍历、中序遍历和后序遍历。(1)前序遍历先访问根结点,然后遍历左子树,最后遍历右子树;并且在遍历左、右子树时,仍需先访问根结点,然后遍历左子树,最后遍历右子树。
(2)中序遍历先遍历左子树、然后访问根结点,最后遍历右子树;并且,在遍历左、右子树时,仍然先遍历左子树,然后访问根结点,最后遍历右子树。例如,对图1-1中的二叉树进行中序遍历的结果(或称为该二叉树的中序序列)(3)后序遍历先遍历左子树、然后遍历右子树,最后访问根结点;并且,在遍历左、右子树时,仍然先遍历左子树,然后遍历右子树,最后访问根结点。考点10:各种排序的复杂度(1)顺序查找需要比较n次(2)冒泡排序在最坏的情况下需要比较次数为n(n-1)/2。(3)简单插入排序法,最坏情况需要n(n-1)/2次比较;(4)希尔排序法,最坏情况需要O(n1.5)次比较。(5)简单选择排序法,最坏情况需要n(n-1)/2次比较;(6)堆排序法,最坏情况需要O(nlog2n)次比较。
第二章:第二章:
程序设计基础考点1:结构化程序设计的原则(1)自顶向上:先考虑整体,再考虑细节;先考虑全局目标,再考虑局部目标;(2)逐步求精:对复杂问题应设计一些子目标作为过渡,逐步细化;(3)模块化:把程序要解决的总目标分解为分目标,再进一步分解为具体的小目标,把每个小目标称为一个模块。(4)限制使用goto语句:在程序开发过程中要限制使用goto语句。考点2:结构化程序的基本结构结构化程序的基本结构有三种类型:顺序结构、选择结构和循环结构。考点3:面向对象方法涵盖对象及对象属性与方法、类、继承、多态性几个基本要素。
对象是面向对象方法中最基本的概念,主要特点:(1)标识惟一型(2)分类性(3)多态性(4)封装性(5)模块独立性好考点4:消息:对象间的相互合作需要一个机制来协助进行,这个机制就是消息考点5:继承是面向对象的方法的一个主要特征,分为单继承和多重继承
第三章:第三章:
软件工程基础考点1:计算机软件是包括程序、数据以及相关
文档的完整集合,软件工程包括3个要素:方法、工具和过程考点2:软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。软件生命周期还可以分为软件定义、软件开发、软件运行维护阶段软件定义阶段包括:可行性研究、需求分析软件开发阶段包括:概要设计、详细设计、实现、测试软件维护阶段包括:使用、维护、退役考点3:软件工程的理论和技术性研究主要包括:软件开发技术和软件工程管理考点4:数据流图图符的含义圆形表示加工,箭头表示数据流,等于号表示存储文件,矩形表示源、潭考点5:数据字典:是结构化分析方法的核心,数据字典是对所有与
系统相关的数据元素的一个有组织的
列表考点6:软件需求规格说明书是需求分析阶段的最后成果考点7:模块独立性衡量模块独立性的定性标准:内聚性与耦合性内聚性:是一个模块内部各个元素间彼此结合的紧密程度的度量耦合性:模块间互相连接的紧密程度的度量一个优秀的设计应尽量做到高内聚、低耦合考点8:典型的数据流类型有两种:变换型和事务型考点9:程序流程图图符的含义