2018计算机考研真题详解：运算、数据结构与算法

2018年计算机考研真题及参考答案涵盖了多个重要的知识点，以下是对部分试题的详细解析： 1. **栈和运算符处理**：题目涉及栈的使用和运算符优先级表达式求值。F()函数通过从S1栈中弹出整数a和b，然后从S2栈中弹出运算符op进行运算，并将结果压回S1。根据给定的栈内容，首先执行F()时，会计算5 * 8 = 40，结果入栈，变为40, 3, 2。第二次F()计算40 - 3 = 37，37压回S1，现在栈顶为37, 2。第三次F()计算37 + 2 = 39，最终栈顶为39。因此，答案是B.15。 2. **队列与栈操作序列**：该问题考察队列和栈的基本操作。根据操作限制，不能得到的输出序列是D.6,5,4,3,2,1，因为如果先出队6，再出队5并入栈，那么5就不可能在队头再次出队。 3. **矩阵存储**：此题考查矩阵的压缩存储，上三角矩阵的存储方式是将对角线以上的元素按行优先顺序存储。对于12x12的矩阵，第6行的元素m6,6应该位于N中的第(6-1)*12+6=55位置，因此答案是C.55。 4. **完全二叉树节点数量**：完全二叉树的性质决定了其非叶结点与叶结点的关系。对于非空完全二叉树，所有叶结点在同一层，非叶结点有2个子结点。若叶结点数为k，从底层到顶层，每一层结点数是前一层的两倍减去1，所以总结点数为k + (k-1) + ... + 1，等于2k - 1。 5. **哈夫曼编码**：这是关于数据压缩中的哈夫曼编码概念。哈夫曼编码通常用来实现最优的二进制编码，每个字符的编码长度与其频率成反比。由于给出的字符频率不同，选项A和B的编码更符合最小带权路径长度的原则，其中A更优。 6. **二叉排序树的性质**：该题考查二叉排序树的性质，即左子树上的所有节点值小于根节点，右子树上的所有节点值大于根节点。根据图示，x1应小于x2、x3和x4，而x2和x3又根据大小关系未知，但x4应小于x3，因此正确答案是B.x1<x4<x5。 7. **有向图拓扑序列**：拓扑序列是指有向图中节点的线性排列，其中从前往后每条边的方向都指向前面的节点。选项C中5->1->2符合拓扑序列的要求，但5->2违反了有向图的顺序，因此不是合法的拓扑序列。 8. **B树的关键字数量**：3阶B树的每个节点最多有3个孩子，高度为5意味着最小度为2。根据B树的性质，根节点最少有两个关键字，其他内部节点至少有3个关键字，叶子节点可能有0或2个关键字。因此，最少的关键字数量为2^(5-1) + 1 = 16 + 1 = 17，选项A、B、D都不正确，答案是C.62，因为62是15（根节点）+ 15（每个内部节点）+ 1（最右边的叶子节点）。 9. **字符串长度与空串**：题目提到的“现有长度为7、初始为空”可能是指一个字符串的长度，但没有提供完整的问题。如果是指一个字符串长度为7，那么可能是关于字符串处理、字符串操作或者字符串相关算法的问题，需要更多上下文才能给出具体知识点。 以上解析涵盖了部分2018年计算机考研真题中的关键知识点，如栈与队列操作、矩阵存储、二叉树结构、图论、数据结构中的哈夫曼编码以及B树等。这些知识点是计算机科学和信息技术领域的重要组成部分，对理解计算机系统设计、算法分析和数据结构有深入学习的价值。