数据结构实验.rar

实验一： 1、（必做题）采用函数统计学生成绩：输入学生的成绩，计算并输出这些学生的最低分、最高分、平均分。 2、（必做题）采用递归和非递归方法计算k阶裴波那契序列的第n项的值，序列定义如下： f0=0, f1=0, …, fk-2=0, fk-1=1, fn= fn-1+fn-2+…+fn-k (n>=k) 要求：输入k(1<=k<=5)和n(0<=n<=30)，输出fn。 3、（选做题）采用递归和非递归方法求解汉诺塔问题，问题描述如下： 有三根柱子A、B、C，在柱子A上从下向上有n个从大到小的圆盘，在柱子B和C上没有圆盘，现需将柱子A上的所有圆盘移到柱子C上，可以借助柱子B，要求每次移动一个圆盘，每根柱子上的圆盘只能大的在下，小的在上。 要求：输入n，输出移动步骤。 实验二： 1、（必做题）每个学生的成绩信息包括：学号、语文、数学、英语、总分、加权平均分；采用动态方法创建数组用于存储若干学生的成绩信息；输入学生的学号、语文、数学、英语成绩；计算学生的总分和加权平均分（语文占30%，数学占50%，英语占20%）；输出学生的成绩信息。 2、（必做题）可以在数组末尾追加新学生的成绩信息；可以根据学号，删除该学生的成绩信息。 3、（选做题）可以根据学号或总分，升序排序学生的成绩信息。 实验三： 1、（必做题）每个学生的成绩信息包括：学号、语文、数学、英语、总分、加权平均分；采用链表存储若干学生的成绩信息；输入学生的学号、语文、数学、英语成绩；计算学生的总分和加权平均分（语文占30%，数学占50%，英语占20%）；输出学生的成绩信息。 2、（必做题）可以在链表末尾追加新学生的成绩信息；可以根据学号，删除该学生的成绩信息。 3、（选做题）可以根据学号或总分，升序排序学生的成绩信息。 实验四： 1、（必做题）假设有序表中数据元素类型是整型，请采用顺序表或（带头结点）单链表实现： （1）OrderInsert(&L, e, int (*compare)(a, b)) //根据有序判定函数compare，在有序表L的适当位置插入元素e； （2）OrderInput(&L, int (*compare)(a, b)) //根据有序判定函数compare，并利用有序插入函数OrderInsert，构造有序表L； （3） OrderMerge(&La, &Lb, &Lc, int (*compare)()) //根据有序判定函数compare，将两个有序表La和Lb归并为一个有序表Lc。 2、（选做题）请实现： （1）升幂多项式的构造，升幂多项式是指多项式的各项按指数升序有序，约定系数不能等于0，指数不能小于0； （2）两个升幂多项式的相加。 实验五： 1、（必做题）假设栈中数据元素类型是字符型，请采用顺序栈实现栈的以下基本操作： （1）Status InitStack (&S) //构造空栈S； （2）Status Push(&S, e) //元素e入栈S； （3）Status Pop(&S, &e) //栈S出栈，元素为e。 2、（必做题）假设队列中数据元素类型是字符型，请采用链队列实现队列的以下基本操作： （1）Status InitQueue(&Q) //构造空队列Q； （2）Status EnQueue(&Q, e) //元素e入队列Q； （3）Status DeQueue (&Q, &e) //队列Q出队列，元素为e。 3、（必做题）请实现：对于一个可能包括括号{}、[]、()的表达式，判定其中括号是否匹配。 实验六： 1、（必做题）假设二叉树中数据元素类型是字符型，请采用二叉链表实现二叉树的以下基本操作： （1）根据二叉树的先序序列和中序序列构造二叉树； （2）根据先序遍历二叉树； （3）根据中序遍历二叉树； （4）根据后序遍历二叉树。 测试数据包括如下错误数据： 先序：1234；中序：12345 先序：1234；中序：1245 先序：1234；中序：4231 2、（必做题）对于一棵二叉树，请实现： （1）计算二叉树的叶子数目； （2）计算二叉树的深度。 3、（选做题）给定n个权值，请构造它们的最优二叉树（赫夫曼树）。 期末大实验： 一、任意长十进制整数加法 二、车厢调度 三、赫夫曼编/译码 四、无线广播部署