没有合适的资源?快使用搜索试试~ 我知道了~
数据结构考研知识点总结.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 187 浏览量
2021-10-10
19:41:00
上传
评论
收藏 793KB DOC 举报
温馨提示
试读
29页
数据结构考研知识点总结.doc
资源推荐
资源详情
资源评论
数据结构考研真题及知识点解析
考察目标
1.理解数据结构的基本概念、基本原理和基本方法。
2.掌握数据的逻辑结构、存储结构及基本操作的实现,能够对算法进行基本的时间复
杂度与空间复杂度的分析。
3.能够运用数据结构的基本原理和方法进行问题的分析与求解,具备采用 C、C++或
Java 语言设计与实现算法的能力。
第 2 章 线性表
一、考研知识点
〔一〕线性表的定义和基本操作
〔二〕线性表的实现
二、考研真题
〔一〕选择题
近两年第 2 章没有考选择题,因为此章主要是线性表的操作,而且又是这门课的一个
基础,考综合题的可能性比较大,而且可以和第 3 章、第 9 章和第 10 章的内容结合来出
题。
1.〔11 年〕设 n 是描述问题规模的非负整数,下面程序片段的时间复杂度是〔 〕。
x=2;
while(x<n/2) x=2*x;
A.O(logn) B.O(n) C.O(nlogn) D.O(n
2
)
分析:答案是 A,此题考查的是算法时间复杂度的计算。可以放在第二章,实际这内
容贯穿每一章内容中算法的度量。
〔二〕综合题
1.〔09 年〕已知一个带有表头结点的单链表结点结构为(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.〔10 年〕设将 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
-1
b,再将 b 逆
置得到 a
-1
b
-1
,最后将整个 a
-1
b
-1
逆置得到〔a
-1
b
-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.〔11 年〕一个长度为 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 语言描述算法,关键之处给出注释。
解答:此题考查线性表的顺序存储,主要是线性表的基本操作的应用。做此题时要把
握算法的效率。
〔1〕算法的基本设计思想如下:
分别求出序列 A 和 B 的中位数,设为 a 和 b,求序列 A 和 B 的中位数过程如下:
1〕假设 a=b,则 a 或 b 即为所求中位数,算法结束;
2〕假设 a<b,则舍弃序列 A 中较小的一半,同时舍弃序列 B 中较大的一半,要求舍
弃的长度相等;
3〕假设 a>b,则舍弃序列 A 中较大的一半,同时舍弃序列 B 中较小的一半,要求舍
弃的长度相等;
在保留的两个升序序列中,重复过程 1〕-3〕,直到两个序列中只含一个元素时为止,
较小者即为所求的中位数。
〔2〕算法实现如下:
int M_search(int A[],int B[].int n)
{
int s1=0,d1=n-1,m1,s2=0,d2=n-1,m2;
//分别表示序列 A 和 B 的首位数、末尾数和中位数
While(s1!=d1||s2!=d2)
{
m1=(s1+d1)/2;
m2=(s2+d2)/2;
if(A[m1]==B[m2]) return A[m1];
else if(A[m1<B[m2])
if(s1+d1)%2==0
{s1=m1;d2=m2;}
else{s1=m1+1;d2=m2;}
else
if(s1+d1)%2==0
{d1=m1;s2=m2;}
else{d1=m1+1;s2=m2;}
}
return A[s1]<B[s2]? A[s1]:B[s2];
}
〔3〕算法的时间复杂度为 O(logn),空间负责杂度为 O(1)。
三、考查重点
1.线性结构的特点;
2.线性表在顺序存储及链式存储方式下的基本操作及其应用;
3.线性表的顺序存储及链式存储情况下,其不同和优缺点比较,及其各自适用的场
合。单链表中设置头指针、循环链表中设置尾指针而不设置头指针的各自好处;
4.能分析所写算法的时间和空间复杂度。
分析:线性表一章在线性结构的学习乃至整个数据结构学科的学习中,其作用都是不
可低估的。线性表一章小的知识点比较少,一般会出一个综合题,并且容易和第三章、第
九章和第十章的内容结合来考,注意对基本知识的理解,能够利用书上的理论解决具体问
题。学习过程中要注意多积累,多看、多写一些相关算法。
四、练习题
〔一〕选择题
1.下述哪一条是顺序存储结构的优点?〔 A 〕
A.存储密度大 B.插入运算方便
C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示
2.下面关于线性表的表达中,错误的选项是哪一个?〔 B 〕
A.线性表采用顺序存储,必须占用一片连续的存储单元。
B.线性表采用顺序存储,便于进行插入和删除操作。
C.线性表采用链接存储,不必占用一片连续的存储单元。
D.线性表采用链接存储,便于插入和删除操作。
3.线性表是具有 n 个〔 C 〕的有限序列〔n>0〕。
A.表元素 B.字符 C.数据元素 D.数据项 E.信息项
4.假设某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除
运算,则利用〔 A 〕存储方式最节省时间。
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(n
2
)
7. 对于顺序存储的线性表,访问结点和增加、删除结点的时间复杂度为〔 C 〕。
A.O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)
8.线性表〔 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.length;i<j;i++,j--)
A.elem[i]<->A.elem[j]; //元素交换
}
链表的就地逆置
void LinkList_reverse(Linklist &L)
{
p=L->next; q=p->next;
while (q)
{
r=q->next;
q->next=p;
p=q; q=r;
}
L->next->next=NULL; //修改第一个元素的指针值
L->next=p; //修改表头结点指针值
}
〔2〕线性表的合并
顺序表的合并:顺序存储的线性表 la,lb 的关键字为整数,元素非递减有序,线性表
空间足够大,试编写高效算法,将 lb 中元素合并到 la 中,使新的 la 的元素仍非递减有序。
分析:从后往前插入,防止移动元素
void union (Sqlist la, Sqlist lb)
{
m=la.length; n=lb.length;
k=m+n; i=m; j=n; //循环指针赋值,从后往前比较
while (i>0&&j>0)
{
if (la.elem[i]>=lb.elem[j])
[k]=la.elem[i]; k--; i--;}
else
m[k]=lb.elem[j]; k--; j--; }
}
if(j>0) //判断 lb 是否为空
{ la.elem[k]=lb.elem[j]; k--; j--;}
la.length=m+n;
剩余28页未读,继续阅读
资源评论
学习使人快乐张
- 粉丝: 14
- 资源: 6万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功