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

一、算法设计题

1． 对给定关键字序号j(1

中找到关键字从小到大排在第j 位上的记

录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。

例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下；

在后半部分继续进行划分

在前半部分继续进行划分

2． 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key 的记录。设此组记录存放于数组

【答案】算法如下:

本句的有无不影响査找结果

第 2 页，共 37 页

中。若查找成功，则输出该记录在r 数组中的位置及其值，否则显示“not

find ”信息。请编写出算法并简要说明算法思想。

3． 给定一个整数数组求出b 中最长平台的长度。

【答案】算法如下:

b 中连续的相等元素构成的子序列称为平台。试设计算法，

//求具有N 个元素的整型数组b 中最长平台的长度。

//局部最长平台

//新平台起点

(“最长平台长度

4． 编写算法打印出由指针Hm 指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非零元的个数。注意:行、列及总表头结点的形式为:

在b 数组中起始下标为

”，1，

k)

它们已用val 域链接成循环链表。非零元的结点形式也同上，每一行(列) 的非零元由right(down)域把它们链接成循环链表，该行(列) 的表头结点即为该行(列) 循环链表的表头。

【答案】算法如下:

//输出由Hm 指向的十字链表中每一行的非零元素个数

//数组A 记各行非零元个数，i 记行号

//循环完各行列表头

//P是稀疏矩阵行内工作指针，num 记该行非零个

数

//完成行内非零元的查找

//指针后移

//存该行非零元个数

//移到下一行列表头

第 3 页，共 37 页

//输出各行非零元个数

第

}算法结束

5． 设有两个栈S 1，S 2都采用顺序栈方式，并且共享一个存储区的操作算法。

【答案】找的定乂:

两栈共享顺序存储空间所能达到的最多元素数

//假设元素类型为整型

； //栈空间

//top为两个栈顶指针

//S是如上定义的结构类型变量，为全局变量

(1)入栈操作:

//入栈操作。i 为栈号，i ＝〇表示左栈Sl ，i ＝l 表示右栈s2，x 是入栈元素。入栈成功返回1，否则返回

(2)出栈操作

//出栈算法。i 代表栈号，i ＝0时为s1栈，i ＝l 时为s2栈。出栈成功返回出栈元素，否则返﹣

1

为了尽量利用

行非零元个数为

}

//稀疏矩阵非零元个数

空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S 1，S 2有关入栈和出找

//算法结束

第 4 页，共 37 页