搜索
1《数据结构》期末复习题及参考答案-第2章线性表一、选择题1、下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。2、线性表是具有n个（）的有限序列（n0）。A．表元素B．字符C．数据元素D．数据项E．信息项3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表4、设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用()最节省时间。A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表5、静态链表中指针表示的是（）.A．内存地址B．数组下标C．下一元素地址D．左、右孩子地址6、链表不具有的特点是（）A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比7、长度为N的线性表，如果是顺序存储，则访问、删除某个结点的时间复杂度分别是（）和（）；如果是链式存储，则访问、删除某个结点的时间复杂度分别是（）和（）。A.O(N),O(1),O(1),O(N)B.O(N),O(1),O(N),O(1)C.O(1),O(1),O(N),O(1)D.O(1),O(N),O(N),O(1)8、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1=i=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)9、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。A．O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)10、线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）A．O（i）B．O（1）C．O（n）D．O（i-1）11、在双向链表指针p的结点前插入一个指针q的结点操作是（）。A.p-Llink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q；B.p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;2C.q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q;D.q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q;12、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。A．p-next=s;s-next=p-next;B．s-next=p-next;p-next=s;C．p-next=s;p-next=s-next;D．p-next=s-next;p-next=s;13、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A．head==NULLB．head→next==NULLC．head→next==headD．head!=NULL14、设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。(A)q=p-next；p-data=q-data；p-next=q-next；free(q)；(B)q=p-next；q-data=p-data；p-next=q-next；free(q)；(C)q=p-next；p-next=q-next；free(q)；(D)q=p-next；p-data=q-data；free(q)；二、填空题1、对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为O(n)，在表尾插入元素的时间复杂度为O(1)。2、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用___顺序____存储结构。1、长度为N的线性表中插入一个结点，对于顺序存储和链式存储的线性表，其插入操作的时间复杂度分别是O(N)和O(1)。3、线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____（n-1）/2___。3、顺序存储的线性表中已有n个结点，插入一个新结点平均需要移动数据n/2次。4、设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点,若将结点y插入结点x之后，则需要执行以下语句:py-next=px-next;px-next=py；5、在一个长度为n的顺序表中第i个元素（1=i=n）之前插入一个元素时，需向后移动___n-i+1___个元素。6、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为___O(1)_____,在给定值为x的结点后插入一个新结点的时间复杂度为____O(n)____。7、根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成___单链表3_____和___多重链表____；而又根据指针的连接方式，链表又可分成__（动态）链表______和___静态链表_____。8、顺序存储结构是通过___物理上相邻_____表示元素之间的关系的；链式存储结构是通过____指针____表示元素之间的关系的。9、一个顺序存储的线性表，第1、第2个元素的存储地址分别是16进制的16A、17A，那么第10个元素的存储地址是16进制的1FA。10、对于双向链表,在两个结点之间插入一个新结点需修改的指针共___4___个，单链表为____2___个。11、循环单链表的最大优点是：___从任一结点出发都可访问到链表中每一个元素。_____。12、在单链表L中，指针p所指结点有后继结点的条件是：__p-next!=NULL13、线性表的存储结构分为__顺序存储结构____和__链式存储结构____。14、采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可将不用结点空间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。15、设单链表结点指针域为next，则删除链表中指针p所指结点的直接后继的的操作是：q=p-next;p-next=q-next;free(q);16、设单链表的头结点的头指针为head,且pre=head，单链表中某指针p所指结点（即p结点）的数据域为data，链指针域为next，则在p结点之前插入s结点的操作是：while(pre-next!=p)pre=pre-next;s-next=p;pre-next=s;17、在单链表p结点之后插入s结点的操作是：s-next=p-next;p-next=s;三、简答题1、已知顺序表La和Lb中数据元素按值非递减有序排列，归并La和Lb得到新的顺序表Lc，使Lc中的数据元素也按值非递减有序排列-这种操作称为顺序表的归并操作。请阅读下列顺序表的归并操作算法代码，分析该算法的时间复杂度，并作简要解释。voidMergeList(SqListLa,SqListLb,SqList&Lc){pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;4pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));if(!Lc.elem)exit(OVERFLOW);//存储分配失败pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(pa=pa_last&&pb=pb_last){if(*pa=*pb)*pc++=*pa++;else*pc++=*pb++;}while(pa=pa_last)*pc++=*pa++;//将La的剩余元素插入while(pb=pb_last)*pc++=*pb++;//将Lb的剩余元素插入}参考答案：上述算法将归并后的数据元素存放在新的顺序表Lc中，顺序表La和Lb不用变化，只是把顺序表La和Lb中的数据元素一个个新插入到顺序表Lc的末尾，最多有La.length+Lb.length个数据元素要插入到顺序表Lc中，所以该算法的时间复杂度是O(La.length+Lb.length)。2、已知顺序表La和Lb，现在将存在于顺序表Lb中而不存在于顺序表La中的数据元素插入到顺序表La中去（如果发现顺序表La的空间不够，则需要扩大顺序表La）。具体做法是从顺序表Lb中依次取得每个数据元素，并依值在顺序表La中进行查访，若不存在，则插入之-这种操作称为顺序表的合并操作。请阅读下列顺序表的合并操作算法代码，分析该算法的时间复杂度，并作简要解释。voidunion(List&La,ListLb){ElemTypee;intLa_len,Lb_len,i;La_len=ListLength(La);//求顺序表的长度Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i++){GetElem(Lb,i,e);//依次取Lb中第i个数据元素赋给eif(!LocateElem(La,e,equal)//依值e在顺序表La中进行查访ListInsert(La,++La_len,e);//La中不存在和e相同的数据元素，则在La的最后面插入}}参考答案：在顺序表La中查访是否存在和Lb中第i个数据元素（值为e）相同的数据元素的方法是:令e和La中的数据元素逐个比较。若La中存在和e相同的数据元素ai，则比较次数为i(1≤i≤La.length),否则为La.length，即算法LocateElem的时间复杂度为O(La.length)。而最多有Lb.length个数据元素要插入到顺序表La中，由此，算法union的时间复杂度为:O(La.length×Lb.length)。53、线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。参考答案：链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。四、算法分析题1、下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确的内容。typedefstructnode{intdata;structnode*next;}linklist;voidlinklistcreate(___linklist_*&head){for(i=1;i=n;i++){p=(linklist*)malloc(sizeof(linklist));scanf(“%d”,&(p-data));p-next=NULL;if(i==1)head=q=p;else{q-next=p;_____q=p_____;}}}2、下面的结构体定义了双向链表的节点结构。请分析如下程序代码，填写其中缺少的语句代码：typedefstructnode{intdata；structnode*last;structnode*next;}Node;voiddeleteOne(Node*head,inttarget){Node*p=headnext;while(p!=NULL){if(pdata!=target)____p=