数据结构算法设计题及答案样本.docx
- 文档编号:9692760
- 上传时间:2023-05-20
- 格式:DOCX
- 页数:10
- 大小:16.35KB
数据结构算法设计题及答案样本.docx
《数据结构算法设计题及答案样本.docx》由会员分享,可在线阅读,更多相关《数据结构算法设计题及答案样本.docx(10页珍藏版)》请在冰点文库上搜索。
数据结构算法设计题及答案样本
数据构造算法设计题及答案
1、对带表头结点有序单链表,编写算法向单链表中插入元素x,使其保持有序。
答案:
typedefdatatypeint;
structnode//结点构造
{datatypedata;
node*next;
};
//注:
也可以用自然语言描述
voidinsertOrder(node*head,datatypex)//记录
{node*s;
p=head;
while(p->next->data 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结点前插入新元素b voidins_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前一种结点q p->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前一种结点q if(q->next==NULL) return(0);//链表中无删除元素 p=q->next;q->next=p->next;//删除q下一种结点p deletep;//释放结点p存储空间 return (1); } 4、对带表头结点单链表,编写算法记录单链表中不不大于x元素个数。 答案: typedefdatatypeint; structnode//结点构造 {datatypedata; node*next; }; //注: 也可以用自然语言描述 intCountX(node*head,datatypex)//记录 {intnum=0; p=head->next; while(p) { if(p->data>x)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,h2 if(root==NULL)return0;//空树 h1=height(root->lchild); h2=height(root->rchild); return1+(h1>=h2)? h1: h2; } //阐明: 算法表达形式及办法各种各样,不可拘泥于固法。 9、编写对有序顺序表折半查找算法。 答案: #defineMaxSize100 typedefstruct {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].key high=mid-1; else low=mid+1; } Return0;//查找失败 } } 10、试写一种算法,鉴别一行字符中圆括号与否配对。 答案: intBracketMatch(char*str) {//圆括号配对鉴别,配对返回1,否则返回0 Stacks; 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; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法 设计 答案 样本