二级VB公共基础知识总结

计算机VB二级公共基础知识总结 1 数据结构的基础知识

数据结构的定义:指数据对象及其相关关系和构造方法。

结构是指结点之间的关系,数据结构就是在结点的优先集合和关系的有限集合。 数据结构的逻辑结构是指结点和结点间的相互关系。

数据结构在计算机的存储内容,一般包括结点的值和结点间的关系,数据结构的存储形式就是数据的存储结构。

数据结构按逻辑关系的不同分为线形结构和非线性结构两大类,非线性又分为树形结构和图结构,树形结构又分为树结构和二叉树结构。

2 线性表

线性表是最简单、最常用的一种数据结构,它是由相同类型的结点组成的有限序列。线性表最重要的性质是线性表中结点的相对位置时确定的。

线性表常用的运算有4种:查找运算、插入运算、删除运算和其他运算。 线性表的存储方式主要有:

1) 顺序存储:能直接访问线性表中的任意一个结点。

2) 链接存储:用单链表存储线性表。

3 栈和队列的含义

栈是只允许在同一端进行插入和删除运算的线性表。

队列是只允许在一端进行插入运算,另一端进行删除运算的线性表。 4 数组和字符串的特点

数组是最常用的数据结构之一,一般用于描述顺序存储的线性表。数组有固定个数的元素组成,全部元素的类型相同,元素按照顺序存储。每个元素对应一个下标,数组元素按数组名和元素的下标引用,引用数组元素的下标个数称为数组的维数。最常用的事二维数组。 5 树的基本概念、存储结构和遍历

树是一种多分支、多层次的数据结构,有一组结点组成。树是由一个结点或多个结点组成的有限集T,满足以下两个条件:

1) 有一个特定的结点,称为根结点

2) 其余的结点分成m个互不相交的有限集T0等,每个集合都是根结点的子树。 树的定义是递归的,即一棵树是由子树组成,子树由更小的子树构成。

树的存储结构:树是非线性的结构,有多种实用的存储结构,最常用的是标准存储形式和带逆存储形式。

树的遍历方法有4种:树的前序遍历、树的后序遍历、树的层次遍历、访问树中所有的叶子特点。

6 二叉树的基本概念及遍历

二叉树是一个有限的结点集合,该集合或者为空,或者有一个结点及其两棵树不相交的左右二叉子树组成。

二叉树的遍历:前序遍历,中序遍历、后序遍历。

7二叉查找树

查找树便于链接存储,还能实现快速查找。或者为空,或者满足以下3个条件:A 该树根结点的左子树非空,其左子树所有结点的键值都小于该树根结点的键值。B该树根结点的右子树非空 ,其右子树所有结点的键值都大于该树根结点的键值C该树的根结点的左子树和右子树均为查找树。

8 关于排序与查找,散列表

对于有N个结点的线性表,将结点红某些数据项的值按递增或递减的次序,重新排列线性表结点的过程,称为排序。

查找就是在案某种数据结构形式存储的数据集合中,找出满足指定条件的结点。

散列表又称杂凑表示一种非常实用的查找技术。由于查找码与结点在数据结构中的位置不存在确定关系,查找只能通过对查找码与结点的关键码的反复比较来实现。

第二章 程序设计基础知识

1程序设计的方法与风格

程序设计的方法主要是结构化程序的设计,集体有面向数据流的方法和面向数据结构的方法。数据结构既影响程序处理的结构又影响程序处理的过程。

程序设计风格主要是指面向过程的程序设计和面向对象的程序设计。面向过程的程序设计主要是指根据事物本身的逻辑过程进行编程的一种方法,而面向对象的主要是强调程序的功能模块化,同时引入了继承、多态的概念,使程序易于编写和维护,最适合规模较大的软件。 2 结构化的程序设计

结构化的程序(SP)设计采取自顶向下逐步求精的设计方法和单入口但出口的控制结构。其设计方法符合抽象和分解的原则。其控制结构使程序的静态结构和动态结构执行过程一致。

3面向对象的设计方法及相关概念

面向对象方法是一种支持模块化设计和软件重用的编程方法。它把程序设计的主要活动集中在建立对象和对象之间的联系上,其基本思想是封装性和可扩展性。以软件设计的对象为基础。

对象:在计算机系统中,指一组属性以及这组属性上的专用操作的封装体。一个对象通常可由对象名,属性和操作3个部分组成。

封装:是一种信息隐蔽技术,用户只能看见对象封装界面上的信息,对象的内部实现对用户是隐蔽的。其目的是使对象的使用者和生产者分离,使对象的定义和实现分开。 属性:对象的特性,是对象外观及行为的特征。

方法:对象所具有的功能。每一个对象的属性,只能通过特定的操作来存取或者修改,这种特定的操作就是方法。

继承:在某个类的层次关联中,不同的类共享属性和操作的一种机制。一个子类可以只有唯一的一个父亲,被称为单一继承,一个子类也可以由多个父亲,从多个父亲中继承特性,叫多重继承。

多态性:指同一个操作作用于不同对象可以有不同的解释,产生不同的执行结果。

动态绑定:在运行过程中,当一个对象发送信息请求服务时,要根据接收对象的具体情况将请求的操作与实现方法连接。

第三章 软件工程基础知识

1软件生存周期各阶段的任务

软件生存周期指软件定义、软件开发和软件维护等阶段组成的全过程。

A定义阶段;确定系统的逻辑模型,产生有需求规格说明书

B开发阶段:软件设计、编码和测试3部分。软件设计分为概要设计和详细设计。编码是用某种程序语言为每个模块编写程序,产生的文档有程序清单。软件测试的任务是发现软件中的错误加以纠正。

C维护阶段:适应外界环境的变化,或扩充其功能,改善其质量,产生的文档有维护计划和维护报告。

2 软件设计的原则

1)抽象原则;抽象的最低层次就是实现该软件的源程序代码。过程抽象和数据抽象是常有的

两种抽象手段。

2)模块化原则:

3)信息隐蔽原则:对提高软件的可修改性、可测试性和可移植性有重要作用。

4)模块独立的原则

3软件测试

软件测试的目的是尽可能多的发现软件产品中的错误和缺陷。

白盒测试主要检查程序中的逻辑通路

黑盒测试主要检查程序的功能是否符合规格说明书的要求。大多的软件生产者使用Alpha测试和Beta测试,后者的开发者通常不在场。

4软件开发工具和环境

软件工具是指用来辅助软件开发、运行、维护、管理和支持等过程中活动的软件。大多包括检测机制。

软件开发环境则把一组相关的工具集成在环境中,提供数据集成、控制集成和界面集成等机制。

第四章 数据库的基础知识

1数据库

数据库:是存储在一起的相关数据的集合,能为各种用户共享,具有最下冗余度,数据间的联系密切,由较高的程序与数据独立性。

数据库管理系统:指位于用户和操作系统之间的一层数据管理软件,为用户或应用程序提供访问数据库的方法,包括数据库的建立、查询、更新及各种数据控制。它是DBS的核心部分。

数据库系统:是实现有组织地,动态的存储大量关联数据,方便多用户访问的计算机软、硬资源组成的系统,即采用了数据库技术的计算机系统。

2 数据模型

常有的数据模型有两种:一种是独立于任何计算机系统的模型,完全不涉及信息在计算机系统中的表示,称为“概念数据模型”。最著名的模型时“实体联系E-R模型”。另一种数据模型直接面向数据库的逻辑数据结构,被称为“基本数据模型”。

基本数据模型主要有层次、网状、关系三种模型。层次模型时用树型结构来表示实体类型及实体间联系的数据模型。网状模型用丛结构表示,关系模型用表格结构表示实体集,用键表示实体间的联系。网状模型采用有向图,层次模型采用树,关系模型采用二维表。在搜索数据时,层次模型采用单向搜索法,网状模型采用可从任一结点开始且沿任何路径搜索,关系模型则是通过对关系进行运算实现的。

3 关系代数

关系数据库的数据与更新操作必须遵循实体完整性规则、饮用完整性原则、用户定义完整性原则。

关系代数是以集合代数为基础发展起来的,以关系为运算对象的一组高级运算的集合。 关系代数的5种基本操作;并、差、笛卡儿积、投影和选择。

关系代数的4种组合操作;交、联接、自然联接和除法。

4在数据库中,用概念模式描述全部数据的整体逻辑结构,负责物理结构与逻辑结构的定义和修改的人员是数据库管理员。数据库管理系统提供的数据定义语言的功能是描述数据库的结构,为用户建立数据库提供手段。在人事管理系统中,规定工程师的基本工资和奖金不能超过1500元,这样的数据完整性约束条件称之为用户定义完整性。在关系数据库的逻辑设计阶段,需将E-R模型转换为关系数据模型。

 

第二篇:二级C公共基础知识总结

基本要求

1.掌握算法的基本概念。

2.掌握基本数据结构及其操作。

3.掌握基本排序和查找算法。

4.掌握逐步求精的结构化程序设计方法。

5.掌握软件工程的基本方法,具有初步应用相关技术进行软件开发的能力。

6.掌握数据库的基本知识,了解关系数据库的设计。

考试内容

一、数据结构与算法

1 算法

算法:是指解题方案的准确而完整的描述。

算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。

算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。特征包括:

(1)可行性;

(2)确定性,算法中每一步骤都必须有明确定义,不充许有模棱两可的解释,不允许有多义性;

(3)有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止,包括合理的执行时间的含义;

(4)拥有足够的情报。

算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构。

指令系统:一个计算机系统能执行的所有指令的集合。

基本运算和操作包括:算术运算、逻辑运算、关系运算、数据传输。

算法的控制结构:顺序结构、选择结构、循环结构。

算法基本设计方法:列举法、归纳法、递推、递归、减斗递推技术、回溯法。

算法复杂度:算法时间复杂度和算法空间复杂度。

算法时间复杂度是指执行算法所需要的计算工作量。

算法空间复杂度是指执行这个算法所需要的内存空间。

2 数据结构的基本基本概念

数据结构研究的三个方面:

(1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构;

(2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;

(3)对各种数据结构进行的运算。

数据结构是指相互有关联的数据元素的集合。

数据的逻辑结构包含:

(1)表示数据元素的信息;

(2)表示各数据元素之间的前后件关系。

数据的存储结构有顺序、链接、索引等。

线性结构条件:

(1)有且只有一个根结点;

(2)每一个结点最多有一个前件,也最多有一个后件。

非线性结构:不满足线性结构条件的数据结构。

3 线性表及其顺序存储结构

线性表由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。

在复杂线性表中,由若干项数据元素组成的数据元素称为记录,而由多个记录构成的线性表又称为文件。

非空线性表的结构特征:

(1)且只有一个根结点a1,它无前件;

(2)有且只有一个终端结点an,它无后件;

(3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。结点个数n称为线性表的长度,当n=0时,称为空表。

线性表的顺序存储结构具有以下两个基本特点:

(1)线性表中所有元素的所占的存储空间是连续的;

(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

ai的存储地址为:adr(ai)=adr(a1)+(i-1)k,,adr(a1)为第一个元素的地址,k代表每个元素占的字节数。

顺序表的运算:插入、删除。 (详见14--16页)

4 栈和队列

栈是限定在一端进行插入与删除的线性表,允许插入与删除的一端称为栈顶,不允许插入与删除的另一端称为栈底。

栈按照“先进后出”(filo)或“后进先出”(lifo)组织数据,栈具有记忆作用。用top表示栈顶位置,用bottom表示栈底。

栈的基本运算:(1)插入元素称为入栈运算;(2)删除元素称为退栈运算;(3)读栈顶元素是将栈顶元素赋给一个指定的变量,此时指针无变化。

队列是指允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。rear指针指向队尾,front指针指向队头。

队列是“先进行出”(fifo)或“后进后出”(lilo)的线性表。

队列运算包括(1)入队运算:从队尾插入一个元素;(2)退队运算:从队头删除一个元素。 循环队列:s=0表示队列空,s=1且front=rear表示队列满

5 线性链表

数据结构中的每一个结点对应于一个存储单元,这种存储单元称为存储结点,简称结点。 结点由两部分组成:(1)用于存储数据元素值,称为数据域;(2)用于存放指针,称为指针域,用于指向前一个或后一个结点。

在链式存储结构中,存储数据结构的存储空间可以不连续,各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的。 链式存储方式即可用于表示线性结构,也可用于表示非线性结构。

线性链表,head称为头指针,head=null(或0)称为空表,如果是两指针:左指针(llink)指向前件结点,右指针(rlink)指向后件结点。

线性链表的基本运算:查找、插入、删除。

6 树与二叉树

树是一种简单的非线性结构,所有元素之间具有明显的层次特性。

在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点,简称树的根。每一个结点可以有多个后件,称为该结点的子结点。没有后件的结点称为叶子结点。

在树结构中,一个结点所拥有的后件的个数称为该结点的度,所有结点中最大的度称为树的度。树的最大层次称为树的深度。

二叉树的特点:(1)非空二叉树只有一个根结点;(2)每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。

二叉树的基本性质:

(1)在二叉树的第k层上,最多有2k-1(k≥1)个结点;

(2)深度为m的二叉树最多有2m-1个结点;

(3)度为0的结点(即叶子结点)总是比度为2的结点多一个;

(4)具有n个结点的二叉树,其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分;

(5)具有n个结点的完全二叉树的深度为[log2n]+1;

(6)设完全二叉树共有n个结点。如果从根结点开始,按层序(每一层从左到右)用自然数1,2,?.n给结点进行编号(k=1,2?.n),有以下结论:

①若k=1,则该结点为根结点,它没有父结点;若k>1,则该结点的父结点编号为int(k/2); ②若2k≤n,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点(也无右子结点);

③若2k+1≤n,则编号为k的结点的右子结点编号为2k+1;否则该结点无右子结点。 满二叉树是指除最后一层外,每一层上的所有结点有两个子结点,则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。

完全二叉树是指除最后一层外,每一层上的结点数均达到最大值,在最后一层上只缺少右边的若干结点。

二叉树存储结构采用链式存储结构,对于满二叉树与完全二叉树可以按层序进行顺序存储。 二叉树的遍历:

(1)前序遍历(dlr),首先访问根结点,然后遍历左子树,最后遍历右子树;

(2)中序遍历(ldr),首先遍历左子树,然后访问根结点,最后遍历右子树;

(3)后序遍历(lrd)首先遍历左子树,然后访问遍历右子树,最后访问根结点。

7 查找技术

顺序查找的使用情况:

(1)线性表为无序表;

(2)表采用链式存储结构。

二分法查找只适用于顺序存储的有序表,对于长度为n的有序线性表,最坏情况只需比较log2n次。

8 排序技术

排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。

交换类排序法:(1)冒泡排序法,需要比较的次数为n(n-1)/2; (2)快速排序法。

插入类排序法:(1)简单插入排序法,最坏情况需要n(n-1)/2次比较;(2)希尔排序法,最坏情况需要o(n1.5)次比较。

选择类排序法:(1)简单选择排序法,

最坏情况需要n(n-1)/2次比较;(2)堆排序法,最坏情况需要o(nlog2n)次比较。

二、程序设计基础

1.程序设计方法与风格

2.结构化程序设计。

3.面向对象的程序设计方法,对象,方法,属性及继承与多态性。

三、软件工程基础

1.软件工程基本概念,软件生命周期概念,软件工具与软件开发环境。

2.结构化分析方法,数据流图,数据字典,软件需求规格说明书。

3.结构化设计方法,总体设计与详细设计。

4.软件测试的方法,白盒测试与黑盒测试,测试用例设计,软件测试的实施,单元测试、集成测试和系统测试。

5.程序的调试,静态调试与动态调试。

四、数据库设计基础

1.数据库的基本概念:数据库,数据库管理系统,数据库系统。

2.数据模型,实体联系模型及E―R图,从E―R图导出关系数据模型。

3.关系代数运算,包括集合运算及选择、投影、连接运算,数据库规范化理 论。

4.数据库设计方法和步骤:需求分析、概念设计、逻辑设计和物理设计的相关策略。