第9页，共 26 页
C.算法程序所占的存储空间 D.算法执行过程中所需要的存储空间 3.下面叙述正确的是______。
A.算法的执行效率与数据的存储结构无关
B.算法的空间复杂度是指算法程序中指令（或语句）的条数
C.算法的有穷性是指算法必须能在执行有限个步骤之后终止
D.以上三种描述都不对
4.在计算机中，算法是指______。 A. 查询方法 B. 加工方法
C. 解题方案的准确而完整的描述 D. 排序方法
5.算法一般都可以用哪几种控制结构组合而成______。 A. 循环、分支、递归 B. 顺序、循环、嵌套 C. 循环、递归、选择 D. 顺序、选择、循环 6.算法分析的目的是______。(D) A. 找出数据结构的合理性 B. 找出算法中输入和输出之间的关系 C. 分析算法的易懂性和可靠性 D. 分析算法的效率以求改进 7.下列列关于算法的叙述中，正确的是______。
A. 算法是解决问题的实现程序 B. 算法是解决问题的计算方法 C. 程序的实现可以优于算法的设计
D. 算法的基本特征是可行性、确定性、有穷性和拥有足够的情报。 8．下列叙述中正确的是______。 A)线性表是线性结构 B)栈与队列是非线性结构 C)线性链表是非线性结构 D)二叉树是线性结构
9. 数据的存储结构是指______。
B)数据的逻辑结构在计算机中的表示 A)数据所占的存储空间量
C)数据在计算机中的顺序存储方式 D)存储在外存中的数据 10．下列关于队列的叙述中正确的是______。
A)在队列中只能插入数据 B)在队列中只能删除数据 C)队列是先进先出的线性表 D)队列是先进后出的线性表 11．下列关于栈的叙述中正确的是______。
A)在栈中只能插入数据 B)在栈中只能删除数据 C)栈是先进先出的线性表 D)栈是先进后出的线性表 12. 以下数据结构中不属于线性数据结构的是______。
A. 队列 B. 线性表 C. 二叉树 D. 栈 13. 数据的存储结构是指______。
A. 数据所占的存储空间量 B. 数据的逻辑结构在计算机中的表示 C. 数据在计算机中的顺序存储方式 D. 存储在外存中的数据 14. 栈和队列的共同点是______。
A. 都是先进后出 B. 都是先进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点 15. 用链表表示线性表的优点是______。
A. 便于插入和删除操作 B. 数据元素的物理顺序与逻辑顺序相同 C. 花费的存储空间较顺序存储少 D. 便于随机存取 16.链表不具有的特点是______。
A）不必事先估计存储空间 B）可随机访问任一元素 C）插入删除不需要移动元素 D）所需空间与线性表长度成正比 17.如果进栈序列为 e1,e2,e3,e4，则可能的出栈序列是______。
A）e3,e1,e4,e2 B）e2,e4,e3,e1 C）e3,e4,e1,e2 D）任意顺序 18．设有下列二叉树：
第10页，共 26 页 B A C E F 对此二叉树中序遍历的结果为______。
A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA 19．在深度为 5 的满二叉树中，叶子结点的个数为______。
A)32 B)31 C)16 D)15
20.设树 T 的度为 4，其中度为 1，2，3，4 的结点个数分别为 4，2，1，1。则 T 树中叶子结点数为______。
A)8 B)7 C)6 D)5
21. 在一棵二叉树上第 5 层的结点数最多是______。
A. 8 B. 16 C. 32 D. 15
22. 设一棵完全二叉树共有 699 个结点，则在该二叉树中的叶子结点数为______。
A. 349 B. 350 C. 255 D. 351
23. 在深度为 5 的满二叉树中，结点的个数为______。
A. 32 B. 31 C. 16 D. 15
24. 已知二叉树后序遍历序列是 dabec，中序遍历序列是 debac，它的前序遍历序列是______。
A. cedba B. acbed C. decab D. deabc
25.已知二叉树前序遍历序列 deabc，是后序遍历序列是 dabec，中序遍历序列是 ______。
A）debac B）decab C）deabc D）cedba
26.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH 和 DBGEACHF，则该二叉树的后序遍历为______。
A）GEDHFBCA B）DGEBHFCA C）ABCDEFGH D）ACBFEDHG 27.树是结点的集合，它的根结点数目是______。
A）有且只有 1 B）1 或多于 1 C）0 或 1 D）至少 2
28.线性表若采用链式存储结构时，要求内存中可用存储单元的地址______。
A）必须是连续的 B）部分地址必须是连续的 C）一定是不连续的 D）连续不连续都可以 29.下列叙述中，错误的是______。
A）数据的存储结构与数据处理的效率密切相关 B）数据的存储结构与数据处理的效率无关
C）数据的存储结构在计算机中所占的空间不一定是连续的 D）一种数据的逻辑结构可以有多种存储结构
30.对于长度为 n 的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是______。
A）冒泡排序为 n/2 B）冒泡排序为 n C）快速排序为 n D）快速排序为 n(n-1)/2 正确答案：
1- 5：C、D、C、C、D 6-10：D、D、A、B、C 11-15：D、C、B、C、A 16-20：B、B、B、C、A 21-25：B、B、B、D、A 26-30：B、A、D、B、D 二．填空题
1.在计算机中，算法是指解题方案的准确而完整的描述
2.算法的时间复杂度是指算法执行过程中所需要的基本运算次数 3.算法的空间复杂度是指执行过程中所需要的存储空间 4.算法分析的目的是分析算法的效率以求改进
5.算法的基本特征是可行性、确定性、有穷性和拥有足够的情报。 6. 算法的复杂度主要包括时间复杂度和空间复杂度。
7.一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。 8. 栈的基本运算有三种：入栈、退栈和读栈顶元素。 9. 队列主要有两种基本运算：入队运算与退队运算。
第11页，共 26 页 D
10. 数据结构包括数据的逻辑结构、数据的存储结构以及对数据的操作运算。
11. 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构或物理结构。 12. 顺序存储方法是把逻辑上相邻的结点存储在物理位置相邻的存储单元中。
13． 在一个容量为15 的循环队列中， 若头指针front=6， 尾指针rear=9，则该循环队列中共有________个元素。 14．设一棵完全二叉树共有 700 个结点，则在该二叉树中有________个叶子结点。
15．设一棵二叉树的中序遍历结果为 DBEAFC，前序遍历结果为 ABDECF，则后序遍历结果为_________
16． 在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、中序遍历和后序 遍历。
17．在最坏的情况下，冒泡排序的时间复杂度为_______ 18．在最坏情况下，堆排序需要比较的次数为________。
19．在长度为 n 的有序线性表中进行二分查找。最坏的情况下，需要的比较次数为________ 。 20．对于输入为 N 个数进行快速排序算法的平均时间复杂度是_________。
2 程序设计基础
2.1 程序设计设计方法和风格
程序的整体风格应该强调简单和清晰，程序必须是可以理解的。
著名的”清晰第一，效率第二”的论点已成为当今主导的程序设计风格。 要形成良好的程序设计风格，主要应注重和考虑以下因素： 1、源程序文档化 2、数据说明的方法 3、.语句的结构 4、输入和输出
2.2 结构化程序设计
2.2.1 结构化程序设计的原则
结构化程序设计方法的主要原则包括：(重要)
1．自顶向下：程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。不要一开始 就过多追求众多的细节，先从最上层总目标开始设计，逐步使问题具体化。
2．逐步求精：对复杂问题，应设计一些子目标作过渡，逐步细化。
3．模块化：一个复杂问题，肯定是由若干稍简单的问题构成。模块化是把程序要解决的总目标分解为分目
标，再进一步分解为具体的小目标，把每个小目标称为模块。
4．限制使用 goto 语句
2.2.2 结构化程序的基本结构与特点
结构化程序的基本结构为顺序结构、选择结构和重复结构三种。
2.3 面向对象的程序设计
2.3.1 关于面向对象方法
面向对象方法的优点：(重要)
1 与人类习怪的思维方法一致 2 稳定性好 3 可重用性好 4 易于开发大型软件产品 5 可维护性好
2.3.2 面向对象方法的基本概念：用辩证唯物的认识论来认识世界。 1．对象：
对象是面向对象方法中最基本的概念，可以用来表示客观世界中的任何实体，对象是实体的抽象。
面向对象的程序设计方法中的对象是系统中用来描述客观事物的一个实体， 是构成系统的一个基本单位，由 一组表示其静态特征的属性和它可执行的一组操作组成。
对象的基本特征如下：
a.标识惟一性：可通过内在本质来区分。
b.分类性：可以将具有相同属性和操作的对象抽象成类。
第12页，共 26 页
c.多态性：指同一个操作可以是不同对象的行为。
d.封装性：从外面不能直接使用对象的处理能力，也不能直接修改内部状态，对象的内部状态只能由其自身 改变。
e.模块独立性好。 2．类和实例
将属性、操作相似的对象归为类。类是具有共同属性、共同方法的对象的集合。所以，类是对象的抽象，它 描述了属于该对象类型的所有对象的性质。而一个对象则是其对应类的一个实例。 3．消息：
对象间的这种相互合作需要一个机制协助进行， 这样的机制称为“消息”。消息是一个实例与另一个实例之
间传递的信息。 4．继承：
继承是指能够直接获得已有的性质和特征， 而不必重复定义他们。继承是使用已有的类定义作为基础建立新
类的定义技术，以使新类自动拥有旧类的所有特征。 5．多态性：
多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。
历届的考题：
1、下列选项不符合良好程序设计风格的是()[2006.9]
A）源程序要文档化 B）数据说明的次序要规范化
C）避免滥用 goto 语句 D）模块设主地要保证高耦合、高内聚 2、下列选项中不属于结构化程序设计方法的是()[2006.4]
A)自顶向下 B)逐步求精 C)模块化 D)可复用 3、在面向对象的方法中，类的实例称为_____。[2005.4]
4、在面向对象方法中，____描述的是具有相似属性与操作的一组对象。[2006.4]
2.4 精典模拟题
一．选择题
1．结构化程序设计主要强调的是
A)程序的规模 B)程序的易读性 C)程序的执行效率 D)程序的可移植性
2．对建立良好的程序设计风格，下列描述正确的是
A)程序应简单、清晰、可读性好 B)符号名的命名只要符合语法 C)充分考虑程序的执行效率 D)程序的注释可有可无
3．在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发送
A)调用语句 B)命令 C)口令 D)消息 4．信息隐蔽的概念与下述哪一种概念直接相关？
A)软件结构定义 B)模块独立性 C)模块类型划分 D)模块耦合度
5．下面对对象概念描述错误的是
B)对象是属性和方法的封装体 A)任何对象都必须有继承性 C)对象间的通讯靠消息传递 D)操作是对象的动态属性
6. 下面描述中，符合结构化程序设计风格的是______。
A. 使用顺序、选择和重复（循环）三种基本控制结构表示程序的控制逻辑 B. 模块只有一个入口，可以有多个出口
C. 注重提高程序的执行效率 D. 不使用 goto 语句 7.下面概念中，不属于面向对象方法的是______(D)
第13页，共 26 页