2013 408 应用题错题

人生无根蒂，飘如陌上尘

已于 2022-05-01 16:15:47 修改

阅读量4.5k

点赞数 1

分类专栏： 408真题选择错题文章标签： 408

于 2022-04-25 10:44:52 首次发布

本文链接：https://blog.csdn.net/programmer9/article/details/124378610

版权

本文分析了408应用题中的查找算法在不同存储结构中的应用，包括顺序表和链式结构。在顺序表中，通过调整元素顺序和采用顺序查找法可降低平均查找长度。而在链式结构中，讨论了Cache和主存的交互，计算了读取效率。此外，还涉及了条件转移指令的设计以及信号量在资源管理中的应用，以及分页存储管理方式的相关计算。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

2013 408应用题错题

1

设包含4个数据元素的集合S={“do”,“for”,“repeat”,“while”}，各元素的查找概率依次为p1=0.35,p2=0.15,p3=0.15,p4=0.35。将S保存在一个长度为4的顺序表中，采用折半查找法，查找成功的平均查找长度为2.2。
（1）若采用顺序存储结构保存S，且要求平均查找长度更短，则元素应如何排列？应使用何种查找办法？查找成功时的平均查找长度是多少？
要求平均查找长度更短，那么查找频率大的元素应该排列在前面，查找频率小的元素应该排列在后面。所以应该是这么排列“do”，“while”，“for”，“repeat”。
那么应该使用哪种查找办法呢？顺序查找法可以吗？
查找成功时的平均查找长度为？
10.35+20.35+30.15+40.15=2.1
（2）若采用链式存储结构保存S，且要求平均查找长度更短，则元素应如何排列？应使用何种查找办法？查找成功时的平均查找长度是多少？
我不知道链式存储和线性存储的区别。

顺序查找是很简单的，就是从前到后逐个匹配而已。
折半查找有几个地方需要注意。第一就是折半是下取整，第二就是折半查找只适用于有序表，第三就是折半查找的时间复杂度是O(log2n),因为折半查找是一种取巧的办法，因此平均情况下它的查找效率比顺序查找要高。