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

一、算法设计题

1． 写出一个递归算法来实现字符串逆序存储。

【答案】算法如下:

//字符串逆序存储的递归算法

r

//需要使用静态变量

//

规定

是字符串输入结束标志

//字符串逆序存储

//字符串结尾标记

//结束算法InvertStore

2． —个有向图G=(V，E) 的平方图

，使得表示。

【答案】算法如下:

3． 设整数序列ai ，a2，a3，…，an ，给出求解最大值的递归程序。

【答案】算法如下:

第 2 页，共 35 页

满足下述性质

:

当且仅当存在某个顶点

且

22

。写一个算法从给定的G 求出G , G 和G 可分别用两个邻接表

//设整数序列存于数组a 中，共有n 个，本算法求解其最大值

4． 已知指针P 指向带表头的中根次序线索二叉树中的某结点，试写一算法FFA(P，q) , 该算法寻找结点P 的父亲结点q 。设线索二叉树的结点结构、表头结点结构和空树结构分别为(LTAG，LLINK ，INFO , RL1NK ，RTAG) ，且规定线索树的最左下结点的LLINK 域和最右下结点的RLINKt 域指向表头。

【答案】算法如下:

在中序线索树t 上，求结点p 的双亲结点q

暂存

找P 的中序最右下的结点

顺右线索找到q 的后继(P的袓先结点

)

若后继是头结点，则转到根结点

根结点无双亲

找最右结点的过程中回找到

P

结束FFA

5． 在一棵以二叉链表表示的二叉树上，试写出按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目的算法。

【答案】算法如下:

层次遍历二叉树，并统计度为1的结点的个数

统计度为1的结点的个数

是以二叉树结点指针为元素的队列

出队，访问结点

度为1的

结点

非空左子女入队

非空右子女入队

返回度为1的结点的个数

第 3 页，共 35 页

准备到左子树中找

P

二、应用题

6． 设有n 个元素采用起泡排序法进行排序，通常需要进行多少趟排序? 对于第J 趟起泡通常需要进行多少次关键字比较? 在程序设计中如何设置判断条件，有可能使起泡趟数可以减少并且能完成排序。

【答案】n 个元素采用起泡排序法进行排序，通常需要进行n －1趟排序。第j 趟起泡排序要进行n －j 次比较。在一趟排序中，若没有记录交换，则表示排序完成。因而，可通过设标记来控制排序结束，下面语句段说明了标记flag 的使用。

用作控制标记

是起泡排序趟数，最多n －1趟

设标记，若本趟不发生交换，本趟起泡排序后，算法结束

发生了交换，还要进行下

趟

7． 对给定文件(28，07，39，10，65，14，61，17，50，21) 选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。

【答案】快速排序的思想如下:首先将待排序记录序列中的所有记录作为当前待排序区域，以第一个记录的关键字作为枢轴(或支点) ，凡其关键字不大干枢轴的记录均移动至该记录之前，凡关键字不小于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列割成两部分:

和

和，且

进行快速排序。快速排序在记录有序时蜕变为起泡排序，

将分

然后再递归地将初始序列:21移动:39移动:17移动:65移动:14移动:

可用“三者取中”法改善其性能，避免最坏情况的出现。

第 4 页，共 35 页