数据结构上机考试试题(C++语言版)

1、数据结构上机考试试题（C+语言版）考试要求：本次考试共列考核试题4大题，考生可以在所列4个考核试题中任选3个小题（即可能只属于2个大题），作为上机考核试题。考核原则：所选题目在上机编程调试通过后即为考核通过。监考教师依据学生编程及调试通过与否情况给予考核成绩。考核成绩评分标准：所选3个题目全部编写出程序并调试通过：优所选3个题目全部编写出程序，但只有2个上机调试通过：良所选3个题目全部编写出程序，但只有1个上机调试通过：及格所选3个题目全部编写出程序但都没有上机调试通过，或没有编写出全部程序：不及格。考核时间：2小时。考核试题：1、建立一个顺序方式存储的线性表，向表中输入若干元素后进行以下操作

2、： （1）向线性表的表头、表尾或合适位置插入元素 （2）对线性表按升序或降序输出2、建立一个动态链接方式存储的线性表，向表中输入若干元素后进行以下操作：（1）从单链表中查找指定元素（2）返回单链表中指定序号的结点值3、建立一个动态链接结构存储的二叉树，向这棵二叉树进行以下操作：（1）按任中序遍历次序输出二叉树中的所有结点 （2）求二叉树的叶子数4、编写一个对整型数组An+1中的A1至An元素进行选择排序的算法，使得首先从待排序区间中选择出一个最大值并同最后一个元素交换，再从待排序区间中选择出一个最小值并同最第一个元素交换，反复进行直到待排序区间中元素的个数不超过1为止。#include#inc

3、lude#includelinearlist1.h/初始化线性表void InitList(LinearList& L, int ms) L.list=new ElemTypems;if(!L.list) cerrMemory allocation failure!endl;exit(1); L.size=0;L.MaxSize=ms;/清空线性表void ClearList(LinearList& L) L.size=0;/求线性表长度int ListSize(LinearList& L) return L.size;/检查线性表是否为空bool ListEmpty(LinearList&

4、L) return L.size=0;/检查线性表是否为满bool ListFull(LinearList& L) return L.size=L.MaxSize;/遍历线性表void TraverList(LinearList& L) for(int i=0; iL.size; i+) coutL.listi ;coutendl;/从线性表中查找元素bool FindList(LinearList& L, ElemType& item) for(int i=0; iL.size; i+)if(L.listi=item) item=L.listi;return true;return fals

5、e;/更新线性表中的给定元素bool UpdateList(LinearList& L, const ElemType& item) for(int i=0; i0) for(int i=L.size-1; i=0; i-)L.listi+1=L.listi;L.list0=item; else if(mark0) L.listL.size=item;else for(int i=0; iL.size; i+) if(item=i; j-) L.listj+1=L.listj; L.listi=item;L.size+;return true;/从线性表中删除表头、表尾或等于给定值的元素boo

6、l DeleteList(LinearList& L, ElemType& item, int mark)if(ListEmpty(L) return false;if(mark0) item=L.list0;for(int i=1; iL.size; i+)L.listi-1=L.listi; else if(mark0) item=L.listL.size-1;else for(int i=0; i=L.size) return false; else item=L.listi; for(int j=i+1; jL.size; j+) L.listj-1=L.listj;L.size-;r

7、eturn true;/对线性表按升序或降序输出void OrderOutputList(LinearList& L, int mark)int* b=new intL.size;int i,k;for(i=0; iL.size; i+)bi=i;for(i=1; iL.size; i+) k=i-1;for(int j=i; jL.size; j+) if(mark=1 & L.listbjL.listbk) k=j; if(mark!=1 & L.listbkL.listbj) k=j;if(k!=i-1) int x=bi-1; bi-1=bk; bk=x;for(i=0; iL.siz

8、e; i+)coutL.listbi ;coutendl;#includeconst int ML=10;#includelinearlist1.h/主文件listmain1.cppvoid main()LinearList a;InitList(a,ML);int i;ElemType x; /依次向线性表a表尾插入5个整数元素cout从键盘输入5个整数:;for(i=0; ix;InsertList(a,x,-1); /依次向线性表a表头插入2个整数元素coutx;InsertList(a,x,1);cinx;InsertList(a,x,1); /按不同次序遍历输出线性表aTraverList(a);OrderOutputList(a,1);OrderOutputList(a,0); /把线性表a中的所有元素依次有序插入到一个新线性表b中 LinearList b;InitList(b,ML);for(i=0; ia.size; i+)InsertList(b, a.listi, 0); /输出线性表bTraverList(b); /从线性表a中分别删除表头、表尾、给定值元素if(DeleteList(a,x,1) coutDelete success!endl;else coutDelete fail!endl;if(DeleteList(a,x,-1) coutDel