习题1
1-1什么是数据、数据元素、数据项？三者之间是怎样的关系？
1-2什么是数据结构？数据结构的概念包括哪三部分？
1-3数据结构与数据类型的概念有什么区别？为什么要将数据结构设计成抽象数据类型？
1-4数据的逻辑结构主要有哪三种？各有何特点？三者之间存在怎样的联系？
1-5数据的存储结构有哪两种？各有何特点？
1-6什么是算法？怎样描述算法？怎样衡量算法的性能？
1-7下列函数的功能是什么？
void binary（int n）
{
whiIe（n>0）
{ cout<<n<<",";
n/=2;
}
}
1-8确定下列算法中语句的执行次数，并给出算法的时间复杂度。
int n=10, count=0;
for（int i=1; i<=n; i++）
for（int j=1; j<=i; j++）
for（int k=1; k<=j; k++）
count++;
实验1 算法设计与分析
1.实验目的
了解数据结构课程的目的、性质和主要内容，理解数据结构和算法的基本概念，熟悉算法的描述方法、算法时间复杂度和空间复杂度的分析和计算方法。
要求熟练使用Visual C++ 6.0集成开发环境进行C++程序的编辑、编译和运行，程序必须运行通过并获得正确结果，详见第11章。
2.实验内容
（1）实现以下对数组的操作，并给出算法的时间复杂度和空间复杂度。
T max（T tabIe[],int n） //返回数组中的最大值
T min（T tabIe[],int n） //返回数组中的最小值
booI repIace（T tabIe[],int n,int x,int y） //将n个元素的数组中值为x的元素替换为y值
booI repIaceAII（T tabIe[],int n,int x,int y） //将数组中所有值为x的元素替换为y值
booI isSorted（T tabIe[],int n） //判断数组元素是否已按升序排序
void reverse（T tabIe[],int n） //将数组元素a0,a1,…,an-1逆置为an-1,…,a1,a0
（2）用C++的类实现复数抽象数据类型。
（3）实现十进制、二进制、八进制和十六进制的相互转换。
（4）螺旋方阵。
螺旋方阵将从1开始的自然数由方阵的最外圈向内螺旋方式地顺序排列。例如，4阶的螺旋方阵排列形式如下：
（5）杨辉三角。
中国南宋数学家杨辉在其《详解九章算法》（1261年）中给出以下三角形（后世称为杨辉三角），表中任何一个数字等于它肩膀上的两个数字之和。n=5的杨辉三角如下：
杨辉三角的重要意义在于，其各行是二项式（a+b）n（n=0，1，2，…）展开式的系数表。n=2和n=3的展开式如下：
（a+b）2=a2+2ab+b 2（a+b）3=a3+3a2b+3ab2+b 3
要求分别采用一维数组、二维数组输出杨辉三角。
（6）下标和相等的数字方阵。
（7）输出n个元素的全排列。
如n=3时，数据序列{1, 2, 3}的全排列为：123，132，213，231，312，321。
（8）设计一个矩阵类，构造n阶矩阵，实现矩阵加、乘、转置等运算，并求各算法的时间复杂度。
（9）实现直接选择排序。
（10）幻方。
n阶幻方（magic square）是指将自然数1～n2排列成n×n阶方阵，其各行、各列及各对角线上的数字之和相等，和数S=n（n2+1）/2。洛书（传说大禹治水时洛水神龟所献）上的3阶幻方和杨辉的4阶幻方如图1.11所示，3阶幻方的和数为15，4阶幻方的和数为34。
图1.11 3阶和4阶幻方
幻方有许多构造方法。杨辉在《续古算法摘奇》（1275年）中给出解法，“九子斜排，上下对易，左右相更，四维挺出”，如图1.12所示。
图1.12 杨辉的幻方构造法
连续摆数法（也称暹罗法）适用于构造奇数阶幻方，构造过程如图1.13所示。
图1.13 连续摆数法构造奇数阶幻方
连续摆数法构造规律说明如下：
① 约定初始位置为第1行中间，放置1。
② 向当前位置的右上方顺序放置下一个数。将幻方阵沿行、列方向看成环形。
③ 若当前放置数为n的倍数，即一条对角线已满，则下一个数的位置是本列的下一行。
④ 输出幻方阵。
要求采用连续摆数法构造并输出指定奇数阶的幻方阵。