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

一、应用题

1． 如果两个串含有相等的字符，能否说它们相等？

【答案】仅从两串含有相等的字符，不能判定两串是否相等，两串相等的充分必要条件是两串长度相等且对应位置上的字符相同（即两串串值相等）。

2． 已知有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 的路径的条数。

3． 在各种排序方法中，哪些是稳定的? 哪些是不稳定的? 并为每一种不稳定的排序方法举出一个不稳定的实例。

【答案】各种排序算法稳定性的归纳如图所示：

图

4． 证明若二叉排序树中的一个结点存在两个孩子，则它的中序后继结点没有左孩子，则它的中序前驱结点没有右孩子。

【答案】根据中序遍历的定义，该结点的中序后继是其右子树上按中序遍历的第一个结点：叶结点或仅有右子树的结点；而其中序前驱是其左子树上按中序遍历的最后个结点：叶结点或仅有左子树的结点。命题得证。

5． 如果只要找出一个具有n 个元素的集合的第种最适合? 给出实现的思想。

【答案】在具有n 个元素的集合中找第

个最小元素，应使用快速排序方法。其基本

思想如下：设n 个元素的集合用一维数组表示，其第一个元素的下标为1，最后一个元素下标为n 。以第一个元素为“枢轴”，经过快速排序的一次划分，找到“枢轴”的位置i ，若i=k，则该位置的元素即为所求；若

则在1至i-1间继续进行快速排序的划分；若

则在i+1至n 间继续进

个最小元

行快速排序的划分。这种划分一直进行到i=k为止，第i 位置上的元素就是第

个最小元素，你所学过的排序方法中哪

素。

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

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

【答案】（1）互斥资源：取机号，故设一个互斥信号量mutex 。

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

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

//定义信号量

//储户进程

//先获得排队机

//若还有座椅则取号

//取号，占用座椅等待叫号

//告知系统储户加1

//释放排队机

//若没有座椅了，则不取号

//不取号，释放排队机

//离开

//等待储户的柜员资源

//排队等待服务的储户数量

//对排队机操作的互斥量

//在座椅上休息等待的储户数

//等待柜员叫号

//进入窗口被服务