2015 年 3 月新增公共基础 80 道（1）下列叙述中正确的是
A）算法的空间复杂度与算法所处理的数据存储空间有关。
B）算法的空间复杂度是指算法程序控制结构的复杂程度。
C）算法的空间复杂度是指算法程序中指令的条数。
D）压缩数据存储空间不会降低算法的空间复杂度。
（2）下列各组排序法中，最坏情况下比较次数相同的是
A）希尔排序与堆排序B）简单插入排序与希尔排序
C）简单选择排序与堆排序D）冒泡排序与快速排序
（3）设数据集合为 D={ 1, 2, 3, 4, 5 }。下列数据结构 B=(D, R)中为非线性结构的是
A） R={ (1,2), (2,3), (3,4), (4,5) }
B） R={ (1,2), (2,3), (4,3), (3,5) }
C） R={ (5,4), (4,3), (3,2), (2,1) }
D） R={ (2,5), (5,4), (3,2), (4,3) }
（4）某二叉树共有 400 个结点，其中有 100 个度为 1 的结点，则该二叉树中的叶子结点数为
A） 149 B） 150
C） 151 D）不存在这样的二叉树
（5）设栈的存储空间为 S(1:50)，初始状态为 top=51。现经过一系列正常的入栈与退栈操
作后，top=20，则栈中的元素个数为
A） 31 B） 30 C） 21 D） 20
（6）下列叙述中正确的是
A）有两个指针域的链表一定是二叉树的存储结构。
B）有多个指针域的链表一定是非线性结构。
C）有多个指针域的链表有可能是线性结构。 D）只
有一个根结点的数据结构一定是线性结构。
（7）某二叉树共有 150 个结点，其中有 50 个度为 1 的结点，则
A）不存在这样的二叉树。B）该二叉树有 49 个叶子结点。
C）该二叉树有 50 个叶子结点。D）该二叉树有 51 个叶子结点。
（8）循环队列的存储空间为 Q(1:50)，初始状态为 front=rear=50。经过一系列正常的入队与退队操作后，front=rear=25，此后又正常地插入了一个元素，则循环队列中的元素个数为A） 51 B） 50 C） 49 D） 1 （9）某二叉树的前序遍历序列为 ABCDE ，中序遍历序列为 CBADE ，则后序遍历序列为
A） CBADE B） EDABC C） CBEDA D） EDCBA （10）下列叙述中正确的是
A）有两个指针域的链表一定是二叉树的存储结构。
B）循环队列是队列的一种存储结构。
C）二分查找适用于任何存储方式的有序表。
D）所有二叉树均不适合采用顺序存储结构。
（11）下列叙述中正确的是
A）数据的存储结构会影响算法的效率。
B）算法设计只需考虑结果的可靠性。
C）算法复杂度是指算法控制结构的复杂程度。
D）算法复杂度是用算法中指令的条数来度量的。
（12）循环队列的存储空间为 Q(1:40)，初始状态为 front=rear=40。经过一系列正常的入队与退队操作后，front=rear=15，此后又正常地退出了一个元素，则循环队列中的元素个数为A） 9 B） 14 C） 16 D） 39
（13）某二叉树的中序遍历序列为 CBADE ，后序遍历序列为 CBEDA ，则前序遍历序列为
A） ABCDE B） CBEDA C） CBADE D） EDCBA （14）下列叙述中正确的是
A）只有一个根结点和一个叶子结点的必定是线性结构。
B）只有一个根结点的必定是线性结构或二叉树。
C）非线性结构可以为空。
D）没有根结点的一定是非线性结构。
（15）设栈的存储空间为 S(1:60)，初始状态为 top=61。现经过一系列正常的入栈与退栈操作后，top=25，则栈中的元素个数为
A） 25B） 26C） 35D） 36
（16）
A）快速排序B）希尔排序C）简单插入排序D）冒泡排序（17）下列叙述中错误的是
A）有一个以上根结点的必定是非线性结构。
B）有一个以上叶子结点的必定是非线性结构。
C）非线性结构中至少有一个根结点。
D）非线性结构中可以没有根结点与叶子结点。
（18）某二叉树中共有 350 个结点，其中 200 个为叶子结点，则该二叉树中度为 2 的结点数为
A）不可能有这样的二叉树B） 150
C） 199 D） 149
（19）设栈的存储空间为 S(1:50)，初始状态为 top=０。现经过一系列正常的入栈与退栈操
作后，top=30，则栈中的元素个数为
A） 31 B） 30 C） 20 D） 19
（20）
A）快速排序B）简单插入排序C）冒泡排序D）堆排序（21）
A）快速排序B）堆排序C）二分查找法D）顺序查找法（22）下列叙述中错误的是
A）所有二叉树都只能用二叉链表表示
B）二分查找法只适用于顺序存储的线性有序表
C）有多个指针域的链表也有可能是线性结构
D）循环队列是队列的存储结构
（23）某二叉树共有 400 个结点，其中有 99 个度为 1 的结点，则该二叉树中的叶子结点数为A）不可能有这样的二叉树B） 151
C） 150 D） 149
（24）循环队列的存储空间为 Q(1:50)，初始状态为 front=rear=50。经过一系列正常的入队
与退队操作后，front=rear=25，则循环队列中的元素个数为
A） 0 或 50 B） 25 C） 26 D） 49
（25）设数据集合为 D={ 1, 2, 3, 4, 5, 6 }。下列数据结构 B=(D, R)中为线性结构的是 A）
R={ (1,2), (2,3), (4,3), (4,5), (5,6) }
B） R={ (1,2), (2,3), (3,4), (4,5), (6,5) }
C） R={ (5,4), (3,4), (3,2), (4,3), (5,6) }
D） R={ (1,2), (2,3), (6,5), (3,6), (5,4) }
（26）设栈的顺序存储空间为 S(1:m)，初始状态为 top=m+1，则栈中的数据元素个数为
A） top-m+1 B） m-top+1 C） m-top D） top-m （27）某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则前序遍历序列为
A） DEFCBA B） CBAFED C） FEDCBA D） ABCDEF （28）在具有 n 个结点的二叉树中，如果各结点值互不相同，但前序遍历序列与中序遍历序列相同，则该二叉树的深度为（根结点在第1层）
A） n+1B） n-1C） n/2+1D） n
（29）设栈的顺序存储空间为 S(1:m)，初始状态为 top=０，则栈中的数据元素个数为
A） top B） m-top+1C） m-top D） top-m
（30）下列叙述中错误的是
A）不管是顺序栈还是带链的栈，在操作过程中其栈底指针均是固定不变的。
B）带链栈的栈底指针在操作过程中是有可能改变的。
C）不管是顺序栈还是带链的栈，在操作过程中其栈顶指针均是动态变化的。
D）顺序栈的栈底指针在操作过程中是固定不变的。
（31）某二叉树的前序遍历序列与中序遍历序列相同，均为 ABCDEF ，则后序遍历序列为
A） BCDEFA B） CDEFAB C） DEFABC D） FEDCBA （32）下列叙述中正确的是
A）多重链表必定是非线性结构。
B）任何二叉树只能采用链式存储结构。 C）排
序二叉树的中序遍历序列是有序序列。
D）堆可以用完全二叉树表示，其中序遍历序列是有序序列。
（33）
A） 0 B） 1 C） 2 D） 3
（34）下面属于黑盒测试方法的是
A）边界值分析法B）基本路径测试
C）条件覆盖D）条件-分支覆盖
（35）下面属于应用软件的是
A）数据库管理系统B）Windows 7 系统
C）编辑软件 WPS D）安卓(AndroiD）操作系统
（36）在软件设计中，
A）应遵循高内聚低耦合的原则B）应遵循高耦合低内聚的原则
C）模块独立性仅与内聚度相关D）模块内聚与耦合无关
（37）将 C 语言的整数设为整数类 I，则下面属于类 I 的实例的是
A） "0x381"B） 0.381C） 381E-2D） -381 （38）下面描述正确的是
A）软件测试是指动态测试
B）软件测试可以随机地选取测试数据
C）软件测试是保证软件质量的重要手段
D）软件测试的目的是发现和改正错误
（39）下面不属于计算机软件构成要素的是
A）数据B）开发方法C）文档D）程序
（40）软件测试的目的是
A）发现程序中的错误B）发现并改正程序中的错误
C）执行测试用例D）诊断和改正程序中的错误
（41）下面不属于需求分析阶段工作的是
A）需求获取B）可行性研究C）需求分析D）撰写软件需求规格说明书
（42）下面不属于软件开发阶段任务的是
A）需求分析B）测试C）详细设计D）系统维护（43）下面属于“类-对象”主要特征的是
A）对象一致性B）对象无关性C）类的多态性D）类的依赖性（44）
A） 3B） 2C） 1D） 4
（45）结构化程序的基本控制结构仅包含
A）顺序结构B）选择结构
C）循环结构D）顺序、选择和循环结构
（46）通常软件测试实施的步骤是
A）单元测试、集成测试、确认测试B）集成测试、系统测试、确认测试、
C）确认测试、集成测试、单元测试D）单元测试、集成测试、回归测试
（47）下面属于系统软件的是
A）财务管理系统B）数据库管理系统C）编辑软件 Word D）杀毒软件（48）
A） 1 B） 2 C） 3 D） 4
（49）下面图中属于软件设计建模工具的是
A） DFD 图(数据流程图) B）程序流程图（PFD 图）
C）用例图（USE_CASE 图）D）网络工程图
（50）下面属于工具(支撑)软件的是
A）PowerBuilde B）数据库管理系统 C）财务管理系统D） iOS 操作系统（51）下面不属于结构化程序设计原则的是
A）自顶向下B）模块化C）逐步求精D）可封装（52）下面属于软件设计阶段产生的文档是
A）软件确认测试计划B）数据流程图和数据字典
C）详细设计规格说明书D）软件需求规格说明书
（53）软件工程包括的要素是
A）方法、工具和过程B）算法和工具
C）算法和过程D）技术和管理
（54）软件生命周期是指
A）软件的需求分析、设计与实现
B）软件的开发与管理
C）软件的实现和维护
D）软件产品从提出、实现、使用维护到停止使用退役的过程
（55）
A） 1B） 2C） 3D） 5