2022知到答案 数据结构（中央财经大学） 最新知到智慧树满分章节测试答案

绪论 单元测试

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:波浪线
B:Big Theta
C:Big O
D:Big Omega
答案: 【
波浪线
Big Theta
Big O
Big Omega
】

第二章 单元测试

1、 问题:假设对N个元素进行归并排序，则需要的归并操作的次数约为（ ）。
选项：
A:N
B:N/2
C:logN
D:NlogN
答案: 【
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:{10, 8, 3, 16, 24, 22, 18}
C:{8, 3, 10, 16, 24, 18, 22}
D:{3, 8, 10, 16, 18, 22, 24}
答案: 【
{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;