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

第一章复习要点是： 数据、数据元素、数据结构(包括逻辑结构、存储结构)以及数据类型的概念、数据的逻辑结构分为哪两大类，及其逻辑特征、数据的存储结构可用的四种基本存储方法。时间复杂度与渐近时间复杂度的概念，如何求算法的时间复杂度。可能出的题目有选择题、填空题或简答题。 第二章复习要点是：线性表的逻辑结构特征、常见的线性表的基本运算，并可以根据这些基本运算组合得到更复杂的运算。顺序表的特征、顺序表中结点地址的计算。顺序表上实现的基本运算(算法)：主要是插入和删除的算法。顺序表的算法应该掌握。算法时间复杂度要记住。单链表的特征、图形表示法。单链表的各种算法实现，并能运用这些算法解决一些简单问题；循环链表的特征、双链表的特征以及它们的主要算法实现。可能出的题型有：填空题、简答题、应用题和算法题。第三章复习要点是：栈的定义、其逻辑结构特征、栈的基本运算、栈的上溢、下溢的概念。队列的逻辑结构，队列的基本运算；循环队列的边界条件处理；以上各种基本运算算法的实现。算法的简单应用。可能出的题型有填空、选择、简答、算法等。第四章复习要点是：串是一种特殊的线性表，它的结点仅由一个字符组成。空串与空白串的区别：空串是长度为零的串，空白串是指由一个或多个空格组成的串。串运算的实现中子串定位运算又称串的模式匹配或串匹配。串匹配中，一般将主串称为目标(串),子串称为模式(串)。本章可能出的题型多半为选择、填空等。 第五章复习要点是：多维数组和广义表的逻辑结构特征：它们是复杂的非线性结构。一个数据元素可能有多个直接前趋和多个直接后继。多维数组的两种顺序存储方式：行优先顺序和列优先顺序。这两种存储方式下的地址计算方法。几种特殊矩阵的特征及其压缩存储地址对应关系。稀疏矩阵的三元组表示(画图形表示)。广义表是线性表的推广，也是树的推广。能画出广义表的图形表示法。广义表的取表头运算与取表尾运算要注意，表头是广义表的第一个元素，它不一定是原子，表尾则必是子表。第六章复习要点是：本章是重点章，二叉树又是本章的重点内容。据分析，本章在试题中所占分数达到20%左右，如加上其他章节与二叉树有关的二叉排序树等内容，则占有四分之一以上的分值，可见树是十分重要的内容，务必仔细掌握各个知识点。首先是树的概念，包括与树有关的各个名词的意义要能够完全领会，在这方面可能出的题目多是填空、选择等题型。树的四种表示方法：树(图)形表示法、嵌套集合表示法、凹入表示法和广义表表示法。二叉树的定义、二叉树的五种基本形态、为什么二叉树不是树的特殊情形，这里要注意二叉树与度为二的有序树的区别所在。二叉树的四个性质，如果理解了二叉树，应该能够推导出来。多会出填空题。对于两种特殊情形的二叉树(完全二叉树和满二叉树的定义)应该十分清楚。二叉树的顺序存储适宜用于完全二叉树。第七章复习要点是：图的概念中主要记忆连通图、连通分量、强连通图和强连通分量的定义和应用(填空、选择、应用)。图的邻接矩阵表示法和邻接表表示法应熟练掌握，根据表示法画出图或者根据图写出邻接矩阵表示或画出邻接表(应用)。注意一个图的邻接矩阵表示是唯一的，而邻接表表示则不是唯一的。稀疏图及稠密图的概念及适用的表示法(填空或选择等)。在图中求顶点的度，在邻接表和邻接矩阵中如何计算(填空题)。图的遍历一定要掌握，对图的深度优先遍历和广度优先遍历的遍历序列应能正确写出(填空或选择)。两种遍历生成树的作图(选择、应用)。最小生成树的两种算法思想(Prim算法、Kruskal算法)要掌握，就是要能在给定的图中分别用两种算法作出最小生成树(包括生成过程)(应用)。最短路径树的生成画图(应用)。拓扑排序的两种方法(无前趋的顶点优先和无后继的顶点优先)应注意到使用DFS遍历算法是后一种方法所排出的拓扑序列(填空、选择)。第九章复习要点是：查找的基本概念应明确动态查找表和静态查找表的含义、内查找和外查找的含义，平均查找长度的定义及计算。线性表的查找有三种方法：顺序查找、二分查找和分块查找。二分查找对线性表的要求。什么是判定树?对于给定的序列，画出二叉判定树。二分查找的平均查找长度，其在最坏情况下查找成功的比较次数也不超过判定树的深度。为什么在链表上无法实现二分查找？分块查找的算法思想。分块有序，块内无序。又称索引顺序查找。三种查找方法各自的优缺点。树上的查找，是重点（这里有二叉排序树、平衡二叉排序树）。什么是二叉排序树?二叉排序树的插入和生成，给定一个序列，请画出二叉排序树的生成过程。二叉排序树中结点的删除。其中要注意的是第三种情况，删除的结点若有两个孩子，则用删除结点的中序后继结点来替换要删的结点。二叉排序树的查找就是从根结点出发走一条从根到待查结点的路径，应能判断某一序列是否是二叉排序树中可能的查找序列。二叉排序树与二分查找的比较及选择。什么是平衡二叉树？B-树，主要应了解B-树的生长过程，当结点分裂时产生的两个结点大约是半满的，向上插入的关键字总是分裂结点中间位置上的关键字，无论按何次序插入关键字，树都是平衡的。这与二叉排序树是不同的。散列表(也是重点内容)，什么是散列表?散列函数、散列值、散列的含义。冲突(碰撞)、同义词的含义。散列函数的选择标准：简单和均匀。学过的几种方法：平方取中法、除余法、相乘取整法、随机数法。处理散列表中冲突的方法：开放定址法和拉链法。产生聚集的原因是什么？使用线性探查法画出散列表，并能计算散列表中查找的平均查找长度。使用拉链法画出生成的散列表，也应能计算查找的平均查找长度。什么是装填因子?装填因子和散列表中冲突发生率的关系。第十章复习要点是：本章亦是很重要的章节，通过试卷分析，分值一般占10%左右，但是本章的内容很多，很难说哪一部分是不重要的。基本概念中应明确稳定排序和不稳定排序的含义、内部排序和外部排序的含义。排序算法好坏的评价标准是执行时间和所需的空间，另外算法本身的复杂程序也是要考虑的一个因素。 (1)插入排序：直接插入排序法应掌握算法(包括算法的实现)(算法题)。希尔排序的算法思想，要能写出每趟排序的结果。希尔排序是不稳定的(希尔：排得希里糊涂尔：) (2)交换排序：交换排序的基本思想(两两比较反即换)。包括冒泡排序和快速排序。冒泡排序的算法应掌握。冒泡排序是稳定的。快速排序法应掌握算法思想(分治)，针对给定的实例，写出快速排序的排序过程。(应用)快速排序的平均时间复杂度为O(nlgn)，它是不稳定的(一快就不稳) (3)选择排序：基本思想就是每趟选一排在后。简单选择排序的算法思想和实现，能写出其各趟排序的过程。堆排序。堆的定义(大根堆就是双亲比孩子大，小根堆就是双亲比孩子小)。请判断一个序列是不是堆(大根堆或小根堆)。建堆和堆排序的图示过程。堆排序是不稳定的。(4)归并排序：算法思想和归并排序过程的表示。 (5)分配排序：基数排序的分配方法(图示)。重点掌握链式基数排序，是稳定的。各种内部排序方法的比较和选择(本章的重点内容)。总复习练习题 一、 填空题1、抽象数据类型ADT是指（）以及 （）2、设有一空栈，栈顶指针为1000H（），现有输入序列为1，2，3，4，5，经过PUSH、PUSH、POP、PUSH、POP、PUSH、PUSH之后，输出序列是（），而栈顶指针值是（）H， 设栈为顺序栈，每个元素占4个字节。3、 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（），所有顶点邻接表中的结点总数为（）。4、若一个广义表为（a，（a，b），d，（i，j，（），k），e），则该表深度为（），而表长度为（）。5、在具有n个结点的有序单链表中，插入一个新结点并依然有序的时间复杂度为（）。6、双端队列是（）的线性表。7、二叉树的链式存储结构中，空指针的数目是（），设该树中有n个结点。8、N个顶点的连通图至少有（）条边。9、设数组A0.n-1为循环队列的存储空间，其队头、队尾指针分别为front和rear，则在队列非满时元素x入队的时指针变化情况为（)。10、基数排序法是（）排序法，它与插入交换和选择排序法的排序策略均不同。11、锦标赛排序的时间复杂度为（）从稳定性上讲是一个（）的排序方法。堆排序的时间复杂度为（）是一个（）的排序方法。12、队列是一种限定（）的线性表，它只允许在表的一端插入，在另一端删除，允许插入的一端叫做（），允许删除的一端叫做（）。13、在结点为N的各棵树中，高度最小的树的高度为（），它有（）个叶结点，（）个分支结点，高度最大的树的高度是（），它有（）个叶子结点，（）个分支结点。14、已知一棵二叉树的前序遍历结果是ABECDFGHIJ，中序遍历的结果是EBCDAFHIGJ，则它的后序遍历结果是（）。15、一棵高度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树，如果按层次自顶向下，同一层自左向右，顺序从1开始对全部结点进行编号，则n层结点个数是( ),编号为i的结点的父结点的编号为（），编号为i的第m个孩子结点若存在，编号是（），编号为i的结点有右兄弟的条件为（），其所有右兄弟结点编号为（）。16、循环队列为空时的队头指针和队尾指针front=rear 为了区别与队空条件，用（）来判断是否队列已满，也就是说，让rear指针指到front的前一位置就认为大小为maxsize的队列已满。17、若单链表的结点具有数据域data和指针域next，frist为链表的头指针，该表为空的条件是（）。 二、 选择题2、折半查找算法的时间复杂度是（）。A O(n2) B O(n) C O(nlog2n) D O(log2n)3、m阶B树中的m是指（）。A 每个结点至少有m棵子树B 非终端结点中关键字的个数C 每个结点至多有m棵子树D m阶B树的深度（或高度）4、对记录的关键字集合Key=50，26，38，80，70，90，8，30，40，20进行排序，各趟排序结束时的结果为50 26 38 80 70 90 8 30 40 2050 8 30 40 20 90 26 38 80 7026 8 30 40 20 80 50 38 90 708 20 26 30 38 40 50 70 80 90 其使用的排序方法是（）。A 快速排序 B 基数排序 C 希尔排序 D 归并排序5、下面那种数据结构可以用作栈的存储结构基础（）。A 二叉树结构 B 静态链表 C 4阶B树结构 D 十字链表6、若循环链表的结点具有数据域data和指针域next，H指向其头结点，该表具有一个结点的条件是（）为真值。A H= =H-next B H= =H-next-next C H-next D !(H-next)7、若A、B、C、D、E、F车顺序进栈，且任意一辆车可以在栈顶时出栈，则出栈次序可以为（）。A DCEFAB B DFEBAC C AEDFCB D AEDFBC8、下列排序算法的时间复杂性最小的是（）。A 直接插入排序 B 希尔排序 C 简单选择排序 D 归并排序9、二叉排序树可通过（）得到排序序列。A 中序遍历二叉树 B 后序遍历二叉树 C 先序遍历二叉树 D 都可以 10、就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是（）。A 堆排序 快速排序 归并排序B 堆排序 归并排序 归并排序 快速排序D 堆排序 快速排序 归并排序E 以上答案都不对 11、一棵完全二叉树上有1001个结点，其叶子结点的个数是（）。A 250 B 500 C 254 D 505 E 以上答案都不对12、下列排序算法的时间复杂度最小的是（）。A冒泡排序 B 希尔排序 C 简单选择排序 D 归并排序13、下列排序算法的空间复杂度最大的是（）。A 直接插入排序 B 希尔排序 C 快速排序 D 归并排序14、数组A三维的长度分别为b3,b2,b1；每个数组元素占一个存储单元；LOC0，0，0为基址。若以行序为主序，Ai, j, k (0=i=b3, 0=j=b2, 0=k=b1)= ( )。A LOC0, 0, 0 + i*b2*b1 + j*b1 + k;B LOC0, 0, 0 + i*b3*b2 + j*b1 + k;C LOC0, 0, 0 + b3*i +b2*j +k;D LOC0, 0, 0 +b3*i*j +b2*j +k;15、采用链表方式表示一个栈，便于结点的插入与删除。栈顶结点的插入与删除能在链表的（）进行A 任意位置 B 一端 C 两端 D 中间进行16、下面哪种数据结构不适合作栈的存储结构基础（）A数组 B单链表 C 静态链表 D 二叉树结构17、栈的操作特点是（）A 先进先出 B 后进先出 C 两端操作 D 都不对18、中缀表达式（A+B）*D+E/（F+A*D）+C 正确的后缀表达式为（）。A AB+D*EFAD*+/+C+ B AB+D*EFA+D*/+C+C AB+DEFAD*+/*+C+ D AB+D*EFDAC+*/+ 19、后缀表达式A-B+C-D+的中缀形式（）A A-B+（-C+D） B -A+B-（C+D） C -A+B-C+D D A+（-B）-C+D 20、三个结点的二叉树的形态有（）种A 3 B 4 C 5 D 621、N个结点的连通图至少有（）条边。A N B N-1 C N+1 D N*（N-1）/222、下图为AOV网，其可能的拓扑有序序列为（）。A ABCDEF B ABCEDF C ABCEFD D ABCDFE23、将上图看作无向图，从A出发的广度优先遍历结果为（） 多选题1、已知输入序列为abcd，经过输出受限的双向队列后能得到的输出序列有（）。A dacb B cadb C dbca D bdac E以上都不对2、在下列情况中，可称为二叉树的是（）。A 每个结点至多有两棵子树的树B 哈夫曼树C 每个结点至多有两棵子树的有序树D 每个结点只有一棵右子树E 以上都不对 三、 画图及综合题 1、设n为正整数，试确定下列各程序段中带标号的语句的执行次数。1） i=1; k=1; while (i=n-1) i=i+1; k=k+10*I; 2) k=0; for ( i=1; i=n; i+) for ( j=1; j=(j+1)*(j+1) j=j