1、国家二级 VB机试（公共基础知识）模拟试卷 5及答案与解析 一、选择题 1 下列叙述中正确的是 ( )。 （ A）所谓算法就是计算方法 （ B）程序可以作为算法的一种描述方法 （ C）算法设计只需考虑得到计算结果 （ D）算法设计可以忽略算法的运算时间 2 设数据结构 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）非线性结构 3 下 列叙述中正确的是 ( )。 （ A）在栈中，栈顶指针的动态变化决定栈中元素的个数
2、 （ B）在循环队列中，队尾指针的动态变化决定队列的长度 （ C）在循环链表中，头指针和链尾指针的动态变化决定链表的长度 （ D）在线性链表中，头指针和链尾指针的动态变化决定链表的长度 4 设有栈 S和队列 Q，初始状态均为空。首先依次将 A， B， C， D， E， F入栈，然后从栈中退出三个元素依次入队，再将 X， Y， Z入栈后，将栈中所有元素退出并依次入队，最后将队列中所有元素退出，则退队元素的顺序为 ( )。 （ A） DEFXYZABC （ B） FEDZYXCBA （ C） FEDXYZCBA （ D） DEFZYXABC 5 在线性表的链式存储结构中，其存储空间一般是不连续的，
3、并且 ( )。 （ A）前件结点的存储序号小于后件结点的存储序号 （ B）前件结点的存储序号大于后件结点的存储序号 （ C）前件结点的存储序号可以小于也可以大于后件结点的存储序号 （ D）以上三种说法均不正确 6 某带链的队列初始状态为： front=rear=NULL。经过一系列正常的人队与退队操作后， front=rear=10。该队列中的元素个数 为 ( )。 （ A） 0 （ B） 1 （ C） 1或 0 （ D）不确定 7 度为 3的一棵树共有 30个结点，其中度为 3， 1的结点个数分别为 3， 4。则该树中的叶子结点数为 ( )。 （ A） 14 （ B） 15 （ C） 16
4、（ D）不可能有这样的树 8 在具有 2n个结点的完全叉树中，叶子结点个数为 ( )。 （ A） n （ B） n+1 （ C） n-1 （ D） n 2 9 某二叉树的中序遍历序列为 CBADE，后序遍历序列为 CBEDA，则前序遍历序列为 ( )。 （ A） CBADE （ B） CBEDA （ C） ABCDE （ D） EDCBA 10 设二叉树中共有 15个结点，其中的结点值互不相同。如果该二叉树的前序序列与中序序列相同，则该二叉树的深度为 ( )。 （ A） 4 （ B） 6 （ C） 15 （ D）不存在这样的二叉树 11 线性表的长度为 n。在最坏情况下，比较次数为 n-1的算
5、法是 ( )。 （ A）顺序查找 （ B）同时寻找最大项与最小项 （ C）寻找最大项 （ D）有序表的插入 12 下列各组排序法中，最坏情况下比较次数相同的是 ( )。 （ A）简单选择排 序与堆排序 （ B）简单插入排序与希尔排序 （ C）冒泡排序与快速排序 （ D）希尔排序与堆排序 13 结构化程序的三种基本控制结构是 ( )。 （ A）顺序、选择和调用 （ B）过程、子程序和分程序 （ C）顺序、选择和重复 (循环 ) （ D）调用、返回和转移 14 下面对软件描述错误的是 ( )。 （ A）文档是不可执行的 （ B）程序和数据是可执行的 （ C）软件文档是与程序开发、维护和应用无关的资
6、料 （ D）软件是程序、数据及相关文档的集合 15 下列叙述中正确的是 ( )。 （ A）软件过程是软件开发过程 （ B）软件过程是软件维护过程 （ C）软件过程是软件开发过程和软件维护过程 （ D）软件过程是把输入转化为输出的一组彼此相关的资源和活动 16 下面描述中不属于软件需求分析阶段任务的是 ( )。 （ A）撰写软件需求规格说明书 （ B）软件的总体结构设计 （ C）软件的需求分析 （ D）软件的需求评审 17 下列数据流图 (DFD)构造规则中正确的是 ( )。 （ A）子图的输入输出数据流与父图中相关加工的输入输出数据流必须一致 （ B） “数据存储 ”间应有数据 流 （ C）
7、“数据流 ”可不带有数据流名 （ D）父图子图是指任意上下层的两个数据流图 18 某系统结构图如下图所示 (图中 n5) 该系统结构图的宽度是 ( )。 （ A） n （ B） 3 （ C） 2 （ D） 1 19 下面不能作为软件设计工具的是 ( )。 （ A） PAD图 （ B）程序流程图 （ C）数据流程图 (DFD图 ) （ D）总体结构图 20 使用自盒测试方法时，设计测试用例应根据 ( )。 （ A）程序的内部逻辑 （ B）程序的复杂结构 （ C）程序的功能 （ D）使用说明书 21 数据库 (DB)、数据库系统 (DBS)和数据库管理系统 (DBMS)之间的关系是 ( )。 （
8、A） DBS就是 DB，也就是 DBMS （ B） DBS包括 DB和 DBMS （ C） DB包括 DBS和 DBMS （ D） DBMS包括 DB和 DBS 22 下列叙述中正确的是 ( )。 （ A）数据库系统避免了一切冗余 （ B）数据库系统减少了数据冗余 （ C）数据库系统中数据的一致性是指数据类型一致 （ D）数据库系统比文件系统能管理更多的数据 23 将数据库的结构划分成多个层次，是为了提高数据库的 ( )。 （ A）管理规范性 （ B）数据处理并发性 （ C）逻辑独立性和物理独立性 （ D）数据共享 24 建立表示学生选修课程活动的实体联系模型，其中的两个实体分别是 ( )。
9、（ A）学生和学号 （ B）课程和课程号 （ C）课程和成绩 （ D）学生和课程 25 ER图中用来表示实体的图形是 ( )。 （ A）菱形 （ B）三角形 （ C）矩形 （ D）椭圆形 26 下列叙述中正确的是 ( )。 （ A）关系模式的候选关键字只能有 1个 （ B）关系模式的候选关键字可以有 1个或多 个 （ C）关系模式可以没有候选关键字 （ D）关系模式必须有 2个以上的候选关键字 27 关系 R经过运算 A=B C 4 D 3(R)的结果为 ( )。 （ A） (a， a， 2， 4) （ B） (e， e， 6， 1) （ C） (c， e， 11， 4) （ D） (a， a
10、， 2， 4)和 (e， e， 6， 1) 28 有三个关系 R， S和 T如下图所示：则由关系 R和 S得到关系 T的运算是( )。 （ A）交 （ B）并 （ C）投影 （ D）自然连接 29 在关系数据库设计中，关系模式设计属于 ( )。 （ A）物理设计 （ B）需求分析 （ C）概念设计 （ D）逻辑设计 30 定义学生、教师和课程的关系模式 S(S#， Sn， Sd， Dc， Sa)(其属性分别为学号、姓名、所在系、所在系的系主任、年龄 )； C(C#， Cn， P#)(其属性分别为课程号、课程名、先修课 )； SC(S#， C#， G)(其属性分别为学号、课程号和成绩 )，则该关
11、系为 ( )。 （ A）第一范式 （ B）第二范式 （ C）第三范式 （ D） BCNF范式 31 设有课程关系模式如下： R(C#， Cn， T， Ta)(其中 C#为课程号， Cn为课程名，T为教师名， Ta为教师地址 )并且假定不同课程号可以有相同的课程名，每个课程号下只有一位任课教师，但每位教师可以有多门课程。该关系模式可进一步规范化为 ( )。 （ A） R1(C#， Cn， T)， R2(T， Ta) （ B） R1(C#， Cn)， R2(T， Ta) （ C） R1(C#， Cn， Ta)， R2(T， Ta) （ D） R1(C#， T)， R2(T， Ta) 国家二级 VB
12、机试（公共基础知识）模拟试卷 5答案与解析 一、选择题 1 【正确答案】 B 【试题解析】 算法是指对解题方案的准确而完整的描述，算法不等于数学上 的计算方法，也不等于程序。算法设计需要考虑可行性、确定性、有穷性与足够的情报，不能只考虑计算结果。算法设计有穷性是指操作步骤有限且能在有限时间内完成，如果一个算法执行耗费的时间太长，即使最终得出了正确结果，也是没有意义的。算法在实现时需要用具体的程序设计语言描述，所以程序可以作为算法的一种描述方法。 【知识模块】 公共基础知识 2 【正确答案】 A 【试题解析】 数据的逻辑结构有两个要素：一是数据元素的集合，通常记为 D；二是 D上的关系，它反映了
13、 D中各数据元素之间的前后件关系，通常记为 R。即一 个数据结构可以表示成 B=(D， R)。其中 B表示数据结构。为了反映 D中各数据元素之间的前后件关系，一般用二元组来表示。例如，假设 a与 b是 D中的两个数据，则二元组 (a， b)表示 a是 b的前件， b是 a的后件。本题中 R中的根结点为 f，元素顺序为 facedb ，满足线性结构的条件。 【知识模块】 公共基础知识 3 【正确答案】 A 【试题解析】 在栈中，通常用指针 top来指示栈顶的位置，用指针 bottom指向栈底。栈顶指针 top动态反应了栈中元素的变化情况。在循环队列中，队头指针和队尾指针的动态 变化决定队列的长度
14、。链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致，故头指针和尾指针或栈顶指针无法决定链表长度。 【知识模块】 公共基础知识 4 【正确答案】 B 【试题解析】 栈是一种特殊的线性表，它所有的插入与删除都限定在表的同一端进行。队列是指允许在一端进行插入，而在另一端进行删除的线性表。将 A， B，C， D， E， F入栈后，栈中元素为 ABCDEF，退出三个元素入队，队列元素为FED，将 X， Y， Z入栈后栈中元素为 ABCXYZ，退栈全部人队 后，队列元素为FEDZYXCBA。 【知识模块】 公共基础知识 5 【正确答案】 C 【试题解析】
15、在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致，因此前件结点的存储序号与后件结点的存储序号之间不存在大小关系。 【知识模块】 公共基础知识 6 【正确答案】 B 【试题解析】 带链队列空时，头指针和尾指针都为 NULL；队列中只有一个元素时，头指针和尾指针都指向这个元素。 【知识模块】 公共基础知识 7 【正确答案】 B 【试题解析】 设叶子结点数为 n，则度为 2的结点数为 30-3-4-n=23-n，根据树中的结点数 =树中所有结点的度之和 +1，得 33+2(23-n)+14+0n+1=30，则n=15。 【知识模块】 公共基
16、础知识 8 【正确答案】 A 【试题解析】 由二叉树的定义可知，树中必定存在度为 0的结点和度为 2的结点，设度为 0结点有 a个，根据度为 0的结点 (即叶子结点 )总比度为 2的结点多一个，得度为 2的结点有 a-1个。再根据完全二叉树的定义，度为 1的结点有 0个或1个，假 设度 1结点为 0个， a+0+a-1=2n，得 2a=2n-1，由于结点个数必须为整数，假设不成立；当度为 1的结点为 1个时， a+1+a-1=2n，得 a=n，即叶子结点个数为 n。 【知识模块】 公共基础知识 9 【正确答案】 C 【试题解析】 二叉树的后序遍历序列为 CBEDA，由于后序遍历最后访问根结点，
17、可以确定该二叉树的根结点是 A。再由中序遍历序列为 CBADE，可以得到子序列 (CB)一定在左子树中，子序列 (DE)一定在右子树中。结点 C、 B在中序序列和后序序列中顺序未变，说明结点 B是结点 C的父结点； 结点 D、 E在中序序列和后序序列中顺序相反，说明结点 D是结点 E的父结点。因此该二叉树的前序遍历序列为 ABCDE。 【知识模块】 公共基础知识 10 【正确答案】 C 【试题解析】 在具有 n个结点的二叉树中，如果各结点值互不相同，若该二叉树的前序序列与中序序列相同，则说明该二叉树只有右子树，左子树为空，二叉树的深度为 n；若该二叉树的后序序列与中序序列相同，则说明该二叉树只
18、有左子树，右子树为空，二叉树的深度为 n。故本题中二叉树的深度为 15。 【知识模块】 公共基础知识 11 【正确答案】 C 【试题解析】 顺序查找要逐个查看所有元素，会比较 n次。在最坏情况下，寻找最大项无论如何需要查看表中的所有元素， n个元素比较次数为 n-1。同时寻找最大项和最小项，需要为判断较大值和较小值分别进行比较，会有更多的比较次数。有序表的插入最坏情况下是插入到表中的最后一个元素的后面位置，则会比较 n次。 【知识模块】 公共基础知识 12 【正确答案】 C 【试题解析】 对于长度为 n的线性表，最坏情况下查找或排序的次数如下表：【知识模块】 公共基础知识 13 【正确答案】
19、C 【试题解析】 1966年 Boehm和 Jacopini证明了程序设计语言仅仅使用顺序、选择和重复三种基本控制结构就足以表达出各种其他形式结构的程序设计方法。 【知识模块】 公共基础知识 14 【正确答案】 C 【试题解析】 软件是程序、数据及相关文档的集合。程序、数据和相关文档又称为软件的三要素。其中，程序是软件开发人员根据用户需求开发的、用程序设计语言描述的、适合计算机执行的指令 (语句 )序列；数据是使程序能正常操纵信息的数据结构；文档是与程序开发、维护和使用有关的图文资料。可见，软件有两部分 组成：一是机器可执行的程序和数据；二是机器不可执行的文档。 【知识模块】 公共基础知识 1
20、5 【正确答案】 D 【试题解析】 软件过程是把输入转化为输出的一组彼此相关的资源和活动。软件过程是为了获得高质量软件所需要完成的一系列任务的框架，它规定了完成各项任务的工作步骤。软件过程所进行的基本活动主要有软件规格说明、软件开发或软件设计与实线、软件确认、软件演进。在过程结束时，将输入 (用户要求 )转化为输出 (软件产品 )。 【知识模块】 公共基础知识 16 【正确答案】 B 【试题解析 】 软件需求是指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。需求分析阶段的工作可以分为 4个方面：需求获取、需求分析、编写需求规格说明书和需求评审。软件的总体结构设计属于软件设计阶段的
21、任务。 【知识模块】 公共基础知识 17 【正确答案】 A 【试题解析】 数据流图应遵循以下构造规则和注意事项： 对加工处理建立唯一、层次性的编号，且每个加工处理通常要求既有输入又有输出。 数据存储之间不应有数据流。 数据流图的一致性。即输入输出、读写的对应。 父图、子图关系与平衡规则。相 邻两层 DFD之间具有父子关系，子图代表了父图中某个加式的详细描述，父图表示了子图间的接口。子图个数不大于父图中的处理个数。所有子图的输入输出数据流和父图中相应处理的输入输出数据流必须一致。 【知识模块】 公共基础知识 18 【正确答案】 A 【试题解析】 宽度指整体控制跨度 (横向最大模块数 )的表示。本
22、题中第 1层有 1个模块，第二层有 n个模块 (注意 n5)，第 3层有 5个模块，故宽度为 n。 【知识模块】 公共基础知识 19 【正确答案】 C 【试题解析】 软件设计可以使用的工具有总 体结构图、程序流程图、 NS图、PAD图、 PDL。数据流程图 (DFD图 )是需求分析使用的工具。 【知识模块】 公共基础知识 20 【正确答案】 A 【试题解析】 白盒测试又称为结构测试或逻辑驱动测试，它允许测试人员利用程序内部的逻辑结构及有关信息来设计或选择测试用例，对程序所有的逻辑路径进行测试。 【知识模块】 公共基础知识 21 【正确答案】 B 【试题解析】 数据库 (DB)是指长期存储在计算
23、机内的、有组织的、可共享的数据集合；数据库管理系统 (DBMS)是用来管理数据及数据 库的系统；数据库系统 (DBS)是由数据库、数据库管理系统、数据库管理员、硬件等在一起的总称。因此 DBS包括 DB和 DBMS。 【知识模块】 公共基础知识 22 【正确答案】 B 【试题解析】 数据库系统共享性大，冗余度小，但只是减少了冗余，并不是避免一切冗余。数据的一致性是指在系统中同一数据在不同位置的出现应保持相同的值，而不是数据类型的一致。数据库系统比文件系统有更强的管理控制能力，而不是管理更多的数据。 【知识模块】 公共基础知识 23 【正确答案】 C 【试题解析】 数据 库系统通常采用三级模式结
24、构并且提供两级映射功能，其中的外模式模式映射保证了数据库系统具有较高的逻辑独立性，而模式内模式映射保证了数据库系统具有较高的物理独立性。 【知识模块】 公共基础知识 24 【正确答案】 D 【试题解析】 实体是概念世界中的基本单位，是客观存在并可以相互区别的事物。要建立表示学生选修课程活动的实体联系模型，能互相区别并可以联系起来的实体是学生和课程。 【知识模块】 公共基础知识 25 【正确答案】 C 【试题解析】 在 ER图中实体集用矩形表示，矩形 框内写实体名；属性用椭圆表示，并用无向边将其与相应的 “实体 ”或 “联系 ”连接起来；联系用菱形表示，在菱形框内写联系名，并用无向边将其与有关实
25、体连接起来，在无向边旁标上联系的类型 (1： 1、 1： n或 n： n)。 【知识模块】 公共基础知识 26 【正确答案】 B 【试题解析】 在关系模式中凡能唯一标识元组的最小属性集称为该关系的键或码。关系模式中可能有若干个键，它们称为该表的候选码或候选键。关系模式中不能没有候选键。 【知识模块】 公共基础知识 27 【正确答案】 C 【试题解析】 选择 运算是在二维表中选出符合条件的行，形成新的关系的过程。设关系的逻辑条件为 F，则关系 R满足 F的选择运算可写成 F(R)。本题中条件为“A=B C 4 D 3”( 为并且的意思 )，只有 (c， c， 11， 4)满足。 【知识模块】 公
26、共基础知识 28 【正确答案】 D 【试题解析】 自然连接要求两个关系中进行比较的是相同的属性，并且进行等值连接，在结果中还要把重复的属性列去掉。本题属于自然连接，隐含条件是R A=S A。 【知识模块】 公共基础知识 29 【正确答案】 D 【试题解析】 关系数据库设计有需求分析、概念设计、逻辑设计、物理设计、编码、测试、运行、进一步修改等几个阶段。在需求分析阶段形成需求说明书，概念设计阶段形成概念数据模型 (ER模型，作为进一步设计数据库的依据 )，逻辑设计阶段形成逻辑数据模型 (从 ER图向关系模式转换、关系视图设计、模式规范化 )，物理设计阶段形成数据库内部模型 (此时涉及具体软件硬件
27、环境 )。 【知识模块】 公共基础知识 30 【正确答案】 B 【试题解析】 本题中关系 S中的 “学号 ”列可决定 “所在系 ”列， “所在系 ”列又可决定 “所在系的系主任 ”，存在传递函数依赖，不满足第三范式。 【知识模块】 公共基础知识 31 【正确答案】 A 【试题解析】 本题的码为课程号，由于每门课程只有一位任课教师，课程号就可以决定教师名、教师地址。课程号可决定教师名，教师名又决定教师地址，这里有对主属性的传递依赖。可将该关系模式拆分为两个关系模式 R1和 R2，其中 R1包含课程号、课程名、教师名， R2包含教师名、教师地址。其中 R1的主码是课程号， R2的主码为教师名。这样两个表都不会出现对主属性的传递依赖。 【知识模块】 公共基础知识
