搜索
数据结构题集第一章绪论一、单选题1.在数据结构中，从逻辑上可以把数据结构分成【C】。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构2.数据结构在计算机内存中的表示是指【A】。A.数据的存储结构B.数据结构C.数据结构的逻辑结构D.数据元素之间的关系3.【A】是数据的最小单位，【B】是数据的基本单位。A.数据项B.数据元素C.信息项D.表元素4.计算机所处理数据一般具有某种内在联系，这是指【B】。A.数据与数据之间存在某种关系B.数据元素与数据元素之间存在某种关系C.元素内部存在某种结构D.数据项与数据项之间存在某种关系5.算法分析的目的是【C】。A.找出数据结构的合理性B.研究输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性6.在存储数据时，不仅要考虑存储各数据元素的值，而且还要存储【C】。A.数据处理的方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法7.算法分析的主要任务是分析【D】。A.算法是否具有较好的可读性B.算法中是否存储语法错误和逻辑错误C.算法的功能是否符合设计要求D.算法的执行时间与问题规模之间的关系。8.数据的运算【A】。A.效率与采用何种存储结构有关B.是根据存储结构来定义的C.有算术运算和关系运算两大类D.必须用程序设计语言来描述9.算法的计算量的大小称为算法的【B】。A.效率B.时间复杂度C.现实性D.难度10.连续存储分配时，存储单元的地址【A】。A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续二、判断题1.数据元素是数据结构的最小单位【.×】。2.数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构【×.】。3.数据的逻辑结构指数据元素的各数据项之间的逻辑关系【×.】。4.算法的优劣与算法的描述语言无关，但与使用的计算机有关【.×】。5.数据结构的抽象操作的定义与具体实现有关【.×】。三、填空题1.数据的逻辑结构指数据元素之间的逻辑关系。2.一个数据结构在计算机中的表示称为存储结构。3.数据的物理结构主要包括顺序存储结构的表示和链式存储结构的表示。4.数据逻辑结构包括集合、线性结构、树和图四种，树结构和图结构统称为非线性结构。5.顺序存储方法把逻辑上逻辑上相邻的元素存储在物理位置相邻的存储单元里；链式存储方法中结点间的逻辑关系是由指针域表示的。6、数据结构研究的是逻辑结构和物理结构以及它们之间的相互关系，并对于这种结构定义相应的运算，设计出相应的算法。7.算法的执行时间是问题规模n的函数。8.以下是4个算法所有语句频度之和的表达式，其中的复杂度相同的是A和B。A.TA(n)=2n3+3n2+1000B.TB(n)=n3-n2log2n-1000C.TC(n)=n2log2n+n2D.TD(n)=n2+1000四、解答题1.简述数据的逻辑结构和存储结构的关系。答：在数据结构中，逻辑结构和存储结构是密切相关的，存储结构不仅将数据元素存储到计算机中，而且还要表示各数据元素之间的逻辑关系。逻辑结构与计算机无关，存储结构是数据元素之间的关系在计算机中的表示。通常情况下，一种逻辑结构可以有多种存储结构，例如，线性结构可以采取顺序存储结构或链式存粗结构表示。2.数据结构和数据类型有什么区别？答：数据结构是相互间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容：数据的逻辑结构、存储结构和多数据的运算。数据类型是一个值得集合和定义在这个值集上的一组操作的总称。数据结构重点考虑元素之间的关系，数据类型重点考虑数据的个体特征。3.当为解决某一问题已经选定其数据的逻辑结构后，选择数据的存储结构时，应从哪些方面考虑？答：通常从两个方面考虑：第一是算法实现的存储空间复杂度；第二是算法执行的时间复杂度。若存储空间难以确定，宜选择链式存储结构，否则选择顺序存储结构。若插入、删除操作频繁，则选链式存储结构，否则选择顺序存储结构。第二章线性表一、单选题1.链表不具备的特点是【A】。A.可随机访问任一结点B.插入删除不需要移动元素C.不必事先估算存储空间D.所需空间与其长度成正比2.设线性表有n个元素，以下操作中，【A】在顺序表上实现比在链表上实现效率更高。A.输出第i（1≤i≤n）个元素的值B.顺序输出这n个元素C.交换第1个与第2个元素的值D.输出与给定值x相等的元素在线性表中的序号3.如果最常用的操作是取第i个结点及其前驱，则采用【D】存储方法最节省时间。A.单链表B.双链表C.线性链表D.顺序表4.线性表是具有n个【C】的有限序列（n≥0）。A.表元素B.字符C.数据元素D.数据项5.下面关于线性表的叙述中，错误的是【B】。A.线性表采用顺序存储，则必须占用一片连续的存储单元B.线性表采用顺序存储，则便于插入和删除操作C.线性表采用链式存储，则不必占用一片连续的存储单元D.线性表采用链式存储，则便于插入和删除操作6.线性表的顺序存储结构是一种【A】。A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构7.单链表中增加一个头结点的目的是为了【C】。A.使单链表至少有一个结点B.标识表首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储8.不带头结点的单链表（头指针为h）为空的条件是【A】。A.h==NULLB.h-next==NULLC.h-next==hD.h!=NULL9.带头结点的单链表（头指针为h）为空的条件是【B】。A.h==NULLB.h-next==NULLC.h-next==hD.h!=NULL10.带头结点的循环双向链表（头指针为L）为空的条件是【D】。A.L==NULLB.L-next-prior==NULLC.L-prior==NULLD.L-next==L11.非空的循环单链表（头指针为head）的尾结点（由p指向）满足【C】。A.p-next==NULLB.p==NULLC.p-next==headD.p==head12.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用【A】最节省时间。A.带头结点的双循环链表B.单循环链表C.带尾指针的单循环链表D.单链表13.若某线性表最常用的操作存取任意指定序号的元素和在表尾进行插入和删除，则选用【A】的存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表14.在n个结点的线性表的顺序实现中，算法的时间复杂度为O(1)的操作是【A】。A.访问第i个结点和求第i个结点的直接前驱B.在第i个结点后插入一个新结点C.删除第i个结点D.以上都不对15.若长度为n的线性表采用顺序存储结构，在第i个位置插入一个新元素的算法的时间复杂度为【C】。A.O(0)B.O(1)C.O(n)D.O(n2)16.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为【C】。A.O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)17.线性表以链式方式存储，访问第i个结点的时间复杂度为【C】。A.O(i)B.O(1)C.O(n)D.O(i-1)18.循环链表H尾结点p的特点是【A】。A.p-next==HB.p-next==H-nextC.p==HD.p==H-next二、判断题【×】1.取线性表的第i个元素的时间同i的大小有关。【×】2.线性表中每个元素都有一个直接前驱和一个直接后继。【×】3.顺序存储方式只能用于存储线性结构。【×】4.线性表采用链式存储时，结点和结点内部的存储空间可以不连续。【×】5.在一个设有头指针和尾指针的单链表中，执行删除单链表最后一个结点的操作与链表的长度无关。三、填空题1.向一个长度为n的顺序表中的第i个元素之前插入一个元素时，需要向后移动n-i+1个元素。2.在一个长度为n的顺序表中删除第i个元素时，需要向前移动n-i个元素。3.在单链表中设置头结点的作用是简化插入、删除算法。4.在单链中要删除某一指定结点，必须找到该结点的直接前驱结点。5.访问单链表中的结点，必须沿着指针域依次进行。6.在双链表中每个结点有两个指针域，一个指向直接前驱结点，一个指向直接后继结点。7.在双向循环链表中，删除最后一个结点的算法时间复杂度为O(1)。8.访问一个线性表中具有给定值的时间复杂度的数量级是O(n)。9.由n个数据元素生成一个顺序表，若每次都调用插入算法把一个元素插入到表头，则整个算法的时间复杂度为O(n)，若每次都调用插入算法把一个元素插入到表尾，则整个算法的时间复杂度为O(n2)。10.在双向链表中，可以用表尾指针代替表头指针。11.根据n个数据元素建立对应的顺序表和单链表存储结构，其算法的时间复杂度最好的情况是O(n)，最坏的情况是O(n2)。12.求线性表的顺序存储和链式存储的长度的算法时间复杂度分别是O(1)和O(n)。13.在一个带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？相同。14.在一个不带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？不相同。四、简答题1.阐述顺序表和链表存储方式的特点。答：顺序表存储方式为数据分配连续的存储单元，数据元素按逻辑顺序依次存储到相应存储单元中，使得逻辑相邻的数据元素物理也相邻，因此可以实现随机访问线性表的数据元素，即数据访问的时间复杂度为O(1)。链表存储方式分配的存储单元可以不连续，通过每个结点的指针域来表示数据元素之间的逻辑关系，只能顺序访问线性表中的数据元素。2.若频繁地对一个线性表进行插入和删除操作，则该线性表宜采用何种存储结构，为什么？答：若频繁地对一个线性表进行插入和删除操作，则该线性表宜采用链式存储结构。因为链式存储结构在插入和删除数据元素时不需要移动数据元素，只需要修改结点的指针域就可以改变数据元素之间的逻辑关系。3.在单链表、双向循环链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从相应的链表中删除？若可以，时间复杂度各为多少。答：要实现删除p结点的操作，必须找到其前驱结点，修改其指针域的值使其指向p的后继结点，以实现删除结点p。单链表不行，因为不知道头指针就无法找到结点p的前驱结点。双向循环链表和单循环链表可以可以实现删除p结点。单循环链表删除p结点的时间复杂度为O(n)，双循环链表删除P结点的时间复杂度为O(1)。4.对链表设置头结点的作用是什么？答：对带头结点的链表，在表的任何结点之前插入结点或删除任何位置的结点，所要做的都是修改前一个结点的指针域，因为在带头结点的链表中任何元素结点都有前驱结点。如果没有头结点，在首元结点前插入结点或删除首元结点都要修改头指针，其算法要比带头结点的算法复杂些。其次，带头结点的链表结构，初始化后的头指针就固定了，除撤销算法外，所有算法都不会修改头指针，可以减少出错的可能性。五、算法设计题1.已知一个线性表用含头结点的单链表做存储结构，写一个算法求单链表的长度。解：算法基本思想：从头结点的下一个结点开发，遍历单链表的每个结点，每遇到一个结点，结点计算器加1。intlistlenght(linklistL){intlength=0;P=L-next;while(p){length++;p=p-next;}return(length);}2.已知一个顺序表L，其中的元素按值递增有序排列，设计一个算法插入一个值为x的元素后保持该顺序表仍然递增有序，且空间复杂度为0（1）。voidinsertsq(sqlistL,elemtypex){n=L.length-1;while(n=0&<(x,L.elem[n]){L.elem[n+1]=L.elem[n];n--;}L.elem[n+1]=x;}L.lenght++;return;}3.写一个算法，从顺序表中删除值为x的所有元素。voiddelallsq(Sqlist&L){inti=0,j=0;while(jL.length){if(L.elem[j]!