数据结构期末考试复习资料.docx

期末测验温习材料一、测验题型1、选择题每题2分，共20分2、填空题每题2分，共10分3、运用题每题6分，共30分4、次序浏览题每题5分，共20分5、编程题每题10分，共20分二、测验重点内容第一章绪论1、时刻庞杂度跟空间庞杂度的盘算。请求能够盘算出次序的履行次数。2、种种观点：数据构造、数据项、数据元素第二章线性表1、单链表的种种操纵，包含单链表的树破、拔出、删除结点的操纵语句序列2、单链表带头结点、不带头结点、轮回单链表的逆置运算。3、双链表的拔出跟删除操纵语句序列。4、单链表的直截了当拔出排序运算。5、静态单链表的拔出跟删除操纵。6、二个有序单链表的兼并、一个单链表拆分为多个单链表第三章栈跟行列1、栈的输入序列跟输入序列、递归函数的输入后果2、轮回行列的入队、出队操纵以及无效元素个数的盘算第四章串1、KMP算法中的next跟nextval值的盘算第五章数组跟狭义表1、二维数组恣意元素地点的盘算2、稀少矩阵的转置算法3、狭义表的两个操纵函数：取表头跟表尾第六章树跟二叉树1、二叉树的性子特不是完整二叉树的性子，比方求完整二叉树的深度等2、二叉树的遍历特不是中序跟先序遍历，请求能够运用客栈实现非递归遍历编程跟递归算法编程，在遍历根底上的种种操纵，比方求二叉树的叶子数、二叉树结点数等操纵，包含有编程算法跟编程填空题3、线索二叉树特不是中序线索化二叉树跟中序线索化二叉树的中序遍历，包含编程算法跟编程填空题，盼望年夜伙儿侧重研讨4、哈夫曼编码要紧是运用题，包含哈夫曼的编码与解码，也包含哈夫曼树的特色5、树与丛林在转化成二叉树时，阁下子树的结点数有何特色6、树的档次遍历运用行列实现、借助树的档次遍历能够推断二叉树能否为完整二叉树、推断二叉树能否为排序二叉树等，能够有编程题或编程填空题弥补：二叉树的物理存储构造链式跟次序存储*第七章图1、图的两种物理存储方法毗邻矩阵与毗邻表存储表现2、图的天生树与最小天生树天生树特色、图的遍历3、求最小天生树的两种算法重点是PRIM算法，特不会写出用PRIM算法求最小天生树的进程4、运用迪杰斯特拉算法求单源最短途径，写出求解进程5、拓扑排序6、求要害途径，请求写失事情跟运动的最早跟最晚开场时刻，深入了解要害途径的含意。第八章查寻1、次序查寻算法2、有序表的折半查寻包含算法编程、求均匀查寻长度等3、二叉排序树的构建跟运用4、均衡二叉排序树的构建跟运用四种扭转5、B-树的拔出跟删除操纵6、运用线性、二次探测法跟链表法实现哈希表的构建、盘算哈希表的均匀查寻长度等第九章排序1、拔出排序庞杂拔出、希尔排序每趟排序的后果2、交流排序包含冒泡排序、疾速排序每趟排序后果，疾速排序的算法实现，能够有次序填空题，特不是冒泡排序的疾速处置技能运用3、选择排序庞杂项选择择排序、堆排序的排序进程及每趟排序后果的运用、堆排序算法填空4、合并排序包含每趟排序的后果5、基数排序包含每趟排序后果次序浏览题范畴：1单链表的种种操纵单链表的树破、删除跟修正、逆置等2客栈的运用包含数制转换等3二叉树的种种递归编程运用求树的深度、叶子的数目、结点的数目等4二叉排序树的编程实现包含查寻跟拔出元素5交流排序的编程实现编程题范畴：1轮回单链表、单链表逆置2两个有序单链表的兼并、一个单链表依照规那么进展拆分、删除有序单链表中反复元素、删除单链表某个结点、单链表的庞杂拔出、单链表选择排序，单链表中求最年夜值跟最小值等。3二叉树的非递归中序遍历跟递归遍历5二叉树的中序线索化算法、对中序线索二叉树进展中序遍历6推断二叉树能否为完整二叉树、二叉树能否为二叉排序树、求二叉树的深度、求二叉树某个结点的子孙等