2018年浙江大学光电信息工程学院408计算机学科专业基础综合之数据结构考研核心题库
● 摘要
一、算法设计题
1． 二路插入排序是将待排关键字序列二路插入。编写实现2-路插入排序算法。
【答案】算法如下:
二路插入排序的算法
辅助存储
插人后部
折半査找插入位置
移动元素
插入有序位置
插入前部
移动元素
将序列复制回去
中关键字分二路分别按序插入到辅助向量
前半部和后半部(注.. 向量d 可视为循环表) ，其原则为，先将r[1]赋给d[1]，再从r[2]记录开始分
2． 设计将数组A[n]中所有的偶数移到奇数之前的算法。要求不增加存储空间，且时间复杂性为〇(n)。
【答案】算法如下:
//n个整数存于数组A 中，本算法将数组中所有偶数排在奇数之前
//用类C 语言编写，数组下标从0开始
//交换A[i]与
A[j]
//算法Arrange 结束
3． 已知L 为没有头结点的的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符、数字字符或其他字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符(要求用最少的时间和最少的空间) 。
【答案】算法如下:
L 是不带头结点的单链表第一个结点的指针，链表中的数据域存放字符
//本算法将链表L 分解成含有英文字母字符、数字字符和其他幸符的带头结点的三个循环链表
//建立三个链表的头结点
//置三个循环链表为空表
//分解原链表
//L指向待处理结点的后继
//处理字母字符
//处理数字字符
//处理其他符号
//结束while(L!＝
null) //算法结束
4． 写出一个递归算法来实现字符串逆序存储。
【答案】算法如下:
//字符串逆序存储的递归算法
r
//需要使用静态变量
//
规定
是字符串输入结束标志
//字符串逆序存储
//字符串结尾标记
//结束算法InvertStore
5． 写一算法找出n 个数的最大值和最小值，要求最坏条件下的元素比较次数为
。
【答案】算法如下:
用最多3n/2－2次比较在n 个元素r 中选出最大值和最小值
n 为偶数时
r 最小值
("最大值) ；
二、应用题
6．
一个长度为的中位数。例如, 若
(1)给出算法的基本设计思想。
(2)根据设计思想, 采用C 或C++或JA V A 语言描述算法, 关键之处给出注释。 (3)说明你所设计算法的时间复杂度和空间复杂度。
【答案】(1)算法的基本设计思想:分别求两个升序序列A 和B 的中位数, 设为a 和b 。 ①若a=b, 则a 或b 即为所求的中位数。
②否则, 若a 的升序序列S , 处在第个位置的数为S 的中位数。例如, 若序列 则S1的中位数是15。两个序列的中位数是含它们所有元素的升序序列 , 则S1和S2的中位数是11。现有两个等长升序序列A 和B , 试设计一个时间和空间两方面都尽可能高效的算法, 找出两个序列A 和B 的中位数。要求:
相关内容
相关标签