2010年计算机二级C语言编程公共基础知识.pdf

特别说明特别说明 此资料来自百度文库（http:/ 此文档原地址来自 感谢您的支持 抱米花 http:/ h t t p:/w e n k u.b a i d u.c o m/v i e w/97a 5a 9b b f d 0a 79563c 1e 7263.h t m l第一章据构与算法经部分考生的查以及近年真的总分析，笔部分经常考查的是算法复度、据构的概念、二叉的遍、二分法查找，者此部分行重点学。重点学知点：1算法的概念、算法间复度及空间复度的概念2据构的定义、据构及物理构的定义3的定义及其运算、性表的存方式4与二叉的概念、二叉的基本性、完全二叉的概念、二叉的遍5二分查找法6冒泡排序法1.1算法考点1算法的基本概念考接：考点1在笔考中考核的几率30%，主要是以填空的形式出，分值2分，此考点容，者了解算法中据的基本运算。算机解的程实际上是在实施某种算法，种算法算机算法。1算法的基本特征：可行性、确定性、有性、拥有足够的情。2算法的基本要素：（1）算法中据的运算和操作一个算法由两种基本要素成：一是据象的运算和操作；二是算法的控制构。在一般的算机系统中，基本的运算和操作有以下4类：算运算、运算、系运算和据输。（2）算法的控制构：算法中各操作之间的行序算法的控制构。描述算法的工具通常有统流程、N-S构化流程、算法描述言等。一个算法一般都可以用序、循3种基本控制构合而成。考点2算法复度考接：考点2在笔考中，是一个经常考查的容，在笔考中出的几率70%，主要是以的形式出，分值2分，此考点重点容，者算法间复度及空间复度的概念。1.算法的间复度算法的间复度是指行算法所需要的算工作量。同一个算法用不同的言实，或者用不同的程序行，或者在不同的算机上运行，效率均不同。表明使用的间位衡量算法的效率是不合适的。撇些与算机硬件、件有的因素，可以一个特定算法运行工作量的大小，只依于的模（通常用整n表示），它是模的函。即算法的工作量=f（n）2.算法的空间复度算法的空间复度是指行个算法所需要的存空间。一个算法所占用的存空间包括算法程序所占的空间、输入的初始据所占的存空间以及算法行程中所需要的外空间。其中外空间包括算法程序行程中的工作元以及某种据构所需要的附加存空间。如果外空间量相于模是常，算法是原地工作的。在多实际中，了减少算法所占的存空间，通常采用存技，以便量减少不必要的外空间。疑解答：算法的工作量用什么算？算法的工作量用算法所行的基本运算次算，而算法所行的基本运算次是模的函，即算法的工作量=f（n），其中n是的模。1.2据构的基本概念考点3据构的定义考接：考点3在笔考中，是一个经常考查的容，在笔考中出的几率70%，主要是以的形式出，分值2分，此考点容，者据的构和存构的概念。据构作算机的一门学科，主要研究和以下三个方面：（1）据集合中个据元素之间所固有的系，即据的构；（2）在据元素行处理，各据元素在算机中的存系，即据的存构；（3）各种据构行的运算。据：是客事物的符号表示，在算机科学中是指所有能输入到算机中并被算机程序处理的符号的总。据元素：是据的基本位，在算机程序中通常作一个整体行考和处理。据象：是性相同的据元素的集合，是据的一个子集。据的构是据元素之间的系的描述，它可以用一个据元素的集合和定义在此集合中的若干系表示。据的构有两个要素：一是据元素的集合，通常D；二是D上的系，它反映了据元素之间的前后件系，通常R。一个据构可以表示成B=（D，R）其中B表示据构。了反映D中各据元素之间的前后件系，一般用二元表示。据的构在算机存空间中的存放形式据的存构（也据的物理构）。由于据元素在算机存空间中的位置系可能与系不同，因此，了表示存放在算机存空间中的各据元素之间的系（即前后件系），在据的存构中，不要存放各据元素的信息，需要存放各据元素之间的前后件系的信息。一种据的构根据需要可以表示成多种存构，常用的存构有序、接、索引等存构。而采用不同的存构，其据处理的效率是不同的。因此，在行据处理，合适的存构是很重要的。考点4性构与非性构考接：考点4在笔考中，然不是考经常考查的容，但者是此考点有所了解，在笔考中出的几率30%，主要是以填空出的形式出，分值2分，此考点容。根据据构中各据元素之间前后件系的复程度，一般据构分两大类型：性构与非性构。如果一个非空的据构足下列两个条件：（1）有且只有一个根点；（2）每一个点最多有一个前件，也最多有一个后件。据构性构。性构又性表。在一个性构中插入或删除任何一个点后是性构。如果一个据构不是性构，之非性构。疑解答：空的据构是性构是非性构？一个空的据构究竟是属于性构是属于非性构，要根据具体情况确定。如果据构的算法是按性构的处理的，属于性构；否属于非性构。1.3及性表考点5及其基本运算考接：考点5在笔考中，是一个必考的容，在笔考中出的几率100%，主要是以的形式出，分值2分，此考点重点掌握容，者掌握的运算。1的基本概念是限定只在一端行插入与删除的性表，通常插入、删除的一端，另一端底。表中有元素空。元素总是后被插入的元素，从而也是最先被删除的元素；底元素总是最先被插入的元素，从而也是最后才能被删除的元素。是按照先后出或后先出的原织据的。2的序存及其运算用一S（1m）作的序存空间，其中m最大容量。在的序存空间S（1m）中，S（b o t t o m）底元素，S（t o p）元素。t o p=0表示空；t o p=m表示。的基本运算有三种：入、退与元素。（1）入运算：入运算是指在位置插入一个新元素。首先指加一（即t o p加1），然后新元素插入到指指向的位置。指已经指向存空间的最后一个位置，明空间已，不可能再行入操作。种情况上溢。（2）退运算：退是指取出元素并一个指定的变量。首先元素（指指向的元素）一个指定的变量，然后指减一（即t o p减1）。指0，明空，不可行退操作。种情况的下溢。（3）元素：元素是指元素一个指定的变量。个运算不删除元素，只是它一个变量，因此指不会改变。指0，明空，不到元素。小技巧：是按照先后出或后先出的原织据，但是出方式有多种，在考中经常考查各种不同的出方式。考点6性表的基本概念考接：考点6在笔考中出的几率30%，主要是以的形式出，分值2分，此考点容。重点点的成。在式存方式中，要求每个点由两部分成：一部分用于存放据元素值，据域，另一部分用于存放指，指域。其中指用于指向点的前一个或后一个点（即前件或后件）。式存方式既可用于表示性构，也可用于表示非性构。（1）性表性表的式存构性表。在某些用中，性表中的每个点设置两个指，一个左指，用以指向其前件点；另一个右指，用以指向其后件点。样的表双向表。（2）的也是性表，也可以采用式存构。的可以用收集算机存空间中所有空的存点，种的可利用。疑解答：在式构中，存空间位置系与系是什么？在式存构中，存据构的存空间可以不，各据点的存序与据元素之间的系可以不一致，而据元素之间的系是由指域确定的。1.4与二叉考点7与二叉及其基本性考接：考点7在笔考中，是一个必考的容，在笔考中出的几率100%，主要是以的形式出，有也有出在填空中，分值2分，此考点重点掌握容。重点及二叉的性。警示：二叉也是完全二叉，而完全二叉一般不是二叉。注意二者的。1、的基本概念(t r e e）是一种的非性构。在构中，每一个点只有一个前件，父点，有前件的点只有一个，的根点。每一个点可以有多个后件，它点的子点。有后件的点叶子点。在构中，一个点所拥有的后件个点的度。叶子点的度0。在中，所有点中的最大的度的度。2、二叉及其基本性（1）二叉的定义二叉是一种很有用的非性构，具有以下两个特点：非空二叉只有一个根点；每一个点最多有两棵子，且分点的左子和右子。由以上特点可以看出，在二叉中，每一个点的度最大2，即所有子（左子或右子）也均二叉，而构中的每一个点的度可以是任意的。另外，二叉中的每个点的子被明地分左子和右子。在二叉中，一个点可以只有左子而有右子，也可以只有右子而有左子。一个点既有左子也有右子，点即叶子点。（2）二叉的基本性二叉具有以下几个性：性1：在二叉的第k上，最多有2k-1（k1）个点；性2：深度m的二叉最多有2m-1个点；性3：在任意一棵二叉中，度0的点（即叶子点）总是比度2的点多一个。性4：具有n个点的二叉，其深度至少l o g 2n+1，其中l o g 2n表示取l o g 2n的整部分。小技巧：在二叉的遍中，无是前序遍，中序遍是后序遍，二叉的叶子点的先后序都是不变的。3、二叉与完全二叉二叉是指样的一种二叉：除最后一外，每一上的所有点都有两个子点。在二叉中，每一上的点都达到最大值，即在二叉的第k上有2k-1个点，且深度m的二叉有2m1个点。完全二叉是指样的二叉：除最后一外，每一上的点均达到最大值；在最后一上只缺少右边的若干点。于完全二叉，叶子点只可能在次最大的两上出：于任何一个点，若其右分支下的子点的最大次p，其左分支下的子点的最大次或p，或p+1。完全二叉具有以下两个性：性5:具有n个点的完全二叉的深度l o g 2n+1。性6:设完全二叉共有n个点。如果从根点始，按次（每一从左到右）用自然1，2，n点行号，于号k（k=1，2，n）的点有以下：若k=1，点根点，它有父点；若k 1，点的父点号INT（k/2）。若2kn，号k的点的左子点号2k；否点无左子点（然也有右子点）。若2k+1n，号k的点的右子点号2k+1；否点无右子点。考点8二叉的遍考接：考点8在笔考中考核几率30%，分值2分，者熟掌握各种遍的具体算法，能由两种遍的果推另一种遍的果。在遍二叉的程中，一般先遍左子，再遍右子。在先左后右的原下，根据根点的次序，二叉的遍分三类：前序遍、中序遍和后序遍。（1）前序遍：先根点、然后遍左子，最后遍右子；并且，在遍左、右子，仍然先根点，然后遍左子，最后遍右子。（2）中序遍：先遍左子、然后根点，最后遍右子；并且，在遍左、右子，仍然先遍左子，然后根点，最后遍右子。（3）后序遍：先遍左子、然后遍右子，最后根点；并且，在遍左、右子，仍然先遍左子，然后遍右子，最后根点。疑解答：与二叉的不同之处是什么？在二叉中，每一个点的度最大2，即所有子（左子或右子）也均二叉，而构中的每一个点的度可以是任意的。1.5查找技考点9序查找考接：考点9在笔考中考核几率在30%，一般出中，分值2分，者具体掌握序查找的算法。查找是指在一个定的据构中查找某个指定的元素。从性表的第一个元素始，依次性表中的元素与被查找的元素相比，若相等表示查找成功；若性表中所有的元素都与被查找元素行了比但都不相等，表示查找失。在下列两种情况下也只能采用序查找：（1）如果性表无序表，不管是序存构是式存构，只能用序查找。（2）即使是有序性表，如果采用式存构，也只能用序查找。考点10二分法查找考接：考点10在笔考中考核几率30%，一般出填空中，分值2分，考核比多查找的比次，者具体掌握二分查找法的算法。二分法只适用于序存的，按非递减排列的有序表，其方法如下：设有序性表的长度n，被查找的元素i，（1）i与性表的中间行比；（2）若i与中间的值相等，查找成功；（3）若i小于中间，在性表的前半部分以相同的方法查找；（4）若i大于中间，在性表的后半部分以相同的方法查找。疑解答：二分查找法适用于哪种情况？二分查找法只适用于序存的有序表。在此所的有序表是指性表中的元素按值非递减排列（即从小到大，但允相邻元素值相等）。个程一直行到查找成功或子表长度0止。于长度n的有序性表，在最坏情况下，二分查找只需要比l o g 2n次。1.6排序技考点11交类排序法考接:考点11属于比的容，一般以的形式考查，考核几率30%，分值2分，者熟掌握几种排序算法的基本程。冒泡排序法和快速排序法都属于交类排序法。（1）冒泡排序法首先，从表头始往后描性表，逐次比相邻两个元素的大小，若前面的元素大于后面的元素，它互，不地两个相邻元素中的大者往后移动，最后最大者到了性表的最后。然后，从后到前描剩下的性表，逐次比相邻两个元素的大小，若后面的元素小于前面的元素，它互，不地两个相邻元素中的小者往前移动，最后最小者到了性表的最前面。剩下的性表重复上述程，直到剩下的性表变空止，此已经排好序。在最坏的情况下，冒泡排序需要比次n（n1）/2。（2）快速排序法它的基本思想是：任取待排序序列中的某个元素作基准（一般取第一个元素），通一趟排序，待排元素分左右两个子序列，左子序列元素的排序均小于或等于基准元素的排序，右子序列的排序大于基准元素的排序，然后分两个子序列行排序，直至整个序列有序。疑解答：冒泡排序和快速排序的平均行间分是多少？冒泡排序法的平均行间是O（n 2），而快速排序法的平均行间是O（n l o g 2n）。1.7例解一、【例1】算法的间复度取决于_。（考点2）A）的模B）待处理的据的初C）的度D）A）和B）解析：算法的间复度不与的模有，在同一个模下，而且与输入据有。即与输入据所有的可能取值范、输入各种据或据集的概率有。答案：D）【例2】在据构中，从上可以把据构分成_。（考点3）A）部构和外部构B）性构和非性构C）凑构和非凑构D）动构和构解析：构反映据元素之间的系，性构表示据元素之间一一的系，非性构表示据元素之间一多或者多一的系，所以答案B）。答案：B）【例3】以下_不是的基本运算。（考点5）A）判是否素空B）置空C）删除元素D）删除底元素解析：的基本运算有：入，出（删除元素），初始化、置空、判是否空或、提取元素等，的操作都是在行的。答案：D）【例4】表不具备的特点是_。（考点6）A）可随机任意一个点B）插入和删除不需要移动任何元素C）不必事先估存空间D）所需空间与其长度成正比解析：序表可以随机任意一个点，而表必从第一个据点出发，逐一查找每个点。所以答案A）。答案：A）【例5】已知某二叉的后序遍序列是DACBE，中序遍序列是DEBAC，它的前序遍序列是_。（考点8）A）ACBED B）DEABC C）DECAB D）EDBAC解析：后序遍的序是左子右子根点；中序遍序是左子根点右子；前序遍序是根点左子右子。根据各种遍算法，不得出前序遍序列是EDBAC。所以答案D）。答案：D）【例6】设有一个已按各元素的值排好序的性表（长度大于2），定的值k，分用序查找法和二分查找法查找一个与k相等的元素，比的次分是s和b，在查找不成功的情况下，s和b的系是_。（考点9）A）s=b B）s b C）s l o g 2n+1。答案：B）【例7】在快速排序程中，每次划分，被划分的表（或子表）分成左、右两个子表，考两个子表，下列一定正确的是_。（考点11）A）左、右两个子表都已各自排好序B）左边子表中的元素都不大于右边子表中的元素C）左边子表的长度小于右边子表的长度D）左、右两个子表中元素的平均值相等解析：快速排序基本思想是：任取待排序表中的某个元素作基准（一般取第一个元素），通一趟排序，待排元素分左右两个子表，左子表元素的排序均小于或等于基准元素的排序，右子表的排序大于基准元素的排序，然后分两个子表行排序，直至整个表有序。答案：B）二、填空【例1】处理方案的正确而完整的描述_。（考点1）解析：算机解的程实际上是在实施某种算法，种算法算机算法。答案：算法【例2】一个空的据构是按性构处理的，属于_。（考点4）解析：一个空的据构是性构或是非性构，要根据具体情况而定。如果据构的运算是按性构处理的，属于性构，否属于非性构。答案：性构【例3】设T的度4，其中度1、2、3和4的点的个分4、2、1、1，T中叶子点的个_。（考点7）解析：根据的性：的点等于所有点的度与的点个乘之和加1。因此的点14223141116。叶子点目等于点总减去度不0的点之和，即16（4211）8。答案：8【例4】二分法查找的存构限于_且是有序的。（考点10）解析：二分查找，也折半查找，它是一种高效率的查找方法。但二分查找有条件限制：要求表必用序存构，且表中元素必按字有序(升序或降序均可）。答案：序存构*公共基知总第一章据构与算法1.1算法算法：是指解方案的准确而完整的描述。算法不等于程序，也不等算机方法，程序的制不可能优于算法的设。算法的基本特征：是一地定义运算序的，每一个都是有效的，是明确的，此序在有限的次下止。特征包括：（1）可行性；（2）确定性，算法中每一步都必有明确定义，不充有模棱两可的解，不允有多义性；（3）有性，算法必能在有限的间做完，即能在行有限个步后止，包括合理的行间的含义；（4）拥有足够的情。算法的基本要素：一是据象的运算和操作；二是算法的控制构。指令系统：一个算机系统能行的所有指令的集合。基本运算和操作包括：算运算、运算、系运算、据输。算法的控制构：序构、构、循构。算法基本设方法：列法、法、递推、递、减斗递推技、回溯法。算法复度：算法间复度和算法空间复度。算法间复度是指行算法所需要的算工作量。算法空间复度是指行个算法所需要的存空间。1.2据构的基本基本概念据构研究的三个方面：（1）据集合中各据元素之间所固有的系，即据的构；（2）在据行处理，各据元素在算机中的存系，即据的存构；（3）各种据构行的运算。据构是指相互有联的据元素的集合。据的构包含：（1）表示据元素的信息；（2）表示各据元素之间的前后件系。据的存构有序、接、索引等。性构条件：（1）有且只有一个根点；（2）每一个点最多有一个前件，也最多有一个后件。非性构：不足性构条件的据构。13性表及其序存构性表由一据元素构成，据元素的位置只取决于自己的序号，元素之间的相位置是性的。在复性表中，由若干据元素成的据元素，而由多个构成的性表又文件。非空性表的构特征：（1）且只有一个根点a 1，它无前件；（2）有且只有一个端点a n，它无后件；（3）除根点与端点外，其他所有点有且只有一个前件，也有且只有一个后件。点个n性表的长度，n=0，空表。性表的序存构具有以下两个基本特点：（1）性表中所有元素的所占的存空间是的；（2）性表中各据元素在存空间中是按序依次存放的。a i的存地址：ADR(a i)=ADR(a 1)+(i-1)k,，ADR(a 1)第一个元素的地址，k代表每个元素占的字。序表的运算：插入、删除。（见14-16页）14和列是限定在一端行插入与删除的性表，允插入与删除的一端，不允插入与删除的另一端底。按照“先后出”（FILO）或“后先出”（LIFO）织据，具有作用。用t o p表示位置，用b o t t o m表示底。的基本运算：（1）插入元素入运算；（2）删除元素退运算；（3）元素是元素一个指定的变量，此指无变化。列是指允在一端（尾）入插入，而在另一端（头）行删除的性表。Re a r指指向尾，f r o n t指指向头。列是“先行出”（FIFO）或“后后出”（LILO）的性表。列运算包括（1）入运算：从尾插入一个元素；（2）退运算：从头删除一个元素。循列：s=0表示列空，s=1且f r o n t=r e a r表示列15性表据构中的每一个点于一个存元，种存元存点，点。点由两部分成：（1）用于存据元素值，据域；（2）用于存放指，指域，用于指向前一个或后一个点。在式存构中，存据构的存空间可以不，各据点的存序与据元素之间的系可以不一致，而据元素之间的系是由指域确定的。式存方式即可用于表示性构，也可用于表示非性构。性表，HEAD头指，HEAD=NULL（或0）空表，如果是两指：左指（Ll i n k）指向前件点，右指（Rl i n k）指向后件点。性表的基本运算：查找、插入、删除。16与二叉是一种的非性构，所有元素之间具有明的次特性。在构中，每一个点只有一个前件，父点，有前件的点只有一个，的根点，的根。每一个点可以有多个后件，点的子点。有后件的点叶子点。在构中，一个点所拥有的后件的个点的度，所有点中最大的度的度。的最大次的深度。二叉的特点：（1）非空二叉只有一个根点；（2）每一个点最多有两棵子，且分点的左子与右子。二叉的基本性：（1）在二叉的第k上，最多有2k-1(k1)个点；（2）深度m的二叉最多有2m-1个点；（3）度0的点（即叶子点）总是比度2的点多一个；（4）具有n个点的二叉，其深度至少l o g 2n+1,其中l o g 2n 表示取l o g 2n的整部分；（5）具有n个点的完全二叉的深度l o g 2n+1；（6）设完全二叉共有n个点。如果从根点始，按序（每一从左到右）用自然1，2，.n点行号（k=1,2.n），有以下：若k=1，点根点，它有父点；若k 1，点的父点号INT(k/2)；若2kn，号k的点的左子点号2k；否点无左子点（也无右子点）；若2k+1n，号k的点的右子点号2k+1；否点无右子点。二叉是指除最后一外，每一上的所有点有两个子点，k上有2k-1个点深度m的二叉有2m-1个点。完全二叉是指除最后一外，每一上的点均达到最大值，在最后一上只缺少右边的若干点。二叉存构采用式存构，于二叉与完全二叉可以按序行序存。二叉的遍：（1）前序遍（DLR），首先根点，然后遍左子，最后遍右子；（2）中序遍（LDR），首先遍左子，然后根点，最后遍右子；（3）后序遍（LRD）首先遍左子，然后遍右子，最后根点。17查找技序查找的使用情况：（1）性表无序表；（2）表采用式存构。二分法查找只适用于序存的有序表，于长度n的有序性表，最坏情况只需比l o g 2n次。18排序技排序是指一个无序序列整理成按值非递减序排列的有序序列。交类排序法：（1）冒泡排序法，需要比的次n(n-1)/2；（2）快速排序法。插入类排序法：（1）插入排序法，最坏情况需要n(n-1)/2次比；（2）希尔排序法，最坏情况需要O(n 1.5)次比。类排序法：（1）排序法,最坏情况需要n(n-1)/2次比；（2）堆排序法，最坏情况需要O(n l o g 2n)次比第二章程序设基21程序设设方法和风格如何形成良好的程序设风格3公共基知总1、源程序文化；2、据明的方法；3、句的构；4、输入和输出。注分序言性注和功能性注，句构清晰第一、效率第二。22构化程序设构化程序设方法的四条原是：1.自向下；2.逐步求精；3.模块化；4.限制使用g o t o句。构化程序的基本构和特点：（1）序构：一种的程序设，最基本、最常用的构；（2）构：又分支构，包括和多分支构，可根据条件，判哪一条分支行相的句序列；（3）重复构：又循构，可根据定条件，判是否需要重复行某一相同程序段。23面向象的程序设面向象的程序设：以60年代末挪威奥斯大学和挪威算机中心研制的SIMULA言志。面向象方法的优点：（1）与人类的思方法一致；（2）定性好；（3）可重用性好；（4）易于发大型件品；（5）可护性好。象是面向象方法中最基本的概念，可以用表示客世界中的任何实体，象是实体的抽象。面向象的程序设方法中的象是系统中用描述客事物的一个实体，是构成系统的一个基本位，由一表示其特征的属性和它可行的一操作成。属性即象所包含的信息，操作描述了象行的功能，操作也方法或服务。象的基本特点：（1）惟一性；（2）分类性；（3）多性；（4）封装性；（5）模块立性好。类是指具有共同属性、共同方法的象的集合。所以类是象的抽象，象是类的一个实例。消息是一个实例与另一个实例之间递的信息。消息的成包括（1）接收消息的象的名；（2）消息符，也消息名；（3）零个或多个参。承是指能够直接得已有的性和特征，而不必重复定义他。承分承和多重承。承指一个类只允有一个父类，多重承指一个类允有多个父类。多性是指同样的消息被不同的象接受可致完全不同的-第三章件工程基31件工程基本概念算机件是包括程序、据及相文的完整集合。件的特点包括：（1）件是一种实体；（2）件的生与硬件不同，它有明的制作程；（3）件在运行、使用期间不存在磨、老化；（4）件的发、运行算机系统具有依性，受算机系统的限制，致了件移植的；（5）件复性高，成本昂；（6）件发涉及多的社会因素。件按功能分用件、系统件、支撑件（或工具件）。件危机主要表在成本、量、生率等。件工程是用于算机件的定义、发和护的一整套方法、工具、文、实准和工序。件工程包括3个要素：方法、工具和程。件工程程是把件化输出的一彼此相的源和活动，包含4种基本活动：（1）P件格明；（2）D件发；（3）C件确；（4）A件演。件周期：件品从提出、实、使用护到停止使用退役的程。件生命周期三个段:件定义、件发、运行护，主要活动段是：（1）可行性研究与划制定；（2）需求分析；（3）件设；（4）件实；（5）件；（6）运行和护。件工程的目和与原：目：在定成本、度的前提下，发出具有有效性、可靠性、可理解性、可护性、可重用性、可适性、可移植性、可追踪性和可互操作性且足用户需求的品。基本目：付出低的发成本；达到要求的件功能；取得好的件性能；发件易于移植；需要低的用；能按完成发，及交付使用。基本原：抽象、信息蔽、模块化、局部化、确定性、一致性、完备性和可性。件工程的理和技性研究的容主要包括：件发技和件工程管理。件发技包括：件发方法学、发程、发工具和件工程境。件工程管理包括：件管理学、件工程经济学、件心理学等容。件管理学包括人织、度安排、量保、配置管理、目划等。件工程原包括抽象、信息蔽、模块化、局部化、确定性、一致性、完备性和可性。32构化分析方法构化方法的核心和基是构化程序设理。需求分析方法有（1）构化需求分析方法；（2）面向象的分析的方法。从需求分析建立的模型的特性分：分析和动分析。构化分析方法的实：着眼于据流，自向下，逐分解，建立系统的处理流程，以据流和据字典主要工具,建立系统的模型。构化分析的常用工具（1）据流；（2）据字典；（3）判定；（4）判定表。据流：描述据处理程的工具，是需求理解的模型的形表示，它直接支持系统功能建模。据字典：所有与系统相的据元素的一个有织的列表，以及精确的、格的定义，使得用户和系统分析于输入、输出、存成分和中间算果有共同的理解。判定：从定义的文字描述中分清哪些是判定的条件，哪些是判定的，根据描述材料中的接找出判定条件之间的从属系、并列系、系，根据它构造判定。判定表：与判定相似，据流中的加工要依于多个条件的取值，即完成加工的一动作是由于某一条件取值的合而引发的，使用判定表描述比适宜。据字典是构化分析的核心。件需求格明的特点：（1）正确性；（2）无岐义性；（3）完整性；（4）可性；（5）一致性；（6）可理解性；（7）可追踪性。33构化设方法件设的基本目是用比抽象概括的方式确定目系统如何完成定的任务，件设是确定系统的物理模型。件设是发段最重要的步，是需求准确地化完整的件品或系统的唯一途。从技点看，件设包括件构设、据设、接口设、程设。构设：定义件系统各主要部件之间的系。据设：分析建的模型化据构的定义。接口设：描述件部、件和作系统之间以及件与人之间如何通信。程设：把系统构部件成件的程描述。从工程管理角度看：概要设和设。件设的一般程：件设是一个迭代的程；先行高次的构设；后行低次的程设；穿插行据设和接口设。衡量件模块立性使用耦合性和聚性两个定性的度量准。在程序构中各模块的聚性越强，耦合性越弱。优秀件高聚，低耦合。件概要设的基本任务是：（1）设件系统构；（2）据构及据设；（3）概要设文；（4）概要设文。模块用一个矩形表示，箭头表示模块间的用系。在构中可以用注的箭头表示模块用程中回递的信息。可用实心的箭头表示递的是控制信息，空心箭心表示递的是据。构的基本形式：基本形式、序形式、重复形式、形式。构有四种模块类型：入模块、出模块、变模块和模块。典型的据流类型有两种：变型和事务型。变型系统构由输入、中心变、输出三部分成。事务型据流的特点是：接受一事务，根据事务处理的特点和性，分派一个适的处理元，然后出果。设：是件构中的每一个模块确定实算法和局部据构，用某种定的表达工具表示算法和据构的。常见的程设工具有：形工具（程序流程）、表格工具（判定表）、言工具（PDL）。34件件定义：使用人工或自动手段运行或定某个系统的程，其目的在于它是否足定的需求或是弄清期果与实际果之间的差。件的目的：发而行程序的程。件方法：和动。包括代查、构分析、代量度量。不实际运行件，主要通人工行。动：是基本算机的，主要包括白盒方法和黑盒方法。白盒：在程序部行，主要用于完成件部操作的。主要方法有覆盖、基本基路。黑盒：主要功能不或漏、界面、据构或外部据、性能、初始化和止条件，用于件确。主要方法有等价类划分法、边界值分析法、推法、因果等。件程一般按4个步行：元、集成、收（确）和系统。35程序的程序的任务是和改正程序中的，主要在发段行。程序的基本步：（1）定位；（2）修改设和代，以排除；（3）行回，防止引新的。件可分表和动。主要是指通人的思分析源程序代和排，是主要的设手段，而动是助。主要方法有：（1）强行排法；（2）回溯法；（3）原因排除法。41据系统的基本概念据：实际上就是描述事物的符号。据的特点：有一定的构，有型与值之分，如整型、实型、字符型等。而据的值出了符合定型的值，如整型值15。据：是据的集合，具有统一的构形式并存放于统一的存介，是多种用据的集成，并可被各个用程序共享。据存放据是按据所提供的据模式存放的，具有集成与共享的特点。据管理系统：一种系统件，据中的据织、据操、据护、控制及保护和据服务等，是据的核心。据管理系统功能：（1）据模式定义：即据构建其据框架；（2）据存取的物理构建：据模式的物理存取与构建提供有效的存取方法与手段；（3）据操：用户使用据的据提供方便，如查询、插入、修改、删除等以及的算运算及统；（4）据的完整性、安生性定义与查；（5）据的并发控制与故障恢复；（6）据的服务：如拷贝、存、重、性能、分析等。完成以上六个功能，据管理系统提供以下的据言：（1）据定义言：据的模式定义与据的物理存取构建；（2）据操言：据的操，如查询与增、删、改等；（3）据控制言：据完整性、安全性的定义与查以及并发控制、故障恢复等。据言按其使用方式具有两种构形式：交互式命令(又自含型或自主型言)宿主型言（一般可嵌入某些宿主言中）。据管理：据行划、设、护、视等的业管理人。据系统：由据（据）、据管理系统（件）、据管理（人）、硬件平台（硬件）、件平台（件）五个部分构成的运行实体。据用系统：由据系统、用件及用界面三者成。文件系统段：提供了的据共享与据管理能力，但是它无法提供完整的、统一的、管理和据共享的能力。次据与网据系统段：统一与共享据提供了有力支撑。系据系统段据系统的基本特点：据的集成性、据的高共享性与低冗余性、据立性（物理立性与立性）、据统一管理与控制。据系统的三模式：（1）概念模式：据系统中全局据构的描述，全体用户公共据视；（2）外模式：也子模式与用户模式。是用户的据视，也就是用户所见到的据模式；（3）模式：又物理模式，它出了据物理存构与物理存取方法。据系统的两映射：（1）概念模式到模式的映射；（2）外模式到概念模式的映射。4.2据模型据模型的概念：是据特征的抽象，从抽象次上描述了系统的特征、动行和束条件，据系统的信息表与操作提供一个抽象的框架。描述了据构、据操作及据束。E-R模型的基本概念（1）实体：实世界中的事物；（2）属性：事物的特性；（3）联系：实世界中事物间的系。实体集的系有一一、一多、多多的联系。E-R模型三个基本概念之间的联接系：实体是概念世界中的基本位，属性有属性域，每个实体可取属性域的值。一个实体的所有属性值叫元。E-R模型的示法：（1）实体集表示法；（2）属性表法；（3）联系表示法。次模型的基本构是形构，具有以下特点：（1）每棵有且有一个无双点，根；（2）中除根外所有点有且有一个双。从上看，网模型是一个不加任何条件限制的无向。系模型采用二表表示，表，由表框架及表的元成。一个二表就是一个系。在二表中凡能唯一元的最小属性或。从所有侯健中取一个作用户使用的主。表A中的某属性是某表B的，属性集A的外或外。系中的据束：（1）实体完整性束：束系的主中属性值不能空值；（2）参照完全性束：是系之间的基本束；（3）用户定义的完整性束：它反映了具体用中据的义要求。4.3系代系据系统的特点之一是它建立在据理的基之上，有很多据理可以表示系模型的据操作，其中最著名的是系代与系演算。系模型的基本运算：（1）插入（2）删除(3)修改（4）查询（包括投影、笛卡尔运算）4.4据设与管理据设是据用的核心。据设的两种方法：（1）面向据：以信息需求主，兼处理需求；（2）面向程：以处理需求主，兼信息需求。据的生命周期：需求分析段、概念设段、设段、物理设段、段、段、运行段、一步修改段。需求分析常用构析方法和面向象的方法。构化分析（SA）方法用自向下、逐分解的方式分析系统。用据流表达据和处理程的系。据设，据字典是行的据收集和据分析所得的主要果。据字典是各类据描述的集合，包括5个部分：据、据构、据流（可以是据，也可以是据构）、据存、处理程。据概念设的目的是分析据在义系。设的方法有两种（1）集中式模式设法（适用于小型或并不复的位或部门）；（2）视集成设法。设方法：E-R模型与视集成。视设一般有三种设次序：自向下、由底向上、由向外。视集成的几种冲突：命名冲突、概念冲突、域冲突、束冲突。系视设：系视的设又外模式设。系视的主要作用：（1）提供据立性；（2）能适用户据的不同需求；（3）有一定据保密功能。据的物理设主要目是据部物理构作整并合理的存取路，以提高据速度有效利用存空间。一般RDBMS中留用户参与物理设的容大致有索引设、集成簇设和分设。据管理的容：（1）据的建立；（2）据的整；（3）据的重；（4）据安全性与完整性控制；（5）据的故障恢复；（6）据控。-二公共基知（填空40道）(1)算法的复度主要包括_复度和空间复度。答：间(2)据的构在算机存空间中的存放形式据的_模式_。答：#模式#概念模式(3)若按功能划分，件的方法通常分白盒方法和_方法。答：黑盒(4)如果一个工人可管理多个设施，而一个设施只被一个工人管理，实体工人与实体设备之间存在_联系。答：一多#1：N#1:n (5)系据管理系统能实的门系运算包括、接和_。答：投影(6)在先左后右的原下，根据根点的次序，二叉的遍可以分三种：前序遍、_遍和后序遍。答：中序(7)构化程序设方法的主要原可以概括自向下、逐步求精、_和限制使用g o t o句。答：模块化(8)件的方法主要有：强行排法、_和原因排除法。答：回溯法(9)据系统的三模式分_概念_模式、部模式与外部模式。答：概念#(10)据字典是各类据描述的集合，它通常包括5个部分，即据、据构、据流、_据存_和处理程。答：(11)设一棵完全二叉共有500个点，在二叉中有_个叶子点。答：250 (12)在最坏情况下，冒泡排序的间复度_。答：n(n-1)/2#n*(n-1)/2#O(n(n-1)/2)#O(n*(n-1)/2)(13)面向象的程序设方法中涉及的象是系统中用描述客事物的一个_实体_。答：(14)件的需求分析段的工作，可以概括四个方面：需求取_、需求分析、需求格明和需求。_答：(15)_是据用的核心。答：据设(16)据构包括据的_构和据的存构。答：(17)件工程研究的容主要包括：_技和件工程管理。答：件发(18)与构化需求分析方法相的是_方法。答：构化设(19)系模型的完整性是系的某种束条件，包括实体完整性、_和自定义完整性。答：参照完整性(20)据模型按不同的用次分三种类型，它是_据模型、据模型和物理据模型。答：概念(21)的基本运算有三种：入、退和_。答：元素#的元素#出元素(22)在面向象方法中，信息蔽是通象的_封装_性实的。答：(23)据流的类型有_和事务型。答：变型(24)据系统中实各种据管理功能的核心件_。答：据管理系统#DBMS (25)系模型的据CAO即是建立在系上的据CAO，一般有_查询_、增加、删除和修改四种CAO作。答：(26)实算法所需的存元多少和算法的工作量大小分算法的_。答：空间复度和间复度(27)据构包括据的构、据的_以及据的CAO作运算。答：存构(28)一个类可以从直接或间接的祖先中承所有属性和方法。采用个方法提高了件的_。答：可重用性(29)面向象的模型中，最基本的概念是象和_。答：类(30)件护活动包括以下几类：改正性护、适性护、_护和防性护。答：完善性(31)算法的基本特征是可行性、确定性、_和拥有足够的情。答：有性(32)序存方法是把上相邻的点存在物理位置_的存元中。答：相邻(33)Ja c k s o n构化程序设方法是英国的M.Ja