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

全国计算机二级考试公共基础知识试题库和答案一、选择题1.下列叙述中正确的是（）A.算法的效率只与问题的规模有关，而与数据的存储结构无关B.算法的时间复杂度是指执行算法所需要的计算工作量C.数据的逻辑结构与存储结构是一一对应的D.算法的时间复杂度与空间复杂度一定相关答案：B解析：算法的效率与问题规模和数据的存储结构都有关系，A选项错误；数据的逻辑结构和存储结构不是一一对应的，一种逻辑结构可以有多种存储结构，C选项错误；算法的时间复杂度和空间复杂度不一定相关，D选项错误。算法的时间复杂度是指执行算法所需要的计算工作量，B选项正确。2.下列数据结构中，属于非线性结构的是（）A.循环队列B.带链队列C.二叉树D.带链栈答案：C解析：线性结构要求有且只有一个根结点和一个终端结点，并且除根结点和终端结点外，每个结点只有一个前驱和一个后继。循环队列、带链队列和带链栈都满足线性结构的特点。而二叉树是一种非线性结构，它的每个结点可以有两个子结点，C选项正确。3.下列数据结构中，能够按照“先进后出”原则存取数据的是（）A.循环队列B.栈C.队列D.二叉树答案：B解析：栈是一种特殊的线性表，它的特点是后进先出（LastInFirstOut，LIFO），也就是先进后出。循环队列和队列都是先进先出（FirstInFirstOut，FIFO）的线性表。二叉树是一种非线性结构，不存在先进后出的存取原则。所以答案是B。4.对于循环队列，下列叙述中正确的是（）A.队头指针是固定不变的B.队头指针一定大于队尾指针C.队头指针一定小于队尾指针D.队头指针可以大于队尾指针，也可以小于队尾指针答案：D解析：在循环队列中，队头指针和队尾指针是可以动态变化的。当队列进行入队和出队操作时，队头指针和队尾指针会相应地移动。队头指针可以大于队尾指针，也可以小于队尾指针，当队列满和队列空的情况不同时，它们的大小关系也不同。所以D选项正确。5.算法的空间复杂度是指（）A.算法在执行过程中所需要的计算机存储空间B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的临时工作单元数答案：A解析：算法的空间复杂度是指算法在执行过程中所需要的计算机存储空间，包括算法程序所占的空间、输入的初始数据所占的空间以及算法执行过程中所需要的额外空间。B选项算法所处理的数据量不是空间复杂度的定义；C选项算法程序中的语句或指令条数与空间复杂度无关；D选项算法在执行过程中所需要的临时工作单元数只是空间复杂度的一部分。所以A选项正确。6.软件按功能可以分为：应用软件、系统软件和支撑软件（或工具软件）。下面属于系统软件的是（）A.编辑软件B.操作系统C.教务管理系统D.浏览器答案：B解析：系统软件是管理计算机的硬件资源，为应用软件提供运行环境等功能的软件，操作系统是典型的系统软件。编辑软件和浏览器属于支撑软件（或工具软件），教务管理系统属于应用软件。所以答案是B。7.软件生命周期是指（）A.软件产品从提出、实现、使用维护到停止使用退役的过程B.软件从需求分析、设计、实现到测试完成的过程C.软件的开发过程D.软件的运行维护过程答案：A解析：软件生命周期是指软件产品从提出、实现、使用维护到停止使用退役的整个过程，它包括软件定义、软件开发和软件维护等阶段。B选项只涵盖了软件开发过程的一部分；C选项软件开发过程只是软件生命周期的一部分；D选项软件的运行维护过程也只是软件生命周期的一部分。所以A选项正确。8.软件测试的目的是（）A.评估软件可靠性B.发现并改正程序中的错误C.改正程序中的错误D.发现程序中的错误答案：D解析：软件测试的目的是发现程序中的错误，而不是改正错误，改正错误是调试的任务。评估软件可靠性也不是软件测试的主要目的。所以D选项正确。9.数据库管理系统是（）A.操作系统的一部分B.在操作系统支持下的系统软件C.一种编译系统D.一种操作系统答案：B解析：数据库管理系统（DBMS）是在操作系统支持下的系统软件，它负责对数据库进行管理和维护，提供数据定义、数据操纵、数据库的运行管理和数据库的建立与维护等功能。它不是操作系统的一部分，也不是编译系统，更不是操作系统。所以B选项正确。10.在E-R图中，用来表示实体联系的图形是（）A.椭圆形B.矩形C.菱形D.三角形答案：C解析：在E-R图中，矩形表示实体，椭圆形表示属性，菱形表示实体之间的联系。所以C选项正确。11.下列叙述中正确的是（）A.栈是“先进先出”的线性表B.队列是“先进后出”的线性表C.循环队列是非线性结构D.有序线性表既可以采用顺序存储结构，也可以采用链式存储结构答案：D解析：栈是“先进后出”的线性表，A选项错误；队列是“先进先出”的线性表，B选项错误；循环队列是线性结构，C选项错误；有序线性表既可以采用顺序存储结构，也可以采用链式存储结构，D选项正确。12.支持子程序调用的数据结构是（）A.栈B.树C.队列D.二叉树答案：A解析：在子程序调用时，需要保存调用前的现场信息（如返回地址等），当子程序执行完后再恢复现场继续执行。栈的后进先出特点正好适合这种需求，在子程序调用时将现场信息压入栈，子程序返回时从栈中弹出信息恢复现场。所以支持子程序调用的数据结构是栈，A选项正确。13.某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是（）A.10B.8C.6D.4答案：C解析：在二叉树中，叶子结点数（度为0的结点数）等于度为2的结点数加1。已知该二叉树有5个度为2的结点，那么叶子结点数为5+1=6。所以C选项正确。14.下列排序方法中，最坏情况下比较次数最少的是（）A.冒泡排序B.简单选择排序C.直接插入排序D.堆排序答案：D解析：冒泡排序、简单选择排序和直接插入排序在最坏情况下的时间复杂度都是$O(n^2)$，而堆排序在最坏情况下的时间复杂度是$O(nlog_2n)$。时间复杂度越低，在最坏情况下的比较次数相对越少。所以D选项正确。15.软件按功能可以分为应用软件、系统软件和支撑软件（或工具软件）。下面属于应用软件的是（）A.编译程序B.操作系统C.教务管理系统D.汇编程序答案：C解析：编译程序和汇编程序属于支撑软件（或工具软件），操作系统属于系统软件，教务管理系统是为了满足学校教务管理需求而开发的软件，属于应用软件。所以C选项正确。16.下面叙述中错误的是（）A.软件测试的目的是发现错误并改正错误B.对被调试的程序进行“错误定位”是程序调试的必要步骤C.程序调试通常也称为DebugD.软件测试应严格执行测试计划，排除测试的随意性答案：A解析：软件测试的目的是发现程序中的错误，而改正错误是程序调试的任务，A选项错误；程序调试的关键步骤就是对被调试的程序进行“错误定位”，B选项正确；程序调试通常也称为Debug，C选项正确；软件测试应严格执行测试计划，排除测试的随意性，以保证测试的有效性和准确性，D选项正确。17.耦合性和内聚性是对模块独立性度量的两个标准。下列叙述中正确的是（）A.提高耦合性降低内聚性有利于提高模块的独立性B.降低耦合性提高内聚性有利于提高模块的独立性C.耦合性是指一个模块内部各个元素间彼此结合的紧密程度D.内聚性是指模块间互相连接的紧密程度答案：B解析：模块的独立性是指每个模块只完成系统要求的独立的子功能，并且与其他模块的联系最少且接口简单。耦合性是指模块间互相连接的紧密程度，内聚性是指一个模块内部各个元素间彼此结合的紧密程度。降低耦合性、提高内聚性有利于提高模块的独立性。所以B选项正确。18.数据库应用系统中的核心问题是（）A.数据库设计B.数据库系统设计C.数据库维护D.数据库管理员培训答案：A解析：数据库应用系统是指系统开发人员利用数据库系统资源开发出来的，面向某一类实际应用的软件系统。数据库设计是数据库应用系统中的核心问题，它的好坏直接影响到整个数据库应用系统的性能和质量。所以A选项正确。19.有两个关系R，S如下：R|A|B|C||---|---|---||a|3|2||b|0|1||c|2|1|S|A|B||---|---||a|3||b|0||c|2|由关系R通过运算得到关系S，则所使用的运算为（）A.选择B.投影C.插入D.连接答案：B解析：投影是从关系中选取若干属性组成新的关系。关系R有A、B、C三个属性，关系S有A、B两个属性，是从关系R中选取了A和B两个属性，所以使用的运算是投影。选择是从关系中选取满足条件的元组；插入是向关系中插入新的元组；连接是将两个关系根据一定的条件组合成一个新的关系。所以B选项正确。20.将E-R图转换为关系模式时，实体和联系都可以表示为（）A.属性B.键C.关系D.域答案：C解析：将E-R图转换为关系模式时，实体和联系都可以表示为关系。实体的属性对应关系的属性，实体之间的联系也可以用关系来表示。所以C选项正确。二、填空题1.假设一个长度为50的数组（数组元素的下标从0到49）作为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素，如果bottom=49，top=30（数组下标），则栈中具有____个元素。答案：20解析：栈中元素个数=栈底指针-栈顶指针+1，已知bottom=49，top=30，所以栈中元素个数=49-30+1=20。2.软件测试可分为白盒测试和黑盒测试。基本路径测试属于____测试。答案：白盒解析：白盒测试是基于程序内部逻辑结构的测试方法，基本路径测试是白盒测试中的一种重要方法，它通过分析程序的控制流图来确定程序中的基本路径，然后设计测试用例覆盖这些基本路径。黑盒测试是基于功能的测试方法，不考虑程序的内部结构。所以基本路径测试属于白盒测试。3.符合结构化原则的三种基本控制结构是：选择结构、循环结构和____。答案：顺序结构解析：符合结构化原则的三种基本控制结构是顺序结构、选择结构和循环结构。顺序结构是按照语句的先后顺序依次执行；选择结构根据条件判断选择执行不同的语句块；循环结构是在满足一定条件下重复执行某一语句块。4.数据库系统的核心是____。答案：数据库管理系统解析：数据库管理系统（DBMS）负责对数据库进行管理和维护，提供数据定义、数据操纵、数据库的运行管理和数据库的建立与维护等功能，是数据库系统的核心。5.在E-R图中，图形包括矩形框、菱形框、椭圆形框。其中表示实体联系的是____框。答案：菱形解析：在E-R图中，矩形框表示实体，椭圆形框表示属性，菱形框表示实体之间的联系。6.线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的____存储结构。答案：顺序解析：循环队列是队列的一种顺序存储结构，它利用数组来实现队列的功能，通过对数组下标的循环操作来模拟队列的入队和出队操作。7.对下列二叉树进行中序遍历的结果为____。```A/\BC/\DE/F```答案：DBFECA解析：中序遍历的规则是先遍历左子树，然后访问根结点，最后遍历右子树。对于该二叉树，先遍历左子树B，B的左子树为D，所以先访问D；然后访问B；B的右子树为E，E的左子树为F，先访问F，再访问E；接着访问根结点A；最后遍历右子树C。所以中序遍历的结果为DBFECA。8.软件生命周期可分为多个阶段，一般分为定义阶段、开发阶段和维护阶段。编码和测试属于____阶段。答案：开发解析：软件生命周期的开发阶段包括需求分析、设计、编码和测试等活动。定义阶段主要进行问题定义、可行性研究等；维护阶段是对软件进行维护和更新。所以编码和测试属于开发阶段。9.在数据库技术中，为提高数据库的逻辑独立性和物理独立性，数据库的结构被划分成用户级、____和存储级三个层次。答案：概念级解析：数据库的结构通常分为用户级、概念级和存储级三个层次。用户级是用户看到和使用的数据库部分；概念级是对数据库整体逻辑结构的描述；存储级是数据库在存储设备上的物理存储结构。这种分层结构可以提高数据库的逻辑独立性和物理独立性。10.在关系数据库中，把数据表示成二维表，每一个二维表称为____。答案：关系解析：在关系数据库中，数据以二维表的形式组织，每一个二维表称为一个关系，表中的行称为元组，表中的列称为属性。三、简答题1.简述算法的基本特征。算法具有以下基本特征：-可行性：算法中的每一个步骤都必须是可行的，能够通过有限次基本运算实现。例如，在一个计算整数加法的算法中，加法运算就是可行的基本运算。-确定性：算法的每一个步骤都必须有明确的定义，不允许有歧义。例如，在判断一个数是否大于另一个数的算法中，“大于”的判断标准是明确的。-有穷性：算法必须在有限的时间内结束，即算法中的步骤是有限的。例如，一个排序算法不能无限制地运行下去，必须在一定的时间内完成排序任务。-拥有足够的情报：算法在执行时需要有足够的输入信息，同时也应该有明确的输出结果。例如，一个计算圆面积的算法，需要输入圆的半径作为输入信息，输出圆的面积作为结果。2.简述数据库系统的特点。数据库系统具有以下特点：-数据结构化：数据库系统采用数据模型来描述数据，数据之间具有复杂的联系，而不是像文件系统那样数据是孤立的。例如，在一个学生管理数据库中，学生信息、课程信息和成绩信息之间存在着关联。-数据的共享性高、冗余度低：多个用户可以同时共享数据库中的数据，减少了数据的重复存储，降低了冗余度。例如，多个部门可以同时使用学生管理数据库中的学生信息。-数据独立性高：包括物理独立性和逻辑独立性。物理独立性是指用户的应用程序与存储在磁盘上的数据库中的数据是相互独立的，当数据的物理存储结构改变时，应用程序不需要改变。逻辑独立性是指用户的应用程序与数据库的逻辑结构是相互独立的，当数据库的逻辑结构改变时，应用程序不需要改变。-数据由数据库管理系统统一管理和控制：数据库管理系统提供了数据的安全性保护、完整性检查、并发控制和数据库恢复等功能。例如，通过设置用户权限来保证数据的安全性，通过定义数据的约束条件来保证数据的完整性。3.简述软件测试的方法和步骤。软件测试的方法主要分为黑盒测试和白盒测试：-黑盒测试：也称为功能测试，它不考虑程序的内部结构和实现细节，只根据程序的功能规格说明来设计测试用例。常用的黑盒测试方法有等价类划分法、边界值分析法、错误推测法等。例如，对于一个计算器程序，只关注输入不同的数字和运算符后是否能得到正确的计算结果。-白盒测试：也称为结构测试，它是基于程序的内部逻辑结构来设计测试用例。常用的白盒测试方法有语句覆盖、判定覆盖、条件覆盖、判定-条件覆盖、条件组合覆盖等。例如，分析程序的代码，确保程序中的每一条语句、每一个判定分支都能被执行到。软件测试的步骤一般包括：-单元测试：对软件中的最小可测试单元进行测试，通常是对一个模块进行测试，检查模块的功能是否正确。例如，对一个函数进行单元测试，检查函数的输入输出是否符合预期。-集成测试：将经过单元测试的模块逐步组装成一个完整的系统进行测试，检查模块之间的接口是否正确，模块之间的交互是否正常。例如，将多个函数集成在一起，测试它们之间的调用关系是否正确。-确认测试：按照软件的需求规格说明，对软件进行全面的测试，验证软件是否满足用户的需求。例如，让用户对软件进行试用，检查软件是否实现了用户所要求的功能。-系统测试：将软件与硬件、操作系统等其他元素结合在一起进行测试，检查整个系统的性能、兼容性等方面是否符合要求。例如，测试软件在不同操作系统、不同硬件配置下的运行情况。4.简述线性表的顺序存储结构和链式存储结构的优缺点。线性表的顺序存储结构的优点：-随机访问效率高：可以通过数组下标直接访问线性表中的任意元素，时间复杂度为$O(1)$。例如，在一个长度为n的顺序表中，访问第i个元素只需要根据数组的首地址和元素的大小计算出该元素的存储地址即可。-存储密度大：不需要额外的指针来表示元素之间的逻辑关系，每个存储单元都用来存储数据元素，空间利用率高。线性表的顺序存储结构的缺点：-插入和删除操作效率低：在顺序表中进行插入和删除操作时，需要移动大量的元素，时间复杂度为$O(n)$。例如，在顺序表的第i个位置插入一个元素，需要将第i个位置及后面的所有元素都向后移动一位。-空间大小固定：在创建顺序表时需要预先分配一定的存储空间，当数据量超过存储空间时，需要进行扩容操作，比较麻烦。线性表的链式存储结构的优点：-插入和删除操作效率高：在链式表中进行插入和删除操作时，只需要修改指针的指向，不需要移动大量的元素，时间复杂度为$O(1)$（前提是已经找到插入或删除的位置）。例如，在链表中插入一个新节点，只需要修改相邻节点的指针即可。-空间动态分配：不需要预先分配固定的存储空间，可以根据需要动态地分配和释放存储空间。线性表的链式存储结构的缺点：-随机访问效率低：在链式表中访问任意元素时，需要从链表的头节点开始依次遍历，时间复