《数据结构上机考试(含答案).docx》由会员分享，可在线阅读，更多相关《数据结构上机考试(含答案).docx（54页珍藏版）》请在三一文库上搜索。
1、数据结构上机练习题1、设有两个有序序列 , 利用归并排序将它们排成有序表 ,并输出。2、设有一有序序列 , 从键盘输入一个数 , 判别是否在序列中 ,如果在输出 “YSE”;否则, 将它插入到序列中使它仍然有序 , 并输出排序后的序列。3、设有一有序序列 ,从键盘输入一个数 ,判别是否在序列中 ,如果不在 ,则输出 “NO”,否则 ,将它从序列中删除它 , 并输出删除后的序列。4、从键盘输入一组任意数据 ,建立一个有序链表 , 并从链头开始输出该链 ,使 输出结果是有序的。5、从键盘输入一组任意数据 ,建立一个包含所有输入数据的单向循环链表 , 并 从链表的任意开始 , 依次输出该链表中的所有
2、结点。10、设有一个链表 ,（ 自己建立, 数据从键盘输入 ）, 再从键盘输入一个数 ,判别 是否在链表中 , 如果不在 , 则输出“ NO“,否则, 将它从链表中删除 , 并输出删除后的 链表。11、设有一个链表 ,（ 自己建立, 数据从键盘输入 ）, 再从键盘输入一个数 ,判别 是否在链表中,如果在输出“ YSE”,否则,将它从插入到链头 ,并输出插入后的链表。12、设有一个链表 ,（ 自己建立, 数据从键盘输入 ）, 再从键盘输入一个数 ,判别是否在链表中,如果在输出“ YSE”,否则,将它从插入到链尾 ,并输出插入后的链表。13、编写栈的压栈 push、弹栈 pop函数, 从键盘输入一
3、组数据 ,逐个元素压入堆栈, 然后再逐个从栈中弹出它们并输出14、编写栈的压栈 push、弹栈 pop函数,用它判别() 的匹配问题15、按类似先序遍历结果输入一序列, 建立一棵二叉树 ( 算法6、4), 输出二叉树中序遍历的结果。16、按类似先序遍历结果输入一序列, 建立一棵二叉树 ( 算法6、4), 输出二叉树先序遍历的结果。17、按类似先序遍历结果输入一序列, 建立一棵二叉树 ( 算法6、4), 输出二叉树后序遍历的结果。18、按类似先序遍历结果输入一序列, 建立一棵二叉树 ( 算法6、4), 输出二叉树的总结点数。19、按类似先序遍历结果输入一序列, 建立一棵二叉树 ( 算法6、4),
4、 输出二叉树叶子结点数。20、按类似先序遍历结果输入一序列, 建立一棵二叉树 ( 算法6、4), 输出此二叉树的高度。21、给出一个无向图的邻接矩阵 , 输出各个顶点的度。22、给出一个有向图的邻接矩阵 , 输出各个顶点的入度与出度。,如在, 则输23、输入一个有序序列 , 利用折半查找来查找一个数是否在序列中 出其位置 ,否则输出“ NO”。24、用插入排序方法对一组数据进行排序 , 并输出每趟排序的结果。25、用选择排序方法对一组数据进行排序 , 并输出每趟排序的结果。26、用希尔 (SHELL)排序方法对一组数据进行排序 ,并输出每趟排序的结果。27、用快速排序方法对一组数据进行排序 ,
5、 并输出每趟排序的结果。 答案:1. #include #include #define N 5#define NULL 0/ 链表的存储结构typedef struct 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;idata);p-next=q; /p 的下一个结点指向新开辟的结点 qp=q; / 将 p 指针指向 qp-n
6、ext=NULL;/ 归并排序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-datadata) pc-next=pa;pc=pa;pa=pa-next; else pc-next=pb;pc=pb;pb=pb-next; pc-
7、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);mergeList(la,lb,lc);printList(lc);2. #include #include
8、#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-next=NULL;/ 判断元素 e 是否在链表中int inList(list l,int e)list p;p=l-next;while(p
9、)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 为 p前一个指针, 方便插入p=l-next;s=l;while(p)if(edata)/ 发现要插入的元素 e比后面的小,开辟空间,并将 e放入空间的数据域中 q=(list)malloc(sizeof(LNode);q-data=e;wh
10、ile(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;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 );
11、elseinsertList(l,e); printList(l);3. #include #include #define N 5 #define NULL 0 #define OK 1 #define ERROR 0 / 链表的存储结构 typedef struct LNode int 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=NU
12、LL;/ 判断元素 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-next; / 否则指针后移 ,继续找return ERROR; / 未找到,返回假值 （没有执行 return OK; 语句） / 输出链表void printList(list l)list
13、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. #include #include #define N 5 #define NULL 0 #define OK 1 #define ERROR 0 / 链表的存储结构
14、typedef struct LNode int 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标记排序的轮数int chang; / 用于交换结点中的数据p=l-next;while(p-next!=NULL)q=l-next; / 每次比较从
15、首结点开始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 main()list l;printf( 创建%d个元素的链表 , 请输入 %d个元素:n,N,N);creatList(l,N)
16、;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);scanf(%d,&l-data); / 头结点也添加元素 , 方便输出p=l;for(int i=1;idata);
17、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;doif(pos=1) printf(%d ,p-data); p=p-next; / 如果指定位置为 1, 即按原样输出else p=p-next; printf(%d ,p-data); /不然 ,p 先移到指定的位置 ,输出其数据while(p-next!=q); / 结束条件 (p 移到的下一个位置
18、不是 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#define OK 1#define ERROR 0/ 链
19、表的存储结构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 pos)list p,q;int
20、 i;for(i=1;inext; /找到指定位置的前一个位置q=p-next;doif(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,N);pri
21、ntf( 请指明从第几个位置输出循环链表中的元素 :); 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)l=(list
22、)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-data=e; / 接p=(list)malloc(sizeof(LNode);
23、 / 为链尾重新开辟空间 到链尾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
24、);13#include #include #define OK 1#define Error 0#define NULL 0#define maxSize 100/ 栈的存储结构typedef structint *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
25、;s.size=maxSize; / 栈的大小为 maxSizereturn 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; /将其所指的元素值赋给 e return e;void main()stack s;int n,e;printf（ 请输入要创建栈的
26、元素的个数 :）;scanf(%d,&n);initStack(s);for(int i=0;in;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 structchar *base; / 由于要存放括号 , 所以为 char 类型 char
27、 *top; int size;stack;/ 栈的初始化 (顺序存储 )int initStack(stack &s) / 注意开辟的空间为 char 类型 if(!(s.base=s.top=(char*)malloc(maxSize*sizeof(char) returnError;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)r
28、eturn 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);while(chi!=n) scanf(%c,&ch+i)
29、; / 先将所有输入的括号存放在 数组 ch 中 lenth=i-1; /数组的长度 , 不包括 ni=0;push(s,chi); / 先将第一个括号压栈if(chi=|chi=)|chi=) flag=0; / 如果第一个压入的是 右括号 , 则肯定不匹配,flag=0else while(idata=ch; / 生成根结点CreateBiTree(T-lchild);/ 构造左子树CreateBiTree(T-rchild);/ 构造右子树return OK;/CreateBiTreeint PrintElement(int e) / 输出元素 e 的值printf(%c,e);retu
30、rn OK;int InOrderTraverse(BiTree T,int(*Visit)(int e)/ 采用二叉链表存储结构 ,visit 是对数据元素操作的应用函数/ 中序遍历二叉树 T的递归算法 , 对每个数据元素调用函数 visit 。/ 调用实例 :InOrderTraverse(T,printElement);if(T)if (InOrderTraverse(T-lchild,Visit)if (V isit(T-data)if (InOrderTraverse(T-rchild,Visit) return OK;return ERROR;else return OK;void
31、 main()BiTree t;printf( 请按先序遍历输入二叉树 ( 当左右子树为空时用空格输入 )n);CreateBiTree(t);printf( 该二叉树的中序遍历为 :n);InOrderTraverse(t,PrintElement);printf(n);16#include stdio.h#include stdlib.h#define stackinitsize 100#define OK 1#define ERROR 0/ 二叉树的二叉链表存储结构typedef struct BiTNodeint data;struct BiTNode *lchild,*rchild;
32、 /左右孩子指针BiTnode,*BiTree;int CreateBiTree(BiTree &T)/ 按先序次序输入二叉树中结点的值 (一个字符 ), 空格字符表示空树 / 构造二叉链表表示的二叉树 T.char ch;scanf(%c,&ch);if(ch= ) T=NULL;elseif(!(T=(BiTNode *)malloc(sizeof(BiTNode) exit(0);T-data=ch; / 生成根结点CreateBiTree(T-lchild);/ 构造左子树CreateBiTree(T-rchild);/ 构造右子树return OK;/CreateBiTreeint
33、PrintElement(int e) / 输出元素 e 的值printf(%c,e);return OK;int PreOrderTraverse(BiTree T,int(*Visit)(int e)/ 采用二叉链表存储结构 ,visit 是对数据元素操作的应用函数/ 先序遍历二叉树 T的递归算法 , 对每个数据元素调用函数 visit/ 调用实例 :PreOrderTraverse(T,printElement);if(T)if (V isit(T-data)if (PreOrderTraverse(T-lchild,Visit)if (PreOrderTraverse(T-rchild
34、,Visit) return OK;return ERROR;else return OK;/preOrderTraV ersevoid 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/ 二叉树的二
35、叉链表存储结构typedef struct BiTNodeint data;struct BiTNode *lchild,*rchild; /左右孩子指针BiTnode,*BiTree;int CreateBiTree(BiTree &T)/ 按先序次序输入二叉树中结点的值 (一个字符 ), 空格字符表示空树/ 构造二叉链表表示的二叉树 T.char ch;scanf(%c,&ch);if(ch= ) T=NULL;elseif(!(T=(BiTNode *)malloc(sizeof(BiTNode) exit(0);T-data=ch; / 生成根结点CreateBiTree(T-lchi
36、ld);/ 构造左子树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/ 调用实例 :PostOrderTraverse(T,printElement);if(T)if (PostOrder
37、Traverse(T-lchild,Visit)if (PostOrderTraverse(T-rchild,V isit)if (V isit(T-data)return OK;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;/ 二叉树的二叉链表存储结构typedef struct BiTNodeint data;struct Bi