考研计算机专业课复习之数据结构.doc

该【考研计算机专业课复习之数据结构 】是由【小果冻】上传分享，文档一共【13】页，该文档可以免费在线阅读，需要了解更多关于【考研计算机专业课复习之数据结构 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。计算机专业课复****之数据结构Ⅰ考查目标计算机学科专业根底综合考试涵盖数据机构、计算机组成原理、操作系统和计算机网络等学科专业根底课程。要求考生比较系统地掌握上述专业根底课程的根本概念、根本原理和根本方法,能够综合运用所学的根本原理和根本方法分析、判断和解决有关理论问题和实际问题。Ⅱ考试形式和试卷结构一、试卷总分值及考试时间本试卷总分值为150分,考试时间为180分钟二、答题方式答题方式为闭卷、笔试三、试卷内容结构数据结构45分计算机组成原理45分操作系统35分计算机网络25分四、试卷题型结构单项选择题80分〔40小题,每题2分〕:数据结构1-11题,共22分综合应用题70分:数据结构41题,42题〔算法设计题〕,共23分计算机专业课复****之数据结构注重2024年考纲增加的内容,属必考内容【绪论】(1小题)主要考察时间复杂的计算年份〔年〕单项选择题综合题考查内容20240涉及算法题中分析所写的时间复杂度和空间复杂度20241题*2’涉及分析给定算法的时间复杂度;算法题中分析所写的时间复杂度和空间复杂度20241题*2’涉及分析给定算法的时间复杂度;算法题中分析所写的时间复杂度和空间复杂度1.〔12,2分〕求整数n(n≥0)阶乘的算法如下,其时间复杂度是()intfact(intn){if(n<=l)return1;returnn*fact(n-1);}(log2n)(n) C.(nlog2n)(n2)考点:分析给定算法的时间复杂度2.〔11,2分〕设n是描述问题规模的非负整数,下面的程序片段的时间复杂度是()x=2;while(x<n/2)x=2*x;(log2n)(n)(nlog2n)(n2)考点:分析给定算法的时间复杂度【栈和队列】〔2小题〕主要考察栈和队列的入出及合法性1命题的形式比较灵巧。2其中栈〔出入栈的过程、出栈序列的合法性〕和队列的操作及其特征是重中之重。3此外,栈和队列的顺序存储结构、链式存储结构及其特点、栈和队列的常见应用,以及数组和特殊矩阵的压缩存储都是读者必须掌握的内容。20242题*2’0队列的常见应用;栈的最大深度20242题*2’0出栈序列的合法性双端队列出队序列的合法性20242题*2’0出栈序列的合法性循环队列的特征20241题*2’0栈在表达式转换中的应用【栈】栈的入出及栈的合法性,注重共享栈的性质及操作1.〔12,2分〕操作符包括'+'、'/'、'('和')'。将中缀表达式a+b-a*((cd)/e-l>g转换为等价的后缀表达式ab+aCd+e/f-*-g+时,用栈来存放暂时还不能确定运算次序的操作符,假设栈初始时为空,那么转换过程中同时保存在栈中的操作符的最大个数是() :栈在表达式转换中的应用2.〔11,2分〕元素a,b,c,d,e依次进入初始为空的栈中,假设元素进栈后可停留、可出栈,直到所有元素都出栈,那么在所有可能的出栈序列中,以元素d开头的序列个数是():出栈序列的合法性3.〔10,2分〕假设元素a,b,c,d,e,f依次进栈,允许进栈、退栈操作交替进行。但不允许连续三次进行退栈工作,那么不可能得到的出栈序列是()????????:出栈序列的合法性4.〔09,2分〕设栈S和队列Q的初始状态均为空,元素abcdefg依次进入栈S。假设每个元素出栈后立即进入队列Q,且7个元素出队的顺序是bdcfeag,那么栈S的容量至少是??()??????考点:栈的最大深度【队列】队列的入出及合法性,队列、循环队列、双端队列的性质及应用1.〔11,2分〕循环队列存储在一维数组A[0…n-1]中,且队列非空时front和rear分别指向队头和队尾元素假设初始时队列为空,且要求第1个进入队列的元素存储在A[0]处,那么初始时front和rear的值分别是(),,n--1,0D,n-1,n-1考点:循环队列的特征2.〔10,2分〕某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作,那么不可能得到的顺序是()???????????:双端队列出队序列的合法性3.〔09,2分〕为解决计算机与打印机之间速度不匹配的问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机那么依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是??()?????考点:队列的常见应用【树与二叉树】〔3个左右小题〕,注重考察实用性〔如二叉树的遍历;最小平衡二叉树的特点等〕,今年同时注重二叉树的全部内容〔二叉树的性质、遍历、平衡二叉树等重要知识点〕1本章不排除会有算法题涉及树的遍历。2树和二叉树的性质、遍历操作、转换、存储结构和操作特性等,满二叉树、完全二叉树、线索二叉树、哈弗曼树的定义和性质,二叉排序树和二叉平衡树的性质和操作等都是选择题必然会涉及的内容。年份〔年〕单项选择题综合题考查内容20244题*2’0给定结点序列的遍历方式;二叉平衡树的定义;完全二叉树的性质与结点特性;树和二叉树转换的性质20244题*2’0后续线索树的定义;平衡二叉树的插入操作;树的性质〔度与结点数的关系〕;哈弗曼树的特点;20244题*2’0完全二叉树的特性;二叉树的各种遍历序列的联系;树和二叉树的转换;二叉排序树的性质;20242题*2’0二叉树的遍历;最小平衡二叉树的特点;二叉树性质1.〔11,2分〕假设一棵完全二叉树有768个结点,那么该二叉树中叶子结点的个数是():完全二叉树的特性2.〔10,2分〕在一棵度为4的树T中,假设有20个度为4的结点,10个度为3的结点,1个度为2的结点,10个度为1的结点,那么树T的叶节点个数是()????????:树的性质〔度与结点数的关系〕3.〔09,2分〕一棵完全二叉树的第6层〔设根为第1层〕有8个叶结点,那么完全二叉树的结点个数最多是??()???????考点:完全二叉树的性质与结点特性遍历1.〔12,2分〕假设一棵二叉树的前序遍历序列为a,e,b,d,c,后序遍历序列为b,c,d,e,a,那么根结点的孩子结点() 、、:二叉树的遍历2.〔11,2分〕假设一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1,那么该二叉树的中序遍历序列不会是(),2,3,,3,4,,2,4,,3,2,1考点:二叉树的各种遍历序列的联系3.〔09,2分〕给定二叉树图所示。设N代表二叉树的根,L代表根结点的左子树,R代表根结点的右子树。假设遍历后的结点序列为3,1,7,5,6,2,4,那么其遍历方式是()?????????考点:给定结点序列的遍历方式平衡二叉树1.〔12,2分〕假设平衡二叉树的髙度为6,且所有非叶结点的平衡因子均为1,那么该平衡二叉树的结点总数为() :最小平衡二叉树的特点2.〔10,2分〕在以下所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树,在新平衡二叉树中,关键字37所在结点的左、右子结点中保存的关键字分别是(),48??,48??,53??,90考点:平衡二叉树的插入操作3.〔09,2分〕以下二叉排序树中,满足平衡二叉树定义的是??()??考点:二叉平衡树的定义树、森林与二叉树1.〔11,2分〕一棵有2024个结点的树,其叶结点个数为116,该树对应的二叉树中无右孩子的结点的个数是():树和二叉树的转换2.〔09,2分〕将森林转换为对应的二叉树,假设在二叉树中,结点u是结点v的父结点的父结点,那么在原来的森林中,u和v可能具有的关系是?()??????????III.?u的父结点与v的父结点是兄弟关系?????????????????????????、II和III??考点:树和二叉树转换的性质二叉排序树7.〔11,2分〕对于以下关键字序列,不可能构成某二叉排序树中一条查找路径的序列是(),22,91,24,94,,20,91,34,88,,89,77,29,36,,25,71,68,33,34考点:二叉排序树的性质线索二叉树3.〔10,2分〕以下线索二叉树中〔用虚线表示线索〕,符合后序线索树定义的是()考点:后续线索树的定义哈夫曼树6.〔10,2分〕对n(n大于等于2)个权值均不相同的字符构成哈夫曼树,关于该树的表达中,错误的选项是()??:哈弗曼树的特点【图】〔3小题或1小题+1大题〕今年注重图的大题是一个方向,选择题仍是图本身的性质。假设不考大题,图倾向于考选择题,倾向于图中知识点的操作过程、性质〔拓扑排序、最小生成树、最短路径和关键路径等〕,弱化图本身的概念性质。1应掌握图的各种根本概念及根本性质〔度、路径长度、回路、路径等〕、图的存储结构〔邻接矩阵和邻接表〕及其特性、存储结构之间转化、基于存储结构上的遍历操作2各种应用〔拓扑排序、最小生成树、最短路径和关键路径等〕。3图的相关算法,通常是要求掌握其根本思想和实现的步骤〔能动手模拟〕。年份〔年〕单项选择题综合题考查内容20241题*2’1题*10’无向连通图的特性;带权图最短路径的解决方法;20242题*2’0连通图的性质;拓扑排序序列;20241题*2’1题*8’图的根本性质;图的存储以及计算关键路径;20244题*2’0图〔邻接表〕的广义优先遍历的时间复杂度;图邻接矩阵与拓扑排序的关系;Dijkstra算法求图的最短路径;最小生成树的性质;图本身的概念性质1.〔11,2分〕以下关于图的表达中,正确的选项是()①回路是简单路径②存储稀疏图,用邻接矩阵比邻接表更省空间③假设有向图中存在拓扑序列,①B仅①、②C仅③D仅①、③考点:图的根本性质2.〔10,2分〕假设无向图G-〔〕中含7个顶点,那么保证图G在任何情况下都是连通的,那么需要的边数最少是()???:连通图的性质3.〔09,2分〕以下关于无向连通图特性的表达中,正确的选项是()????????????????B.?只有II???????考点:无向连通图的特性拓扑序列6.〔12,2分〕假设用邻接矩阵存储有向图,矩阵中主对角线以下的元素均为零,那么关于该图拓扑序列的结构是(),且唯一 ,,可能不唯一 :图邻接矩阵与拓扑排序的关系8.〔10,2分〕对以下列图进行拓扑排序,可以得到不同的拓扑序列的个数是()???????:拓扑排序序列广度优先遍历算法时间复杂度5.〔12,2分〕对有n个结点、e条边且使用邻接表存储的有向图进行广度优先遍历,其算法时间复杂度是()(n) (e) (n+e)(n*e)考点:图〔邻接表〕的广义优先遍历的时间复杂度最小生成树性质8.〔12,2分〕以下关于最小生成树的说法中,正确的选项是()I. 最小生成树树的代价唯一II. 权值最小的边一定会出现在所有的最小生成树中III. 用普里姆〔Prim)算法从不同顶点开始得到的最小生成树一定相同IV. 普里姆算法和克鲁斯卡尔〔Kmskal) 、III 、IV考点:最小生成树的性质迪杰斯特拉〔Dijkstra)算法7.〔12,2分〕如下有向带权图,假设采用迪杰斯特拉〔Dijkstra)算法求源点a到其他各顶点的最短路径,得到的第一条最短路径的目标顶点是b,第二条最短路径的目标顶点是C,那么到的其余各最短路径的目标顶点依次是【此题的权值和选项可能不准确】()db 3 3 4fa 1 4 1ec 5 1 .…D.…考点:Dijkstra算法求图的最短路径【查找】〔1小题〕性质根本已考过,注重考察操作过程。散列〔Hash〕表和折半查找的操作过程,折半查找及B树的性质。1对于散列查找,应掌握散列表的构造〔散列函数和装填因子的关系〕、冲突处理方法〔各种方法的处理过程〕、查找成功和查找失败的平均查找长度、散列查找的特征和性能分析。2读者还应掌握折半查找的过程、构造判定树、分析查找成功和查找失败的平均查找长度等。3B-和B+树是本章的难点,考纲仅要求了解B+树的根本概念和性质,而B-树那么要求掌握插入、删除和查找操作的过程〔不要求掌握算法〕。年份〔年〕单项选择题综合题考查内容20241题*2’0B树的定义20241题*2’1题*10’折半查找的性质;散列表的构造和平均查找长度;20241题*2’0散列表查找的性质;算法题中结合折半查找;20241题*2’0B树的删除〔结点的合并〕459.〔12,2分〕己知一棵3阶B树,如以下列图所示。删除关键字78得到一棵新B树,其最右叶结点中的关键字是() ,62 ,65 :B树的删除〔结点的合并〕9.〔11,2分〕为提高散列〔Hash〕表的查找效率,可采取的正确措施是()①增大装填因子②设计冲突少的散列函数③处理冲突时防止产证聚集现象仅①②①②②③考点:散列表查找的性质9.〔10,2分〕一个长度为16的顺序表L,其元素按关键字有序排列,假设采用折半查找法查找一个不存在的元素,那么比较次数最多是()???????:折半查找的性质?8.〔09,2分〕以下表达中,不符合m阶B树定义要求的是()???????????考点:B树的定义【排序】〔2小题〕倾向于排序的比较、性质,弱化排序过程,但麻烦容易出错的仍会考。外部排序通常采用归并排序方法。出题方向可能是12年大题的思路或者外排的性质、思想、比较的总体把握。1堆排序〔建堆、插入和调整〕和快速排序〔划分、过程特征〕是重点。2读者应深入掌握各种排序算法的思想、排序过程〔能动手模拟〕和特征〔初态的影响、时空复杂度、稳定性、适用性等〕。3此外,对某特定序列,读者应具有选择最优排序算法〔根据排序算法特征〕的能力。年份〔年〕单项选择题综合题考查内容20242题*2’0堆的插入和调整;各种排序算法的排序过程和特征;20242题*2’0快速排序的特征;各种排序算法的排序过程和特征;20242题*2’0快速排序的特征;堆的插入和调整;20242题*2’1题*10’各种排序算法的特征;折半插入排序和直接插入排序的比较;最正确归并的过程〔归并排序与哈弗曼树的综合〕;10.〔12,2分〕在内部排序过程中,对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。以下排序方法中,每一趟排序结束都至少能够确定一个元素最终位置的方法是() 、III、IV 、III、、III、IV 、IV、V考点:各种排序算法的特征11.〔12,2分〕对一待排序序列分别进行折半插入排序和直接插入排序,两者之间可能的不同之处是() :折半插入排序和直接插入排序的比较10.〔11,2分〕为实现快速排序算法,待排序序列宜采用的存储方式是():快速排序的特征11.〔11,2分〕序列25,13,10,12,9是大根堆,在序列尾部插入新元素18,将其再调整为大根堆,调整过程中元素之间进行的比较次数是():堆的插入和调整10.〔10,2分〕采用递归方式对顺序表进行快速排序,以下关于递归次数的表达中,正确的选项是(),,:快速排序的特征11.〔10,2分〕对一组数据〔2,12,16,88,5,10〕进行排序,假设前三趟排序结果如下〔〕,12,16,5,10,,12,5,10,16,,5,10,12,16,88那么采用的排序方法可能是()???:各种排序算法的排序过程和特征?9.〔09,2分〕关键序列5,8,12,19,28,20,15,22是小根堆〔最小堆〕,插入关键字3,调整后得到的小根堆是??(),5,12,8,28,20,15,22,19??B.?3,5,12,19,20,15,22,8,28??,8,12,5,20,15,22,28,19??D.?3,12,5,8,28,20,15,22,19??考点:堆的插入和调整?10.〔09,2分〕假设数据元素序列11,12,13,7,8,9,23,4,5是采用以下排序方法之一得到的第二趟排序后的结果,那么该排序算法只能是?()