Question

数据结构题

索引顺序表上的查找分两个阶段：（1 ）是——（2）是——
设表中的元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序、和归并排序方法对其进行排序（按递增顺序），（ ）最省时间，（ ）最费时间。（麻烦给解释一下）
利用两个栈S1和S2模拟一个队列时，如何用栈的运算实现队列的插入，删除以及判队空运算，请简述算法思想。

Answer 1

1 。确定待查元素所在的块；在块内查找待查的元素
2 。对冒泡排序来讲，由于算法中设置了一个标志flag，用于记载一趟排序中是否出现了记录交换，以便判断当前排序区域是否已自然有序。因此本题中用冒泡排序最省时间。
当初始时记录已按键值递增有序，若按快速排序，因每次所选取的中间元素都是最小的，故划分出的左右两个区域一个为空，另一个比原区域少一个元素，使得元素的比较次数只比上一趟少1，所以总的时间消耗是O(n^2 )，因此在本题中用快速排序法最费时间。
[答案]冒泡排序，快速排序。
3 。一个栈S1进,一个栈S2出.
入队时候,就在进的栈S1里放在尾巴上
出队的时候,如果出的栈S2不为空,则出.
否则把进的栈S1的一一出栈,并一一进入出的栈S2,再出.
否则,出错.
判空就是判断两个栈是否同时为空