二级公共基础知识.docx

公共基础学问基本要求1 .驾驭算法的基本概念。2 .驾驭基本数据结构及其操作。3 .驾驭基本排序和杳找算法。4 .驾驭逐步求精的结构化程序设计方法。5 .驾驭软件工程的基本方法，具有初步应用相关技术进行软件开发的实力。6 .驾驭数据库的基本学问，/解关系数据库的设计.考试内容一、基本数据结构与算法1 .算法的基本概念：算法困琲度的概念和意义（时间困雄度与空间困难度）。2 .数据结构的定义；数据的逻辑结构与存储结构：数据结构的图形表示：线性结构与非线性结构的概念。3 .线性表的定义：线性表的依次存储结构及其插入与删除运兑。4 .栈和队列的定义：栈和队列的依次存储结构及其基本运算。5 .线性单链表、双向链表与循环链表的结构及其基本运算.6 .树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7 .依次查找与二分法杳找兑法：基本排序算法（交换类排序，选择类排序，插入类排序）。二、程序设计基础1 .程序设计方法与风格。2 .结构化程序设计。3 .面对对象的程序设计方法，对象，方法，属性及继承与多态性。三、软件工程基础1 .软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。2 .结构化分析方法，数据流图，数据字典，软件需求规格说明书。3 .结构化设计方法，总体设计与具体设计。4 .软件测试的方法,白盒测试与黑盒测试,测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。5 .程序的调试，静态调忒与动态调试。四、数据库设计基研I1.数据库的基本概念：数据库，数据库管理系统，数据库系统.2 .数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。3 .关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。4 .数据库设计方法和步界：需求分析、概念设计、逻辑设计和物理设计的相关策略。考试方式公共基础学问有10道选择题和5道填空题共三特别。第一堂数据结构与算法1.1 算法算法：是指解题方案的精确而完整的描述。算法不等于程序，也不等计算机方法,程序的编制不行能优于算法的设计。算法的基本特征：是一组严遒地定义运算依次的规则，每一个规则都是有效的，是明确的，此依次将在有限的次数下终止。特征包括：（I）可行性；（2）确定性，算法中每一步骤都必需有明确定义，不充许有模棱两可的说明，不允许有多义性；（3）有穷性，算法必需能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义：（4）拥有足够的情报.算法的基本要素：一是对数据对象的运算和操作：二是算法的限制结构。指令系统：一个W算机系统能执行的全部指令的集合。基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。算法的限制结构：依次结构、选择结构、循环结构。算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法.算法困难度：匏法时间困难度和算法空间困难度算法时间困难度是指执行算法所须要的计兑工作量，算法空间困难度是指执行这个算法所须要的内存空间。1.2 数据结构的基本基本概念数据结构探讨的:个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构：（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构：（3）对各种数据结构进行的运獴。数据结构是指相Ii有美联的数据元素的集合。数据的逻辑结构包含：（1）表示数据元素的信息：（2）表示各数据元素之间的前后件关系.数据的存储结构有依次、链接、索引等。线性结构条件：（I）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。非线性结构：不满意线性结构条件的数据结构。1.3线性表及其依次存储结构线性表由一组数据元素构成，数据元素的位理只取决于自己的序号，元本之间的相对位置是线性的。在困难线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。非空线性表的结构特征：（1）且只有个根结点a1.,它无前件：（2）有且只有个终端结点an,它无后件：（3）除根结点与终端结点外，其他全部结点有且只有一个前件，也有且只有一个后件.结点个数n称为线性表的长度，当n=0时，称为空表。线性表的依次存储结构具有以卜.两个基本特点：（1）线性表中全部元素的所占的存储空间是连续的：（2）线性表中各数据元素在存储空间中是按逻辑依次依次存放的。ai的存储地址为：ADR（ai）=ADR（a1.）+（i-1.）k,ADR（a1.）为第一个元素的地址，k代表每个元素占的字节数。依次表的运算：插入、删除。（详见I4-I6页）1.4栈和队列栈是限定在一端进行插入与删除的线性表，允许插入与删除的端称为栈顶，不允许插入与删除的另一端称为栈底。栈依据“先进后出“（FI1.O）或“后进先出”（1.IFO）组织数据，栈具有记忆作用。用top表示栈顶位置，用bo1.tom表示栈底。栈的基本运算：（1）插入元素称为入栈运算：（2）删除元素称为退栈运算：（3）读梭顶元素是将栈顶元素赋绐个指定的变量，此时指针无变更。队列是指允许在一湍（队尾）进入插入，而在另一端（队头）进行删除的线性表.Rear指针指向队里，front指针指向队头。队列是“先进行出"（FIFO）或“后进后出”（1.I1.O）的线性表。队列运算包括（1）入队运算：从队尾插入一个元素：（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空,s=1.J1.front=ear表示队列满I.5线性链表数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，荷称结点。结点由两部分组成：（D用于存储数据元素值，称为数据域：（2）用于存放指针，称为指针域，用r指向前一个或后一个结点。在集式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储依次与数据元素之间的逻辑关系可以不一样，而数据元素之间的逻辑关系是由指针域来确定的。徒式存储方式即可用于表示线性结构，也可用于表示非线性结构，线性链表，HEAD称为头指针，HEAd=NU1.1.（或0）称为空表,假如是两指针:左指针（1.Iink）指向前件结点，右指针（RIink）指向后件结点.线性链表的施本运算：自找、插入、删除。1.6树与二叉树树是一种简洁的非线性结构，全部元素之间具有明显的U次特性.在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。在树结构中，个结点所拥有的后件的个数称为该结点的度，全部结点中最大的度称为树的度”树的最大层次称为树的深度.二叉树的特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两株子树，且分别称为该结点的左子树与右子树。二叉树的基本性质：（1）在二叉树的第k层上,最多有2k1.（Q1.）个结点：（2）深度为m的二叉树最多有2m-1.个结点：（3度为0的结点（即叶子结点）总是比度为2的结点多一个：<4）具有n个结点的二叉树,其深度至少为Iog2n）+I,其中Iog2n）表示取1.og2n的整数部分：（5）具有n个结点的完全二叉树的深度为k>g2n+1.:（6）设完全二叉树共有n个结点。假如从根结点起先，按层序（每一层从左到右）用自然数1.2,n绐结点进行编号<k=1.,2.n）,有以下结论：若k=I,则该结点为根结点，它没有父结点：若k>1.,则该结点的父结点编号为INT（k/2）：若2kn,则编号为k的结点的左子结点编号为2k：否则该结点无左子结点（也无右子结点）：若2k+1.n,则编号为k的结点的右子结点编号为2k+1.：否则该结点无右子结点。满二叉树是指除最终一以外，每一U上的全部结点有两个子结点，则k层上有2k-1.个结点深度为m的满二叉树有2m-1.个结点。完全二叉树是指除最终一层外，每一层上的结点数均达到显大值，在段终一层上只缺少右边的若干结点。二叉树存储结构接受链式存储结构，对于满二叉树与完全二叉树可以按层序进行依次存储。二叉树的遍历：（I）前序遍历（D1.R）,首先访问根结点，然后遍历左子树，最终遍历右子树：中序遍历（1.DR）,首先遍历左子树，然后访问根结点，最终遍历右子树：（3）后序遍历（1.RD）首先遍历左子树，然后访问遍历右子树，最终访问根结点。I.7查找技术依次杳找的运用状况：（1）线性表为无序表；（2）表接受链式存储结构。二分法查找只适用于依次存储的有序表，对于长度为n的有序线性表，最坏状况只需比较1.og2n次。I.8排序技术排序是指聘一个无序序列整理成按值非递减依次排列的有序序列,交换类排序法：（1）日泡排序怯，须要比较的次数为n（nN2;（2）快速排序怯。插入类排序法：（1）简洁插入排序法，最坏状况须要n（n-1）/2次比较：（2）希尔排序法，最坏状况须要0（n1.5）次比较。选择类排序法：（1）简洁选择排序法，最坏状况须要Mn-Iv2次比较：（2）堆排序法，最坏状况须要O（n1.og2n）次比较。其次章程序设计基础2.1程序设计设计方法和风格如何形成良好的程序设计风格I、源程序文档化：2、数据说明的方法；3、语句的结构：4,输入和输出.注样分序言性注理和功能性注样，语句结构清晰第一、效率其次。2.2结构化程序设计结构化程序设计方法的四条原则是：1.自顶向下：2.逐步求精：3.模块化：4.限制运用goio语句。结构化程序的基本结构和特点：（1）依次结构：一种简洁的程序设计，最基本、最常用的结构：（2）选择结构：乂称分支结构，包括简洁选择和多分支选择结构，可依据条件,推断应当选择哪一条分支来执行相应的语句序列：（3）IIi复结构：又称循环结构，可依据给定条件，推断是否须要玳复执行某一相同程序段。2.3面对对象的程序地计面对对象的程序设计：以6（）年头木挪威奥斯陆高校和挪城计钵机中心研制的SIMU1.A语言为标记。面对对象方法的优点：（1）与人类习惯的思维方法样：（2）稳定性好：（3）可重用性好；（4）易于开发大型软件产品;（5）可维护性好。时象是面对对象方法中最基本的概念，可以用来表示客观世界中的任何实体，对象是实体的抽缭。面对对象的程序设计方怯中的对象是系统中用来描述客观事物的一个实体，是构成系统的个基本单位，由组表示其静态特征的属性和它可执行的组操作组成。属性即对象所包含的信息,操作描述了对象执行的功能,操作也称为方法或服务。对象的基本特点：（1）标识惟性：（2）分类性;（3）多态性：（4）封装性：（5）模块独立性好。类是指具有共同属性,共同方法的对象的集合.所以类是对象的抽象，对象是对应类的一个实例。消息是一个实例与另一个实例之间传递的信息。消息的组成包括（1）接收消息的对象的名称：（2）消息标识符，也称消息名：（3）零个或多个参数。维承是指能够干脆获得已有的性质和特征，而不必我更定义他们。继承分总继承和多重继承。中维承指一个类只允许有一个父类，多重继承指一个类允许石多个父类。多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象.第三章软件工程基础3.I软件工程基本概念计算机软件是包括程序、数据及相关文档的完整集合。软件的特点包括：（1）软件是一种逻辑实体：（2）软件的生产与硬件不同，它没有明显的制作过程：（3）软件在运行、运用期间不存在磨损、老化问题：（4）软件的开发、运行对计算机系统具有依靠性，受计算机系统的限制，这导致了软件移植的问题：（5）软件困难性高，成本昂贵：（6）软件开发涉及诸多的社会因素。软件按功能分为应用软件,系统软件、支