2015年考研计算机专业基础综合真题解析

### 2015年考研计算机专业基础综合真题解析 #### 考查知识点概述 根据提供的2015年全国硕士研究生入学统一考试计算机学科专业基础综合试题的部分内容，我们可以归纳出以下考查的知识点： 1. **栈的基本概念和函数调用的原理** 2. **二叉树的基本概念及计数方法** 3. **哈夫曼树的基本原理** 4. **AVL树（平衡二叉树）的概念与性质** 5. **图的深度优先遍历** 6. **最小生成树算法（Prim与Kruskal算法的区别）** 7. **二分查找算法** 8. **模式匹配（KMP）算法** 9. **排序算法的特性及其比较** 10. **最小堆的概念及调整** 11. **希尔排序的基本思想与实现** 12. **计算机硬件与机器语言的关系** 13. **二进制补码表示法** 14. **浮点数加减运算的相关规则** 接下来，我们将逐一详细解释这些知识点。 ### 栈的基本概念和函数调用的原理 **栈**是一种后进先出（Last In First Out, LIFO）的数据结构，常用于函数调用时参数传递、返回地址存储等。在C++中，当函数被调用时，系统会自动为每个函数创建一个栈帧，用来存储局部变量、参数和返回地址等信息。函数调用的顺序决定了栈帧的存储顺序，即先调用的函数的栈帧存储在后调用的函数之前。因此，对于题目中的函数调用顺序，正确答案为D：S(1)->S(0)->main()，因为函数s()是递归调用自身，先调用s(1)，再调用s(0)，最后返回到main()。 ### 二叉树的基本概念及计数方法 **不同二叉树的个数**可以通过卡特兰数计算得出。题目中提到的是一颗具有特定先序序列的二叉树，根据先序序列构造不同的二叉树，关键在于如何确定左右子树的划分。对于有n个节点的二叉树，不同形态的二叉树数目可以通过卡特兰数计算，本题的答案是15种，即C项。 ### 哈夫曼树的基本原理 **哈夫曼树**也称为最优二叉树，它是由给定的权重集合构建的一类特殊的二叉树。在哈夫曼树中，权值较小的节点往往靠近叶子节点。题目中给出了两组路径上的权值序列，要求判断是否可以属于同一棵哈夫曼树。通过分析，只有选项C的两个序列可以满足哈夫曼树的构建条件，即24,10,10和24,14,11，这是因为在这两个序列中，从根节点到叶子节点的路径上的权值之和是相等的，并且权值较小的节点更靠近叶子节点。 ### AVL树（平衡二叉树）的概念与性质 **AVL树**是一种特殊的二叉搜索树，其特点是任何节点的两个子树的高度差至多为1。题目中提到，如果一棵AVL树经过中序遍历可以得到一个降序序列，那么这棵树中的最小元素一定是叶节点。这是因为AVL树的中序遍历序列是升序的，而题目中的条件为降序，因此最小的元素出现在序列的末尾，也就是树的最右边，而AVL树中的最小元素一定位于最左边，这意味着这棵树实际上是反向构造的，所以最小元素一定是叶节点。 ### 图的深度优先遍历 **深度优先遍历**是一种图的遍历算法，它按照深度优先的原则访问图中的节点。题目中的图是一个简单的有向图，从V0开始进行深度优先遍历，可以得到多种不同的遍历序列。由于图中存在多个从V0出发可达的顶点，故遍历结果可能存在多种情况，本题答案为D：5种可能的遍历序列。 ### 最小生成树算法（Prim与Kruskal算法的区别） **最小生成树算法**包括Prim算法和Kruskal算法两种。这两种算法都可以找到图的最小生成树，但是它们的工作机制有所不同。Prim算法是从一个节点开始，逐步添加边直到形成一棵包含所有节点的树；而Kruskal算法则是按边的权重从小到大排序，逐条加入边直到形成一棵包含所有节点的树。题目中给出了一张带权图，要求找出在使用Kruskal算法时第二次选中的边以及Prim算法（从V4开始）第二次选中的边。根据两种算法的特点，答案为A：(V1,V3)。 ### 二分查找算法 **二分查找算法**是一种在有序数组中查找指定元素的有效方法。算法的核心思想是在每次查找时都将查找区间减半。题目中给出了一组关键字比较序列，要求判断哪个序列不符合二分查找的要求。分析可知，选项A中的序列500，200，450，180不符合二分查找的要求，因为在中间值200的右侧出现了比200小的值450，故正确答案为A。 ### 模式匹配（KMP）算法 **KMP算法**是一种高效的字符串匹配算法，它可以有效地处理模式串与文本串之间的匹配问题。题目中给出了一段文本串和模式串，要求判断第一次出现失配时的下一次匹配位置。根据KMP算法的原理，当首次出现失配时，根据失配的位置调整模式串的起始位置，从而避免了不必要的比较。本题答案为C：i=5，j=2。 ### 排序算法的特性及其比较 **排序算法**有很多种，如直接插入排序、冒泡排序、基数排序、快速排序等。题目中要求找出一种排序算法，其中元素的移动次数与关键字的初始排列次序无关。在这些排序算法中，只有冒泡排序的移动次数与初始排序无关，因为冒泡排序只会在相邻元素之间进行交换，不论数据初始状态如何，每次比较都会确保较大的元素向后移动，因此移动次数与初始状态无关，答案为B：起泡排序。 ### 最小堆的概念及调整 **最小堆**是一种特殊的数据结构，其中每个父节点的关键字小于或等于其子节点的关键字。题目中给出了一棵小根堆，要求在删除根节点后重新构建堆的过程中需要比较的关键字数量。根据最小堆的性质，删除根节点后需要调整堆结构，以恢复堆的性质。在本题中，删除根节点后需要比较两次，答案为B：2。 ### 希尔排序的基本思想与实现 **希尔排序**是一种基于插入排序的改进算法。它的基本思想是首先将整个待排序序列分割成若干个子序列，分别进行直接插入排序，然后依次缩减增量再进行排序，直到增量为1，最后对整个序列进行一次直接插入排序。题目中要求填入希尔排序中组内排序采用的方法，根据希尔排序的基本思想，答案为A：直接插入排序。 ### 计算机硬件与机器语言的关系 **机器语言**是一种可以直接被计算机硬件识别和执行的语言。题目中询问哪些程序可以直接被计算机硬件执行。根据计算机系统的架构，只有机器语言程序可以直接被硬件执行，答案为A：仅Ⅰ。 ### 二进制补码表示法 **二进制补码**是计算机内部表示有符号整数的一种方式。题目中要求计算由3个“1”和5个“0”组成的8位二进制补码所能表示的最小整数值。根据补码表示法，该数的最高位为1，表示负数，其余位为正数部分。将该数转换为十进制，最小整数值为-125，答案为B：-125。 ### 浮点数加减运算的相关规则 **浮点数加减运算**涉及到对阶、尾数运算、规格化等一系列步骤。题目中给出了一些关于浮点数加减运算的描述，要求判断哪些描述是正确的。根据浮点数加减运算的规则，选项Ⅰ、Ⅱ、Ⅲ、Ⅳ都是正确的描述，但是题目只允许选择两项，因此正确答案为：Ⅱ.右规和尾数舍入都可能引起阶码上溢；Ⅲ.左规时可能引起阶码下溢。 以上就是针对2015年考研计算机专业基础综合真题解析中涉及的知识点的详细说明。