公共基础习题

二级公共基础知识新大纲

基本要求

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

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

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

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

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

考试内容

一,基本数据结构与算法

1, 算法的基本概念;算法复杂度的概念和意义(时间复杂度与空间复杂度).

2, 数据结构的定义;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念.

3, 线性表的定义;线性表的顺序存储结构及其插入与 除运算.

4, 栈和队列的定义;栈和队列的顺序存储结构及其基本运算.

5, 线性单链表,双向链表与循环链表的结构及其基本运算.

6, 树的基本概念;二*树的定义及其存储结构;二*树的前序,中序和后序遍历.

7, 顺序查找与二分法查找算法;基本排序算法(交换类排序,选择类排序,插入类排序).

二,程序设计基础

1, 程序设计方法与风格.

2, 结构化程序设计.

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

三,软件工程基础

1, 软件工程基本概念,软件声明周期概念,软件工具与软件开发环境.

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

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

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

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

四,数据库设计基础

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

数据模型,实体练习模型及E-R图,从E-R图导出关系数据模型.

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)用于存储数据元素值,称为数据域;(2)用于存放指针,称为指针域,用于指向前一个或后一个结点.

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

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

线性链表,HEAD称为头指针,HEAD=NULL(或0)称为空表,如果是两指针:左指针(Llink)指向前件结点,右指针(Rlink)指向后件结点.

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

1.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)首先遍历左子树,然后访问遍历右子树,最后访问根结点.

1.7 查找技术

顺序查找的使用情况:

(1)线性表为无序表;

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

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

1.8 排序技术

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

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

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

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

最坏情况需要n(n-1)/2次比较;(2)堆排序法,最坏情况需要O(nlog2n)次比较.第二章程序设计基础

2.1 程序设计设计方法和风格

如何形成良好的程序设计风格

1,源程序文档化; 2,数据说明的方法;

3,语句的结构; 4,输入和输出.

注释分序言性注释和功能性注释,语句结构清晰第一,效率第二.

2.2 结构化程序设计

结构化程序设计方法的四条原则是:1. 自顶向下;2. 逐步求精;3.模块化;4.限制使用goto语句.

结构化程序的基本结构和特点:

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

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

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

2.3 面向对象的程序设计

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

面向对象方法的优点:

(1)与人类习惯的思维方法一致;

(2)稳定性好;

(3)可重用性好;

(4)易于开发大型软件产品;

(5)可维护性好.

对象是面向对象方法中最基本的概念,可以用来表示客观世界中的任何实体,对象是实体的抽象.

面向对象的程序设计方法中的对象是系统中用来描述客观事物的一个实体,是构成系统的一个基本单位,由一组表示其静态特征的属性和它可执行的一组操作组成.

属性即对象所包含的信息,操作描述了对象执行的功能,操作也称为方法或服务.

对象的基本特点:

(1)标识惟一性;

(2)分类性;

(3)多态性;

(4)封装性;

(5)模块独立性好.

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

消息是一个实例与另一个实例之间传递的信息.

消息的组成包括(1)接收消息的对象的名称;(2)消息标识符,也称消息名;(3)零个或多个参数.

继承是指能够直接获得已有的性质和特征,而不必重复定义他们.

继承分单继承和多重继承.单继承指一个类只允许有一个父类,多重继承指一个类允许有多个父类.

多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象.第三章软件工程基础

3.1 软件工程基本概念

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

软件的特点包括:

(1)软件是一种逻辑实体;

(2)软件的生产与硬件不同,它没有明显的制作过程;

(3)软件在运行,使用期间不存在磨损,老化问题;

(4)软件的开发,运行对计算机系统具有依赖性,受计算机系统的限制,这导致了软件移植的问题;

(5)软件复杂性高,成本昂贵;

(6)软件开发涉及诸多的社会因素.

软件按功能分为应用软件,系统软件,支撑软件(或工具软件).

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

软件工程是应用于计算机软件的定义,开发和维护的一整套方法,工具,文档,实践标准和工序.

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

软件工程过程是把软件转化为输出的一组彼此相关的资源和活动,包含4种基本活动:

(1)P――软件规格说明;(2)D――软件开发;

(3)C――软件确认;

(4)A――软件演进.

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

软件生命周期三个阶段:软件定义,软件开发,运行维护,主要活动阶段是:

(1)可行性研究与计划制定;(2)需求分析;(3)软件设计;(4)软件实现;(5)软件测试;(6)运行和维护.

软件工程的目标和与原则:

目标:在给定成本,进度的前提下,开发出具有有效性,可靠性,可理解性,可维护性,可重用性,可适应性,可移植性,可追踪性和可互操作性且满足用户需求的产品.

基本目标:付出较低的开发成本;达到要求的软件功能;取得较好的软件性能;开发软件易于移植;需要较低的费用;能按时完成开发,及时交付使用.

基本原则:抽象,信息隐蔽,模块化,局部化,确定性,一致性,完备性和可验证性.

软件工程的理论和技术性研究的内容主要包括:软件开发技术和软件工程管理.

软件开发技术包括:软件开发方法学,开发过程,开发工具和软件工程环境.

软件工程管理包括:软件管理学,软件工程经济学,软件心理学等内容.

软件管理学包括人员组织,进度安排,质量保证,配置管理,项目计划等.

软件工程原则包括抽象,信息隐蔽,模块化,局部化,确定性,一致性,完备性和可验证性.

3.2 结构化分析方法

结构化方法的核心和基础是结构化程序设计理论.

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

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

结构化分析方法的实质:着眼于数据流,自顶向下,逐层分解,建立系统的处理流程,以数据流图和数据字典为主要工具,建立系统的逻辑模型.

结构化分析的常用工具

(1)数据流图; (2)数据字典; (3)判定树; (4)判定表.

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

数据字典:对所有与系统相关的数据元素的一个有组织的列表,以及精确的,严格的定义,使得用户和系统分析员对于输入,输出,存储成分和中间计算结果有共同的理解.

判定树:从问题定义的文字描述中分清哪些是判定的条件,哪些是判定的结论,根据描述材料中的连接词找出判定条件之间的从属关系,并列关系,选择关系,根据它们构造判定树.

判定表:与判定树相似,当数据流图中的加工要依赖于多个逻辑条件的取值,即完成该加工的一组动作是由于某一组条件取值的组合而引发的,使用判定表描述比较适宜.

数据字典是结构化分析的核心.

软件需求规格说明书的特点:

(1)正确性;(2)无岐义性;(3)完整性;(4)可验证性;(5)一致性;(6)可理解性;(7)可追踪性.

3.3 结构化设计方法

软件设计的基本目标是用比较抽象概括的方式确定目标系统如何完成预定的任务,软件设计是确定系统的物理模型.

软件设计是开发阶段最重要的步骤,是将需求准确地转化为完整的软件产品或系统的唯一途径.

从技术观点来看,软件设计包括软件结构设计,数据设计,接口设计,过程设计.

结构设计:定义软件系统各主要部件之间的关系.

数据设计:将分析时创建的模型转化为数据结构的定义.

接口设计:描述软件内部,软件和协作系统之间以及软件与人之间如何通信.

过程设计:把系统结构部件转换成软件的过程描述.

从工程管理角度来看:概要设计和详细设计.

软件设计的一般过程:软件设计是一个迭代的过程;先进行高层次的结构设计;后进行低层次的过程设计;穿插进行数据设计和接口设计.

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

在程序结构中各模块的内聚性越强,则耦合性越弱.优秀软件应高内聚,低耦合.

软件概要设计的基本任务是:

(1)设计软件系统结构; (2)数据结构及数据库设计;

(3)编写概要设计文档; (4)概要设计文档评审.

模块用一个矩形表示,箭头表示模块间的调用关系.

在结构图中还可以用带注释的箭头表示模块调用过程中来回传递的信息.还可用带实心圆的箭头表示传递的是控制信息,空心圆箭心表示传递的是数据.

结构图的基本形式:基本形式,顺序形式,重复形式,选择形式.

结构图有四种模块类型:传入模块,传出模块,变换模块和协调模块.

典型的数据流类型有两种:变换型和事务型.

变换型系统结构图由输入,中心变换,输出三部分组成.

事务型数据流的特点是:接受一项事务,根据事务处理的特点和性质,选择分派一个适当的处理单元,然后给出结果.

详细设计:是为软件结构图中的每一个模块确定实现算法和局部数据结构,用某种选定的表达工具表示算法和数据结构的细节.

常见的过程设计工具有:图形工具(程序流程图),表格工具(判定表),语言工具(PDL).

3.4 软件测试

软件测试定义:使用人工或自动手段来运行或测定某个系统的过程,其目的在于检验它是否满足规定的需求或是弄清预期结果与实际结果之间的差别.

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

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

静态测试包括代码检查,静态结构分析,代码质量度量.不实际运行软件,主要通过人工进行.

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

白盒测试:在程序内部进行,主要用于完成软件内部操作的验证.主要方法有逻辑覆盖,基本基路径测试.

黑盒测试:主要诊断功能不对或遗漏,界面错误,数据结构或外部数据库访问错误,性能错误,初始化和终止条件错,用于软件确认.主要方法有等价类划分法,边界值分析法,错误推测法,因果图等.

软件测试过程一般按4个步骤进行:单元测试,集成测试,验收测试(确认测试)和系统测试.

3.5 程序的调试

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

程序调试的基本步骤:

(1)错误定位;(2)修改设计和代码,以排除错误;(3)进行回归测试,防止引进新的错误.

软件调试可分表静态调试和动态调试.静态调试主要是指通过人的思维来分析源程序代码和排错,是主要的设计手段,而动态调试是辅助静态调试.主要调试方法有:

(1)强行排错法;(2)回溯法;(3)原因排除法.

4.1 数据库系统的基本概念

数据:实际上就是描述事物的符号记录.

数据的特点:有一定的结构,有型与值之分,如整型,实型,字符型等.而数据的值给出了符合定型的值,如整型值15.

数据库:是数据的集合,具有统一的结构形式并存放于统一的存储介质内,是多种应用数据的集成,并可被各个应用程序共享.

数据库存放数据是按数据所提供的数据模式存放的,具有集成与共享的特点.

数据库管理系统:一种系统软件,负责数据库中的数据组织,数据操纵,数据维护,控制及保护和数据服务等,是数据库的核心.

数据库管理系统功能:

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

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

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

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

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

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

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

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

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

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

数据语言按其使用方式具有两种结构形式:交互式命令(又称自含型或自主型语言)宿主型语言(一般可嵌入某些宿主语言中).

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

数据库系统:由数据库(数据),数据库管理系统(软件),数据库管理员(人员),硬件平台(硬件),软件平台(软件)五个部分构成的运行实体.

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

文件系统阶段:提供了简单的数据共享与数据管理能力,但是它无法提供完整的,统一的,管理和数据共享的能力.

层次数据库与网状数据库系统阶段 :为统一与共享数据提供了有力支撑.

关系数据库系统阶段

数据库系统的基本特点:数据的集成性 ,数据的高共享性与低冗余性 ,数据独立性(物理独立性与逻辑独立性),数据统一管理与控制.

数据库系统的三级模式:

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

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

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

数据库系统的两级映射:

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

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

4.2 数据模型

数据模型的概念:是数据特征的抽象,从抽象层次上描述了系统的静态特征,动态行为和约束条件,为数据库系统的信息表与操作提供一个抽象的框架.描述了数据结构,数据操作及数据约束.

E-R模型的基本概念

(1)实体:现实世界中的事物;(2)属性:事物的特性;(3)联系:现实世界中事物间的关系.实体集的关系有一对一,一对多,多对多的联系.

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

E-R模型的图示法:(1)实体集表示法; (2)属性表法; (3)联系表示法.

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

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

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

从图论上看,网状模型是一个不加任何条件限制的无向图.

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

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

关系中的数据约束:

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

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

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

4.3关系代数

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

关系模型的基本运算:

(1)插入 (2)删除 (3)修改 (4)查询(包括投影,选择,笛卡尔积运算)

4.4 数据库设计与管理

数据库设计是数据应用的核心.

数据库设计的两种方法:

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

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

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

需求分析常用结构析方法和面向对象的方法.结构化分析(简称SA)方法用自顶向下,逐层分解的方式分析系统.用数据流图表达数据和处理过程的关系.对数据库设计来讲,数据字典是进行详细的数据收集和数据分析所获得的主要结果.

数据字典是各类数据描述的集合,包括5个部分:数据项,数据结构,数据流(可以是数据项,也可以是数据结构),数据存储,处理过程.

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

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

(2)视图集成设计法.

设计方法:E-R模型与视图集成.

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

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

关系视图设计:关系视图的设计又称外模式设计.

关系视图的主要作用:

(1)提供数据逻辑独立性;

(2)能适应用户对数据的不同需求;

(3)有一定数据保密功能.

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

数据库管理的内容:

(1)数据库的建立;

(2)数据库的调整;

(3)数据库的重组;

(4)数据库安全性与完整性控制;

(5)数据库的故障恢复;

(6)数据库监控.

附件一: 国家二级基础知识题库及分析

第一套: http://www.chinaNCRE.com博日电脑技术学校二级教研组

(1)栈和队列的共同特点是 D

A)都是先进先出 B)都是先进后出

C)只允许在端点处插入和删除元素 D)没有共同点

解析:栈和队列都是一种特殊的操作受限的线性表,只允许在端点处进行插入和删除.二者的区别是:栈只允许在表的一端进行插入或删除操作,是一种"后进先出"的线性表;而队列只允许在表的一端进行插入操作,在另一端进行删除操作,是一种"先进先出"的线性表.所以没有共同点

(2)已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是 D

A)acbed B)decab

C)deabc D)cedba

解析: 依据后序遍历序列可确定根结点为c;再依据中序遍历序列可知其左子树由deba构成,右子树为空;又由左子树的后序遍历序列可知其根结点为e,由中序遍历序列可知其左子树为d,右子树由ba构成,如下图所示.求得该二叉树的前序遍历序列为选项D).

http://www.chinaNCRE.com博日电脑技术学校二级教研组

(3)链表不具有的特点是 B

A)不必事先估计存储空间 B)可随机访问任一元素

C)插入删除不需要移动元素 D)所需空间与线性表长度成正比

解析: 链表采用的是链式存储结构,它克服了顺序存储结构的缺点:它的结点空间可以动态申请和释放;它的数据元素的逻辑次序靠结点的指针来指示,不需要移动数据元素.但是链式存储结构也有不足之处:① 每个结点中的指针域需额外占用存储空间;② 链式存储结构是一种非随机存储结构.

(4)结构化程序设计的3种结构是 D

A)顺序结构,选择结构,转移结构 B)分支结构,等价结构,循环结构

C)多分支结构,赋值结构,等价结构 D)顺序结构,选择结构,循环结构

解析: 顺序结构,选择结构和循环结构(或重复结构)是结构化程序设计的3种基本结构.

(5)为了提高测试的效率,应该 D

A)随机选取测试数据 B)取一切可能的输入数据作为测试数据

C)在完成编码以后制定软件的测试计划 D)集中对付那些错误群集的程序

解析: 测试的目的是发现软件中的错误.经验表明,程序中存在错误的概率与该程序中已发现的错误数成正比.这一现象说明,为了提高测试效率,测试人员应该集中对付那些错误群集的程序.

(6)算法的时间复杂度是指 C

A)执行算法程序所需要的时间 B)算法程序的长度

C)算法执行过程中所需要的基本运算次数 D)算法程序中的指令条数

解析: 算法的复杂度主要包括算法的时间复杂度和算法的空间复杂度.所谓算法的时间复杂度是指执行算法所需要的计算工作量;算法的空间复杂度一般是指执行这个算法所需要的内存空间.

(7)软件生命周期中所花费用最多的阶段是 D

A)详细设计 B)软件编码

C)软件测试 D)软件维护

解析: 软件生命周期分为软件定义,软件开发及软件运行维护3个阶段.本题中,详细设计,软件编码和软件测试都属于软件开发阶段;维护是软件生命周期的最后一个阶段,也是持续时间最长,花费代价最大的一个阶段,软件工程学的一个目的就是提高软件的可维护性,降低维护的代价.

(8)数据库管理系统DBMS中用来定义模式,内模式和外模式的语言为 C

A)C B)Basic C)DDL D)DML

解析: 选项A),B)显然不合题意.数据定义语言(Data Definition Language,简称DDL)负责数据的模式定义与数据的物理存取构建;数据操纵语言(Data Manipulation Language,简称DML)负责数据的操纵,包括查询及增,删,改等操作.

(9)下列有关数据库的描述,正确的是 C

A)数据库是一个DBF文件 B)数据库是一个关系

C)数据库是一个结构化的数据集合 D)数据库是一组文件

解析: 数据库(Database,简称DB)是数据的集合,它具有统一的结构形式并存放于统一的存储介质内,是多种应用数据的集成,并可被各个应用程序所共享.数据库中的数据具有"集成","共享"之特点.

(10)下列有关数据库的描述,正确的是 D

A)数据处理是将信息转化为数据的过程

B)数据的物理独立性是指当数据的逻辑结构改变时,数据的存储结构不变

C)关系中的每一列称为元组,一个元组就是一个字段

D)如果一个关系中的属性或属性组并非该关系的关键字,但它是另一个关系的关键字,则称其为本关系的外关键字

解析: 数据处理是指将数据转换成信息的过程,故选项A)叙述错误;数据的物理独立性是指数据的物理结构的改变,不会影响数据库的逻辑结构,故选项B)叙述错误;关系中的行称为元组,对应存储文件中的记录,关系中的列称为属性,对应存储文件中的字段,故选项C)叙述错误.

填空题

(1)算法的基本特征是可行性,确定性, 【1】 和拥有足够的情报.答案:有穷性

解析: 算法是指解题方案的准确而完整的描述.它有4个基本特征,分别是可行性,确定性,有穷性和拥有足够的情报.

(2)在长度为n的有序线性表中进行二分查找.最坏的情况下,需要的比较次数为 【2】 .答案:log2n

解析: 对于长度为n的有序线性表,在最坏情况下,二分查找只需要比较log2n次,而顺序查找需要比较n次.

(3)在面向对象的程序设计中,类描述的是具有相似性质的一组 【3】 .答案:对象

解析: 将属性,操作相似的对象归为类,也就是说,类是具有共同属性,共同方法的对象的集合.

(4)通常,将软件产品从提出,实现,使用维护到停止使用退役的过程称为 【4】 .答案:软件生命周期

解析: 软件产品从考虑其概念开始,到该软件产品不能使用为止的整个时期都属于软件生命周期.一般包括可行性研究与需求分析,设计,实现,测试,交付使用以及维护等活动.

(5)数据库管理系统常见的数据模型有层次模型,网状模型和 【5】 3种.答案:关系模型

解析: 数据库管理系统是位于用户与操作系统之间的一层系统管理软件,是一种系统软件,是用户与数据库之间的一个标准接口.其总是基于某种数据模型,可以分为层次模型,网状模型和关系模型.

第二套:

(1)已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历为

A)GEDHFBCA B)DGEBHFCA

C)ABCDEFGH D)ACBFEDHG

解析: 利用前序和中序遍历的方法可以确定二叉树的结构,具体步骤如下:① 前序遍历的第一个结点A为树的根结点;② 中序遍历中A的左边的结点为A的左子树,A右边的结点为A的右子树;③ 再分别对A的左右子树进行上述两步处理,直到每个结点都找到正确的位置.

(2)树是结点的集合,它的根结点数目是

A)有且只有1 B)1或多于1

C)0或1 D)至少2

解析: 树是一个或多个结点组成的有限集合,其中一个特定的结点称为根,其余结点分为若干个不相交的集合.每个集合同时又是一棵树.树有且只有1个根结点.

(3)如果进栈序列为e1,e2,e3,e4,则可能的出栈序列是

A)e3,e1,e4,e2 B)e2,e4,e3,e1

C)e3,e4,e1,e2 D)任意顺序

解析: 由栈"后进先出"的特点可知:A)中e1不可能比e2先出,C)中e3不可能比e4先出,且e1不可能比e2先出,D)中栈是先进后出的,所以不可能是任意顺序.B)中出栈过程如图所示:

(4)在设计程序时,应采纳的原则之一是

A)不限制goto语句的使用 B)减少或取消注解行

C)程序越短越好 D)程序结构应有助于读者理解

解析: 滥用goto 语句将使程序流程无规律,可读性差,因此A)不选;注解行有利于对程序的理解,不应减少或取消,B)也不选;程序的长短要依照实际情况而论,而不是越短越好,C)也不选.

(5)程序设计语言的基本成分是数据成分,运算成分,控制成分和

A)对象成分 B)变量成分

C)语句成分 D)传输成分

解析: 程序设计语言是用于书写计算机程序的语言,其基本成分有以下4种,数据成分:用来描述程序中的数据.运算成分:描述程序中所需的运算.控制成分:用来构造程序的逻辑控制结构.传输成分:定义数据传输成分,如输入输出语言.http://www.chinaNCRE.com博日电脑技术学校二级教研组

(6)下列叙述中,不属于软件需求规格说明书的作用的是

A)便于用户,开发人员进行理解和交流

B)反映出用户问题的结构,可以作为软件开发工作的基础和依据

C)作为确认测试和验收的依据

D)便于开发人员进行需求分析

解析: 软件需求规格说明书(SRS,Software Requirement Specification)是需求分析阶段的最后成果,是软件开发中的重要文档之一.它有以下几个方面的作用:① 便于用户,开发人员进行理解和交流;② 反映出用户问题的结构,可以作为软件开发工作的基础和依据;③ 作为确认测试和验收的依据.

(7)下列不属于软件工程的3个要素的是

A)工具 B)过程 C)方法 D)环境

解析: 软件工程包括3个要素,即方法,工具和过程.方法是完成软件工程项目的技术手段;工具支持软件的开发,管理,文档生成;过程支持软件开发的各个环节的控制,管理.

(8)单个用户使用的数据视图的描述称为

A)外模式 B)概念模式 C)内模式 D)存储模式

解析: 选项A)正确,外模式是用户的数据视图,也就是用户所见到的数据模式;选项B)不正确,全局数据视图的描述称为概念模式,即数据库中全部数据的整体逻辑结构的描述;选项C)不正确,物理存储数据视图的描述称为内模式,即数据库在物理存储方面的描述;选项D)不正确,存储模式即为内模式.

(9)将E-R图转换到关系模式时,实体与联系都可以表示成

A)属性 B)关系 C)键 D)域

解析: 数据库逻辑设计的主要工作是将E-R图转换成指定RDBMS中的关系模式.首先,从E-R图到关系模式的转换是比较直接的,实体与联系都可以表示成关系,E-R图中属性也可以转换成关系的属性.实体集也可以转换成关系.

(10)SQL语言又称为

A)结构化定义语言 B)结构化控制语言

C)结构化查询语言 D)结构化操纵语言

解析: 结构化查询语言(Structured Query Language,简称SQL)是集数据定义,数据操纵和数据控制功能于一体的数据库语言.

http://www.chinaNCRE.com博日电脑技术学校二级教研组

填空题

(1)数据结构分为逻辑结构与存储结构,线性链表属于 【1】 .

解析: 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构;数据的存储结构是指数据的逻辑结构在计算机存储空间中的存放形式.在数据的存储结构中,不仅要存放各数据元素的信息,还需要存放各数据元素之间的前后件关系的信息.

(2)在面向对象方法中,类之间共享属性和操作的机制称为 【2】 .

解析: 类是面向对象语言中必备的程序语言结构,用来实现抽象数据类型.类与类之间的继承关系实现了类之间的共享属性和操作,一个类可以在另一个已定义的类的基础上定义,这样使该类型继承了其超类的属性和方法,当然,也可以定义自己的属性和方法.

(3)耦合和内聚是评价模块独立性的两个主要标准,其中 【3】 反映了模块内各成分之间的联系.

解析: 内聚性是一个模块内部各个元素间彼此结合的紧密程度的度量,内聚是从功能角度来度量模块内的联系;耦合性是模块间互相连接的紧密程度的度量.

4)一个项目具有一个项目主管,一个项目主管可管理多个项目,则实体"项目主管"与实体"项目"的联系属于 【4】 的联系.http://www.chinaNCRE.com博日电脑技术学校二级教研组

解析: 两个实体集间的联系实际上是实体集间的函数关系,这种函数关系可以有3种,即一对一(1:1)的联系,一对多(1:N)或多对一(N:1)的联系和多对多(N:N)的联系.

(5)数据库设计分为以下6个设计阶段:需求分析阶段, 【5】 ,逻辑设计阶段,物理设计阶段,实施阶段,运行和维护阶段.

解析: 数据库设计分为以下6个设计阶段:需求分析阶段,概念设计阶段,逻辑设计阶段,物理设计阶段,实施阶段及数据库运行和维护阶段.

答案: BABDD DDABC

存储结构 继承 内聚 一对多或1:N 概念设计阶段

第三套:

(1)算法的空间复杂度是指

A)算法程序的长度 B)算法程序中的指令条数

C)算法程序所占的存储空间 D)执行过程中所需要的存储空间

解析: 算法的复杂度主要包括算法的时间复杂度和算法的空间复杂度.所谓算法的时间复杂度是指执行算法所需要的计算工作量;算法的空间复杂度一般是指执行这个算法所需要的内存空间.

(2)用链表表示线性表的优点是

A)便于随机存取 B)花费的存储空间较顺序存储少

C)便于插入和删除操作 D)数据元素的物理顺序与逻辑顺序相同

解析: 链式存储结构克服了顺序存储结构的缺点:它的结点空间可以动态申请和释放;它的数据元素的逻辑次序靠结点的指针来指示,不需要移动数据元素.故链式存储结构下的线性表便于插入和删除操作.

(3)数据结构中,与所使用的计算机无关的是数据的

A)存储结构 B)物理结构

C)逻辑结构 D)物理和存储结构

解析: 数据结构概念一般包括3个方面的内容,数据的逻辑结构,存储结构及数据上的运算集合.数据的逻辑结构只抽象的反映数据元素之间的逻辑关系,而不管它在计算机中的存储表示形式.

(4)结构化程序设计主要强调的是

A)程序的规模 B)程序的效率

C)程序设计语言的先进性 D)程序易读性

解析: 结构化程序设计方法的主要原则可以概括为自顶向下,逐步求精,模块化及限制使用goto语句,总的来说可使程序结构良好,易读,易理解,易维护.

(5)软件设计包括软件的结构,数据接口和过程设计,其中软件的过程设计是指

A)模块间的关系 B)系统结构部件转换成软件的过程描述

C)软件层次结构 D)软件开发过程

解析: 软件设计包括软件结构设计,数据设计,接口设计和过程设计.其中结构设计是定义软件系统各主要部件之间的关系;数据设计是将分析时创建的模型转化为数据结构的定义;接口设计是描述软件内部,软件和操作系统之间及软件与人之间如何通信;过程设计则是把系统结构部件转换成软件的过程性描述.

(6)检查软件产品是否符合需求定义的过程称为

A)确认测试 B)集成测试

C)验证测试 D)验收测试

解析: 确认测试的任务是验证软件的功能和性能,以及其他特性是否满足需求规格说明定的各种需求;集成测试的主要目的是发现与接口有关的错误.

(7)数据流图用于抽象描述一个软件的逻辑模型,数据流图由一些特定的图符构成.下列图符名标识的图符不属于数据流图合法图符的是http://www.chinaNCRE.com博日电脑技术学校二级教研组

A)控制流 B)加工

C)数据存储 D)源和潭

解析: 数据流图包括4个方面,即加工(转换)(输入数据经加工变换产生输出),数据流(沿箭头方向传送数据的通道,一般在旁边标注数据流名),存储文件(数据源)(表示处理过程中存放各种数据的文件),源和潭(表示系统和环境的接口,属系统之外的实体).不包括选项中的控制流.

(8)应用数据库的主要目的是

A)解决数据保密问题 B)解决数据完整性问题

C)解决数据共享问题 D)解决数据量大的问题

解析: 数据库中的数据具有"集成"与"共享"的特点,亦即是数据库集中了各种应用的数据,进行统一构造与存储,而使它们可以被不同应用程序所使用,故选项C)正确.

(9)在数据库设计中,将E-R图转换成关系数据模型的过程属于

A)需求分析阶段 B)逻辑设计阶段

C)概念设计阶段 D)物理设计阶段

解析: E-R模型即实体-联系模型,是将现实世界的要求转化成实体,联系,属性等几个基本概念,以及它们之间的两种联接关系.数据库逻辑设计阶段包括以下几个过程:从E-R图向关系模式转换,逻辑模式规范化及调整,实现规范化和RDBMS,以及关系视图设计.

(10)在数据管理技术的发展过程中,经历了人工管理阶段,文件系统阶段和数据库系统阶段.其中数据独立性最高的阶段是

A)数据库系统 B)文件系统

C)人工管理 D)数据项管理

解析: 人工管理阶段是在20世纪50年代中期以前出现的,数据不独立,完全依赖于程序;文件系统是数据库系统发展的初级阶段,数据独立性差;数据库系统具有高度的物理独立性和一定的逻辑独立性.

填空题:

(1)数据的逻辑结构有线性结构和 【1】 两大类.

解析: 数据的逻辑结构有线性结构和非线性结构两大类.

(2)顺序存储方法是把逻辑上相邻的结点存储在物理位置 【2】 的存储单元中.

解析: 常用的存储表示方法有4种,顺序存储,链式存储,索引存储,散列存储.其中,顺序存储方法是把逻辑上相邻的结点存储在物理位置也相邻的存储单元中.

(3)一个类可以从直接或间接的祖先中继承所有属性和方法.采用这个方法提高了软件的 【3】 .

解析: 本题考查了继承的优点:相似的对象可以共享程序代码和数据结构,从而大大减少了程序中的冗余,提高软件的可重用性.

(4)软件工程研究的内容主要包括: 【4】 技术和软件工程管理.

解析: 基于软件工程的目标,软件工程的理论和技术性研究的内容主要包括:软件开发技术和软件工程管理.软件开发技术包括:软件开发方法学,开发过程,开发工具和软件工程环境,其主体内容是软件开发方法学.软件工程管理包括:软件管理学,软件工程经济学,以及软件心理学等内容.

(5)关系操作的特点是 【5】 操作.

解析: 在关系操作中,所有操作对象与操作结果都是关系.而关系定义为元数相同的元组的集合.因此,关系操作的特点是集合操作.

答案: DCCDB AACBA

非相邻结构 相邻 可重用性 软件开发 集合

第四套: http://www.chinaNCRE.com博日电脑技术学校二级教研组

(1)在深度为5的满二叉树中,叶子结点的个数为

A)32 B)31 C)16 D)15

解析: 所谓满二叉树是指这样的一种二叉树:除最后一层外,每一层上的所有结点都有两个叶子结点.这就是说,在满二叉树中,层上的结点数都达到最大值,即在满二叉树的第k层上有2k-1个结点,且深度为m的满二叉树有2m-1个结点.

(2)若某二叉树的前序遍历访问顺序是abdgcefh,中序遍历访问顺序是dgbaechf,则其后序遍历的结点访问顺序是

A)bdgcefha B)gdbecfha

C)bdgaechf D)gdbehfca

解析: 前序遍历的第一个结点a为树的根结点;中序遍历中a的左边的结点为a的左子树,a右边的结点为a的右子树;再分别对a的左右子树进行上述两步处理,直到每个结点都找到正确的位置.

(3)一些重要的程序语言(如C语言和Pascal语言)允许过程的递归调用.而实现递归

调用中的存储分配通常用

A)栈 B)堆 C)数组 D)链表

解析: 一些较流行的程序语言允许过程的递归调用.递归调用就是过程调用本身.递归实现的是:当过程每一次执行后,都能返回到最近一次调用它的过程中.这样各调用点之间形成一种后进先出关系,而栈结构正适合来存储这些调用点.http://www.chinaNCRE.com博日电脑技术学校二级教研组

(4)软件工程的理论和技术性研究的内容主要包括软件开发技术和

A)消除软件危机 B)软件工程管理

C)程序设计自动化 D)实现软件可重用

解析: 软件工程的目标是,在给定的成本,进度的前提下,开发出具有有效性,可靠性,可理解性,可维护性,可重用性,可适应性,可移植性,可追踪性和可互操作性且满足用户需求的产品.基于这一目标,软件工程的理论和技术性研究的内容主要包括:软件开发技术和软件工程管理.

(5)开发软件时对提高开发人员工作效率至关重要的是

A)操作系统的资源管理功能 B)先进的软件开发工具和环境

C)程序人员的数量 D)计算机的并行处理能力

解析: 软件工程鼓励研制和采用各种先进的软件开发方法,工具和环境.工具和环境的使用又进一步提高了软件的开发效率,维护效率和软件质量.

(6)在软件测试设计中,软件测试的主要目的是

A)实验性运行软件 B)证明软件正确

C)找出软件中全部错误 D)发现软件错误而执行程序

解析: 使用人工或自动手段来运行或测定某个系统的过程,其目的在于检验它是否满足规定的需求或是弄清预期结果与实际结果之间的差别.软件测试是为了发现错误而执行程序的过程.测试要以查找错误为中心,而不是为了演示软件的正确功能.

(7)数据处理的最小单位是

A)数据 B)数据元素

C)数据项 D)数据结构

解析: 数据处理的最小单位是数据项;由若干数据项组成数据元素;而数据是指能够被计算机识别,存储和加工处理的信息载体;数据结构是指数据之间的相互关系和数据运算.故正确答案为选项C).

(8)索引属于

A)模式 B)内模式

C)外模式 D)概念模式

解析: 内模式(Internal Schema)又称物理模式(Physical Schema),它给出了数据库物理存储结构与物理存取方法,如数据存储的文件结构,索引,集簇及hash等存取方式与存取路径.

(9)下述关于数据库系统的叙述中正确的是

A)数据库系统减少了数据冗余 B)数据库系统避免了一切冗余

C)数据库系统中数据的一致性是指数据类型一致

D)数据库系统比文件系统能管理更多的数据

解析: 数据库系统的数据具有高共享性和低冗余性,但不能完全避免数据冗余;数据的一致性是指在系统中同一数据的不同出现应保持相同的值.

(10)数据库系统的核心是

A)数据库 B)数据库管理系统

C)模拟模型 D)软件工程

解析: 数据库管理系统(Database Management System,简称DBMS)是数据库的机构,它是一种系统软件,负责数据库中的数据组织,数据操纵,数据维护,控制及保护和数据服务等,数据库管理系统是数据库系统的核心.

http://www.chinaNCRE.com博日电脑技术学校二级教研组

填空题

(1)在树形结构中,树根结点没有 【1】 .

解析: 在树形结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点;每一个结点可以有多个后件,它们都称为该结点的子结点.没有后件的结点称为叶子结点.

(2)Jackson结构化程序设计方法是英国的M.Jackson提出的,它是一种面向 【2】 的设计方法.

解析: 结构化分析方法主要包括:面向数据流的结构化分析方法(SA-Structured analysis),面向数据结构的Jackson方法(JSD-Jackson system development method)和面向数据结构的结构化数据系统开发方法(DSSD-Data structured system development method).

(3)面向对象的模型中,最基本的概念是对象和 【3】 .

解析: 面向对象模型中,最基本的概念是对象和类.对象是现实世界中实体的模型化;将属性集和方法集相同的所有对象组合在一起,可以构成一个类.

(4)软件设计模块化的目的是 【4】 .

解析: 模块化是指解决一个复杂问题时自顶向下逐层把软件系统划分成若干模块的过程,由此分解来降低复杂性.

(5)数据模型按不同应用层次分成3种类型,它们是概念数据模型, 【5】 和物理数据模型.

解析: 数据是现实世界符号的抽象,而数据模型(data model)则是数据特征的抽象,它从抽象层次上描述了系统的静态特征,动态行为和约束行为,为数据库系统的信息表示与操作提供一个抽象的框架.

数据模型按不同的应用层次分成3种类型,它们是概念数据模型(conceptual data model),逻辑数据模型(logic data model),物理数据模型(physical data model).

答案: BDABB DCBBB

前件 数据结构 类 降低复杂性 逻辑数据模型

第五套:

(1)数据结构作为计算机的一门学科,主要研究数据的逻辑结构,对各种数据结构进行的运算,以及

A)数据的存储结构 B)计算方法

C)数据映象 D)逻辑存储

解析: 数据结构是研究数据元素及其之间的相互关系和数据运算的一门学科,它包含3个方面的内容,即数据的逻辑结构,存储结构和数据的运算.

(2)串的长度是

A)串中不同字符的个数 B)串中不同字母的个数

C)串中所含字符的个数且字符个数大于零

D)串中所含字符的个数

解析: 串的长度指的是串中的字符的个数,且其字符个数可以为零.

(3)在计算机中,算法是指

A)加工方法 B)解题方案的准确而完整的描述

C)排序方法 D)查询方法

解析: 计算机算法是指解题方案的准确而完整的描述,它有以下几个基本特征:可行性,确定性,有穷性和拥有足够的情报.

(4)以下不属于对象的基本特点的是

A)分类性 B)多态性

C)继承性 D)封装性

解析: 对象有如下一些基本特点,即标识惟一性,分类性,多态性,封装性和模块独立性.

(5)开发软件所需高成本和产品的低质量之间有着尖锐的矛盾,这种现象称作

A)软件投机 B)软件危机

C)软件工程 D)软件产生

解析: 软件工程概念的出现源自软件危机.所谓软件危机是泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题.总之,可以将软件危机归结为成本,质量,生产率等问题.

(6)下面不属于软件设计原则的是

A)抽象 B)模块化 C)自底向上 D)信息隐蔽

解析: 软件设计遵循软件工程的基本目标和原则,建立了适用于在软件设计中应该遵循的基本原理和与软件设计有关的概念,它们是抽象,模块化,信息隐蔽和数据独立性.自底向上是集成测试中增量测试的一种.

(7)开发大型软件时,产生困难的根本原因是

A)大系统的复杂性 B)人员知识不足

C)客观世界千变万化 D)时间紧,任务重

解析: 软件的显著特点是规模庞大,复杂度超线性增长,在开发大型软件时,要保证高质量,极端复杂困难,不仅涉及技术问题,更重要的是必须要有严格而科学的管理.

(8)下列SQL语句中,用于修改表结构的是

A)ALTER B)CREATE C)UPDATE D)INSERT

解析: SQL语句中凡创建都用CREATE,删除都用DROP,改变用ALTER,再跟类型和名字,附加子句.

(9)数据库,数据库系统和数据库管理系统之间的关系是

A)数据库包括数据库系统和数据库管理系统

B)数据库系统包括数据库和数据库管理系统

C)数据库管理系统包括数据库和数据库系统

D)3者没有明显的包含关系

解析: 数据库系统(Database System,简称DBS)包括数据库(Database,简称DB)和数据库管理系统(Database Management System,简称DBMS).

(10)关系模型允许定义3类数据约束,下列不属于数据约束的是

A)实体完整性约束 B)参照完整性约束

C)域完整性约束 D)用户自定义的完整性约束

解析: 关系模型允许定义3类数据约束,它们是实体完整性约束,参照完整性约束及用户自定义的完整性约束.其中前两种完整性约束由关系数据库系统支持,对于用户自定义的完整性约束,则由关系数据库系统提供完整性约束语言,用户利用该语言给出约束条件,运行时由系统自动检查.

http://www.chinaNCRE.com博日电脑技术学校二级教研组

填空题

(1)长度为n的顺序存储线性表中,当在任何位置上插入一个元素概率都相等时,插入一个元素所需移动元素的平均个数为 【1】 .

解析: 在线性表的任何位置插入一个元素的概率相等,即概率为p=1/(n+1),则插入一个元素时所需移动元素的平均次数为E=(1/(n+1))*0((n+1)*n/2)=n/2.

(2)用树型结构表示实体类型及实体间联系的数据模型称为 【2】 .

解析: 用树型结构表示实体类型及实体间联系的数据模型称为层次模型,用有向图结构表示实体类型及实体间联系的数据模型称为网状模型,用二维表格结构表示实体及其联系的数据模型称为关系模型.

(3)类是一个支持集成的抽象数据类型,而对象是类的 【3】 .

解析: 将属性,操作相似的对象归为类,也就是说,类是具有共同属性,共同方法的对象的集合.所以,类是对象的抽象,对象则是其对应类的一个实例.

(4)数据流图的类型有 【4】 和事务型.

解析: 典型的数据流类型有两种:变换型和事务型.变换型是指信息沿输入通路进入系统,同时由外部形式变换成内部形式,进入系统的信息通过变换中心,经加工处理以后再沿输出通路变换成外部形式离开软件系统;在很多软件应用中,存在某种作业数据流,它可以引发一个或多个处理,这些处理能够完成该作业要求的功能,这种数据流就叫做事务.

(5)当数据的物理结构(存储结构,存取方式等)改变时,不影响数据库的逻辑结构,从而不致引起应用程序的变化,这是指数据的 【5】 .

解析: 数据独立性是数据与程序间的互不依赖性,即数据库中数据独立于应用程序而不依赖于应用程序.也就是说,数据的逻辑结构,存储结构与存取方式的改变不会影响应用程序.数据独立性一般分为物理独立性与逻辑独立性两级.http://www.chinaNCRE.com博日电脑技术学校二级教研组

答案; ADBCB CAABC

n/2 层次模型 实例 变换型 物理独立性

第六套:

(1)假设线性表的长度为n,则在最坏情况下,冒泡排序需要的比较次数为

A)log2n B)n2 C)O(n1.5) D)n(n-1)/2

解析: 假设线性表的长度为n,则在最坏情况下,冒泡排序要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描,需要的比较次数为n(n-1)/2.

(2)算法分析的目的是

A)找出数据结构的合理性 B)找出算法中输入和输出之间的关系

C)分析算法的易懂性和可靠性 D)分析算法的效率以求改进

解析: 算法分析是指对一个算法的运行时间和占用空间做定量的分析,一般计算出相应的数量级,常用时间复杂度和空间复杂度表示.分析算法的目的就是要降低算法的时间复杂度和空间复杂度,提高算法的执行效率.

(3)线性表L=(a1,a2,a3,…ai,…an),下列说法正确的是

A)每个元素都有一个直接前件和直接后件

B)线性表中至少要有一个元素

C)表中诸元素的排列顺序必须是由小到大或由大到小

D)除第一个元素和最后一个元素外,其余每个元素都有一个且只有一个直接前件和直接后件

解析: 线性表可以为空表;第一个元素没有直接前件,最后一个元素没有直接后件;线性表的定义中,元素的排列并没有规定大小顺序.

(4)在单链表中,增加头结点的目的是

A)方便运算的实现 B)使单链表至少有一个结点

C)标识表结点中首结点的位置 D)说明单链表是线性表的链式存储实现

解析: 头结点不仅标识了表中首结点的位置,而且根据单链表(包含头结点)的结构,只要掌握了表头,就能够访问整个链表,因此增加头结点目的是为了便于运算的实现.

(5)软件工程的出现是由于

A)程序设计方法学的影响 B)软件产业化的需要

C)软件危机的出现 D)计算机的发展

解析: 软件工程概念的出现源自于软件危机.为了消除软件危机,通过认真研究解决软件危机的方法,认识到软件工程是使计算机软件走向工程科学的途径,逐步形成了软件工程的概念.

(6)软件开发离不开系统环境资源的支持,其中必要的测试数据属于 D

A)硬件资源 B)通信资源 C)支持软件 D)辅助资源

(7)在数据流图(DFD)中,带有名字的箭头表示

A)模块之间的调用关系 B)程序的组成成分

C)控制程序的执行顺序 D)数据的流向

解析: 数据流相当于一条管道,并有一级数据(信息)流经它.在数据流图中,用标有名字的箭头表示数据流.数据流可以从加工流向加工,也可以从加工流向文件或从文件流向加工,并且可以从外部实体流向系统或从系统流向外部实体.

(8)分布式数据库系统不具有的特点是

A)数据分布性和逻辑整体性 B)位置透明性和复制透明性

C)分布性 D)数据冗余

解析: 分布式数据库系统具有数据分布性,逻辑整体性,位置透明性和复制透明性的特点,其数据也是分布的;但分布式数据库系统中数据经常重复存储,数据也并非必须重复存储,主要视数据的分配模式而定.若分配模式是一对多,即一个片段分配到多个场地存放,则是冗余的数据库,否则是非冗余的数据库.

(9)关系表中的每一横行称为一个

A)元组 B)字段 C)属性 D)码

解析: 关系表中,每一行称为一个元组,对应表中的一条记录;每一列称为表中的一个属性,对应表中的一个字段;在二维表中凡能惟一标识元组的最小属性集称为该表的键或码.

(10)下列数据模型中,具有坚实理论基础的是

A)层次模型 B)网状模型 C)关系模型 D)以上3个都是

解析: 关系模型较之格式化模型(网状模型和层次模型)有以下方面的优点,即数据结构比较简单,具有很高的数据独立性,可以直接处理多对多的联系,以及有坚实的理论基础.

http://www.chinaNCRE.com博日电脑技术学校二级教研组

填空题

(1)在算法正确的前提下,评价一个算法的两个标准是 【1】 .

(2)软件危机出现于60年代末,为了解决软件危机,人们提出了 【3】 的原理来设计软件,这就是软件工程诞生的基础.

(3) 【4】 是数据库设计的核心.

解析: 数据模型是对客观事物及联系的数据描述,它反映了实体内部及实体与实体之间的联系.因此,数据模型是数据库设计的核心.

(4)在关系模型中,把数据看成一个二维表,每一个二维表称为一个 【5】 .

解析: 在关系模型中,把数据看成一个二维表,每一个二维表称为一个关系.表中的每一列称为一个属性,相当于记录中的一个数据项,对属性的命名称为属性名;表中的一行称为一个元组,相当于记录值.

答案: DDDAC DDDAC

时间复杂度和空间复杂度 软件工程学 数据模型 关系

第七套

(1)下列叙述中正确的是

A)线性表是线性结构 B)栈与队列是非线性结构

C)线性链表是非线性结构 D)二叉树是线性结构

解析: 线性表是一种线性结构,数据元素在线性表中的位置只取决于它们自己的序号,即数据元素之间的相对位置是线性的;栈,队列,线性链表实际上也是线性表,故也是线性结构;树是一种简单的非线性结构.

(2)非空的循环单链表head的尾结点(由p所指向),满足

A)p->next==NULL B)p==NULL

C)p->next=head D)p=head

解析: 循环链表就是将链表的最后一个结点指向链表头结点(或第一个结点),即p->next=head.

(3)已知数据表A中每个元素距其最终位置不远,为节省时间,应采用的算法是

A)堆排序 B)直接插入排序

C)快速排序 D)直接选择排序

解析: 当数据表A中每个元素距其最终位置不远,说明数据表A按关键字值基本有序,在待排序序列基本有序的情况下,采用插入排序所用时间最少,故答案为选项B).

(4)对建立良好的程序设计风格,下面描述正确的是

A)程序应简单,清晰,可读性好 B)符号名的命名只要符合语法

C)充分考虑程序的执行效率 D)程序的注释可有可无

解析: 程序设计应该简单易懂,语句构造应该简单直接,不应该为提高效率而把语句复杂化.

(5)下列不属于结构化分析的常用工具的是

A)数据流图 B)数据字典

C)判定树 D)PAD图

解析: 结构化分析的常用工具有数据流图,数据字典,判定树和判定表.而PAD图是常见的过程设计工具中的图形设计.

(6)在软件生产过程中,需求信息的给出是

A)程序员 B)项目管理者

C)软件分析设计人员 D)软件用户

解析: 软件需求是指用户对目标软件系统在功能,行为,性能,设计约束等方面的期望.

(7)下列工具中为需求分析常用工具的是

A)PAD B)PFD

C)N-S D)DFD

解析: 需求分析中的常用工具有PAD,PFD及N-S等,而DFD(数据流图)为结构化分析工具.

(8)NULL是指

A)0 B)空格

C)未知的值或无任何值 D)空字符串

解析: 此题属于记忆性的题目,NULL是指未知的值或无任何值.

(9)数据库的故障恢复一般是由

A)数据流图完成的 B)数据字典完成的

C)DBA完成的 D)PAD图完成的

解析: 一旦数据库中的数据遭受破坏,需要及时进行恢复,RDBMS一般都提供此种功能,并由DBA负责执行故障恢复功能.

(10)下列说法中,不属于数据模型所描述的内容的是

A)数据结构 B)数据操作

C)数据查询 D)数据约束

解析: 数据模型所描述的内容有3个部分,它们是数据结构,数据操作和数据约束.其中,数据模型中的数据结构主要描述数据的类型,内容,性质,以及数据库的联系等;数据操作主要是描述在相应数据结构上的操作类型与操作方式.

http://www.chinaNCRE.com博日电脑技术学校二级教研组

填空题

(1)冒泡排序算法在最好的情况下的元素交换次数为 【1】 .

解析: 根据冒泡排序算法思想可知,若待排序的初始序列为"正序"序列,则只需进行一趟排序,在排序过程中进行n-1次关键字间的比较,且不移动和交换记录,这种情况是冒泡排序的最好情况,故冒泡排序算法在最好的情况下的元素交换次数为0.

(2)在最坏情况下,堆排序需要比较的次数为 【2】 .

(3)若串s="MathTypes",则其子串的数目是 【3】 .

解析: 串s中共有9个字符,由于串中字符各不相同,则其子串中有0个字符的1个(空串),1个字符的9个,2个字符的8个,3个字符的7个,4个字符的6个,5个字符的5个,6个字符的4个,7个字符的3个,8个字符的2个,9个字符的1个,共有1+2+3+4+5+6+7+8+9+1=46.

(4)软件开发环境是全面支持软件开发全过程的 【4】 集合.

(5)关系数据库的关系演算语言是以 【5】 为基础的DML语言.

解析: 关系数据库中的关系演算包括元组关系演算和域关系演算.二者都是由原子公式组成的公式.而这些关系演算都是以数理逻辑中的谓词演算为基础的.

答案: ACBAA DDCCC

0 O(nlog2n) 46 软件工具 谓词演算

第八套:

(1)循环链表的主要优点是

A)不再需要头指针了

B)从表中任一结点出发都能访问到整个链表

C)在进行插入,删除运算时,能更好的保证链表不断开

D)已知某个结点的位置后,能够容易的找到它的直接前件

解析: 循环链表就是将单向链表中最后一个结点的指针指向头结点,使整个链表构成一个环形,这样的结构使得从表中的任一结点出发都能访问到整个链表.

(2)栈底至栈顶依次存放元素A,B,C,D,在第五个元素E入栈前,栈中元素可以出栈,则出栈序列可能是

A)ABCED B)DCBEA

C)DBCEA D)CDABE

解析: 栈操作原则上"后进先出",栈底至栈顶依次存放元素A,B,C,D,则表明这4个元素中D是最后进栈,B,C处于中间,A最早进栈.所以出栈时一定是先出D,再出C,最后出A.

(3)n个顶点的强连通图的边数至少有

A)n-1 B)n(n-1)

C)n D)n+1

解析: 在有向图中,若任意两个顶点都连通,则称该图是强连通图,这样的有向图的形状是环状,因而至少应有n条边.

(4)在结构化程序设计思想提出之前,在程序设计中曾强调程序的效率,现在,与程序的效率相比,人们更重视程序的

A)安全性 B)一致性

C)可理解性 D)合理性

(5)模块独立性是软件模块化所提出的要求,衡量模块独立性的度量标准则是模块的

A)抽象和信息隐蔽 B)局部化和封装化

C)内聚性和耦合性 D)激活机制和控制方法

解析: 模块的独立程序是评价设计好坏的重要度量标准.衡量软件的模块独立性使用耦合性和内聚性两个定性的度量标准.

(6)软件开发的结构化生命周期方法将软件生命周期划分成

A)定义,开发,运行维护 B)设计阶段,编程阶段,测试阶段

C)总体设计,详细设计,编程调试 D)需求分析,功能定义,系统设计

解析: 通常,将软件产品从提出,实现,使用维护到停止使用退役的过程称为软件生命周期.它可以分为软件定义,软件开发及软件运行维护3个阶段.

(7)在软件工程中,白箱测试法可用于测试程序的内部结构.此方法将程序看做是

A)路径的集合 B)循环的集合

C)目标的集合 D)地址的集合

解析: 软件的白盒测试方法是把测试对象看做一个打开的盒子,它允许测试人员利用程序内部的逻辑结构及有关信息,设计或选择测试用例,对程序所有逻辑路径进行测试.

(8)在数据管理技术发展过程中,文件系统与数据库系统的主要区别是数据库系统具有

A)特定的数据模型 B)数据无冗余

C)数据可共享 D)专门的数据管理软件

解析: 在文件系统中,相互独立的记录其内部结构的最简单形式是等长同格式记录的集合,易造成存储空间大量浪费,不方便使用.而在数据库系统中,数据是结构化的,这种结构化要求在描述数据时不仅描述数据本身,还要描述数据间的关系,这正是通过采用特定的数据模型来实现的.

(9)数据库设计包括两个方面的设计内容,它们是

A)概念设计和逻辑设计 B)模式设计和内模式设计

C)内模式设计和物理设计 D)结构特性设计和行为特性设计

(10)实体是信息世界中广泛使用的一个术语,它用于表示

A)有生命的事物 B)无生命的事物

C)实际存在的事物 D)一切事物

解析: 实体是客观存在且可以相互区别的事物.实体可以是具体的对象,如一个学生,也可以是一个抽象的事件,如一次出门旅游等.因此,实体既可以是有生命的事物,也可以是无生命的事物,但它必须是客观存在的,而且可以相互区别.

填空题

(1)常用的黑箱测试有等价分类法, 【1】 ,因果图法和错误推测法4种.

解析: 黑箱测试方法完全不考虑程序的内部结构和内部特征,而只是根据程序功能导出测试用例.常用的黑箱测试有等价分类法,边值分析法,因果图法和错误推测法4种.

(2)测试的目的是暴露错误,评价程序的可靠性;而 【2】 的目的是发现错误的位置并改正错误.

解析: 软件测试的目标是在精心控制的环境下执行程序,以发现程序中的错误,给出程序可靠性的鉴定;调试也称排错,它是一个与测试有联系又有区别的概念.具体来说,测试的目的是暴露错误,评价程序的可靠性,而调试的目的是发现错误的位置,并改正错误.

(3)软件维护活动包括以下几类:改正性维护,适应性维护, 【3】 维护和预防性维护.

解析: 软件维护活动包括以下几类:改正性维护,适应性维护,完善性维护和预防性维护.改正性维护是指在软件交付使用后,为了识别和纠正软件错误,改正软件性能上的缺陷,排除实施中的误使用,应当进行的诊断和改正错误的过程;适应性维护是指为了使软件适应变化,而去修改软件的过程;完善性维护是指为了满足用户对软件提出的新功能与性能要求,需要修改或再开发软件,以扩充软件功能,增强软件性能,改进加工效率,提高软件的可维护性;预防性维护是为了提高软件的可维护性,可靠性等,为以后的进一步改进软件打下良好基础.

(4)在面向对象的设计中,用来请求对象执行某一处理或回答某些信息的要求称为【4】 .

解析: 在面向对象技术中,主要用到对象(object),类(class),方法(method),消息(message),继承(inheritance),封装(encapsulation)等基本概念.其中消息是用来请求对象执行某一处理或回答某些信息的要求.

(5)关键字ASC和DESC分别表示 【5】 的含义.

解析: ASC表示升序排列,DESC表示降序排列,多用在索引定义和SELECT语句中的ORDER子句中.

答案: BBCCC AAAAC

边值分析法 调试 完善性 消息 升序排序和降序排序

第九套: http://www.chinaNCRE.com博日电脑技术学校二级教研组

(1)由两个栈共享一个存储空间的好处是

A)减少存取时间,降低下溢发生的机率 B)节省存储空间,降低上溢发生的机率

C)减少存取时间,降低上溢发生的机率 D)节省存储空间,降低下溢发生的机率

解析: 常常一个程序中要用到多个栈,为了不发生上溢错误,就必须给每个栈分配一个足够大的存储空间.但实际中,很难准确地估计,若每个栈都分配过大的存储空间,势必造成系统空间紧张;若让多个栈共用一个足够大的连续存储空间,则可利用栈的动态特性使他们的存储空间互补.

(2)设有两个串p和q,求q在p中首次出现位置的运算称作

A)连接 B)模式匹配

C)求子串 D)求串长

解析: 子串的定位操作通常称作串的模式匹配,是各种串处理系统中最重要的操作之一,算法的基本思想是:从主串的开始字符起和模式的第一个字符比较,若相等则继续比较后续字符,否则从主串的下一个字符起再重新和模式的字符比较,依次类推,直至模式中的每一个字符依次和主串中的一个连续的字符序列相等,称匹配成功,否则称匹配不成功.

(3)n个顶点的连通图中边的条数至少为

A)0 B)1

C)n-1 D)n

解析: 在无向图(边没有方向性的图)中,若从顶点vi到vj有路径,则称vi和vj是连通的,若该图中任意两个顶点都是连通的,则称该图为连通图.

(4)对象实现了数据和操作的结合,是指对数据和数据的操作进行

A)结合 B)隐藏

C)封装 D)抽象

解析: 对象是由数据及可以对这些数据施加的操作组成的统一体.对象的内部,即处理能力的实行和内部状态,对外是看不见的,这一特性称做对象的封装.

(5)下列叙述中,正确的是

A)软件就是程序清单 B)软件就是存放在计算机中的文件

C)软件应包括程序清单及运行结果 D)软件包括程序和文档

解析: 软件(software)是计算机系统中与硬件相互依存的另一部分,是包括程序,数据及相关文档的完整集合.

(6)软件设计中,有利于提高模块独立性的一个准则是

A)低内聚低耦合 B)低内聚高耦合

C)高内聚低耦合 D)高内聚高耦合

解析: 模块的独立程度是评价设计好坏的重要度量标准.衡量软件的模块独立性使用耦合性和内聚性两个定性的度量标准.一般优秀的软件设计,应尽量做到高内聚,低耦合,即减弱模块之间的耦合性和提高模块内的内聚性,有利于提高模块的独立性.

(7)软件生命周期中花费时间最多的阶段是

A)详细设计 B)软件编码

C)软件测试 D)软件维护

解析: 软件生命周期分为软件定义,软件开发及软件运行维护3个阶段.本题中,详细设计,软件编码和软件测试都属于软件开发阶段;维护是软件生命周期的最后一个阶段,也是持续时间最长,花费代价最大的一个阶段,软件工程学的一个目的就是提高软件的可维护性,降低维护的代价.

(8)下列4项中说法不正确的是

A)数据库减少了数据冗余 B)数据库中的数据可以共享

C)数据库避免了一切数据的重复 D)数据库具有较高的数据独立性

解析: 数据库系统具有以下几个特点,一是数据的集成性,二是数据的高共享性与低冗余性,三是数据的独立性,四是数据统一管理与控制.

(9) 下列4项中,必须进行查询优化的是

A)关系数据库 B)网状数据库

C)层次数据库 D)非关系模型

解析: 关系数据模型诞生之后迅速发展,深受用户喜爱,但关系数据模型也有缺点,其最主要的缺点是由于存取路径对用户透明,查询效率往往不如非关系数据模型,因此为了提高性能,必须对用户的查询请求进行优化.

(10) 最常用的一种基本数据模型是关系数据模型,它的表示应采用

A)树 B)网络

C)图 D)二维表

解析: 关系数据模型用统一的二维表结构表示实体及实体之间的联系(即关系).

填空题

(1)当线性表采用顺序存储结构实现存储时,其主要特点是 【1】 .

解析: 顺序存储结构的主要特点是数据元素按线性表的逻辑次序,依次存放在一组地址连续的存储单元中.在存储单元中各元素的物理位置和逻辑结构中各结点间的相邻关系是一致的.

(2)软件工程的出现是由于 【2】 .

解析: 从20世纪60年代中期到70年代中期,随着计算机应用的日益普及,软件数量急剧膨胀,在程序运行时发现的错误必须设法改正,用户有了新的需求时必须相应的修改程序以适应新的环境.种种软件维护工作耗费惊人的资源,更严重的是许多程序个体化使得程序最终无法维护,"软件危机"就这样出现了.为了更有效的开发与维护软件,新兴了一门软件工程学即软件工程.

(3)单元测试又称模块测试,一般采用 【3】 测试.

解析: 软件测试过程一般按4个步骤进行,即单元测试,集成测试,验收测试和系统测试.单元测试的技术可以采用静态分析和动态测试.对动态测试多采用白盒动态测试为主,辅之以黑盒测试.

(4)数据库恢复是将数据库从 【4】 状态恢复到某一已知的正确状态.

解析: 数据库恢复是将数据库中的数据从错误状态中恢复到某种逻辑一致的状态.如果数据库中包含成功事务提交的结果,则称数据库处于一致性状态.

(5)数据的基本单位是 【5】 .http://www.chinaNCRE.com博日电脑技术学校二级教研组

答案; BBCCD CDCAD

逻辑结构中相邻的结点在存储结构中仍相邻

软件危机的出现 白盒测试法 错误 数据元素

第十套:

(1)线性表若采用链式存储结构时,要求内存中可用存储单元的地址

A)必须是连续的 B)部分地址必须是连续的

C)一定是不连续的 D)连续不连续都可以

解析: 在链式存储结构中,存储数据结构的存储空间可以是连续的,也可以是不连续的,各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致.

(2)在待排序的元素序列基本有序的前提下,效率最高的排序方法是

A)冒泡排序 B)选择排序

C)快速排序 D)归并排序

解析: 从平均时间性能而言,快速排序最佳,其所需时间最少,但快速排序在最坏情况下的时间性能不如堆排序和归并排序.当序列中的记录基本有序或元素个数较少时,冒泡排序和简单选择排序为最佳排序方法,故本题答案应该为选项A).

(3)下列叙述中,错误的是

A)数据的存储结构与数据处理的效率密切相关 B)数据的存储结构与数据处理的效率无关

C)数据的存储结构在计算机中所占的空间不一定是连续的

D)一种数据的逻辑结构可以有多种存储结构

解析: 一般来说,一种数据结构根据需要可以表示成多种存储结构.常用的存储结构有顺序,链接,索引等,而采用不同的存储结构,其数据处理的效率是不同的;一个数据结构中的各数据元素在计算机存储空间中的位置关系与逻辑关系是有可能不同的.

(4)希尔排序属于

A)交换排序 B)归并排序

C)选择排序 D)插入排序

解析: 希尔排序的基本思想是把记录按下标的一定增量分组,对每组记录使用插入排序,随增量的逐渐减小,所分成的组包含的记录越来越多,到增量的值减小到1时,整个数据合成一组,构成一组有序记录,故其属于插入排序方法.

(5)下列叙述中,不属于结构化分析方法的是

A)面向数据流的结构化分析方法 B)面向数据结构的Jackson方法

C)面向数据结构的结构化数据系统开发方法 D)面向对象的分析方法

解析: 常见的需求分析方法有结构化分析方法和面向对象的分析方法两类.其中结构化分析方法又包括面向数据流的结构化分析方法(SA-Structured analysis),面向数据结构的Jackson方法(JSD-Jackson system development method)和面向数据结构的结构化数据系统开发方法(DSSD-Data structured system development method).

(6)详细设计的结果基本决定了最终程序的

A)代码的规模 B)运行速度

C)质量 D)可维护性

解析: 详细设计阶段的根本目标是确定应该怎样具体的实现所要求的系统,但详细设计阶段的任务还不是具体的编写程序,而是要设计出程序的"蓝图",以后程序员将根据这个蓝图写出实际的程序代码,因此,详细设计阶段的结果基本上就决定了最终的程序代码的质量.

(7)下列不属于静态测试方法的是

A)代码检查 B)白盒法

C)静态结构分析 D)代码质量度量

解析: 静态测试包括代码检查,静态结构分析和代码质量度量等.其中白盒测试属于动态测试.

(8)公司中有多个部门和多名职员,每个职员只能属于一个部门,一个部门可以有多名职员,从职员到部门的联系类型是

A)多对多 B)一对一

C)多对一 D)一对多

解析: 现实世界中事物之间的联系在信息世界中反映为实体集之间的联系,实体集间的联系个数不仅可以是单个的也可以是多个的,这种关系可以有下面几种对应:一对一,一对多(多对一)多对多.两个实体集间的联系可以用下图表示:http://www.chinaNCRE.com博日电脑技术学校二级教研组

(9)下列关系运算的叙述中,正确的是

A)投影,选择,连接是从二维表行的方向进行的运算

B)并,交,差是从二维表的列的方向来进行运算

C)投影,选择,连接是从二维表列的方向进行的运算

D)以上3种说法都不对

解析: 在关系模型的数据语言中,一般除了运用常规的集合运算(并,交,差,笛卡尔积等),还定义了一些专门的关系运算,如投影,选择,连接等.前者是将关系(即二维表)看成是元组的集合,这些运算主要是从二维表的行的方向来进行的.后者是从二维表的列的方向来进行运算的.

(10)关系数据库管理系统应能实现的专门的关系运算包括

A)排序,索引,统计 B)选择,投影,连接

C)关联,更新,排序 D)显示,打印,制表

解析: 关系数据库建立在关系数据模型基础上,具有严格的数学理论基础.关系数据库对数据的操作除了包括集合代数的并,差等运算之外,更定义了一组专门的关系运算:连接,选择和投影.关系运算的特点是运算的对象都是表.

填空题

(1)用链表表示线性表的突出优点是 【1】 .

解析: 为了克服顺序表中插入和删除时需要移动大量数据元素的缺点,引入了链式存储结构.链表表示线性表的突出优点是插入和删除操作方便,不必移动数据元素,执行效率高.

(2)子程序通常分为两类: 【2】 和函数,前者是命令的抽象,后者是为了求值.

解析: 当程序之间发生调用关系时,调用命令所在的代码段被称为主程序,被调用的代码段被称为子程序.子程序是对功能的抽象,可分为过程和函数两类,两者的区别是函数是通过函数名来返回值的,而过程只能通过形式参数或对全局变量进行修改以返回值.

(3)软件的 【3】 设计又称为总体结构设计,其主要任务是建立软件系统的总体结构.

(4)对软件是否能达到用户所期望的要求的测试称为 【4】 .

(5)实体之间的联系可以归结为一对一联系,一对多(或多对多)的联系与多对多联系.如果一个学校有许多教师,而一个教师只归属于一个学校,则实体集学校与实体集教师之间的联系属于 【5】 的联系.

答案; DABDD CBCCB

便于插入与删除操作 过程 概要 有效性测试 一对多或1:N

附二:2005年4月2日VB语言\C语言\VFP语言\考试基础知识试题

选择题http://www.chinaNCRE.com博日电脑技术学校二级教研组

(1)数据的存储结构是指 D

A)存储在外存中的数据 B)数据所占的存储空间量

C)数据在计算机中的顺序存储方式 D)数据的逻辑结构中计算机中的表示

(2)下列关于栈的描述中错误的是 B

A)栈是先进后出的线性表 B)栈只能顺序存储

C)栈具有记忆作用 D)对栈的插入与删除操作中,不需要改变栈底指针

(3)对于长度为n的线性表,在最坏情况下,下列各排序法所对应的比较次数中正确的是 D

A)冒泡排序为n/2 B)冒泡排序为n

C)快速排序为n D)快速排序为n(n-1)/2

(4)对长度为n的线性表进行顺序查找,在最坏情况下所需要的比较次数为 C

A)log2n B) n/2

C) n D) n+1

(5)下列对于线性链表的描述中正确的是 A

A)存储空间不一定是连续,且各元素的存储顺序是任意的

B)存储空间不一定是连续,且前件元素一定存储在后件元素的前面

C)存储空间必须连续,且前件元素一定存储在后件元素的前面

D)存储空间必须连续,且各元素的存储顺序是任意的

(6)下列对于软件的描述中正确的是 C

A)软件测试的目的是证明程序是否正确 B)软件测试的目的是使程序运行结果正确

C)软件测试的目的是尽可能多地发现程序中的错误 D)软件测试的目的是使程序符合结构化原则

(7)为了使模块尽可能独立,要求 B

A)模块的内聚程序要尽量高,且各模块间的耦合程序要尽量强

B)模块的内聚程序要尽量高,且各模块间的耦合程序要尽量弱

C)模块的内聚程序要尽量低,且各模块间的耦合程序要尽量弱

D)模块的内聚程序要尽量低,且各模块间的耦合程序要尽量强

(8)下列描述中正确的是 D

A)程序就是软件 B)软件开发不受计算机系统的限制

C)软件既是逻辑实体,又是物理实体 D)软件是程序,数据与相关文档的集合

(9)数据独立性是数据库技术的重要特点之一.所谓数据独立性是指 D

A)数据与程序独立存放 B)不同的数据被存放在不同的文件中

C)不同的数据只能被对应的应用程序所使用 D)以上三种说法都不对

(10)用树形结构表示实体之间联系的模型是 C

A)关系模型 B)网状模型

C)层次模型 D)以上三个都是

填空题(每空2分,共40分)

(1)某二叉树中,度为2的结点有18个,则该二叉树中有 19 个叶子结点.

(2)在面向对象的方法中,类的实例称为 对象 .

(3)诊断和改正程序中错误的工作通常称为 程序调试 .

(4)在关系数据库中,把数据表示成二维表,每一个二维表称为 关系 .

(5)问题处理方案的正确而完整的描述称为 算法