1、二级公共基础知识-11 及答案解析(总分：30.00，做题时间：90 分钟)一、单项选择题(总题数：10，分数：20.00)1.对长度为 n的线性表排序，在最坏情况下，比较次数不是 n(n-1)/2的排序方法是_。（分数：2.00）A.快速排序B.冒泡排序C.直接插入排序D.堆排序2.下列叙述中正确的是_。（分数：2.00）A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C.顺序存储结构能存储有序表，链式存储结构不能存储有序表D.链式存储结构比顺序存储结构节省存储空间3.假定利用数组 an顺序存储一个栈，利用
2、top表示栈顶指针，用 top=n+1表示栈空，该数组所能存储的栈的最大长度为 n，则表示栈满的条件是_。（分数：2.00）A.top=-1B.top=0C.top1D.top=14.对建立良好的程序设计风格，下面描述正确的是_。（分数：2.00）A.程序应简单、清晰、可读性好B.符号名的命名只要符合语法C.充分考虑程序的执行效率D.程序的注释可有可无5.在软件开发中，需求分析阶段产生的主要文档是_。（分数：2.00）A.可行性分析报告B.软件需求规格说明书C.概要设计说明书D.集成测试计划6.一问宿舍可住多个学生，则实体宿舍和学生之间的联系是_。（分数：2.00）A.一对一B.一对多C.多对
3、一D.多对多7.数据流图是用于表示软件模型的一种图示方法，在下列可采用的绘制方法中，_是常采用的。（分数：2.00）A.自顶向下B.自底向上C.分层绘制D.逐步求精8.下述描述中，不属于数据库管理系统功能的是_。（分数：2.00）A.定义数据库B.提供进程调度C.提供用户接口D.提供并发控制机制9.设有表示学生选课的三张表，学生 S(学号，姓名，性别，年龄，身份证号)，课程 C(课号，课名)，选课 SC(学号，课号，成绩)，则表 SC的关键字(键或码)为_。（分数：2.00）A.课号，成绩B.学号，成绩C.学号，课号D.学号，姓名，成绩10.计算机算法指的是_。（分数：2.00）A.计算方法B
4、.调度方法C.排序方法D.解决某一问题的有限运算序列二、填空题(总题数：5，分数：10.00)11.设某循环队列的容量为 50，头指针。front=5(指向队头元素的前一位置)，尾指针 rear=29(指向队尾元素)，则该循环队列中共有 1 个元素。（分数：2.00）填空项 1:_12.设二叉树根结点的层次为 O，对含有 100个结点的二叉树，可能的最大树深度和最小树深度分别是 1。（分数：2.00）填空项 1:_13.按照软件测试的一般步骤，集成测试应在 1 测试之后进行。（分数：2.00）填空项 1:_14.结构化分析阶段的常用工具有数据流图和 1。（分数：2.00）填空项 1:_15.数
5、据库设计包括概念设计、 1 和物理设计。（分数：2.00）填空项 1:_二级公共基础知识-11 答案解析(总分：30.00，做题时间：90 分钟)一、单项选择题(总题数：10，分数：20.00)1.对长度为 n的线性表排序，在最坏情况下，比较次数不是 n(n-1)/2的排序方法是_。（分数：2.00）A.快速排序B.冒泡排序C.直接插入排序D.堆排序 解析：解析 冒泡排序是一种最简单的交换类排序，它通过相邻元素的交换逐步将线性表变成有序。对于长度为 n的线性表，在最坏的情况下，所有的元素正好为逆序，冒泡排序需要经过 n/2遍的从前往后的扫描和 n/2遍的从后往前的扫描，需要比较的次数为(n-1
6、)+(n-2)+2+1=n(n-1)/2。快速排序也是一种互换类的排序方法，但比冒泡法的速度快，快速排序法的关键是对线性表的分割，以及对其分割出的子表再进行分割。直接插入排序是将无序列表中的各元素一次插入到已经有序的线性表中，这种排序方法的效率与冒泡排序法相同，在最坏的情况下，所有元素正好为逆序，需要比较的次数为 1+2+(n-1)+(n-2)=n(n-1)/2。堆排序属于选择类排序方法，它首先将一个无序序列建成堆，然后将堆顶元素与堆中最后一个元素交换，然后将左、右子树调整为堆，继续交换元素，直至子序列为空。在最坏的情况下，堆排序需要比较的次数为 O(nlog2n)。2.下列叙述中正确的是_。
7、（分数：2.00）A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的 B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C.顺序存储结构能存储有序表，链式存储结构不能存储有序表D.链式存储结构比顺序存储结构节省存储空间解析：解析 在顺序存储结构中所有元素所占的存储空间是连续的，而在链式存储结构中，存储数据结构的存储空间可以不连续，因此选项 A是正确的。线性表在计算机中的存放可以采用顺序存储结构，也可采用链式存储结构，顺序存储结构和链式存储结构都是既可用于线性结构，也可以用于非线性结构，因此选项 B、C 是错误的。采用链式存储结构，不仅要存储元素的值，元素间的逻辑
8、关系还需要通过附设的指针字段来表示，因此，链式存储结构需要更多的存储空间。3.假定利用数组 an顺序存储一个栈，利用 top表示栈顶指针，用 top=n+1表示栈空，该数组所能存储的栈的最大长度为 n，则表示栈满的条件是_。（分数：2.00）A.top=-1B.top=0C.top1D.top=1 解析：4.对建立良好的程序设计风格，下面描述正确的是_。（分数：2.00）A.程序应简单、清晰、可读性好 B.符号名的命名只要符合语法C.充分考虑程序的执行效率D.程序的注释可有可无解析：5.在软件开发中，需求分析阶段产生的主要文档是_。（分数：2.00）A.可行性分析报告B.软件需求规格说明书 C
9、.概要设计说明书D.集成测试计划解析：解析 软件需求规格说明书是需求分析阶段最后的成果，它是作为需求分析的一部分而制定的可交付文档。在概要设计阶段，需要编写的文档有：概要设计说明书、数据库说明书、集成测试计划等。6.一问宿舍可住多个学生，则实体宿舍和学生之间的联系是_。（分数：2.00）A.一对一B.一对多 C.多对一D.多对多解析：解析 一间宿舍对应多个学生，则宿舍和学生之间的联系是一对多，学生和宿舍的联系是多对一。7.数据流图是用于表示软件模型的一种图示方法，在下列可采用的绘制方法中，_是常采用的。（分数：2.00）A.自顶向下B.自底向上 C.分层绘制D.逐步求精解析：8.下述描述中，不
10、属于数据库管理系统功能的是_。（分数：2.00）A.定义数据库B.提供进程调度 C.提供用户接口D.提供并发控制机制解析：9.设有表示学生选课的三张表，学生 S(学号，姓名，性别，年龄，身份证号)，课程 C(课号，课名)，选课 SC(学号，课号，成绩)，则表 SC的关键字(键或码)为_。（分数：2.00）A.课号，成绩B.学号，成绩C.学号，课号 D.学号，姓名，成绩解析：解析 在二维表中凡能唯一标识元组的最小属性集称为关键字，关键字具有标识元组、建立元组间联系等重要作用。此题中，(学号，课号)是表 SC的主键，学号、课号分别为外键，学号是表 S的关键字，课号是表 C的关键字。10.计算机算法
11、指的是_。（分数：2.00）A.计算方法B.调度方法C.排序方法D.解决某一问题的有限运算序列 解析：二、填空题(总题数：5，分数：10.00)11.设某循环队列的容量为 50，头指针。front=5(指向队头元素的前一位置)，尾指针 rear=29(指向队尾元素)，则该循环队列中共有 1 个元素。（分数：2.00）填空项 1:_ （正确答案：24）解析：解析 当 frontrear 时循环队列中元素的个数为 rear-front，当 frontrear 时，循环队列中元素的个数为 N(N为循环队列容量)-front+rear。此题中 front=5rear=29，因此该循环队列中共有 29-
12、5=24个元素。12.设二叉树根结点的层次为 O，对含有 100个结点的二叉树，可能的最大树深度和最小树深度分别是 1。（分数：2.00）填空项 1:_ （正确答案：99 和 6）解析：13.按照软件测试的一般步骤，集成测试应在 1 测试之后进行。（分数：2.00）填空项 1:_ （正确答案：单元）解析：解析 软件测试过程一般按 4个步骤进行，即单元测试、集成测试、验收测试和系统测试。可见集成测试是在单元测试之后进行的，主要进行软件单元的接口测试、全局数据结构测试、边界条件和非法输入的测试。14.结构化分析阶段的常用工具有数据流图和 1。（分数：2.00）填空项 1:_ （正确答案：数据字典）解析：15.数据库设计包括概念设计、 1 和物理设计。（分数：2.00）填空项 1:_ （正确答案：逻辑设计）解析：解析 数据库设计目前一般采用生命周期法将数据库应用系统的开发分解成目标独立的若干阶段：需求解析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段。
