第9章自测卷答案_百度文库
赠送免券下载特权
10W篇文档免费专享
部分付费文档8折起
每天抽奖多种福利
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
第9章自测卷答案
阅读已结束，下载本文需要
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，同时保存到云知识，更方便管理
加入VIP
还剩5页未读，
定制HR最喜欢的简历
你可能喜欢借地，救命，请教几个DS题！_百度知道
借地，救命，请教几个DS题！
（1）折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素（ ）比较大小。 答案是不是：4，6，12，20 （2）哈希函数值发生冲突的原因是因为关键字相等 （判断——这句话是错的吗？） （3）若对序列（tang deng a...
我有更好的答案
第一题， 折半查找的思路：先给每个关键字编号，这道题是从1到10编号。其中low=1，high=10； 第一躺查找的编号应该是mid=（low+high）/2（取整）的关键字，也就是第5个关键字28。 比较之后发现28&20，所以20一定在28的左边。所以low不变，high=mid-1=4。 第二躺查找的编号mid=（low+high）/2=2，所以和6比较。 因为6&28，所以20在6的右边，所以higt不变，low=mid+1=3； 第三躺，mid=（low+high）/2=3，所以和12比较，步骤参考第二躺。 第四躺，查找成功。
MS小新兄也考DS啊~~~ 第一题某不明白，希望楼上大哥解释一下
不会 我大脑就相当于TLB一样硬件并行处理比较扫描全部牌 要眼观六路，耳听8方，还要善于察言观色，我打金花以前很厉害的，心理战术，又善于观察！
那你每次出牌都要花费O(n)的时间
其他1条回答
为您推荐：
其他类似问题
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。2012年计算机考研模拟试题_图文_百度文库
赠送免券下载特权
10W篇文档免费专享
部分付费文档8折起
每天抽奖多种福利
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
2012年计算机考研模拟试题
&&王道论坛2012年计算机考研模拟试题,这是前3套~
阅读已结束，下载本文需要
想免费下载更多文档？
定制HR最喜欢的简历
下载文档到电脑，同时保存到云知识，更方便管理
加入VIP
还剩44页未读，
定制HR最喜欢的简历
你可能喜欢C&& 先对数组排序&在进行折半查找
以下小编就为大家介绍两种实现方法。第一种方法是，选择排序法+循环折半查找法。第二种方法是，冒泡排序法+递归折半查找法。需要的朋友可以过来参考下，希望对大家有所帮助
第一步：输入15个整数
第二步：对这15个数进行排序
第三部：输入一个数，在后在排好序的数中进行折半查找，判断该数的位置
实现代码如下：
选择排序法+循环折半查找法
#include&iostream&
int main(){
int a[15];
void array_sort(int a[], int n);
int zeban(int a[], int start ,int end,int n);
cout&&"Please input 15 numbers:"&&
for(i=0;i&15;i++){
cin&&a[i];
cout&&"Sorted order:"&&
//==============选择排序========
array_sort(a,15);
//=======输出排序完成的数组====
for(i=0;i&15;i++){
cout&&a[i]&&" ";
cout&&"please input a number:";
//================折半查找==========
cout&&"number "&&n&&" locate in "&&zeban(a,0,14,n)&&
void array_sort(int a[],int n){
int i,j,k,
for(i=0;i&n;i++){
for(j=(i+1);j&n;j++){
if(a[j]&a[k]){
tool=a[i];
a[i]=a[k];
int zeban(int a[],int start,int end,int n){
int tag=-1;
for(start=0,end=14;start&=){
if(n==a[(start+end)/2]){
tag=(start+end)/2+1;
}else if(n&a[(start+end)/2]){
end=(start+end)/2;
}else if(n&a[(start+end)/2]){
start=(start+end)/2;
第二种方法：
冒泡排序法+递归折半查找法
#include&iostream&
int main(){
int a[15];
void array_sort(int a[], int n);
int IterBiSearch(int data[], const int x, int beg, int last);
cout&&"Please input 15 numbers:"&&
for(i=0;i&15;i++){
cin&&a[i];
cout&&"Sorted order:"&&
//==============选择排序========
array_sort(a,15);
//=======输出排序完成的数组====
for(i=0;i&15;i++){
cout&&a[i]&&" ";
cout&&"please input a number:";
//================折半查找==========
cout&&"number "&&n&&" locate in "&&IterBiSearch(a,n, 0, 14)&&
void array_sort(int a[],int n){
for(i=0;i&n;i++){
for(j=0;j&(n-i-1);j++){
if(a[j]&a[j+1]){
tool=a[j];
a[j]=a[j+1];
int IterBiSearch(int data[], const int x, int beg, int last)
int mid = -1;
mid = (beg + last) / 2;
if (x == data[mid])
return (mid+1);
else if (x & data[mid])
return IterBiSearch(data, x, beg, mid - 1);
else if (x & data[mid])
return IterBiSearch(data, x, mid + 1, last);
return -1;
Copyright (C) , All Rights Reserved.
版权所有 闽ICP备号
processed in 0.035 (s). 12 q(s)后使用快捷导航没有帐号？
只需一步，快速开始
请完成以下验证码
请完成以下验证码
主题帖子荣誉
查看: 10033|回复: 25
& 累计签到：2396 天连续签到：3 天
马上注册加入鱼C，享用更多服务吧^_^
才可以下载或查看，没有帐号？
如果从文件中读取的数据记录的关键字是有序排列的，则可以用一种效率比较高的查找方法来查找文件的记录，这就是折半查找法，又称为二分法搜索。
折半查找的基本思想是：减小查找序列的长度，分而治之地进行关键字的查找。
折半查找的实现过程是：先确定待查找记录的所在范围，然后逐渐缩小这个范围，直到找到该记录或查找失败（查无该记录）为止。
例如有序列：1 1 2 3 5 8 13 21 34 55 89（该序列包含 11 个元素，而且关键字单调递增。），现要求查找关键字 key 为 55 的记录。
我们可以设指针 low 和 high 分别指向关键字序列的上界和下界，指针 mid 指向序列的中间位置，即 mid = (low+high)/2。
No pic you say a J8 之图1：
1.jpg (12.32 KB, 下载次数: 7)
03:51 上传
首先将 mid 所指向的元素与 key 进行比较，因为我们这里 key = 55，大于 8，这就说明待查找的关键字一定位于 mid 和 high 之间。于是我们执行 low = mid+1; mid = (low+high)/2;
No pic you say a J8 之图2：
2.jpg (11.79 KB, 下载次数: 6)
03:51 上传
然后再将 mid 所指的 34 与 key 进行比较，仍然 mid & key，所以继续执行 low = mid+1; mid = (low+high)/2;
No pic you say a J8 之图3：
3.jpg (12.67 KB, 下载次数: 5)
03:51 上传
接下来仍然将 mid 所指的元素与 key 进行比较，结果相等，查找成功，可喜可贺，可口可乐！
返回 mid 的指针值，程序结束！
假设我们要查找的关键字 key = 88，那么上述的查找还要继续进行下去 low = mid+1; mid = (low+high)/2;
No pic you say a J8 之图4：
4.jpg (16.84 KB, 下载次数: 6)
03:51 上传
完整实现代码如下：
// ********************************
// By 小甲鱼，http://www.fishc.com
// ********************************
#include &stdio.h&
int bin_search( int str[], int n, int key )
{
& && &&&int low, high,
& && &&&
& && &&&low = 0;
& && &&&high = n-1;
& && &&&while( low &= high )
& && &&&{
& && && && && & mid = (low+high)/2;
& && && && && & if( str[mid] == key )
& && && && && & {
& && && && && && && && && && && && && & // 查找成功
& && && && && & }
& && && && && & if( str[mid] & key )
& && && && && & {
& && && && && && && && &low = mid + 1;& && &&&// 在后半序列中查找
& && && && && & }
& && && && && & if( str[mid] & key )
& && && && && & {
& && && && && && && && &high = mid - 1;& && &&&// 在前半序列中查找
& && && && && & }
& && &&&}
& && &&&return -1;& && && && && && && && && && &&&// 查找失败
}
int main()
{
& && &&&int str[11] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
& && &&&int n,
& && &&&printf(&请输入待查找的关键字: &);
& && &&&scanf(&%d&, &n);
& && &&&addr = bin_search(str, 11, n);
& && &&&if( -1 != addr )
& && &&&{
& && && && && & printf(&查找成功，可喜可贺，可口可乐! 关键字 %d 所在的位置是: %d\n&, n, addr);
& && &&&}
& && &&&else
& && &&&{
& && && && && & printf(&查找失败!\n&);
& && &&&}
& && &&&return 0;
}复制代码
& 累计签到：169 天连续签到：1 天
这个好，强大的算法
& 累计签到：22 天连续签到：0 天
写了个递归的：
#include&stdio.h&
#define SIZE 10
typedef int ElemT
int refind(ElemType *data,int begin,int end,ElemType num);
int main(void){
& && && && &ElemType data[SIZE]={10,20,30,40,50,60,70,80,90,100};
& && && && &ElemT
& && && && &for(int i = 0;i&SIZE;i++)
& && && && && && &&&printf(&%d &,data[i]);
& && && && &printf(&\n请输入要查找的数据:\n&);
& && && && &scanf(&%d&,&num);
& && && && &int flag = refind(data,0,SIZE,num);
& && && && &printf(&位置为:%d\n&,flag);
& && && && &return 0;
}
/
//递归
int refind(ElemType *data,int begin,int end,ElemType num)
{
& && && && &if(begin & end)
& && && && &{
& && && && && && && & printf(&没找到\n&);
& && && && && && && & return -1;
& && && && & }
& && && && & int mid = (begin+end)/2;
& && && && & if(data[mid] == num)
& && && && &{
& && && && && && && &
& && && && & }else if(data[mid] &= num)
& && && && && && && & return refind(data,mid+1,end,num);
& && && && & else
& && && && && && && & return refind(data,begin,mid-1,num);
}复制代码
& 累计签到：76 天连续签到：1 天
我有个问题，如果mid的值不是整数怎么弄啊？比如LOW = 0 High = 9，MID =4.5 这个时候怎么办啊？str[4.5]不可以啊
& 累计签到：2396 天连续签到：3 天
YYB 发表于
我有个问题，如果mid的值不是整数怎么弄啊？比如LOW = 0 High = 9，MID =4.5 这个时候怎么办啊？str[4.5]不 ...
这里的MID是向下取整└MID┘
& 累计签到：84 天连续签到：1 天
（）冒充下高手（）'“/&是求整不是除法哦
& 累计签到：6 天连续签到：0 天
不错学习下。
& 累计签到：140 天连续签到：0 天
顶起，不错呀
& 累计签到：49 天连续签到：0 天
谢谢小甲鱼！存钱买视频！
& 累计签到：69 天连续签到：1 天
强烈支持楼主ing……楼下的听好了……
& 累计签到：52 天连续签到：0 天
数组元素再加一个就挂了？？:curse:
& 累计签到：2 天连续签到：1 天
int binsearch_recursion(int a[], int low, int high, int key)
& & & & if(low & high)
& & & & & & & & return -1;
& & & & int mid = (low + high)/2;
& & & & if(a[mid] & key)
& & & & & & & & return binsearch_recursion(a, low, mid-1, key);
& & & & else if(a[mid] & key)
& & & & & & & & return binsearch_recursion(a, mid+1, high, key);
& & & & else
& & & & & & & &
& 累计签到：129 天连续签到：1 天
# include &stdio.h&
int bin_search(int *, int, int);
int main(void)
& & & & int a[11] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
& & & & printf(&%d\n&, bin_search(a, 11, 21));
& & & & return 0;
int bin_search(int * a, int n, int val)
& & & & int pos, low, hig,
& & & & for (low=0, hig=n-1, mid=(low+hig) / 2; low &= mid=(low+hig) / 2) {
& & & & & & & & if ( val == a[mid] )
& & & & & & & & & & & & return mid + 1;
& & & & & & & & else if ( a[mid] & val )
& & & & & & & & & & & & hig = mid - 1;
& & & & & & & & else
& & & & & & & & & & & & low = mid + 1;
& & & & return -1;
& 累计签到：87 天连续签到：1 天
这个学习对我帮助很大啊& &好好学习
& 累计签到：319 天连续签到：1 天
现在才学习，附上我的代码：
#include &stdio.h&
#include &stdlib.h&
int find(int num[],int low,int high,int a)
{
& & int mid=(low+high)/2;
& & if(low&=high)
& & {
& && &&&if(num[mid]==a)
& && &&&{
& && && && &
& && &&&}
& && &&&if(num[mid]&a)
& && &&&{
& && && && &return find(num,low,mid-1,a);
& && &&&}
& && &&&if(num[mid]&a)
& && &&&{
& && && && &return find(num,mid+1,high,a);
& && &&&}
& & }else
& & {
& && &&&return -1;
& & }
}
void main()
{
& & int num[]={1,1,2,3,5,8,13,21,34,55,89};
& & int n,
& & printf(&请输入你要查找的数：&);
& & scanf(&%d&,&n);
& & result=find(num,0,10,n);
& & if(result==-1)
& & {
& && &&&printf(&不存在此数&);
& & }else
& & {
& && &&&printf(&你要找的数在第%d个位置。&,result+1);
& & }
}复制代码
& 累计签到：136 天连续签到：1 天
感谢小甲鱼
& 累计签到：7 天连续签到：1 天
RE: 折半查找法（迭代实现）
强烈支持楼主ing……
用迭代实现了一下：
#include &stdio.h&
#include &stdlib.h&
int bin_serach(int str[], int n, int key)
{
& & int low, mid,
& & low = 0;
& & high = n - 1;
& & while(low &= high)
& & {
& && &&&mid = (low + high)/2;
& && &&&if (str[mid] == key)
& && &&&{
& && && && &
& && &&&}
& && &&&else if (str[mid] & key)
& && &&&{
& && && && &low = mid + 1;
& && &&&}
& && &&&else {
& && && && &high = mid - 1;
& && &&&}
& & }
& & return -1;
}
int getAddr(int str[], int key, int low, int high)
{
& & if (low & high)
& && &&&return -1;
& & int mid = (low + high) / 2;
& & if (key == str[mid])
& && &&&
& & if (str[mid] & key)
& & {
& && &&&low = mid + 1;
& & }
& & else if (str[mid] & key)
& & {
& && &&&high = mid - 1;
& & }
& & return getAddr(str, key, low, high);
}
int main()
{
& & int str[11] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
& & int n,
& & printf(&请输入要查询的数字：&);
& & scanf(&%d&, &n);
& & //addr = bin_serach(str, 11, n);
& & addr = getAddr(str, n, 0, 11);
& & if (-1 != addr)
& & {
& && &&&printf(&查找成功，查询数字%d所在的位置是：%d\n&, n, addr);
& & }
& & else
& & {
& && &&&printf(&查找失败&);
& & }
& & return 0;
}
复制代码
& 累计签到：26 天连续签到：1 天
& 累计签到：15 天连续签到：1 天
#include&stdio.h&
int bin_search(int arr[], int low, int high, int key);
void main()
{
& & int arr[10]={10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
& &
& & printf(&\n请输入要查找的数据:\n&);
& & scanf(&%d&, &key);
& & int addr = bin_search(arr, 0, 9, key);
& & if(addr != -1)
& & {
& & & & & & printf(&key: %d, address: %d\n&, key, addr);
& & & & }
& & else
& & & & {
& & & & & & & & printf(&输入错误&);
& & & & }
}
int bin_search(int arr[], int low, int high, int key)
{
& & & & int mid = (low + high)/2;
& & & & if(key == arr[mid])
& & & & {
& & & & & & & &
& & & & }
& & & &
& & & & if(key &= arr[mid])
& & & & {
& & & & & & & & high = mid - 1;
& & & & & & & & bin_search(arr, low, high, key);& & & &
& & & & }
& & & &
& & & & if(key &= arr[mid])
& & & & {
& & & & & & & & low = mid + 1;
& & & & & & & & bin_search(arr, low, high, key);& & & &
& & & & else
& & & & {
& & & & & & & & return -1;
& & & & }
}复制代码
& 累计签到：92 天连续签到：1 天
这个算法貌似就是那个所谓的“二分法”吧！！
小甲鱼强烈推荐
新的视频新的面貌，希望大家喜欢 (≧∇≦)ﾉ
- - - - - - - - - - - -
新课程，新体验！
移动客户端下载（未启用）
微信公众号
Powered by
Copyright &
&&& All Rights Reserved.