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

专升本数据结构考前必看.doc:..:栈和队列找是只允许在一端进行插入和删除操作的线性表,允许插入和删除的一端叫栈顶,另一端叫栈底。最后插入的元素最先删除,故栈也称后进先出(L1F0)农。队列是允许在一端插入而在另一端删除的线性表,允许插入的一端叫队尾,允许删除的一端叫队头。最先插入队的元素最先离开(删除),故队列也常称先进先出(FIFO)表。,则对初态和终态均为空的栈操作可由S和X组成的序列表示(如SXSX)。(1) 试指出判别给定序列是否合法的一般规则,(2) 两个不同合法序列(对同一输入序列)能否得到相同的输出元索序列?如能得到,请举列说明。【答案】(1)通常有W条规则。第一是给定序列中S的个数和X的个数相等;第二是从给定序列的开始,到给定序列屮的任一位靑,S的个数要大于或等于X的个数。(2)可以得到相同的输出元素序列。例如,输入元索为A,B,C,则两个输入的合法序列ABC和BAC均可得到输出元索序列ABC。对丁•合法序列ABC,我们使用本题约定的SXSXSX操作序列;对于合法序列BAC,我们使用SSXXSX操作序列。,试问能否通过栈结构得到以下两个序列:435612和135426,诺说明为什么不能或如何才能得到。【答案】输入序列为123456,不能得出435612,其理山是,输出序列最后W元素是12,前而4个元素(4356)得到后,栈屮元素剩12,且2在找顶,不讨能栈底元素1在栈顶元素2之前出栈。得到135426的过程如下:1入栈并出栈,得到部分输出序列1;然后2和3入栈,3出找,部分输出序列变为:13;接着4和5入栈,5,4和2依次出栈,部分输fli序列变为13542;最后6入栈并退栈,得最终结果135426。。【答案】设顺序存储队列用一维数组qLm]表示,其中m为队列中元素个数,队列中元素在向量中的下标从0到m-1。设队久•指针为front,队尾指针是rear,约定front指向队?又•元素的前一位S,rear指向队犀元素。当front等丁-1时队空,rear等于m-1时为队满。由于队列的性质(“删除”在队头而“插入”在队尾),所以当队尾指针rear等于m-1时,若front不等于-1,则队列屮仍宥空闲单元,所以队列并不是S满。这吋若洱冇入队操作,会造成假“溢出”。其解决办法冇二,一足将队列元素内前“平移”(占川0至rear-front-1);二是将队列看成首尾相连,即循环队列(0..m-1k在循环队列卜,仍定义front=rear时为队空,而判断队满则用两种办法,一是用“牺牲一个单元”,即rear+l=front(准确记是(rear+1)%m=front,m是队列容量)时为队满。另一种解法是“设标记”方法,如设标记tag,tag等于0情况卜\若删除吋导致front=rear为队&tag=l情况卜\若因插入导致front=rear则为队满。、2、3、4作为双端队列的输入序列,试分别求出以下条件的输出序列:(1) 能由输入受限的双端队列得到,但不能由输出受限的双端队列得到的输出序列;(2) 能由输出受限的双端队列得到,侃不能由输入受限的双端队列得到的输出序列;(3) 既不能山输入受限双端队列得到,也不能出输出受限双端队列得到的输出序列。【答案】(1)4132 (2)4213 (3):空格中与空中。【答案】空格是一个字符,JtASCII码偾是32。空格串是由空格组成的串,其长度等于空格的个数。空串是不含任何字符的串,即空串的长度是零。,S2为串,请给出使S1/*S2=S2/*S1成立的所冇町能的条件(/*为连接符)。【答案】(1) si和s2均为空中;(2) 两串之一为空串;(3) 两串串值相等(即两串长度相等且对应位置上的字符相同)。(4) 两牢中一个中长是另一个中长(包括串忪力1仅冇一个字符的情况)的数倍,而且长串就好象是由数个短中经过连接操作得到的。[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,3)=Loc(0,0)+3*15+3=644+45+3=,为了节约存储,可以只存对角线及对角线以上的元索,或者只存