学海网

数据结构课后习题及答案
第一章 绪论
1-4．什么是抽象数据类型？试用C++的类声明定义“复数”的抽象数据类型。要求
(1) 在复数内部用浮点数定义它的实部和虚部。
(2) 实现3个构造函数：缺省的构造函数没有参数；第二个构造函数将双精度浮点数赋给复数的实部，虚部置为0；第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。
(3) 定义获取和修改复数的实部和虚部，以及+、-、*、/等运算的成员函数。
(4) 定义重载的流函数来输出一个复数。
【解答】
抽象数据类型通常是指由用户定义，用以表示应用问题的数据模型。抽象数据类型由基本的数据类型构成，并包括一组相关的服务。
......
第二章 数组
2-1 设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，……，如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是：对于任意给定的n, s和m，求出这n个人的出局序列。请以n = 9, s = 1, m = 5为例，人工模拟Josephus的求解过程以求得问题的解。
【解答】
出局人的顺序为5, 1, 7, 4, 3, 6, 9, 2, 8。
2-2 试编写一个求解Josephus问题的函数。用整数序列1, 2, 3, ……, n表示顺序围坐在圆桌周围的人，并采用数组表示作为求解过程中使用的数据结构。然后使用n = 9, s = 1, m = 5，以及n = 9, s = 1, m = 0，或者n = 9, s = 1, m = 10作为输入数据，检查你的程序的正确性和健壮性。最后分析所完成算法的时间复杂度。
.......