专升本数据结构考前必看.doc

数据结构是计算机科学中至关重要的基础课程，尤其对于准备专升本考试的学生来说，掌握好数据结构的知识至关重要。本文将详细解析文档中的关键知识点，并展开讨论相关理论。 1. 栈与队列： 栈是一种后进先出（LIFO）的数据结构，允许在栈顶进行插入（压栈）和删除（弹栈）操作。队列则是先进先出（FIFO）的数据结构，允许在队尾进行插入（入队）操作，在队头进行删除（出队）操作。栈和队列都是线性表的特例，广泛应用于算法设计中，如表达式求值、递归、内存管理等场景。 2. 栈操作序列的合法性： 合法的栈操作序列应满足两个规则：一是栈操作的次数（S 和 X 的总数）相等，因为每插入一个元素，就必须有一个相应的删除操作；二是从序列的任意位置开始，S 的数量都应大于等于 X 的数量，以确保任何时候栈中都不为空。 3. 栈实现序列转换： 对于特定输入序列，可以通过不同的栈操作顺序得到不同的输出序列。例如，输入序列123456不能直接转化为435612，因为12必须保持原来的顺序，但在栈中无法实现。而通过适当的操作，可以将123456转化为135426。 4. 顺序存储队列的管理： 顺序存储队列使用一维数组表示，队头和队尾由指针标识。队空的条件是front等于-1，队满的条件是rear等于m-1（假设数组大小为m）。为了避免假溢出，可以采用循环队列，使得队列首尾相连，这样当rear再次指向front时，不是队满，而是队空。另外，可以设置标记tag来区分队空和队满。 5. 双端队列的输出序列： 双端队列允许在两端进行插入和删除操作，输入受限双端队列意味着只能在队尾插入，输出受限则只能在队头删除。例如，序列4132只能由输入受限的双端队列得到，因为4必须最先输出，而4213只能由输出受限的双端队列得到，因为4不能先于2输出。序列4231既不能由输入受限双端队列也不能由输出受限双端队列得到，因为它违反了双端队列的操作规则。 6. 字符串操作： 空格串由多个空格组成，空串则没有任何字符。字符串连接操作/*，如果S1/*S2=S2/*S1成立，可能的情况包括：两串为空、一串为空、两串相等或一串是另一串的整数倍。 7. 二维数组的存储： 二维数组A[m][n]中，元素A[i][j]的位置可以通过计算得出。例如，如果A[0][0]在644，A[2][2]在676，每个元素占一个空间，那么A[3][3]的位置可以通过公式Loc(3,3)=Loc(2,2)+3*n+3=676+3*n+3计算得出。 以上是专升本数据结构考试中的一些重点知识，理解和熟练运用这些概念对考试至关重要。考生应该通过做题、实践和复习加深理解，提高解题能力。