第一题（15分）

　　试用PASCAL语言编写一个将单链表颠倒的过程说明。

　　第二题（15分）

　　（1）已知某二叉树的前序遍历次序为：ABDCEFGH；中序遍历次序为：DBAECFHG.画出这棵二叉树。

　　（2）已知一棵一般树如图，将这棵树转换成二叉树，试画出转换后的二叉树图形。

　　第三题（15分）

　　设二叉树已按通常的链接结构存贮。指针变量root指向树根。每个结点的类型为：

　　type node=record data：integer；

　　left，right：pointer；

　　lfag，rflag：boolean

　　end；

　　其中，left和right分别为指向它的左右子树的指针，在存贮时已有值。试用PASCAL语言编写一个过程说明，将这棵二叉树改变为中序穿线结构存贮。

　　第四题（15分）

　　（1）试写出下面（左）有向图的三种拓扑排序次序。

　　（2）画出下面（右）图一个最小代价生成数。

　　第五题（15分）

　　用文字叙述快速排序的算法思想（不必写程序）。该算法最好和最坏时的时间、空间复杂度是什么？何时发生最坏的情况？

　　第六题（15分）

　　设排序二叉树已按通常的链接结构存贮，指针变量root指向树根，结点的类型如下：

　　type pointer=node

　　node=record key；integer；

　　left，right：pointer

　　end；

　　试用PASCAL语言编写一个查找某关键字的过程说明。

　　第七题（10分）

　　设G=（v，E）是一个有向图，每条边上有一个表示距离的正权值。试写出一个算法，计算从某固定源点（V1）到其它各顶点的最短路程（DIJKSTRA算法），并且说明该算法是正确的。