数据结构上机考试试题(C++语言版)(共5页).doc
精选优质文档-倾情为你奉上数据结构上机考试试题（C+语言版）考试要求：本次考试共列考核试题4大题，考生可以在所列4个考核试题中任选3个小题（即可能只属于2个大题），作为上机考核试题。考核原则：所选题目在上机编程调试通过后即为考核通过。监考教师依据学生编程及调试通过与否情况给予考核成绩。考核成绩评分标准：所选3个题目全部编写出程序并调试通过：优所选3个题目全部编写出程序，但只有2个上机调试通过：良所选3个题目全部编写出程序，但只有1个上机调试通过：及格所选3个题目全部编写出程序但都没有上机调试通过，或没有编写出全部程序：不及格。考核时间：2小时。考核试题：1、建立一个顺序方式存储的线性表，向表中输入若干元素后进行以下操作： （1）向线性表的表头、表尾或合适位置插入元素 （2）对线性表按升序或降序输出2、建立一个动态链接方式存储的线性表，向表中输入若干元素后进行以下操作：（1）从单链表中查找指定元素（2）返回单链表中指定序号的结点值3、建立一个动态链接结构存储的二叉树，向这棵二叉树进行以下操作：（1）按任中序遍历次序输出二叉树中的所有结点 （2）求二叉树的叶子数4、编写一个对整型数组An+1中的A1至An元素进行选择排序的算法，使得首先从待排序区间中选择出一个最大值并同最后一个元素交换，再从待排序区间中选择出一个最小值并同最第一个元素交换，反复进行直到待排序区间中元素的个数不超过1为止。#include<iomanip.h>#include<stdlib.h>#include"linearlist1.h"/初始化线性表void InitList(LinearList& L, int ms) L.list=new ElemTypems;if(!L.list) cerr<<"Memory 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& L) return L.size=0;/检查线性表是否为满bool ListFull(LinearList& L) return L.size=L.MaxSize;/遍历线性表void TraverList(LinearList& L) for(int i=0; i<L.size; i+) cout<<L.listi<<' 'cout<<endl;/从线性表中查找元素bool FindList(LinearList& L, ElemType& item) for(int i=0; i<L.size; i+)if(L.listi=item) item=L.listi;return true;return false;/更新线性表中的给定元素bool UpdateList(LinearList& L, const ElemType& item) for(int i=0; i<L.size; i+)if(L.listi=item) L.listi=item;return true;return false;/向线性表的表头、表尾或合适位置插入元素bool InsertList(LinearList& L, const ElemType& item, int mark) if(ListFull(L) return false;if(mark>0) for(int i=L.size-1; i>=0; i-)L.listi+1=L.listi;L.list0=item; else if(mark<0) L.listL.size=item;else for(int i=0; i<L.size; i+) if(item<L.listi) break; for(int j=L.size-1; j>=i; j-) L.listj+1=L.listj; L.listi=item;L.size+;return true;/从线性表中删除表头、表尾或等于给定值的元素bool DeleteList(LinearList& L, ElemType& item, int mark)if(ListEmpty(L) return false;if(mark>0) item=L.list0;for(int i=1; i<L.size; i+)L.listi-1=L.listi; else if(mark<0) item=L.listL.size-1;else for(int i=0; i<L.size; i+) if(L.listi=item) break; if(i>=L.size) return false; else item=L.listi; for(int j=i+1; j<L.size; j+) L.listj-1=L.listj;L.size-;return true;/对线性表按升序或降序输出void OrderOutputList(LinearList& L, int mark)int* b=new intL.size;int i,k;for(i=0; i<L.size; i+)bi=i;for(i=1; i<L.size; i+) k=i-1;for(int j=i; j<L.size; j+) if(mark=1 && L.listbj<L.listbk) k=j; if(mark!=1 && L.listbk<L.listbj) k=j;if(k!=i-1) int x=bi-1; bi-1=bk; bk=x;for(i=0; i<L.size; i+)cout<<L.listbi<<' 'cout<<endl;#include<iomanip.h>const int ML=10;#include"linearlist1.h"/主文件listmain1.cppvoid main()LinearList a;InitList(a,ML);int i;ElemType x; /依次向线性表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); /按不同次序遍历输出线性表aTraverList(a);OrderOutputList(a,1);OrderOutputList(a,0); /把线性表a中的所有元素依次有序插入到一个新线性表b中" LinearList b;InitList(b,ML);for(i=0; i<a.size; i+)InsertList(b, a.listi, 0); /输出线性表bTraverList(b); /从线性表a中分别删除表头、表尾、给定值元素if(DeleteList(a,x,1) cout<<"Delete success!"<<endl;else cout<<"Delete fail!"<<endl;if(DeleteList(a,x,-1) cout<<"Delete success!"<<endl;else cout<<"Delete fail!"<<endl;cout<<"从键盘上输入一个待删除的整数:"cin>>x;if(DeleteList(a,x,0) cout<<"Delete success!"<<endl;else cout<<"Delete fail!"<<endl; /输出线性表aTraverList(a);专心-专注-专业
