数据结构课后练习题汇编

数据结构课后练习题第一章绪论一、选择题1、数据结构被形式定义为（D，S），其中D是（）的有限集合，S是D上的（）有限集合。A、算法B、数据元素C、数据操作D、逻辑关系E、操作F、映象G、存储H、关系2、数据结构是一门研究非数值计算的程序设计问题中计算机的（（1））以及它们之间的（②）和运算的学科。（1）A、操作对象B、计算方法C、逻辑存储D、数据映象（2）A、结构B、关系C、运算D、算法3、算法分析的目的是（），算法分析的二个主要方面是（）。A、给出数据结构的合理性B、研究算法中输入输出的关系C、空间复杂性和时间复杂性D、分析算法的效率以求改进E、正确性和简明性F、分析算法的易懂性和文档性4、在数据结构中，从逻辑上可以把数据结构分成（）。A、动态和静态结构B、紧凑接和非紧凑结构C、线性与非线性结构D、内部结构和外部结构5、计算机算法指的是（），它必具备输入、输出和（）5个特性。A、计算方法B、排序方法C、解决问题的有限运算序列D、可行性、可移植性和可扩充性E、可行性、确定性和有穷性6、线性表的顺序存储结构是一种（）的存储结构，线性表的链式存储结构是一种（）A、随机存取B、顺序存取C、索引存取D、散列存取7、算法的时间复杂度取决于（）A、问题的规模B、待处理数据的初态C、问题的规模和待处理数据的初态8、线性表若采用链表存储结构时，要求内存中可用存储单元的地址（）A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续不连续都可以9、在以下的叙述中，正确的是（）A、线性表的线性存储结构优于链式存储结构B、二维数组是它的每个数据元素为一个线性表的线性表C、栈的操作方式是先进先出D、队列的操作方式是先进后出10、根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式。以下解释错误的是()A、集合中任何两个结点之间都有逻辑关系但组织形式松散B、线性结构中结点按逻辑关系依次排列形成一条锁链C、树形结构具有分支、层次特性，其形态有点像自然界中的树D、图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接11、以下说法正确的是()A、数据元素是数据的最小单位B、数据项是数据的基本单位C、数据结构是带有结构的各数据项的集合D、数据结构是带有结构的数据元素的集合二、填空题1、数据逻辑结构包括（）四种类型，树型和图型结构合称（）。2、对于给定的n个元素，可以构造出的逻辑结构有（）、（）、（）和（）四种。3、算法的五个重要特性是（）。4、评价算法的性能从利用计算机资源角度看主要从（）方面进行分析。5、线性结构中元素之间存在（）关系，树型结构中元素之间存在（）关系，图型结构中元素之间存在（）关系。6、下面程序段的时间复杂度是（）。i=s=0;while(sn){i++;s++;}7、下面程序段的时间复杂度是（）。s=0;for(I=0;In;I++)for(j=0;jm;j++)s+=a[i][j];8、所谓数据的逻辑结构指的是数据元素之间的_______。9、数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容________。10、在线性结构中，开始结点_____前驱结点，其余每个结点有且只有____个结点。11、在树形结构中，根结点只有______，根结点无前驱，其余每个结点有且只有______前驱结点；叶子结点没有______结点，其余每个结点的后继结点可以_____。12、在图形结构中，每个结点的前驱结点和后继结点可以有_______。13、存储结构是逻辑结构的__________实现。14、从数据结构的观点看，通常所说的数据应分成三个不同的层次，即__________、__________和__________。15、根据需要，数据元素又被称为__________、__________、__________或__________。16、通常，存储结点之间可以有__________、__________、__________、________四种关联方式，称为四种基本存储方式。17、通常从___________、___________、___________、___________等几方面评价算法的(包括程序)的质量。18、一个算法的时空性能是指该算法的________________和________________，前者是算法包含的___________，后者是算法需要的___________。19、在一般情况下，一个算法的时间复杂性是___________的函数。20、常见时间复杂性的量级有：常数阶O(___________)、对数阶O(___________)、线性阶O(___________)、平方阶O(___________)、和指数阶O(___________)。通常认为，具有指数阶量级的算法是___________的。21、数据结构的基本任务是数据结构的___________和___________。22、数据对象是性质相同的的集合。23、抽象数据类型是指一个以及定义在该模型上的一组操作。三、判断题1.数据元素是数据的最小单位。2.数据结构是带有结构的数据元素的集合。3.数据结构，数据元素，数据项在计算机中的映象分别称为存储结构，结点，数据域。4.数据项是数据的基本单位。5.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。6.数据的物理结构是数据在计算机中实际的存储形式。7.算法和程序没有区别，所以在数据结构中二者是通用的。8.顺序存储结构属于静态结构，链式存储结构属于动态结构。四、计算应用题1、设n为正正数。确定下列各程序段中前置以记号@的语句的频度。（1）I=1;k=0;While(In-1)@{k+=10*I;I++;}k=0;for(I=1;I=n;I++){for(j=I;j=n;j++)@k++;}(2)I=1;j=0;While(I+j=n)@{if(Ij)j++;elseI++;}2、写出下面算法中带标号语句的频度。Voidperm(inta[],k,n){intx,I;(1)if(k==n)(2)for(I=1;I=n;I++)(3)printf(“%d”,a[I]);else{(4)for(I=k;I=n;I++)(5)a[I]+=I*I;(6)perm(a,k+1,n);}}执行函数调用语句perm(a,1,n)3、指出下列两个算法的时间复杂度。（1）intsum1(intn){intp=1,sum=0,I;for(I=1;I=n;I++){p*=I;sum+=p;}return(sum);}(2)intsum2(intn){intsum=0,I,j;for(I=1;I=n;I++){p=1;for(j=1;j=I;j++)p*=j;sum+=p;}returm(sum);}4、有下列几种用二元组表示的数据结构，画出它们对应的逻辑图形表示，并指出它们属于哪种结构。（1）A=（K，R），其中：K={a,b,c,d,e,f,g,h}R=(r)r={a,b,b,c,c,d,d,e,e,f,f,g,g,h}(2)B=(K,R),其中：K={a,b,c,d,e,f,g,h}R=(r)r={d,b,d,g,d,a,b,c,g,e,g,h,e,f}(3)C=(K,R),其中：k={1,2,3,4,5,6}R={r}r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}(4)D=(K.R),K={48,25,64,57,82,36,75},R={r1,r2}r1={25,36,36,48,48,57,57,64,64,75,75,82}r2={48,25,48,64,64,57,64,82,25,36,84,75}5、设有如图所示的逻辑结构图，给出它的逻辑结构。6、简述下列术语：数据，数据元素，数据结构，数据对象。7、逻辑结构与存储结构是什么关系?8、将数量级102，n，n2，n3，nlog2n，log2n，2n，n，n!，n32，32n，按增长率进行排列。五、算法设计题1.已知输入x,y,z三个不相等的整数，设计一个算法，使得这三个数按从大到小输出，并考虑所用算法的比较次数和元素移动次数。2.编写在输入10个数中找出最小或最大的数的算法。3.在数组A[n]中查找值为k的元素,若找到则输出其位置i(1≤i≤n),否则输出0作为标志。设计求解此问题的类C语言算法，并分析其最坏情况时间复杂度。第二章线性表练习题一、选择题1、表长为N的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（），删除一个元素需要移动的元素个数为（）。A.(N-1)/2B.NC.N+1D.N-1E.N/2F.(N+1)/2G.(N-2)/22、线性表是具有N个（）的有限序列。A、表元素B、字符C、数据元素D、数据项E、信息3、“线性表的逻辑顺序和物理顺序总是一致的。”这个结论是（）。A、正确的B、错误的C、不一定，与具体结构有关。4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（）。A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以。5、带头结点的单链表为空的判定条件是（）。A、head==NULLB、head-next==NULLC、head-next==headD、head!=NULL6、不带头结点的单链表head为空的判定条件是（）。A、head==NULLB、head-next==NULLC、head-next==headD、head!=NULL7、非空的循环单链表head的尾结点P满足（）。A、P-NEXT=NULLB、p=NULLC、p-next==headD、p==head8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。A、O(1)B、O(n)C、O(n2)D、O(nlog2n)9、在一个单链表中，若删除P所指结点的后继结点，则执行（）。Ａ、p-next=p-next-nextＢ、p=p-next;p-next=p-next-nextＣ、p-next=p-next;Ｄ、p=p-next-next;10、在一个单链表中，若在Ｐ所指结点之后插入Ｓ所指结点，则执行（）。Ａ、s-next=p;p-next=s;Ｂ、s-next=p-next;p-next=s;Ｃ、s-next=p-next;p=s;Ｄ、p-next=s;s-next=p;11、在一个单链表中，已知q是p的前趋结点，若q和p之间插入结点s，则执行（）。Ａ、s-next=p-next;p-next=s;Ｂ、p-next=s-next;s-next=p;Ｃ、q-next=s;s-next=p;Ｄ、p-next=s;s-next=q;12、假设双链表结点的类型如下：typedefstructlinknode{intdata;／／数据域structlinknode*llink;／／指向前趋结点的指针域structlinknode*rlink;／／指向后继结点的指针域}bnode现将一个q所指新结点作为非空双向链表中的p所指结点的前趋结点插入到该双链表中，能正确完成此要求的语句段是（）。Ａ、q-rlink=p;q-llink=p-llink;p-llink=q;p-llink-rlink=q;Ｂ、p-llink=q;q-rlink=p;p-llink-rlink=q;q-llink=p-llinkＣ、q-llink=p-rlink;q-rlink=p;p-llink-rlink=q;p-llink=q;Ｄ、以上都不对１３、如上题结点结构，如在此非空循环双向链表的结点p之后插入结点s的操作序列