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

一、应用题

1． 用一个数组S （设大小为MAX ）作为两个堆栈的共享空间。请说明共享方法，栈满/栈空的，其中i 为0或1，用判断条件，并用C 语言或PASCAL 语言设计公用的入栈操作push （i ，x ）于表示栈号，x 为入栈值。

，栈底设在数组的两端，两栈顶相邻时为栈满。设【答案】两栈共享一向量空间（一维数组）

共享数组为S[MAX]，则一个栈顶指针为一1，另一个栈顶指针为MAX 时，栈为空。用C 语言写的入栈操作push （i ，x ）如下：

2． 写出下面算法中带标号语句的频度。

设k 的初值等于1。

【答案】（1）这是一个递归调用，因k 初值为1，由语句（6）知，每次调用k 增1，故第（1）语句执行n 次，所以频度是n 。

（2）这是FOR 循环语句，在满足（1）的条件下执行，该语句进入循环体（3）n 次，加上最后一次判断出界，故执彳丁了n ＋1次，所以频度是n ＋1。

（3）这是循环体语句，共执行了n 次，所以频度是n 。

，k=2时判断n 次，最后（4）这是循环语句，当k=l时判断n ＋1次（进入循环体（5）n 次）

一次k=n－l 时判断3次，故执行次数是（n ＋1）＋n ＋... ＋3=（n ＋4）（n －1）/2次，所以频度是（n ＋4）（n －1）/2。

（5）语句（5）是（4）的循环体，每次比（4）少一次判断，故执行次数是n ＋（n －1）＋... ＋2=（n ＋2）（n －1）/2次，所以频度是（n ＋2）（n －1）/2。

（6）这是循环体语句，共执行了n －1次，所以频度是n －1。

3． 画出同时满足下列两个条件的两棵不同的二叉树。

（1）按前序遍历二叉树的顺序为ABCDE 。

（2）高度为5其对应的树（森林）的高度最大为4。 【答案】（1）满足条件的二叉树如图1所示：

图1

（2）满足条件的二叉树如图2所示：

图2

4． 画出对算术表达式表所示。

求值时操作数栈和运算符栈的变化过程。

求值，过程如

【答案】设操作数栈是opnd ，运算符栈是optr ，对算术表达式

表 操作数栈和运算符找的变化过程

5． 请写出应填入下列叙述中（ ）内的正确答案。

排序有各种方法，如插入排序、快速排序、堆排序等。

设一数组中原有数据如下：15，13，20，18，12，60。下面是一组用不同排序方法进行一遍排序后的结果。

（ ）排序的结果为：12，13，15，18，20，60 （ ）排序的结果为：13，15，18，12，20，60 （ ）排序的结果为：13，15，20，18，12，60 （ ）排序的结果为：12，13，20，18，15，60 【答案】①快速排序②起泡排序③直接插入排序④堆排序

6． 给出一组关键字：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;