1、算法的概念

(1)概念：是指解题方案的准确而完整的描述。

【考题1】在计算机中，算法是指()

A查询方法B加工方法C对解题方案的准确而完整的描述D排序方法

【答案】：C

【考题2】问题处理方案的正确而完整的描述称为。

【答案】：算法

2、算法的特征

(1)算法的特征具有4种：可行性、确定性、有穷性、拥有足够的情报。

① 可行性：在算法的执行过程中，每一个步骤都要可行，可通。经过执行能够得到一个结果。

② 确定性：算法中的每一个步骤都要有确切的含义，不能有二义性，对于相同的输入必须能得出相同的执行结果。

③ 有穷性：一个算法包含的操作步骤是有限的。也就是说，在执行若干个操作步骤之后算法结束，而且每一个步骤都要在合理的时间内完成。

④ 拥有足够的情报：即拥有足够的输入数据。通过大量的给算法输入数据来验证算法输出的结果是否有误。

【考题1】下列选项中不属于算法特征的是()

A无穷性B确定性C可行性D拥有足够的情报

【答案】：A

【考题2】对于一个算法，它必须要在有限步骤合理时间内完成，这属于算法的()

A可行性B确定性C有穷性D拥有足够的情报

【答案】：C

【考题3】在算法中，算法的特征具有可行性、确定性、、拥有足够的情报。

【答案】：有穷性

3、算法的组成

(1)算法的组成有两种：对数据对象的运算和操作、算法的控制结构。

(2)算法的控制结构有3种：顺序结构、选择结构、循环结构。

4、算法的方法

(1)在算法中，对问题描述的方法有6种：列举法、归纳法、递推、递归、减半递推技术、回溯法。

5、算法的复杂度

(1)算法的复杂度是对算法中的各种方法进行衡量的标准。

(2)算法的复杂度有两种：算法的时间复杂度和算法的空间复杂度。

① 算法的时间复杂度：是指执行算法所需要的（计算工作量）基本运算次数。

② 算法的空间复杂度：是指执行算法所需要的内存空间。

【知道】算法时间复杂度的好与坏不会影响空间复杂度的好与坏。

【考题1】算法的时间复杂度是指()

A执行算法程序所需要的时间B算法程序的长度

C算法执行过程中所需要的基本运算次数D算法程序中的指令条数

【答案】：C

【考题2】算法的空间复杂度是指()

A算法程序的长度B算法程序中的指令条数

C算法程序所占的存储空间D算法执行过程中所需要的存储空间

【答案】：D

【考题3】下列叙述中正确的是()

A一个算法的空间复杂度大，则其时间复杂度也必定大

B一个算法的空间复杂度大，则其时间复杂度必定小

C一个算法的时间复杂度大，则其空间可复杂度必定小

D上述三种说法都不对

【答案】：D

【解析】：算法时间复杂度的好与坏不会影响空间复杂度的好与坏。

1、数据结构

(1)数据结构主要研究和讨论三个方面的内容：逻辑结构、存储结构、运算。

【考题1】数据结构包括数据的和数据的存储结构。

【答案】：逻辑结构

2、逻辑结构

(1)满足逻辑结构的的条件：① 表示数据元素的信息；② 表示各数据元素之间的前后件关系。

(2)逻辑结构的分类：线性结构、非线性结构。

①线性结构：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。

在本书中，线性结构主要讲到的有：线性表、栈、队列。

②非线性结构：不满足线性结构条件的就属于非线性结构。

在本书中，非线性结构主要讲到的有：树、二叉树。

【考题1】数据结构中，与所使用的计算机无关的是数据的()

A存储结构B物理结构C逻辑结构D物理和存储结构

【答案】：C

【解析】：逻辑结构讨论的是现实世界中数据与数据之间的关系；存储结构也叫物理结构，指的是逻辑结构在计算机存储空间的存放形式。所以存储结构和计算机有关。A、B和D都不选。

【考题2】以下数据结构中不属于线性结构的是()

A队列B线性表C二叉树D栈

【答案】：C

【考题3】数据的逻辑结构有线性结构和两大类。

【答案】：非线性结构

3、存储结构

(1)概念：数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构)

(2)数据的逻辑结构在计算机存储空间中的存储形式通常有两种：顺序存储结构、链式存储结构。

① 顺序存储结构：数据在存储空间中必须连续，且元素之间一定要有前后件的关系。

② 链式存储结构：数据在存储空间中不一定连续，且各元素的存储顺序是任意的。

(3)两种存储结构的优缺点：

① 顺序存储结构：优点是查找方便。缺点是插入、删除不方便。

② 链式存储结构：优点是插入、删除方便。缺点是查找不方便。

【考题1】数据的存储结构是指()

A存储在外存中的数据B数据所占的存储空间

C数据在计算机中的顺序存储D数据的逻辑结构在计算机中的表示

【答案】：D

【考题2】下列叙述正确的是()

A一个逻辑数据结构只能有一种存储结构

B数据的逻辑结构属于线性结构，存储结构属于非线性结构

C一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率

D一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率

【答案】：D

【解析】：一个逻辑数据结构可以有多种存储结构，例如顺序存储结构和链式存储结构。所以A答案不正确；数据的逻辑结构分为两类：线性结构和非线性结构。存储结构的存储形式可以有多种，例如顺序存储结构和链式存储结构。逻辑结构和存储结构都是我们数据结构的讨论内容。所以B答案不正确；只有D答案正确，因为一个逻辑数据结构可以有多种存储结构，例如顺序存储结构和链式存储结构，且各种存储结构影响数据处理的效率。

【考题3】下列叙述中正确的是()

A算法的效率只与问题的规模有关，而与数据的存储结构无关

B算法的时间复杂度是指执行算法所需要的计算工作量

C数据的逻辑结构与存储结构是一一对应的

D算法的时间复杂度与空间复杂度一定相关

【答案】：B

【解析】：算法的执行效率与数据的存储结构密切相关。所以A不正确；B是正确的；数据的逻辑结构与存储结构中的顺序存储结构是一一对应的（一致的），而与链式存储结构就不一定一一对应了。所以C不正确；算法时间复杂度的好与坏不会影响空间复杂度的好与坏，所以不相关，故D不正确。

【考题4】下列叙述中正确的是()

A程序执行的效率与数据的存储结构密切相关B程序执行的效率只取决于程序的控制结构

C程序执行的效率只取决于所处理的数据量D以上三种说法都不对

【答案】：A

4、线性表

(1)线性表往计算机中进行存放，不仅可以采用顺序存储结构存放，还可以采用链式存储结构存放。

① 顺序表：即线性表采用顺序存储结构存放。

② 线性链表：即线性表采用链式存储结构存放。

(2)顺序表和线性链表的特点：

① 顺序表：随机（访问）存取、查找方便，插入删除不方便、事先估计存储空间。

② 线性链表：顺序（访问）存取、插入删除方便，查找不方便、不必事先估计存储空间。

【考题1】在下面关于线性表的叙述中，选出正确的一项()

A线性表的每一个元素都有一个直接前驱和直接后继

B线性表中至少要有一个元素

C线性表中的元素必须按递增或递减的顺序排列

D除第一个元素和最后一个元素外，每个元素都有一个直接前驱和直接后继

【答案】：D

【解析】：A答案不正确，因为除第一个元素和最后一个元素外，每个元素都有一个直接前驱和直接后继；B答案不正确，线性表中也可以没有元素，此时为空表；C答案不正确，线性表中元素的排列顺序没有要求；D答案正确。

【考题2】下列对线性链表描述正确的是()

A存储空间不一定连续，且各元素的存储顺序是任意的

B存储空间不一定连续，且前件元素一定存储在后件元素的前面

C存储空间必须连续，且前件元素一定存储在后件元素的前面

D存储空间必须连续，且各元素的存储顺序是任意的

【答案】：A

【解析】：线性表采用顺序存储结构存储时，数据在计算机存储空间中必须连续，且元素之间一定要有前后件的关系；线性表采用链式存储结构存储时，数据在计算机存储空间中不一定连续，且各元素的存储顺序是任意的。

【考题3】下列对线性表叙述中，正确的一项是()

A采用链式存储的线性表，必须占用一片连续的存储单元

B采用顺序存储的线性表，便于进行插入和删除操作

C采用链式存储的线性表，不必占用一片连续的存储单元

D链式和顺序存储的线性表，都便于进行插入和删除操作

【答案】：C

【解析】：线性表采用顺序存储结构存储时，数据在计算机存储空间中必须连续，且元素之间一定要有前后件的关系；线性表采用链式存储结构存储时，数据在计算机存储空间中不一定连续，且各元素的存储顺序是任意的。顺序表便于查找，线性链表便于插入和删除操作。

【考题4】线性表的顺序存储结构和线性表的链式存储结构分别是()

A顺序存取的存储结构、顺序存取的存储结构B随机存取的存储结构、顺序存取的存储结构

C随机存取的存储结构、随机存取的存储结构D任意存取的存储结构、任意存取的存储结构

【答案】：B

【解析】：顺序表的特点是随机（访问）存取；线性链表的特点是顺序（访问）存取。

【考题5】链表不具有的特点是()

A不必事先估计存储空间B可随机访问任一元素

C插入删除不需要移动元素D所需空间与线性表长度成正比

【答案】：B

【解析】：线性链表具有的特点：顺序（访问）存取、插入删除方便，查找不方便、不必事先估计存储空间。A、C、D都属于，其D也要知道，线性表多长，在内存空间中也就多长。故B不正确。

【考题6】数据结构分为逻辑结构与存储结构，线性链表属于。

【答案】：存储结构

【解析】：线性链表是线性表在计算机的存储空间中的链式存储结构。所以在计算机的存储空间中，因此属于存储结构。

5、栈

(1)栈是一种特殊的线性表，其特殊性是插入与删除运算都只在线性表的一端进行。即栈的一个考点是：入栈和退栈都是在一端（栈顶）进行的。

(2)栈在计算机中进行存储时通常采用的存储方式有：顺序存储结构、链式存储结构。

(3)栈的原则是：先进后出、后进先出。

【考题1】下列关于栈的描述正确的是()

A在栈中只能插入元素而不能删除元素B在栈中只能删除元素而不能插入元素

C栈是特殊的线性表，只能在一端插入或删除元素

D栈是特殊的线性表，只能在一端插入元素，而不能在一端删除元素

【答案】：C

【解析】：栈的入栈运算和退栈运算都是在一端进行的，即栈顶。

【考题2】下列关于栈的描述中错误的是()

A栈是先进后出的线性表B栈只能顺序存储

C栈具有记忆作用D对栈的插入与删除操作中，不需要改变栈底指针

【答案】：B

【解析】：栈通常采用的存储方式有：顺序存储结构、链式存储结构。所以B不正确；关于C答案同学们也要知道，栈具有记忆作用。

6、队列

(1)队列是一个允许在一端进行插入、而在另一端进行删除的线性表。即队列的一个考点是：队列的入队运算是在队尾进行、退队运算是在队头进行的。

(2)队列在计算机中进行存储时通常采用的存储方式有：顺序存储结构、链式存储结构。

(3)队列的原则是：先进先出、后进后出。

(4)循环队列是队列在计算机存储空间中采用顺序存储结构进行存储的一种形式。

【考题1】下列关于队列的叙述中正确的是()

A在队列中只能插入元素B在队列中只能删除数

C队列是先进先出的线性表D队列是先进后出的线性表

【答案】：C

【解析】：队列是一个先进先出的特殊线性表，其特殊性在于队列的插入是从队尾进行的，删除是从队头进行的。

【考题2】一个队列的入队序列是1，2，3，4，则队列的输出序列是()

A 4，3，2，1B 1，2，3，4C1，4，3，2D 3，2，4，1

【答案】：B

【考题3】栈和队列的共同点是()

A都是先进后出B都是先进先出C只允许在端点处插入和删除元素D没有共同点

【答案】：C

【解析】：栈和队列的共同点都是在端点处进行运算的。栈的插入与删除运算都只在线性表的一端进行；队列是一个允许在一端进行插入、而在另一端进行删除的特殊线性表。而与前面所讲的线性表不同，它可以在任意位置进行插入、删除运算。

【考题4】线性表在计算机中的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的存储结构。

【答案】：顺序

【考题5】设某循环队列的容量为50，头指针front=5(指向队头元素的前一位置)，尾指针rear=29(指向对尾元素)，则该循环队列中共有个元素。

【答案】：24

【解析】：队头指针中不存放元素，从6号空间到29号空间中，总共有24个元素。

7、树和二叉树

(1)树是一种简单的非线性结构。在树中，所有数据元素之间的关系具有明显的层次特性。树的根节点可以没有或有一个。

(2)二叉树的性质：

①2k-1：在二叉树的第k层上，最多有多少的结点。

②2k-1：深度为k的二叉树中，最多有多少个总结点。

③n=n0+n1+n2：二叉树的总结点个数n等于叶子结点个数n0、度为1的结点个数n1、度为2的结点个数n2之和。

④n0=n2+1：叶子结点个数n0等于度为2的结点个数n2加1。

(3)二叉树的特殊情况：满二叉树、完全二叉树。

①满二叉树：每一层的结点都达到了最多。

②完全二叉树：结点按从上到下、从左到右的顺序依次进行排放的二叉树。

(4)二叉树的遍历方法：前序(根、左边、右边)、中序(左、根、右边)、后序(左、右边、根)。

【考题1】一棵二叉树第5层的结点数最多为()

A 8B16C32D 15

【答案】：B

【解析】：利用二叉树的性质2k-1。

【考题2】设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为()

A 12B13C14D 15

【答案】：B

【考题3】设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为()

A 349B350C255D351

【答案】：B

【考题4】某二叉树中度为2的结点有18个，则该二叉树中有个叶子结点。

【答案】：19

【考题5】在深度为7的满二叉树中,叶子结点的个数为()

A 32B31C64D 63

【答案】：C

【解析】：利用二叉树的性质2k-1。27-1

【考题6】在深度为7的满二叉树中,度为2的结点个数为()

A 32B31C64D 63

【答案】：D

【解析】：利用二叉树的性质2k-1。27-1，接着使用n2= n0-1。

【考题7】有如右图二叉树，请分别写出：

前序：中序：后序：

【答案】：ABDYECFXZ、DYBEAFCZX、YDEBFZXCA

8、查找

(1)查找的方法有两种：顺序查找、二分法查找(对分查找)。

①顺序查找：顺序查找在最坏的情况下需要比较n次，即时间复杂度为n。

②二分法查找(对分查找)：二分法查找在最坏的情况下需要比较log2n次，即时间复杂度为log2n。

★ 只有在顺序存储、并且是有序表的情况下才可以进行二分法查找。

【考题1】对长度为n的线性表进行顺序查找，在最坏的情况下所需要的比较次数为()

A Log2nBn/2CnD n+1

【答案】：C

【考题2】下列数据结构中，能用二分法进行查找的是()

A顺序存储的有序线性表B线性链表C二叉链表D有序线性链表

【答案】：A

9、排序

①交换类：★冒泡排序法：n(n-1)/2★快速排序法：最坏情况下也比较n(n-1)/2次

②插入类：★简单插入排序法：n(n-1)/2★希尔排序法：O(n1.5)

③选择类：★简单选择排序法：n(n-1)/2★堆排序法：O(nlog2n)

【考题1】对于长度为n的线性表，在最坏的情况下，下列各排序法所对应的比较次数中正确的是()

A冒泡排序为n/2B冒泡排序为nC快速排序为nD快速排序为n(n-1)/2

【答案】：D

【考题2】希尔排序法属于哪一种类型的排序法()

A交换类排序法B插入类排序法C选择类排序法D建堆排序法

【答案】：B

备考巩固练习

一、选择题

(1)算法一般都可以用哪几种控制结构组合而成()

A循环、分支、递归B顺序、循环、嵌套C循环、递归、选择D顺序、选择、循环

(2)下列叙述正确的是()

A算法的执行效率与数据的存储结构无关

B算法的空间复杂度是指算法程序中指令（或语句）的条数

C算法的有穷性是指算法必须能在执行有限个步骤之后终止D以上三种描述都不对

(3)用链表表示线性表的优点是()

A便于插入和删除操作B数据元素的物理顺序与逻辑顺序相同

C花费的存储空间较顺序存储少D便于随机存取

(4)线性表若采用链式存储结构时，要求内存中可用存储单元的地址()

A必须是连续的B部分地址必须是连续的C一定是不连续的D连续不连续都可以

(5)栈通常采用的两种存储结构是()

A顺序存储结构和链式存储结构B散列方式和索引方式

C链表存储结构和数组D线性存储结构和非线性存储结构

(6)树最适合用来表示()

A有序数组元素B无序数组元素

C元素之间具有分支层次关系的数据D元素之间无联系的数据

(7)在一个二叉树中，第6层的结点数最多有()

A 32B31C64D 63

(8)在一棵深度为6的满二叉树中，叶子结点有()

A 32B31C64D 63

(9)在一棵深度为6的满二叉树中，度为2的结点数有()

A 32B31C64D 63

(10)某二叉树结点的前序序列为EACBDGF，中序序列为ABCDEFG。该二叉树结点的后序序列为()

A BDCAFGEB DBCFAGEC DCEGFABD DEGACFB

(11)已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是()

A cedbaB acbedC decabDdeabc

(12)二分法查找适合用于存储结构为()且按关键字排好序的线性表

A顺序存储B链式存储C顺序和链式存储D索引存储

(13)冒泡排序法的时间复杂度为()

A nB n-1Cn(n-1)/2D (n-1)/2

二、填空题

(1)算法复杂度主要包括时间复杂度和复杂度。

(2)数据的逻辑结构在计算机存储空间中的存放形式称为数据的。

(3)数据结构分为逻辑结构和存储结构，循环队列属于结构。

(4)顺序存储方法是把逻辑上相邻的结点存储在物理位置的存储单元中。

(5)二叉树的遍历可以分为三种：前序遍历、遍历和后序遍历。

(6)设一棵完全二叉树共有500个结点，则在该二叉树中有个叶子结点。

(7)在最坏情况下，堆排序需要比较的次数为。

参考答案

一、选择题

(1)-(5)：DCADA(6)-(10)：CAABA(11)-(13)：AAC

二、填空题

(1)、空间(2)、存储结构(3)、存储(4)、相邻(5)、中序(6)、250(7)、0(nlog2n)

1、 程序设计的风格

(1)程序设计的风格注重的是：清晰第一、效率第二。

(2)要使程序的清晰达到最好，我们在程序设计的过程中将源程序文档化：

① 符号名的命名应具有一定的实际含义，以便于读者理解。

② 程序中的注释要尽量多，程序中的注释又分为：序言性注释、功能性注释。

③ 视觉组织要合理。

【考题1】结构化程序设计主要强调的是()

A程序的规模B程序的易读性C程序的执行效率D程序的可移植性

【答案】：B

【解析】：程序设计主要强调的是：清晰第一、效率第二。程序的易读性、可理解性都表示程序清晰。

【考题2】对建立良好的程序设计风格，下面描述正确的是()

A程序应简单、清晰、可读性好B符号名的命名要符合语法

C充分考虑程序的执行效率D程序的注释可有可无

【答案】：A

【解析】：程序设计主要强调的是：清晰第一、效率第二。程序的易读性、可理解性都表示程序清晰。所以A正确；符号名的命名要有一定的实际含义，应做到见名之意；所以B不正确。

2、 结构化程序设计

(1)结构化程序设计的基本结构有三种：顺序结构、选择结构、循环结构。

(2)结构化程序设计的基本原则有四种：自顶向下、逐步求精、模块化、限制使用goto语句。

【考题1】下列选项中不属于结构化程序设计方法的是()

A自顶向下B逐步求精C模块化D可复用

【答案】：D

3、 面向对象的程序设计

(1)对象：客观世界中任何的实体称为对象。

对象的特点有：标识唯一性、分类性、多态性、封装性、模块独立性好。

(2)类：是具有共同属性，共同方法的对象的集合。即类是从对象抽象出来的。

(3)实例：类中的实例称为对象；对象是类的实例。

(4)消息：是指对象间传递信息的手段。

(5)继承：类之间共享属性和操作的机制称为继承。继承的优点可以提高软件的可重用性。

(6)总结：类具有封装性、模块具有独立性、信息具有隐蔽性、继承具有传递性。

【考题1】在面向对象方法中，描述的是具有相似属性与操作的一组对象。

【答案】：类

【考题2】在面向对象方法中，类的实例称为。

【答案】：对象

【考题3】下面概念中，不属于面向对象方法的是()

A对象B继承C类D过程调用

【答案】：D

【解析】：在面向对象的方法中，主要讲到了：类、对象、实例、消息、继承、多态性、封装性、模块独立性等。

备考巩固练习

一、选择题

(1)在设计程序时，应采纳的原则之一是()

A程序结构应有助于读者理解B不限制goto语句的使用

C减少或取消注解行D程序越短越好

(2)在结构化程序设计思想提出之前，在程序设计中曾强调程序的效率，现在与程序的效率相比，人们更重视程序的()

A安全性B一致性C可理解性D合理性

(3)下面描述中，符合结构化程序设计风格的是()

A使用顺序、选择和重复(循环)三种基本控制结构表示程序的控制逻辑

B模块只有一个入口，可以有多个出口C注重提高程序的执行效率D不使用goto语句

(4)下面对对象概念描述错误的是()

A任何对象都必须有继承性B对象是属性和方法的封装体

C对象间的通讯靠消息传递D操作是对象的动态性属性

(5)面向对象的设计方法与传统的的面向过程的方法有本质不同，它的基本原理是()

A模拟现实世界中不同事物之间的联系B强调模拟现实世界中的算法而不强调概念

C使用现实世界的概念抽象地思考问题从而自然地解决问题

D鼓励开发者在软件开发的绝大部分中都用实际领域的概念去思考

二、填空题

(1)结构化程序设计方法的主要原则可以概括为自顶向下、逐步求精、和限制使用goto语句。

(2)面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个。

(3)在面向对象方法中，信息隐蔽是通过对象的性来实现的。

(4)面向对象的模型中，最基本的概念是对象和。

(5)在面向对象方法中，类之间共享属性和操作的机制称为。

(6)在面向对象方法中,类的实例称为。

(7)源程序文档化要求程序应加注释。注释一般分为序言性注释和注释。

(8)结构化程序设计方法中所指的三种基本数据控制结构包括顺序结构、选择结构、。

参考答案

一、选择题

(1)-(5)：ACAAC

二、填空题

(1)、模块化(2)、实体(3)、封装(4)、类(5)、继承(6)、对象(7)、功能性(8)、循环结构

1、软件

(1)软件是包括程序、数据及其相关文档的完整集合。

(2)软件按功能分为：应用软件、系统软件、支撑软件(工具软件)。

【考题1】下列描述中正确的是()

A程序就是软件B软件开发不受计算机系统的限制

C软件即是逻辑实体，又是物理实体D软件是程序、数据与相关文档的集合

【答案】：D

【解析】：本题选择D，因为软件是包括程序、数据及其相关文档的完整集合；A答案中，程序和软件不能恒等；B答案不正确的原因是：软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制；C答案不正确的原因是：软件是一种逻辑实体，而不是物理实体，具有抽象性。

2、软件危机

(1)软件危机是指在计算机软件的开发和维护过程中所遇到的一系列严重问题。

3、软件工程

(1)定义：为了解决软件危机在软件的开发和维护过程中尽可能多的使用过程科学的原理来指导工作。

(2)3个要素：方法、工具和过程。

(3)核心思想：尽可能多的使用工程科学的原理来指导工作。

(4)达到目标，要研究的内容有：软件开发技术、软件工程管理。

(5)原则：抽象、信息隐蔽、模块化、局部化等。

(6)软件开发环境：是软件工具的集合。

如：CASE(计算机辅助软件工程)

【考题1】下列描述中正确的是()

A软件工程只解决软件项目的管理问题B软件工程主要解决软件产品的生产率问题

C软件开发的主要思想是强调在软件开发的过程中需要应用工程化原则

D软件工程只解决软件开发中的技术问题

【答案】：C

【解析】：软件工程应用计算机科学、数学及管理科学等原理采用工程化原则和方法开发软件系统。它不仅解决软件开发中的技术问题，还解决软件项目的管理问题和软件产品的生产率问题。

【考题2】下面不属于软件工程的3个要素的是()

A工具B过程C方法D环境

【答案】：D

【考题3】在软件研制过程中，CASE是()

A计算机辅助系统过程B CAD和CAM技术发展动力

C正在实验室用的工具D计算机辅助软件工程

【答案】：D

【考题4】软件工程概念的出现源自。

【答案】：软件危机

【解析】：软件工程是在软件危机的情况下提出的。

4、软件生命周期

(1)软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。软件生命周期分为以下三个阶段：

①定义阶段：提出、分析和定义。

②开发阶段：编码、测试。

③维护阶段：维护软件的功能，对软件的功能进行增加和删改。此阶段最重要，而且所花费用也最高。

【考题1】软件开发的结构化生命周期方法将软件生命周期划分成()

A定义、开发、运行维护B设计阶段、编程阶段、测试阶段

C总体设计、详细设计、编程调试D需求分析、功能定义、系统设计

【答案】：A

【考题2】软件生命周期中所花费用最多的阶段是()

A详细设计B软件编码C软件测试D软件维护

【答案】：D

【考题3】下列叙述中正确的是()

A软件交付使用后还需要进行维护B软件一旦交付使用就不需要再进行维护

C软件交付使用后其生命周期就结束D软件维护是指修复程序中被破坏的指令

【答案】：A

【解析】：通常，将软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。软件交付使用后还需要在运行、使用过程中不断维护，根据新提出的需求进行必要而且可能的扩充和删改。

1、需求分析

(1)任务：准确地确定软件系统必须做什么，确定软件系统必须具备那些功能。

(2)阶段：① 需求获取、② 需求分析、③ 编写需求规格说明书、④ 需求评审。

【考题1】在软件生命周期中，能准确地确定软件系统必须做什么和必须具备哪些功能的阶段是()

A概要设计B详细设计C可行性分析D需求分析

【答案】：D

【考题2】软件需求分析四个阶段分为：需求获取、需求分析、编写需求规格说明书以及()

A阶段性报告B需求评审C总结D都不正确

【答案】：B

2、结构化分析方法

(1)在需求分析中，结构化分析方法是常用的一种，其目的是帮助弄清用户对软件的需求。

(2)结构化分析方法中常使用的工具有四种：数据流图、数据字典、判定表、判定树。

①数据流图(DFD)：图形中的箭头表示“数据流”。

②数据字典(DD)：字典的作用是解释；也是结构化分析方法的核心。

【考题1】在结构化方法中，用数据流程图（DFD）作为描述工具的软件开发阶段是()

A可行性分析B需求分析C详细设计D程序编码

【答案】：B

【解析】：在需求分析阶段，常使用的工具是结构化分析方法中的数据流图，所以选择B。

【考题2】数据流图用于抽象描述一个软件的逻辑模型，数据流图由一些特定的图符构成。下列图符名标识的图符不属于数据流图合法图符的是()

A控制流B加工C数据存储D源和潭

【答案】：A

【解析】：数据流图中的图形有加工、数据流、存储文件、源和潭。控制流是属于程序流程图中的。

【考题3】下列工具中属于需求分析常用工具的是()

A PADB PFDC N-SD DFD

【答案】：D

【考题4】下列不属于结构化分析的常用工具的是()

A数据流图B数据字典C判定树DPAD图

【答案】：D

3、软件需求规格说明书

(1)软件需求规格说明书的作用：

①便于用户、开发人员进行理解和交流。

②反映出用户问题的结构，可以作为软件开发工作的基础和依据。

③作为确认测试和验收的依据。

(2)软件需求规格说明书的特点：无歧义性这一特点是整个当中最为重要的。

【考题1】下列叙述中，不属于软件需求规格说明书的作用的是()

A便于用户、开发人员进行理解和交流

B反映出用户问题的结构，可以作为软件开发工作的基础和依据

C作为确认测试和验收的依据D便于开发人员进行需求分析

【答案】：D

1、结构化设计方法

(1)按技术观点来分类：结构设计、数据设计、接口设计、过程设计。

(2)按工程管理角度分类：概要设计、详细设计。

①概要设计：将软件的功能进行分解。

★概要设计的工具有：结构图(SC)。

★结构图中的箭头表示调用关系；深度表示控制的层数；宽度表示跨度最大的模块数目。

②详细设计：确定每个模块的实现算法和局部数据结构。

★详细设计的工具有：程序流程图(PFD)、N-S、PAD、HIPO、判定表、PDL。

★程序流程图中的箭头表示控制流。

★N-S是用方框图来代替传统的程序流程图的。

(3)软件设计的(原则)原理：抽象、模块化、信心隐蔽、模块独立性。

① 其中模块独立性这一原则非常重要，其考点是：模块要想尽可能独立必须要遵循“高内聚、低耦合”的设计原则。

(4)数据流的类型有两类：变换型、事务型。

【考题1】在结构化方法中，软件功能分解属于下列软件开发中的阶段是()

A详细设计B需求分析C总体设计D编程调试

【答案】：C

【解析】：总体设计也称为概要设计。即对软件的总体进行分解。

【考题2】下面不属于软件设计原则的是()

A抽象B模块化C自底向上D信息隐蔽

【答案】：C

【考题3】程序流程图（PFD）中的箭头代表的是()

A数据流B控制流C调用关系D组成关系

【答案】：B

【考题4】为了使模块尽可能独立，要求()

A模块的内聚程度要尽量高，且各模块间的耦合程度要尽量强

B模块的内聚程度要尽量高，且各模块间的耦合程度要尽量弱

C模块的内聚程度要尽量低，且各模块间的耦合程度要尽量弱

D模块的内聚程度要尽量低，且各模块间的耦合程度要尽量强

【答案】：B

【考题5】面向数据流的设计方法,一般把信息流分为，另一种称为事务流。

【答案】：变换流

2、软件测试

(1)软件测试的目的：发现错误。

(2)软件测试的实施(过程)：单元测试、集成测试、确认测试(验收测试)、系统测试。

①单元测试：目的是发现各模块内部可能存在的各种错误。

②集成测试：目的是发现与接口有关的错误。

③确认测试(验收测试)：测试是否满足需求分析。

(3)软件测试的方法：静态测试、动态测试。

①静态测试：不由计算机执行程序代码，主要是通过人看出程序错误。

②动态测试：有计算机执行程序进行测试，是基于计算机的测试。

★白盒测试：内部结构的测试。又称为“路径测试”。

白盒测试的方法又包括：逻辑覆盖测试、基本路径测试等。

★黑盒测试：外部接口的功能测试。

黑盒测试的方法又包括：等价类划分法、边界值分析法、错误推测法、因果图法等。

【考题1】在软件工程中，白箱测试法可用于测试程序的内部结构。此方法将程序看做是()

A循环的集合B地址的集合C路径的集合D目标的集合

【答案】：C

【解析】：白盒(白箱)测试的基本原则是：保证所测模块中每一独立路径至少执行一次。白盒法又叫“路径测试”。

【考题2】软件测试的目的是()

A发现错误B改正错误C改善软件的性能D挖掘软件的潜能

【答案】：A

【考题3】软件测试的内容包括:①集成测试、②验收测试、③系统测试、④单元测试。下列正确的测试顺序是()

A①②③④B④③②①C④①②③D④①③②

【答案】：C

【考题4】若按功能划分，软件测试的方法通常分为白盒测试方法和测试方法。

【答案】：黑盒

【考题5】为了提高测试的效率，应该()

A随机选取测试数据B取一切可能的输入数据作为测试数据

C在完成编码以后制定软件的测试计划D集中对付那些错误群集的程序

【答案】：D

【解析】：经验表明，程序中存在错误的概率与程序中已发现的错误数成正比。这一现象说明，为了提高测试的效率，测试人员应该集中对付那些错误群集的程序。

【考题6】下列叙述中正确的是()

A程序设计就是编制程序B程序的测试必须由程序员自己去完成

C程序经调试改错后还应进行再测试D程序经调试改错后不必进行再测试

【答案】：C

【解析】：程序设计包括程序的结构设计、数据设计、接口设计、过程设计，并不是只有编制程序这么简单，所以选项A叙述错误；在软件测试准则中明确说明程序员应尽量避免检查自己的程序，所以选项B叙述错误；程序经过调试改错后可能会引起其他错误的现象发生，所以程序经过调试改错后必须再进行测试。所以选项D叙述错误。

3、程序调试

(1)程序调试的目的：改正错误。

(2)程序调试的方法：强行排错法、回溯法、原因排除法。

【考题1】软件调试的目的是()

A发现错误B改正错误C改善软件的性能D挖掘软件的潜能

【答案】：B

【考题2】下列不属于软件调试技术的是()

A强行排错法B集成测试法C回溯法D原因排除法

【答案】：B

备考巩固练习

一、选择题

(1)下列关于计算机软件特点的描述,错误的是()

A软件是物理实体,不过其具有抽象性B软件没有明显的制作过程

C软件开发复杂性高,成本昂贵D软件在运行、使用期间不存在磨损和老化的问题

(2)需求分析阶段的任务是确定()

A软件开发方法B软件开发工具C软件开发费用D软件系统功能

(3)在数据流图（DFD）中，带有名字的箭头表示()

A控制程序的执行顺序B模块之间的调用关系C数据的流向D程序的组成成分

(4)软件设计包括软件的结构、数据接口和过程设计，其中软件的过程设计是指()

A模块间的关系B系统结构部件转换成软件的过程描述C软件层次结构D软件开发过程

(5)为了避免流程图在描述程序逻辑时的灵活性，提出了用方框图来代替传统的程序流程图，通常也把这种图称为()

A PAD图B N-S图C结构图D数据流图

(6)开发软件所需高成本和产品的低质量之间有着尖锐的矛盾，这种现象称作()

A软件投机B软件危机C软件工程D软件生产

二、填空题

(1)软件工程研究的内容主要包括：技术和软件工程管理。

(2) Jackson结构化程序设计方法是一种面向的设计方法。

(3)测试的目的是暴露错误，评价程序的可靠性；而的目的是发现错误的位置并改正错误。

(4)软件的调试方法主要有：强行排错法、和原因排除法。

(5)软件维护活动包括以下几类：改正性维护、适应性维护、维护和预防性维护。

参考答案

一、选择题

(1)-(6)：ADCBBB

二、填空题

(1)、软件开发(2)、数据结构(3)、调试(4)、回溯法(5)、完善性

1、数据库系统的组成

(1)数据库系统(DBS)的组成主要有：数据库(DB)、数据库管理系统(DBMS)。

①数据库(DB)：是存储在计算机存储设备上的结构化的相关数据集合。

②数据库管理系统(DBMS)：是对数据库进行建立、使用和维护而配置的软件。其中数据库管理系统是数据库系统的核心。

(2)数据库管理系统提供的数据语言有：数据定义语言(DDL)、数据操纵语言(DML)、数据控制语言(DCL)。

①数据定义语言(DDL)：该语言负责数据的模式定义与数据的物理存储构建。

②数据操纵语言(DML)：该语言负责数据的操纵，包括查询及增删改等操作。

③数据控制语言(DCL)：该语言负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等功能。

【考题1】数据库系统的核心是()

A数据模型B数据库管理系统C软件工具D数据库

【答案】：B

【解析】：数据库系统主要是由数据库和数据库管理系统组成，其中数据库管理系统是数据库系统的核心。

【考题2】下列有关数据库的描述，正确的是()

A数据库是一个DBF文件B数据库是一个关系

C数据库是一个结构化的数据集合D数据库是一组文件

【答案】：C

2、数据管理的发展阶段

(1)数据管理发展至今已经历了三个阶段，分别是：人工管理阶段、文件系统阶段和数据库系统阶段。

(2)数据库系统的特点：

①数据的共享性高

②数据的冗余性低

③数据的独立性高

★其中的数据独立性是指数据与程序之间互不依赖。数据独立性又分为：物理独立性、逻辑独立性。

【考题1】在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。其中数据独立性最高的阶段是()

A数据库系统B文件系统C人工管理D数据项管理

【答案】：A

3、数据库系统的内部体系结构

(1)三级模式：外模式、概念模式、内模式。

①外模式：它是用户可以见到的模式。也称子模式或用户模式。

②内模式：是和物理数据库打交道的。也称物理模式。

(2)两级映射：概念模式->内模式、外模式->概念模式。

【考题1】单个用户使用的数据视图的描述称为()

A外模式B概念模式C内模式D存储模式

【答案】：A

1、E-R模型

(1) E-R模型又叫E-R图，是由一些基本图形组成，图形有：矩形、椭圆、菱形。

① 矩形：表示实体。

② 椭圆：表示属性。

③ 菱形：表示联系。

★实体与实体之间的联系有三种：一对一、一对多、多对多。

【考题1】在E-R图中，实体的属性所对应的图形是()

A矩形B椭圆C菱形D四边形

【答案】：B

【考题2】如果一个工人可管理多个设施，而一个设施只被一个工人管理，则实体"工人"与实体"设备"之间存在联系。

【答案】：一对多

2、数据模型

(1)数据模型分为三类：层次模型、网状模型、关系模型。

① 层次模型：是用树型结构来组织数据的。

② 网状模型：是用图的结构来组织数据的。

③ 关系模型：是用二维表来组织数据的。

(2)其中关系模型就是用二维表来组织数据的，关于关系模型中又涉及到很多的概念，如下：

① 关系：就是一张二维表。

② 属性：二维表中的列(字段)。

③ 元组：二维表中的行(记录)。

④ 域：二维表中列的取值范围。

⑤ 关键字：能区分关系中每一行的列。

⑥ 关系中的数据约束：实体完整性约束、参照完整性约束、用户定义的完整性约束。

【考题1】用树形结构来表示实体之间联系的模型称为()

A关系模型B层次模型C网状模型D数据模型

【答案】：B

【考题2】在关系数据库中，用来表示实体之间联系的是()

A树结构B网结构C线性表D二维表

【答案】：D

【考题3】关系表中的每一横行称为一个()

A元组B字段C属性D码

【答案】：A

【考题4】关系模型的完整性规则是对关系的某种约束条件，包括实体完整性、和自定义完整性。

【答案】：参照完整性

【考题5】数据库管理系统常见的数据模型有层次模型、网状模型和三种。

【答案】：关系模型

3、关系代数

(1)并运算：两个关系进行并运算，就是把两个关系上下合并。如图所示：

RST=R U S

U

(2)差运算：两个关系进行差运算，就是把两个关系中相同的行去掉(即有底纹的去掉)，剩下来的就是结果。

RST=R - S

-

(3)交运算：两个关系进行交运算，就是把两个关系中相同的行留下(即有底纹的留下)，作为结果。

RST=R∩S

∩

(4)专门的关系运算(查询)：选择、投影、连接。

①选择：选择行。

②投影：投影列。

③连接：连接表。用的是笛卡尔积。

4、数据库设计

(1)数据库设计是数据库应用的核心。

(2)数据库设计经历了四个阶段，分别是：需求分析、概念设计、逻辑设计、物理设计。

备考巩固练习

一、选择题

(1)下列叙述中正确的是()

A数据库是一个独立的系统，不需要操作系统的支持B数据库设计是指设计数据库管理系统

C数据库技术的根本目标是要解决数据共享的问题D数据库系统中，数据的物理结构必须与逻辑结构一致

(2) SQL语言又称为()

A结构化定义语言B结构化控制语言C结构化查询语言D结构化操纵语言

(3)下列模式中，能够给出数据库物理存储结构与物理存取方法的是()

A内模式B外模式C概念模式D逻辑模式

(4)索引属于()

A模式B内模式C外模式D概念模式

(5)下述关于数据库系统的叙述中正确的是()

A数据库系统减少了数据冗余B数据库系统避免了一切冗余

C数据库系统中数据的一致性是指数据类型的一致D数据库系统比文件系统能管理更多的数据

(6)在数据管理技术发展过程中，文件系统与数据库系统的主要区别是数据库系统具有()

A数据无冗余B数据可共享C专门的数据管理软件D特定的数据模型

(7)将E-R图转换到关系模式时，实体与联系都可以表示成()

A属性B关系C键D域

(8)关系数据库管理系统能实现的专门关系运算包括()

A排序、索引、统计B选择、投影、连接C关联、更新、排序D显示、打印、制表

(9)数据库概念设计的过程中，视图设计一般有三种设计次序，以下各项中不对的是()

A自顶向下B由底向上C由内向外D由整体到局部

(10)视图设计一般有3种设计次序，下列不属于视图设计的是()

A自顶向下B由外向内C由内向外D自底向上

(11)数据处理的最小单位是()

A数据B数据元素C数据项D数据结构

二、填空题

(1)关系数据库管理系统能实现的专门关系运算包括选择、连接和。

(2)数据库系统的三级模式分别为模式、内部级模式与外部级模式。

(3)是数据库应用的核心。

(4)数据模型按不同的应用层次分为三种类型，它们是数据模型、逻辑数据模型和物理数据模型。

(5)数据库系统中实现各种数据管理功能的核心软件称为。

(6)关系模型的数据操纵即是建立在关系上的数据操纵，一般有、增加、删除和修改四种操作。

(7)数据库设计分为以下6个设计阶段：需求分析阶段、、逻辑设计阶段、物理设计阶段、实施阶段、运行和维护阶段。

(8)数据库保护分为：安全性控制 、、并发性控制和数据的恢复。

(9)一个项目具有一个项目主管，一个项目主管可管理多个项目，则实体"项目主管"与实体"项目"的联系属于的联系。

(10)数据的基本单位是。

(11)数据字典是各类数据描述的集合，它通常包括5个部分，即数据项、数据结构、数据流、和处理过程。

参考答案

一、选择题

(1)-(5)：CCABA(6)-(10)：DBBDB(11)：C

二、填空题

(1)、投影(2)、概念(3)、数据库设计(4)、概念(5)、数据库管理系统(6)、查询

(7)、概念设计阶段(8)、完整性控制(9)、一对多(10)、元素(11)、数据存

点精心提炼

1、计算机数据管理

计算机在数据管理方面经历了由低级到高级的发展过程。分为3个阶段：人工管理阶段、文件系统阶段和数据库系统阶段。

2、数据库系统的组成

(1)数据库系统由5个部分组成：硬件系统、数据库、数据库管理系统、数据库管理员和用户。

(2)其中数据库管理系统是数据库系统的核心。

3、数据模型

(1)实体与实体之间的联系分为三种：一对一、一对多、多对多。

(2)数据模型分为三种：层次模型(树状)、网状模型(图状)、关系模型(二维表)。

4、关系运算

(1)传统的集合运算：并、交、差(三种运算的方法见25页)。

(2)专门的关系运算：选择(行)、投影(列)、连接。

5、数据库的设计原则

为了合理的组织数据，数据库的设计应该遵从以下四个原则：

① 关系数据库的设计应该遵从概念单一化“一事一地”的原则、

② 避免表之间出现重复的字段

③ 表中的字段必须是原始数据和基本数据元素。

④ 用外部关键字保证有关联的表之间的联系。

重点考点解析

【考题1】在关系模型中，每个关系模型中的关键字()

A可由多个任意属性组成B最多由一个属性组成

C可由一个或多个其值能唯一标识关系中任何元组的属性组成D以上说法都不对

【答案】：C

【解析】：关键字是指属性或者属性组的集合，其值能够唯一的标识一个元组。如果一个表中有多个字段都符合关键字的条件，则只能选择一个作为主关键字，其余的作候选关键字。

【考题2】Visual FoxPro是一种关系型数据库管理系统，这里关系通常是指()

A数据库文件(.dbc文件)B一个数据库中两个表之间有一定的关系

C表文件(.dbf文件)D一个表文件中两条记录之间有一定的关系

【答案】：C

【解析】：一个关系就是一张二维表。一张二维表就是一个关系。

【考题3】在Visual FoxPro中以下叙述错误的是()

A关系也被称作表B数据库文件不存储用户数据

C表文件的扩展名是.dbfD多个表存储在一个物理文件中

【答案】：D

【解析】：数据库文件是不存储用户数据的，数据库在Visual FoxPro中主要起到的是管理数据的作用。每个表都是单独存放的。

【考题4】关系运算中的选择运算是()

A从关系中找出满足给定条件的元组的操作B从关系中选择若干个属性组成新的关系的操作

C从关系中选择满足给定条件的属性的操作D A和B都对

【答案】：A

【解析】：从关系中找出满足给定条件的元组的操作称为选择。从关系模式中指定若干个属性组成新的关系的操作称为投影。

【考题5】Visual FoxPro是一种()

A数据库系统B数据库管理系统C数据库D数据库应用系统

【答案】：B

【解析】：无

【考题6】操作对象只能是一个表的关系运算是()

A连接和选择B连接和投影C选择和投影D自然连接和选择

【答案】：C

【解析】：连接是关系的基本操作之一，是一种基于多个关系的运算。

【考题7】在“项目管理器”下为项目建一个新报表，应该使用的选项卡是()

A数据B文档C类D代码

【答案】：B

【解析】：要把“项目管理器”各选项卡里的内容记住。

【考题8】在奥运会游泳比赛中，一个游泳运动员可以参加多项游泳比赛，一个游泳比赛项目可以有多个运动员参加，游泳运动员于游泳比赛项目两个实体之间的联系是联系。

【答案】：多对多

备考巩固练习

一、选择题

(1)数据库DB、数据系统DBS、数据库管理系统DBMS三者之间的关系是()

A DBS包括DB和DBMSB DBMS包括DB和DBS

C DB包括DBS和DBMSD DBS就是DB，也就是DBMS

(2)关系数据库管理系统的3种专门的关系运算不包括()

A选择B投影C比较D连接

(3)下列关于数据库系统的叙述中，正确的是()

A数据库系统只是比文件系统管理的数据更多B数据库系统中数据的一致性是指数据的类型一致

C数据库系统避免了数据冗余D数据库系统减少了数据冗余

(4)数据库管理员的主要职责不包括()

A参与数据库的规划、设计和建立B规划和实施数据库的备份和恢复

C开发数据库应用系统D支持开发和应用数据库技术

(5)在关系的基本运算中，下列属于专门关系运算的是()

A选择、排序B选择、投影C并、差、交D连接、笛卡尔积

(6)在Visual FoxPro中，可以对项目中的数据、文档进行集中管理，并可以对项目进行创建和维护的是()

A工具栏B设计器C文件编辑器D项目管理器

(7)打开Visual FoxPro“项目管理器”的“文档”选项卡，其中包括()

A表单文件B报表文件C标签文件D以上三种文件

(8)在关系运算中，查找满足一定条件的元组，相关的运算称为()

A选择B投影C连接D扫描

(9)在Visual FoxPro中修改数据库、表单、报表等的可视化工具是()

A向导B设计器C生成器D项目管理器

二、填空题

(1)数据处理是指将数据转换成的过程。

(2)在关系数据模型中，二维表的列称为属性，二维表的行称为。

(3)数据库系统由计算机硬件系统、数据库、数据库管理系统、数据库管理员和用户五个部分组成，其核心是。

(4)一个项目具有一个项目主管，一个项目主管可管理多个项目，则实体“项目主管”与实体“项目”的联系属于的联系。

(5) Visual FoxPro的项目文件的扩展名是。

参考答案

一、选择题

(1)-(5)：ACDCB(6)-(9)：DDAB

二、填空题

(1)、信息(2)、元组(3)、数据库管理系统(4)、一对多(5)、.pjx