《数据结构》-数据结构试卷第一章

数据结构期末复习题及参考答案第1章绪论一、选择题1、算法的时间复杂度取决于（）A问题的规模B待处理数据的初态CA和B2、计算机算法指的是（1），它必须具备（2）这三个特性。1A计算方法B排序方法C解决问题的步骤序列D调度方法2A可执行性、可移植性、可扩充性B可执行性、确定性、有穷性C确定性、有穷性、稳定性D易读性、稳定性、安全性3、一个算法应该是（）。A程序B问题求解步骤的描述C要满足五个基本特性DA和C4、以下的算法时间复杂度中，算法速度最快的是（）。AONBONLOG2NCON2DO2N5、下面说法错误的是（）1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模N下，复杂度ON的算法在时间上总是优于复杂度O2N的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A1B1,2C1,4D36、从逻辑上可以把数据结构分为（）两大类。A动态结构、静态结构B顺序结构、链式结构C线性结构、非线性结构D初等结构、构造型结构7、下面程序的时间复杂度为（）FORI0IARRJKARRIARRIARRJARRJKAONBON2COLOG2NDO2N9、以下数据结构中，（）是非线性数据结构。A树B字符串C队D栈10、连续存储设计时，存储单元的地址（）。A一定连续B一定不连续C不一定连续D部分连续，部分不连续二、填空题1、数据的物理结构包括数据元素的表示和数据元素间关系的表示。2、根据数据元素之间的逻辑关系，一般可以构造出四种逻辑结构分别是集合、线性结构、树形结构、图状或网状结构。3、数据的逻辑结构是指数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或称“邻接关系”。4、一个数据结构在计算机中表示（又称映像）称为存储结构。5、如果一个算法的时间复杂度是N34N2LOG2N3N/N，那么用数量级表示的时间复杂度应该是ON2。6、抽象数据类型的定义仅取决于它的一组逻辑特性_，而与在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。7、数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。8、算法设计应考虑4种质量要求正确性、可读性、健壮性、效率与低存储量要求。9、数据结构是研讨数据的逻辑结构和物理结构_，以及它们之间的相互关系，并对与这种结构定义相应的操作（运算），设计出相应的算法_。10、一个算法具有5个重要特性有穷性、确定性、可行性、有零个或多个输入、有一个或多个输出。11、请分析如下程序代码的时间复杂度，填写其中的空格VOIDDELETEALLINTARRAY,INTN,INTTARGETINTI0WHILEIIJS13、下面程序段的时间复杂度为_ON_。N1SUM1；FORI0SUMI1JFORK1KJ1KSUMPRINTF“SUMDN“,SUM；RETURNSUM参考答案第一层FOR循环判断N1次，往下执行N次，第二层FOR执行次数为NN1N21，第三层循环体受第一层循环和第二层循环的控制，其执行次数如下表执行次数为