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

1、数据结构算法设计题及答案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-&g

2、t;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

3、 /结点结构 datatype data;node * next;);单链表的插入参考算法：在包含元素x的结点前插入新元素bvoid 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-

4、>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; d

5、elete head; head=p; return(1); q=head;while (q->next!=NULL)&&(q->next)->d)!=x) q=q->next;/ 寻找包含元素 x的前一个结点 qif (q->next=NULL)return(0); /链表中无删除的元素p=q->next; q->next=p->next;/ 删除 q 的下个结点 p delete p;/释放结点p的存储空间return(1);x的元素个数.4、对带表头结点的单链表,编写算法统计单链表中大于答案：typedef datatype

6、 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;)；/ 注：也可以用自然语言描述

7、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; nod

8、e * 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-&g

9、t;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 * Ichild, *rchild;)；前序遍历空树前序遍历根的左子树前序遍历根的右子树/注：也可以用自然语言描述 void preOrder(node* root) / if(ro

10、ot=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 )+ nu

11、mOfLeaf (root->rchild ); )/说明：算法的表达形式及方法多种多样,不可拘泥于固法.8、对以二叉链表存储的二叉树,编写对二叉树进行中序遍历的算法,以及求二叉树高度的 算法.答案：typedef datatype int;struct node / 结点结构 datatype data;node * lchild, *rchild;);前序遍历空树中序遍历根的左子树中序遍历根的右子树/注：也可以用自然语言描述 void inOrder(node* root) / if(root=NULL) return ; / inOrder (root->lchild );/

12、 printf("%5d", root->data);inOrder (root->rchild ); /)int height (node* root) /求二叉树的高度 int h1,h2if(root=NULL) return 0; /空树h1=height (root->lchild );h2= height (root->rchild ); return 1+(h1>=h2)?h1:h2;)/说明：算法的表达形式及方法多种多样,不可拘泥于固法.9、编写对有序顺序表的折半查找算法.答案：#define MaxSize 100 typed

13、ef struct KeyType key;OtherType otherData;datatype;struct SeqList / 结点结构 datatype dataMaxSize; /0号单元不用int len;int BinSearch(SeqList SL, KeyType k) low=1, high=SL.len; while(low<=high) mid=( low+high)/2;if(SL.datamid.key=k) return mid; /查找成功if(SL.datamid.key<k) high= mid-1; elselow= mid+1;Return 0;查找失败 10、试写一个算法,判别一行字符中的圆括号是否配对.答案：int BracketMatch(char*str)圆括号