《数据结构》课程设计——题目54学时.doc

数据结构课程设计题目(程序实现采用C语言)题目1：猴子选王（学时：3）一堆猴子都有编号，编号是1，2，3 .m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。要求：m及n要求从键盘输入，存储方式采用向量 及链表两种方式实现该问题求解。 题目2 ：字符逆转（学时：3） 从键盘读入一个字符串，把它存入一个链表（每个结点存储1个字符），并按相反的次序将字符串输出到显示屏。题目3 ：工资核算（学时：3）设有一个单位的人员工资有如下信息：name、department、 base pay、allowance、total。现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata取出工资数据并给每个人的base pay增加100元，增加后将工资数据显示于屏幕(每行1人)。题目4：满足条件的有序表生成（学时：3）已知三个有序表A、B、C，它们皆由同一类元素构成，现要求对于表A作以下运算而获得有序表D：排出A中所有的既在B中又在C中出现的元素。另外该任务要求具有建立有序表功能以及输出有序表到屏幕的功能。先判断b和c。在从头开始找a。for(i=0;i10;i+)for(j=0;j10;j+)if(bi=cj)for(k=0;k10;k+)if(ak=bi)ak=0;题目5：一元多项式的减法（学时：6）摄有两个一元多项式A(x),B(x)，请完成运算A(x)+B(x)、A(x)-B(x)，要求多项式采用链表进行存储。另外该任务要求具有建立多项式链表以及输出多项式到屏幕的功能。题目6：床位分配（学时：6）某客店有N个等级的房间，第k级客房有A（k）个，每个房间有B（k）个单人床，以菜单调用方式设计为单身旅客分配床位以及离店时收回床位的程序。/view/7202b929b4daa58da0114a2d.html1要求分配成功时，印出旅客姓名、年龄、性别、到达日期、客房等级、房间号及床位号；2分配不成功时，允许更改房间等级，3若不更改等级，印出“满客”提示。房间等级房间号床位一等A10112341021234二等B201123202123三等C3011230212303121 0 02 0 13 0 24 0 31 1 02 1 13 1 24 1 31 2 02 2 13 2 2Null 2 31 3 02 3 13Null1 4 02 4 1Null42Null331 5 02NullNull1 6 02Null 6 2Null36A47总共有三个等级的房间（a。b。c）A等有2间房间，每间房间4张床 8B等有2间房间，每间房间3张床 6 C等有3间房间，每间房间2张床 6 总过有20张床题目7：文本文件单词的检索及计数（学时：6）要求编程建立一个文本文件，每个单词不包括空格及跨行，单词由字符序列构成且区分大小写，完成以下功能：统计给定单词在文本文件中出现的总次数、检索输出某单词在文本文件中首次出现的行号及位置。1 建立文本文件 有空格有跨行有大小写2 要有读入的功能3 函数（ ，单词/大写版单词 ）题目8：二叉树的遍历（学时：6） 二叉树以lson-rson链接方式存储，以菜单方式设计并完成功能任务：建立并存储树、输出前序遍历结果、输出中序遍历结果、输出后序遍历结果、交换左右子树、统计高度，其中对于中序、后序的遍历运算要求采用非递归方式。题目9：创建二叉排序树（学时：3） 二叉排序树以lson-rson链接方式存储，编写能够通过键盘输入建立二叉排序树，并在建立完立即在屏幕显示中序遍历结果的程序。题目10：霍夫曼编码应用（学时：3） 假设一串由大写字母构成的电文，采用霍夫曼规则对其进行编码，以菜单方式设计并完成功能任务：建立霍夫曼树、霍夫曼编码生成、编码文件译码。题目11：关键路径寻找（学时：6）对于给定的一个工程施工图，该图以边为单位从键盘输入，编写能够找出该图的关键路径的程序。题目12：堆排序实现（学时：3）假设有一个数据类型为整型的一维数组A，A 中的数据元素呈无序状态，编写一个采用堆排序法将A中的数据元素按由小到大进行排序的程序。题目13基数排序的实现（学时：3）A为每个关键字不超过3位的十进制整数关键字集合，试编写一个采用静态链表组织模式实