全国计算机等级考试二级c语言考点解析第二部分数据结构.doc

全国计算机等级考试二级c语言考点解析第二部分数据结构.doc

  1. 1、本文档共4页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
全国计算机等级考试二级c语言考点解析第二部分数据结构

考点1算法的基本概念 是对特定问题求解步骤的一种描述,算法是指令的有限序列,其中每一条指令表示一个或多个操作。 基本特征:(1)可行性(2)确定性(3)有穷性(4)有足够的情报【(4)输入(5)输出】 基本方法:(1)列举法(2)归纳法(3)递推法(4)递归(5)减半递推技术(6)回溯法 设计要求:(1)正确性(2)可读性(3)健壮性(4)效率与低存储量要求 时间复杂度:一个算法中的语句执行次数称为语句频度或时间频度。记为T(n) 空间复杂度:指算法在计算机内执行时所需存储空间的度量。记作 S(n)=O(f(n)) 考点2数据结构的基本概念 数据的逻辑结构:集合、线性结构、树形结构和图(网)状结构。 数据的存储结构:数据的逻辑结构在计算机中的映像,也称为数据的物理结构。通常有顺序、链接、散列和索引等结构。 考点3线性表及顺序存储结构 线性表:n(30)个数据元素的有限???列 顺序存储结构:将线性表中的元素相继存放在一个连续的存储空间 顺序存储方式: LOC(a i+1) = LOC( a i )+l LOC(a i) = LOC(a1)+(i-1)*l 顺序的插入:算法的复杂度E=n/2 顺序的删除:算法的复杂度E=(n-1)/2 考点4栈和队列 栈:限定仅在表尾进行插入或删除操作的线性表。 允许插入和删除的一端 称为栈顶(top),另一端 称为栈底(bottom) 特点:后进先出 (LIFO) 队列:只允许在表的一端进行插入,而在另一端删除元素的线性表。 在队列中,允许插入的一端叫队尾(rear) 允许删除的一端称为对头(front)。 特点:先进先出 (FIFO) 考点5树与二叉树 树的定义:由 n (n 3 0) 个结点的有限集合。如果 n = 0,称为空树;如果 n 0,则 有且仅有一个特定的称之为根(Root)的结点,它只有直接后继,但没有直接前驱; 当n 1,除根以外的其它结点划分为 m (m 0) 个互不相交的有限集 T1,T2 ,…,Tm,其中每个集合本身又是一棵树,并且称为根的子树(SubTree) 二叉树:另一种树型结构,它是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。 特点:每个结点至多只有两棵子树(二叉树中不存在度大于2的结点) 五种形态: L L R R 性质1:在二叉树的第 i 层上至多有 2i -1个结点。 性质2 :深度为 k 的二叉树至多有 2 k-1个结点(k 3 1)。 性质3:对任何一棵二叉树T, 如果其叶结点数为 n0, 度为2的结点数为 n2,则n0=n2+1. 满二叉树 (Full Binary Tree) :一棵深度为k且有2 k-1个结点的二叉树称为满二叉树。 完全二叉树 (Complete Binary Tree):若设二叉树的高度为h,则共有h层。除第 h 层外,其它各层 (0 ~ h-1) 的结点数都达到最大个数,第 h 层从右向左连续缺若干结点,这就是完全二叉树。 6 2 1 7 5 4 3 8 9 10 11 12 完全二叉树 2 1 5 4 3 6 7 非完全二叉树 2 1 6 5 4 3 非完全二叉树 考点6二叉树的遍历(重点) 前序遍历 方法:若二叉树为空,则执行空操作。否则: 访问根节点; 前序遍历左子树; 前序遍历右子树; 中序遍历 方法:若二叉树为空,则执行空操作。否则: 中序遍历左子树; 访问根节点; 中序遍历右子树; 后续遍历 方法:若二叉树为空,则执行空操作。否则 后序遍历左子树; 后序遍历右子树; 访问根节点; 例: A B C D E F 前序遍历:ABDECF 中序遍历:DBEACF 后序遍历:DEBFCA 考试常出题型:给定二叉树的某两种遍历顺序,求另外一种遍历顺序。 考点6查找技术 顺序查找、二分法查找。 考点7排序技术(重点) 交换类排序技术 冒泡排序 快速排序 选择类排序 简单选择排序 堆排序 插入类排序 简单插入排序 希尔(Shell)排序

文档评论(0)

2017ll + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档