国二新增公共基础知识试题

国二新增公共基础知识试题国二新增公共基础知识试题全文共22页，当前为第1页。第1套新增公共基础知识试题国二新增公共基础知识试题全文共22页，当前为第1页。1.下列叙述中正确的是（）。A）有两个指针域的链表一定是二叉树的存储结构B）有多个指针域的链表一定是非线性结构C）有多个指针域的链表有可能是线性结构D）只有一个根结点的数据结构一定是线性结构答案：C【解析】一个非空的数据结构如果满足以下两个条件：有且只有一个根节点；每一个节点最多有一个前件，也最多有一个后件，称为线性结构，称为线性表。双向链表节点有两个指针域，指向前一个节点的指针和指向后一个节点的指针，但它是线性结构，A、B选项错误。树只有一个根节点，但它是一种简单的非线性结构，D选项错误。故只有C选项正确。2.设栈的存储空间为S(1:50)，初始状态为top=0。现经过一系列正常的入栈与退栈操作后，top=30，则栈中的元素个数为（）。A）31B）30C）20D）19答案：B【解析】栈是一种特殊的线性表，它所有的插入与删除都限定在表的同一端进行。入栈运算即在栈顶位置插入一个新元素，退栈运算即取出栈顶元素赋予指定变量。栈为空时，栈顶指针top=0，经过入栈和退栈运算，指针始终指向栈顶元素。初始状态为top=0，当国二新增公共基础知识试题全文共22页，当前为第2页。top=30时，元素依次存储在单元0：29中，个数为30，B选项正确。国二新增公共基础知识试题全文共22页，当前为第2页。3.某二叉树的前序遍历序列为ABCDE，中序遍历序列为CBADE，则后序遍历序列为（）。A）CBADEB）EDABCC）CBEDAD）EDCBA答案：C【解析】二叉树遍历可以分为3种：前序遍历（访问根节点在访问左子树和访问右子树之前）、中序遍历（访问根节点在访问左子树和访问右子树两者之间）、后序遍历（访问根节点在访问左子树和访问右子树之后）。前序序列为ABCDE，可知A为根节点。中序序列为CBADE，可知C和B均为左子树节点，D、E为右子树节点。由前序序列BC，中序序列CB，可知B为根节点，C为B的左子树节点。由前序序列DE，中序序列DE，可知D为根节点，E为D的右子树节点。故后序序列为CBEDA，C选项正确。4.下列排序方法中，最坏情况下时间复杂度（即比较次数）低于O(n2)的是（）。A）快速排序B）希尔排序C）简单插入排序D）冒泡排序答案：B【解析】对长度为n的线性表排序，下表为常用排序方法最坏情况的时间复杂度：方法最坏情况时间冒泡排序O(n2)国二新增公共基础知识试题全文共22页，当前为第3页。简单插入排序国二新增公共基础知识试题全文共22页，当前为第3页。O(n2)简单选择排序O(n2)快速排序O(n2)堆排序O(nlog2n)上表中未包括希尔排序，因为希尔排序的时间效率与所取的增量序列有关，如果增量序列为：d1=n/2,di+1=di/2，在最坏情况下，希尔排序所需要的比较次数为O(n1.5)。最坏情况下，时间复杂度低于O(n2)的排序算法有堆排序和希尔排序。B选项正确。5.将C语言的整数设为整数类I，则下面属于类I的实例的是（）。A）"0x381"B）0.381C）381E-2D）-381答案：D【解析】整数类实例包括：十进制常量用0~9表示，不能以0开头；八进制常量用0~7表示，必须用0开头；十六进制常量用0～9和A～F(a～f)表示，必须以0x或0X开头。A选项是字符串类实例，B选项是浮点数类实例，C选项为科学计数法表示的浮点数类实例，D为整数类实例，故D选项正确。6.某系统结构图如下图所示国二新增公共基础知识试题全文共22页，当前为第4页。国二新增公共基础知识试题全文共22页，当前为第4页。该系统结构图的最大扇入数是A）0B）1C）2D）3答案：C【解析】扇入指的是调用一个给定模块的模块个数。题干中某系统功能3.1模块扇入数均最大为2，其余模块扇入数均为1，故C选项正确。7.下面属于黑盒测试方法的是（）。A）边界值分析法B）基本路径测试C）条件覆盖D）条件-分支覆盖答案：A【解析】黑盒测试完全不考虑程序内部的逻辑结构和处理过程，黑盒测试是在软件接口处进行，检查和验证程序的功能是否符合需求规格说明书的功能说明。常用的黑盒测试方法和技术有：等价类划分法、边界值分析法、错误推测法和因果图等。白盒测试的主要技术有逻辑覆盖测试（语句覆盖、路径覆盖、判断覆盖、条件覆盖）、基本路径测试等，选项B、C、D均为白盒测试方法。A选项正确。国二新增公共基础知识试题全文共22页，当前为第5页。8.下列对数据库的描述中不正确的是（）。国二新增公共基础知识试题全文共22页，当前为第5页。A）数据库中的数据可以共享B）若系统是完全可以控制的，则系统可确保更新时的一致性C）数据库不存在数据冗余D）数据库减少了数据冗余答案：C【解析】数据库中的数据按一定的数据模型组织、描述和存储，具有较小的冗余度、较高的数据独立性和易扩展性，并可为各种用户（应用程序）共享，A选项叙述正确。数据库要有数据库管理员对数据库进行规划、设计、维护和监视，可以保证系统更新时的一致性，B选项叙述正确。数据库只是减少了数据冗余，并不能完全消除数据冗余，D选项叙述正确，C选项叙述错误。故选择C选项。9.每所学校都有一名校长，而每个校长只在一所学校任职，则实体学校和实体校长之间的联系是（）。A）一对一B）一对多C）多对一D）多对多答案：A【解析】实体集之间通过联系来建立联接关系分为三类：一对一联系（1:1）、一对多联系（1:m）、多对多联系（m:n）。每所学校只对应一名校长，每个校长只对应一所学校，故实体学校和实体校长之间的联系是一对一，A选项正确。10.国二新增公共基础知识试题全文共22页，当前为第6页。国二新增公共基础知识试题全文共22页，当前为第6页。A）交B）差C）选择D）并答案：A【解析】交：R∩S结果是既属于R又属于S的记录组成的集合，R∩S得到一个元组，按照属性ABC的顺序是c311，与关系T相同，A选项正确。差：R-S结果是属于R但不属于S的记录组成的集合，R-S得到三个元组，按照属性ABC的顺序是a112、b211、e415，B选项错误。从关系中找出满足给定条件的元组的操作称为选择。这种操作运算是对单个关系进行，不是两个关系之间的运算，C选项错误。并：R∪S是将S中的记录追加到R后面，R∪S得到5个元组，按照属性ABC的顺序是a112、b211、c311、d312、e415，D选项错误。第2套新增公共基础知识试题1.下列叙述中正确的是（）。A）只有一个根结点和一个叶子结点的必定是线性结构B）只有一个根结点的必定是线性结构或二叉树国二新增公共基础知识试题全文共22页，当前为第7页。C）非线性结构可以为空国二新增公共基础知识试题全文共22页，当前为第7页。D）没有根结点的一定是非线性结构答案：C【解析】一个非空的数据结构如果满足以下两个条件：有且只有一个根节点；每一个节点最多有一个前件，也最多有一个后件，称为线性结构。不满足以上两个条件的为非线性结构。只有一个根节点的可以是线性结构、二叉树也可能是普通的树，A、B选项均只满足一个条件，故错误。数据结构为空的时候，不能确定其是线性还是非线性结构，故D选项错误。非线性结构可以为空数据结构，故C选项正确。2.循环队列的存储空间为Q(1:40)，初始状态为front=rear=40。经过一系列正常的入队与退队操作后，front=rear=15，此后又正常地退出了一个元素，则循环队列中的元素个数为（）。A）9B）14C）16D）39答案：D【解析】循环队列是队列的一种顺序存储结构，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。入队运算时，队尾指针进1（即rear+1），然后在rear指针指向的位置插入新元素。当front=rear=15时可知队列空或者队列满，此后又正常地退出了一个元素说明之前队列满，由于满队列里共有40个元素，所以退出一个元素后队列里有39个元素。D选项正确。国二新增公共基础知识试题全文共22页，当前为第8页。3.某二叉树的中序遍历序列为CBADE，后序遍历序列为CBEDA，则前序遍历序列为（）。国二新增公共基础知识试题全文共22页，当前为第8页。A）ABCDEB）CBEDAC）CBADED）EDCBA答案：A【解析】二叉树遍历可以分为3种：前序遍历（访问根节点在访问左子树和访问右子树之前）、中序遍历（访问根节点在访问左子树和访问右子树两者之间）、后序遍历（访问根节点在访问左子树和访问右子树之后）。后序序列为CBEDA，中序序列为CBADE，可知A为根节点，C和B均为左子树节点，D、E为右子树节点。由后序序列CB，中序序列CB，可知B为根节点，C为B的左子树节点。由后序序列ED，中序序列DE，可知D为根节点，E为D的右子树节点。故前序序列为ABCDE，A选项正确。4.下列算法中，最坏情况下时间复杂度为O(nlog2n)的是（）。A）快速排序B）堆排序C）二分查找法D）顺序查找法答案：C【解析】对长度为n的线性表排序时，最坏的情况下，快速排序的时间复杂度为O(n2)，堆排序的时间复杂度为O(nlog2n)。对于长度为n的线性表进行顺序查找，最坏的情况下，查找次数为n。对于长度为n的有序线性表进行二分法查找，最坏的情况下，查找次数为log2n。故C选项正确。5.下面不属于结构化程序设计原则的是（）。A）自顶向下B）模块化C）逐步求精D）可封装国二新增公共基础知识试题全文共22页，当前为第9页。答案：D国二新增公共基础知识试题全文共22页，当前为第9页。【解析】结构化程序设计方法的重要原则是自顶向下、逐步求精、模块化及限制使用goto语句。可封装性是类-对象的特征，故选择D选项。6.下面属于应用软件的是（）。A）数据库管理系统B）Windows7系统C）编辑软件WPSD）安卓(Android）操作系统答案：D【解析】计算机软件按功能分为应用软件、系统软件、支撑软件（或工具软件）。系统软件是管理计算机的资源，提高计算机的使用效率，为用户提供各种服务的软件。应用软件是为了应用于特定的领域而开发的软件。支撑软件是介于系统软件和应用软件之间，协助用户开发软件的工具型软件，其中包括帮助程序人员开发和维护软件产品的工具软件，也包括帮助管理人员控制开发进程和项目管理的工具软件。A、B、D选项均为系统软件，C选项正确。7.在软件设计中（）。A）应遵循高内聚低耦合的原则B）应遵循高耦合低内聚的原则C）模块独立性仅与内聚度相关D）模块内聚与耦合无关答案：A【解析】软件设计中，模块的独立程度可以由两个定性标准度量：内聚性和耦合性。耦合衡量不同模块彼此间互相依赖（连接）的紧密程度。内聚衡量一个模块内部各个元素彼此结合的紧密程度。一般来说，国二新增公共基础知识试题全文共22页，当前为第10页。要求模块之间的耦合尽可能弱，即模块尽可能独立，且要求模块的内聚程度尽可能高。内聚性和耦合性是一个问题的两个方面，耦合性程度弱的模块，其内聚程度一定高。故A选项正确。国二新增公共基础知识试题全文共22页，当前为第10页。8.长期储存在计算机内、有组织的、可共享的大量数据的集合是（）。A）数据库B）数据库系统C）数据文件D）数据库管理系统答案：A【解析】数据库是指长期存储在计算机内的、有组织的、可共享的数据集合。数据库管理系统是数据库的机构，它是一个系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等。数据库系统由如下几部分组成：据库、数据库管理系统、数据库管理员、硬件平台、软件平台，这些构成了一个以数据库管理系统为核心的完整的行实体。A选项正确。9.某工厂生产中使用若干种原材料，原材料置于多个仓库中，并且同样的材料可放在不同的仓库中，则实体材料和实体仓库之间的联系是（）。A）一对一B）多对一C）一对多D）多对多答案：D【解析】实体集之间通过联系来建立联接关系分为三类：一对一联系（1:1）、一对多联系（1:m）、多对多联系（m:n）。一个仓库中可以放多种材料，一种材料可放在多个仓库中，故实体材料和实体仓库之间的联系是多对多，D选项正确。10.国二新增公共基础知识试题全文共22页，当前为第11页。国二新增公共基础知识试题全文共22页，当前为第11页。A）(a,a,2,2)B）(b,e,1,2)C）(c,c,11,4)D）(e,e,6,1)答案：C【解析】表示选择运算，针对元组；为关系交。题目中的表达式要求在关系R中选出符合条件的元组，条件为属性A、B的元素值相同，并且属性D的元素值大于2，符合条件的元组是(cc114)，C选项正确。第3套新增公共基础知识试题1.设顺序表的长度为n。下列算法中，最坏情况下比较次数小于n的是（）。A）寻找最大项B）堆排序C）快速排序D）顺序查找法答案：A【解析】在顺序表中查找最大项，最坏情况比较次数为n-1；顺序国二新增公共基础知识试题全文共22页，当前为第12页。查找法最坏情况下比较次数为n。快速排序在最坏情况下需要进行n(n-1)/2、堆排序需要nlog2n，这两种方法无法确定比较次数是否小于n。故本题答案为A选项。国二新增公共基础知识试题全文共22页，当前为第12页。2.设栈的顺序存储空间为S(1:m)，初始状态为top=m+1。现经过一系列正常的入栈与退栈操作后，top=0，则栈中的元素个数为（）。A）不可能B）m+1C）1D）m答案：A【解析】栈是一种特殊的线性表，它所有的插入与删除都限定在表的同一端进行。入栈运算即在栈顶位置插入一个新元素，退栈运算即取出栈顶元素赋予指定变量。栈为空时，栈顶指针top=0，经过入栈和退栈运算，指针始终指向栈顶元素，栈满时，top=m。初始状态为top=m+1是不可能的。故本题答案为A选项。3.某二叉树的后序遍历序列与中序遍历序列相同，均为ABCDEF，则按层次输出（同一层从左到右）的序列为（）。A）FEDCBAB）CBAFEDC）DEFCBAD）ABCDEF答案：A国二新增公共基础知识试题全文共22页，当前为第13页。【解析】二叉树遍历可以分为3种：前序遍历（访问根结点在访问左子树和访问右子树之前）、中序遍历（访问根结点在访问左子树和访问右子树两者之间）、后序遍历（访问根结点在访问左子树和访问右子树之后）。二叉树的中序遍历序列和后序遍历序列均为ABCDEF，可知该树只有左子树结点，没有右子树结点，F为根结点。中序遍历序列与后序遍历序列相同说明该树只有左子树没有右子树，因此该树有6层，从顶向下从左向右依次为FEDCBA。故本题答案为A选项。国二新增公共基础知识试题全文共22页，当前为第13页。4.循环队列的存储空间为Q(1:200)，初始状态为front=rear=200。经过一系列正常的入队与退队操作后，front=rear=1，则循环队列中的元素个数为（）。A）0或200B）1C）2D）199答案：A【解析】循环队列是队列的一种顺序存储结构，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。入队运算时，队尾指针进1（即rear+1），然后在rear指针指向的位置插入新元素；退队运算时，排头指针进1（即front+1），然后删除front指针指向的位置上的元素。当front=rear=1时可知队列空或者队列满，历此队列里有0个或者200个元素。故本国二新增公共基础知识试题全文共22页，当前为第14页。题答案为A选项。国二新增公共基础知识试题全文共22页，当前为第14页。5.软件设计一般划分为两个阶段，两个阶段依次是（）。A）总体设计（概要设计）和详细设计B）算法设计和数据设计C）界面设计和结构设计D）数据设计和接口设计答案：A【解析】在系统比较复杂的情况下，软件设计阶段可分解成概要设计阶段和详细设计阶段。编写概要设计说明书、详细设计说明书和测试计划初稿，提高评审。故本题答案为A选项。6.结构化程序设计强调（）。A）程序的易读性B）程序的效率C）程序的规模D）程序的可复用性答案：A【解析】由于软件危机的出现，人们开始研究程序设计方法，结构化程序设计的重要原则是顶向下、逐步求精、模块化及限制使用goto语句。这样使程序易于阅读，利于维护。故本题答案为A选项。7.下面不属于系统软件的是（）。A）杀毒软件B）操作系统国二新增公共基础知识试题全文共22页，当前为第15页。C）编译程序国二新增公共基础知识试题全文共22页，当前为第15页。D）数据库管理系统答案：A【解析】软件按功能可分为应用软件、系统软件和支撑软件。应用软件是为了解决特定领域的应用而开发的软件。系统软件是计算机管理自身资源，提高计算机使用效率并服务于其他程序的软件。支撑软件是介于系统软件和应用软件之间，协助用户开发软件的工具性软件。杀毒软件属于应用软件。故本题答案为A选项。8.E-R图中用来表示实体的图形是（）。A）矩形B）三角形C）菱形D）椭圆形答案：A【解析】在E－R图中实体集用矩形表示，属性用椭圆表示，联系用菱形表示。故本题答案为A选项。9.在关系表中，属性值必须是另一个表主键的有效值或空值，这样的属性是（）。A）外键B）候选键C）主键D）以上三项均不是国二新增公共基础知识试题全文共22页，当前为第16页。答案：A国二新增公共基础知识试题全文共22页，当前为第16页。【解析】【解析】二维表中的一行称为元组。候选键（码）是二维表中能唯一标识元组的最小属性集。若一个二维表有多个候选码，则选定其中一个作为主键（码）供用户使用。表M中的某属性集是表N的候选键或者主键，则称该属性集为表M的外键（码）。故本题答案为A选项。10.现有表示患者和医疗的关系如下：P(P#，Pn，Pg，By)，其中P#为患者编号，Pn为患者姓名，Pg为性别，By为出生日期，Tr(P#，D#，Date，Rt)，其中D#为医生编号，Date为就诊日期，Rt为诊断结果。检索在1号医生处就诊且诊断结果为感冒的病人姓名的表达式是（）。答案：A【解析】π表示投影运算，针对属性；σ表示选择运算，针对元组；∧为关系交；∞表示自然连接。首先在Tr表中选择D#为1且就诊且诊断结果为感冒的记录σD#=1∧Rt=’感冒’(Tr)，并检索出这些记录中患者的编号πP#(σD#=1∧Rt=’感冒’(Tr))，检索结果与表P进行自然连接生成中间表πP#(σD#=1∧Rt=’感冒’国二新增公共基础知识试题全文共22页，当前为第17页。(Tr))∞P，最后在中间表中检索患者的姓名πPn(πP#(σD#=1∧Rt=’感冒’(Tr))∞P)。故本题答案为A选项。国二新增公共基础知识试题全文共22页，当前为第17页。第4套新增公共基础知识试题1.设栈的顺序存储空间为S(1:m)，初始状态为top=0。现经过一系列正常的入栈与退栈操作后，top=m+1，则栈中的元素个数为（）。A）不可能B）m+1C）0D）m答案：A【解析】栈是一种特殊的线性表，它所有的插入与删除都限定在表的同一端进行。入栈运算即在栈顶位置插入一个新元素，退栈运算即取出栈顶元素赋予指定变量。栈为空时，栈顶指针top=0，经过入栈和退栈运算，指针始终指向栈顶元素，栈满时，top=m。初始状态为top=m+1是不可能的。故本题答案为A选项。2.下列排序法中，最坏情况下时间复杂度最小的是（）。A）堆排序B）快速排序C）希尔排序D）冒泡排序答案：A【解析】堆排序最坏情况时间下的时间复杂度为O(nlog2n)；希尔国二新增公共基础知识试题全文共22页，当前为第18页。排序最坏情况时间下的时间复杂度为O(n1.5)；快速排序、、冒泡排序最坏情况时间下的时间复杂度为O(n2)。故本题答案为A选项。国二新增公共基础知识试题全文共22页，当前为第18页。3.某二叉树的前序遍历序列与中序遍历序列相同，均为ABCDEF，则按层次输出（同一层从左到右）的序列为（）。A）ABCDEFB）BCDEFAC）FEDCBAD）DEFABC答案：A【解析】二叉树遍历可以分为3种：前序遍历（访问根结点在访问左子树和访问右子树之前）、中序遍历（访问根结点在访问左子树和访问右子树两者之间）、后序遍历（访问根结点在访问左子树和访问右子树之后）。二叉树的中序遍历序列和前序遍历序列均为ABCDEF，可知该树只有右子树结点，没有左子树结点，A为根结点。中序遍历序列与前序遍历序列相同说明该树只有右子树没有左子树，因此该树有6层，从顶向下从左向右依次为ABCDEF。故本题答案为A选项。4.下列叙述中正确的是（）。A）对数据进行压缩存储会降低算法的空间复杂度B）算法的优化主要通过程序的编制技巧来实现C）算法的复杂度与问题的规模无关D）数值型算法只需考虑计算结果的可靠性国二新增公共基础知识试题全文共22页，当前为第19页。答案：A国二新增公共基础知识试题全文共22页，当前为第19页。【解析】算法的空间复杂度指执行这个算法所需要的内存空间。在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。由于在编程时要受到计算机系统运行环境的限制，因此，程序的编制通常不可能优于算法的设计。算法执行时所需要的计算机资源越多算法复杂度越高，因此算法的复杂度和问题规模成正比。算法设计时要考虑算法的复杂度，问题规模越大越是如此。故本题答案为A选项。5.软件需求规格说明的内容应包括（）。A）软件的主要功能B）算法详细设计C）E-R模型D）软件总体结构答案：A【解析】软件需求规格说明应重点描述软件的目标，软件的功能需求、性能需求、外部接口、属性及约束条件等。功能需求是软件需求规格说明，给出软件要执行什么功能的详尽描述。性能需求是指定量的描述软件系统应满足的具体性能需求，即各种软件功能的速度、响应时间、恢复时间。外部接口指软件如何与人、系统的硬件及其他硬件和其他软件进行交互。属性是指与软件有关的质量属性，如正确性、可用性、可靠性、安全性、可维护性等。约束条件包括影响软件实现的各种设计约束，如使用的标准、编程语言、数据库完整性方针、资源国二新增公共基础知识试题全文共22页，当前为第20页。限制、运行环境等方面的要求。故本题答案为A选项。国二新增公共基础知识试题全文共22页，当前为第20页。6.某系统结构图如下图所示（图中n≥5）该系统结构图的宽度是（）。A）nB）3C）2D）1答案：A【解析】系统结构图的宽度指整体控制跨度（横向最大模块数）的表示