数据结构上机实验题目-2015

《数据结构》上机实验题目 （共8次，每次上机4小时）

第一阶段（线性部分）

《数据结构》第1上机题 （线性表练习） 1．编程实现书P19 ADT List 基本操作12个：

（1） 用顺序存储结构实现； （2）用链式存储结构实现； 2．编程实现顺序表和单链表的就地逆置（习题集P18 2.21 2.22）。

《数据结构》第2上机题 （线性表练习）

1．分别用顺序结构和单链表结构编程实现下列功能：假设以两个元素依值递增有序排列的线性表A和B 分别表示两个集合，现要求在A的空间上构成一个新线性表C，其元素为A和B元素的交集，且表C中的元素也是依值递增有序排列（习题集P18 2.25 2.26）；

2．设有一个双向循环链表，每个结点中除有pre，data和next三个域外，还增设了一个访问频度域freq。在链表被起作用前，频度域freq的值均初始化为零，而当对链表进行一次LOCATE(L,x)的操作之后，被访问的结点（即元素值等于x的节点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编程实现之（习题集P19 2.38）。

《数据结构》 第3次上机题（栈与队列练习）

1．编程实现书P45 ADT Stack 基本操作9个，用顺序存储结构实现； 2．编程实现书P59 ADT Queue 基本操作9个，用链式存储结构实现； 3．试利用循环队列编写求k阶斐波那契序列中前n+1项的算法。要求满足：

fn?max 并且 fn?1?max, 其中max为某个约定常数。 (注意：本题所用循

环队列的容量仅为k, 则在算法执行结束时，留在循环队列中的元素应是所求k阶斐波那契序列中的最后k项) （习题集P26 3.32）； 4. 利用栈操作实现八皇后问题求解 (选做题) 。

第一阶段总结

第二阶段（树与图部分）

《数据结构》 第4次上机题目 (二叉树练习 )

1. 编程实现书P121 ADT BinaryTree 基本操作20个，用二叉链表结构实现； 2. 二叉树的先序、中序、后序遍历递归（非递归选做）方法，层次遍历。

《数据结构》 第5次上机题目 ( 二叉树 图 练习 )

1．编程实现书P156 ADT Graph 基本操作13个，用邻接矩阵存储结构实现； 2. 哈夫曼树的建立。

《数据结构》 第6次上机题目 ( 图 练习 ) 1. 图的深度优先和广度优先遍历； 2．拓扑排序；

3. 关键路径练习(选做题)；

4．最短路径练习(选做题)。

第二阶段总结

第三阶段（查找与排序部分）

《数据结构》 第7次上机题目 ( 查找 练习 ) 1. 哈希表设计 ( 习题集 P166. 6.2 )；

2. 编写程序，判断一棵二叉树是否为二叉排序树（习题集 P58 9.31 )； 2. 平衡二叉树练习 ( 习题集 P166. 6.4 题) (选做题) 。

《数据结构》 第8次上机题目 ( 排序 练习 ) 1．实现插入、交换、选择、归并等简单排序算法； 2．实现快速排序算法； 3．实现堆排序算法；

4．实现基数排序算法 (选做题)。

第三阶段总结