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

《数据结构上机实验题目-2015》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》上机实验题目（共8次，每次上机4小时）第一阶段（线性部分）《数据结构》第1上机题（线性表练习）1．编程实现书P19ADTList基本操作12个：（1）用顺序存储结构实现；（2）用链式存储结构实现；2．编程实现顺序表和单链表的就地逆置（习题集P182.212.22）。《数据结构》第2上机题（线性表练习）1．分别用顺序结构和单链表结构编程实现下列功能：假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合，现要求在A的空间上构成一个新线性表C，其元素为A和B元素的交集，且表C中的元素也是依值递增有序排列（习题集P182.252.

2、26）；2．设有一个双向循环链表，每个结点中除有pre，data和next三个域外，还增设了一个访问频度域freq。在链表被起作用前，频度域freq的值均初始化为零，而当对链表进行一次LOCATE(L,x)的操作之后，被访问的结点（即元素值等于x的节点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编程实现之（习题集P192.38）。《数据结构》第3次上机题（栈与队列练习）1．编程实现书P45ADTStack基本操作9个，用顺序存储结构实现；2．编程

3、实现书P59ADTQueue基本操作9个，用链式存储结构实现；3．试利用循环队列编写求k阶斐波那契序列中前n+1项的算法。要求满足：,其中max为某个约定常数。(注意：本题所用循环队列的容量仅为k,则在算法执行结束时，留在循环队列中的元素应是所求k阶斐波那契序列中的最后k项)（习题集P263.32）；4.利用栈操作实现八皇后问题求解(选做题)。第一阶段总结第二阶段（树与图部分）《数据结构》第4次上机题目(二叉树练习)1.编程实现书P121ADTBinaryTree基本操作20个，用二叉链表结构实现；2.二叉树的先序、中序、后序遍历递归（非递归

4、选做）方法，层次遍历。《数据结构》第5次上机题目(二叉树图练习)1．编程实现书P156ADTGraph基本操作13个，用邻接矩阵存储结构实现；2.哈夫曼树的建立。《数据结构》第6次上机题目(图练习)1.图的深度优先和广度优先遍历；2．拓扑排序；3.关键路径练习(选做题)；4．最短路径练习(选做题)。第二阶段总结第三阶段（查找与排序部分）《数据结构》第7次上机题目(查找练习)1.哈希表设计(习题集P166.6.2)；2.编写程序，判断一棵二叉树是否为二叉排序树（习题集P589.31)；2.平衡二叉树练习(习题集P166.6.4题)(选做题)。《

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