《计算机等级二级公共基础知识优秀PPT.ppt》由会员分享，可在线阅读，更多相关《计算机等级二级公共基础知识优秀PPT.ppt（144页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算机等级二级公共基础知识现在学习的是第1页，共144页公共基础知识一、基本数据结构与算法。二、程序设计基础。三、软件工程基础。四、数据库设计基础。现在学习的是第2页，共144页第一部分 数据结构与算法5-7个题（10-14分）考试大纲:一.基本要求:1.掌握算法的基本概念2.掌握基本数据结构及其操作3.掌握基本排序和查找算法现在学习的是第3页，共144页二.考试内容:1.算法的基本概念;算法复杂度的概念和意义(时间复杂度和空间复杂度)2.数据结构的定义;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念3.线性表的定义;线性表的顺序存储结构及其插入与删除运算4.栈和队列
2、的定义;栈和队列的顺序存储结构及其基本运算5.线性单链表、双向链表与循环链表的结构及其基本运算6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）现在学习的是第4页，共144页考点一、算法（P1）一.算法的基本概念 所谓算法是指解题方案的准确而完善的描述。1.算法的基本特征可行性：是否可行。确定性：指算法中的每一个步骤必须有明确定义，不允许有模棱两可的解释，也不允许有多义性。有穷性：指算法必须在有限的时间内做完，即算法必须能在执行有限个步骤后终止。拥有足够的情报：收集的输入信息等。现在学习的是
3、第5页，共144页2.算法的基本要素一个算法通常由两种要素组成：一是对数据对象的运算和操作，二是算法的控制结构。（1）算法中对数据的运算和操作（指令）（P2）算术运算：加、减、乘、除逻辑运算：与、或、非关系运算：大于、小于、等于、不等于数据传输：赋值、输入、输出（2）算法的控制结构（P3）一个算法一般都可以用顺序、选择、循环三种基本控制结构组成。描述算法的工具有：传统流程图、N-S结构化流程图、算法描述语言。现在学习的是第6页，共144页传统流程图、N-S结构化流程图、算法描述语言。条件语句序列1语句序列2ENDIF后面的语句真假条件语句序列1ENDIF后面的语句a=0?yesno输入a,b,
4、c b2-4acdelta b0?delta0?Yes No方程有一个根方程无意义 方程有二个实根方程有二个虚根输出方程的根 noyes3.算法设计的基本方法列举法 归纳法 递推法 递归法 减半递推技术现在学习的是第7页，共144页二.算法的复杂度（P5）算法的复杂度主要包括:时间复杂度和空间复杂度.1.算法的时间复杂度:指执行算法所需要的计算工作量.工作量可以用算法所执行的基本运算次数来度量,而算法所执行的基本运算次数是问题规模的函数 即算法的工作量=f(n)其中n是问题的规模.可以用平均性态和最坏情况复杂性两种方法.现在学习的是第8页，共144页2.算法的空间复杂度:指执行这个算法所需要的
5、内存空间.包括算法程序所占的空间、输入的初始数据所占的存储空以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及基本种数据结构所需要的附加存储空间（例如，在链式结构中，除了存储数据本身外，还需要存储链接信息）。现在学习的是第9页，共144页考点二、数据结构的基本概念（P7）数据结构学科主要研究如下三个方面的内容:数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构.在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构.对各种数据结构进行的运算.数据结构学科的研究目的:提高数据处理的效率.主要包括:数据处理速度.尽量节省在数据处理过程中所占用
6、的计算机存储空间.现在学习的是第10页，共144页一.数据结构的定义:指相互关联的数据元素的集合.1.数据处理:指对数据集合中的各元素以各种方式进行运算.(插入,删除,查找,更改等)2.数据元素:在数据处理领域中,每一个需要处理的对象都可以抽象为数据元素.3.数据结构:是指反映数据元素之间关系的数据元素集合的表示.一个数据结构应包括两方面的信息:一是表示数据元素的信息,二是表示各数据元素之间的前后件关系.现在学习的是第11页，共144页数据的逻辑结构（P11）:指反映数据元素之间逻辑关系的数据结构.它包含两个要素:一是数据元素的集合,通常记为D,二是D上的关系,它反映了D中各数据元素之间的前后
7、件关系,通常记为R,形式表示为:B=(D,R)其中B表示数据结构 为了反映D中各数据元素之间的前后件关系,一般用二元组来表示.例如,假设a与b是D中的两个数据,则二元组(a,b)表示a是b的前件,b是a的后件.这样,在D中的每两个元素之间的关系都可以用这种二元组来表示.现在学习的是第12页，共144页例:一年四季的数据结构可以表示成:B=(D,R)D=春，夏，秋，冬 R=（春,夏）,（夏,秋）,（秋,冬）数据的存储结构（P12）:指数据的逻辑结构在计算机存储空间中的存放形式.也称为物理结构.一般来说,一种数据的逻辑结构根据需要表示成多种存储结构,常用存储结构有顺序,链接,索引等.各数据元素在计
8、算机存储空间中的位置关系与它们的逻辑关系不一定是相同的,而且一般也不可能相同.（P13）现在学习的是第13页，共144页二.数据结构的图形表示 一个数据结构除了用二元关系表示外,还可以直观的用图形表示.图形表示方法:对于数据集合D中的每一个数据元素用中间标有元素值的方框表示,一般称之为数据结点,简称为结点;对于关系R中的每一个二元组,用一条有向线段从前件结点指向后件结点,以表示数据元素之间的前后件关系.春夏秋冬女儿儿子父亲现在学习的是第14页，共144页例:用图形表示数据结构B=(D,R),其中 D=di|1i6=d1,d2,d3,d4,d5,d6 R=(d1,d2),(d1,d3),(d3,
9、d4),(d5,d4),(d5,d6)这个数据结构的图形表示为:d1d2d3d5d4d6现在学习的是第15页，共144页三.线性结构和非线性结构（概念）（P14）数据结构一般分为线性结构和非线性结构两大类.一个非空的线性结构满足如下条件:有且仅有一个根结点;每一个结点最多有一个前件,也最多有一个后件;在一个线性结构中插入或删除一个结点后还是线性结构.如果一个数据结构不是线性结构,则称之为非线性结构.线性结构有:栈,队列,双向链表;非线性结构:树,二叉树.ACBABCABCD现在学习的是第16页，共144页1.线性表的基本概念线性表定义:线性表是由n(n=0)个数据元素a1,a2,an组成的一个
10、有限序列,表中的每一个数据元素,除了第一个外,有且只有一个前件,除了最后一个外,有且只有一个后件.即线性表或是一个空表,或是可以表示为:(a1,a2,an)其中ai(i=1,2,n)是属于数据对象的元素,通常也称为线性表中的一个结点.非空线性表的基本特征:有且只有一个根结点a1，它无前件；有且只有一个终端结点an，它无后件；除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表的长度：线性表中结点的个数n称为线性表的长度。当n=0时，称为空表。考点三、线性表及其顺序存储结构现在学习的是第17页，共144页2.线性表的顺序存储结构（P16）具有两个基本特点：线性表中所有元
11、素所占的存储空间是连续的；线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。由此可以看出，在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件一定存储在后件元素的前面。现在学习的是第18页，共144页线性表的随机存取地址的计算公式：ADR（ai）=ADR(a1)+(i-1)k k指每个元素所占的字节：a1a2aian：ADR(a1)占k个字节占k个字节占k个字节占k个字节：ADR(a1)+kADR(a1)+(i-1)kADR(a1)+(n-1)k线性表的主要操作:插入、删除、查找、排序、分解、合并、复制、逆转现在学习的是第19页，共144页3.线性表的插入运算一个长度为n
12、的线性表，要在第i（1in）个元素之前插入一个新元素时，首先要从最后一个（即第n个）元素开始向后移动一个位置，直到第i个元素之间的n-i+1个元素依次向后移动一个位置，移动结束后，第i个位置就被空出，然后将新元素插入到第i项。插入结束后，线性表的长度就增加了1，变为n+1.其时间复杂度，在平均情况下，需要移动一半的元素，最坏情况下要移动所有元素。现在学习的是第20页，共144页4731243536561829473124353656182947312435365618872912345678910123456789101234567891087线性表顺序存储结构的适用场合：对于小线性表或者其中
13、元素不常变动的线性表来说是合适的，因为顺序存储的结构比较简单，对于元素需要变动的大线性表就不太合适了，因为插入和删除的效率比较低。现在学习的是第21页，共144页4.线性表的删除运算要删除第i（1in）个元素时，首先要从第i+1个元素开始，直到最后一个（即n个）元素之间的n-1个元素依次向前移动一个位置。删除结束后，线性表的长度就减少了1。变为n-1。删除操作的时间复杂度：在平均情况下，需要移动表中一半的元素，最坏情况下要移动表中的所有元素。现在学习的是第22页，共144页考点四、栈和队列(重点)（P19）1、栈及其基本运算(1)栈的定义:栈是限定在一端进行插入和删除操作的线性表.它按照”后进
14、先出”(或”先进后出”)的原则组织数据.(2)栈的顺序存储:在程序设计语言中一般是用一维数据S(1:m)作为栈的顺序存储空间,其中m为栈的最大容量.(3)栈的基本运算入栈运算:首先将栈顶指针(top)加1,然后将新元素插入到栈顶指针指向的位置.当栈顶指针已经指向存储空间的最后一个位置时说明本栈空间已满,不可能再进行入栈操作.退栈操作:首先将栈顶元素赋给一个指定的变量,然后将栈顶指针(top)减1.当栈顶指针为0时,说明栈空,不可能再进行退栈操作.读栈顶元素:将栈顶元素赋给一个指定的变量,栈指针(top)不变.当栈顶指针为0时,说明栈空,读栈顶元素操作失败.现在学习的是第23页，共144页ABC
15、DEF10987654321topbottomABCD10987654321topbottom入栈入栈退栈退栈现在学习的是第24页，共144页2、队列及其基本运算（P21）（1）队列的定义：队列是指允许在一端进行插入、而在另一端进行删除的线性表。它按照“先进先出”的原则组织数据。FEDCBA退队入队frontrear（2）循环队列：将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。（3）循环队列的基本运算入队运算：首先将队尾指针加1（real=real+1），并当real=m+1时，置real=1，然后将新元素插入到指针指向的位置。退队运算：首先将排头指针加1（
16、front=front+1），并当front=m+1时置front=1，然后将排头指针指向的元素赋给指定的变量。现在学习的是第25页，共144页ABCDEF87654321realfront具有6个元素的循环队列加入X和Y后的循环队列realABCDEF87654321frontXYBCDEF87654321frontXYreal退出一个元素后的循环队列栈和队列都是顺序存储的。现在学习的是第26页，共144页考点五、线性链表（P24）1、线性链表的基本概念：线性表的链式存储结构称为线性链表。线性链表的存储结构：线性链表的每个结点中数据域存放数据元素的值，指针域存放后件结点的存储地址。双向链表的
17、存储结构：双向链表的存储结构比线性链表的存储结构多出一个指针域，它用来存放前件结点的存放地址。带链的栈，带链的队列HEADA0BH0HEAD0现在学习的是第27页，共144页2、线性链表的基本运算（P27）：插入、删除、合并、分解、逆转、复制、排序、查找。线性链表的插入：先从栈中为新元素分配一个新的结点q，并赋值。然后利用线性链表的查找算法找到待插入位置的前一个结点的指针p。先将q指向p的后件，然后将q挂在p结点的后面。xpxpqxpq现在学习的是第28页，共144页线性链表的删除：先找到待删除元素的前一个结点p，用另一个指针q暂时保存p的后续结点（即待删除结点），然后把q结点的后续链直接挂接
18、在p的后面。最后归还q结点所分配的栈空间。xpqxpq现在学习的是第29页，共144页3、循环链表（P30）：循环链表的几个特点：在循环链表中增加一个表头结点，使得循环链表对空表和非空表的操作实现了统一。循环链表中最后一个结点的指针域不是空，而是指向表头结点。判断循环链表是否为空的办法不是看表头指针为空，而是看表头结点的后续结点是否还是表头结点。在循环链表中，从任何一个结点出发都可以访问到表中其它所有的结点。xYHEADz现在学习的是第30页，共144页考点六、树与二叉树(重点)（P31）1、树的基本概念树是一种非线性结构，在树的这种数据结构中，所有数据元素之间的关系具有明显的层次特性。父结点
19、：在树结构中，每一个结点只有一个前件结点，称为父结点。根结点：没有前件的结点只有一个，称为树的根结点。子结点：每一个结点可以有多个后件，它们都称为该结点的子结点。叶子结点：没有后件的结点称为叶子结点。IKGFHEDCBAR现在学习的是第31页，共144页结点的度：一个结点所拥的后件个数称为该结点的度。树的度：在树中，所有结点中的最大的度称为树的度。树的深度：树的最大层次称为树的深度，树的深度也可以称为树的高度，根结点在第1层。子树：在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。叶子结点没有子树。IKGFHEDCBAR现在学习的是第32页，共144页IKGFHECBR2、二叉树及
20、其基本性质（P34）二叉树的两个特点：非空二叉树只有一个根结点；每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。二叉树的基本性质：在二叉树的第k层上，最多有 2k-1(k=1)个结点。深度为m的二叉树最多有2m-1个结点。在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。具有n个结点的二叉树，其深度至少为2n+1。现在学习的是第33页，共144页FGEHDCBAIJKMLPNFGEHDCBAIJK3、满二叉树和完全二叉树（P35）满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。完全二叉树：除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少
21、右边的若干结点。基本性质：满二叉树的第k层上有2k-1(k=1)个结点，且深度为m的二叉树有2m-1个结点。具有n个结点的完全二叉树的深度为2n+1。设完全二叉树共有n个结点，如果从根结点开始，按层序（第一层从左到右）用自然数1、2、n给结点进行编号，则对于编号为k的结点有以下结论：若k=1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点编号为INT(K/2)。现在学习的是第34页，共144页若2k=n，则编号为k的结点的左子结点编号为2k，否则该结点无左子结点（显然也没有右子结点）若2k+1=n，则编号为k的结点的右子结点编号为2k+1，否则该结点无右子结点。FGEHDCBAIJK
22、4、二叉树的存储结构（P36）L(i)：左指针域，指向该结点的左子结点（存放左子结点的存储地址）。R(i)：右指针域，指向该结点的右子结点（存放右子结点的存储地址）。V(i)：存放结点的值。L(i)V(i)R(i)现在学习的是第35页，共144页5、二叉树的遍历（P38）前序遍历：先访问根结点，后前序遍历左子树，再前序遍历右子树。中序遍历：先中序遍历左子树，后访问根结点，再中序遍历右子树。后序遍历：先后序遍历左子树，后后序遍历右子树，再访问根结点。对下图进行前序遍历的结果是：ABDECF；中序遍历的结果是：DBEACF；后序遍历的结果是：DEBFCA。FEDCBA现在学习的是第36页，共144
23、页考点七、查找技术（P39）1、顺序查找：适用于无序表或采用链式存储的表（不管有序还是无序）。查找方法：从表头到表尾逐个查找，若相同则结束查找，否则一直继续比较下一个表中元素直到整个表都遍历完。对于长度为n的线性表，平均要进行n/2次比较，在最坏情况下要进行n次比较。2、二分查找：适用于顺序存储的有序表。每次把特查找值与表中间元素比较，以减半的方式缩小搜索范围。对于长度为n的线性表，在最坏情况下要进行 2n次比较。例题分析：请写出用二分查找法在有序顺序表（1、2、3、4、6、8、9、11）中查找3的比较序列：4、2、3123468911现在学习的是第37页，共144页考点八、排序技术(比较次数
24、)（P40）交换类排序：冒泡排序法，快速排序法。插入类排序：简单插入排序法，希尔排序法。选择类排序：简单选择排序法，堆排序法。1、冒泡排序法：通过相邻元素的比较、交换，逐步将线性表变成有序。首先，从表头开始往后扫描线性表，在扫描过程中依次比较相邻两个元素的大小，若前者大于后者则交换它们的位置。这样就将线性表中的最大者换到了表的最后。然后，从后往前扫描剩下的线性表，同样，在扫描过程中依次比较相邻的两个元素的大小，若后者小于前者则交换位置，这样就将线性表中的最小者换到了表的最前面。对剩下的线性表重复上述过程，直到剩下的线性表变空为止。以时已变为有序。假设线性表的长度为n，则在最坏情况下，需经过n/
25、2遍的从前往后扫描和n/2遍的从后往前扫描，需要比较的次数为n(n-1)/2。现在学习的是第38页，共144页例题分析：请写出用冒泡排序法对序列（5，1，7，3，6，9，3，2，7，6）进行第一遍扫描后的中间结果是：5173693276原序列：第1遍现在学习的是第39页，共144页2、快速排序：从线性表中选取一个元素，设为T，将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果就将线性表分成了两部分（称为两个子表），T插入到其分界线的位置处。如此再对两个子表进行分割，直到分割成的子表为空时。对线性表分割的步骤：首先，在表的第一个、中间一个、最后一个元素中选取中项，设为P(k)，并
26、将P(k)赋给T，再将表中第一个元素移到P(k)的位置上。然后，设置两个指针i和j分别指向表的起始与最后的位置，反复操作以下两步：将j逐渐减小，并逐次比较P(j)与T，直到发现一个P(j)T，将P(i)移到P(j)的位置上。现在学习的是第40页，共144页例题分析：用快速排序法对序列（5，1，7，3，6，9，3，2，7，6）进行第一次排序后的中间结果是：5173693276原序列：T：ij现在学习的是第41页，共144页3、简单插入排序：指将无序序列中的各元素依次插入到已经有序的线性表中。一般来说，假设线性表中前j-1个元素已经有序，现在要将线性表中第j个元素插入到前面的有序子表中，插入过程如
27、下：首先将第j个元素放到一个变是T中，然后从有序子表的最后一个元素（即线性表中第j-1个元素）开始，往前逐个与T进行比较，将大于T的元素均向后移动一个位置，直到发现一个元素不大于T为止，此时就将T（即原线性表中的第j个元素）插入到刚移出的空位置上，有序子表的长度就变为j了。在最坏情况下需要比较n(n-1)/2次。例题分析：用简单插入排序法对序列（5，1，7，3，6，9，3，2，7，6）进行排序。原序列：T：5136732769现在学习的是第42页，共144页4、希尔排序：将整个无序序列分割成若干个小的子序列分别进行插入排序（插入排序：开始线性表中只有第1个元素，然后从线性表的第2个元素开始直到
28、最后一个元素，逐次将其中的每一个元素插到前面已经有序的子表中）。子序列的分割方法：将相隔某个增量h（ht=n/2k (k=1,2,3,2n，n为待排序的线性表的长度）的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时进行一次插入排序，排序完成。现在学习的是第43页，共144页例题分析：用希尔排序法对序列（5，1，7，3，6，9，3，2，7，6）进行排序。5173693276原序列：Hk=n/2k(k=1、2、)H1=10/21=55173693276H2=10/22=25173693276H3=10/23=15173693276现在学习的是第44页，共144页5、简单选择排
29、序：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面，然后对剩下的子表采用同样的方法，直到子表空为止。最坏情况下需要比较n(n-1)/2次。例题分析：用简单选择排序法对序列（5，1，7，3，6，9，3，2，7，6）进行排序。5173693276原序列：现在学习的是第45页，共144页6、堆排序：堆的定义如下：具有n个元素的序列（h1、h2、hn），当且仅当满足 hi=h2i hi=h2i+1 hi=1)个结点方法二：特例法3 9frontrear现在学习的是第53页，共144页【2007年9月】一、选择题1、下列叙述中正确的是：（）A、数据的逻辑结构与存储结构必定是一一对应的。B、由于
30、计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构。C、程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构。D、上述三种说法都不对。2、冒泡排序在最坏情况下比较的次数为A)n(n+1)/2 B)nlog2n C)n(n-1)/2 D)n/2 3、一棵二叉树中共有70个叶子结点与80个度为1的结点：由该二叉树中的总结点数为A、219 B、221 C、229 D、231CCA方法一：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。方法二：特例法现在学习的是第54页，共144页二、填空题1、线性表的存储结构主要分为顺序存储结构和链式存储结
31、构。队列是一种特殊的线性表，循环队列是队列的_存储结构。2、对下列二叉树进行中序遍历的结果为_。顺序HPGFBCEADACBDFEHGP现在学习的是第55页，共144页【2007年4月】一、选择题1.下列叙述中正确的是：A、算法的效率只与问题的规模有关,而与数据的存储结构无关。B、算法的时间复杂度是指执行算法所需要的计算工作量。C、数据的逻辑结构与存储结构是一一对应的。D、算法的时间复杂度与闪间复杂度一定相关。2.下列对队列的叙述正确的是：A、队列属于非线性表 B、队列按“先进后出”原则组织数据 C、队列在队尾删除数据 D、队列按“先进先出”原则组织数据 BD现在学习的是第56页，共144页3
32、.对下列二叉树进行前序遍历的结果为：A、DYBEAFCZX B、YDEBFZXCA C、ABDYECFXZ D、ABCDEFXYZ4.某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为：A、n+1 B、n-1 C、2n D、n/2 二、填空题1.在深度为7的满二叉树中,度为2的结点个数为()ZFXAYBCDECA方法一：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。方法二：特例法方法一：满二叉树的第k层上有2k-1(k=1)个结点在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。方法二：特例法63现在学习的是第57页，共144页【2006年
33、9月】一.选择题1.下列叙述中正确的是：A、一个算法的空间复杂度大，则其时间复杂度也必定大。B、一个算法的空间复杂度大，则其时间复杂度必定小。C、一个算法的时间复杂度大，则其空间处长杂度必定小。D、上述三种说法都不对。2.在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为：A、63 B、64 C、6 D、73.对右图二叉树进行中序遍历的结果是：A、ACBDFEG B、ACBDEGE C、ABDCGEF D、FCADBEG FCEADGB二.填空题1.按“先进后出”原则组织数据的数据结构是（）。2.数据结构分为线性结构和非线性结构，带链的队列属于（）。DBA栈线性结构一个非空的线
34、性结构满足如下条件:有且仅有一个根结点;每一个结点最多有一个前件,也最多有一个后件;在一个线性结构中插入或删除一个结点后还是线性结构.如果一个数据结构不是线性结构,则称之为非线性结构.线性结构有:栈,队列,双向链表;非线性结构:树,二叉树.现在学习的是第58页，共144页【2006年4月】一.选择题1.按照“后进先出”原则组织数据的数据结构是：A、队列 B、栈 C、双向链表 D、二叉树2.下列叙述中正确的是：A、线性链表是线性表的链式存储结构 B、栈与队列是非线性结构 C、双向链表是非线性结构 D、只有根结点的二叉树是线性结构3.对右图二叉树进行后序遍历的结果是：A、ABCDEF B、DBEA
35、FC C、ABDECF D、DEBFCA 4.在深度为7的满二叉树中，叶子结点个数为：A、32 B、31 C、64 D、63二.填空题1.对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为（）。ABCDEFBAD方法一：满二叉树的第k层上有2k-1(k=1)个结点方法二：特例法C假设线性表的长度为n，则在最坏情况下，需经过n/2遍的从前往后扫描和n/2遍的从后往前扫描，需要比较的次数为n(n-1)/2。45现在学习的是第59页，共144页【2005年9月】一.选择题1.下列数据结构中，能用二分法进行查找的是：A、顺序存储的有序线性表 B、线性链表 C、二叉链表 D、有序线性链表2.下
36、列关于栈的描述中正确的是：A、在栈中只能插入元素而不能删除元素 B、在栈中只能删除元素而不能插入元素 C、栈是特殊的线性表，只能在一端插入或删除元素 D、栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素3.下列叙述正确的是：A、一个逻辑数据结构只能有一种存储结构 B、数据的逻辑结构属于线性结构，存储结构属于非线性结构 C、一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处 理的效率 D、一个逻辑数据结构可以有多种存储结构，且各种存储结构影响处理的效 率 ACD现在学习的是第60页，共144页【2005年9月】二.填空题1.算法复杂度主要包括时间复杂度和（）复杂度。2.一棵二
37、叉树第六层（根结点为每一层）的结点数最多为（）个。3.数据结构分为逻辑结构和存储结构，循环队列属于（）结构。空间复杂度满二叉树最多第k层上的结点数为2k-1个32存储结构常用的存储结构有顺序、链式和索引存储结构。逻辑结构对应的存储结构线性表顺序表（线性表的顺序存储结构）线性链表（链式存储结构）循环链表（链式存储结构）栈栈的顺序存储结构带链的栈（链式存储结构）队列循环队列（顺序存储结构）带链的队列（链式存储结构）树树的链式存储结构二叉树二叉树的链式存储结构现在学习的是第61页，共144页【2005年4月】一.选择题1.数据的存储结构是指：A、存储在外存中的数据 B、数据所占的存储空间量 C、数据
38、在计算机中的顺序存储方式 D、数据的逻辑结构在计算机中的表示2.下列关于栈的描述中错误的是：A、栈是先进后出的线性表 B、栈只能顺序存储 C、栈具有记忆作用 D、对栈插入与删除操作，不需要改变栈底指针3.对于长度为n的线性表，在最坏情况下，下列各排序所对应的比较次数中正确的是：A、冒泡排序为n/2 B、冒泡排序为n C、快速排序为n D、快速排序为n(n-1)/2D栈可以用来保护断点信息BD现在学习的是第62页，共144页4.对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为：A、2n B、n/2 C、n D、n+15.下列对于线性链表的描述中正确的是：A、存储空间不一定是连续，且
39、各元素的存储顺序是任意的 B、存储空间不一定是连续，且前件元素一定存储在后件元素的前面 C、存储空间必须连续，且前件元素一定存储在后件元素的前面 D、存储空间必须连续，且各元素的存储顺序是任意的二、填空题1.某二叉树中度为2的结点有18个，则该二叉树中有（）个叶子结点。2.问题处理方案的正确而完整的描述称为（）。CA19算法现在学习的是第63页，共144页第二部分 程序设计基础1-2题（2-4分）考试大纲:一、基本要求:1.掌握逐步求精的结构化程序设计方法。二、考试内容1.程序设计方法与风格2.结构化程序设计3.面向对象的程序设计方法、对象、方法、属性及继承与多态性。现在学习的是第64页，共1
40、44页考点一、程序设计方法与风格（P48）1、程序设计方法和技术的发展主要经过了结构化程序设计和面向对象程序设计两个阶段。2、程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思想。程序设计风格会深刻影响软件的质量和可维护性。著名的“清晰第一，效率第二”的论点已经成为当今主要的程序设计风格。3、要形成良好的程序设计风格，主要应注意和考虑下述一些因素：现在学习的是第65页，共144页（1）源程序的文档结构组织对源程序的文档结构的组织要注意以下三点：符号的命名：符号的命名应具有一定的实际含义。程序注释：一般分为序言性注释和功能性注释。视觉组织：在程序中利用空格、空行、缩进等技巧使程序层次清晰。（
41、2）数据说明的方法对数据的说明要注意三点：第一，数据说明的次序规范化；第二，说明语句中变量安排有序化；第三，使用注释来说明复杂数据结构。现在学习的是第66页，共144页（3）语句的结构对语句的结构安排要遵循以下一些原则：在一行内只写一条语句；程序编写应优先考虑清晰性。除非对效率有特殊要求，程序编写要做到清晰第一，效率第二。首先要保证程序正确，然后才要求是提高速度；避免使用临时变量而使程序的可读性下降；避免不必要的转移；尽可能使用库函数；避免复杂的条件语句；尽量少使用“否定”条件的条件语句；数据结构要有利于程序的简化；要模块化，使模块的功能尽可能单一化；利用信息隐蔽，确保每一个模块的独立性；从数
42、据出发去构造程序；不要修补不好的程序，要重新编写。现在学习的是第67页，共144页（4）输入和输出对输入和输出用户界面要注意以下几点：对所有的输入数据都要检验数据的合法性；检查输入项的各种重要组合的合理性；输入格式要简单，以使得输入的步骤和操作尽可能简单；输入数据时，应允许使用自由格式；应允许缺省值；输入一批数据时，最好使用输入结束标志；在以交互式输入/输出方式进行输入时，要在屏幕上使用提示符明确提示输入的请求，同时在数据输入过程中和输入结束时，应屏幕上给出状态信息；当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性；给所有的输出加注释，并设计输出报表格式。现在学习的是第6
43、8页，共144页考点二、结构化程序设计（P50）（1）结构化程序设计的原则在结构化程序中要遵循以下四个基本原则：自顶向下：先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标逐步求精：对复杂问题，先设计一些子目标作过渡，然后逐步细化。模块化：把程序要解决的总目标分解为一个一个的模块。限制使用GOTO语句：程序的质量与GOTO语句的数据成反比。现在学习的是第69页，共144页（2）结构化程序的基本结构与特点结构化程序设计中常采用顺序、选择和循环三种基本结构。结构化程序设计的优点第一：程序易于理解、使用和维护；第二：提高了编程的效率，降低了软件开发成本。结构化程序设计原则和方法的应用应该做到以下
44、几个方面：使用程序设计语言中的顺序、选择、循环等有限的控制结构表示控制逻辑；选用的控制结构只准许有一个入口和一个出口；程序语句组成容易识别的块，每块只有一个入口和一个出口；复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现；语言所没有的控制结构，应该采用前后一致的方法来模拟；严格控制GOTO语句的使用。现在学习的是第70页，共144页考点三、面向对象程序设计（P52）（1）面向对象方法的本质（2）面向对象方法的优点（3）面向对象方法的基本概念（P54）对象：指描述该对象属性的数据以及对这些数据施加的所有操作封装在一起构成的统一体。对象是对问题域中某个实体的抽象。对象的属性和方法：属性是对象所包
45、含的信息，它在设计对象时确定，一般只能通过执行对象操作来改变。方法描述了对象执行的功能，若通过消息传递，还可以为其他对象使用。对象的基本特点：标志唯一性：对象可由其内在本质来区分，而不是通过描述来区分。分类性：可以将具有相同属性和操作的对象抽象成类。多态性：同一操作可以是不同对象的行为。封装性：从外面看不到对象的内部，只能看到对象的外部特性。模块独立性好：一个对象就相当于一个模块。现在学习的是第71页，共144页类和实例：类是具有共同属性、共同方法的对象的集合，类是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例。消息：指对象间的相互协助机制，是一个对象与另
46、一个对象之间传递的消息。消息的组成：消息是由接收消息的对象名称、消息标识符、零个或多个参数组成。继承：指使用已有的类定义作为基础建立新类的定义技术。继承分为单继承和多继承。单继承中一个类只允许有一个父类，多继承中一个类允许有多个父类。多态性：是指同样的消息被不同的对象接受时可导致完全不同的动作的现象。现在学习的是第72页，共144页例年考题分析【2008年9月】一、选择题1.数据流图中带有箭头的线段表示的是：A、控制流B、事件驱动C、模快调用 D、数据流2.在面向对象的方法中，不属于“对象”基本特点的是：A、一致性 B、分类性 C、多态性 D、标识唯一性AD现在学习的是第73页，共144页【2
47、008年4月】一、选择题1.程序流程图中带有箭头的线段表示的是：A、图元关系 B、数据流 C、控制流 D、调用关系 2.结构化程序设计的基本原则不包括：A、多态性 B、自顶向下 C、模块化 D、逐步求精 AC现在学习的是第74页，共144页【2007年9月】一、选择题1.在面向对象方法中，实现信息隐蔽是依靠：A、对象的继承 B、对象的多态 C、对象的封装 D、对象的分类 2.下列叙述中，不符合良好程序设计风格要求的是：A、程序的效率第一，清晰第二 B、程序的可读性好 C、程序中有必要的注释 D、输入数据前要有提示信息 3.下列叙述中正确的是：A、程序执行的效率与数据的存储结构密切相关B、程序执
48、行的效率只取决于程序的控制结构C、程序执行的效率只取决于所处理的数据理D、以上三种说法都不对ACA现在学习的是第75页，共144页【2007年4月】一、选择题1.在结构化程序设计中,模块划分的原则是：A、各模块应包括尽量多的功能 B、各模块的规模应尽量大C、各模快之间的联系应尽量紧密 D、模块内具有高内聚度、模块间具有低耦合度2.下面选项中不属于面向对象程序设计特征的是：A、继承性 B、多态性 C、类比性 D、封装性CD现在学习的是第76页，共144页【2006年9月】1.下列选项中不符合良好程序设计风格的是：A、源程序要文档化 B、数据说明的次序要规范化C、避免滥用goto语句 D、模块设计
49、要保证高耦合、高内聚【2006年4月】1.下列选项中不属于结构化程序设计方法的是：A、自顶向下 B、逐步求精 C、模块化 D、可复用2.在面向对象方法中（）描述的是具有相似属性与操作的一组对象。【2005年4月】1.在面向对象方法中，类的实例称为（）。DD类对象现在学习的是第77页，共144页第三部分 软件工程基础3-5个题（6-10分）一、基本要求掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。二、考试内容1、软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。2、结构化分析方法，数据流图，数据字典，软件需求规格说明书。3、结构化设计方法，总体设计与详细设计。4、软件
50、测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。5、程序的调试，静态调试与动态调试。现在学习的是第78页，共144页(一)软件工程基本概念（P60）1、软件定义与软件特点软件的定义：软件是与计算机操作相关的计算机程序、规程、规则，以及可能有的文件、文档及数据。软件的三个要素：程序、数据和文档。软件的特点：软件作为一种特殊的信息产品，具有以下特点：软件是一种逻辑实体，具有抽象性；软件没有明显的制作过程；软件在运行、使用期间不存在磨损、老化问题；软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导制了软件的移植性；软件复杂性高，成本昂贵；软件