计算机二VB公共基础知识

1/33一、基本概念： 点、记录，可以有若干个数据项(字段、域、属性)组成。❖数据结构(DataStructure)：指的是数据之间的相互关系，即数据的组织形式。其包括三个部分：之间的逻辑关系3、数据的运算(算法)：即对数据施加的操作❖数据的逻辑结构有两大类：1、线性结构：特征是：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点最多只有一个直接前趋和一个直接后继。2、非线性结构：特征是：一个结点可能有多个直接前趋和直接后继。❖数据的存储结构有以下基本存储方法：1、顺序存储方法：2/33该方法是将逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，一般通过数组来实现的。2、链接存储方法：该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。通过指针类型来实现的。3、索引存储方法：该方法通常是在存储结点信息的同时，还建立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是：关键字，地址。4、散列存储方法：该方法的基本思想是根据结点的关键字直接计算出该结点的存储地址，通过散列函数实现。例：除余法散列函数、相乘取整法散列函数❖算法的基本特征：2、确定性(Definiteness)：算法中的每一个步骤都必须有明确的定义，不允许二、线性表：3/33❖线性表的存储结构：。是连续的，也可以是不连续的，在存储每个结点值的同时，还存储指向其后继结点的地址，用这种方法存储的线性表称为链表。❖常见的运算有：❖顺序表和链表的比较：置指针域，存储密度小于12、基于时间的考虑：4/33总之，当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构；当线性表的长度变化较大，难以估计其存储规模时，以采用链表作为存储结构为好。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；对于频繁进行插入和删除的线性表，宜采用链表做存储结构。例：关于线性表的描述中，错误的是()A、线性表是线性结构B、线性表的顺序存储结构，必须占用一片连续的存储单元C、线性表是单链表D、线性表的链式存储结构，不必占用一片连续的存储单元用数组表示线性表的优点是()A、便于插入和删除操作B、便于随机存取C、可以动态地分配存储空间D、不需要占用一片连续的存储空间❖栈的基本运算有：❖栈的存储：5/33进行出栈操作，则不可能出现的出栈序列是()为队尾(Rear)。(类似于生活中的购物排队)。是一种先进先出的线性表，又❖队列的基本运算：❖队列的存储实现：存储五、串： 注：空串是任意串的子串，任意串是其自身的子串6/33❖串有串常量、串变量之分：。❖串的基本运算：六、树(非线性结构)：满足如下两个条件：Leaf结点❖同一个双亲的孩子称为兄弟结点(Sibling)❖结点的层数(Level)是从根起算,设根的层数为1,其余结点的层数等于其双亲7/33❖树中结点的最大层数称为树的高度(Height)或深度(Depth).❖二叉树的五种基本形态：lBinaryTreekk二叉树的性质：8/33性质性质4：具有n个结点的完全二叉树的深度为[]+1(取下整)或二叉树的遍历：9/33空操作。否则：；中序遍历：(又称为中根遍历)空操作。否则：点；后序遍历：(又称为后根遍历)空操作。否则：；例：已知一棵二叉树的中序遍历序列是：FDGBACHE，其后序遍历序列是：10/33❖所谓排序，就是指整理文件中的记录，使之按关键字递增(或递减)次序排❖冒泡排序(BubbleSorting)：相邻元素的排序码，若发现逆序则交换，使排序码较大的元素逐渐从前部移向后部或较小的元素逐渐从后部移向前部(从下标较大的单元移向下标较小的单元)。❖直接选择排序(SelectionSorting)：11/33❖直接插入排序(InsertionSorting)：❖快速排序(QuickSorting)：任取待排序序列中的某个元素作为基准(一般取第一个元素)，通过一趟排序，将待排元素分为左右两个子序列，左子序列列的排序码则大于基各种内部排序方法的比较时间复杂度时间复杂度平均时间空间复杂度排序方法直接插入冒泡快速堆最好时间最坏时间例：对一个具有n个元素的序列进行冒泡排序，在最坏情况下，要进行交换的次数是()对n个元素进行冒泡排序过程中，最好情况下的时间复杂性为()12/33对n个元素进行快速排序的过程中，平均情况下的时间复杂性为()八、查找(Searching)：关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的n13/332.1程序设计方法与风格程序设计是一门技术，需要相应理论、技术、方法和工具来支持。程序设计方法和技术的发展而言，主要经过了结构化程序设计和面向对象的程序设计阶段。养成良好的程序设计的设计风格，主要考虑下述的因素：1.源程序文档化源程序文档化应考虑如下几点： (1)符号名的命名：符号名的命名有一定含义，便于理解 (2)程序注释：正确的注释帮助读者理解程序 (3)视觉组织：程序层次清晰2.数据说明的方法数据说明应考虑如下几点： (1)数据说明的次序规范化 (2)说明语句中变量安排有序化。 (3)使用注释来说明复杂数据结构3.语句的结构程序应该简单易懂，语句构造应该简单直接。应该注意的是： (1)在一行内只写一条语句 (2)程序编写应优选考虑清晰性 (5)避免使用临时变量而使程序可读性下降 (6)避免不必要的转移14/33 (7)尽可能使用库函数 (8)避免使用复杂的条件语句 (9)尽量减少使用“否定”条件的条件语句 (10)数据结构要有利于程序的简化 (11)要模块化，使模块功能尽可能单一化 (12)利用信息隐藏，确保每一个模块的独立性 (13)从数据出发去构造程序 (14)不要修补不好的程序，要重新编写4.输入和输出下原则： (1)对所有的输入数据都要检验数据的合理性 (2)检查输入项的各种重要组合的合理性 (3)输入格式要简单。 (4)输入数据时，应允许使用自由格式 (5)应允许缺省值 (6)输入一批数据时，最好使用输入结束标志 (7)在交互式输入/输出方式进行输入时，要在屏幕上使用提示符明确提示输入要求，在数据输入过程中和输入结束时应在屏幕给出状态信息 格要求时，应保持输入格式与输出语句的2.2结构化程序设计15/332.2.1结构化程序设计的原则结构化程序设计方法主要原则包括：题，逐步细化。.模块化。4.限制使用goto语句2.2.2结构化程序的基本结构与特点结构化程序设计方法是程序设计的先进方法和。和采用结构化程序设计方法编写程序，可使程序结构良好、易读、易理解、易维护。结构化程序设计方法种基本结构就可实现。1.顺序结构顺序结构是顺序顺序执行结构，即是按照程序语句的自然顺序，一条一条语句2.选择结构选择结构又称分支结构，它包括简单选择和多分支选择，这种结构可以根据给定条件，判断执行哪一个分支中的语句。3.重复结构重复结构又称为循环结构。它根据给定的条件判断是否重复执行某一段相同的2.2.3结构化程序设计原则和方法的应用在结构化程序设计的具体实施中，要注意把握如下要素： (1)使用程序设计语言中的顺序、选择、循环等控制结构表示程序的控制逻辑16/33 (2)选用的控制结构只准许有一个入口和一个出口 (3)程序语句组成容易识别的程序专项，每块只有一个入口和一个出口 (4)复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现 (5)语言中所没有的控制结构，应该采用前后一致的方法来模拟 (6)严格控制GOTO语句使用。2.3面向对象的程序设计2.3.1关于面向对象方法面向对象(ObjectOriented)方法已经发展成为主流的软件开发方法。面向对象方法的形成起源于实现语言，首先对设计语言的研究，随之形成面向对象分面向对象方法的本质，就是主张从客观世界固有的事物出发来构造系统，提倡用人类在现实生活中常用的思维方法来认识、理解和描述客观事物，强调最终建立的系统能够映射问题域。也就是说，系统中的对象以及对象之间的关系能够如实反映问题域中固有事物及其关系。面向对象方法有如下优点：1.与人类习惯的思维方法一致与客观实体有直接的对应关系。对象之间通过传递消息互相联系，以模拟现实2.稳定性好功能需求变化时并不会引起软件结构的整体变化，往往仅需要作一些局部性的17/333.可重用性好软件重用是指在不同的软件开发过程中重复使用相同或相似软件元素(一般称为利用可重用的软件成分构造新的软件系统，一个对象类可以重复使用，对象类可以创建，也以在已有的类上修改，但不影响原有类。4.易于开发大型软件产品可以把一个大型产品看作一系列互相独立的小产品来处理，这样不公降低了5.可维护性好一般用传统的开发方法和面向过程的方法开发出来的软件很难维护，而面向 (1)稳定性较好 (2)易于修改 (3)易于理解 (4)易于测试和调试2.3.2面向对象方法的基本概念关于面向对象方法，对其概念有许多不同的看法，但都涵盖了对象及对象属1.对象(object)对象是面向对象方法中最基本的概念。对象用来表示客观世界中的任何实体。18/33面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行对象有如下特点： (1)标识惟一性 (2)分类性 (3)多态性 (4)封装性 (5)模块独立性好2.类(Class)和实例(Instance)对象归为类，类具有共同属性、共同方法的对象的集合。3.消息(Message)面向对象的世界是通过对象与对象彼此的相互合作来推动的，对象间的这种相互合作需要一个机制协助进行，这的机制称为“消息”。消息是一个实例与另一个实例之间传递的信息，它请求对象执行某一处理或回答某一要求的信息，它统一了数据流和控制流。一个消息由三部分组成： (1)接收消息的对象的名称 (2)消息标识符(也称消息名) (3)零个或多个参数比如在窗体上画一个圆，对象名MyForm,消息名Circle,参数(50,50)为圆心,2519/33e4.继承(Inheritance)接获得已有的性质和特征)建立新类的定义技术。5.多态性(Polymorphism)对象根据所接受的消息而做出动作，同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性三．软件工程基础一、基本概念： e❖软件危机的表现：20/33❖软件工程的目标：❖软件生存周期：是指一个软件从提出开发要求开始直到该软件报废(停止运❖软件生存周期模型：是描述软件开发过程中各种活动如何执行的模型。模型、变换模型和基瀑布模型是将软件生存周期各个活动规定为依线性顺序连接的若干阶段的模型。主要包括问题定义及可行性分析、项目开发计划、需求分析、概要设计、详细设计、编码、测试和维护几个阶段。A、程序就是软件B、软件开发不受计算机系统的限制C二、软件可行性研究与项目开发计划：❖软件可行性研究的目的是用最小的代价在尽可能短的时间内确定该软件项目是否能够开发，是否值得去开发。21/33❖可行性研究的任务：C、社会可行性(法律可行性)❖可行性研究的具体步骤：三、软件需求分析： 式功能规约(需求规格说明)的过程。❖需求分析的基本任务：22/33❖需求分析的方法：sSA方法利用图形等半形式化的描述方式表达需求，主要描述工具：ADFDSA系统逻辑模型的一种工具，以图形C言、判定表、判定树2、IDEF方法(是ICAMDefinition的缩写)：四、软件概要设计：❖软件概要设计的基本任务：23/332、数据结构及数据库设计(概要设计、逻辑设计、物理设计)：4、评审：❖软件设计的方法：五、软件详细设计：❖软件详细设计的基本任务：24/33计、评审：❖详细设计常用三种工具：、七、软件测试： ❖软件测试的目的：❖软件测试的原则：25/33❖软件测试方法：误要求。常用的技术是等价类划分法、边界值分析法、错误推测法、因果图法、综合策略法主要测试程序的内部结构和处理过程。常用的技术是语句覆盖、条件覆盖、路径覆盖、判定覆盖等❖软件测试的实施：1、单元测试：单元测试是对软件设计的最小单位——模块(程序单元)进行正确性检验测试，主要针对模块的以下五个基本特征进行测试：A、模块接口26/33C径：集成测试：主要方法有两种：集成测试，每加入一个新模块进行一次集成测试，重复此过程直至程序组装完3、确认测试：确认测试又称有效性测试，它的任务是检查软件的功能与性能是否与需求规格说明书中确定的指标相符合，因而需求规格说明是确认测试的基础。4、系统测试：环境下对计算机系统进行一系列的集成测试和确认测试。❖程序调试：27/33例：软件测试的目的是()误CD件系统中存在错误28/3329/33A、结构合理性B、软件外部功能C、程序正确性D、程序内部逻辑八、软件维护： 软件投入使用后进行的阶段，是软件生存周期中时间最长的一个阶段，所花费的精力和费用也是最多的一个阶段。主要是因为：隐含的错误要修改；新增的功能要加入进去；环境的变化对程序进行变动等。❖软件维护的内容有四类：1、校正性维护：为了识别和纠正错误，修改软件性能上的缺陷，其占整个维护工作的21%2、适应性维护：为了使应用软件适应环境(硬件、系统软件、数据)的变化而修改软件的过程维护工作的25%3、完善性维护：4、预防性维护：其30/33占整个维护工作的4%例：软件维护是指()A、维护软件正常运行B、软件的配置更新件生命周期中所花费用最多的阶段是()A、详细设计B、软件编码C、软件测试D、软件维护❖数据处理：是指将数据转换成信息的过程护提供操作手段下阶段：31/33DBMS和维护进行管理和配置的软件系统。是数