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