数据�l�构�W�二章应用题�?qi��ng)参考答案[3]_跨考网

　  1. 如何通过攚w��的方法，把一个单向链表变成一个与原来链接方向相反的单向链表？�?a target="_blank">中国人民大学 2001 二�?/span>4 �Q?/span>2分）(j��)�?/span>

　　【参考答案�?/span>

　　本题是链表的逆置问题。设该链表带头结点，���头�l�点摘下�Q��ƈ���其指针域置�I�。然后从�W�一元素�l�点开始，直到最后一个结点�ؓ(f��)止，依次前插入头�l�点的后面，则实��C��(ji��n)链表的逆置�?/span>

　　2. 下面是一���法的核�?j��)部分，试说明该���法的功能�?/span>

　　pre:=L�?/span>.next;

　　{L是一单链表，�l�点有数据域 data和指针域 next}

　　IF pre<>NIL THEN

　　WHILE pre�?/span>.next<>NIL DO

　　BEGIN p:=pre�?/span>.next; IF p�?/span>.data>=pre�?/span>.data THEN pre:=p ELSE return(false) END;

　　return(true); �?a target="_blank">燕山大学 2000 七�?/span>1 �Q?/span>7分）(j��)�?/span>

　　【参考答案�?/span>

　　该算法的功能是判断链�?/span>L是否是非递减有序�Q�若是则�q�回�?/span>true”；否则�q�回�?/span>false“�?/span>pre指向当前�l�点�Q?/span>p指向pre的后�l��?/span>

　　3. 讑֍�链表�l�点指针域�ؓ(f��)next�Q�试写出删除链表中指�?/span>p所指结点的直接后���?/span>C语言语句。�?a target="_blank">北京�U�技大学 2000 一�?/span>3�?/span>

　　【参考答案�?/span>

　　q=p->next; p->next=q->next; free(q);

　　4. 讑֍�链表中某指针p所指结点（�?/span>p�l�点�Q�的数据域�ؓ(f��)data�Q�链指针域�ؓ(f��)next�Q�请写出�?/span>p�l�点之前插入s�l�点的操作（PASCAL语句�Q�。�?a target="_blank" class="keylink">北京�U�技大学 1999 一�?/span>2 �Q?/span>2分）(j��)�?/span>

　　【参考答案�?/span>

　　讑֍�链表的头�l�点的头指针�?/span>head,�?/span>pre=head�Q?/span>

　　while(pre->next!=p) pre=pre->next;

　　s->next=p; pre->next=s;