《数据结构与 Java 集合框架》期末试卷
（2013 级软件技术、游戏软件，共 72 人）
本卷共 7 道算法阅读与设计题，根据要求完成答题。 一、请补充完成下面程序的代码，使得测试代码能够顺利执行。（10 分） public class Test01 {
public static void main(String[] args) { System.out.println(add(3, 4)); System.out.println(add(3, 4, 5)); System.out.println(add(3, 4, 5,7,21));
MyArrayStack() { data = (E[]) new Object[10]; _______________________; // 初始化的时候，是一个空栈
}
public E push(E item) { // 把项压入堆栈顶部。 top++; _______________________; return item;
while (i < j && array[i] < x) // 从前面忘后面找，找到第一个比 x 大的数字 i++;
if (i < j) { ______________________________ j--;
} } array[i] = x;
// 将前面一部分元素快速排序 quickSort(array, low, i - 1); // 将后面一部分元素快速排序
五、MyArrayStack.java 模拟实现了顺序栈。 import java.util.Arrays; import java.util.EmptyStackException;
public class MyArrayStack<E> { // 顺序存储结构实现的栈
private E data[]; private int top; // top 标识栈顶元素下标
数组当中 {
// 0 到 i-1 位置上的所有元素，已经排好序 int x = array[i]; int j; for (j = i - 1; j >= 0; j--)
}
public E pop() {
// 移除堆栈顶部的对象，并作为此函数的值返回该对象。
if(top == -1)
throw new EmptyStackException();
E temp = data[top]; _______________________; return temp; }
public E peek() { // 查看堆栈顶部的对象，但不从堆栈中移除它。 if(top == -1) throw new EmptyStackException(); return data[top];
数所指定的元素数。 if (minCapacity > this.size) {
Integer temp[] = new Integer[minCapacity]; for (int i = 0; i < data.length; i++)
temp[i] = data[i]; data = temp; } }
}
public void clear() { this.size = 0;
}
public void add(int index, Integer element) { // 将指定的元素插入此列表中的指定位置。向右移动当前位于该位置的元素（如果有）以 //及所有后续元素（将其索引加 1）。
if (index < 0 || index > this.size) throw new IndexOutOfBoundsException();
} } 三、Test03.java 实现了几个常见的递归应用，任选其中的 1 个，将算法代码补充完整。（10 分） public class Test03 {
public static void main(String[] args) { System.out.println(fib(20)); writeBinary(8); hanoi(3, "A", "B", "C");
} private static long fib(int n) {
//返回 Fibonacci 数列的第 n 项。Fibonacci 数列，F1=1，F2=1，Fn=Fn-1+Fn-2
} private static void writeBinary(int n) {
//将十进制数 n 按照二进制输出
}
public boolean empty() {// 测试堆栈是否为空。 return top == -1;
}
}
1．在横线上补充完成代码，使得方法能正确执行。（9 分）
2．一个栈的输入序列为 1 2 3 4 5，下列不可能是栈的输出序列的是（ ）。（2 分）
A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5
}
private static int add(int... x) {
} } 二、下面程序代码运行结果是：______________________________________。（10 分） public class Test02 {
public static void main(String[] args) { String str = "abcsts454ystasd37486shy87a7sksdye"; String s[] = str.split("s"); for (String t : s) System.out.print(t+"*");
private Integer data[]; private int size;
MyArrayList() { data = new Integer[10]; size = 0;
}
MyArrayList(int initialCapacity) { //在下 Nhomakorabea完成代码
}
public boolean add(Integer e) { if (size >= data.length) this.ensureCapacity(data.length + data.length / 2); data[size] = e; size++; return true;
for (int i = 0; i < array.length; i++) array[i] = temp[i];
}
public void insertSort(int[] array) {// 直接插入排序 for (int i = 1; i < array.length; i++) // 将后面的所有元素，插入到一个已经排好序的
public int size() { return this.size;
}
public boolean isEmpty() { // 如果此列表中没有元素，则返回 true，在下面补充完成代码
}
} 1．补充完成构造器 MyArrayList(int initialCapacity) 的实现代码。（6 分） 2．补充方法 isEmpty()的实现代码。（4 分） 3．补充方法 add(int index, Integer element)的实现代码（10 分）
D. 1 5 4 3 2
3．如有元素 1、2、3 进行进出栈操作，可能的出栈序列有___________________
______________________________________________________。（4 分）
六、Sort.java 演示了几种常见的排序算法。在横线上补充完成所有代码，使得方法能正确 执行。（15 分） import java.util.Random;
if (size >= data.length) // 扩容 this.ensureCapacity(data.length + data.length / 2);
//在下面补充完成代码
}
public void ensureCapacity(int minCapacity) { // 如有必要，增加此 ArrayList 实例的容量，以确保它至少能够容纳最小容量参
______________________________ } }
public void countSort(int[] array) {// 计数排序 int[] temp = new int[array.length]; for (int i = 0; i < array.length; i++) { int count = 0; for (int j = 0; j < array.length; j++) { if (array[j] < array[i]) count++; } while (temp[count] == array[i]) count++; temp[________________] = array[i]; }
}
public void printArray(int[] data) { for (int i : data) { System.out.print(i + " "); } System.out.println();
}
public static void main(String[] args) { Sort sortTest = new Sort(); int[] array = sortTest.createArray(); sortTest.printArray(array); // sortTest.selectSort(array); // sortTest.insertSort(array);//直接插入排序 // sortTest.countSort(array); sortTest.quickSort(array);// 快速排序 System.out.println("进行排序之后的数组："); sortTest.printArray(array);