《全国计算机等级考试》由会员分享，可在线阅读，更多相关《全国计算机等级考试（47页珍藏版）》请在金锄头文库上搜索。
1、全国计算机等级考试二级二级公共公共基础基础知识知识竞籍酸喳础棱兴遗篡拴甸投觉枣寸咱沾蘸漱碴锗伐泡蹬驯膘旋矩农详伟崖全国计算机等级考试全国计算机等级考试公共基础知识公共基础知识内容：内容：考试大纲考试大纲数据结构与算法数据结构与算法程序设计基础程序设计基础软件工程基础软件工程基础数据库设计基础数据库设计基础优设望训舌拈郁殆津动归您耳挺襄焦摈笔焊瞪疙秦倔椽隧孝足搏俞顷戈流全国计算机等级考试全国计算机等级考试2考试大纲考试大纲基本要求基本要求1、掌握算法的基本概念。、掌握算法的基本概念。2、掌握基本数据结构及其操作。、掌握基本数据结构及其操作。3、掌握基本排序和查找算法。、掌握基本排序和查找算法。4
2、、掌握逐步求精的结构化程序设计方法。、掌握逐步求精的结构化程序设计方法。5、掌握软件工程的基本方法，具有初步应用、掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。相关技术进行软件开发的能力。6、掌握数据库的基本知识，了解关系数据库、掌握数据库的基本知识，了解关系数据库的设计。的设计。措钨内瞳契锻轻虽斡扎酞喧崖椭负伴杨真矣佣柳棍氧榜咖狈呼漱组委颖咏全国计算机等级考试全国计算机等级考试3考试大纲考试大纲考试内容考试内容一、基本数据结构与算法一、基本数据结构与算法1、算法的基本概念；算法复杂度的概念和意义、算法的基本概念；算法复杂度的概念和意义(空间复杂度与空间复杂度与时间复杂度时间
3、复杂度)。2、数据结构的定义；数据的逻辑结构和存储结构；数据结构、数据结构的定义；数据的逻辑结构和存储结构；数据结构的图形表示；线性结构与非线性结构的概念。的图形表示；线性结构与非线性结构的概念。3、线性表的定义；线性表的顺序存储结构及其插入删除运算。、线性表的定义；线性表的顺序存储结构及其插入删除运算。4、栈和队列的定义；栈和队列的顺序存储结构及其基本运算。、栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5、线性单链表，双向链表与循环链表的结构及其基本运算。、线性单链表，双向链表与循环链表的结构及其基本运算。6、树的基本概念；二叉树的定义及其存储结构；二叉树的前、树的基本概念；二叉树的
4、定义及其存储结构；二叉树的前序、中序和后序遍历。序、中序和后序遍历。7、顺序查找与二分查找算法；基本排序算法、顺序查找与二分查找算法；基本排序算法(交换类排序、选交换类排序、选择类排序、插入类排序择类排序、插入类排序)。礁旺裔霜玩丈拂萍演菌绽杭银谱柿甘距含栋耿碘汗休扎醇种牢住浊厨传疗全国计算机等级考试全国计算机等级考试4考试大纲考试大纲考试内容考试内容二、程序设计基础二、程序设计基础1、程序设计方法与风格。、程序设计方法与风格。2、结构化程序设计。、结构化程序设计。3、面向对象的程序设计方法，对象，方法，属性及继承与多、面向对象的程序设计方法，对象，方法，属性及继承与多态性。态性。畔惭仕颠缆卸
5、病玫摆侣枯棒烁典簿樱后涂乔贿都锭淑拯烛孕扫棒冒腥既签全国计算机等级考试全国计算机等级考试5考试大纲考试大纲考试内容考试内容三、软件工程基础三、软件工程基础1、软件工程的基本概念；软件生命周期概念；软件工具与软、软件工程的基本概念；软件生命周期概念；软件工具与软件开发环境。件开发环境。2、结构化分析方法；数据流图，数据字典，软件需求规格说、结构化分析方法；数据流图，数据字典，软件需求规格说明书。明书。3、结构化设计方法；、结构化设计方法； 总体设计，详细设计。总体设计，详细设计。4、软件测试的方法；白盒测试，黑盒测试，测试用例设计；、软件测试的方法；白盒测试，黑盒测试，测试用例设计；软件测试的实
6、施；单元测试，集成测试，系统测试。软件测试的实施；单元测试，集成测试，系统测试。5、程序的调试，静态调试与动态调试。、程序的调试，静态调试与动态调试。蚂直化少届釜蛮锅及未颗颈绎讶球芥台锐祥遂箍娥遇烙蒸串逝帅岭际嫉疤全国计算机等级考试全国计算机等级考试6考试大纲考试大纲考试内容考试内容四、数据库设计基础四、数据库设计基础1、数据库的基本概念；数据库，数据库管理系统，数据库系、数据库的基本概念；数据库，数据库管理系统，数据库系统。统。2、数据模型；实体联系模型及、数据模型；实体联系模型及E-R图，从图，从E-R图导出关系数据图导出关系数据模型。模型。3、关系代数运算，包括集合运算及选择、投影、连接
7、运算；、关系代数运算，包括集合运算及选择、投影、连接运算；数据库规范化理论。数据库规范化理论。4、数据库设计方法和步骤；需求分析、概念设计、逻辑设计、数据库设计方法和步骤；需求分析、概念设计、逻辑设计和物理设计的相关策略。和物理设计的相关策略。绿科矫队蔓支敢机谰免纬簿坑笼赂芒笺壳模钢椭算儡阴妹炳途谈卡半毡扯全国计算机等级考试全国计算机等级考试7考试大纲考试大纲考试题型考试题型选择题选择题10 题题每题每题 2 分分共共 20 分分填空题填空题5 题题每题每题 2 分分共共 10 分分合计合计 30 分分满脱掉疗歹植拿隅擞茅感骸篆吧扒烧盟固恿乌哲语揭停泛雌恕胞随宁摇裤全国计算机等级考试全国计算机
8、等级考试8数据结构与算法数据结构与算法关键考点关键考点算法基本概念及算法复杂度算法基本概念及算法复杂度数据的存储结构数据的存储结构栈和队列栈和队列线性链表线性链表二叉树基本概念及其特性二叉树基本概念及其特性查找技术查找技术观富扬栈窗纯称躬缴缀糊幂前岿筐崔存批铭腕坝碧击孜登倍坍鸥嫡踢漫雍全国计算机等级考试全国计算机等级考试9数据结构与算法数据结构与算法算法的基本概念算法的基本概念1、算法、算法算法是指解题方案的准确而完整的描述算法是指解题方案的准确而完整的描述。注意：算法与数学上的计算方法不是同一个概念。算法要考虑计算机的注意：算法与数学上的计算方法不是同一个概念。算法要考虑计算机的特点，要考虑
9、计算方法的可行性。特点，要考虑计算方法的可行性。算法也不等于程序。算法不考虑具体的机器及编程语言。解决问题算法也不等于程序。算法不考虑具体的机器及编程语言。解决问题时，总是先设计算法，然后进行编程。时，总是先设计算法，然后进行编程。2、算法的基本特征、算法的基本特征可行性可行性确定性确定性有穷性有穷性拥有足够的情报拥有足够的情报算法是一个动态概念，强调实际的执行过程。算法是一个动态概念，强调实际的执行过程。数学上的计算方法是一个静态概念，注重理论上的正确性。数学上的计算方法是一个静态概念，注重理论上的正确性。数学上的计算方法是设计算法的基础。数学上的计算方法是设计算法的基础。呵抬瞪伊误蹲缮释例
10、规级油梁袭需枉贡气修予黎身讶椒偿囚屋郡欧神慑蘑全国计算机等级考试全国计算机等级考试10数据结构与算法数据结构与算法算法的基本概念算法的基本概念3、算法的基本要素、算法的基本要素算法中对数据的运算和操作算法中对数据的运算和操作基本的运算和操作有：算术运算、逻辑运算、关系运算、数据传输。基本的运算和操作有：算术运算、逻辑运算、关系运算、数据传输。算法的控制结构算法的控制结构控制结构决定操作的执行顺序。要求符合结构化原则，强调易读性。控制结构决定操作的执行顺序。要求符合结构化原则，强调易读性。4、算法设计基本方法、算法设计基本方法列举法列举法 列举所有可能情况，检测其中符合条件的结果。列举所有可能情
11、况，检测其中符合条件的结果。归纳法归纳法 列举若干特殊情况，分析归纳出一般规律。列举若干特殊情况，分析归纳出一般规律。递推递推 从已知初始条件出发，逐步推导出中间及最后结果。从已知初始条件出发，逐步推导出中间及最后结果。递归递归 将复杂问题归结为简单问题，在归结为更简单问题，将复杂问题归结为简单问题，在归结为更简单问题， 。减半递推技术减半递推技术 将问题规模将问题规模“减半减半”，并重复该，并重复该“减半减半” 的过程。的过程。回溯法回溯法 分析问题，找出某些线索，沿线索逐步试探。若试探成功，则分析问题，找出某些线索，沿线索逐步试探。若试探成功，则继续，若试探失败，则回退。直至问题解决。继续
12、，若试探失败，则回退。直至问题解决。捣剿义淑澄皆颧散赵查恶囤斡乐堡脆观授臭苛筐匣拣撂融冤淑鸦冲司僵胎全国计算机等级考试全国计算机等级考试11数据结构与算法数据结构与算法算法的基本概念算法的基本概念5、算法的时间复杂度、算法的时间复杂度指执行算法所需要的计算工作量指执行算法所需要的计算工作量算法工作量的度量应与计算机、编程语言、编程细节等无关。算法工作量的度量应与计算机、编程语言、编程细节等无关。算法的工作量用算法的工作量用算法所执行的基本运算次数算法所执行的基本运算次数衡量。衡量。算法工作量是问题规模的函数：算法工作量是问题规模的函数：算法的工作量算法的工作量= f (n)度量方法有：度量方法
13、有：平均性态分析平均性态分析 计算其加权平均值计算其加权平均值最坏情况分析最坏情况分析 计算其基本运算的最大次数计算其基本运算的最大次数6、算法的空间复杂度、算法的空间复杂度指执行算法所需要的存储空间指执行算法所需要的存储空间包括：算法程序所占据的存储空间包括：算法程序所占据的存储空间待处理数据所占据的存储空间待处理数据所占据的存储空间算法程序执行中所需要的额外存储空间算法程序执行中所需要的额外存储空间如果额外存储空间大小不随问题规模变化，则称之为如果额外存储空间大小不随问题规模变化，则称之为算法原地工作算法原地工作。降低算法的空间复杂度，应从数据的存储空间和额外空间入手。降低算法的空间复杂度
14、，应从数据的存储空间和额外空间入手。具箭竣榨朵靠搀鉴殆秩矗拔掀怕甫敖存暂攀操梭赠狙赋羚概到绽娠羹弥血全国计算机等级考试全国计算机等级考试12数据结构与算法数据结构与算法数据结构的基本概念数据结构的基本概念1、数据结构、数据结构数据结构是指相互有关联的数据元素的集合数据结构是指相互有关联的数据元素的集合数据结构是指带有结构的数据元素的集合。数据结构是指带有结构的数据元素的集合。结构结构 通常指前后件关系。通常指前后件关系。主要研究：数据元素间的固有逻辑关系主要研究：数据元素间的固有逻辑关系 数据元素在计算机中的存储关系数据元素在计算机中的存储关系 对各种数据结构进行的运算对各种数据结构进行的运算
15、2、数据的逻辑结构、数据的逻辑结构指反映数据元素之间逻辑关系的数据结构指反映数据元素之间逻辑关系的数据结构前后件前后件(直接前驱和直接后继直接前驱和直接后继)关系就是指逻辑关系关系就是指逻辑关系3、数据的存储结构、数据的存储结构数据的逻辑结构在计算机中的存储形式数据的逻辑结构在计算机中的存储形式存储结构也称为物理结构存储结构也称为物理结构同一种逻辑结构可以有不同的存储结构同一种逻辑结构可以有不同的存储结构常用的有：顺序、链接、索引等形式常用的有：顺序、链接、索引等形式台房洲窟衣头揣垂防账役俄凶扳龚传鳖够减归居砰柒怪铁挟膳龚阅呐殊岭全国计算机等级考试全国计算机等级考试13数据结构与算法数据结构与
16、算法数据结构的基本概念数据结构的基本概念4、数据结构的表示、数据结构的表示二元关系表示：二元关系表示：两个要素：数据元素的集合两个要素：数据元素的集合D，该集合上的关系，该集合上的关系R。即：即：B=(D,R)如：如：D=春春,夏夏,秋秋,冬冬 R=(春春,夏夏),(夏夏,秋秋),(秋秋,冬冬)图形表示：图形表示：标有元素值的方框表示结点，有向线段表示逻辑关系。标有元素值的方框表示结点，有向线段表示逻辑关系。春春 夏夏 秋秋 冬冬5、线性结构和非线性结构、线性结构和非线性结构线性结构：线性结构：一个非空的线性结构有且只有一个根结点，每一个非空的线性结构有且只有一个根结点，每个结点最多只有一个直
17、接前驱、最多只有一个直接后继。个结点最多只有一个直接前驱、最多只有一个直接后继。非线性结构：非线性结构：不是线性结构的数据结构。不是线性结构的数据结构。彩嘎壹绕双哄症巨夫悬畜整讣续供愧设鲤疼曙宪曝禹极弗米辐虏霉吨绵敦全国计算机等级考试全国计算机等级考试14数据结构与算法数据结构与算法线性表及其顺序存储结构线性表及其顺序存储结构1、线性表、线性表线性表是由线性表是由 n (n0)个元素组成的有限序列：个元素组成的有限序列：(a1,a2,ai,an)有且只有一个根结点，它无直接前驱。有且只有一个根结点，它无直接前驱。有且只有一个终端结点，它无直接后继。有且只有一个终端结点，它无直接后继。除根结点和
18、终端结点外，其他所有结点都有且只有一个直接前驱和直接后继。除根结点和终端结点外，其他所有结点都有且只有一个直接前驱和直接后继。结点个数结点个数n称为线性表的长度。称为线性表的长度。n=0时，称为空表。时，称为空表。2、线性表的顺序存储、线性表的顺序存储顺序存储也称为顺序分配顺序存储也称为顺序分配线性表中所有元素所占的存储空间是连续的线性表中所有元素所占的存储空间是连续的线性表中各元素在存储空间中按照逻辑顺序依次存储线性表中各元素在存储空间中按照逻辑顺序依次存储3、顺序表的运算、顺序表的运算线性表的顺序存储结构通常称为线性表的顺序存储结构通常称为顺序表顺序表包括：插入、删除、查找、分解、合并、复
19、制、逆转等。包括：插入、删除、查找、分解、合并、复制、逆转等。在高级语言中，顺序表对应一维数组。在高级语言中，顺序表对应一维数组。顺序表的查找方便，插入和删除较麻烦。顺序表的查找方便，插入和删除较麻烦。烁巢妊照耕钒铰撑走统瑞雁坏剿漏粳铭攒太冕橱镜渭耶堕情怔嘴滥悠断抄全国计算机等级考试全国计算机等级考试15数据结构与算法数据结构与算法线性表及其顺序存储结构线性表及其顺序存储结构注意：注意： 线性表属于线性结构。线性表属于线性结构。 线性表的顺序存储结构通常称为顺序表。线性表的顺序存储结构通常称为顺序表。 在顺序表中，所有元素按照其逻辑顺序连续存储，前后件元素紧邻，在顺序表中，所有元素按照其逻辑顺
20、序连续存储，前后件元素紧邻，前件元素一定存储在后件元素的前面。前件元素一定存储在后件元素的前面。 在程序设计语言中，线性表的顺序存储结构对应了一维数组。因为在程序设计语言中，线性表的顺序存储结构对应了一维数组。因为在程序设计语言中，一维数组与计算机中实际的存储空间结构是一致在程序设计语言中，一维数组与计算机中实际的存储空间结构是一致的。的。 在顺序表中，如果要在第在顺序表中，如果要在第 i 个位置插入一个新元素，则原第个位置插入一个新元素，则原第 i 个元素个元素以及之后的所有元素都要依次后移一个位置。在平均情况下，在顺序以及之后的所有元素都要依次后移一个位置。在平均情况下，在顺序表中插入一个
21、新元素，需要移动表中插入一个新元素，需要移动 n/2 个元素。个元素。 在顺序表中，如果要删除第在顺序表中，如果要删除第 i 个位置的元素，则原第个位置的元素，则原第 i 个元素之后的个元素之后的所有元素都要依次前移一个位置。在平均情况下，在顺序表中删除一所有元素都要依次前移一个位置。在平均情况下，在顺序表中删除一个元素，需要移动个元素，需要移动 n/2 个元素。个元素。 圈嗣了鼠袱瘁泌帧境烩呢兑枝噶釜馁逊肉任啼炽砌医卷吏秉钙娶盈滥箍诗全国计算机等级考试全国计算机等级考试16数据结构与算法数据结构与算法栈及其基本运算栈及其基本运算1、栈、栈栈栈(stack)是限定在一端进行插入和删除的线性表是
22、限定在一端进行插入和删除的线性表允许进行插入或删除的一端称为允许进行插入或删除的一端称为栈顶栈顶。不允许进行插入或删除的另一端称为不允许进行插入或删除的另一端称为栈底栈底。其特点为其特点为“先入后出先入后出”(FILO)或或“后入先出后入先出”(LIFO)。(记忆作用记忆作用)通常设置指针通常设置指针top指向栈顶，指针指向栈顶，指针bottom指向栈底。指向栈底。2、栈的顺序存储结构、栈的顺序存储结构栈的各个数据元素按其逻辑顺序依次连续存储。栈的各个数据元素按其逻辑顺序依次连续存储。由于插入删除操作只能在栈顶一端进行，所以由于插入删除操作只能在栈顶一端进行，所以不需要移动数据元素。不需要移动
23、数据元素。3、栈的基本运算、栈的基本运算入栈入栈：在栈顶位置插入新元素。：在栈顶位置插入新元素。出栈出栈：取出栈顶位置的元素。：取出栈顶位置的元素。读栈顶元素读栈顶元素：读出栈顶位置的元素。：读出栈顶位置的元素。“上溢上溢”：入栈时堆栈已满。：入栈时堆栈已满。“下溢下溢”：出栈时堆栈已空。：出栈时堆栈已空。南曳赘矿谜庆肮蔬似岳灿咳荣刑晨瞄蔡柯连携寞眠许佰缅孙谰饼词膳馒媳全国计算机等级考试全国计算机等级考试17数据结构与算法数据结构与算法队列及其基本运算队列及其基本运算1、队列、队列队列队列(queue)是限定在一端进行插入另一端进行删除的线性表是限定在一端进行插入另一端进行删除的线性表允许进行
24、插入的一端称为允许进行插入的一端称为队尾队尾。允许进行删除的另一端称为允许进行删除的另一端称为队头队头。其特点为其特点为“先入先出先入先出”(FIFO)或或“后入后出后入后出”(LILO)。(先来先服务先来先服务)通常设置指针通常设置指针rear指向队尾，指针指向队尾，指针front指向队头。指向队头。2、队列的顺序存储结构、队列的顺序存储结构队列的各个数据元素按其逻辑顺序依次连续存储。队列的各个数据元素按其逻辑顺序依次连续存储。由于插入删除操作只能在队列的两端进行，所以由于插入删除操作只能在队列的两端进行，所以不需要移动数据元素。不需要移动数据元素。3、队列的基本运算、队列的基本运算在实际应
25、用中常常使用在实际应用中常常使用循环队列循环队列。入队入队：在队尾位置插入新元素。：在队尾位置插入新元素。 出队出队：取出队头位置的元素。：取出队头位置的元素。 “上溢上溢”：入队时队列已满。：入队时队列已满。“下溢下溢”：出队时队列已空。：出队时队列已空。差驼泳缸情氧插入遣桌奢炬榔埂蒙酥窘驱彩桶莫很卯阅扬虾质湃隆低驳朝全国计算机等级考试全国计算机等级考试18数据结构与算法数据结构与算法线性链表线性链表1、链式存储方式、链式存储方式 结点由两部分组成：结点由两部分组成：数据域数据域(存储数据存储数据)、指针域指针域(指向其前件或后件指向其前件或后件)。 数据结构的存储空间可以不连续，存储顺序与
26、逻辑关系可以不一致。数据结构的存储空间可以不连续，存储顺序与逻辑关系可以不一致。 链式存储方式既可以用来表示线性结构，也可以表示非线性结构。链式存储方式既可以用来表示线性结构，也可以表示非线性结构。2、线性链表、线性链表线性表的链式存储结构称为线性表的链式存储结构称为线性链表线性链表。(栈的链式存储结构称为链栈、队列的链式存储结构称为链队列栈的链式存储结构称为链栈、队列的链式存储结构称为链队列)常用的线性链表有：常用的线性链表有：单链表单链表 (一个指针域，指向直接后继一个指针域，指向直接后继)双向链表双向链表 (两个指针域，指向直接后继及后继两个指针域，指向直接后继及后继) 循环链表循环链表
27、 (所有结点的指针构成循环链所有结点的指针构成循环链)3、线性链表的基本运算、线性链表的基本运算查找查找：在线性链表中查找指定元素。：在线性链表中查找指定元素。插入插入：在线性链表中插入新结点。：在线性链表中插入新结点。删除删除：在线性链表中删除指定结点。：在线性链表中删除指定结点。补盆弟彤另延垮汗抿愤扇洒伟脓己臣蔼频劝钩摧旬取卞腕壮鄙霓邵作催驯全国计算机等级考试全国计算机等级考试19数据结构与算法数据结构与算法树的基本概念树的基本概念1、树、树树是一种简单的非线性结构。树是一种简单的非线性结构。元素间的关系具有明显的层次结构。元素间的关系具有明显的层次结构。2、相关的术语、相关的术语根结点根
28、结点叶节点叶节点父结点父结点子结点子结点子树子树结点的度结点的度树的度树的度树的深度树的深度淘募钉示三讫峭奸惦既乎关砌屈泛乘羞隶缅沏膏铅矣舶嫉呀缴禹槛谈箩盗全国计算机等级考试全国计算机等级考试20数据结构与算法数据结构与算法二叉树二叉树1、二叉树的特点、二叉树的特点非空二叉树只有一个根结点。非空二叉树只有一个根结点。每个结点最多有左右两棵子树。每个结点最多有左右两棵子树。2、二叉树的基本性质、二叉树的基本性质第第 k 层上最多有层上最多有 2 k-1个结点个结点深度为深度为 m 的二叉树最多有的二叉树最多有 2m-1个结点个结点任何二叉树叶结点总比度为任何二叉树叶结点总比度为 2 的节点多一个
29、的节点多一个n 个节点的二叉树的深度为个节点的二叉树的深度为 log2n+13、满二叉树、满二叉树4、完全二叉树、完全二叉树5、二叉树的遍历、二叉树的遍历先序遍历先序遍历 中序遍历中序遍历后序遍历后序遍历ABDEGCFHI DBGEACHFI DGEBHIFCA营拂惫磺冠肛疾踏胰竖岭茨乌驼熬阂欧堕井处丈冲附默羔郡安元绊渡匿丽全国计算机等级考试全国计算机等级考试21数据结构与算法数据结构与算法查找技术查找技术1、顺序查找、顺序查找从线性表的第一个元素开始，依次与指定数据比较，若相等则查找成功，从线性表的第一个元素开始，依次与指定数据比较，若相等则查找成功，若比较的所有元素都不相等，则查找失败。若
30、比较的所有元素都不相等，则查找失败。最坏情况的比较次数为表长最坏情况的比较次数为表长n，平均情况为，平均情况为n/2。无序顺序表的查找只能采用顺序查找的方法。无序顺序表的查找只能采用顺序查找的方法。线性表在链式存储时也只能采用顺序查找的方法。线性表在链式存储时也只能采用顺序查找的方法。2、二分法查找、二分法查找在顺序存储的线性表为有序的情况下，可以使用二分法查找。在顺序存储的线性表为有序的情况下，可以使用二分法查找。方法为：方法为：将待查数据与线性表的中间项比较：将待查数据与线性表的中间项比较：若相等，则查找成功；若相等，则查找成功；若小于，则在线性表的前半部分进行二分法查找；若小于，则在线性
31、表的前半部分进行二分法查找；若大于，则在线性表的后半部分进行二分法查找；若大于，则在线性表的后半部分进行二分法查找；反复进行直到相等反复进行直到相等(查找成功查找成功)或子表长度为或子表长度为0(查找失败查找失败)。距钵苞算毁阿堂短窜揪缘牧建卧邹诺北吭荷锤搬腿鄂寇殊俭鲸篆躲往翻藤全国计算机等级考试全国计算机等级考试22数据结构与算法数据结构与算法排序技术排序技术1、交换类排序、交换类排序起泡排序起泡排序最坏情况下的比较次数为最坏情况下的比较次数为 n(n-1)/2 。 快速排序快速排序最坏情况下的比较次数为最坏情况下的比较次数为 n(n-1)/2 。 2、插入类排序、插入类排序简单插入排序简单
32、插入排序最坏情况下的比较次数为最坏情况下的比较次数为 n(n-1)/2 。 希尔排序希尔排序最坏情况下的比较次数为最坏情况下的比较次数为 O( n 1.5) 。3、选择类排序、选择类排序简单选择排序简单选择排序最坏情况下的比较次数为最坏情况下的比较次数为 n(n-1)/2 。堆排序堆排序最坏情况下的比较次数为最坏情况下的比较次数为 O( n log2n) 。察仔字膏弄级茅飞水蛹窟样贩吭税搀之韭择搔幂竟舞狮木氦股概证界高桌全国计算机等级考试全国计算机等级考试23数据结构与算法数据结构与算法本章重点本章重点1、算法是问题处理方案正确而完整的描述，算法的效率与数据的存储结构、算法是问题处理方案正确而
33、完整的描述，算法的效率与数据的存储结构有密切的关系。有密切的关系。2、数据的逻辑结构在计算机中的表示、数据的逻辑结构在计算机中的表示(存储方式存储方式)称为数据的存储结构称为数据的存储结构(物理物理结构结构)。一种逻辑结构可以有多种存储结构。一种逻辑结构可以有多种存储结构。3、在长度为、在长度为 n 的顺序表中，插入或删除一个元素平均需要移动一半元素。的顺序表中，插入或删除一个元素平均需要移动一半元素。4、栈是特殊的线性表，具有记忆作用。特点是、栈是特殊的线性表，具有记忆作用。特点是“先进后出先进后出(后进先出后进先出)”。栈顶指针动态反映了栈中元素的变化情况。栈顶指针动态反映了栈中元素的变化
34、情况。5、队列是特殊的线性表。特点是、队列是特殊的线性表。特点是“先进先出先进先出(后进后出后进后出)”。队头和队尾指。队头和队尾指针动态地反映了队列中元素的变化情况。针动态地反映了队列中元素的变化情况。6、线性链表是线性表的链式存储结构。在线性链表中，各元素节点的存储、线性链表是线性表的链式存储结构。在线性链表中，各元素节点的存储空间可以不连续，存储顺序也可以与逻辑顺序不一致。线性链表的插入删空间可以不连续，存储顺序也可以与逻辑顺序不一致。线性链表的插入删除操作不需要移动数据元素。除操作不需要移动数据元素。7、二叉树是一种非线性结构。主要性质有：、二叉树是一种非线性结构。主要性质有：第第k层
35、上最多有层上最多有 2 k-1 个结点个结点深度为深度为 m 时，最多有时，最多有2 m 1 个结个结点点度为度为0的结点比度为的结点比度为2的多一个的多一个深度至少为深度至少为 log2n +1崇偏禁佃琴啤藉邵赁标灭斜溢盾鉴丙的箱幼袜鲁秧形朗赔座管悍漳官闲凛全国计算机等级考试全国计算机等级考试24数据结构与算法数据结构与算法本章重点本章重点8、满二叉树是二叉树的特殊形态，满二叉树的各层结点都达到最大值，叶、满二叉树是二叉树的特殊形态，满二叉树的各层结点都达到最大值，叶结点只出现在最后一层。结点只出现在最后一层。9、完全二叉树是二叉树的特殊形态，完全二叉树除最后一层外，各层结点、完全二叉树是二
36、叉树的特殊形态，完全二叉树除最后一层外，各层结点都达到最大值，叶结点只出现在最后两层。满二叉树属于完全二叉树。都达到最大值，叶结点只出现在最后两层。满二叉树属于完全二叉树。10、根据扫描根结点的顺序，按照先左后右的原则，遍历二叉树有三种、根据扫描根结点的顺序，按照先左后右的原则，遍历二叉树有三种方法：前序遍历、中序遍历、后序遍历。方法：前序遍历、中序遍历、后序遍历。11、在长度为、在长度为 n 的线性表中进行顺序查找，最坏情况需要比较的线性表中进行顺序查找，最坏情况需要比较 n 次。次。12、在长度为、在长度为 n 的线性表中进行对分查找，最坏情况需要比较的线性表中进行对分查找，最坏情况需要比
37、较 log2n 次。但次。但对分查找只适用于有序顺序表。对分查找只适用于有序顺序表。13、在冒泡排序、快速排序、简单插入排序、选择排序的方法中，最坏情况、在冒泡排序、快速排序、简单插入排序、选择排序的方法中，最坏情况下需要比较的次数为下需要比较的次数为 n(n-1)/2 。曝寅征舔彰蓟啊九芥耻榨脱凑涎江饮伪旱伤内脂豺箭给梆害理绦依衙党碾全国计算机等级考试全国计算机等级考试25程序设计基础程序设计基础关键考点关键考点结构化设计的原则结构化设计的原则面向对象方法的基本概念面向对象方法的基本概念贮尘筋展站仆玫邮裕柏铁筏欧砰咱化戴吝胯堡遵湛秉闹妖哑射樱膝为化纠全国计算机等级考试全国计算机等级考试26程
38、序设计基础程序设计基础程序设计方法与风格程序设计方法与风格1、程序设计方法、程序设计方法就程序设计的方法和技术的发展而言就程序设计的方法和技术的发展而言主要经历了主要经历了结构化程序设计结构化程序设计和和面向对象程序设计面向对象程序设计两个阶段两个阶段2、程序设计风格、程序设计风格程序设计风格是指编写程序时所表现出来的程序设计风格是指编写程序时所表现出来的特点特点、习惯习惯和和逻辑思路逻辑思路。程序设计风格会深刻影响软件的质量和可维护性，良好的程序设计风格程序设计风格会深刻影响软件的质量和可维护性，良好的程序设计风格可以使程序的结构清晰合理，使程序代码便于维护。可以使程序的结构清晰合理，使程序
39、代码便于维护。程序设计风格的主导：程序设计风格的主导：“清晰第一清晰第一，效率第二效率第二”。主要因素：主要因素：源程序文档化源程序文档化数据说明的方法数据说明的方法语句的结构语句的结构输入和输出输入和输出鄙豪填念念湘甲渡蔷澳裕捎札莉聂翌漱沽每俱猩湃晌衬吟鄂哨窿襄梨垒价全国计算机等级考试全国计算机等级考试27程序设计基础程序设计基础结构化程序设计结构化程序设计1、结构化程序设计、结构化程序设计要求把程序的结构限制为顺序、选择和循环三种基本结构。要求把程序的结构限制为顺序、选择和循环三种基本结构。2、结构化程序设计的原则、结构化程序设计的原则自顶向下自顶向下先总体后细节，先全局后局部。先总体后细
40、节，先全局后局部。逐步求精逐步求精对复杂问题设计子目标过度，逐步细化。对复杂问题设计子目标过度，逐步细化。模块化模块化将复杂问题分解为若干简单问题。将复杂问题分解为若干简单问题。限制使用限制使用GOTO语句语句防止造成程序逻辑结构混乱。防止造成程序逻辑结构混乱。3、三种基本结构、三种基本结构顺序结构顺序结构 选择结构选择结构循环结构循环结构4、特点、特点所有控制结构由三种基本结构组成所有控制结构由三种基本结构组成各个模块单入口单出口各个模块单入口单出口模块的内聚性强模块的内聚性强 模块间的偶合性低模块间的偶合性低比局隙碑做软榜自忘征象那叭恿佐物袍慧萨腺蔗泪川傍渤窘甘暖赠怕俱鼎全国计算机等级考试
41、全国计算机等级考试28程序设计基础程序设计基础面向对象的程序设计面向对象的程序设计1、面向对象、面向对象面向对象方法的本质，是从客观世界固有的事物出发来构造系统，用现面向对象方法的本质，是从客观世界固有的事物出发来构造系统，用现实生活中常用的思维方法来描述客观事物，是系统中的对象及对象间的实生活中常用的思维方法来描述客观事物，是系统中的对象及对象间的关系能如实反映事物及其关系。关系能如实反映事物及其关系。2、主要优点、主要优点与人类习惯的思维方法一致与人类习惯的思维方法一致稳定性好稳定性好可重用性好可重用性好易于开发大型软件产品易于开发大型软件产品可维护性好可维护性好3、基本概念、基本概念对象
42、对象类和实例类和实例消息消息继承继承多态性多态性烽号泼朱防砖嘛践砾浑铺泉箔锑渴憾怕美熊踞怪呆滤帅少智缆面侗忌珊梨全国计算机等级考试全国计算机等级考试29程序设计基础程序设计基础本章重点本章重点1、程序设计并不等于编程，编程只是程序设计过程中的一小步。、程序设计并不等于编程，编程只是程序设计过程中的一小步。2、结构化程序设计要求把程序的结构限制为顺序、选择、循环三种基本结、结构化程序设计要求把程序的结构限制为顺序、选择、循环三种基本结构。构。3、模块化设计是指把一个大程序按人们能理解的大小规模进行分解。划分、模块化设计是指把一个大程序按人们能理解的大小规模进行分解。划分模块的基本原则是使每个模块
43、都易于理解。在按功能划分模块时，要求模块的基本原则是使每个模块都易于理解。在按功能划分模块时，要求各模块功能尽量单一，各模块之间的联系尽量的少。各模块功能尽量单一，各模块之间的联系尽量的少。4、客观世界是由实体及其联系所组成的。客观世界中的实体称为问题域的、客观世界是由实体及其联系所组成的。客观世界中的实体称为问题域的对象。对象。5、类描述的是具有相似性质一组对象。一个对象称为类的实例。、类描述的是具有相似性质一组对象。一个对象称为类的实例。6、允许作用于某个对象上的各种操作称为方法。、允许作用于某个对象上的各种操作称为方法。7、消息是用来请求对象执行某一处理或回答某些信息的要求。、消息是用来
44、请求对象执行某一处理或回答某些信息的要求。8、继承是表示类之间的相似性的一种机制。、继承是表示类之间的相似性的一种机制。9、封装是一种信息隐蔽机制，目的是将对象的使用者与对象的设计者分开。、封装是一种信息隐蔽机制，目的是将对象的使用者与对象的设计者分开。用户只需了解对象封装界面上的信息，不必知道内部的具体细节。用户只需了解对象封装界面上的信息，不必知道内部的具体细节。寐棚彤昔刮薯最腑今南禹迄苗炯犬瞄群菌屡夫陈养遏凝淬被刷葬胸尽咸花全国计算机等级考试全国计算机等级考试30软件工程基础软件工程基础关键考点关键考点软件定义与特点软件定义与特点软件开发过程的过程化原则软件开发过程的过程化原则结构化分析
45、方法结构化分析方法结构化设计方法结构化设计方法软件测试技术与方法软件测试技术与方法程序调试基本概念程序调试基本概念棒镐墓塌塑姥棕县概饿闯池结凋氨驰崇蘸遂抿皑铅绕滩祥吓幻朱汹卷错招全国计算机等级考试全国计算机等级考试31软件工程基础软件工程基础软件工程基本概念软件工程基本概念1、软件、软件软件是包括程序、数据及相关文档的完整集合。软件是包括程序、数据及相关文档的完整集合。2、软件的特点、软件的特点抽象性抽象性可大量拷贝可大量拷贝无磨损及老化问题无磨损及老化问题受计算机系统限制受计算机系统限制(移植问题移植问题)复杂性高成本昂贵复杂性高成本昂贵开发过程涉及诸多社会因素开发过程涉及诸多社会因素3、软
46、件工程、软件工程软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。文档、实践标准和工序。三个要素三个要素方法：完成软件工程项目的技术手段。方法：完成软件工程项目的技术手段。工具：支持软件的开发、管理、文档生成。工具：支持软件的开发、管理、文档生成。过程：支持软件开发各个环节的管理、控制。过程：支持软件开发各个环节的管理、控制。目标目标：在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可适应性、可追踪性、可互操作
47、性满足用户要求的软件产品。可维护性、可适应性、可追踪性、可互操作性满足用户要求的软件产品。抨炼艘匀跃婴娶柞做哺棱姐犀搂吝统氮念滞煤衣命鸣冯扇询袜瘩洛轮拆追全国计算机等级考试全国计算机等级考试32软件工程基础软件工程基础软件开发过程的过程化原则软件开发过程的过程化原则1、软件工程过程、软件工程过程 为获得软件产品，在软件工具支持下的一系列软件工程活动。为获得软件产品，在软件工具支持下的一系列软件工程活动。Plan软件规格说明。软件规格说明。Do软件开发。软件开发。Check软件确认。软件确认。Action 软件演进。软件演进。 使用适当的资源，为开发软件进行的一组开发活动，在过程结束时将使用适当
48、的资源，为开发软件进行的一组开发活动，在过程结束时将用户要求转化为软件产品。用户要求转化为软件产品。软件工程过程应确定软件工程过程应确定方法使用的顺序方法使用的顺序、要求交付的文档资料要求交付的文档资料、为保证质为保证质量与适应变化所需要的管理量与适应变化所需要的管理、软件开发各阶段要完成的任务软件开发各阶段要完成的任务。2、软件生命周期、软件生命周期 定义阶段定义阶段可行性研究及项目计划可行性研究及项目计划需求分析需求分析 开发阶段开发阶段概要设计概要设计详细设计详细设计实现实现测试测试 维护阶段维护阶段使用使用维护维护退役退役漆有陌孜渺郡嘎癸者立奄峦综径蚌涪糠离贬惶揽戍沪嫂泌善葵利谷酿祥弥
49、全国计算机等级考试全国计算机等级考试33软件工程基础软件工程基础结构化分析方法结构化分析方法在系统分析阶段，结构化分析方法用来对系统进行逻辑设计。在系统分析阶段，结构化分析方法用来对系统进行逻辑设计。1、需求分析、需求分析需求分析的任务是发现需求、求精、建模和定义需求。需求分析的任务是发现需求、求精、建模和定义需求。 常见的需求分析方法：常见的需求分析方法：结构化分析方法结构化分析方法 面向对象的分析方法面向对象的分析方法2、结构化分析方法、结构化分析方法 结构化分析就是使用结构化分析就是使用数据流图数据流图(DFD)、数据字典数据字典(DD)、结构化英语结构化英语、判判定表定表和和判定树判定
50、树等工具，来建立一种被称为结构化规格说明的目标文档。等工具，来建立一种被称为结构化规格说明的目标文档。 结构化分析方法的实质是着眼于数据流的、自顶向下逐层分解的、建立结构化分析方法的实质是着眼于数据流的、自顶向下逐层分解的、建立系统的处理流程，它以数据流图和数据字典为主要工具，建立系统的逻系统的处理流程，它以数据流图和数据字典为主要工具，建立系统的逻辑模型。辑模型。3、 软件需求规格说明书软件需求规格说明书是需求分析阶段的最后成果，是软件开发的重要文档之一。是需求分析阶段的最后成果，是软件开发的重要文档之一。软件需求规格说明书把软件计划中确定的软件范围加以展开，制定出完软件需求规格说明书把软件
51、计划中确定的软件范围加以展开，制定出完整的信息描述、详细的功能说明、恰当的检验标准、其他与要求有关的整的信息描述、详细的功能说明、恰当的检验标准、其他与要求有关的信息。信息。悄数帐戏魁切孕辐昂颓红热兴欺肥兽血锦擂单衅扒决卞棺幸抱茧畏断影铲全国计算机等级考试全国计算机等级考试34软件工程基础软件工程基础结构化设计方法结构化设计方法1、软件设计、软件设计软件设计是把软件需求转换为软件表示的过程。软件设计是把软件需求转换为软件表示的过程。从技术角度：软件设计包括结构设计、数据设计、接口设计、过程设计。从技术角度：软件设计包括结构设计、数据设计、接口设计、过程设计。从工程角度：软件设计包括概要设计、详
52、细设计。从工程角度：软件设计包括概要设计、详细设计。软件设计的基本原理包括：抽象、模块化、信息隐蔽、模块独立性软件设计的基本原理包括：抽象、模块化、信息隐蔽、模块独立性2、概要设计、概要设计概要设计的基本任务：概要设计的基本任务：系统结构设计系统结构设计数据结构设计数据结构设计编写设计文档编写设计文档 设计文档评审设计文档评审结构图是软件结构设计的常用工具。结构图是软件结构设计的常用工具。3、详细设计、详细设计详细设计的任务，是为软件结构图中的每一个模块确定算法和局部数据详细设计的任务，是为软件结构图中的每一个模块确定算法和局部数据结构，用某种选定的工具表示算法和数据结构的细节。结构，用某种选
53、定的工具表示算法和数据结构的细节。常见的设计工具：常见的设计工具：图形工具：流程图、图形工具：流程图、N - S、PAD、HIPO表格工具：判定表表格工具：判定表语言工具：语言工具：PDL(伪码伪码)靳暑痘琶掂球洗蝉李抠拳乳姓蛋棉掇建成沟迄碧柯律霸饭肠翁疾剪百得油全国计算机等级考试全国计算机等级考试35软件工程基础软件工程基础软件测试软件测试1、测试、测试软件测试的目标是在精心控制的环境下执行程序，以发现程序中的错误，软件测试的目标是在精心控制的环境下执行程序，以发现程序中的错误，给出程序可靠性的鉴定。给出程序可靠性的鉴定。测试不是为了证明程序是正确的，目的是设法暴露程序中的错误和缺陷。测试不
54、是为了证明程序是正确的，目的是设法暴露程序中的错误和缺陷。测试只能说明程序有错，不能证明程序无错。程序不能测试只能说明程序有错，不能证明程序无错。程序不能100%可靠。可靠。2、测试方法、测试方法程序的静态分析程序的静态分析程序的动态分析程序的动态分析自动测试工具自动测试工具3、测试层次、测试层次模块测试模块测试(单元测试单元测试)整体测试整体测试(集成测试集成测试)又分为又分为 功能测试功能测试 和和 验收测试验收测试 两种。两种。4、白盒法、白盒法根据对程序内部逻辑结构的分析来导出测试用例。根据对程序内部逻辑结构的分析来导出测试用例。5、黑盒法、黑盒法不考虑程序的内部结构特征，根据程序功能
55、导出测试用例。不考虑程序的内部结构特征，根据程序功能导出测试用例。涅陪帝什核漂凸幻瀑侄篇芋熙绰伏朽趋岩约乐弱暇园力寝币擂郧厕斩募缀全国计算机等级考试全国计算机等级考试36软件工程基础软件工程基础程序调试程序调试1、调试与测试、调试与测试 测试的目的是发现错误，评价可靠性；调试的目的是发现错误的位置，测试的目的是发现错误，评价可靠性；调试的目的是发现错误的位置，改正发现的错误。改正发现的错误。 测试揭示设计人员的过失，由非设计人员承担；调试帮助设计人员改正错误，测试揭示设计人员的过失，由非设计人员承担；调试帮助设计人员改正错误，由设计人员自己承担。由设计人员自己承担。 测试是机械的、强制的、严格
56、的、可预测的；调试要求随机应变、联想、经测试是机械的、强制的、严格的、可预测的；调试要求随机应变、联想、经验、智力，并要求自主地完成。验、智力，并要求自主地完成。 测试发现的错误可立即进行调试改正，然后还必须再进行测试。测试发现的错误可立即进行调试改正，然后还必须再进行测试。 调试用例与测试用例可以一致也可以不一致。调试用例与测试用例可以一致也可以不一致。2、调试方法、调试方法 强行排错法强行排错法 回溯法回溯法 原因排除法原因排除法审祈篱潞菲冗贾仲隶卧蘸壶笆鹿讲簿孕剩擒深烽健狈聪寺贤攀久容宵即轧全国计算机等级考试全国计算机等级考试37软件工程基础软件工程基础本章重点本章重点1、软件生命周期分
57、为三个时期共八个阶段：、软件生命周期分为三个时期共八个阶段：软件定义期：问题定义、可行性研究、需求分析。软件定义期：问题定义、可行性研究、需求分析。软件开发期：系统设计、详细设计、编码、测试。软件开发期：系统设计、详细设计、编码、测试。软件维护期：运行维护。软件维护期：运行维护。2、在系统分析阶段，结构化分析方法用来对系统进行逻辑设计，此时不考虑物理实、在系统分析阶段，结构化分析方法用来对系统进行逻辑设计，此时不考虑物理实现的问题，而只考虑现的问题，而只考虑“做什么做什么”的问题，系统的物理设计的问题，系统的物理设计(“如何做如何做”)的问题留的问题留在系统设计阶段用结构化设计方法来完成。在系
58、统设计阶段用结构化设计方法来完成。3、数据流图有两种典型的结构形式：变换型、事务型。、数据流图有两种典型的结构形式：变换型、事务型。4、评价模块的独立性的标准有两个：、评价模块的独立性的标准有两个：耦合性：表明两个模块间联系的强弱。耦合性：表明两个模块间联系的强弱。内聚性：表明模块内部联系是否紧密。内聚性：表明模块内部联系是否紧密。内聚性要强，偶合性要弱。内聚性要强，偶合性要弱。5、软件测试是在精心控制的环境下执行程序，发现程序中的错误，给出程序可靠性、软件测试是在精心控制的环境下执行程序，发现程序中的错误，给出程序可靠性的鉴定。的鉴定。6、测试是程序执行的过程，目的在于发现错误；一个好的测试
59、在于能发现至今未能、测试是程序执行的过程，目的在于发现错误；一个好的测试在于能发现至今未能发现的错误，一个成功的测试是发现了至今未发现的错误。发现的错误，一个成功的测试是发现了至今未发现的错误。7、测试发现错误后，可进行调试；调试后的程序还应再测试，以检验调试效果。、测试发现错误后，可进行调试；调试后的程序还应再测试，以检验调试效果。郊戊扎绊岿警蘸雨近渠雷贤导历燕凝蚜舒媒清禁池炒晾汀衫渗情幕授纽揍全国计算机等级考试全国计算机等级考试38数据库设计基础数据库设计基础关键考点关键考点数据库系统基本概念数据库系统基本概念数据模型数据模型撩甲劝激筐墒牟岿咬割北诀误赋数坊桌朵玉套藤株化嚎鱼翁询斯芭焰斋科
60、全国计算机等级考试全国计算机等级考试39数据库设计基础数据库设计基础数据库系统的基本概念数据库系统的基本概念1、数据库、数据库 DB是数据的集合，具有统一的结构形式并存放于统一的存储介质中，是多是数据的集合，具有统一的结构形式并存放于统一的存储介质中，是多种应用数据的集成，可被各个应用程序所共享。种应用数据的集成，可被各个应用程序所共享。2、数据库管理系统、数据库管理系统 DBMS数据库的管理机构，系统软件，负责数据组织、操纵、维护、控制、保数据库的管理机构，系统软件，负责数据组织、操纵、维护、控制、保护等。护等。为数据库构作模式为数据库构作模式为数据模式的实现提供方法和手段为数据模式的实现提
61、供方法和手段为用户使用提供查询、插入、修改、删除等功能为用户使用提供查询、插入、修改、删除等功能提供对数据库中数据的多种服务功能提供对数据库中数据的多种服务功能(复制、重组、检测等复制、重组、检测等)。3、DBMS提供的语言提供的语言数据定义语言数据定义语言数据操纵语言数据操纵语言数据控制语言数据控制语言拭炉编炳拒瓷缸少弱践瑰溜术绦饼少冈戴爽坏淑吹备鄙偷搐惺恩遮矛钟置全国计算机等级考试全国计算机等级考试40数据库设计基础数据库设计基础数据库系统的基本概念数据库系统的基本概念4、数据库系统、数据库系统 DBS由由DB、DBMS、数据库管理员、数据库管理员(DBA)、硬件平台、软件平台组成。、硬件
62、平台、软件平台组成。5、数据库系统的基本特点、数据库系统的基本特点数据的集成性数据的集成性数据的高共享性低冗余性数据的高共享性低冗余性数据的独立性数据的独立性数据统一管理和控制数据统一管理和控制6、数据库系统的三级模式、数据库系统的三级模式概念模式概念模式：数据库中全局数据的逻辑描述，与具体的软硬件环境无关。数据库中全局数据的逻辑描述，与具体的软硬件环境无关。外模式外模式：也叫用户模式，是用户的数据视图。也叫用户模式，是用户的数据视图。内模式内模式：也叫物理模式，描述数据库中数据的存储结构和存取方式。也叫物理模式，描述数据库中数据的存储结构和存取方式。吠令酬恨兄顺臻似历伪晤嚷照近瓮表拙孟褐具射
63、晋笋爪友占穆勇咬佑良恿全国计算机等级考试全国计算机等级考试41数据库设计基础数据库设计基础数据模型数据模型1、三种不同应用层次的数据模型、三种不同应用层次的数据模型概念模型概念模型：概念数据模型，面向客观世界、面向用户，与具体的概念数据模型，面向客观世界、面向用户，与具体的DBMS无关。无关。数据模型数据模型：逻辑数据模型，面向逻辑数据模型，面向DBS的模型，着重于数据库系统的实现。的模型，着重于数据库系统的实现。物理模型物理模型：物理数据模型，面向计算机系统，是数据模型的物理表示。物理数据模型，面向计算机系统，是数据模型的物理表示。2、实体集之间的联系、实体集之间的联系一对一一对一一对多或多
64、对一一对多或多对一多对多多对多3、E - R模型的图示法模型的图示法实体集表示法实体集表示法：在：在E - R图中用矩形表示实体集，矩形内注明实体集名称。图中用矩形表示实体集，矩形内注明实体集名称。属性表示法属性表示法：在：在E - R图中用椭圆，椭圆中注明属性名称。图中用椭圆，椭圆中注明属性名称。联系表示法联系表示法：在：在E - R图中用菱形表示联系，菱形中注明联系名称。图中用菱形表示联系，菱形中注明联系名称。实体集与属性之间的连接关系实体集与属性之间的连接关系：在：在E - R图中用连接两个图形的无向线段表示。图中用连接两个图形的无向线段表示。液哈递蜜携前凶猪价异贴赁踌看钞脂妄帽培屑骋综
65、轴克瘤井呐缠阎岳够胚全国计算机等级考试全国计算机等级考试42数据库设计基础数据库设计基础数据模型数据模型4、层次模型、层次模型 层次模型的基本结构是树形结构。层次模型的基本结构是树形结构。5、网状模型、网状模型网状模型是一个不加任何条件限制的无向图。网状模型是一个不加任何条件限制的无向图。6、关系模型、关系模型关系模型用关系模型用二维表二维表表示关系。表示关系。二维表有二维表有表框架表框架(关系模式关系模式)和表和表元组元组组成。组成。表框架由表框架由n个命名的个命名的属性属性组成。组成。属性的取值范围称为属性的取值范围称为值域。值域。二维表中能够二维表中能够唯一标识唯一标识元组的最小属性集成
66、为元组的最小属性集成为“键键”(关键字关键字)。二维表中可能有若干键，称为二维表中可能有若干键，称为侯选键侯选键(侯选关键字侯选关键字) 。侯选键中选择作为用户使用的称为侯选键中选择作为用户使用的称为主键主键(主关键字主关键字) 。关系框架和关系元组构成关系框架和关系元组构成关系关系。朋纲徊碉仟钮棉狮苹撤喷卉连沙隧嘎腰漓膳毋咯巳扬业宽庄篙嘘侵侗气蛾全国计算机等级考试全国计算机等级考试43数据库设计基础数据库设计基础关系代数关系代数1、关系模型的基本操作、关系模型的基本操作插入插入删除删除修改修改查询查询2、基本运算、基本运算并运算并运算(插入插入)差运算差运算(删除删除)投影投影(查询查询)选
67、择选择(查询查询) 笛卡尔积笛卡尔积(查询查询)交运算交运算除运算除运算连接运算连接运算(有条件的笛卡尔积有条件的笛卡尔积) 自然连接运算自然连接运算(公共域等值连接公共域等值连接)立茂粉侍畦迎导做色咸撅胀秘符腺昨筋容夕虏挣与琅狄侧们助冠场速菱塌全国计算机等级考试全国计算机等级考试44数据库设计基础数据库设计基础数据库设计与管理数据库设计与管理1、数据库设计、数据库设计数据库设计的基本任务是根据用户的信息需求、处理需求、软硬件环境数据库设计的基本任务是根据用户的信息需求、处理需求、软硬件环境设计出数据模式。设计出数据模式。在数据库设计中有两种方法：在数据库设计中有两种方法：面向数据的方法面向数
68、据的方法以信息需求为主兼顾处理需求以信息需求为主兼顾处理需求。面向过程的方法面向过程的方法以处理需求为主兼顾信息需求以处理需求为主兼顾信息需求。数据库设计中一般采用生命周期法。数据库设计中一般采用生命周期法。需求分析需求分析：用户需求调查，产生需求说明书。用户需求调查，产生需求说明书。概念设计概念设计：分析数据的内在关联，产生概念数据模型。分析数据的内在关联，产生概念数据模型。逻辑设计逻辑设计：将将E R图转换为关系模式，产生逻辑数据模型。图转换为关系模式，产生逻辑数据模型。物理设计物理设计：调整内部结构选择存取路径，产生数据库内模式。调整内部结构选择存取路径，产生数据库内模式。2、数据库管理
69、、数据库管理包括：包括：数据库建立数据库建立数据库调整数据库调整数据库重组数据库重组安全性控制安全性控制完整性控制完整性控制故障恢复故障恢复运行监控运行监控宵峡死吨哨乃债博凛荧持张渠齐框透根吧阮焰镍温陵戍肇奠兄掖逼外文烽全国计算机等级考试全国计算机等级考试45数据库设计基础数据库设计基础本章重点本章重点1、数据管理技术的发展分为三个阶段：、数据管理技术的发展分为三个阶段：人工管理、文件管理、数据库管理。人工管理、文件管理、数据库管理。2、数据库系统是由操作系统、数据库管理系统和应用程序在一定的硬件支、数据库系统是由操作系统、数据库管理系统和应用程序在一定的硬件支持下所构成的。数据库管理系统持下
70、所构成的。数据库管理系统(DBMS)是整个数据库系统的核心，它对是整个数据库系统的核心，它对数据库中的数据进行管理，还作为用户应用与数据库之间的接口。数据库中的数据进行管理，还作为用户应用与数据库之间的接口。3、数据库技术的根本目标是要解决数据的共享问题。、数据库技术的根本目标是要解决数据的共享问题。4、数据库技术的特点之一是数据的独立性。数据的物理独立性表示数据的、数据库技术的特点之一是数据的独立性。数据的物理独立性表示数据的物理结构改变不会影响数据库的逻辑结构，不致引起应用程序的变化。物理结构改变不会影响数据库的逻辑结构，不致引起应用程序的变化。数据的逻辑独立性表示数据库总体逻辑结构改变不
71、会影响局部逻辑结构，数据的逻辑独立性表示数据库总体逻辑结构改变不会影响局部逻辑结构，基于局部逻辑结构的应用程序也不必修改。基于局部逻辑结构的应用程序也不必修改。5、实体与实体之间的联系归结为三类：、实体与实体之间的联系归结为三类：一对一联系、一对多联系、多对多联系。一对一联系、一对多联系、多对多联系。6、在数据库系统中，由于采用的数据模型不同，响应的数据库管理系统、在数据库系统中，由于采用的数据模型不同，响应的数据库管理系统(DBMS)也不同。目前常用的有：层次模型、网状模型、关系模型。也不同。目前常用的有：层次模型、网状模型、关系模型。紫高洛韵权煌鹊腥液雾屹详砍专砂宫湘剐泵郑价龄垛笺笑衡席哪
72、蜕还皖疑全国计算机等级考试全国计算机等级考试46数据库设计基础数据库设计基础本章重点本章重点7、网状模型和层次模型都属于格式化模型。所谓格式化模型，是指在建立、网状模型和层次模型都属于格式化模型。所谓格式化模型，是指在建立数据模型时，根据应用的需要，事先将数据之间的逻辑关系固定下来数据模型时，根据应用的需要，事先将数据之间的逻辑关系固定下来(先先对数据的逻辑结构进行设计使其结构化对数据的逻辑结构进行设计使其结构化)。8、在关系模型中，把数据看成二维表，每个二维表是一个关系。表中的列、在关系模型中，把数据看成二维表，每个二维表是一个关系。表中的列成为属性成为属性(记录的数据项记录的数据项)，表中
73、的行称为元组，相当于记录。，表中的行称为元组，相当于记录。9、选择运算是在关系中选择满足条件的元组构成新的关系，该新关系是原、选择运算是在关系中选择满足条件的元组构成新的关系，该新关系是原关系的一个子集，它在关系的行方向上进行运算。关系的一个子集，它在关系的行方向上进行运算。10、投影运算是在关系的某些域上进行操作，它是在关系的列方向上进行、投影运算是在关系的某些域上进行操作，它是在关系的列方向上进行运算。运算。11、数据库设计是指在已有数据库管理系统的基础上建立数据库的过程。、数据库设计是指在已有数据库管理系统的基础上建立数据库的过程。12、数据库设计分为需求分析、概念结构设计、逻辑结构设计、物理结构、数据库设计分为需求分析、概念结构设计、逻辑结构设计、物理结构设计等阶段。设计等阶段。13、E-R图图(实体实体-联系图联系图)是设计概念模型的有力工具。是设计概念模型的有力工具。14、数据字典是数据库的信息系统，是由关于数据库的数据描述信息组成、数据字典是数据库的信息系统，是由关于数据库的数据描述信息组成的库，也称为描述数据库。的库，也称为描述数据库。寻梭谆肯绘梅锭揉踊褐栽杰柜乌充晃巍誉吧托碎昆屎皋汹舅萍偶啸森砰雷全国计算机等级考试全国计算机等级考试47
