数据结构复习.docx

1、数据结构复习1.二叉树T, 前序是 ABDEFGHCILJKM,中序是 DFEGBHAILCKMJ，画树。2. 二叉树T, 前序是ABCDEFGHIJKL,中序是BDCEAGFIKJLH，画树3 有向图如下:（1）每个顶点的出度和入度；（2）邻接矩阵；（3）邻接表；4. 9个数：56，78，24，57，22，19，68，37，54 完成下列各种排序的结果 1）归并排序：写出每一次归并排序的结果。2）堆排序：建堆，写出第一次排序后的结果.5. 10个数：36，58，44，67，29，56，68，47，59 完成下列各种排序的结果 1）归并排序：写出每一次归并排序的结果。2）堆排序：建堆，写出第一

2、次排序后的结果.6. 哈希表长16, 哈希函数是H(key)=key MOD 13，利用线性再探测技术解决冲突. 请你们填写以下数据：11,19,18,26,22,25,45,23，78，9，51，48，16，80写出过程，并计算ASL（平均查找长度）0123456789101112131415哈希表长13, 哈希函数是H(key)=key MOD 11，利用线性再探测技术解决冲突. 请你们填写以下数据：12 ， 23 ， 45 ， 57 ， 20 ， 03 ， 78 ， 31 ， 15 ， 36写出过程，并计算ASL（平均查找长度）01234567891011121314157. 把树转换成二叉树。 8. 画出二叉排序树: （1）29、33、18、19、32、15、70、36、34，12,45,43，80,13,3,7（2）23,44,24,12,34,56,54,33,11,19,37,58,65,31,30,55,459. 生成平衡二叉排序树: （1）29、33、18、19、32、15、46、36、34，12,45,43，80,13,3,11,67,43（2）24,41,22,12,34,56,54,33,10,19,37,58,65,31,30,55,45,47,5010. 画出最小生成树。 11. 使用Floyd 算法求出任意两点间的最短路径