数据结构实训项目卡.

1、数据结构实训项目卡数学与计算机科学系Department of Mathematics and Computer Science实 训 项 目 卡数学与计算机科学系 计算机实验室 计算机机房 分室实验序号1实验名称数据结构实现基础实验类别基础课程名称数据结构实验类型验证性实验者类别本科计划学时2实验要求必做实验组数81每组人数1实 验内 容1、复习数据结构的前导知识C语言中循环、数组、递归函数和链表等知识点的应用。2、掌握指针类型、结构体类型等数据类型的使用。3、结合实际问题，培养学生算法描述的能力，加强对算法特性的理解。具体题目：实验案例1：模拟简单计算器的工作。假设计算器只能进行加减乘除运

2、算，运算数和结果都是整数，4种运算符的优先级相同，按从左到右的顺序计算。实验案例2：递增链表的插入。给定一个递增整数序列和某个整数M，构造出次递增序列对应的链表，并创建以M为值的新结点且插入到链表中，使其结果序列依然保持递增顺序。名 称型 号数 量仪器设备PC机VC+6.0联想8181低值耐用品名 称 及 消 耗 额备 注消耗材料实验室主任: 填卡人: 万厚冲 填卡日期:2012.9.10实 训 项 目 卡数学与计算机科学系 计算机实验室 计算机机房 分室实验序号2实验名称单链表的插入和删除实验类别基础课程名称数据结构实验类型验证性实验者类别本科计划学时2实验要求必做实验组数81每组人数1实

3、验内 容1、掌握线性表的链式存储结构。2、熟练掌握链表的基本操作。3、结合实际问题，培养学生算法描述的能力，加强对算法特性的理解。具体题目：实验案例：完成对单链表的插入和删除，单链表的数据域为字符串，插入时不允许重复的字符串插入表中；删除时是根据输入的字符串，先找到相应的结点，后删除之。（1）输入的形式和输入值的范围：输入的字符串可以含有空格，以回车键结束。如果直接按回车键表示建立链表结束。输入的字符串最大长度默认为10，用户可以修改头文件改变此长度。（2）输出的形式：单链表的输出是每个字符串占一行。当插入重复的字符串到表中时，有信息提示，否则输出插入后的单链表：当根据输入的字符串删除时，如果

4、没有找到相应的结点，有信息提示，否则输出删除后的单链表。（3）程序所能达到的功能：能够根据要求正确的实现插入和删除功能。名 称型 号数 量仪器设备PC机VC+6.0联想8181低值耐用品名 称 及 消 耗 额备 注消耗材料实验室主任: 填卡人: 万厚冲 填卡日期: 2012.9.10实 训 项 目 卡数学与计算机科学系 计算机实验室 计算机机房 分室实验序号3实验名称栈和队列实验类别基础课程名称数据结构实验类型验证性实验者类别本科计划学时2实验要求必做实验组数81每组人数1实 验内 容1、熟练掌握堆栈的基本操作。2、熟练掌握队列的基本操作。3、结合实际问题，培养学生算法描述的能力，加强对算法特

5、性的理解。具体题目：实验案例1：数制转换。本实验采用顺序表作为栈的的存储结构，完成对数制的转换。（1）输入的形式和输入值的范围：输入任意一个非负十进制整数，范围在-3276832767之间。（2）输出的形式：输入与之等值的八进制数。（3）程序所能达到的功能：能够根据要求正确的实现十进制整数与八进制整数之间的转换，并由此加深对栈后进先出特点的认识与理解。实验案例2：银行业务队列简单模拟。设某银行有A、B两个业务窗口，且处理业务的速度不一样，其中A窗口处理速度是B窗口的2倍即当A窗口每处理完2个顾客时，B窗口处理完1个顾客。给定到达银行的顾客序列，请按业务完成的顺序输出顾客序列。假定不考虑顾客先后

6、达到的时间间隔，并且当不同窗口同时处理完2个顾客时，A窗口顾客优先输出。名 称型 号数 量仪器设备PC机VC+6.0联想8181低值耐用品名 称 及 消 耗 额备 注消耗材料实验室主任: 填卡人: 万厚冲 填卡日期: 2012.9.10实 训 项 目 卡数学与计算机科学系 计算机实验室 计算机机房 分室实验序号4实验名称二叉树的操作实验类别基础课程名称数据结构实验类型验证性实验者类别本科计划学时2实验要求必做实验组数81每组人数1实 验内 容1、熟练掌握二叉树的存储结构。2、熟练掌握二叉树的遍历及其应用。3、结合实际问题，培养学生算法描述的能力，加强对算法特性的理解。具体题目：实验案例1：还原

7、二叉树。给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。（1）输入说明：输入第1行给出正整数N（N50），为树中结点总数。随后2行先后给出先序和中序遍历序列，均为长度为N的不包含重复英文字母（区分大小写）的字符串。（2）输出说明：输出为一个整数，即该二叉树的高度。实验案例2：完成对二叉树的建立、先序、中序、后序及按层次遍历的操作，求所有叶子及结点总数的操作。（1）输入的形式和输入值的范围：二叉树中结点的值默认为字符类型，以先序形式输入并创建二叉树，空指针以“#”字符代替，字符连续输入，以按回车键表示结束。（2）输出的形式：二叉树的输出是每个字符占一列，输出完成后换行。（3）

8、程序所能达到的功能：能够根据要求正确的实现二叉树的所有要求的操作。名 称型 号数 量仪器设备PC机VC+6.0联想8181低值耐用品名 称 及 消 耗 额备 注消耗材料实验室主任: 填卡人: 万厚冲 填卡日期: 2012.9.10实 训 项 目 卡数学与计算机科学系 计算机实验室 计算机机房 分室实验序号5实验名称哥尼斯堡的“七桥问题”实验类别基础课程名称数据结构实验类型验证性实验者类别本科计划学时2实验要求必做实验组数81每组人数1实 验内 容1、熟练掌握图的存储结构。2、熟练掌握图的连通性判断方法。3、结合实际问题，培养学生算法描述的能力，加强对算法特性的理解。具体题目：实验案例：18世纪

9、时，欧洲有一个风景秀丽的小城哥尼斯堡(今俄罗斯加里宁格勒)，那里的普莱格尔河上有七座桥。将河中的两个岛和河岸连结，城中的居民经常沿河过桥散步，于是提出了一个问题：一个人怎样才能一次走遍七座桥，每座桥只走过一次，最后回到出发点？（1）输入说明：输入第1行给出两个正整数N（1N1000）和边数M，随后的M行对应M条边，每行给出一对正整数，分别是该条边连通的两个结点的编号（结点从1到N编号）。（2）输出说明：若欧拉回路存在则输出1，否则输出0。名 称型 号数 量仪器设备PC机VC+6.0联想8181低值耐用品名 称 及 消 耗 额备 注消耗材料实验室主任: 填卡人: 万厚冲 填卡日期: 2012.9

10、.10实 训 项 目 卡数学与计算机科学系 计算机实验室 计算机机房分室实验序号6实验名称旅游规划实验类别基础课程名称数据结构实验类型验证性实验者类别本科计划学时2实验要求必做实验组数81每组人数1实 验内 容熟练掌握迪杰斯特拉算法的应用。具体题目：实验案例：根据一张自驾旅游路线图，可以知道城市间的高速公路长度以及该公路要收取的过路费。现在编写一个程序，找出一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出过路费最少的一条路径。（1）输入说明：输入第1行给出4个正整数N,M,S,D，其中N（2N500）是城市的个数，顺便假设城市的编号为0（N-1）；M是高速公路的条数；

11、S是出发地的城市编号；D是目的地的城市编号。随后M行，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间以空格分隔，数字均为整数且不超过500.输入保证解的存在。（2）输出说明：在一行中输出路径长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。名 称型 号数 量仪器设备PC机VC+6.0联想8181低值耐用品名 称 及 消 耗 额备 注消耗材料实验室主任: 填卡人: 万厚冲 填卡日期: 2012.9.10实 训 项 目 卡数学与计算机科学系 计算机实验室 计算机机房 分室实验序号7实验名称整型关键字的散列映射实验类别基础课程名称数据结构实验类型验证性实验者类

12、别本科计划学时2实验要求必做实验组数81每组人数1实 验内 容（1）熟练掌握除留余数法散列映射。（2）熟练掌握用线性探测解决冲突的机制。实验案例：给定一系列整型关键字和素数P，用除留余数法定义的散列函数H（key）=Key % P 将关键字映射到长度为P的散列表中。用线性探测法解决冲突。（1）输入说明：输入第1行首先给出两个正整数N（N1000）和P（N的最小素数），分别为待插入的关键字总数以及散列表的长度。第2行给出N个整型关键字。数字间以空格分隔。（2）输出说明：在一行内输出每个整型关键字在散列表中的位置。数字间以空格分隔，但行末尾不得有多余空格。名 称型 号数 量仪器设备PC机VC+6.

13、0联想8181低值耐用品名 称 及 消 耗 额备 注实验室主任: 填卡人: 万厚冲 填卡日期: 2012.9.10实 训 项 目 卡数学与计算机科学系 计算机实验室 计算机机房 分室实验序号8实验名称模拟Excel排序实验类别基础课程名称数据结构实验类型验证性实验者类别本科计划学时2实验要求必做实验组数81每组人数1实 验内 容熟练掌握快速排序的库函数调用。实验案例：Excel可以对一组记录按任意指定列排序。现编写程序实现类似功能。（1）输入说明：输入第1行包含两个正整数N（N105）和C，其中N是记录的条数，C是指定排序的列号。之后有N行，每行包含一条学生记录。每条学生记录由学号（6位数字，保证没有重复学号）、姓名（不超过8位且不包含空格的字符串）、成绩（0,100