数据结构与算法实训内容及要求

《数据结构与算法实训内容及要求》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法实训内容及要求Ⅰ基础题部分实训内容及要求一、顺序表操作1、显示2、插入3、查找（显示比较次数）4、删除（显示移动次数）5、排序（普通、快速，显示比较次数、移动次数）6、折半查找（显示比较次数）7、编程实现一个顺序表的就地逆置，即利用原表的存储空间将顺序表逆置。提高题：8*、要求以较高的效率实现删除顺序表中元素值在x到y(x和y自定)之间的所有元素。[解题思路]在顺序表中设置两个初值为0的下标变量i和j，其中，i为比较元素的下标，j为赋值元素的下标。依次取顺序表中下标为i的元素与x和y比较，假若是x到y之外

2、的元素，则赋值给下标为j的元素。这种算法比删除一个元素后立即移动其后面的元素的效率高得多。9*、编程实现将两个有序的顺序表进行合并，要求同样的数据元素只出现一次。[解题思路]由于两个顺序表中的元素呈有序排列，在进行合并的时候，依次比较，哪个顺序表的元素值小，就先将这个元素复制到新的顺序表中，若两个元素相等，则复制一个即可，这样一直到其中的一个顺序表结束，然后将剩余的顺序表复制到新的顺序表中即可。10*、有序插入（显示比较次数、移动次数），屏幕提示后，从键盘输入一个元素值，在经过排序的线性表中插入这个元素；屏幕显示比较次

3、数和移动次数，应有溢出判断和报告。顺序表操作菜单如下图所示:二、单链表操作1、创建2、显示3、查找（显示比较次数）4、插入5、删除（显示比较次数）6、将链接存储线性表逆置，即最后一个结点变成第1个结点，原来倒数第2个结点变成第2个结点，如此等等。7、生成有序的两个单链表A和B（链表的数据和个数自定），其首结点指针分别为a和b，要求将两个单链表合并为一个有序的单链表C，其首结点指针为c，并且合并后的单链表的数据不重复。8、将一个首结点指针为a的单链表A分解成两个单链表A和B，其首结点指针分别为a和b，使得链表A中含有原链

4、表A中序号为奇数的元素，而链表B中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。单链表操作菜单如下图所示:三、二叉树操作(一)实现功能：1：初始化2：显示(Map.txt)3：先序遍历(递归法)4中序遍历(递归法)5：后序遍历(递归法)6：统计叶子结点数目7：二叉树深度8：左右子树交换9：生成二叉排序树a：查找排序树中的结点b：删除排序树中的结点c：先序遍历(非递归法)d：层次遍历e：凹入法表示二叉树f：广义表表示二叉树(二)二叉树操作1、创建。2、用递归方法分别先序、中序、后序遍历以Tree为根指针的二叉树。

5、3、编写递归算法，计算二叉树中叶子结点的数目。4、编写递归算法，计算二叉树的深度。5、编写递归算法，将二叉树中所有结点的左、右子树相互交换。6、使用数组elem中的随机数序列（以0表示结束，不包括0），生成以Tree为根指针的二叉排序树。7、在以Tree为根指针的二叉排序树中查找结点。8、从以Tree为根指针的二叉排序树中删除结点（适用各种位置的结点）。9、用非递归算法，先序遍历以Tree为根指针的二叉树。提示：用数组BiTNode*stack[max]构成堆栈，利用这个堆栈实现功能。10、对以Tree为根指针的二叉树

6、，从根结点开始，逐层从左到右输出各结点的数据。提示：用数组BiTNode*queue[max]构成队列，利用这个队列实现功能11、用凹入表示法的表示以Tree为根指针的二叉树，例如：//324//123//746//690//56712、用广义表表示以Tree为根指针的二叉树，例如//(324(123(746,690),567))提高题：13*、根据Huffman编码原理，使用数组elem中的随机数序列（以0表示结束，不包括0）作为结点的权重，生成赫夫曼树，以及赫夫曼编码，计算平均带权径长度。14*、（1）随机生成二叉

7、树。（2）生成并保存先（后）序、中序输出序列。（3）按照保存的一对输出序列恢复出二叉树。（4）生成先（后）序输出序列。二叉树操作菜单如下:Ⅱ综合题部分实训内容及要求要求：第一题和第二题为必做题，第三题到第五题为选做题。最后，需要提交的内容包括：每个题目的源代码，以及该题的说明文档。说明文档的具体要求见最后的附录A。一、运动会分数统计问题描述参加运动会的n个学校编号为1~n。比赛分成m个男子项目和w个女子项目，项目编号分别为1~m和m+1~m+w。由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1

8、；还有些项目只取前三名，得分顺序为5，3，2。写一个统计程序产生各种成绩单和得分报表。基本要求产生各学校的成绩单，内容包括各校所取得的每项成绩的项目号、名次（成绩）、姓名和得分；产生团体总分报表，内容包括校号、男子团体总分、女子团体总分和团体总分。测试数据对于n=4,m=3,w=2，编号为奇数的项目取前五名，编号为偶数的项目取前三