《考研计算机专业课复习之数据结构》由会员分享，可在线阅读，更多相关《考研计算机专业课复习之数据结构（13页珍藏版）》请在金锄头文库上搜索。
1、计算机专业课复习之数据结构考查目标计算机学科专业基础综合考试涵盖数据机构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。考试形式和试卷结构一、试卷满分及考试时间本试卷满分为150分，考试时间为180分钟二、 答题方式答题方式为闭卷、笔试三、试卷内容结构数据结构 45分计算机组成原理 45分操作系统 35分计算机网络 25分四、试卷题型结构单项选择题 80分（40小题，每小题2分）：数据结构1-11题，共22分综合应用题 70分：数据结构41
2、题,42题（算法设计题），共23分计算机专业课复习之数据结构注重2014年考纲增加的内容，属必考内容【绪论】(1小题)主要考察时间复杂的计算年份（年）单选题综合题考查内容20100涉及算法题中分析所写的时间复杂度和空间复杂度20111题*2涉及分析给定算法的时间复杂度；算法题中分析所写的时间复杂度和空间复杂度20121题*2涉及分析给定算法的时间复杂度；算法题中分析所写的时间复杂度和空间复杂度1.（12,2分）求整数n(n0)阶乘的算法如下，其时间复杂度是( ) int fact(int n) if (n=l)return 1; return n*fact(n-1); A. 0(log2n)
3、B. 0(n)C. (nlog2n) D. 0(n2)考点：分析给定算法的时间复杂度2.（11,2分）设n 是描述问题规模的非负整数，下面的程序片段的时间复杂度是( )x=2; while(xg转换 为等价的后缀表达式ab+aCd+e/f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是( ) A. 5 B. 7 C. 8 D. 11考点：栈在表达式转换中的应用2.（11,2分）元素a,b,c,d,e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d 开头的序列个数是(
4、 )A.3 B.4 C.5 D.6考点：出栈序列的合法性3.（10,2分）若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行。但不允许连续三次进行退栈工作，则不可能得到的出栈序列是( )A. d c e b f a B. c b d a e f C. d b c a e f D. a f e d c b考点：出栈序列的合法性4.（09,2分）设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是( )A1 B.2 C.3 D.4考点：栈的最大深度【队列】队列的入出及合法性，队列、循环
5、队列、双端队列的性质及应用1.（11,2分）已知循环队列存储在一维数组A0n-1中，且队列非空时front 和rear 分别指向队头和队尾元素若初始时队列为空，且要求第1 个进入队列的元素存储在A0处，则初始时front 和rear 的值分别是( )A.0,0 B.0,n-1 C.n-1,0 D,n-1,n-1考点：循环队列的特征2.（10,2分）某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是( )A. b a c d e B. d b a c e C. d b c a e D. e c b a d考点：双端队列出队序列的合法性3.（09,2分）为解决计算机与
6、打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( )A.栈 B.队列 C.树 D.图考点：队列的常见应用【树与二叉树】（3个左右小题），注重考察实用性（如二叉树的遍历；最小平衡二叉树的特点等），今年同时注重二叉树的全部内容（二叉树的性质、遍历、平衡二叉树等重要知识点）1本章不排除会有算法题涉及树的遍历。2树和二叉树的性质、遍历操作、转换、存储结构和操作特性等，满二叉树、完全二叉树、线索二叉树、哈弗曼树的定义和性质，二叉排序树和二叉平衡树的性质和操作等都是选择题必然会涉及的内容。年份（年）单
7、选题综合题考查内容20094题*20给定结点序列的遍历方式；二叉平衡树的定义；完全二叉树的性质与结点特性；树和二叉树转换的性质20104题*20后续线索树的定义；平衡二叉树的插入操作；树的性质（度与结点数的关系）；哈弗曼树的特点；20114题*20完全二叉树的特性；二叉树的各种遍历序列的联系；树和二叉树的转换；二叉排序树的性质；20122题*20二叉树的遍历；最小平衡二叉树的特点；二叉树性质1.（11,2分）若一棵完全二叉树有768 个结点，则该二叉树中叶子结点的个数是( )A.257 B.258 C.384 D.385考点：完全二叉树的特性2.（10,2分）在一棵度为4的树T中，若有20个度
8、为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶节点个数是( )A.41 B.82 C.113 D.122考点：树的性质（度与结点数的关系）3.（09,2分）已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是( )A39 B.52 C.111 D.119考点：完全二叉树的性质与结点特性遍历1.（12,2分）若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，则根结点的孩子结点( )A.只有e B.有e、b C.有e、c D.无法确定考点：二叉树的遍历2.（11,2分）若一棵二叉树的前序遍历序列和后序
9、遍历序列分别为1,2,3,4 和4,3,2,1，则该二叉树的中序遍历序列不会是( )A.1,2,3,4 B.2,3,4,1 C.3,2,4,1 D.4,3,2,1考点：二叉树的各种遍历序列的联系3.（09,2分）给定二叉树图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是( )ALRN B.NRL C.RLN D.RNL考点：给定结点序列的遍历方式平衡二叉树1.（12,2分）若平衡二叉树的髙度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为( )A. 10 B. 20 C. 32 D. 33考点
10、：最小平衡二叉树的特点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.115 B.116 C.1895 D.1896考点：树和二叉树的转换2.（09,2分）将森林转换为对应的二叉树
11、，若在二叉树中，结点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,71 B.92,20,91,34,88,35 C.21,89,77,29,36,38 D.12,25,71,68,33,34考点：二叉排序树的性质线索二叉树3.（10,2分）下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是( )考点：后续线索树的定义哈夫曼树6.（10,2分）对n(n大于等于2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是( )A.该树一定是一棵完全二叉树B.树中一定没有度为1的结点C.树中两个权值最小的结点一定是兄弟结点D.树中任一非叶结点的权值一定不小于下一任一结点的权值考点：哈弗曼树的特点【图】（3小题或1小题+1大题）今年注重图的大题是一个方向，选择题仍是图本身的性质。若不考大题，图倾向于考选择题，倾向于图中知识点的操作过程、性质（拓
