《计算机等级考试二.ppt》由会员分享，可在线阅读，更多相关《计算机等级考试二.ppt（138页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算机等级考试二级教程公共基础知识公共基础知识一、基本数据结构与算法。二、程序设计基础。三、软件工程基础。四、数据库设计基础。2第一部分 数据结构与算法5-7个题（10-14分）考试大纲:一.基本要求:1.掌握算法的基本概念2.掌握基本数据结构及其操作3.掌握基本排序和查找算法3二二.考试内容考试内容:1.算法的基本概念算法的基本概念;算法复杂度的概念和意义算法复杂度的概念和意义(时间复杂度和空间复时间复杂度和空间复杂度杂度)2.数据结构的定义数据结构的定义;数据的逻辑结构与存储结构数据的逻辑结构与存储结构;数据结构的图形表数据结构的图形表示示;线性结构与非线性结构的概念线性结构与非线性结构的
2、概念3.线性表的定义线性表的定义;线性表的顺序存储结构及其插入与删除运算线性表的顺序存储结构及其插入与删除运算4.栈和队列的定义栈和队列的定义;栈和队列的顺序存储结构及其基本运算栈和队列的顺序存储结构及其基本运算5.线性单链表、双向链表与循环链表的结构及其基本运算线性单链表、双向链表与循环链表的结构及其基本运算6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。序和后序遍历。7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）排序，
3、插入类排序）4考点一、算法（P1）一.算法的基本 概念 所谓算法是指解题方案的准确而完善的描述。1.算法的基本特征可行性：是否可行。确定性：指算法中的每一个步骤必须有明确定义，不允许有模棱两可的解释，也不允许有多义性。有穷性：指算法必须在有限的时间内做完，即算法必须能在执行有限个步骤后终止。拥有足够的情报：收集的输入信息等。52.算法的基本要素一个算法通常由两种要素组成：一是对数据对象的运算和操作，二是算法的控制结构。（1）算法中对数据的运算和操作（指令）（P2）算术运算：加、减、乘、除、求余逻辑运算：与、或、非关系运算：大于、小于、等于、不等于数据传输：赋值、输入、输出（2）算法的控制结构（
4、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.算法的时间复杂度:指执行算法所需要
5、的计算工作量.工作量可以用算法所执行的基本运算次数来度量,而算法所执行的基本运算次数是问题规模的函数 即算法的工作量=f(n)其中n是问题的规模.可以用平均性态和最坏情况复杂性两种方法.82.算法的空间复杂度:指执行这个算法所需要的内存空间.包括算法程序所占的空间、输入的初始数据所占的存储空以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及基本种数据结构所需要的附加存储空间（例如，在链式结构中，除了存储数据本身外，还需要存储链接信息）。9考点二、数据结构的基本概念（P7）数据结构学科主要研究如下三个方面的内容:数据集合中各数据元素之间所固有的逻辑关系,即数据的
6、逻辑结构.在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构.对各种数据结构进行的运算.数据结构学科的研究目的:提高数据处理的效率.主要包括:数据处理速度.尽量节省在数据处理过程中所占用的计算机存储空间.10一.数据结构的定义:指相互关联的数据元素的集合.（P10）1.数据处理:指对数据集合中的各元素以各种方式进行运算.(插入,删除,查找,更改等)2.数据元素:在数据处理领域中,每一个需要处理的对象都可以抽象为数据元素.3.数据结构:是指反映数据元素之间关系的数据元素集合的表示.一个数据结构应包括两方面的信息:一是表示数据元素的信息,二是表示各数据元素之间的前后件关系.11数
7、据的逻辑结构（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）:指数据的逻辑结构在计算机存储空间中的
8、存放形式.也称为物理结构.一般来说,一种数据的逻辑结构根据需要表示成多种存储结构,常用存储结构有顺序,链接,索引等.各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的,而且一般也不可能相同.（P13）13二.数据结构的图形表示 一个数据结构除了用二元关系表示外,还可以直观的用图形表示.图形表示方法:对于数据集合D中的每一个数据元素用中间标有元素值的方框表示,一般称之为数据结点,简称为结点;对于关系R中的每一个二元组,用一条有向线段从前件结点指向后件结点,以表示数据元素之间的前后件关系.春夏秋冬女儿儿子父亲14例:用图形表示数据结构B=(D,R),其中 D=di|1i6=d1,
9、d2,d3,d4,d5,d6 R=(d1,d2),(d1,d3),(d3,d4),(d5,d4),(d5,d6)这个数据结构的图形表示为:d1d2d3d5d4d6注意（P14页）在数据结构中，没有前件的结点称为根结点。没有后件的结点称为终端结点（也称为叶子结点。）15三.线性结构和非线性结构（概念）（P14）数据结构一般分为线性结构和非线性结构两大类.一个非空的线性结构满足如下条件:有且仅有一个根结点;每一个结点最多有一个前件,也最多有一个后件;在一个线性结构中插入或删除一个结点后还是线性结构.如果一个数据结构不是线性结构,则称之为非线性结构.线性结构有:栈,队列,双向链表;非线性结构:树,二
10、叉树.ACBABCABCD161.线性表的基本概念线性表定义:线性表是由n(n=0)个数据元素a1,a2,an组成的一个有限序列,表中的每一个数据元素,除了第一个外,有且只有一个前件,除了最后一个外,有且只有一个后件.即线性表或是一个空表,或是可以表示为:(a1,a2,an)其中ai(i=1,2,n)是属于数据对象的元素,通常也称为线性表中的一个结点.非空线性表的基本特征:有且只有一个根结点a1，它无前件；有且只有一个终端结点an，它无后件；除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表的长度：线性表中结点的个数n称为线性表的长度。当n=0时，称为空表。考点三、
11、线性表及其顺序存储结构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线性表的主要操作:插入、删除、查找、排序、分解、合并、复制、逆转
12、193.线性表的插入运算一个长度为n的线性表，要在第i（1in）个元素之前插入一个新元素时，首先要从最后一个（即第n个）元素开始向后移动一个位置，直到第i个元素之间的n-i+1个元素依次向后移动一个位置，移动结束后，第i个位置就被空出，然后将新元素插入到第i项。插入结束后，线性表的长度就增加了1，变为n+1.其时间复杂度，在平均情况下，需要移动一半的元素，最坏情况下要移动所有元素。204731243536561829473124353656182947312435365618872912345678910123456789101234567891087线性表顺序存储结构的适用场合：对于小线性表
13、或者其中元素不常变动的线性表来说是合适的，因为顺序存储的结构比较简单，对于元素需要变动的大线性表就不太合适了，因为插入和删除的效率比较低。214.线性表的删除运算要删除第i（1in）个元素时，首先要从第i+1个元素开始，直到最后一个（即n个）元素之间的n-1个元素依次向前移动一个位置。删除结束后，线性表的长度就减少了1。变为n-1。删除操作的时间复杂度：在平均情况下，需要移动表中一半的元素，最坏情况下要移动表中的所有元素。22考点四、栈和队列(重点)（P19）1、栈及其基本运算(1)栈的定义:栈是限定在一端进行插入和删除操作的线性表.它按照”后进先出”(或”先进后出”)的原则组织数据.(2)栈
14、的顺序存储:在程序设计语言中一般是用一维数据S(1:m)作为栈的顺序存储空间,其中m为栈的最大容量.(3)栈的基本运算入栈运算:首先将栈顶指针(top)加1,然后将新元素插入到栈顶指针指向的位置.当栈顶指针已经指向存储空间的最后一个位置时说明本栈空间已满,不可能再进行入栈操作.退栈操作:首先将栈顶元素赋给一个指定的变量,然后将栈顶指针(top)减1.当栈顶指针为0时,说明栈空,不可能再进行退栈操作.读栈顶元素:将栈顶元素赋给一个指定的变量,栈指针(top)不变.当栈顶指针为0时,说明栈空,读栈顶元素操作失败.23ABCDEF10987654321topbottomABCD10987654321
15、topbottom入栈入栈退栈退栈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，然后将排头指针指向的元素赋给指定
16、的变量。25ABCDEF87654321realfront具有6个元素的循环队列加入X和Y后的循环队列realABCDEF87654321frontXYBCDEF87654321frontXYreal退出一个元素后的循环队列栈和队列都是顺序存储的。26考点五、线性链表（P24）1、线性链表的基本概念：线性表的链式存储结构称为线性链表。线性链表的存储结构：线性链表的每个结点中数据域存放数据元素的值，指针域存放后件结点的存储地址。双向链表的存储结构：双向链表的存储结构比线性链表的存储结构多出一个指针域，它用来存放前件结点的存放地址。带链的栈，带链的队列HEADA0BH0HEAD0272、线性链表的
17、基本运算（P27）：插入、删除、合并、分解、逆转、复制、排序、查找。线性链表的插入：先从栈中为新元素分配一个新的结点q，并赋值。然后利用线性链表的查找算法找到待插入位置的前一个结点的指针p。先将q指向p的后件，然后将q挂在p结点的后面。xpxpq28线性链表的删除：先找到待删除元素的前一个结点p，用另一个指针q暂时保存p的后续结点（即待删除结点），然后把q结点的后续链直接挂接在p的后面。最后归还q结点所分配的栈空间。xpq293、循环链表（P30）：循环链表的几个特点：在循环链表中增加一个表头结点，使得循环链表对空表和非空表的操作实现了统一。循环链表中最后一个结点的指针域不是空，而是指向表头结
18、点。判断循环链表是否为空的办法不是看表头指针为空，而是看表头结点的后续结点是否还是表头结点。在循环链表中，从任何一个结点出发都可以访问到表中其它所有的结点。xYHEADz30考点六、树与二叉树(重点)（P31）1、树的基本概念树是一种非线性结构，在树的这种数据结构中，所有数据元素之间的关系具有明显的层次特性。父结点：在树结构中，每一个结点只有一个前件结点，称为父结点。根结点：没有前件的结点只有一个，称为树的根结点。子结点：每一个结点可以有多个后件，它们都称为该结点的子结点。叶子结点：没有后件的结点称为叶子结点。IKGFHEDCBAR31结点的度：一个结点所拥的后件个数称为该结点的度。树的度：在
19、树中，所有结点中的最大的度称为树的度。树的深度：树的最大层次称为树的深度，树的深度也可以称为树的高度，根结点在第1层。子树：在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。叶子结点没有子树。IKGFHEDCBAR32IKGFHECBR2、二叉树及其基本性质（P34）二叉树的两个特点：非空二叉树只有一个根结点；每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。二叉树的基本性质：在二叉树的第k层上，最多有 2k-1(k=1)个结点。深度为m的二叉树最多有2m-1个结点。在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。具有n个结点的二叉树，其深度至少为
20、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/
21、2)。34若2k=n，则编号为k的结点的左子结点编号为2k，否则该结点无左子结点（显然也没有右子结点）若2k+1=n，则编号为k的结点的右子结点编号为2k+1，否则该结点无右子结点。FGEHDCBAIJK355、二叉树的遍历（P38）前序遍历：先访问根结点，后前序遍历左子树，再前序遍历右子树。中序遍历：先中序遍历左子树，后访问根结点，再中序遍历右子树。后序遍历：先后序遍历左子树，后后序遍历右子树，再访问根结点。对下图进行前序遍历的结果是：ABDECF；中序遍历的结果是：DBEACF；后序遍历的结果是：DEBFCA。FEDCBA36考点七、查找技术（P39）1、顺序查找：适用于无序表或采用链式存
22、储的表（不管有序还是无序）。查找方法：从表头到表尾逐个查找，若相同则结束查找，否则一直继续比较下一个表中元素直到整个表都遍历完。对于长度为n的线性表，平均要进行n/2次比较，在最坏情况下要进行n次比较。2、二分查找：适用于顺序存储的有序表。每次把特查找值与表中间元素比较，以减半的方式缩小搜索范围。对于长度为n的线性表，在最坏情况下要进行 2n次比较。例题分析：请写出用二分查找法在有序顺序表（1、2、3、4、6、8、9、11）中查找3的比较序列：4、2、312346891137考点八、排序技术(比较次数)（P40）交换类排序：冒泡排序法，快速排序法。插入类排序：简单插入排序法，希尔排序法。选择类
23、排序：简单选择排序法，堆排序法。1、冒泡排序法：通过相邻元素的比较、交换，逐步将线性表变成有序。首先，从表头开始往后扫描线性表，在扫描过程中依次比较相邻两个元素的大小，若前者大于后者则交换它们的位置。这样就将线性表中的最大者换到了表的最后。然后，从后往前扫描剩下的线性表，同样，在扫描过程中依次比较相邻的两个元素的大小，若后者小于前者则交换位置，这样就将线性表中的最小者换到了表的最前面。对剩下的线性表重复上述过程，直到剩下的线性表变空为止。以时已变为有序。假设线性表的长度为n，则在最坏情况下，需经过n/2遍的从前往后扫描和n/2遍的从后往前扫描，需要比较的次数为n(n-1)/2。38例题分析：请
24、写出用冒泡排序法对序列（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分别指向表的起始与最后的位置
25、，反复操作以下两步：将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-
26、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、循环队列中元素的
27、个数是由队头指针和队尾指针共同决定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)
28、堆排序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、由于计算机存储空间是向量式的存储结构，
29、因此，数据的存储结构一定是线性结构。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、算法的时间复杂度是指执行算法所
30、需要的计算工作量。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的结点多一个。
31、方法二：特例法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.数据结构分为线性结构和非线性结构，带链的队列属于（）
32、。DAA栈线性结构一个非空的线性结构满足如下条件:有且仅有一个根结点;每一个结点最多有一个前件,也最多有一个后件;在一个线性结构中插入或删除一个结点后还是线性结构.如果一个数据结构不是线性结构,则称之为非线性结构.线性结构有:栈,队列,双向链表;非线性结构:树,二叉树.51【2006年4月】一.选择题1.按照“后进先出”原则组织数据的数据结构是：A、队列 B、栈 C、双向链表 D、二叉树2.下列叙述中正确的是：A、线性链表是线性表的链式存储结构 B、栈与队列是非线性结构 C、双向链表是非线性结构 D、只有根结点的二叉树是线性结构3.对右图二叉树进行后序遍历的结果是：A、ABCDEF B、DBE
33、AFC 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.下列关于栈的描述中正确的是：
34、A、在栈中只能插入元素而不能删除元素 B、在栈中只能删除元素而不能插入元素 C、栈是特殊的线性表，只能在一端插入或删除元素 D、栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素3.下列叙述正确的是：A、一个逻辑数据结构只能有一种存储结构 B、数据的逻辑结构属于线性结构，存储结构属于非线性结构 C、一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处 理的效率 D、一个逻辑数据结构可以有多种存储结构，且各种存储结构影响处理的效 率 ACD53【2005年9月】二.填空题1.算法复杂度主要包括时间复杂度和（）复杂度。2.一棵二叉树第六层（根结点为每一层）的结点数最多为（）个。3.
35、数据结构分为逻辑结构和存储结构，循环队列属于（）结构。空间复杂度满二叉树最多第k层上的结点数为2k-1个32存储常用的存储结构有顺序、链式和索引存储结构。逻辑结构对应的存储结构线性表顺序表（线性表的顺序存储结构）线性链表（链式存储结构）循环链表（链式存储结构）栈栈的顺序存储结构带链的栈（链式存储结构）队列循环队列（顺序存储结构）带链的队列（链式存储结构）树树的链式存储结构二叉树二叉树的链式存储结构54【2005年4月】一.选择题1.数据的存储结构是指：A、存储在外存中的数据 B、数据所占的存储空间量 C、数据在计算机中的顺序存储方式 D、数据的逻辑结构在计算机中的表示2.下列关于栈的描述中错误
36、的是：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、存储空间必须连续，且前
37、件元素一定存储在后件元素的前面 D、存储空间必须连续，且各元素的存储顺序是任意的二、填空题1.问题处理方案的正确而完整的描述称为（）。CA算法56第二部分 程序设计基础1-2题（2-4分）考试大纲:一、基本要求:1.掌握逐步求精的结构化程序设计方法。二、考试内容1.程序设计方法与风格2.结构化程序设计3.面向对象的程序设计方法、对象、方法、属性及继承与多态性。57考点一、程序设计方法与风格（P48）1、程序设计方法和技术的发展主要经过了结构化程序设计和面向对象程序设计两个阶段。2、程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思想。程序设计风格会深刻影响软件的质量和可维护性。著名的“清晰
38、第一，效率第二”的论点已经成为当今主要的程序设计风格。3、要形成良好的程序设计风格，主要应注意和考虑下述一些因素：58（1）源程序的文档结构组织对源程序的文档结构的组织要注意以下三点：符号的命名：符号的命名应具有一定的实际含义。程序注释：一般分为序言性注释和功能性注释。视觉组织：在程序中利用空格、空行、缩进等技巧使程序层次清晰。（2）数据说明的方法对数据的说明要注意三点：第一，数据说明的次序规范化；第二，说明语句中变量安排有序化；第三，使用注释来说明复杂数据结构。59（3）语句的结构对语句的结构安排要遵循以下一些原则：在一行内只写一条语句；程序编写应优先考虑清晰性。除非对效率有特殊要求，程序编
39、写要做到清晰第一，效率第二。首先要保证程序正确，然后才要求是提高速度；避免使用临时变量而使程序的可读性下降；避免不必要的转移；尽可能使用库函数；避免复杂的条件语句；尽量少使用“否定”条件的条件语句；数据结构要有利于程序的简化；要模块化，使模块的功能尽可能单一化；利用信息隐蔽，确保每一个模块的独立性；从数据出发去构造程序；不要修补不好的程序，要重新编写。60（4）输入和输出对输入和输出用户界面要注意以下几点：对所有的输入数据都要检验数据的合法性；检查输入项的各种重要组合的合理性；输入格式要简单，以使得输入的步骤和操作尽可能简单；输入数据时，应允许使用自由格式；应允许缺省值；输入一批数据时，最好使
40、用输入结束标志；在以交互式输入/输出方式进行输入时，要在屏幕上使用提示符明确提示输入的请求，同时在数据输入过程中和输入结束时，应屏幕上给出状态信息；当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性；给所有的输出加注释，并设计输出报表格式。61考点二、结构化程序设计（P50）（1）结构化程序设计的原则在结构化程序中要遵循以下四个基本原则：自顶向下：先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标逐步求精：对复杂问题，先设计一些子目标作过渡，然后逐步细化。模块化：把程序要解决的总目标分解为一个一个的模块。限制使用GOTO语句：程序的质量与GOTO语句的数据成反比。62（
41、2）结构化程序的基本结构与特点结构化程序设计中常采用顺序、选择和循环三种基本结构。结构化程序设计的优点第一：程序易于理解、使用和维护；第二：提高了编程的效率，降低了软件开发成本。结构化程序设计原则和方法的应用应该做到以下几个方面：使用程序设计语言中的顺序、选择、循环等有限的控制结构表示控制逻辑；选用的控制结构只准许有一个入口和一个出口；程序语句组成容易识别的块，每块只有一个入口和一个出口；复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现；语言所没有的控制结构，应该采用前后一致的方法来模拟；严格控制GOTO语句的使用。63考点三、面向对象程序设计（P52）（1）面向对象方法的本质（2）面向对象
42、方法的优点（3）面向对象方法的基本概念（P54）对象：指描述该对象属性的数据以及对这些数据施加的所有操作封装在一起构成的统一体。对象是对问题域中某个实体的抽象。对象的属性和方法：属性是对象所包含的信息，它在设计对象时确定，一般只能通过执行对象操作来改变。方法描述了对象执行的功能，若通过消息传递，还可以为其他对象使用。对象的基本特点：标志唯一性：对象可由其内在本质来区分，而不是通过描述来区分。分类性：可以将具有相同属性和操作的对象抽象成类。多态性：同一操作可以是不同对象的行为。封装性：从外面看不到对象的内部，只能看到对象的外部特性。模块独立性好：一个对象就相当于一个模块。64类和实例：类是具有共
43、同属性、共同方法的对象的集合，类是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例。消息：指对象间的相互协助机制，是一个对象与另一个对象之间传递的消息。消息的组成：消息是由接收消息的对象名称、消息标识符、零个或多个参数组成。继承：指使用已有的类定义作为基础建立新类的定义技术。继承分为单继承和多继承。单继承中一个类只允许有一个父类，多继承中一个类允许有多个父类。多态性：是指同样的消息被不同的对象接受时可导致完全不同的动作的现象。65例年考题分析【2008年9月】一、选择题2.在面向对象的方法中，不属于“对象”基本特点的是：A、一致性 B、分类性 C、多态性 D
44、、标识唯一性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、以上三种说法都不对ACA6
45、8【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分）一、基本要求
46、掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。二、考试内容1、软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。2、结构化分析方法，数据流图，数据字典，软件需求规格说明书。3、结构化设计方法，总体设计与详细设计。4、软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。5、程序的调试，静态调试与动态调试。72(一)软件工程基本概念（P60）1、软件定义与软件特点软件的定义：软件是与计算机操作相关的计算机程序、规程、规则，以及可能有的文件、文档及数据。软件的三个要素：程序、数据和文档。软件的特点：软件作为一种特殊的信息产品，具
47、有以下特点：软件是一种逻辑实体，具有抽象性；软件没有明显的制作过程；软件在运行、使用期间不存在磨损、老化问题；软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导制了软件的移植性；软件复杂性高，成本昂贵；软件开发涉及诸多的社会因素。73软件分类:软件按功能可分为应用软件、系统软件和支撑软件(或工具软件)三大类。支撑软件是介于系统软件和应用软件之间，协调用户开发软件的工具性软件。2、软件危机与软件工程（P61）软件危机的含义：软件危机泛指在计算机软件的开发和维护中所遇到的一系列严重问题。软件危机主要表现为：软件需求的增长得不到满足；软件开发的成本和进度无法控制；软件质量难以保证；软件
48、不可维护或维护程度非常低；软件的成本不断提高；软件开发生产率的提高跟不上硬件的发展和应用需要的增长。软件危机产生的原因：宏观方面是由于软件日益深入社会生活的各个层面，对软件需求的增长速度大大超过了技术进步所能带来的软件生产率的提高。而就每一项具体的工程任务来看，软件危机许多困难来源于软件工程所面临的任务和其它工程之间的差异以及软件和其他工业产品的不同。74软件工程的定义（P62）软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。软件工程的三个要素：方法、工具和过程。方法是完成软件工程项目的技术手段；工具支持软件的开发、管理、文档生成；过程支持软件开发的各个环
49、节的控制、管理。软件工程的核心思想是软件当作一个工程产品来处理。75（3）软件工程过程与软件生命周期（P63）软件工程过程定义：软件工程过程是把输入转化为输出的一组相关的资源和活动。内涵：软件工程过程是指为获得软件产品，在软件工具支持下由软件工程师完成的一系列软件过程活动。从软件开发的观点来看，它就是使用适当的资源，为开发软件进行的一组开发活动，在过程结束时将输入（用户要求）转化为输出（软件产品）。软件工程过程包含的4个基本活动：软件规格说明（P）、软件开发（D）、软件确认（C）和软件演进（A）。76软件生命周期（P63）定义：软件生命周期就是软件产品从提出、实现、使用维护到停止使用退役的全过
50、程。三个阶段：软件生命周期包括软件定义、软件开发及软件维护三个阶段（每个阶段的任务）。软件定义阶段的任务包括可行性研究与计划制定、需求分析；软件开发阶段的任务包括概要设计、详细设计、软件实现、软件测试；软件维护的任务包括软件的运行、维护和退役。77可行性研究初步项目计划需求分析概要设计详细设计实现测试使用维护退役定义阶段开发阶段维护阶段软件生命周期784、软件工程的目标与原则（P64）软件工程的目标软件工程的目标是，以给定成本、进度的前提下，开发出具有时效性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。软件工程的理论和技术性研究的内容：软件开发技