数据结构基础复习09

《数据结构基础复习09》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构考研辅导–基础复习浙江大学计算机学院内容提纲考研概述1基础内容复习2线性表、堆栈、队列、数组A树与图B查找与排序C考研概述考察目标理解数据结构的基本概念：掌握数据结构的逻辑结构、存储结构及其差异，以及各种基本操作的实现。在掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。能够选择合适的数据结构和方法进行问题求解。考研概述考试形式整卷满分为150分，考试时间为180分钟数据结构占45分，估计用时45~50分钟单选题：40题2分/题，估计占10题20分左右，建议用时不超过2分钟/题综合题：70分，估计占2

2、题共20~25分，建议用时不超过10分钟/题考研概述复习计划基础理论复习例题详解题目范围：真题1套+模拟题9套+补充题模拟题第10套将用于最后一天模拟考试基础内容复习《数据结构（C语言版）》，严蔚敏、吴伟民，清华大学出版社线性表、堆栈、队列、数组树与图查找与排序6线性表、堆栈、队列、数组线性表定义：n个数据元素的有限序列基本操作：随机访问、插入、删除、前驱、后继、倒序等实现方式：顺序存储：数组aiai+1…………Loc(ai)Loc(ai+1)=Loc(ai)+llLoc(ai)=Loc(a1)+?(i-1)*l线性表实现方

3、式：顺序存储：数组线性表、堆栈、队列、数组是一种随机存取的存储结构，方便随机存取第i个数据元素插入、删除复杂度为O(n)，需要移动大量元素自测题在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是：访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)在第i个结点后插入一个新结点（1≤i≤n）删除第i个结点（1≤i≤n）将n个结点从小到大排序线性表、堆栈、队列、数组线性表、堆栈、队列、数组线性表实现方式：链式存储：链表线性链表存储地址数据域指针域1LiNULL7Qian1313Sun119Zhao7头指

4、针H=19HZhaoQianSunLi若p->data=ai则p->next->data=ai+1typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;有时附加头结点自测题线性表若采用链式存储结构时，要求内存中可用存储单元的地址:必须是连续的部分地址必须是连续的一定是不连续的连续或不连续都可以线性表、堆栈、队列、数组线性表、堆栈、队列、数组线性表实现方式：链式存储：链表线性链表插入、删除复杂度为O(1)，仅需修改指针而不需要移动元素是一种非

5、随机存取的存储结构，不方便随机存取第i个数据元素*静态链表（p.31-35）自测题下面的叙述不正确的是（）线性表在链式存储时，查找第i个元素的时间同i的值成正比线性表在链式存储时，查找第i个元素的时间同i的值无关线性表在顺序存储时，查找第i个元素的时间同i的值成正比线性表在顺序存储时，查找第i个元素的时间同i的值无关线性表、堆栈、队列、数组自测题在一个单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行：s->next=p;p->next=s;s->next=p->next;p->next=s;s->next

6、=p->next;p=s;p->next=s;s->next=p;线性表、堆栈、队列、数组ps自测题在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是：p=p->next;p->next=p->next->next;p->next=p;p=p->next->next;线性表、堆栈、队列、数组xp线性表、堆栈、队列、数组线性表实现方式：链式存储：链表循环链表双向链表HHHH有时设尾指针可简化某些操作，如两表合并。自测题设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用()最节省时间。单链表单循环链表

7、带尾指针的单循环链表带头结点的双循环链表线性表、堆栈、队列、数组自测题将线性表La和Lb头尾连接，要求时间复杂度为O(1)，且占用辅助空间尽量小。应该使用哪种结构？单链表单循环链表带尾指针的单循环链表带头结点的双循环链表线性表、堆栈、队列、数组tmp=La->next;La->next=Lb->next;Lb->next=tmp;LaLb线性表、堆栈、队列、数组线性表练习1：分别实现数组、单链表、循环链表、双向链表的插入和删除操作。练习2：实现单链表的原地逆转。练习3：分别用一元多项式的两种表示实现多项式加法。32-51-2

8、3000-1103200P19自测题给定2个带有表头结点的单链表的头指针L1和L2，结点结构为。假设这2个链表的结点已经按Data域递增有序，请设计算法把它们合并成一个按Data域递增有序的链表。注意：算法不能使用额外的结点空间。线性表、堆栈、队列、数组DataNext算法思路为顺序比较