2022年计科数据结构实验大纲.docx
《2022年计科数据结构实验大纲.docx》由会员分享,可在线阅读,更多相关《2022年计科数据结构实验大纲.docx(21页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、精选学习资料 - - - - - - - - - 数据结构试验教案大纲课程编号: 404511043课程类别: 专业基础必修课试验学时: 试验 16 学时学 分: 5适用专业: 运算机科学与技术一、试验教案目的和任务数据结构是信息与运算科学专业中一门重要的专业基础课程;当用运算机来解决实际 问题时,就要涉及到数据的表示及数据的处理,而数据表示及数据处理正是数据结构课程的主要讨论对象,通过这两方面内容的学习,为后续课程,特殊是软件方面的课程打下了 厚实的学问基础,同时也供应了必要的技能训练;因此,数据结构课程在运算机应用专业中具有举足轻重的作用;本课程的任务是:通过实践,同学对常用数据结构的基本
2、概念及其不同的实现方法的 理论得到进一步的把握,并对在不同储备结构上实现不同的运算方式和技巧有所体会;二、试验教案基本要求本课程是一门实践性很强的专业课,只有明白这门课程的特点和基本要求,学习时才 能做到有的放矢,举一反三,本课程特点主要有以下几个方面:1 内容丰富,理论性强;本课程为以后学习专业基础课和专业课如:运算机操作系统、数据库原理等打下良好的基础;2 留意理论联系实际,加强试验环节的训练;只有通过试验,才能透彻懂得基本原 理;三、试验教案内容试验分验证性试验和设计性试验两部分,课外20学时用来完成验证性试验工程,以下的试验一至试验五为验证性试验,验证性试验的详细内容见数据结构验证性试
3、验指导 书,每个验证性试验工程完成后要提交一份电子试验报告,每份验证性试验报告至少包 括试验工程中的三个试验任务,电子验证性试验报告模板见附录 1;试验 16 学时用来完成设计性试验工程,全班同学分成小组,每组 3-4 人,设计性试验 工程的源程序全部由同学自己设计,同组的同学可以分工帮助,每人至少完成设计性试验 工程中的一个子任务,必需提前预备好设计性试验工程的代码,试验课开头时立刻提交自 己的源代码,试验课时老师立即抽取一个小组,第一,由小组同学讲解自己编写的代码并演示执行,接着,由老师和同学依据演示同学的代码提问,由演示的同学回答,假如当堂 不能解决,可下去预备,在下次试验课时再来解答;
4、课后,被抽中的小组同学在试验课后准时上交一份设计性试验报告,记录自己演示代码及回答提问时的情形及代码改进的情 况,既提交电子稿又要交打印稿,设计性试验报告模板见附录 2;验证性试验工程试验一 线性表的次序储备试验1、试验目的及要求:1 明白线性表的次序储备方法,把握用在 VC环境下上机调试单链表的基本方法;2 把握次序表的插入、删除、查找、求表长以及有序次序表的合并算法的实现 2、试验内容及学时安排:4 学时)1 / 12 名师归纳总结 - - - - - - -第 1 页,共 12 页精选学习资料 - - - - - - - - - 1 次序表基本操作的实现2有序次序表的合并,已知次序表la
5、 和 lb 中的数据元素按非递减有序排列,将la和 lb表中的数据元素,合并成为一个新的非递减有序次序表lc ,并且不破坏la和 lb 表试验二 单链表试验1、试验目的及要求:1 把握用在 VC环境下上机调试单链表的基本方法2 把握单链表、循环链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现2、试验内容及学时安排:4 学时)1 单链表基本操作的实现2 有序单链表的合并,已知单链表 la 和 lb 中的数据元素按非递减有序排列,将 la和 lb 中的数据元素 , 合并为一个新的单链表 lc,lc 中的数据元素仍按非递减有序排列,要求不破坏 la 表和 lb 表的结构;3 约瑟夫环问题
6、,设有 N 个人围坐一圈,现从某个人开头报数,数到 M 的人出列,接着从出列的下一个人开头重新报数,数到M 的人以出列,如此下去,直到全部人都出列为此;试设计确定他们的出列次序序列的程序;挑选单向循环链表作为储备结构模拟整个过程,并依次输出列的各人的编号;4 编程实现两个循环单链表的合并;试验三 栈、队列的实现及应用1、试验目的及要求:1 把握栈和队列的次序储备结构和链式储备结构,以便在实际背景下敏捷运用;2 把握栈和队列的特点,即先进后出与先进先出的原就;3 把握栈和队列的基本操作实现方法;2、试验内容及学时安排:4 学时)1 实现栈的次序储备2 利用栈实现数制转换3 实现循环队列的次序储备
7、4 次序串的基本操作试验四 二叉树的基本操作及应用1、试验目的及要求:1 进一步把握指针变量、动态变量的含义;2 把握二叉树的结构特性,以及各种储备结构的特点和适用范畴;3 把握用指针类型描述、拜访和处理二叉树的运算;2、试验内容及学时安排:4 学时)1 以二叉链表作储备结构,试编写前序、中序、后序及层次次序遍历二叉树的算法;2 以二叉链表作储备结构,试编写运算二叉树深度、全部结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法3编写按中序次序建立一棵二叉树的非递归算法的C 语言源程序,并且用非递归方式遍历二叉树 先序、中序或后序),输出遍历序列;4赫夫曼树与赫夫曼编码,利用Huffma
8、n 编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本;但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接受端将传来的数据编码进行译码复原);对于有些信道,每端都需要一个完整的编译码系统;试为这样的信息收发站编写一个Huffman 的编译码系统;给定一组权值 7 ,9, 5,6,10,1,13,15,4,8 ,构造一棵赫夫曼树,并运算带权路径长度 WPL;2 / 12 名师归纳总结 - - - - - - -第 2 页,共 12 页精选学习资料 - - - - - - - - - 试验五 查找与排序1、试验目的及要求:1 把握查找的不同方法,并能用高级语言实现查找算法
9、;2 娴熟把握次序表的查找方法和有序次序表的折半查找算法以及静态查找树的构造方法和查找算法;3 把握二叉排序树的生成、插入、删除、输出运算;4 把握常用的排序方法,并能用高级语言实现排序算法;5 深刻懂得排序的定义和各种排序方法的特点,并能加以敏捷运用;6 明白各种方法的排序过程及依据的原就,并把握各种排序方法的时间复杂度的分析方法;2、试验内容及学时安排:, operator* , operator- , Containsx, AddMember x, DelMemberx, Min ,试给出全部这些函数的实现;7 用序列 46, 88, 45, 39,70, 58,101,10,66, 3
10、4)建立一个排序二叉树,编程实现二叉排序树的建立、查找、中序遍历算法,运算和输出每次查找所需和关键字进行比较的次数,以及在等概率情形下查找胜利时的平均查找长度;8 设计一个程序读入一个字符串,统计该字符串中显现的字符及其次数,然后以表的形式输出结果;要求用一个二叉树来储存处理结果,字符串中的每个不同的字符用树中不同的结点描述,每个结点包含四个域,格式为:字符、该字符的显现次数、指向ASCII 码小于该字符的左子树指针、指向ASCII 码大于该字符的右子树指针;因此程序的功能是依次从输入字符串中取出一个字符,把它们插入到树中新显现字符)或修改原树中相应结点的“ 显现次数域”,把它插入到结果链表的
11、最前端;由于在原始链表中摘下的排序码越来越小,在结果链表前端插入的排序码也越来越小,最后形成的结果链表中的结点将按排序码非递减的次序有序链接;设计性试验工程1. 线性表的合并:已知线性表La 和 Lb 的元素按值非递减排列;归并La 和 Lb 得到新的线性表 Lc,Lc 的元素也按值非递减排列;分别采纳次序储备结构和链式结构来实现;2. 线性表的逆置:设有一个线性表e0, e1, , en-2 , en-1 ),请编写一个函数将这个线性表原地逆置,即将线性表内容置换为 采纳数组表示作为求解过程中使用的数据结构;3 / 12 名师归纳总结 - - - - - - -第 3 页,共 12 页精选学
12、习资料 - - - - - - - - - 2 采纳单向循环链表作为储备结构模拟整个过程,循环链表可不设头节点 , 必需留意空表和非空表的界限;4. 数制转换:利用次序栈和链栈实现数制转换5. 二叉树的遍历:分别以次序储备结构和二叉链表作储备结构,试编写前序、中序、后序及层次次序遍历二叉树的算法;6. 赫 夫 曼 树 与 赫 夫 曼 编 码 : 已 知 某 系 统 在 通 信 联 络 中 只 可 能 出 现 8 种 字 符a,b,c,d,e,f,g,h,其概率分别为 0.05 ,0.29 ,0.07 ,0.08 ,0.14 ,0.23 ,0.03 ,0.11 ,试设计 Huffman 编码,并
13、运算其平均码长;1 初始化:从键盘读入 8 个字符,以及它们的权值,建立 Huffman 树;2 编码:依据建立的 Huffman 树,求每个字符的 Huffman 编码;对给定的待编码字符序列进行编码;3 译码:利用已经建立好的Huffman 树,对上面的编码结果译码;译码的过程是分解电文中的字符串,从根结点动身,按字符0和1确定找左孩子或右孩子,直至叶结点,便求得该子串相应的字符;4 打印 Huffman 树;7. 同学成果治理查询系统:每个同学的数据信息有准考证号主关键字)、姓名、语文、英语、数学、和总分等数据项,全部同学的信息构成一个同学成果表;假设准考证号的头两位表示地区编号;请设计
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022 年计科 数据结构 实验 大纲
限制150内