数据结构作业

数据结构》作业一。

1-1什么是数据？它与信息是什么关系？

1-2什么是数据结构？有关数据结构的讨论涉及哪三个方面？

1-3数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、栈、队列、优先级队列等；非线性结构包括树、图等、

数据结构》作业一。

1-1什么是数据？它与信息是什么关系？

1-2什么是数据结构？有关数据结构的讨论涉及哪三个方面？

1-3数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、栈、队列、优先级队列等；非线性结构包括树、图等、这两类结构各自的特点是什么？

1-4．什么是抽象数据类型？试用c++的类声明定义“复数”的抽象数据类型。要求。

(1) 在复数内部用浮点数定义它的实部和虚部。

(2) 实现3个构造函数：缺省的构造函数没有参数；第二个构造函数将双精度浮点数赋给复数的实部，虚部置为0；第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。

(3) 定义获取和修改复数的实部和虚部，以及+、-等运算的成员函数。

(4) 定义重载的流函数来输出一个复数。

1-5 用归纳法证明：

1-6 什么是算法？算法的5个特性是什么？试根据这些特性解释算法与程序的区别。

1-7 设n为正整数，分析下列各程序段中加下划线的语句的程序步数。

(1) for (int i = 1; i <=n; i2) x = 0; y = 0;

for (int j = 1; j <=n; jfor (int i = 1; i <=n; i

c[i][j] =0.0for (int j = 1; j <=i; j++)

for (int k = 1; k <=n; kfor (int k = 1; k <=j; k++)

c[i][j] =c[i][j] +a[i][k] *b[k][jx = x + y;

(3) int i = 1, j = 14) int i =1;

while (i<=n &&j<=ndo

(2) 将由(1)所得到的程序化简。使得化简后的程序与化简前的程序具有相同的count值。

(3) 程序执行结束时的count值是多少？

(4) 使用执行频度的方法计算这个程序的程序步数，画出程序步数统计表。

1-10 设有3个值大小不同的整数a、b和c，试求。

1) 其中值最大的整数；

2) 其中值最小的整数；

3) 其中位于中间值的整数。

2-1 设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，……如此反复直到所有的人全部出局为止。下面要解决的josephus问题是：对于任意给定的n, s和m，求出这n个人的出局序列。

请以n = 9, s = 1, m = 5为例，人工模拟josephus的求解过程以求得问题的解。

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作为输入数据，检查你的程序的正确性和健壮性。

最后分析所完成算法的时间复杂度。

2-3 设有一个线性表 (e0, e1, …en-2, en-1) 存放在一个一维数组a[arraysize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为 (en-1, en-2, …e1, e0)。

2-4 假定数组a[arraysize]中有多个零元素，试写出一个函数，将a 中所有的非零元素依次移到数组a的前端a[i]（0≤ i ≤ arraysize）。

2-5 顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下，对有127个元素的顺序表进行插入，平均需要移动多少个元素？删除一个元素，又平均需要移动多少个元素？

2-6 若矩阵amn中的某一元素a[i][j]是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵的一个鞍点。假设以二维数组存放矩阵，试编写一个函数，确定鞍点在数组中的位置（若鞍点存在时），并分析该函数的时间复杂度。

2-7 设有一个二维数组a[m][n]，假设a[0][0]存放位置在644(10)，a[2][2]存放位置在676(10)，每个元素占一个空间，问a[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

2-8 利用顺序表的操作，实现以下的函数。

(1) 从顺序表中删除具有最小值的元素并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。

(2) 从顺序表中删除第i个元素并由函数返回被删元素的值。如果i不合理或顺序表为空则显示出错信息并退出运行。

(3) 向顺序表中第i个位置插入一个新的元素x。如果i不合理则显示出错信息并退出运行。

(4) 从顺序表中删除具有给定值x的所有元素。

(5) 从顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素，如果s或t不合理或顺序表为空则显示出错信息并退出运行。

(6) 从有序顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素，如果s或t不合理或顺序表为空则显示出错信息并退出运行。

(7) 将两个有序顺序表合并成一个新的有序顺序表并由函数返回结果顺序表。

(8) 从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。

2-9 设有一个nn的对称矩阵a，如图(a)所示。为了节约存储，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。

我们把它们按行存放于一个一维数组b中，如图(b)和图(c)所示。并称之为对称矩阵a的压缩存储方式。试问：

(1) 存放对称矩阵a上三角部分或下三角部分的一维数组b有多少元素？

(2) 若在一维数组b中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素aij在只存上三角部分的情形下(图(b))应存于一维数组的什么下标位置？给出计算公式。

(3) 若在一维数组b中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素aij在只存下三角部分的情形下(图(c))应存于一维数组的什么下标位置？给出计算公式。

数据结构作业

数据结构作业

数据结构作业

数据结构作业

其他用户还读了