數(shù)據(jù)結(jié)構(gòu)上機(jī)試題教育試題

《數(shù)據(jù)結(jié)構(gòu)上機(jī)試題教育試題》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)上機(jī)試題教育試題（22頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、數(shù)據(jù)結(jié)構(gòu)上機(jī)試題一、 順序表的操作（1）插入元素操作：將新元素x插入到順序表a中第i個(gè)位置。（2）刪除元素操作：刪除順序表a中第i個(gè)元素。#include#include#define MAX 100；typedef structint data100;int length;sqlist;void init(sqlist &a)/線性表初始化 a.length=0;void insert(sqlist &a ,int i,int x)/ 插入元素操作int j;if(ia.length+1|a.length=100);elsefor(j=a.length+1;ji;j-)a.dataj=a.d

2、ataj-1;a.dataj=x;a.length+; void deleted(sqlist &a ,int i)/ 刪除元素操作int j;if(ia.length);elsefor(j=i;ja.length;j+)a.dataj=a.dataj+1;a.length-;void main() sqlist a;/線性表為a int i,e,x,n,j,s;/i插入位置，e動(dòng)態(tài)建線性表要用，X插入元素，n表長(zhǎng) init(a);/構(gòu)造一個(gè)空表 coutn; cout輸入表長(zhǎng)為 n 個(gè)數(shù): ; for(j=0;je; insert(a,j,e); cout插入前: ; for(j=0;ja.

3、length ;j+) couta.dataj ; couti; coutx; cout打算在第i個(gè)位置插入元素x ; insert(a,i-1,x);/由于從0開(kāi)始，要構(gòu)造顯示從一開(kāi)始，所以減1 cout插入后結(jié)果: ; for(j=0;ja.length;j+) couta.dataj ; couts; deleted(a,s-1);/由于從0開(kāi)始，要構(gòu)造顯示從一開(kāi)始，所以減1 cout刪除后結(jié)果: ; for(j=0;ja.length;j+) couta.dataj ;二、單鏈表的操作（1）創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的單鏈表；（2）插入元素操作：將新元素x插入到單鏈表中第i個(gè)元素之后；（3）刪除

4、元素操作：刪除單鏈表中值為x的元素；#include#includetypedef struct LNodeint data;struct LNode *next;LNode;/創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的長(zhǎng)度長(zhǎng)度長(zhǎng)度為n的鏈表L；void createlist(LNode *&L ,int n)int i;LNode *p;L=(LNode *)malloc(sizeof(LNode);L-next=NULL;for(i=1;i=n;i+)p=(LNode *)malloc(sizeof(LNode);cout請(qǐng)輸入鏈表第ip-data;p-next=L-next;L-next=p;/插入元素操作：將

5、新元素x插入到單鏈表L中第i個(gè)元素之后void insert(LNode *&L ,int i,int x)int j=0;LNode *p,*q;p=L;while(p-next!=NULL)j+;if(j=i)q=(LNode *)malloc(sizeof(LNode);/找到位置q-data=x;/放入數(shù)據(jù)q-next=p-next;p-next=q;break;p=p-next;if(p-next=NULL)q=(LNode *)malloc(sizeof(LNode);/找到位置q-data=x;/放入數(shù)據(jù)q-next=p-next;p-next=q;/刪除元素操作：刪除單鏈表中值

6、為x的元素；void deleted(LNode *&L ,int x)LNode *p,*q;p=L;while(p-next!=NULL)if(p-next-data=x)q=p-next;p-next=p-next-next;free(q);p=p-next;void print(LNode *&L)LNode *p;p=L-next;while(p!=NULL)coutdatanext;void main()LNode * L,*p;/節(jié)點(diǎn)為L(zhǎng)int i,x,y,s,n;/i插入位置，X插入元素，y為刪除元素，n表長(zhǎng)coutn;createlist(L,n);cout輸出插入之前：;p

7、rint(L);couti;coutx;insert(L,i,x);cout輸出插入后：;print(L);couty;deleted(L,y);/刪除元素操作：刪除單鏈表中值為y的元素；cout輸出刪除后：;print(L);三、在順序棧上實(shí)現(xiàn)將非負(fù)十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)#include#include#define MAX 100/在順序棧上實(shí)現(xiàn)將非負(fù)十進(jìn)制數(shù)x轉(zhuǎn)換成二進(jìn)制數(shù)void conversion(int &x)int stackMAX;int top=-1;int t;while(x)stack+top=x%2;x=x/2;while(top!=-1)t=stacktop-;co

8、utt;void main()int x,t;cout請(qǐng)輸入你要轉(zhuǎn)換的非負(fù)十進(jìn)制數(shù)x:x;cout輸出轉(zhuǎn)換后的二進(jìn)制數(shù):;conversion(x);coutendl;四、在順序表中采用順序查找算法和折半查找算法尋找關(guān)鍵字X在順序表中的位置。#include#include#define MAX 100/在順序表中采用順序查找算法和折半查找算法尋找關(guān)鍵字X在順序表中的位置typedef struct int dataMAX;int length;sqlist;void init(sqlist &a)/線性表初始化 a.length=0;void insert(sqlist &a ,int i,

9、int x)/ 插入元素操作int j;if(ia.length+1|a.length=100);elsefor(j=a.length+1;ji;j-)a.dataj=a.dataj-1;a.dataj=x;a.length+; int search(sqlist &sq,int x)/順序查找算法int i;for(i=0;isq.length;i+)/順序表存儲(chǔ)從0開(kāi)始if(sq.datai=x)return i;int hsearch(sqlist &sq,int low,int high,int x)/折半查找算法int mid;while(lowx)high=mid-1;else i

10、f(sq.datamidx)low=mid+1;void main() sqlist sq;/線性表為sq int i,e,x,y,n;/i插入位置，x,y要查找元素，n表長(zhǎng) init(sq);/構(gòu)造一個(gè)空表 coutn; cout輸入表長(zhǎng)為 n 個(gè)數(shù): ; for(i=0;ie; insert(sq,i,e); cout查找前（便于判斷）:endl; for(i=0;isq.length ;i+) coutsq.datai ; coutendl; cout采用順序查找算法： endl; coutendl; coutx; coutendl; cout關(guān)鍵字x在順序表中的位置為search(sq

11、,x)+1endl; /下表從0開(kāi)始，+1顯示時(shí)，轉(zhuǎn)化成從1開(kāi)始了 cout采用折半查找算法： endl; coutendl; couty; coutendl; cout關(guān)鍵字y在順序表中的位置為hsearch(sq,1,sq.length,y)+1endl; 五、將無(wú)序數(shù)列使用直接插入排序算法和快速排序算法將其排成遞增有序數(shù)列。#include#include#define MAX 100/將無(wú)序數(shù)列使用直接插入排序算法和快速排序算法將其排成遞增有序數(shù)列typedef struct int dataMAX;int length;sqlist;void init(sqlist &a)/線性表初

12、始化 a.length=0;void insert(sqlist &a ,int i,int x)/ 插入元素,構(gòu)造無(wú)序數(shù)列int j;if(ia.length+1|a.length=100);elsefor(j=a.length+1;ji;j-)a.dataj=a.dataj-1;a.dataj=x;a.length+; /將哨兵放在a.datan中，被排序的記錄放在a.data0.n-1中，直接插入排序算法。void insertsort(sqlist &a)/直接插入排序算法int i,j;int n=a.length;for(i=n-2;i=0;i-) if(a.dataia.data

13、i+1) a.datan=a.datai;/a.datan是哨兵 j=i+1; do a.dataj-1=a.dataj; j+;while(a.dataja.datan);a.dataj-1=a.datan;int Partition(sqlist &a,int i,int j)int pivot=a.datai;while(ij)while(i=pivot) j-; if(ij) a.datai+=a.dataj; while(ij&a.datai=pivot) i+; if(ij) a.dataj-=a.datai; a.datai=pivot; return i;void QuickS

14、ort(sqlist &a,int low,int high)/快速排序 int pivotpos; /劃分后的基準(zhǔn)記錄的位置if(lowhigh)/僅當(dāng)區(qū)間長(zhǎng)度大于1時(shí)才須排序pivotpos=Partition(a,low,high); QuickSort(a,low,pivotpos-1); QuickSort(a,pivotpos+1,high); void main() sqlist sq1,sq2;/線性表為sq1,sq2 int i,e,x,n1,n2;/n表長(zhǎng) init(sq1);/構(gòu)造一個(gè)空表 coutn1; cout輸入表長(zhǎng)為 n1 個(gè)數(shù): ; for(i=0;ie; in

15、sert(sq1,i,e);/ 插入元素,構(gòu)造無(wú)序數(shù)列 cout無(wú)序數(shù)列為:endl; for(i=0;isq1.length ;i+) coutsq1.datai ; coutendl; insertsort(sq1); cout直接插入排序后數(shù)列為:endl; for(i=0;isq1.length ;i+) coutsq1.datai ; coutendl; coutendl; coutendl; init(sq2);/構(gòu)造一個(gè)空表 coutn2; cout輸入表長(zhǎng)為 n2 個(gè)數(shù): ; for(i=0;ie; insert(sq2,i,e);/ 插入元素,構(gòu)造無(wú)序數(shù)列 cout無(wú)序數(shù)列為:endl; for(i=0;isq2.length ;i+) coutsq2.datai ; coutendl; QuickSort(sq2,0, n2-1); cout快速排序后數(shù)列為:endl; for(i=0;isq2.length ;i+) coutsq2.datai ; coutendl;22借鑒試題