简述创建线索二叉树的目的，以及建立线索二叉树的思路。（4分）

给定关键字序列T＝（11,13,12,14,5,6,8,7,9,10），采用快速排序算法，以第一个元素为枢轴，对该序列由小到大排序，并写出具体排序过程，要求给出每趟排序后的中间结果。（3分）

对于给定11个数据元素的有序表T＝｛2,3,10,15,20,25,28,29,30,35,40｝采用折半查找，请回答以下问题。（本题共三小题，前两小题各2分，第三小题4分，共计8分）

（1）若查找给定值为20的元素，将依次与表中哪些元素比较？

（2）若查找给定值为26的元素，将依次与哪些元素比较？

（3）假设查找表中每个元素的概率相同，求查找成功时的平均查找长度和查找不成功时的平均查找长度

设有一段正文由字符集｛A. B，C，D. E. F）组成，正文长度为100个字符，其中每个字符在正文中出现的次数分别为17,12,5,28,35,3。若采用Huffman编码对这段正文进行压缩存储，请完成如下问题。（本题共四小题，每小题各2分，共计8分）

（1）根据上述背景，构造出Huffman树（规定权值较小的结点为左子树）。

（2）给出每个字符的Huffiman编码。

（3）若有某一段正文的二进制编码序列为01101010110011，请将它翻译成所对应的正文。

（4）计算按Huffman 编码压缩存储这段正文共需要多少个字节。

已知一个有向网G的带权邻接矩阵如下所示，回答以下问题。（本题共两小题，第一小题2分，第二小题5分，共计7分）

(1) 画出该带权有向图（假设顶点编号为VO，VI，V2，V3，V4，V5）.

(2) 使用Dijkstra（迪杰斯特拉）算法求出从顶点VO到其余各顶点的最短路径，并写出过程。

已知一个无向图如下图2所示，分别用Prim和Kruskal 算法生成最小生成树，要求画出构造过程（设Prim算法以顶点V1为起点）。（10分）