复习课_数据结构与算法ppt课件.ppt

《复习课_数据结构与算法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ForFinalTest数据结构与算法目录页第2页1234温习知识点和知识结构关于我们的考试一些训练答疑及其它知识结构知识结构第3页计算机世界的研究问题：建模+算法+实现数据结构的研究视角：（1）数据的逻辑结构和物理结构；（2）基于特定结构的通用操作描述。抽象数据类型：数据+数据间联系+数据上的操作集合大礼包大礼包第4页不属于考核范围的内容：Chapter2：2.5、2.6Chapter3：3.3Chapter6：6.2Chapter7：7.4、7.5、7.6Chapter9：9.5.2、9.6、9.7Chap

2、ter10内容温习Chapter1知识点第5页数据结构数据+关系：前驱、后继数据逻辑结构：（线性结构+非线性结构）线性、树型、集合、图数据存储结构顺序、链接、散列、索引算法及其分析输入+输出+步骤算法性能评价：时间复杂度+空间复杂度O()温故知新Chapter1测试一下第6页数据结构在计算机内存中的表示是（）A.数据的存储结构B.数据结构C.数据的逻辑结构D.数据元素之间的关系为规模n的问题设计了一个算法，其中最频繁操作的执行次数是n的函数：f(n)=3n3+100n2+9n+10000，则该算法的时间复杂度是

3、多少。内容温习Chapter2知识点第7页逻辑结构视角线性表：（直接）前驱、（直接）后继抽象数据类型：插入操作、删除操作物理结构视角顺序表数据元素存储地址的计算顺序存储的线性表，插入或删除一个元素，平均移动多少个元素？链接表（插入+删除）结点结构：数据域+指针域单链表双向链表循环链表问题分析1：链表中头结点的用途？判定带头结点的单链表是空表的条件？问题分析2：顺序表和链接表的优缺点对比温故知新Chapter2测试一下第8页请分析下面代码段的功能。typedefstructNode{Elemtypedata;St

4、ructNode*next;}Node;intcount(Node*list,ElemTypex){inti=0;Node*p=list;while(p!=NULL){if(p->data==x)i++;p=p->next;}returni;}温故知新Chapter2测试一下第9页2.请分别给出删除结点b和结点c的操作1.请分别给出删除结点c和插入结点x的操作温故知新Chapter2测试一下第10页P16816list1和list2分别是两个带有头结点的有序（升序）单向链表的头指针，请写出将两个有序链表合并为一

5、个有序链表（升序）的算法。（要求在原表基础上合并）温故知新Chapter2测试一下第11页P16816//升序合并为升序PListmergeList(PListlist1,PListlist2){PListp1=list1,p2=list2,head=NULL,tail=NULL,temp;if(p1->valuevalue){head=p1;tail=p1;p1=p1->next;tail->next=NULL;}else{head=p2;tail=p2;p2=p2->next;tail->next

6、=NULL;}while((p1!=NULL)&&(p2!=NULL)){if(p1->value>p2->value){temp=p2->next;tail->next=p2;tail=p2;tail->next=NULL;p2=temp;}else{temp=p1->next;tail->next=p1;tail=p1;tail->next=NULL;p1=temp;}}if(p1!=NULL)tail->next=p1;if(p2!=NULL)tail->next=p2;returnhead;}请问升序转

7、降序如何实现？内容温习Chapter3知识点第12页字符串是一种线性表，可以采用顺序存储结构和链式存储结构。其与普通线性表的区别在于：表中的每个元素是一个字符。两个字符串相等的充要条件是：两个字符串的长度相等+两个字符串中对应位置上的字符相同内容温习Chapter4知识点第13页栈特点：FILO；栈顶、出栈、入栈；顺序栈和链栈；栈在递归中的作用；队列特点：FIFO；队头、队尾、出队列、入队列；队列的顺序存储实现和链接存储实现；循环队列：假溢出；队列满和空的条件；栈和队列的综合应用温故知新Chapter4测试一下

8、第14页若已知一个栈的入栈序列是1,2,3,…,n，其输出序列是p1,p2,p3,…,pn，若p1=n，则pi是（）A.1B.n-1C.n-i+1D.不确定温故知新Chapter4测试一下第15页下图描述的队列（1）如何在队列中进行删除操作；（2）如何插入current指向的结点。温故知新Chapter4测试一下第16页循环单链表，head和tail分别是头指针和尾指针。1.请给出该循