34. 叙述树的定义及其逻辑特征
树是n（n≥0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n>1时，其余结点被分成m（m>0）个互不相交的子集T1,T2,...,Tm，每个子集又是一棵树。
树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。 树中所有结点可以有零个或多个后继结点
35. 叙述二叉树的定义及其逻辑特征
二叉树：
a) 每个结点最多有两棵子树； b) 子树有左右之分。
二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。即使结点只有一棵子树也要区分是左子树还是右子树。
36. 什么是满二叉树和完全二叉树
满二叉树： 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。 完全二叉树 叶子结点只出现在最下层和次最下层，且最下层的叶子结点集中在树的左部的二叉树。
37. 叙述实现顺序存储二叉树的方法
a) 对于完全二叉树和满二叉树：按照二叉树结点从上至下、从左到右的顺序依次把各
结点存储到一组连续的存储单元中。由二叉树的性质知，完全二叉树和满二叉树中结点的序号可以唯一地反映出结点之间的逻辑关系。可以利用数组元素的下标值确定结点在二叉树中的位置及结点之间的关系。 b) 对于一般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在
一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系。可通过增添一些并不存在的空结点，使之成为一棵完全二叉树后，再用一维数组顺序存储。
38. 什么是树的先序遍历，中序遍历，后序遍历
(1)先序遍历
若二叉树为空，则结束遍历操作；否则访问根结点；遍历左子树；遍历右子树。
(2) 中序遍历
若二叉树为空，则结束遍历操作；否则遍历左子树；访问根结点；遍历右子树。
(3) 后序遍历
若二叉树为空，则结束遍历操作；否则遍历左子树；遍历右子树；访问根结点。
39. 叙述哈夫曼树的定义
哈夫曼树又称为最优二叉树:由n个带权叶结点构成的所有二叉树中带权路径长度WPL最小的二叉树。
40. 叙述构造一棵哈夫曼树的方法
构造哈夫曼树的过程：
1.将给定的n个权值{w1,w2,...,wn}作为n个根结点的权值构造一个具有n棵二叉树的森林{T1,T2,...,Tn}，其中每棵二叉树只有一个根结点；
2.在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新二叉树，新二叉树的根结点权值为这两棵树根的权值之和；
3.在森林中，将上面选择的这两棵根权值最小的二叉树从森林中删除，并将刚刚新构造的二叉树加入到森林中；
4.重复上面（2）和（3），直到森林中只有一棵二叉树为止。这棵二叉树就是哈夫曼树。
41. 举例说明图的三种表示方法
几何表示法：
集合表示法：
图G1的顶点集和边集分别为： V(G1)={v1,v2,v3,v4,v5}
E(G1)={(v1,v2),(v2,v5),(v1,v4),(v3,v4),(v3,v5)} 矩阵表示法：
42. 给出一个图的最小生成树
设G=（V，E）是一带权图，其中V为G中所有顶点的集合，E为G中所有带权边的集合。T=（U，TE）为将要构造的生成树，其中集合U用于存放G的最小生成树中的顶点，集合TE存放G的最小生成树中的边。令集合U的初值为U＝{u1}（假设构造最小生成树
时，从顶点u1出发，且u1∈V），集合TE的初值为空集。 普里姆算法描述如下：
(1)U={u1},TE=Ф;
(2)选择权数最小的边(u，v)，其中u∈U, v∈V-U,将v加入U中，(u，v) 加入TE中； (3)重复步骤 (2)，直至U=V为止，这时最小生成树构造完毕，集合TE中包含了最小生成树的所有边。
43. 给出一个图中一顶点到其他顶点的最短路径
著名科学家迪杰斯特拉提出一个按路径长度递增的次序产生最短路径的算法。描述如下（假设顶点个数大于1）：
(1) 设置顶点的集合S和T＝V－S，S中存放已找到最短路径的顶点，T存放还未找到最短路径的顶点。初始时，S={v0},仅包含源点v0；
(2) 计算v0到T中各顶点的最短路径长度值：若T中顶点u与v0相连，则v0到该顶点的最短路径长度值为该边的权值，否则v0到该顶点的最短路径长度为∞。
(3) 从T中选择一个从v0到T中各顶点的最短路径长度值中值最小的顶点u，将u加入到S中；
(4) T=V-S, 若T为空，则求解完成，转 (6);
(5) 计算v0经过顶点u到达T中各顶点的最短路径长度是否比原先的长度值小，若是则用新的最短路径长度修改原长度的值，转 (3)； (6) 输出v0到各顶点的最短路径及其长度值。
44.叙述基本的排序方法
直接插入排序方法
先将存放于数组中的第一个数据元素看成是一个有序的子序列，然后从第2个数据元素起逐个按序插入到有序子序列中，直到整个序列有序为止。
冒泡排序方法（设用r[1],r[2],···,r[n]存放待排序数列） 对r[1],r[2],···,r[n]依次比较相邻的两个数据，遇到r[i] >r[i+1] 时，交换r[i]和r[i+1]中的数据，使较大的数不断向后移动，结果使r[n]中存放数列中最大的一个数；不再考虑r[n]，对r[1],r[2],···,r[n-1] 重复上述过程，使得r[n-1]中存放r[1]~r[n-1]中最大一个数；如此重复，直到剩下一个数r[1]时，n个数已在 r[1],r[2],···,r[n]中有序（为升序）。
快速排序 取出待排序数列中第一个数，经过与其它各数的比较和必要的移动，让小于该数的排在其前，大于该数的排在其后，其结果既确定了该数在有序数列中的位置又把数列划分为大于和小于该数的两个部分。再对各部分重复上述过程，直到整个序列有序为止。
44. 数据库基本概念
数据处理
数据处理是指将数据转换成信息的过程，即对数据进行收集、组织、整理、加工、存储和传播等一系列活动过程。数据处理的过程主要包括数据管理——收集信息、表示数据、组织和保存数据；数据加工——对数据进行变换、抽取和运算；数据传播——在空间或时间上以各种形式传播信息（不改变数据的结构、性质和内容）。通过数据管理获得数据；通过数据加工得到更有用的数据（以指导或控制人的决策行为或事物的变化趋势）；通过数据传播，使更多的人共享信息。
数据库
数据库是长期储存在计算机内的、有组织的、可共享的数据集合，也是现实世界中相互关联的大量数据及数据间关系的集合
数据库管理系统
数据库管理系统是一个通用的软件系统，是位于用户和操作系统之间的数据管理软件,由一组计算机程序构成。数据库管理系统是数据库系统的一个重要部分，具有数据定义功能、数据操纵功能、数据库的运行管理、数据库的建立和维护功能。
E-R图
E-R图提供了表示实体型、属性和联系的方法： （1）用长方形表示实体集，长方形内写明实体集名。
（2）用椭圆形表示实体集的属性，并用线段将其与相应的实体集连接起来。
（3）用菱形表示实体集间的联系，菱形内写上联系名，用线段分别与有关实体集连接起来，在线段旁标出联系的类型。如果联系具有属性，则该属性仍用椭圆框表示，仍需要用线段将属性与其联系连接起来。
相关推荐：
loading