数据结构之散列查找
函数题
6-1 二分查找
分数 15
全屏浏览题目
切换布局
作者?陈越
单位?浙江大学
本题要求实现二分查找算法。
函数接口定义：
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：
5
12 31 55 89 101
31
输出样例1：
2
输入样例2：
3
26 78 233
31
输出样例2：
0Position BinarySearch( List LL, ElementType X ){
int L=1;
int R=LL->Last;
int mid;
while(L<=R){
mid=(L+R+1)/2;
if(LL->Data[mid]==X){
return mid;
}
else if(LL->Data[mid]<X){
L=mid+1;
}
else{
R=mid-1;
}
}
return NotFound;
}6-2 线性探测法的查找函数
分数 15
全屏浏览题目
切换布局
作者?DS课程组
单位?浙江大学
试实现线性探测法的查找函数。
函数接口定义：
Position Find( HashTable H, ElementType Key );
其中HashTable是开放地址散列表，定义如下：
#define MAXTABLESIZE 100000 /* 允许开辟的最大散列表长度 */
typedef int ElementType; /* 关键词类型用整型 */
typedef int Index; /* 散列地址类型 */
typedef Index Position; /* 数据所在位置与散列地址是同一类型 */
/* 散列单元状态类型，分别对应：有合法元素、空单元、有已删除元素 */
typedef enum { Legitimate, Empty, Deleted } EntryType;
typedef struct HashEntry Cell; /* 散列表单元类型 */
struct HashEntry{
ElementType Data; /* 存放元素 */
EntryType Info; /* 单元状态 */
};
typedef struct TblNode *HashTable; /* 散列表类型 */
struct TblNode { /* 散列表结点定义 */
int TableSize; /* 表的最大长度 */
Cell *Cells; /* 存放散列单元数据的数组 */
};
函数Find应根据裁判定义的散列函数Hash( Key, H->TableSize )从散列表H中查到Key的位置并返回。如果Key不存在，则返回线性探测法找到的第一个空单元的位置；若没有空单元，则返回ERROR。
裁判测试程序样例：
#include <stdio.h> #define MAXTABLESIZE 100000 /* 允许开辟的最大散列表长度 */ typedef int ElementType; /* 关键词类型用整型 */ typedef int Index; /* 散列地址类型 */ typedef Index Position; /* 数据所在位置与散列地址是同一类型 */ /* 散列单元状态类型，分别对应：有合法元素、空单元、有已删除元素 */ typedef enum { Legitimate, Empty, Deleted } EntryType; typedef struct HashEntry Cell; /* 散列表单元类型 */ struct HashEntry{ ElementType Data; /* 存放元素 */ EntryType Info; /* 单元状态 */ }; typedef struct TblNode *HashTable; /* 散列表类型 */ struct TblNode { /* 散列表结点定义 */ int TableSize; /* 表的最大长度 */ Cell *Cells; /* 存放散列单元数据的数组 */ }; HashTable BuildTable(); /* 裁判实现，细节不表 */ Position Hash( ElementType Key, int TableSize ) { return (Key % TableSize); } #define ERROR -1 Position Find( HashTable H, ElementType Key ); int main() { HashTable H; ElementType Key; Position P; H = BuildTable(); scanf("%d", &Key); P = Find(H, Key); if (P==ERROR) printf("ERROR: %d is not found and the table is full.\n", Key); else if (H->Cells[P].Info == Legitimate) printf("%d is at position %d.\n", Key, P); else printf("%d is not found. Position %d is returned.\n", Key, P); return 0; } /* 你的代码将被嵌在这里 */
输入样例1：（注：-1表示该位置为空。下同。）
11
11 88 21 -1 -1 5 16 7 6 38 10
38
输出样例1：
38 is at position 9.
输入样例2：
11
11 88 21 -1 -1 5 16 7 6 38 10
41
输出样例2：
41 is not found. Position 3 is returned.
输入样例3：
11
11 88 21 3 14 5 16 7 6 38 10
41
输出样例3：
ERROR: 41 is not found and the table is full.Position Find( HashTable H, ElementType Key ){
int a=Key%H->TableSize;
int count=0;
while(H->Cells[a].Info!=Empty&&count!=H->TableSize){
count++;
if(H->Cells[a].Data==Key)
return a;
else
a=(a+1)%H->TableSize;
}
if(H->Cells[a].Info==Empty)
return a;
else
return ERROR;
}
?
6-3 创建哈希表及查找(拉链法)
分数 15
全屏浏览题目
切换布局
作者?王东
单位?贵州师范学院
实现哈希表创建及查找算法，哈希函数使用除余法，用拉链法处理冲突。
函数接口定义：
void CreateHash(HashTable HT[],int n); //输入不大于m的n个不为0（0表示空值）的数，用拉链法解决冲突构造散列表 float ASL(HashTable HT[]); //计算平均查找长度
其中?HT?表示哈希表， n表示记录数。
裁判测试程序样例：
#include<iostream> using namespace std; #define P 13 typedef struct HashNode{ int key; struct HashNode *next; }HashNode,* HashTable; void CreateHash(HashTable HT[],int n); float ASL(HashTable HT[]); int main() { int i,n; HashTable HT[P]; for(i=0;i<P;i++) HT[i]=NULL; cin >> n; CreateHash(HT,n); cout << ASL(HT); return 0; } /* 请在这里填写答案 */
输入样例：
12
19 14 23 1 68 20 84 27 55 11 10 79
输出样例：
输出拓扑序列。
1.75 void CreateHash(HashTable HT[],int n){
int number;
for (int i=0; i<n; i++) {
scanf("%d",&number);
if (HT[number%P] != NULL) {
HashTable p = HT[number%P];
while(p->next){
p = p->next;
}
HashTable node = (HashTable)malloc(sizeof(HashNode));
p->next = node;
node->key = number;
node->next = NULL;
}
if (HT[number%P] == NULL){
HashTable node = (HashTable)malloc(sizeof(HashNode));
node->key = number;
node->next = NULL;
HT[number%P] = node;
}
}
}
float ASL(HashTable HT[]){
float cnt = 0;
int n=0;
for (int i=0; i<P; i++){
if (HT[i] == NULL){
continue;
}
if (HT[i] != NULL){
int add = 2;
cnt = cnt + 1;
n++;
HashTable p = HT[i]->next;
while (p){
cnt += add; //+2,+3,+4.....
n++;
p = p->next;
add++;
}
}
}
return cnt / n;
}?
6-4 二分查找（含排序）
分数 15
全屏浏览题目
切换布局
作者?启迪-数据结构教研组
单位?广西科技大学
本题要求实现两个函数：（1）排序；（2）二分查找
先利用排序算法将数据按关键字从小到大排序，再对排序后的数据进行二分查找
函数接口定义：
void Sort(List L); //对用户传入的线性表进行排序 int BinarySearch( List L,int X ); //查找X，如果查找成功返回对应的数组下标位置；查找失败，则返回NotFound
其中List结构定义如下：
struct LNode{ int Data[MAXSIZE]; //Data为待排序序列数组 int Last; //Last为最后一个元素的数组下标 }; typedef struct LNode *List;
裁判测试程序样例：
#include <stdio.h> #include <stdlib.h> #define MAXSIZE 10 #define NotFound -1 struct LNode{ int Data[MAXSIZE]; //Data为待排序序列数组 int Last; //Last为最后一个元素的数组下标 }; typedef struct LNode *List; void Sort(List L); int BinarySearch( List L,int X ); List Create() { List L; L = (List)malloc(sizeof(struct LNode)); int j = 0,n,ch; scanf("%d",&n); for(j=0;j<n;j++) { scanf("%d",&ch); L->Data[j] = ch; } L->Last = n-1; return L; } int main() { List L; int x,p; L = Create(); scanf("%d", &x); //输入要查找的关键字 Sort(L); p = BinarySearch(L,x); if(p != -1){ printf("所查找数据的位置为：%d",p); }else{ printf("NotFound"); } return 0; } /* 请在这里填写答案 */
输入样例1：
8
99 66 45 33 37 10 22 13
20
输出样例1：
NotFound
输入样例2：
8
99 66 45 33 37 10 22 13
13
输出样例2：
所查找数据的位置为：1void Sort(List L){
int min=0;
int t;
for(int i=0;i<L->Last;i++){
min=i;
for(int j=i+1;j<=L->Last;j++){
if(L->Data[j]<L->Data[min])
min=j;
}
t=L->Data[i];
L->Data[i]=L->Data[min];
L->Data[min]=t;
}
}
int BinarySearch( List LL,int X ){
int L=1;
int R=LL->Last;
int mid;
while(L<=R){
mid=(L+R+1)/2;
if(LL->Data[mid]==X){
return mid;
}
else if(LL->Data[mid]<X){
L=mid+1;
}
else{
R=mid-1;
}
}
return NotFound;
}
编程题?
?
7-1 集合相似度
分数 20
全屏浏览题目
切换布局
作者?陈越
单位?浙江大学
给定两个整数集合，它们的相似度定义为：Nc?/Nt?×100%。其中Nc?是两个集合都有的不相等整数的个数，Nt?是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。
输入格式：
输入第一行给出一个正整数N（≤50），是集合的个数。随后N行，每行对应一个集合。每个集合首先给出一个正整数M（≤104），是集合中元素的个数；然后跟M个[0,109]区间内的整数。
之后一行给出一个正整数K（≤2000），随后K行，每行对应一对需要计算相似度的集合的编号（集合从1到N编号）。数字间以空格分隔。
输出格式：
对每一对需要计算的集合，在一行中输出它们的相似度，为保留小数点后2位的百分比数字。
输入样例：
3
3 99 87 101
4 87 101 5 87
7 99 101 18 5 135 18 99
2
1 2
1 3
输出样例：
50.00%
33.33%#include<stdio.h>
#include<set>
using namespace std;
int n, m, k;
int num, a, b;
int c, t;
int i, j;
double sum;
set<int>s[55];
int main()
{
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
scanf("%d", &m);
for (j = 1; j <= m; j++)
{
scanf("%d", &num);
s[i].insert(num);
}
}
scanf("%d", &k);
for (i = 0; i < k; i++)
{
c = 0;
scanf("%d %d", &a, &b);
for (set<int>::iterator it = s[a].begin(); it != s[a].end(); it++) {
if (s[b].count(*it) == 1)
{
c++;
}
}
t = s[b].size() + s[a].size() - c;
sum = 1.0 * c / t * 100;
printf("%.2lf%%\n", sum);
}
return 0;
}
?注意：这里我使用了c++中的set容器，实在是太懒了不想写了，大家提交的时候注意用c++提交
7-2 悄悄关注
分数 20
全屏浏览题目
切换布局
作者?陈越
单位?浙江大学
新浪微博上有个“悄悄关注”，一个用户悄悄关注的人，不出现在这个用户的关注列表上，但系统会推送其悄悄关注的人发表的微博给该用户。现在我们来做一回网络侦探，根据某人的关注列表和其对其他用户的点赞情况，扒出有可能被其悄悄关注的人。
输入格式：
输入首先在第一行给出某用户的关注列表，格式如下：
人数N 用户1 用户2 …… 用户N
其中N是不超过5000的正整数，每个用户i（i=1, ...,?N）是被其关注的用户的ID，是长度为4位的由数字和英文字母组成的字符串，各项间以空格分隔。
之后给出该用户点赞的信息：首先给出一个不超过10000的正整数M，随后M行，每行给出一个被其点赞的用户ID和对该用户的点赞次数（不超过1000），以空格分隔。注意：用户ID是一个用户的唯一身份标识。题目保证在关注列表中没有重复用户，在点赞信息中也没有重复用户。
输出格式：
我们认为被该用户点赞次数大于其点赞平均数、且不在其关注列表上的人，很可能是其悄悄关注的人。根据这个假设，请你按用户ID字母序的升序输出可能是其悄悄关注的人，每行1个ID。如果其实并没有这样的人，则输出“Bing Mei You”。
输入样例1：
10 GAO3 Magi Zha1 Sen1 Quan FaMK LSum Eins FatM LLao
8
Magi 50
Pota 30
LLao 3
Ammy 48
Dave 15
GAO3 31
Zoro 1
Cath 60
输出样例1：
Ammy
Cath
Pota
输入样例2：
11 GAO3 Magi Zha1 Sen1 Quan FaMK LSum Eins FatM LLao Pota
7
Magi 50
Pota 30
LLao 48
Ammy 3
Dave 15
GAO3 31
Zoro 29
输出样例2：
Bing Mei You#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct user user;
struct user{
char name[5];
int dianzancishu;
};
int panduan(char names[5000][5],char* name,int n){
for(int i=0;i<n;i++){
int flag=strcmp(names[i],name);
if(flag==0)
return 1; //表示在这个榜上
}
return 0;
}
int cmp(const void *a,const void *b)
{
return strcmp((char*)a, (char*)b);
}
int main(){
int n;
scanf("%d",&n);
char names[5000][5];
user users[10000];
for(int i=0;i<n;i++){
scanf("%s",names[i]);
}
int m;
int sum=0;
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%s %d",users[i].name,&users[i].dianzancishu);
sum=sum+users[i].dianzancishu;
}
float summ=sum*1.0/m;
//接下来判断其是否在关注列表上
char namess[5000][5];
int k=0;
for(int i=0;i<m;i++){
if(panduan(names,users[i].name,n)==0&&users[i].dianzancishu>summ){
strcpy(namess[k++],users[i].name);
}
}
if(k==0)
printf("Bing Mei You");
else{
qsort(namess,k,sizeof(namess[0]),cmp);
for(int i=0;i<k;i++){
printf("%s\n",namess[i]);
}
}
}?
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！