计算机等级考试 二级c 之一 公共基础数据结构.ppt

公共基础知识内容与考点公共基础知识内容与考点• •基本要求基本要求– –掌握算法的基本概念掌握算法的基本概念– –掌握基本数据结构及其操作掌握基本数据结构及其操作– –掌握基本排序和查找算法掌握基本排序和查找算法– –掌握逐步求精的结构化程序设计方法掌握逐步求精的结构化程序设计方法– –掌握软件工程的基本方法，具有初步应用相关技术进行掌握软件工程的基本方法，具有初步应用相关技术进行 软件开发的能力软件开发的能力– –掌握数据库的基本知识，了解关系数据库的设计掌握数据库的基本知识，了解关系数据库的设计考试方式考试方式1 1．公共基础知识的考试方式为笔试，与．公共基础知识的考试方式为笔试，与C C语言程序设语言程序设计计(C++(C++语言程序设计、语言程序设计、JavaJava语言程序设计、语言程序设计、Visual Visual BasicBasic语言程序设计、语言程序设计、Visual FoxProVisual FoxPro数据库程序设计或数据库程序设计或AccessAccess数据库程序设计数据库程序设计) )的笔试部分合为一张试卷，公的笔试部分合为一张试卷，公共基础知识部分占全卷的共基础知识部分占全卷的3030分。

分2 2．公共基础知识有．公共基础知识有l0l0道选择题和道选择题和5 5道填道填第第 1 1 章章 数据结构与算法数据结构与算法• • 考试内容考试内容–– 算法算法– – 数据结构的基本概念数据结构的基本概念– – 线性表及顺序存储结构线性表及顺序存储结构 – – 栈和队列栈和队列– – 树与二叉树树与二叉树– – 线性链表线性链表( (单、双、循环）的结构及基本运算单、双、循环）的结构及基本运算– – 查找技术查找技术– – 排序技术排序技术选择题：选择题：4~54~5 填空题：填空题：1~21~2考点1： 算法的基本概念• •考点考点1 1：算法的基本概念：算法的基本概念解题方案的准确而完善的描述解题方案的准确而完善的描述考点考点1 1在笔试考试中考核的几率为在笔试考试中考核的几率为30%30%，主要是以填空，主要是以填空 题的形式出现，分值为题的形式出现，分值为2 2分，此考点为识记内容，读者分，此考点为识记内容，读者 还应该了解算法中对数据的基本运算还应该了解算法中对数据的基本运算20052005年年3 3月：填空题月：填空题 （（5 5）问题处理方案的正确而完整的描述称为）问题处理方案的正确而完整的描述称为 。

算法算法─ ─算法的基本特征：算法的基本特征：可行性可行性、、确定性确定性、、有穷性有穷性、、拥有足够的情报拥有足够的情报20052005年年3 3月：选择题月：选择题 （（1111）算法具有五个特性，以下选项不属于算法特性的是：）算法具有五个特性，以下选项不属于算法特性的是： A A）有穷性）有穷性 B B）简洁性）简洁性 C C）可行性）可行性 D D）确定性）确定性B B考试链接 算法的基本要素：算法的基本要素： （（1 1）算法中对数据的运算和操作）算法中对数据的运算和操作一是对数据对象的运算和操作；二是算法的控制结一是对数据对象的运算和操作；二是算法的控制结构在一般的计算机系统中，基本的运算和操作有以下在一般的计算机系统中，基本的运算和操作有以下4 4类：算术运算、逻辑运算、关系运算和数据传输类：算术运算、逻辑运算、关系运算和数据传输 （（2 2））算法的控制结构：算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构算法中各操作之间的执行顺序称为算法的控制结构描述算法的工具通常有传统流程图、描述算法的工具通常有传统流程图、N-SN-S结构化流程结构化流程图、算法描述语言等。

一个算法一般都可以用顺序、选图、算法描述语言等一个算法一般都可以用顺序、选 择、循环择、循环3 3种基本控制结构组合而成种基本控制结构组合而成考点2：算法的复杂度• • 算法复杂度的基本概念算法复杂度的基本概念执行算法所需要的计算工作量执行算法所需要的计算工作量– – 算法的计算工作量用算法所执行的算法的计算工作量用算法所执行的基本运算次数表示表示– – 算法的算法的基本运算次数表示是问题规模的函数表示是问题规模的函数算法的工作量算法的工作量= =f(nf(n) )n n是问题的规是问题的规 模模在同一问题规模下，如果算法所需的基本运算次数取决在同一问题规模下，如果算法所需的基本运算次数取决 于某一特定输入时，可用平均性态或最坏情况复杂性分于某一特定输入时，可用平均性态或最坏情况复杂性分 析算法的工作量析算法的工作量平均性态• • 各种特定输入下基本运算次数的加权平均值来衡量算法各种特定输入下基本运算次数的加权平均值来衡量算法其中其中x x是所有可能输入中的某个特定输入，是所有可能输入中的某个特定输入，p(xp(x) )是是x x出现的概率，出现的概率，t(xt(x) )是在输入为是在输入为x x时所执行的基本运算时所执行的基本运算次数，次数，DnDn表示当问题规模为表示当问题规模为n n时，算法所有可能输时，算法所有可能输入的集合。

入的集合最坏情况复杂性• • 在规模为在规模为n n时，算法所执行的基本运算的最大次数时，算法所执行的基本运算的最大次数算法的空间复杂度包括算法程序所占的空间、输入数据所占的空间，以及包括算法程序所占的空间、输入数据所占的空间，以及 算法执行过程中所需要的额外空间算法执行过程中所需要的额外空间• • 执行这个算法所需要的内存空间执行这个算法所需要的内存空间– – 如果额外空间量相对于问题规模来说是常数，则称该如果额外空间量相对于问题规模来说是常数，则称该 算法是算法是原地的真题实例真题实例考点考点2 2在笔试考试中，是一个经常考查的内容，在笔试在笔试考试中，是一个经常考查的内容，在笔试 考试中出现的几率为考试中出现的几率为70%70%，主要是以选择的形式出现，，主要是以选择的形式出现， 分值为分值为2 2分，此考点为重点识记内容，读者还应该识记分，此考点为重点识记内容，读者还应该识记 算法时间复杂度及空间复杂度的概念算法时间复杂度及空间复杂度的概念20102010年年3 3月：选择题月：选择题 （（2 2）算法的时间复杂度指：）算法的时间复杂度指： A A）算法的执行时间）算法的执行时间 B B）算法所处理的数据量）算法所处理的数据量 C C）算法指令中的语句或指令条数）算法指令中的语句或指令条数 D D）算法在执行过程中所需要的基本运算次数）算法在执行过程中所需要的基本运算次数20092009年年9 9月：选择题月：选择题 （（4 4）算法的空间复杂度指：）算法的空间复杂度指： A A）算法的执行过程中所需要的计算机存储空间）算法的执行过程中所需要的计算机存储空间 B B）算法所处理的数据量）算法所处理的数据量 C C）算法指令中的语句或指令条数）算法指令中的语句或指令条数 D D）算法在执行过程中所需要的临时工作单元数）算法在执行过程中所需要的临时工作单元数D DA A考点3：数据结构的基本概念考点考点3 3在笔试考试中，是一个经常考查的内容，在笔试在笔试考试中，是一个经常考查的内容，在笔试 考试中出现的几率为考试中出现的几率为70%70%，主要是以选择的形式出现，，主要是以选择的形式出现， 分值为分值为2 2分，此考点为识记内容，读者还应该识记数据分，此考点为识记内容，读者还应该识记数据 的逻辑结构和存储结构的概念。

的逻辑结构和存储结构的概念在数据结构中，从逻辑上可以把数据结构分成在数据结构中，从逻辑上可以把数据结构分成______________ A A）内部结构和外部结构）内部结构和外部结构 B B）线性结构和非线性结构）线性结构和非线性结构 C C）紧凑结构和非紧凑结构）紧凑结构和非紧凑结构 D D）动态结构和静态结构）动态结构和静态结构解析：逻辑结构反映数据元素之间的逻辑关系，解析：逻辑结构反映数据元素之间的逻辑关系， 线性结构表示数据元素之间为一对一的关系，线性结构表示数据元素之间为一对一的关系， 非线性结构表示数据元素之间为一对多或者多对一的关系，非线性结构表示数据元素之间为一对多或者多对一的关系， 所以答案为所以答案为B B）考点3：数据结构的基本概念• • 数据元素数据元素– – 每一个需要处理的对象都可以抽象成每一个需要处理的对象都可以抽象成数据元素一般情况下，在具有相同特征的数据元素集合中，各个一般情况下，在具有相同特征的数据元素集合中，各个 元素之间有某种关系，这个关系反映了该集合中的数据元素之间有某种关系，这个关系反映了该集合中的数据 元素之间固有的一种结构。

在数据处理领域中，统常把元素之间固有的一种结构在数据处理领域中，统常把 数据元素之间的这种固有的关系简单的用前后件关系来数据元素之间的这种固有的关系简单的用前后件关系来 描述描述• • 数据结构数据结构– – 带有带有结构结构的数据元素的集合的数据元素的集合数据元素之间的前后件关系数据元素之间的前后件关系(数据的逻辑结构 (数据的存储结构 (数据的运算数据的逻辑结构数据的逻辑结构• • 数据的逻辑结构是反映数据之间逻辑关系的结构数据的逻辑结构是反映数据之间逻辑关系的结构数据结构的两要素：：数据结构的两要素：： Data-Structure Data-Structure ＝＝ (D,R)(D,R) 其中：其中：D D是数据元素的集合，是数据元素的集合，R R是是D D上关系的集合上关系的集合例11 一年四季的数据结构可表示成B=B=（（D D，，R R））D={D={春，夏，秋，冬春，夏，秋，冬} }R={R={（春，夏），（夏，秋），（秋，冬）（春，夏），（夏，秋），（秋，冬）} }数据的存储结构数据的存储结构• • 数据的逻辑结构在计算机存储空间内的存放形式数据的逻辑结构在计算机存储空间内的存放形式20052005年年3 3月：选择题月：选择题 （（1 1）数据的存储结构是指）数据的存储结构是指 A A）存储在外存的数据）存储在外存的数据 B B）数据所占的存储空间量）数据所占的存储空间量 C C）数据在计算机中的顺序存储方式）数据在计算机中的顺序存储方式 D D）数据的逻辑结构在计算机中的表示）数据的逻辑结构在计算机中的表示D D数据结构的图形表示数据结构的图形表示• • 数据结构的图形表示数据结构的图形表示数据元素：数据元素：R R关系的二元组：一条有向线段从前件指向后件关系的二元组：一条有向线段从前件指向后件– – 没有前件的结点称为没有前件的结点称为“ “根结点”– – 没有后件的结点称为没有后件的结点称为“ “叶子结点”– – 除了根结点和叶子结点的其它结点称为除了根结点和叶子结点的其它结点称为“ “内部结点”考点考点4 4：线性表：线性表a1 a2 a3an-1 an•线性表的逻辑结构是n个数据元素的有限序列:(a1, a2 ,a3,…an) n为线性表的长度(n≥0)，n=0的表称为空表•数据元素呈线性关系.必存在唯一的称为“第一个”的 数据元素;必存在唯一的称为“最后一个”的数据元素 ；• 除第一个元素外，每个元素都有且只有一个前驱元素； 除 最后一个元素外，每个元素都有且只有一个后继元素。

• 所有数据元素ai在同一个线性表中必须具有相同的数据类型• 线性表按其存储结构可分为顺序表和链表用顺序存储结构存 储的线性表称为顺序表顺序表顺序表；顺序表顺序表• • 线性表的存储结构线性表的存储结构– – 线性表中所有元素所占的存储空间是线性表中所有元素所占的存储空间是“ “连续的”– – 线性表中各元素在存储空间。