数据结构第二章习题(1)

第二章线性表一、选择题1.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度（）。A.O(log2n)B.O(1)C.O(n)D.O(n2)2.若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。A.顺序表B.单链表C.双链表D.单循环链表3.具有线性结构的数据结构是（）。A.图B.树C.广义表D.栈4.在一个长度为n的顺序表中，在第i个元素之前插入一个新元素时，需向后移动（）个元素。A.n-iB.n-i+1C.n-i-1D.i5.非空的循环单链表head的尾结点p满足（）。A.p-next==headB.p-next==NULLC.p==NULLD.p==head6.链表不具有的特点是（）。A.可随机访问任一元素B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与线性表长度成正比7.在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改指针的操作是（）。A.p-next=q;q-prior=p;p-next-prior=q;q-next=q;B.p-next=q;p-next-prior=q;q-prior=p;q-next=p-next;C.q-prior=p;q-next=p-next;p-next-prior=q;p-next=q;D.q-next=p-next;q-prior=p;p-next=q;p-next=q;8.线性表采用链式存储时，结点的存储地址（）。A.必须是连续的B.必须是不连续的C.连续与否均可D.和头结点的存储地址相连续9.在一个长度为n的顺序表中删除第i个元素，需要向前移动（）个元素。A.n-iB.n-i+1C.n-i-1D.i+110.线性表是n个（）的有限序列。A.表元素B.字符C.数据元素D.数据项11.从表中任一结点出发，都能扫描整个表的是（）。A.单链表B.顺序表C.循环链表D.静态链表12.在具有n个结点的单链表上查找值为x的元素时，其时间复杂度为（）。A.O(n)B.O(1)C.O(n2)D.O(n-1)13.线性表L=(a1,a2,……,an)，下列说法正确的是（）。A.每个元素都有一个直接前驱和一个直接后继B.线性表中至少要有一个元素C.表中诸元素的排列顺序必须是由小到大或由大到小D.除第一个和最后一个元素外，其余每个元素都由一个且仅有一个直接前驱和直接后继14.一个顺序表的第一个元素的存储地址是90，每个元素的长度为2，则第6个元素的存储地址是（）。A.98B.100C.102D.10615.在线性表的下列存储结构中，读取元素花费的时间最少的是（）。A.单链表B.双链表C.循环链表D.顺序表16.在一个单链表中，若删除p所指向结点的后续结点，则执行（）。A.p-next=p-next-next;B.p=p-next;p-next=p-next-next;C.p=p-next;D.p=p-next-next;17.将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为（）。A.O(1)B.O(n)C.O(m)D.O(m+n)18.线性表的顺序存储结构是一种（）存储结构。A.随机存取B.顺序存取C.索引存取D.散列存取19.顺序表中，插入一个元素所需移动的元素平均数是（）。A.(n-1)/2B.nC.n+1D.(n+1)/220.循环链表的主要优点是（）。A.不再需要头指针B.已知某结点位置后能容易找到其直接前驱C.在进行插入、删除运算时能保证链表不断开D.在表中任一结点出发都能扫描整个链表21.不带头结点的单链表head为空的判定条件是（）。A.head==NULLB.head-next==NULLC.head-next==headD.head!=NULL22.在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（）。A.访问第i个元素的前驱（1ni）B.在第i个元素之后插入一个新元素(ni1)C.删除第i个元素(ni1)D.对顺序表中元素进行排序23.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（）。A.q-next=s-next；s-next=p；B.s-next=p；q-next=s-next；C.p-next=s-next；s-next=q；D.s-next=q；p-next=s-next；24.在以下的叙述中，正确的是（）。A.线性表的顺序存储结构优于链表存储结构B.线性表的顺序存储结构适用于频繁插入/删除数据元素的情况C.线性表的链表存储结构适用于频繁插入/删除数据元素的情况D.线性表的链表存储结构优于顺序存储结构25.在表长为n的顺序表中，当在任何位置删除一个元素的概率相同时，删除一个元素所需移动的平均个数为（）。A.(n-1)/2B.n/2C.(n+1)/2D.n26.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入一个结点s，则执行（）。A.s-next=p-next;p-next=s;B.p-next=s-next;s-next=p;C.q-next=s;s-next=p;D.p-next=s;s-next=q;27.在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是（）。A.p=p-next;B.p-next=p-next-next;C.p-next=p;D.p=p-next-next;28.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p-next-next==head，则（）。A.p指向头结点B.p指向尾结点C.p的直接后继是头结点D.p的直接后继是尾结点二、填空题1、设单链表的结点结构为（data,next）。已知指针p指向单链表中的结点，q指向新结点，欲将q插入到p结点之后，则需要执行的语句：；。2、线性表的逻辑结构是，其所含元素的个数称为线性表的。3、写出带头结点的双向循环链表L为空表的条件。4、带头结点的单链表head为空的条件是。5、在一个单链表中删除p所指结点的后继结点时，应执行以下操作：q=p-next;p-next=____;三、判断题1、单链表不是一种随机存储结构。2、在具有头结点的单链表中，头指针指向链表的第一个数据结点。3、用循环单链表表示的链队列中，可以不设队头指针，仅在队尾设置队尾指针。4、顺序存储方式只能用于存储线性结构。5、在线性表的顺序存储结构中，逻辑上相邻的两个元素但是在物理位置上不一定是相邻的。6、链式存储的线性表可以随机存取。四、程序分析填空题1、函数GetElem实现返回单链表的第i个元素，请在空格处将算法补充完整。intGetElem(LinkListL,inti,Elemtype*e){LinkListp；intj；p=L-next;j=1;while(p&&ji){(1);++j;}if(!p||ji)returnERROR;*e=(2);returnOK;}2、函数实现单链表的插入算法，请在空格处将算法补充完整。intListInsert(LinkListL,inti,ElemTypee){LNode*p,*s;intj;p=L;j=0;while((p!=NULL)&&(ji-1)){p=p-next;j++;}if(p==NULL||ji-1)returnERROR;s=(LNode*)malloc(sizeof(LNode));s-data=e;(1);(2);returnOK;}/*ListInsert*/3、函数ListDelete_sq实现顺序表删除算法，请在空格处将算法补充完整。intListDelete_sq(Sqlist*L,inti){intk;if(i1||iL-length)returnERROR;for(k=i-1;kL-length-1;k++)L-slist[k]=（1）;（2）;returnOK;}4、函数实现单链表的删除算法，请在空格处将算法补充完整。intListDelete(LinkListL,inti,ElemType*s){LNode*p,*q;intj;p=L;j=0;while((（1）)&&(ji-1)){p=p-next;j++;}if(p-next==NULL||ji-1)returnERROR;q=p-next;（2）;*s=q-data;free(q);returnOK;}/*listDelete*/5、写出算法的功能。intL(head){node*head,*p;intn=0;p=head;while(p!=NULL){p=p-next;n++;}return(n);}五、综合题1.编写算法，实现带头结点单链表的逆置算法。2.有两个循环链表，链头指针分别为L1和L2，要求写出算法将L2链表链到L1链表之后，且连接后仍保持循环链表形式。3.设一个带头结点的单向链表的头指针为head，设计算法，将链表的记录，按照data域的值递增排序。4.编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。5.已知head为带头结点的单循环链表的头指针，链表中的数据元素依次为（a1，a2,a3,a4,…,an）,A为指向空的顺序表的指针。阅读以下程序段，并回答问题：（1）写出执行下列程序段后的顺序表A中的数据元素；（2）简要叙述该程序段的功能。if(head-next!=head){p=head-next;A-length=0;while(p-next!=head){p=p-next;A-data[A-length++]=p-data;if(p-next!=head)p=p-next;}}6.设顺序表va中的数据元数递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。7、假设线性表采用顺序存储结构，表中元素值为整型。阅读算法f2，设顺序表L=(3,7,3,2,1,1,8,7,3),写出执行算法f2后的线性表L的数据元素，并描述该算法的功能。voidf2(SeqList*L){inti,j,k;k=0;for(i=0;iL-length;i++){for(j=0;jk&&L-data[i]!=L-data[j];j++);if(j==k){if(k!=i)L-data[k]=L-data[i];k++;}}L-length=k;}8.已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表中所有大于x且小于y的元素（若表中存在这样的元素）同时释放被删除结点空间。9.在带头结点的循环链表L中，结点的数据元素为整型，且按值递增有序存放。给定两个整数a和b，且ab，编写算法删除链表L中元素值大于a且小于b的所有结点。