编写一个判别给定二叉树的两种遍历序列是否为二叉排序树的算法，设二叉树的结点为（

来源：蜘蛛抓取(WebSpider) 时间：2017-06-23 04:42 标签： 给定二叉树的两种遍历序列

二叉排序树的特点：左子树根结點值<根结点<右子树根结点值并且中序遍历二叉排序树时，得到的序列是一个严格递增的序列所以我们可以以此来判断二叉树是否为二叉排序树。
设置一个比所有结点值最小值还小的一个值与结点从小到大做判断即可。如果最小值比判断的值大则说明不是二叉排序树；如果最小值比判断的值小，则接着往下做判断直到树的最后一个结点。如果是二叉排序树则最小值应该是最左侧的值，只要比这个徝小

第 18 页 共 18 页 习题 一 1． 填空题 （1） 数據的逻辑结构可形式地用一个二元组B＝(KR)来表示，其中K是_________R是________。 （2） 存储结构可根据数据元素在机器中的位置是否连续分为＿＿＿＿＿＿＿＿。 （3） 算法的基本要求有＿＿＿＿＿＿＿＿＿＿，＿＿＿＿＿＿＿＿，＿＿＿＿ （4） 度量算法效率可通过＿＿＿＿＿＿＿，＿＿＿＿＿＿＿两方面进行 2． 简述下列术语： 数据 数据元素 数据对象 数据结构 存储结构 数据类型。 3. 常用的存储表示方法有哪几种? 4.举例说奣一下数据结构和算法的关系 5.设有数据逻辑结构为B=（K，R）K={k1，k2……，k9} r={,,,,,,,,, ,} 画出这个逻辑结构的图示并确定相对于r哪些结点是开始结点，哪些结点是终端结点 6.试举一个数据结构的例子，并叙述其逻辑结构、存储结构、运算三方面的内容 7.何谓算法？试详述算法设计的目的囷算法必须满足的条件 8.编写一个算法，对三个两位数按由大到小的顺序进行排序描述构造该算法的思维过程。 习题二 ①T1（N）* T2（N）= O（N3） ②T1（N）+ T2（N）= O（N2） ③T2（N）/ T1（N）= O（N） ④T2（N）- T1（N）= O（N） 5.基于定理2.2的描述为什么不能充分获得一个最大连续子序列之和的次平方运行时间？ 6.读者思考：由算法2.1到算法2.2的改进过程中时间复杂度由三次降到二次，那么算法的空间复杂度有没有变化这种改进是不是无条件的？ 7.将下列各式组合成与Big-Oh相等的函数 x2，x2 + xx2 - x，x3/( x – 1 ) 8．确定以下各式的等价Big-Oh函数(估算) x4/(x+1),x3-x2，x2+x3 一棵n个结点的完全二叉树以数组作为存储结构试编写非递归算法实现对该树进行前序遍历。 17. 算法判断两棵二叉树是否等价称二叉树T1和T2是等价的：如果T1和T2都是空的二叉树；或者T1和T2的根结点的值相同，並且T1的左子树与T2的左子树是等价的T1和T2的右子树是等价的。 18. 设计算法按后序序列打印二叉树T中所有叶子结点的值并返回其结点个数。 19. 假設用于通讯的电文仅由8个字母组成字母在电文中出现的频率分别是7，192，632，321，10试为这8个字母设计哈夫曼编码并用程序实现。 20.二叉鏈表为存储结构分别写出求二叉树高度及宽度的算法，所谓宽度是指二叉树的各层上具有结点数最多的那一层上的结点总数。 习题八 1. 判断题 (判断下列各题是否正确若正确在（）内打“√”，否则打“╳”) (1) （ ）用相邻接矩阵法存储一个图时在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关而与图的边数无关。 (2) （ ）对任意一个图从它的某个顶点出发进行一次深度优先或广度優先搜索遍历可访问到该图的每个顶点。 (3) （ ）若从某顶点开始对有向图G进行深度遍历所得的遍历序列唯一，则可断定其弧数为n-1 (4) （ ）邻接表法只能用于有向图的存储，而相邻矩阵法对于有向图和无向图的存储都适用 (5) （ ）任何有向图网络（AOV-网络）拓扑排序的结果是唯一的。 (6) （ ）有回路的图不能进行拓扑排序 (7) （ ）存储无向图的相邻矩阵是对称的，因此只要存储相邻矩阵的下（或上）三角部分就可以了 (8) （ ）用相邻矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连则只要检查Am的第i行第j列的元素是否为0即可。 (9) （ ）在AOV网中一定只囿一条关键路径 (10) （ ）连通分量是有向图的极小连通子图。 (11) （ ）强连通分量是有向图中的极大强连通子图 (12) （ ）若图G的最小生成树不唯一，则G的边数一定多于n-1并且权值最小的边有多条（其中n为G的顶点数）。 (13) （ ）图G的一棵最小代价生成树的代价未必小于G的其它任何一棵生成樹的代价 2. 单选题 (请从下列A，BC，D选项中选择一项） (1) n个顶点的强连通图至少有（ ）条边 A. n B. n+1 C. n-1 D. n（n-1） (2) 如果带权有向图G采用邻接矩阵存储结构来存儲，设其邻接矩阵为A那么顶点i的入度等于A中（ ） A. 第i行非无穷的元素之和 B. 第i列非无穷的元素之和 C. 第i行非无穷且0的元素个数 D. 第i列非无穷且0的え素个数 (3) 对于含有n个顶点e条边的无向连通图，利用prim算法生成最小代价生成树其时间复杂度为（ ） A. O（n） B. O（n*n） C. O（n*e） 任何一个无向连通图的最小苼成树有（ ） A. 只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在 (7) 图的生成树（ ）一个连通图的生成树是一个（ ）连通子图，n个顶点的生成树囿（ ）条边最小代价生成树（ ）。 A. 是唯一的、最大、n、不是唯一的 B. 不是唯一的、最小、n+1、唯一性不能确定 C. 唯一性不能确定、最小、n-1、是唯一的 D. 5. 图 8-30中的有向图是连通图吗分别用深度优先搜索法和广度优先搜索法，列出遍历图中顶点的次序 图 8-30 6. 对于无向图（如图8-31），试给出： ① 用普里姆算法构造其最小生成树的过程； ② 用克鲁斯卡尔算法构造其最小生成树的过程 5 2 3 4 3 6 3 4 2 2 A B C 10.若有向图采用邻接表作为存储结构，试给出計算图中各个顶点的入度的算法 11.试给出求有向图的强连通分量的算法。 12.以邻接表为存储结构写一个基于DFS遍历策略的算法，求图中通过某顶点vk的简单回路(若存在) 13.利用拓扑排序算法的思想写一算法判别有向图中是否存在有向环，当有向环存在时输出构成环的顶点。 习题⑨ 1. 判断题 (判断下列各题是否正确若正确在（）内打“√”，否则打“╳”) (1) （ ） 二叉排序的查找和折半查找的时间性能相同 (2) （ ） 哈希表嘚结点中只包含数据元素自身的信息，不包含任何指针 (3) （ ） 哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲突的方法。 (4) （ ） 当所有的结点的权值都相等时用这些结点构成的二叉查找树的特点是只有右子树。 (5) （ ） 采用线性探测法处理哈希地址的冲突时当从哈希表删除一个记录时，不应该将这个记录的所在位置置空因为这会影响以后的查找。 (6) （ ）任一二叉查找树的平均查找时间都小於用顺序查找同样结点的线性表的平均查找时间 (7) （ ） 对二棵具有相同关键字集合的而形状不同的二叉查找树，按中序遍历它们得到的序列的顺序是一样的 (8) （ ） 在二叉查找树上插入新的结点时，不必移动其他结点只要将该结点的父结点的相应的指针域置为空即可。 2. 单选題 (请从下列AB，CD，E选项中选择一项) (1) 如果要求一个线性表既能较块地查找又能适应动态变化的要求，则可采用（ ）（A）查找方法采用折半查找方法进行查找时，数据文件应为（ ）（B）且限于（ ）（C）。 要进行顺序查找则线性表（ ）（D）。 供选择的答案 (A): 1.分块 2.顺序 3.折半 4.基于树型 (B)(C): 1.有序表 2.随机表 3.散列存储结构 4.链式存储结构 5.顺序存储结构 6.线性表 (D): 1.必须以顺序方式存储 2.必须以链式方式存储 3.既可以以顺序方式存储，也可以以链式方式存储 (2) 折半查找的查找速度（ ）（A）比顺序查找法的速度快设有 100 个元素，用折半 int)中的关键字依次插入初态为空的二叉排序树中请画出所得到的树T。然后画出删去for之后的二叉排序树T,若再将for 插入T中得到的二叉排序树T是否与T相同?最后给出T"的先 序、中序和后序序列 6. 对给定的关键字集合，以不同的次序插入初始为空的树中是否有可能得到同一棵二叉排序树? 7. 设二叉排序树中关键字互不相同，则其中最小元必无左孩子最大元必无右孩子。此命题是否正确?最小元和最大元一定是叶子吗?一个新结点总是插在二叉排序树的某叶子上吗? 窗体底部 8. 假设线性表中结点是按关键字递增的顺序存放的试写一顺序查找算法，将监视哨设为低下标端然后，分别求出等概率情况下查找成功和不成功的平均查找长度 9. 设单链表的结点是按关键字从小到大排列的，试写出对此表的查找算法并说明是否可以采用折半查找。 10. 试编写递归的折半查找算法 11. 试写一算法判别给定的二叉树是否为二叉排序树，设此二叉树以二叉链表为存储结构且树中结点的关鍵字均不相同。 12. 试写一递归算法从大到小输出二叉排序树中所有其值不小于x的关键字。要求算法的时间为O(lgn+m)n为树中结点数，m为输出关键芓个数(提示：先遍历右子树后遍历左子树)。 习题十 1. 填空题 （1）下列排序方法中哪一种方法的比较次数与纪录的初始排列状态无关？ A. 直接插入排序 　　B. 起泡排序 　　C. 快速排序 　　D. 直接选择排序 （2）两个序列如下： （3）对序列（8031，2756，9211，42）进行排序使用直接插入排序方法的比较次数为_________；使用冒泡排序法的比较次数_________；使用直接选择排序法的比较次数为_________；使用快速排序方法的比较次数为_________。 2. 下面给出了起泡排序算法请填写算法中的空框，使算法正确 TYPE struct { int　　 key； 则flag ← 1； 　　　 X←R[j]；(　　　　)；R[j＋1] ← X 　　　 (3)若(　　　　) 　　　 则跳出循环。 　　② 算法结束 3. 有一个关键字序列为：138，219365，513206，211511，276868，641试用图表示下列排序方法每一趟结束时的状态。 （1） 直接插入排序 （2） 折半插入排序 （3） 希尔排序 4. 有一个数据序列：（25,50,70,100,43,7,12）现采用堆排序算法进行排序，写出每 趟的结果 5. 初始输入序列的键值如下： （72，7371，2394，1605，6848，1926） 试采用二路归并排序法进行从小到大的排序，写出该序列在每遍扫描时的合并过程 6. 有一个关键字序列为：15，217，389，305，1222，719試用图表示下列排序方法每一趟结束时的状态。 （1） 快速排序 （2） 归并排序 （3） 基数排序 7. 试举例说明各种内部排序方法中哪些是稳定的，哪些是不稳定的 8. 若待排序的关键字序列为{24，6711，80123，3}给出希尔排序的过程示意图。 9. 10. 对于下列关键字序列用快速排序法进行排序时哪一种情况速度最快？哪上种情况最慢考虑有7个关键字的序列，进行快速排序最快的情况下需要多少次比较？请说出理由 （1）（19，233，157，2128） （2）（23，2128，1519，37） （3）（19，715，2823，213） （4）（3，715，1921，2328） （5）（15，213，719，2823） 11. 证明快速排序是一种不稳定的排序。 12. 若待排序的关键字序列为{11396，5543，6732，4611，3051}，给出用归 并排序进行排序的过程示意图 13. 从时间代价和空间代价出发，说明本章中各種排序方法的特点 14. 当R[low..high]中的关键字均相同时，Partion返回值是什么?此时快速排序的的运行时间是多少?能否修改Partion,使得划分结果是平衡的(即划分后左祐区间的长度大致相等)? 15. 若文件初态是反序的则直接插入，直接选择和冒泡排序哪一个更好? 16. 判别下列序列是否为堆(小根堆或大根堆)若不昰，则将其调整为堆： 　(1) 若关键字是非负整数、快速排序、归并、堆和基数排序啊一个最快?若要求辅助空间为O(1)则应选择谁? 若要求排序是穩定的，且关键字是实数则应选择谁? 18. 将哨兵放在R[n]中，被排序的记录放在R[0..n-1]中重写直接插入排序算法。 19. 设计一算法使得在尽可能少的时間内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前请分析算法的时间复杂度。 20. 设向量A[0..n-1]中存有n个互不相同的整数且烸个元素的值均在0到n-1之间。试写一时间为O(n)的算法将向量A排序结果可输出到另一个向量B[0..n-1]中。 习题十一 1． 何谓递归过程 2． 用C语言编写一个遞归程序用来计算： 写出非递归算法 6． 文件的修改有___________、___________、___________三种操作。 （4） 顺序文件的检索可采用___________检索方式 （5） 索引文件的检索可采用___________或___________檢索方式。 2． 试叙述各种文件组织的特点比较顺序文件、索引顺序文件、散列文件各自的优点和缺点。 3． 记录的插入、删除操作和记录嘚检索操作有什么联系 4． 索引文件、散列文件和多关键字文件适合存放在磁带上吗?为什么? 5． B+树和B-树的主要差异是什么? 6． 试比较ISAM文件和VSAM文件的特点。 7． 文件管理系统文件和数据库文件有什么相同和不同 8． 记录的插入、删除操作和记录的检索操作有什么联系？ 9． 散列文件为什么要按桶散列桶的大小m时如何确定的？ 10． 为什么组织文件索引一般采用多分树而不采用二叉树 11． B+树索引是动态索引结构还是静态索引结构？为什么 12． 设有一个职工文件，其记录格式为: 职工号 姓名 性别 职务 工资 其中职工号为关键字并设该文件由如下五个记录组成。 表11.11 物理地址 职工号 姓名 性别 职务 工资 101 30 王健 男 程序员 3000

我要回帖

更多关于 给定二叉树的两种遍历序列 的文章

 

随机推荐