《专升本数据结构考前必看》由会员分享，可在线阅读，更多相关《专升本数据结构考前必看（13页珍藏版）》请在金锄头文库上搜索。
1、1名词解释：栈和队列 栈是只允许在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除， 故栈也称后进先出（LIFO）表。队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离 开（删除），故队列也常称先进先出（FIFO）表。2假设以S和X分别表示入栈和出栈操作，贝V对初态和终态均为空的栈操作可由S和X组成的序列表示（如SXSX）。（1）试指出判别给定序列是否合法的一般规则。（2）两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列？如能得到，请举列说明。【答案】（1）通常有两条规则。第
2、一是给定序列中S的个数和X的个数相等；第二是从给定序列的开始，到给定序列中的任一 位置，S的个数要大于或等于X的个数。（2）可以得到相同的输出元素序列。例如，输入元素为A, B, C,则两个输入的合法 序列ABC和BAC均可得到输出元素序列ABC。对于合法序列ABC，我们使用本题约定的SXSXSX操作序列；对于合法序列BA C，我们使用SSXXSX操作序列。3. 如果输入序列为123456，试问能否通过栈结构得到以下两个序列：435612和13542 6,请说明为什么不能或如何才能得到。 【答案】输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素（4
3、356）得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。得到135426的过程如下： 1入栈并出栈，得到部分输出序列1； 然后2和3入栈， 3出栈，部分输出序列变为： 13；接着4和5入栈， 5， 4和2依次出栈，部分输出序列变为13542；最后6入栈并退 栈，得最终结果135426。4. 简述顺序存储队列的假溢出的避免方法及队列满和空的条件。【答案】设顺序存储队列用一维数组qm表示，其中m为队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指 针为front，队尾指针是rear，约定front指向队头元素的前一位置，rear指向队尾元素。当front等于T
4、时队空，rear等 于m-1时为队满。由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针rear等于m-1时，若front不等 于-1，则队列中仍有空闲单元，所以队列并不是真满。这时若再有入队操作，会造成假“溢出”。其解决办法有二，一是将队 列元素向前“平移”（占用0至rear-front-1）；二是将队列看成首尾相连，即循环队列（0.m-l）。在循环队列下，仍定 义 front=rear 时为队空， 而判断队满则用两种办法， 一是用“牺牲一个单元” ， 即 rear+1=front （准确记是（rear+1）%m=front，m 是队列容量）时为队满。另一种解法是“设标记”方法
5、，如设标记 tag，tag 等于 0 情况下，若删除 时导致front=rear为队空；tag= 1情况下，若因插入导致front=rear则为队满。5. 若以1、2、3、4作为双端队列的输入序列，试分别求出以下条件的输出序列：（1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列；（2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列；（3）既不能由输入受限双端队列得到，也不能由输出受限双端队列得到的输出序列。【答案】（1） 4132（2） 4213（3） 42311描述以下概念的区别：空格串与空串。【答案】空格是一个字符，其ASCI I码值是32。空
6、格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串 ，即空串的长度是零。2设S1，S2为串，请给出使S1/*S2=S2/*S1成立的所有可能的条件（/*为连接符）。【答案】（1） s1和s2均为空串；（ 2）两串之一为空串；（3）两串串值相等（即两串长度相等且对应位置上的字符相同）。（4）两串中一个串长是另一个串长（包括串长为1仅有一个字符的情况）的数倍，而且长串就好象是由数个短串经过连接操作 得到的。5.4 应用题1 设有一个二维数组Amn，假设A00存放位置在644, A22存放位置在676，每个元素占一个空间，问A3存放在什 么位置？【答案】设数组元素Aij存放在起始地址
7、为Loc （ i, j ）的存储单元中。Loc （ 2, 2 ） = Loc （ 0, 0 ） + 2 * n + 2 = 644 + 2 * n + 2 = 676.n = （ 676 - 2 - 644 ） / 2 = 15Loc （ 3, 3 ） = Loc （ 0, 0 ） + 3 * 15 + 3 = 644 + 45 + 3 = 692.2设有一个nxn的对称矩阵A,为了节约存储，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。 前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行存放于一个一维数组B中，称之为对称矩阵A的压缩存储方式。 试问：（1）存放对称矩
8、阵A上三角部分或下三角部分的一维数组B有多少元素？（2）若在一维数组B中从0号位置开始存放，则对称矩阵中的任一元素丐在只存下三角部分的情形下应存于一维数组的什么下标位置 ？给出计算公式。【答案】（1）数组B共有1 + 2 + 3 + n= （ n+1 ） *n / 2个元素。（2）只存下三角部分时，若ij,则数组元素Aij前面有i-1行（1i-1,第0行第0列不算），第1行有1个元素，第2行有2个元素，第i-1行有i-1个元素。在第i行中，第j号元素排在第j个元素位置，因此，数组元素Aij在数组B中的存放位置为：1 + 2 + + （i-1） + j = （ i-1） *i / 2 + j若i
9、 j时,=i* (i+1) / 2 + j当ij时，=j* (j+1) / 2 + i3利用广义表白的head和tail操作写出函数表达式，把以下各题中的单元素banana从广义表中分离出来: ( 1 ) L1 ( apple, pear, banana, orange)( 2) L2( apple, pear) , ( banana, orange)( 3) L3( apple) , ( pear) , ( bananA) , ( orange)( 4) L4( apple) , ( pear) , ( bananA) , orange)答案】(1)( 2)( 3)( 4 )( 5 )Hea
10、d Head HeadHead Head( 5) L5( apple) , pear) , bananA) , orange)Tail (Tail(L1) ) )Head ( Tail ( L2) ) )Head(Tail(Tail(Head(L3) ) ) ) )Head (Tail(Tail(L4) ) ) )Tail ( Head( L5) ) )1从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树 的主要区别。【答案】树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例， 即森林中只
11、有一棵树的特殊情况）可用二叉树惟一表示，并可使用二叉树的一些算法去解决树和森林中的问题。树和二叉树的区别有3：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分支的情况下， 也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。2若在内存中存放一个完全二叉树，在二叉树上只进行下面两个操作： （1）寻找某个结点双亲； （2）寻找某个结点的子女；请问应该用何种结构来存储该二叉树？【答案】用顺序存储结构存储n个结点的完全二叉树。编号为i的结点，其双亲编号是Li/2（i=1时无双亲），其左子女是2i（若2i9 ，否则i无左子女）
12、，右子女是2i+1（若2i+19，否则无右子女）。3求含有n个结点、采用顺序存储结构的完全二叉树中的序号最小的叶子结点的下标。要求写出简要步骤。【答案】根据完全二叉树的性质，最后一个结点（编号为n）的双亲结点的编号是Ln/2，这是最后一个分支结点，在它之后是 第一个终端（叶子）结点，故序号最小的叶子结点的下标是Ln/2+1。4试证明，同一棵二叉树的所有叶子结点，在先序序列、中序序列以及后序序列中都按相同的相对位置出现（即先后顺序相 同），例如先序abc，后序bca，中序bac。【答案】先序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。三种遍历中只是访问“根”结点的时机不 同，对
13、左右子树均是按左右顺序来遍历的，因此所有叶子都按相同的相对位置出现。5试找出满足下列条件的二叉树： 1）先序序列与后序序列相同； 2）中序序列与后序序列相同；3）先序序列与中序序列相同； 4）中序序列与层次序列相同；【答案】先序遍历二叉树的顺序是“根左子树右子树”，中序遍历“左子树根右子树”，后序遍历顺序是：“左子树 右子树一根”，根据以上原则，解答如下:1）若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。2）若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。（3）若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。（4）若中序序列与
14、层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树6已知一棵二叉树的中序序列和后序序列分别为GLDHBEIACJFK和LGHDIEBJKFCA2）题图7一棵非空二叉树其先序序列和后序序列正好相反，画出二叉树的形状。【答案】先序序列是“根左右”后序序列是“左右根”，可见对任意结点，若至多只有左子女或至多只有右子女，均可使先序序列与后序序列相反，图示如下：8假设一棵二叉树的层次次序（按层次递增顺序排列，同一层次自左向右）为ABECFGDHI，中序序列为BCDAFEHIG。请画 出该二叉树，并将其转换为对应的森林。【答案】按层次遍历，第一个结点（若树不空）为根，该结点在中序序列中把序列
15、分成左右两部分：左子树和右子树。若左子 树不空，层次序列中第二个结点为左子树的根；若右子树为空，则层次序列中第三个结点为右子树的根。对右子树也作类似的 分析。层次序列的特点是，从左到右每个结点或是当前情况下子树的根或是叶子。_ _ C D E _ G H I _ K C B _ _ F A _ J K I G _ E F D B _ J I H _ A9已知一个森林的先序序列和后序序列如下，请构造出该森林。先序序列：ABCDEFGHIJKLMNO后序序列： CDEBFHIJGAMLONK【答案】森林的先序序列和后序序列对应其转换的二叉树的先序序列和中序序列，应先据此构造二叉树，再构造出森林。10.先序序列 中序序列 ： 后序序列 ：11.设有正文AADBAACACCDACACAAD，字符集为A, B, C, D,设计一套
