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

这是我写的顺序查找和二分查找代码
#include
#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<<"顺序查找："< cout<<"a1[]=";
printarray(a1,n);
cout<<"输入要查找的数据：";
cin>>x;
if((i=sqsearch(a1,n,x))>0) //找到
cout<<"找到x==a1["< else //未找到
cout<<"找不到"< cout< sqsearch2(a1,n,x); //查找过程
cout<<"完成顺序查找！"< //二分法查找
cout<<"二分法查找："< cout<<"a2[]=";
printarray(a2,n);
cout<<"输入要查找的数据：";
cin>>x;
if((i=binsearch(a2,n,x))>0) //找到
cout<<"找到x==a1["< else //未找到
cout<<"找不到"< cout< binsearch2(a2,n,x);
cout<<"完成顺序查找！"< 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<"< else
cout< 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 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< return mid;
}
else if(x {
cout<"< high=mid-1;
}
else
{
cout< low=mid+1;
}
}
return 0;
}

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

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

第一题：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，…，等。
　该方法的缺陷是不易探查到整个散列空间。

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

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

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

4、不清楚，没了解过

第4题看参考资料