数据结构课程设计题目参考2010.doc

1以邻接矩阵的方式确定一个图，完成：建立并显示出它的邻接链表；以非递归的方式进行深度优先遍历，显示遍历的结果，（并随时显示栈的入、出情况）；对该图进行广度优先遍历，显示遍历的结果，（并随时显示队列的入、出情况）。2以邻接矩阵的方式确定一个图，完成：建立并显示出它的邻接链表；给出它的关键路径（要求：显示出VE，VL，E，L，L-E的结果）。3以邻接矩阵的方式确定一个图，完成：建立并显示出它的邻接链表；分别用普里姆算法和克鲁斯卡尔算法构造其最小生成树，随时显示其构造的过程；4建立一棵二叉树，并用非递归方式对它进行先序、中序、后序遍历，给出遍历过程中栈的变化情况；5哈夫曼树、编码、译码 (1)输入一组字符集的大小、字符及权值，建立哈夫曼树，显示该哈夫曼树，并给出每个字符的哈夫曼编码 (2)给出一串字符，按照已建立的哈夫曼树进行编码，显示结果或存入文件 (3)用(2)的结果，按照哈夫曼树进行译码。6二叉排序树的建立和删除给出一组关键值，建立相应的二叉排序树，完成结点的删除操作。要求可以实现删除根结点、叶子结点以及其它任意结点的功能；随时显示操作的结果。7. 几种排序，随时给出某一趟的变化情况直接插入排序、折半插入排序、希尔排序；冒泡排序、快速排序；简单选择排序(4)堆排序8. 要求是：(1)从键盘输入一个表达式，如（23-（45.2-2.8）/5=(2)支持+，-，/,( )等符号 (3)支持运算符的优先级 (4)支持括号的嵌套 (5)支持小数点及负数 (6)有查错功能，如非法字符，小数点过多（如3.44.3），括号不匹配等错误。9. 以邻接矩阵的方式确定一个图，完成：建立并显示出它的邻接链表；给出某一确定顶点到所有其它顶点的最短路径； 10. 约瑟夫环问题 问题描述编号是1，2，,n的n个人按照顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 基本要求1.利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。此题所用的循环链表中不需要“头结点”，请注意空表和非空表的界限。2.向上述程序中添加在顺序结构上实现的部分。 测试数据 m的初值为20，n=7,7个人的密码依次为3，1，7，2，4，7，4，首先m=则正确的输出是什么？要求：输入数据：首先输入待处理人员数及他们的密码，然后输入m的初值，建立单循环链表。输出形式：建立一个输出函数，将正确的出列序列输出。11. 任意长的整数加法问题描述：设计一个程序实现两个任意长的整数的求和运算。基本要求：利用双向循环链表，设计一个实现任意长的整数进行加法运算的演示程序。要求输入和输出每四位一组，组间用逗号隔开。如：1，0000，0000，0000，0000。12. 串的查找和替换问题描述：打开一篇英文文章，在该文章中找出所有给定的单词，然后对所有给定的单词替换为另外一个单词，再存盘。13. 括号匹配问题问题描述：假设一个算术表达式中可包含三种括号：圆括号，方括号和花括号且这三种括号可按任意次序嵌套使用。试利用栈的运算，编写判别给定表达式中所含括号是否正确配对出现的算法。14. 一元多项式简单计算问题描述：设计一个一元多项式简单的计算器。基本要求：一元多项式简单计算器的基本功能为： (1) 输入并建立多项式；(2)输出多项式；(3)两个多项式想加，建立并输出和多项式；(4)两个多项式相减，建立并输出差多项式。 实现提示：可选择带头结点的单向循环链表或单链表存储多项式，头结点可存放多项式的参数，如项数等。 15. 迷宫问题问题描述：迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次试验终于得到它学习走迷宫的路线。设计一个计算机程序对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 要求：在给出入口和出口的前提下，给出动态的迷宫行走路线。 16. 八皇后问题 要求：试编写程序实现将八个皇后放置在国际象棋棋盘的无冲突的位置上的算法，并给出所有的解。 提示：在国际象棋上放置皇后时，任何一个皇后的水平、竖直和斜45都不能有另一个皇后。解决该问题采用逐次试探的方法，即采用递归调用putchess函数的方法。首先将第一个皇后放于第一行第一列，然后开始向下一行递归。每一步递归中，首先检测待放置位置是否与已放置的皇后冲突，如不冲突，则进行下一行的放置，否则，选择该行的下一个位置进行检测。如整行的位置都冲突，则回到上一行，重新选择位置。17. 程序分析 问题描述 读入一个C程序，统计程序中代码、注释和空行的行数以及函数的个数和平均行数，并利用统计信息分析评价该程序的风格。 基本要求 (1)把C程序文件按字符顺序读入源程序； (2)边读入程序，边识别统计代码行、注释行和空行，同时还要识别函数的开始和结束，以便统计其个数和平均行数。 (3)程序的风格评价分为代码、注释和空行三个方面。每个方面分为A，B，C和D四个等级，等级的划分标准是： A级 B级 C级 D级 代码(函数平均长度)1015行 89或1620行57或2124行24行 注释(占总行数比率)1525 1014或2630 59或3135 35 空行(占总行数比率)1525 1014或2630 59或3135 35 以下是对某程序文件分析的输出结果示例： The resulfs Of analystag program“ProgAnalC”； lanes Of code： 180 lanes Of comments：63 B1ank 1ines： 52 ， Code Comments Space 61 2l 18 The program includes 9 functions The average 1ength Of a section OcOde is 12.9 lines Grade A：Exeellent routine size style Grade A：Excellent commenting style. Grade A：Excellent white space style 测试数据 先对较小的程序进行分析。当你的程序能正确运行时，对你的程序本身进行分析。 实现提示 为了实现的方便，可作以下约定： (1)头两个字符是”/”的行称为注释行(该行不含语句)。除了空行和注释行外，其余均为代码行(包括类型定义、变量定义和函数头)。 (2)每个函数代码行数(除去空行和注释行)称为该函数的长度。 (3)每行最多只有一个“”、“”、“switch”和struct”(便于识别函数的结束行)。18. 集合的并、交和差运算 问题描述 编制一个能演示执行集合的并、交和差运算的程序。 基本要求 (1)集合的元素限定为小写字母字符a z。 (2)演示程序以用户和计算机的对话方式执行。 测试数据 (1)Setl”magazine”，Set2”paper， SetlSet2”aeginmprz，SetlSet2”ae”，Setl一Set2gimnz。 (2)Setl”0120per4a6tion89，Set2”error data， SetlSet2”adeinoprt，SetlSet2”aeort”，Setl一Set2”inp”。 实现提示 以有序链表表示集合。19.数组的应用举例魔方阵 魔方阵是一个古老的智力问题，它要求在一个nn的矩阵中填入1到n2的数字（n为奇数），使得每一行、每一列、每条对角线的累加和都相等，如图所示。 编写算法实现魔方阵. 20. 稀疏矩阵运算器 问题描述 稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。 基本要求以三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示而运算结果的矩阵则以通常的阵列形式列出。 实现提示 1首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。可设矩阵的行数和列数均不超过20。 2程序可以对三元组的输入顺序加以限制，例如，按行优先。 3在用三元组表示稀疏矩阵时，相加或相减所得结果矩阵应该另生成，乘积矩阵也可用二维数组存放。 21.回文词 回文词是一种对称的字符串，即从左到右读