专升本数据结构考前看.docx

1、专升本数据结构考前看1名词解释：栈和队列栈是只允许在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出（LIFO）表。队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开（删除），故队列也常称先进先出（FIFO）表。2. 假设以S和X分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S和X组成的序列表示（如SXSX）。（1）试指出判别给定序列是否合法的一般规则。（2）两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列？如能得到，请举列说明。【答案】（1）通

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

3、（4356）得到后，栈中元素剩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等于-1时队空，r

4、ear等于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情况下

5、，若删除时导致front=rear为队空；tag=1情况下，若因插入导致front=rear则为队满。5. 若以1、2、3、4作为双端队列的输入序列，试分别求出以下条件的输出序列：（1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列；（2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列；（3）既不能由输入受限双端队列得到，也不能由输出受限双端队列得到的输出序列。【答案】（1）4132 （2）4213 （3）42311描述以下概念的区别：空格串与空串。【答案】空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。空串是不

6、含任何字符的串，即空串的长度是零。2设S1，S2为串，请给出使S1/*S2=S2/*S1成立的所有可能的条件（/*为连接符）。【答案】（1）s1和s2均为空串；（2）两串之一为空串；（3）两串串值相等（即两串长度相等且对应位置上的字符相同）。（4）两串中一个串长是另一个串长（包括串长为1仅有一个字符的情况）的数倍，而且长串就好象是由数个短串经过连接操作得到的。 5.4应用题1设有一个二维数组Amn，假设A00存放位置在644，A22存放位置在676，每个元素占一个空间，问A33存放在什么位置？ 【答案】设数组元素Aij存放在起始地址为Loc （ i, j ） 的存储单元中。 Loc （ 2,

7、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设有一个nn的对称矩阵A，为了节约存储，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行存放于一个一维数组B中，称之为对称矩阵A的压缩存储方式。试问：（1） 存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素？（2）

8、若在一维数组B中从0号位置开始存放，则对称矩阵中的任一元素aij在只存下三角部分的情形下应存于一维数组的什么下标位置？给出计算公式。【答案】（1） 数组B共有12 + 3 + + n= （ n+1 ）*n / 2个元素。 （2） 只存下三角部分时，若i j，则数组元素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 j，数组元素Aij在数组B中没有存放，可以找它的

9、对称元素Aji。在数组B的第 （j-1）*j / 2 + i位置中找到。如果第0行第0列也计入，数组B从0号位置开始存放，则数组元素Aij在数组B中的存放位置可以改为：当i j时，= i*（i+1） / 2 + j当i j时，= j*（j+1） / 2 + i 3利用广义表的head和tail操作写出函数表达式，把以下各题中的单元素banana从广义表中分离出来： （1） L1（apple, pear, banana, orange） （2） L2（apple, pear）, （banana, orange） （3） L3（apple）, （pear）, （bananA）, （orange）

10、（4） L4（apple）, （pear）, （bananA）, orange） （5） L5（apple）, pear）, bananA）, orange） 【答案】 （1） Head （Tail （Tail （L1） ） ） （2） Head （Head （Tail （L2） ） ） （3） Head （Head （Tail （Tail （Head （L3） ） ） ） ） （4） Head （Head （Tail （Tail （L4） ） ） ） （5） Head （Tail （Head（L5） ） ） 1从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的

11、是什么，并指出树和二叉树的主要区别。【答案】树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树惟一表示，并可使用二叉树的一些算法去解决树和森林中的问题。树和二叉树的区别有3：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分支的情况下， 也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。2若在内存中存放一个完全二叉树，在二叉树上只进行下面两个操作：（1）寻找某个结点双亲 ； （2）寻找某个结点的子女；请问应该用何种结构来存储该

12、二叉树？【答案】用顺序存储结构存储n个结点的完全二叉树。编号为i的结点，其双亲编号是i/2(i=1时无双亲)，其左子女是2i(若2in，否则i无左子女)，右子女是2i+1(若2i+1n，否则无右子女)。3求含有n个结点、采用顺序存储结构的完全二叉树中的序号最小的叶子结点的下标。要求写出简要步骤。【答案】根据完全二叉树的性质，最后一个结点（编号为n）的双亲结点的编号是n/2，这是最后一个分支结点，在它之后是第一个终端（叶子）结点，故序号最小的叶子结点的下标是n/2+1。4试证明，同一棵二叉树的所有叶子结点，在先序序列、中序序列以及后序序列中都按相同的相对位置出现（即先后顺序相同），例如先序abc

13、，后序bca，中序bac。【答案】先序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。三种遍历中只是访问“根”结点的时机不同，对左右子树均是按左右顺序来遍历的，因此所有叶子都按相同的相对位置出现。5试找出满足下列条件的二叉树：1）先序序列与后序序列相同； 2）中序序列与后序序列相同；3）先序序列与中序序列相同； 4）中序序列与层次序列相同；【答案】先序遍历二叉树的顺序是“根左子树右子树”，中序遍历“左子树根右子树”，后序遍历顺序是：“左子树右子树根”，根据以上原则，解答如下：1）若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。2）若中序序列与后序序列相同，则或为空树

14、，或为任一结点至多只有左子树的二叉树。（3）若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。（4）若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树6已知一棵二叉树的中序序列和后序序列分别为GLDHBEIACJFK和LGHDIEBJKFCA（1）给出这棵二叉树；（2）转换为对应的森林。【答案】7一棵非空二叉树其先序序列和后序序列正好相反，画出二叉树的形状。【答案】先序序列是“根左右” 后序序列是“左右根”，可见对任意结点，若至多只有左子女或至多只有右子女，均可使先序序列与后序序列相反，图示如下：8假设一棵二叉树的层次次序（按层次递增顺序排列，

15、同一层次自左向右）为ABECFGDHI,中序序列为BCDAFEHIG。请画出该二叉树，并将其转换为对应的森林。【答案】按层次遍历，第一个结点（若树不空）为根，该结点在中序序列中把序列分成左右两部分：左子树和右子树。若左子树不空，层次序列中第二个结点为左子树的根；若右子树为空，则层次序列中第三个结点为右子树的根。对右子树也作类似的分析。层次序列的特点是，从左到右每个结点或是当前情况下子树的根或是叶子。9已知一个森林的先序序列和后序序列如下，请构造出该森林。先序序列：ABCDEFGHIJKLMNO后序序列：CDEBFHIJGAMLONK 【答案】森林的先序序列和后序序列对应其转换的二叉树的先序序列

16、和中序序列，应先据此构造二叉树，再构造出森林。10一棵二叉树的先序、中序、后序序列如下，其中一部分未标出，请构造出该二叉树。先序序列 ：_ _ C D E _ G H I _ K 中序序列 ：C B _ _ F A _ J K I G后序序列 ：_ E F D B _ J I H _ A 【答案】11设有正文AADBAACACCDACACAAD，字符集为A，B，C，D，设计一套二进制编码，使得上述正文的编码最短。【答案】字符A，B，C，D出现的次数为9，1，5，3。其哈夫曼编码如下：A:1，B:000，C:01，D:001。AOE网的性质（1）只有在某顶点所代表的事件发生后，从该顶点出发的各有

17、向边所代表的活动才能开始。（2）只有在进入某点的各有向边所代表的活动都已结束，该顶点所代表的时事件才能发生。整个工程只有一个开始点，一个结束点。AOV网用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网，简称AOV网。在网中，若从顶点i到顶点j有一条有向路径，则i是j 的前驱AOV网是一种有向无环图。强连通图是指一个有向图中任意两点v1、v2间存在v1到v2的路径及v2到v1的路径的图。1设有一有向图为G=(V，E)。其中，V= v1, v2, v3, v4, v5，E=, , , , , , ，请画出该有向图并判断是否是强连通图。分析：作该题的关键是弄清楚以下两点（1）边集

18、E中表示一条以vi为弧尾，vj为弧头的有向弧。（2）强连通图是任意两顶点间都存在路径的有向图。【答案】该有向图是强连通图，表示如下： 2画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。并说明在n个顶点的无向完全图中，边的条数为n(n-1)/2。【答案】【解析】因为在有n个顶点的无向完全图中，每一个顶点与其它任一顶点都有一条边相连，所以每一个顶点有n-1条边与其他顶点相连，则 n个顶点有n(n-1)条边。但在无向图中，顶点i到顶点j与顶点j到顶点i是同一条边，所以总共有n(n-1)/2条边。3对n个顶点的无向图G，采用邻接矩阵表示，如何判别下列有关问题：（1）图中有多少条边?（

19、2）任意两个顶点i和j是否有边相连?（3）任意一个顶点的度是多少?【答案】（1）无向图的邻接矩阵是对称的，故它的边数应是上三角或下三角的非0元个数。（2）邻接矩阵中如果第i行第j列的元素非0则表示顶点i与顶点j相连。（3）任意一个顶点vi的度是第i行或第i列上非0元的个数。4熟悉图的存储结构，画出下面有向图的邻接矩阵、邻接表、逆邻接表、十字链表。写出邻接表表示的图从顶点A出发的深度优先遍历序列和广度优先遍历序列。【答案】邻接矩阵如下： 邻接表如下： 逆邻接表如下： 十字链表如下： 深度优先遍历序列为ABCFED，广度优先遍历序列为ABDCEF5已知下面是某无向图的邻接表，画出该无向图，并分别给

20、出从A出发的深度优先搜索生成树和广度优先搜索生成树。【解析】作该题的关键是弄清楚邻接表的概念，理解深度优先搜索和广度优先搜索的全过程以及二者的区别。【答案】该无向图如下所示： 深度优先搜索生成树为： 广度优先搜索生成树为： 6请分别用Prim算法和Kruskal算法构造以下网络的最小生成树，并求出该树的代价。【解析】Prim算法的操作步骤：首先从一个只有一个顶点的集合开始，通过加入与其中顶点相关联的最小代价的边来扩充顶点集，直到所有顶点都在一个集合中。【答案】【解析】Kruscal算法的操作步骤： 首先将n个顶点看成n个互不连通的分量，从边集中找最小代价的边，如果落在不同连通分量上，则将其加入

21、最小生成树，直到所有顶点都在同一连通分量上。【答案】7 写出求以下AOE网的关键路径的过程。要求：给出每一个事件和每一个活动的最早开始时间和最晚开始时间。【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下（1）求事件的最早发生时间ve(j), 最晚发生时间vl(j);（2）最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6), 最晚发生时间从vl(6)按逆拓扑排序向后递推到 vl(0);（3）计算e(i),l(i)：设ai由弧表示，持续时间记为dut，则有下式成立e(i)=ve(j)l(i)=vl(k)-dut()（4）找出e(i)-l(i)=0的活动既是关键活动。【答案】顶点

22、 ve vl活动 e l l-eV0 0 0v1 2 2v2 4 5 v3 10 10v4 7 7v5 9 10v6 14 14a0 0 0 0a1 0 4 4a2 0 1 1a3 2 9 7a4 2 2 0a5 4 5 1a6 7 7 0a7 7 10 3a8 4 5 1a9 10 10 0a10 9 10 1关键路径为：a0-a4-a6-a98 拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。【解析】解题关键是弄清拓扑排序的步骤（1）在AOV网中，选一个没有前驱的结点且输出；（2）删除该顶点和以它为尾的弧；（3）重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。【答案】（1）

23、0132465 （2）01234659给定带权有向图G和源点v1,利用迪杰斯特拉（Dijkstra）算法求从v1到其余各顶点的最短路径。【解析】求解该题的关键是掌握迪杰斯特拉（Dijkstra）算法的设计原理-从一个顶点v到另一顶点vk的最短路径或者是(v,vk)或者是(v,vj,vk),它的长度或者是从v到vk弧上的权值，或者是Dj与vj到vk弧上的权值之和，其中Dj是已经找到的从v到vj的最短路径。【答案】S是已找到最短路径的终点的集合。终点从v1到各终点的D值和最短路径的求解i=2 i=3 i=4i=5i=6v25(v1,v2)5(v1,v2)v34(v1,v3)v43276732767

24、327679(v1,v2,v5,v4)v532767327676(v1,v2,v5)v6327673276712(v1,v2,v6)9(v1,v2,v5,v6)9(v1,v2,v5,v6)vjv3v2v5v4v6Sv1,v3v1,v2v1,v2,v5v1,v2,v5,v4v1,v2,v5,v610利用Floyd算法求下图中各对顶点之间的路径。【解析】Floyd算法是依次添加顶点来修改相应路径，也就是说,若（vi，vk）和(vk，vj)分别是从vi到vk和从vk到vj的中间顶点的序号不大于k-1的最短路径，则将（vi，vk，vj）和已经得到的从vi到vj且中间顶点序号不大于k-的最短路径相比较，

25、其长度较短者便是从vi到vj的中间顶点的序号不大于k的最短路径。经过n次比较后必求得vi到vj的最短路径，依次，可求得各对顶点间的最短路径。求解的关键是求解如下的一个n阶方阵序列：D(1)，D(0)，D(1)，D(k)，D(n1)其中D(1)ij=Garcsij D(k)=MinD(k-1)ij，D(k-1)ik+D(k-1)kj 0kn-1【答案】DD(-1)D(0)D(1)D(2)012012012012001701701401410303031203290910091009100PP(-1)P(0)P(1)P (2)0120120120120ACABACABACACBACACB1CBCB

26、CBCBACB2BABABACBABACBABAC每对顶点之间的最短路径及长度总结如下：顶点A到顶点C最短路径为：A-C，长度为： 顶点A到顶点B最短路径为：A-C-B，长度为：4 顶点C到顶点A最短路径为：C-B-A，长度为：12 顶点C到顶点B最短路径为：C-B，长度为：3 顶点B到顶点A最短路径为：B-A，长度为：9 顶点B到顶点C最短路径为：B-A-C，长度为：10 8.4应用题1顺序查找时间为O(n)，二分法查找时间为O(log2n)，散列法为O(1)，为什么有高效率的查找方法而低效率的方法不被放弃?【答案】不同的查找方法适用的范围不同，高效率的查找方法并不是在所有情况下都比其他查找

27、方法效率要高，而且也不是在所有情况下都可以采用。2对含有n个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较?【答案】n-1次【解析】设变量max和min用于存放最大元和最小元(的位置)，第一次取两个元素进行比较，大的放入max，小的放入min。从第2次开始，每次取一个元素先和max比较，如果大于max则以它替换max，并结束本次比较；若小于max则再与min相比较，在最好的情况下，比较下去都不用和min相比较，所以这种情况下，至少要进行n-1次比较就能找到最大元和最小元。3若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均

28、查找长度：（1）查找不成功，即表中无关键字等于给定值K的记录；（2）查找成功，即表中有关键字等于给定值K的记录。【答案】（1）不成功时需要n+1 次比较 （2）成功时平均为(n+1)/2次【解析】有序表和无序表顺序查找时，都需要进行n+1次比较才能确定查找失败。因此平均查找长度都为n+1。查找成功时，平均查找长度都为(n+1)/2，有序表和无序表也是一样的。因为顺序查找与表的初始序列状态无关。4设有序表为(a, b, c, d, e, f, g, h, i, j, k, p, q)，请分别画出对给定值a, g和n进行折半查找的过程。【答案】（1）查找a的过程如下(圆括号表示当前比较的关键字)，经过三次比较，查找成功。下标12345678910111213区间第一次比较abcdef(g)hijkpqa.q第二次比较ab(c）defghijkpqa.f第三次比较(a）bcdefghijkpqa.b（2）g的查找过程如下，一次比较成功。 a b c d e f (g) h i j k p q （3）n的查找过程如下，经过四次比较，查找失败。下标12345678910111213区间