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

《数据结构》上机练习题

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

#include

#define N 5

#define NULL 0

//链表的存储结构

typedef struct LNode

{

int data;

struct LNode *next;

}LNode,*list;

//顺序创建链表

void creatList(list &l,int n)

{

}

int i; list p,q; l=(list)malloc(sizeof(LNode)); //开辟头结点 p=l; //指针p 指向头结点 for(i=0;idata); p->next=q; //p的下一个结点指向新开辟的结点q p=q; //将p 指针指向q } p->next=NULL;

//归并排序

void mergeList(list &la,list &lb,list &lc)

{ //将已经排好序的la,lb 中的数重新排列成有序（非递减）

list pa,pb,pc; pa=la->next;pb=lb->next; lc=pc=la; //默认将la 做为lc 的头结点（lb 亦可） while(pa&&pb) { //让pc 接到数据小的结点上，直到pa,pb 两者有一指向空结点 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 有剩余结点，即将其直接加入到lc 中，反之将lb 的剩余结点加到lc 中

} free(lb);

void printList(list l)

{

list p;

p=l->next;

}

void main()

{

}

2. #include

#include

#define N 5

#define NULL 0

#define OK 1

#define ERROR 0

//链表的存储结构

typedef struct LNode

{

int data;

struct LNode *next;

}LNode,*list;

//创建链表

void creatList(list &l,int n)

{

list p,q; l=(list)malloc(sizeof(LNode)); p=l; for(int i=0;idata); p->next=q; list la,lb,lc; printf("创建两个含%d个元素的链表，请输入：\n",N); creatList(la,N); creatList(lb,N); mergeList(la,lb,lc); printList(lc); while(p) { printf("%d ",p->data);p=p->next;}

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; //发现在里面，返回真值 p=p->next; //否则指针后移, 继续找 //未找到，返回假值（没有执行return OK;语句） } return ERROR;

}

//插入元素

void insertList(list &l,int &e)

{

list p,q,s; //q为新插入的元素开辟一个存储空间的指针，s 为p 前一个指针，方便插入

p=l->next; s=l; while(p) { } if(edata) {//发现要插入的元素e 比后面的小, 开辟空间，并将e 放入空间的数据域中 } p=p->next; 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;

}

//输出链表

void printList(list l)

{

list p;

}

{

while(p) { printf("%d ",p->data); p=p->next;} void main() list l; int e; 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

#include

#define N 5

#define NULL 0

#define OK 1

#define ERROR 0

//链表的存储结构

typedef struct LNode

{

int data;

struct LNode *next;

}LNode,*list;

//创建链表

void creatList(list &l,int n)

{

list p,q; l=(list)malloc(sizeof(LNode)); p=l; for(int i=0;i

} p->next=q; p=q; } p->next=NULL;

//判断元素e 是否在链表中

int insertDeleteList(list l,int e)

{

}

//输出链表

void printList(list l)

{

}

void main()

{

list l; int e; printf("创建%d个元素的链表，请输入%d个元素：\n",N,N); creatList(l,N); printf("请输入要判断的元素"); scanf("%d",&e); list p; p=l->next; while(p) { printf("%d ",p->data); p=p->next;} list p,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); return OK; } //发现在里面，返回真值 p=p->next; //否则指针后移, 继续找 //未找到，返回假值（没有执行return OK;语句） } return ERROR;

} printf("NO "); else printList(l);

4. #include

#include

#define N 5

#define NULL 0

#define OK 1

#define ERROR 0

//链表的存储结构

typedef struct LNode

{

int data; struct LNode *next;

}LNode,*list;

//创建链表

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标记排序的轮数 int chang; //用于交换结点中的数据 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; //下一轮比较

//输出链表

void printList(list l)

{

}

void main()

{

} list l; printf("创建%d个元素的链表，请输入%d个元素：\n",N,N); creatList(l,N); sortList(l); printList(l); list p; p=l->next; while(p) { printf("%d ",p->data); p=p->next;}

5. #include

#include

#define N 5

#define NULL 0

#define OK 1

#define ERROR 0

//链表的存储结构

typedef struct LNode

{

int data; struct LNode *next;

}LNode,*list;

//创建链表

void creatList(list &l,int n)

{

}

//输出链表

void printList(list l,int pos)

{

list p,q; int i; p=l; for(i=1;inext; //找到指定位置的前一个位置 q=p->next; do list p,q; l=(list)malloc(sizeof(LNode)); scanf("%d",&l->data); //头结点也添加元素，方便输出 p=l; for(int i=1;idata); p->next=q; p=q; } p->next=l; //让最后一个p->next指针指向头结点，构成循环链表

{

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, 完成循环输出）

}

void main()

{

list l; int pos; printf("创建%d个元素的循环链表，请输入%d个元素：\n",N,N); creatList(l,N); printf("请指明从第几个位置输出循环链表中的元素："); 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

//链表的存储结构

typedef struct LNode

{

int data;

struct LNode *next;

}LNode,*list;

//创建链表

void creatList(list &l,int n)

{

list p,q;

l=(list)malloc(sizeof(LNode));

scanf("%d",&l->data);

p=l;

for(int i=1;i

{

q=(list)malloc(sizeof(LNode));

scanf("%d",&q->data);

p->next=q;

p=q;

}

p->next=l;

链表

}

//输出链表

void printList(list l,int pos)

{

list p,q;

int i; //头结点也添加元素，方便输出 //让最后一个p->next指针指向头结点，构成循环

for(i=1;inext; //找到指定位置的前一个位置

q=p->next;

do

{

if(pos==1) {printf("%d ",p->data); p=p->next;} //如果指定位置为1，即按原样输出

else {p=p->next; printf("%d ",p->data);} //不然，p 先移到指定的位置，输出其数据

}

void main()

{

list l; int pos; printf("创建%d个元素的循环链表，请输入%d个元素：\n",N,N); creatList(l,N); printf("请指明从第几个位置输出循环链表中的元素："); scanf("%d",&pos); while(posN) { printf("输入的位置不存在，请重新输入... "); scanf("%d",&pos); } printList(l,pos); }while(p->next!=q); //结束条件（p 移到的下一个位置不是q ，即不是最初的p, 完成循环输出）

}

12#include

#include

#define N 5

#define NULL 0

#define OK 1

#define ERROR 0

//链表的存储结构

typedef struct LNode

{

int data; struct LNode *next;

}LNode,*list;

//创建链表

void creatList(list &l,int n)

{

} l=(list)malloc(sizeof(LNode)); p=l; for(int i=0;inext=NULL; q=(list)malloc(sizeof(LNode)); scanf("%d",&q->data); p->next=q; p=q;

//判断元素e 是否在链表中

int inList(list l,int e)

{

}

//输出链表

void printList(list l)

{

list p; p=l->next; while(p) { printf("%d ",p->data); p=p->next;} list p,q; q=p=l->next; while(p) { if(p->data==e) return OK; //发现在里面，返回真值 p=p->next; //否则指针后移, 继续找 } //没有执行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 main()

} list l; int e; printf("创建%d个元素的链表，请输入%d个元素：\n",N,N); creatList(l,N); printf("请输入要判断的元素："); scanf("%d",&e); if(inList(l,e)) printf("YES "); else printList(l);

13#include

#include

#define OK 1

#define Error 0

#define NULL 0

#define maxSize 100

//栈的存储结构

typedef struct

{

int *base; int *top; int size;

}stack;

//栈的初始化（顺序存储）

int initStack(stack &s)

{ //开辟maxSize 大小的空间，base 和top 都指向基地址, 同时判断是否开辟成功，不成功返回0

if(!(s.base=s.top=(int*)malloc(maxSize*sizeof(int)))) return Error; s.size=maxSize; //栈的大小为maxSize return OK;

}

//进栈操作

int push(stack &s,int e)

{

*s.top=e; //先将元素e 赋值给s.top 所指的存储空间

s.top++; //top指针上移

}

return OK;

//出栈操作

int pop(stack &s,int &e)

{

if(s.base==s.top) return Error; //如果栈为空，返回0

s.top--; //top指针先后移

}

void main()

{

} stack s; int n,e; printf("请输入要创建栈的元素的个数："); scanf("%d",&n); initStack(s); for(int i=0;i

14#include

#include

#include

#include

#define stackincrement 8

#define OK 1

#define Error 0

#define NULL 0

#define maxSize 100

//栈的存储结构

typedef struct

{

char *base; //由于要存放括号，所以为char 类型

char *top;

int size;

}stack;

//栈的初始化（顺序存储）

int initStack(stack &s)

{ //注意开辟的空间为char 类型

if(!(s.base=s.top=(char*)malloc(maxSize*sizeof(char)))) return Error; s.size=maxSize; //栈的大小为maxSize return OK;

}

//进栈操作

int push(stack &s,int e)

{

*s.top=e; //先将元素e 赋值给s.top 所指的存储空间

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; //如果栈为空，返回0

s.top--; //top指针先后移 e=*s.top; //将其所指的元素值赋给e

return e;

}

//括号匹配

int match()

{

stack s; initStack(s); char ch[100],e; int flag=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

else while(i

{

i++;char t;

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，如果不满足，则不匹配，直接退出循环

} else push(s,ch[i]); //输入的是左括号，直接压入

}

if(!isEmpty(s)) flag=0; //通过不断的压栈和弹栈，如果最后栈不为空，则肯定是左括号多于右括号，不匹配

} return flag;

void main()

{

}

15#include "stdio.h"

#include "stdlib.h"

#define stackinitsize 100

#define OK 1

#define ERROR 0

//二叉树的二叉链表存储结构

typedef struct BiTNode{

int data;

struct BiTNode *lchild,*rchild; //左右孩子指针

}BiTnode,*BiTree;

int CreateBiTree(BiTree &T){

//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。

//构造二叉链表表示的二叉树T.

char ch;

scanf("%c",&ch); int result; printf("判断输入的各种括号是否匹配：\n"); result=match(); if(result) printf("括号匹配正确 ^_^\n"); else printf("括号匹配错误 *.*\n");

if(ch==' ') T=NULL;

else{

if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit(0);

T->data=ch; //生成根结点

CreateBiTree(T->lchild);//构造左子树

CreateBiTree(T->rchild);//构造右子树

}

return OK;

}//CreateBiTree

int PrintElement(int e)

{ //输出元素e 的值

printf("%c",e);

return OK;

}

int InOrderTraverse(BiTree T,int(*Visit)(int e))

//采用二叉链表存储结构，visit 是对数据元素操作的应用函数， //中序遍历二叉树T 的递归算法，对每个数据元素调用函数visit 。 //调用实例： 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("请按先序遍历输入二叉树（当左右子树为空时用空格输入）\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

//二叉树的二叉链表存储结构

typedef struct BiTNode{

int data;

struct BiTNode *lchild,*rchild; //左右孩子指针

}BiTnode,*BiTree;

int CreateBiTree(BiTree &T){

//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。 //构造二叉链表表示的二叉树T.

char ch;

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);//构造右子树

}

return OK;

}//CreateBiTree

int PrintElement(int e)

{ //输出元素e 的值

printf("%c",e);

return OK;

}

int PreOrderTraverse(BiTree T,int(*Visit)(int e))

//采用二叉链表存储结构，visit 是对数据元素操作的应用函数， //先序遍历二叉树T 的递归算法，对每个数据元素调用函数visit 。 //调用实例： 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;

}//preOrderTraVerse

void main()

{

BiTree t;

printf("请按先序遍历输入二叉树（当左右子树为空时用空格输入）\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

//二叉树的二叉链表存储结构

typedef struct BiTNode{

int data;

struct BiTNode *lchild,*rchild; //左右孩子指针

}BiTnode,*BiTree;

int CreateBiTree(BiTree &T){

//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。 //构造二叉链表表示的二叉树T.

char ch;

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);//构造右子树

}

return OK;

}//CreateBiTree

int PrintElement(int e)

{ //输出元素e 的值

printf("%c",e);

return OK;

}

int PostOrderTraverse(BiTree T,int(*Visit)(int e))

//采用二叉链表存储结构，visit 是对数据元素操作的应用函数， //后序遍历二叉树T 的递归算法，对每个数据元素调用函数visit 。 //调用实例： 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("请按先序遍历输入二叉树（当左右子树为空时用空格输入）\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 0

static int count=0;

//二叉树的二叉链表存储结构

typedef struct BiTNode{

int data;

struct BiTNode *lchild,*rchild; //左右孩子指针

}BiTnode,*BiTree;

int CreateBiTree(BiTree &T){

//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。 //构造二叉链表表示的二叉树T.

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);//构造右子树

}

return OK;

}//CreateBiTree

int PrintElement(int e)

{ //记录遍历结点数

count++;

return OK;

}

int PreOrderTraverse(BiTree T,int(*Visit)(int e))

//采用二叉链表存储结构，visit 是对数据元素操作的应用函数，

{

if(T){

if (Visit(T->data))

if (PreOrderTraverse(T->lchild,Visit))

if (PreOrderTraverse(T->rchild,Visit)) return OK;

return ERROR;

}else return OK;

}//preOrderTraVerse

void main()

{

BiTree t;

printf("请按先序遍历输入二叉树（当左右子树为空时用空格输入）\n");

CreateBiTree(t);

printf("该二叉树的总结点数为: ");

PreOrderTraverse(t,PrintElement);

printf("%d\n",count);

}

19#include "stdio.h"

#include "stdlib.h"

#define stackinitsize 100

#define ERROR 0

static int count=0;

//二叉树的二叉链表存储结构

typedef struct BiTNode{

int data;

struct BiTNode *lchild,*rchild; //左右孩子指针

}BiTnode,*BiTree;

int CreateBiTree(BiTree &T){

//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。

//构造二叉链表表示的二叉树T.

char ch;

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);//构造右子树

}

return OK;

}//CreateBiTree

int PrintElement(int e)

{ //判断叶子结点的个数，此函数可不做操作

return OK; }

int PreOrderTraverse(BiTree T,int(*Visit)(int e))

//采用二叉链表存储结构，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)) return OK;

return ERROR;

}else return OK;

}//preOrderTraVerse

void main()

{

BiTree t;

printf("请按先序遍历输入二叉树（当左右子树为空时用空格输入）\n"); CreateBiTree(t);

PreOrderTraverse(t,PrintElement);

printf("该二叉树的叶子结点的个数为: %d\n",count);

}

20#include "stdio.h"

#include "stdlib.h"

#define stackinitsize 100

#define OK 1

#define ERROR 0

//二叉树的二叉链表存储结构

typedef struct BiTNode{

int data;

struct BiTNode *lchild,*rchild; //左右孩子指针

}BiTnode,*BiTree;

int CreateBiTree(BiTree &T){

//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。 //构造二叉链表表示的二叉树T.

char ch;

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);//构造右子树

}

return OK;

}//CreateBiTree

//首先分析二叉树的深度（高度）和它的左、右子树深度之间的关系。

//从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。 //由此，需先分别求得左、右子树深度, 返回其最大值，然后加 1 。

int GetDepth(BiTree T){

if(T)

{

int depthLeft = GetDepth( T->lchild );

int depthRight= GetDepth( T->rchild );

return (depthLeft>depthRight?depthLeft:depthRight)+1;

}

else return ERROR;

}

void main()

{

BiTree t;

printf("请按先序遍历输入二叉树（当左右子树为空时用空格输入）\n"); CreateBiTree(t);

printf("该二叉树的高度为: %d\n",GetDepth(t));

}

21. // 21、给出一个无向图的邻接矩阵，输出各个顶点的度。

#include

#include

#include

using namespace std;

const int max=50;

typedef char type;

typedef struct

{

type vexs[max]; bool arcs[max][max]; int vexnum,arcnum;//顶点个数、边数

}graph;

int main()

{

graph g; cin>>g.vexnum>>g.arcnum; int i,j; for(i=0;i>g.vexs[i]; memset(g.arcs,0,sizeof(g.arcs)); for(i=0;i

cin>>x>>y;

g.arcs[x][y]=1;

g.arcs[y][x]=1;

}

cout

for(i=0;i

{

for(j=0;j

cout

}

for(i=0;ireturn 0;

}

22//22、给出一个有向图的邻接矩阵，输出各个顶点的入度与出度。

#include

#include

#include

using namespace std;

const int max=50;

typedef char type;

typedef struct

{

type vexs[max];

bool arcs[max][max]; int vexnum,arcnum;//顶点个数、边数

}graph;

int main()

{

graph g; cin>>g.vexnum>>g.arcnum; int i,j; for(i=0;i>g.vexs[i]; memset(g.arcs,0,sizeof(g.arcs)); for(i=0;i

{ int x,y;

cin>>x>>y;

g.arcs[x][y]=1;

} cout

for(i=0;i

{

for(j=0;j

cout

}

for(i=0;i

{

int in=0,out=0; for(j=0;j

}

23//23、输入一个有序序列，利用折半查找来查找一个数是否在序列中，

//如在，则输出其位置，否则输出"NO" 。

#include

#include

#include

using namespace std;

typedef int type;

struct sqlist

{

type *data; int length;

};

int init_sqlist(sqlist &L,int n)

{

}

int binary_search(sqlist L,type n)

{

int low=1,high=L.length,mid; while(low>L.data[i]; L.length=n; return 1;

}

{

else if(L.data[mid]>n; cout>t) { n=binary_search(L,t); if(n) cout

return 0;

}

24//24、用插入排序方法对一组数据进行排序，并输出每趟排序的结果。

#include

#include

#include

using namespace std;

typedef int type;

struct sqlist

{

type *data; int length;

};

int init_sqlist(sqlist &L,int n)

{

}

L.data=(type *)malloc ((n+1)*sizeof(type)); if(!L.data)return -2; for(int i=1;i>L.data[i]; L.length=n; return 1;

void straight_insert_sort(sqlist &L)

{

int i,j,k=1; for(i=2;i

}

void binary_insert_sort(sqlist &L)

{

}

{

int i,j,k; for(i=2;i=high+1;--j)L.data[j+1]=L.data[j]; L.data[high+1]=L.data[0]; for(k=1;k>n; cout

straight_insert_sort(L);

//binary_insert_sort(L);

return 0;

}

25//25、用选择排序方法对一组数据进行排序，并输出每趟排序的结果。

#include

#include

#include

using namespace std;

typedef int type;

struct sqlist

{

type *data;

int length;

};

int init_sqlist(sqlist &L,int n)

{

L.data=(type *)malloc ((n+1)*sizeof(type));

if(!L.data)return -2; for(int i=1;i>L.data[i];

L.length=n;

return 1;

}

void select_sort(sqlist &L)

{

int i,j,k,cur=1; for(i=1;iL.data[j])

{min=L.data[j];k=j;}

if(k!=i)

}

int main()

{

int n; sqlist L; } { type t=L.data[k];L.data[k]=L.data[i];L.data[i]=t; } cout

cout>n; cout

}

26//26、用希尔（SHELL ）排序方法对一组数据进行排序，并输出每趟排序的结果。 //掌握得不是很好

#include

#include

#include

using namespace std;

typedef int type;

struct sqlist

{

type *data;

int length;

};

int init_sqlist(sqlist &L,int n)

{

} L.data=(type *)malloc ((n+1)*sizeof(type)); if(!L.data)return -2; for(int i=1;i>L.data[i]; L.length=n; return 1;

void Shell_Sort(sqlist &L,int dlta[],int t)

{

int i,j,k,cur=1;

for(k=0;k0&&L.data[0]

}

cout

for(i=1;i

cout

}

}

int main()

{

int n,dlta[3]={5,3,1};

}

/*

10

49 38 65 97 76 13 27 49 55 04

*/

27. //27、用快速排序方法对一组数据进行排序，并输出每趟排序的结果。．

#include

#include

#include

using namespace std;

typedef int type;

struct sqlist

{

type *data;

int length;

};

int init_sqlist(sqlist &L,int n)

{

L.data=(type *)malloc ((n+1)*sizeof(type));

}

void Quick_Sort(sqlist &L,int low,int high)

{

if(low>L.data[i]; L.length=n; return 1; sqlist L; cin>>n; init_sqlist(L,n); Shell_Sort(L,dlta,3);

{ while(low1=key)--high1; L.data[low1]=L.data[high1]; while(low1

}

}

int main()

{

} int n; sqlist L; cin>>n; init_sqlist(L,n); Quick_Sort(L,1,n);