64,685
社区成员
发帖
与我相关
我的任务
分享百度在线笔试题求解！！
一、编程题：30分 共1题
注意：要求尽可能提供完整代码，如果可以编译运行酌情加分。
1.内存中有一个长数组，条目数为10万，数组单元为结构体struct array，sizeof(struct array)为512字节。结构有一int型成员变量weight。现需要取得按weight值从大到小排序的前500个数组单元，请实现算法，要求效率尽可能高。
二、设计题：35分 共1题
注意：请尽可能详细描述你的数据结构、系统架构、设计思路等，建议多写一些伪代码或者流程说明。
1.请设计一个字典。以字符串为索引，存储用户定义的定长结构。要求有增、删、查、改的功能。已经给定一个函数，可以由字符串映射到一个签名，每个签名由两个unsigned int类型组成。假设每一个字符串能够对应唯一的一个签名，完全没有重复（或者重复的概率可以忽略），并且签名分布足够均匀。
请描述你的数据结构？内存如何申请？增、删、查、改的功能如何实现？如果操作很频繁，该如何优化？
注意：要求尽可能提供完整代码，如果可以编译运行酌情加分。
1.内存中有一个长数组，条目数为10万，数组单元为结构体struct array，sizeof(struct array)为512字节。结构有一int型成员变量weight。现需要取得按weight值从大到小排序的前500个数组单元，请实现算法，要求效率尽可能高。
二、设计题：35分 共1题
注意：请尽可能详细描述你的数据结构、系统架构、设计思路等，建议多写一些伪代码或者流程说明。
1.请设计一个字典。以字符串为索引，存储用户定义的定长结构。要求有增、删、查、改的功能。已经给定一个函数，可以由字符串映射到一个签名，每个签名由两个unsigned int类型组成。假设每一个字符串能够对应唯一的一个签名，完全没有重复（或者重复的概率可以忽略），并且签名分布足够均匀。
请描述你的数据结构？内存如何申请？增、删、查、改的功能如何实现？如果操作很频繁，该如何优化？
...全文
请发表友善的回复…
发表回复
Dugowe 2006-10-10
- 打赏
- 举报
ding
qing_li73 2006-10-10
- 打赏
- 举报
old problems but pretty good :)
taodm 2006-10-09
- 打赏
- 举报
OOPhaisky(异化$渴望成功~~) ，没认真看stl源码剖析吧，去查partial_sort。
OOPhaisky 2006-10-09
- 打赏
- 举报
不会吧，stl上会有这种东西的源码？
--------------------------------------------------------
STL中不会有这个问题的直接答案，但是STL源代码确是[数据结构和算法]的极佳教程。
至于排序相关问题，STL的sort系列肯定是有的，而且效率很高。
至于第二题：字典问题，STL中的map就是采用树形结构来实现的，楼住可以参考一下。
--------------------------------------------------------
STL中不会有这个问题的直接答案，但是STL源代码确是[数据结构和算法]的极佳教程。
至于排序相关问题，STL的sort系列肯定是有的，而且效率很高。
至于第二题：字典问题，STL中的map就是采用树形结构来实现的，楼住可以参考一下。
superarhow 2006-10-09
- 打赏
- 举报
第1题个人认为定义一个10万的指针数组,再qsort一把会比较快。第二题不就是std::map么？
dick248 2006-10-09
- 打赏
- 举报
mark
heartbeast 2006-10-09
- 打赏
- 举报
第一题用堆排序最好了。
第二题直接用STL里的map。
第二题直接用STL里的map。
taodm 2006-10-09
- 打赏
- 举报
呃，第一题，确实stl已经提供好了的，在stl源码剖析上也有详细说明。
rubyhlp0925 2006-10-09
- 打赏
- 举报
内存中有一个长数组，条目数为10万什么意思,??我们只用到结构体struct array里的一个成员变量weight而乙,进行逐个访问顺序就好了
hell_wolf 2006-10-09
- 打赏
- 举报
第二题应该是用哈希查找表吧.
song x 2006-10-09
- 打赏
- 举报
不懂，mark
taodm 2006-10-09
- 打赏
- 举报
STL的源码，当然是侯捷的《STL源码剖析》
neoadane 2006-10-09
- 打赏
- 举报
第一题已基本解决，下面这个网址上有类似问题比较详细的解答
http://lanphaday.blogchina.com/5145363.html
我现在搞不清第二个问题，麻烦哪位详细解释一下啊。第二题是不是跟数据库编程有关的啊？我从来没搞过这方面的，题目都不太懂。。。
http://lanphaday.blogchina.com/5145363.html
我现在搞不清第二个问题，麻烦哪位详细解释一下啊。第二题是不是跟数据库编程有关的啊？我从来没搞过这方面的，题目都不太懂。。。
lwaaa 2006-10-09
- 打赏
- 举报
看来有空一定要看看STL的原码啊，哪位兄弟推荐一本书看看？
jackch88 2006-10-09
- 打赏
- 举报
1.
struct array
vector<array>arr;
2.
multimap<string,string>dir;
struct array
vector<array>arr;
2.
multimap<string,string>dir;
hziee_ 2006-10-09
- 打赏
- 举报
STL 里的算法最优,是很多大师的结晶,凡人很难超越.除非问题的特殊化可有改进的空间.
yym314 2006-10-09
- 打赏
- 举报
“从大到小排序的前500个数组单元”也就是要得到值最大的500个元素，所以不需要把整个数组都进行排序的。
我的方法是这样的：
1.定义一个500大小的数组resultArray用于按大小顺序存放结果
2.for( i=0...10万）
比较查看元素i的值和resultArray中的最小值，如果大于等于，用二分法找到元素i在resultArray中的存放位置，存放元素i,后移动其后的元素。
循环结束后，resultArray中存放的就是结果
我的方法是这样的：
1.定义一个500大小的数组resultArray用于按大小顺序存放结果
2.for( i=0...10万）
比较查看元素i的值和resultArray中的最小值，如果大于等于，用二分法找到元素i在resultArray中的存放位置，存放元素i,后移动其后的元素。
循环结束后，resultArray中存放的就是结果
neoadane 2006-10-08
- 打赏
- 举报
不会吧，stl上会有这种东西的源码？
hziee_ 2006-10-08
- 打赏
- 举报
第一题stl有个相关算法，（具体忘了），去翻一下stl源码剖析，应可以看得算法的实现。
