考研数据结构辅导.docx

全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合考试大纲I .考查目标计算机学科专业基础综合考试是为高等院校和科研院所招收计算机科学与技术学科的硕士研究生而设置的具有选拔性质的联考科目，其目的是科学、公平、有效地测试考生掌握计算机科学与技术学科大学本科阶段专业基础知识、基本理论、基本方法的水平和分析问题、解决问题的能力，评价的标准是高等学校计算机科学与技术学科优秀本科生所能达到的及格或及格以上水平，以利于各高等院校和科研院所择优选拔，确保硕士研究生的入学质量。计算机学科专业基础综合考试涵盖数据机构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生系统地掌握上述专业基础课程的概念、基本原理和基本方法，能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。II .考试形式和试卷结构一、试卷满分及考试时间：本试卷满分为150分，考试时间为180分钟。二、答题方式：答题方式为闭卷、笔试。三、试卷内容结构数据结构45分计算机组成原理45分操作系统35分计算机网络25分四、试卷题型结构单项选择题80分（40小题，每小题2分）综合应用题70分III .考查内容数据结构考查目标1 .掌握数据结构的基本概念、基本原理和基本方法。2 .掌握数据的逻辑结构、存储结构及基本操作的实现,能够对算法进行基本的时间复杂度与空间复杂度的分析。3 .能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C或C+或Java语言设计与实现算法的能力。一、线性表（一）线性表的定义和基本操作（二）线性表的实现1.顺序存储结构2.链式存储结构3.线性表的应用一、栈、队列和数组（一）栈和队列的基本概念（二）栈和队列的顺序存储结构（三）栈和队列的链式存储结构（四）栈和队列的应用（五）特殊矩阵的压缩存储三、树与二叉树（一）树的基本概念（二）二叉树1 .二叉树的定义及其主要特证2 .二叉树的顺序存储结构和链式存储结构3 .二叉树的遍历4 .线索二叉树的基本概念和构造（三）树、森林1.树的存储结构2.森林与二叉树的转换3.树和森林的遍历（四）树与二叉树的应用1 .二叉排序树2.平衡二叉树3.哈夫曼（Huffman）树和哈夫曼编码四、图（一）图的基本概念（二）图的存储及基本操作1.邻接矩阵法2.邻接表法（三）图的遍历1.深度优先搜索2.广度优先搜索（四）图的基本应用1.最小（代价）生成树2.最短路径3.拓扑排序4.关键路径五、查找（一）查找的基本概念（二）顺序查找法（三）折半查找法（四）B树及其基本操作、B树的基本概念+（五）散歹！I （Hash）表（六）查找算法的分析及应用六、排序（一）排序的基本概念（二）插入排序1.直接插入排序2.折半插入排序（三）起泡排序（bubble sort）（四）简单选择排序（五）希尔排序（shell sort）（六）快速排序（七）堆排序（八）二路归并排序（mergesort）（九）基数排序（十）外部排序（+-）各种排序算法的比较（十二）排序算法的应用重点章：绪论线性表栈和队列（数组）树图查找排序第1章绪论【复习要点】1 .数据结构相关的基本概念和术语2 .数据结构的三要素：逻辑结构、物理结构和数据运算3 .算法的时间复杂度和空间复杂度的分析与计算【考题分析】年份单选题/分综合题/分考查内容2009年002010年07分析给定程序段的时间复杂度2011年1题/2V分析给定程序段的时间复杂度；大题中分析所写算法的时间复杂度2012年1题/2V分析给定程序段的时间复杂度；大题中分析所写算法的时间复杂度2013年1题/2V分析给定程序段的时间复杂度；大题中分析所写算法的时间复杂度2014年1题/20分析给定程序段的时间复杂度2011年1 .设n是描述问题规模的非负整数，下面程序片段的时间复杂度是。x=2；while(x<n/2)x=2*x；A. O(log2n) B.0(n) C. O(nlog2n)D.0(n2)2012年1 .求整数n(n20)阶乘的算法如下，其时间复杂度是 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；否则，只返回0o要求：(1)描述算法的基本设计思想(2)描述算法的详细实现步骤(3)根据设计思想和实现步骤，采用程序设计语言描述算法(使用C或C+或TAVA«言实现)，关键之处请给出简要注释。2010年42.(13分)设将n(n,1)个整数存放到一维数组R中,试设计一个在时间和空间两方面尽可能有效的算法，将R中保有的序列循环左移P (0<P<n)个位置，即将R中的数据由(X0X1Xn-1)变换为(Xp Xp+1Xn-1 X0 X1Xp-1)要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用C或C+或TAVA博言表述算法，关键之处给出注释。(3)说明你所设计算法的时间复杂度和空间复杂度2011年42.(15分)一个长度为L (L21)的升序序列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)说明你所设计算法的时间复杂度和空间复杂度。2012年42.假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading”和“being”的存储映像如下图所示。str Istr2设strl和str2分别指向两个单词所在单链表的头结点，链表结点结构为，请设计一个时间上尽可能高效的算法，找出由strl和str2所指向两个链表共同后缀的起始位置（如图中字符i所在结点的位置p）。要求：1）给出算法的基本设计思想。2）根据设计思想，采用C或C+或JAVA-语言描述算法，关键之处给出注释。3）说明你所设计算法的时间复杂度。2013年n.(13分)已知一个整数序列4=(旬吗,，qT), Ja m = ap2= ci .=x 且7>/2(0< pk <n,<k< m),(0,5,5,3,5,7,5,5),侧5为主元素；又如4二 A中没有主元素。假设A中的个元素保存在一个一?的算法，找出A的主元素。若存在主元素，则输出该元(1)给出算法的基本设计思想。(2)根据设计思想，采用C或C+皿Java语言描述算充(3)说明你所设计算法的时间复杂度和空间复杂度。【答案解析】2009年42.K个节点(1)算法基本思想如下：从头至尾遍历单链表，并用指针P指向当前节点的前K个节点。当遍历到链表的最后一个节点时，指针P所指向的节点即为所查找的节点。(2)详细实现步骤：增加两个指针变量和一个整型变量，从链表头向后遍历，其中指针P1指向当前遍历的节点，指针P指向P1所指向节点的前K个节点，如果P1之前没有K个节点，那么P指向表头节点。用整型变量i表示当前遍历了多少节点，当i>k 时，指针p随着每次遍历，也向前移动一个节点。当遍历完成时，p或者指向表头就节点，或者指向链表中倒数第K个位置上的节点。(3)算法描述:int LocateElement(linklist list, int k)K个节点P LP=list;P1=list->link;while(P1)P1=P1->link;idF jif(i>k) p=p->next;如果 i>k,贝1J p 也往后移)if(p=list)return 0;说明链表没有k个结点else printf( u%dn u,p->data); return 1;)2010年42.循环左移p位解法一：(1)算法的基本设计思想：分三次倒置：先倒置前p个元素，再倒置后 np个元素，最后全部元素倒置。(2)详细程序void ReverseSeg(int R,int fromjnt 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 个元素；将后面的np个元素放到前面;再将临时数组中的元素回放到后面。借助辅助数组来实现(2)详细程序void ConverseLeft2(int R,int n,int p) int TMAX;int i;for(i=0;i<p;i+) Ti=Ri;for(i=p;i<n;i+) Ri-p=Ri;for(i=n-p;i<n;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;j<p;j+) int temp=R0;for(int i=1;i<n;i+) Ri<1=Ri;Rn-1=temp;(3)时间复杂度0(pXN);空间复杂度o(1)循环右移p位方法一：分三次倒置：先倒置前np个元素，再倒置后p个元素，最后全部元素倒置。方法二：另设一个临时数组，存放前面的np个元素； 将后面的p个元素放到前面； 再将临时数组中的元素回放到后面。方法三： 每次拿出最后一个元素，将元素向后平移一位； 再将拿出的元素放入最前一个位置，重复p次。2011年42.(1)算法的基本设计思路如下：分别求两个升序序列A、B的中位数，设为 a和b。求序列A、B的中位数的过程如下:1)若2=则a或b即为所求的中位数;2）若a<b,则舍弃序列A中较小的一半，同时舍弃序列B中较大的一半,要求两次舍弃的元素个数相同。3）若a>b,则舍弃序列A中较大的一半，同时舍弃序列B中较小的一半,要求两次舍弃的元素个数相同。在保留的两个升序序列中，重复上述过程，直到两个序列中均只含一个元素时为止，则较小者即为所求的中位数。若ab,则肯定不在S1的左半边，因为如果在S1的左半边则中位数<ab,即也在S2的左半边，在整个S1+S2中也是在左半边,不是在中点，与中位数矛盾；同理不在s2的右半边若a>b时，原理同上当S1长度为奇数时，左半边=右半边，直接舍弃即可当S1长度为偶数时，左半边+1=右半边。若a<b,舍弃a的左半边（包括中点）舍弃b的右半边（保留中点）始终保持SI, S2等长int get_middle_number（int a, int b, int n）int startl =0, end1= n-1, ml;/分别表示序列A的首位数、末尾数和中位数的位置int start2=0, end2= n-1, m2;/分别表示序列A的首位数、末尾数和中位数的位置while (startl != end1| st art 2!= end2)(ml =(startl + end1)/2;m2=(start2+ end2)/2;if (am1= bm2)/a=breturn am1;if (am1<bm2)/a<bif (startl +end1)%2=0)若元素个数为奇数startl = ml;舍弃A中间点以前的部分且保留中间点end2= m2;舍弃B中间点以后的部分且保留中间点 else 若元素个数为偶数startl = ml +1;舍弃A中间点及中间点以前的部分end2= m2;舍弃B中间点以后的部分且保留中间点 else /a>bif (start1+end1)%2=0)end1= ml;start 2= m2; else end1= ml;start 2= m2+1;)return astart1< bstart2? astart1: bstart2;2012年42.公共后缀【解析】（1）算法思想：顺序遍历两个链表到尾结点时，并不能保证两个链表同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另一个链表长k个结点，我们先在长链表上遍历k个结点，之后同步遍历两个链表。这样我们就能够保证它们同时到达最后一个结点了。由于两个链表从第一个公共结点到链表的尾结点都是重合的。所以它们肯定同时到达第一个公共结点。于是得到算法思路：遍历两个链表求的它们的长度L1, L2；比较L1, L2,找出较长的链表，并求 L=|L1-L2|；先遍历长链表的L个结点；同步遍历两个链表，直至找到相同结点或链表结束。typedef struct Nodechar data;struct Node *next;SNode;/*求链表长度的函数7int listlen(SNode *head)int len=0;while(head->next!=NULL)len+;head=head->next;return len;/*找出共同后缀的起始地址7SNode* find_addr(SNode *strl5SNode*str2)int m,n;SNode *p,*q;m=listlen (strl);求 strl 的长度n=listlen (str2);求 str2的长度for (p=str1;m>n;m«)若 m>n,使 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分)算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素M/机。然后重新计数，确认N机是否是主元素。算法可分为以下两步：选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数机保存至肥中，记录N机的出现次数为1；若遇到的下一个整数仍等于N机，则计数加1,否则计数减1；当计数减到0时，将遇到的下一个整数保存到c中，计数重新记为L开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。判断c中元素是否是真正的主元素：再次扫描该数组，统计。中元素出现的次数，若大于n/2,则为主元素；否则，序列中不存在主元素。(2)算法实现：(7分)int Majority(int A, int n)|int i, c, count=l;/c用来保存候选主元素，count用来计数c = A0;/设置A0为候选主元素for (i=l; i<n; i+)/查找候选主元素if(Ai= c)count+;/对A中的候选主元素计数elseif ( count >0)/处理不是候选主元素的情况count-;else/更换候选主元素，重新计数 c = Ai;count =1;if (count>0)for (i=count=0; i<n; i+)/统计候选主元素的实际出现次数if(Ai= c)count+;if ( count> n/2) return c;/确认候选主元素else return -1;/不存在主兀素(1)、(2)的评分说明】若考生设计的算法满足题目的功能要求且正确，则(1)、(2)根据所实现算法的效率给分，细则见下表:时间复杂度0( n)0( n)空间复杂度0( 1)0( n)(1)得分 (2)得$47460( nlogln)其他362。(2)其他35int 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<n; k+) p Ak+;/计数器+1if (pAk> p max ) max =Ak;/记录出现次数最多的元素)if ( p max > n/2) return max;else return -1;)若在算法的基本设计思想描述中因文字表达没有非常清晰反映出算法思路，但在算法实现中能够清晰看出算法思想且正确的，可参照的标准给分。若算法的基本设计思想描述或算法实现中部分正确，可参照中各种情况的相应给分标准酌情给分。参考答案中只给出了使用C语言的版本,使用C+或Java语言的答案视同使用C语>*己。(3)说明算法复杂性：(2分)参考答案中实现的程序的时间复杂度为。()，空间复杂度为O (1) o【评分说明】若考生所估计的时间复杂度与空间复杂度与考生所实现的算法一致，可各给1分。时间复杂度为线性0(n),基于分治法的线性时间求主元素算法。算法的基本设计思想：中位数：数列排序后位于最中间的那个数。如果一个数列有主元素，那么必然是其中位数。求一个数列有没有主元素，只要看中位数是不是主元素。找中位数的方法:选择一个元素作为划分起点，然后用快速排序的方法将小于它的移动到左边，大于它的移动到右边。这样就将元素划分为两个部分。此时，划分元素所在位置为ko如果k>n/2,那么继续用同样的方法在左边部分找；如果kvn/2,就在右边部分找；k=n/2就找到了中位元素。根据快速排序的思想，可以在平均时间复杂度为0(n)的时间内找出一个数列的中位数。然后再用0(n)的时间检查它是否是主元素。C语言源码如下：int partition(int a,int lowjnt high)int pivotkey = alow;while(low<high)if(low<high && ahigh>=pivotkey)high;if(low<high) alow=ahigh; low+;if(low<high && alow<=pivotkey)+low;if(low<high) ahigh=alow;-high;alow=pivotkey;return low;快排int quick_sort(int a,int lowjnt high) if(low<high)int position = partition(a,low,high); if(position>n/2)quick_sort(a,low,position-1);else if(position<n/2)quick_sort(a,position+1,high);elsemid=aposition;找至!j 中位数int main()int a100;printf(”请输入个数nnM);scanf(M%dM,&n);for(int i=1;i<=n;i+)ai=O;初始化for(int i=1;i<=n;i+)scanf(,%d,5&ai);mid=quick_sort(a,1,n);int count=0;for(int i=1;iv=n;i+)中位数个数if(ai= mid)count+;if(count > n /2)printf(“有主元素为%d出现了%d 次n”,mid,count);elseprintf。无主元素n")； system(MpauseM);下面来看看如果无序，不能比较大小的算法，具体思想就是“在一个集合中，删除两个不同的数，则集合的主元素保持不变。”根据这个原理，可以很快求出主元素。只有最后剩下的元素才可能是主元素。#include <stdio.h>int getMainElement(int a,int len)int i,mainElement,repeatTimes =0;每次若不相同则减小这个计数，若相同则增加for(i =0;i<len;i+)if(repeatTimes =0) mainElement = ai; repeatTimes =1;else(if(mainElement = ai) repeatTimes+;else repeatTimes"return mainElement;int main()while(1)int len,i,mainElement,flagCount =0; scanf(M%dM,&len);int *a = new intlen;for(i =0;i<len;i+) scanf(M%d'&ai);mainElement=getMainElement(a,len);for(i = O;i<len;i+) if(mainElement = ai) flagCount+;if(flagCount>len/2)printff,%dnM5mainElement);elseprintf(MNonenM);return 0;