2243计算机软件基础(一)复习资料5

73、循环队列空的条件是：front=rear

  满的条件是：front=（rear+1）%m

74、循环队列中的元素个数为：（rear- front + m）%m

75、求元素A_i,j的地址一般形式为：

       数组首地址+A_i,j元素前已存入元素的个数*各元素的字节数。

76、所谓的压缩存储是指对零元素不分配空间,相同元素只分配一个空间。

77、三对角阵公式：已知i和j，求k=2i+j

已知k，求i=(k+1)/3向下取整

已知k，求j=k-2*i

78、下三角阵公式：已知i和j，求k=i(i+1)/2+j  (i≥j)

79、上三角阵公式：已知i和j，求k=i(2n-i+1)/2+j-i  (i≤j)        

80、对称阵公式：可按下三角阵公式或上三角阵公式储存

81、树的有关名词：节点的度：节点的孩子称为节点的度。

树的度：树中节点最大的度为该树的度。

叶子节点：度为0的点称为叶子节点。

双亲节点：一个节点的双亲节点是这个节点的父亲节点。

树的高度：树的层数为树的高度。

82、树和二叉树的区别是：⑴树不能是空的，但二叉树可以是空的

    ⑵树是无序的，而二叉树则是有序的

83、二叉树的几个性质是：

⑴、二叉树的第i层上，最多有2^i-1个结点

⑵、深度为k的二叉树上最多有2^k-1个结点

⑶、二叉树上n₀=n₂+1

⑷、具有2^k-1个结点的二叉树是滿二叉树

⑸、滿二叉树的最下层自右至左连续缺n个结点的二叉树为完全

二叉树

⑹、完全二叉树上它的左孩子为2i(当2i≤n)，右孩子为2i+1(2i+1≤n), 当i＞1根为i/2取整，当i=1根为i

⑺、完全二叉树的深度为log₂ⁿ取整+1

84、一棵有1000个结点的完全二叉树其n₀=500,n₁=1,n₂=499,h=10

85、n个结点的二叉树共有2n个指针域，其中n-1为孩子指针域

　　n+1为空指针域

86、二叉树的三种基本遍历方法：先序遍历、后序遍历和中序遍历。

87、树的储存结构有：双亲表示法、孩子链表示法和孩子兄弟链表示法三种

88、哈夫曼树的性质：答：1）、给定权值的哈夫曼树不唯一；2）权值越大的节点离根节点就越近。3）、哈夫曼树中无度为1的节点。4）、哈夫曼树节点总个数n=2x叶子节点个数-1=2x权值个数-1=2n₀-1。

89、哈夫曼树是一棵带权路径长度总和最小的二叉树

90、哈夫曼树的应用是：分类判定树和哈夫曼树

91、图G是由顶点集合V和边集合E组成，记为G=(V，E)，图有有向图和无向图两种。

91、对有向完全图其边数e=n(n-1)；对无向完全图其边数为e=n(n-1)/2

    图中顶点与度的关系为：e=图中各顶点度数和的一半

92、图的储存结构有：邻接矩阵和邻接表两种，无向图和完全有向图的邻接矩阵是：一个对称矩阵

93、有向图的邻接矩阵中，有e个非0节点，n ²-e个0节点；无向图的邻接矩阵中，有2e个非0节点，n ²-2e个0节点；

94、有向图的邻接表中，有e个表节点，n +e个节点；无向图的邻接矩阵中，有2e个表节点，n +2e个节点；

95、图的遍历有：深度优先遍历和广度优先遍历两种，并在邻接矩阵下两种遍历都是从最小顶点序号开始的；

96、一个图的生成树只有n个顶点和n-1条边，可通过深度优先遍历和广度优先遍历得到图的生成树

97、最小生成树是指图中各边权值最小的生成树，构造最小的生成树的算法有普里姆算法和克鲁斯卡尔算法两种

98、拓扑排序的前提条件是：AOV网中不存在回路

99、常用的查找方法有：顺序查找、折半查找和二叉排序树上的查找三种

100、顺序查找的时间复杂度为：O（n），折半查找的平均查找长度为：ASL=log₂ ⁽ⁿ⁺¹⁾-1，但只限于顺序储存的有序表同，二叉排序树上的查找的平均查找长度也是ASL=log₂ ⁽ⁿ⁺¹⁾-1，但二叉排序树是一种动态储存结构，进行插入删除操作比较方便，而折半查找采用的是静态储存结构，进行插入删除操作时要移动表中的元素。