2016年秋数据结构课程设计题目

《2016年秋数据结构课程设计题目》由会员分享，可在线阅读，更多相关《2016年秋数据结构课程设计题目（5页珍藏版）》请在金锄头文库上搜索。

1、设计题目赫夫曼树的建立任务：建立最优一叉树函数要求：可以建立函数输入二叉树，并输出其赫夫曼树已知技术 参数和设 计要求在上交资料中请写明：存储结构、基本算法（可以使用程序流程 图）、输入输出、源程序、测试数据和结果、算法的时间复杂度、 另外可以提出算法的改进方法；设计题目利用Hash技术统计C源程序中关键字的频度一、任务描述扫描一个C源程序，用Hash表存储该程序中出现的关键字，并统计该 程序中的关键字出现的度。用线性探测法解决Hash冲突。设Hash函数为： Hash（Key） = （Key的首字母序号）*100+（Key的尾字母序号）Mod 41。关键 字39个，参考C语言教材。二、数据结

2、构设计关键字表的存储结构；Hash表中的结点结构。频度、冲突次数三、功能设计从一个大字符串中分解单词已知技术 参数和设 计要求 识别是否是关键词；用哪种方法：有序表查找、二叉查找树？ Hash函数，解决冲突，统计冲突次数。key =地址 插入Hash表，或调整Hash表项中的频度 输出Hash表，关键词总数，冲突次数 自己想象，功能要多，设计要合理。四、技术讨论 文件不冋，Hash表各项次序是否一样？ 考察多个C源程序文件，计算当关键词总数约为1000时，冲突次数的总 次数？ Hash表空间增大后，是否冲突一定减少？ 比较其他的Hash函数，其他的冲突处理方法，效率有何差别。 题目所给的Has

3、h函数，好吗？设计题目(拓扑排序)已知技术 参数和设 计要求本次课程设计的任务是：针对学院的计算机系本科课程，根据课程之间的依赖关系，制 定课程安排计划，并满足各学期课程数大致相同。按照用户输入的课程数，学期数，课 程间的先后关系数目以及课程间两两间的先后关系，程序执行后会给出每学期应学的课 程。(1) 输入的形式和输入值的范围：输入间用空格隔开。要求用户输入的课程数小于20， 学期数小于或是等于8,课程名的长度小于等于10个字符。(2) 程序所能达到的功能：按照用户的输入，给出每学期应学的课程。(4)测试数据：输入：学期数：5,课程数：12,课程间的先后关系数：16,课程的代 表值：v1,v

4、2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12。课程间两两间的先后关系：v1 v2,v1 v3, v1 v4,v1 v12,v2 v3,v3 v5,v3 v7,v3 v8, v4 v5, v5 v7,v6 v8, v9 v10, v9 v11 , v9 v12,v10 v12,v11 v6输出：第1学期应学的课程：v1 v9第2学期应学的课程：v2 v4 v10 v11 第3学期应学的课程：v3 v6 v12第4学期应学的课程：v5 v8第5学期应学的课程：v7四、对给定的图，编写求最小生成树算法，用 prim 思想五、设计题目顺序结构、动态链表结构下的一元多项式的加法、

5、减法、乘法的实现。已知技术 参数和设 计要求设有一兀多项式Am(x)和Bn(x).Am(x)=A0+Alxl+A2x2+A3x3+ +AmxmBn(x)=B0+Blxl+B2x2+B3x3+Bnxn请实现求 M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和 M(x)= Am(x)XBn(x)o要求：1) 首先判定多项式是否稀疏2) 分别采用顺序和动态存储结构实现；3) 结果M(x)中无重复阶项和无零系数项；4)要求输出结果的升幕和降幕两种排列情况约瑟夫生者死者游戏约瑟夫生者死者游戏的大意是：30 个旅客同乘一条船，因为严重超 载，加上风高浪大，危险万分；因此船长告诉乘客

6、，只有将全船一半 的旅客投入海中，其余人才能幸免遇难。无奈，大家只得同意这种办 法，并议定 30 个人围成一圈，由第一个人开始，依次报数，数到第 9 人，便把他投入大海中，然后从他的下一个人数起，数到第 9 人， 再将他投入大海，如此循环，直到剩下 15 个乘客为止。问哪些位置 是将被扔下大海的位置。2 设计思路 本游戏的数学建模如下：假设 n 个旅客排成一个环 形，依次顺序编号1, 2, n。从某个指定的第1号开始，沿环计 数，每数到第 m 个人就让其出列，且从下一个人开始重新计数，继 续进行下去。这个过程一直进行到剩下k个旅客为止。 本游戏的要 求用户输入的内容包括： 1. 旅客的个数，也

7、就是 n 的值； 2. 离 开旅客的间隔数，也就是 m 的值； 3. 所有旅客的序号作为一组数 据要求存放在某种数据结构中。 本游戏要求输出的内容是包括 1. 离开旅客的序号； 2. 剩余旅客的序号； 所以，根据上面的模型 分析及输入输出参数分析，可以定义一种数据结构后进行算法实现。3 数据结构 为了解决这一问题，可以用长度为 30 的数组作为 线性存储结构，并把该数组看成是一个首尾相接的环形结构，那么每 投入大海一个乘客，就要在该数组的相应位置做一个删除标记，该单 元以后就不再作为计数单元。这样做不仅算法较为复杂，而且效率低， 还要移动大量的元素。用单循环链表解决这一问题，实现的方法相对 要

8、简单得多。首先要定义链表结点，单循环链表的结点结构与一般的 结点结构完全相同，只是数据域用一个整数来表示位置；然后将它们 组成具有30个结点的单循环链表。接下来从位置为1的结点开始数， 数到第 8 个结点，就将下一个结点从循环链表中删去，然后再从删去 结点的下一个结点开始数起，数到第8 个结点，再将其下一个结点删 去，如此进行下去，直到剩下 15 个结点为止。 七散列表的设计与实现【问题描述】设计散列表实现电话号码查找系统。【基本要求】1) 设每个记录有下列数据项：电话号码、用户名、地址；2) 从键盘输入各记录，分别以电话号码和用户名为关键字建立散列 表；3) 采用一定的方法解决冲突；4) 查找并显示给定电话号码的记录；5) 查找并显示给定用户名的记录。