1、二级公共基础知识培训l二级公共基础知识分值10分,全部为选择题。l包括内容：包括内容：数据结构及算法（40%）程序设计基础（20%）软件工程基础（20%）数据库设计基础（20%）第一章第一章 数据结构及算法数据结构及算法l算法算法是指解题方案的准确而完整的描述。换句话说，是指解题方案的准确而完整的描述。换句话说，算法是对特定问题求解步骤的一种描述。算法是对特定问题求解步骤的一种描述。l算法不等于程序算法不等于程序，也不等于计算方法。程序的编制，也不等于计算方法。程序的编制不可能优于算法的设计。不可能优于算法的设计。l所谓所谓算法，是一组严谨地定义运算顺序的规则算法，是一组严谨地定义运算顺序的规
2、则，并，并且每一个规则都是有效的，且是明确的，此顺序将且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。在有限的次数下终止。算法定义算法定义l（1）可行性可行性。针对实际问题而设计的算法，执行后能够得到满意。针对实际问题而设计的算法，执行后能够得到满意的结果。的结果。l（2）确定性确定性。每一条指令的含义明确，无二义性。并且在任何条。每一条指令的含义明确，无二义性。并且在任何条件下，算法只有唯一的一条执行路径，即相同的输入只能得出相同件下，算法只有唯一的一条执行路径，即相同的输入只能得出相同的输出。的输出。l（3）有穷性有穷性。算法必须在有限的时间内完成。有两重含义，一是。算法必
3、须在有限的时间内完成。有两重含义，一是算法中的操作步骤为有限个，二是每个步骤都能在有限时间内完成。算法中的操作步骤为有限个，二是每个步骤都能在有限时间内完成。l（4）拥有足够的情报拥有足够的情报。一个算法执行的结果总是及输入的初始数。一个算法执行的结果总是及输入的初始数据有关，不同的输入将会有不同的结果输出。当输入不够或输入错据有关，不同的输入将会有不同的结果输出。当输入不够或输入错误时，算法将无法执行或执行有错。一般说来，当算法拥有足够的误时，算法将无法执行或执行有错。一般说来，当算法拥有足够的情报时，此算法才是有效的；而当提供的情报不够时，算法可能无情报时，此算法才是有效的；而当提供的情报
4、不够时，算法可能无效。效。算法的基本特征算法的基本特征l算法算法时间复杂度时间复杂度是指执行算法所需要的是指执行算法所需要的计算工计算工作量作量，可以用执行算法的过程中所需，可以用执行算法的过程中所需基本运算基本运算的执行次数的执行次数来度量。来度量。l算法算法空间复杂度空间复杂度是指执行这个算法所需要的是指执行这个算法所需要的内内存空间存空间。算法复杂度算法复杂度思考：算法的时间复杂度及空间复杂度是否相关？思考：算法的时间复杂度及空间复杂度是否相关？真题示例真题示例答案：答案：C答案：答案：D(2)算法的时间复杂度是指（算法的时间复杂度是指（）(2010.3)A.算法的执行时间算法的执行时间
5、 B.算法所处理数据和数据量算法所处理数据和数据量 C.算法程序中的语句或指令条数算法程序中的语句或指令条数 D.算法在实现过程中所需要的基本运算次数算法在实现过程中所需要的基本运算次数l数据结构数据结构是指相互有关联的数据元素的集合。是指相互有关联的数据元素的集合。l数据结构主要研究和讨论以下三个方面的问题：数据结构主要研究和讨论以下三个方面的问题：l数据集合中各数据元素之间所固有的逻辑关系，即数据集合中各数据元素之间所固有的逻辑关系，即数据的数据的逻辑逻辑 结构结构。数据的逻辑结构包含：。数据的逻辑结构包含：1）表示数据元素的信息；）表示数据元素的信息；2）表）表 示各数据元素之间的前后件
6、关系。示各数据元素之间的前后件关系。l在对数据进行处理时，各数据元素在计算机中的存储关系，即在对数据进行处理时，各数据元素在计算机中的存储关系，即 数据的存储结构（物理结构）数据的存储结构（物理结构）。数据的存储结构有。数据的存储结构有顺序、链顺序、链 接、索引接、索引等等。l对各种数据结构进行的运算。对各种数据结构进行的运算。l注：逻辑结构和物理结构不是一一对应关系逻辑结构和物理结构不是一一对应关系。数据的逻辑结构反映数据元素之间的逻辑关系，数据的存储结构是数据的物理结构在计算机存储空间中的存放形式。同一种逻辑结构的数据可以采用不同的存储结构，同一种逻辑结构的数据可以采用不同的存储结构，但影
7、响数据处理效率。但影响数据处理效率。数据结构的基本概念数据结构的基本概念 l线性结构线性结构：1）有且只有一个根结点）有且只有一个根结点2）每一个结点最）每一个结点最 多有一个前件，也最多有一个后件。多有一个前件，也最多有一个后件。常见的线性结构有线常见的线性结构有线性表、栈、队列和线性链表等。性表、栈、队列和线性链表等。l非线性结构非线性结构：不满足线性结构条件的数据结构。常见不满足线性结构条件的数据结构。常见 的非线性结构有的非线性结构有树、二叉树和图树、二叉树和图等。等。数据结构的类型数据结构的类型 数据结构分为线性结构和非线性结构，带链的队列属于（数据结构分为线性结构和非线性结构，带链
8、的队列属于（）（）（2006.9）带链的栈属于（带链的栈属于（）(2011.9)l线性表由一组数据元素构成，数据元素的位置只取决于自线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。线性表是由己的序号，元素之间的相对位置是线性的。线性表是由n(n0)个数据元素组成的一个有限序列，个数据元素组成的一个有限序列，表中的每一个数表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件个外，有且只有一个后件。线性表中线性表中数据元素的个数数据元素的个数称为称为线性表的长度。线性表的长度
9、。线性表可以为空表线性表可以为空表。（a1,a2,a3,ai-1,ai,ai+1,an)l线性表是一种存储结构，它的存储方式：线性表是一种存储结构，它的存储方式：顺序顺序和链式和链式。线性表及其顺序存储结构线性表及其顺序存储结构 l特点：特点：（1）线性表中所有元素所占的存储空间是连续的；）线性表中所有元素所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。放的。l顺序表的插入、删除、查找运算顺序表的插入、删除、查找运算 演示演示顺性表的插入运算时需要移动元素，在等概率情况下，平均需要移动顺性表的插入运算时需要移
10、动元素，在等概率情况下，平均需要移动n/2个个元素；进行顺性表的删除运算时也需要移动元素，在等概率情况下，平均元素；进行顺性表的删除运算时也需要移动元素，在等概率情况下，平均需要移动（需要移动（n-1）/2个元素。个元素。插入、删除运算不方便插入、删除运算不方便。线性表顺序存储结构线性表顺序存储结构 真题练习真题练习：在长度为在长度为n的顺序存储的线性表中插入一个元素，的顺序存储的线性表中插入一个元素，最坏情况下需要移动表中最坏情况下需要移动表中()个元素个元素(2011.9)，删除一个元素最坏情况下需要移动的元素个数为（删除一个元素最坏情况下需要移动的元素个数为（）(2012.3)答案答案:
11、n,n-1l是限定是限定在一端进行插入及删除运算在一端进行插入及删除运算的线性表的线性表 l在栈中，允许插入及删除的一端称为在栈中，允许插入及删除的一端称为栈顶栈顶，不允许插入及删除，不允许插入及删除的另一端称为的另一端称为栈底栈底。栈顶元素总是最后被插入的元素，栈底元。栈顶元素总是最后被插入的元素，栈底元素总是最先被插入的元素。即栈是按照素总是最先被插入的元素。即栈是按照“先进后出先进后出”或或“后进后进先出先出”的原则组织数据的。的原则组织数据的。栈具有记忆作用，支持子过程调用栈具有记忆作用，支持子过程调用。l栈的基本运算：栈的基本运算：1）插入元素称为）插入元素称为入栈运算入栈运算；2）
12、删除元素称为）删除元素称为退栈运算退栈运算；3）读栈顶元素是将栈顶元素赋给一个指定的变量，）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。此时指针无变化。l栈的存储方式和线性表类似，也有两种，即栈的存储方式和线性表类似，也有两种，即顺序栈顺序栈和和链式栈链式栈。栈及其基本运算栈及其基本运算（演示）（演示）l一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E 依次入栈，然后再依次出栈，则元素出栈的顺序是（）。A）12345ABCDE B）EDCBA54321 C）ABCDE12345 D）54321EDCBA 答案：答案：Bu假设用一个长度为50的数组（数组元素的下
13、标从0到49）作为栈的存储空间，栈底指针bottom指间栈底元素，栈顶指针top指向栈顶元素，如果bottom=49，top=30（数组下标），则栈中具有_个元素 答案：答案：20真题示例真题示例u下列关于栈的叙述正确的是（下列关于栈的叙述正确的是（）。）。A）栈按）栈按“先进先出先进先出”组织数据组织数据B）栈按）栈按“先进后出先进后出”组织数据组织数据C）只能在栈底插入数据）只能在栈底插入数据D）不能删除数据）不能删除数据u 一个栈的初始状态为空。首先将元素一个栈的初始状态为空。首先将元素5,4,3,2,1依次入栈，然后依次入栈，然后退栈一次退栈一次，再将元素，再将元素 A,B,C,D依次
14、入栈，之后将所有元素依次入栈，之后将所有元素全部退全部退栈栈，则所有元素退栈（包括中间退栈的元素）的顺序为，则所有元素退栈（包括中间退栈的元素）的顺序为_（2010.9）真题示例真题示例答案：答案：1DCBA2345 u下列关于栈的叙述中，正确的是（）A)栈底元素一定是最后入栈的元素 B）栈操作遵循先进后出的原则 C)栈顶元素一定是最先入栈的元素 D)以上三种说法都不对u设栈的存储空间为S（1:40），初始状态为bottom=0,top=0。现经过一系列入栈及出栈运算后，top=20，则当前栈中有_个元素 答案：答案：20真题示例真题示例(2012.9)l是指允许在一端（队尾）进入插入，而在另
15、一端（队头）是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。进行删除的线性表。尾指针尾指针（Rear）指向队尾元素，）指向队尾元素，头头指针指针（front）指向排头元素的前一个位置（队头）。）指向排头元素的前一个位置（队头）。l队列是队列是“先进先出先进先出”或或“后进后出后进后出”的线性表。的线性表。l队列运算包括：队列运算包括：1）入队运算入队运算：从队尾插入一个元素；：从队尾插入一个元素；2）退队运算退队运算：从队头删除一个元素。：从队头删除一个元素。队列及其基本运算队列及其基本运算（演示）（演示）l循环队列循环队列，就是将队列存储空间的最后一个位置绕到第一，就是将
16、队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列中，用环队列中，用队尾指针队尾指针rear指向队列中的队尾元素，用指向队列中的队尾元素，用排排头指针头指针front指向排头元素的前一个位置，因此，从头指指向排头元素的前一个位置，因此，从头指针针front指向的后一个位置直到队尾指针指向的后一个位置直到队尾指针rear指向的位置之指向的位置之间，所有的元素均为队列中的元素。间，所有的元素均为队列中的元素。l循环队列一般用循环队列一般用顺序存储顺序存储。循环队列循环队列（演示）（演示）循环队列中元素的个数循
17、环队列中元素的个数是由队头指针和队尾指是由队头指针和队尾指针共同决定针共同决定l（1）循环队列元素的个数为）循环队列元素的个数为（rear-front+m）%m，其中，其中 m为循环队列容量。为循环队列容量。l（2）如果）如果rear-front0,则循环队列元素个数为则循环队列元素个数为rear-front;如果如果rear-front0,则循环队列元素个数为则循环队列元素个数为rear-front+m;l真题示例：真题示例：（1）设某循环列队的容量为）设某循环列队的容量为50，如果头指针，如果头指针front=45（指向（指向队头元素的前一位置），尾指针队头元素的前一位置），尾指针rear
18、=10（指向队尾元素），（指向队尾元素），则该循环队列中共有则该循环队列中共有_ 个元素。个元素。答案：答案：15 （2010.3）（2）对于循环队列，下列叙述中正确的是（）对于循环队列，下列叙述中正确的是（）lA)队头指针是固定不变的队头指针是固定不变的lB)队头指针是一定大于队尾指针队头指针是一定大于队尾指针lC)队头指针一定小于队尾指针队头指针一定小于队尾指针lD)队头指针可以大于队尾指针，也可以小于队尾指针队头指针可以大于队尾指针，也可以小于队尾指针 计算循环队列个数两种方法：计算循环队列个数两种方法：真题示例：真题示例：（3）下列叙述中正确的是：（）下列叙述中正确的是：（）（2012
19、.3）lA)循环队列是队列的一种顺序存储结构循环队列是队列的一种顺序存储结构 lB)循环队列是队列的一种链式存储结构循环队列是队列的一种链式存储结构lC)循环队列是非线性结构循环队列是非线性结构 D)循环队列是一直逻辑结构循环队列是一直逻辑结构（4）设循环队列的存储空间为设循环队列的存储空间为Q(1:30),初始状态为初始状态为front=rear=30。现经过一系列入队及退队运算后，。现经过一系列入队及退队运算后，front=16，rear=15，则循环队列中有则循环队列中有_个元素。个元素。（2012.3）(5)设循环队列的存储空间为设循环队列的存储空间为Q（1:35），初始状态为），初始
20、状态为ront=rear=35.现经过一系列入队及退队运算后，现经过一系列入队及退队运算后，front=15,rear=15，则循环队列中的元素个数为（则循环队列中的元素个数为（）（2012.9）lA)20B)0或或35C)15D)16答案：答案：A，29,20l线性表顺序存储的线性表顺序存储的缺点缺点：（：（1）插入或删除的运算效率很低插入或删除的运算效率很低。在顺序存储的线性表中，插入或删除数据元素时需要移动大量在顺序存储的线性表中，插入或删除数据元素时需要移动大量的数据元素；（的数据元素；（2）线性表的顺序存储结构下，线性表的）线性表的顺序存储结构下，线性表的存储存储空间不便于扩充空间不
21、便于扩充；（；（3）线性表的顺序）线性表的顺序存储结构不便于对存储存储结构不便于对存储空间的动态分配空间的动态分配。l线性链表：线性链表：线性表的链式存储结构称为线性链表，是一种物理线性表的链式存储结构称为线性链表，是一种物理存储单元上存储单元上非连续非连续、非顺序非顺序的存储结构，数据元素的逻辑顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接来实现的。因此，在链式存储方式中，是通过链表中的指针链接来实现的。因此，在链式存储方式中，每个结点由两部分组成：一部分用于存放数据元素的值，称为每个结点由两部分组成：一部分用于存放数据元素的值，称为数据域数据域；另一部分用于存放指针，称为；另一部
22、分用于存放指针，称为指针域指针域，用于指向该结，用于指向该结点的前一个或后一个结点（即前件或后件）点的前一个或后一个结点（即前件或后件）线性链表线性链表（演示）（演示）线性链表分为线性链表分为单链表、双向链表和循环链表单链表、双向链表和循环链表三种类型三种类型。在在单链表单链表中，每一个结点只有一个指针域，由这个指针中，每一个结点只有一个指针域，由这个指针只能找到其后件结点，而不能找到其前件结点。只能找到其后件结点，而不能找到其前件结点。在某些应用中，对于线性链表中的每个结点设置两个指在某些应用中，对于线性链表中的每个结点设置两个指针，一个称为左指针，指向其前件结点；另一个称为右针，一个称为左
23、指针，指向其前件结点；另一个称为右指针，指向其后件结点，这种链表称为指针，指向其后件结点，这种链表称为双向链表双向链表 l下列叙述中正确的是（下列叙述中正确的是（）（2010.9）A）线性表的链式存储结构及顺序存储结构所需要的存储）线性表的链式存储结构及顺序存储结构所需要的存储空间是空间是相同相同的的B）线性表的链式存储结构所需要的存储空间一般要）线性表的链式存储结构所需要的存储空间一般要多于多于顺序存储结构顺序存储结构C）线性表的链式存储结构所需要的存储空间一般要）线性表的链式存储结构所需要的存储空间一般要少于少于顺序存储结构顺序存储结构D）上述三种说法都不对）上述三种说法都不对真题示例真题
24、示例答案：答案：Bl下列关于线性链表的叙述中，正确的是（）下列关于线性链表的叙述中，正确的是（）（2011.9）A)各数据结点的存储空间可以不连续，但它们的存储顺序及各数据结点的存储空间可以不连续，但它们的存储顺序及逻辑顺序必须一致逻辑顺序必须一致B)各数据结点的存储顺序及逻辑顺序可以不一致，但它们的各数据结点的存储顺序及逻辑顺序可以不一致，但它们的存储空间必须连续存储空间必须连续C)进行插入及删除时，不需要移动表中的元素。进行插入及删除时，不需要移动表中的元素。D)以上三种说法都不对以上三种说法都不对真题示例真题示例答案：答案：Cl树是一种简单的非线性结构。在树结构中，每一个结点只有一个前件
25、，称为父结点父结点。没有前件的结点只有一个，称为树的根结点，简称树的根树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点叶子结点。l在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为所有结点中最大的度称为树的度。树的最大层次称为树的深度树的深度。树的基本概念树的基本概念判断哪些结点是根及叶子结点？树判断哪些结点是根及叶子结点？树的度及深度是？的度及深度是？真题练习真题练习某系统总体结构图如下图所示某系统总体结构图如下图所示：该系统总体结构图的深度是（该系统总体结构图的深度是（）（2011.9）A)7 B)6 C)3
26、 D)2答案：答案：C l二叉树是一种很有用的非线性结构，它具有以下两个特二叉树是一种很有用的非线性结构，它具有以下两个特点：点：1）非空二叉树只有一个根结点非空二叉树只有一个根结点；2）每一个结点最每一个结点最多有两棵子树多有两棵子树，且分别称为该结点的左子树及右子树。，且分别称为该结点的左子树及右子树。l二叉树的基本性质二叉树的基本性质：二叉树及其基本性质二叉树及其基本性质计算计算：深度为深度为5的二叉树最多有的二叉树最多有_个结点，其中第个结点，其中第4层上层上最多有最多有_个结点个结点真题示例真题示例l某二叉树中有n 个度为2 的结点，则该二叉树中的叶子结点数为（）。A）n+1 B）n
27、-1 C）2n D）n/2l某二叉树有某二叉树有5个度为个度为2的结点以及的结点以及3个度为个度为1的结点，则该的结点，则该二叉树中共有二叉树中共有_个结点个结点 l某二叉树共有7个结点个结点，其中叶子结点只有叶子结点只有1个个，则该二叉树的深度为（假设根结点在第1层）A）3 B）4 C）6 D）7答案：答案：A 14 D 真题示例真题示例l一棵二叉树共有一棵二叉树共有25个节点个节点，其中，其中5个个是是叶子节点叶子节点，那么，那么度为度为1的节点数为（的节点数为（）A)4 B)6 C)10 D)16l一棵二叉树中共有一棵二叉树中共有70个叶子结点及个叶子结点及80个度为个度为1的结点，的结
28、点，则该二叉树中的总结点数为（则该二叉树中的总结点数为（）A）219 B）221 C）229 D）231答案：答案：D A l满二叉树满二叉树：除最后一层外，每一层上的所有结点都有两个：除最后一层外，每一层上的所有结点都有两个子结点。子结点。l完全二叉树完全二叉树：除最后一层外，每一层上的结点数均达到最：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。大值；在最后一层上只缺少右边的若干结点。完全二叉树及满二叉树完全二叉树及满二叉树l第k层上有 个结点l深度为m的满二叉树共有 个结点)1(21kk满二叉树特性满二叉树特性12m真题练习：深度为5 的满二叉树有_个叶子
29、结点注：一般二叉树通常采用链式存储结构，对于满二叉树及完全二叉树来说，一般二叉树通常采用链式存储结构，对于满二叉树及完全二叉树来说，可以按层序进行顺序存储可以按层序进行顺序存储。这样，不仅节省了存储空间，又能方便地确定每一个结点的父结点及左右子结点的位置，但顺序存储结构对于一般的二叉树不适用。二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历可以分为以下三种：l（1）前序遍历（）前序遍历（DLR）：若二叉树为空，则结束返回。否则：首先访问根结点，然后遍历左子树，最后遍历右子树首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后
30、遍历右子树。l（2）中序遍历（）中序遍历（LDR）：若二叉树为空，则结束返回。否则：首先遍历左子树，然后访问根结点，最后遍历右子树首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。l（3）后序遍历（）后序遍历（LRD）：若二叉树为空，则结束返回。否则：首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。二叉树遍历二叉树遍历二叉树遍历二叉树遍历RACDBEFG练习：对该二叉树进行前序练习：对该二叉树进行前序/中序中序/后序遍历结果后序遍历结果?真题练习
31、：真题练习：真题练习：真题练习：设二叉树如下：设二叉树如下：对该二叉树进行后序遍历的结果为对该二叉树进行后序遍历的结果为（）。答案答案;EDBGHFCA l一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为 _。真题练习：真题练习：答案：答案：DEBFCAl下列链表中，其逻辑结构属于非线性结构的是（）（2012.9）l A)双向链表B)带链的栈C)二叉链表D)循环链表真题练习：真题练习：答案：答案：Cl查找：查找：根据给定的某个值，在查找表中确定一个其关键字根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。等于给定值的数据元素。l查找结果：查找
32、结果：（查找成功：找到；查找不成功：没找到。）（查找成功：找到；查找不成功：没找到。）l平均查找长度平均查找长度：查找过程中关键字和给定值比较的平均次：查找过程中关键字和给定值比较的平均次数。数。查找技术查找技术l基本思想：基本思想：从表中的第一个元素开始，将给定的值及表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。l在平均情况下，利用顺序查找法在线性表中查找一个元素，大约要及线性表中一半的元素进行比较，最坏情况下需要比较最坏情况下需要比较n次次。l顺序查找一个具有n个元素的线性表，其平均复杂度为平均复杂度为O（n），），平均长度为（平
33、均长度为（n+1）/2.顺序查找顺序查找l思想：思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。l前提：前提：必须在具有顺序存储结构的有序表顺序存储结构的有序表中进行。l查找过程：（演示过程）查找过程：（演示过程）l1）若中间项（中间项mid=(n-1)/2，mid的值四舍五入取整）的值等于x，则说明已查到；l2）若x小于中间项的值，则在线性表的前半部分查找；l3）若x大于中间项的值，则在线性表的后半部分查找。l特点：比顺序查找方法效率高。最坏的情况下，需要比较log2n次。l二分法查找只适用于顺序存储的线性表，且表中元素必须按关二分法查找只适用于顺序存储的
34、线性表，且表中元素必须按关键字有序（升序）排列键字有序（升序）排列。对于无序线性表和线性表的链式存储结构只能用顺序查找。在长度为n的有序线性表中进行二分法查找，其时间复杂度为O（log2n）。二分法查找二分法查找(演示演示)l排序排序是指将一个无序序列整理成按值非递减顺序排列的有是指将一个无序序列整理成按值非递减顺序排列的有序序列，即是将无序的记录序列调整为有序记录序列的一序序列，即是将无序的记录序列调整为有序记录序列的一种操作。种操作。l1、交换类排序法交换类排序法（方法：冒泡排序，快速排序）。（方法：冒泡排序，快速排序）。l2、插入类排序法插入类排序法（方法：简单插入排序，希尔排序）。（方
35、法：简单插入排序，希尔排序）。l3、选择类排序法选择类排序法（方法：简单选择排序，堆排序）。（方法：简单选择排序，堆排序）。排序技术排序技术排序技术总结排序技术总结（1）下列排序方法中，最坏情况下比较次数最少的是）下列排序方法中，最坏情况下比较次数最少的是 A）冒泡排序）冒泡排序 B）简单选择排序）简单选择排序 C）直接插入排序）直接插入排序 D）堆排序）堆排序真题练习真题练习冒泡排序、直接插入排序、简单选择排序冒泡排序、直接插入排序、简单选择排序最坏情况下都需要比较最坏情况下都需要比较n(n-1)/2.堆排序法，堆排序法，最坏情况需要最坏情况需要o(nlong2n)次比较次比较（2）对长度为
36、对长度为10 的线性表进行冒泡排序，最坏情况的线性表进行冒泡排序，最坏情况下需要比较的次数为下需要比较的次数为 _。第二章第二章 程序设计基础程序设计基础l主要强调主要强调“清晰第一、效率第二清晰第一、效率第二”。l主要应注重和考虑下述一些因素主要应注重和考虑下述一些因素：l（1）源程序文档化。）源程序文档化。（2）数据说明）数据说明 （3）语句的结构。）语句的结构。（4）输入和输出。）输入和输出。程序设计风格程序设计风格l结构化程序设计方法的主要原则可以概括为：自顶向下自顶向下，逐步求精逐步求精，模块化模块化，限制使用限制使用goto语句语句。l（1）自顶向下自顶向下。程序设计时，应先考虑总
37、体，后考虑细节；先考虑全局目标，后考虑局部目标。不要一开始就过多追求众多的细节，先从最上层总目标开始设计，逐步使问题具体化。l（2）逐步求精逐步求精。对复杂问题，应设计一些子目标作过渡，逐步细化。l（3）模块化模块化。一个复杂问题，肯定是由若干稍简单的问题构成。模块化是把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。l（4）限制使用限制使用goto语句语句。结构化程序设计结构化程序设计l1）顺序结构顺序结构。一种简单的程序设计，即按照程序语句行的自然顺序，一条语句一条语句地执行程序，它是最基本、最常用的结构。2）选择结构选择结构。又称分支结构分支结构，包
38、括简单选择和多分支选择结构，可根据条件，判断应该选择哪一条分支来执行相应的语句序列。3）重复结构重复结构。又称循环结构循环结构，可根据给定的条件，判断是否需要重复执行某一相同的或类似的程序段。结构化程序基本结构结构化程序基本结构流程图流程图语句语句1语句语句2判读下列流程图分别是什么结构？判读下列流程图分别是什么结构？(1)下列选项中不属于结构化程序设计原则的是（）下列选项中不属于结构化程序设计原则的是（）（2009.9）A)可封装可封装B)自顶向下自顶向下 C)模块化模块化 D)逐步求精逐步求精（2）结构化程序所要求的基本结构不包括）结构化程序所要求的基本结构不包括（）（）(2011.3)A
39、）顺序结构）顺序结构 B）GOTO跳转跳转 C）选择（分支）结构）选择（分支）结构 D）重复（循环）结构）重复（循环）结构真题练习真题练习l客观世界中任何一个事物都可以被看成是一个对象，面向面向对象方法的本质就是主张从客观世界固有的事物出发来构对象方法的本质就是主张从客观世界固有的事物出发来构造系统，提倡人们在现实生活中常用的思维来认识、理解造系统，提倡人们在现实生活中常用的思维来认识、理解和描述客观事物和描述客观事物，强调最终建立的系统能够映射问题域。也就是说，系统中的对象及对象之间的关系能够如实地反映问题域中固有的事物及其关系。面向对象程序设计面向对象程序设计l面向对象方法的主要优点：（1
40、）及人类习惯的思维方法及人类习惯的思维方法一致一致；（；（2）稳定性好稳定性好；（；（3）可重用性好可重用性好；（；（4）易于开易于开发大型软件产品发大型软件产品；（；（5）可维护性好可维护性好。l面向对象的程序设计主要考虑的是提高软件的可重用性提高软件的可重用性。l面向对象三大特征：封装性、继承性、多态性封装性、继承性、多态性。l对象对象是面向对象方法中最基本的概念，可以用来表示客观世界中的任何实体，对象是实体的抽象。面向对象的程序设计方法中的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，由一组表示其静态特征的属性和它可执行的一组操作组成。对象是属性和方法的封装体对象是属
41、性和方法的封装体。l属性属性即对象所包含的信息，它在设计对象时确定，一般只能通过执行对象的操作来改变。l操作操作描述了对象执行的功能，操作也称为方法或服务。操作是对象的动态属性。一个对象由对象名对象名、属性属性和和操作操作三部分组成。面向对象程序设计有关概念面向对象程序设计有关概念l（1）标识惟一性标识惟一性。指对象是可区分的，并且由对象的内在本质来区分，而不是通过描述来区分。l（2）分类性分类性。指可以将具有相同属性的操作的对象抽象成类。l（3）多态性多态性。指同一个操作可以是不同对象的行为。l（4）封装性封装性。从外面看只能看到对象的外部特性，即只需知道数据的取值范围和可以对该数据施加的操
42、作，根本无需知道数据的具体结构以及实现操作的算法。对象的内部，即处理能力的实行和内部状态，对外是不可见的。从外面不能直接使用对象的处理能力，也不能直接修改其内部状态，对象的内部状态只能由其自身改变。信息隐蔽是通过对象的封装性来实现信息隐蔽是通过对象的封装性来实现的的 l（5）模块独立性好模块独立性好。对象是面向对象的软件的基本模块，它是由数据及可以对这些数据施加的操作所组成的统一体，而且对象是以数据为中心的，操作围绕对其数据所需做的处理来设置，没有无关的操作。从模块的独立性考虑，对象内部各种元素彼此结合得很紧密，内聚性强。对象基本特点对象基本特点l类是指具有共同属性、共同方法的对象的集合。所以
43、类是对象类是对象的抽象，对象是对应类的一个实例的抽象，对象是对应类的一个实例。消息是一个实例及另一个实例之间传递的信息消息是一个实例及另一个实例之间传递的信息。l在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发送消息。继承继承是指能够直接获得已有的性质和特征，而不必重复定义他们。继承分单继承和多重继承单继承和多重继承。单继承指一个类只允许有一个父类，多重继承指一个类允许有多个父类。l 类的继承性继承性是类之间共享属性和操作的机制，它提高了软件的可重用性。多态性多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。面向对象程序设计有关概念面向对象程序设计有关概念l面向对
44、象方法中，继承是指（）（2010.9）A）一组对象所具有的相似性质 B）一个对象具有另一个对象的性质 C）各对象之间的共同性质 D）类之间共享属性和操作的机制真题示例真题示例答案：答案：Dl下列选项中属于面向对象设计方法主要特征的是()(2011.9)A)继承 B)自顶向下 C)模块化 D)逐步求精答案：答案：Al常见的软件工程方法有结构化方法和面向对象方法，类、继承以及多态性等概念属于_。(2012.3)第三章第三章 软件工程基础软件工程基础l计算机软件是包括计算机软件是包括程序程序、数据数据及相关及相关文档文档的完整集合。的完整集合。l软件按功能分为软件按功能分为应用软件应用软件、系统软件
45、系统软件、支撑软件支撑软件（或工具（或工具软件）软件）软件有关概念软件有关概念真题练习真题练习（1）软件按功能可以分为：应用软件、系统软件和支撑软件（或）软件按功能可以分为：应用软件、系统软件和支撑软件（或工具软件）。下面属于工具软件）。下面属于系统软件系统软件的是（的是（）（2010.3）A)编辑软件编辑软件 B)操作系统操作系统 C)教务管理系统教务管理系统 D)浏览器浏览器(2)软件按功能可以分为应用软件、系统软件和支撑软件（或工具软件按功能可以分为应用软件、系统软件和支撑软件（或工具 软件）。下面属于软件）。下面属于应用软件应用软件的是（的是（）（2011.9）A)学生成绩管理系统学生
46、成绩管理系统 B)C语言编译程序语言编译程序 C)UNIX操作系统操作系统 D)数据库管理系统数据库管理系统答案答案：（1）B （2）Al软件危机软件危机是泛指是泛指在计算机软件的开发和维护过程中所遇到的在计算机软件的开发和维护过程中所遇到的一系列严重问题一系列严重问题。主要表现在。主要表现在成本、质量、生产率成本、质量、生产率等问题。等问题。l软件工程软件工程是应用于计算机软件的定义、开发和维护的一整套是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。方法、工具、文档、实践标准和工序。l主要思想是将主要思想是将工程化工程化原则运用到软件开发过程，它包括原则运用到软
47、件开发过程，它包括3个个要素：要素：方法方法、工具工具和和过程过程（2008.9）。方法是完成软件工程项。方法是完成软件工程项目的技术手段；工具是支持软件的开发、管理、文档生成；目的技术手段；工具是支持软件的开发、管理、文档生成；过程支持软件开发的各个环节的控制、管理。软件工程过程过程支持软件开发的各个环节的控制、管理。软件工程过程是把是把输入输入转化为转化为输出输出的一组彼此相关的资源和活动。的一组彼此相关的资源和活动。软件工程及软件危机软件工程及软件危机l软件生命周期软件生命周期是指软件产品从提出、实现、使用维护到停止使用是指软件产品从提出、实现、使用维护到停止使用退役的过程退役的过程。l
48、软件生命周期分为软件生命周期分为软件定义软件定义、软件开发软件开发及及软件运行维护软件运行维护三个阶段：三个阶段：1）软件定义阶段软件定义阶段：包括制定计划和需求分析。：包括制定计划和需求分析。制定计划制定计划：确定总目标；可行性研究；探讨解决方案；制定开发计：确定总目标；可行性研究；探讨解决方案；制定开发计划。划。需求分析需求分析：对待开发软件提出的需求进行分析并给出详细的定义。：对待开发软件提出的需求进行分析并给出详细的定义。l2）软件开发阶段软件开发阶段：软件设计软件设计：分为：分为概要设计概要设计和和详细设计详细设计两个部分。两个部分。软件实现软件实现：把软件设计转换成计算机可以接受的
49、程序代码。：把软件设计转换成计算机可以接受的程序代码。软件测试软件测试：在设计测试用例的基础上检验软件的各个组成部分。：在设计测试用例的基础上检验软件的各个组成部分。l3）软件运行维护阶段软件运行维护阶段：软件投入运行，并在使用中不断地维护，：软件投入运行，并在使用中不断地维护，进行必要的扩充和删改。进行必要的扩充和删改。l软件生命周期中所花费最多的阶段是软件生命周期中所花费最多的阶段是软件运行维护阶段软件运行维护阶段。软件生命周期软件生命周期l（1）软件生命周期可分为定义阶段，开发阶段和维护阶段。）软件生命周期可分为定义阶段，开发阶段和维护阶段。详详细设计细设计属于（属于（）（2010.3）
50、A)定义阶段定义阶段 B)开发阶段开发阶段 C)维护阶段维护阶段 D)上述三个阶段上述三个阶段l（2）软件生命周期可分为多个阶段，一般分为定义阶段、开发）软件生命周期可分为多个阶段，一般分为定义阶段、开发阶段和维护阶段。阶段和维护阶段。编码和测试编码和测试属于属于_阶段。阶段。(2007.4)l(3)下面描述中，不属于软件危机表现的是（下面描述中，不属于软件危机表现的是（）(2010.9)A）软件过程不规范）软件过程不规范 B）软件开发）软件开发生产率生产率低低 C）软件）软件质量质量难以控制难以控制 D）软件）软件成本成本不断提高不断提高(4)软件生命周期中的活动不包括（软件生命周期中的活动
