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

1．名词解释：栈和队列
栈是只允许在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出（LIFO）表。
队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开（删除），故队列也常称先进先出（FIFO）表。
2. 假设以S和X分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S和X组成的序列表示（如SXSX）。
（1）试指出判别给定序列是否合法的一般规则。
（2）两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列？如能得到，请举列说明。
【答案】（1）通常有两条规则。第一是给定序列中S的个数和X的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，S的个数要大于或等于X的个数。（2）可以得到相同的输出元素序列。例如，输入元素为A，B，C，则两个输入的合法序列ABC和BAC均可得到输出元素序列ABC。对于合法序列ABC，我们使用本题约定的SXSXSX操作序列；对于合法序列BAC，我们使用SSXXSX操作序列。
3. 如果输入序列为123456，试问能否通过栈结构得到以下两个序列：435612和13542 6，请说明为什么不能或如何才能得到。
【答案】输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为：13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。
4. 简述顺序存储队列的假溢出的避免方法及队列满和空的条件。
【答案】设顺序存储队列用一维数组q[m]表示，其中m为队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front指向队头元素的前一位置，rear指向队尾元素。当front等于-1时队空，rear等于m-1时为队满。由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针rear等于m-1时，若front不等于-1，则队列中仍有空闲单元，所以队列并不是真满。这时若再有入队操作，会造成假“溢出”。其解决办法有二，一是将队列元素向前“平移”（占用0至rear-front-1）；二是将队列看成首尾相连，即循环队列（0..m-1）。在循环队列下，仍定义front=rear时为队空，而判断队满则用两种办法，一是用“牺牲一个单元”，即rear+1=front（准确记是（rear+1）%m=front，m是队列容量）时为队满。另一种解法是“设标记”方法，如设标记tag，tag等于0情况下，若删除时导致front=rear为队空；tag=1情况下，若因插入导致front=rear则为队满。
5. 若以1、2、3、4作为双端队列的输入序列，试分别求出以下条件的输出序列：
（1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列；
（2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列；
（3）既不能由输入受限双端队列得到，也不能由输出受限双端队列得到的输出序列。
【答案】（1）4132 （2）4213 （3）4231
1．描述以下概念的区别：空格串与空串。
【答案】空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零。
2．设S1，S2为串，请给出使S1/*S2=S2/*S1成立的所有可能的条件（/*为连接符）。
【答案】
（1）s1和s2均为空串；
（2）两串之一为空串；
（3）两串串值相等（即两串长度相等且对应位置上的字符相同）。
（4）两串中一个串长是另一个串长（包括串长为1仅有一个字符的情况）的数倍，而且长串就好象是由数个短串经过连接操作得到的。
　应用题
1．设有一个二维数组A[m][n]，假设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，问A[3][3]存放在什么位置？
【答案】设数组元素A[i][j]存放在起始地址为Loc （ i, j ） 的存储单元中。
∵ Loc （ 2, 2 ） = Loc （ 0, 0 ） + 2 * n + 2 = 644 + 2 * n + 2 = 676.
∴ n = （ 676 - 2 - 644 ） / 2 = 15
∴ Loc （ 3,