2022年数据结构总复习 .pdf

第一章绪论1、 数据结构主要包括哪三方面内容？2、 数据结构是一个二元组（D，R ） ，其中 D 、R分别代表什么？3、 什么是逻辑结构？什么是存储结构？两者有何关系？4、 逻辑结构主要分哪两个类型？5、 存储结构主要有那些方式？6、 顺序存储方式是如何表示数据元素之间的关系？其存储地址一定连续吗？7、 链式存储方式是如何表示数据元素之间的关系？其存储地址一定连续吗？8、 逻辑结构与具体计算机有关吗？存储结构呢？9、 什么是算法？算法有哪五个基本性质？10、 算法与具体的计算机及计算机语言有关吗？11、 算法与程序有何异同与联系？12、 算法分析主要从哪三方面考虑？第二章线性表1、 线性结构的逻辑关系是什么？2、 顺序表是如何表示数据元素的逻辑关系的？3、 单链表的特点是什么？4、 如何在单链表指定结点之后插入一个新结点？如何将指定结点之后的结点删除？5、 循环链表的特点是什么？6、 双向链表的特点是什么？7、 如何在双向链表指定结点之前或之后插入一个新结点？如何将指定结点删除？8、 顺序表与链表比较各自的优缺点是什么？9、 算法要求：（分别在顺序表和链表实现下面算法）（特别是会修改指针）（1） 建立。（链表的头插法和尾插法）（2） 查找指定元素。查找第i 个元素。（3） 插入在第i 个位置、插入在指定元素前或后、有序表的插入。（4） 删除第 i 元素、删除指定元素。（5） 线性表逆置。（6） 两个线性表的有条件合并。第三章栈、队列复习题1. 栈的操作原则是什么？2. 栈有哪些基本运算？3. 算法要求：在顺序表和链栈实现基本运算。注意：栈空的条件和栈满的条件及栈顶指针的移动。4. 两个栈共享空间时基本运算如何实现? 5 递归与栈有何关系？6. 队列的操作原则是什么? 7. 队列有哪些基本运算？8. 顺序队列操作中的“假溢出”是什么？9. 循环队列是存储在循环链表中吗？10. 循环队列空的条件、满的条件及求长度公式各是什么？11. 算法要求：在循环队列和链式队列实现基本运算。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - 注意：队列空的条件和队列满的条件及队头、队尾指针的移动。10. 栈和队列的共同点和不同点是什么？第四章串复习题1、 串的逻辑结构是什么？2、 空串与空格串的区别是什么？3、 两个串相等的充分必要条件是什么？4、 空串是任意串的子串吗？串自身呢？5、 什么是结点大小？6、 了解串的基本运算的含义。7、 什么是模式匹配？如何实现？8、 算法要求（顺序串和链串）：串的插入、删除、置换、模式匹配等。第五章数组的复习题1、数组的逻辑结构是什么？2、数组的特点是什么？数组可以进行插入删除操作吗？3、数组通常以什么方式存储？4、存储二维数组有哪两种排列方式？（要求会计算存储地址）5、特殊矩阵的压缩存储基本思想是什么？6、对称矩阵、三角矩阵和对三角矩阵如何压缩存储？7、稀疏矩阵只需存储非零元素的值吗？8、操作要求：会画出稀疏矩阵的三元组表和十字链表的表示。9、算法要求： 在稀疏矩阵的三元组表和十字链表中，给定一组下标求出中元素值及矩阵简单操作。第七章树的复习题1、树的递归定义是什么？树的逻辑结构是什么？2、什么是树的度？什么是树的深度？3、树有那些存储方式？要求会画出各种存储方式。4、操作要求：给定树或森林写出先根遍历序列和后根遍历序列两种遍历序列。5、二叉树与度为2 的树有何区别？6、操作要求：会画出二叉树的5 种基本形态。7、三个结点能组成几种不同的二叉树？8、二叉树的五个性质是什么？9、满二叉树的特点是什么？完全二叉树的特点是什么？10、会画出二叉树按顺序方式存储和链式方式存储的表示。11、什么是（二叉树或树）遍历？（1）给出一棵二叉树要求会写出其前序遍历序列、中序遍历序列及后序遍历序列。（2）给出一棵二叉树的先根遍历序列和中根遍历序列要求能画出其二叉树。给出一棵二叉树的中根遍历序列和后根遍历序列要求能画出其二叉树。12、算法要求：二叉树的遍历算法。（递归遍历、非递归遍历及按层次遍历的算法）遍历算法的应用。13、N个结点的线索二叉树按二叉链表方式存，共有多少指针域？其中多少指针域为线索。14、操作要求：会画线索二叉树。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - 15、操作要求：给定二叉树能转换为树或树林，给定树或树林能转换为二叉树。第八章广义表的复习题1、什么是广义表？其逻辑结构是什么？2、广义表主要有哪些基本运算？3、求表头运算结果一定是原子元素吗？求表尾一定是个子表吗？4、 操作要求： 给定广义表能画出其单链表示，并能进行求表头、 求表尾、 求长度及深度运算。第九章图复习题1、图的逻辑结构是什么？2、一个具有N个顶点的完全无向图有多少条边？完全有向图呢？3、什么是图中顶点的度？4、任意图是其自身的子图吗？5、什么是连通图及连通分量？6、什么是生成树？生成树的三个特点是什么？7、操作要求：给出图要求能画出其邻接矩阵、邻接表、十字链表和多重邻接表。8、邻接矩阵占的存储空间大小与图中顶点个数有何关系？与边（或弧）的个数有何关系？9、邻接表中无向图中每条边要占多少结点？有向图呢？10、什么是图的遍历？两种基本方法是什么？11、操作要求：给定图（或给定其存储结构示意图）要求能写出其两种遍历序列。并画出对应的生成树或森林。12、图的应用 : 最小生成树和最短路径13、算法要求：两种不同存储方式下实现插入边、删除边及求顶点的度。两种遍历的通用算法及具体存储方式的遍历算法。第十章查找复习题1、ASL是什么？其有何用？2、顺序查找ASL为多少？3、可用于二分查找( 折半查找 ) 的查找有什么要求？4、二分查找 ( 折半查找 )若加入插入其效率如何？要求会计算折半查找的比较次数。6、算法要求：二分查找( 折半查找 ) 的算法。7、操作要求：会画有n 个记录的二叉判定树，并求出ASL（成功与不成功） 。8、什么是二叉排序树？9、中序遍历二叉排序树将得到什么结果？10、操作要求：给出一个序列能构造二叉排序树，并求出相应的ASL（成功与不成功） 。11、算法要求：二叉排序树的插入（及建立）、二叉排序树的查找。12、什么是AVL树？其特点是什么？13、操作要求：会构造AVL树，并求出ASL 。如何进行LL、RR 、LR、RL调整。14、AVL树与二叉排序树有何同异？15、什么是哈希函数？常用的是什么？什么是同义词？什么是冲突？什么是装填因子？17、操作要求：给出一个序列及哈希函数，并求出相应的ASL（成功与不成功） 。（1）能画出开放定址法的哈希表，并求出相应的ASL （成功与不成功） 。（2）能画出拉链法的哈希表，并求出相应的ASL （成功与不成功） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 4 页 - - - - - - - - - 18、哈希表的查找效率与n 有关吗？第十一章内排序复习题1、什么是排序？什么是排序的稳定性？2、内部排序与外部排序的主要区别是什么？3、连续顺序文件排序与链表排序的区别是什么？4、如何进行直接插入排序？什么情况下效率最高？最少比较多少次？移动多少次？5、如何进行起泡排序？什么情况下效率最高？最少比较多少次？移动多少次？6、如何进行直接选择排序？其比较次数与初始状态有关吗？7、快速排序在什么情况下效率低？8、在 8 种排序中哪些排序方法能在第一趟就确定出最大（或最小）元素？9、操作要求：给出一组关键字序列能分别写出各种排序的每趟结果。给出一组序列能判断是否是堆？会构造堆。10、算法要求：直接插入排序、起泡排序、直接选择排序、快速排序及堆排序名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -