第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;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分别表示两个集合（即同一表...
