考研数据结构辅导

全国硕士研究生入学统一考试

计算机科学与技术学科联考计算机学科专

业基础综合考试大纲I•考查目标计算机学科专业基础综合考试是为高等院校和科研院所招收计算机科学与技术学科的硕士研究生而设置的具有选拔性质的联考科目其目的是科学、公平、有效地测试考生掌握计算机科学与技术学科大学本科阶段专业基础知识、基本理论、基本方法的水平和分析问题、解决问题的能力，评价的标准是高等学校计算机科学与技术学科优秀本科生所能达到的及格或及格以上水平，以利于各高等院校和科研院所择优选拔，确保硕士研究生的入学质量。计算机学科专业基础综合考试涵盖数据机构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生系统地掌握上述专业基础课程的概念、基本原理和基本方法，能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。II•考试形式和试卷结构一、 试卷满分及考试时间：本试卷满分为150分，考试时间为180分钟。二、 答题方式：答题方式为闭卷、笔试。三、 试卷内容结构TOC\o"1-5"\h\z数据结构 45分 计算机组成原理 45分操作系统 35分 计算机网络 25分四、 试卷题型结构单项选择题 80分（40小题，每小题2分） 综合应用题 70分皿.考查内容数据结构［考查目标］•掌握数据结构的基本概念、基本原理和基本方法。•掌握数据的逻辑结构、存储结构及基本操作的实现，•能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C或C++或Java语言设计与实现算法的能力。一、线性表（一） 线性表的定义和基本操作（二） 线性表的实现 1顺序存储结构 2•链式存储结构 3•线性表的应用二、 栈、队列和数组（一） 栈和队列的基本概念（二） 栈和队列的顺序存储结构（三） 栈和队列的链式存储结构（四） 栈和队列的应用（五） 特殊矩阵的压缩存储三、 树与二叉树（一） 树的基本概念（二） 二叉树1二叉树的定义及其主要特证•二叉树的顺序存储结构和链式存储结构•二叉树的遍历（三）树、森林1树的存储结构 1树的存储结构 2・3•树和森林的遍历森林与二叉树的转换（四）树与二叉树的应用（四）树与二叉树的应用1二叉排序树 1二叉排序树 2・平衡二叉树 3•哈夫曼（Huffman）树和哈夫曼编码四、图（一） 图的基本概念（二） 图的存储及基本操作 1・邻接矩阵法2•邻接表法（三） 图的遍历 1深度优先搜索2•广度优先搜索（四） 图的基本应用 1・最小（代价）生成树2•最短路径 3•拓扑排序 4•关键路径五、查找（一） 查找的基本概念（二） 顺序查找法（三） 折半查找法（四） B树及其基本操作、B树的基本概念+（六）查找算法的分析及应用六、排序（一） 排序的基本概念（二） 插入排序 1直接插入排序 2•折半插入排序（三） 起泡排序（bubblesort）（四） 简单选择排序（五） 希尔排序（shellsort）（六） 快速排序（七） 堆排序（八） 二路归并排序（mergesort）（九） 基数排序（十）外部排序（十一）各种排序算法的比较（十二）排序算法的应用重点章：绪论线性表栈和队列（数组）树图查找排序第1章绪论【复习要点】数据结构相关的基本概念和术语数据结构的三要素：逻辑结构、物理结构和数据运算算法的时间复杂度和空间复杂度的分析与计算【考题分析】年份单选题份综合题/分考查内容2009年002010年0V分析给定程序段的时间复杂度2011年1题/2V分析给定程序段的时间复杂度；大题中分析所写算法的时间复杂度2012年1题/2V分析给定程序段的时间复杂度；大题中分析所写算法的时间复杂度2013年1题/2V分析给定程序段的时间复杂度；大题中分析所写算法的时间复杂度2014年1题/20分析给定程序段的时间复杂度年

1设n是描述问题规模的非负整数的时间复杂度是，下面程序片段x=2；while(xvn/2)x=2*x1设n是描述问题规模的非负整数的时间复杂度是，下面程序片段x=2；while(xvn/2)x=2*x；A.O(log2n) B.O(n)D.O(n2)年C.O(nlog2n)1求整数n(nMO)阶乘的算法如下，其时间复杂度intfact(intn){if(nv=1)return1;returnn*fact(n-1);}C.O(nlog2n)A.O(logC.O(nlog2n)D.O(n2)年1.已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是 。A.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分)已知一个带有表头结点的单链表，结点结构为=1假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，査找链表中倒数第k个位置上的结点(k为正整数)。若查找成功，算法输出该结点的data值，并返回1；否则，只返回=10。要求:(1)(1)描述算法的基本设计思想描述算法的详细实现步骤根据设计思想和实现步骤，采用程序设计语言(3)根据设计思想和实现步骤，采用程序设计语言描述算法(使用C或C++或JAVA语言实现)，关键之处请给出简要注释。年=142.(13分)设将n(n,1)个整数存放到一维数组R中，试设计一个在时间和空间两方面尽可能有效的算法，将R中保有的序列循环左移P(0<P<n)个位置，即将R中的数据由(X0X1……Xn-1)变换为(XpXp+1……Xn-1X0X1……Xp-1)要求：=1(1)给出算法的基本设计思想。(2)根据设计思想，采用C或C++或JAVA语言表述算法，关键之处给出注释。(3)说明你所设计算法的时间复杂度和空间复杂度年42.(15分)一个长度为L(LM1)的升序序列S,处在第 个位置的数称为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)说明你所设计算法的时间复杂度和空间复杂度。年42•假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading”和“being”的存储映像如下图所示。设strl和str2分别指向两个单词所在单链表的头结点，链表结点结构为 ，请设计一个时间上尽可能高效的算法，找出由strl和str2所指向两个链表共同后缀的起始位置（如图中字符i所在结点的位置p）。要求:1）给出算法的基本设计思想。2）根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释。3）说明你所设计算法的时间复杂度。年ap[=ap2=—=aptn=xUm>n/2(0<pk<n.\<k<m)?（0, 5，5，3,5，7，5,5）,侧5为主元素；又如A二A屮没有主元素。假设A屮的«个元素保存在•个一纟的算法，找出A的主元素。若存在主元素，则输出该元（Q给出算法的基本设计思想。（2） 根据设计思想，采川C或C++|^Java语言描述算辛（3） 说明你所设讣算法的时间复杂度和帘间复杂度。【答案解析】42.K个节点P1链表，并用指针P指向当前节点的前K个节点。当遍历到链表的最后一个节点时，指针P所指向的节点即为所査找的节点。(2)详细实现步骤：增加两个指针变量和一个整型变量，从链表头向后遍历，其中指针P1指向当前遍历的节点,指针P(2)详细实现步骤：增加两个指针变量和一个整型变量，从链表头向后遍历，其中指针P1指向当前遍历的节点,指针P指向P1所指向节点的前K个节点，如果P1之前没有K个节点，那么P指向表头节点。用整型变量i表示当前遍历了多少节点，当i>k时，指针p随着每次遍历，也向前移动一个节点。当遍历完成时，p或者指向表头就节点，或者指向链表中倒数第K个位置上的节点。ijiiJIJJJJ=1■I■■■■

IWijiiJ(3)算法描述:K个节点K个节点listP=list;P一listi=1；while(P1){P1=P1->link;i++；if(i〉k)p二p-〉next如果/i>k则p也往后移}if(p==list)return0;说朋链表没有k个结点else{print“(％d\n“，p-〉data);return1;}}2010年42.循环左移p位解法―：(1)算法的基本设计思想:分三次倒置：先倒置前P个元素，再倒置后n-p个元素，最后全部元素倒置。(2)详细程序voidReverseSeg(intR[],intfrom,intto){for(inti=0;iv(to-from+1)/2;i++){inttemp;temp=R[from+i];R[from+i]=R[to-i]; R[to-i]=temp;}}voidConverseLeft(intR[],intn,intp){ReverseSeg(R,0,p-1);ReverseSeg(R,p,n-1);ReverseSeg(R,0,n-1);}(3)时间复杂度O(N);空间复杂度o(p)解法二：算法的基本设计思想：另设一个临时数组，存放前面的p个元素；将后面的n-p个元素放到前面;再将临时数组中的元素回放到后面。借助辅助数组来实现⑵详细程序voidConverseLeft2(intR[],intn,intp){intT[MAX];inti;for(i=0;ivp;i++)T[i]=R[i];for(i=p;ivn;i++)R[i-p]=R[i];for(i=n-p;ivn;i++)R[i]=T[i-p-n];}(3)时间复杂度O(N);空间复杂度o(p)解法三：(1)算法的基本设计思想：每次拿出最前一个元素，将元素向前平移一位；再将拿出的元素放入最后一个位置，重复p次。详细程序voidConverseLeft3(intR[],intn,intp){for(intj=0；jvp；j++)inttemp=R[0];for(inti=1;ivn;i++)R[i-1]=R[i];R[n-1]=temp;}时间复杂度O(pXN);空间复杂度o(1)循环右移p位方法一：l¥l分三次倒置：先倒置前n-p个元素，再倒置后p个元素，最后全部元素倒置。l¥l方法二另设一个临时数组，存放前面的n-p个将后面的p个元素放到前面；再将临时数组中的元素回放到后面。方法三：①每次拿出最后一个元素，将元素向后平移一位；②再将拿出的元素放入最前一个位置，重复p次。年42.(1)算法的基本设计思路如下：分别求两个升序序列A、B的中位数，设为a和bo求序列A、B的中位数的过程如下:若a=b,则a或b即为所求的中位数;2）若avb，则舍弃序列A中较小的一半，同时舍弃序列B中较大的一半，要求两次舍弃的元素个数相同。3）若a>b，则舍弃序列A中较大的一半，同时舍弃序列B中较小的一半，要求两次舍弃的元素个数相同。在保留的两个升序序列中，重复上述过程,直到两个序列中均只含一个元素时为止，则较小者即为所求的中位数。若a<b，则肯定不在S1的左半边，因为如果在S1的左半边则中位数<a<b,即也在S2的左半边，在整个S1+S2中也是在左半边,不是在中点，与中位数矛盾;同理不在s2的右半边若a>b时，原理同上当S1长度为奇数时，左半边二右半边，直接舍弃即可当S1长度为偶数时，左半边+1=右半边。若a<b，舍弃a的左半边（包括中点）舍弃b的右半边（保留中点）始终保持S1,S2等长intget_middle_number（inta[],intb[],intn）intstartl=0,endl=n-1,ml;//分别表示序列A的首位数、末尾数和中位数的位置intstart2=0,end2=n-1,m2;//分别表示序列A的首位数、末尾数和中位数的位置while(startl!=endl||start2!=end2){m1=(start1+end1)/2;m2=(start2+end2)/2;if(a[m1]==b[m2]) //a=breturna[m1];if(a[m1]<b[m2]){ //avbif((start1+end1)%2==0){〃若元素个数为奇数start1=m1; 〃舍弃A中间点以前的部分且保留中间点end2=m2; 〃舍弃B中间点以后的部分且保留中间点〃若元}else{〃若元素个数为偶数startl=ml+1; 〃舍弃A中间点及中间点以前的部分〃舍弃end2=m2;〃舍弃B中间点以后的部分且保留中间点}}else{ //a>bif((start1+end1)%2==0){endl=ml;start2=m2;}else{endl=ml;start2=m2+1;}}}returna[start1]<b[start2]?a[start1]:b[start2];}年42.公共后缀【解析］（1）算法思想：顺序遍历两个链表到尾结点时，并不能保证两个链表同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另一个链表长k个结点，我们先在长链表上遍历k个结点，之后同步遍历两个链表。这样我们就能够保证它们同时到达最后一个结点了。由于两个链表从第一个公共结点到链表的尾结点都是重合的。所以它们肯定同时到达第一个公共结点。于是得到算法思路：①遍历两个链表求的它们的长度L1,L2；②比较L1,L2,找出较长的链表，并求L=|L1-L2|；先遍历长链表的L个结点;同步遍历两个链表，直至找到相同结点或链表结束。typedefstructNode{chardata;structNode*next;}SNode;/*求链表长度的函数*/intlistlen(SNode*head){intlen=0;whlle(head->next!=NULL){len++;head=head->next;}returnlen;}/*找出共同后缀的起始地址*/SNode*find_addr(SNode*strl,SNode*str2){intm,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;}//whilereturnp->next;//返回共同后缀的起始地址}年42.“在一个集合中，删除两个不同的数，则集合的主元素保持不变。”（1）给出算法的基本设计思想：（4分）算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num。然后重新计数，确认Num是否是主元素。算法可分为以下两步：选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数Num保存到c中，记录Num的出现次数为1；若遇到的下一个整数仍等于Num,则计数加1,否则计数减1；当计数减到0时，将遇到的下一个整数保存到c中，计数重新记为1,开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。判断c中元素是否是真正的主元素：再次扫描该数组，统计c中元素出现的次数，若大于n/2,则为主元素；否则，序列中不存在主元素。2）算法实现：（7分）intMajority(intA[],intn){inti,c,count=1; //c用来保存候选主元素，count用来计数c=A[0];候选主元素for(i=1;i<n;i++)素//设置A[0]为//查找候选主元if(A[i]==c)

count++;主元素计数elseif(count>0)主元素的情况count--;else素，重新计数//对A中的候选//处理不是候选//更换候选主元{c=A[i];count=1;if(count>0)for(i=count=0;i<n;i++)//统计候选主元素的实际出现次数if(A[i]==c)count++;if(count>n/2)returnc; //确认候选主元素elsereturn-1; //不存在主元素}【(1)、(2)的评分说明】①若考生设计的算法满足题目的功能要求且正确，则(1)、(2)根据所实现算法的效率给分，细则见下表：时间复杂度O(n)O(n)空间复杂度O(1)O(n)(1)得分44(2)得分76O(nlog2n)其他36MO(n2)其他35intMajority1(intA[],intn)//采用计数排序思想，时间：O(n),空间：0(n)intk,*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[A[k]]++;//计数器+1if(p[A[k]]>p[max])max=A[k];//记录出现次数最多的元素}if(p[max]>n/2)returnmax;elsereturn-1;}②若在算法的基本设计思想描述中因文字表达没有非常清晰反映出算法思路，但在算法实现中能够清晰看出算法思想且正确的，可参照①的标准给分。若算法的基本设计思想描述或算法实现中部分正确，可参照①中各种情况的相应给分标准酌情给分。参考答案中只给出了使用C语言的版本,使用C++或Java语言的答案视同使用C语(3)说明算法复杂性：(2分)参考答案中实现的程序的时间复杂度为O(“)，空间复杂度为O(1)。【评分说明】若考生所估计的时间复杂度与空间复杂度与考生所实现的算法一致，可各给1分。时间复杂度为线性0(n)基于分治法的线性时间求主元素算法。算法的基本设计思想：中位数：数列排序后位于最中间的那个数。如果一个数列有主元素，那么必然是其中位数。求一个数列有没有主元素，只要看中位数是不是主元素。找中位数的方法:选择一个元素作为划分起点，然后用快速排序的方法将小于它的移动到左边，大于它的移动到右边。这样就将元素划分为两个部分。此时，划分元素所在位置为k。如果k>n/2,那么继续用同样的方法在左边部分找；如果kvn/2，就在右边部分找；k=n/2就找到了中位元素。根据快速排序的思想，可以在平均时间复杂度为0(n)的时间内找出一个数列的中位数。然后再用0(n)的时间检查它是否是主元素。C语言源码如下:intpartition(inta[],intlow,inthigh){intpivotkey=a[low];while(lowvhigh){if(lowvhigh&&a[high]>=pivotkey)-high;if(low<high){a[low]=a[high];low++;}if(low<high&&a[low]<=pivotkey)++low;if(low<high){a[high]=a[low];--high;}}a[low]=pivotkey;returnlow;}//快排intquick_sort(inta[],intlow,inthigh){if(low<high){intposition=partition(a,low,high);if(position>n/2)quick_sort(a,low,po