數(shù)據(jù)結(jié)構(gòu)上機(jī)考試(含答案).doc

數(shù)據(jù)結(jié)構(gòu)上機(jī)練習(xí)題1、設(shè)有兩個(gè)有序序列，利用歸并排序?qū)⑺鼈兣懦捎行虮?，并輸出?、設(shè)有一有序序列，從鍵盤輸入一個(gè)數(shù)，判別是否在序列中，如果在輸出“YSE”；否則，將它插入到序列中使它仍然有序，并輸出排序后的序列。3、設(shè)有一有序序列，從鍵盤輸入一個(gè)數(shù)，判別是否在序列中，如果不在，則輸出“NO”，否則，將它從序列中刪除它，并輸出刪除后的序列。4、從鍵盤輸入一組任意數(shù)據(jù)，建立一個(gè)有序鏈表，并從鏈頭開始輸出該鏈，使輸出結(jié)果是有序的。5、從鍵盤輸入一組任意數(shù)據(jù)，建立一個(gè)包含所有輸入數(shù)據(jù)的單向循環(huán)鏈表，并從鏈表的任意開始，依次輸出該鏈表中的所有結(jié)點(diǎn)。10、設(shè)有一個(gè)鏈表，（自己建立，數(shù)據(jù)從鍵盤輸入），再從鍵盤輸入一個(gè)數(shù)，判別是否在鏈表中，如果不在，則輸出“NO“，否則，將它從鏈表中刪除，并輸出刪除后的鏈表。11、設(shè)有一個(gè)鏈表，（自己建立，數(shù)據(jù)從鍵盤輸入），再從鍵盤輸入一個(gè)數(shù)，判別是否在鏈表中，如果在輸出“YSE”，否則，將它從插入到鏈頭，并輸出插入后的鏈表。12、設(shè)有一個(gè)鏈表，（自己建立，數(shù)據(jù)從鍵盤輸入），再從鍵盤輸入一個(gè)數(shù)，判別是否在鏈表中，如果在輸出“YSE”，否則，將它從插入到鏈尾，并輸出插入后的鏈表。13、編寫棧的壓棧push、彈棧pop函數(shù)，從鍵盤輸入一組數(shù)據(jù)，逐個(gè)元素壓入堆棧，然后再逐個(gè)從棧中彈出它們并輸出。14、編寫棧的壓棧push、彈棧pop函數(shù)，用它判別（）的匹配問題。15、按類似先序遍歷結(jié)果輸入一序列，建立一棵二叉樹（算法6、4），輸出二叉樹中序遍歷的結(jié)果。16、按類似先序遍歷結(jié)果輸入一序列，建立一棵二叉樹（算法6、4），輸出二叉樹先序遍歷的結(jié)果。17、按類似先序遍歷結(jié)果輸入一序列，建立一棵二叉樹（算法6、4），輸出二叉樹后序遍歷的結(jié)果。18、按類似先序遍歷結(jié)果輸入一序列，建立一棵二叉樹（算法6、4），輸出二叉樹的總結(jié)點(diǎn)數(shù)。19、按類似先序遍歷結(jié)果輸入一序列，建立一棵二叉樹（算法6、4），輸出二叉樹葉子結(jié)點(diǎn)數(shù)。20、按類似先序遍歷結(jié)果輸入一序列，建立一棵二叉樹（算法6、4），輸出此二叉樹的高度。21、給出一個(gè)無向圖的鄰接矩陣，輸出各個(gè)頂點(diǎn)的度。22、給出一個(gè)有向圖的鄰接矩陣，輸出各個(gè)頂點(diǎn)的入度與出度。23、輸入一個(gè)有序序列，利用折半查找來查找一個(gè)數(shù)是否在序列中，如在，則輸出其位置，否則輸出“NO”。24、用插入排序方法對一組數(shù)據(jù)進(jìn)行排序，并輸出每趟排序的結(jié)果。25、用選擇排序方法對一組數(shù)據(jù)進(jìn)行排序，并輸出每趟排序的結(jié)果。26、用希爾（SHELL）排序方法對一組數(shù)據(jù)進(jìn)行排序，并輸出每趟排序的結(jié)果。27、用快速排序方法對一組數(shù)據(jù)進(jìn)行排序，并輸出每趟排序的結(jié)果。答案：1. #include #include #define N 5#define NULL 0/鏈表的存儲(chǔ)結(jié)構(gòu)typedef struct LNodeint data;struct LNode *next;LNode,*list;/順序創(chuàng)建鏈表void creatList(list &l,int n)int i;list p,q;l=(list)malloc(sizeof(LNode); /開辟頭結(jié)點(diǎn)p=l; /指針p指向頭結(jié)點(diǎn)for(i=0;idata);p-next=q; /p的下一個(gè)結(jié)點(diǎn)指向新開辟的結(jié)點(diǎn)qp=q; /將p指針指向qp-next=NULL;/歸并排序void mergeList(list &la,list &lb,list &lc) /將已經(jīng)排好序的la,lb中的數(shù)重新排列成有序（非遞減）list pa,pb,pc;pa=la-next;pb=lb-next;lc=pc=la; /默認(rèn)將la做為lc的頭結(jié)點(diǎn)（lb亦可）while(pa&pb) /讓pc接到數(shù)據(jù)小的結(jié)點(diǎn)上，直到pa,pb兩者有一指向空結(jié)點(diǎn)if(pa-datadata) pc-next=pa;pc=pa;pa=pa-next; else pc-next=pb;pc=pb;pb=pb-next; pc-next=pa?pa:pb; /如果最后la有剩余結(jié)點(diǎn)，即將其直接加入到lc中，反之將lb的剩余結(jié)點(diǎn)加到lc中free(lb);void printList(list l)list p;p=l-next;while(p) printf(%d ,p-data);p=p-next;void main()list la,lb,lc;printf(創(chuàng)建兩個(gè)含%d個(gè)元素的鏈表，請輸入：n,N);creatList(la,N);creatList(lb,N);mergeList(la,lb,lc);printList(lc);2. #include #include #define N 5#define NULL 0#define OK 1#define ERROR 0/鏈表的存儲(chǔ)結(jié)構(gòu)typedef struct LNodeint data;struct LNode *next;LNode,*list;/創(chuàng)建鏈表void creatList(list &l,int n)list p,q;l=(list)malloc(sizeof(LNode);p=l;for(int i=0;idata);p-next=q;p=q;p-next=NULL;/判斷元素e是否在鏈表中int inList(list l,int e)list p;p=l-next;while(p)if(p-data=e) return OK; /發(fā)現(xiàn)在里面，返回真值p=p-next; /否則指針后移,繼續(xù)找return ERROR; /未找到，返回假值（沒有執(zhí)行return OK;語句）/插入元素void insertList(list &l,int &e)list p,q,s; /q為新插入的元素開辟一個(gè)存儲(chǔ)空間的指針，s為p前一個(gè)指針，方便插入p=l-next;s=l;while(p)if(edata)/發(fā)現(xiàn)要插入的元素e比后面的小,開辟空間，并將e放入空間的數(shù)據(jù)域中q=(list)malloc(sizeof(LNode);q-data=e;while(s-next!=p) s=s-next; /找到p前的一個(gè)指針q-next=p; / 畫圖好好理解 -s-p- s-next=q; / q-break;p=p-next;/輸出鏈表void printList(list l)list p;p=l-next;while(p) printf(%d ,p-data); p=p-next;void main()list l;int e;printf(創(chuàng)建%d個(gè)元素的鏈表，請輸入%d個(gè)元素：n,N,N);creatList(l,N);printf(請輸入要判斷的元素：);scanf(%d,&e);if(inList(l,e)printf(YES );elseinsertList(l,e);printList(l);3. #include #include #define N 5#define NULL 0#define OK 1#define ERROR 0/鏈表的存儲(chǔ)結(jié)構(gòu)typedef struct LNodeint data;struct LNode *next;LNode,*list;/創(chuàng)建鏈表void creatList(list &l,int n)list p,q;l=(list)malloc(sizeof(LNode);p=l;for(int i=0;idata);p-next=q;p=q;p-next=NULL;/判斷元素e是否在鏈表中int insertDeleteList(list l,int e)list p,q;p=l-next; q=l;while(p)if(p-data=e) while(q-next!=p) q=q-next; /找到p前一個(gè)結(jié)點(diǎn)，方便刪除操作q-next=p-next; /刪除結(jié)點(diǎn)pfree(p);return OK; /發(fā)現(xiàn)在里面，返回真值p=p-next; /否則指針后移,繼續(xù)找return ERROR; /未找到，返回假值（沒有執(zhí)行return OK;語句）/輸出鏈表void printList(list l)list p;p=l-next;while(p) printf(%d ,p-data); p=p-next;void main()list l;int e;printf(創(chuàng)建%d個(gè)元素的鏈表，請輸入%d個(gè)元素：n,N,N);creatList(l,N);printf(請輸入要判斷的元素);scanf(%d,&e);if(!insertDeleteList(l,e)printf(NO );elseprintList(l);4. #include #include #define N 5#define NULL 0#define OK 1#define ERROR 0/鏈表的存儲(chǔ)結(jié)構(gòu)typedef struct LNodeint data;struct LNode *next;LNode,*list;/創(chuàng)建鏈表void creatList(list &l,int n)list p,q;l=(list)malloc(sizeof(LNode);p=l;for(int i=0;idata);p-next=q;p=q;p-next=NULL;/鏈表排序void sortList(list &l)list p,q,r; /p標(biāo)記排序的輪數(shù)int chang; /用于交換結(jié)點(diǎn)中的數(shù)據(jù)p=l-next;while(p-next!=NULL)q=l-next; /每次比較從首結(jié)點(diǎn)開始while(q-next!=NULL)r=q-next; if(q-datar-data) /發(fā)現(xiàn)前一個(gè)比后一個(gè)大，交換數(shù)據(jù) chang=q-data;q-data=r-data;r-data=chang; q=q-next; /相鄰間下一個(gè)比較p=p-next; /下一輪比較/輸出鏈表void printList(list l)list p;p=l-next;while(p) printf(%d ,p-data); p=p-next;void main()list l;printf(創(chuàng)建%d個(gè)元素的鏈表，請輸入%d個(gè)元素：n,N,N);creatList(l,N);sortList(l);printList(l);5. #include #include #define N 5#define NULL 0#define OK 1#define ERROR 0/鏈表的存儲(chǔ)結(jié)構(gòu)typedef struct LNodeint data;struct LNode *next;LNode,*list;/創(chuàng)建鏈表void creatList(list &l,int n)list p,q;l=(list)malloc(sizeof(LNode); scanf(%d,&l-data); /頭結(jié)點(diǎn)也添加元素，方便輸出p=l;for(int i=1;idata);p-next=q;p=q;p-next=l; /讓最后一個(gè)p-next指針指向頭結(jié)點(diǎn)，構(gòu)成循環(huán)鏈表/輸出鏈表void printList(list l,int pos)list p,q;int i;p=l;for(i=1;inext; /找到指定位置的前一個(gè)位置q=p-next;do if(pos=1) printf(%d ,p-data); p=p-next; /如果指定位置為1，即按原樣輸出else p=p-next; printf(%d ,p-data); /不然，p先移到指定的位置，輸出其數(shù)據(jù)while(p-next!=q); /結(jié)束條件（p移到的下一個(gè)位置不是q，即不是最初的p,完成循環(huán)輸出）void main()list l;int pos;printf(創(chuàng)建%d個(gè)元素的循環(huán)鏈表，請輸入%d個(gè)元素：n,N,N);creatList(l,N);printf(請指明從第幾個(gè)位置輸出循環(huán)鏈表中的元素：);scanf(%d,&pos);while(posN)printf(輸入的位置不存在，請重新輸入. );scanf(%d,&pos);printList(l,pos);11#include #include #define N 5#define NULL 0#define OK 1#define ERROR 0/鏈表的存儲(chǔ)結(jié)構(gòu)typedef struct LNodeint data;struct LNode *next;LNode,*list;/創(chuàng)建鏈表void creatList(list &l,int n)list p,q;l=(list)malloc(sizeof(LNode); scanf(%d,&l-data); /頭結(jié)點(diǎn)也添加元素，方便輸出p=l;for(int i=1;idata);p-next=q;p=q;p-next=l; /讓最后一個(gè)p-next指針指向頭結(jié)點(diǎn)，構(gòu)成循環(huán)鏈表/輸出鏈表void printList(list l,int pos)list p,q;int i;p=l;for(i=1;inext; /找到指定位置的前一個(gè)位置q=p-next;do if(pos=1) printf(%d ,p-data); p=p-next; /如果指定位置為1，即按原樣輸出else p=p-next; printf(%d ,p-data); /不然，p先移到指定的位置，輸出其數(shù)據(jù)while(p-next!=q); /結(jié)束條件（p移到的下一個(gè)位置不是q，即不是最初的p,完成循環(huán)輸出）void main()list l;int pos;printf(創(chuàng)建%d個(gè)元素的循環(huán)鏈表，請輸入%d個(gè)元素：n,N,N);creatList(l,N);printf(請指明從第幾個(gè)位置輸出循環(huán)鏈表中的元素：);scanf(%d,&pos);while(posN)printf(輸入的位置不存在，請重新輸入. );scanf(%d,&pos);printList(l,pos);12#include #include #define N 5#define NULL 0#define OK 1#define ERROR 0/鏈表的存儲(chǔ)結(jié)構(gòu)typedef struct LNodeint data;struct LNode *next;LNode,*list;/創(chuàng)建鏈表void creatList(list &l,int n)list p,q;l=(list)malloc(sizeof(LNode);p=l;for(int i=0;idata);p-next=q;p=q;p-next=NULL;/判斷元素e是否在鏈表中int inList(list l,int e)list p,q;q=p=l-next;while(p)if(p-data=e) return OK; /發(fā)現(xiàn)在里面，返回真值p=p-next; /否則指針后移,繼續(xù)找/沒有執(zhí)行return OK;語句,說明未找到while(q-next!=p) q=q-next; /找到鏈尾p=(list)malloc(sizeof(LNode); /為鏈尾重新開辟空間p-data=e; /接到鏈尾p-next=q-next;q-next=p;return ERROR; /未找到，返回假值/輸出鏈表void printList(list l)list p;p=l-next;while(p) printf(%d ,p-data); p=p-next;void main()list l;int e;printf(創(chuàng)建%d個(gè)元素的鏈表，請輸入%d個(gè)元素：n,N,N);creatList(l,N);printf(請輸入要判斷的元素：);scanf(%d,&e);if(inList(l,e)printf(YES );elseprintList(l);13#include #include #define OK 1#define Error 0#define NULL 0#define maxSize 100/棧的存儲(chǔ)結(jié)構(gòu)typedef struct int *base;int *top;int size;stack;/棧的初始化（順序存儲(chǔ)）int initStack(stack &s) /開辟maxSize大小的空間，base和top都指向基地址,同時(shí)判斷是否開辟成功，不成功返回0if(!(s.base=s.top=(int*)malloc(maxSize*sizeof(int) return Error; s.size=maxSize; /棧的大小為maxSizereturn OK;/進(jìn)棧操作int push(stack &s,int e)*s.top=e; /先將元素e賦值給s.top所指的存儲(chǔ)空間s.top+; /top指針上移return OK;/出棧操作int pop(stack &s,int &e)if(s.base=s.top) return Error; /如果棧為空，返回0s.top-; /top指針先后移e=*s.top; /將其所指的元素值賦給ereturn e; void main()stack s;int n,e;printf(請輸入要?jiǎng)?chuàng)建棧的元素的個(gè)數(shù)：);scanf(%d,&n);initStack(s);for(int i=0;in;i+)scanf(%d,&e);push(s,e);while(s.base!=s.top)printf(%d ,pop(s,e);14#include #include #include #include #define stackincrement 8#define OK 1#define Error 0#define NULL 0#define maxSize 100/棧的存儲(chǔ)結(jié)構(gòu)typedef struct char *base; /由于要存放括號，所以為char類型char *top;int size;stack;/棧的初始化（順序存儲(chǔ)）int initStack(stack &s) /注意開辟的空間為char類型if(!(s.base=s.top=(char*)malloc(maxSize*sizeof(char) return Error; s.size=maxSize; /棧的大小為maxSizereturn OK;/進(jìn)棧操作int push(stack &s,int e)*s.top=e; /先將元素e賦值給s.top所指的存儲(chǔ)空間s.top+; /top指針上移return OK;int isEmpty(stack s)return s.base=s.top?OK:Error;/出棧操作char pop(stack &s,char &e)if(isEmpty(s) return Error; /如果棧為空，返回0s.top-; /top指針先后移e=*s.top; /將其所指的元素值賦給ereturn e; /括號匹配int match()stack s;initStack(s);char ch100,e;int flag=1,i=0 ,lenth; /flag用于標(biāo)記，如果匹配，值為1，否則為0scanf(%c,&chi);while(chi!=n) scanf(%c,&ch+i); /先將所有輸入的括號存放在數(shù)組ch中 lenth=i-1; /數(shù)組的長度，不包括ni=0;push(s,chi); /先將第一個(gè)括號壓棧if(chi=|chi=)|chi=) flag=0; /如果第一個(gè)壓入的是右括號，則肯定不匹配，flag=0else while(idata=ch; /生成根結(jié)點(diǎn) CreateBiTree(T-lchild);/構(gòu)造左子樹 CreateBiTree(T-rchild);/構(gòu)造右子樹 return OK; /CreateBiTreeint PrintElement(int e) /輸出元素e的值 printf(%c,e); return OK;int InOrderTraverse(BiTree T,int(*Visit)(int e) /采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，visit是對數(shù)據(jù)元素操作的應(yīng)用函數(shù)， /中序遍歷二叉樹T的遞歸算法，對每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit。 /調(diào)用實(shí)例： InOrderTraverse(T,printElement); if(T) if (InOrderTraverse(T-lchild,Visit) if (Visit(T-data) if (InOrderTraverse(T-rchild,Visit) return OK; return ERROR;else return OK; void main() BiTree t; printf(請按先序遍歷輸入二叉樹（當(dāng)左右子樹為空時(shí)用空格輸入）n); CreateBiTree(t); printf(該二叉樹的中序遍歷為：n); InOrderTraverse(t,PrintElement); printf(n);16#include stdio.h#include stdlib.h#define stackinitsize 100#define OK 1#define ERROR 0/二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)typedef struct BiTNode int data; struct BiTNode *lchild,*rchild; /左右孩子指針 BiTnode,*BiTree;int CreateBiTree(BiTree &T) /按先序次序輸入二叉樹中結(jié)點(diǎn)的值（一個(gè)字符），空格字符表示空樹。 /構(gòu)造二叉鏈表表示的二叉樹T. char ch; scanf(%c,&ch); if(ch= ) T=NULL; else if(!(T=(BiTNode *)malloc(sizeof(BiTNode) exit(0); T-data=ch; /生成根結(jié)點(diǎn) CreateBiTree(T-lchild);/構(gòu)造左子樹 CreateBiTree(T-rchild);/構(gòu)造右子樹 return OK; /CreateBiTreeint PrintElement(int e) /輸出元素e的值 printf(%c,e); return OK;int PreOrderTraverse(BiTree T,int(*Visit)(int e) /采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，visit是對數(shù)據(jù)元素操作的應(yīng)用函數(shù)， /先序遍歷二叉樹T的遞歸算法，對每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit。 /調(diào)用實(shí)例： PreOrderTraverse(T,printElement); if(T) if (Visit(T-data) if (PreOrderTraverse(T-lchild,Visit) if (PreOrderTraverse(T-rchild,Visit) return OK; return ERROR;else return OK; /preOrderTraVersevoid main() BiTree t; printf(請按先序遍歷輸入二叉樹（當(dāng)左右子樹為空時(shí)用空格輸入）n); CreateBiTree(t); printf(該二叉樹的先序遍歷為：n); PreOrderTraverse(t,PrintElement); printf(n);17#include stdio.h#include stdlib.h#define stackinitsize 100#define OK 1#define ERROR 0/二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)typedef struct BiTNode int data; struct BiTNode *lchild,*rchild; /左右孩子指針 BiTnode,*BiTree;int CreateBiTree(BiTree &T) /按先序次序輸入二叉樹中結(jié)點(diǎn)的值（一個(gè)字符），空格字符表示空樹。 /構(gòu)造二叉鏈表表示的二叉樹T. char ch; scanf(%c,&ch); if(ch= ) T=NULL; else if(!(T=(BiTNode *)malloc(sizeof(BiTNode) exit(0); T-data=ch; /生成根結(jié)點(diǎn) CreateBiTree(T-lchild);/構(gòu)造左子樹 CreateBiTree(T-rchild);/構(gòu)造右子樹 return OK; /CreateBiTreeint PrintElement(int e) /輸出元素e的值 printf(%c,e); return OK;int PostOrderTraverse(BiTree T,int(*Visit)(int e) /采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，visit是對數(shù)據(jù)元素操作的應(yīng)用函數(shù)， /后序遍歷二叉樹T的遞歸算法，對每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit。 /調(diào)用實(shí)例： PostOrderTraverse(T,printElement); if(T) if (PostOrderTraverse(T-lchild,Visit) if (PostOrderTraverse(T-rchild,Visit) if (Visit(T-data)return OK; return ERROR;else return OK; void main() BiTree t; printf(請按先序遍歷輸入二叉樹（當(dāng)左右子樹為空時(shí)用空格輸入）n); CreateBiTree(t); printf(該二叉樹的后序遍歷為：n); PostOrderTraverse(t,PrintElement); printf(n);18#include stdio.h#include stdlib.h#define stackinitsize 100#define OK 1#define ERROR 0/#define NULL 0static int count=0;/二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)typedef struct BiTNode int data; struct BiTNode *lchild,*rchild; /左右孩子指針 BiTnode,*BiTree;int CreateBiTree(BiTree &T) /按先序次序輸入二叉樹中結(jié)點(diǎn)的值（一個(gè)字符），空格字符表示空樹。 /構(gòu)造二叉鏈表表示的二叉樹T. char ch; scanf(%c,&ch); if(ch= ) T=NULL; else if(!(T=(BiTNode *)malloc(sizeof(BiTNode) return -1; T-data=ch; /生成根結(jié)點(diǎn) CreateBiTree(T-lchild);/構(gòu)造左子樹 CreateBiTree(T-rchild);/構(gòu)造右子樹 return OK; /CreateBiTreeint PrintElement(int e) /記錄遍歷結(jié)點(diǎn)數(shù) count+; return OK;int PreOrderTraverse(BiTree T,int(*Visit)(int e) /采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，visit是對數(shù)據(jù)元素操作的應(yīng)用函數(shù)， if(T) if (Visit(T-data) if (PreOrderTraverse(T-lchild,Visit) if (PreOrderTraverse(T-rchild,Visit) return OK; return ERROR;else return OK; /preOrderTraVersevoid main() BiTree t; printf(請按先序遍歷輸入二叉樹（當(dāng)左右子樹為空時(shí)用空格輸入）n); CreateBiTree(t); printf(該二叉樹的總結(jié)點(diǎn)數(shù)為: ); PreOrderTraverse(t,PrintElement); printf(%dn,count);19#include stdio.h#include stdlib.h#define stackinitsize 100#define OK 1#define ERROR 0static int count=0;/二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)typedef struct BiTNode int data; struct BiTNode *lchild,*rchild; /左右孩子指針 BiTnode,*BiTree;int CreateBiTree(BiTree &T) /按先序次序輸入二叉樹中結(jié)點(diǎn)的值（一個(gè)字符），空格字符表示空樹。 /構(gòu)造二叉鏈表表示的二叉樹T. char ch; scanf(%c,&ch); if(ch= ) T=NULL; else if(!(T=(BiTNode *)malloc(sizeof(BiTNode