线性表专题一、选择题1．关于顺序存储的叙述中,哪一条是不正确的( )A.存储密度大B.逻辑上相邻的结点物理上不必邻接C.可以通过计算直接确定第i个结点的位置D.插入、删除操作不方便2．长度为n的单链表连接在长度为m的单链表后的算法的时间复杂度为( )A O(n)B O(1)C O(m)D O(m+n)3．在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．一个向量第一个元素的存储地址是100 ，每个元素的长度为2 ，则第5 个元素的地址是：( )（A ）110 （ B ）108 （C ）100 （D ）1205．已知一个顺序存储的线性表，设每个结点需要占m个存储单元，若第一个结点的地址为da，则第i个结点的地址为：( )A）da+(i-1)*m B) da+i*m C) da-i*m D) da+(i+1)*m6．在具有n个结点的单链表中，实现（）的操作，其算法的时间复杂度为O(n)。

A）遍历链表和求链表的第i个结点B）在地址为p的结点之后插入一个结点C）删除开始结点D）删除地址为p的结点的后继结点7．链表是一种采用（）存储结构存储的线性表。

（ A ）顺序（B ）链式（ C ）星式（D ）网状8．线性表若采用链式存储结构时，要求内存中可用存储单元的地址：（）（ A ）必须是连续的（ B ）部分地址必须是连续的（ C ）一定是不连续的（ D ）连续或不连续都可以9．线性表Ｌ在（）情况下适用于使用链式结构实现。

（Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入（Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂10．在长度为n 的顺序表的第i (1≤i≤n+1) 个位置上插入一个元素，元素的移动次数为( )A.n-i+1B.n-iC.iD.i-111．线性表是（）。

a、一个有限系列，可以为空b、一个有限系列，不能为空c、一个无限系列，可以为空d、一个无限系列，不能为空12. （）线性表。

A.(孔子,诸葛亮,曹雪芹)B.{A,B,C,D}C.{10,11,12,13,14}D.(1,2,3,...)13. （）是表示线性数据结构的。

A.循环链表B.邻接多重表C.孩子链表D.单链表14. 将线性表的数据元素以（）结构存放, 查找一个数据元素所需时间不依赖于表长。

A.循环双链表B.哈希(Hash)表C.一维数组D.单链表15. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（B）。

（A）s->link=p;p->link=s;（B）s->link=p->link;p->link=s;（C）s->link=p->link;p=s;（D）p->link=s;s->link=p;16. 在循环链表中first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是( )。

（A）current->link=NULL (B)first->link=current（C）first=current (D)current->link=first17. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较( )个结点。

A. nB. n/2C.（n-1）/2D. (n+1)/218. 在一个具有n个结点的有序单链表中，插入一新结点并仍然有序的时间复杂度为( )。

A. O(1)B. O(n)C. O(n2)D. O(nlog2n)19. 用链表表示线性表的优点是( )。

A. 便于随机存取B. 花费的存储空间比顺序表少C. 便于插入与删除D. 数据元素的物理顺序与逻辑顺序相同20. 当需要随机查找线性表的元素时,宜采用( )作存储结构。

A. 双向链表B. 循环链表C. 顺序表D. 单链表21. 线性表的链接实现有利于（）运算。

A、插入b、读表元c、查找d、定位22. 线性表采用链式存储时，其地址（）。

A 必须是连续的B 部分地址是连续的C 一定是不连续的D 连续与否均可以23. 设单链表中指针p指着结点a，若要删除a之后的结点（若存在），则需要修改指针的操作为（）。

A、p->next=p->next->next b、p=p->nextC、p= p->next->next d、p->next=p24. 向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动（）个元素。

A、8B、63.5C、63D、725. 向一个有127 个元素的顺序表中删除一个元素，平均要移动（）个元素（A）8 （B）63.5 （C）63（D）726. 用链表表示线性表的优点是（）A 便于插入和删除操作B 数据元素的物理顺序与逻辑顺序相同C 花费的存储空间较顺序存储少D 便于随即存取27. 以下数据结构中不属于线性数据结构的是（）A 队列B 线性表C 二叉树D 栈28．对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为（）。

A．N+1 B．N C．(N+1)/2 D．N/229．下列叙述中正确的是( )。

A. 线性表是线性结构B. 栈与队列是非线性结构C. 线性链表是非线性结构D. 二叉树是线性结构30．在单链表中，增加头结点的目的是( )。

A. 方便运算的实现B. 使单链表至少有一个结点C. 标识表结点中首结点的位置D. 说明单链表是线性表的链式存储实现31．线性表的顺序存储结构和线性表的链式存储结构分别是（）。

A.顺序存取的存储结构、顺序存取的存储结构B.随机存取的存储结构、顺序存取的存储结构C.随机存取的存储结构、随机存取的存储结构D.任意存取的存储结构、任意存取的存储结构33．线性表中正确的说法是( )。

A. 每个元素都有一个直接前驱和一个直接后继B. 线性表至少要求一个元素C. 表中的元素必须按由小到大或由大到小排序D. 除了第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继34．线性表是具有n个（）的有限序列。

A. 表元素B. 字符C. 数据元素D. 数据项35．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）。

（1≤i≤n+1）A. O(0)B. O(1)C. O(n)D. O(n2)36．在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度（）。

A. O(1)B. O(n)C. O(nlogn)D. O(n2)37．某线性表最常用的运算是插入和删除，插入运算是指在表尾插入一个新元素，删除运算是指删除表头第一个元素，那么采用（）存储方式最节省运算时间。

A. 仅有尾指针的单向循环链表B. 仅有头指针的单向循环链表C. 单向链表D. 双向链表二、填空题1．在单项链表中删除一个指定结点的后继的时间复杂度为2．线性表中______ ___________________ 称为表的长度。

3. 在n 个结点的单链表中，在P 指向的结点之后插入一个结点的时间复杂度为。

4．设长度为n的线性表顺序存贮,若在它的第i-1和第i个元素之间插入一个元素, 共需移动个元素(1<i≤n)。

5．在顺序表中访问任意结点的时间复杂度为，因此顺序表也称为存储的数据结构。

6．在单链表中要在已知结点*p之前插入一新结点，需找到，其时间复杂度为，而在双链表中，完成同样操作的时间复杂度为。

7．循环链表的主要优点是。

8．在一个单链表中删除p所指结点的下一个结点时，应执行以下操作：q=p->link;p->link=_ __ __Delete q9．将适当的语句添入单链表搜索函数find中。

template<class Type>ListNode<Type>*List<Type>::find(Type value) { current=first->link；while(current!=NULL)if(current->data=value) breakelse current=current->link;return}10．顺序存储方法是把逻辑上相邻的结点存储在物理位置的存储单元中。

11．顺序存储结构使线性表中逻辑上相邻的数据元素在物理上也相邻。

因此，这种表便于访问，是一种。

12．在一个不带头结点的单链表中，在表头插入或删除与其在其他位置插入或删除操作的过程。

13．在链表的结点中，数据元素所占存储量和整个结点所占的存储量之比称作存储密度。

14．已知L是无头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点，添加合适的语句。

1) P结点之后插入结点S：2)P结点之前插入结点S：3)在表首插入结点S：4) 在表尾插入结点S：15．已知P结点是某双向链表的中间结点，添加合适的语句。

1)P结点之后插入结点S：2)P结点之前插入结点S：3)删除P结点的直接后继结点：4)删除P结点的直接前驱结点：5)删除P结点：三、判断题1．线性链表中各个链结点之间的地址不一定要连续。

( )2．若频繁地对线性表进行插入和删除操作，该线性表采用顺序存储结构更合适。

( ) 3．若线性表采用顺序存储结构，每个数据元素占用4个存储单元，第12个数据元素的存储地址为144，则第1个数据元素的存储地址是101。

( )4．若长度为n的线性表采用顺序存储结构，删除表的第i个元素之前需要移动表中n-i+1个元素。

( )5．在顺序表中取出第i 个元素所花费的时间与i 成正比。

（）四、写出下列算法完成的功能1）ListNode *Demo1(LinkList L, ListNode *p)/*L是带有头结点的单链表*/{ ListNode *q = L->next;while(q && q->next !=p)q = q->next;if(q)return q;elseerror(“*p is not in L!”);}2) void Demo2(ListNode *p, ListNode *q){ DataType temp;temp = p->data;p->data = q->data;q->data = temp;}3) LinkList Demo3(LinkList L)/*L是无头结点的单链表*/{ ListNode *p, *q;if(L && L->next){ q=L;L=L->next;p=L;While(p->next) p=p->next;p->next = q;q->next = NULL;}return L;}4) LinkList *Connect(LinkList *L1, LinkList *L2)/* L1,L2是带有头结点的单链表*/{ LinkList *p;p=L1;while(p->next!=NULL) p=p->next;p->next = L2->next;return(L1);}。