专升本数据结构复习题.doc

《专升本数据结构复习题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.填空⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。⑺在一般情况下，一个算法的时间复杂度是（）的函数。⑻设待处理问题的规模为n，若一个算法的

2、时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。2.选择题⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。A线性结构B非线性结构C存储位置D指针⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（）。A树B图C线性表D集合⑶算法指的是（）。A对特定问题求解步骤的一种描述，是指令的有限序列。B计算机程序C解决

3、问题的计算方法D数据处理⑷下面（）不是算法所必须具备的特性。A有穷性B确切性C高效性D可行性⑸算法分析的目的是（），算法分析的两个主要方面是（）。A找出数据结构的合理性B研究算法中输入和输出的关系C分析算法的效率以求改进D分析算法的易读性和文档性E空间性能和时间性能F正确性和简明性G可读性和文档性H数据复杂性和程序复杂性3.判断题⑴算法的时间复杂度都要通过算法中的基本语句的执行次数来确定。⑵每种数据结构都具备三个基本操作：插入、删除和查找。⑶所谓数据的逻辑结构指的是数据之间的逻辑关系。⑷逻辑结构与数据元素本身的内

4、容和形式无关。⑸基于某种逻辑结构之上的基本操作，其实现是唯一的。4.分析以下各程序段，并用大O记号表示其执行时间。⑴i=1;k=0;　　　　　　　while(ij)j++;　　elsei++;⑸for(i=1;i<=n;i++)f

5、or(j=1;j<=i;j++)for(k=1;k<=j;k++)x++;　　　5．设有数据结构（D，R），其中D={1,2,3,4,5,6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。试画出其逻辑结构图并指出属于何种结构。学习自测及答案1．顺序存储结构的特点是（），链接存储结构的特点是（）。2.算法在发生非法操作时可以作出处理的特性称为（）。3.常见的算法时间复杂度用大Ｏ记号表示为：常数阶()、对数阶()、线性阶()、平方阶()和指数阶()。4．将下

6、列函数按它们在n®¥时的无穷大阶数，从小到大排列。n,n-n3+7n5,nlogn,2n/2,n3,log2n,n1/2+log2n,(3/2)n,n!,n2+log2n5．对下列用二元组表示的数据结构,试分别画出对应的逻辑结构图，并指出属于何种结构。⑴A=(D，R)，其中D={a1,a2,a3,a4}，R={}⑵B=(D，R)，其中D={a,b,c,d,e,f}，R={,,,,}⑶C=(D，R)，其中D={a，b，c，d，e，f}，R={,,

7、,,,}⑷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)}6.求下列算法的时间复杂度。count=0;x=1;while(x