数据结构第2章习题及答案

7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（）存储方式最节省运算时间。【北京理工大学2000一、1（2分）】A．单链表B．双链表C．单循环链表D．带头结点的双循环链表8.静态链表中指针表示的是（）.【北京理工大学2001六、2（2分）】A．内存地址B．数组下标C．下一元素地址D．左、右孩子地址9.链表不具有的特点是（）【福州大学1998一、8(2分)】A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比10.下面的叙述不正确的是（）【南京理工大学1996一、10（2分）】A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B.线性表在链式存储时，查找第i个元素的时间同i的值无关C.线性表在顺序存储时，查找第i个元素的时间同i的值成正比D.线性表在顺序存储时，查找第i个元素的时间同i的值无关11.线性表的表元存储方式有(（1）)和链接两种。试指出下列各表中使用的是何种存储方式：表1是(（2）)存储方式；表2是(（3）)存储方式；表3是(（4）)存储方式；表4是(（5）)存储方式。表左的s指向起始表元。供选择的答案：A.连续B.单向链接C.双向链接D.不连接E.循环链接F.树状G.网状H.随机I.顺序J.顺序循环【上海海运学院1995二、1（5分）】12.(1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（）【南京理工大学2000一、3（1.5分）】A．（1），（2）B．（1）C．（1），（2）,(3)D.（2）13.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1Rlink=p;p-Llink-Rlink=q;q-Llink=q；B.p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;C.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;24．在单链表指针为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;【青岛大学2001五、3（2分）】25．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A．head==NULLB．head→next==NULLC．head→next==headD．head!=NULL【北京工商大学2001一、5（3分）】26.在双向链表存储结构中，删除p所指的结点时须修改指针（）。A．(p^.llink)^.rlink:=p^.rlink(p^.rlink)^.llink:=p^.llink;B．p^.llink:=(p^.llink)^.llink(p^.llink)^.rlink:=p;C．(p^.rlink)^.llink:=pp^.rlink:=(p^.rlink)^.rlinkD．p^.rlink:=(p^.llink)^.llinkp^.llink:=(p^.rlink)^.rlink;【西安电子科技大学1998一、1（2分）】27.双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p指向链表中的一个结点，现要求删去p所指结点，则正确的删除是（）（链中结点数大于2，p不是第一个结点）A．p^.llink^.rlink:=p^.llink;p^.llink^.rlink:=p^.rlink;dispose(p);B．dispose(p);p^.llink^.rlink:=p^.llink;p^.llink^,rlink:=p^.rlink;C．p^.llink^.rlink:=p^.llink;dispose(p);p^.llink^.rlink:=p^.rlink;D．以上A，B，C都不对。【南京理工大学1997一、1（2分）】二、判断1.链表中的头结点仅起到标识的作用。()【南京航空航天大学1997一、1（1分）】2.顺序存储结构的主要缺点是不利于插入或删除操作。()【南京航空航天大学1997一、2（1分）】3．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。()【北京邮电大学1998一、2（2分）】4．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。()【北京邮电大学2002一、2（1分）】5.对任何数据结构链式存储结构一定优于顺序存储结构。()【南京航空航天大学1997一、3（1分）】6．顺序存储方式只能用于存储线性结构。()【中科院软件所1999六、1-2（2分）】【上海海运学院1997一、1（1分）】7．集合与线性表的区别在于是否按关键字排序。()【大连海事大学2001一、5(1分)】8.所谓静态链表就是一直不发生变化的链表。()【合肥工业大学2000二、1（1分）】9.线性表的特点是每个元素都有一个前驱和一个后继。()【合肥工业大学2001二、1（1分）】10.取线性表的第i个元素的时间同i的大小有关.()【南京理工大学1997二、9（2分）】11.循环链表不是线性表.()【南京理工大学1998二、1（2分）】12.线性表只能用顺序存储结构实现。()【青岛大学2001四、2（1分）】13.线性表就是顺序存储的表。()【青岛大学2002一、1（1分）】14．为了很方便的插入和删除数据，可以使用双向链表存放数据。()【上海海运学院1995一、1（1分）】【上海海运学院1997一、2（1分）】15.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。()【上海海运学院1996一、1（1分）】【上海海运学院1999一、1（1分）】16.链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。()【上海海运学院1998一、2（1分）】三、填空1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。【北方交通大学2001二、4】2．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。【北方交通大学2001二、9】3．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点,若将结点y插入结点x之后，则需要执行以下语句:_______；______;【华中理工大学2000一、4（2分）】4．在一个长度为n的顺序表中第i个元素（11DOBEGINp:=p^.link;i:=i-1END;(D)___;WHILEjp^.pre^.freqDOp:=p^.pre;IFpqTHEN[（3）______]]；IF（4）_THEN[q^.next:=p,q^.pre;=p^.pre;p^.pre^.next:=q;p^.pre:=q]return(q);END;【北京工业大学1999五(12分)】29．循环链表a和b的结点值为字母，其中a表非递减有序，下面的程序欲构造一个递增有序的循环链表c，其中结点的值为同时在a，b两链表中出现的字母，且c中字母不重复，请补上程序中空缺的部分，并估计算法的时间复杂度。（设a，b的结点数分别为m，n）TYPElink=^node;node=RECORDkey:char;next:linkEND;PROCjj(a,b:link;VARc:link);VARp,q,r,s:link;BEGINnew(c);c^.next:=c;q:=a;p:=a^.next;WHILEpaDO[（1）___；WHILEp^.key=p^.next^.keyDO[q:=p;p=p^.next];｛跳过相同字母｝r:=b^.next;（2）_____;WHILEr^.keyp^.keyDOr:=r^.next;IFrbTHEN[s:=p;q^.next:=p^.next;（3）;s^.next:=c^.next;c^.next:=s;c:=s]ELSE[q:=p;p:=p^.next]];c:=c^.next；END;算法时间复杂度为O（4）___【北京工业大学2000四(15分)】30.以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。voidreverse(pointerh)/*h为附加头结点指针；类型pointer同算法设计第3题*/{pointerp,q;p=h-next;h-next=NULL;while((1)________){q=p;p=p-next;q-next=h-next;h-next=(2)________;}}【西南交通大学2000一、9】31.下面是用c语言编写的对不带头结点的单链表进行就地逆置的算法，该算法用L返回逆置后的链表的头指针，试在空缺处填入适当的语句。voidreverse（linklist&L）{p=null；q=L；while（q！=null）{(1);q-next=p；p=q；(2)___;}(3)_____;}【北京理工大学2001九、1（6分）】32．下面程序段是逆转单向循环链表的方法，p0是原链表头指针，逆转后链表头指针仍为p0。（可以根据需要增加标识符）p:=p0;q0:=NIL;WHILE（1）________DOBEGIN（2）________;（3）________;（4）______;（5）________END;p^.next:=q0;p0^.next:=p;p0:=p;【中国人民大学2000二、1（4分）】33．一个无头结点的线性链表(不循环)有两个域。数据域data，指针域next，链首head，下面算法用read(num)读入数据，当num小于0时，输入结束。建立一个数据以递增序组成的链表。PROCinsert(head,x);{在链首为head的表中按递增序插入x}new(r);r＾.data:=x;IFhead=NILTHEN[head:=(1)_____;r＾.next:=(2)________]ELSEIF(3)___THEN[r＾.next:=head;head:=r]ELSE[p:=head;WHILE(4)___AND(p＾.next≠NIL)DO[q:=p;(5)___];IF(6)___THEN[q＾.next:=(7)___;r＾.next:=(8)____;]ELSE[p＾.next:=(9)____;r＾.next:=(10)___;]]ENDP;PROCcreat(head);head:=(11)______;read(num);WHILEnum0DO[insert(head,num);read(num)]ENDP;【南京理工大学1999三、4（11分）】34.一元稀疏多项式以循环单链表按降幂排列，结点有三个域，系数域coef，指数域exp和指针域next；现对链表求一阶导数，链表的头指针为ha，头结点的exp域为–1。derivative(ha){q=ha;pa=ha-next;while((1)_______){if((2)____){((3)__);free(pa);pa=((4)_);}else{pa-coef((5)___);pa-exp((6)___);q=((7)__);}pa=((8)________);