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

数据结构算法设计题及答案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、 对带表头结点的单链表，编写算法求单链表的长度答案：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的结点前插入新元素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;//新结点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); //链表中无删除的元素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->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,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 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

答案：int BracketMatch(char*str){ 〃圆括号配对判别，配对返回1，否则返回0Stack 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;}。