题目内容
（请给出正确答案）
提问人：网友anonymity
发布时间：2022-01-06
[主观题]
现在有一个已排序的字典，请改写二分法检索算法，使之当排序码key在字典中重复出现时算法能找出第一个key出现
的元素下标(用*position来保存)。保持算法时间代价为O(logn)。
简答题官方参考答案
（由简答题聘请的专业题库老师提供的解答）
查看官方参考答案
网友您好，请在下方输入框内输入要搜索的题目：
搜题
题目内容
（请给出正确答案）
简答题官方参考答案
（由简答题聘请的专业题库老师提供的解答）
更多“现在有一个已排序的字典，请改写二分法检索算法，使之当排序码key在字典中重复出现时算法能找出第一个key出现”相关的问题
第2题
在实现快速排序的非递归算法时，可根据基准元素.将待排序排序码序列划分为两个子序列。若下一趟首先对较短的子序列进行排序，试编写相应的算法，并说明在此做法下，快速排序所需要的栈的深度为O(log2n)，
点击查看答案
第3题
在已排好序的序列中，一个元素所处的位置取决于具有更小排序码的元素的个数。基于这个思想，可得计数排序方法。该方法在声明元素时为每个元素增加一个计数域count，用于存放在已排好序的序列中该元素前面的元素数日，最后依count域的值，将序列重新排列，就可完成排序。试编写一个算法，实现计数排序。并说明对于一个有n个元素的序列，为确定所有元素的count值，最多需要进行n(n-1)/2次排序码比较。
点击查看答案
第4题
设在一棵二叉搜索树的每个结点中，含有关键码key域和统计相同关键码结点个数的count域，当向该树插入一个元素时，若树中已存在与该元素的关键码柑同的结点，则就使该结点的count域增1，否则就由该元素生成一个新结点而插入到树中，并使其count域置为1，试按照这种插入要求编写一个算法。
点击查看答案
第5题
在内排序的过程中，通常需要对待排序元素序列的排序码做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将集合(tang，deng，an，wan，shi，bai，fang，l)中的排序码按升序排列，则(1)是起泡排序一趟扫描的结果，(2)是初始步长为4的希尔排序一趟扫描的结果。(3)是二路归并排序一趟扫描的结果。(4)是以第一个元素为分界元素的快速排序一趟扫描的结果。(5)是堆排序初始建堆的结果。
点击查看答案
A.deng，tang，an，wan，bai，shi，fang，li
B.an，deng，bai，li，shi，tang，iang，wan
C.deng，an，tang，shi，bai，fang，li，wan
D.deng，tang，an，wan，bai，shi，fang，li
E.an，bai，deng，fang，li，shi，tang，wan
F.an，tang，deng，wan，shi，bai，fang，li
G.li，deng，an，shi，bai，fang，tang，wan
H.shi，bai，an，li，tang，deng，fang，wan
第7题
奇偶交换排序是另一种交换排序。它的第一趟对序列中的所有奇数项i拼描，第二趟对序列中的所有偶数项i扫描，若A[i]≥Ali+1]，则交换它们。第三趟对所有的奇数项扫描，第四趟对所有的偶数项扫描，……，如此反复，直到整个序列全部排好序为止。
点击查看答案
(1)这种排序方法结束的条件是什么?
(2)写出奇偶交换排序的算法。
(3)当待排序排序码序列的初始排列是从小到大有序，或从大到小有序时，在奇偶交换排序过程中的排序码比较次数是多少?
第9题
假定把关键码key散列到有m个表项(从0到m-1编址)的散列表中。对于下面的每一个函数Hash(key)(key为整数)，这些函数能够当作散列函数吗(即对于插入和查找，散列程序能正常工作吗)?如果能够，它是一个好的散列函数吗?请说明理由。设函数random(m)返回一个0到m-1之间的随机整数(包括0与m-1在内)。
点击查看答案
(1)Hash(key)==key/m;
(2)Hash(key)=1;
(3)IIash(key)==(key+random(m))%rn;
(4)Hash(key)=key%p(m);其中p(m)是不大于m的最大素数。
