2017年重庆交通大学数据结构(同等学力加试)复试仿真模拟三套题
● 摘要
一、应用题
1． 假定有下列，
矩阵（n 为奇数）
如果用一维数组B 按行主次序存储A 的非零元素，问： （1）A 中非零元素的行下标与列下标的关系； （2）给出A 中非零元素的下标位在B 中的位置公式。
【答案】（1）主对角线上元素的坐标是i=j，副对角线上元素的坐标i 和j 有所以A 中非零元素的行下标和列下标的关系是
或
的关系，
与B 中的下标R 的关系；
给出利用的下标
定
（3）假定矩阵中每个元素占一个存储单元且B 的起始地址为
（2）非零元素分布在两条主、副对角线上，除对角线相交处一个元素（下称“中心元素”）外，其余每行都有两个元素。主对角线上的元素，在向量B 中存储的下标
是
副对角线上的元素，在中心元素前，在向量B
中存储的下标是
在中心元素后，其下标如下：
（3）在B 中的位置如下：
2． 某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号 机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：
请添加必要的信号量和P 、V （或wait （ ）、signal （ ））操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。
【答案】（1）互斥资源：取机号，故设一个互斥信号量mutex 。
（2）同步问题：顾客需要获得空座位等待叫号，当营业员空闲时，将选取一位顾客为其服务。空座位的有、 无影响等待顾客数量，顾客的有、无决定两营业员是否能开始服务。另外，顾客获得空座位后，需要等待叫号和被服务，顾客与营业员就服务何时开始有同步关系。设信号量teller ，customer 和mutex 初值分别为0，0和1，设waiting 为整型量，表示排队的储户数量，其初始为0, 表示顾客初始时为0, 最大不超过10 （10把座椅），各进程的具体实现如下所示：
//座椅数，也是最多排队的储户数
//定义信号量
//储户进程
//先获得排队机
//若还有座椅则取号
//取号，占用座椅等待叫号
//告知系统储户加1
//释放排队机
//若没有座椅了，则不取号
//不取号，释放排队机
//离开
//等待储户的柜员资源
//排队等待服务的储户数量
//对排队机操作的互斥量
//在座椅上休息等待的储户数
//等待柜员叫号
//进入窗口被服务
//并发调度无限循环
//叫号
//需要获得排队机的控制权
//将等候的顾客数减1
//提供柜员服务
//释放排队机
//为储户服务
3． 在某程序中，有两个栈共享一个一维数组空间的栈底。
分别是两个栈
（1）对栈1、栈2, 试分别写出（元素x ）入栈的主要语句和出栈的主要语句。 （2）对栈1、栈2, 试分别写出栈满、栈空的条件。 【答案】（1）入栈主要语句
出栈主要语句
（2）
4． 一个ISAM 文件除了主索引外，还包括哪两级索引？
【答案】ISAM 文件有三级索引：磁盘组、柱面和磁盘，柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时，可建立柱面索引的索引一主索引。故还包括的两级索引是盘组和磁道。
5． 在模试匹配KMP 算法中所用失败函数的定义中，为何要求真子串？且为最大真子串？
【答案】失败函数（即next ）的值只取决于模式串自身，若第j 个字符与主串第i 个字符失配时，假定主串不回溯，模式串用第k （即next[j]个字符与第i 个相比，有
为了
不因模式串右移与主串第i 个字符比较而丢失可能的匹配，对于上式中可能存在的多个k 值，应取其中最大的一个。这样，因j-k 最小，即模式串向右滑动的位数最小，避免因右移造成可能匹配的丢失。
两头匹配的
相关内容
相关标签