精华内容
下载资源
问答
  • 计算机专业基础综合数据结构排序历年真题试卷汇编5 (总分66.00做时间90分钟) 一 单项选择(总数15分数30.00) 1.已知关键字序列58121928201522是小根堆(最小堆)插入关键字3调整后得到的小根堆是( )2009年全国...
  • 排序是最基础和常用的算法之一一般情况下排序不开比较数据交换怎样降低算法的时间及空间复杂性是算法设计的目标尽管经典算法已有不少但研究一直不断2001年还有综合性能很好的新算法出现 为了对n个元素的线性表进行...
  • 4 计算机专业基础综合数据结构集合历年真题试卷汇编) 分钟做时间90(总分70.0040.00) 分数总数20一 单项选择( 分)2009年全国试题4(21.下列二叉排序树中满足平衡二叉树定义的是( ) 分数2.00 A. B. C. D. 解析 树...
  • 奇偶排序算法不是严蔚敏老师书上的算法,是今年上海大学计算机考研(832计算机组成原理与数据结构)的一道考试,听朋友说了之后感觉很不错,给大家分享一下。 题目大致含义如下: 已知奇偶交换排序如下所述: ...

    一、冒泡排序

    1、奇偶排序简介

    奇偶排序算法不是严蔚敏老师书上的算法,是今年上海大学计算机考研(832计算机组成原理与数据结构)的一道考试题,听朋友说了之后感觉很不错,给大家分享一下。

    题目大致含义如下:

    已知奇偶交换排序如下所述:
    
    1.第一趟对序列中所有奇数项i扫描,将a[i]和a[i+1]进行比较;
    2.第二趟对序列中所有偶数项i扫描,将a[i]和a[i+1]进行比较。
    3.每次比较时若 a[i]>a[i+1],则将两者交换。
    4.第三趟对所有奇数项,第四趟对所有偶数项……,如此重复,直至整个序列有序。
    5.写出奇偶交换排序算法

     

    2、算法思想及流程

    这个算法原理是也是比较简单的,接下来就给大家分享一下我的做法。以下面这几个数据来模拟方便大家理解:

    给定一组数据如下:1,3,5,2,8,6,4,7

    第一趟排序,对所有奇数项扫描,如果比后一项大,交换:

    [1,3],[5,2],[8,6],[4,7]   =>  [1,3],[2,5],[6,8],[4,7]

    第二趟排序,对所有偶数项扫描,如果比后一项大,交换:

    1,[3,2],[5,6],[8,4],7  =>  1,[2,3],[5,6],[4,8],7

    第三趟排序,对所有奇数项扫描,如果比后一项大,交换:

    [1,2],[3,5],[6,4],[8,7]   =>  [1,2],[3,5],[4,6],[7,8]

    第四趟排序,对所有偶数项扫描,如果比后一项大,交换:

    1,[2,3],[5,4],[6,7],8  =>  1,[2,3],[4,5],[6,7],8 

    通过这个分析,我想大家对这个;排序过程应该有比较深刻的了解了,我们会注意到两个问题:

    1,一串数据可能有奇数个,可能有偶数个,怎么保证它不访问最后一个,导致出错呢?

    答:我们可以通过设置循范围,当循环变量到总个数-1时,停止循环。

    2,我们人眼能分辨到第四趟停止,计算机怎么实现呢?

    答:我们设置两个中间变量m,n来控制,如果奇排序过程中有元素交换,m为1,否则为0;如果偶排序过程中有元素交换,n为1,否则为0。当mn同时为0时,说明奇偶都没有交换,这个时候说明数据有序。

    接下来分享我的全部代码。

    二、全部代码

    刚才上面是分析,接下来我将所有的代码分享一下。为了更好的看效果,我找了奇数个数字(因为示例是偶数个数字),并且换了一组数字来测试。

    #include<iostream>
    using namespace std;
    
    void Sort(int Arr[], int length) {
    	int temp;
    	int m = 1;
    	int n = 1;
    	while (m||n)
    	{
    		for (int i = 0; i < length - 1; i = i + 2)
    		{
    			if (Arr[i] > Arr[i + 1])
    			{
    				temp = Arr[i];
    				Arr[i] = Arr[i + 1];
    				Arr[i + 1] = temp;
    				m = 1;
    			}
    			else
    				m = 0;
    		}
    		for (int j = 1; j < length - 1; j = j + 2)
    		{
    			if (Arr[j] > Arr[j + 1])
    			{
    				temp = Arr[j];
    				Arr[j] = Arr[j + 1];
    				Arr[j + 1] = temp;
    				n = 1;
    			}
    			else
    				n = 0;
    		}
    	}
    }
    
    void OutputArr(int Arr[], int length) {
    	for (int i = 0; i < length; i++)
    	{
    		cout << Arr[i] << ", ";
    
    	}
    	cout << endl;
    }
    
    void main() {
    	int Arr[] = { 45,57,12,31,1,60,92,71,87 };
    	Sort(Arr, 9);
    	OutputArr(Arr, 9);
    }

    三、运行结果

    这个算法并不唯一,如果大家有更好的算法,可以在下面分享,大家有什么问题也可以在下面留言哦!!!

     

    展开全文
  • 再因为是千万级的数据,可以考虑使用桶排序,建立一个有711大小的桶(数组),遍历整个文档,根据分数大小在相应的桶号上计数。 3.根据上面两步,基本是可以实现单纯的成绩排序。而且时间复杂度为O(n),空间复杂度...
  • 排序是根据(A)的大小重新安排各元素的顺序。A.关键字B.数组C....内排序是指在排序的整个过程中,全部数据都在计算机的(A)中完成的排序。A.内存B.外存C.内存和外存D.寄存器4.直接插入排序...

    ===Tips:点击上方 蓝字 关注 并 查看历史消息===

    2cae3b5a5230bfa9560cf2b9e48d12b4.gif

    1排序是根据(A)的大小重新安排各元素的顺序。

    A.关键字

    B.数组

    C.元素件

    D.结点

    2.评价排序算法好坏的标准主要是(D)

    A.执行时间

    B.辅助空间

    C.算法本身的复杂度  

    D.执行时间和所需的辅助空间

    3.内排序是指在排序的整个过程中,全部数据都在计算机的(A)中完成的排序。

    A.内存

    B.外存

    C.内存和外存

    D.寄存器

    4.直接插入排序的方法是(B)的排序方法。

    A.不稳定

    B.稳定

    C.外部

    D.选择

    5.直接插入排序的方法要求被排序的数据(B)存储。

    A.必须链表

    B.必须顺序

    C.顺序或链表

    D.可以任意

    6.直接插入排序的方法是从第(B)个元素开始,插入到前边适当位置的排序方法。

    A.1

    B.2

    C.3

    D.n

    7从待排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较,并将其放入已排序的正确位置上的方法,称为(C)

    A.希尔排序

    B.冒泡排序

    C.插入排序

    D.选择排序

    8排序方法中,从未排序序列中挑选元素,并将其依次放入已排序序列(初始时为空)的一端的方法,称为(D)

    A.希尔排序

    B.归并排序

    C.插入排序

    D.选择排序

    9按排序策略分类,冒泡排序属于(B)

    A.分配排序

    B.交换排序

    C.插入排序

    D.选择排序

    10每次把待排序的数据划分为左、右两个区间,其中左区间中元素的值不大于基准元素的值,右区间中元素的值不小于基准元素的值,此种排序方法称为(C)

    A.冒泡排序

    B.堆排序

    C.快速排序

    D.归并排序

    11.快速排序在(B)情况下最不利于易发挥其长处。

    A.待排序的数据量太大`  

    B.待排序的数据已基本有序

    C.待排序的数据完全无序

    D.待排序的数据个数为奇数

    12.下述几种排序方法中,要求内存量最大的是(D)

    A.插入排序

    B.选择排序

    C.快速排序

    D.归并排序

    13.堆的形状是一棵(C)

    A.二叉排序树

    B.满二叉树

    C.完全二叉树

    D.平衡二叉树

    14.快速排序的方法是(A)的排序方法。

    A.不稳定

    B.稳定

    C.外部

    D.选择

    15.下列排序方法中,关键字比较次数与记录的初始排列次序无关的是(A)

    A.选择排序

    B.希尔排序

    C.插入排序

    D.冒泡排序

    16.下述几种排序方法中,平均时间复杂度最小的是(A)

    A.希尔排序

    B.插入排序

    C.冒泡排序

    D.选择排序

    17.对n个不同的排序码进行冒泡(递增)排序,在下列(B)情况比较的次数最多。

    A.从小到大排列好的

    B.从大到小排列好的

    C.元素无序

    D.元素基本有序

    18.用直接插入排序法对下面的4个序列进行由小到大的排序,元素比较次数最少的是(B)

    A.94,32,40,90,80,46,21,69

    B.21,32,46,40,80,69,90,94

    C.32,40,21,46,69,94,90,80

    D.90,69,80,46,21,32,94,40

    19一组记录的排序码为(25,48,16,35,79,82,23,40),其中含有4个长度为2的有序表,按归并排序的方法对该序列进行一趟归并后的结果为(A)

    A16,25,35,48,23,40,79,82

    B16,25,35,48,79,82,23,40

    C16,25,48,35,79,82,23,40

    D16,25,35,48,79,23,40,82

    20一个数据序列的关键字为(46,79,56,38,40,84),采用快速排序,并以第一个数为基准得到第一次划分的结果为(C)

    A(38, 40, 46, 56, 79, 84)

    B(40, 38, 46, 79, 56, 84)

    C(40, 38, 46, 56, 79, 84)

    D(40, 38, 46, 79, 56, 84)

    6f0866878cdfcfae2a9e2708a56436a8.png

    911f3cd85c36165a0e7f00a011da3982.png

    展开全文
  • 数 据 结 构 基 础 课 外 实 验 指 导 书 计算机学院 2015年...地点鉴主1108 一上机实验概述 上机实验是对学生的一种全面综合训练是与课堂听讲自学和练习相辅相成的必不可少的一个教学环节通常实验中的问题比平时的习
  • 桂电2018数据结构试题及答案 单项选择每2分共50分 1数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间B和运算的学科 A结构 B关系 C运算 D算法 2计算机算法指的是B ? A程序? B问题求解...
  • 重新排序数组每个数字,当扫描到数字m的时候判断下标为i的数字是否等于m:如果是,就寻找下一个;如果不是,就判断下标为m的对应的数字是否等于m,如果它与第m个数字相等,就等于找到了一个重复的数字,如果不相等就...

    https://www.jianshu.com/p/cec86f055b02

     

    判断素数

    • 直接判断

    • 去偶数判断

    • 只需要判断到平方根

     


    2.如何在给定的整数数组中找到重复的数字?

     

    插入排序

    HashSet

     

    重新排序数组每个数字,当扫描到数字m的时候判断下标为i的数字是否等于m:如果是,就寻找下一个;如果不是,就判断下标为m的对应的数字是否等于m,如果它与第m个数字相等,就等于找到了一个重复的数字,如果不相等就把第i个数与第m个数交换位置,把m放在其对应的下标m的位置。

     

    例如:

     

    首先给定数组arr[] = {2, 3, 0, 1, 3}。因为数组中最大的数是n-1,那就一个萝卜一颗坑。从0号下标位置开始,0号元素为2,不等于0,交换0号和2号位置,数组变为: 

    {0, 3, 2, 1, 3}。再比较0号位置,下标和值相等,往后走到1号下标元素为3,不等于1,交换1号和3号,变成:{0, 1, 2, 3, 3}。再继续,下标来到4号位置,发现元素下标与值不相等,比较4号和3号下标位置,发现元素相等,返回3即可。

     


    3.如何在未排序整数数组中找到最大值和最小值?

     

    一次遍历,2n次比较

    首尾先比较,再线性找最大最小,1.5n次

     


    4.如何找到数组所有和等于一个给定数的数对?

     

    直接比较

    排序后比较

    Hash表,看看sum-x在不在表里

     


    如何在一次遍历中找到单个链表的中值?

     

    如果有序:快慢指针

    如果无序:开一个新空间进行排序

     


    5.如何实现桶排序算法?

     

    桶排序(Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶里。每个桶再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序),最后依次把各个桶中的记录列出来记得到有序序列。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是比较排序,他不受到O(n log n)下限的影响。

     


    如何在不使用第三个变量的情况下交换两个数字?

          int a,b;

          a=10;b=12;

          a=b-a; //a=2;b=12

          b=b-a; //a=2;b=10

          a=b+a; //a=10;b=10

     


    什么是决策树


    1.数组和链表的区别,请详细解释。

     

    从逻辑结构来看:

    • a) 数组必须事先定义固定的长度(元素个数),不能适应数据动态地增减的情况。当数据增加时,可能超出原先定义的元素个数;当数据减少时,造成内存浪费;数组可以根据下标直接存取。

    • b) 链表动态地进行存储分配

     

    从内存存储来看:

    • a) (静态)数组从栈中分配空间, 对于程序员方便快速,但是自由度小

    • b) 链表从堆中分配空间, 自由度大但是申请管理比较麻烦

     

    从上面的比较可以看出,如果需要快速访问数据,很少或不插入和删除元素,就应该用数组;

    相反, 如果需要经常插入和删除元素就需要用链表数据结构了。

     


    3、快速排序的改进

    只对长度大于k的子序列递归调用快速排序,让原序列基本有序,然后再对整个基本有序序列用插入排序算法排序。实践证明,改进后的算法时间复杂度有所降低,且当k取值为 8 左右时,改进算法的性能最佳。

     

    选择基准元的方式

    对于分治算法,当每次划分时,算法若都能分成两个等长的子序列时,那么分治算法效率会达到最大。也就是说,基准的选择是很重要的。选择基准的方式决定了两个分割后两个子序列的长度,进而对整个算法的效率产生决定性影响。最理想的方法是,选择的基准恰好能把待排序序列分成两个等长的子序列。

     

    方法1 固定基准元

    如果输入序列是随机的,处理时间是可以接受的。如果数组已经有序时,此时的分割就是一个非常不好的分割。

     

    方法2 随机基准元

    这是一种相对安全的策略。由于基准元的位置是随机的,那么产生的分割也不会总是会出现劣质的分割。在整个数组数字全相等时,仍然是最坏情况,时间复杂度是O(n^2)。实际上,随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。

     

    方法3 三数取中

    引入的原因:虽然随机选取基准时,减少出现不好分割的几率,但是还是最坏情况下还是O(n^2),要缓解这种情况,就引入了三数取中选取基准。

    分析:最佳的划分是将待排序的序列分成等长的子序列,最佳的状态我们可以使用序列的中间的值,也就是第N/2个数。可是,这很难算出来,并且会明显减慢快速排序的速度。这样的中值的估计可以通过随机选取三个元素并用它们的中值作为基准元而得到。事实上,随机性并没有多大的帮助,因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为基准元。

     

    选择排序算法准则:

    一般而言,需要考虑的因素有以下四点:

    设待排序元素的个数为n.

    1)当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序。

    2)当n较大,内存空间允许,且要求稳定性:归并排序

    3)当n较小,可采用直接插入或直接选择排序。

        直接插入排序:当元素分布有序,直接插入排序将大大减少比较次数和移动记录的次数。

        直接选择排序 :元素分布有序,如果不要求稳定性,选择直接选择排序

    5)一般不使用或不直接使用传统的冒泡排序。

    6)基数排序

    它是一种稳定的排序算法,但有一定的局限性:

      1、关键字可分解。

      2、记录的关键字位数较少,如果密集更好

      3、如果是数字时,最好是无符号的

     


    冒泡排序算法的改进

    1.设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。

    2.传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

     


    B树和B+树的区别,以一个m阶树为例。

    • 1. 关键字的数量不同;B+树中分支结点有m个关键字,其叶子结点也有m个,其关键字只是起到了一个索引的作用,但是B树虽然也有m个子结点,但是其只拥有m-1个关键字。

    • 2. 存储的位置不同;B+树中的数据都存储在叶子结点上,也就是其所有叶子结点的数据组合起来就是完整的数据,但是B树的数据存储在每一个结点中,并不仅仅存储在叶子结点上。

    • 3. 分支结点的构造不同;B+树的分支结点仅仅存储着关键字信息和儿子的指针(这里的指针指的是磁盘块的偏移量),也就是说内部结点仅仅包含着索引信息。

    • 4. 查询不同;B树在找到具体的数值以后,则结束,而B+树则需要通过索引找到叶子结点中的数据才结束,也就是说B+树的搜索过程中走了一条从根结点到叶子结点的路径。

    • 每个叶子结点都存有相邻叶子结点的指针

     

     

     

    3.红黑树的定义

    红黑树是一种二叉查找树,但在每个结点上增加了一个存储位表示结点的颜色,可以是RED或者BLACK。通过对任何一条从根到叶子的路径上各个着色方式的限制,红黑树确保没有一条路径会比其他路径长出两倍,因而是接近平衡的。

     

    当二叉查找树的高度较低时,这些操作执行的比较快,但是当树的高度较高时,这些操作的性能可能不比用链表好。红黑树(red-black tree)是一种平衡的二叉查找树,它能保证在最坏情况下,基本的动态操作集合运行时间为O(lgn)。

     

    红黑树必须要满足的五条性质:

    • 性质一:节点是红色或者是黑色; 在树里面的节点不是红色的就是黑色的,没有其他颜色,要不怎么叫红黑树呢,是吧。

    • 性质二:根节点是黑色; 根节点总是黑色的。它不能为红。

    • 性质三:每个叶节点(NIL或空节点)是黑色;

    • 性质四:每个红色节点的两个子节点都是黑色的(也就是说不存在两个连续的红色节点); 就是连续的两个节点不能是连续的红色,连续的两个节点的意思就是父节点与子节点不能是连续的红色。

    • 性质五:从任一节点到其每个叶节点的所有路径都包含相同数目的黑色节点。从根节点到每一个NIL节点的路径中,都包含了相同数量的黑色节点。

     

     


    字典树

     

    trie,又称前缀树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。

     

     


    (3) 了解并查集吗?(低频)

    什么是合并查找问题呢?

     

    顾名思义,就是既有合并又有查找操作的问题。举个例子,有一群人,他们之间有若干好友关系。如果两个人有直接或者间接好友关系,那么我们就说他们在同一个朋友圈中,这里解释下,如果Alice是Bob好友的好友,或者好友的好友的好友等等,即通过若干好友可以认识,那么我们说Alice和Bob是间接好友。随着时间的变化,这群人中有可能会有新的朋友关系,这时候我们会对当中某些人是否在同一朋友圈进行询问。这就是一个典型的合并-查找操作问题,既包含了合并操作,又包含了查找操作。

     

    并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。

     

    并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。

     

    并查集也是使用树形结构实现。不过,不是二叉树。每个元素对应一个节点,每个组对应一棵树。在并查集中,哪个节点是哪个节点的父亲以及树的形状等信息无需多加关注,整体组成一个树形结构才是重要的。类似森林

     


    贪心算法和动态规划的区别

     

    贪心算法:局部最优,划分的每个子问题都最优,得到全局最优,但是不能保证是全局最优解,所以对于贪心算法来说,解是从上到下的,一步一步最优,直到最后。

     

    动态规划:将问题分解成重复的子问题,每次都寻找左右子问题解中最优的解,一步步得到全局的最优解.重复的子问题可以通过记录的方式,避免多次计算。所以对于动态规划来说,解是从小到上,从底层所有可能性中找到最优解,再一步步向上。

     

    https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode/

     

    分治法:和动态规划类似,将大问题分解成小问题,但是这些小问题是独立的,没有重复的问题。独立问题取得解,再合并成大问题的解。

     

     

    贪心算法的典型:

    • 哈夫曼树

     

    例子:比如钱币分为1元3元4元,要拿6元钱,贪心的话,先拿4,再拿两个1,一共3张钱;实际最优却是两张3元就够了。

     

    区分用动态规划还是贪心:找特例

     


    (8) Top K问题(可以采取的方法有哪些,各自优点?)

    1.将输入内容(假设用数组存放)进行完全排序,从中选出排在前K的元素即为所求。有了这个思路,我们可以选择相应的排序算法进行处理,目前来看快速排序,堆排序和归并排序都能达到O(nlogn)的时间复杂度。

     

    2.对输入内容进行部分排序,即只对前K大的元素进行排序(这K个元素即为所求)。此时我们可以选择冒泡排序或选择排序进行处理,即每次冒泡(选择)都能找到所求的一个元素。这类策略的时间复杂度是O(Kn)。

     

    3.对输入内容不进行排序,显而易见,这种策略将会有更好的性能开销。我们此时可以选择两种策略进行处理:

     

    用一个桶来装前k个数,桶里面可以按照最小堆来维护

     

    a)利用最小堆维护一个大小为K的数组,目前该小根堆中的元素是排名前K的数,其中根是最小的数。此后,每次从原数组中取一个元素与根进行比较,如大于根的元素,则将根元素替换并进行堆调整(下沉),即保证小根堆中的元素仍然是排名前K的数,且根元素仍然最小;否则不予处理,取下一个数组元素继续该过程。该算法的时间复杂度是O(nlogK),一般来说企业中都采用该策略处理top-K问题,因为该算法不需要一次将原数组中的内容全部加载到内存中,而这正是海量数据处理必然会面临的一个关卡。

     

    b)利用快速排序的分划函数找到分划位置K,则其前面的内容即为所求。该算法是一种非常有效的处理方式,时间复杂度是O(n)(证明可以参考算法导论书籍)。对于能一次加载到内存中的数组,该策略非常优秀。

     


    (9) Bitmap的使用,存储和插入方法

     

    BitMap从字面的意思

    很多人认为是位图,其实准确的来说,翻译成基于位的映射。

    在所有具有性能优化的数据结构中,大家使用最多的就是hash表,是的,在具有定位查找上具有O(1)的常量时间,多么的简洁优美。但是数据量大了,内存就不够了。

    当然也可以使用类似外排序来解决问题的,由于要走IO所以时间上又不行。

    所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。

    其实如果你知道计数排序的话(算法导论中有一节讲过),你就会发现这个和计数排序很像。

     

    BitMap应用:排序示例

     

    假设我们要对0-7内的5个元素(4,7,2,5,3)排序(这里假设这些元素没有重复)。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数,我们就只需要8个Bit(1Bytes),首先我们开辟1Byte的空间,将这些空间的所有Bit位都置为0

    然后遍历这5个元素,首先第一个元素是4,那么就把4对应的位置为1(可以这样操作 p+(i/8)|(0×01<<(i%8)) 当然了这里的操作涉及到Big-ending和Little-ending的情况,这里默认为Big-ending。不过计算机一般是小端存储的,如intel。小端的话就是将倒数第5位置1),因为是从零开始的,所以要把第五位置为一(如下图):

     

    然后再处理第二个元素7,将第八位置为1,,接着再处理第三个元素,一直到最后处理完所有的元素,将相应的位置为1,这时候的内存的Bit位的状态如下:

     

    然后我们现在遍历一遍Bit区域,将该位是一的位的编号输出(2,3,4,5,7),这样就达到了排序的目的。

     

    bitmap排序复杂度分析

    Bitmap排序需要的时间复杂度和空间复杂度依赖于数据中最大的数字。

    bitmap排序的时间复杂度不是O(N)的,而是取决于待排序数组中的最大值MAX,在实际应用上关系也不大,比如我开10个线程去读byte数组,那么复杂度为:O(Max/10)。也就是要是读取的,可以用多线程的方式去读取。时间复杂度方面也是O(Max/n),其中Max为byte[]数组的大小,n为线程大小。

    空间复杂度应该就是O(Max/8)bytes吧

     

    BitMap算法流程

    假设需要排序或者查找的最大数MAX=10000000(lz:这里MAX应该是最大的数而不是int数据的总数!),那么我们需要申请内存空间的大小为int a[1 + MAX/32]。

    其中:a[0]在内存中占32为可以对应十进制数0-31,依次类推:

    bitmap表为:

    a[0]--------->0-31

    a[1]--------->32-63

    a[2]--------->64-95

    a[3]--------->96-127

     

    我们要把一个整数N映射到Bit-Map中去,首先要确定把这个N Mapping到哪一个数组元素中去,即确定映射元素的index。我们用int类型的数组作为map的元素,这样我们就知道了一个元素能够表示的数字个数(这里是32)。于是N/32就可以知道我们需要映射的key了。所以余下来的那个N%32就是要映射到的位数。

     

    1.求十进制数对应在数组a中的下标:

    先由十进制数n转换为与32的余可转化为对应在数组a中的下标。

    如十进制数0-31,都应该对应在a[0]中,比如n=24,那么 n/32=0,则24对应在数组a中的下标为0。又比如n=60,那么n/32=1,则60对应在数组a中的下标为1,同理可以计算0-N在数组a中的下标。

    i = N>>K % 结果就是N/(2^K)

    Note: map的范围是[0, 原数组最大的数对应的2的整次方数-1]。

     

    2.求十进制数对应数组元素a[i]在0-31中的位m:

    十进制数0-31就对应0-31,而32-63则对应也是0-31,即给定一个数n可以通过模32求得对应0-31中的数。

    m = n & ((1 << K) - 1) %结果就是n%(2^K)

     

    3.利用移位0-31使得对应第m个bit位为1

    如a[i]的第m位置1:a[i] = a[i] | (1<<m)

    如:将当前4对应的bit位置1的话,只需要1左移4位与B[0] | 即可。

     

    BitMap算法评价

    优点:

    1. 运算效率高,不进行比较和移位;

    2. 占用内存少,比如最大的数MAX=10000000;只需占用内存为MAX/8=1250000Byte=1.25M。

    3.

    缺点:

    1. 所有的数据不能重复,即不可对重复的数据进行排序。(少量重复数据查找还是可以的,用2-bitmap)。

    2. 当数据类似(1,1000,10万)只有3个数据的时候,用bitmap时间复杂度和空间复杂度相当大,只有当数据比较密集时才有优势。

     


    为什么要使用红黑树,B树和B+树

     

    B/B+树是为了磁盘或其它存储设备而设计的一种平衡多路查找树(相对于二叉,B树每个内节点有多个分支),与红黑树相比,在相同的的节点的情况下,一颗B/B+树的高度远远小于红黑树的高度(在下面B/B+树的性能分析中会提到).B/B+树上操作的时间通常由存取磁盘的时间和CPU计算时间这两部分构成,而CPU的速度非常快,所以B树的操作效率取决于访问磁盘的次数,关键字总数相同的情况下B树的高度越小,磁盘I/O所花的时间越少.

     

    数据库索引采用B+树的主要原因是:B树在提高了IO性能的同时并没有解决元素遍历的效率低下的问题,正是为了解决这个问题,B+树应用而生.B+树只需要去遍历叶子节点就可以实现整棵树的遍历.而且在数据库中基于范围的查询是非常频繁的,而B树不支持这样的操作(或者说效率太低)。


    https://baijiahao.baidu.com/s?id=1651803445417553212&wfr=spider&for=pc

     

    一、并查集原理

    话说在江湖上有很多门派,这些门派相互争夺武林霸主。毕竟是江湖中人,两个人见面一言不合就开干。但是打归打,总是要判断一下是不是自己人,免得误伤。

    于是乎,分了各种各样的门派,比如说张无忌和杨过俩人要打架,就先看看是不是同一门派的,不是的话那就再开干。要是张无忌和杨过觉得俩人合得来,那就合并门派。

    而且规定了,每一个门派都有一个掌门人,比如武当派就是张三丰。华山派就是岳不群等等。

     

    现在我们把目光转到并查集上。

    (1)张无忌和杨过打架之前,先判断是否是同一门派,这就涉及到了并查集的查找操作。

    (2)张无忌和杨过觉得俩人合得来,那就合并门派,这就涉及到了并查集的合并操作。

    (3)每一个门派都有一个掌门人,这涉及到了并查集的存储方式。掌门人代表了这个门派的根节点。

    现在我们从这个例子的思想开始认识一下并查集。

     

     

     

     

     

     

    展开全文
  • 算法与数据结构面试更新地址:算法与数据结构面试 算法与数据结构面试 加油! 文章目录算法与数据结构面试考查数据结构本身什么是数据结构为什么要使用数据结构常见的数据结构顺序结构和链式结构的区别?...

    算法与数据结构面试题更新地址:算法与数据结构面试题

    算法与数据结构面试题


    加油!


    文章目录


    考查数据结构本身

    什么是数据结构

    简单地说,数据结构是以某种特定的布局方式存储数据的容器。这种“布局方式”决定了数据结构对于某些操作是高效的,而对于其他操作则是低效的。首先我们需要理解各种数据结构,才能在处理实际问题时选取最合适的数据结构。

    为什么要使用数据结构

    数据是计算机科学当中最关键的实体,而数据结构则可以将数据以某种组织形式存储,因此,数据结构的价值不言而喻。

    无论你以何种方式解决何种问题,你都需要处理数据——无论是涉及员工薪水、股票价格、购物清单,还是只是简单的电话簿问题。

    数据需要根据不同的场景,按照特定的格式进行存储。有很多数据结构能够满足以不同格式存储数据的需求。

    常见的数据结构

    首先列出一些最常见的数据结构,我们将逐一说明:

    • 数组

      • 数组是最简单、也是使用最广泛的数据结构。栈、队列等其他数据结构均由数组演变而来。
      • 每个数据元素都关联一个正数值,我们称之为索引,它表明数组中每个元素所在的位置。大部分语言将初始索引定义为零。
      • 以下是数组的两种类型:
        • 一维数组
        • 多维数组(数组的数组)
      • 数组的基本操作:
        • Insert——在指定索引位置插入一个元素
        • Get——返回指定索引位置的元素
        • Delete——删除指定索引位置的元素
        • Size——得到数组所有元素的数量
      • 后进先出
      • 栈的基本操作
        • Push——在顶部插入一个元素
        • Pop——返回并移除栈顶元素
        • isEmpty——如果栈为空,则返回true
        • Top——返回顶部元素,但并不移除它
    • 队列

      • 与栈相似,队列是另一种顺序存储元素的线性数据结构。栈与队列的最大差别在于栈是LIFO(后进先出),而队列是FIFO,即先进先出。
      • 队列的基本操作
        • Enqueue() —— 在队列尾部插入元素
        • Dequeue() ——移除队列头部的元素
        • isEmpty()——如果队列为空,则返回true
        • Top() ——返回队列的第一个元素
    • 链表

      • 链表是另一个重要的线性数据结构,乍一看可能有点像数组,但在内存分配、内部结构以及数据插入和删除的基本操作方面均有所不同。
      • 链表就像一个节点链,其中每个节点包含着数据和指向后续节点的指针。 链表还包含一个头指针,它指向链表的第一个元素,但当列表为空时,它指向null或无具体内容。
      • 链表一般用于实现文件系统、哈希表和邻接表。
      • 链表包括以下类型:
        • 单链表(单向)
        • 双向链表(双向)
      • 链表的基本操作
        • InsertAtEnd - 在链表的末尾插入指定元素
        • InsertAtHead - 在链接列表的开头/头部插入指定元素
        • Delete  - 从链接列表中删除指定元素
        • DeleteAtHead - 删除链接列表的第一个元素
        • Search  - 从链表中返回指定元素
        • isEmpty - 如果链表为空,则返回true
      • 树形结构是一种层级式的数据结构,由顶点(节点)和连接它们的边组成。 树类似于图,但区分树和图的重要特征是树中不存在环路。
      • 树形结构被广泛应用于人工智能和复杂算法,它可以提供解决问题的有效存储机制。
      • 树的基本术语
        • Root - 根节点
        • Parent - 父节点
        • Child - 子节点
        • Leaf - 叶子节点
        • Sibling - 兄弟节点
      • 树型结构的基本类型
        • N元树
        • 平衡树
        • 二叉树
        • 二叉搜索树
        • AVL树
        • 红黑树
        • 2-3树
      • 其中,二叉树和二叉搜索树是最常用的树
      • 图是一组以网络形式相互连接的节点。节点也称为顶点。 一对节点(x,y)称为边(edge),表示顶点x连接到顶点y。边可以包含权重/成本,显示从顶点x到y所需的成本。
      • 图的类型
        • 无向图
        • 有向图
      • 在程序语言中,图可以用两种形式表示:
        • 邻接矩阵
        • 邻接表
      • 常见图遍历算法
        • 广度优先搜索
        • 深度优先搜索
    • 字典树(Trie)(这是一种高效的树形结构,但值得单独说明)

      • 字典树,也称为“前缀树”,是一种特殊的树状数据结构,对于解决字符串相关问题非常有效。它能够提供快速检索,主要用于搜索字典中的单词,在搜索引擎中自动提供建议,甚至被用于IP的路由。
    • 散列表(哈希表)

      • 哈希法(Hashing)是一个用于唯一标识对象并将每个对象存储在一些预先计算的唯一索引(称为“键(key)”)中的过程。因此,对象以键值对的形式存储,这些键值对的集合被称为“字典”。可以使用键搜索每个对象。基于哈希法有很多不同的数据结构,但最常用的数据结构是哈希表。
      • 哈希表通常使用数组实现。
      • 散列数据结构的性能取决于以下三个因素:
        • 哈希函数
        • 哈希表的大小
        • 碰撞处理方法

    !> 简单谈谈常见的数据结构

    a、数组:顺序存储,随机访问 链表:链表存储,顺序访问

    b、栈,分为栈顶和栈底,遵循先进后出原则

    c、队列 ,一个线性表,像排队一样,受约束控制,遵循先进先出原则

    d、树:二叉树、平衡二叉树、大顶堆,小顶堆等

    e、图:最短路径,关键路径

    顺序结构和链式结构的区别?

    顺序结构是指内存连续的存储单元进行存储,而链式结构是指 内存不连续的结构,通过一个节点指向另外一个节点的地址。

    数据结构的三要素

    • 逻辑结构:探讨数据元素之间的逻辑关系
      • 集合:各个元素同属于一个集合,别无其他关系
      • 线性结构:
        • 数据元素之间是一对一的关系
        • 除了第一个元素,所有元素都有唯一前驱
        • 除了最后一个元素,所有元素都有唯一后继
      • 树形结构:数据元素之间是一对多的关系
      • 图状结构(网状结构):数据元素之间是多对多的关系
    • 物理结构(存储结构):探讨如何用计算机表示数据元素的逻辑关系?
      • 顺序存储
      • 链式存储
      • 索引存储
      • 散列存储
        • 根据元素的关键字直接计算出该元素的存储地址,又称为哈希(Hash)存储
    • 数据的运算

    复杂度是什么 ⭐

    复杂度包括时间复杂度和空间复杂度,用来评价一个算法的好坏。

    考查线性表

    线性表查找有那几类?

    直接查找和有序表的二分查找。

    单链表和顺序表的对比

    (1)存储方式:顺序表用一组连续的存储单元依次存储线性表的数据元素;而单链表用一组任意的存储单元存放线性表的数据元素。

    (2)时间性能:采用循序存储结构时查找的时间复杂度为O(1),插入和删除需要移动平均一半的数据元素,时间复杂度为O(n)。采用单链表存储结构的查找时间复杂度为O(n),插入和删除不需要移动元素,时间复杂度仅为O(1)。

    (3)空间性能:采用顺序存储结构时需要预先分配存储空间,分配空间过大会造成浪费,过小会造成问题。采用单链表存储结构时,可根据需要进行临时分配,不需要估计问题的规模大小,只要内存够就可以分配,还可以用于一些特殊情况,如一元多项的表示。

    顺序结构和链式结构的区别 ⭐

    顺序结构是指内存连续的存储单元进行存储,而链式结构是指内存不连续的结构,通过一个节点指向另外一个节点的地址。

    考查数组

    寻找数组中第二小的元素

    找到数组中第一个不重复出现的整数

    合并两个有序数组

    重新排列数组中的正值和负值

    数组和链表的区别 ⭐

    从逻辑结构上来看,数组必须实现定于固定的长度,不能适应数据动态增减的情况,即数组的大小一旦定义就不能改变。当数据增加是,可能超过原先定义的元素的个数;当数据减少时,造成内存浪费;链表动态进行存储分配,可以适应数据动态地增减的情况,且可以方便地插入、删除数据项。

    从内存存储的角度看;数组从栈中分配空间(用new则在堆上创建),对程序员方便快速,但是自由度小;链表从堆中分配空间,自由度大但是申请管理比较麻烦。

    从访问方式类看,数组在内存中是连续的存储,因此可以利用下标索引进行访问;链表是链式存储结构,在访问元素时候只能够通过线性方式由前到后顺序的访问,所以访问效率比数组要低。

    考查栈

    使用栈计算后缀表达式

    对栈的元素进行排序

    判断表达式是否括号平衡

    栈和队列的区别 ⭐

    栈是先进后出的特殊线性表,队列是先进先出的线性表。

    • 栈的插入和删除操作都是在一端进行的,而队列的操作却是在两端进行的。
    • 栈是先进后出的特殊线性表,队列是先进先出的线性表
    • 栈只允许在表尾一端进行插入和删除,队列只允许在表尾一端进行插入,在表头一端进行删除。

    换种方式询问:栈和队列的不同,以及他们的相应存储方式。(这个后面一问有点难度,要回答在不同方式下的存储)

    栈的存储方式 ⭐

    栈也有两种存储方法:一是顺序栈;二是链式栈。栈的顺序存储结构是利用一组地址连续的存储单元依次存储自栈底到栈顶的数据元素,同时附设指针 top 指示栈顶元素的位置。由于栈的操作是线性表操作的特例,相对而言,链式栈的操作更易于实现。

    栈和堆的区别 ⭐

    栈区:由编辑器自动分配释放,存放函数的参数值,局部变量的值等(基本类型值)。

    堆区:由程序员分配释放,若程序员不释放,程序结束时可能有 OS 回收(引用类型值)。

    栈(数据结构):一种先进后出的数据结构。

    堆(数据结构):堆可以被看成是一棵树,如:堆排序。

    用两个栈实现一个队列的功能

    算法思路:(时间复杂度为 O(1))

    设 2 个栈为 A、B,一开始均为空

    入队:将新元素 push 入栈 A

    出队:

    (1)判断栈 B 是否为空

    (2)如果不为空,则将栈 A 中所有元素依次 pop 出并 push 给栈 B

    (3)将栈 B 的栈顶元素 pop 出

    Heap 和 Stack 的区别

    Heap 是堆,Stack 是栈

    1 Stack 的空间由操作系统自动分配和释放,Heap 上的空间手动分配和释放

    2 Stack 空间有限,Heap 是很大的自由存储区

    3 C 中的 malloc 函数分配的内存空间即在堆上,C++ 中对应的是 new 操作符

    考查队列

    使用队列表示栈

    对队列的前k个元素倒序

    使用队列生成从1到n的二进制数

    队列的存储方式 ⭐

    队列也有两种存储方法:一是顺序队列;二是链式队列,拿链式结构来实现队列,只要将头节点当作队头,尾结点当作队尾,入队时尾节点后移(next),出队时头节点后移(next)

    考查链表

    头节点的作用是什么 ⭐

    头节点是指向初始地址的一个节点,它本身数据段没有内容,通过它可以标识这个链表。

    反转链表

    检测链表中的循环

    返回链表倒数第N个节点

    删除链表中的重复项

    考查图

    图的存储 ⭐

    邻接矩阵和邻接表,是多对多的关系,分为有向图和无向图。

    实现广度和深度优先搜索

    深度优先和广度优先的对比

    深度优先搜索(回溯法)
    算法思路
    深度优先搜索(DFS,Depth-First Search)是搜索的手段之一
    它从某个状态开始,不断地转移状态直到无法转移,然后回退到前一步状态,继续转移到其他状态,如此不断重复,直到找到最终的解.根据深度优先搜索的特点,采用递归函数(隐式地利用了栈进行计算)实现比较简单.

    算法效率
    深度优先搜索从最开始的状态出发,遍历所有可以到达的状态.由此可以对所有的状态进行操作,或列举出所有的状态.作为搜索算法的一种,DFS对于寻找一个解的NP(包括NPC)问题作用很大.

    但是,搜索算法毕竟是时间复杂度是O(n!)的阶乘级算法,它的效率比较低,在数据规模变大时,这种算法就显得力不从心了.关于深度优先搜索的效率问题,有多种解决方法.最具有通用性的是**剪枝(prunning),**也就是去除没有用的搜索分支.有可行性剪枝和最优性剪枝两种.此外,对于很多问题,可以把搜索与动态规划(DP,dynamic programming)、完备匹配(匈牙利算法)等高效算法结合.

    2.宽度优先搜索(分支限界法)
    算法思路
    宽度优先搜索(BFS,Breadth-First Search)也是搜索的手段之一.他与深度优先搜索类似,从某个状态出发搜索所有可以到达的状态.根据宽度优先搜索的特点,采用队列实现比较简单.

    算法效率
    与深度优先不同之处在与搜索的顺序,宽度优先搜索总是先搜索距离初始状态近的状态.也就是说,它是按照开始状态->只需1次转移就可以到达的所有状态->只需2次转移就可以到达的所有状态->…这样的顺序进行搜索.对于同一个状态,宽度优先搜索只经过一次,因此复杂度为

    O(状态数*转移的方式).很容易地用来求最短路径、最少操作之类问题的答案.

    广度搜索的判断重复如果直接判断十分耗时,我们一般借助哈希表来优化时间复杂度.

    3.Death-Breadth总结
    宽度优先搜索与深度优先搜索一样,都会生成所有能够遍历到的状态,因此需要对所有状态进行处理时使用宽度优先也是可以的.但是递归函数可以很简短地编写,而且状态的管理也更简单,所以大多数情况下还是用深度优先搜索实现.反之,在求取最短路时深度优先搜索需要反复经过同样的状态,所以还是使用宽度优先搜索比较好.

    宽度优先搜索会把状态逐个加入队列,因此通常需要与状态数成正比的内存空间.反之,深度优先搜索是与最大的递归深度成正比的.一般与状态数相比,递归的深度并不会太大,所以可以认为深度优先搜索更加节省内存.

    检查图是否为树

    计算图的边数

    找到两个顶点之间的最短路径

    邻接矩阵与邻接表

    邻接矩阵表示法:在一个一维数组中存储所有的点,在一个二维数组中存储顶点之间的边的权值

    邻接表表示法:图中顶点用一个一维数组存储,图中每个顶点vi的所有邻接点构成单链表

    对比

    1)在邻接矩阵表示中,无向图的邻接矩阵是对称的。矩阵中第 i 行或 第 i 列有效元素个数之和就是顶点的度。

    在有向图中 第 i 行有效元素个数之和是顶点的出度,第 i 列有效元素个数之和是顶点的入度。

    2)在邻接表的表示中,无向图的同一条边在邻接表中存储的两次。如果想要知道顶点的度,只需要求出所对应链表的结点个数即可。

    有向图中每条边在邻接表中只出现一次,求顶点的出度只需要遍历所对应链表即可。求入度则需要遍历其他顶点的链表。

    3)邻接矩阵与邻接表优缺点:

    邻接矩阵的优点是可以快速判断两个顶点之间是否存在边,可以快速添加边或者删除边。而其缺点是如果顶点之间的边比较少,会比较浪费空间。因为是一个 n∗n 的矩阵。

    而邻接表的优点是节省空间,只存储实际存在的边。其缺点是关注顶点的度时,就可能需要遍历一个链表。

    考查树

    介绍以下各种树 ⭐

    树,二叉树:有左右子树的区分和度不超过2.

    二叉排序树:左子树均小于根,根均小于右节点。。

    线索二叉树:设置两个标识标记左右指针指向的是孩子还是前躯节点。

    平衡二叉树:左右子树高度差绝对值小于等于1。

    哈夫曼树:压缩用的。权值大小排列。

    完全二叉树:只能从右边为空。

    度为 2 的树和二叉树的区别 ⭐

    二叉树有左右子树的定义。

    树的存储结构 ⭐

    孩子链存储结构和双亲存储结构。

    树的遍历 ⭐

    先序中序后序三种。递归实现。

    求二叉树的高度

    在二叉搜索树中查找第k个最大值

    查找与根节点距离k的节点

    在二叉树中查找给定节点的祖先节点

    开销量,为何使用二叉树

    计算机科学中,二叉树是每个结点最多有两个子树的有序树。通常根的子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用作二叉查找树二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在出度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。

    文件系统和数据库系统一般都采用树(特别是B树)的数据结构数据,主要为排序和检索的效率。二叉树是一种最基本最典型的排序树,用于教学和研究树的特性,本身很少在实际中进行应用,因为缺点太明显了(看看教科书怎么说的)。就像冒泡排序一样,虽然因为效率问题并不实用,单不失一种教学例子的好手段。

    B树和B+树的区别,以一个m阶树为例

    关键字的数量不同:B+树中分支结点有m个关键字,其叶子结点也有m个,其关键字只是起到了一个索引的作用,但是B树虽然也有m个子结点,但是其只拥有m-1个关键字。

    存储的位置不同:B+树中的数据都存储在叶子结点上,也就是其所有叶子结点的数据组合起来就是完整的数据,但是B树的数据存储在每一个结点中,并不仅仅存储在叶子结点上。

    分支结点的构造不同:B+树的分支结点仅仅存储着关键字信息和儿子的指针(这里的指针指的是磁盘块的偏移量),也就是说内部结点仅仅包含着索引信息。

    查询不同:B树在找到具体的数值以后,则结束,而B+树则需要通过索引找到叶子结点中的数据才结束,也就是说B+树的搜索过程中走了一条从根结点到叶子结点的路径。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XLajxvI3-1591090641255)(…/images/20200318152614777.png)]

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EAg39nYG-1591090641260)(…/images/20200318152632753.png)]

    请比较最小生成树的算法(普里姆算法,克鲁斯卡尔算法)的异同

    最小生成树:
    最小生成树来自于无向网。
    无向图在边上加上权值就成了无向网。
    一个无向图可以有多种不同姿态连接的生成树。
    最小生成树就是–各边上权值之和最小的生成树。

    普里姆算法(Prim)和克鲁斯卡尔(Kruskal)算法

    普里姆算法的基本思想:(简单的说就是一直加点)
    取图中任意一个顶点 v 作为生成树的根,之后往生成树上添加新的顶点 w。添加顶点w的条件为:w 和已在生成树上的顶点v 之间必定存在一条边,并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点,直至生成树上含有 n-1 个顶点为止。

    克鲁斯卡尔算法的基本思想:(简单的说就是找不围成圈的最小的边)

    考虑问题的出发点: 为使生成树上边的权值之和达到最小,则应使生成树中每一条边的权值尽可能地小。

    具体做法: 先构造一个只含 n 个顶点的子图 SG,然后从权值最小的边开始,若它的添加不使SG 中产生回路,则在 SG 上加上这条边,如此重复,直至加上 n-1 条边为止。

    什么时候最小生成树唯一?

    当带权连通图的任意一个环中所包含的权值均不相同

    Dijkstra 算法与 Prim 算法的区别

    1.prim算法过程:

     prim算法是最小生成树算法,它运用的是贪心原理,设置两个点集合,
     一个集合为要求的生成树的点集合A,另一个集合为未加入生成树的点B。
    

    它的具体实现过程是:
    (1):所有的点都在集合B中,A集合为空。(memset(visited,0,sizeof(visited))
    (2):任意以一个点为开始,把这个初始点加入集合A中,从集合B中减去这个点(visited[1]=1)。寻找与它相邻的点中路径最短的点,如后把这个点也加入集合A中,从集合B中减去这个点(visited[pos]=1)。
    (3):更新未被访问的节点的dist[]值。
    (4):重复上述过程。一直到所有的点都在A集合中结束。

    2.dijkstra算法过程:

    (1)初始时,S只包含源点v,即S=v。U包含除v外的其他顶点,U中顶点u距离为边上的权(若v与u有边)或(若u不是v的出边邻接点)。
    (2)从U中选取一个距离v最小的顶点k,把k,加入S中(该选定的距离就是v到k的最短路径长度)。
    (3)以k为新考虑的中间点,修改U中各顶点的距离;若从源点v到顶点u(u U)的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值的顶点k的距离加上边上的权。
    (4)重复步骤(2)和(3)直到所有顶点都包含在S中。

    3.小总结

    1:Prim是计算最小生成树的算法,Dijkstra是计算最短路径的算法,
    2、都是使用贪婪和线性规划,每一步都是选择权值/花费最小的边。
    贪婪:一个局部最有解也是全局最优解;
    线性规划:主问题包含n个子问题,而且其中有重叠的子问题。

    什么是平衡二叉树

    左右子树都是平衡二叉树,且左右子树的深度差值的绝对值不大于 1

    考查字典树

    计算字典树中的总单词数

    打印存储在字典树中的所有单词

    使用字典树对数组的元素进行排序

    使用字典树从字典中形成单词

    构建T9字典(字典树+ DFS )

    考查算法

    请说出以下算法的时间复杂度

    冒泡排序法 插入排序法 堆排序法 二叉树排序法

    O(n^2) O(n^2) O(nlog2n) 最差 O(n2) 平均 O(nlog2n)

    快速排序法 希尔排序法

    最差 O(n^2) 平均 O(nlog2n) O(nlog n) 不稳定

    排序算法有哪些 ⭐

    或者问:C语言总共有多少种排序法

    • 排序算法有很多,每种算法有不同的时间和空间复杂度,效率也有差别,那么针对使用上也有不同的场合。原则上说,数据结构是一门领域,跟语言没有绝对的联系,很多时候同样的算法可以用很多种语言实现。
    • 下面罗列一些常见的算法:插入排序,冒泡排序,选择排序,快速排序,堆排序,归并排序,基数排序,希尔排序等。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-01dv9SdE-1591090641277)(…/images/20190315143432196.png)]

    插入排序有直接插入和折半插入。都是在有序表里插入进去的。

    交换排序:冒泡,快速:以一个数字划分两个区域,然后分别对两个区域继续划分,直到区间为一。注意快排是不稳定。

    选择排序:简单的选择排序,堆排序

    归并排序:将两个有序表归并到一个有序表。将两个有序表放到一起进行各个比较,比较完之后放回原来数组内。

    时间复杂度:

    (1)平方阶(O(n2))排序
      各类简单排序:直接插入、直接选择和冒泡排序;
    (2)线性对数阶(O(nlog2n))排序
      快速排序、堆排序和归并排序;
    (3)O(n1+§))排序,§是介于0和1之间的常数。

    ​ 希尔排序
    (4)线性阶(O(n))排序
      基数排序,此外还有桶、箱排序。

    稳定性:

    排序算法的稳定性:若待排序的序列中,存在多个具有相同关键字的记录,经过排序,这些记录的相对次序保持不变,则称该算法是稳定的;若经排序后,记录的相对次序发生了改变,则称该算法是不稳定的。

    稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序

    不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序

    什么是稳定的算法 ⭐

    不乱动已经排序好的数字,这样算法稳定一些。

    选择排序算法的准则

    一般而言,需要考虑的因素有以下四点:

    设待排序元素的个数为n.

    **1)**当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序序。

    **2)**当n较大,内存空间允许,且要求稳定性:归并排序

    **3)**当n较小,可采用直接插入或直接选择排序。

    直接插入排序:当元素分布有序,直接插入排序将大大减少比较次数和移动记录的次数。

    直接选择排序 :元素分布有序,如果不要求稳定性,选择直接选择排序

    **5)**一般不使用或不直接使用传统的冒泡排序。

    6**)**基数排序
    它是一种稳定的排序算法,但有一定的局限性:
      1、关键字可分解。
      2、记录的关键字位数较少,如果密集更好
      3、如果是数字时,最好是无符号的

    简述快速排序过程

    1)选择一个基准元素,通常选择第一个元素或者最后一个元素,

    2)通过一趟排序将待排序的记录分割成独立的两部分,其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值比基准值大。

    3)此时基准元素在其排好序后的正确位置

    4)然后分别对这两部分记录用同样的方法继续进行排序,直到整个序列有序。

    快速排序的改进

    只对长度大于k的子序列递归调用快速排序,让原序列基本有序,然后再对整个基本有序序列用插入排序算法排序。实践证明,改进后的算法时间复杂度有所降低,且当k取值为 8 左右时,改进算法的性能最佳。

    选择基准元的方式

    对于分治算法,当每次划分时,算法若都能分成两个等长的子序列时,那么分治算法效率会达到最大。也就是说,基准的选择是很重要的。选择基准的方式决定了两个分割后两个子序列的长度,进而对整个算法的效率产生决定性影响。最理想的方法是,选择的基准恰好能把待排序序列分成两个等长的子序列。

    方法1 固定基准元

    如果输入序列是随机的,处理时间是可以接受的。如果数组已经有序时,此时的分割就是一个非常不好的分割。

    方法2 随机基准元

    这是一种相对安全的策略。由于基准元的位置是随机的,那么产生的分割也不会总是会出现劣质的分割。在整个数组数字全相等时,仍然是最坏情况,时间复杂度是O(n^2)

    实际上,随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。

    方法3 三数取中

    引入的原因:虽然随机选取基准时,减少出现不好分割的几率,但是还是最坏情况下还是O(n^2),要缓解这种情况,就引入了三数取中选取基准。

    分析:最佳的划分是将待排序的序列分成等长的子序列,最佳的状态我们可以使用序列的中间的值,也就是第N/2个数。可是,这很难算出来,并且会明显减慢快速排序的速度。这样的中值的估计可以通过随机选取三个元素并用它们的中值作为基准元而得到。事实上,随机性并没有多大的帮助,因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为基准元。

    冒泡排序算法的改进

    1.设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。

    2.传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

    用循环比递归效率高吗?

    递归和循环两者完全可以互换。不能完全决定性地说循环地效率比递归的效率高。

    递归算法

    优点:代码简洁、清晰,并且容易验证正确性。

    缺点:它的运行需要较多次数的函数调用,如果调用层数比较深,需要增加额外的堆栈处理(还有可能出现堆栈溢出的情况),比如参数传递需要压栈等操作,会对执行效率有一定影响。
    但是,对于某些问题,如果不使用递归,那将是极端难看的代码。在编译器优化后,对于多次调用的函数处理会有非常好的效率优化,效率未必低于循环。

    循环算法

    优点:速度快,结构简单。

    缺点:并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话,最好使用循环。

    请简述 KMP 算法

    在一个字符串中查找是否包含目标的匹配字符串

    其主要思想是每趟比较过程让子串先后滑动一个合适的位置。

    当发生不匹配的情况时,不是右移一位,而是移动(当前匹配的长度– 当前匹配子串的部分匹配值)位。

    考查散列表

    哈希表是什么,怎么理解哈希表

    散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数

    解决哈希冲突的方法

    哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。

    1) 线性探测法

    2) 平方探测法

    3) 伪随机序列法

    4) 拉链法

    在数组中查找对称键值对

    追踪遍历的完整路径

    查找数组是否是另一个数组的子集

    检查给定的数组是否不相交

    展开全文
  • C语言数据结构应用

    2019-12-12 21:36:04
    数据结构应用整理了一下数据结构的应用,考试比较常见的,都是应用,没有代码。我只是整理了一下其他博主的文章,嗯嗯嗯,方便大家查找,使用,感谢各位博主的文章,我自己的博客正在搭建,还需要一段时间。1....
  • 数据结构教案 PAGE 5 习题一数据线性结构 授课时间 年 月 日 授课班级 说明 教学方法 启发 教学准备 一主要知识点 第一章主要知识点 1.1 数据结构课程研究的内容 数据结构是一门研究非数值计算的程序设计问题中...
  • 7.数据结构 142 7.1 TRIE 142 7.2 线段树 147 7.3 并查集 151 7.4 树状数组 152 7.5 点树 154 7.6 STL 156 7.7 离散化 157 8.图论 158 8.0 2-SAT 158 8.2 寻找Euler回路 163 8.3 拓扑排序 163 8.4 差分约束系统 164 ...
  • 数据结构1800.docx

    2020-07-09 00:39:37
    数据结构1800 可修改 可打印 数据结构1800例题与答案 第一章 绪 论 一、选择(每小2分) 1.算法的计算量的大小称为计算的( B )。  A.效率 B.复杂性 C.现实性 D.难度 2.算法的时间复杂度取决于(C...
  • 数据结构课程设计 排序算法演示系统 1 2020 年 4 月 19 日 计算机学院 数据结构课程设计 数据结构排序算法演示系统 班 级 姓 名 学 号 同组人姓名 起 迄 日 期: 课程设计地点 : 指导教师 评阅意见 成绩评定 ...
  • 武汉理工大学数据结构课程设计 PAGE 2 课程设计任务书 学生姓名 专业班级 指导教师 工作单位 计算机科学系 目: 拓扑排序 初始条件 1采用邻接表作为有向图的存储结构 2给出所有可能的拓扑序列 3测试用例见严蔚敏...
  • 数据结构复习 简答 抽象数据类型是如何定义的写出一个 ADT的描述 数据的存储结构可用哪四种基本的存储方法得到 简述单链表的概念 画出在单链表上插入和删除结点的示意图 试比较顺序表和链表的优缺点 二叉树是...
  • 数据结构与算法 题库

    2010-03-04 21:59:11
    待处理数据的初态 C. A和B 3.计算机算法指的是(1),它必须具备(2) 这三个特性。 (1) A.计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A.可执行性、可移植性、可扩充性 B. 可执行性、确定性、...
  • 找工作知识储备(3)---从头说12种排序算法:原理、图解、动画视频演示、代码以及笔试面试题目中的应用(该博主博客很多面试数据结构与算法方面的干货!推荐!) 找工作笔试面试那些事儿(15)---互联网公司面试的零零...
  • 数据结构复习三.doc

    2020-10-12 01:41:50
    PAGE / NUMPAGES 数据结构复习三 一单项选择 (1)计算机算法指的是( ) A)计算方法 B)排序方法 C)解决某一问题的有限运算序列 D)调度方法 (2)某个向量第一元素的存储地址为100每个元素的长度为2则第五个元素 地址...
  • 网页 资讯 视频 图片 知道 文库 贴吧 采购 地图 | 百度首页 登录 VIP新客立...百度文库 专业资料 IT/计算机 课 程 设 计 课 程 设 计 课程数据结构 课程数据结构 排序算法比较 排序算法比较 专业班级 专业班
  • 数据结构课程设计 排序算法演示系统 1 2020 年 4 月 19 日 计算机学院 数据结构课程设计 数据结构排序算法演示系统 班 级 姓 名 学 号 同组人姓名 起 迄 日 期: 课程设计地点 : 指导教师 评阅意见 成绩评定 ...
  • 数据结构试题库答案 数据结构试题及答案 一单项选择 (1) 一个算法应该是 A) 程序 的描述 C) 要满足五个基本属性 (2) 算法指的是 A) 计算机程序 计算方法 C) 排序算法 有限运算序列 B) 问题求解步骤 D)A和C B) 解决...
  • 数据结构排序算法作业

    千次阅读 2019-05-03 14:48:24
    目录一、单选题二、简答题三、计算题 一、单选题 1、内部排序方法的稳定性是指( B )。 A、排序算法不允许有相同的关键字记录 B、排序算法允许有相同的关键字记录,排序前后相同关键字记录的相对位置不变 C、平均时间...
  • 数据结构面试

    2020-01-11 10:49:57
    如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。 2. 金字塔最小路径之和: 给定一个金字塔形状的二维数组,找出自顶向下的最小路径和。每一步只能移动到下一行...
  • 根据人口普查结果,知道目前淄博市大约500万人口,你的任务是帮助人口普查办公室按年龄递增的顺序输出每个年龄有多少人,其中不满1周岁的按0岁计算,1到2周岁的按1岁计算,依次类推,大于等于100岁的老人全部按100岁...
  • 数据结构面试常见的数据结构一. 数组1.寻找数组中第二大的元素2.寻找数组中不重复出现的整数3.实现数组中负数在左,正数在右二. 栈1.用栈计算后缀表达式2.对栈数据进行排序2.用栈来判断括号匹配问题三. 队列 常见...
  • 5.4.一维数组的逻辑结构是线性结构,存储结构是顺序存储结构;对二维或多维数组,分别按行优先和列优先两种不同的存储方式。7.4.在有向图的邻接矩阵表示中,计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的...
  • 数据结构 1800

    热门讨论 2012-12-27 16:52:03
    数据结构 1800》 第一章 绪论 一、选择 1. 算法的计算量的大小称为计算的(B )。【北京邮电大学2000 二、3 (20/8分)】 A.效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于(C )...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 549
精华内容 219
关键字:

数据结构排序计算题

数据结构 订阅