数据库系统l试题库及答案-第2章-线性表

第2章线性表2.1知识点:线性表的逻辑结构一、填空题1.线性表是一个有限序列，结点间的关系是的。2.线性表的存储方式分为和。3.线性表中的数据元素可以是简单的数据类型，也可以由若干组成。4.每个操作在层次上尚不能用具体的某种程序语言写出具体的算法，而算法只有在确立之后才可以实现。二、选择题1.()线性表L=（a,a,…,a）,下列说法正确的是（）。A．每个元素都有一个直接前驱和一个直接后继。B．线性表中至少要有一个元素。C．表中诸元素的排列顺序必须是由小到大或由大到小。D．除第一个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继。2.()在线性表的下列运算中，不改变数据元素之间结构关系的运算是（）。A．插入B．删除C．排序D．定位3.()线性表是具有n个（）的有限序列（n=0）。A．表元素B．字符C．数据元素D．数据项E．信息项4.()以下不属于线性结构的是()。A．栈B.队列C.串D.二维数组E.二叉树三、判断题1.（）同一线性表的数据元素可以具有不同的特性。2.（）线性表的长度n就是表中数据元素的个数，当n=0时，称为空表。3.（）基本操作的实现可以在逻辑结构分析之后进行。2.2知识点：线性表的顺序存储结构一、填空题1.在线性表的顺序存储结构中，元素间的逻辑关系是通过决定的。2.在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与______________有关。3.向一个长度为n的顺序表的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动个元素。4.从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时，需向前移动个元素。5.在顺序表中访问任意一结点的时间复杂度均为，因此，顺序表也称为的数据结构。6.线性表的顺序存储是用一组连续的空间单元实现数据元素的存储，逻辑上相邻的元素的物理位置相邻。7.向一个长度为n的顺序表中任意位置插入一个元素所需移动的平均次数为。8.从一个长度为n的顺序表中删除任意一个元素所需移动的平均次数为。二、选择题1.()1.数据在计算机存储器内表示时，物理地址与逻辑地址相同并连续，称之为()。A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构2.()顺序表第一个元素的存储地址是100，每个元素长度为2，则第5个元素的地址是()。A.110B.108C.100D.1203.()在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是()。A.访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B.在第i个结点后插入一个新结点（1≤i≤n）C.删除第i个结点（1≤i≤n）D.将n个结点从小到大排序4.()若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱元素，则采用()存储方式最节省时间。A.单链表B.双链表C.单向循环D.顺序表5.()下述哪一条是顺序存储结构的优点（）。A．存储密度大B．插入运算方便C．删除运算方便D．按照序号定位6.()若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）（1=i=n+1）。A．O（0）B．O（1）C．O（n）D．O（n）三、判断题1.（）从长度为n的顺序表中删除任何一个元素，时间复杂度都是O(n)。2.（）顺序表中任意一个数据元素的地址都可以通过计算得到。3.（）存放顺序表的数据元素的地址空间可以连续也可以不连续。4.（）在顺序表中按值进行查找的时间复杂度是O(n)。5.（）顺序存储方式的特点是存储密度大且插入和删除运算效率高。四、简答题1．已知线性表的存储结构为顺序表，阅读下列算法，并回答问题：voidf30（SqList&L）{inti，j;for（i=j=0;iL.length;i++）if（L.elem[i]=0）{if（i!=j）L[j]=L.elem[i];j++；}L.length=j;}（1）设线性表L=（21，-7，-8，19，0，-11，34，30，-10），写出执行f30（&L）后的L状态；（2）简述算法f30的功能。四、算法设计题1.设计一个算法从一给定的有序顺序表L中删除元素值在x到y（x=y）之间的所有元素，要求以较高的效率来实现。要求算法的空间复杂度为O(1)。2.设有一个顺序表L，含有2n个整数，其中n个为负数，n个为正数，设计一个算法将L中所有元素按正负数相间排列。要求本算法的时间复杂度为O(n)，空间复杂度为O(1)。3.假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同一表中的元素值各不相同），要求分别设计求A和B交、并、差集的算法，要求结果线性表中的元素依值递增有序排列。试对顺表实现以上算法。4.假设一个顺序表L中所有元素为整数，设计一个算法调整该顺序表，使其中所有小于0的元素放在所有大于等于0的元素的前面。5.设顺序表A中前m个有序，后n个有序，试设计一算法使得整个顺序表有序。2.3知识点：线性表的链式存储结构一、填空题1.在链式存储中，元素之间的逻辑关系是通过___________决定的。2.在单链表中，除了首元结点外，任一结点的存储位置由指示。3.在n个结点的单链表中要删除已知结点*p，需找到它的，其时间复杂度为。4.在双链表中，每个结点有两个指针域，一个指向,另一个指向。5.在一个单链表中的p所指结点之后插入一个s所指结点时，执行的操作是。6.对于一个具有n个结点的单链表，在p结点后插入一个新结点的时间复杂度是；在给定值x的结点后插入一个新结点的时间复杂度是。7.头结点地址指针为L的循环单链表，空表的判别标志是。8.在一个单链表中删除p所指结点时，应执行以下操作：q=p-next;p-data=q-data;;free（p）;9.带头结点的单链表head为空的判定条件是。10.在一个单链表head中，已知p指向某个非终端节点，若要删除其后的一个结点则执行的运算是。二、选择题1.（）链表是一种采用（）存储结构存储的线性表。A.顺序B.链式C.星式D.网状2.（）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续或不连续都可以3.（）线性表Ｌ在（）情况下适用于使用链式结构实现。A.需经常修改Ｌ中的结点值B.需不断对Ｌ进行删除插入C.Ｌ中含有大量的结点D.Ｌ中结点结构复杂4.（）单链表的存储密度（）。A.大于1B.等于1C.小于1D.不能确定5.（）单链表不具备的特点是（）。A.可随机访问任一节点B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与其长度成正比6.（）设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是（）；r=s;r-next=null;。A.r-next=s;B.s-next=r;C.s-next=null;D.s=r;7.()在一个单链表中,q为p的前驱结点，要删除p所指结点时，应执行以下操作（）。A.q=p-next;B.p-next=q-next;C.p-next=q;D.q-next=p-next8.（）完成在双循环链表结点p之后插入s的操作是（）。A.p-next=s;s-prior:=p;p-next-prior:=s;s-next=p-next;B.p-next-prior=s;p-next=s;s-prior=p;s-next:=p-next;C.s-prior=p;s-next=p-next;p-next=s;p-next-prior=s;D.s-prior=p;s-next=p-next;p-next-prior=s;p-next=s;9.()某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用（）存储方式最节省运算时间。A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表10.()以下说法错误的是（）。A．求表长、定位两种运算在采用顺序存储结构时的时间复杂度为O(n)B．顺序存储的线性表可以随机存取C．由于顺序存储要求连续的存储区域,所以在存储管理上不够灵活D．线性表的链式存储结构优于顺序存储结构11.在一个双链表中，删除p结点（非尾结点）之后的一个结点的操作是（）。A．p-next=p-next-next;p-next-next-prior=p;B.p-next-prior=p;p-next=p-next-next;C.p-next=p-next-next;p-next-prior=p;D.p-next-next=p-next;p-next-prior=p;12.在带头结点的循环单链表中，至少有一个结点的条件是（）,其尾结点p的条件是()。A．L-next！=NULLB.L-next!=LC.p==NULLD.p-next=L三、判断题1.（）线性表的逻辑顺序与存储顺序总是一致的。2.（）在单链表中存取某个元素，只要知道指向该元素的指针，因此单链表是随即存取的存储结构。3.（）在顺序表中存取某个元素，需要按照顺序进行，因此顺序表是顺序存取的存储结构。4.（）单链表从任何一个结点出发，都能访问到所有结点。四、简答题1.描述以下三个概念的区别：头指针.头结点.首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？2.试比较线性表的两种存储结构的优缺点。在什么情况下用顺序表比链表好？五、算法设计题1．试写一算法，对单链表实现就地逆置。2．设计一个算法，求A和B两个单链表表示的集合的交集、并集和差集，单链表中的数据递增有序排列。要求分别按照共用原有空间和重新申请空间两种方案分别设计算法。3．已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意，mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。第2章线性表2.1知识点:线性表的逻辑结构一、填空题1.一对一2.顺序存储链式存储3.数据项_4.逻辑结构存储结构二、选择题1.D2.D3．C4.E三、判断题1.×2.√3.×2.2知识点：线性表的顺序存储结构一、填空题1.物理存储位置2.表中一半表长和该元素在表中的位置3.n-i+14.n-I5.O(1)随机存取6.地址必定7.（n+1）/28.n/2二、选择题1.C2.B3.A4.D5.AD6.C三、判断题1.×2.√3.×4.√5.×四、答题1．（1）（21，19，0，34，30）（2）功能是选出线性表中大于等于零的数。四、算法设计题1.voiddelete(SqList&L,ElemTypex,ElemTypey){inti=0,k=0;while(iL.length){if(L.elem[i]=x&&L.elem[i]=y)k++;//记录被删记录的个数elseL.elem[i-k]=L.elem[i];//前移k个位置i++;}L.length=L.length-k;}2.voidmove(SqList&L){inti=0,j=L.length-1;inttemp;while(ij)//使得正数都在前半部分，负数都在后半部分{while(ij&&L.elem[i]0)i++;while(ij&&L.elem[j]0)j--;if(ij)//交换L.elem[i](负数)和L.elem[j](正数){temp=L.elem[i];L.elem[i]=L.elem[j];L.elem[j]=temp;}}i=1;while(iL.length/2)//通过交换使得正负数相间{j=L.length-2;temp=L.elem[i];L.elem[i]=L.elem[j];L.elem[j]=temp;i=i+2;j=j-2;}}3.交集:voidinte