31 哈希表应用
【问题描述】
利用哈希表进行存储。 【任务要求】
任务要求：针对一组数据进行初始化哈希表，可以进行显示哈希表，查找元素，插入元素，删除元素，退出程序操作。
设计思想：哈希函数用除留余数法构造，用线性探测再散列处理冲突。 设计目的：实现哈希表的综合操作
简体中文控制台界面：用户可以进行创建哈希表，显示哈希表，查找元素，插入元素，删除元素。
显示元素：显示已经创建的哈希表。
查找元素：查找哈希表中的元素，分为查找成功和查找不成功。 插入元素：在哈希表中，插入一个元素，分为插入成功和失败。 删除元素：在已有的数据中，删除一个元素。 退出系统：退出程序。 【测试数据】
自行设定，注意边界等特殊情况。
32 商品货架管理
[问题描述]
商品货架可以看成一个栈，栈顶商品的生产日期最早，栈底商品的生产日期最近。 上货时，需要倒货架，以保证生产日期较近的商品在较下的位置。 [基本要求]
针对一种特定商品，实现上述管理过程。 [实现提示]
用栈模拟货架和周转空间。 [测试数据]
由学生依据软件工程的测试技术自己确定。注意测试边界数据，如空栈。
33 停车场管理
[问题描述]
设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。
31
[测试数据]
设n=2,输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3， 20）， （‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。 [基本要求]
以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。
[实现提示]
需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。
34 稀疏矩阵的完全链表表示及其运算
[问题描述]
稀疏矩阵的每个结点包含down，right，row，col和value五个域。用单独一个结点表示一个非零项，并将所有结点连接在一起，形成两个循环链表。使得第一个表即行表，把所有结点按照行序（同一行内按列序）用right域链接起来。使得第二个表即列表，把所有结点按照列序（同一列内按行序）用down链接起来。这两个表共用一个头结点。另外，增加一个包含矩阵维数的结点。稀疏矩阵的这种存储表示称为完全链表表式。
实现一个完全链表系统进行稀疏矩阵运算，并分析下列操作函数的计算时间和额外存储空间的开销。
（2）设计目的
认识和掌握稀疏矩阵的完全链表表示；能够建立并运用这种存储结构 (3) 基本要求
建立一个用户友好、菜单式系统进行下列操作，并使用合当的测试数据测试该系统。 读取一个稀疏矩阵建立其完全链表表示 输出一个稀疏矩阵的内容 删除一个稀疏矩阵 两个稀疏矩阵相加 两个稀疏矩阵相减 两个稀疏矩阵相乘 稀疏矩阵的转置 （4）实现提示 链表上的操作。
35 电视大赛观众投票及排名系统（排序应用）
32
【问题描述】
在很多的电视大赛中，通常当选手表演结束后，现场观众通过手中的按键对参赛选手进行投票，然后对选手获得的票数进行统计，从高到低进行降序排序，从而自动产生冠军、亚军和季军。现在要求编写一程序模拟实现上述系统的功能。 【实现提示】
在本例中，首先输入参赛选手的人数（范围为1-9个），然后根据人数通过malloc函数来开辟存放选手信息的顺序表。将选手的编号和姓名依此存入顺序表单元中，观众通过按键进行投票，按’1’为1号选手投票，按’2’为2号选手投票，以此类推，以按’0’作为投票结束标志。投票结束后进行排序，在此采用希尔排序，然后为每个选手计算名次，得票相同的名次也相同，
（1）存储类型的定义
参赛选手信息存储类型的定义： typedef struct node{
char name[8]; /*选手姓名*/ int num; /*选手编号*/ int score; /*选手得分*/ int tax; /*选手名次*/ }Node;
36 学生搭配问题。
一班有m个女生,有n个男生（m不等于n），现要开一个舞会。男女生分别编号坐在舞池的两边的椅子上。每曲开始时，依次从男生和女生中各出一人配对跳舞，本曲没成功配对者坐着等待下一曲找舞伴。
请设计一系统模拟动态地显示出上述过程，要求如下： （1）输出每曲配对情况；
（2）计算出任何一个男生（编号为X）和任意女生（编号为Y），在第K曲配对跳舞的情况.至少求出K的两个值；
（3） 尽量设计出多种算法及程序。 提示：用队列来解决比较方便.
37 敢死队问题
有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。
排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。
要求：至少采用两种不同的数据结构的方法实现。
33
38 数制转换问题
任意给定一个M进制的数x ，请实现如下要求 : 1) 求出此数x的10进制值（用MD表示）
2) 实现对x向任意的一个非M进制的数的转换。
3) 至少用两种或两种以上的方法实现上述要求（用栈解决，用数组解决，其它方法解决）。
39迷宫问题（栈）
以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 要求：
首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向，如：对于下列数据的迷宫，输出的一条通路为：（1，1，1），（1,2,2）,(3,2,3),(3,1,2),?。 测试数据：
迷宫的测试数据如下：左下角（1，1）为入口，右下角（8，9）为出口。 实现提示：
计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设的迷宫没有通路。 可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。 选做内容：（1）编写递归形式的算法，求得迷宫中所有可能的通路；（2）以方阵形式输出迷宫及其通路。
40 迷宫问题（队列）（同上）
以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 要求：
首先实现一个以链表作存储结构的队列，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向，如：对于下列数据的迷宫，输出的一条通路为：（1，1，1），（1,2,2）,(3,2,3),(3,1,2),?。 测试数据：
迷宫的测试数据如下：左下角（1，1）为入口，右下角（8，9）为出口。 实现提示：
计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设的迷宫没有通路。 可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、
34
西、北四个方向可通。 选做内容：
（1）编写递归形式的算法，求得迷宫中所有可能的通路； （2）以方阵形式输出迷宫及其通路。
41 最短路
【问题描述】 给定一个计算机网络以及机器间的双向连线列表，每一条连线允许两端的计算机进行直接的文件传输，其他计算机间若存在一条连通路径，也可以进行间接的文件传输。请写出程序判断：任意指定两台计算机，它们之间是否可以进行文件传输？
【输入要求】 输入若干测试数据组成。对于每一组测试，第1行包含一个整数N（≤10000），即网络中计算机的总台数，因而每台计算机可用1到N之间的一个正整数表示。接下来的几行输入格式为I C1 C2或者 C或者C C1C2或者S，其中C1和C2是两台计算机的序号，I表示在C1和C2间输入一条连线，C表示检查C1和C2间是否可以传输文件，S表示该组测试结束。当N为0时，表示全部测试结束，不要对该数据做任何处理。 【输出要求】 1 5 4 2 3 9 8 7 6 500m 200m 200m 100m 200m 50m 100m 500m 700m 100m 100m
对每一组C开头的测试，检查C1和C2间是否可以传输文件，若可以，则在一行中输出“yes”，否则输出“no”。当读到S时，检查整个网络。若网络中任意两机器间都可以传输文件，则在一行中输出“The network is connected.”，否则输出“There are k components.”,其中k是网络中连通集的个数。两组测试数据之间请输出一空行分隔。
42 拦截导弹
问题描述
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
一行，为导弹依次飞来的高度
输出格式
两行，分别是最多能拦截的导弹数与要拦截所有导弹最少要配备的系统数
样例输入
389 207 155 300 299 170 158 65
样例输出
6 2
43 二叉搜索树
35