数据结构各章复习题

1第一章概述一、选择题1．以下哪种数据结构中任何两个结点之间都没有逻辑关系（）。A．树形结构B．集合C．图形结构D．线性结构2．要求同一逻辑结构的所有数据元素具有相同的性质，这意味着（）。A．数据元素具有同一的特点B．不仅数据元素包含的数据项的个数相同，而且对应数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等3．以下说法正确的是（）。A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构(或称关系)的数据项的集合D．数据结构是带有结构(或称关系)的数据元素的集合4．下面的叙述不是算法的特性的是（）。A．有穷性B．输入性C．可行性D．可读性5．下面的叙述中（）不是设计一个好的算法应达到的目标。A．健壮性B．可读性C．高存储量D．正确性6．下面运算中（）不是数据结构所具备的基本运算。A．插入B．排序C．退出D．删除7．数据结构是一门研究非数值计算的程序设计问题中计算机的（1）以及它们之间的（2）和运算等的学科。（1）A．数据元素B．计算方法C．逻辑存储D．数据映像（2）A．结构B．关系C．运算D．算法8．数据结构被形式地定义为（K，R），其中K是（1）的有限集，R是K上的（2）的有限集。（1）A．算法B．数据元素C．数据操作D．逻辑结构（2）A．操作B．映像C．存储D．关系9．在数据结构中，从逻辑上可以把数据结构分成（）。A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构10．数据结构在计算机内存中的表示是指（）。A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系11．在数据结构中，与所使用的计算机无关的是数据的（）结构。A．逻辑B．存储C．逻辑和存储D．物理12．算法分析的目的是（1），算法分析的两个主要方面是（2）。（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进D．分析算法的易懂性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性13．计算机算法指的是（1），它必须具备输入、输出和（2）等5个特性。（1）A．计算方法B．排序方法C．解决问题的有限运算序列D．调度方法（2）A．可行性、可移植性和可扩充性B．可行性、确定性和有穷性C．确定性、有穷性和稳定性D．易读性、稳定性和安全性14．在以下的叙述中，正确的是（）。A．线性表的线性存储结构优于链式存储结构B．二维数组是其数据元素为线性表的线性表C．栈的操作方式是先进先出D．队列的操作方式是先进后出15．在决定选取何种存储结构时，一般不考虑（）。A．各结点的值如何B．结点个数的多少2C．对数据有哪些运算D．所用编程语言实现这种结构是否方便16．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（）。A．数据的处理方法B．数据元素的类型C．数据元素之间的关系D．数据的存储方法17．下面说法错误的是（）。（1）算法原地工作的含义是指不需要任何额外的辅助空间。（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法。（3）所谓时间复杂度是指最坏情况下，估计算法执行的一个上界。（4）同一个算法，实现语句的级别越高，执行效率越低。A．（1）B．（1）（2）C．（1）（4）D．（3）二、填空题1．一种数据结构在计算机内存中的（）称为存储结构。2．数据的逻辑结构包括（）（）和（）三种结构，树形结构和图形结构合称为（非线性结构）。3．在线性结构中，第一个结点（）前驱结点，其余每个结点有且只有（）个前驱结点；最后一个结点（）后继结点，其余每个结点有且只有（）个后继结点。4．在树形结构中，根结点没有（）结点，其余每个结点有且只有（）个前驱结点，叶子结点没有（）结点，其余每个结点的后继结点可以（）。5．在图形结构中，每个结点的前驱结点数和后继结点数可以（）。6．线性结构中元素之间存在（）关系，树形结构中元素之间存在（）关系，图形结构中元素之间存在（）关系。7．算法的5个重要特性是（）、（）、（）输入和输出。8．算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实现上就是程序了。这种说法是（）的。9．算法效率分析可分为（）分析和（）分析。10．数据结构的存储方式有（）、（）、（）和（）4种。11．数据结构包括（）、（）、（）三个组成部分。12．数据对象是性质相同的（）的集合。三、判断题1．顺序存储方式只能用于存储线性结构。（）2．数据元素是数据的最小单位。（）3．数据结构、数据元素、数据项在计算机中的映像（或表示）分别称为存储结构、结点、数据域。（）4．数据的物理结构是指数据在计算机内实际的存储形式。（）5．数据的逻辑结构是对数据元素之间关系的描述，它与数据元素的存储形式无关。（）四、问答题1．指出下列程序段的时间复杂度（1）i=1(2)i=nwhile(i=n)while(i=0&&a[i]!=k)i=i*3;i--;(3)for(i=0;im;i++)(4)fact(n)for(j=0;jn;j++){if(n=1)a[i][j]=i*j;return(1);elsereturn(n*fact(n-1));}2．画出下列二元组表示的数据结构对应的逻辑图形，并指出分别属于何种结构。（1）B=（K，R）3K={a,b,c,d,e,f,g,h}R={d,b,d,g,d,a,b,c,g,e,g,h,e,f}(2)C=(K,R)K={1,2,3,4,5,6}R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}第二章线性表一、选择题1．链表不具备的特点是（）。A．可随机访问任一结点B．插入删除不需要移动元素C．不必事先估计存储空间D．所需空间与其长度成正比2．不带头结点的单链表head为空的判定条件是（）。A．head==NULLB．head-next==NULLC．head-next==headD．head!=NULL3．带头结点的单链表head为空的判定条件是()。A．head==NULLB．head-next==NULLC．head-next==headD．head!=NULL4．带头结点的双循环链表L为空表的条件是（）。A．L==NULLB．L-next==NULLC．L-prior==NULLD．L-next==L5．非空的循环单链表head的尾结点（由P所指向）满足（）。A．p-next==NULLB．p==NULLC．p-next==headD．p==head6.在循环双链表的p所指结点之前插入s所指结点的操作是（）。A．p-prior=s；s-next=p；p-prior-next=s；s-prior=p-prior；B．p-prior=s；p-prior-next=s；s-next=p；s-prior=p-prior；C．s-next=p；s-prior=p-prior；p-prior=s；p-right-next=s；D．s-next=p；s-prior=p-prior；p-prior-next=s；p-prior=s；7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（）存储方式最节省运算时间。A．单链表B．给出表头指针的单循环链表C．双链表D．带头结点的双循环链表8．某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用（）存储方式最节省运算时间。A．单链表B．仅有头结点的单循环链表C．双链表D．仅有尾指针的单循环链表9．如果最常用的操作是取第i个结点及其前驱，则采用（）存储方式最节省时间。A．单链表B．双链表C．单循环链表D．顺序表10．在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（）。A．O(1)B．O(n)C．O(n2)D．O(nlog2n)11．在一个长度为n(n1)的单链表上，设有头和尾两个指针，执行（）操作与链表的长度有关。A．删除单链表中的第一个元素B．删除单链表中的最后一个元素C．在单链表第一个元素前插入一个新元素D．在单链表最后一个元素后插入一个新元素12．设线性表有n个元素，以下算法中，（）在顺序表上实现比在链表上实现效率更高。A．输出第i(0≤i≤n-1)个元素值B．交换第0个元素与第1个元素的值C．顺序输出这n个元素的值D．输出与给定值x相等的元素在线性表中的序号13．设线性表中有2n个元素，算法（），在单链表上实现比在顺序表上实现效率更高。A．删除所有值为x的元素B．在最后一个元素的后面插入一个新元素C．顺序输出前k个元素D．交换第i个元素和第2n-i-1个元素的值(i=0，1，..，n-1)14．与单链表相比，双链表的优点之一是（）。A．插入、删除操作更简单B．可以进行随机访问C．可以省略表头指针或表尾指针D．顺序访问相邻结点更灵活15．如果对线性表的运算只有4种，即删除第一个元素，删除最后一个元素，在第一个元素前面插入新元4素，在最后一个元素的后面插入新元素，则最好使用（）。A．只有表尾指针没有表头指针的循环单链表B．只有表尾指针没有表头指针的非循环双链表C．只有表头指针没有表尾指针的循环双链表D．既有表头指针也有表尾指针的循环单链表16．如果对线性表的运算只有2种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用（）。A．只有表头指针没有表尾指针的循环单链表B．只有表尾指针没有表头指针的循环单链表C．非循环双链表D．循环双链表17．设有两个长度为n的单链表，结点类型相同，若以h1为表头指针的链表是非循环的，以h2为表头指针的链表是循环的，则（）。A．对于两个链表来说，删除第一个结点的操作，其时间复杂度都是O(1)B．对于两个链表来说，删除最后一个结点的操作，其时间复杂度都是O(n)C．循环链表要比非循环链表占用更多的内存空间D．h1和h2是不同类型的变量18．在长度为n的（）上，删除第一个元素，其算法的时间复杂度为O(n)。A．只有表头指针的不带表头结点的循环单链表B．只有表尾指针的不带表头结点的循环单链表C．只有表尾指针的带表头结点的循环单链表D．只有表头指针的带表头结点的循环单链表19．线性表是（）。A．一个有限序列，可以为空B．一个有限序列，不能为空C．一个无限序列，可以为空D．一个无限序列，不能为空20.设单链表中指针p指向结点M，指针f指向将要插入的新结点X：（1）当X插在链表中两个数据元素M和N之间时，只要先修改（）后修改（）即可。（2）当X插在链表中最后一个结点M之后时，只要先修改（）后修改（）即可。A．p-next=fB．p-next=p-next-nextC．p-next=f-nextD．f-next=p-nextE．f-next=NULLF．f-next=p21.在单循环链表中指针p指向结点A，若要删除A之后的结点，则指针的操作方式为（）。A．p-next=p-next-nextB．p=p-nextC．p=p-next-nextD．p-next=p22．给定有n个元素的向量，建立一个有序单链表的时间复杂度为（）。A．O（1）B．O（n）C．O(n2)D．O(nlog2n)23．线性表采用链式存储时，其地址（）。A．必须是连续的B．一定是不连续的C．部分地址必须是连续的D．连续与否均可以24．从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（）个元素。A．n/2B．nC．(n+1)/2D．(n-1)/2二、填空题1．在单链表中，要删除某一指定的结点，必须找到该结点的（）结点。2．访问单链表中的结点，必须沿着（）依次进行。3．在双链表中，每个结点都有两个指针域，一个指向（），另一个指向（）。4．在（）链表上，删除最后一个结点，其算法的时间复杂长为O