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

数据结构上机考试试题(C++语言版)数据结构上机考试试题(C++语言版)数据结构上机考试试题(C++语言版)资料仅供参考文件编号：2022年4月数据结构上机考试试题(C++语言版)版本号：A修改号：1页次：1.0审核：批准:发布日期：数据结构上机考试试题（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为止。#include<>#include<>#include""//初始化线性表voidInitList(LinearList&L,intms){ =newElemType[ms]; if(!{ cerr<<"Memoryallocationfailure!"<<endl; exit(1); }=0; =ms;}//清空线性表voidClearList(LinearList&L){=0;}//求线性表长度intListSize(LinearList&L){ return;}//检查线性表是否为空boolListEmpty(LinearList&L){ return==0;}//检查线性表是否为满boolListFull(LinearList&L){ return==;}//遍历线性表voidTraverList(LinearList&L){ for(inti=0;i<;i++)cout<<[i]<<''; cout<<endl;}//从线性表中查找元素boolFindList(LinearList&L,ElemType&item){ for(inti=0;i<;i++) if[i]==item){ item=[i]; returntrue; } returnfalse;}//更新线性表中的给定元素boolUpdateList(LinearList&L,constElemType&item){ for(inti=0;i<;i++) if[i]==item){ [i]=item; returntrue; } returnfalse;}//向线性表的表头、表尾或合适位置插入元素boolInsertList(LinearList&L,constElemType&item,intmark){ if(ListFull(L))returnfalse; if(mark>0){ for(inti=;i>=0;i--) [i+1]=[i]; [0]=item; }elseif(mark<0)[]=item; else{for(inti=0;i<;i++) if(item<[i])break; for(intj=;j>=i;j--) [j+1]=[j]; [i]=item; } ++; returntrue;}//从线性表中删除表头、表尾或等于给定值的元素boolDeleteList(LinearList&L,ElemType&item,intmark){ if(ListEmpty(L))returnfalse; if(mark>0){ item=[0]; for(inti=1;i<;i++) [i-1]=[i]; }elseif(mark<0)item=[]; else{for(inti=0;i<;i++) if[i]==item)break; if(i>= returnfalse; elseitem=[i]; for(intj=i+1;j<;j++) [j-1]=[j]; } ; returntrue;}//对线性表按升序或降序输出voidOrderOutputList(LinearList&L,intmark){ int*b=newint[]; inti,k; for(i=0;i<;i++) b[i]=i; for(i=1;i<;i++){ k=i-1; for(intj=i;j<;j++){ if(mark==1&&[b[j]]<[b[k]])k=j; if(mark!=1&&[b[k]]<[b[j]])k=j; } if(k!=i-1){intx=b[i-1];b[i-1]=b[k];b[k]=x;} } for(i=0;i<;i++) cout<<[b[i]]<<''; cout<<endl;}#include<>constintML=10;#include""//主文件voidmain(){ LinearLista; InitList(a,ML); inti; ElemTypex;//依次向线性表a表尾插入5个整数元素 cout<<"从键盘输入5个整数:"; for(i=0;i<5;i++){ cin>>x; InsertList(a,x,-1); }//依次向线性表a表头插入2个整数元素 cout<<"从键盘输入2个整数:"; cin>>x; InsertList(a,x,1); cin>>x; InsertList(a,x,1);//按不同次序遍历输出线性表a TraverList(a); OrderOutputList(a,1); OrderOutputList(a,0);//把线性表a中的所有元素依次有序插入到一个新线性表b中"LinearListb; InitList(b,ML); for(i=0;i<;i++) InsertList(b,[i],0);//输出线性表b TraverList(b);//从线性表a中分别删除表头、表尾、给定值元素 if(DeleteList(a,x,1))cout<<"Deletesuccess!"<<endl; elsecout<<"Deletefail!"<<endl; if(DeleteList(a,x,-1))cout<<"Deletesuccess!"<<endl; else