基础知识第一章数据结构与算法

考点 算法的基本概考点 算法复杂运行，效率均不同。这表明使用时间单位衡量算法的效率是不合适的。撇开这些与计算考点 数据结构的定 数据的逻辑结构是对数据元间的逻辑关系的描述，它可以用一个数据元素的集合和定构由于数据元素在计算机空间中的位置关系可能与逻辑关系不同，因此，为了表示存放在计算机空间中的各数据元间的逻辑关系（即前后件关系），在数据的结构中，不仅要存放各数据元素的信息，还需要存放各数据元间的前后件关系的信息。一种数据的逻辑结构根据需要可以表示成多种结构，常用的结构有顺序、、索引等结构。而采用不同的结构，其数据处理的效率是不同的。因此，在进行数据处考点 线性结构与非线性结考点 栈及其基本运为2分，此考点为重点掌握内容，读者应该掌握栈的运算。栈是限定只在一端进行与删除的线性表，通常称、删除的这一端为栈顶，另一端为栈底。当表中没有元素时称为空栈。栈顶元素总是后入的元素，从而也是最先被删除的入栈运算：入栈运算是指在栈顶位置一个新元素。首先将栈顶指针加一（即top1考点 线性链表的基本概在链式方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据线性表的链式结构称为线性链表。 考点 树与二叉树及其基本性性质5:具有n个结点的完全二叉树的深度为［log2n］+1IN（k/2考点 二叉树的遍考点 顺序查 考点10二分法查找 对于长度为n的有序线性表，在情况下，二分查找只需要比较log2n次考点11交换类排序法 【例3】以 A 【例6】设有一个已按各元素的值排好序的线性表（长度大于2）定的值k，分别用顺下，s和b的关系是（考点9） 左边子表中的元素都不大于右边子表中的元素C） （考点 （考点 考点 结构化程序设计的原思想和结构化思想，使大型的开发和编程得到了极大的改善。结构化程序设计方法的主要考点 面象方法的基本概 解析：20世纪70年代提出了"结构化程序设计（structuredprogramming）"的思想和方法。结构化程序设计方法引入了工程化思想和结构化思想，使大型的开发和编程得到了极大的 （考点 （考点 第三章工程基经过对部分考生的以及对近年的总结分析，笔试部分经常考查的是生命周期、设计的基本原理，测试的目的、调试的基本概念，读者应对此部分进行重点考点1定义与特集合。程序是开发根据用户需求开发的、用程序设计语言描述的、适合计算机执行的指令序列。数据是使程序能正常信息的数据结构。文档是与程序的开发、和使用有关小提示：应用是为解决特定领域的应用而开发的；系统是计算机管理自身资源，提高计算机使用效率并为计算机用户提供各种服务的；支撑是介于两者之间，协助用户开发的工具性软考点2工程过程与生命周内容，读者应该识记生命周期的定义，主要活动阶段及其任务。 考点3设计的基本概1.设计的基 2.设计的基本原在程序结构中，各模块的内聚性越强，则耦合性越弱。一般较优秀的设计，应尽量做考点 详细设考点5测试的目考点6测试的实 集成测试是测试和组装的过程，主要目的是发现与接口有关的错误，主要依据是概要设计说明书。集成测试所设计的内容包括：单元的接口测试、全局数据结构测试、边界条件和输入的测试等。集成测试时将模块组装成程序，通常采用两种方式：非增量方式组装确认测试的任务是验证的功能和性能，以及其他特性是否满足了需求规格说明中确定的各种需求，包括配置是否完全、正确。确认测试的实施首先运用黑盒测试方法，对进行有效性测试，即验证被测是否满足需求规格说明确认的标准。系统测试是通过测试确认，作为整个基于计算机系统的一个元素，与计算机硬件、外设、支撑、数据和等其他系统元素组合在一起，在实际运行（使用）环境下对计算机考点7调试的基本概考 疑难解答：

3.5 （考点 开 演 解析：关于测试目的的基本知识，IEEE的定义是：使用人工或自动来运行或测定某个 （考点 （考点 （考点7）A）注意修改错误本身而不仅仅是错误的征兆和表现B） 本目标是用比较抽象概括的方式确定目标系统如何完成预定的任务，即设计是确定系统的【例2】是指把一个待开发的（考点【例3】数据流图采用4种符号表示、数据源点和终点、数据流向和数据加工（考解析：数据流图可以表达系统的数据、数据源点和终点、数据流向和数据加工。其中，用箭头表示数据流向，用圆或者椭圆表示数据加工，杠表示数据，用方框来表经过对部分考生的以及对近年的总结分析，笔试部分经常考查的是数据库管理系阶段的特点、数据的物理独立性及逻辑独立性、数据管理与控制、三级模式及两级的考点 数据、数据库、数据库管理系数据是数据库中的基本对象，描述事物的符号记录。数据库是长期在计算机内、有组织的、可共享的大量数据的集合，它具有的结构形式并存放于的介质内，是多种应用数据的集成，并可被各个应用程序所共享。考点2表4-1各阶段特点的详细说明考点3据的物理结构（包括结构、存取方式等）改变时，如设备的更换、物理的更换、考点 数据库系统的结构体内模式处于最底层，它反映了数据在计算机物理结构中的实际形式，概念模式处于中小提示：内模式处于最底层，它反映了数据在计算机物理结构中的实际形式，概念模式处于中间层，考点 数据模型的基本概考点 E-R模考点 层次模考点 关系模考点 关系代设有关系R、S，R有域A1，A2，…，An，S有域B1，B2，…，Bm，并且 Bm（σAi1=B1^Ai2=B2^^Aij=,Bj考点10数据库设计概述兼顾信息需求。由于数据在系统中稳定性高，数据已成为系统的，因此面向数据的设计方

4.4作的是（考点1） 据库；重构数据库。所以，定义数据库内容，决定结构和存取策略及安全等是数据库 （考点 改变时，由数据库管理员对外模式/模式做相应改变，可以使外模式保持不变。应用程序是 A）具有封装机制 系统在这3级模式之间提供了两层：外模式/模式，模式/内模式。这两层保证 A）属 B）关C） D） ， A）数据定义功 B）数据功C）数据功 D）数据控制功（