计科13级数据结构实习题目.docx

先秦计科131-2数据结构课程设计题目1、大整数运算器要求：（1）用顺序线性表存储整数，每个单元存储4位。（2）以字符串形式输入大整数。（3）实现大整数的加、减、乘法。（4）输出格式：从个位向左，每4位一组，组间用空格隔开，最左边若正好4位一组，符号与数字之间不必间隔。如：-12358769524应输出为：-123 5876 9524（5）人机交互界面。2、求整数的阶乘（不小于20的数的阶乘）要求：（1）用顺序线性表存储阶乘，每个单元存储4位。（2）输出格式：fact(n)=n!，n用具体的数代替，n！从个位向左，每4位一组，组间用空格隔开。3、一元稀疏多项式运算器要求：（1）用带头结点的单链表作为多项式的存储结构，多项式的每一项只存储系数和指数，多项式各项的顺序为：按照指数降序排列，如：5x8-3x3+x2-9（输出也是如此格式，即符合数学上常用的格式）。（2）实现多项式的输入、输出和加、减和乘法运算，运算结果也按（1）中的格式存储和输出。（3）人机交互界面。4、集合的交、并和差运算要求：（1）以链表作为集合的存储结构，集合的元素限定为字符型。（2）实现集合的输入、输出、交、并和差。可以用字符串的形式进行输入输出。（3）人机交互界面。5、通讯录管理系统要求：（1）用顺序表作为通讯录的存储结构。每条通讯录包含：姓名，城市，电话。表中的记录按姓名非递减有序，每插入一条记录后，应使表中记录仍保持按姓名非递减排序。（2）实现插入、删除、修改、显示、查找功能（插入、删除、查找均以姓名作为关键字折半查找），可能会有重名的人，应将所有名字一样的记录查找出来。（3）人机交互界面。6、算术表达式求值要求：（1）实现算术（整数）表达式的加、减、乘、除四则运算，表达式可带括号，操作数超过1位数时，应按1个整数对待，如123，为1个数。（2）建立算符优先关系表。（3）建立操作数栈和运算符栈。表达式以字符串的形式输入。（4）能够检查出不合法的表达式，并给出出错信息。7、稀疏矩阵运算器要求：（1）以“带行逻辑链接信息”的三元组顺序表作为稀疏矩阵的存储结构。（2）实现稀疏矩阵的输入、输出以及加、减、乘法运算，并输出结果。（3）人机交互界面。8、稀疏矩阵运算器要求：（1）以十字链表作为稀疏矩阵的存储结构。（2）实现稀疏矩阵的输入、输出以及加、减、乘、转置运算，并输出结果。（3）人机交互界面。9、赫夫曼编/译码器要求：（1）参考教材，采用顺序结构存储赫夫曼树。（2）实现以下功能：将字符集大小n以及n个字符和n个权值（按照习题集P149表格中的字符和权值）存入文本文件char.txt中。l 初始化：从char.txt文件中读取字符个数n及n个字符及其权值，建立赫夫曼树，并进行赫夫曼编码（选作：可将赫夫曼树存入文件hfmTree文件中，将赫夫曼编码存入文件hfmCode中）。l 编码：利用已建好的赫夫曼树对某个文件内容进行编码，将结果存入文件CodeFile中。l 译码：利用已建好的赫夫曼树对文件CodeFile中的代码进行译码，结果存入文件TextFile中。l 选作：若实现了将赫夫曼树存入文件hfmTree中，那么，如果执行编码或译码前没有进行初始化，即赫夫曼树不在内存，则需读入，否则不必再读入。若未实现将第（1）条中的选作内容，则不必考虑。l 人机交互界面。10、河南科技学院下设17个二级学院，每个二级学院下设若干专业，各个专业下分多个班级，为了方便教师和学生了解各个学院的情况，请你为我校的机构设计一棵树。要求：（1）建立我校的机构树。请自选树的存储结构。（2）输出所有的二级学院的名称。（3）查询并输出某个二级学院下设的各个专业的名称。（4）查询并输出某专业所属二级学院的名称，如：计算机科学与技术专业所属二级学院：信息工程学院。（5）查询并输出某班级所属专业的名称和所属二级学院的名称，如：计科121所属专业：计算机科学与技术，所属二级学院：信息工程学院。（6）人机交互界面。11、家谱要求：（1）为该家族建立家谱树，用孩子链表作为家谱的存储结构。每个人的信息包含以下内容：姓名，性别，婚姻状况（0表未婚，1表已婚），配偶姓名、子女数，若未婚，则配偶姓名为空，子女数为0。（2）查询并输出某人的基本信息。（3）查询并输出某人所有子女的基本信息。（4）查询某人的双亲。（5）人机交互界面。12、无向图的遍历要求：以邻接多重表为存储结构，分别实现深度和广度优先遍历。13、有向图的遍历要求：以十字链表为存储结构，分别实现深度和广度优先遍历。14、最小生成树。需要在新乡市的n个居民区之间铺设天然气管道，则在这n个居民区之间只要铺设n-1条管道即可。假设任意两个居民区之间都可以架设管道，但由于地理环境的不同，所需经费不同。请选择最优的施工方案能使总投资尽可能少。要求：用克鲁斯卡尔算法实现。筛选最小代价边时用堆排序方法（不要求对所有边排序，只要选出n-1条最小代价边即可）。98.752.579.210.541.167.385.621.356.48.712.144.65.932.818.2ABCHBGEDF15、基于邻接矩阵的图的基本操作。要求：在邻接矩阵存储结构上实现无向图和有向图的基本操作：l 插入点InsertVex(G,v)；l 插入边InsertArc(G,v,w)；l 删除点DeleteVex(G,v)；l 删除边DeleteArc(G,v,w)；l 为了检验结果，需要建立无向图和有向图、输出图中的顶点和边。16、基于邻接表的图的基本操作。要求：在邻接表存储结构上实现无向图和有向图的基本操作：l 插入点InsertVex(G,v), l 插入边InsertArc(G,v,w), l 删除点DeleteVex(G,v), l 删除边DeleteArc(G,v,w)。l 为了检验结果，需要建立无向图和有向图、输出图中的顶点和边。17、公交查询。我校到河南师范大学有多种乘坐公交的方式，请给出到河南师范大学的乘坐公交的所有方式及最快方式。要求：l 任选新乡市的景点构造有向图，除了我校和河南师范大学外，不少于5个景点。l 2点之间多于1条公交线路的，保留一条线路。18、校园导游。设计一个校园导游程序，为来访的客人提供各种信息查询服务。要求：1）设计校园平面图，在校园景点选10个左右景点。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。2）为来访客人提供图中任意景点相关信息的查询。3）为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。实现提示：一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网。顶点和边均含有相关信息。19、图书信息管理系统要求：用二叉排序树管理图书信息，图书信息包括：书名，作者，出版社，数量，书名为关键字。（1）实现图书信息的录入；（2）删除图书信息；（3）修改图书信息（书名一旦修改，位置可能变化）（4）以书名为关键字查找图书信息。（5）人机交互界面。20、内部排序要求：实现直接插入排序、希尔排序、快速排序、堆排序、归并排序，输出每一趟排序的结果。21、教务课程计划的辅助制定。一个学生在一个学期可以同时学习多门课程，同一学期的各门课程之间不存在次序关系，制定课程计划使学生可以在6学期内学完所有课程。测试数据开设课程为计算机专业必修课，它们是计算机导论，线性代数、离散数学、汇编语言、数据结构、操作系统等。各门课之间的次序关系见AOV网的数据模型。课程先修关系如下： 课程编号课程名称学分先决条件C1程序设计基础2无C2离散数学3C1C3数据结构4C1，C2C4汇编语言3C1C5语言的设计和分析2C3，C4C6计算机原理3C11C7编译原理4C5，C3C8操作系统4C3，C6C9高等数学7无C10线性代数5C9C11普通物理2C9C12数值分析3C9，C10，C122、打印目录。将数据结构课本的目录录入文件目录.txt，一行一条。自选树的结构，根据文件目录.txt建立目录树，在屏幕上打印该目录树，打印格式和课本一样。附件：实习报告格式，如下：数据结构实习报告班 级：姓 名：xxx（20121514101） xxx（201215