Skip to main content

第八章 内排序上

问题:排序稳定性的意义

王天明答:保持第一关键字相同的数据排序前后顺序不变,若不稳定的排序要做到这一点,则需要增加第二个关键字。

问题:快排的另一种写法

王天明答:两个指针从序列的两端向中扫描,遇到两个需要交换的记录做一次交换。

问题:堆排序有什么优点?

邹良川答:稳定且快速;在只需得到最大或最小的一部分元素时有优势(部分排序)

问题:快速排序轴值选择的标准?

邹良川答:尽量将区间划分为相近的两半

问题:冒泡排序和直接选择排序哪个更优?

郭秭含答:冒泡排序和直接选择排序从时间复杂度上来讲是一样的,都是O(n^2)的排序算法,但是因为冒泡排序是每次交换相邻两个,所以在常数上可能要稍微大一点。冒泡排序是稳定的,直接选择排序是不稳定的。

问题:输入2个整数NK,给定N个整数,在O(n)的时间内找出第K小的数

郭秭含答:用一种类似于快速排序的方法,快排每次都会把区间分成左右两半,左边的每个数会小于右边的每个数,这样就可以用K和左边数集的大小进行比较。如果K<sizeL,那么要找的数一定在左边,右边就不用管了;如果K>sizeL,那么要找的数一定在右边,此时K-=sizeL,再递归到右边去找。因为快速排序的复杂度不是稳定的O(nlogn)的,所以这个题的复杂度也不是稳定的O(n)的,只能说均摊是O(n)的。而且为了防止被特殊数据卡,可以在一开始打乱顺序。

问题:bellman-ford 为什么最多只需要迭代 n-1 次就可以求出最短路?

答:因为考虑 S 为最短路,S 在有 n 个顶点的图中,因为不能有回路,所以最多只有 n-1

条边,每次迭代中,S 中的边(因为是最短的)至少会出现一条,于是经过 n-1 次后就会出现 n-1 条边,S 就计算出来了。如果最短路的 S 的边少于 n-1 条(很多时候都是这样的),那么循环就会提前结束。

问题:为何排序需要考虑“正序”与“逆序”序列?

答:因为考虑到这两种情况之后就可以节省掉一些运算,直接得到结果。而且有些情况下逆序(或者正序)会导致算法几乎失效,比如取首元素为 pivot 的快排。

问题:快速排序为什么是不稳定的

罗浩然答:比如对于一个序列 3 7 4 5 1 9 2 3 5 6,第一步选择的轴值为1,第一个3会被放到第二个3的后面,从而造成不稳定.(也就是因为后面的元素下标是由后向前,导致前面的元素在向后放的时候会放到相等的元素后面)

问题:讨论插入排序的变种:发现逆序对直接交换、查找待插入位置时,采用二分法。

李芊答:我觉得发现逆序对直接交换实际上与循环后移是一样的效果。查找待插入位置时采用二分法,这个方法非常好,因为待插入元素之前的元素一定都是排好序的,所以可以用二分法查找位置。

问题:Shell 排序的每一轮子序列排序可以用其他方法吗?

李芊答:可以用其它方法。因为各个子序列都是互相独立的所以可以用其它方法,不过插入排序由于比较简单而且在比较有序的情况下复杂度比较低,一般选它。

第八章 内排序下

问题:普通归并算法和Sedgewick算法相比哪个更优?从二者的比较次数和赋值次数以及归并时子序列下标是否需要边界判断出发.

杜若谷答:Sedgewick算法需要更多地元素之间的比较,但是普通算法需要判断边界,所以比较次数更多。总体来说Sedgewick 算法更优。

刘家霖答:从比较次数上看,普通归并最好情况2n,最坏情况3n;优化归并为2n

问题:基数排序的时间代价

吴鹏答:基数排序中应该是d>=logrmm为排序码中的最大数。所以代价应为nlogm。实际测试的时候当n>=10亿时,在64bit系统下基数排序还是有优势的。甚至比introsort还要快一些。张铭补充:只有排序码中元素两两不相同时,才有m=n

问题:ranksort之后怎么处理结果。

吴鹏答:ranksort实际上就是计算出每个排序码对应的key的排名,那么就直接把对应的value放到结果数组中就好了,如result[rank[i]]=rank[i].value

问题:归并排序递归转非递归用什么栈还是队列作为辅助更好

李祝祺答:队列,因为归并的过程是从最后一层开始,做完一层再返回上一层

问题:如何利用归并排序解K-th number那道题

罗浩然答:对整个序列进行排序的同时,在节点之中记录这一段排好的序列.每次查找的时候,二分取值范围,在左子树和右子树中分别查找有多少个比当前值小的数,加起来再加一,即得到当前数在这个区间里的排序,如果小于k,则证明当前数取得小了,则在右区间里面继续进行.

问题:为什么改进过的归并排序算法不是稳定的?

罗浩然答:因为如果左边序列的指标越过了左序列的最后一个元素,那么在左右指标指的元素相等的时候会把左指标指的元素加入排好序的数组.但左指标此时指的元素原先在右指标指的元素后面.(例如 1 1 1 1这样的序列)

问题:桶式排序中m的数量级在多少比较合适?

罗浩然答: 我觉得不要超过nlogn比较好,因为桶式排序的算法复杂度为O(n+m),如果m过大则换用其它方法比较好.

问题:对于稳定的排序算法,如何修改可以使之不稳定?若算法不稳定,可否通过修改使之稳定?

邹良川答:对于稳定的排序算法,在排序前将数据随机打乱,就可以达到不稳定的效果了。对于不稳定的排序算法,可以将数据扩充出一个域,用于记录初始下标,当数据关键值相同时,比较下标大小,这样排序算法就是稳定的了。

问题:归并排序中,对于小序列,采用直接插入排序,为什么?

刘家霖答:因为归并排序本身是递归进行的需要消耗一定时间空间,对于小序列一般为基本有序的故插入排序的效率反倒更高。

问题:普通归并和 Sedgewick 算法都是稳定的吗?

刘家霖答:普通归并排序是稳定的,因为合并的时候是按照顺序合并。Sedgewick采用一个正序一个逆序合并所以相同值会颠倒顺序。所以是不稳定的。

问题:为什么桶排要从后往前收集

刘家霖答:从后往前才能保证桶排序的稳定性。

问题:桶排中怎样改成从前往后

郭秭含答:修改count的定义,count[i]表示关键码为i的记录第一次出现的位置。

然后从前往后扫描,找到一个记录p后把count[val[p]]++

问题:修改快排得到第一种索引的结果

郭秭含答:循环前记录轴值的index

把所有比较中的low,I,j改成index[low],index[i],index[j]

赋值(修改)语句中的修改r改成修改index

最后修改轴值改成修改轴值的index

问题:对静态链的基数排序结果进行简单变换得到第二种索引的方法

郭秭含答:静态链排序最后一步要整理答案,整理答案的方法是把桶从小到大扫描,取出每个链接在一起。在这个过程中就可以记录有多少个记录小于当前的记录(即扫描到它的时候已经处理过了多少记录)

 第九章 外排序

问题:什么是外排序?

李祝祺答:外排序是对比较大的存在外存中的文件进行排序。

问题:外排序的步骤是什么?

李祝祺答:    1.生成小顺串2.对顺串进行归并排序

问题:对一共n个串进行k路归并,k的数目选择多少能使访外存次数最少?

罗浩然答:访外存次数与k其实没有关系.可以类比于比赛中的单循环,比赛的场数只与参赛队伍的总数有关系,与比赛的先后,淘汰的制度都无关.譬如一共有10个串,可以算出来进行2,5,10路归并的次数都是一样的.

问题:置换选择排序的结果分析

杜若谷答:

最好情况下数据顺序输入且都大于堆顶元素,可以得到最长的顺串

最差情况是每次数据都小于堆顶元素,每个顺串长度等于堆的大小M

平均情况是得到2M的顺串

因为根据扫雪机模型,扫到的位置相当于堆顶元素,大于它的元素可以进入顺串,小于它的只能进入下一个顺串,假设每次扫雪中所下雪量为N,则每次扫雪完毕后只能看见N/2的雪量也就是下次堆的大小M=N/2,而每一次扫雪除了扫到上一次遗留的M的雪之外,还能扫到新下的M的雪,所以最终扫到的是2M的雪。

 问题:磁盘读一次数据要多长时间?

李芊答:平均读取一次数据时间 = 平均寻道时间+平均转动时间+读取一个块的时间。9 + 0.5 * 60*1000/7200RPM+ 60*1000/7200RPM/400 = 13.02ms

问题:内存、磁盘、硬盘、高速缓存价格?

李芊答:我从“京东”、“中关村在线”等网站查找了一下。内存:4GB价格大概为248元,1G大概要62元。

硬盘:查到的价格差异比较大啊。IBM500GB机械硬盘大概是1500元, 相当于1GB只用3元。要是固态硬盘就比较贵了,512G东芝的大概要2400元,1GB要接近5元,也不是特别贵。不过我查的硬盘可能是专业级别的,普通硬盘应该更便宜一些。

磁带:相当的便宜,750元可以买到6250GB容量的磁带。平均1GB只要0.12元。

但是没有查到高速缓存设备的价格。

问题:主流硬盘的性能指标?

李芊答:以东芝3TB硬盘为例:

容量:3000GB

旋转速度:7200rpm

交错因子:没查到。

寻道时间:4.16ms

旋转延迟时间:8.3ms

问题:败者树比胜者树优在哪?

王皓答:由于败者树中直接保存了比赛失败者而不是胜利者的索引,故每次比较时不需要去访问兄弟结点。

为什么建立khuffman树时满足(n-1) mod (k-1)=0就不需要加入空节点?

吴鹏回答:因为对于n个节点,构造khuffman树时最后需要只剩一个节点,而构造的过程是n-k+1(取出k个节点,合成1个后又放回优先队列中),直到最后只剩1个节点,所以就是(n-1) mod (k-1)=0时不需要加入空节点。具体过程就是 n-M(k-1)=1(取出M次后为1)所以n-1=M(k-1)

第十章 检索

问题:几种检索方法适合的应用场景分别是什么

郭秭含答:顺序检索适用于修改次数多查询次数少的情况。二分检索适用于修改次数少(几乎无数据修改),对查询效率要求高的情况。分块检索适用于较折中的情况。

问题:假设线性表为(a, b, c)检索 abc 的概率分别为 0.40.10.5 。顺序:检索算法的平均检索长度是多少?(即平均需要多少此次比较给定值与表中关键码值才能找到待查元素)

杜若谷答:0.4 * 1 + 0.1 * 2 + 0.5 * 3 = 2.1

问题:碰撞处理的选择

杜若谷答:针对检索准确性要求不高的情况(比如POJ),可以使用不同的hash函数,构建不同的几个散列同时检索,所有散列都为真时才为真。这样可以保证高效率,同时基本可以保证POJ的通过。

问题:集合的还有哪些实现方式。

吴鹏答:除了set用红黑树实现外还有C++ 11的加入的unordered_sethash表实现。

王皓答:

<set>:红黑树

<bitset>:类似于本节课所讲的集合。相当于一个固定长度的位向量,支持各种位运算

<algorithm>:对于有序序列的处理

set_union:集合并

set_intersection:集合交

set_difference:集合差

set_symmetric_difference:集合对称差

问题:插入同义词时,如何对同义词链进行组织?

吴鹏答:如果key是可以比较大小的,则可以把同义词链建立成二叉树,这样就可以在查找插入时加快速度。

问题:Bloom Filter有哪些应用?

吴鹏答:在使用python做网页抓取时,判定一个网页是否被抓取过可以用Bloom Filter判定。如果当前网页特征位不在Filter set里,那么一定没有被抓取过,就抓取。

问题:试比较顺序检索、二分检索和分块检索的优缺点

高飙答:顺序检索优点:对表的特性没有要求,数据元素可以任意排列,插入元素只要O(1);缺点:当数据规模大时,检索效率低;

二分检索优点:效率很高,Ologn);缺点:要求表有序,排序本身费时,修改困难;

分块检索优点:性能高于顺序检索,低于二分检索,插入删除元素较简单;缺点:分组不均匀时效率会下降。

王皓答:

算法

ASL

 效率

预排序

存储方法

插入/删除

顺序检索

(n+1)/2

顺序/链接

二分检索

log2(n+1)-1

顺序

分块检索

log2(1+n/s)+s/2

较快

顺序

问题:双散列函数  h2(K)   h1(K)  有什么关系?

王皓答:di = (h1(K) + i * h2(K)) % Mh1(K) 作为基地址,h2(K) 作为步长。

李芊答:h1(key)产生基地址,h2(key)产生的是探查序列的步长。只有基地址冲突的时候,才会考虑进行探查。

问题:调研除散列以外字典的其他实现方法。

王皓答:字符串可以使用 Trie 树实现。STL map 使用红黑树实现

 

第十一章 索引

问题:多分树的阶(子结点的个数)应该怎么确定?

王皓答:权衡外存访问次数、缓冲区大小、读入结点的时间,结点个数需要稍大,最好能放在一个磁盘块中

问题:除了红黑树的旋转和B树的分裂合并,还有什么别的方法来维持一个树的效率,还有什么其它树的结构?

吴鹏答:比如treap树是加入随机数,通过旋转维护堆的性质来保持效率。而splay树是单纯通过旋转维持效率(旋转次数较多)。Size Blance Tree是通过旋转维护size域保持效率。如果说不用旋转的话,还有一些比如“朝鲜树”通过设定深度,当树深度超过一定限制就暴力重建的方法(重建只用O(n)),听说也是均摊O(logn)查找删除复杂度。

问题:B 树的定义中关于度数的定义为从m/2m之间,是否可以调整为其他范围?

吴先答:可以调整,但是不合适。m/2恰好保证了在合并的时候不会因为合并而导致分裂,同时让每一层的结点尽可能得多,修改的话要么让树的深度增加,要么让删除操作变得复杂。

赵若远答:首先,不能下限不能高于[m/2],否则合并操作就无法进行。当下限低于[m/2]时,合并和分裂都是可行的,完全可以满足B树的各种条件。但是下限降低会导致树变得更稀疏,深度会变大,降低检索的效率。

问题:在什么情况下需要组织二级线性索引?

王皓答:一级线性索引文件过大而无法放入内存中,从而每次检索可能需要多次访问磁盘

问题:怎样有效地组织属性倒排索引表?

王皓答:对于每一个属性,对于其中的每一个属性值,都建立一个线性表,存放与此属性值相对应的所有记录的指针

问题:一个关键词如果在同一个文本中多次出现, 它在倒排文件中的索引项是否能进行合并?

王皓答:如果问题只要求查找到词所在的文本编号,那么当然可以进行合并

问题:B树插入时,如果发生上溢出就分裂,为什么不是送给兄弟结点一些关键码?

李祝祺答:因为插入操作大部分是发生在创建阶段,分裂的结点很快会增加新的关键码。而如果送给兄弟结点,则会修改兄弟结点和父结点,访外开销太大。

第十二章 高级数据结构

问题:内存是随机访问存取器,即访问每个元素所需的时间都是一样的,为什么还会存在局部性的概念(访问速度不同)?

邹良川答:但就内存而言,的确访问每个元素所需时间是相同的,但计算机系统中还有多级高速缓存,有较好局部性的程序对于数据的请求更容易被缓存命中,因而速度更快。

问题:小G是一位糕点制作大师,他每天会制作m个不同品种的糕点。为了显示大师作品的珍贵性,对于每个品种的糕点,小G只会做出全世界独一无二的一份。现在小G收到了n份订单,每份订单都描述了顾客对若干种( [0,m] )糕点的需求。小G不希望给任何一位顾客留下遗憾,所以他今天只能接受一部分订单。他希望能完全满足这些顾客的需求,同时将他的糕点全都卖出去。他应该接受哪些订单呢?

杜若谷答:这是一个精确覆盖问题,意思是在一个矩阵中找到一个行的集合,使每个列都有且只有一个元素是1。算法的思想是枚举和回溯,但是使用矩阵会有很多不必要的拷贝工作,所以我们可以在这个地方使用十字链表和递归的进行枚举。每次枚举一个行,清除所以和它有列重复的行,直到不能再枚举。如果此时所剩矩阵全为1,则我们找到了一个解,否则我们应当回溯,继续枚举。

问题:三元组存储稀疏矩阵的优缺点?

吴鹏答:优点是形式简单,容易实现。缺点就是太慢,查找某一元素需要遍历全部元素查找。

问题:矩阵乘法的优化?

吴鹏答:计算幂的时候用快速幂,将计算n幂次转化为计算(n/2)幂。

问题:广义表与树、图各有什么区别与联系?

李芊答:如果广义表的每个元素都是同类型的原子,那么可以认为就是线性表。如果广义表是纯表,可以认为是树,也是一种特殊的图。如果广义表是可重入表但无循环,那么可以认为是有向无环图(DAG)。如果是循环表,那么就是有向有环的图了。

问题:遍历数组时,维度的顺序对速度有无影响?

罗浩然答:有影响的.比如对一个按行存储的语言,最好是外层循环是行,内层为列,这样遍历时两个相邻数据在内存中位置较近,空间局部性好.

问题:后缀数组在实际中的应用

李祝祺答:可以求重复k次的最长周期,求解RMQ问题,最长公共子串等。

问题: AVL中平衡因子的绝对值不能大于1的这个定义能否修改?比如改成2可以吗?

罗浩然答:其实这个数字的多少只是一个约定罢了,改成多少没有本质区别.比如改成2,一样也可以有对应的调整操作,保证它高度比较平衡,但是此时需要考虑的调整情况比较多,而且树形可能也没有约定为1的时候好.

问题:中文是否适合组织字符树?是否适合 PATRICIA Trie 结构?

杜若谷答:中文不是和组织字符树,因为中文的字符量有数万个,如果组织字符树会导致结点过于庞大且不便查找。中文也不适合普通的PATRICIA Trie结构,因为中文的常用字只有约3000个,并且随机选择两个字就能组成词的概率就更小了,这就会导致Trie树非常不满,树高过高。我们可以通过缩减路径长度版本的PATRICIA Trie树来组织中文,就会很好。

问题:红黑树、AVL树和Splay树的比较 -它们与访问频率的关系? -树形结构与输入数据的顺序关系? -统计意义上哪种数据结构的性能更好? -哪种数据结构最容易编写?

邹良川答: Splay树在每次访问时将被访问节点移至根,在访问频率较高时性能较好; AVL树和红黑树对于顺序数据仍能保证较为平衡的形态,而Splay则不同; 统计意义上,红黑树的性能较好; Splay树所处理的情况比较简单,代码易于编写。

问题:对于中文的trie树建立的方法

吴先答:因为中文字符比较多,直接把所有字符作为节点会导致trie树过宽。可以选择把一个节点拆分成两层甚至更多层节点来表示。举个例子,假设原本一层有65536个子结点,可以转换成一层有256个节点,然后用两层节点来表示一个字符(256*256==65536)。

问题:元素个数为k的二叉树个数?

谢毅泽答:可以看做对任意0<=m<=k-1左子树元素个数为m,右子树为k-1-m的二叉树个数之和。这满足Catalan数列的递归版本定义。所以总个数为C(2k,k)/(k+1)