重庆邮电大学2017年数据结构考研真题

"这是一份来自重庆邮电大学的2017年数据结构硕士研究生入学考试试题，包含了选择题和可能涉及的知识点，如时间复杂度分析、链表特性、栈的操作、循环队列的判断、字符串操作以及二叉树的高度和遍历等。" 在数据结构的学习中，这些题目涵盖了多个核心概念： 1. 时间复杂度分析：题目中的第一道选择题涉及到嵌套循环的时间复杂度计算，正确的答案是D.O(m*n)，这是因为在两个嵌套循环中，外层循环执行n次，内层循环执行m次，总共执行m*n次。 2. 链表特性：链表是一种动态数据结构，它的主要特点是插入和删除操作不需要移动元素，因此选项B正确。而链表不支持随机访问，所以选项A错误。 3. 栈的操作：栈是一种后进先出（LIFO）的数据结构。如果输出序列的第一个元素为n，那么第二个输出元素可能是n-1，因为栈顶元素通常是最后压入的，但具体取决于栈的具体操作，所以选项D“都有可能”是正确的。 4. 循环队列的判断：当队列满时，如果队列采用循环结构，判断条件通常为Q.front == (Q.rear + 1) % m，所以选项C是正确的。 5. 字符串定位：第五题涉及到的是子串在主串中首次出现的位置，这是子串定位问题，选项D正确。 6. 矩阵存储：矩阵的行优先存储方式意味着按照从左到右、从上到下的顺序存储，根据题目中的信息，可以推算出矩阵元素的地址，但具体的计算需要更多上下文，这里给出的是一个例子，答案是C.1108。 7. 二叉树高度：一棵包含18个节点的二叉树，如果是最矮的形态，即完全二叉树，其高度应该是log2(18)+1，取整后为5，因此选项C正确。 8. 二叉树的遍历：后序遍历的顺序是左子树 -> 右子树 -> 根节点，对于顺序存储的二叉树，需要对存储的节点序列进行特定的遍历算法来还原原始二叉树的结构，然后进行后序遍历。 以上是题目中涉及的数据结构基本知识点的解析。数据结构是计算机科学的基础，理解和掌握这些概念对于编程和算法设计至关重要。通过解决此类试题，考生可以检验自己对这些概念的理解程度，并提升问题解决能力。