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

数据结构上机考试试题（C++语言版）考试要求：本次考试共列考核试题4大题，考生可以在所列4个考核试题中任选3个小题（即可能只属于2个大题），作为上机考核试题。考核原则：所选题目在上机编程调试通过后即为考核通过。监考教师依据学生编程及调试通过与否情况给予考核成绩。考核成绩评分标准：所选3个题目全部编写出程序并调试通过：优所选3个题目全部编写出程序，但只有2个上机调试通过：良所选3个题目全部编写出程序，但只有1个上机调试通过：及格所选3个题目全部编写出程序但都没有上机调试通过，或没有编写出全部程序：不及格。考核时间：2小时。考核试题：1、建立一个顺序方式存储的线性表，向表中输入若干元素后进行以下操作：（1）向线性表的表头、表尾或合适位置插入元素（2）对线性表按升序或降序输出2、建立一个动态链接方式存储的线性表，向表中输入若干元素后进行以下操作：（1）从单链表中查找指定元素（2）返回单链表中指定序号的结点值3、建立一个动态链接结构存储的二叉树，向这棵二叉树进行以下操作：（1）按任中序遍历次序输出二叉树中的所有结点（2）求二叉树的叶子数4、编写一个对整型数组A[n+1]中的A[1]至A[n]元素进行选择排序的算法，使得首先从待排序区间中选择出一个最大值并同最后一个元素交换，再从待排序区间中选择出一个最小值并同最第一个元素交换，反复进行直到待排序区间中元素的个数不超过1为止。#includeiomanip.h#includestdlib.h#includelinearlist1.h//初始化线性表voidInitList(LinearList&L,intms){L.list=newElemType[ms];if(!L.list){cerrMemoryallocationfailure!endl;exit(1);}L.size=0;L.MaxSize=ms;}//清空线性表voidClearList(LinearList&L){L.size=0;}//求线性表长度intListSize(LinearList&L){returnL.size;}//检查线性表是否为空boolListEmpty(LinearList&L){returnL.size==0;}//检查线性表是否为满boolListFull(LinearList&L){returnL.size==L.MaxSize;}//遍历线性表voidTraverList(LinearList&L){for(inti=0;iL.size;i++)coutL.list[i]'';coutendl;}//从线性表中查找元素boolFindList(LinearList&L,ElemType&item){for(inti=0;iL.size;i++)if(L.list[i]==item){item=L.list[i];returntrue;}returnfalse;}//更新线性表中的给定元素boolUpdateList(LinearList&L,constElemType&item){for(inti=0;iL.size;i++)if(L.list[i]==item){L.list[i]=item;returntrue;}returnfalse;}//向线性表的表头、表尾或合适位置插入元素boolInsertList(LinearList&L,constElemType&item,intmark){if(ListFull(L))returnfalse;if(mark0){for(inti=L.size-1;i=0;i--)L.list[i+1]=L.list[i];L.list[0]=item;}elseif(mark0)L.list[L.size]=item;else{for(inti=0;iL.size;i++)if(itemL.list[i])break;for(intj=L.size-1;j=i;j--)L.list[j+1]=L.list[j];L.list[i]=item;}L.size++;returntrue;}//从线性表中删除表头、表尾或等于给定值的元素boolDeleteList(LinearList&L,ElemType&item,intmark){if(ListEmpty(L))returnfalse;if(mark0){item=L.list[0];for(inti=1;iL.size;i++)L.list[i-1]=L.list[i];}elseif(mark0)item=L.list[L.size-1];else{for(inti=0;iL.size;i++)if(L.list[i]==item)break;if(i=L.size)returnfalse;elseitem=L.list[i];for(intj=i+1;jL.size;j++)L.list[j-1]=L.list[j];}L.size--;returntrue;}//对线性表按升序或降序输出voidOrderOutputList(LinearList&L,intmark){int*b=newint[L.size];inti,k;for(i=0;iL.size;i++)b[i]=i;for(i=1;iL.size;i++){k=i-1;for(intj=i;jL.size;j++){if(mark==1&&L.list[b[j]]L.list[b[k]])k=j;if(mark!=1&&L.list[b[k]]L.list[b[j]])k=j;}if(k!=i-1){intx=b[i-1];b[i-1]=b[k];b[k]=x;}}for(i=0;iL.size;i++)coutL.list[b[i]]'';coutendl;}#includeiomanip.hconstintML=10;#includelinearlist1.h//主文件listmain1.cppvoidmain(){LinearLista;InitList(a,ML);inti;ElemTypex;//依次向线性表a表尾插入5个整数元素cout从键盘输入5个整数:;for(i=0;i5;i++){cinx;InsertList(a,x,-1);}//依次向线性表a表头插入2个整数元素cout从键盘输入2个整数:;cinx;InsertList(a,x,1);cinx;InsertList(a,x,1);//按不同次序遍历输出线性表aTraverList(a);OrderOutputList(a,1);OrderOutputList(a,0);//把线性表a中的所有元素依次有序插入到一个新线性表b中LinearListb;InitList(b,ML);for(i=0;ia.size;i++)InsertList(b,a.list[i],0);//输出线性表bTraverList(b);//从线性表a中分别删除表头、表尾、给定值元素if(DeleteList(a,x,1))coutDeletesuccess!endl;elsecoutDeletefail!endl;if(DeleteList(a,x,-1))coutDeletesuccess!endl;elsecoutDeletefail!endl;cout从键盘上输入一个待删除的整数:;cinx;if(DeleteList(a,x,0))coutDeletesuccess!endl;elsecoutDeletefail!endl;//输出线性表aTraverList(a);}