- —四川最大高校综合门户网
2001年攻读硕士学位研究生入学考试试题 学科，专业：…………研究方向：………….考试科目：数据结构及程序设计 算法请用类 PASCAL或类C 语言编写，程序请用PASCAL 或类C语言编写 一．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点（注意不设头指针
2001年攻读硕士学位研究生入学考试试题
学科，专业：…………研究方向：………….考试科目：数据结构及程序设计
算法请用类 PASCAL或类C 语言编写，程序请用PASCAL 或类C语言编写
一．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点（注意不设头指针），试编写相应的置空队列，入队列和出队列的算法。（10分）
二．假设有两个按元素值递增有序排列的线性表A和B，A和B均一单链表表示，请编写算法将表A，B归并成一按元素值递减有序排列的线性表C，并要求利用原表（即表A和表B）结点空间存放表C。（10分）
三．1．何谓排序方法的稳定性？（3分）
2．下列排序方法哪些是稳定的哪些是不稳定的？（4分）
3．对不稳定的方法举实例说明之。（8分）
直接插入排序，希尔排序，快速排序，归并排序
四．试编写归并排序算法。（10分）
五．有下列关键字：（10分）
15，23，29，31，47，66，74，85，90，98，102
1．画出描述折半查找过程的判别树。
2．对含关键字的有序表，采用折半查找，在查找成功时，关键字比较次数至多是多少？在查找不成功时，关键字比较次数至多是多少？
六．编写一算法，判别以邻接表方式存储的有向图中是否存在顶点Vi到顶点Vj的路径。（10分）
七．1．何谓二叉排序树？（5分）
2．把数据组织为二叉排序树有和优点？（5分）
3．设有一组数据a1,a2,a3,……,an,试编写一程序把这n个数据放入一二叉排序树中，要求该树尽可能平衡（二叉排序树用链表表示，算法输出为该二叉排序树的根结点）。（10分）
八．编写一算法，输出一集合的幂集。（15分）
