(2025年)全国计算机等级考试(NCRE)二级公共基础知识样题及参考答案

(2025年)全国计算机等级考试(NCRE)二级公共基础知识样题及参考答案一、单项选择题1.某算法的时间复杂度为O(n²)，当输入规模n=100时，执行时间为5ms。若输入规模n=300时，执行时间约为（）。A.15msB.30msC.45msD.450ms2.若一个栈的输入序列为1,2,3,4,5，则不可能的输出序列是（）。A.5,4,3,2,1B.2,3,5,4,1C.3,1,2,4,5D.1,2,3,4,53.已知某二叉树的后序遍历序列为D,E,B,F,C,A，中序遍历序列为D,B,E,A,F,C，则其前序遍历序列为（）。A.A,B,D,E,C,FB.A,C,F,B,D,EC.A,B,E,D,C,FD.A,C,B,D,E,F4.下列关于线性链表的描述中，错误的是（）。A.存储空间不一定连续B.元素的逻辑顺序与物理顺序可能不一致C.可随机访问任意节点D.插入和删除操作不需要移动元素5.对长度为n的有序线性表进行二分查找，最坏情况下的比较次数为（）。A.log₂nB.n/2C.nD.nlog₂n6.结构化程序设计的三种基本控制结构是（）。A.顺序、选择、递归B.顺序、循环、跳转C.顺序、选择、循环D.选择、循环、递归7.面向对象方法中，对象的基本特征不包括（）。A.封装性B.继承性C.多态性D.可移植性8.软件生命周期中，确定软件系统“做什么”的阶段是（）。A.需求分析B.详细设计C.编码D.测试9.下列不属于黑盒测试方法的是（）。A.等价类划分B.边界值分析C.路径覆盖D.错误推测法10.软件调试的目的是（）。A.发现错误B.定位错误原因并纠正C.评估软件质量D.验证软件功能11.在数据库系统中，用户看到的数据视图称为（）。A.概念模式B.外模式C.内模式D.物理模式12.关系模型中，实体集之间的联系用（）表示。A.二维表B.树结构C.图结构D.链表13.设有关系R（A,B,C）和S（B,D），则R与S的自然连接结果中包含的属性是（）。A.A,B,C,DB.BC.A,B,CD.A,C,D14.关系模式R（学号，姓名，课程号，成绩，教师号，教师姓名）中，存在的函数依赖为：学号→姓名，（学号，课程号）→成绩，课程号→教师号，教师号→教师姓名。则R最高满足（）。A.1NFB.2NFC.3NFD.BCNF15.若要从关系中找出满足某个条件的元组，应使用的关系代数运算是（）。A.投影B.选择C.连接D.除二、填空题16.一个队列的初始状态为空，若依次执行入队操作：A,B,C,D，然后执行两次出队操作，再执行入队操作E,F，则队列中的元素为（）（按顺序填写）。17.某完全二叉树有700个节点，其叶子节点数为（）。18.冒泡排序在最好情况下（已有序）的时间复杂度为（）。19.面向对象方法中，类的实例称为（）。20.软件需求规格说明书的核心内容是（）。21.数据库系统的核心是（）。22.关系模型中，能够唯一标识一个元组的属性或属性组称为（）。23.在E-R图中，矩形框表示（），菱形框表示（）。三、简答题24.简述算法的时间复杂度与空间复杂度的定义，并说明两者的关系。25.比较顺序查找与二分查找的适用场景及优缺点。26.什么是面向对象的多态性？举例说明其应用。27.软件测试应遵循哪些基本原则？28.简述数据库设计的主要步骤。参考答案一、单项选择题1.D解析：时间复杂度为O(n²)，执行时间与n²成正比。n=100时，时间t=k×100²=5ms；n=300时，t=k×300²=k×9×100²=9×5=45ms？此处需修正：原题中n=100时t=5ms，k=5/(100²)；n=300时，t=k×300²=5×(300²/100²)=5×9=45ms？但选项中无45ms？原题选项可能设置错误，正确计算应为n=100时t=5ms，n=300时t=5×(300/100)²=5×9=45ms，对应选项C。但可能题目中选项D为450ms是笔误，正确应为C。（注：经核查，正确计算应为n²的比例，故n=300时时间为5×(300/100)²=45ms，选C。可能原题选项D为干扰项，正确选项应为C。）2.C解析：栈的输出序列需满足后进先出原则。选项C中，输出3后，栈内剩余1,2（输入顺序为1,2,3，3出栈后栈顶为2），此时输出1不可能，因为2未出栈时1无法出栈（栈顶是2）。3.A解析：后序遍历最后一个节点是根（A），中序遍历中A左边是左子树（D,B,E），右边是右子树（F,C）。左子树的后序为D,E,B，根为B；中序中B左边是D，右边是E。右子树的后序为F,C，根为C；中序中C左边是F。前序遍历顺序为根→左→右，故前序为A,B,D,E,C,F。4.C解析：线性链表只能顺序访问，无法随机访问（数组可随机访问）。5.A解析：二分查找最坏情况下比较次数为log₂n（向下取整加1），时间复杂度为O(log₂n)。6.C解析：结构化程序设计的三种基本结构是顺序、选择（分支）、循环（重复）。7.D解析：对象的基本特征是封装、继承、多态，可移植性是软件特性，非对象特征。8.A解析：需求分析阶段确定系统“做什么”，详细设计确定“怎么做”。9.C解析：路径覆盖是白盒测试（基于代码逻辑），其他是黑盒测试（基于功能）。10.B解析：测试发现错误，调试定位并纠正错误。11.B解析：外模式是用户视图，概念模式是全局逻辑结构，内模式是物理存储结构。12.A解析：关系模型用二维表表示实体及联系。13.A解析：自然连接在公共属性B上进行等值连接，结果包含所有不重复的属性（A,B,C,D）。14.B解析：R的主码是（学号，课程号）。存在部分依赖：学号→姓名（非主属性姓名部分依赖于主码），因此不满足2NF？不，2NF要求消除非主属性对主码的部分依赖。主码是（学号，课程号），姓名仅依赖于学号（主码的一部分），属于部分依赖，因此R不满足2NF，最高满足1NF？此处需重新分析：函数依赖：（学号，课程号）→成绩（完全依赖）学号→姓名（部分依赖，因为姓名仅依赖于学号，主码的一部分）课程号→教师号（部分依赖，教师号仅依赖于课程号，主码的一部分）教师号→教师姓名（传递依赖）因此，R存在非主属性（姓名、教师号、教师姓名）对主码的部分依赖，不满足2NF，最高满足1NF。但原题选项可能设置为2NF，需确认。（正确结论：若存在部分依赖，则不满足2NF，故R最高满足1NF，选A。）15.B解析：选择运算是从关系中选取满足条件的元组（行），投影是选取列。二、填空题16.C,D,E,F解析：队列先进先出。入队A,B,C,D后，队列是[A,B,C,D]；两次出队后，队首A,B出队，剩余[C,D]；入队E,F后，队列是[C,D,E,F]。17.350解析：完全二叉树节点数n=700，设深度为k，则2^(k-1)≤700<2^k。计算得k=10（2^9=512，2^10=1024）。前9层有512个节点，第10层有700-512=188个节点。叶子节点数=第9层的叶子数+第10层节点数。第9层最多有2^8=256个节点，其中非叶子节点数为第10层节点数/2（向上取整）=188/2=94。因此第9层的叶子数=256-94=162，总叶子数=162+188=350。18.O(n)解析：冒泡排序最好情况（已有序）只需遍历一次，比较n-1次，时间复杂度O(n)。19.对象解析：类是模板，对象是类的实例。20.软件的功能需求、性能需求及约束条件解析：需求规格说明书需明确系统“做什么”，核心是功能和性能要求。21.数据库管理系统（DBMS）解析：DBMS是数据库系统的核心，负责数据管理。22.主码（主键）解析：主码唯一标识元组，候选码的子集。23.实体；联系解析：E-R图中矩形表示实体，菱形表示联系，椭圆表示属性。三、简答题24.时间复杂度衡量算法执行时间随输入规模增长的变化趋势，通常用大O符号表示；空间复杂度衡量算法执行过程中所需存储空间的变化趋势。两者是算法效率的两个维度，需在时间与空间之间权衡（如哈希表用空间换时间）。25.顺序查找适用于无序或小规模数据，优点是无需预处理，实现简单；缺点是时间复杂度O(n)，效率低。二分查找适用于有序数据，优点是时间复杂度O(log₂n)，效率高；缺点是需数据有序，且仅适用于顺序存储结构（如数组）。26.多态性指不同对象接收相同消息时产生不同行为的特性。例如，图形类（Shape）有子类矩形（Rectangle）和圆形（Circle），它们都重写了draw()方法。当调用Shape对象的draw()方法时，实际执行的是具体子类的draw()实现，体现多态。27.软件测试的基本原则包括：测试应尽早开始并贯穿生命周期；测试用