《数据结构算法设计题及答案》由会员分享，可在线阅读，更多相关《数据结构算法设计题及答案（7页珍藏版）》请在金锄头文库上搜索。
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 -datanext;s=( node *)malloc(sizeof(node);s-data=x;s-next= p-next;p-next=s;2、对带表头结点的单链表，编写算法求单链表的长
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的结点前插入新
3、元素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-next!=NULL)&(q-next)-d)!=x)q=q-next;/寻找包含元素x的前一个结点q p-next=q-next;q-next=p;/
4、新结点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的前一个结点qif (q-next=NULL)return(0); /链表
5、中无删除的元素p=q-next; q-next=p-next;/删除 q 的下一个结点 pdelete 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-datax) num+ ;p=p-next;return num;5、对带表
6、头结点的单链表，编写算法将单链表就地逆置。答案：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 d
7、ata;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-fro
8、nt-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-da
9、ta);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、对以二叉链表存储的二叉树，编写对二叉树进
10、行中序遍历的算法，以及求二叉树高度的 算法。答案：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
11、,h2if(root=NULL) return 0; / 空树h1=height (root-lchild );h2= height (root-rchild );return 1+(h1=h2)?h1:h2;说明：算法的表达形式及方法多种多样，不可拘泥于固法。9、编写对有序顺序表的折半查找算法。答案：#define MaxSize 100typedef struct KeyType key;OtherType otherData;datatype;struct SeqList /结点结构 datatype dataMaxSize; /0 号单元不用 int len;int BinSearch
12、(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.keyk)high= mid-1;elselow= mid+1;Return 0;/查找失败10、试写一个算法，判别一行字符中的圆括号是否配对。答案：int BracketMatch(char*str)圆括号配对判别，配对返回1，否则返回0Stack s;InitStack(&s);for(i=0; stri; i+)switch( stri) case (： Push(&s, stri); break;case )： if( IsEmpty(s) ) return 0;Pop(&s);if( IsEmpty(s) ) return 1;return 0;
