2026年计算机等级考试公共基础知识库及答案

2026年计算机等级考试公共基础知识库及答案1.数据结构中，线性表的顺序存储与链式存储的本质区别是？顺序存储要求内存连续，可随机访问（时间复杂度O(1)），但插入/删除需移动元素（时间复杂度O(n)）；链式存储内存不连续，通过指针链接，插入/删除只需修改指针（时间复杂度O(1)，若需定位则O(n)），但无法随机访问。2.若栈的输入序列为3,1,4,2,5，不可能的输出序列是？例如5,2,4,1,3不可能。因为5出栈时，1、2、3、4必须已入栈，此时栈内顺序为3（底）→1→4→2→5（顶），5出栈后栈顶是2，下一个出栈应为2，而非4（若4要在2前出栈，需2先出栈，矛盾）。3.完全二叉树有1023个结点，其叶子结点数是多少？完全二叉树中，叶子结点数等于⌈n/2⌉。n=1023为奇数，故叶子结点数为(1023+1)/2=512。4.对长度为n的有序数组进行二分查找，最坏情况下的时间复杂度是？二分查找每次将区间减半，最坏需log₂n次比较，时间复杂度为O(log₂n)。5.冒泡排序在最好情况下（已有序）的比较次数和交换次数分别是？最好情况（正序）只需遍历一次，比较次数为n-1次，交换次数为0次。6.队列的“假溢出”是如何产生的？顺序队列中，队尾指针到达数组末尾时，若队头指针之前有空闲空间，因队尾无法后移导致的空间浪费现象，解决方法是使用循环队列。7.深度为5的满二叉树（根结点深度为1），其叶子结点数是多少？满二叉树第k层有2^(k-1)个结点，深度5的满二叉树叶子结点在第5层，数量为2^(5-1)=16。8.已知某二叉树的前序遍历序列为ABDCE，中序遍历序列为BDAEC，求后序遍历序列。前序根为A，中序中A左侧B、D为左子树，右侧E、C为右子树。左子树前序为BD→根B，中序B左侧无，右侧D→左子树结构B→D（右孩子）。右子树前序为CE→根C，中序C左侧E→E为C左孩子。后序遍历顺序为D→B→E→C→A，即DBECA。9.对关键字序列[5,2,7,1,3]进行直接插入排序（升序），第三趟排序后的序列是？直接插入排序每趟将当前元素插入已排序序列。初始：[5]；第一趟插入2→[2,5]；第二趟插入7→[2,5,7]；第三趟插入1→[1,2,5,7]；第四趟插入3→[1,2,3,5,7]。第三趟后为[1,2,5,7,3]？不，第三趟处理的是第4个元素（索引3，值1），此时已排序序列是[2,5,7]，插入1后变为[1,2,5,7]，原序列变为[1,2,5,7,3]。10.快速排序在平均情况下的时间复杂度是？O(nlog₂n)，最坏情况（已有序或逆序）为O(n²)。11.结构化程序设计的核心原则是？自顶向下、逐步求精、模块化设计，使用顺序、选择、循环三种基本控制结构，避免无条件跳转（如goto）。12.面向对象方法中，“封装”的含义是？将对象的属性（数据）和方法（操作）绑定为一个整体，隐藏内部实现细节，仅通过公共接口对外提供服务。13.继承可分为单继承和多继承，Java语言仅支持哪种？单继承（类只能继承一个父类），但接口可多实现。14.多态的实现机制包括编译时多态和运行时多态，举例说明。编译时多态通过函数重载（同一类中同名不同参数的方法）实现；运行时多态通过子类重写父类的虚函数（如Java中的@Override），运行时根据对象实际类型调用对应方法。15.模块的内聚性越高，耦合性越低，软件质量越好。其中，“功能内聚”是指？模块内所有元素共同完成一个单一功能，缺一不可，是内聚性最高的类型。16.软件生命周期中，“需求分析”阶段的主要任务是？确定软件的功能、性能、数据、界面等要求，提供需求规格说明书（SRS），作为后续设计的依据。17.瀑布模型的主要缺点是？强调阶段间的顺序性和依赖性，缺乏灵活性，后期发现需求错误时修改成本极高。18.黑盒测试与白盒测试的主要区别是？黑盒测试（功能测试）不关注内部代码逻辑，仅根据需求规格验证功能是否正确；白盒测试（结构测试）基于代码结构（如语句、分支、路径）设计测试用例，验证代码逻辑的正确性。19.软件调试的目的是？定位并修复测试中发现的错误（bug），而测试的目的是发现错误。20.敏捷开发的核心实践包括？迭代开发（短周期发布可工作软件）、用户故事（从用户角度描述需求）、每日站会（快速同步进度）、持续集成（频繁合并代码并测试）。21.数据模型的三要素是？数据结构（描述数据的静态特性）、数据操作（如查询、更新）、数据完整性约束（如实体完整性、参照完整性）。22.关系数据库中，“候选键”的定义是？能唯一标识关系中一个元组的最小属性集合（即其任何真子集都不能唯一标识元组）。23.关系R(A,B,C)和S(B,D)进行自然连接，结果包含哪些属性？自然连接会自动匹配相同属性名（B），结果属性为A,B,C,D（去重B）。24.关系模式R(学号,姓名,课程号,成绩,系别,系主任)，存在函数依赖：学号→姓名,系别；系别→系主任；(学号,课程号)→成绩。判断R最高符合第几范式。1NF（属性不可再分）；2NF要求消除非主属性对候选键的部分依赖。候选键是(学号,课程号)，非主属性为姓名、系别、系主任、成绩。姓名、系别仅依赖于学号（候选键的部分），存在部分依赖，故R仅符合1NF。若分解为R1(学号,姓名,系别,系主任)和R2(学号,课程号,成绩)，则R1中系主任传递依赖于学号（学号→系别→系主任），R1符合2NF但不符合3NF；R2符合3NF（无传递依赖）。25.E-R图中，实体、属性、联系的表示符号分别是？实体用矩形，属性用椭圆，联系用菱形，联系与实体间用线段连接，标注联系类型（1:1、1:n、m:n）。26.数据库三级模式结构中，“外模式”是指？用户级模式，是数据库用户（如应用程序）能看见和使用的局部数据的逻辑结构和特征描述，一个数据库可有多外模式。27.数据字典的作用是？对数据流程图（DFD）中各元素（数据项、数据结构、数据流、数据存储、处理逻辑）的详细定义和描述，是需求分析阶段的重要文档。28.事务的ACID特性是指？原子性（Atomicity，操作要么全做要么全不做）、一致性（Consistency，事务执行后数据保持一致状态）、隔离性（Isolation，事务间互不干扰）、持久性（Durability，事务提交后修改永久保存）。29.索引的主要作用是？提高数据查询效率（通过建立属性值到记录的映射），但会增加插入、删除、更新的开销。30.若关系R和S的笛卡尔积有m×n个元组，则R和S分别有多少个元组？R有m个元组，S有n个元组（笛卡尔积是所有可能的元组组合，数量为两关系元组数的乘积）。31.线性链表中，删除指定值的第一个结点，需修改哪些指针？需找到该结点的前驱结点，将前驱的next指针指向该结点的后继结点（若删除的是头结点，需更新头指针）。32.一个具有n个结点的线性表，采用顺序存储时，插入一个元素的平均移动次数是？平均需移动(n-1)/2个元素（插入位置i的概率为1/(n+1)，移动次数为n-i，求和后平均）。33.树的基本遍历方式包括先根遍历、后根遍历，对应的二叉树遍历方式是？树的先根遍历对应二叉树的前序遍历，后根遍历对应二叉树的中序遍历（因树转换为二叉树时，兄弟结点变为右子树）。34.对有序数组[1,3,5,7,9,11,13]进行二分查找，查找元素7时，需要比较几次？第一次中间值为7（索引3），直接找到，比较1次。35.希尔排序的核心思想是？将整个数组分成若干子序列（间隔为增量d），分别进行插入排序，逐步减小增量d（如d=5,3,1），最终对整个数组进行插入排序，利用局部有序提高效率。36.程序设计中，“对象”与“类”的关系是？类是对象的抽象（模板），对象是类的实例（具体实例化结果）。37.面向对象设计的“里氏替换原则”是指？子类可以替换其父类且不影响程序正确性，即子类应保持父类的行为约定。38.软件设计中，“扇入”和“扇出”的含义是？扇入指一个模块被其他模块调用的次数（越高表示复用性越好）；扇出指一个模块直接调用的其他模块数（过大可能导致复杂度高，一般建议3-5）。39.测试用例应包括？输入数据、预期输出，以及测试环境、测试步骤等信息。40.数据库设计的步骤包括？需求分析→概念设计（E-R图）→逻辑设计（转换为关系模式）→物理设计（存储结构、索引设计）→实施与维护。41.关系代数中，“投影”运算的作用是？从关系中选出若干属性列组成新关系（消除重复元组），对应SQL中的SELECT列名。42.若关系模式R满足3NF，则其一定满足？1NF和2NF（3NF是在2NF基础上消除传递函数依赖）。43.E-R图转换为关系模式时，多对多联系（m:n）如何处理？创建一个新的关系模式，包含两个实体的主键和联系的属性，主键为两实体主键的组合。44.数据库管理系统（DBMS）的主要功能包括？数据定义（DDL）、数据操纵（DML）、数据控制（安全性、完整性、并发控制、恢复）、数据库维护。45.栈的典型应用场景包括？函数调用栈、表达式求值（中缀转后缀）、括号匹配、回溯算法。46.队列的典型应用场景包括？操作系统进程调度（FCFS）、网络数据分组缓存、广度优先搜索（BFS）。47.二叉排序树（BST）的定义是？左子树所有结点值小于根结点，右子树所有结点值大于根结点，左右子树也是BST。48.对二叉排序树进行中序遍历，结果是？一个有序序列（升序）。49.哈希表（散列表）的冲突是指？不同关键字通过哈希函数映射到同一存储地址的现象，解决方法有开放定址法（线性探测、二次探测）、链地址法（哈希桶）。50.软件危机的主要表现是？软件需求变更难以应对，开发周期失控，成本超支，质量低下，维护困难。51.结构化分析方法（SA）的主要工具是？数据流程图（DFD）、数据字典（DD）、判定表/判定树。52.面向对象分析（OOA）的核心是？识别问题域中的对象，分析对象间的关系（如关联、继承、依赖），建立对象模型。53.数据库的完整性约束包括？实体完整性（主键非空唯一）、参照完整性（外键要么为空，要么匹配被参照表的主键）、用户定义完整性（如字段取值范围）。54.事务的隔离级别中，“可重复读”能解决哪些问题？解决脏读（读取未提交数据），但可能存在不可重复读（同一事务两次读取结果不同）和幻读（读取到新插入数据）。55.索引分为聚集索引和非聚集索引，区别是？聚集索引决定数据的物理存储顺序（一个表只能有一个），非聚集索引不影响物理顺序（可多个）。56.线性表的链式存储中，头结点的作用是？简化插入/删除操作（尤其是头结点的处理），使所有结点的操作统一。57.图的遍历方式有深度优先搜索（DFS）和广度优先搜索（BFS），分别使用什么