考研数据结构辅导.pdf

全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合考试大纲I .考查目标计算机学科专业基础综合考试是为高等院校和科研院所招收计算机科学与技术学科的硕士研究生而设置的具有选拔性质的联考科目，其目的是科学、公平、有效地测试考生掌握计算机科学与技术学科大学本科阶段专业基础知识、基本理论、基本方法的水平和分析问题、解决问题的能力，评价的标准是高等学校计算机科学与技术学科优秀本科生所能达到的及格或及格以上水平，以利于各高等院校和科研院所择优选拔，确保硕士研究生的入学质量。计算机学科专业基础综合考试涵盖数据机构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生系统地掌握上述专业基础课程的概念、基本原理和基本方法，能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。II.考试形式和试卷结构一、试卷满分及考试时间：本试卷满分为150分，考试时间为 180分钟。二、答题方式：答题方式为闭卷、笔试。三、试卷内容结构数据结构 4 5 分 计算机组成原理 4 5 分操作系统 3 5 分 计算机网络 2 5 分四、试卷题型结构单项选择题 8 0 分（4 0 小题，每小题2 分）综合应用题 7 0 分I I I.考查内容数据结构 考查目标1.掌握数据结构的基本概念、基本原理和基本方法。2.掌握数据的逻辑结构、存储结构及基本操作的实现,能够对算法进行基本的时间复杂度与空间复杂度的分析。3.能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C 或 C+或 Java语言设计与实现算法的能力。一、线性表（一）线性表的定义和基本操作（二）线性表的实现 1.顺序存储结构 2.链式存储结构 3.线性表的应用二、栈、队列和数组（一）栈和队列的基本概念（二）栈和队列的顺序存储结构（三）栈和队列的链式存储结构（四）栈和队列的应用（五）特殊矩阵的压缩存储三、树与二叉树（一）树的基本概念（二）二叉树1.二叉树的定义及其主要特证2.二叉树的顺序存储结构和链式存储结构3.二叉树的遍历4.线索二叉树的基本概念和构造（三）树、森林1.树的存储结构 2.森林与二叉树的转换3.树和森林的遍历（四）树与二叉树的应用1.二叉排序树 2.平衡二叉树 3.哈夫曼（Huffman）树和哈夫曼编码四、图（一）图的基本概念（二）图的存储及基本操作2.邻接表法1.邻接矩阵法（三）图的遍历2.广度优先搜索1.深度优先搜索（四）图的基本应用 1.最 小（代价）生成树2.最短路径 3.拓扑排序 4.关键路径五、查找（-）查找的基本概念（二）顺序查找法（三）折半查找法（四）B 树及其基本操作、B 树的基本概念+（五）散歹U（Hash）表（六）查找算法的分析及应用六、排序（一）排序的基本概念（二）插入排序 1.直接插入排序 2.折半插入排序（三）起泡排序（bubble sort）（四）简单选择排序（五）希尔排序（shell sort）（六）快速排序（七）堆排序（八）二路归并排序（mergesort）（九）基数排序（+）外部排序（十一）各种排序算法的比较（十二）排序算法的应用重点章：绪论 线性表 栈和队列（数组）树图 查 找 排序第1章绪论【复习要点】1.数据结构相关的基本概念和术语2.数据结构的三要素：逻辑结构、物理结构和数据运算3.算法的时间复杂度和空间复杂度的分析与计算【考题分析】2011 年年份单选题/分综合题/分考查内容2009 年002010 年0分析给定程序段的时间复杂度2011 年1题/2V分析给定程序段的时间复杂度；大题中分析所写算法的时间复杂度2012 年1题/2V分析给定程序段的时间复杂度；大题中分析所写算法的时间复杂度2013 年1题/2V分析给定程序段的时间复杂度；大题中分析所写算法的时间复杂度2014 年1题/20分析给定程序段的时间复杂度1.设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是。x=2；while(xn/2)x=2*x；A.O(log2n)B.0(n)C.O(nlog2n)D.0(n2)2012 年1.求整数n(n，0)阶乘的算法如下，其时间复杂度是Oint fact(int n)if(n=1)return 1;return n*fact(n-1);A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)2013 年1.已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最 坏 情 况 下 的 时 间 复 杂 度 是 oA.0(n)B.O(mXn)C.O(min(m,n)D.O(max(m,n)第2章线性表【考纲内容】(-)线性表的定义和基本操作(二)线性表的实现 1.顺序存储结构 2.链式存储结构 3.线性表的应用【考题分析】年份单选题/分综合题/分考查内容2009 年01 题/15查找链表中倒数第k个结点2010 年01 题/13将数组中的序列循环左移2011 年01 题/15求两个有序顺序表中的中位数2012 年01 题/13求两个单链表中的公共结点2013 年01 题/15寻找一个数组序列中的主元素2014 年002009 年42.(15分)已知一个带有表头结点的单链表，结点结构为假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data值，并返回1；否则，只返回0 o要求：(1)描述算法的基本设计思想(2)描述算法的详细实现步骤(3)根据设计思想和实现步骤，采用程序设计语言描述算法(使用C或C+求JAVA博言实现)，关键之处请给出简要注释。2010 年42.(13分)设将n(n,1)个整数存放到一维数组R中,试设计一个在时间和空间两方面尽可能有效的算法，将R中保有的序列循环左移P(0 P n1 2(0 pk n,kk时，指针p 随着每次遍历，也向前移动一个节点。当遍历完成时，p 或者指向表头就节点，或者指向链表中倒数第K 个位置上的节(3)算法描述：int LocateElement(linklist list,int k)P1=list-link;while(P1)P1=P1-link;i+；if(ik)p=p-next;如果 ik,贝U p 也往后移)if(p=list)return 0;说明链表没有k个结点else printf(dn,p-data);return 1;2010 年4 2.循环左移p位解法一：(1)算法的基本设计思想：分三次倒置：先倒置前p个元素，再倒置后np个元素，最后全部元素倒置。(2)详细程序void ReverseSeg(int R,int from jnt to)for(int i=0;i(to-from+1)/2;i+)int temp;temp=Rfrom+i;Rfrom+i=Rto-i;Rto-i=temp;void ConverseLeft(int R,int n,int p)ReverseSeg(R,0,p-1);ReverseSeg(R,p,n-1);ReverseSeg(R,0,n-1);(3)时间复杂度O(N);空间复杂度o(p)解法二：(1)算法的基本设计思想：另设一个临时数组，存放前面的p个元素；将后面的n-p个元素放到前面；再将临时数组中的元素回放到后面。借助辅助数组来实现(2)详细程序void ConverseLeft2(int R,int n,int p)int TMAX;int i;for(i=0;ip;i+)Ti=Ri;for(i=p;in;i+)Ri-p=Ri;for(i=n-p;in;i+)Ri=Ti-p-n;)(3)时间复杂度O(N);空间复杂度o(p)解法三：(1)算法的基本设计思想：每次拿出最前一个元素，将元素向前平移一位；再将拿出的元素放入最后一个位置，重复P次。(2)详细程序void ConverseLeft3(int R,int n,int p)for(int j=O;jp;j+)int temp=R0;for(int i=1;in;i+)Ri1=Ri;Rn-1=temp;(3)时间复杂度0(p X N);空间复杂度o(1)循环右移p 位方法一：分三次倒置：先倒置前n p 个元素，再倒置后 p 个元素，最后全部元素倒置。方法二：另设一个临时数组，存放前面的np 个元素；将后面的p 个元素放到前面；再将临时数组中的元素回放到后面。方法三：每次拿出最后一个元素，将元素向后平移一位；再将拿出的元素放入最前一个位置，重复 P 次。2011 年42.(1)算法的基本设计思路如下：分别求两个升序序列A、B 的中位数，设为a 和 b。求序列A、B 的中位数的过程如下:1)若 a=b,则 a 或 b 即为所求的中位数;2）若a b,则舍弃序列A中较大的一半，同时舍弃序列B中较小的一半,要求两次舍弃的元素个数相同。在保留的两个升序序列中，重复上述过程，直到两个序列中均只含一个元素时为止，则较小者即为所求的中位数。若 2 处，则肯定不在si 的左半边，因为如果在si 的左半边则中位数 b 时,原理同上当S 1 长度为奇数时，左半边=右半边，直接舍弃即可当S 1 长度为偶数时，左半边+1=右半边。若 a b,舍弃a的左半边（包括中点）舍弃b的右半边（保留中点）始终保持S I,S 2 等长int get_middle_number（int a,int b,int n）int startl=0,end1=n-1,m l;/分 另1 J表示序列A的首位数、末尾数和中位数的位置int start2=0,end2=n-1,m2;/分别表示序列A的首位数、末尾数和中位数的位置while(startl!=end1|start2!=end2)(ml=(startl+end1)/2;m2=(start2+end2)/2;if(am1=bm2)/a=breturn am1;if(am1bm2)/abif(start1+end1)%2=0)end1=ml;start2=m2;else end1=m l;start2=m2+1;)return astart1 next!=NULL)len+;head=head-next;return len;)/*找出共同后缀的起始地址7SNode*find_addr(SNode*strl,SNode*str2)int m,n;SNode*p,*q;m=listlen(strl);求 strl 的长度n=listlen(str2);求 str2 的长度for(p=str1;mn;m-)若 mn,使 p指向链表中的第m-n+1个结点p=p-next;for(q=str2;mvn;n“)若 mvn,使 q 指向链表中的第n-m+l个结点q=q-next;while(p-next!=NULL&p-next!=q-next)/将指针p和q同步向后移动p=p-next;q=q-next;/whilereturn p-next;/返回共同后缀的起始地址2013 年42.“在一个集合中，删除两个不同的数，则集合的主元素保持不变。”(1)给出算法的基本设计思想：(4分)算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素机。然后重新计数，确认N机是否是主元素。算法可分为以下两步：选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数加保存至!Jc中，记录N 机的出现次数为1；若遇到的下一个整数仍等于N 帆，则计数加1,否则计数减1；当计数减到0时，将遇到的下一个整数保存到。中，计数重新记为1,开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。判断。中元素是否是真正的主元素：再次扫描该数组，统计c中元素出现的次数，若大于山2,则为主元素；否则，序列中不存在主元素。(2)算法实现：(7分)int Majority(int A,int n)|int i,c,count=l;/c用来保存候选主元素，count用来计数c=A0;/设置A0为候选主元素for(i=l;i 0)主元素的情况count-;else素，重新计数/查找候选主元/对A中的候选/处理不是候选/更换候选主元 c=Ai;count=1;if(count0)for(i=count=0;i n/2)return c;候选主元素else return-1;在主元素(1)、(2)的评分说明】/统计/确认/不存若考生设计的算法满足题目的功能要求且正确，则(1)、(2)根据所实现算法的效率给分，细则见下表：时间复杂度0(n)0(n)空间复杂度。(1)0(n)(1)得分44(2)得 夕760(nlogln)2。(nl)其他其他3365int Majorityl(int A,int n)/采用计数排序思想，时间：0(n),空间：0(n)int k,*p,max;p=(int*)malloc(sizeof(int)*n);/申请辅助计数数组for(k=0;k n;k+)p k=0;/计数数组清0max=0;for(k=0;k p max)max=Ak;/记录出现次数最多的元素if(p max n/2)return max;else return-1;)若在算法的基本设计思想描述中因文字表达没有非常清晰反映出算法思路，但在算法实现中能够清晰看出算法思想且正确的，可参照的标准给分。若算法的基本设计思想描述或算法实现中部分正确，可参照中各种情况的相应给分标准酌情给分。参考答案中只给出了使用C 语言的版本,使用C+或 Java语言的答案视同使用C 语言。(3)说明算法复杂性：(2分)参考答案中实现的程序的时间复杂度为。()，空间复杂度为。(1)o【评分说明】若考生所估计的时间复杂度与空间复杂度与考生所实现的算法一致，可各给 1 分。时间复杂度为线性0(n),基于分治法的线性时间求主元素算法。算法的基本设计思想：中位数：数列排序后位于最中间的那个数。如果一个数列有主元素，那么必然是其中位数。求一个数列有没有主元素，只要看中位数是不是主元素。找中位数的方法:选择一个元素作为划分起点，然后用快速排序的方法将小于它的移动到左边，大于它的移动到右边。这样就将元素划分为两个部分。此时，划分元素所在位置为ko如果kn/2,那么继续用同样的方法在左边部分找；如果kvn/2,就在右边部分找；k=n/2就找到了中位元素。根据快速排序的思想，可以在平均时间复杂度为0(n)的时间内找出一个数列的中位数。然后再用0(n)的时间检查它是否是主元素。C 语言源码如下：int partition(int a,int low,int high)int pivotkey=alow;while(lowhigh)(if(low=pivotkey)-high;if(lowhigh)alow=ahigh;low+;if(lowhigh&alow=pivotkey)+low;if(lowhigh)ahigh=alow;-high;)alow=pivotkey;return low;)快排int quick_sort(int a,int low,int high)if(lown/2)quick_sort(a,low,position-1);else if(positionn/2)quick_sort(a,position+1,high);elsemid=aposition;找 至！J 中位数)int main()int a100;printf(请输入个数nn);scanf(%d,&n);for(int i=1;i=n;i+)(ai=O;初始化for(int i=1;i n/2)printf(有 主 元 素 为%d出现了%d次rT，mid,count);elseprintf(无主元素n”)；system(pauseM);)下面来看看如果无序，不能比较大小的算法，具体思想就是“在一个集合中，删除两个不同的数，则集合的主元素保持不变。”根据这个原理，可以很快求出主元素。只有最后剩下的元素才可能是主元素。#include int getMainElement(int 矶Jnt len)int i,mainElement,repeatTimes=0;每次若不相同则减小这个计数，若相同则增加for(i=0;ilen;i+)if(repeatTimes=0)mainElement=ai;repeatTimes=1;elseif(mainElement=ai)repeatTimes+;elserepeatTimes-;)return mainElement;)int main()while(1)int len,i,mainElement,flagCount=0;scanf(%d,&len);int*a=new intlen;for(i=0;ilen;i+)scanf(M%dM,&ai);)mainElement=getMainElement(a,len);for(i=O;ilen/2)printf(M%dnM5mainElement);elseprintf(Nonen);return 0;)