专升本数据结构考前必看.docx
- 文档编号:11507951
- 上传时间:2023-06-01
- 格式:DOCX
- 页数:32
- 大小:411.13KB
专升本数据结构考前必看.docx
《专升本数据结构考前必看.docx》由会员分享,可在线阅读,更多相关《专升本数据结构考前必看.docx(32页珍藏版)》请在冰点文库上搜索。
专升本数据结构考前必看
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和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.简述顺序存储队列的假溢出的避免方法及队列满和空的条件。
【答案】设顺序存储队列用一维数组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仅有一个字符的情况)的数倍,而且长串就好象是由数个短串经过连接操作得到的。
5.4 应用题
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,3)=Loc(0,0)+3*15+3=644+45+3=692.
2.设有一个nn的对称矩阵A,为了节约存储,可以只存对角线及对角线以上的元素,或者只存对角线或对角线以下的元素。
前者称为上三角矩阵,后者称为下三角矩阵。
我们把它们按行存放于一个一维数组B中,称之为对称矩阵A的压缩存储方式。
试问:
(1)存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素?
(2)若在一维数组B中从0号位置开始存放,则对称矩阵中的任一元素aij在只存下三角部分的情形下应存于一维数组的什么下标位置?
给出计算公式。
【答案】
(1)数组B共有1+2+3++n=(n+1)*n/2个元素。
(2)只存下三角部分时,若ij,则数组元素A[i][j]前面有i-1行(1i-1,第0行第0列不算),第1行有1个元素,第2行有2个元素,,第i-1行有i-1个元素。
在第i行中,第j号元素排在第j个元素位置,因此,数组元素A[i][j]在数组B中的存放位置为:
1+2++(i-1)+j=(i-1)*i/2+j
若i 在数组B的第(j-1)*j/2+i位置中找到。 如果第0行第0列也计入,数组B从0号位置开始存放,则数组元素A[i][j]在数组B中的存放位置可以改为: 当ij时,=i*(i+1)/2+j 当i 3.利用广义表的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) (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.从概念上讲,树,森林和二叉树是三种不同的数据结构,将树,森林转化为二叉树的基本目的是什么,并指出树和二叉树的主要区别。 【答案】树的孩子兄弟链表表示法和二叉树二叉链表表示法,本质是一样的,只是解释不同,也就是说树(树是森林的特例,即森林中只有一棵树的特殊情况)可用二叉树惟一表示,并可使用二叉树的一些算法去解决树和森林中的问题。 树和二叉树的区别有3: 一是二叉树的度至多为2,树无此限制;二是二叉树有左右子树之分,即使在只有一个分支的情况下,也必须指出是左子树还是右子树,树无此限制;三是二叉树允许为空,树一般不允许为空(个别书上允许为空)。 2.若在内存中存放一个完全二叉树,在二叉树上只进行下面两个操作: (1)寻找某个结点双亲; (2)寻找某个结点的子女; 请问应该用何种结构来存储该二叉树? 【答案】用顺序存储结构存储n个结点的完全二叉树。 编号为i的结点,其双亲编号是i/2(i=1时无双亲),其左子女是2i(若2i≤n,否则i无左子女),右子女是2i+1(若2i+1≤n,否则无右子女)。 3.求含有n个结点、采用顺序存储结构的完全二叉树中的序号最小的叶子结点的下标。 要求写出简要步骤。 【答案】根据完全二叉树的性质,最后一个结点(编号为n)的双亲结点的编号是n/2,这是最后一个分支结点,在它之后是第一个终端(叶子)结点,故序号最小的叶子结点的下标是n/2+1。 4.试证明,同一棵二叉树的所有叶子结点,在先序序列、中序序列以及后序序列中都按相同的相对位置出现(即先后顺序相同),例如先序abc,后序bca,中序bac。 【答案】先序遍历是“根左右”,中序遍历是“左根右”,后序遍历是“左右根”。 三种遍历中只是访问“根”结点的时机不同,对左右子树均是按左右顺序来遍历的,因此所有叶子都按相同的相对位置出现。 5.试找出满足下列条件的二叉树: 1)先序序列与后序序列相同;2)中序序列与后序序列相同; 3)先序序列与中序序列相同;4)中序序列与层次序列相同; 【答案】先序遍历二叉树的顺序是“根—左子树—右子树”,中序遍历“左子树—根—右子树”,后序遍历顺序是: “左子树—右子树―根”,根据以上原则,解答如下: 1)若先序序列与后序序列相同,则或为空树,或为只有根结点的二叉树。 2)若中序序列与后序序列相同,则或为空树,或为任一结点至多只有左子树的二叉树。 (3)若先序序列与中序序列相同,则或为空树,或为任一结点至多只有右子树的二叉树。 (4)若中序序列与层次遍历序列相同,则或为空树,或为任一结点至多只有右子树的二叉树 6.已知一棵二叉树的中序序列和后序序列分别为GLDHBEIACJFK和LGHDIEBJKFCA (1)给出这棵二叉树; (2)转换为对应的森林。 【答案】 7.一棵非空二叉树其先序序列和后序序列正好相反,画出二叉树的形状。 【答案】先序序列是“根左右”后序序列是“左右根”,可见对任意结点,若至多只有左子女或至多只有右子女,均可使先序序列与后序序列相反,图示如下: 8.假设一棵二叉树的层次次序(按层次递增顺序排列,同一层次自左向右)为ABECFGDHI,中序序列为BCDAFEHIG。 请画出该二叉树,并将其转换为对应的森林。 【答案】按层次遍历,第一个结点(若树不空)为根,该结点在中序序列中把序列分成左右两部分: 左子树和右子树。 若左子树不空,层次序列中第二个结点为左子树的根;若右子树为空,则层次序列中第三个结点为右子树的根。 对右子树也作类似的分析。 层次序列的特点是,从左到右每个结点或是当前情况下子树的根或是叶子。 9.已知一个森林的先序序列和后序序列如下,请构造出该森林。 先序序列: ABCDEFGHIJKLMNO 后序序列: CDEBFHIJGAMLONK 【答案】森林的先序序列和后序序列对应其转换的二叉树的先序序列和中序序列,应先据此构造二叉树,再构造出森林。 10.一棵二叉树的先序、中序、后序序列如下,其中一部分未标出,请构造出该二叉树。 先序序列: __CDE_GHI_K 中序序列: CB__FA_JKIG 后序序列: _EFDB_JIH_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)只有在某顶点所代表的事件发生后,从该顶点出发的各有向边所代表的活动才能开始。 (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)边集E中 (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)图中有多少条边? (2)任意两个顶点i和j是否有边相连? (3)任意一个顶点的度是多少? 【答案】 (1)无向图的邻接矩阵是对称的,故它的边数应是上三角或下三角的非0元个数。 (2)邻接矩阵中如果第i行第j列的元素非0则表示顶点i与顶点j相连。 (3)任意一个顶点vi的度是第i行或第i列上非0元的个数。 4.熟悉图的存储结构,画出下面有向图的邻接矩阵、邻接表、逆邻接表、十字链表。 写出邻接表表示的图从顶点A出发的深度优先遍历序列和广度优先遍历序列。 【答案】邻接矩阵如下: 邻接表如下: 逆邻接表如下: 十字链表如下: 深度优先遍历序列为ABCFED,广度优先遍历序列为ABDCEF 5.已知下面是某无向图的邻接表,画出该无向图,并分别给出从A出发的深度优先搜索生成树和广度优先搜索生成树。 【解析】作该题的关键是弄清楚邻接表的概念,理解深度优先搜索和广度优先搜索的全过程以及二者的区别。 【答案】该无向图如下所示: 深度优先搜索生成树为: 广度优先搜索生成树为: 6.请分别用Prim算法和Kruskal算法构造以下网络的最小生成树,并求出该树的代价。 【解析】Prim算法的操作步骤: 首先从一个只有一个顶点的集合开始,通过加入与其中顶点相关联的最小代价的边来扩充顶点集,直到所有顶点都在一个集合中。 【答案】 【解析】Kruscal算法的操作步骤: 首先将n个顶点看成n个互不连通的分量,从边集中找最小代价的边,如果落在不同连通分量上,则将其加入最小生成树,直到所有顶点都在同一连通分量上。 【答案】 7.写出求以下AOE网的关键路径的过程。 要求: 给出每一个事件和每一个活动的最早开始时间和最晚开始时间。 【解析】求关键路径首先求关键活动,关键活动ai的求解过程如下 (1)求事件的最早发生时间ve(j),最晚发生时间vl(j); (2)最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6),最晚发生时间从vl(6)按逆拓扑排序向后递推到vl(0); (3)计算e(i),l(i): 设ai由弧 e(i)=ve(j) l(i)=vl(k)-dut( (4)找出e(i)-l(i)=0的活动既是关键活动。 【答案】 顶点vevl 活动ell-e V000 v122 v245 v31010 v477 v5910 v61414 a0000 a1044 a2011 a3297 a4220 a5451 a6770 a77103 a8451 a910100 a109101 关键路径为: a0->a4->a6->a9 8.拓扑排序的结果不是唯一的,试写出下图任意2个不同的拓扑序列。 【解析】解题关键是弄清拓扑排序的步骤 (1)在AOV网中,选一个没有前驱的结点且输出; (2)删除该顶点和以它为尾的弧;(3)重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。 【答案】 (1)0132465 (2)0123465 9.给定带权有向图G和源点v1,利用迪杰斯特拉(Dijkstra)算法求从v1到其余各顶点的最短路径。 【解析】求解该题的关键是掌握迪杰斯特拉(Dijkstra)算法的设计原理----从一个顶点v到另一顶点vk的最短路径或者是(v,vk)或者是(v,vj,vk),它的长度或者是从v到vk弧上的权值,或者是D[j]与vj到vk弧上的权值之和,其中D[j]是已经找到的从v到vj的最短路径。 【答案】S是已找到最短路径的终点的集合。 终点 从v1到各终点的D值和最短路径的求解 i=2 i=3 i=4 i=5 i=6 v2 5 (v1,v2) 5 (v1,v2) v3 4 (v1,v3) v4 32767 32767 32767 9 (v1,v2,v5,v4) v5 32767 32767 6 (v1,v2,v5) v6 32767 32767 12 (v1,v2,v6) 9 (v1,v2,v5,v6) 9 (v1,v2,v5,v6) vj v3 v2 v5 v4 v6 S {v1,v3} {v1,v2} {v1,v2,v5} {v1,v2,v5,v4} {v1,v2,v5,v6} 10.利用Floyd算法求下图中各对顶点之间的路径。 【解析】Floyd算法是依次添加顶点来修改相应路径,也就是说,若(vi,...,vk)和(vk,...,vj)分别是从vi到vk和从vk到vj的中间顶点的序号不大于k-1的最短路径,则将(vi,...vk,...,vj)和已经得到的从vi到vj且中间顶点序号不大于k-1的最短路径相比较,其长度较短者便是从vi到vj的中间顶点的序号不大于k的最短路径。 经过n次比较后必求得vi到vj的最短路径,依次,可求得各对顶点间的最短路径。 求解的关键是求解如下的一个n阶方阵序列: D(_1),D(0),D (1),...,D(k),D(n_1) 其中 D(_1)[i][j]=G.arcs[i][j] D(k)=Min{D(k-1)[i][j],D(k-1)[i][k]+D(k-1)[k][j]}0≤k≤n-1 【答案】 D D(-1) D(0) D (1) D (2) 0 1 2 0 1 2 0 1 2 0 1 2 0 0 1 7 0 1 7 0 1 4 0 1 4 1 ∞ 0 3 ∞ 0 3 ∞ 0 3 12 0 3 2 9 ∞ 0 9 10 0 9 10 0 9 10 0 P P(-1) P(0) P (1) P (2) 0 1 2 0 1 2 0 1 2 0 1 2 0 AC AB AC AB AC ACB AC ACB 1 CB CB CB CBA CB 2 BA BA BAC BA BAC BA BAC 每对顶点之间的最短路径及长度总结如下: 顶点A到顶点C最短路径为: A->C,长度为: 1 顶点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),为什么有高效率的查找方法而低效率的方法不被放弃? 【答案】不同的查找方法适用的范围不同,高效率的查找方法并不是在所有情况下都比其他查找方法效率要高,而且也不是在所有情况下都可以采用。 2.对含有n个互不相同元素的集合,同时找最大元和最小元至少需进行多少次比较? 【答案】n-1次 【解析】设变量max和min用于存放最大元和最小元(的位置),第一次取两个元素进行比较,大的放入max,小的放入min。 从第2次开始,每次取一个元素先和max比较,如果大于max则以它替换max,并结束本次比较;若小于max则再与min相比较,在最好的情况下,比较下去都不用和min相比较,所以这种情况下,至少要进行n-1次比较就能找到最大元和最小元。 3.若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找,试在下述两种情况下分别讨论两者在等概率时的平均查找长度: (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的过程如下(圆括号表示当前比较的关键字),经过三次比较,查找成功。 下标 1 2 3 4 5 6 7 8 9 10 11 12 13 区间 第一次比较 a b c d e f (g) h i j k p q [a..q] 第二次比较 a b (c) d e f g h i j k p q [a..f] 第三次比较 (a) b c d e f g h i j k p q [a..b] (2)g的查找过程如下,一次比较成功。 [abcdef(g)hijkpq] (3)n的查找过程如下, 经过四次比较,查找失败。 下标 1 2 3 4 5 6 7 8 9 10 11 12 13 区间 第一次比
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 考前