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

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-

2、>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 i

3、nt;struct node /结点结构 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

4、=head;while (q->next!=NULL)&&(q->next)->d)!=x)q=q->next;/寻找包含元素x的前一个结点qp->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->nex

5、t; delete 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的下一个结点pdelete p;/释放结点p的存储空间return(1);4、 对带表头结点的单链表，编写算法统计单链表中大于x的元素个数。答案：typedef datatype in

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

7、d 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 * re

8、ar; 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-

9、>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(&

10、quot;%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 )+ numOf

11、Leaf (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("

12、;%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 100type

13、def 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) /