四川大学期末考试：数据结构与算法试题

"311076040-17181-09B_数据结构与算法1" 这是一份来自四川大学期末考试的闭卷试题，针对2016级软件工程专业的“数据结构与算法”课程。试卷由多项选择题组成，涉及了数据结构和算法的基础知识，包括二叉树的前序遍历和中序遍历的关系，后缀表达式（逆波兰表示法）的转换，以及在一般树中搜索的最坏情况时间复杂性。 1. 题目考察的是二叉树的遍历。前序遍历（Preorder Traversal）是先访问根节点，然后递归地遍历左子树，最后遍历右子树。给定的前序遍历顺序是`ABCDEFG`，问可能的中序遍历（Inorder Traversal）是什么。中序遍历的顺序是左子树-根节点-右子树。因此，正确答案需要找到一个序列，使得按照前序遍历的根节点`A`将序列分成两部分，左边是左子树的中序遍历，右边是右子树的中序遍历。根据二叉树性质，`C`必须位于`A`的左侧，因为它是`A`的左子树的第一个元素，而`D`必须位于`A`的右侧，因为它属于右子树。所以，正确答案是`(D) ADCFEBG`。 2. 这个问题涉及到算术表达式到后缀表达式的转换。后缀表达式（又称逆波兰表示法）是一种没有括号的表达式，运算符位于操作数之后。对于给定的算术表达式`a + b * (c + d / e)`，转换成后缀表达式应该是`abcde/*+`，这意味着先进行括号内的计算，然后乘法，最后加法。所以，正确答案是`(C) abcde/+*+`。 3. 询问在一般树（非平衡的）中搜索的最坏情况时间复杂性。对于一般的非平衡树，搜索可能需要遍历所有节点，因此最坏情况的时间复杂度是线性的，即`(B) n`。 这份试卷主要检验学生对基本数据结构（如二叉树）和基础算法（如树的遍历和后缀表达式）的理解，以及他们在实际问题中的应用能力。通过解决这类问题，学生可以加深对数据结构和算法原理的掌握，这对于未来在计算机科学领域的工作和研究至关重要。