数据结构上机测试题.doc

数据结构上机测试题1、 编写算法，将二个升序链表在原表空间内归并成一个升序链表。#include#includetypedef struct elemtype int data; struct elemtype *next; LinkList;LinkList *UnionList(LinkList *&la,LinkList *lb)LinkList *pa=la-next,*pb=lb-next,*s,*r=la;while(pa!=NULL&pb!=NULL)if(pa-datadata)r=pa;pa=pa-next;elses=(LinkList *)malloc(sizeof(LinkList);s-data=pb-data;s-next=pa;r-next=s;r=s;pb=pb-next;if(pb!=NULL) r-next=pb;return la;LinkList * Create() LinkList *head;head=(LinkList*)malloc(sizeof(LinkList);LinkList *p,*q=head; int temp=1; while(1) scanf(%d,&temp); if(temp!=0) p=(LinkList*)malloc(sizeof(LinkList); p-data=temp; q-next=p;q=p; elseq-next=NULL; break; return head;void main() LinkList *a,*b,*p; printf(请输入第一个序列:(以0结束)n); a=Create(); printf(请输入第二个序列:(以0结束)n); b=Create();UnionList(a,b); printf(排序后的序列为：n);p=a-next; while(p!=NULL) printf(%dn,p-data); p=p-next;2、 编写算法，将二个升序链表在原表空间内归并成一个降序链表。#include#includetypedef int ElemType;typedef struct LNodeElemType data;struct LNode *next;LinkList;void CreateList(LinkList *&L,ElemType a,int n)LinkList *r,*s;int i;L=(LinkList *)malloc(sizeof (LinkList);r=L;for(i=0;idata =ai;r-next =s;r=s;r-next=NULL;void DispList(LinkList *L)LinkList *p=L-next ;while(p!=NULL)printf(%d,p-data );p=p-next ;printf(n);void DestroyList(LinkList *L)LinkList *p=L,*q=p-next ;while(q!=NULL)free(p);p=q;q=q-next ;free(p);LinkList *combine(LinkList *&L1,LinkList *&L2)LinkList *p=L1-next ;LinkList *q=L2-next;LinkList *r;while(p!=NULL&q!=NULL)if(p-data q-data )r=q;q=q-next ;L2-next =q;r-next =L1-next ;L1-next =r;else if(p-data data )if(p-next )if(p-next -data q-data ) r=q; q=q-next ; r-next =p-next ; p-next =r; p=r ;else p=p-next ;else r=p;r-next =q;p=NULL;if(q=NULL)L2-next =NULL;free(L2);return L1;void nixu(LinkList *&L)LinkList *p=L-next ,*q;L-next =NULL;while(p)q=p-next ;p-next =L-next ;L-next=p;p=q;void main()LinkList *L1,*L2;int a10,b10;int i;printf(请升序输入五个整数);for(i=0;i5;i+)scanf(%d,&ai);printf(请再按升序输入五个整数);for(i=0;i5;i+)scanf(%d,&bi);CreateList(L1,a,5);CreateList(L2,b,5); L1=combine(L1,L2);nixu(L1);DispList(L1);3、 编写算法，用顺序存储结构实现二个升序集合的AB运算。#include#include#define Maxsize 100typedef int ElemType;typedef structElemType dataMaxsize;int length;SqList;void CreateList(SqList *&L,ElemType a,int n)int i;L=(SqList *)malloc(sizeof(SqList);for(i=0;idatai=ai;L-length=n;void ListDelete(SqList *&L,int i)int j;for(j=i;jlength-1;j+)L-dataj=L-dataj+1;L-length-;SqList *minus(SqList *&L1,SqList *L2)int m=L1-length;int n=L2-length;int k=0,i,j;for(i=0;im;i+)for(j=k;jdatai=L2-dataj)ListDelete(L1,i);k=j+1;return L1;void display(SqList *L)int i;for(i=0;ilength;i+)printf(%d ,L-datai);void main()SqList *L1,*L2,*L=NULL;int a10,b10,i;printf(请输入4个升序数字:);for(i=0;i4;i+)scanf(%d,&ai);printf(请再输入4个升序数字:);for(i=0;i4;i+)scanf(%d,&bi);CreateList(L1,a,4);CreateList(L2,b,4); L1=minus(L1,L2);display(L1);4、 编写算法，将一单链表就地逆置#include#includetypedef struct lnode char data;struct lnode *next;linklist;int listinsert(linklist *&l,int i,char e)int j=0;linklist *p=l,*s;while(jnext ;if(p=NULL)return 0;else s=(linklist*)malloc(sizeof(linklist);s-data=e;s-next=p-next;p-next=s;return 1;void displist(linklist *l) linklist *p=l-next;while(p!=NULL)printf(%c,p-data);p=p-next;printf(n);void reverse(linklist *&l)linklist *p=l-next,*q;l-next=NULL;while(p!=NULL)q=p-next;p-next=l-next;l-next=p;p=q;void main()linklist *l;l=(linklist*)malloc(sizeof(linklist);l-next=NULL;listinsert(l,1,a);listinsert(l,2,b); listinsert(l,3,c);displist(l);reverse(l);displist(l);5、 编写算法，删除一升序单链表中所有值相同的多余元素，释放被删结点空间。#include #include typedef struct _list int v; struct _list* n;*node;node create(int* beg, int* end) / 从数组创建链表 node root, *cur; cur = &root; while(beg != end) *cur = (node)malloc(sizeof(_list); (*cur)-v = *beg+; (*cur)-n = NULL; cur = &(*cur)-n; return root;void traversal(node root) / 遍历输出 while(root) printf(%d , root-v); root = root-n; putchar(n);void slice(node bbeg, node end) / 切除指定范围内的节点 node t = bbeg-n; bbeg-n = end-n; end-n = NULL; bbeg = t; while(bbeg) t = bbeg; bbeg = bbeg-n; free(t); void unique(node root) node p, c, dp; int f;c = root-n; p = root; dp = NULL; f = 0; while(c) if(!f & c-v = p-v) dp = p; f = 1; else if(f & c-v != p-v) slice(dp, p); f = 0;dp = NULL; p = c; c = c-n; if(dp) slice(dp, p);void destruct(node root) node t; while(root) t = root; root = root-n; free(t); int main() int a = 0,0,1,2,2,2,3,4,4,5,5,5,5,6,7,8,8,9,9,9; node root; root = create(a, a + sizeof(a)/sizeof(int); traversal(root); unique(root); traversal(root); destruct(root); return 0;6、 编写算法，删除一升序单链表中所有值在mink,maxk之间的元素，释放被删结点空间。#include #include #include typedef int ElemType;typedef struct LNode ElemType data; struct LNode *next; LNode; LNode *creatL() LNode *h,*p,*s; ElemType x; h=(LNode *)malloc(sizeof(LNode); h-next=NULL; p=h; printf(输入一串数字 ); scanf(%d,&x); while( x!=-1) s=(LNode *)malloc(sizeof(LNode); s-data=x; s-next=NULL; p-next=s; p=s; scanf(%d,&x); return(h); void dispL(LNode *L) LNode *p; p=L-next; printf(n数据是:); while(p!=NULL) printf(%d,p-data); p=p-next; void deleteL(LNode *L,int mink,int maxk) LNode *p,*q; p=L; q=p; p=p-next; if(p=NULL) printf(链表为空); while(p!=NULL) if(p-data mink) & (p-data next=p-next; free(p); p=q-next; else q=p; p=p-next; void main()LNode *L; int mink,maxk; L=creatL( ); dispL(L); printf(n请输入要删除的元素的范围x和y:n); scanf(%d%d,&mink,&maxk); deleteL(L,mink,maxk); dispL(L); printf(n);7、 编写算法，判断一表达式中的括号是否配对，包括大、中、小三类括号。#include#include#include#define max 10000typedef struct char bracesmax;int top;SeqStack;void InitStack(SeqStack *p);void Print(char expression);void Choose(int choice,char expression);void InputForm(char expression);void JudgeForm(char expression);int Match(char x,char y);void Push(SeqStack *p,char x);void Pop(SeqStack *p);int main(void)/SeqStack S;/SeqStack *p;/p=&S;/InitStack(p);char expressionmax= ;Print(expression);while(true) printf(按enter键继续.); getchar(); getchar(); system(cls); Print(expression);return 0;void InitStack(SeqStack *p)p-top=-1;void Print(char expression)int choice; printf(1.输入一个带括号的数学表达式.n);printf(2.判断当前表达式是否合法.n);printf(3.按其它任意键退出.n);printf(-n);printf(请选择你要的操作:);scanf(%d,&choice);Choose(choice,expression);void Choose(int choice,char expression)switch(choice)case 1: InputForm(expression); break;case 2: JudgeForm(expression); break;default: exit(0);void InputForm(char expression)printf(请输入一个数学表达式:n);scanf(%s,expression);printf(输入成功！n);void JudgeForm(char expression)printf(当前表达式:);printf(%s,expression);SeqStack S;SeqStack *p;p=&S;InitStack(p);int flag=1;int length;int i;length=strlen(expression);for(i=0;itop+;p-bracesp-top=x;void Pop(SeqStack *p)p-top-;8、 编写算法，计算一后缀表达式的值。#includeconst int MaxSize=100;const int MaxOp=100;struct char ch;int pri;lpri=,0,(,1,*,5,/,5,+,3,-,3,),6,rpri=,0,(,6,*,4,/,4,+,2,-,2,),1;int leftpri(char op)int i;for(i=0;iMaxOp;i+)if(lprii.ch=op)return lprii.pri;int rightpri(char op)int i;for(i=0;iMaxOp;i+)if(rprii.ch=op)return rprii.pri;int inop(char ch)if(ch=(|ch=)|ch=+|ch=-|ch=*|ch=/)return 1;elsereturn 0;int pre(char op1,char op2)if(leftpri(op1)=rightpri(op2)return 0;else if(leftpri(op1)=0&*exp=0&*postexp=9)d=10*d+*postexp-0;postexp+;st.top+;st.datast.top=d;break;postexp+;return(st.datast.top);void main()char exp=(5-2)*(4+2);char postexpMaxSize;trans(exp,postexp);coutexpendl;coutpostexpendl;coutcom(postexp);9、 编写算法，求解hanoi塔问题。#include#includevoid hanoi(int n,char x,char y,char z)if(n=1)printf(将第%d个盘片从%c移动到%cn,n,x,z);elsehanoi(n-1,x,z,y);printf(将第%d个盘片从%c移动到%cn,n,x,z);hanoi(n-1,y,x,z);void main()int n;char x,y,z;cinnxyz;hanoi(n,x,y,z);10、 编写算法，求子串t在主串s中的位置。11、 编写算法，删除主串s中所有和串t相同的子串。#include#include#define MaxSize 10typedef char ElemType;typedef struct snodechar dataMaxSize;int length;SqString;void StrAssign(SqString &s,char cstr)int i;for(i=0;cstri!=0;i+) s.datai=cstri;s.length=i;void del(SqString s,SqString t,int a)int i=0,j=0,n=0;/SqString str;while(is.length&j=t.length)an=i-t.length;n+;/i+;/i=i-t.length+1;j=0;for(;nMaxSize;n+)an=-1;void main() char sMaxSize,tMaxSize;int aMaxSize,i,j=0,r; gets(s); gets(t); SqString p,q; StrAssign(p,s); StrAssign(q,t);del(p,q,a);/*for(int n=0;nMaxSize;n+)printf(%d ,an);printf(n);*/for(i=0;ip.length;i+)if(aj=-1|i!=aj)printf(%c,p.datai);elsefor(r=0;rq.length;r+)i+;j+;i-;printf(n);12、 编写算法，实现串的比较。#include#define MaxSize 5typedef structchar dataMaxSize;int length;SqString;void StrAssign(SqString &s,char cstr)int i;for(i=0;cstri!=0;i+)s.datai=cstri;s.length=i;int Strcmp(SqString s,SqString t)int i,comlen;if(s.lengtht.length)comlen=s.length; else comlen=t.length;for(i=0;icomlen;i+)if(s.datait.datai)return 1;if(s.length=t.length)return 0;else if(s.lengtht.length)return -1;else return 1;void main()SqString s1,s2;int a,i,j;char str1MaxSize,str2MaxSize;printf(请输入两个串:n);gets(str1);gets(str2);StrAssign(s1,str1);StrAssign(s2,str2);a=Strcmp(s1,s2);printf(比较两个串:n);if(a=-1)printf(s1s2n);13、 编写算法，实现先序遍历二叉树。#include#include#includetypedef struct nodechar data;struct node *lchild;struct node *rchild;Btnode;const int Maxsize=50;void create(Btnode *&b,char *str)Btnode *stMaxsize,*p=NULL;int top=-1,k,j=0;char ch;ch=strj;b=NULL;while(ch!=0)switch(ch)case(:top+;sttop=p;k=1;break;case):top-;break;case,:k=2;break;default:p=(Btnode *)malloc(sizeof(Btnode);p-data=ch;p-lchild=p-rchild=NULL;if(b=NULL)b=p;elseswitch(k)case 1:sttop-lchild=p;break;case 2:sttop-rchild=p;break;j+;ch=strj;void preorder(Btnode *&b)if(b!=NULL)coutdata;preorder(b-lchild);preorder(b-rchild);void main()Btnode *b;char str50;cinstr;create(b,str);preorder(b);14、 编写算法，实现中序遍历二叉树。#include#includetypedef struct nodechar data;struct node *lchild;struct node *rchild;Btnode;const int Maxsize=50;void create(Btnode *&b,char *str)Btnode *stMaxsize,*p=NULL;int top=-1,k,j=0;char ch;ch=strj;b=NULL;while(ch!=0)switch(ch)case(:top+;sttop=p;k=1;break;case):top-;break;case,:k=2;break;default:p=(Btnode *)malloc(sizeof(Btnode);p-data=ch;p-lchild=p-rchild=NULL;if(b=NULL)b=p;elseswitch(k)case 1:sttop-lchild=p;break;case 2:sttop-rchild=p;break;j+;ch=strj;void preorder(Btnode *&b)if(b!=NULL)coutdata;preorder(b-lchild);preorder(b-rchild);void main()Btnode *b;char str50;cinstr;create(b,str);inorder(b);15、 编写算法，实现后序遍历二叉树。typedef struct nodechar data;struct node *lchild;struct node *rchild;Btnode;const int Maxsize=50;void create(Btnode *&b,char *str)Btnode *stMaxsize,*p=NULL;int top=-1,k,j=0;char ch;ch=strj;b=NULL;while(ch!=0)switch(ch)case(:top+;sttop=p;k=1;break;case):top-;break;case,:k=2;break;default:p=(Btnode *)malloc(sizeof(Btnode);p-data=ch;p-lchild=p-rchild=NULL;if(b=NULL)b=p;elseswitch(k)case 1:sttop-lchild=p;break;case 2:sttop-rchild=p;break;j+;ch=strj;void postorder(Btnode *&b)if(b!=NULL)postorder(b-lchild);postorder(b-rchild);coutdata;void main()Btnode *b;char str50;cinstr;create(b,str);postorder(b);16、 编写算法，实现层序遍历二叉树。#includeusing namespace std;typedef struct node char data;struct node *lchild,*rchild;BTnode;void create(BTnode*&b,char *s)BTnode *st100,*p=NULL; int top =-1,k,j=0; char ch; b=NULL; ch=sj; while(sj!=0) switch(ch) case (:k=1;top+;sttop=p;break; case ,:k=2;break ; case ):top-;break; default: p=(BTnode*)malloc(sizeof(BTnode); p-data =ch; p-lchild =p-rchild =NULL; if(b=NULL) b=p; else switch(k) case 1: stto