资源描述：
《数据结构-树和二叉树复习题及答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、树和二叉树：纸质作业一、已知二叉树T逻辑结构如下图所示，请分别用顺序存储和二叉链表存储法表示此树。二、将下面的森林F=﹛T1，T2，T3﹜转换为对应的二叉树，并写出相应二叉树的先根遍历序列。三、将下列由三棵树组成的森林转换为二叉树，并写出相应二叉树的中根遍历序列NPGHJMOLIKEDFBAC四、已知树T的孩子链表存储结构如图所示，试画出此树逻辑结构，以及此树转换成的二叉树逻辑结构，并写出二叉树的后根遍历序列五、设一棵二叉树的先序序列为：ABDFCEGH中序遍历序列为：BFDAGEHC（1）画出这棵二叉树。（2）将这棵二叉树转换成对应的树（或森林）。六、给定集合{1
2、5,3,14,2,6,9,16,17}（1）构造相应的huffman树（规定：二叉树中两个结点，权值小的结点居左）（2）计算它的带权路径长度（3）写出它的huffman编码：（规定：左子树编码为0，右子树编码为1,左小右大）七、假设通信电文使用的字符集为{a,b,c,d,e,f}，各字符在电文中出现的频度分别为：0.34，0.05，0.12，0.23，0.08，0.18，试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树(要求树中左孩子节点的权值小于右孩子节点的权值，左分支表示字符“0”，右分支表示字符“1”)，然后分别写出每个字符对应的编码。八、假定教室中有
3、A、B、C、D、E五个设备，需编写一套指令集对五个设备进行自动开关控制，五个设备一天中的使用次数分别是7，5，2，4，9次。为使得指令集长度最短，请对五个设备进行编码，要求画出哈夫曼树，并写出五个设备所对应的哈夫曼编码。九、假定用于通讯的电文仅有8个字母C1，C2，…，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，试为这8个字母设计哈夫曼编码树，并写出8个字符的哈夫曼编码十、A,B,C,D,E的权值为{3,2,4,5,1}，用此权值构造哈夫曼（Huffman）树，并求此哈夫曼（Huffman）树和各个字符的哈夫曼编码（左分支为0，
4、右分支为1）纸质作业2：排序一、初始关键字序列如下：{49，38，65，97，76，13，27，49，5504}，请写出它们的希尔排序的全过程(其中d=5,3,1）二、给定的关键字序列21，22，27，78，40，05，47，69，12，99，要按升序排序，请写出采用冒泡排序法前3趟的结果，和用堆排序法选择出最大和次大关键字的结果（图）三、已知某文件的记录关键字集为{50，10，75，40，45，85，80}，写出快速排序方法进行排序的前2次划分的结果四、已知某文件的记录关键字集为{50，10，30，40，45，85，80}，要从小到大进行排序，请分别写出直接插入排
5、序的前2趟结果和直接选择排序的前3趟结果。五、设要将序列（17,8,3,25,16,1,13,19,18,4,6,24）中的关键字按升序重新排列，请给出对该序列进行冒泡排序的第一趟排序结果、及以第一个元素为枢轴的快速排序的第一次划分的结果。纸质作业3：查找一、设哈希（Hash）表的地址范围为0～13，哈希函数为：H（K）＝KMOD13。K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：（23，24，32，4，31，30，46，47）造出Hash表，试回答下列问题：（1）画出哈希表的示意图；（2）若查找关键字30，需要依次与哪些关键字进行比较？（3）若查找关键
6、字14，需要依次与哪些关键字比较？假定每个关键字的查找概率相等，求查找成功时的平均查找长度。二、请用序列（45，24，53，12，37，93）建立一棵二叉排序树，画出该树，并求在等概率情况下，查找成功的平均查找长度。三、选取哈希函数H(key)＝keyMod11，用线性探测再散列开放定址法解决冲突。试在0～10的散列地址空间内对关键字序列{19、11、31、23、17、27、41、13、91、61}构造哈希表，并计算在等概率下成功查找的平均查找长度。四、设有一组关键字{9,1,23,14,55,20,84,27}，采用哈希函数：H（key）=keymod7，表长为1
7、0，用开放地址法的线性探测再散列方法解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。五、设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）=KMOD16，K为关键字，用线性探测再散列法处理冲突，输入关键字序列：{10，24，32，17，31，30，46，47，40，63，49}造出哈希表，试回答下列问题：（1）画出哈希表示意图；（2）若查找关键字63，需要依次与哪些关键字比较?（3）若查找关键字60，需要依次与哪些关键字比较?（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。六、对于序列：12，16，23，34，
