数据结构|综合问题.doc

综合问题1.将一组记录的关键字序列设置为（49、83、59、41、43、47），使用堆排序算法完成以下操作: （需要一个小的根堆，并绘制（中间过程）（1）由二叉树6描述两个元素的初始堆（2）是一个二叉树，描述了5个元素的堆和4个元素的堆，这些堆在将栈顶元素一一取整之后进行了调整. 2.有一个没有头节点的单链表，头指针是头，节点类型是NODE，每个节点接下来包含一个数据字段数据和一个指针字段，链表有两个节点，p指向第二个对于每个节点（尾节点），请根据以下要求编写相应的语句（不需要完整的程序，（1），（2），（3），（4）是连续的过程）. （1）创建一个新节点，使指针s指向该节点，并将该节点的数据成员数据分配为值1. （2）将节点插入链接列表的末尾并释放指针s（ 3）删除链接列表的第一项节点（4）知道p1指向另一个新节点，并将其插入p指向的节点与尾节点（1）之间s =（NODE *）malloc（sizeof （NODE））; s-> data = 1; （2）p-> next = s; s-> next = NULL; free（s）（3）head = head-> next; （4）p1-> next = p-> next; p-> next = p1; 4.（1）设置顺序{10，12，15，19，22，25，100，130，150，200}，以将上述搜索的决策树画成两半（按顺序，其中的元素用作树的节点）（2）要成功找到100个元素，需要将元素进行多少次比较？为了找到9，元素比较多少次才知道搜索失败？ 3.顺序表为（13，19，25，36，48，51，63，84，91，116，135，200），元素的下标顺序为1,2，...，12

（1）在成功查找元素4次之后说要比较哪些元素（2）绘制与上述有序表的半搜索对应的决策树（使用树节点的下标）表示形式（3）假设您要查找元素5，需要进行多少次元素比较才能确定您找不到5. （1）对于给定的数字序列{7,16,4,8,20 ，9,6,18,5}，依次获取序列中的数据，以构建二叉排序树. （2）对于给定的搜索值，简要描述搜索二进制排序树的算法步骤. 在上述二叉树中找到元素20需要进行多少元素比较？ （2）首先，将给定值与根进行比较对于节点比较，如果它们相等，则搜索成功，否则，如果它们小于根节点，则它们将继续在左侧子树中搜索，如果大于根节点时，它们将在右侧的子树中搜索. 6.（1）有一个查询表{5,14,2,6,18,7,4,16,3}，表中的数据又被取出来构造一个二进制排序树. （2）解释如何从序列的二进制排序树中获得相应序列的排序结果，并将中阶遍历的结果提供给上述二进制排序. （2）中阶遍历中阶2、3、4、5、6、7、14、16、181. （1）已知二叉树的后阶遍历序列是debca，并且中阶遍历序列为dbeac. 在二叉树（2）中，如果上述二叉树的每个节点的字符分别表示不同的整数（不相等），而该树恰好是二叉排序树，则尝试给出a，b，c ，d，e（3）的大小关系给出了树（1）（2）d 二叉排序树 堆，16，32，57，52}构建到堆（小根堆）中，绘制相应的完整二叉树（不需要中间过程）（ 2）写入通过对与上述堆相对应的完整二叉树执行中阶遍历而获得的序列（2）102、52、42、82、16、67、32、576. （1）创建一个给定权重值为1，2，12，12，13，20，25的霍夫曼树作为叶子节点（2）如果霍夫曼树有n个非叶节点，则该树有多少个节点