数据结构上机考试（含答案）

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 #include #define N 5#define NULL 0/链表的存储结构typedef struct LNodeint data;struct LNode *

5、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;idata);p-next=q; /p的下一个结点指向新开辟的结点qp=q; /将p指针指向qp-next=NULL;/归并排序void mergeList(list &la,list &lb,list &lc) /将已经排好序的la,lb中的数重新排列成有序（非递减）list pa,pb,pc;pa=la-next;pb=lb-next;lc=

6、pc=la; /默认将la做为lc的头结点（lb亦可）while(pa&pb) /让pc接到数据小的结点上，直到pa,pb两者有一指向空结点if(pa-datadata) pc-next=pa;pc=pa;pa=pa-next; else pc-next=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

7、()list la,lb,lc;printf(创建两个含%d个元素的链表，请输入：n,N);creatList(la,N);creatList(lb,N);mergeList(la,lb,lc);printList(lc);2. #include #include #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=(l

8、ist)malloc(sizeof(LNode);p=l;for(int i=0;idata);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 &l,int &e)list p,q,s; /q为新插入的元素开辟一个存储空间的指针，s

9、为p前一个指针，方便插入p=l-next;s=l;while(p)if(edata)/发现要插入的元素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=p-next;/输出链表void printList(list l)list p;p=l-next;while(p) printf(%d ,p-data); p=p-next;void main()list

10、 l;int e;printf(创建%d个元素的链表，请输入%d个元素：n,N,N);creatList(l,N);printf(请输入要判断的元素：);scanf(%d,&e);if(inList(l,e)printf(YES );elseinsertList(l,e);printList(l);3. #include #include #define N 5#define NULL 0#define OK 1#define ERROR 0/链表的存储结构typedef struct LNodeint data;struct LNode *next;LNode,*list;/创建链表void

11、 creatList(list &l,int n)list p,q;l=(list)malloc(sizeof(LNode);p=l;for(int i=0;idata);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 OK; /发现在里面，返回真值p=p-n

12、ext; /否则指针后移,继续找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(请输入要判断的元素);scanf(%d,&e);if(!insertDeleteList(l,e)printf(NO );elseprintList(l);4. #

13、include #include #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;idata);p-next=q;p=q;p-next=NULL;/链表排序void sortList(list &l)list p,q,r; /p标记

14、排序的轮数int chang; /用于交换结点中的数据p=l-next;while(p-next!=NULL)q=l-next; /每次比较从首结点开始while(q-next!=NULL)r=q-next; if(q-datar-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

15、 main()list l;printf(创建%d个元素的链表，请输入%d个元素：n,N,N);creatList(l,N);sortList(l);printList(l);5. #include #include #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)

16、; scanf(%d,&l-data); /头结点也添加元素，方便输出p=l;for(int i=1;idata);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;inext; /找到指定位置的前一个位置q=p-next;do if(pos=1) printf(%d ,p-data); p=p-next; /如果指定位置为1，即按原样输出else p=p-next; printf(%d ,p-data); /不然，p先移到

17、指定的位置，输出其数据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(posN)printf(输入的位置不存在，请重新输入. );scanf(%d,&pos);printList(l,pos);11#include #include #define N 5#define NULL 0#de

18、fine 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;idata);p-next=q;p=q;p-next=l; /让最后一个p-next指针指向头结点，构成循环链表/输出链表void printList(list l,int

19、 pos)list p,q;int i;p=l;for(i=1;inext; /找到指定位置的前一个位置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;int pos;printf(创建%d个元素的循环链表，请输入%d个元素：n,N,N);creatList(l,

20、N);printf(请指明从第几个位置输出循环链表中的元素：);scanf(%d,&pos);while(posN)printf(输入的位置不存在，请重新输入. );scanf(%d,&pos);printList(l,pos);12#include #include #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=

21、(list)malloc(sizeof(LNode);p=l;for(int i=0;idata);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; /否则指针后移,继续找/没有执行return OK;语句,说明未找到while(q-next!=p) q=q-next; /找到链尾p=(list)malloc(sizeof(LNode); /为链尾重新开辟空间p-data=e;

22、/接到链尾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 main()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 #include

23、 #define OK 1#define Error 0#define NULL 0#define maxSize 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; /栈的大小为maxSizeretur

24、n OK;/进栈操作int push(stack &s,int e)*s.top=e; /先将元素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;in

25、;i+)scanf(%d,&e);push(s,e);while(s.base!=s.top)printf(%d ,pop(s,e);14#include #include #include #include #define stackincrement 8#define OK 1#define Error 0#define NULL 0#define maxSize 100/栈的存储结构typedef struct char *base; /由于要存放括号，所以为char类型char *top;int size;stack;/栈的初始化（顺序存储）int initStack(stack &s

26、) /注意开辟的空间为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;int isEmpty(stack s)return s.base=s.top?OK:Error;/出栈操作char pop(stack &s,char &e)if(isEmpty(

27、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);while(chi!=n) scanf(%c,&ch+i); /先将所有输入的括号存放在数组ch中 lenth=i-1; /数组的长度，不包括ni=0;push(s,chi); /先将第一个括号压栈if(chi=|chi=)|

28、chi=) flag=0; /如果第一个压入的是右括号，则肯定不匹配，flag=0else while(idata=ch; /生成根结点 CreateBiTree(T-lchild);/构造左子树 CreateBiTree(T-rchild);/构造右子树 return OK; /CreateBiTreeint PrintElement(int e) /输出元素e的值 printf(%c,e); return OK;int InOrderTraverse(BiTree T,int(*Visit)(int e) /采用二叉链表存储结构，visit是对数据元素操作的应用函数， /中序遍历二叉树T的

29、递归算法，对每个数据元素调用函数visit。 /调用实例： InOrderTraverse(T,printElement); if(T) if (InOrderTraverse(T-lchild,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); InO

30、rderTraverse(t,PrintElement); printf(n);16#include 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) /按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。 /构造二叉链表表示的

31、二叉树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-rchild);/构造右子树 return OK; /CreateBiTreeint PrintElement(int e) /输出元素e的值 printf(%c,e); return OK;int PreOrderTraverse(BiTree T,int(*Visi

32、t)(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; /preOrderTraVersevoid main() BiTree t; printf(

33、请按先序遍历输入二叉树（当左右子树为空时用空格输入）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/二叉树的二叉链表存储结构typedef struct BiTNode int data; struct BiTNode *lchild,*rchild; /左右孩子指针 BiTnode,*BiTre

34、e;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-rchild);/构造右子树 return OK; /CreateBiTreeint PrintElement(int e)

35、 /输出元素e的值 printf(%c,e); return OK;int PostOrderTraverse(BiTree T,int(*Visit)(int e) /采用二叉链表存储结构，visit是对数据元素操作的应用函数， /后序遍历二叉树T的递归算法，对每个数据元素调用函数visit。 /调用实例： PostOrderTraverse(T,printElement); if(T) if (PostOrderTraverse(T-lchild,Visit) if (PostOrderTraverse(T-rchild,Visit) if (Visit(T-data)return OK;

36、 return ERROR;else return OK; void main() BiTree t; printf(请按先序遍历输入二叉树（当左右子树为空时用空格输入）n); CreateBiTree(t); printf(该二叉树的后序遍历为：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;/二叉树的二

37、叉链表存储结构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) return -1; T-data=ch; /生成根结点 CreateBiTre

38、e(T-lchild);/构造左子树 CreateBiTree(T-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,Visi

39、t) return OK; return 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,*rchild; /左右孩子指针 BiTnode,*BiTree;int CreateBiTree(BiTree &T) /按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。 /构造二叉链表表示的二叉树T. char ch; scanf(%c,&ch); if(ch= ) T=NULL; else if(!(T=(BiTNode *)malloc(sizeof(BiTNode