数据结构上机考试(含答案)

数据结构上机考试(含答案)数据结构上机考试(含答案)数据结构上机考试(含答案)xxx公司数据结构上机考试(含答案)文件编号：文件日期：修订次数：第1.0次更改批准审核制定方案设计，管理制度《数据结构》上机练习题1、设有两个有序序列，利用归并排序将它们排成有序表，并输出。2、设有一有序序列，从键盘输入一个数，判别是否在序列中，如果在输出“YSE”；否则，将它插入到序列中使它仍然有序，并输出排序后的序列。3、设有一有序序列，从键盘输入一个数，判别是否在序列中，如果不在，则输出“NO”，否则，将它从序列中删除它，并输出删除后的序列。4、从键盘输入一组任意数据，建立一个有序链表，并从链头开始输出该链，使输出结果是有序的。5、从键盘输入一组任意数据，建立一个包含所有输入数据的单向循环链表，并从链表的任意开始，依次输出该链表中的所有结点。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;//顺序创建链表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("创建两个含%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;//创建链表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;//发现在里面，返回真值 p=p->next;//否则指针后移,继续找 } returnERROR; //未找到，返回假值（没有执行returnOK;语句）}//插入元素voidinsertList(list&l,int&e){ listp,q,s;//q为新插入的元素开辟一个存储空间的指针，s为p前一个指针，方便插入 p=l->next; s=l; while(p) { if(e<=p->data) {//发现要插入的元素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("创建%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;//创建链表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; }//发现在里面，返回真值 p=p->next;//否则指针后移,继续找 } returnERROR; //未找到，返回假值（没有执行returnOK;语句）}//输出链表voidprintList(listl){ listp; p=l->next; while(p) {printf("%d",p->data);p=p->next;}}voidmain(){ listl; inte; printf("创建%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;//创建链表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)//发现前一个比后一个大，交换数据 {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("创建%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;//创建链表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指针指向头结点，构成循环链表}//输出链表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,完成循环输出）}voidmain(){ listl; intpos; printf("创建%d个元素的循环链表，请输入%d个元素：\n",N,N); creatList(l,N); printf("请指明从第几个位置输出循环链表中的元素："); 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;//创建链表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指针指向头结点，构成循环链表}//输出链表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,完成循环输出）}voidmain(){ listl; intpos; printf("创建%d个元素的循环链表，请输入%d个元素：\n",N,N); creatList(l,N); printf("请指明从第几个位置输出循环链表中的元素："); 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;//创建链表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;//发现在里面，返回真值 p=p->next;//否则指针后移,继续找 } //没有执行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("创建%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("请输入要创建栈的元素的个数："); 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，如果不满足，则不匹配，直接退出循环 } 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