计算机算法知识

4计算机算法知识：

  A：算法特点：算法的改进，在很大程度上推动了计算机科学与技术的进步；判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性；目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法；

   B：采用比较为主要操作的算法是：冒泡、插入、选择排序

9、函数或表达式：

      A：PASCAL语言中，表达式（21XOR 2）的值是（23）

B：PASCAL语言，判断a不等于0且 b不等于0的正确的条件表达式是（a<>0）and(b<>0)

5、数据结构基础：

      A：栈的出入顺序是先进后出，队列是先进先出；例如：某个车站呈狭长形，宽度只能容下一台车，并且出入口是一个。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进、出、进、进、进、出、出、进、进、出、出”。假设车辆入站的顺序为1，2，3，4，5，6，7则车辆出站的顺序为（1，4，3，7，6）。

B：高度为N的均衡的二叉树是：如果去掉叶结点及相应的树枝，它应该是高度为N-1的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有2381个结点，则该树的树高为（11）。

C：（1）结点的度：一个结点的子树数目称为该结点的度（区分图中结点的度）。图中，结点i度为3，结点t的度为2，结点b的度为1。显然，所有树叶的度为0。（2）树的度：所有结点中最大的度称为该树的度(宽度）。（3）树的深度（高度）：树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的儿子在第二层，其余各层依次类推。图中的树共有五层。在树中，父结点在同一层的所有结点构成兄弟关系。树中最大的层次称为树的深度，亦称高度。

D：树的表示除自然界的树形表示法外（画图）还有括号表示法：先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。例如图可写成如下形式（r（a（w，x（d（h），e）），b（f），c（s，t（i（m，o，n），j），u）））

E：二叉树的递归定义和基本形态：二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件：⑴有一个特定的结点称为根；⑵余下的结点分为互不相交的子集L和R，其中L是根的左子树；R是根的右子树；L和R又是二叉树；

F：二叉树的两个特殊形态：

⑴满二叉树：若深度为K的二叉树，共有2K-1个结点，即第I层有2I-1的结点，称为满二叉树。

⑵完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树

G：二叉树的三个主要性质：

性质1：在二叉树的第i（≥1）层上，最多有2i-1个结点

性质2：在深度为k(k≥1)的二叉树中最多有2k-1个结点。

性质3：在任何二叉树中，叶子结点数总比度为2的结点多1。n0=n2+1

H：二叉树的遍历是不重复地访问二叉树中的每一个结点。在访问到每个结点时，可以取出结点中的信息，或对结点作其它的处理。如果用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，限定先左后右的次序，三种组合DLR、LDR、 LRD；这三种遍历规则分别称为先（前）序遍历、中序遍历和后序遍历（以根为标准）。

样题：1、给出一棵二叉树的先序遍历：ABCDEFGH中序遍历：CBEDAGHF并写出后序遍历结果。

2、已知一棵二叉树，其中序与后序遍历为：中序遍历:CBGEAFHDIJ后序遍历:CGEBHFJIDA求先序

file:///C:/Users/20901/AppData/Local/Temp/msohtmlclip1/01/clip_image002.gif

前序遍历    前序遍历的规则如下：    若二叉树为空，则退出。否则       ⑴访问处理根结点；   ⑵前序遍历左子树；   ⑶前序遍历右子树；            a b d e h i c f g

中序遍历

中序遍历的规则如下：

    若二叉树为空，则退出；否则

⑴中序遍历左子树；⑵访问处理根结点；

⑶中序遍历右子树；

若中序遍历上图中的二叉树，可以得到如下的中序序列：    d b h e i a f c g

后序遍历

后序遍历的规则如下：

     若二叉树为空，则退出；否则

⑴后序遍历左子树；⑵后序遍历右子树；

⑶访问处理根结点；

   若后序遍历上图中的二叉树，可以得到如下的后序序列    d h i e b f g c a