(2025年)计算机二级《公共基础知识》基础习题及答案

(2025年)计算机二级《公共基础知识》基础习题及答案一、数据结构与算法1.若一个栈的输入序列为3,1,4,2,5（元素依次入栈，中间可随时出栈），则以下不可能的输出序列是（）A.3,1,4,2,5B.1,3,2,5,4C.5,2,4,1,3D.4,3,5,2,1答案：C解析：栈的操作遵循后进先出原则。选项C中第一个输出元素是5，意味着1、2、3、4、5需全部入栈后才能出栈5，但此时栈内剩余元素为4、3、2、1（按入栈顺序，5入栈前是2，2入栈前是4，4入栈前是1，1入栈前是3），所以5出栈后下一个出栈元素只能是2（若2未出栈），但2在栈中的位置是5入栈前的次顶元素（栈内顺序为3、1、4、2、5），5出栈后栈顶是2，因此第二个输出应为2，与选项C的“5,2”后续的“4”矛盾（此时栈顶是2，4在2下方，需2出栈后才能出4），故C不可能。2.某二叉树共有35个节点，其中度为2的节点有11个，则该二叉树的叶子节点数为（）答案：25解析：二叉树中，叶子节点数（度为0的节点数）N0与度为2的节点数N2满足N0=N2+1。已知N2=11，故N0=12？此处需重新计算。实际公式为：总节点数N=N0+N1+N2（N1为度1的节点数），且二叉树中边数=总节点数-1=N1+2N2（每个度1节点贡献1条边，度2节点贡献2条边）。联立得：N0=N2+1。本题中N=35，N2=11，代入得N0=11+1=12，则N1=35-12-11=12。但题目未限制N1，故叶子节点数应为12？可能题目数据有误，正确公式为N0=N2+1，因此答案应为12。（注：原解析可能存在笔误，正确计算应为N0=11+1=12）3.对长度为n的线性表进行顺序查找，在最坏情况下的时间复杂度为（）答案：O(n)解析：顺序查找需遍历所有元素，最坏情况需比较n次，时间复杂度为O(n)。4.下列排序算法中，最坏情况下时间复杂度为O(nlogn)的是（）A.冒泡排序B.快速排序C.堆排序D.插入排序答案：C解析：堆排序的最坏、平均、最好时间复杂度均为O(nlogn)；快速排序最坏为O(n²)；冒泡和插入排序最坏为O(n²)。二、程序设计基础5.面向对象方法中，对象的三个基本特性是（）答案：封装、继承、多态解析：封装指将数据和操作绑定；继承指子类继承父类属性和方法；多态指同一操作在不同对象上有不同表现。6.下列不属于结构化程序设计原则的是（）A.自顶向下B.模块化C.多态性D.逐步求精答案：C解析：结构化程序设计原则包括自顶向下、逐步求精、模块化、限制使用goto语句；多态性是面向对象的特性。7.程序的三种基本控制结构是（）答案：顺序结构、选择结构、循环结构解析：任何程序均可由这三种结构组合而成。三、软件工程基础8.软件生命周期中，确定软件系统“做什么”的阶段是（）答案：需求分析解析：需求分析阶段明确用户需求，定义系统功能，解决“做什么”的问题；设计阶段解决“怎么做”。9.软件测试的目的是（）A.发现程序中的错误B.证明程序正确C.优化程序性能D.改善代码结构答案：A解析：测试的目的是尽可能发现错误，而非证明正确性；优化和改善代码是编码或维护阶段的任务。10.黑盒测试法主要依据的是（）A.程序的内部逻辑B.程序的外部功能C.程序的数据结构D.程序的流程控制答案：B解析：黑盒测试不关心内部逻辑，仅根据需求规格说明书测试功能是否满足。四、数据库设计基础11.在E-R图中，用来表示实体的图形是（）A.矩形B.椭圆形C.菱形D.三角形答案：A解析：E-R图中，矩形表示实体，椭圆表示属性，菱形表示联系。12.关系模型中的“元组”对应数据库中的（）答案：行（记录）解析：关系模型中，二维表的行称为元组，列称为属性。13.设有关系R（A,B,C）和S（B,D,E），则R与S的自然连接结果中包含的属性是（）答案：A,B,C,D,E解析：自然连接是在公共属性（B）上的等值连接，结果包含所有不重复的属性，即A、B、C、D、E。14.若关系模式R属于3NF，则R一定属于（）A.1NFB.2NFC.4NFD.BCNF答案：A、B解析：范式级别从低到高为1NF→2NF→3NF→BCNF→4NF，属于3NF的关系必然属于1NF和2NF。15.数据库设计的四个阶段是（）答案：需求分析、概念设计、逻辑设计、物理设计解析：需求分析确定数据需求；概念设计构建E-R模型；逻辑设计将E-R模型转换为关系模型；物理设计确定存储结构和索引。五、综合应用题16.已知某完全二叉树有768个节点，求其叶子节点数。答案：384解析：完全二叉树中，若节点数n为偶数，则叶子节点数为n/2；若n为奇数，叶子节点数为(n+1)/2。本题n=768（偶数），故叶子节点数=768/2=384。17.对序列{5,3,8,4,6,2,7,1}进行冒泡排序（升序），写出第一趟排序后的结果。答案：3,5,4,6,2,7,1,8解析：冒泡排序每趟将最大元素“冒”到末尾。第一趟比较5和3（交换→3,5），5和8（不交换），8和4（交换→3,5,4,8），8和6（交换→3,5,4,6,8），8和2（交换→3,5,4,6,2,8），8和7（交换→3,5,4,6,2,7,8），8和1（交换→3,5,4,6,2,7,1,8）。18.某数据库中有学生表（学号，姓名，年龄，性别）和课程表（课程号，课程名，学分），以及选课表（学号，课程号，成绩）。写出查询“选修了课程号为‘C001’且成绩大于80分的学生姓名”的SQL语句。答案：SELECT姓名FROM学生表WHERE学号IN(SELECT学号FROM选课表WHERE课程号='C001'AND成绩>80);解析：通过子查询获取选修C001且成绩>80的学号，再在学生表中查询对应姓名。19.分析以下程序的时间复杂度：voidfunc(intn){inti=1;while(i<=n){i=i2;}}答案：O(logn)解析：循环中i每次乘以2，设循环次数为k，则2^k≤n→k≤log₂n，时间复杂度为O(logn)。20.已知二叉树的前序遍历序列为ABDGHCEFI，中序遍历序列为GDHBAECIF，画出该二叉树的后序遍历序列。答案：GHDBEIFCA解析：前序首元素为根（A），中序中A左边为左子树（GDHB），右边为右子树（E