《c题库期末复习》ppt课件

《《c题库期末复习》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、期末复习第一章绪论数据结构的基本概念和术语数据、数据元素、数据项、数据对象、数据结构等基本概念数据结构的逻辑结构，存储结构及数据运算的含义及其相互关系数据结构的四种逻辑结构及四种常用的存储表示方法抽象数据类型的概念及其与数据结构的关系算法的描述和分析算法、算法的时间复杂度和空间复杂度的概念算法描述和算法分析的方法第二章线性表线性表的逻辑结构线性表的逻辑结构特征线性表上定义的基本运算，并能利用基本运算构造出较复杂的运算线性表的顺序存储结构顺序表的存储方式及它如何映射线性表中元素之间的逻辑关系顺序表的存储结构定义线性表基本运算在顺序表上的实现方法及其时间性能分析利用顺序表设计算

2、法解决应用问题设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。解题思路：在递增有序的顺序表中插入一个元素x，首先应查找待插入元素的位置。因顺序表元素递增有序，采用折半查找法比顺序查找效率要高。查到插入位置后，从此位置直到线性表尾依次向后移动一个元素位置，之后将元素x插入即可。假设顺序表va存放在数组A[]中（假设下标从1开始）。voidInsert（ElemTypeA[]，intsize,ElemTypex）。{low=1；high=num；//假设下标从1开始while（low<=high）∥对分查找元素x的插入位置。{mi

3、d=（low+high）/2；if（A[mid]==x）{low=mid+1；break；}elseif（A[mid]>x）high=mid-1；elselow=mid+1；}for（i=num；i>=low；i--）A[i+1]=A[i]；∥元素后移。A[i+1]=x；∥将元素x插入。}算法结束线性表的链式存储结构链表的存储方式及它如何映射线性表中元素之间的逻辑关系链表中头指针和头节点的使用单链表、双链表、循环链表在链接方式上的区别各种链表的存储结构定义线性表基本运算在链表上的实现方法及其时间性能分析循环链表上尾指针取代头指针的作用利用链表设计算法解决简单的应用问题已知线

4、性表中的元素以值递增有序排列，并以单链表（带头结点）作为存储结构，试写一算法删除表中所有值大于mink且小于maxk的元素。解题思路：首先找到最后一个元素值小于等于mink的结点位置（q）；再往后依次删除结点直到第一个值大于等于maxk结点为止。voiddelete(sqlist*la,intmink,intmark){sqlist*p,*q,;q=la;  p=la->next;while(p&&p->data<=mink)  {q=p;p=p->next;}while(p&&p->datanext;free(p);}q->next=p

5、;}写出单链表（带头结点）就地逆置算法。voidreverse(linklist*h){linklistp,q;p=h->next;h->next=NULL;while(p!=null){q=p;//q指向当前结点p=p->next;//p指向下一个结点q->next=h->next;//将*q插入到*h之后h->next=q;}}顺序表和链表的比较顺序表和链表的主要优缺点根据应用问题的时空要求，为线性表选择合理的存储结构第三章栈与队列栈的逻辑结构，存储结构及其相关算法栈的逻辑结构特点，栈与线性表的关系顺序栈和链栈的存储结构定义顺序栈和链栈上进栈、退栈等基本运算的实现方法栈

6、上的“上溢”和“下溢”的概念及其判别条件递归过程中栈的作用设计递归程序的原则和方法利用栈设计算法解决简单的应用问题假设以S和X分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S和X组成的序列表示（如SXSX）。（1）试指出判别给定序列是否合法的一般规则。（2）两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列？如能得到，请举列说明。（1）通常有两条规则。第一是给定序列中S的个数和X的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，S的个数要大于或等于X的个数。（2）可以得到相同的输出元素序列。例如，输入元素为A，B，C，则两个输入的合法序列ABC

7、和BAC均可得到输出元素序列ABC。对于合法序列ABC，我们使用本题约定的S×S×S×操作序列；对于合法序列BAC，我们使用SS××S×操作序列。试证明：若借助栈由输入序列1,2,…,n得到输出序列为P1,P2,…,Pn（它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：存在着ipj的情况，则说明要将pj压到pi之上，也就是在pj出栈之后pi才能出栈。这就说明，对于i