数据结构期末复习范围第一章算法与程序1、何谓算法？简述算法的基本特性和表示方法。
2、如何评价一个算法？简述环路复杂度、空间复杂度和时间复杂度的概念。
3、简述算法与程序的联系与区别，并列举常用的算法设计方法。
第二章常用数据结构1、数据类型与数据结构的联系与区别是什么？2、数据类型的6个显著特征是什么？3、举例说明数据结构的逻辑结构、数据的存储结构和数据的运算三个方面的内容。
4、什么是线性结构？什么是非线性结构？举例说明。
第三章简单数据结构1、线性表可用顺序表和单链表作为存储结构。
问：●两种存储表示各有哪些主要优缺点？●如果有n个表同时并存，且处理过程中各表的长度会动态发生变化，表的总数也可能自动改变；在此情况下应选用哪种存储表示？为什么？●若表的总数基本稳定，且很少插入和删除，但要求以最快速度存取表中元素；这是应采取哪种存储表示？为什么？2、设有一个栈，元素的进栈次序依次为A、B、C、D、E，问能否得到下面的出栈序列？若能请写出操作序列，若不能请说明原因？●C、E、A、B、D●C、B、A、D、E●D、C、A、B、E●A、C、B、E、D`●A、B、C、D、E●E、A、B、C、D3、已知表达式的中缀表示为(A+B)*D+E/(F+A*D)+C，利用栈把它改写成为后缀表示，并写出转换过程中栈的变化。
4、何为队列的上溢现像？解决方法有哪些？各种方法的工作原理是什么？第四章树与二叉树1、已知一棵树边的集合为{(I,M),(I,N),(E,I),(B,E),(B,D),(A,B),(G,J), (G,K),(C,G),(C,F),(H,L),(C,H),(A,C)}，请画出这棵树并回答如下问题：●那个是根结点？●那些是叶子结点？●那个是结点G的双亲？●那些是结点G的祖先？●哪些是结点G的孩子？●哪些是结点E的子孙？●哪些是结点E的兄弟？哪些是结点F的兄弟？●结点B和结点N的层次号分别是多少？●树的深度是多少？树的度是多少？●以结点C为根的子树的深度是多少?2、分别画出有三个结点的树和有三个结点的二叉树的所有不同形态。
3、已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，问该树中有多少叶子结点？4、一棵深度为h的满k叉树是这样的一棵树，他的第h层上的结点全部是叶子结点，其余各层上的每个结点都有k可非空子树。
如果对深度为h的满k叉树按层次自上而下，同层次自左至右的顺序从1开始对所有结点编号，问：●各层的结点数目是多少？●编号为n的结点的双亲结点若存在，其编号是多少？●编号为n的结点的第i个孩子结点若存在，其编号是多少？●编号为n的结点有右兄弟的条件是什么？其右兄弟编号是多少？4、一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各为多少？5、对于下图所示的一棵二叉树，分别写出：●前序遍历序列●中序遍历序列●后序遍历序列●层次遍历序列6、已知一棵二叉树的前序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK。
请画出该二叉树，并写出它的后序序列和层次序列。
7、已知一棵二叉树的后序序列为DCEGBFHGIKJ，中序序列为DCBGEAHFIJK。
请画出该二叉树，并写出它的前序序列和层次序列。
8、已知一棵二叉树的层次序列为ABCDEFGHIJ，中序序列为DBGEHJACIF。
请画出该二叉树，并写出它的前序序列和后序序列。
9、把下图所示的两棵树，分别转化为相应的二叉树。
P12610、把下图所示的森林转化为相应的一棵二叉树。
P12711、把下图所示二叉树转化为相应的树，然后分别写出其先根序列和后根序列。
P12712、给定一个权重集合为W={3,15,17,14,6,16,9,2}，请画出相应的哈夫曼树，并计算其带权路径长度WPL。
13、已知二叉树以二叉链表作为存储结构，编写按层次遍历该二叉树的算法。
14、已知二叉树以二叉链表作为存储结构，编写按前序遍历该二叉树的算法。
第五章图与网1、对如下有向图给出其邻接矩阵、邻接表和逆邻接表，并计算每个顶点的度。
P159 图5-34（a）2、对如下有向图给出其邻接矩阵、邻接表和逆邻接表，并计算每个顶点的度。
P159 图5-34 （b）3、对下图分别给出：⑴深度优先搜素遍历序列和深度优先生成树；⑵广度优先搜素遍历序列和广度优先生成树；⑶用Prim算法求得最小生成树的过程；⑷用Kruskal算法求得最小生成树的过程。
P159 图5-354、对下图分别给出：⑴邻接矩阵；⑵用Dijkstra算法求从v1出发到各顶点的最短路径。
P159 图 5-365、用Floyd算法求下图中每对顶点间的最短路径。
P159 图 5-376、用邻接矩阵表示图时，若图中有100个顶点和100条边，则形成的邻接矩阵中有多少个元素？有多少个非零元素？是否为稀疏矩阵？7、用邻接矩阵表示图时，矩阵中元素的个数与顶点个数是否相关？与边的条数是否相关？8、有n个顶点的无向连通图至少有多少条边？有n个顶点的有向强连通图至少有多少条边？9、对于有n个顶点的无向图，若采用邻接矩阵表示如何判断以下问题：⑴图中有多少条边？⑵任意两个顶点i和j之间是否有边相连？⑶任意一个顶点的度是多少？第六章数据结构的程序实现1、阐述数据结构在问题建模中的重要作用。
第七章检索与基本算法1、若对大小为n的顺序表和有序表分别进行顺序检索，在等概率的前提下，工况时的平均检索长度是否相同：⑴检索不成功，即表中没有关键字值等于给定值k的记录；⑵检索成功，表中只有一个关键字值等于给定值k的记录；⑶检索成功，表中有若干个关键字值等于给定值k的记录，依次检索要求能全部找出所有关键值等于给定值k的记录。
2、对长度为20的有序表进行二分法检索，画出他的一棵判定树，并求出在等概率情况下检索成功和不成功时的平均检索长度。
3、对于10000个项的线性表，若采用等分区间顺序检索方法进行检索，问：⑴每块的理想长度为多少？此时把线性表划分成多少个块？⑵平均检索长度为多少？假定在等概率情况下讨论。
⑶若每块长度为40，请平均检索长度为多少？4、设结点序列为（60，30，90，50，120，70，40，80），用二叉检索树的插入算法，画出按此结点序列建立的一棵二叉检索树T1；再用二叉检索树的删除算法，画出依次删除结点40，70，60之后的二叉检索树T2。
5、已知长度为12的表如下所示：（Jan,Feb，Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec）⑴按表中元素的顺序依次插入一棵初始为空的二叉检索树中，画出最终的二叉检索树，并求在等概率情况下检索成功时的平均检索长度。
⑵若先对表中元素排序成有序表，求在等概率情况下进行二分法检索时检索成功的平均检索长度。
⑶构造一棵二叉平衡树，求在等概率情况下进行二分法检索时检索成功的平均检索长度。
6、具有n个结点的二叉检索树有多少种不同的形态？一个高度为h的二叉平衡树至少有多少个结点？具有n个结点的二叉平衡树的最大高度和最小高度各是多少？7、给定关键字序列为（19，14，23，1，68，20，84，27，55，11，10，79），设哈希表长为13，哈希函数为h（k）=k%13：⑴画出用线性探索法消除地址冲突时所构造的哈希表。
⑵画出用链地址法消除地址冲突时所构造的哈希表。
⑶并求出以上两种哈希表的平均检索长度。
8、设计一个算法，求出指定结点在二叉检索树中的层次数。
第八章排序与基本算法1、什么是排序？什么是内排序？什么是外排序？2、给定排序码序列为（17，8，21，35，32，15，21，25，12，23），分别写出：●直接插入排序●希尔排序（增量为5，2，1）●二路插入排序●折半插入排序●共享栈插入排序●冒泡排序●快速排序●直接选择排序●树形选择排序●堆排序●二路归并排序●基数排序3、在冒泡排序方法中，什么情况下排序码会朝着与最终位置相反的方向移动？是举例说明。
4、对于n个排序码进行快速排序时，所需的比较次数与排序码的初始序列有关。
当n=7时，回答下列问题：⑴在最好的情况下需要进行多少次比较？请说明理由。
⑵给出在最好情况下的排序码初始序列的一个实例。
⑶在最坏的情况下需要进行多少次比较？请说明理由。
⑷给出在最坏情况下的排序码初始序列的一个实例。
5、写出快速排序的非递归算法，并回答下面问题：⑴在非递归实现排序快速排序时，通常要用一个栈来保存待排序区间的两个端点。
这个栈能否用队列来代替？为什么？⑵在非递归实现排序快速排序时，可根据基准把待排序区间分割为两个区间。
若下一趟先对较短的区间进行排序。
证明在这种情况下快速排序所需栈的深度为O（nlogn）。
6、若排序码有11个，为了完成树形选择排序，至少需要进行多少次关键字值的比较？7、判断下列序列是否为堆。
若不是堆则把它们调整为堆：●（100，85，98，77，80，60，82，40，20，10，66）●（100，98，85，82，80，77，66，60，40，20，10）●（100，85，40，77，80，60，66，98，82，10，20）●（10，20，40，60，66，77，80，82，85，98，100）8、希尔排序、直接选择排序、快速排序、堆排序都是不稳定的排序方法，举例说明。