数据结构期末复习小总结
目录
例题：后缀算式 9 2 3 + - 10 2 / - 的值是多少，
最小生成树（Kruskal，Prime）及最短路（Floyd，Dijkstra）总结
前言：前几天我还做了两套卷子，但是我们老师出的卷子只有大题，还是分享一下把，做了这两套卷子我觉得要去复习的一些知识点。以及还有一些例题的一些疑惑与讲解。
关于链表的例题：
若用链表存储一棵二叉树时，每个节点除数据域外，还有指向左孩子和右孩子的两个指针，在这种存储结构中，n歌节点的二叉树共有2N个指针域，其中有N-1个指针域存放了地址，有N+1个指针是空指针。
邻接表例题
-
对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有___e___个和____2e___个。
AOV和AOE图的讲解
AOV网和AOE网
AOV 网与拓扑排序
二分查找例题：
其实做这题的时候，我才开始选的是 C，但是答案是D，然后搜了搜，原来，是按照源代码来的
若有18个元素的有序表存放在一维数组A[19]C中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )
前缀，中缀，后缀表达式
前缀表达式的计算机求值：
从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。
例如前缀表达式“- × + 3 4 5 6”：
(1) 从右至左扫描，将6、5、4、3压入堆栈；
(2) 遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素，注意与后缀表达式做比较），计算出3+4的值，得7，再将7入栈；
(3) 接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈；
(4) 最后是-运算符，计算出35-6的值，即29，由此得出最终结果。
后缀表达式的计算机求值：
与前缀表达式类似，只是顺序是从左至右：
从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 op 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。
例如后缀表达式“3 4 + 5 × 6 -”：
(1) 从左至右扫描，将3和4压入堆栈；
(2) 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素，注意与前缀表达式做比较），计算出3+4的值，得7，再将7入栈；
(3) 将5入栈；
(4) 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
(5) 将6入栈；
(6) 最后是-运算符，计算出35-6的值，即29，由此得出最终结果。
例题：后缀算式 9 2 3 + - 10 2 / - 的值是多少，
后缀表达式是遇到符号时，取栈顶元素进行计算，并将结果再次压入栈顶。
9 2 3 + - 10 2 / - 计算过程如下：
9 2 3 入栈
遇到 + 号，取出 2 3 相加，并将结果入栈，结果为
9 5
又遇到 - 号，同理，此时的栈为：
4
再入 10 2, 栈为：
4 10 2
遇到 / 号，栈变更为：
4 5
再遇到 - 号，栈变更为：
-1
后缀表达式结束，所以最终结果为 -1
该后缀表达式还原成中缀表达式为：9 - (2 + 3) - 10 / 2
有向图和无向图的例题：
-
在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。