数据结构期末数据结构实验测试题（含答案）

某顺序表（自己定义、建立），查找某数据元素，找到返回位序，找不到返回0某顺序表（自己定义、建立），在合法的位置插入某数据元素某顺序表（自己定义、建立），在合法的位置删除某数据元素某顺序表（自己定义、建立），就地逆置（即不另设置空间）用头插法建立单链表，并输出用尾插法建立单链表，并输出某单链表（自己定义、建立），就地逆置（即不另设置空间）某单链表（自己定义、建立），查找某数据元素，找到返回位序，找不到返回0某单链表（自己定义、建立），求其长度某单链表（自己定义、建立），在合法的位置插入某数据元素某单链表（自己定义、建立），在合法的位置删除某数据元素某单链表（自己定义、建立），在最后位置插入或删除某二叉链表（自己定义、建立），输出前序、中序、后序遍历序列某二叉链表（自己定义、建立），求其高度（深度）某二叉链表（自己定义、建立），求其叶子结点数某二叉链表（自己定义、建立），求其总结点个数某二叉链表（自己定义、建立），将其左右子树交换方式：抽签，单人单桌，每组8-10人，杜绝作弊！时间：<30分钟总分：100分数据结构C语言描述10分数据结构建立30分基本操作30分主函数20分运行结果10分用途：20%计入学业成绩1.某顺序表（自己定义、建立），查找某数据元素，找到返回位序，找不到返回0#include<stdio.h>typedefstruct{intelem[100];intlength;}sqlist;voidcreate(sqlist*L,intn){inti; printf("请输入%d个数：\n",n); for(i=0;i<n;i++)scanf("%d",&L->elem[i]); L->length=n;}voidprint(sqlistL,intn){inti; printf("顺序表为："); for(i=0;i<n;i++)printf("-%d",L.elem[i]); printf("\n");}intlocate(sqlistL,intn){inti,e; printf("请输入需要查找的数：\n"); scanf("%d",&e); for(i=0;i<n;i++) { if(L.elem[i]==e) { printf("找到该数据：%d\n该数据的位置是：%d\n",e,i); } continue; return0; }}main(){sqlistl;intm;printf("输入此顺序表总数据的个数："); scanf("%d",&m);create(&l,m);print(l,m); locate(l,m);}2.某顺序表（自己定义、建立），在合法的位置插入某数据元素#include<stdio.h>typedefstruct{intelem[100];intlength;}sqlist;voidcreate(sqlist*L,intn){inti; printf("请输入%d个数：\n",n); for(i=0;i<n;i++)scanf("%d",&L->elem[i]); L->length=n;}voidprint(sqlistL,intn){inti; printf("顺序表为："); for(i=0;i<n;i++)printf("-%d",L.elem[i]); printf("\n");}voidinsert(sqlist*L,inti,inte){ intj;if((i<1)||(i>L->length+1)) printf("error"); for(j=L->length;j>=i-1;j--) L->elem[j]=L->elem[j-1]; L->elem[i-1]=e; L->length++;}main(){sqlistl;intm,e,i;printf("输入此顺序表总数据的个数："); scanf("%d",&m);create(&l,m);print(l,m); printf("请输入需要插入的数据：\n"); scanf("%d",&e); printf("请输入需要插入数的位置：\n"); scanf("%d",&i); insert(&l,i,e); print(l,l.length);}3.某顺序表（自己定义、建立），在合法的位置删除某数据元素#include<stdio.h>typedefstruct{intelem[100];intlength;}sqlist;voidcreate(sqlist*L,intn){inti; printf("请输入%d个数：\n",n); for(i=0;i<n;i++)scanf("%d",&L->elem[i]); L->length=n;}voidprint(sqlistL,intn){inti; printf("顺序表为："); for(i=0;i<n;i++)printf("-%d",L.elem[i]); printf("\n");}voiddel(sqlist*L,inti){ intj;if((i<1)||(i>L->length+1)) printf("error"); for(j=i;j<=L->length-1;j++) L->elem[j-1]=L->elem[j]; L->length--;}main(){sqlistl;intm,e;printf("输入此顺序表总数据的个数："); scanf("%d",&m);create(&l,m);print(l,m); printf("请输入需要删除数据位置：\n"); scanf("%d",&e); del(&l,e); print(l,l.length);}4.某顺序表（自己定义、建立），就地逆置（即不另设置空间）#include<stdio.h>typedefstruct{intelem[100];intlength;}sqlist;voidcreate(sqlist*L,intn){inti; printf("请输入%d个数：\n",n); for(i=0;i<n;i++)scanf("%d",&L->elem[i]); L->length=n;}voidprint(sqlistL,intn){inti; printf("顺序表为："); for(i=0;i<n;i++)printf("-%d",L.elem[i]); printf("\n");}voidnizhi(sqlistL,intn){ inti,t; for(i=0;i<n/2;i++) { t=L.elem[i]; L.elem[i]=L.elem[n-i-1]; L.elem[n-i-1]=t; } for(i=0;i<n;i++)printf("-%d",L.elem[i]); printf("\n");}main(){sqlistl;intm;printf("输入此顺序表总数据的个数："); scanf("%d",&m);create(&l,m);print(l,m); printf("此顺表逆置后为：");nizhi(l,m);}5.用头插法建立单链表，并输出#include<stdio.h>typedefstructLnode{intdata;structLnode*next;}Lnode,*Linklist;Linklistcreate(intn){inti;LinklistL;Linklistp;L=newLnode;L->next=NULL;for(i=0;i<n;i++){p=newLnode; p->data=i; p->next=L->next; L->next=p;}returnL;}voidprint(LinklistL){ Linklistp; p=L->next; while(p){ printf("-%d",p->data); p=p->next;}printf("\n");}voidmain(){intm=6;Lnode*head;head=create(m);print(head);}6.用尾插法建立单链表，并输出#include<stdio.h>typedefstructLnode{intdata;structLnode*next;}Lnode,*Linklist;Linklistcreate(intn){inti;LinklistL;Linklistp;Linklistr;L=newLnode;L->next=NULL;r=L;for(i=0;i<n;i++){p=newLnode; p->data=i; r->next=p; r=p;}p->next=NULL;returnL;}voidprint(LinklistL){ Linklistp; p=L->next; while(p){ printf("-%d",p->data); p=p->next;}printf("\n");}voidmain(){intm=6;Lnode*head;head=create(m);print(head);}7.某单链表（自己定义、建立），就地逆置（即不另设置空间）#include<stdio.h>typedefstructLnode{intdata;structLnode*next;}Lnode,*Linklist;Linklistcreate(intn){inti;LinklistL;Linklistp;Linklistr;L=newLnode;L->next=NULL;r=L;for(i=0;i<n;i++){p=newLnode; p->data=i; r->next=p; r=p;}p->next=NULL;returnL;}voidprint(LinklistL){ Linklistp; p=L->next; while(p){ printf("-%d",p->data); p=p->next;}printf("\n");}voidnizhi(LinklistL){Linklistp,q;p=L;p=p->next;L->next=NULL;while(p){ q=p; p=p->next; q->next=L->next; L->next=q;}}voidmain(){intm=6;Lnode*head;head=create(m);print(head);printf("此逆置单链表为");nizhi(head);print(head);}8.某单链表（自己定义、建立），查找某数据元素，找到返回位序，找不到返回0#include<stdio.h>typedefstructLnode{intdata;structLnode*next;}Lnode,*Linklist;Linklistcreate(intn){inti;LinklistL;Linklistp;Linklistr;L=newLnode;L->next=NULL;r=L;for(i=0;i<n;i++){p=newLnode; p->data=i; r->next=p; r=p;}p->next=NULL;returnL;}voidprint(LinklistL){ Linklistp; p=L->next; while(p){ printf("-%d",p->data); p=p->next;}printf("\n");}intlocate(LinklistL){inti=1,e; Linklistp; p=L->next; printf("请输入需要查找第几个的结点:"); scanf("%d",&e); while(p) { if(i==e) printf("该结点的数据域是：%d\n",p->data); else return0; p=p->next; i++; }}voidmain(){intm=6;Lnode*head;head=create(m);print(head);locate(head);}9.某单链表（自己定义、建立），求其长度#include<stdio.h>typedefstructLnode{intdata;structLnode*next;}Lnode,*Linklist;Linklistcreate(intn){inti;LinklistL;Linklistp;Linklistr;L=newLnode;L->next=NULL;r=L;for(i=0;i<n;i++){p=newLnode; p->data=i; r->next=p; r=p;}p->next=NULL;returnL;}voidprint(LinklistL){ Linklistp; p=L->next; while(p) { printf("-%d",p->data); p=p->next; } printf("\n");}intlength(LinklistL){inti=0;Linklistp; p=L->next;while(p){ p=p->next; i++;}returni;}voidmain(){intm=6;Lnode*head;head=create(m);print(head);printf("单链表长度：%d\n",length(head));}10.某单链表（自己定义、建立），在合法的位置插入某数据元素#include<stdio.h>typedefstructLnode{intdata;structLnode*next;}Lnode,*Linklist;Linklistcreate(intn){inti;LinklistL;Linklistp;Linklistr;L=newLnode;L->next=NULL;r=L;for(i=0;i<n;i++){p=newLnode; p->data=i; r->next=p; r=p;}p->next=NULL;returnL;}voidprint(LinklistL){ Linklistp; p=L->next; while(p){ printf("-%d",p->data); p=p->next;}printf("\n");}voidinsert(LinklistL,inti,inte){ intj=0; Linklistp,s; p=L;if((!p)||(j>i-1)) printf("error");while(p&&(j<i-1)) { p=p->next; ++j; } s=newLnode; s->data=e; s->next=p->next; p->next=s;}voidmain(){intm=6,i,e;Lnode*head;head=create(m);print(head);printf("请输入需要插入的数：\n"); scanf("%d",&e); printf("请输入需要插入数的位置：\n"); scanf("%d",&i); insert(head,i,e); printf("新的单链表是:"); print(head);}11.某单链表（自己定义、建立），在合法的位置删除某数据元素#include<stdio.h>typedefstructLnode{intdata;structLnode*next;}Lnode,*Linklist;Linklistcreate(intn){inti;LinklistL;Linklistp;Linklistr;L=newLnode;L->next=NULL;r=L;for(i=0;i<n;i++){p=newLnode; p->data=i; r->next=p; r=p;}p->next=NULL;returnL;}voidprint(LinklistL){ Linklistp; p=L->next; while(p){ printf("-%d",p->data); p=p->next;}printf("\n");}voiddel(LinklistL,inti){ Linklistp,q; p=L; intj=0; while(p&&(j<i-1)) { p=p->next; ++j; } q=p->next; p->next=q->next; deleteq;}voidmain(){intm=6,e;Lnode*head;head=create(m);print(head);printf("请输入需要删除的结点位置：\n"); scanf("%d",&e); del(head,e); print(head);}12.某单链表（自己定义、建立），在最后位置插入或删除#include<stdio.h>typedefstructLnode{intdata;structLnode*next;}Lnode,*Linklist;Linklistcreate(intn){inti;LinklistL;Linklistp;Linklistr;L=newLnode;L->next=NULL;r=L;for(i=0;i<n;i++){p=newLnode; p->data=i; r->next=p; r=p;}p->next=NULL;returnL;}voidprint(LinklistL){ Linklistp; p=L->next; while(p) {printf("-%d",p->data);p=p->next; } printf("\n");}voidinsert(LinklistL,inte){ Linklistp,s; p=L;while(p->next!=NULL) { p=p->next; } s=newLnode; s->data=e; s->next=p->next; p->next=s;}voiddel(LinklistL){ Linklistp,q; p=L; while(p->next!=NULL) { q=p; p=p->next; } q->next=NULL; deletep;}voidmain(){intm=6,e;Lnode*head;head=create(m);print(head);printf("请输入需要插入的数：\n"); scanf("%d",&e); insert(head,e); printf("新的单链表是:"); print(head);printf("删除后的单链表是：\n"); del(head); print(head);}13.某二叉链表（自己定义、建立），输出前序、中序、后序遍历序列#include<stdio.h>typedefstructBitnode{intdata;structBitnode*lchild,*rchild;}Bilnode,*Bitree;Bitreecreate(){charch;Bitreet;ch=getchar();if(ch=='*')t=NULL;else{t=newBilnode; t->data=ch; t->lchild=create();t->rchild=create();}returnt;}voidqianxu(Bitreet){if(t){ printf("%c",t->data);qianxu(t->lchild); qianxu(t->rchild); }}voidinorder(Bitreet){if(t){inorder(t->lchild); printf("%c",t->data); inorder(t->rchild); }}voidhouxu(Bitreet){if(t){houxu(t->lchild); houxu(t->rchild); printf("%c",t->data);}}voidmain(){ Bitreet; printf("输入："); t=create(); printf("这棵二叉树的前序遍历为:\n"); qianxu(t); printf("\n"); printf("这棵二叉树的中序遍历为:\n"); inorder(t); printf("\n"); printf("这棵二叉树的后序遍历为:\n"); houxu(t); printf("\n"); }14.某二叉链表（自己定义、建立），求其高度（深度）#include<stdio.h>typedefstructBitnode{intdata;structBitnode*lchild,*rchild;}Bilnode,*Bitree;Bitreecreate(){charch;Bitreet;ch=getchar();if(ch=='*')t=NULL;else{t=newBilnode; t->data=ch; t->lchild=create();t->rchild=create();}returnt;}intlength(Bitreet){ inth1,h2; if(t==NULL) return0;else { h1=length(t->lchild);h2=length(t->rchild); if(h1>h2) returnh1+1; else returnh2+1; }}voidmain(){ Bitreet; printf("输入："); t=create(); printf("这棵二叉树的高度为：%d\n",length(t));}15.某二叉链表（自己定义、建立），求其叶子结点数#include<stdio.h>typedefstructBitnode{intdata;structBitnode*lchild,*rchild;}Bilnode,*Bitree;Bitreecreate(){charch;Bitreet;ch=getchar();if(ch=='*')t=NULL;else{t=newBilnode; t->data=ch; t->lchild=create();t->rchild=create();}returnt;}intcountzero(Bitreet){if(t==NULL) return0;else if(t->lchild==NULL&&t->rchild==NULL) return1;else returncountzero(t->lchild)+countzero(t->rchild);}voidmain(){ Bitreet; printf("输入："); t=create(); printf("这棵二叉树叶子结点的个数为：%d\n",c