数据结构与算法（Java语言版） 教案15--28（48+8）耿祥义 第7--14章 栈与Stack类----经典算法思想.docx

参考教案（共计56学时，含4个上机实践教案）

耿祥义编写

《数据结构与算法（java语言版）》

清华大学出版社出版

耿祥义，张跃平主编

参考教案15（2学时，实践）

1.实践前的复习

完成下列选择题。

（1）Arrays类的sort()方法是()。

A.双轴快速排序。

B.稳定排序。

C.时间复杂度比气泡法高的排序。

D.时间复杂度比选择法高的排序。

（2）下列叙述正确的是()。

A.链表的单向迭代器在遍历链表时也可以删除节点。

B.链表的单向或双向迭代器在遍历链表时，不允许链表调用set(intindex，Eobj)方法更新节点中的数据。

C.如果增加或删除链表节点，链表之前的视图仍然能被使用。

D.可以对不可变链表经行排序操作。

（3）顺序表的时间复杂度不是O(1)的方法是()

A.publicEget(intindex)。

B.publicintindexOf(Objectobj)。

C.publicbooleanadd(Ee)。

D.publicEset(intindex,Eelement)。

（4）对于下列代码，下列叙述错误的是()。

importjava.util.LinkedList;

importjava.util.ListIterator;

publicclassC{

publicstaticvoidmain(Stringargs[]){

LinkedListStringlist=newLinkedList();

for(charc=A;c=F;c++){

list.add(+c);

}

ListIteratorStringiterTwoWay=list.listIterator();

System.out.println(iterTwoWay.next());//代码A

System.out.println(iterTwoWay.previous());//代码B

iterTwoWay.next();

System.out.println(iterTwoWay.next());//代码C

iterTwoWay.next();

iterTwoWay.next();

System.out.println(iterTwoWay.next());//代码D

}

}

A.代码A输出的结果是A。

B.代码B输出的结果是B。

C.代码C输出的结果是B。

D.代码D输出的结果是E。

（5）对于下列代码，下列叙述错误的是()。

importjava.util.ArrayList;

publicclassC{

publicstaticvoidmain(Stringargs[]){

ArrayListStringlist=newArrayList();

list.add(A);

list.add(B);

list.add(F);

list.add(F);

list.add(B);

list.add(G);

System.out.println(list.lastIndexOf(F));//代码A

System.out.println(list.remove(B));//代码B

System.out.println(list.indexOf(B));//代码C

System.out.println(list.remove(2));//代码D

}

}

A.代码A输出的结果是3。

B.代码B输出的结果是true。

C.代码C输出的结果是1。

D.代码D输出的结果是F。

2.实践内容

完成后，要向老师展示程序的运行效果，老师根据完成情况，记载相关成绩。

（1）输出int型数组的一个最长的递增子数组，例如，对于

int[]a={15,16,6,8,9,10,11,11,11,8,2,10};

程序输出[6,8,9,10,11]。

（2）链表删除头节点和尾节点的时间复杂度都是O(1)。对于某些问题，可以利用链表的这一特点快速的处理数据。编写一个程序，