数据结构大二上学期考点-数据结构大二上学期考点.md

焦虑烧麦 185 2022-05-02

基础知识

什么是算法

算法指解题方案的准确而完整的描述,是一系列解决问题的清晰指令。

算法的5个基本特征

正确性,有穷性,确定性,输入,输出

  1. 正确性:能按设计要求解决具体问题,并得到正确的结果。
  2. 有穷性:任何一条指令都只能执行有限次,即算法必须在执行有限步后结束。
  3. 确定性:算法中每条指令的含义必须明确,不允许由二义性
  4. 可行性:算法中待执行的操作都十分基本,算法应该在有限时间内执行完毕。
  5. 输入:一个算法的输入可以包含零个或多个数据。
  6. 输出:算法有一个或多个输出

评价算法好坏的标准有哪些

  • 正确:算法应能满足设定的功能和要求 。
  • 可读:思路清晰、层次分明、易读易懂 。
  • 健壮:输入非法数据时应能作适当的反应和处理。
  • 高效(时间复杂度):解决问题时间越短,算法的效率就越高。
  • 低存储量(空间复杂度):完成同一功能,占用存储空间应尽可能少。

数据的逻辑结构(线性结构与非线性结构)和存储结构有哪些

顺序存储结构;链式存储结构;索引存储结构;散列式存储结构

什么是线性表,有什么特点

是一种可以在任意位置进行插入删除数据元素操作的有序列表
特点:除第一个和最后一个元素外,其他元素都有一个直接前驱和后继元素

什么是顺序表,什么是链表,顺序表和链表的优缺点有哪些

  • 顺序表:使用顺序存储结构存储数据的线性表
    :随机读取;内存空间利用率高
    :需要预先估计表容量;插入和删除操作时需移动大量的数据元素
  • 链表:用链式存储结构存储数据的线性表
    :无限量存储数据;效率高
    :空间利用率低

什么是栈和队列,它们有什么特点

栈:是一种允许在表的一端(栈顶)进行插入删除操作的线性表;特点 先进后出
队列:允许在表的一端进行插入操作,在另一端删除操作的线性表;特点 先进先出

树与图结构有什么特点

树形结构是一对多的结构
图形结构是多对多结构,每个结点都可能有多个直接前驱和直接后继

给定一棵二叉树,会进行二叉树的遍历

二叉树的三种遍历:
先序遍历:根左右
中序遍历:左根右
后序遍历:左右根

例子:
20210110_225512.jpg

那么

先序(根左右):A B D H E I C F J K G
中序(左根右):D H B E I A J F K C G
后序(左右根):H D I E B J K F G C A

给定一组关键字,会构造哈希表(给定哈希函数和解决冲突的方法)

给定一组权值,会构造哈夫曼编码

折半查找对查找表有什么要求。给定一个有序查找表,会利用折半查找分析查找过程

折半查找法要求查找表中各元素的键值必须是递增或递减排列

算法部分(查找 和 排序)

排序

冒泡排序

public class BubbleSort3 {
    public static void main(String[] args) {
        int[] arr = {-12,3,5,8,9,21,45,67};

        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length -1; j++) {
                if (arr[j] > arr[j + 1]){
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}

快速排序

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = { 10,2,45,65,32,12,35,12,45,78,5 };
        quickSort(arr,0, arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(" ");
            System.out.print(arr[i]);
        }
    }

    public static void quickSort(int[] arr,int low,int high){
        int i,j,temp,t;
        if(low>high){
            return;
        }
        i = low;
        j = high;
        //temp就是基准位(参考数)
        temp = arr[low];

        while (i<j){
            //先看右边,依次往左递减
            while (temp<=arr[j]&&i<j){
                j--;
            }
            //再看左边,依次往右递增
            while (temp>=arr[j]&&i<j){
                i++;
            }
            //如果满足条件则交换
            if (i<j){
                t =arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
        }
        //最后将基准为与i和j相等位置的数字交换
        arr[low] = arr[i];
        arr[i] = temp;
        //递归调用左半数组
        quickSort(arr, low, j - 1);
        //递归调用右半数组
        quickSort(arr,j + 1,high);
    }

}

查找

二分查找

public class BinarySearch{
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9,10};
        int key = 8;    //查找的数
        int p = BinarySearch(arr,key,0,arr.length - 1);

        if(p == -1){
            System.out.println("查找的是"+key+",序列中没有该数!");
        }else{
            System.out.println("查找的是"+key+",找到位置为:"+p);
        }
    }

    /**
     * 功能描述: 递归实现二分算法
     * @Param: 参数 [key, array, low, high]
     * @Return: int
     * @Author: Liu
     * @Date: 1/9/2021 7:01 PM
     */
    public static int BinarySearch(int[] arr,int key,int low,int high){
        if(key < arr[low] || key > arr[high] || low > high){
            return -1;
        }

        int mid = (low + high) / 2;	//初始中间位置
        if(arr[mid] > key){
            //比关键字大则关键字在左区域
            return BinarySearch(arr, key, low, mid - 1);
        }else if(arr[mid] < key){
            //比关键字小则关键字在右区域
            return BinarySearch(arr, key, mid + 1, high);
        }else {
            return mid;
        }
    }

}

顺序查找

public class SeqSearch {
    public static void main(String[] args) {
        int[] array = {49,38,65,97,76,13,27,49,78,34,12,64,5,4,62};
        System.out.println("输入查找的数:");
        Scanner scanner = new Scanner(System.in);
        int input = scanner.nextInt();
        SeqSearch(array,input);
    }

    /**
     * 功能描述: 
     * @Param: 参数 [arr, input]
     * @Return: void
     * @Author: Liu
     * @Date: 1/9/2021 10:47 PM
     */
    public static void SeqSearch(int[] arr,int input){
        for (int i = 0; i < arr.length; i++) {
            if (arr[i]==input){
                System.out.println(input+"的位置是:"+i);
                break;
            }
            if (i == arr.length-1){
                System.out.println("没有该数");
            }
        }
    }

}