2017年武汉工程大学数据结构(C语言版)之数据结构(C语言版)复试仿真模拟三套题
● 摘要
目录
2017年武汉工程大学数据结构(C语言版) 之数据结构(C语言版) 复试仿真模拟三套题（一） ... 2 2017年武汉工程大学数据结构(C语言版) 之数据结构(C语言版) 复试仿真模拟三套题（二） . 11 2017年武汉工程大学数据结构(C语言版) 之数据结构(C语言版) 复试仿真模拟三套题（三） . 18
第 1 页，共 24 页
一、应用题
1． 某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号 机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：
请添加必要的信号量和P 、V （或wait （ ）、signal （ ））操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。
【答案】（1）互斥资源：取机号，故设一个互斥信号量mutex 。
（2）同步问题：顾客需要获得空座位等待叫号，当营业员空闲时，将选取一位顾客为其服务。空座位的有、 无影响等待顾客数量，顾客的有、无决定两营业员是否能开始服务。另外，顾客获得空座位后，需要等待叫号和被服务，顾客与营业员就服务何时开始有同步关系。设信号量teller ，customer 和mutex 初值分别为0，0和1，设waiting 为整型量，表示排队的储户数量，其初始为0, 表示顾客初始时为0, 最大不超过10 （10把座椅），各进程的具体实现如下所示：
//座椅数，也是最多排队的储户数
//定义信号量
第 2 页，共 24 页 //等待储户的柜员资源
//排队等待服务的储户数量
//对排队机操作的互斥量
//在座椅上休息等待的储户数
//储户进程
//先获得排队机
//若还有座椅则取号
//取号，占用座椅等待叫号
//告知系统储户加1
//释放排队机
//若没有座椅了，则不取号
//不取号，释放排队机
//离开
//并发调度无限循环
//叫号
//需要获得排队机的控制权
//将等候的顾客数减1
//提供柜员服务
//释放排队机
//为储户服务
//等待柜员叫号
//进入窗口被服务
2． 假定在一个8位字长的计算机中运行下列C 程序段：
若编译器编译时将8个8位寄存器R1〜R8分别分配给变量
回答下列问题。（提示：带符号整数用补码表示）
（1）执行上述程序段后，寄存器Rl 、R5和R6的内容分别是什么？（用十六进制表示） （2）执行上述程序段后，变量m 和kl 的值分别是多少？（用十进制表示） 请
（3）上述程序段涉及带符号整数加/减、无符号整数加/减运算，这四种运算能否利用同一个
第 3 页，共 24 页
加法器及辅助电路实现? 简述理由。
（4）计算机内部如何判断带符号整数加/减运算的结果是否发生溢出? 上述程序段中，哪些带符号整数运算语句的执行结果会发生溢出？
【答案】（1）无符号整数运算，（Rl ） =x=134=10000110B=86H、（R5）=x-y=246=10010000B=90H、（R6）=x+y=01111100B=7CH。
（2） m 的机器数与x 的机器数相同为86H=1000 0110B，解释为带符号整数（用补码表示）时，其值为-111 1010B= -112; 同理kl=（m-n ）=（x-y ）=90H=1001 0000B，解释为带符号整数（用补码表示）时，其值为-111 1010B=-112；
（3）四种运算可以利用同一个加法器及辅助电路实现，n 位加法器实现的是模2n 无符号整数加法运算。对于无符号整数a 和b , a+b可以直接用加法器实现，而实现；对于带符号整数用补码表示，补码加减运算公式为
：
，所以四种运算都可在n 位加法器
中实现。
（4）判断溢出的方法有3种：一位符号位、进位位和双符号位。上述程序段中只有
语句会发 生溢出，因为2个带符号整数均为负数，它们相加之后，结果小于8位二进制所能表示的最小负数。
3． 如果两个串含有相等的字符，能否说它们相等？
【答案】仅从两串含有相等的字符，不能判定两串是否相等，两串相等的充分必要条件是两串长度相等且对应位置上的字符相同（即两串串值相等）。
4． 解答问题。设有数据逻辑结构为：
（1）画出这个逻辑结构的图示。
（2）相对于关系R ，指出所有的开始结点和终端结点。
（3）分别对关系R 中的开始结点，举出一个拓扑序列的例子。
（4）分别画出该逻辑结构的正向邻接表和逆向邻接表。
【答案】
⑴如图1所示：
图1
第 4 页，共 24 页