数据结构习题

本文格式为Word版，下载可任意编辑——数据结构习题

习题一

一、选择题

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

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

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

3、线性表的规律顺序和存储顺序总是一致的，这种说法（B）。树形

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

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

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

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

2、数据元素是数据的__基本单位_，有些状况下也称为元素、结点、顶点、记录等。

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

4、简而言之，数据结构是数据之间的__相互关系_，即数据的_组织关系_。5、数据的规律结构是指数据之间的_规律关系_。规律结构是从_规律关系_上描述数据，它与具体存储无关，是独立于计算机的。因此规律结构可以看作是从具体问题抽象出来的_数学模型_。

6、数据的__存储结构_指数据元素及其关系在计算机存储器内的表示。__存储结构_是规律结构在计算机里的实现，也称之为映像。

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

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

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

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

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

15、索引存储方式又可以分为_稠密索引_和__稀疏索引_。若每个结点在索引表中都有

1

一个索引项，则该种索引存储方式称为_稠密索引_；若一组结点在索引表中只对应一个索引项，则索引存储方式称为_稀疏索引_。在_稠密索引中，索引项的地址指示结点所在的位置，而_稀疏索引_中，索引项的地址指示一组结点的起始位置。

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

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

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

19、算法的__确定_性是指算法中的每一个步骤必需是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。并且，在任何条件下，算法只能有惟一的一条执行路径，即只要输人是一致的就只能得到__一致__的输出结果。20、算法的__可行__性又称为算法的能行性，是指算法中描述的操作是可以通过已经实现的基本运算执行__有限__次来实现，即算法的___具体实现_应当能够被计算机执行。21、判断一个算法的好坏主要以下几个标准：__正确性_、__可读性_、__顽强性_、__效率__。

22、算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机__运行时间_的长短和___所占据空间__的大小。

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

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；O（m×n）2、写出下面算法的时间繁杂度：i＝0；S=0S=1s=0；

S=1+2while(s＜n）

S=1+2+3｛i++;

s+=i;

S=1+2+3++(m-1)｝O(n)m*(m-1)/2next=s;H.q=p;

B.p->next=p->next->next;I.while(p->next!=q)p=p->next;C.p->next=s->next;J.while(p->next!=NULL)p=p->next;D.s->next=p->next;K.p=q;E.s->next=L;L.p=L;F.s->next=p;M.L=s;G.s->next=NULL;N.L=p;

二、填空题

1．线性表（LinearList）是最简单、最常用的一种数据结构。线性表中的元素存在着__一对一_的相互关系。

2．线性表中有且仅有一个开始结点，表中有且仅有一个终端结点，除开始结点外，其他每个元素有且仅有一个__直接前驱_，除终端结点外，其他每个元素有且仅有一个_直接后继_。

3．线性表是n（n>=0）个数据元素的__有限序列_。其中n为数据元素的个数，定义为线性表的__长度_。当n为零时的表称为__空表_。

4．所谓顺序表（SequentialLISt）是线性表的__顺序存储结构_，它是将线性表中的结点按其__规律顺序_依次存放在内存中一组连续的存储单元中，使线性表中相邻的结点存放在__地址相邻_的存储单元中。

5．单链表不要求规律上相邻的存储单元在物理上也一定要相邻。它是分派一些_任意__的存储单元来存储线性表中的数据元素，这些存储单元可以分散在内存中的__任意_的位置上，它们在物理上可以是一片连续的存储单元，也可以是__不连续__的。因此在表示线性表这种数据结构时，必需在存储线性表元素的同时，也存储线性表的规律关系。

6．线性表的链式存储结构的每一个结点（Node）需要包括两个部分：一部分用来存放元素的数据信息，称为结点的_数据域_；另一部分用来存放元素的指向直接后继元素的指针(即直接后继元素的地址信息)，称为_指针域_或___链域__。

7．线性链表的规律关系是通过每个结点指针域中的指针来表示的。其规律顺序和物理存储顺序不再一致，而是一种__非顺序_存储结构，又称为__非顺序映像_。

8．假使将单链表最终一个结点的指针域改为存放链表中的头结点的地址值，这样就构成了__循环链表_。

9．为了能够快速地查找到线性表元素的直接前驱，可在每一个元素的结点中再增加一个指向其前驱的指针域，这样就构成了__双向链表_。

10．双向链表某结点的指针P，它所指向结点的