哈尔滨工程大学考研-数据结构-1.doc

《哈尔滨工程大学考研-数据结构-1.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、选择题1.算法的时间复杂度取决于（A）。A．问题的规模B.待处理数据的初态C.A和B2．一个算法应该是（B）。A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.3.下面关于算法说法错误的是（ABC）A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上几个都是错误的4．从逻辑上可以把数据结构分为（C）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构5．在下面的程序段中，对x的赋值语句的频度为（C）FORi:=1TOnDOF

2、ORj:=1TOnDOx:=x+1;A．O(2n)B．O(n)C．O(n2)D．O(log2n)二、判断题1.数据元素是数据的最小单位。（错，数据项是数据不可分割的最小单位。）2.数据的逻辑结构是指数据的各数据项之间的逻辑关系。（错，逻辑结构中描述的是数据元素之间的逻辑关系。）3．算法的优劣与算法描述语言无关，但与所用计算机有关。（错，同一个算法用不同的语言实现，或用不同的编译程序进行编译，或者在不同的计算机上运行时，效率均不同）4．数据的物理结构是指数据在计算机内的实际存储形式。（错，物理机构是指数据的逻辑结构在计算机存储器中的实现）5.数据结构的基本操作的设置的

3、最重要的准则是，实现应用程序与存储结构的独立。三、填空题1．数据的物理结构包括数据元素的表示和关系的表示。2．数据的逻辑结构是指数据集合中各数据元素之间所固有的逻辑关系。3．一个数据结构在计算机中存储关系称为存储结构。4．数据结构中评价算法的两个重要指标是时间复杂度和空间复杂度。5．在下面的程序段中，对ｘ的赋值语句的频度为O(n)（表示为n的函数）FOR　　i：＝１TOn　DO　　　FOR　　j：＝１　TOi　DO　FOR　k：＝1　TO　j　DO　ｘ：＝ｘ＋delta；四、应用题1.数据结构是一门研究什么内容的学科？数据结构是一门研究非数值计算的程序设计问题中计算

4、机的操作对象以及它们之间的关系和操作等的学科2.数据元素之间的关系在计算机中有几种表示方法？各有什么特点？集合：机构中的数据元素之间除了“同属一个集合”的关系外，别无其他关系；线性结构：结构中的数据元素之间存在一个对一个得关系；树形结构：结构中的数据元素之间存在一个对多个的关系；图状结构或网状结构：机构中的数据元素之间存在多个对多个的关系。3.数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？数据类型是一个值得集合和定义在这个值集上的一组操作的总称；抽象数据类型是指一个数学模型以及定义在该模型

5、上的一组操作。4.回答问题（1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？算法设计，取决于选定的逻辑结构；算法实现，依赖于选取的存储结构。（2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明之。对，如学生表，既可用顺序存储结构，又可用链式存储结构。（3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。对，如对全校学生进行学号查找，和对某个系进行学号查找，都用顺序存储结构，可是数据结构不同。（4）评价各种不同数据结构的标准是什么？取决于该数据结构

6、中数据元素及其之间关系的表示。5．评价一个好的算法，您是从哪几方面来考虑的？答：正确性，可读性，健壮性，效率及低存储量需求这四个方面。