Question

数据结构计算题目

1．设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。
2．设给定一个权值集合W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。
3．设一组初始记录关键字序列为(19，21，16，5，18，23)，要求给出以19为基准的一趟快速排序结果以及第2趟直接选择排序后的结果。
4.设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。

Answer 1

1.前序：A B D E C
中序：D B E A C
后序：D E B C A

2.（3+5）*3+（7+9+11）*2=82

3.快速排序：18 5 16 19 21 23
直接选择：5 16 18 19 21 23

4. 45
40 80
22 48
78
一颗树上的大小顺序：左孩子小于根节点小于右孩子