《数据结构》习题及答案 袁凌 -第1--5章.docx

第一章

一、选择题

1．以下说法不正确的是B 。

A．数据可由若干个数据元素构成 B．数据项可由若干个数据元素构成

C．数据元素是数据的基本单位 D．数据项是不可分割的最小标识单位

2．以下属于数据结构中非线性结构的是D 。

A．栈 B．串 C．队列 D．平衡二叉树

3．以下属于逻辑结构的是B 。

A．顺序表 B．有序表 C．双链表 D．单链表

4．在计算机中存储数据时，通常不仅要存储各数据元素的值，还要存储C 。

A．数据的处理方法 B．数据元素的类型

C．数据元素之间的关系 D．数据的存储方法

5．数据结构在计算机内存中的表示是指A 。

A．数据的存储结构 B．数据结构 C．数据的逻辑结构D．数据元素之间的关系

6．数据采用链式存储结构时，要求A 。

A．每个结点占用一片连续的存储区域 B．所有结点占用一片连续的存储区域

C．结点的最后一个数据域是指针类型 D．每个结点有多少个后继就设多少个指针域

7．以下说法中错误的是B 。

（1）原地算法是指不需要任何额外的辅助空间

（2）在相同的问题规模n下，时间复杂度为O(nlog2n)的算法在执行时间上总是优于时间复杂度为O(n2)的算法

（3）时间复杂度通常是指最坏情况下，估计算法执行时间的一个上限

（4）一个算法的时间复杂度与实现算法的语言无关

A．（1） B．（1）、（2）、（4）C．（1）、（4） D．（3）

8．下面程序的时间复杂度为B 。

A．O(n) B．O(n2) C．O(n3) D．O(n4)

9．【20l7统考真题】下列函数的时间复杂度是B 。

A．O(logn) B．O(n1/2) C．O(n) D．O(nlogn)

10．以下函数中时间复杂度最小的是A 。

A．T1(n)=1000log2n B．T2(n)=nlog2n-1000log2n

C．T3(n)=n2-1000log2n D．T4(n)=2nlog2n-1000log2n

11．【2019统考真题】设n是描述问题规模的非负整数，下列程序段的时间复杂度是B 。

A．O(logn) B．O(n1/2) C．O(n) D．O(n2)

12．下面程序的时间复杂度为C 。

A．O(n) B．O(n2) C．O(log2n) D．O(nlog2n)

13．下面程序的时间复杂度为A 。

A．O(n) B．O(n2) C．O(log2n) D．O(nlog2n)

14．【2013统考真题】已知两个长度分别为m和n的升序链表，若将它们合并为长度为m+n的一个降序链表，则最坏情况下的时间复杂度是D 。

A．O(n) B．O(nm) C．O(min(m,n)) D．O(max(m,n))

15．算法的时间复杂度为O(n2)，表明该算法的C 。

A．问题规模是n2 B．执行时间等于n2

C．执行时间与n2成正比 D．问题规模与n2成正比

二、判断题

1．数据元素是数据的最小单位。（×）

2．数据对象就是一组任意数据元素的集合。（×）

3．数据的逻辑结构与数据元素在计算机中如何存储有关。（×）

4．如果数据元素值发生改变，则数据的逻辑结构也随之改变。（×）

5．逻辑结构相同的数据，可以采用多种不同的存储方法。（√）

6．逻辑结构不相同的数据，必须采用多种不同的存储方法。（×）

7．数据的逻辑结构是指数据的各数据项之间的逻辑关系。（×）

8．算法的优劣与算法描述语言无关，但与所用的计算机有关。（×）

9．程序一定是算法。（×）

10．算法的可行性是指指令不能有二义性。（×）

第二章

一、选择题

1．线性表是具有n个C的有限序列。

A．表元素 B．字符 C．数据元素 D．数据项

2．关于线性表的正确说法是D。

A．每个元素都有一个前驱和一个后继元素

B．线性表中至少有一个元素

C．表中元素的排列顺序必须是由小到大或由大到小

D．除首元素和尾元素外，其余元素有且仅有一个直接前驱和一个直接后继元素

3．线性表采用链表存储时，其存放各个元素的单元地址是D 。

A．必须连续的 B．一定不连续的

C．部分地址必须连续的 D．连续与否均可以

4．线性表的静态链表存储结构与顺序存储结构相比，优点是C 。

A．所有的操作算法实现简单 B．便于随机存取

C．便于插入和删除 D．便于利用零散的存储器空间

5．设线性表中有n个元素，以下 A操作在单链表上实现要比在顺序表上实现效率高。

A．删除指定位置元素的后一个元素

B．在第n个元素的后面插入一个新元素

C．顺序输出前k个元素

D．交换第i个元素和第n-i+1个元素的值

6．在单链表中，增加一个头结点的目的是C 。

A．使单链表至少有一个结点