《数据结构》课程设计

《《数据结构》课程设计》由会员分享，可在线阅读，更多相关《《数据结构》课程设计（13页珍藏版）》请在装配图网上搜索。

1、数据结构课程设计大纲课程编号: 课程名称:数据结构周数/学分： 先修课程: 离散数学、C程序设计适用专业：计算机科学与技术、软件、网络、信息管理 开课分院或专业：理工分院一课程设计的目的 增强学生实际应用能力、创新能力。二课程设计的内容和要求1课程设计的内容 根据教学大纲，选取具有实际意义、能力、思维提高的题目。2课程设计的要求 学生自选题，每人至少选2个题。三课程设计进度安排进度表如下：序号阶段内容所 用 时 间1学生选题2节课 2题目分析、算法设计6节课 3题目讲解3节课 4编程实现4节课 5撰写论文3节课 6答辩2节课合 计20节课时 四、课程设计说明书与图纸要求1设计题目附后2正文格式

2、书写格式的基本要求说明：说明书一律使用A4打印纸计算机打印或手写，封面标明“海南大学三亚学院数据结构课程设计说明书字样。正文内容使用宋体小4号字。打印版面上空2.5cm，下空2cm，左空2.5cm，右空2cm（左装订），固定行距，24磅。页眉和页脚用宋体，小5号字居中标明。 五、课程设计评分标准评定项目评分成绩1. 选题合理、目的明确（10分）2. 设计方案正确，具有可行性、创新性（20分）3. 设计结果（例如：硬件成果、软件程序）（20分）4. 态度认真、学习刻苦、遵守纪律（15分）5. 设计报告的规范化、参考文献充分（不少于5篇）（10分）6. 答辩（25分）总分(100分)备注：成绩等级

3、：优（90分100分）、良（80分89分）、中（70分79分）、及格（60分69分）、60分以下为不及格。六、课程设计参考资料1、数据结构（C语言版），清华大学出版社，严蔚敏等编。2、C程序设计，清华大学出版社，李春葆编。执笔： 段景辉审阅： 日期：审定： 日期：课程设计任务书一、设计题目：（宋体，小四号字，加黑）二、设计目的（宋体，小四号字，加黑）1 (宋体,小四号字)2 三、设计任务及要求（宋体，小四号字，加黑） 四、课程设计人数与分组情况表：班级人数设计地点指导教师起止时间五、设计时间及进度安排（宋体，小四号字，加黑）设计时间共 周（具体日期）,具体安排如下表：周安排设 计 内 容设计时

4、间第一周第二周第三周第四周六、课程设计评分标准评定项目评分成绩1. 选题合理、目的明确（15分）2. 设计方案正确，具有可行性、创新性（25分）3. 设计结果（例如：硬件成果、软件程序）（25分）4. 态度认真、学习刻苦、遵守纪律（20分）5. 设计报告的规范化、参考文献充分（15分）总分(100分)备注：成绩等级：优（90分100分）、良（80分89分）、中（70分79分）、及格（60分69分）、60分以下为不及格。七、经费预算 编制人： 专业负责人： 日期： 审核人： 日期：课程名称课程设计指导书分院名称年 月 日课程名称 课程设计指导书一、 课程设计的目的: 正文（宋体小四号字），可以增

5、加内容编号如1、2、二、课程设计的要求：正文（宋体小四号字）可以增加内容编号如1、2、三、课程设计内容：正文（宋体小四号字），可以增加内容编号如1、2、四、课程设计方法与步骤：1、课程设计方式：正文（宋体小四号字）2、课程设计单位或场所：正文（宋体小四号字）3、课程设计进度安排：正文（宋体小四号字）应当详细具体的说明实习进度安排如：“第一天”或“第一天到第三天”等等4、实习方法：正文（宋体小四号字）五、课程设计组织与纪律：正文（宋体小四号字），可以增加内容编号如1、2、六、课程设计总结内容及要求：正文（宋体小四号字），可以增加内容编号如1、2、七、考核方式与成绩评定标准：正文（宋体小四号字），

6、可以增加内容编号如1、2、八、教材及主要参考资料：正文（宋体小四号字），可以增加内容编号如1、2、九、大纲说明正文（宋体小四号字），可以增加内容编号如1、2、十、安全问题和注意事项 正文（宋体小四号字），可以增加内容编号如1、2、编制人： 审核人： 年 月 日 海南大学三亚学院课程设计考核表分院 专业 班级课程设计题目学生姓名学号课程设计时间年 月 日至 年 月 日同组人序号姓名学号课程设计总结报告（完成情况）（后可附页）指导教师评定意见审核人意见 指导教师： 年 月 日 审核人： 年 月 日附：课程设计题目1、可利用空间链表结构示意图，如下：存储请求分别有： 10000 1000 56000

7、030000 012000010000 AV 试用首次拟合法和最佳拟合法求出分配结果。2、设计算法并实现，判断某输入字符串是否具有中心对称关系，例如ababbaba，baxzxab皆具有对称性。3、计算下列串的next值，并编程实现。 (1)a a a b c a a b c (2)a b c a b c a c b4、设计算法并实现，将数组A0n-1中的元素循环右移k位，要求只使用一个元素大小的附加存储空间。5、迷宫求解问题。所谓迷宫问题可以这样来描述，即把一只老鼠放入一个大箱中，箱内设置若干隔板，使老鼠走动的方向受到阻碍，看其如何找到一条通路走出大箱。6、编写按层次顺序（同一层自左至右）遍

8、历二叉树的算法。7、设民航公司有一个自动预订飞机票的系统，该系统中有一张用双重链表示的乘客表，表中结点按乘客姓氏的字母序相链。例如，下面是张某个时刻的乘客表。试为该系统写出一个当任一乘客要订票时修改乘客表的算法。序号 data Llink Rlink 1 Liu 6 5 2 Chan 4 9 3 Wang 5 7 4 Bao 0 2 5 Mai 1 3 6 Dong 8 1 7 Xi 3 0 8 Deng 9 6 9 Cuang 2 88、已知三个带头结点的线性链表A、B和C中的结点均依元素值自小至大非递减排列（可能存在两个以上值相同的结点），编写算法对A表进行如下操作：使操作后的链表A中仅留

9、下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为O（m+n+p），其中m、n和p分别为三个表的长度。9、已知Q是一个非空队列，S是一个空栈。仅用队列和栈的ADT函数和少量工作变量，使用C语言编写一个算法，将队列Q中的所有元素逆置。 栈的ADT函数有： makeEmpty(s:stack); 置空栈 push(s:stack; value:datatype); 新元素value进栈 pop(s:stack):datatype; 出栈，返回栈顶值 isEmpty(s:stack):boolean; 判栈空否 队列的ADT函数有 enqueue(q:q

10、ueue;value:datatype); 元素value进队 deQueue(q:queue):datatype; 出队列，返回队头值 isEmpty(q:queue):boolean; 判队列空否10、从左到右及从右到左遍历一个单链表是可能的，其方法是在从左向右遍历的过程中将连接方向逆转，如图1所示。在图中的指针p指向当前正在访问的节点，指针pr指向指针p所指节点的左侧的节点。此时，指针p所指节点左侧的所有节点的连接方向都已逆转。 使用C语言编写一个算法，从任一给定位置（pr,p）开始，将指针p右移1 个节点。如果p移出链表，则将p置为NULL，并让pr留在链表最右边的节点上。 使用Pas

11、cal或C语言编写一个算法，从任一给定位置（pr,p）开始，将指针p左移一个节点。如果p移出链表，则将p置为NULL,并让pr停留在链表最左边的节点上。11、设有大小不等的n个数据组（n个数据组中数据的总数为m），顺序存放在空间区D内，每个数据占一个存储单元，数据组的首地址由数组s给出（如下图所示），试编写将新数据x插入到第i个数据组的末尾且属于第i个数据组的算法，插入后，空间区D和数组S的相互关系仍保持正确。12、写出删除二叉排序树bt中值为x的结点的算法（二叉排序树以二叉链表形式存储，删除后仍然保持二叉排序性质）。 13、设计算法，并实现，已知某结点值序列为 45，24，53，12，28，

12、90 试将其构造一棵二叉排序树(BST)。14、设二叉树中左枝标号为”0”，右枝标号为”1”，且增设一个头结点。令二叉树根结点为该头结点的右孩子，则从头结点到树中任一结点所经分支的序列为一个二进制序列，可认作是某十进制数的二进制数表示。例如，下图所示中结点A对应的二进制序列为1 1 0是十进制数6的表示。已知一棵非空的二叉树以顺序存储表示，变量i为树上某结点在顺序存储结构中的下标值。试编写程序，求出与该结点对应的十进制数d。15、(1)证明：在结点数大于1的哈夫曼树中不存在度为1的结点。 (2)证明：非空的完全二叉树是路径长度最短的二叉树。16、设有8枚硬币，即a、b、c、d、e、f、g、h，

13、其中仅有一枚是伪造的。真币重量相同，伪造与真币重量不同，可轻可重。设计算法，编写程序，用最少的比较次数将伪币挑出来。17、对于一个具有n个顶点、e条边的无向图G=(V,E)，设计算法，编写程序建立它的邻接矩阵，且满足 1 当(vi，vj)E(G)时 Ai,j=0 当vi=vj或(vi，vj) E(G)时18、从顶点Vi出发广度优先搜索图G。G是一个连通图，且是用邻接矩阵存储的。 设计算法，编程实现BFS算法。19、(1)试利用迪杰斯特拉算法，求如图所示有向图从顶点1到其余个顶点的最短路径，并给出执行过程中dist数组的变化状况。 10 20 15 2 4 30 4 10 15 10 (2)若森

14、林共有n个结点和b条边(bn)，则森林中有多少棵树？20、要求二叉树按二叉链表形式存储。(1)编写一个建立二叉树的算法，并编程实现。(2)写一个判别给定的二叉树是否是完全二叉树的算法，并实现。 注：完全二叉树的定义为：深度为K、具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1到N的结点一一对应。21、以孩子兄弟链表作为存储结构，设计算法递归和非递归算法求树的深度，并编程实现之。22、设计算法并实现对二叉树按前序、中序、后序线索化。23、给定一组项及按其权值，假定项都存放于二叉树的树叶结点，则具有最小带权路径长度的树称为哈夫曼树。 (1) 给出构造哈夫曼树的算法。(2) 给定项及相

15、应的权如下图，画出执行上述算法后的哈夫曼树。序号123456789项ABCDEFGHI权1567122546115(3) 编程实现构造哈夫曼树的程序。24、设在4地(A、B、C、D)之间架设有6座桥，如图， A 24 1 6 C D35 B25、欲用四种颜色对地图上的国家涂色，有相邻边界的国家不能用同一种颜色（点相交不算相邻）。(1) 试用一种数据结构表示地图上各国相邻的关系。(2) 设计算法，并实现。26、给定n个村庄之间的交通图，若村庄i和村庄j之间有道路，则将顶点i和j用边连接，边上的权表示这条道路的长度，现在要从这n个村庄中选定一个村庄建一所医院，问这个医院应该建在那个村庄，才能使离医

16、院最远的村庄到医院的路程最短？设计算法，并实现。27、设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法： （1）找出最大值结点，且打印该数值； （2）若该数值是偶数，则将其与直接后继结点的数值交换；（3）若该数值是奇数，则将其直接后继结点删除；28、设一颗二叉树以二叉链表为存储结构，设计一个算法将所有结点的左、右子树相互交换。29、已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个删除表中所有值小于max但大于min的元素的算法。30、 设一棵二叉树T以二叉链表为存储结构，编写算法求该二叉树叶子结点的数 目。31、已知一个含有1000个记录的表，关键字为中国人姓氏的拼音，请给出此表的一个哈希表设计方案，要求它在等概率情况下查找成功的平均查找长度不超过3。32、已知某哈希表的装载因子小于1，哈希函数H(key)为关键字（标识符）的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。33、编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。34、试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w)，即删除一条边的操作。35、编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。