数据结构-期末复习习题.doc

【精品文档】如有侵权，请联系网站删除，仅供学习与交流数据结构-期末复习习题.精品文档.1. 假设已知一棵二叉树的先序序列：ABDGJEHCFIKL；中序序列：DJGBEHACKILF，要求：（1）画出该二叉树（简要写明分析过程）：（2）写出该二叉树的后序遍历序列：2. 一棵二叉树如下面的图所示，要求：（1）写出对此二叉树进行中序遍历时得到的结点序列。（2）画出由此二叉树转换得到的森林。3. 给定一组权值（5，9，11，2，7，16），试设计相应的Huffman树, 并计算所构造的Huffman树的带权路径长度。4.设矩阵A是一个n阶对称矩阵，对之压缩存储，将其上三角部分（包括主对角线上的元素）以列序为主序依次存放在一维数组B1.n(n+1)/2中，对下三角部分中任一元素aij (ij)，在数组B的下标位置k的值是?。5. 若对如下的二叉树进行中序线索化，则结点x的左、右线索指向的结点分别是?bdxeac6.判定一个循环队列 QU（最多元素为 m0）为满队列的条件是?7.在一个单链表中，已知 q 所指结点是 p 所指结点的前驱结点，若在 q 和 p 之间插入s 结点，则执行的序列是?8.从一个具有n个结点的单链表中查找其值等于 x 结点时，在查找成功的情况下，需平均比较多少个结点? 9.一个广义表为（a，（a，b），d，e，（i，j），k），则该广义表的深度是多少?表尾是多少?