数据结构与算法分析第二次作业习题课.pptVIP

设栈S和队列Q的初始状态为空,元素a,b,c,d,e,f,g依次进入栈S.若每个元素出栈后立即进入队列Q,且7个元素出队的顺序是b,d,c,f,e,a,g,则栈S的容量至少是 A.1B.2C.3D.4统考题a,b,c,d,e,f,g依次进入栈Sb,d,c,f,e,a,gabtopcgdefSupposethatasinglylistisimplementedwithbothaheaderandtailnode. Describecontant-timealgorithmstoa.Insertitemxbeforepositionp(givenbyaniterator).b.Removetheitemstoredatpositionp(givenbyaniterator)2ABCheadtailPABBCheadPtailAXBCheadPtailSwaptwoadjacentelementsbyadjustingonlythelinks(andnotthedata)using:a.Singlylinkedlists.b.Doublylinkedlists.3.1通过只调整链来交换两个相邻的元素，使用 a.单链表 b.双链表3.1abcd①a.next=b.next③a.next.next=bb.next=a.next.next②单链表abcd①②③⑥⑤④1.a.right=b.right；2.b.right=a.right.right；3.a.right.right=b；4.b.right.left=b;5.a.right.left=a;6.b.left=a.right;双链表赋值某个链后，原链已经不存在，不能使用原链来获得节点修改链表不完全，遗漏只画图，没代码注意GiventwosortedlistsL1andL2,writeaproceduretocomputeL1∩L2usingonlythebasiclistoperations.3.2给定两个已排序的表L1和L2,只使用基本的链表操作编写计算L1∩L2的过程。3.2假设链表节点已按照节点值从小到大排列。新建链表L，存放L1∩L2的结果，故返回值类型为链表。遍历L1和L2，比较L1、L2当前节点的值L1当前节点值=L2当前节点值，把该节点加入L，同时L1、L2前进L1当前节点值L2当前节点值，L1前进L1当前节点值L2当前节点值，L2前进若L1或者L2为空，停止遍历返回L。分析publicLinkedListintersection(LinkedListL1,LinkedListL2){ LinkedListItritr1=L1.first(); LinkedListItritr2=L2.first(); LinkedListL=newLinkedList(); LinkedListItritr=L.zeroth();//返回header while(!itr1.isPastEnd()!itr2.isPastEnd()){//当前节点是否为空 if(itr1.retrive()==itr2.retrive()){ //若两个链表当前节点值相等 L.insert(itr1.current,itr); itr1.advance(); itr2.advance(); } elseif(itr1.retrive()itr2.retrive()) itr1.advance(); else itr2.advance(); } } returnL;}代码如果不创建新链表，直接在L1上修改，p3指向已选择出的结果的最后一个节点。那么while循环结束后，没有把p3.next=null。直接在原链表上修改，