请输入或粘贴题目内容
搜题
拍照、语音搜题，请扫码下载APP
题目内容
（请给出正确答案）
a)试按照以上思路，实现一个排序算法：
b)你的这一算法，时间和空间复杂度各是多少？
c)改进你的算法，使之能够在O(n+M)时间内对来自[0，M)范围内的n个整数进行排序，且使用的辅助空间不超过O(M)。
答案
更多“若将任一有序序列等效地视作有序向量，则其中每个元素的秩，应恰好就等于序列中不大于该元素的元”相关的问题
第2题
设采用实现如教材48页代码2.21所示的二分查找binSearch()算法版本A，针对独立均匀分布于[0，2n]内的整数目标，在固定的有序向量(1，3，5，...，2n-1)中查找。
a)若将平均的成功和失败查找长度分别记作S和F，试证明：(S+1)•n=F•(n+1);
b)上述结论，是否适用于binSearch()算法的其它版本？为什么？
c)上述结论，是否适用于fibSearch()算法的各个版本？为什么？
d)若待查找的整数按照其它的随机规律分布，以上结论又应如何调整？
第4题
比如，在仅能使用直尺的情况下，可通过反复实验，用鸡蛋刚能摔碎的下落高度(比如精确到毫米)来度量蛋壳的硬度。尽管可以假定在破裂之前蛋壳的硬度保持不变，但毕竟破裂是不可逆的。故若仅有一枚鸡蛋，则我们不得不从0开始，以1毫米为单位逐步增加下落的高度，若蛋壳的硬度不超过n毫米，则需要进行o(n)次实验。就效率而言，这等价于退化到无序向量的顺序查找。
a)若你拥有两枚鸡蛋(假定它们硬度完全相同)，所需实验可减少到多少次？试给出对应的算法;
b)进一步地，如果你拥有三枚鸡蛋呢？
c)一般地，如果共有d枚鸡蛋可用呢？
第5题
第8题
设有一个有向图G-(V，E)，其中：
不属于该图的拓扑有序序列是()
A、
B、
C、
D、
第9题
(1)这种排序方法结束的条件是什么？
(2)写出奇偶交换排序的算法。
(3)当待排序排序码序列的初始排列是从小到大有序，或从大到小有序时，在奇偶交换排序过程中的排序码比较次数是多少？
第10题
据占12字节。所有记录均已按关键码有序地存储在磁盘文件中。另外在内存中开辟了256K字节的空间可用于存放线性索引。试问：
(1)若将线性索引常驻内存，文件中最多可以存放多少个记录？(每个索引项8字节，其中关键码4字节，地址4字节)
(2)如果使用二级索引，第二级索引占用1024字节(有128个索引项，每个索引项8字节)，这时文件中最多可以存放多少个记录？
