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

1．?以邻接矩阵的方式确定一个图，完成：建立并显示出它的邻接链表；以非递归的方式进行深度优先遍历，显示遍历的结果，（并随时显示栈的入、出情况）；对该图进行广度优先遍历，显示遍历的结果，（并随时显示队列的入、出情况）。．以邻接矩阵的方式确定一个图，完成：建立并显示出它的邻接链表；给出它的关键路径（要求：显示出VE，VL，E，L，L-E的结果）。．以邻接矩阵的方式确定一个图，完成：建立并显示出它的邻接链表；分别用普里姆算法和克鲁斯卡尔算法构造其最小生成树，随时显示其构造的过程；．建立一棵二叉树，并对它进行先序、中序、后序遍历，给出遍历过程中栈的变化情况；．哈夫曼树、编码、译码 1 输入一组字符集的大小、字符及权值，建立哈夫曼树，显示该哈夫曼树，并给出每个字符的哈夫曼编码 2 给出一串字符，按照已建立的哈夫曼树进行编码，显示结果或存入文件 3 用 2 的结果，按照哈夫曼树进行译码。．二叉排序树的建立和删除给出一组关键值，建立相应的二叉排序树，完成结点的删除操作。要求可以实现删除根结点、叶子结点以及其它任意结点的功能；随时显示操作的结果。. 几种排序，随时给出某一趟的变化情况直接插入排序、折半插入排序、希尔排序；冒泡排序、快速排序；简单选择排序 4 堆排序要求是：1 从键盘输入一个表达式，如（23-（4×5.2-2.8））/5 2 支持+，-，×，/, 等符号 3 支持运算符的优先级4 支持括号的嵌套5 支持小数点及负数 6 有查错功能，如非法字符，小数点过多（如3.44.3），括号不匹配等错误。 以邻接矩阵的方式确定一个图，完成：建立并显示出它的邻接链表；给出某一确定顶点到所有其它顶点的最短路径；约瑟夫环问题 [问题描述]编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 [基本要求]利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。此题所用的循环链表中不需要“头结点”，请注意空表和非空表的界限。 [测试数据] m的初值为20，n 7?,7个人的密码依次为3，1，7，2，4，7，4，首先m 则正确的输出是什么？要求：输入数据：首先输入待处理人员数及他们的密码，然后输入m的初值，建立单循环链表。输出形式：建立一个输出函数，将正确的出列序列输出。 问题描述：设计一个程序实现两个任意长的整数的求和运算。 基本要求：利用双向循环链表，设计一个实现任意长的整数进行加法运算的演示程序。要求输入和输出每四位一组，组间用逗号隔开。如：1，0000，0000，0000，0000。 12. 串的查找和替换 问题描述：打开一篇英文文章，在该文章中找出所有给定的单词，然后对所有给定的单词替换为另外一个单词，再存盘。 13. 括号匹配问题 问题描述：假设一个算术表达式中可包含三种括号：圆括号，方括号和花括号且这三种括号可按任意次序嵌套使用。试利用栈的运算，编写判别给定表达式中所含括号是否正确配对出现的算法。 14. 一元多项式简单计算 问题描述：设计一个一元多项式简单的计算器。 基本要求：一元多项式简单计算器的基本功能为： 输入并建立多项式； 2 输出多项式； 3 两个多项式想加，建立并输出和多项式； 4 两个多项式相减，建立并输出差多项式。 实现提示：可选择带头结点的单向循环链表或单链表存储多项式，头结点可存放多项式的参数，如项数等。 15. 迷宫问题 问题描述：迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次试验终于得到它学习走迷宫的路线。设计一个计算机程序对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 要求：在给出入口和出口的前提下，给出动态的迷宫行走路线。 16. 八皇后问题 要求：试编写程序实现将八个皇后放置在国际象棋棋盘的无冲突的位置上的算法，并给出所有的解。 提示：在国际象棋上放置皇后时，任何一个皇后的水平、竖直和斜45o都不能有另一个皇后。解决该问题采用逐次试探的方法，即采用递归调用putchess函数的方法。首先将第一个皇后放于第一行第一列，然后开始向下一行递归。每一步递归中，首先检测待放置位置是否与已放置的皇后冲突，如不冲突，则进行下一行的放置，否则，选择该行的下一个位置进行检