Question

算法与数据结构试题 急用！！！

1、请用类C语言描述链串的类型定义。

2、顺序查找时间为O(n),二分查找时间为O(log2n),散列查找时间为O(1),为什么有高效率的查找方法而不放弃低效率的方法？

3、简述折半查找的思想和过程。

4、简述二次探测法解决冲突的基本思想。

Answer 1

这是我写的顺序查找和二分查找代码
#include<iostream.h>
#define elemtype int

int sqsearch(elemtype a[],int n,elemtype x); //顺序查找
int sqsearch2(elemtype a[],int n,elemtype x); //顺序查找，打印查找过程
int binsearch(elemtype a[],int n,elemtype x); //折半查找
int binsearch2(elemtype a[],int n,elemtype x); //折半查找，打印查找过程

void printarray(elemtype a[],int n); //打印数组数据

int main()
{
int i,x;
const int n=9;
elemtype a1[10]={0,34,23,12,56,90,78,89,45,67};
elemtype a2[10]={0,12,23,34,45,56,67,78,89,90};

//顺序查找
cout<<"顺序查找："<<endl;
cout<<"a1[]=";
printarray(a1,n);
cout<<"输入要查找的数据：";
cin>>x;
if((i=sqsearch(a1,n,x))>0) //找到
cout<<"找到x==a1["<<i<<"]"<<endl;
else //未找到
cout<<"找不到"<<x<<endl;
cout<<endl<<"查找过程："<<endl;
sqsearch2(a1,n,x); //查找过程
cout<<"完成顺序查找！"<<endl;
//二分法查找
cout<<"二分法查找："<<endl;
cout<<"a2[]=";
printarray(a2,n);
cout<<"输入要查找的数据：";
cin>>x;
if((i=binsearch(a2,n,x))>0) //找到
cout<<"找到x==a1["<<i<<"]"<<endl;
else //未找到
cout<<"找不到"<<x<<endl;
cout<<endl<<"查找过程："<<endl;
binsearch2(a2,n,x);
cout<<"完成顺序查找！"<<endl;
return 0;
}

//在数组a[1.2...n]中顺序查找x
//找到时返回元素下标，否则返回0
int sqsearch(elemtype a[],int n,elemtype x) //a[]是数组，n是元素个数，x是要查找的数
{
int i;
if(a[0]==x)
return 1;
else
{
a[0]=x;
for(i=n;!(a[i]==x);--i); //若找到则i大于0
return i;
}
}

//在数组a[1.2...n]中顺序查找x,打印每次比较结果
//找到时返回元素下标，否则返回0
int sqsearch2(elemtype a[],int n,elemtype x) //a[]是数组，n是元素个数，x是要查找的数
{
int i;
a[0]=x;
for(i=n;!(a[i]==x);--i)
if(a[i]>x)
cout<<a[i]<<">"<<x<<endl;
else
cout<<a[i]<<"<"<<x<<endl;
return i;
}

//在数组a[1.2...n]中二分法查找x
//找到时返回元素下标，否则返回0
//前提：a[1.2...n]是非递减有序的
int binsearch(elemtype a[],int n,elemtype x) //二分查找
{
int mid,low=1,high=n;
while(low<=high)
{
mid=(low+high)/2;
if(x==a[mid])
return mid;
else if(x<a[mid])
high=mid-1;
else
low=mid+1;
}
return 0;
}

//在数组a[1.2...n]中二分法查找x，每次打印比较结果
//找到时返回元素下标，否则返回0
//前提：a[1.2...n]是非递减有序的
int binsearch2(elemtype a[],int n,elemtype x) //查找过程
{
int mid,low=1,high=n;
while(low<=high)
{
mid=(low+high)/2;
if(x==a[mid])
{
cout<<a[mid]<<"="<<x<<endl;
return mid;
}
else if(x<a[mid])
{
cout<<a[mid]<<">"<<x<<endl;
high=mid-1;
}
else
{
cout<<a[mid]<<"<"<<x<<endl;
low=mid+1;
}
}
return 0;
}

//打印顺组数据a[1....n]
void printarray(int a[],int n)
{
int i;
cout<<"{";
for(i=0;i<=n;i++)
{
cout<<a[i];
while(i<n)
{
cout<<",";
break;
}
}
cout<<"}"<<endl;
}

Answer 2

1、
// LString.h 串的块链存储表示
#define CHUNKSIZE 4 // 可由用户定义的块大小

typedef struct Chunk
{
char ch[CHUNKSIZE]; //块的数据域
struct Chunk *next; //块的指针域
}Chunk;

typedef struct
{
Chunk *head, // 串的头指针
*tail; // 串的尾指针
int curlen; // 串的当前长度
}LString;

char blank = '#'; // 全局变量,用于填补空余

// 初始化(产生空串)字符串T。
void InitString(LString *T)
{
(*T).curlen=0;
(*T).head=NULL;
(*T).tail=NULL;
}

// 生成一个其值等于chars的串T(要求chars中不包含填补空余的字符)
// 成功返回1，否则返回0

2、
这个跟所写代码环境相关。高效的算法一般都是以花费更多内存来实现的。而且有些算法虽然效率高，但可读性差。效率低的算法可读性高，容易理解，空间复杂度低等。

3、
折半查找的算法思想是将数列按有序化(递增或递减)排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。 折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，折半查找的先决条件是查找表中的数据元素必须有序。
折半查找算法步骤描述
step1. 首先确定整个查找区间的中间位置 　　mid = （ left + right ）/ 2 　　
step2. 用待查关键字值与中间位置的关键字值进行比较； 若相等，则查找成功；若大于，则在后（右）半个区域继续进行折半查找；若小于，则在前（左）半个区域继续进行折半查找。　　Step3. 对确定的缩小区域再按折半公式，重复上述步骤。最后，得到结果：要么查找成功，要么查找失败。
折半查找的存储结构采用一维数组存放。

4、
见（百度强大）
http://jpkc.nwu.edu.cn/sjjg/study_online/book/8/4_2.htm

Answer 3

第一题：typedef struct node
{
elemtype data;
elemtype code;
struct node *next;
}Lnode;
第二题，因为高效率的算法对要查找的序列要求高，如二分查找要求查找序列有序，低效率的查找对查找的序列要求很低，甚至没有要求。
第三问：
折半查找的算法思想是将数列按有序化(递增或递减)排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。 折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，折半查找的先决条件是查找表中的数据元素必须有序
第四问 ：二次探查法的探查序列是：
hi=(h(key)+i*i)％m 0≤i≤m-1 //即di=i2
即探查序列为d=h(key)，d+12，d+22，…，等。
　该方法的缺陷是不易探查到整个散列空间。

Answer 4

1、
typedef struct tagTList
{
int nIndex;
tagTList *m_pNext; //单向的链表
}TList;

2、因为如果数据量很少，查找效率是可以忽略的，低效的代码简单。

3、折半查找是建立在有序的情况下，因为有序，就可以在所有数的一半处取值，比较是否相等，如果相等，则返回；如果一半处的值大，则把一半减一的值的下标作为最大下标，继续比较，反之，则，一半值下标+1的值作为最小值下标，继续比较。

4、不清楚，没了解过

Answer 5

第4题看参考资料