第一部分
二叉树
排序
前序：中左右
中序：左中右
后序：左右中
中：就是根节点的值
左：就是左孩子的值
右：就是右孩子的值
也可以根据根结点的位置判断是哪一种序列排序。
例题1
设某二叉树的后序为CBA，中序为ABC，则该二叉树的前序序列为：ABC
口诀记法：
前中一样，后序倒着写
中后一样，前序倒着写
计算叶子结点
二叉树：
N = n0 + n1+ n2
n0 = n2 +1
n0,n1,n2 分别是0、1、2个孩子的结点，N是总共的结点数
满二叉树
N = 2^n -1
n0 = 2^(n-1) n 为深度或树的层次
例题2
某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是：6
解析：五个度为2 说明n2 = 5 所以叶子结点（即 n0 ） 为 5+1
完全二叉树
中间不能缺结点
例题3
深度为7的完全二叉树中共有125个结点，则该完全二叉树中叶子结点数为：63
解析：在完全二叉树中 n1 = 0 / 1 ，由公式 N = n0 + n1 + n2 得 125 = n0 + 1 +n2 ,
因为 n0 = n2 + 1，所以 125 = n0 +1 +n0 -1 所以 n0 = 63
本题中 n1 = 0 不能等于 1，等于1 时，除以2 不能整除
例题 4
设二叉树共有150个结点，其中度为1 的结点有10个 ，则该二叉树中的叶子结点数为：
解析：在完全二叉树中 n1 = 0 / 1 ，由公式 N = n0 + n1 + n2 得 150= n0 + 10+n2 ,
因为 n0 = n2 + 1，所以 150= n0 +10 +n0 -1 ，n0 = （150-10+1）/ 2
本题中除以2 不能整除，所以不存在这样的二叉树
例题5
深度为7 的满二叉树中，度为 2 的结点个数为 63
解析: n0 = 2^(n-1)
n0 = 2^(7-1) = 64
n0 = n2 +1
所以 ：n2 = 63
二叉树排序
例题6
某二叉树的前序序列为ABCDEFG，中序序列为DCBAEFG，则该二叉树的后序序列为 D
(A） EFGDCBA(B) DCBEKGA
(C）BCDGFEA
(D) DCBGFEA
解析：前序和后序一样，则倒着写，先左后右 则是 BCD GFE A 上面的口诀记法
例题7
某二叉树的前序序列为ABDFHCEG，中序序列为HFDBACEG。该二叉树的后序序列为 A
(A） HFDBGECA
(B)ABCDEFGH
(C) HGFEDCBA
(D） ACEGBDFH
解析：左子树CEG相同，则倒着写GEC 就可以排除
例题8
31、【题7791】设某二叉树中共有140个结点，其中有40个度为1的结点。则， D
(A)该二叉树中有51个叶子结点
(B)该二叉树中有50个叶子结点
(C)该二叉树中有51个度为2的结点
(D)不可能有这样的二叉树
解析：N = n0+ n1+ n2
n0 = n2 +1
140 = n0+ n1+ n0 -1
n1=40
101/2不能整除，所以不存在这样的二叉树
例题9
一棵二叉树共有25个结点，其中5个是叶子结点，则度为1的结点数为 16
用公式计算即可
队列
例题10
某带链的队列初始状态 为 front = rear = NULL。 经过一系列的正常的入队与出队操作后，front = rear = 10，该队列中的元素个数为：1
fornt 和 near 有如下几种情况：
| 初始状态 | 现在个数 |
| 相等 | 0或者1 |
| 相等且初始化相等 | 1 |
| 不相等 | 无法判断 |
例题11
某带链栈的初始状态为top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=10，bottom=20。该栈中的元素个数为 A
(A）不确定(B)10
(C）1
(D)0
例题12
在带链栈中，经过一系列正常的操作后，如果top=bottom，则栈中的元素个数为 0/1
循环队列
例题13
循环队列的存储空间为Q(1:50)，初始状态为front=rear=50。经过一系列正常的入队与退队操作后，friont=rear=25，此后又插入一个元素，则循环队列中的元素个数为 A
(A)1，或50且产生上溢错误
(B)51
(C)26
(D)2
循环队列的元素个数判断：
| rear > front | rear -front |
| rear -front | rear -front+N （N是队列的存储空间） |
| rear = front | 0或者满 |
下列叙述中正确的是 A
(A)在栈中，栈顶指针的动态变化决定栈中元素的个数(B)在循环队列中，队尾指针的动态变化决定队列的长度
(C)在循环链表中，头指针和链尾指针的动态变化决定链表的长度
(D)在线性链表中，头指针和链尾指针的动态变化决定链表的长度
例题 14
下列叙述中正确的是 D
(A)存储空间不连续的所有链表一定是非线性结构(B)结点中有多个指针域的所有链表一定是非线性结构
(C)能顺序存储的数据结构一定是线性结构
(D)带链的栈与队列是线性结构
解析:
栈和队列都是线性结构的，不管有没有带链，
栈: 先进后出；队列：先进先出
顺序存储、链式存储
例题15
下列叙述中正确的是 A
(A)顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的(B)顺序存储结构只针对线性结构，链式存储结构只针对非线性结构
(C）顺序存储结构能存储有序表，链式存储结构不能存储有序表
(D）链式存储结构比顺序存储结构节省存储空间
标准答案:A
例题16
下列叙述中正确的是B
(A)栈与队列都只能顺序存储
(B）循环队列是队列的顺序存储结构(C）循环链表是循环队列的链式存储结构
解析:栈和队列都可以进行顺序存储和链式存储
链表
例题17
下列叙述中错误的是 C
(A)在双向链表中，可以从任何一个结点开始直接遍历到所有结点(B)在循环链表中，可以从任何一个结点开始直接遍历到所有结点
(C)在线性单链表中，可以从任何一个结点开始直接遍历到所有结点
(D)在二叉链表中，可以从根结点开始遍历到所有结点
解析：若从中间结点访问则前面的结点无法访问到双向链表是线性结构；二叉链表是非线性结构，都有两个指针域(前驱 和后继 )。
有指针域的不一定都是线性结构
例题18
设顺序表的长度为n。下列排序方法中最环情况下比较次数小于n(n-1)/2的是 堆排序
| 堆 | nlog2n |
| 快速排序 | n（n -1）/2 |
| 简单插入排序 | n（n -1）/2 |
| 冒泡排序 | n（n -1）/2 |
| 希尔排序 | n^2 |
| 顺序查找 | n |
| 寻找最大（小）项 | n-1 |
| 有序二分查找 | log2n |
例题19
设表的长度为n。下列查找算法中，在最坏情况下，比较次数最少的是 A
(A)有序表的二分查找 (high,low,middle)(B)顺序查找
(C）寻找最大项
(D）寻找最小项
例题20
33、【题7793】设顺序表的长度为n。下列算法中，最坏情况下比较次数小于n的是
寻找最大项
例题21
支持子程序调用的数据结构是 A
(A)栈
(B)树
(C)队列
(D)二叉树
堆
大堆：一组数据由上到下，由左到右，根结点比孩子节点大，且左孩子比右孩子大
小堆：一组数据由上到下，由左到右，根结点比孩子节点小，且左孩子比右孩子大
例题22
11、【题7771】下列各序列中不是堆 C
(A)(91,85,53,36,47,30,24,12)
(B) (91,85,53,47,36,30,24,12)
(C)(47,91,53,85,30,12,24,36)
(D)(91,85,53,47,30,12,24,36)
解析：
图中显示的顺序不对 ，不能组成堆
例题23
下列链表中，其逻辑结构属于非线性结构的是 A
(A)二叉链表 如下图则为二叉链表 是非线性结构
(B)循环链表
(C）双向链表
(D）带链的栈
| 循环链表 | 线性结构 |
| 双向练笔 | 线性结构 |
| 栈 | 线性结构 |
| 列表 | 线性结构 |
| 二叉链表 | 非线性结构 |
例题24
设表的长度为20。则在最外情况下，冒泡排序的比较树为 A
(A)190
( B )20
(C)19
(D）90n(n-1)/2 = 190
例题25
下列叙述中正确的是 D
(A）循环队列有队头和队尾两个指针，因此，循环队列是非线性结构(B)在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况
(C)在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况
(D)循环队列中元素的个数是由队头指针和队尾指针共同决定
例题26
设一棵树的度为3，其中没有度为2的结点，且叶子结点数为6。该树中度为3的结点数为 A
a：不可能存在这样的树b：1
c：2
d：3
例题27
设数据元素的集合D={1，2，3，4，5} ，则满足下列关系R的数据结构中为线性结构的是 B
(A) R={(1,2),(3,4).(5,1)}
(B）R={(1,3),(4,1),(3,2),(5,4)}
(C)R={(1,2),(2,3),(4,5)}
(D)R={(1,3),(2,4),(3,5)}
解析:
例题28
下列叙述中正确的是 B
(A)所谓算法就是计算方法
(B)程序可以作为算法的一种描述方法
(C）算法设计只需考虑得到计算结果
(D）算法设计可以忽略算法的运算时间
时间复杂度和栈
例题29
算法时间复杂度的度量方法是B
(A）算法程序的长度
(B)执行算法所需要的基本运算次数
(C）执行算法所需要的所有运算次数
(D)执行算法所需要的时间
例题30
45、【题7805】算法的有穷性是指 A
(A）算法程序的运行时间是有限的
(B)算法程序所处理的数据量是有限的
(C）算法程序的长度是有限的
(D)算法只能被有限的用户使用
例题31
下列叙述中正确的是 B
(A）有的二叉树也能用顺序存储结构表示
(B)有两个指针域的链表就是二叉链表
(C)多重链表一定是非线性结构
(D)顺序存储结构一定是线性结构
例题
下列关于栈的叙述中，正确的是 C
(A)栈底元素一定是最后入栈的元素
(B）栈顶元素一定是最先入栈的元素
(C）栈操作遵循先进后出的原则
例题32
设栈的顺序存储空间为s(1:m),初始状态为top=0。现经过一系列正常的入栈与退栈操作后，top=m+-1，则栈中的元素个数为 A
(A）不可能(B)m+1
(C)
(D) m
例题33
下列关于栈叙述正确的是 B
(A栈顶元素最先能被删除
(B)栈顶元素最后才能被删除
(C）栈底元素永远不能被删除
例题34
一个栈的初始状态为空。现将元素1.2.3.A,B,C依次入栈，然后再依次出栈，则元素出栈的顺序是
(A）1,2,3,A,B,C(B) C,B,A,1,2,3
(C)C,B,A,3,2,1
(D)1,2,3,C,B,A
先进后出
例题35
下列数据结构中，不能采用顺序存储结构的是 A
(A)非完全二叉树
(B）堆
(C)队列
(D)栈
例题36
在长度为n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中,则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为A
( A) 3n/4(B)n
(C)n/2
(D)n/4
解析：
例题37
算法的空间复杂度是指 A
(A）算法在执行过程中所需要的计算机存储空间(B）算法所处理的数据量
(C）算法程序中的语句或指令条数
(D）算法在执行过程中所需要的临时工作单元数
例题38
下列排序法中，每经过一次元素的交换会产生新的逆序的是 A
(A)快速排序(B)冒泡排序
(C)简单插入排序
(D)简单选择排序
例题39
设栈的顺序存储空间为S(1:50),初始状态为top=0。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为 20
例题40
下列叙述中正确的是
(A）对数据进行压缩存储会降低算法的空间复杂度(B）算法的优化主要通过程序的编制技巧来实现
(C）算法的复杂度与问题的规模无关
(D)数值型算法只需考虑计算结果的可靠性
例题41
设栈的顺序存储空间为S(1:m)，初始状态为top=m+1。现经过一系列正常的入栈与退栈操作后，top=0，则栈中的元素个数为 A
(A)不可能
( B )m+1
(C)1
(D)m
最大为m
例题42
下列叙述中正确的是
(A)在链表中，如果每个结点有两个指针域，则该链表一定是非线性结构 双向链表是线性结构
(B）在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是非线性结构
(C）在链表中，如果每个结点有两个指针域，则该链表一定是线性结构
(D)在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是线性结构
例题43
设二叉树共有375个结点，其中度为2的结点有187个。则度为1的结点个数是
例题44
下列叙述中正确的是
(A）链表结点中具有两个指针域的数据结构可以是线性结构，也可以是非线性结构
(B）线性表的链式存储结构中，每个结点必须有指向前件和指向后件的两个指针
(C）线性表的链式存储结构中，每个结点只能有一个指向后件的指针(D)线性表的链式存储结构中，叶子结点的指针只能是空
例题45
下列叙述中正确的是
(A)在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化(B)在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化
(C)在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化
例题46
下列叙述中正确的是
(A）带链队列的存储空间可以不连续，但队头指针必须大于队尾指针(B）带链队列的存储空间可以不连续，但队头指针必须小于队尾指针
(C）带链队列的存储空间可以不连续，且队头指针可以大于也可以小于队尾指针
例题47
下列算法中均以比较作为基本运算，则平均情况与最环情况下的时间复杂度相同的是
(A)在顺序存储的线性表中寻找最大项(B)在顺序存储的线性表中进行顺序查找
(C)在顺序存储的有序表中进行对分查找
(D）在链式存储的有序表中进行查找
第二部分
程序、软件
例题48
下面属于系统软件的是 A
(A） Oracle数据库管理系统
(B）人事管理系统
(C) WPS编辑软件
(D)杀毒软件
例题49
下面不属于软件需求分析阶段工作的是 B
(A）需求获取(B）需求计划
(C）生成需求规格说明书
(D）需求评审
软件需求分析四个阶段：
例题50
结构化程序包括的基本控制结构是 C
(A）主程序与子程序
(B）选择结构、循环结构与层次结构
(C)顺序结构、选择结构与循环结构
例题 51
下列选项中，不是面向对象主要特征是 （A）
(A）复用(B）抽象(C）继承(D)封装
例题 52
下面描述不属于软件特点的是 D
(A）软件是一种逻辑实体，具有抽象性
(B）软件在使用中不存在磨损、老化问题
(C）软件复杂性高
(D)软件使用不涉及知识产权
例题 53
程序测试的目的是 C
(A)为被测程序设计正确的测试用例
(B）发现并改正程序中的错误
(C)发现程序中的错误
(D)改正程序中的错误
例题 54
下面描述中不属于软件需求分析阶段任务的是 B
(A)撰写软件需求规格说明书
(B)软件的总体结构设计
(C)软件的需求分析
(D)软件的需求评审
例题 55
软件设计一般划分为两个阶段，两个阶段依次是 A
(A）总体设计(概要设计）和详细设计
(B)算法设计和数据设计
(C）界面设计和结构设计
(D）数据设计和接口设计
例题 56
下面属于字符类的实例是 D
(A) '518'
(B）“5” 字符串
(C ) 'nm'
(D)'\n' 转义字符
解析：单引号里面只能是有一个字符，双引号是字符串B项
例题 57
在面向对象方法中，不属于“对象”基本特点的是 A
(A)一致性
(B)分类性
(C)多态性
(D)标识唯一性
例题 58
下面属于白盒测试方法的是 B
(A）边界值分析法(B）基本路径测试(C）等价类划分法(D）错误推测法
白盒：白逻基
黑盒：等边错
例题 59
软件按功能可以分为:应用软件、系统软件和文撑软件(或工具软件)。下面属于应用软件的是C
(A）编译程序
(B）操作系统(C）教务管理系统
(D)汇编程序
例题 60
软件测试用例包括 A
(A）输入数据和预期输出结果
(B）测试计划和测试数据
(C）被测程序和测试规程
(D)输入数据和输出数据
例题 61
计算机软件的构成是 D
(A）源代码
(B）程序和数据
(C）程序和文档
(D)程序、数据及相关文档
例题 62
软件测试:目的是发现错误!
程序调试:目时是改成错误!软件测试的目的是 D
(A）评估软件可靠性
(B）发现并改正程序中的错误
(C）改正程序中的错误
(D)发现程序中的错误
例题 63
在黑盒测试方法中，设计测试用例的主要根据是 B
(A）程序内部逻辑(B）程序外部功能(C）程序数据结构(D)程序流程图
例题 64
软件需求规格说明的内容不包括 A
(A）算法详细设计(B)软件的主要功能(C）软件的性能(D）运行环境
例题 65
下面不属于需求分析阶段任务的是 D
(A）确定软件系统的功能需求
(B）确定软件系统的性能需求
(C）需求规格说明书评审
(D)制定软件集成测试计划
例题 66
在软件开发中，需求分析阶段可以使用的工具是 在软件开发中，需求分析阶段可以使用的工具是 B
(A） N-S图(B） DFD图(C）PAD图(D）程序流程图
例题 67
下面不能作为软件设计工具的是 下面不能作为软件设计工具的是 C
(A )PAD图 (B)程序流程图 (C）数据流程图(DFD图) (D)总体结构图
例题 68
下面对“对象”概念描述错误的是 A
(A）对象不具有封装性
(B）对象是属性和方法的封装体(C）对象间的通信是靠消息传递
D)一个对象是其对应类的实例
1、对象是属性和方法的封装体
2、对象间的通信是靠消息传递
3、一个对象是其对应类的实例
例题 69
软件需求规格说明的内容应包括 A
(A）软件的主要功能(B）算法详细设计(C）E-R模型(D）软件总体结构
例题 70
下面不能作为结构化方法软件需求分析工具的是 A
(A）系统结构图 (B）数据字典(DD) (C）数据流程图(DFD图) (D)判定表
例题 71
结构化程序设计强调 A
(A）程序的易读性
(B）程序的效率
(C）程序的规模
(D）程序的可复用性
例题 72
数据字典(DD)所定义的对象都包含于 A
(A)数据流图(DFD图) (B）程序流程图 (C）软件结构图(D）方框图
例题 73
下面不属于软件开发阶段任务的是 B
(A）测试
(B)可行性研究
(C）设计
(D）实现
例题 74
下面属于应用软件的是 A
(A）人事管理系统 (B ) Oracle数据库管理系统 (C)C++编译系统 (D) ios操作系统
例题 75
软件测试的实施步骤是 A
(A）单元测试，集成测试，确认测试 验收测试
(B）集成测试，确认测试，系统测试
(C）确认测试，集成测试，单元测试
(D)单元测试，集成测试，回归测试
例题 76
软件生命周期是指 A
(A)软件产品从提出、实现、使用、维护到停止使用退役的过程(B)软件的需求分析、设计与实现
(C）软件的开发与管理
(D)软件的实现和维护
例题 77
下面描述错误的是 A
(A)模块的独立性与模块的信息隐蔽和局部化无关 是相关的(B)内聚性和耦合性是模块独立程度的定性度量标准
(C)个模块的内聚性越高则该模块的独立性越强
(D）一个模块的耦合性越高则该模块的独立性越弱
高内聚，低耦合
例题 78
下面叙述中错误的是 A
(A）软件测试的目的是发现错误并改正错误 是软件调试
(B)对被调试的程序进行“错误定位”是程予狗风女少然(C）程序调试通常也称为Debug
(D)软件测试应严格执行测试计划，排除测试的随意性
例题 79
软件生命周期中的活动不包括 A
(A）市场调研
(B）需求分析
(C）软件测试
(D）软件维护
例题 80
例题 81
结构化程序的三种基本结构是 A
(A)顺序、选择和循环
(B)过程、函数和子程序
(C）递归、迭代和回溯
(D）调用、返回和选择
例题 82
下面描述中，不属于软件危机表现的是 A
(A）软件过程不规范
(B）软件开发生产率低(C）软件质量难以控制
(D)软件成本不断提高
例题 83
软件设计中模块划分应遵循的准则是C
(A）高耦合低内聚
(B）高耦舍高内聚(C）低耦合高内聚
(D）低耦合低内聚
例题 84
都是基础的内容。
