《计算机二级公共基础知识》课程教学资源（教材电子书，WORD版，含习题与答案）.doc

目录第1章数据结构与算法........................................................................................................ 1 1.1 算法................................................................................................................. 1 1.1.1算法的基本概念................................................................................................. 1 1.1.2 算法复杂度...................................................................................................... 4 1.2 数据结构的基本概念................................................................................................ 7 1.2.1什么是数据结构................................................................................................. 7 1.2.2数据结构的图形表示.........................................................................................12 1.2.3线性结构与非线性结构.....................................................................................13 1.3线性表及其顺序存储结构 ...........................................................................................14 1.3.1线性表的基本概念............................................................................................14 1.3.2线性表的顺序存储结构.....................................................................................15 1.3.3顺序表的插入运算............................................................................................16 1.3.4顺序表的删除运算............................................................................................17 1.4 栈和队列................................................................................................................19 1.4.1栈及其基本运算................................................................................................19 1.4.2队列及其基本运算............................................................................................20 1.5 线性链表................................................................................................................22 1.5.1线性链表的基本概念.........................................................................................22 1.5.2线性链表的基本运算.........................................................................................26 1.5.3循环链表及其基本运算.....................................................................................28 1.6 树与二叉树.............................................................................................................29 1.6.1树的基本概念...................................................................................................29 1.6.2二叉树及其基本性质.........................................................................................32 1.6.3二叉树的存储结构............................................................................................34 1.6.4二叉树的遍历...................................................................................................35 1.7 查找技术................................................................................................................36 1.7.1顺序查找..........................................................................................................37 1.7.2二分法查找.......................................................................................................37 1.8 排序技术................................................................................................................37 1.8.1交换类排序法...................................................................................................38 1.8.2插入类排序法...................................................................................................39 1.8.3选择类排序法...................................................................................................41 习题 1.......................................................................................................................43 第2章程序设计基础............................................................................................................45 2.1 程序设计方法与风格...............................................................................................45 2.2 结构化程序设针......................................................................................................46 2.2.1结构化程序设计的原则.....................................................................................46 2.2.2结构化程序设计的基本结构和特点....................................................................47

2.2.3结构化程序设计原则和方法的应用....................................................................48 2.3面向对象的程序设计 ..................................................................................................48 2.3.1关于面向对象方法............................................................................................48 2.3.2面向对象方法的基本概念..................................................................................51 习题 2.......................................................................................................................54 第3章软件工程基础............................................................................................................56 3.1 软件工程基本概念..................................................................................................56 3.1.1软件定义与软件特点.........................................................................................56 3.1.2软件危机与软件工程.........................................................................................57 3.1.3软件工程过程与软件生命周期...........................................................................58 3.1.4软件工程的目标与原则.....................................................................................59 3.1.5软件开发工具与软件开发环境...........................................................................60 3.2 结构化分析方法......................................................................................................61 3.2.1 需求分析与需求分析方法................................................................................61 3.2.2结构化分析方法................................................................................................62 3.2.3软件需求规格说明书.........................................................................................66 3.3 结构化设计方法......................................................................................................67 3.3.1软件设计的基本概念.........................................................................................67 3.3.2概要设计..........................................................................................................70 3.3.3详细设计..........................................................................................................74 3.4 软件测试................................................................................................................78 3.4.1软件测试的目的................................................................................................79 3.4.2软件测试的准则................................................................................................79 3.4.3软件测试技术与方法综述..................................................................................79 3.4.4软件测试的实施................................................................................................86 3.5程序的调试 ................................................................................................................89 3.5.1基本概念..........................................................................................................89 3.5.2软件调试方法...................................................................................................90 习题 3.......................................................................................................................92 第4章数据库设计基础.........................................................................................................93 4.1 数据厍系统的基本概念...........................................................................................93 4.1.1数据、数据库、数据库管理系统.......................................................................93 4.1.2数据库系统的发展............................................................................................96 4.1.3数据库系统的基本特点.....................................................................................98 4.1.4数据库系统的内部结构体系..............................................................................99 4.2 数据模型..............................................................................................................100 4.2.1数据模型的基本概念.......................................................................................100 4.2.2E-R模型..........................................................................................................101 4.2.3层次模型........................................................................................................105 4.2.4网状模型........................................................................................................105 4.2.5关系模型........................................................................................................106

第1章数据结构与算法第1章数据结构与算法 1.1算法 11.1算法的基本概念所谓算法是指解题方案的准确而完整的描述。对于一个问题,如果可以通过一个计算机程序,在有限的存储空间内运行有限长的时间而得到正确的结果,则称这个问题是算法可解的。但算法不等于程序,也不等于计算方法。当然, 程序也可以作为算法的一种描述,但程序通常还需考虑很多与方法和分析无关的细节问题,这是因为在编写程序时要受到计算机系统运行环境的限制。通常,程序的编制不可能优于算法的设计。 1算法的基本特征作为一个算法,一般应具有以下几个基本特征 (1)可行性( effectiveness) 针对实际问题设计的算法,人们总是希望能够得到满意的结果。但一个算法又总是在某个特定的计算工具上执行的,因此,算法在执行过程中往往要受到计算工具的限制,使执行结果产生偏差。例如,在进行数值计算时,如果某计算工具具有7位有效数字(如程序设计语言中的单精度运算),则在计算下列三个量 A=1012,B=1,C=-10 的和时,如果采用不同的运算顺序,就会得到不同的结果,即 A+B+C=1012+1+(-1012)=0 A+C+B=1012+(-1012)+1=1 而在数学上,A+B+C与A+C+B是完全等价的。因此,算法与计算公式是有差别的。在设计一个算法时,必须要考虑它的可行性,否则是不会得到满意结果的 2)确定性( definiteness 算法的确定性,是指算法中的每一个步骤都必须是有明确定义的,不允许有模棱两可的解释,也不允许有多义性。这一性质也反映了算法与数学公式的明显差别。在解决实际问题时, 可能会出现这样的情况:针对某种特殊问题,数学公式是正确的,但按此数学公式设计的计算过程可能会使计算机系统无所适从。这是因为根据数学公式设计的计算过程只考虑了正常使用的情况,而当出现异常情况时,此计算过程就不能适应了 (3)有穷性( finiteness 算法的有穷性,是指算法必须能在有限的时间内做完,即算法必须能在执行有限个步骤之后终止。数学中的无穷级数,在实际计算时只能取有限项,即计算无穷级数值的过程只能是有穷的。因此,一个数的无穷级数表示只是一个计算公式,而根据精度要求确定的计算过程才是有穷的算法。算法的有穷性还应包括合理的执行时间的含义。因为,如果一个算法需要执行千万年,显然失去了实用价值 (4)拥有足够的情报个算法是否有效,还取决于为算法所提供的情报是否足够。通常,算法中的各种运算总

第 1 章数据结构与算法 1 第 1 章数据结构与算法 1.1 算法 1.1.1 算法的基本概念所谓算法是指解题方案的准确而完整的描述。对于一个问题，如果可以通过一个计算机程序，在有限的存储空间内运行有限长的时间而得到正确的结果，则称这个问题是算法可解的。但算法不等于程序，也不等于计算方法。当然，程序也可以作为算法的一种描述，但程序通常还需考虑很多与方法和分析无关的细节问题，这是因为在编写程序时要受到计算机系统运行环境的限制。通常，程序的编制不可能优于算法的设计。 1.算法的基本特征作为一个算法，一般应具有以下几个基本特征。 (1)可行性(effectiveness) 针对实际问题设计的算法，人们总是希望能够得到满意的结果。但一个算法又总是在某个特定的计算工具上执行的，因此，算法在执行过程中往往要受到计算工具的限制，使执行结果产生偏差。例如，在进行数值计算时，如果某计算工具具有 7 位有效数字(如程序设计语言中的单精度运算)，则在计算下列三个量 A=1012，B=1，C=-1012 的和时，如果采用不同的运算顺序，就会得到不同的结果，即 A+B+C=1012+1+(-1012)=0 A+C+B=1012+(-1012)+1=1 而在数学上，A+B+C 与 A+C+B 是完全等价的。因此，算法与计算公式是有差别的。在设计一个算法时，必须要考虑它的可行性，否则是不会得到满意结果的。 (2)确定性(definiteness) 算法的确定性，是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。这一性质也反映了算法与数学公式的明显差别。在解决实际问题时，可能会出现这样的情况：针对某种特殊问题，数学公式是正确的，但按此数学公式设计的计算过程可能会使计算机系统无所适从。这是因为根据数学公式设计的计算过程只考虑了正常使用的情况，而当出现异常情况时，此计算过程就不能适应了。 (3)有穷性(finiteness) 算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。数学中的无穷级数，在实际计算时只能取有限项，即计算无穷级数值的过程只能是有穷的。因此，一个数的无穷级数表示只是一个计算公式，而根据精度要求确定的计算过程才是有穷的算法。算法的有穷性还应包括合理的执行时间的含义。因为，如果一个算法需要执行千万年，显然失去了实用价值。 (4)拥有足够的情报一个算法是否有效，还取决于为算法所提供的情报是否足够。通常，算法中的各种运算总

第1章数据结构与算法是要施加到各个运算对象上,而这些运算对象又可能具有某种初始状态,这是算法执行的起点或是依据。因此,一个算法执行的结果总是与输入的初始数据有关,不同的输入将会有不同的结果输出。当输入不够或输入错误时,算法本身也就无法执行或导致执行有错。一般来说,当算法拥有足够的情报时,此算法才是有效的,而当提供的情报不够时,算法可能无效。综上所述,所谓算法,是一组严谨地定义运算顺序的规则,并且每一个规则都是有效的且是明确的,此顺序将在有限的次数下终止 2算法的基本要素一个算法通常由两种基本要素组成:一是对数据对象的运算和操作,二是算法的控制结构 (1)算法中对数据的运算和操作每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。因此,计算机算法就是计算机能处理的操作所组成的指令序列通常,计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合,称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列。在一般的计算机系统中,基本的运算和操作有以下四类 ①算术运算:主要包括加、减、乘、除等运算 ②逻辑运算:主要包括“与”、“或”、“非”等运算 ③关系运算:主要包括“大于”、“小于”、“等于”、“不等于”等运算 ④数据传输:主要包括赋值、输入、输出等操作。前面提到,计算机程序也可以作为算法的…种描述,但由于在编制计算机程序时通常要考虑很多与方法和分析无关的细节问题(如语法规则,因此,在设计算法的一开始,通常并不直接用计算机程序来描述算法,而是用别的描述工具(如流程图,专门的算法描述语言,甚至用自然语言)来描述算法。但不管用哪种工具来描述算法,算法的设计一般都应从上述四种基本操作考虑,按解题要求从这些基本操作中选择合适的操作组成解题的操作序列。算法的主要特征着重于算法的动态执行,它区别于传统的着重于静态描述或按演绎方式求解问题的过程。传统的演绎数学是以公理系统为基础的,问题的求解过程是通过有限次推演来完成的,每次推演都将对问题作进一步的描述,如此不断推演,直到直接将解描述出来为止。而计算机算法则是使用些最基本的操作,通过对已知条件一步一步的加工和变换,从而实现解题目标。这两种方法的解题思路是不同的 (2)算法的控制结构一个算法的功能不仅取决于所选用的操作,而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构算法的控制结构给出了算法的基本框架,它不仅决定了算法中各操作的执行顺序,而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S结构化程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而 3算法设计基本方法计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。计算机算法不同于人工处理的方法本节介绍工程上常用的几种算法设计方法,在实际应用时,各种方法之间往往存在着一定的联系。 (1)列举法

第 1 章数据结构与算法 2 是要施加到各个运算对象上，而这些运算对象又可能具有某种初始状态，这是算法执行的起点或是依据。因此，一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。当输入不够或输入错误时，算法本身也就无法执行或导致执行有错。一般来说，当算法拥有足够的情报时，此算法才是有效的，而当提供的情报不够时，算法可能无效。综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。 2.算法的基本要素一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。 (1)算法中对数据的运算和操作每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。因此，计算机算法就是计算机能处理的操作所组成的指令序列。通常，计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列。在一般的计算机系统中，基本的运算和操作有以下四类： ①算术运算：主要包括加、减、乘、除等运算。 ②逻辑运算：主要包括“与”、“或”、“非”等运算。 ③关系运算：主要包括“大于”、“小于”、“等于”、“不等于”等运算。 ④数据传输：主要包括赋值、输入、输出等操作。前面提到，计算机程序也可以作为算法的…种描述，但由于在编制计算机程序时通常要考虑很多与方法和分析无关的细节问题(如语法规则)，因此，在设计算法的一开始，通常并不直接用计算机程序来描述算法，而是用别的描述工具(如流程图，专门的算法描述语言，甚至用自然语言)来描述算法。但不管用哪种工具来描述算法，算法的设计一般都应从上述四种基本操作考虑，按解题要求从这些基本操作中选择合适的操作组成解题的操作序列。算法的主要特征着重于算法的动态执行，它区别于传统的着重于静态描述或按演绎方式求解问题的过程。传统的演绎数学是以公理系统为基础的，问题的求解过程是通过有限次推演来完成的，每次推演都将对问题作进一步的描述，如此不断推演，直到直接将解描述出来为止。而计算机算法则是使用一些最基本的操作，通过对已知条件一步一步的加工和变换，从而实现解题目标。这两种方法的解题思路是不同的。 (2)算法的控制结构一个算法的功能不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S 结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。 3.算法设计基本方法计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。计算机算法不同于人工处理的方法。本节介绍工程上常用的几种算法设计方法，在实际应用时，各种方法之间往往存在着一定的联系。 (1)列举法