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

一、综合题

1． 如果输入序列为123456，试问能否通过栈结构得到以下两个序列:435612和135426; 请说明为什么不能或如何才能得到。

【答案】输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素(4356)得到后，栈中元素剩12，且2在栈顶，栈底元素1不可能在栈顶元素2之前出栈。得到135426的过程如下:1入栈并出栈，得到部分输出序列1; 然后2和3入栈，3出栈，部分输出序列变为13; 接着4和5入栈，5、4和2依次出栈，部分输出序列变为13542; 最后6入栈并出栈，得到最终结果135426。

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)按前序遍历二叉树的顺序为ABCDE 。

(2)高度为5其对应的树(森林) 的高度最大为4。

【答案】(1)满足条件的二叉树如图1所示:

图1

(2)满足条件的二叉树如图2所示:

图2

4． 对于具有n 个叶结点且所有非叶结点都有左、右孩子的二叉树。

(1)试问这种二叉树的结点总数是多少？

(2)试证明。其中:表示第i 个叶结点所在的层号(设根结点所在层号为1) 。

【答案】(1)根据二叉树中度为2的结点个数等于叶结点个数减1的性质，故具有n 个叶结点且非叶子结点均有左子树的二叉树的结点数是2n －1。

(2)当i=1时，，公式成立。设当i=n－1时公式成立，证明当i=n时公式仍成立。 设某叶结点的层号为t ，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1，对于公式的变化，是减少了一个原来的叶结点，增加了两个新叶结点，反映到公

，所以结果不变，这就证明当i=n时公式仍成立。 式中，因为

5． 下列关于堆(Heap)的一些问题:

(1)堆的存储表示是顺序的还是链接的？

(2)设有一个最小堆，即堆中任意结点的关键码均不大于它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方？

(3)对n 个元素进行初始建堆的过程中，最多做多少次数据比较(不用大O 表示法) ？

【答案】(1)堆的存储是顺序的。

(2)最大值元素一定是叶结点，在最下两层上。