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

1、数据结构测试（长春理工大学精品课）第1章     绪论        一、选择题1.计算机算法指的是（    ）。查看答案 A计算方法     B. 排序方法     C. 解决问题的步骤序列      D. 调度方法 答案是:C 解释：计

2、算机算法指的是对特定问题的求解步骤。收起2从逻辑上可以把数据结构分为（    ）两大类。查看答案A动态结构、静态结构       B顺序结构、链式结构 C线性结构、非线性结构     D初等结构、构造型结构 答案是C   解释：逻辑结构主要分为集合，线性，树，图四种。集合，树形，图结构又被称为非线性结构。收起3以下与数据的存储结构无关的术语是（    ）。查看答案A循

3、环队列       B. 链表        C. 哈希表       D.  栈 答案是D   解释：栈是一种逻辑结构，是操作受限制的线性表，存储时可采用顺序存储或链式存储方式。收起4以下数据结构中，哪一个是线性结构（    ）？查看答案A广义表   

4、60;     B. 二叉树      C. 稀疏矩阵         D.  串 答案是D   解释：串是数据元素确定为字符的线性表，。收起5在下面的程序段中，对x的赋值语句的频度为（    ）查看答案FOR （i=1;i<=n;i+)    FOR 

5、（j=1;j<=n;j+)             X+;A 2n       Bn       Cn2         Dlog2n  答案是C   解释：语句的频度是语句执行的次数，x+语句执行的次数是外层循环

6、次数*内层循环次数，即为n*n次。收起6程序段   FOR  (i=n-1;i>0;i-)            FOR (j=1;j<=i;j+)                IF (Aj>Aj+1)       &#

7、160;           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时，语句

8、执行n-2次；依次类推，i=1时，语句执行1次，因此语句执行次数=（n-1）+（n-2）+.+1=（n-1）n/2，时间复杂度为 O(n2) 。收起7以下数据结构中，（    ）是非线性数据结构。查看答案A树        B字符串       C队           D栈 答案是A &

9、#160;  解释：非线性数据结构包括树，图，集合。收起8连续存储设计时，存储单元的地址（    ）。查看答案A一定连续  B一定不连续  C不一定连续  D部分连续，部分不连续 答案是A    解释：顺序储存占连续的存储空间。收起9以下属于逻辑结构的是（    ）。查看答案A顺序表       B. 哈希表   &#

10、160;    C.有序表         D.  单链表 答案是C    解释：有序表指的是表中元素按关键字有序，存储结构可以选择顺序结构，也可选择链式结构。 收起10. 算法的时间复杂度取决于（    ）查看答案A问题的规模      B. 待处理数据的初态    

11、  C. A和B 答案是C  收起 二、填空题1. 对于给定的n个元素,可以构造出的逻辑结构有  -（1）-  ，-（2）-  ，-（3）-  ，_（4）_四种。查看答案  正确答案是:集合  线性结构   树形结构   图状结构或网状结构   收起2数据结构中评价算法的两个重要指标是。查看答案   

12、;正确答案是:时间复杂度和空间复杂度     解释：衡量算法优劣一般从时间和空间两方面考虑。收起3. 数据结构是研讨数据的_（1）_和_（2）_，以及它们之间的相互关系，并对与这种结构定义相应的_（3）_，设计出相应的（4）_。查看答案  正确答案是:（1）逻辑结构（2）物理结构（3）操作（运算）（4）算法。   收起       4已知如下程序段FOR （i= n;i>0;i-) 

13、;              语句1     x:=x+1；               语句2   FOR (j=n;j>=i;j-)           y:=y+1;  

14、0;                 语句1执行的频度为 （1） ；语句2执行的频度为 （2） ；查看答案正确答案是:（1）n+1  （2）n解释：语句1执行的次数是i从n到0,所以是n+1次；语句2执行的次数是i从n到1,所以执行了n次。 收起5.下面程序段中带下划线的语句的执行次数的数量级是：         &#

15、160;    i=1；WHILE （i<n）i：=i*2;查看答案 正确答案是: log2n    解释：i的变换是以2次幂的方式增长，即i的变化是1,2，4,8.，所以执行的次数是log2n级别。收起     三、应用题1. 数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？查看答案解：    数据类型是

16、程序设计语言中的一个概念，它是一个值的集合和操作的集合。如C语言中的整型、实型、字符型等。整型值的范围（对具体机器都应有整数范围），其操作有加、减、乘、除、求余等。实际上数据类型是厂家提供给用户的已实现了的数据结构。“抽象数据类型（ADT）”指一个数学模型及定义在该模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部如何表示和实现无关。无论其内部结构如何变化，只要它的数学特性不变就不影响它的外部使用。抽象数据类型和数据类型实质上是一个概念。此外，抽象数据类型的范围更广，它已不再局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自行定义的数据类型。使用抽象数