收藏 网站地图 登录 免费注册
购物车

全选

0件商品

共计:0

首页 > 学科资料 > 信息技术 > 主干知识 > 正文

了解线性表、栈、队列、二叉树、图的基本概念

作者: 小吖   发布时间: 2018-09-03 10:26 浏览: 120

常见的数据结构包括线性结构、树形结构、图形结构等,其中要解线性表、栈、队列、二叉树、图的基本概念是福建省教师招聘考试大纲要求考生掌握的信息技术科知识点之一,今天我们一起来学习一下吧~

一、数据结构的分类

(一)线性结构:数组、链表、队列、栈;

(二)树形结构:二叉树及其变型,线段树,巴拉巴拉;

(三)图形结构:各种图;

二、线性表

(一)定义:一个线性表示具有n个数据元素的有限序列。

(二)特点:同一性、有穷性、有序性。

三、栈

了解线性表、栈、队列、二叉树、图的基本概念

(一)定义:栈是一种具有线性结构的数据结构,是操作受限的线性表。

(二)特点:是后进先出,只能在栈顶进行插入和删除操作,入栈、出栈顺序栈中。

栈空标志:S.top=S.base;

栈满标志:S.top-S.base>=S.stacksize;

链栈中,不设头结点,头结点就是栈顶指针,栈空S=NULL。

(三)用途:数值转换,括号匹配检验、行编辑程序,迷宫问题、算数表达式求值(2个栈),递归的实现递归(算法设计方法)后调用先返回。

四、队列

了解线性表、栈、队列、二叉树、图的基本概念

(一)定义:一种具有线性结构的数据结构,是操作受限的线性表;

(二)特点:先进先出,只能在队尾插入元素和队头删除元素,称为入队列和出队列;

队满标志:(Q.rear+1)%MAXOQSIZE==Q.front;

链队列中,队空标志:Q.front=Q.rear;

空间范围内不会出现队满的情况。

五、二叉树

了解线性表、栈、队列、二叉树、图的基本概念

(一)定义:二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。二叉树常被用于实现二叉查找树和二叉堆。

(二)性质:

1.二叉树的第i层至多有2i-1个结点;

2.深度为k的二叉树至多有2k-1个结点;

3.对任意一个二叉树,若终端结点数为n0,度为2的结点数为n2,则n0=n2+1;

4.具有n个结点的完全二叉树的深度。

(三)特殊树:满二叉树,完全二叉树

1.完全二叉树:设二叉树的深度为h,除第 h层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h层所有的结点都连续集中在最左边。

2.满二叉树:深度为k且有2^k-1个结点的二叉树称为满二叉树。

(四)存储:顺序存储,链式存储结构。

六、图

(一)定义:两个集合V、E组成,记为G=(V,E),其中V是顶点的有限集合,E是连接V中两个不同顶点(顶点对)的边的有限集合,记为E(G)。

(二)基本术语:完全图、稀疏图、稠密图、子图、顶点的度(入度、出度)、权与网、路径和图、连通图、强连通图(来回都连通)、连通分量等

(三)存储结构:邻接矩阵表示法(数组表示法)、邻接表存储方法、邻接多重表、十字链表(有向图的邻接表和逆邻接表结合在一起)。

以上,是福建教师招考根据考试大纲整理的信息技术学科知识点数据结构,希望可以帮助到各位考生备考复习。



推荐阅读:

2019年福建教师招考信息技术学科更多相关文章

2019年福建教师招考信息技术学科教材教法相关文章

了解线性表、栈、队列、二叉树、图的基本概念