数据结构算法设计题及答案.doc

(完整word版)数据结构算法设计题及答案
数据结构算法设计题及答案

1、 对带表头结点的有序单链表，编写算法向单链表中插入元素x，使其保持有序。

答案：
typedef datatype int;
struct node //结点结构
{ datatype data;
node * next;
};
//注：也可以用自然语言描述
void insertOrder(node *head, datatype x) //统计
{ node *s;
p=head;
while (p->next ->data<x)
p=p->next;
s=( node *)malloc(sizeof(node)) ;
s->data=x;
s->next= p->next;
p->next=s;
}

2、 对带表头结点的单链表，编写算法求单链表的长度。

答案：
typedef datatype int;
struct node //结点结构
{ datatype data;
node * next;
};
//注：也可以用自然语言描述
int Length(node *head) // 求单链表的长度
{ int num=0;
node *p=head->next;
while (p)
{
num++ ;
p=p->next;
}
return num;
}

3、 试写出单链表的插入与删除算法，并用C编写相应的程序。

答案：
typedef datatype int;
struct node //结点结构
{ datatype data;
node * next;
};

单链表的插入参考算法：
//在包含元素x的结点前插入新元素b
void ins_linked_LList(node * head , datatype x, datatype b)
{ node *p, *q;
p=new node ;//申请一个新结点
p->d=b;//置新结点的数据域
if (head==NULL)//原链表为空
{ head=p; p->next=NULL; return;}
if (head->d==x)//在第一个结点前插入
{ p->next=head;head=p;return; }
q=head;
while ((q->next!=NULL)&&(((q->next)->d)!=x))
q=q->next;//寻找包含元素x的前一个结点q
p->next=q->next;
q->next=p;//新结点p插入到结点q之后
return;
}

单链表的删除参考算法：
int del_linked_LList(node * head ,T x) //删除包含元素x的结点元素
{ node *p, *q;
if (head==NULL) return(0); //链表为空，无删除的元素
if ((head->d)==x)//删除第一个结点
{ p=head->next; delete head; head=p; return(1); }
q=head;
while ((q->next!=NULL)&&(((q->next)->d)!=x))
q=q->next;//寻找包含元素x的前一个结点q
if (q->next==NULL)
return(0); //链表中无删除的元素
p=q->next; q->next=p->next;//删除q的下一个结点p
delete p;//释放结点p的存储空间
return(1);
}

4、 对带表头结点的单链表，编写算法统计单链表中大于x的元素个数。

答案：
typedef datatype int;
struct node //结点结构
{ datatype data;
node * next;
};
//注：也可以用自然语言描述
int CountX(node *head, datatype x) //统计
{ int num=0;
p=head->next;
while (p)
{
if(p->data>x) num++ ;
p=p->next;
}
return num;
}

5、 对带表头结点的单链表，编写算法将单链表就地逆置。

答案：
typedef datatype int;
struct node //结点结构
{ datatype data;
node * next;
};
//注：也可以用自然语言描述
void ReverseList(node *head) // 将单链表就地逆置
{
node *q, *p=head->next;
head->next=NULL；
while (p)
{
q=p;
p=p->next;
q->next= head->next;
head->next=q ;
}
}

6、 写出链队列的入队、出队的算法。

答案：
typedef datatype int;
struct node //结点结构
{ datatype data;
node * next;
};
//注：也可以用自然语言描述
struct LinkQueue //结点结构
{ node * front;
node * rear;
};
int EnterQueue(LinkQueue *q, datatype e)
{ //带头结点的链队列入队
q->rear->next=( node *)malloc(sizeof(node));
q->rear->data=e;
q->rear= q->rear->next;
return 1;
}
int DeleteQueue(LinkQueue *q, datatype *e)
{ //带头结点的链队列出队
if(q->rear== q->front) return 0;
p= q->front->next;
*e= p->data;
q->front->next=p->next;
free(p);
if(q->front->next==NULL)
q->rear= q->front;
return 1;
}

7、 编写算法对二叉链表存储的二叉树进行前序遍历，并统计二叉树中叶子结点数。

答案：
typedef datatype int;
struct node //结点结构
{ datatype data;
node * lchild, *rchild;
};
//注：也可以用自然语言描述
void preOrder(node* root) //前序遍历
{
if(root==NULL) return ; // 空树
printf("%5d", root->data);
preOrder (root->lchild );// 前序遍历根的左子树
preOrder (root->rchild ); // 前序遍历根的右子树
}

int numOfLeaf (node* root) //统计二叉树中结点总数
{
if(root==NULL) return 0; // 空树
if((root->lchild ==NULL)&& (root->rchild ==NULL) )
return 1; // 叶子
return numOfLeaf (root->lchild )+ numOfLeaf (root->rchild );
}
//说明：算法的表达形式及方法多种多样，不可拘泥于固法。

8、 对以二叉链表存储的二叉树，编写对二叉树进行中序遍历的算法，以及求二叉树高度的算法。

答案：
typedef datatype int;
struct node //结点结构
{ datatype data;
node * lchild, *rchild;
};
//注：也可以用自然语言描述
void inOrder(node* root) //前序遍历
{
if(root==NULL) return ; // 空树
inOrder (root->lchild );// 中序遍历根的左子树
printf("%5d", root->data);
inOrder (root->rchild ); // 中序遍历根的右子树
}

int height (node* root) //求二叉树的高度
{ int h1,h2
if(root==NULL) return 0; // 空树
h1=height (root->lchild );
h2= height (root->rchild );
return 1+(h1>=h2)?h1:h2;
}
//说明：算法的表达形式及方法多种多样，不可拘泥于固法。

9、 编写对有序顺序表的折半查找算法。

答案：
#define MaxSize 100
typedef struct
{ KeyType key;
OtherType otherData;
}datatype;
struct SeqList //结点结构
{ datatype data[MaxSize]; //0号单元不用
int len;
};
int BinSearch(SeqList SL, KeyType k)
{ low=1, high=SL.len;
while(low<=high)
{ mid=( low+high)/2;
if(SL.data[mid].key==k)
return mid; //查找成功
if(SL.data[mid].key<k)
high= mid-1;
else
low= mid+1;
}
Return 0;//查找失败
}
}

10、 试写一个算法，判别一行字符中的圆括号是否配对。

答案：
int BracketMatch(char*str)
{ //圆括号配对判别, 配对返回1，否则返回0
Stack s;
InitStack(&s);
for(i=0; str[i]; i++)
{
switch( str[i] )
{ case ‘(‘: Push(&s, str[i]); break;
case ‘)’: if( IsEmpty(s) ) return 0;
Pop(&s);
}
}
if( IsEmpty(s) ) return 1;
return 0;
}