6-1 数据结构考题 - 顺序查找
分数 25
全屏浏览题目
切换布局
作者 陈皓
单位 合肥师范学院
建立一个顺序表，用顺序查找的方法对其实施查找。
顺序表的类型描述：
1. #define MAXSIZE 50 2. typedef int ElemType; 3. typedef struct 4. { 5. ElemType *R; 6. int length; 7. } SSTable;
函数接口定义：
下面给出了 顺序查找 函数的大部分内容，但缺少了一部分（以下划线____标识出来的部分）。
请先将以下代码中画横线的部分补充完整，然后将完整的函数Search_Seq提交系统，完成题目要求的功能。
int Search_Seq (SSTable T,ElemType k) { int i; T.R[0]= ____ ; for ( i=____ ; T.R[ ____ ]!= k ; ____ ); return ____ ; }
该函数中的参数说明：
ElemType k 要搜索的值
顺序表中第一个数据元素存储在 T.R[1]
测试主程序样例：
int main () { SSTable T; ElemType k; Create(T); cin>>k; int pos=Search_Seq(T,k); if(pos==0) cout<<"NOT FOUND"<<endl; else cout<<pos<<endl; return 0; }
输入格式:
第一行输入一个整数n，表示顺序表的元素个数。
第二行行输入n个数字，依次为表内元素值。
第三行输入一个要查找的值。
输出格式:
输出这个值在表中的位置。如果没有找到，输出NOT FOUND。
输入样例:
1. 5 2. 9 5 3 7 6 3. 7
输出样例:
4
输入样例2:
1. 5 2. 9 5 3 7 6 3. 8
输出样例2:
NOT FOUND
1. int Search_Seq (SSTable T,ElemType k) 2. { 3. for(int i=0;i<=T.length;i++) 4. { 5. if(T.R[i]==k) 6. { 7. return (i); 8. } 9. } 10. return 0; 11. }
6-2 二分查找
分数 25
全屏浏览题目
切换布局
作者 陈越
单位 浙江大学
本题要求实现二分查找算法。
函数接口定义：
Position BinarySearch( List L, ElementType X );
其中List结构定义如下：
typedef int Position; typedef struct LNode *List; struct LNode { ElementType Data[MAXSIZE]; Position Last; /* 保存线性表中最后一个元素的位置 */ };
L是用户传入的一个线性表，其中ElementType元素可以通过>、==、<进行比较，并且题目保证传入的数据是递增有序的。函数BinarySearch要查找X在Data中的位置，即数组下标（注意：元素从下标1开始存储）。找到则返回下标，否则返回一个特殊的失败标记NotFound。
裁判测试程序样例：
#include <stdio.h> #include <stdlib.h> #define MAXSIZE 10 #define NotFound 0 typedef int ElementType; typedef int Position; typedef struct LNode *List; struct LNode { ElementType Data[MAXSIZE]; Position Last; /* 保存线性表中最后一个元素的位置 */ }; List ReadInput(); /* 裁判实现，细节不表。元素从下标1开始存储 */ Position BinarySearch( List L, ElementType X ); int main() { List L; ElementType X; Position P; L = ReadInput(); scanf("%d", &X); P = BinarySearch( L, X ); printf("%d\n", P); return 0; } /* 你的代码将被嵌在这里 */
输入样例1：
1. 5 2. 12 31 55 89 101 3. 31
输出样例1：
2
输入样例2：
1. 3 2. 26 78 233 3. 31
输出样例2：
0
1. Position BinarySearch( List L, ElementType X ) 2. { 3. int low=1; 4. int high=L->Last; 5. int mid; 6. while(low<=high) 7. { 8. mid=(low+high)/2; 9. if(X>L->Data[mid]) 10. { 11. low=mid+1; 12. } 13. else if(X<L->Data[mid]) 14. { 15. high=mid-1; 16. } 17. else 18. { 19. return mid; 20. } 21. } 22. return NotFound; 23. }
7-1 二分查找
分数 20
全屏浏览题目
切换布局
作者 usx程序设计类课程组
单位 绍兴文理学院
对于输入的n个整数，先进行升序排序，然后进行二分查找。
输入格式:
测试数据有多组，处理到文件尾。每组测试数据第一行输入一个整数n(1≤n≤100)，第二行输入n个各不相同的待排序的整数，第三行是查询次数m（1≤m≤100），第四行输入m个待查找的整数。
输出格式:
对于每组测试，分2行输出，第一行是排序后的升序的结果，每两个数据之间留一个空格；第二行是查找的结果，若找到则输出排序后元素的位置（从1开始，每两个数据之间留一个空格），否则输出0。
输入样例:
1. 9 2. 4 7 2 1 8 5 9 3 6 3. 5 4. 10 9 8 7 -1
输出样例:
1. 1 2 3 4 5 6 7 8 9 2. 0 9 8 7 0
迭代法查找
1. #include<bits/stdc++.h> 2. using namespace std; 3. const int N=1e5+10; 4. int a[N]; 5. int main() 6. { 7. int n; 8. while(scanf("%d",&n)!=EOF) 9. { 10. for(int i=0;i<n;i++) 11. cin>>a[i]; 12. sort(a,a+n); 13. for(int i=0;i<n;i++) 14. { 15. if(i) 16. { 17. cout<<" "; 18. } 19. cout<<a[i]; 20. } 21. cout<<endl; 22. int m,count=0; 23. cin>>m; 24. while(m--) 25. { 26. int t; 27. cin>>t; 28. int w=lower_bound(a,a+n,t)-a; 29. if(a[w]==t) 30. { 31. if(count==0) 32. { 33. cout<<w+1; 34. count=1; 35. } 36. else cout<<" "<<w+1; 37. } 38. else 39. { 40. if(count==0) 41. { 42. cout<<0; 43. count=1; 44. } 45. else cout<<" "<<0; 46. } 47. } 48. cout<<endl; 49. } 50. }
二分查找
1. #include<bits/stdc++.h> 2. using namespace std; 3. int check (int *a,int x,long n) 4. { 5. int mid,low=0,high=n-1; 6. while(low<=high) 7. { 8. mid=(low+high)/2; 9. if(x<a[mid]) 10. { 11. high=mid-1; 12. } 13. else if(x>a[mid]) 14. { 15. low=mid+1; 16. } 17. else 18. { 19. return (mid+1); 20. } 21. } 22. return (0); 23. } 24. int main() 25. { 26. int n; 27. cin>>n; 28. int a[n]; 29. for(int i=0;i<n;i++) 30. { 31. cin>>a[i]; 32. } 33. sort(a,a+n); 34. for(int i=0;i<n;i++) 35. { 36. cout<<a[i]; 37. if(i<n-1) 38. { 39. cout<<" "; 40. } 41. if(i==n-1) 42. { 43. cout<<endl; 44. } 45. } 46. int m; 47. cin>>m; 48. int b[m]; 49. for(int j=0;j<m;j++) 50. { 51. cin>>b[j]; 52. int temp=b[j]; 53. cout<<check(a,temp,n); 54. if(j<m-1) 55. { 56. cout<<" "; 57. } 58. if(j==m-1) 59. { 60. cout<<endl; 61. } 62. } 63. return 0; 64. }
