当前位置:文档之家› 二级公共基础知识总结

二级公共基础知识总结

二级公共基础知识总结
二级公共基础知识总结

二级公共基础知识总结(30分:10选择+5填空)

第一章数据结构与算法

一.算法

1.概念:是解题方案的准确而完整的描述。算法不等于程序,也不等于计算方法。

2.基本特征:

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

(2)有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止;

(3)可行性,算法原则上能够精确地执行;

(4)拥有足够的情报。

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

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

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

6.基本控制结构:顺序结构、选择结构、循环结构。

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

8.算法复杂度(算法效率的度量)

(1)算法时间复杂度:指执行算法所需要的计算工作量。即算法执行过程中所需要的基本运算次数。通常,一个算法所用的时间包括编译时间和运行时间。

(2)算法空间复杂度:指执行这个算法所需要的内存空间。包括算法程序所占的空间,输入的初始数据所占的空间,算法执行过程中所需的额外空间。

二.数据结构

1.数据的基本单位是数据元素

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

3.数据的存储结构(也称数据物理结构):数据的逻辑结构在计算机存储空间中的存放形

4.数据的存储结构有顺序、链接、索引、散列。

5.数据结构类型(按各元素之间前后件关系的复杂度划分):

(1)线性结构的条件:①有且只有一个根结点;②每一个结点最多有一个前件,也最多有一个后件。

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

6.线性结构:

(1)线性表

①记录:由若干项数据元素组成的数据元素

②文件:由多个记录构成的线性表。

③线性表的顺序存储结构基本特点:

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

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

④线性链表(线性表的链式存储结构)

数据结构中的每一个结点对应于一个存储单元,这种存储单元称为存储结点,简称结点。

结点由两部分组成:

a)用于存储数据元素值,称为数据域;

b)用于存放指针,称为指针域,用于指向前一个或后一个结点。

★在链式存储结构中,存储数据结构的存储空间可以不连续,各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的。

★链式存储方式即可用于表示线性结构,也可用于表示非线性结构。

★链式存储结构需要更多地存储空间

(2)栈

①限定在一端(即栈顶)进行插入与删除的线性表。

②栈顶位置用指针top表示。栈底位置用指针bottom表示。

③栈按照“先进后出”(FILO)或“后进先出”(LIFO)组织数据,栈具有记忆作用。

④栈的存储方式有顺序存储和链式存储。

⑤栈的基本运算:

a)入栈运算,在栈顶位置插入元素;

b)退栈运算,删除元素(取出栈顶元素并赋给一个指定的变量);

c)读栈顶元素,将栈顶元素赋给一个指定的变量,此时指针无变化。

⑥栈的元素个数=bottom-top+1

(3)队列

①指允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。

②用rear指针指向队尾,用front指针指向队头元素的前一个位置。

③队列是“先进先出”(FIFO)或“后进后出”(LILO)的线性表。

④队列运算包括:

a) 入队运算:从队尾插入一个元素;b) 退队运算:从队头删除一个元素。

⑤队列的顺序存储结构一般采用队列循环的形式。

循环队列s=0表示队列空;s=1且front=rear表示队列满。

⑥循环队列的元素个数:

front

front>rear时,元素个数=n(循环队列容量)-front+rear

7.非线性结构

(1)树

①每一个结点只有一个前件,称为父结点。

②没有前件的结点只有一个,称为树的根结点,简称树的根。

③每一个结点可以有多个后件,称为该结点的子结点。

④没有后件的结点称为叶子结点。

⑤一个结点所拥有的后件的个数称为该结点的度,所有结点中最大的度称为树的度。

⑥树的最大层次称为树的深度。

(2)二叉树

①特点:

a)非空二叉树只有一个根结点;

b)每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。

②满二叉树是指除最后一层外,每一层上的所有结点有两个子结点,则k层上有2k-1个结点深

度为m的满二叉树有2m-1个结点。

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

③基本性质:

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

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

c)度为0的结点(即叶子结点)=度为2的结点数+1;

d)二叉树总结点数=度为0的结点数+度为1的结点数+度为2的结点数

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

部分

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

g)完全二叉树中度为1的节点只可能是0或1个

补充:增加度为1的结点不会影响二叉树的叶子结点数,每增加一个度为2的结点便会增加一个叶子结点,没有度为2的结点时叶子结点数为1。

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

⑤二叉树的遍历:

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

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

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

前序遍历结果为 a b d e h i c f g ;中序遍历结果为 d b h e i a f c g ;后序遍历结果为 d h i e b f g c a

例2:图1.13的二叉树。

图1.13

(1)前序遍历

先访问整棵二叉树的根结点A,然后再先序遍历左子树T1;在访问T1时,也以先序遍历原则,先访问T1的根结点B,然后再先序遍历T1的左子树T11;在访问T11时,也以先序遍历原则,先访问T11的根结点D,然后再先序遍历T11的左子树。由于此时T11的左子树只有H结点,所以访问H结点,T11的左子树先序遍历结束,根据先序遍历的原则,进行先序遍历T11的右子树。由于T11的右子树只有I结点,故访问此结点后T11的右子树的先序遍历结束。先序遍历完T11子树后,返回T1子树,先序遍历T1的右子树。先序遍历完T1子树后,接着先序遍历根结点A的右子树T2。先序遍历完T2后,该二叉树的所有结点都已经访问过,各结点被访问的顺序为:ABDHIECFG

(2)中序遍历:

先中序遍历左子树,然后再访问根结点,最后再中序遍历右子树。对图1.12的二叉树进行中序遍历,访问各个结点的顺序为:HDIBEAFCG

(3)后序遍历:

先后序遍历左子树,然后再后序遍历右子树,最后再访问根结点。对图1.12的二叉树进行后序遍历,访问各个结点的顺序为:HIDEBFGCA。

下面树的先序、中序、后续遍历的结果依次为__ abdcef _、bdaecf _、_ dbefca

小结:逻辑结构可分为线性表和非线性表。

线性表包括栈、队列,其存储方式为顺序存储、链式存储均可。链式型有:线性链表,带链的栈,带链的队列,循环链表等。

非线性表包括树(二叉树),其存储方式为链式存储。

8. 查找技术

只能使用顺序查找的两种情况:

(1)线性表为无序表,不管是顺序存储还是链式存储;

(2)表采用链式存储结构,即使是有序线性表。

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

次,而顺序查找需要比较n次。

9. 排序技术

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

类别排序方法最坏情况下的比较次数

交换类冒泡排序n(n-1)/2快速排序n(n-1)/2

插入类简单插入排序n(n-1)/2希尔排序O(n1.5)

选择类简单选择排序n(n-1)/2堆排序O(nlog2n)

★相比以上几种(除希尔排序法外),堆排序法的时间复杂度最小。

第二章程序设计基础

一.程序设计设计方法和风格

1.“清晰第一、效率第二”已成为当今主导的程序设计风格。

2. 形成良好的程序设计风格需注意:

(1)源程序文档化;(2)数据说明的次序要规范化;

(3)语句的结构应该简单直接,不要为提高效率而复杂化;(4)输入数据前要有提示信息和输出信息符合规范。

3. 注释:序言性注释和功能性注释。

二.结构化程序设计

1. 基本原则:

(1)自顶向下;(2)逐步求精;(3)模块化;(4)限制使用goto语句。

2. 基本结构:

(1)顺序结构:一种简单的程序设计,最基本、最常用的结构;

(2)选择结构:又称分支结构,包括简单选择和多分支选择结构,可根据条件,判断应该选择哪一条分支来执行相应的语句序列;

(3)循环结构:又称重复结构,可根据给定条件,判断是否需要重复执行某一相同或类似的程序段。

3. 基本工具:程序流程图,N-S图

4. 特点:只有一个入口和出口

三.面向对象的程序设计(主要考虑的是提高软件的可重用性)

1. 面向对象的程序设计的首次提出以60年代末挪威奥斯陆大学和挪威计算机中心研制的SIMULA语言为标志。

2. 面向对象方法的优点:

(1)与人类习惯的思维方法一致;(2)稳定性好;(3)可重用性好;(4)易于开发大型软件产品;(5)可维护性好。

3. 面向对象技术的基本特征:

(1)抽象性

(2)继承性

①继承具有传递性,一个类实际上继承了他上层的全部基类的特性。

②继承分单继承和多重继承。

单继承指一个类只允许有一个父类,即类等级为树形结构;多重继承指一个类允许有多个父类。

*:类的继承性是类之间共享属性和操作的机制,它提高了软件的可重用性。

(3)多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象

(4)封装性

4. 对象是属性和方法的封装体,一个对象由对象名、属性和操作三部分组成,对象是实体的抽象。

(1)基本特点:标识唯一性,分类性,多态性,封装性(实现信息屏蔽)和模块独立性

(2)属性即对象所包含的信息,它在设计对象时确定,一般只能通过执行对象的操作来改变。

操作描述了对象执行的功能,是对象的动态属性,操作也称为方法或服务。

5. 类是指具有共同属性、共同方法的对象的集合。所以类是对象的抽象,对象是对应类的一个实例。

6. 消息是一个实例与另一个实例之间传递的信息。对象间的通信靠消息传递。它统一了数据流和控制流。

*:在面向对象方法中,一个对象请求另一个对象为其服务的方式是通过发送消息。

第三章软件工程基础

一.软件工程基本概念

1. 计算机软件是包括程序、数据及相关文档的完整集合。

2. 软件按功能分为:

应用软件:教务管理系统

系统软件:操作系统

支撑软件(或工具软件):编译软件,汇编软件

3. 软件危机主要表现在成本、质量、生产率等问题。

4. 软件工程的核心思想是把软件产品看作是一个工程产品来处理。

5. 软件工程包括3个要素:方法、工具和过程。

6. 软件生命周期:软件产品从提出、实现、使用维护到停止使用退役的过程。

分三个阶段:(1)定义阶段:可行性研究与计划制定;需求分析

(2)开发阶段:软件设计(概要设计和详细设计);软件实现;软件测试

(3)维护阶段:运行和维护

二.需求分析

1.工作:需求获取,需求分析,编写需求规格说明书,需求评审。

2.从需求分析建立的模型的特性来分:静态分析和动态分析

3.软件需求规格说明书(SRS)是需求分析阶段的最后成果

特点:正确性;无歧义性;完整性;可验证性;一致性;可理解性;可追踪性

4.方法:(1)结构化需求分析方法;(2)面向对象的分析的方法

三.结构化分析方法

1. 结构化分析方法(SA):面向数据流进行需求分析的方法

2. 结构化分析方法的实质:着眼于数据流,自顶向下,逐层分解,建立系统的处理流程,以数据流图

和数据字典为主要工具,建立系统的逻辑模型。

3. 结构化分析的常用工具:数据流图;数据字典;判定树;判定表。

(1)数据流图(DFD图):描述数据处理过程的工具,是需求理解的逻辑模型的图形表示,它直接支持系统功能建模。

①加工(转换)——圆框,输入数据经加工变换产生的输出。

②数据流——箭头,沿箭头方向传递数据的通道,一般在旁边标注数据流名。

③存储文件(数据源)——双横线,表示处理过程中存放各种数据的文件。

④源、潭——方框,表示系统和环境的接口,属系统之外的实体。

*:数据字典是结构化分析的核心。

四.结构化设计方法

1. 软件设计的基本原理是:(1)抽象;(2)模块化;(3)信息隐蔽;(4)模块独立性。

2. 衡量软件模块独立性使用耦合性和内聚性两个定性的度量标准。

耦合性是模块见相互连接的紧密程度的度量。内聚性是一个模块内部各个元素间彼此结合的紧密程度的度量。

*:在程序结构中各模块的内聚性越强,则耦合性越弱。

*:优秀软件应高内聚,低耦合,有利于提高模块的独立性。

五.软件设计

1. 概要设计的基本任务是:

(1)设计软件系统结构;(2)数据结构及数据库设计;(3)编写概要设计文档;(4)概要设计文档评审。

在结构图(SC)中,模块用一个矩形表示,箭头表示模块间的调用关系。

可以用带注释的箭头表示模块调用过程中来回传递的信息。

还可用带实心圆的箭头表示传递的是控制信息,空心圆箭心表示传递的是数据。

2. 详细设计常见工具:

?图形工具:程序流程图(PFD)、N-S图(方框图)、问题分析图(PAD)和HIPO图

?表格工具:判定表

?语言工具:PDL(伪码)

*:程序流程图中:箭头为控制流、方框为加工步骤、菱形为逻辑条件。

六.软件测试

1. 软件测试的目的:发现错误而执行程序的过程。

2. 软件测试方法:静态测试和动态测试。

(1)静态测试:代码检查、静态结构分析、代码质量度量。不实际运行软件,主要通过人工进行。

(2)动态测试:是基本计算机的测试,主要包括白盒测试方法和黑盒测试方法。

白盒测试:也称结构测试或逻辑测试。在程序内部进行,主要用于完成软件内部操作的验证。白盒测试主要考虑内部的逻辑结构。主要方法有逻辑覆盖、基本路径测试。

黑盒测试:也称功能测试或数据驱动测试。是在软件接口处进行,完成功能验证。黑盒测试完全不考虑程序内部的逻辑结构和内部特性,只依据程序的需求和功能规格说明,检查程序的

功能是否符合它的设计要求。用于软件确认测试。主要方法有等价类划分法、边界值分

析法、错误推测法、因果图等。

3. 软件测试过程一般按4个步骤进行:

(1)单元测试、集成测试、验收测试(确认测试)和系统测试。

(2)单元测试是对模块(程序单元)进行,静态动态均有,动态时以白盒为主辅之以黑盒。

(3)集成测试是测试、组装软件。

(4)确认测试的任务是验证软件的功能和性能及其他特性是否满足了需求规格说明中的各项需求以及软件配置是否完全正确,先用黑盒。

七.程序的调试

1. 程序调试的任务是诊断和改正程序中的错误,主要在开发阶段进行。

2.程序调试的基本步骤:

(1)错误定位;

(2)修改设计和代码,以排除错误;

(3)进行回归测试,防止引进新的错误。

3.软件调试可分为静态调试和动态调试。

静态调试主要是指通过人的思维来分析源程序代码和排错,是主要的设计手段,而动态调试是辅助静

态调试。

主要调试方法有:(1)强行排错法;(2)回溯法;(3)归纳法;(4)演绎法。

第四章数据库设计基础

一.数据库系统的基本概念

1. 数据库管理系统的六大功能:

(1)数据模式定义:即为数据库构建其数据框架;

(2)数据存取的物理构建:为数据模式的物理存取与构建提供有效的存取方法与手段;

(3)数据操纵:为用户使用数据库的数据提供方便,如查询、插入、修改、删除等以及简单的算术运算及统计;

(4)数据的完整性、安全性定义与检查;

(5)数据库的并发控制与故障恢复;

(6)数据的服务:如拷贝、转存、重组、性能监测、分析等。

为完成以上功能,数据库管理系统提供以下的数据语言:

(1)数据定义语言(DDL):负责数据的模式定义与数据的物理存取构建;

(2)数据操纵语言(DML):负责数据的操纵,如查询与增、删、改等;

(3)数据控制语言(DCL):负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等。

数据语言按其使用方式具有两种结构形式:

交互式命令(又称自含型或自主型语言);宿主型语言(一般可嵌入某些宿主语言中)。

2.数据库管理员:对数据库进行规划、设计、维护、监视等的专业管理人员。

3.数据库系统:由数据库(数据)、数据库管理系统(软件)、数据库管理员(人员)、硬件平台(硬

件)、软件平台(软件)五个部分构成的运行实体。数据库系统需要操作系统的支持.

4.数据库应用系统:由数据库系统、应用软件及应用界面三者组成。

5.数据管理发展的三个阶段:人工管理阶段,文件系统阶段,数据库系统阶段。而数据独立性最高的是

数据库系统。

6.数据库系统的基本特点:数据的集成性、数据的高共享性与低冗余性、数据独立性(物理独立性与

逻辑独立性)、数据统一管理与控制。

6.数据库系统的三级模式:

(1)概念模式:数据库系统中全局数据逻辑结构的描述,全体用户公共数据视图;

(2)外模式:也称子模式与用户模式。是用户的数据视图,也就是用户所见到的数据模式;

(3)内模式:又称物理模式,它给出了数据库物理存储结构与物理存取方法。

7.数据库系统的两级映射:

(1)概念模式到内模式的映射;

(2)外模式到概念模式的映射。

二数据模型

1. (1)E-R模型(实体联系模型)的基本概念

①实体:现实世界中的事物;

②属性:事物的特性;

③联系:现实世界中事物间的关系。实体集间的联系有一对一、一对多、多对多的联系。

E-R模型基本概念之间的联接关系:实体是概念世界中的基本单位,属性有属性域,每个实体可取属性域内的值。一个实体的所有属性值叫元组。

(2)E-R模型的图示法:描述概念模型的常用工具。

实体集表示法——矩形;属性表法——椭圆形;联系表示法——菱形。

2.数据库管理系统常见的数据模型有层次模型、网状模型和关系模型三种。

▲层次模型的基本结构是树形结构,具有以下特点:

(1)每棵树有且仅有一个无双亲结点,称为根;

(2)树中除根外所有结点有且仅有一个双亲。

▲从图论观点看,网状模型是一个不加任何条件限制的无向图。

▲关系模型是数学化的模型。要用到集合论、离散数学等理论知识。

关系模型采用二维表来表示,简称表,由表框架及表的元组组成。一个二维表就是一个关系。

每行数据称为元组。在二维表中凡能唯一标识元组的最小属性称为键或码。从所有侯选键中选取一个作为用户使用的键称主键。表A中的某属性是某表B的键,则称该属性集为A的外键或外码。

二维表的表框架由n个命名的属性组成,n称为属性元数。每个属性有一个取值范围称为值域。表框架对应了关系的模式,即类型的概念。在表框架中按行可以存放数据,每行数据称为元组,实际上,一个元组是由n个元组分量所组成,每个元组分量是表框架中每个属性的投影值。

学号姓名性别出生年月班级籍贯

2007102张洁然男07-07-8807动画1班天津

2007203李一明男05-01-8707播音5班广西南宁

2007305王丽女04-09-8807管理4班辽宁沈阳

2007406刘宏男10-11-8807新闻3班江苏南京

*:同一个关系模型的任两个元组值不能完全相同。

主码:或称为关键字、主键,简称码、键,表中的一个属性或几个属性的组合、其值能唯一地标识表中一个元组的,称为关系的主码或关键字。例如,学生的学号。主码属性不能取空值。

外部关键字:或称为外键,在一个关系中含有与另一个关系的关键字相对应的属性组称为该关系的外部关键字。外部关键字取空值或为外部表中对应的关键字值。例如,在学生表中含有的所属班级名字,是班级表中的关键字属性,它是学生表中的外部关键字。

关系中的数据约束:

(1)实体完整性约束:约束关系的主键中属性值不能为空值;

(2)参照完全性约束:是关系之间的基本约束;

(3)用户定义的完整性约束:它反映了具体应用中数据的语义要求。

3。关系代数

( 1).关系数据库系统的特点之一是它建立在数据理论的基础之上,有很多数据理论可以表示关系模型的数据操作,其中最为著名的是关系代数与关系演算。

( 2 )关系数据库管理系统能实现的专门关系运算包括:选择、投影、连接。

( 3 )关系模型的基本运算:

①插入②删除③修改④查询(包括投影、选择、笛卡尔积运算)

还有扩充运算交、除、连接及自然连接运算。在关系运算中,连接运算后得到的新表的属性是运算前表中属性相加。即多于原来关系中属性的个数。

( 4 )集合运算及选择、投影、连接运算

①并(∪):关系R和S具有相同的关系模式,R和S的并是由属于R或属于S的元组构成的集合。

②差(-):关系R和S具有相同的关系模式,R和S的差是由属于R但不属于S的元组构成的集

合。

③交(∩):关系R和S具有相同的关系模式,R和S的交是由属于R且属于S的元组构成的集合。

④广义笛卡尔积(×):设关系R和S的属性个数分别为n、m,则R和S的广义笛卡尔

积是一个有(n+m)列的元组的集合。每个元组的前n列来自R的一个元组,后m列来自S的一个元组,记为R×S。

*:根据笛卡尔积的定义:有n元关系R及m元关系S,它们分别有p、q个元组,则关系R与S经笛卡尔积记为R×S,该关系是一个n+m元关系,元组个数是p×q,由R与S的有序组组合而成。

例:有两个关系R和S,分别进行并、差、交和广义笛卡尔积运算。

(5)在关系型数据库管理系统中,基本的关系运算有选择、投影与联接三种操作:

1)选择:选择指的是从二维关系表的全部记录中,把那些符合指定条件的记录挑出来。(产生新行)2)投影:投影是从所有字段中选取一部分字段及其值进行操作,它是一种纵向操作。(产生新列)3)联接:联接将两个关系模式基于共有属性拼接成一个更宽的关系模式,生成的新关系中包含满足联接条件的元组。

4. 数据库设计与管理

(1)数据库设计是数据应用的核心。数据库设计的根本目标是解决数据共享问题.

(2)数据库设计的两种方法:

1)面向数据:以信息需求为主,兼顾处理需求;

2)面向过程:以处理需求为主,兼顾信息需求。

(3)数据库的生命周期:需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段、编码阶段、测试阶段、运行阶段、进一步修改阶段。

(4)数据库设计分为四个阶段:需求分析阶段,概念设计阶段,逻辑设计阶段,物理设计阶段。

(5)需求分析常用结构化分析方法和面向对象的方法。结构化分析(简称SA)方法用自顶向下、逐层分解的方式分析系统。用数据流图表达数据和处理过程的关系。对数据库设计来讲,数据字典是进行详细的数据收集和数据分析所获得的主要结果。数据字典是各类数据描述的集合,包括5个部分:数据项、数据结构、数据流(可以是数据项,也可以是数据结构)、数据存储、处理过程。

(6)数据库概念设计的目的是分析数据内在语义关系。设计的方法有两种

1)集中式模式设计法(适用于小型或并不复杂的单位或部门);

2)视图集成设计法。

设计方法:E-R模型与视图集成进行设计。

视图设计一般有三种设计次序:自顶向下、由底向上、由内向外。

视图集成的几种冲突:命名冲突、概念冲突、域冲突、约束冲突。

(7)关系视图设计又称外模式设计。

关系视图的主要作用:

1)提供数据逻辑独立性;2)能适应用户对数据的不同需求;3)有一定数据保密功能。

(8)数据库的物理设计主要目标是对数据内部物理结构作调整并选择合理的存取路径,以提高数据库访问速度有效利用存储空间。一般RDBMS中留给用户参与物理设计的内容大致有索引设计、集成簇设计和分区设计。

(9)数据库管理的内容:

1)数据库的建立;2)数据库的调整;3)数据库的重组;

4)数据库安全性与完整性控制;5)数据库的故障恢复;6)数据库监控。

(10)数据库设计方法和步骤

1)数据库设计阶段包括:需求分析、概念分析、逻辑设计、物理设计。

2)数据库设计的每个阶段都有各自的任务:

a)需求分析阶段:这是数据库设计的第一个阶段,任务主要是收集和分析数据,这一阶段收集

到的基础数据和数据流图是下一步设计概念结构的基础。

b)概念设计阶段:分析数据间内在语义关联,在此基础上建立一个数据的抽象模型,即形成E-R

图。

1.*:数据库概念设计的过程包括选择局部应用、视图设计和视图集成。

c)逻辑设计阶段:将E-R图转换成指定RDBMS中的关系模式。

d)物理设计阶段:对数据库内部物理结构作调整并选择合理的存取路径,以提高数据库访问速

度及有效利用存储空间。

2011全国计算机等级考试二级公共基础知识教程

目录 二级公共基础知识考纲 (1) 第一章数据结构与算法 (2) 第二章程序设计基础 (19) 第三章软件工程基础 (23) 第四章数据库设计基础 (32) 全国计算机等级考试二级公共基础知识考纲 考试内容 一、基本数据结构与算法 1.算法的基本概念;算法复杂度的概念和意义(时间复杂度与空间复杂度)。 2.数据结构的定义;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念。 3.线性表的定义;线性表的顺序存储结构及其插入与删除运算。 4.栈和队列的定义;栈和队列的顺序存储结构及其基本运算。 5.线性单链表、双向链表与循环链表的结构及其基本运算。 6.树的基本概念;二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历。 7.顺序查找与二分法查找算法;基本排序算法(交换类排序,选择类排序,插入类排序)。 二、程序设计基础 1.程序设计方法与风格。 2.结构化程序设计。 3.面向对象的程序设计方法,对象,方法,属性及继承与多态性。 三、软件工程基础 1.软件工程基本概念,软件生命周戎概念,软件工具与软件开发环境。 2.结构化分析方法,数据流图,数据字典,软件需求规格说明书。 3.结构化设计方法,总体设计与详细设计。 4.软件测试的方法,白盒测试与黑盒测试,测试用例设计,软件测试的实施,单元测试、集成测试和系统测试。 5.程序的调试,静态调试与动态调试。 四、数据库设计基础 1.数据库的基本概念:数据库,数据库管理系统,数据库系统。 2.数据模型,实体联系模型及E-R图,从E-R图导出关系数据模型。 3.关系代数运算,包括集合运算及选择、投影、连接运算,数据库规范化理论。 4.数据库设计方法和步骤:需求分析、概念设计、逻辑设计和物理设计的相关策略。 考试方式 公共基础的考试方式为笔试,与C语言(V isualBASIC、V isual FoxPro、Java、Access、Visual C++)的笔试部分合为一张试卷。 公共基础部分占全卷的30分。公共基础知识有10道选择题和5道填空题。 第一章数据结构与算法 一、内容要点 (一)算法 1.算法的基本概念 算法是指解题方案的准确而完整的描述。即是一组严谨地定义运算顺序的规则,并且每一个规则都是有效的,且是明确的,没有二义性,同时该规则将在有限次运算后可终止。 1)算法的基本特征 (1)可行性 由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题而设计的,因此,它总是受到计算工具的限制,使执行产生偏差。

全国计算机等级考试二级公共基础知识要点汇总

全国计算机等级考试二级公共基础知识要点汇总 第一章数据结构与算法 1.1 算法 算法:是指解题方案的准确而完整的描述。 算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。 算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。特征包括: (1)可行性; (2)确定性,算法中每一步骤都必须有明确定义,不充许有模棱两可的解释,不允许有多义性; (3)有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止,包括合理的执行时间的含义; (4)拥有足够的情报。 算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构。 指令系统:一个计算机系统能执行的所有指令的集合。 基本运算包括:算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构:顺序结构、选择结构、循环结构。 算法基本设计方法:列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度:算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 1.2 数据结构的基本概念 数据结构研究的三个方面: (1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构; (2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;(3)对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含: (1)表示数据元素的信息; (2)表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件: (1)有且只有一个根结点; (2)每一个结点最多有一个前件,也最多有一个后件。 非线性结构:不满足线性结构条件的数据结构。 1.3 线性表及其顺序存储结构 线性表是由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。 在复杂线性表中,由若干项数据元素组成的数据元素称为记录,而由多个记录构成的线性表又称为文件。 非空线性表的结构特征: (1)且只有一个根结点a1,它无前件;

教育公共基础知识总结归纳

2010年教师招聘考试公共基础知识总结归纳 填空: 1、制度化教育阶段开始于:近代。 2、各国的学校教育系统基本形成于:19世纪末。 3、现在世界上大多数国家的义务教育年限在:9年或9年以上。 4、“不愤不启,不悱不发”启发教学法的最早倡导者是:孔子。 5、“建国君民,教学为先”提示了教育的重要性和:教育与政治的关系。 6、建国初期,对我国教育理论体系影响较大的苏联教育家是:凯洛夫。 7、狭义的教育主要是指:学校教育。产生于奴隶社会初期 8、古代中国学校教育的主要内容是六艺,它包括:礼、乐、射、御、书、数。 9、在古代印度,能够享受最好教育的是当时的最高种姓:婆罗门。 10、制度化教育或正规教育形成的主要标志是形成近代的:学校教育系统。 11、中国的科举制度开始于:隋唐时期。 12、战国后期,我国出现的具有世界影响的教育文献是:《学记》。 13、在古希腊,最早提出发现法的大教育家是:苏格拉底。 14、古希腊着名思想家柏拉图的教育代表作是:《理想国》。 15、在人类教育史上首次提出“教育遵循自然”学说的教育思想家是古希腊的:亚里士多德。 16、教育学作为一门独立的学科萌芽于:资本主义社会初期夸美纽斯的《大教育学论》。(首先提出普及教育思想的教育家及其着作) 17、强调教育学的心理学和伦理学基础,奠定了科学教育学基础的教育家是:赫尔巴特。 18、资产阶级传统教育学的代表人物是:赫尔巴特。 19、20世纪初实用主义教育学的代表人物和作品是:杜威《民本主义与教育》。 20、主张教师应以学生的发展为目的,以儿童中心主义着称的美国教育家是:杜威。实用主义 21、制度化的教育是指具有:层次结构和年龄分级的教育制度。 22、普通教育主要是指以升学为目标,以(基础科学知识)为主要教学内容的学校教育。 23、职业教育是以生产劳动的知识和技能为主要教学内容,以(就业)为主要目标的学校教育。 24、英国教育家洛克将那种既有贵族气派,又有资产阶级创业精神和才干,还有强健的体魄的人称之为(绅士)。 25、教育区别于其他事物和现象的根本特征,教育的质的规定性是指教育是一种(培养人)的社会活动。 26、规定着一个国家各级各类学校教育的系统,包括各级各类学校的性质、任务、入学条件、企业年限以及它们之间关系的制度中(学校教育制度)。27、西欧中世纪早期的教会学校主要学习神学和七艺,七艺包括(修词、音乐、算术、几何、文法、天文、辨证法) 28、中国近代制度化教育兴起的标志是清朝末年的(“废科举,兴学校”)。 29、中国近代完备的学制系统产生于1902年的“壬寅学制”以及1903年的(“癸卯学制”)。

计算机二级公共基础知识题库及答案

第一章数据结构 一、选择题 (1)下列数据结构中,能用二分法进行查找的是 A)顺序存储的有序线性表 B)线性链表 C)二叉链表 D)有序线性链表 【答案】A 【解析】二分查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列(即从小到大.但允许相邻元素值相等)的。选项A正确。 (2)下列关于栈的描述正确的是 A)在栈中只能插入元素而不能删除元素 B)在栈中只能删除元素而不能插入元素 C)栈是特殊的线性表,只能在一端插入或删除元素 D)栈是特殊的线性表,只能在一端插入元素,而在另一端删除元素 【答案】C 【解析】栈是一种特殊的线性表,其插入与删除运算都只在线性表的一端进行。由此可见,选项A、选项B和选项D错误,正确答案是选项C。 (3)下列叙述中正确的是 A)一个逻辑数据结构只能有一种存储结构 B)数据的逻辑结构属于线性结构,存储结构属于非线性结构 C)一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理的效率 D)一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理的效率 【答案】D 【解析】一般来说,一种数据的逻辑结构根据需要可以表示成多种存储结构,常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构,其数据处理的效率是不同的。由此可见,选项D的说法正确。 (4)算法执行过程中所需要的存储空间称为算法的 A)时间复杂度B)计算工作量C)空间复杂度D)工作空间 【答案】c 【解析】算法执行时所需要的存储空间,包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间,其中额外空间还包括算法程序执行过程的工作单元以及某种数据结构所需要的附加存储空间。这些存储空间共称为算法的空间复杂度。 (5)下列关于队列的叙述中正确的是 A)在队列中只能插入数据B)在队列中只能删除数据 C)队列是先进先出的线性表D)队列是先进后出的线性表 【答案】c 【解析】对队列可以进行插入和删除数据的操作,只是插入数据只能在队尾,删除数据只能在队头。所以队列是先进先出的线性表。 (6)设有下列二叉树: A

公共基础知识精髓要点总结

公共基础知识精髓要点总结 1.我国政权组织形式是人民代表大会制。 2.行政许可是行政机关的批准行为。 3. 行政行为以受法律规范拘束的程度为标准,可以分为两类羁束行政行为与自行政行为以受法律规范拘束的程度为标准,由裁量行政行为。由裁量行政行为。 4. 在诉讼期间的最后六个月内,因不可抗力或者其他障碍不能行使请求权的,在诉讼期间的最后六个月内,因不可抗力或者其他障碍不能行使请求权的,诉讼时效中止。(最长诉讼时效为适用范围没有限制,诉讼时效中止。最长诉讼时效为20 年,适用范围没有限制,从权利受侵害时(开始计算,不适用中止和中断,只适用于延长)开始计算,不适用中止和中断,只适用于延长) 5.书写公文中的成文日期应使用汉字。(其中零还是用阿拉伯数字0 表示) 6.规定用于依照有关法律规定发布行政法规和规章。 7.以上请示事项当否,请即批复。 8.命令不属于规定性文件,属于规定性文件的有规定、条例、办法。 9.由机关领导对发文稿批注核准发出的意见并签署姓名及日期的活动,是发文处理中的签发。(是发文中的核心程序,收文中的核心程序是承办)。 10.一切唯心主义哲学认为世界的本原是意识的。(唯心主义与唯物主义的根本分歧是:谁是世界的本原)

11.“静者,动之静也”的观点是认为静止是运动的特殊状态 12.运动的主体是物质 13.质变是事物根本性质的变化 14.马克思主义哲学认为否定是辩证的否定。 15.“离开革命实践的理论是空洞的理论,而不以革命理论为指南的实践是盲目的实践。” 这段话强调的是要坚持理论和实践相结合的原则 16.历史唯物主义的任务在于揭示社会发展的一般规律社会基本矛盾运动(即生产关系和生产力的矛盾) 17.社会进步的内在根据是社会基本矛盾运动(即生产关系和生产力的矛盾) 18.在社会主义建设新时期,中国共产党完成指导思想拨乱反正的标志是党的十一届六中全会通过《关于建国以来党的若干历史问题的决议》届六中全会通过《关于建国以来党的若干历史问题的决议》 19.邓小平对党的思想路线的贡献在于强调解放思想 20.党的十四大把社会主义初级阶段理论作为社会主义发展阶段问题进行了新的论述,成为邓小平理论的重要基础。 21.我国企业改革的目标是建立现代企业制度 22.建立社会主义市场经济体制,就是要使市场在国家宏观调控下对生产力的配置起基础性作用 23.当社会总需求大于社会总供给时(经济过热),一般不宜采取松的货币政策,采取紧缩的货币政策)

计算机二级公共基础知识(全)

1.1 算法 考点1 算法的基本概念 计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。 算法(algorithm)是一组严谨地定义运算顺序的规则,并且每一个规则都是有效的,同时是明确的;此顺序将在有限的次数后终止。算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作。 1算法的基本特征 (1)可行性(effectiveness):针对实际问题而设计的算法,执行后能够得到满意的结果。 (2)确定性(definiteness):算法中的每一个步骤都必须有明确的定义,不允许有模棱两可的解释和多义性。 (3)有穷性(finiteness):算法必需在有限时间内做完,即算法必需能在执行有限个步骤之后终止。 (4)拥有足够的情报:要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时,此算法才最有效的;而当提供的情报不够时,算法可能无效。 2算法的基本要素 (1)算法中对数据的运算和操作:每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。 计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合,称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列在一般的计算机系统中,基本的运算和操作有以下4类: ①算术运算:主要包括加、减、乘、除等运算; ②逻辑运算:主要包括“与”、“或”、“非”等运算; ③关系运算:主要包括“大于”、“小于”、“等于”、“不等于”等运算; ④数据传输:主要包括赋值、输入、输出等操作。 (2)算法的控制结构:一个算法的功能不仅仅取决于所选用的操作,而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。 算法的控制结构给出了算法的基本框架,它不仅决定了算法中各操作的执行顺序,而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。 (3)算法设计的基本方法 计算机算法不同于人工处理的方法,下面是工程上常用的几种算法设计,在实际应用时,各种方法之间往往存在着一定的联系。 (1)列举法 列举法是计算机算法中的一个基础算法。列举法的基本思想是,根据提出的问题,列举所有可能的情况,并用问题中给定的条件检验哪些是需要的,哪些是不需要的。 列举法的特点是算法比较简单。但当列举的可能情况较多时,执行列举算法的工作量将会很大。因此,在用列举法设计算法时,使方案优化,尽量减少运算工作量,是应该重点注意的。 (2)归纳法 归纳法的基本思想是,通过列举少量的特殊情况,经过分析,最后找出一般的关系。从本质上讲,归纳就是通过观察一些简单而特殊的情况,最后总结出一般性的结论。

全国计算机等级考试二级公共基础知识总结

公共基础知识总结 第一章数据结构与算法 1.1 算法 算法:是指解题方案的准确而完整的描述。 算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。 算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。特征包括: (1)可行性; (2)确定性,算法中每一步骤都必须有明确定义,不充许有模棱两可的解释,不允许有多义性; (3)有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止,包括合理的执行时间的含义; (4)拥有足够的情报。 算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构。 指令系统:一个计算机系统能执行的所有指令的集合。 基本运算和操作包括:算术运算、逻辑运算、关系运算、数据传输。算法的控制结构:顺序结构、选择结构、循环结构。 算法基本设计方法:列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度:算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 1.2 数据结构的基本基本概念 数据结构研究的三个方面: (1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构; (2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构; (3)对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含: (1)表示数据元素的信息; (2)表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。

线性结构条件: (1)有且只有一个根结点; (2)每一个结点最多有一个前件,也最多有一个后件。 非线性结构:不满足线性结构条件的数据结构。 1.3 线性表及其顺序存储结构 线性表由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。 在复杂线性表中,由若干项数据元素组成的数据元素称为记录,而由多个记录构成的线性表又称为文件。 非空线性表的结构特征: (1)且只有一个根结点a1,它无前件; (2)有且只有一个终端结点an,它无后件; (3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。结点个数n称为线性表的长度,当n=0时,称为空表。线性表的顺序存储结构具有以下两个基本特点: (1)线性表中所有元素的所占的存储空间是连续的; (2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为:ADR(ai)=ADR(a1)+(i-1)k,,ADR(a1)为第一个元素的地址,k代表每个元素占的字节数。 顺序表的运算:插入、删除。(详见14--16页) 1.4 栈和队列 栈是限定在一端进行插入与删除的线性表,允许插入与删除的一端称为栈顶,不允许插入与删除的另一端称为栈底。 栈按照“先进后出”(FILO)或“后进先出”(LIFO)组织数据,栈具有记忆作用。用top表示栈顶位置,用bottom表示栈底。 栈的基本运算:(1)插入元素称为入栈运算;(2)删除元素称为退栈运算;(3)读栈顶元素是将栈顶元素赋给一个指定的变量,此时指针无变化。 队列是指允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。Rear指针指向队尾,front指针指向队头。 队列是“先进行出”(FIFO)或“后进后出”(LILO)的线性表。 队列运算包括(1)入队运算:从队尾插入一个元素;(2)退队运算:从队头删除一个元素。 循环队列:s=0表示队列空,s=1且front=rear表示队列满 1.5 线性链表 数据结构中的每一个结点对应于一个存储单元,这种存储单元称为存储结点,简称结点。

全国计算机等级考试二级公共基础知识

全国计算机等级考试二级公共基础知识复习资料 全国计算机等级考试二级公共基础知识复习资料 第一章数据结构与算法 1.1 算法 算法:是指解题方案的准确而完整的描述。 算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。 算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。特征包括: (1)可行性; (2)确定性,算法中每一步骤都必须有明确定义,不充许有模棱两可的解释,不允许有多义性; (3)有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止,包括合理的执行时间的含义; (4)拥有足够的情报。 算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构。 指令系统:一个计算机系统能执行的所有指令的集合。 基本运算包括:算术运算、逻辑运算、关系运算、数据传输。算法的控制结构:顺序结构、选择结构、循环结构。

算法基本设计方法:列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度:算法时间复杂度和算法空间复杂度。算法时间复杂度是指执行算法所需要的计算工作量。算法空间复杂度是指执行这个算法所需要的内存空间。1.2 数据结构的基本基本概念 数据结构研究的三个方面: (1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构; (2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构; (3)对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。数据的逻辑结构包含: (1)表示数据元素的信息; (2)表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件:(1)有且只有一个根结点;(2)每一个结点最多有一个前件,也最多有一个后件。非线性结构:不满足线性结构条件的数据结构。 1.3 线性表及其顺序存储结构 线性表是由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。

计算机二级公共基础知识高频考点归纳总结

第一章数据结构与算法 算法 1、算法:是指解题方案的准确而完整的描述。算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。 2、算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。特征包括:(1)可行性;(2)确定性(3)有穷性(4)拥有足够的情报。 3、算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构。 4、指令系统:一个计算机系统能执行的所有指令的集合。 5、基本运算包括:算术运算、逻辑运算、关系运算、数据传输。 6、算法的控制结构:顺序结构、选择结构、循环结构。 7、算法基本设计方法:列举法、归纳法、递推、递归、减斗递推技术、回溯法。 8、算法复杂度:算法时间复杂度和算法空间复杂度。 9、算法时间复杂度是指执行算法所需要的计算工作量。 10、算法空间复杂度是指执行这个算法所需要的内存空间。 数据结构的基本基本概念 1、数据结构研究的三个方面: (1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构; (2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;(3)对各种数据结构进行的运算。数据结构是指相互有关联的数据元素的集合。 2、数据的逻辑结构包含:(1)表示数据元素的信息;(2)表示各数据元素之间的前后件关系。数据的存储结构有顺序、链接、索引等。 3、线性结构条件:(1)有且只有一个根结点;(2)每一个结点最多有一个前件,也最多有一个后件。非线性结构:不满足线性结构条件的数据结构。 线性表及其顺序存储结构 1、线性表是由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。在复杂线性表中,由若干项数据元素组成的数据元素称为记录,而由多个记录构成的线性表又称为文件。 2、非空线性表的结构特征: (1)且只有一个根结点a1,它无前件;(2)有且只有一个终端结点an,它无后件; (3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。结点个数n称为线性表的长度,当n=0时,称为空表。 3、线性表的顺序存储结构具有以下两个基本特点:(1)线性表中所有元素的所占的存储空间是连续的; (2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 4、顺序表的运算:插入、删除。 栈和队列 1、栈是限定在一端进行插入与删除的线性表,允许插入与删除的一端称为栈顶,不允许插入与删除的另一端称为栈底。栈按照“先进后出”(FILO)或“后进先出”(LIFO)组织数据,栈具有记忆作用。用top表示栈顶位置,用bottom 表示栈底。 2、栈的基本运算:(1)插入元素称为入栈运算;(2)删除元素称为退栈运算;(3)读栈顶元素是将栈顶元素赋给一个指定的变量,此时指针无变化。 3、队列是指允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。Rear指针指向队尾,front 指针指向队头。 4、队列是“先进行出”(FIFO)或“后进后出”(LILO)的线性表。 线性链表

教育公共基础 知识点总结.

教育公共基础知识点总结 1、教育学的研究对象是学校教育现象。 2、教育现象包括学校教育、家庭教育、社会教育。 3、教育学是一种综合性的学科,既是理论学科也是应用学科。 4、完备的教师知识结构是学科基础知识、教育学科基础知识和广泛的文化科学知识。 5、孔子对我国教育的贡献有三个方面:创立私学、创立儒学、删订六经。 6、福禄贝尔被称为“幼儿园之父”。 7、杜威是“进步主义教育学派”的代表。 8、历史研究法的工作是:史料真伪的鉴别,鉴别包括:外部考证和内部考证。 9、调查研究法可分为确定课题、搜集资料、做出结论。 10、调查研究法包括:调查、研究、访问。 11、在个体早期生命中有一个比较短暂的时期,在此时期,个体对某种刺激特别敏感,过了这一时期,同样的刺激对之影响很小或没有影响。心理学者把此时期称之为关键期。 12、智力测验中的一个重要概念是智商,简称IQ=(智力年龄MA÷实际年龄 CA×100。 13、我国教育心理学家主张学生的学习分为知识的学习、技能的学习和行为规范的学习。 14、桑代克认为尝试——错误学习的基本规律有:效果律、练习律

和准备律。 15、心理辅导的一般目标可归纳为两个方面,第一是学会调适,第二是寻求发展。 16、教师合理的知识结构应包括扎实的事业知识、广泛的文化科学知识、娴熟的教育科学知识等方面;教师的能力结构主要有组织管理人员能力、语言表达能力、教育机智等方面。 17、教师良好的心理素质至少应包括良好的意志品质,稳定的情绪,良好的性格特征,清晰的自我意识等方面。 18、我国的师生关系是以培养全面发展的新人为根本目标的。其明显的特征是教育民主,尊师爱生,教学相长。 19、师生关系与一般社会关系的最大不同就在于它是因教育_而生,又为教育而存,其最大的功能就是教育功能。 20、一般来说,在师生关系中有几种典型的模式,它们分别是放任型,专制型,民主型。 21、17世纪捷克教育家夸美纽斯说:教师是太阳底下最光荣的职业。 22、俄国教育家乌伸斯基说:教师职业是历史上最伟大的事业。 23、“古之学者必有师”出自韩愈的师说《师说》。 24、前苏联教育理论家加里宁说:"教师是人类灵魂的工程师"。 25、1985年开始我国确定每年的9月10日为教师节。 26、文化对教育的制约作用表现在:教育思想和教育观点、教育内容。 27、教育通过对文化的传递、选择、融合、创造来促进文化的发展。

计算机二级公共基础知识要点总结

计算机二级公共基础知识要点总结 1.栈按先进后出的原则组织数据,所以入栈最早的最后出栈,而队列是先进先出的线性 表。 2.循环队列有队头和队尾两个指针,但是循环队列仍是线性结构的线性表。 在循环队列中只需要对头指针与队尾两个指针来共同反映队列中元素的动态变化情况。 3.当有序线性表为顺序存储时才能用二分法查找。可以证明的是对于长度为n的有序线性 表,在最坏的情况下二分法查找只需要比较log2n次,而顺序查找需要比较n次。 4.链式存储结构既可以针对线性结构也可以针对非线性结构。 链式存储结构中每个结点都由数据域与指针域两部分组成,增加了存储空间。 顺序存储结构的存储一定是连续的,链式存储结构的存储空间不一定是连续的。 5.数据流图中带箭头的线段表示的是数据流,即沿箭头方向传送数据的通道一般在旁边标 注数据流名。 程序流程图中带有箭头的线段表示的是控制流。 6.在软件开发中,需求分析阶段可以使用的工具有数据流图DFD图,数据字典DD,判定 树与判定表。 7.“对象”有如下一些基本特点:标识唯一性,分类型,多态性,封装性,模块独立性好。 8.数据管理发展至今已经历了三个阶段:人工管理阶段,文件系统阶段和数据库系统阶段。 其中最后一个阶段结构简单,使用方便,逻辑性强,物理性少,在各方面的表现都最好,一直占据数据库领域的主导地位。 9.自然链接是一种特殊的等值连接,它要求两个关系中进行比较的分量必须是相同的属性 组,并且在结果中把重复的属性列去掉。 10.内存又称主存,是CPU能直接寻址的存储空间,由半导体器件制成。内存的特点是存取 速率快。所以微机中访问速度最快的存储器是内存。 11.计算机能直接识别和执行的语言是机器语言,机器语言是用二进制代码表示的计算机能 直接识别和执行的一种机器指令的集合。它是计算机的设计者通过计算机的硬件结构赋予计算机的操作功能。机器语言具有灵活,直接执行和速度快等特点。 12.1MB=1024KB=1024*1024B=220B 13.Internet的四层结构分别是:网络接口层,网络层,传输层和应用层。 14.有序线性表既可以采用顺序存储结构,也可以采用链式存储结构。 15.栈支持子程序调用。栈是一种只能在一端进行插入或删除的线性表。 16.二叉树的基本性质:在任意一棵二叉树中,度为0的叶子结点总是比度为2的结点多一 个。 例如:某二叉树有五个度为2的结点,则该二叉树中的叶子结点数是5+1=6个。 17.冒泡排序与简单插入排序与简单选择排序法在最坏情况下均需要比较n(n-1)/2次,而堆 排序在最坏的情况下需要比较的次数是nlog2n,即在排序方法中,最坏情况下比较次数最少的是堆排序。 18.软件按功能可分为:应用软件,系统软件和支撑软件(或工具软件)。 19.软件测试的目的是为了发现错误而执行程序的过程,并不涉及改正错误。 程序调试的基本步骤有:错误定位,修改设计和代码,以排除错误进行回归测试,防止引进新的错误。程序调试通常称为Debug,即排错。 20.软件测试的基本准则有:所有测试都应追溯到需求,严格执行测试计划,排除测试的随 意性,充分注意测试中的群集现象,程序员应避免检查自己的程序,穷举测试不可能,

2017计算机二级公共基础知识完整

2017计算机二级公共基础知识完整

第一章数据结构与算法 经过对部分考生的调查以及对近年真题的总结分析,笔试部分经常考查的是算法复杂度、数据结构的概念、栈、二叉树的遍历、二分法查找,读者应对此部分进行重点学习。 详细重点学习知识点: 1.算法的概念、算法时间复杂度及空间复杂度的概念 2.数据结构的定义、数据逻辑结构及物理结构的定义 3.栈的定义及其运算、线性链表的存储方式 4.树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历 5.二分查找法 6.冒泡排序法 1.1 算法 考点1 算法的基本概念 考试链接: 考点1在笔试考试中考核的几率为30% ,主要是以填空题的形式出现,分值为2分,此考点为识记内容,读者还应该了解算法中对数据的基本运算。 计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。 1.算法的基本特征:可行性、确定性、有穷性、拥有足够的情报。 2.算法的基本要素:

(1)算法中对数据的运算和操作一个算法由两种基 本要素组成:一是对数据对象的运算和操作;二是算 法的控制结构。在一般的计算机系统中,基本的运算 和操作有以下4类:算术运算、逻辑运算、关系运算 和数据传输。 (2)算法的控制结构:算法中各操作之间的执行顺序称为算法的控制结构。 描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。 考点2 算法复杂度 考试链接: 考点2在笔试考试中,是一个经常考查的内容,在笔试考试中出现的几率为70% ,主要是以选择的形式出现,分值为2分,此考点为重点识记内容,读者还应该识记算法时间复杂度及空间复杂度的概念。 1.算法的时间复杂度算法的时间复杂度是指执行算 法所需要的计算 工作量。 同一个算法用不同的语言实现,或者用不同的编译 程序进行编译,或者在不同的计算机上运行,效率均不 同。这表明使用绝对的时间单位衡量算法的效率是不合 适的。撇开这些与计算机硬件、软件有关的因素,可 以认为一个特定算法" 运行工作量" 的大小,只依赖 于问题的规模(通常用整数n表 示),它是问题规模的函数。即算法的工作量=f(n) 2.算法的空间复杂度 算法的空间复杂度是指执行这个算法所需要的内存

公共基础知识大总结

201.毛泽东的《星星之火可以燎原》一文,标志着农村包围城市革命理论的形成 毛泽东——《目前形势和我们的任务》,明确提出了新民主主义的三大纲领 毛泽东在《目前形势和我们的任务》中指出土地改革必须注意的两个基本原则: ①必须满足雇农和贫农的要求 ②必须坚决的团结中农,不损害中农的利益 毛泽东——《将革命进行到底》,提出了人民民主专政 毛泽东1946年6月30日——《论人民民主专政》,标志着人民民主专政理论的最终形成 毛泽东1955年《中国农村的社会主义高潮》——提出了“政治工作是一切经济工作的生命线” 毛泽东1930年5月《反对本本主义》——“中国革命的胜利要靠中国同志了解中国情况”毛泽东1925《中国社会各阶级的分析》——中国过去一切革命斗争成效甚少的主要原因是:没有找到团结真正的朋友以攻击真正的敌人 八七会议——提出了“枪杆子里出政权” 《井冈山的斗争》1928.11 农村包围城市,武装夺取政权的重要文献之一 《星星之火,可以燎原》1930.1 初步形成了农村包围城市,夺取全国胜利的革命道路理论 《反对本本主义》1930.5 “没有调查,就没有发言权”,提出从实际出发的思想,首次明确反对教条主义 《中国革命和中国共产党》1939.12 首次提出了“新民主主义革命”的科学概念 系统地阐明了中国革命的历史进程必须分为民主主义革命和社会主义革命两部分 《新民主主义论》1940.1.9 指出中国革命的历史进程,必须分两步,第一步是民主主义革命,第二步是社会主义革命,这是性质不同的两个革命过程 《<共产党人>发刊词》1939.10 提出三大法宝的理论体系:统一战线、武装斗争、党的建设。提出建立一个思想上、政治上、组织上完全巩固的政党,是一项“伟大的工程”。第一次明确提出“马克思主义的理论和中国革命实践相结合”这个根本思想原则。 《论十大关系》1956.4.25 主要阐述了正确解决我国经济建设方面存在的某些矛盾的基本原理,强调要处理好矛盾的各个方面以调动各种积极因素。 《关于正确处理人民内部矛盾》1957.6.19 第一次系统阐述了社会主义社会基本矛盾的学说,提出了正确区分和处理两类不同性质矛盾的学说。 《关于领导方法的若干问题》1943.6 第一次从哲学高度对群众路线做了理论概括。“在我党的一切工作中,凡属正确的领导,必须是从群众中来,到群众中去。” 《论联合政府》1945.4 毛泽东在中共七大上的讲话。提出党的三大作风(理论联系实践,密切联系群众,批评与自我批评); 《论人民民主专政》1949年6月30 为纪念中国共产党成立二十八周年而写的一篇论文。论述了即将成立的中华人民共和国的国家性质,各阶级在国家中的地位及其相互关系,国家对内、对外政策等。 《将革命进行到底》1948.12.30 第一次使用“人民民主专政”的概念。 《反对党八股》1942.2 延安整风的文献 八七会议1927.8.7 属于毛泽东思想形成的雏形阶段。 在“八七”会议上,毛泽东就统一战线、农村问题、军事和组织问题作了多次发言,针对大革命失败后的实际情况提出了带有根本性的意见,为制定党的路线方针和政策起了重要作用。毛泽东思想作为中国化的马克思主义,对中国革命和中国共产党的指导性作用是在八七会议上第一次比较完整地体现的 首次提出马克思主义中国化的问题。提出了“枪杆子里面出政权”的著名论断

二级公共基础知识分类模拟题43

二级公共基础知识分类模拟题43 单项选择题 1、下列叙述中正确的是______。 A.所谓算法就是计算方法 B.程序可以作为算法的一种描述方法 C.算法设计只需考虑得到计算结果 D.算法设计可以忽略算法的运算时间 2、下列叙述中正确的是______。 A.算法的复杂度包括时间复杂度与空间复杂度 B.算法的复杂度是指算法控制结构的复杂程度 C.算法的复杂度是指算法程序中指令的数量 D.算法的复杂度是指算法所处理的数据量 3、下列叙述中正确的是______。 A.算法的时间复杂度与计算机的运行速度有关 B.算法的时间复杂度与运行算法时特定的输入有关 C.算法的时间复杂度与算法程序中的语句条数成正比 D.算法的时间复杂度与算法程序编制者的水平有关 4、下列叙述中正确的是______。 A.非线性结构可以为空 B.只有一个根结点和一个叶子结点的必定是线性结构 C.只有一个根结点的必定是线性结构或二叉树 D.没有根结点的一定是非线性结构 5、设数据结构B=(D,R),其中 D={a,b,c,d,e,f} R={(f,a),(d,b),(e,d),(c,e),(a,c)} 该数据结构为______。 A.线性结构 B.循环队列 C.循环链表 D.非线性结构 6、下列叙述中正确的是______。 A.矩阵是非线性结构 B.数组是长度固定的线性表 C.对线性表只能作插入与删除运算 D.线性表中各元素的数据类型可以不同 7、在线性表的顺序存储结构中,其存储空间连续,各个元素所占的字节数______。 A.不同,但元素的存储顺序与逻辑顺序一致 B.不同,且其元素的存储顺序可以与逻辑顺序不一致 C.相同,元素的存储顺序与逻辑顺序一致 D.相同,但其元素的存储顺序可以与逻辑顺序不一致 8、下列叙述中正确的是______。 A.能采用顺序存储的必定是线性结构 B.所有的线性结构都可以采用顺序存储结构 C.具有两个以上指针的链表必定是非线性结构 D.循环队列是队列的链式存储结构 9、下列叙述中正确的是______。 A.在栈中,栈顶指针的动态变化决定栈中元素的个数

计算机二级公共基础知识(全)

1.1 算法 考点1 算法的基本概念计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。 算法(algorithm)是一组严谨地定义运算顺序的规则,并且每一个规则都是有效的,同时是明确的;此顺序将在有限的次数后终止。算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作。 1 算法的基本特征 (1) 可行性(effectiveness):针对实际问题而设计的算法,执行后能够得到满意的结果。 (2) 确定性(definiteness):算法中的每一个步骤都必须有明确的定义,不允许有模棱两可的解释和多义性。 ⑶有穷性(finiteness):算法必需在有限时间内做完,即算法必需能在执行有限个步骤之后终止。 (4)拥有足够的情报:要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时,此算法才最有效的;而当提供的情报不够时,算法可能无效。 2 算法的基本要素 (1) 算法中对数据的运算和操作:每个算法实际上是按解题要求从环境能进行的所 有操作中选择合适的操作所组成的一组指令序列。计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合,称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列在一般的计算机系统中,基本的运算和操作有以下 4 类: ①算术运算:主要包括加、减、乘、除等运算; ②逻辑运算:主要包括“与” 、“或”、“非”等运算; ③关系运算:主要包括“大于” 、“小于”、“等于”、“不等于”等运算; ④数据传输:主要包括赋值、输入、输出等操作。 (2) 算法的控制结构:一个算法的功能不仅仅取决于所选用的操作,而且还与各操 作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。算法的控制结构给出了算法的基本框架,它不仅决定了算法中各操作的执行顺序,而且 也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S 结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3 种基本控制结构组合而成。 (3) 算法设计的基本方法 计算机算法不同于人工处理的方法,下面是工程上常用的几种算法设计,在实际应用时,各种方法之间往往存在着一定的联系。 (1) 列举法 列举法是计算机算法中的一个基础算法。列举法的基本思想是,根据提出的问题,列举所有可能的情况,并用问题中给定的条件检验哪些是需要的,哪些是不需要的。 列举法的特点是算法比较简单。但当列举的可能情况较多时,执行列举算法的工作量将会很大。因此,在用列举法设计算法时,使方案优化,尽量减少运算工作量,是应该重点注意的。 (2) 归纳法 归纳法的基本思想是,通过列举少量的特殊情况,经过分析,最后找出一般的关系。从 本质上讲,归纳就是通过观察一些简单而特殊的情况,最后总结出一般性的结论。 (3) 递推递推是指从已知的初始条件出发,逐次推出所要求的各中间结果和最后结果。其中初始条件或是问题本身已经给定,或是通过对问题的分析与化简而确定。递推本质上也属于归纳法,工程上许多递推关系式实际上是通过对实际问题的分析与归纳而得到的,因此,递推 关系式往往是归纳的结果。对于数值型的递推算法必须要注意数值计算的稳定性问题。

整理好的超完整计算机二级公共基础知识

第1章数据结构与算法 经过对部分考生的调查以及对近年真题的总结分析,笔试部分经常考查的是算法复杂度、数据结构的概念、栈、二叉树的遍历、二分法查找,读者应对此部分进行重点学习。 详细重点学习知识点: 1.算法的概念、算法时间复杂度及空间复杂度的概念 2.数据结构的定义、数据逻辑结构及物理结构的定义 3.栈的定义及其运算、线性链表的存储方式 4.树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历 5.二分查找法 6.冒泡排序法 1.1算法 考点1 算法的基本概念 考试链接: 考点1在笔试考试中考核的几率为30%,主要是以填空题的形式出现,分值为2分,此考点为识记内容,读者还应该了解算法中对数据的基本运算。 计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。 1.算法的基本特征:可行性、确定性、有穷性、拥有足够的情报。 2.算法的基本要素: (1)算法中对数据的运算和操作 基本的运算和操作有以下4类:算术运算、逻辑运算、关系运算和数据传输。 (2)算法的控制结构:算法中各操作之间的执行顺序称为算法的控制结构。 描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。 一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。 考点2 算法复杂度 考试链接: 考点2在笔试考试中,是一个经常考查的内容,在笔试考试中出现的几率为70%,主要是以选择的形式出现,分值为2分,此考点为重点识记内容,读者还应该识记算法时间复杂度及空间复杂度的概念。 1.算法的时间复杂度 算法的时间复杂度是指执行算法所需要的计算工作量。 同一个算法用不同的语言实现,或者用不同的编译程序进行编译,或者在不同的计算机上运行,效率均不同。这表明使用绝对的时间单位衡量算法的效率是不合适的。撇开这些与计算机硬件、软件有关的因素,可以认为一个特定算法"运行工作量"的大小,只依赖于问题的规模(通常用整数n表示),它是问题规模的函数。即 算法的工作量=f(n) 2.算法的空间复杂度 算法的空间复杂度是指执行这个算法所需要的内存空间。

整理好的超完整计算机二级公共基础知识

整理好的超完整计算机二级公共基础知识

第1章数据结构与算法 经过对部分考生的调查以及对近年真题的总结分析,笔试部分经常考查的是算法复杂度、数据结构的概念、栈、二叉树的遍历、二分法查找,读者应对此部分进行重点学习。 详细重点学习知识点: 1.算法的概念、算法时间复杂度及空间复杂度的概念 2.数据结构的定义、数据逻辑结构及物理结构的定义 3.栈的定义及其运算、线性链表的存储方式 4.树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历 5.二分查找法 6.冒泡排序法 1.1算法 考点1 算法的基本概念 考试链接: 考点1在笔试考试中考核的几率为30%,主要是以填空题的形式出现,分值为2分,此考点为识记内容,读者还应该了解算法中对数据的基本运算。 计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。 1.算法的基本特征:可行性、确定性、有穷性、拥有足够的情报。 2.算法的基本要素: (1)算法中对数据的运算和操作 基本的运算和操作有以下4类:算术运算、逻辑运算、关系运算和数据传输。 (2)算法的控制结构:算法中各操作之间的执行顺序称为算法的控制结构。 描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。 一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。 考点2 算法复杂度 考试链接: 考点2在笔试考试中,是一个经常考查的内容,在笔试考试中出现的几率为70%,主要是以选择的形式出现,分值为2分,此考点为重点识记内容,读者还应该识记算法时间复杂度及空间复杂度的概念。 1.算法的时间复杂度 算法的时间复杂度是指执行算法所需要的计算工作量。 同一个算法用不同的语言实现,或者用不同的编译程序进行编译,或者在不同的计算机上运行,效率均不同。这表明使用绝对的时间单位衡量算法的效率是不合适的。撇开这些与计算机硬件、软件有关的因素,可以认为一个特定

相关主题
相关文档 最新文档