2009年1

【知识点详解】 1. **线性表的删除操作** - 描述中提到的线性表L=(a0,a1,a2,…an-1)用数组表示，删除表中任一元素的概率相同。若删除一个元素，平均移动次数为2。这是因为在一个完全平衡的线性表中，每个元素被删除时，需要将后面的元素向前移动一位来填补空位，平均而言，每个元素后面正好有一个元素需要移动。 2. **栈的性质** - 在栈的题目中： - (2) 入栈和出栈序列问题，对于4个数据元素，可以推导得出有15种不同的出栈序列。 - (3) 栈和队列的操作，根据描述，元素依次通过栈S后再进入队列Q，出队顺序为a3, a6, a8, a7, a5, a4, a2, a1。分析这个过程，可以看出栈S至少需要能容纳4个元素（a1, a2, a3, a4）同时存在，因为a3先出栈进入队列，然后a4、a5、a6再依次出栈进入队列，而a7和a8可以直接出栈进入队列，所以栈的最小容量为4。 3. **图的连通性** - (4) 在具有6个结点的无向简单图中，要确保图一定是连通的，至少需要有6-1=5条边，因为树形结构是最小连通图的形态。 4. **排序算法比较次数** - (5) 直接选择排序的最好情况是每次都能找到当前未排序部分的最小值，比较次数为n(n-1)/2；直接插入排序的最好情况是输入已经有序，比较次数为n-1。 5. **对称矩阵的存储** - (6) 用数组B按行存放对称矩阵A的下三角部分，访问下三角部分的第i行第j列元素，当下标从0开始时，表示为B[i*(i+1)/2+j]。 6. **二叉树的遍历** - (7) 从给定的中序和后序遍历序列，可以反推出先序遍历序列为A, D, B, E, F, C, G。 7. **Huffman树的性质** - (8) 有n个叶子的Huffman树的节点总数为2n-1。 8. **链式结构插入操作的时间复杂度** - (1) 链式结构在第i个位置插入元素的时间复杂度为O(n)，因为可能需要遍历到第i个位置。 9. **循环队列元素计数** - (2) 当front和rear的值分别为121和92时，队列中的元素个数为(rear - front + m) % m = (92 - 121 + 200) % 200 = 71。 10. **森林与二叉树的关系** - (3) 第三棵树的结点个数N3对应于森林转换成二叉树后，根结点的右子树上的结点个数。 11. **关键路径** - (4) 关键路径是指AOE网络中从源点到汇点的最长路径，因为它决定了项目的最短完成时间。 12. **折半查找的时间复杂度** - (5) 折半查找的时间复杂度为O(logn)。 13. **快速排序最坏情况** - (6) 快速排序最坏的情况发生在被排序序列已经逆序时，每次划分只能减少一个元素，导致时间复杂度接近O(n^2)。 14. **二叉树的性质** - (7) 错误的论述是B，因为二叉树的度可以是任意非负整数，包括0，1，和2。 15. **AVL树的插入操作** - 插入关键码序列{ 1，26，3，23，4，24，25 }到AVL树中，每次插入都会涉及到平衡调整，具体操作需要绘制AVL树的结构，这里无法文字描述，建议手动绘制。 16. **序列构建二叉树** - 给定一个元素序列和两种遍历序列，可以唯一确定一颗二叉树，但仅给定先序或中序序列是不足以唯一确定的。