数据结构习题集包含全部答案

数据结构习题集(自编)

第一章绪论

一、选择题

1.数据结构就是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的()与运算的学科。

A.结构

B.关系

C.运算

D.算法

2.在数据结构中,从逻辑上可以把数据结构分成()。

A.动态结构与静态结构

B.紧凑结构与非紧凑结构

C.线性结构与非线性结构

D.逻辑结构与存储结构

3.线性表的逻辑顺序与存储顺序总就是一致的,这种说法()。

A.正确

B.不正确

C.无法确定

D.以上答案都不对

4.算法分析的目的就是()。

A.找出算法的合理性

B.研究算法的输人与输出关系

C.分析算法的有效性以求改进

D.分析算法的易懂性

5、算法的时间复杂度取决于( )

A.问题的规模B待处理数据的初态 C、 A与B

6.一个算法应该就是( )。

A.程序

B.问题求解步骤的描述

C.要满足五个基本特性

D.A与C、

7、下面关于算法说法错误的就是( )

A.算法最终必须由计算机程序实现

B、为解决某问题的算法与为该问题编写的程序含义就是相同的

C、算法的可行性就是指指令不能有二义性

D、以上几个都就是错误的

8.以下与数据的存储结构无关的术语就是( )。

A.循环队列 B、链表 C、哈希表D、栈

9.在下面的程序段中,对x的赋值语句的频度为( )

for(i=0;i

for(j=0;j

x=x+1;

n

A. 2n

B.n

C.n2

D.log

2

10.以下数据结构中,( )就是非线性数据结构

A.树

B.字符串

C.队列

D.栈

11、下列数据中,( )就是线性数据结构。

A.哈夫曼树 B、有向无环图 C、二叉排序树 D、栈

12.以下属于逻辑结构的就是( )。

A.顺序表 B、哈希表C、有序表 D、单链表

二、填空题

1、_______就是信息的载体,就是对客观事物的符号表示,它能够被计算机识别、存储、加工与处理,________就是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。(数据、数据)

2、数据元素就是数据的______,有些情况下也称为元素、结点、顶点、记录等。(基本单位)

3、________就是数据不可分割的最小单元,就是具有独立含义的最小标识单

位。例如构成一个数据元素的字段、域、属性等都可称之为________。(数据项、数据项)

4、数据的逻辑结构就是指数据之间的________。逻辑结构就是从________上描述数据,它与具体存储无关,就是独立于计算机的。因此逻辑结构可以瞧作就是从具体问题抽象出来的______________。(逻辑关系、逻辑关系、数学模型)

5、数据的________指数据元素及其关系在计算机存储器内的表示。_________就是逻辑结构在计算机里的实现,也称之为映像。(存储结构、存储结构)

6、数据逻辑结构可以分为四种基本的类型,_______结构中的元素除了仅仅只就是同属于一个_________________,不存在什么关系。(集合、集合)

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

8、数据逻辑结构的四种基本类型中,____________中的元素就是一种一对多的关系。(树形结构)

9、图型结构或图状结构就是一种________的关系。在这种逻辑结构中,所有结点均可以有多个前驱与多个后继。(多对多)

10、有时也可将树型结构、集合与图型结构称为__________,这样数据的逻辑结构就可以分为__________与________两大类。(非线性结构、线性结构、非线性机构)

11、____________方式就是指逻辑上相邻的结点被存储到物理上也相邻的存储单元中。这种存储结构只存储结点的数值,不存储结点之间的关系,结点之间的关系就是通过存储单元的相邻关系隐含的表示出来的。(顺序存储)

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

13、_________方式就是利用结点关键字的值直接计算出该结点存储单元地址,然后将结点按某种方式存人该地址的一种方法。(散列存储或哈希存储)

14、所谓算法(Algorithm)就是对特定问题求解步骤的一种描述,它就是指令的其中每个指令表示一个或多个操作。算法的五个重要特性就是__________、__________、__________、__________与__________。(有限序列、有穷性、确定性、可行性、输入、输出)

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

16、算法的________性就是指算法中的每一个步骤必须就是有明确定义的,不允许有模棱两可的解释,也不允许有多义性。并且,在任何条件下,算法只能有惟一的一条执行路径,即只要输人就是相同的就只能得到____________的输出结果。(确定性、相同)

17、算法的____________性又称为算法的能行性,就是指算法中描述的操作就是可以通过已经实现的基本运算执行有限次来实现。(可行性)

18、判断一个算法的好坏主要以下几个标准:________、________、________、_________。(正确性、可读性、健壮性、时间效率与空间效率)

19、算法分析就是对一种算法所消耗的计算机资源的估算,其中包括计算机_________的长短与___________________的大小。(运行时间、所占据空间)

20、空间复杂度(SPace ComPlexity)也就是度量一个算法好坏的标准,它所

描述的就是算法在运行过程中所占用_____________的大小。(存储空间)

三、判断题

1.顺序存储方式只能用于存储线性结构。(×)

2.数据元素就是数据的最小单位。(×)

3.算法的优劣与算法描述语言无关,但与所用计算机有关。(×)

4.健壮的算法不会因非法的输入数据而出现莫名其妙的状态。()

5.数据的逻辑结构就是指各元素之间的逻辑关系,就是根据用户需要而建立

的。

6.数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、

数据域。()

7.数据的物理结构就是指数据在计算机中实际的存储形式。()

8.具有存取任一元素的时间相等这一特点的存储结构称为随机存取结构。

9.算法实际上就就是程序,程序也一定就是算法。(×)

10、在顺序存储结构中,有时也存储数据结构中元素之间的关系。(×)

11、顺序存储方式的优点就是存储密度大,且插入、删除运算效率高。(×)

12、数据结构的基本操作的设置的最重要的准则就是,实现应用程序与存储结构的独立。()

13、数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。 (×)

14、判断一个算法的好坏主要以下几个标准:正确性、有穷性、健壮性与可

行性。(×)

15.算法的时间复杂度T(n)=O(f(n))表示随问题规模n的增大,算法执行时

间的增长率与函数f(n)的增长率相同。()

四、综合题

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;

｝

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)