数据结构操作题

1、实验一线性表操作一、实验目的熟悉并掌握线性表的逻辑结构、物理结构。熟悉并掌握顺序表的存储结构、基本操作和具体的函数定义。熟悉 VC+程序的基本结构，掌握程序中的用户头文件、实现文件和主文件之间的相互关系及各自的作用。熟悉 VC+操作环境的使用以及多文件的输入、编辑、调试和运行的全过程。二、实验要求实验之前认真准备，编写好源程序。实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。不断积累程序的调试方法。三、实验内容基本题:对元素类型为整型的顺序存储的线性表进行插入、删除和查找操作。加强、提高题：2、编写一个求解 Josephus问题的函数。用整数序列1, 2, 3, , n

2、 表示顺序围坐在圆桌周围的人。然后使用n = 9, s = 1, m = 5 ，以及 n = 9, s = 1, m = 0 ，或者 n9, s = 1, m = 10 作为输入数据，检查你的程序的正确性和健壮性。最后分析所完成算法的时间复杂度。定义 JosephusCircle 类，其中含完成初始化、报数出圈成员函数、输出显示等方法。（可以选做其中之一）加强题：1、采用数组作为求解过程中使用的数据结构。提高题：2、采用循环链表作为求解过程中使用的数据结构。运行时允许指定任意 n、s、m数值，直至输入 n = 0 退出程序。实验二栈、队列的实现、递归应用一、实验目的熟悉栈、队列这种特殊线性结构

3、的特性熟练掌握栈、队列在顺序存储结构和链表存储结构下的基本操作。二、实验要求实验之前认真准备，编写好源程序。实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。不断积累程序的调试方法。三、实验内容基本题（必做）：分别就栈的顺序存储结构和链式存储结构实现栈的各种基本操作。、假设以带头结点的循环链表表示队列，并且只设一个指针指向对尾结点，不设头指针，试设计相应的置队空、入队和出队的程序。加强题：1、设线性表 A中有 n 个字符，试设计程序判断字符串是否中心对称，例如 xyzyx 和 xyzzyx都是中心对称的字符串。提高题：1、试编写程序：将中缀表达式计算转换成后缀表达式。后缀

4、表达式的计算实现中的算法，要考虑实际运算时，后缀表达式中相邻操作数的界定。实验三树、图的实现与应用一、实验目的理解树结构的逻辑特性熟练掌握二叉树的逻辑结构特性及各种存储方法熟练掌握二插树的各种基本操作，尤其是三种遍历熟练掌握图的存储结构掌握图的邻接矩阵和邻接表表示分别进行深度和广度优先搜索遍历的算法。了解图的最小生成树算法。二、实验要求实验之前认真准备，编写好源程序。实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。不断积累程序的调试方法。三、实验内容基本题1、给定一棵用链表表示的二叉树，其根指针为root ，试写出求二叉树结点数目。2、对图的邻接矩阵和邻接表表示分别进行

5、深度优先搜索遍历算法的实现。加强题1、试写出中序遍历二叉树的递归和非递归程序并调试。2、写出中序线索二叉树的中序遍历程序并调试。提高题1、实现霍夫曼编、解码（1）输入一系列字符及其出现频率并以此构造霍夫曼树进行编码并输出码表，另输入一段文字，对其进行霍夫曼编码。例：CASTCASTSATATATASA（2）在 1 中已构成的霍夫曼树的基础上，输入一段 01 编码，要求输出其解码的原文。例：、校园导游咨询。要求：（1）设计一个校园的平面图，所含景点不少于8 个。以图中的顶点表示校内各景点，存放景点名称、代号、简介等信息。以边表示路径，存放路径长度等相关信息。（2）为来访客人图中任意景点相关信息的

6、查询。（3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短路。实验四搜索一、实验目的熟练掌握顺序搜索、折半搜索和索引搜索等基本搜索算法，熟悉这些算法适合在何种存储结构下实现熟练掌握二叉排序树的特性、建立方法以及动态搜索算法熟练掌握散列表的特点及构造方法二、实验要求实验之前认真准备，编写好源程序。实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。不断积累程序的调试方法。三、实验内容基本题1、实现基于有序顺序表的折半搜索。2、设单链表的结点是按关键字的值从小到大排列的，试写出对此表的搜索程序并调试。加强题1、若输入 12000 个不同的整数，其值介于0

7、 和 19999之间，用散列法将这些数进行存储，散列函数为 H(n)=n/2，请设计实现程序并调试。提高题1、建立二叉搜索树、实现其删除算法。要求：实现后分析其时间复杂度实验五排序一、实验目的熟练掌握各种内排序方法，深刻理解排序算法及其执行过程学会分析各种内排序算法的性能了解各种排序方法的优缺点，对于实际问题能够选择一种较好的排序方案二、实验要求实验之前认真准备，编写好源程序。实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。不断积累程序的调试方法。三、实验内容基本题1、希尔排序算法的实现。2、快速排序算法的实现。加强题（可选择其中之一）1、堆排序算法的实现2、给出 n 个学生的考试成绩表，成绩表由姓名和分数组成，试设计一个程序