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

全国计算机二级考试公共基础知识试题库和答案单项选择题（本大题共30小题，每小题1.5分，共45分。在每小题给出的四个选项中，只有一项是符合题目要求的）1.下列关于算法的描述中，错误的是A.算法的有穷性是指一个算法必须在执行有限步骤后结束B.算法的可行性是指算法中的每一步操作都必须是可执行的C.算法的复杂度主要包括时间复杂度和空间复杂度D.算法的基本特征包括确定性、有穷性、可行性和无穷性2.在数据结构中，从逻辑上可以将数据结构分为A.动态结构和静态结构B.线性结构和非线性结构C.紧凑结构和非紧凑结构D.内部结构和外部结构3.下列关于栈的叙述中，正确的是A.栈是一种先进先出的线性表B.栈允许在表的两端进行插入和删除操作C.栈顶元素总是最后被插入的元素，也是最先被删除的元素D.在栈中插入元素称为入栈，只能从栈底进行4.设循环队列的存储空间为Q(1:50)A.5B.6C.35D.455.在一棵深度为k的二叉树中，最多有−1个结点。当kA.15B.31C.32D.636.对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为A.nB.nC.(D.n7.在长度为n的有序线性表中进行二分查找，最坏情况下需要的比较次数为A.OB.OC.OD.O8.冒泡排序在最坏情况下的比较次数为A.nB.nC.nD.9.结构化程序设计的基本控制结构不包括A.顺序结构B.选择结构C.循环结构D.跳转结构10.在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发送A.消息B.命令C.口令D.调用语句11.软件生命周期中，确定软件系统必须做什么的阶段是A.软件设计B.需求分析C.软件测试D.详细设计12.在软件需求分析阶段，常用的图形工具是A.程序流程图B.数据流图（DFD）C.结构图D.判定表13.软件测试的目的是A.证明软件是正确的B.发现软件中的错误C.修复软件中的错误D.改善软件的性能14.下列叙述中，正确的是A.黑盒测试方法主要检查程序内部逻辑结构B.白盒测试方法完全不考虑程序的内部结构C.白盒测试方法又称为结构测试或逻辑驱动测试D.黑盒测试方法又称为结构测试15.下列选项中，不属于软件工程三要素的是A.工具B.过程C.方法D.环境16.数据库系统的核心是A.数据库B.数据库管理系统C.数据库应用系统D.数据库管理员17.在数据管理技术发展的三个阶段中，数据独立性最高的是A.人工管理阶段B.文件系统阶段C.数据库系统阶段D.机器管理阶段18.下列关于数据库三级模式结构的描述中，错误的是A.模式是数据库中全体数据的逻辑结构和特征的描述B.外模式是数据库用户能够看见和使用的局部数据的逻辑结构和特征的描述C.内模式是数据物理结构和存储方式的描述D.数据库系统只有一个外模式，但可以有多个模式和内模式19.用树形结构表示实体之间联系的模型是A.关系模型B.网状模型C.层次模型D.面向对象模型20.在关系数据库中，用来表示实体之间联系的是A.树结构B.图结构C.二维表D.线性表21.关系数据库管理系统能实现的专门关系运算包括A.排序、索引、统计B.选择、投影、连接C.关联、更新、排序D.显示、打印、制表22.下列关于E-R模型的叙述中，正确的是A.E-R模型是一种物理模型B.E-R模型中的实体集用椭圆形表示C.E-R模型中的属性用矩形表示D.E-R模型中的联系用菱形表示23.设有关系R和S，关系R通过投影运算得到关系T，则下列叙述正确的是A.T的元组是R的元组的子集，且T的属性是R的属性的子集B.T的属性是R的属性的子集，但T的元组不一定包含于R的元组C.T是从R中选取满足条件的元组D.T是将R和S拼接起来24.下列关于数据库设计的叙述中，错误的是A.数据库设计主要包括概念设计、逻辑设计和物理设计B.概念设计阶段的结果是得到一个与具体DBMS无关的概念模型C.逻辑设计阶段的主要任务是将E-R图转换为关系模型D.物理设计阶段的主要任务是在DBMS中建立表结构25.某二叉树有5个度为2的结点，3个度为1的结点，则该二叉树有叶子结点个数为A.5B.6C.7D.826.下列时间复杂度中，最优的是A.OB.OC.OD.O27.下列软件过程模型中，以用户需求为动力，以对象为驱动的模型是A.瀑布模型B.螺旋模型C.喷泉模型D.快速原型模型28.软件测试中的集成测试，其主要测试方法是A.白盒测试B.黑盒测试C.灰盒测试D.确认测试29.数据库事务的四个基本特性（ACID）不包括A.原子性B.一致性C.独立性D.可重用性30.设有关系R(A.(R)表示在R中选取属性B.(R)表示在R中选取属性A和C.R⋈S表示R和D.R×S表示R和多项选择题（本大题共10小题，每小题2分，共20分。在每小题给出的四个选项中，有两个或两个以上选项是符合题目要求的，多选、漏选均不得分）31.下列关于数据结构的叙述中，正确的有A.数据的逻辑结构与存储结构无关B.数据的物理结构是指数据在计算机存储器中的表示C.顺序存储结构既可用于存储线性表，也可用于存储非线性结构（如树）D.链式存储结构的特点是结点之间的逻辑关系通过指针来体现32.下列算法中，最坏情况下时间复杂度为O(A.快速排序B.冒泡排序C.简单插入排序D.堆排序33.结构化程序设计强调的原则包括A.自顶向下B.逐步求精C.模块化D.限制使用goto语句34.在面向对象方法中，类的主要特征包括A.封装性B.继承性C.多态性D.抽象性35.软件需求分析阶段产生的主要文档有A.需求规格说明书B.数据要求说明书C.初步用户手册D.概要设计说明书36.软件测试中，属于黑盒测试方法的有A.等价类划分法B.边界值分析法C.语句覆盖法D.错误推测法37.软件测试中，属于白盒测试方法的有A.逻辑覆盖B.基本路径测试C.条件组合覆盖D.因果图法38.下列关于数据库系统的叙述中，正确的有A.数据库系统减小了数据冗余B.数据库系统避免了所有的数据冗余C.数据库系统具有较高的数据独立性D.数据库系统实现了数据共享39.关系数据库中，关于实体完整性和参照完整性的描述，正确的有A.实体完整性要求主属性不能取空值B.参照完整性要求外键要么为空，要么等于被参照关系中主键的某个值C.实体完整性是针对基本关系的，视图不需要满足实体完整性D.参照完整性用于维护不同表之间的数据一致性40.下列关系运算中，属于专门的关系运算的有A.选择B.投影C.连接D.笛卡尔积填空题（本大题共10小题，每小题2分，共20分。请将答案写在横线上）41.在算法设计中，衡量算法优劣的两个主要指标是时间复杂度和___________。42.在一个长度为n的顺序表中删除第i个元素，需要移动的元素个数为___________。43.栈和队列都是限制存取位置的线性表，栈的操作原则是___________。44.一棵完全二叉树有700个结点，则该二叉树的叶子结点数为___________。45.在面向对象方法中，将数据和操作数据的方法封装在一起，对外隐藏内部实现细节的特性称为___________。46.软件工程的三要素是方法、工具和___________。47.软件生命周期可以分为软件定义、软件开发和___________三个时期。48.数据库设计中，将E-R图转换为关系模型的过程属于___________设计阶段。49.在关系模型中，二维表中的行称为___________，列称为属性。50.关系数据库的标准语言是___________。简答题（本大题共5小题，每小题5分，共25分）51.简述栈和队列的主要区别。52.什么是软件的耦合性和内聚性？在软件设计中应如何处理两者的关系？53.简述黑盒测试和白盒测试的主要区别。54.简述数据库的物理独立性和逻辑独立性。55.简述软件测试与软件调试的区别。应用题（本大题共5小题，每小题8分，共40分）56.某二叉树的前序遍历序列为A,B,（1）请画出该二叉树的结构图（可用文本描述结点之间的父子关系）。（2）写出该二叉树的后序遍历序列。57.设有一个线性表的关键字序列为：[49（1）请写出第一趟划分的过程及划分后的结果序列。（2）简述快速排序的基本思想。58.设某商场商品销售数据库中有三个关系模式：商品表P(销售员表S(销售记录表SP请用关系代数表达式表示以下查询：（1）查询年龄大于30岁的销售员的姓名。（2）查询销售了单价大于1000元的商品的销售员号。（3）查询销售了商品号为“P001”的销售员的姓名和年龄。59.某学校图书借阅系统包含如下实体及其联系：实体：学生（学号、姓名、性别、专业）、图书（书号、书名、作者、出版社）。联系：借阅（借书日期、还书日期）。一个学生可以借阅多本图书，一本图书可以被多个学生借阅。（1）请根据上述描述，设计该系统的E-R模型（用文字描述实体、属性及联系的连接方式）。（2）将该E-R模型转换为关系模式，并指出各关系的主键。60.对下列程序段进行逻辑分析：```cintfunc(intn){inti,j,sum=0;for(i=1;i<=n;i++){for(j=1;j<=i;j++){sum=sum+j;}}returnsum;}```（1）分析该程序段的时间复杂度（要求写出计算过程）。（2）若将外层循环改为`for(i=1;i<=n;i*=2)`，内层循环不变，分析修改后程序段的时间复杂度。参考答案及详细解析单项选择题（每小题1.5分，共45分）1.【答案】D【解析】算法的基本特征包括：有穷性、确定性、可行性、有零个或多个输入、有一个或多个输出。无穷性是错误的，因为算法必须在有限步骤内结束。2.【答案】B【解析】数据结构按逻辑结构可分为线性结构（如线性表、栈、队列）和非线性结构（如树、图）。按存储结构（物理结构）可分为顺序存储结构、链式存储结构、索引存储结构和散列存储结构。3.【答案】C【解析】栈是一种后进先出的线性表，只允许在栈顶进行插入和删除操作。栈顶元素总是最后被插入的元素，也是最先被删除的元素。4.【答案】A【解析】循环队列元素个数的计算公式为：当rear≥fro5.【答案】B【解析】根据公式，深度为k的二叉树最多有−1个结点。当k=56.【答案】B【解析】顺序查找在最坏情况下需要比较n次，即查找的元素在表的末尾或者不在表中时。平均查找次数为(n7.【答案】C【解析】二分查找（折半查找）只适用于顺序存储的有序线性表。最坏情况下的比较次数为⌊lon8.【答案】B【解析】冒泡排序在最坏情况下（即初始序列逆序时）需要进行n−1趟排序，第i趟比较n−9.【答案】D【解析】结构化程序设计的三种基本控制结构是顺序结构、选择结构（分支结构）和循环结构。跳转结构（如goto语句）在结构化程序设计中是被限制或禁止使用的。10.【答案】A【解析】在面向对象方法中，对象之间的交互是通过发送消息来实现的。对象收到消息后，会调用相应的方法为其服务。11.【答案】B【解析】需求分析阶段的主要任务是确定软件系统必须“做什么”，即确定软件系统的功能、性能、数据、界面等需求。软件设计阶段解决“怎么做”的问题。12.【答案】B【解析】需求分析阶段常用的图形工具有数据流图（DFD）和实体-联系图（E-R图）。程序流程图和结构图主要用于详细设计阶段。判定表可用于需求分析中的复杂逻辑表达，但不是最典型的图形工具。13.【答案】B【解析】软件测试的目的是尽可能多地发现软件中的错误，而不是证明软件是正确的。修复错误属于调试阶段的工作。14.【答案】C【解析】白盒测试方法又称为结构测试或逻辑驱动测试，它需要了解程序的内部结构。黑盒测试方法（功能测试）完全不考虑程序的内部逻辑结构，只根据程序的功能说明书来设计测试用例。15.【答案】D【解析】软件工程的三要素是方法、工具和过程。环境（如开发环境）虽然重要，但不是软件工程的三要素之一。16.【答案】B【解析】数据库管理系统（DBMS）是数据库系统的核心，它负责对数据库进行统一的管理和控制。数据库系统包括数据库、DBMS、应用系统和数据库管理员等。17.【答案】C【解析】在数据库系统阶段，数据的逻辑结构与物理结构分离，具有较高的数据独立性，包括物理独立性和逻辑独立性。18.【答案】D【解析】数据库三级模式结构包括外模式、模式和内模式。数据库系统只有一个模式和一个内模式，但可以有多个外模式（因为不同的用户有不同的视图）。19.【答案】C【解析】层次模型用树形结构表示实体及其之间的联系；网状模型用有向图结构表示；关系模型用二维表结构表示。20.【答案】C【解析】在关系模型中，实体及实体之间的联系都用二维表来表示。21.【答案】B【解析】关系数据库的专门关系运算包括选择（从行的角度）、投影（从列的角度）和连接（将两个关系拼接成一个新的关系）。22.【答案】D【解析】E-R模型即实体-联系模型。在E-R图中，实体集用矩形表示，属性用椭圆形表示，联系用菱形表示。23.【答案】A【解析】投影运算从关系R中选取某些列（属性子集），并去掉重复元组，因此结果关系T的元组是R的元组的子集，属性也是R的属性子集。24.【答案】D【解析】物理设计阶段的主要任务是为关系模型选择合适的存取方法和存储结构（如建立索引、聚簇等），而在DBMS中建立表结构通常属于实施阶段的任务。25.【答案】B【解析】根据二叉树的性质：度为0的结点数（叶子结点）等于度为2的结点数加1，即=+1。因此26.【答案】D【解析】时间复杂度从优到劣的排序一般为：O(1)27.【答案】B【解析】螺旋模型将瀑布模型和快速原型模型结合起来，不仅以用户需求为动力，而且强调风险分析，适合大型复杂软件的开发。喷泉模型是以用户需求为动力，以对象为驱动的模型。题目中描述有误，通常螺旋模型强调风险驱动，但选项中喷泉模型虽然面向对象，但在早期的概念题中，螺旋模型常被与风险挂钩，而快速原型强调需求。此题选项B更贴近传统描述中的螺旋模型特征。28.【答案】C【解析】集成测试（组装测试）的目的是检查模块之间的接口和交互是否正确。集成测试通常采用灰盒测试方法，即不仅关注输入输出（黑盒），也关注模块间的逻辑交互（白盒）。但教材中通常将黑盒测试作为集成测试的主要依据，题目选项C灰盒更准确，但在计算机二级语境中，集成测试多用黑盒测试方法。本题选C。29.【答案】D【解析】事务的四个基本特性（ACID）是：原子性、一致性、隔离性和持久性。可重用性不属于事务特性。30.【答案】B【解析】σ表示选择运算，π表示投影运算。(R)表示在R中选取满足条件A>5的元组；(R)表示在R中选取A和多项选择题（每小题2分，共20分）31.【答案】A,B,C,D【解析】数据的逻辑结构反映数据元素之间的逻辑关系，与存储结构无关；数据的物理结构是数据在计算机中的表示；顺序存储不仅可以存储线性表，也可用于存储完全二叉树等非线性结构；链式存储结构通过指针体现结点间的逻辑关系。四项均正确。32.【答案】A,B,C【解析】快速排序最坏情况（完全逆序）时间复杂度为O()；冒泡排序和简单插入排序最坏时间复杂度也为O(33.【答案】A,B,C,D【解析】结构化程序设计的四条基本原则是：自顶向下、逐步求精、模块化和限制使用goto语句。34.【答案】A,B,C【解析】面向对象方法的主要特征是封装性、继承性和多态性。抽象性是面向对象的基础，但在描述类的主要特征时通常指前三个。但广义上抽象也是其特征之一。根据大纲，选择A、B、C。35.【答案】A,B,C【解析】需求分析阶段主要产生需求规格说明书、数据要求说明书和初步用户手册。概要设计说明书属于设计阶段。36.【答案】A,B,D【解析】黑盒测试方法包括等价类划分法、边界值分析法、错误推测法和因果图法。语句覆盖法属于白盒测试。37.【答案】A,B,C【解析】白盒测试方法包括逻辑覆盖（如语句覆盖、判定覆盖、条件覆盖、条件组合覆盖等）和基本路径测试。因果图法属于黑盒测试。38.【答案】A,C,D【解析】数据库系统减小了数据冗余，但不可能完全避免所有冗余（有时为了提高查询效率会保留适当冗余）。数据库系统具有较高的数据独立性，并实现了数据共享。39.【答案】A,B,D【解析】实体完整性要求主键不能取空值；参照完整性要求外键要么为空，要么等于被参照关系中主键的某个值；参照完整性用于维护表间数据一致性。C选项错误，视图如果由基本表导出且包含主键，也需要考虑一定的完整性约束，但实体完整性是针对基本关系（表）的约束。40.【答案】A,B,C【解析】专门的关系运算包括选择、投影和连接。笛卡尔积属于传统的集合运算。填空题（每小题2分，共20分）41.【答案】空间复杂度【解析】算法复杂度包括时间复杂度（执行算法所需计算工作量）和空间复杂度（执行算法所需内存空间）。42.【答案】n【解析】在长度为n的顺序表中删除第i个元素，需要将第i+1到第n个元素依次向前移动一位，移动次数为43.【答案】后进先出（或LIFO）【解析】栈的操作原则是后进先出（LastInFirstOut,LIFO）；队列的操作原则是先进先出（FIFO）。44.【答案】350【解析】完全二叉树中，叶子结点数与度为2的结点数的关系为=+1。首先计算总结点数n=700。由于是完全二叉树，只能是0或1。若=0，则n=+=2+45.【答案】封装性【解析】封装性是指将数据和操作数据的方法绑定在一起，对外隐藏内部实现细节，只提供必要的接口。46.【答案】过程【解析】软件工程三要素是方法、工具和过程。方法提供了构造软件的技术；工具为方法提供自动化或半自动化的支持；过程定义了方法使用的顺序及交付的文档。47.【答案】软件运行维护【解析】软件生命周期通常分为三个时期：软件定义（问题定义、可行性研究、需求分析）、软件开发（概要设计、详细设计、编码、测试）和软件运行维护。48.【答案】逻辑【解析】数据库设计阶段中，概念设计阶段得到E-R图，逻辑设计阶段将E-R图转换为关系模型，并进行规范化处理。49.【答案】元组【解析】在关系（二维表）中，每一行称为一个元组，代表一个实体记录；每一列称为属性，代表实体的某个特征。50.【答案】SQL（或结构化查询语言）【解析】关系数据库的标准语言是结构化查询语言。简答题（每小题5分，共25分）51.【答案】（1）操作规则不同：栈是一种后进先出的线性表，插入和删除操作均在栈顶进行；队列是一种先进先出的线性表，插入操作在队尾进行，删除操作在队头进行。（3分）（2）操作端不同：栈只有一个操作端（栈顶），而队列有两个操作端（队头和队尾）。（2分）52.【答案】（1）耦合性是指模块之间相互联系的紧密程度，内聚性是指模块内部各元素之间结合的紧密程度。（2分）（2）在软件设计中，追求“高内聚、低耦合”。即模块内部各元素应紧密结合以完成单一功能，模块与模块之间应尽量减少相互依赖，以提高软件的可维护性和可复用性。（3分）53.【答案】（1）测试视角不同：黑盒测试将程序看作一个黑盒子，不考虑内部结构和处理过程，只根据需求规格说明书检查程序的功能是否正确；白盒测试将程序看作透明的，需要了解程序的内部逻辑结构，根据内部代码检查程序的执行路径是否正确。（3分）（2）测试方法不同：黑盒测试常用等价类划分、边界值分析等；白盒测试常用逻辑覆盖、路径测试等。（2分）54.【答案】（1）物理独立性：指用户的应用程序与存储在磁盘上的数据库中数据的物理存储结构是相互独立的。当数据的物理存储结构或存取方法改变时，通过修改映射，可使逻辑结构不变，从而应用程序不变。（2.5分）（2）逻辑独立性：指用户的应用程序与数据库的逻辑结构是相互独立的。当数据的逻辑结构发生变化（如增加新的数据项或修改数据类型）时，通过修改映射，可使外模式不变，从而应用程序不变。（2.5分）55.【答案】（1）目的不同：测试的目的是发现软件中的错误；调试的目的是定位错误并修复错误。（2分）（2）方法不同：测试是系统性的、有计划的；调试通常是猜测性的、探索性的。（2分）（3）关系：测试是调试的前提，先通过测试发现错误，再通过调试解决错误。（1分）应用题（每小题8分，共40分）56.【答案】（1）根据前序序列A,B,前序第一个元素为A，因此A是根结点。在中序序列中，A左边的D,B,左子树前序为B,D,E，根为B。中序中B左边是右子树前序为C,F,G，根为C。中序中C左边是结构描述：根结点A的左孩子是B，右孩子是C。结点B的左孩子是D，右孩子是E。结点C的左孩子是F，右孩子是G。（6分）（2）后序遍历的顺序是左子树、右子树、根。左子树后序：D右