VF程序设计经典题型.doc

第一章 数据结构与算法11算法1算法定义：是指解题方案的准确而完整的描述。2基本特征：可行性、确定性、有穷性、拥有足够的情报。3基本要素：算法中对数据的运算和操作；算法的控制结构（描述算法的工具有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可用顺序、选择、循环三种基本控制结构组合而成。4设计基本方法：列举法、归纳法、递推、递归、减半递推技术5算法的复杂度包括：时间复杂度（执行算法所需要的额计算工作量）、空间复杂度（执行算法所需要的内存空间）12数据结构的基本概念1数据结构研究和讨论问题包括：数据的逻辑结构 数据的存储结构 运算 讨论目的：为了提高数据处理的效率。（包括提高处理速度，节省存储空间）2数据处理定义：指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等，也包括对数据元素进行分析。*对分查找只适用于有序表。一般情况下，在具有相同特征的数据元素中，各个数据元素之间存在某种关系，反映了该集合中的数据元素所固有的一种结构，此关系叫前后件关系（或直接前驱与直接后继关系）数据结构应包括：表示数据元素的信息表示各元素之间的前后间关系是指他们的逻辑关系，而与存储位置无关数据的逻辑结构定义：指反映数据元素之间逻辑关系的数据结构数据的逻辑结构要素：数据元素的集合，记为是上的关系，它反映了中各数据元素之间的前后件关系，记为即数据结构可表示为（，）数据的存储结构定义：数据的逻辑结构在计算机存储空间中的存放形式，也称数据的物理结构。*在数据结构中，没有前件的结点称为根结点，没有后件的结点称为终端节点（也叫叶子节点）。除了根和终端外的其他结点一般称为内部结点13线性表及其顺序存储结构1.线性表的规律：是由n个元素a1 a2 an 组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表，或表示为（a1 a2 ai an）2.非空线性表的结构特征：有且只有一个根结点a1 。它无前件 有且只有一个终端结点an，它无后件 除根结点和终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表结点的个数n称为线性表的长度。当n=0时，称为空表。3.线性表的顺序结构运算：线性表的插入、删除、查找、排序、分解、合并、复制、逆转14栈和队列1.栈的含义：栈实际上也是线性表，只不过是一种特殊的线性表。插入与删除运算都只在线性表的一端进行。即在这种线性表的结构中，一端是封闭的（不允许），另一端是开口的（允许）。允许插入与删除的一端叫栈顶，不允许的叫栈底。栈是按照“先进后出”或“后进先出”的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。在栈的顺序存储空间S(1:m)中，S(bottom)通常为栈底元素，S(top)为栈顶元素。Top=0表示栈空；top=m表示栈满。2.栈的基本运算：入栈、退栈、读栈顶元素。3.队列的含义：指允许在一端插入、而在另一端进行删除的线性表。又称为“先进先出”或“后进后出”表，它体现了先来先服务的原则。4.循环队列的定义：就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的循环空间，供队列循环使用。在循环队列中，队列空的条件为s=0；队列满的条件为s=1且pront=rear 。在队尾加入一个新元素叫入队运算；在队列派头位置退出一个元素并赋给指定变量叫退队运算。15线性链表1.线性链表的基本概念：为了在顺序存储的线性表中插入或删除一个元素，需要移动线性表中约一半的元素；在最坏的情况下，则需要移动线性表中的所有元素。因此，对于大的线性表，特别是元素的插入或删除很频繁的情况下，采用顺序存储结构是很不方便的，插入与删除运算的效率很低。在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点（即前件或后件）。线性表的链式存储结构称为线性链表。在线性链表中，各数据元素之间的前后件关系是由各结点的指针域来指示的，指向线性表中的第一个结点的指针HEAD称为头指针，当HEAD=NULL(或0)时称为空表。上面讨论的线性链表又称为线性单链表。为了弥补线性单链表的缺点，在某些应用中，对线性链表的每个结点设置两个指针，一个称为左指针，另一个是右指针。这样的线性链表称为双向链表。2.线性链表的基本运算：插入删除合并分解逆转复制排序查找16树与二叉树1.树结构的基本术语：在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。一个结点所拥有的后件个数称为该结点的度，树的最大层次称为树的深度。2.二叉树的特点：非空二叉树只有一个根结点 每一个结点最多有两棵子树。（即每一个结点的度最大为2）3.二叉树的基本性质：在二叉树的第k层上，最多有2k-1个结点。深度为m（二叉树共有m层）的二叉树最多有2m-1个结点 在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个 具有n个结点的二叉树，其深度至少为 log2 n+1,其中log2 n表示取log2 n的整数部分。4.二叉树的遍历的定义：指不重复的访问二叉树中的所有结点。5.二叉树的遍历的分类：前序、中序、后序17查找技术1.查找的定义：是指在一个给定的数据结构中查找某个指定的元素。2.查找的分类：顺序查找、二分法查找（当有序线性表为顺序存储时才能采用二分查找）18排序技术1.排序的分类：一交换类排序法：冒泡排序法快速排序法 二插入类排序法：简单插入排序法（将无序序列中的个元素依次插入到已经有序的线性表中）希尔排序法（将无序序列分割成若干插入） 三选择类排序法：简单选择排序法（选出最小元素）堆排序法（堆顶元素必为最大项，最坏情况下，堆排序需要比较的次数为0）第二章 程序设计基础21程序设计方法与风格1.经历阶段：结构化程序设计、面向对象的程序设计2.当今主导的设计风格：强调简单和清晰“清晰第一，效率第二”3.程序设计要考虑的因素：（具体见P49）源程序文档化数据说明的方法语句结构输入和输出22结构化程序设计1.结构化程序设计原则：自顶向下逐步求精模块化限制使用goto语句2.结构化程序的基本结构与特点：结构：顺序、选择、重复 特点：程序易于理解、使用和维护提高了编程工作的效率，降低了软件开发的成本3.实施结构化程序设计要把握的要素：使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑 选择的控制结构只准有一个入口和一个出口 程序语句组成容易识别的快，每块只有一个入口和一个出口 复杂结构应该用嵌套的基本控制结构 语言中所没有的控制结构，应采用前后一致的方法来模拟 严格控制GOTO语句的使用23面向对象的程序设计1.面向对象方法的优点：与人类习惯的思维方法一致 稳定性好 可重用性好 易于开发大型软件产品 可维护性好2.对象的基本特点：标识唯一性、分类型、多态性、封装性、模块的独立性好3.消息的组成：接收消息的对象的名称；消息标识符（也称消息名）；零个或多个参数4.多态性的定义：对象根据所接受的消息而做出动作，同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性。第三章 软件工程基础31软件工程基本概念1.关于软件的定义：计算机软件：是计算机系统中与硬件相互依存的另一部分，是包括程序、数据及相关文档的完整集合。程序：是软件开发人员根据用户需求开发的、用程序设计语言描述的、适合计算机执行的指令（语句）序列。数据：是使程序能正常操纵信息的数据结构。文档：是与程序开发、维护和使用有关的图文资料。2.计算机软件的国际标准定义：与计算机系统的操作有关的计算机程序、规程、规则，以及可能有的文件、文档和数据。3.软件的组成：机器可执行的程序和数据 机器不可执行的，与软件开发、运行、维护、使用等有关的文档4.软件的特点：是一种逻辑实体，是物理实体，具有抽象性 没有明显的制作过程 不存在磨损、老化问题 对计算机系统有依赖性，手计算机系统的限制，导致了软件移植的问题 复杂性高，成本昂贵 开发涉及诸多社会因素5.软件的分类：应用软件、系统软件、支撑软件（工具软件）6.软件危机的定义：泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题。7.软件危机的表现：软件需求的增长得不到满足 软件开发成本和进度无法控制 软件质量难以保证 软件不可维护或维护成都非常低 软件的成本不断提高 软件开发生产率的提高赶不上硬件发展和应用需求的增长 总之，可以归结为成本、质量、生产率等问题。8.软件工程的三要素：方法、工具和过程9.软件工程的核心思想：把软件产品看作是一个工程产品来处理。10.软件生命周期的主要活动阶段：可行性研究与计划制定 需求分析 软件设计 软件实现 软件测试 运行和维护11.软件工程的目标：付出较低的开发成本；达到要求的软件功能；取得较好的软件性能；开发的软件易于移植；需要较低的维护费用；能按时完成开发，及时交付使用。12.软件工程理论和技术性研究的内容：软件开发技术和软件工程管理13.软件工程的原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性、可验证性。32结构化分析方法1.核心和基础：结构化程序设计理论2.需求分析的四个方面：需求获取、需求分析、编写需求规格说明书、需求评审3.需求的分析方法：结构化分析方法、面向对象的分析方法4.结构化分析的定义：使用数据流图（DFD）、数据字典(DD)、结构化英语、判定表和判定树等工具，来建立一种新的、称为结构化规格说明的目标文档。5.结构化分析方法的实质：着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，一数据流图的数据字典为主要工具，建立系统的逻辑模型。33结构化设计方法1.软件设计的基本目标：用比较抽象概括的方式确定目标系统如何完成预定的任务，即软件设计是确定系统的物理模型。2.软件设计的重要性：软件开发阶段是关键环节 软件设计是最重要的步骤，是唯一途径 软件设计做出的决策，最终影响软件实现的成败 设计是软件工程和软件维护的基础3.软件设计的基本原理：抽象、模块化、信息隐蔽、模块独立性（是评价设计好坏的重要度量标准，包括内聚性和耦合性4.内聚性：定义：是一个模块内部各个元素之间彼此结合的紧密程度的度量，是从功能角度来度量联系。种类（从弱到强排列）：偶然内聚、逻辑内聚、时间内聚、过程内聚、通信内聚、顺序内聚、功能内聚5.耦合性：定义：是模块之间互相连接紧密程度的度量。种类（由高到低）：内容耦合、公共耦合、外部耦合、控制耦合、标记耦合、数据耦合、非直接耦合6.两者关系：是模块独立性的两个定性标准，是相互关联的，内聚性越强，耦合性越弱。一般优秀的软件设计，应做到高内聚，低耦合，以提高模块的独立性。7.概要设计的基本任务：设计软件系统结构 数据结构及数据库设计 编写概要设计文档 概要设计文档评审 【注】程序结构图（常用的软件结构设计工具）8.数据流的类型：变换型 事务型 9.设计的准则：提高模块独立性 模块规模适中 深度、宽度、扇出和扇入适当 使模块的作用域在该模块的控制域内 应减少模块的接口和界面的复杂性 设计成单入口、单出口的模块 设计功能可预测的模块 10.详细设计中，常见的过程设计工具有：图形工具：程序流程图，N-S，PAD，HIPO 表格工具：判定表 语言工具：PDL（伪码）11.程序流程图的基本图符：或：控制流 矩形：加工步骤 菱形：逻辑条件12.什么是N-S图？ 为了避免流程图的随意性和灵活性而制造（N和S代表两个外国人名），用方框图来代替传统的程序流程图。13.什么是PAD图？ 是问题分析图的英文缩写，主要用于描绘软件详细设计14.PAD图的特征：结构清晰，结构化程度高 易于阅读 最左端的纵线是程序主干线，对应程序的第一层结构；每增加一层，图就向右扩展一条纵线，故程序的纵线数等于程序层次数。程序从最左主干线上端结点开始，自上而下、自左向右依次执行，程序终止于最左主干线。15.PDL（过程设计语言，也称结构化的英语和伪码）的常用词汇：条件：if then else endif 循环：do while enddo 重复：repeat until endrepeat 分支：case_of when select endcase 34软件测试1.软件测试的准则：所有测试都应追溯到需求 严格执行测试计划，排除测试的随意性 充分注意测试中的群集现象 程序员应避免检查自己的程序 穷举测试不可能 妥善保存测试计划、测试用例、出错统计和最终分析报告，为维护提供方便。2.软件测试技术与方法：一.静态测试与动态测试（静态测试包括代码检查、静态结构分析、代码质量度量等。可由人工或借助软件工具自动进行，但不实际运行软件，主要是靠人工进行 / 动态测试是基于计算机的测试，是为了发现错误而执行程序的过程。设计高效、合理的测试用例是动态测试的关键。二.白盒测试方法和黑盒测试方法白盒：也称结构测试或逻辑驱动测试。根据内部过程，确定内部规格要求。所以，白盒测试是在程序 内部 进行，主要用于完成软件 内部 操作的验证。其测试的基本原则是都保证各方面至少执行一次。白盒法是穷举路径测试。白盒测试的主要方法有逻辑覆盖测试（包括语句覆盖、路径覆盖、判定覆盖、条件覆盖、判断-条件覆盖）、基本路径测试等。黑盒：也称功能测试或数据驱动测试，是对功能是否满足需求进行测试和验证。完全不考虑内部，只根据说明，检查是否符合功能说明。所以黑盒测试是在软件接口处进行，完成功能验证。其功能是诊断功能不对或遗漏、界面错误、数据结构或外部数据库访问错误、性能错误、初始化和终止条件错误。黑盒测试的主要方法有等价类比划分法（分为有效和无效）、边界值分析法、错误推测法、因果图等。主要用于软件确认测试。3.软件测试过程的步骤：单元测试、集成测试（有两种方式非增量方式组装和增量方式组装）、验收测试（也称确认测试，任务是验证软件的功能和性能及其他特性是否满足了需求规格说明中确定的各种需求，以及软件配置是否完全、正确）和系统测试（实施包括功能测试、性能测试、操作测试、配置测试、外部接口测试、安全性测试等）。、35程序的调试1.程序调试与软件测试的不同：软件测试是尽可能多地发现软件中的错误。先要发现错误，然后借助于一定的调试工具去找出错误的具体位置。程序调试的任务是诊断和改正程序中的错误。软件测试贯穿整个软件生命期，调试主要是在开发阶段。2.程序调试的组成：根据错误的迹象确定程序中错误的确切性质、原因和位置。对程序进行修改，排除这个错误。3.程序调试的基本步骤：错误定位；修改设计和代码，以排除错误；进行回归测试，防止引进新的错误4.程序调试的原则：一有错，许别也有错 只修改了表现，没改本质 可能会引入新的错误，因此必须进行回归测试 暂时回到程序设计阶段 修改源代码，不要改变目标代码5.软件调试的方法：强行排错法、回溯法、原因排除法第四章 数据库设计基础41数据库系统的基本概念1.什么是数据？ 实际上是描述事物的符号记录。数据分为两部分，即临时性数据和持久性数据。在数据库系统及数据库应用系统中，数据占主体地位，程序退居附属地位。2.什么是数据库？ 简称DB，是数据的集合，它具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序所共享。具有“集成”“共享”的特点。3.什么是数据库管理系统？ 简称DBMS，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等。数据库管理系统是数据库系统的核心，具有如下的功能：数据模式定义 数据存储的物理构建 数据操纵 数据完整性、安全性定义与检查（数据完整性与安全性的维护是数据库管理系统的基本功能） 数据库的并发控制与故障恢复 数据的服务 数据库管理系统提供的数据语言有：数据定义语言、操纵语言、控制语言。有两种结构形式：交互式命令语言和宿主型语言。4.什么是数据库管理员？简称DBA，其主要工作是：数据库设计、数据库维护以及改善系统功能，提高系统效率。5.什么是数据库系统？简称DBS，由数据库、数据库管理系统、数据库管理员、硬件平台、软件平台五部分组成。其中，硬件平台包括计算机、网络操作系统、数据库系统开发工具、接口软件。6.数据库系统的发展阶段：文件系统阶段、层次数据库与网状数据库系统阶段、关系数据库系统阶段7.数据库系统的基本特点：数据的集成性 数据的高共享性与低冗余性 数据的独立性（物理独立&逻辑独立） 数据统一管理与控制（包含三方面数据的完整性检查、数据的安全性保护、并发控制）8.数据库系统的内部结构体系：三级模式（包括概念模式、外模式和内模式）和二级映射（包括概念模式到内模式的映射和外模式到概念模式的映射）42数据模型1.数据模型的概念：是根据特征的抽象，它从抽象层次上描述了系统的静态特征、动态行为和约束条件，为数据库系统的信息表示与操作提供了一个抽象的框架。2.数据模型所描述的内容：数据结构、数据操作、数据约束3.数据模型的分类：（按不同的应用层次分）概念数据模型、逻辑数据模型、物理数据模型。4.数据模型的典型：E-R模型、层次模型、网状模型、关系模型。5.关于E-R模型：基本概念：实体、属性、联系（分为两个实体间联系，多个实体间联系，一个实体集内部一对一以及一对多或多对一得联系）实体、属性、联系三者的联接关系：（1）（实体集）联系与属性的关系：实体有型与值之别，一个实体的所有属性构成了这个实体的型；相同的实体构成了实体集（联系）。（2）实体（集）与联系6.关于层次模型：是本上是树型结构，任一树结构有一下特性：每棵树有且只有一个无双亲结点，称为根；树中，除根外所有结点有且只有一个双亲。7.关于网状模型：注意DBTG（是一个标准）8.关于关系模型：采用二维表表示，简称表。二维表由表框架 及表的元组组成。二维表满足以下七个特征（1）元组个数有限性（2）元组唯一性（3）元组次序无关性（4）元组分量的原子性（5）属性名唯一性（6）属性的次序无关性（7）分量值域的同一性。 表中一定要有键，在关系元组的分量中允许出现空值。关系操纵分为查询、增加、删除及修改四种操作。关系模型的基本操作有：（1）关系的属性指定（2）关系的元组选择（3）两个关系的合并（4）一个或多个关系的查询（5）关系中元组的插入（6）关系中元组的删除 关系中的数据约束包括实体完整性约束、参照完整性约束、用户定义的完整性约束。43关系代数1.关系模型的基本操作：插入、删除、修改和查询。可进一步分解成六种基本操作：关系的属性指定 关系的元组选择 两个关系的合并 关系的查询 关系元组的插入 关系元组的删除2.关系模型的基本运算：插入、删除、修改、查询（包括 投影选择笛卡尔积3.关系代数中的扩充运算：交运算、除运算、连接与自然连接运算44数据库设计与管理1.数据库应用的核心：数据库设计 在数据库应用系统中的一个核心问题就是设计一个能满足用户需求，性能良好的数据库，这就是数据库设计。2.数据库设计的基本任务：根据用户对象的信息需求、处理需求和数据库的支持环境设计出数据模式。3.数据库设计的两种方法：是以信息需求为主，兼顾处理需求，称为面向数据的方法。是以处理需求为主，兼顾信息需求，称为面向过程的方法。 面向数据的设计方法是主流方法。 数据库设计目前一般采用生命周期法。4.数据库设计的需求分析：需求收集和分析是数据库设计的第一阶段，这一阶段收集到的基础数据和一组数据流图是下一步设计概念结构的基础。需求分析阶段的任务是通过详细调查现实世界要处理的对象，充分了解原系统的工作概况，明确用户各种需求，然后在此基础上确定新系统的功能。新系统必须充分考虑今后可能的扩充和改变，不能仅按当前应用需求来设计数据库。5.数据库为节省空间，我将答案都放在了Program和End中间了，大家可以学学看哦！（以下各题答案请在Program和End中间填写）1.用循环程序求出115之间能被3整除的整数的阶乘和存入变量OUT中，要求用For循环语句实现。SET TALK OFFSET LOGERRORS ONOUT=0*Program*T=1FOR N=1 TO 15T=T*NIF N%3=0OUT=OUT+TENDIFENDFOR?OUT* End *SET TALK ONDO YZJ17 WITH OUTRETURN2. 编程判断一个整数w的各位数字平方之和能否被5整除, 可以被5整除则返回1,否则返回0。将结果存入变量OUT中，要求用Do While语句实现。SET TALK ONSET LOGERRORS ON? 输入一个整数：w=39 OUT=-1w=39*Program*S=0DO WHILE W0S=S+(W%10)* (W%10)W=INT(W/10)ENDDOIF S%5=0Out=1ELSEOUT=0ENDIF?OUT* End *DO YZJ WITH OUTSET LOGERRORS OFFSET TALK OFF3.编程当n=10时，计算如下表达式a10的值。a1=1,a2=1/(1+a1),a3=1/(1+a2),.an=1/(1+a(n-1)。将结果存入变量OUT中，要求用For循环语句实现。SET TALK ONSET LOGERRORS ONOUT=-1*Program*a=1for i=1 to 9a=1.0/(1+a)endforout=a?out* End *DO YZJ WITH OUTSET LOGERRORS OFFSET TALK OFF4. 从键盘输入一个整数，输出所有