部分公共基础知识.ppt

《部分公共基础知识.ppt》由会员分享，可在线阅读，更多相关《部分公共基础知识.ppt（33页珍藏版）》请在三一办公上搜索。

1、第一部分 公共基础知识（30分：10道选择题+5道填空题）,数据结构与算法数据结构：讨论数据的逻辑结构和存储结构算法：对特定问题求解步骤的一种描述，算法复杂度的概念和意义。程序设计基础结构化程序设计面向对象程序设计方法软件工程基础用科学知识和技术原理来定义、开发、维护软件。数据库设计基础研究数据库的结构、存储、设计、管理和使用的一门软件学科。,一、数据结构含义相互之间存在一种或多种特定关系的数据元素的集合。,数据结构与算法,逻辑结构,集合,线性,树,图,数据的存储结构（物理结构）是指_A)存储在外存中的数据 B)数据所占的存储空间量C)数据在计算机中的顺序存储方式 D数据的逻辑结构在计算机中的

2、表示,D,二、线性结构1、线性表,数据元素：记录,a1,a2,an,空闲,内存状态,顺序存储,a1,a2,an,链式存储,俗称单链表，也可形成循环单链表，双链表,循环双链表。,指针,二、线性结构2、栈和队列,进栈,出栈,栈顶,栈底,a1 a2 a3 an,队头,队尾,入队列,出队列,各自的特点是？,eg：下列数据结构中，能够按照“先进后出”原则存取数据的是_ A）循环队列 B）栈 C）队列 D）二叉树,B,三、非线性结构1、树和二叉树,2、二叉树的性质（1）在二叉树的第i层上至多有 结点。（i1）（2）深度为k的二叉树至多有 结点。（k 1）（3）一棵深度为k且有2k-1结点的二叉树称为满二叉

3、树。（4）深度为k，有n个节点的二叉树，当且仅当其每个节点都与深度为k的满二叉树中编号从1至n的节点一一对应时，称之为完全二叉树。,第i层：1 2 4 8 依次推断,2i-1,深i层：1 3 7 15 依次推断,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）中序遍历（左子树 根结点

4、 右子树）（3）后序遍历（左结点 右子树 根结点）先序：1 2 4 5 3 6 中序：4 2 5 1 6 3后序：4 5 2 6 3 1,图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依次如栈，之后将所有元素退栈，则

5、所有元素退栈（包括中间退栈的元素）的顺序为_eg:设某循环队列的容量为50，如果头指针front=45（指向队头元素的前一位置），尾指针rear=10（指向队尾元素），则该循环队列中共有_个元素。eg:某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为（假设根结点在第1层）_A）3 B）4 C）6 D）7eg:一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为 _。eg:下列数据结构中，属于非线性结构的是_ A）循环队列 B）带链队列 C）二叉树 D）带链栈 eg:某二叉树有5个度为2的结点以及3个度为1的结点，则该二叉树中共有 _个结点。eg:在

6、深度为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,查找（在一个给定的数据结构中查找

7、某个指定的元素）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),

8、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

9、),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)

10、,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

11、)直接插入排序 D)堆排序,A,D,n(n-1)/2,nlog2n,堆排序希尔排序（冒泡排序、简单选择排序、直接插入排序）,一、程序设计方法1、结构化程序设计方法：程序=算法+数据结构，围绕信息流。2、面向对象程序设计方法：软件系统是一系列离散对象的集合。二、结构化方法1、特点模块化：待开发系统由功能模块构成自顶向下，逐步求精有顺序、选择和循环三种基本结构形式2、结构化模块设计原则高内聚（模块内各元素联系紧密）低耦合（模块间联系弱）,程序设计基础,三、面向对象方法1、对象：对应用具有明确边界或意义的事物。如：一辆自行车，一台彩电，一种思想，一种调度策略。标识唯一性、分类性、多态性、封装性、模块

12、独立性2、类:具有相似属性和相同行为（方法）模式的一组对象。类可以有子类，也可以有父类。对象是类的具体化，类是对象的抽象；继承性：子类继承父类的属性和操作。多态性：同一操作可以由多个不同类的行为或方法来具体实现。,程序设计基础,(人）王成都28,(人）田谋才28,换工作换住址,eg:软件生命周期可分为定义阶段，开发阶段和维护阶段。详细设计属于()A）定义阶段 B）开发阶段 C）维护阶段 D）上述三个阶段eg:面向对象方法中，继承是指（）A)一组对象所具有的相似性质 B)一个对象具有另一个对象的性质C)各对象之间的共同性质 D)类之间共享属性和操作的机制eg:结构化程序所要求的基本结构不包括()

13、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、概念：用科学知识和技术原理来定义、开发、维护软件的一门学科。（三要素）方法：完

14、成软件工程项目的技术手段 工具：支持软件的开发、关了、文档生成 过程：支持软件开发的各个环节的控制、管理2、软件生命周期：从提出开发软件要求开始，直到该软件报废不用为止的整个时期。软件定义期-软件开发期-运行维护期 问题定义-可行性研究-需求分析-概要设计-详细设计-软件编码-软件测试-软件维护（最长）,软件工程,三、结构化分析方法（SA法，是需求分析中使用最多的方法）1、特点：分解，抽象（将系统抽象成一个模型，有输入和输出的盒子，对这个盒子逐层分解）2、描述工具（1）数据流图（DFD）描述系统内数据的流动及其变化的图示。建立顶层DFD-细化DFD（2）数据字典（DD）将DFD中的数据流和数据

15、存储元素进一步细化。病人报表=病床号+病人姓名+年龄+性别+一般症候+要害症候*DFD和DD构成系统的逻辑模型（3）软件需求规格说明书,软件工程,监视病员系统,病员数据,病员报表,病员病历,三、结构化设计方法（SD法）1、原则模块化；抽象；信息隐蔽；模块的独立性（高内聚、低耦合）2、内容（1）概要设计（总体）：明确系统干什么，划分模块，功能，调用关系；CSD控制结构图（2）详细设计：解决系统如何干，为任务选择适当的技术手段 和处理方法；模块处理说明书，PAD问题分析 图，NS图,程序流程图。四、软件测试1、目的：为发现软件中的错误而执行软件的过程。,软件工程,四、软件测试2、方法（1）白盒法（

16、结构测试）法：检验程序每条通路。（2）黑盒（功能测试）法：在程序接口进行的测试。3、步骤（1）单元测试：发现模块内部逻辑结构及接口的错误。（白盒）（2）集成测试：发现模块组装过程中的错误。-非渐增式测试：将所有经过单元测试的模块连接测试-渐增式测试：逐步组装测试（3）验收（确认）测试：验证软件的功能和性能。（4）系统测试：把经过测试的模块装配成一个完整系统测试，用 户积极参与，往往使用实际数据eg:对软件设计的最小单位（模块或程序单元）进行的测试通常称为【】测试。五、调试：诊断和改正程序中的错误,软件工程,eg1:软件（程序）调试的任务是()A）诊断和改正程序中的错误 B）尽可能多地发现程序中

17、的错误 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）软件测试的

18、目的是发现错误并改正错误B）对被调试的程序进行“错误定位”是程序调试的必要步骤C）程序调试通常也称为DebugD）软件测试应严格执行测试计划，排除测试的随意性。eg:程序流程图中带箭头的线段表示的是（）A）图元关系 B）数据流 C）控制流 D）调用关系eg:下列选项中不属于软件生命周期开发阶段任务的是()A）软件测试 B）概要设计 C）软件维护 D）详细设计 eg:下列描述中正确的是()A）软件工程只是解决软件项目的管理问题 B）软件工程主要解决软件产品的生产率问题 C）软件工程的主要思想是强调在软件开发过程中需要应用工程化原则 D）软件工程只是解决软件开发中的技术问题 eg:在软件设计中，不

19、属于过程设计工具的是()A）PDL(过程设计语言)B）PAD图 C）N-S图 D）DFD图,A,C,C,C,D,一、基本概念DBDBMS（数据库开发工具）DBS二、数据库的“一少三性”三、数据库系统的三级模式模式（概念模式）：是数据库中全体数据的逻辑结构和特征描述外模式（用户模式）：数据库用户能看见和使用的局部数据的逻辑结构和特征描述内模式（存储模式）：数据物理结构和存储方式的描述eg:数据库中数据是否压缩、加密是涉及到数据库系统的_模式设计。A）内 B）外 C）概念 D）用户四、数据模型 数据在数据库内的相互依存关系的描述（层次、网状、关系），任何DBMS都是基于某种数据模型。,数据库设计基

20、础,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、结构数据模型-电脑角度关系模型：用二维表格结构表达实体集，用外键表示实体间联系。-关系：一张二维表格称为一个关系。（一个关系就是一个二维表）元组：表格中的每一行称为一个元组。在Access 2003中，称为记录。属性：表格中的每一列称为一个属性。在Acc

21、ess 2003中，称为字段。域：属性的取值范围。（度：属性的个数。）候选键：唯一标识元组的属性值主键（码）：从候选键中选取一个作为用户使用的键外键：如果表中一个字段不是本表的主关键字，而是另外一个表的主关键字。3、关系操作选择（Select）：它是在关系中选择满足条件的元组。选择操作是从行的角度进行的运算。投影（Project）：关系R上的投影是指从R中选择若干属性组成新的关系。选择操作是从列的角度进行的运算。,数据库设计基础,eg:在关系A(S,SN,D)和关系B(D,CN,NM)中，A的主关键字是S，B的主关键字是D，则称【】是关系A的外码。,3、关系操作,数据库设计基础,R,S,(1)

22、RS(2)RS(3)A,CR(4)R S(5)R S,21,联接（Join）：联接是关系的横向结合，联接运算将两个关系模式拼接成一个更宽的关系模式，生成的新关系中包含满足联接条件的元组。-等值联接：按照字段值对应相等为条件进行的联接操作。-自然联接：是去掉重复属性的等值联接。-笛卡尔积,四、数据库规范化原理1、实体完整性 关系中主码的值不能为空。或者说若属性A是基本关系R的主码，则属性A不能取空值。2、参照完整性 若属性（或属性组）F是基本关系R的外码,它与基本关系S的主码Ks相对应，则对于R中每个元组在F上的值必须为：-或者取空值；-或者等于S中某个元组的主码值。3、用户自定义完整性 如：某

23、个属性的取值范围在0-100之间,数据库设计基础,实体完整性约束要求关系数据库中元组的【4】属性值不能为空。,四、关系模型的规范化1、第一范式（1NF）：每个属性不可再分。2、第二范式（2NF）：每一个非主属性完全函数依赖于R的主码。3、第三范式（3NF）：每一个非主属性都不传递函数依赖于R的任何一个的候选码。五、数据库设计,数据库设计基础,eg1：层次型、网状型和关系型数据库划分原则是（）A)记录长度 B)文件大小 C)联系的复杂程度 D)数据间的联系方式eg2:数据库设计中反映用户对数据要求的模式是（）A)内模式 B)概念模式 C)外模式 D)设计模式,D,A,C,B,D,eg:数据库设计

24、中，用E-R图来描述信息结构但不涉及信息在计算机中的表示，它属于数据库设计的()A）需求分析阶段 B）逻辑设计阶段 C）概念设计阶段 D）物理设计阶段eg:在学生管理的关系数据库中，存取一个学生信息的数据单位是()A）文件 B）数据库 C）字段 D）记录 eg:数据库管理系统中负责数据模式定义的语言是()A）数据定义语言 B）数据管理语言C）数据操纵语言 D）数据控制语言,C,D,A,（1）数据定义语言：负责数据的模式定义与数据的物理存取构建；（2）数据操纵语言：负责数据的操纵，如查询与增、删、改等；（3）数据控制语言：负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等。,eg:数据库设计的四个阶段是：需求分析，概念设计，逻辑设计和_,物理设计,则由关系R和S得到关系T的操作是?,则由关系R得到关系S的操作是?,eg:索引属于()A)模式 B)内模式 C)外模式 D)概念模式,B,