2017年成都信息工程大学数据结构复试实战预测五套卷
● 摘要
一、应用题
1． 已知有5个顶点的图G 如下图所示
请回答下列问题
（1）写出图G 的邻接矩阵A （行、列下标从0开始）。
（2）求什么？
【答案】（1）邻接矩阵为
矩阵中位于0行3列元素值的含义是什么？ 非零元素的含义是（3）若已知具有n （n>=2）个顶点的邻接矩阵为B ，则
（2）
为：
0行3列的元素的含义是顶点0到顶点3间是相通的，并且路径长度为2的路径有2条。 （3）中非零元素的含义是：假设此顶点位于i 行j 列，表示从i 结点到j 结点路径长度为m 的路径的条数。
2． 试比较顺序文件、索引非顺序文件、索引顺序文件、哈希文件的存储代价，检索、插入、删除记录时的优点和缺点。
【答案】（1）顺序文件只能顺序查找，优点是批量检索速度快，不适于单个记录的检索。顺序文件不能像顺序表那样插入、删除和修改，因文件中的记录不能象向量空间中的元素那样“移动”，只能通过复制整个文件实现上述操作。
（2）索引非顺序文件适合随机存取，不适合顺序存取，因主关键字未排序，若顺序存取会引起磁头频繁移动。索引顺序文件是最常用的文件组织，因主文件有序，既可顺序存取也可随机存取。索引非顺序文件是稠密索引，可以“预查找”，索引顺序文件是稀疏索引，不能“预查找”，但由于索引占空间较少，管理要求低，提高了索引的查找速度。
（3）散列文件也称直接存取文件，根据关键字的哈希函数值和处理冲突的方法，将记录散列到外存上。这种文件组织只适用于像磁盘那样的直接存取设备，其优点是文件随机存放，记录不必排序，插入、删除方便，存取速度快，无需索引区，节省存储空间。缺点是散列文件不能顺序存取，且只限于简单查询。经多次插入、删除后，文件结构不合理，需重组文件，这很费时。
3． 某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号 机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：
请添加必要的信号量和P 、V （或wait （ ）、signal （ ））操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。
【答案】（1）互斥资源：取机号，故设一个互斥信号量mutex 。
（2）同步问题：顾客需要获得空座位等待叫号，当营业员空闲时，将选取一位顾客为其服务。空座位的有、 无影响等待顾客数量，顾客的有、无决定两营业员是否能开始服务。另外，顾客获得空座位后，需要等待叫号和被服务，顾客与营业员就服务何时开始有同步关系。设信号量teller ，customer 和mutex 初值分别为0，0和1，设waiting 为整型量，表示排队的储户数量，其初始为0, 表示顾客初始时为0, 最大不超过10 （10把座椅），各进程的具体实现如下所示：
//座椅数，也是最多排队的储户数
//定义信号量
//等待储户的柜员资源
//排队等待服务的储户数量
//对排队机操作的互斥量
//在座椅上休息等待的储户数
//储户进程
//先获得排队机
//若还有座椅则取号
//取号，占用座椅等待叫号
//告知系统储户加1
//释放排队机
//等待柜员叫号
//进入窗口被服务
//若没有座椅了，则不取号
//不取号，释放排队机
//离开
//并发调度无限循环
//叫号
//需要获得排队机的控制权
//将等候的顾客数减1
//提供柜员服务
//释放排队机
//为储户服务
4． 已知有6个顶点（顶点编号为0--5）的有向带权图G , 其邻接矩阵A 为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。
要求：
（1）写出图G 的邻接矩阵A 。
（2）画出有向带权图G 。
（3）求图G 的关键路径，并计算该关键路径的长度。
【答案】（1）由题可以画出待定上三角矩阵的结构图如下（图中? 为待定元素）：