自考数据结构02331知识点

《自考数据结构02331知识点》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、1、二叉树并非是树的特殊情形，它们是两种不同的数据结构。2、在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。3、在直接插入排序中，每次取出的未排序数字是从后往前依次比较的。如：对于记录(54,38,96,23,15,72,60,45,83)，当把第7个记录60插入时，需比较3次。解：前6个已排序好记录15,23,38,54,72,96，所以从后往前要比较96,72和54。在快速排序中，前后的i和j是从后面的j开始比较的，比较者不动，被替换者后(前)移如：对于记录(51,22,83,46,75,18,6

2、8,30)解：第一趟划分：哨兵R[0]=i=51,先从j=30比较，30<51,30替换51，i=22，i≯51，后移i=83,83>51,83替换30，j=68，依次继续。冒泡排序中，最好与最坏时间复杂度不相同。无论待排序列是否有序(即不受数据初始状态影响)，时间复杂度都是O(n2)的排序算法是直接选择排序。记录关键字比较次数与记录的初始排列次序无关的是直接选择排序。在待排序的记录关键字序列基本有序的前提下，效率最高的排序方法是直接插入排序，效率最低的是快速排序。2013.1.23对同一个基本有序的待排序序列分别进行堆排序、快速排序和冒泡排序，最省时间的是4、对于哈夫曼编码，应该先构造哈夫

3、曼树：每次取权值最小的两个结点(包含新生成的结点)放一起生成新结点。至于左右孩子之分，按照编码字出现的先后顺序去决定(还是左小右大)。关于哈夫曼树的一些解释：哈夫曼树不唯一，和你左右子树的编码有关。但最小带权路径长度唯一。你记住每次都是从集合中寻找两个最小元素，权值相加之后形成的那个元素得重新放入集合参与新的比较。递归下去生成的树才没有问题，否则弄不好就是一个单枝树上去了。你最好采取我建议的规则，自己设置一个优先级。譬如你新生成的节点的权值和原集合的某各节点的权值相等的时候。新生成的节点具有高结合优先级。这样便于做出和标准答案一致的解。5、堆排序中的初始堆就是第一次将最大值放在根上的堆，然后

4、才是第一次、第二次重建堆。线性探查法的散列表6、对称矩阵中的上三角是右上三角，下三角是左下三角。如果二叉树的每个非叶结点都有非空的左子树和右子树，那么这样的二叉树称为严格二叉树。7、三元组表的行表：每一行矩阵的非零元素在三元组表的起始位置。8、队列的队尾指针rear指向队尾元素的下一个位置。9、采用邻接矩阵存储有向图，则结点k对应的入度等于A中结点k对应的列元素之和。10、栈顶指针指的是栈顶元素，顺序循环队列的队尾指针始终指向队尾元素的下一个位置。链队列不区分普通和循环，链队列的尾指针指的就是队尾的元素。注意头结点和队头结点的区别，p78页。链队列一般是不带头结点的，但和单链表类似，为了简化

5、边界条件的处理，在队头结点之前也附加一个头结点，并设队头指针指向此结点。链式存储的栈，其链头即为栈顶。11、循环队列当前元素个数公式（rear-front+m）%m，其中+m的意义是有可能rear已经跑到了front前面的小数字，所以要+m。12、哈夫曼树编码树上的0和1是在分支上，不是在结点上，一定要记住，不然就会陷入迷茫。13、前序遍历一棵树等价于前序遍历该树对应的二叉树，后序遍历一棵树等价于中序遍历该树对应的二叉树。14、两个算法没有什么太多的联系，只能说是想法类似，都用了一定程度的贪心思维。最短路径是要求一点到另外的点的最短路径，只要最短的长度到达就好，除了出发点和终点外一概不管。如

6、果不求一点到所有点的最短路，甚至可以不管所有点是否都联通。最小生成树则要保证第一所有点都是联通的，不然就称不上是树了，而后保证树的边长度之和最小。15、任何一个非空广义表的表头可以是原子，也可以是子表，而其表尾必定是子表。16、为了克服顺序存储分配固定空间所产生的溢出和空间浪费问题。可采用链式存储结构来存储栈。链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。其插入和删除操作进限制在表头（栈顶）位置。17、用普里姆算法和克鲁斯卡尔算法构造的最小生成树，所得到的最小生成树可能相同，也可能不同。这是由于最小生成树不唯一。18、二叉排序树的插入一定是个叶子节点。19、线索二叉树中的

7、线索是指指针。20、一个图的邻接矩阵表示唯一，邻接表表示不唯一。21、稀疏矩阵在用三元组表示时，还必须将稀疏矩阵的总行数、总列数和非零元素个数作为三元组的辅助属性加以说明。所以它的存储还要在加上三个整数的位置。