第一部分 公共基础知识.ppt

第一部分公共基础知识（30分：10道选择题+5道填空题）,数据结构与算法数据结构：讨论数据的逻辑结构和存储结构算法：对特定问题求解步骤的一种描述，算法复杂度的概念和意义。程序设计基础结构化程序设计面向对象程序设计方法软件工程基础用科学知识和技术原理来定义、开发、维护软件。数据库设计基础研究数据库的结构、存储、设计、管理和使用的一门软件学科。,一、数据结构含义相互之间存在一种或多种特定关系的数据元素的集合。,数据结构与算法,逻辑结构,集合,线性,树,图,数据的存储结构（物理结构）是指_A)存储在外存中的数据B)数据所占的存储空间量C)数据在计算机中的顺序存储方式D数据的逻辑结构在计算机中的表示,D,二、线性结构1、线性表,数据元素：记录,a1,a2,an,空闲,内存状态,顺序存储,a1,a2,an,链式存储,俗称单链表，也可形成循环单链表，双链表,循环双链表。,指针,二、线性结构2、栈和队列,进栈,出栈,栈顶,栈底,a1a2a3an,队头,队尾,入队列,出队列,各自的特点是？,eg：下列数据结构中，能够按照“先进后出”原则存取数据的是_A）循环队列B）栈C）队列D）二叉树,B,三、非线性结构1、树和二叉树,2、二叉树的性质（1）在二叉树的第i层上至多有结点。（i1）（2）深度为k的二叉树至多有结点。（k1）（3）一棵深度为k且有2k-1结点的二叉树称为满二叉树。（4）深度为k，有n个节点的二叉树，当且仅当其每个节点都与深度为k的满二叉树中编号从1至n的节点一一对应时，称之为完全二叉树。,第i层：1248依次推断,2i-1,深i层：13715依次推断,2i-1,2i-1,2i-1,满二叉树完全二叉树非完全二叉树,1,2,3,4,5,6,1,2,3,4,（5）具有n个节点的完全二叉树的深度为log2n+1（6）树的度为所有结点中最大的度（7）任何一棵二叉树如叶子结点数为n1，度为2的结点数n2，则n1=n2+13、遍历二叉树（按某种搜索路径巡访树中各节点）-图1（1）先序遍历（根结点左子树右子树）（2）中序遍历（左子树根结点右子树）（3）后序遍历（左结点右子树根结点）先序：124536中序：425163后序：452631,图1,根结点,叶子结点,DBXEAYFZC,A,B,C,D,E,F,Z,X,Y,对二叉树进行中序遍历的结果?,对二叉树进行后序遍历的结果?,DXEBYZFCA,eg1:下列叙述中正确的是_A）有一个以上根结点的数据结构不一定是非线性结构B）只有一个根结点的数据结构不一定是线性结构C）循环链表是非线性结构D）双向链表是非线性结构,B,eg:一个栈初始状态为空，首先将5,4,3,2,1依次入栈，然后退栈一次，再将元素A,B,C,D依次如栈，之后将所有元素退栈，则所有元素退栈（包括中间退栈的元素）的顺序为_eg:设某循环队列的容量为50，如果头指针front=45（指向队头元素的前一位置），尾指针rear=10（指向队尾元素），则该循环队列中共有_个元素。eg:某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为（假设根结点在第1层）_A）3B）4C）6D）7eg:一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为_。eg:下列数据结构中，属于非线性结构的是_A）循环队列B）带链队列C）二叉树D）带链栈eg:某二叉树有5个度为2的结点以及3个度为1的结点，则该二叉树中共有_个结点。eg:在深度为7的满二又树中，度为2的结点个数为_,1,D,C,B,A,2,3,4,5,15,D,DEBFCA,C,14,63,1、算法特征可行性、确定性、有穷性、拥有足够情报2、算法基本运算算术运算、逻辑运算、关系运算、数据传输3、算法基本控制结构顺序、选择、循环结构4、算法基本设计方法列举法、归纳法、递推、回溯等5、算法度量时间复杂度:执行算法所需要的计算工作量空间复杂度：算法在执行过程中所需的计算机存储空间,算法,eg:算法的时间复杂度是指_A）算法的执行时间B）算法所处理的数据量C）算法程序中的语句或指令条数D）算法在执行过程中所需要的基本运算次数,D,查找（在一个给定的数据结构中查找某个指定的元素）21，46，24，57，99，77，86，查找99顺序查找：从表中第一个记录开始，逐个进行记录关键字和给定值的比较。(适用条件)二分查找：先确定待查记录所在的区间，然后逐步缩小范围直到找到或找不到为止。（适用条件）,查找,-线性表为无序表，无论是顺序还是链式存储结构，只能用顺序查找-即使是有序线性表，如果采用链式存储结构，也只能顺序查找,-线性表为有序且顺序存储,log2n,eg:对于长度为n的有序线性表，在最坏情况下，二分查找需比较_次。,Eg:R(45),R(67),R(54),R(98),R(12),R(35),R(45),R(54),R(67),R(45),R(54),R(67),R(98),R(12),R(45),R(54),R(67),R(98),R(12),R(35),R(45),R(54),R(67),R(98),直接插入排序（将一个记录插入到已排好序的有序表中）,内部排序,排序（将记录的任意序列，重新排列成按关键字有序的序列）（1）内部排序-内存中的记录排序,Eg:R(30),R(67),R(54),R(98),R(12),R(35),R(54),R(67),交换排序（起泡排序）,内部排序,R(12),R(98),R(35),R(98),R(30),R(54),R(67),R(12),R(35),R(98),一趟交换,二趟交换,R(30),R(54),R(12),R(35),R(67),R(98),三趟交换,R(30),R(12),R(35),R(54),R(67),R(98),四趟交换,R(12),R(30),R(35),R(54),R(67),R(98),两两对比，将大数往后移，每一趟将最大的数往下沉，需要比较n-2趟。,Eg:R(30),R(67),R(54),R(98),R(12),R(35),选择排序（每一趟）,内部排序,R(12),R(67),R(54),R(98),R(30),R(35),四趟选择,二趟选择,R(12),R(30),R(54),R(98),R(67),R(35),三趟选择,R(12),R(30),R(35),R(98),R(67),R(54),一趟选择,R(12),R(30),R(35),R(54),R(67),R(98),每i趟在i至n的范围中选出最小的记录，作为有序序列中第i个记录。,eg1:下列叙述中，正确的是()A）对长度为n的有序链表进行查找，最坏情况下需要的比较次数为nB）对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为（n/2）C）对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为（log2n）D）对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为（nlog2n）eg2:下列排序方法中，最坏情况下比较次数最少的是()A)冒泡排序B)简单选择排序C)直接插入排序D)堆排序,A,D,n(n-1)/2,nlog2n,堆排序希尔排序（冒泡排序、简单选择排序、直接插入排序）,一、程序设计方法1、结构化程序设计方法：程序=算法+数据结构，围绕信息流。2、面向对象程序设计方法：软件系统是一系列离散对象的集合。二、结构化方法1、特点模块化：待开发系统由功能模块构成自顶向下，逐步求精有顺序、选择和循环三种基本结构形式2、结构化模块设计原则高内聚（模块内各元素联系紧密）低耦合（模块间联系弱）,程序设计基础,三、面向对象方法1、对象：对应用具有明确边界或意义的事物。如：一辆自行车，一台彩电，一种思想，一种调度策略。标识唯一性、分类性、多态性、封装性、模块独立性2、类:具有相似属性和相同行为（方法）模式的一组对象。类可以有子类，也可以有父类。对象是类的具体化，类是对象的抽象；继承性：子类继承父类的属性和操作。多态性：同一操作可以由多个不同类的行为或方法来具体实现。,程序设计基础,(人）王成都28,(人）田谋才28,换工作换住址,eg:软件生命周期可分为定义阶段，开发阶段和维护阶段。详细设计属于()A）定义阶段B）开发阶段C）维护阶段D）上述三个阶段eg:面向对象方法中，继承是指（）A)一组对象所具有的相似性质B)一个对象具有另一个对象的性质C)各对象之间的共同性质D)类之间共享属性和操作的机制eg:结构化程序所要求的基本结构不包括()A）顺序结构B）GOTO跳转C）选择（分支）结构D）重复（循环）结构eg:下列选项中不属于结构化程序设计原则的是()A）可封装B）自顶向下C）模块化D）逐步求精eg:在面向对象方法中，不属于“对象”基本特点的是（）A）一致性B）分类性C）多态性D）标识唯一性eg:下列选项不符合良好程序设计风格的是()A）源程序要文档化B）数据说明的次序要规范化C）避免滥用goto语句D）模块要保证高耦合、高内聚,B,D,B,A,A,D,一、软件：计算机程序及相关文档的集合。（应用软件+系统软件）二、软件工程1、概念：用科学知识和技术原理来定义、开发、维护软件的一门学科。（三要素）方法：完成软件工程项目的技术手段工具：支持软件的开发、关了、文档生成过程：支持软件开发的各个环节的控制、管理2、软件生命周期：从提出开发软件要求开始，直到该软件报废不用为止的整个时期。软件定义期-软件开发期-运行维护期问题定义-可行性研究-需求分析-概要设计-详细设计-软件编码-软件测试-软件维护（最长）,软件工程,三、结构化分析方法（SA法，是需求分析中使用最多的方法）1、特点：分解，抽象（将系统抽象成一个模型，有输入和输出的盒子，对这个盒子逐层分解）2、描述工具（1）数据流图（DFD）描述系统内数据的流动及其变化的图示。建立顶层DFD-细化DFD（2）数据字典（DD）将DFD中的数据流和数据存储元素进一步细化。病人报表=病床号+病人姓名+年龄+性别+一般症候+要害症候*DFD和DD构成系统的逻辑模型（3）软件需求规格说明书,软件工程,监视病员系统,病员数据,病员报表,病员病历,三、结构化设计方法（SD法）1、原则模块化；抽象；信息隐蔽；模块的独立性（高内聚、低耦合）2、内容（1）概要设计（总体）：明确系统干什么，划分模块，功能，调用关系；CSD控制结构图（2）详细设计：解决系统如何干，为任务选择适当的技术手段和处理方法；模块处理说明书，PAD问题分析图，NS图,程序流程图。四、软件测试1、目的：为发现软件中的错误而执行软件的过程。,软件工程,四、软件测试2、方法（1）白盒法（结构测试）法：检验程序每条通路。（2）黑盒（功能测试）法：在程序接口进行的测试。3、步骤（1）单元测试：发现模块内部逻辑结构及接口的错误。（白盒）（2）集成测试：发现模块组装过程中的错误。-非渐增式测试：将所有经过单元测试的模块连接测试-渐增式测试：逐步组装测试（3）验收（确认）测试：验证软件的功能和性能。（4）系统测试：把经过测试的模块装配成一个完整系统测试，用户积极参与，往往使用实际数据eg:对软件设计的最小单位（模块或程序单元）进行的测试通常称为【】测试。五、调试：诊断和改正程序中的错误,软件工程,eg1:软件（程序）调试的任务是()A）诊断和改正程序中的错误B）尽可能多地发现程序中的错误C）发现并改正程序中的所有错误D）确定程序中错误的性质eg2:数据流程图（DFD图）是()A）软件概要设计的工具B）软件详细设计的工具C）结构化方法的需求分析工具D）面向对象方法的需求分析工具eg3:在软件开发中，需求分析阶段产生的主要文档是（）A）软件集成测试计划B）软件详细设计说明书C）用户手册D）软件需求规格说明书eg4:下面描述中错误的是（）A）系统总体结构图支持软件系统的详细设计B）软件设计是将软件需求转换为软件表示的过程C）数据结构与数据库设计是软件设计的任务之一D）PAD图是软件详细设计的表示工具,A,C,D,A,eg:下列叙述中错误的是()A）软件测试的目的是发现错误并改正错误B）对被调试的程序进行“错误定位”是程序调试的必要步骤C）程序调试通常也称为DebugD）软件测试应严格执行测试计划，排除测试的随意性。eg:程序流程图中带箭头的线段表示的是（）A）图元关系B）数据流C）控制流D）调用关系eg:下列选项中不属于软件生命周期开发阶段任务的是()A）软件测试B）概要设计C）软件维护D）详细设计eg:下列描述中正确的是()A）软件工程只是解决软件项目的管理问题B）软件工程主要解决软件产品的生产率问题C）软件工程的主要思想是强调在软件开发过程中需要应用工程化原则D）软件工程只是解决软件开发中的技术问题eg:在软件设计中，不属于过程设计工具的是()A）PDL(过程设计语言)B）PAD图C）N-S图D）DFD图,A,C,C,C,D,一、基本概念DBDBMS（数据库开发工具）DBS二、数据库的“一少三性”三、数据库系统的三级模式模式（概念模式）：是数据库中全体数据的逻辑结构和特征描述外模式（用户模式）：数据库用户能看见和使用的局部数据的逻辑结构和特征描述内模式（存储模式）：数据物理结构和存储方式的描述eg:数据库中数据是否压缩、加密是涉及到数据库系统的_模式设计。A）内B）外C）概念D）用户四、数据模型数据在数据库内的相互依存关系的描述（层次、网状、关系），任何DBMS都是基于某种数据模型。,数据库设计基础,A,三、数据模型1、实体联系模型（E-R图）-概念模型一对一联系（1：1）一对多联系（1：n）一对一联系（m：n）eg：一个教师可讲授多门课程，一门课程可由多个教师讲授。则实体教师和课程间的联系是_A）1:1联系B）1:m联系C）m:1联系D）m:n联系注：矩形表示实体，菱形表示联系，属性用椭圆形,数据库设计基础,D,四、数据模型2、结构数据模型-电脑角度关系模型：用二维表格结构表达实体集，用外键表示实体间联系。-关系：一张二维表格称为一个关系。（一个关系就是一个二维表）元组：表格中的每一行称为一个元组。在Access2003中，称为记录。属性：表格中的每一列称为一个属性。在Access2003中，称为字段。域：属性的取值范围。（度：属性的个数。）候选键：唯一标识元组的属性值主键（码）：从候选键中选取一个作为用户使用的键外键：如果表中一个字段不是本表的主关键字，而是另外一个表的主关键字。3、关系操作选择（Select）：它是在关系中选择满足条件的元组。选择操作是从行的角度进行的运算。投影（Project）：关系R上的投影是指从R中选择若干属性组成新的关系。选择操作是从列的角度进行的运算。,数据库设计基础,eg:在关系A(S,SN,D)和关系B(D,CN,NM)中，A的主关键字是S，B的主关键字是D，则称【】是关系A的外码。,3、关系操作,数据库设计基础,R,S,(1)RS(2)RS(3)A,CR(4)RS(5)RS,21,联接（Join）：联接是关系的横向结合，联接运算将两个关系模式拼接成一个更宽的关系模式，生成的新关系中包含满足联接条件的元组。-等值联接：按照字段值对应相等为条件进行的联接操作。-自然联接：是去掉重复属性的等值联接。-笛卡尔积,四、数据库规范化原理1、实体完整性关系中主码的值不能为空。或者说若属性A是基本关系R的主码，则属性A不能取空值。2、参照完整性若属性（或属性组）F是基本关系R的外码,它与基本关系S的主码Ks相对应，则对于R中每个元组在F上的值必须为：-或