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

《数据结构-期末复习习题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.假设已知一棵二叉树的先序序列：ABDGJEHCFIKL；中序序列：DJGBEHACKILF，要求：（1）画出该二叉树（简要写明分析过程）：（2）写出该二叉树的后序遍历序列：2.一棵二叉树如下面的图所示，要求：（1）写出对此二叉树进行中序遍历时得到的结点序列。（2）画出由此二叉树转换得到的森林。3.给定一组权值（5，9，11，2，7，16），试设计相应的Huffman树,并计算所构造的Huffman树的带权路径长度。4.设矩阵A是一个n阶对称矩阵，对之压缩存储，将其上三角部分（包括主对角线上的元素）以列序为主序依次存放在

2、一维数组B[1..n(n+1)/2]中，对下三角部分中任一元素aij(i≥j)，在数组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）），则该广义表的

3、深度是多少?表尾是多少?