数据结构与C语言综合训练实习
86 机房机位预定系统 87 万年历查询程序。 88 汉诺塔移动 请选择系统功能项： a、成绩录入 b、成绩显示 c、成绩保存 d、成绩排序 e、成绩修改（要求先输入密码） f、成绩统计 20台机器，编号1到20，从早八点到晚八点。两小时一个时间段，每次可预定一个时间段。功能要求： （1）系统以菜单方式工作 （2）查询，根据输入时间，输出机位信息。 （3）机位预定，根据输入的时间查询是否有空机位，若有则预约，若无则提供最近的时间段， 另：若用户在非空时间上机，则将用户信息列入等待列表。 （4）退出预定，根据输入的时间，机器号撤销该事件的预定！ （5）查询是否有等待信息，若有则提供最优解决方案（等待时间尽量短），若无则显示提示信息。 功能要求： （1）提供菜单方式选择 （2）输入年份、月份、日期，计算得到的是这一天据今天有多少天，星期几； （3）输入公历的年月日，输出农历年月日。 （4）输入农历节气，输出当年农历的年月日及公历年月日。可以假定只涉及年份是1940年到2040年。 输入盘子数（2个以上有效），移动速度，开始演示汉诺塔移动的步骤，要求：盘子，A，B，C柱需要自己绘制，初始时盘子在A柱上通过B柱最终移动到C柱上，显示出盘子在几个 柱之间的移动过程。 21
数据结构与C语言综合训练实习
89 运动会比赛计分系统 要求：初始化输入：N-参赛学校总数，M-男子竞赛项目数，W-女子竞赛项目数 各项目名次取法有如下几种： 取前5名：第一名得分7分，第二名得分5，第三名得分3，第四名得分2，第五名得分1；取前3名：第一名得分5，第二名得分3，第三名得分2； 功能要求： （1）系统以菜单方式工作 （2）由程序提醒用户填写比赛结果，输入各项目获奖运动员信息。 （3）所有信息记录完毕后，用户可以查询各个学校的比赛成绩 （4）查看参赛学校信息和比赛项目信息等。 Skip List作为有序链表结构的一种扩展，如下图所示，其中a是普通的单链表；而b是在次基础上加上第二层（level 2）的额外指针，这些额外的指针指向间隔为2的下一个结点，skip list因此得名；类似的c是加上level 3后的skip list；d是加上level 4后的skip list。 90 Skip List的实现及分析 基本结构示意图 Skip List上查找的基本思想是先从最高的Level层上查找，找到key所在的范围后，再从较低的层次继续重复查找操作，直到Level 1。 22
数据结构与C语言综合训练实习
91 B-Trees的实现及分析 插入操作的示意图 Skip List上的删除操作只需直接删除元素即可（包括指针的修整）。 构造并实现Skip List的ADT，同时实现双向Skip List的ADT及循环Skip List的ADT。 基本要求 ① ADT中应包括初始化、查找、插入、删除等基本操作。 ② 分析各基本操作的时间复杂性。 ③ 针对一个实例实现Skip List的动态演示(图形演示)。 B-Trees是一类满足特殊条件的M路查找树。首先说明M路查找树，M路查找树是二元查找树的一般化，其结构如下图所示的3路查找树：M路查找树中的任一结点至多存放M-1个数据，并至多拥有M棵子树；每个结点中的数据按升序排列V1 < V2 < ... Vk (k <= M-1)，每个数据Vi都存在一棵左子树和一棵右子树，如果左子树不空的话，该子树中所有结点的值都小于Vi,如果右子树不空的话，该子树中所有结点的值都大于Vi。 23
数据结构与C语言综合训练实习
3-路查找树的结构示意图 B-Trees是满足如下两个条件的M路查找树： ① 所有叶结点的高度相同。 ② 除根之外的所有结点都至少是半满的，即该结点包含M/2或更多的值。 下图是一个B-树的实例。 3-路B-树的结构示意图 基本要求 ① 实现在B-树上的查找，并分析其时间复杂性。 ② 实现B-树的ADT，包括其上的基本操作：结点的加入和删除。 ③ 要求B-树结构中的M=3或5，实现其中的一种即可。 ④ 实现基本操作的演示。 24
数据结构与C语言综合训练实习
92 AVL Tree的实现及分析 93 汽车租借公司的管理 AVL(Adelson-Velskii and Landis)树是一株平衡的二元查找树。一株平衡的二元树就是指对其每一个结点，其左子树和右子树的高度之差不超过1。下图就是一个AVL树的实例。 编写程序实现AVL树的判别；并实现AVL树的ADT，包括其上的基本操作：结点的加入和删除。BST和AVL的差别就在平衡性上，所以AVL的操作关键要考虑如何在保持二元查找树定义条件下对二元树进行平衡化。 基本要求 ① 编写AVL树判别程序，并判别一个二元查找树是否为AVL树。二元查找树用其先序遍历结果表示，如：5，2，1，3，7，8。 ② 实现AVL树的ADT，包括其上的基本操作：结点的加入和删除；另外包括将一般二元查找树转变为AVL树的操作。 (1) 问题描述 设计数据结构及算法完成某个汽车租借公司日常工作的组织与管理。该管理系统的基本管理对象为汽车，每台汽车用一个license number进行唯一标识。每个汽车存在三种可能状态： ·可以租借（available for rent） ·已借（rented） ·修理中（in repair） 其中在available队列中汽车应该依据汽车行驶过的路程进行排序，行驶路程最少的汽车排在最前面。在rented队列中的汽车应依据其预期返回时间进行排序，排在最前的 应是预期最早返回的汽车。 (2) 课程设计目的 应用线性数据结构存储信息，并能够应用上面的基本操作实现事务管理。 (3) 基本要求 ① 用三个链表组织三种状态的汽车。 ② 能够实现租借的日常事务：引入新车，租借，收费，修理等。 ③ 租借收费应根据汽车行驶的路程及借去的时间综合计算得出，路程收费标准如下： 25