第2章测试题(1)(12页).doc

《第2章测试题(1)(12页).doc》由会员分享，可在线阅读，更多相关《第2章测试题(1)(12页).doc（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-一、二、三、四、 第2章测试题(1)-第 12 页五、 选择题1从一个具有n个结点的单链表中查找值为x的结点，在查找成功情况下，需平均比较（ d）n个节点，单链表。如果x等于第一个元素的值。则要比较1次 x等于第二个元素的值，则要比较2次最不巧：x值刚好等于第n个元素，则要比较x次所以总次数是1+2+3+n-1+n=(n+1)*n/2所以平均需要：(n+1)/2次。顺序数组可以用折半查找，需要 log2为低N 次个结点。AnBn/2C（n-1）/2D（n+1）/22（a ）插入、删除速度快，但查找速度慢。链表只需要修改前驱或者前驱与后继的指针就可以，查找时链表需要顺序查找，并且由于读取指针耗

2、费时间A链表B顺序表C有序顺序表D上述三项无法比较3若希望从链表中快速确定一个结点的前驱，则链表最好采用（ c）方式。双链表在结点前驱后继查找上的时间复杂度是O(1)A单链表B循环单链表C双向链表D任意4在一个单链表中，若删除p所指结点的后继结点，则执行（d）。p-next指向p指针的后继结点，p-next-next指向后继结点的后继结点。Ap-next=p-nextBp=p-next-nextCp=p-next;p-next=p-next-next;Dp-next=p-next-next5带头结点的单链表head为空的判定条件是（b ）。Ahead=NULLBhead-next=NULLCh

3、ead-next=headDhead!=NULL6在循环双向链表的p所指结点之后插入s所指结点的操作是（ d）。Ap-next=s;s-prior=p;p-next-prior=s;s-next=p-next;Bp-next=s;p-next-prior=s;s-prior=p;s-next=p-next;Cs-prior=p;s-next=p-next;p-next=s;p-next-prior=s;Ds-prior=p;s-next=p-next;p-next-prior=s;p-next=s;7若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ a）存储方

4、式最节省时间。想要存取任一指定序号的元素，链表实现这个功能的代价很大本来顺序表的弱点在于插入和删除元素，但是题目要求只最后进行插入和删除运算，所有顺序表是最好的选择！A顺序表B双向链表C带头结点的双循环链表D单循环链表六、 填空题1对于采用顺序存储结构的线性表，当随机插入或删除一个数据元素时，平均约需移动表中 一半 元素。2当对一个线性表经常进行的是插入和删除操作时，采用 链式 存储结构为宜。因为采用链式结构存储线性表，插入和删除操作需要从头结点起查找被插入或删除结点的前驱结点，并修改这些结点的指针域，查找过程平均移动指针域为表长的一半3当对一个线性表经常进行的是存取操作，而很少进行插入和删除

5、操作时，最好采用 顺序 存储结构。它的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中任一元素，它的存储位置可用一个简单，直观的公式来表示4在一个长度为n的顺序存储结构的线性表中，向第i个元素（1in+1）之前插入一个新元素时，需向后移动 n-i+1 个元素。这道题，可以进行举例来验证，比如要是在第一个元素前插入元素，需要移动n个元素。i=1时，需要移动n个，进行验证5从长度是n的采用顺序存储结构的线性表中删除第i个元素（1in），需向前移动 n-i 个元素。6对于长度是n的顺序存储结构的线性表，插入或删除元素的时间复杂度为 0（n） 。7在具有n个结点的有序单链表中插入

6、一个新结点并仍然有序的时间复杂度是 0（n） 。因为单链表保存的信息只有表头 如果要在特定位置插入一个节点 需要先从表头一路找到那个节点 这个过程是O(n)的8在双向链表中，每个结点共有两个指针域，一个指向 前驱 结点，另一个则指向 后继 结点。七、 判断题1链表中的头结点仅起到标识的作用。（ f）头结点的数据域还可以存储一些必要的数据，如表长。2顺序存储结构的主要缺点是不利于插入和删除操作。（ t）3线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（ f）结点内部空间是连续的。4顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（ f）还有其他比较参数。如空间利用率，

7、难易程度，存取快捷等。5对任何数据结构链表存储结构一定优于顺序存储结构。（ f）还有其他比较参数。如空间利用率，难易程度，存取快捷等。6顺序存储方式只能用于存储线性结构。（ f）也可用于树、二叉树等7循环链表不是线性表。（ f）8为了很方便地插入和删除数据，可以使用双向链表存放数据。（ t）9线性表的特点是每个元素都有一个前驱和一个后继。（ f）第一个结点无前驱，最后一个结点无后继。10取线性表的第i个元素的时间与i的大小有关。（ f）看线性表的存储机构，链表有关，顺序表无关。八、 应用题1线性表有两种存储结构：一是顺序表，二是链式表。试问：如果有n个线性表同时并存，并且在处理过程中各表的长度

8、会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？链表，理由是链表能够高效的执行插入删除操作，适用于元素变化较多的情形若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？顺序存储结构。顺序表可以随机存取，时间复杂度为O（1）2线性表的顺序存储结构具有三个弱点：其一，在进行插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分的利用。线性表的链式存储结构是否一定都能克服以上缺点，试讨论之。链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不

9、需移动元素，只修改指针，时间复杂度为O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。3线性表（a1，a2，.，an）用顺序映射表示时，ai和ai+1（1=inext;p;p=p-next) e=p-data;for(q=p-next;q;) if(e=q-data)s=q; p-next=q-next; q=q-next; free(s);else q=q-next;2 将数据元素x插入到递增有序的顺序表的适当位置，使插入后的顺序表仍为递增有序。struct list *p

10、, *q, *s, *head; p = head; while(p != NULL) if(x p-data)q = p; p = p-next; else s = (struct list*)malloc(sizeof(struct list); s-data = x; q-next = s; s-next = p; 3 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。#includestdio.h #includemalloc.h struct list int

11、data; struct list *next; struct list *head1,*head2,*p1,*p2,*q1,*q2; void main() int n=0; void unionlist(); p1=q1=(struct list*)malloc(sizeof(struct list); printf(请输入第一个链表的信息n); scanf(%d,&p1-data); while(p1-data!=0) n=n+1; if(n=1) head1=q1; else q1-next=p1; q1=p1; p1=(struct list*)malloc(sizeof(struc

12、t list); scanf(%d,&p1-data); q1-next=NULL; n=0; p2=q2=(struct list*)malloc(sizeof(struct list); printf(请输入第二个链表的信息n); scanf(%d,&p2-data); while(p2-data!=0) n=n+1; if(n=1) head2=q2; else q2-next=p2; q2=p2; p2=(struct list*)malloc(sizeof(struct list); scanf(%d,&p2-data); q2-next=NULL; unionlist(); voi

13、d unionlist() struct list *head,*p; int i=0; p1=head1; p2=head2; head=p=(struct list*)malloc(sizeof(struct list); p-data=0; while(p1 & p2) if(p1-datadata)p-next=p1; p=p1; p1=p1-next; elsep-next=p2; p=p2; p2=p2-next; p-next=p1?p1:p2; p=head; printf(合并后的链表为如下:n); while(p) i=i+1; if(i=1) p=p-next; prin

14、tf(%3d,p-data); p=p-next; printf(n); free(head1); free(head2); 4 已知递增有序的两个单链表A，B分别存储了一个集合。设计算法实现求两个集合的并集的运算A=AB。/无头链表 /#define data data_int #include head.h struct LNode / char data10; int data; struct LNode *next; typedef struct LNode * LinkList; void InitList_L(LinkList &L)/链表构造函数 L=new LNode; L-n

15、ext=NULL; void PrintList_L(LinkList &H)/链表显示函数LinkList L=H; L=L-next; while(1) coutdata value is datanext; if (L=NULL) return; void Insert_L(LinkList &H,int n=0)/插入链表 LinkList L=H; LinkList p=L; int i=0; if (n=0) n=1; while(p-next!=NULL)p=p-next; n+; else if (n1) couterrorendl; return; for (i=0;inex

16、t=NULL) couterrornext; p=new LNode; coutp-data; p-next=L-next; L-next=p; LinkList bing_LinkList(LinkList a,LinkList b) LinkList c; LinkList nc; LinkList t; InitList_L(c); nc=c; a=a-next; while (a!=NULL)/复制a到c t=new LNode; t-data=a-data; nc-next=t; t-next=NULL; nc=nc-next; a=a-next; b=b-next; while (

17、b!=NULL) nc=c; while (nc-next!=NULL)if (nc-next-data=b-data) break; nc=nc-next; if (nc-next=NULL) t=new LNode; t-data=b-data; nc-next=t; t-next=NULL; nc=nc-next; b=b-next;return c; void main() LinkList a,b,c; int i=0; InitList_L(a); coutnI will input date.endl; for (i=1;i=3;i+) Insert_L(a,i); / PrintList_L(a); InitList_L(b); coutnI will input date.endl; for (i=1;i=3;i+) Insert_L(b,i); / PrintList_L(b); c=bing_LinkList(a,b); PrintList_L(c); 5 设有两个链表，ha为单向链表，hb为单向循环链表。编写算法，将两个链表合并为一个单向链表，要求算法所需时间与链表长度无关。