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

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

2、： （1）向線(xiàn)性表的表頭、表尾或合適位置插入元素 （2）對(duì)線(xiàn)性表按升序或降序輸出2、建立一個(gè)動(dòng)態(tài)鏈接方式存儲(chǔ)的線(xiàn)性表，向表中輸入若干元素后進(jìn)行以下操作：（1）從單鏈表中查找指定元素（2）返回單鏈表中指定序號(hào)的結(jié)點(diǎn)值3、建立一個(gè)動(dòng)態(tài)鏈接結(jié)構(gòu)存儲(chǔ)的二叉樹(shù)，向這棵二叉樹(shù)進(jìn)行以下操作：（1）按任中序遍歷次序輸出二叉樹(shù)中的所有結(jié)點(diǎn) （2）求二叉樹(shù)的葉子數(shù)4、編寫(xiě)一個(gè)對(duì)整型數(shù)組An+1中的A1至An元素進(jìn)行選擇排序的算法，使得首先從待排序區(qū)間中選擇出一個(gè)最大值并同最后一個(gè)元素交換，再?gòu)拇判騾^(qū)間中選擇出一個(gè)最小值并同最第一個(gè)元素交換，反復(fù)進(jìn)行直到待排序區(qū)間中元素的個(gè)數(shù)不超過(guò)1為止。#include#inc

3、lude#includelinearlist1.h/初始化線(xiàn)性表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;/清空線(xiàn)性表void ClearList(LinearList& L) L.size=0;/求線(xiàn)性表長(zhǎng)度int ListSize(LinearList& L) return L.size;/檢查線(xiàn)性表是否為空bool ListEmpty(LinearList&

4、L) return L.size=0;/檢查線(xiàn)性表是否為滿(mǎn)bool ListFull(LinearList& L) return L.size=L.MaxSize;/遍歷線(xiàn)性表void TraverList(LinearList& L) for(int i=0; iL.size; i+) coutL.listi ;coutendl;/從線(xiàn)性表中查找元素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;/更新線(xiàn)性表中的給定元素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;/從線(xiàn)性表中刪除表頭、表尾或等于給定值的元素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;/對(duì)線(xiàn)性表按升序或降序輸出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; /依次向線(xiàn)性表a表尾插入5個(gè)整數(shù)元素cout從鍵盤(pán)輸入5個(gè)整數(shù):;for(i=0; ix;InsertList(a,x,-1); /依次向線(xiàn)性表a表頭插入2個(gè)整數(shù)元素coutx;InsertList(a,x,1);cinx;InsertList(a,x,1); /按不同次序遍歷輸出線(xiàn)性表aTraverList(a);OrderOutputList(a,1);OrderOutputList(a,0); /把線(xiàn)性表a中的所有元素依次有序插入到一個(gè)新線(xiàn)性表b中 LinearList b;InitList(b,ML);for(i=0; ia.size; i+)InsertList(b, a.listi, 0); /輸出線(xiàn)性表bTraverList(b); /從線(xiàn)性表a中分別刪除表頭、表尾、給定值元素if(DeleteList(a,x,1) coutDelete success!endl;else coutDelete fail!endl;if(DeleteList(a,x,-1) coutDel