数据结构上机

1． 已知长度为n的线性表L采用顺序存储结构，编写一个时间复杂度为O(n)，空间复杂度

为O(1)的算法，该算法删除线性表中所有值为item的数据元素。

2． 用顺序表A和B表示的两个线性表，元素的个数分别为m和n，若表中数据都是由小

到大顺序排列的，且这(m+n)个数据中没有相重的。设计一个算法将些两个线性表合并成一个，仍是数据由小到大排列的线性表，存储到另一个顺序表C中。

3． 已知线性表{a0,a1,……,an-1}按顺序存储，且每个元素都是不相等的整数。设计把所有

的奇数移到所有的偶数前边的算法（要求时间最少，辅助空间最少）。 4． 输入一组整型元素序列，建立单链表。

5． 写出在带头结点的单向链表l中删除第i个结点的算法。

6． 编写算法,将带头结点的单链表拆分成一个奇数链表和一个偶数链表。

7． 设C={a1,b1,a2,b2,……,an,bn}为一线性表，采用带头结点的Hc单链表存放，编写一个

就地算法，将其拆分成两个线性表，使得：A={a1,a2,…..,an} C={b1,b2,….,bn} 8． 编写出判断带头结点的双向循环链表L是否对称相等的算法。 9． 设计一算法，将一带头结点的数据域依次为a1,a2,…,an(n>=3)的单链表的所有结点逆置。 10． 设ha=(a1,a2,……,an)和hb=(b1,b2,……,bm)是两个带头结点的循环单链表，编写将

这两个表合并为带头结点的循环单链表hc的算法。 11． 设A和B是两个单链表（带头结点），其表中元素递增有序。试写一算法将A和B

归并成一个按元素值递增有序的单链表C，要求辅助空间为O（1），并分析算法的时间复杂度。 12． 假设在长度大于1的单循环链表中，即无头结点指针也无首数据结点指针。S为指

向链表中某个结点的指针，试编写算法删除结点*S的直接前趋结点。 13． 已知单链表L（带头结点）是一个递增有序表，试写一高效算法，删除表中值大于

min且小于max的结点（若表中有这样的结点），同时释放被删结点的空间，这里min和max是两个给定的参数。 14． 编写一算法将单链（带头结点）中值重复的结点删除，使所得的结果表中各结点值

均不相同。 15． 有一递增单链表（允许出现值域重复的结点），设计一个算法删除值域重复的结点。 16． 已知由单链表表示的线性表中，含有三类字符的数据元素（如：字母字符，数字字

符和其他字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另开辟空间。 17． 已知带头结点的单循环链表L中至少有两个结点，每个结点的两个字段为data和

next，其中data的类型为整型。试设计一个算法判断该链表中每个元素的值是否小于其后续两个结点的值之和。若满足，则返回1；否则返回0。 18． 设计一算法判定单链表L（带头结点）是否是递增的。 19． 试分别在一个双链表head（带头结点）中值为x的结点之前插入值为y的结点。

假设在双链表中不存在值域相同的两个结点。 20． 试分别在一个双链表head（带头结点）中值为x的结点之后插入值为y的结点。

假设在双链表中不存在值域相同的两个结点。 21． 假设二叉树采用二叉链表存储结构存储，设计一个算法，按层次顺序（同一层次自

左向右）遍历二叉树。 22． 假设二叉树采用二叉链表存储结构存储，设计一个算法，先序非递归遍历二叉树。 23． 假设二叉树采用二叉链表存储结构存储，设计一个算法，中序非递归遍历二叉树。 24． 假设二叉树采用二叉链表存储结构存储，设计一个算法，计算一棵给定二叉树的所

有结点数。

25． 假设二叉树采用二叉链表存储结构存储，设计一个算法，删除该二叉树并释放所有

的结点。 26． 假设二叉树采用二叉链表存储结构存储，设计一个算法，将左右子树进行交换。 27． 假设二叉树采用二叉链表存储结构存储，设计一个算法，求二叉树的高度。 28． 假设二叉树采用二叉链表存储结构存储，设计一个算法，输出一个二叉树的所有叶

子结点。 29． 以单链表作为存储结构实现直接插入排序算法。 30． 以单链表作为存储结构实现起泡排序算法。 31． 以单链表作为存储结构实现选择排序算法。

本文来源：https://www.bwwdw.com/article/434h.html