数据结构习题集(自编)第一章绪论一、选择题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与B6.一个算法应该就是( )。

A.程序B.问题求解步骤的描述C.要满足五个基本特性D.A与C、7、下面关于算法说法错误的就是( )A.算法最终必须由计算机程序实现B、为解决某问题的算法与为该问题编写的程序含义就是相同的C、算法的可行性就是指指令不能有二义性D、以上几个都就是错误的8.以下与数据的存储结构无关的术语就是( )。

A.循环队列 B、链表 C、哈希表D、栈9.在下面的程序段中,对x的赋值语句的频度为( )for(i=0;i<n;i++)for(j=0;j<n;j++)x=x+1;nA. 2nB.nC.n2D.log210.以下数据结构中,( )就是非线性数据结构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<t; 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);elseprintf(”％d is not a prime number、＼n”,n);｝1、该算法的时间复杂度为:O(m×n)。

2、该算法的时间复杂度为3、该算法的时间复杂度为:O(m×n×t)。

(n)。

4、该算法的时间复杂度为:log3。

5、该算法的时间复杂度为6.将下列函数,按它们在n→∝时的无穷大阶数,从小到大排序。

n, n-n3+7n5, nlogn, 2n/2, n3, logn, n1/2+logn, (3/2)n, ,n!, n2+logn 从小到大排列为:logn, n1/2+logn, n, nlogn, n2+logn,n3, n-n3+7n5, 2n/2, (3/2)n, n!,第二章线性表一、选择题1.在一个长度为n的顺序表中删除第i个元素(0<i<=n)时,需要向前移动( )个元素。

A.n-iB.n-i+1C.n-i-1D.i+12.从一个具有n个元素的线性表中查找其值等于x的结点时,在查找成功的情况下,需平均比较( )个元素结点。

A.n/2B.nC.(n-1)/2D.(n +1)/23.对一个具有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-iB.n-i＋1C.n－i－1D.i＋18.如果某链表中最常用的操作就是取第i个结点及其前驱,则采用( )存储方式最节省时间。

A.单链表B.双向链表C.单循环链表D.顺序表9.一个顺序存储线性表的第一个元素的存储地址就是90,每个元素的长度就是2,则第6个元素的存储地址就是()。

A.98B.100C.102D.10610.在顺序存储的线性表(a1……an)中,删除任意一个结点所需移动结点的平均移动次数为( )A.nB.n／2C.(n-1)/2D.(n＋l)/211.在线性表的下列存储结构中,读取第i个元素花费的时间最少的就是()。