數(shù)據(jù)結(jié)構(gòu)上機(jī)考試試題(C++語言版)

1、數(shù)據(jù)結(jié)構(gòu)上機(jī)考試試題（C+語言版）考試要求：本次考試共列考核試題4大題，考生可以在所列4個(gè)考核試題中任選3個(gè)小題（即可能只屬于2個(gè)大題），作為上機(jī)考核試題?？己嗽瓌t：所選題目在上機(jī)編程調(diào)試通過后即為考核通過。監(jiān)考教師依據(jù)學(xué)生編程及調(diào)試通過與否情況給予考核成績?？己顺煽冊u分標(biāo)準(zhǔn)：所選3個(gè)題目全部編寫出程序并調(diào)試通過：優(yōu)所選3個(gè)題目全部編寫出程序，但只有2個(gè)上機(jī)調(diào)試通過：良所選3個(gè)題目全部編寫出程序，但只有1個(gè)上機(jī)調(diào)試通過：及格所選3個(gè)題目全部編寫出程序但都沒有上機(jī)調(diào)試通過，或沒有編寫出全部程序：不及格?？己藭r(shí)間：2小時(shí)。考核試題：1、建立一個(gè)順序方式存儲的線性表，向表中輸入若干元素后進(jìn)行以下操作

2、： （1）向線性表的表頭、表尾或合適位置插入元素 （2）對線性表按升序或降序輸出2、建立一個(gè)動態(tài)鏈接方式存儲的線性表，向表中輸入若干元素后進(jìn)行以下操作：（1）從單鏈表中查找指定元素（2）返回單鏈表中指定序號的結(jié)點(diǎn)值3、建立一個(gè)動態(tài)鏈接結(jié)構(gòu)存儲的二叉樹，向這棵二叉樹進(jìn)行以下操作：（1）按任中序遍歷次序輸出二叉樹中的所有結(jié)點(diǎn) （2）求二叉樹的葉子數(shù)4、編寫一個(gè)對整型數(shù)組An+1中的A1至An元素進(jìn)行選擇排序的算法，使得首先從待排序區(qū)間中選擇出一個(gè)最大值并同最后一個(gè)元素交換，再從待排序區(qū)間中選擇出一個(gè)最小值并同最第一個(gè)元素交換，反復(fù)進(jìn)行直到待排序區(qū)間中元素的個(gè)數(shù)不超過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個(gè)整數(shù)元素cout從鍵盤輸入5個(gè)整數(shù):;for(i=0; ix;InsertList(a,x,-1); /依次向線性表a表頭插入2個(gè)整數(shù)元素coutx;InsertList(a,x,1);cinx;InsertList(a,x,1); /按不同次序遍歷輸出線性表aTraverList(a);OrderOutputList(a,1);OrderOutputList(a,0); /把線性表a中的所有元素依次有序插入到一個(gè)新線性表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