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

数据结构算法设计题及答案1、对带表头结点的有序单链表，编写算法向单链表中插入元素x，使其保持有序。答案：typedefdatatypeint;structnode//结点结构{datatypedata;node*next;};//注：也可以用自然语言描述voidinsertOrder(node*head,datatypex)//统计{node*s;p=head;while(p-next-datax)p=p-next;s=(node*)malloc(sizeof(node));s-data=x;s-next=p-next;p-next=s;}2、对带表头结点的单链表，编写算法求单链表的长度。答案：typedefdatatypeint;structnode//结点结构{datatypedata;node*next;};//注：也可以用自然语言描述intLength(node*head)//求单链表的长度{intnum=0;node*p=head-next;while(p){num++;p=p-next;}returnnum;}3、试写出单链表的插入与删除算法，并用C编写相应的程序。答案：typedefdatatypeint;structnode//结点结构{datatypedata;node*next;};单链表的插入参考算法：//在包含元素x的结点前插入新元素bvoidins_linked_LList(node*head,datatypex,datatypeb){node*p,*q;p=newnode;//申请一个新结点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的前一个结点qp-next=q-next;q-next=p;//新结点p插入到结点q之后return;}单链表的删除参考算法：intdel_linked_LList(node*head,Tx)//删除包含元素x的结点元素{node*p,*q;if(head==NULL)return(0);//链表为空，无删除的元素if((head-d)==x)//删除第一个结点{p=head-next;deletehead;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的下一个结点pdeletep;//释放结点p的存储空间return(1);}4、对带表头结点的单链表，编写算法统计单链表中大于x的元素个数。答案：typedefdatatypeint;structnode//结点结构{datatypedata;node*next;};//注：也可以用自然语言描述intCountX(node*head,datatypex)//统计{intnum=0;p=head-next;while(p){if(p-datax)num++;p=p-next;}returnnum;}5、对带表头结点的单链表，编写算法将单链表就地逆置。答案：typedefdatatypeint;structnode//结点结构{datatypedata;node*next;};//注：也可以用自然语言描述voidReverseList(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、写出链队列的入队、出队的算法。答案：typedefdatatypeint;structnode//结点结构{datatypedata;node*next;};//注：也可以用自然语言描述structLinkQueue//结点结构{node*front;node*rear;};intEnterQueue(LinkQueue*q,datatypee){//带头结点的链队列入队q-rear-next=(node*)malloc(sizeof(node));q-rear-data=e;q-rear=q-rear-next;return1;}intDeleteQueue(LinkQueue*q,datatype*e){//带头结点的链队列出队if(q-rear==q-front)return0;p=q-front-next;*e=p-data;q-front-next=p-next;free(p);if(q-front-next==NULL)q-rear=q-front;return1;}7、编写算法对二叉链表存储的二叉树进行前序遍历，并统计二叉树中叶子结点数。答案：typedefdatatypeint;structnode//结点结构{datatypedata;node*lchild,*rchild;};//注：也可以用自然语言描述voidpreOrder(node*root)//前序遍历{if(root==NULL)return;//空树printf(%5d,root-data);preOrder(root-lchild);//前序遍历根的左子树preOrder(root-rchild);//前序遍历根的右子树}intnumOfLeaf(node*root)//统计二叉树中结点总数{if(root==NULL)return0;//空树if((root-lchild==NULL)&&(root-rchild==NULL))return1;//叶子returnnumOfLeaf(root-lchild)+numOfLeaf(root-rchild);}//说明：算法的表达形式及方法多种多样，不可拘泥于固法。8、对以二叉链表存储的二叉树，编写对二叉树进行中序遍历的算法，以及求二叉树高度的算法。答案：typedefdatatypeint;structnode//结点结构{datatypedata;node*lchild,*rchild;};//注：也可以用自然语言描述voidinOrder(node*root)//前序遍历{if(root==NULL)return;//空树inOrder(root-lchild);//中序遍历根的左子树printf(%5d,root-data);inOrder(root-rchild);//中序遍历根的右子树}intheight(node*root)//求二叉树的高度{inth1,h2if(root==NULL)return0;//空树h1=height(root-lchild);h2=height(root-rchild);return1+(h1=h2)?h1:h2;}//说明：算法的表达形式及方法多种多样，不可拘泥于固法。9、编写对有序顺序表的折半查找算法。答案：#defineMaxSize100typedefstruct{KeyTypekey;OtherTypeotherData;}datatype;structSeqList//结点结构{datatypedata[MaxSize];//0号单元不用intlen;};intBinSearch(SeqListSL,KeyTypek){low=1,high=SL.len;while(low=high){mid=(low+high)/2;if(SL.data[mid].key==k)returnmid;//查找成功if(SL.data[mid].keyk)high=mid-1;elselow=mid+1;}Return0;//查找失败}}10、试写一个算法，判别一行字符中的圆括号是否配对。答案：intBracketMatch(char*str){//圆括号配对判别,配对返回1，否则返回0Stacks;InitStack(&s);for(i=0;str[i];i++){switch(str[i]){case‘(‘:Push(&s,str[i]);break;case‘)’:if(IsEmpty(s))return0;Pop(&s);}}if(IsEmpty(s))return1;return0;}