数据结构复习题

1、1 绪论沈阳理工大学应用技术学院信息与控制学院计算机科学与技术教研室2011-5-8数据结构复习题：绪论单选题1、在数据结构中，与所使用的计算机无关的数据叫_结构。a存储|b物理|c逻辑|d物理和存储2、在数据结构中，从逻辑上可以把数据结构分成_。a动态结构和静态结构|b紧凑结构和非紧凑结构|c线性结构和非线性结构|d内部结构和外部结构图3、数据结构在计算机内存中的表示是指_。数据的存储结构|数据结构|数据的逻辑结构|数据元素之间的关系4、在数据结构中，与所使用的计算机无关的是数据的_结构。逻辑|存储|逻辑和存储|物理5、在以下的叙述中，正确的是_。线性表的线性存储结构优于链表存储结构|二维数

2、组是其数据元素为线性表的线性表|栈的操作方式是先进先出|队列的操作方式是先进后出6、在决定选取何种存储结构时，一般不考虑_。各结点的值如何|结束个数的多少|对数据有哪些运算|所用编程语言实现这种结构是否方便7、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储_。数据的处理方法|数据元素的类型|数据元素之间的关系|数据的存储方法8、下面说法错误的是_。(1)算法原地工作的含义是指不需要任何额外的辅助空间(2)在相同的规模n下，复杂度o(n)的算法在时间上总是优于复杂度o(2n)的算法(3)所谓时间复杂度是指最坏情况下，估计算法执行时间的一个上界(4)同一个算法，实现语句的级别越高，执行效

3、率越低(1)|(1)、(2)|(1)、(4)|(3)9、通常要求同一逻辑结构中的所有数据元素具有相同的特性。这意味着_。数据元素具有同一特点|不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致|每个数据元素都一样|数据元素所包含的数据项的个数要相等10、以下说法正确的是_。数据元素是数据的最小单位|数据项是数据的基本单位|数据结构是带结构的数据项的集合|一些表面上很不相同的数据可以有相同的逻辑结构11、_是数据的最小单元,_是数据的基本单位.数据项|数据元素|信息项|表元素12、数据结构是指_以及它们之间的_.(1)数据元素 (2)结构|(1)计算方法 (2)关系|(1)逻辑

4、存储 (2)运算|(1)数据映像 (2)算法13、计算机所处理的数据一般具备某种内在的关系,这是的指_.数据和数据之间存在的某种关系|元素和元素之间存在某种关系|元素内部具有某种结构|数据项和数据项之间存在某种关系14、数据的逻辑结构可以分为_两类.动态结构和表态结构|紧凑结构和非紧凑结构|线性结构和非线性结构|内部结构和外部结构15、数据的逻辑结构是指_关系的整体.数据元素之间逻辑|数据项之间逻辑|数据类型之间|存储结构之间16、在存储数据时,通常不仅要存储各数据元素的值,而且还要存储_.数据的处理方法|数据元素的类型|数据元素之间的关系|数据的存储方法17、在数据的存储结构中,一个存储结点

5、存储一个_.数据项|数据元素|数据结构|数据类型18、在计算机的存储器中表示时,物理地址和逻辑地址直接对应并且是连续的,称之为_.逻辑结构|顺序存储结构|链式存储结构|以上都对19、数据采用链式存储结构时,要求_.每个结点用占一片连续的存储区域|所有结点占用一片连续的存储区域|结点的最后一个数据域是指针类型|每个结点有多少个后继,就设多少个指针域20、数据的运算_.效率与采用何种存储结构有关|是根据存储结构来定义的|有算术运算和关系运算两大类|必须用程序设计语言来描述21、下列说法中,不正确的是_.数据元素是数据的基本单位|数据项是数据中不可分割的最小可标识单位|数据可由若干个数据元素构成|数

6、据项可由若干个数据元素构成22、_不是算法的基本特性.可行性|长度有限|在规定的时间内完成|确定性23、计算机中算法指的是解决某一问题的有限运算序列,它必须具备输入、输出、_.可行性、可移植性和可扩充性|可行性、有穷性和确定性|确定性、有穷性和稳定性|易读性、稳定性和确定性24、以下不属于算法特性的是_.可行性|有输入|确定性|健壮性25、下面关于算法的说法正确的是_.算法最终必须由程序实现|算法的有穷性是对于任意的一组输入值必须在有穷步骤后结束|算法的可行性是指指令不能有二义性|以上几个都是错误的26、算法的时间复杂度与_有关问题规模|计算机硬件性能|编译程序质量|程序设计语言27、算法分析

7、的主要任务是分析_.算法是否具有较好的可读性|算法中是否存在语法错误|算法的功能是否符合设计要求|算法的执行时间和问题规模之间的关系28、某算法的时间复杂度为o(n2),表明该算法的_.问题规模是n2|执行时间等于n2|执行时间与n2成正比|问题规模与n2成正比29、算法分析的目的是_.找出数据结构的合理性|研究算法中输入和输出关系|分析算法的效率以求改进|分析算法的易读性和文档性30、线性表是具有n个_的有限序列。表元素|字符|数据元素|数据项31、线性表是_。一个有限序列，可以为空|一个有限序列，不可以为空|一个无限序列，可以为空|一个无限序列，不可以为空32、线性表采用链表存储时，其地址

8、_。必须是连续的|一定是不连续的|部分地址必须是连续的|连续与否均可以33、链表不具备的特点是_。可随机访问任一结点|插入删除不需要移动元素|不必事先估计存储空间|所需空间与其长度成正比34、线性表的静态存储结构与顺序存储结构相比优点是_。所有的操作算法实现简单|便于随机存取|便于插入和删除|便于利用零散的存储器空间35、设线性表有n个元素，以下操作中，_在顺序表上实现比在链表上实现效率更高。输出第i(1=i=n)个元素值|交换第1个元素与第2个元素的值|顺序输出这n个元素的值|输出与给定值x相等的元素在线性表中的序号36、对于一个线性表，既要求能够较快地进行插入和删除，又要求存储结构能够反映

9、数据元素之间的逻辑关系，则应采用_存储结构。顺序|链式|散列|索引37、设线性表中有2n个元素，以下操作中，_在单链表上实现要比在顺序表上实现效率更高。删除指定的元素|在最后一个元素的后面插入一个新元素|顺序输出前k个元素|交换第i个元素和第2n-i-1个元素的值(i=0，1，n-1)38、需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是_。单链表|静态链表|线性链表|顺序存储结构39、如果最常用其所长的操作是取第i个结点及其前驱，则采用_结构方式最节省时间。单链表|双链表|单循环链表|顺序表40、与单链表相比，双链表的优点之一是_。插入、删除操作更简单|可以进行随机访问|可以

10、省略表头指针或表尾指针|访问前后相邻结点更灵活41、数据结构在计算机内存中的表示是指_.数据的存储结构|数据结构|数据的逻辑结构|数据元素之间的关系42、下面程序段的时间复杂度为_o(m)| o(n)|o(m*n)|o(m+n) for(int i=0;im;i+) for(int j=0;jn;j+) aij=i*j;数据结构复习题答案：绪论单选题1、存储|物理|逻辑|物理和存储 c1c 2c 3a 4a 5b 6a 7c 8a 9b 10d 11ab 12ab 13b 14c 2、动态结构和静态结构|紧凑结构和非紧凑结构|线性结构和非线性结构|内部结构和外部结构图 ? a c3、数据的存储

11、结构|数据结构|数据的逻辑结构|数据元素之间的关系 a4、逻辑|存储|逻辑和存储|物理 a5、线性表的线性存储结构优于链表存储结构|二维数组是其数据元素为线性表的线性表|栈的操作方式是先进先出|队列的操作方式是先进后出 b6、各结点的值如何|结束个数的多少|对数据有哪些运算|所用编程语言实现这种结构是否方便 a7、数据的处理方法|数据元素的类型|数据元素之间的关系|数据的存储方法 c8、(1)|(1)、(2)|(1)、(4)|(3) a9、数据元素具有同一特点|不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致|每个数据元素都一样|数据元素所包含的数据项的个数要相等 b10、

12、数据元素是数据的最小单位|数据项是数据的基本单位|数据结构是带结构的数据项的集合|一些表面上很不相同的数据可以有相同的逻辑结构 d11、数据项|数据元素|信息项|表元素 a|b12、(1)数据元素 (2)结构|(1)计算方法 (2)关系|(1)逻辑存储 (2)运算|(1)数据映像 (2)算法 a|b13、数据和数据之间存在的某种关系|元素和元素之间存在某种关系|元素内部具有某种结构|数据项和数据项之间存在某种关系 b14、动态结构和表态结构|紧凑结构和非紧凑结构|线性结构和非线性结构|内部结构和外部结构 c 15a 16c 17b 18b 19a 20a21d 22b 23b 24d 25b

13、26a 27d 28c 29c 30c 31a 32d 33a 34c 35a 36b 37a 38b 39b 40d 41a 42c15、数据元素之间逻辑|数据项之间逻辑|数据类型之间|存储结构之间 a16、数据的处理方法|数据元素的类型|数据元素之间的关系|数据的存储方法 c17、数据项|数据元素|数据结构|数据类型 b18、逻辑结构|顺序存储结构|链式存储结构|以上都对 b19、每个结点用占一片连续的存储区域|所有结点占用一片连续的存储区域|结点的最后一个数据域是指针类型|每个结点有多少个后继,就设多少个指针域 a20、效率与采用何种存储结构有关|是根据存储结构来定义的|有算术运算和关系

14、运算两大类|必须用程序设计语言来描述 a21、数据元素是数据的基本单位|数据项是数据中不可分割的最小可标识单位|数据可由若干个数据元素构成|数据项可由若干个数据元素构成 d22、可行性|长度有限|在规定的时间内完成|确定性 b23、可行性、可移植性和可扩充性|可行性、有穷性和确定性|确定性、有穷性和稳定性|易读性、稳定性和确定性 b24、可行性|有输入|确定性|健壮性 d25、算法最终必须由程序实现|算法的有穷性是对于任意的一组输入值必须在有穷步骤后结束|算法的可行性是指指令不能有二义性|以上几个都是错误的 b26、问题规模|计算机硬件性能|编译程序质量|程序设计语言 a27、算法是否具有较好

15、的可读性|算法中是否存在语法错误|算法的功能是否符合设计要求|算法的执行时间和问题规模之间的关系 d28、问题规模是n2|执行时间等于n2|执行时间与n2成正比|问题规模与n2成正比 c29、找出数据结构的合理性|研究算法中输入和输出关系|分析算法的效率以求改进|分析算法的易读性和文档性 c30、表元素|字符|数据元素|数据项 c31、一个有限序列，可以为空|一个有限序列，不可以为空|一个无限序列，可以为空|一个无限序列，不可以为空 a32、必须是连续的|一定是不连续的|部分地址必须是连续的|连续与否均可以 d33、可随机访问任一结点|插入删除不需要移动元素|不必事先估计存储空间|所需空间与其

16、长度成正比 a34、所有的操作算法实现简单|便于随机存取|便于插入和删除|便于利用零散的存储器空间c 35、输出第i(1=i=n)个元素值|交换第1个元素与第2个元素的值|顺序输出这n个元素的值|输出与给定值x相等的元素在线性表中的序号 a36、顺序|链式|散列|索引 b37、删除指定的元素|在最后一个元素的后面插入一个新元素|顺序输出前k个元素|交换第i个元素和第2n-i-1个元素的值(i=0，1，n-1) a38、单链表|静态链表|线性链表|顺序存储结构 b39、单链表|双链表|单循环链表|顺序表 d40、插入、删除操作更简单|可以进行随机访问|可以省略表头指针或表尾指针|访问前后相邻结点

17、更灵活 d41、数据的存储结构|数据结构|数据的逻辑结构|数据元素之间的关系 a42、o(m|o(m*n)|o(m+n) c数据结构复习题：绪论判断题1、数据元素是数据的最小单位。2、数据项是数据的基本单位。3、数据元素是数据的最小单位4、数据对象就是一组任意数据元素的集合5、任何数据结构都具备3个基本运算: 插入、删除和查找.6、数据是由一些类型相同的数据元素构成的7、数据是逻辑结构与各数据元素在计算机中如何存储有关8、如果数据元素值发生改变,则数据的逻辑结构也随之改变.9、逻辑结构相同的数据,可以采用多种不同的存储方法.10、逻辑结构相同的数据,结点类型也一定相同11、逻辑结构不相同的数据

18、,必须采用不同的存储方式来存储12、数据的逻辑结构是指数据的各数据项之间的逻辑关系.13、算法的优劣与算法描述语言有无关，但与所有计算机有关。14、算法可以用不同的语言描述，如果用c或pascal等高级语言来描述，则算法实际上就是程序了。15、程序一定是算法。16、算法最终必须由计算机程序实现。f19、健壮的算法不会因非法入输数据而出现莫名其妙的执行结果。数据结构复习题答案：绪论判断题1、false2、false3、false4、false5、false6、true7、false8、false9、true10、false11、false12、false13、false14、false15、fa

19、lse16、false19、true数据结构复习题：绪论算法分析题1、求两个n阶矩形的乘法c=a*b,其算法如下:#define max 100void maxtrixmult(int ,float amaxmax,bmaxmax,float cmaxmax) int i,j,k; float x; for(i=1;i=n;i+) / for (j=1;j=n;j+) / x=0; / for(k=1;k=n;k+) / x+=aik*bkj; / cij=x; / 计算各语句的频度,并分析该算法的时间复杂度。2、设n是偶数,试计算运行下列程序段后m的值并给出该程序段的时间复杂度。m=0;fo

20、r(i=1;i=n;i+) for(j=2*1;j=n;j+) m+; 3、阅读下列算法:void suan_fa(int n) int i,j,k,s,x; for (s=0,i=0;in;i+) for (j=i;jn;j+) s+; i=1;j=n;x=0; while (ij) i+; j-; x+=2; pirntf(s=%d,x=%d,s,x);(1) 分析算法中语句s+;的执行次数; (2) 分析算法中语句x+=2;的执行次数; (3) 分析该算法的时间复杂度; (4) 假定n=5, 试指出执行该算法的输出结果。6、设n是偶数,试计算运行下列程序段后m的值并给出该程序段的时间复杂

21、度。int m=0,i,j;for (i=1;i=n;i+) for (j=2*i;j=n;j+) m+; m=n*n/4 o()数据结构复习题答案：绪论算法分析题1、答： 语句 频度for(i=1;i=n;i+) / n+1 for (j=1;j=n;j+) / n(n+1)x=0; / n2for(k=1;k=n;k+) / n2(n+1)x+=aik*bkj; / n3cij=x; / n2所以：f(n)n+1+ n(n+1)+ n2+ n2(n+1)+ n3+ n2=2n3+4n2+2n+1=o( n3 )2、答：m+n(n-1) o(n2)3、分析算法中语句”s+;”的执行次数：n+

22、（n-1）+(n-2)+1=n(n+1)/2分析算法中语句”x+=2;”的执行次数: n/2分析该算法的时间复杂度: o(n2) 假定n=5，试指出执行该算法的输出结果: s=15, x=46、数据结构复习题：绪论填空题1、一个数据结构在计算机中_映像_称为存储结构。2、数据逻辑结构包括 、 和 三种类型，树形结构和图形结构合称为_。3、在线性结构中，第一个结点_前驱结点，其余每个结点有且只有_个前驱结点：最后一个结点_后续结点，其余每个结点有且只有_个后续结点。4、在树形结构中，树根结点没有_结点，其余每个结点有且只有_个前驱结点:叶子结点没有_结点,其余每个结点后的后续结点可以_5、在图形

23、结构中，每个结点的前驱结点数和后续结点数可以_任意多个_。6、线性结构中元素之间存在_一对一_关系，树形结构中元素之间存在_一对多_关系，图形结构中元素之间存在_多对多_关系。7、算法的5个重要特性是_、_、_、输入和输出。8、算法可以用不同的语言描述，如果用c语言或pascal语言等高级语言来描述，则算法实现上就是程序了。这个断言是_。9、数据结构、数据元素和数据项在计算机中的映射(或表示)分别称为存储结构、结点和数据域。这个断言是_。10、下面程序段的时间复杂度是_。 for (i=0;in;i+) for(j=0;jm;j+) aij=0;11、下面程序段的时间复杂度是_o(sqrt(n

24、)_。 i=s=0; while(sn) i+; s+=i; 12、下面程序段的时间复杂度是_。s=0;for (i=0;in;i+) for (j=0;jn;j+) s+=bij;sum=s;13、下面程序段的时间复杂度是_o(log3n)_。i=1;while(i=n) i=i*3;14、有如下递归函数fact(n),分析其时间复杂度。int fact(int n) if (n=1) return 1; else return (n*fact(n-1);15、指出下列各算法的时间复杂度(1) prime(int n) int i=2; while(n%i!=0 & isqrt(n) pri

25、ntf 是一素数; else printf 不是一素数; o(sqrt(n)(2) sum1(int n) int p=1,sum=0,i; for (i=1;i=n;i+) p*=i; sum+=p; returm (sum); (3) sum2(int n) int sum=0,i,j; for (i=1;i=n;i+) p=1; for (j=1;j=i;j+) p*=j; sum+=p; return (sum); 16、数据的逻辑结构是指_.17、一个数据结构在计算机中的_表示_称为存储结构.18、顺序存储方法是把逻辑上_相邻的结点_存储在物理位置上_相邻的存储单元_里;链式存储方法

26、中结点间的逻辑关系是由 附加的指针字段表示_的.19、数据结构是指研究数据的_存储结构_和_逻辑结构_以及它们之间的相互关系,并对这种结构定义相应的_运算_,设计出相应的_算法_,从而确保经过这些运算后所得到的新结构是原来的结构类型.20、一个算法具有5个特性:_、_、_、输入和输出。21、算法的执行时间是_的函数。22、数据的逻辑结构是从逻辑上描述数据,它与数据的_存储结构、物理结构_无关,是独立于计算机的.23、数据的逻辑结构被分为_、_、_和_种。24、数据的存储结构被分为_、_、_和_种。25、在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着_1:1_、_1：n_、_m:

27、n_的联系。26、一种抽象数据类型包括_数据_和_操作_两个部分。27、从一维数组an中顺序查找出一个最大值元素的时间复杂度为_，输出一个二维数组bmn中所有元素值的时间复杂度为_28、在下面程序段中，s=s+p语句的执行次数为_n_，p*=j语句的执行次数为_n*(n+1)/2_，该程序段的时间复杂度为_o(n*n)_。int i=0,s=0;while(+i=n) int p=1;for(int j=1;jlink=f即可。8、在双向链表存储结构中，删除p所指的结点时需修改指针_。9、在双向链表存储结构中，删除p所指的结点的前趋结点（若存在）时需修改指针_。10、根据线性表的链式存储结构，

28、每个结点所含指针的个数，链表分为单链表和_。11、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上_。12、链表不具备的特点是_。13、不带头结点的单链表head为空的判定条件是_。14、带头结点的单链表的head为空的判定条件是_。15、带头结点的双循环表l为空表的条件是_l-next=l_。16、非空的循环单链表head的尾结点(由p所指向)满足_。17、在循环双链表的p所指结点之前插入s所指结点的操作是_。18、若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用_带头结点的双循环链表_存储方式最节省运算时间。19、某线性表最常用的操作是在最后一个结点之后插

29、入一个结点或删除第一个结点，故采用_仅有尾指针的单循环链表_存储方式最节省运算时间。20、需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是_。21、如果最常用的操作是取第i个结点及其前驱，则采用_顺序表_存储方式最节省时间。22、在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是_。23、在一个长度为n(n1)的单链表上，设有头和尾两个指针，执行_删除单链表中的最后一个元素_操作与链表的长度有关。24、设线性表有n个元素，以下算法中，_在顺序表上实现比在链表上实现效率更高。25、设线性表中有2n个元素，算法_删除所有值为x的元素_，在单链表上实现要比在顺

30、序表上实现效率更高。26、与单链表相比，双链表的优点之一是_。27、如果对线性表的运算只有4种，即删除第一个元素，删除最后一个元素，在第一个元素前面插入新元素，在最后一个元素的后面插入新元素，则最后使用_只有表头指针没有表尾指针的循环双链表_。28、如果对线性表的运算只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用_。29、设有两个长度为n的单链表，结点类型相同。若以h1为表头指针的链表是非循环的，以h2为表头指针的链表是循环的，则_。30、在长度为n的_上，删除第一个结点，其算法的时间复度为o(n)。31、将两个各有n个元素的有序顺序表归并成一个有序顺序表，其最少的比较

31、次数是_n_。32、带头结点的单链表l为空的判定条件是_。33、在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是_。34、在一个长度为n(n1)的带头结点的单链表h上，另设有尾指针r(指向尾结点)，执行_操作与链表的长度有关。35、在一个双链表中，在*p结点之后插入结点*q的操作是_。36、在一个双链表中，在*p结点之前插入*q结点的操作是_。37、在一个双链表达式，删除*p结点的操作是_。38、在一个双链表中，删除*p结点之后的一个结点的操作是_。39、非空的循环单链表l的尾结点(由p所指向)满足_。40、带头结点的双循环链表l为空表的条件是_。41、若某表最常用的

32、操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用_带头结点的循环双链表_存储方式最节省运算时间。42、如果对含有n(n1)个元素的线性表的运算只有4种:删除第一个元素；删除最后一个元素；在第一个元素前面插入新元素；在最后一个元素的后面插入新元素，则最好使用_只有头结点指针没有尾结点指针的循环双链表_。43、某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，则采用_仅有尾结点指针的单循环链表_存储方式最节省运算时间。44、设有两个长度为n的单链表，结点类型相同，若以h1为头结点的链表是非循环的，以h2为头结点指针的链表是循环的，则_。45、在长度驎n(n1)的_

33、只有首结点指针h的不带头结点的循环单链表_上，删除第一个元素，其算法的时间复杂度为o(n)。46、元素a、b、c、d依次进顺序栈后，栈顶元素是_，栈底元素是_。47、经过以下栈运算后，x的值是_。initstack(s);push(s,a);push(s,b);pop(s,x);gettop(s,x);48、经过以下的栈运算后，stackempty(s)的值是_。initstack(s);push(s,a);push(s,b);pop(s,x);pop(s,y)49、设一个栈的输入序列为a、b、c、d，则借助一个栈所得到的输出序列不可能是_。50、若线性表最常用的运算是存取第i个元素及其前驱的

34、值,则采用_存储方式节省时间.51、链表不具备的特点是_.52、在一个长度为n的顺序存储的线性表中，向第i个元素(1=i=n+1)位置插入一个新元素时，需要从后向前依次后移_个元素53、在一个长度为n的顺序存储的线性表中，删除第i个元素(1=inext=p-next; p-next=s;|p-next=s-next; s-next=p;|q-next=s; s-next=p;|p-next=s; s-next=q; c4、一个有限序列，可以为空。|一个有限序列，不能为空。|一个无限序列，可以为空。|一个无限序列，不能为空。 a5、n+1|n-1|(n-1)/2|n c6、必须是连续的。|部分地址必须是连续的。|一定是不连续的。|连续与否均可以。d7、f-link=p;|f-link=p-link;|p-link=f-link;|f=nil; b8、(p-rlink) -rlink) -link=p;p-rlink=(p-rlink) -rlink;|(p-llink) -rlink=p-rlink;(p-rlink) -llink=p-llink;|p-llink=(p-llink) -