《数据结构考研知识点总结-》由会员分享，可在线阅读，更多相关《数据结构考研知识点总结-（33页珍藏版）》请在金锄头文库上搜索。
1、数据结构考研真题及知识点解析考察目标1. 理解数据结构的基本概念、基本原理和基本方法。2. 掌握数据的逻辑结构、 存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。3. 能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C、C+或Java语言设计与实现算法的能力。第2章线性表一、考研知识点(一) 线性表的定义和基本操作(二) 线性表的实现1. 顺序存储2. 链式存储3. 线性表的应用二、考研真题(一) 选择题近两年第2章没有考选择题，因为此章主要是线性表的操作，而且又是这门课的一个基础，考综合题的可能性比较大，而且可以和第3章、第9章和第10章的内容结合来
2、出题。1. (11年)设n是描述问题规模的非负整数，下面程序片段的时间复杂度是()。x=2;while(xk时，指针p随着每次遍历，也向前移动一个结点。当遍历完成时，p或者指向表头结点，或者指向链表中倒数第k个位置上的结点。(3) 算法描述：int locate(Li nklist list, i nt k)p1=list-li nk;p=list;i=1;while(pl)p1=p1-li nk;i+;if(ik)p=p-next; /如果 ik，贝U p 也后移if(p=list)return 0;/链表没有 k 个结点elseprintf(“ n” ,p-data);return 1;2
3、. ( 10年)设将n(n,1)个整数存放到一维数组R中，试设计一个在时间和空间两方面尽可能有效的算法，将R中保有的序列循环左移 P ( 0 P n)个位置，即将 R中的数据由(XO X1Xn-1 )变换为(Xp Xp+1Xn -1 X0 X1Xp-1 )要求:(1) 给出算法的基本设计思想。(2) 根据设计思想，采用 C或C+或 JAVA语言表述算法，关键之处给出注释。(3) 说明你所设计算法的时间复杂度和空间复杂度分析：此题考查的是数组的操作，线性表的顺序存储的核心就是数组，因此此题实质上是考查的线性表的顺序存储的操作及其应用。做此题时要考虑算法的时间和空间复杂度。解法一：(1) 算法的基
4、本设计思想： 可以将这个问题看做是把数组 ab转化成数组ba( a代表数 组的前p个元素，b代表数组中余下的 n-p个元素)，先将a逆置得到a-1 b，再将b逆置得 到a1 b，最后将整个ab1逆置得到(a b1) 一1 =ba。设reverse函数执行将数组元素逆置的操作，对abcdefgh向左循环移动3 (p=3)个位置的过程如下: reverse(0,p-1)得至Ucbadefgh；reverse(p,n-1)得至Ucbahgfde;reverse(0,n-1)得至Udefghabc。注：reverse中，两个参数分别表示数组中待转换元素的始末位置。(2) 算法描述:void rever
5、se(i nt R, int low, int high)/将数组中从low到high的元素逆置int temp;for(i=0;i=1 )的生序列S,处在第rL/2个位置的数称为 S的中位 数，例如，若序列 S仁(11,13,15,17,19),贝U S1的中位数是15,两个序列的中位数是含它 们所有元素的升序序列的中位数。例如，若S2= (2,4,6,8,20),则S1和S2的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间方面都尽可能高效的算法，找出两个序列A和B的中位数。要求：(1) 给出算法的基本设计思想。(2) 根据设计思想，采用 C或C+或JAVA语言描述算法，
6、关键之处给出注释。解答：此题考查线性表的顺序存储，主要是线性表的基本操作的应用。做此题时要把握算法的效率。(1) 算法的基本设计思想如下：分别求出序列 A和B的中位数，设为 a和b,求序列A和B的中位数过程如下：1) 若a=b,则a或b即为所求中位数，算法结束；2) 若ab,则舍弃序列 A中较大的一半，同时舍弃序列B中较小的一半，要求舍弃的 长度相等；在保留的两个升序序列中，重复过程1) -3 ),直到两个序列中只含一个元素时为止，较小者即为所求的中位数。(2) 算法实现如下：int M_search(i nt A,i nt B.i nt n)in t s1= 0,d1= n-1,m1,s2=
7、0,d2=n-1,m2;/分别表示序列 A和B的首位数、末尾数和中位数While(s1!=d1|s2!=d2)m1= (s1+d1)/2;m2=(s2+d2)/2;if(Am1=Bm2) return Am1;else if(Am1Bm2)if(s1+d1)%2=0s1=m1;d2=m2;elses 仁 m1+1;d2=m2;elseif(s1+d1)%2=0d1=m1;s2=m2;elsed 仁 m1+1;s2=m2;return As10)。A.表元素B .字符 C.数据元素D .数据项E.信息项4. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用(A)存
8、储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D .单循环链表5 .某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素， 则采用(D )存储方式最节省运算时间。A.单链表B .仅有头指针的单循环链表C.双链表D .仅有尾指针的单循环链表6. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的 时间复杂度为(C ) (1=i=n+1)。A. O(0) B. O(1)C. O( n)D. O(n2)7. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为(C )。A. O(n) 0(n)B. O(n) 0(1) C. O(1) O
9、(n) D. O(1) O(1)&线性表(a1,a2,an )以链接方式存储时，访问第i位置元素的时间复杂性为(C )。A. O (i) B . O (1) C . O (n) D . O (i-1)(二) 综合题1掌握线性表中几个最基本的操作算法(1 )逆置操作顺序表的就地逆置void reverse(SqList &A)for(i=1,j=A.le ngth;ij;i+,j-)A. elemiA.elemj; /元素交换链表的就地逆置void Lin kList_reverse(L in klist &L)p=L-n ext; q=p-n ext;while (q)r=q-n ext;q-n ext=p;p=q; q=r;L- next-next=NULL; /修改第一个元素的指针值L- next=p; /修改表头结点指针值(2)线性表的合并顺序表的合并：顺序存储的线性表la , lb的关键字为整数，元素非递减有序，线性表空间足够大，试编写高效算法，将lb中元素合并到la中，使新的la的元素仍非递减有序。分析：
