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

计算机专业课复习之数据结构Ⅰ考查目标计算机学科专业基础综合考试涵盖数据机构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。Ⅱ考试形式和试卷结构一、试卷满分及考试时间本试卷满分为150分，考试时间为180分钟二、答题方式答题方式为闭卷、笔试三、试卷内容结构数据结构45分计算机组成原理45分操作系统35分计算机网络25分四、试卷题型结构单项选择题80分（40小题，每小题2分）：数据结构1-11题，共22分综合应用题70分：数据结构41题,42题（算法设计题），共23分计算机专业课复习之数据结构注重2014年考纲增加的内容，属必考内容【绪论】(1小题)主要考察时间复杂的计算年份（年）单选题综合题考查内容20100涉及算法题中分析所写的时间复杂度和空间复杂度20111题*2’涉及分析给定算法的时间复杂度；算法题中分析所写的时间复杂度和空间复杂度20121题*2’涉及分析给定算法的时间复杂度；算法题中分析所写的时间复杂度和空间复杂度1.（12,2分）求整数n(n≥0)阶乘的算法如下，其时间复杂度是()intfact(intn){if(n<=l)return1;returnn*fact(n-1);}A.0(log2n)B.0(n) C.(nlog2n)D.0(n2)考点：分析给定算法的时间复杂度2.（11,2分）设n是描述问题规模的非负整数，下面的程序片段的时间复杂度是()x=2;while(x<n/2)x=2*x;A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)考点：分析给定算法的时间复杂度【栈和队列】（2小题）主要考察栈和队列的入出及合法性1命题的形式比较灵活。2其中栈（出入栈的过程、出栈序列的合法性）和队列的操作及其特征是重中之重。3此外，栈和队列的顺序存储结构、链式存储结构及其特点、栈和队列的常见应用，以及数组和特殊矩阵的压缩存储都是读者必须掌握的内容。20092题*2’0队列的常见应用；栈的最大深度20102题*2’0出栈序列的合法性双端队列出队序列的合法性20112题*2’0出栈序列的合法性循环队列的特征20121题*2’0栈在表达式转换中的应用【栈】栈的入出及栈的合法性，注重共享栈的性质及操作1.（12,2分）已知操作符包括'+'、'/'、'('和')'。将中缀表达式a+b-a*((cd)/e-l>g转换为等价的后缀表达式ab+aCd+e/f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是()A.5 B.7 C.8 D.11考点：栈在表达式转换中的应用2.（11,2分）元素a,b,c,d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是()A.3B.4C.5D.6考点：出栈序列的合法性3.（10,2分）若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行。但不允许连续三次进行退栈工作，则不可能得到的出栈序列是()A.dcebfa

B.cbdaef

C.dbcaef

D.afedcb考点：出栈序列的合法性4.（09,2分）设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是

()A．1

B.2

C.3

D.4

考点：栈的最大深度【队列】队列的入出及合法性，队列、循环队列、双端队列的性质及应用1.（11,2分）已知循环队列存储在一维数组A[0…n-1]中，且队列非空时front和rear分别指向队头和队尾元素若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是()A.0,0B.0,n-1C.n-1,0D,n-1,n-1考点：循环队列的特征2.（10,2分）某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是()A.bacde

B.dbace

C.dbcae

D.ecbad考点：双端队列出队序列的合法性3.（09,2分）为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是

()A.栈B.队列

C.树

D.图

考点：队列的常见应用【树与二叉树】（3个左右小题），注重考察实用性（如二叉树的遍历；最小平衡二叉树的特点等），今年同时注重二叉树的全部内容（二叉树的性质、遍历、平衡二叉树等重要知识点）1本章不排除会有算法题涉及树的遍历。2树和二叉树的性质、遍历操作、转换、存储结构和操作特性等，满二叉树、完全二叉树、线索二叉树、哈弗曼树的定义和性质，二叉排序树和二叉平衡树的性质和操作等都是选择题必然会涉及的内容。年份（年）单选题综合题考查内容20094题*2’0给定结点序列的遍历方式；二叉平衡树的定义；完全二叉树的性质与结点特性；树和二叉树转换的性质20104题*2’0后续线索树的定义；平衡二叉树的插入操作；树的性质（度与结点数的关系）；哈弗曼树的特点；20114题*2’0完全二叉树的特性；二叉树的各种遍历序列的联系；树和二叉树的转换；二叉排序树的性质；20122题*2’0二叉树的遍历；最小平衡二叉树的特点；二叉树性质1.（11,2分）若一棵完全二叉树有768个结点，则该二叉树中叶子结点的个数是()A.257B.258C.384D.385考点：完全二叉树的特性2.（10,2分）在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶节点个数是()A.41

B.82

C.113

D.122考点：树的性质（度与结点数的关系）3.（09,2分）已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是

()A．39

B.52

C.111

D.119

考点：完全二叉树的性质与结点特性遍历1.（12,2分）若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，则根结点的孩子结点()A.只有e B.有e、bC.有e、cD.无法确定考点：二叉树的遍历2.（11,2分）若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1，则该二叉树的中序遍历序列不会是()A.1,2,3,4B.2,3,4,1C.3,2,4,1D.4,3,2,1考点：二叉树的各种遍历序列的联系3.（09,2分）给定二叉树图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是()

A．LRN

B.NRL

C.RLN

D.RNL

考点：给定结点序列的遍历方式平衡二叉树1.（12,2分）若平衡二叉树的髙度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为()A.10 B.20 C.32 D.33考点：最小平衡二叉树的特点2.（10,2分）在下列所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树，在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是()A.13，48

B.24，48

C.24，53

D.24，90考点：平衡二叉树的插入操作3.（09,2分）下列二叉排序树中，满足平衡二叉树定义的是

()

考点：二叉平衡树的定义树、森林与二叉树1.（11,2分）已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点的个数是()A.115B.116C.1895D.1896考点：树和二叉树的转换2.（09,2分）将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是

()

I．父子关系

II.兄弟关系

III.

u的父结点与v的父结点是兄弟关系

A.只有II

B.I和II

C.I和III

D.I、II和III

考点：树和二叉树转换的性质二叉排序树7.（11,2分）对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是()A.95,22,91,24,94,71B.92,20,91,34,88,35C.21,89,77,29,36,38D.12,25,71,68,33,34考点：二叉排序树的性质线索二叉树3.（10,2分）下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是()考点：后续线索树的定义哈夫曼树6.（10,2分）对n(n大于等于2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是()A.该树一定是一棵完全二叉树

B.树中一定没有度为1的结点C.树中两个权值最小的结点一定是兄弟结点

D.树中任一非叶结点的权值一定不小于下一任一结点的权值考点：哈弗曼树的特点【图】（3小题或1小题+1大题）今年注重图的大题是一个方向，选择题仍是图本身的性质。若不考大题，图倾向于考选择题，倾向于图中知识点的操作过程、性质（拓扑排序、最小生成树、最短路径和关键路径等），弱化图本身的概念性质。1应掌握图的各种基本概念及基本性质（度、路径长度、回路、路径等）、图的存储结构（邻接矩阵和邻接表）及其特性、存储结构之间转化、基于存储结构上的遍历操作2各种应用（拓扑排序、最小生成树、最短路径和关键路径等）。3图的相关算法，通常是要求掌握其基本思想和实现的步骤（能动手模拟）。年份（年）单选题综合题考查内容20091题*2’1题*10’无向连通图的特性；带权图最短路径的解决方法；20102题*2’0连通图的性质；拓扑排序序列；20111题*2’1题*8’图的基本性质；图的存储以及计算关键路径；20124题*2’0图（邻接表）的广义优先遍历的时间复杂度；图邻接矩阵与拓扑排序的关系；Dijkstra算法求图的最短路径；最小生成树的性质；图本身的概念性质1.（11,2分）下列关于图的叙述中，正确的是()①回路是简单路径②存储稀疏图，用邻接矩阵比邻接表更省空间③若有向图中存在拓扑序列，则该图不存在回路A.仅①B仅①、②C仅③D仅①、③考点：图的基本性质2.（10,2分）若无向图G-（V.E）中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是()A.6

B.15

C.16

D.21考点：连通图的性质3.（09,2分）下列关于无向连通图特性的叙述中，正确的是()

I．所有顶点的度之和为偶数

II.边数大于顶点个数减1

III.至少有一个顶点的度为1

A.只有I

B.

只有II

C.I和II

D.I和III

考点：无向连通图的特性拓扑序列6.（12,2分）若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结构是()A.存在，且唯一 B.存在，且不唯一C.存在，可能不唯一 D.无法确定是否存在考点：图邻接矩阵与拓扑排序的关系8.（10,2分）对下图进行拓扑排序，可以得到不同的拓扑序列的个数是()A.4

B.3

C.2

D.1考点：拓扑排序序列广度优先遍历算法时间复杂度5.（12,2分）对有n个结点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是()A.0(n) B.0(e) C.0(n+e)D.0(n*e)考点：图（邻接表）的广义优先遍历的时间复杂度最小生成树性质8.（12,2分）下列关于最小生成树的说法中，正确的是()I. 最小生成树树的代价唯一II. 权值最小的边一定会出现在所有的最小生成树中III. 用普里姆（Prim)算法从不同顶点开始得到的最小生成树一定相同IV. 普里姆算法和克鲁斯卡尔（Kmskal)算法得到的最小生成树总不相同A.仅IB.仅II C.仅I、III D.仅II、IV考点：最小生成树的性质迪杰斯特拉（Dijkstra)算法7.（12,2分）如下有向带权图，若采用迪杰斯特拉（Dijkstra)算法求源点a到其他各顶点的最短路径，得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是C,那么到的其余各最短路径的目标顶点依次是【本题的权值和选项可能不准确】()dbdb 3 3 4fa 1 4fa 1ec 5ec 1 3A.defB.fedC.…D.…考点：Dijkstra算法求图的最短路径【查找】（1小题）性质基本已考过，注重考察操作过程。散列（Hash）表和折半查找的操作过程，折半查找及B树的性质。1对于散列查找，应掌握散列表的构造（散列函数和装填因子的关系）、冲突处理方法（各种方法的处理过程）、查找成功和查找失败的平均查找长度、散列查找的特征和性能分析。2读者还应掌握折半查找的过程、构造判定树、分析查找成功和查找失败的平均查找长度等。3B-和B+树是本章的难点，考纲仅要求了解B+树的基本概念和性质，而B-树则要求掌握插入、删除和查找操作的过程（不要求掌握算法）。年份（年）单选题综合题考查内容20091题*2’0B树的定义20101题*2’1题*10’折半查找的性质；散列表的构造和平均查找长度；20111题*2’0散列表查找的性质；算法题中结合折半查找；20121题*2’0B树的删除（结点的合并）459.（12,2分）己知一棵3阶B树，如下图所示。删除关键字78得到一棵新B树，其最右叶结点中的关键字是()4555651735556517357860624710372178606247103721A.60 B.60,62 C.62,65 D.65考点：B树的删除（结点的合并）9.（11,2分）为提高散列（Hash）表的查找效率，可采取的正确措施是()①增大装填因子②设计冲突少的散列函数③处理冲突时避免产证聚集现象仅①B.仅②C.仅①②D.仅②③考点：散列表查找的性质9.（10,2分）已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查找一个不存在的元素，则比较次数最多是()A.4

B.5

C.6

D.7考点：折半查找的性质

8.（09,2分）下列叙述中，不符合m阶B树定义要求的是()

A．根节点最多有m棵子树

B.所有叶结点都在同一层上

C．各结点内关键字均升序或降序排列

D.叶结点之间通过指针链接

考点：B树的定义【排序】（2小题）倾向于排序的比较、性质，弱化排序过程，但麻烦容易出错的仍会考。外部排序通常采用归并排序方法。出题方向可能是12年大题的思路或者外排的性质、思想、比较的总体把握。1堆排序（建堆、插入和调整）和快速排序（划分、过程特征）是重点。2读者应深入掌握各种排序算法的思想、排序过程（能动手模拟）和特征（初态的影响、时空复杂度、稳定性、适用性等）。3此外，对某特定序列，读者应具有选择最优排序算法（根据排序算法特征）的能力。年份（年）单选题综合题考查内容20092题*2’0堆的插入和调整；各种排序算法的排序过程和特征；20102题*2’0快速排序的特征；各种排序算法的排序过程和特征；20112题*2’0快速排序的特征；堆的插入和调整；20122题*2’1题*10’各种排序算法的特征；折半插入排序和直接插入排序的比较；最佳归并的过程（归并排序与哈弗曼树的综合）；10.（12,2分）在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束都至少能够确定一个元素最终位置的方法是()I.简单选择排序II.希尔排序III.快速排序IV堆排序 V.二路归并排序A.仅I、III、IV B.仅I、III、VC.仅II、III、IV D.仅III、IV、V考点：各种排序算法的特征11.（12,2分）对一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是()A.排序的总趟数 B.元素的移动次数

C.使用辅助空间的数量 D.元素之间的比较次数考点：折半插入排序和直接插入排序的比较10.（11,2分）为实现快速排序算法，待排序序列宜采用的存储方式是()顺序存储B.散列存储C链式存储D索引存储考点：快速排序的特征11.（11,2分）已知序列25,13,10,12,9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是()A.1B.2C.4D.5考点：堆的插入和调整10.（10,2分）采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是()A.递归次数与初始数据的排列次序无关B.每次划分后，先处理较长的分区可以减少递归次数C.每次划分后，先处理较短的分区可以减少递归次数D.递归次数与每次划分后得到的分区处理顺序无关考点：快速排序的特征11.（10,2分）对一组数据（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.基数排序考点：各种排序算法的排序过程和特征

9.（09,2分）已知关键序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后得到的小根堆是

()A．3，5，12，8，28，20，15，22，19

B.

3，5，12，19，20，15，22，8，28

C．3，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是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是

()

A．起泡排序

B.插入排序

C.选择排序

D.二路归并排序

考点：各种排序算法的排序过程和特征大题第一题：今年注重图的大题，栈和队列结合其他章节的大题及其他考过大题的章节的重要知识点和不同知识点【排序】最佳归并的过程（归并排序与哈弗曼树的综合）外部排序41. (12，10分）设有6个有序表A、B、C、D、E、F，分别含有10、35、40、50、60和200,个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。请问答下列问题。(1) 请写出合并方案，并求出最坏情况下比较的总次数。(2) 根据你的合并过程，描述N (N≥2)个不等长升序表的合并策略，并说明理由。考点：最佳归并的过程（归并排序与哈弗曼树的综合）【图】图的存储以及计算关键路径；41.(11，8分)已知有一个6个顶点（顶点编号0～5）的有向带权图G，其邻接矩阵A为上三角矩阵，它的压缩存储如下：46∞∞∞5∞∞∞43∞∞33题41表要求：(1)写出图G的邻接矩阵A；(2)画出有向带权图G；(3)求图G的关键路径，并计算关键路径的长度。考点：图的存储以及计算关键路径【查找】散列表的构造和平均查找长度；41.（10，10分）将关键字序列（7、8、11、18、9、14）散列存储到散列列表中，散列表的存储空间是一个下标从0开始的一个一维数组，散列函数为：H（key）=（key×3）MODT，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。问题：（1）请画出所构造的散列表；（2）分别计算等概率情况下，查找成功和查找不成功的平均查找长度。考点：散列表的构造和平均查找长度【图】带权图最短路径的解决方法；41.（09，10分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法.

①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；

②选择离u最近且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点u=v；

③重复步骤②，直到u是目标顶点时为止。

请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，请举例说明。

考点：带权图最短路径的解决方法第二大题：【线性表】，同时注重树的遍历年份（年）单选题综合题考查内容200901题*15’查找链表中倒数第K个结点201001题*13’将数组中的序列循环左移201101题*15’求两个有序顺序表的中位数201201题*13’求两个单链表的公共结点线性表是考研中的重中之重，近4年的算法设计题都是基于线性表的（顺序表和单链表），这类算法题往往要求具有最优的性能（时间和空间复杂度最优），才能能获得满分。因此，应牢固掌握线性表的各种基本操作（基于两种存储结构），读者在平时的学习中应多注重积累和培养动手能力。另外，需要提醒的是，算法最重要的是思想，在考场上的时间有限，在试卷上答题不一定要求结果具有实际的可执行性。因此不必过于拘泥每一个细节。【单链表】42. (12，13分）假定釆用带头结点的单链表，如果有共同后缀，…则可共享相同的后缀存储空间，例如：“loading”和“being”，如下图所示。题42图“loading”和“being”公共结点stri和str2分别指向两个单词所在单链表的头结点，链表结点结构为datanext

请设计一个时间上尽可能高效的算法，找出由strl