没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
第 1 章 数据结构与算法
经过对部分考生的调查以及对近年真题的总结分析,笔试部分经常考查的是算法复杂度、数据结构的
概念、栈、二叉树的遍历、二分法查找,读者应对此部分进行重点学习。
详细重点学习知识点:
1 .算法的概念、算法时间复杂度及空间复杂度的概念
2 .数据结构的定义、数据逻辑结构及物理结构的定义
3 .栈的定义及其运算、线性链表的存储方式
4 .树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历
5 .二分查找法
6 .冒泡排序法
1.1 算法
考点 1 算法的基本概念
计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。
1 .算法的基本特征:可行性、确定性、有穷性、拥有足够的情报。
2 .算法的基本要素:
( 1 )算法中对数据的运算和操作
一个算法由两种基本要素组成:一是对数据对象的运算和操作;二是算法的控制结构。
在一般的计算机系统中,基本的运算和操作有以下 4 类:算术运算、逻辑运算、关系运算和数据传输。
( 2 )算法的控制结构:算法中各操作之间的执行顺序称为算法的控制结构。
描述算法的工具通常有传统流程图 、 N-S 结构化流程图 、 算法描述语言等 。 一个算法一般都可以用顺序
、
选择、循环 3 种基本控制结构组合而成。
考点 2 算法复杂度
1. 算法的时间复杂度
算法的时间复杂度是指执行算法所需要的计算工作量。
同一个算法用不同的语言实现 , 或者用不同的编译程序进行编译 , 或者在不同的计算机上运行 , 效率均
不同。这表明使用绝对的时间单位衡量算法的效率是不合适的。撇开这些与计算机硬件、软件有关的因素 ,
可以认为一个特定算法 " 运行工作量 " 的大小 , 只依赖于问题的规模 ( 通常用整数 n 表示 ) , 它是问题规模的函
数。即
算法的工作量 =f ( n )
2. 算法的空间复杂度
算法的空间复杂度是指执行这个算法所需要的内存空间。
一个算法所占用的存储空间包括算法程序所占的空间 、 输入的初始数据所占的存储空间以及算法执行过
程中所需要的额外空间 。 其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加
存储空间。如果额外空间量相对于问题规模来说是常数,则称该算法是原地工作的。在许多实际问题中 , 为
了减少算法所占的存储空间,通常采用压缩存储技术,以便尽量减少不必要的额外空间。
疑难解答:算法的工作量用什么来计算?
算法的工作量用算法所执行的基本运算次数来计算 , 而算法所执行的基本运算次数是问题规模的函数 , 即算法的工作量 =f
( n ) ,其中 n 是问题的规模。
1.2 数据结构的基本概念
考点 3 数据结构的定义
数据结构作为计算机的一门学科,主要研究和讨论以下三个方面:
( 1 )数据集合中个数据元素之间所固有的逻辑关系,即数据的逻辑结构;
( 2 )在对数据元素进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;
( 3 )对各种数据结构进行的运算。
数据 : 是对客观事物的符号表示 , 在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符
号的总称。
数据元素:是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。
数据对象:是性质相同的数据元素的集合,是数据的一个子集。
数据的逻辑结构是对数据元素之间的逻辑关系的描述 , 它可以用一个数据元素的集合和定义在此集合中
的若干关系来表示 。 数据的逻辑结构有两个要素 : 一是数据元素的集合 , 通常记为 D ; 二是 D 上的关系 , 它反
映了数据元素之间的前后件关系,通常记为 R 。一个数据结构可以表示成
B= ( D , R )
其中 B 表示数据结构。为了反映 D 中各数据元素之间的前后件关系,一般用二元组来表示。
数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构 ) 。
由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同 , 因此 , 为了表示存放在计算机存储
空间中的各数据元素之间的逻辑关系(即前后件关系 ) ,在数据的存储结构中,不仅要存放各数据元素的信
息,还需要存放各数据元素之间的前后件关系的信息。
一种数据的逻辑结构根据需要可以表示成多种存储结构 , 常用的存储结构有顺序 、 链接 、 索引等存储结
构 。 而采用不同的存储结构 , 其数据处理的效率是不同的 。 因此 , 在进行数据处理时 , 选择合适的存储结构
是很重要的。
考点 4 线性结构与非线性结构
根据数据结构中各数据元素之间前后件关系的复杂程度 , 一般将数据结构分为两大类型 : 线性结构与非
线性结构。如果一个非空的数据结构满足下列两个条件:
( 1 )有且只有一个根结点;
( 2 )每一个结点最多有一个前件,也最多有一个后件。
则称该数据结构为线性结构 。 线性结构又称线性表 。 在一个线性结构中插入或删除任何一个结点后还应
是线性结构。如果一个数据结构不是线性结构,则称之为非线性结构。
疑难解答:空的数据结构是线性结构还是非线性结构?
一个空的数据结构究竟是属于线性结构还是属于非线性结构 , 这要根据具体情况来确定 。 如果对该数据结构的算法是按线
性结构的规则来处理的,则属于线性结构;否则属于非线性结构。
1.3 栈及线性链表
考点 5 栈及其基本运算
1 .栈的基本概念
栈是限定只在一端进行插入与删除的线性表 , 通常称插入 、 删除的这一端为栈顶 , 另一端为栈底 。 当表
中没有元素时称为空栈 。 栈顶元素总是后被插入的元素 , 从而也是最先被删除的元素 ; 栈底元素总是最先被
插入的元素,从而也是最后才能被删除的元素。栈是按照 " 先进后出 " 或 " 后进先出 " 的原则组织数据的。
2 .栈的顺序存储及其运算
用一维数组 S ( 1 ∶ m )作为栈的顺序存储空间,其中 m 为最大容量。
在栈的顺序存储空间 S ( 1 ∶ m ) 中 , S ( bottom ) 为栈底元素 , S ( top ) 为栈顶元素 。 top=0 表示栈空 ; top=m
表示栈满。
栈的基本运算有三种:入栈、退栈与读栈顶元素。
( 1 )入栈运算:入栈运算是指在栈顶位置插入一个新元素。首先将栈顶指针加一(即 top 加 1 ) ,然后将
新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时,说明栈空间已满 , 不
可能再进行入栈操作。这种情况称为栈 " 上溢 " 错误。
( 2 )退栈运算:退栈是指取出栈顶元素并赋给一个指定的变量。首先将栈顶元素(栈顶指针指向的元
素)赋给一个指定的变量,然后将栈顶指针减一(即 top 减 1 ) 。当栈顶指针为 0 时,说明栈空,不可进行退栈
操作。这种情况称为栈的 " 下溢 " 错误。
( 3 )读栈顶元素:读栈顶元素是指将栈顶元素赋给一个指定的变量。这个运算不删除栈顶元素,只是
将它赋给一个变量,因此栈顶指针不会改变。当栈顶指针为 0 时,说明栈空,读不到栈顶元素。
小技巧: 栈是按照 " 先进后出 " 或 " 后进先出 " 的原则组织数据,但是出栈方式有多种选择,在考题中经常考查各种不
同的出栈方式。
考点 6 线性链表的基本概念
在链式存储方式中 , 要求每个结点由两部分组成 : 一部分用于存放数据元素值 , 称为数据域 , 另一部分
用于存放指针,称为指针域。其中指针用于指向该结点的前一个或后一个结点(即前件或后件 ) 。
链式存储方式既可用于表示线性结构,也可用于表示非线性结构。
( 1 )线性链表
线性表的链式存储结构称为线性链表。
在某些应用中 , 对线性链表中的每个结点设置两个指针 , 一个称为左指针 , 用以指向其前件结点 ; 另一
个称为右指针,用以指向其后件结点。这样的表称为双向链表。
( 2 )带链的栈
栈也是线性表 , 也可以采用链式存储结构 。 带链的栈可以用来收集计算机存储空间中所有空闲的存储结
点,这种带链的栈称为可利用栈。
疑难解答:在链式结构中,存储空间位置关系与逻辑关系是什么?
在链式存储结构中 , 存储数据结构的存储空间可以不连续 , 各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致
,
而数据元素之间的逻辑关系是由指针域来确定的。
1.4 树与二叉树
考点 7 树与二叉树及其基本性质
误区警示:
满二叉树也是完全二叉树,而完全二叉树一般不是满二叉树。应该注意二者的区别。
1 、树的基本概念
树 (tree )是一种简单的非线性结构。在树结构中,每一个结点只有一个前件,称为父结点,没有前件的
结点只有一个 , 称为树的根结点 。 每一个结点可以有多个后件 , 它们称为该结点的子结点 。 没有后件的结点
称为叶子结点。
在树结构中,一个结点所拥有的后件个数称为该结点的度。叶子结点的度为 0 。在树中,所有结点中的
最大的度称为树的度。
2 、二叉树及其基本性质
( 1 )二叉树的定义
二叉树是一种很有用的非线性结构,具有以下两个特点:
① 非空二叉树只有一个根结点;
② 每一个结点最多有两棵子树,且分别称为该结点的左子树和右子树。
剩余19页未读,继续阅读
资源评论
- G_SANGSK2021-03-22我以为是选择题讲解,原始概念。。。
airsars
- 粉丝: 5
- 资源: 11
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 排球场地的排球识别 yolov7标记
- DOTA 中的 YOLOX 损失了 KLD (定向物体检测)(Rotated BBox)基于YOLOX的旋转目标检测.zip
- caffe-yolo-9000.zip
- Android 凭证交换和更新协议 - “你只需登录一次”.zip
- 2024 年 ICONIP 展会.zip
- 微信小程序毕业设计-基于SSM的电影交流小程序【代码+论文+PPT】.zip
- 微信小程序毕业设计-基于SSM的食堂线上预约点餐小程序【代码+论文+PPT】.zip
- 锐捷交换机的堆叠,一个大问题
- 微信小程序毕业设计-基于SSM的校园失物招领小程序【代码+论文+PPT】.zip
- MATLAB《结合萨克拉门托模型和遗传算法为乐安河流域建立一个水文过程预测模型》+项目源码+文档说明
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功