搜索
第一章数据结构与算法1.算法的基本特征：可行性，确定性，有穷性，拥有足够的情报。2.算法的有穷性是指算法程序的运行时间是有限的。3.算法的时间复杂度：执行算法所需要的计算工作量（基本运算次数）。算法的空间复杂度：这个算法所需要的内存空间。两者之间没有必然直接的联系4.程序执行的效率与数据的存储结构、数据的逻辑结构、程序的控制结构、所处理的数据量等有关。5.线性结构的两大条件：有且只有一个根节点；每一个结点最多只有一个前件，也最多有一个后件。6.线性表的顺序存储结构具备如下两个基本特征：（１）线性表中的所有元素所占的存储空间是连续的；（２）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。7.栈是先进后出的线性表。8.队列是先进先出的线性表。9.栈和队列都是线性结构。10.栈顶元素总是后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。11.循环队列中元素的个数是由队头指针和队尾指针共同决定。12.树是简单的非线性结构，所以二叉树作为树的一种也是一种非线性结构。13.循环队列中的元素个数随队头指针与队尾指针的变化而动态变化。14.由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时，头尾指针均相等。15.在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化。16.循环队列是队列的一种顺序存储结构。17.循环链表和双向链表都是线性结构。18.线性链表中数据的插入和删除都不需要移动表中的元素，只需改变结点的指针域即可。19.线性链表中的各数据结点的存储空间可以不连续，各数据元素的存储顺序与逻辑顺序可以不一致。20.链式存储结构既可以针对线性结构也可以针对非线性结构。21.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的。22.线性表（线性结构）的链式存储结构所需要的存储空间一般要多于顺序存储结构。23.栈支持子程序调用。栈是一种只能在一端进行插入或删除的线性表，在主程序调用子函数时要首先保存主程序当前的状态，然后转去执行子程序，最终把子程序的执行结果返回到主程序中调用子程序的位置，继续向下执行。24.在任意一棵二叉树中，度为0的叶子节点总是比度为2的节点多一个。25.满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点。26.完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。27.二叉树的遍历：1．前序遍历：①访问根结点；②前序遍历左子树；③前序遍历右子树2．中序遍历：①中序遍历左子树；②访问根结点；③中序遍历右子树3．后序遍历：①后序遍历左子树；②后序遍历右子树；③访问根结点28.一颗二叉树的前序遍历序列为ABDGCFK，中序遍历序为DGBAFCK，则结点的后序遍历序序列为什么？后序应该是GDBFKCA。中序：顺序为左根右。并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。29.顺序查找：最好情况：1次；最坏情况：n次；需要比较n/2次，复杂度为O(n)。二分法查找：最坏情况：次；复杂度为30.排序中：最坏情况冒泡排序，简单插入排序，简单选择排序，选择排序的最坏情况时间都为而堆排序的最坏情况时间为冒泡排序，简单插入排序，简单选择排序，选择排序的最坏情况比较次数都为n(n-1)/2次而堆排序的最坏情况次数为次第二章程序设计基础1.结构化程序设计的基本原则：自顶而下；逐步求精；模块化；限制goto语句使用。2.结构化程序所要求的基本结构：顺序结构；选择（分支）结构；重复（循环）结构。3.对象的基本特点：标识唯一性；分类性；多态性；封装性；模块独立性好。4.对象之间进行通信的构造叫做消息。5.对象的多态性是指同一个操作可以是不同对象的行为，导致完全不同的行为。6.对象不一定必须有继承性。7.继承是面向对象的方法的一个主要特征。8.继承是指类之间共享属性和操作的机制。第三章软件工程基础1.软件指的是计算机系统中与硬件相互依赖的另一部分，包括程序、数据和有关的文档。2.软件生命周期是指软件产品从提出、实现、使用维护到停止使用退役的过程。3.软件的生命周期有三大阶段：一．软件定义期：问题定义；可行性研究；需求分析。二．软件开发期：软件设计（概要设计和详细设计）；软件实现；软件测试。三．运行维护期：运行和维护。4.需求分析阶段的主要工作：需求获取；需求分析；编写需求规格说明书；需求评审。5.需求分析阶段（结构化分析方法）常用的工具：数据流图（DFD）；数据字典（DD）；判定表；判定树；6.数据字典（DD）是结构化分析的核心。7.软件需求规格说明书有以下几个方面的作用：①便于用户、开发人员进行理解和交流；②反映出用户问题的结构，可以作为软件开发工作的基础和依据；③作为确认测试和验收的依据。8.软件设计中常用的工具：①图形工具：程序流程图；N-S图；PAD图；HIPO。②表格工具：判定表。③语言工具：PDL（伪码）。9.在数据流图（DFD）中，用标有名字的箭头表示数据流。在程序流程图中，用标有名字的箭头表示控制流。10.软件测试是为了发现错误而执行程序的过程，测试要以查找错误为中心，而不是为了演示软件的正确功能。不是为了评估软件或改正错误。11.软件测试方法：一．静态测试和动态测试；二．黑盒测试和白盒测试；①白盒测试：逻辑覆盖测试（语句，路径，判定，条件覆盖）；基本路径测试。②黑盒测试：等价类划分法；边界值分析法；错误推测法。12.白盒测试又称为结构测试或者逻辑驱动测试。（注重内部逻辑结构和信息）13.黑盒测试又称功能测试或者数据驱动测试。（注重测试软件的功能）14.软件测试的实施过程：单元测试；集成测试；确认（验收）测试；系统测试。15.程序调试的目的是在测试发现错误后排除错误的过程。16.软件调试的方法：强行排错法；回溯法；原因排除法（二分法；归纳法；演绎法）。第四章数据库设计基础1.数据库管理系统是数据库的机构，它是一种系统软件，负责数据库中数据组织、数据操纵、数据维护、控制及保护和数据服务等。是一种在操作系统之上的系统软件。2.数据库管理系统是数据库系统的核心。3.数据库管理系统的数据语言：①数据定义语言：负责数据的模式定义与数据的物理存取构建。②数据操纵语言：负责数据的操纵，包括查询与增，删，改等操作。③数据控制语言：负责数据的完整性。安全性的定义与检查以及并发控制，故障恢复等功能。4.数据库系统由数据库，数据库管理系统，数据库管理员，硬件，软件平台组成。5.数据库系统的特点：数据集成性；数据高共享低冗杂；数据独立性高；数据统一管理和控制（安全性，完整性，并发控制）。6.数据库应用系统中的核心问题是数据库的设计。7.数据库系统的三级模式结构：①概念模式：数据库系统中全局数据逻辑结构的描述，全体用户公共数据视图。②外模式：也称子模式或用户模式，它是用户的数据视图，给出了每个用户的局部数据描述。③内模式：又称物理模式，它给出了数据库物理存储结构与物理存取方法。8.一个数据库只有一个概念模式和一个内模式，有多个外模式。9.数据库系统的两级映射：外模式/概念模式的映射和概念模式/内模式的映射。10.当概念模式改变时，只需改变外模式/概念模式的映射，不需改变外模式，保证了数据的逻辑独立性。当内模式改变时，只需改变概念模式/内模式的映射，不需改变概念模式，保证了数据的物理独立性。11.E-R模型的基本概念：实体；属性；联系。12.E-R图中：矩形表示实体集，椭圆形表示属性，菱形表示联系。13.层次模型：用树形结构表示实体及其之间联系的模型。14.网状模型：用网状结构表示实体机器之间联系的模型。15.关系模型：用二维表来表示关系。16.二维表中的一列称为属性；一行称为元组。17.有表示公司和职员及工作的三张表，职员可在多家公司兼职。其中公司C（公司号，公司名，地址，注册资本，法人代表，员工数），职员S（职员号，姓名，性别，年龄，学历），工作W（公司号，职员号，工资），则表W的键（码）为A)公司号，职员号B)职员号，工资C)职员号D)公司号，职员号，工资参考答案：A【解析】由于职员可以再多加公司兼职，表W的键（码）应为公司关系和职员关系的主码，即公司号和职员号。18.投影：从关系模式中指定若干个属性组成的新的关系。也就是垂直分解。19.选择：从关系中找出满足给定条件的元组的操作。也就是水平抽取。20.自然连接：一种特殊的等值连接，它要求两个关系中进行比较的分量必须是相同的属性组，并且在结果中把重复的属性列去掉。而等值连接并不去掉重复的属性列。21．数据库设计的步骤：1、需求分析阶段：了解用户的数据需求、处理需求、安全性及完整性要求；2、概念设计阶段：通过数据抽象，设计系统概念模型，一般为E-R模型；3、逻辑设计阶段：设计系统的模式和外模式，将E-R图向关系数据模型转换；4、物理设计阶段：设计数据的存储结构和存取方法，如索引的设计；5、系统实施：组织数据入库、编制应用程序、试运行；6、运行维护：系统投入运行，长期的维护工作。22.在需求分析阶段建立数据字典。上机练习中的题目：1.SQL语言又称为结构化查询语言。（U4）2.视图设计一般有三种视图：自顶而下；自底而上；由内向外。(U4)3.从工程管理角度，软件设计一般分为概要设计与详细设计。（U3）4.该系统结构图的最大扇入数是__n___。5.某系统结构图如下图所示该系统结构图的最大扇出数是__3__。6.扇入指该模块在结构图中的直接上层模块数，扇出是该模块在结构图的直接下层模块数。7.单元测试主要涉及的文档是编码和详细设计说明书。（U3）。2015.8.31于杭州电子科技大学自动化学院