专升本数据结构考前必看

《专升本数据结构考前必看》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1．名词解释：栈和队列栈是只允许在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出（LIFO）表。队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开（删除），故队列也常称先进先出（FIFO）表。2.假设以S和X分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S和X组成的序列表示（如SXSX）。（1）试指出判别给定序列是否合法的一般规则。（2）两个不同合法序列（对同一输入序列）

2、能否得到相同的输出元素序列？如能得到，请举列说明。【答案】（1）通常有两条规则。第一是给定序列中S的个数和X的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，S的个数要大于或等于X的个数。（2）可以得到相同的输出元素序列。例如，输入元素为A，B，C，则两个输入的合法序列ABC和BAC均可得到输出元素序列ABC。对于合法序列ABC，我们使用本题约定的SXSXSX操作序列；对于合法序列BAC，我们使用SSXXSX操作序列。3.如果输入序列为123456，试问能否通过栈结构得到以下两个序列：435612和

3、135426，请说明为什么不能或如何才能得到。【答案】输入序列为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.简述顺序存储队列的假溢出的避免方法及队列满和空的条件。【答案

4、】设顺序存储队列用一维数组q[m]表示，其中m为队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front指向队头元素的前一位置，rear指向队尾元素。当front等于-1时队空，rear等于m-1时为队满。由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针rear等于m-1时，若front不等于-1，则队列中仍有空闲单元，所以队列并不是真满。这时若再有入队操作，会造成假“溢出”。其解决办法有二，一是将队列元素向前“平移”（占用0至rear-

5、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）能由输

6、入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列；（2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列；（3）既不能由输入受限双端队列得到，也不能由输出受限双端队列得到的输出序列。【答案】（1）4132（2）4213（3）42311．描述以下概念的区别：空格串与空串。【答案】空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零。2．设S1，S2为串，请给出使S1/*S2=S2/*S1成立的所有可能的条

7、件（/*为连接符）。【答案】（1）s1和s2均为空串；（2）两串之一为空串；（3）两串串值相等（即两串长度相等且对应位置上的字符相同）。（4）两串中一个串长是另一个串长（包括串长为1仅有一个字符的情况）的数倍，而且长串就好象是由数个短串经过连接操作得到的。5.4　应用题1．设有一个二维数组A[m][n]，假设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，问A[3][3]存放在什么位置？【答案】设数组元素A[i][j]存放在起始地址为Loc（i,j）的存储单元中。∵Loc（

8、2,2）=Loc（0,0）+2*n+2=644+2*n+2=676.∴n=（676-2-644）/2=15∴Loc（3,3）=Loc（0,0）+3*15+3=644+45+3=692.2．设有一个n´n的对称矩阵A，为了节约存储，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行存放于一个一维数组B中，称之为对称矩阵A的压缩存储