数据结构基本知识

《数据结构基本知识》由会员分享，可在线阅读，更多相关《数据结构基本知识（58页珍藏版）》请在金锄头文库上搜索。

1、数据结构基础知识 熟识数据结构相关的概念、知识内容 熟记数据结构的基本操作及相应的代码实现 理解数据结构的逻辑结构，能根据题目要求选择 合适的数据结构 掌握基本操作及数据结构的基本应用，熟练基本 应用的程序设计一、栈1、栈的定义栈是一种线性表，对它的插入和删除都限制地表的同一 端进行。这一端叫做栈的“顶”，另一端则叫做栈的“底”。特点:后进先出(LIFO)、或者先进后出（FILO）通常栈可以用顺序的方式存储(数组)，分配一块连续的存储区域存放 栈中的表目，并用一个变量t指向当前栈顶（如下图）。假设栈中表目数的上限为m，所有表目都具有同一类型 stype，则可以用下列方式定义栈：Constm=栈

2、表目数的上限；Var s： array1m of stype ；栈t： integer； 栈顶指针，初始值为注意：不一定进栈结束后才出栈，进出栈可交叉进行。2、栈的基本操作栈的基本操作包括初始化（init）、进栈（push）、出栈（ pop）和读取栈顶元素（top）四种。1） 过程init(s,t)procedure init;begint:=0;end;2)、过程push(x)往栈s中压入一个值为x的数据：procedure push（ x：stype)；begintt+1； stx； x入栈end；Push3)、函数pop从栈中弹出一个表目function pop ：stype；begin

3、popst； 栈顶元素出栈 tt-1； 指针下移 end；pop4)、函数top读栈顶元素function top ：stype；beginif t=0 then writeln (stack empty)else topst； 返回栈顶元素end；top【竞赛试题】 以下哪一个不是栈的基本运算( C) (NOIP7)A)删除栈顶元素 B)删除栈底的元素 C)判断栈是否为空 D)将栈置为空栈一个栈的输入顺序为1、2、3、4、5，下列序列中可能是栈的 输出序列是 ( BCD )。(A)54312 (B)2415(C)21543 (D)1253若已知一个栈的入栈顺序是1，2，3，n，其输出序 列为

4、P1，P2，P3，Pn，若P1是n，则Pi是(C ) (NOIP7)A)i B)n-1 C)n-i+1 D)不确定n-i+1 栈的排列遵循先进后（即后进先出）出的原则 因为P1是n，是出栈的第一个数字，说明在n之前进栈的数字都没 有出栈，所以这个顺序是确定的。还可以知道，最后出栈的一定是数字1，也就是Pn。代入这个式子，是正确的。 4、设有一个顺序栈S，元素S1, S2, S3, S4, S5, S6依次 进栈，如果6个元素的出栈顺序为S2, S3, S4, S6, S5, S1，则顺序栈的容量至少应为多少？A A) 3 B) 4 C) 5 D) 65、向顺序栈中压入新元素时，应当（ A ）。

5、A先移动栈顶指针，再存入元素 B先存入元素，再移动栈顶指针C先后次序无关紧要 D同时进行二、队列1 队列的定义所谓队列，就是允许在一端进行插入，在另一端进行删除的线性表。 允许插入的一端称为队尾，通常用一个队尾指针w指向队尾元素，即w总是 指向最后被插入的元素；允许删除的一端称为队首，通常也用一个队首指 针t指向排头元素。初始时t=w=0（如下图）。 3265419队列头 t队列尾 w当他tw时,队列空队列数组a下标： 1 2 3 4 5 6 7我们按照如下方式定义队列：Constm=队列元素的上限；Typeequeue=array1m of qtype； 队列的类型定义Var q：equeu

6、e； 队列t，w：integer； 队尾指针和队首指针 2、队列的基本运算队列的运算主要有两种：入队（aDD）和出队（ DEL）1、过程ADD(x)在队列q的尾端插入元素xprocedure ADD( x：qtyper)；begin后移队尾指针并插入元素xw:=w+1； qwx；end；ADD2、函数DEL取出q队列的队首元素function DEL；begin取出队首元素并后移队首指针del:=qt；t:=t+1;end；DEL【竞赛试题】已知队列（13，2，11，34，41，77，5，7，18，26，15）， 第一个进入队列的元素是13，则第五个出队列的元素是（B ）。(NOIP9)A）

7、5 B） 41 C ） 77 D） 13 E） 18设栈S和队列Q的初始状态为空，元素e 1 ，e 2 ，e 3 ，e 4 ， e 5 ，e 6依次通过栈S，一个元素出栈后即进入队列Q，若出队 的顺序为e 2 ，e 4 ，e 3 ，e 6 ，e 5 ，e 1 ，则栈S的容量至少 应该为（ B ）。(NOIP8)A）2 B）3 C）4 D）5栈、队列属于线性结构。在这种结构中，不管其存储 方式（顺序和链式）如何，数据元素的逻辑位置之间呈线 性关系，即每一个数据元素通常只有一个前驱（除第一个 元素外）和一个后继（除最后一个元素外）。但也有很多问题数据元素间的逻辑关系不能用线性结 构明确、方便地描述

8、出来。一般来说，至少存在一个结点 （数据元素）有多于一个前驱或后继的数据结构称为非线 性结构。具有非线性结构特征的数据结构有两种树，图三、树一）、.树的概念1、树的定义树是一种常见的非线性的数据结构。树的递归定义如下：树是n(n0)个结点的有限集，这个集合满足以下条件：有且仅有一个结点没有前驱（父亲结点），该结点称为 树的根；除根外，其余的每个结点都有且仅有一个前驱；除根外，每一个结点都通过唯一的路径连到根上（否则 有环）。这条路径由根开始，而未端就在该结点上，且除根 以外，路径上的每一个结点都是前一个结点的后继（儿子结 点）；由上述定义可知，树结构没有封闭的回路。 树可以只有根结点2、结点的

9、分类 结点一般分成三类根结点：没有父亲的结点。 在树中有且仅有一个根结点。分支结点：除根结点外，有 孩子的结点称为分支结点。b， c，x，t，d，i。分支结点亦是 其子树的根；叶结点：没有孩子的结点称 为树叶。w，h，e，f，s，m，o ，n，j，u为叶结点。根结点到每一个分支结点或叶 结点的路径是唯一的。从根r到 结点i的唯一路径为rcti。3、有关度的定义结点的度：一个结点的子树数目称为该结点的度 （区分图中结点的度）。图中，结点i度为3，结点t的度为2， 结点b的度为1。显然，所有树叶的度为0。树的度：所有结点中最大的度称为该树的度(宽度） 。图中树的度为3。4、树的深度（高度）树是分层

10、次的。结点所在的层次是从根算起的。根结 点在第一层，根的儿子在第二层，其余各层依次类推。图 中的树共有五层。在树中，父结点在同一层的所有结点构 成兄弟关系。（e和i也是兄弟关系）树中最大的层次称为树的深度，亦称高度。图中树的 深度为5。5、森林所谓森林，是指若干棵互不相交的树的集合。如图去掉根 结点r，其原来的三棵子树Ta，Tb，Tc的集合Ta，Tb，Tc就为 森林，这三棵子树的具体形态如图（c）。6、有序树和无序树按照树中同层结点是否保持有序性，可 将树分为有序树和无序树。如果树中同层结 点从左而右排列，其次序不容互换，这样的 树称为有序树；如果同层结点的次序任意， 这样的树称为无序树。有序

11、树树中任意节点的子结点之间有顺序关系，这种树称为有序树 无序树树中任意节点的子结点之间没有顺序关系，这种树称为无序树,也称为 自由树， 三）、二叉树的概念二叉树是一种很重要的非线性数据结构，它的特点是每个 结点最多有两个孩子，且其子树有左右之分（二叉树是有序树 ，次序不能任意颠倒）。（二叉树可以每个节点只有一个孩子 ）1、二叉树的递归定义和基本形态二叉树是以结点为元素的有限集，它或者为空，或者满足 以下条件：有一个特定的结点称为根；余下的结点分为互不相交的子集L和R，其中L是根的左子树； R是根的右子树；L和R又是二叉树；？ 二叉树是不是树？二叉树树？由上述定义可以看出，二叉树和树是两个不同的

12、概念树的每一个结点可以有任意多个后件，而二叉树中每个结点 的后继不能超过2；树的子树可以不分次序（除有序树外）；而二叉树的子树有 左右之分。我们称二叉树中结点的左后件为左儿子，右后件为 右儿子。前面引入的有关树的一些基本术语对二叉树仍然适用。下图列 出二叉树的五种基本形态：2、二叉树的两个特殊形态满二叉树： 如果一棵深度为K的二叉树，共有2K-1个结点， 即第I层有2I-1的结点，称为满二叉树。(a)完全二叉树：如果一棵二叉树最多只有最下面两层结点度数 可以小于2，并且最下面一层的结点都集中在该层最左边的若 干位置上，则称此二叉树为完全二叉树（例如下图(b)）满二叉树一定是完全二叉树，完全二叉

13、树不一定是满二叉树3、二叉树的三个主要性质性质1：在二叉树的第i（1）层上，最多有2i-1个结点性质2：在深度为k(k1)的二叉树中最多有2k-1个结点。性质3：在任何二叉树中，叶子结点数总比度为2的结点多 1。n0=n2+1(NOIP9)一个高度为h 的二叉树最小元素数目（ C ）。A） 2h+1 B） h C） 2h-1 D） 2h E） 2h- 1(NOIP8)按照二叉数的定义，具有3个结点的二叉树有（ C ）种 。A）3 B）4 C）5 D）6(NOIP8)设有一棵k叉树，其中只有度为0和k两种结点，设n 0 ， n k ，分别表示度为0和度为k的结点个数，试求出n 0 和n k之间的

14、 关系（n 0 = 数学表达式，数学表达式仅含n k 、k和数字）。 (NOIP7).一棵二叉树的高度为h，所有结点的度为0，或为2， 则此树最少有(B )个结点 （带个数进去试试）A)2h-1 B)2h-1 C)2h+1 D)h+1(NOIP6)已知，按中序遍历二叉树的结果为：abc 问：有多少种不同形态的二叉树可以得到这一遍历结果， 并画出这些二叉树。5种、给出一棵二叉树的中序遍历：DBGEACHFI与后序遍 历：DGEBHIFCA画出此二叉树。 D B GE A C HFID GE B HIF C AA BDEGCFHI1、将一棵有100个结点的完全二叉树从根结点这一层开始， 每一层从左到右依次对结点进行编号，根结点的编号为1， 则编号为49的结点的左孩子的编号为 A 98 B 99 C 97 D 502、对二叉树从1进行连续编号，要求每个结点的编号大于其 左右孩子的编号，同一结点的左右孩子中，其左孩子的编号 小于其右孩子的 编号，则可以采取 C 次序的遍历 方法。A 先序 B中序 C后序 D从根开始的层次遍历3、有n个结点并且其高度为n的二叉树的数目是 A、n B、 2n C、 2n-1 D、