2024知到答案 数据结构（中央财经大学） 完整智慧树网课章节测试答案
绪论 单元测试
1、判断题：
数据结构是计算机科学与技术专业的基础核心课程。（ ）
选项：
A:对
B:错
答案: 【对】
第一章 单元测试
1、判断题：
用链表实现栈，当栈顶位于链表首部时，最坏情况下对栈的每次push和pop操作仅需要常数时间。（ ）
选项：
A:对
B:错
答案: 【对】
2、单选题：
对容量已满的栈执行push操作，会发生（ ）。
选项：
A:下溢
B:对象游离
C:空指针异常
D:上溢
答案: 【上溢】
3、判断题：
泛型可以在编译期发现类型不匹配的错误。 （ ）
选项：
A:错
B:对
答案: 【对】
4、判断题：
二分查找可以用最多lg N次键值比较完成对大小为N的排序数组的查找。 （ ）
选项：
A:错
B:对
答案: 【错】
5、多选题：
算法理论分析中的常用符号有（ ）。
选项：
A:Big Theta
B:Big O
C:Big Omega
D:波浪线
答案: 【Big Theta;
Big O;
Big Omega;
波浪线】
第二章 单元测试
1、单选题：
假设对N个元素进行归并排序，则需要的归并操作的次数约为（ ）。
选项：
A:NlogN
B:N/2
C:logN
D:N
答案: 【logN】
2、单选题：
假设要从2000个元素中得到10个最小元素，最好采用（ ）。
选项：
A:快速排序
B:插入排序
C:归并排序
D:堆排序
答案: 【堆排序】
3、单选题：
给定数组{16, 22, 3, 24, 10, 8, 18}，用16作为切分元素完成一次快速排序切分后，其结果为（ ）。
选项：
A:{10, 3, 8, 16, 22, 24, 18}
B:{8, 3, 10, 16, 24, 18, 22}
C:{3, 8, 10, 16, 18, 22, 24}
D:{10, 8, 3, 16, 24, 22, 18}
答案: 【{10, 8, 3, 16, 24, 22, 18}】
4、单选题：
自然的归并排序。编写一个自底向上的归并排序，当需要将两个子数组排序时能够利用数组中已经有序的部分。首先找到一个有序的子数组（移动指针直到当前元素比上一个元素小为止），然后再找出另一个并将它们归并。public class MergeBUN { //GetIndex函数功能： 从index[1]开始记录第二个自然分组以及之后每个自然分组的"开始下标" private static int GetIndex(Comparable[] a, int[] a_index) { int j = 0; a_index[j++] = 0; //第一个自然分组开始下标默认为0 for(int i = 0; i < a.length-1; i++) { if(less(a[i+1],a[i])) { a_index[j++] = i+1; } } //j为自然分组的个数 return ( ？ ); } private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) { // copy to aux[] for (int k = lo; k <= hi; k++) { aux[k] = a[k]; } // merge back to a[] int i = lo, j = mid+1; for (int k = lo; k <= hi; k++) { if (i > mid) a[k] = aux[j++]; else if (j > hi) a[k] = aux[i++]; else if (less(aux[j], aux[i])) a[k] = aux[j++]; else a[k] = aux[i++]; } } public static void sort(Comparable[] a) { int n = a.length; Comparable[] aux = new Comparable[n]; int[] index=new int[n]; int num = GetIndex(a,index); //识别数组中的自然分组 int mergeNum=num; //保存自然分组的个数 for (int i = 2; i/2 < num; i*=2) { // int count=0; int j=0; for (int temp = 0; temp < mergeNum/2; temp++) { //内循环次数是分组个数除以2的整数部分，如分组个数为5，则内循环2次 int lo=index[j]; //记录归并起始位 int mid = index[j+i/2]-1; //记录两个归并分组中第一个分组的最后一位 int hi =0; if(j+i>num-1) hi=a.length-1; else hi=index[j+i]-1; //记录两个归并分组中第二个分组的最后一位merge(a, aux, lo, mid, hi); count++; //记录每次内循环完成的归并次数 j=j+i; } mergeNum=mergeNum-count; //得到剩余需要归并的分组个数 } } private static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0; } private static void show(Comparable[] a) { for (int i = 0; i < a.length; i++) { StdOut.print(a[i]); } }public static void main(String[] args) { String[] a = {"D","R","T","E","X","A","M","C","L","B","O","R","T","E","X","A","M","G","L","A","M","I","L" }; MergeBUN.sort(a); show(a); }}
选项：
A:i
B:j
C:a
D:a_index
答案: 【j】
5、单选题：
找出最小元素。在 MaxPQ中加入一个min()方法。你的实现所需的时间和空间都应该是常数。public class MaxPQ<Key> implements Iterable<Key> { private Key[] pq;private int n; private key min; …… public void insert(Key x) { if (n == pq.length - 1) resize(2 * pq.length); if(isEmpty()) min=x; else if(((Comparable<Key>)x).compareTo(min)<0) min=x; pq[( ？ )] = x; swim(n);}public Key delMax() { if (isEmpty()) return null; if(n==1) min=null; Key max = pq[1]; exch(1, n--); sink(1); pq[n+1] = null; if ((n > 0) && (n == (pq.length - 1) / 4))resize(pq.length / 2); return max; }public Key getMin(){ return min;}……}
选项：
A:n++
B:n
C:其他选项均不正确
D:++n
答案: 【++n】