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

一、算法设计题

1． 已知两个线性表A , B 均以带头结点的单链表作存储结构，且表中元素按值递增有序排列。设计算法求出A 与B 的交集C ，要求C 另开辟存储空间。，并同样以元素值的递增有序的单链表形式存储。

【答案】算法如下:

//线性表A 和B 以带头结点的单链表作为存储结构。本算法求A 和B 的交集C , C 另辟空间

//pa、pb 是两链表的工作指针

//监视哨

//pa指针后移

//pb指针后移

//处理交集元素

//删除重复元素

//交集元素并入结果表

//置结果链表尾

2． 设稀疏矩阵中有t 个非零元素，用三元组顺序表的方式存储。请设计一个算法，计算矩阵M 的转置矩阵N ，要求转置算法的时间复杂度为0(n＋t) 。

【答案】算法如下:

//采用三元组表方式存储，按列序实现矩阵的转置

//行数、列数和非零元素个数

//设置N 中第一个非零元素从下标1开始存储

//按列，共

//在

第 2 页，共 40 页

列

个元素中查找

//转置

//三元组表上实现矩阵的快速转置的算法

//矩阵M 每一列非零元初始化为零

//求矩阵M 每一列的非

零元个数

//第1列第一个非零元在转置后的三元组中下标是

1

//求

第j 列第一个非零元在

中的序号

//求转置矩阵N 的三元组表

//同列下一非零元

素位置

3． 若x 和y 是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。

【答案】算法如下:

//本算法判断两个顺序存储的串x 和y 是否相等，相等返回1，否则返回

//对应字符相等，指针后移

第 3 页，共 40 页

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

【答案】算法如下:

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

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

况

返回第一邻接点，

和

中必有一个等于

i

取第一个边结点

5． 给定(已生成) 一个带表头结点的单链表，设head 为头指针，结点的结构为(data，next) ，data 为整型元素，next 为指针，试写出算法:按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间(要求:不允许使用数组作辅助空间) 。

【答案】算法如下:

//head是带头结点的单链表的头指针

//本算法按递增顺序输出单链表各结点的值，并释放结点所占的存储空间

//循环到仅剩头结点

//pre为元素最小值结点的前驱结点的指针

//P为工作指针

//记住当前最小值结点的前驱

//输出元素最小值结点的数据

//删除元素值最小的结点，释放结点

空间

//释放头结点

二、应用题

6． 已知一个整数序列

且又如要求:

第 4 页，共 40 页

, 其中

, 则称x 为A 的主元素。例如

, 若存在

, 则称5为主元素;

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

请设计一个尽可能高效的算法, 找出A 的主元素。若存在主元素, 则输出该元素; 否则输出-1。