数据结构习题课8ppt课件.ppt

数据结构习题第8章 第8章作业 8 48 7 8 8 8 9 8 108 138 22 8 23 8 4 设有关键词为A B C和D 按照不同的输入顺序 共可能组成多少种不同的二叉查找树 请画出其中高度较小的6种 参考答案 以A为根的BST共5种B为第2个元素 2种C为第2个元素 1种 高度为2 D为第2个元素 2种以B为根的BST共2种 高度为2 以C为根的BST共2种 高度为2 以D为根的BST共5种 类似A 一共有14种 高度为2的有6种 为3的有8种 8 7 画出对长度为10的有序表进行折半查找的判定树 并求其等概率时查找成功的平均查找长度 参考答案 ASLsucc 1 2 2 3 4 4 3 10 29 10ASLunsucc 5 3 6 4 11 39 11 8 8 对长度为12的有序表 a1 a2 a12 其中aia12 ai x ai 1 i 1 2 11 等情况发生的概率相等 则查找不成功的平均查找长度是多少 二叉判定树如下 ASLUNSUCC En n 1 3 3 4 10 13 49 13 参考答案 8 9 假设按下述递归方法进行顺序表的查找 若表长n 10 则进行顺序查找 否则进行折半查找 试画出对表长n 50的顺序表进行上述查找时 描述该查找的判定树 并求出在等概率情况下查找成功的平均查找长度 ASL 1 2 2 3 4 4 5 6 7 8 8 9 3 50 284 50 参考答案 8 10 已知下列关键词和它们对应的散列函数值 由此构造哈希表 用线性探测法冲突 计算平均查找长度ASL 若用拉链法解决冲突情况又如何 参考答案 线性探测法 假设散列表的长度是8 下标从0开始 查找成功ASL 1 5 3 1 7 1 7 15 7 拉链法 假设散列表长度是8 下标从0开始 查找成功ASL 1 5 2 1 2 1 7 9 7 合并拉链法 算法C 拉链法 假设散列表的长度是8 下标从0开始 查找成功ASL 1 5 2 1 2 1 7 9 7 8 13 已知序列 17 31 13 11 20 35 25 8 4 11 24 40 27 请画出该序列的二叉查找树 并分别给出下列操作后的二叉查找树 1 插入数据9 2 删除节点17 3 再删除节点13 参考答案 动态插入创建二叉查找树 17 31 13 11 20 35 25 8 4 11 24 40 27 17 17 31 13 11 20 35 25 8 4 11 24 40 27 插入数据9 删除17 再删除节点13 8 22 编写判定给定的二叉树是否是二叉查找树的算法 提示 判定二叉树是否为二叉查找树是建立在中根遍历的框架基础下 在遍历中附设一指针pre指向当前访问节点的中根直接前驱 每访问一个节点便比较前驱节点pre和此节点是否有序 若遍历结束后各节点和其中根直接前驱均满足有序 则此二叉树为二叉查找树 否则 只要有一个节点不满足 那么此二叉树就不是二叉查找树 算法BST t pre flag 使用中根遍历和pre指针判断t是否是二叉查找树 B1 特判 flag TRUE IFt NULLTHENRETURN B2 中根遍历 BST left t pre flag IF flag THENRETURN IF pre NULLANDdata pre data t THEN flag FALSE RETURN pre t BST right t pre flag C boolbst BinTreeNode t BinTreeNode 8 23 给定整型数组B 0 m 0 n 已知B中数据在每一维方向上都按从小到大的次序排列 且整型变量x在B中存在 试设计一个算法 找出一对满足B i j x的i j值 要求比较次数不超过m n 提示 本题中主要是要确定每次进行比较的对象 其中 二维数组右上角的元素是一个较为特殊的元素 可以逐次跟二维数组右上角的元素进行比较 每次比较有3种可能的结果 若相等则结束比较 若右上角的元素小于x 则可断定二维数组的最上面一行中肯定不包含x 下次比较时搜索范围即可减少一行 若右上角的元素大于x 则可断定二维数组的最右面一列中肯定不包含x 下次比较时搜索范围即可减少一列 这样 每次至少可使搜索范围减少一列或一行 最多经过m n次即可找到x 参考答案 算法Find B m n x 在B中查找x 时间复杂度O m n F1 初始化 i 0 j n F2 比较B i j 与x WHILE i 0 DO IF B i j x THENRETURNTRUE IF B i j x THENi i 1 IF B i j x THENj j 1 RETURNFALSE 1 8分 数组A中存放n个整数 0 A i 10000 1 i n 设计算法求出数组A中的第k小数 1 k n 10000 例如 若数组A中包含4个整数为1 9 4 16 则A中第2小数为4 1 给出算法的基本设计思想 2分 高效算法有额外加分 2分 2 描述算法 并要求对算法中的关键步骤给出注释 3分 3 给出算法的时间复杂性分析 1分 分析 本题方法较多 典型有三种 方法一 先排序 任意一种排序方法 输出第k大的数O nlogn 方法二 执行k步选择最小值 可以用堆优化 O k n 方法三 利用快排的分划思想O logn logn 方法四 桶排序O n 方法三 四都认为是较优的算法 参考答案 方法三 算法思想 利用快排的分划思想求第k小元素 若分划位置j k 则查找成功 若j k则在 j 1 e 这段里查找第k小位置 若j k 则在 s j 1 查找第k小位置时间复杂度 logn logn 算法描述 intsearch intk intn ints 1 e n while 1 inti s j e while i a i if k j 第1步 s 1 e n 第2步 循环做如下操作2 1分划 得到i 2 2如果k i 那么返回A i 如果k i 那么s i 1 k k i 如果k i 那么e i 1 12分 给定无向连通正权图G和G中的一个结点v 求G的支撑树T 并使其满足如下两个条件 第一 T的根为v 第二 T中v到任一顶点u的路径长度等于G中v到u的最短路径长度 要求 1 给出算法的基本设计思想 3分 2 设计图G和支撑树T的存储结构 2分 3 基于以上设计的存储结构 用算法描述语言描述算法 并要求对算法中的关键步骤给出注释 7分 1 算法设计思想 利用Dijkstra算法求该支撑树 即在用Dijkstra算法求以v作为源点的最短路的过程中 把每次确定为最短路的点和边加入到生成树T中 2 图G用邻接表存储 边的存储结构为Edge VerAd