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

一、应用题

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． 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：

（1）归并排序，每归并一次书写一个次序。 （2）快速排序，每划分一次书写一个次序。

（3）堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。 【答案】（1）2—路归并第一趟：18，29，25，47，12，58，10，51: 第二趟：18，25，29， 47，10，12，51，58;

第三趟：10，12，18，25，29，47，51，58

（2）快速排序第一趟：10，18，25，12，29，58，51，47; 第二趟：10，18，25，12，29，47，51，88; 第三趟：10，12，18，25，29，47，51，88 （3）堆排序

建大堆：58，47，51，29，18，12，25，10; ①51，47，25，29，18，12，10，58; ②47，29，25，10，18，12，51，58; ③29，18，25，10，12，47，51，58; ④25，18，12，10，29，47，51，58; ⑤18，10，12，25，29， 47，51，58; ⑥12，10，18，25，29，47，51，58; ⑦10，12，18，25，29， 47，51，58

3． 三个进程P1、P2, P3互斥使用一个包含N P1每次用produce （N ＞0）个单元的缓冲区。（ ）生成一个正整数并用put （ ）送入缓冲区某一空单元中；P2每次用getodd （ ）从该缓冲区中取出一个奇数并用countodd （ ）统计奇数个数；P3每次用geteven （ ）从该缓冲区中取出一个偶数并用counteven （ ）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。

【答案】定义信号量S1控制P1与P2之间的同步；S2控制P1与P3之间的同步；empty 控制生产者与消费者之间的同步；mutex 控制进程间互斥使用缓冲区，程序如下：

4．

已知一个整数序列

其中

则称x 为A 的主元素。

例如

若存在

且

则称5为主元素；

又如

则A 中没有主元素。假设A 中的n 个元素保存在一个一维数组中，请设计一个

尽可能高效的算法，找出A 的主元素。若存在主元素，则输出该元素；否则输出-1。要求：

（1）给出算法的基本设计思想。 （2）根据设计思想，采用C 或【答案】

（1）算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num 。然后重新计数，确认Num 是否是主元素。

算法可分为以下两步：

①选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数Num 保存到c 中，记录Num 的出现次数为1; 若遇到的下一个整数仍等于Num ，则计数加1否则计数减1; 当计数减到0时，将遇到的下一个整数保存到c 中，计数重新记为1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。

②判断c 中元素是否是真正的主元素，再次扫描该数组，统计c 中元素出现的次数，若大于则为主元素；否则，序列中不存在主元素。

（2）算法实现如下：

用来保存候选主元素，count 用来计数

设置A [0]为候选主元素

查找候选主元素

为A 中的候选主元素计数

处理不是候选主元素的情况

更换候选主元素

或Java 语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度和空间复杂度。