2017年曲阜师范大学信息科学与工程学院859数据结构[专业硕士]考研题库
● 摘要
一、算法设计题
1． 结点类型和存储结构如下：
试设计一个排序算法，要求不移动结点的存储位置，只在结点的count 字段记录结点在排序中的序号，并将排序结果按升序输出。
【答案】算法如下：
2． 元素集合己存入整型数组树T 的非递归算法
：
【答案】算法如下：
中，试写出依次取A 中各值
构造一棵二叉排序
3． 设计算法将一个带头结点的单链表A 分解为两个具有相同结构的链表B 、C ，其中B 表的结点为A 表中值小于零的结点，而C 表的结点为A 表中值大于零的结点（链表A 的元素类型为整型，要求B 、C 表利用A 表的结点）。
【答案】算法如下：
4． 假设串的存储结构如下所示，编写算法实现串的置换操作。
【答案】算法如下：
和t 是用一维数组存储的串，本算法将s 串第i 个字符开始连续j 个字符用t 串置换，操作
成功返回1, 否则返回0表示失败
5． 给出以十字链表作存储结构，建立图的算法，输入（i ，j ，v ） ，其中I , j 为顶点号，v 为权值。
【答案】算法如下：
//建立有向图的十字链表存储结构
//假定权值为整型
//建立顶点向量
//当输入i , j 、v 之一为0时，结朿算
法运行
//申请结点
//弧结点中杈值域
//算法结束
6． 起泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）；请给出上浮和下沉过程交替的起泡排序算法。
【答案】算法如下：
语言编写时间
7． 以三元组表存储的稀疏矩阵A ，B 非零元个数分别为m 和n 。试用类复杂度为O 述所用结构。
【答案】算法如下：
的算法将矩阵B 加到矩阵A 上去。A 的空间足够大，不另加辅助空间。要求描