数据结构教学资料数据结构作业布置.doc

《数据结构教学资料数据结构作业布置.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一次作业(注:各题的题号为教材课后练习的题号)第一章数据结构概论笔做题1-4什么是抽象数据类型？试用C++的类声明定义“复数”的抽象数据类型。要求(1)在复数内部用浮点数定义它的实部和虚部。(2)实现3个构造函数：缺省的构造函数没有参数；第二个构造函数将双精度浮点数赋给复数的实部，虚部置为0；第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。(3)定义获取和修改复数的实部和虚部，以及+、-、*、/等运算的成员函数。(4)定义重载的流函数来输出一个复数。1-9(1)在下面所给函数的适当地方插入计算count的语句：voidd(Ar

2、rayElementx[],intn){inti=1;do{x[i]+=2;i+=2;}while(i<=n);;i=1;while(i<=(n/2)){x[i]+=x[i+1];i++;}}(2)将由(1)所得到的程序化简。使得化简后的程序与化简前的程序具有相同的count值。(3)程序执行结束时的count值是多少？(4)使用执行次数的方法计算这个程序的程序步数，画出程序步数统计表。上机题1-8试编写一个函数计算n!*2n的值，结果存放于数组A[arraySize]的第n个数组元素中，0£n£arraySize。若设计算机中允许的整数

3、的最大值为maxInt，则当n>arraySize或者对于某一个k(0£k£n)，使得k!*2k>maxInt时，应按出错处理。可有如下三种不同的出错处理方式：(1)用cerr<<及exit(1)语句来终止执行并报告错误；(2)用返回整数函数值0,1来实现算法，以区别是正常返回还是错误返回；(3)在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。思考题1.1判断下列叙述的对错。如果正确，在题前打“Ö”，否则打“´”。(1)数据元素是数据的最小单位。(2)数据

4、结构是数据对象与对象中数据元素之间关系的集合。(3)数据结构是具有结构的数据对象。(4)数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。(5)算法和程序原则上没有区别，在讨论数据结构时二者是通用的。1.2判断下列叙述的对错。如果正确，在题前打“Ö”，否则打“´”。(1)所谓数据的逻辑结构是指数据元素之间的逻辑关系。(2)同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数都相等。(3)数据的逻辑结构与数据元素本身的内容和形式无关。(4)数据结构是指相互之间存在一种或多种关系的数据元素的全体。

5、(5)从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构。1-7设n为正整数,分析下列各程序段中加下划线的语句的程序步数。(1)for(inti=1;i<=n;i++)(2)x=0;y=0;for(intj=1;j<=n;j++){for(inti=1;i<=n;i++)c[i][j]=0.0;for(intj=1;j<=i;j++)for(intk=1;k<=n;k++)for(intk=1;k<=j;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];x=x+y;}(3)inti=1,j=1;(4)int

6、i=1;while(i<=n&&j<=n){do{i=i+1;j=j+i;for(intj=1;j<=n;j++)}i=i+j;}while(i<100+n);参考题1.填空题算法是一个有穷的指令集，它为解决某一特定任务规定了一个运算序列。它应当具有输入、输出、(①)、有穷性和可执行性等特性。算法效率的度量分为(②)和(③)。(②)主要通过在算法的某些部位插装时间函数来测定算法完成某一规定功能所需的时间。而(③)不实际运行算法，它是分析算法中语句的执行次数来度量算法的时间复杂性。程序所需的存储空间包含两个部分(④)和(⑤)。(④)空间的大

7、小与输入输出数据的个数多少，数值大小无关；(⑤)空间主要包括其大小与问题规模有关的成分变量所占空间，引用变量所占空间，以及递归栈所用的空间，还有在算法运行过程中动态分配和回收的空间。2.试用大O表示法给出下面程序的时间复杂性。voidout(floatx[][],intm,intn){floatsum[];for(inti=0;i

8、dl;}第二章数组笔做题2-3设有一个线性表（e0,e1,…,en-2,en-1）存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组