赞
踩
栈和队列的相同点:
栈和队列的不同点:
栈:先进后出;
队列:先进先出。
栈的插入和删除只能在栈的栈顶进行,后进栈的元素必定先出栈,因此把栈又称为FILO表;队列的插入和删除运算分别在队列的两端进行,先进队列的元素必定先出队列,所以又把队列称为FIFO表。
用不带头节点的单链表存储队列,其头指针指向队头结点,尾指针指向队尾结点,则在进行出队操作时,队头、队尾指针都可能要修改(一般只需修改头指针,但当队列里面只有一个元素时需要同时修改尾指针)
循环队列的优点是什么?
循环队列的优点是:它可以克服顺序队列的“假溢出”现象,能够使存储队列的向量空间得到充分利用。
向量、栈、队列都是线性结构,可以在向量的任何位置插入和删除元素;对于栈只能在栈顶插入和删除元素;对于队列只能在队尾插入和队首删除元素。
栈是一种特殊的线性表,允许插入和删除运算的一端称为栈顶。不允许插入和删除元素的一端称为栈底。
在栈的ADT定义中,除初始化操作外,其他基本操作的初始条件都要求栈已存在
在带头结点的链队列中,队头指针指向链表的头结点
栈是实现过程和函数等子程序所必须的结构
两个栈共享空间时栈满的条件是两栈顶指针相邻
多个栈共存时,最好用链式存储结构
进行入栈操作前一定要先判断栈未满
循环队列是队列的一种顺序存储结构
链队列将值x入队前要先申请新空间,赋值,而后入队
一个函数在结束本函数运行之前,直接或间接调用函数自身,称为递归。
递归程序的优点是程序结构简单、易读、清晰、易证明其正确性。缺点是执行中占内存空间较多,运行效率低,不易优化。
递归程序执行中需借助栈这种数据结构来实现
递归程序的入口语句和出口语句一半用条件判断语句来实现
哈夫曼树:在含有n个带权叶子结点的二叉树中,其中带权路径长度(WPL)最小的二叉树称为哈夫曼树。
哈夫曼树的构造过程:
给定n个带权值的结点,将这n个结点分别作为n棵仅含一个结点的二叉树,构造森林F;
构造一个新结点,从F中选取两个根结点权值最小的树作为新结点的左、右子树,并且将新结点的权值置为左、右子树上根结点的权值之和;
从F中删除刚才选出的两棵树,同时将新得到的树加入F中;
重复上述两步,直至F中剩下一棵树为止。
哈夫曼编码的过程:
构造出对应的哈夫曼树;
由于字符结点都出现在叶子结点中。我们将字符的编码解释为从根至该字符的路径上边标记的序列,其中边标记为0表示“转向左孩子”,标记为1表示“转向右孩子”。
完全二叉树:设一个高度为h、有n个结点的二叉树,当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时,称为完全二叉树。
具有n个结点的完全二叉树的高度为log(n+1)向上取整。
深度为k的完全二叉树,其叶子结点必在第k层上,可能在第k或k-1层上。
在有n个结点的二叉链表中,空链域的个数为n+1.
二叉树中每个结点的两棵子树是有序的。
树的度是树中结点的最大度数,而非树的分支数
若一个叶子结点是某二叉树中的中序遍历序列的最后一个结点,则它必是该二叉树的先序遍历序列的最后一个结点。
线索二叉树的左线索指向遍历序列的前驱,右线索指向其遍历序列的后继
二叉树的后序遍历序列中,任意一个结点均处在其孩子结点的后面。
度为2的有序树是二叉树的说法是错误的(有序树的结点次序是相对于另一结点而言的,若有序树的子树中只有一个孩子时,这个孩子的结点无须区分左右次序)
m个结点进行k路归并,为实现最佳归并(带权路径长度最小),若(m-1)%(k-1) = 0,不需要加虚段,否则第一次构造时要使用(m-1)%(k-1)+1个结点
当结点数目一定时具有最小深度的二叉树是完全二叉树
若二叉树采用二叉链表存储结构,要交换其所有分支结点左、右子树的位置,利用前序、后序遍历方法最合适
二叉树在线索化后,仍不能有效求解的问题是后序线索二叉树中求后序后继
由n个结点可以构造出的树的数量与n-1个结点构造二叉树的数量相同
具有n个结点,其路径长度最短的二叉树是完全二叉树
判断是否为哈夫曼编码时,除了判断是前缀编码外,还得符合哈夫曼树构造规则
树与二叉树是两种不同的树形结构,二者不存在谁是谁的特殊情况
只有对完全二叉树编号时,其结点下标才有规律,否则慎重思考
同一层上的各个结点不一定存在兄弟关系,存在兄弟关系的一定有相同的双亲
树的双亲表示法中兄弟节点的编号不一定时连续的
并非所有二叉树的后序线索树进行后序遍历时都必须用栈,任意结点只有左子树就不用栈
树只有先根遍历和后根遍历
对于一个具有n个结点的二叉树,当它为一棵完全二叉树时具有最小高度,当它为一棵高度为n的二叉树时,具有最大高度
哈夫曼树是带权路径长度最小的二叉树
树的孩子兄弟链表表示法和二叉树二叉链表表示法,本质上是一样的,只是解释不同,也就是说,树是森林的特例,它可用二叉树唯一表示,并可以使用二叉树的一些算法去解决树和森林的问题。
树和二叉树均属于树形结构,其区别有三:一是二叉树的度之多为2,树无此限制;二是二叉树有左右子树之分,即使在只有一个分支的情况下,也必须指出是左子树还是右子树,树无此限制;三是二叉树允许为空,树一般不允许为空。
二叉树不是树的特例。
完全二叉树的最后一个非终端结点的序号即完全二叉树最后结点的双亲结点。
一个带权的无向连通图存在权值相同的多条边时,最小生成树可能不唯一。
拓扑排序:由一个有向无环图的顶点组成的序列,当且仅当满足下列条件时,称为该图的一个拓扑排序
每个顶点出现且仅出现一次;
若顶点A在序列中排在顶点B的前面,则在图中不存在从顶点B到顶点A的路径。
(由集合上的一个偏序关系得到整个集合上的一个全序,这个操作称为拓扑排序)
拓扑排序应用于判断图中是否有环。
若一有向图的邻接矩阵中对角线以下元素均为0,则该图的拓扑序列必存在。
在一个无向图中,所有顶点的度数之和等于图的边数2倍;在一个有向图中,所有顶点的度数之和等于图的边数。
求最小生成树时,权值为负不会对结果产生影响。
求最短路径的Dijkstra算法不适用边上带有负权值的图,Floyd算法允许图中有带负权值的边,但不允许有包含带负权值的边组成的回路。
最小生成树:连通图的生成树为包括连通图的所有顶点,且任意两顶点有且仅有一条通路的图。在这个生成树集合中边的权值之和最小的那棵生成树称为连通图的最小生成树。
权值互不相等的最小支撑树唯一吗?给出理由。
假设存在两棵不同的最小支撑树T1、T2,如果从T1中找出一条边e不在T2中且权值尽可能的小。将e加入T2中,此时图T2+e肯定有一个环。
a) 若该环中每条边都比e小,则这些边应当在T1中,此时T1中存在环,不是支撑树,矛盾;
b) 若环中至少存在一条边必e大,将这条边去掉后形成新的图T3仍是一棵生成树,且权值必T2小,此时T2不是最小支撑树,矛盾。
综上所述,当图中边的权值互不相等时,最小支撑树唯一。
a) 二叉检索树不会有冲突,这意味着我们额能够保证二叉检索树的插入和查找操作一直都是O(logn)的时间复杂度;
b) 二叉检索树的空间占用和输入的数据一致,故不需要为其预先分配空间;
c) 所有元素在树中是排好序的;
总的来说,如果进行动态查找,二叉检索树是一个折中的选择。
a) 堆中某个节点的值总是不大于或不小于其父节点的值;
b) 堆总是一棵完全二叉树。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。