1、二级公共基础知识-22 及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：46，分数：100.00)1.算法的有穷性是指_。（分数：2.50）A.算法程序的运行时间是有限的B.算法程序所处理的数据量是有限的C.算法程序的长度是有限的D.算法只能被有限的用户使用2.对长度为 n的线性表排序，在最坏情况下，比较次数不是 n(n-1)，2 的排序方法是_。（分数：2.50）A.快速排序B.冒泡排序C.简单插入排序D.堆排序3.一个栈的初始状态为空。现将元素 1、2、3、4、5、A、B、C、D、E 依次入栈，然后再依次出栈，则元素出栈的顺序是_。（分数：2.50）A.123
2、45ABCDEB.EDCBA54321C.ABCDE12345D.54321EDCBA4.下列叙述中正确的是_。（分数：2.50）A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C.顺序存储结构能存储有序表，链式存储结构不能存储有序表D.链式存储结构比顺序存储结构节省存储空间5.支持子程序调用的数据结构是_。（分数：2.50）A栈B树C.队列D.二叉树6.下列叙述中正确的是_。（分数：2.50）A.循环队列有队头和队尾两个指针，因此，循环队列是非线性结构B.在循环队列中，只需要队头指针就能反映队列中元素的动态变
3、化情况C.在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况D.循环队列中元素的个数是由队头指针和队尾指针共同决定7.下列叙述中正确的是_。（分数：2.50）A.栈是“先进先出”的线性表B.队列是“先进后出”的线性表C.循环队列是非线性结构D.有序线性表既可以采用顺序存储结构，也可以采用链式存储结构8.某二叉树有 5个度为 2的结点，则该二叉树中的叶子结点数是_。（分数：2.50）A.10B.8C.6D.49.在长度为 n的有序线性表中进行二分查找，最坏情况下需要比较的次数是_。 A.O(n) B.O(n2) C.O(10g2n) D.O(nlog2n)（分数：2.50）A.B.C.
4、D.10.下列关于栈的叙述正确的是_。（分数：2.50）A.栈按“先进先出”组织数据B.栈按“先进后出”组织数据C.只能在栈底插入数据D.不能删除数据11.下列排序方法中，最坏情况下比较次数最少的是_。（分数：2.50）A.冒泡排序B.简单选择排序C.直接插入排序D.堆排序12.结构化程序设计的基本原则不包括_。（分数：2.50）A.多元性B.自顶向下C.模块化D.逐步求精13.在面向对象方法中，不属于“对象”基本特点的是_。（分数：2.50）A.一致性B.分类性C.多态性D.标识唯一性14.程序流程图中带有箭头的线段表示的是_。（分数：2.50）A.图元关系B.数据流C.控制流D.调用关系1
5、5.软件设计中模块划分应遵循的准则是_。（分数：2.50）A.低内聚低耦合B.高内聚低耦合C.低内聚高耦合D.高内聚高耦合16.在软件开发中，需求分析阶段产生的主要文档是_。（分数：2.50）A.可行性分析报告B.软件需求规格说明书C.概要设计说明书D.集成测试计划17.下面叙述中错误的是_。（分数：2.00）A.软件测试的目的是发现错误并改正错误B.对被调试的程序进行“错误定位”是程序调试的必要步骤C.程序调试通常也称为 DebugD.软件测试应严格执行测试计划，排除测试的随意性18.在数据库设计中，将 E-R图转换成关系数据模型的过程属于_。（分数：2.00）A.需求分析阶段B.概念设计阶
6、段C.逻辑设计阶段D.物理设计阶段19.设有表示学生选课的 3张表，学生 S(学号，姓名，性别，年龄，身份证号)，课程 C(课号，课名)，选课 SC(学号，课号，成绩)，则表 SC的关键字(键或码)为_。（分数：2.00）A.课号，成绩B.学号，成绩C.学号，课号D.学号，姓名，成绩20.一间宿舍可住多个学生，则实体宿舍和学生之间的联系是_。（分数：2.00）A.一对一B.一对多C.多对一D.多对多21.有 3个关系 R、S 和 T如下： R A B m 1 n 2 S B C 1 3 3 5 T A B C m 1 3 由关系 R和 S通过运算得到关系 T，则所使用的运算为_。（分数：2.0
7、0）A.笛卡尔积B交C并D.自然连接22.数据库应用系统中的核心问题是_。（分数：2.00）A.数据库设计B.数据库系统设计C.数据库维护D.数据库管理员培训23.算法的时间复杂度是指_。（分数：2.00）A.执行算法程序所需要的时间B.算法程序的长度C.算法执行过程中所需要的基本运算次数D.算法程序中的指令条数24.下列叙述中正确的是_。（分数：2.00）A.线性链表是线性表的链式存储结构B.栈与队列是非线性结构C.双向链表是非线性结构D.只有根结点的二叉树是线性结构25.有下列二叉树，对此二叉树前序遍历的结果为_。 （分数：2.00）A.ACBEDGFHB.ABDGCEHFC.HGFEDC
8、BAD.ABCDEFGH26.某二叉树共有 60个叶子结点与 50个度为 1的结点，则该二叉树中的总结点数为_。（分数：2.00）A.148B.169C.182D.19827.下列叙述中正确的是_。（分数：2.00）A.一个逻辑数据结构只能有一种存储结构B.逻辑结构属于线性结构，存储结构属于非线性结构C.一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D.一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率28.有下列二叉树，对此二叉树中序遍历的结果为_。 （分数：2.00）A.BDYEACFXZB.DYBEAFCZXC.ABCDEFXYZD.ABDYEC
9、FXZ29.已知一个有序线性表为(13，18，24，35，47，50，62，83，90，115，134)，当用二分法查找值为 90的元素时，查找成功的比较次数为_。（分数：2.00）A.1B.2C.3D.930.下列叙述中错误的是_。（分数：2.00）A.线性表是由 n个元素组成的一个有限序列B.线性表是一种线性结构C.线性表的所有结点有且仅有一个前件和后件D.线性表可以是空表31.栈 S最多能容纳 4个元素，现有 6个元素按 A、B、C、D、E、F 的顺序进栈，下列哪个序列不是可能的出栈序列?_（分数：2.00）A.C、B、E、D、A、FB.C、D、B、F、E、AC.A、D、E、C、B、FD
10、.A、F、E、D、C、B32.两个或两个以上模块之间联系的紧密程度称为_。（分数：2.00）A.耦合性B.内聚性C.复杂性D.数据传输特性33.在下列关于二叉树的叙述中，正确的一项是_。（分数：2.00）A.在二叉树中，任何一个结点的度都是 2B.二叉树的度为 2C.在二叉树中至少有一个结点的度为 2D.一棵二叉树的度可以小于 234.待排序的关键码序列为(33，18，9，25，67，82，53，95，12，70)，要按关键码值递增的顺序排序，采取以第一个关键码为基准元素的快速排序法，第一趟排序后关键码 33被放到第_个位置。（分数：2.00）A.3B.5C.7D.935.设根结点的层次为 0
11、，高度为 K的二叉树的最大结点数为_个。 A.2K B.2K+1-1 C.2K+1 D.2K+1+1（分数：2.00）A.B.C.D.36.算法的有穷性是指_。（分数：2.00）A.算法程序的长度是有限的B.算法程序所处理的数据量是有限的C.算法程序的运行时间是有限的D.算法只能被有限的用户使用37.以下描述中，不是线性表顺序存储结构特征的是_。（分数：2.00）A.不便于插入和删除B.需要连续的存储空间C.可随机访问D.需另外开辟空间来保存元素之间的关系38.按照“先进后出”原则组织数据的数据结构是_。（分数：2.00）A.队列B栈C.双向链表D.二叉树39.已知一棵二叉树的先根序列为 AB
12、CDEFK，中根序列为 DGBAFCK，则结点的后根序列为_。（分数：2.00）A.ACFKDBGB.GDBFKCAC.KCFAGDBD.ABCDFKG40.深度为 6的满二叉树中，度为 2的结点个数为_。（分数：2.00）A.31B.32C.63D.6441.下列数据结构中，能用二分法进行查找的是_。（分数：2.00）A.顺序存储的有序线性表B.线性链表C.二叉链表D.有序线性表42.以下关于顺序存储结构的叙述中，_是正确的。（分数：2.00）A.每个结点中至少包含一个指针域B.逻辑上相邻的结点物理上不必邻接C.可用于栈、队列、树等逻辑结构的存储表示D.插入、删除运算操作不方便43.有 3个
13、结点的二叉树有_。（分数：2.00）A.2种形态B.4种形态C.7种形态D.5种形态44.在一棵二叉树的前序遍历、中序遍历、后序遍历所产生的序列中，所有叶结点的先后顺_。（分数：2.00）A.都不相同B.完全相同C.前序和中序相同，而与后序不同D.中序和后序相同，而与前序不同45.下列叙述中正确的是_。（分数：2.00）A.线性链表的各元素在存储空间中的位置必须是连续的B.线性链表的头元素一定存储在其他元素的前面C.线性链表中的各元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他元素的前面D.线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的46.线性
14、表常采用的两种存储结构是_。（分数：2.00）A.顺序存储结构和链式存储结构B.散列方法和索引方式C.链表存储结构和数组D.线性存储结构和非线性存储结构二级公共基础知识-22 答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：46，分数：100.00)1.算法的有穷性是指_。（分数：2.50）A.算法程序的运行时间是有限的 B.算法程序所处理的数据量是有限的C.算法程序的长度是有限的D.算法只能被有限的用户使用解析：解析 算法的有穷性是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。2.对长度为 n的线性表排序，在最坏情况下，比较次数不是 n(n
15、-1)，2 的排序方法是_。（分数：2.50）A.快速排序B.冒泡排序C.简单插入排序D.堆排序 解析：解析 各种排序方法中最坏情况下需要比较的次数分别为：冒泡排序 n(n-1)/2、快速排序 n(n-1)/2、简单插入排序 n(n-1)/2、希尔排序 O(n 1.5 )、简单选择排序 n(n-1)/2、堆排序 O(nlog 2 n)。3.一个栈的初始状态为空。现将元素 1、2、3、4、5、A、B、C、D、E 依次入栈，然后再依次出栈，则元素出栈的顺序是_。（分数：2.50）A.12345ABCDEB.EDCBA54321 C.ABCDE12345D.54321EDCBA解析：解析 栈是按照“
16、先进后出”或“后进先出”的原则组织数据的。所以出栈顺序是 EDCBA54321。4.下列叙述中正确的是_。（分数：2.50）A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的 B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C.顺序存储结构能存储有序表，链式存储结构不能存储有序表D.链式存储结构比顺序存储结构节省存储空间解析：解析 顺序存储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。而链式存储结构的存储空间不一定是连续的。5.支持子程序调用的数据结构是_。（分数：2.50）A栈 B
17、树C.队列D.二叉树解析：解析 栈是一种限定在一端进行插入与删除的线性表。在主函数调用子函数时，要首先保存主函数当前的状态，然后转去执行子函数，把子函数的运行结果返回到主函数调用子函数时的位置，主函数再接着往下执行，这种过程符合栈的特点。所以一般采用栈式存储方式。6.下列叙述中正确的是_。（分数：2.50）A.循环队列有队头和队尾两个指针，因此，循环队列是非线性结构B.在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况C.在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况D.循环队列中元素的个数是由队头指针和队尾指针共同决定 解析：解析 循环队列中元素的个数是由队头指针和队
18、尾指针共同决定的，元素的动态变化也是通过队头指针和队尾指针来反映的。7.下列叙述中正确的是_。（分数：2.50）A.栈是“先进先出”的线性表B.队列是“先进后出”的线性表C.循环队列是非线性结构D.有序线性表既可以采用顺序存储结构，也可以采用链式存储结构 解析：解析 本题主要考查了栈、队列、循环队列的概念，栈是先进后出的线性表，队列是先进先出的线性表。根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。有序线性表既可以采用顺序存储结构，又可以采用链式存储结构。8.某二叉树有 5个度为 2的结点，则该二叉树中的叶子结点数是_。（分数：2.50）A
19、.10B.8C.6 D.4解析：解析 根据二叉树的性质，在任意二叉树中，度为 0的结点(即叶子结点)总是比度为 2的结点多一个。9.在长度为 n的有序线性表中进行二分查找，最坏情况下需要比较的次数是_。 A.O(n) B.O(n2) C.O(10g2n) D.O(nlog2n)（分数：2.50）A.B.C. D.解析：解析 对于长度为 n的有序线性表，在最坏情况下，二分法查找只需比较 log 2 n次，而顺序查找需要比较 n次。10.下列关于栈的叙述正确的是_。（分数：2.50）A.栈按“先进先出”组织数据B.栈按“先进后出”组织数据 C.只能在栈底插入数据D.不能删除数据解析：解析 栈是限定
20、在一端进行插入和删除的线性表，允许进行插入和删除元素的一端称为栈顶，另一端称为栈底。栈是按照“先进后出”的原则组织数据的。11.下列排序方法中，最坏情况下比较次数最少的是_。（分数：2.50）A.冒泡排序B.简单选择排序C.直接插入排序D.堆排序 解析：解析 冒泡排序、简单选择排序和直接插入排序法在最坏的情况下比较次数为：n(n-1)/2。而堆排序法在最坏的情况下需要比较的次数为 O(nlog 2 n)。12.结构化程序设计的基本原则不包括_。（分数：2.50）A.多元性 B.自顶向下C.模块化D.逐步求精解析：解析 结构化程序设计方法的主要原则可以概括为：自顶向下、逐步求精、模块化和限制使用
21、GOTO语句，其中不包括多态性。13.在面向对象方法中，不属于“对象”基本特点的是_。（分数：2.50）A.一致性 B.分类性C.多态性D.标识唯一性解析：解析 对象具有如下特征：标识唯一性、分类性、多态性、封装性、模块独立性。14.程序流程图中带有箭头的线段表示的是_。（分数：2.50）A.图元关系B.数据流C.控制流 D.调用关系解析：解析 程序流程图是一种传统的、应用广泛的软件过程设计工具，通常也称为程序框图。其中，用带箭头的线段表示控制流，用矩形表示加工步骤，用菱形表示逻辑条件。15.软件设计中模块划分应遵循的准则是_。（分数：2.50）A.低内聚低耦合B.高内聚低耦合 C.低内聚高耦
22、合D.高内聚高耦合解析：解析 耦合性和内聚性是模块独立性的两个定性标准，各模块的内聚性越强，则耦合性越弱。软件设计应该遵循高内聚低耦合。16.在软件开发中，需求分析阶段产生的主要文档是_。（分数：2.50）A.可行性分析报告B.软件需求规格说明书 C.概要设计说明书D.集成测试计划解析：解析 需求分析的最终结果是生成软件需要规格说明书，可以为用户、分析人员和设计人员之间的交流提供方便，可以直接支持目标确认，又可以作为控制软件开发进程的依据。17.下面叙述中错误的是_。（分数：2.00）A.软件测试的目的是发现错误并改正错误 B.对被调试的程序进行“错误定位”是程序调试的必要步骤C.程序调试通常
23、也称为 DebugD.软件测试应严格执行测试计划，排除测试的随意性解析：解析 软件测试是为了发现错误而执行程序的过程。软件测试要严格执行测试计划，排除测试的随意性。程序调试通常也称 Debug，对被调试的程序进行“错误”定位是程序调试的必要步骤。18.在数据库设计中，将 E-R图转换成关系数据模型的过程属于_。（分数：2.00）A.需求分析阶段B.概念设计阶段C.逻辑设计阶段 D.物理设计阶段解析：解析 数据库的设计阶段包括需要分析、概念设计、逻辑设计和物理设计，其中将 E-R图转换成关系数据模型的过程属于逻辑设计阶段。19.设有表示学生选课的 3张表，学生 S(学号，姓名，性别，年龄，身份证
24、号)，课程 C(课号，课名)，选课 SC(学号，课号，成绩)，则表 SC的关键字(键或码)为_。（分数：2.00）A.课号，成绩B.学号，成绩C.学号，课号 D.学号，姓名，成绩解析：解析 关键字是指属性或属性的组合，其值能够唯一地标识一个元组，而在 SC中学号和课程号的组合可以对元组进行唯一地标识。20.一间宿舍可住多个学生，则实体宿舍和学生之间的联系是_。（分数：2.00）A.一对一B.一对多 C.多对一D.多对多解析：解析 两个实体集间的联系可以有下面几种：一对一的联系、一对多或多对一的联系和多对多的联系。由于一个宿舍可以住多个学生，所以它们的联系是一对多联系。21.有 3个关系 R、S
25、 和 T如下： R A B m 1 n 2 S B C 1 3 3 5 T A B C m 1 3 由关系 R和 S通过运算得到关系 T，则所使用的运算为_。（分数：2.00）A.笛卡尔积B交C并D.自然连接 解析：解析 在实际应用中，最常用的连接是一个叫自然连接的特例。它满足下面的条件：两关系间有公共域；通过公共域的相等值进行连接。通过观察 3个关系 R，S，T 的结果可知关系 T是由关系 R和 S进行自然连接得到的。22.数据库应用系统中的核心问题是_。（分数：2.00）A.数据库设计 B.数据库系统设计C.数据库维护D.数据库管理员培训解析：解析 在数据库应用系统中的一个核心问题就是设计
26、一个能满足用户要求，性能良好的数据库，这就是数据库设计。所以数据库设计是数据应用的核心。23.算法的时间复杂度是指_。（分数：2.00）A.执行算法程序所需要的时间B.算法程序的长度C.算法执行过程中所需要的基本运算次数 D.算法程序中的指令条数解析：24.下列叙述中正确的是_。（分数：2.00）A.线性链表是线性表的链式存储结构 B.栈与队列是非线性结构C.双向链表是非线性结构D.只有根结点的二叉树是线性结构解析：25.有下列二叉树，对此二叉树前序遍历的结果为_。 （分数：2.00）A.ACBEDGFHB.ABDGCEHF C.HGFEDCBAD.ABCDEFGH解析：26.某二叉树共有 6
27、0个叶子结点与 50个度为 1的结点，则该二叉树中的总结点数为_。（分数：2.00）A.148B.169 C.182D.198解析：27.下列叙述中正确的是_。（分数：2.00）A.一个逻辑数据结构只能有一种存储结构B.逻辑结构属于线性结构，存储结构属于非线性结构C.一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D.一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率 解析：28.有下列二叉树，对此二叉树中序遍历的结果为_。 （分数：2.00）A.BDYEACFXZB.DYBEAFCZX C.ABCDEFXYZD.ABDYECFXZ解析：29.已知一个有
28、序线性表为(13，18，24，35，47，50，62，83，90，115，134)，当用二分法查找值为 90的元素时，查找成功的比较次数为_。（分数：2.00）A.1B.2 C.3D.9解析：30.下列叙述中错误的是_。（分数：2.00）A.线性表是由 n个元素组成的一个有限序列B.线性表是一种线性结构C.线性表的所有结点有且仅有一个前件和后件 D.线性表可以是空表解析：31.栈 S最多能容纳 4个元素，现有 6个元素按 A、B、C、D、E、F 的顺序进栈，下列哪个序列不是可能的出栈序列?_（分数：2.00）A.C、B、E、D、A、FB.C、D、B、F、E、AC.A、D、E、C、B、FD.A、
29、F、E、D、C、B 解析：32.两个或两个以上模块之间联系的紧密程度称为_。（分数：2.00）A.耦合性 B.内聚性C.复杂性D.数据传输特性解析：33.在下列关于二叉树的叙述中，正确的一项是_。（分数：2.00）A.在二叉树中，任何一个结点的度都是 2B.二叉树的度为 2 C.在二叉树中至少有一个结点的度为 2D.一棵二叉树的度可以小于 2解析：34.待排序的关键码序列为(33，18，9，25，67，82，53，95，12，70)，要按关键码值递增的顺序排序，采取以第一个关键码为基准元素的快速排序法，第一趟排序后关键码 33被放到第_个位置。（分数：2.00）A.3B.5 C.7D.9解析：
30、35.设根结点的层次为 0，高度为 K的二叉树的最大结点数为_个。 A.2K B.2K+1-1 C.2K+1 D.2K+1+1（分数：2.00）A.B. C.D.解析：36.算法的有穷性是指_。（分数：2.00）A.算法程序的长度是有限的B.算法程序所处理的数据量是有限的C.算法程序的运行时间是有限的 D.算法只能被有限的用户使用解析：37.以下描述中，不是线性表顺序存储结构特征的是_。（分数：2.00）A.不便于插入和删除B.需要连续的存储空间C.可随机访问D.需另外开辟空间来保存元素之间的关系 解析：38.按照“先进后出”原则组织数据的数据结构是_。（分数：2.00）A.队列B栈 C.双向
31、链表D.二叉树解析：39.已知一棵二叉树的先根序列为 ABCDEFK，中根序列为 DGBAFCK，则结点的后根序列为_。（分数：2.00）A.ACFKDBGB.GDBFKCA C.KCFAGDBD.ABCDFKG解析：40.深度为 6的满二叉树中，度为 2的结点个数为_。（分数：2.00）A.31 B.32C.63D.64解析：41.下列数据结构中，能用二分法进行查找的是_。（分数：2.00）A.顺序存储的有序线性表 B.线性链表C.二叉链表D.有序线性表解析：42.以下关于顺序存储结构的叙述中，_是正确的。（分数：2.00）A.每个结点中至少包含一个指针域B.逻辑上相邻的结点物理上不必邻接C
32、.可用于栈、队列、树等逻辑结构的存储表示D.插入、删除运算操作不方便 解析：43.有 3个结点的二叉树有_。（分数：2.00）A.2种形态B.4种形态C.7种形态D.5种形态 解析：44.在一棵二叉树的前序遍历、中序遍历、后序遍历所产生的序列中，所有叶结点的先后顺_。（分数：2.00）A.都不相同B.完全相同 C.前序和中序相同，而与后序不同D.中序和后序相同，而与前序不同解析：45.下列叙述中正确的是_。（分数：2.00）A.线性链表的各元素在存储空间中的位置必须是连续的B.线性链表的头元素一定存储在其他元素的前面C.线性链表中的各元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他元素的前面D.线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的 解析：46.线性表常采用的两种存储结构是_。（分数：2.00）A.顺序存储结构和链式存储结构 B.散列方法和索引方式C.链表存储结构和数组D.线性存储结构和非线性存储结构解析：
