二级公共基础知识课件.ppt

二二 级级 公公 共共 基基 础础 知知 识识 授课老师：授课老师：潘英花潘英花授课时间：授课时间：2011 2011 年年 3 3 月月 一、涉及面广，但难度小一、涉及面广，但难度小一、涉及面广，但难度小一、涉及面广，但难度小 公共基础知识考题特点及复习建议公共基础知识考题特点及复习建议公共基础知识考题特点及复习建议公共基础知识考题特点及复习建议 计算机等级二级理论考试中有关公共知识部分计算机等级二级理论考试中有关公共知识部分计算机等级二级理论考试中有关公共知识部分计算机等级二级理论考试中有关公共知识部分的题目共有的题目共有的题目共有的题目共有15151515道，涉及道，涉及道，涉及道，涉及算法及数据结构算法及数据结构算法及数据结构算法及数据结构、程序设计基础程序设计基础程序设计基础程序设计基础、软件工程基础软件工程基础软件工程基础软件工程基础和和和和数据库设计基础数据库设计基础数据库设计基础数据库设计基础等四门学科，但是从整等四门学科，但是从整等四门学科，但是从整等四门学科，但是从整体上分析，本次考试中的考核内容的难度不大，考点也体上分析，本次考试中的考核内容的难度不大，考点也体上分析，本次考试中的考核内容的难度不大，考点也体上分析，本次考试中的考核内容的难度不大，考点也相对集中些。相对集中些。相对集中些。相对集中些。二、考核重点为基本概念、基本方法二、考核重点为基本概念、基本方法二、考核重点为基本概念、基本方法二、考核重点为基本概念、基本方法 和基本运算和基本运算和基本运算和基本运算 计算机等级二级理论考试中涉及的计算机等级二级理论考试中涉及的计算机等级二级理论考试中涉及的计算机等级二级理论考试中涉及的题目都是题目都是题目都是题目都是基本概念基本概念基本概念基本概念、基本方法基本方法基本方法基本方法和和和和基本运算基本运算基本运算基本运算，考核以概念和认识性内容为主，理解性、应考核以概念和认识性内容为主，理解性、应考核以概念和认识性内容为主，理解性、应考核以概念和认识性内容为主，理解性、应用性内容极少。用性内容极少。用性内容极少。用性内容极少。三、考核重点是数据结构和算法三、考核重点是数据结构和算法三、考核重点是数据结构和算法三、考核重点是数据结构和算法 以下是对以往二级理论以下是对以往二级理论以下是对以往二级理论以下是对以往二级理论考试考试考试考试的大概统的大概统的大概统的大概统计：计：计：计：v 算法及数据结构算法及数据结构算法及数据结构算法及数据结构：50%50%50%50%v 程序设计基础程序设计基础程序设计基础程序设计基础：12.5%12.5%12.5%12.5%v 软件工程基础软件工程基础软件工程基础软件工程基础：18.75%18.75%18.75%18.75%v 数据库设计基础数据库设计基础数据库设计基础数据库设计基础：18.75%18.75%18.75%18.75%四、六点复习及应试建议四、六点复习及应试建议四、六点复习及应试建议四、六点复习及应试建议vv复习的关键是复习的关键是复习的关键是复习的关键是考生必须准确判断和掌握常见考点考生必须准确判断和掌握常见考点考生必须准确判断和掌握常见考点考生必须准确判断和掌握常见考点vv 考生必须在准确把握知识点的基础上，考生必须在准确把握知识点的基础上，考生必须在准确把握知识点的基础上，考生必须在准确把握知识点的基础上，学会把学会把学会把学会把“知识点知识点知识点知识点”连连连连 成成成成“知识链知识链知识链知识链”，并把，并把，并把，并把“知识链知识链知识链知识链”织成织成织成织成“知识网知识网知识网知识网”vv 考生一定考生一定考生一定考生一定不要采取题海战术不要采取题海战术不要采取题海战术不要采取题海战术，更，更，更，更不能在知道正确答案的同时不能在知道正确答案的同时不能在知道正确答案的同时不能在知道正确答案的同时 记住三个错误答案记住三个错误答案记住三个错误答案记住三个错误答案vv 考生考生考生考生不要太追求灵活掌握该部分的内容不要太追求灵活掌握该部分的内容不要太追求灵活掌握该部分的内容不要太追求灵活掌握该部分的内容，最好经历一个，最好经历一个，最好经历一个，最好经历一个“先死先死先死先死 后活、熟能生巧后活、熟能生巧后活、熟能生巧后活、熟能生巧”的过程，这是多数考生常犯的另一种错误的过程，这是多数考生常犯的另一种错误的过程，这是多数考生常犯的另一种错误的过程，这是多数考生常犯的另一种错误vv 最后给大家一个最后给大家一个最后给大家一个最后给大家一个答题技巧答题技巧答题技巧答题技巧：“会就会，不会就不会会就会，不会就不会会就会，不会就不会会就会，不会就不会”，不要拖不要拖不要拖不要拖 时间，要考虑成本时间，要考虑成本时间，要考虑成本时间，要考虑成本/效果的关系，为后面的题目提供时间效果的关系，为后面的题目提供时间效果的关系，为后面的题目提供时间效果的关系，为后面的题目提供时间。本本本本 课课课课 程程程程 授授授授 课课课课 安安安安 排排排排 共讲授共讲授共讲授共讲授 7 7 7 7个学时，具体安排如下：个学时，具体安排如下：个学时，具体安排如下：个学时，具体安排如下：vv 本周周六（本周周六（本周周六（本周周六（3 3 3 3月月月月12121212日）上午（日）上午（日）上午（日）上午（1-1-1-1-2 2 2 2节）：节）：节）：节）：算法与数据结构算法与数据结构算法与数据结构算法与数据结构vv本周周六（本周周六（本周周六（本周周六（3 3 3 3月月月月12121212日）上午（日）上午（日）上午（日）上午（3-3-3-3-5 5 5 5节）节）节）节）：软件工程与程序设计基础软件工程与程序设计基础软件工程与程序设计基础软件工程与程序设计基础vv 本周周周六（本周周周六（本周周周六（本周周周六（3 3 3 3月月月月1 1 1 12 2 2 2日）下午（日）下午（日）下午（日）下午（6-76-76-76-7节）节）节）节）：数据库系统数据库系统数据库系统数据库系统1 1、了解算法的基本概念和一些常用的算法，学会计算算法的时间复杂度；、了解算法的基本概念和一些常用的算法，学会计算算法的时间复杂度；2 2、掌握数据结构的基本概念，并了解数据的逻辑结构和存储结构，学会利、掌握数据结构的基本概念，并了解数据的逻辑结构和存储结构，学会利 用图形的方式表示数据结构用图形的方式表示数据结构 ；学学学学习习习习目目目目标标标标与与与与要要要要求求求求 算法与数据结构：算法与数据结构：算法与数据结构：算法与数据结构：3 3、了解线性表的基本概念，并掌握线性表的顺序存储结构以及顺序存储的、了解线性表的基本概念，并掌握线性表的顺序存储结构以及顺序存储的 线性表的基本运算；线性表的基本运算；4 4、了解栈和队列的基本概念，并掌握它们的基本运算；、了解栈和队列的基本概念，并掌握它们的基本运算；5 5、了解线性链表的基本概念，并掌握线性链表的基本运算，同时，了解循、了解线性链表的基本概念，并掌握线性链表的基本运算，同时，了解循 环链表的基本概念和基本操作；环链表的基本概念和基本操作；6 6、理解树的概念，尤其是二叉树的基本概念和相关性质，掌握二叉树的存、理解树的概念，尤其是二叉树的基本概念和相关性质，掌握二叉树的存 储结构和遍历技术；储结构和遍历技术；7 7、掌握查找技术，学会利用顺序查找和二分查找在数列中查找指定的数据；、掌握查找技术，学会利用顺序查找和二分查找在数列中查找指定的数据；8 8、学会利用相关的排序技术实现无序数列的排序操作。、学会利用相关的排序技术实现无序数列的排序操作。1 1、了解软件工程的基本概念；、了解软件工程的基本概念；2 2、了解软件工程过程与软件的生命周期，以及软件工程的目标和原则；、了解软件工程过程与软件的生命周期，以及软件工程的目标和原则；学学学学习习习习目目目目标标标标与与与与要要要要求求求求 软件工程软件工程软件工程软件工程：3 3、了解利用结构化分析法进行软件工程中的需求分析的方法，并了解需、了解利用结构化分析法进行软件工程中的需求分析的方法，并了解需 求分析的方法和需要完成的任务；求分析的方法和需要完成的任务；4 4、了解数据流图的使用方法；、了解数据流图的使用方法；5 5、了解如何利用结构化设计方法进行软件设计，并了解软件设计的一些、了解如何利用结构化设计方法进行软件设计，并了解软件设计的一些 常用工具；常用工具；6 6、了解软件测试的目的和方法，以及软件测试的准则，了解常用的软件、了解软件测试的目的和方法，以及软件测试的准则，了解常用的软件 测试方法的区别和各自的功能与特点；测试方法的区别和各自的功能与特点；7 7、了解程序调试的方法和原则、了解程序调试的方法和原则 。1 1、了解程序设计的方法，以及程序设计风格确立的一些因素，掌握程序、了解程序设计的方法，以及程序设计风格确立的一些因素，掌握程序 设计的基本规则；设计的基本规则；2 2、了解结构化程序设计的基本原则，掌握结构化程序设计的基本结构与特点、了解结构化程序设计的基本原则，掌握结构化程序设计的基本结构与特点;学学学学习习习习目目目目标标标标与与与与要要要要求求求求 程序设计基础程序设计基础程序设计基础程序设计基础：3 3、了解面向对象的程序设计方法，并理解面向对象方法的一些基本概念。、了解面向对象的程序设计方法，并理解面向对象方法的一些基本概念。数据库系统数据库系统数据库系统数据库系统：1 1、了解数据库系统的基本概念，以及数据库系统的发展；、了解数据库系统的基本概念，以及数据库系统的发展；2 2、了解数据模型的基本概念，并对、了解数据模型的基本概念，并对E-RE-R模型、层次模型、网状模型和关系模型模型、层次模型、网状模型和关系模型 进行了解，并掌握关系模型的数据结构、关系的操作和数据约束等知识；进行了解，并掌握关系模型的数据结构、关系的操作和数据约束等知识；3 3、了解关系模型的基本操作，掌握关系模型的基本运算及扩充运算；、了解关系模型的基本操作，掌握关系模型的基本运算及扩充运算；4 4、了解数据库的设计与管理，掌握数据库设计的几个阶段的方法和特点。、了解数据库的设计与管理，掌握数据库设计的几个阶段的方法和特点。程程程程序序序序设设设设计计计计基基基基本本本本概概概概念念念念一、一、计算机工作原理计算机工作原理 通过工作原理了解，熟悉计算机内部执行功能的基本意义。为理解程序打下基础，特别理解计算机是机器。二、二、程序的定义程序的定义v 指令的集合。（解释指令）v 通过硬件控制系统自动完成某一功能。v 通过一系列代码实现。程程程程序序序序设设设设计计计计基基基基本本本本概概概概念念念念三、三、程序怎样执行、如何编写程序程序怎样执行、如何编写程序v计算机本身仅能识别二进制代码“0”、“1”。v编程最直接、最低级的就是机器语言。v为解决机器语言难理解、记忆等问题。出现符号语言。v为使编程接近自然语言，出现高级语言。如C、PASCAL、FORTRAN等。v为配合高级语言编程，出现了开发工具，提高效率、减轻劳动量。如VB、VC、PB、Delphi、VFP等。因此VFP不是编程语言。程程程程序序序序设设设设计计计计基基基基本本本本概概概概念念念念v 不管什么形式编写代码，最终都应将代码翻译成机器语言，这就是编译程序的工作。不同的语言有不同的编译器。v 程序控制是一种逻辑控制。因此，严谨的逻辑思维是一个 程序员必备的基本素质。v 用程序实现某一功能。有许多方法。具体用哪种完全取决 于程序员个人的思维方式。因此，程序是脑力劳动的结晶，从某种意义上，编程又是一门艺术。v 程序的特殊性决定了程序的复杂性，且与实现功能的复杂 性密切相关成正比。因此为使复杂的、智力的编程工作规 范化、科学化，便出现了各种编程设计方法。如结构化编 程方法、面向对象的程序设计方法等。程程程程序序序序设设设设计计计计基基基基本本本本概概概概念念念念v 不管用什么方法编程，不管编程者智力程度如何，不管 采用什么样的编程语言和方法，程序最终完成的功能稳 定、可靠、实用、易维护和安全等是程序的最终目标，也是程序员的追求。v 程序设计是一个复杂艰巨的过程。编写代码仅是程序设 计的一部分。必须先有思想，再有方法，然后才是编写 代码，且要经过许多反复，不可急功近利。程程程程序序序序设设设设计计计计基基基基本本本本概概概概念念念念四、四、程序设计语言或工具程序设计语言或工具v 程序设计语言指的是用来编写程序的语言。v 人与计算机交流要使用语言，以便让计算机工作，计算 机也通过语言把结果告诉用计算机的人“人机对 话”。v 人与计算机交流的语言非平常人与人之间交流的语言，是专门的语言程序设计语言。v 程序设计语言是计算机系统软件的重要组成部分。程程程程序序序序设设设设计计计计基基基基本本本本概概概概念念念念v 执行程序设计的语言有很多，可分高级语言和低级语言，区别在于接近自然语言的程度v 高级语言一般与具体的计算机硬件无关，比较接近人类 自然语言的语法习惯及数学表达形式。v 用高级语言编写的源程序不能被机器直接执行，需通过 编译或解释程序的翻译才可被机器执行（机器语言）。四、四、程序设计语言或工具（续）程序设计语言或工具（续）算算算算法法法法与与与与数数数数据据据据结结结结构构构构一、算法（一、算法（algorithm）1 1、算法的基本概念、算法的基本概念 算法是对特定问题求解步骤的一种准确而完整的描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。它是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。*：算法不等于程序，也不等于计算方法。算法具有有穷性有穷性、确定性确定性、可行性可行性、输入输入和输出输出（拥有足够的情报）等个重要特性。算法的基本特征（1 1）可行性。可行性。针对实际问题而设计的算法，执行后能够针对实际问题而设计的算法，执行后能够得到满意的结果。得到满意的结果。（2 2）确定性。确定性。每一条指令的含义明确，无二义性。并且每一条指令的含义明确，无二义性。并且在任何条件下，算法只有唯一的一条执行路径，即在任何条件下，算法只有唯一的一条执行路径，即相同的相同的输入只能得出相同的输出。输入只能得出相同的输出。（3 3）有穷性。有穷性。算法必须在有限的时间内完成。有两重含算法必须在有限的时间内完成。有两重含义，一是算法中的操作步骤为有限个，二是每个步骤都能义，一是算法中的操作步骤为有限个，二是每个步骤都能在有限时间内完成。在有限时间内完成。（4 4）拥有足够的情报。拥有足够的情报。算法中各种运算总是要施加到各算法中各种运算总是要施加到各个运算对象上，而这些运算对象又可能具有某种初始状态，个运算对象上，而这些运算对象又可能具有某种初始状态，这就是算法执行的起点或依据。因此，这就是算法执行的起点或依据。因此，一个算法执行的结一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。结果输出。当输入不够或输入错误时，算法将无法执行或当输入不够或输入错误时，算法将无法执行或执行有错。一般说来，当算法拥有足够的情报时，此算法执行有错。一般说来，当算法拥有足够的情报时，此算法才是有效的；而当提供的情报不够时，算法可能无效。才是有效的；而当提供的情报不够时，算法可能无效。学学学学习习习习目目目目标标标标与与与与要要要要求求求求2 2、算法的基本要素、算法的基本要素v 对数据对象的运算和操作：算术运算、逻辑运算、关系运算、数据传输 算法中各操作之间的执行顺序；描述算法的工具通常有传统流程图、N-S结构化流程 图、算法描述语言等；一个算法一般可以用顺序、选择、循环三种基本结构 组合而成。v 算法的控制结构：算算算算法法法法与与与与数数数数据据据据结结结结构构构构3 3、算法设计的基本方法、算法设计的基本方法v 列举法v 归纳法v 递推v 递归（以简洁的形式设计和描述算法）v 减半递推技术v 回溯法算算算算法法法法与与与与数数数数据据据据结结结结构构构构二、算法的复杂度（二、算法的复杂度（包括包括包括包括时间复杂度时间复杂度时间复杂度时间复杂度和和和和空间复杂度空间复杂度空间复杂度空间复杂度）v（1）算法时间复杂度是指执行算法所需要的计算工作量，可以用执行算法的过程中所需基本运算的执行次数来度量。v（2）算法空间复杂度是指执行这个算法所需要的内存空间，,包括算法程序所占空间,输入的初始数据所占空间和执行过程中所需要的额外空间.算算算算法法法法与与与与数数数数据据据据结结结结构构构构3 3、例题讲解、例题讲解v 算法的时间复杂度是指算法的时间复杂度是指(C C)A A、执行算法程序所需要的时间执行算法程序所需要的时间 B B、算法程序的长度算法程序的长度 C C、算法执行过程中所需要的基本运算次数算法执行过程中所需要的基本运算次数 D D、算法程序中的指令条数算法程序中的指令条数v 算法的基本特征是可行性、确定性、算法的基本特征是可行性、确定性、【1 1】和拥有足够和拥有足够 的情报。的情报。【答案】【答案】:有穷性有穷性v 算法的空间复杂度是指算法的空间复杂度是指(D D)A)A)算法程序的长度算法程序的长度 B)B)算法程序中的指令条数算法程序中的指令条数 C)C)算法程序所占的存储空间算法程序所占的存储空间 D)D)执行过程中所需要的存储空间执行过程中所需要的存储空间算算算算法法法法与与与与数数数数据据据据结结结结构构构构v 在计算机中，算法是指（B B）A)加工方法 B)B)解题方案的准确而完整的描述解题方案的准确而完整的描述 C)排序方法 D)查询方法v 算法分析的目的是(D D)A)找出数据结构的合理性 B)找出算法中输入和输出之间的关系 C)分析算法的易懂性和可靠性 D)D)分析算法的效率以求改进分析算法的效率以求改进v 算法的工作量大小和实现算法所需的存储单元多少分别称 为算法的【1 1】。【答案】【答案】:时间复杂度和空间复杂度时间复杂度和空间复杂度算算算算法法法法与与与与数数数数据据据据结结结结构构构构三、数据结构（三、数据结构（Data Structure）1 1、数据结构研究的主要内容、数据结构研究的主要内容v当今计算机应用的特点：1、所处理的数据量大且具有一定的关系；2、对其操作不再是单纯的数值计算，而更多地是需 要对其进行组织、管理和检索。v应用举例1学籍档案管理 假设一个学籍档案管理系统应包含如下表1-1所示的学生信息。特点：每个学生的信息占据一行，所有学生的信息按学号顺序依 次排列构成一张表格；表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；对它的操作通常是插入某个学生的信息，删除某个学生的 信息，更新某个学生的信息，按条件检索某个学生的信息 等等。v 应用举例2输出n个对象的全排列 输出n个对象的全排列可以使用下图1-1所示的形式描述。图图图图 1-1 3 1-1 3 1-1 3 1-1 3个对象的全排列过程个对象的全排列过程个对象的全排列过程个对象的全排列过程特点：在求解过程中，所处理的数据之间具有层次关系，这是我们 所说的树形结构；对它的操作有：建立树形结构，输出最低层结点内容等等。v 应用举例3制定教学计划 在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表所示：v 课程先后关系的图形描形式：课程先后关系的图形描形式：c1c9c4c2c12c10c11c5c3c6c7c8图 1-2 计算机专业必修课程开设先后关系结论：结论：数据结构主要研究以下三个方面的问题：数据结构主要研究以下三个方面的问题：数据的逻辑结构：数据集合中各数据元素之间所固有的逻辑关系数据集合中各数据元素之间所固有的逻辑关系，包含：1）表示数据元素的信息；2）表示各数据元素之间的前后件关系 数据的存储结构：在对数据进行处理时，各数据元素在计算机中的在对数据进行处理时，各数据元素在计算机中的存储关系存储关系，数据的存储结构有顺序、链接、索引等数据的存储结构有顺序、链接、索引等。对各种数据结构进行的运算 *：数据的逻辑结构反映数据元素之间的逻辑关系，数据的存储结构（也称数据的物理结构）是数据的逻辑结构在计算机存储空间中的存放形式。同一种逻辑结构的数据可以采用不同的存储结构，但影响数据处理效率。算算算算法法法法与与与与数数数数据据据据结结结结构构构构2 2、基本概念和术语、基本概念和术语数据结构是一门研究数据数据数据数据组织组织、存储存储和运算运算的一般方法的学科。例：整数整数(1,2)、实数实数(1.1,1.2)字符串字符串(Beijing)、图形图形、声音声音。计算机管理图书问题：在图书馆里有各种卡片：有按书名编排的、有按作者编排的、有按分类编排。如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间。最简单的办法之一是建立一张表，每一本书的信息在表中占一行，如：数据元素在计算机中的表示数据结构是一门研究数据数据数据数据组织组织、存储存储和运算运算的一般方法的学科。如何将0,1,2,3,4,5,6,7,8,9这10个数存放在计算机中能最快地达到你所需要的目的？目的不同，最佳的存储方方法就不同。从大到小排列：9,8,7,6,5,4,3,2,1,0输出偶数：0,2,4,6,8,1,3,5,7,9 对数据结构中的节点进行操作处理(插入、删除、修改、查找、排序)v 数据元素数据元素(Data Element)Data Element)数据元素是数据的基本单位，即数据集合中的个体。有时一个数据元素可由若干数据项数据项(Data ItemData Item)组成。数据项是数据的最小单位。PS:数据元素是数据的基本单位，数据项是属于数据元素的！数据项是最小单位！数据元素亦称节点节点或记录记录。数据结构可描述为数据结构可描述为 Group=Group=（D D，R R）有限个数据元素的集合有限个数据元素的集合有限个节点间关系的集合有限个节点间关系的集合有限个节点间关系的集合有限个节点间关系的集合数据结构可描述为数据结构可描述为Group=（D，R）1 1、数据的、数据的逻辑结构逻辑结构 2 2、数据的、数据的存储结构存储结构 3 3、数据的、数据的运算运算：检索、排序、插入、删除、修改等。：检索、排序、插入、删除、修改等。A A线性结构线性结构 B B非线性结构非线性结构A A顺序存储顺序存储 B B链式存储链式存储 线性表线性表堆堆栈栈队列和线性链表队列和线性链表树形结构树形结构图形结构图形结构数数据据结结构构的的三三个个方方面面(亦称物理结构亦称物理结构)条件：条件：1）有且只有一个根）有且只有一个根结点；点；2）每一个）每一个结点最多点最多有一个前件，也最多有一个后件。有一个前件，也最多有一个后件。不不满足足线性性结构条构条件的数据件的数据结构。构。v 线性结构：线性结构：例如：例如：A,B,C,A,B,C,，X X,Y,Z,Y,Z学学 生生 成成 绩绩 表表86868686胡孝臣胡孝臣胡孝臣胡孝臣986110398611039861103986110395959595刘忠赏刘忠赏刘忠赏刘忠赏9861107986110798611079861107100100100100张卓张卓张卓张卓9861109986110998611099861109成成成成 绩绩绩绩姓姓姓姓 名名名名学学学学 号号号号v 线性表线性表结点间是以线性关系联结：结点间是以线性关系联结：算算算算法法法法与与与与数数数数据据据据结结结结构构构构v 树形结构全校学生档案管理的组织方式全校学生档案管理的组织方式计算机程序管理系统也是典型的计算机程序管理系统也是典型的树形结构树形结构。H HG GF FE EC CD DB BA A树形结构树形结构树形结构树形结构结点间具有分层次的连接关系结点间具有分层次的连接关系结点间具有分层次的连接关系结点间具有分层次的连接关系HHB BC CD DE EF FGGA A1 14 42 23 3D=1,2,3,4D=1,2,3,4R=(1,2),(1,3),R=(1,2),(1,3),(1,4),(2,3),(1,4),(2,3),(3,4),(2,4)(3,4),(2,4)2 21 13 3 D=1,2,3 D=1,2,3 R=(1,2),(2,3),(3,2),(1,3)R=(1,2),(2,3),(3,2),(1,3)v 图形结构图形结构节点间的连结是任意的节点间的连结是任意的顺顺序序存存储储存储地址存储地址存储内容存储内容元素元素n n.元素元素i i.元素元素2 2元素元素1 1L L L Lo o o oL Lo o+m+mL Lo o+(i-1)*m+(i-1)*mLo+Lo+（n-1)*n-1)*m mm是每个元素所占用是每个元素所占用的存储单元个数的存储单元个数顺序存储结构具有两个基本特点：顺序存储结构具有两个基本特点：（1）所有元素所占的存储空间是）所有元素所占的存储空间是连续的；连续的；（2）各数据元素在存储空间中是）各数据元素在存储空间中是按逻辑顺序依次存放的。按逻辑顺序依次存放的。数据的存储结构顺序存储链链 式式 存存 储储 hv 每个节点都由两部分组成：数据域数据域和指针域指针域。v数据域数据域存放元素本身的数据，指针域指针域存放指针。v 数据元素之间逻辑上的联系由指针来体现。1531536 6元素元素2 21401400 0元素元素1 11341346 6元素元素3 3 元素元素4 4134513451341345 5 1346134613461346 元素元素元素元素3 3 3 3 1536153615361536 .1536153615361536 元素元素元素元素2 2 2 2 1400140014001400 .元素元素元素元素4 4 4 4 1346134613461346 1400140014001400 元素元素元素元素1 1 1 1 1345134513451345 指针指针 存储内容存储内容存储地址存储地址数据的数据的存储结构存储结构1、比顺序存储结构的占用的存储空间要大 (每个节点都由数据域和指针域组成)。2、逻辑上相邻的节点物理上不必相邻。3、插入、删除灵活 (不必移动节点，只要改变节点中的指针)。v 链式存储结构特点：链式存储结构特点：算算算算法法法法与与与与数数数数据据据据结结结结构构构构v 线性结构和非线性结构线性结构和非线性结构如果一个非空的数据结构满足下列两个条件：如果一个非空的数据结构满足下列两个条件：有且只有一个根结点；有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件每一个结点最多有一个前件，也最多有一个后件 则称该数据结构为线性结构（线性表）。则称该数据结构为线性结构（线性表）。如果一个数据结构不是线性结构，则称之为非线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。算算算算法法法法与与与与数数数数据据据据结结结结构构构构3 3、例题讲解、例题讲解v链表不具有的特点是（链表不具有的特点是（B B ）A)A)不必事先估计存储空间不必事先估计存储空间 B)B)可随机访问任一元素可随机访问任一元素 C)C)插入删除不需要移动元素插入删除不需要移动元素 D)D)所需空间与线性表长度成正比所需空间与线性表长度成正比v数据结构分为逻辑结构与存储结构，线性链表属于数据结构分为逻辑结构与存储结构，线性链表属于 【1 1】。【答案【答案】存储结构存储结构v数据结构中，与所使用的计算机无关的是数据的数据结构中，与所使用的计算机无关的是数据的(C C )A)A)存储结构存储结构B)B)物理结构物理结构 C)C)逻辑结构逻辑结构D)D)物理和存储结构物理和存储结构 v数据的逻辑结构有线性结构和数据的逻辑结构有线性结构和 【2 2】两大类。两大类。非线性结构非线性结构v顺序存储方法是把逻辑上相邻的结点存储在物理位置顺序存储方法是把逻辑上相邻的结点存储在物理位置 【3 3】的存储单元中。的存储单元中。【答案【答案】相邻相邻v数据处理的最小单位是数据处理的最小单位是(C C )A)A)数据数据 B)B)数据元素数据元素 C)C)数据项数据项 D)D)数据结构数据结构v数据结构作为计算机的一门学科，主要研究数据的逻辑结构、数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及对各种数据结构进行的运算，以及(A A )A)A)数据的存储结构数据的存储结构 B)B)计算方法计算方法 C)C)数据映象数据映象 D)D)逻辑存储逻辑存储v线性表的顺序存储结构和线性表的链式存储结构分别是线性表的顺序存储结构和线性表的链式存储结构分别是(B B )A)A)顺序存取的存储结构、顺序存取的存储结构顺序存取的存储结构、顺序存取的存储结构 B)B)随机存取的存储结构、顺序存取的存储结构随机存取的存储结构、顺序存取的存储结构 C)C)随机存取的存储结构、随机存取的存储结构随机存取的存储结构、随机存取的存储结构 D)D)任意存取的存储结构、任意存取的存储结构任意存取的存储结构、任意存取的存储结构 v根据数据结构中各数据元素之间前后件关系的复杂程度，一根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成般将数据结构分成(C C )A)A)动态结构和静态结构动态结构和静态结构 B)B)紧凑结构和非紧凑结构紧凑结构和非紧凑结构 C)C)线性结构和非线性结构线性结构和非线性结构 D)D)内部结构和外部结构内部结构和外部结构 v数据结构包括数据的逻辑结构、数据的数据结构包括数据的逻辑结构、数据的 【4 4】以及对数据以及对数据的操作运算。的操作运算。【答案【答案】物理结构（或存储结构）物理结构（或存储结构）v数据的基本单位是数据的基本单位是 【5 5】。【答案【答案】数据元素数据元素3 3、例题讲解、例题讲解v下列叙述中，错误的是（下列叙述中，错误的是（B B ）A)A)数据的存储结构与数据处理的效率密切相关数据的存储结构与数据处理的效率密切相关 B)B)数据的存储结构与数据处理的效率无关数据的存储结构与数据处理的效率无关 C)C)数据的存储结构在计算机中所占的空间不一定是连续的数据的存储结构在计算机中所占的空间不一定是连续的 D)D)一种数据的逻辑结构可以有多种存储结构一种数据的逻辑结构可以有多种存储结构v数据的存储结构是指（数据的存储结构是指（B B ）A A）数据所占的存储空间数据所占的存储空间B B）数据的逻辑结构在计算机中的表示数据的逻辑结构在计算机中的表示C C）数据在计算机中的顺序存储方式数据在计算机中的顺序存储方式D D）存储在外存中的数据存储在外存中的数据 3 3、例题讲解、例题讲解4 4、线性表（、线性表（Linear ListLinear List）v 线性表的定义线性表的定义:线性表线性表是是n n个元素的有限序列，它们之间的关系可以排成个元素的有限序列，它们之间的关系可以排成一个线性序列：一个线性序列：a1a1，a2a2，aiai，anan 其中其中n n称作表的称作表的长度长度，当，当n=0n=0时，称作时，称作空表空表。v线性表的特点：线性表的特点：1 1、线性表中所有元素的性质相同。、线性表中所有元素的性质相同。2 2、除第一个和最后一个数据元素之外，其它数据元素有且、除第一个和最后一个数据元素之外，其它数据元素有且 仅有一个前驱和一个后继。第一个数据元素无前驱，最仅有一个前驱和一个后继。第一个数据元素无前驱，最 后一个数据元素无后继。后一个数据元素无后继。3 3、数据元素在表中的位置只取决于它自身的序号。、数据元素在表中的位置只取决于它自身的序号。v在线性表上常用的运算有：在线性表上常用的运算有：初始化、求长度、取元素、修改、前插、删除、检索、排序。初始化、求长度、取元素、修改、前插、删除、检索、排序。v 线性表的顺序存储结构及其插入与删除操作线性表的顺序存储结构及其插入与删除操作特点：特点：1 1、线性表中数据元素类型一致，只有数据域，存储空间、线性表中数据元素类型一致，只有数据域，存储空间 利用率高。利用率高。2 2、所有元素所占的存储空间是连续的。、所有元素所占的存储空间是连续的。3 3、各数据元素在存储空间中是按逻辑顺序依次存放的、各数据元素在存储空间中是按逻辑顺序依次存放的 （a a）做插入、删除时需移动大量元素。插入运算时平均需要移动做插入、删除时需移动大量元素。插入运算时平均需要移动n/2n/2个元素；删除运算时个元素；删除运算时 ，平均需要移动（，平均需要移动（n-1n-1）/2/2个元素。个元素。（b b）空间估计不明时，按最大空间分配。空间估计不明时，按最大空间分配。（c c）不便于对存储空间的动态分配。不便于对存储空间的动态分配。算算算算法法法法与与与与数数数数据据据据结结结结构构构构顺序存储结构示意图顺序存储结构示意图(顺序表顺序表)：元素元素元素元素anananan.元素元素元素元素aiaiaiai.元素元素元素元素a2a2a2a2元素元素元素元素a a a a1 1 1 1bb+mb+(i-1)*mb+(maxlen-1)*m存储地址存储地址内存状态内存状态LocLoc(元素元素i i)=b+=b+（i-1)*i-1)*m m每个元素所占用每个元素所占用的存储单元个数的存储单元个数首地址首地址起始地址起始地址基地址基地址*：由此可以看出，：由此可以看出，在线性表的顺序存在线性表的顺序存储结构中，其前后储结构中，其前后件两个元素在存储件两个元素在存储空间中是紧邻的，空间中是紧邻的，且前件元素一定存且前件元素一定存储在后件元素的前储在后件元素的前面，可以通过计算面，可以通过计算机直接确定第机直接确定第i个结个结点的存储地址。点的存储地址。元素元素a a1 1元素元素a a2 2.元素元素a ai+1i+1.0 0 1 1i i线性表的顺序存储结构线性表的顺序存储结构可用可用C C语言中的一维数组来描述语言中的一维数组来描述.第第i i个元素的个元素的a ai i存储地址：存储地址：Loc(aLoc(ai i)=Loc(a)=Loc(a1 1)+(i-1)*m)+(i-1)*mVV VV ViViVm-1Vm-1 intint VM;VM;其中：其中：V V是数组的名字，是数组的名字，M M是数组大小，是数组大小，假设数组中的元素是整型类型假设数组中的元素是整型类型算算算算法法法法与与与与数数数数据据据据结结结结构构构构 插入运算插入运算.a a2 2a a1 1a an n.a ai+1i+1a ai i01i-1in-1a ai-1i-1.a a2 2a a1 1a alengthlength a ai+1i+1a ai ix x a ai-1i-1.a a2 2 a a1 1 X X a ai ia ai+1i+1.a alengthlength插入算法的分析插入算法的分析插入算法的分析插入算法的分析 假设线性表中含有假设线性表中含有假设线性表中含有假设线性表中含有n n n n个数据元素，在进行插入操作个数据元素，在进行插入操作个数据元素，在进行插入操作个数据元素，在进行插入操作时，若时，若时，若时，若假定在假定在假定在假定在n+1n+1n+1n+1个位置上插入元素的可能性均等，则平均移个位置上插入元素的可能性均等，则平均移个位置上插入元素的可能性均等，则平均移个位置上插入元素的可能性均等，则平均移动元素动元素动元素动元素的个数为：的个数为：的个数为：的个数为：删除算法的分析删除算法的分析 在进行删除操作时，若假定删除每个元素的可能性均等，在进行删除操作时，若假定删除每个元素的可能性均等，在进行删除操作时，若假定删除每个元素的可能性均等，在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：则平均移动元素的个数为：