数据结构习题

习题一

一、选择题

1、数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的（）和运算的学科。

A．结构 B．关系 C．运算 D．算法 2、在数据结构中，从逻辑上可以把数据结构分成（）。

A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．逻辑结构和存储结构

3、线性表的逻辑顺序和存储顺序总是一致的，这种说法（）。

A．正确 B．不正确 C．无法确定 D．以上答案都不对

4、算法分析的目的是（）。

A．找出算法的合理性 B．研究算法的输人与输出关系 C．分析算法的有效性以求改进 D．分析算法的易懂性 二、填空题

1、_______是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储、加工和处理，________是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。例如，数学中所用到的整数和实数，文本编辑所用到的字符串等。

2、数据元素是数据的______，有些情况下也称为元素、结点、顶点、记录等。

3、________是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为________。

4、简而言之，数据结构是数据之间的________，即数据的________。

5、数据的逻辑结构是指数据之间的________。逻辑结构是从________上描述数据，它与具体存储无关，是独立于计算机的。因此逻辑结构可以看作是从具体问题抽象出来的______________。 6、数据的________指数据元素及其关系在计算机存储器内的表示。_________是逻辑结构在计算机里的实现，也称之为映像。

7、__________是指对数据施加的操作。它定义在数据的逻辑结构之上，每种逻辑结构都有一个____________。常用的有：查找、排序、插人、删除、更新等操作。 8、数据逻辑结构可以分为四种基本的类型，_______结构中的元素除了仅仅只是同属于一个_________________，不存在什么关系。

9、数据逻辑结构的四种基本类型中，________中的元素是一种一对一的关系，这种结构的特征是：若结构是非空集，则有且只有一个开始结点和一个终端结点，并且所有结点最多只能有一个直接前驱和一个直接后继。

10、数据逻辑结构的四种基本类型中，____________中的元素是一种一对多的关系。 11、图型结构或图状结构是一种________的关系。在这种逻辑结构中，所有结点均可以有多个前驱和多个后继。

12、有时也可将树型结构、集合和图型结构称为__________，这样数据的逻辑结构就可以分为__________和________两大类。 13、____________方式是指逻辑上相邻的结点被存储到物理上也相邻的存储单元中。这种存储结构只存储结点的数值，不存储结点之间的关系，结点之间的关系是通过存储单元的相邻关系隐含的表示出来的。

14、_______方式是种存储方法，不要求逻辑上相邻的结点在物理上也相邻，即数据元素可以存储在任意的位置上。

1

15、索引存储方式又可以分为______和________。若每个结点在索引表中都有一个索引项，则该种索引存储方式称为__________；若一组结点在索引表中只对应一个索引项，则索引存储方式称为________。在一中，索引项的地址指示结点所在的位置，而一中，索引项的地址指示一组结点的起始位置。

16、_________方式是利用结点关键字的值直接计算出该结点存储单元地址，然后将结点按某种方式存人该地址的一种方法。

17、所谓算法（Algorithm）是对特定问题求解方法和步骤的一种描述，它是指令的一组__________，其中每个指令表示一个或多个操作。

18、算法的_______性是指算法必须能够在执行有限个步骤之后结束，并且每个步骤都必须在有穷的时间内完成。

19、算法的________性是指算法中的每一个步骤必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。并且，在任何条件下，算法只能有惟一的一条执行路径，即只要输人是相同的就只能得到____________的输出结果。 20、算法的____________性又称为算法的能行性，是指算法中描述的操作是可以通过已经实现的基本运算执行_________次来实现，即算法的__________应该能够被计算机执行。 21、判断一个算法的好坏主要以下几个标准：________、________、________、_________。 22、算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机_________的长短和___________________的大小。

23、空间复杂度（SPace ComPlexity）也是度量一个算法好坏的标准，它所描述的是算法在运行过程中所占用_____________的大小。 三、判断题

1、顺序存储方式只能用于存储线性结构。（） 2、数据元素是数据的最小单位。（）

3、算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言描述，则算法实际上就是程序了。（）

4、数据结构是带有结构的数据元素的集合。（）

5、数据的逻辑结构是指各元素之间的逻辑关系，是用户根据需要而建立的。（） 6、数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。（）

7、数据的物理结构是指数据在计算机中实际的存储形式。（）

8、具有存取任一元素的时间相等这一特点的存储结构称为随机存取结构。（） 四、综合题

1、用大O形式表示下面算法的时间复杂度： for（i=0；i＜m；i十十） for（j=0；j＜n；j＋＋） A[i][j]=i*j；

2、写出下面算法的时间复杂度： i＝0； s=0；

while(s＜n） ｛ i++; s+=i; ｝

2

3、写出以下算法的时间复杂度： for（i＝0; i＜m; i＋＋）

for（j＝0 ; j＜t; j＋＋）

c[i][j]=0；

for（i=0；i＜m；i＋＋）

for（j=o; j

for（k=0；k＜n；k＋＋） c［i］［j］＋＝a［i］［k］*b[k][j];

4、写出下面算法的时间复杂度：

i=1;

while（i＜＝n）

i=i*3;

5、求下面函数中各条语句的频度和算法的时间复杂度：

prime（int n） ｛

int i＝2； while ((n％i）！=0＆＆i＜sqrt(n) ) i++;

if（i＞sqrt(n) )

printf（”％d is a prime number.＼n”，n）； else

printf（”％d is not a prime number.＼n”，n）；｝ 3

习题二

一、选择题

1．在一个长度为n的顺序表中删除第i个元素（0＜i

2．从一个具有n个元素的线性表中查找其值等于x的结点时，在查找成功的情况下，需平均比较( )个元素结点。

A．n/2 B．n C．(n-1)/2 D．(n +1)/2 3．对一个具有n个元素的线性表，建立其单链表的时间复杂度为( )。 A．O(n) B．O(1) C．O(n2） D．O（long2n） 4．线性表采用链式存储时，其地址( )。

A． 必须是连续的 B．一定是不连续的 C．部分地址必须连续 D．连续与否均可以

5．在一个具有n个结点的有序单链表中插人一个新的结点，使得链表仍然有序，该算法的时间复杂度是( )。

A．O（long2n） B．O（l） C．O（n2） D．O（n）

6．线性表是( )。

A．一个有限序列，可以为空 B．一个有限序列，不可以为空 C．一个无限序列，可以为空 D．一个无限序列，不可以为空 7．在一个长度为n的顺序表中，向第i个元素（0一1＜n＋1）之前捕人一个新元素时，需要向后移动( )个元素。

A．n-i B．n-i＋1 C．n－i－1 D．i＋1 8．如果某链表中最常用的操作是取第i个结点及其前驱，则采用( )存储方式最节省时间。

A．单链表 B．双向链表 C．单循环链表 D．顺序表

9．一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（）。

A．98 B．100 C．102 D．106

10．下列排序方法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )。 A．堆排序 B．冒泡排序 C．直接插人排序 D．快速排序 11．对线性表进行二分查找时，要求线性表必须（）。 A．以顺序方法存储 B．以链接方法存储

C．以顺序方法存储，且结点接关键字有序排列 D．以链接方法存储，且结点接关键字有序排列

12．在顺序存储的线性表（a1??an）中，删除任意一个结点所需移动结点的平均移动次数为( )

A．n B．n／2 C．(n-1)/2 D．（n＋l）/2 13．在线性表的下列存储结构中，读取元素花费的时间最少的是（）。 A．单链表 B．双链表 C．循环链表 D．顺序表

14．若某链表中最常用的操作为在最后一个结点之后插入一个结点和删除最后一个结点，则采用（）存储方式最节省时间。

A．双链表 B．单链表 C．单循环链表 D．带头结点的双循环链表 二、填空题

1．线性表（Linear List）是最简单、最常用的一种数据结构。线性表中的元素存在着

4