数据结构复习要点.doc

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

1、.A—熟练掌握B—理解C—了解第一章：绪论1.基本概念：包括数据的逻辑结构、数据的存储结构和数据的相关运算。C四类数据组织结构：集合、线性表、树形、图状结构C数据的存储方式：顺序存储和链式存储。B2.算法和分析算法的特征、时间复杂度的分析和常见的时间复杂度增长率排序、空间复杂度B本章重点：分析算法时间复杂度例1.下面关于算法说法错误的是（）A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上几个都是错误的D例2.以下那一个术语与数据的存储结构无关？

2、（）A．栈B.哈希表C.线索树D.双向链表A．例3.．求下段程序的时间复杂度：voidmergesort(inti,intj){intm;if(i!=j){m=(i+j)/2;mergesort(i,m);mergesort(m+1,j);merge(i,j,m);}}其中mergesort()用于对数组a[n]归并排序，调用方式为mergesort(0,n-1);，merge()用于两个有序子序列的合并，是非递归函数，时间复杂度为。解：分析得到的时间复杂度的递归关系：为merge（）所需的时间，设为cn（c为常量）。因此令

3、，有有..第二章：线性表1.线性表的基本运算：…..C2.线性表的顺序存储（利用静态数组或动态内存分配）。　相应的表示与操作A3.线性表的链式存储。相应的表示与操作。包括循环链表、双向链表。A4.顺序存储与链式存储的比较：基于时间的考虑--分别适用于静态的和动态的操作：比如静态查找和插入删除）；基于空间的考虑--…….B这也适用于后面用两种方式存储的其他数据结构。★本章重点：很熟悉顺序表，单链表、双链表，循环链表的基本操作；并学会在各种链表上进行一些算法设计（与基本操作类似的操作或组合），请仔细复习。例4．假设有两个按元素值

4、递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。[题目分析]因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比较，将小的链入链表中，同时后移链表工作指针。该问题要求结果链表按元素值递减次序排列。故在合并的同时，将链表结点逆置。voidUnion(LinkListla,LinkListlb) ∥la,lb分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列，本算法将两链表合并成一个按元素值递减

5、次序排列的单链表。 {pa=la->next;pb=lb->next;∥pa，pb分别是链表la和lb的工作指针   la->next=null;          ∥la作结果链表的头指针，先将结果链表初始化为空。   while(pa!=null&&pb!=null)∥当两链表未访问结束     if(pa->data<=pb->data)       {q=pa->next;          ∥将pa的后继结点暂存于q。         pa->next=la->next;   ∥将pa结点链于结果表中，同时逆置。l

6、a->next=pa;pa=q;                ∥恢复pa为当前待比较结点。}     else{q=pb->next;∥将pb的后继结点暂存于q。pb->next=la->next;∥将pb结点链于结果表中，同时逆置。la->next=pb;pb=q;∥恢复pb为当前待比较结点。}     while(pa!=null)∥将la表的剩余部分链入结果表，并逆置。          {q=pa->next;pa->next=la->next;la->next=pa;pa=q;}       while(pb!=

7、null)          {q=pb->next;pb->next=la->next;la->next=pb;pb=q;}}∥算法Union结束。注意：（1）此处q用作暂存后继结点，操作后pa或pb还回原指向位置；这与我们原来不改变pa或pb的指向，增加一个q=pa或pb作为摘取结点进行添加操作起到的作用一样。（2）此处要完成逆序插入操作故用头插法（基于头指针la或lb），注意尾插法（附设一个尾指针，基于该指针插入）的可完成顺序插入。（注意：逆序另一种方式也要掌握！）..练习：练习题2编程1——67.判断带头结点双向循环

8、链表L是否对称相等.8.设计一个算法判断单链表（带头结点）是否是递增的（注意比排序算法应该简单，链表排序也要会实现）9.设计一个算法判断有序表A是否是有序表B的子集（即表A中的元素在B中）。（思考：如果递归程序怎么写？）第三章：栈与队列1.两种特殊线性表：分别有后进先出、先进先出的特性。B