數據結構上機考試(含答案)

數據結構上機考試(含答案)數據結構上機考試(含答案)數據結構上機考試(含答案)xxx公司數據結構上機考試(含答案)文件編號：文件日期：修訂次數：第1.0次更改批準審核制定方案設計，管理制度《數據結構》上機練習題1、設有兩個有序序列，利用歸并排序將它們排成有序表，并輸出。2、設有一有序序列，從鍵盤輸入一個數，判別是否在序列中，如果在輸出“YSE”；否則，將它插入到序列中使它仍然有序，并輸出排序后的序列。3、設有一有序序列，從鍵盤輸入一個數，判別是否在序列中，如果不在，則輸出“NO”，否則，將它從序列中刪除它，并輸出刪除后的序列。4、從鍵盤輸入一組任意數據，建立一個有序鏈表，并從鏈頭開始輸出該鏈，使輸出結果是有序的。5、從鍵盤輸入一組任意數據，建立一個包含所有輸入數據的單向循環(huán)鏈表，并從鏈表的任意開始，依次輸出該鏈表中的所有結點。10、設有一個鏈表，（自己建立，數據從鍵盤輸入），再從鍵盤輸入一個數，判別是否在鏈表中，如果不在，則輸出“NO“，否則，將它從鏈表中刪除，并輸出刪除后的鏈表。11、設有一個鏈表，（自己建立，數據從鍵盤輸入），再從鍵盤輸入一個數，判別是否在鏈表中，如果在輸出“YSE”，否則，將它從插入到鏈頭，并輸出插入后的鏈表。12、設有一個鏈表，（自己建立，數據從鍵盤輸入），再從鍵盤輸入一個數，判別是否在鏈表中，如果在輸出“YSE”，否則，將它從插入到鏈尾，并輸出插入后的鏈表。13、編寫棧的壓棧push、彈棧pop函數，從鍵盤輸入一組數據，逐個元素壓入堆棧，然后再逐個從棧中彈出它們并輸出。14、編寫棧的壓棧push、彈棧pop函數，用它判別（）的匹配問題。15、按類似先序遍歷結果輸入一序列，建立一棵二叉樹（算法6、4），輸出二叉樹中序遍歷的結果。16、按類似先序遍歷結果輸入一序列，建立一棵二叉樹（算法6、4），輸出二叉樹先序遍歷的結果。17、按類似先序遍歷結果輸入一序列，建立一棵二叉樹（算法6、4），輸出二叉樹后序遍歷的結果。18、按類似先序遍歷結果輸入一序列，建立一棵二叉樹（算法6、4），輸出二叉樹的總結點數。19、按類似先序遍歷結果輸入一序列，建立一棵二叉樹（算法6、4），輸出二叉樹葉子結點數。20、按類似先序遍歷結果輸入一序列，建立一棵二叉樹（算法6、4），輸出此二叉樹的高度。21、給出一個無向圖的鄰接矩陣，輸出各個頂點的度。22、給出一個有向圖的鄰接矩陣，輸出各個頂點的入度與出度。23、輸入一個有序序列，利用折半查找來查找一個數是否在序列中，如在，則輸出其位置，否則輸出“NO”。24、用插入排序方法對一組數據進行排序，并輸出每趟排序的結果。25、用選擇排序方法對一組數據進行排序，并輸出每趟排序的結果。26、用希爾（SHELL）排序方法對一組數據進行排序，并輸出每趟排序的結果。27、用快速排序方法對一組數據進行排序，并輸出每趟排序的結果。．答案：1.#include<stdio.h>#include<stdlib.h>#defineN5#defineNULL0//鏈表的存儲結構typedefstructLNode{ intdata; structLNode*next;}LNode,*list;//順序創(chuàng)建鏈表voidcreatList(list&l,intn){ inti; listp,q; l=(list)malloc(sizeof(LNode));//開辟頭結點 p=l;//指針p指向頭結點 for(i=0;i<n;i++) { q=(list)malloc(sizeof(LNode));//新的結點 scanf("%d",&q->data); p->next=q;//p的下一個結點指向新開辟的結點q p=q;//將p指針指向q } p->next=NULL;}//歸并排序voidmergeList(list&la,list&lb,list&lc){//將已經排好序的la,lb中的數重新排列成有序（非遞減） listpa,pb,pc; pa=la->next;pb=lb->next; lc=pc=la;//默認將la做為lc的頭結點（lb亦可） while(pa&&pb) {//讓pc接到數據小的結點上，直到pa,pb兩者有一指向空結點 if(pa->data<=pb->data) {pc->next=pa;pc=pa;pa=pa->next;} else {pc->next=pb;pc=pb;pb=pb->next;} } pc->next=pa?pa:pb;//如果最后la有剩余結點，即將其直接加入到lc中，反之將lb的剩余結點加到lc中 free(lb); }voidprintList(listl){ listp; p=l->next; while(p) {printf("%d",p->data);p=p->next;}}voidmain(){ listla,lb,lc; printf("創(chuàng)建兩個含%d個元素的鏈表，請輸入：\n",N); creatList(la,N); creatList(lb,N); mergeList(la,lb,lc); printList(lc);}2.#include<stdio.h>#include<stdlib.h>#defineN5#defineNULL0#defineOK1#defineERROR0//鏈表的存儲結構typedefstructLNode{ intdata; structLNode*next;}LNode,*list;//創(chuàng)建鏈表voidcreatList(list&l,intn){ listp,q; l=(list)malloc(sizeof(LNode)); p=l; for(inti=0;i<n;i++) { q=(list)malloc(sizeof(LNode)); scanf("%d",&q->data); p->next=q; p=q; } p->next=NULL;}//判斷元素e是否在鏈表中intinList(listl,inte){ listp; p=l->next; while(p) { if(p->data==e) returnOK;//發(fā)現(xiàn)在里面，返回真值 p=p->next;//否則指針后移,繼續(xù)找 } returnERROR; //未找到，返回假值（沒有執(zhí)行returnOK;語句）}//插入元素voidinsertList(list&l,int&e){ listp,q,s;//q為新插入的元素開辟一個存儲空間的指針，s為p前一個指針，方便插入 p=l->next; s=l; while(p) { if(e<=p->data) {//發(fā)現(xiàn)要插入的元素e比后面的小,開辟空間，并將e放入空間的數據域中 q=(list)malloc(sizeof(LNode)); q->data=e; while(s->next!=p)s=s->next;//找到p前的一個指針 q->next=p;//畫圖好好理解--->s--->p---> s->next=q;//q---> break; } p=p->next; }}//輸出鏈表voidprintList(listl){ listp; p=l->next; while(p) {printf("%d",p->data);p=p->next;}}voidmain(){ listl; inte; printf("創(chuàng)建%d個元素的鏈表，請輸入%d個元素：\n",N,N); creatList(l,N); printf("請輸入要判斷的元素："); scanf("%d",&e); if(inList(l,e)) printf("YES"); else { insertList(l,e); printList(l); }}3.#include<stdio.h>#include<stdlib.h>#defineN5#defineNULL0#defineOK1#defineERROR0//鏈表的存儲結構typedefstructLNode{ intdata; structLNode*next;}LNode,*list;//創(chuàng)建鏈表voidcreatList(list&l,intn){ listp,q; l=(list)malloc(sizeof(LNode)); p=l; for(inti=0;i<n;i++) { q=(list)malloc(sizeof(LNode)); scanf("%d",&q->data); p->next=q; p=q; } p->next=NULL;}//判斷元素e是否在鏈表中intinsertDeleteList(listl,inte){ listp,q; p=l->next;q=l; while(p) { if(p->data==e) { while(q->next!=p)q=q->next;//找到p前一個結點，方便刪除操作 q->next=p->next;//刪除結點p free(p); returnOK; }//發(fā)現(xiàn)在里面，返回真值 p=p->next;//否則指針后移,繼續(xù)找 } returnERROR; //未找到，返回假值（沒有執(zhí)行returnOK;語句）}//輸出鏈表voidprintList(listl){ listp; p=l->next; while(p) {printf("%d",p->data);p=p->next;}}voidmain(){ listl; inte; printf("創(chuàng)建%d個元素的鏈表，請輸入%d個元素：\n",N,N); creatList(l,N); printf("請輸入要判斷的元素"); scanf("%d",&e); if(!insertDeleteList(l,e)) printf("NO"); else printList(l);}4.#include<stdio.h>#include<stdlib.h>#defineN5#defineNULL0#defineOK1#defineERROR0//鏈表的存儲結構typedefstructLNode{ intdata; structLNode*next;}LNode,*list;//創(chuàng)建鏈表voidcreatList(list&l,intn){ listp,q; l=(list)malloc(sizeof(LNode)); p=l; for(inti=0;i<n;i++) { q=(list)malloc(sizeof(LNode)); scanf("%d",&q->data); p->next=q; p=q; } p->next=NULL;}//鏈表排序voidsortList(list&l){ listp,q,r;//p標記排序的輪數 intchang;//用于交換結點中的數據 p=l->next; while(p->next!=NULL) { q=l->next;//每次比較從首結點開始 while(q->next!=NULL) { r=q->next; if(q->data>r->data)//發(fā)現(xiàn)前一個比后一個大，交換數據 {chang=q->data;q->data=r->data;r->data=chang;} q=q->next;//相鄰間下一個比較 } p=p->next;//下一輪比較 }}//輸出鏈表voidprintList(listl){ listp; p=l->next; while(p) {printf("%d",p->data);p=p->next;}}voidmain(){ listl; printf("創(chuàng)建%d個元素的鏈表，請輸入%d個元素：\n",N,N); creatList(l,N); sortList(l); printList(l); }5.#include<stdio.h>#include<stdlib.h>#defineN5#defineNULL0#defineOK1#defineERROR0//鏈表的存儲結構typedefstructLNode{ intdata; structLNode*next;}LNode,*list;//創(chuàng)建鏈表voidcreatList(list&l,intn){ listp,q; l=(list)malloc(sizeof(LNode)); scanf("%d",&l->data);//頭結點也添加元素，方便輸出 p=l; for(inti=1;i<n;i++) { q=(list)malloc(sizeof(LNode)); scanf("%d",&q->data); p->next=q; p=q; } p->next=l;//讓最后一個p->next指針指向頭結點，構成循環(huán)鏈表}//輸出鏈表voidprintList(listl,intpos){ listp,q; inti; p=l; for(i=1;i<pos-1;i++)p=p->next;//找到指定位置的前一個位置 q=p->next; do { if(pos==1){printf("%d",p->data);p=p->next;}//如果指定位置為1，即按原樣輸出 else{p=p->next;printf("%d",p->data);}//不然，p先移到指定的位置，輸出其數據 }while(p->next!=q); //結束條件（p移到的下一個位置不是q，即不是最初的p,完成循環(huán)輸出）}voidmain(){ listl; intpos; printf("創(chuàng)建%d個元素的循環(huán)鏈表，請輸入%d個元素：\n",N,N); creatList(l,N); printf("請指明從第幾個位置輸出循環(huán)鏈表中的元素："); scanf("%d",&pos); while(pos<=0||pos>N) { printf("輸入的位置不存在，請重新輸入..."); scanf("%d",&pos); } printList(l,pos);}11#include<stdio.h>#include<stdlib.h>#defineN5#defineNULL0#defineOK1#defineERROR0//鏈表的存儲結構typedefstructLNode{ intdata; structLNode*next;}LNode,*list;//創(chuàng)建鏈表voidcreatList(list&l,intn){ listp,q; l=(list)malloc(sizeof(LNode)); scanf("%d",&l->data);//頭結點也添加元素，方便輸出 p=l; for(inti=1;i<n;i++) { q=(list)malloc(sizeof(LNode)); scanf("%d",&q->data); p->next=q; p=q; } p->next=l;//讓最后一個p->next指針指向頭結點，構成循環(huán)鏈表}//輸出鏈表voidprintList(listl,intpos){ listp,q; inti; p=l; for(i=1;i<pos-1;i++)p=p->next;//找到指定位置的前一個位置 q=p->next; do { if(pos==1){printf("%d",p->data);p=p->next;}//如果指定位置為1，即按原樣輸出 else{p=p->next;printf("%d",p->data);}//不然，p先移到指定的位置，輸出其數據 }while(p->next!=q); //結束條件（p移到的下一個位置不是q，即不是最初的p,完成循環(huán)輸出）}voidmain(){ listl; intpos; printf("創(chuàng)建%d個元素的循環(huán)鏈表，請輸入%d個元素：\n",N,N); creatList(l,N); printf("請指明從第幾個位置輸出循環(huán)鏈表中的元素："); scanf("%d",&pos); while(pos<=0||pos>N) { printf("輸入的位置不存在，請重新輸入..."); scanf("%d",&pos); } printList(l,pos);}12#include<stdio.h>#include<stdlib.h>#defineN5#defineNULL0#defineOK1#defineERROR0//鏈表的存儲結構typedefstructLNode{ intdata; structLNode*next;}LNode,*list;//創(chuàng)建鏈表voidcreatList(list&l,intn){ listp,q; l=(list)malloc(sizeof(LNode)); p=l; for(inti=0;i<n;i++) { q=(list)malloc(sizeof(LNode)); scanf("%d",&q->data); p->next=q; p=q; } p->next=NULL;}//判斷元素e是否在鏈表中intinList(listl,inte){ listp,q; q=p=l->next; while(p) { if(p->data==e) returnOK;//發(fā)現(xiàn)在里面，返回真值 p=p->next;//否則指針后移,繼續(xù)找 } //沒有執(zhí)行returnOK;語句,說明未找到 while(q->next!=p)q=q->next;//找到鏈尾 p=(list)malloc(sizeof(LNode));//為鏈尾重新開辟空間 p->data=e;//接到鏈尾 p->next=q->next; q->next=p; returnERROR;//未找到，返回假值 }//輸出鏈表voidprintList(listl){ listp; p=l->next; while(p) {printf("%d",p->data);p=p->next;}}voidmain(){ listl; inte; printf("創(chuàng)建%d個元素的鏈表，請輸入%d個元素：\n",N,N); creatList(l,N); printf("請輸入要判斷的元素："); scanf("%d",&e); if(inList(l,e)) printf("YES"); else printList(l);}13#include<stdio.h>#include<stdlib.h>#defineOK1#defineError0#defineNULL0#definemaxSize100//棧的存儲結構typedefstruct{ int*base; int*top; intsize;}stack;//棧的初始化（順序存儲）intinitStack(stack&s){//開辟maxSize大小的空間，base和top都指向基地址,同時判斷是否開辟成功，不成功返回0 if(!(s.base=s.top=(int*)malloc(maxSize*sizeof(int))))returnError; s.size=maxSize;//棧的大小為maxSize returnOK;}//進棧操作intpush(stack&s,inte){ *s.top=e;//先將元素e賦值給s.top所指的存儲空間 s.top++;//top指針上移 returnOK;}//出棧操作intpop(stack&s,int&e){ if(s.base==s.top)returnError;//如果棧為空，返回0 s.top--;//top指針先后移 e=*s.top;//將其所指的元素值賦給e returne;}voidmain(){ stacks; intn,e; printf("請輸入要創(chuàng)建棧的元素的個數："); scanf("%d",&n); initStack(s); for(inti=0;i<n;i++) { scanf("%d",&e); push(s,e); } while(s.base!=s.top) { printf("%d",pop(s,e)); }}14#include<stdlib.h>#include<stdio.h>#include<stdio.h>#include<stdlib.h>#definestackincrement8#defineOK1#defineError0#defineNULL0#definemaxSize100//棧的存儲結構typedefstruct{ char*base;//由于要存放括號，所以為char類型 char*top; intsize;}stack;//棧的初始化（順序存儲）intinitStack(stack&s){//注意開辟的空間為char類型 if(!(s.base=s.top=(char*)malloc(maxSize*sizeof(char))))returnError; s.size=maxSize;//棧的大小為maxSize returnOK;}//進棧操作intpush(stack&s,inte){ *s.top=e;//先將元素e賦值給s.top所指的存儲空間 s.top++;//top指針上移 returnOK;}intisEmpty(stacks){ returns.base==s.top?OK:Error;}//出棧操作charpop(stack&s,char&e){ if(isEmpty(s))returnError;//如果棧為空，返回0 s.top--;//top指針先后移 e=*s.top;//將其所指的元素值賦給e returne;}//括號匹配intmatch(){ stacks; initStack(s); charch[100],e; intflag=1,i=0,lenth;//flag用于標記，如果匹配，值為1，否則為0 scanf("%c",&ch[i]); while(ch[i]!='\n')scanf("%c",&ch[++i]);//先將所有輸入的括號存放在數組ch[]中 lenth=i-1;//數組的長度，不包括'\n' i=0; push(s,ch[i]);//先將第一個括號壓棧 if(ch[i]==']'||ch[i]==')'||ch[i]=='}')flag=0;//如果第一個壓入的是右括號，則肯定不匹配，flag=0 elsewhile(i<lenth)//||!emptystack(s) { i++;chart; if(ch[i]==']'||ch[i]==')'||ch[i]=='}') {t=pop(s,e);//彈出先前壓入的元素，將后繼輸入的括號與先前壓入的比較 if((t!=ch[i]-1)&&(t!=ch[i]-2)){flag=0;break;}//左右小括號與左右大括號的ASCII碼都相差1，左右中括號相差2，如果不滿足，則不匹配，直接退出循環(huán) } elsepush(s,ch[i]);//輸入的是左括號，直接壓入 }if(!isEmpty(s))flag=0;//通過不斷的壓棧和彈棧，如果最后棧不為空，則肯定是左括號多于右括號，不匹配 returnflag;}voidmain(){ intresult; printf("判斷輸入的各種括號是否匹配：\n"); result=match(); if(result)printf("括號匹配正確^_^\n"); elseprintf("括號匹配錯誤*.*\n"); }15#include"stdio.h"#include"stdlib.h"#definestackinitsize100#defineOK1#defineERROR0//二叉樹的二叉鏈表存儲結構typedefstructBiTNode{intdata;structBiTNode*lchild,*rchild;//左右孩子指針}BiTnode,*BiTree;intCreateBiTree(BiTree&T){//按先序次序輸入二叉樹中結點的值（一個字符），空格字符表示空樹。//構造二叉鏈表表示的二叉樹T.charch;scanf("%c",&ch);if(ch=='')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(0);T->data=ch;//生成根結點CreateBiTree(T->lchild);//構造左子樹CreateBiTree(T->rchild);//構造右子樹}returnOK;}//CreateBiTreeintPrintElement(inte){//輸出元素e的值printf("%c",e);returnOK; }intInOrderTraverse(BiTreeT,int(*Visit)(inte))//采用二叉鏈表存儲結構，visit是對數據元素操作的應用函數，//中序遍歷二叉樹T的遞歸算法，對每個數據元素調用函數visit。//調用實例：InOrderTraverse(T,printElement);{if(T){if(InOrderTraverse(T->lchild,Visit))if(Visit(T->data))if(InOrderTraverse(T->rchild,Visit))returnOK;returnERROR; }elsereturnOK;}voidmain(){BiTreet;printf("請按先序遍歷輸入二叉樹（當左右子樹為空時用空格輸入）\n");CreateBiTree(t);printf("該二叉樹的中序遍歷為：\n");InOrderTraverse(t,PrintElement);printf("\n");}16#include"stdio.h"#include"stdlib.h"#definestackinitsize100#defineOK1#defineERROR0//二叉樹的二叉鏈表存儲結構typedefstructBiTNode{intdata;structBiTNode*lchild,*rchild;//左右孩子指針}BiTnode,*BiTree;intCreateBiTree(BiTree&T){//按先序次序輸入二叉樹中結點的值（一個字符），空格字符表示空樹。//構造二叉鏈表表示的二叉樹T.charch;scanf("%c",&ch);if(ch=='')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(0);T->data=ch;//生成根結點CreateBiTree(T->lchild);//構造左子樹CreateBiTree(T->rchild);//構造右子樹}returnOK;}//CreateBiTreeintPrintElement(inte){//輸出元素e的值printf("%c",e);returnOK; }intPreOrderTraverse(BiTreeT,int(*Visit)(inte))//采用二叉鏈表存儲結構，visit是對數據元素操作的應用函數，//先序遍歷二叉樹T的遞歸算法，對每個數據元素調用函數visit。//調用實例：PreOrderTraverse(T,printElement);{if(T){if(Visit(T->data))if(PreOrderTraverse(T->lchild,Visit))if(PreOrderTraverse(T->rchild,Visit))returnOK;returnERROR; }elsereturnOK;}//preOrderTraVersevoidmain(){BiTreet;printf("請按先序遍歷輸入二叉樹（當左右子樹為空時用空格輸入）\n");CreateBiTree(t);printf("該二叉樹的先序遍歷為：\n");PreOrderTraverse(t,PrintElement);printf("\n");}17#include"stdio.h"#include"stdlib.h"#definestackinitsize100#defineOK1#defineERROR0//二叉樹的二叉鏈表存儲結構typedefstructBiTNode{intdata;structBiTNode*lchild,*rchild;//左右孩子指針}BiTnode,*BiTree;intCreateBiTree(BiTree&T){//按先序次序輸入二叉樹中結點的值（一個字符），空格字符表示空樹。//構造二叉鏈表表示的二叉樹T.charch;scanf("%c",&ch);if(ch=='')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(0);T->data=ch;//生成根結點CreateBiTree(T->lchild);//構造左子樹CreateBiTree(T->rchild);//構造右子樹}returnOK;}//CreateBiTreeintPrintElement(inte){//輸出元素e的值printf("%c",e);returnOK; }intPostOrderTraverse(BiTreeT,int(*Visit)(inte))//采用二叉鏈表存儲結構，visit是對數據元素操作的應用函數，//后序遍歷二叉樹T的遞歸算法，對每個數據元素調用函數visit。//調用實例：PostOrderTraverse(T,printElement);{if(T){if(PostOrderTraverse(T->lchild,Visit))if(PostOrderTraverse(T->rchild,Visit)) if(Visit(T->data))returnOK;returnERROR; }elsereturnOK;}voidmain(){BiTreet;printf("請按先序遍歷輸入二叉樹（當左右子樹為空時用空格輸入）\n");CreateBiTree(t);printf("該二叉樹的后序遍歷為：\n");PostOrderTraverse(t,PrintElement);printf("\n");}18#include"stdio.h"#include"stdlib.h"#definestackinitsize100#defineOK1#defineERROR0//#defineNULL0staticintcount=0;//二叉樹的二叉鏈表存儲結構typedefstructBiTNode{intdata;structBiTNode*lchild,*rchild;//左右孩子指針}BiTnode,*BiTree;intCreateBiTree(BiTree&T){//按先序次序輸入二叉樹中結點的值（一個字符），空格字符表示空樹。//構造二叉鏈表表示的二叉樹T.charch;scanf("%c",&ch);if(ch=='')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))return-1;T->data=ch;//生成根結點CreateBiTree(T->lchild);//構造左子樹CreateBiTree(T->rchild);//構造右子樹}returnOK;}//CreateBiTreeintPrintElement(inte){//記錄遍歷結點數count++; returnOK; }intPreOrderTraverse(BiTreeT,int(*Visit)(inte))//采用二叉鏈表存儲結構，visit是對數據元素操作的應用函數，{if(T){if(Visit(T->data))if(PreOrderTraverse(T->lchild,Visit))if(PreOrderTraverse(T->rchild,Visit))returnOK;returnERROR; }elsereturnOK;}//preOrderTraVersevoidmain(){BiTreet;printf("請按先序遍歷輸入二叉樹（當左右子樹為空時用空格輸入）\n");CreateBiTree(t);printf("該二叉樹的總結點數為:");PreOrderTraverse(t,PrintElement);printf("%d\n",count);}19#include"stdio.h"#include"stdlib.h"#definestackinitsize100#defineOK1#defineERROR0staticintcount=0;//二叉樹的二叉鏈表存儲結構typedefstructBiTNode{intdata;structBiTNode*lchild,*rchild;//左右孩子指針}BiTnode,*BiTree;intCreateBiTree(BiTree&T){//按先序次序輸入二叉樹中結點的值（一個字符），空格字符表示空樹。//構造二叉鏈表表示的二叉樹T.charch;scanf("%c",&ch);if(ch=='')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(0);T->data=ch;//生成根結點CreateBiTree(T->lchild);//構造左子樹CreateBiTree(T->rchild);//構造右子樹}returnOK;}//CreateBiTreeintPrintElement(inte){//判斷葉子結點的個數，此函數可不做操作 returnOK; }intPreOrderTraverse(BiTreeT,int(*Visit)(inte))//采用二叉鏈表存儲結構，visit是對數據元素操作的應用函數，//先序遍歷二叉樹T的遞歸算法，對每個數據元素調用函數visit。//調用實例：PreOrderTraverse(T,printElement);{if(T){if(Visit(T->data))if(PreOrderTraverse(T->lchild,Visit)) if(T->rchild==NULL)count++;//當左右結點都為空時，即是葉子結點if(PreOrderTraverse(T->rchild,Visit))returnOK;returnERROR; }elsereturnOK;}//preOrderTraVersevoidmain(){BiTreet;printf("請按先序遍歷輸入二叉樹（當左右子樹為空時用空格輸入）\n");CreateBiTree(t);PreOrderTraverse(t,PrintElement);printf("該二叉樹的葉子結點的個數為:%d\n",count);}20#include"stdio.h"#include"stdlib.h"#definestackinitsize100#defineOK1#defineERROR0//二叉樹的二叉鏈表存儲結構typedefstructBiTNode{intdata;structBiTNode*lchild,*rchild;//左右孩子指針}BiTnode,*BiTree;intCreateBiTree(BiTree&T){//按先序次序輸入二叉樹中結點的值（一個字符），空格字符表示空樹。//構造二叉鏈表表示的二叉樹T.charch;scanf("%c",&ch);if(ch=='')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(0);T->data=ch;//生成根結點CreateBiTree(T->lchild);//構造左子樹CreateBiTree(T->rchild);//構造右子樹}returnOK;}//CreateBiTree//首先分析二叉樹的深度（高度）和它的左、右子樹深度之間的關系。//從二叉樹深度的定義可知，二叉樹的深度應為其左、右子樹深度的最大值加1。//由此，需先分別求得左、右子樹深度,返回其最大值，然后加1。intGetDepth(BiTreeT){if(T){intdepthLeft=GetDepth(T->lchild);intdepthRight=GetDepth(T->rchild);return(depthLeft>depthRight?depthLeft:depthRight)+1;}elsereturnERROR;}voidmain(){BiTreet;printf("請按先序遍歷輸入二叉樹（當左右子樹為空時用空格輸入）\n");CreateBiTree(t);printf("該二叉樹的高度為:%d\n",GetDepth(t));}21.//21、給出一個無向圖的鄰接矩陣，輸出各個頂點的度。#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;constintmax=50;typedefchartype;typedefstruct{ typevexs[max]; boolarcs[max][max]; intvexnum,arcnum;//頂點個數、邊數}graph;intmain(){ graphg; cin>>g.vexnum>>g.arcnum; inti,j; for(i=0;i<g.vexnum;++i)cin>>g.vexs[i]; memset(g.arcs,0,sizeof(g.arcs)); for(i=0;i<g.arcnum;++i) {intx,y;cin>>x>>y;g.arcs[x][y]=1;g.arcs[y][x]=1; } cout<<"無向鄰接矩陣為:"<<endl; for(i=0;i<g.vexnum;i++){ for(j=0;j<g.vexnum;j++)cout<<g.arcs[i][j]; cout<<endl;} for(i=0;i<g.vexnum;++i) { intamount=0; for(j=0;j<g.vexnum;++j) if(g.arcs[i][j])++amount; cout<<"頂點"<<g.vexs[i]<<"的度為"<<amount<<endl; } return0;}22//22、給出一個有向圖的鄰接矩陣，輸出各個頂點的入度與出度。#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;constintmax=50;typedefchartype;typedefstruct{ typevexs[max]; boolarcs[max][max]; intvexnum,arcnum;//頂點個數、邊數}graph;intmain(){ graphg; cin>>g.vexnum>>g.arcnum; inti,j; for(i=0;i<g.vexnum;++i)cin>>g.vexs[i]; memset(g.arcs,0,sizeof(g.arcs)); for(i=0;i<g.arcnum;++i) {intx,y;cin>>x>>y;g.arcs[x][y]=1; } cout<<"有向鄰接矩陣為:"<<endl; for(i=0;i<g.vexnum;i++){ for(j=0;j<g.vexnum;j++)cout<<g.arcs[i][j]; cout<<endl;} for(i=0;i<g.vexnum;++i) { intin=0,out=0; for(j=0;j<g.vexnum;++j) { if(g.arcs[i][j])++out; if(g.arcs[j][i])++in; } cout<<"頂點"<<g.vexs[i]<<"的出度為"<<out<<"入度為"<<in<<endl; } return0;}23//23、輸入一個有序序列，利用折半查找來查找一個數是否在序列中，//如在，則輸出其位置，否則輸出"NO"。#include<iostream>#include<cstdlib>#include<cstdio>usingnamespacestd;typedefinttype;structsqlist{ type*data; intlength;};intinit_sqlist(sqlist&L,intn){ L.data=(type*)malloc((n+1)*sizeof(type)); if(!L.data)return-2; for(inti=1;i<=n;i++)cin>>L.data[i]; L.length=n; return1;}intbinary_search(sqlistL,typen){ intlow=1,high=L.length,mid; while(low<=high) { mid=(low+high)/2; if(L.data[mid]==n)returnmid; elseif(L.data[mid]<n)low=mid+1; elsehigh=mid-1; } return0;}intmain(){ intn; typet; sqlistL; cout<<"請輸入有序表長度:"<<endl; cin>>n; cout<<"請按從小到大的順序輸入"<<n<<"個元素:"<<endl; init_sqlist(L,n); cout<<"請輸入要查找的數"<<endl; while(cin>>t) { n=binary_search(L,t); if(n)cout<<t<<"在有序表中的位置是"<<n<<endl; elsecout<<t<<"不在有序表中"<<endl; } return0;}24//24、用插入排序方法對一組數據進行排序，并輸出每趟排序的結果。#include<iostream>#include<cstdlib>#include<cstdio>usingnamespacestd;typedefinttype;structsqlist{ type*data; intlength;};intinit_sqlist(sqlist&L,intn){ L.data=(type*)malloc((n+1)*sizeof(type)); if(!L.data)return-2; for(inti=1;i<=n;i++)cin>>L.data[i]; L.length=n; return1;}voidstraight_insert_sort(sqlist&L){ inti,j,k=1; for(i=2;i<=L.length;i++) { if(L.data[i]<L.data[i-1]) { L.data[0]=L.data[i]; for(j=i-1;L.data[0]<L.data[j];j--) L.data[j+1]=L.data[j]; L.data[j+1]=L.data[0]; } cout<<"第"<<k<<"趟排序后序列為:"<<endl; for(j=1;j<=L.length;j++)cout<<L.data[j]<<''; cout<<endl; }}voidbinary_insert_sort(sqlist&L){ inti,j,k; for(i=2;i<=L.length;i++) { L.data[0]=L.data[i]; intlow=1,high=i-1,mid; while(low<=high) { mid=(low+high)/2; if(L.data[0]<L.data[mid])high=mid-1; elselow=mid+1; } for(j=i-1;j>=high+1;--j)L.data[j+1]=L.data[j]; L.data[high+1]=L.data[0]; for(k=1;k<=L.length;++k)cout<<L.data[k]<<''; cout<<endl; }}intmain(){ intn; sqlistL; cout<<"請輸入序列長度"<<endl; cin>>n; cout<<"請輸入"<<n<<"個元素:"<<endl; init_sqlist(L,n); straight_insert_sort(L); //binary_insert_sort(L); return0;}25//25、用選擇排序方法對一組數據進行排序，并輸出每趟排序的結果。#include<iostream>#include<cstdlib>#include<cstdio>usingnamespacestd;typedefinttype;structsqlist{ type*data; intlength