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

《大学数据结构复习要点.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堆排

16、序快速排序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)=()。ALOC0,0,0+i*

17、b2*b1+j*b1+k;BLOC01O10+i*b3*b2+j*b1+k;CLOC0,0,0+b3*i+b2*j+k;DLOC0,0,0+b3*i*j+b2*j+k;15、采用链表方式表示一个栈，便于结点的插入与删除。栈顶结点的插入与删除能在链表的0进行A任意位置B一端C两端D中间进行16、下面哪种数据结构不适合作栈的存储结构基础0A.数组B单链表C静态链表D二叉树结构17、栈的操作特点是0A先进先出B后进先出C两端操作D都不对18、中缀表达式(A+B)*D+E(F+A*D)+C正确的后缀表达式为0。AAB+D*EFAD*+C+BAB+D*EFA+D*+C+CAB+DEFAD*+*+C+DA

18、B+D*EFDAC+*/+19、后缀表达式A-B+C-D+的中缀形式()AA-B+(-C+D)B-A+B-(C+D)C-A+B-C+DDA+(-B)-C+D20、三个结点的二叉树的形态有。种A3B4C5D621、N个结点的连通图至少有0条边。ANBN-1CN+1DN*(N-1)/222、下图为AC)V网，其可能的拓扑有序序列为0。AABCDEFBABCEDFCABCEFDDABCDFE23、将上图看做无向图，从A出发的广度优先遍历结果为O多选题1、已知输入序列为abed,经过输出受限的双向队列后能得到的输出序列有()。AdacbBcadbCdbcaDbdacE以上都不对2、在下列情况中，可称为

19、二叉树的是()。A每一个结点至多有两棵子树的树B哈夫曼树C每一个结点至多有两棵子树的有序树D每一个结点惟独一棵右子树E以上都不对三、画图及综合题1、设n为正整数，试确定下列各程序段中带标号的语句的执行次数。1) i=1;k=1;while(i=n-1)i=i+1;k=k+10*l;)2) k=0;for(i=1;i=n;i+)for(j=1;j=G+1)*(i+1)(j=j+1;)2、用类似于带表头结点的链表存储方式画出如下列表LS的存储结构图，并分别求其长度和深度值。LS=(),a,(b,c),(),d),(e)3、根据B树的定义，3阶B树中允许每一个结点至少要有2个子树，最多有3个子树，试

20、画出在下图所示的2-3树中删除关键字15后B树的形状，并说明其变化过程。4、从一-棵空的平衡二叉树开始，把关键字(5,17,6,21,14,13,28,3,40)按浮现的先后次序逐个插入，从而构造一棵平衡二叉排序树。请画出每插入一个关键字后得到的树型结构，若需要进行平衡旋转，则表明旋转类型及旋转后的结果。5、己知一个度为m的树中有I个度为1的结点，7个度为2的结点，%个度为3的结点，L个度为m的结点。问该树的叶子结点数？m6、已知一个由n(设n=10)个整数组成的线性表，试设计该线性表的一种存储结构，并用C+描述算法，实现将n个元素中所有大于等于100的整数放在所有小于IOC)的整数之后。要求算法的时间复杂度为O(n),空间复杂度为O(1).#includeincludemain()(inta101;inti,j,t;for(i=0Jai;i=0j=9;t=aO;while(ij)(while(i=100)j-;if(ij)ai+=aj;while(ij&ai100)i+;if(ij)aj-=ai;)ai=t;for(i=1J10;i+)coutaicoutendl;)