计算机二级考试之公共基础知识课件.ppt

《计算机二级考试之公共基础知识课件.ppt》由会员分享，可在线阅读，更多相关《计算机二级考试之公共基础知识课件.ppt（141页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机二算机二级考考试之公共基之公共基础知知识课件件二级公共基础知识点分值分布二级公共基础知识点分值分布 第一章 数据结构与算法(30%)n 考试大纲1.算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3.线性表的定义；线性表的顺序存储结构及其插入与删除运算。4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5.线性单链表、双向链表与循环链表的结构及其基本运算。6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7.顺序查找与二分法查找算法；基本排序算法（

2、交换类排序，选择类排序，插入类排序）。一.算法的基本概念*1.所谓算法是指解题方案的准确而完整的描述。严格来说，一个算法必须具有以下五个主要特征：n有穷性有穷性（有限步骤内完成）、确定性确定性（结果不能模棱两可）、可可行性行性（能够完成目标要求）、输入输入、输出输出n输出和输出输出和输出可说成：拥有足够的情报拥有足够的情报 2.算法的组成要素n算法中对数据的运算和操作n算法的控制结构一.算法的基本概念3.算法设计的要求算法设计的要求 通常设计一个“好”的算法，应考虑达到以下目标。n正确性正确性：算法应当满足具体问题的需求。n可读性可读性：算法主要是为了人的阅读与交流，其次才是机器执行。可读性好

3、有助于人对算法的理解。n健壮性健壮性：当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫明其妙的输出结果。n效率与低存储量需求。效率与低存储量需求。效率指的是算法执行时间。对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高。低存储量需求指算法执行过程中所需要的最大存储空间。一.算法的基本概念4.算法设计基本方法n列举法n归纳法n递推n递归n减半递推n回溯法一.算法的基本概念*5.算法的复杂度可分为时间复杂度和空间复杂度，是衡量算法优劣的量度。（1）算法的时间复杂度算法的时间复杂度n算法的时间复杂度是指执行算法所需要的工作量。一般情况下，算法的时间复杂度为算法中的基本操作

4、重复执行的次基本操作重复执行的次数数。是问题规模n的某个函数f(n)f(n)。一.算法的基本概念n何估算算法的时间复杂度？任何一个算法都是由一个“控制结构”和若干“原操作原操作”组成的，因此一个算法的执行时间可以看成是所有原操作的执行时间之和 (原操作原操作(i)(i)的执行次数的执行次数原操作原操作(i)(i)的执行时间的执行时间 )nFor i=1 to 100 for j=1 to 100 s=i*j。算法时间复杂度为：O（n2)一.算法的基本概念（2 2）算法的空间复杂度）算法的空间复杂度n算法的空间负杂度是指执行这个算法所需要的内存空间。空间复杂度作为算法所需存储空间的量度，记作：S

5、(n)=O(g(n)S(n)=O(g(n)，其中n n为问题的规模，表示随问题规模的增大，算法运行所需存储量的增长率与g(n)g(n)的增长率相同。n一般不估计空间复杂度(3)(3)算法分析：算法分析：对算法的效率算法的效率进行分析，以求改以求改进进的过程。典型例题1.一个算法是对某类给定的问题求解过程的精确描述，算法中的操作都 可能通过将已经实现的基本操作执行有限次来实现，这句话说明算法具有什么特性？A 有穷性 B 可行性 C 确定性 D 健壮性2.算法的时间复杂度是指（）A）执行算法程序所需要的时间 B）算法程序的长度 C）算法执行过程中所需要的基本运算次数 D）算法程序中的指令条数 3.

6、下面叙述正确的是（）A）算法的执行效率与数据的存储结构无关 B）算法得空间复杂度是指算法程序中指令（或语句）的条数 C）算法得有穷性是指算法必须能在执行有限个步骤之后终止 D）以上三种描述都不对 4.算法能正确地实现预定功能的特性称为算法的（）。A正确性 B易读性 C健壮性 D高效率5.算法的计算量的大小称为计算的（）。A效率 B.复杂性 C.现实性 D.难度 二.数据结构1.数据结构的定义：数据结构的定义：是指相互有关联的数据元素的集合。备注：1）数据元素：是数据的基本单位基本单位，由数据项组成。通俗的说：数据元素就是现实世界中的一个实体的抽象。2）数据项：数据的最小单位最小单位。*2.数据

7、结构主要研究三个方面的问题：数据结构主要研究三个方面的问题：1)数据集合中各数据元素之间的逻辑关系，即数据的逻辑结构逻辑结构。2)在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构存储结构。3)对各种数据结构进行的运算运算。数据结构简单实例Student Student zhangsan Student lisi name;zhangsan;lisi;Sno;s20081001;s20081001;class;计算机1班；计算机1班；Rscore;515；501；数据的逻辑结构n数据逻辑结构数据逻辑结构是对数据元素之间存在的逻辑关系的描述（本身固有的），它可以用一个数据元素的

8、集合和定义在此集合上的若干关系表示。n与数据在计算机中的存储位置无关，是独立于计算机的。n常见的有线性结构线性结构和非线非线性结构性结构两种。数据的存储结构n数据的存储结构数据的存储结构是数据元素及其关系在计算机存储器中的表示，也称为物理结构物理结构。存储结构的主要内容是指在存储空间中使用一个存储结点来存储一个数据元素数据元素，在存储空间中建立各存储结点之间的关联关联，来表示数据元素之间的逻辑关系逻辑关系。n常见的存储结构：n顺序存储结构、链式存储结构、索引存储结构、散列存储结构典型例题（1）数据结构中，与所使用的计算机无关的是数据的A）存储结构 B）物理结构C）逻辑结构 D）物理和存储结构（

9、2）数据在计算机中的存储位置改变了，（）不变。A.数据的存储地址 B.数据间的逻辑关系C.数据的物理存储结构 D.逻辑结构和物理结构线性结构和非线性结构线性结构线性结构n在数据元素的非空有限集合中，线性结构的逻辑特征如下：n存在一个唯一的被称为“第一个”的数据元素n存在一个唯一的被称为“最后一个”的数据元素n除第一个之外，集合中的每个数据元素均有且只有一个直接前驱n除最后一个之外，集合中的每个数据元素均有且只有一个直接后继非线性结构非线性结构n非线性结构的逻辑特征是：一个结点可能有多个直接前驱和直接后继，树和图都属于非线性结构。线性表n通常以下列 n 个数据元素的序列”表示线性表线性表 ：(a

10、1,a2,.,ai,.,an)n序列中数据元素的个数 n 定义为线性表的表长表长；n=0 时的线性表被称为空表空表。称 i 为ai在线性表中的位序位序。n元素大多数时候称为”结点结点“线性表的顺序存储n线性表的顺序存储结构用一组地址连续地址连续的存储单元依次存放依次存放线性表中的数据元素，即以“存储位置相邻存储位置相邻”表示“位序相继的两个数据元素之间的前驱和后继的关系，并以表中第一个元素的存储位置作为线性表的起始地址，称作线性表的基地址线性表的基地址。所有结点的存储位置均可由第一个结点的存储位置得到 ADR(ai)=ADR(a1)+(i-1)C 基地址基地址 一个数据元素所占存储量一个数据元

11、素所占存储量 线性表的插入和删除运算n插入结点插入结点：要在第i(1in)个元素之前插入一个新元素时，首先要从最后一个元素开始，直到第i个元素之间共n-i+1个元素依次向后移动一个位置，然后将新元素插入到第i项。n删除结点：删除结点：要删除第i(1in)个元素，要从第i+1个元素开始，直到第n个元素，共n-i个元素依次向前移动一个位置。栈n栈栈是限定仅在表的一端进行插入和删除表的一端进行插入和删除操作的线性表线性表。允许插入和删除的一端称为栈顶，另一端称为栈底。n栈顶元素栈顶元素总是最后被插入的元素，从而也是最先被删除的元素；栈栈底元素底元素总是最先被插入，也是最后被删除的元素。因此，栈是一种

12、后进先出后进先出（LIFO）的线性表。n通常用指针top指示栈顶位置，用指针bottom指示栈底位置。栈的顺序存储及运算n用一维数组S(1:m)作为栈的顺序存储空间，m为栈的最大容量。top=0表示栈为空，top=m表示栈满。n栈的操作n入栈：入栈：在栈顶位置插入一个新元素，栈顶指针top加1。n退栈退栈：取出栈顶元素并赋值给一个指定的变量，栈顶指针top减1。n取栈顶元素：取栈顶元素：将栈顶元素的值赋给一个指定的变量，不删除栈顶元素，栈顶指针栈顶指针toptop不变不变。栈的溢出n上溢上溢 当栈满时再做进栈运算必定产生空间溢出，简称“上溢”。n下溢下溢 当栈空时再做退栈运算也将产生溢出，简称

13、“下溢”。n备注备注 (1)上溢是一种出错状态出错状态，应该设法避免避免之；下溢则可能是正常正常现象现象。(2)两个栈共享两个栈共享一块空间时，分配的存储空间要大于等于栈元大于等于栈元素较多的栈素较多的栈，这样可以减少减少“上溢上溢”。栈n如果某栈的入栈顺序是ABCDEF，则出栈顺序不可能是哪个（）A、DCEFBA B、ABCDEF C、EDFCAB D、CBAEDF 备注：这样的题目，字母出来的顺序不可以：备注：这样的题目，字母出来的顺序不可以：先大，先大，后小，再中。后小，再中。例：如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是A）e3,e1,e4,e2 B）e2,e4,e3,e

14、1C）e3,e4,e1,e2 D）任意顺序队列n队列队列是一种先进先出先进先出的线性表线性表，它只允许在表的一端插一端插入入元素(队尾队尾)，在另一端删除元素另一端删除元素(队头队头)。n向队尾队尾插入一个元素的操作称为入队，头指针入队，头指针front+1front+1，从队头队头删除一个元素的操作称为退队退队，尾指针尾指针rear+1rear+1。n队列和栈队列和栈一样是一种特殊的线性表特殊的线性表、是操作受限操作受限的线性线性表表、也称其为限定性数据结构为限定性数据结构。循环队列n将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的逻辑上的环状空间环状空间。循环队列初始状态为空，即f

15、ront=rear=0.nFront总是指示队头元素，rear指示队尾元素加1的位置。n入队操作时，rear加1，若rear+1=容量，则置rear=0；n退队操作时，front加1，若front+1=容量，则置front=0。n*当rearfront时，元素个数rearfront；当rearnextP-next删除节点：删除节点：p-next=p-next-nextp-next=p-next-next插入节点：插入节点：p-next=pxp-next=px px-next=p-after that px-next=p-after that双向链表和循环链表n在双向链表中的结点包含两个指针域，

16、其中一个指向直接后继，另一个指向直接前驱。n循环链表的特点是表中最后一个结点的指针域指向第一个结点，整个链表成为一个由链指针相链接的环。据此，从表中任一节点出发均可找到表中其它结点。在循环链表中增加了一个表头结点，其指针域指向第一个元素结点，头指针则指向头结点。HEADHEADHEADHEADHEADHEAD回顾：例：已知一组数据原先采用顺序存储，现改为散列存储，则（）不变。A.存储结构 B.逻辑结构 C.数据间的顺序 D.不确定例：常见的线性结构有_,_,_例：在线性表中删除第5个节点，则原第6个节点的位置（），如果单链表则（）A.6 B.5 C.不变 D.不确定例：已知栈的头指针front

17、当前位置为5，从栈中读取一个数据，则front指向（）A.5 B.6 C.不变 D.不确定例：如果某栈的入栈顺序是123456，则出栈顺序不可能是哪个（）A、435621 B.123456 C、546312 D、654321树及其基本概念n树是一种简单的非线性结构，在树中，所有的数据元素之间具有明显的层次性关系。n树是(n0)个结点的有限集合，在任意一棵非空树中：(1)有且仅有一个特定的结点称为根结点。(2)当n1时，其余的结点可分为m个互不相交的子集T1,T2,Tm，其中每个有限子集本身又是一棵树，并且称为根的子树。n集合为空的树简称为空树；树中的元素称为结点。树的主要术语n结点的度：结点拥

18、有的子树数。n叶节点(终端结点)：度为0的结点。n双亲、孩子和兄弟：结点的子树的根节点称为该结点的孩子，该结点称为孩子结点的双亲结点。同一个双亲结点的孩子互称为兄弟。n层次：结点的层次从根开始定义，根为第一层，根的孩子为第二层。n深度：树中结点的最大层次称为树的深度或高度。二叉树n二叉树是n(n0)个数据元素的有限集，它或为空集,或者含有唯一的称为根的元素，且其余元素分成两个互不相交的子集，每个子集自身也是一棵二叉树，分别称为根的左子树和右子树。n二叉树是另一种树型结构，其特点是每个结点至多有两棵子树，并且二叉树的子树有左右之分，其顺序不能任意颠倒。二叉树的基本性质n性质性质1 1 在二叉树的

19、第i层上至多有2i-1个结点（i1）n性质性质2 2 深度为k的二叉树至多有2k-1个结点（k1）n性性质质3 3 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则：n0=n2+1n性性质质4 4 具有n个结点的二叉树，其深度至少为log2n+1例：一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为 A）221 B）219 C）231 D）229 例：一棵含18个结点的二叉树的高度至少为(),至多为（）A）3 B）4 C）5 D）6 E)18 F)17满二叉树和完全二叉树n满二叉树满二叉树除最后一层外，每一层上的所有结点都有两个子节点，也就是说每一

20、层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m-1个结点。n完全二叉树完全二叉树除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。具有n个结点的完全二叉树，其深度为log2n+1。n从以上定义可知，满二叉树也是完全二叉树，反之则不然。满二叉树满二叉树 最大层的结点最大层的结点均向左靠齐均向左靠齐 完全二叉树完全二叉树 ADCBEF二叉树的基本性质性质性质5 5 如果对一棵有 n 个结点的完全二叉树（其深度为log2n+1）的结点按层序（从第1层到第log2n+1 层，每层从左到右）从1起开始编号，则对任一编号为 i 的结

21、点(1in)，则:(1)如果 i=1，则编号为 i 的结点是二叉树的根，无双亲；如果 i1，则其双亲结点 parent(i)的编号是i/2。(2)如果 2in，则编号为 i 的结点无左孩子（编号为 i 的结点为叶子结点）；否则其左孩子结点 lChild(i)的编号是 2i。(3)如果 2i+1n，则编号为 i 的结点无右孩子；否则其右孩子结点 rChild(i)的编号是结点 2i+1。例：在一棵二叉树上第5层的结点数最多是 A）8 B）16 C）32 D）15例：在深度为5的满二叉树中，叶子结点的个数为 A）32 B）31 C）16 D）15例：深度为4的二叉树中，编号为7的节点，它的右孩子节

22、点为（）该树为满二叉树；如果该树是完全二叉树，但不是满二叉树，则它的最大节点编号为（）A）14 B）8 C）9 D）15例：设树T的度为4，其中度为1，2，3，4的结点个数分别人4，2，1，1.则T中的叶子结点数为 A)8 B)7 C)6）二叉树的链式存储结构n在二叉树的链式存储结构中，每个结点设置三个域，即数据域，左指针域和右指针域，两个指针域分别存储左右子树根节点的存储位置，即指针。L(i)V(i)R(i)LchildvalueRchild二叉树的链式存储结构二叉树的遍历n二叉树的遍历指不重复地访问二叉树的所有结点。从二叉树的结构定义得知，二叉树是由根结点、左子树和右子树三部分构成，则遍历

23、二叉树的操作可分解为访问根结点、遍历左子树和遍历右子树三个子操作，并且由二叉树的递归定义可知，遍历左子树和遍历右子树可如同遍历二叉树一样递归进行。先序遍历二叉树先序遍历二叉树中序遍历二叉树中序遍历二叉树后序遍历二叉树后序遍历二叉树若二叉树为空，则空操作；否则(1)访问根结点；(2)先序遍历左子树；(3)先序遍历右子树。若二叉树为空，则空操作；否则(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右子树。若二叉树为空，则空操作；否则(1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点。二叉树的遍历先序遍历：ABDEGHCFIJ中序遍历：DBGEHACIJF后序遍历：DGHEBJIFC

24、A二叉树的遍历n已知前序和中序遍历时，根据前序判断出根，根据已知前序和中序遍历时，根据前序判断出根，根据中序分出左右子树；再根据前序分别判断出左右子中序分出左右子树；再根据前序分别判断出左右子树的根，然后再分出左右子树，以此类推下去树的根，然后再分出左右子树，以此类推下去例：某二叉树的前序遍历结点访问顺序是A B D E C，中序遍历的结点访问顺序是D B E A C，则后序遍历的结点访问顺序是：n已知后序和中序遍历时，根据后序判断出根，根据已知后序和中序遍历时，根据后序判断出根，根据中序分出左右子树；再根据后序分别判断出左右子中序分出左右子树；再根据后序分别判断出左右子树的根，然后再分出左右

25、子树，以此类推下去树的根，然后再分出左右子树，以此类推下去例：已知一棵二叉树的中根序列和后根序列分别为31564和36541，试画出这棵二叉树。前序和中序推理过程nA B D E C 前序nD B E A C 中序中序和后序推理过程n3 6 5 4 1 后序n3 1 5 6 4 中序例题例例1 1：某二叉树的前序遍历结点访问顺序是A AB BD DG GC CE EF FH H，中序遍历的结点访问顺序是D DG GB BA AE EC CH HF F，则后序遍历的结点访问顺序是：例例2 2：已知一棵二叉树的中根序列和后根序列分别为B BD DC CE EA AF FH HG G和D DE EC

26、 CB BH HG GF FA A，试画出这棵二叉树。GDBEHFCA例：例：某二叉树的前序遍历结点访问顺序是ABEFGHMN，中序遍历的结点访问顺序是EFBGAMHN，则后序遍历的结点访问顺序是：例：已知一棵二叉树的中根序列和后根序列分别为和，试画出这棵二叉树。(节点为0到9的数字）FEGBMNHA查找n顺序查找:是指在一个给定的数据结构中查找某个指定的元素。n顺序查找一般是指在线性表中查找指定元素，基本方法如下：从线性表的第一个元素开始，依次将线性表中的元素与被查找元素进行比较，若相等则表示找到，即查找成功；若线性表中的所有元素与被查找元素都不相等，则查找失败。n如果线性表为无序表，即表中

27、元素的排列是无序的，则不管线性表采用顺序存储还是链式存储，都必须使用顺序查找。n如果线性表有序，但采用链式存储结构，则也必须使用顺序查找。n平均查找长度为（n+1)/2，最坏为n.二分查找(折半查找)二分查找法只适用于顺序存储的有序表。先确定待查目标元素所在范围(区间)，然后逐步缩小范围直至找到该元素，或者当查找区间缩小到0也没有找到目标元素为止。n查找过程中，给定值首先和处于待查区间“中间位置”的关键字进行比较，若相等，则查找成功，否则将查找区间缩小到“前半个区间”或“后半个区间”之后继续进行查找。n在等概率状态下查找成功时的平均查找长度为：ASLlog2（n1）-1（当n 50时）折半查找

28、二分查找例题：1.以顺序查找方法从长度为n的线性表中查找一个元素时，平均查找长度为(n+1)/2,时间复杂度为O(n)。2.以二分查找方法从长度为n的线性表中查找一个元素时，平均查找长度小于等于log2(n+1)，时间复杂度为O(log2n)。排序n排序是指将一个无序序列整理成按值递增或递减(本章均采用递增规则)的有序序列。n排序可以在各种不同的存储结构上实现，本章所介绍的算法以顺序存储的线性表为排序对象，在程序设计语言中就是一维数组。n常见的排序方法有插入排序插入排序(包括简单插入排序法和希尔排序法等)、交换排序(包括冒泡排序和快速排序法等)和选择排序(包括简单选择排序和堆排序等)。交换类排

29、序n冒泡排序n基本思想：从表头开始扫描线性表，在扫描的过程中依次比较相邻两个元素的大小，若前面的元素大于后面的元素，则交换它们的位置。显然，在扫描过程中，不断地将将相邻元素间较大的向后移动，最后将线性表中最大的元素移到表尾。n然后，从后向前扫描剩下的线性表，同样在扫描的过程中依次比较相邻两个元素的大小，若后面的元素小于前面的元素，则交换位置。在扫描过程中，不断地将将相邻元素间较小的向前移动，最后将线性表中最小的元素移到表头。n对剩下的线性表重复上述过程，直到剩余线性表为空为止，此时线性表变为有序。n最坏情况下运算的次数为：最坏情况下运算的次数为：n*(n-1)/2n*(n-1)/2（即时间复杂

30、度）。最好情况下为：最好情况下为：n-1.n-1.冒泡排序示例第一遍第一遍(从前向后从前向后)第一遍第一遍(从后向前从后向前)第二遍第二遍(从前向后从前向后)第二遍第二遍(从后向前从后向前)快速排序n基本思想：从线性表中选取一个元素，设为T，将线性表后面小于T的元素移动到前面，将前面大于T的元素移动到后面，将线性表分为两个部分(子表)，T放到分界线的位置，这个过程称为线性表的分割，通过一次分割，就以T为分界将线性表分为两个子表，前面的子表中的所有元素均不大于T，而后面子表中的元素均不小于T。按照上述原则对子表继续进行分割，直到子表为空，则整个线性表有序。快速排序n操作步骤：n首先，在表的第一个

31、元素、最后一个元素和中间元素中选取一个中值，设为P(k)，并将P(k)赋值给T，再将表中的第一个元素移到P(k)的位置。设两个指针i，j分别指向表的起始和最后位置，反复操作以下两步：将j逐渐减小，并逐次比较P(j)和T，直到发现一个P(j)T为止，并将P(i)移到 P(j)的位置上。n上述两步操作交替进行，直到i和j指向同一个位置，再将T移动到P(i)的位置上，完成一次分割。31 68 45 90 233954 12 87 7631暂存枢轴记录暂存枢轴记录T T：lowhighhighhigh1212low6868highhighhigh2323low4545highhigh3131快速排序的

32、一次分割过程快速排序的一次分割过程31插入类排序n简单插入排序n基本思想：将待排序列表分成两部分：已排序部分和未排序部分。每次扫描将未排序列表中的第一个元素取出并插入到已排序列表中的合适位置。包含n个元素的列表最多需要n-1次扫描。简单插入排序示例原始序列第1趟第2趟第3趟第4趟第5趟希尔排序n基本思想：将整个无序序列分割成若干个小的子序列分别进行插入排序。n子序列的分割方法：将相隔某个增量h的元素构成一个子序列，在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序完成。n增量序列一般取ht=n/2k(k=1,2log2n)希尔排序h=6h=6h=1h=1h=3h=3完成完

33、成选择类排序n简单选择排序n基本思想：将待排序列表分成两部分：已排序部分和未排序部分。找到未排序部分中的最小元素并把它和未排序部分中的第一个元素进行交换。经过一次选择和交换，列表中已排序部分增加一个元素，未排序部分减少一个元素。每次把一个元素从未排序部分移动到已排序部分称为完成一次分类扫描分类扫描或称为一趟排序一趟排序。n一个包含n个元素的列表需要进行n-1次扫描完成排序。简单选择排序示例原始序列第1趟第2趟第3趟第4趟第5趟排序时间复杂度汇总（基数空间为O（rd)*从上表应当看出：1.当原表有序或基本有序时,直接插入排序和冒泡排序最好，时间复杂度可降至O(n)。（也就是最好情况下）。如果选择

34、快速排序则相反，达到最坏时间复杂度。2.空间复杂度最坏的是归并排序O（n)，其次是基数排序O（rd)。3.平均时间最好的是快速、堆、归并排序O（nlgn)。4.稳定排序和不稳定排序（希尔、堆、直接选择，快速）。5.最坏情况下，时间复杂度最小的是：堆和归并排序。第二章 程序设计基础(15%)n考试大纲n1.程序设计方法与风格。2.结构化程序设计。3.面向对象的程序设计方法，对象，方法，属性及继承与多态性。知识点归纳n程序设计是一门技术，需要相应的理论、方法和工具来支持。就程序设计方法和技术的发展而言，主要经历了结构化的程序设计和面向对象的程序设计阶段。n在程序设计中，通常采用“自顶向下，逐步求精

35、”的方法，即把一个模块的功能逐步分解，细化为一系列具体的步骤，进而转换成一系列用某种程序设计语言编写的程序。程序设计风格n除了程序设计设计方法和技术之外，程序风格也是非常重要的。良好的程序设计风格概括起来包括以下及格方面：n源程序文档化n数据说明的方法n语句的结构n输入和输出程序设计风格（4个方面）n源程序文档化n标识符的命名标识符的命名:要有一定的实际含义要有一定的实际含义。n程序的注释：程序的注释：较完善程序一般要有注视。n序言性注释：通常置于每个程序模块的开头部分,一般给出程序的程序的整体说明。整体说明。n功能性注释：一般是对某条语句的功能性说明。n程序的视觉组织：程序的视觉组织：一定要

36、层次清晰层次清晰n数据的说明n数据说明的次序应该规范化：数据说明的次序应该规范化：比如先说明变量，其次是简单类型（如数组），接着是构造类型（如自己定义的数据结构）。n说明语句中变量的安排有序化：说明语句中变量的安排有序化：例如多个变量出现在同一个说明语句中，要按顺序排列。n使用注释说明复杂的数据结构使用注释说明复杂的数据结构程序设计风格n语句结构语句结构n在一行内只写一条语句n程序编写应优先考虑清晰性程序编写应优先考虑清晰性n除非对效率有特殊要求，程序编写要做到清晰第一，效率第二清晰第一，效率第二n首先要保证程序正确，然后才要求提高速度n避免使用临时变量而使程序的可读性下降n避免不必要的转移n

37、尽可能使用库函数n避免使用复杂的条件语句n尽量减少使用“否定”条件的条件语句n数据结构要有利于程序的简化n要模块化，使模块功能尽可能单一化要模块化，使模块功能尽可能单一化n利用信息隐蔽，确保每一个模块的独立性利用信息隐蔽，确保每一个模块的独立性n从数据出发构造程序n不要修补不好的程序，要重写编写不要修补不好的程序，要重写编写程序设计风格n输入和输出n对所有输入数据检验合法性对所有输入数据检验合法性n检查输入项的各种重要组合的合法性n输入格式要简单，以使输入的步骤和操作尽可能简单n输入数据时，应允许使用自由格式n应允许缺省值n输入一批数据时，最好使用输入结束标志n在以交互式输入/输出方式进行输入

38、时，要在屏幕上使用提示符明确提示输入的请求，同时在数据输入结束时，应在屏幕上给出状态信息n当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性；给所有的输出加注释，并设计输出报表格式。结构化程序设计n结构化程序设计的原则n自顶向下自顶向下。程序设计时，应先考虑总体先考虑总体，后考虑细节细节；先考虑全局目标全局目标，后考虑局部目标局部目标。不要一开始就过多追求细节，先从最上层总目标开始设计，逐步使问题具体化。n逐步求精逐步求精。对复杂的问题，应设计一些子目标过渡，逐步细化。n模块化模块化。一个复杂问题肯定是有若干简单问题构成。模块化是把程序要解决的总目标分解为分目标，再进一步分

39、解为具体的小目标，每个小目标成为一个模块。n严格限制严格限制GOTOGOTO语句的使用语句的使用。（不是不能使用）结构化程序设计的基本结构和特点n程序由一些基本结构组成，任何一个程序都可以用三种基本控制结构组成：顺序结构、选择结构和循环结构顺序结构、选择结构和循环结构n程序结构的特点：单入口、单出口、结构中无单入口、单出口、结构中无死循环死循环（也称有限的控制结构），程序中三种基本控制结构之间形成顺序执行关系。n一个大型程序应按功能分割成一些模块，并把这些模块按层次关系进行组织层次关系进行组织。n在程序设计时应采用自顶向下、逐步细化的实施方法。例：结构化程序设计的基本思想是采用自自顶向下，逐步

40、求精顶向下，逐步求精的程序设计方法和单入口单出口单入口单出口的控制结构。面向对象程序设计 面向对象方法的基本概念1.1.对象、类和属性对象、类和属性 (1)对象的定义：在面向对象程序设计中，对象对象是程序的基本单位。对象可以表示客观世界中的任何实体实体，是对问题域中某个实体的抽象。(2)对象通常由对象名、属性和操作三部分组成。(3)类是对一组具有共同属性和相似行为的对象的一种抽象，类是对象的抽象类是对象的抽象，而对象是类的具体实例对象是类的具体实例。类是抽抽象的，象的，不占用内存不占用内存，而对象是具体的对象是具体的，占用存储空间占用存储空间。对象的特点n标识唯一性：对象名是唯一的n分类性：每

41、个对象都有属于自己的类。n封装性：将对象的属性和操作封装成一个整体，也实现了数据的隐藏。n模块独立性：例题：信息隐蔽的概念与下述哪一种概念直接相关_。A.软件结构定义 B.模块独立性 C.模块类型划分 D.模拟耦合度 对象的特点继承继承：指一个类(子类)直接使用另一个类(父类)的所有属性和方法。单重继承：单重继承：一个类从另一个类继承属性和操作 多重继承：多重继承：一个类有几个父类多态性：多态性：多态性可以用“一个对外界面，多个内部实现一个对外界面，多个内部实现”来表示。可以通过方法重载和方法重写重载和方法重写来实现多态。举一个例子，计算机中的堆栈可以存储各种格式的数据，包括整型，浮点或字符。

42、不管存储的是何种数据，堆栈的算法实现是一样的。n例：有三个栈（对象），分别放数值型、字符型、日期型数据，队列（对象）向三个栈发送同样的“读取”消息，则产生的结果不一样。2.2.方法方法 方法也可称为操作或服务操作或服务，它描述了对象执行的功能，若通过消息传递，还可为其他对象使用。3.消息：消息：面向对象系统中的对象之间是通过消息消息机制彼此相互合作的。消息由三部分组成：消息标识符、零个或多个参数、接受消息消息标识符、零个或多个参数、接受消息对象的对象名对象的对象名面向对象程序设计的特点n按照人的思维方式对客观世界进行抽象n稳定性好n可重用性好可重用性好n易于开发大型软件n可维护性好n1、程序设

43、计语言的基本成分是数据成分、运算成分、控制成分和（D）A）对象成分 B）变量成分 C）语句成分 D）传输成分n2、结构化程序设计主要强调的是（D）A）程序的规模 B）程序的效率 C）程序设计语言的先进性 D）程序易读性n3、对建立良好的程序设计风格，下面描述正确的是（A）A）程序应简单、清晰、可读性好 B）符号名的命名只要符合语法 C）充分考虑程序的执行效率 D）程序的注释可有可无n4、NULL是指（C）A）0 B）空格 C）未知的值或无任何值 D）空字符串n5、在结构化程序设计思想提出之前，在程序设计中曾强调程序的效率，现在，与程序的效率相比，人们更重视程序的（C）nA）安全性 B）一致性

44、C）可理解性 D）合理性n6、子程序通常分为两类：【过程】和函数，前者是命令的抽象，后者是为了求值。n7、.在面向对象方法中，类之间共享属性和操作的机制称为【继承】。n8、一个类可以从直接或间接的祖先中继承所有属性和方法，提高了软件的【可重用性】第三章 软件工程基础n考试大纲n1.软件工程基本概念，软件危机，软件工程的软件工程基本概念，软件危机，软件工程的三要素、目标与原则三要素、目标与原则。2.结构化分析方法，数据流图，数据字典，软结构化分析方法，数据流图，数据字典，软件需求规格说明书。件需求规格说明书。3.结构化设计方法，总体设计与详细设计结构化设计方法，总体设计与详细设计。4.软件测试的

45、方法，白盒测试与黑盒测试，测软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集试用例设计，软件测试的实施，单元测试、集成测试和系统测试。成测试和系统测试。5.5.程序的调试，静态调试与动态调试。程序的调试，静态调试与动态调试。软件定义和特点计算机软件计算机软件是计算机系统中与硬件相互依存的另一部分，是包括程序、数据及相关文档的完整程序、数据及相关文档的完整集合集合。计算机软件具有如下特点：n软件是一种逻辑实体，具有抽象性n软件生产没有明显的制造过程n软件在运行、使用期间不存在磨损、老化问题n软件的开发、运行对计算机系统具有依赖性n软件复杂性高，成本昂贵n软件开发涉及

46、诸多社会因素软件危机n所谓软件危机是指在计算机软件开发和维护过程中所遇到的一系列严重问题，包括：n软件需求的增长得不到满足n软件开发成本和进度无法控制n软件质量难以保证n软件不可维护或可维护性低n软件成本不断提高n软件开发生产率的提高赶不上硬件的发展和应用需求的增长。软件工程n为了消除软件危机，提出了软件工程学。软件工程是为了消除软件危机，提出了软件工程学。软件工程是应用于计算机软件定义、开发和维护的一整套方法、应用于计算机软件定义、开发和维护的一整套方法、工具、文档、实践标准和工序。工具、文档、实践标准和工序。n软件工程的三要素n方法：方法：软件开发提供了“如何做”的技术。它包括了多方面的任

47、务，如项目计划、软件系统需求分析、系统总体结构的设计、编码、测试及维护等。n工具：工具：提供了自动的或半自动的软件支撑环境，即通常所说的软件工具。n过程：过程：软件工程过程n软件工程过程是把输入转化为输出的一组彼此相关的资源和活动。它包括两方面含义：n1.软件工程过程是指为获得软件产品获得软件产品，在软件工具支持下由软件工程师完成的一系列工程活动一系列工程活动。通常包括四种基本活动：nP(Plan)：软件规格说明nD(Do)：软件开发nC(Check)：软件确认nA(Action)：软件演进n2.从软件开发的观点看，软件工程过程是使用适当的资源，为开发软件进行的一组开发活动一组开发活动，在活动

48、结束时将输入输入(用户需求用户需求)转化为输出(软件产品软件产品)。软件工程目标与原则目标：目标：在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。基本原则：基本原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。*软件工程的理论和技术性研究的内容包括：软件工程的理论和技术性研究的内容包括：软件开发技术和软件工程管理。软件开发技术包括：软件开发技术包括：软件开发方法学、开发过程、开发工具和软件工程环境。软件工程管理包括：软件工程管理包括：软件管理学、软件工程经济学、软件心理学等内容

49、。*衡量软件的指标：衡量软件的指标：高内聚（模块内）、低耦合（模块间）。软件开发工具与软件开发环境计算机辅助软件工程计算机辅助软件工程(CASE):(CASE):是一组工具和方法集合，可以辅助软件开发生命周期个阶段进行软件开发帮助进行应用程序开发的软件，包括分析、设计和代码生成.(CASE)(CASE)的集成的集成:(1)平台集成：工具运行在相同的硬件/操作系统平台。(2)数据集成：工具使用共享数据模型来操作。(3)表示集成：工具提供相同的用户界面。(4)控制集成：工具激活后能控制其他工具的操作。(5)过程集成：工具在一个过程模型和“过程机”的指导下使用。软件生命周期n软件从提出、实现、使用、

50、维护到停止使用的过程称为软件的生命周期。一般包括以下几个阶段：n可行性研究：可行性研究：目的就是用最小的代价在尽可能短的时间内确定该软件项目是否值得去开发。其实质是要进行一次简化、压缩了的需其实质是要进行一次简化、压缩了的需求分析求分析n需求分析：需求分析：任务就是导出目标系统的逻辑模型，解决“做什么”的问题（即系统功能）。需求分析的方法是：结构化分析方法和面向对象分析方法。n软件设计：软件设计：任务从软件需求规格说明书出发，形成软件的具体设计方案，即划分模块结构的过程.n软件实现：软件实现：把软件设计转换成计算机可以接受的程序代码。n软件测试软件测试:n运行和维护：运行和维护：软件生命周期中