当前位置：问答库＞考研试题

一、算法设计题

1． 给定(已生成) 一个带表头结点的单链表，设head 为头指针，结点的结构为(data，next) ，data 为整型元素，next 为指针，试写出算法:按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间(要求:不允许使用数组作辅助空间) 。

【答案】算法如下:

//head是带头结点的单链表的头指针

//本算法按递增顺序输出单链表各结点的值，并释放结点所占的存储空间

//循环到仅剩头结点

//pre为元素最小值结点的前驱结点的指针

//P为工作指针

//记住当前最小值结点的前驱

//输出元素最小值结点的数据

//删除元素值最小的结点，释放结点

空间

//释放头结点

2． 设从键盘输入一整数的序列:a 1，a 2，a 3，... ，a n ，试编写算法实现:用栈结构存储输入的整数，

当

时，将

入栈；当

时，输出栈顶整数并出栈。算法应对异常情况(入栈满等) 给

出相应的信息。

【答案】算法如下

:

栈空间容量

//s是元素为整数的栈，本算法进行入栈和出栈操作

//top为栈顶指针，定义top ＝0时为栈空

//n个整数序列进行处理

//从键盘读入整数序列

//读入的整数不等于﹣1时人栈

//读入的整数等于﹣1时出栈

//算法结束。

3． 写一算法找出n 个数的最大值和最小值，要求最坏条件下的元素比较次数为

。

【答案】算法如下:

用最多3n/2－2次比较在n 个元素r 中选出最大值和最小值

n 为偶数时

r 最小值

("最大值) ；

4． 若x 和y 是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。

【答案】算法如下:

//本算法判断两个顺序存储的串x 和y 是否相等，相等返回1，否则返回

//对应字符相等，指针后移

5． 写算法将单链表11拆成二个链表，其中以11为头的链表保持原来向后的链接，另一个链表的头为12，其链接方向与11相反，11包含原链表的奇数序号的结点，12包含原链表的偶数序号的结点。

【答案】算法如下:

//本算法将链表L1拆成L1和L2两个链表，L2链接方向与L1相反

//空链表

//奇数序号结点在L1中

//偶数序号

结点逆置插入到L2中

//置L1

表尾

二、应用题

6． 某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时, 若有空座位, 则到取号机上领取一个号, 等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时, 通过叫号选取一位顾客, 并为其服务。顾客和营业员的活动过程描述如下:

请添加必要的信号量和P 、V(或wait （ ）、signal （ ）) 操作, 实现上述过程中的互斥与同步。要求写出完整的过程, 说明信号量的含义并赋初值。

【答案】(1)互斥资源:取机号, 故设一个互斥信号量mutex 。

(2)同步问题:顾客需要获得空座位等待叫号, 当营业员空闲时, 将选取一位顾客为其服务。空座位的有、无影响等待顾客数量, 顾客的有、无决定两营业员是否能开始服务。另外, 顾客获得空座位后, 需要等待叫号和被服务, 顾客与营业员就服务何时开始有同步关系。设信号量teller , customer 和mutex 初值分别为0, 0和1, 设waiting 为整型量, 表示排队的储户数量, 其初始为0, 表示顾客初始时为0, 最大不超过10(10把座椅) , 各进程的具体实现如下所示:

座椅数, 也是最多排队的储户数