计算机等级考试二课件

计算机等级考试二级教程公共基础知识公共基础知识一、基本数据结构与算法。二、程序设计基础。三、软件工程基础。四、数据库设计基础。2第一部分 数据结构与算法5-7个题（10-14分）考试大纲:一.基本要求:1.掌握算法的基本概念2.掌握基本数据结构及其操作3.掌握基本排序和查找算法3二二.考试内容考试内容:1.算法的基本概念算法的基本概念;算法复杂度的概念和意义算法复杂度的概念和意义(时间复杂度和空间复杂时间复杂度和空间复杂度度)2.数据结构的定义数据结构的定义;数据的逻辑结构与存储结构数据的逻辑结构与存储结构;数据结构的图形表示数据结构的图形表示;线性结构与非线性结构的概念线性结构与非线性结构的概念3.线性表的定义线性表的定义;线性表的顺序存储结构及其插入与删除运算线性表的顺序存储结构及其插入与删除运算4.栈和队列的定义栈和队列的定义;栈和队列的顺序存储结构及其基本运算栈和队列的顺序存储结构及其基本运算5.线性单链表、双向链表与循环链表的结构及其基本运算线性单链表、双向链表与循环链表的结构及其基本运算6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。序和后序遍历。7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）排序，插入类排序）4考点一、算法（P1）一.算法的基本 概念 所谓算法是指解题方案的准确而完善的描述。1.算法的基本特征可行性：是否可行。确定性：指算法中的每一个步骤必须有明确定义，不允许有模棱两可的解释，也不允许有多义性。有穷性：指算法必须在有限的时间内做完，即算法必须能在执行有限个步骤后终止。拥有足够的情报：收集的输入信息等。52.算法的基本要素一个算法通常由两种要素组成：一是对数据对象的运算和操作，二是算法的控制结构。（1）算法中对数据的运算和操作（指令）（P2）算术运算：加、减、乘、除、求余逻辑运算：与、或、非关系运算：大于、小于、等于、不等于数据传输：赋值、输入、输出（2）算法的控制结构（P3）一个算法一般都可以用顺序、选择、循环三种基本控制结构组成。描述算法的工具有：传统流程图、N-S结构化流程图、算法描述语言。6传统流程图、N-S结构化流程图、算法描述语言。条件语句序列1语句序列2ENDIF后面的语句真假条件语句序列1ENDIF后面的语句a=0?yesno输入a,b,c b2-4acdelta b0?delta0?Yes No方程有一个根方程无意义 方程有二个实根方程有二个虚根输出方程的根 noyes3.算法设计的基本方法列举法 归纳法 递推法 递归法 减半递推技术7二.算法的复杂度（P5）算法的复杂度主要包括:时间复杂度和空间复杂度.1.算法的时间复杂度:指执行算法所需要的计算工作量.工作量可以用算法所执行的基本运算次数来度量,而算法所执行的基本运算次数是问题规模的函数 即算法的工作量=f(n)其中n是问题的规模.可以用平均性态和最坏情况复杂性两种方法.82.算法的空间复杂度:指执行这个算法所需要的内存空间.包括算法程序所占的空间、输入的初始数据所占的存储空以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及基本种数据结构所需要的附加存储空间（例如，在链式结构中，除了存储数据本身外，还需要存储链接信息）。9考点二、数据结构的基本概念（P7）数据结构学科主要研究如下三个方面的内容:数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构.在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构.对各种数据结构进行的运算.数据结构学科的研究目的:提高数据处理的效率.主要包括:数据处理速度.尽量节省在数据处理过程中所占用的计算机存储空间.10一.数据结构的定义:指相互关联的数据元素的集合.（P10）1.数据处理:指对数据集合中的各元素以各种方式进行运算.(插入,删除,查找,更改等)2.数据元素:在数据处理领域中,每一个需要处理的对象都可以抽象为数据元素.3.数据结构:是指反映数据元素之间关系的数据元素集合的表示.一个数据结构应包括两方面的信息:一是表示数据元素的信息,二是表示各数据元素之间的前后件关系.11数据的逻辑结构（P11）:指反映数据元素之间逻辑关系的数据结构.它包含两个要素:一是数据元素的集合,通常记为D,二是D上的关系,它反映了D中各数据元素之间的前后件关系,通常记为R,形式表示为:B=(D,R)其中B表示数据结构 为了反映D中各数据元素之间的前后件关系,一般用二元组来表示.例如,假设a与b是D中的两个数据,则二元组(a,b)表示a是b的前件,b是a的后件.这样,在D中的每两个元素之间的关系都可以用这种二元组来表示.12例:一年四季的数据结构可以表示成:B=(D,R)D=春，夏，秋，冬 R=（春,夏）,（夏,秋）,（秋,冬）数据的存储结构（P12）:指数据的逻辑结构在计算机存储空间中的存放形式.也称为物理结构.一般来说,一种数据的逻辑结构根据需要表示成多种存储结构,常用存储结构有顺序,链接,索引等.各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的,而且一般也不可能相同.（P13）13二.数据结构的图形表示 一个数据结构除了用二元关系表示外,还可以直观的用图形表示.图形表示方法:对于数据集合D中的每一个数据元素用中间标有元素值的方框表示,一般称之为数据结点,简称为结点;对于关系R中的每一个二元组,用一条有向线段从前件结点指向后件结点,以表示数据元素之间的前后件关系.春夏秋冬女儿儿子父亲14例:用图形表示数据结构B=(D,R),其中 D=di|1i6=d1,d2,d3,d4,d5,d6 R=(d1,d2),(d1,d3),(d3,d4),(d5,d4),(d5,d6)这个数据结构的图形表示为:d1d2d3d5d4d6注意（P14页）在数据结构中，没有前件的结点称为根结点。没有后件的结点称为终端结点（也称为叶子结点。）15三.线性结构和非线性结构（概念）（P14）数据结构一般分为线性结构和非线性结构两大类.一个非空的线性结构满足如下条件:有且仅有一个根结点;每一个结点最多有一个前件,也最多有一个后件;在一个线性结构中插入或删除一个结点后还是线性结构.如果一个数据结构不是线性结构,则称之为非线性结构.线性结构有:栈,队列,双向链表;非线性结构:树,二叉树.ACBABCABCD161.线性表的基本概念线性表定义:线性表是由n(n=0)个数据元素a1,a2,an组成的一个有限序列,表中的每一个数据元素,除了第一个外,有且只有一个前件,除了最后一个外,有且只有一个后件.即线性表或是一个空表,或是可以表示为:(a1,a2,an)其中ai(i=1,2,n)是属于数据对象的元素,通常也称为线性表中的一个结点.非空线性表的基本特征:有且只有一个根结点a1，它无前件；有且只有一个终端结点an，它无后件；除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表的长度：线性表中结点的个数n称为线性表的长度。当n=0时，称为空表。考点三、线性表及其顺序存储结构172.线性表的顺序存储结构（P16）具有两个基本特点：线性表中所有元素所占的存储空间是连续的；线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。由此可以看出，在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件一定存储在后件元素的前面。18线性表的随机存取地址的计算公式：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线性表的主要操作:插入、删除、查找、排序、分解、合并、复制、逆转193.线性表的插入运算一个长度为n的线性表，要在第i（1in）个元素之前插入一个新元素时，首先要从最后一个（即第n个）元素开始向后移动一个位置，直到第i个元素之间的n-i+1个元素依次向后移动一个位置，移动结束后，第i个位置就被空出，然后将新元素插入到第i项。插入结束后，线性表的长度就增加了1，变为n+1.其时间复杂度，在平均情况下，需要移动一半的元素，最坏情况下要移动所有元素。204731243536561829473124353656182947312435365618872912345678910123456789101234567891087线性表顺序存储结构的适用场合：对于小线性表或者其中元素不常变动的线性表来说是合适的，因为顺序存储的结构比较简单，对于元素需要变动的大线性表就不太合适了，因为插入和删除的效率比较低。214.线性表的删除运算要删除第i（1in）个元素时，首先要从第i+1个元素开始，直到最后一个（即n个）元素之间的n-1个元素依次向前移动一个位置。删除结束后，线性表的长度就减少了1。变为n-1。删除操作的时间复杂度：在平均情况下，需要移动表中一半的元素，最坏情况下要移动表中的所有元素。22考点四、栈和队列(重点)（P19）1、栈及其基本运算(1)栈的定义:栈是限定在一端进行插入和删除操作的线性表.它按照”后进先出”(或”先进后出”)的原则组织数据.(2)栈的顺序存储:在程序设计语言中一般是用一维数据S(1:m)作为栈的顺序存储空间,其中m为栈的最大容量.(3)栈的基本运算入栈运算:首先将栈顶指针(top)加1,然后将新元素插入到栈顶指针指向的位置.当栈顶指针已经指向存储空间的最后一个位置时说明本栈空间已满,不可能再进行入栈操作.退栈操作:首先将栈顶元素赋给一个指定的变量,然后将栈顶指针(top)减1.当栈顶指针为0时,说明栈空,不可能再进行退栈操作.读栈顶元素:将栈顶元素赋给一个指定的变量,栈指针(top)不变.当栈顶指针为0时,说明栈空,读栈顶元素操作失败.23ABCDEF10987654321topbottomABCD10987654321topbottom入栈入栈退栈退栈242、队列及其基本运算（P21）（1）队列的定义：队列是指允许在一端进行插入、而在另一端进行删除的线性表。它按照“先进先出”的原则组织数据。FEDCBA退队入队frontrear（2）循环队列：将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。（3）循环队列的基本运算入队运算：首先将队尾指针加1（real=real+1），并当real=m+1时，置real=1，然后将新元素插入到指针指向的位置。退队运算：首先将排头指针加1（front=front+1），并当front=m+1时置front=1，然后将排头指针指向的元素赋给指定的变量。25ABCDEF87654321realfront具有6个元素的循环队列加入X和Y后的循环队列realABCDEF87654321frontXYBCDEF87654321frontXYreal退出一个元素后的循环队列栈和队列都是顺序存储的。26考点五、线性链表（P24）1、线性链表的基本概念：线性表的链式存储结构称为线性链表。线性链表的存储结构：线性链表的每个结点中数据域存放数据元素的值，指针域存放后件结点的存储地址。双向链表的存储结构：双向链表的存储结构比线性链表的存储结构多出一个指针域，它用来存放前件结点的存放地址。带链的栈，带链的队列HEADA0BH0HEAD0272、线性链表的基本运算（P27）：插入、删除、合并、分解、逆转、复制、排序、查找。线性链表的插入：先从栈中为新元素分配一个新的结点q，并赋值。然后利用线性链表的查找算法找到待插入位置的前一个结点的指针p。先将q指向p的后件，然后将q挂在p结点的后面。xpxpq28线性链表的删除：先找到待删除元素的前一个结点p，用另一个指针q暂时保存p的后续结点（即待删除结点），然后把q结点的后续链直接挂接在p的后面。最后归还q结点所分配的栈空间。xpq293、循环链表（P30）：循环链表的几个特点：在循环链表中增加一个表头结点，使得循环链表对空表和非空表的操作实现了统一。循环链表中最后一个结点的指针域不是空，而是指向表头结点。判断循环链表是否为空的办法不是看表头指针为空，而是看表头结点的后续结点是否还是表头结点。在循环链表中，从任何一个结点出发都可以访问到表中其它所有的结点。xYHEADz30考点六、树与二叉树(重点)（P31）1、树的基本概念树是一种非线性结构，在树的这种数据结构中，所有数据元素之间的关系具有明显的层次特性。父结点：在树结构中，每一个结点只有一个前件结点，称为父结点。根结点：没有前件的结点只有一个，称为树的根结点。子结点：每一个结点可以有多个后件，它们都称为该结点的子结点。叶子结点：没有后件的结点称为叶子结点。IKGFHEDCBAR31结点的度：一个结点所拥的后件个数称为该结点的度。树的度：在树中，所有结点中的最大的度称为树的度。树的深度：树的最大层次称为树的深度，树的深度也可以称为树的高度，根结点在第1层。子树：在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。叶子结点没有子树。IKGFHEDCBAR32IKGFHECBR2、二叉树及其基本性质（P34）二叉树的两个特点：非空二叉树只有一个根结点；每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。二叉树的基本性质：在二叉树的第k层上，最多有 2k-1(k=1)个结点。深度为m的二叉树最多有2m-1个结点。在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。具有n个结点的二叉树，其深度至少为2n+1。33FGEHDCBAIJKMLPNFGEHDCBAIJK3、满二叉树和完全二叉树（P35）满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。完全二叉树：除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。基本性质：满二叉树的第k层上有2k-1(k=1)个结点，且深度为m的二叉树有2m-1个结点。具有n个结点的完全二叉树的深度为2n+1。设完全二叉树共有n个结点，如果从根结点开始，按层序（第一层从左到右）用自然数1、2、n给结点进行编号，则对于编号为k的结点有以下结论：若k=1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点编号为INT(K/2)。34若2k=n，则编号为k的结点的左子结点编号为2k，否则该结点无左子结点（显然也没有右子结点）若2k+1=n，则编号为k的结点的右子结点编号为2k+1，否则该结点无右子结点。FGEHDCBAIJK355、二叉树的遍历（P38）前序遍历：先访问根结点，后前序遍历左子树，再前序遍历右子树。中序遍历：先中序遍历左子树，后访问根结点，再中序遍历右子树。后序遍历：先后序遍历左子树，后后序遍历右子树，再访问根结点。对下图进行前序遍历的结果是：ABDECF；中序遍历的结果是：DBEACF；后序遍历的结果是：DEBFCA。FEDCBA36考点七、查找技术（P39）1、顺序查找：适用于无序表或采用链式存储的表（不管有序还是无序）。查找方法：从表头到表尾逐个查找，若相同则结束查找，否则一直继续比较下一个表中元素直到整个表都遍历完。对于长度为n的线性表，平均要进行n/2次比较，在最坏情况下要进行n次比较。2、二分查找：适用于顺序存储的有序表。每次把特查找值与表中间元素比较，以减半的方式缩小搜索范围。对于长度为n的线性表，在最坏情况下要进行 2n次比较。例题分析：请写出用二分查找法在有序顺序表（1、2、3、4、6、8、9、11）中查找3的比较序列：4、2、312346891137考点八、排序技术(比较次数)（P40）交换类排序：冒泡排序法，快速排序法。插入类排序：简单插入排序法，希尔排序法。选择类排序：简单选择排序法，堆排序法。1、冒泡排序法：通过相邻元素的比较、交换，逐步将线性表变成有序。首先，从表头开始往后扫描线性表，在扫描过程中依次比较相邻两个元素的大小，若前者大于后者则交换它们的位置。这样就将线性表中的最大者换到了表的最后。然后，从后往前扫描剩下的线性表，同样，在扫描过程中依次比较相邻的两个元素的大小，若后者小于前者则交换位置，这样就将线性表中的最小者换到了表的最前面。对剩下的线性表重复上述过程，直到剩下的线性表变空为止。以时已变为有序。假设线性表的长度为n，则在最坏情况下，需经过n/2遍的从前往后扫描和n/2遍的从后往前扫描，需要比较的次数为n(n-1)/2。38例题分析：请写出用冒泡排序法对序列（5，1，7，3，6）进行第一遍扫描后的中间结果是：(从小到大）51736原序列：第1遍51736第2遍1736第3遍第4遍51736517365392、快速排序：从线性表中选取一个元素，设为T，将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果就将线性表分成了两部分（称为两个子表），T插入到其分界线的位置处。如此再对两个子表进行分割，直到分割成的子表为空时。对线性表分割的步骤：首先，在表的第一个、中间一个、最后一个元素中选取中项，设为P(k)，并将P(k)赋给T，再将表中第一个元素移到P(k)的位置上。然后，设置两个指针i和j分别指向表的起始与最后的位置，反复操作以下两步：将j逐渐减小，并逐次比较P(j)与T，直到发现一个P(j)T，将P(i)移到P(j)的位置上。40例题分析：用快速排序法对序列（5，1，7，3，6，9，3，2，7，6）进行第一次排序后的中间结果是：5173693276原序列：T：ij173693276ij541查找技术的比较次数：对于长度为n的线性表，1.顺序查找：平均要进行n/2次比较，在最坏情况下要进行n次比较。2.二分查找：在最坏情况下要进行 2n次比较。各类排序的时间复杂度：对于长度为n的线性表，在最坏情况下，需要比较的次数：1.冒泡排序：n(n-1)/2 2.快速排序：n(n-1)/2 3.简单插入排序：n(n-1)/24.希尔排序：O(n1.5)5.简单选择排序：n(n-1)/26.堆排序：O(n2n)。42例年考题分析【2008年9月】一、选择题1、一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是：A、12345ABCDE。B、EDCBA54321。C、ABCDE12345。D、54321EDCBA。2、下列叙述中正确的是：A、循环队列有队头和队尾两个指针，因此，循环队列是非线性结构 B、在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况 C、在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况 D、循环队列中元素的个数是由队头指针和队尾指针共同决定3、在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是：A、O(n)B、O(n2)C、O(log2n)D、O(nlog2n)BDC43【2008年9月】二、填空题1、对下列二叉树进行中序遍历的结果是_ DBXEAYFZC ABCDEFXYZ44【2008年4月】一、选择题1、算法的有穷性是指（）A)算法程序的运行时间是有限的 B)算法程序所处理的数据量是有限的 C)算法程序的长度是有限的 D)算法只能被有限的用户使用2、对长度为n的线性表排序，在最坏情况下，比较次数不是n(n-1)/2的排序方法是A)快速排序 B)冒泡排序 C)直线插入排序 D)堆排序3、下列关于栈的叙述正确的是A)栈按“先进先出”组织数据 B)栈按“先进后出”组织数据 C)只能在栈底插入数据 D)不能删除数据BDB45【2008年4月】二、填空题1、深度为5的满二叉树有_个叶子结点。2、设某循环队列的容量为50，头指针front=5(指向队头元素的前一位置)，尾指针rear=29(指向对尾元素)，则该循环队列中共有_个元素。1624方法一：满二叉树的第k层上有2k-1(k=1)个结点方法二：特例法3 9frontrear46【2007年9月】一、选择题1、下列叙述中正确的是：（）A、数据的逻辑结构与存储结构必定是一一对应的。B、由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构。C、程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构。D、上述三种说法都不对。2、冒泡排序在最坏情况下比较的次数为A)n(n+1)/2 B)nlog2n C)n(n-1)/2 D)n/2 CC47二、填空题1、线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的_存储结构。2、对下列二叉树进行中序遍历的结果为_。顺序HPGFBCEADACBDFEHGP48【2007年4月】一、选择题1.下列叙述中正确的是：A、算法的效率只与问题的规模有关,而与数据的存储结构无关。B、算法的时间复杂度是指执行算法所需要的计算工作量。C、数据的逻辑结构与存储结构是一一对应的。D、算法的时间复杂度与空间复杂度一定相关。2.下列对队列的叙述正确的是：A、队列属于非线性表 B、队列按“先进后出”原则组织数据 C、队列在队尾删除数据 D、队列按“先进先出”原则组织数据 BD493.对下列二叉树进行前序遍历的结果为：A、DYBEAFCZX B、YDEBFZXCA C、ABDYECFXZ D、ABCDEFXYZ4.某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为：A、n+1 B、n-1 C、2n D、n/2 ZFXAYBCDECA方法一：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。方法二：特例法50【2006年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.数据结构分为线性结构和非线性结构，带链的队列属于（）。DAA栈线性结构一个非空的线性结构满足如下条件:有且仅有一个根结点;每一个结点最多有一个前件,也最多有一个后件;在一个线性结构中插入或删除一个结点后还是线性结构.如果一个数据结构不是线性结构,则称之为非线性结构.线性结构有:栈,队列,双向链表;非线性结构:树,二叉树.51【2006年4月】一.选择题1.按照“后进先出”原则组织数据的数据结构是：A、队列 B、栈 C、双向链表 D、二叉树2.下列叙述中正确的是：A、线性链表是线性表的链式存储结构 B、栈与队列是非线性结构 C、双向链表是非线性结构 D、只有根结点的二叉树是线性结构3.对右图二叉树进行后序遍历的结果是：A、ABCDEF B、DBEAFC 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。4552【2005年9月】一.选择题1.下列数据结构中，能用二分法进行查找的是：A、顺序存储的有序线性表 B、线性链表 C、二叉链表 D、有序线性链表2.下列关于栈的描述中正确的是：A、在栈中只能插入元素而不能删除元素 B、在栈中只能删除元素而不能插入元素 C、栈是特殊的线性表，只能在一端插入或删除元素 D、栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素3.下列叙述正确的是：A、一个逻辑数据结构只能有一种存储结构 B、数据的逻辑结构属于线性结构，存储结构属于非线性结构 C、一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处 理的效率 D、一个逻辑数据结构可以有多种存储结构，且各种存储结构影响处理的效 率 ACD53【2005年9月】二.填空题1.算法复杂度主要包括时间复杂度和（）复杂度。2.一棵二叉树第六层（根结点为每一层）的结点数最多为（）个。3.数据结构分为逻辑结构和存储结构，循环队列属于（）结构。空间复杂度满二叉树最多第k层上的结点数为2k-1个32存储常用的存储结构有顺序、链式和索引存储结构。逻辑结构对应的存储结构线性表顺序表（线性表的顺序存储结构）线性链表（链式存储结构）循环链表（链式存储结构）栈栈的顺序存储结构带链的栈（链式存储结构）队列循环队列（顺序存储结构）带链的队列（链式存储结构）树树的链式存储结构二叉树二叉树的链式存储结构54【2005年4月】一.选择题1.数据的存储结构是指：A、存储在外存中的数据 B、数据所占的存储空间量 C、数据在计算机中的顺序存储方式 D、数据的逻辑结构在计算机中的表示2.下列关于栈的描述中错误的是：A、栈是先进后出的线性表 B、栈只能顺序存储 C、栈具有记忆作用 D、对栈插入与删除操作，不需要改变栈底指针3.对于长度为n的线性表，在最坏情况下，下列各排序所对应的比较次数中正确的是：A、冒泡排序为n/2 B、冒泡排序为n C、快速排序为n D、快速排序为n(n-1)/2D栈可以用来保护断点信息dD554.对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为：A、2n B、n/2 C、n D、n+15.下列对于线性链表的描述中正确的是：A、存储空间不一定是连续，且各元素的存储顺序是任意的 B、存储空间不一定是连续，且前件元素一定存储在后件元素的前面 C、存储空间必须连续，且前件元素一定存储在后件元素的前面 D、存储空间必须连续，且各元素的存储顺序是任意的二、填空题1.问题处理方案的正确而完整的描述称为（）。CA算法56第二部分 程序设计基础1-2题（2-4分）考试大纲:一、基本要求:1.掌握逐步求精的结构化程序设计方法。二、考试内容1.程序设计方法与风格2.结构化程序设计3.面向对象的程序设计方法、对象、方法、属性及继承与多态性。57考点一、程序设计方法与风格（P48）1、程序设计方法和技术的发展主要经过了结构化程序设计和面向对象程序设计两个阶段。2、程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思想。程序设计风格会深刻影响软件的质量和可维护性。著名的“清晰第一，效率第二”的论点已经成为当今主要的程序设计风格。3、要形成良好的程序设计风格，主要应注意和考虑下述一些因素：58（1）源程序的文档结构组织对源程序的文档结构的组织要注意以下三点：符号的命名：符号的命名应具有一定的实际含义。程序注释：一般分为序言性注释和功能性注释。视觉组织：在程序中利用空格、空行、缩进等技巧使程序层次清晰。（2）数据说明的方法对数据的说明要注意三点：第一，数据说明的次序规范化；第二，说明语句中变量安排有序化；第三，使用注释来说明复杂数据结构。59（3）语句的结构对语句的结构安排要遵循以下一些原则：在一行内只写一条语句；程序编写应优先考虑清晰性。除非对效率有特殊要求，程序编写要做到清晰第一，效率第二。首先要保证程序正确，然后才要求是提高速度；避免使用临时变量而使程序的可读性下降；避免不必要的转移；尽可能使用库函数；避免复杂的条件语句；尽量少使用“否定”条件的条件语句；数据结构要有利于程序的简化；要模块化，使模块的功能尽可能单一化；利用信息隐蔽，确保每一个模块的独立性；从数据出发去构造程序；不要修补不好的程序，要重新编写。60（4）输入和输出对输入和输出用户界面要注意以下几点：对所有的输入数据都要检验数据的合法性；检查输入项的各种重要组合的合理性；输入格式要简单，以使得输入的步骤和操作尽可能简单；输入数据时，应允许使用自由格式；应允许缺省值；输入一批数据时，最好使用输入结束标志；在以交互式输入/输出方式进行输入时，要在屏幕上使用提示符明确提示输入的请求，同时在数据输入过程中和输入结束时，应屏幕上给出状态信息；当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性；给所有的输出加注释，并设计输出报表格式。61考点二、结构化程序设计（P50）（1）结构化程序设计的原则在结构化程序中要遵循以下四个基本原则：自顶向下：先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标逐步求精：对复杂问题，先设计一些子目标作过渡，然后逐步细化。模块化：把程序要解决的总目标分解为一个一个的模块。限制使用GOTO语句：程序的质量与GOTO语句的数据成反比。62（2）结构化程序的基本结构与特点结构化程序设计中常采用顺序、选择和循环三种基本结构。结构化程序设计的优点第一：程序易于理解、使用和维护；第二：提高了编程的效率，降低了软件开发成本。结构化程序设计原则和方法的应用应该做到以下几个方面：使用程序设计语言中的顺序、选择、循环等有限的控制结构表示控制逻辑；选用的控制结构只准许有一个入口和一个出口；程序语句组成容易识别的块，每块只有一个入口和一个出口；复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现；语言所没有的控制结构，应该采用前后一致的方法来模拟；严格控制GOTO语句的使用。63考点三、面向对象程序设计（P52）（1）面向对象方法的本质（2）面向对象方法的优点（3）面向对象方法的基本概念（P54）对象：指描述该对象属性的数据以及对这些数据施加的所有操作封装在一起构成的统一体。对象是对问题域中某个实体的抽象。对象的属性和方法：属性是对象所包含的信息，它在设计对象时确定，一般只能通过执行对象操作来改变。方法描述了对象执行的功能，若通过消息传递，还可以为其他对象使用。对象的基本特点：标志唯一性：对象可由其内在本质来区分，而不是通过描述来区分。分类性：可以将具有相同属性和操作的对象抽象成类。多态性：同一操作可以是不同对象的行为。封装性：从外面看不到对象的内部，只能看到对象的外部特性。模块独立性好：一个对象就相当于一个模块。64类和实例：类是具有共同属性、共同方法的对象的集合，类是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例。消息：指对象间的相互协助机制，是一个对象与另一个对象之间传递的消息。消息的组成：消息是由接收消息的对象名称、消息标识符、零个或多个参数组成。继承：指使用已有的类定义作为基础建立新类的定义技术。继承分为单继承和多继承。单继承中一个类只允许有一个父类，多继承中一个类允许有多个父类。多态性：是指同样的消息被不同的对象接受时可导致完全不同的动作的现象。65例年考题分析【2008年9月】一、选择题2.在面向对象的方法中，不属于“对象”基本特点的是：A、一致性 B、分类性 C、多态性 D、标识唯一性A66【2008年4月】一、选择题2.结构化程序设计的基本原则不包括：A、多态性 B、自顶向下 C、模块化 D、逐步求精 A67【2007年9月】一、选择题1.在面向对象方法中，实现信息隐蔽是依靠：A、对象的继承 B、对象的多态 C、对象的封装 D、对象的分类 2.下列叙述中，不符合良好程序设计风格要求的是：A、程序的效率第一，清晰第二 B、程序的可读性好 C、程序中有必要的注释 D、输入数据前要有提示信息 3.下列叙述中正确的是：A、程序执行的效率与数据的存储结构密切相关B、程序执行的效率只取决于程序的控制结构C、程序执行的效率只取决于所处理的数据理D、以上三种说法都不对ACA68【2007年4月】一、选择题2.下面选项中不属于面向对象程序设计特征的是：A、继承性 B、多态性 C、类比性 D、封装性C69【2006年9月】1.下列选项中不符合良好程序设计风格的是：A、源程序要文档化 B、数据说明的次序要规范化C、避免滥用goto语句 D、模块设计要保证高耦合、高内聚【2006年4月】1.下列选项中不属于结构化程序设计方法的是：A、自顶向下 B、逐步求精 C、模块化 D、可复用2.在面向对象方法中（）描述的是具有相似属性与操作的一组对象。【2005年4月】1.在面向对象方法中，类的实例称为（）。DD类对象7071第三部分 软件工程基础3-5个题（6-10分）一、基本要求掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。二、考试内容1、软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。2、结构化分析方法，数据流图，数据字典，软件需求规格说明书。3、结构化设计方法，总体设计与详细设计。4、软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。5、程序的调试，静态调试与动态调试。72(一)软件工程基本概念（P60）1、软件定义与软件特点软件的定义：软件是与计算机操作相关的计算机程序、规程、规则，以及可能有的文件、文档及数据。软件的三个要素：程序、数据和文档。软件的特点：软件作为一种特殊的信息产品，具有以下特点：软件是一种逻辑实体，具有抽象性；软件没有明显的制作过程；软件在运行、使用期间不存在磨损、老化问题；软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导制了软件的移植性；软件复杂性高，成本昂贵；软件开发涉及诸多的社会因素。73软件分类:软件按功能可分为应用软件、系统软件和支撑软件(或工具软件)三大类。支撑软件是介于系统软件和应用软件之间，协调用户开发软件的工具性软件。2、软件危机与软件工程（P61）软件危机的含义：软件危机泛指在计算机软件的开发和维护中所遇到的一系列严重问题。软件危机主要表现为：软件需求的增长得不到满足；软件开发的成本和进度无法控制；软件质量难以保证；软件不可维护或维护程度非常低；软件的成本不断提高；软件开发生产率的提高跟不上硬件的发展和应用需要的增长。软件危机产生的原因：宏观方面是由于软件日益深入社会生活的各个层面，对软件需求的增长速度大大超过了技术进步所能带来的软件生产率的提高。而就每一项具体的工程任务来看，软件危机许多困难来源于软件工程所面临的任务和其它工程之间的差异以及软件和其他工业产品的不同。74软件工程的定义（P62）软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。软件工程的三个要素：方法、工具和过程。方法是完成软件工程项目的技术手段；工具支持软件的开发、管理、文档生成；过程支持软件开发的各个环节的控制、管理。软件工程的核心思想是软件当作一个工程产品来处理。75（3）软件工程过程与软件生命周期（P63）软件工程过程定义：软件工程过程是把输入转化为输出的一组相关的资源和活动。内涵：软件工程过程是指为获得软件产品，在软件工具支持下由软件工程师完成的一系列软件过程活动。从软件开发的观点来看，它就是使用适当的资源，为开发软件进行的一组开发活动，在过程结束时将输入（用户要求）转化为输出（软件产品）。软件工程过程包含的4个基本活动：软件规格说明（P）、软件开发（D）、软件确认（C）和软件演进（A）。76软件生命周期（P63）定义：软件生命周期就是软件产品从提出、实现、使用维护到停止使用退役的全过程。三个阶段：软件生命周期包括软件定义、软件开发及软件维护三个阶段（每个阶段的任务）。软件定义阶段的任务包括可行性研究与计划制定、需求分析；软件开发阶段的任务包括概要设计、详细设计、软件实现、软件测试；软件维护的任务包括软件的运行、维护和退役。77可行性研究初步项目计划需求分析概要设计详细设计实现测试使用维护退役定义阶段开发阶段维护阶段软件生命周期784、软件工程的目标与原则（P64）软件工程的目标软件工程的目标是，以给定成本、进度的前提下，开发出具有时效性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。软件工程的理论和技术性研究的内容：软件开发技术：软件开发技术包括软件开发方法学、开发过程、开发工具、软件工程环境等内容。软件工程管理：软件工程管理包括软件管理学、软件工程经济学、软件心理学等内容。软件工程的原则包括：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。795、软件开发工具与软件开发环境（P65）软件开发工具：软件工具的发展是从单项工具的开发逐步向集成工具发展的，软件工具为软件工程的方法提供了自动的或半自动的软件支撑环境。软件开发环境：软件开发环境是全面支持软件开发过程的软件工具集合。计算机辅助软件工程是当前软件开发环境中富有特色研究工作和发展方向。80(二)结构化分析方法软件开发方法包括分析方法、设计方法和程序设计方法。结构化方法包括结构化分析方法、结构化设计方法和结构化编程方法。1、需求分析与需求分析方法需求分析：软件需求是指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。需求分析的任务是发现需求、求精、建模和定义需求的过程。主要包括：需求获取、需求分析、编写需求规格说明书和需求评审。需求分析方法：常见的有结构化分析方法和面向对象分析方法两种。需求分析方法：常见的有结构化分析方法和面向对象分析方法两种。结构化结构化分析方法主要包括分析方法主要包括面向数据流的结构化分析方法（面向数据流的结构化分析方法（SA）、面向数据结构的）、面向数据结构的Jackson方法（方法（JSD）、面向数据结构的结构化数据系统开发方法（）、面向数据结构的结构化数据系统开发方法（DSSD）。从）。从需求分析建立的模型的特性来分，需求分析方法又分为静态分析方法和动态分需求分析建立的模型的特性来分，需求分析方法又分为静态分析方法和动态分析方法。析方法。812、结构化分析方法结构化分析方法是结构化程序设计理论在软件需求分析阶段的应用。它是基于功能分解的分析方法，其目的是帮助弄清用户对软件的需求。结构化分析的常用工具有数据流图（DFD）、数据字典（DD）、判定树和判定表。其中最重要的工具是数据流图。其中最重要的工具是数据流图。数据流图中的主要图形元素数据流图中的主要图形元素有加工（用有加工（用表示）、表示）、数据流（用数据流（用表示）表示）、存储文件（又叫数据源，用、存储文件（又叫数据源，用表示）表示）以及源（又叫潭，用以及源（又叫潭，用表示）。表示）。建立数据流图的步骤是：建立数据流图的步骤是：第第1步：由外向里：先画系统的输入和输出，然后画系统内部；步：由外向里：先画系统的输入和输出，然后画系统内部；第第2步：自顶向下：顺序完成顶层、中间层、底层数据流图；步：自顶向下：顺序完成顶层、中间层、底层数据流图；第第3步：逐层分解。步：逐层分解。数据字典：是对DFD中出现的被命名的图形元素的确切解释。823、软件需求规格说明书软件需求规格说明书（SRS）是需求分析阶段的最后结果，是软件开发中的重要文档之一。软件需求规格说明书有以下几个作用：便于用户、开发人员进行理解和交流。反映出用户问题的结构，可以作为软件开发工作的基础和依据。作为确认测试和验收的依据。软件需求规格说明书的内容：包括概述、数据描述、功能描述、参考文献目录和附录。软件需求规格说明书的特点：软件需求规格说明书具有正确性、无歧义性、完整性、可验证性、一致性、可理解性、可修改性和可追踪性等特点。83（三）结构化设计方法（P73）1、软件设计概念软件设计是软件工程的重要阶段，是一个把软件需求转换为软件表示的过程。软件设计的重要性和地位：a.软件开发阶段（设计、编码、测试）占软件项目开发总成本绝大部分，是在软件开发中形成质量的关键环节；b.软件设计是开发阶段最重要的步骤，是将需求准确地转化为完整的软件产品或系统唯一途径；c.软件设计作出的决策，最终影响软件实现的成败；d.设计是软件工程和软件维护的基础。84软件设计的内容：从技术观点看，软件设计包括结构设计、数据设计、接口设计和过程设计。其中结构设计是定义软件系统各主要部件之间的关系。数据设计是将分析时创建的模型转化为数据结构的定义。接口设计是描述软件内部、软件和协作系统之间以及软件与人之间如何通信。过程设计是把系统结构部件换成软件的过程性描述。从工程管理角度看，软件设计包括概要设计和详细设计。概要设计的任务是将软件需求转化为软件体系统结构、确定系统级接口、全局数据结构或数据库模式。详细设计的任务是确立每个模块的实现算法和局部数据结构，用适当方法表示算法和数据结构的细节。85其中度量模块独立性的标准是模块内部的内聚性和模块间的耦合性。模块的内聚性模块的内聚性是指一个模块内部各个元素之间彼些结合的紧密程度的度量。内聚有如下种类，它们之间的内聚性由弱到强的排列为：偶然内聚、逻辑内聚、时间内聚、过程内聚、通信内聚、顺序内聚、功能内聚。模块的偶合性模块的偶合性是指模块间相连接的紧密程度的度量。模块间的耦合有以下几种，它们由强到弱排列为：内容耦合、公共耦合、外部耦合、控制耦合、标记耦合、数据耦合、非直接耦合。结构化设计方法的基本思想：将软件设计成由相对独立、单一功能的模块组成的结构。软件设计的基本原理:抽象、模块化、信息隐蔽和模块独立性。为了提高模块的独立性，应该尽量提高模块的内聚性，降低模块间的耦合性。(低内聚，高耦合）862、概要设计（P75）在需求分析阶段，已经将系统分解成层次结构，而在概要设计阶段，需要进一步分解，划分为模块以及模块的层次结构。概要设计的基本任务：设计软件系统结构、确定数据结构及数据库设计、编写概要设计文档、进行概要设计文档评审。软件结构设计工具：结构图（SC），也称为程序结构图。结构图的有关术语：深度：表示控制的层数。宽度：整体控制跨度（最大模块数的层）的表示。扇入、扇出：扇入是指调用一个给定模块的模块数；扇出指一个模块直接调用其他模块数。原子模块：树中位于叶子结点的模块。面向数据流的设计方法：数据流类型：典型的数据流类型有两种，变换型和事务型。变换型是指信息沿输入通路进入系统，同时由外部形式变换成内部形式，进入系统的信息通过变换中心，经过加工处理后再沿输出通路变换成外部形式离开软件系统。在很多软件应用中，存在某种作业数据流，它可以引发一个或多个处理，这些处理能够完成作业要求的功能，这种数据流叫做事务型数据流。873、详细设计详细设计的任务：为软件结构图中的每一个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。过程设计的任务：对每相模块规定的功能以及算法的设计，给出适当的算法描述。过程设计的工具：常用工具有图形工具（程序流程图、N-S图、PAD图（问题分析图）、HIPO）、表格工具（判定表）和语言工具（PDL（过程设计语言）。条件语句序列1ENDIF后面的语句控制流加工步骤逻辑条件88（四）软件测试（P85）软件测试是保证软件质量的重要手段，其主要过程涵盖了整个软件生命周期的过程，包括需求定义阶段的需求测试，编码阶段的单元测试、集成测试以及后期的确认测试、系统测试，验证软件是否合格、能否交给用户使用等。1、软件测试的目的软件测试是为了发现错误而执行程序的过程。2、软件测试用例包括两部分：输入值集和输入值集892、软件测试的准则软件测试过程中应遵循以下准则：所有测试都应追溯到需求严格执行测试计划，排除测试的随意性充分注意测试中的群集现象程序员应避免检查自己的程序穷举测试不可能妥善保存测试计划、测试用例、出错统计和最终分析报告。3、软件测试技术与方法综述（P86）软件测试从是否要执行被测试软件的角度可以分为静态测试和动态测试。静态测试：静态测试包括代码检查、静态结构分析、代码质量度量等。动态测试：动态测试是基于计算机的测试，是为了发现错误而执行程序的过程。90软件测试按照功能划分可以分为白盒测试和黑盒测试方法。白盒测试：是根据软件产品的内部工作过程，检查内部成分，以确认每种内部操作符合设计规范要求。白盒测试的基本原则：保证所测模块中每一独立路径至少执行一次；保证所测模块所有判断的每一分支至少执行一次；保证所测模块每一循环都在边界条件和一般条件下至少各执行一次；验证所有内部数据结构的有效性。白盒测试的主要方法：1）逻辑覆盖法泛指一系列以程序内部的逻辑结构为基础的测试用例设计技术。逻辑覆盖法有语句覆盖、路径覆盖、判定覆盖、条件覆盖以及判断-条件覆盖。2）基本路径测试法基本路径测试的思想和步骤是，根据软件过程性描述中的控制流程确定程序的环路复杂性度量，用此度量定义基本路径集合，并由此导出一组测试用例对每一条独立执行路径进行测试。91黑盒测试法（P90）：是对软件已经实现的功能是否满足需求进行测试和验证。黑盒测试的方法：1）等价类划分法：将程序的所有可能的输入数据划分成若干部分（即若干等价类），然后从每个等价类中选取数据作为测试用例。2）边界值分析法：边界分析法是对各种输入、输出范围的边界情况设计测试用例的方法。3）错误推测法：靠经验和直觉推测程序中可能存在的各种错误，从而有针对性地编写检查这些错误的例子的方法。924、软件测试的实施（P93）软件测试过程一般按4个步骤进行，即单元测试、集成测试、验收测试（确认测试）和系统测试。单元测试：是对软件设计的最小单位模块进行正确性检验的测试。主要目的是发现各模块内部可能存在的各种错误。集成测试：是把模块在按照设计要求组装起来的同时进行测试，主要目的是发现与接口有关的错误。确认测试：其任务是验证软件的功能和性及其他特性是否满足了需求规格说明中确定的各种需求，以及软件配置是否安全、正确。系统测试：是将通过测试确认的软件，作为整个基于计算机系统的一个元素，与计算机硬件、外高、支持软件、数据和人员等其他系统元素组合在一起，在实际运行环境下对计算机系统进行一系列的集成测试和确认测试。93（五）程序的调试（P96）程序调试的任务是诊断和改正程序中的错误它与软件测试不同软件测试是尽可能多地发现软件中的错误。软件测试贯穿整个软件生命期，调试主要在开发阶段。1、基本概念程序调试的步骤：第一步：错误定位；第二步：修改设计和代码，以排除错误；第三步：进行回归测试，防止引进新的错误。94程序调试的原则确定错误的性质和位置时应该注意的事项有：分析思考与错误征兆相关的信息；避开死胡同；只把调试工具当作辅助手段来用；避免用试探法，最多只能把它当作最后手段。修改错误时应遵循如下原则：在出现错误的地方，还可能有别的错误；不应只修改了错误的征兆或表现而没有修改错误本身；注意修正一个错误的同时有可能会引入新的错误；修改错误的过程将迫使人们暂时回到程序设计阶段；修改源代码程序，不要改变目标代码。2、软件调试方法主要方法有强行排错法、回溯法和原因排除法。其中强行排错法是传统的调试方法，回溯法适合于小规模程序的徘错，原因排除法是通过演绎和归纳以及二分法来实现的。95例年考题分析【2008年9月】一、选择题1、在软件开发中，需求分析阶段可以使用的工具是：A、N-S图 B、DFD图 C、PAD图 D、程序流程图二、填空题1、按照软件测试的一般步骤，集成测试应在_测试之后进行。：2、软件工程三要素包括方法、工具和过程，其中，_支持软件开发的各个环节的控制和管理。单元B过程96【2008年4月】一、选择题1、软件设计中模块划分应遵循的准则是：A、低内聚低耦合 B、高内聚低耦合 C、低内聚高耦合 D、高内聚高耦合 2、在软件开发中，需求分析阶段产生的主要文档是A、可行性分析报告 B、软件需求规格说明书 C、概要设计说明书 D、集成测试计划二、填空题1、测试用例包括输入值集和_值集。BB输出97【2007年9月】一、选择题1、软件是指：A、程序 B、程序和文档 C、算法加数据结构 D、程序、数据与相关文档的完整集合 2、软件调试的目的是A、发现错误 B、改正错误 C、改善软件的性能 D、验证软件的正确性BD98【2007年9月】二、填空题1、软件需求规格说明书尖具有完整性、无岐义性、正确性、可验证性、可修改性等特性。其中最重要的是_2、在两程基本测试方法中，_测试的原则之一是保证所测模块中每一个独立路径至少要执行一次。白