数据结构第一章测试(长春理工大学精品课)(共3页).docx

《数据结构第一章测试(长春理工大学精品课)(共3页).docx》由会员分享，可在线阅读，更多相关《数据结构第一章测试(长春理工大学精品课)(共3页).docx（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上数据结构测试（长春理工大学精品课）第1章绪论一、选择题1.计算机算法指的是（）。查看答案A计算方法 B.排序方法 C.解决问题的步骤序列 D.调度方法答案是:C解释：计算机算法指的是对特定问题的求解步骤。收起2从逻辑上可以把数据结构分为（）两大类。查看答案A动态结构、静态结构 B顺序结构、链式结构C线性结构、非线性结构 D初等结构、构造型结构答案是C解释：逻辑结构主要分为集合，线性，树，图四种。集合，树形，图结构又被称为非线性结构。收起3以下与数据的存储结构无关的术语是（）。查看答案A循环队列 B.链表 C.哈希表 D.栈答案是D解释：栈是一种逻辑结构，是操作受限制的

2、线性表，存储时可采用顺序存储或链式存储方式。收起4以下数据结构中，哪一个是线性结构（）？查看答案A广义表 B.二叉树 C.稀疏矩阵 D.串答案是D解释：串是数据元素确定为字符的线性表，。收起5在下面的程序段中，对x的赋值语句的频度为（）查看答案FOR（i=1;i=n;i+) FOR（j=1;j0;i-) FOR (j=1;jAj+1) Aj与Aj+1对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（）查看答案A. O（n） B.O(nlogn) C. O(n3) D. O(n2)答案是D解释：i=n-1时，语句执行n-1次；i=n-2时，语句执行n-2次；依次类推，i=1时，语句执行1

3、次，因此语句执行次数=（n-1）+（n-2）+.+1=（n-1）n/2，时间复杂度为O(n2)。收起7以下数据结构中，（）是非线性数据结构。查看答案A树 B字符串 C队 D栈答案是A解释：非线性数据结构包括树，图，集合。收起8连续存储设计时，存储单元的地址（）。查看答案A一定连续 B一定不连续 C不一定连续 D部分连续，部分不连续答案是A解释：顺序储存占连续的存储空间。收起9以下属于逻辑结构的是（）。查看答案A顺序表 B.哈希表 C.有序表 D.单链表答案是C解释：有序表指的是表中元素按关键字有序，存储结构可以选择顺序结构，也可选择链式结构。收起10.算法的时间复杂度取决于（）查看答案A问题的

4、规模 B.待处理数据的初态 C. A和B答案是C收起二、填空题1.对于给定的n个元素,可以构造出的逻辑结构有 -（1）-，-（2）-，-（3）-，_（4）_四种。查看答案正确答案是:集合线性结构树形结构图状结构或网状结构收起2数据结构中评价算法的两个重要指标是。查看答案正确答案是:时间复杂度和空间复杂度解释：衡量算法优劣一般从时间和空间两方面考虑。收起3.数据结构是研讨数据的_（1）_和_（2）_，以及它们之间的相互关系，并对与这种结构定义相应的_（3）_，设计出相应的（4）_。查看答案正确答案是:（1）逻辑结构（2）物理结构（3）操作（运算）（4）算法。收起4已知如下程序段FOR（i=n;i

5、0;i-) 语句1 x:=x+1； 语句2 FOR (j=n;j=i;j-) y:=y+1; 语句1执行的频度为 （1） ；语句2执行的频度为 （2） ；查看答案正确答案是:（1）n+1（2）n解释：语句1执行的次数是i从n到0,所以是n+1次；语句2执行的次数是i从n到1,所以执行了n次。收起5.下面程序段中带下划线的语句的执行次数的数量级是：i=1；WHILE（in）i：=i*2;查看答案正确答案是:log2n解释：i的变换是以2次幂的方式增长，即i的变化是1,2，4,8.，所以执行的次数是log2n级别。收起三、应用题1.数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数

6、据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？查看答案解：数据类型是程序设计语言中的一个概念，它是一个值的集合和操作的集合。如C语言中的整型、实型、字符型等。整型值的范围（对具体机器都应有整数范围），其操作有加、减、乘、除、求余等。实际上数据类型是厂家提供给用户的已实现了的数据结构。“抽象数据类型（ADT）”指一个数学模型及定义在该模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部如何表示和实现无关。无论其内部结构如何变化，只要它的数学特性不变就不影响它的外部使用。抽象数据类型和数据类型实质上是一个概念。此外，抽象数据类型的范围更广，它已不再局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自行定义的数据类型。使用抽象数据类型定义的软件模块含定义、表示和实现三部分，封装在一起，对用户透明（提供接口），而不必了解实现细节。抽象数据类型的出现使程序设计不再是“艺术”，而是向“科学”迈进了一步。收起2.当你为解决某一问题而选择数据结构时，应从哪些方面考虑？查看答案解： 通常考虑算法所需要的存储空间量和算法所需要的时间量。后者又涉及到四方面：程序运行时所需输入的数据总量，对源程序进行编译所需时间，计算机执行每条指令所需时间和程序中指令重复执行的次数。收起专心-专注-专业