没有合适的资源?快使用搜索试试~ 我知道了~
首页二分查找详解:算法与线性表排序元素的关系
二分查找详解:算法与线性表排序元素的关系
需积分: 17 1 下载量 196 浏览量
更新于2024-07-15
收藏 1.94MB PDF 举报
本资源是一份关于算法查找的专项题库,包含了详细的题目答案与解析。主要内容涉及线性表的数据结构和查找算法的应用,重点讨论了顺序表和链表的存储方式以及它们在查找操作中的影响。 1. 题目涉及到了线性表的存储方式,区分了顺序方式和链接方式。顺序表强调的是元素连续存储,而链表则通过指针连接元素,但不一定有序。对于二分查找,它依赖于顺序存储且元素有序的特性,例如选项B中的"链接方式存储,元素有序"和D中的"顺序方式存储,元素有序"是二分查找适用的条件。 2. 折半查找,也即二分查找,是一种高效的查找算法,它要求表必须是顺序存储且元素已排序。在有序列表中查找元素X的次数取决于列表的大小,如第3题中提到,如果有序表有1000个元素,理论上最多需要比较log2(1000)次,约等于10次,但实际上可能少于这个次数。 3. 在一个具体示例的顺序表中,如第4题所示,通过二分查找20这个关键码,我们计算了查找过程中的比较次数,最终确定了需要3次比较才能找到该元素。这展示了二分查找的分治思想,每次将搜索范围减半,直到找到目标或搜索范围为空。 4. 第5题考查了二分查找的实际应用,给出了有序数组123456789查找数字3的正确序列。在这个例子中,由于3位于数组中间,二分查找的序列是逐步逼近目标值的过程,最终序列是B.5->2->3。 这份题库涵盖了基础的线性表概念、查找算法的原理(如二分查找)以及如何在实际问题中运用这些算法。理解并掌握这些知识点对于提高算法分析和解决实际问题的能力至关重要。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/13108679/bgc.jpg)
A. i=1,j=0
B. i=5,j=0
C. i=5,j=2
D. i=6,j=2
C. 32
D. 39
E. 40
没看懂题😂😂😂😂
翻译大概如下:假设含有80个元素的选择排序完成了主循环的32次迭代。 现在有多少元素被保留在最后的位置(永远不会被再次移
动)?
就是说执行了32次选择操作,每执行一次,将确定一个元素的最终位置,所以答案为32次。
选择排序,每一轮确定一个值得最终位置
24. 给定的一个长度为N的字符串str,查找长度为P(P<;N)的字符串在str中的出现次数.下面的说法正确的是()
A. 不存在比最坏时间复杂度O(NP)好的算法
B. 不存在比最坏时间复杂度O(N^2)好的算法
C. 不存在比最坏时间复杂度O(P^2)好的算法
D. 存在最坏时间复杂度为O(N+P)的算法
E. 存在最坏时间复杂度为O(log(N+P))的算法
F. 以上都不对
建议大家还是有空看看KMP算法,还有部分匹配值的计算。
还是很有用的。推荐大家一个博客,就是讲KMP的。
http://blog.csdn.net/liu940204/article/details/51318281
朴素匹配算法 时间复杂度O((N-P+1)@P)
KMP匹配算法 时间复杂度为O(N+P)
kmp最坏时间复杂度应该是O(NP),而通过kmp不能确定答案,而是考虑比kmp更好的bm和Sunday算法
25.
已知字符串S 为“abaabaabacacaabaabcc”,模式串 t 为“abaabc”。采用 KMP 算法进行匹配,第一
次出现“失配”(s[i]≠t[j]) 时,i=j=5,则下次开始匹配时,i 和 j 的值分别是
()
。
如果以上回答看不明白的朋友,或者KMP算法不明白的朋友可以参考一下这篇博客。http://blog.csdn.net/yutianzuijin/article/details/
11954939/
https://www.bilibili.com/video/av11866460?from=search&seid=13031204092636618468
小哥哥讲的可好了
先计算模式串abaabc的next数组
abaabc
011223
当匹配到i=5时,a!=c,
abaabaabacacaabaabcc
abaabc
![](https://csdnimg.cn/release/download_crawler_static/13108679/bgd.jpg)
A. 500,200,450,180
B. 500,450,200,180
C. 180,500,200,450
D. 180,200,500,450
123456789
然后 next[5]=3,移动模式串t往后3个位置,
abaabaabacacaabaabcc
xxxabaabc
12345678
i=5,j=2,继续比较
26.
下列选项中,不能构成折半查找中关键字比较序列的是
()。
“不能构成折半查找中关键字比较序列的是”
意思是:答案中的序列不是要查找的数据的完整序列,只是在查找过程中比较过的关键字的序列
然后画判定树,显然A不正确
27. KMP算法下,长为n的字符串中匹配长度为m的子串的复杂度为()
A. O(N)
B. O(M+N)
C. O(M+LOGM)
D. O(N+LOGM)
kmp算法完成的任务是:给定两个字符串O和f,长度分别为n和
m,判断f是否在O中出现,如果出现则返回出现的位置。常规方法是遍历O的每一个位置,然后从该位置开始和f进行匹配,但是这种
方法的复杂度是 O(nm)。kmp算法通过一个O(m)的预处理,使匹配的复杂度降为O(n+m)。
kmp算法思想
我们首先用一个图来描述kmp算法的思想。在字符串O中寻
找f,当匹配到位置i时两个字符串不相等,这时我们需要将字符串f向前移动。常规方法是每次向前移动一位,但是它没有考虑前i-1
位已经比较过这个事实, 所以效率不高。事实上,如果我们提前计算某些信息,就有可能一次前移多位。假设我们根据已经获得的信
![](https://csdnimg.cn/release/download_crawler_static/13108679/bge.jpg)
理解了kmp算法的基本原理,下一步就是要获得字符串f每一个位置的最大公共长度。这个最大公共长度在算法导论里面被记为next
数组。在这里要注意一点,
息知道可以前移k位,我们分析移位前后的f有什么特点。我们可以得到如下的结论:
A段字符串是f的一个前缀。
B段字符串是f的一个后缀。
A段字符串和B段字符串相等。
所以前移k位之后,可以继续比较位置i的前提是f的前i-1个位置满足:长度为i-k-1的前缀A和后缀B相同。只有这样,我们才可以前移
k位后从新的位置继续比较。
所以kmp算法的核心即是计算字符串f每一个位置之前的字
符串的前缀和后缀公共部分的最大长度(不包括字符串本身,否则最大长度始终是字符串本身)。获得f每一个位置的最大公共长度
之后,就可以利用该最大公共长
度快速和字符串O比较。当每次比较到两个字符串的字符不同时,我们就可以根据最大公共长度将字符串f向前移动(已匹配长度-最
大公共长度)位,接着继续比 较下一个位置。事实上,字符串f的前移只是概念上的前移,只要我们在比较的时候从最大公共长度之后比
较f和O即可达到字符串f前移的目的。
next数组计算
剩余66页未读,继续阅读
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/88f96aa0b3d443799445259096eff67f_qq_32711799.jpg!1)
潇洒郎
- 粉丝: 260
- 资源: 15
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 中国微型数字传声器:技术革新与市场前景
- 智能安防:基于Hi3515的嵌入式云台控制系统设计
- 手机电量低时辐射真增千倍?解析手机使用谣言
- 56F803型DSP驱动的高精度大功率超声波电源控制策略研究
- ARM与GPRS结合的远程监测系统设计
- GPS与RFID技术结合的智能巡检系统设计
- CPLD驱动的低功耗爆炸场温度测试系统设计
- 基于FPGA的智能驱动控制系统:可扩展设计与工业网络协议
- 基于ATmega128和CH374的嵌入式USB接口设计
- 基于AT89C52的温度补偿超声波测距仪:高精度设计与应用
- MSP430F448单片机在交流数字电压表中的应用
- 提升变频器应用效率的12项实用技巧
- STM32F103在数字电镀电源并联均流系统中的应用
- PSpice仿真下的升压开关电源设计:拓扑分析与CCM稳定性提升
- 轻巧高效:MSP430主导的低成本无线传感器网络节点设计
- FPGA在EDA/PLD中实现LVDS接口的应用解析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)