欢迎来到天天文库
浏览记录
ID:35960084
大小:795.00 KB
页数:28页
时间:2019-04-28
《数据结构考研知识点总结-(30008)》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、--WORD格式--专业资料--可编辑---数据结构考研真题及知识点解析考察目标1. 理解数据结构的基本概念、基本原理和基本方法。2. 掌握数据的逻辑结构、存储结构及基本操作的实现,能够对算法进行基本的时间复杂度与空间复杂度的分析。3. 能够运用数据结构的基本原理和方法进行问题的分析与求解,具备采用C、C++或Java语言设计与实现算法的能力。第2章线性表一、考研知识点(一)线性表的定义和基本操作(二)线性表的实现1.顺序存储2.链式存储3.线性表的应用二、考研真题(一)选择题近两年第2章没有考选择题,因为此章主
2、要是线性表的操作,而且又是这门课的一个基础,考综合题的可能性比较大,而且可以和第3章、第9章和第10章的内容结合来出题。1.(11年)设n是描述问题规模的非负整数,下面程序片段的时间复杂度是()。x=2;while(x3、表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data值,并返回1;否则,只返回0。要求:(1)描述算法的基本设计思想;(2)描述算法的详细实现步骤;(3)根据设计思想和实现步骤,采用程序设计语言描述算法(使用C或C++或JAVA语言实现),关键之处给出简要注释。分析:此题考查线性表的链式存储,主要是线性表的基本操作的应用。做此题时要把握算法的效率。(1)算法基本思想如下:从头到尾遍历单链表,并用指针p指向当4、前结点的前k个结点。当遍历到链表的最后一个结点时,指针p所指向的结点即为所查找的结点。(2)详细实现步骤:增加两个指针变量和一个整型变量,从链表头向后遍历,其中指针p1指向当前遍历的结点,指针p指向p1所指向结点的前k个结点,如果p1之前没有k个结点,那么p指向表头结点。用整型变量i表示当前遍历了多少结点,当i>k时,指针p随着每次遍历,也向前移动一个结点。当遍历完成时,p或者指向表头结点,或者指向链表中倒数第k个位置上的结点。(3)算法描述:----WORD格式--专业资料--可编辑---intlocate(L5、inklistlist,intk){p1=list->link;p=list;i=1;while(p1){p1=p1->link;i++;if(i>k)p=p->next;//如果i>k,则p也后移}if(p==list)return0;//链表没有k个结点else{printf(“%”,p->data);return1;}}2.(10年)设将n(n,1)个整数存放到一维数组R中,试设计一个在时间和空间两方面尽可能有效的算法,将R中保有的序列循环左移P(0﹤P﹤n)个位置,即将R中的数据由(X0X1……Xn-6、1)变换为(XpXp+1……Xn-1 X0 X1……Xp-1)要求:(1)给出算法的基本设计思想。(2)根据设计思想,采用C或C++或JAVA语言表述算法,关键之处给出注释。(3)说明你所设计算法的时间复杂度和空间复杂度分析:此题考查的是数组的操作,线性表的顺序存储的核心就是数组,因此此题实质上是考查的线性表的顺序存储的操作及其应用。做此题时要考虑算法的时间和空间复杂度。解法一:(1)算法的基本设计思想:可以将这个问题看做是把数组ab转化成数组ba(a代表数组的前p个元素,b代表数组中余下的n-p个元素),先将a7、逆置得到a-1b,再将b逆置得到a-1b-1,最后将整个a-1b-1逆置得到(a-1b-1)-1=ba。设reverse函数执行将数组元素逆置的操作,对abcdefgh向左循环移动3(p=3)个位置的过程如下:reverse(0,p-1)得到cbadefgh;reverse(p,n-1)得到cbahgfde;reverse(0,n-1)得到defghabc。注:reverse中,两个参数分别表示数组中待转换元素的始末位置。(2)算法描述:voidreverse(intR[],intlow,inthigh){//将8、数组中从low到high的元素逆置inttemp;for(i=0;i<=(high-low)/2;i++){temp=R[low+i];R[l0ow+i]=R[high-i];----WORD格式--专业资料--可编辑---R[high-i]=temp;}}voidconverse(intR[],intn,intp){reverse(R,0,p-1);reverse(R,
3、表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data值,并返回1;否则,只返回0。要求:(1)描述算法的基本设计思想;(2)描述算法的详细实现步骤;(3)根据设计思想和实现步骤,采用程序设计语言描述算法(使用C或C++或JAVA语言实现),关键之处给出简要注释。分析:此题考查线性表的链式存储,主要是线性表的基本操作的应用。做此题时要把握算法的效率。(1)算法基本思想如下:从头到尾遍历单链表,并用指针p指向当
4、前结点的前k个结点。当遍历到链表的最后一个结点时,指针p所指向的结点即为所查找的结点。(2)详细实现步骤:增加两个指针变量和一个整型变量,从链表头向后遍历,其中指针p1指向当前遍历的结点,指针p指向p1所指向结点的前k个结点,如果p1之前没有k个结点,那么p指向表头结点。用整型变量i表示当前遍历了多少结点,当i>k时,指针p随着每次遍历,也向前移动一个结点。当遍历完成时,p或者指向表头结点,或者指向链表中倒数第k个位置上的结点。(3)算法描述:----WORD格式--专业资料--可编辑---intlocate(L
5、inklistlist,intk){p1=list->link;p=list;i=1;while(p1){p1=p1->link;i++;if(i>k)p=p->next;//如果i>k,则p也后移}if(p==list)return0;//链表没有k个结点else{printf(“%”,p->data);return1;}}2.(10年)设将n(n,1)个整数存放到一维数组R中,试设计一个在时间和空间两方面尽可能有效的算法,将R中保有的序列循环左移P(0﹤P﹤n)个位置,即将R中的数据由(X0X1……Xn-
6、1)变换为(XpXp+1……Xn-1 X0 X1……Xp-1)要求:(1)给出算法的基本设计思想。(2)根据设计思想,采用C或C++或JAVA语言表述算法,关键之处给出注释。(3)说明你所设计算法的时间复杂度和空间复杂度分析:此题考查的是数组的操作,线性表的顺序存储的核心就是数组,因此此题实质上是考查的线性表的顺序存储的操作及其应用。做此题时要考虑算法的时间和空间复杂度。解法一:(1)算法的基本设计思想:可以将这个问题看做是把数组ab转化成数组ba(a代表数组的前p个元素,b代表数组中余下的n-p个元素),先将a
7、逆置得到a-1b,再将b逆置得到a-1b-1,最后将整个a-1b-1逆置得到(a-1b-1)-1=ba。设reverse函数执行将数组元素逆置的操作,对abcdefgh向左循环移动3(p=3)个位置的过程如下:reverse(0,p-1)得到cbadefgh;reverse(p,n-1)得到cbahgfde;reverse(0,n-1)得到defghabc。注:reverse中,两个参数分别表示数组中待转换元素的始末位置。(2)算法描述:voidreverse(intR[],intlow,inthigh){//将
8、数组中从low到high的元素逆置inttemp;for(i=0;i<=(high-low)/2;i++){temp=R[low+i];R[l0ow+i]=R[high-i];----WORD格式--专业资料--可编辑---R[high-i]=temp;}}voidconverse(intR[],intn,intp){reverse(R,0,p-1);reverse(R,
此文档下载收益归作者所有