[键入文字]

疑难解答：二分查找法适用于哪种情况？

这个过程一直进行到查找成功或子表长度为0为止。

对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次。

二分查找法只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列（即从小到大，但允许相邻元素值相等）。

1.6排序技术

考点11 交换类排序法

考试链接:

考点11属于比较难的内容，一般以选择题的形式考查，考核几率为30%，分值约为2分，读者应该熟练掌握几种排序算法的基本过程。

冒泡排序法和快速排序法都属于交换类排序法。 （1）冒泡排序法

首先，从表头开始往后扫描线性表，逐次比较相邻两个元素的大小，若前面的元素大于后面的元素，则将它们互换，不断地将两个相邻元素中的大者往后移动，最后最大者到了线性表的最后。

然后，从后到前扫描剩下的线性表，逐次比较相邻两个元素的大小，若后面的元素小于前面的元素，则将它们互换，不断地将两个相邻元素中的小者往前移动，最后最小者到了线性表的最前面。

对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时已经排好序。 在最坏的情况下，冒泡排序需要比较次数为n（n－1）/2。 （2）快速排序法

它的基本思想是：任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。 疑难解答：冒泡排序和快速排序的平均执行时间分别是多少？

2

冒泡排序法的平均执行时间是O（n），而快速排序法的平均执行时间是O（nlog2n）。

1.7 例题详解

一、选择题

【例1】算法的时间复杂度取决于_______。（考点2）

A）问题的规模 B）待处理的数据的初态 C）问题的难度 D）A）和B）

解析：算法的时间复杂度不仅与问题的规模有关，在同一个问题规模下，而且与输入数据有关。即与输入数据所有的可能取值范围、输入各种数据或数据集的概率有关。

答案：D）

【例2】在数据结构中，从逻辑上可以把数据结构分成_______。（考点3）

A）内部结构和外部结构 B）线性结构和非线性结构 C）紧凑结构和非紧凑结构 D）动态结构和静态结构

解析：逻辑结构反映数据元素之间的逻辑关系，线性结构表示数据元素之间为一对一的关系，非线性结构表示数据元素之间为一对多或者多对一的关系，所以答案为B）。

答案：B）

【例3】以下_______不是栈的基本运算。（考点5）

A）判断栈是否为素空 B）将栈置为空栈

6

[键入文字]

C）删除栈顶元素 D）删除栈底元素

解析：栈的基本运算有：入栈，出栈（删除栈顶元素），初始化、置空、判断栈是否为空或满、提取栈顶元素等，对栈的操作都是在栈顶进行的。

答案：D）

【例4】链表不具备的特点是_______。（考点6）

A）可随机访问任意一个结点 B）插入和删除不需要移动任何元素 C）不必事先估计存储空间 D）所需空间与其长度成正比

解析：顺序表可以随机访问任意一个结点，而链表必须从第一个数据结点出发，逐一查找每个结点。所以答案为A）。

答案：A）

【例5】已知某二叉树的后序遍历序列是DACBE，中序遍历序列是DEBAC，则它的前序遍历序列是_______。（考点8）

A）ACBED B）DEABC C）DECAB D）EDBAC

解析：后序遍历的顺序是\左子树－右子树－根结点\；中序遍历顺序是\左子树－根结点－右子树\；前序遍历顺序是\根结点－左子树－右子树\。根据各种遍历算法，不难得出前序遍历序列是EDBAC。所以答案为D）。

答案：D）

【例6】设有一个已按各元素的值排好序的线性表（长度大于2），对给定的值k，分别用顺序查找法和二分查找法查找一个与k相等的元素，比较的次数分别是s和b，在查找不成功的情况下，s和b的关系是_______。（考点9）

A）s=b B）s>b C）s

解析：对于顺序查找，查找不成功时和给定关键字比较的次数为n+1。二分查找查找不成功的关键字比较次数为［log2n］+1。当n≥2时，显然n+1>［log2n］+1。

答案：B）

【例7】在快速排序过程中，每次划分，将被划分的表（或子表）分成左、右两个子表，考虑这两个子表，下列结论一定正确的是_______。（考点11）

A）左、右两个子表都已各自排好序

B）左边子表中的元素都不大于右边子表中的元素 C） 左边子表的长度小于右边子表的长度 D）左、右两个子表中元素的平均值相等

解析：快速排序基本思想是：任取待排序表中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子表，左子表元素的排序码均小于或等于基准元素的排序码，右子表的排序码则大于基准元素的排序码，然后分别对两个子表继续进行排序，直至整个表有序。

答案：B） 二、填空题

【例1】问题处理方案的正确而完整的描述称为_______。（考点1）

解析：计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。 答案：算法

【例2】一个空的数据结构是按线性结构处理的，则属于_______。（考点4）

解析：一个空的数据结构是线性结构或是非线性结构，要根据具体情况而定。如果对数据结构的运算是按线性结构来处理的，则属于线性结构，否则属于非线性结构。

答案：线性结构

【例3】设树Ｔ的度为４，其中度为１、２、３和４的结点的个数分别为４、２、１、１，则Ｔ中叶子结点的个数为_______。（考点7）

解析：根据树的性质：树的结点数等于所有结点的度与对应的结点个数乘积之和加１。

7

[键入文字]

因此树的结点数为１×４＋２×２＋３×１＋４×１＋１＝16。叶子结点数目等于树结点总数减去度不为０的结点数之和，即16－（４＋２＋１＋１）＝８。

答案：8

【例4】二分法查找的存储结构仅限于_______且是有序的。（考点10）

解析：二分查找，也称折半查找，它是一种高效率的查找方法。但二分查找有条件限制：要求表必须用顺序存储结构，且表中元素必须按关键字有序(升序或降序均可）。 答案：顺序存储结构

第二章 程序设计基础

经过对部分考生的调查以及对近年真题的总结分析，笔试部分经常考查的是结构化程序设计的原则、面向对象方法的基本概念，读者应对此部分进行重点学习。

详细重点学习知识点：

1．结构化程序设计方法的四个原则

2．对象、类、消息、继承的概念、类与实例的区别

2.1结构化程序设计

考点1 结构化程序设计的原则

考试链接：

考点1在笔试考试中出现的几率为30%，主要是以选择题的形式出现，分值为2分，此考点为识记内容，读者应该识记结构化程序设计方法的四个主要原则。

20世纪70年代提出了\结构化程序设计\的思想和方法。结构化程序设计方法引入了工程化思想和结构化思想，使大型软件的开发和编程得到了极大的改善。结构化程序设计方法的主要原则为：自顶向下、逐步求精、模块化和限制使用goto语句。

疑难解答：如何进行自顶向下设计方法？

程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标；不要一开始就过多追求众多的细节，先从最上层总目标开始设计，逐步使问题具体化。

2.2面向对象的程序设计

考点2 面向对象方法的基本概念

考试链接：

考点2在笔试考试中，是一个经常考查的内容，在笔试考试中出现的几率为70%，主要是以填空题的形式出现，分值为2分，此考点为重点识记内容，读者应该识记几个基本要素的定义、对象的特征以及消息、继承、类的定义。

误区警示：

当使用\对象\这个术语时，既可以指一个具体的对象，也可以泛指一般的对象，但是当使用\实例\这个术语时，必须是指一个具体的对象。

面向对象方法涵盖对象及对象属性与方法、类、继承、多态性几个基本要素。 （1）对象

通常把对对象的操作也称为方法或服务。

属性即对象所包含的信息，它在设计对象时确定，一般只能通过执行对象的操作来改变。属性值应该指的是纯粹的数据值，而不能指对象。

8

[键入文字]

操作描述了对象执行的功能，若通过信息的传递，还可以为其他对象使用。 对象具有如下特征：标识惟一性、分类性、多态性、封装性、模块独立性。 （2）类和实例

类是具有共同属性、共同方法的对象的集合。它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例。

类是关于对象性质的描述，它同对象一样，包括一组数据属性和在数据上的一组合法操作。 （3）消息

消息是实例之间传递的信息，它请求对象执行某一处理或回答某一要求的信息，它统一了数据流和控制流。

一个消息由三部分组成：接收消息的对象的名称、消息标识符（消息名）和零个或多个参数。

（4）继承

广义地说，继承是指能够直接获得已有的性质和特征，而不必重复定义它们。

继承分为单继承与多重继承。单继承是指，一个类只允许有一个父类，即类等级为树形结构。多重继承是指，一个类允许有多个父类。

（5）多态性

对象根据所接收的消息而做出动作，同样的消息被不同的对象接收时可导致完全不同的行动，该现象称为多态性。 疑难解答：能举一下现实中的对象及其属性和操作吗？

一辆汽车是一个对象，它包含了汽车的属性（如颜色、型号等）及其操作（如启动、刹车等）。一个窗口是对象，它包含了窗口的属性（如大小、颜色等）及其操作（如打开、关闭等）。

2.3 例题详解

一、选择题

【例1】结构化程序设计方法提出于_______。（考点1）

A）20世纪50年代 B）20世纪60年代 C）20世纪70年代 D）20世纪80年代

解析：20世纪70年代提出了\结构化程序设计（structured programming）\的思想和方法。结构化程序设计方法引入了工程化思想和结构化思想，使大型软件的开发和编程得到了极大的改善。

答案：C）

【例2】结构化程序设计方法的主要原则有下列4项，不正确的是_______。（考点1）

A）自下向上 B）逐步求精

C）模块化 D）限制使用goto语句

解析：结构化程序设计方法的主要原则为：

（1）自顶向下：即先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。 （2）逐步求精：对复杂问题，应设计一些子目标作过渡，逐步细化。

（3）模块化：把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。

（4）限制使用goto语句。 答案：A）

【例3】面向对象的开发方法中，类与对象的关系是_______。（考点2）

A）抽象与具体 B）具体与抽象 C）部分与整体 D）整体与部分

解析：现实世界中的很多事物都具有相似的性质，把具有相似的属性和操作的对象归为类，也就是说类是具有共同属性、共同方法的对象的集合，是对对象的抽象。它描述了该对象类型的所有对象的性质，而一个对象则是对应类的一个具体实例。所以本题正确答案为A）项。

答案：A）

9

[键入文字]

二、填空题

【例1】在面向对象方法中，使用已经存在的类定义作为基础建立新的类定义，这样的技术叫做_______。（考点2）

解析：继承是面向对象方法的一个主要特征。继承是使用已有的类定义作为基础建立新类的定义技术。已有的类可当作基类来引用，则新类相应地可当作派生类来引用。

答案：继承

【例2】对象的基本特点包括_______、分类性、多态性、封装性和模块独立性好等5个特点。（考点2）

解析：对象具有如下的基本特点：

（1）标识惟一性。对象是可区分的，并且由对象的内在本质来区分； （2）分类性。可以将具有相同属性和操作的对象抽象成类； （3）多态性。同一个操作可以是不同对象的行为；

（4）封装性。只能看到对象的外部特征，无需知道数据的具体结构以及实现操作的算法； （5）模块独立性。面向对象是由数据及可以对这些数据施加的操作所组成的统一体。 答案：标识惟一性

【例3】对象根据所接收的消息而做出动作，同样的消息被不同的对象所接收时可能导致完全不同的行为，这种现象称为_______。（考点2）

解析：对象根据所接收的消息而做出动作，同样的消息被不同的对象接收时可导致完全不同的行为，该现象称为多态性。 答案：多态性

第三章 软件工程基础

经过对部分考生的调查以及对近年真题的总结分析，笔试部分经常考查的是软件生命周期、软件设计的基本原理，软件测试的目的、软件调试的基本概念，读者应对此部分进行重点学习。

详细重点学习知识点：

1．软件的概念、软件生命周期的概念及各阶段所包含的活动

2．概要设计与详细设计的概念、模块独立性及其度量的标准、详细设计常用的工具 3．软件测试的目的、软件测试的4个步骤、 4．软件调试的任务

3.1软件工程基本概念

考点1 软件定义与软件特点

考试链接：

考点1在笔试考试中，是一个经常考查的内容，考核的几率为70%，主要是以选择题的形式出现，分值为2分，此考点为识记内容，读者应该识记软件的定义，特点及其分类。

软件指的是计算机系统中与硬件相互依存的另一部分，包括程序、数据和相关文档的完整集合。程序是软件开发人员根据用户需求开发的、用程序设计语言描述的、适合计算机执行的指令序列。数据是使程序能正常操纵信息的数据结构。文档是与程序的开发、维护和使用有关的图文资料。可见，软件由两部分组成：

（1）机器可执行的程序和数据；

10