计算机数据结构今年考研真题及答案.doc

该【计算机数据结构今年考研真题及答案 】是由【小吴】上传分享，文档一共【23】页，该文档可以免费在线阅读，需要了解更多关于【计算机数据结构今年考研真题及答案 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机那么依次从该缓冲区中取出数据。,元素abcdefg依次进入栈S。假设每个元素出栈后立即进入队列Q,且7个元素出队的顺序是bdcfeag,。设N代表二叉树的根,L代表根结点的左子树,R代表根结点的右子树。假设遍历后的结点序列为3,1,7,5,6,2,4,,〔设根为第1层〕有8个叶结点,,假设在二叉树中,结点u是结点v的父结点的父结点,那么在原来的森林中,、,,,8,12,19,28,20,15,22是小根堆〔最小堆〕,插入关键字3,,5,12,8,28,20,15,22,,5,12,19,20,15,22,8,,8,12,5,20,15,22,28,,12,5,8,28,20,15,22,,12,13,7,8,9,23,4,5是采用以下排序方法之一得到的第二趟排序后的结果,.〔10分〕带权图〔权值非负,表示边连接的两顶点间的距离〕的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点;②选择离u最近且尚未在最短路径中的一个顶点v,参加到最短路径中,修改当前顶点u=v;③重复步骤②,直到u是目标顶点时为止。请问上述方法能否求得最短路径?假设该方法可行,请证明之;否那么,请举例说明。42.〔15分〕一个带有表头结点的单链表,结点结构为datalink假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点〔k为正整数〕。假设查找成功,算法输出该结点的data值,并返回1;否那么,只返回0。要求:〔1〕描述算法的根本设计思想〔2〕描述算法的详细实现步骤〔3〕根据设计思想和实现步骤,采用程序设计语言描述算法〔使用C或C++或JAVA语言实现〕,关键之处请给出简要注释。20241、假设元素a,b,c,d,e,f依次进栈,允许进栈、退栈操作交替进行。但不允许连续三次进行退栈工作,那么不可能得到的出栈序列是〔〕A:dcebfaB:cbdaefC:dbcaefD:afedcb2、某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作,那么不可能得到的顺序是〔〕A:bacdeB:dbaceC:dbcaeD:ecbad3、以下线索二叉树中〔用虚线表示线索〕,符合后序线索树定义的是〔〕4、在以下所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树,在新平衡二叉树中,关键字37所在结点的左、右子结点中保存的关键字分别是〔〕A:13,48B:24,48C:24,53D:24,905、在一棵度为4的树T中,假设有20个度为4的结点,10个度为3的结点,1个度为2的结点,10个度为1的结点,那么树T的叶节点个数是〔〕A:41B:82C:113D:1226、对n(n大于等于2)个权值均不相同的字符构成哈夫曼树,关于该树的表达中,错误的选项是〔〕A:该树一定是一棵完全二叉树B:树中一定没有度为1的结点C:树中两个权值最小的结点一定是兄弟结点D:树中任一非叶结点的权值一定不小于下一任一结点的权值7、假设无向图G-〔〕中含7个顶点,那么保证图G在任何情况下都是连通的,那么需要的边数最少是〔〕A:6B:15C:16D:218、对以下列图进行拓补排序,可以得到不同的拓补序列的个数是〔〕A:4B:3C:2D:19、一个长度为16的顺序表L,其元素按关键字有序排列,假设采用折半查找法查找一个不存在的元素,那么比较次数最多是〔〕A:4B:5C:6D:710、采用递归方式对顺序表进行快速排序,以下关于递归次数的表达中,正确的选项是〔〕A:递归次数与初始数据的排列次序无关B:每次划分后,先处理较长的分区可以减少递归次数C:每次划分后,先处理较短的分区可以减少递归次数D:递归次数与每次划分后得到的分区处理顺序无关11、对一组数据〔2,12,16,88,5,10〕进行排序,假设前三趟排序结果如下〔〕第一趟:2,12,16,5,10,88第二趟:2,12,5,10,16,88第三趟:2,5,10,12,16,88那么采用的排序方法可能是:A:起泡排序B:希尔排序C:归并排序D:基数排序41.〔10分〕将关键字序列〔7、8、11、18、9、14〕散列存储到散列列表中,散列表的存储空间是一个下标从0开始的一个一维数组散列函数维:H〔key〕=〔key×3〕MODT,处理冲突采用线性探测再散列法,要求装填〔载〕:〔1〕请画出所构造的散列表;〔2〕分别计算等概率情况下,查找成功和查找不成功的平均查找长度。42.〔13分〕设将n(n,1)个整数存放到一维数组R中,试设计一个在时间和空间两方面尽可能有效的算法,将R中保有的序列循环左移P〔0﹤P﹤n〕个位置,即将R中的数据由〔X0X1……Xn-1〕变换为〔XpXp+1……Xn-1X0X1……Xp-1〕要求:〔1〕给出算法的根本设计思想。〔2〕根据设计思想,采用C或C++或JAVA语言表述算法关键之处给出注释。〔3〕,下面程序片段的时间复杂度是 x=2; while(x<n/2) x=2*x; (log2n)(n)(nlog2n)(n2),b,c,d,e依次进入初始为空的栈中,假设元素进栈后可停留、可出栈,直到所有元素都出栈,那么在所有可能的出栈序列中,[0..n-1]中,且队列非空时front和rear分别指向队头元素和队尾元素。假设初始时队列为空,且要求第1个进入队列的元素存储在A[0]处,,,n--1,-1,n-,,2,3,4和4,3,2,1,,2,3,,3,4,,2,4,,3,2,,其叶结点个数为116,,,22,91,24,94,,20,91,34,88,,89,77,29,36,,25,71,68,33,,,,、、(Hash)表的查找效率,(载)(碰撞)(碰撞)时防止产生聚集(堆积)、、,,13,10,12,9是大根堆,在序列尾部插入新元素18,将其再调整为大根堆,.(8分)有6个顶点(顶点编号为0~5)的有向带权图G,其邻接矩阵A为上三角矩阵,按行为主序(行优先)保存在如下的一维数组中。要求:(1)写出图G的邻接矩阵A。(2)画出有向带权图G。(3)求图G的关键路径,并计算该关键路径的长度。42.(15分)一个长度为L(L≥1)的升序序列S,处在第éL/2ù个位置的数称为S的中位数。例如,假设序列S1=(11,13,15,17,19),那么S1的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如,假设S2=(2,4,6,8,20),那么S1和S2的中位数是11。现有两个等长升序序列A和B,试设计一个在时间和空间两方面都尽可能高效的算法,找出两个序列A和B的中位数。要求:(1)给出算法的根本设计思想。(2)根据设计思想,采用C或C++或JAVA语言描述算法,关键之处给出注释。(3)说明你所设计算法的时间复杂度和空间复杂度。20241、求整数n(n≥0)阶乘的算法如下,其时间复杂度是()intfact(intn){if(n<=1)return1;returnn*fact(n-1);}(log2n)(n)C.(nlog2n)(n2)2、操作符包括‘+’、‘-’、‘*’、‘/’、‘(’和‘)’。将中缀表达式a+b-a*((c+d)/e-f)+g转换为等价的后缀表达式ab+acd+e/f-**-g+时,用栈来存放暂时还不能确定运算次序的操作符,假设栈初始时为空,那么转换过程中同时保存栈中的操作符的最大个数是()、假设一颗二叉树的前序遍历序列为a,e,b,d,c,后续遍历序列为b,c,d,e,a,那么根节点的孩子节点()、、、假设平衡二叉树的高度为6,且所有非叶节点的平衡因子均为1,那么该平衡二叉树的节点总数为()、对有n个节点、e条边且使用邻接表存储的有向图进行广度优先遍历,其算法时间复杂度()(n)(e)(n+e)(n*e)6、假设用邻接矩阵存储有向图,矩阵中主对角线以下的元素均为零,那么关于该图拓扑序列的结构是(),,,、如下有向带权图,假设采用迪杰斯特拉〔Dijkstra〕算法求源点a到其他各顶点的最短路径,得到的第一条最短路径的目标顶点是b,第二条最短路径的目标顶点是c,后续得到的其余各最短路径的目标顶点依次是(),e,,d,,d,,e,d8、以下关于最小生成树的说法中,正确的选项是()Ⅰ、最小生成树的代价唯一Ⅱ、所有权值最小的边一定会出现在所有的最小生成树中Ⅲ、使用普里姆〔Prim〕算法从不同顶点开始得到的最小生成树一定相同Ⅳ、使用普里姆算法和克鲁斯卡尔〔Kruskal〕ⅠⅡⅠ、ⅢⅡ、Ⅳ9、一棵3阶B-树,如以下列图所示。删除关键字78得到一棵新B-树,其最右叶结点中的关键字是(),,、在内部排序过程中,对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。以下排序方法中,每一趟排序结束都至少能够确定一个元素最终位置的方法是()Ⅰ.简单项选择择排序Ⅱ.希尔排序Ⅲ.快速排序Ⅳ.堆排序Ⅴ.Ⅰ、Ⅲ、ⅣⅠ、Ⅲ、ⅤⅡ、Ⅲ、ⅣⅢ、Ⅳ、Ⅴ,两者之间可能的不同之处是()、问答题。41、〔10分〕设有6个有序表A、B、C、D、E、F,分别含有10、35、40、50、60和200个数据元素,各表中元素按升序排列。要求通过5次两两合并,将6个表最终合并成1个升序表,并在最坏情况下比较的总次数到达最小。请答复以下问题。〔1〕给出完整的合并过程,并求出最坏情况下比较的总次数。〔2〕根据你的合并过程,描述N(N≥2)个不等长升序表的合并策略,并说明理由。42、〔13分〕假定采用带头结点的单链表保存单词,当两个单词有相同的后时缀,那么可共享相同的后缀存储空间,例如,“loaging〞和“being〞,如以下列图所示。设str1和str2分别指向两个单词所在单链表的头结点,链表结点结构为〔data,next〕,请设计一个时间上尽可能高效的算法,找出由str1和str2所指向两个链表共同后缀的起始位置〔如图中字符i所在结点的位置p〕。要求:〔1〕给出算法的根本设计思想。〔2〕根据设计思想,采用C或C++或java语言描述算法关键之处给出注释。〔3〕说明你所设计算法的时复杂度。,假设将它们合并为一个长度为m+n的降序链表,(n)(m*n)(min(m,n))(max(m,n)),2,3,,n,其出栈序列是p1,p2,p3,pn。假设p2=3,那么p3可能取值的个数是:---,2,3,4,5,6,7依次插入到初始为空的平衡二叉树T中,,3,4,5,6,7,T的带权〔外部〕,且X存在左兄弟结点Y,,删除某结点v之后形成二叉排序树T2,再将v插入T2形成二叉排序树T3。以下关于T1与T3的表达中,,,,,、、、、。,2,1,,2,1,,4,2,,4,2,,那么以下选项中,,c,a,b,d,e,g,,a,f,g,b,h,c,,b,c,a,h,e,f,,b,c,d,h,e,f,g9、以下的AOE网表示一项包含8个活动的工程。通过同时加快假设干活动的进度可以缩短整个工程的工期。以下选项中,加快其进度就可以缩短整个工程的工期的是:Ac和eBd和eCf和dDf和h10、在一棵高为2的5阶B树中,所含关键字的个数最少是A5B7C8D14A=?(?0,5,5,3,5,7,5,5?),侧5为主元素;又如A=?(?0,5,5,3,5,1,5,7?),那么A中没有主元素。假设A中的n个元素保存在一个一维数组中,请计一个尽可能高效的算法,找出A的主元素。假设存在主元素,那么输出该元素;否那么输出-1。要求:?????〔1〕给出算法的根本设计思想。?〔2〕根据设计思想,采用C或C++或Java语言描述算法,关键之处给出释。???〔3〕说明你所设计算法的时间复杂度和空间复杂度。42.〔10分〕设包含4个数据元素的集合S={?"do","for","?repeat","?while"},各元素查找概率依次为:p1=,p2?=?,p3=0.?15,p4=。将S保存在一个长度为4的顺序表中,采用折半查找法,。请答复:〔1〕假设采用顺序存储结构保存S,且要求平均查找长度更短,那么元素应如何排列?应使用何种查找方法?查找成功时的平均查找长度是多少?〔2〕假设采用链式存储结构保存S,且要求平均查找长度更短,那么元素应如何排列?应使用何种查找方法?查找成功时的平均查找长度是多少?=0;for(k=1;k<=n;k*=2)for(j=1;j<=n;j+1)count++;(log2n)(n)(nlog2n)(n2),将中缀表达式转换为等价后缀表达式的过程中,当扫描到f时,[0…M-1]中,end1指向队头元素,end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作,队列中最多能容纳M-1个元素。初始时为空,以下判断队空和队满的条件中,:end1==end2;队满:end1==(end2+1):end1==end2;队满:end2==(end1+1)mod(M-1):end2==(end1+1)modM;队满:end1==〔end2+1〕:end1==〔end2+1〕modM;队满:end2==(end1+1)mod(M-1),那么结点x的左、,,,,,,,0000,0001,001,,000,001,010,,001,010,011,,001,010,011,,,1,2,4,5,,1,2,4,6,,1,4,2,5,,1,4,2,6,〔散列〕方法处理冲突〔碰撞〕时可能出现堆积〔聚集〕现象,以下选项中,〔装载〕,,假设第1趟排序结果为9,1,4,13,7,8,20,23,15,那么该趟排序采用的增量〔间隔〕,,3,5,4,6,7,,7,5,6,4,3,,2,5,4,7,6,,2,3,5,7,6,941.〔13分〕二叉树的带权路径长度〔WPL〕是二叉树中所有叶结点的带权路径长度之和,给定一棵二叉树T,采用二叉链表存储,节点结构为: