大学数据结构复习要点.docx

上传人:王** 文档编号:334259 上传时间:2023-06-02 格式:DOCX 页数:7 大小:41.44KB
下载 相关 举报
大学数据结构复习要点.docx_第1页
第1页 / 共7页
大学数据结构复习要点.docx_第2页
第2页 / 共7页
大学数据结构复习要点.docx_第3页
第3页 / 共7页
大学数据结构复习要点.docx_第4页
第4页 / 共7页
大学数据结构复习要点.docx_第5页
第5页 / 共7页
大学数据结构复习要点.docx_第6页
第6页 / 共7页
大学数据结构复习要点.docx_第7页
第7页 / 共7页
亲,该文档总共7页,全部预览完了,如果喜欢就下载吧!
资源描述

《大学数据结构复习要点.docx》由会员分享,可在线阅读,更多相关《大学数据结构复习要点.docx(7页珍藏版)》请在优知文库上搜索。

1、第一章复习要点是:数据、数据元素、数据结构(包括逻辑结构、存储结构)以及数据类型的概念、数据的逻辑结构分为哪两大类,及其逻辑特征、数据的存储结构可用的四种基本存储方法。时间复杂度与渐近时间复杂度的概念,如何求算法的时间复杂度。可能出的题目有选择题、填空题或者简答题。第二章复习要点是:线性表的逻辑结构特征、常见的线性表的基本运算,并可以根据这些基本运算组合得到更复杂的运算。顺序表的特征、顺序表中结点地址的计算。顺序表上实现的基本运算(算法):主要是插入和删除的算法。顺序表的算法应该掌握。算法时间复杂度要记住。单链表的特征、图形表示法。单链表的各种算法实现,并能运用这些算法解决一些简单问题;循环链

2、表的特征、双链表的特征以及它们的主要算法实现。可能出的题型有:填空题、简答题、应用题和算法题。第三章复习要点是:栈的定义、其逻辑结构特征、栈的基本运算、栈的上溢、下溢的概念。队列的逻辑结构,队列的基本运算:循环队列的边界条件处理:以上各种基本运算算法的实现。算法的简单应用。可能出的题型有填空、选择、简答、算法等。第四章复习要点是:串是一种特殊的线性表,它的结点仅由一个字符组成。空串与空白串的区别:空串是长度为零的串,空白串是指由一个或者多个空格组成的串。串运算的实现中子串定位运算又称串的模式匹配或者串匹配。串匹配中,普通将主串称为目标(串),子串称为模式(串)。本章可能出的题型多半为选择、填空

3、等。第五章复习要点是:多维数组和广义表的逻辑结构特征:它们是复杂的非线性结构。一个数据元素可能有多个直接前趋和多个直接后继。多维数组的两种顺序存储方式:行优先顺序和列优先顺序。这两种存储方式下的地址计算方法。几种特殊矩阵的特征及其压缩存储地址对应关系。稀疏矩阵的三元组表示(耐图形表示)。广义表是线性表的推广,也是树的推广。能画出广义表的图形表示法。广义表的取表头运算与取表尾运算要注意,表头是广义表的第一个元素,它不一定是原子,表尾则必是子表。第六章复习要点是:本章是重点章,二叉树又是本章的重点内容。据分析,本章在试题中所占分数达到20%摆布,如加之其他章节与二叉树有关的二叉排序树等内容,则占有

4、四分之一以上的分值,可见树是十分重要的内容,务必子细掌握各个知识点。首先是树的概念,包括与树有关的各个名词的意义要能够彻底领略,在这方面可能出的题目多是填空、选择等题型。树的四种表示方法:树(图)形表示法、嵌套集合表示法、凹入表示法和广义表表示法。二叉树的定义、二叉树的五种基本形态、为什么二叉树不是树的特殊情形,这里要注意二叉树与度为二的有序树的区别所在。二叉树的四个性质,如果理解了二叉树,应该能够推导出来。多会出填空题。对于两种特殊情形的二叉树(彻底二叉树和满二叉树的定义)应该十分清楚。二叉树的顺序存储适宜用于彻底二叉树。第七章复习要点是:图的概念中主要记忆连通图、连通分量、强连通图和强连通

5、分量的定义和应用(填空、选择、应用)。图的邻接矩阵表示法和邻接表表示法应熟练掌握,根据表示法画出图或者根据图写出邻接矩阵表示或者画出邻接表(应用)。注意一个图的邻接矩阵表示是惟一的,而邻接表表示则不是唯的。稀疏图及稠密图的概念及合用的表小法(二:或f,抨等)。在图中求顶点的度,在邻接表和邻接矩阵中如何计算(填空题)。图的遍历一定要掌握,对图的深度优先遍历和广度优先遍历的遍历序列应能正确写出(填空或者选择)。两种遍历生成树的作图(选择、应用)。最小生成树的两种算法思想(Prim算法、KrUSkal算法)要掌握,就是要能在给定的图中分别用两种算法作出最小生成树(包括生成过程)(应用)。最短路径树的

6、生成画图(应用)。拓扑排序的两种方法(无前趋的顶点优先和无后继的顶点优先)应注意到使用DFS遍历算法是后一种方法所排出的拓扑序列(填空、选择)。第九章复习要点是:查找的基本概念应明确动态查找表和静态查找表的含义、内查找和外查找的含义,平均查找长度的定义及计算。线性表的查找有三种方法:顺序查找、二分查找和分块查找。二分查找对线性表的要求。什么是判定树?对于给定的序列,画出二叉判定树。二分查找的平均查找长度,其在最坏情况下查找成功的比较次数也不超过判定树的深度。为什么在链表上无法实现二分查找?分块查找的算法思想。分块有序,块内无序。又称索引顺序查找。三种查找方法各自的优缺点。树上的查找,是重点(这

7、里有二叉排序树、平衡二叉排序树)。什么是二叉排序树?二叉排序树的插入和生成,给定一个序列,请画出二叉排序树的生成过程。二叉排序树中结点的删除。其中要注意的是第三种情况,删除的结点若有两个孩子,则用删除结点的中序后继结点来替换要删的结点。二叉排序树的查找就是从根结点出发走一条从根到待查结点的路径,应能判断某一序列是否是二叉排序树中可能的查找序列。二叉排序树与二分查找的比较及选择。什么是平衡二叉树?B-树,主要应了解B-树的生长过程,当结点分裂时产生的两个结点大约是半满的,向上插入的关键字总是分裂结点中间位置上的关键字,无论按何次序插入关键字,树都是平衡的。这与二叉排序树是不同的。散列表(也是重点

8、内容),什么是散列表?散列函数、散列值、散列的含义。冲突(碰撞)、同义词的含义。散列函数的选择标准:简单和均匀。学过的几种方法:平方取中法、除余法、相乘取整法、随机数法。处理散列表中冲突的方法:开放定址法和拉链法。产生会萃的原因是什么?使用线性探查法画出散列表,并能计算散列表中查找的平均查找长度。使用拉链法画出生成的散列表,也应能计算查找的平均查找长度。什么是装填因子?装填因子和散列表中冲突发生率的关系。第十章复习要点是:本章亦是很重要的章节,通过试卷分析,分值普通占10%摆布,但是本章的内容不少,很难说哪部份是不重要的。基本概念中应明确稳定排序和不稳定排序的含义、内部排序和外部排序的含义。排

9、序算法好坏的评价标准是执行时间和所需的空间,此外算法本身的复杂程序也是要考虑的一个因素。(1)插入排序:直接插入排序法应掌握算法(包括算法的实现)(算法题)。希尔排序的算法思想,要能写出每趟排序的结果。希尔排序是不稳定的(希尔:排得希里胡涂尔:)(2)交换排序:交换排序的基本思想(两两比较反即换)。包括冒泡排序和快速排序。冒泡排序的算法应掌握。冒泡排序是稳定的。快速排序法应掌握算法思想(分治),针对给定的实例,写出快速排序的排序过程。(应用)快速排序的平均时间复杂度为O(nlgn),它是不稳定的(一快就不稳)选择排序:基本思想就是每趟选一排在后。简单选择排序的算法思想和实现,能写出其各排序的过

10、程。堆排序。堆的定义(大根堆就是双亲比孩子大,小根堆就是双亲比孩子小)。请判断个序列是不是堆(大根堆或者小根堆)。建堆和堆排序的图示过程。堆排序是不稳定的。(4)归并排序:算法思想和归并排序过程的表示。(5)分配排序:基数排序的分配方法(图示)。重点掌握链式基数排序,是稳定的。各种内部排序方法的比较和选择(本章的重点内容)。总复习练习题一、填空题1、抽象数据类型ADT是指0以及()2、设有一空栈,栈顶指针为IooOH(),现有输入序列为1,2,3,4,5,经过PUSH、PUSH、POP、PUSH、POP、PUSH、PUSH之后,输出序列是(),而栈顶指针值是()H,设栈为顺序栈,每一个元素占4

11、个字节。3、对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为(),所有顶点邻接表中的结点总数为()。4、若一个广义表为(a,(a,b),d,(i,j,0),k),e),则该表深度为(),而表长度为()。5、在具有n个结点的有序单链表中,插入一个新结点并依然有序的时间复杂度为0。6、双端队列是()的线性表。7、二叉树的链式存储结构中,空指针的数目是0,设该树中有n个结点。8、N个顶点的连通图至少有0条边。9、设数组A0.n-1为循环队列的存储空间,其队头、队尾指针分别为front和rear,则在队列非满时元素X入队的时指针变化情况为()。10、基数排序法是。排序法,它与

12、插入交换和选择排序法的排序策略均不同。11、锦标赛排序的时间复杂度为0从稳定性上讲是一个0的排序方法。堆排序的时间复杂度为0是一个0的排序方法。12、队列是一种限定。的线性表,它只允许在表的一端插入,在另一端删除,允许插入的一端叫做0,允许删除的一端叫做()。13、在结点为N的各棵树中,高度最小的树的高度为(),它有。个叶结点,()个分支结点,高度最大的树的高度是0,它有。个叶子结点,0个分支结点。14、已知一棵二叉树的前序遍历结果是Abecdfghij,中序遍历的结果是Ebcdafhigj,则它的后序遍历结果是()。15、一棵高度为h的满k叉树有如下性质:第h层上的结点都是叶子结点,其余各层

13、上每一个结点都有k棵非空子树,如果按层次自顶向下,同一层自左向右,顺序从1开始对全部结点进行编号,则n层结点个数是(),编号为i的结点的父结点的编号为(),编号为i的第m个孩子结点若存在,编号是0,编号为i的结点有右兄弟的条件为0,其所有右兄弟结点编号为0。16、循环队列为空时的队头指针和队尾指针front=rear为了区别与队空条件,用。来判断是否队列已满,也就是说,让rear指针指到front的前一位置就认为大小为maxsize的队列已满。17、若单链表的结点具有数据域data和指针域next,Mst为链表的头指针,该表为空的条件是O。二、选择题2、折半查找算法的时间复杂度是O。A0(2)

14、BO(n)CO(nlog2)DO(log2)3、m阶B树中的m是指0。A每一个结点至少有m棵子树B非终端结点中关键字的个数C每一个结点至多有m棵子树Dm阶B树的深度(或者高度)4、对记录的关键字集合Key=50,26,38,80,70,90,8,30,40,20进行排序,各趟排序结束时的结果为5026388070908304020508304020902638807026830402080503890708202630384050708090其使用的排序方法是()。A快速排序B基数排序C希尔排序D归并排序5、下面那种数据结构可以用作栈的存储结构基础0。A二叉树结构B静态链表C4阶B树结构D十字

15、链表6、若循环链表的结点具有数据域data和指针域next,H指向其头结点,该表具有一个结点的条件是()为真值。AH=H-nextBH=H-next-nextCH-nextD!(H-next)7、若A、B、C、D、E、F车顺序进栈,且任意一辆车可以在栈顶时出栈,则出栈次序可以为()。ADCEFABBDFEBACCAEDFCBDAEDFBC8、下列排序算法的时间复杂性最小的是0。A直接插入排序B希尔排序C简单选择排序D归并排序9、二叉排序树可通过。得到排序序列。A中序遍历二叉树B后序遍历二叉树C光序遍历二叉树D都可以10、就排序算法所用的辅助空间而言,堆排序、快速排序、归并排序的关系是0。A堆排序快速排序V归并排序B堆排序V归并排序快速排序C堆排序归并排序快速排序D堆排序快速排序归并排序E以上答案都不对11、一棵彻底二叉树上有1001个结点,其叶子结点的个数是()。A250B500C254D505E以上答案都不对12、下列排序算法的时间复杂度最小的是O。A.冒泡排序B希尔排序C简单选择排序D归并排序13、下列排序算法的空间复杂度最大的是0。A直接插入排序B希尔排序C快速排序D归并排序14、数组A三维的长度分别为b3,b2,b1;每一个数组元素占一个存储单元;LoqO,0,0为基址。若以行序为主序,Ai,j,k(0=i=b3,0=j=b2,0=k=b1)=()。ALOC

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 研究生考试 > 专业课

copyright@ 2008-2023 yzwku网站版权所有

经营许可证编号:宁ICP备2022001189号-2

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!