《数据结构与算法分析期末复习ppt》由会员分享，可在线阅读，更多相关《数据结构与算法分析期末复习ppt（64页珍藏版）》请在金锄头文库上搜索。
1、一命数据结松“复习指导2010.6“本课程为闭卷考试“考试时间为120分钟。“考试题型为:“选择题(20分)“填空题C20分*判断题(10分)*应用题(20分(选做*算法题(20分(选做“附加题一、各章节主要知识点讲解二、对相关知识点的要求和举例三、习题选讲匹一人初1.数据结构的基本概念“数据结构:是相互之间存在一种或多种特定关系的数据元素的集合,数据元素间的关系称为结构“逻辑结构:数据元素间的巡辑(抽豪7关系,与计算机无关,同一种逻辑结构可以有不同的存储结构(物理结构例:链式顺序)“物理结构:数据的逻辑结构在计算机中的表示(数据元素的表示和关系的表示江“4种基本的逻辑结构:集合线性(一对一)
2、树形(一对多图形(多对多“4种基本的物理结构:顺序结构链式结构散列结构索引结构*习题集P21.8(1,2,3)匹一人初2.算法的基本概念“算法的5个特性:(有穷性、确定性、可行性、零个或多个输入、一个或多个输出)“时间复杂度:评估算法的重要标准之一,能较好的体现算法本身的时间效率,与计算机硬件无关(基本操作、问题的规模、基本操作的频度是问题规模的函数)例:n个数中找最大的*习题集P1.7C2,3)1.8(6,7)2怡途1.线性表的逻辑结构“前驱、后继“一对一的关系.线性表的顺序存储结构(使用连续的存傅空间“顺序表特点:叶以随机访问“插入;劫有n个元索的顺序表八在第个元素之前插入,也即插入元素作
3、为第i个元素i=n+1时移动元素次数为0;i=1时移动元素次数为n;般情况n-i+l;Ci国口许“删除让1时移动元素次数为n-1;i=n时移动元素次数为0:-般情况移动次数n-i;“插入、删除的基本操作为元素移动时间复梁度为0()*习题集P42.7C1,2)“当线性表的元素总数基木稳定,且很少进行插入和删除操作,但要求以最快的速度存取线性表中的元素时,应采用()存傅结构。1述“顺序查找、折半查找线性表中某个元素x,返回其位置“查找顺序表中某个元素x的个数“线性表的插入和别除算法Ci国口许3.线性表的链式存储结构(存傅空间可以连续也可以不连续“链表(结点、头指针、尾结点、带头结点的链表特点:不能随机访问
