数据结构作业第1章

《数据结构作业第1章》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第1章绪论1.填空（1）（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。（2）（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。（3）从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。（4）数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。（5）算法具有五个特性，分别是（）、（）、（）、（）、（）。（6）在一般情况下，一个算法的时间复杂度是（）的函数。（7）设待处理问题的规模为n,若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n,则表

2、示成数量级的形式为（）。2.选择题⑴顺序存储结构屮数据元素Z间的逻辑关系是由（）表示的，链式存储结构屮的数据元素之间的逻辑关系是由（）表示的。A线性结构B非线性结构C存储位置D指针⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（）。A树B图C线性表D集合⑶算法指的是（）oA对特定问题求解步骤的一种描述，是指令的有限序列。B计算机程序C解决问题的计算方法D数据处理⑷下面（）不是算法所必须具备的特性。A有穷性B确切性C高效性D可行性⑸算法分析的目的是（）

3、，算法分析的两个主要方面是（）oA找出数据结构的合理性B研究算法中输入和输出的关系C分析算法的效率以求改进D分析算法的易读性和文档性E空间性能和时间性能F正确性和简明性G可读性和文档性H数据复杂性和程序复杂性3.判断题（1）算法的时间复杂度都要通过算法中的基本语句的执行次数來确定。（2）每种数据结构都具备三个基本操作：插入、删除和查找。（3）逻辑结构与数据元素本身的内容和形式无关。（4）基于某种逻辑结构之上的基本操作，其实现是唯一的。4.分析以下各程序段，并用大O记号表示其执行时间。(1)i=l;k=0;(2)i=l;k=0;while(i

4、do{{k=k+10*i;k=k+10*i;i++;i++;}}while(i<=n)⑶i=l；j=0;⑷y=0;while(i+j<=n)while((y+l)*(y+l)<=n)if(i>j)j++；elsei++;尸y+i;⑸for(i=l;i<=n;i++)for(j=l；jv=i;j++)for(k=l;k<=j;k++)x++;5・设有数据结构（D,R）,其中D二{1,2,3,4,5,6},R={,<2,3>,<2,4>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>}。试画出其逻辑结构图并指出属于何种结构。6・求多

5、项式A（x）的算法可根据下列两个公式之一来设计：（1）A（x）=anxn+an-1x11l+...+alx+aO⑵A（x）=（...（（O*x+an）x+an-1）x+...+al）x）+aO根据算法的吋间复杂度分析比较这两种算法的优劣。7・算法设计（要求：算法用伪代码和C++描述，并分析最坏情况下的时

6、'可复杂度）（1）对一个整型数组A[n]设计一个排序算法。⑵找出整型数组A[n]中元素的最大值和次最大值。学习自测及答案1.顺序存储结构的特点是（）,链式存储结构的特点是（）。2.算法在发生非法操作时可以作出处理的特性称为（）。3・常见的算法时间复杂

7、度用大o记号表示为：常数阶（）、对数阶（）、线性阶（）、平方阶（）和指数阶（）。4・将下列函数按它们在n时的无穷大阶数，从小到大排列。n,n-n3+7n5,nlogn,2n/2,n3,log2n,nl/2+log2n,（3/2）n,n!,n2+log2n5.试描述数据结构和抽彖数据类型的概念与程序设讣语言中数据类型概念的区别。6・对下列用二元组表示的数据结构，试分别画出对应的逻辑结构图，并指出属于何种结构。(1)A=(D,R),其中D二{al,a2,a3,a4},R={}(2)B=(D,R),其中D二{a,b,c,d,e,f},R={,

8、,c>,,,}(3)C=(D,R),其中D={a,b,c,d,e,f},R={(d,b),(e,g),(a,b),(b,c),(e,g),(g,h)}(4)D=(D,R),其中D二{1,2,3,4,5,6},R二{(1,2),(1,4),(2,3),(2,4),(3,4),(3,5),(3,6),(4,6)}7.求下列算法的时间复杂度。count=0;x=l;while(x<=n){x*=2;count++;1returncount;