"2012年考研计算机统考408真题"
本资源涉及计算机科学领域的多个方面,包括算法、数据结构、图论、树、排序算法、计算机系统等。以下是对资源中每个问题的详细解释和知识点总结:
1. 算法时间复杂度:该问题考察了算法的时间复杂度计算。要计算算法的时间复杂度,需要分析算法的循环次数和操作次数。这里的算法是计算整数n的阶乘,其时间复杂度为O(n)。
知识点:算法时间复杂度、阶乘计算。
2. 中缀表达式转换:该问题考察了中缀表达式的转换为后缀表达式,以及栈的应用。中缀表达式转换为后缀表达式需要使用栈来存放操作符,栈的最大深度是7。
知识点:中缀表达式、后缀表达式、栈应用。
3. 二叉树遍历:该问题考察了二叉树的前序遍历和后序遍历。给定二叉树的前序遍历序列和后序遍历序列,可以确定根结点的孩子结点。
知识点:二叉树遍历、前序遍历、后序遍历。
4. 平衡二叉树:该问题考察了平衡二叉树的结点数计算。平衡二叉树的高度为6,所有非叶结点的平衡因子均为1,则该平衡二叉树的结点总数为32。
知识点:平衡二叉树、结点数计算。
5. 广度优先遍历:该问题考察了广度优先遍历的算法时间复杂度。对有n个结点、e条边且使用邻接表存储的有向图进行广度优先遍历,其算法时间复杂度是O(n+e)。
知识点:广度优先遍历、算法时间复杂度。
6. 邻接矩阵存储:该问题考察了邻接矩阵存储的特点。若用邻接矩阵存储有向图,矩阵中主对角线以下的元素均为零,则关于该图拓扑序列的结论是存在的且唯一。
知识点:邻接矩阵存储、有向图、拓扑序列。
7. 迪杰斯特拉算法:该问题考察了迪杰斯特拉算法的应用。对有向图,若采用迪杰斯特拉算法求从源点a到其他各顶点的最短路径,则得到的第一条最短路径的目标顶点是b,第二条最短路径的目标顶点是c,后续得到的其余最短路径的目标顶点依次是d、e、f。
知识点:迪杰斯特拉算法、最短路径、有向图。
8. 最小生成树:该问题考察了最小生成树的特点。正确的叙述是最小生成树的代价唯一,所有权值最小的边一定会出现在所有的最小生成树中。
知识点:最小生成树、代价唯一、权值最小的边。
9. B-树删除操作:该问题考察了B-树删除操作的结果。删除关键字78后,得到一颗新B-树,其最右叶结点中的关键字是62、65。
知识点:B-树、删除操作、关键字。
10. 排序算法:该问题考察了排序算法的特点。每一趟排序结束都至少能够确定一个元素最终位置的方法是简单选择排序、希尔排序、快速排序、堆排序、二路归并排序。
知识点:排序算法、简单选择排序、希尔排序、快速排序、堆排序、二路归并排序。
11. 排序算法比较:该问题考察了不同的排序算法之间的比较。折半插入排序和直接插入排序之间可能的不同之处是排序的总趟数、元素的移动次数、使用辅助空间的数量、元素之间的比较次数。
知识点:排序算法比较、折半插入排序、直接插入排序。
12. 程序运行时间:该问题考察了程序运行时间的计算。假定基准程序A在某计算机上的运行时间为100秒,其中90秒为CPU时间,其余为I/O时间。若CPU速度提高50%,I/O速度不变,则运行基准程序A所耗费的时间是60秒。
知识点:程序运行时间、CPU时间、I/O时间。
13. 编译器规定:该问题考察了编译器对变量类型的规定。假定编译器规定int和short型长度分别为32位和16位,执行下列C语言语句:unsigned short x=65530;unsigned int y=x;得到y的机器数为0000 7FFA。
知识点:编译器规定、变量类型、机器数。
14. 浮点数表示:该问题考察了浮点数的表示。float类型(即IEEE754单精度浮点数格式)能表示的最大正整数是2^127-1。
知识点:浮点数表示、IEEE754单精度浮点数格式。
15. 结构体存储:该问题考察了结构体的存储方式。假定编译器规定int型和short型长度分别为32位和16位,并且数据按边界对齐存储。某C语言程序段如下:struct{int a;char b;short c;}record;record.a=273;若record变量的首地址为0xC008,则地址0xC008中的内容及record.c的地址分别为0x11、0xC00E。
知识点:结构体存储、边界对齐存储、C语言程序。
16. 闪存(memory):该问题考察了闪存的特点。错的叙述是信息可读可写,并且读、写速度一样快。
知识点:闪存、读写速度。