数据结构考研分类复习真题 第二章 答案[3]

．

．从任一结点出发都可访问到链表中每一个元素

．u=p>next; p>next=u>next; free(u);

．L>next>next==L ．p>next!=null

．L>next==L && L>prior==L

．s>next=p>next;p>next=s;

．() IF pa=NIL THEN return(true);

() pb<>NIL AND pa^data>=pb^data

() return(inclusion(papb));

() pb:=pb^next;

() return(false);

非递归算法

()pre:=pb;

() pa<>NIL AND pb<>NIL AND pb^data>=pa^data

()pa:=pa^next; pb:=pb>next;

()pb:=pre^next;pre:=pb;pa:=pa^next;

()IF pa=NIL THEN return(true) ELSE return(false);

[注]本题是在链表上求模式匹配问题非递归算法中用指针pre指向主串中开始结点(初始时为第一元素结点)若主串与子串对应数据相等两串工作指针pa和pb后移;否则主串工作指针从pre的下一结点开始(这时pre又指向新的开始结点)子串工作指针从子串第一元素开始比较一直继续到循环条件失败若pa为空则匹配成功返回true否则返回false

．A．VAR head:ptr B new(p) C p^data:=k D q^next:=p E q:=p(带头结点)

．() new(h);∥生成头结点以便于操作

() r^next:=p;

() r^next:=q;

() IF (q=NIL) THEN r^next:=p;

．A: r^link^data<>max AND q^link^data<>max

B: r:=r^link

C: q^link

D: q^link

E: r^link

F: r^link

G: r:=s(或r:= r^link)

H: r:=r^link

I: q^link:=s^link

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []