全国计算机二级公共基础知识考试试题及答案

全国计算机二级公共基础知识考试试题及答案选择题1.下列叙述中正确的是（）A.算法的效率只与问题的规模有关，而与数据的存储结构无关B.算法的时间复杂度是指执行算法所需要的计算工作量C.数据的逻辑结构与存储结构是一一对应的D.算法的时间复杂度与空间复杂度一定相关答案：B解析：算法的效率不仅与问题的规模有关，还与数据的存储结构有关，A选项错误；数据的逻辑结构是指数据元素之间的逻辑关系，而存储结构是指数据在计算机中的存储方式，它们不是一一对应的，C选项错误；算法的时间复杂度和空间复杂度之间没有必然的联系，D选项错误；算法的时间复杂度是指执行算法所需要的计算工作量，B选项正确。2.下列关于栈的叙述中正确的是（）A.栈按“先进先出”组织数据B.栈按“先进后出”组织数据C.只能在栈底插入数据D.不能删除数据答案：B解析：栈是一种特殊的线性表，它遵循“先进后出”（FILO）或“后进先出”（LIFO）的原则，A选项错误，B选项正确；栈只能在栈顶进行插入和删除操作，C、D选项错误。3.一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为（）A.219B.221C.229D.231答案：A解析：根据二叉树的性质：对于任意一棵二叉树，如果其叶子结点数为$n_0$，度为2的结点数为$n_2$，则$n_0=n_2+1$。已知叶子结点数$n_0=70$，则度为2的结点数$n_2=n_0-1=69$。总结点数$N=n_0+n_1+n_2$，其中$n_1$为度为1的结点数，已知$n_1=80$，$n_0=70$，$n_2=69$，所以$N=70+80+69=219$。4.对长度为n的线性表排序，在最坏情况下，比较次数不是$n(n-1)/2$的排序方法是（）A.快速排序B.冒泡排序C.直接插入排序D.堆排序答案：D解析：快速排序、冒泡排序和直接插入排序在最坏情况下的比较次数均为$n(n-1)/2$。堆排序在最坏情况下的时间复杂度为$O(nlog_2n)$，其比较次数不是$n(n-1)/2$，所以答案选D。5.下列对于线性链表的描述中正确的是（）A.存储空间不一定是连续，且各元素的存储顺序是任意的B.存储空间不一定是连续，且前件元素一定存储在后件元素的前面C.存储空间必须连续，且前件元素一定存储在后件元素的前面D.存储空间必须连续，且各元素的存储顺序是任意的答案：A解析：线性链表是一种链式存储结构，它的存储空间不一定是连续的，各元素的存储顺序是任意的，通过指针来表示元素之间的逻辑关系。A选项正确，B、C、D选项错误。6.下列数据结构中，属于非线性结构的是（）A.循环队列B.带链队列C.二叉树D.带链栈答案：C解析：循环队列、带链队列和带链栈都属于线性结构，它们的元素之间存在一对一的线性关系。而二叉树是一种非线性结构，其元素之间存在一对多的层次关系，所以答案选C。7.软件按功能可以分为：应用软件、系统软件和支撑软件（或工具软件）。下面属于系统软件的是（）A.编辑软件B.操作系统C.教务管理系统D.浏览器答案：B解析：系统软件是指控制和协调计算机及外部设备，支持应用软件开发和运行的软件，主要包括操作系统、语言处理系统、数据库管理系统等。编辑软件和浏览器属于工具软件，教务管理系统属于应用软件，操作系统属于系统软件，所以答案选B。8.软件（程序）调试的任务是（）A.诊断和改正程序中的错误B.尽可能多地发现程序中的错误C.发现并改正程序中的所有错误D.确定程序中错误的性质答案：A解析：软件调试的任务是诊断和改正程序中的错误。软件测试的目的是尽可能多地发现程序中的错误，但不能发现并改正程序中的所有错误。确定程序中错误的性质只是调试过程中的一个环节，不是调试的主要任务。所以答案选A。9.数据流程图（DFD图）是（）A.软件概要设计的工具B.软件详细设计的工具C.结构化方法的需求分析工具D.面向对象方法的需求分析工具答案：C解析：数据流程图（DFD图）是结构化方法的需求分析工具，它从数据传递和加工的角度，以图形的方式描述了系统的数据运动情况，反映了系统的逻辑功能。软件概要设计的工具主要有结构图等，软件详细设计的工具主要有程序流程图、N-S图等。所以答案选C。10.数据库管理系统中负责数据模式定义的语言是（）A.数据定义语言B.数据管理语言C.数据操纵语言D.数据控制语言答案：A解析：数据定义语言（DDL）用于定义数据库的模式、外模式和内模式，如创建、修改和删除数据库对象等。数据操纵语言（DML）用于对数据库中的数据进行查询、插入、更新和删除等操作。数据控制语言（DCL）用于对数据库的访问权限进行控制。不存在数据管理语言这一说法。所以答案选A。11.下列选项中不属于结构化程序设计原则的是（）A.可封装B.自顶向下C.模块化D.逐步求精答案：A解析：结构化程序设计的原则包括自顶向下、逐步求精、模块化和限制使用goto语句。可封装是面向对象程序设计的特点，不是结构化程序设计的原则。所以答案选A。12.数据库设计中，用E-R图来描述信息结构但不涉及信息在计算机中的表示，它属于数据库设计的（）A.需求分析阶段B.逻辑设计阶段C.概念设计阶段D.物理设计阶段答案：C解析：数据库设计分为需求分析、概念设计、逻辑设计和物理设计等阶段。在概念设计阶段，使用E-R图来描述信息结构，它独立于具体的数据库管理系统，不涉及信息在计算机中的表示。需求分析阶段主要是收集和分析用户的需求；逻辑设计阶段是将E-R图转换为关系模型；物理设计阶段是设计数据库的物理存储结构。所以答案选C。13.有两个关系R和T如下：|R||||---|---|---||A|B|C||a|1|2||b|2|2||c|3|2||d|3|2||T||||---|---|---||A|B|C||c|3|2||d|3|2|则由关系R得到关系T的操作是（）A.选择B.投影C.交D.并答案：A解析：选择操作是从关系中找出满足给定条件的元组。在本题中，关系T是从关系R中选择出A属性值为'c'和'd'的元组，所以是选择操作。投影操作是从关系中选取若干属性列组成新的关系；交操作是取两个关系中公共的元组；并操作是将两个关系中的元组合并在一起。所以答案选A。14.设有表示学生选课的三张表，学生S（学号，姓名，性别，年龄，身份证号），课程C（课号，课名），选课SC（学号，课号，成绩），则表SC的关键字（键或码）为（）A.课号，成绩B.学号，成绩C.学号，课号D.学号，姓名，成绩答案：C解析：关键字是能够唯一标识一个元组的属性或属性组。在选课表SC中，学号和课号的组合可以唯一确定一个学生的选课记录，因为一个学生可以选多门课程，一门课程也可以被多个学生选，所以需要学号和课号共同作为关键字。所以答案选C。15.算法的空间复杂度是指（）A.算法在执行过程中所需要的计算机存储空间B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的临时工作单元数答案：A解析：算法的空间复杂度是指算法在执行过程中所需要的计算机存储空间，包括算法程序所占的空间、输入的初始数据所占的空间以及算法执行过程中所需要的额外空间。算法所处理的数据量不是空间复杂度的定义；算法程序中的语句或指令条数与空间复杂度无关；算法在执行过程中所需要的临时工作单元数只是空间复杂度的一部分。所以答案选A。16.下列关于队列的叙述中正确的是（）A.队列按“先进后出”原则组织数据B.队列按“先进先出”原则组织数据C.队列在队尾删除数据D.队列在队头插入数据答案：B解析：队列是一种特殊的线性表，它遵循“先进先出”（FIFO）的原则。队列在队尾插入数据，在队头删除数据。A、C、D选项错误，B选项正确。17.对下列二叉树进行中序遍历的结果是（）```A/\BC/\/DEF```A.ACBDFEB.DBEAFCC.ABDECFD.DEBFCA答案：B解析：中序遍历的规则是：先遍历左子树，然后访问根节点，最后遍历右子树。对于该二叉树，先遍历左子树B，B的左子树为D，访问D，然后访问B，B的右子树为E，访问E；接着访问根节点A；再遍历右子树C，C的左子树为F，访问F，最后访问C。所以中序遍历的结果是DBEAFC，答案选B。18.设循环队列的存储空间为Q(1:35)，初始状态为front=rear=35。现经过一系列入队与退队运算后，front=15，rear=15，则循环队列中的元素个数为（）A.15B.16C.20D.0或35答案：D解析：循环队列中，当front=rear时，队列可能为空，也可能为满。在本题中，初始状态front=rear=35，经过一系列操作后front=rear=15，此时队列可能为空（经过一系列入队和出队操作后，队列为空），也可能为满（队列经过循环后，又回到front=rear的状态且队列已满）。所以循环队列中的元素个数为0或35，答案选D。19.下列排序方法中，最坏情况下比较次数最少的是（）A.冒泡排序B.简单选择排序C.直接插入排序D.堆排序答案：D解析：冒泡排序、简单选择排序和直接插入排序在最坏情况下的时间复杂度均为$O(n^2)$，比较次数为$n(n-1)/2$。堆排序在最坏情况下的时间复杂度为$O(nlog_2n)$，其比较次数相对较少。所以答案选D。20.软件生命周期中的活动不包括（）A.市场调研B.需求分析C.软件测试D.软件维护答案：A解析：软件生命周期包括可行性研究与计划制定、需求分析、软件设计、软件编码、软件测试、软件维护等活动。市场调研不属于软件生命周期中的活动，它主要是在软件开发之前进行的市场需求和竞争情况的调查。所以答案选A。21.从工程管理角度，软件设计一般分为两步完成，它们是（）A.概要设计与详细设计B.数据设计与接口设计C.软件结构设计与数据设计D.过程设计与数据设计答案：A解析：从工程管理角度，软件设计一般分为概要设计和详细设计两步。概要设计的主要任务是确定软件系统的总体结构和模块划分，详细设计则是对每个模块进行具体的设计，包括算法设计、数据结构设计等。数据设计、接口设计、软件结构设计和过程设计等都是软件设计中的具体内容，但不是从工程管理角度的两步划分。所以答案选A。22.数据库系统的三级模式不包括（）A.概念模式B.内模式C.外模式D.数据模式答案：D解析：数据库系统的三级模式包括外模式、概念模式和内模式。外模式是用户与数据库系统的接口，是用户看到的数据视图；概念模式是数据库系统中全局数据逻辑结构的描述；内模式是数据物理结构和存储方式的描述。数据模式不是数据库系统三级模式的内容，所以答案选D。23.有三个关系R、S和T如下：|R||||---|---|---||A|B|C||a|1|2||b|2|1||c|3|1||S||||---|---|---||A|B|C||a|1|2||b|2|1||T||||---|---|---||A|B|C||c|3|1|则由关系R和S得到关系T的操作是（）A.自然连接B.交C.除D.差答案：D解析：差操作是从一个关系中减去另一个关系中相同的元组。在本题中，关系T是由关系R减去关系S中相同的元组得到的，所以是差操作。自然连接是在两个关系中找出公共属性值相等的元组进行连接；交操作是取两个关系中公共的元组；除操作是一种较为复杂的关系运算，与本题情况不符。所以答案选D。24.在关系数据库中，用来表示实体间联系的是（）A.属性B.二维表C.网状结构D.树状结构答案：B解析：在关系数据库中，用二维表来表示实体以及实体之间的联系。属性是二维表中的列，用于描述实体的特征；网状结构和树状结构分别是网状数据库和层次数据库中表示数据联系的方式。所以答案选B。填空题1.一个栈的初始状态为空。首先将元素5，4，3，2，1依次入栈，然后退栈一次，再将元素A，B，C，D依次入栈，之后将所有元素全部退栈，则所有元素退栈（包括中间退栈的元素）的顺序为__________。答案：1，D，C，B，A，2，3，4，5解析：元素5，4，3，2，1依次入栈后，栈内元素从栈顶到栈底为1，2，3，4，5。退栈一次，出栈元素为1。然后元素A，B，C，D依次入栈，此时栈内元素从栈顶到栈底为D，C，B，A，2，3，4，5。再将所有元素全部退栈，出栈顺序为D，C，B，A，2，3，4，5。所以所有元素退栈的顺序为1，D，C，B，A，2，3，4，5。2.某二叉树中度为2的结点有18个，则该二叉树中有__________个叶子结点。答案：19解析：根据二叉树的性质：对于任意一棵二叉树，如果其叶子结点数为$n_0$，度为2的结点数为$n_2$，则$n_0=n_2+1$。已知度为2的结点数$n_2=18$，则叶子结点数$n_0=n_2+1=19$。3.软件测试可分为白盒测试和黑盒测试。基本路径测试属于__________测试。答案：白盒解析：白盒测试是基于程序内部逻辑结构的测试方法，它需要了解程序的内部结构和算法。基本路径测试是白盒测试中的一种重要方法，它通过分析程序的控制流图，找出程序中的独立路径，然后对这些路径进行测试。黑盒测试是基于功能的测试方法，不考虑程序的内部结构，只关注程序的输入和输出。所以基本路径测试属于白盒测试。4.符合结构化原则的三种基本控制结构是：选择结构、循环结构和__________。答案：顺序结构解析：符合结构化原则的三种基本控制结构是顺序结构、选择结构和循环结构。顺序结构是按照语句的先后顺序依次执行；选择结构根据条件的真假选择不同的执行路径；循环结构在满足一定条件时重复执行一段代码。5.数据库系统的核心是__________。答案：数据库管理系统解析：数据库系统由数据库、数据库管理系统、应用程序、数据库管理员和用户等组成。其中，数据库管理系统是数据库系统的核心，它负责对数据库进行管理和维护，包括数据的定义、存储、查询、更新和控制等功能。6.在关系模型中，把数据看成是二维表，每一个二维表称为一个__________。答案：关系解析：在关系模型中，数据被组织成二维表的形式，每一个二维表称为一个关系。关系中的每一行称为一个元组，每一列称为一个属性。7.算法执行过程中所需要的存储空间称为算法的__________。答案：空间复杂度解析：算法的空间复杂度是指算法在执行过程中所需要的计算机存储空间，包括算法程序所占的空间、输入的初始数据所占的空间以及算法执行过程中所需要的额外空间。8.线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的__________存储结构。答案：顺序解析：循环队列是队列的一种顺序存储结构，它通过使用数组来存储队列元素，并利用取模运算来实现队列的循环。链式存储结构则是通过指针将各个元素连接起来。9.某二叉树的前序遍历序列为ABCDE，中序遍历序列为CBADE，则后序遍历序列为__________。答案：CBEAD解析：前序遍历的顺序是根节点、左子树、右子树，中序遍历的顺序是左子树、根节点、右子树。根据前序遍历序列ABCDE可知，A是根节点；再结合中序遍历序列CBADE，可知CB是左子树的节点，DE是右子树的节点。对左子树进行分析，前序遍历中B在前，所以B是左子树的根节点，中序遍历中C在B前，所以C是B的左子树。对右子树进行分析，前序遍历中D在前，所以D是右子树的根节点，中序遍历中E在D后，所以E是D的右子树。得到二叉树的结构后，后序遍历（左子树、右子树、根节点）的结果为CBEAD。10.软件需求规格说明书应具有完整性、无歧义性、正确性、可验证性、可修改性等特性，其中最重要的是__________。答案：无歧义性解析：软件需求规格说明书是软件开发的重要文档，它描述了软件系统的功能、性能、约束等需求。无歧义性是最重要的特性，因为如果需求说明书存在歧义，开发人员可能会对需求产生不同的理解，从而导致开发出的软件不符合用户的要求。完整性、正确性、可验证性和可修改性等特性也是很重要的，但无歧义性是基础。11.在数据库设计中，将E-R图转换成关系数据模型的过程属于__________阶段。答案：逻辑设计解析：数据库设计分为需求分析、概念设计、逻辑设计和物理设计等阶段。E-R图是概念设计阶段的产物，将E-R图转换成关系数据模型的过程属于逻辑设计阶段，该阶段的主要任务是将概念模型转换为具体的数据库管理系统支持的数据模型。12.设有一个关系Student（学号，姓名，系名，课程号