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

一、算法设计题

1． 编写算法，将自然数1〜n 2按“蛇形”填nxn 矩阵中。例(1〜42) 如图所示(用程序实现) 。

图

【答案】算法如下:

//将自然数

，按" 蛇形M 填入n 阶方阵A 中

//i，j 是矩阵元素的下标，k 是要填入的自然数

//从右上向左下填数

//副对角线及以上部分的新i ，j 坐标

//副对角线以下的新的i ，j 坐标

//从左下向右上

//最外层

while

2． 串以静态存储结构存储，结构如下所述，试实现串操作equal 算法。

串被确认的最大长度

【答案】算法如下:

//本算法判断字符串S 和字符串t 是否相等，如相等返回1，否则返回

//在类C 中，一维数组下标从零开始

//两串相等

//算法结束

3． 用邻接多重表存储结构，编写FERST-ADJ(G，V) 函数，函数返回值为第一个邻接点，若V 没有邻接点，返回零。

【答案】算法如下:

在邻接多重表g 中，求v 的第一邻接点, 若存在，返回第一邻接点，否则返回

确定顶点v 在邻接多重表向量中的下标, 不考虑不存在v 的情

况

返回第一邻接点，

和

中必有一个等于

i

取第一个边结点

4． 线性表中元素存放在向量A(1，... ，，1) 中，元素是整型数。试写出递归算法求出A 中的最大和最小元素。

【答案】算法如下:

//一维数组A 中存放有n 个整型数，本算法递归的求出其中的最小数和最大数

//算法结束

5． 已知二叉树T ，试写出复制该二叉树的算法(t→T) 。

【答案】算法如下:

复制二叉树t 的非递归算法

是二叉树的结点指针的队列，容量足够大

结束本题

二、应用题

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

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

和

和，且

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

将分

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

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

7． 假定有下列，nxn 矩阵(n为奇数

)

如果用一维数组B 按行主次序存储A 的非零元素，问: (1)A中非零元素的行下标与列下标的关系； (2)给出A 中非零元素在B 中的位置公式。

(1)主对角线上元素的坐标是i ＝j ，【答案】副对角线上元素的坐标i 和j 有i ＋j ＝n ＋l 的关系，

的下标(i，j) 与B 中的下标R 的关系；

，给出利用

的下标(i，j) 定位

(3)假定矩阵中每个元素占一个存储单元且B 的起始地址为