数据构造考研真题及知识点解析
考察目的
1. 理解数据构造基本概念、基本原理和基本办法。
2. 掌握数据逻辑构造、存储构造及基本操作实现，可以对算法进行基本时间复杂度与空间复杂度分析。
3. 可以运用数据构造基本原理和办法进行问题分析与求解，具备采用C、C++或Java语言设计与实现算法能力。
第2章 线性表
一、考研知识点
（一）线性表定义和基本操作
（二）线性表实现
1.顺序存储
数据结构与算法考研真题2.链式存储
3.线性表应用
二、考研真题
（一）选取题
近两年第2章没有考选取题，由于此章重要是线性表操作，并且又是这门课一种基本，考综合题也许性比较大，并且可以和第3章、第9章和第10章内容结合来出题。
1．（）设n是描述问题规模非负整数，下面程序片段时间复杂度是（  ）。
    x=2;
    while(x<n/2)  x=2*x;
A.O(logn)      B.O(n)      C.O(nlogn)      D.O(n2)
分析：答案是A，此题考查是算法时间复杂度计算。可以放在第二章，实际这内容贯穿每一章内容中算法度量。
（二）综合题
1.（）已知一种带有表头结点单链表结点构造为(data,link)，假设该链表只给出了头指针list。在不变化链表前提下，请设计一种尽量高效算法，查链表中倒数第k个位置上结点（k为正整数）。若查成功，算法输出该结点data值，并返回1；否则，只返回0。规定：
（1）描述算法基本设计思想；
（2）描述算法详细实现环节；
（3）依照设计思想和实现环节，采用程序设计语言描述算法（使用C或C++或JAVA语言实现），核心之处给出简要注释。                                                                                   
分析：此题考查线性表链式存储，重要是线性表基本操作应用。做此题时要把握算法效率。
（1）算法基本思想如下：从头到尾遍历单链表，并用指针p指向当前结点前k个结点。当遍
历到链表最后一种结点时，指针p所指向结点即为所查结点。
（2）详细实现环节：增长两个指针变量和一种整型变量，从链表头向后遍历，其中指针p1指向当前遍历结点，指针p指向p1所指向结点前k个结点，如果p1之前没有k个结点，那么p指向表头结点。用整型变量i表达当前遍历了多少结点，当i>k时，指针p随着每次遍历，也向前移动一种结点。当遍历完毕时，p或者指向表头结点，或者指向链表中倒数第k个位置上结点。
（3）算法描述：
int locate(Linklist list，int k)
{
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)return 0；    //链表没有k个结点
else
{
        printf(“%\n”,p->data);
        return 1;
}
}
2.（）设将n(n,1)个整数存储到一维数组R中，试设计一种在时间和空间两方面尽量有效算法，将R中保有序列循环左移P（0﹤P﹤n）个位置，即将R中数据由（X0 X1 ……Xn-1）变换为（Xp Xp+1 ……Xn-1  X0  X1 ……Xp-1）规定：
（1）给出算法基本设计思想。
（2）依照设计思想，采用C或C++或JAVA语言表述算法，核心之处给出注释。
（3）阐明你所设计算法时间复杂度和空间复杂度
分析：此题考查是数组操作，线性表顺序存储核心就是数组，因而此题实质上是考查线性表顺序存储操作及其应用。做此题时要考虑算法时间和空间复杂度。
解法一：
（1）算法基本设计思想：可以将这个问题看做是把数组ab转化成数组ba（a代表数组前p个元素，b代表数组中余下n-p个元素），先将a逆置得到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）算法描述：
void reverse(int R[]，int low，int high)
{//将数组中从low到high元素逆置
    int temp;
    for(i=0;i<=(high-low)/2;i++)
    {
        temp=R[low+i];
        R[l0ow+i]=R[high-i];
        R[high-i]=temp;
}
}
void converse(int R[]，int n，int p)
{
    reverse(R,0,p-1);
    reverse(R,p,n-1);
    reverse(R,0,n-1);
}
（3）上述算法中三个reverse函数时间复杂度分别是O(p/2)、O((n-p)/2)、O(n/2)，故所设计算法时间复杂度为O(n)，空间复杂度为O(1)。
解法二：
算法思想：创立大小为p辅助数组S，将R中前p个整数依次暂存在S中，同步将R中后n-p个整数左移，然后将S中暂存p个数依次放回到R中后续单元。
时间复杂度为O(n)，空间复杂度为O(p)。
3.（）一种长度为L（L>=1）生序列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语言描述算法，核心之处给出注释。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。