数据结构期末习题答案.doc

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

1、第一章绪论一，选择题1．组成数据的基本单位是（　）A．数据项　　B．数据类型　　C．数据元素　　D．数据变量2．数据结构是研究数据的（　）以及它们之间的相互关系。A．理想结构，物理结构　　B．理想结构，抽象结构C．物理结构，逻辑结构　　D．抽象结构，逻辑结构3．算法分析的两个主要方面是（）A．正确性和简单性　　B．可读性和文档性C．数据复杂性和程序复杂性　D．时间复杂度和空间复杂度4．算法分析的目的是（）。A．找出数据结构的合理性　B．研究算法中的输入和输出的关系C．分析算法的效率以求改进　D．分析算法的易懂性和文档性5.算法的

2、时间复杂度取决于（）A．问题的规模B.待处理数据的初态C.A和B　Ｄ．以上都不是6．一个算法应该是（）。A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.7.下面关于算法说法错误的是（）A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上几个都是错误的8．从逻辑上可以把数据结构分为（）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构9．程序段for(i=n-1;i>=1;i--)for(

3、j=1j<=i;j++)if(A[j]>A[j+1])A[j]与A[j+1]对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（）A．O（n）B．O(nlogn)C.．O(n3)D．O(n2)10．连续存储设计时，存储单元的地址（）。A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续二，判断题1．数据结构的抽象操作的定义与具体实现有关。()2．数据结构是数据对象与对象中数据元素之间关系的集合。3．在顺序存储结构中，有时也存储数据结构中元素之间的关系。()4．数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按

4、使用的需要建立的。5．算法和程序原则上没有区别，在讨论数据结构是两者是通用的。6．同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数都相等。7．数据的逻辑结构与数据元素本身的内容和形式无关。8．算法的优劣与算法描述语言无关，但与所用计算机有关。()9．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。()10．算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。()一，选择题1．C2．C3．D4．C5．C6．B7．D8．C9．D10．A二，判断题1.×

5、2.√3.×4.√5.×6.×7.√8.×9.√10.×三，填空1．数据的物理结构包括的表示和的表示。2.对于给定的n个元素,可以构造出的逻辑结构有，，，___四种。3．一个数据结构在计算机中称为存储结构。4．抽象数据类型的定义仅取决于它的一组___，而与__无关，即不论其内部结构如何变化，只要它的__不变，都不影响其外部使用。5．线性结构中元素之间存在关系,树形结构中元素之间存在关系,图形结构中元素之间存在关系。6．一个算法有5个特性:、、，有零个或多个输入、有一个或多个输出。7．已知如下程序段for（i=n；i<=1;i++

6、）{语句1}{x:=x+1；{语句2}for(j=n;j<=i;j++){语句3}y:=y+1;{语句4}}语句1执行的频度为；语句2执行的频度为；语句3执行的频度为；语句4执行的频度为。8．在下面的程序段中，对ｘ的赋值语句的频度为______（表示为n的函数）for(i＝1;i<=n;i++)for(j＝１;j<=i;j++)for(k＝1;k<=j;j++)ｘ＝ｘ＋delta；9.计算机执行下面的语句时，语句s的执行次数为_______。for(i=l；i=i;j--)s;10.下面程序

7、段的时间复杂度为________。(n>1)sum=1；for(i=0;sum

8、?2．什么是数据结构?数据结构是研究什么内容的学科？有关数据结构的讨论涉及哪三方面?3．评价一个好的算法，从哪几方面考虑？4.若将数据结构定义为一个二元组（D，R）,说明符号D，R应分别表示什么？5．解释算法与程序的区别？6．有下列几种用二元组表示的数据结构，画