数据结构上机考试(含答案)

1、数据结构上机练习题1、设有两个有序序列，利用归并排序将它们排成有序表，并输出。2、设有一有序序列，从键盘输入一个数，判别是否在序列中，如果在输出“YSE”；否则，将它插入到序列中使它仍然有序，并输出排序后的序列。3、设有一有序序列，从键盘输入一个数，判别是否在序列中，如果不在，则输出“NO”，否则，将它从序列中删除它，并输出删除后的序列。4、从键盘输入一组任意数据，建立一个有序链表，并从链头开始输出该链，使输出结果是有序的。5、从键盘输入一组任意数据，建立一个包含所有输入数据的单向循环链表，并从链表的任意开始，依次输出该链表中的所有结点。10、设有一个链表，（自己建立，数据从键盘输入），再从键

2、盘输入一个数，判别是否在链表中，如果不在，则输出“NO“，否则，将它从链表中删除，并输出删除后的链表。11、设有一个链表，（自己建立，数据从键盘输入），再从键盘输入一个数，判别是否在链表中，如果在输出“YSE”，否则，将它从插入到链头，并输出插入后的链表。12、设有一个链表，（自己建立，数据从键盘输入），再从键盘输入一个数，判别是否在链表中，如果在输出“YSE”，否则，将它从插入到链尾，并输出插入后的链表。13、编写栈的压栈push、弹栈pop函数，从键盘输入一组数据，逐个元素压入堆栈，然后再逐个从栈中弹出它们并输出。14、编写栈的压栈push、弹栈pop函数，用它判别（）的匹配问题。15、按

3、类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树中序遍历的结果。16、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树先序遍历的结果。17、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树后序遍历的结果。18、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树的总结点数。19、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树叶子结点数。20、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出此二叉树的高度。21、给出一个无向图的邻接矩阵，输出各个顶点的度。22、给出一个有向图

4、的邻接矩阵，输出各个顶点的入度与出度。23、输入一个有序序列，利用折半查找来查找一个数是否在序列中，如在，则输出其位置，否则输出“NO”。24、用插入排序方法对一组数据进行排序，并输出每趟排序的结果。25、用选择排序方法对一组数据进行排序，并输出每趟排序的结果。26、用希尔（SHELL）排序方法对一组数据进行排序，并输出每趟排序的结果。27、用快速排序方法对一组数据进行排序，并输出每趟排序的结果。答案：1. #include <stdio.h>#include <stdlib.h>#define N 5#define NULL 0/链表的存储结构typedef stru

5、ct LNodeint data;struct LNode *next;LNode,*list;/顺序创建链表void creatList(list &l,int n)int i;list p,q;l=(list)malloc(sizeof(LNode); /开辟头结点p=l; /指针p指向头结点for(i=0;i<n;i+)q=(list)malloc(sizeof(LNode); /新的结点scanf("%d",&q->data);p->next=q; /p的下一个结点指向新开辟的结点qp=q; /将p指针指向qp->next=N

6、ULL;/归并排序void mergeList(list &la,list &lb,list &lc) /将已经排好序的la,lb中的数重新排列成有序（非递减）list pa,pb,pc;pa=la->next;pb=lb->next;lc=pc=la; /默认将la做为lc的头结点（lb亦可）while(pa&&pb) /让pc接到数据小的结点上，直到pa,pb两者有一指向空结点if(pa->data<=pb->data) pc->next=pa;pc=pa;pa=pa->next; else pc->n

7、ext=pb;pc=pb;pb=pb->next; pc->next=pa?pa:pb; /如果最后la有剩余结点，即将其直接加入到lc中，反之将lb的剩余结点加到lc中free(lb);void printList(list l)list p;p=l->next;while(p) printf("%d ",p->data);p=p->next;void main()list la,lb,lc;printf("创建两个含%d个元素的链表，请输入：n",N);creatList(la,N);creatList(lb,N);me

8、rgeList(la,lb,lc);printList(lc);2. #include <stdio.h>#include <stdlib.h>#define N 5#define NULL 0#define OK 1#define ERROR 0/链表的存储结构typedef struct LNodeint data;struct LNode *next;LNode,*list;/创建链表void creatList(list &l,int n)list p,q;l=(list)malloc(sizeof(LNode);p=l;for(int i=0;i<

9、;n;i+)q=(list)malloc(sizeof(LNode);scanf("%d",&q->data);p->next=q;p=q;p->next=NULL;/判断元素e是否在链表中int inList(list l,int e)list p;p=l->next;while(p)if(p->data=e) return OK; /发现在里面，返回真值p=p->next; /否则指针后移,继续找return ERROR; /未找到，返回假值（没有执行return OK;语句）/插入元素void insertList(list

10、 &l,int &e)list p,q,s; /q为新插入的元素开辟一个存储空间的指针，s为p前一个指针，方便插入p=l->next;s=l;while(p)if(e<=p->data)/发现要插入的元素e比后面的小,开辟空间，并将e放入空间的数据域中q=(list)malloc(sizeof(LNode);q->data=e;while(s->next!=p) s=s->next; /找到p前的一个指针q->next=p; / 画图好好理解 ->s->p-> s->next=q; / q->break;p

11、=p->next;/输出链表void printList(list l)list p;p=l->next;while(p) printf("%d ",p->data); p=p->next;void main()list l;int e;printf("创建%d个元素的链表，请输入%d个元素：n",N,N);creatList(l,N);printf("请输入要判断的元素：");scanf("%d",&e);if(inList(l,e)printf("YES ")

12、;elseinsertList(l,e);printList(l);3. #include <stdio.h>#include <stdlib.h>#define N 5#define NULL 0#define OK 1#define ERROR 0/链表的存储结构typedef struct LNodeint data;struct LNode *next;LNode,*list;/创建链表void creatList(list &l,int n)list p,q;l=(list)malloc(sizeof(LNode);p=l;for(int i=0;i&

13、lt;n;i+)q=(list)malloc(sizeof(LNode);scanf("%d",&q->data);p->next=q;p=q;p->next=NULL;/判断元素e是否在链表中int insertDeleteList(list l,int e)list p,q;p=l->next; q=l;while(p)if(p->data=e) while(q->next!=p) q=q->next; /找到p前一个结点，方便删除操作q->next=p->next; /删除结点pfree(p);return

14、 OK; /发现在里面，返回真值p=p->next; /否则指针后移,继续找return ERROR; /未找到，返回假值（没有执行return OK;语句）/输出链表void printList(list l)list p;p=l->next;while(p) printf("%d ",p->data); p=p->next;void main()list l;int e;printf("创建%d个元素的链表，请输入%d个元素：n",N,N);creatList(l,N);printf("请输入要判断的元素"

15、);scanf("%d",&e);if(!insertDeleteList(l,e)printf("NO ");elseprintList(l);4. #include <stdio.h>#include <stdlib.h>#define N 5#define NULL 0#define OK 1#define ERROR 0/链表的存储结构typedef struct LNodeint data;struct LNode *next;LNode,*list;/创建链表void creatList(list &l

16、,int n)list p,q;l=(list)malloc(sizeof(LNode);p=l;for(int i=0;i<n;i+)q=(list)malloc(sizeof(LNode);scanf("%d",&q->data);p->next=q;p=q;p->next=NULL;/链表排序void sortList(list &l)list p,q,r; /p标记排序的轮数int chang; /用于交换结点中的数据p=l->next;while(p->next!=NULL)q=l->next; /每次比较

17、从首结点开始while(q->next!=NULL)r=q->next; if(q->data>r->data) /发现前一个比后一个大，交换数据 chang=q->data;q->data=r->data;r->data=chang; q=q->next; /相邻间下一个比较p=p->next; /下一轮比较/输出链表void printList(list l)list p;p=l->next;while(p) printf("%d ",p->data); p=p->next;void m

18、ain()list l;printf("创建%d个元素的链表，请输入%d个元素：n",N,N);creatList(l,N);sortList(l);printList(l);5. #include <stdio.h>#include <stdlib.h>#define N 5#define NULL 0#define OK 1#define ERROR 0/链表的存储结构typedef struct LNodeint data;struct LNode *next;LNode,*list;/创建链表void creatList(list &

19、l,int n)list p,q;l=(list)malloc(sizeof(LNode); scanf("%d",&l->data); /头结点也添加元素，方便输出p=l;for(int i=1;i<n;i+)q=(list)malloc(sizeof(LNode);scanf("%d",&q->data);p->next=q;p=q;p->next=l; /让最后一个p->next指针指向头结点，构成循环链表/输出链表void printList(list l,int pos)list p,q;in

20、t i;p=l;for(i=1;i<pos-1;i+) p=p->next; /找到指定位置的前一个位置q=p->next;do if(pos=1) printf("%d ",p->data); p=p->next; /如果指定位置为1，即按原样输出else p=p->next; printf("%d ",p->data); /不然，p先移到指定的位置，输出其数据while(p->next!=q); /结束条件（p移到的下一个位置不是q，即不是最初的p,完成循环输出）void main()list l;in

21、t pos;printf("创建%d个元素的循环链表，请输入%d个元素：n",N,N);creatList(l,N);printf("请指明从第几个位置输出循环链表中的元素：");scanf("%d",&pos);while(pos<=0|pos>N)printf("输入的位置不存在，请重新输入. ");scanf("%d",&pos);printList(l,pos);11#include <stdio.h>#include <stdlib.h&g

22、t;#define N 5#define NULL 0#define OK 1#define ERROR 0/链表的存储结构typedef struct LNodeint data;struct LNode *next;LNode,*list;/创建链表void creatList(list &l,int n)list p,q;l=(list)malloc(sizeof(LNode); scanf("%d",&l->data); /头结点也添加元素，方便输出p=l;for(int i=1;i<n;i+)q=(list)malloc(sizeof(

23、LNode);scanf("%d",&q->data);p->next=q;p=q;p->next=l; /让最后一个p->next指针指向头结点，构成循环链表/输出链表void printList(list l,int pos)list p,q;int i;p=l;for(i=1;i<pos-1;i+) p=p->next; /找到指定位置的前一个位置q=p->next;do if(pos=1) printf("%d ",p->data); p=p->next; /如果指定位置为1，即按原样

24、输出else p=p->next; printf("%d ",p->data); /不然，p先移到指定的位置，输出其数据while(p->next!=q); /结束条件（p移到的下一个位置不是q，即不是最初的p,完成循环输出）void main()list l;int pos;printf("创建%d个元素的循环链表，请输入%d个元素：n",N,N);creatList(l,N);printf("请指明从第几个位置输出循环链表中的元素：");scanf("%d",&pos);while(p

25、os<=0|pos>N)printf("输入的位置不存在，请重新输入. ");scanf("%d",&pos);printList(l,pos);12#include <stdio.h>#include <stdlib.h>#define N 5#define NULL 0#define OK 1#define ERROR 0/链表的存储结构typedef struct LNodeint data;struct LNode *next;LNode,*list;/创建链表void creatList(list &

26、amp;l,int n)list p,q;l=(list)malloc(sizeof(LNode);p=l;for(int i=0;i<n;i+)q=(list)malloc(sizeof(LNode);scanf("%d",&q->data);p->next=q;p=q;p->next=NULL;/判断元素e是否在链表中int inList(list l,int e)list p,q;q=p=l->next;while(p)if(p->data=e) return OK; /发现在里面，返回真值p=p->next; /否则

27、指针后移,继续找/没有执行return OK;语句,说明未找到while(q->next!=p) q=q->next; /找到链尾p=(list)malloc(sizeof(LNode); /为链尾重新开辟空间p->data=e; /接到链尾p->next=q->next;q->next=p;return ERROR; /未找到，返回假值/输出链表void printList(list l)list p;p=l->next;while(p) printf("%d ",p->data); p=p->next;void ma

28、in()list l;int e;printf("创建%d个元素的链表，请输入%d个元素：n",N,N);creatList(l,N);printf("请输入要判断的元素：");scanf("%d",&e);if(inList(l,e)printf("YES ");elseprintList(l);13#include <stdio.h>#include <stdlib.h>#define OK 1#define Error 0#define NULL 0#define maxSiz

29、e 100/栈的存储结构typedef struct int *base;int *top;int size;stack;/栈的初始化（顺序存储）int initStack(stack &s) /开辟maxSize大小的空间，base和top都指向基地址,同时判断是否开辟成功，不成功返回0if(!(s.base=s.top=(int*)malloc(maxSize*sizeof(int) return Error; s.size=maxSize; /栈的大小为maxSizereturn OK;/进栈操作int push(stack &s,int e)*s.top=e; /先将元

30、素e赋值给s.top所指的存储空间s.top+; /top指针上移return OK;/出栈操作int pop(stack &s,int &e)if(s.base=s.top) return Error; /如果栈为空，返回0s.top-; /top指针先后移e=*s.top; /将其所指的元素值赋给ereturn e; void main()stack s;int n,e;printf("请输入要创建栈的元素的个数：");scanf("%d",&n);initStack(s);for(int i=0;i<n;i+)scan

31、f("%d",&e);push(s,e);while(s.base!=s.top)printf("%d ",pop(s,e);14#include <stdlib.h>#include <stdio.h>#include <stdio.h>#include <stdlib.h>#define stackincrement 8#define OK 1#define Error 0#define NULL 0#define maxSize 100/栈的存储结构typedef struct char *b

32、ase; /由于要存放括号，所以为char类型char *top;int size;stack;/栈的初始化（顺序存储）int initStack(stack &s) /注意开辟的空间为char类型if(!(s.base=s.top=(char*)malloc(maxSize*sizeof(char) return Error; s.size=maxSize; /栈的大小为maxSizereturn OK;/进栈操作int push(stack &s,int e)*s.top=e; /先将元素e赋值给s.top所指的存储空间s.top+; /top指针上移return OK;i

33、nt isEmpty(stack s)return s.base=s.top?OK:Error;/出栈操作char pop(stack &s,char &e)if(isEmpty(s) return Error; /如果栈为空，返回0s.top-; /top指针先后移e=*s.top; /将其所指的元素值赋给ereturn e; /括号匹配int match()stack s;initStack(s);char ch100,e;int flag=1,i=0 ,lenth; /flag用于标记，如果匹配，值为1，否则为0scanf("%c",&chi)

34、;while(chi!='n') scanf("%c",&ch+i); /先将所有输入的括号存放在数组ch中 lenth=i-1; /数组的长度，不包括'n'i=0;push(s,chi); /先将第一个括号压栈if(chi=''|chi=')'|chi='') flag=0; /如果第一个压入的是右括号，则肯定不匹配，flag=0else while(i<lenth)/|!emptystack(s)i+;char t;if(chi=''|chi=')

35、9;|chi='') t=pop(s,e); /弹出先前压入的元素，将后继输入的括号与先前压入的比较 if(t!=chi-1)&&(t!=chi-2) flag=0;break; /左右小括号与左右大括号的ASCII码都相差1，左右中括号相差2，如果不满足，则不匹配，直接退出循环 else push(s,chi); /输入的是左括号，直接压入 if(!isEmpty(s) flag=0; /通过不断的压栈和弹栈，如果最后栈不为空，则肯定是左括号多于右括号，不匹配return flag;void main()int result;printf("判断输入

36、的各种括号是否匹配：n");result=match();if(result) printf("括号匹配正确 _n");else printf("括号匹配错误 *.*n");15#include "stdio.h"#include "stdlib.h"#define stackinitsize 100#define OK 1#define ERROR 0/二叉树的二叉链表存储结构typedef struct BiTNode int data; struct BiTNode *lchild,*rchild;

37、 /左右孩子指针 BiTnode,*BiTree;int CreateBiTree(BiTree &T) /按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。 /构造二叉链表表示的二叉树T. char ch; scanf("%c",&ch); if(ch=' ') T=NULL; else if(!(T=(BiTNode *)malloc(sizeof(BiTNode) exit(0); T->data=ch; /生成根结点 CreateBiTree(T->lchild);/构造左子树 CreateBiTree(T-&

38、gt;rchild);/构造右子树 return OK; /CreateBiTreeint PrintElement(int e) /输出元素e的值 printf("%c",e); return OK;int InOrderTraverse(BiTree T,int(*Visit)(int e) /采用二叉链表存储结构，visit是对数据元素操作的应用函数， /中序遍历二叉树T的递归算法，对每个数据元素调用函数visit。 /调用实例： InOrderTraverse(T,printElement); if(T) if (InOrderTraverse(T->lchi

39、ld,Visit) if (Visit(T->data) if (InOrderTraverse(T->rchild,Visit) return OK; return ERROR;else return OK; void main() BiTree t; printf("请按先序遍历输入二叉树（当左右子树为空时用空格输入）n"); CreateBiTree(t); printf("该二叉树的中序遍历为：n"); InOrderTraverse(t,PrintElement); printf("n");16#include

40、"stdio.h"#include "stdlib.h"#define stackinitsize 100#define OK 1#define ERROR 0/二叉树的二叉链表存储结构typedef struct BiTNode int data; struct BiTNode *lchild,*rchild; /左右孩子指针 BiTnode,*BiTree;int CreateBiTree(BiTree &T) /按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。 /构造二叉链表表示的二叉树T. char ch; scanf(&q

41、uot;%c",&ch); if(ch=' ') T=NULL; else if(!(T=(BiTNode *)malloc(sizeof(BiTNode) exit(0); T->data=ch; /生成根结点 CreateBiTree(T->lchild);/构造左子树 CreateBiTree(T->rchild);/构造右子树 return OK; /CreateBiTreeint PrintElement(int e) /输出元素e的值 printf("%c",e); return OK;int PreOrder

42、Traverse(BiTree T,int(*Visit)(int e) /采用二叉链表存储结构，visit是对数据元素操作的应用函数， /先序遍历二叉树T的递归算法，对每个数据元素调用函数visit。 /调用实例： PreOrderTraverse(T,printElement); if(T) if (Visit(T->data) if (PreOrderTraverse(T->lchild,Visit) if (PreOrderTraverse(T->rchild,Visit) return OK; return ERROR;else return OK; /preOrd

43、erTraVersevoid main() BiTree t; printf("请按先序遍历输入二叉树（当左右子树为空时用空格输入）n"); CreateBiTree(t); printf("该二叉树的先序遍历为：n"); PreOrderTraverse(t,PrintElement); printf("n");17#include "stdio.h"#include "stdlib.h"#define stackinitsize 100#define OK 1#define ERROR 0/

44、二叉树的二叉链表存储结构typedef struct BiTNode int data; struct BiTNode *lchild,*rchild; /左右孩子指针 BiTnode,*BiTree;int CreateBiTree(BiTree &T) /按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。 /构造二叉链表表示的二叉树T. char ch; scanf("%c",&ch); if(ch=' ') T=NULL; else if(!(T=(BiTNode *)malloc(sizeof(BiTNode) exit(

45、0); T->data=ch; /生成根结点 CreateBiTree(T->lchild);/构造左子树 CreateBiTree(T->rchild);/构造右子树 return OK; /CreateBiTreeint PrintElement(int e) /输出元素e的值 printf("%c",e); return OK;int PostOrderTraverse(BiTree T,int(*Visit)(int e) /采用二叉链表存储结构，visit是对数据元素操作的应用函数， /后序遍历二叉树T的递归算法，对每个数据元素调用函数visit

46、。 /调用实例： PostOrderTraverse(T,printElement); if(T) if (PostOrderTraverse(T->lchild,Visit) if (PostOrderTraverse(T->rchild,Visit) if (Visit(T->data)return OK; return ERROR;else return OK; void main() BiTree t; printf("请按先序遍历输入二叉树（当左右子树为空时用空格输入）n"); CreateBiTree(t); printf("该二叉树

47、的后序遍历为：n"); PostOrderTraverse(t,PrintElement); printf("n");18#include "stdio.h"#include "stdlib.h"#define stackinitsize 100#define OK 1#define ERROR 0/#define NULL 0static int count=0;/二叉树的二叉链表存储结构typedef struct BiTNode int data; struct BiTNode *lchild,*rchild; /左右

48、孩子指针 BiTnode,*BiTree;int CreateBiTree(BiTree &T) /按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。 /构造二叉链表表示的二叉树T. char ch; scanf("%c",&ch); if(ch=' ') T=NULL; else if(!(T=(BiTNode *)malloc(sizeof(BiTNode) return -1; T->data=ch; /生成根结点 CreateBiTree(T->lchild);/构造左子树 CreateBiTree(T->

49、;rchild);/构造右子树 return OK; /CreateBiTreeint PrintElement(int e) /记录遍历结点数 count+; return OK;int PreOrderTraverse(BiTree T,int(*Visit)(int e) /采用二叉链表存储结构，visit是对数据元素操作的应用函数， if(T) if (Visit(T->data) if (PreOrderTraverse(T->lchild,Visit) if (PreOrderTraverse(T->rchild,Visit) return OK; return

50、ERROR;else return OK; /preOrderTraVersevoid main() BiTree t; printf("请按先序遍历输入二叉树（当左右子树为空时用空格输入）n"); CreateBiTree(t); printf("该二叉树的总结点数为: "); PreOrderTraverse(t,PrintElement); printf("%dn",count);19#include "stdio.h"#include "stdlib.h"#define stackinitsize 100#define OK 1#define ERROR 0static int count=0;/二叉树的二叉链表存储结构typedef struct BiTNode int data; struct BiTNode *lchild,*r