《数据结构》程序设计实习题目

《数据结构》程序设计实习题目

1.分别以顺序表和单链表作为存储结构，实现将线性表就地逆置的操作。（所谓“就地逆置”是指辅

助空间为O（1），即利用原表中的结点空间）。

2.写一程序将单链表中值重复的结点删除，使得表中各结点值均不相同。

3.已知一单链表中含有两类字符的数据元素（如：字母、数字），试编写程序将该单链表分成两个单

链表，使得每个链表中只含有同一类的字符。

4.假设有两个按元素值递增有序的单链表A和B，试编写程序将A和B归并成一个按元素值递减有

序的单链表。

5.利用线性结构（顺序表或链表）实现两个20位大整数的加法运算。

6.已知两个以顺序结构存储的线性表A和B，试编写程序实现从A表中删除包含在B表中的元素。

7.已知两个单链表A和B，试编写程序实现从A表中删除包含在B表中的元素。

8.已知两个以顺序结构存储的线性表A和B，试编写程序实现：将在B表中但不在A表中的元素插

入到A表。

9.已知两个单链表A和B，试编写程序实现：将在B表中但不在A表中的元素插入到A表。

10.试编写程序，对任意输入的一个算术表达式，将式中的数字和运算符分成两类（一类是数字，一

类是运算符），并按逆序输出。（提示：利用栈来实现）

11.利用栈结构，编写一个程序，对以逆波兰式表示的表达式求值。

12.编写程序，求得所有包含在串S中而不包含在串T中的字符（S中重复的字符只选一个）构成的

新串R。

13.编写程序，求任意输入的串S中所含不同字符的总数和每种字符的个数。

14.一个文本串可用事先给定的字母映射表进行加密。例如：设字母映射表为：

a b c d e f g h i j k l m n o p q r s t u v w x y z

n g z q t c o b m u h e l k p d a w x f y i v r s j

则字符串“encrypt”被加密为“tkzwsdf”。试写一程序将输入的文本串进行加密后输出。

15.假设两个10×10的稀疏矩阵A和B以三元组表的方式存储，试编写程序实现矩阵的相加运算，

其结果存放在三元组表C中。

16.对给定的整数序列，建立一棵二叉排序树，并按中序遍历输出树中结点。

17.编写按层次顺序（同一层自左至右）遍历二叉树的算法。

18.编写一算法，计算二叉树中叶子结点的数目。

19.编写一算法，计算二叉树的深度。

20.对给定的图的邻接矩阵，试编写程序，建立该图的邻接表。

21.假设一个有向图以邻接矩阵方式存储，试编写程序，求出图中各结点的出度和入度。

22.实现克鲁斯卡尔算法，求出给定图的最小生成树。（只需输出各条选中的边）

23.对一个给定的有向图，编写算法判断它是否是强连通图。

24.编写算法，实现从二叉排序树中删除一个关键字。

25.编写程序，实现对索引顺序表的查找。（即分块查找）

26.编写程序实现：以“除留余数法”为哈希函数，对任意输入的一批100以内的整数，构造哈希表，

表长为30。（注：解决冲突可以用开放定址法）

27.以单链表为存储结构，实现直接插入排序。

28.按折半查找的方法，实现直接插入排序。（即教材中的2-路插入排序）

29.编写程序，对任意输入的一批数据，建立一个大根堆。

30.以单链表为存储结构，实现简单选择排序算法。

31.编写程序，对n个正、负整数组成的序列进行整理，将所有的负数排到非负数之前。

32.荷兰国旗问题（三色旗问题）：设有一个仅由红、白、蓝三种颜色的条块组成的条块序列（三种色

块的数目可不同，各色块是任意排列的），试编写一个算法，使得这些条块按红、白、蓝的顺序排好（即所有红色的条块集中在序列前部，白色在中部，蓝色在后部）。

33.以基数排序的方法，实现对任意输入的一组2位正整数进行排序。